# 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 your first try can be difficult, and there is a much better chance of your challenge being well received if you post it in the Sandbox first.

To post to the Sandbox, scroll to the bottom of this page and click "Answer This Question", or click on the "Add Proposal" link below. Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the Sandbox post.

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

# Make a quine that shrinks and grows

Write a program that outputs another program that is:

• Larger in bytes than the original
• Outputs a program that is smaller than itself that also obeys these rules and is larger than the original program

Basically the output should alternate between larger than the previous program and smaller than it, while increasing in total size as it goes.

Related

• Perhaps it should be "larger than the program two before" rather than "larger than the original?" As stated, a 5-length program could output a 7-length, which outputs a 6-length, which then oscillates between 7 and 6, not growing in total size as it goes. – Ethan Chapman Oct 8 '20 at 18:51
• Probably should be named something other than a quine because I find that term misleading for the challenge you described. – Beefster Oct 14 '20 at 21:12

The goal of this challenge is to fill a niche that is mostly lacking on this site. In my observations there most parsing verification challenges fall into two categories:

1. Super easy parsing. This parsing can usually be done with a regex, and regex based answers usually do well.

2. Super complex parsing. These are challenges with a lot of small parsing components that would on their own be type 1, but together make for long code with a lot of edge cases.

Neither of these categories are really bad, each can have fun challenges, but I want to shoot for something different. A challenge which is hard, hard enough that a regex will be unable to do the brunt of the work but with a easy to understand spec.

The goal of this challenge is to parse a lisp-like lambda function. Your code should accept a string as input and output of two possible consistent values. One which corresponds to an affirmative response (i.e. the input is a properly formatted lambda) and the other corresponds to a negative response (i.e. the input is not a properly formatted lambda).

I've put together 3 specifications of what constitutes a validly formatted lambda for this challenge. The first is a quick intuition base explanation. It explains the process and what things mean even if it is not perfectly rigorous. The second a formal grammar which expresses the idea succinctly and with no ambiguity. And the third is raw code, which is the hardest to read for humans but allows you to play around with the idea by trying different inputs. I recommend you read one of the first two and play around with the third.

## Formatting

The challenge uses a lisp like format. This consists of "lists" which are just parentheses enclosing lowercase words, and other lists separated each by a single space. So

(foo (bar baz) foobar)


Would be a lisp-like "list". For our challenge each list will be identified by it's first element (which should by highlighted by the syntax highlighter), which must be either app, abs, or var, representing applications, abstractions and variables, respectively.

An application is the application of one lambda function to another. It is represented by a three element list starting with of course app followed by two other valid lambda expressions. So if S and K were valid lambdas then:

(app S K)


would be a valid lambda too.

The other two abstractions and variables work together, an abstraction introduces new names for variables and variables use those names. An abstraction encloses some lambda which must be valid with the introduced variable name, and a variable can only use names which are given by abstractions that surround it. So

(abs x (abs y (var x)))


Is valid because the x name was introduced and used in a nested context. But

(app (abs x (var x)) (var x))


Is not because even though there is an abstraction for x the second (var x) is not surrounded by any abstraction at all, let alone one that introduces x.

Additionally abstractions can only introduce new variables, so

(abs x (abs x (var x)))


is not valid because the name x is ambiguous, it could refer to either abstraction. Variable names must be a string of lowercase ascii letters (a-z).

## Grammar

Now for the golfy definition. This parse cannot be defined in terms of a context free grammar, so this grammar uses context. The context is a set of strings of lowercase ascii letters as these are the valid variable names.

$$\ \begin{array}[rr] \ S\left(x\in C\right) &:= \color{green}{\texttt{(var }}x\color{green}{\texttt{)}} \\ S\left(x\notin C\right) &:= \color{green}{\texttt{(abs }} x\texttt{ }S(C\cup\{x\})\color{green}{\texttt{)}} \\ S\left(C\right) &:= \color{green}{\texttt{(app }} S(C)\texttt{ }S(C)\color{green}{\texttt{)}} \end{array} \$$

Any string spanned by the grammar is valid and any string not is invalid.

## Code

I've exhausted myself with the above. I will write to code in a bit when I've eaten and stuff.

## Scoring

This is so answers will be scored in bytes with the goal being a smaller score.

## Test cases

### Reject

(abs x (var x
uuuuuuuuu
)))(abs x (var x))
app (abs x (var x)) (abs x (var x))
(mmm hummus)
(abs x (var y))
(abs x (abs x (var x)))
(app (abs x (var x)) (var x))
(abs (var k) (var (vark k)))


### Accept

(abs x (var x))
(abs x (abs y (var x)))
(abs xx (app (var xx) (var xx)))
(app (abs ab (app (var ab) (var ab))) (abs ab (app (var ab) (var ab))))


## In need of title.

Note: In the final challenge $$\N\$$ will be a concrete number (I am thinking about 100), but while this is in the sandbox it is subject to change so I have left it as $$\N\$$.

This challenge is based off of a list of $$\N\$$ Castilian Spanish words and the words they originate from.

You are to write a program or function which takes the origin word as input and outputs as close as possible the Castilian derivative. Your program should be no longer than $$\N\$$ bytes.

## Scoring

To calculate your score run your program on every origin word and calculate the distance between your output and the correct answer. Your score is the sum of all these distances.

The distance here is a modified version of Levenshtein distance. It is the same as Levenshtein distance except replacement steps that add or remove a diacritic cost only 1/2 of a step as opposed to their normal 1.

You can use this code to calculate the distance between two strings.

The goal is to have as low a score as possible.

All of the origin words, spare 1, are Latin words (Late or Classical depending on the word). The one exception is ezkerra (the origin for izquierda) which is of Basque origin. It has been added as an extra curve-ball in case you can get all the others with a little space to spare.

Verbs are always in the infinitive form and nouns in the nominative singular.

The words are not chosen randomly but rather I have focused on choosing words that follow a number of simple rules. The list is also organized so that words that undergo similar transformations are grouped together. This is for your ease of use, nothing more.

# The list

faba, haba
facienda, hacienda
facere, hacer
fundus, hondo
profundus, profundo
fungus, hongo
fabulare, hablar
furnus, horno
ferrum, hierro
filus, hijo
filum, hilo
folia, hoja
fovea, hoyo
fagea, haya
fastidium, hastío
fastidiare, hastiar
afflare, hallar
formica, hormiga
fetere, heder
ficcare, hincar
factor, hechor
factum, hecho
octo, ocho
octavus, ochavo
noctu, noche
lacte, leche
iactare, echar
coctus, cocho
capere, caber
sapere, saber
lupus, lobo
lacrima, lágrima
lacuna, laguna
eruca, oruga
liber, libro
thema, tema
theatrum, teatro
thesaurus, tesoro
thesis, tesis
thorax, tórax
aether, éter
anthropologia, antropología
orthographia, ortografía
sapphirus, zafiro
philosophia, filosofía
echo, eco
chalare, callar
chamaeleon, camaleón
chaos, caos
materia, materia
resistentia, resistencia
aurum, oro
taurus, toro
autumnus, otoño
annus, año
scribere, escribir
scutum, escudo
scutella, escudilla
scriptor, escritor
ezkerra, izquierda

• I think it's interesting in that it should be near impossible to get a perfect score without built-ins. As a suggestion I'd remove the non-ASCII words, or at least normalise them, and perhaps not let $N$ be too high. Also, I wonder what the default cat program would be. – Jo King Mar 3 '20 at 12:31
• @JoKing I am looking to somewhat twart perfect scores, I feel there should always be some room for improvement, It just is a little hard to balance this with golfing-languages ability for expressiveness. I am interested to hear what ranges for $N$ you think are too high. I started out by avoiding any non-ASCII characters, but it was really hard to build up a representative corpus of words. Plus the accents and eñe really are a feature of the language. I may adjust the scoring so that i and í for example are only half away from each other so that the penalty is small. – Wheat Wizard Mar 3 '20 at 13:05
• Suggested title: Hispanize these words. Also mention that words should be in lowercase. Finally I think it makes more sense to restrict programs to $N$ characters rather than $N$ bytes. – SunnyMoon Nov 20 '20 at 15:24
• I'm not a fan of "Your program should be no longer than N bytes". I think a scoring rule which incorporates both the Levenshtein distance and the byte count would be better, as in the Moby Dick challenge: it would allow more languages to compete, and would allow for more creativity. – Robin Ryder Nov 22 '20 at 23:43
• @RobinRyder I think that metrics that combine two non-obviously related factors such as in the Moby Dick challenge or as you are suggested rarely work. In fact I can't even think of an example I feel is good. They simply require fine tuning that can only really be done in retrospect. I also don't know how this would allow more languages to compete and I certainly don't know how it would "allow for more creativity". If you have a specific metric in mind and a compelling reason why that metric would not be broken I would be happy to try it out and see. – Wheat Wizard Nov 23 '20 at 1:38
• Sorry, I'll expand: with a low, hard limit on the number of characters, non-golfing languages don't stand a chance (hence the "more languages" part). If instead you set a high hard limit, it will be possible to reach a (near) perfect score, with no incentive to golf or search for trade-offs (hence the "creativity" part). There surely exists a sweet spot for the character limit where neither of these issues arise, but (a) it will be hard to find and (b) it will be highly language-dependent. – Robin Ryder Nov 23 '20 at 7:53
• @RobinRyder I think that 100 characters is plenty of characters for nearly any language to implement something a bit more complex than cat (e.g. replace ^f with ^h). I also think that it would require quite a few characters any language to acheive a perfect score. More than half of the words have seemly random vowel mutations that are not covered by any general rule. The only way I can see a perfect score is a compression decompression method. It seems to me to write the de-compressor and make up for the loss would require a deal of room. – Wheat Wizard Nov 24 '20 at 15:56
• What I'm saying is that I think that sweet spot is actually very large. And I think that adding more dimensions to the problem only increase the risk of missing the sweet spot. – Wheat Wizard Nov 24 '20 at 15:57
• I'm not sure the modified version of the Levenshtein distance really adds something to the challenge, but it certainly makes it harder to score an answer. Would you consider updating your script so that it accepts the whole list of translations? – Arnauld Dec 2 '20 at 22:36
• Some possible typos (I'm a native Castillian Spanish speaker and I'm familiar with Latin): afflare, hallar; factor, factor; chalare, callar – Luis Mendo Dec 20 '20 at 18:00
• @LuisMendo hallar and chalare are definitely typos. But hechor was intentional. I suspect your hang up is that factor and hechor are doublets but factor is more similar to the Latin. There are plenty of words here for which the Latin is not a direct translation or the Spanish or vice versa (even factor is not). I chose to include hechor because it is a good example of some of the changes that I want to highlight, (f -> h and ct -> ch). – Wheat Wizard Dec 21 '20 at 23:26
• The thing is, I never heard hechor. But I just checked in the dictionary and it is included, albeit as an old form, not in current use – Luis Mendo Dec 21 '20 at 23:46

# Strobogrammatic Numbers

### Definition

A number which is rotationally symmetrical, i.e., it'll appear the same when rotated by 180 deg in the plane of your screen. The following figure illustrates it better,

(source: w3resource.com)

Given a number as the input, determine if it's strobogrammatic or not.

# Examples

• Truthy
1
8
0
69
96
69169
1001
666999
888888
101010101

• Falsey
2
3
4
5
7
666
969
1000
88881888
969696969


# Rules

• The number is guaranteed to be less than a billion.
• We are considering 1 in it's roman numeral format for the sake of the challenge.
• Input can be taken as number, or an array of chars, or as string.
• Output would be a truthy/falsey value.
• This is a , so fewest bytes will win!

# Meta

• Although I've tried a search, but is this a duplicate?
• Is the challenge's text clear enough?
• Any tricky/interesting test case?

# Explain a Code Golf Answer code-golfstring

## Background

When writing Code Golf answers, it is often a good idea to add an explanation of the code so the reader understands what's going on. For example, this this answer by @Makonede (abridged):

        θ  # last element of
Σ          # the input, sorted in increasing order by
1¢    # the number of ones of
%       # modulo
žJ        # 4294967296
b      # in binary


The full program is written on the first line, then a blank line, then on each successive line, a little snippet of the program, aligned using spaces with its position in the full program, and then some comments on the right-hand side explaining each part.

I, for one, find writing and aligning these explanations tedious, so let's outsource it to a program.

Given a program as a string, and a list of sets of pairs of start/end indices to form an inclusive range, output each sub-string defined by the indices on a new line, indented to its respective position in the whole string, with a # at the end of the line, padded so that there are two spaces before the # after the last sub-string, ready for the user to add their explanation.

## Rules

• You may use 0-based or 1-based indexing
• You are guaranteed to receive valid, non-overlapping ranges, which together cover the whole string
• You may assume the program string contains no newlines, tabs or other unprintable characters, and no double-width characters
• Standard I/O rules and loopholes apply
• This is , so shortest code in bytes wins

## Examples (1-based indexing)

Inputs: abcdwxyz, (1-8)
Output:

abcdwxyz  #


Inputs: abcdwxyz, (5-7), (1-2),(8-8), (3-4)
Output:

    wxy   #
ab     z  #
cd      #


Inputs: <<<$[grep -c wx$0-grep -c y\z $0];:<<'Q', (6-20), (22-37), (4-5),(38-38),(21-21), (1-3), (39-39), (40-40), (41-45)] Output:  grep -c wx$0                           #
grep -c y\z $0 #$[               -                ]         #
<<<                                            #
;        #
:       #
<<'Q'  #


# Meta

• Is this a duplicate?
• Is this clear enough?
• Any other feedback?
• Related – Razetime Dec 24 '20 at 10:32
• @Razetime I would say this is a dupe :-( – pxeger Dec 24 '20 at 13:35
• I'd say this is simpler and more suited for code golf because it functions without the need for a complex priority system. You may want to request more opinions on the nineteenth byte. – Razetime Dec 24 '20 at 17:51

# Interpret Interval Notation

• @Adám yes to ∪ and -ish characters. I also broadened the scope to all meaningful intervals, so ranges may overlap and [5,5] (all integers x where 5<=x<=5)is [5] but not [5,5) (all integers x where 5<=x<5) and (5,5) (all integers x where5<x<5) are undefined. – Aiden4 Dec 22 '20 at 21:07
• All integers x where 5<=x<5 would be [], no? – Adám Dec 22 '20 at 22:25
• I'd put all the undefined cases separately, or at least at the end. – Adám Dec 23 '20 at 0:09
• Typo: the [9,13] test case should either be [9,13) or 13 is missing from the output. – Dingus Dec 23 '20 at 2:35
• undefined cases should be undefined behavior instead. Otherwise, one need to handle it separately which feels bad. Otherwise, it's a good challenge :) – vrintle Dec 23 '20 at 11:22
• If you allow other symbols for the brackets, make sure to prohibit other phrases as that can be abused. – Adám Dec 23 '20 at 15:16
• @Adám what do you mean by phrases? – pxeger Dec 23 '20 at 16:06
• @pxeger Multi-character constructs. It'd allow solutions to require an input format that contained the necessary code such that the solution becomes an eval. – Adám Dec 23 '20 at 16:46
• Related – Razetime Dec 24 '20 at 10:44
• Is parsing a string necessary? Could you also allow other constructs (tuples with a marker to show if they're open or closed)? – user Dec 25 '20 at 21:56
• Just asking frankly, did you forgot to post this, or is something yet missing? – vrintle Jan 4 at 2:59
• @user I am going to say no to other constructs otherwise, it is basically a duplicate of the related challenge. – Aiden4 Jan 4 at 15:03
• @vrintle Something like that. I haven't really been active since just before Christmas. I'll probably post it this afternoon. – Aiden4 Jan 4 at 15:04

# Implement a zipwith function

• APL or J will win this with 2 bytes (that's the shortest possible score, right?) – Adám Jan 14 at 21:23
• Required tag: restricted-source – Adám Jan 14 at 21:24
• Why the builtin restriction? – Redwolf Programs Jan 14 at 21:45
• @RedwolfPrograms To avoid trivialising the challenge – caird coinheringaahing Jan 14 at 21:52
• @Adám 1) if those 2 bytes are a builtin, then no, otherwise, very possible. 2) Why [restricted-source]? – caird coinheringaahing Jan 14 at 21:52
• Any reason for banning that builtin in Haskell and Jelly? What's wrong with people submitting that as answer? They won't get upvoted much anyway. And it still lets people use builtins in other languages. – user Jan 14 at 22:14
• @cairdcoinheringaahing No, that'd be prohibited by your source restrictions rule on an exact built-in. Rather, it'd be a more general built-in (so not "exact") plus a parameter that makes the general built-in choose the required behaviour. – Adám Jan 15 at 3:21
• Allowing the built-in and seeing how many languages have it could be interesting in its own right. Or, generalize the problem to nzipwith, which takes an n-ary function and n sequences (and optionally the value n) and call the function for each n-tuple from the n sequences. – Bubbler Jan 15 at 6:10
• I've softened the builtin ban to simply encourage people to post a non-builtin answer as well. @Bubbler Possibly, but I think it'd be a good challenge to simply have the basic zipwith given that it's a fairly common functional programming construct – caird coinheringaahing Jan 15 at 14:39
• I think it's better to not ban them, and simply let builtin users wallow in their downvotes/shame so they don't do it again – pxeger Jan 16 at 19:45
• @pxeger I've removed the builtin ban, and changed it to encourage builtin-only answers to include a non-builtin version as well – caird coinheringaahing Jan 16 at 19:47
• Would taking input as two lazily evaluated iterators over the elements of the list or outputting an iterator over the results be acceptable – Aiden4 Jan 26 at 1:39
• @Aiden4 I think that taking lists as lazy iterators is an accepted I/O method, so yes – caird coinheringaahing Jan 26 at 9:11
• I find the former ban on Jelly's " interesting considering that there's no way to really pass it a function. – Unrelated String Jan 26 at 9:36

# Calculate the 'geothmetic meandian' of a set of numbers

Randall Munroe's March 10 xkcd comic "Geothmetic Meandian" defines the 'geothmetic meandian' of a set of positive real numbers as follows.

Define a function F, such that F accepts a set of n positive real numbers and returns the set (a, b, c), where a is the arithmetic mean of the set (the sum of the numbers in the set divided by n), b is the geometric mean of the set (the product of the numbers in the set to the power of 1/n), and c is the median of the set (the average of the middle two numbers in the sorted set when n is even, and the middle number in the set when n is odd). The function F can therefore be applied again to its own output. Iterating F an infinite number of times should cause its three outputs to converge to one value g. This value g is defined as the geothmetic meandian of the original set of positive reals. (For the purposes of this challenge, you may assume this value exists and does not diverge.)

Given a nonempty list of positive real numbers in any convenient and reasonable format and a positive integer q, compute its 'geothmetic meandian' to q significant figures. Standard rules apply, and the shortest code in bytes wins.

## Test cases

[[1], 2] --> 1.0
[[2, 8], 4] --> 4.742
[[1, 1, 2, 3, 5], 6] --> 2.08906
[[1, 2, 4, 8], 6] --> 3.13227
[[1.1, 2.2, 4.4, 8.8], 9] --> 3.44550208

• This seems like a decent challenge, but I don't know if the rounding requirement adds anything. – rak1507 Mar 11 at 2:40
• @rak1507 I was accounting for if different languages have different levels of floating-point precision, and also because the calculation needs to stop at some defined point. – Cloudy7 Mar 11 at 3:24
• The problem with taking the number of significant figures q as input is that you're banning the use of float and double numbers entirely (doubles will break at q >= 16 or so), which is a big no-no. You could take the number of iterations i instead and require the solutions to output the result of i-th iteration. – Bubbler Mar 12 at 5:05
• @Bubbler I envisioned part of the challenge to be determining when to stop the iteration of F. Should I then restrict q to be a positive integer from 1 to 7 or something similar? – Cloudy7 Mar 12 at 17:28
• Alternatively, we can have have a fixed number of iterations i and output the geothmetic meandian to the highest precision possible given i iterations. However, thinking about it, I agree this part of the challenge may be unfeasible. – Cloudy7 Mar 12 at 17:39
• Oh dear. I just tried another test case and due to floating-point errors in calculation, my program slowly drifts by 2e-12 indefinitely as F is iterated... – Cloudy7 Mar 12 at 17:49
• How about this: Given a value q (a positive floating-point number), stop iteration when the difference between the maximum and the minimum is less than q, and output any of the three numbers (or all of them). Allow the solutions to fail if q is too small compared to the input (i.e. it is outside the precision capability of the floating-point type in use). I think this is clearer to specify the error margin this way. – Bubbler Mar 15 at 3:46
• Or just require that all programs use a fixed q, e.g. 100? – pxeger Mar 20 at 17:53
• I feel like adding anything to do with the precision will just complicate things, and most of the code will be for handling that, not for actually answering the challenge. IMO it's fine to say 'until it converges', and leave specifics up to the challenge answerers. – rak1507 Mar 22 at 12:19

# Complete the landscape

Carcassonne is a tile-based game, where the objective is to construct Roads, Cities and Monasteries, in order to score points. The game works by players taking turns to draw and place tiles to construct a landscape, then claiming roads, cities and monasteries. An example landscape is:

There are $$\19\$$ distinct tiles (ignoring rotations), each of which contains at least one feature (Road, City or Monastery):

Also, notice that the landscape must be consistent. This means that roads must connect to other roads, city edges must connect to other city edges and fields must connect to fields. Therefore, these tiles are inconsistent:

To avoid this challenge being about image processing, we can translate each tile into a list containing $$\5\$$ values, according to this legend:

[North edge, East edge, South edge, West Edge, # of cities]

0: Field
2: City


For instance, this tile can be described as [2, 0, 1, 1, 1]. Using this legend, we can describe each tile uniquely, and it's rotations are rotations of the first four elements. The entire grid can be described as a rectangular matrix, with a $$\20^\text{th}\$$ distinct value for an empty square. Translating the first landscape into this format, we get:

[
[             [],              [], [1, 1, 0, 0, 0], [1, 1, 2, 1, 1], [0, 1, 0, 1, 0],              [],              []],
[[1, 0, 1, 0, 0],              [], [0, 0, 0, 0, 0], [2, 0, 2, 0, 2],              [], [0, 2, 2, 2, 1], [0, 0, 0, 2, 1]],
[[1, 1, 0, 1, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], [2, 2, 0, 0, 1], [2, 2, 0, 2, 1], [2, 0, 0, 2, 1],              []]
]


using [] to represent an empty square. The complete list of tiles (ignoring rotations) in the same grid as the second image is

[1, 0, 1, 0, 0] [0, 0, 1, 1, 0] [2, 1, 1, 1, 1] [0, 1, 1, 1, 0] [2, 0, 0, 0, 1]
[2, 2, 0, 2, 1] [0, 0, 0, 0, 0] [2, 2, 2, 2, 1] [2, 2, 0, 0, 1] [2, 1, 1, 2, 1]
[2, 2, 0, 0, 2] [0, 0, 1, 0, 0] [2, 0, 1, 1, 1] [2, 1, 1, 0, 1] [0, 2, 0, 2, 1]
[1, 1, 1, 1, 0] [2, 1, 0, 1, 1] [2, 2, 1, 2, 1] [2, 0, 2, 0, 2]


Your task is to take in a rectangular matrix where every element save one is one of the 19 tiles given above or one of their rotations. Tiles can appear more than once, and not every tile will appear in every input. This landscape will be consistent, as defined above. You should take in this input and output the tile that could fill the empty space in the array, keeping the landscape consistent, as defined above.

As the number of cities on a tile is redundant for this task, you may choose instead to only work with 17 tiles (as 2 tiles are duplicated when ignoring cities) and take input as lists in the form [N, E, S, W] instead.

If there are multiple tiles that would work, you may output either all of them or just one. If no such tile exists, you may produce any output/result that could not be construed as a tile (i.e. it's not in the 19 tiles specified above, nor in any of their rotations). The representation of the "empty space" in the input may be your choice, so long as its consistent, and (although I'm not sure why you would) it isn't one of the 19 tiles above or their rotations, and there will only ever be a single empty space.

This is , so the shortest code in bytes wins.

# Meta

• Is this clear enough?
• More specifically, is the definition of a "consistent landscape" objective and understandable?
• This is a somewhat related question, but I believe there are enough differences between the two for them to not be duplicates. Thoughts?
• Tags are , , , . Any suggestions?
• Any further feedback?
• @Beefster Aside from involving tiling, I'm not quire sure how that challenge is related, let alone a possible duplicate – caird coinheringaahing Sep 28 '20 at 22:00
• Filling Carcassonne tiles in a grid can be thought of as a specific case of wang tiles with a different set of tiles, but upon closer inspection, seeing as your challenge is to complete the landscape, rather than fill a grid from nothing, this is actually a pretty different challenge. – Beefster Sep 28 '20 at 22:03
• Related – Beefster Sep 28 '20 at 22:04
• Does the 5th field, the # of citys, add anything? Makes it more cumbersome to store/rotate the tiles. Though it's understandable if you want to keep true to Carcassonne. – xash Mar 17 at 19:21
• @xash Yes, without the number of cities, some tiles (e.g. [2,2,0,0,1] and [2,2,0,0,2]) have the same representation as an array – caird coinheringaahing Mar 17 at 19:22
• @xash As "there will only ever be a single empty space.", "the empty space" makes more sense, as it refers to the only empty space in the input – caird coinheringaahing Mar 17 at 19:26
• Ah! I thought "The "empty space" in the input may be your choice" refers to which empty space to choose to fill, not the representation. Sorry, haven't slept well, makes perfect sense. :-) – xash Mar 17 at 19:29
• While I agree that to match Carcassonne, the number of cities field is useful for disambiguating two different tiles, it would never affect whether a tile fits into the space or not, so for this challenge it seems redundant. – Nick Kennedy Mar 20 at 7:42
• Will the 19 possible tiles be supplied as an input or do they need to be encoded into the answer? – Nick Kennedy Mar 20 at 7:46
• @NickKennedy Good point, I didn't realise that. I've added in a note about the redundancy of the city count. No, the tiles will not be provided as input, so the answer will need to implement some way of encoding them – caird coinheringaahing Mar 21 at 11:52

# Hide a message in ASCII art and an image

(needs cooler title)

# Robbers

• How the heck?! I was just drafting a challenge about stenography and images yesterday and then I see this.. – Redwolf Programs Mar 26 at 16:28
• @RedwolfPrograms was your idea the exact same as mine? – Beefster Mar 26 at 16:35
• Not identical, there was no ASCII art included, but considering there are only 5 steganography questions on the whole site that's an insane coincidence – Redwolf Programs Mar 26 at 17:03
• If the robber doesn’t know any of the messages, it might be hard to verify any potential explanation. It might be more fun and easier to verify a correct solution if the cop posts N codes and the solutions to N-1 of them, and the robber has to use those to reverse engineer the method and decode the last one. Alternately, the cop could have to pick from a list of pre-selected messages so the robber has some idea what to look for. – water_ghosts Mar 26 at 17:33
• Do the ascii+png files have to contain all the information necessary for decoding? For example, could I use a book cipher where the PNG encodes word numbers, and you then have to look up the corresponding words from The Great Gatsby? – water_ghosts Mar 26 at 18:03
• @water_ghosts I think a book cipher should only be allowed if you provide a link to the book. All data needed to decode aside from the image and ascii art should be present in the post and be constant across all encodings. – Beefster Mar 29 at 18:43
• This is amazing! You, dear sir/ma'am, get an upvote – StackMeter Apr 3 at 17:05

# Determine Circles

• Nice idea, but could you make it clearer what do you mean by cross? A test case would be good. – math Apr 6 at 7:04
• @math intersect or some concept like that. Can you give some better wording if you can understand what I mean? I can't find any word that suit line go over dot – okie Apr 6 at 7:09
• Maybe: 1, 2, 3 points will need 1 circle only to be sure that the points touch the circles boundary? Is that what you mean? – math Apr 6 at 7:17
• Some testcases are definitely needed, like five points on one circle and three points on another. Also, are the coordinates integers or real numbers? – Bubbler Apr 6 at 8:15
• @Bubbler Real number I think – okie Apr 6 at 8:17
• @okie Then you need to explicitly write it down, and add some testcases with non-integer coordinates. – Bubbler Apr 6 at 8:21
• In this problem, the answer does not change continuously with small perturbations of the input coordinates. Is it allowed to output the wrong answer due to floating point errors? For instance, if the input coordinates were (0,0),(0.3,0.3),(1,1) then the output should be 2. However, if the second point were instead (0.3,0.300...00001) then the answer should be 1. Given that floating point types are usually unable to tell these two cases apart, are we allowed to output either 1 or 2? – Delfad0r Apr 6 at 16:01
• @Delfad0r Thanks for your help. To solve such problem (float precision), I decided to add a limit to float so that precision are not extreme. – okie Apr 7 at 0:15
• Another possible approach (which I personally prefer, but the choice is entirely up to you) could be to only have integer coordinates as input, and then ask for an exact solution. If I am not mistaken, this problem should be solvable without resorting to square roots and similar, and therefore without any possibility of floating point errors. – Delfad0r Apr 7 at 12:30
• @Delfad0r But it's like a float *100 0.03*100 = 30 which just get every number bigger? – okie Apr 7 at 23:38
• @okie Yes, but the difference is that computations with integers are exact, while computations with floats are not. It shouldn't matter too much however, do whatever you prefer :) – Delfad0r Apr 7 at 23:43
• @Delfad0r I think I would take Integer, Thanks! – okie Apr 8 at 0:04

# posted lol

• Another suggestion it can be kolmogorov complexity challe ge too, if someone downloads tags and compresses the text – Wasif Apr 12 at 5:31
• @Wasif it's better as an internet challenge because a new tag might be created after challenge posting making the list invalid. – lyxal Apr 12 at 5:31
• Should the list include the synonym tags, i.e. the tags that are listed as being on no questions in the tag listing? – caird coinheringaahing Apr 12 at 13:30
• @cairdcoinheringaahing if it is listed on the tags page, then it needs to be included – lyxal Apr 12 at 22:54
• What is the 43 for in example program? – tsh Apr 14 at 3:18
• @tsh 43 is the number of occurrences of tag when you try and access a page of tags that doesn't exist – lyxal Apr 14 at 3:19
• Rule is still too wide, everyone can upload code to codegolf.stackexchange.com – l4m2 Apr 15 at 4:19
• @l4m2 if people include all the tags in a post, then they will have to a) keep it constantly updated (which wouldn't be viewed favourably by the community) and b) withstand potential downvotes for loop holing on both the answer to this and the answer that has the tags – lyxal Apr 15 at 4:45

# Implement an Over function

• Can we take $a$ and $b$ as [a,b]? In effect, this would make the challenge a $g$ reduction of $f$ mapped over that input list. – Adám Apr 19 at 21:12
• @Adám I think it would be unfair (and potentially unobservable) to ban languages from taking it as [a,b], and doing so would likely just create solutions in the form pair input; map f; reduce g – caird coinheringaahing Apr 19 at 21:41

# Rob the King: Hexagonal Mazes

Consider the following hexagonal maze:

     E . \ . . .
. . . \ . \ .
. . . . \ . \ .
_ _ _ _ . \ . \ .
. / . . . . . . | .
. | . . _ _ _ _ / . .
. \ . \ . . . / . .
. \ . \ . . / . .
. \ . \ . . . .
. \ . \ / . .
. \ . | . X


E represents the entrance, X the exit. |_/\ are walls and . are free spaces. In order to navigate from E to X, we can move to any free space in the up to 6 immediately surrounding spaces. The path from E to X, marked with P is:

     E P \ P P P
. . P \ P \ P
. . . P \ P \ P
_ _ _ _ P \ P \ P
. / . . . P P P | P
. | . . _ _ _ _ / . P
. \ . \ . . . / . P
. \ . \ . . / . P
. \ . \ . . . P
. \ . \ / . P
. \ . | . X


This isn't the only path, but the others are trivial variations on it.

# Cops

You are to write a function in Python 3 which takes a positive integer $$\n \ge 2\$$ and returns a hexagonal maze of side-length $$\n\$$, as shown above. The maze will meet the following criteria:

• The only characters in the output are EX.|_\/, space and newline
• The hexagon is shown as a hexagon. That means:
• The first $$\n\$$ lines will have one more non-space character than the previous line (the first has $$\n\$$ non-space characters), separated by a single space, and offset from adjacent lines
• The first $$\n\$$ lines have one fewer leading space than the previous line (the first line has $$\n - 1\$$ leading spaces)
• The next $$\n - 1\$$ lines have one more leading space than the previous line
• The next $$\n - 1\$$ lines will have one fewer non-space character than the previous line, separated by a single space, and offset from adjacent lines
• Lines may not have trailing whitespace
• The E is the first non-space character on the first line, and the X is the last non-space character on the last line
• There is at least 1 valid path that connects the E and the X, only moving from one free space to an adjacent free space.

How your program generates these mazes is entirely up to you. It could randomly places walls in the grid, ensuring there is always at least one path left, or it could only block the center row except for one gap, or anything else.

You may return either a multi-line string, or a list of lines. Lines should have appropriate space padding at the start, and may have a consistent amount of trailing spaces. "Consistent" here means either the same number on each line, or padding each line to the same length.

The Robbers will be writing maze-solving programs that try to solve your mazes, so you should aim to generate mazes that are somewhat difficult to solve.

This is not , you are under no obligation to golf your submission.

Additionally, you may submit multiple submissions. You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

Empty mazes of sizes $$\n = 2, 3, 4, 5, 6\$$:

                                                                 E . . . . .
E . . . .            . . . . . . .
E . . .          . . . . . .          . . . . . . . .
E . .        . . . . .        . . . . . . .        . . . . . . . . .
E .      . . . .      . . . . . .      . . . . . . . .      . . . . . . . . . .
. . .    . . . . .    . . . . . . .    . . . . . . . . .    . . . . . . . . . . .
. X      . . . .      . . . . . .      . . . . . . . .      . . . . . . . . . .
. . X        . . . . .        . . . . . . .        . . . . . . . . .
. . . X          . . . . . .          . . . . . . . .
. . . . X            . . . . . . .
. . . . . X


# Robbers

You are to write a Python 3 function that takes in the return value of a cop's answer. It may also take the number of sides, $$\n\$$, as an argument if you so wish. The input will only contain EX_|/\. and space, and newlines if inputting as a multiline string. It will either be a multiline string or a list of lines. Your function should handle both.

Your function should then output the maze with any valid path connecting the E and X using only connected free spaces. You may show the path with any character aside from EX_|/\., space or newline.

This is not , you are under no obligation to golf your submission.

Additionally, you may submit multiple submissions. You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

## Scoring

The scoring will take the form of a round-robin, similar to challenges. Every cop will be paired up with every robber, and the following will happen with each pair:

• The controller will call the cop's function 5 times with $$\n = 2\$$ as an argument, saving each of the 5 mazes. The cop will have 1 minute to produce each maze
• It will then pass each maze to the robber to solve. The robber will have 1 minute per maze to produce a correct output.
• If all 5 mazes are correctly solved by the robber within 1 minute each, the controller goes again, but with $$\n = 3\$$, and so on, increasing the $$\n\$$ by one, until either:
• The robber fails to solve a maze within 1 minute
• The robber produces an incorrect solution to an input maze
• The cop fails to return a maze within 1 minute
• The cop returns a maze with no path

At this point, both the cop and the robber receive points equal to the highest $$\n\$$ that neither of them failed. If the cop failed, the robber receives an additional point, and if the robber failed, the cop receives an additional point instead.

If both the cop and the robber reach $$\n = 50\$$ without failing, they both receive $$\50\$$ points.

After all pairs have be run, the cop and robber with the most points are the respective winners

# Meta

• If you want to automate the scoring process, you might want to restrict the I/O further, e.g. only allow stdin/stdout as a hexagon-shaped multi-line string. (I'm suggesting stdio because I assume you want to allow different languages.) Looks interesting, though I have a slight feeling that a full Dijkstra impl in C will almost surely win as a robber. – Bubbler Apr 12 at 23:01
• @Bubbler Good point, I've updated the I/O to be stricter. – caird coinheringaahing Apr 12 at 23:22
• @Bubbler I've decided to limit it to Python 3 functions, as I was struggling to make a controller that would allow any language to compete – caird coinheringaahing Apr 23 at 15:49
• It's a minor thing, but maybe change E and X to A and B? It seems more logical that way – pxeger Apr 24 at 15:52
• @pxeger I chose E and X as "entrance" and "exit" respectively, but I doubt it'll affect any solutions as opposed to A/B – caird coinheringaahing Apr 24 at 16:06

## Death-onacci sequence (WIP)

The traditional Fibonacci sequence grows forever:

0 1 1 2 3 5 8 13 21 ... 1,346,269 ...


and is given by this formula:

f(n) = f(n-1) + f(n-2)


where the initial numbers in the sequence are 0, 1.

However, there's a set of as-yet unnamed sequences, where a previous number 'dies' and is removed from the total.

For instance the sequence for the 5th death-onacci (m = 5) is given by

f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) - f(n-5)


And the first m-1 numbers is 0, followed by a single 1 (so for m=5 the sequence start 0 0 0 0 1)

Test cases:

Here are some test cases:

n f(n), m=3 f(n), m=4 f(n), m=5
0 0 0 0
1 0 0 0
2 1 0 0
3 1 1 0
4 2 1 1
5 2 2 1
6 3 4 2
7 3 6 4
8 4 11 8
9 4 19 14
10 5 32 27
11 5 56 51
12 6 96 96
13 6 165 180
14 7 285 340
15 7 490 640
16 8 844 1205
17 8 1454 2269
18 9 2503 4274
19 9 4311 8048
20 10 7424 15156
21 10 12784 28542
22 11 22016 53751
23 11 37913 101223
24 12 65289 190624
25 12 112434 358984
26 13 193620 676040
27 13 333430 1273120
28 14 574195 2397545
29 14 988811 4515065
30 15 1702816 8502786
31 15 2932392 16012476

You must write a function or program that takes one number M, and prints out the first 31 M-Death-onacci numbers. M will be a whole number larger than 0 and less than 31. The output can be in any human readable format, and you can take input in any reasonable manner. (Command line arguments, function arguments, STDIN, etc.)

As usual, this is Code-golf, so standard loopholes apply and the shortest answer in bytes wins!

• Very similar. – Razetime Apr 24 at 9:57
• @Razetime definitely, but hopefully different enough? – Pureferret Apr 24 at 10:02
• Well, it's a WIP. You can go ahead and add more details which distinguish it. 'tis the sandbox, after all. – Razetime Apr 24 at 10:04
• @Razetime how's it looking now? – Pureferret Apr 24 at 10:23
• looks better, and the tests are more comprehensive. I suggest posting in TNB for other people's feedback. – Razetime Apr 24 at 11:11
• taking P as a fraction seems fine, but it seems more convenient separately since we're just supposed to increment N and P till the desired ratio is achieved. What is the allowance for floating point errors on this question? – Razetime Apr 24 at 10:07
• an additional "Streak bonus" for every x games might be an interesting addition. – Razetime Apr 24 at 10:08
• @Razetime Oh did I say fraction, I meant a decimal value between 0 and 1, eg: 0.53 for 53%. There wont be more than two decimal places in the input so I doubt if any language will run into floating point errors at all. – Manish Kundu Apr 24 at 10:11
• I updated the question to allow P as decimal. About the streak bonus, I think it might complicate things quite a bit so I am not going with that. – Manish Kundu Apr 24 at 10:21
• You should clarify in the text if the inputs W, N can be taken separately or only as one number corresponding to W/N. And if so, please address Razetime's comment on floating point errors – Luis Mendo Apr 24 at 15:17
• @LuisMendo Yes, taking them separately is fine. I updated the post again, please check if it is clear now. – Manish Kundu Apr 24 at 15:47
• I'd suggest also allowing languages to take P as a fraction. Other than that, this looks good to go – caird coinheringaahing Apr 24 at 16:09
• I think they have to be taken separately. In the first example, if you take W/N as 0.2 you cannot compute the output, because you don't know if W=1, N=5, or W=2,N=10, or... – Luis Mendo Apr 24 at 17:32
• Oh yes, you're right about that. You'd have to consider both the values to calculate the answer. – Manish Kundu Apr 24 at 19:01
• @LuisMendo But if it somehow benefits you to take it say as a string of the form "W/N" with the original values of W and N, then that's fine too. I think the rules clarify that point. – Manish Kundu Apr 24 at 19:16

# Implement Minceraft

• Is the use of special char (!,,,:, etc) allowed? – okie Apr 13 at 6:29
• "You can only use up to three of the letters from the string "minecraft"". If I choose i, c, and e (as the example discussed). Is this means "I can only use iîïíīįìIÎÏÏĪĮÌcçćčCÇĆČeèéêëēėęEÈÉEÊËĒĖĘ and none of other characters." or "I cannot use mMnñńNÑŃrRaàáâäæãåāAÀÁÂÄÆÃÅĀfFtT but I can still use bcdeghijkl..." – tsh Apr 13 at 7:29
• @tsh Sorry, I worded it confusingly. The second case. – A username Apr 13 at 8:25
• @okie All characters that aren't some variant of minecraft can be used. – A username Apr 13 at 8:28
• I don't feel like the restricted-source adds much to be honest, it just boils down to a "do X without X" challenge. On its own the task is quite interesting because of how it swaps letters randomly, which I think creates room for some interesting golfs – pxeger Apr 13 at 8:48
• @pxeger Ok. Changing. – A username Apr 13 at 9:04
• Suggested tags: remove restricted-source, add random. – Bubbler Apr 13 at 9:45
• @Bubbler Oops, forgot to get rid of the tag. – A username Apr 13 at 9:47

# Generate all solvable 2xN mazes

• Note that the sequence is equal to A001333 and has very simple recurrence a(n+2) = 2a(n+1) + a(n), which makes the challenge a near-dupe of Fibonacci. – Bubbler Apr 26 at 4:31
• @Bubbler Didn't notice that. Should I still post this? Also, why does the recurrence happen like that? – A username Apr 26 at 5:25
• I don't have a strong opinion about posting it or not. It's worth asking in chat before posting to main though. The recurrence can be derived from a case analysis on the state of the last column, as "both cells are open" and "only one cell is open". – Bubbler Apr 26 at 5:35
• what is one end to the other? can you clarify – qwr Apr 26 at 21:27
• @qwr Basically, that there exists a path of empty cells which can be traced from the left side of the maze to the right side. – A username Apr 26 at 21:29
• I've modified the challenge because it was a close dupe. – A username Apr 26 at 23:02
• Since it involves output of the mazes now, you'll need to specify how they can be output(2D array, string, ascii art). I recommend keeping it flexible. – Razetime Apr 27 at 2:33
• @Razetime True. – A username Apr 27 at 4:19

# Drawing the Stack Overflow logo

• I don't think restricting the language is a good idea. Move languages promotes diversity among submissions. However, I'm still new to the site so I'm not really sure. – EnderShadow8 Apr 30 at 4:32
• Like Ender said, language-specific challenges are strongly discouraged - here, it doesn't add anything, so removing the restriction would improve the challenge by allowing a wider variety of approaches and solutions. – hyper-neutrino Apr 30 at 4:34
• Also, seeing as to how this is a ascii-art challenge, you will need to either provide the exact text that needs to be outputted or a formal specification of what is considered valid output and what isn't - for example, could I just submit . and claim it's a very zoomed out logo? These will need to be clarified. Overall, I like the idea though. – hyper-neutrino Apr 30 at 4:35
• I think if you require the output to be the exact example you gave it would make it much easier to determine which answers are valid. – Redwolf Programs Apr 30 at 5:15
• @RedwolfPrograms It's the best I got, but I'll make it official. – Matt Sanchez Apr 30 at 5:20
• This challenge looks pretty good now, so I've upvoted, although I'd still recommend waiting a day or two just in case anyone else has feedback on the formatting or finds something unclear. – Redwolf Programs Apr 30 at 5:28
• A tip for future challenges: Anyone (not just you) reading the challenge and an answer should be able to decide (without disagreement) if the answer is valid or not. "Resembles a logo" is very subjective in this sense, and phrases like "as close as" should be avoided too. – Bubbler Apr 30 at 5:34
• @Bubbler Is this better? – Matt Sanchez Apr 30 at 6:10
• Yeah, it's better. A question: would you allow printing trailing spaces at the end of each line, or printing a trailing newline at the end? (These are commonly allowed because they don't impact the ascii art shown and they're hard to avoid in multiple languages) – Bubbler Apr 30 at 6:21
• @Bubbler I added a list of questions that are asked in the comments. Can I add the same if I posted this on main? – Matt Sanchez Apr 30 at 7:39
• I'd recommend to edit the challenge text directly to include any clarifications. – Bubbler Apr 30 at 7:45
• @Bubbler It will do and I'm hoping that when this gets published, I gain enough reputation just to talk in chat. – Matt Sanchez Apr 30 at 7:50
• Tags-wise: [kolmogorov-complexity]. I'd suggest just removing the 2 paragraphs beneath the output, as they just make it more confusing. A simple "output this exact text, with an optional trailing newline. Lines may have optional trailing spaces. Shortest code wins" is enough (plus the output itself) – caird coinheringaahing Apr 30 at 17:35
• I've edited this down to a stub now that it's been posted to save space – caird coinheringaahing May 1 at 13:46

# Time bomb KoTH

• Enforcing determinism prevents luck based winning, which I personally like. Adds a sense of balance. – Razetime May 1 at 15:59
• Determinism also means anyone can run a simulation of the game on their own machine. The game then devolves into aggressive metagaming and iteratively updating one's bots to always beat the opponents'. If you decide to enforce determinism among the bots, you must have some outside source of randomness to prevent players from simply simulating the entire game and instead actually formulate a strategy that is robust enough to still work well in the face of unknowns. – EnderShadow8 May 2 at 9:57
• I personally like a bit of non determinism to spice things up but then this came along. So you have to be careful. – EnderShadow8 May 2 at 9:58
• @EnderShadow8 yeah I saw that answer. In the current design, the array for the numbers selected in the previous round will be initialized with random numbers on the first round, giving the initial seed of randomness – leo3065 May 2 at 15:36
• Another thing to consider: high numbers will have very small winning chances, and the entire game is biased towards low numbers (they come first, they don't subtract much, large numbers take many points on explosion vs large numbers give many points on success). So all "smart" bots will choose <= n / 2 numbers, but then the trigger will also be lower, so bots have to choose even lower numbers. That can lead to a case of positive feedback. It may or may not cause problems, but it may be good to keep that in mind. – FZs May 2 at 19:24
• And to the determinism topic: a viable compromise between determinism and randomness could be made: making the only allowed non-deterministic part a seeded PRNG function provided by the controller. The PRNG seeds used for the official ranking are kept secret, but it's still possible to replicate the given match by using the same seed. – FZs May 2 at 19:58
• @FZs That's true. I may need to buff the reward for larger numbers to encourage playing them. Also about the determinism topic, after some searching I found some method to provide a seeded random, and I think I'm going to try that. – leo3065 May 3 at 7:41
• More about the determinism: I decided to decide the secret seed before the challenge starts and provide the hash to prove that I won't change the key mid-challenge. – leo3065 May 3 at 9:14
• I've edited this down to a stub now that it's been posted to save space – caird coinheringaahing May 3 at 14:17

# Swap encoding iteration count

• Implement the naive algorithm, so no math solution is allowed(if there exists one)? – okie Apr 28 at 2:44
• @okie Sorry for the confusion, I meant time yours against the naive algorithm. – A username Apr 29 at 4:48
• Scoring is usually done against your benchmark ultimately by you on your machine. Having people calculate their own score against their own benchmark could be a bit of disaster. What's to stop people accidently making their benchmark perform extremely poorly? – Noodle9 May 1 at 22:05
• @Noodle9 True, will change that. – A username May 1 at 22:08
• I think this could be more easily scored by algorithmic complexity rather than time on your machine. It would be unambiguous, since it is not vulnerable to variance between separate runs, and answerers would be able to score their own answers without your machine. – Wheat Wizard May 3 at 9:05
• @WheatWizard How would algorithmic complexity work for this? Return value or time duration is by no means proportional to the input size. It's a very complex problem and we still haven't figured out any general-purpose formula. – A username May 3 at 9:12
• Return value (and thus time in the naive approach) is definitely related to the input size in the worst case, which is generally what asymptotic complexity cares about. Just to see this with one character the most you can get is 0, with 2 and 3 it is still 0, with 4 it is 2, with 5 it is at least 3 etc. You can always find a string of length n that takes 0 steps, but the more characters long the input is the more opportunity there is for complexity. – Wheat Wizard May 3 at 9:20
• @WheatWizard The question is now, related how? With 5 it is 3, with 6 it is 4, with 7 it is 6, with 8 it is 12. My brute-force algorithm almost crashed TIO trying to prove that the most you can get with 9 is 38, for any pattern of the form 012031231. So it's obviously related, but how does this work, and where did 38 of all numbers come from? – A username May 3 at 9:46
• That does require a bit of math. If you would like it is totally possible to talk about time complexity relative to the solution. So the naïve solution would be O(nmm) where n is the number of steps and m is the size of the input, that would probably involve less math, however you still want to consider how to rank scores on two variables. (My guess would be first by n complexity, then by m complexity). – Wheat Wizard May 3 at 9:55
• Just for fun: I also made a brute forcer and got the maximums for up to 12 on TIO. 9 is 38, 10 is 117, 11 is 234, 12 is 650. – Wheat Wizard May 3 at 10:15
• @WheatWizard On TIO? My program's still stuck on 10, on my laptop. Anyway, the series 3,4,6,12,38,117,234,650 doesn't really make any sense, aside from 234 being double 117. So n-values would probably be quite inconstent. – A username May 3 at 10:19
• @WheatWizard Also, can I see your brute-forcer? – A username May 3 at 10:20
• – Wheat Wizard May 3 at 10:24

# Count up to 21

21 is a game my teachers had my classmates and I play in order to kill some time. The game works as follows:

• All contestants stand in a circle. The aim is to count to 21, one by one.
• At any time, any player may begin the counting by saying 1.
• The plays then continue the counting by saying the next number. However, if multiple players say the number at the same time, the count resets, and someone has to say 1 again.
• The first player who says 21 is "out", and the game begins again with the same contestants except for the "out" player(s)
• The final player left is disqualified, and the entire game begins again. The last player not disqualified wins.

We are going to run a challenge, where bots aim to play this game.

You are to write a function in Python 3 that takes a list of lists $$\L\$$ as argument. Each list in $$\L\$$ represents a round in the game, with the last element being the most recent. The $$\i\$$th element of each list always corresponds to the same bot. Each list in $$\L\$$ will contain $$\n\$$ integers between $$\0\$$ and $$\21\$$, where $$\n\$$ is the number of contestants left in the game. The lists are either all $$\0\$$s, or are $$\n-1\$$ $$\0\$$s and a single non-zero value $$\v\$$.

If a list is all $$\0\$$s, either it is the first round, or the counter was reset in the previous round.

That function should then return either:

• $$\0\$$, meaning that your bot stays quiet
• $$\v+1\$$, meaning that your bot is attempting to guess this round

And that's it!

The competition will work exactly as described above. The controller will run 100 games. Each game will works as follows:

• The first round begins with all $$\n\$$ contestants. They will count up to 21, eliminating each contestant as they count to 21, and resetting the count to 0. The final player left is then eliminated, and the next round with $$\n-1\$$ contestants is run. At the end, the final player left standing wins
• The player with the most wins after 100 games wins overall

You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

If any game has more than 10000 rounds, it'll be terminated and no player will win.

## Example bot

This is Random:

import random

def bot(history):
return random.choice([0, max(history[-1]) + 1])

• Infinite loops might happen quite often – Redwolf Programs Apr 28 at 1:51
• @RedwolfPrograms Put a limit of 10000 rounds per game – caird coinheringaahing Apr 28 at 20:32
• TNB Feedback link – caird coinheringaahing Apr 28 at 21:16
• So, if next number is 21: Is there any reason a bot will not to say 21 in that round? – tsh Apr 29 at 1:30
• I feel like someone's going to just add a bot to say every single number no matter what. – A username Apr 29 at 10:54
• @tsh If multiple bots say 21, none of them win and the count resets – caird coinheringaahing Apr 29 at 11:51
• Can you post the code to run the game so we can test our bots? – fasterthanlight Apr 29 at 21:05
• @fasterthanlight I haven't written the controller yet, so no – caird coinheringaahing Apr 29 at 22:57
• but if i will lost their turn if i dont say 21, and the worst case is a tie if I say 21? So any reason I try to be silent? – tsh Apr 30 at 5:10
• Because there's no reason to not say 21, infinite loops are probably going to occur no matter what. You might want to consider adding a rule regarding this to prevent infinite loops (or if everyone but 1 says a number the bot who said 0 can be eliminated) – fasterthanlight Apr 30 at 12:44
• Just wondering, is saving state between different turns allowed? Or between rounds? Or between games? You also don't seem to distinguish between rounds and turns (i.e times when the count resets vs. opportunities to guess), which may cause confusion. Also, a suggestion: Maybe let each game have only a small subset of the bots as contestants, so that if there's that one bot who always says 21 as soon as possible, it would just harm itself rather than ruining the challenge. (Sorry for this long block of text.) – Andrew Li May 4 at 3:42

## Challenge Statement

The goal of this challenge is to build the 5 state Infinite Time Turing machine that takes the longest to halt.

The rest of this challenge is some definitions and an example to help you.

## Turing Machines

For clarity we will define the Turing machines as used for this problem. This is going to be rather formal. If you are familiar with Turing machines this is a single-tape, binary Turing machine, without an explicit halt state, and with the possibility of a no shift move. But for the sake of absolute clarity here is how we will define a classical Turing machine and its execution:

A Turing machine consists of a $$\3\$$-Tuple containing the following:

• $$\Q\$$: A finite non-empty set of states.
• $$\q_s : Q\$$: The initial state.
• $$\\delta : Q\times \{0,1\} \nrightarrow Q\times \{0,1\}\times\{1, 0, -1\}\$$: A partial transition function, which maps a state and a binary symbol, to a state, a binary symbol and a direction (left, right or no movement).

During execution of a specific Turing machine the machine has a condition which is a $$\3\$$-Tuple of the following:

• $$\\xi_\alpha : \mathbb{Z}\rightarrow \{0,1\}\$$: The tape represented by a function from an integer to a binary symbol.
• $$\k_\alpha :\mathbb{Z}\$$: The location of the read head.
• $$\q_\alpha : Q\$$: The current state.

For a Turing machine the transition function takes the condition of a machine at step $$\\alpha\$$ and tells us the state of the machine at step $$\\alpha + 1\$$. This is done using the transition function $$\\delta\$$. We call the function $$\\delta\$$ with the current state and the symbol under the read head:

$$\ \delta\left(q_\alpha, \xi_\alpha\left(k_\alpha\right)\right) \$$

If this does not yield a result, then we consider the machine to have halted at step $$\\alpha\$$, and the condition remains the same. If it does yield a result $$\\left(q_\delta, s_\delta, m_\delta\right)\$$ then the new state at $$\\alpha+1\$$ is as follows:

• $$\\xi_{\alpha+1}(k) = \begin{cases}s_\delta & k = k_\alpha \\ \xi_\alpha(k) & k \neq k_\alpha\end{cases}\$$ (That is the tape replaces the symbol at the read head with the symbol given by $$\\delta\$$)
• $$\k_{\alpha+1} = k_\alpha+m_\delta\$$ (That is the read head moves left right or not at all)
• $$\q_{\alpha+1} = q_\delta\$$ (That is the new state is the state given by $$\\delta\$$)

Additionally we define the condition of the machine at time $$\0\$$.

• $$\\xi_0(k)=0\$$ (Tape is all zeros to start)
• $$\k_0=0\$$ (Read head starts a zero)
• $$\q_0=q_s\$$ (Start in the initial state)

And thus by induction the state of a Turing machine is defined for all steps corresponding to a natural number.

## Infinite Ordinals

In this section I will introduce the concept of transfinite ordinals in a somewhat informal context. If you would like to look up a more formal definition this explanation is based of of the Von Neumann definition of ordinals.

In most contexts when talking about the order of events we use natural numbers. We can assign numbers to events such that events with smaller numbers happen earlier. However in this challenge we will care about events that happen after an infinite number of prior events, and for this natural numbers fail. So we will introduce infinite ordinals.

To do this we will use a special function $$\g\$$. The $$\g\$$ function takes a set of numbers and gives us the smallest number greater than all the numbers in that set. For a finite set of natural numbers this is just the maximum plus 1. However this function is not defined on natural numbers alone. For example what is $$\g(\mathbb{N})\$$, or the smallest number greater than all naturals. To create our ordinals we say

• $$\0\$$ exists and is an ordinal.
• If $$\X\$$ is a set of ordinals then $$\g(X)\$$ exists and is an ordinal.

This gives us the natural numbers (e.g. $$\1 = g(\{0\})\$$, $$\2 = g(\{1\})\$$ etc.) but also gives us numbers beyond that. For example $$\g(\mathbb{N})\$$, this is the smallest infinite ordinal, and we will call it $$\\omega\$$ for short. And there are ordinals after it, for example $$\g(\{\omega\})\$$ which we will call $$\\omega + 1\$$.

We will in general use some math symbols $$\+\$$, $$\\times\$$ etc. in ways that are not defined explicitly. There are precise rules about these operators, but we will just use them as special notation without definition. Hopefully their use should be clear though. Here are a few specific ordinals to help you out:

$$\ \begin{eqnarray} \omega\times 2 &=& \omega+\omega &=& g(\{\omega + x : x\in \mathbb{N}\})\\ \omega^2 &=& \omega\times\omega &=& g(\{\omega \times x + y : x\in \mathbb{N}, y\in \mathbb{N}\})\\ \omega^3 &=& \omega\times\omega\times\omega &=& g(\{\omega^2\times x+\omega\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z\in \mathbb{N}\})\\ \omega^\omega &=& & & g(\{\omega^x\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z < \omega^x\})\\ \end{eqnarray} \$$

If an ordinal is not the successor of another ordinal, meaning there is not a next smaller ordinal, we call that ordinal a limit ordinal. For example $$\\omega\$$, $$\\omega\times3\$$, and $$\\omega^{\omega\times 2}+\omega^6\times 4\$$ are all limit ordinals. $$\3\$$, $$\\omega\times 5 + 12\$$ and $$\\omega^{\omega^\omega}+1\$$ are not. Some authors will specify further that 0 is not a limit ordinal, we will be explicit about 0 when we talk about limit ordinals to avoid confusion.

## Infinite Time Turing Machines

A classical Turing machine is equipped with a start status, and a way to get from one status to another. This allows you to determine the status of the machine at any finite step.

Infinite time Turing machines extend classical Turing machines to have a defined status non-zero limit ordinals as well. That is ordinals as defined above which are not the successor of any previous ordinal. This addition makes the condition of the machine defined at transfinite time as well.

### Formal definition

• $$\q_l : Q\$$: The limit state

And we define the condition of the machine at some limit ordinal $$\\lambda\$$ to be

• $$\\xi_\lambda(k) = \limsup_{n\rightarrow \lambda} \xi_n(k)\$$
• $$\k_n = 0\$$
• $$\q_n = q_l\$$

$$\\$$

# Example

Here we have a diagram of the current 2-state champion:

If we want to calculate how long this takes to halt we can't just throw it into a computer and run it, rather we have to determine it by hand.

To start we follow the machine through it's normal execution. It starts at $$\q_1\$$ and we can see that from there it always moves to $$\q_2\$$ flipping the cell under the read-write head. So here it turns the cell on. Then since the cell is on it will transition back to $$\q_1\$$, turning the cell off and moving to the right. This puts us in the exact same condition as the start, except the read-write head has advanced by 1. So it will continue in this loop of flipping on bit on and off and moving to the right endlessly.

ANIMATION 1 HERE

Now that we have determined the behavior of the machine for all finite steps we can figure out the state at step $$\\omega\$$. Each cell is on for at most 1 step, before being turned off, and then it is never on again. So the limit supremum of each cell is $$\0\$$, and at step $$\\omega\$$ the tape is entirely empty.

So this means that after $$\\omega\$$ the machine just repeats its exact behavior, the condition at step $$\\omega+n\$$ is the same as the condition at step $$\n\$$. And this persists even after we hit another limit ordinal, $$\\omega+\omega\$$, the tape remains blank and just repeats the same behavior over and over.

ANIMATION 2 HERE

So we now have an accurate description of the machine for states of the form $$\\omega\times n + m\$$, and it doesn't halt for any of those steps. It just repeats the same infinite pattern an infinite number of times. So now we can look at the step after all the steps we have described. We take the next limit ordinal:

$$\ g(\{\omega\times n + m : n\in \mathbb{N}, m \in \mathbb{N}\}) = \omega\times\omega = \omega^2 \$$

Your first instinct might be that the tape will be completely empty again, since it was empty at every step $$\\omega\times n\$$. However with infinities instincts can be misleading, so we should look at the definitions carefully instead.

In order for a cell to be zero it must converge to zero. Since the only possibilities are zero and one, this means that for each cell there must be some step $$\x\$$ after which that cell is always zero. Previously since each cell was only turned on once that step was just the step after it was turned off.

Now if such a step were to exist for a cell $$\k\$$ it would be of the form $$\\omega\times n + m\$$, however we know that the cell will be turned on again some time during the $$\\omega\times(n+1)\$$ iteration. In fact it will be turned on at exactly step $$\\omega\times(n+1) + 2k + 1\$$.

So no cell (with a non-negative index) will converge to a stable value. Meaning that by the limit supremum all non-negative cells will be on at time $$\\omega^2\$$.

ANIMATION 3 HERE

So here we finally get some new behavior. With cell 0 on, the machine transitions to $$\q_2\$$ turning the cell off, and since $$\q_2\$$ doesn't have a transition for off cells the machine halts.

This gives us a total of $$\\omega^2+1\$$ steps until halting.

• It'd be nice to link the ITTM paper. Also, showing an example ITTM and explaining its halting time (like your ⍵×⍵ 2-state ITTM) would be helpful. – user41805 May 7 at 12:39
• @user41805 I'm currently working on an explanation for my 2-state ITTM champion. But the animations are a bit time consuming. I meant to link some ITTM papers, so I will add those links when I finish the edit I am working on. Thanks. – Wheat Wizard May 7 at 12:42

# Floor of complex number code-golfmathcomplex-numbersaplopen-ended-function

## Background

Complex floor is a domain extension of the mathematical floor function for complex numbers. This is used in some APL languages to implement floor ⌊, ceiling ⌈, residue |, GCD ∨, and LCM ∧ on complex numbers.

For the rest of this challenge, an integer refers to a Gaussian integer, i.e. a complex number whose real and imaginary parts are integers.

Eugene McDonnell defined seven requirements of a complex floor function (copied from the wiki page, with APL code fragments translated into plain math notation):

1. Existence. Every number has a floor.
2. Uniqueness. Every number has only one floor.
3. Fractionality. The magnitude of the difference of a number and its floor shall be less than one. This property must be satisfied to guarantee that remainders are less in magnitude than divisors. It may be called the fundamental property of the floor function.
4. Integrity. The floor of a number is an integer.
5. Convexity. If $$\g\$$ is the floor of the numbers $$\z\$$ and $$\w\$$, then it is also the floor of all numbers on the line segment between $$\z\$$ and $$\w\$$.
6. Integer Translation. For $$\c\$$ a complex integer, $$\c+ \lfloor z \rfloor = \lfloor c+z \rfloor\$$.
7. Compatibility. The complex floor function is compatible with the real floor function. Furthermore, its action on purely imaginary numbers is similar to the action of the real floor function on real numbers. In particular, $$\\operatorname{re}(\lfloor z \rfloor) ≤ \operatorname{re}(\lceil z \rceil)\$$ and $$\\operatorname{im}(\lfloor z \rfloor) ≤ \operatorname{im}(\lceil z \rceil)\$$. (Ceiling for complex numbers is defined as $$\\lceil z \rceil = -\lfloor -z \rfloor \$$.)

One shape that satisfies these conditions is a rectangle $$\\sqrt{1\over2}\$$ units high and $$\\sqrt2\$$ units wide, rotated 45 degrees, as in the following image.

One interesting consequence of fractionality is that the magnitude of the residue is always smaller than that of the divisor, and the Euclidean algorithm always terminates on arbitrary complex number inputs.

Define your own complex floor that satisfies the requirements listed above, and implement it. It is OK if you simply use McDonnell's function. If you use a different function, please include an explanation of how it satisfies the requirements.

You may represent a complex number as a built-in complex number or a pair of real numbers. You don't need to care too much about boundary conditions, since floating-point imprecision will impact its correctness anyway.

It is known to be implemented in Dyalog APL, J, and NARS2000. You are not allowed to use floor/ceiling/residue/GCD/LCM functions with non-real complex arguments for these languages.

Standard rules apply. Shortest code in bytes wins.

# Reveal by Halves (in need of a better name)

Inspired by this: http://nolandc.com/smalljs/mouse_reveal/ (source).

• Takes a number $$\w\$$ and (assumed non-negative) integer $$\x\$$.
• Outputs an integer list with a length of $$\2^w\$$, initially filled with zeroes.
• For each number $$\n\$$ from $$\0\$$ to $$\w-1\$$ (inclusive), divide the list into sub-lists of size $$\2^n\$$, then increment all of the values in the sub-list that contains the index $$\x\$$.

## Examples

(with coordinates from left, 0 indexed, but your answer may have change these)

w=3, x=1
23110000

w=2, x=2
0021

w=3, x=5
00002311

w=4, x=4
1111432200000000

w=2, x=100
Do not need to handle (can do anything) because x is out of bounds


## Meta questions

• Are these tags fitting?
• Would this be better in one dimension? (like $$\3, 2\$$ returns 11320000) Edit: I've changed it to one dimension but I can revert if it makes it less interesting.
• Should $$\w\$$ or $$\2^w\$$ be the input?
• Is this a duplicate?
• My opinions on some meta questions. 1) I think one dimension would be better, the core of the challenge remains the same but the challenge itself becomes more "pure" which, in my opinion, is a good thing. 2) I'm a fan of flexible I/O, so if it were up to me I'd let people choose if they want $w$, $2^w$ or both as input. If you don't like this, both options are honestly fine. – Delfad0r 2 days ago
• I think I saw l4m2's proposal which is essentially the same thing, but this one is arguably much better and clearly worded. Btw, the first example is just a special case of Chaitin's constant with power-of-0.5 weights. – Bubbler yesterday
• I don't see how it's possible, if $f(n)$ is computable, isn't the limit of $f(n)$ computable by the definition of limit? – Command Master 22 hours ago
• @CommandMaster Actually no! This is just one of a million ways in which limits can be counter intuitive. For an example, imagine an $f$ where $f(n)$ just takes the first $n$ Turing machines and runs them for $n$ steps, if machine $m$ halts in the test run then you add $2^{-m}$ to a total (think about what this means in binary). This is obviously computable, we can simulate Turing machines for $n$ steps and add rational numbers. But the limit encodes the exact solution to the halting problem. This is actually the first example number there. – Wheat Wizard 21 hours ago
• Does $f(n)$ have to be an exact rational (i.e. a pair (numerator, denominator)), or can it be represented as a floating point number? In other words, can we output $f(n)$ as a floating point number which will, necessarily, be inexact for large values of $n$, as long as the algorithm theoretically works if given arbitrary precision? – Delfad0r 19 hours ago
• @Delfad0r I'm not entitled to answer your question, but I don't think float or double are applicable here. Arbitrary-precision floating-point numbers are certainly applicable tho. – Dannyu NDos 18 hours ago
• @WheatWizard Thanks for the clarification! Does the first option include, say, a pair [numerator,denominator] (even though it's not a built-in rational type)? In this case, is the pair required to be reduced (i.e. gcd=1)? – Delfad0r 5 hours ago
• @Delfad0r I will add that as another form, and the second format shows a non-reduced fraction as an example so it would be all right for this format as well. – Wheat Wizard 5 hours ago

# Metagolf: Catlike Piet

The goal of this is to write a catlike program, which would be executed (in a Unix environment, though you needn't stick to that) by the following:

yourprogram < file > output
piet output


where piet output writes the contents of file to stdout. That is, you're to generate a Piet program which prints the input to yourprogram.

One-liners

Straight line programs can be written in Piet... in straight lines. If you're willing to take a hit to your score, your output can take the form of a string of commands:

=  none (continue color block)
|  push
^  pop
-  subtract
*  multiply
/  divide
%  mod
~  not
>  greater
.  pointer
\  switch
:  duplicate
@  roll
$input number ? input character # output number ! output character  which is trivial to convert to a Piet program with the following (partially golfed) Python code: def P(s): h=v=0;l=len(s)+1;R="P3 %i 2 255 192 0 0 "%(l+2) C=[1,3,2,6,4,5];V=[0,192,192,255,0,255] for x in map("=|^+-*/%~>.,:@$?#!".find,s):
C=C[x//3:]+C[:x//3];V=V[x%3*2:]+V[:x%3*2]
for i in [1,2,4]:R+="%i "%V[(C[0]//i)%2]
return R+"255 "*4+"0 0 "+"255 "*l*3+"255 0 0 "*2


The dimension of said program is (n+3) x 2 if there are n characters in the string.

Scoring

Your code will be judged on the maximum dimension of the images that it outputs.

• Part 1: Take the maximum score taken over all ascii codes (that is, single-character inputs), discounting EOF.

• Part 2: Take the score for the input "Hello. My name is Inigo Montoya. You killed my father. Prepare to die."

Your score is the product of the scores in part 1 and part 2.

Punishment: Double your score if you write one-liners as above (that is, if you don't output an image).

Bonus: If your program is written in Piet, take the square root of your score above.

• It took me a while to understand the task as "Write a program taking INPUT which produces as output a piet program that takes no input but produces INPUT." I think it is a interesting and challenging, but it's reception will depend entirely on how many people are willing to learn/futz-around-in/deal-with piet. And I have no feel for how many that is. – dmckee --- ex-moderator kitten Jul 7 '11 at 3:12
• @dmckee; would it be better if I just used a reduced instruction set, and only ask for the instruction stream? I think this is still challenging with {push 1,duplicate,add,subtract,multiply,output}. Come to think of it, if I restrict to {push 1,duplicate,add,output}, there's a reduction to some awesome algorithms. – boothby Jul 7 '11 at 4:48
• I did this in piet some time ago: craigoclock.blogspot.com/2011/05/metaprogramming-in-piet.html – captncraig May 21 '12 at 18:31
• Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) – programmer5000 Jun 9 '17 at 15:22

## Chess move

The Challenge

Write a program that gets a string containing a chessmove and a chessboard as input, and then outputs the chessboard.

Requirements

The chess move will have this format:

<from square><to square>[<promoted to>]


Examples:

d2d4
f8g7
a7a8R


The chessboard format is not fixed, but there must be a 1 to 1 relation between the board and the string to represent the board. Also the format of the input must bet the same as the format of the output. Two suggestions of what it could look like:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

rnbqkbnr pppppppp 00000000 00000000  00000000  00000000 PPPPPPPP RNBQKBNR


It is not required to store anything except the location of the pieces, and validity of moves can be assumed.

Scoring

Base score is character count (assuming your program can move pieces for all moves)

Bonus multipliers:

• If the program updates the promoted piece, divide by 2
• If the program also moves the rook when castling, divide by 2
• If the program also removes the pawn when capturing en passent, divide by 2

The moves, and castling & en passent in particular are explaned on Wikipedia.

So basically writing a 100 character solution for the base problem gives the same score as an 800 character solution with all bonus multipliers.

Examples

If you would choose to use one of the board formats above, your input would look like one of these strings:

e2e4 rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

e2e4 rnbqkbnr pppppppp 00000000 00000000  00000000  00000000 PPPPPPPP RNBQKBNR


Your corresponding output string would then be one of these:

rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

rnbqkbnr pppppppp 00000000 00000000  0000P000  00000000 PPPP0PPP RNBQKBNR

• Before I get on to more specific criticisms: as presented, without the bonus this is too trivial to be interesting. I suggest removing some flexibility: require Fen notation for the board position and algebraic notation for the move, and making the current bonus options mandatory. On specifics: it's not clear why you talk about storage; and the board position notations you suggest don't include enough information to know whether en passant is possible. – Peter Taylor Dec 22 '13 at 23:56
• @PeterTaylor I agree that compared to chess programs this may be trivial, but I would like to make it a golf challenge. Compared to the hot code golf questions this is quite elaborate already in its basic form. (For a good solution the board design may need to be changed drastically). It is true that there is no attention to the legality of moves (whether it is possible to capture en passent) but for a mere viewer this is not required so I am not too worried about this. So far the chess questions seem to get very few answers as they tend to be complex and I hope to offer relatively easy entry. – Dennis Jaheruddin Dec 30 '13 at 11:02
• Your point about en passant is valid - you had said in the spec to not worry about legality. I'll try to convince you of my first point: without the bonus, this reduces to: a) parse first four characters into (col 1, row 1, col 2, row 2); b) take board as a 64-char string; c) board[8*row_2+col_2] := board[8*row_1+col_1]; board[8*row_1+col_1] := ' '; print board. This is trivial compared to any good golf question. (Note that the hot questions at the moment are neither golf questions nor good questions). – Peter Taylor Dec 30 '13 at 12:14
• This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this. – programmer5000 Jun 9 '17 at 15:40

# Black Box

Your task is to analyze a given situation for the game Black Box. Given a sequence of guesses and answers, your program is to either print the solution or suggest the next move.

## The game

The board consists of 8×8 cells, with edges labeled like this:

I'll probably create nice images here, particularly to make sure that the squares of the board are really square.

 abcdefgh
i        I
j        J
k        K
l        L
m        M
n        N
o        O
p        P
ABCDEFGH


The player shoots rays into the interior of the box, where they might get deflected, reflected or absorbed. He is told the position where the ray leaves the black box again, and from that has to deduce the positions of 4 atoms inside the black box.

I'll have to include more of the game rules here, but for now see Wikipedia.

# Input and output

Input is a sequence of line, each consisting of two characters. The first denotes the point where the ray of light enters the black box, the second the place where it comes out again. In the case of a reflection, both characters will be equal. In the case of a hit, the second character will be -.

If the input is enough to fully determine the locations of the atoms, then output should be four lines giving the coordinates of each atom. The lines should be two lower case characters each, the first giving the row and the second giving the column of the found solution. The atom positions must be printed in lexicographical order.

If the input is consistent with more than one set of atom positions, then the output should consist of a single line containing a single character, which is the location where the next ray should be shot. That location has to be chosen in such a way that it can help find the solution. This is the case unless all of the atom positions consistent with the input so far would produce the same output for this next ray as well.

Your output has to be terminated by a newline character.

# Examples

Let's take the atom configuration the Wikipedia article uses as an example as well:

 abcdefgh
i        I
j        J
k O    O K
l        L
m        M
n   O    N
o        O
p      O P
ABCDEFGH


If the input were

cf
D-
Em
HH
Co


then the output should be

kb
kg
nd
pg


but if the input were only

Em
HH


then the output might be for example

K


## Scoring

This is code golf, so shortest answer wins. However, I'll only accept answers which are practical in so far as they compute their result in reasonable time. I'd say no more than five minutes on my system where I'll evaluate the answers, and I'll simply hope that correct solutions will be much faster and incorrect ones much slower, so that the speed of my system doesn't make a difference. A submission which gives a wrong answer for one of my test cases will be disqualified until it gets fixed. I will probably point out the problem in a comment to that post.