# What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, 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. 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, replace the post here with a link to the challenge and delete it.

See the Sandbox FAQ for more information on how to use the Sandbox.

## Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

Chad is a variant of chess. It is played on an uncheckered board measuring twelve by twelve squares. Squares are denoted using standard chess notation, so a12 is the top left corner and l1 is the bottom right corner. The opening position of Chad looks like this:

Above: Chad gameboard and opening position.

The 3x3 area that the kings start in is called the castle. The twelve shaded squares around each castle is called the wall. Here are how the pieces interact with each other and the wall:

• The King can move and capture like a King but also as a Knight. However, he is confined to his 3x3 castle.
• The Rook moves like a Rook in chess, unimpeded by walls or castles. If the Rook ends on a square inside the enemy castle, it is automatically promoted into a Queen.
• A Queens move like a Queen in chess. She is also unimpeded by walls or castles.
• The mutual right of capture between two pieces (except for the King) exists if, and only if, one piece is on the enemy's wall, and the other piece is in their own castle. Otherwise, pieces simply block each other.
• The King may capture pieces inside his castle, provided he can attack the piece (remember that the King can move both as a King and as a Knight).
• Check occurs if the King is in the path of a Rook or Queen, regardless of whether the Rook or Queen is on the wall or not. Walls do not block checks.
• As in regular chess, white moves first, a capturing piece replaces the piece captured, and checkmate wins the game.
• A draw occurs if:
• x moves have passed without any piece being captured.
• There is three or less pieces on the board.
• It is a stalemate.

This is a king-of-the-hill Chad competition. To enter write a program that decides what moves to make, using the IO format below. This program will be pitted against other entrants to find out which program is the strongest.

## Inputs and Outputs

Your program will be ran from the command line for each move, and input will be given as a command line argument. Here is the input format:

[colour] [board] [history] [moves]

• [color] is 0 if you are playing White, and 1 if you are playing Black.

• [board] is an ASCII representation of the board with newlines stripped. K is a King, R is a Rook. Lowercase letters indicate black, uppercase means white. A dot . is a blank space. The starting position would look like this:

 ...............................rrr.........rkr.........rrr................RRR.........RKR.........RRR...............................

• [history] is a comma separated list of the moves you and your oppoment have done. It is in a modified long algebraic notation, consisting of the starting and ending squares separated by a hyphen, without a letter identifer for the piece. If it is a capture, the hyphen is replaced with an x. There is no !? or other such ornaments. This is blank if you are White and making the first move - be prepared for this!

• [moves] is a comma separated list of the valid moves you can make in your current situation. It is also in the modified long algebraic notation.

Note that you don't have to use all of the information given in the input if you do not want to. The information is supplied to simplify the process of making the program.

You program should output a single move in the modified long algebraic notation, indicating what move you want to make on that turn. The move must be valid. The program must output its move within y seconds, otherwise it will resign. If the program outputs anything other than a valid move, it will be counted as a resignation.

## Entering

To enter, submit an answer with the following information:

• The name of the bot (to be used for score tables, etc.)
• The language the bot is written in
• The command line command needed to run the bot

If I cannot include your bot for any reason, I will add a comment explaining why I cannot. I will endeavour to install any programs required to run your bot, as long as it is legally free to access (sorry Mathematica people).

The final round will occur on xxxx/xx/xx. It is a round robin. Each bot plays against each other bot two times - once as black, and once as white. If a bot wins both rounds, it gains 1 point. If it wins one round, it gains 0.5 points. If it doesn't win either, it gains 0 points. The bot with the most points gets the green checkmark.

I will also hold regular practice rounds, of which you may find the results of here. The last practice round was held on xxxx/xx/xx. These practice rounds will continue even after the final round has finished.

## Questions

• Is the explanation of Chad's rules clear?
• What would be good values for x and y?
• Would the extra information in the input be helpful?
• Any other advice would be appreciated.

I haven't written the control program yet. I intend on getting the specification ironed out first.

• I'm sad to see this sort of thing here rather than elsewhere where it might find more long term interest. – Sparr Sep 11 '14 at 3:52
• I strongly suggest that before posting to live you set up a github repo with the control framework, a sample bot, and a build script which builds all of the bots. See github.com/pjt33/ppcg36515 . I also have a suggestion which I've been mulling over with respect to koth in general: round robin emphasises the metagame over actual good play. How about having round robin for seeding purposes followed by a best-of-5 knock-out bracket? – Peter Taylor Sep 11 '14 at 9:16
• ​​​​​​​​​​​​​​​@PeterTaylor When I finish the control framework I'll put it in a github repo. A tournament bracket sounds interesting - I'll try it on this KOTH and we'll see how it goes. – absinthe Sep 11 '14 at 9:28
• Hi, this seems like a fun KOTH challengw. Is it still in the works? – AndoDaan Sep 21 '14 at 5:51
• @AndoDaan Yes it is. I'm still writing the control framework. The problem was that before writing the challenge I didn't actually know how to program, so ​​​​​​​​​​​​​​​I have to learn how to program before I can make the control framework. – absinthe Sep 21 '14 at 6:04
• Cool. Big task to start in, but I can imagine you'll get to know all the nooks and crannies of your 1st language. Have fun, and don't get disheartened! – AndoDaan Sep 21 '14 at 6:18

# King of the Tournaments

This game is based off of Graph Theory Tournaments

The competition will be a series of tournaments, where the Kings of a tournament will play in the next until the winner(s) is found

Every player will play every other player exactly once in a tournament. Each player will recieve 5*N points each tournament (where N is the number of opponents in that tournament). Furthermore, each player will have an advantage over N/2 players, and a disadvantage to N/2 players. This advantage is decided at the beginning of the game.

Each battle will consist of a player commiting X points. Whoever commits more points will win that battle. If both players commit the same amount of points, the player with the advantage over the other will win.

After a tournament, the Kings will be the players that defeat all other players. P1 defeats P2 if P1 beat P2 in battle, or if P1 beat a player that beat P2. If all players are kings, then the players with the least amounts of wins this tournament are eliminated. If all have the same amount of wins, then the players with the least amount of total wins are eliminated. In the case of a tie, the remaining players are declared the winners

# IO

Your bot must stay alive throughout the entire game. You will pass in a number every round through STDOUT. You may pass in a few codes through STDOUT to recieve information via STDIN:

W will return IDs of the players you have won to this tournament

L will return the IDs of the players you have lost to this tournament

OW will return the IDs of the players your opponent has won this tournament

OL will return the IDs of the players your opponent has lost to this tournament

A will return 1 if you have an advantage over the player, else 0

H will return the history of your battles against the player. The list will be comma-seperated, where each battle is represented by Num1/Num2 where Num1 is the points you committed, and Num2 is the points your opponent committed.

• 1. It be probably be clearer to say that "In layman's terms, it represents the outcome of a round-robin tournament". 2. What's the connection between the two introductory paragraphs and the third one? I can't follow your train of thought here at all. 3. Each player plays each other player twice per round, on turns D and N-D where D is the difference between their positions? – Peter Taylor Sep 15 '14 at 9:56

# Thinking about the Box outside of the Box

## (looking for input from community)

Everyone has heard about the 9 points 4 lines challenge, where the goal is to connect all the points on a 3x3 grid with only 4 straight line segments, and without lifting your pen.

It has been proven that it is simple to calculate the minimum number of lines needed for any square:

Write a program that takes 2 positive integers as inputs, the dimensions of the grid of points (x points wide, y points tall) and calculates the minimum number of straight consecutive line segments needed to join all of the points on the grid.

The line segments may go off of the grid of points. (obviously :P) If either input is 0, output 0. If either input is 1, output 1. Otherwise you have to calculate the result. The inputs can be any positive integer, so hardcoding the solution is impossible.

Your program is correct until proven wrong. Only one counterexample on one set of dimensions is enough to prove a program wrong. (lets say a program outputs 5 for the set x=3, y=3, and the real solution is 4, then the entire program is wrong and it is not counted)

This is a code-golf challenge, shortest code to fulfill the requirements wins.

• It sounds good, but I don't know if this problem has a known closed-form solution which might make it quite trivial. – Martin Ender Sep 19 '14 at 9:44
• The "correct until proven wrong" thing doesn't sit well with me. I think that you should first post a question on puzzling.stackexchange.com asking whether there exists a closed form solution. I hypothesise a very simple one, but I don't have time now to prove it, but if I'm correct then this would be a very boring question once the first person posts it. – Peter Taylor Sep 19 '14 at 12:06
• hmm, maybe requiring them to output the lines could be more challenging? – rodolphito Sep 19 '14 at 22:18

Pointlessly Restrictive Integers

In this question, all code blocks are independent of each other.

I'm designing a new programming language called Pointlessly Restrictive. The integers in Pointlessly Restrictive work in a peculiar fashion:

1. An integer must be explicitly declared with its length before being used (there is one exception to this rule, described below). This is done using the syntax A = [x], where A is the name of the integer (always a single, uppercase character) and x is the length of the integer. For instance:

A = [2]
B = [5]


This declares an integer A of length 2, and an integer B of length 5. Note that at this point, the actual digits of the integer are not defined - so any integer of the specified length is a possible value. For example:

A = 23


is an invalid statement, because I haven't declared the variable with its length before using it.

2. The length of an integer is immutable. For instance:

A = [5]
A = [3]


is invalid, because I cannot change the length of an integer after making it.

3. Values are assigned to an integer using the syntax B = x. For instance:

B = [5]
B = 21436


is a valid assignment. Note that:

B = [5]
B = 314


would be invalid, because the values given is inconsistent with the specified length of 5.

4. The + operator only concatenates integers, as if they were strings. For instance:

A = [3]
A = 123
B = [2]
B = 45
C = A + B


C, in this case, is equal to 12345. Note that I didn't need to declare the length of C before using it – the length is instead decided based on the component integers. In addition, I can use the [x] notation in this definition method:

A = [3]
A = 123
C = A + [2]


Any integer that has length 5 and begins with 123 is a possible value for C. In addition, if I use an integer twice in this definition method, it must hold the same value each time:

A = [2]
C = A + A + A
D = C + [2]


Any integer that consists of a subsequence of length 2 repeated three times (for instance, 161616) is a possible value for C. That possible value, with any two numbers after it, would be a possible value for D (e.g. 16161623). For instance, the sequence 142632 could not be C.

5. A value is printed by baldly printing the name of the integer on one line. If there are unknown digits, it substitutes lower case letters - the letters that are chosen are up to the interpreter. If there are more than 26 lower case letters required (e.g. A = [27]), it is an error.

A = [2]
A = 14
A


outputs 14. Another example:

A = [3]
A = 163
B = A + [1]
B


outputs 163a.

A = [3]
B = A + A + [1]
B


outputs abcabcde

Note that the abc repeats because the A repeats.

6. Integers can be reassigned, specialised, or generalised at any time. For instance:

A = [2]
A = 13
B = A + [1]


B is equal to 13a. This is also possible:

A = [2]
A = 13
B = A + [1]
B = 134


On the fourth line, I have specialised B to a specific value. This is also possible:

A = [2]
A = 13
B = A + 1
B = [3]


On the fourth line, I have generalised B to make it less specific. However, note that I cannot change the length of the integer - so B = [4] there would have been invalid.

Pointlessly Restrictive requires each statement to be on its own line. There is no semicolons at the end of lines.

Your task is to write an interpreter for Pointlessly Restrictive. It should be runnable from the command line - as its input, it will be given a filename, which can be assumed to be in the working directory of the operating system. The file contains some Pointlessly Restrictive statements. Your interpreter should check for any errors in the file (for instance, an assignment with the incorrect length), and output Error! if there is an error.

If there are no errors in the file, output whatever values are printed in the file.

Sample Inputs and Outputs

Input:

A = [2]
A = 13
A


Output:

13


Input:

A = [2]
A = 13
B = A + A
B


Output:

1313


Input:

C = [4] + [2] + [3]
C


Output:

abcdefghi


Input:

J = [2]
J = 13
L = [4]
L = 143 + [1]
K = L + J
K


Output:

143a13


Input:

J = [2]
K = J + J + J
K = 231323
K


Output:

Error!


Input:

J = [2]
K = J + J + J
L = K + [3]
K
L


Output:

abababcde


Notes

• Spaces do not hold any syntactic value in Pointlessly Restrictive - A = [2] is equivalent to A=[2], A= [2], or even A=[ 2 ].
• This means that the integer 123 54 is the same thing as 12354 for your interpreter.
• Judging from your output in section 6, "all possible values" means 0-9. You might want to state that limit more clearly. Now it just says "Arrays can only store integers," which is a lot broader. – Geobits Sep 16 '14 at 12:54
• @Geobits Thinking about it, it probably makes more sense if I make it storage of integers instead of arrays. Will change when I have time.​​​​​​​​​​​​​​​ – absinthe Sep 16 '14 at 20:10
• Two more things (I think) you didn't specify: can values be reassigned? And can I specialise an integer later one? E.g. at the end of your very last example, could I do K = 143913? – Martin Ender Sep 17 '14 at 11:05
• This simply looks like string operations, where [#] defaults to lowercase letters. The hardest part of this challenge is validating if A = 123 is valid. – Nathan Merrill Sep 17 '14 at 17:40
• @NathanMerrill I will agree it's not a difficult challenge. I feel that the number validation part is enough to create some interesting answers however. – absinthe Sep 17 '14 at 22:31
• @Lilac Did you address my last comment? – Martin Ender Sep 18 '14 at 9:45
• @MartinBüttner Yes for both. – absinthe Sep 19 '14 at 23:15

# Markdown to HTML converter

## Challenge

Write a program that takes a file name ending in .md, .mkd or .markdown as a command-line argument (or the closest equivalent in your language of choice) and converts it to a valid HTML 5 document.

## Rules

• If an error is detected, you must print an error message and terminate the program with a non-zero exit status.
• The output file name must be the input file name with the extension changed to .html.
• You don't have to include a doctype or <html>, <head>, <body> tags.
• You must support everything listed in the CommonMark specification, except for embedded HTML and HTML entities.
• You may not use an existing library or similar tool for processing Markdown.

• The spec is notoriously incomplete. This needs a very big set of test cases. I personally favour Michel Fortin's test cases. – Peter Taylor Jul 3 '14 at 17:09
• The test cases themselves won't fit in the post; and there are a small number which won't be appropriate (either because they use the parts of the spec which you've said we don't need to support, or because they're too implementation-dependent). Perhaps the best thing would be for you to fork the git repo, trim it down to the relevant test cases, and link to your fork. – Peter Taylor Jul 4 '14 at 11:14
• I just discovered CommonMark, so I'm using that now. – nyuszika7h Oct 4 '14 at 13:53
• That is excellent news. I've been checking for signs of progress on that project every couple of months since Atwood announced the idea on his blog. – Peter Taylor Oct 5 '14 at 21:32

## Game Rules

Play your card right is a game played with a pack of 52 cards (no jokers). At the start the deck is shuffled and the dealer will lay a single card on the table. The player then has to decide if the next card is higher or lower than the card on the table (note that ace is low here).

The dealer then lays another card on the table. If the card is the same as your guess (higher or lower), then you continue the game. If the card is equal to the last or not the same as your guess, all of the cards on the table are put into a separate pile and the game starts again (the cards in the separate pile are completely discounted).

You lose the game when the deck is emptied. You win the game if you get six cards on the table.

## Challenge

Given the last card to be laid on the table you must make a guess as to whether the next card will be higher or lower.

## Specifics

The necessary information will be supplied via argv:

• If the argument is newGame then wipe all data stored about the previous game
• If the argument is clearTable then clear the table and move all cards to the separate pile
• If the argument is not detailed above then it is a card name: 1 to 10 or J,Q,K,A

You may store information. I will be testing this on Ubuntu 12.04.

## Winning

The shortest code wins. Please note that these have to be optimal solutions (winning most of the games played by the following controller)

Controller coming tomorrow (8/10)

• Should this be code golf? The way it's scored now, everyone will tie because the optimal solution is pretty easy. If the flipped card is higher than half of the remaining cards, guess low. Otherwise, guess high. – Rainbolt Oct 7 '14 at 17:11
• What is the difference between newGame, loseGame, and winGame? Are we supposed to keep track of our losses and wins? – Rainbolt Oct 7 '14 at 18:26
• @Rainbolt Good point, there isn't a difference. – Beta Decay Oct 7 '14 at 18:31
• Now that it's code golf you do need to mention that solutions must implement the optimal strategy. You also might want to write a little controller to probabilistically verify correctness of the submissions. – Martin Ender Oct 7 '14 at 18:50
• A good way to specify "optimal strategy" (short of presenting the algorithm) would be to write a reference implementation of the strategy Rainbolt outlined, running it a few thousand times to measure how often it wins and stating that submissions should achieve that same ratio. – Martin Ender Oct 7 '14 at 19:03
• You say that "You may store information, but you must not use a file". But in UNIX, and therefore also in Linux, everything is a file. – Peter Taylor Oct 7 '14 at 20:11

I posted this earlier but they suggested I put it in the sandbox which made a lot of sense.

Your job is to take an image of sheet music and make it usefull for someone that doesn't read notes.

### Output

3/4 (Which is the beat)
C F B,A,D E F C (Notes, Space seperated and comma seperated if notes are tied)
Images of the notes to play.


Layout images: The images must show a piano with the layout of an 61 key piano.

Each image will display a set of 5 consecutive notes. Tied notes will be treated as 1 note.
If the first note of a set is C there will be a '1' on the C key,
Second note F there will be a '2' on the F key and so on.
Like i said tied notes will be treated as 1 note but the index will count up.
So B,A,D will result in:
'1' on B; '2' on A; '3' on D.

If the same note is used twice in 1 set the note will show both indexes. How you display that is up to you, you can either seperate them by comma or newline.

Some information on reading notes can be found here:

• The code (Golfed and ungolfed).
• Image used (or link to image).
• The output (both text and images).

Not sure about the tag. I tagged it for now but if someone has a better idea let me know.
(should I also use the tag?)

Right now this is so the one with the lowest bytes wins.

Happy coding :)

• To reiterate what was said in the comments, (i) this is a seriously hard challenge. Programs will be very complex and not so fun to golf, so it's probably better to make a winning criterion based purely on accuracy. This will probably involve providing a definitive set of test images; (ii) you need to figure out how to avoid 'workarounds' where people just hash the test images you provide. (For example, keep some test images hidden until it's time to judge the winner - though that does make it time limited.) – Nathaniel Oct 21 '14 at 14:02
• (iii) this is really two challenges, the easy graphical output challenge and the very very hard OCR-for-sheet-music challenge. It would probably be better to stick to just one of them, and have either text-based input or text-based output. I think that was about it. – Nathaniel Oct 21 '14 at 14:03
• Nice idea, but honestly I think the reverse challenge (input notes in scientific pitch notation and output a musical score) would work better. EDIT: Oops, what I'm suggesting has already been done: codegolf.stackexchange.com/q/24783/15599 – Level River St Oct 29 '14 at 23:45

# 5 Miscellaneous Flag Challenges code-golfgraphical-outputgeometry

We've had questions on the South Korean flag and the flag of Nepal. I thought that some other flag questions could be interesting.

I've grouped these into one post to avoid cluttering the sandbox with potentially bad posts. Once we've decided which of these are worth doing challenges for, I'll separate them out into separate posts, and make exact specifications of what it should look like.

Flag pictures taken from CIA World Factbook, which is in the public domain.

How much hardcoding should be allowed, if any? Is it better to decide on a per-flag basis?

Your task is to output the flag, to a file, STDOUT or the screen, in any common format (SVG, PostScript, RAW, PNG).

## Malawi

Pros: Relatively simple
Cons: The "beams of sunlight" may need to be simplified slightly as they are some weird shape that I don't even know a name for

# Saint Pierre and Miquelon

Pros: Quite a lot of repetition. Complex but not impossible. Probably fun.
Cons: That ship and the lions are going to be quite difficult - probably need to be simplified a bit

# Australia

Pros: Simple geometric shapes. There's nothing hugely overcomplicated here. Some repetition. Shouldn't be too hard.
Cons: The stars have already appeared in the Nepal question - there is some overlap.

## Mongolia

Pros: Simple geometric shapes (mostly), but quite a lot of them.
Cons: The yin-yang bit is similar to the South Korean flag, which we've done already

## Togo

Pros: Simple
Cons: Maybe too simple?

• The problem with Saint Pierre and Miquelon will be to specify the shapes exactly enough to make this a good code golf. I also think that Togo is too trivial, as is Malawi. The others could be interesting. Another one I had in mind was Brazil. – Martin Ender Oct 21 '14 at 12:46
• @MartinBüttner Brazil is interesting, I almost forgot that one - can I add that to the list or do you want to post that one yourself? You could simplify Saint Pierre and Miquelon by turning all the curves into circle arcs and getting rid of bits such as the white curves in the sea. The crow's nest could just be a rectangle. I'm not sure my GIMP abilities go that far though... – user16402 Oct 21 '14 at 12:59
• I don't intend to post another flag any time soon. It's good fun, but it will get boring if we have one of these every week. There are only a limited number of interesting flags, so I don't see a point in exhausting them for challenges quickly. – Martin Ender Oct 21 '14 at 13:02
• There are many flags based on the UK flag besides Australia, listed here: en.wikipedia.org/wiki/Union_Jack. Wikpedia has the spec of the UK (it was used as a tutorial in the Sinclair ZX Spectrum manual back in the 80's.) Maybe do the Union jack first and the other flags of the family as a follow-up. The spec of the Australian flag inevitably refers back to the Union Jack. en.wikipedia.org/wiki/Flag_of_Australia but I think Australia is about the right level of complexity. Another (rather simple) family of flags is the Scandinavian: en.wikipedia.org/wiki/Nordic_Cross_flag. – Level River St Oct 21 '14 at 23:26
• The Scandinavian ones might make sense in a single challenge with a parameter. – Martin Ender Oct 22 '14 at 11:37
• @MartinBüttner that was my thought about the Scandinavian ones too, but even so, it's very simple. How to make it more complicated: a guessing game? – Level River St Oct 22 '14 at 22:07
• The more I think about it, the more I like the flag of Hawaii as a challenge from the Union Jack family. It's slightly easier than the Australian flag, and has the appeal of being not particularly well known. en.wikipedia.org/wiki/Flag_of_Hawaii – Level River St Oct 22 '14 at 22:10
• I've upvoted now, because I think enough time has passed since Martin's Korean flag challenge. I do believe it's important to use the authentic specification for flag drawing challenges. With that in mind, are you going to go ahead with Australia (or Hawaii?) The reason I ask is because I've thought of another flag challenge (unrelated to national flags.) BTW, I think St Pierre & Miquelon is too hard to draw, let alone specify, but it might work if you designed a nice ASCII art representation to generate. – Level River St Nov 30 '14 at 1:07
• A codegolf in itself would be to take a flag and make it into a waving flag animation. A standard challenge in computer graphics since the old days, but we don't see too many CG golfing challenges here. – Abulafia Feb 26 '15 at 14:13

# Rearrange pixels from one image to form another, with different pixel counts

This would be very similar to American Gothic in the palette of Mona Lisa: Rearrange the pixels except that the images would not necessarily have the same area. If the palette image is larger, then the pixels can be chosen amongst and some left unused. If the palette image is smaller, then the result will be resized/resampled to the same aspect ratio as the other image.

The inspiration for this challenge is a real world application, using limited numbers of colored tiles to make a mosaic copy of a full color image. There would be an unlimited number of white/background tiles, but I can't think of a way to represent that in the challenge description, so I'd probably just fake the number of white tiles for a given target resolution.

• I think you mean area rather than aspect ratio, but I would vote to close this as a duplicate. Some of the existing answers would need no modification other than to do the rescale to get a large enough palette. – Peter Taylor Oct 28 '14 at 7:47
• @PeterTaylor I definitely meant aspect ratio. – Sparr Oct 28 '14 at 15:07
• I like problems like this and hope some variation can go live. However, as currently conceived, the problem is that some way to define how to interpolate a palette of m pixels into another of n pixels is needed, and then given the input is fixed the output is the exact same problem as the "rearrange the pixels" problem? – Will Oct 30 '14 at 10:30
• @Will it might be more complex than that. since it involves resizing, it could also involve anti-moire algorithms and different priorities in selecting or tweaking dithering algorithms. – Sparr Oct 30 '14 at 15:13

# Draw the Tree of Life

A contest to render the tree of life data (which is in the simple Newick format) sideways in ASCII, using the same formatting as this example:

   __/a
__/  \b
\   _/c
\_/ \d
\e


Note that the distance in the source data is ignored; the tree should be drawn as compact as possible.

The source data can be fed into the program via stdin or by opening a file or as a parameter to a function. The output should be printing to stdout.

The output should not be hard-coded; the tree data must be read in and parsed by the program.

Actually printing a tree on its side is itself a bit of a coding challenge; see this SO question for inspiration.

• Is this a contest to make a program which can render general trees from Newick format to the sideways ASCII format, or does it only have to work on the one data set? If it's the general form, does that data set test all the corner cases? – Peter Taylor Oct 30 '14 at 11:23
• @PeterTaylor its to render this particular data set. – Will Oct 30 '14 at 11:27

# Multi-File Code Golf

This is a new challenge Idea. Multi-File Code Golf. The idea is to write your golfed code in more than one file, and your score is the size of the largest file.

You need to fit the specs with a program that spans multiple files. Any languages that use multiple files are valid. For example you could use C++ with a header file, JS/HTML or Ruby with require. files may be named anything you want, and be in any directory.

Score equal to the size of your largest file. (in bytes)

# Chalinge

(Originally I had tic-tac-toe, but I decided that was a bad idea.) I need a good idea for a challenge that will work well in this format. Any ideas? It needs to be complex enough for multiple files to be helpful.

• I'm not sure how much the multiple files thing adds to the golfitude. Wouldn't most of your files just be a single statement plus import/include another file? It seems like it could easily boil down to "who has the shortest import statement". – Geobits Oct 25 '14 at 2:27
• @Geobits I see your point. would it be better to give a max file count (maybe 5, 10?) I make it a challenge to spread code most evenly? – MegaTom Oct 25 '14 at 2:38
• Probably better, but I'd wait for input from others who may be more knowledgeable about tricky imports ;) – Geobits Oct 25 '14 at 2:43
• Rather than using imports, I think exec(open("a").read()) or similar might be easier to do – Sp3000 Oct 25 '14 at 2:53
• Tic-tac-toe has been done. – Peter Taylor Oct 25 '14 at 7:13
• @Sp3000 In some languages, yes... – Ypnypn Oct 29 '14 at 0:23
• I agree with Peter. The scoring is a novel concept with potential (but not without problems.) But we don't need another tic-tac-toe question. – Level River St Oct 29 '14 at 13:07

# Help me sweep the floors

I have to sweep the floor of an MxN foot floor every night, where M and N can be any value between 1 and 1000. I need to know the most efficient method of sweeping this floor so I can get it done in the least amount of time.

## Rules:

1. Each stroke of the broom clears a 1 square foot area.
2. Each stroke of the broom can be directed in one of 4 directions - North, South, East, or West. You can represent these as N, S, E, and W, respectively.
3. When I make a stroke, if there is more than 1 unit of dirt on a square, 75% of the dirt will go onto the square directly swept towards, and the remaining 25% will be equally divided among the side squares. If there is less than 1 unit of dirt, 90% of the dirt will go onto to square swept towards, and the remaining 10% is divided among the side squares. The back square receives no dirt. If I sweep into the wall, 75% of the dirt remains on the swept square. If I sweep adjacent to the wall, there is only one side square.
4. Your program must keep track of the strokes I need to sweep each floor - this is your score.
5. I must stand in a square adjacent to the square I am sweeping. I can sweep that square in any direction, but I 95% of the time I will sweep to my right or left; otherwise, I brush the dirt into the air and choke or sweep it all over my feet.
6. Each square initially contains 1 unit of dirt. The floor is considered clean when no square has more than .025 units of dirt remaining on it.
7. When I take a step, I can either step onto an adjacent square or over an adjacent square onto the next square.
8. The floor is considered swept when the remaining dirt is contained in one square on the floor so I can pick it up.
9. I start at any position [0, {0-N}]. Your program must input a value in the range of 0-N on which I start.

Your program must return the minimum number of steps and strokes I take to sweep this floor. It may not backtrack and do some steps over, but it can use look-ahead - it must simulate sweeping the floor in actual life. It must take as input M and N, as well as a value in the range of 0-N specifying where the door is, and output to the screen how many strokes I must take to sweep the floor. Your score is the number of strokes I must take. The program that returns the lowest number of strokes for any input is the winner. Ties will be won by the smallest program character-wise. Your program will be disqualified if you do not explain the algorithm used in the answer.

• How is it possible to remove dirt from the room? Also missing: a running time limit; initial position of the sweeper; which values of M and N programs will be judged on. – feersum Oct 18 '14 at 18:54
• @feersum M and N can be any value between 1 and 1000. The dirt must be swept into a pile on 1 square so I can put it in the dust pan, and does there need to be a runtime limit? – user10766 Oct 18 '14 at 20:59
• If you don't have a runtime limit you're going to get mostly exponential-time solutions searching for the optimal solution, which you can't possibly run to completion. – feersum Oct 18 '14 at 23:26
• How will I define a limit? I can't run every program on my computer. – user10766 Oct 19 '14 at 0:40
• Why can't you run every program? I suggest the running time should be shorter than the age of the universe on some computer that currently exists. – feersum Oct 19 '14 at 4:30
• Why? I don't have a compiler for every language on my computer, and I certainly can't buy Mathematica. I agree that the running time should be reasonable, but I don't understand big O notation yet... – user10766 Oct 19 '14 at 17:57
• @hosch250 Don't worry about the big O complexity or running all the answers. Requiring that programs run within some time limit on some reference computer is perfectly acceptable. Though if the answers have to be optimal doing things in a time limit may be impossible. – Calvin's Hobbies Nov 4 '14 at 3:44
• @Calvin'sHobbies Thanks. So I should just specify that if it runs within that time limit, people can calculate or guess if it is likely to, and that will work? – user10766 Nov 4 '14 at 3:54

In this game, each bot will own a factory that accepts N products, and can produce M of a different product, denoted by #,Input->#,Output. There are 3 products A,B, and C and three types of factories, A->B, B->C, and C->A. Each factory of the same type will input the same number of products, and outputs the same number of products. Each both will be assigned a factory type, which can be queried (as described below) Producing A->B->C->A will increase the total amount of A.

Example: Bot 1's factory is 5A->2B, and starts with 500A. Bot 2's factory is 3B->7C and starts with 300B. Bot 3's factory is 5C->6A and starts with 500C.

You start with $1000, and your goal is to increase that money. Each turn you will produce, buy, and then sell in that order. To produce you will pass in the number of inputs. If you pass in more inputs than you currently have in inventory, then you will only produce what you have in inventory. If the amount input isn't divisible, then a remainder of your input will remain which couldn't be produced. To sell, you will pass the type you want to sell, the price, and the max amount you will sell. To buy, you will pass the type you want to buy, the max you will pay for it, and the max amount you will buy. The buyer with the highest max price will then be paired up with the seller with the highest price that is under the buyer's price. The buyer will then buy as many products as possible at the seller's price. If the seller reaches his maximum of products to sell, then the buyer will continue to buy from the next seller. If the buyer reaches his maximum of products to buy, then the seller will continue to sell his product to the buyer with the next highest maximum price. All products and dollar amounts are integers (there are no cents or partial products). There will be 3 copies of each bot, each assigned to a different factory. These bots cannot communicate with each other or with any other bot. The player with the most money across all of their bots after 500 rounds wins. Any language can be used, and input/output will come through STDIO. If you wanted to produce 34 of your product, buy 10 of product A at the price$5 and sell 20 of product B at the price of $6, then you would pass in P,34 B,A,10,5 S,B,20,6. At any time you can pass in: I to query your inventory, which will return something like 5A 10B 8C M to query the amount of money you have T to query your history of trades. It will be a space delimited list of trades. Each trade will look like like B,1275,A,49,90 (You bought from player #1275 49 of product A at the price of$90) or S,385,B,29,30 (You sold to player #385 29 of product B at the price of $30). R to query the number of rounds left F to query your factory type. It will return something like 5A->2B • How do you initialize the factories? A random initialization may give some bots much better factories than others. – Zgarb Nov 27 '14 at 20:48 • They are initialized randomly, but because there is no dollar amount attached to a factory, theres no way to say which factory has the advantage. – Nathan Merrill Nov 28 '14 at 16:05 • Well, intuitively I'd say that 2A->4B has an advantage over 4A->2B, and it's difficult to say how big the advantage is, since it depends on all the other bots' factories. I think it might be better to give every team the same set of factories, or the game will be very difficult to balance, since a bot is stuck with its factory for the entire run. – Zgarb Nov 28 '14 at 22:03 • The example you proposed wouldn't ever happen, at least in the same game. All bots with an A factory will have the same production ratios. – Nathan Merrill Nov 30 '14 at 0:17 • Ok, I had misunderstood you, this makes much more sense now. Still, if a player optimizes their bots for some specific factory configuration, their success depends heavily on the random initialization. Perhaps it would be worth running the simulation on some finite number of sufficiently different (predefined?) factory configurations, and taking the average score from those to determine the winner. – Zgarb Nov 30 '14 at 17:00 # Smuggle these Pincodes After many years, our covert agent has managed to amass a list of all PIN codes in an enemy nation. But there is a complication. The government of the country did become aware of our actions. Now our agent needs to smuggle the PINs past the customs without being caught! Our spy needs help. Hiding a list of 10 000 codes will be too difficult. Luckily, our government can enlist the help of its loyal programmers (you!). ## The Challenge Write a program that will output a list of all PIN codes from 0000 up to 9999 (inclusive). The program needs to be as short as possible to get past customs unnoticed. ### Rules • The PINs must each be on a separate line. • The program may not output anything other than the required output. However, it may output one (and no more than one) line end after the last PIN; e.g. 9999\n. And, in case you were wondering: • Your program must not: • Depend on any external resources. • Depend on having a specific file name. • Take exceptionally long to run. If your program runs over a minute on an average home user’s computer, it’s invalid. • Be written in a programming language for which there did not exist a publicly available compiler / interpreter before this challenge was posted. ### Scoring The shortest code (in bytes, in any language) wins. Any non-standard command-line arguments (arguments that aren’t normally required to run a script) count towards the total character count. Your program’s output may deviate from the given list order, in which case your program’s byte count will incur a +10% penalty (rounded up). • "You may assume your program won't receive invalid input." Why would it receive any input at all? What exactly is "valid" input here? – FireFly Nov 18 '14 at 22:52 • @FireFly I copied that line from a previous question without realizing that the program does not receive any input. I have removed it. – user2428118 Nov 18 '14 at 23:01 • Isn't this a bit trivial? It's just printing numbers from 0 to 9999 which are padded two 4 characters. Or printing the numbers from 10000 to 19999, ditching the leading 1, if you like. (Nothing against simple challenges, but I'm not sure how much room for optimisation this leaves.) – Martin Ender Nov 18 '14 at 23:03 • @MartinBüttner I realize it's a very simple challenge. I could not find any duplicates however, so I decided to put it in the sandbox anyway. But yes, there isn't much left to optimize, other than the things you mention and choosing the right programming language for the job. If there is consensus that it's too easy I can try to make it more challenging (or delete it). – user2428118 Nov 18 '14 at 23:15 • I think it's too easy. A golfer could write an optimal solution in 5 minutes. – xnor Nov 19 '14 at 8:17 • Easy questions give less experienced programmers another opportunity to participate. I'd still make it more challenging before you post it, but I don't think being easy is bad. – hmatt1 Nov 19 '14 at 16:46 # Writing the Hydra Function # Preamble Sometime in the early 21st century, computer scientists would discover the Hydra function (also known as the Lächerlich function), f, whose signature is given by R = f( A, B, L, x, y, z )  where A, B, L, and R are finite integers, and x, y, and z are integers in the range [-231 231). The function would quickly rise to preeminence due to the fact that it can perform 40 useful and well-known binary operations on A and B, returning the result in R. These operations are listed in the section "Operations" below, which provides a rigorous description of each. It is important to note here that "integer" refers to the mathematical concept of an integer. In particular, there is no concept of integer overflow or of binary representation. In the case of variables A, B, and L, integer values are unbounded. In the case of x, y, z, the variables may not violate their explicit bound; any operation that could potentially assign an out-of-range value to these variables is an error and forbidden. # Operations The following code snippet defines all 40 (potential) operations of f. In each case, a name, description, and precise mathematical definition is provided. As a convenience, each operation also includes a C function that (notwithstanding data type bounds) implements the operation when compiled by gcc. In all cases, the mathematical definition should be considered authoritative. <style>tr:nth-child(4n-3) td:first-child { width: 150px; font: bold 24px Times New Roman,Times,serif; }</style><style>tr:nth-child(4n-2) span { font-family: Courier New,monospace; }</style><style>tr:nth-child(4n) { font-family: Courier New,monospace; white-space:pre; }</style><style>tr:nth-child(4n) td { padding-bottom: 50px; }</style><script type="text/javascript" src="http://code.jquery.com/jquery-1.10.1.min.js"></script><div>Note that $$\left\lfloor\frac{A}{B}\right\rfloor _0$$ indicates "divide and truncate towards zero", and that $$\operatorname{sgn}\left( x\right)$$ indicates the signum function evaluated at $$x$$.<br><br>Also note that for operations conditionally returning $${\rm anything}$$, "anything" may be any value representable as an integer, or a fatal error. "Anything" does not have to be consistent from operation to operation. You may rely on the results returned for "anything" in subsequent calculations.</div><hr><br><br><div id="main">1. 0 [Constant 0] (0) $R = 0\cdot A + 0\cdot B$ {{return 0;}} 2. 1 [Constant 1] (1) $R = 1 + 0\cdot A + 0\cdot B$ {{return 1;}} 3. 2 [Constant 2] (2) $R = 2 + 0\cdot A + 0\cdot B$ {{return 2;}} 4. A [Value of A] (A) $R = A + 0\cdot B$ {{return A;}} 5. A + B [Sum of A and B] (sum) $R = A + B$ {{return A + B;}} 6. A - B [Difference of A and B] (diff) $R = A - B$ {{return A - B;}} 7. AB [Product of A and B] (prod) $R = AB$ {{return A*B;}} 8. A &#247; B [Truncated Quotient of A by B] (div) $R = \left\{ {\begin{array}{*{20}{l}}!!{\rm{anything}}&{{\rm{if\ }}B = 0} \\!!{\left\lfloor {\frac{A}{B}} \right\rfloor _0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return A/B;}} 9. A &#247; B Remainder [Remainder after Division of A by B] (rem) $R = \left\{ {\begin{array}{*{20}{l}}!!{\rm{anything}}&{{\rm{if\ }}B = 0} \\!!{A - B\left\lfloor {\frac{A}{B}} \right\rfloor _0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return A % B;}} 10. A modulo |B| [A Modulo |B|] (mod) $R = \left\{ {\begin{array}{*{20}{l}}!!{\rm{anything}}&{{\rm{if\ }}B = 0} \\!!{A\operatorname{mod} \left| B\right|}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{ int X, Q;!! X = B < 0 ? -B : B;!! Q = A % X;!! return Q < 0 ? Q + X : Q;}} 11. A = B [A Equals B] (is) $R = \left\{ {\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}A = B} \\!!{0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return A == B;}} 12. |A| > |B| [A is of Greater Magnitude than B] (gmag) $R = \left\{ {\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}\left| A\right| > \left| B\right|} \\!!{0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return (A > 0 ? A : -A) > (B > 0 ? B : -B);}} 13. A &and; B [Both A and B are Nonzero] (and) $R = \left\{ {\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}\left( A \neq 0\right) \wedge \left( B \neq 0\right)} \\!!{0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return A && B;}} 14. A &or; B [Either A or B is Nonzero] (or) $R = \left\{ {\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}\left( A \neq 0\right) \vee \left( B \neq 0\right)} \\!!{0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return A || B;}} 15. A &#8891; B [Either A or B is Nonzero, but Not Both] (xor) $R = \left\{ {\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}\left( A \neq 0\right) \wedge \left( B = 0\right)} \\!!{1}&{{\rm{if\ }}\left( A = 0\right) \wedge \left( B \neq 0\right)} \\!!{0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return (A != 0) ^ (B != 0);}} 16. A<sup>B</sup> [A to the Power of B] (pow) $R = \left\{ {\begin{array}{*{20}{l}}!!{A^B}&{{\rm{if\ }}B \geq 0\rm{\ or\ }\left| A\right| = 1} \\!!{0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return (int)pow( A, B );}} 17. &#189;(A + B) [Average (Arithmetic Mean) of A and B] (avg) $R = \left\lfloor\frac{A + B}{2}\right\rfloor _0$ {{return (A + B)/2;}} 18. A<sup>2</sup> + B<sup>2</sup> [Sum of Squares of A and B] (sumsqs) $R = A^2 + B^2$ {{return A*A + B*B;}} 19. A<sup>2</sup> - B<sup>2</sup> [Difference of Squares of A and B] (diffsqs) $R = A^2 - B^2$ {{return A*A - B*B;}} 20. &#189;((-1)<sup>A</sup> - (-1)<sup>B</sup>) [Synchronicity of A and B] (sync) $R = \left( -1\right)^A - \left( -1\right)^B$ {{return (int)(pow( -1, A ) - pow( -1, B ));}} 21. |A + B| [Absolute Sum of A and B] (abssum) $R = \left| A + B\right|$ {{return A + B < 0 ? -(A + B) : (A + B);}} 22. |A - B| [Distance from A to B] (dist) $R = \left| A - B\right|$ {{return A < B ? (B - A) : (A - B);}} 23. max( A, B ) [Maximum of A and B] (max) $R = \max\left( A, B\right)$ {{return A > B ? A : B;}} 24. min( A, B ) [Minimum of A and B] (min) $R = \min\left( A, B\right)$ {{return A < B ? A : B;}} 25. minmod( A, B ) [Minmod Limiter] (minmod) $R = \left\{ {\begin{array}{*{20}{l}}!!{\min\left( A, B\right)}&{{\rm{if\ }}A > 0 {\rm\ and\ } B > 0} \\!!{\max\left( A, B\right)}&{{\rm{if\ }}A < 0 {\rm\ and\ } B < 0} \\!!{0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{ if( A > 0 && B > 0 )!! return A < B ? A : B;!! if( A < 0 && B < 0 )!! return A > B ? A : B;!! return 0;}} 26. A ? B : 0 [Return B Conditionally] (condb) $R = \left\{ {\begin{array}{*{20}{l}}!!{B}&{{\rm{if\ }}A \neq 0} \\!!{0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return A ? B : 0;}} 27. &#189;(A + B)(|B - A| + 1) [Sum of Integers from A to B] (sumatob) $R = \frac{\left( A + B\right)\left( \left| B - A\right| + 1\right)}{2}$ {{return (A + B)*((B < A ? (A - B) : (B - A)) + 1)/2;}} 28. A <<<sub>2</sub> B [Left-shift A by B Zeroes in Binary] (rsh) $R = \left\{ {\begin{array}{*{20}{l}}!!{2^B A}&{{\rm{if\ }}B \geq 0} \\!!{\left\lfloor\frac{A}{2^{-B}}\right\rfloor _0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return B >= 0 ? A*(1 << B) : A/(1 << -B);}} 29. A <<<sub>10</sub> B [Left-shift A by B Zeroes in Decimal] (rsh10) $R = \left\{ {\begin{array}{*{20}{l}}!!{10^B A}&{{\rm{if\ }}B \geq 0} \\!!{\left\lfloor\frac{A}{10^{-B}} \right\rfloor _0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return (int)A*pow( 10, B );}} 30. A + sgn(B - A) [Increment A Towards B] (twrdb) $R = A + \operatorname{sgn}\left( B - A \right)$ {{return A + (B > A) - (B < A);}} 31. |A| sgn(B) [Magnitude of A with the Phase of B] (magphs) $R = \left| A\right|\operatorname{sgn}\left( B\right)$ {{return (A < 0 ? -A : A)*((B > 0) - (B < 0));}} 32. |A| > |B| ? A : B [Return Furthest From Zero: A or B] (ffzero) $R = \left\{ {\begin{array}{*{20}{l}}!! {A\rm{\ or\ }B}&{{\rm{if\ }}\left| A\right| = \left| B\right|} \\!!{A}&{{\rm{if\ }}\left| A\right| > \left| B\right|} \\!!{B}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return (A < 0 ? -A : A) > (B < 0 ? -B : B) ? A : B;}} 33. gcd( |A|, |B| ) [Greatest Common Denominator of A and B] (gcd) $R = \left\{ {\begin{array}{*{20}{l}}!!{\rm{anything}}&{{\rm{if\ }}A = 0\rm{\ or\ }B = 0} \\!!{\operatorname{gcd}\left( {\left| A\right| , \left| B\right|}\right)}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{ int X, Y, T;!! X = A < 0 ? -A : A;!! Y = B < 0 ? -B : B;!! while( Y != 0 ) {!! T = Y;!! Y = X % Y;!! X := T;!! }!! return X;}} 34. lcm( |A|, |B| ) [Least Common Multiple of A and B] (lcm) $R = \left\{ {\begin{array}{*{20}{l}}!!{\rm{anything}}&{{\rm{if\ }}A = 0\rm{\ or\ }B = 0} \\!!{\frac{AB}{\operatorname{gcd}\left( {\left| A\right| , \left| B\right|}\right)}}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{ int X, Y, T, P;!! X = A < 0 ? -A : A;!! Y = B < 0 ? -B : B;!! P = X*Y;!! while( Y != 0 ) {!! T = Y;!! Y = X % Y;!! X := T;!! }!! return P/X;}} 35. A*B/(A + B) [Harmonic Mean of A and B] (harm) $R = \left\{ {\begin{array}{*{20}{l}}!!{\rm{anything}}&{{\rm{if\ }}A + B = 0} \\!!{\left\lfloor\frac{AB}{A + B}\right\rfloor _0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return A*B/(A + B);}} 36. max(-|B|,min(|B|,A)) [Value of A Clipped to +/-|B|] (clip) $R = \max\left( -\left| B\right| , \min\left( \left| B\right| , A\right)\right)$ {{ int X;!! X = B < 0 ? -B : B;!! return A < -B ? -B : (A > B : B : A);}} 37. A|B| - B|A| [Commutator Bracket of A and B] (comm) $R = A\left| B\right| - B\left| A\right|$ {{return A*B < 0 ? (2*A*B*((B > 0) - (B < 0))) : 0;}} 38. |A| mod 10 = |B| mod 10 [A and B Have Same Last Decimal Digit] (sameldd) $R = \left\{ {\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}\left| A\right| = \left| B\right|\;\;\left(\operatorname{mod} 10\right)} \\!!{0}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{ int X, Y;!! X = A < 0 ? -A : A;!! Y = B < 0 ? -B : B;!! return X % 10 == Y % 10;}} 39. (A<sup>B</sup> - 1)/(A - 1) [Sum of First B Terms in Power Series 1 + A + A<sup>2</sup> + ...] (pwrsrs) $R = \left\{ {\begin{array}{*{20}{l}}!!{\rm{anything}}&{{\rm{if\ }}B < 0} \\!!{\rm{anything}}&{{\rm{if\ }}A \leq 1} \\!!{\frac{A^B - 1}{A - 1}}&{{\rm{otherwise}}}!!\end{array}} \right.$ {{return (int)(pow( A, B ) - 1)/(A - 1);}} 40. B<sup>2</sup>/(A<sup>2</sup> + 1) [Squared Distance of the Line Ax + B to the Origin] (sqdist2orgn) $R = \frac{B^2}{A^2 + 1}$ {{return B*B/(A*A + 1);}}</div><script type="text/javascript">$('#main').html( '<table>' + $('#main').html().replace( /([^$]+) \[(.+?)$ $$(.+?)$$ \\$(.+?)\\$ \{\{(.+?)\}\}/g, '<tr><td>$1</td></tr><tr><td>$2 (<span>$3</span>)</td></tr><tr><td>\$4\$</td></tr><tr><td>$5</td></tr>' ).replace( /!!/g, "\n" ) + '</table>' );</script><script type="text/x-mathjax-config;executed=true">MathJax.Hub.Config( { "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"], linebreaks: { automatic: true }, EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50) }, tex2jax: { inlineMath: [ ["$", ""], ["\\\$$","\\\$$"] ], displayMath: [ ["$$","$$"],["\$", "\$"] ], processEscapes: true, ignoreClass: "tex2jax_ignore|dno" }, TeX: { noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" }}, Macros: { href: "{}" } }, messageStyle: "none" } );</script><script src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML-full"></script> # The Nature of f The properties of f are summarized as follows: • The operations in f are purchased with operation points (OP) and branching points (BP). f is implemented using no more than 120 OP and no more than 20 BP. OP and BP purchases costs apply once per code element purchased. For example, the code while( A > 0 ) A = A - B;  incurs the costs of one while loop, one condition, one assignment, and one binary operation, even if the condition, assignment, and binary operation may be evaluated more than once. • No unary operations are permitted. • Constant conditions (e.g. true, false, or equivalent) are permitted. All non-constant conditions must be explicit (e.g. no if( A )). • Only the binary operations and conditions listed under "Binary Operations and Conditions" are permitted. • The ternary operation <condition> ? <iftrue> : <iffalse> is permitted at the cost of 1 BP plus any cost(s) associated with the operands. Languages that don't explicitly support this ternary operation may implement it as a function. • f must return a result in worst case O(log max(|A|,|B|)) time or better. • f may recursively invoke itself at a cost of either 1 BP or 2 OP, but only to a worst case stack depth of O(log max(|A|,|B|)) or better. • The following control structures are permitted in f: • if blocks cost 1 BP each plus the cost of the branch condition • if else blocks cost 2 BP each plus the cost of the branch condition • if elseif blocks cost 1 BP per if, elseif, or else, plus the cost(s) of any branch conditions • while loops and for loops cost 2 BP each plus the cost(s) of any initialization, loop condition, and loop update statements • do while loops cost 1 BP each plus the cost of the loop condition • goto, break, named break, continue, and named continue statements cost 1 BP each • return statements cost 1 BP each, with the exception of the last top-level return that appears in f, which costs nothing Programming languages that do not support the above structures may implement them as separate functions/methods/closures or as semantically equivalent code. For example, the code  while( 1 ) { <statement> ... if( A == B ) break; }  is semantically equivalent to the code  do { <statement> ... } while( A != B )  and hence the former may be used at the cost of 1 BP (the cost of a do while loop). # Variables and Data Types Variables and data types in f are summarized as follows: • No variables may be defined or used by f except for the parameters A, B, L, x, y, z, which may be both read and assigned. Variable assignments may not be chained or nested in expressions (e.g. A = B = 0, w = y == 1 || (z = 10) are not permitted). If a programming language does not support assignment to parameters, parameters may alternatively be copied into proxy local variables at the start of the function. Once this is done, the original parameters may not be referenced. • Variable assignment incurs no OP or BP costs. • Assignment to x, y, and z must respect the strict bounds on these variables. For example, if A is not guaranteed to be bounded by [-231 231), the assignment x = A is an error and illegal, even if a programming language would ordinarily allow it. The assignment x = A % 2 (with the semantics of the % operator defined below) is legal since all values of A are guaranteed to yield a legal value of x. Note that these same restrictions apply when passing arguments to recursive invocations of f. • It is recommended that A, B, L, x, y, z all be represented using the same type, but this is not a requirement. Implicit casts, explicit casts, method calls, and/or explicit function calls for converting between data types are allowed in all contexts, provided that both: • no clipping, truncation, or wraparound occurs as a result of the conversion • all operations on all data types are homomorphic to operations on the integers (notwithstanding the limited range of x, y, and z) • Constants may be defined at no cost, but may only have values in the range [-231 231). Constants with values outside this range can be realized via binary operations (e.g. 123456789*987654321) but these operations incur costs as normal. A constant may be defined using any data type and converted (implicitly or explicitly) to any data type so long as the conversion respects the rules listed above. • A, B, L are ideally represented by a "big integer" type while x, y, z are best represented as big integers or signed 32-bit ints, but these are not requirements. In particular, an implementation of f may choose to represent all variables using bounded data types, which is allowable subject to two restrictions: • under no circumstances may non-ideal effects such as clipping, truncation, floating point precision errors, etc. be used or exploited in the implementation of f • any implementation of f relying on bounded data types that has these types replaced with unbounded counterparts must function properly over all inputs in this expanded domain # Binary Operations and Conditions Only the following set of binary operations and conditions may be used in the implementation of f. Each operation/condition has a cost of 1 OP. Operations/conditions may be implemented in any way (e.g. via infix operators, function calls, method calls, etc.) provided they are stateless and they conform exactly to the given definitions. <style>tr:first-child { font: bold 18px Times New Roman,Times,serif; }</style><style>td { text-align:center; }</style><style>tr:nth-child(2n) { background-color:#eee; }</style><style>tr:not(:first-child) td:nth-child(3) { font-family: Courier New,monospace; white-space: pre; }</style><script type="text/javascript" src="http://code.jquery.com/jquery-1.10.1.min.js"></script><div id="main">addition $x + y$ {{x + y}} subtraction $x - y$ {{x - y}} multiplication $xy$ {{x*y}} integer division with truncation towards zero* $\left\lfloor\frac{x}{y}\right\rfloor _0$ {{x/y}} remainder of integer division* $x - y\left\lfloor\frac{x}{y}\right\rfloor _0$ {{x % y}} modulo** $x \operatorname{mod} \left| y\right|$ {{int k, q;!!k = y < 0 ? -y : y;!!q = x % k;!!return q < 0 ? q + k : q;}} binary left shift ${\begin{array}{*{20}{l}}!!{2^y x}&{{\rm{if\ }}y \geq 0} \\!!{\left\lfloor\frac{x}{2^{-y}} \right\rfloor _0}&{{\rm{otherwise}}}!!\end{array}}$ {{y >= 0 ? x*(1 << y) :!! x/(1 << -y)}} binary right shift ${\begin{array}{*{20}{l}}!!{\left\lfloor\frac{x}{2^y} \right\rfloor _0}&{{\rm{if\ }}B \geq 0} \\!!{2^{-y} x}&{{\rm{otherwise}}}!!\end{array}}$ {{y >= 0 ? x/(1 << y) :!! x*(1 << -y)}} logical AND ${\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}\left( x \neq 0\right) \wedge \left( y \neq 0\right)} \\!!{0}&{{\rm{otherwise}}}\end{array}}$ {{x && y}} logical OR ${\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}\left( x \neq 0\right) \vee \left( y \neq 0\right)} \\!!{0}&{{\rm{otherwise}}}\end{array}}$ {{x || y}} equality (Dirac delta) ${\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}x = y} \\!!{0}&{{\rm{otherwise}}}\end{array}}$ {{x == y}} inequality ${\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}x \neq y} \\!!{0}&{{\rm{otherwise}}}\end{array}}$ {{x != y}} less than ${\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}x < y} \\!!{0}&{{\rm{otherwise}}}\end{array}}$ {{r < y}} greater than ${\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}x > y} \\!!{0}&{{\rm{otherwise}}}\end{array}}$ {{x > y}} less than or equal to ${\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}x \leq y} \\!!{0}&{{\rm{otherwise}}}\end{array}}$ {{x <= y}} greater than or equal to ${\begin{array}{*{20}{l}}!!{1}&{{\rm{if\ }}x \geq y} \\!!{0}&{{\rm{otherwise}}}\end{array}}$ {{x >= y}} bitwise AND of absolutes $\begin{array}{*{20}{l}}!!{\sum\limits_k {{x_k}{y_k}{2^k}} {\rm{\ given}}} \\!!{\,\,\,\,\,\,\,\left| x \right| = \sum\limits_k {{x_k}{2^k}} } \\!!{\,\,\,\,\,\,\,\left| y \right| = \sum\limits_k {{y_k}{2^k}} } \\!!{\,\,\,\,\,\,\,{x_k},{y_k} \in \left\{ {0,1} \right\}\,\,\forall \,k}!!\end{array}$ {{(x < 0 ? -x : x) & !!(y < 0 ? -y : y)}}</div><hr><div>*division by zero is a fatal error<br>**modulo zero is a fatal error</div><script type="text/javascript">('#main').html( '<table cellspacing="0"><tr><td>Operation</td><td>Definition</td><td>C Code (gcc)</td></tr>' + $('#main').html().replace( /([^$]+) \\\[(.+?)\\$ \{\{(.+?)\}\}/g, '<tr><td>$1</td><td>\$2\$</td><td>$3</td></tr>' ).replace( /!!/g, "\n" ) + '</table>' );</script><script type="text/x-mathjax-config;executed=true">MathJax.Hub.Config( { "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"], linebreaks: { automatic: true }, EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50) }, tex2jax: { inlineMath: [ ["$", "$"], ["\\\$$","\\\$$"] ], displayMath: [ ["$$","$$"],["\$", "\$"] ], processEscapes: true, ignoreClass: "tex2jax_ignore|dno" }, TeX: { noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" }}, Macros: { href: "{}" } }, messageStyle: "none" } );</script><script src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML-full"></script> # Objective Your objective is to write a function or a program containing a function that implements as many of the 40 operations of f as possible. When invoked at the top level, the arguments of f are assigned as follows: • A and B specify the two general operands for the operation being selected. For any of the 40 listed operations where the result is not symmetric in A and B, you may return a result for swapped A and B if desired. For example, the function A + sgn(B - A) may alternatively return the value of B + sgn(A - B). Operations with swapped operands should be documented in your submission. • L must always be zero when passed to the top level invocation of f. Recursive invocations of f may pass any legal value to L. • x, y and z collectively specify the operation to be performed. This datum can be encoded any way you desire (respecting the limited range of these parameters). Your submission should include a list of at least one (x,y,z) tuple per implemented operation that causes f to compute the result for that operation. You may assume that only these tuples will be passed to a top level invocation of f, hence f may exhibit arbitrary behaviour (including errors and/or illegal operations) if undocumented tuples are passed to top level invocations. As with L, recursive invocations of f may pass any legal values to x, y, and z. The results of any such intermediary operations need not be documented. # Scoring Scoring rules are as follows: • If f does not implement all 40 operations, score 10 points per implemented operation plus 1 point per unused BP plus 1 point per unused OP. • If f does implement all 40 operations, score 400 points plus 50 points per unused BP plus 25 points unused OP. The highest scoring submission is the winner. # Origami Code Golf I like origami (especially unit origami), but lack the patience to actually complete a project. Sounds like a wonderful job for a computer! ## Objective Make a program or function that accepts a series of numbers (see next part) and outputs a folded version of a 1 x 1 square. ## Input You will receive a list of numbers {a,b,c,d,e,f},{g,h,i,j,k,l}... (curly braces only added for clarity) Each set of numbers corresponds to 3 coordinates (a,b), (c,d) and (e,f). (a,b) and (c,d) each lie on the unit square (which also means that it is in the first quadrant). (e,f) lies within the unit square, but on a portion of the paper that is not on the line formed by (a,b) and (c,d). (a,b) and (c,d) determine the line over which to fold the paper. The portion of the paper that (e,f) lies in determines which side of the paper remains stationary during the fold. You may assume that this value will always lie on a portion of the square (e.g. not on a part of the square that is not there because of a fold). For example, the input 0.5, 0, 0.5, 1, 0.25, 0.5 means that one should fold the paper in half over the vertical line at 0.5, with the left side remaining stationary. Each fold (set of input numbers) is sequential, so one fold is made after another. For example, if the previous example was followed by the input 0, 0.5, 1, 0.5, 0.75, 0.75, the paper should be folded over the horizontal line at 0.5, with the top part remaining stationary. ## Output Your program or function must only output (graphically) the resulting shape and rotation of the folding. It is not required to output the correct location or size. ## Test Cases input 0, 0.5, 1, 0.5, 0.5, 0.75 - input 0, 0, 1, 1, 0.25, 0.5 - input - 0.5, 1, 1, 0, 0.25, 0.5, 0, 0.25, 1, 0.25, 0.25, 0.75 - input - 0.5, 0, 1, 0.5, 0.5, 0.5, 1, 0.5, 0.5, 1, 0.5, 0.5, 0.5, 1, 0, 0.5, 0.5, 0.5, 0, 0.5, 0.5, 0, 0.5, 0.5, 0, 0.25, 1, 0.25, 0.5, 0.5 This is code-golf, so shortest code (in bytes) wins. • So all folds are valley folds? No mountain folds at all? You could add support for that by adding a command that flips the paper. Also, I don't think your resolution of the folding direction is unambiguous. Which way do I fold a fold that goes from the top left corner to the bottom right corner? And what coordinate system are you using? – Martin Ender Dec 7 '14 at 22:28 • I'm sorry, but all of that seems contradictory. If the origin is in the upper left, I assume that the y axis points down. In that case, the fold would be indicated by (0,0) to (1,1). This fold can occur bottom left to top right or vice versa. Your first rule says we should fold right, but the second rule says we should fold down. Therefore, I think this is ambiguous. – Martin Ender Dec 7 '14 at 22:36 • Hopefully this is better specified. (BTW, I was confused when you said top left to bottom right. That would have worked left to right/top to bottom. I see what you meant now). – Stretch Maniac Dec 8 '14 at 3:30 • "Your program or function must only output the resulting shape and rotation of the folding." In what format? Your examples show pictures, but it's not clear whether this is intended to be a graphical-output question or whether e.g. a list of vertices is acceptable. – Peter Taylor Dec 8 '14 at 9:59 • This challenge proposal has been inactive for over a month. I would like to take ownership of the challenge and make it ready for posting. Please let me know within the next 14 days if you have any objections and would still like to finish and post this challenge yourself. – Nathan Merrill Apr 12 '15 at 19:05 • Feel free to post it yourself. I have no objections to your ownership. Good luck! – Stretch Maniac Apr 12 '15 at 19:31 ## Phoneword generator This is ### Goal The goal is to write the shortest phoneword generator. ### Input As input you get for just a sequence of numbers (0-9). Given via stdin. ### Output You should write the first 15 possible results to stdout bonus points if the output only contains real words. The words need to have the exact same length like the input string. What if there are less than 15 options? Then you can just make up words. ### Phoneword A phoneword, is a sequence of characters, that is typed with letters in your phone which map to the numbers they display. How to treat 0 and 1 If the input contains a 0 or a 1, you should treat them as 0 and 1. To make a word with them anyway, you can use leetspeak. ### Mapping For the mapping check this picture: Taken from wikipedia As example I use codegolf itself: 26334653 translates to CODEGOLF it also gives many more words, here is a list. ### Bonus You can divide the amount of characters by 2, if your code gives only words which are in listed in the Oxford dictionary. For that you are allowed to use a web api to check them. • Why is it a [restricted-source]? Are there any characters we cannot use in our code? – ProgramFOX Dec 29 '14 at 11:32 • Seems pretty similar to this question. The only difference seems to be that you require full matches. – Sp3000 Dec 29 '14 at 11:36 • @ProgramFOX Because I would like to ban languages that are mode for codegolf, I gonna add this. – Knerd Dec 29 '14 at 12:59 • @Knerd That isn't indicated by [restricted-source]; there isn't a tag for that. But why banning golfing languages? That doesn't seem fair to me. – ProgramFOX Dec 29 '14 at 13:02 • @Sp3000 I agree, that it is similar, but I still would see a difference in the questions themselves, because a) it needs an exact match and b) the 1 and 0 are valid ;) – Knerd Dec 29 '14 at 13:03 • @ProgramFOX I edited it a bit, check under rules. The main reason is, usually golfing languages win a contest, because they are made for that purpose. Which seems unfair for me towards other languages. – Knerd Dec 29 '14 at 13:06 • Then what does count as a "golfing language"? If you disallow them, there in my opinion should also be a clear definition of what exactly is disallowed. – ProgramFOX Dec 29 '14 at 13:18 • @ProgramFOX I think you are right. I'll go and remove that part. – Knerd Dec 29 '14 at 13:22 • It's not clear from the question what the input is, what the output is, what mapping between letters and digits you assume, what you mean by a word, or why it isn't a duplicate of the question which Sp3000 mentioned. – Peter Taylor Dec 29 '14 at 14:47 • @PeterTaylor I updated it a bit. – Knerd Dec 30 '14 at 14:52 • If there are less than 15 possibilities that are allowed by the Oxford dictionary, should the code output only the dictionary-approved possibilities, or make it up to 15 with other possibilities? – trichoplax Jan 3 '15 at 23:41 • The question as written doesn't specify whether 1 and 0 are valid in the input, and if they are, how they should be treated. – trichoplax Jan 3 '15 at 23:44 • @githubphagocyte check my edit :) – Knerd Jan 4 '15 at 14:45 • I would recommend phrasing Then you can just make up words more clearly. I'm guessing you mean that the remainder of the 15 possibilities do not need to use real words? – trichoplax Jan 4 '15 at 14:51 • To ensure everyone has the same interpretation of the rules, I would recommend clarifying what you mean by leetspeak. Does this mean 1 can be used as L and 0 can be used as O? Or can 1 only be used as i? Or either? – trichoplax Jan 4 '15 at 14:53 # Generate a Random Boolean Expression In this challenge, you generate a random Boolean expression -- and then evaluate it. ## Input Nothing, or a random seed if your program requires one. ## Output A random Boolean expression and its value, formatted as a string <expr> = <value>  The expression should be generated according to the following BNF grammar: <expr> ::= "0" | "1" | "(" <expr> "^" <expr> ")" | "(" <expr> "v" <expr> ")" | "(" <expr> ">" <expr> ")" | "~" <expr>  Here, ^ stands for binary AND, v for binary OR, > for implication, and ~ for NOT. Whitespace is not significant. The correct value for the expression should be self-explanatory. Some correct outputs include 0 = 0 ~ (~1 ^ 1) = 1 ((1v1) ^ ~(0 >(1 ^ ~~~0))) = 0  ## Detailed Rules Assuming a perfect random number generator, your program must be able to generate any valid Boolean expression with nonzero probability (discounting whitespace). You must use you language's standard RNG, or one of higher quality. You can write either a function or a full program, and a function can either return its result or print it to STDOUT. The fewest bytes wins, and standard loopholes are disallowed. I'd like some input on whether this challenge is essentially similar to either this or this. • The intro line talks about evaluating the expression, but none of the rest of the question does, and it seems to me that an approach which builds up the string and the value in parallel would meet spec. In that case, it's not a duplicate of the second question. It's borderline-duplicate of the first one, though. I probably wouldn't vote to close as a dupe, but I wouldn't put money on it staying open. – Peter Taylor Jan 15 '15 at 9:39 # Operator, i can't remember my phone number... code-challengequine "Hello? Operator? How do i get my phone to tell me its own number?" The challenge is to write a quine -- from your cellphone. Not a smartphone with a virtual keyboard, mind you. One of the old phones, where to get a 'c' you have to press 2 three times. Because programmers are lazy, you want to do it in the least amount of keypresses. A previous challenge (Calculate cell-phone keypresses) was to calculate the amount of keypresses it takes to produce a set of characters on a cellphone keyboard. The challenge there wrote out all the keymappings well, so i'll just quote it here. The keymaps are: 1:1 2:abcABC2 3:defDEF3 4:ghiGHI4 5:jklJKL5 6:mnoMNO6 7:pqrsPQRS7 8:tuvTUV8 9:wxyzWXYZ9 0:<space><newline>0  To type exaMPle TExt 01 , you would press 33 99 2 6666 77777 555 33 0 8888 33333 99 8 0 <a 1-sec pause here in real life but we'll ignore it>000 1 for a total of 37 keypresses. The * key brings up a map of special characters: .,'?! "-()@ /:_;+ &%*=< >£€$¥
¤[]{}
\~^¡¿
§#|


with the first one (.) highlighted. You can move to highlight the required character using rectangular navigation keys and it takes another keypress to select.

So to insert $, you would press *↓↓↓↓→→→<select> i.e. a total of 9 key-presses. This means, that if you use a = 3 in your code, that is a (1), space (1), = (8), space (1), 3 (7), for a total of 18, even though it's only 5 bytes. So as not to rule out languages/entries that use characters outside of this range, you can reach it with #, insert, special, select, {type the Unicode number of the character}, select for a total of 5 + Unicode #. I suppose you could use this trick to reduce the number of keypresses via *. ## Scoring Your score is the number of keypresses used to type out the code. There is a Stack Snippet that you can use to calculate. It automatically picks the lower number if you could use either * or #. The entry with the lowest score after 2 weeks wins! • To facilate easy calculating of the score, i plan to include a snippet with the JS entry from the old challenge. – Scimonster Jan 22 '15 at 20:34 • While I think the scoring is a nice twist, I'm not a fan of reusing exactly the same challenge. This way, the scoring seems more like a gimmick than anything else. So I'd prefer if you used it for a different challenge (which may still be related to cellphone keys, just not exactly the same). Also, just a note, please don't actually tag it code-golf - the scoring is too different not to tag it code-challenge. – Martin Ender Jan 22 '15 at 20:35 • I actually thought of my challenge first, and only after went to see if it had already been asked. But if you think it's too similar, i'll try and think of a slightly different challenge. – Scimonster Jan 22 '15 at 20:37 • I redid the whole thing, what do you think of it now? – Scimonster Jan 25 '15 at 18:58 • I have an APL phone where every funny symbol has its own button. – feersum Jan 26 '15 at 9:01 • I like this scoring idea and definitely want to see a challenge based on it, even if it isn't a "quine" challenge. – PhiNotPi Feb 27 '15 at 4:09 • For once CJam wouldn't win – HEGX64 Apr 4 '15 at 10:32 # Find longest alphabet path (code-golf) You are given a 2d array of size nxn that is filled with lowercasel letters a-z. Your goal is to find the longest continous path by only moving up/down/left/right. A path is a sequence of cells of the 2d grid, where the successor of the current cell must be a neighbour that is above, below, left or right. Also, each cell of the array can only be visited once per sequence. The value (the lowercase letter) of the successor must right before or after the one in the current cell (if the current cell has the value c, the successor must have value b or d). # Output You have to solve two tasks: • The challenge stated above • The challenge stated above plus another restriction: successors can only have the next letter in the alphabet, but not the previosu (if the current cell has the value c the successor must have the value d) The output must consist of two n x n grids the same size as the input, each for one of the two tasks. The grids have to be the identical again, but all the unused cells that are not part of the longest sequence have to be set to a whitespace. If there are two or more longest sequences, only one arbitrary one of them has to be in the output. # Testcases (more to be added) Input: Out1: Out2: ababa ababa ab babab babab ababa ababa babab babab ababa ababa Input: Out: Out: aba aba ab aba aba abcd abcd abcd hgfe hgfe hgfe gfeb gfeb babc babc  • This looks to me like a duplicate of codegolf.stackexchange.com/q/44922/194 – Peter Taylor Jan 28 '15 at 10:53 • Thanks, I didn't remember that challenge, but to me it seems different enough for a new challenge: On the one hand this challenge uses a 2d string instead of 1d on the other hand there is no restriction to words plus another output format needed. I think the overall ideas and needed approaches are quite different. Inspiration (i do not know what those puzzles are called genearlly) – flawr Jan 28 '15 at 10:59 • I see it as two versions of the longest path problem on sparse graphs with different graphs. – Peter Taylor Jan 28 '15 at 11:06 • Ok if you look at it like this, they are indeed the same problem, but I think the implementation will provide very different challenges. – flawr Jan 28 '15 at 11:14 # Logic Dots code-golfpuzzle-solver - Posted • This wants the tag puzzle-solver. It isn't clear until really late that the shapes to place are all lines (or a by 1 rectangles, if you prefer): making that clear quite early would be useful. Without that context, the two 2s in the second example look like a requirement to place a 2x2 square. On my first read-through I took "they can also be vertical" to mean that some of the input shapes could be vertical: it wasn't until I saw the examples that I could reinterpret it as "You may rotate the shapes when placing them". – Peter Taylor Jan 27 '15 at 9:30 • @PeterTaylor fixed. – globby Jan 27 '15 at 15:48 • Posting test cases as an answer is a bad idea. To shorten the post, you could try putting the examples side by side, and you could use Stack Snippets. – Peter Taylor Jan 27 '15 at 22:45 # Hide your code in a Boggle board! This proposal is intended to supersede my earlier proposal Find the Needle in the Haystack, of which I'm not convinced any more that it would work very well. I'll keep both proposals around for now, though. ## The Cops' Challenge First, choose a program output, consisting of less than 100 printable ASCII characters (character code 0x20 to 0x7E, inclusive) - in particular the program must be written on a single line. Next, you should write a number of programs (not necessarily in the same language), which all output that exact same string (including any trailing newlines) to STDOUT or closest alternative. Each of those programs should be made up of less than 100 printable ASCII characters, too. Finally, design a Boggle board, which contains all of these programs. The Boggle board may contain as many unused character as you wish, but it has to be rectangular and all characters have to be in the printable ASCII range. See "Boggle Rules" below for how the Boggle board works. You want the number of programs to be large, the board to be small and the programs to be hard to find. None of the programs must take any input. You may print to STDOUT, a GUI dialog (as with JavaScript's alert()), or assume a REPL environment (like a browser console) - but if it's different from STDOUT, you need to state clearly where your output will go in each case. Each program has to complete within 5 seconds on a reasonable machine. You are not allowed to use cryptographic methods, hashing functions, random seeds or string compression. If your submission's boggle board is X characters wide, and Y characters tall, and you've hidden N programs in it, your submission's score is N3/(X*Y). You should deliver: • X, Y, N and your score. • The languages of your N programs, including output destination if it differs from STDOUT. • The Boggle board. • The output of the programs. An answer is cracked if N programs in the specified languages are found by a single robber (see The Robbers' Challenge below). If your answer has not been cracked for 7 days, you may claim immunity by revealing the programs in your answer (to prove that your answer was solvable). The winner will be the immune submission with the highest score. ## The Robbers' Challenge Every user has one attempt at cracking each submission. Your cracking attempt will be a list of programs found in a the submission's Boggle board. If your guess matches the description (all programs can be found according to the Boggle rules, all produce the correct output to the correct destination, and they are written in the required languages), and you are the first correct guess, then you get N*X*Y points. It is important to note that your programs do not have to exactly match the originals, as long as they meet the specification and can be found in the Boggle board. This means there could be more than one correct answer. The robber with the most points wins. In the case of a tie, the robber who submitted fewer cracks wins. Robbers should post their cracks as answers to the associated Robbers' thread. ## Boggle Rules • To find a program in a Boggle board, you start at an arbitrary cell and add characters to the string by repeatedly moving to one of its neighbours. • You may move one cell at a time, horizontally, vertically, or diagonally. • No cell must be used more than once (within a single program or by multiple programs). ## Example Consider this Boggle board as a cop submission: 1$int
arun"
!pts0
b "2K


Along with the specification that the output is 20, and that there are 2 CJam programs, one Python 2 program and one Ruby program. A robber could now find:

• K in the bottom right corner and 20 next to it as two valid CJam program.
• print "20" as a valid Python 2 program:

__i__
_r_n"
_pt_0
_ "2_

• puts"20" as a valid Ruby program:

_____
__u_"
_pts0
__"2_


If no one cracked this, the cop's score would be 42/(5*4) = 0.8. If someone did crack this, that robber would get 4*5*4 = 80 points.

## Sandbox Notes

• I intend to provide stack snippets which generate leaderboards for the cops and robbers.
• The scores probably need some balancing. Suggestions?
• I admit that the robbers' challenge is pretty similar to Calvin's Hobbies' recent challenge. This happened purely by accident - I was originally thinking about a word search C'n'R, which would have been too easily brute-forcible, so I changed it to a Boggle board. Of course, that doesn't matter when considering if it's a duplicate of course, but I think with hand-designed boards, looking for programs with fixed outputs in prescribed languages, makes this quite different and should hopefully make for a more balanced challenge. Furthermore, the cops' challenge of designing the boards is completely different. Please let me know if you disagree, though.
• Should I allow cells to be reused within a single program?
• I'd guess that allowing cells to be reused within a single program would make it much harder for a cop to prevent multiple unintended programs appearing in the board. – trichoplax Jan 24 '15 at 10:10
• I dislike the 'output any 100 printable ASCII characters rule' from the Unscramble challenge. It makes it too easy for cops, who can print out any stream of gibberish. It some languages, it is even possible for them to enter random characters without even knowing what the code does. – feersum Jan 26 '15 at 9:09
• @feersum I'm absolutely open to suggestions for better tasks. – Martin Ender Jan 26 '15 at 10:18
• How about recommend allowing cells to be reused (the whole fun of Boggle), but allowing one program per language? – Ypnypn Jan 29 '15 at 15:56
• @Ypnypn hm, sounds like a good idea. – Martin Ender Jan 29 '15 at 18:44

# Cursor Wars

This question is based off of my previous Navigate Text with Arrow Keys golf. Here, a segment of text is the battle arena, and the opponents move like cursors.

## Idea 1: Tron / Light-Bikes

As the cursors move left to right, they paint parts of the text. Neither cursor can move through a painted area. The cursor who runs out of moves first loses.

To add a twist to the board's topology, I could make it so that the text area is flipped for the opponent. If I see the board:

X-----
---
------Y


Then the opponent sees the board:

Y------
---
-----X


With line-wrapping working differently for each player, they don't have the same movement patterns.

## Idea 2: Area Painting

Like in the Tron idea, cursors paint an area. The cursor that paints the most area wins.

I could make it make a few versions

• Area painted once cannot be repainted: the winner is the cursor that painted the majority of area
• Area can painted my moving right and cleared by moving left (backspacing). The winner is the one that painted the most area times time. (Each time step, players earn one point per painted area.)
• Idea 3 (rather vague): Put actual characters on the board and have people collect them to form words or sentences (either as the winning criterion or to get some form of power-ups). This could still be based around a Tron idea, or characters could simply be used up (so that others can still travel there, but thy can't collect those characters again). – Martin Ender Feb 9 '15 at 16:37

# War of the Partitions

You have been assigned 1000 men to your cause, and you must fight your opponent on 20 different battlefields simultaneously. You must decide how to split up your 1000 men into 20 ways. Furthermore, since the Nth battlefield is larger than the (N+1)th battlefield, the 20 partitions must be in non-increasing order.

Each battlefield will have a skirmish. If you send more men than your opponent, you win that skirmish. Winning more skirmishes than your opponent across all battlefields scores you 1 Battle Point.

You will then face every other opponent, where you will be allowed to reassign your men to another location. You have a large supply of necromancers that allow you to keep all of your men alive from battle to battle, so you may allocate all 1000 men every time you face another opponent.

You will face each opponent 25 times. The player with the most Battle Points wins.

# IO

You will be passed a string of the history of the battles between you and your current opponent. Each line consists of a different battle. The choices will be space separated, and your opponent's choices will be listed first, separated by a comma. The following input:

50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50,60 59 58 57 56 55 54 53 52 51 49 48 47 46 45 44 43 42 41 40
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50,51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 21


would represent two battles between a player. The first one would be a tie (each player won 10 skirmishes), while the second you won a Battle Point by winning 19 skirmishes.

You must return a string containing a space separated list of integers. The total of all of the values must be 1000, and must be in decreasing order.

• This game idea sounds very... familiar... but I don't see any KOTH based on it. Seems like a good idea. – PhiNotPi Feb 11 '15 at 23:38
• Maybe change decreasing to non-increasing to prevent ambiguity. – randomra Feb 14 '15 at 17:43
• Will the 25 battles be consecutive? It could be much quicker to save state (if allowed) than re-parse the whole history. (edit: file IO maybe slower, depends on the submissions and time limits) – randomra Feb 14 '15 at 17:49
• @rcrmn the two battling bots are side by side. The top line is the first battle, the second line is the second battle. – Nathan Merrill Feb 24 '15 at 14:24
• Sorry, I totally misread it! – rorlork Feb 24 '15 at 14:24

Do you have a large number of source files that you forgot to put a header on, but never bothered. Well then this challenge is for you! This is code golf, so shortest program that works wins.

# The Challenge

Write a function (if your language doesn't support this, write a program, that accepts a cmd line arg for the file name) that takes the name of a file then attaches to the top of that file a comments section stating the name of the author, the current date, and the file name, as comments in your language (if your language supports comments, if not then in C-Style/Doxygen).

For instance, if your language was C/C++ the following must be appended at the top. using myself as the example.

/** \author Henry Schmale
* \date 2015-02-19
* \file [File Name]
*/


# Notes

• You may subtract the length of your name from your submission.
• Languages that don't support file I/O are not eligible for this code golf.
• The date code should be in a human readable format, no unix time. Preferably in ISO format.
• if your language supports multiple comment formats, you may use either or so long as the final result is the same, a documentation header on that file.
• @MartinBüttner I did this before I learned how to use doxygen. – HSchmale Feb 19 '15 at 0:47
• What file name should be used if reading from stdin and writing to stdout? – Peter Taylor Feb 19 '15 at 12:21
• The spec regarding the file name is a bit confusing now. First you say "Write a function [...] that takes the name of a file then attaches to the top of that file [...] the file name" but then you say "Assume the file name is main.c". I think a simpler option would be to always take the file name as a command-line or function argument, but allow people to choose between STDIN/STDOUT, file I/O and another function parameter/return value for the actual file contents. – Martin Ender Feb 20 '15 at 9:26
• So why did you go back to disallowing languages without file system support now? :/ – Martin Ender Feb 21 '15 at 10:18

I'm only posting this in the sandbox because it may be too broad, even for a pop-con. If it gets some support I'll post it very soon.

# Generating Postmodernist Writing and Other Logorrhea

Postmodernist writings are known for dealing with highly abstract ideas, potentially in a verbose manner that may sound nonsensical to someone reading them. This type of writing is often called logorrhea, and is not limited to postmodernism.

People have made programs that use natural language processing to generate realistic looking academic writings that are actually utter nonsense. One example is the Postmodernism Generator (wiki), which creates a random postmodernist essay every time the page is loaded. Another example is SCIgen (wiki), which can generate random papers about computer science.

Your task in this popularity contest is to write a program that can generate random, convincing paragraphs of academic logorrhea. You can choose what topic your program will generate text about. Postmodernism, CS, math, physics, and philosophy seem to be likely choices, but you can choose something else.

• Your program must be able to take in a 32 bit integer (a value from 0 to 232-1) as a seed value and output a random paragraph of text on your topic. None of the 232 outputs should be identical. (If desired, you can include an option for no input, where the seed number is just chosen randomly.)
• The paragraphs should be from 2 to 8 sentences long and between 300 and 1000 characters. The sentences should start with capitals and end with periods. Including other punctuation is optional.
• The actual content of the sentences does not need to make grammatical sense, though it should consist of real English words. Presumably, the more it does make sense the more it will be upvoted.
• You do not need to include author names or citations like the Postmodernism Generator does. You could though, and you are welcome to take some liberties and generate a full essay or a mini-paper or something if it's clear that what you're doing is more difficult that just generating a paragraph.
• You may use any NLP libraries or resources, provided they don't already automatically generate random academic text. e.g. taking a paragraph from a random SCIgen paper would not be allowed at all.

• Perhaps it needs to be narrowed down to a specific topic/area. How about homeopathy? – trichoplax Feb 25 '15 at 12:53
• @trichoplax: Randomly generated articles on homeopathy might end up getting published. ;) – Alex A. Apr 2 '15 at 2:57
• @AlexA. that would be priceless :) The winning condition could be the number of homeopathy journals it gets published in. – trichoplax Apr 7 '15 at 21:28

# Which Children Don't Play Well Together? [code-golfchallenge]

You are a kindergarten teacher who is having problems with fights breaking out among the students. You have noticed that altercations happen only when certain groups of children are together. A group of children who can't play well together, but will coexist peacefully if any one student is removed from the group, is known as a MIKG (minimal incompatible kindergartener group). Every MIKG contains at least two children. To help prevent problems, you decide to identify all such groups of kindergarteners.

Each day, your class has Group Reading Time. This involves dividing the children into groups of 1 or more students, who take turns reading pages from a picture book. If all the children from an MIKG are placed in the same reading group, a commotion will erupt. The distraction rapidly involves all the students in the class, so you can't tell which reading group it originated from.

You want to find all the MIKGs as soon as possible, so you write a computer program to help you do the math. Let f(N) be the maximum number of days it will take to identify all the MIKGs in a class of size N, assuming an optimal strategy is used. The program should not take more than f(N) days to find the answer.

## Input/Output

At the beginning of the program, it takes a positive integer input of N which tells the number of students in the class. Then, the program creates a plan for the day's reading groups. The user (kindergarten teacher) will input 1 if a disruption occurred during reading time, or a 0 if it remained calm. When the program determines all the MIKGs, it shall print them out and exit.

## Challenge

You will be given random test cases for class sizes between (a) and (b). The goal is to determine the MIKGs in as few days as possible. The program that makes the smallest amount of queries is the winner, with tiebreak by earliest post.

## Restrictions

• The program must respond in under (x) seconds
• Due to the interactivity requirement, you must submit a full program, not a function.
• You may specify any format for the I/O as long as it is clear, unambiguous, consistent, and doesn't use characters other than printable ASCII and newlines.

## Sandbox notes

• I presume that an MIKG must contain at least two children, but it would be good to make that explicit. – Peter Taylor Mar 12 '15 at 9:01

# Introduction

If you take a look at the front panel of your desktop or laptop computer, chances are that you'll find a handful of blinkenlights, including a hard disk activity indicator.

Image taken from here

The idea of this challenge is to "play" the Shave and a Haircut melody with that light.

Your task is to write a full program with the following behavior. If the program is placed in an empty directory, compiled (if applicable) and run, it causes the hard drive activity light to blink the notes of the Shave and a Haircut melody (unless, of course, the hard drive is active for some other reason). After that, it shall exit gracefully.

# Precise Rules

The specification of the melody is as follows. Let t be a unit of time between 0.2 seconds and 0.7 seconds. Starting from some time tinit, the activity light shall blink at tinit, tinit + t, tinit + 1.5*t, tinit + 2*t, tinit + 3*t, tinit + 5*t, and tinit + 6*t. The blink must be long enough to be noticed by the human eye, but no more than 0.25*t.

Your program may create and modify any files and subdirectories in the directory it is placed in, including its own source code. The program does not have to be cross-platform, but you must state your operating system in your answer, and any necessary hardware requirements. In particular, some environments allow the blinkenlights to be controlled manually; this is perfectly acceptable, but must be explicitly stated.

Your program may not damage or significantly alter the host computer.

# Scoring

This is code-golf, so the lowest byte count wins. Standard loopholes are disallowed.

## Sandbox Notes

My main concern is whether my challenge would be too similar to this.

• This seems somewhat hard to test. The hard drive activity in response to a given file access sequence could depend on the model of drive, the filesystem, and any number of filesystem or OS config options. I don't think it's reasonable to expect anyone to be able to state the hardware and config requirements. – Peter Taylor Mar 16 '15 at 14:48
• Musical nitpick: what you want is the Shave and a Haircut rhythm not melody. I thought you were asking something more difficult (especially as I didn't know that jingle was called that.) I like the challenge though. – Level River St Mar 24 '15 at 2:02
• I think this might have a problem - lots of processes go on at all times in a computer. It would be hard to predict when the light just blinks randomly, and you couldn't shut those processes down (i.e, compiz on Linux). Plus, how would the challenge be verified, and what if it was only qualified/disqualified because of a random blink? – ASCIIThenANSI Apr 7 '15 at 13:07

I've been reading this forum for a bit and I thought it might be a good idea to do a short sequence of challenges themed on famous mathematicians. It's my first post here so please point out any shortcomings.

It is Irving Kaplansky's birthday today. Among other things he is famous for his conjectures on group rings. It is one of these conjectures in mathematics that requires virtually no special knowledge to understand. There a couple of words that need explaining in them but their definitions are very simple. These words are "group", "torsion-free group", "ring", "domain", "group ring", "idempotent", "unit".

Please read up if you want to. This challenge doesn't require understanding these words or the conjecture. All that's needed is the concept of a finite cyclic group. I'm sure most of you know what it is, but I'll give a short introduction. A cyclic group of order n can be understood as what you get when you take something (whatever) called a generator, say p, and decide that it can be raised to integer powers. These powers can be multiplied like so: pk * pl = pk+l. But there's one catch: whenever the exponents of the powers give the same remainder from the division by n, these powers are considered equal. This means, in particular, that there are exactly n powers really: p0, p1,...,pn-1. Any other power is equal to one of these.

The challenge is to implement a certain operation on certain formal expressions involving these powers. The expressions are of this form:

r0 * p0 + r1 * p1 + ... + rn-1 * pn-1,

where all ri are real numbers.

The operation, called multiplication, consists in, first, multplying two such expressions as if they were real sums, that is for example, for n=3:

(2 * p0 + 3 * p1 + 2 * p2) * (0 * p0 + 1 * p1 + 2 * p2)=

(2 * p0) * (0 * p0) + (2 * p0) * (1 * p1) + (2 * p0) * (2 * p2) +

(3 * p1) * (0 * p0) + (3 * p1) * (1 * p1) + (3 * p1) + (2 * p2) +

(2 * p2) * (0 * p0) + (2 * p2) * (1 * p1) + (2 * p2) + (2 * p2).

Then, we simplify each of the summands according to the rule

(r * pk) * (s * pl) = (r * s) * (pk * pl) = (r * s) * pk+l.

And finally, we simplify the resulting sum according to the rule

(r * pk) + (s * pk) = (r + s) * pk.

This means that for n=3, we have 2 * p2 + 5 * p5 = 7 * p2 because p2=p5!

The resulting sum is again of the form

r0 * p0+ r1 * p1 + ... + rn-1 * pn-1

after we order the summands by the exponents.

This operation is exactly the product in the group ring R[C], where R is the field of real numbers and C is a finite cyclic group. This group ring doesn't satisfy the hypothesis of Kaplansky's conjecture because finite cyclic groups aren't torsion-free.

Your task is to implement this in any language. Your program/procedure/whatever has to take a natural number n>0 as user input. This will be the order of your cyclic group. Then it has to take 2n "real numbers" as user input. I don't really care what the "real numbers" are in your implementation. They could be ints for all I care. Just make them something that can reasonably be interpreted as real numbers and has a reasonable arithmetic. The first n numbers will be the coefficients of the first formal sum and the other n numbers will be the coefficients of the second formal sum. You need to output the n coefficients of their product. You don't need to compute the product in the way describe above. It just has to be correct (modulo rounding errors and other things computers do wrong with numbers).

Shortest code wins. You can assume the input is valid. Both input and output can be in any reasonable form. I'm not sure if this is a good restriction on this site, but I'd like you to think "actually usable". Though I don't really care about how long it takes to compute. I guess all standard loopholes apply, as I've noticed it seems to be a mantra here. :-)

• Did you mean to shift the indices in "r_1 * p^0 + r_2 * p^1 + ... + r_(n-1) * p^(n-1)"? Also, do I understand right that you're asking for us to multiply formal polynomials under the relationx^n = 1? – xnor Mar 22 '15 at 22:53
• @xnor I didn't mean to do that! And yes, that's one way of saying this. Another way of saying it is to multiply elements of the group ring R[C] where C is a finite cyclic group and R is the field of real numbers. My goal is to introduce the concept of a group ring and this is one of the simplest cases. For the infinite cyclic group it would amount to the Laurent polynomials, and that's too familiar I think. This is the next simplest case. – ymar Mar 22 '15 at 22:59
• @Martin Done, thanks! – ymar Mar 22 '15 at 23:18
• @xnor I've corrected the indices (there were some more errors). Do you think this is too simple? I was thinking of doing it with the quaternion group... – ymar Mar 22 '15 at 23:19
• Added the statement that this is a group ring product. – ymar Mar 22 '15 at 23:23
• I think the problem is OK, but people might just do this by multiplying regular polynomials and then combining x^(n+i) with x^i. I like the group idea, but I've already done the quaternions. – xnor Mar 23 '15 at 4:03
• @xnor Well, for the quaternions it wouldn't be as simple. Perhaps I could stipulate that one of the answers to your problem should be used in some way? – ymar Mar 23 '15 at 4:16
• What do you mean that it wouldn't be as simple? – xnor Mar 23 '15 at 4:20
• @xnor I mean that it wouldn't be just a simple variation on polynomial multiplication. It's still similar because that's what the (semi)group ring multiplication is: a generalization of polynomial multiplication. But the case of the quaternion group is further away from polynomials than cyclic groups. – ymar Mar 23 '15 at 4:24

# Functioning HTML-Encoded Program

Introduction

When showing code to others on the web, some characters are generally replaced by their HTML-encoded entities. Browsers display this properly, but if a user copies the code directly from HTML or a script tries running the code without decoding its entities, the code will likely contain errors.

Challenge

You are to come up with a program that uses all of the following five characters: ", &, ', <, and >. When encoded to their named XHTML entities, the code must still run using the following respective entities: &quot;, &amp;, &apos;, &lt; and &gt;. The code must be able to run both ways without throwing errors. Each of the five characters must be used outside of comments and string-like objects at least once (ie. for JS, outside of literal regex). You may use an expression in place of a statement up to one time (if your language supports it).

Example JS Script (1/5 required characters)

Unencoded: (Sets lt to true)

var lt = 6;
lt = 3 < lt;


Encoded: (Sets lt to 2)

var lt = 6;
lt = 3 &lt; lt;


Encoder/Decoder

Here's a converter to make testing your code easy (click run code to use):

function encode() {
document.getElementById('post').value = document.getElementById('pre').value.replace(/&/g, '&amp;').replace(/"/g, '&quot;').replace(/'/g, '&apos;').replace(/</g, '&lt;').replace(/>/g, '&gt;');
if (entity=document.getElementById('pre').value.match(/&\S+?;/)) alert('Warning: Unencoded text may already have entities. (ie: ' + entity[0] + ')');
} function decode() {
document.getElementById('pre').value = document.getElementById('post').value.replace(/&quot;/g, '"').replace(/&apos;/g, '\'').replace(/&lt;/g, '<').replace(/&gt;/g, '>').replace(/&amp;/g, '&')
if (entity=document.getElementById('post').value.match(/&(?:[\s;]|[^\s;]*(?:\s|\$))|<|>|'|"/)) alert('Warning: Encoded text may contain unencoded characters. (ie: ' + entity[0][0] + ')');
}
<label for="pre"><b>Unencoded:</b></label> <button onclick="encode()">Encode</button><br /><textarea id="pre" style="width:100%;min-height:49px;resize:vertical"></textarea><br /><br />
<label for="post"><b>Encoded:</b></label> <button onclick="decode()">Decode</button><br /><textarea id="post" style="width:100%;min-height:49px;resize:vertical"></textarea>`

The shortest functioning unencoded code block wins. Have fun!

• I would vote to close this as too broad, because as far as I can tell from the question, all the program has to do is not crash. It probably wouldn't be a good question even with a spec which required it to perform a stated task, though, because it's so easy to bypass the intent by using no-ops. – Peter Taylor Mar 27 '15 at 23:37
• @PeterTaylor That was the point of me including "You may use an expression in place of a statement up to one time (if your language supports it)," but I suppose that I can't assume that'll cover every case of no-ops in programming languages out there. – Pluto Mar 30 '15 at 19:40