title: Making Music Boxes

text:
# Question
Title: Making Music Boxes
Your task is to take a sequence of characters (the music) as input (in a function or program), and print (or return) the music as it would look like in a music box.

You will only receive the characters `ABCDEFG.()` as input, and the input will never be empty. You may also receive the letters in lowercase, if you wish for it.

This is an empty music box, of length 3:

```
.......
.......
.......

```

As you can see, the lines are 7 characters long, and since the length of the music box is 3, we have 3 lines. There are only `.`s here, since the music box is empty. Let's put some music in it!

First, we create the music box. In this example, the input will be `CDAG.DAG`.

The length of `CDAG.DAG` is 8, so we need a music box of length 8:

```
.......
.......
.......
.......
.......
.......
.......
.......

```

Then, we read the input, one character at a time, and place an `O` at its respective position.

The first character is `C`, and the location of each note is equivalent to this (I added spaces for clarity):

```
 A B C D E F G
 . . . . . . .
 . . . . . . .
 (and so on)

```

If the input character is a `.`, then we just print an empty line `.......`

So, the `C` would be the 3rd character along. Let's put it in our music box at the top:

```
..O....
.......
.......
.......
.......
.......
.......
.......

```

We will repeat this process for all the other characters (the text in brackets is just to show you the note, you shouldn't output that):

```
..O.... (C)
...O... (D)
O...... (A)
......O (G)
....... (.)
...O... (D)
O...... (A)
......O (G)

```

Because of how music boxes work, if we use a character other than `O`, `.` and `<insert newline here>`, such as a space, in our output, then it won't play the correct music!

This is a chord:

```
(ACE)

```

This chord is instructing us to play the notes `A`, `C` and `E` at the same time. There will never be a pause (ie a `.`) in a chord.

This is how it would be written:

```
O.O.O...

```

And this is how it might appear in music: `B(ACE)D`

You will never receive a chord in a chord, ie this won't be valid: `(AB(CD)EF)` or this: `A(B())`, and chord will not be empty, ie this won't be valid: `A()B`

You will never receive an invalid input.

### Examples:

```
B(ACE)D

.O.....
O.O.O..
...O...

B

.O.....

GGABC

......O
......O
O......
.O.....
..O....

...

.......
.......
.......

A..F.C(DA).

O......
.......
.......
.....O.
.......
..O....
O..O...
.......

.(ABCDEF)

.......
OOOOOO.

```

Trailing/leading whitespace on the output is permitted.

As this is , the shortest code wins!

# Answer
# Pip, 29 bytes

28 bytes of code, +1 for `-l` flag.

```
'.X7RA_'OMz@?a@`\(\w+.|.`@XL

```

Takes input in lowercase as a command-line argument. Try it online!

### Explanation

```
                              a is 1st cmdline arg; XL is `[a-z]`; z is lowercase alphabet
             a@`\(\w+.|.`     List of all matches in a of this regex:
                               Either a ( followed by letters followed by another
                               character (i.e. the closing paren), or any one character
                         @XL  For each of those matches, a list of all matches of this
                               regex (effectively, split the match into a list of
                               characters and keep only the lowercase letters)
          z@?                 Find index of each letter in the lowercase alphabet
         M                    To that list of lists of indices, map this function:
'.X7                           Take a string of 7 periods
    RA_                        and replace the characters at all indices in the argument
       'O                      with O
                              Finally, autoprint the resulting list, with each item on
                              its own line (-l flag)

```

Here's a sample of how an input is transformed:

```
"b.(ceg)"
["b" "." "(ceg)"]
[["b"] [] ["c" "e" "g"]]
[[1] [] [2 4 6]]
[".O....." "......." "..O.O.O"]

```
> 2 votes

# Answer
# Python 2, ~~95~~ 94 bytes

<sup>-1 byte thanks to Value Ink</sup>

```
x=1
for i in input():
 if x:o=['.']*7
 if'@'<i:o[ord(i)-65]='O'
 if'*'>i:x=i>'('
 if x:print o

```

Try it online! or Try all test cases

### Explanation

`'@'<i` is to check if `i` is a letter, replacing the `.` by `O` on the right position.
`'*'>i` is to check if `i` is a parenthesis, if it is `x=i>'('` will put `0` on `x` to prevent the printing/clearing of `o`, when `i==')'`, it will put `1` on `x` re-enabling the printing/clearing of `o`.
When `i=='.'` nothing will be changed, and `'.......'` will be printed.
The charater order is given by their ASCII code, where `'('<')'<'*'<'.'<'@'<'A'`
> 6 votes

# Answer
## Batch, 209 bytes

```
@set s=%1
@set p=)
@for %%n in (a b c d e f g)do @set %%n=.
:g
@if %s:~,1% lss @ (set "p=%s:~,1%")else set %s:~,1%=O
@set s=%s:~1%
@if %p%==( goto g
@echo %a%%b%%c%%d%%e%%f%%g%
@if not "%s%"=="" %0 %s%

```

Works by accumulating letters and outputting the line if the last symbol seen was not a `(`.
> 4 votes

# Answer
# Röda, ~~97~~ ~~78~~ 76 bytes

```
{search`\(\w+\)|.`|{|c|seq 65,71|{|l|["O"]if[chr(l)in c]else["."]}_;["
"]}_}

```

Try it online!

It's an anonymous function that reads the input from the stream. Use it like this: `main { f={...}; push("ABCD") | f() }`. It uses the regex from ETHproductions' answer.

Ungolfed:

```
{
    search(`\(\w+\)|.`) | for chord do
        seq(ord("A"), ord("G")) | for note do
            if [ chr(note) in chord ] do
                push("O")
            else
                push(".")
            done
        done
        push("\n")
    done
}

```

Previous answer:

```
f s{(s/"(?=([^()]*(\\([^()]*\\))?)*$)")|{|c|seq 65,71|{|l|["O"]if[chr(l)in c]else["."]}_;["
"]}_}

```

Try it online!

It works by splitting the given string at places where the string following contains only matched parentheses. Then, for each chord, it iterates through possible notes and print `O` if the note is a member of the chord and `.` otherwise.
> 4 votes

# Answer
# JavaScript (ES6), ~~86~~ ~~85~~ 76 bytes

*Saved 9 bytes thanks to @Neil*

```
let f =
s=>s.replace(r=/\(\w+\)|./g,x=>`ABCDEFG
`.replace(r,c=>x.match(c)?"O":"."))
```

```
<input oninput="if(/^([A-G.]|\([A-G]+\))+$/.test(value))O.textContent=f(value)"><br>
<pre id=O></pre>
```

### Explanation

First, we match what will form each line of the output: chords, and chars that aren't part of a chord. Then, for each line, we take the string `ABCDEFG\n` and replace each non-newline character in it with an `O` if the line contains it, and a `.` otherwise.
> 4 votes

# Answer
## JavaScript (ES6), ~~118~~ ~~116~~ 114 bytes

```
f=([c,...t],s)=>c?((s?0:x=[...'.......'],c='ABCDEFG)('.indexOf(c))>6?c-7:(x[c]='O',s))?f(t,1):x.join``+`
`+f(t):''

```

### Test cases

```
f=([c,...t],s)=>c?((s?0:x=[...'.......'],c='ABCDEFG)('.indexOf(c))>6?c-7:(x[c]='O',s))?f(t,1):x.join``+`
`+f(t):''

console.log(f("B(ACE)D"))
console.log(f("GGABC"))
console.log(f("..."))
console.log(f("A..F.C(DA)."))
console.log(f(".(ABCDEF)"))
```
> 2 votes

# Answer
# Ruby, ~~78~~ ~~75~~ 71 bytes

```
->x{x.scan(/\(\w+\)|./).map{|x|l=?.*7
x.bytes{|x|x>47?l[x-65]=?O:1};l}}

```

Returns an array of strings.

## Ungolfed + explanation

```
def boxes string
  string.scan(/\(\w+\)|./)    # Split the string into an array of chords.
  .map do |chord|             # Replace each chord with...
    line = '.' * 7            # a line, where by default each character is a '.',
    chord.bytes do |note|     # but for each note in the chord...
      if note > '.'.ord       # (if it is in fact a note and not a dot or paren)
        line[note-65] = 'O'   # replace the corresponding dot with an 'O'.
      end
    end
    line
  end
end

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 30 bytes

```
'.O'[⍉(⍳7)∘.∊⍎⍕⎕A⍳@(~∊∘'()')⎕]

```

Try it online!

Only 1b off the Pip solution, what a shame!

## Explanation

```
'.O'[⍉(⍳7)∘.∊⍎⍕⎕A⍳@(~∊∘'()')⎕]   ⍝
                            ⎕    ⍝ Read input. For below examples, this starts at '(AC).D'
               ⎕A⍳               ⍝ Converts to the index (⍳) of the alphabet (⎕A)...
                  @              ⍝ ... For characters which are...
                   (~∊∘'()')     ⍝ ... Not (~) an element (∊) of '()'. Characters outside the alphabet (e.g. dots) will get index 26
                                 ⍝ e.g. '(AC).D' -> ( 0 2 ) 26 3
              ⍕                  ⍝ Convert the mixed array (numerics and characters) to characters (⍕)
             ⍎                   ⍝ Evaluate this string. This abuses the remaining brackets to work as groups, e.g. ( 0 2 ) 26 3 -> three array elements (0  2) 26 3
          ∘.                     ⍝ For each element, compute the outer product of...
      (⍳7)                       ⍝ Each number 0-6...
            ∊                    ⍝ ... vs a boolean of whether this integer is contained in the corresponding vector. Result is a boolean matrix
     ⍉                           ⍝ Transpose this matrix. The result is now in the correct shape with 1 where 'O' needs to be and 0 where a '.' needs to be
'.O'[                        ]   ⍝ For each element of the boolean matrix, treat it as an index of the string '.O'. This will turn 1 into 'O' and 0 into '.'

```
> 2 votes

# Answer
# Perl, ~~87~~ ~~71~~ 45 + 2 (`-nl` flag) = 47 bytes

```
#!/usr/bin/env perl -nl
use v5.10;
say map$&=~/$_/i?O:".",a..g while/\(\w+\)|./g

```

Using:

```
perl -nlE 'say map$&=~/$_/i?O:".",a..g while/\(\w+\)|./g' <<< "A..F.C(DA)."

```

Try it on Ideone.
> 1 votes

# Answer
# PHP, 171 bytes

```
preg_match_all('#[A-G\.]|\([A-G]+\)#',$argv[1],$m);foreach($m[0]as$l){if($l=='.')echo".......";else foreach([A,B,C,D,E,F,G]as$a)echo strpos($l,$a)!==false?O:'.';echo"\n";}

```

**Breakdown :**

```
preg_match_all('#[A-G\.]|\([A-G]+\)#',$argv[1],$m); // Matches either one character in the range [A-G.] OR multiple [A-G] characters between parentheses
foreach($m[0]as$l)                                  // For each match :
    if($l=='.')                                     //   If no note is played
        echo".......";                              //     Echo empty music line
    else                                            //   Else
        foreach([A,B,C,D,E,F,G]as$a)                //     For each note in the [A-G] range
            echo strpos($l,$a)!==false?O:'.';       //       Echo O i the note is played, . if not
    echo"\n";                                       //  Echo new line
}

```

Try it here!
> 1 votes

# Answer
# Retina, 120 bytes

```
O`(?<=\([^)]*)[^)]
T`L.`d
(?<=\([^)]*)\d
$*x
\)
m¶
+`\b(x+) \1(x+) m
$1 m$2
 m?x

T`x m(`.\O_
\d
$*.O¶
¶
6$*.¶
%7>`.

```

I'm sure there's room for golfing, but it works now, so I'll try to golf it more later.

Try it online!

**How it works**

Basically, the program works by changing each character to a number, then assigning a `O` to that position in a line. It maps `ABCDEFG.` to `01234569`.

To generate the single note lines, all that has to be done is to put an `O` after the corresponding number of `.`s, then pad out the line to 7 characters long.

However, the chords are a bit trickier to do. A similar process is used, but the numbers have to be translated to increments, i.e. the first note in the chord is (whatever), the second is X positions after the first, the third is Y positions after that, etc.

**Code**

```
O`(?<=\([^)]*)[^)]

```

Start out by sorting all characters within chords.

```
T`L.`d

```

Perform the transliteration (mapping) from letters to numbers.

```
(?<=\([^)]*)\d
$*x

```

Replace all digits within brackets with a unary representation (using `x`s), followed by a space.

```
\)
m¶

```

Replace all closing brackets with `m` followed by a newline. The `m` will be used as a marker of sorts for the coming loop:

```
+`\b(x+) \1(x+) m
$1 m$2

```

This is a replacement stage that loops until it can't replace anymore. It takes the last two sequences of `x`s before an `m`, and subtracts the first from the second, moving the `m` back. The marker `m` is needed because it has to perform this operation from right to left.

```
 m?x

```

Remove the first `x` in each sequence except the first one.

```
T`x m(`.\O_

```

`T`ransliterate by replacing `x` with `.`, space with `O`, and deleting `m` and `(`.

At this point, all the lines for the chords have been created. Now the single-note lines have to be created.

```
\d
$*.O¶

```

Replace each digit with that many `.`s, followed by an `O` and a newline.

```
¶
6$*.¶
%7>`.

```

Pad each line to length 7 by adding `.`s to the right. This works by adding 6 `.`s to the end of each line (each line will have at least 1 other character), then replacing every character after the first 7 on each line with nothing. (Since `.` maps to 9, the `O` will be cut out on those lines)
> 1 votes

# Answer
# Retina 0.8.2, 52 bytes

```
\(\w+\)|.
abcdefg$&¶
+`([a-g])(.*)\1
O$2
T`().l`___.

```

Try it online! Takes input in lower case. Explanation:

```
\(\w+\)|.
abcdefg$&¶

```

Split the music into chords or notes, and start building the output by adding the list of note equivalents.

```
+`([a-g])(.*)\1
O$2

```

For each note in each chord, change the output to an `O` and delete the note from the chord.

```
T`().l`___.

```

Delete all the now extraneous music, and change all the unmatched notes to empty.
> 1 votes

# Answer
# 05AB1E, 24 bytes

```
žuS¡2Å€S}˜ε'.7×AySkv'Oyǝ

```

Input with lowercase letters; output as a list of lines.

Try it online or verify all test cases. (The  in the footer is used to pretty-print the output by joining with newlines. Feel free to remove it to see the actual output-list.)

**Explanation:**

```
žu                       # Push builtin string "()<>[]{}"
  S                      # Convert "()<>[]{}" to a list of characters
   ¡                     # Split the (implicit) input by these characters
                         # (NOTE: If the input starts with a "("
                         #  the first item will be an empty string)
    2Å€ }                # For every item at a 0-based index that is divisible by 2:
       S                 #  Convert the string to a list of characters
         ˜               # Flatten the list
          ε              # Map each item to:
           '.7×         '#  Push a string with 7 "."s: "......."
               A         #  Push the lowercase alphabet
                y        #  Push the current item we're mapping over
                 S       #  Convert it to a list of characters
                  k      #  Get the index of each in the alphabet (-1 if it's a ".")
                   v     #  Loop over those indices:
                    'O  '#   Push an "O"
                      yǝ #   Insert it in the "......." string at the current index
                         #   (`ǝ` doesn't work with -1, but still pops the "O" and -1)
                         # (after which the resulting list of lines is output implicitly)

```
> 1 votes

# Answer
# Perl 5 - 78 + 1(flag) + 2(Input Quotes) = 81 Bytes

```
for(;/(\([a-g]+\)|[a-g\.])/g;){$i=$1;print$i=~/$_/?'o':'.'for(a..g);print"\n"}

```

Can be run like so:

```
perl -n <name of file holding script> <<< <input in quotations>

```
> 0 votes

# Answer
# Ruby, 68 bytes

```
->s{w=?.*m=7
s.bytes{|i|i>64?w[i-65]=?O:m=i!=40;m&&(puts w;w=?.*7)}}

```

The idea is to modify the string `.......` every time we find a letter, then output and reset it, but only when we are outside brackets. `(` switches the outputting off. `)` and `.` both switch/leave the outputting on, but the latter is inconsequential as it will never be found inside a bracket.

**Ungolfed in test program**

```
f=->s{w=?.*m=7              #set m to a truthy value (7) and w to seven .'s
  s.bytes{|i|               #for each byte in the string
    i>64?w[i-65]=?O:m=i!=40 #if a letter, modify the appropriate character of w ELSE set m to false if inside brackets, true otherwise.
    m&&(puts w;w=?.*7)      #if m is true, output the contents of w and reset to seven .'s
  }
}

p 1
f["B(ACE)D"]
p 2
f["B"]
p 3
f["GGABC"]
p 4
f["A..F.C(DA)."]
p 5
f[".(ABCDEF)"]

```
> 0 votes

# Answer
# Python 3, 94 bytes

An anonymous function

```
import re
lambda s:[''.join('.O'[c in x]for c in'ABCDEFG')for x in re.findall(r'\(\w+\)|.',s)]

```
> 0 votes

# Answer
# Haskell, 101 bytes

```
c#s|elem c s=c|1<3='.'
s?r=map(#s)"ABCDEFG":p r
p('(':r)|(x,_:t)<-span(')'<)r=x?t
p(x:r)=[x]?r
p e=[]

```

Try it online! Usage: `p "AB.(CA)D"`. Returns a list of strings.

**Explanation:**

The function `p` recurses over the string. If it finds an opening bracket `'('` then `(x,_:t)<-span(')'<)r` partitions the rest string `r` into the strings `x` before the occurrence of the closing bracket `')'` and `t` after it. Otherwise the current character `x` is turned into a string `[x]`. In both cases the function `?` is called with the current string of notes and the rest string. `?` maps the function `#` over the string `"ABCDEFG"`, where `#` replaces all chars that are not in the current string of notes with `'.'`. The resulting music box line is prepended to the recursive call of `p` on the rest list `r`.
> 0 votes

# Answer
# PHP, 93 bytes

```
for($s=$t="
.......";$c=ord($argn[$i++]);$d||$s=$t.!print$s)$c<65?$c-46&&$d=~$c&1:$s[$c&7]=O;

```

Run as pipe with `-nR` or try it online.

**breakdown**

```
for($s=$t="\n.......";      // init
    $c=ord($argn[$i++]);    // loop through characters
    $d||                        // 2. if chord flag is unset
        $s=$t.!print$s)             // then print and reset chord
    $c<65                       // 1. if not note
        ?$c-46                      // and not dot
            &&$d=~$c&1              // then set or clear chord flag
        :$s[$c&7]=O             // else set note in chord
    ;

```
> 0 votes

---
Tags: code-golf, string, parsing
---


title: Non-integer bases

text:
# Question
Title: Non-integer bases
# Description:

A non-integer representation of a number uses non-integer numbers as the bases of a positional numbering system.

e.g. Using the golden ratio (the irrational number 1 + √5/2 ≈ 1.61803399 symbolized by the Greek letter φ) as its base, the numbers `1` to `10` can be written:

```
Decimal Powers of φ             Base φ
1       φ0                      1
2       φ1 + φ−2                10.01
3       φ2 + φ−2                100.01
4       φ2 + φ0 + φ−2           101.01
5       φ3 + φ−1 + φ−4          1000.1001
6       φ3 + φ1 + φ−4           1010.0001
7       φ4 + φ−4                10000.0001
8       φ4 + φ0 + φ−4           10001.0001
9       φ4 + φ1 + φ−2 + φ−4     10010.0101
10      φ4 + φ2 + φ−2 + φ−4     10100.0101

```

Note that just as with any base-n system, numbers with a terminating representation have an alternative recurring representation. In base-10, this relies on the observation that 0.999...=1. In base-φ, the numeral 0.1010101... can be seen to be equal to 1 in several ways:

Conversion to nonstandard form: 1 = 0.11φ = 0.1011φ = 0.101011φ = ... = 0.10101010....φ

One representation in a non-integer base can be found using the greedy algorithm.

# Challenge:

Given a number `n`, a non-integer real base `b` (`1 < b < 10`, **since, as @xnor pointed out in comments, representation in current format would be nonsensical**), and decimal places `l`, output a non-integer representation of `n` in base `b` to `l` decimal places.

# Test Cases:

```
n=10, b=(1 + Sqrt[5])/2, l=5,     ->     10100.01010
n=10, b=E, l=5,                   ->     102.11201
n=10, b=Pi, l=5,                  ->     100.01022
n=10, b=1.2, l=14,                ->     1000000000001.00000000000001
n=10^4, b=Sqrt[2], l=12,          ->     100001000010010000010000100.000000000001

```

Note any valid representation is allowed. e.g.

```
n=450, b=E, l=6,     ->     222010.221120

```

or

```
n=450, b=E, l=6,     ->     1002020.211202

```

# Prohibitions:

Calling Wolfram Alpha or any other external computational site is disallowed. Standard loopholes apply. This is Code Golf, so shortest code wins.

# Answer
# Mathematica, 85 bytes

```
(r=RealDigits[#,#2,9#3];k=r[[2]];s=ToString/@r[[1]];""<>s[[;;k]].""<>s[[k+1;;k+#3]])&

```

# Mathematica, 86 bytes

```
(s=TakeDrop@##&@@RealDigits[#,#2,9#3];FromDigits@s[[1]].""<>ToString/@s[[2]][[;;#3]])&

```

**input**

> \[450,E,6\]
> 2 votes

# Answer
# Python 3, ~~151~~ ~~134~~ 121 120 bytes

```
import math
def f(n,b,l,r=''):
 for i in range(int(math.log(n,b)),-l-1,-1):r+="%i"%(n/b**i)+'.'*(0==i);n%=b**i
 return r

```

Try it online!

Returns a string of the non-integer base representation. This can probably be golfed more; stay tuned.

---

Special thanks to:

* @LeakyNun for saving 13 bytes!
* @Zacharý for saving 1 byte!
> 6 votes

# Answer
# APL (Dyalog Unicode), 47 bytes

```
{⌽⊃∘⍕¨⍺⍺(↑,'.',↓)⌊(⊣,⍨⍺×1|⊢)⍣(⍺⍺+z)⍨⍵÷⍺*z←⌊⍺⍟⍵}

```

Try it online!

A dop that takes `n`, `b`, `l` as  (right arg),  (left arg), `⍺⍺` (left operand) respectively. Does greedy conversion from the most significant digit.

### How it works

```
{⌽⊃∘⍕¨⍺⍺(↑,'.',↓)⌊(⊣,⍨⍺×1|⊢)⍣(⍺⍺+z)⍨⍵÷⍺*z←⌊⍺⍟⍵}  ⍝ ⍵←n, ⍺←b, ⍺⍺←l

⍵÷⍺*z←⌊⍺⍟⍵  ⍝ Part 1
      ⌊⍺⍟⍵  ⍝ Floor of Log of n with base b
            ⍝ (number of digits above decimal point - 1)
    z←      ⍝ Assign to z
⍵÷⍺*        ⍝ Divide n by b^z, so that floor will give highest digit
            ⍝ Let's say the value is k

(⊣,⍨⍺×1|⊢)⍣(⍺⍺+z)⍨k  ⍝ Part 2
(        )⍣(⍺⍺+z)⍨k  ⍝ Repeat l+z times, using k as both the
                     ⍝ left arg (fixed) and right arg (moving)...
      1|⊢  ⍝ Fractional part of right arg
    ⍺×     ⍝ Multiply b
 ⊣,⍨       ⍝ Append left arg
⍝ The net effect is "prepend next significant digit, keeping fractional part"
⍝ Let's say the resulting array is v

⌽⊃∘⍕¨⍺⍺(↑,'.',↓)⌊v  ⍝ Part 3
                ⌊v  ⍝ Floor each number in v
     ⍺⍺(↑,'.',↓)    ⍝ Insert the decimal point after l digits
 ⊃∘⍕¨               ⍝ Convert each digit to a char
⌽                   ⍝ Reverse, so that the highest digit comes first

```
> 1 votes

# Answer
# C (clang), ~~129~~ ~~123~~ ~~121~~ ~~120~~ 118 bytes (115 + `-lm` compiler flag)

```
f(n,b,l,i,y,z)double n,b,l,z;{for(i=log(n)/log(b);~i<l;n=fmod(n,z))z=pow(b,i),printf(".%d"+!!~i--,y=n/z);puts("");}

```

Try it online!

~~7~~ ~~8~~ 10 bytes shaved off thanks to ceilingcat!
> 0 votes

---
Tags: code-golf, number, base-conversion
---


title: Find the longest snake on a grid

text:
# Question
Title: Find the longest snake on a grid
## Background

A **snake** is a path over the cells of a square grid, such that it doesn't touch itself on a side of a unit square. Touching at a corner is allowed.

An example snake:

```
##.#.
.#.##
##..#
#.###
###..

```

Some example non-snakes:

```
###.#
#.#.#
#####
.#...
.####

###
.#.

##
##

```

## Challenge

Given an empty grid with the two endpoints of a snake marked on it, find the longest possible snake that fits on the grid. If there are multiple answers having the same length, you may choose to output one or all of them.

The input can be given as a character matrix (or equivalent) with two endpoints marked on it, or the dimensions (width, height) and the coordinates of the endpoints. You may choose to output the grid containing the snake or a list of coordinates of cells occupied by the snake (or equivalent).

Standard rules apply. The shortest code in bytes wins.

## Example I/O

Each I/O example is given as a character matrix, `#` being the part of the snake.

```
Input:
..#...#...
Output:
..#####...

Input: (corner case)
......
......
..##..
......
......
......
Output: same as input (no way to get longer without violating no-touch condition)

Input:
..#.#
.....
.....
.....
Output:
###.#
#...#
#...#
#####

Input:
#....
.....
.....
.....
....#
Output:
#####
....#
#####
#....
#####

```

# Answer
# Python 3.8 (pre-release), ~~207~~ ~~194~~ 181 bytes

*-7 bytes thanks to @ovs*

### Input

The width \\$ w \\$, the height \\$ h \\$, the starting point \\$ s \\$, and the ending point \\$ e \\$. \\$ s \\$ and \\$ e \\$ are complex numbers which represent the coordinates of the endpoints.

### Output

A list of points, in the form of complex numbers.

---

```
C={1,-1,1j,-1j}
def f(w,h,s,e):P=[[s]];exec("P=[j+[t+(t==e==(A:=j+[t]))]for j in P for k in C if w>(t:=j[-1]+k).real>-1<t.imag<h>0<all({t+l}-{*j}for l in{0}|C-{-k})];"*w*h);return A

```

Try it online!

## Explanation

We use a breadth-first search to search for all possible snakes, starting at \\$ s \\$, making sure that the next tile is not adjacent to any previous tile, and that we do not go past the boundary. After each iteration, we check for all paths whose last element is \\$ e \\$, meaning that we have found a complete path from \\$ s \\$ to \\$ e \\$. Instead of storing all complete paths and returning the one with maximum length, we can simply return the last path found, since breadth-first search already searches for paths by length.
> 5 votes

# Answer
# , ~~275~~ ~~272~~ ~~251~~ ~~229~~ ~~206~~ 197 bytes

```
f=function(p,m){a=p+cbind(-1:0,1:0,0:-1,0:1)
v=m[a<-t(a[,!colSums(!a|a>dim(m))])]
t=sum(!!v)
m[t(p)]=2
`if`(t<3&any(v==1),m,if(t<2)(s<-lapply(split(a,seq(v))[!v],f,m))[[which.max(sapply(s,sum))]])}

```

Try it online!

*Edits 1-4: -69 bytes by using increasingly-arcane golfing obfuscations*

*Edit 5: -9 more bytes by removing useless explicit return of NULL for 'touching' cases, and instead just falling-off the end of the function*

Recursive function:

* find adjacent squares
* count touching squares
* mark position (differently to finish point)
* if touching \< 3 and we're touching the finish: return the matrix
* else if touching \> 1 (it's either a loop or an illegal position): return NULL
* otherwise (there should always be at least one adjacent empty square left)
    + call self recursively with each adjacent empty square to get snakes from this position
    + return the longest snake

Code before golfing:

```
longest_snake=function(pos,matrix){

    # find adjacent squares
    d=dim(matrix)
    adjacent_squares=lapply(list(-1:0,1:0,0:-1,0:1),function(p){n=pos+p;if(all(n>0 & n<=d)){n}})
    adjacent_squares=do.call(rbind,adjacent_squares)

    # count touching squares
    adjacent_vals=matrix[adjacent_squares]
    touching=sum(!!adjacent_vals)

    # mark current position (differently to end, which is 1)
    matrix[pos]=2

    # if touching<3 & pos is touching finish => return matrix
    if((touching<3)&&any(adjacent_vals==1)){ return( matrix ) }

    # else if touching>1 then its either an illegal position or a loop
    else if(touching>1){ return( NULL ) }

    else { # there should always be at least one adjacent empty square

        # now consider each of the adjacent empty squares
        new_pos=lapply(which(adjacent_vals==0),function(i) adjacent_squares[i,,drop=F])

        # get the longest snake from each of them
        snakes_from_here=lapply(new_pos,longest_snake,matrix)

        # and return the longest of these
        longest=which.max(sapply(snakes_from_here,sum))
        return(snakes_from_here[[longest]])
    }
}

```
> 4 votes

# Answer
# , ~~178~~ ~~169~~ ~~164~~ 161 bytes

```
f=function(s,e,w,h,l=length,`/`=c,`*`=`%in%`,k=s[1]-1/-1i/-1/1i)if(!any(s[-2]*k))`if`(e*k,s/e,{for(j in k[Re(k)*1:w&Im(k)*1:h])if(l(F)<l(n<-f(j/s,e,w,h)))F=n;F})

```

Try it online!

This works with complex numbers, similarly to @dingledooper's answer. Inputs are 1-indexed coordinates of start and end points, as well as width and height of the grid. Output is a vector of points which form the snake.

### Explanation

```
f = function(s, e, w, h) # start, end, width, height
{ # Select points to try at next iteration as neighbors of the snake head cell:
  k = s[1] + c(-1,1i,1,-1i)
  # To avoid touches, only proceed if none of k points are already in snake:
  if(!any(s[-2] %in% k)) #s[2] is an exception - this is where we came from
    `if`(e %in% k, # If the neighbors include the endpoint, then...
      c(s,e)       # The loop is closed, add the endpoint to snake and return
      {# Loop through k, filtered so that all points fit in 1:w by 1:h grid:
        for(j in k[Re(k) %in% 1:w & Im(k) %in% 1:h])
        { # Prepend j to snake, and construct it further by recursive call:
          n <- f(c(j, s), e, w, h)
          if(length(F) < length(n))
            F = n # Select the longest snake that we encountered
        }
        F # Return the longest snake
      }
    )
}

```
> 2 votes

# Answer
# Python 3.8 (pre-release), 214 bytes

Takes a 1D boolean array `g` where the endpoints are marked `True`, and returns a 1D boolean array where snake tiles are marked `True`.

Try it online!

```
lambda w,h,g:max((list(map(v,range(w*h)))for x in range(2<<(w*h))if all((v:=lambda i:0<=i<w*h and(g[i]or x>>i&1))(i)==0 or(i%w>0 and v(i-1))+(i%w<w-1 and v(i+1))+v(i-w)+v(i+w)+g[i]==2 for i in range(w*h))),key=sum)

```

---

### Explanation:

```
def f(w, h, g):
    return max(
        (
            # Brute force all possible grid configurations by counting in binary.
            # For each iteration, let the ith binary digit of x signify
            # whether the ith tile is considered part of the snake.
            [v(i) for i in range(w*h)] # <- Return a boolean array.
            for x in range(2<<(w*h))

            # Check if there is a valid snake path.
            if all(
                # The ith tile is part of the path if it's a given endpoint (g[i])
                # or the ith binary digit of x is 1 (x>>i&1).
                ( v:=lambda i:0<=i<w*h and (g[i] or x>>i&1) )(i) == 0
                # For a grid to have a valid snake path,
                # every tile must either not be part of the snake (v(i) == 0)...
                or
                # ...or the tile must have exactly 2 neighbors in the snake path.
                # (If the tile is an endpoint (g[i]), count itself as a neighbor.)
                (i%w>0 and v(i-1)) + (i%w<w-1 and v(i+1)) + v(i-w) + v(i+w) + g[i]
                == 2

                # Repeat this check for every tile.
                for i in range(w*h)
            )
        ),

        # Use max() to find the grid configuration with the most snake tiles;
        # that is, the most times that v(i) == True.
        key=sum
    )

```
> 1 votes

# Answer
# JavaScript (Node.js), 199 bytes

```
s=>(o=g=(t,k,h=c=>t.replace(/2/,c),a=h(0),b=h(1),m=2*~s[0].length)=>a==b?[...a].some((_,i)=>_&1&~1<<B[i]>>a[i-m]>>a[i+m]>>a[i-2]>>a[i+2]|k<o)||(o=k,r=a):g(a,k)|g(b,-~k))(B=JSON.stringify(s))&&eval(r)

```

Try it online!

Seems this way is not that good one
> 1 votes

# Answer
# Charcoal, 76 bytes

```
ＷＳ⊞υι≔⪫υ¶θ≔⟦ω⟧ηＦηＦＥ⁴⁺ικ«Ｊ⁰¦⁰Ｐθ…θ⌕θ@Ｆκ✳⊗λ#¿∧›ＫＫ#‹№ＫＶ#²¿⁼ＫＫ@«#≔ＫＡζ»⊞ηκ»ＵＭＫＡ§ζκ

```

Try it online! Link is to verbose version of code. Takes input as two `@` endpoints in a field of ASCII characters greater than `#` (e.g. `.`). Explanation:

```
ＷＳ⊞υι≔⪫υ¶θ

```

Input the field.

```
≔⟦ω⟧ηＦη

```

Start a breadth-first search with an empty path, and for each path...

```
ＦＥ⁴⁺ικ«

```

... search over the four possible paths formed by concatenating each direction.

```
Ｊ⁰¦⁰Ｐθ…θ⌕θ@

```

Print the field and move to the position of the first endpoint.

```
Ｆκ✳⊗λ#

```

Print the path.

```
¿∧›ＫＫ#‹№ＫＶ#²

```

Test whether the current position is legal (not off the edge, doubled back, or touching itself).

```
¿⁼ＫＫ@«

```

If we reached the other endpoint,

```
#≔ＫＡζ

```

then overwrite it with a `#` and save the canvas.

```
»⊞ηκ

```

Otherwise add this path to the search candidates.

```
»ＵＭＫＡ§ζκ

```

Restore the canvas from the saved last (i.e. longest) path that reached the other endpoint.
> 0 votes

---
Tags: code-golf, grid
---


title: Magic Square, Magic Code

text:
# Question
Title: Magic Square, Magic Code
A magic square is an \\$ n \times n \\$ square grid, such that the sum of the integers on each row and column are equal. Note that the definition which will be used in this challenge is different than the one used by Wikipedia, since

* diagonal sums are not accounted for
* the numbers are not required to be distinct or in the range \\$ 1, 2, ..., n^2 \\$

## Task

Write a program/function such that given an \\$ n \times n \\$ square, return *Truthy* if it is a *magic square*, and *Falsey* otherwise. There is a catch, however. The source code itself must also form a magic square, where each character in the source code corresponds to its *Unicode codepoint*.

## Rules/Clarifications

* You may take input in any reasonable format (e.g. 2D array, flattened list, etc.)
* The source code should be a list of \\$ n \\$ strings, each consisting of \\$ n \\$ characters, joined by newlines.
* The unicode character should be in its *composed* representation.
* Here is a program to check if your program/function is a magic square

This is , so the shortest code in bytes wins!

# Answer
# 05AB1E, 11 bytes

Executed code is the same as this answer. I was extremely lucky all the required characters were in the 05AB1E codepage.

```
ø«O
Ëq¶
/Öí

```

Try it online! Verify it!
> 9 votes

# Answer
# Jelly, 19 bytes

```
§E;Z
Z;E§
E§Z;
;Z§E

```

A monadic Link which yields `1` if the argument is a magic square as per the definition and `0` otherwise. Also works as a full program which prints the result (the first three helper links are actually unused).

The sums of the diagonals of the Unicode characters in the code are also equal to the row and column sums (385).

**Try it online!**

### How?

```
;Z§E - Main Link: list of lists of numbers, M
 Z   - transpose M
;    - M concatenated with that
  §  - sums
   E - all equal?

```
> 8 votes

# Answer
# 05AB1E, 29 bytes

Just a port of the Jelly answer.

```
ø«OËq
qø«OË
Ëqø«O
OËqø«
«OËqø

```

Try it online!

## Explanation

```
ø     Transpose the input
 «    Concatenate with the original input
  O   Sum (vectorizes over sublists)
   Ë  Are these sums all equal?
    q Exit the program (to create a garbage dump)

Now we got a HUGE garbage dump over here.

qø«OË
Ëqø«O
OËqø«
«OËqø

```
> 3 votes

---
Tags: code-golf, grid, source-layout
---


title: Holey Knight's Tour

text:
# Question
Title: Holey Knight's Tour
Given a rectangular board of cells with some number of holes in it, determine whether it is possible to complete a "holey knight's tour" (That is, a path that visits every non-hole cell exactly once using only chess knight moves, not returning to the starting cell) that starts on the top-left cell.

For the sake of completeness of the challenge definition, knights move by teleporting directly to a cell that is two cells away along one axis and one cell along the other axis.

## Examples

Using `.` for open spaces and `X` for holes

### 1

```
. . .
. X .
. . .

```

YES

### 2

```
. . . X
. X . .
. . X .
X . . .

```

NO

### 3

```
. . . . .
X . . . .
. . X . .
. X . . .
. . . . .

```

YES

### 4

```
. . X . .
X . . . X
. . . . .
. X . . .
X . . X X

```

YES

### 5

```
. . . . . .
. . X . . .
. X . . . .
. . . . . .
. . . . . .

```

NO

## Rules and Assumptions

* You must theoretically be able to support boards up to 1000x1000
* Boards do not necessarily have to be square
* As this problem could potentially have exponential time complexity in the worst case, and in an effort to not make testing solutions take forever, board sizes up to 6x6 must return an answer within one minute on modern hardware.
* A board with a hole in the top-left corner (where the knight starts) is always unsolvable

Shortest code wins

# Answer
> 4 votes
# Sledgehammer, 29 bytes

```
⠑⡘⣡⡪⡾⢸⢹⣎⡷⡬⢵⣅⢞⣽⣤⡥⠃⠏⢂⢜⠩⡬⢸⠜⡻⣠⡪⢄⡯

```

That's not very readable, so here's the corresponding Mathematica code:

```
 AnyTrue[Thread@
   FindHamiltonianPath[
    Subgraph[KnightTourGraph[#2, #3],
     o = First /@ StringPosition[#, "."]], 1, o],
  ListQ@# && Length@# > 0 &] &

```

This removes unneeded vertices from the knight's graph (first obtained via KnightTourGraph), calls `FindHamiltonianPath` with all possible end vertices (it either takes nothing and finds *any* Hamiltonian path, or it takes both a start and an end vertex) and checks whether any paths were actually found.

Example input (for the fourth test case)

```
{"..X..X...X......X...X..XX", 5, 5}

```

The first line is a flat version of the grid (obtained by reading it in row-major order).

I have first thought that this doesn't work, but then I investigated and finally found what seems to be a bug in the interpreter: the `hammer.wls` main script doesn't call `postprocess`, and (when decoding) it ends up evaluating the code with all slots (`#, #2, #3`) replaced by variables `s1, s2, s3` :(. Fortunately, the interactive app, while even less convenient, doesn't have this bug.

# Answer
> 2 votes
# Python 3, 166 bytes

```
def f(g,s=[0]):w=len(g[0])+2;k='XX'.join(g)+w*'XXX';*p,x=s;return{*s,'.'}>{*p,k[x]}and any(f(g,s+[x+a])|f(g,s+[x-a])for a in(w+2,w-2,w-~w,w+w-1))|len(s)//k.count('.')

```

Try it online!

Brute force all paths.

Adaptation from my answer to Find the shortest route on an ASCII road.

# Answer
> 1 votes
# , ~~243~~ 213 bytes

*Edit: -30 bytes by merciless code-trimming...*

```
function(p,m,n=1e4,f=function(p,m,x){m[t(p)]=1
d=p+matrix(c(q<-c(1,2,2,1,1,-2,2,-1),-q),2)
`if`(w<-sum(v<-!m[d<-t(d[,!colSums(d<1|d>dim(m))])]),f(d[which(v)[sample(w,1)],],m),!sum(!m))})mean(sapply(1:n,f,p=p,m=m))

```

Try it online!

This is a stochastic algorithm.

The complete search (163 bytes) of all tours on a 6x6 board without holes can require up to approx 36 (positions) x 2^36 (combinations of already-visited squares or holes), which does not run in a \<1 minute time-frame, and even memoising already-tried partial-tours isn't feasible (since unfortunately R vectors are limited to a length of 2^31).

So instead we repeatedly attempt random tours. 1e5 random tours is sufficient to sample the entire, no-hole, 6x6 board and repeatedly find successful tours within 1 minute (although unfortunately not on TIO).

At the cost of 1 wasted byte, the implementation here reports the fraction of successful to unsuccessful attempted tours.

# Answer
> 0 votes
# Perl 5, 305 bytes

```
sub f{my($b,$x,$y)=(@_,1,1);$b=~/.+/;$lx=length$&;$P=sub{($X,$Y)=@_;$X<1||$X>$lx||$Y<1||$Y>$b=~y/\n//?0:($Y-1)*($lx+1)+$X};(!(substr($b,&$P($x,$y)-1,1)=~s,\.,x,)or$b!~/\./)||(any{f($b,@$_)}grep{substr($b,&$P(@$_)-1,1)eq'.'}map[$x+$$_[0],$y+$$_[1]],[2,-1],[2,1],[1,-2],[1,2],[-2,1],[-2,-1],[-1,2],[-1,-2])}

```

Try it online!

---
Tags: code-golf, decision-problem, grid, chess, restricted-time
---


title: The Return of FizzBuzz

text:
# Question
Title: The Return of FizzBuzz
# Intro

Beauty lies in the eye of the beholder. Output lies in the choice of the compiler. There are some codes that give different outputs based on what language they are executed in. Take for instance, the code given below:

```
# include <stdio.h>
# define print(a) int main(){printf("C is better"); return 0;}
print("Python is better")

```

When executed in C, it prints "C is better". When using a python interpreter, it prints "Python is better".

# Challenge

The challenge is a modification of the FizzBuzz challenge. Write a code that gives different outputs based on language it is executed in. When executed with the first language, it prints all numbers from 1 to 1000 (both inclusive) which are not divisible by 2. If a number is divisible by 2, it outputs "FizzBuzz". When executed with the second language, if a number is not divisible by 3, it is printed. Else, the string "FizzBuzz" is printed.

# Example

Output when executed in language 1 would be

```
1 FizzBuzz 3 FizzBuzz 5 FizzBuzz 7 FizzBuzz 9 FizzBuzz ... (upto FizzBuzz 999 FizzBuzz)

```

Output when executed in language 2 would be

```
1 2 FizzBuzz 4 5 FizzBuzz 7 8 FizzBuzz 10 11 FizzBuzz 13 14 FizzBuzz ... (upto 998 FizzBuzz 1000)

```

# Optional Challenge

You can optionally allow the program to execute in more than 2 languages. For the ith language, every multiple of (i+1) is substituted with FizzBuzz. It isn't necessary, but at least 2 languages are compulsory.

# Constraints

Need to write a fully functioning code. For instance, a method/function/procedure alone (which could not independently execute) would not be acceptable

Can use only 1 file

All outputs to be printed to standard output (not to standard error)

All other standard rules of code-golf apply

**EDIT**: Fixed a loophole:

No taking of user inputs during execution

**Edit** I got a comment saying the question wasn't clear if a non-empty separator is mandatory between the numbers. Assume it's not mandatory

# Scoring

Total score = Number of bytes in the program.

# Winning

Consider different participation brackets (based on number of languages being used). Person with least characters in each bracket can be considered a winner.

# Answer
# 05AB1E / 05AB1E (legacy) / 2sable, 27 bytes

```
3°Lv®dтнOÌyDrÖi"FizzBuzz"},

```

2: Try it online in 2sable.
3: Try it online in 05AB1E.
4: Try it online in 05AB1E (legacy).

**Explanation:**

Let's start with a bit of history of these three languages. The development of 05AB1E started at the start of 2016 (or actually, the very first git-commit was on December 21st, 2015). This new codegolf language was being built in Python as backend. Mid 2016 2sable was branched of the 05AB1E version (July 7th, 2016 to be exact), and the strength of 2sable in comparison to that old 05AB1E version was added: implicit inputs. Later on implicit input was also added to 05AB1E, and 2sable was basically a forgotten version right after it was created on that day July 7th, 2016. Then in mid-2018, a new 05AB1E version was being started, this time completely rewritten in Elixir instead of Python, with loads of new builtins added and some builtins changed or even removed.

So, let's go over the code and see what it does in each of the three languages:

```
3°                          # Push 10^3: 1000 (NOTE: I'm unable to use builtin `₄` for
                            # 1000, since it wasn't available in 2sable yet)
  Lv                        # Loop `y` in the range [1,1000] (NOTE: I'm unable to use
                            # builtin `E` for the [1,n] loop, since it wasn't available
                            # in 2sable nor the legacy version yet)
    ®                       #  Push -1
     d                      #  2sable: check if -1 only consist of digits (falsey / 0)
                            #  05AB1E (legacy): check if -1 is an integer (truthy / 1)
                            #  New 05AB1E: check if -1 is non-negative ≥0 (falsey / 0)
      т                     #  2sable: no-op, so does nothing
                            #  05AB1E (legacy) / new 05AB1E: push 100
       н                    #  Pop and push its first character
                            #   2sable: does this for the 0 of the `d` falsey result
                            #   05AB1E (legacy) / new 05AB1E: 100 → 1
        O                   #  Sum all values on the stack:
                            #   2sable: 0
                            #   05AB1E (legacy): 2 (1+1)
                            #   New 05AB1E: 1 (0+1)
         Ì                  #  Increase it by 2
                            #   2sable: 2
                            #   05AB1E (legacy): 4
                            #   New 05AB1E: 3
          yD                #  Push the loop value `y` two times
            r               #  Reverse the values on the stack
             Öi          }  #  If `y` is divisible by the value we calculated earlier:
               "FizzBuzz"   #   Push string "FizzBuzz"
                          , #  Pop and print the top value with trailing newline

```

Note: the `O` to sum the stack will also add the previous value that was divisible (since we've duplicated it with `D`, but only popped and printed `"FizzBuzz"`). But since we know it's divisible, the increased sum in that next iteration doesn't make a difference to the divisibility check.
> 12 votes

# Answer
# Python 2/Python 3, ~~81~~ ~~61~~ ~~57~~ 54 bytes

-20 with thanks to @KevinCruijssen

-4 with thanks to @dingledooper for the idea (prints from 1000 to 1)

-3 with thanks to @Ayxan by losing an unneeded `int`

```
x=1000
while x:print((x,'FizzBuzz')[x%(3/2*2)<1]);x-=1

```

Uses the differences of the `/` operator in Python 2 and 3. In Python 2 `3/2` is `1` (integer division) while in Python 3 it is `1.5`.

Try it online (Python 2)!

Try it online (Python 3)!

# Python 2/Python 3, 81 bytes

```
import sys
print([(x,'FizzBuzz')[x%sys.version_info[0]<1]for x in range(1,1001)])

```

Try it online (Python 2)!

Try it online (Python 3)!

Although it is longer, I am keeping the original as I think it is pretty cool the way the version numbers tie in with the the requirement for 2nd and 3rd elements :-)
> 12 votes

# Answer
# Fortran (GFortran)/Ruby, ~~80~~ ~~79~~ 75 bytes

```
print&!1.upto(1e3)do|i|puts i%3<1?"
*,(i,'FizzBuzz',i=1,999,2)!"[7,8]:i
end

```

Try it online! (Fortran), Try it online! (Ruby)

The Fortran compiler just sees

```
print&
*,(i,'FizzBuzz',i=1,999,2)
end

```

(`!` is the comment character in Fortran). The Ruby interpreter sees the full program, but we hide the otherwise invalid (Fortran) syntax at the start of the second line by wrapping it in a string.
> 11 votes

# Answer
# JavaScript/PHP 5.4+, ~~83~~ 81 bytes

This was a somewhat simple, but fun challenge.

The code is really simple (outputs to the console in JavaScript and to stdout in PHP with `-r`):

```
for($i=0;$i<1e3;)[console.log,'printf'][+![]]("%s\n",++$i%(2+![])?$i:'FizzBuzz');
```

For JavaScript, outputs FizzBuzz on even numbers, while in PHP outputs in multiples of 3.

---

The code picks which function to call to output the value based on `+![]` (previously `+!'0'`).
An empty array (`[]`) (previously was `'0'` \- a string with 0) is a truthy value in JavaScript, but a falsy value in PHP.
An array is an object in JavaScript, and all objects are truthy in JavaScript.
Using this, one can do `![]` to detect if the code is in JavaScript (`false`) or PHP (`true`).
Since Javascript would coerce `false` to a string, the `+` is needed to ensure it is a numeric value.

Using this same value, one can just do `2+![]`, resulting in `3` for PHP (`2+!false` = `2+true` = `3`) and `2` for JavaScript (`2+!true` = `2+false` = `2`).
That value is then used to check if it is a multiple.

The `$i=0` is required because JavaScript will throw an `Uncaught ReferenceError: $i is not defined`.

The `\n` in the output can't be replaced because newlines are line terminators in JavaScript, causing a syntax error if replaced with an actual newline.
Without the `\n`, PHP would output `"12FizzBuzz45FizzBuzz[...]"`.
JavaScript's console ignores it just fine.
> 8 votes

# Answer
# Perl 4, ~~54~~ 48 bytes

```
for(;$i++<1e3;){print$i%(2+true)?$i:'FizzBuzz';}

```

Try it online!

# PHP, ~~54~~ 48 bytes

```
for(;$i++<1e3;){print$i%(2+true)?$i:'FizzBuzz';}

```

Try it online!

Simple: uses PHP's auto conversion from boolean `true` to integer `1` while PERL doesn't

EDIT: saved 3 bytes with a leading space separator instead of a trailing one

EDIT2: saved 6 bytes by removing the separator
> 8 votes

# Answer
# Zsh `+X`/Bash, 58 bytes

```
for i in {1..1000};{ ((i%${#-}))&&echo $i||echo FizzBuzz;}

```

Try it online!

This uses the `$-` parameter, which holds some options used by the shell. By default, it is `569X` in Zsh, and `hB` in Bash. Unsetting the `-X` option in Zsh results in a parameter of `569`. Since `${#-}` is the length of that parameter in both Bash and Zsh, we `%2` in Bash and `%3` in Zsh.

---

# Zsh/Bash, 65 bytes

```
a=(2 3)
for i in {1..1000};{ ((i%a[1]))&&echo $i||echo FizzBuzz;}

```

Zsh: Try it online! Bash: Try it online!

Zsh arrays are one-indexed, Bash arrays are zero-indexed. The surrounding `{ }` in the loop are needed in Bash, not in Zsh.

---

Normally, options count as different languages. However, there is potential for abuse where the options are visible in a parameter. (Ab)Using the `$-` parameter in Zsh allows for a **50 byte** program runnable in 45 "languages" (N = 2..46)
> 5 votes

# Answer
# Perl 5, ~~60~~ 54 bytes

```
for(;$i++<1e3;){print$i%(-1**2+3+true)?$i:'FizzBuzz';}

```

Try it online!

# PHP, ~~60~~ 54 bytes

```
for(;$i++<1e3;){print$i%(-1**2+3+true)?$i:'FizzBuzz';}

```

Try it online!

# Perl 4, ~~60~~ 54 bytes

```
for(;$i++<1e3;){print$i%(-1**2+3+true)?$i:'FizzBuzz';}

```

Try it online!

Another answer, a bit longer with 3 languages!!!

still the same difference with `true` between PHP and PERL, but in PERL 5 and PHP `**` takes precedence over the opposite operator `-`, while the contrary in PERL 4

EDIT: saved 6 bytes by removing the separator
> 5 votes

# Answer
# R (various versions); 74,626 languages; 61 bytes

```
z=1:1000;z[z%%as.double(R.version$`svn rev`)==0]="fizzbuzz";z

```

This answer may be ruled to be illegal depending on whether different svn revisions count as different languages or not.

(Is there a more efficient way to convert text to numeric than `as.double` that will work with the oldest versions of R? I feel like there is, but I cannot remember it.)

This program will continue to work as long as R continues to release versions and the number of languages will increase. I ran this using R 3.5.0.

Haven't included 74,626 TIO links for obvious reasons. here is one for a recent version of R, but it is not very interesting as it is \>1000 in the list, so there are no actual instances of fizzbuzz.
> 5 votes

# Answer
# Befunge-98 / Befunge-93, 55 bytes

```
1+:.:"}"8*-!#@_5j$1+:.1+" zzuBzziF",,,,,,,,,:"}"8*-!#@_

```

Try it in 98! Try it in 93!

This is based on the introduction of `j`ump in Befunge 98. By jumping in 98 the part `1+:.` (add `1`, duplicate, print) is only executed in Befunge 93.
> 3 votes

# Answer
# C 89 (gcc)/C 99 (gcc) 64 bytes

```
i;main(){while(i++<1e3)printf(i%(2//**/
+1)?"%d":"FizzBuzz",i);}

```

Try online (C 89)
Try online (C 99)

**Explanation:**
You can find an explanation on how this works here.
> 3 votes

# Answer
# Io/Erlang (escript), 134 bytes

Outputs a string as a list of codepoints in Erlang. Halts with an error in Io.

```
1%1+1000 repeat(i,if((i+1)%2<1,"FizzBuzz",i+1)println)
main(_)->io:write([if I rem 3<1->"FizzBuzz";1<2->I end||I<-lists:seq(1,1000)]).

```

Try it online! (in Io) Try it online! (in Erlang)
> 2 votes

# Answer
# JavaScript (Node.js), 58 bytes

```
for(i=0;i++<1e3;)console.log(i%(2+(this>{}))?i:'FizzBuzz')

```

Try it online!

# JavaScript (V8), 58 bytes

Try it online!
> 2 votes

# Answer
# Python 2, ~~136~~ ~~133~~ 130 bytes

Saved 3 bytes thanks to ceilingcat!!!
Saved 3 bytes thanks to Abhay Aravinda!!!

```
#define print(a)i;main(){for(;i++<1e3;)printf(i%3?"%d":"FizzBuzz",i);}
print(''.join(i%2and`i`or"FizzBuzz"for i in range(1,1001)))

```

Try it online!

# C (gcc), ~~136~~ ~~133~~ 130 bytes

Saved 3 bytes thanks to ceilingcat!!!
Saved 3 bytes thanks to Abhay Aravinda!!!

```
#define print(a)i;main(){for(;i++<1e3;)printf(i%3?"%d":"FizzBuzz",i);}
print(''.join(i%2and`i`or"FizzBuzz"for i in range(1,1001)))

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~132~~ ~~128~~ ~~101~~ ~~99~~ ~~84~~ ~~82~~ 81 bytes

```
main(){for(int i;i++<1e3;)__builtin_printf(i%(2+sizeof'a'%2)?"%d":"fizzbuzz",i);}

```

Try it online!

# C++ (gcc), ~~132~~ ~~128~~ ~~101~~ ~~99~~ ~~84~~ ~~82~~ 81 bytes

```
main(){for(int i;i++<1e3;)__builtin_printf(i%(2+sizeof'a'%2)?"%d":"fizzbuzz",i);}

```

Try it online!

~~-27~~ -28 bytes from ceilingcat (plus another inspired by ceiling cat)

-15 bytes from Ayxan
> 1 votes

# Answer
# Bash/Perl, 96 bytes

```
eval 'for i in `seq 500`;do echo $((i*2-1))FizzBuzz;done;exit';print$_%3?$_:FizzBuzz for 1..1000

```

This is based on an old Perl trick to get a Perl program to run as Perl, if executed as it were a shell program. If executed in either language, it takes the argument to `eval`, and tries to execute it (Bash) or compile, then execute it (Perl). When run as Bash, it dutifully execute the code, printing the numbers, replacing every second number with FizzBuzz, then exits. Perl, OTOH, tries to compile the string, which fails. It then carries on the execute the second statement, printing out the numbers, replacing every third with FizzBuzz.

Since non-empty separators are allowed, when executed in Bash, there will only be newlines after each FizzBuzz, while when executed in Perl, no whitespace will be outputted at all.

Try it online! (Bash)

Try it online! (Perl)
> 1 votes

# Answer
# Perl -M5.010/C (gcc -w), 112 bytes

```
//;say$_*2-1,Fizzbuzz for 1..500;<<'}';
main(){for(int i=1;i<1001;i++){i%3?printf("%d",i):printf("FizzBuzz");}
}

```

Try it online! (C)

Try it online! (Perl)

This hides the Perl code behind a C++ style comment, and the C code inside a Perl here doc, using the final character of the C code as the here doc terminator. The C++ style comment marker looks like an empty regular expression to Perl, which happily executes it, to no visible effect. Just as the here doc which is in void context.

The C version does not print any whitespace, the Perl version prints a newline after each `FizzBuzz`.
> 1 votes

# Answer
# Befunge-93/Perl -M5.010, 125108 Bytes

```
#  v            .:  <>
say $_*2-1,# >:1+:3%|
#  >:8555***-|
             @
,,,,,,,,"FizzBuzz" #<^
for 1..500

```

Try it online!

Try it online!

This can probably easy golfed down further, but I'm far from a Befunge expert. This code cannot be separated into different pieces of code, where each language ignores the part written in the different language -- the `,,,,,,,,"FizzBuzz"` section is used by both Perl and Befunge.

To explain it further, what Perl sees, after removing the comments, is:

```
say $_*2-1,,,,,,,,,"FizzBuzz" for 1..500

```

and what Befunge sees is:

```
#  v            .:  <>
             >:1+:3%|
   >:8555***-|
             @
,,,,,,,,"FizzBuzz" #<^

```
> 1 votes

# Answer
# JavaScript (Node.js) / Ruby / Python 2 / Python 3 / Perl 5 / PHP \+ `-d short_open_tag=on -d output_buffering=on` / Bash, 311 bytes

```
s=0;f='FizzBuzz';0//1;'''=;y=/.__id__;eval"s+=1;puts s%3>0?s:f;"*1e3;%q}<?ob_end_clean();$i=+1;for(;$i<1e3;){print((++$i%(6+true)?$i:FizzBuzz)."
");};die;#?>";while(s<1e3)console.log(++s%2?s:f)//';for i in {1..1000};{ a=($f);echo ${a[((i%8))]:-$i};} #''';exec('s+=1;print(s if s%(5if 3/2>1else 4)else f);'*1000)

```

Try them all online! (truncates to the first 25 lines of each language)

I know there's no benefit to adding more languages, but I enjoyed this so thought I'd have a try at adding a few. Overall I'd like to share more of the code if possible, but the different looping structures make it pretty tricky. I'm sure there's a way I could share the Python and Ruby code to reduce some bytes, so I'll play with that more next.

# JavaScript (Node.js) (with comments and unused strings removed)

```
s=0;f='FizzBuzz';0
while(s<1e3)console.log(++s%2?s:f)

```

# Ruby (with comments and unused strings removed)

```
s=0;f='FizzBuzz';0//1;'''=;y=/.__id__;eval"s+=1;puts s%3>0?s:f;"*1e3;die;

```

`0//1;.../.__id__;`: this is `0` `/` `/1;.../.__id__` where `/1;.../` is a RegExp and the `__id__` property is just a short property that exists on the RegExp object that returns a number to prevent a type error. This uses string repetition and `eval` as it was slightly shorter (but a true Rubyist might be able to correct me!).

# Python 2 / Python 3 (with comments and unused strings removed)

```
s=0;f='FizzBuzz';0//1;exec('s+=1;print(s if s%(5if 3/2>1else 4)else f);'*1000)

```

This uses the classic floored integer division check for Python 2 vs. 3 and string repetition the same as Ruby because it was shorter (although, again, any Pythonistas please feel free to correct me!)

# Perl 5 \+ `-M5.10.0` (with unused strings removed/truncated)

```
s=...=...=;y=...=...=+1;for(;$i<1e3;){print((++$i%(6+true)?$i:FizzBuzz)."
");};die;

```

This uses Perl's `s///` and `y///` (`tr///`) operators to ignore most of the code. This is the same code as is used for PHP and works because there's no `true` in Perl, so the bareword `true` evaluates to `0`.

# PHP \+ `-d short_open_tag=on -d output_buffering=on` (with non-executed code removed)

```
<?ob_end_clean();$i=+1;for(;$i<1e3;){print((++$i%(6+true)?$i:FizzBuzz)."
");};die;#?>

```

A bit cheaty, but uses a pretty well known technique of the `output_buffering` option and `ob_end_clean()` to discard the content before the first `<?`, then `die;#?>` before the rest of the program is parsed, basically 'hiding' the PHP program within strings and comments of the others. The majority of this code is shared with Perl.

# Bash (with comments and unused strings removed)

```
s=0;f='FizzBuzz';0//1;for i in {1..1000};{ a=($f);echo ${a[((i%8))]:-$i};}

```

Because of how variables are set in Bash (`var=value`) we can share `f='FizzBuzz'` from the JavaScript, Ruby, Python code, but it's pretty much just on its own. The useful thing with Bash is that `'''` isn't a syntax error, it's just concatenating an empty string and the start of a new string, so Bash pretty much just 'ignores' (executes and returns an error) all the code and it's relatively easy to find a space to drop it into.
> 1 votes

# Answer
# Python 2 / Python 3 / Octave, 109 bytes

This is an add-on to @ElPedro's answer, adding Octave to his clever solution for Python 2 and 3.

```
x=1000;
while x>0%1:print((x,'FizzBuzz')[x%(3/2*2)<1]);x-=1;"""
printf('%d FizzBuzz %d ',x,x-1)
x-=3;
end%"""

```

Try it online! (Python 2)

Try it online! (Python 3)

Try it online! (Octave)
> 0 votes

---
Tags: code-golf, polyglot
---


title: Solve the Rook's Round Trip

text:
# Question
Title: Solve the Rook's Round Trip
# The riddle

In yesterday's newspaper, I found a puzzle in which a Rook should start in the lower-left corner of a 12x12 checkerboard and then, during a round trip, visit each field exactly once except for a selection which must be avoided. The puzzle came with a picture that identified the fields to be avoided as black:

After some minutes, I came up with a solution, that you can find here.
(There's no pic of the solution because you might want to challenge yourself by solving it first...)

# The challenge

To write code that produces the same output as my code (that's in TikZ):

```
\documentclass[tikz,border=1cm]{standalone}\def~{document}\begin~\tikz{\def~{)rectangle++(,)(}\filldraw[step=1]grid(12,12)(8,0~4,~0,3~8,5~11,5~,8~11,9~2,10~4,11~7,11~,);\def~#1#2#3{)-|++(6-#1,4-#2)-|++(6-#3,4-}\draw[line width=2mm,red](.5,.5~1355~5353~5356~7540~7375~7575~7375~7373~7372~5555~5553~5552~7375~7373~7345~5355~5555~5355~5272~5395~5673~7373~7583~9555~7955~5555~8376);\fill[blue](.5,.5)circle(.3)}\end~

```

of the picture that shows the solution to the Rook's Round Trip. This is Code Golf!

# Requirement(s) for the In-/Output

* Use whatever language you want.
* From your output, be able to somehow produce the pixelwise
exact same PNG as in the code section below.

PNG code

```
data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAABXoAAAV6AgMAAAAuWCySAAAADFBMVEX///8AAAD/AAAAAP8xSkYMAAAKsklEQVR4Aezdx5HcRhSA4a2aOz2TYBLDEOg6CUSxSeAuRwclsfHotFdZSBiJLftqt7deA0Po+6+vHlDzVcuCM7g4myRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJksqt04s7+D5fYVCiwo0H0eBp82d/0HvAly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvlNylw2+N9z8ixbfZ1NuX5ynL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fC9Tnh/f3jfYePB3rXbfGKVl8IwvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX75840ptWhpLQvVSCRvDMnhbGmrcaLjUi1XOb/tpbD/xD9pP47bnly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvny7v80tLvaN+2KjDb58+fLly5cvX758+fLly5cvX758+fLly5cvX758+W7rG8M3+7bfI//ZbryR8sSZL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fMvNnXzHcmYN02+9Tdi4/aVerHJ+442dnN+nfPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5Zv//reWjfZL5b+0jS9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvvv0DT57341gkP+YmC9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnyzfUttWhpLQ4kb4WBYBm9LXLiRMOh5fkvU7s9vfA++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPnyTfHNf2Nc6Bv2xRobfPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny3YFv1g+r1hIeEwcb6ffgy5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cv31I7oYwlo8RLhQ3LPd6ueo8XDa7Jh8755cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL99gEJa0sf1r3vjy5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5bsD34ZB1j3aP2K8kTqo8eXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLl2+pTUtjqbUMghIuNSyDtyUu3kgfvNjs/Dq/fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5bvpi+G2e81b0C58+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLlW0vYqGU8Jq51HfDly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5dvqZ1QxlKLB3HxRnrDco+3Zc1e/I/P79NmlPAeTz8fX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLlG7bGxhcpvje8Rm8Hvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58k3fCAcBY5ZvwqVqfPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5Vtq09JYGsrbiAfDMngbD+JSLuX81kFQ/qX48uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXL99xe8xb7hn2xwcZmvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58t30wXLDk9rGx8S9L8WXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++5eZOWmM8jzc2aVhu/rbHpV5k+jq/CeeXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPu/GG7717ztwJcvX758+fLly5cvX758+fLly5cvX758+fLly5cvX77pP6waD+KP2P7ZEy7Fly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLtyW+fPny5cuXL1++fPk2dEIZMzbiwbAM3jYMgoKNpsGLO/g+v/vA+eXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly/fM3nN22Xn17ztyZcvX758+fLly5cvX758+fLly5cvX758+fLly5cvX74xymWfB8tBDxoGjShJvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uVbaieUsdTiQVz7Rn7DcvO3d9+IBy/O9PyWqP2fX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fJtq913Wuc1b0G78OXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLl2+tfdDse5n/bLfbBl++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPmW2rQ0lk2Kbz4sg7fxIC5/40X/85s/SDq/TyOjF/nnly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLdx++387z/EM3X77z0lUnRr7351OdGPnOv3fdhZHv/fmPujDyPX7yverAyPcwf+q6AyPf+9X3pw6MfI9zrQMj3/nPrvim+x7+4nvNN933/l98f+rqy3fmm+57/KvvFd9s33k9X77XfJN9Dyv68v2Jb7Lvfb58d+M7T9sU+4a1+7aX4Hvky3c/vt/x/RRfvnxnvnz58uXLly9fvnz5rpv/fuPLly/fqcbX8yG+fDd7fhz0oHkQ++bd47P48yV8r/km+16s6Mv3im+273E9X76pWnz7f7+F76GrL9+Lvt9/43vs+v1Nvve7fv+Y76Hr9+f5XvT9/Qe+x66/D8P3UP/20IGRbz3AV30Y+R7q8eWb7lv/Fa2DFt8K/FO+Ft8gvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvrv0Lbp1v7YHBwQAABAAgEz0f40ZoMqAKQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKAAAO+uutlkASEAAAAASUVORK5CYII=

```

# Bonus imaginary internet points

* Write the code in TikZ
* Your TikZ-code should compile without any errors, warnings, and boxes.
* You should be able to produce a PNG-file with Overleaf that, when saved in the same dimensions, must be able to withstand a bitwise comparsion with my solution.

# Answer
# C (gcc), ~~959~~ ~~947~~ 937 bytes

-12 -10 bytes thanks to ceilingcat!

```
#define Z g&&S(r,c+40,20,q,1)
#define W write(o
H=1402;y=4206;char*s="VDRMOSMWK[I^HaGcFeEgDiCkBlAnAo@p@q?r?s>t>u>u=v=w=w=w<x<x<x<x<x<x<x<x<x=w=w=w=v=v>u>t>t?s?r@q@pAoBmBlCjDhEfFdGbI_J]LYNUPPSJ",*I,d[]="\0o\20\x90\xef",*G=",&&* ,* ,&&*%* %&#%*%*,#,#,&*,*%*)) ) %*%#%*%#%*),*%*,*%*,*)))%*%#%*%#%#)%*%*,*) ,* %*%*%#%#,#%* %*%*,*,#,*),*%*%#%#,#)))%&# ,*,#,#)%&&&&#%# %&#";P[]={0,255,~0<<16,~0},o,C,u,v,i,j,r,c,q=60,z=100;S(a,b,w,h,X){for(h+=a;h/a;h--)for(C=b+w;C/b;)bcopy(P+X,I+h*y+C--*3,3);}main(g){I=memset(malloc(y*H),~0,y*H);for(W=open("a.png",33537),"\x89PNG\r\n\32\n\0\0\0\rIHDR\0\0\5z\0\0\5z\b\2\0\0\0\xDCTSV\0Z\eNIDAT\b\35",43);++i<13;)for(j=0;j<12;8&Z)g=*G++%32,u=j++==5,v=i==7,S(r=i*z+i/7,c=j*z|j>6,z+u,z+v,0),g&&S(r+!v,c+1,98+u,98+v,3),1&Z,r+=40,g&2&&S(r,c,q,20,1),g&4&&S(r,c+40,q,20,1);for(r=61;r--;)S(1281-r,s[r*2]+q,s[r-~r]-q,0,2);for(r=H;r--;I+=W,I,y))*d=!r,W,d,6);W,"\xfc\xa3\xea\xe1\xe8\x93\274a\0\0\0\0IEND\256B`\x82",20);}

```

Try it online!

Each position on the board is stored in the lower four nibbles of the characters of the string `G`. A zero means a black tile, otherwise each bit corresponds to one "arm" of a junction:

```
 0
1 2
 3

```

So a ┌ junction would be stored as the bits 1100, for example.

We simply loop through the string and draw tiles accordingly. Care is taken to match the jankiness that occurs in the middle of the board (slightly wider tiles and therefore everything shifted down/right thenceforth).

Everything is drawn as filled rectangles. An empty tile is just a black rectangle with slightly smaller white rectangle painted over it.

The circle caused some headache; just the data for it takes almost as much as the data for the rest of the board. I tried some circle-drawing methods, but the circle is not symmetrical, so no luck.

Various CRCs and similar are hardcoded, since we will always output the same image.

Stores output to "a.png".
> 4 votes

# Answer
# Mathematica, 1900 bytes

```
"H4sIAAAAAAAACsVWa1ATVxSOtRQNYFqIIkrEgiAUQrQODW0Eq6AFKYICrRQlWKjtqCQgYFA24KPBYcCgqGQwBca3xRaoHQwQWEQwMQOIj9ZYNFlDCA8xWZIAIYQk3bR11D/rdPujO3P3nr3nce+53zlnT1Hsps+c8IvwOBzOKTIifAsOZ3fANt6ajawEbg0oQybH2M/j1yOzFWd7Ic850uJQhJybEZGYhcM5uNjGLNyZHxYiRHtk+Nr43D617JdMZTDxnZR9NyImtnr7ai8G3krYNpd391BUPS1jwIe4/fmnzV6GALVEFFg157jzhHmEbz8HSlkhLD599/nFry2MhWMqf8Comw8CRjwdvMmj0BVdvLoxVdeXUy8WAQ7Fxvln8YX434svxF+xYeO8tGHjvLRh47xiw8ZxHktfRlO7gSwXYplH8B/a8g9aCqWWj9YeQhQQKVUX798SVE0ePbj0PYhOmHhXy6a0cO3R1ZIvwaknTMpVbI+2RIlpP+jm68ZhYdwbIaJNS9Yo6jtz4jy1Z8tIV8H6Isf58G1STWWaVcRKBcRtxx4dk+aHjmGzruoybGRfzu0hp3JPehfKd/LPHUHX0U8PytU7p0RDV1gC/r2V06IK7Bc78ngm9Ajc3FT/03RMg9/9E7R4msRCboymZFlBjLeFEMxuqiH9+hPu4TDvzf0kdPHtJczhM40p4sgdfdWRmHekQFlAqazDWRq91I5WxkmgPwofjNjX6RBkYO4tvwVDJR9PYXZHcJDZ/q28DIxb7ej67CmqCtxgFNUVnSQ1URvsKGyHO+2Y3eGPhzQ7+Y5eCsfPO91dU526asQ9XWJeDGVPYgYbMObHXdF1JzHEYbvUcdno4WroA8I497JKmnzyCbtb9ZiBgd3AnvcRXHqknQ6SzqNfTXCi07hp4uF1u62feGDGJC8ETFhSyFdUCGLt0YXreqih8de89i92b/PhEoKab/wHRNLnucU+7JEuQxyh9SdOZO054/dAPmZhO51fNpSLPXTpoFSZpHJrfcI96gk29Q5r0YE5wL48HOyXNuOorgC/KezHnjFmy6OQgEzZ21vqvRK3IrhcON49fJax3yoqyMzpjsVcLVV5ib0t3mwloSNB84ZsaQF/TQ4Ykv/GbfKppRIxxzXzvsDIfufnHJeIlvMpX5gH+IvCGrzZaqjZhB0SqpI22pFB+LEh5h56EkP+OnJu9MxuSHzbWSnt1J7FXmgM7lCJo++oJ0lys4ayx5OT1h9WSexbBcAbiM+xJ70OAfmhrX5lhehF6K5ETbJLiPjkgOUUtpLjF1iOOQS6WG3MV5IFv/P3GNDvfuaW7yjZVh/XQQA9LtBCxmlK5KJrrX5WIfiQ0PGGTFnHRioxZxskXsQSvqneodnxYZcWk8obGYORe3W2PwteUqKxeSLnLC+FIempzcIZPUpzY1gNrWmuNRUzg6DaXgdoI+hxhCkWlMEEuaaCOR+yXoczZ+vJz4TmcbYiqZ1lkOQFL50qHw9xJ8hcIDx4VKnIwOnJI3kD5tUHjQvGZeYBU7egERbHgDHA1el9QLGJIaTYr4AOgyRoBKg2LpiUaSvvGoqYOyACCLgqH8t6T11gis6nN4Fa4phMpxK6Q2v+OtgDgfK18xYUIN91BdbWXXRDGMBT0sTmTB2eKjiuoB3g+lus3gLb1vVwFfw9SAGiTAzjpiHhUFIfaxIWBDxhiQU1cL4GbiPLWDS9gcrTmFbqDaU8jZBvNOmjDLLeGROh2CC7YzKtQKZKdwLQNZ3PeOoK5gAsKwQCDibLlFdfFZMMFRyqngRGjcmxaD0jIrfh2oMqhb/d/9Dkvr7laSZgnbVnKNulsP9gkK3bj1y/Kbx2XcrhPwH+UUsXJwwAAA=="~ImportString~"Base64"

```

I tried to use the grid-board to my advantage, and it still probably would be, but the thicknesses of the lines seem to very by 1 px either way, making this a likely comparable solution in length.
> 2 votes

# Answer
# Python 2, ~~3864~~ ~~3846~~ ~~3832~~ 3815 bytes

I’m new, so I could use help shortening it. It outputs to a file in the same folder called i.png.

`from base64 import*
open('i','wb').write(b64decode("iVBORw0KGgoAAAANSUhEUgAABXoAAAV6AgMAAAAuWCySAAAADFBMVEX///8AAAD/AAAAAP8xSkYMAAAKsklEQVR4Aezdx5HcRhSA4a2aOz2TYBLDEOg6CUSxSeAuRwclsfHotFdZSBiJLftqt7deA0Po+6+vHlDzVcuCM7g4myRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJkiRJksqt04s7+D5fYVCiwo0H0eBp82d/0HvAly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvlNylw2+N9z8ixbfZ1NuX5ynL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fC9Tnh/f3jfYePB3rXbfGKVl8IwvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX75840ptWhpLQvVSCRvDMnhbGmrcaLjUi1XOb/tpbD/xD9pP47bnly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvny7v80tLvaN+2KjDb58+fLly5cvX758+fLly5cvX758+fLly5cvX758+W7rG8M3+7bfI//ZbryR8sSZL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fMvNnXzHcmYN02+9Tdi4/aVerHJ+442dnN+nfPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5Zv//reWjfZL5b+0jS9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvvv0DT57341gkP+YmC9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnyzfUttWhpLQ4kb4WBYBm9LXLiRMOh5fkvU7s9vfA++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPnyTfHNf2Nc6Bv2xRobfPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny3YFv1g+r1hIeEwcb6ffgy5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cv31I7oYwlo8RLhQ3LPd6ueo8XDa7Jh8755cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL99gEJa0sf1r3vjy5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5bsD34ZB1j3aP2K8kTqo8eXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLl2+pTUtjqbUMghIuNSyDtyUu3kgfvNjs/Dq/fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5bvpi+G2e81b0C58+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLlW0vYqGU8Jq51HfDly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5dvqZ1QxlKLB3HxRnrDco+3Zc1e/I/P79NmlPAeTz8fX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLlG7bGxhcpvje8Rm8Hvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58k3fCAcBY5ZvwqVqfPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5Vtq09JYGsrbiAfDMngbD+JSLuX81kFQ/qX48uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXL99xe8xb7hn2xwcZmvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58t30wXLDk9rGx8S9L8WXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++5eZOWmM8jzc2aVhu/rbHpV5k+jq/CeeXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPu/GG7717ztwJcvX758+fLly5cvX758+fLly5cvX758+fLly5cvX77pP6waD+KP2P7ZEy7Fly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLtyW+fPny5cuXL1++fPk2dEIZMzbiwbAM3jYMgoKNpsGLO/g+v/vA+eXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly/fM3nN22Xn17ztyZcvX758+fLly5cvX758+fLly5cvX758+fLly5cvX74xymWfB8tBDxoGjShJvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uVbaieUsdTiQVz7Rn7DcvO3d9+IBy/O9PyWqP2fX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fLly5cvX758+fJtq913Wuc1b0G78OXLly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLl2+tfdDse5n/bLfbBl++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPny5cuXL1++fPmW2rQ0lk2Kbz4sg7fxIC5/40X/85s/SDq/TyOjF/nnly9fvnz58uXLly9fvnz58uXLly9fvnz58uXLdx++387z/EM3X77z0lUnRr7351OdGPnOv3fdhZHv/fmPujDyPX7yverAyPcwf+q6AyPf+9X3pw6MfI9zrQMj3/nPrvim+x7+4nvNN933/l98f+rqy3fmm+57/KvvFd9s33k9X77XfJN9Dyv68v2Jb7Lvfb58d+M7T9sU+4a1+7aX4Hvky3c/vt/x/RRfvnxnvnz58uXLly9fvnz5rpv/fuPLly/fqcbX8yG+fDd7fhz0oHkQ++bd47P48yV8r/km+16s6Mv3im+273E9X76pWnz7f7+F76GrL9+Lvt9/43vs+v1Nvve7fv+Y76Hr9+f5XvT9/Qe+x66/D8P3UP/20IGRbz3AV30Y+R7q8eWb7lv/Fa2DFt8K/FO+Ft8gvnz58uXLly9fvnz58uXLly9fvnz58uXLly9fvrv0Lbp1v7YHBwQAABAAgEz0f40ZoMqAKQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKAAAO+uutlkASEAAAAASUVORK5CYII="))`

I could use advice on shortening it. This is the first time I have ever done anything like this.
> 2 votes

---
Tags: code-golf, kolmogorov-complexity, graphical-output
---


title: Placing Dominoes On A Chequerboard

text:
# Question
Title: Placing Dominoes On A Chequerboard
How many ways can one place (unlabelled) dominoes on a square chequerboard such that the number placed horizontally is equal to the number placed vertically?

The dominoes must align with, and may not protrude, the chequerboard and may not overlap.

This is OEIS sequence A330658, `1, 1, 1, 23, 1608, 371500, 328956227, 1126022690953, ...`

### Challenge

Given the side length of the chequerboard, \\$n\\$, produce the number of ways to arrange dominoes as described above, \\$a(n)\\$, in as few bytes as possible in your chosen programming language. Alternatively you may use any of the defaults.

You do not have to handle \\$n=0\\$
If you're producing a list/generator/etc. it may start either:

* `1, 1, 23, 1608, ...` or,
* `1, 1, 1, 23, 1608, ...`

### A Worked Example, \\$n=3\\$

There are \\$23\\$ ways to place an equal number of horizontal and vertical dominoes on a three by three board. Here they are represented as `0` where no dominoes lie and labelling cells where distinct dominoes lie as positive integers:

There is one way to place zero in each direction:

```
0 0 0
0 0 0
0 0 0

```

There are twenty ways to place one in each direction:

```
1 1 0   1 1 0   1 1 0   1 1 2      0 0 2      2 0 0      2 1 1   0 1 1   0 1 1   0 1 1
2 0 0   0 2 0   0 0 2   0 0 2      1 1 2      2 1 1      2 0 0   2 0 0   0 2 0   0 0 2
2 0 0   0 2 0   0 0 2   0 0 0      0 0 0      0 0 0      0 0 0   2 0 0   0 2 0   0 0 2

2 0 0   0 2 0   0 0 2   0 0 0      0 0 0      0 0 0      0 0 0   2 0 0   0 2 0   0 0 2
2 0 0   0 2 0   0 0 2   0 0 2      1 1 2      2 1 1      2 0 0   2 0 0   0 2 0   0 0 2
1 1 0   1 1 0   1 1 0   1 1 2      0 0 2      2 0 0      2 1 1   0 1 1   0 1 1   0 1 1

```

There are two ways to place two in each direction:

```
1 1 2   2 1 1
3 0 2   2 0 3
3 4 4   4 4 3

```

There are no ways to place more than two in each direction.

\\$1+20+2=23 \implies a(3)=23\\$

# Answer
> 6 votes
# APL (Dyalog Extended), 61 bytes

```
{+/∊{(∪≡⊢)¨(,2,/m)[M],.,⍉C[M←⍵⌂cmat≢C]}¨0,⍳≢C←,2,⌿⊢m←⍵⊥¨⍳,⍨⍵}

```

Try it online!

Finally got how to circumvent the funky inner assignment on Extended ;-)

The difference with the one below is that `dfns` is auto-loaded under , and a no-op is added after assignment into `m`.

I have a 68-byte Unicode and 60-byte Extended solution by rewriting from scratch; it is left as an exercise for the reader.

---

# APL (Dyalog Unicode), ~~72~~ 69 bytes

```
⎕CY'dfns'
{+/∊{(∪≡⊢)¨(,2,/m)[M],.,⍉C[M←⍵cmat≢C]}¨0,⍳≢C←,2,⌿m←⍵⊥¨⍳,⍨⍵}

```

Try it online!

Non-recursive brute force. This works the other way around: generate all possible horizontal/vertical domino placements, generate all possible combinations of `n` horizontal and `n` vertical placements, and count the ones that don't have any duplicated cells.

### Ungolfed with comments

```
⎕CY'dfns'  ⍝ Load dfns library to access function "cmat"

f←{  ⍝ Main function; ⍵←1-based index n (does not handle 0)

  m←⍵⊥¨⍳,⍨⍵  ⍝ n-by-n matrix of unique integers
        ,⍨⍵  ⍝ [n n]
       ⍳     ⍝ Nested matrix having [1..n;1..n]
    ⍵⊥¨      ⍝ Compute n×i+j for each cell containing [i j]

  R←,2,/m  ⍝ Horizontal domino placements
     2,/m  ⍝ From the matrix m, pair horizontally consecutive cells
    ,      ⍝ Flatten the outermost layer to make it a nested vector
  C←,2,⌿m  ⍝ Vertical domino placements, using ⌿ instead of /

  +/(0,⍳≢R){M←⍺cmat⍵⋄+/(∪≡⊢)¨,R[M],.,⍉C[M]}¨≢R  ⍝ Count the placements
    (0,⍳≢R){                              }¨≢R  ⍝ For each ⍺←0..length(≢) of R with ⍵←R,
            M←⍺cmat⍵                        ⍝ Generate all combinations to use for R and C
                    ⋄        ,R[M],.,⍉C[M]  ⍝ Concatenate all combinations of R with all combinations of C
                     +/(∪≡⊢)¨  ⍝ Count the ones whose cell values are all unique
  +/  ⍝ Sum all the counts
}

```

# Answer
> 4 votes
# Charcoal, ~~88~~ ~~84~~ 66 bytes

```
Ｎθ⊞υ⁰ＦυＦ×¹⁵Ｘ⁴⊖Φ×θθ﹪κθＦ∧¬＆ικ×θ⊖θ«≔×Ｘ⁴λ⊕Ｘ⁴θη≧｜ικ¿¬∨＆κη№υ｜κη⊞υ｜κη»ＩＬυ

```

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

```
Ｎθ

```

Input `n`.

```
⊞υ⁰

```

Start the list of results with an empty chequerboard of size `n`. This is represented using an integer in base 4 of  digits with each digit representing an element of the array in row-major order, `0` for empty, `1` for half of a vertical domino and `3` for half of a horizontal domino. (`2` is unused, but that's code golf for you.)

```
Ｆυ

```

Perform a breadth-first search of chequerboards.

```
Ｆ×¹⁵Ｘ⁴⊖Φ×θθ﹪κθ

```

Consider all squares of the current chequerboard that are not on the left column, then decrement the index, giving the squares that are not on the right column, then convert to a pair of base 4 digits `33` representing a horizontal domino on those two squares.

```
Ｆ∧¬＆ικ×θ⊖θ«

```

Check whether those squares are empty on the current chequerboard. If so, then consider all of the squares of the current chequerboard, except for the bottom row.

```
≔×Ｘ⁴λ⊕Ｘ⁴θη

```

Calculate the base 4 digits corresponding to a vertical domino at that square.

```
≧｜ικ

```

Merge the current chequerboard with the current horizontal domino.

```
¿¬∨＆κη№υ｜κη⊞υ｜κη

```

If the vertical domino does not overlap the merged chequerboard and the domino arrangement including the vertical domino has not yet been seen then add it to the list.

```
»ＩＬυ

```

Output the number of arrangements found.

# Answer
> 4 votes
# JavaScript (ES6),  ~~150 133~~  126 bytes

```
n=>(g=(a,k=0,y=n,x,h=d=>a[(b=[...a])[y-!~d]|=m=2+d<<x,y]&m?0:g(b,k+~~d,y,-~x))=>(x%=n)||y--?h()+(y&&h(-1))+(x^n-1&&h(1)):!k)``

```

Try it online!

### Commented

The board is described as an array of \\$n\\$ bit masks. We start at \\$(0,n-1)\\$ and attempt to put either a horizontal domino, a vertical domino or no domino at all at each position, going from right to left and bottom to top:

$$\begin{matrix} (n-1,0)&\cdots&(1,0)&(0,0)\\ (n-1,1)&\cdots&(1,1)&(0,1)\\ \vdots&&\vdots&\vdots\\ (n-1,n-1)&\cdots&(1,n-1)&(0,n-1) \end{matrix}$$

For horizontal dominoes, we test the bits at \\$(x,y)\\$ and \\$(x+1,y)\\$ and set both of them if the location is available. For vertical dominoes, we only test the bit at \\$(x,y)\\$ and set the one at \\$(x,y-1)\\$ if the location is available.

The helper function \\$h\\$ is used to process the tests and the recursive calls to its parent function \\$g\\$ in the scope of which it's defined:

```
h = d =>                // helper function taking a direction d:
                        //   -1 = vertical, undefined = no domino, 1 = horizontal
  a[                    // test a[]:
    (b = [...a])        //   b[] = copy of the current board
    [y - !~d] |=        //   apply the mask m to either b[y] or b[y - 1]
      m =               //   set m to:
        2 + d << x,     //     3 << x for horizontal, 1 << x for vertical,
                        //     or 0 for no domino (NaN << x)
    y                   //   test a[y]
  ] & m ?               // if there's a collision:
    0                   //   do nothing and leave the final result unchanged
  :                     // else:
    g(                  //   do a recursive call to g:
      b,                //     use the updated board
      k + ~~d,          //     add d to k
      y,                //     leave y unchanged
      -~x               //     increment x
    )                   //   end of recursive call

```

Below is the main recursive function \\$g\\$:

```
g = (                   // main recursive function taking:
  a,                    //   a[] = board
  k = 0,                //   k = counter which is incremented when a horizontal
                        //       domino is put on the board and decremented when
                        //       a vertical domino is used
  y = n, x,             //   (x, y) = current position
  h = ...               //   h = helper function (see above)
) =>                    //
  (x %= n) ||           // turn x = n into x = 0
  y--                   // decrement y if x = 0
  ?                     // if we haven't reached the end of the board:
    h() +               //   try to put no domino
    (y && h(-1)) +      //   if y > 0, try to put a vertical domino
    (x ^ n - 1 && h(1)) //   if x < n - 1, try to put a horizontal domino
  :                     // else:
    !k                  //   return 1 if k = 0 (meaning that we've put as many
                        //   horizontal dominoes as vertical ones)

```

# Answer
> 3 votes
# Jelly, ~~38~~ 31 bytes

-7 bytes thanks to Jonathan Allan

```
’»1p⁸U+Ø.żƊŒPẈĠịƊpU$€ẎḅFQƑɗ€⁹S‘

```

TIO can run successfully for `n=1,2,3`, but it times out for `n>3` since this is a brute force solution. I have verified `n=4` on my computer.

Try it online!

### Commented

```
’»1p⁸U+Ø.żƊŒPẈĠịƊpU$€ẎḅFQƑɗ€⁹S‘  # main link
’  p³                            # [1..n-1] Cartesian product with [1..n]
 »1                              # [1..n] x [1..n] if n=1 to avoid empty list output
     U                           # reverse, yielding list of pairs from ex. [1,1] to [3,2] for n=3 (tops of vertical dominoes)
      +Ø.                        # add [0,1] to each pair to get coordinates of bottoms of vertical dominoes
         żƊ                      # zip with the tops list to get a list of pairs of pairs: [[[1,1], [1,2]], ...]
           ŒPẈĠịƊ                # take the powerset to get all possible vertical dominoes, and group these subsets by length
                   U             # switch coordinates to get grouped horizontal domino sets
                  p $€           # Cartesian product of each set of horizontal dominoes with each set of vertical dominos of the same count
                      Ẏ          # tighten to get a single list of domino sets
                       ḅFQƑɗ€⁹   # 1 for each set pair if it is a valid arrangement of dominoes, otherwise 0 (check for no repeat coordinates)
                              S‘ # sum to find the count of valid arrangements, and increment for the case where there are no 0's

```

# Answer
> 3 votes
# Clingo, 98 bytes

```
{v(1..n,2..n)}.{h(2..n,1..n)}.:-{v(I,J)}=C,{h(I,J)}!=C.:-I=1..n,J=1..n,2{v(I,J..J+1);h(I..I+1,J)}.

```

Wow, I'm just describing the problem, and it's still bigger than most of the more explicit solutions!

A commented version:

```
% Select some positions for vertical dominoes,
% v(I,J) is meant to also cover (I,J-1).
{v(1..n,2..n)}.

% Select some positions for horizontal dominoes,
% h(I,J) is meant to also cover (I-1,J).
{h(2..n,1..n)}.

% Constraints:

% The selections must not have different sizes:
:- {v(I,J)}=C,{h(I,J)}!=C.

% No position can be covered by two or more dominoes:
:- I=1..n,J=1..n,2{v(I,J..J+1);h(I..I+1,J)}

```

Save the program in a file `dom.lp` and give `n` as command line argument as shown below. The result is the number of models reported.

Here is an example run:

```
$ clingo -c n=5 dom.lp -q 0
clingo version 5.1.0
Reading from dom.lp
Solving...
SATISFIABLE

Models       : 371500
Calls        : 1
Time         : 2.519s (Solving: 2.51s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 2.510s

```

`-q` stops `clingo` from printing solutions, `0` tells it to search for all solutions. Performance can be increased with the option `--config=frumpy`. With it, I was able to compute `n=6` in 48 min.

In Debian, clingo is in the `gringo` packet.

---
Tags: code-golf, sequence, combinatorics
---


title: Fizz! Buzz! 'ave a banana!

text:
# Question
Title: Fizz! Buzz! 'ave a banana!
Here's one for fans of Cabin Pressure. There is an episode in which the characters devise a new version of Fizz Buzz, which is simplified to contain absolutely no mathematics.

It has these rules:

* If someone says "fizz", you say "buzz".
* If someone says "buzz", you sing "'ave a banana"
* If someone says your name, you say "fizz".

The result is that whenever a name is uttered, that person says "fizz" and the sequence has to run to completion.

---

Let's write some code.

I'd like you to write a program/function/whatever which works thus:

* It accepts one single string of text as input.
* If the string equals the name of the language your code is written in, it outputs "fizz".
* If the string equals "fizz", it outputs "buzz".
* If the string equals "buzz", it outputs "'ave a banana" (note the apostrophe at the start).
* If the input is not one of these things, it should terminate.
* Here's the kicker: The output string must go to two places.
* + Output to be seen by the user
* + Back into your code as input
* I don't really care if they are output in each iteration, or build a string for eventual output.
* Outputs must be separated by new lines (in console or result string)

# Rules

* This is code golf, write in any language you like and attempt to make your code as small as possible.
* Standard loopholes apply.
* I'd like to see links to an online interpreter.
* The language name can be a full name or common short-form of the language the answer is written in. E.g. JS is acceptable, but shortening Ruby to R is not).

# Test Cases

Input

```
'buzz'

```

Output

```
'ave a banana

```

---

Input

```
'fizz'

```

Output

```
buzz
'ave a banana

```

---

Input

```
ruby # or the name of the language your answer is written in

```

Output

```
fizz
buzz
'ave a banana

```

---

Input

```
something else

```

No output

# Answer
# perl -M5.010 -n, 47 bytes

```
"Perl\nfizz\nbuzz\n'ave a banana"=~/\b$_/;say$'

```

Try it online!

Prints whatever is following the input, or nothing if there is no match. Assumes input is newline terminated.
> 12 votes

# Answer
# Jelly, 26 bytes

```
“Çȥȧ>$ỌĿɦ@⁴Ƙ½Æ/ṠṫḞƇ»Ỵṣ⁸ḊẎY

```

**Try it online!**

### How?

```
“...»Ỵṣ⁸ḊẎY - Link: list of characters, W
“...»       - compressed string = "Jelly\nfizz\nbuzz\n'ave a banana"
     Ỵ      - split at newlines = ["Jelly","fizz","buzz","'ave a banana"]
      ṣ     - split at:
       ⁸    -   chain's left argument, W  e.g. "Jelly" -> [[],["fizz","buzz","'ave a banana"]]
        Ḋ   - dequeue                                   = [["fizz","buzz","'ave a banana"]]
         Ẏ  - tighten                                   = ["fizz","buzz","'ave a banana"]
          Y - join with new lines                       = "fizz\nbuzz\n'ave a banana"

```
> 7 votes

# Answer
# Bash, 63 bytes

```
bash=fizz
fizz=buzz
buzz="'ave a banana"
echo ${x=${!1}}&&$0 $x

```

Try it online!

This requires `.` to be in your `PATH`. If that's not acceptable, then replace `$0` with `./$0` (assuming the program is being run from the current working directory) at the cost of 2 bytes (65 bytes total).

Input is passed as an argument, output is on stdout. The language name is entered as `bash`.

(There's spurious output to stderr, but that's OK under our generic rules.)
> 6 votes

# Answer
# 05AB1E, ~~46~~ 33 bytes

```
’
05AB1E
fizz
ÒÖ
'ž™ a æé’I¶.ø¡¦θ

```

-13 bytes by porting *@Abigail*'s Perl answer, so make sure to upvote her!!

Outputs `[]` for invalid inputs.

Try it online.

**Original 46 bytes approach:**

```
"fizz"U•äƵí•hRQiX=}XQi'ÒÖ=}'ÒÖQi’'ž™ a æé’,}õ?

```

Outputs nothing for invalid inputs.

Try it online.

**Explanation:**

```
’
05AB1E
fizz
ÒÖ
'ž™ a æé’         '# Push dictionary string "\n05AB1E\nfizz\nbuzz\n'ave a banana"
         I         # Push the input
          ¶.ø      # Surround it with leading and trailing newline
             ¡     # Split the string on this
              ¦    # Remove the first part (for invalid inputs)
               θ   # Pop and only leave the last part (or an empty list)
                   # (and output it implicitly as result)

"fizz"U            # Puts "fizz" in variable `X`
•äƵí•              # Push compressed integer 14793296
     h             # Convert it to hexadecimal: E1BA50
      R            # Reverse it to 05AB1E
       Qi  }       # If the (implicit) input-string is equal to this:
         X         #  Push "fizz" from variable `X`
          =        #  Print it with trailing newline without popping
X                  # Push "fizz" from variable `X`
 Qi    }           # If the top of the stack equals "fizz",
                   # which will use the (implicit) input if the stack is empty:
   'ÒÖ            '#  Push dictionary string "buzz"
      =            #  Print it with trailing newline without popping
'ÒÖQi           } '# If the top of the stack (or implicit input) equals "buzz":
     ’'ž™ a æé’   '#  Push dictionary string "'ave a banana"
               ,   #  Pop and print it
õ?                 # Print "" without newline
                   # (for invalid input, which otherwise would be output implicitly)

```

See this 05AB1E tip of mine (sections *How to use the dictionary?* and *How to compress large integers?*) to understand why `•äƵí•` is `14793296`; `'ÒÖ` is `"buzz"`; and `’'ž™ a æé’` is `"'ave a banana"`.
> 4 votes

# Answer
# JavaScript (ES6), 64 bytes

Expects `"js"` for the language name. Returns an array of strings.

```
s=>[k="js","fizz","buzz","'ave a banana"].filter(w=>k*(k|=s==w))

```

Try it online!
> 4 votes

# Answer
# Retina 0.8.2, 56 bytes

```
$
¶Retina¶fizz¶buzz¶'ave a banana
^(.*¶)(.*¶)*?(\1|.*$)

```

Try it online! Link includes test cases. Explanation:

```
$
¶Retina¶fizz¶buzz¶'ave a banana

```

Append the possible inputs and outputs.

```
^(.*¶)(.*¶)*?(\1|.*$)

```

Try to delete only up to and including a line matching the original input. If this is not possible, then just delete everything.
> 4 votes

# Answer
# Python 3, ~~77~~ 76 bytes

```
t="Python","fizz","buzz","'ave a banana"
*map(print,t[t.index(input())+1:]),

```

Try it online!

Takes input from `STDIN`, and print the results to `STDOUT`.
> 4 votes

# Answer
# APL (Dyalog Unicode), 43 bytes

```
'APL' 'fizz' 'buzz' '''ave a banana'(↑⍳↓⊣)⊂

```

Try it online!

List of string literals is quite expensive...

### How it works

```
S←'APL' 'fizz' 'buzz' '''ave a banana'  ⍝ Let's call this array S
S(↑⍳↓⊣)⊂  ⍝ The function
S( ⍳  )⊂  ⍝ 1-based index of the input in S, 5 if not found
    ↓⊣    ⍝ Drop that many items from the start of S
  ↑       ⍝ Convert the remaining items to be placed on each line

```
> 4 votes

# Answer
# Java (OpenJDK 8), 117 bytes

```
void a(String s){System.out.println(s=s=="fizz"?"buzz":s=="buzz"?"'ave a banana":s=="java"?"fizz":"");if(s!="")a(s);}

```

Try it online!
> 4 votes

# Answer
# Charcoal, 39 bytes

```
≔⪪“Jε(h&]⦄_⁷¦⊗‹f·ⅈ⦄⊗x⍘ς3➙Ａ⁸“↑”¶υΦυ№…υκθ

```

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

```
≔⪪“Jε(h&]⦄_⁷¦⊗‹f·ⅈ⦄⊗x⍘ς3➙Ａ⁸“↑”¶υ

```

Split the string `Charcoal\nfizz\nbuzz\n'ave a banana` on newlines and save the result in a variable.

```
Φυ№…υκθ

```

Filter on the result and show only those entries that appear after the input.
> 3 votes

# Answer
# C (gcc), <sup>~~115~~ \\$\cdots\\$ ~~105~~</sup> 98 bytes

Saved 4 bytes thanks to ceilingcat!!!

Saved 7 bytes thanks to Neil!!!

```
i;*y[]={"c","fizz","buzz","'ave a banana"};f(char*s){for(i=0;i<3;)strcmp(s,y[i++])||puts(s=y[i]);}

```

Try it online!
> 3 votes

# Answer
# Python 2, ~~102~~ 79 bytes

```
a='fizz'
b='buzz'
def f(s):t={'Python':a,a:b,b:"'ave a banana"}[s];print t;f(t)

```

Try it online!

Uses a different approach from the other answer, recursive function

Edit: Thanks @SurculoseSputum for saving 23 bytes!
> 3 votes

# Answer
# Brachylog, ~~52~~ 47 bytes

```
∧"Brachylog
fizz
buzz
'ave a banana"ṇ;?⟨a₁h⟩b~ṇ

```

Try it online!

The predicate fails on inputs on which it should "terminate". If outputting an unbound variable is more desirable, +2 bytes for `.∨`; if an empty string is necessary, +1 on top of that for .
> 3 votes

# Answer
## Kotlin, 103 bytes

```
fun f(x:String){listOf("fizz","buzz","'ave a banana").fold("Kotlin"){a,b->if(x==a){println(b);f(b)};b}}

```

Try it online!
> 2 votes

---
Tags: code-golf
---


# Question
Title: Write an interpreter for my new esoteric language PointerLang
I designed a language in which pointer arithmetic is the main tool of programming.

Here are some examples.

```
(print 0 to 8)
=9[>1=9-*-1.>-1-1]

(print 1 to 10 with spaces in between, character literal extension used)
=1[.>1=10-*-1[>1=' '!>-2+1;-2];1]='\n'!

(compute the factorial of 10)
=10>1=*-1-1[>-1**1>1-1]>-1.

(print "hi")
=104!=105!

(print "hi" with extension for arrays)
={104,105,0}[!>1]

(print "Hello, world!" with extension for C-style string literals)
="Hello, world!"[!>1]

```

## Language Specification

The language definition is very simple. You will understand very easily if you have experience with C, but I will not assume so.

Every program in PointerLang has *the pointer*, in short, `P`. You can think it as a hidden single global variable, which you can control by using *commands*. `P` initially *points to* the beginning of *the array*. Every element in the array has the type `int` which is a 32-bit signed integer.

For C programmers

```
int32_t *P = malloc(1000);

```

In PointerLang, there are *commands* and *arguments*. An argument is an `int` which must come after a command. All commands are executed from left to right unless specified otherwise. The following is the list of commands. `A` stands for argument. A command without `A` means it does not take an argument. A command with `A` must take an argument. Inside the parentheses is the equivalent C expression.

* `=A` : assign A at P (`*P = A`)
* `+A` : add A at P (`*P += A`)
* `-A` : subtract A at P (`*P -= A`)
* `*A` : multiply by A at P (`*P *= A`)
* `/A` : divide by A at P (`*P /= A`)
* `>A` : move `P` by `A` (`P += A`)
* `.` : print the integer at P (`printf("%d", *P)`)
* `!` : print the integer at P as ASCII (`printf("%c", (char)*P)`)
* `[` : if the value at P is 0 go to the command after the next `]` (`while (*P) {`)
* `]` : go to the previous `[` that is the matching pair (`}`)
* `;A` : if `A` is positive, go to the command after the `A`th `]` coming next; if `A` is negative, go to the `A`th `[` coming before; if A is 0, do nothing.

An integer literal is an argument.

The following two are special arguments that take an argument.

* `-A` : evaluated as an argument having the same absolute value as `A` and the opposite sign of `A`; unary minus
* `*A` : move `P` by `A`, evaluate the value at `P`, move `P` by `-A` (`P[A]`)

All comments in PointerLang are between parentheses `(comment)`.

## Example Program

This program which counts from 1 to 10 is a good example to complete your understanding.

```
(print 1 to 10 with spaces in between)
=1[.>1=10-*-1[>1=32!>-2+1;-2];1]=10!

```

Be careful when you interpret `-*-1`. `-` is the command and `*-1` is the argument. An integer literal effectively indicates the end of a command-argument pair.

It can be translated to C with 1-to-1 correspondence as

```
int main(void) {
    int32_t *P = malloc(1000);
    *P = 1; // =1
l:
    while (*P) { // [
        printf("%d", *P); // .
        P += 1; // > 1
        *P = 10; // =10
        *P -= P[-1]; // -*-1
        while (*P) { // [
            P += 1; // >1
            *P = 32; // =32
            printf("%c", (char)*P); // !
            P += -2; // >-2
            *P += 1; // +1
            goto l; // ;-2
        } // ]
        break; // ;1
    } // ]
    *P = 10; // =10
    printf("%c", (char)*P); // !
    return 0;
}

```

Extensions can be applied to this language such as character literals, arrays, string literals etc, but you don't have to implement them, for simplicity.

## The Challenge

You have to implement the core features detailed in the *Language Specification* section and the NOTEs below. Give it a try with your favourite programming language, writing the shortest program possible.

NOTE1: The size of *the array* is undefined. But it should be big enough to solve most problems.

NOTE2: Integer overflow is undefined.

NOTE3: The specification only defines the result or effect of certain language constructs. For example, you don't have to exactly follow the steps in the definition of the argument `*`.

NOTE4: ~~Any characters that are not commands, arguments, or comments~~ Whitespaces are ignored. `=104!=105!` is as same as `= 1 0 4! = 1 05 !` for example.

NOTE5: Comments are not nested. `((comment))` is a syntax error.

NOTE6: I've made a breaking change to fix a hole in my language. The `~` command is now unused and `;` always takes an argument.

NOTE7: Every integer literal is decimal.

# Answer
# C 406

**Thanks to @ceilingcat for some very nice pieces of golfing - now even shorter**

```
#define L strtol(I++,0,0)
#define A*I==42?I++,P[L]:L
#define F(a)-91-a|i;i-=*I-93+a?*I==91+a:-1);}
i,c;char*I;X[999],*P=X;Y(){for(;*I++F(2)B(){for(i=!--I;*--I F(0)main(j,a)int**a;{for(I=a[1];j=*I++;printf(j-4?j+9?j==19?*P=A:j==1?*P+=A:j==3?*P-=A:!j?*P*=A:j==5?*P/=A:j==20?P+=A:j-17?j-51?j-49?I=j+2?I:index(I,41)+1:*P||Y(i=1):B():({for(c=A;c;c+=c<0?:-1)if(i=c<1)B();else for(;*I++F(2)),"":P:"%d",*P))j-=42;}

```

Try it online!

and the slightly less golfed version of my original answer:

```
#include <stdio.h>
#include <stdlib.h>
#define L strtol(I++,&I,10)
#define A *I=='*'?I++,P[L]:L
int X[999],*P=X;
int main(int i, char *a[])
{
  char* I=a[1];
  while(*I)
  {
    switch(*I++)
    {
      case '(': while(*I++!=')'); break;
      case '.': printf("%d",*P); break;
      case '!': printf("%c",(char*)*P); break;
      case '[': if(!*P)
                  for(i=1;*I++!=']'||i;)
                  {
                    if(*I=='[')
                      i+=1;
                    if(*I==']')
                      i-=1;
                  }
                break;
      case ']': for(--I,i=0;*--I !='['||i;)
                {
                  if(*I==']')
                    i+=1;
                  if(*I=='[')
                    i-=1;
                }
                break;
      case '=': *P=A; break;
      case '+': *P+=A; break;
      case '-': *P-=A; break;
      case '*': *P*=A; break;
      case '/': *P/=A; break;
      case '>': P+=A; break;
      case ';': for(int c=A; c; c+=c<0?1:-1)
                {
                  if(c>0)
                    for(i=0;*I++!=']'||i;)
                    {
                      if(*I=='[')
                        i+=1;
                      if(*I==']')
                        i-=1;
                    }
                  else
                    for(--I,i=0;*--I !='['||i;)
                    {
                      if(*I==']')
                        i+=1;
                      if(*I=='[')
                        i-=1;
                    }
                }
    }
  }
  return 0;
}

```
> 3 votes

# Answer
# JavaScript (ES6) - 560 bytes

Uses `prompt()` for input and `alert()` for output. It could be shortened if `alert()` was called for every character instead but I decided it would be better to buffer the characters so they could all be displayed at once.

```
b=[],d=0,e=[],f=0,g="",h="",k=prompt().replace(/(\s+|\(.*\))/g,""),l=0;n=()=>{m=g;if(m&&(a=m.substr(1),c=m.charAt(),a="*"==a.charAt()?b[d+parseInt(a.substr(1))]:parseInt(a),"["==c&&(b[d]?e.push(f-1):l++),"]"==c&&l&&(0<l&&(f=e.pop()),0>l&&(l=-l),l--),!l&&("="==c&&(b[d]=a),"+-*/".includes(c)&&eval("b[d]"+c+"=a"),">"==c&&(d+=a),"."==c&&(h+=b[d]),"!"==c&&(h+=String.fromCharCode(b[d])),";"==c&&(0<a&&(l=-l-a),0>a))))for(i=0;i<-a;i++)f=e.pop()}
for(f=0;f<k.length;f++)0<f&&"=+-*/>.![];".includes(k[f])&&k[f-1].match(/[0-9.!\[\]]/)&&(n(),g=""),g+=k[f];h&&alert(h);

```
> 1 votes

---
Tags: code-golf, interpreter
---