568
\$\begingroup\$

This "sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to main. This is useful because writing a clear and fully specified challenge on your first try can be difficult, and there is a much better chance of your challenge being well received if you post it in the sandbox first.

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

\$\endgroup\$
0

4557 Answers 4557

1
84 85
86
87 88
152
1
\$\begingroup\$

WumpusWars King of the Hill

This is probably going to stay in the sandbox for a few weeks, until I get the time to write the actual scoring code up... Yep, I'm both lazy and busy :P I'm not very good at coding challenges but I'm good at thinking up creative ideas, so this time my idea is to try reviving the genre of KotH, as the last one on this site (Crazyhouse Chess) has been very unsuccessful (0 submissions for pretty obvious reasons) and the others are all many months old...

Inspired by Hunt the Wumpus, an early command line game. It is somewhat popular among esolang communities as a programming challenge, especially for languages like Befunge. However, the original, singleplayer version is boring, so I wanna upgrade it. Hence I created WumpusWars, a better version of it!

Story: You are a brave hunter in a dark cave, trying to kill the Wumpus, a mysterious monster. You start with 5 arrows that can kill the Wumpus if you shoot the arrow into the same room as the Wumpus. The cave consists of large rooms and small passageways in between. It can be represented, hence, with a graph, so that the rooms are nodes/vertices and the passageways are edges. There are a total of 50 vertices in the graph, each of them having a degree of at least 3, and the graph is guaranteed to be connected. Rooms are numbered from 0 to 49. You are spawned in a random room.

The place is so dark that you cannot see anything, but you can feel, smell, and hear. Hence you have access to the functions listed in the source code below. Lemme explain what the functions are associated with in more detail:

  1. Bats: There are 5 rooms in total that contain bats. Entering one of them will cause you to be carried away to a random empty room ("empty room" defined as a room without bats, pits, players, or the wumpus, but there can be corpses in the room).
  2. Pits: There are 5 rooms in total that contain a pit. Entering one of them will cause you to BOOM! CLASH! CRACK!
  3. Wumpus: It remains in its own room unless either an arrow is shot by anyone anywhere, or the game is in deathmatch mode (see gamemode list for explanation). If it enters your room then... You know what. When an arrow is shot or in deathmatch mode it moves randomly to adjacent rooms. Bats and pits do not affect it.
  4. Players: Other players. Note that you cannot shoot a player in the same room as you because the arrow is magically explosive and shooting in the same room as your own will cause you to BOOM! CLASH! CRACK!
  5. Corpse: When a player is killed by anything except a pit they become a corpse, and corpses don't move (obviously). You can collect arrows from the corpses, and if the corpse has already been arrow-collected there will be 0 arrows on it.

Also, every 10 rounds an arrow will spawn in an empty room. Entering that room will cause your number of arrows to be incremented by 1. Multiple arrows can spawn in the same room which gives you several at once, but that's pretty rare.

You need to write a player program in Python and submit it as an answer to the post. Use the "PlayerName" class template. You will have to define with the participate function which gamemodes are you participating in (the input to the function will be one of the abbreviation strings):

  1. Singleplayer (abbrev: "SP"). Precisely what the name says. Your score is the percentage of games in which you win (by shooting the Wumpus with an arrow). You lose if you die. After 100 rounds the game enters deathmatch mode, where the Wumpus keeps moving randomly every round regardless of whether an arrow is shot.
  2. Player vs Environment (abbrev: "PVE"). Same as singleplayer except that there are multiple players. The winner is the one who kills the Wumpus (if multiple players shoot it in the same round they split the point equally). If everyone dies then no one wins. Arrows have no effect on players. Deathmatch starts after 20*n rounds, where n is the number of players.
  3. Player vs Player (abbrev: "PVP"). Kinda PVE inverted. The Wumpus is now immortal –– but the players are not! If you get shot by other players or get eaten by the Wumpus you die and lose. The last one standing is the winner. If multiple people die last in the same round they split the point equally. It's deathmatch from start to finish.
  4. Among Us (abbrev: "IP" for Imposter and "CM" for Crewmate). The Wumpus is immortal. Some players become impostors. Others are crewmates. Impostors get 3 arrows at the beginning (number might change according to # of players). Crewmates start with no arrows (but can still pick randomly spawned arrows up). Crewmates are immune from arrows fired by other crewmates. If all impostors die then all crewmates (dead or alive) win a point. If all crewmates die then all impostors (dead or alive) win a point. No deathmatch.

If you have any ideas please lemme know!

Source code:

class Environment:
    def __init__():
        # Hidden
    def legal_moves(player) -> list:
        # Returns an ordered list of adjacent rooms
        # Example: [5, 8, 10]
    def bats(player) -> bool:
        # True if bats are in adjacent rooms, false otherwise
    def pits(player) -> bool:
        # True if pits are in adjacent rooms, false otherwise
    def wumpus(player) -> bool:
        # True if wumpus is in adjacent rooms, false otherwise
    def others(player) -> bool:
        # True if the shortest path from you to the nearest player passes at most 2 edges.
    def arrows(player) -> int:
        # Returns the number of arrows player has
    def corpse(player) -> list:
        # Returns a list of integers
        # The length of the list is the number of corpses in the player's room
        # Elements in the list are the number of arrows on each corpse
    # Other functions hidden

Template:

class PlayerName: # Change the name!
    def __init__(mode:str, room:int, env):
        # Gamemode. Such as 'SP'.
        self.mode = mode
        # Current room number.
        self.room = room
        # Environment
        self.env = env
    def participate() -> bool:
        # Add code here...
        
        # Return True if self.mode is a supported gamemode
        # False if not
    def action() -> tuple:
        legal_moves = self.env.legal_moves(self)
        bats = self.env.bats(self)
        pits = self.env.pits(self)
        wumpus = self.env.wumpus(self)
        others = self.env.others(self)
        arrows = self.env.arrows(self)
        corpse = self.env.corpse(self)

        # No methods or variables from Environment class allowed below here!
        # Suggested to first check which gamemode and use strats accordingly.

        # Add code here...

        # Return a tuple of type (bool, int)
        # The bool is True for shooting, False for moving
        # The int is the cave number to shoot or move to
        # An illegal move signifies doing nothing
```
\$\endgroup\$
1
\$\begingroup\$

Write a Turing machine that draws this fractal

This challenge is inspired by and similar to my other challange about a fractal matrix, but uses a slightly different matrix (for n up to 3 the matrices are nearly the same, but for n >= 4 they start to differ more significantly)


A 2D-Turing machine is like a regular Turing Machine but the memory tape is 2 dimensional, meaning that after each step you can in addition to moving left or right also move up or down.

[...]

Your task is to create a 2 dimensional Turing machine that prints the infinite fractal matrix generated by the following procedure:

  • Start with a single cell, set it to 1
  • repeat n times:
  1. add a copy of the previous matrix to the left of the previous matrix
  2. add a copy of the previous matrix below the previous matrix
  3. add a copy of the previous matrix with 1 and 0 swapped, diagonally to the bottom right of the previous matrix.

First few steps:

n=0:

1

n=1:

1 1
1 0

n=2:

1 1 1 1
1 0 1 0
1 1 0 0
1 0 0 1

n=3:

1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0
1 1 0 0 1 1 0 0
1 0 0 1 1 0 0 1
1 1 1 1 0 0 0 0
1 0 1 0 0 1 0 1
1 1 0 0 0 0 1 1
1 0 0 1 0 1 1 0

n=4:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0
1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1
1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0
1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1
1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1
1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1
1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1
1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0
1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1
1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0
1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

Rules:

  • It is allowed to output/display any two (distinguishable) distinct cells values for the two different values in the matrix

  • Cells inside the matrix have to have the correct value more that 50% of the time (\$\lim_{steps \to \infty} \frac{correct}{steps} >0.5\$)

  • Cells outside the matrix should be empty more that 50% of the time.

  • The score of an answer is the number of distinct cell values used times the number of states of the Turing machine

  • This is the solution with the lowest score wins

related: generate the matrix


Meta:

  • Is this a duplicate?

  • Is my explanation clear?

  • Should I link to an example implementation of a 2D Turing machine?

\$\endgroup\$
2
  • \$\begingroup\$ I feel like saying "it differs for n>=4" suggests you might want an example for n = 4 at least :) \$\endgroup\$
    – RubenVerg
    Jul 22 at 18:06
  • \$\begingroup\$ Duplicate? \$\endgroup\$
    – alephalpha
    Jul 28 at 7:43
1
\$\begingroup\$

Pack the sequence!

You have a list of sequences of numbers (1 byte max, unsigned) as an input, e.g.:

4 6 4 9 3 15 150
3 2 1
9 6 4 1
…

Your task is to pack as many of them as possible into the square composed from the numbers from this list - the size of square is also an input.

The square of size 4 may look like:

10 13 56 30
98 11 10  4
15 36 77 86
 1  1 45 11

The numbers may repeat as many times as you want.

The sequence is considered "packed" if you can draw the line from the first number inside square to the next adjacent number in sequence and so on. Each number may be used only once for a single sequence.

For example, the sequence 36 11 77 11 is packed into the square above - the number may have up to 8 adjacent numbers: top, left, right, bottom and diagonals. While the sequence 11 36 10 11 is not - since the same number 11 can't be used twice.

Scoring

For the packed sequence of size S you get 2^S scores. Each sequence counts only once - even if you can pack it multiple times in the same square.

Victory Condition

The algorithm wins if it outputs the square of expected size with the maximum scoring for some hidden test lists. The algorithm is expected to be general enough to work with any random list.

Output

Program should output square as a sequence of numbers on a single line. For example: 1 2 3 4 5 6 7 8 9 is the square of size 3:

1 2 3
4 5 6
7 8 9

Limitations

  • Any list contains [1, 1000000] sequences.
  • Any sequence contains [N, 20] numbers, where N is size of square.
  • The size of square N is [2, 10].
  • Program should use no more than 1Gb of user-space memory.
  • Program should work no more than 60 seconds and use a single thread.
  • Program may output more than one square - one per line. The last full square after 60 seconds is considered the answer.
\$\endgroup\$
2
  • \$\begingroup\$ It's too likely that no two number is same, and best solution is trivial \$\endgroup\$
    – l4m2
    Aug 1 at 6:07
  • \$\begingroup\$ How is it likely? Numbers are limited in [0, 255]. Max possible 1000000*20 = 2'000'000 numbers in the list - they are definitely likely to be the same. Also in some test scenarios specifically numbers can be tuned to be in much smaller interval like [0, 9] only. \$\endgroup\$
    – abyss.7
    Aug 1 at 7:46
1
\$\begingroup\$

The New York Times have a new game -

Letter Boxed

(try it at https://www.nytimes.com/puzzles/letter-boxed, the rules below match it).

The game consists of a square, with three Letters on each side. The aim of the game is to join the letters to make words. Each word must start with the last letter of the previous word; and each letter must not share a side of the square with the previous letter. The aim is to solve (use all of the letters at least once) in as few words as possible.

For example:

  H  E  M

O         U

S         R

W         N

  A  I  G

You could use all of the letters in one go to form the word Housewarming, but Swim would be forbidden because the S and the W are consecutive and share a side on the square.

Additionally, HOUSE followed by ERGO would be allowed, but HOUSE followed by WARM would not because they don't share a last/first letter (E->W).

Letters can be repeated (e.g. WEARER), but not sequentially (so SEEN is forbidden), because they share a side.

The challenge

, usual rules.

The aim is to write a program that takes in the set of letters in any reasonably form (a string, or an array of arrays, for example); along with a word list (or you can read the word list in your code for free).

The output should be a word of sequential list of words that solve the puzzle by using all of the letters at least once.

The puzzle will always be solvable for the letters and word list given, but not always in one word.

\$\endgroup\$
1
\$\begingroup\$

Comment Out the Comment

I'm back! Lately I've been working on something, but finally I've finished it and can return to CGCC! I'll be continuing the Fast & Golfiest Series soon, and also try to start working on (given I have the time and energy) WumpusWars. For now, a new question as a gift for everyone!

In LaTeX if you type %a, the a would be commented out. But if you type \%a, the a would still be there because the backwards slash converted the meaning of %. And if you type \\%a, the a would be commented out because the first backwards slash converted the meaning of the second one. So do you know what happens to the a if you type \\\\\\\\\\\%\\\%a? (Answer: The a is not commented out).

This is a code golf challenge so shortest code wins: the input is a string which consists exclusively of \ and %, except that at the end there is always %a. Output 1 or True if the a is commented out, and 0 or False otherwise.

\$\endgroup\$
2
  • \$\begingroup\$ Is \a valid?. \$\endgroup\$
    – l4m2
    Aug 12 at 3:02
  • \$\begingroup\$ @l4m2 Thanks for pointing that out! No. I'll add that a is always preceded by %. \$\endgroup\$ Aug 12 at 3:03
1
\$\begingroup\$

How Turing complete is you language?

\$\endgroup\$
4
  • \$\begingroup\$ The premise is good, but I don't think the definition of "syntax character" is helpful here. It just moves the problem from languages that have "all TC sets must contain X" to those that have "all TC sets must contain either X or Y". \$\endgroup\$
    – Bubbler
    Aug 14 at 10:15
  • \$\begingroup\$ @Bubbler Do you think allowing to reuse characters is bad in general (which would make solutions in most normal languages impossible) or do you think I have to improve my definition for which characters I allow to reuse. \$\endgroup\$
    – bsoelch
    Aug 14 at 11:46
  • \$\begingroup\$ Yes to the former. Arbitrary rules like that tend to not go well, mainly because there are so many different langs and different (often unexpected) ways they work. It isn't that trivial even in the case of Python (you can write nontrivial programs without whitespace). So let's just take the task literally and see what creative stuff people can come up with. \$\endgroup\$
    – Bubbler
    Aug 14 at 12:39
  • \$\begingroup\$ @Bubble you may be right, I tried to find two disjoint Turing complete sets in Python and the main limiting factors seems to be the letter enot : or \n as I previously expected \$\endgroup\$
    – bsoelch
    Aug 14 at 12:46
1
\$\begingroup\$

Optimal Duck Game Moves

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I would prefer if the instructions were in the post itself, they aren’t that long. \$\endgroup\$
    – noodle man
    Aug 6 at 14:55
1
\$\begingroup\$

The rectangle spanned by two numbers

\$\endgroup\$
1
\$\begingroup\$

Print every Unicode character (almost)

Print every Unicode character, except U+0000. Any order is allowed.

Specification

Every Unicode character from U+0001 to U+10FFFF, inclusive. Exclude U+D800 to U+DFFF inclusive as apparently these 'surrogates' cause weird behaviour.

To be honest, I don't know much about Unicode so before this gets posted someone will have to fill me in on how Unicode works

\$\endgroup\$
4
  • 2
    \$\begingroup\$ This might be more suitable as a CMC. \$\endgroup\$
    – Adám
    Aug 23 at 11:53
  • 1
    \$\begingroup\$ Please remove your edit in all caps and/or change it to not be in caps. This just clutters the post. \$\endgroup\$ Aug 23 at 15:32
  • 4
    \$\begingroup\$ Does this include non-printable (e.g. U+00) / unassigned (e.g. U+D800-U+D8FF) Unicode characters? \$\endgroup\$
    – bsoelch
    Aug 23 at 17:37
  • \$\begingroup\$ What's a CMC? @Adám || EDIT: nvm found it "chat mini challenge" \$\endgroup\$
    – W D
    Aug 24 at 6:15
1
\$\begingroup\$

Multiply multivariate polynomials

\$\endgroup\$
1
\$\begingroup\$

Make a braille cribbage board

The braille characters lie in the range U+2800 () to U+28FF (), making it a SBCS (Single Byte Character Set). Oddly enough, the braille patterns look a lot like holes in a cribbage board. Here is an image of one of the many cribbage boards for reference:

Cribbage Board

So you must print this pattern:

+-------+
|⣀⣀⠀⣿⠀⣀⣀|
|⣿⣿⠀⠀⠀⣿⣿|
|⣿⣿⠀⠀⠀⣿⣿|
|⣿⣿⠀⠀⠀⣿⣿|
|⣿⣿⠀⠀⠀⣿⣿|
|⣿⣿⠀⠀⠀⣿⣿|
|⣿⣿⠀⠀⠀⣿⣿|
|⣿⣿⠀⠀⠀⣿⣿|
|⠉⠉⠀⣿⠀⠉⠉|
+-------+

Note that the blanks are U+2800 and NOT the space.

,? is ,7tag3code-golf7'1 s %orte/ code w9s6

Oh, we're not using grade 2 contracted braille. You're not blind.

This is , so shortest code wins!


\$\endgroup\$
0
1
\$\begingroup\$

Half even rounding

\$\endgroup\$
1
  • \$\begingroup\$ As far as I know, PowerShell and brev also use banker's rounding, and some languages like Jelly that may be similar/based on Python may have a built-in that's a "Python round() function" || also, you may want to specify that this is Python 3 behaviour \$\endgroup\$
    – W D
    Aug 22 at 9:24
1
\$\begingroup\$

Implement RAID

RAID, or Redundant Array of Independent Disks is a way to efficiently store data in such a way that if any one disk fails you can still recover the data. Instead of implementing the official protocol, any function that can preserve data counts.

Your task is to produce two functions.

The first is the encoder. Given N lists with M elements each, produce N+1 lists with M elements each. What these lists contain is up to you.

The second part is the recovery system. Take as input the lists produced by the encoded, except one is missing. You must be able to recover the original data no matter which of the lists is gone.

Each list should contain only integers between 0 and 255. It is your choice how to represent the empty list, for example you can:

  • Replace it with an empty list
  • Replace it with a non-list value like None
  • Prefix all present lists with a 1 and the missing list with 0.
  • Take as a separate input which list is missing then just zero out the values.

Example

A basic XOR based solution could look like this:

Encoder:

def encode(list_of_lists):
    return [*list_of_lists, [reduce(lambda a,b:a^b, i) for i in zip(*list_of_lists)]]

def decode(list_with_one_removed):
    return [
        (i if i else [reduce(lambda a,b:a^b, j) for j in zip(*(k for k in list_with_one_removed if k))
        for i in list_with_one_removed
    ][:-1]

You don't need to use a XOR based solution, as long as you can extract the original data again your solution is valid.

\$\endgroup\$
1
\$\begingroup\$

Efficiently solve quadratic equations when 1+1=0

This is a sequel to my previous challenge about solving quadratic equations in the shortest possible code, this challenge is about solving the same task the fastest possible way

The goal of this challenge is to find a solutions for a general quadratic polynomial ax²+bx+c. Meaning be an integer r such that a*r*r+b*b+c is zero, with + meaning exclusive or and * being carry-less multiplication (use xor as addition in binary long multiplication).

To simplify the problem, you can assume that both a and b are one, so you only have to solve equations of the form r*(r+1)=n for an integer n. As any quadratic equation can be converted in this normal form, this is enough to solve the general case (up to linear transformations)

Your challenge will be to solve this simplified equation in the most efficient way possible.

Input: An integer n Output: A number r such that r*(r+1)=n with * being multiplication without carry and + being exclusive or.

Rules:

  • You may assume there is an integral solution to the equation
  • You only have to return one of the two roots (the other root will only differ in the last bit)
  • You program should be able to handle inputs up to at least 0x5555555555555555aaaaaaaaaaaaaaaa
  • The algorithm you are using should work for arbitrarily large n
  • The program with the lowest time complexity in n wins
  • For your score you can assume that xor-addition and xor-multiplication are computed in O(1) (even if your program might need O(n²) operations)
  • If multiple programs have the same complexity, the shortest program (per language) wins

Examples (both possible solutions given):

6 -> 2 | 3
20 -> 4 | 5
18 -> 6 | 7
72 -> 8 | 9
78 -> 10 | 11
...
113427455640312821160607117168492587690 = 0x5555555555555555aaaaaaaaaaaaaaaa -> 0xfffffffffffffffe | 0xffffffffffffffff

Meta

  • Would this be an interesting challenge ?
  • Should I extend the challenge to general polynomials (this can be done in O(1) multiplications/divisions after solving the original problem (or computing the normal square root in some cases))?
  • Is the rule about multiplication&addition do not count towards the complexity clear?
\$\endgroup\$
1
\$\begingroup\$

Golf the fast growing hierarchy

\$\endgroup\$
2
  • \$\begingroup\$ Looks like a really interesting challenge; but you might want to be careful with languages saying "oh but my biggest integer value is [X small number] so I only have to deal with that case" \$\endgroup\$
    – W D
    Aug 22 at 8:12
  • 2
    \$\begingroup\$ @WD That would abuse the loophole "Abusing native number types to trivialize the challenge". \$\endgroup\$ Sep 3 at 15:01
1
\$\begingroup\$

Simulate Round Robin Scheduling

\$\endgroup\$
1
\$\begingroup\$

Fastest decimal to binary

Same challenge, but code golf

Given a decimal number, your task is to convert it to binary.

Test cases

8496867758 -> 111111010011100111110100110101110
28284301455933783441 -> 11000100010000110000001100101000101001000111111110011110110010001
701550526345030865283462565098928586836 -> 1000001111110010011011011101110100010101010100010110011100010101100110100000111111010100100011101000000011010011011100000001010100

Rules

  • You can take input either as a string containing decimal digits, or a list of decimal digits.
  • You need to output the number in binary, either as a string containing the binary digits or a list of binary digits.
  • You are allowed to have leading zeros in the output.
  • The input won't contain leading zeros.

Scoring

Your score is the maximum number of digits your code can handle in under a second on my computer (Intel Core i7-9700 with 8 threads, 32GB RAM). If your code takes less than a second for a number with a million digits, you beat all solutions which can't do that, and the tie-breaker is the time it takes for a million digit number.

To calculate the time I will randomly select 10 numbers, and look at the average time.

Meta question

Is this a dupe? I looked for this question but couldn't find it.

I noticed that using GMP's standard I/O functions this takes 0.05 seconds for a million digit number. Is there a point to this question, or is it likely GMP is optimized enough that this will be the winning solution?

\$\endgroup\$
6
  • \$\begingroup\$ Will the program be reset between calls or is it allowed to reuse temporary values (e.g powers of 10) computed in the first call for the other 9 calls \$\endgroup\$
    – bsoelch
    Sep 21 at 15:35
  • \$\begingroup\$ @bsoelch I'd say it's reset between calls, although allowing precomputation somehow might be good? I'm not sure what would be more interesting. \$\endgroup\$ Sep 21 at 15:39
  • \$\begingroup\$ On my computer time python3 -c 'bin(int("1"*1000000))' executes for 4 seconds \$\endgroup\$
    – l4m2
    Sep 22 at 0:31
  • \$\begingroup\$ About GMP: You could ban third party libraries. At least in Python the standard library version of string to int is not the fastest possible solution (I tried a relatively simple recursive approach and managed to get the time for 1000000 digits from over 4 seconds to below one second). \$\endgroup\$
    – bsoelch
    Sep 22 at 17:20
  • 1
    \$\begingroup\$ Bad news: Python is probably getting an impl that can convert 4,000,000-digit numbers in 0.3s. It is already available as a 3rd party lib. github.com/python/cpython/issues/90716#issuecomment-1717742073 \$\endgroup\$
    – Bubbler
    Sep 25 at 6:32
  • 1
    \$\begingroup\$ Also there is very little point in banning 3rd party libs, as you can always copy the entire code to submit it anyway. \$\endgroup\$
    – Bubbler
    Sep 25 at 6:38
1
\$\begingroup\$

Barbrack

Your task is to write a program or function that takes a non-negative integer (in decimal or any other convenient base for your language) and output a number in the numbering system Barbrack.

What's that?

Barbrack is a numbering system I made up that can represent non-negative integers. Zero is represented with an empty string or an underscore, one is represented with [], and all other positive integers can be represented with a brack.

A brack is delimited with brackets [] and works as follows (with an example of 84):

  1. Take your number a and find its prime factorization. In this case, the prime factorization of 84 is 22*31(*50)*71.
  2. Find the indices of these primes, where the index of 2 is 1. In this case, the index of 3 is 2, since it's the prime right after 2, and the index of 7 is 4, since it's the fourth prime.
  3. Take the exponents of each prime, and put them in brackets in increasing order of the size of the prime, with consecutive exponents being separated by bars (|). So the general format is [exponent of 2|exponent of 3|exponent of 5…]—in this case, [2|1|0|1]. Minimize the number of cells!
  4. Recursively calculate the exponents in Barbrack, remembering that 0 is the empty string and 1 is []. So [2|1|0|1] => [[1]|[]||[]] => [[[]]|[]||[]].
  5. Output the final result.

Test inputs

0 -> (nothing)
1 -> []
2 -> [[]]
5 -> [||[]]
45 -> [|[[]]|[]]
84 -> [[[]]|[]||[]]
65535 -> [|[]|[]||||[](48 bars)[]]
65536 -> [[[[[]]]]]

(sidenote: (48 bars) means 48 consecutive bars in the actual output)

Rules

Scoring

Minimum bytes on a per-language basis.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Can characters other than [|] be used? \$\endgroup\$
    – lyxal
    Sep 24 at 23:59
  • \$\begingroup\$ No, actually. I would allow other symbols, but I'm trying to stay true to my own base. (Let me guess, angle brackets for Vyxal?) \$\endgroup\$
    – Someone
    Sep 25 at 0:02
  • \$\begingroup\$ @Someone It's generally preferred to be flexible with the output format. There's no reason for those characters specifically to be used, as far as I can tell. In fact, instead of strings, you could allow nested lists too (unless I'm reading the challenge wrong) \$\endgroup\$
    – user
    Sep 25 at 1:15
  • \$\begingroup\$ Yeah, the /10 bonus was definitely imbalanced. \$\endgroup\$
    – Someone
    Sep 25 at 12:56
  • \$\begingroup\$ Input validation is generally discouraged. Is there a particular reason you want it? How would it even work if I write a function which takes unsigned int as input? \$\endgroup\$ Sep 25 at 18:45
  • \$\begingroup\$ Fair point. The rule was basically just "undefined behavior" but dumber anyway. \$\endgroup\$
    – Someone
    Sep 25 at 18:47
1
\$\begingroup\$

Golf my code


For this challenge, I'll use edit histories of answers to create a dataset of answers that have been golfed. Your task will be to write a program/function that, given a submission that was golfed in the future, will attempt to golf the submission.

You may choose the language, out of a set I'll choose based on the quantity and quality of data available, that your inputs will be in. You may choose to take inputs from multiple languages, which will not be differentiated (e.g., you can choose to score your answer over a combined Python + Jelly dataset).

The first part of your score will be the sum of bytes golfed by your program for each input, with any submissions that don't become shorter (including becoming longer) or become invalid having no impact on your score (might change this later, since otherwise you have no reason not to use a dataset of all languages).

Your final score will be your score, minus the number of bytes in your program. So, if you golf a total of 1920 bytes off the Python answers dataset, with 1080 bytes of code, your final score will be 840. Higher scores are better.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I get the idea that the program is supposed to golf answers in a specific language, but I don't understand how we're expected to do that and programmatically return correct golfed answers, please add an example \$\endgroup\$
    – noodle man
    Sep 30 at 18:18
  • 1
    \$\begingroup\$ On top of the problem of validation, I feel like this has some problems depending on the languages you pick. Definitely don't include unary. \$\endgroup\$ Oct 3 at 19:20
1
\$\begingroup\$

Given A Binary String, Determine Which Of Certain Substrings Are Equal And Opposite

yea the title is going to need some work

Concept

Take an even length binary string

1 1 0 1 0 0 1 0

Between each bit, place an arrow

1 1 0 1 0 0 1 0
 ^ ^ ^ ^ ^ ^ ^

Next, find each substring centered on each arrow which includes either/both the start and the end of the string

1 1
 ^
1 1 0 1
   ^
1 1 0 1 0 0
     ^
1 1 0 1 0 0 1 0
       ^
    0 1 0 0 1 0
         ^
        0 0 1 0
           ^
            1 0
             ^

If each half of the binary string has all of the flipped bits of the other half (in any order), replace the arrow with a 1, else a 0

1 1
 0
1 1 0 1
   0
1 1 0 1 0 0
     1
1 1 0 1 0 0 1 0
       1
    0 1 0 0 1 0
         0
        0 0 1 0
           0
            1 0
             1

Then get rid of the sublists which will leave you with just the arrows-turned-bits

 0 0 1 1 0 0 1

You must output those bits.

Examples:

00 0
01 1
10 1
11 0
0000 000
0001 001
0011 010
1001 111
1011 100
1100 010
000011 00010
100101 11111
101101 10001
00110011 0101010
00111100 0101010
10101010 1111111
11000101 0111011
11010010 0011001
11100010 0011101

Meta

yea I don't have the vocabulary for this. I'm gonna hammer at it some more but if you read this and something jumps out at you where youre like "oh i know what thats called" Please let me know thank you

\$\endgroup\$
10
  • \$\begingroup\$ What does "opposite digits" mean? \$\endgroup\$
    – Someone
    Sep 25 at 0:22
  • \$\begingroup\$ @Someone im not sure how to phrase it, but if you have X 1s and Y 0s on one end, you need to have Y 1s and X 0s on the other side. \$\endgroup\$ Sep 25 at 1:05
  • \$\begingroup\$ So order doesn't matter? \$\endgroup\$
    – Someone
    Sep 25 at 12:55
  • \$\begingroup\$ @Someone exactly. Would tacking "in any order" onto it fix that, or would you suggest a full rephrasing? EDIT: actually tried something out here, any better or still off? \$\endgroup\$ Sep 25 at 19:08
  • \$\begingroup\$ It's good—I was just making sure. I think the examples explain it well enough. \$\endgroup\$
    – Someone
    Sep 25 at 19:23
  • 1
    \$\begingroup\$ (1) For your example 11010010, the answer should be 0011001, shouldn't it? (2) Can I rephrase the task to »For each position to break the string into two, starting from the left, place a 1 if the number of 0 digits on the shorter part is equal to the number of 1 digits among the neighboring substring of the same length on the other side, otherwise, put a 0.«? \$\endgroup\$
    – Philippos
    Oct 3 at 12:25
  • \$\begingroup\$ @Philippos (1) Yes, typo, corrected, thanks! (2) Yes! Can I include that wording / a version of it? that seems like the way to go as far as making this more explicit/formally stated... Thanks :-) \$\endgroup\$ Oct 3 at 15:10
  • \$\begingroup\$ (1) The same typo is in the final line of the demonstrated example; I'm sorry I can't correct it myself. (2) Of course you can, maybe with some more words to make it more comprehendable. \$\endgroup\$
    – Philippos
    Oct 3 at 16:51
  • \$\begingroup\$ @Philippos (1) lmao how did i miss that twice, thanks (2) Thank you, I'll keep working on it based on your suggestion :-) \$\endgroup\$ Oct 3 at 17:11
  • \$\begingroup\$ If you want to thank me, please comment on my idea. someone downvoted, but did not write why. \$\endgroup\$
    – Philippos
    Oct 3 at 17:56
1
\$\begingroup\$

Generate Conway's Atomic Elements

\$\endgroup\$
1
\$\begingroup\$

Implement the RegPack decompressor

\$\endgroup\$
1
\$\begingroup\$

Is it a stable structure?

In this challenge, a structure is a combination of row of ---- and columns of |, such that all rows are above at least one column and all columns are on top of either a row or the ground. Additionally, a structure must have all its component rows or columns connected vertically.

For example, the following are structures:

          ---      -----      -----
     |     |        |  |      | | |
|    ---   |----    -- -----  |---|
|     |    |   |    |  |   |  | | |

And the following are not:

|             |                     |
     --    ---|   ---- ---          |-----
|   |  |    | |   |      |     ---  || |

The last two are not structures because, although they satisfy all the other rules, they contain multiple vertically connected parts - specifically, the end of a - cannot connect with the side of a |.

A single row of -s can have multiple |s under it. That row is stable if the center of the row occurs within the span of the |s. For example, take this row:

---X---
 |  ||

The center of that row is the position marked X, and as this falls within the outer two |, the row is stable.

---XX---     ---XX---
   |||          |

You can also have rows with even length, in which case both central positions have to fall within the span of the columns. The first example here is stable, the second is not.

---X---
   |

Rows can even be balanced on a single | as long as their center is on that |.

A structure is stable if every row of ---- in it is stable by the above criteria.

Your challenge is to, given a valid ascii-art structure by the criterion above, determine whether it is stable or not.

Output may either be truthy/falsy using your language's convention (swapping is allowed) or outputting two distinct values for truthy/falsy.

This is , shortest wins!

Testcases

Truthy

|

-
|

---
| |

  ---
  | |
--- ---
 ||  |

-----
 | ||
 |---
 | |

|
---------
 | |    |


   -------
   |  |
  ------
  | |  |
-----  |
|  |   |

Falsy

--
|

--------
   |

------
| |
------
 |  |

  ---
    |
---------
    |


------------------
 | | |

-------------
|           |
------ ------
|           |
\$\endgroup\$
1
\$\begingroup\$

Make a super fair number

\$\endgroup\$
1
  • \$\begingroup\$ I'm not sure if the super fair condition is equivalent to every slice with an arithmetic progression of digit positions being evenly distributed, but I think this alternate condition might be easier for solvers to prove correctness for. \$\endgroup\$
    – xnor
    Aug 5, 2022 at 11:38
1
\$\begingroup\$

Compile Japt to JavaScript

this is a work in progress challenge! the spec is not finished

[Japt] is a programming language designed by [@ETHProductions] in 2017 designed as a code-golf version of JavaScript (from which its name is derived; JavaScript → Japt). Code written in Japt is compiled to JS code. This challenge is about code-golfing that compilation process.

For this challenge, we will be using a slightly simplified version of Japt that does not support compressed string literals, shortcuts, or ß for recursion. This version of Japt also lacks the semi-famous bug that unterminated array literals make the parser break.

Japt syntax

Japt programs consist of a series of chained function calls (like the JavaScript something.a(1).b(2).c(3)). In Japt, these are written as follows:

a1 b2 c3 

Each lowercase letter tells the parser to start reading arguments, and each space tells it to stop and call the function with those arguments. Here's what passing multiple arguments to functions looks like:

a1,2 b3,4,5 c6 

Japt programs don't just consist of lowercase letters, digits, and spaces. Japt has syntax for four kinds of literals:

  1. Numbers, like 1234 or 1.23 or 0.7
  2. Strings, like "abcd" or "player 1 has {U} points" (interpolation)
  3. Arrays, like [1,2,3] or [1,"a",["b","c",[2]],"d"]
  4. Functions, like X{X+1} or XYZ{XaY b5 +Z} (uppercase letters are parameter names, brackets surround function body)

An expression is made of one of the above literals, followed by any number (including zero) of chained function calls.

Note that, when the either the program ends or the parser hits a newline, any unfinished literal or function call is automatically closed:

mX{Xa"bcd

can still be parsed as calling m with a function that takes X and calls a on it with argument "bcd", even though many structures are not fully

Compilation to JavaScript

Japt expressions translate pretty much one-to-one with JavaScript expressions. Many expressions can be translated slightly differently and have the same results, so for this challenge, any output that is equivalent to the JavaScript expression as explained here is OK output. For example, for a1 b2 c3 you may choose to output U.a(1).b(2).c(3) or you might output U.a(1 ).b((2)).c(3 ) or similar.

If a number literal is the first part of a chained function call, it must be either surrounded in parentheses (1.5 becomes (1.5)) or have a trailing space (1.5 ). Your submission may choose either of these. You may also choose to have all numbers follow one of these conventions, not only

Test cases

Japt:
a1 b2 c3
JavaScript:
U.a(1).b(2).c(3)

Japt:
a1b2c3 d4  e5
JavaScript:
U.a(1 .b(2 .c(3).d(4)).e(5)

Japt:
q| mZ{ùT+=Zl} ú mZ{Z+S+V
JavaScript:
U.q("I").m((Z)=>Z.ù(T+=Z.l())).ù().m((Z)=>Z+S+V)

Japt:
1 +2 +3 +4
JavaScript:
(((1)+2)+3)+4
\$\endgroup\$
1
\$\begingroup\$

Perform Gray Addition

Objective

Given two non-negative integers encoded in unbounded-length Gray code, add them and output the result, where the result is also encoded in Gray code.

Gray code

There are many equivalent formulations of Gray code, but here's an intuitive one.

The Gray code encodes each non-negative integer as an infinite bit-string. Starting from encoding zero, as the enumeration goes, the least significant bit keeps cycling through "0110". Each place of bit keeps cycling through what the previously significant bit cycles through, but doubled entry-wise. To summarize:

0th LSB: Cycles through "0110"
1st LSB: Cycles through "00111100"
2nd LSB: Cycles through "0000111111110000"
3rd LSB: Cycles through "00000000111111111111111100000000"
(And so on)

That gives the encodings of few non-negative integers as:

Integer = Gray code
("..." stands for infinitely many leading zeroes)
0 = "...00000"
1 = "...00001"
2 = "...00011"
3 = "...00010"
4 = "...00110"
5 = "...00111"
6 = "...00101"
7 = "...00100"
8 = "...01100"
9 = "...01101"

Note that, for each pair of integers differing by one, their Gray codes differ by only one bit.

I/O format

Flexible. Standard loopholes apply.

Examples

Here, inputs and outputs are Gray codes with their leading zeroes stripped off.

"" + "" = ""
"1" + "1" = "11"
"1" + "10" = "110"
"10" + "1" = "110"
"10" + "11" = "111"
"111" + "111" = "1111"
\$\endgroup\$
1
\$\begingroup\$

Pushing Penguins on an Integer Iceberg

An iceberg is represented by a rectangular grid of cells. Each cell can hold one of three penguins. Penguins can be pushed in any free orthogonal direction, but they slide until they reach the edge of the grid or would bump into another penguin. Example:

.........
.1.....2.
....3....
.........

If you push each penguin in turn to the right, they will end up in the following positions:

.........
......1.2
........3
.........

Given an initial position and a target cell, your challenge is to push any of the penguins so that it comes to rest in that cell.

You can take the initial position as an iceberg size and list of penguin coordinates, or as an iceberg array of bytes, with one value for the empty cells and one or three distinct values for the penguins. In the latter case the target cell can have its own distinct value or it can be a coordinate. (Although the input can only be bytes the type of the array can be larger.)

The output list of pushes should identify the penguin to be pushed, either by its initial index or its current position, and either the direction (which can be encoded as any four convenient byte values) or target of the push, or if the penguins have three distinct values then it can be a list of updated iceberg arrays each with one penguin having been pushed to a new position from the previous. (The initial position does not have to be included in the output.)

You can assume that the target cell will be in the interior of the iceberg as the edge cells are trivial as they only require two penguins to solve. (And the corner cells are even more trivial as they only require one penguin.)

Your doesn't have to output an optimal solution but it must be deterministic. One approach is to devise a systematic solution that solves every cell on the iceberg but only output as far as the target cell.

This is , so the shortest program or function that breaks no standard loopholes wins!

\$\endgroup\$
1
\$\begingroup\$

Moved to the main site

\$\endgroup\$
2
  • \$\begingroup\$ I'd recommend not having a fixed message required for the case where no order is possible -- AFAIK, the way it's usually done in code golf challenges is to allow the golfer to pick any distinct symbol to output. (Also, of the two options given, there is absolutely no way that any golfer would choose to output the full sentence instead of the empty string.) \$\endgroup\$ Oct 16 at 22:06
  • \$\begingroup\$ @97.100.97.109 Of course not! This was just meant to be a funny side mark, maybe drawing some other jokes in the answers. But I can omit it if it confuses. \$\endgroup\$
    – Philippos
    Oct 17 at 9:53
1
\$\begingroup\$

Challenge - Find the nearest "well known" fraction

Find the nearest useful, well-known fraction for any decimal.

Here I'm defining well-known fractions as

  • 1/2s - everyone can get on board with halves
  • 1/3s - similarly easy to picture
  • 1/4s - slicing up a pizza for greedy people
  • 1/5s - at the edge of usefulness, but I think still useful
  • 1/6s - only 1/6 and 5/6 are not covered by the above, but it's a pizza slice so just sneaks in

BUT NOT

  • 1/7s - no-one uses sevenths
  • 1/8s and 1/9s - might as well just go to decimals now

Thus, the challenge is, given any number between 0 and 1, output a numerator and denominator where the latter is between 1 and 6 inclusive, with a forward slash in-between, representing the nearest fraction to the decimal, from the following:

0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1

Zero and One results can either be output as 0/1 or 0, 1/1 or 1

TIE BREAK - where a decimal is equidistant between two common fractions (e.g. 0.775 is equidistant from 4/5 and 3/4), then the LOWEST denominator wins, so an input of 0.775 outputs 3/4.

(Sandbox comment - I hope this isn't trivially easy!)

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Hello, and welcome to Code Golf! This seems like it's definitely not a trivially easy challenge. \$\endgroup\$ Oct 31 at 14:46
  • 3
    \$\begingroup\$ Nice first challenge! The requirement of a slash between the numerator and denominator seems a bit annoying. Why can't answers return a pair of numbers? Regarding the tie breaker - if the input is a floating-point number, then none of the midpoints are exactly representable, which mean the tie breaker isn't relevant, which significantly disadvantages taking the input as a fraction. I'd suggest either dropping the tie breaker, or allowing only exact fractions as input. Lastly, the phrasing is a bit awkward - just "return the closest fraction with denominator as most 6" would be enough. \$\endgroup\$ Oct 31 at 16:29
  • \$\begingroup\$ I was thinking of posing a similar question, except the output would be one of the Unicode vulgar fractions U+00BC-U+00BE or U+2150-215E (you would pick the nearest as before). \$\endgroup\$
    – Neil
    Nov 6 at 1:40
  • \$\begingroup\$ The other approach for tie breaking is for a given input the code should always output the same result but for the ties either output is acceptable. \$\endgroup\$
    – Neil
    Nov 6 at 1:42
1
\$\begingroup\$

Twist words to intersect

Given three strings of alphabetic characters \$A\$, \$B\$, and \$X\$, (all uppercase or all lowercase, your choice), output an arrangement of \$A\$ and \$B\$ on a grid such that they intersect only at the letters of \$X\$. Each word can start at any location in the grid; after that, every character in the word must be placed in the grid at a location orthogonal (directly above, below, to the left, or to the right) of the previous character. The word must not intersect itself. The grid can be arbitrarily large.

For example, if \$A\$ was ASHAMEFULACT, \$B\$ was CHARACTER, and \$X\$ was HAT, one possible arrangement is shown below.

enter image description here

In text format:

_ _ _ _ _ _ _
_ _ a m e f _
_ c H a r u _
_ a s c A l _
_ _ e T c _ _
_ _ r _ _ _ _
_ _ _ _ _ _ _

(The places where the words intersect are shown in capitals; the rest of the letters are shown in lowercase.)

You can output in any reasonable format -- the format above is not required. For example, you do not need to have the intersecting letters be a different case than the rest of the letters in the words. One possible output format would be a 2D array of characters, like

[ ["",  "A", "M", "E", "F"],
  ["C", "H", "A", "R", "U"],
  ["A", "S", "C", "A", "L"],
  ["",  "E", "T", "C", "" ],
  ["",  "R", "",  "",  "" ] ]

You can assume that such an arrangement is possible to create -- e.g. \$A\$ and \$B\$ will both have the letters of \$A\$ as a subsequence (in order).

Standard loopholes are forbidden. As this is , shortest program wins.

\$\endgroup\$
2
  • \$\begingroup\$ Is the grid assumed to be of infinite size? You might want to say that somewhere. Also, I think you should recommend a specific format that might help answerers get on track, and then they can come up with golfier formats. (A matrix of characters doesn't seem complicated, but this challenge looks a bit more complicated than it is, so it might be better to state some options outright.) \$\endgroup\$
    – noodle man
    Nov 2 at 21:34
  • \$\begingroup\$ @noodleman Does this address edit your concerns? Do you have a suggestion for a golf-y format to mention? \$\endgroup\$ Nov 2 at 23:43
1
84 85
86
87 88
152

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .