title: Win 270 electoral college votes

text:
# Question
Title: Win 270 electoral college votes
You are the electoral strategist for a sudden late entrant in the 2020 US presidental election.

**Your task**: print out the names of states\* your candidate will win, totalling at least 270 electoral college votes.

## Background

Each state (and Washington DC) in the US system has an arbitrary number of "electoral college votes". A candidate has to win a majority of the 538 votes available, so at least 270 votes.

The number of votes for each state is:

`[['Alabama', 9], ['Alaska', 3], ['Arizona', 11], ['Arkansas', 6], ['California', 55], ['Colorado', 9], ['Connecticut', 7], ['Delaware', 3], ['Florida', 29], ['Georgia', 16], ['Hawaii', 4], ['Idaho', 4], ['Illinois', 20], ['Indiana', 11], ['Iowa', 6], ['Kansas', 6], ['Kentucky', 8], ['Louisiana', 8], ['Maine', 4], ['Maryland', 10], ['Massachusetts', 11], ['Michigan', 16], ['Minnesota', 10], ['Mississippi', 6], ['Missouri', 10], ['Montana', 3], ['Nebraska', 5], ['Nevada', 6], ['New Hampshire', 4], ['New Jersey', 14], ['New Mexico', 5], ['New York', 29], ['North Carolina', 15], ['North Dakota', 3], ['Ohio', 18], ['Oklahoma', 7], ['Oregon', 7], ['Pennsylvania', 20], ['Rhode Island', 4], ['South Carolina', 9], ['South Dakota', 3], ['Tennessee', 11], ['Texas', 38], ['Utah', 6], ['Vermont', 3], ['Virginia', 13], ['Washington', 12], ['Washington DC', 3], ['West Virginia', 5], ['Wisconsin', 10], ['Wyoming', 3]]`

## Input

None

## Output

A list (or similar) containing just the names of the states in your winning strategy. If a string, there must be separators between state names. States must be capitalised as in the list provided above.

You must not output anything other than valid state names and separators. The number of states in your strategy is up to you.

## Rules

You may not use any external (or built-in) list of US state names. Standard loopholes are forbidden.

This is code golf. Shortest code in bytes wins, with the electoral college score as a tie-breaker.

Since there is no input, your code can be a program/script/statement rather than a function.

If you are using space as a separator, then you can't include any states with spaces in the name. Or you would have to do something like enclosing each state name in double quotes. (A separator has to be something that could be used to automatically split the string up into the correct elements.)

`*` For the purpose of this challenge, Washington DC is considered a state.

# Answer
> 7 votes
# Charcoal,  ~~52 ... 45~~  42 bytes (270 votes)

A list of states that optimizes the compression with Brotli.

```
”}∧J⟧´⪫3⎚>↘≡ＶＮb7>¹l↙⁵Þ7/…ξ⌕↑τc<y\MΦＧＣ＆⸿Dρ~

```

Try it online!

### Output

```
Texas
Pennsylvania
Georgia
Illinois
Washington
Indiana
California
Arizona
Michigan
Virginia
Florida
New York

```

### Node.js script

The initial list was found with the following Node.js script that shuffles the 30 most efficient states, extracts the shortest leading sub-list with a score greater than or equal to 270, joins it with `\r` and invokes the Brotli compressor on the resulting string.

It was optimized some more by shuffling the most promising sub-list to find an order offering the best compression.

```
let states = [ ['Alabama', 9], ['Alaska', 3], ['Arizona', 11], ... ];

states =
  states.map(a => [a[0], a[1], a[1] / a[0].length])
  .sort((a, b) => b[2] - a[2])
  .slice(0, 30);

const zlib = require('zlib');

let bestLen = 1 / 0, bestScore = 1 / 0,
    list, score, str, pack;

while(1) {
  for(let i = states.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1));
    [ states[i], states[j] ] = [ states[j], states[i] ];
  }

  for(
    let n = 1;
    (score = (list = states.slice(0, n)).reduce((p, c) => p + c[1], 0)) < 270;
    n++
  ) {}

  str = list.map(s => s[0]).join('\r');
  pack = zlib.brotliCompressSync(Buffer(str));

  if(pack.length < bestLen || (pack.length == bestLen && score <= bestScore)) {
    bestLen = pack.length;
    bestScore = score;
    console.log(bestLen, bestScore, str.split('\r').join('\\r'));
  }
}

```

# Answer
> 6 votes
# 05AB1E, ~~68~~ 66 bytes, 271 votes

```
.•2Y±e1¸Zí¼³sçj†Êè”šʒÕʒ½‘ε-нUeC·ûÝì£…
õ%î!¯aàáè˜3ÒƵLweh³•#`„€¢…Œ»™

```

Outputs the following 12 states newline-separated, totaling 271 votes:

```
California,Florida,Georgia,Illinois,Indiana,Michigan,Ohio,Pennsylvania,Texas,Utah,Virginia,New York

```

Try it online.

If builtins were allowed, we could have used the dictionary for **27 bytes, 270 votes**

```
”‡Â†éŠ§›ÕïÁ–Û—Ñ—ïŽŽ‡¹¢ÇŸÏžÏ

```

Outputs the following 13 states space-delimited, totaling exactly 270 votes:

```
California Texas Florida Pennsylvania Illinois Ohio Michigan Georgia Virginia Washington Tennessee Massachusetts Indiana

```

Try it online.

**Explanation:**

```
.•2Y±e1¸Zí¼³sçj†Êè”šʒÕʒ½‘ε-нUeC·ûÝì£…
õ%î!¯aàáè˜3ÒƵLweh³• # Push compressed string "california florida georgia illinois indiana michigan ohio pennsylvania texas utah virginia"
  #                 # Split it on spaces
   `                # Push them all separated to the stack
    „€¢…Œ           # Push dictionary string "new york" (which are both English words)
         »          # Join all strings on the stack by newlines
          ™         # And title-case each word
                    # (after which it is output implicitly as result)

”‡Â†éŠ§›ÕïÁ–Û—Ñ—ïŽŽ‡¹¢ÇŸÏžÏ
                    # Push the dictionary string "California Texas Florida Pennsylvania Illinois Ohio Michigan Georgia Virginia Washington Tennessee Massachusetts Indiana"
                    # (after which it is output implicitly as result)

```

See this 05AB1E tips of mine (sections *How to use the dictionary?* and *How to compress strings not part of the dictionary?*) to understand why:

* `.•2Y±e1¸Zí¼³sçj†Êè”šʒÕʒ½‘ε-нUeC·ûÝì£…\nõ%î!¯aàáè˜3ÒƵLweh³•` is `"california florida georgia illinois indiana michigan ohio pennsylvania texas utah virginia"`;
* `„€¢…Œ` is `"new york"`;
* and `”‡Â†éŠ§›ÕïÁ–Û—Ñ—ïŽŽ‡¹¢ÇŸÏžÏ` is `"California Texas Florida Pennsylvania Illinois Ohio Michigan Georgia Virginia Washington Tennessee Massachusetts Indiana"`.

# Answer
> 6 votes
# Charcoal, ~~59~~ ~~51~~ ~~50~~ 41 bytes

```
”}∧I⊗⪫σ³»α“"⸿u↙¦Ｃ^±Ｗ)ＲLκ&⁰Ｙ2Ｅ¬«]f“ＷN+'|⁺≕

```

Try it online! Link is to verbose version of code. Simply the compressed string for `Texas\nVirginia\nIllinois\nMichigan\nGeorgia\nPennsylvania\nFlorida\nWashington\nNew York\nCalifornia\nMassachusetts\nTennessee`; total 270 votes.

This solution was found with the help of a Python 3 program that randomly selected voting states and took the length of the resulting string. It then tracked the number of times each state appeared in the strings that were less than a certain cutoff length, initially 60, but gradually reduced to 45 as I optimised the input.

Optimisation consisted both of creating a list of frequently used states and removing infrequently used states from the list thus allowing more shuffles to be performed.

Eventually I got to the point where each shuffle always had the states California, Florida, Georgia, Illinois, Michigan, New York, Pennsylvania and Texas, and four of the six states Arizona, Indiana, Massachusetts, Tennessee, Virginia and Washington. At this point I could generate all 15 combinations of 12 states and just had to shuffle the states around in the hope of getting a short answer. Shuffling script:

```
import brotli
import itertools
import random
import sys

bigstates = ['California', 'Florida', 'Georgia', 'Illinois', 'Michigan', 'New York', 'Pennsylvania', 'Texas']
smallstates = ['Arizona', 'Indiana', 'Massachusetts', 'Tennessee', 'Virginia', 'Washington']

while True:
 for states in itertools.combinations(smallstates, 4):
  states = bigstates + list(states)
  for j in range(100):
   random.shuffle(states)
   if len(brotli.compress('\n'.join(states).encode("ascii"))) < 39:
    print(states)
    sys.exit()

```

Try it online! The script also found the following shuffles with the same byte count:

```
Print("Texas\nTennessee\nVirginia\nPennsylvania\nWashington\nCalifornia\nMichigan\nMassachusetts\nNew York\nGeorgia\nFlorida\nIllinois");
Print("Texas\nVirginia\nMichigan\nIllinois\nGeorgia\nPennsylvania\nFlorida\nWashington\nTennessee\nMassachusetts\nNew York\nCalifornia");
Print("Texas\nGeorgia\nTennessee\nVirginia\nIllinois\nPennsylvania\nMichigan\nWashington\nCalifornia\nNew York\nMassachusetts\nFlorida");
Print("Texas\nNew York\nVirginia\nPennsylvania\nWashington\nFlorida\nMassachusetts\nGeorgia\nCalifornia\nTennessee\nMichigan\nIllinois");

```

Previous 50-byte solution:

```
”}∧UV↔ΦＪU№ＥIＧ➙eêPn¡Ｆ{⦃←στ⸿Ｍ⊕!⪫¹Ｐ？Ｍξ⁹#<″⊘bh%0ＲＺ⌈⧴↑·

```

Try it online! Link is to verbose version of code. Simply the compressed string for `Pennsylvania\nWisconsin\nTexas\nCalifornia\nIllinois\nNew York\nFlorida\nGeorgia\nMichigan\nVirginia\nArizona\nNew Jersey`; total 271 votes.

I started off with the best value states, Texas, California, Florida, Ohio, New York, Illinois, Georgia, Michigan, Pennsylvania, Virginia and Arizona, plus Iowa to make up the numbers. I then tried various permutations of states to find out which ones Charcoal compressed best; moving Ohio, Illinois and New York to the end worked best. (There are 12! possibilities so I'm not trying them all.) I then tried switching Arizona and Iowa with Indiana and Utah, taken from @SurculoseSputum's answer; Arizona made no difference but Utah saved a further byte.

Edit: Saved 8 bytes by printing Utah and Ohio literally instead of trying to compress them. Saved a further byte by using New Jersey and Wisconsin instead of Utah and Ohio. (This did mean reordering the states again for optimal compression. Colorado, Indiana, Maryland, Massachusetts, Minnesota, Mississippi and Missouri and also work instead of Wisconsin.)

# Answer
> 5 votes
# Python 2, 106 bytes, 271 votes

```
print"California,Florida,Georgia,Illinois,Indiana,Michigan,New York,Ohio,Pennsylvania,Texas,Utah,Virginia"

```

Try it online!

Picks the states with the best votes/name length ratio.

Turns out this is the shortest possible combination of states to achieve at least `270`, as shown in this DP program.

# Answer
> 3 votes
# Turing Machine Code, 1059 bytes (270 votes)

```
0 * C r 1
1 * a r 2
2 * l r 3
3 * i r 4
4 * f r 5
5 * o r 6
6 * r r 7
7 * n r 8
8 * i r 9
9 * a r π
π * , r a
a * T r b
b * e r c
c * x r d
d * a r e
e * s r f
f * , r g
g * F r h
h * l r i
i * o r j
j * r r k
k * i r l
l * d r m
m * a r n
n * , r o
o * N r p
p * e r q
q * w r r
r * _ r s
s * Y r t
t * o r u
u * r r v
v * k r w
w * , r x
x * I r y
y * l r z
z * l r A
A * i r B
B * n r C
C * o r D
D * i r E
E * s r F
F * , r G
G * P r H
H * e r I
I * n r J
J * n r K
K * s r L
L * y r M
M * l r N
N * v r O
O * a r P
P * n r Q
Q * i r R
R * a r S
S * , r T
T * O r U
U * h r V
V * i r W
W * o r X
X * , r Y
Y * G r Z
Z * e r `
` * o r ¬
¬ * r r "
" * g r £
£ * i r $
$ * a r %
% * , r ^
^ * M r &
& * i r (
( * c r )
) * h r +
+ * i r {
{ * g r }
} * a r [
[ * n r ]
] * , r -
- * N r =
= * o r :
: * r r '
' * t r @
@ * h r #
# * _ r ~
~ * C r
> * o r .
. * l r ?
? * i r /
/ * n r |
| * a r \
\ * , r ©
© * N r À
À * e r Á
Á * w r Â
Â * _ r Ã
Ã * J r Ä
Ä * e r Å
Å * r r Æ
Æ * s r Ç
Ç * e r È
È * y r halt

```

This will print:

```
California (55; 55)
Texas (38; 93)
Florida (29; 122)
New York (29; 151)
Illinois (20; 171)
Pennsylvania (20; 191)
Ohio (18; 209)
Georgia (16; 225)
Michigan (16; 241)
North Carolina (15; 256)
New Jersey (14; 270)

```

Or to be more precise: `California,Texas,Florida,New York,Illinois,Pennsylvania,Ohio,Georgia,Michigan,North Carolina,New Jersey`

*Updated to reflect a later rule change - thanks @Laikoni. No byte size change.*

Try it online!

# Answer
> 2 votes
# Stax, 75 bytes, 271 votes

```
ê╢G.₧¢ƒdXb╜L7äF9₧⌐Ä╚ç⌂oPrçer┬♦s4⌠╧!S∟☻ƒÆà²ÿ☼{4?àç÷Uó("Φå9dgYútY°lènÜÉ↔TI╙í↨

```

Run and debug it

# Answer
> 2 votes
# Jelly, 37 bytes

```
“£+ʠṅṖḳ!⁺PUB.BJçŒṖ{ScḤ?[¢¤c}€£Y,qbẆ|»

```

A niladic Link which yields a list of characters using a space as the separator. The states have a total value of 270 (and contain no spaces themselves):

```
California    55
Texas         38
Florida       29
Pennsylvania  20
Illinois      20
Ohio          18
Georgia       16
Virginia      13
Massachusetts 11
Indiana       11
Arizona       11
Maryland      10
Colorado       9
Alabama        9
           = 270

```

**Try it online!**

### How?

A compressed string. After taking big hitters containing no spaces I chose states which are earlier alphabetically to keep the result shorter.

# Answer
> 2 votes
# Ruby, 115 bytes

```
puts"California
Texas
Florida
Nor#{s="th Carolina
New "}York
Sou#{s}Jersey
Illinois
Ohio
Georgia
Michigan
Virginia"

```

Try it online!

Makes use of the string `"th Carolina\nNew "`

# Answer
> 2 votes
# Bash, ~~102~~ 108 bytes (270 electoral votes)

```
echo \"{{Californ,Georg,Virgin}ia,Florida,Arizona,Indiana,Texas,Ohio,New\ {York,Jersey},Illinois,Michigan}\"

```

Try it online!

*Added 6 bytes to accommodate the modification to the challenge on using a space as a separator. The original answer was:*

```
echo {Californ,Georg,Virgin}ia Florida Arizona Indiana Texas Ohio New\ {York,Jersey} Illinois Michigan

```

# Answer
> 2 votes
# Whitespace, 777 bytes; 274 EV's

```

```

Outputs the states as a `j`-separated list. You read that part right.
Try it online!

## States

`"Arizona", "California", "Florida", "Georgia", "Illinois", "Indiana", "Iowa", "Michigan", "Ohio", "Pennsylvania", "Tennessee", "Texas", "Utah", "Virginia"`
List chosen using @Surculose Sputum's Python script, but modified to ignore states with spaces in their names. This was because spaces have an ascii value of `32`, and `32 - 105= -73`, so pushing it would raise the byte count by a lot (I think). I have yet to test this theory though (because when removing NY I had to add something like 4 more states), so the code may yet get smaller.

## Code

A pretty standard Whitespace answer. Pushes the names of the states minus 105 to the stack, separated by a `j`, and then runs through the stack adding back the `105` and printing the result as a character. The printing part looks something like:

```
label 0:
  push 105
  add
  printc
  jmp 0

```

`105` because the character with the most occurences is `i`, which has an ascii value of 105. Outputting as a `j` separated list because `j` has a value of `106`. I used this script to generate the WSA (WhiteSpace Assembly) to quickly test the offset number, and used this IDE to compile it to regular Whitespace.

# Answer
> 1 votes
## JavaScript, 114 characters, 270 votes

```
_=>`California,Texas,Florida,Nor${s='th Carolina,New '}York,Sou${s}Jersey,Illinois,Ohio,Georgia,Michigan,Virginia`

```

Just a straight port of Level River St's Ruby answer.

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


title: Play a Game of Minigolf

text:
# Question
Title: Play a Game of Minigolf
## Background

I feel that for a site named code-golf we have a shockingly little amount of golf being played. Let's fix that.

## Challenge

Determine whether the hole of a minigolf course can be reached after exactly a certain number of movements and whether it can be reached at all.

## How to play

Inputs are an integer "power level" and an ASCII art minigolf course. The ball starts on the `X` (capital) and the hole is an `O` (capital). The walls of the course are made of the characters `+` `|` `-` `\` and `/`. The characters `+` `|` and `-` rotate the direction of the ball 180 degrees and the characters `\` and `/` rotate the direction 90 degrees as you would expect. When a ball hits the wall it enters the wall for that turn and then leaves the next turn.

Launch the ball in each of the four cardinal directions from the starting `X`.

* If the ball enters the hole after **exactly** the power level moves, then output `truthy`.
* If the ball could make it to the hole given a different power level, then output `mediumy`.
* If the ball cannot enter the hole regardless of the power level, output `falsy`.

## Rules

* This is so shortest answer in bytes wins.
* Assume only valid input will be given.
* All input strings will be rectangular. (All rows will be the same length)
* Assume that there is no way to escape the course and leave the edge of the string.
* No solution will require the ball to be in the same place facing the same direction twice.
* Standard loopholes disallowed.
* Only a string or a list of strings is acceptable for the course input.
* Output can be any three distinct values.
* The ball will never hit the characters `|` or `-` "end-on."

## Example

```
11
   -----+
  /   X |
 | +----+
 | |
 |O|
 +-+

```

This is true. If the ball starts heading east it will be on the wall after two movements.

```
   -----+
  /   X o<- ball right here. movements:2
 | +----+
 | |
 |O|
 +-+

```

It will then change directions until it hits the corner

```
   -----+
  o   X | movements:8
 | +----+
 | |
 |O|
 +-+

```

Now it is heading south and will end in the hole after 11 moves. Note that 13 would also be true as the ball could bounce off of the bottom wall and into the hole. Other valid power levels for this course are 7 and 9.

## Test Cases

All answers validated using this java code: https://github.com/Dragon-Hatcher/CodeGolfMiniGolf/tree/master/MinigolfCodeGolf/src

```
power
course
output

11
   -----+
  /   X |
 | +----+
 | |
 |O|
 +-+

truthy

10
    +---+
    | X |
    +---+
 +-+
 |O|
 +-+

falsy

25

      ---------
     /     X   \
    +++-------+ |
    | |       | |
    |O|       | |
    | \-------/ |
     \         /
      ---------

truthy

2

 +-+
 |X|
 | |
 | |
 |O|
 +-+

mediumy

34

      +------+
      |/    \|
      | +--+ |
      |X|  | |
  +---+ +--+ |
  |    O    /|
  +---+ +----+
      +-+

true

```

# Answer
# APL (Dyalog Unicode), ~~146~~ 115 bytes

```
{(∨/+⍺⊃⊢)∨⌿↑{'O'=1↓⊃¨⊢∘(((⊢,⍉∘⊖∘⌽¨)1⌽¨⊂,⊂∘⍉)⊃⍨1⌈¯2+'X O\/'⍳⊃)\(4×≢,⍵)⍴⊂⍵}¨({¯1+⊃⊃⍸'X'=⍵}⌽⍉)⍣2¨(⊢,⌽∘⊖¨)(⊂,⊂∘⍉)⍵,⍳≢⍵}

```

*-31 bytes (!) thanks to @Bubbler (combining transformations; simplifying iteration end condition; smaller details)*

Try it online!

Outputs `2` for truthy, `1` for mediumy, and `0` for falsy.

Similarly to my solution to Solve the Halting Problem for Modilar SNISP, this moves the grid around the ball location, so the ball is always in the top-left, moving right. This might not be the best strategy (as opposed to storing a pointer position and direction) in this case because the ball doesn't always start from the top-left moving right, so I spend many bytes rotating and aligning the grid.

## Details

Append 1,2,3,4,...,n to the input grid. This prevents symmetric grids from comparing equal after some sequence of moves

```
⍵,⍳≢⍵

```

We must be careful here and elsewhere in the code that we do not affect the angle of `/` and `\`. Using a simple reflection  to reverse direction should change `/` to `\`, but the reflection of the character `'/'` is `'/'`.

Conveniently, APL matrix reflection operators are visually sensible:

* reflects across a vertical line: swaps `/` and `\`
* reflects across a horizontal line: swaps `/` and `\`
* (transpose) reflects across the main diagonal: no change

Thus we must use an even total number of  and  in all transforms.

Obtain all 4 starting directions/rotations:

```
(⊢,⌽∘⊖¨)(⊂,⊂∘⍉)

```

Shift each grid so that 'X' is in the top left (Shifts 'X' to the left edge twice, transposing the matrix in between)

```
{(¯1+⊃⊃⍸'X'=⍵)⌽⍉⍵}⍣2¨

```

For each starting grid, beginning with the starting grid, repeat 4×#coordinates (= max # of states) times...

```
\(4×≢,⍵)⍴⊂⍵

```

...move by one step:

```
(((⊢,⍉∘⊖∘⌽¨)1⌽¨⊂,⊂∘⍉)⊃⍨1⌈¯2+'X O\/'⍳⊃)
  ⍝ Get the ID of the entry: `X`, ` `, or `O`:1, `\`:2, `/`:3, `|`,`+`, or `-`:4
  ⍝ We can consider |, +, and - as the same because we are always travelling
  ⍝ horizontally (albeit on a rotated grid), and these all do the same action
  1⌈¯2+'X O\/'⍳⊃
  ⍝ Get the corresponding grid position after the move
  ((⊢,⍉∘⊖∘⌽¨)1⌽¨⊂,⊂∘⍉)⊃⍨

```

`1` if there exists a move history whose final move's top-left element is `O`, and add another `1` if there exists a move history where the -th move has top-left element equal to `O`.

```
(∨/+⍺⊃⊢)∨⌿↑{'O'=1↓⊃¨

```
> 5 votes

# Answer
# JavaScript (Node.js),  ~~170 ... 147~~  145 bytes

Expects `(n)(a)`, where `n` is an integer and `a` is an array of strings. Returns `3` for *truthy*, `0` for *falsy* or `1` for *mediumy*.

```
n=>a=>(g=(d,y=a.findIndex(r=>~(x=r.search`X`),j=n))=>+(a+a+1)[~j]?D&&g(--D):!(k=Buffer(a[y+=(d-2)%2])[x+=~-d%2]*5%26%5)*-~!--j|g(d^4-k&3,y))(D=3)

```

Try it online!

### How?

We use the following compass for the directions:

```
  1
0 + 2
  3

```

Which means that we have \\$dx=(d-1)\bmod 2\\$ and \\$dy=(d-2)\bmod 2\\$, assuming that the sign of the modulo is the sign of the dividend.

With this setup, we want to update \\$d\\$ to:

* \\$(d\operatorname{XOR}2)\\$ for a 180° turn (bouncing on either `-`, `+` or `|`)
* \\$(d\operatorname{XOR}1)\\$ for a 90° turn when bouncing on a `\`
* \\$(d\operatorname{XOR}3)\\$ for a 90° turn when bouncing on a `/`

We use the following formula to convert any board character of ASCII code \\$n\\$ to \\$k\in\[0..4\]\\$:

$$k=((n\times5)\bmod 26)\bmod 5$$

The great thing about this formula is that the value that \\$d\\$ must be XOR'ed with when going through a character is immediately given by \\$4-k\\$ (except `O` which is turned into \\$4\\$).

```
 char. | code | *5  | %26 | %5 | 4-k
-------+------+-----+-----+----+-----
  ' '  |   32 | 160 |   4 |  4 |  0
  'X'  |   88 | 440 |  24 |  4 |  0
  'O'  |   79 | 395 |   5 |  0 |  4
  '/'  |   47 | 235 |   1 |  1 |  3
  '\'  |   92 | 460 |  18 |  3 |  1
  '|'  |  124 | 620 |  22 |  2 |  2
  '-'  |   45 | 225 |  17 |  2 |  2
  '+'  |   43 | 215 |   7 |  2 |  2

```

### Commented

```
n => a => (                   // n = number of moves; a[] = array of strings
  g = (                       // g is a recursive function using:
    d,                        //   d = current direction
    y = a.findIndex(r =>      //   y = index of the row r[] in a[]
      ~(x = r.search`X`),     //       which contains an 'X' at position x
      j = n                   //   j = move counter, initialized to n
    )                         //
  ) =>                        //
    +(a + a + 1)[~j] ?        //   if j is negative and we have visited at
                              //   least more than twice the total number of
                              //   cells in a[]:
      D &&                    //     if D is not equal to 0:
        g(--D)                //       do a recursive call with D - 1
    :                         //   else:
      !(k =                   //     compute k:
        Buffer(               //       get the ASCII code at (x + dx, y + dy)
          a[y += (d - 2) % 2] //       add dy to y
        )[x += ~-d % 2]       //       add dx to x
        * 5 % 26 % 5          //       apply the formula described above
      ) *                     //     k = 0 means that we've reached the hole,
      -~!--j                  //     in which case we yield 1 if j != 0
      |                       //     or 2 if j = 0 (j is first decremented)
      g(d ^ 4 - k & 3, y)     //     update d and do a recursive call
)(D = 3)                      // initial call to g with d = D = 3

```
> 4 votes

# Answer
# Python 3, ~~384~~ 378 bytes

```
def l(d,r,m,i,c,p):
 m+=[[d]+p];p[1]+=(d-1)*(~d%2);p[0]-=(d-2)*(d&1);s=r"/\-|+OX ".index(c[p[1]][p[0]])
 if s<2:d+=(s^d&1)*2+1;d%=4
 if 1<s<5:d+=2;d%=4
 if s==5:r+=[i]
 if [d]+p in m:return r
 return l(d,r,m,i+1,c,p)
def f(c,v):
 i=c.index("X");i2=c.index("\n");p=[i%(i2+1),i//i2];c=c.split("\n");r=[];
 for d in range(4):r+=l(d,[],[],1,c,p)
 print([[1,0],[2,2]][v in r][r==[]])

```

Try it online!

*Edit*: Saved 6 Bytes thanks to Ad Hoc Garf Hunter's suggestion.

Takes input c = string, v = power level Outputs 0 for falsy, 1 for mediumly and 2 for truthy

This is my first codegolf submission, so there's most likely a better way but I tried best:

**Explanation:**

Note: Directions are encoded as an integer, where 0 = North, 1 = East, 2 = South, 3 = West

```
def l(d,r,m,i,c,p):                       # d:=direction, r:=result, m:=moves
                                          # i:=steps, c:=course, p:=position
    m += [[d]+p]                          # add direction and position as a move
    p[1] += (d-1)*(~d%2)                  # if direction is even move up or down
    p[0] -= (d-2)*(d&1)                   # if direction is odd move to the left or to the right
    s = r"/\-|+OX ".index(c[p[1]][p[0]])  # get next token as an int
    if s<2:                               # case "/" or "\"
        d += (s^d&1)*2+1                  # rotate either 270 or 90 degrees, depending on
                                          # whether the direction is odd or even
                                          # flip the condition depending if "/" or "\"
        d%=4                              # correct direction in case of overflow
    if 1 < s < 5:                         # edge hit
        d += 2                            # rotate 180 degrees
        d %= 4                            # if direction overflows
    if s == 4:                            # case "O"
        r+=[i]                            # add number of steps to result list
    if [d]+p in m:                        # if move was already made
        return r                          # return result
    return l(d,r,m,i+1,c,p)               # call next step

def f(c,v):                                             # c is the string, v the power level
    i = c.index("X")                                    # getting the index of the "X"
    i2 = c.index("\n")                                  # getting the width of the course
    p = [i % (i2+1), i // i2]  # transforming it to a [x,y] position
    c = c.split("\n")                                   # splitting the string into a list
                                                        # so it can be accessed via [y][x]
    r = []
    for d in range(4):                                  # the 4 starting directions
        r += l(d,[],[],1,c,p)                           # starting the loop with the init values
    print(2 if v in r else 0 if r == [] else 1)         # if the power level is in the list
                                                        # output 2
                                                        # if the list is empty (hole could not be reached)
                                                        # output 0
                                                        # else output 1

```
> 2 votes

# Answer
# Scala, 298 bytes

```
l=>s=>{def h(d:Int,c:(Int,Int),p:Int,r:Set[Any]):Int={val x=(c._1+(d-2)%2,c._2+(d-1)%2)
val a=s(x._2)(x._1)
if(a==79)if(p==1)1 else math.max(0,h(d,x,p-1,r+(c->d)))else if(!r(x->d))h(d^(4-5*a%26%5),x,p-1,r+(c->d))else-1}
0 to 3 map(h(_,s.map(_ indexOf'X').zipWithIndex.find(_._1>=0)get,l,Set()))max}

```

Try it online!

I used the brilliant formula Arnauld used in their answer, but it's still a pretty large amount of code.

Outputs -1 for false, 0 for mediumy, and 1 for truthy.

Prettier version:

```
//l is the power level, s is the golf course, split on \n
l => s => {
  //h is a recursive helper function
  //dir is the direction, c is the (x,y) coordinates of the ball,
  //p is the power level, and seen is a set holding a tuple of all the coordinates and directions
  //(In reality, seen is a Set[((Int,Int),Int)], but I was lazy)
  def h(dir: Int, c: (Int, Int), p: Int, seen: Set[Any]): Int = {
    //The new position
    val x = (c._1 + (dir - 2) % 2, c._2 + (dir - 1) % 2)
    //The character at the new position
    val a = s(x._2)(x._1)
    if (a == 79) {  //Found the hole!
      if (p == 1) 1 //Power level is right
      else math.max(0, h(dir, x, p - 1, seen + (c->d))) //Power level is right
    } else if (seen(x, d)) -1 //We're just looping around, it's never going to work
    else h(dir ^ (4 - 5 * a % 26 % 5), x, p - 1, seen + (c -> d)) //Go on to the next move
  }
  //Try out every direction
  (0 to 3).map(h(d =>
    d,
    s.map(_.indexOf('X')).zipWithIndex.find(_._1 >= 0).get, //The start coordinate
    l,
    Set()
  )).max
}

```
> 2 votes

# Answer
# Charcoal, 94 bytes

```
ＷＳ⊞υι≔⪫υ¶ηＰη…η⌕ηX≔⟦⟧υＦ⁴«≔⟦⟧ζＷ¬№ζ⟦ⅈⅉι⟧«⊞ζ⟦ⅈⅉι⟧Ｍ✳⊗ι≡ＫＫO⊞υＬζ\≦⁻³ι/≔﹪⁻⁵ι⁴ι¿№+|-ＫＫ≔﹪⁺²ι⁴ι»»⎚ＦυＰ=№υＮ

```

Try it online! Link is to verbose version of code. Takes input as the course and power level separated by a blank line, and outputs `-` for correct power level, `=` for incorrect power level, and nothing for an impossible course. Explanation:

```
ＷＳ⊞υι

```

Input the course until the blank line is reached.

```
≔⪫υ¶ηＰη

```

Join the lines back together and print the course without moving the cursor.

```
…η⌕ηX

```

Print the course up to the `X`, which leaves the cursor at the start.

```
≔⟦⟧υ

```

Start keeping track of the working power levels.

```
Ｆ⁴«

```

Loop over all orthogonal directions.

```
≔⟦⟧ζ

```

Start keeping track of visited positions. (Because I really need a repeat...until loop here, this is slightly golfier than just comparing the current position with the initial position. I also need the number of steps anyway.)

```
Ｗ¬№ζ⟦ⅈⅉι⟧«

```

Repeat until we're at a previous position and direction. (This can only happen when we get back to our starting point and direction, since the other saved positions can only be reached from there.)

```
⊞ζ⟦ⅈⅉι⟧

```

Save the current position and direction.

```
Ｍ✳⊗ι

```

Move in the current direction. (In Charcoal, direction 0 is to the right, increasing by 45 degrees anticlockwise each time, so that e.g. 6 is down. Since we're not interested in diagonals, I work in multiples of right angles and double them for the `Move` command.)

```
≡ＫＫ

```

Switch on the character under the cursor.

```
O⊞υＬζ

```

If it's an `O` then save the power level (i.e. number of steps) needed to get here.

```
\≦⁻³ι

```

If it's a `\` then XOR the direction with 3, which here is simply equivalent to subtracting it from 3, as Charcoal has no XOR operator.

```
/≔﹪⁻⁵ι⁴ι

```

If it's a `/` then XOR the direction with 1, which is equivalent to subtracting from 5 modulo 4.

```
¿№+|-ＫＫ≔﹪⁺²ι⁴ι

```

Otherwise if it's any other wall then XOR the direction with 2, which is equivalent to adding 2 modulo 4.

```
»»⎚

```

Clear the canvas once all directions have been considered.

```
ＦυＰ=

```

If it was possible to get the ball in the hole then output a `=`.

```
№υＮ

```

But if the input power level was correct then change that to a `-`.
> 2 votes

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

```
(g,P,w=g.indexOf('\n')+1,f=(d,i=g.indexOf('X'),p=P,a=[],c=g.replace(/-|\|/g,'+')[i],s=Math.sign(d),q=w+1-d/s)=>a.includes(k=''+[i,d])?0:!p&&c=='O'?3:c=='O'|f((d=c=='/'?-s*q:c=='\\'?s*q:c=='+'?-d:d),i+d,p-1,[...a,k]))=>f(1)|f(-1)|f(w)|f(-w);

```

Returns `3` for truthy, `1` for mediumy, and `0` for falsey.

Try it online!

Nice question!

I'm not super happy with my result, but I did learn a cool trick in the meantime: you can save some bytes by replacing

```
(a1,a2)=>{x=f(a1,a2);return g(x)}

```

with

```
(a1,a2,x=f(a1,a2))=>g(x)

```
> 2 votes

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


title: The Third String

text:
# Question
Title: The Third String
Given two strings, output a third string that is not equal to either of the two inputs, but has the same length (in characters) as either of the inputs. There is guaranteed to be at least one valid output.

# Test Cases

Test cases are quoted to show they are strings. Outputs are one of many possible.

```
input, input -> output

"test", "test" -> "tttt"
"do", "don't" -> "dnut_"
"ye s", "yes" -> "fals"
"yes", "yes" -> "noo"
"maybe", "mayue" -> "false"
"false", "false" -> "truee"
"false", "true" -> "fatr"
"1", "" -> "0"
"", "t" -> "s"
"", "abcabc" -> "testst"
"abcdefghijklmnopqrstuvwxyz", "aaaaaaaaaaaaaaaaaaaaaaaaaa" -> "zbcdefghijklmnopqrstuvwxya"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" -> "cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc"

```

## Rules

* You may chose your input domain, but it must be composed of at least printable ASCII, and your output domain must be the same as your input domain.
* The input lengths may be the same or different.
* The output must be valid with probability 1; that is, you may generate random strings until one is valid (and theoretically you might infinite loop), but you can't just output a random string and hope it's valid. Note that this means you output does not need to be deterministic.
* Automatic trailing newlines allowed, but they do not count towards the length of the output.
* Due to questions regarding Memory Errors, it must work within 60 seconds up to input lengths of `6`. An answer that works for that and theoretically works for longer strings is OK, but something that Memory Errors on modern computer for input length `4` is not valid.

This is , so shortest answer in bytes wins.

# Answer
# Haskell, 43 bytes

```
x!y=[s|s<-(<$max x y)<$>"abc",s/=x,s/=y]!!0

```

Takes the max (lexicographically later) string, which we know is nonempty; replaces all characters with one of "a", "b", and "c" using `<$`; and returns the first that is neither of the inputs. I think this is similar to Neil's Charcoal answer and/or geokavel's CJam answer.

(I've lurked for a while but this is my first time answering on this site; hi!)
> 13 votes

# Answer
# Brainfuck, 97 bytes

```
+>+[-,[>>,]<<[<<]>]>>[>]<<<[<]>[<+>>[-<+<+>>][>]<[->+<]<[-]>>>++<[<]>[.>>]>[>>]]>[+[>]+[<]>[.>>]]

```

Run code online (note that "dynamic memory" must be selected in the bottom-right)

Awesome challenge! I thought it would be trivial but it ended up being really difficult. I keep coming back to it because I feel like there *should* be some elegant 20-or-so-byte BF solution. At this point, I'm pretty happy I (seemingly) got it to work at all in BF.

Input is taken as `str1` \+ `\0` \+ `str2`, where strings are consecutive non-zero 1-byte characters.

Returns `(first str1 + first str2) or (first str1 + 1) or 2`. This algorithm was thought up by the brilliant @ØrjanJohansen, (presumably) based on my (broken) original one.

Commented:

```
# Let (Kn) be the nth character of K
# Let (^) designate the pointer
# Let F be the first string inputted
# Let S be the second string inputted

+>+[-  # Twice do
,[>>,]  # Input string (characters separated by 1)
<<[<<]>  # Go to left of beginning of string
]>  # End on first character of second string
# If second string is null we will end one too far to the left
>[>]<<<[<]>  # If first string is null we will end there too
# We will use this to do flow control

[  # Only run if both strings were non null

# Tape:    S0 ' F0 ' S1 ' F1 ' S2 ' F2 ' etc
#          ^

<+>>  # Let F0* = F0 (plus) 1  (is 1 as of now; F0 will be added later)
[-<+<+>>] # Let A = S0 (plus) F0
# A may or may not be zero
# F0* may or may not be zero
# Tape:    F0* ' A ' 0  ' S1 ' F1 ' etc
#                ^

[>]<[->+<]  # Let B = A or F0*
# B may or may not be zero
<[-]>>  # Clear F0*
# Tape:     0 ' B ' 0 ' S1 ' F1 ' etc    (if A was zero)
#               ^
# OR        0 ' 0 ' B ' s1 ' F1 ' etc    (if A was nonzero)
#                   ^

# Let C = B or 2
# C will be guaranteed nonzero and unique from S0 and F0
>++<[<]>  # Create C
[.>>]  # Print (using S or F; does not matter)

>[>>]  # End on a zero cells with zero cells all to the right
# This is necessary for the coming functionality
# also as to not loop
]  # End non null block

# Now we consider if one of the strings was null
# Tape:    0 ' E0 ' 0 ' E1 ' etc    (if one string was null)
#          ^
# Tape:    0 '  0 ' 0 '  0 ' etc    (if neither string was null)
#          ^
# Where E is F or S (we don't care)

>[  # Execute only if one string was null

+  # Let A = E0 (plus) 1
# A may or many not be zero
# Tape: 0 ' A ' 0 ' E1 ' etc
#           ^

[>]+[<]>  # Let B = A or 1
# B is guaranteed nonzero and != E0
# Tape: 0 ' B ' ? ' E1 ' 0 ' E2 ' etc
#           ^

[.>>]  # Print

# End on zero cell as not to loop
]  # End null block

```
> 9 votes

# Answer
# Jelly, 8 bytes

```
żḟ@€ØAZḢ

```

**Try it online!**

### How?

```
żḟ@€ØAZḢ - Link: list of characters, a; list of characters, b
ż        - zip a and b
    ØA   - uppercase alphabet
 ḟ@€     - filter discard for €ach (swap @rguments)
      Z  - transpose the result
       Ḣ - head

```
> 6 votes

# Answer
# Python 3, 62 47 57 54 51 bytes

**Edit:** \- 5 bytes thanks to @Mr.Xcoder

**Edit:** +10 bytes to fix a bug

**Edit:** -3 bytes thanks to @betaveros

**Edit:** -3 bytes by using max instead of pop

```
lambda x,y:max({*"abc"}-{x[:1],y[:1]})+max(x,y)[1:]

```

Try it online!
> 5 votes

# Answer
# Mathematica, 111 bytes

```
(c=Characters;a=#2;While[f=Alphabet[]~RandomChoice~Length@#;f==#||f==c@a]&[#&@@c@{##}~MaximalBy~Length];""<>f)&

```

try it online (paste code with ctrl+v, place input at the end and hit shift+enter)

input

> \["test","me"\]

*thanx **@Not a tree** for checking and golfing -21 bytes*
> 4 votes

# Answer
# Charcoal, 22 bytes

```
ＦＥα×ι⌈⟦ＬθＬη⟧¿¬№⟦θη⟧ιＰι

```

Try it online! Link is to verbose version of code. Generates all strings of uppercase characters repeated to the length of the longer input and overprints all those that don't appear in the input. In other words, the output is normally `ZZZ...` unless that is one of the inputs, in which case it's `YYY...` unless that is the other input, in which case it's `XXX...`.
> 4 votes

# Answer
# Zsh, ~~51~~ ~~47~~ ~~37~~ 36 bytes

***-4** bytes by using builtin array `argv`, **-10** bytes by using prefix removal and `RC_EXPAND_PARAM`, **-1** byte by inlining the brace expansion.*

```
<<<${${${:-{1..3}${^@#?}}:|argv}[1]}

```

Try it online!

First, this was an awesome challenge, I went through a ton of ideas before landing on this one.

```
<<<${${${:-{1..3}${^@#?}}:|argv}[1]}
       ${:-             }            # empty fallback
                 ${ @#?}             # remove first character from each parameter
                 ${^@  }             # enable brace expansion (set -P)
           {1..3}${^@#?}             # expand to 1foo 2foo 3foo 1bar 2bar 3bar
     ${                  :|argv}     # Set difference with 'argv'
   ${                           [1]} # The first found element
<<<                                  # print to stdout

```

`@` and `*` are not identifiers, so `${ :|@}` and `${ :|*}` don't work, hence the use of `${ :|argv}`

> This method will work up to 93 inputs and find a 94th which is unique. Simply replace the `{1..3}` with the maximum possible range `{~..!}`.

# Zsh, ~~48~~ 47 bytes\*

```
for ((;$#i<${#${1:-$2}}||$@[(I)$i];i++)):
<<<$i

```

Try it online!

Completely new method courtesy of JoKing's Perl 6 submission, but doesn't work on large strings (n\>20) due to integer size restrictions. `$@[(I)$i]` is reverse array lookup to largest index, it will output zero (falsy in arithmetic expansion) if $i is not found in the command line parameters.
> 4 votes

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

```
{(1 x.max.comb...*∉$_).tail}

```

Try it online!

Anonymous codeblock that takes input as a list of two strings, and returns the first number from `1111...` with a non-empty amount of 1s that isn't in the input.

### Explanation:

```
{                          }   # Anonymous code block
  1 x.max.comb                 # String multiply 1 by the size of the non-empty string
              ...              # Create a sequence increasing by 1
                 *∉$_          # Until the number is not in the input
 (                   ).tail    # And take the last number

```
> 4 votes

# Answer
# MATL, 12 bytes

```
c"1Y2@X-1)&h

```

Input is a cell array of strings containing printable ASCII chars. The output is formed from the letters `'ABC'`, and so belongs to the input domain.

Try it online!

### Explanation

The output is as long as the longest input string. Its *n*-th character is the first letter from `'ABC'` that is different from the *n*-th character of both input strings.

```
c        % Concatenate the two strings vertically. If one is shorter it is
         % right-padded with spaces. Gives a 2-row character matrix
"        % For each column
  1Y2    %   Push the string 'ABC...Z' (the upper-case letters)
  @      %   Push current column
  X-     %   Set difference
  1)     %   Get first character
  &h     %   Horizontally concatenate the results so far
         % End (implicit). Display stack (implicit)

```
> 3 votes

# Answer
# 05AB1E, ~~8~~ 7 bytes

```
øvAyм¬?

```

Uses the **05AB1E** encoding. Try it online!
> 3 votes

# Answer
## Haskell, ~~56~~ ~~52~~ 48 bytes

```
x#y|_:t<-max x y=[c:t|c<-"abc",c:t/=x,c:t/=y]!!0

```

Try it online!

Replace the first char of the maximum of the two input strings with `a`, `b`and `c` and pick the first one that is different from both input strings.
> 3 votes

# Answer
# Ruby, 53 bytes

```
->a,b{([?a,?b,?c].map{|e|e*[a,b].max.size}-[a,b])[0]}

```

Try it online!

Basically generates the strings `a...a`, `b...b`, and `c...c` and selects the first not in the input.
> 3 votes

# Answer
# ES6, 54 bytes

```
a=>b=>(a[0]+b[0]|0?'a':9-(a[0]^b[0]))+(a||b).substr(1)

```
> 3 votes

# Answer
# Pyth, 7 ~~8~~ bytes

```
hC-LG.T

```

*1 byte thanks to Jakube*

Test suite

We use `.T`, length preserving transpose, rather than `C`, truncating transpose, so that it works on inputs where one string is empty.

Given two strings as a tuple, we transpose them (`.T`), then map the resulting pair of characters or single character by subtracting the character(s) from the lowerase alphabet with `-LG`, then transpose the resulting list of strings of unused characters with `C`, then return the first such string with `h`. This consists of the first letter alphabetically that is not in either string, for each position.
> 3 votes

# Answer
# Java (OpenJDK 8), ~~100~~ 73 bytes

-27 bytes thanks to @Nevay's magical touch! :)

```
a->b->{b=b.length<1?a:b;if(a.length<1||(b[0]^=2)==a[0])b[0]^=1;return b;}

```

Try it online!

Input domain = Printable ASCII + codepoint 127.
> 3 votes

# Answer
# APL (Dyalog Unicode), 11 bytesSBCS

Full program, takes input as a 2-element nested list.

```
⊃¨⎕A∘~¨,⌿↑⎕

```

Try it online!
> 3 votes

# Answer
# Pyth, 23 22 bytes

```
+.)-.{<G3.{,<Q1<KE1t|K

```

**Try it here!**

# Pyth, 22 bytes

```
+eS-.{<G3.{,<Q1<KE1t|K

```

**Test Suite!**

---

# Explanation

```
+.)-.{<G3.{,<Q1<KE1t|K  - Full program.
      <G3               - Yields the String "abc"; Alphabet[:3].
    .{                  - Set formed by the above.
         .{,<Q1<KE1     - Set formed by input_1[:1] and input_2[:1]
   -                    - Set subtraction.
 .)                     - Pop the last element.
+                       - Append.
                   t|K  - input_1[1:] or input_2[1:], relying on the result of Logical OR.

```
> 2 votes

# Answer
# Ruby, 56 bytes

```
->a,b{a,b=b,a if a<b;a[0]=([?a,?b,?c]-[a[0],b[0]])[0];a}

```
> 2 votes

# Answer
# Java 8, 119 bytes

Lambda (curried) from `String` to lambda from `String` to `String`. Assign to `Function<String, Function<String, String>>`.

```
s->t->{String r=s.length()>t.length()?s:t;while((s+t).contains(r))r=r.substring(1)+(char)(Math.random()*128);return r;}

```

Try It Online

## Ungolfed lambda

```
s ->
    t -> {
        String r = s.length() > t.length() ? s : t;
        while ((s + t).contains(r))
            r = r.substring(1) + (char) (Math.random() * 128);
        return r;
    }

```

This solution rotates random ASCII characters into the longer string until the required conditions are satisfied. Inputs are UTF-8 and outputs are ASCII.

I don't know the gritty details of Unicode, but it seems plausible to me that this solution could fail when an appended `char` joins the preceding code point to form a single code unit. If someone who knows more about this can verify this, I'll change the input domain to ASCII.

# Java 8, 126 bytes

Same type as above.

```
s->t->{String r;for(byte[]o=(s.length()>t.length()?s:t).getBytes();(s+t).contains(r=new String(o));o[0]%=128)o[0]++;return r;}

```

Try It Online

## Ungolfed lambda

```
s ->
    t -> {
        String r;
        for (
            byte[] o = (s.length() > t.length() ? s : t).getBytes();
            (s + t).contains(r = new String(o));
            o[0] %= 128
        )
            o[0]++;
        return r;
    }

```

This increments the first byte of the longer string, wrapping within ASCII, until the required conditions are met. Inputs and outputs are ASCII strings.
> 2 votes

# Answer
# Perl 5, ~~82~~ 79 bytes

```
sub{$_=$_[0];$_=$_[1]||$_ if/^(xz*)?$/;s/[^z]/z/||s/./y/;$_ eq$_[1]&&s/./x/;$_}

```

Takes input as two separate arguments and returns the third string.

The subroutine attempts to produce a string very similar to the first string but with the first non-`z` character replaced with a `z`. Then it deals with corner cases by replacing the first character with `y` or `x`, as needed, if it finds that one of the inputs was in fact a sequence of all `z`'s.
> 2 votes

# Answer
# R, ~~89~~ 67 bytes

*@Giuseppe saved 9 bytes, @user2390246 saved 13 bytes*

### function

```
function(x,y)sub("^.",letters[!letters%in%substr(c(x,y),1,1)][1],x)

```

### demo

```
# define function
f <- function(x,y)sub("^.",letters[!letters%in%substr(c(x,y),1,1)][1],x)

# test cases
f("test","test")
[1] "aest"
f("do","don't")
[1] "ao"
f("ye s","yes")
[1] "ae s"
f("maybe","mayue")
[1] "aaybe"
f("false","false")
[1] "aalse"
f("false","true")
[1] "aalse"
f("1","")
[1] "a"
f("art","bug")
[1] "crt"

```
> 2 votes

# Answer
# Perl 5, 68 bytes

```
sub{$_="a"x length $_[0]||$_[1];$_++while $_ eq$_[0]||$_ eq$_[1];$_}

```

Explanation:

* starts with (string of letter "a" as long as first string) or second string if that is false i.e. zero-length
* keeps incrementing that until it's different from both first and second

Starting from "a"s was to avoid incrementing to point where Perl lengthens the string; with only two strings to avoid being same as, it couldn't overflow.

Execute with:

```
perl -e '$s = ' -E 'sub{$_="a"x length $_[0]||$_[1];$_++while $_ eq$_[0]||$_ eq$_[1];$_}' -E ';say $s->("z", "true")'

```
> 2 votes

# Answer
# C (gcc), ~~70~~ ~~65~~ ~~73~~ ~~67~~ 61 bytes

The function needs the provided strings to be mutable (i.e. either arrays or dynamically allocated).

```
f(a,b)char*a,*b;{a=*a?a:b;*a=*a>70?33:99;*a+=*a==*b;puts(a);}

```

Try it online!

Works for the standard ASCII range

Explanation:

```
a=*a?a:b           // If a is empty, point to b instead
*a=*a>70?33:99     // Choose a different value for the 1st character of a,
                   // while giving enough space to increment it without
                   // going back to its previous value
*a+=*a==*b         // Increment the 1st character of a if the arbitrary
                   // chosen value is equal to the value of the 1st
                   // character of b
puts(a)            // Outputs a

```
> 2 votes

# Answer
# Bash, ~~115~~ .. 77 bytes

Replaces first char of the first (non-empty) input string with 1,2,3 until no match is found to either input. Try it Online!

***-9, -12, -9, -8*** *bytes all thanks to GammaFunction*

```
x="${1:-$2}"
for s in {1..3}"${x:1}"
{ [[ $s = @($1|$2) ]]||break;}
echo "$s"

```

(quite an improvement over the original...)
> 2 votes

# Answer
# Brachylog, 10 bytes

```
∋l~lℕṫ.&≡ⁿ

```

Try it online!

### Explanation

There may be a better way to do this, but I've been fighting Brachylog strings for a while now and this solution works.

```
∋           For some element of the input list
 l          get its length
  ~l        That is also the length of
    ℕ       some positive integer
     ṫ      Converting that integer to a string
      .     is the output
       &    Also:
         ⁿ  It is not true, for any X in the input list
        ≡   that the output equals X

```

Outputs strings like `"100"`. If `"100"` is already in the input list, goes to `"101"`, etc.
> 2 votes

# Answer
# Perl 5, 79 + 1 (-p) = 80 bytes

```
$"=<>;chop;$_=length($,=$_)>length$"?$_:$";s/./chr$&+65+$i++/e while/^($"|$,)$/

```

Try it online!
> 1 votes

# Answer
# Japt, 17 bytes

```
;B¬£ñl g1 çXÃkU v

```

Repeats the letters `A-Z` to the length of the longer input, removes the values in the input, and get the first item in the array.

Try it online!

## Old solution, 18 bytes

```
;@!UøX}a@ñl g1 çBö

```

Try it online!

Chooses a random character from the alphabet and repeats it to the length of the longer input string, until it is not present in the input.
> 1 votes

# Answer
# CJam, ~~31~~ ~~30~~ 23 bytes

```
q~:A:e>,3,sf*{A\f=:+!}=

```

Takes printable ASCII as input. Outputs either a string of 0's, 1's, or 2's that is the same length as one of the input strings. The logic is that one of those can't be either of the input strings!

Try it Online

```
q~:A    e# Store input array as var 'A'
:e>,    e# Take the length of the lexicographically greater string in the input array
3,s     e# Generate "012"
f*      e# Repeat each number as many times as the longer string length, yielding something like ["000","111","222"]
{       e# Search array of number strings for first that returns true for this function
A\f=    e# Map each string in the input array to whether it equals the current number string (0,1)
:+!     e# Add up the array of bits and take the logical not. This returns true iff both array values were not equal to the current number string.
}=      e# Return the first number string that returns true.

```
> 1 votes

# Answer
# Python 3, 74 73 bytes

-1 byte thanks to Step Hen

```
def f(x,y,i=1):
 while i*10<10**len(x or y)or str(i)in x+y:i*=2
 print(i)

```

Prints lowest integer with the same length as the first of the inputs that has nonzero length.
> 1 votes

# Answer
# Python 2, 77 bytes

```
a=input()
b=ord(a[0][0])+1
if b==ord(a[1][0]):b+=1
print unichr(b)+a[0][1:-1]

```

I think it has some potential. The idea is that it adds 1 to the 1st char in the 1st string, then checks if the other input's 1st char is the same.

\**Note, ^ doesn't handle 0 length strings, so it doesn't really work at this length.

Here's a super long solution that works with 0 length

# 146 Bytes

```
a=input()
def c(i):print unichr(ord(a[i][0])+1)+a[i][1:];exit();
for x in range(2):if len(a[x-1])<1:c(x)
if a[0]==a[1]:c(1)
print a[1][0]+a[0][1:]

```

Any improvements would be appreciated!
> 1 votes

# Answer
# C# (Mono), 94 bytes

```
s=>t=>{var r=s!=""?s:t;while(r==s|r==t)r=r.Substring(1).Insert(0,(char)(r[0]+1)+"");return r;}

```

Try it online!
> 1 votes

# Answer
# Python 3, 67 bytes

```
lambda a,b:[k for k in"abc"if k not in b[:1]+a[:1]][0]+(a or b)[1:]

```

Try it online!

Picks the first character of `"a"`, `"b"`, and `"c"` which neither string begins with - all three characters can't be the first character of one of two strings. The first character of `a` is then replaced with that character, unless `a` is empty, in which case the first character in `b` is replaced instead.
> 1 votes

# Answer
# Pip, 16 bytes

```
T#iN#*g&iNIg++ii

```

Try it online!

Increments the number `i` until `i` has the same length as one of the inputs and does not equal either of the inputs, and then prints `i`. Takes about 30 seconds on TIO to output `100000` for length-six input.
> 1 votes

# Answer
# Pip, 16 bytes

```
YMXgRXX9WyNg--yy

```

Try it online!

Different approach from my first submission (and much faster):

```
   g              List of command-line args     ["abc" "9999"]
    R             Replace
     XX           any character (regex `.`)
       9          with 9                        ["999" "9999"]
 MX               Get the max                   9999
Y                 Yank it into y variable
        W         Loop while
         yNg      y is in the cmdline args:
            --y    Decrement y
               y  Output y                      9998

```
> 1 votes

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

```
a=>b=>(a[0]&1^b[0]&2^7)+(a||b).slice(1)

```

Try it online!

Obvious source the 3rd byte
> 1 votes

# Answer
# Haskell, 41 bytes

```
n[]_=[]
n _[]=[]
n(i:c)(h:t)=succ i:n c t

```
> -1 votes

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


title: Simplest Tiling of the Floor

text:
# Question
Title: Simplest Tiling of the Floor
You should write a program or function which receives a string describing the floor as input and outputs or returns the area of the simplest meta-tiling which could create the given pattern of the floor.

The floor is a part of a square grid. Every square tile is colored either azure or black (represented by `a` and `b` in the input).

An example floor:

```
  aaaa
ababab
aaaaa

```

A meta-tiling

* is built from an `N` by `M` rectangular meta-tile of azure and black squares
* the used meta-tiles are identical up to translation (you cannot rotate or mirror them)
* if the sides of two meta-tiles are connected they should connect along their whole length (i.e. meta-tiles tile the space in a grid-like fashion)

An example meta-tile:

```
ba
aa

```

and the meta-tiling created by it:

```
       .
       .
       .
    babababa
    aaaaaaaa
... babababa ...
    aaaaaaaa
    babababa
    aaaaaaaa
       .
       .
       .

```

This meta-tiling creates the upper shown floor as the left letters show:

```
       .
       .
       .
    ********
    ***aaaa*
... *ababab* ...
    *aaaaa**
    ********
    ********
       .
       .
       .

```

A meta-tiling is simpler than another if the area of its meta-tile is smaller. Our example has an area of `2*2 = 4` which is the smallest possible for the example floor. So the output should be `4` for the example.

## Input

* A string consisting of the characters `a b space` and `newline` containing at least one `a` or `b`.
* The letters (`ab`) form one 4-connected (side-by-side connected) shape.
* There will be no unnecessary spaces at the front of the rows i.e. there will be at least one row starting with `a` or `b`.
* You can choose of two input format:

+ No unnecessary whitespace at the end of rows (as seen in the examples).
    + Spaces on the right side of the rows to make all rows the same length as the longest row.
* Trailing newline is optional.

## Output

* A single integer, the area of the smallest possible meta-tile whose tiling contains the input floor.

## Examples

Examples are delimited by dashes. The three parts of an example are input, output and one of the possible smallest meta-tiles.

```
a

1

a
-----------------
 aaaa
aaa
a

1

a
-----------------
aabaab
abaa
aaba

6

aab
aba
-----------------
aabaab
a  a a
aabab

18

aabaab
aaaaaa
aababa
-----------------
ba
aaab

8

baaa
aaab
-----------------
 aaaa
ababb
aaaa

10

aaaaa
ababb
-----------------
 a aa
ab ba
 aba

6

aa
ab
ba
-----------------
 aaaa
abab
aaaa

4

aa
ab
-----------------
ba
 ba
  b

4

ba
ab
-----------------
baa
aba
aab

9

baa
aba
aab
-----------------
 aaaa
aabaa
aaaa

6

aaa
aab

```

This is code golf so the shortest entry wins.

# Answer
> 4 votes
## C - 208 bytes

```
w,q,n,m,r,g,u;t(char*f){for(w=0;f[w++]-10;);for(q=1;;q++)for(n=1;m=q/n,n<=q;++n)if(n*m==q){char t[q];bzero(t,q);r=q;for(g=0;f[g];++g){u=g/w%m*n+g%w%n;r=t[u]+f[g]-195?r:0;if(f[g]&64)t[u]=f[g];}if(r)return r;}}

```

Equivalent code before golfing:

```
#include <stdio.h>
#include <strings.h>

int t(char* f) {
    int w = 0;
    for ( ; f[w++] - 10; );

    for (int q = 1; ; q++) {
        char t[q];
        for (int n = 1; n <= q; ++n) {
            int m = q / n;
            if (n * m == q) {
                bzero(t, q);
                int r = q;
                for (int g = 0; f[g]; ++g) {
                    int u = g / w % m * n + g % w % n;
                    if (t[u] + f[g] == 195) {
                        r = 0;
                    }
                    if (f[g] & 64) {
                        t[u] = f[g];
                    }
                }
                if (r) {
                    return r;
                }
            }
        }
    }
}

```

The algorithm is fairly brute force, so it should be reasonably obvious how it works based on the code. Here are a few comments anyway:

* Input is expected to have the form with trailing spaces so that all lines have the same length.
* First loop finds the width by looking for first newline character.
* Outer loop is over candidate meta-tile sizes `q`. Exits with a `return` when a meta-tile can cover the floor. Note that the loop does not need another exit condition since there is always a solution (worst case is size of input).
* First nested loop and following `if` enumerates valid meta-tile width/height combinations for size `q`.
* A character array matching the candidate meta-tile size is zero-initialized.
* Inner loop iterates over all tiles in the floor.
* `u` is the index in the meta-tile that corresponds to the floor tile.
* If both floor tile and meta-tile tile are `a` or `b` and different (sum of `a = 97` and `b = 98` is `195`), there is a mismatch, and the meta-tile size with the attempted dimensions will not work.
* Otherwise, if the floor tile is `a` or `b`, the tile color is copied to the candidate meta-tile.
* Returns size of meta-tile when successful match was made, i.e. if the attempted match was not marked as failed.

Test code used:

```
#include <stdio.h>

extern int t(char* s);

int main()
{
    printf("%d\n", t(
        "a\n"
    ));
    printf("%d\n", t(
        " aaaa\n"
        "aaa  \n"
        "a    \n"
    ));
    printf("%d\n", t(
        "aabaab\n"
        "abaa  \n"
        "aaba  \n"
    ));
    printf("%d\n", t(
        "aabaab\n"
        "a  a a\n"
        "aabab \n"
    ));
    printf("%d\n", t(
        "ba  \n"
        "aaab\n"
    ));
    printf("%d\n", t(
        " aaaa\n"
        "ababb\n"
        "aaaa \n"
    ));
    printf("%d\n", t(
        " a aa\n"
        "ab ba\n"
        " aba \n"
    ));
    printf("%d\n", t(
        " aaaa\n"
        "abab \n"
        "aaaa \n"
    ));
    printf("%d\n", t(
        "ba \n"
        " ba\n"
        "  b\n"
    ));
    printf("%d\n", t(
        "baa\n"
        "aba\n"
        "aab\n"
    ));
    printf("%d\n", t(
        " aaaa\n"
        "aabaa\n"
        "aaaa \n"
    ));
    return 0;
}

```

Output:

```
1
1
6
18
8
10
6
4
4
9
6

```

# Answer
> 6 votes
# APL(Dyalog Unicode), ~~53~~ ~~37~~ 36 bytes SBCS

```
{⌊/×/¨⍸(~6∊' a'∧/⍤⍳⍵⊢⌸⍥,⍨|)⍤0 2⍨⍳⍴⍵}

```

Try it on APLgolf!

Instead of partitioning, this one groups the characters in the matrix by their 2D indices modulo current size. I came up with it independently, but apparently it's the same as Zgarb's idea. But there's a funky part in this solution: in order to test if a group contains both `a` and `b`, it maps space/a/b into 1, 2, 3 respectively via find-index function, and calculates their LCM to see if it is 6.

---

# APL (Dyalog Unicode), 53 bytes

```
{⌊/×/¨⍸{∧/,⍲/¨'ab'∘∊¨⊃{⍉,⌿↑⍺⊂⍵}/(⊂,⍨⍴⍴¨⍺↑¨≡)⍵}∘⍵¨⍳⍴⍵}

```

Try it online!

A function that takes a character matrix as the argument. Basically, tries all possible tile sizes, testing if partitioning by that size would give at most one of `ab` on every cell.

### Illustration

```
Example input:
 a aa
ab ba
 aba
Example tile size: 2 rows, 2 columns
Partition:
+--+--+-+
| a| a|a|
|ab| b|a|
+--+--+-+
| a|ba| |
+--+--+-+
Cells collected into a tile:
+------+------+
|  a b |aa aa |
+------+------+
|a a   |bb    |
+------+------+
Since top left cell has both a and b, this tile size is invalid.

```

### How the code works

```
{⌊/×/¨⍸{∧/,⍲/¨'ab'∘∊¨⊃{⍉,⌿↑⍺⊂⍵}/(⊂,⍨⍴⍴¨⍺↑¨≡)⍵}∘⍵¨⍳⍴⍵}
             ⍝ ⍵ ← Char matrix
        ⍳⍴⍵  ⍝ Generate possible tile sizes as a matrix of length-2 vectors
{...}∘⍵¨     ⍝ Test if each tile size is valid...
             ⍝   ⍵ ← Input char matrix, ⍺ ← tile size
(⊂,⍨⍴⍴¨⍺↑¨≡)⍵  ⍝ Create partition vectors and join with ⍵ for RTL reduction
(         ≡)⍵  ⍝ Depth of ⍵, which always gives 1 for valid input
       ⍺↑¨     ⍝ Overtake 1 to the length of each of ⍺, e.g. (1 0)(1 0 0)
    ⍴⍴¨        ⍝ Cycle each to the length of the dimensions of ⍵,
               ⍝ e.g. (1 0 1 0 1)(1 0 0 1 0)
 ⊂,⍨           ⍝ Append the enclosed ⍵
⊃{⍉,⌿↑⍺⊂⍵}/  ⍝ Partition and collect all cells at the same position in the tile
 {       }/  ⍝ Reduce by...
      ⍺⊂⍵    ⍝ Partition ⍵ into consecutive columns at 1s of ⍺
     ↑       ⍝ Mix so that short partition is padded with spaces
   ,⌿        ⍝ Collect the cells at the same position
  ⍉          ⍝ Transpose to do the same for rows
⊃            ⍝ Disclose one level of nesting (which is a side effect of /)
∧/,⍲/¨'ab'∘∊¨  ⍝ Test if no tile position contains both a and b
      'ab'∘∊¨  ⍝ For each tile position, evaluate (has a)(has b)
   ⍲/¨         ⍝ Reduce each by NAND; 1 if the tile position has at most one of ab
∧/,            ⍝ Test if it is true for all positions
⌊/×/¨⍸  ⍝ Extract the answer (the smallest area)
     ⍸  ⍝ 1-based coordinates of ones; the tile sizes which passed the test
⌊/×/¨   ⍝ Minimum of the areas

```

# Answer
> 4 votes
# Husk, 30 bytes

```
ḟ(SδV(ΛË←k→f←δṁz,¶⁰¤Ṫeo¢ḣ)↔Ḋ)1

```

Try it online!

## Explanation

I loop through all nonnegative integers until I find one that, when split into two factors in some way, gives a horizontal and vertical period for the input patch. The period is checked by grouping the 2D indices of non-space characters by their values modulo the two numbers, and checking that each group contains equal characters.

```
ḟ(…)1   Starting from 1, find a number that satisfies (…).

SδV(…)↔Ḋ   We're looking at a number, say n=6.
       Ḋ   Divisors: d = [1,2,3,6]
S     ↔    Reverse and apply to both:
 δV(…)     does any pair from d and its reverse satisfy (…)?
           For n=6, the pairs are (1,6), (2,3), (3,2), and (6,1).

ΛË←k→f←δṁz,¶⁰¤Ṫeo¢ḣ   Check if (a,b) is a valid metatile.
             ¤        For both a and b:
                  ḣ     take range from 1 to it
                o¢      and cycle it infinitely.
              Ṫ       Combine these by taking outer product by
               e      pairing.
                      For (a,b)=(2,3), this gives the infinite 2D array
                      A=[[[1,1],[1,2],[1,3],[1,1],..],
                         [[2,1],[2,2],[2,3],[2,1],..],
                         [[1,1],[1,2],[1,3],[1,1],..],
                         ..]
           ¶⁰         The input, split at newlines.
       δṁ             For each row of it and A:
         z,             zip them (discarding overflowing rows and pairs of A)
       δṁ               and concatenate the results.
                      Now we have a list of pairs like ('a',[2,3]) that contain
                      a character from the input and its coordinates mod (a,b).
     f←               Keep those whose left part is truthy, i.e. not a space.
   k→                 Classify (into separate lists) by right part.
Λ                     Does every class
 Ë←                   have all equal left parts?

```

# Answer
> 3 votes
# Pip `-r`, 52 bytes

```
MN:$*_M{$&{$*$Q*$.aDCs}M_UWa@1MMyUW@a}FI\,#gCP\,#@Yg

```

Takes input from lines of stdin, with trailing spaces as needed. Try it online!

Approach taken from Bubbler's APL answer: We try all possible meta-tile dimensions, filtering for the ones that have a unique non-space character at each position. `UW` (unweave) is very useful for grouping the input grid by tile positions. We then multiply each successful pair of dimensions to get the area of the tile, and take the minimum.

Leave a comment if you'd like a more detailed explanation.

# Answer
> 2 votes
# Brachylog, 44 bytes

```
∧ℕf⟨≡z↔⟩∋[X,Y]×.&ṇġ↙Xz₁ġᵐ²↙Yz₁ᵐ²zᵐ{c;Ṣx=}ᵐ²∧

```

Try it online!

A port of Zgarb's Husk answer. Brachylog doesn't have infinite lists or cyclic indexing, so instead I'm using the "groups" predicate `ġ` (`[1,2,3,4,5]ġ₂ -> [[1,2],[3,4],[5]]`) and then zip `z` (`[[1,2],[3,4],[5]]z₁ -> [[1,3,5],[2,4]]`) to get lists of the characters at tile-equivalent positions.

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


title: Inspired by HQ9+: 4-Behavior Polyglot

text:
# Question
Title: Inspired by HQ9+: 4-Behavior Polyglot
Create a program that can be run in 4 different languages such that:

* One language prints "Hello World!"
* One language outputs its own source code
* One language outputs 99 bottles of beer on the wall, that is:
```
99 bottles of beer on the wall
99 bottles of beer
Take one down, pass it around
98 bottles of beer on the wall

98 bottles of beer on the wall
98 bottles of beer
Take one down...

<the pattern continues for a while>

...pass it around
1 bottle of beer on the wall

1 bottle of beer on the wall
1 bottle of beer
Take one down, pass it around
No more bottles of beer on the wall

```
* One language takes a nonnegative integer as an input and outputs that integer + 1

## Rules and Scoring

* This is code golf, so shortest code wins. **Score in character count** rather than byte count for this challenge so that golfing languages that use specialized codepages are not disadvantaged by their UTF-8 representations.
* Standard rules and loopholes apply
* Each language may optionally output a trailing newline for its designated output
* Each language may use any I/O convention that is convenient to that language. The convention does not need to be consistent across all four languages; for instance, one uses stdout, another uses the return value, one writes to a file, and the last one spawns an alert containing the text.
* Golfing languages that have the option to use specialized codepages must use a standard encoding; they may not take advantage of a byte being interpreted as a different character in another encoding.
* Hello World may optionally include a comma after "Hello", thus `Hello, World!` is a valid output.
* Standard quine rules apply and the only superfluous output allowed is a trailing newline.
    + Text, or any other "language" where all programs are quines, is not a valid language for the quine.
* 99 Bottles of Beer requires:
    + A blank line between each verse
    + No blank lines within any verse
    + The singular/plural distinction of 'bottle' vs 'bottles'
    + `no more` instead of `0` on the last line
    + Each line may have any amount of trailing whitespace (or none at all)
* The incrementing program must support all input integers that can be incremented natively by its language.
    + For languages which support unsigned integers, the largest unsigned integer should be used
    + For languages which represent all numbers as floating point numbers, this would require supporting all input numbers up to \\$2^{53}-1\\$.
    + For languages which natively support arbitrary-sized integers, *all* positive integers must be supported.

Format the header of your answer like this:

```
# <language for H, <language for Q>, <language for 9>, <language for +>, n characters

```

# Answer
# Ruby, \>\<\>, HQ9+, Befunge-93, 62 characters

```
#9&1+.@.10[0[fr'
puts"\u0048ello World!"#.1*57;!?lo r]r}:*3da'

```

**"Hello World!"** (Ruby)

Relevant part of code:

`puts"\u0048ello World!"`

**quine** (\>\<\>)

After colliding with the `#` mirror, both lines are read as string literals and printed with a newline between.

**99 bottles of beer on the wall** (HQ9+)

Code contains no `H` or `Q`, and exactly one `9`, so the lyrics of the song are printed once.

**+1 program** (Befunge-93)

After jumping over `9` due to the `#` trampoline, a simple +1 program is run `&1+.@`
> 10 votes

# Answer
# Python 2, Perl 5, JavaScript (Node.js), Ruby, 524 characters

```
0//1;q=0;print"Hello, World!";'''/.__id__;puts STDIN.read.succ;%q[=;$_=q{print q@0//1;q=0;print"Hello, World!";'@.qq@''/.__id__;puts STDIN.read.succ;%q[=;\$_=q{$_};eval;q[\n@.q@for(x=99,z=(a=' on the wall\n')=>`${x||'No more'} bottle${1-x?'s':''} of beer`+a;x;)console.log(z()+z(n='\n')+'Take one down and pass it around\n'+(x--,z()))//]#]#'@.q@''@};eval;q[
for(x=99,z=(a=' on the wall\n')=>`${x||'No more'} bottle${1-x?'s':''} of beer`+a;x;)console.log(z()+z(n='\n')+'Take one down and pass it around\n'+(x--,z()))//]#]#'''

```

## `Hello, World!`, Python 2

Pretty straightforward, this performs integer division in void context, then sets `q` to `0`, prints `Hello, World!` and the rest of the program is contained in a `'''` quoted multi-line string. With long, unprocessed, strings removed:

```
0//1;q=0;print"Hello, World!";'''...'''

```

Try it online!

## Quine, Perl 5

Probably the most complicated, but not overly. It's a pretty standard `$_="...";eval` quine template, but we have to include the preceding code for other languages too. The `0//1` performs integer division in a void context and then `q=...=` is a single-quoted string delimited by `=` in a void context. Then the quine is built into `$_` using an `@`-delimited string. I switched from using `$<` in Ruby for `STDOUT` to avoid having to keep switching in and out of quotes more, although I ended up having to do that for Python 2's `'''` anyway, which needed to be broken up to avoid being triggered. Once `$_` is built, `eval` is called and the rest of the program is contained in `q[...]` (a `[`...`]` delimited, single-quoted string). Here's a simplified version:

```
0//1;q=...=;$_=q{print q@...'@.qq@''...=;\$_=q{$_};eval;q[\n@.q@...'@.q@''@};eval;q[...]...

```

Try it online! Verification.

## 99 bottles of beer, JavaScript (Node.js)

JavaScript is relatively easy to have in other code as `//` comments out the rest of the line, so `0//1` is just `0` in void context, followed by a comment and the string closing delimiters of the other three languages are avoided using `//` too.

I borrowed the main code from here for this, amending as necessary as using `\n` instead of a literal newline was slightly easier for the quine contents.

```
0//...
for(x=99,z=(a=' on the wall\n')=>`${x||'No more'} bottle${1-x?'s':''} of beer`+a;x;)console.log(z()+z(n='\n')+'Take one down and pass it around\n'+(x--,z()))//...

```

Try it online!

## Accumulator, Ruby

This uses a technique I've used in quite a few polyglots with Ruby in the past. The `0//.../.__id__` construct is parsed as `0` dividede by the `__id__` property of the `/.../` regex (`__id__` is chosen as it's a short property that returns a number to avoid a type mismatch error). Then `STDIN.read.succ` returns the next string that succeeds it, so `9` results in `10`, etc. The rest of the code is wrapped in `%q[...]` effectively hiding it.

```
0//.../.__id__;puts STDIN.read.succ;%q[...]#...

```

Try it online!

---

# Python 2, Perl 5, HQ9+, Ruby, 181 characters

Using HQ9+ for the `99 Bottles` implementation, reduces code size considerably:

```
0//1;q=9;print chr(72)+'ello, World!'#/.__id__;puts STDIN.read.succ;#=;$_=q{print"0//1;q=@{[1^8]};print chr(72)+'ello, World!'#/.__id__;puts STDIN.read.succ;#=;\$_=q{$_};eval"};eval

```

## `Hello, World!`, Python 2

Try it online!

## Quine, Perl 5

Try it online! Verification.

## 99 bottles of beer, HQ9+

Since the code only contains `9` from `HQ9` (and `+` doesn't cause any output) it's all that's executed. My main worry with this is finding an interpreter that complies with the requirements, which might make this invalid perhaps.

```
9

```

## Accumulator, Ruby

Try it online!
> 8 votes

# Answer
# Trigger, Ruby, Fortran (GFortran), COW, ~~371~~ ~~370~~ 312 characters

```
!t='HHHeeelll lllooom   WWWooorrrlllddd!!!MoO  qOOM
character*35::n="No more bottles of beer on the wall",f="(2(a,/),a)",b
do i=99,1,-1
write(b,"(i0,a)")i,n(8:14)//n(15+1/i:)
if(i<99)print f,b
print f,b,b(:18-1/i),"Take one down, pass it around"
enddo
print"(a)",n
end!';eval$s=%q($><<"!t='#{t}';eval$s=%q(#$s)")

```

What an unholy combination this is!

### *Hello World!*, Trigger

The idea to use Trigger came from some of the answers to this question. The main advantage is that it's relatively easy to embed within other garbage. The interpreter effectively sees

```
!t='HHHeeelll lllooom   WWWooorrrlllddd!!!MoO  q
q($><<"!t='#{t}';eval$s=%q(#$s)")

```

Try it online!

The functional part is `HHHeeelll lllooo WWWooorrrlllddd!!!`: triple letters are printed once. (The space between the two `lll` groups is needed for proper parsing.) The  `q` (two leading spaces) at the end of the first line is essential to avoid double letters later in the full code (such as those in `bottles` and `beer`) that would otherwise create conditional jumps with hard-to-predict consequences. (Indeed, without  `q` the code appears to enter an infinite loop.) This possibility is headed off by jumping forward to the next `q`, which happens to be in the last line of the full program. As far as the outside world is concerned, the remainder of the program is no-ops.

### Quine, Ruby

The full program is really just a straightforward extension of the Ruby quine

```
eval s=%q(puts"eval s=%q(#{s})")

```

with two modifications: (i) the global variable `$s` saves a byte on the string interpolation and (ii) `$><<` is used instead of `puts` to avoid a trailing newline. The rest of the program defines a string variable `t`, which contains all the functional code for the other three parts of the polyglot. The exclamation mark (negation) in `!t` at the top of the program is effectively a no-op (though a warning is emitted to STDERR).

Try it online! or verify quine (thanks to @DomHastings for the idea)

### *99 Bottles of Beer*, Fortran

Fortran's string manipulation capabilities are truly horrendous, but it's one of the few languages I'm proficient enough in to golf *99 Bottles* from scratch.

As `!` is the comment character in Fortran, the compiler sees

```
character*35::n="No more bottles of beer on the wall",f="(2(a,/),a)",b
do i=99,1,-1
write(b,"(i0,a)")i,n(8:14)//n(15+1/i:)
if(i<99)print f,b
print f,b,b(:18-1/i),"Take one down, pass it around"
enddo
print"(a)",n
end

```

Try it online!

Except for the first and last verses, each iteration of the loop actually prints the last line of the previous verse followed by the first three lines of the current verse.

### Increment, COW

As COW completely ignores all non-instructions, all the interpreter sees is

```
oomMoOOOM

```

Try it online!

This is a simple sequence of three operations: read an integer from STDIN (`oom`), increment it (`MoO`), and print to STDOUT (`OOM`). TIO's COW interpreter uses signed 32-bit integers so the largest input for which the output is correct is \\$2^{31}-2\\$.
> 7 votes

# Answer
# Help, WarDoq!, Befunge-98 (FBBI), HQ9+, SOGL, 15 characters

```
I←9La@,+1!',kf"

```

I already feel bad for writing this. At least the quine is not in PHP.

# Explanation

## Help, WarDoq!

Ignores the first 3 characters, `L` prints `Hello World!` and `a` tries to read 2 integers (and exits with an error).

## Befunge

Mostly stolen from this. `I` bounces unless redefined by a fingerprint, so it can be used instead of the starting `<`.

## HQ9+

I used the interpreter http://web.archive.org/web/20060714044320/http://www.safalra.com/programming/interpreters/hq9plus/. Its output is very similar to the lyrics in the question, but, unfortunately, it's not exactly the same. When I found it, I assumed that there is at least one HQ9+ interpreter that outputs the correct lyrics. However, finding it is left as an exercise to the reader. and since the challenge is inspired by HQ9+, how can HQ9+ be wrong?

## SOGL

Implicit input, then `I` increments and  exits (with implicit output).
> 4 votes

# Answer
# Hello++, , 99, brainf\***, 5 characters

```
#H,+.

```

---

# "Hello World" in Hello++

According to the language spec:

> Hello++ will print out "Hello World" whenever it encounters 'h' or 'H'. It ignores all other characters silently.

So it prints out "Hello World" when it encounters that `H` and ignores everything else.

---

# Quine in H

The only needed characters in H are "h", "w", and "q". All incorrect programs become quines.

---

# 99 bottles of beer in 99

All valid programs in 99 print the lyrics to the song we all love. For a program to be valid, it just needs to start each line with a `#`

---

# \+ in brainf\***

All the characters before `,+.` are ignored, and those last three read a number, increment it, and print, respectively.

---

I'm not sure if this is valid, but if it isn't, just let me know and I'll remove it.
> 4 votes

# Answer
# brainf\***, Java, Groovy, Whitespace, 1461 bytes

A tad long, but I'm sure it can be golfed further

```
class   Q{//++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.>[
public static void main(String[]a){

Character   c=10;char   Q=34;char   w=32;char   t=9;String  x="classzz$Q{//++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.>[#publiczstaticzvoidzmain(String[]a){#%#Character%c=10;char%Q=34;char%w=32;char%t=9;String%x=WXW;if(x.contains(WW+Q)){StringzC=WW+c;for(Integerzi=100;--i>0;)z%#%System.out.println(String.join(WW+w,WW+i,i<2?WbottleW:WbottlesW,WofW,WbeerW,WonW,WtheW,WwallW,C.concat(WW+i),i==1?WbottleW:WbottlesW,WofW,WbeerW,C.concat(WTakeW),WoneW,Wdown,W,WpasszitzaroundW,C.concat(i==1?WNozmoreW:WW+(i-1)),i==2?WbottleW:WbottlesW,WofW,WbeerW,WonW,WtheW,WwallW,C));%}#z%else###System.out.println(x.replace((char)122,w).replace((char)35,c).replace((char)87,Q).replace((char)37,t).replace((char)36,w).replace(c.toString(88),x));}}//]";if(x.contains(""+Q)){String C=""+c;for(Integer i=100;--i>0;)
    System.out.println(String.join(""+w,""+i,i<2?"bottle":"bottles","of","beer","on","the","wall",C.concat(""+i),i==1?"bottle":"bottles","of","beer",C.concat("Take"),"one","down,","pass it around",C.concat(i==1?"No more":""+(i-1)),i==2?"bottle":"bottles","of","beer","on","the","wall",C));   }
    else

System.out.println(x.replace((char)122,w).replace((char)35,c).replace((char)87,Q).replace((char)37,t).replace((char)36,w).replace(c.toString(88),x));}}//]

```

---

## brainf\*** code (ignoring other characters):

```
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

>[[]++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.>[[].++-->...+,+,<,,,,,,.+,,,,.,,,,,.+-,,,,,,,...,.,.,.,.,..,].++-->...+,+,<,,,,,,.+,,,,.,,,,,.+-,,,,,,,...,.,.,.,.,..,]

```

Try it in brainf\*** online!

**Edit**: Originally, this didn't work because while testing, I used the wrong version of my code. It's fixed now, but even longer than it was before.

The first line prints "Hello world!", and the second line basically just makes sure the rest of the code never runs by moving to a cell that's 0 and wrapping everything inside square brackets.

---

## Whitespace code (ignoring other characters):

```
[S] [S] [S] [LF]
[S] [S] [S] [LF]
[T] [LF]
[T] [T] [T] [T] [T] [S] [S] [S] [T] [LF]
[T] [S] [S] [S] [T] [LF]
[S] [T] [LF]
[LF]
[LF]

```

Explanation:

```
[S][S][S][L]     ----   push 0
[S][S][S][L]     ----   push 0
[T][L][T][T]     ----   read a number and put it at address 0 in the heap (0 because the top of the stack is 0)
[T][T][T]        ----   retrieve the number at address 0 in the heap
[S][S][S][T][L]  ----   push 1
[T][S][S][S]     ----   add
[T][L][S][T]     ----   print the number at the top of the stack
[L][L][L]        ----   exit the program

```

Try it in Whitespace online!

---

Try it in Java online!

---

Try it in Groovy online!
> 2 votes

# Answer
# Python 2, Python 3, HQ9+, Python 2 `-O`, 84 bytes

```
s="print(8/9and's=%r;exec(s)'%s or __debug__*'\\x48ello World!'or-~input())";exec(s)

```

Try H online!
Try Q online!
Try + online!
> 1 votes

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


title: Never trust a mastermind

text:
# Question
Title: Never trust a mastermind
You probably know the game mastermind:

The player tries to guess a code of 4 slots, with 8 possible colors - no duplicates this time. Let's call those colors A through H, so possible solutions could be ABCD or BCHD.

Each time you place a guess, the game master will respond with two information: how many slots you got right, and how many colors you got right but in the wrong place.

Some examples:

```
If the code is ABCD
and your guess is ACHB
the response 12: the color A is correctly placed, the two colors B&C are in the wrong place.

Code is ABCD
you guess EFGH
response is 00

Code is ABCD
you guess ABCD
response is 40

A full representation would be:
ABCD04,DCBA40
or
ABCD00,EFGH22,EFHG13,HFGE40

A partial game does not contain the final solution,
nor necessarily enough data to define a unique solution.
ABCD00,EFGH22,EFHG13

An example for an invalid partial game would be:
ABCD03,EFGH02: This would require that 5 colors are present

```

In essence, all games that cannot have a solution are invalid. The gamemaster made a mistake.

**Your task**

Never trust a game master. Your task is to write a program that takes a partial or full game description and validates whether such a game state is possible.

* Expect that no game description is longer than 8 attempts.
* Expect that the gamemaster can make a mistake on the very first turn, e.g. ABCD41
* The player can make an "invalid" guess to gain further information, e.g. AAAA to check if there is an A at all. Such a game is still valid, you only evaluate the gamemaster's responses. In such a case, exact hit takes precedence over near-misses, for code ABCD it's AAAA10, not AAAA14.
* You can format the input and output in whatever way you see fit, including replacing the colors by digits etc.
* Any pre-generated hashtable counts towards the total number of bytes.
* You know the loophole thing.

**The shortest code wins.**

Additional test cases:

```
 - ABCD11,ACEG02,HGFE11,CCCC10,CDGH01 => valid
 - ABCD01,EFGH03,CGGH11,HGFE21 => valid
 - ABCD22,EFGH01,ACDE11 => invalid
 - ABCD02,EFGH01,AABB21,AEDH30 => invalid
 - ABCD03,DCBA02 => invalid
 - ABCD32 => invalid

```

You can generate any number of valid cases by playing the game. Invalid solutions are hard to come up with. If you find invalid combinations that first slipped through your code, please comment it below for your fellow golfers.

**Bonus:** Bonus points if you come up with a solution that uses a significantly different approach than generating and traversing all possible permutations.

# Answer
> 16 votes
# JavaScript (ES6),  ~~116 112~~  107 bytes

Expects an array of entries in the following format: `[[a,b,c,d], "XY"]`, where `a` to `d` are integers in `[0..7]`, `X` is the number of correct digits and `Y` is the number of near-misses.

Returns **0** or **1**.

```
f=(a,n)=>n>>12?0:!a.some(([a,x])=>!a.every(o=(d,i)=>o[x-=d^(v=n>>i*3&7)?a.includes(v):10,v]^=1)|x)|f(a,-~n)

```

Try it online!

### Commented

```
f = (                     // f is a recursive function taking:
  a,                      //   a[] = input
  n                       //   n = 12-bit counter, initially undefined, to
) =>                      //       describe all possible codes
n >> 12 ?                 // if n = 4096:
  0                       //   stop the recursion
:                         // else:
  !a.some(([a, x]) =>     //   for each entry [a, x, y] in a[], with a[] =
                          //   guess, x = correct digits and near-misses:
    !a.every(o =          //     we use the object o to keep track of the
                          //     digits that were already extracted from n,
                          //     in order to discard invalid codes
      (d, i) =>           //     for each value d at position i in a[]:
      o[                  //
        x -=              //       update x:
          d ^ (           //         compare d with ...
            v =           //         ... v which is defined as ...
              n >> i * 3  //         ... the next 3-bit digit extracted from n
              & 7         //
          ) ?             //         if d is not equal to v, decrement x if ...
            a.includes(v) //           ... v appears elsewhere in a[]
          :               //         else:
            10,           //           subtract 10 from x
        v                 //       actual index in o to ...
      ] ^= 1              //       ... mark this digit as used; or yield 0
                          //       and exit every() if it was already used
    )                     //     end of every(); the iteration fails if it's
    | x                   //     falsy or x is not equal to 0
  )                       //   end of some()
  | f(a, -~n)             //   do a recursive call with n + 1

```

# Answer
> 7 votes
# Charcoal, 47 bytes

```
⊙ＥＸ⁸¦⁴Ｅ⁴§α﹪÷ιＸ⁸λ⁸∧⬤ι⁼№ιλ¹⬤θ⁼Ｉ…⮌λ²ΣＥι∨⁼ν§λξ∧№λνχ

```

Try it online! Link is to verbose version of code. Brute-force, but only takes a second or so on TIO. Outputs a Charcoal boolean, i.e. `-` for truthy, nothing for falsy. Explanation:

```
⊙ＥＸ⁸¦⁴Ｅ⁴§α﹪÷ιＸ⁸λ⁸

```

Generate all possible codes including duplicates, and see if any of them satisfies the following.

```
∧⬤ι⁼№ιλ¹

```

Check that the code contains no duplicates, and...

```
⬤θ

```

... check whether all of the guesses satisfy the following.

```
⁼Ｉ…⮌λ²

```

Get the result of the guess and check that it equals the following.

```
ΣＥι

```

Map over each character of the code.

```
∨⁼ν§λξ

```

Check whether it's an exact match.

```
∧№λνχ

```

Check whether it's misplaced.

~~60~~ ~~46~~ 44-byte version for a version that allows duplicates in the code:

```
⊙ＥＸ⁸¦⁴Ｅ⁴§α﹪÷ιＸ⁸λ⁸⬤θ⁼Σλ⁺×⁹ΣＥι⁼ν§λξΣＥα⌊⟦№ιν№λν

```

Try it online! Link is to verbose version of code. Brute-force, so takes a few seconds on TIO for falsy cases. Outputs a Charcoal boolean, i.e. `-` for truthy, nothing for falsy. Explanation:

```
⊙ＥＸ⁸¦⁴Ｅ⁴§α﹪÷ιＸ⁸λ⁸

```

Generate all possible codes including duplicates, and see if any of them satisfies the following.

```
⬤θ

```

Check whether all of the guesses satisfy the following.

```
⁼Σλ⁺

```

Extract the result of the guess (when passed a string which contains non-digits, `Sum` looks for embedded integer(s) and takes their sum rather than their digital sum) and check that it equals the sum of the following:

```
×⁹ΣＥι⁼ν§λξ

```

Count 9 for each exact match.

```
ΣＥα⌊⟦№ιν№λν

```

Count each match (whether exact or misplaced).

Edit: I had inadvertently calculated 4⁸ instead of 8⁴, so the code was taking 16 times longer than it needed to.

# Answer
> 3 votes
## Python3, ~~304~~ 140 bytes

```
lambda l:any(all(sum((x in t)+9*(x==y)for x,y in zip(p,t))==int(t[4:])for t in l)for p in permutations('ABCDEFGH',4))
from itertools import*

```

Lambda expecting input in the form of an array. Try it online!

Or 156 bytes as a full python program with textual input/output:

```
from itertools import*
l=input()
print(any(all(sum((x in t)+9*(x==y)for x,y in zip(p,t))==int(t[4:])for t in l.split())for p in permutations('ABCDEFGH',4)))

```

(try it online)

Could save 2 bytes by replacing `'ABCDEFGH'` with `range(8)`, but then input should be in the form `012311,024602,765411,222210,236701`.

**History of edits:** move `r=[0,1,2,3]` outside of function and remove `[]` to save 3 bytes; remove `()` around `return` value to save 2 bytes; replace `def f(p,t):` with `lambda p,t:` to save about 8 bytes; replace `[...].count(True)` with `sum(...)` to save 5+3=8 bytes; remove intermediary variable `m` to save 5 bytes; use `:=` in a much better way to get rid of the nested `lambda` and the awkward `(,,)[-1]` and save 26 bytes; @Arnauld fixed a mistake with the rules of mastermind and golfed it down to 221 bytes; @Arnauld did some magic with the booleans and ints to golf it to 185; replace `for i in range(4)` with `for x,y in zip(p,t)` to save 7 bytes; save 10 bytes by replacing `(lambda l:...)(input())` with `l=input() ...`; @Arnauld saves 8 bytes by replacing `t.count(x)and 1+9*(x==y)` with `(x in t)+9*(x==y)` (which is also easier to understand in my opinion) plus 3 bytes by requiring whitespace-separated input to replace `.split(',')` with `.split()`, @Arnauld saves 1 byte by replacing `import itertools as i` with `from itertools import*`; @Arnauld removed 16 bytes by making it a lambda instead of a full python program

**Less compact, more readable version**

```
import itertools as i

r=0,1,2,3
def f(p,t):
    correct = [p[i]==t[i] for i in r]
    misplaced = [t.count(p[i]) and not correct[i] for i in r]
    return sum(correct) * 10 + sum(misplaced) == int(t[4:])

def z(line):
    return any(all(f(p,t) for t in line.split(',')) for p in i.permutations('ABCDEFGH',4))

print(z(input()))

```
* `f(p,t)` is `True` if combination `p` passes test `t`. `p` is a size-4 array which might not contain duplicates (eg `ABCD`). `t` is a size-6 array which might contain duplicates (eg `CCCC10`).
* `z(line)` is `True` if there exists at least one legal combination `p` which passes all tests `t`; tests are described by the comma-separated string `line`.

# Answer
> 2 votes
# \+ gtools, ~~130~~ 125 bytes

```
function(l)any(apply(permutations(8,4),1,function(c)all(sapply(l,function(g)g[[2]]==c(x<-sum(c==el(g)),sum(c%in%el(g))-x)))))

```

Try it online!

Colours are represented by digits 1..8. Returns 'TRUE' for valid games and 'FALSE' for invalid gamemaster responses.

**Commented:**

```
mastermind_check=function(l)            # l=list of lists of [guess,response]
 any(                                   # do any of...
  apply(permutations(8,4),1,            # all possible codes...
   function(c)all(                      # produce all valid responses for...
    sapply(l,                           # every [guess,response] pair...
     function(g)                        # using this function to define valid response:
      all(g[[2]]==c(                    # - both of these must be the same:
        x<-sum(c==el(g)),               #   - response[1] == sum of correct cols in correct pos
        sum(c%in%el(g))-x               #   - response[2] == sum of correct cols in any pos
      )                                 #                    minus response[1]
)))))                                   # ...?

```

---

# , 114 bytes

```
function(l){while(T)T=!all(y<-sample(1:8,4),sapply(l,function(g)g[[2]]==c(x<-sum(y==el(g)),sum(y%in%el(g))-x)));1}

```

Try it online!

Stochastic function that checks random codes until it finds one that could satisfy the gamemaster responses, at which point it halts and returns `1`.
Halting is assured in finite time for all valid gamemaster responses.
If gamemaster response is invalid, function never halts.

---
Tags: code-golf, decision-problem, combinatorics
---


title: Implement Rijndael's S-box

text:
# Question
Title: Implement Rijndael's S-box
Rijndael's S-box is a frequently used operation in AES encryption and decryption. It is typically implemented as a 256-byte lookup table. That's fast, but means you need to enumerate a 256-byte lookup table in your code. I bet someone in this crowd could do it with less code, given the underlying mathematical structure.

Write a function in your favorite language that implements Rijndael's S-box. Shortest code wins.

# Answer
> 6 votes
### Ruby, 161 characters

```
R=0..255
S=R.map{|t|t=b=R.select{|y|x=t;z=0;8.times{z^=y*(x&1);x/=2;y*=2};r=283<<8;8.times{r/=2;z^r<z/2&&z^=r};z==1}[0]||0;4.times{|r|t^=b<<1+r^b>>4+r};t&255^99}

```

In order to check the output you can use the following code to print it in tabular form:

```
S.map{|x|"%02x"%x}.each_slice(16){|l|puts l*' '}

```

# Answer
> 10 votes
# x86-64 Machine code - ~~23 22 20~~ 19 bytes

Uses the AES-NI instruction set

```
66 0F 6E C1          movd        xmm0,ecx
66 0F 38 DD C1       aesenclast  xmm0,xmm1
0F 57 C1             xorps       xmm0,xmm1
66 0F 3A 14 C0 00    pextrb      eax,xmm0,0
C3                   ret

```

Using Windows calling conventions, takes in a byte and outputs a byte. It is not necessary to reverse the `ShiftRows` as it does not affect the first byte.

# Answer
> 9 votes
# GolfScript, 60 characters

```
{[[0 1{.283{1$2*.255>@*^}:r~^}255*].@?~)={257r}4*99]{^}*}:S;

```

This code defines a function named `S` that takes in a byte and applies the Rijndael S-box to it. (It also uses an internal helper function named `r` to save a few chars.)

This implementation uses a logarithm table to compute the GF(28) inverses, as suggested by Thomas Pornin. To save a few chars, the whole logarithm table is recalculated for each input byte; even so, and despite GolfScript being a very slow language in general, this code takes only about 10 ms to process a byte on my old laptop. Precalculating the logarithm table (as `L`) speeds it up to about 0.5 ms per byte, at the modest cost of three more chars:

```
[0 1{.283{1$2*.255>@*^}:r~^}255*]:L;{[L?~)L={257r}4*99]{^}*}:S;

```

For convenience, here's a simple test harness that calls the function `S`, as defined above, to compute and print out the whole S-box in hex like on Wikipedia:

```
"0123456789abcdef"1/:h; 256, {S .16/h= \16%h= " "++ }% 16/ n*

```

Try this code online.

(The online demo precalculates the logarithm table to avoid taking too much time. Even so, the online GolfScript site may sometimes randomly time out; this is a known issue with the site, and a reload usually fixes it.)

### Explanation:

Let's start with the logarithm table calculation, and specifically with the helper function `r`:

```
{1$2*.255>@*^}:r

```

This function takes two inputs on the stack: a byte and a reduction bitmask (a constant between 256 and 511). It duplicates the input byte, multiplies the copy by 2 and, if the result exceeds 255, XORs it with the bitmask to bring it back under 256.

Within the log-table generating code, the function `r` is called with the reduction bitmask 283 = 0x11b (which corresponds to the Rijndael GF(28) reduction polynomial *x*8 \+ *x*4 \+ *x*3 \+ *x* \+ 1), and result is XORed with the original byte, effectively multiplying it by 3 (= *x* \+ 1, as a polynomial) in the Rijndael finite field. This multiplication is repeated 255 times, starting from the byte 1, and the results (plus an initial zero byte) are collected into a 257-element array `L` that looks like this (middle part omitted):

```
[0 1 3 5 15 17 51 85 255 26 46 ... 180 199 82 246 1]

```

The reason why there are 257 elements is that, with the prepended 0 and with 1 occurring twice, we can find the modular inverse of any given byte simply by looking up its (zero-based) index in this array, negating it, and looking up the byte at the negated index in the same array. (In GolfScript, as in many other programming languages, negative array indexes count backwards from the end of the array.) Indeed, this is exactly what the code `L?~)L=` at the beginning of the function `S` does.

The rest of the code calls the helper function `r` four times with the reduction bitmask 257 = 28 \+ 1 to create four bit-rotated copies of the inverted input byte. These are all collected into an array, together with the constant 99 = 0x63, and XORed together to produce the final output.

# Answer
> 8 votes
The table can be generated without computing inverses in the finite field GF(256), by using logarithms. It would look like this (Java code, using `int` to avoid problems with the signed `byte` type):

```
int[] t = new int[256];
for (int i = 0, x = 1; i < 256; i ++) {
    t[i] = x;
    x ^= (x << 1) ^ ((x >>> 7) * 0x11B);
}
int[] S = new int[256];
S[0] = 0x63;
for (int i = 0; i < 255; i ++) {
    int x = t[255 - i];
    x |= x << 8;
    x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
    S[t[i]] = (x ^ 0x63) & 0xFF;
}

```

The idea is that 3 is a multiplicative generator of GF(256)\*. The table `t[]` is such that `t[x]` is equal to 3x; since 3255 = 1, we get that 1/(3x) = 3255-x.

# Answer
> 6 votes
## GolfScript (82 chars)

```
{256:B,{0\2${@1$3$1&*^@2/@2*.B/283*^}8*;;1=},\+0=B)*:A.2*^4A*^8A*^128/A^99^B(&}:S;

```

Uses global variables `A` and `B`, and creates the function as global variable `S`.

The Galois inversion is brute-force; I experimented with having a separate `mul` function which could be reused for the post-inversion affine transform, but it turned out to be more expensive because of the different overflow behaviour.

This is too slow for an online demo - it would time out even on the first two rows of the table.

# Answer
> 5 votes
## Python, 176 chars

This answer is for Paŭlo Ebermann's comment-question about making the function constant time. This code fits the bill.

```
def S(x):
 i=0
 for y in range(256):
  p,a,b=0,x,y
  for j in range(8):p^=b%2*a;a*=2;a^=a/256*283;b/=2
  m=(p^1)-1>>8;i=y&m|i&~m
 i|=i*256;return(i^i/16^i/32^i/64^i/128^99)&255

```

# Answer
> 4 votes
# APL (Dyalog Unicode), 70 bytes

```
⎕⊃99,1↓(2⊥¨(⊂b⊤99)≠≠⌿(⍳5)∘.⌽⌽p)[⍋2⊥¨p←{(2≠/⍵,0)≠b⊤27×⊃⍵}\,b⍴⊂1⊤⍨b←8⍴2]

```

Try it online!

# Answer
> 2 votes
## d

```
ubyte[256] getLookup(){

    ubyte[256] t=void;
    foreach(i;0..256){
        t[i] = x;
        x ^= (x << 1) ^ ((x >>> 7) * 0x1B);
    }
    ubyte[256] S=void;
    S[0] = 0x63;
    foreach(i;0..255){
        int x = t[255 - i];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        S[t[i]] = cast(ubyte)(x & 0xFF) ^ 0x63 ;
    }
    return S;

}

```

this can generate the lookup table at compile time, I could save some by making ubyte a generic param

edit direct `ubyte` to `ubyte` without array lookups, no branching and fully unrollable loops

```
B[256] S(B:ubyte)(B i){
    B mulInv(B x){
        B r;
        foreach(i;0..256){
            B p=0,h,a=i,b=x;
            foreach(c;0..8){
                p^=(b&1)*a;
                h=a>>>7;
                a<<=1;
                a^=h*0x1b;//h is 0 or 1
                b>>=1;
            }
            if(p==1)r=i;//happens 1 or less times over 256 iterations
        }
        return r;
    }
    B s= x=mulInv(i);
    foreach(j,0..4){
        x^=(s=s<<1|(s>>>7));
    }
    return x^99;
}

```

edit2 used @Thomas' algo for creating the lookup table

# Answer
> 2 votes
# Stax, 53 bytes

```
ë■ÿÆ♂◄º5hUø√!«mr¿¡ƒR3Å←ç≥#/$taJkαn∩╓▒ÿ╔τy╫π§╪S♫╔┴H╔║Ö

```

Run and debug it

I have no particular understanding of S-boxes. This is a conversion of Thomas Pornin's (8 year old!) solution.

---
Tags: code-golf, math, cryptography
---