title: A Quine on Every Line

text:
# Question
Title: A Quine on Every Line
Your goal is to create a program that prints itself indefinitely, with a new line after each one. Thus, if your program is a one-liner, it would be repeated on every line of the output.

### Example

Program:

```
A

```

Output:

```
A
A
A
...

```

### Rules

* It must be a complete program, not a snippet or function.
* The program should loop forever without stack-overflow or recursion limit errors.
* Output is to stdout or closest alternative.
* No program input is accepted.
* Standard loopholes are disallowed, such as opening the program's file or accessing an external resource. Empty programs are disallowed as a standard loophole.
* If your program code ends with a trailing newline, this does not count as the necessary newline between quines, and you must print another.
* \- Shortest code wins!

# Answer
> 19 votes
# Fission, 7 bytes

```
'!+!NR"

```

A rather simple modification of the shortest Fission quine I have found so far: I'm simply using the non-destructive `!` instead of `O` and added an `N` for newline.

So all in all, here is how it works: control flow starts at the `R` with a right-going atom. `"` toggles string mode, which means everything until the next `"` is printed: in this case `'!+!NR`. That leaves the `"` and the newline to be printed. `'!` sets the atom's mass to 33, `+` increments it to 34 (the character code of `"`) and `!` prints the quote. `N` prints a newline, and `R` is now a no-op in this case, so the loop starts over.

The following 7-byte solution also works:

```
"NR'!+!

```

# Answer
> 9 votes
# \>\<\>, 16 bytes

```
'ard3*o50l2)?.~~

```

The traditional \>\<\> quine uses too many `o`s, so we use a loop for printing. Before each jump we push 5 and 0 (the coordinates of where to jump to), after which we either jump with `.` if there's still something to print, or pops the top two values with `~~`.

(Reverted to the 16 version since I forgot about the stack overflow rule.)

# Answer
> 8 votes
# CJam, 13 bytes

```
{_o"_g
"o1}_g

```

The online interpreter doesn't print anything before the program terminates, so you'll have to test this in the Java interpreter.

## Explanation

Finally a generalised CJam quine which doesn't end in `_~`.

```
{_o"_g
"o1}

```

This simply pushes a block. `_g` duplicates the block and executes it repeatedly while the top of the stack is truthy (discarding the condition).

Now inside the block, the other copy of the block is still on the stack. We duplicate and print it with `_o` and then we print `_g` followed by a newline (the required extra newline between quines) with `"_g\n"o`. Finally we push a `1` onto the stack for the loop to repeat, because unfortunately, blocks aren't truthy (or falsy) in CJam.

# Answer
> 7 votes
# Python 2, 39

Not a very interesting task in Python as it's trivial to add the while loop to a normal quine.

```
c='while 2:print"c=%r;exec c"%c';exec c

```

# Answer
> 6 votes
# Perl 5.10+, ~~40~~ 37 bytes

```
$_=q{say"\$_=q{$_};eval"while 1};eval

```

or (also 37 bytes)

```
$_=q{{say"\$_=q{$_};eval";redo}};eval

```

Invoke with the `-M5.010` or `-E` command line flag, e.g.

```
$ perl -E '$_=q{say"\$_=q{$_};eval"while 1};eval'
$_=q{say"\$_=q{$_};eval"while 1};eval
$_=q{say"\$_=q{$_};eval"while 1};eval
$_=q{say"\$_=q{$_};eval"while 1};eval
...

```

---

Thanks to Ilmari Karonen for shaving off 3 bytes from my original solution, which was:

```
eval while$_=q{say"eval while\$_=q{$_}"}

```

This, as well as the shorter 37-byte solutions above, are all simple variations of the following quine, which I first saw in one of Ilmari's other posts:

```
$_=q{say"\$_=q{$_};eval"};eval

```

Since all I added in my original solution was a `while` loop, he really deserves most of the credit. :-)

# Answer
> 5 votes
# Self-modifying Brainf\*** (SMBF), 14 bytes

The trailing newline `\n` needs to be a literal, Unix, newline (ASCII code 10).

```
[<[<]>[.>]<.]\n

```

### Explanation:

The code moves the pointer to the far left of its source code, then prints it all, including the newline (twice b/c of the rule). The loop continues.

# Answer
> 3 votes
# PowerShell, 143 Bytes

```
$d='$d={0}{1}{0}{2}while(1){3}Write($d -f [char]39,$d,"`n",[char]123,[char]125){4}'
while(1){Write($d -f [char]39,$d,"`n",[char]123,[char]125)}

```

Based off the Rosetta Code PowerShell quine, I'm pretty confident this isn't the shortest possible. String replacement formatting in PowerShell is icky for this, because the same delimiters for where to put the replacements `{}` also delimit code blocks `while{}`, so we have to use `[char]` casting, which bloats the code a bunch.

# Answer
> 3 votes
# Underload, 25 bytes

First time I've tried something like this and I'm not sure if follows all the rules as it is a couple of lines. The newline was a bit of a pain.

```
(::a~*S:a~*^
)::a~*S:a~*^

```

# Answer
> 3 votes
# Befunge, ~~30~~ 20 bytes

```
<,+55,*2+98_ #!,#:<"

```

A variation of a popular befunge quine that prints out a newline and pops -1 on the stack if it finishes the line.
Unfortunately, Befunge gets verbose when doing things in one line. I tried to remove all of the launchpads (`#`) that i could, but some had to be left in to skip certain commands (like `,`).

Changes:

**30-20** -\> changed the base quine to a custom one I made that uses string input. This way, the branching is a lot easier.

Old:

```
:0g,:93*`>0-10 #,+$#: #5 _1+>

```

I don't think this is optimal, but it's acceptable for now.

# Answer
> 2 votes
# \>\<\>, ~~31~~ 29 bytes

A simple modification of the traditional \>\<\> quine.

```
"ar00gc0.0+efooooooooooooooo|

```

To run, paste it here, click 'Submit', then 'Start' (running without animation doesn't work). Feel free to increase the execution speed.

# Answer
> 2 votes
# K, 30 bytes

```
{f:$_f;{x}{`0:f,"[]\n";1}/1}[]

```

# Answer
> 2 votes
## R, 34 bytes

```
repeat{write(commandArgs()[5],'')}

```

to invoke from the command line as follows:

```
Rscript -e "repeat{write(commandArgs()[5],'')}"

```

# Answer
> 2 votes
# Python 2, 48 bytes

```
c='c=\'%s\';while 1:print c%c';while 1:print c%c

```

# Answer
> 2 votes
# GolfScript, 16 bytes

```
{.".do
":n\p}.do

```

This ended up looking a lot like Martin Büttner's CJam entry. An interesting feature is that, as it turns out, the shortest way to append `".do"` to the block when it's printed is to assign it to the line terminator `n`. (Of course, we also need to include an actual newline in the string, to replace the one `n` normally contains.) The same string (being truthy in GolfScript) is also left on the stack for the `do` loop to pop off, ensuring that the loop runs forever.

# Answer
> 2 votes
# Brachylog, 16 bytes

```
∋"∋~kgjẉ₁⊥"gjẉ₁⊥

```

You can't quite try it online, but I have verified that it works on my installation.

# Brachylog, 18 bytes

```
∋"∋~kgjw₁⊥~n"gjw₁⊥

```

Try it online!

Adapted from the alternate version of this quine, with a backtracking hack I had initially devised for bogosort of all things. Spends two bytes on `~n` because  (the usual means for printing with a trailing newline) hits some odd issues with character encoding on TIO, and an actual newline inserted into the string literal gets printed through `~k` as `\n`.

```
               w      Print
 "∋~kgjw₁⊥~n"         "∋~kgjw₁⊥~n"
∋                     which is an element of
                      the (unused and unconstrained) input
                ₁     formatted
          ~n          (so that the ~n is replaced with a newline)
             gj       with itself
   ~k                 (so that the ~k is replaced with the string in quotes),
                 ⊥    then try again.

```

Since `w₁` takes input as a list `[string to be formatted, formatting arguments]`, wrapping a string in a list with `g` then concatenating it to itself with `j` allows it to be formatted with itself. And since no input is given to the program, the input variable which is implicitly present at the beginning of the program can take on any value, so it can be constrained to one of the infinitely many lists which contain `"∋~kgjw₁⊥~n"` as an element, creating a single choice point to be backtracked to when after printing its source the program hits .

# Answer
> 2 votes
# **Python 3.6, ~~48~~ 43 bytes.**

-5 bytes thanks to @Jo King

```
x='while 1:print("x=%r;exec(x)"%x)';exec(x)

```

# Answer
> 2 votes
# Gol\>\<\>, 10 bytes

```
"r2sslRoao

```

Try it online!

This can probably be golfed down more

# Answer
> 1 votes
# BASH, 76 bytes

Just couldn't resist, especially with PowerShell here :)

```
while true;do
a ()
{
    echo while true\;do
    declare -f a
    echo a\;done
}
a;done

```

The whitespace is important for an EXACT copy.

# Answer
> 1 votes
## Batch, 10 (+ 4 for filename length)

Not sure if this qualifies for two reasons:

* Technically, there may or may not be textual side effects from the Windows command shell, as that depends on how it is configured.
* This program invokes itself by name, and I am not sure whether that's prohibited by the rules (specifically the "no opening of program file" rule). It is not opening itself for the purposes of reading and printing out the text; it is simply re-running itself. Further, the file system structure is an integral part of old-school batch scripts (oftentimes even being used to store program state, etc). As such, I am not sure whether this violates the 5th rule or not.

The code (for a program named q.bat):

```
echo on&&q

```

# Answer
> 1 votes
# Javascript (ES6), 64

```
for(;;(_=>console.log(`for(;;(_=>${arguments.callee})());`))());

```

Alternatively (also 64)

```
a="for(;;)console.log(`a=${JSON.stringify(a)};eval(a)`)";eval(a)

```

# Answer
> 1 votes
# Microscript, 22 bytes

```
"f1{CqxCanx"f1{CqxCanx

```

Based on the quine from the Esolangs article: `"fCqxah"fCqxah`. Exploits the fact that the language autoappends closing braces as needed, without which this would be two bytes longer.

# Answer
> 1 votes
# Ceylon, ~~210~~ 208 bytes

Of course this won't win anything...

```
shared void u(){value q="\"\"\"";value t="""shared void u(){value q="\"\"\"";value t=""";value b="""while(1<2){print(t+q+t+q+";value b="+q+b+q+";"+b);}}""";while(1<2){print(t+q+t+q+";value b="+q+b+q+";"+b);}}

```

Original:

`shared void u(){value q="\"\"\"";value t="""shared void u(){value q="\"\"\"";value t=""";value b="""while(true){print(t+q+t+q+";value b="+q+b+q+";"+b);}}""";while(true){print(t+q+t+q+";value b="+q+b+q+";"+b);}}`

I modified my Quine from two days ago by adding the `while(true){...}` loop, so I come from the 185 bytes of the plain Quine to 210 (I don't need the trailing new line character anymore). But then I found that a `while(1<2){...}` loop is even two bytes shorter:

`shared void u(){value q="\"\"\"";value t="""shared void u(){value q="\"\"\"";value t=""";value b="""while(1<2){print(t+q+t+q+";value b="+q+b+q+";"+b);}}""";while(1<2){print(t+q+t+q+";value b="+q+b+q+";"+b);}}`

(Ceylon has no `for(;;)` loop like Java, and the braces are also needed for this loop.)

# Answer
> 1 votes
## PowerShell, 132 107 Bytes

```
$a='$a={0}{1}{0};for(){2}$a-f[char]39,$a,[char]123,[char]125{3}';for(){$a-f[char]39,$a,[char]123,[char]125}

```

Based off of the Rosetta Quine (Same as @AdmBorkBork) although doesn't use formatting for string replacement... maybe switching to a for loop and using formatting would be best?

I'm sure if AdmBorkBork came back they would beat this by a lot :P

**EDIT** Figured out the for loop and replacements, all thanks to my predecessor :)

Old attempt:

```
$a='$a=;for(){$a.substring(0,3)+[char]39+$a+[char]39+$a.substring(3)}';for(){$a.substring(0,3)+[char]39+$a+[char]39+$a.substring(3)}

```

# Answer
> 1 votes
# Ruby, ~~41~~ 39 bytes

A modification of one of the Ruby quines found here.

```
_="_=%p;loop{puts _%%_}";loop{puts _%_}

```

# Answer
> 1 votes
# Java 10, 194 bytes

```
interface M{static void main(String[]a){for(var s="interface M{static void main(String[]a){for(var s=%c%s%1$c;;)System.out.println(s.format(s,34,s));}}";;)System.out.println(s.format(s,34,s));}}

```

**Explanation:**

Try it online (times out after 60 sec).

```
interface M{                    // Class
  static void main(String[]a){  //  Mandatory main-method
    for(var s="interface M{static void main(String[]a){for(var s=%c%s%1$c;;)System.out.println(s.format(s,34,s));}}";
                                //   Unformatted source code
        ;)                      //   Loop indefinitely
       System.out.println(      //    Print with trailing new-line:
         s.format(s,34,s));}}   //     The formatted source code

```

-part:

* The String `s` contains the unformatted source code.
* `%s` is used to input this String into itself with the `s.format(...)`.
* `%c`, `%1$c` and the `34` are used to format the double-quotes.
* `s.format(s,34,s)` puts it all together

Challenge part:

* `for(;;)` is used to loop indefinitely.
* `System.out.println(...)` is used to print with trailing new-line

# Answer
> 1 votes
# Funky, 29 bytes

```
f=@print`f=[f]for)f()`for)f()

```

Try it online!

# Answer
> 1 votes
# RProgN 2, 7 bytes

```
«]³]]p:

```

Try it online!

# Answer
> 1 votes
# Jelly, 14 bytes

```
“;@ṾṄṛ¢”;@ṾṄṛ¢

```

Try it online!

# Answer
> 1 votes
# Pyth, 11 bytes

```
#jN B"#jN B

```

Try it here!

# Answer
> 1 votes
# Keg, 16 bytes

```
`{④⑩9⑨,}`{④⑩9⑨,}

```

Try it online!

Ties with most other golfing languages, so I'm happy with that. Pushes the string `{④⑩9⑨,}`, which is then infinitely printed rawly, then nicely followed by a newline infinitely.

---
Tags: code-golf, quine
---


title: Cycles in run-length encoding

text:
# Question
Title: Cycles in run-length encoding
Consider some binary sequence, using `1` and `2`, e.g.:

```
1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1 ...

```

Let's write down the run lengths of that:

```
1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1 ...
_  _  ____  ____  _  _  _  ____
1, 1, 2,    2,    1, 1, 1, 2,   ...

```

In this case we happen to get another binary sequence. Of course, that's not guaranteed (e.g. if we repeated the process, the third run would be `3`), but let's assume we do.

Now the question is, can we find a sequence such that applying this type of run-length encoding multiple times gives us back the original sequence? For a cycle-length of 1 (i.e. a fixed point of this transformation), we find the Oldenburger-Kolakoski sequence (OEIS entry A0000002):

```
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, ...

```

(There is actually another solution: we can also omit the leading `1`.)

What about a cycle of length-2? That's also possible! The following two sequences are each others' list of run lengths:

```
1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, ...
2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, ...

```

(These are OEIS entries A025142 and A025143. This is the only solution.)

Can we find a cycle of length 3? Sure, here each sequence is the run-length encoding of the next (and the third one is the run-length encoding of the first):

```
1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, ...
1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, ...
2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, ...

```

In this case there is one other solution. It turns out that we can find such a cycle for every cycle length. In fact, the number of distinct cycles of length n is given by OEIS entry A001037 (this is not counting the arbitrary choice of which sequence in a cycle is considered the first).

**Fun fact:** As unlikely as it seems, this challenge was inspired by studying the complex map `f(z) = z - 1/z`. Whoever figures out what that map has to do with this challenge gets a cookie.

## The Challenge

Given a cycle length `k > 0` and a sequence length `n > 0`, output the first `n` terms of `k` distinct (infinite) binary sequences that form a cycle under the above run-length transformation. If multiple cycles exist, you may output any one of them. It's up to you which sequence in the cycle to start with, and which direction the cycle goes (so you can either output them such that each sequence describes the next, or such that each sequence describes the previous one, cyclically).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Output may be in any convenient, unambiguous, nested list format, such that the the outer dimension is `k` and the inner dimension is `n`.

Standard rules apply.

## Additional examples

Here are some examples. But as I said, the solutions are not unique, so your own solutions might differ and still be correct. Maybe these will help you come up with a solution though. Each example is `k n` followed by the sequences, such that each line describes the next (cyclically):

```
4 20
1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2
2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1
2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1
1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1

5 6
2, 2, 1, 2, 2, 1
1, 1, 2, 2, 1, 2
2, 1, 2, 2, 1, 1
1, 1, 2, 1, 1, 2
2, 1, 2, 2, 1, 2

8 20
2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2
1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1
2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2
2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2
1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1
2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2
1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1
2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1

13 50
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2
2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1
1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1
1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1
1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1
1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1

```

Note that not all of the lines in the last two outputs differ, although they would eventually if `n` was large enough.

### Related Questions

# Answer
> 7 votes
## CJam (41 bytes)

```
{Ma*{1:Bm<{1+ee{(1&B^)+}%e~A<0:B;}%}@:A*}

```

This is an anonymous function which takes input on the stack in the order `n k` and leaves output on the stack. Online demo

The basic idea is to start with a Lyndon word column `[2 1 1 1 ...]` and iteratively extend right on the basis that knowing the initial element of each row and the alternation we can run-length decode and get more elements.

# Answer
> 3 votes
# Haskell, 72 bytes

```
~(a:b)?c=c:[c|a>1]++b?(3-c)
k!n=take k$take n<$>last(k!n)?2:map(?1)(k!n)

```

Demo:

```
*Main> 4!20
[[2,1,1,2,2,1,2,2,1,2,1,1,2,1,1,2,2,1,2,1],[1,1,2,1,2,2,1,1,2,1,1,2,2,1,2,2,1,2,1,1],[1,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2],[1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2]]

```

# Answer
> 3 votes
# APL (Dyalog Unicode), 35 bytes

```
{(⍺↑¨⊣{⍵/(≢⍵)⍴⍺,3-⍺}¨¯1⌽⊢)⍣≡⍨1+⍵↑1}

```

Try it online!

An anonymous dfn whose left argument is `n` and right is `k`.

Almost direct translation of Anders Kaseorg's Haskell answer (adapted to the finite and strict nature of APL arrays), with a bit of hint from Peter Taylor's idea:

> The basic idea is to start with a Lyndon word column `[2 1 1 1 ...]` and iteratively extend right on the basis that knowing the initial element of each row and the alternation we can run-length decode and get more elements.

### How it works

```
{(⍺↑¨⊣{⍵/(≢⍵)⍴⍺,3-⍺}¨¯1⌽⊢)⍣≡⍨1+⍵↑1}  ⍝ left argument(⍺)←n, right(⍵)←k
                             1+⍵↑1   ⍝ u←[2, 1, ..., 1] of length k
                            ⍨        ⍝ Run the following with both sides being u:
 (                       )⍣≡         ⍝  Repeat until fixpoint:
                                     ⍝  (left: u, right: intermediate result v)
                     ¯1⌽⊢            ⍝   Rotate v down once
     ⊣{            }¨                ⍝   Zip with left side u: (left elem u_i, right elem v_i)
              ⍺,3-⍺                  ⍝    Make a 2-elem array [u_i, 3-u_i] which is [1 2] or [2 1]
         (≢⍵)⍴                       ⍝    Cycle the above to the length of v_i
       ⍵/                            ⍝    Duplicate each element of above v_i times e.g. 1 1 2/2 1 2 → 2 1 2 2
       ⍵/(≢⍵)⍴⍺,3-⍺                  ⍝    Run-length decode v_i with alternating 1 and 2's, starting with u_i
  ⍺↑¨                                ⍝   Extend or truncate each row to length n

```

### Comparison with Anders' Haskell version

Anders' Haskell code (parenthesized for clarity) works like this:

```
~(a:b)?c=(c:[c|a>1])++(b?(3-c))
  (c:[c|a>1])  -- Two copies of c if head of x > 1, one copy otherwise
  ++(b?(3-c))  -- Run-length decode the rest with alternating 1 and 2

k!n=take k$take n<$>((last(k!n))?2):(map(?1)(k!n))
  take k$         -- take first k rows
  take n<$>       -- take first n elements from each row
  ((last(k!n))?2) -- run-length decode the last row with starting value 2
  :(map(?1)(k!n)) -- run-length decode the other rows with starting value 1

```

In one iteration, this is equivalent to "prepend the k-th row, run-length decode each row, and then discard the last row". We can simplify it to "rotate once and run-length decode", which I implemented as `¯1⌽`.

For the run-length decoding function, I simply used the APL primitive `/`, while the Haskell version uses infinite lists to implement it.

# Answer
> 2 votes
# 05AB1E, 22 bytes

```
YΔ´12¹иćRšvyÞsÅΓI∍Dˆ]¯

```

Try it online!

---
Tags: code-golf, number, sequence
---


title: Smallest Fibonacci Multiples

text:
# Question
Title: Smallest Fibonacci Multiples
Sandbox

# Background (not necessary for the challenge)

A standard number theory result using the pigeonhole principle is the fact that given any natural number k, there is a Fibonacci number that is a multiple of k.

We can see this by considering modular pairs (F(n-1) % k, F(n) % k), and noting that there are only a finite number of possibilities of the pairs, while there are infinitely many pairs, so by the pigeonhole principle, there are naturals n, m such that (F(m-1) % k, F(m) % k) = (F(n-1) % k, F(n) % k). But, this implies that F(m-2) % k = F(n-2) % k, and more generally, F(m-i) % k = F(n-i) % k. Notably, if m \< n, F(0) % k = F(n-m) % k. But, F(0)=0, so this means that F(n-m) is a multiple of k.

# Challenge

You must provide a program that takes in a natural k as an input and return m, the smallest Fibonacci number that is a multiple of k. This program must be irreducible in the sense that one can't remove any bytes and maintain the same functionality.

This challenge is a , as your score will be the smallest Fibonacci multiple of (the number of bytes in your program + 1).

To find your program's score, use this TIO link: Try it online!

The lowest score for a valid response in each language wins!

# Test Cases

```
1: 1
2: 2
3: 3
4: 8
5: 5
6: 144
7: 21
8: 8
9: 144
10: 610
11: 55
12: 144
13: 13
14: 46368
15: 6765
16: 144
17: 34
18: 144
19: 2584
20: 832040
21: 21
22: 832040
23: 46368
24: 144
25: 75025
26: 10946
27: 14930352
28: 46368
29: 377
30: 1548008755920
31: 832040
32: 46368
33: 6765
34: 34
35: 102334155
36: 144
37: 4181
38: 2584
39: 317811
40: 832040
41: 6765
42: 46368
43: 701408733
44: 832040
45: 1548008755920
46: 46368
47: 987
48: 144
49: 225851433717
50: 2111485077978050
51: 14930352
52: 267914296
53: 196418
54: 14930352
55: 55
56: 46368
57: 14930352
58: 267914296
59: 591286729879
60: 1548008755920
61: 610
62: 832040
63: 46368
64: 4807526976
65: 9227465
66: 1548008755920
67: 72723460248141
68: 2584
69: 46368
70: 5358359254990966640871840
71: 190392490709135
72: 144
73: 24157817
74: 365435296162
75: 354224848179261915075
76: 2584
77: 102334155
78: 160500643816367088
79: 8944394323791464
80: 1548008755920
81: 16641027750620563662096
82: 1548008755920
83: 160500643816367088
84: 46368
85: 1134903170
86: 1725375039079340637797070384
87: 317811
88: 832040
89: 89
90: 1548008755920
91: 225851433717
92: 46368
93: 1548008755920
94: 4807526976
95: 2880067194370816120
96: 46368
97: 7778742049
98: 57602132235424755886206198685365216
99: 1548008755920

```

You can use the TIO link above to generate more test cases if needed.

**EDIT**: As there seems to be some confusion on the scoring, here is how to generate your score:

Take the number of bytes in your function, add 1, and take the result of this addition, and find the smallest Fibonacci multiple of this result.

# Answer
# JavaScript (Node.js), 33 bytes, score: 34

Expects a BigInt as input.

```
f=(n,x=0n,y=1n)=>y%n?f(n,y,x+y):y

```

Try it online!
> 6 votes

# Answer
# , 33 bytes, score 34

```
n=scan();while(T%%n)F={T=T+F}-F;T

```

Try it online!

I thought I was going to have to resort to a 54 byte solution for a score of 55 (and had fun making an irreducible one), but eventually found this 33 byte solution.

When coerced to integers, `F` and `T` are initially worth 0 and 1; they go through the Fibonacci sequence until `T` is divisible by `n`.
> 6 votes

# Answer
# Japt, 12 bytes, Score: 13

```
@XvU}a@MgX+1

```

Try it

## Explanation

The shortest possible solution (below) for this is 9 bytes, which means we're looking for the lowest possible score greater than or equal to `f(10)=610`.

```
_©vU}a!gM

```

Try it

That gives a target length of 12 bytes as `f(13)=13`, which can easily be achieved with some ungolfing/code bowling, giving:

```
@XvU}a@MgX+1     :Implicit input of integer U
@                :Left function, taking an integer X as argument
 XvU             :  Is X divisible by U?
    }            :End function
     a           :Starting at 0, pass each integer through the right function and return the first result that returns true when passed through the left function
      @          :Right function, taking an integer X as argument
       MgX+1     :  X+1th Fibonacci number

```

## Proofs

Hopefully, showing that no one character can be removed should also suffice to show that 2 or more characters can't be removed. I'll try to add a few words of explanation to the rest of these tomorrow.

```
*{box-sizing:border-box;}html{background:#fff;}body{background:#fff;color:#000;margin:0 auto;padding:20px;max-width:600px;}p{font-family:Arial,Helvetica Neue,Helvetica,sans-serif;font-size:14px;line-height:20px;margin:0 0 15px;}p.link{background:#eff0f1;border-radius:3px 0 0 3px;display:inline-block;margin:0 0 10px;width:32px;}a{display:block;padding:4px;}svg{fill:#212121;height:24px;width:24px;vertical-align:middle;}svg.warning{fill:#b00020;}pre{background:#eff0f1;border-radius:0 3px 3px 0;display:inline-block;line-height:16px;margin:0 0 10px 2px;padding:8px;width:calc(100% - 34px);}code{font-family:Consolas,Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace,sans-serif;font-size:13px;}p>code{background:#eee;padding:1px 5px;}
```

```
<p>Click the play icon next to each programme to test it. Note that all programmes will auto-run and some, highlighted in red with a circle, may freeze or crash the tab they're running in so proceed with cautiond.</p><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=WHZVfWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>XvU}a@MgX+1</code></pre><p>Without the first <code>@</code> to open the left function the, now unmatched, closing <code>}</code> causes the programme to throw an error.</p><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QHZVfWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@vU}a@MgX+1</code></pre><p>Removing the first <code>X</code> results in <code>U</code> being auto-inserted between the <code>@</code> and the <code>v</code> and, therefore, the left function instead testing whether <code>U</code> is divisible by itself, which, of course, it is. So, no matter the input, the programme will exit after the first iteration and always return <code>1</code>.</p><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFhVfWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XU}a@MgX+1</code></pre><p>If the <code>v</code> is removed then the <code>X</code> is ignored and the left function now tests whether <code>U</code> is truthy, which, for all non-zero inputs, it always will be. So, as above, the programme will exit after the first iteration and always return <code>1</code>.</p><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2fWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@Xv}a@MgX+1</code></pre><p>The default agrument for the <code>v</code> method when applied to an integer is <code>2</code> so, by checking if <code>X</code> is divisible by 2, this version will always return the first even Fibonacci number: <code>2</code>.<p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvUa@MgX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1ATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}@MgX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hTWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}aMgX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQGdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}a@gX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQE1YKzE&input=MTM" target="_blank"><svg class="warning" viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M12,20C7.59,20 4,16.41 4,12C4,7.59 7.59,4 12,4C16.41,4 20,7.59 20,12C20,16.41 16.41,20 12,20M12,2A10,10 0 0,0 2,12A10,10 0 0,0 12,22A10,10 0 0,0 22,12A10,10 0 0,0 12,2M10,16.5L16,12L10,7.5V16.5Z"/></svg></a></p><pre><code>@XvU}a@MX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQE1nKzE&input=MTM" target="_blank"><svg class="warning" viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M12,20C7.59,20 4,16.41 4,12C4,7.59 7.59,4 12,4C16.41,4 20,7.59 20,12C20,16.41 16.41,20 12,20M12,2A10,10 0 0,0 2,12A10,10 0 0,0 12,22A10,10 0 0,0 22,12A10,10 0 0,0 12,2M10,16.5L16,12L10,7.5V16.5Z"/></svg></a></p><pre><code>@XvU}a@Mg+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQE1nWDE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}a@MgX1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQE1nWCs&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}a@MgX+</code></pre>
```

---

## Alternative, 12 bytes, score: 13

Unlike the original solution above, this one can't be golfed any further.

```
°õ!gM ævN ªß

```

Try it
> 4 votes

# Answer
# Perl 6, 33 bytes, Score: 34

```
->$a {(1,1,*+*...*).first(*%%$a)}

```

Try it online!

There's no specifically redundant parts, even if it would pretty easy to golf.
> 4 votes

# Answer
# Jelly, 12 bytes score = 13

```
ÆḞ
1Çḍ@¥1#ÆḞ

```

Try it online!

A full program that takes an integer and returns an integer.
> 4 votes

# Answer
# Python 2, 54 bytes; score 55

```
def f(n):
 a,b=0,1
 while b/n*n!=b:a,b=b,a+b
 return b

```

Try it online!
> 4 votes

# Answer
# C++ (clang), 54 bytes, score : 55

```
int F(int m,int a=1,int b=1){return a%m?F(m,a+b,a):a;}

```

Try it online!
> 4 votes

# Answer
# Cubix, 20 bytes, Score 21

```
U;;O01I%!^;u.@|W$p+q

```

Try it online!

Maps onto the cube as follows

```
    U ;
    ; O
0 1 I % ! ^ ; u
. @ | W $ p + q
    . .
    . .

```

Watch it run

Fairly basic, builds the sequence on the stack checking the % for each iteration until it is zero then outputs and exits.

* `01I` seed the stack with start of the sequence and input. `11I` would also work.
* `%!` take modulus of TOS and test for 0. Also start of the loop
* `^;U;O!$@` if 0 pop TOS, u-Turn, pop TOS and output number, a couple of no affecting commands and halt
* `;uq+p` otherwise, pop TOS, u-turn, push TOS to bottom (input), add TOS and pull BOS to top
* `$W|W` some trickery to keep the score nice while keeping it irreducible. skip the next command(W), reflect back onto the W, change the lane up onto the beginning of the loop
> 4 votes

# Answer
# Red, 54 bytes, score 55

```
func[n][a: 0 b: 1 until[t: a a: b(b: t + b)// n = 0]b]

```

Try it online!

In fact it doesn't work in Red console after removing the space in front of `n`:

```
>> f: func[n][a: 0 b: 1 until[t: a a: b(b: t + b)//n = 0]b]
== func [n][a: 0 b: 1 until [t: a a: b (b: t + b) / /n = 0] b]
>> f 55
*** Script Error: / does not allow refinement! for its value2 argument
*** Where: /
*** Stack: f

```

so I thiink it's a valid submission. I suppose there are some subtle differences in Red for Win and Linux

## Alternative:

# Red, 67 bytes, score 2584

```
func[n][set[a b][0 1]until[set[t a]reduce[a b]zero?(b: t + b)% n]b]

```

Try it online!
> 3 votes

# Answer
# C (clang), 54 bytes, score 55

```
f(n){int a=0,b=1;while(b%n){b+=a;a-=b;a=-a;}return b;}

```

Try it online!
> 3 votes

# Answer
# 05AB1E, score: 8 (7 bytes)

```
∞Åf.ΔIÖ

```

Try it online or verify the first \\$n\\$ outputs.

**Explanation:**

```
∞        # Push an infinite list: [1,2,3,...]
 Åf      # Get the n'th Fibonacci number for each value in this list
   .Δ    # Leave the first value of this list which is truthy for:
      Ö  #  Is it divisible by
     I   #  The input
         # (after which this is output implicitly as result)

```

These are all the possible builtins after removing one or multiple characters of the program, none of which are able to have the same functionality as the full program above:

```
∞   # Push an infinite list: [1,2,3,...]
Åf  # Get the `a`'th Fibonacci number
f   # Get the prime factors of the given number(s) `a`
.Δ  # Leave the first value of the given list `a` which is truthy for
Δ   # Repeat the inner code until the result no longer changes
ÅΔ  # Get the (0-based) index of the first element of list `a` which is truthy for
Ö   # Check if integer `a` is divisible by `b`
I   # Push the input
.I  # Get the `a`'th permutation of `b`
Å   # No-op
.   # No-op

```
> 3 votes

# Answer
# SNOBOL4 (CSNOBOL4), 71 bytes, score 144

```
	N =INPUT
	T =1
F	F =(T =F + T) - F
	OUTPUT =T EQ(REMDR(T,N))	:F(F)
END

```

Try it online!

This might also be the most golfed version of this program, which would be interesting; I also learned that inline assignment works...
> 3 votes

# Answer
# MATL, (12 bytes), score 13

```
Ol`tb+tG\]wx

```

Try it online!

## Explanation

```
O       % Push 0
l       % Push 1
`       % Do...while. The stack contains F(k), F(k+1)
  tb+   %   Duplicate, bubble up, add. The stack contains F(k+1), F(k+2)
  t     %   Duplicate
  G     %   Push input
  \     %   Modulo
]       % End. If top of the stack is nonzero the loop continues
wx      % Swap, delete. This leaves only the latest Fibonacci number
        % Implicitly display

```
> 2 votes

# Answer
# Charcoal, 20 bytes, score 21

```
⊞υ¬υＷ⌊﹪υＩθ⊞υΣ…⮌υ²Ｉ⊟υ

```

Try it online! Link is to verbose version of code. Explanation:

```
⊞υ¬υ

```

Take the logical not of the predefined empty list and push that to the list. (Using a literal 1 would increase my score of course.)

```
Ｗ⌊﹪υＩθ

```

Divide each member of the list by the input and repeat while the minimum remainder is nonzero.

```
⊞υΣ…⮌υ²

```

Reverse the list, take the first (originally last) two elements (duplicates the single element in the first pass), take the sum, and push that to the list.

```
Ｉ⊟υ

```

Cast the last element of the list to string for implicit print.
> 2 votes

# Answer
# **C++, 60 bytes, score : 610**

```
long f(int m){long a=0,b=1;while(b%m){b+=a;a=b-a;}return b;}

```

If I had used `int` all the way, I would have had a score of `591286729879`!

Try it online!
> 2 votes

# Answer
# APL(NARS), chars 44, bytes 88, score 89

```
r←u w
a←1⋄⎕ct←0⋄r←1x
→0×⍳0=w∣r⋄r+←a⋄a←r-a⋄→2

```

The above has the problem change the global variable ⎕ct, and not define the variable 'a' as local (so if there is one extern global variable name 'a' and a extern function use 'a' or ⎕ct even trhu some operation, that extern function could return the wrong result...).

test:

```
  (1..8),¨u¨1..8
 1 1  2 2  3 3  4 8  5 5  6 144  7 21  8 8
  u 70
5358359254990966640871840
  u 89
89
  u 7373
1895175617433302745829870137958720928499852361085393597796453313487
  4796286293483889267053950822315526092023966574765828063258184
  5381860131060934476214808351544411531275197835352771384243811
  1374862903608742278191775434865737602577844700159135211456619
  9731096037977185178018629433653291613989743478589685505639564
  4857727724829027387848536067017682345714489064874396569806069
  164055864141425

```

I copy "r+←a⋄a←r-a" from https://codegolf.stackexchange.com/a/196929/58988
> 2 votes

# Answer
# Ruby, 33 bytes, score 34

```
->n{a=b=1;a=b+b=a until b%n==0;b}

```

Try it online!
> 1 votes

# Answer
# JavaScript (Node.js), 28 bytes, score 377

```
for(a=o=1;o%i;t=a,a+=o,o=t);

```

**Edit:** -2 bytes

Try it online!

Input goes in `i`, output goes in `o`
> 0 votes

# Answer
# C (gcc), 33 bytes, Score:34

Based off xibu's answer.

```
int F(m,a,b){m=a%m?F(m,a+b,a):a;}

```

Try it online!
> 0 votes

---
Tags: math, code-challenge, fibonacci, pristine-programming
---


title: Create a diagonal sudoku board

text:
# Question
Title: Create a diagonal sudoku board
A Diagonal Sudoku board is a special case of Latin squares. It has the following properties:

* The board is a 9-by-9 matrix
* Each row contains the numbers `1-9`
* Each column contains the numbers `1-9`
* Each 3-by-3 sub-region contains the numbers `1-9`
* Both diagonals contains the numbers `1-9`

**Challenge:**

Create a program or function that outputs a complete board with all 81 numbers that complies with the rules above.

The number in at least one position must be random, meaning the result should vary accross executions of the code. The distribution is optional, but it must be possible to obtain at least 9 *structurally different* boards. A board obtained from another by *transliteration* is not considered *structurally* different. Transliteration refers to substituting each number *x* by some other number *y*, consistently in all positions of number *x*.

Hardcoding 9 boards is not accepted either.

**Rules:**

* Output format is optional, as long as it's easy to understand (list of list is OK)
* The random number can be taken as input instead of being created in the script, but only if your language doesn't have a RNG.

This is code golf so the shortest code in bytes win!

**Example boards:**

```
7   2   5  |  8   9   3  |  4   6   1
8   4   1  |  6   5   7  |  3   9   2
3   9   6  |  1   4   2  |  7   5   8
-------------------------------------
4   7   3  |  5   1   6  |  8   2   9
1   6   8  |  4   2   9  |  5   3   7
9   5   2  |  3   7   8  |  1   4   6
-------------------------------------
2   3   4  |  7   6   1  |  9   8   5
6   8   7  |  9   3   5  |  2   1   4
5   1   9  |  2   8   4  |  6   7   3

```

---

```
4   7   8  |  1   9   5  |  3   2   6
5   2   6  |  4   8   3  |  7   1   9
9   3   1  |  6   7   2  |  4   5   8
-------------------------------------
2   5   9  |  8   6   7  |  1   3   4
3   6   4  |  2   5   1  |  9   8   7
1   8   7  |  3   4   9  |  5   6   2
-------------------------------------
7   1   2  |  9   3   8  |  6   4   5
6   9   3  |  5   2   4  |  8   7   1
8   4   5  |  7   1   6  |  2   9   3

```

# Answer
> 4 votes
# SWI-Prolog, 438 bytes

```
:-use_module(library(clpfd)).
a(R):-l(9,R),m(l(9),R),append(R,V),V ins 1..9,transpose(R,C),d(0,R,D),maplist(reverse,R,S),d(0,S,E),r(R),m(m(all_distinct),[R,C,[D,E]]),get_time(I),J is ceil(I),m(labeling([random_value(J)]),R).
l(L,M):-length(M,L).
r([A,B,C|T]):-b(A,B,C),r(T);!.
b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-all_distinct([A,B,C,D,E,F,G,H,I]),b(X,Y,Z);!.
d(X,[H|R],[A|Z]):-nth0(X,H,A),Y is X+1,(R=[],Z=R;d(Y,R,Z)).
m(A,B):-maplist(A,B).

```

Returns the answer as a list of lists, e.g. `a(Z)` unifies `Z` with `[[2, 3, 6, 4, 9, 8, 7, 1, 5], [4, 5, 9, 2, 1, 7, 8, 3, 6], [7, 8, 1, 5, 3, 6, 9, 2, 4], [3, 2, 8, 7, 6, 4, 5, 9, 1], [5, 1, 4, 9, 8, 2, 3, 6, 7], [9, 6, 7, 1, 5, 3, 4, 8, 2], [1, 9, 2, 3, 4, 5, 6, 7, 8], [8, 7, 5, 6, 2, 9, 1, 4, 3], [6, 4, 3, 8, 7, 1, 2, 5, 9]]`.

### Explanation

```
:-use_module(library(clpfd)).          % Constraint Programming Library

a(R):-                                 % Main Predicate
    l(9,R),m(l(9),R),append(R,V),      % R is a list of 9 lists, each of length 9
    V ins 1..9,                        % Values in R are between 1 and 9
    transpose(R,C),                    % C is the transpose of R
    d(0,R,D),                          % D is the diagonal of R
    maplist(reverse,R,S),d(0,S,E),     % E is the anti-diagonal of R
    r(R),                              % All 3*3 blocks must contain numbers from 1 to 9
    m(m(all_distinct),[R,C,[D,E]]),    % Each row of R, each row of C, D and E must contain
                                       % only distinct numbers
    get_time(I),J is ceil(I),          % Set J to a random number based on the current time
    m(labeling([random_value(J)]),R).  % Randomly find a solution for R

l(L,M):-                               % L is the length of M
    length(M,L).

r([A,B,C|T]):-                         % For each group of 3 rows, the 3*3 blocks must
    b(A,B,C),r(T);!.                   % contain distinct numbers

b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-     % Checks that the 3 3*3 blocks of 3 rows have
                                       % distinct numbers inside them
    all_distinct([A,B,C,D,E,F,G,H,I]),
    b(X,Y,Z);!.

d(X,[H|R],[A|Z]):-                     % [A|Z] is the diagonal of [H|R]
    nth0(X,H,A),
    Y is X+1,
    (R=[],Z=R;d(Y,R,Z)).

m(A,B):-
    maplist(A,B).

```

# Answer
> 7 votes
# APL (Dyalog Unicode), 56 bytes

```
(,⊖⍣(?2)↑a(3+⍳3)(10-⌽a←3?3)){⍺ ⍺⌷9 9⍴∊⌽⍵∘.⌽⍵⊖¨⊂3 3⍴⍳9}⍳3

```

Try it online!

A full program that randomly gives a 9-by-9 matrix of digits.

By OP mentioning "it must be possible to obtain at least 9 structurally different boards", I believe it was to prevent using just trivial transformations like reflection and rotation. But there are more possible transformations than that. I use two kinds of transformations:

* Permute R19C19, R28C28 and R37C37 (6 cases)

```
Example: Swap R19C19 and R28C28

a b c - - - A B C     e d f - - - D F E
d e f - - - D E F     b a c - - - A C B
g h j - - - G H J     h g j - - - G J H
- - - - - - - - -     - - - - - - - - -
- - - - - - - - - ==> - - - - - - - - -
- - - - - - - - -     - - - - - - - - -
k l m - - - K L M     l k m - - - K M L
n p q - - - N P Q     s r t - - - R T S
r s t - - - R S T     p n q - - - N Q P

```
* Reverse the order of boxes in both dimensions (2 cases: reverse both or keep intact)

```
a b c - - - A B C     K L M - - - k l m
d e f - - - D E F     N P Q - - - n p q
g h j - - - G H J     R S T - - - r s t
- - - - - - - - -     - - - - - - - - -
- - - - - - - - - ==> - - - - - - - - -
- - - - - - - - -     - - - - - - - - -
k l m - - - K L M     A B C - - - a b c
n p q - - - N P Q     D E F - - - d e f
r s t - - - R S T     G H J - - - g h j

```

resulting in 12 structurally different boards. Note that, in both cases, the thing that changes on the diagonals is the *order* of the digits. Also, the center box is always intact, so no two boards are equivalent under transliteration.

### Part 1: Construct a valid diagonal sudoku board

```
⍝ A 3x3 box of 1..9
⊂3 3⍴⍳9
┌─────┐
│1 2 3│
│4 5 6│
│7 8 9│
└─────┘

⍝ The box rotated upwards 1, 2, 3 times
(⍳3)⊖¨⊂3 3⍴⍳9
┌─────┬─────┬─────┐
│4 5 6│7 8 9│1 2 3│
│7 8 9│1 2 3│4 5 6│
│1 2 3│4 5 6│7 8 9│
└─────┴─────┴─────┘

⍝ The boxes rotated left 1, 2, 3 times
(⍳3)∘.⌽(⍳3)⊖¨⊂3 3⍴⍳9
┌─────┬─────┬─────┐
│5 6 4│8 9 7│2 3 1│
│8 9 7│2 3 1│5 6 4│
│2 3 1│5 6 4│8 9 7│
├─────┼─────┼─────┤
│6 4 5│9 7 8│3 1 2│
│9 7 8│3 1 2│6 4 5│
│3 1 2│6 4 5│9 7 8│
├─────┼─────┼─────┤
│4 5 6│7 8 9│1 2 3│
│7 8 9│1 2 3│4 5 6│
│1 2 3│4 5 6│7 8 9│
└─────┴─────┴─────┘

⍝ Horizontally reverse the boxes, keeping the contents inside the boxes
⌽(⍳3)∘.⌽(⍳3)⊖¨⊂3 3⍴⍳9
┌─────┬─────┬─────┐
│2 3 1│8 9 7│5 6 4│
│5 6 4│2 3 1│8 9 7│
│8 9 7│5 6 4│2 3 1│
├─────┼─────┼─────┤
│3 1 2│9 7 8│6 4 5│
│6 4 5│3 1 2│9 7 8│
│9 7 8│6 4 5│3 1 2│
├─────┼─────┼─────┤
│1 2 3│7 8 9│4 5 6│
│4 5 6│1 2 3│7 8 9│
│7 8 9│4 5 6│1 2 3│
└─────┴─────┴─────┘

⍝ Enlist the digits and reshape into 9x9 matrix
⍝ (Each box goes to each row)
9 9⍴∊⌽(⍳3)∘.⌽(⍳3)⊖¨⊂3 3⍴⍳9
2 3 1 5 6 4 8 9 7
8 9 7 2 3 1 5 6 4
5 6 4 8 9 7 2 3 1
3 1 2 6 4 5 9 7 8
9 7 8 3 1 2 6 4 5
6 4 5 9 7 8 3 1 2
1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3

```

### Part 2: Generate permutation vector

```
,⊖⍣(?2)↑a(3+⍳3)(10-⌽a←3?3)
                    a←3?3   ⍝ Generate a permutation of 1 2 3
                            ⍝ ex) 2 3 1
        a(3+⍳3)(10-⌽a    )  ⍝ Permutation vector in chunks of 3
                            ⍝ ex) (2 3 1)(4 5 6)(9 7 8)
       ↑                    ⍝ Promote to matrix
 ⊖⍣(?2)                     ⍝ Reverse vertically 1 or 2 times
                            ⍝ ex) [9 7 8][4 5 6][2 3 1]
,                           ⍝ Flatten ex) 9 7 8 4 5 6 2 3 1

```

### Part 3: Permute the rows and columns

```
⍝ Permute both rows and columns of the matrix through indexing function
perm perm⌷mat
⍝ Using the example permutation above, the sudoku board is:
3 1 2 7 8 9 5 6 4
9 7 8 4 5 6 2 3 1
6 4 5 1 2 3 8 9 7
8 9 7 6 4 5 1 2 3
5 6 4 3 1 2 7 8 9
2 3 1 9 7 8 4 5 6
4 5 6 2 3 1 9 7 8
1 2 3 8 9 7 6 4 5
7 8 9 5 6 4 3 1 2

```

---
Tags: code-golf, random, sudoku
---


title: Chess960 position lookup

text:
# Question
Title: Chess960 position lookup
This is a follow-up to Chess960 position generator.

In Chess960, there are 960 possible starting positions that can be enumerated from 0 to 959 (or, at your choice, from 1 to 960). The enumeration scheme is defined in http://en.wikipedia.org/wiki/Chess960\_numbering\_scheme:

> White's Chess960 starting array can be derived from its number N (0 ... 959) as follows:
>
> a) Divide N by 4, yielding quotient N2 and remainder B1. Place a **B**ishop upon the bright square corresponding to B1 (0=b, 1=d, 2=f, 3=h).
>
> b) Divide N2 by 4 again, yielding quotient N3 and remainder B2. Place a second **B**ishop upon the dark square corresponding to B2 (0=a, 1=c, 2=e, 3=g).
>
> c) Divide N3 by 6, yielding quotient N4 and remainder Q. Place the **Q**ueen according to Q, where 0 is the first free square starting from a, 1 is the second, etc.
>
> d) N4 will be a single digit, 0 ... 9. Place the K**n**ights according to its value by consulting the following table:
>
> ```
> Digit     Knight positioning
> 0         N   N   -   -   -
> 1         N   -   N   -   -
> 2         N   -   -   N   -
> 3         N   -   -   -   N
> 4         -   N   N   -   -
> 5         -   N   -   N   -
> 6         -   N   -   -   N
> 7         -   -   N   N   -
> 8         -   -   N   -   N
> 9         -   -   -   N   N
>
> ```
>
> e) There are three blank squares remaining; place a **R**ook in each of the outer two and the **K**ing in the middle one.

You can find the complete table at http://www.mark-weeks.com/cfaa/chess960/c960strt.htm.

**Your task:** Write a program that takes an integer as its input and returns the white baseline pieces for that index, e.g.

```
f(1) = "BQNBNRKR"
f(518) = "RNBQKBNR"

```

Or, you might as well use unicode `"♖♘♗♕♔♗♘♖"` if your language supports that.

<sub>For your inspiration, here's a pretty straight-forward (not optimized) JS implementation: http://jsfiddle.net/Enary/1/ </sub>

# Answer
> 5 votes
## GolfScript (100 97 95 91 90 84 80 79 chars)

```
~:?4%2*)?4/4%2*].8,^?16/6%?96/4,{5,>({}+/}%2/=+{1$=.@^}/]'BBQNNRKR'+8/zip${1>}%

```

This approach follows the instructions forwards rather than backwards. Basically it takes an array of indices and repeatedly removes the selected offsets, leaving them further down the stack; at the end, it gathers them together with the letters and uses them to sort.

# Answer
> 6 votes
## Python, 179 chars

```
i=input()
a=i%4*2+1
b=i/4%4*2
c=i/16%6
d=i/96*5
s='NNRKRNRNKRNRKNRNRKRNRNNKRRNKNRRNKRNRKNNRRKNRNRKRNN'[d:d+5]
s=s[:c]+'Q'+s[c:]
if a>b:a,b=b,a
print s[:a]+'B'+s[a:b-1]+'B'+s[b-1:]

```

Builds it backwards from the description order so we don't have to count the spaces that are already taken.

# Answer
> 4 votes
## C, 221 chars

Explanations:

1. The result is accumulated in `r`.
2. `g` calculates division and remainder into `n` and `x`.
3. `p` and `P` write a character in the n'th available slot.

Interesting points:

1. `x~-x` is `2*x+1`.
2. In `!s*!*m`, one `*` serves as `&&`, the other is dereference.
3. `P` uses `s+0`, so with an empty parameter you get `+0`.

The knights calculation is the hardest, and accounts for the longest line. Can probably be improved.

```
char*m,r[9],c;
n,x;
g(r){x=n%r;n/=r;}
p(s){!s*!*m?*m=c:p(s-!*m++);}
#define P(s,t);m=r;c=*#t;p(s+0);
main(){
    scanf("%d",&n);
    g(4)P(x-~x,B)
    g(4);r[x*2]=c;
    g(6)P(x,Q)
    P(n>3?(n-=3)>3?(n-=2)>3?n=3:2:1:0,N)
    P(n,N)
    P(,R)P(,K)P(,R)
    puts(r);
}

```

# Answer
> 4 votes
# Javascript, 230 204 200 chars, with Unicode ♖♘♗♕♔♗♘♖

With ideas from chron's Ruby answer and Keith Randall's Python answer

```
N=prompt();
(r='♘♘♖♔♖♘♖♘♔♖♘♖♔♘♖♘♖♔♖♘♖♘♘♔♖♖♘♔♘♖♖♘♔♖♘♖♔♘♘♖♖♔♘♖♘♖♔♖♘♘'.substr(~~(N/96)*5,5).split(''))[s='splice'](N/16%6,0,'♕');
a=~~(N/4)%4*2;
b=N%4*2;
r[s](a>b?b+1:b,0,B='♗');
r[s](a,0,B);
alert(r.join(''))

```

(and **194 chars** without Unicode)

```
N=prompt();
(r=btoa('4ÔJDÔM)Q(ÔMD¤MDÓJEJ5M)Q(ÓQD£Q54Ó').substr(~~(N/96)*5,5).split(''))[s='splice'](N/16%6,0,'Q');
a=~~(N/4)%4*2;
b=N%4*2;
r[s](a>b?b+1:b,0,B='B');
r[s](a,0,B);
alert(r.join(''))

```

I added both newlines and semicolons for readability. You can remove either of them when determining the character count.

# Answer
> 3 votes
### GolfScript, 109 80 chars

Using Peter's suggestion for an encoding of the string we can reduce the char count considerably.

```
~:§96/'€’ŒŽÈÂÄ°²¸'=3base{'KNR'=}%81§16/6%{.3$<@+@@>+}:^~[§4/4%2*§4%2*)]${'B'\^}/

```

A more or less direct translation of Keith Randall's solution to GolfScript.

# Answer
> 2 votes
## Ruby, 150 + 1 chars

Trying a new approach using gsub and `$_`.

```
n,$_=$_.to_i,?R*8
{B:[n%4*2+1,n/4%4*2],Q:n/16%6,N:[k=(n/=96)/4+n/7-n/8+n/9,k+1+(n+n/7+n/9*2)%4],K:1}.map{|p,l|x=-1;gsub(?R){[*l].include?(x+=1)?p:$&}}

```

This needs to be run with the -p flag, and takes the sequence number on stdin. For example:

```
echo 518 | ruby -p chess960-lookup.rb
RNBQKBNR

```

# Answer
> 2 votes
# x86 machine code, 84 bytes

```
60 4F B9 02 00 BA 03 00 8B D8 23 DA D1 E3 03 D9
C6 01 42 C1 E8 02 E2 F0 33 DB B1 06 F6 F1 FE C4
43 38 29 75 FB FE CC 75 F7 C6 01 51 BB 4A 01 D7
2B DA 47 38 2D 75 FB 32 E4 F6 F2 86 C4 D7 88 05
86 C4 E2 EE AA 61 C3 4B 4E 52 B8 B2 C4 8E B0 C2
8C C8 92 80

```

This is an even more straightforward implementation adapted from LeanChess960.

Rather than calculate indices, it writes directly to the buffer (which is assumed to contain 0s).

I found the LUT approach to be more economical - it only requires 1 byte per arrangement thanks to ternary encoding of the starting positions (0 - K, 1 - N, 2 - R). LeanChess Barebone editions use a trick that may further reduce the code size by transforming a piece type (0..7) to ASCII (K, N, O, P, Q and R), but I was too lazy to find a transform for KNR (0..2).

Assembly source code:

```
gen960:
    pusha
    dec di

bishop:
    mov cx, 2
    mov dx, 3

bish_loop:
    mov bx, ax
    and bx, dx
    shl bx, 1
    add bx, cx
    mov byte ptr [di + bx], 'B'
    shr ax, 2
    loop bish_loop

queen:
    xor bx, bx
    mov cl, 6
    div cl
    inc ah

queen_loop:
    inc bx
    cmp [di + bx], ch
    jne queen_loop
    dec ah
    jne queen_loop
    mov byte ptr [di + bx], 'Q'

knr:
    mov bx, offset knr_db
    xlat
    sub bx, dx

knr_loop:
    inc di
    cmp [di], ch
    jne knr_loop
    xor ah, ah
    div dl
    xchg al, ah
    xlat
    mov [di], al
    xchg al, ah
    loop knr_loop

done:
    stosb
    popa
    ret

K  equ 0
N  equ 1
R  equ 2

    db "KNR"

knr_db:
    db N + N * 3 + R * 9 + K * 27 + R * 81
    db N + R * 3 + N * 9 + K * 27 + R * 81
    db N + R * 3 + K * 9 + N * 27 + R * 81
    db N + R * 3 + K * 9 + R * 27 + N * 81
    db R + N * 3 + N * 9 + K * 27 + R * 81
    db R + N * 3 + K * 9 + N * 27 + R * 81
    db R + N * 3 + K * 9 + R * 27 + N * 81
    db R + K * 3 + N * 9 + N * 27 + R * 81
    db R + K * 3 + N * 9 + R * 27 + N * 81
    db R + K * 3 + R * 9 + N * 27 + N * 81

```

# Answer
> 1 votes
## vba, 472

```
Function f(n)
s="--------"
s=r(s,"B",m(n,4)*2)
n=n\4
s=r(s,"B",m(n, 4)*2-1)
n=n\4
s=r(s,"Q",m(n,6))
n=n\6
Select Case n
Case 0:x=1:y=2
Case 1:x=1:y=3
Case 2:x=1:y=4
Case 3:x=1:y=5
Case 4:x=2:y=3
Case 5:x=2:y=4
Case 6:x=2:y=5
Case 7:x=3:y=4
Case 8:x=3:y=5
Case 9:x=4:y=5
End Select
s=r(s,"N",y)
s=r(s,"N",x)
s=r(s,"R",1)
s=r(s,"K",1)
f=r(s,"R",1)
End Function
Function m(n,q)
m=n Mod q+1
End Function
Function r(s,c,p)
r=Replace(Replace(s,"-",c,,p),c,"-",,p-1)
End Function

```

# Answer
> 1 votes
# Excel, 345 bytes

```
=SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(REPLACE(REPLACE(11111111,2*MOD(A1,4)+2,1,"B"),2*MOD(QUOTIENT(A1,4),4)+1,1,"B"),1,"Q",MOD(QUOTIENT(QUOTIENT(A1,4),4),6)+1),1,"N",CHOOSE(QUOTIENT(QUOTIENT(QUOTIENT(A1,4),4),6)+1,1,1,1,1,2,2,2,3,3,4)),1,"N",CHOOSE(QUOTIENT(QUOTIENT(QUOTIENT(A1,4),4),6)+1,1,2,3,4,2,3,4,3,4,4)),1,"K",2),1,"R")

```

Breakdown for those interested.

For simplicity, first the codes used to determine the Numbers used:

```
{N2} =QUOTIENT(A1,4)
{B1} =MOD(A1,4)                               # For Bishop
{N3} =QUOTIENT(QUOTIENT(A1,4),4)
{B2} =MOD(QUOTIENT(A1,4),4)                   # For Bishop
{N4} =QUOTIENT(QUOTIENT(QUOTIENT(A1,4),4),6)  # For Knights
{Q}  =MOD(QUOTIENT(QUOTIENT(A2,4),4),6)       # For Queen

```

And from the middle outwards:

```
REPLACE(11111111,2*{B1}+2,1,"B")           # Start with String of '1's
                                           # Place the first Bishop

REPLACE(...,
            2*{B2}+1,1,"B")                # Place Second Bishop

SUBSTITUTE(...,                            # Place Queen in Empty Square
           1,"Q",{Q}+1)

SUBSTITUTE(...,                            # Place first Knight
           1,"N",CHOOSE({N4}+1,            # Using a Lookup
           1,1,1,1,2,2,2,3,3,4))

SUBSTITUTE(...,                            # Place Second Knight
           1,"N",CHOOSE({N4}+1,            # Using a Lookup, with
           1,2,3,4,2,3,4,3,4,4))           # index-1 because other Knight already placed

SUBSTITUTE(...,                            # Place King
            1,"K",2)                       # In second Empty Square

SUBSTITUTE(...,1,"R")                      # Rooks in Remaining Squares

```

# Answer
> 1 votes
# Perl 5, 196 bytes

```
sub e{$l=int pop;$i=-1;1until!$r[++$i]&&!$l--;$i}$r[$_/4%4*2]=$r[$_%4*2+1]=B;$r[e$_/16%6]=Q;$r[e$a]=$r[e(($n+1,$n-2,$n-3,4)[$a=substr'0000111223',$n=$_/96,1])]=N;$r[e 0]=$r[e 2]=R;$r[e 0]=K;say@r

```

Try it online!

# Answer
> 0 votes
# IA-32 machine code, 99 bytes

Hexdump:

```
60 68 4e 52 4b 52 68 42 42 51 4e 60 8b fc 8a c1
24 03 d0 e0 40 aa 8a c1 24 0c d0 e8 aa 6a 04 58
91 d3 e8 d4 06 aa 3a e1 72 07 2a e1 49 fe c5 eb
f5 8a c5 aa 02 c4 aa 33 c0 ab 8d 77 17 8b fa ab
ab aa 8b fa 6a 08 59 8a 46 e0 33 db 4b 43 80 3c
1f 00 75 f9 fe c8 7d f5 ac 88 04 1f e2 e9 83 c4
28 61 c3

```

A pretty straightforward implementation of the rules. First, it calculates the index of each piece, in the order specified by the rules. After placing the knights, the indices of Rook, King and Rook (in that order) are 0.

Then, it converts the indices to "absolute indices", taking into account occupied places. Empty places are marked by a zero byte, and occupied places are marked by the name (letter) of the piece.

Division by 4 is implemented by bit-fiddling. After dividing the starting position by 16 (twice by 4), the quotient is smaller than 256, so it's possible to use `aam` to divide by 6.

The positions of the knights are determined by a calculation, not by a LUT - the code seems to be smaller that way.

Assembly source code:

```
    pushad;         // save all registers
    push 'RKRN';    // prepare a LUT of names of pieces
    push 'NQBB';
    pushad;         // allocate temporary variables (values = junk)
    mov edi, esp;   // prepare a pointer to indices of pieces

    // Calculate the index of a Bishop from bits 1 and 0
    mov al, cl;
    and al, 3;
    shl al, 1;
    inc eax;
    stosb;          // store the index of Bishop

    // Calculate the index of a Bishop from bits 3 and 2
    mov al, cl;
    and al, 12;
    shr al, 1;
    stosb;          // store the index of Bishop

    // Divide by 16; also load 4 into ecx
    push 4;
    pop eax;
    xchg eax, ecx;
    shr eax, cl;

    // Divide by 6
    _emit 0xd4;
    _emit 6;
    stosb;          // store the index of Queen

    // Calculate the indices of Knights:
    // Subtract 4, 3, 2, 1 until no longer possible.
    // Knight 1 index: number of times subtraction succeeded
    // Knight 2 index: that, plus remainder
kloop:
    cmp ah, cl;
    jb kdone;
    sub ah, cl;
    dec ecx;
    inc ch;
    jmp kloop;

kdone:
    mov al, ch;
    stosb;          // store the index of Knight
    add al, ah;     // calculate the index of the other knight
    stosb;          // store the index of Knight

    xor eax, eax;
    stosd;          // store indices of Rook, King and Rook

    lea esi, [edi+23]; // point to the names of pieces

    // Fill the output buffer with zeros
    mov edi, edx;
    stosd;
    stosd;
    stosb;
    mov edi, edx;

    // Initialize loop counter for the loop over pieces
    push 8;
    pop ecx;

pc_loop:
    mov al, [esi-32];   // read the index of the piece
    xor ebx, ebx;   // initialize the absolute index
    dec ebx;

pos_loop:
    // Find a zero byte
    inc ebx;
    cmp byte ptr [edi+ebx], 0;
    jne pos_loop;

    // Decrease the index until it hits -1
    dec al;
    jge pos_loop;

    lodsb;          // read the name of the piece
    mov [edi+ebx], al; // store it into the output string

    loop pc_loop;   // repeat for all pieces

    add esp, 40;    // restore stack pointer
    popad;          // restore all registers
    ret;            // return

```

---
Tags: code-golf, combinatorics, chess
---


# Question
Title: Cheat at Rock-Paper-Scissors-Lizard-Spock
When playing Rock-Paper-Scissors-Lizard-Spock, your robot reflexes let you see your opponent's throw before they make it. You just need to choose a throw that beats theirs, in as few bytes as possible of course.

There's always two winning throws, and either one will work.

```
Input    -> Possible outputs
------------------------------
Rock     -> Spock or Paper
Spock    -> Paper or Lizard
Paper    -> Lizard or Scissors
Lizard   -> Scissors or Rock
Scissors -> Rock or Spock

```

Take a string as input, and output one of the strings that beats it. Strings must be exactly as given, with capitalization. List of characters may substitute for strings.

# Answer
# Perl 6, ~~36~~ 30 bytes

```
{<Spock Lizard Rock>[.comb%4]}

```

Try it online!

Gets each output based on the length of the input modulo 4. I think this is probably the optimal strategy.
> 67 votes

# Answer
# Perl 5 `-p`, 28 bytes

```
$_=/k/?Paper:/i/?Rock:Lizard

```

Try it online!

Tried @JoKing's length mod 4 method, but this turned out to be even shorter.
> 21 votes

# Answer
# PHP, 39 bytes

Shorter `md5` variants by Christoph and Benoit Esnard.

```
<?=[Lizard,Spock,Rock][md5(y.$argn)%3];

```

Try it online!

```
<?=[Spock,Rock,Lizard][md5($argn.m)%7];

```

Try it online!

---

# PHP, 40 bytes

```
<?=[Rock,Spock,Lizard][md5($argn)[5]%3];

```

Try it online!

Takes sixth character of md5 of input, which gives unique number of `1` for "Rock" and "Scissors", unique number of `2` for "Spock" and "Paper" and unique number of `9` for "Lizard". A mod 3 on those numbers and we have `0` or `1` or `2` indexes.

```
| Input    | MD5                              | 6th char | %3 | Output |
|----------|----------------------------------|----------|----|--------|
| Rock     | 4cfbb125e9878528bab91d12421134d8 |        1 |  1 | Spock  |
| Spock    | 5769c28299713c949cd59d5469e40ace |        2 |  2 | Lizard |
| Paper    | d0a662a5235ecde30739fe50cf0de830 |        2 |  2 | Lizard |
| Lizard   | 2f7569e00c4d97aef5f2c2b3a4d2213f |        9 |  0 | Rock   |
| Scissors | 28204140cee6e34a9843b64e5a490b08 |        1 |  1 | Spock  |

```

---

# PHP, 40 bytes

Alternative 40 bytes, port of Jo King's answer.

```
<?=[Spock,Lizard,Rock][strlen($argn)%4];

```

Try it online!

---

# PHP, 41 bytes

This is based on 79037662's answer.

```
<?=[Lizard,Rock,Paper][ord($argn[-1])%3];

```

Try it online!

---

# PHP (7.4), 42 bytes

Uses fifth and sixth characters of input to get one of 0, 1 or 2.

```
fn($s)=>[Rock,Lizard,Paper][!$s[5]+!$s[4]]

```

Try it online!

---

# PHP, 43 bytes

Uses CRC32 of input and mod to get 0, 1 or 2.

```
<?=[Rock,Lizard,Paper][crc32($argn)%866%3];

```

Try it online!

---

# PHP, 43 bytes

Uses second to the last character of input ("Rock" and "Spock" = "c", "Paper" = "e", "Lizard" and "Scissors" = "r").

```
<?=[c=>Paper,e=>Lizard,r=>Rock][$argn[-2]];

```

Try it online!
> 13 votes

# Answer
# APL (Dyalog Unicode), 28 bytes

```
'Spock' 'Lizard' 'Rock'⊃⍨4|≢

```

Try it online!

Uses the simple strategy based on input length modulo 4 (idea from Jo King's answer). `⎕IO←0`.

---

# APL (Dyalog Unicode), 34 bytes

```
'Lizard' 'Rock' 'Paper'⊃⍨'Xbj'⍸2∘⊃

```

Try it online!

Uses the shortest choice for all cases. `⎕IO←1`.

### How it works

```
'Lizard' 'Rock' 'Paper'⊃⍨'Xbj'⍸2∘⊃
2∘⊃     Take the second character
'Xbj'⍸  Classify it by intervals:
        'X'≤c<'b': 1
        'b'≤c<'j': 2
        'j'≤c    : 3
...⊃⍨   Give the nth string

```
> 7 votes

# Answer
# Jelly, ~~16~~ 14 bytes

```
Lị“ŀ¡ḋ¤:1KỌ»Ḳ¤

```

Try it online!

-2 bytes thanks to Jonathan Allan and Nick Kennedy both independently coming up with splitting on spaces instead of using a list literal.

A translation of Jo King's Perl 6 solution, using Jelly's compressed strings and modular indexing.

```
 ị                The element of
  “ŀ¡ḋ¤:1KỌ»      "Lizard Rock  Spock"
            Ḳ¤    split on spaces
 ị                at (1-based) index
L                 length of the input
  “ŀ¡ḋ¤:1KỌ»Ḳ¤    mod 4.

```
> 4 votes

# Answer
# JavaScript, 40 bytes

```
s=>['Spock','Lizard','Rock'][s.length%4]

```

Try it online!
> 4 votes

# Answer
# Runic Enchantments, 42 bytes

```
il͍4%:0)9*?~"Spock"@1)9*?"Lizard"@"Rock"@

```

Try it online!

Footer runs all five input possibilities (the `y` sequences make them print in the correct order, no I'm not sure why the last one needed so many) and presets the stack with an input value (the `i`nput command then reads no input) and a newline. Remove the footer to use input instead.
> 3 votes

# Answer
# Python 3, 44 bytes

```
lambda s:["Spock","Lizard","Rock"][len(s)%4]

```

Try it online!

Uses the input-length-modulo-4 strategy in Jo King's answer.
> 3 votes

# Answer
# C (gcc), 51 49 bytes

Thanks to Unrelated String for the suggestion.

The second byte of the string has sufficient uniqueness that I can take its two least-significant bits and use them to then index into a string (with the longest-length result at the end if I rotate the result, fortunately!) The separator between the strings should be a literal `NUL` character, but I put a space in between them below so that you can see the gaps.

```
f(char*s){s="Spock Paper Scissors"+(s[1]-3)%4*6;}

```

Try it online!
> 3 votes

# Answer
# Python 2, ~~73~~ 69 bytes

```
lambda i:l[l.index(i)-1]
l="Rock Lizard Spock Scissors Paper".split()

```

Try it online!

Since there are already plenty of ports of @JoKing's excellent answer, here is a different way of doing it.
> 3 votes

# Answer
# Haskell, 43 bytes

```
(k!!).length
k="Spock":"Lizard":"Rock":"":k

```

Try it online!

The mod-4 approach. Longer approaches:

```
f t|t<"Q"="Scissors"|t<"Sd"="Spock"|1<2="Paper"   (47)
f.last;f 'k'="Paper";f 'r'="Lizard";f _="Rock"    (46)
(["Spock","Lizard","Rock"]!!).(`mod`4).length     (45)
(words"Spock Lizard Rock"!!).(`mod`4).length      (44)
(cycle["Spock","Lizard","Rock",""]!!).length      (44)
(cycle(words"Spock Lizard Rock .")!!).length      (44)

```
> 3 votes

# Answer
# Shakespeare Programming Language, 1359 bytes

(Whitespace added for readability)

```
R.Ajax,.Puck,.Act I:.Scene I:.[Enter Ajax and Puck]Ajax:
Open mind.Open mind.You is the remainder of the quotient betweenyou a big big cat.
Be you nicer a cat?If solet usScene V.
Be you nicer I?If solet usScene X.
You is twice twice twice twice the sum ofa big big cat a cat.Speak thy.You is the sum ofthe sum ofyou a big big big big cat a cat.Speak thy.You is the sum ofthe sum ofyou a big big big big cat a pig.Speak thy.You is the sum ofthe square oftwice the sum ofa big big cat a cat a cat.Speak thy.You is the sum ofyou the sum ofa cat twice twice the sum ofa big cat a cat.Let usScene L.
Scene V:.Ajax:
You is the sum ofa big cat the square ofthe sum ofa big big big cat a cat.Speak thy.You is twice twice twice twice the sum ofa big big big cat a pig.Speak thy.You is the sum ofyou a pig.Speak thy.You is the sum ofyou twice twice the sum ofa big pig a pig.Speak thy.You is the sum ofyou a big big big cat.Let usScene L.
Scene X:.Ajax:
You is the sum ofa big cat the square ofthe sum ofa big big big cat a cat.Speak thy.You is the sum ofyou a big big big big cat.Speak thy.You is the sum ofyou twice the sum ofa big cat a cat.Speak thy.You is the sum ofyou twice the sum ofa big big cat a cat.Remember you.Speak thy.Speak thy.You is the sum ofyou a big big pig.Speak thy.You is the sum ofyou the sum ofa big cat a cat.Speak thy.Recall.
Scene L:.Ajax:Speak thy.

```

Try it online!

Explanation:

I get the second character of the input mod 4:

* This is 0 when the input is `Spock`, at which point Puck is neither nicer than a cat nor nicer than Ajax. Then, Scene I prints `Paper`.
* This is 1 when the input is `Paper` or `Lizard`, at which point Puck is not nicer than a cat, but he is nicer than Ajax. Then, Scene X prints `Scissors`.
* This is 3 when the input is `Rock` or `Scissors`, at which point Puck is nicer than a cat. Then, Scene L prints `Spock`.

Possible improvements:

* Better math when printing to get between the letters, including switching characters and using `Recall` more
* Better modulus because some of the things are longer than others, and I could reuse the `ock`
* Possibly better ways to write the existing numbers. I actually am using a brute forcer that I wrote to do this, but it doesn’t yet account for getting between the letters (using ‘you’). GitHub link coming soon.

This was really fun and I love this language and I have no regrets.
> 3 votes

# Answer
# Retina, ~~30~~ 27 bytes

```
'R(`R
Sp
'i(K`Rock
K`Lizard

```

Try it online! Link includes all possible test cases. @BusinessCat's answer works perfectly well in Retina 0.8.2 but for Retina 1 we can do a little better by using a conditional stage. Explanation:

```
'R(`

```

If the input contains `R`...

```
R
Sp

```

... then replace the `R` with `Sp`, thus turning `Rock` into `Spock`...

```
'i(

```

... otherwise if the input contains `i`...

```
K`Rock

```

... then overwrite it with the string `Rock`, which beats `Lizard` and `Scissors`...

```
K`Lizard

```

... otherwise overwrite the input with `Lizard`, which beats `Spock` and `Paper`.
> 2 votes

# Answer
# Ruby, ~~42~~ 36 bytes

```
->c{%w(Spock Lizard Rock)[c.size%4]}

```

Try it online!

---

# Ruby, ~~43~~ 39 bytes

```
->c{%w(Lizard Rock Paper)[c[-1].ord%3]}

```

Try it online!

The second one is an alternative I found to Jo's method, using the ASCII value of the last character, but alas is 3 bytes longer in Ruby.

It is conceivable that my method is better in some language where finding the ASCII value of the last character is shorter than finding the string's length, but I don't know of any.

EDIT: Saved several bytes thanks to @IMP1
> 2 votes

# Answer
# F# (.NET Core), ~~53~~ ~~49~~ 46 bytes

```
 ["Spock";"Lizard";"Rock"].[String.length n%4]

```

Try it online!

I am using the input-length-modulo-4 strategy from Jo King's answer, so please check his answer.
And I know it's not in competition but I wanted to try something new…
> 1 votes

# Answer
# V (vim), 28 bytes

```
2ORock
Lizard
SpockLÝkYHVGp

```

Try it online!

Hexdump:

```
00000000: 324f 526f 636b 0d4c 697a 6172 640d 5370  2ORock.Lizard.Sp
00000010: 6f63 6b1b 4cdd 6b59 4856 4770            ock.L.kYHVGp

```
> 1 votes

# Answer
# Japt, 24 bytes

```
`Spock Lizd Rock`¸gUÊu4

```

Try it

```
"Spock Lizard Rock" //=>compressed
.q(S) // split on " "
.g(U.l().u(4)) // return element at index ( length of input % 4 )

```

Thanks to @Shaggy for the help
> 1 votes

# Answer
## Python 3, ~~69~~ ~~64~~ ~~61~~ 57 bytes

```
lambda s:[["Scissors","Paper"]['k'in s],"Rock"]['i'in s]

```

Not as short as the mod 4 solution, but not a bad alternative.

Try it online!
> 1 votes

# Answer
# Pyth, 24 bytes

```
@c."Lzž›^ºéëEL”‡"\`lz

```

Try it online!

Port of Jo King's mod-4 answer. Without the compressed string, it's 2 bytes longer: `@c"Spock`Lizard`Rock`"\`lz`
> 1 votes

# Answer
# Excel, 49 bytes

Mod4 approach:

```
=CHOOSE(MOD(LEN(A1),4)+1,"Spock","Lizard","Rock")

```

---

Switching on last character: 57 bytes

```
=CHOOSE(MOD(CODE(RIGHT(A1)),3)+1,"Lizard","Rock","Paper")

```
> 1 votes

# Answer
# R, 52 bytes

```
function(x)c("Spock","Lizard","Rock")[nchar(x)%%4+1]

```
> 1 votes

# Answer
# C# dotnet core, 47 bytes

```
h=>(new[]{"Spock","Lizard","Rock"})[h.Length%4]

```

Try it online

Uses the input-length-modulo-4 strategy in Jo King's answer.
> 1 votes

# Answer
# K, 26 bytes

```
`Paper`Rock`Lizard@&/"ki"?

```
> 1 votes

# Answer
# ///, ~~81~~ 70 bytes

```
/~/\/\/.//.Sp/.~R/.~ock/Paper~Paper/Lizard~Lizard/Rock~Scissors/Rock/.

```

Because there is no other way to take input in ///, it goes after the `.` at the end of the code. For an input of `Spock`:

```
/~/\/\/.//.Sp/.~R/.~ock/Paper~Paper/Lizard~Lizard/Rock~Scissors/Rock/.Spock

```

Try it online!

Test suite

**Explanation:**

/// works by replacing strings with other strings, within the code.

The first chunk of code, `/~/\/\/./`, works as a macro replacing `~` with `//.`. After this, the code expands to:

```
/.Sp/.//.R/.//.ock/Paper//.Paper/Lizard//.Lizard/Rock//.Scissors/Rock/

```

`/.Sp/./` and `/.R/./` change `spock` and `rock` to `ock`, allowing me to just replace `ock` with `Paper`.

The rest of the cases are just explicitly handled.

The period before the input is to make sure that none of the code itself is changed, just the input.
> 1 votes

# Answer
# Python 2, 50 bytes

```
lambda s:["Lizard","Rock","Paper"][cmp(s[-2],"e")]

```

Try it online!
> 1 votes

# Answer
# Wren, 47 bytes

```
Fn.new{|s|["Spock","Lizard","Rock"][s.count%4]}

```

Try it online!

Uses the input-length-modulo-4 strategy in Jo King's answer.
> 0 votes

# Answer
# 05AB1E, 16 bytes

```
”‰«†ÕâŸard”#I3öè

```

Try it online!
> 0 votes

# Answer
# Retina 0.8.2, ~~36~~ ~~33~~ 31 bytes

-3 thanks to Neil

```
R
s
.{6,}
Rock
.{5}
Lizard
s
Sp

```

Try it online!
> 0 votes

# Answer
## Batch, 87 bytes

```
@set/ps=
@for %%a in (Rock.d Rock.s Paper.k Lizard.r)do @if %%~xa==.%s:~-1% echo %%~na

```

Takes input on STDIN. Works by switching on the last character of the input, which saves a case.
> 0 votes

---
Tags: code-golf, string, game
---


# Question
Title: Generate an ASCII art representation of a ribbon plot
Sandbox post

In this challenge, you are provided with a series of y values at even x-values as well as a console width and height. The desired output is an ASCII-art representation of a ribbon plot of the y-values scaled to the desired size. If all values are positive or negative, the x-axis should be displayed at the bottom or top respectively. Otherwise, the x-axis should be displayed at the appropriate position with the graph extending to the top and bottom.

The data should be scaled horizontally by splitting the data into sublists of equal (+/- 1) size and taking the arithmetic mean of each sublist. There will never be fewer values than columns, but can be more.

Inspired by this question which was posed as a tips in C question. Most similar question is here but there are some important differences in terms of input (floats versus equation) and output style.

Default loopholes apply.

## Input/output

* Default I/O rules apply.
* Default loopholes forbidden.
* The y-values will be a list, array or equivalent of floating point numbers at least as long as the width of the console. These may be positive or negative. Choice of float type is at the discretion of the answerer. Y values should be rounded to the nearest integer after scaling to the relevant size; the default rounding method for 0.5s supported by the language is fine (rounding to even, rounding away from zero, etc.) (See Wikipedia for a discussion of different rounding methods if this is an unfamiliar topic.) However, truncation/floor/ceiling are not permitted approaches.
* The range of y values will always be non-zero (i.e. there will be more than 1 y value, and there will be at least 2 different values).
* The console width and height will be two integers, with the height always at least 2.
* The output can be a return value or be output to STDOUT. If opting for a return value, this can be a single newline-separated string, a list of strings, a list of lists of characters or a matrix of characters.
* Any distinct character can be chosen for the filled area, but the blank area should be a space character.
* A separate non-space character should be used to indicate the x-axis.
* Trailing space on each line is optional.

## Worked example of how the data is scaled to width

```
Floats: 1.0,2.0,3.0,4.0,5.0
Width: 3

Split into three pieces: [1,2],[3,4],[5]
Take arithmetic mean of each: [1.5,3.5,5]

```

## Examples of full input/output

Input

```
Floats: [1.4330127018922192, 1.4740546219716173, 1.46726631732171, 1.4118917879852302, 1.3095749615197134, 1.1642846441770978, 0.98209964435211, 0.770867389064186, 0.5397574401179837, 0.29873801741462563, 0.05800851721072442, -0.17257624372014382, -0.38405389828888165, -0.5688402657187754, -0.7211228325469043, -0.8371379250265838, -0.915315134687127, -0.9562812209887335, -0.9627248583907679, -0.939132622452629, -0.8914149315594007, -0.8264477348143321, -0.7515611018951998, -0.6740091786833334, -0.6004570095761375, -0.5365184287338843, -0.48637567624364625, -0.45250583664959154, -0.4355319935803172, -0.43420862005149424, -0.445541730745404, -0.46503530191616943, -0.4870470099638535, -0.5052290073886498, -0.5130237273726901, -0.5041809629881258, -0.47326095136808916, -0.41608900827923856, -0.330130352731954, -0.21475893339455088, -0.07140098112303239, 0.09645778693148394, 0.28340343297327375, 0.4823565362517651, 0.6849507176587676, 0.8820035800170399, 1.0640505126834876, 1.2219075413197402, 1.3472273300168627, 1.433012701892219]
Width: 24
Height: 24

```

Output:

```
#
#                      #
##                     #
##                    ##
##                    ##
##                    ##
###                   ##
###                  ###
###                  ###
###                  ###
####                ####
####                ####
####                ####
####                ####
------------------------
    ###############
     ##############
     ##############
     #############
     #######   ##
      #####
      #####
       ###
       ##

```

Input

```
Floats: [0.5, 3, 7.5, 14, 22.5, 33, 45.5, 60, 76.5, 95, 115.5, 138, 162.5, 189, 217.5, 248, 280.5, 315, 351.5, 390, 430.5, 473, 517.5, 564, 612.5, 663, 715.5, 770, 826.5, 885, 945.5, 1008, 1072.5, 1139, 1207.5, 1278, 1350.5, 1425, 1501.5, 1580, 1660.5, 1743, 1827.5, 1914, 2002.5, 2093, 2185.5, 2280, 2376.5, 2475]
Width: 24
Height: 24

```

Output

```
                       #
                       #
                      ##
                      ##
                     ###
                    ####
                    ####
                   #####
                  ######
                  ######
                 #######
                ########
               #########
               #########
              ##########
             ###########
            ############
           #############
          ##############
        ################
       #################
     ###################
  ######################
------------------------

```

Input

```
Floats: [-4.0,0.0,0.0,4.0,2.0]
Width: 5
Height: 5

```

Output

```
   #
   ##
-----
#
#

```

Input

```
Floats: [0.0,1.0,2.0,3.0]
Width: 4
Height: 4

```

Output

```
    #
   ##
  ###
 ----

```

# Answer
> 3 votes
# Jelly,  ~~40~~  33 bytes

-7 thanks to NickKennedy!

```
œsÆm÷_ṂṀƊ$×⁵’¤ær0r0FṀ‘,_¥ƲṬSz0o⁶Y

```

A full program printing the result to STDOUT with `1`s for bars and `2`s for the x-axis.

**Try it online!**

### How?

```
œsÆm÷_ṂṀƊ$×⁵’¤ær0r0FṀ‘,_¥ƲṬSz0o⁶Y - Main Link: values, width
œs                                - split (values) into (width) chunks
  Æm                              - arithmetic mean (vectorises)
         $                        - last two links as a monad:
        Ɗ                         -   last three links as a monad:
      Ṃ                           -     minimum
     _                            -     (left) subtract (minimum) (vectorises)
       Ṁ                          -     maximum
    ÷                             -   divide (vectorises)
             ¤                    - nilad followed by link(s) as a nilad:
           ⁵                      -   third program argument (height)
            ’                     -   decrement
          ×                       - mutiply (vectorises)
              ær0                 - round to 0 decimal places (vectorises)
                 r0               - inclusive range to zero (vectorises)
                         Ʋ        - last four links as a monad:
                   F              -   flatten
                    Ṁ             -   maximum
                     ‘            -   increment
                        ¥         -   last two links as a monad:
                       _          -     subtract (vectorises)
                      ,           -     pair
                          Ṭ       - untruth (vectorises)  (e.g. 3 -> [0,0,1])
                           S      - sum (vectorises)
                            z0    - transpose with filler zero
                              o⁶  - logical OR with a space character (i.e. replace zeros)
                                Y - join with newline characters
                                  - implicit, smashing print

```

# Answer
> 2 votes
# 05AB1E, 41 bytes

```
äÅAWUZX-I/I<LR*X+©δ@øD®dÏs®d_Ï_¹Å8s)J˜0ð:

```

Inputs in the order `width, [floats], height`.
Outputs as a list of lines with `1` for the bars and `8` for the x-axis.
Also doesn't round at all for more accurate scaling (similar output as the Jelly answer, which differs from the test cases for some bars).

Try it online or verify all test cases. (Uses `»` in the footer to join the resulting list of lines by newlines to pretty-print it. The test suite will have the input-order as `height, width, [floats]` instead.)

**Explanation:**

```
ä                # Split the second (implicit) input-list `floats` into the first (implicit)
                 # input-integer `width` amount of equal-sized parts
 ÅA              # Take the arithmetic mean of every inner sublist
   W             # Push the minimum of this list (without popping the list itself)
    U            # Pop and store it in variable `X`
   Z             # Push the maximum of this list (again without popping the list itself)
    X-           # Subtract the minimum `X` from it
      I/         # Divide it by the third input `height`
        I<L      # Push a list in the range [1, `height`-1]
           R     # Reverse it to [`height`-1, 1]
            *    # Multiply each value by the (max-min)/height we calculated
             X+  # And add the minimum `X`
               © # Store this list of y-axis steps in variable `®` (without popping)
   δ             # Apply double-vectorized on the arithmetic mean and y-step lists:
    @            #  Check >= among the two
     ø           # Zip/transpose this matrix (swapping rows/columns)
      D          # Duplicate it
       ®         # Push the y-steps again from variable `®`
        d        # Check for each whether its non-negative (>= 0)
         Ï       # And only leave those inner sublists of the matrix (top part)
      s          # Swap to get the duplicated list again
       ®d_Ï      # Do the same, but this time for all negative values (bottom part)
           _     # Invert each (0 becomes 1; everything else becomes 0)
      ¹Å8        # Push a list with the first input `width` amount of 8s
         s       # Swap so the stack order is: top-part, x-axis, bottom-part
          )      # Wrap these three into a list
           J     # Join each inner(-most) list of digits to a single string
            ˜    # Flatten it to a single list of string lines
             0ð: # And replace all 0s with spaces
                 # (after which the resulting list of lines is output implicitly as result)

```

# Answer
> 2 votes
# Haskell, ~~324~~ ~~312~~ 298 bytes

```
import Data.List
l=genericLength
(!)=replicate
0#_=[]
w#x=take n x:(w-1)#(drop n x)where n=ceiling(l x/w)
d x=transpose$(++).(!'#')<*>(!' ').(maximum x-).max 0<$>x
w?h=((++).reverse.d<*>((round w)!'-':).d.map(*(-1))).(\x->round.(*(((h-1)/).((-).maximum<*>minimum).(0:))x)<$>x).map((/).sum<*>l).(w#)

```

Try it online!

A lot longer than the other answers, ~~but I would already be happy to get it under 300 bytes.~~ It also gives a slightly different result for test-case 2 (the 16th column is 11 high instead of 10), but I'm not sure how to fix that. I guess it's the difference in rounding methods? Haskell rounds 0.5 to even as far as I know.

# Answer
> 2 votes
# 05AB1E, ~~30~~ 26 bytes

```
äÅAÐδ-àI<//òÝMαεðIиāΘyǝ}øJ

```

Try it online! or validate all test cases.

```
# scale and round the values
ä                # split the list of values in width sublists
 ÅA              # arithmetic mean of each sublist
   Ð             # triplicate
    δ-           # double-vectorized subtraction
      à          # maximum
       I</       # divide by (height - 1)
          /      # divide the list by the result
           ò     # round to nearest integer

# draw the plot
M                # maximum of the stack
 α               # absolute difference of each value with this max
  ε       }      # for each difference y:
   ðIи           #  a space character, repeated width times
      āΘ         #  list [1, 0, 0, 0, ...] (width elements)
        yǝ       #  replace characters at the indices in y
           ø     # transpose
            J    # join

```

# Answer
> 1 votes
# Charcoal, 49 bytes

```
⊞θ⁰≧×∕⊖ζ⁻⌈θ⌊θθ⊟θＦη«≔÷Ｌθ⁻ηιι≦∕ΣＥι⊟θιＰ↑⁺⊘³ιＰ↓⁻⊘³ι←¹

```

Try it online! Link is to verbose version of code. Uses `|` as the drawing character. I'm not sure I've got all of the desired calculations, but I am now using the latest array splitting, which allowed me to save 9 bytes. Explanation:

```
⊞θ⁰≧×∕⊖ζ⁻⌈θ⌊θθ⊟θ

```

Temporarily add a `0` to the array so that the values can be scaled to the desired height.

```
Ｆη«

```

Loop over the width. Although this loop counts up, the array is actually processed from right-to-left.

```
≔÷Ｌθ⁻ηιι

```

Calculate how many array elements to pop.

```
≦∕ΣＥι⊟θι

```

Pop that many elements and calculate the mean.

```
Ｐ↑⁺⊘³ιＰ↓⁻⊘³ι←¹

```

Print the desired amount upwards or downwards as applicable, then print the X-axis in a leftward direction.

---
Tags: code-golf, ascii-art
---


title: Plight of the Concorde

text:
# Question
Title: Plight of the Concorde
# Background

The traveling salesman problem (TSP) asks for the shortest circuit that visits a given collection of cities. For the purposes of this question, the cities will be points in the plane and the distances between them will be the usual Euclidean distances (rounded to the nearest integer). The circuit must be "round-trip", meaning it must return to the starting city.

The Concorde TSP solver can solve instances of the Euclidean traveling salesman problem, *exactly* and much faster than one would expect. For example, Concorde was able to solve an 85,900-point instance exactly, parts of which look like this:

However, some TSP instances take too long, even for Concorde. For example, no one has been able to solve this 100,000-point instance based on the Mona Lisa. (There is a $1,000 prize offered if you can solve it!)

Concorde is available for download as source code or an executable. By default, it uses the built-in linear program (LP) solver QSopt, but it can also use better LP solvers like CPLEX.

# The challenge

What is the smallest TSP instance you can generate that takes Concorde more than *five minutes* to solve?

You can write a program to output the instance, or use any other method you would like.

# Scoring

The fewer points in the instance the better. Ties will be broken by the file size of the instance (see below).

# Standardization

Different computers run faster or slower, so we will use the NEOS Server for Concorde as the standard of measurement for runtime. You can submit a list of points in the following simple 2-d coordinate form:

```
#cities
x_0 y_0
x_1 y_1
.
.
.
x_n-1 y_n-1

```

The settings that should be used on NEOS are "Concorde data(xy-list file, L2 norm)", "Algorithm: Concorde(QSopt)", and "Random seed: fixed".

# Baseline

The 1,889-point instance `rl1889.tsp` from TSPLIB takes "Total Running Time: 871.18 (seconds)", which is more than five minutes. It looks like this:

# Answer
> 18 votes
# 88 Cities, 341 seconds runtime on NEOS

In a recent paper we constructed a family of hard to solve euclidean TSP instances. You can download the instances from this family as well as code for generating them here:

http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html

The 88 city instance from this family takes Concorde on the NEOS server more than 5 minutes. The 178-city instance from this family takes already more than a day to solve.

# Answer
> 10 votes
# 77 cities, 7.24 minutes (434.4 seconds) average run time on NEOS

I’m a little late to the party, but I’d like to contribute a 77-node instance, weruSnowflake77.

I created this instance while trying to understand which local and global characteristics impose an upward pressure on the amount of time concorde takes to match its best lower bound with the length of its shortest found tour.

To construct this instance, I began with a base graph (13 x 13 square), and then systematically introduced new points or translated old points, retaining the adjustments that appeared to make concorde go deeper into its branches on average before cutting.

The technique is similar to the way a genetic algorithm mutates existing tours and retains shorter tours for the next generation of mutations, except the graph itself is being mutated and the harder-to-solve graphs are retained. It's also similar to the way we mutate graphs using relaxations to help construct good lower bounds, except I'm going the opposite way, mutating an existing graph to construct a graph with hard to find lower bounds.

In the process I’ve found a few smaller graphs that take concorde minutes to solve, but this is the first small graph I’ve found that takes concorde a minimum of 5 minutes.

With 10 trial runs on NEOS using the fixed seed and QSopt, the average runtime was 7.24 minutes (434.531 seconds). The minimum runtime was 5.6 minutes (336.64 seconds). The maximum runtime was 8.6 minutes (515.80 seconds). No trials were discarded. Full benchmark table below:

## Benchmark results over 10 runs:

```
----------------------------------
| Run | Job ID# | Total running  |
|     |         | time (seconds) |
|-----|---------|----------------|
| 1   | 7739963 | 513.44         |
| 2   | 7740009 | 336.64         |
| 3   | 7740023 | 514.25         |
| 4   | 7740029 | 447.97         |
| 5   | 7740038 | 357.10         |
| 6   | 7740072 | 447.47         |
| 7   | 7740073 | 336.19         |
| 8   | 7740075 | 515.80         |
| 9   | 7740088 | 361.26         |
| 10  | 7740091 | 515.19         |
----------------------------------

```

weruSnowflake77 (x-y list, L2 norm):

```
77
-700 -700
700 -700
200 0
0 200
-200 0
0 -200
0 0
-600 600
-500 600
-400 600
-300 600
-200 600
-100 600
0 600
100 600
200 600
300 600
400 600
500 600
600 600
-600 -600
-500 -600
-400 -600
-300 -600
-200 -600
-100 -600
0 -600
100 -600
200 -600
300 -600
400 -600
500 -600
600 -600
600 -500
600 -400
600 -300
600 -200
600 -100
600 0
600 100
600 200
600 300
600 400
600 500
-600 -500
-600 -400
-600 -300
-600 -200
-600 -100
-600 0
-600 100
-600 200
-600 300
-600 400
-600 500
-500 -500
-400 -400
-300 -300
-200 -200
-100 -100
100 100
200 200
300 300
400 400
500 500
100 -100
200 -200
300 -300
400 -400
500 -500
-100 100
-200 200
-300 300
-400 400
-500 500
700 700
-700 700

```

## Repository

Problem set files from repo:

* weruSnowflake77.txt (x-y list file, L2 norm)
* weruSnowflake77.tsp (TSPLIB format, EUC\_2D)

# Answer
> 5 votes
# Python 3, 911 cities, 1418 seconds of run time on NEOS

The following Python 3.x script generates the coordinates of 911 cities. It took NEOS 1418 seconds to calculate the shortest path of 47739.

Here is A picture of thee shortest path (thanks to A. Rex):

The code/algorithm is based on the Feigenbaum bifurcation, which I used to generate a series of values, which I used as a basis for generating the coordinates of the cities. I experimented with the parameters until I found a number of cities under 1000 that took NEOS a surprising amount of time (well above the required 5 minutes).

```
x = 0.579
coords = []
for _ in range(1301):
    if int(3001*x) not in coords:
        coords.append(int(3001*x))
    x = 3.8*x*(1-x)
coords = list(zip(coords, coords[::-1]))
print(len(coords))
for coord in coords:
    print(f"{coord[0]} {coord[1]}")

```

PS: I have a script running in search for a lower number of cities that also take \>5 minutes on NEOS. I'll post them in this answer if I find any.

PS: Damn! Running this script with *l* parameter 1811 instead of 1301 results in 1156 cities with a running time on NEOS of just over 4 hours, which is a lot more than other cases with similar parameters...

---
Tags: code-challenge, optimization, busy-beaver, restricted-time
---