title: Toroidally magnify-blur a matrix

text:
# Question
Title: Toroidally magnify-blur a matrix
## Task

Given a matrix of numbers \\$M\\$ with \\$r\\$ rows and \\$c\\$ columns, and the magnification factor \\$n\\$, build the matrix with \\$rn\\$ rows and \\$cn\\$ columns where the original elements are spaced \\$n\\$ units apart and the gaps are filled by piecewise linear interpolation:

$$ \begin{bmatrix} a\_{11} & a\_{12} & \cdots \\ a\_{21} & a\_{22} & \cdots \\ \vdots & \vdots & \ddots \\ \end{bmatrix} \Rightarrow \begin{bmatrix} a\_{11} & \frac{(n-1)a\_{11} + a\_{12}}{n} & \cdots & a\_{12} & \cdots \\ \frac{(n-1)a\_{11} + a\_{21}}{n} & \frac{(n-1) \frac{(n-1)a\_{11} + a\_{21}}{n} + \frac{(n-1)a\_{12} + a\_{22}}{n}}{n} & \cdots & \frac{(n-1)a\_{12} + a\_{22}}{n} & \cdots \\ \vdots & \vdots & \ddots & \vdots \\ a\_{21} & \frac{(n-1)a\_{21} + a\_{22}}{n} & \cdots & a\_{22} & \cdots \\ \vdots & \vdots & & \vdots & \ddots \\ \end{bmatrix} $$

Because the operation is toroidal, the "gaps" between the \\$r\\$-th row and the 1st row (resp. the \\$c\\$-th column and the 1st column) must also be filled, which is placed below the original elements of the \\$r\\$-th row (resp. on the right side of the \\$c\\$-th column).

You can take \\$M\\$ and \\$n\\$ (and optionally \\$r\\$ and \\$c\\$) as input and output the resulting matrix in any suitable format. \\$n\\$ is guaranteed to be a positive integer. The input matrix and the result may have non-integers.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
# one-element matrix
M = [[1]], n = 3
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]

# one-element matrix, large n
M = [[1]], n = 100
(100-by-100 matrix of ones)

# one-row matrix
M = [[0, 6, 3, 6]], n = 3
[[0, 2, 4, 6, 5, 4, 3, 4, 5, 6, 4, 2],
 [0, 2, 4, 6, 5, 4, 3, 4, 5, 6, 4, 2],
 [0, 2, 4, 6, 5, 4, 3, 4, 5, 6, 4, 2]]

# one-column matrix
M = [[0], [6], [3], [6]], n = 3
(transpose of the above)

# n = 1
M = [[1, 9, 8, 3],
     [5, 4, 2, 7],
     [3, 8, 5, 1]], n = 1
(same as M)

# 2-by-2 matrix; here the result is rounded to 2 decimal places for convenience.
# An answer doesn't need to round them, though one may choose to do so.
M = [[0, 9],
     [3, 6]], n = 3
[[0, 3,    6,    9, 6,    3],
 [1, 3.33, 5.67, 8, 5.67, 3.33],
 [2, 3.67, 5.33, 7, 5.33, 3.67],
 [3, 4,    5,    6, 5,    4],
 [2, 3.67, 5.33, 7, 5.33, 3.67],
 [1, 3.33, 5.67, 8, 5.67, 3.33]]

# a larger test case
M = [[0, 25, 0],
     [25, 0, 0],
     [0, 0, 25]], n = 5
[[0, 5, 10, 15, 20, 25, 20, 15, 10, 5, 0, 0, 0, 0, 0],
 [5, 8, 11, 14, 17, 20, 16, 12, 8, 4, 0, 1, 2, 3, 4],
 [10, 11, 12, 13, 14, 15, 12, 9, 6, 3, 0, 2, 4, 6, 8],
 [15, 14, 13, 12, 11, 10, 8, 6, 4, 2, 0, 3, 6, 9, 12],
 [20, 17, 14, 11, 8, 5, 4, 3, 2, 1, 0, 4, 8, 12, 16],
 [25, 20, 15, 10, 5, 0, 0, 0, 0, 0, 0, 5, 10, 15, 20],
 [20, 16, 12, 8, 4, 0, 1, 2, 3, 4, 5, 8, 11, 14, 17],
 [15, 12, 9, 6, 3, 0, 2, 4, 6, 8, 10, 11, 12, 13, 14],
 [10, 8, 6, 4, 2, 0, 3, 6, 9, 12, 15, 14, 13, 12, 11],
 [5, 4, 3, 2, 1, 0, 4, 8, 12, 16, 20, 17, 14, 11, 8],
 [0, 0, 0, 0, 0, 0, 5, 10, 15, 20, 25, 20, 15, 10, 5],
 [0, 1, 2, 3, 4, 5, 8, 11, 14, 17, 20, 16, 12, 8, 4],
 [0, 2, 4, 6, 8, 10, 11, 12, 13, 14, 15, 12, 9, 6, 3],
 [0, 3, 6, 9, 12, 15, 14, 13, 12, 11, 10, 8, 6, 4, 2],
 [0, 4, 8, 12, 16, 20, 17, 14, 11, 8, 5, 4, 3, 2, 1]]

```

# Answer
# APL (Dyalog Extended), ~~27~~ 26 bytes

-1 thanks to Bubbler.

Anonymous infix lambda. Takes \\$n\\$ as left argument and \\$M\\$ as right argument.

```
{⊃+⌿,(⍳⍺)⍉⍤⌽\⍣2⊂⍺/⍺⌿⍵÷⍺*2}

```

Try it online! (the \\$n=100\\$ case run out of memory on TIO gives by default, but works offline)

`{``}` "dfn";  is \\$n\\$ and  is \\$M\\$

`⍺*2`\\$n^2\\$

`⍵÷`\\$M\over n^2\\$

`⍺⌿` replicate vertically so each row becomes \\$n\\$ copies

`⍺/` replicate horizontally so each column becomes \\$n\\$ copies

enclose to work on entire matrix

`(⍳⍺)``⍣2` do the following twice, each time with the \\$0,1…n-1\\$ as left argument:

`\` outer "product" using the following tacit function instead of multiplication:

cyclically rotate the rows by the indices

then:

transpose

`,` flatten

`+⌿` sum

disclose (since the summation reduced rank from 1 to 0 by enclosing)
> 6 votes

# Answer
# , 22 bytes

```
(1#.&|:<@[1&|.[#%~)^:2

```

Try it online!

The "blur" is separable so operate in two passes where each pass operates on the rows and transposes its results.
> 4 votes

# Answer
# , ~~97~~ ~~92~~ ~~91~~ 86 bytes

```
function(m,n,`[`=apply)m[1,h][1,h<-function(i)approxfun(c(i,i))(0:(n*sum(1|i)-1)/n+1)]

```

Try it online!

Thanks to Giuseppe for -5 bytes.
> 2 votes

# Answer
## *Mathematica*, 63?

I can't remember the rules regarding non-ASCII characters but it looks like they are in play.

```
ListCorrelate[##/n^2&[n-Abs[n-Range[2n-1]]],Upsample[m,n,n],1]

```

 is short notation for `TensorProduct`.
> 2 votes

# Answer
# Charcoal, 36 bytes

```
ＩＥ×ηＬθＥ×ηＬ§θ⁰∕ΣＥη∕ΣＥη§§θ÷⁺ινη÷⁺λπηηη

```

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

Cast the final array to string for implicit print (each row's cells print vertically and rows are double-spaced).

```
Ｅ×ηＬθ

```

Loop over each row of the final array.

```
Ｅ×ηＬ§θ⁰

```

Loop over each column of the final array.

```
∕ΣＥη∕ΣＥη§§θ÷⁺ινη÷⁺λπηηη

```

Extract an `n`-by-`n` square from a virtual array created by a simple inflation of the original array, where the top left of the square is at the final row and column. Cyclic indexing ensures that the square wraps around toroidally. The average of the elements is then taken.
> 1 votes

# Answer
# Python 2, 109 bytes

```
M,n=input()
exec"M=[[i%n*((r*2)[i/n+1]-r[i/n])/n+r[i/n]for i in range(len(r)*n)]for r in zip(*M)];"*2
print M

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES10), 170 bytes

Takes input as `(m)(n)`.

```
m=>n=>(T=m=>m.map((r,y)=>r.map((v,x)=>(M[x]=M[x]||[])[y]=v),M=[])&&M)((g=m=>m.map((r,y)=>r.flatMap((v,x)=>[...Array(n)].map((_,i)=>v+(r[-~x%r.length]-v)*i/n))))(T(g(m))))

```

Try it online! (with formatted outputs for readability)
> 0 votes

---
Tags: code-golf, array, matrix, image-processing
---


title: Print a Sorry Board

text:
# Question
Title: Print a Sorry Board
I was just playing the board game *Sorry!* with some people, and I realized that I could base a few interesting challenges off of it. This one is pretty simple.

You task is simply to output an version of a sorry board, placing pieces where I tell you to.

# Specs

First, here is an image of an actual *Sorry!* board for reference:

The empty board looks like:

```
# > - - o # # # # > - - - o # #
#   #   S                     v
o   #             H # # # # # |
|   #                         |
|   #                       S o
|   #                         #
^   H                         #
#                             #
#                             #
#                         H   v
#                         #   |
o S                       #   |
|                         #   |
| # # # # # H             #   o
^                     S   #   #
# # o - - - < # # # # o - - < #

```

Notice a few features.

* The `#`'s are empty squares.
* The `S`'s and `H`'s are Start's and Home's respectively.
* The `>v<^`'s are the start of the slides, depending on which direction they face.
* The `|`'s and `-`'s are the middles of slides, depending on if they're horizontal or vertical.
* The `o`'s are the end's of slides.
* Each column is separated by a column of spaces to make it look more square-like.

Now here is what *you* have to do:

* Your input is a list of coordinates of various pieces that have been placed on the board.
* The coordinates start at `0` at the square outside the Start of the bottom color (yellow in the picture), and increase by one per square clockwise.
* After these 60 squares, the safe zones have the next and last 20 coordinates, starting from the one on the bottom (which gets 60-64), then going clockwise.
* You will have to place star's(`*`'s) on the correct coordinate, replacing the character underneath for all players.
* Additionally, if any of the players are on the start square of a slider, move them to the end of the slider before placing them.
* You can assume that there will be no collisions, before or after resolving sliders.
* You con't need to worry about the Home's or Start's.
* You can be 1-indexed if you want, but the test cases are 0-indexed.

# Test Cases

```
[0, 20] ->

# > - - o # # # # > - - - o # #
#   #   S                     v
*   #             H # # # # # |
|   #                         |
|   #                       S o
|   #                         #
^   H                         #
#                             #
#                             #
#                         H   v
#                         #   |
o S                       #   |
|                         #   |
| # # # # # H             #   o
^                     S   #   #
# # o - - - < # # # # * - - < #

[2, 7, 66] ->

# > - - o # # # # > - - - o # #
#   #   S                     v
o   #             H # # # # # |
|   #                         |
|   #                       S o
|   #                         #
^   H                         #
#                             #
#                             #
#                         H   v
#                         #   |
o S                       #   |
|                         #   |
| # * # # # H             #   o
^                     S   #   #
# # o - * - < # # * # o - - < #

```

# Answer
# APL (Dyalog Unicode), 204 bytes

```
(~2|⍳31)\'H'@(g⊂2 9)⊢'S'@(g⊂4 14)⊢('*'@({(60>⍵)⊃⍵,60|⍵+4 3+.×5 12=15|⍵}¨⎕)⊢'o####<---o##^||o####^|||o##>--o####>---o##v||o####v|||o##<--',20⍴'#')@((4⌽g 15,⍨¨⍳15),(g←(15∘-,⊢)(|15 0-⌽)¨,⊢)2,¨14-⍳5)⊢16 16⍴''

```

Try it online!

It is very likely possible to compress the hardcoded length-60 string, but I'm too lazy :P

A full program that takes a vector of numbers from stdin and prints the board to stdout. Uses lots of `@` to place various things at various places, starting from an empty board. This is an interesting use case for an otherwise seldom used built-in `@`.

### Ungolfed with comments

```
⍝ Hardcoded string of the 80 positions that can be occupied by players
s←'o####<---o##^||o####^|||o##>--o####>---o##v||o####v|||o##<--',20⍴'#'

⍝ Place '*' for actual players' positions
s←'*'@({(60>⍵)⊃⍵,60|⍵+4 3+.×5 12=15|⍵}¨⎕)⊢s
      ({                             }¨⎕)  ⍝ Take input and slide the positions
                    ⍵+4.3+.×5 12=15|⍵      ⍝ If n%15=5, add 4; if n%15=12, add 3
                 60|                       ⍝ Wrap 60 to 0
        (60>⍵)⊃⍵,                          ⍝ Discard change if n is 60 or higher
  '*'@ ... ⊢s  ⍝ Overwrite '*' at players' positions on s

⍝ Helper function to generate positions on 2D board
g←(15∘-,⊢)(|15 0-⌽)¨,⊢  ⍝ Take a vector of coordinates on the right side
                    ,⊢  ⍝ Prepend to self...
          (|15 0-⌽)¨    ⍝   abs((15-y,x)); 90 degrees counterclockwise
  (15∘-,⊢)              ⍝ Take the above and prepend 180 degrees rotation

⍝ Main result
(~2|⍳31)\'H'@(g⊂2 9)⊢'S'@(g⊂4 14)⊢s@((4⌽g 15,⍨¨⍳15),g 2,¨14-⍳5)⊢16 16⍴''
16 16⍴''  ⍝ Empty 16×16 board
s@((4⌽g 15,⍨¨⍳15),g 2,¨14-⍳5)  ⍝ Place the 80 chars around the board
   (4⌽g 15,⍨¨⍳15)              ⍝   First 60 positions on the boundaries
                 ,g 2,¨14-⍳5   ⍝   and the other 20 positions inside
'S'@(g⊂4 14)  ⍝ Place S's
'H'@(g⊂2 9)  ⍝ Place H's
(~2|⍳31)\  ⍝ Insert blank columns

```
> 4 votes

# Answer
## Python 2, 476 bytes

Short 3-line solution (Try it online)

```
s=map(list,''.join(b if b in'#^v<>-|oSH~'else' '*int(b,16)for b in "#>--o####>---o##~#1#1SAv~o1#6H#####|~|1#C|~|1#BSo~|1#C#~^1HC#~#E#~#E#~#CH1v~#C#1|~oSB#1|~|C#1|~|#####H6#1o~^AS1#1#~##o---<####o--<#").split('~'))
for i in input():x,y=(lambda n:([11-n,15]*12+[0,26-n]*14+[n-26,0]*16+[15,n-41]*14+[71-n,15]*4+[13,n-50]*5+[70-n,13]*5+[2,75-n]*5+[n-65,2]*5)[2*n:2*n+2])((lambda n:4if n in[5,20,35,50]else 3if n in[12,27,42,57]else 0)(i)+i);s[y][x]='*'
for r in s:print' '.join(r)

```

One-liner in 534 (Try it online):

```
for r in(lambda B,I:[[[i,j]in map(lambda n:([11-n,15]*12+[0,26-n]*14+[n-26,0]*16+[15,n-41]*14+[71-n,15]*4+[13,n-50]*5+[n-64,13]*5+[2,75-n]*5+[n-65,2]*5)[2*n:2*n+2],map(lambda n:n+4if n in[5,20,35,50]else n+3if n in[12,27,42,57]else n,I))and'*'or b for i,b in enumerate(a)]for j,a in enumerate(B)])(map(list,''.join(b if b in'#^v<>-|oSH~'else' '*int(b,16)for b in"#>--o####>---o##~#1#1SAv~o1#6H#####|~|1#C|~|1#BSo~|1#C#~^1HC#~#E#~#E#~#CH1v~#C#1|~oSB#1|~|C#1|~|#####H6#1o~^AS1#1#~##o---<####o--<#").split('~')),input()):print' '.join(r)

```

I assume indices of safe zone this way:

```
#  >  -  -  o  #  #  #  #  >  -  -  -  o  #  #
#     74    S                                v
o     73                   H 75 76 77 78 79  |
|     72                                     |
|     71                                  S  o
|     70                                     #
^     H                                      #
#                                            #
#                                            #
#                                      H     v
#                                      60    |
o  S                                   61    |
|                                      62    |
|  69 68 67 66 65 H                    63    o
^                                S     64    #
#  #  o  -  -  -  <  #  #  #  #  o  -  -  <  #

```

Explanation (lines are separated a bit for better understanding):

```
# Hardcode board. Spaces are changed to their number in hex (as there are up to 14 spaces in row)
# Unfortunatly v^<> characters made board non-symmetrical and replacing chars costs too much in python, so I had to hardcode it all
B="#>--o####>---o##~#1#1SAv~o1#6H#####|~|1#C|~|1#BSo~|1#C#~^1HC#~#E#~#E#~#CH1v~#C#1|~oSB#1|~|C#1|~|#####H6#1o~^AS1#1#~##o---<####o--<#"

# Encode board to list of lists of characters
s=map(list,''.join(b if b in'#^v<>-|oSH~'else' '*int(b,16)for b in B).split('~'))

# Map coordinates, based on n (awfully long)
# Creates long list (lenght of 80) with values based on n and only one valid, which occures under index n
l=lambda n:([11-n,15]*12+[0,26-n]*14+[n-26,0]*16+[15,n-41]*14+[71-n,15]*4+[13,n-50]*5+[70-n,13]*5+[2,75-n]*5+[n-65,2]*5)[2*n:2*n+2]

# Returns additional move of n if it appers to be on slide start
j=lambda n:4if n in[5,20,35,50]else 3if n in[12,27,42,57]else 0

# Here takes input as list of numbers, get coordinates for them and update board with *
for i in input():x,y=l(j(i)+i);s[y][x]='*'

# Print board, spacing characters with one whitespace
for r in s:print' '.join(r)

```
> 3 votes

# Answer
# 05AB1E, 169 bytes

```
11Ý₅+R14L17*R15Ý¤DL17*+¤3Lα4Ý©17*DƵ—αs19+®Ƶ_+s®48α)˜•1ŠΓ;Ü|má•Ƶªв•5–à†@1δ!•Ƶ§в‡Iè'*•3‡Ù¬¨èˆ‚1æ°þBÚ•" #
0o1HS"ÅвJ.BD€SøíJ‚øJ»∊2ä`¶¡í»«8Å120Å0«">>v^v^<<"„-|S5×Jº«S.;rǝS¶¡»

```

Try it online or verify all test cases.

**Explanation:**

We start by creating a list of all possible coordinates of the `*` on the finished board.
The list we want to create for the 0-based indices is:

```
[266,265,264,263,262,257,260,259,258,257,256,255,187,221,204,187,170,153,136,119,34,85,68,51,34,17,0,4,2,3,4,5,6,7,8,13,10,11,12,13,14,15,83,49,66,83,100,117,236,151,168,185,202,219,236,253,270,266,268,267,251,234,217,200,183,222,223,224,225,226,19,36,53,70,87,48,47,46,45,44]

```

The duplicated coordinates are for the positions that are on the start of a slider, which end up at the end of the slider.

Using a straight-forward compressed list would be 86 bytes:

```
•€l:å–£²voùäÉÿ¢º(ºT≠εÁ~нΣûÑ‚Ćδ·нäVø<:‘.IWÚC¯ht;t∍W₂zþ#6÷(›ǝé$)‚ιô.!=É/g=Ë₁Ìjh:½~₃Y•Ƶ«в

```

But instead, we create the list manually in 79 bytes:

```
11Ý           # Push a list in the range [0,11]
   ₅+         # Add 255 to each
     R        # And reverse it
14L           # Push a list in the range [1,14]
   17*        # Multiply each by 17
      R       # And reverse it
15Ý           # Push a list in the range [0,15]
¤             # Push its last value (15) (without popping the list itself)
 D            # Duplicate it
  L           # Create a list in the range [1,15]
   17*        # Multiply each by 17
      +       # And add the 15 to each
¤             # Push its last value (270) without popping the list itself)
 3L           # Push a list in the range [1,3]
   α          # Take the absolute difference of each value with 270
4Ý            # Push a list in the range [0,4]
  ©           # Store it in variable `®` (without popping)
   17*        # Multiply each by 17
      D       # Duplicate this list
       Ƶ—     # Push compressed integer 251
         α    # And take the absolute difference of each value with this 251
s             # Swap so the duplicated list of [0,4] * 17 is at the top again
 19+          # Add 19 to each
®             # Push the list in the range [0,4] again from variable `®`
 Ƶ_           # Push compressed integer 222
   +          # Add it to each
s             # Swap the two lists at the top of the stack
®             # Push the list in the range [0,4] once again from variable `®`
 48α          # Take the absolute difference of each value with 48
)             # Now wrap all lists on the stack into a list
 ˜            # And flatten it to a single list

# And finally adjust this list with the slider positions:
•1ŠΓ;Ü|má•    # Push compressed integer 108136777658162939
          Ƶª  # Push compressed integer 270
            в # Convert the larger integer to base-270 as list:
              #  [1,9,32,102,134,238,261,269]
•5–à†@1δ!•    # Push compressed integer 391758411553146080
          Ƶ§  # Push compressed integer 267
            в # Convert the larger integer to base-267 as list
              #  [4,13,83,34,236,187,257,266]
‡             # Transliterate; replace all values of the first list with the values of
              # the second list in the big list we created earlier

```

Now that we have this list of coordinates for the `*`, we use the input to get the positions:

```
I             # Push the input-list
 è            # Index it into the list we created
'*           '# Push a "*" (which we will use later on)

```

Now we are going to create the empty board (without the space columns for now). We do this as follows:

```
•3‡Ù¬¨èˆ‚1æ°þBÚ•
              # Push compressed integer 68098022849564198525854900638097
 " #\n0o1HS"  # Push this string
  Åв          # Convert the large integer to base-" #\n0o1HS", which means it's converted
              # to base-length, and then indexed into the string
    J         # And join the entire list of characters to a string

```

We now have a quarter of the board as template (without trailing spaces):

```
#100o###
# # S
o #
0 #
0 #
0 #
1 H
#

```

Which we'll use to create the entire board:

```
.B            # Box it. This will split on newlines, but also make all lines of equal
              # length by adding trailing spaces
  D           # Duplicate this list of lines
€S            # Convert each line to a list of characters
  ø           # Zip/transpose; swapping rows/columns
   í          # Reverse each row
              # (`øí` basically rotates a character-matrix once clockwise)
    J         # Join each inner list together to a string
‚             # Pair it with the list of strings we duplicated
 ø            # Zip/transpose; swapping rows/columns
  J           # Join the pair of lines together
   »          # And join the lines by newlines

```

We now have halve the board:

```
#100o####1000o##
# # S          1
o #      H#####0
0 #            0
0 #           So
0 #            #
1 H            #
#              #

```

And we'll continue:

```
∊             # Mirror vertically
 2ä           # Split it into two halves
   `          # Pop and push both halves separated to the stack
¶¡            # Split the top list on newlines again
  í           # Reverse each row
   »          # Join it by newlines
«             # And then merge it back to the first halve

# And now we'll fix the arrows and lines:
8Å1           # Push a list of 8 1s
   20Å0       # Push a list of 20 0s
       «      # Merge those two together
">>v^v^<<"    # Push this string
„-|           # Push string "-|"
   S          # Convert it to a pair of characters: ["-","|"]
    5×        # Repeat each 5 times: ["-----","|||||"]
      J       # Join it together to a string "-----|||||"
       º      # Mirror it horizontally: "-----||||||||||-----"
        «     # Append it to the arrows-string
          S   # Convert it to a list of characters
.;            # Replace each of the 1s/0s one-by-one with these characters in the board

```

So we end up with our completed empty board (without space columns):

```
#>--o####>---o##
# # S          v
o #      H#####|
| #            |
| #           So
| #            #
^ H            #
#              #
#              #
#            H v
#            # |
oS           # |
|            # |
|#####H      # o
^          S # #
##o---<####o--<#

```

Then we'll place the `"*"` we pushed earlier at the positions we calculated earlier:

```
r             # Reverse the values on the stack
 ǝ            # Insert the "*" at the position of the list in the board-string

```

And finally we fix the space-columns, and output the result:

```
S             # Convert the entire board to a list of characters
 ¶¡           # Split it on newlines
   »          # Join each inner list by spaces, and then each line by newlines
              # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand how the compression works.
I've used this 05AB1E tip to generate the quarter board.
> 0 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity, board-game
---


# Question
Title: Tic-Tac-Toe and Chess, with fewest [distinct] characters
In this form of the game Tic-Tac-Chec, the goal is to move chess pieces to get four-in-a-row. Your goal here is to figure out if a position has a winning move.

# Rules

The rules are similar, but not identical, to those of Tic-Tac-Chec.

The board is 4 by 4 squares. Each player has a rook, bishop, knight, and queen. On your turn, you have two options. You can move one of your pieces already on the board, following standard chess rules. Or you can place a piece not already on the board, on any unoccupied place.

If you move an existing piece onto an opponent's piece, their piece is taken off the board and returned to them. However, you may not place a new piece on top of an opponent's piece.

As soon as one player has all of their pieces in a row (or column, or diagonal), they win.

# Challenge

Write a full program that accepts a board from STDIN, and outputs whether the white player can win on the next turn.

## Input

Four strings of 4 characters each. Each character is either a space or a chess piece. Only rooks, bishops, knights, and queens are used, and at most one of each (per color) may appear. Neither player already has a four-in-a-row.

You can choose whether to accept as input the Unicode symbols for the chess pieces, or letters. If you choose letters, `RBKQ` represents white pieces, and `rbkq` represents black pieces.

## Output

If the white player can win on the next turn, output `true` or `1`. Otherwise, output `false` or `0`.

## Program

Choose a number X. Your program may contain at most X distinct characters, and no character may appear more than X times.

## Winning

Lowest X wins. In case of a tie, fewest characters wins.

# Examples

These examples assume the input uses letters to represent the pieces.

```
rkb

RB Q
true - the white player can place the knight to complete the bottom row.
-----------------------------------
rk

RBbQ
false - the black bishop prevents the white knight from completing the row.
-----------------------------------
rk
 K

RBbQ
true - the white knight can capture the black bishop and complete the row.
-----------------------------------
rkRB

 Qb
K
true - the white rook can move down one to complete the diagonal.

```

# Answer
# APL (Dyalog Unicode), 369 characters, score 28

```
{Q←(QQ←⍴⍵)[1]
R←∨/¨⍵=⊂'RBQK'
B←({⍵(⍵[↑(⍳Q),¨¨⊂1--Q-⍳Q])}↑(⍳Q)=⊂⍳Q),{⍵,{⍵[{⍵[(1--1)1]}¨⍳QQ]}¨⍵}(⊂QQ)⍴¨(⍳Q)=⊂⍳Q
K←(Q-1)={∨/1↑⍴{(,⍵)/,⍳⍴⍵}⍵}¨B×⊂R
1-∨/K:1-1
K←↑∨/K/B
BB←{(,⍵)/,⍳⍴⍵}K×1-R
R←↑∨/BB-B←{(,⍵)/,⍳⍴⍵}R×1-K
1-⍴B:⍵[BB]=1↑''
BB←(1-∨/¨'RBQK'=⊂⍵[(,K)/,⍳⍴K])/'RBQK'
'K'=BB:×/∨/¨(⍳1--1)=⊂R∨-R
1-∨/(1-(⍳1--1)='RB'⍳BB)×(=/,{∨/1-×⍵})R∨-R:1-1
×/(1↑'')=⍵[B--(×⊂R)×⍳-1-∨/R]}↑⍞⍞⍞⍞

```

Try it online!

Character statistics:

```
 -  1  B  )  (  ⍵  /  Q  ⍳  R  '  ∨  LF   K  ,  =  ←  }  { ⊂ × ¨ ⍴ ↑ ] [ ⍞ :
27 26 22 20 20 19 19 18 15 15 14 12  12  12 12 11 10 10 10 9 9 9 8 8 7 7 4 4
chars 28

```

Decisions made during optimizing the score:

* Boolean guard `:` is needed for early returns from a dfn `{}`. Either LF (`\n`) or a statement separator character  cannot be removed as a side effect.
* I didn't try to avoid four letters `RBQK` as avoiding it requires *at least* `⎕A` and the code would get messy.
* Removed composition , reflex/flip , and self  in favor of dfns and explicitly writing down arguments with parentheses.
* Removed  (tally) in favor of  (shape/reshape), as tally = first element of shape, and reshape is unavoidable.
* Removed  (transpose) and  (reverse/rotate) in favor of explicit indexing `[]` combined with index generator . Although there are one-char functions to do the indexing (, ), none is suitable for transpose operation.
* Removed  (first/pick) in favor of  (mix/take), as take is unavoidable and indexing+mix can simulate both uses of .
* Removed  (logical and) in favor of `×` (times), and `|` (abs/mod) by using the workaround `x∨-x` for `|x` (abs) and explicit membership  (which was removed later) for `x|y` (mod).  was also removed that way.
* Removed `∘.f` in favor of `f⊂` or `f¨⊂`. Similar trick was used to simulate  (membership) and `~` (set minus): `x∊y → ∨/¨x=⊂y`, `x~y → (1-∨/¨x=⊂y)/x`
* Removed  (extract indices of ones) with the workaround `(,x)/,⍳⍴x`.
* Removed zero with `1-1`, four by extracting from `⍴⍵`, and `+` with `--`.
* Removing blanks in plain code is easy, but this code has `' '`. I avoided it with `1↑''`, which "overtakes" length 1 from an empty string and gives a single blank. (It is a slightly different thing from the literal `' '`, but they are compatible in most cases.)

### Ungolfed with comments

```
{
  ⍝ 4×4 boolean matrix where 1 means a white piece
  whites←⍵∊'RBKQ'
  ⍝ one matrix per a winning position; roughly looks like
  ⍝ 1 0 0 0 ... 1 1 1 1 ... 1 0 0 0
  ⍝ 1 0 0 0     0 0 0 0     0 1 0 0
  ⍝ 1 0 0 0     0 0 0 0     0 0 1 0
  ⍝ 1 0 0 0     0 0 0 0     0 0 0 1
  masks←((⊂,⊂∘⌽)∘.=⍨⍳4),(⊢,⍉¨)(⍳4)⌽¨⊂4 4⍴4↑1
  ⍝ 1 if the white is about to win in that specific winning position
  filter←3=masks{≢⍸⍺∧⍵}¨⊂whites
  ⍝ No three-in-a-row: return false
  ~∨/filter:0

  ⍝ fetch the mask closest to white's winning
  mask←(⍸filter)⊃masks
  ⍝ coordinates of misplaced piece (from) and empty position (to)
  from←⍸whites>mask
  to←⍸whites<mask
  ⍝ No from: the remaining place must be empty
  ~≢from:' '=⍵[to]

  ⍝ get the type of the piece to move
  type←'RBKQ'~⍵[⍸mask]
  ⍝ Knight: true if 1×2 steps away, ignoring any obstacles
  'K'=type:∧/1 2∊|⊃from-to
  ⍝ two booleans indicating if it can move in diagonals (BQ) or
  ⍝ cardinal directions (RQ)
  diag cross←0 2⊤⊃'RB'⍳type
  ⍝ two booleans indicating if the direction to move is actually
  ⍝ diagonal or cardinal
  isdiag←=/|⊃from-to
  iscross←0∊|⊃from-to
  ⍝ Not aligned with the piece to move: return false
  diag cross⍱.∧isdiag iscross:0
  ⍝ If aligned, true if all cells between from and to are blanks
  ∧/' '=¯1↓⍵[from+(×v)×⍳⌈/⊃|v←to-from]
}↑{⍞}¨⍳4  ⍝ Take 4 lines of input, format as matrix and pass to function

```
> 5 votes

# Answer
# C, 53 distinct chars

This uses `"#%&()*+,-./01234569;<=>BKQR[\]acdefghilmnoprstu{|}`, space and newline, distributed as follows: 24×`\n`, 33×, 20×`"`, 2×`#`, 3×`%`, 16×`&`, 46×`(`, 46×`)`, 13×`*`, 12×`+`, 35×`,`, 10×`-`, 2×`.`, 2×`/`, 18×`0`, 9×`1`, 4×`2`, 4×`3`, 4×`4`, 4×`5`, 3×`6`, 3×`9`, 34×`;`, 6×`<`, 46×`=`, 2×`>`, 2×`B`, 2×`K`, 3×`Q`, 2×`R`, 8×`[`, 1×`\`, 8×`]`, 39×`a`, 23×`c`, 5×`d`, 19×`e`, 15×`f`, 1×`g`, 22×`h`, 36×`i`, 5×`l`, 1×`m`, 35×`n`, 9×`o`, 33×`p`, 44×`r`, 20×`s`, 43×`t`, 15×`u`, 8×`{`, 14×`|`, 8×`}`.

```
#include <stdio.h>
#include <string.h>
int n(char*a,char*e,int i)
{int c=0;for(;a<e;)c+=*a++=="\n"[0];return c==i;}

int p(char *t, int r, int u)
{char h[]=" RBQK";char*p=t+r;char*a;int c=0;
for(int i=0;i<=3;++i,p+=u){char*s=strchr(h,*p);if(s&&s==h==0){++c;*s=" "[0];}else{a=p;}}
if(c-3)return 0;
char o=h[strspn(h, " ")];
p=strchr(t, o);
if(p==0)return*a==" "[0];
if(p<a){char*s=p;p=a;a=s;}
if(o=="K"[0])return(p-a)==3&&n(a,p,1)||(p-a)==2+5&&n(a,p,1)||(p-a)==9&&n(a,p,2)||(p-a)==11&&n(a,p,2);
if((p-a)%5==0||n(a,p,0))return (int)strchr("RQ", o);
return((p-a)%4==0&&n(a,p,(p-a)/4)||(p-a)%6==0&&n(a,p,(p-a)/6))&&strchr("BQ",o);}

int f(char *t)
{for(int i=0;i<4;++i)if(p(t,i,5)||p(t,i*5,1))return 1;
return p(t,0,6)||p(t,3,4);}

int main()
{char t[20];fread(t,19,1,stdin);t[19]=0;
if(f(t))puts("true");else puts("false");}

```

## Explanation

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

/* count newlines */
int n(char *a, char *e)
{
    int c = 0;
    for (;a<e;) c += *a++=='\n';
    return c;
}

/* check a single row, column or diagonal */
int p(char *t, int start, int stride)
{
    char h[] = " RBQK"; /* pieces not in line */
    char *p = t+start;
    char *a;
    int c = 0;
    for (int i = 0;  i <= 3;  ++i, p+=stride) {
        char *s = strchr(h, *p);
        if (s && s == h == 0) {
            /* a white piece */
            ++c;
            *s = " "[0];
        } else {
            /* candidate target square */
            a = p;
        }
    }

    /* did we find three white pieces in this line? */
    if (c != 3)
        return 0;

    char o = h[strspn(h, " ")];

    p = strchr(t, o);

    if (p==0)
        return *a == " "[0];

    /* ensure a < p */
    if (p < a) {
        char *s = p;
        p = a;
        a = s;
    }

    /* knight moves */
    if (o == 'K')
        return (p-a)==3 && n(a,p)==1
            || (p-a)==7 && n(a,p)==1
            || (p-a)==9 && n(a,p)==2
            || (p-a)==11 && n(a,p)==2;

    /* rook moves */
    if ((p-a)%5 == 0 || n(a,p)==0)
        return 0==strchr("RQ", o)==0;

    /* bishop moves */
    return
        ((p-a)%4==0 && n(a,p)==(p-a)/4 ||
         (p-a)%6==0 && n(a,p)==(p-a)/6)
        && strchr("BQ", o);
}

/* main predicate function */
int f(char *t)
{
    /* try rows and columns */
    for (int i = 0;  i < 4;  ++i)
        if (p(t, i, 5) || p(t, i*5, 1))
            return 1;
    /* try diagonals */
    return p(t, 0, 6) || p(t, 3, 4);
}

int main()
{
    char t[20];
    fread(t, 19, 1, stdin);
    t[19]=0;
    if (f(t)) puts("true"); else puts("false");
}

```

It works by looking for a row, column or diagonal containing three of the white pieces; `a` points to the target position (not already containing a white piece). Then the missing piece (`o`) is identified - it's the one we didn't remove from string `h` as we saw it.

If the piece is not on the board, it must be in the hand, and it can only be played into a space. Otherwise (if we found it on the board), it must be in a position where it can move into the target square. Since moves are reversible, we swap if necessary, so that `a < p`.

We test knight moves first - there are four legal downwards moves, and we avoid wrapping around the left/right edges of the board by verifying the number of newlines we pass.

After that, we test rook moves, and then bishop moves, using a similar algorithm (and a queen can use either of these moves).

## Test program

```
int expect_true(char *board)
{
    if (strlen(board) != 19) {
        fprintf(stderr, "Wrong length board:\n%s\n\n", board);
        return 1;
    }
    if (!f(board)) {
        fprintf(stderr, "Expected true, but got false, for\n%s\n\n", board);
        return 1;
    }
    return 0;
}

int expect_false(char *board)
{
    if (strlen(board) != 19) {
        fprintf(stderr, "Wrong length board:\n%s\n\n", board);
        return 1;
    }
    if (f(board)) {
        fprintf(stderr, "Expected false, but got true, for\n%s\n\n", board);
        return 1;
    }
    return 0;
}

int main()
{
    return
        + expect_true("rkb \n"
                      "    \n"
                      "    \n"
                      "RB Q")
        + expect_false("rk  \n"
                       "    \n"
                       "    \n"
                       "RBbQ")
        + expect_true("rk  \n"
                      " K  \n"
                      "    \n"
                      "RBbQ")
        + expect_true("rk  \n"
                      "    \n"
                      "K   \n"
                      "RBbQ")
        + expect_true("rkRB\n"
                       "    \n"
                       " Qb \n"
                       "K   ")
        + expect_true("rk  \n"
                      "    \n"
                      "K   \n"
                      "RBbQ");
}

```

## Counting program (in C++)

```
#include<algorithm>
#include<iostream>
#include<map>

int main()
{
    std::map<char,int> m;
    for (int c;  (c = getchar()) != EOF; )
        ++m[c];

    for (auto e: m)
        std::cout << e.first;

    std::cout << "\n distributed as follows: ";
    for (auto e: m)
        std::cout << e.second << "×`" << e.first << "`, ";
}

```
> 4 votes

---
Tags: code-challenge, decision-problem, chess, board-game, tic-tac-toe
---


title: Restricted-source polyglot string

text:
# Question
Title: Restricted-source polyglot string
Your goal is to write a program that prints the string `abc` in two languages. However, while the full code will print `abc` in one language (we'll call it Language 1), the other one (Language 2) must print `abc` if (and only if) every other character is skipped starting from the second character. If the full code is run in language 2, it must throw an error. If the skipped code is run in language 1, likewise, it must throw an error.

# Rules and Clarification

* Trailing newlines are allowed.
* Output must be lowercase.
* "Run" means compiled for compiled languages.
* We will define "throwing an error" as outputting nothing to STDOUT and something to STDERR.

# Test Cases

```
Language 1: 12345 -> abc
Language 1: 135 -> error
Language 2: 135 -> abc
Language 2: 12345 -> error

```

# Scoring

The shortest code in bytes wins (the full code, not the skipped code).

**Edit: I have clarified the rules based on feedback in the comments. The existing answers should still be valid.**

# Answer
> 8 votes
# brainfuck, ~~28~~ 26 bytes

```
a+b[c-/[/---<]>>- ]<-.+.+.

```

Try it online!

Got the bf code from here.

Fails in Ink due to Expected target for new thread but saw `'.+.+.'`.

# ink

```
abc//-<>-]-++

```

Try it online!

Ink will just print `abc` and the rest is a comment.

Fails in brainfuck due to mismatched bracket.

# Answer
> 6 votes
# Keg, ~~21~~ 19 bytes (~~19~~ 17 characters)

```
abc#1 / ╘ " a b c

```

Try it online!

Simply prints `abc` and the rest is a comment.

Fails in MathGolf due to an undefined operator overload of `/`. `/` can not work on an integer (`1`) and a string( pushed via the space instruction.)

# MathGolf

```
ac1/╘"abc

```

Try it online!

Does a bunch of nonsense, then  deletes the whole stack. `"abc` pushes `abc` and the stack has an implicit output.

Fails in Keg due to the failure of implicit-outputting a floating-point number in its character form.

# Answer
> 5 votes
# Japt and Pyth, 20 bytes

Both are shortenings of common scripting languages, nice

Japt: `"_a_b_c_"v ë2,1 +[]` (TIO, error in Pyth)

Pyth: `"abc" 21 [` (TIO, error in Japt)

# Answer
> 5 votes
# CJam and Gaia, 15 bytes

(CJam only cares about printable ASCII, so Gaia's codepage can be used to encode both programs)

**Full:**

```
 'a'b'c'” 'ọ;e<

```

Works in CJam

Errors in Gaia

**Reduced:**

```
 abc”'ọe

```

Works in Gaia

Errors in CJam

### Explanation

This takes some advantage of the fact that `'` defines a character literal in both languages.

**Full program:**

We push 5 characters: `a`, `b`, `c`, , and . `;` deletes the  and `e<` leaves the minimum of `c` and , which is `c`. The remaining characters (`abc`) are joined together and output implicitly.

In Gaia, everything up to  is a string literal. We then push the char , and then copy (`;`) the string literal back to the top and attempt to eval it (`e`). This throws an error because the last character in that string is `'`, which is improper syntax (a character literal after it is expected).

**Reduced program:**

(or, more specifically, byte 0xFB) is not defined, so the program terminates with an error.

In Gaia we get the string literal `abc` (with leading space). We then push the character  and eval it, which is the command for trim. This leaves plain `abc` on the stack, which is implicitly output.

# Answer
> 5 votes
# naz / , 54 bytes

```
6a6a5a5m1a5a1a5a1o5s1a5a1o5s1a5a1o0m3a4a1a2a2a7a4a0a3a

```

This has to be the most esoteric answer I've submitted so far.

**Explanation of the full code** (works in naz)

```
6a6a5a5m1a5a1a5a     # Set the register to a value of 97 ("a")
1o                   # Output once
5s1a5a1o             # Output "b"
5s1a5a1o             # Output "c"
0m3a4a1a2a2a7a4a0a3a # Extra arithmetic to allow for a valid 7 program

```

Fails in 7: `6 command run with no bar in the frame at /opt/7/7.pl line 605, <> chunk 1.`

**The reduced code** (works in 7)

```
665515151515151510341227403

```

Try it online!

Fails in naz: `error: attempt to chain number literals`

I can't give a very accurate explanation of the reduced code due to my relatively poor understanding of 7. I invite anyone who can make sense of it to improve this post.

# Answer
> 4 votes
# PHP and Emoji, 21 chars, 30 bytes

### Full:

```
⛽_a_b_c_➡➡;echo abc;

```

### Skipped:

```
⛽abc➡eh b;

```

PHP, Full - Try it online! Prints: `abc`

Emoji, Skipped - Try it online! Prints: `abc`

PHP, Skipped - Try it online! Error: `PHP Parse error: syntax error, unexpected 'b' (T_STRING)`

Emoji, Full - Try it online! Error: `IndexError: pop from empty list`

# Answer
> 4 votes
# JavaScript (V8) and PHP, 29 bytes

### Full:

```
print`abc`;'e_c_h_o_ _a_b_c';

```

### Skipped:

```
pitac;echo abc;

```

JavaScript, Full - Try it online! Prints: `abc`

PHP, Skipped - Try it online! Prints: `abc`

JavaScript, Skipped - Try it online! Error: `SyntaxError: Unexpected identifier`

PHP, Full - Try it online! Error: `abc: command not found`

# Answer
> 4 votes
# C++ (gcc) / C (gcc), 87 bytes

## Full (C++)

```
//*
#import<cstdio>
main(){puts("abc"/*//
m_a_i_n_(_)_{_p_u_t_s_(_"_a_b_c_"_/*/

) ; }

```

## Skipped (C)

```
/*#motcti>mi({us"b"*/main(){puts("abc"//
);}

```

Full C++, Working

Skipped C++, Error

Full C, Error

Skipped C, Working

# Answer
> 4 votes
## Backhand and \>\<\>, 39 bytes

### Full

```
8.cv*c0*~]!]/]:::[@:1[+ooo2o+@o.3.+.o.;

```

Prints abc in Backhand

Errors in \>\<\>

### Skipped

```
8c*0~!/::@1+o2+o3+o;

```

Prints abc in \>\<\>

Errors in Backhand

### Explanation

Backhand doesn't execute the instructions one by one. In the full version, it goes 3, then the `v` instruction turns it to two steps. In the skipped version, this has the consequence that only the first instruction overlaps with the full version.

When you run the skipped version on Backhand, it divides by zero. Errors in backhand don't stop the program, so I added a stop command, which makes \>\<\> a bit harder. (It's still a command in \>\<\>, just not a good one.)

\>\<\>, on the other hand, does not skip instructions. In the full version, a `.` means jump. Fish is a 2D language, so it pops two arguments. However, only 1 thing was pushed (because of `8`). Thus, `something smells fishy...`.

How I get around some of the commands in \>\<\> is simple. When `0` is executed, it pushes 0, then it immediately removes it. Then it skips the next command, which is a mirror. Finally, it duplicates twice, meaning 3 of the same thing is in the stack, which means `@`, which cycles the top 3 items in the stack, does absolutely nothing.

# Answer
> 3 votes
# Turing Machine Code and Whitespace, 85 bytes

**Full**

```
 	 0 _	a	r 1 ; ; ;	;

 1 _ b r 2	;	; ; ; ;	; ;

 2 _ c * 3	;	; ; ; ;	;	;
	;
 ; ;

```

Works in Turing Machine Code
Errors in Whitespace: `Prelude.!!: index too large`

**Reduced**

```

```

Works in Whitespace
Errors in Turing Machine Code: `Halted. No rule for state '0' and symbol '_'.`

Takes advantage of the fact that Turing Machine Code ignores most white space and Whitespace pretty much ignores everything else.

# Answer
> 2 votes
# GolfScript / MathGolf, 15 bytes

Here is a golfing language one in *pure* ASCII. (I guess the best score possible is 15 bytes...)

```
"abc"#; " a b c

```

Try it online!

## GolfScript explanation

```
"abc"           # Start a string
     #          # Create a comment (rest is a comment)
      ; " a b c

```

## MathGolf explanation

```
"abc"           Start a string
     #;         Perform expoentiation between the string and the input (implicitly a string)
                This isn't defined yet, so it throws an error
                Discarding the value won't be executed
        " a b c So does this

```

# MathGolf/GolfScript, 8 bytes

```
"b";"abc

```

Try it online!

# MathGolf Explanation

```
"b";     # Push b and then discard the value
    "abc # Push abc and then implicitly print

```

# GolfScript explanation

```
"b";     # Push b and then discard the value
    "abc # Unterminated string, throws an error

```

# Answer
> 2 votes
# Python 3 and Befunge-98, 36 bytes

```
z= print("@ , , , ""a b c "[8: :2] )

```

Works in Python:

```
z= print("@ , , , ""a b c "[8: :2] )

         "@ , , , "                  #String literal
                   "a b c "          #The second string literal is concatenated to the first
                           [8: :2]   #Extract every other character starting from index 8, which gives us "abc"
   print(                          ) #Print that and return None
z=                                   #Assign the result (None) to the variable z

```

Errors in Befunge:

```
z= print("@ , , , ""a b c "[8: :2] )

z     #No-op
 =    #Execute "" (raises an error in both FBBI and PyFunge)

```

## Every other character

```
z rn(@,,,"abc"8 2

```

Errors in Python

The code is nowhere close to anything resembling valid Python syntax, so it raises a `SyntaxError`.

Works in Befunge:

```
z rn(@,,,"abc"8 2

z                  #No-op
  r                #Reverse direction
z                  #No-op
              8 2  #Push 2 and 8 (which we don't care about) onto the stack
         "abc"     #Push "cba" onto the stack
        ,          #Print the top of the stack ("a")
       ,           #Print the top of the stack ("b")
      ,            #Print the top of the stack ("c")
     @             #End the program

```

# Answer
> 2 votes
# Rust / Python 3, 70 bytes

## Full (Rust)

```
const _:i8= 3;//1 ; p r i n t ( " a b c " ) #
fn main(){print!("abc")}

```

## Skipped (Python):

```
cnt_i=3/1;print("abc")#f an)pit(ac)

```

Rust fails on the skipped version with

```
error: unexpected closing delimiter: `)`
 --> a.py:1:28
  |
1 | cnt_i=3/1;print("abc")#f an)pit(ac)
  |                            ^ unexpected closing delimiter

error: aborting due to previous error

```

And Python fails on the full version with

```
  File "a.rs", line 1
    const _:i8= 3;//1 ; p r i n t ( " a b c " ) #
          ^
SyntaxError: invalid syntax

```

The Rust comment is turned into a division when one of the slashes disappears; the rest is fairly straightforward. I also avoided a compiler warning by naming the useless variable ‘`_`’.

# Answer
> 1 votes
# 05AB1E / MathGolf, 13 bytes/bytes

```
"aabbccc"1FÙ;

```

Try it online in 05AB1E (outputs `abc`).
Try it online in MathGolf (errors).

Every second character:

```
"abc"F;

```

Try it online in 05AB1E (errors).
Try it online in MathGolf (outputs `abc`).

**Explanation:**

```
# Full program in 05AB1E:
"aabbccc"     # Push string "aabbccc"
         1F   # Loop 1 time:
           Ù  #  Uniquify the top of the stack
            ; #  Halve it (no-op on strings)
              # (after the loop, the top of the stack is output implicitly)

# Full program in MathGolf:
           Ù  # Errors during compilation, because `Ù` isn't part of its known character-
              # set from the MathGolf codepage

# Reduced program in 05AB1E:
"abc"         # Push string "abc"
     F        # Loop that many times, which results in an error because it isn't an integer

# Reduced program in MathGolf:
"abc"         # Push string "abc"
     F        # Push builtin integer 17
      ;       # Discard the top of the stack
              # (after which the entire stack joined together is output implicitly as result)

```

# Answer
> 0 votes
# Ruby & Perl 5 \+ `-M5.10.0`, 29 bytes

```
s=a=y=$> .write  a=?a ,?b ,?c

```

`abc` in Ruby, error in Perl

This sets the variables `s`, `a` and `y` to the result of `write`ing `a=?a ,?b, ?c` (equivalent to `'abc'` as `?` defines a character literal and `write` accepts multiple arguments) to `$>` (`$>` points to `STDOUT` by default).

```
say$ wie =a,b,c

```

`abc` in Perl, error in Ruby

This calls `say` with `$ wie =a,b,c`, which sets `$ wie` to the bareword `a` and passes the barewords `b` and `c`.

---
Tags: code-golf, string, restricted-source, polyglot
---


title: Lucky dice rolls

text:
# Question
Title: Lucky dice rolls
## Lucky dice rolls

In pen and paper roleplaying games dice are used for various chance calculations. The usual way to describe a roll is \\$n\textbf{d}k\\$ where \\$n\\$ is the number of dice and \\$k\\$ is the number of faces on a die. For example \\$3d6\\$ means that you need to roll the classical 6-sided die 3 times (or roll 3 dice at the same time). Both \\$n\\$ and \\$k\\$ are positive integers. Each die's output value ranges from 1 to \\$k\\$.

Usually the values are then summed and they are used for various game mechanics like chance to hit something or damage calculations.

A lucky roll will mean that you have Fortuna's favor on your side (or against you). Luckiness is an integer number that increases (or decreases) the sum in the following way. The roll is modified to \\${(n+|luck|)}\textbf{d}{k}\\$ and the sum will be the \\$n\\$ best (or worst) values. Each die is fair, so they will have the same probability for the outcome of the possible values per die.

The \\$luck\\$ can be a negative number, in this case you need to get the \\$n\\$ worst values for the sum.

### Input

The integer values for \\$n,k,luck\\$ in any way.

### Output

The expected value for the sum of the (un)lucky roll. The expected value is \\$\sum{x\_{i} p\_{i}}\\$ where \\$x\_{i}\\$ is the possible outcome of the sum and \\$p\_{i}\\$ is the probability for \\$x\_{i}\\$ occuring, and \\$i\\$ indexes all possible outcomes. The output value can be float or rational number, at least 3 decimal places of accuracy or a fraction of two integer numbers, whichever suits your program better.

### Examples

```
n,k,luck    expected value
1,6,0       3.5
2,6,0       7
2,6,-1      5.54166
2,6,1       8.45833
2,6,-5      3.34854
2,10,-1     8.525
2,10,1      13.475
6,2,15      11.98223
6,2,-15     6.01776

```

### Scoring

Shortest code in bytes wins.

### Other

With this mechanic you essentially create fake dice using only fair dice. I wonder if there is a nice formula to calculate this mathematically.

Good luck! ;)

# Answer
# AnyDice, 82 bytes

```
function:l N K L{ifL<0{result:[lowestNof(N-L)dK]}else{result:[highestNof(N+L)dK]}}

```

Try it online!

For the output, check the "export" view and "summary" data and take the first value next to the output name (normally the link brings you there, but if you encounter issues, you know).

## Ungolfed for readability

```
function: l N K L {                  \ function with 3 parameters                                     \
  if L<0 {                           \  if L is negative                                              \
    result: [lowest N of (N-L)dK]    \   return the lowest N dice among (N-L) rolls of a K-sided die  \
  } else {                           \  else                                                          \
    result: [highest N of (N+L)dK]   \   return the highest N dice among (N-L) rolls of a K-sided die \
  }                                  \  end if                                                        \
}                                    \ end function                                                   \

```
> 9 votes

# Answer
# MATL, 24 bytes

```
|+i:Z^!S1G0>?P]2G:Y)XsYm

```

Inputs are: `luck`, `n`, `k`.

### How it works

```
|      % Implicit input: luck. Absolute value
+      % Implicit input: n. Add. Gives n+|luck|
i:     % Input: k. Range [1 2 ... k]
Z^     % Cartesian power. Gives a matrix with n+|luck| columns, where each
       % row is a Cartesian tuple
!      % Transpose
S      % Sort each column in ascending order
1G     % Push first input (luck) again
0>     % Is it positive?
?      % If so
  P    %   Flip vertically: the order within each column becomes descending
]      % End
2G:    % Push second input (n) again. Range [1 2 ... n]
Y)     % Row-index. This keeps the first n rows
Xs     % Sum of each row
Ym     % Mean. Implicit display

```

Try it online! Or verify all test cases.
> 4 votes

# Answer
# , ~~106~~ ~~96~~ 88 bytes

```
function(n,k,l)n*mean(apply(expand.grid(rep(list(NA,1:k),n+abs(l))),1,sort,l>0,T)[1:n,])

```

Try it online!

Credit to Dominic van Essen for the `l>0` for the `descending` argument to `sort`, and for golfing down a lot of other bytes!
> 4 votes

# Answer
# 05AB1E, 15 bytes

```
L²³Ä+ãε{³.$O}ÅA

```

Inputs in the order \\$k,n,luck\\$.

Try it online or verify all test cases.

**Explanation:**

```
L             # Push a list in the range [1, (implicit) input `k`]
 ²            # Push the second input `n`
  ³Ä+         # Add the absolute value of the third input `luck`
     ã        # Take the cartesian product of the list and this value
      ε       # Map each inner list to:
       {      #  Sort the list
        ³.$   #  Drop the third input amount of leading items,
              #   `luck` = 0: no items are removed
              #   `luck` = 1: the first item is removed
              #   `luck` = -1: the last item is removed
           O  #  Sum the remaining list of values
      }ÅA     # After the map: calculate the average of this list of sums
              # (after which it is output implicitly as result)

```
> 3 votes

# Answer
# Perl 5 `-MList::Util=sum -ap`, 116 bytes

```
@r=1..$F[1];$_=(sum map{(sort{$F[2]<0?$a-$b:$b-$a}/\d+/g)[0.."@F"-1]}@g=glob join$"=',',("{@r}")x("@F"+abs$F[2]))/@g

```

Try it online!

Enumerates all possible rolls, selects the top (bottom) entries from each list, adds all of those up, and divides by the number of combinations.
> 3 votes

# Answer
# , ~~152~~ ~~127~~ 109 bytes

```
function(n,k,l,w=n+abs(l))n*mean(apply(cbind(NA,mapply(rep,list(1:k),e=k^(w:1-1),l=k^w)),1,sort,l>0,T)[1:n,])

```

Try it online!

*Edit: -18 bytes thanks to Giuseppe for a really nice bit of programming! Note that this solution avoids a key `R` built-in function `expand.grid`, but Giuseppe's improvement manages to close-the-gap on his own solution (that uses the function) quite a lot.*

Commented:

```
lucky_total=function(n,k,l){
    m=n+abs(l)          # number of rolls including lucky rolls
    a=matrix(NA))       # initial (empty) matrix of roll results
    for(r in 1:m){      # do all the rolls & combine results in matrix
        a=cbind(a[rep(seq(d<-k^(r-1)),k),],rep(1:k,e=d))
    }
    mean(               # get the mean result of...
        apply(a,1,function(b)
                        # all the rolls, but only keeping
                        # the highest/lowest 'lucky' dice
                        # (using luck>0 to decide whether to sort
                        # increasing or decreasing)
            sum(sort(b,l>0)[1:n])
        )
    )
}

```
> 3 votes

# Answer
# , 45 bytes

Takes input as `k` on the left side and `n, luck` on the right side.

```
[:(+/%#){:@]+/@}.&|:1+[:/:~"1[#.inv(i.@^+&|/)

```

Try it online!

### How it works

```
[:(+/%#){:@]+/@}.&|:1+[:/:~"1[#.inv(i.@^+&|/)
                                    i.@^+&|/ 0..k^(|n| + |luck|)
                             [#.inv          to base k 0 0 0..5 5 5
                        /:~"1                sort each roll
                    1+                       0 0 0 -> 1 1 1
        {:@]   }.&|:                         transpose and drop luck rows
                                             negative values drop from end
            +/                               sum each roll
  (+/%#)                                     average of all rolls

```
> 3 votes

# Answer
# Python 2, 131 bytes

```
from itertools import*
n,k,l=input()
w=n+abs(l)
print sum(sum(sorted(x)[l>0and-n:][:n])for x in product(*[range(1,k+1)]*w))*1./k**w

```

Try it online!
> 2 votes

# Answer
# , ~~131~~ 119 bytes

```
function(Z,Y,l,E=Z*(1+Y)/2,`[`=pbinom)(sum(1:Y*((K=rep(1:Z-1,e=Y))[X<-abs(l)+Z,J<-1-1:Y/Y]-K[X,J+1/Y]))-E)*(-1)^(l<0)+E

```

Try it online!

Quite a fast implementation; calculates the value directly. It's binomials all the way down.

The key is the identity found here, for the expected value of a rolling \\$X\\$ d\\$Y\\$ and keeping the highest \\$Z\\$ of them. I rearranged it slightly to

$$\sum\_{j=1}^{Y}j \sum\_{k=0}^{Z-1} \sum\_{l=0}^k \binom{X}{l}\left(\left(\frac{Y-j}{Y}\right)^l\left(\frac{j}{Y}\right)^{X-l} - \left(\frac{Y-j+1}{Y}\right)^l\left(\frac{j-1}{Y}\right)^{X-l}\right). $$

Recognizing the innermost sum as the difference of two binomial CDFs, it's implemented as

```
sum(1:Y*(p(K<-rep(1:Z-1,e=Y),X,J)-p(K,X,J+1/Y)))

```

for maximum (ab)use of R's recycling rules. There is then an adjustment for the fact that we may wish to keep the *lowest* `n` dice, but that's easy due to the symmetry of the binomial distribution.
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~61~~ ~~58~~ ~~57~~ ~~64~~ 61 bytesSBCS

Full program, input order is `k`, `luck` and `n`.

```
(⊢⌹=⍨){w←1∘/⍵⋄1⊥w[⍒w]↑⍨n×(¯1*<∘0)l}¨(,∘.,)⍣(¯1+(n←⎕)+|l←⎕)⍨⍳⎕

```

Try it online! (with two extra bytes to print in TIO) or check all test cases!
> 1 votes

# Answer
# JavaScript (ES10), 143 bytes

A naive, straightforward approach.

```
(n,k,l)=>eval([...Array(N=k**(t=l<0?n-l:n+l))].flatMap((_,v)=>[...Array(t)].map((_,i)=>-~(v/k**i%k)).sort((a,b)=>(a-b)*l).slice(-n)).join`+`)/N

```

Try it online!

### How?

We generate \\$N=k^{n+|l|}\\$ arrays of length \\$n+|l|\\$ corresponding to all possible rolls, keeping only the \\$n\\$ best or \\$n\\$ worst die in each array.

We turn that into a single flat list of values, compute its sum and divide it by \\$N\\$.
> 1 votes

# Answer
# perl -alp -MList::Util=sum, 144 bytes

```
@,=map{@;=sort{$a<=>$b}/\d+/g;pop@;for$F[2]..-1;shift@;for 1..$F[2];sum @;}glob join",",("{".join(",",1..$F[1])."}")x($_+abs$F[2]);$_=sum(@,)/@,

```

Try it online!

More readable written:

```
use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

my ($n, $k, $luck) = @F;

my @a = map {         # Iterate over all possible rolls
    my @b = sort {$a <=> $b} /\d+/g;  # Grab the digits, sort them.
    pop @b for $luck .. -1;           # Remove the -luck best rolls.
    shift @b for 1 .. $luck;          # Remove the  luck worst rolls.
    sum @b;                           # Sum the remaining pips.
}
glob       #  Glob expansion (as the shell would do)
join ",",  #  Separate the results of each die in a roll.
           #  Almost any character will do, as long as it's
           #  not special for glob expansion, and not a digit
     (
        "{" .      # "{" introduces a set of things glob can choose from
            join (",", 1 .. $k) .   # 1 to number of faces
         "}"       # matching "}"
     ) x ($n + abs $luck);  # Number of dice in a roll

$_ = sum (@a) / @a;  # Sum the results of each different roll,
                     # and divide by the number of rolls; $_ is
                     # printed at the end of the program.

__END__

```

Reads space separated numbers from `STDIN`. Writes results to `STDOUT`.
> 1 votes

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

```
k=>l=>g=(n,w=[],h=i=>i&&g(n-1,[...w,i])+h(i-1),L=l<0?-l:l)=>n+L?h(k)/k:eval(w.sort((a,b)=>(a-b)*l).slice(L).join`+`)

```

Try it online!
> 1 votes

# Answer
# Charcoal, 57 bytes

```
ＮθＮηＮζ≧⁺↔ζθ≔ＸηθεＦε«≔⊕…⮌↨⁺ιεηθδＦ↔ζ≔Φδ⁻μ⌕δ÷⌊×δζζδ⊞υΣδ»Ｉ∕Συε

```

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

```
ＮθＮηＮζ

```

Input `n`, `k` and `l`.

```
≧⁺↔ζθ

```

Add `|l|` to `n`.

```
≔Ｘηθε

```

Calculate the number of possible outcomes of rolling `n+|l|` `k`-sided dice.

```
Ｆε«

```

Loop over each outcome index.

```
≔⊕…⮌↨⁺ιεηθδ

```

Generate the next outcome by converting to base `k` padded to length `n+|l|`.

```
Ｆ↔ζ

```

For each element of luck, ...

```
≔Φδ⁻μ⌕δ÷⌊×δζζδ

```

... remove the lowest or highest value from the outcome.

```
⊞υΣδ

```

Save the sum of the remaining dice.

```
»Ｉ∕Συε

```

Output the average sum.

41 bytes if `l` is limited to `-1`, `0` or `1`:

```
ＮθＮηＮζ≧⁺↔ζθ≔ＸηθεＩ∕ΣＥＥε⊕…⮌↨⁺ιεηθ⁻Σι×⌊×ιζζε

```

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

```
ＮθＮηＮ

```

Input `n`, `k` and `l`.

```
≧⁺↔ζθ

```

Add `|l|` to `n`.

```
≔Ｘηθε

```

Calculate the number of possible outcomes of rolling `n+|l|` `k`-sided dice.

```
Ｉ∕ΣＥＥε⊕…⮌↨⁺ιεηθ⁻Σι×⌊×ιζζε

```

Generate all the possible outcomes, but if the luck is `-1` or `1` then subtract the largest or smallest entry from the sum, finally calculating the average sum.
> 1 votes

---
Tags: code-golf, probability-theory
---


# Question
Title: Can this polyomino tile the toroidal grid?
Inspired by certain puzzles on *Flow Free: Warps*.

## Background

We all know that L-triominos can't tile the 3x3 board, and P-pentominos can't tile the 5x5 board. But the situation changes if we allow the board to wrap around in both dimensions:

### L-triominos can tile 3x3 toroidal grid

The 3rd tile wraps around through all four edges.

```
┌ ┌─┐ ┐
  │ │3
┌─┤ └─┐
│ │2  │
│ └─┬─┘
│1  │
└───┘ ┘

```

### P-pentominos can tile the 5x5 toroidal grid

The 5th tile wraps around through all four edges.

```
┌ ┌───┬─┐ ┐
  │   │ │
┌─┘   │ └─┐
│  1  │2  │
├─────┤   │
│  3  │   │
│   ┌─┴─┬─┤
│   │   │ │
└─┬─┘   │ ╵
  │  4  │5
└ └─────┘ ┘

```

Note that, in both cases, wrapping around in only one dimension doesn't allow such tiling.

In case the Unicode version is hard to read, here is the ASCII version:

```
3 2 3
1 2 2
1 1 3

5 1 1 2 5
1 1 1 2 2
3 3 3 2 2
3 3 4 4 5
5 4 4 4 5

```

## Challenge

Given a polyomino and the size (width and height) of the toroidal grid, determine if the polyomino can tile the toroidal grid. The polyomino can be flipped and/or rotated.

A polyomino can be given in a variety of ways:

* A list of coordinates representing each cell of polyomino
* A 2D grid with on/off values of your choice (in this case, you *cannot* assume that the size of the grid defining the polyomino matches that of the toroidal grid)

The output (true or false) can be given using the truthy/falsy values in your language of choice, or two distinct values to indicate true/false respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

The polyomino is given as the collection of `#` symbols.

### Truthy

```
# (singleton, a.k.a. monomino)
5x7 (or any size)
--------
## (domino)
4x3 (or any even size)
--------
#
## (L-triomino)
3x3 (as shown above)
--------
##
### (P-pentomino)
5x5 (as shown above)
--------
##
 ## (Z-tetromino)
4x4 (left as an exercise to the reader)
--------
###
#
# (V-pentomino)
5x5
--------
####
   #
   ### (a polyomino larger than the grid is possible)
4x4
--------
###
  ###
    ### (single polyomino can cover the entire grid, and can wrap multiple times)
3x3

```

### Falsy

```
## (domino)
3x5 (or any odd sizes)
--------
###
#
1x8
--------
# #
### (U-pentomino)
5x5

```

# Answer
> 8 votes
# Python 2, ~~300~~ ~~265~~ 163 bytes

*-35 bytes after suggestions from @xnor, @ovs, and largely @user202729 (removing evenly divisible check allowed for a one-liner + lambda)*

*-102 bytes following encouragement + general suggestions by @user202729*

```
lambda l,w,h:all(w*h-len({((e-(p&4)*e//2)*1j**p+p/8+p/8/w*1j)%w%(1j*h)for e in l for p in c})for c in combinations(range(8*w*h),w*h/len(l)))
from itertools import*

```

Takes input as a list of complex coordinates of each cell of the polyomino. Outputs False for Truthy and True for Falsey (quirky de Morgan optimization).

Try it online with many testcases. Since this brute-forces, I have commented out a few cases to run fast enough for TIO.

Thoroughly commented:

```
lambda l,w,h:
    all(                        # we want any configuration to work, but De Morgan gives any(L==len) <==> not all(L!=len) <==> not all(L-len)
        w*h-len(                      # if two polyominos in a configuration overlap, then there are duplicate cells
                                    #   so the length of the set is less
                {                   # create a set consisting of each possible position+orientation of L/len(l) polyominos:
                    (                   # here, e is a single cell of the given polyomino
                        (               # reflect e across the imaginary axis if p >= 4 (mod 8)
                            e-          # e-e.real*2 = e-e//.5 reflects across the Im axis
                            p&4             # Only reflect if the 2^2 bit is nonzero: gives 4* or 0* following
                            *e//2           # floor(z) = z.real when z is complex, so
                        )                   # e//2 (floor division) gives z.real/2 (complex floor division only works in Python 2)
                        *1j**p          # rotate depending on the 2^0 and 2^1 bits. i**x is cyclic every 4
                        +p/8              # translate horizontally (real component) by p>>3 (mod this later)
                        +p/8/w*1j           # translate vertically (im component) by p>>3 / w
                    )%w%(1j*h)          # mod to within grid (complex mods only work in Python 2)
                    for e in l      # find where each cell e of the given polyomino goes
                    for p in c      # do this for each c (each set of position+orientation integers)
                }
        )
        for c in combinations(           # iterate c over all sets of w*h/len(l) distinct integers from 0 to 8*L-1
            range(8*w*h)              # each of these 8*L integers corresponds to a single position/orientation of a polyomino
                                    # Bits 2^0 and 2^1 give the rotation, and 2^2 gives the reflection
                                    # The higher bits give the position from 0 to L=w*h-1  ==> (0,0) to (w-1,h-1)
            ,w*h/len(l)        # w*h/len(l) is the number of polyominos needed since len(l) is the number of cells per polyomino
                                    # can't switch to *[range(8*w*h)]*(w*h/len(l)) because Python 3 does not allow short complex operations as above
        )
    )
from itertools import*

```

A new 169-byte solution that replaces `combinations` with recursion:

```
g=lambda l,w,h,k=[]:all(g(l,w,h,k+[((e-(p&4)*e//2)*1j**p+p/8+p/8/w*1j)%w%(1j*h)for e in l])for p in range(8*w*h))if w*h>len(k)else len(set(k))-w*h
from itertools import*

```

This has the advantage of removing `combinations` (12 characters on its own) and one for loop, but the self-invocation takes many bytes. Currying would not save length.

# Answer
> 6 votes
# JavaScript (ES7), 233 bytes

Takes input as `(w)(h)(p)`, where \\$p\\$ is a binary matrix describing the polyomino. Returns \\$0\\$ or \\$1\\$.

Similar to my original answer, but uses a more complex expression to update the cells of the matrix instead of explicitly rotating the polyomino.

```
w=>h=>g=(p,m=Array(w*h).fill(o=1))=>+m.join``?(R=i=>i--?m.map((F,X)=>(F=k=>p.map((r,y)=>r.map((v,x)=>k|=v?m[Z=i&2?p[0].length+~x:x,~~(X/w+(i&1?Z:W))%h*w+(X+(i&1?W:Z))%w]^=1:0,W=i&4?p.length+~y:y))&&k)(F()||g(p,m)))|!o||R(i):0)(8):o=0

```

Try it online!

---

# JavaScript (ES7),  ~~311 ... 252~~  250 bytes

Takes input as `(w)(h)(p)`, where \\$p\\$ is a binary matrix describing the polyomino. Returns a Boolean value.

Not quite as desperately long as I was expecting. :p

```
w=>h=>g=(p,m=Array(w*h).fill(o=1),P)=>+m.join``?[...13**7+''].some(i=>(p.sort(_=>i-7).map((r,y)=>r.map((v,x)=>(P[x]=P[x]||[])[y]=v),P=[]),m.map((F,X)=>(F=k=>P.map((r,y)=>r.map((v,x)=>k|=v?m[~~(X/w+y)%h*w+(X+x)%w]^=1:0))&&k)(F()||g(p,m))),p=P,!o)):o=0

```

Try it online!

### How?

The following code builds all possible transformations \\$P\\$ of the polyomino \\$p\\$:

```
[...13 ** 7 + '']         // this expands to ['6','2','7','4','8','5','1','7']
.some(i =>                // for each value i in the above list:
  ( p.sort(_ => i - 7)    //   reverse the rows of p[], except when i = '8'
    .map((r, y) =>        //   for each row r[] at position y in m[]:
      r.map((v, x) =>     //     for each value v at position x in r[]:
        ( P[x] =          //       transpose p[y][x]
          P[x] || [] )    //              to P[x][y]
        [y] = v           //
      ),                  //     end of inner map()
      P = []              //     start with an empty array
    )                     //   end of outer map()
    (...)                 //   more fun things happen here!
    p = P,                //   get ready for the next transformation
    !o                    //   success if o is cleared
  )                       //
)                         // end of some()

```

We use a flat array of \\$w\times h\\$ entries to describe the matrix. All of them are initially set to \\$1\\$.

The function \\$F\\$ inserts the polyomino in the matrix at the position \\$(X,Y)\\$ by XOR'ing the cells. It returns \\$0\\$ if the operation was done without setting any cell back to \\$1\\$.

```
F = k =>                  // expects k undefined for the first call
  P.map((r, y) =>         // for each row r[] at position y in P[]:
    r.map((v, x) =>       //   for each value v at position x in r[]:
      k |=                //     update k:
        v ?               //       if v is set:
          m[~~(X / w + y) //         toggle the value at (X + x, Y + Y),
            % h * w +     //         taking the wrapping around into account
            (X + x) % w   //
          ] ^= 1          //         k is set if the result is not 0
        :                 //       else:
          0               //         leave k unchanged
    )                     //   end of inner map()
  ) && k                  // end of outer map(); return k

```

For each position \\$(X,Y)\\$ in the matrix:

* We do a first call to \\$F\\$. If successful, it is followed by a recursive call to the main function \\$g\\$.
* We just need to call \\$F\\$ a second time to remove the polyomino -- or to clear the mess if it was inserted at an invalid position.

Hence the code:

```
F(F() || g(p, m))

```

The recursion stops when there's no more \\$1\\$'s in the matrix (success) or there's no more valid position for the polyomino (failure).

# Answer
> 2 votes
# Charcoal, ~~120~~ 115 bytes

```
ＮθＮηＷＳ⊞υ⌕Ａι#≔⟦⟧ζＦθＦηＦ²«≔ＥθＥη⁰εＦＬυＦ§υμ¿λ§≔§ε⁺κν﹪⁺ιμη¹§≔§ε⁺ιμ﹪⁺κνη¹Ｆ²Ｆ²⊞ζ↨⭆⎇μ⮌εε⪫⎇ν⮌ξξω²»≔…ζ¹υＦυＦζＦ¬＆ικ⊞υ｜ικ⁼⊟υ⊖Ｘ²×θη

```

Try it online! Link is to verbose version of code. Takes inputs in the order width, height, newline-terminated polyomino and outputs a Charcoal boolean i.e. `-` only if the polyomino tiles the torus. Explanation:

```
ＮθＮη

```

Input the size of the grid.

```
ＷＳ⊞υ⌕Ａι#

```

Input the polyomino and convert it to a list of horizontal indices.

```
≔⟦⟧ζ

```

Start building up a list of polyomino placements.

```
ＦθＦηＦ²«

```

Loop through each vertical and horizontal offset and direction.

```
≔ＥθＥη⁰ε

```

Start with an empty grid.

```
ＦＬυＦ§υμ

```

Loop over each cell of the polyomino...

```
¿λ§≔§ε⁺κν﹪⁺ιμη¹§≔§ε⁺ιμ﹪⁺κνη¹

```

... place the optionally transposed cell in the grid, but offset by the outer indices.

```
Ｆ²Ｆ²⊞ζ↨⭆⎇μ⮌εε⪫⎇ν⮌ξξω²

```

For each of four reflections of the grid, push the grid to the list of placements, represented as a base 2 integer (e.g. a grid with just the bottom right square filled would be 1 etc.)

```
»≔…ζ¹υＦυ

```

Start a breadth first search using the first placement.

```
Ｆζ

```

Loop over each placement.

```
Ｆ¬＆ικ

```

If this placement does not overlap the grid so far...

```
⊞υ｜ικ

```

... then push the merged grid to the list of grids.

```
⁼⊟υ⊖Ｘ²×θη

```

Check whether we pushed a completed grid. (This must be the last entry because any incomplete grid must by definition have fewer polyominoes and would therefore have been discovered earlier.)

---
Tags: code-golf, decision-problem, grid, tiling, polyomino
---


# Question
Title: Reachability measure in Conway's Soldiers
## Background

**Conway's Soldiers** is a version of peg solitaire played on an infinite checkerboard. The board is initially full of pegs below an infinite horizontal line, and empty above it. Following the ordinary peg solitaire rules (move a peg by jumping over another one horizontally or vertically, removing the one that was jumped over), the objective is to move a peg as far above the horizontal line as possible.

Wikipedia page has the solutions for 1 to 4 units above the line: (A and B denote two possible alternatives.)

In ASCII notation (using alternative B):

```
                         X
               X         .
        X      .         .
_X_   __._   __.__   ____.____
 O    OOO    OOOOO   OOOOOOOOO
 O      O      OOO     OOOO
                      OOOOO
                        OO

```

Conway proved that it is impossible to reach 5 units above the line with finite number of moves. To prove it, he assigned a value to each peg: if a peg is \\$n\\$ units away from the target position in terms of Manhattan distance, it is assigned the value of \\$\varphi^n\\$, where

$$ \varphi = \frac{\sqrt5 - 1}{2} $$

(The value is the golden ratio minus 1.)

This value was carefully chosen to ensure that every possible move keeps the total value constant when a move is towards `X`, and decreasing when a move is away from it. Also, the final state must have a peg precisely at the target position, giving the value of \\$\varphi^0 = 1\\$, so the target position is unreachable if the initial configuration has the value sum less than 1.

For the target position at 5 units above the line, the configuration looks like this:

```
     X
     .
     .
     .
_____._____
OOOCBABCOOO
OOOOCBCOOOO
OOOOOCOOOOO
    ...

```

The peg at the position `A` is given \\$\varphi^5\\$, the ones at `B` are \\$\varphi^6\\$ each, and so on. Then he showed that the sum for the infinite number of pegs is exactly 1, and therefore the value sum of any *finite* subset is less than 1, concluding the proof of non-reachability.

## Task

Now, let's apply this measure to an arbitrary configuration, not just for the original problem, e.g. the pegs may surround the target position:

```
OOOOO
O...O
O.X.O
O...O
OOOOO

```

Given such a configuration, calculate Conway's measure on it and **output truthy if the measure is at least 1, falsey otherwise**. (Note that the truthy output does not *guarantee* that the target is actually reachable, while the falsey output *does* say that the target is too far away from the pegs to reach it.)

The calculated measure should be within `1e-6` margin. A program that produces wrong answers when the computed one falls within \\$\pm10^{-6}\\$ from the true measure is acceptable. You can use `(sqrt(5)-1)/2` or `0.618034`, but not `0.61803` or `0.61804`.

You can choose any three distinct symbols (characters, numbers, or any other kind of values) to indicate a peg, an empty space, and the target position respectively. You can take the grid as a matrix, a list of strings (or lists of symbols), or a single string (or a list of symbols) with a delimiter of your choice. You can assume that the input has exactly one target position, and it is not already occupied by a peg.

## Test cases

In the test cases below, `O` is a peg, `X` is the target position, and `.` is a blank.

### True

```
measure = 1 (0.61803 will fail all of the measure=1 cases)
OOX
--------------
measure = 1
OO.X
.O..
.O..
--------------
measure = 1
..X..
.....
.....
OOOOO
..OOO
--------------
measure = 1
....X....
.........
.........
.........
OOOOOOOOO
..OOOO...
.OOOOO...
...OO....
--------------
measure = 4
OOOOO
O...O
O.X.O
O...O
OOOOO
--------------
measure ~ 1.00813
X....OOOO
....OOOO.
...OOOO..
..OOOO...
.OOOO....

```

### False

```
measure ~ 0.618
OO.X
--------------
measure ~ 0.999975 (0.61804 will fail)
OOOOOOOOOOOOOOOOOOOOOO.X
--------------
measure ~ 0.9868
X....OOO
....OOOO
...OOOO.
..OOOO..
.OOOO...
--------------
measure = 0
.....
.....
..X..
.....
.....

```

# Answer
> 5 votes
# Python 3.8, 109 bytes

```
lambda s,i=-1:sum(c%2*.618034**(abs((i:=i+1)//(n:=(h:=s.index)(0)+1)-(x:=h(2))//n)+abs(i%n-x%n))for c in s)>1

```

Try it online!

Input is a list of integers, created by concatenating all rows of the grid. Each row is terminated by the number `0`. Use the numbers `1, 2, 4` to represents `"O", "X", "."`.

---

### Python 3.8, 108 bytes

```
lambda s,i=-1:sum(c%2*.618034**(abs((i:=i+1)//(n:=s.find(0)+1)-(x:=s.find(2))//n)+abs(i%n-x%n))for c in s)>1

```

Try it online!

Pushing the input format a little bit here by using unprintable characters. Input is a single byte string of concatenated rows, where each row is terminated by a `NULL` character (code point `0`).
Replace `X` with the character `SOT` (code point `2`).

Byte string is essentially an integer list of code points. The reason I'm not using list of integer is because list doesn't have `find` method. The code points of the row terminator and `X` are chosen to be single digit.

---

**How**:

The length of each row (including the terminator) can be simply calculated as:

```
n:=s.find(0)+1  # terminator is represented as 0

```

Similarly, the target position is

```
x:=s.find(2)    # X is represented as 2

```

We can then do some modular tricks to figure out the Manhattan distance between a position `i` and the target `x`:

```
abs(i//n + x//n) + abs(i%n + x%n)

```

All of these are shoved into a single expression by abusing walrus operator.

# Answer
> 3 votes
# Python 2, ~~111~~ 110 bytes

Thanks to @xnor for suggesting to use numbers as input, rather than a list of strings

```
g=input()
f=g.index;l=f(5)+1
c=i=0
for r in g:c+=r/9*.618034**(abs(f(2)/l-i/l)+abs(f(2)%l-i%l));i+=1
print c>1

```

Try it online!

Input is a single list of numbers. Uses `9` for pegs, `0` for blanks, `2` for the target, and `5` as a line terminator.

---

### Python 2, 118 bytes

Solution provided by @Surculose Sputum

```
g=input()
f=g.find;l=f(',')+1;m=f('X')
c=i=0
for r in g:c+=(r<',')*.618034**(abs(m/l-i/l)+abs(m%l-i%l));i+=1
print c>1

```

Try it online!

Uses `+` instead of `O` to represent a peg. Input is a single string where rows are terminated by commas (`,`).

---

### Original solution, 128 bytes

```
g=input();l=len(g[0]);g=''.join(g)
m=g.find('X')
c=i=0
for r in g:c+=(r<'-')*.618034**(abs(m/l-i/l)+abs(m%l-i%l));i+=1
print c>1

```

Try it online!

Uses `+` instead of `O` to represent a peg. Input is a list of strings representing the rows

# Answer
> 2 votes
# , 46 bytes

```
$(1<:1#.0.618034^1&#.)@(|@-"1{.)/@(#:I.)1 2=/,

```

Try it online!

# Answer
> 2 votes
# Charcoal, ~~86~~ 84 bytes

```
ＷＳ⊞υι≔⌕Ｅυ№ιX¹θ≔⟦⟧ζＦＬυＦ⁻⌕Ａ§υιO⌕§υθX⊞ζ⁺↔⁻ιθ↔κ≔Ｅ²ιδＦ⌈ζ⊞δ↨…⮌δ²±¹Ｉ⊘⁺ΣＥζ⁺§δ⊖ι§δ⊕ι×₂⁵ΣＥζ§δι

```

Try it online! Link is to verbose version of code. Uses exact surd arithmetic, and then converts the final surd to floating-point using \\$ \sqrt 5 \\$. Explanation:

```
ＷＳ⊞υι

```

Input the configuration.

```
≔⌕Ｅυ№ιX¹θ

```

Find the row that contains the `X`.

```
≔⟦⟧ζ

```

Start a list of `O` distances.

```
ＦＬυ

```

Loop through each row.

```
Ｆ⁻⌕Ａ§υιO⌕§υθX

```

Loop through each column that contains an `O`, and calculate the relative column offset from the `X`.

```
⊞ζ⁺↔⁻ιθ↔κ

```

For each relative column offset, add its absolute value to the absolute value of the relative row offset, and push that to the list of `O` distances.

(I would prefer to write the above as `Ｆ⁺↔⁻ιθ↔⁻⌕Ａ§υιO⌕§υθX⊞ζκ` which is slightly more efficient but Charcoal can't take the absolute value of an empty list.)

```
≔Ｅ²ιδ

```

Now start generating negative Fibonacci numbers starting with \\$ F\_0, F\_{-1} \\$ and working down.

```
Ｆ⌈ζ⊞δ↨…⮌δ²±¹

```

Get the maximum distance and add that many more negative Fibonacci numbers.

```
Ｉ⊘⁺ΣＥζ⁺§δ⊖ι§δ⊕ι×₂⁵ΣＥζ§δι

```

Calculate the total distance using the formula \\$ \sum \phi^{-n} = \frac 1 2 \left ( \sum L\_{-n} + \sqrt 5 \sum F\_{-n} \right ) \\$ where \\$ L\_n = F\_{n-1} + F\_{n+1} \\$.

# Answer
> 1 votes
# Jelly, 25 bytes

```
ŒĠḊạ€Ɲ§µ5½’H*SS<1¬
SS>3aÇ

```

Try it Online!

All testcases This should yield 6 truthy then 5 falsey outputs (I added the extra cases `OX` and `X`, which cause special problems with this algorithm). See the calculated value sums if interested.

Takes input as a rectangular array, where `.OX` corresponds to `012` (empty, peg, target).

## How it works

```
ŒĠḊạ€Ɲ§µ5½’H*SS<1¬  # Is the value sum at least 1?
ŒĠ                    # Get an tuple of (coords of all 0 entries, coords of all 1 entries, coords of all 2 entries)
                      # If the matrix does not contain one of these, then that element of the tuple is left out, necessitating the SS>3 check
  Ḋ                   # Dequeue: remove the irrelevant coords of all 0 entries
   ạ€Ɲ                # Get the absolute (x,y) offset of all 1 entries from the 2 entry
      §               # Sum for Manhattan distance
       µ              # We are left with the Manhattan distances of each 1 from the 2
        5½’H          # (sqrt(5)-1)/2
            *         # to the power of
             S        # Each distance (S is sum, why is this an identity?)
              S       # Sum these powers to get the value sum
               <1¬    # Is this not less than 1? (Jelly has no <= operator)
                      # As a side note, ‘ÆC counts the number of primes <= z+1
                      # This is the same number of bytes as <1¬ and also returns a nonnegative value iff z is at least 1

SS>3aÇ               # Main link
SS>3                  # Is the sum of all entries > 3? (this is necessary to deal with having no pegs or no blanks, which messes with ŒĠ)
    a                 # and
     Ç                # the value sum is at least one

```

## Extras

Another 25-byte solution:

```
;0ŒĠḊạ€Ɲ§µ5½’H*SS<1¬
ḢLaÇ

```

21 bytes if `[[2]]` (target but no pegs) is not included as a testcase;

```
;0ŒĠḊạ€Ɲ§µ5½’H*SS

```

# Answer
> 0 votes
# Pyth, 37 bytes

```
!>1s.e*/b9^t.n3+a/KxQ2JhxQ5/kJa%KJ%kJ

```

Try it online! (You can copy-paste formatted test cases from my Python answer)

Port of my Python answer. Input is a single list of numbers. Uses `9` for pegs, `0` for blanks, `2` for the target, and `5` as a line terminator.

```
!>1s.e*/b9^t.n3+a/KxQ2JhxQ5/kJa%KJ%kJ
                  KxQ2       Initialize K to be the index of 2 in the input
                      JhxQ5  Initialize J to be the index of 5, plus 1
    .e                       Enumerated Map over the input, with b as the value, k as the index
            .n3              pre-initialized constant: phi (~1.6180339)
           t                  minus 1
          ^                  raised to the exponent:
                a/KJ/kJ       absolute difference between K/J and (index)/J
               +               plus
                a%KJ%kJ       absolute difference between K%J and (index)%J
                             (this gives us the manhattan distance between the current point and the target)
      *                      Multiply by
       /b9                    divide b by 9, yields 1 if b is a peg, 0 otherwise
   s                    Sum the mapped values
!>1                     Return true if greater than or equal to 1, false otherwise
                       (We can't use "less than" because the first test case yields 1.0 exactly)

```

---
Tags: code-golf, math, decision-problem, grid
---