# 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.

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]

# Voice recognition: "yes" or "no"?

Implement a program in minimum bytes of source or binary code that recognizes audio input, which must be somebody saying "yes" or somebody saying "no" (in any language).

Standard "no longer funny loopholes" apply.

Audio files can be supplied from stdin (as raw or compressed audio in any format), or read from file. Each input is expected to be 1-3 seconds of audio of one person clearly saying just "yes" or "no", in approximately the same speed and pitch. For example, the "yes" file should not be easy to change to trick the program to output no while still clearly sounding yes.

External libraries and builtins: only functions accepting constant-sized input (i.e. sin, pow) can be used, not FFT, for example.

Questions:

1. Should it be code-golf or popularity contest?
2. Should I provide test cases?
3. Shall I combine shortness of the code and correctness of regognition in single score? Or limit one of them?
• 1) Provide the audio files. If code golf, provide a large number of samples. 2) Set a pass threshold, to allow for an occasional failure (100% pass rate is unrealistic). 3) Drop the "no standard loopholes" tag line. I am so tired of seeing that on every single post. It's more of an eyesore than the loopholes themselves. /rantoff – Rainbolt Jun 30 '14 at 19:11
• Is it possible to both have 'yes' and 'no' may be said in any language and code-golf? I can't provide samples for all languages... – Vi. Jun 30 '14 at 19:33
• If you cannot provide samples for every language, then you should not be running a competition with every language. – Rainbolt Jun 30 '14 at 20:05
• What's better: 1. just stick to English, 2. Provide as many languages as I can and limit to them? – Vi. Jun 30 '14 at 20:29
• I would be biased if I said limit it to English. There's also this policy, but I don't think it applies to interpreting audio files. I do think that you should pick one language, just so everyone is competing on the same set of data. The language you choose is really up to you. – Rainbolt Jun 30 '14 at 20:54
• It's not clear to me whether you're after real voice recognition or just the ability to distinguish two files. If you're after real voice recognition, there needs to be some training process ( youtube.com/watch?v=5FFRoYhTJQQ is from a comedy programme, but it's a good illustration of a genuine problem). If you just want to distinguish two files, it's no challenge at all. – Peter Taylor Jun 30 '14 at 22:40
• @PeterTaylor, So two sets should be provided (learning and test), to avoid just hardcoding hashes? – Vi. Jul 1 '14 at 6:40
• I think it's also necessary to require that the program not hard-code any data at all, to prevent people pre-tuning it against the test data. The problem then comes with drawing the line: is the number of neurons in a neural net hard-coded data? Or the function used by the neuron? I think it's a good idea, but hard to fit into the PCCG model. – Peter Taylor Jul 3 '14 at 7:20
• @PeterTaylor, is the number of neurons in a neural net hard-coded data? -> "nothing up my sleeve" numbers? – Vi. Jul 3 '14 at 9:00
• I don't see the relevance. – Peter Taylor Jul 4 '14 at 11:15
• I've just written a Perl script that generates WAV files from text-to-speech calls with random parameters. It needs OS X to run, but I can generate the files for you if you like. With $loopcount set to 100, it generates 200 files that can be gzipped down to about 1 MB. – r3mainer Jul 5 '14 at 8:04 • @squeamishossifrage, I plan yo just record me saying "yes... no... yes... no... ..." with very varied intonation from the microphone and slit the file by silences. – Vi. Jul 6 '14 at 17:55 • @Vi. So much the better :-) – r3mainer Jul 6 '14 at 18:17 • Shall I keep both training and scoring sets public? – Vi. Jul 6 '14 at 23:26 • Would you mind deleting this one, now that the sandbox is merged and the challenge has been posted? – Martin Ender Sep 1 '14 at 10:03 # Finding Integer Linear Factors of Integer Polynomials You get a string containing a list of integers which represent the coefficients of an integer polynomial. E.g. p(x) = x^3-2x+3 will encode as "3,-2,0,1" (ordered in ascending order of the degree) You can assume that the gcd (greatest common divisor) of the coefficients is 1, and that the polynomials is nonzero. Your task is finding all roots p(x) = 0 where x is an integer. The output string will consist of two parts, separated with semicolon: • The first part contains a list of the integer roots in ascending order. (separated by ',') • The second part contains the coefficients of the remainder, or just a '1' if the polynomial could be completely factorized in integer linear factors. ## Examples • The polynomial x^4+2x^3-x-2 will encode as "-2,-1,0,2,1". It can be factorized as (x^2+x+1)(x-1)(x+2) so the output will be: "-2,1;1,1,1" • x^3-x+2 is irreducible will encode as "2,-1,0,1", output will be ";2,-1,0,1" • -2x^6-2x^5+7x^4+x^3-x^2+2x-6 is a product of two irreducible polynomials (x^2+x-3)(-2x^4+x^2+2), has therefore no integer roots and encodes as "-6,2,-1,1,7,-2,-2" output will be ";-6,2,-1,1,7,-2,-2" • x-1 will encode as "-1,1" and has the output "1;1" • 3 will encode as "3" and has the output ";3" ## I/O You only have to write a function, that takes the input string as argument and returns the output. If this is not available to your language, use an equivalent structure. (function, named block, or named verb) ## Goal The shortest (correct) solution (in bytes) wins. (codegolf) Please upvote special and elegant solutions! EDIT: More examples, assumptions, I/O • May we assume that the input coefficients are coprime? If not, what are the implications for the output? Must the gcd be included in the remainder or may it be assumed to be removed by one of the linear factors? – Peter Taylor Jul 7 '14 at 10:33 • Also, you describe the input and output formats; it would be good to say explicitly that the coefficients are ordered from constant coeff to leading coeff. What you don't describe is the I/O mechanism. Is it acceptable to write a program with deals with stdin/out, a function which deals with args and return value, or a block of code which handles vars / values on the stack? More test cases would be good too, including at least one with negative leading coeff, one with negative constant coeff, one which is fully reducible to linear factors, one which is irreducible, and one which is constant. – Peter Taylor Jul 7 '14 at 10:37 • @PeterTaylor Thank you for those points: Yes I think I should exclude the case that the factors are not coprime, (gcd of all factors (together) is 1). What do you think would be a good input/output mechanism? I think a function that accepts and returns the strings would be appropriate. Regarding the examples: Up to now I did not consider providing test cases, but of course I need to! I want to point out one tricky part of the task as it is now: A polynomial can be a product of two irreducible polynomials, so that the polynomial itself is not irreducible but also doesn't have linear factors. – flawr Jul 8 '14 at 6:18 • [continuing] Do you think that this is too difficult? I also thought about reducing the task to polynomials which have maximum one irreducible factor. I mean quite a bit of math is required in order to determine the irreducibility. A way simpler task would be the factorization of a polynomial that consists only of linear factors... – flawr Jul 8 '14 at 6:23 • True, you should have a test case for that too. But it's not necessary to restrict the task to polynomials which are a product of linear factors and one irreducible factor, because it's not necessary to test irreducibility. On the assumption that this is a code-golf, I would expect everyone to use the Cauchy bound on the real roots. – Peter Taylor Jul 8 '14 at 8:13 • A function which takes a string and returns a string is fine, although you might want to say "function, named block, or named verb" to cover some of the languages which are used a lot more on this site than in the real world. – Peter Taylor Jul 8 '14 at 8:18 • Well you do not have to use the bounds, since all the roots have to divide the constant term. – flawr Jul 8 '14 at 11:10 # Build a GenericScript Compiler Your task is to build part of a compiler for the new programming language GenericScript. In this challenge you are only required to check the input source code for syntax errors and not build a running program. Given the source code for a GenericScript program as input, parse the source code to check that it conforms to the syntax rules for the language. The syntax definition for GenericScript is below. If a part of the source code is found to be invalid, a message must be displayed informing the programmer that there is a mistake. Since the challenge is for syntax only, you are not required to check for correct usage of variables e.g. use of undeclared variable. Only the syntax rules specified need to be checked. A bonus will be given if the output message includes the line of code where the problem occurs. Win Criteria This is code golf. Shortest code wins. Implementing the line number bonus allows you to multiply you score by 0.8 e.g. only 80% of your code length will be counted as your score. Syntax "C" style whitespace rules apply i.e. multiple whitespace characters are treated the same as a single whitespace character & whitespace is only required in between tokens if it would otherwise cause syntax ambiguity. Program = Statement Statement = Assignment | If | Output | Sequence | While | StringDeclaration | BooleanDeclaration Assignment = Identifier "=" (String | Bool); StringDeclaration = "string" Identifier "=" String ";" BooleanDeclaration = "bool" Identifier "=" Bool ";" If = "if(" Bool ")" Statement ["else" Statement] While = "while(" Bool ")" Statement Output = "print(" String ");" Sequence = "{" [SequenceContent] "}" SequenceContent = Statement [SequenceContent] Identifier = {Any sequence of alphanumeric characters with at least 7 characters (all language keywords are shorter than this) } Bool = BoolConstant | OperatorAnd | OperatorOr | OperatorNot | StringEquals | BoolEquals | Identifier BoolConstant = "true" | "false" OperatorAnd = Bool "&&" Bool OperatorOr = Bool "||" Bool OperatorNot = "!" Bool StringEquals = String "==" String BoolEquals = Bool "==" Bool String = StringConstant | OperatorConcat | Input | Identifier StringConstant = "'"StringConstContent"'" StringConstContent = "\\" | "\'" | Character [StringConstContent] Character = {Any character except for "\" and "'"} OperatorConcat = String "&" String Input = "read()"  Test Input Valid Input: print('What is your name?') string myInput = read(); print('Hello ' & myInput);  Invalid Syntax: If(read() == 'DoTask1') print('Executing you'r command');  • Wow, that sounds like quite a task. A few issues I can think of: a) you should specify exactly how scoping works. b) your first bonus is a bit hard to nail down - how detailed does the error message have to be? And do the strings for those error messages (or any warnings) count towards the code size? Because then this may just devolve into people using ridiculous shorthand for notifications and claiming they are sufficient. c) Are you 100% sure your grammar is complete, correct and consistent? d) You provide a grammar but no definition of the semantics of the individual constructs. (continued) – Martin Ender Jun 21 '14 at 17:07 • Most of the symbols have an implied meaning, but there doesn't seem to be a specification what any individual literal, operator or function is supposed to do, so any compiler that checks the syntax could claim it compiled the program correctly based on some arbitrary spec. – Martin Ender Jun 21 '14 at 17:08 • Don't get me wrong, I quite like the idea, but it seems to be a bit too much of a mammoth project to work well on PPCG - the main problem being that this is very prone to little mistakes not being caught before the challenge goes on main and people start working on it... which just leads to frustration all around. – Martin Ender Jun 21 '14 at 17:09 • @m.buettner Thanks for your feedback. I have simplified the chalenge and simplified the syntax rules. – rdans Jun 22 '14 at 12:14 • Is it case-sensitive? If yes, then your syntax list contains some case-changes. – Kyle Kanos Jul 2 '14 at 2:41 # Survival of the fittest king-of-the-hill As Chris Jester-Young suggested here, i will propose my challenge here. At the moment, this is merely a draft but i want to ask for suggestions to this idea as early as possible. For discussions, i suggest using the chatroom at chat.stackexchange.com specifically for this challenge. My draft in its newest state plus all source code is hosted at github where you can make pull requests with suggestions. The post here consists of the rules my challenge will have. Look at the github to see a lengthy explanation of what i post here. Feedback of all kind is appreciated! # Rules Board The challenge is held on a two dimensional board with x and y coordinates. 0|0 is on the left-top side and increases in y downwards and in x to the right. Every field on the board can only hold one object. Objects are all kind of things in the game, from resources to units and even buildings. Board corners are solid, so the board is surrounded by walls. Everything on the board is randomly distributed. The board size is determined by the number of players in the game. Actions Every AI acts as one faction of humans. These factions have their explicit name and can be recognized by all other factions. Each round, all factions are given the complete board state and they have to submit some actions. Actions will be executed based on the time stamp of submission. So a faster calculating AI has the benefit of moving first. Animals and NPCs will move after all actions from the AIs are executed. Then there is a new round. Game limits The game ends, when there is only one faction left. There can be a time limit, if is turns out to take ages... There will also be a time limit for each round. Taking more time than the limit means, your program will be cut off and the rest of your actions will be omitted. After 5 consecutive rounds hitting the time limit, an AI will be disqualified. Gameplay Each faction starts the game with four workers and a stockpile. They have to collect wood, stone and food to survive. Food is used up every round to fill the workers stomach. All three resources will be needed to construct buildings and advance in technology and in numbers. Workers are able to reproduce in housings. but they can also be converted to soldiers. Soldiers can not work nor reproduce, but excel in their fighting ability. With more advanced technology, workers can be converted to better soldiers. Soldiers can not be upgraded. Strategy There are numerous buildings available and the more advanced cost a huge amount of resources. Fighters can destroy buildings, while workers can conquer them. Buildings allow for things like reproductions, boosts on resource collection and overall attributes of each unit. Units get more experienced in things, while they are doing them. This experience is handed down to the next generation. Since there need to be two units, to get an offspring, a genetic algorithm will mix their abilities together. This can be better or worse. Your units can have offspring with units from other factions, but both units have to agree on the matter. The offspring randomly chooses between the two factions and stays there. Control The AI does not control its units directly. It only gives orders. There is no limit on how many orders an AI can give each turn but every unit can only have one active order at a time. Giving a second order overrides the first one. Units try to execute the orders that are given to them. They are doing this automatically and orders are carried to the next round, if they are not fully completed. While the AI hat full informations over the board, their units have not. Giving an attack order to a place the unit can't see, the unit will try to walk there and attack when in view of the target. Alliances There is a global chat that all AIs share and where all AIs can talk to while calculating actions. AIs can specify other AIs that they think are friendly. They can not attack these. If two AIs each think of each other as friendly, they from a bond. A chain of such bonds is called an alliance. Even if you do not consider them friendly, your alliances friends are not attackable for you. So forming an alliance with someone, who friends everyone means, you cannot attack anyone, but they can attack you, if they don't friend back. Each round you can alter your friends to your liking. There is no such thing as an alliance chat, so you have to use encryption to chat in secret. And remember, in the end, only one AI wins the game. Scoring Scoring is done in number of rounds survived. Perhaps there will be some more scoring factors included to make the game more interesting. Please bear in mind, that i will edit this answer a lot the next time to reflect the changes in the challenge. • This is rather vague at the moment. What do you want feedback on? – Peter Taylor Jul 12 '14 at 17:10 • I wanted to propose the idea of a challenge like this here first. I am at the moment thinking about the rules of the challenge. Any 'Hey, xyz would be cool!' or 'what if abc?' helps me. It will get less vague soon! Until then, every meta-feedback on the challenge is appreciated. Just speak out your mind. – reggaemuffin Jul 12 '14 at 17:16 • @PeterTaylor I have now written an outline of the rules, this challenge will have. Can you look over it and tell me, if something is unclear? – reggaemuffin Jul 12 '14 at 19:43 • I suggest to add titles to each text-section you have. It is quite hard to read right now... – CommonGuy Jul 14 '14 at 12:04 • @Manu I have added some titles that seem to fit well. Do you have any other suggestions? – reggaemuffin Jul 14 '14 at 13:16 • @Kostronor much better :) As Peter Taylor said, everything is rather vague. Try to specify rules, such as the time limit, actions and so on... – CommonGuy Jul 14 '14 at 13:25 • @Manu My intention for this project is to make something a bit more complex, that has many distinct strategies to win. I am writing on the controller at the moment, which helps me specify the rules in a more detailed manner. Until then, can you give me some feedback on the overall gameplay? Do you think, this could be interesting? – reggaemuffin Jul 14 '14 at 13:35 • @Kostronor Sure it is interesting. I hope it doesn't get too complicated ;) – CommonGuy Jul 14 '14 at 13:39 • This sounds really interesting to me. However, especially due to the complexity, be prepared to get only a handful of submissions. So far the popular KotH's were popular because you could whip up a simple bot in a couple of minutes (which wouldn't have any chance of winning, but it's fun posting it anyway to get the ball rolling). If your game is sufficiently complex that even the most basic strategy takes half an hour and some debugging to implement, that will put a lot of people off (who might take this on them if there are already simpler submissions to be beaten). – Martin Ender Jul 15 '14 at 23:06 • Btw, I really like the idea of handling commands in the order they come in! :) – Martin Ender Jul 15 '14 at 23:06 • @m.buettner I thought, to lower the starting requirements, i will write some basic bots myself, where everyone can start. I think, the main focus should be on the strategy and not on the coding, so i will try and get some abstraction done, like the example bots from 'petri dish'. Yeah, the commands in order thing is something, that trades of better action against faster thinking. But it's a pain to implement it ;) – reggaemuffin Jul 16 '14 at 9:25 # Empire wars This is very close to Risk, but not quite. You command an empire, composed of armies, trying to take over the world. ### The world The world is a grid. For n competitors, the side length of the grid is sqrt(n)*4 (casted to an integer). At the beginning, the world is part of the "neutral" empire. Each neutral army contains 200 soldiers. The neutral army only defends, it never attacks. Your starting army of your empire is randomly selected from the grid. Note that the world wraps around if you go off the edge. ### Receiving soldiers Every turn, you will be given 500 + 50t soldiers to distribute, where t is the number of armies/territories you command. You can give any amount to any army, as long as you don't exceed 500 + 50t in total. You may then attack or transfer any number of soldiers to another location. That means that, if you have enough soldiers, you can move soldiers from multiple different territories to multiple new territories. ### Attack/Transfer During your turn, you may move any number of soldiers from any of your armies to any of the squares bordering your army. You can move diagonally. One of two things will happen 1. You already control the square your army is moving to: Nothing special. The new square gets some more soldiers. 2. Another empire controls the square: The two armies will fight (see below). If your army wins, the surviving soldiers will inhabit the territory. Otherwise, any surviving soldiers will retreat back. ### Battle The order of battle is randomized every turn, because the empires who go first have a slight advantage or disadvantage (depends on the algorithm). For example, if I occupy a territory on my turn, but I go before another empire, then that empire could potentially attack my new territory. Suppose a is the number of soldiers attacking and d is the number of soldiers defending. The defenders lose a * 0.6 soldiers and the attackers lose d * 0.7 soldiers. If the defenders have no soldiers remaining, the attacker's surviving soldiers inhabit the territory. For example, suppose the world looks like: N-200 N-200 N-200 N-200 N-200 N-200 N-200 N-200 N-200 N-200 A-500 N-200 N-200 N-200 N-200 N-200  where N-200 represents a neutral army with 200 soldiers and A-500 represents an army of your empire. Suppose the following happens: 1. Your empire (A) decides to move 250 people north. First of all, north is not controlled by your empire, so a battle is started. N-200 loses 250 * 0.6 soldiers and A-500 loses 200 * 0.7 soldiers, with a result of N-200 --> 50 and the 250 attacking soldiers will be reduced to 110. Since the territory wasn't conquered, the 110 survivors retreat. The world will now look like: N-200 N-200 N-200 N-200 N-200 N-200 N-50 N-200 N-200 N-200 A-360 N-200 N-200 N-200 N-200 N-200  2. You now decide to move 180 people north. The same thing happens: N-50 loses 108 soldiers and A-360 loses 35 soldiers. Since N-50 has been eliminated, the remaining 58 soldiers move into the new territory. N-200 N-200 N-200 N-200 N-200 N-200 A-58 N-200 N-200 N-200 A-180 N-200 N-200 N-200 N-200 N-200  Note that neutral territories never attack. ### Example implementation: The code should be in Java (thinking of extending it to other languages) and needs to extend the abstract class Empire. // The code MUST be in the package "empire" and extend the class "Empire" from mainengine package empire; import java.io.IOException; import java.util.List; import mainengine.*; public class TestEmpire1 extends Empire { // Occurs at the beginning of the turn // You get 500 + 50t soldiers to deploy @Override public void deploy(ArmyDeployer toDeploy) { // Get all of my armies List<Army> armies = getArmies(); // Distribute my new armies to each army evenly int perArmy = toDeploy.armiesLeft() / armies.size(); for (Army a : armies) { a.addPower(toDeploy, perArmy); } } // You can move your armies as well @Override public void move() throws IOException { // Get the world World world = World.world; // Get the map of the world // Note that you can only see the areas adjacent to your armies // All other locations appear as "null" Army[][] map = getMap(); for (Army a : getArmies()) { // Find the least guarded territory Move bestMove = null; int leastDefended = Integer.MAX_VALUE; for (Move move : Move.values()) { int newX = world.wrapPosition(move.getXOffset() + a.getPoint().x), newY = world.wrapPosition(move.getYOffset() + a.getPoint().y); if (map[newY][newX] != null && map[newY][newX].getStrength() <= leastDefended) { leastDefended = map[newY][newX].getStrength(); bestMove = move; } } // Attack with half of our strength a.move(bestMove, a.getStrength() / 2); } } }  See github for the code that will be executing it: https://github.com/prakol16/EmpireWars/tree/master/EmpireWars/src The "number of points" that an empire receives is how many territories it controls after one run (about 50, subject to change, or so turns). The program will be run 10 times and the empire with the most total points wins. In addition, the program creates an html file record.html which contains a record of every turn. • Sounds interesting! :) A few comments: 1. I don't think this is very close to Risk. I'd say "inspired by Risk" is as close as it gets, because I suspect the battle system to play out vastly differently (for instance, attackers are always at a disadvantage here). 2. Up until your example it's not clear that neutral territories are occupied by some army, and that this neutral empire starts with 200 soldiers on each cell. 3. Since this caused some confusion recently, I'd remove "the world is round" (and only mention that it wraps around), because it implies that the world is spherical... [ctd.] – Martin Ender Jul 15 '14 at 9:36 • in which case north/south wouldn't wrap around. A map which wraps on both edges is in fact in the shape of a torus, but mentioning that would probably confuse some other people, so I'd say only state that both edges wrap around and nothing else. 4. How many are "many rounds" (after which the game ends)? 5. You might want to think about providing a wrapper implementation of Empire which calls a separate process, in order to allow submissions in other languages. Like Rusher did here. 6. Can I attack and transfer... [ctd.] – Martin Ender Jul 15 '14 at 9:40 • units from multiple territories into multiple territories within a single round? Or do I have to stick to one transfer or one (repeated) attack? 7. I suppose the order of players will be randomised? I also expect a fair share of submissions to be probabilistic. In that case deciding the overall winner based on a single run might not be fair (unless the winner is always the same submission anyway). Are you prepared to run multiple simulations if that happens (such that the winner is submission that wins the largest number of individual simulations)? – Martin Ender Jul 15 '14 at 9:43 • @m.buettner Ok, updated some stuff. For #4, 7: I'm not sure how many yet, but it should be enough that luck doesn't affect the empire that much. For #6: Yes, you can send different commands to multiple armies in different locations. Just note that if you occupy a new territory, it won't be available for you to command until the next turn. #7. Yes, the order is randomized every turn, because if I occupy a territory, even though I can't command it immediately, another empire could still attack me immediateley. – soktinpk Jul 15 '14 at 14:47 • Alright, thanks for clarifying. I don't like the idea of sending your orders before everyone makes their turn. You'd have no idea what would happen to the territories you're attacking before you're actually invading there. 8. How many soldiers do I have to leave behind when attacking/transferring? – Martin Ender Jul 15 '14 at 14:55 • @m.buettner You could potentially leave none when attacking/transferring. That would leave the territory completely undefended though. As for sending your orders before everyone makes their turn: if it isn't done this way, then the people who go first have a huge disadvantage because they don't know anything about who's attacking the territory, while the ones who go last have lots of information. Your orders should be based on what's currently there (what happened in the previous turn) – soktinpk Jul 15 '14 at 15:21 • If you buffer the orders, those going at the end will have a huge disadvantage because they have no idea what the map will look like when their order is actually carried out, whether there's no uncertainty at all for those going first. I think this difference is much more unfair than the first player having to make a decision before everyone else. 9. Do you get your soldiers when it's your turn or does everyone get their soldiers at the same time once everyone's moves have been completed? – Martin Ender Jul 15 '14 at 15:32 • @m.buettner I see your point. I don't think I'll buffer the orders then (it makes more sense not to now that I think about it). 9. Everyone gets soldiers at the same time. – soktinpk Jul 15 '14 at 15:38 • You could look at the board game Diplomacy for some ideas about how to handle simultaneous resolution of everyone's orders. (I confess that I don't know offhand whether it's a good system, but I do know that it's a system). – Peter Taylor Jul 15 '14 at 16:42 # XKCD: (Battle of the) Hats http://imgs.xkcd.com/comics/hats.png Enough background, get into the game A challenge. You all started at a point. At the count on 3, you decides to wear yourself 1 black hat, 2 black hats or 1 white hat. Here's what happened: (If you find this description confusing, you can look at the table below, credit to Peter Taylor) If you use 1 black hat -> -> If your opponent also uses 1 black hat or white hat, your opponent moves backward 1 step. -> If your opponent uses 2 black hats, you have 50% chance making your opponent moves 2 steps backward. Else your opponent does nothing. If you use 2 black hats -> -> If your opponent doesn't use white hat, your move is considered successful 2 black hats attempt. Your opponent moves backward x+3 steps, where x is # of your previous successful 2 black hats attempt. -> Else: Your attack gives no effect. If you use white hat -> -> If your opponent use 2 black hat, you're considered making successful white hat attempt. Your opponent moves backward y+3 steps, where y is # of your previous successful white hat attempt. -> Else: You're considered making a failed white hat attempt. You move backward z+3 steps, where z is # of your previous failed white hat attempt. The game ends when somebody moves 20 step backward or 10 rounds played. If one person moves 20 or more steps backward while one doesn't, then the one who not is declared the winner. If both moves 20 or more steps backward in the same round or no one moves 20 or more steps backward in 10 rounds, no one win. Your bot will play 5 tournaments. In each tournament, you face each enemy once. The player who score most win in those 5 tournaments accumulated, is declared the champion ## Communication Protocol Your bot will get this from STDIN: id round step0 step1 move0 move 1  Where id is your player id, can be 0 or 1; round means current round (match starts at Round 1); step0 and step1 means how many step has player 0 and player 1 has taken; move0 and move1 is the move taken by player 0 and player 1. In first round, move 0 and move 1 will be empty. In next round, it will the move as this 12w21  This means one player use 1 black hat; 2 black hats; white hat; 2 black hats; 1 black hat, respectively. Your bot gives me output from your STDOUT as 1 if your bot want to wear 1 black hat, 2 if your bot want to wear 2 black hats, w if your bot want to wear white hat. PS: Do aware that I use small-case "w" Table:  +--------------------+--------------------+---------------------+ | | P0 action | | | 1 | 2 | w | +---------------+--------------------+--------------------+---------------------+ | 1 | P0 back 1 | P0 back 0 or 2 | P0 back z0+4; z0++ | | | P1 back 1 | P1 back x0+3; x0++ | . | +---------------+--------------------+--------------------+---------------------+ | P1 action 2 | P0 back x1+3; x1++ | P0 back x1+3; x1++ | . | | | P1 back 0 or 2 | P1 back x0+3; x0++ | P1 back y0+3; y0++ | +---------------+--------------------+--------------------+---------------------+ | w | . | P0 back y1+3; y1++ | P0 back z0+3; z0++ | | | P1 back z1+4; z1++ | . | P1 back z1+3; z1++ | +---------------+--------------------+--------------------+---------------------+  • 1. The scoring table would almost certainly be easier to read in a table. 2. Could you be more precise in the definition of x, y, z? Whose previous moves are counted, and what counts as "successful"? 3. In the "You move z+3 steps", is that forwards or backwards? 4. Is it intended that the bots should not know what x, y, z are? 5. It makes more sense for the controller (of which there is one) to handle the naming issue and let each bot (maybe a dozen) handle the simple case of always being player 0. – Peter Taylor Aug 22 '14 at 11:28 • You can figure x y z from history move. For the scoring table, I cant figure out how to make this without using image (trying to make this as html as possible), I shall rewrite the 2 black hats and white hats. – Realdeo Aug 22 '14 at 11:36 • I agree that a table that is not an image would be better, but until you find a way to make that work, please could you include an image of a table? – trichoplax Aug 22 '14 at 11:47 • The table won't fit or render correctly in a comment, so I've added it to the answer. – Peter Taylor Aug 22 '14 at 11:58 • Thank you. I have credited you. – Realdeo Aug 22 '14 at 12:04 # Making a dichotomous key A dichotomous key, also known as a single-access key is often used to identify plants/animals. Your task is, given a set of data, write the shortest program that outputs the shortest (in steps) possible dichotomous key. If there are multiple solutions, the program may print either one. Input Input will be received by stdin, or in cases where that doesn't exist (e.g. Client-side javascript) you can take input from prompt or something similar. The input will be a list of items followed by characteristics: The format of the definition of an item will be item[delimiter1]characteristic1[delimiter2]characteristic2[delimiter2]characteristic3  Your program may choose the delimiters. In this example, I will use : as delimiter one, and , as delimeter 2. Between each item definition is delimiter3, which will be \n in this example (but you can make it anything that isn't delimiter1 or delimiter2). Note that none of the delimeters can be [a-zA-Z] letters. Characteristics and items are composed of a series of [a-zA-Z] characters. Example input: quadrilateral:fourSides trapezoid:fourSides,onePairParallel parallelogram:fourSides,twoPairsParallel,oppositeSidesEqual rectangle:fourSides,twoPairsParallel,fourRightAngles,oppositeSidesEqual rhombus:fourSides,twoPairsParallel,oppositeSidesEqual,allSidesEqual square:fourSides,twoPairsParallel,oppositeSidesEqual,allSidesEqual,fourRightAngles  Output Output should be written to stdout, or alert or something similar where it doesn't exist. You must output a characteristic followed by delimiter one, followed by two integers separated by delimiter two. The first is the step to go to if the item contains the characteristic, and the second is the step to go to if the item doesn't contain the characteristic. Note that the 1st step is considered 0. Alternatively, instead of an integer, you could have an item. Example output: twoPairsParallel:2,1 onePairParallel:trapezoid,quadrilateral allSidesEqual:3,4 fourRightAngles:square,rhombus fourRightAngles:rectangle,parallelogram  This is code-golf so shortest code wins. • The example output looks wrong to me. Shouldn't the first line be twoPairsParallel:2,1? Also, since the transformation doesn't inherently use any biology at all and since you use shapes, it would be clearer to talk in terms of "classes" or "taxons" rather than "organisms". It's also good to be explicit about I/O assumptions; since you talk about a program and string delimiters between items in a list, I would guess that you want a full program which takes input from stdin and writes output to stdout. State that. – Peter Taylor Aug 22 '14 at 8:36 This is nearly done now, just need someone to double check that everything makes sense # Generate Lightning Forks in a 3D Grid # Objective: Overview: Write a program, that given the two inputs number of rays and ray length, will produce a procedurally random array of connected points, containing the ray number, number in sequence and coordinates of each point. Details: The lightning is in the form of rays, which are determined by points stored as coordinates in a grid. The initial point (0,0,0), is the cloud, where the lightning is first generated. The first ray starts here and travels out in a random direction, and will continue moving in random directions (each point has an equal chance of any direction, not influenced by the previous point), and will terminate once it reaches the ray length limit or cannot go any further (if it fails enough new direction retries when intersecting with another point). This will leave a single path between the origin and the end point. However, lighting doesn't stay as one single ray and will fork, so while all other rays should be generated in a similar way, their origin should be randomly chosen from any of the already generated points, and the sequence then continues from this point. The Ray Number is simply which ray iteration the code is on. Each ray is it's own individual path. The origin point of the ray will have the same coordinates as the point it branches off from. The Number In Sequence is how many points away from the cloud (or how far into the generation) it is. If lightning forks at point 50, both separate paths will start at 51. While this is not currently used for anything aside from checking the code is working correctly, it would allow for future improvements such as animation (see gif at bottom for an example). Coordinates are the 3D points the ray passes through. They should be stored as integers. Simple 2D Diagram: Here is an example output during generation after 24 points have been calculated. The numbers written in black are the numbers in sequence, and as you can see when the 2nd ray (blue) branches out, it continues from 10. The red line is an example of when it would try intersect with existing points and get stuck. This shows the cloud as it's own ray, you are free however to do this differently. # Rules: • Can be written in any code (without extra plugins), although I can't guarantee anything but PHP and Python will be tested, unless someone else with access to a lot more languages helps out. • Randomness must be seed based, so if you were to define a seed (not needed), it would produce the same result. • A point can move in any one of the 3 dimensions - meaning it can go up, down, left, right, forwards, or backwards (x,y,z,-x,-y,-z) from the previous point, but not diagonally. • No two points can have the same coordinates. • The one exception of this rule is that each ray must start with the same coordinate of where it branches out (for the purpose of connecting everything together). • If an intersection is detected, at least 3 retries must be done to find new direction, then it may be terminated. The retries must be for each point, so having 1 retry on 3 different points shouldn't terminate the ray. • No multithreading allowed. • The code should output the final number of points generated and time taken. • The program should be timed to when the array of points is complete. Anything after this (such as for the bonus points) is fine and won't impact on the execution time. # Scoring: • Generate 100 rays with a maximum length of 200. If your code is super efficient and you want to show off, you're welcome to post the times for more complex results. • Most efficient code wins, based on the execution time. Someone will test multiple submissions and take an average from at least 4 generations to make it more fair. Important: So I can easily check your code works as it should, I wrote something that will display the rays in a 3D program. You'll need to generate 30 rays with a length of 15, in 2D (easy to switch - where it randomly chooses from from 6 directions, change this to 4), and copy it to pastebin. Format it like I have done here, and keep it limited to square brackets, commas, and integers: http://pastebin.com/8XHtv4is Bonus Points: • Given any two random points, there is one and only path between them both. If you can code something that would be able to calculate a path between these two random points and store it in a new array with the same structure, you get 15% off the execution time. • Instead of limited to 3 dimensions, code it for n dimensions, as more than 3 dimensions should work, despite being a little hard to visualise. If you manage you can knock 10% from the execution time. • As not everyone will be able to do it, this is only worth 5%, but you get it, if you code a way to visually draw the rays (2D is allowed, any method is allowed, but it must be able to run at the end of the code, as opposed to copying the list into a graphing program). # Tips: • Start working with a 2D grid for easier debugging. • Use small ray length and ray amount values until properly optimised. • While intersections are fairly easy to see, diagonals are not, running the code with a single short ray to print the output can be useful. # Example code: Generation Time for 100x200: 75-85 seconds length=15 forks=30 import time import random as rd startTime=time.time() def getDirection(num): if(num==1): direction=[1,0,0] if(num==2): direction=[-1,0,0] if(num==3): direction=[0,1,0] if(num==4): direction=[0,-1,0] if(num==5): direction=[0,0,1] if(num==6): direction=[0,0,-1] return direction listOfPoints = [[0,[0,0,0],0]] for i in range(forks): randomPoint = listOfPoints[rd.randint(0,len(listOfPoints)-1)] start = randomPoint[0] newLocation = randomPoint[1] listOfPoints.append([randomPoint[0],randomPoint[1],i+1]) j=0 j2=0 while j in range(length): j+=1 oldLocation = newLocation k = 0 while True: invalid = 0 newDirection = getDirection(rd.randint(1,6)) newLocation = [oldLocation[0]+newDirection[0],oldLocation[1]+newDirection[1],oldLocation[2]+newDirection[2]] for n in range(len(listOfPoints)): location = listOfPoints[n][1] if location==newLocation: invalid = 1 newLocation = oldLocation if invalid==0 or k>4: break k+=1 if invalid == 0: listOfPoints.append([j2+start+1,newLocation,i+1]) j2+=1 print "Time: "+str(round(time.time()-startTime,2))+" seconds" print "Generated/Maximum points: "+str(len(listOfPoints))+"/"+str(length*forks)+"("+str(round(len(listOfPoints)/float(length*forks),3))+"%)"  # Visualised Output: (From a more advanced version I did before, I was aiming to make a flower) • You seem to be using the word "fork" to mean two different things: a single line of points, and a bifurcation where one line becomes two. Perhaps you could use "ray" for the first, since it's conceptualised as a lightning simulator. You also seem to use "point" to mean "point in an integer lattice", but I don't think you actually state anywhere that you're working solely in integers. – Peter Taylor Aug 20 '14 at 20:26 • Is the cloud at the origin (0,0,0)? Does the first ray travel in a random direction, or always in the same direction? When the first bifurcation is created by picking a random point on the first ray, does the second ray travel in a random direction or always in the same direction? If in a random direction, what happens if the direction selected is parallel with the first ray? – Peter Taylor Aug 20 '14 at 20:26 • The explanation of bifurcation says that "However, lightning doesn't stay as one straight line, so for the second fork..." This strongly implies that each ray is a straight line. But the 2D diagram shows rays changing direction a lot. What is the correct generation process for a single ray? For the "cannot go any further" termination process to kick in, does it have to be unable to go in any direction at all, or just to pick a random direction which is blocked? (This is partially explained further down in the rules, but it would be convenient to group the explanation in one place). – Peter Taylor Aug 20 '14 at 20:28 • What is the point of the unique ID? Each tuple would already appear to have at least one primary key: the (fork number, number in sequence) pair. The later rules seem to make it clear that the coordinates are also a primary key. Separately, what are the parameters of the simple 2D diagram? In particular, what is the fork length? The red line seems to imply a lower bound of 13, but the blue line isn't that long. – Peter Taylor Aug 20 '14 at 20:28 • You can pretty much guarantee that someone will be able to test most obscure languages posted here. See also this meta thread. Up, down, left, right, forwards, and backwards are 6 directions, not 6 dimensions. It sounds like you actually want 3 dimensions. There's no point posting obfuscated example code. In general, it's better to post a reference implementation as an answer to avoid clutter. The 2D visualised output is unhelpful. I would remove it to avoid confusing people. The hand-drawn 2D image is a lot more useful. – Peter Taylor Aug 20 '14 at 20:29 • The bottleneck for many implementations could well be the I/O, so you should explain how you will take that into account when measuring performance. On the bonuses: Calculating the path between two items in a tree should be pretty simple: you track back from both until you find a common ancestor. But even though it's simple, you don't say how much of a bonus it gives. The other bonus confuses matters slightly when it says that it "should technically work for infinite dimensions": actually, it can't, because there's no fair probability distribution over an infinite set. – Peter Taylor Aug 20 '14 at 20:30 • Thanks for the comments, I'll reword the question and set it to generating lightning forks, gives it a better title. As to the potential infinite dimensions, how would you reword it? I could manually code in 100 dimensions if I wanted to spend 20 minutes doing it, I'm just suggesting someone codes the option where it'll do it automatically. – Peter Aug 21 '14 at 0:15 • Oh also, as to the bottleneck you mentioned, that's the main efficiency problem, I'm curious if anyone can find a method that doesn't involve reading the entire list every time a new point is added – Peter Aug 21 '14 at 0:42 • Hey, just updated it again, do things make a lot more sense now? – Peter Aug 22 '14 at 20:53 # Confused Automatons king-of-the-hill ## [work in progress] This is a 1v1 (or not? could be more) king-of-the-hill, where you and your opponent both issue commands to the same, perpetually confused, gladiators and try to survive. Toroidal arena with N gladiators. They understand the following simple commands: • Move one of 8 directions or • Hold plus one of: • Shoot target. Range of 5. Can’t shoot the following turn. • Dodge (no target required) • Nothing On each turn you may issue one command ([M/H]+[S/D/N]) to each gladiator. All gladiators will execute the commands from both players each turn. Movement happens first. If a gladiator is given two shoot commands, they will shoot twice that turn; two dodge commands and they will dodge twice. One dodge will avoid one shot. A gladiator can't shoot himself. Movement in opposite directions will cancel; movement in the same direction means moving a distance of two. If there is both an [H] command and an [M] command for the same gladiator, the [H] will be ignored. One of the gladiators is your commander. You lose when your commander dies. Your commander ignores commands from your opponent. You don’t know which gladiator is your opponent’s commander. ## Input TBD ## Output TBD ## Scoring TBD • I am just as confused as the automoton. Won't you easily be able to figure out which gladiator is the commander by seeing who ingored the command? – Rohan Jhunjhunwala Jul 16 '16 at 1:18 ## Unicode Case Mapping code-golf ### Challenge: Given a string as input, print it in both lowercase and uppercase. The string will be valid UTF-8, and your output should be as well. Characters without lowercase or uppercase mappings should be printed unmodified. Invalid, un-assigned, and private-use characters need not be handled. Uppercasing and lowercasing should be doing according to Unicode 7.0 "simple" case mapping rules. ### Rules: This is code-golf, shortest program wins. Your program shouldn't use any external data files or access anything from the internet; all of the information it needs should be contained within the code itself. You may not use your language's built-in case-mapping functions, built-in copies of the Unicode Character Databse, or libraries such as ICU. For example, in Perl the lc and uc functions as well as Unicode::UCD are prohibited. Since this challenge is about Unicode I will throw in a small scoring twist: if your program is valid Unicode text (in whatever encoding your language prefers, probably UTF-8) you may score it at a rate of one point per character (regardless of how many bytes those characters take up). If it contains binary data then it must be scored at one point per byte. I will clarify what constitutes "binary data" if I have to. ### Bonus: Support "full" Unicode case mapping. The difference between "full" and "simple" mapping is that in "simple" mapping every codepoint maps to a single codepoint, while in full mapping a codepoint may map to multiple codepoints. For example, the uppercase of the character "ﬀ" (U+FB00) is "FF" (U+0046 U+0046). Assume that all "conditions" are false (that is, any rule with a non-empty condition_list should be ignored). Question: offer a point bonus for this? Recognize a separate winner among people that manage it? Drop it entirely? ### Resources: • Created at the suggestion of @guifa after this challenge. – hobbs Sep 1 '14 at 6:05 • Interesting and to the best of my memory not a dupe. It's going to need a good set of test cases, and they may need to be provided in base64 or hexdump format. – Peter Taylor Sep 1 '14 at 17:25 • @PeterTaylor I have no problem supplying those :) – hobbs Sep 1 '14 at 17:40 • Do empty characters like '󠀠' count towards the score? – Vi. Sep 6 '14 at 12:06 ## King of the server - virus wars • There is a virtual machine with Linux running various services (SSH server, Apache (with SSL), FTP server, rsync server, etc); • There is tool which checks that the server is running (periodically accessing all its services - trying to view the page from Apache, download a file from FTP server, etc.) and analysing responses for special ID codes; • There are submissions that are started on the server as root and should "inject" some ID code (individual per solution) in as much as possible places while inhibiting competitors; • Each solution should try to attain the following goals: • Make the server and it's services mention the ID code in maximum number of places with maximum reliability; • Avoid stopping the server or breaking any of the services, avoid breaking reboots; • Inhibiting competiting solutions (if any) while allowing them to post their ID code at least once; The virtual machine gets booted, the solutions gets started there, then the script accesses the server from virtual network to check SSH/FTP/HTTP/... still running. The script also looks at the reply and counts any ID codes that appears in the replies. It happens multiple times. The serve gets rebooted N times. Not all solutions gets planted on the server each time, just some random subset. A solutions scheduled for the given round receive negative penalty points if: 1. The server crashed (stopped replying on requests from the virtual network); 2. Some service on the server crashed (i.e. SSH still works, but HTTP is down); 3. A competing solution have failed to provide it's ID code even once; If your solution crashes something or fails to provice the code even once even if run alone (without competitors) - it gets disqualified. The solutions may use variety of methods to complete the goals: 1. Just changing configuration in /etc; 2. Patching system libraries to inject the ID code and/or supress other solutions; 3. Carrying "clean" copy of libraries to avoid point "2."; 4. Loading kernel modules; 5. Extracting competing ID code and manually providing it exactly once (to avoid the "spawn camping" early-kill penalty); 6. Loading security modules to make root less omnipotent; 7. Overriding a boot loader, making the server boot nonstandardly... The virtual machine image will be available from the beginning. Questions: 1. Is the idea worth thinking and fits PPCG enough? 2. Shall all solutions be public from the beginning, or there can be hidden solutions (to prevent easy directed attacks)? 3. Shall binary-only submissions be allowed? • I'm not especially comfortable with this as a concept: it risks crossing the line into writing actual malware. But if you do go ahead with it, it has some other problems which need fixing. Most pressingly, unless the subsets run are fair, it penalises people for ending up in the same run as a bad bot. And that's without taking into account "If your solution crashes something... it gets disqualified". How are you going to attribute the blame when a combination of changes from different bots breaks things? As for binary-only submissions: you'd be foolhardy to run them. – Peter Taylor Sep 1 '14 at 14:12 • As for binary-only submissions: you'd be foolhardy to run them. -> What's the problem? They are expected to be run in a fortified secured environment. Binary-only (or source + binary modified by hand) can be useful to dodge other bots. – Vi. Sep 1 '14 at 14:39 • How are you going to attribute the blame when a combination of changes from different bots breaks things -> The offending bot will get the most penalty (as it probably breaks something every time), and others only sporadically. Subset choice is random. – Vi. Sep 1 '14 at 14:40 • crossing the line into writing actual malware -> 1. It is inspired by how malware works; 2. Finding vulnerabilities is not a priority, as all solutions start as root from the beginning; 3. I haven't seen any anti-malware clauses in FAQ; 4. Bots do "distribute" only by mentioning some hash, not the actual code, client programs (FTP client, browser, etc) are out of scope. – Vi. Sep 1 '14 at 14:45 • Your points 1, 2 and 4 are relevant, but for point 3 I would point out that the FAQs and guidelines of PPCG and SE in general are not the only factors people base their votes on. Even if a question doesn't technically break any rules, it can be downvoted for being unethical, according to the various ethical positions of the voters. Hopefully enough people will share their ethical views here in the sandbox that you can stay the right side of their various lines. – trichoplax Sep 1 '14 at 16:30 • You also need to bear in mind that just because you take steps to make sure a question doesn't result in usable malware doesn't stop the question giving the impression of being about creating malware. Just that potential impression is enough to make some people wary of allowing the question on the site - understandably as it may affect the perception of the site as a whole. Your question has the potential for a very interesting contest but you will have more work to do with this question than your average question due to having to tread carefully. – trichoplax Sep 1 '14 at 16:37 • If you're asking for code which looks like malware, are you 100% certain that you (and everyone else who might want to test it) can tell it apart from real malware? If it's non-obfuscated source you can probably be moderately confident, but if you're allowing binary submissions then I stand by the word foolhardy. As to "the offending bot will get the most penalty", you haven't understood that question. I could rephrase it as "How do you decide which one is the offending bot?" – Peter Taylor Sep 1 '14 at 17:21 • @PeterTaylor, The system should not peep into what actually happens on the server and can only observe crashed vs not crashed. Therefore the only viable option for penalties is to penalize everything, but let the statistics route the most of penalty points to the actual offender. Crashing services is not absolutely prohibited, it just attracts penalty points. But you can't use this tool against somebody else bot, unless it's many on one. The penalty points vs crash probability can be non-linear. – Vi. Sep 1 '14 at 17:29 • @PeterTaylor is right about the binary submissions. Reasonably readable code, though, would make this fun. </2cents> – Soham Chowdhury Sep 16 '14 at 10:17 # Dots and Boxes The goal is writing a function in [language], that accepts the grid and outputs what dots it wants to connect next. This is a King of the Hill challenge. ## How the game works The (square) field has 6x6 dots. The two players are conenct one after another each time two neighbour dots (vertically or horizontally). If one player closed a square (1x1) in his last step, this square counts as his. The game is finished as soon there are no more dots to connect. ## Scoring Each program will be playing against each other program. The score is the total number of conquered number of boxes. ## Open Questions • How can we encode the grid in an easy way as 2D(?) array? • How should the function endcode which dots to connect? • What language / environment would you suggest for doing so? (It would be easiest if there was only one language. I'd say Python or JavaScript.) • Is it better to count the total of the captured squares or only the number of won matches? • relevant – Martin Ender Sep 9 '14 at 12:42 • What do you mean by "quadratic"? I think this is a great idea however if you write some nice controller code. The easiest thing is to get the answers to read and write standard input/output I think that way answers can be in any language people want. Your code should verify they make a valid move however and just call the answer code with the new setup. – user9206 Sep 9 '14 at 12:51 • I mean 'square' sorry=) Since I am not THAT good at programming I thougth it would be best doing it in just one (popular and easy to use) language, so I could just copy/paste the code. The requirements for the controller code are: validation of moves, keeping track of the scores (and running all the games) something missing? What do you think about the other Question Another idea I just had was letting ALL the bots play together on one huge arena. – flawr Sep 9 '14 at 13:51 • Here's a suggestion: Squares (or Dots and Boxes as you call it) in four dimensional space. The winner is the person with the most whole tesseracts. – Beta Decay Sep 10 '14 at 9:45 • Ew. I do not think that I can wrap my head around that=) (I am not even sure whether the game would really work this way) but thanks for the input! Do you have an idea how to encode it in a 2d array? – flawr Sep 10 '14 at 9:49 • This question needs a volunteer to rewrite it I think. It's a great idea but needs some effort from someone generous with their time. – user9206 Sep 10 '14 at 10:37 • What would you change / why would you rewrite it? – flawr Sep 10 '14 at 11:25 • It needs a controller that calls people's code. Their code should take either a move or position as input and return a move. The controller should check this is valid and pass it to the other competitor. This allows people to write their answers in any language they like, – user9206 Sep 10 '14 at 11:58 • Of course but thats on the one hand what we've already discussed. And it makes no sence programming it as long as it is still unsure wheter it will make it out of the sandbox at all. – flawr Sep 10 '14 at 12:17 • I think it won't make it out without a controller. Maybe someone will be kind enough to write one for you. – user9206 Sep 10 '14 at 12:21 • You could have a 2d array of x by y with each element representing the lines between each dot. You could then have populate the array with N as unowned and then have A if the line has been drawn by player A and B if a line has been drawn by player B. Then, you have another x by y 2d array with ownership of each box. – Beta Decay Sep 10 '14 at 14:00 • You could store the grid as a 2D array of the top-left corners. Each point has two lines that go right and down. For the bottom and right sides of the map, there is only one line (unless you want to make a toroidal map) – Justin Sep 11 '14 at 23:19 • @Quincunx thanks, thats a good idea! – flawr Sep 12 '14 at 9:08 • @flawr That's what I did to build my own dots and boxes controller for a KotH that I'm no longer going to host (I don't have time anymore) – Justin Sep 12 '14 at 13:37 # Chad 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 [COMPLETE. Currently proofreading. Waiting for upvotes / objections before posting.] 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 # Play Your Cards Right ## 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. # Reading sheet music 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: http://www.wikihow.com/Read-Music http://readsheetmusic.info/readingmusic.shtml Submitted answers must have: • 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. # Your Program 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 # Traders for life 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.

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

# 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