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

# Be Rational! Finding Rational Roots of Polynomials

In this challenge you are to find all rational zeroes of a polynomial. The results have to be exact. I would suggest using The Rational Root Theorem.

## Input

Input can be through function argument, command argument, or user input. Input will be a polynomial. The polynomial may have rational coefficients. If a term has a coefficient of zero, that term will not be included in the input. x^1 will be abbreviated as x.

Examples:

-x^7+4x^4/7-21x^2/2+5x+23/19
...//More to be added when posted


## Output

Output will be a list of the rational roots of the input polynomial. Output can be through function return value or stdout. If output in string format, you will use improper fractions separated by commas. The output must be simplified as much as possible. Duplicate roots should not be printed more than once.

Examples:

4/5,2/3,-15/2
...//More to be added when posted.


## Example Cases

> x^2-1
1,-1
...//More to be added when posted.


Just like all questions, the answer with the lowest byte count wins.

## Questions:

Is this too much like Peter's earlier question?
Are there any points I haven't covered or are not clear?
Any grammar/spelling mistakes?
Any tips on improved formatting?

• Somewhat related question – Sp3000 Aug 17 '15 at 2:01
• The title is one character shy of the minimum title length and "abbreviate" should be "abbreviated." Can the roots be listed in any order? Do they have to be fully reduced or could we, for example, use 2/4 in place of 1/2? I would also suggest rewording "fractional coefficients" to "rational coefficients." – Alex A. Aug 17 '15 at 2:38

# Rec(ursion)less execution

We have a simple (non-Turing complete) language.

Each line of program is a set of terms separated by single space. Some of terms (ending with ()) are function calls. Some lines (whose first term ends with :) are function definitions. The lines that are not function definitions are called expressions.

This is a sample program:

funa: one two three
funb: funa() four oclock rock
here we go funb()


Here we have two function definition lines and one expression line.

And this is BNF for this language just for clarity:

literal ::= [any printable char other than ' ', ':', '(', ')']+
function_call ::= literal '()'
term ::= literal | function_call
expression ::= term | expression_list ' ' term

program_line ::= function_definition | expression
program ::= [program_line '\n']+


The task is to write a program or function that validates the program P and performs EXECUTE(P) if the program adheres to validation rules.

Validation rules:

1. EXECUTE(P) eventually stops (it's not Turing complete - enough to check if one of the called functions would eventually cause itself to be called - either being recursive itself or "mutually recursive" with other function it calls),

2. while calling EXECUTE(P) -> EXECUTE_LINE(P,L), each function definition search succeedes (in other words - the program will not try to call undefined function).

If program does not pass validation rule 1 or 2, ERROR: RECURSIVE FUNCTION or ERROR: UNRECOGNIZED FUNCTION should be printed respectively.

When both rules seem to be violated, assume that search for undefined function causes the algorithm to fail (stop) instantly, so recursion that would occur later if the function was found, is not reported. We only report ERROR: UNRECOGNIZED FUNCTION in this case (see Example 5 below).

In similar way, if recursion prevents a call to function that would not be found otherwise, even though the function containing call to unrecognized function is called only ERROR: RECURSIVE FUNCTION is reported (see Example 4 below).

If validation does not report any of those two errors, EXECUTE(p) should be called.

Executing a program is defined like this:

EXECUTE(P)
- for each line L in the program P:
- if L is not a function definition EXECUTE_LINE(P,L)

EXECUTE_LINE(P,L)
- for each term T in L:
- if T is a literal
print T followed by single space
else
FH = T without '()' + ':'
FDL = find in P a line starting with term FH
FD = all terms of FDL after FH
EXECUTE_LINE(FD)



Example 1:

a: b()
b: a()
c: cucumber
other: nofun()
d: apple banana and c()
we have d()


Output:

we have apple banana and cucumber


Note, that in spite of existence of mutually recursive function definitions a and b and function definition other calling undefined function nofun error was not raised, because execution never goes to any to this functions.

Example 2:

other: nofun()
c: apple banana and cucumber
we have other()


Output:

ERROR: UNRECOGNIZED FUNCTION


Example 3:

a: b()
b: a()
c: apple banana and cucumber
we have b()


Output:

ERROR: RECURSIVE FUNCTION


Example 4:

a(): a() nofun()
hello a()


Output:

ERROR: RECURSIVE FUNCTION


We don't output ERROR: UNRECOGNIZED FUNCTION, because the program would never try to execute nofun, recurring infinitely into first term of definition of a.

Example 5.

a(): nofun() a()
hello a()


Output:

ERROR: UNRECOGNIZED FUNCTION


We don't output ERROR: RECURSIVE FUNCTION here, because the program would fail to find definition for nofun before even tring to recurse into a.

Accepted solution: a function or a program that takes a program in the above-defined language, validates and runs it. You can assume that program has already been split into single lines, however you can use raw input or accept program as single string when convenient.

This is code-golf, so the shortest submission in term of bytes will win. However, all working submissions in all languages will be appreciated.

• The two rules seem to be inconsistent: the first one prohibits the recursive function f: f() even if f isn't called; and the second prohibits the function which calls an undefined function f: fail(), but only if f is called. It would be less confusing to make them both syntactic (based on the text of P) or both semantic (based on the execution of P). – Peter Taylor Aug 22 '15 at 7:35
• @PeterTaylor I didn't mean to prohibit existence of recursive functions that are not called, this was my description that was not precise enough. I clarified the description and added some more examples. So now, both rules are based on execution of P rather than text of P. – pawel.boczarski Aug 22 '15 at 8:57

(anything in italic parenthesis is a note for the sandbox)

Triple Triad is a card game from the Final Fantasy series. I've never played a FF game that included it, though, so I'm only familiar with the version in the Pokémon fangame Pokémon Insurgence. It may or may not be different than the original version, so apologies in advance if this isn't quite what you're expecting. :)

In Triple Triad, each card has 4 numerical stats that range from 1 to 10*: An "up" value, a "left" value, a "right" value, and a "down" value. Here's an example of a card with an "up" value of 1, a "left" value of 6, a "right" value of 3 and a "down" value of 2:

At the beginning of each game, players construct a "deck" of five cards, chosen from their entire collection. These cards are kept secret from the other player.

Triple Triad is played on a 3x3 grid. Players take turns choosing a card from their deck and placing it on an empty square of the grid. The goal of the game is to control the majority of the cards when the grid is filled. When the game is complete, one card is randomly selected from the loser's deck and given to the winner.

### Control

When a card is placed on the grid, it is controlled by its owner. In order to come out of the game victorious, you must gain control of cards that the opponent played.

To gain control of an opponent's card, you must place a card of your own that "beats" it adjacent (not including diagonals) to the card you want to take control of. Whether or not your card beats the opponent's depends on their stats and which side you place your card on.

Imagine this board as the current game state and the blue card as a card in my deck:

If I want to take control of the opponent's Numel, I have to place my Mareep adjacent to it. This leaves only two options: The top middle square or the middle right square. If I were to place it on the top middle square, my card would be to the left of the opponent's. As a result, Mareep's "right" value of 2 would be contested against Numel's "left" value of 4. 2 is not greater than 4, so my opponent would retain control of Numel. Note that my value must be strictly greater; a tie would be the same as a loss.

If I were to place my card in the middle right corner, it would be below the opponent's card. As a result, Mareep's "up" value of 4 would be contested against Numel's "down" value of 3. 4 is greater than 3, so I would gain control of Numel (which would turn blue to indicate that).

This process is applied in all four directions at once. If there was a card below Mareep with an "up" value of 1 or 2, I would gain control of it as well. However, gaining control is not done passively or recursively. Control can only be contested at the exact moment a card is placed, and gaining control of a card does not count as "placing it".

## Tournament Rules

Each bot is given a budget of (TBD) with which to purchase cards before the tournament (this will be done by the author, not the bot itself, and will be hardcoded into the bot). Here are the cards, along with their costs:

There - 1000
will - 1500
be - 1500
a - 2500
list - 3000
here - 4000


The bots will play in a Round Robin tournament with Bo3 matches (subject to change. not sure if round robin will work well or if i should be using Bo5 or what). The bot that wins the most matches will be declared the winner.

### Match Procedure

1. Each bot chooses 5 cards from their collection to create a deck. (If they have less than five cards, they forfeit the match.)
2. The game is played as described above, until the board is filled. (i'm not sure how to decide who should go first. alternate? winner of the last game? loser?)
3. When the game is complete, a random card from the loser's deck is removed from their collection and inserted into the winner's collection. (At the end of the match, each bot's collection is reset to its original state.) (i'm not totally sure about choosing a random card. it's how the original game works, but it's not necessarily 100% fair. the idea is that over the course of a round robin tournament, any RNG variance will be smoothed out, but i don't know...)
4. Repeat steps 1 through 3 until one bot has won 2 games.

## Input / Output Specifications and Controller Details

(none yet lmao)

* The Insurgence variant has some nonsense regarding Pokémon types at higher difficulty levels, but this challenge will ignore that.

• Your mention of excluding recursive moves makes me wonder what the game would be like including recursion, on a much larger board... (perhaps as a separate KotH) – trichoplax Sep 1 '15 at 14:34
• Choosing a random card for the winner will introduce unfair variation in a single round robin, but I think that's worth it for the increased variety of games that will test strategies more thoroughly. As long as you don't mind running the round robin multiple times until it converges on a fair score, I would keep the random element. – trichoplax Sep 3 '15 at 7:23

# Is a point inside a polygon?

Given the polygon with 2 < N < 11 sides, on 2D plane, find out if a given point is inside the polygon.

The input can be an array of points in x, y, each determining a vertex, or by a string in format X Y x1 y1 x2 y2 ... xN yN (you may choose other separator). The X and Y are the coordinates of the point to be tested. The list then contains N verices, and the last point is connected to the first point. All x and y are integers.

Using any built-in functions performing the test is prohibited (like this one)

You should consider that a point is inside a polygon also when it is one of its vertices or it lies on one of its edges.

# Notes

1. Tags would be and
2. Should max x and y be determined?
3. Should they be positive (uint) values only?
4. Some questions of this type have already been asked on StackOverflow (example 1, example 2). Is it ok to ask this question here? (I didn't find it)
5. Should the question also allow non-convex polygons? A non-convex (concave) is a polygon which has at least one of its angles larger than 180 deg., and can borders intersect? (I think it can be too complicated and in my opinion it should be for convex polygons only).
• The question should definitely allow non-convex polygons, but if it allows self-intersection then you'll need to pick a winding rule and explain how it works. – Peter Taylor Sep 8 '15 at 19:58
• Be aware that some of the answers here generalize to polygons. – xnor Sep 12 '15 at 18:57

# Literal Fourier Transform (or Fouriest Numbers?)Dupe

(inspired by this Saturday Morning Breakfast Cereal comic)

It's called a fourier tranform when you take a number and convert it to the base system where it will have more fours, thus making it "fourier". If you pick the base with the most fours, the number is said to be "fouriest."

Goal: Given a positive integer n in base 10:

$$4 \le n_{10} \le 2^{31} -1$$

Write a function that displays its equivalent in another base in the format below that maximizes the number of 4s, i.e. the fouriest:

Base x; Fouriest y


Notes:

1. If multiple bases tie on the number of 4s, any base will be accepted. E.g. if the input has the fouriest value already, it's fine to return/display the input.
2. Numbers may not necessary yield a 4, see last example below.

Examples:

• (from comic) 624 -> Base 5; Fouriest 4444
• 2316780 -> Base 14; Fouriest 444444
• 4 -> Base 10; Fouriest 4
• 5 -> Base 10; Fouriest 5

Bonus:

1. Have your function accept a second argument m for the input base: 1/4 reduction in submission size.

Winning:

Shortest code in bytes wins.

This is .

• If two different bases give the same number of 4s, can either be chosen? – trichoplax Sep 8 '15 at 7:18
• @trichoplax yes, I think that'll be an extension of point 1 under "Notes". :) – h.j.k. Sep 8 '15 at 7:22
• I'm not personally a fan of bonuses (I prefer just one well defined objective), but if you choose to have a bonus it might work better to make it a percentage reduction instead of a number of bytes. Otherwise the bonus has very different effect on different languages. – trichoplax Sep 8 '15 at 7:38
• P.S. With or without a bonus, I think this is a brilliant challenge. – trichoplax Sep 8 '15 at 7:42
• @trichoplax along the lines of everything-to-do-with-four, I was thinking of shaving 1/4 for the bonus component, but then I'm not too sure if that's too much. :p I guess I can still consider that... while awaiting for other suggestions. :D – h.j.k. Sep 8 '15 at 8:01
• Dupe – Peter Taylor Sep 8 '15 at 13:32
• @PeterTaylor thanks for pointing that out! I wouldn't be posting this then. It didn't mention "fourier", which explains why it slipped through my search for posted questions. – h.j.k. Sep 8 '15 at 14:23

## Find all matchings code-golfpermutations

Golf this SO question in any language. Fewest bytes wins.

Given two equal-size sets of positive integers,

A={3,1,5}
B={2,4,3}


a matching pairs up elements from each set, like:

{(5, 2), (1, 4), (3, 3)}


There's one matching for each permutation of n elements, where n is the size. Your goal is to print or return all the matchings.

{(3, 2), (1, 4), (5, 3)}
{(3, 2), (1, 3), (5, 4)}
{(1, 2), (3, 4), (5, 3)}
{(1, 2), (5, 4), (3, 3)}
{(5, 2), (3, 3), (1, 4)}
{(3, 4), (1, 3), (5, 2)}


Input: Two nonempty equal-size collections (lists, arrays, sets) of positive integers. Numbers won't repeat within a collection, but may overlap between them. If your collection is ordered, you may assume it to be sorted.

Output: Print or return all possible matchings.

Each matchings must appear exactly once, in any order. They must be somehow grouped or separated, so you can tell where each one beings and ends. These rules also apply to the pairs in each matching.

Banned: Built-ins that generate matchings or permutations.

I have an idea for a challenge but I'm not sure if it would be best as a or , I'm also not sure what rules I should apply to make it more interesting.

## "Convert an image to LEGO safe-colours"

The task is to convert the existing colours from a JPEG image into LEGO-safe colours.

## What are LEGO-Safe colours?

For the purpose of this challenge, LEGO-Safe colours are defined as the seven oldest solid colours produced by LEGO that are still in production. (The exception being grey which has changed in recent years, for the purpose of this challenge, the original grey will be used).

The colours are hexadecimal approximations from this list.

White, #f2f3f2
Grey, #a1a5a2
Black, #000000
Bright Red, #c4281b
Bright Yellow, #f5cd2f
Dark Green, #287f46
Bright Blue, #0d69ab


## Images

You may demonstrate your results using images provided by yourself or the ones shown below.

Lego Factory (Colour)

Lego and Duplo Bricks (Greyscale)

• Dupe – Peter Taylor Sep 18 '15 at 14:27
• @PeterTaylor Bummer – Ambo100 Sep 19 '15 at 9:26

# Another cake question - Share it fairly!

I'm having a party, and there were going to be 8 of us. As I like to cut the slices of cake fairly, I normally get a round cake and make the cuts with the help of a protractor (any code golfer would!) But this time I found the bakery were making octagonal cakes, so I bought one of these to help me with my cutting.

The problem is, now there are only 7 of us! Some people are so inconsiderate, dropping out at the last minute! How am I going to cut the cake fairly now?

Well it turns out that at https://puzzling.stackexchange.com/a/18244/4768 they have the answer. Although my protractor is no good, it's still true that if I start my cuts at evenly spaced points on the perimeter of the cake and end at the centre, all the slices will be of equal size and have an equal area of icing. This is very important. This is quite easy to prove for cakes in the shape of any regular polygon, using the fact that the area of a triangle is base*height/2.

I need you to write me a program or function to show me how to cut my cake.

The code will take 2 inputs: the number of edges on the cake (3 to 15) and the number of pieces to cut it into (3 to 40).

It will output a diagram showing the cake (a regular polygon) and the positions where the cuts are to be made (lines radiating out from the centre to equally spaced points on the perimeter.)

Some examples are shown below. Note for example that for the case 3,9 the slices are all equal size, but the angles at the centre of the cake are not.

You can orient the cake any way you like, but one of the cuts has to pass through a vertex for easy comparison of answers.

Scoring: this is code golf. Shortest code in bytes wins.

# Last Minute Shipments

Here's the situation: You're an engineer for Acme Rail Shipping Inc. There's a string of shipments to make for tomorrow but it turns out at the last moment that they're actually expected to arrive today! There isn't enough time to stop at every destination. It doesn't matter if you skip a few stops as long as you get to others as fast as possible. Your task is to figure out which ones to skip.

### Challenge

Given a list of stops and a minimum number of stops to make, write a program or function that outputs the list of stops to make that results in the lowest total time taken. Here's the catch: Your train is very long and very heavy, so it takes a long time to accelerate. Sometimes it may be more efficient to skip a stop rather than to slow down to make it.

• Your train starts with the front at the origin and is at rest.
• Each stop is a point along your 1D route defined by a positive distance from the origin.
• To make a stop, you must slow down to rest with the front of the train on the point. The shipment is delivered immediately so right as you reach rest, you start accelerating again.
• The train accelerates uniformly at 0.3 m/s^2 and brakes uniformly at 1.2 m/s^2 (I'm not sure how realistic these values are. Subject to change. Feedback would be helpful.)
• Assume that there is no upper speed limit to the train. Therefore, you should be accelerating at every point between stops.
• Added: You cannot go backwards.
• Added: Total time will be measured from when you start to when you pass or arrive at the last stop, regardless of whether you decide to make it or not. You can't just leave your train in the middle of the route! This means that, for example, if you skip the last stop, then the total time will include the time taken for the train to accelerate from the second to last stop and reach the last stop at some velocity. If you don't skip the last stop, the measured time will end when you come to rest at the last stop.

### Input

Input will be a number for the minimum number of stops to make, followed by a list of distances from the origin for each stop. The first item in the list will be the distance for stop #1, the next will be distance for stop #2, then distance for stop #3, etc. Distances in the list are strictly increasing and are defined in meters.

You can take input in any reasonable format, such as a delimited list on stdin with the first item as the minimum number of stops, as program arguments with the first item as the minimum number, or as parameters to a function.

### Output

Output will be a list of stops to make. This list will contain the numbers of each stop, as defined in the previous section. For example, if it is determined that stops 2, 3, and 5 out of five stops need to be made, the output would be 2, 3, 5.

Output can be any reasonable format, such as a delimited list on stdout, or an array return value from a function. Trailing whitespace or newlines are acceptable. The list doesn't necessarily have to be sorted.

### Example I/O

Coming soon


Standard rules apply. Shortest code wins, however clever solutions will get my upvotes. Good luck!

• This feels like a minor variant on the several existing single-source shortest path questions. It's borderline enough that I wouldn't use my unilateral close-as-dupe powers, but I wouldn't be surprised to see it closed as a dupe. – Peter Taylor Sep 21 '15 at 17:52
• @PeterTaylor I did search before I posted this but I didn't find anything, maybe I didn't use the right terms. Are there any examples specifically that you are referring to? – DankMemes Sep 21 '15 at 18:41
• codegolf.stackexchange.com/search?q=shortest+path+is%3Aquestion Not all of them are shortest path in a graph, but I think most of them are. – Peter Taylor Sep 21 '15 at 21:42
• @PeterTaylor I intended distance to always be the same, and the optimization to be for shortest time (I've updated the answer to clarify distance). The point here isn't that you must visit all nodes as fast as possible, it's that you must visit n of the nodes and decide which ones to pass. – DankMemes Sep 21 '15 at 22:07
• Yes, I understood that. So the graph has vertices which are pairs (stop, num visited), for each k > j >= i there is an edge (stop_j, i) --> (stop_k, i+1) with weight corresponding to the time to get from stop j to stop k, and you start at (0, 0) and want the shortest path to (any, n). – Peter Taylor Sep 22 '15 at 6:28

# Strata

Strata is a puzzle game in which you lay coloured ribbons across a grid. When two ribbons intersect, the cell under the intersection takes on the colour of the uppermost ribbon. Here's an example puzzle, ready to solve:

After laying the first ribbon, no cells have been assigned a colour yet:

Laying a perpendicular ribbon colours a cell in:

Notice that, if the uppermost ribbon isn't the correct colour, the cell isn't filled in to let you know you've got it wrong. Also, if a cell doesn't have a target colour, it doesn't matter what colour ends up on top of it; the cell remains colourless when the second ribbon is laid across it:

And a completed solution:

# The Challenge

The object of this challenge is to write a program or function that will provide a step-by-step solution for a Strata puzzle. Here is the layout for the example puzzle provided above, rotated 45 degrees clockwise and with letters a-c substituted for the cell colours:

 ba
ab
a c


For ease of the following discussion, I've labelled the columns 1-3 and the rows A-C.

  ABC
+---
1| ba
2|ab
3|a c


The notation for the output commands will be a single character representing the row or column to lay a ribbon upon, and then another character representing the ribbon type. For example, the command Cb represents laying a ribbon of type b on the rightmost column of this layout.

One of a number of valid solutions for this puzzle is 3a, Cc, 1a, 2a, Bb, Aa. Another is Ca, 3c, 2a, 1a, Aa, Bb.

# Input

Input will consist of the layout for a Strata puzzle. The puzzle will always form a square, with side length of 2-9 inclusive. Each character in the input will be one of the following:

• a lower case letter, representing the ribbon type which should be laid on top of the intersection in the completed puzzle
• a space, representing a cell where the type of the uppermost ribbon does not matter

Note that a puzzle can use between 2-26 (inclusive) ribbon types, and that the types will not necessarily a the first nth letters of the alphabet. Your program/function won't be provided these separately, and should be acquired from the puzzle layout if required.

Input may be provided in any reasonable form that is convenient for your chosen language. For example, you may accept input as single newline-delimited string, as an array or list of strings, etc. Please provide a description of how your submission will expect its input for testing purposes.

Similarly, input can be provided in any appropriate manner. For example, as command line arguments, function arguments, as a stream via STDIN, etc. You should only specify this if it is not immediately obvious.

# Output

Output should consist of a valid solution for the given puzzle. It should consist of an ordered series of instructions, each consisting of two characters:

• The first character should be a number or upper case letter; a number represents a row, starting with 1 for the uppermost row, a letter represents a column, starting with A for the leftmost column (e.g., in the puzzle above, the instruction 4a would be invalid as there are only 3 rows)
• The second character should be the type of the ribbon to lay on the grid; this should be a lower case character, corresponding to one of the types provided on the input (e.g., in the example puzzle above, the instruction Az would be invalid as z is not one of the types used in the grid)

Your program/function can provide the output pairs in any reasonable form, and on any reasonable medium. For example, as a series of comma, space, or newline separated values on STDOUT, as an array for return from a function, written to a file with specified name, etc.

# Other Rules

• A puzzle is only considered complete when all rows and columns have had a single ribbon laid across them, and no row or column can have more than one ribbon laid on it. This means that your output will consist of 2 * (side length) instructions.
• This is code golf, so the winner is the shortest solution in bytes. In the event of a tie, the earliest submission wins.

# Test Cases

Input:

ba
ab
a c

Possible output:
3a, Cc, 1a, 2a, Bb, Aa


This is my first PPCG question, so I tried to make sure every angle was covered. I think I may have gone overboard though, do you think I should get rid of any sections?

As this isn't a puzzle of my own invention, would there be any problems with posting in-game screenshots?

This puzzle is actually pretty easy to work out if you employ a backtracking technique - find a row or column consisting of a single colour, ignoring spaces and cells which have been crossed once. Add this instruction pair to the end of the prototype solution, then mark all the cells as having been crossed once (or twice). Repeat this 2 * (side length) times and you'll have a solution, if there is one to be found.

I want to discourage brute force solutions, so I'm going to come up with a 9x9 test case with more than 10 different types. My stats skills aren't up to much, but I think that, for a puzzle with side length n and number of ribbon types t, the total number of possible ways to lay ribbons on the grid is:

(2n)! * (2n)^t


Could anyone double check that for me? Also, if I were to put in a 9x9, 10-type test case, would that be big enough to rule out a brute force solution? Should I impose some form of computation time limit, and if so, how long on what sort of machine?

• @trichoplax There is indeed a solution which is significantly faster than brute force, which is as described in my comments. For a puzzle of side length n, it requires exactly 2n iterations to find a solution if one exists, and requires a maximum of [the (2n)th triangle number] row/column inspections in the worst case scenario. I can add a discussion of this to the main body of the challenge, but I'm worried that it's already too long! – Sok Sep 22 '15 at 11:32
• I misread that part and thought that was the brute force solution - but I can see now that it is much faster - I'll delete my irrelevent comment... – trichoplax Sep 22 '15 at 11:37
• I confirm your count for a really brute force solution. It's possible to optimise slightly by observing that if there's a sequence of parallel ribbons then the order in which they're placed is irrelevant. – Peter Taylor Sep 23 '15 at 20:26

## Just repeat yourself

Write a program that outputs "Do not repeat yourself!"

Your program code must respect the following constraints :

• its length must be an even number
• each character that is in position 2n (where n is an integer > 0) must be equal to the character in position 2n-1. The second character of the program is equal to the first, the fourth is equal to the third, etc.

Examples:

HHeellllooWWoorrlldd is a valid program

123 or AAABBB or HHeello are incorrect

This is code-golf, so the shortest code wins!

• This rules out most languages which require a keyword to output. For example, print, put or output would be excluded. Maybe there is some way of specifying the constraints to allow many languages to compete, while still being highly restrictive? I can't think of a way, but I wonder if it would help to say "meet 2 of 3 constraints" rather than "meet 2 constraints". Hopefully someone else can come up with a better way that I can't think of... – trichoplax Sep 22 '15 at 11:52
• @trichoplax maybe "each character in the source code must have one and only one neighbour at the left, the right, the bottom or the top with the same character value". – Arnaud Sep 22 '15 at 13:29
• @SuperChafouin Based on that, would comments be allowed? – ASCIIThenANSI Sep 22 '15 at 18:45
• @ASCII yes comments should not be allowed, that would be too easy (just double each line and add "\\") – Arnaud Sep 23 '15 at 2:14
• I think I'll stay on my current rules - they sure rule out some languages, but a lot can still compete. These questions also exclude a lot of languages, yet they are popular and interesting imho : codegolf.stackexchange.com/questions/52809/… codegolf.stackexchange.com/questions/39993/… – Arnaud Sep 23 '15 at 2:19

The shortest code for testing reliable password ( for Vault Password Rank 3 puzzle )

Introduction

I started playing Empire of Code recently, and there was some challenge. The player is supposed to write a code on a python or on javascript to detect if passed string is reliable password, that is, contains at least one lowercase Latin letter, one uppercase Latin letter and one digit and has at least 10 characters.

It was quite easy for me to fit in 130 characters limit for rank 3 using javascript, however, I spent a lot of time trying to fit in 100 characters limit for rank 3 using Python. Some guy said that he has managed to fit in 71 characters for Python. I was trying hard but still couldn't reduce the code less than 90 characters. Is it possible to use even less than 71 character?

Challenge Vault Password [ the following description is mostly copied from https://empireofcode.com/ ]

We've installed a new vault to contain our valuable resources and treasures, but before we can put anything into it, we need a suitable password for our new vault. One that should be as safe as possible.

The password will be considered strong enough if its length is greater than or equal to 10 characters, it contains at least one digit, as well as at least one uppercase letter and one lowercase letter. The password may only contain ASCII latin letters or digits, no punctuation symbols.

You are given a password. We need your code to verify if it meets the conditions for a secure password.

In this mission the main goal to make your code as short as possible. The shorter your code, the more points you earn. Your score for this mission is dynamic and directly related to the length of your code.

Input: A password as a string.

Output: A determination if the password safe or not as a boolean, or any data type that can be converted and processed as a boolean. When the results process, you will see the converted results.

Example:

golf('A1213pokl') === false

golf('bAse730onE') === true

golf('asasasasasasasaas') === false

golf('QWERTYqwerty') === false

golf('123456123456') === false

golf('QwErTy911poqqqq') === true

Precondition:

password matches by regexp expression "[a-zA-Z0-9]+"

Scoring:

Scoring in this mission is based on the number of characters used in your code (comment lines are not counted).

Rank1:

Any code length.

Rank2:

Your code should be shorter than 230 characters for Javascript code or shorter than 200 characters for Python code.

Rank3:

Your code should be shorter than 130 characters for Javascript code or shorter than 100 characters for Python code.

How it is used:

If you are worried about the security of your app or service, you can use this handy code to personally check your users' passwords for complexity. You can further use these skills to require that your users passwords meet or include even more conditions, punctuation or unicode.

# Compute factorials code-golf

In the style of the Hello, World! catalog, this question is a collection of the shortest programs that compute a factorial (a common task for new programmers) in any given language.

## Specifications

Your program must take a positive integer as input from STDIN, and output the corresponding factorial to STDOUT (or your language's closest alternatives).
Your program must also accept the special case of 0! = 1 if 0 is entered. No negative numbers will be entered.

Your program must handle numbers up to 40 factorial (8.159152832×10⁴⁷). Sandbox question: Is 40 factorial too large a minimum requirement? I was also considering 50 factorial is 40 is too small.

## Test Cases

3
6

6
720

0
1

11
39916800


• This is not about finding the language with the shortest approach for computing factorials, this is about finding the shortest approach in every language. Because of this, no answer will be marked as accepted.

• Submissions are scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8. For example, Piet is scored in codels rather than bytes. If you're not sure how your language is scored, you can ask on Meta.

• Nothing can be printed to STDERR.

• Feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program computes factorials, then congrats, you've just created a boring answer.

• Your language must have a valid way to test your program (through an interpreter, compiler, etc.) If there aren't any, you can write one yourself.

• Standard loopholes are disallowed except where specified by these rules.

• For languages with several integer types/ranges, how high do we need to support? There's a big difference between doing this with int and BigInteger in Java, for instance. – Geobits Sep 24 '15 at 14:15
• It's up to you, but I think it'd be more interesting to include 0! = 1 as valid input as well (i.e. input nonnegative integer rather than positive). Also, if FizzBuzz is happening soon, it might be good to wait a while before doing another catalogue. – Sp3000 Sep 24 '15 at 14:16
• @Sp3000 Thanks for that reminder, I overlooked the special 0! = 1 rule when writing this challenge. As for FizzBuzz, if it gets posted soon I'll make sure to leave this unposted for a little while. – ASCIIThenANSI Sep 24 '15 at 14:25
• @Geobits Thanks for pointing that out, didn't think there would be a problem. Programs must support numbers between 0 and 2^31 -1 inclusive. – ASCIIThenANSI Sep 24 '15 at 14:28
• Hmm. I meant more a limit on the output rather than input, since it grows so quickly. Trying to find the factorial of 2^31-1 would probably break most languages :) – Geobits Sep 24 '15 at 14:58
• @Geobits Yup, I tried 50 factorial and it was really big. I've changed it so programs must support numbers up to 100 factorial, but I'm not sure if this is too big. – ASCIIThenANSI Sep 24 '15 at 15:17
• @ASCIIThenANSI I'd argue that, because the amount of observable atoms in Universe is about 10^80 atoms, 50! is almost to big. It might be annoying to check results with slower languages. – MatthewRock Sep 25 '15 at 22:10
• Also, I'd leave out the requirement for valid interpreter - because, depending on language, there might be no such thing - I'd take C++ as an example - I'm almost sure that there can't be valid C++ interpreter, because it wouldn't be compatible with standard (I may be wrong though). – MatthewRock Sep 25 '15 at 22:11
• @MatthewRock Thanks for your suggestions. I've changed the limit to 40 factorial, and changed the interpreter rule to "some valid way to run". – ASCIIThenANSI Sep 26 '15 at 15:37
• I also think that allowing the competition to have a winner could be more appealing, but that's a side note. – MatthewRock Sep 26 '15 at 15:39
• @Geobits WA (1, 2) suggests that you would need about 7.93 gigabytes just to store the number as binary. – LegionMammal978 Sep 26 '15 at 16:24
• There's an old challenge to find factorials with 100 answers. What does this add to that? – xnor Oct 16 '15 at 9:18

# Golf a game of Nim

Similar to my previous Write the shortest game of Alak challenge, this time you have to golf another simple game - Nim.

You may already know how to play, but if you don't, here are the rules:

• In Nim, two players take turns removing objects from heaps (piles).
• Each turn, one player removes at least one object from any heap.
• You can take as many objects as you want, provided they all come from the same heap.
• You can take from any heap you want, but you can't take objects from two different heaps in the same move.
• The player to take the last piece(s) wins.

There are 3 heaps, each starting out with a random number of objects between 2 and 20.

Input

Input is in the form of two numbers - a heap number and the number of objects to take from that heap.
For example, the input 1 2 means "take 2 objects from heap #1".

Output

Every turn, the program must print to STDOUT (or your language's closest alternative) the amount of objects in each heap. (This includes at the start of the game.)
For example, if there were 5 objects in heap #1, 2 objects in heap #2, and 0 objects in heap #3, you would output this:
5 2 0
When one player wins by taking the last piece(s), you have to output P# wins and end the game, where # is the number of the player who won (1 or 2.)

Assumptions

• Input will always be in the form of Heap# Amount. Any invalid input can be handled however you like.
• The input will never ask to take from a heap that doesn't exist, or take more objects than a heap contains.

# Questions for Meta

• Are there any loopholes?
• Should the sizes of each heap be set, rather than random?
• Should there be a random number of heaps?
• Should programs have to handle taking objects from non-existent heaps, or more objects that a heap has?
• I'm 99% certain I've covered everything, but have I left out any rules of Nim?
• Maybe I'm too tired, but I don't see any specification for how the initial sizes of the heaps are set. With respect to your questions, personally I think the rules of Nim are trivial; and that it's if not standard then at least typical for interactive code-golf to not require handling bad inputs. – Peter Taylor Aug 29 '15 at 19:29
• @PeterTaylor Thanks, I've added that to the challenge. – ASCIIThenANSI Aug 29 '15 at 22:56

Cookie Clicker: Simple, stupid, and yet strangely addictive. In it you must click a cookie (hence the title). Once you have enough cookies, you can spend them on items that will produce cookies for you. Eventually you will be getting hundreds, then thousands, then millions of cookies per second.

There are a few different items that you can buy for cookies: A clicker (that clicks the cookies for you), a grandma (that bakes the cookies for you), a farm (that grows cookies for you), a factory (that mass produces cookies for you), a mine (that will mine and process veins of dough for you), a shipment (that ships cookies from other planets to you), an alchemy lab (that transforms gold into cookies), and others that we won't worry about.

Let's golf a simplified Cookie Clicker.

# Challenge

Write a full program. Your program should always display the number of cookies as a whole integer. Every second, your program should add the current cookies per second (defaulted to 0) to the cookie count.

• When the spacebar is pressed, it adds the base click amount (defaulted to 1) to your cookie count.

• When the key "1" is pressed, if there are 10 or more cookies in the cookie count, subtracts the cookie count by 10 and adds 0.1 to the current cookies per second.

• When the key "2" is pressed, if there are 100 or more cookies in the cookie count, subtracts the cookie count by 100 and adds 0.5 to the current cookies per second.

• When the key "3" is pressed, if there are 500 or more cookies in the cookie count, subtracts the cookie count by 500 and adds 4 to the current cookies per second.

• When the key "4" is pressed, if there are 3,000 or more cookies in the cookie count, subtracts the cookie count by 3,000 and adds 10 to the current cookies per second.

• When the key "5" is pressed, if there are 10,000 or more cookies in the cookie count, subtracts the cookie count by 10,000 and adds 40 to the current cookies per second.

• When the key "6" is pressed, if there are 40,000 or more cookies in the cookie count, subtracts the cookie count by 40,000 and adds 100 to the current cookies per second.

• When the key "7" is pressed, if there are 200,000 or more cookies in the cookie count, subtracts the cookie count by 200,000 and adds 400 to the current cookies per second.

• When the key "0" is pressed, if there are 50 or more cookies in the cookie count, subtracts the cookie count by 50 and adds 1 to the base click amount.

There is no input, only output, being changed every second to update the cookie count. No other key should do anything, so you cannot press enter after every key and have it do something.

# Other information

• This is code golf so shortest program in bytes wins.

# Thoughts for sandbox

• There are many, many more features I could add to this challenge if it is too simple. I feel that challenge entries for this will already be long enough.

• I do not see many challenges that ask for constant input. Does this mean that this challenge is a bad idea?

• Have I crossed a line?

• Requiring real-time user input is definitely rare. One big reason is that it's fairly hard to do and (probably) often requires a library. Many if not most esolangs won't be able to do it at all. – El'endia Starman Oct 3 '15 at 3:08
• A lot of people will ask if they can require the player to press enter after typing each number, so you should be explicit that this is not allowed. – feersum Oct 3 '15 at 3:30
• It's a real shame that non-blocking terminal reading isn't easier to work around, although it has been done a few times: 1, 2, 3 it probably would be a bit of a barrier. I do like the sound of this though! – Dom Hastings Oct 8 '15 at 9:35
• The list should show what is being bought here (instead you can skim down the introductory paragraph). – Paŭlo Ebermann Oct 11 '15 at 8:19

This is a raw draft about an idea for a popularity contest. Any input would be appreciated.

# My watch, it has two buttons

I have this watch with two buttons and a display that can show six characters split into groups of two by colons like this

12:34:56


Each character is displayed by a 5x7 LCD-Matrix, so arbitrary ASCII-characters can be displayed.

I'd like to call the buttons "select" and "modify".

The problem is that the watch is dead. It needs a new operating system.

Since I'm not very trained at designing operating systems I want you to write an emulator for my watch. The emulator should be programmable using the following commands.

• big letters A-Z represent short presses of "select" the corresponding number of times.
• small letters a-z have the same meaning for the modify button.
• < represents keeping "select" pressed for half a second (or something like that).
• > represents the same for the modify button.
• numbers in the code mean to wait for that number of hundredth of seconds.

You're free to program any kind of functionality into my watch, but it should at least be usable as a watch showing the time and as a stopwatch showing minutes, seconds and hundredth of seconds.

One thing I know about my watch is that it can be programmed to receive data from my stdin and send data to my stdout. So once the operating system is installed I could send data and a program to the watch and print the results of the execution to my console.

# Spot the differences

Little Timmy is waking you up on this Saturday morning once again to help him solve his puzzles. You love the little bugger, but those Spot the Differences games are starting to undermine your patience. Like always, you plan to delegate this tedious task to Robotic Dad™ so you can better spend your time... planning for your child education? Yeah, I think that was the plan.
Anyway, you tell Timmy not to worry, that you're going to help him soon enough, grab a beer and sit in front of your computer to help your child solve those puzzles, once and for all.

Your task is to write code that will take two similar pictures which differ in a few spots and somehow output the differences between them. The format of the output is free, however a 5 year-old child should be able to get it.

Here are examples of input :

Since there is no formally defined output, this is a .
Please also keep in mind that you'd like to spend a little time sipping your beer calmly in front of your computer. In this regard, built-in solution should be regarded less highly.

Meta : I plan to post a community answer as an example output, linking to the http://franklinta.com/2014/11/30/image-diffing-using-css/ article which made me think of this challenge and using a snippet to illustrate it. Is it enough?

• I don't understand the last sentence. If I want to sip beer calmly, surely a built-in solution is the best? – Peter Taylor Oct 11 '15 at 20:33
• It immediately occurs to me that the easiest way of doing this is to XOR the two images together. BTW What is the input format? – Level River St Oct 11 '15 at 23:35
• The technical side seems like it'd simply be subtracting or xor'ing the two arrays, then the popularity side is very open-ended (just draw freehand circles around them?) – Nick T Oct 12 '15 at 0:18
• @PeterTaylor the father described in this question seems to enjoy his time in front of his computer more than with his child. He still wants to improve his child's future but will use any excuse to do it in front of his computer. Disclaimer : I do not encourage bad parenting ;) – Aaron Oct 12 '15 at 8:47
• @NickT & steveverrill I do not know the first thing about image processing so my challenge may indeed be too way too easy. Do you know how I could avoid simple XOR answers? – Aaron Oct 12 '15 at 8:51

# Sudoku with handicap

Note: I've completely reworked this, as the comments convinced me that there's not a good way to describe the restrictions I originally was after in a language-independent way without unreasonably restricting languages. Thanks to all the commenters.

I now reworked the question in a way that also inhibits traditional recursive solving (at least doing so in a straightforward way), and at the same time even allows to add a metrics about the "efficiency" of the algorithm. The basic idea being that your program is called not once, but many times, each time only having limited information about the field.

Also note that this new version requires me to write a driver program; so the question cannot go live until the driver program is written.

Questions are set in italics inside the text

The goal of this challenge is to solve a given Sudoku. However there's a twist: The program cannot access the full board at any time. Instead it is called repeatedly, and each time it has only limited information about the board. I'll refer to the totality of all calls as the "calling loop". The program can then request different information for the next run, or declare that it is finished (that is, request to not be called again; the call loop is terminated).

The only way to pass information between different runs is through the Sudoku board, and a small amount of scratch space. The Sudoku board is initialized before the first call with the Sudoku to solve (obviously) and is then checked after the call loop terminated. During the call loop, the Sudoku board is not checked, so you may "abuse" it to store additional information, as long as at the end, a valid result is generated.

Since it may not be possible to completely solve all Sudokus using such an algorithm, the only hard requirement is that the call loop is guaranteed to eventually terminate, the Sudoku field after termination is in a valid state. The rest is covered by scoring.

Standard loopholes are explicitly disallowed.

# The stored data

The data that is stored outside the program consists of 90 nine-it unsigned numerical values (that is, minimal nmumber 0, maximal number 511), 81 of which represent the Sudoku field, and 9 values are scratch space. The values of the field are interpreted as bit fields, as described below.

In the following I'll use as example the Sudoku field

4.5|.7.|89.
..2|.5.|6..
..7|9..|542
---+---+---
..3|5.6|489
...|3.8|...
684|7.9|1..
---+---+---
238|..5|9..
..6|.9.|3..
.79|.3.|2.1


where dots contain fields that have not been filled.

Initially, the data gets filled as follows:

• Each field pre-filled with number $n$ is represented by the value $2^{n-1}$, that is, the bit corresponding to that number is set, and all other bits are unset.

• The unfilled fields are represented by the value $511$ (that is, all nine bits are set).

• The scratch space is filled with $0$.

After the run loop terminates, each pre-filled field needs to have the same value as initially, and each initially empty field must have at least the bit corresponding to the correct solution set. That is, every zero bit represents a value that your program excluded for that field, and a program that excludes the correct solution is disqualified.

The contents of the field is only evaluated at the end of the call loop. So in between your program is free to make creative use of the storage space given.

# The input

The program receives its data through standard input of the following form:

The first line contains a description of which data is given to/set by the program in this run. It consists of one to three space-separated words from the following list. On the first run, it is just "S". At later runs, it is exactly what the program requested at its previous run.

The possible values and corresponding interpretation are:

• R1 to R9: The indicated row of the Sudoku, 1 being the uppermost row.
• C1 to C9: The indicated column of the Sudoku, 1 being the leftmost column.
• F1 to F9: The indicated $3\times 3$ subfield of the Sudoku, numbered left to right, up to down. So for example 1 denotes the upper left subfield, 6 denotes the middle right subfield.
• S: The scratch space.

The next one to three lines contain the corresponding data, from left to right, and from up to down, as space separated decimal numbers.

S
0 0 0 0 0 0 0 0 0


At the second run with the example Sudoku field, the input to your program might be:

R2 C3 F4
511 511 2 511 16 511 32 511 511
16 2 64 4 511 8 128 32 256
511 511 4 511 511 511 32 128 8


# Output

The first one to three lines are the new values to replace the ones given in the input. The number of the lines must be the same as the number of fields in the first input line, and each line must contain nine values separated by whitespace (leading/trailing whitespace gets ignored).

If some field appears in more than one data line, the corresponding values are bitwise anded together. For example, if the initial line of your program's input was

R1 C1


and the first two line of your output read (with question marks replacing values that are irrelevant for this example — of course your code may not actually output question marks here)

3 ? ? ? ? ? ? ? ?
5 ? ? ? ? ? ? ? ?


then the upper left value us the Sudoku storage field will be 3 & 5, that is, 1

Following those data lines, there will be a single line containing either the single word STOP, in which case the run loop is terminated and the resulting field is created, or a line containing one to three whitespace separated words requesting data to be served in the next run, that is, the words to be presented in the first line of the next run of the program.

# Scoring:

The score for qualifying entries is calculated as follows (lower score is better):

• You get 1 score point for each run of your program.
• You get 5 score points for each set bit in the final representation of your Sudoku field
• At the end, subtract 45 (because a perfectly solved Sudoku will have nine bits set; if your program leaves less bits set, it will be disqualified anyway).

The total score is then calculated as weighted mean of the test cases, where the difficulty is used as weight, rounded up to the next integer. That is, if $d_k$ is the difficulty assigned to test case $k$, and $S_k$ is the score you achieved at test case $k$, your total score is $$S = \left\lceil \frac{\sum_k d_k S_k}{\sum_k d_k}\right\rceil$$

Sandbox question: Should I change the relative weight of program runs versus unsolved fields? And is the difficulty weighting a good idea, or should I simply add up all scores?

# Test cases:

(Hardness as reported by GNOME Sudoku)

Test case 1: Easy (0.17)

4.5|.7.|89.
..2|.5.|6..
..7|9..|542
---+---+---
..3|5.6|489
...|3.8|...
684|7.9|1..
---+---+---
238|..5|9..
..6|.9.|3..
.79|.3.|2.1


Solution:

415|672|893
892|453|617
367|981|542
---+---+---
723|516|489
951|348|726
684|729|135
---+---+---
238|165|974
146|297|358
579|834|261


Test case 2: Hard (0.63)

.6.|52.|..8
7..|...|9.2
.82|71.|56.
---+---+---
.59|...|..6
.76|...|14.
8..|...|72.
---+---+---
.18|.36|25.
6.3|...|..1
5..|.41|.9.


Solution:

961|524|378
745|683|912
382|719|564
---+---+---
159|472|836
276|398|145
834|165|729
---+---+---
418|936|257
693|257|481
527|841|693


Test case 3: Very hard (0.96)

.35|.94|...
..8|.53|..9
4..|8..|...
---+---+---
..1|9..|.85
..9|1.5|3..
54.|..8|9..
---+---+---
...|..7|..1
6..|58.|7..
...|41.|82.


Solution

135|294|678
268|753|149
497|861|532
---+---+---
371|946|285
829|175|364
546|328|917
---+---+---
982|637|451
614|582|793
753|419|826


Sandbox question: Should I add more test cases?

• Pretty sure you meant code golf not gode golf. – Blue Sep 2 '15 at 10:49
• Is using constraint programming libraries/capabilities of a language allowed, since I'm only calling them and not writing them? – Fatalize Sep 2 '15 at 14:06
• Also do you intend to add a time limit constraint to the challenge? I could write an answer that tries every possible grid until one is valid, without recursion or stacks – Fatalize Sep 2 '15 at 14:09
• @muddyfish: Definitely. Thanks, fixed. – celtschk Sep 2 '15 at 20:12
• @Fatalize: I don't know constrained programming libraries; it might be something I also want to ban. Maybe ban every built-in library that could not be written without recursion? Also, good point on the brute force method. I don't really like time limits, because they are too vague (different computers have different speed), maybe limitations on loops would be an alternative. Or limitations on how often the same variable/memory location may be changed. – celtschk Sep 2 '15 at 20:25
• Limitations on how often a variable can change would be useless in python because you can setattr globals. – Blue Sep 2 '15 at 22:05
• @muddyfish: setattr also changes a variable (by adding attributes to it), doesn't it? – celtschk Sep 3 '15 at 7:38
• Yes but if you're saying you can't do that, you're saying you can only have a certain number of variables. – Blue Sep 3 '15 at 7:59
• I really don't know what's banned as a recursive technique. For instance, what is a stack data structures? Can I use a list and extract the last element? What if I used dynamic programming instead of recursion? – xnor Sep 4 '15 at 7:46
• Are stack-based languages (CJam, GolfScript, PostScript, FORTH, etc) banned? If so, are languages which use a stack for function/method calls (C, Java, etc.) also banned? Would a better approach be to forget talking about stacks and instead allow only a certain number of memory locations to be used, and limit each of them to 8-bit values? Then C-like language programmers can use a single global array for all their memory, or split it between a few global arrays and some loop variables; stack-based language programmers can work with a limited maximum stack depth; etc. – Peter Taylor Sep 4 '15 at 14:07
• Basically what I want to prevent is algorithms trying to insert some numbers, and when it fails, track back and try something different. – celtschk Sep 5 '15 at 5:43

# The Drunken Knight

Inputs

• a: Starting location of the knight, e.g. A2
• b: Target location of the knight, e.g. B4. The starting and target locations may be the same.
• n: An integer equal to or greater than 0.

Output

The probability that a knight starting at a, moving at random for n turns on an 8x8 board, ends at b.

Notes

• The knight has equal probability to move to any of the squares which it can access.
• There are no other pieces on the board that could block any squares from the knight.
• Any time constraints? – Sp3000 Oct 7 '15 at 14:21
• @Sp3000 I haven't really thought about that yet. Do you think it would be more interesting if I tried to disallow brute force solutions via a time constraint? – absinthe Oct 7 '15 at 14:24
• From a simple test (assuming my implementation is right), caching seems to be all you need if you want to bypass a time constraint (brute force ~10 moves in a lot of secs, caching > 100 in less than a sec). So I guess it might be better off without a time constraint after all... – Sp3000 Oct 7 '15 at 14:51
• 1. Is the knight moving on an 8x8 board? 2. Please tag markov-chain – Peter Taylor Oct 11 '15 at 20:50
• Ah, another thought which occurs: valid output formats? The obvious three are floating point to a certain precision and accuracy; exact rational; and exact rational reduced to simplest form. – Peter Taylor Oct 13 '15 at 13:31

# Time Series Analysis

Time series analysis comprises methods for analyzing time series data in order to extract meaningful statistics and other characteristics of the data (from here).

## The challenge

Write a program or function that take a time series vector ts and output a the coefficient of determination of a simple linear regression model estimated by the ordinary least squares.

The coefficient of determination should be the squared correlation between the predicted values of the model and the real values of the input, in such way that any perfectly linear time series should have 1  as it's coefficient.

### Considerations

• ts is a vector of racional numbers of length $\dpi{80} \boldsymbol{n | 2 \leq n \leq 99}$.
• To make the model assume ts is time sucessive and use time as its regressor.
• You can assume that ts is already loaded.
• You can't use build-in modeling functions such as lm() or similars.
• The input should be in any reasonable format.

### Examples

# input
1,2,3,4,5,6
# output
0


#input
0.244,0.569,1.575,1.965,2.604,3.493,4.084,4.436,5.209,6.110,6.979,7.245,8.229,9.161,10.309
# output
0.971


Let the shortest code win!

• This could use either a link to a page that clearly explains the terms and method used, or preferably a better explanation within the post. – Geobits Oct 14 '15 at 18:42
• Good idea, I will link it. – Mutador Oct 14 '15 at 18:43
• The fact that this is time series doesn't change anything since it's just OLS estimation, which is not specific to time series. OLS requires two dimensions, so x is essentially position in the series and y is the value of the series? – Alex A. Oct 14 '15 at 18:43
• I thought about saying time series to add some context, but yeah, it is just that, not sure about the output though. – Mutador Oct 14 '15 at 18:46
• What does lm() do? – flawr Oct 14 '15 at 18:53
• @flawr lm() is a function in R for fitting linear models. – Alex A. Oct 14 '15 at 19:33

# Cops and Robbers: Text Transformations

### Cops' challenge

The cops must write a fully deterministic program that reads input from STDIN and writes output to STDOUT as its only side effects. The mapping from strings to strings performed by this program will be called f.

A cop's post consists of such a program's source code, along with its length and the name of the language the program is written in. The poster must also prepare a possible crack (see below), and release it when their post is safe. A cop's post is safe when it remains uncracked for exactly two weeks.

A safe post where the original code is n bytes long is worth 1/n² points. The author with the highest point total wins. The tiebreaker is popularity (sum of votes of answers in the robbers' thread.)

A single author may not use the same language twice in two different cop answers.

### Robbers' challenge

To crack a cop's post, a robber must figure out which transformation f the program in the post is performing, and write a program P in the language used by the cop, so that both P and f(P) perform the transformation f.

The length, method, or complexity of P are irrelevant; as long as is produces the same output as the cop's original code for any input you pass it, the solution is valid.

Successfully cracking a cop's post is worth one point. The author with the highest point total wins. The tiebreaker is popularity (sum of votes of answers in the robbers' thread.)

This is a bit hard to conceptualize, so here's a very simple example.

If the cop's post is:

## Python 3, 20 bytes

print(input()[::-2])


(i.e., reverse STDIN and remove every other character) The robber's answer might be:

print(input()[::-2])# ) ] 2 - : : [ ) ( t u p n i ( t n i r p


as passing this program as input to itself yields a new program that does the same thing:

print(input()[::-2])#]-:)tpitip


As another example, if a cop writes a C++ program that rotates lines on STDIN by 90 degrees, a valid solution is a C++ program that also rotates lines by 90 degrees, and does the very same thing if you rotate it by 90 degrees.

The difficulty for cops is to come up with transformations that are short to express, but difficult to code around (and, of course, they essentially have to crack their own post -- but at least they know f in advance.)

The difficulty for robbers is to decipher the cops' solutions to find out which transformation f they're performing, and then write any program P such that both P and f(P) perform f.

• "A single author may not use the same language twice in two different cop answers." Not a fan of rules like that. Anyway, is there anything to prevent a cop from using a function like "Return the (n/2)nd character of the string." In that case it's pretty much impossible for f(P) to compute this function. Or should the mapping be surjective? Also do cops and robbers have to use the same language? Finally, how do we prove that a robber's implementation computes the exact same function as the cop's, especially if the cop's code is obfuscated and undocumented? – Martin Ender Oct 19 '15 at 12:07
• If it's impossible for f(P) to compute f, the original post is invalid anyway -- cops must be able to crack their own cop answers and release the solutions if they go uncracked. Also, yeah, they would use the same language. – Lynn Oct 19 '15 at 13:16
• @feersum pointed out a more serious problem in chat: cops can post something like x = readline(); if (md5(x) == 'f0a92b8efc0...') print x, which is nearly impossible for other people to solve. – Lynn Oct 19 '15 at 13:18

# Watermelon Contest

You and your buddies are contesting a lone piece of watermelon left in the middle of the table. You decide to make a program to contest for you.

## The Goal

You want to be the last program standing. Then you get the watermelon.

## The Process

Every iteration 1 program will be eliminated from the watermelon contest. This will be decided by a vote among all the remaining programs. This means that your program will have 1 and only 1 vote to spend on the elimination of another program. Whichever program ends up with the most votes is eliminated.

This continues until there are only 1 program left, the winner. This entire process is considered a "round".

After there is a winner, another round will be started with a new piece of watermelon. All programs will be re-entered. When 10,000 rounds have been completed, the program with the most "wins" will be considered the "grand champion". All the rounds combined is considered the "tournament".

## The Catch

Every program will have an opportunity to send a message to all the other programs. The message must be the same for every program. The message is a string, up to 500 bytes long.

You may have a file in which you may store any data you wish from previous rounds. This will persist over the entire tournament.

## The Program

Write a program or function that accepts the following input in any (convenient) form:

[program-name], [message], "The Slug", "hey! don't vote for me!", "Chucknorium II", "a2TEI5ds#" ...


and outputs the name of the program that you vote for:

Chucknorium II


## Notes

• In the likely event of a tie, one of the high scoring programs will be randomly eliminated
• Messages can be anything that doesn't mess with stuff it's not supposed to (e.g. don't mess with the controller or other people's programs). This is what makes the challenge interesting.
• You may not hard-code program names into your program! In other words, numbering the programs randomly at the beginning of the game should produce the same output. Names are just more fun.
• For observation purposes, your program will still be run even if it has been eliminated. It will not, however, have a chance to vote that round.
• This seems to reward out-of-band collaboration (or posting multiple answers, which is effectively the same thing). – Peter Taylor Oct 20 '15 at 8:20
• So the winner between the last two is basically always random (since I assume neither will vote themselves out)? – Geobits Oct 20 '15 at 18:34
• @Geobits correct. Over several thousand rounds this should even out. – Stretch Maniac Oct 20 '15 at 19:49
• I see. There's nothing about how many rounds will be played, so I was wondering about that. If you add this, you should make sure to distinguish turns/rounds or rounds/games, etc. – Geobits Oct 20 '15 at 19:53
• Also, do programs continue to be called once they're "out"? If I want to track who did well each round, for instance, I don't think I can (since I think I only get input up to when I get voted out). – Geobits Oct 20 '15 at 19:56
• Good point. Yes. You just won't be able to vote. I'll change that (and other things) when I get to a computer. – Stretch Maniac Oct 20 '15 at 19:59
• I don't need to hard-code program names: I just need to agree a signature algorithm whereby the combination of name and message means that either the program is a collaborator or they're piggybacking on our agreement. – Peter Taylor Oct 20 '15 at 20:37
• I see... How about a statement that prevents engineering to specific programs? Would that prevent pre-determined collaboration? – Stretch Maniac Oct 20 '15 at 20:42
• Can you clarify the format of the input – user193661 Oct 21 '15 at 9:05
• I hate to be a party pooper, but I honestly don't see the point of this KOTH since it seems to be more politics than programming. Then again I didn't get the cake cutting one either and look at how that one turned out... – Sp3000 Oct 23 '15 at 12:36

# "The" Gaidhlig Challenge

The Gaidhlig language has some non-trivial rules when it comes to putting "the" in front of a word.

You're challenge is to create a program that takes two inputs, the first input is a string of text, a real word or made up that we can pretend is a noun. The second input is either the letter 'f' or the letter 'b' to denote whether the word is masculine or feminine.

The type of delimiter between these two inputs is your choice but must not be the letters a to z, a dash, or an apostrophe.

1. The first input is always assumed to be a noun.
2. The second input denotes whether the noun is masculine (f) or feminine (b).
3. We will always assume all inputs is valid.

You're output will be the the first input, modified for the following rules:

## Masculine Nouns (where 'f' is supplied.)

1. Before vowels: An t-

2. Before b f m p: Am

3. Before all other instances: An

## Feminine Nouns (where 'b' is supplied.)

1. Before sl sr sn so se si su: An t-

2. Before b m p c g : A' [with lentition]

3. Before f: An [with lentition]

Before all other instances: An

## Whether the word is masculine or feminine:

Words that start with l n r sg sm sp st always start with: An

## Lentition

When lentition is asked for, you must add the letter h after the first letter of your word in cases where the word starts with b c d f g m p s t. Otherwise the word remains unchanged. Further, you must not add an additional letter h if there is already a h in place.

Examples

Lentition of Aran: Aran

Lentition of Ghoul: Ghoul

Lentition of Goul: Ghoul

Lentition of House: House

# Examples

Cat f An Cat

Cat b A' Chat

fear f Am fear

fear b A' fhear

Obair f An t-Obair

Obair b An Obair

snow f An snow

snow b An t-snow

Shortest code in bytes wins.

• I think you have a consistent typo: it should be lenition, right? – Peter Taylor Oct 23 '15 at 21:54

I would love to hear your thoughts about the following challenge. Too difficult or contrived? Or should we actually want more complicated and challenging tasks? I'll provide an example implementation in MATLAB by the time I post the challenge.

## Concert Harp: Pedal Meddle code-golf

Sometimes I hear people say, ‘Why would anyone outside the ICT business learn how to program?’ Often, they get replies like ‘well, sometimes there are problems to which there is no software available’, but when asked about what kind of problems these would be, they’re forced to admit that all they really wanted was to make Conway’s Game Of Life for their own entertainment.

However, I recently found a problem that I think the home-and-garden programmer could face in reality. It considers a harp (a side effect sharing an apartment with a significant other) and a completely dumbfound pianist/programmer, who’s struggling enough with one pedal as it is. The harp in question has seven.

Now, for some background music/harp theory. You may skip as much as your musical background, or lack thereof, allows.

# Music theory (a very condensed version)

Both in a harp and a piano, the strings/keys are laid out as follows:

… C | D | E F | G | A | B C | D | E F | G A | B …


There are seven root notes, [A-G], with at some locations a | in between to signify that there’s a note in between. These |’s are address by making a note higher by appending a #, or lower by appending a b. For example, C#==Db, F#==Gb (and also, Fb==E). Using these notes, we can make a scale. The difference between D and D# is called a half note, and between D and E a whole note.

Scales are made as follows: 1: take the root note 1: Find the next notes by going up a whole or half number of notes in the following pattern (last step in () because that makes you end up at the root note again)

Major: 1 1 ½ 1 1 1 (½)
Minor: 1 ½ 1 1 1 1 (½)


For example, D major and A# minor D E F# G A B C# (D) A# B# C# D# E# F# G# A#

Of course, these notations are not unique, since for example E#==F.

# Problem

A harp has seven pedals, each responsible for one note. This note, they can either raise half a note, or lower half a note. For example, the C pedal can either make all C’s sound like C#(==Db) or like Cb(==B). Let’s designate raising by a pedal setting of +1 and lowering by -1, and leaving it as-is as 0. Given an input scale, write a program or function that outputs how each of the pedals should be set to achieve all of the tones in that scale.

# Input

A scale designation. Scales are designated as follows: R[m][k]

• R: Root. [A-G]
• [m]: Optional: modification. Either flat b or sharp #
• [k]: Optional: minor key, designated as m.

Valid inputs would be for example

• C C major
• Dm D minor
• Fbm F flat minor

# Output

The pedal setting -1, 0 or 1 for each of the pedals, in the following order, reflecting the actual location of the pedals on a harp:

D C B | E F G A


Test cases: (not exhaustive; i.e., there may be more solutions, I only included a double solution to one input)

C , B#, Am -> 0 0 0 | 0 0 0 0
Cm, B#m    -> 0 0 0 | -1 0 0 0
F#m, Gbm   -> 1 1 0 | 1 1 1 1
or -> -1 -1 -1 | -1 0 -1 -1

• I'm confused: you say "Given an input scale" and then describe the input as "A chord designation". Which is it? – Peter Taylor Oct 25 '15 at 7:38
• @PeterTaylor thanks, I was doubting between two versions of this challenge so that must've slipped through, edited now. What do you think of the challenge itself though? – Sanchises Oct 25 '15 at 10:18

# Stupid leaks

Considering how immensely successful my last two challenges have been, I'll do a different style this time.

Drip, drip, drip, drip...

It's the year 3000. Due to clean air shortages, a system was created that turns water into air. However, that caused a water shortage (don't you love progress?). Therefore, a new (expensive!) system was created to convert the air back into water.

All that to say that water prices have skyrocketed.

And yet, here you are, stuck with a leaky faucet. Plumbers are expensive, but if you do it yourself, you have to order the parts online and wait for them to get here. You need a way to determine what is cheaper: calling a plumber and getting it fixed in a day, or buying the parts online but having water leak until they get here.

## The input

You need to take seven positive numbers as input:

• The price of water per gallon g.
• The number of drops leaking per hour d.
• The number of gallons wasted per drop z. This will always be a floating-point number less than 1.
• The price of calling a plumber to fix it p.
• The price of ordering the parts online o.
• The number of hours it takes for the plumber to fix the leak l.
• The number of hours it takes for the parts to get here s.

Only g, z, p, and o can be floats; all the rest will be counting numbers (integers greater than 0).

The gallons of water wasted per hour from the leak is d*z*g. For the sake of brevity, let's call that rate R. If R*l+p is less than R*s+o, then you should print/return DIY!. If greater than, print/return Call the plumber!. If equal, print/return Whatever....

## Precision

Floating-point precision through calculations is very...weird. Basically, your program can use whatever your language's default is. If you're using a language where the default floating-point type has infinite precision. If your language's default floating-point type can lose precision throughout calculations (like in Python, where .1+.1+.1+.1+.1+.1+.1+.1 != .8), then that works, too.

Short version: floating-point semantics and precision are however your language is by default.

## Scoring

Code-golf. Shortest wins. Standard loopholes banned.

• What is a "counting number"? Does it include 0? You also might want to specify at what precision the equality will be checked (presumably hundredths?), and how rounding should be handled for the "Whatever..." case. – FryAmTheEggman Nov 2 '15 at 18:24
• @FryAmTheEggman Is this better? – kirbyfan64sos Nov 2 '15 at 21:03
• My language doesn't support floating point at all, so can I always just output Whatever...? More seriously, I'm failing to see the point of this question. Do some trivial arithmetic and then output one of three strings which between them take up 90% of the code? – Peter Taylor Nov 2 '15 at 21:15
• I think it is better, but I think you do have to spend a bit addressing Peter's comment about languages that don't support floats. – FryAmTheEggman Nov 2 '15 at 23:55

Oh, no! There's been a fire at Claus HQ, and it's destroyed Santa's flight route! He has called on you to come up with a route that has him arriving at every home between the hours of 9PM Christmas Eve and 7AM Christmas Day. He'd also like to finish his deliveries in as little time as possible.

Input

Your program will take data for as many geographical areas as you or Santa chooses to enter. For every geographical area to be added, your program will accept:the name of the area, and the geographical coordinates of the area's center and the number of "nice" children who live in that geographical area.

Output In a .csv file your program will place:

1) Each geographical area's name, 1 per line, listed in order, with the area to be visited first placed first, and the area to be visited last placed last.

2) Next to the name, an ETA to the area in local time, and estimated time of departure, assuming Santa takes about 1/6100 seconds per child.

3) At the last line of the file, the total number of miles travelled, as determined by the sum of the great-circle distances - determined using the Vincenty formula, assuming an oblate spheroid Earth - from each stop to the next. Other than as stated above, I don't care what your file looks like. Rules

-You may not use any external library to perform any task except the following:

--Converting from one timezone to another.

-You may give your output file whatever name you choose.

-Estimated departure times must be no later than 7:01 AM.

Scoring For simplicity, scoring will be done using US states as areas. The population inputted will be the number of 14-and-under Christians residing in each state.

You get 1 point for every thousand miles travelled and an additional point for every hour of travel.

• 1. "Vincenty formula" should be hyperlinked to a clear explanation, and geode parameters should be supplied. 2. Converting between timezones isn't hard, and doesn't need an external library, but the input does need to include the timezones. It would also be good to state explicitly whether or not the International Date Line needs to be taken into consideration. 3. We have no way of calculating travel times, because you haven't given us a speed. We also have no way of scoring our programs, because you haven't supplied the test data. – Peter Taylor Nov 8 '15 at 8:11

## Convert your Language to Turing Machine Code

You are locked into a room, with only a laptop and a single-bidirectionallyinfinite-tape, two symbols Turing Machine (Therefore supports only 0s and 1, and it has a tape which is infinite in both directions). Your perverted captor set you a task: he will set you free only if solve all of the problems on the Project Euler page.

However, there is a catch. You are not allowed to solve the problem using your laptop, but you'll need to use the Turing Machine instead.

Since you think it will be incredibly tedious to convert your code to Turing Machine Code, you decided to write an source-to-source compiler on your computer, and since you're incredibly eager to get out, you decide to write your code in the shortest form possible.

## Summary

• Write in your language of choice an compiler that converts your language into your Turing Machine Code.
• Your language may not need to be completely transformed, but at least the basic operations needed for mathematical computations need to be implemented, therefore you will need to implement at least three of the following, with mandatorily being able to translate a looping construct of your language, then for each more operator implemented you will get a 10% bonus:

• Subtraction
• Division
• Multiplication
• Modulus
• Looping (Mandatory)
• Bitwise operators: &(AND) |(OR) ^(XOR) !(NOT) (they count as 3 distinct ones)

In practice your code should be able to translate at least a primality testing algorithm into Turing Machine Code.

• When I refer to Turing Machine Code, I refer to code for TML (Syntax explained later here)

## Technicalities

• The turing machine does not support decimal numbers, only binary, so you may (or may not if you have a better method) write numbers in unary. e.g 11111011 are respectively 5 and 2

• Since the Turing Machine does not have a predefined IO, you may consider leaving the return value on the tape and halting as returning a value. e.g 111110000 and halting will return 5.

• For the Input, you have full access to the starting tape, according that you don't do any other operation rather than initializing the variables. e.g if you implemented add(a,b) and run add(5,7) you may initialize the tape to this: 1111101111111 or 11111001111111 or 111110001111111 exc. but you may not initialize the tape to: 111111111111

• TML Language description. TML which is the language your are interpreting your code to, uses a systems of cards, in this form 0{0-1}{0-1}{Integer}-1{0-1}{0-1}{Integer} where the first value determines which piece of code to execute (reading a value from the tape and comparing it, if it is 0 it will execute the code after the 0 until the dash, else the other piece of code), the second one tells what to write on the tape(0, 1), the third one finally tells the tape whether to go left(1) or right(0). The last value tells us to which card to go next, with the card 0 reserved for halting.

Note that TML is not 100% complete, so if your code follows the specs, but doesn't actually work just let me know, so I can fix the Language interpreter (if it's actually broken)

This is Code Golf, so the shortest code wins!

• 1. The mention of interpreters is confusing: what you're asking for is a source-to-source compiler. 2. It would be useful to mention in the first sentence that the TM only supports two symbols. 3. What does "when to execute the card" mean? 4. In what circumstances could n be useful? It just seems to overcomplicate the explanation. 5. Is the tape infinite in both directions or just one? 6. What are "the basic operations needed for mathematical computations"? – Peter Taylor Nov 7 '15 at 12:31
• @PeterTaylor I've modified the question a bit, I think it should be clearer this way, the only thing I haven't changed is the use of n, which I think could be useful if one were to implement something like a "pass" card (just speculating). What do you think? – WizardOfMenlo Nov 7 '15 at 13:04
• That's rather a long list of mathematical operations! Is the intention to handicap higher levels languages because they support more operations and so will have more cases to compile? Write nothing is equivalent to writing what you read; move nothing is "Enter an infinite loop" if you wrote the symbol you read, or "See the other side of this card" otherwise. So all ns can be eliminated trivially except the infinite loop case, which can be eliminated by adding two cards x and y with instructions 000y-100y and 001x-101x respectively. – Peter Taylor Nov 7 '15 at 13:19
• @PeterTaylor. The long list of operations I've introduced as sample operations, that I think a standard programming language should have, however I am no Programming Language expert, and I'm quite ignorant (yet) of the variety that they present, especially regarding the operations. Regarding the "n", I think that your logic is more than valid, and I will also project this change to the language itself. Thank you a lot! P.s If you have some more effective ideas for the operations to implement, please be welcome! – WizardOfMenlo Nov 7 '15 at 23:17
• There are a lot of astandard languages on this site! The obvious language to use to answer this challenge is BF, which doesn't have anything more than increment and decrement. (And even a language as mainstream as Java doesn't have an operator for exponentiation or integer square root). – Peter Taylor Nov 7 '15 at 23:39
• @PeterTaylor I've now added a system of bonuses, what do you think? Do you think the question is ready to be asked? – WizardOfMenlo Nov 8 '15 at 8:51
• In addition to the issue of languages not having all of the operations on that list built-in, I find long lists of bonuses unappealing in general. I suggest that you scrap the list of operations, and instead require that the source language has to be able to translate all of its own functionality. This would create an interesting tradeoff between languages which are powerful, but have too many functions to implement, and ones that have the advantage of being minimal, but are difficult to program in. If you go with this, make sure to require the source language be Turing-complete. – feersum Nov 9 '15 at 8:10

# First 100 Twin Primes

### What Are Twin Primes?

Twin primes are two prime numbers that has a gap of 2 between them; i.e. 3-5, 5-7, 11-13...

### Goal

• Take no input and print first 100 twin primes to STDOUT.
• Shortest code in bytes wins.

### Rules

• Your submission should be an executable complete program.
• Every prime couple should be on a new line.
• Printed twins should have a space between them.
• All standard rules are applied.

### Restrictions

• No usage of built-in or external methods or functions that returns a prime number.
• No hardcoded prime numbers except 2 (as number, not count).

Any suggestions? I looked to similar questions but i couldn't see an identical one.

• Unfortunately, we consider questions for which most solutions can be easily transferred duplicates, so without the restriction on builtins (and probably even with) your question would be closed as a duplicate of codegolf.stackexchange.com/questions/31822/… – lirtosiast Nov 10 '15 at 1:14

# Rounding Fractions

Back in the old days of game programming, before FPUs were the norm, games predominantly used fixed-point math to represent non-integer values. Typically, the lower 8 or 12 bits of a 32-bit word are used as fractional parts, and the rest are treated as the integral part. Sometimes when looking at fixed-point constants in old game code, I get confused trying to figure out what they were actually trying to approximate, particularly if it's not a number between 0 and 1 (0x4C = 0.3, 0x119 = 1.1?, 0x73 = ???).

Since just rounding 1/256ths and 1/4096ths has a limited range of applications, the challenge here is to take any integer ratio a/b, and output the simplest fraction that rounds down to it. More specifically, output the ratio p/q with lowest denominator such that a/b ≤ p/q < (a+1)/b.

This code should support any non-negative a and positive b up to at least 10,000, and should run in a reasonable time for anything in that range (nothing on the order of minutes, at least). Answers should be correct, i.e., no rounding errors due to floating-point. Answers can be in the form of a full program or function, and use any convenient input / output (a string '1/2', an ordered pair (1, 2), a list of two integers {1, 2}, etc).

This challenge is code-golf, lowest score in bytes wins.

Some test cases:

1/3 -> 1/3
4/10 -> 2/5
33/100 -> 1/3
66/100 -> 2/3
67/100 -> 19/28
115/256 -> 9/20  (who knew?)
0/417 -> 0/1
653/654 -> 653/654
1404/702 -> 2/1


## Sandbox Questions

Hey! I'm a long-time lurker, first-time-question-asker; I'm pretty sure this hasn't been asked before (more general than "Un-round fractions", not quite "Closest fraction"). Not sure what to set for a deadline before accepting an answer, since this is my first time actually participating. Anything else obvious I missed?

• Don't set a deadline before accepting an answer, at least in the sense of putting a date in the question. As a rule of thumb, wait a week, accept the winning answer, and if someone later posts an improved answer then change the accepted answer. – Peter Taylor Nov 14 '15 at 18:19
• Sort of duplicate? The differences seem to be normal rounding vs rounding down and the odd restriction to a single loop in the existing challenge. – Martin Ender Nov 14 '15 at 23:46
• That challenge is only about decimals, whereas this starts with an arbitrary rational number. Not sure if that's enough of a differentiation, but this one's broader, I guess. – Jonathan Aldrich Nov 15 '15 at 0:02
• @MartinBüttner, I agree it's borderline, but some of the answers to the older question couldn't easily be adapted because they rely on converting float to string, and that only works in base 10. – Peter Taylor Nov 15 '15 at 8:47
• @PeterTaylor It is a duplicate. floor(x)=round(x-0.5) – Xwtek Nov 17 '15 at 12:04
• @ChristianIrwan, why is that relevant? – Peter Taylor Nov 17 '15 at 14:32
• @PeterTaylor Oh, sorry, misread. – Xwtek Nov 18 '15 at 9:45

# Nondeterministic Turing Machine

## Introduction

We all know the concept of Turing machines, if not let's reiterate the concept. We have the following things that define a Turing machine:

• A tape that is divided into cells and is (potentially) infinite to the right.

• A transition function that defines state changes and the direction in which the head shall move, based on the current state and the input read.

We can now have to supply some input, and the definition of the transition function (the set of states is implicit, and contains all states defined in the function). Additionally we assume that the alphabet is [0-9a-zA-Z!?()^+-] and space is the blank symbol. The tape head is then postioned over the leftmost character on the tape, which in our case is the first character of the input tape. The machine then starts applying the transition function. The computation continues until one of the following happens:

• The machine reaches the HALT state
• There is no transition defined in the transition function for the current state with the given input.

If the first case occurs, we say that the machine "accepts" the word. If the second case occurs we say that the machine "rejects" the word.

We can now extend this definition, to obtain a nondeterministic Turing Machine. To do this we allow the transition function to define more than one "next" state for each state/input combination. The machine can then choose which "execution path" to take. We then say that the machine accepts the word if it reaches the "HALT" state in any execution path, and it rejects it if it does not reach this state in all exection pats.

## Problem definition

You must supply a program or function that accepts a string and returns a truth-ish value (either true/false, or 0/1, or anything else, at long as the meaning is clear) indicating wheter the word is accepted for at least one computation path or not. The input has the following for:

(<current_state>,<input_read>,<output>,<follow_up_state>,<move_direction>)


All the parts of the tuple are provided as strings where

• <input read> is a string of length 1, which can contain any character except ","
• <output> is also a string of length 1
• <move_direction> is either "l" (move left) or "r" (move right)

You may assume the following:

• The machine will always halt (i.e. no infite loops)
• There is only one state on which the machine halts which is HALT
• The alphabet is [0-9a-zA-Z!?()^+-] plus space as the blank symbol
• The leftmost character is always a blank, to indicate the ending of the tape on the left side.
• States are defined implicitly by the tranistion function. So the only states the machine knows are the one that occure during the definition of the transition function and there is no explicit definition of the states.
• The initial state is always s_i

The input has the following form

<nr_of_tuples_for_definition_of_transition_function>
<tuple_1>
<tuple_2>
...
<tuple_n>
<input_string>


All lines end with a newline character (\n) and the input string is not under double quotes.

Standard loopholes are disallowed! Shortest answer in byte wins.

# Notes

Working example is still missing, I'll update that in the following days

• "The machine then starts the computation at the beginning of the input": I suggest adding "i.e. with the first character under the tape head, and the others to the right". I'm not sure what you mean by "States are defined implicitly by the tranistion function". – Peter Taylor Nov 13 '15 at 13:59
• Followup questions: 1. What characters can appear in the name of a state? 2. What delimiters occur between the tuples in the input? 3. What delimits the end of the initial tape contents and the start of the tuples? – Peter Taylor Nov 13 '15 at 18:20
• Thank you very much for your feedback. I just realized that I didnt think the input part through, I'll need some time to rethink that. – wastl Nov 13 '15 at 18:54
• I realised today that there's another thing which needs specifying in the input: what is the starting state? This could done implicitly by saying that it's the <current_state> of the first tuple. – Peter Taylor Nov 14 '15 at 18:20
• I added input specification. Do you think this is an adequate method to provide the input? – wastl Nov 16 '15 at 11:39
• Yes, that works. – Peter Taylor Nov 16 '15 at 12:16