title: Distances to coordinates

text:
# Question
Title: Distances to coordinates
There are *n* people on a 2D plane. Using distances between them we're going to find their positions. To get a unique answer you must make four assumptions:

1. There are at least 3 people.
2. The first person is at position (0, 0).
3. The second person is at position (x, 0) for some x \> 0.
4. The third person is at position (x, y) for some y \> 0.

So your challenge is to write a program or function that given a 2D array of distances (where `D[i][j]` gives the distance between person `i` and `j`) returns a list of their coordinates. Your answer must be accurate to at least 6 significant figures. Shortest solution in bytes wins.

---

### Examples

```
[[0.0, 3.0, 5.0], [3.0, 0.0, 4.0], [5.0, 4.0, 0.0]]

=>

[[0.0, 0.0], [3.0, 0.0], [3.0, 4.0]]

[[0.0, 0.0513, 1.05809686, 0.53741028, 0.87113533], [0.0513, 0.0, 1.0780606,
0.58863967, 0.91899559], [1.05809686, 1.0780606, 0.0, 0.96529704,
1.37140397], [0.53741028, 0.58863967, 0.96529704, 0.0, 0.44501955],
[0.87113533, 0.91899559, 1.37140397, 0.44501955, 0.0]]

=>

[[0.0, 0.0], [0.0513, 0.0], [-0.39, 0.9836], [-0.5366, 0.0295], [-0.8094, -0.3221]]

[[0.0, 41.9519, 21.89390815, 108.37048253, 91.40006121, 49.35063671,
82.20983622, 83.69080223, 80.39436793, 86.5204431, 91.24484876, 22.32327813,
99.5351474, 72.1001264, 71.98278813, 99.8621559, 104.59071383, 108.61475753,
94.91576952, 93.20212636], [41.9519, 0.0, 24.33770482, 144.67214389,
132.28290899, 49.12079288, 85.34321428, 117.39095617, 103.60848008,
79.67795144, 69.52024038, 42.65007733, 105.60007249, 110.50120501,
89.92218111, 60.03623019, 133.61394005, 76.26668715, 130.54041305,
122.74547069], [21.89390815, 24.33770482, 0.0, 130.04213984, 112.98940283,
54.26427666, 71.35378232, 104.72088677, 81.67425703, 90.26668791,
71.13288376, 18.74250061, 109.87223765, 93.96339767, 69.46698314,
84.37362794, 124.38527485, 98.82541733, 116.43603102, 113.07526035],
[108.37048253, 144.67214389, 130.04213984, 0.0, 37.8990613, 111.2161525,
176.70411028, 28.99007398, 149.1355788, 124.17549005, 198.6298252,
126.02950495, 101.55746829, 37.24713176, 152.8114446, 189.29178553,
34.96711005, 180.83483984, 14.33728853, 35.75999058], [91.40006121,
132.28290899, 112.98940283, 37.8990613, 0.0, 111.05881157, 147.27385449,
44.12747289, 115.00173099, 134.19476383, 175.9860033, 104.1315771,
120.19673135, 27.75062658, 120.90347767, 184.88952087, 65.64187459,
183.20903265, 36.35677531, 60.34864715], [49.35063671, 49.12079288,
54.26427666, 111.2161525, 111.05881157, 0.0, 125.59451494, 82.23823276,
129.68328938, 37.23819968, 118.38443321, 68.15130552, 56.84347674,
84.29966837, 120.38742076, 78.30380948, 91.88522811, 72.15031414,
97.00421525, 82.23460459], [82.20983622, 85.34321428, 71.35378232,
176.70411028, 147.27385449, 125.59451494, 0.0, 158.1002588, 45.08950594,
161.43320938, 50.02998891, 59.93581537, 180.43028005, 139.95387244,
30.1390519, 133.42262669, 182.2085151, 158.47101132, 165.61965338,
170.96891788], [83.69080223, 117.39095617, 104.72088677, 28.99007398,
44.12747289, 82.23823276, 158.1002588, 0.0, 136.48099476, 96.57856065,
174.901291, 103.29640959, 77.53059476, 22.95598599, 137.23185588,
160.37639016, 26.14552185, 152.04872054, 14.96145727, 17.29636403],
[80.39436793, 103.60848008, 81.67425703, 149.1355788, 115.00173099,
129.68328938, 45.08950594, 136.48099476, 0.0, 166.89727482, 92.90019808,
63.53459104, 177.66159356, 115.1228903, 16.7609065, 160.79059188,
162.35278463, 179.82760993, 140.44928488, 151.9058635], [86.5204431,
79.67795144, 90.26668791, 124.17549005, 134.19476383, 37.23819968,
161.43320938, 96.57856065, 166.89727482, 0.0, 148.39351779, 105.1934756,
34.72852943, 106.44495924, 157.55442606, 83.19240274, 96.09890812,
61.77726814, 111.24915274, 89.68625779], [91.24484876, 69.52024038,
71.13288376, 198.6298252, 175.9860033, 118.38443321, 50.02998891,
174.901291, 92.90019808, 148.39351779, 0.0, 72.71434547, 175.07913091,
161.59035051, 76.3634308, 96.89392413, 195.433818, 127.21259331,
185.63246606, 184.09218079], [22.32327813, 42.65007733, 18.74250061,
126.02950495, 104.1315771, 68.15130552, 59.93581537, 103.29640959,
63.53459104, 105.1934756, 72.71434547, 0.0, 121.04924013, 88.90999601,
52.48935172, 102.51264644, 125.51831504, 117.54806623, 113.26375241,
114.12813777], [99.5351474, 105.60007249, 109.87223765, 101.55746829,
120.19673135, 56.84347674, 180.43028005, 77.53059476, 177.66159356,
34.72852943, 175.07913091, 121.04924013, 0.0, 93.63052717, 171.17130953,
117.77417844, 69.1477611, 95.81237385, 90.62801636, 65.7996984],
[72.1001264, 110.50120501, 93.96339767, 37.24713176, 27.75062658,
84.29966837, 139.95387244, 22.95598599, 115.1228903, 106.44495924,
161.59035051, 88.90999601, 93.63052717, 0.0, 117.17351252, 159.88686894,
48.89223072, 156.34374083, 25.76186961, 40.13509273], [71.98278813,
89.92218111, 69.46698314, 152.8114446, 120.90347767, 120.38742076,
30.1390519, 137.23185588, 16.7609065, 157.55442606, 76.3634308, 52.48935172,
171.17130953, 117.17351252, 0.0, 145.68608389, 162.51692098, 166.12926334,
142.8970605, 151.6440003], [99.8621559, 60.03623019, 84.37362794,
189.29178553, 184.88952087, 78.30380948, 133.42262669, 160.37639016,
160.79059188, 83.19240274, 96.89392413, 102.51264644, 117.77417844,
159.88686894, 145.68608389, 0.0, 169.4299171, 33.39882791, 175.00707479,
160.25054951], [104.59071383, 133.61394005, 124.38527485, 34.96711005,
65.64187459, 91.88522811, 182.2085151, 26.14552185, 162.35278463,
96.09890812, 195.433818, 125.51831504, 69.1477611, 48.89223072,
162.51692098, 169.4299171, 0.0, 156.08760216, 29.36259602, 11.39668734],
[108.61475753, 76.26668715, 98.82541733, 180.83483984, 183.20903265,
72.15031414, 158.47101132, 152.04872054, 179.82760993, 61.77726814,
127.21259331, 117.54806623, 95.81237385, 156.34374083, 166.12926334,
33.39882791, 156.08760216, 0.0, 167.00907734, 148.3962894], [94.91576952,
130.54041305, 116.43603102, 14.33728853, 36.35677531, 97.00421525,
165.61965338, 14.96145727, 140.44928488, 111.24915274, 185.63246606,
113.26375241, 90.62801636, 25.76186961, 142.8970605, 175.00707479,
29.36259602, 167.00907734, 0.0, 25.82164171], [93.20212636, 122.74547069,
113.07526035, 35.75999058, 60.34864715, 82.23460459, 170.96891788,
17.29636403, 151.9058635, 89.68625779, 184.09218079, 114.12813777,
65.7996984, 40.13509273, 151.6440003, 160.25054951, 11.39668734,
148.3962894, 25.82164171, 0.0]]

=>

[[0.0, 0.0], [41.9519, 0.0], [19.6294, 9.6969], [-88.505, -62.5382],
[-88.0155, -24.6423], [21.2457, -44.5433], [14.7187, 80.8815], [-59.789,
-58.5613], [-29.9331, 74.6141], [34.5297, -79.3315], [62.6017, 66.3826],
[5.2353, 21.7007], [6.1479, -99.3451], [-62.597, -35.7777], [-13.6408,
70.6785], [96.8736, -24.2478], [-61.4216, -84.6558], [92.2547, -57.3257],
[-74.7503, -58.4927], [-55.0613, -75.199]]

```

# Answer
> 6 votes
# APL (Dyalog Unicode), ~~74~~ 59 bytes

```
+⍣(0>11○3⊃⊢)p÷×2⊃p←0j1⊥2↑⍉⊃⌹∘⍉⍨/1 .5*⍨2↑8415⌶.5×(⊣.+⍨-⊢)×⍨⎕

```

Try it online!

Lots of golfing at various places thanks to @H.PWiz and @ngn.

Uses the formula shown in the paper shared by Jonathan Allan. The formula on the paper involves EVD (eigenvalue decomposition), and fortunately Dyalog APL has its generalized version SVD(singular value decomposition). For square symmetric matrix \\$M\\$ as input, it exactly computes orthonormal \\$U\\$ and the diagonal matrix of eigenvalues \\$\Lambda\\$ in \\$M=U\Lambda U^T\\$.

### Ungolfed and how it works

```
f←{
  m←×⍨⍵                     ⍝ square of distances
  v←1⌷m                     ⍝ first row
  G←.5×v+⍤1⍉m-⍤1⍨v          ⍝ -(m - column v - row v)÷2
            m-⍤1⍨v  ⍝ add v to -m by rows (rank 1)
           ⍉        ⍝ transpose
       v+⍤1         ⍝ add v to that by rows
    .5×             ⍝ halve

  U E←2↑8415⌶G              ⍝ singular value decomposition
        8415⌶G  ⍝ SVD built-in
                ⍝ since G is square and symmetric, it is identical to EVD
                ⍝ and gives orthonormal U, eigenvalue diagonal E,
                ⍝ transpose of V (≡ U), and a boolean indicator for success
      2↑        ⍝ we need only U and E

  pts←0j1⊥⊖(2↑E*.5)+.×⍉U    ⍝ compute pts as shown in the paper
                            ⍝ and convert to complex
           (2↑E*.5)         ⍝ first 2 rows of element-wise sqrt of E
                   +.×⍉U    ⍝ matmul with transposed U
                            ⍝ the resulting matrix is 2-row matrix where
                            ⍝ 1st row is x-coords and 2nd is y-coords
      0j1⊥⊖                 ⍝ compute x+yi for post-processing

  pts←pts×+×2⊃pts     ⍝ rotate by 2nd point's angle reversed
            2⊃pts  ⍝ the 2nd point
           ×       ⍝ signum; unit vector (representing angle)
          +        ⍝ complex conjugate (negation of angle)
      pts×         ⍝ rotate all points by that angle

  +⍣(0>11○3⊃pts)⊢pts  ⍝ mirror w.r.t. x-axis if 3rd point is below x-axis
  +⍣(          )  ⍝ conjugate all points (mirror w.r.t. x-axis) if...
          3⊃pts   ⍝ the 3rd point
       11○        ⍝ its complex part
     0>           ⍝ is negative
}

```

# Answer
> 5 votes
# Python 2, ~~183~~ ~~178~~ ~~166~~ ~~161~~ ~~160~~ ~~159~~ ~~158~~ 156 bytes

*Saved 1 byte thanks to @Giuseppe and 2 bytes thanks to @JonathanFrech.*

```
def f(D):
 X=D[0][1];o=[0,X];O=[0,0];n=2
 for d in D[2:]:y=d[0]**2;x=(y-d[1]**2)/X/2+X/2;y-=x*x;o+=x,;O+=y**.5*(y>d[2]**2-(x-o[2])**2or-1),;n+=1
 return o,O

```

Try it online!

Uses the first 3 points to calculate the rest. Returns a pair of `x-coords, y-coords` as allowed in comments.

# Answer
> 5 votes
## R, 107

```
function(d){y=t(cmdscale(d))
y=y-y[,1]
p=cbind(c(y[3],-y[4]),y[4:3])%*%y/sum(y[,2]^2)^.5
p*c(1,sign(p[6]))}

```

The big head start is on line 1 where I use R's function for Multi-Dimensional Scaling (MDS). The rest is probably inefficient (thanks for making suggestions on how to improve): line 2 translates the data so that the first point is at (0, 0); line 3 rotates the points so that the second point is at (0,x); line 4 flips everything so that the third point is at y\>0.

# Answer
> 3 votes
# JavaScript (ES7), ~~202~~ 193 bytes

```
d=>{for(k=7;(a=d.map((r,i)=>[x=(r[0]**2-r[1]**2+a*a)/2/a,(d[0][i]**2-x*x)**.5*(k>>i&1||-1)],a=d[0][1])).some(([x,y],i)=>a.some(([X,Y],j)=>(Math.hypot(x-X,y-Y)-d[i][j])**2>1e-6));k+=8);return a}

```

### Test cases

```
let f =

d=>{for(k=7;(a=d.map((r,i)=>[x=(r[0]**2-r[1]**2+a*a)/2/a,(d[0][i]**2-x*x)**.5*(k>>i&1||-1)],a=d[0][1])).some(([x,y],i)=>a.some(([X,Y],j)=>(Math.hypot(x-X,y-Y)-d[i][j])**2>1e-6));k+=8);return a}

format = a => a.map(JSON.stringify).join`\n`

console.log(format(f([[0.0,3.0,5.0],[3.0,0.0,4.0],[5.0,4.0,0.0]])))
console.log(format(f([[0.0,0.0513,1.05809686,0.53741028,0.87113533],[0.0513,0.0,1.0780606,0.58863967,0.91899559],[1.05809686,1.0780606,0.0,0.96529704,1.37140397],[0.53741028,0.58863967,0.96529704,0.0,0.44501955],[0.87113533,0.91899559,1.37140397,0.44501955,0.0]])))
console.log(format(f([[0.0,41.9519,21.89390815,108.37048253,91.40006121,49.35063671,82.20983622,83.69080223,80.39436793,86.5204431,91.24484876,22.32327813,99.5351474,72.1001264,71.98278813,99.8621559,104.59071383,108.61475753,94.91576952,93.20212636],[41.9519,0.0,24.33770482,144.67214389,132.28290899,49.12079288,85.34321428,117.39095617,103.60848008,79.67795144,69.52024038,42.65007733,105.60007249,110.50120501,89.92218111,60.03623019,133.61394005,76.26668715,130.54041305,122.74547069],[21.89390815,24.33770482,0.0,130.04213984,112.98940283,54.26427666,71.35378232,104.72088677,81.67425703,90.26668791,71.13288376,18.74250061,109.87223765,93.96339767,69.46698314,84.37362794,124.38527485,98.82541733,116.43603102,113.07526035],[108.37048253,144.67214389,130.04213984,0.0,37.8990613,111.2161525,176.70411028,28.99007398,149.1355788,124.17549005,198.6298252,126.02950495,101.55746829,37.24713176,152.8114446,189.29178553,34.96711005,180.83483984,14.33728853,35.75999058],[91.40006121,132.28290899,112.98940283,37.8990613,0.0,111.05881157,147.27385449,44.12747289,115.00173099,134.19476383,175.9860033,104.1315771,120.19673135,27.75062658,120.90347767,184.88952087,65.64187459,183.20903265,36.35677531,60.34864715],[49.35063671,49.12079288,54.26427666,111.2161525,111.05881157,0.0,125.59451494,82.23823276,129.68328938,37.23819968,118.38443321,68.15130552,56.84347674,84.29966837,120.38742076,78.30380948,91.88522811,72.15031414,97.00421525,82.23460459],[82.20983622,85.34321428,71.35378232,176.70411028,147.27385449,125.59451494,0.0,158.1002588,45.08950594,161.43320938,50.02998891,59.93581537,180.43028005,139.95387244,30.1390519,133.42262669,182.2085151,158.47101132,165.61965338,170.96891788],[83.69080223,117.39095617,104.72088677,28.99007398,44.12747289,82.23823276,158.1002588,0.0,136.48099476,96.57856065,174.901291,103.29640959,77.53059476,22.95598599,137.23185588,160.37639016,26.14552185,152.04872054,14.96145727,17.29636403],[80.39436793,103.60848008,81.67425703,149.1355788,115.00173099,129.68328938,45.08950594,136.48099476,0.0,166.89727482,92.90019808,63.53459104,177.66159356,115.1228903,16.7609065,160.79059188,162.35278463,179.82760993,140.44928488,151.9058635],[86.5204431,79.67795144,90.26668791,124.17549005,134.19476383,37.23819968,161.43320938,96.57856065,166.89727482,0.0,148.39351779,105.1934756,34.72852943,106.44495924,157.55442606,83.19240274,96.09890812,61.77726814,111.24915274,89.68625779],[91.24484876,69.52024038,71.13288376,198.6298252,175.9860033,118.38443321,50.02998891,174.901291,92.90019808,148.39351779,0.0,72.71434547,175.07913091,161.59035051,76.3634308,96.89392413,195.433818,127.21259331,185.63246606,184.09218079],[22.32327813,42.65007733,18.74250061,126.02950495,104.1315771,68.15130552,59.93581537,103.29640959,63.53459104,105.1934756,72.71434547,0.0,121.04924013,88.90999601,52.48935172,102.51264644,125.51831504,117.54806623,113.26375241,114.12813777],[99.5351474,105.60007249,109.87223765,101.55746829,120.19673135,56.84347674,180.43028005,77.53059476,177.66159356,34.72852943,175.07913091,121.04924013,0.0,93.63052717,171.17130953,117.77417844,69.1477611,95.81237385,90.62801636,65.7996984],[72.1001264,110.50120501,93.96339767,37.24713176,27.75062658,84.29966837,139.95387244,22.95598599,115.1228903,106.44495924,161.59035051,88.90999601,93.63052717,0.0,117.17351252,159.88686894,48.89223072,156.34374083,25.76186961,40.13509273],[71.98278813,89.92218111,69.46698314,152.8114446,120.90347767,120.38742076,30.1390519,137.23185588,16.7609065,157.55442606,76.3634308,52.48935172,171.17130953,117.17351252,0.0,145.68608389,162.51692098,166.12926334,142.8970605,151.6440003],[99.8621559,60.03623019,84.37362794,189.29178553,184.88952087,78.30380948,133.42262669,160.37639016,160.79059188,83.19240274,96.89392413,102.51264644,117.77417844,159.88686894,145.68608389,0.0,169.4299171,33.39882791,175.00707479,160.25054951],[104.59071383,133.61394005,124.38527485,34.96711005,65.64187459,91.88522811,182.2085151,26.14552185,162.35278463,96.09890812,195.433818,125.51831504,69.1477611,48.89223072,162.51692098,169.4299171,0.0,156.08760216,29.36259602,11.39668734],[108.61475753,76.26668715,98.82541733,180.83483984,183.20903265,72.15031414,158.47101132,152.04872054,179.82760993,61.77726814,127.21259331,117.54806623,95.81237385,156.34374083,166.12926334,33.39882791,156.08760216,0.0,167.00907734,148.3962894],[94.91576952,130.54041305,116.43603102,14.33728853,36.35677531,97.00421525,165.61965338,14.96145727,140.44928488,111.24915274,185.63246606,113.26375241,90.62801636,25.76186961,142.8970605,175.00707479,29.36259602,167.00907734,0.0,25.82164171],[93.20212636,122.74547069,113.07526035,35.75999058,60.34864715,82.23460459,170.96891788,17.29636403,151.9058635,89.68625779,184.09218079,114.12813777,65.7996984,40.13509273,151.6440003,160.25054951,11.39668734,148.3962894,25.82164171,0.0]])))
```

### How?

Let ***di,j*** be the input and ***xi***, ***yi*** be the expected output.

By the challenge rules, we know that:

* For any pair ***(i, j)***: ***di,j = √((xi \- xj)² + (yi \- yj)²)***
* ***x0 = y0 = y1 = 0***

We can immediately deduce that:

1. ***x1 = d0,1***
2. ***d0,j = √((x0 \- xj)² + (y0 \- yj)²) = √(xj² + yj²)***
***d0,j² = xj² + yj²***
3. ***d1,j = √((x1 \- xj)² + (y1 \- yj)²) = √((x1 \- xj)² + yj²)***
***d1,j² = (x1 \- xj)² + yj² = x1² + xj² + 2x1xj \+ yj² = d0,1² + xj² + 2d0,1xj \+ yj²***

**Computing *xj***

By using 2 and 3, we get:

***xj² - (d0,1² + xj² - 2d0,1xj) = d0,j² - d1,j²***

Which leads to:

> ***xj = (d0,j² - d1,j² + d0,1²) / 2d0,1***

**Computing *yj***

Now that ***xj*** is known, we have:

***yj² = d0,j² - xj²***

Which gives:

> ***yj = ±√(d0,j² - xj²)***

We determine the sign of each ***yj*** by simply trying all possible combinations until we match the original distances. We also have to make sure that we have ***y2 \> 0***.

We do that by using the bitmask ***k*** where ***1***'s are interpreted as positive and ***0***'s are interpreted as negative. We start with ***k = 7*** (***111*** in binary) and add ***8*** at each iteration. This way, positive values of ***yj*** are guaranteed to be selected for ***0 ≤ j ≤ 2***. (We could start with ***k = 4*** just as well, because ***y0 = y1 = 0*** anyway. But using ***7*** prevents negative zeros from appearing.)

# Answer
> 3 votes
# , ~~227~~ ~~215~~ ~~209~~ ~~176~~ 169 bytes

```
function(d){x=y=c(0,0)
x[2]=a=d[1,2]
d=d^2
i=3:nrow(d)
D=d[1,i]
x[i]=(D+a^2-d[2,i])/2/a
y[3]=e=sqrt(d[1,3]-x[3]^2)
y[i]=(D-d[3,i]+x[3]^2+e^2-2*x[3]*x[i])/2/e
Map(c,x,y)}

```

Try it online!

Once upon a time, I took a course in Computational Geometry. I'd like to say that helped, but I clearly learned nothing.

Input is an R matrix, with the output a list of 2-element vectors `(x,y)` (which is closer to the spec *and* saves bytes).

The problem here is, of course, the first three points. Once you fix three points, you can compute all the others based on those.

I just used a bit of algebra to simplify things and then noticed that since I'm only using the first 3 points to solve for the others, this all vectorized very neatly.

Outgolfed by flodel

# Answer
> 2 votes
# JavaScript (ES7), ~~140~~ ~~139~~ ~~126~~ ~~121~~ ~~118~~ 117 bytes

*Saved 1 byte thanks to @Giuseppe.*

```
/* this line for testing only */ f =
D=>D.map((d,n)=>n>1?(y=d[0]**2,D[n]=x=(y-d[1]**2)/X/2+X/2,y-=x*x,[x,y**.5*(y>d[2]**2-(x-D[2])**2||-1)]):[X=n*d[0],0])
```

```
<!-- HTML for testing only --><textarea id="i" oninput="test()">[[0.0, 0.0513, 1.05809686, 0.53741028, 0.87113533], [0.0513, 0.0, 1.0780606, 0.58863967, 0.91899559], [1.05809686, 1.0780606, 0.0, 0.96529704, 1.37140397], [0.53741028, 0.58863967, 0.96529704, 0.0, 0.44501955], [0.87113533, 0.91899559, 1.37140397, 0.44501955, 0.0]]</textarea><pre id="o"></pre><script>window.onload=test=function(){try{document.querySelector("#o").innerHTML=JSON.stringify(f(JSON.parse(document.querySelector("#i").value)))}catch(e){}}</script>
```

Works somewhat like my Python answer. Returning `[x,y]` pairs turned out much shorter than separate X and Y lists in JS. Overwrites the argument list, so don't use it as input multiple times.

# Answer
> 2 votes
# Mathematica, 160 bytes

```
(s=Table[0{,},n=Tr[1^#]];s[[2]]={#[[1,2]],0};f@i_:=RegionIntersection~Fold~Table[s[[j]]~Circle~#[[j,i]],{j,i-1}];s[[3]]=Last@@f@3;Do[s[[i]]=#&@@f@i,{i,4,n}];s)&

```

The program use built-in `RegionIntersection` to calculate intersection point of circles. Program requires exact coordinate to work.

This assumes `RegionIntersection` always make the point with higher y-coordinate the last one in its result if the x-coordinate is equal. (at least it is true on Wolfram Sandbox)

For some reason `RegionIntersection` doesn't work if there is too many circles in its input so I have to process each pair once by using `Fold`.

Demonstrate screenshot:

---
Tags: code-golf, geometry
---


title: Triangles in a tetrahedron

text:
# Question
Title: Triangles in a tetrahedron
The goal of this challenge is to extend the OEIS sequence A334581.

> Number of ways to choose \\$3\\$ points that form an equilateral triangle from the \\$\binom{n+2}{3}\\$ points in a regular tetrahedral grid of side length \\$n\\$.

The sequence begins `0, 0, 4, 24, 84, 224, 516, 1068, ...`

# Example

For example, if we take side lengths of \\$n=4\\$, as in the example below, there are \\$\binom{4+2}{3} = 20\\$ vertices and \\$\binom{20}{3} = 1140\\$ ways to choose three of them. Of these, there are \\$84\\$ ways to choose \\$3\\$ vertices that form an equilateral triangle:

# Challenge

This challenge will have you compute as many terms of the sequence `[A334581(0), A334581(1), ...]` that you can in ten minutes, as measured on my machine.

# Answer
# Rust, \\$A(1), \dotsc, A(1375)\\$ in 10 minutes

Unofficial score on Ryzen 7 1800X (8 cores/16 threads). Build with `cargo build --release` and run with `time target/release/tetrahedron n` to compute \\$A(1), \dotsc, A(n)\\$.

This runs in \\$O(n^4)\\$ time. (So to estimate a good value of \\$n\\$ for your CPU, first time it for some smaller \\$n\\$, then multiply that \\$n\\$ by a factor of \\$\left(\frac{600\\,\mathrm{s}}{t}\right)^{1/4}\\$.)

### How it works

Any triangle that fits inside a tetrahedron of minimal side \\$k \le n\\$ may be translated inside a tetrahedron of side \\$n\\$ in exactly \\$\binom{n - k + 3}{3}\\$ ways. This means we only need to find it in one position, leaving six free parameters. Two of these parameters may be computed from the other four (up to a sign choice) if the triangle is to be equilateral, so we only need to loop over an \\$O(n^4)\\$ space.

### `src/main.rs`

```
use rayon::prelude::*;

fn get_counts(n: i64, a0: i64) -> Vec<i64> {
    let mut c = vec![0; n as usize];
    let a0a0 = a0 * a0;
    for a1 in if a0 == 0 { 1 } else { -n + 1 }..n {
        let d = a0a0 + a1 * a1;
        let m = n - a0.abs() - a1.abs();
        for a2 in if m > 0 {
            -n + 2 - (m & 1)..n
        } else {
            -n - m + 2..n + m
        }
        .step_by(2)
        {
            let d = d + a2 * a2;
            let r = 2 * (a0a0 - d);
            if r == 0 {
                continue;
            }
            for b0 in a0..n {
                let pp = d * (3 * d - 4 * (a0a0 + b0 * (b0 - a0)));
                if pp < 0 {
                    break;
                }
                let p = (pp as f64).sqrt() as i64;
                if p * p != pp {
                    continue;
                }
                let q = 2 * a0 * b0 - d;
                let mut check = |p: i64| {
                    let b1r = p * a2 + q * a1;
                    if b1r % r != 0 {
                        return;
                    }
                    let b1 = b1r / r;
                    let b2r = -p * a1 + q * a2;
                    if b2r % r != 0 {
                        return;
                    }
                    let b2 = b2r / r;
                    if (b0, b1, b2) <= (a0, a1, a2) || b0 + b1 + b2 & 1 != 0 {
                        return;
                    }
                    let t = 0.max(a0 + a1 + a2).max(b0 + b1 + b2)
                        + 0.max(-a0 - a1 + a2).max(-b0 - b1 + b2)
                        + 0.max(-a0 + a1 - a2).max(-b0 + b1 - b2)
                        + 0.max(a0 - a1 - a2).max(b0 - b1 - b2);
                    if t >= 2 * n {
                        return;
                    }
                    c[t as usize / 2] += 1;
                };
                check(p);
                if p != 0 {
                    check(-p);
                }
            }
        }
    }
    c
}

fn add_vec(c0: Vec<i64>, c1: Vec<i64>) -> Vec<i64> {
    c0.into_iter().zip(c1).map(|(x0, x1)| x0 + x1).collect()
}

fn main() {
    let n = std::env::args().skip(1).next().expect("missing argument");
    let n = n.parse().expect("not an integer");
    let counts = (0..n)
        .into_par_iter()
        .map(|a0| get_counts(n, a0))
        .reduce(|| vec![0; n as usize], add_vec);
    let (mut d0, mut d1, mut d2, mut d3) = (0, 0, 0, 0);
    for (i, x) in (1..).zip(counts) {
        d3 += x;
        d2 += d3;
        d1 += d2;
        d0 += d1;
        println!("{} {}", i, d0);
    }
}

```

### `Cargo.toml`

```
[package]
name = "tetrahedron"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[dependencies]
rayon = "1.3.0"

```

Try it online! (Parallelism removed for TIO.)
> 8 votes

# Answer
# C++, all up to 40 in ten minutes

Runs in \\$O(n^9)\\$ time complexity (fortunately, it seems to be divided by at least 36 and it's also multi-threaded). I tested on Ubuntu 19.10 on AMD Ryzen 5 2600 (12 threads), tested with `clang++ -Ofast -march=native -flto -no-pie -fopenmp` and ran with `timeout 600 ./a.out`.

Code:

```
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstring>
#include <complex>
#include <streambuf>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <list>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <unordered_set>
#include <thread>

struct pt3
{
    short x, y, z;
    bool operator < (const pt3& rhs) const
    {
        return std::tie(x, y, z) < std::tie(rhs.x, rhs.y, rhs.z);
    }
    pt3 operator - (const pt3& rhs) const
    {
        return {short(x - rhs.x), short(y - rhs.y), short(z - rhs.z)};
    }
    int sqdist() const
    {
        return int(x)*int(x) + int(y)*int(y) + int(z)*int(z);
    }
};
int solve(int n)
{
    //the several lines below took a lot of tinkering-until-it-works
    std::set<pt3> pt3s;
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
    {
        if(i+j+k >= n) continue;
        pt3 pt { short(i+j), short(j+k), short(i+k) };
        pt3s.insert(pt);
    }
    std::vector<pt3> points; //copy into a vector, they're much faster for this
    for(pt3 el : pt3s) points.push_back(el);

    //printf("n=%d, ps=%d\n", n, points.size());
    int64_t ans = 0;
#pragma omp parallel for schedule(guided) reduction(+:ans)
    for(int i = 0; i < points.size(); i++)
    for(int j = i + 1; j < points.size(); j++)
    for(int k = j + 1; k < points.size(); k++)
    {
        pt3 a = points[i], b = points[j], c = points[k];
        //consider pairwise distances
        pt3 p1 = a-b, p2 = a-c, p3 = b-c; //33% of all time
        int d1 = p1.sqdist(), d2 = p2.sqdist(), d3 = p3.sqdist(); //another 33% of all time
        if(d1 != d2 || d1 != d3) continue;
        ans++;
        //printf("%d %d %d; %d %d %d; %d %d %d\n", p1.x, p1.y, p1.z, p2.x, p2.y, p2.z, p3.x, p3.y, p3.z);
    }
    return ans;
}
int main()
{
    for(int i = 1;; i++)
    {
        int ans = solve(i);
        printf("n=%d: %d\n", i, ans);
    }
}

```

Output:

```
n=1: 0
n=2: 4
n=3: 24
n=4: 84
n=5: 224
n=6: 516
n=7: 1068
n=8: 2016
n=9: 3528
n=10: 5832
n=11: 9256
n=12: 14208
n=13: 21180
n=14: 30728
n=15: 43488
n=16: 60192
n=17: 81660
n=18: 108828
n=19: 142764
n=20: 184708
n=21: 236088
n=22: 298476
n=23: 373652
n=24: 463524
n=25: 570228
n=26: 696012
n=27: 843312
n=28: 1014720
n=29: 1213096
n=30: 1441512
n=31: 1703352
n=32: 2002196
n=33: 2341848
n=34: 2726400
n=35: 3160272
n=36: 3648180
n=37: 4195164
n=38: 4806496
n=39: 5487792
n=40: 6244992

```
> 4 votes

# Answer
# JavaScript (ES7), a(30) in ~50 seconds1

*1: when run locally on my laptop*

A very simple algorithm.

```
function count(n) {
  const r0 = (8 / 3) ** 0.5, r1 = 2 / 3, r2 = 3 ** 0.5;
  let cnt = 0;

  for(let z1 = 0; z1 < n; z1++)
  for(let Z1 = z1 * r0,
          y1 = 0; y1 <= z1; y1++)
  for(let Y1 = (y1 - z1 * r1) * r2,
          x1 = 0; x1 <= y1; x1++)
  for(let X1 = 2 * x1 - y1,
          z2 = z1; z2 < n; z2++)
  for(let Z2 = z2 * r0,
          y2 = z2 > z1 ? 0 : y1; y2 <= z2; y2++)
  for(let Y2 = (y2 - z2 * r1) * r2,
          x2 = z2 > z1 || y2 > y1 ? 0 : x1 + 1; x2 <= y2; x2++)
  for(let X2 = 2 * x2 - y2,
          S1 = (X1 - X2) ** 2 + (Y1 - Y2) ** 2 + (Z1 - Z2) ** 2,
          z3 = z2; z3 < n; z3++)
  for(let Z3 = z3 * r0,
          y3 = z3 > z2 ? 0 : y2; y3 <= z3; y3++)
  for(let Y3 = (y3 - z3 * r1) * r2,
          x3 = z3 > z2 || y3 > y2 ? 0 : x2 + 1; x3 <= y3; x3++) {
    let X3 = 2 * x3 - y3,
        S2 = (X1 - X3) ** 2 + (Y1 - Y3) ** 2 + (Z1 - Z3) ** 2;

    if(Math.abs(S1 - S2) < 1e-9) {
      let S3 = (X2 - X3) ** 2 + (Y2 - Y3) ** 2 + (Z2 - Z3) ** 2;

      if(Math.abs(S1 - S3) < 1e-9) {
        cnt++;
      }
    }
  }
  return cnt;
}

```

Try it online!
> 3 votes

---
Tags: sequence, geometry, combinatorics, grid, fastest-code
---


title: Rubik's Snakes! (Part 1)

text:
# Question
Title: Rubik's Snakes! (Part 1)
The Rubik's Snake (or Rubik's Twist) is a toy consisting of several triangular prisms strung together in a line in such a way that the pieces can be rotated about one another in 90 degree turns.

Any snake can be described by an ordered sequence of rotations (format described below). Some sequences do not describe physically possible, "valid", snakes because they would cause the pieces to self-intersect. Some sequences describe "cyclic" snakes, which happens when the open square faces of the first and last piece of the snake meet.

Given a sequence of rotations, your task is to output whether the snake is "valid" and output whether the snake is "cyclic".

# Input

A sequence of length *n-1* describes a snake with *n* pieces. The index of the sequence describes the state of the interface between two pieces at that index, i.e., how those two pieces are rotated. Any alphabet with 4 letters can be used to describe the possible rotations.

Here we will use:

* `0` \- No rotation
* `1` \- 90 degree rotation
* `2` \- 180 degree rotation
* `3` \- 270 degree rotation

Note that this implies some chirality. For the demos below I use a left-hand rule but the choice is arbitrary as long as you are consistent.

Here are some basic examples:

`00000000000` \- A straight, unfolded Rubik's Mini Snake (12 pieces)

`0220` \- A simple 5 piece snake

`11111111111111111111111` \- A Rubik's Snake (24 pieces) consisting only of 90 degree clockwise turns

`13131` \- A "cyclic" snake that mixes clockwise and counterclockwise turns

`20220200022020020220002` \- A classic Rubik's Snake dog design without symmetry

`222` \- The shortest "cyclic" snake

`13133311131333111313331` \- A more elaborate "cyclic" design on the Rubik's Snake

`0022200` \- Not a "valid" snake because it self-intersects

`00031310000` \- A more elaborate invalid snake

`0003131000313` \- Snakes which are not "valid" may still be "cyclic"

`2222222` \- Another invalid snake which is still "cyclic" (deceptively similar to `222`, which is valid)

The first image is the "Twin Peaks" pattern as found on Wikipedia (the pattern was found there, the images here are my original work). It is described by `10012321211233232123003` and is both "valid" and "cyclic".

Finally, a bonus 240 piece Rubik's Snake (yes, they actually sell these) `01113133131131331311313330020013000000310000003100000013000000130022031000013211001302020031002203100001300001300003121102022011001300130031001300310031001121300003323100000013211000031000031000220000130000003100000031002022022031233213002`

**Caveats**

* By default, the input is a string consisting of `0`s, `1`s, `2`s, and `3`s
* Must be able to handle all sequences of length 3 or greater (*n* \>= 4)
* If it is more practical or golf-able to handle a list of characters or a list of integers 0 thru 3, you may do so as long as it is consistent. Just be sure to specify in your answer.

# Output

Given a sequence as described above, your program should ouput whether the sequence describes a snake that is:

* "valid" and "cyclic" (`[true, true]`)
* "valid" but not "cyclic" (`[true, false]`)
* not "valid" but "cylcic" (`[false, true]`)
* not "valid" and not "cyclic" (`[false, false]`)

**Caveats**
The format of your output need not be exactly `[bool, bool]`, as long as:

* There are exactly 4 possible outputs
* Each possible output uniquely corresponds exactly 1-to-1 with `[true, true]`, `[true, false]`, `[false, true]`, `[false, false]` for `[valid, cyclic]`
* Your chosen format is consistent for each input
* Standard loopholes. Ask for clarification in comments

For example, if you want your outputs to be `"alice"`, `bob`, `37`, `[]`, you may do so as long as you specify what that means in your answer.

# Examples

```
INPUT=====================+=OUTPUT==========
Sequence                  | Valid  | Cyclic
==========================+========+========
00000000000               | true   | false
0220                      | true   | false
11111111111111111111111   | true   | false
13131                     | true   | true
20220200022020020220002   | true   | false
222                       | true   | true
13133311131333111313331   | true   | true
0022200                   | false  | false
00031310000               | false  | false
0003131000313             | false  | true
2222222                   | false  | true
10012321211233232123003   | true   | true
                          |        |
0111313313113133131131333 |        |
  00200130000003100000031 |        |
  00000013000000130022031 |        |
  00001321100130202003100 |        |
  22031000013000013000031 | true   | true
  21102022011001300130031 |        |
  00130031003100112130000 |        |
  33231000000132110000310 |        |
  00031000220000130000003 |        |
  10000003100202202203123 |        |
  3213002                 |        |
==========================+========+========

```

---

This is `code-golf`, so shortest answer wins!

# Answer
# Python 2, ~~217 212 198~~ 194 bytes

```
from numpy import*
A=any
d,t,_=eye(3)
p=b=t
v=0
S=[]
for m in input():S+=(p,d,t),;exec"t=cross(t,d);"*m;p,d,t=p+d,t,d;v|=A([all(p==P)*A([d+D,t+T])*A([d-T,t-D])for P,D,T in S])
print v,A([p,d-b])

```

Try it online! or Verify all test cases!

*-6 bytes thanks to @dingledooper!*

**Input**: A list of integers from `STDIN`
**Output**: A number and a boolean, printed to `STDOUT`.
The number is `0` if the snake is valid, `1` otherwise.
The boolean is `False` if the snake is cyclic, `True` otherwise.

### Big idea:

Each snake piece fits exactly into half of a unit cube in a 3D grid. There are 12 possible orientations of a piece, corresponding to 6 ways of slicing a cube in half diagonally.

Thus, each snake piece can be characterized by the `x, y, z` coordinates of the cube containing it, and the orientation of the piece within the cube.

Now that we have a way to store each piece's info, we can build the snake, then detect self-intersection and cycle.

If 2 pieces occupy the same cube, they intersect unless the 2 pieces are exactly opposite of each other in the cube:

Example orientations that can coexists within the same cube. Image taken from here

### Details

**Snake building**

A simple way to characterize the orientation of a piece is with 2 directions: the "in" direction \\$t\\$, and "out" direction \\$d\\$. \\$d\\$ and \\$t\\$ are always axis-aligned (since they are always perpendicular to a face of a cube).

For each piece, we store the cube position \\$p\\$ and the 2 directions \\$d, t\\$. This makes it easy to figure out the position and orientation of the next piece. Consider the piece \\$(A)\\$ in the figure above. If the move is \\$0\\$ (no turn), then the next piece will be \\$(B)\\$. If the move is \\$(1)\\$ (90 degree turn), then the next piece will be \\$(C)\\$. We can see that if the current piece is \\$(p\_1, d\_1, t\_1)\\$ and the number of turns is \\$m\\$, then the next piece is: $$ p\_2 = p\_1 + d\_1 $$ $$ t\_2 = d\_1 $$ $$ d\_2 = t\_1 \text{ rotated } m \text{ times around } d\_1 $$

**Cycle detection**

If the snake is cyclic, then the last and first piece must be connected. This means that the "out" direction of the last piece must be the same as the "in" direction of the first piece, and their coordinates must be adjacent in that direction.

If the first piece has the default value: \\$p=(0,0,0), t=(0,1,0)\\$, then the last piece must have the value: \\$p=(0,-1,0), d=(0,1,0)\\$.

**Self-intersection detection**

If 2 pieces intersect each other, then the following must be true:

* They are in the same cube: \\$p\_1 = p\_2\\$
* Their orientations are not opposite of each other.

The orientations of 2 pieces are opposite of each other when one of the following happens:

* \\$d\_1 = -d\_2\\$ and \\$t\_1 = -t\_2\\$
* or \\$d\_1 = t\_2\\$ and \\$t\_1 = d\_2\\$
> 7 votes

---
Tags: code-golf, math, geometry, combinatorics
---


# Question
Title: Perfect scores in Martian rules football
## Story

Martians have been observing Aussie rules football matches from space with great curiosity. Having totally fallen in love with the game, they have been inspired to start their very own football league. However, being dim-witted creatures, they are unable to comprehend the scoring system.\*

We know that in Aussie rules, a *goal* is worth 6 points (\\$G=6\\$) and a *behind* is worth 1 point (\\$B=1\\$). The Martians are cluey enough to work out that there are two types of scores, but not smart enough to realise that they can deduce the point values of these scores by analysing match outcomes. Undeterred, the International Olympus Mons Committee decrees that in all Martian rules football matches, the point values for goals and behinds (i.e. \\$G\\$ and \\$B\\$) will be chosen at random.

## 'Perfect' scores

When \\$G = 6\\$ and \\$B = 1\\$ (as in Aussie rules), there are exactly four integer pairs \\$\[g,b\]\\$ such that a team with \\$g\\$ goals and \\$b\\$ behinds has a score of \\$gb\\$ points. We will refer to \\$\[g,b\]\\$ pairs that satisfy $$gG+bB=gb$$ as *perfect* scores. The four perfect scores in Aussie rules are \\$\[g,b\]=\[2,12\]\\$, \\$\[3,9\]\\$, \\$\[4,8\]\\$, and \\$\[7,7\]\\$.

## Challenge

Given two strictly positive integers \\$G\\$ and \\$B\\$ representing the point values of goals and behinds in a Martian rules football match, write a program or function that determines all possible perfect scores for that match. Rules:

* Input may be taken in any convenient format (pair of integers, list, string, etc.). You may *not* assume that \\$G\>B\\$.
* Output may also be in any format, provided that the \\$\[g,b\]\\$ pairs are unambiguously identifiable (e.g. successive elements in a list or string). The order of pairs does not matter. You may output pairs in \\$\[b,g\]\\$ order instead provided that you state this in your answer. You may *not* output the total scores (the products \\$gb\\$) instead, because in general there are multiple non-perfect ways to achieve the same total score.
* Your program/function must terminate/return in finite time.

This is : the shortest submission (in bytes) in each language wins.

## Test cases

Input -\> Output

```
[6, 1] -> [[2, 12], [3, 9], [4, 8], [7, 7]]
[6, 2] -> [[3, 18], [4, 12], [5, 10], [6, 9], [8, 8], [14, 7]]
[1, 1] -> [[2, 2]]
[1, 6] -> [[7, 7], [8, 4], [9, 3], [12, 2]]
[7, 1] -> [[2, 14], [8, 8]]
[7, 5]  -> [[6, 42], [10, 14], [12, 12], [40, 8]]
[13, 8] -> [[9, 117], [10, 65], [12, 39], [16, 26], [21, 21], [34, 17], [60, 15], [112, 14]]

```

---

* This problem never, *ever*, occurs on Earth.

# Answer
> 6 votes
# 05AB1E, 10 bytes

```
>PLãʒ*OyPQ

```

Try it online or verify all test cases.

**Explanation:**

```
>           # Increase both values in the (implicit) input-pair by 1
 P          # And take the product of those
  L         # Pop and push a list in the range [1, (G+1)*(B+1)]
   ã        # Create all possible pairs by taking the cartesian product with itself
    ʒ       # Filter those pairs [g,b] by:
     *      #  Multiply it with the (implicit) input-pair at the same positions:
            #   [G,B] * [g,b] will result in [Gg,Bb]
      O     #  Sum those: Gg+Bb
       yP   #  Take the product of the current pair: gb
         Q  #  And check that both values are the same: Gg+Bb == gb
            # (after which the result is output implicitly)

```

The last test case no longer times out by using an upper bound of \\$(G+1)\times(B+1)\\$ instead of my initial \\$(2^G+2^B)\\$ (byte count remains the same). Make sure to upvote *@SurculoseSputum*'s Python answer for providing this mathematical upper bound.

# Answer
> 6 votes
# Python 2, ~~85 81~~ 78 bytes

```
G,B=input()
R=range(~G*~B)
print[(g,b)for g in R for b in R if g*G+b*B==g*b>0]

```

Try it online! or Check all test cases!

A program that reads 2 integers `G, B` from `STDIN`, and prints to `STDOUT` all pairs of `g,b`.

The upper bounds of \\$g\\$ and \\$b\\$ are: $$g \leq B(G+1)$$ $$b \leq G(B+1)$$ or as used in the program: \\$ g, b \< (G+1)(B+1) \\$

This is derived as follow:

$$ gG + bB = gb $$ $$ g(b-G) = bB $$ $$ \frac{g}{B} = \frac{b}{b-G} $$ $$ \frac{g}{B} = 1 + \frac{G}{b-G} \leq 1 + G $$ $$ g \leq B(1 + G) $$

# Answer
> 4 votes
# Python 2, 58 bytes

```
lambda G,B:[(i+B,G*B/i+G)for i in range(1,G<<B)if G*B%i<1]

```

Try it online!

We can write \\$gG+bB=gb\\$ as $$(g-B)(b-G)=GB,$$ that is, \\$ij=GB\\$ with $$g=i+B$$ $$b=j+G$$ So, the outputs \\$(g,b)\\$ are just the divisor pairs \\$(i,j)\\$ multiplying to \\$GB\\$, but shifted up by the input values:

$$(g,b)\in\\{(i+B,j+G) \mid ij=GB; \thinspace i,j\in \mathbb{Z}^{+}\\} $$

Note that negative \\$(i,j)\\$ are not included because they produce a negative \\$g\\$ or \\$b\\$.

The code is mostly straightforward, iterating over all potential factors \\$i\\$ of \\$GB\\$, taking those that are exact divisor, to produce the \\$(g,b)\\$ given by the formula. We could have looped over both \\$i\\$ and \\$j\\$ and take those with \\$ij=GB\\$, but the length of writing a second loop makes this unviable in Python, though other languages may prefer this option.

We need to test all potential divisors \\$i\\$ in the closed interval \\$\[1,GB\]\\$, excluding zero to avoid a modulo-by-zero error. For the half-open upper bound for `range`, we write `G<<B` to make some value strictly bigger than \\$GB\\$, noting that \\$G \cdot 2^B \geq G(B+1) \> GB \\$. Despite this clunky `range` call, it seems longer to replace the iteration by a recursive function.

As a program:

**Python 2, 60 bytes**

```
G,B=input()
P=i=G*B
while i:
 if P%i<1:print i+B,P/i+G
 i-=1

```

Try it online!

# Answer
> 3 votes
# Python 3.8 (pre-release), 59 bytes

A recursive port of the below.

```
def f(G,B,i=1):m=G*B;m%i or print(i+B,G+m/i);i<m<f(G,B,i+1)

```

Try it online!

# Python 2, ~~64~~ 60 bytes

Takes the two integers \\$ G \\$ and \\$ B \\$ as input, and outputs the integer solutions in \\$ \[g, b\] \\$ order, each on a new line.

```
G,B=input()
n=m=G*B
exec'if m%n<1:print n+B,G+m/n\nn-=1\n'*n

```

Try it online!

We first isolate \\$ b \\$, giving us:

$$ gG + bB = gb $$ $$ gG = gb - bB $$ $$ gG = b(g - B) $$ $$ \frac{gG}{g - B} = b $$

All we need to do now is find values of \\$ g \\$ that produce a positive integer solution when plugged into the formula. We also get that \\$ g \leq B + GB \\$ from Surculose Sputum's answer, and that \\$ B \< g \\$, otherwise it would produce a negative solution because of the denominator.

One thing which I did in my program is subtract \\$ B \\$ from \\$ g \\$. The formula then becomes

$$ \frac{(g + B)G}{g} $$

and the inequality becomes \\$ 0 \< g \leq GB \\$. This change turned out to slightly improve the byte count.

# Answer
> 2 votes
# Charcoal, ~~32~~ ~~30~~ 27 bytes

```
ＩＥΦΠθ¬﹪Πθ⊕ι⟦⁺⊕ι§θ¹⁺÷Πθ⊕ι§θ⁰

```

Try it online! Link is to verbose version of code. Takes input as a list. I converted my 30 byte version (below) to take input as a list, which ends up making it behave like @xnor's answer. Explanation:

```
   Πθ                       G*B
  Φ                         Filter over implicit range
         ⊕ι                 g-B
     ¬﹪                     Divides
       Πθ                   G*B=G*g-G*(g-B)
 Ｅ                          Map over filtered values
           ⟦                Tuple of
            ⁺⊕ι§θ¹          (g-B)+B=g
                  ⁺÷Πθ⊕ι§θ⁰ G*B/(g-B)+G=G*g/(g-B)=b
Ｉ                           Cast to string
                            Implicitly print

```

Previous 30-byte version:

```
ＮθＮηＩＥΦ…·¹×ηθ¬﹪×ηθι⟦⁺ιη÷×⁺ιηθι

```

Try it online! Link is to verbose version of code. The lower bound for `g` is `B+1` and the upper bound (as independently calculated by @SurculoseSputum) is `B(G+1)` so it simply remains to calculate those values where `b` is an integer. Explanation:

```
ＮθＮη

```

Input `G` and `B`.

```
ＩＥΦ…·¹×ηθ

```

Loop `i` from `1` to `BG`. This is equivalent to looping `g` from `B+1` to `B(G+1)`, where `g=i+B`.

```
¬﹪×ηθι

```

Filter on `b` being an integer. Edit: Saved 2 bytes by checking whether `i` divides `GB` rather than whether `b=gB/i=(G+i)B/i` is an integer.

```
⟦⁺ιη÷×⁺ιηθι

```

Output `g` and `b`.

# Answer
> 2 votes
# C (gcc), 84 bytes

```
b;g;f(B,G){for(b=0;++b<~B*~G;)for(g=0;++g<~B*~G;b*B+g*G-b*g||printf("%d %d ",b,g));}

```

Try it online!

Prints out the values of \\$b\\$ and \\$g\\$ separated by spaces.

Uses the upper bounds for \\$b\\$ and \\$g\\$ as calculated by Surculose Sputum in his Python answer.

# Answer
> 1 votes
# Pyth, 17 bytes

```
fq*FTs*VTQ^Sy*FQ2

```

Try it online!

Port of @KevinCruijssen's 05AB1E Answer, with a few modifications to make it more suitable for Pyth.

In particular, the upper bounds of

$$g \leq B(G+1)$$ $$b \leq G(B+1)$$

from @SurculoseSputum's answer have been used to derive that:

$$g,b \leq 2GB$$

```
fq*FTs*VTQ^Sy*FQ2
            y*FQ    Multiply G and B, then multiply by 2
           S        Range( 1, 2*GB )
          ^     2   Cartesian product of that range with itself
f                   Filter for elements (g,b) satisfying:
  *FT                g*b
 q                    equals
     s*VTQ            G*g + B*b

```

---

**Bonus**: Port of @xnor's Python answer (**21 bytes**)

```
AQVSJ*GHI!%JN+NH+G/JN

```

Try it online!

Outputs each pair `g,b` on two separate lines. I find this solution amusing because it contains only uppercase letters and operators.

# Answer
> 1 votes
# Erlang (escript), 61 bytes

Boring port of the Python answer. (To get me started.)

```
f(G,B)->[[I+B,G*B/I+G]||I<-lists:seq(1,G bsl B),G*B rem I<1].

```

Try it online!

---
Tags: code-golf, arithmetic, integer
---


title: Electoral votes from state name

text:
# Question
Title: Electoral votes from state name
Given a the name of a state of the United States as a string (with case), return the number of votes the state has in the Electoral College. Write a full program or function, and take input and output through any default I/O method.

A list of all inputs and outputs (source):

```
[['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], ['West Virginia', 5], ['Wisconsin', 10], ['Wyoming', 3]]

```

Any other input is undefined behavior. This is , so the shortest solution in bytes wins.

Hint: You probably shouldn't store all of the state names.

If you're solving this challenge with a builtin, please also write a solution without, for the sake of an interesting answer.

# Answer
> 9 votes
# Python 3, 137 bytes

```
lambda s:b"2F$&#+*&4#(#'*&$++&''0+)-/ &)$# #(0*W% *&4)$= ,   %.# = %#$"[sum(b'!!E$/!5.!!!&#"!!1_&!!$#<!./'[ord(c)%32]-32for c in s)-4]-32

```

Although not required by the challenge, this accepts case-insensitive state names. I computed parts of this hash function with GPerf.

# Answer
> 5 votes
# Python 2, 289 bytes

```
c="las,De,Mo,Da,Ve,Wy 3 Ha,Id,ai,Rh 4 eb,xi,st 5 ka,Io,Ka,pp,ev,U 6 ct,Ok,go 7 Ke,ui 8 Al,ad,Sou 9 ry,ta,ou,Wi 10 iz,nd,tt,ee 11 sh 12 Vi 13 Je 14 ro 15 Ge,ch 16 Oh 18 ll,yl 20 Fl,Yo 29 xa 38 if 55"
f=0
u=input()
for i in c.split():
 if f:print i;break
 f=any(j in u for j in i.split(','))

```

---

### Example

```
$ python2 test.py
"Tennessee"
11

$ python2 test.py
"California"
55

$ python2 test.py
"Rhode Island"
4

```

# Answer
> 3 votes
# JavaScript (Node.js),  ~~147 145~~  127 bytes

```
s=>Buffer("@>~;;F~<~;~?~~^~UL~~C~~?~<<@~EBB~B?~>~~~~AD>~A~=;~>=>H~~~C>A~BG<H;C<CoUJ~~=;L")[parseInt(s[8]+0+s,35)%561%263%80]-56

```

Try it online!

## How?

### Transforming the input string

In this paragraph, we temporarily assume that we're going to convert some transformation of the input string from base 36 to decimal.

We can't just pass the state name to `parseInt()` to turn it into a unique numeric identifier because some state names include a space that would cause the parsing to stop, whatever base is used. For instance, `"North Carolina"` and `"North Dakota"` would be both parsed as `"north"`.

Possible solutions:

* We could remove the space or replace it with another character. But this is a lengthy operation.
* We could pick 3 arbitrary letters. Any permutation of either `(s[2],s[4],s[6])` or `(s[0],s[4],s[8])` would work. This is better but still a bit lengthy.
* Another possible strategy is to prepend the 9th character to the full name. For instance, `"North Carolina"` is turned into `"rNorth Carolina"` and parsed as `"rnorth"`, while `"North Dakota"` is parsed as `"knorth"`.

The last strategy looks promising, but we have a problem with `"Michigan"` vs `"Missouri"`. When the length of a state is less than 9, `"undefined"` is inserted instead, leading to a rather long string which is likely to cause a loss of precision. That's why `"Michigan"` and `"Missouri"` are both parsed as `"undefinedmh000000"`, where `mh000000` is the rounded value of `mi......`.

Fortunately, we can fix that by doing:

```
s[8] + 0 + s

```

This time, when the 9th character is missing, it is turned into `undefined + 0 = NaN`. So, `"Michigan"` is parsed as `"nanmichiga8"` and `"Missouri"` is parsed as `"nanmissourk"` (only the last 'digit' is rounded).

### Choosing the base

With this transformation, we can use any base between 32 and 36. In base 32, the characters *w*, *x*, *y* and *z* cause the parsing to stop. But the states that contain these letters are still turned into unique values:

```
 State           | Turned into       | Parsed as
-----------------+-------------------+--------------
 "Arizona"       | "NaNArizona"      | "nanari"
 "Delaware"      | "NaNDelaware"     | "nandela"
 "Hawaii"        | "NaNHawaii"       | "nanha"
 "Iowa"          | "NaNIowa"         | "nanio"
 "Kentucky"      | "NaNKentucky"     | "nankentuck"
 "Maryland"      | "NaNMaryland"     | "nanmar"
 "New Hampshire" | "s0New Hampshire" | "s0ne"
 "New Jersey"    | "e0New Jersey"    | "e0ne"
 "New Mexico"    | "c0New Mexico"    | "c0ne"
 "New York"      | "NaNNew York"     | "nanne"
 "Pennsylvania"  | "a0Pennsylvania"  | "a0penns"
 "Texas"         | "NaNTexas"        | "nante"
 "Wyoming"       | "NaNWyoming"      | "nan"
 "West Virginia" | "g0West Virginia" | "g0"
 "Wisconsin"     | "n0Wisconsin"     | "n0"
 "Wyoming"       | "NaNWyoming"      | "nan"
 "Washington"    | "o0Washington"    | "o0"

```

See the full tables in base 32 to base 36

### Choosing the hash function

We can now try to brute-force a hash function that leads to the shortest possible lookup table.

I've actually tried many different things, but the pattern that worked best was:

```
parseInt(s[8] + 0 + s, B) % M0 % M1 % M2

```

with 32 ≤ B ≤ 36, 50 ≤ M0 \< 1000, 50 ≤ M1 \< M0 and 50 ≤ M2 \< M1.

This eventually led to:

```
parseInt(s[8] + 0 + s, 35) % 561 % 263 % 80

```

and a lookup string of 77 characters.

# Answer
> 2 votes
# JavaScript (ES6) ~~333~~ ~~331~~ ~~329~~ 223 characters

Many thanks to ETHproductions and Neil, 100+ characters thanks to both of you, and I haven't tried findIndex() yet :-)

```
s=>(d="0,;y\\>|Kb^6 |kn|xw|r?||8MD|hQ|EU|7|2||R|e||||F|||||||||G".split("|"),d[35]="",d[52]="3",d.map((a,j)=>{if(~a.indexOf(String.fromCharCode([...s].reduce((S,c)=>S*32+c.charCodeAt(),0)%153)))o=j}),o+3)

```

### Expanded version

(With \0xx instead of characters)

```
s => (
    d = "0,;y\\>|Kb^6\t|kn\x1D|\x05\x7F\x84x\bw|r\x12?|\x07\x98|8MD|\x93h\x8E\x11Q|\x8FEU\x1B|7|2|\v|R|\x92e||\x19||\x04F|||||||||\x94G".split("|"),
    d[35] = "\x13",
    d[52] = "3",
    d.map(
        (a,j) => {
            if(~a.indexOf(
                String.fromCharCode([...s].reduce(
                    (S,c)=>S*32+c.charCodeAt(),0)%153)
                ))
                o = j
        }
    ),
    o+3
)

```

## Approach:

### Preprocessing:

Calculate an hash of each state name and store them in an array where one dimension is the number of votes the state has.

### Processing:

Recalculate the hash and retrieve the information.

An hash of a state name is calculated with `s.split('').reduce((S,c)=>S*32+c.charCodeAt(0),0)%153`.

It transform "Iowa" in `(32^3*'I' + 32^2*'o' + 32*'w' + 'a')%153` (with ascii value for characters).

Why 32 and 153? Because after a few empiric tests those values minimize hashes without collision between states that have different number of votes.

I don't believe that it will be hard to do something shorter with a better approach but since I spent a few time on it ;).

# Answer
> 2 votes
# Retina, 210 bytes

```
Wi|Min|Mar|ri$
10
G|J|Mas|^Vi|rth C|Oh|Wa|ch
1
Ari|In|Ten
11
F|Y|gt
2
lv|is$
20
las|D|Mo|T|(1)r|g$
$1 3
H|R|Ma|Id|rs
4
al|if|eb|(1)a|V|Mex
$1 5
Ar|gi?a|Io|Ka|pi|Nev|U
6
cu|O
7
[KLx]|io$
8
Al|do|id|rk| C
9
T`Ll

```

The last line has a trailing space. Output contains a trailing newline. If that's a problem, it'll be one more byte

Version for all states has `m`` in few places to make it work with multiple lines.

Try it online!
Try it online with all states!

# Answer
> 1 votes
## Mathematica / Wolfram Language 235 bytes.

I use a built-in for state names.

```
f[x_] := Select[
   Transpose[{CountryData["UnitedStates",
       "AdministrativeDivisions"][[All, 2, 1]], {9, 3, 11, 6, 55, 9,
      7, 3, 0, 29, 16, 4, 4, 20, 11, 6, 6, 8, 8, 4, 10, 11, 16, 10, 6,
       10, 3, 5, 6, 4, 14, 5, 29, 15, 3, 18, 7, 7, 20, 4, 9, 3, 11,
      38, 6, 3, 13, 12, 5, 10, 3}}], #[[1]] == x &][[1, 2]]

```

# Answer
> 1 votes
# Ruby, 232 bytes

Uses an array of regular expressions that each represent one bit of the elector count.

```
r=[/[bzCDFYV]|om|e[tge]|Me|di|sk|Mo/,/[zkfDJOTU]..|o[nwtm].|[lai].s|[edy].a|rt/,/[fFHvJxYRUg]...|[hnIg]o|[srx].s|ct|M.i|r.*C/,/[zlLsYrtc]o.|se|ba|y$|ry|di|^Vir/,/[fFGYP]|Oh|ig|Il/,/xa|al/];h=->s{t=0;6.times{|i|s=~r[i]?t+=2**i :0};t}

```

# Answer
> 1 votes
# C (gcc), 289 bytes

Truncates incoming string until it is found in lookup. Immediately preceding every partial state name is the number of electoral votes. Dual-word names are shortened to save some space on the pattern "Foo Bar" -\> "FBar".

The average length of each entry is 2.3, and I had real trouble finding a good hash shorter than that.

Still, too many strX() calls lying around.

```
f(s){char*t=strdup(s),*p=strchr(t,32);for(p++&&memmove(t+1,p,strlen(p)+1);*t*!(p=strstr(")Alab#Alas+Ari&ArkWCa)Col'Con#D=F0G$H$Id4Il+In&Io&Ka(Ke(L$Mai*Mar+Mas0Mic*Min&Missi*Misso#Mo%Neb&Nev$NH.NJ%NM=NY/NC#ND2Oh'Ok'Or4P$R)SC#SD+TenFTex&U#Ve-Vi,Wa%WV*Wi#Wy",t));t[strlen(t)-1]=0);s=*--p-32;}

```

Try it online!

# Answer
> 1 votes
# Ruby, 164 bytes

```
s=gets
g=9
41.times{|i|s[j=i/39,i/8+3].index('IndaMWictAbNekgKO
w ymuTxUSRPGLFvzfJYDHaip'[i,1+j])&&(g=":-1*1206))/5+,3,-8,+0).1L,/*:6.C,1]4C)**,"[i].ord-38)}
puts g

```

Try it online!

**Explanation**

I searched for a single character from the name to identify each state. This worked for about a third of the states, then I started truncating the names on the right hand side. This worked for all states except Maine (which is at the top of the list below and is identified by the string `ai`, along with Hawaii which has the same number of votes.) The program works in reverse, starting with the assumption that the state is Colorado, and revising to a different state each time a character is found. The state length is truncated to `i/8+3` characters. A special consideration is given to Mississippi because its identifying character `p` is so far to the right that it has to be checked at the end.

This is a full program, and input is expected to be newline terminated (as it would at the Ruby console.) This is important because the newline is used as the identifying character for Ohio (when this test is done the string is truncated to 5 characters, and Ohio is the only 4-letter state which does not have another test, so this identifies it.)

**Data used to build the program**

```
i=40 chars=8+1=9
ip['Mississippi', 6],
32..39=7
ai ['Maine', 4],  ['Hawaii', 4],
H['New Hampshire', 4],
D['North Dakota', 3], ['South Dakota', 3], ['Delaware', 3],
Y['New York', 29],
J['New Jersey', 14],
f['California', 55],
z['Arizona', 11],
v['Nevada', 6],
i=24..31 chars=6
F['Florida', 29],
L['Louisiana', 8],
G['Georgia', 16],
P['Pennsylvania', 20],
R['Rhode Island', 4],
S['South Carolina', 9],
U['Utah', 6],
x['Texas', 38]
i=16..23 chars=5
T['Tennessee', 11],
u['Kentucky', 8],
m ['Wyoming', 3]['Vermont', 3],
y['Maryland', 10],
SPACE['New Mexico', 5], ['West Virginia', 5],
w['Iowa', 6],
NEWLINE['Ohio', 18]
O['Oklahoma', 7], ['Oregon', 7],
i=8..15 chars=4
K['Kansas', 6],
g['Virginia', 13],
k['Arka', 6],
e['Nebr', 5],
N['Nort', 15],
b['Alab', 9],
A['Alas', 3],
t['Mont', 3],
i=0..7 chars=3
c['Mich', 16],
i['Minn', 10],  ['Miss', 10],  ['Wisc', 10],
W['Wash', 12],,
M['Mass', 11],
a['Idah', 4],
d['Indi', 11],
n['Conn', 7],
I['Illi', 20],
Initial guess
 ['Colo', 9],

```

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


title: Solve a Picross Row

text:
# Question
Title: Solve a Picross Row
# Introduction

A picross, also known as a nonogram, is a logic puzzle in which the player is given an initially blank grid and must shade in particular boxes on the grid to reveal an image. Numbers are written on the top and the left side, and they explain the image's coloration: each number corresponds to an unbroken line of shaded-in boxes in its row or column. Consider any individual row or column from this completed puzzle to see this correspondence:

Not shown in the image is the fact that one can write an "X" to indicate that a box is known not to be shaded in. Partially solving a row or column by shading in and crossing out boxes provides necessary information for the rest of the puzzle, as rows and columns usually cannot be completely solved on their own (for instance, in the image, this is only possible in the first row).

# The Challenge

To take the hints for a given row along with the state of each box in the row as inputs, and output the row solved to the fullest extent possible.

---

# Examples

In these examples, let `0` represent a box with an "X", `1` a shaded-in box, and `2` an unknown or unknowable (that is, blank) box.

---

This row would be input as

```
[1,3,7,1], [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]

```

and the program should output the following:

```
[2,2,2,2,2,2,2,2,2,2,2,1,1,2,2,2,2,2,2,2]

```

This output corresponds to this row, and no more information can be found:

The boxes marked `1` are always that way, no matter the arrangement of the shading. Essentially, if a box always has the same state, it must assume that state, lest the shading contradicts what is known. If there is not a unanimous agreement, then the box is unknowable and is marked `2`.

---

```
Input: [1,3,7,1], [2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2]
Output:           [2,2,2,2,2,2,0,2,2,2,2,1,1,1,2,2,2,2,2,2]

```

---

```
Input: [6], [2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2]
Output:     [0,0,0,0,0,0,0,2,2,2,2,2,1,2,2,2,2,2,0,0,0,0,0,0,0]

```

If a 6-wide shading were to begin in any of the first 7 boxes, the row would have to have `[6,1]` or `[7]` as its hints, and so none of the first 7 boxes can be filled in. The same is true for the right side.

---

```
Input: [3], [2,0,2,2,2,2,0,2]
Output:     [0,0,2,1,1,2,0,0]

```

Because a 3-wide shading can only fit in the 4-wide gap in the middle, the 1-wide gaps on the edges can be turned into `0`s

---

# Rules

* Any three distinct symbols may be used in the place of `0`, `1` and `2` so long as it is indicated which symbol corresponds to which state
* Assume the input hints and row never form an impossible combination
* This is , so the shortest program in bytes in each language wins

# Answer
> 8 votes
# Python 2, ~~127 124~~ 123 bytes

*-1 byte thanks to @ovs !*

```
l,a,b,c=input()
x=y=i=a|b|c
while i:
 if[len(z)for z in bin(i)[2:].split("0")if z]==l>i&a<1>~i&b:x&=~i;y&=i
 i-=1
print x,y

```

Try it online! or Verify test cases

(Timed-out in TIO for the 2nd test case, but I have verified the program on my PC.)

Reads from `STDIN` the list of streaks `l`, and 3 numbers `a, b, c` representing bit-masks of empty cells, filled cells, and unknown cells.
Prints to `STDOUT` 2 numbers, representing the bit-masks of guaranteed empty cells and guaranteed filled cells.

# Answer
> 1 votes
# Charcoal, 129 bytes

```
ＳθＷΣθ«⊞υιＳθ»≔Ｅυ⁰ζ⊞ζ⁻Ｌθ⁺Συ⊖Ｌυ≔⟦⭆ζ⁺×:⊕ι×#§υκ⟧εＷ⌊ΦＬζ∧κ§ζκ«ＵＭζ⎇‹λι∧⁼λ⊖ι⊕Σ…ζι⁻κ⁼λι⊞ε⭆ζ⁺×:⊕κ×#§υλ»≔Φε⬤θ№⁺-§ι⊕μλε⭆θ§-#:⁻⬤ε⁼§λ⊕κ#⬤ε⁼§λ⊕κ:

```

Try it online! Link is to verbose version of code. I've used `-` for unknown, `:` for empty and `#` for shaded, but of course these could readily be changed to other characters. Explanation:

```
ＳθＷΣθ«⊞υιＳθ»

```

Input the runs and the known state.

```
≔Ｅυ⁰ζ⊞ζ⁻Ｌθ⁺Συ⊖Ｌυ

```

Start by putting all the spare space after the last run.

```
≔⟦⭆ζ⁺×:⊕ι×#§υκ⟧ε

```

Create a list whose entry is an image of that spacing, but with an extra space at the start and junk after the end.

```
Ｗ⌊ΦＬζ∧κ§ζκ«

```

Repeat while runs can be moved.

```
ＵＭζ⎇‹λι∧⁼λ⊖ι⊕Σ…ζι⁻κ⁼λι

```

Calculate the next permutation of runs. This is achieved by moving left the first run that can still be moved left, and then moving all the previous runs to its immediate left.

```
⊞ε⭆ζ⁺×:⊕κ×#§υλ»

```

Push an image of the new spacing to the list.

```
≔Φε⬤θ№⁺-§ι⊕μλε

```

Delete the runs that don't match the original input.

```
⭆θ§-#:⁻⬤ε⁼§λ⊕κ#⬤ε⁼§λ⊕κ:

```

Output the knowable state.

# Answer
> 1 votes
# Wolfram Language, 155 bytes

```
Union@*List~MapThread~Cases[IntegerDigits[i,2,l]~Table~{i,0,2^(l=Length@#)}~Cases~#,
{0...,Splice@Riffle[1~Repeated~{#}&/@#2,0..],0...}]/.{0,1}->_/.{a_}->a&

```

(newline added for "readability")

Try it online!

Note: Since the version that tio.run has is apparently not the latest version (12.1), and Splice was added in it, I have added an equivalent definition.

Uses `_` rather than `2` in the input to leverage built-in pattern-matching capabilities.

The method this answer uses is not very efficient, so don't try any massive inputs.

Program description:

1. Generates all sequences of `0` and `1` of the proper length: `IntegerDigits[i,2,l]~Table~{i,0,2^(l=Length@#)}`
2. Filter to those that match the already solved cells: `~Cases~#` (super easy because I specify the input to work as a pattern)
3. Filter to those that match the row description: `Cases[ ,{0...,Splice@Riffle[1~Repeated~{#}&/@#2,0..],0...}]`
4. Get list of options for each position: `Union@*List~MapThread~`
5. Convert back to input form: `/.{0,1}->_/.{a_}->a`

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


title: Classify State's Senators

text:
# Question
Title: Classify State's Senators
United States senators are sorted into three classes, based on what year their six-year term starts. Since each state has two senators, each state has a senator in two of the three classes.

Given a full state name and a class number (1, 2, or 3), output truthy if that state has a senator of that class, and falsey if that state does not have a senator of that class.

States with Class 1 senators:

> Arizona, California, Connecticut, Delaware, Florida, Hawaii, Indiana, Maine, Maryland, Massachusetts, Michigan, Minnesota, Mississippi, Missouri, Montana, Nebraska, Nevada, New Jersey, New Mexico, New York, North Dakota, Ohio, Pennsylvania, Rhode Island, Tennessee, Texas, Utah, Vermont, Virginia, Washington, West Virginia, Wisconsin, Wyoming

States with Class 2 senators:

> Alabama, Alaska, Arkansas, Colorado, Delaware, Georgia, Idaho, Illinois, Iowa, Kansas, Kentucky, Louisiana, Maine, Massachusetts, Michigan, Minnesota, Mississippi, Montana, Nebraska, New Hampshire, New Jersey, New Mexico, North Carolina, Oklahoma, Oregon, Rhode Island, South Carolina, South Dakota, Tennessee, Texas, Virginia, West Virginia, Wyoming

States with Class 3 senators:

> Alabama, Alaska, Arizona, Arkansas, California, Colorado, Connecticut, Florida, Georgia, Hawaii, Idaho, Illinois, Indiana, Iowa, Kansas, Kentucky, Louisiana, Maryland, Missouri, Nevada, New Hampshire, New York, North Carolina, North Dakota, Ohio, Oklahoma, Oregon, Pennsylvania, South Carolina, South Dakota, Utah, Vermont, Washington, Wisconsin

### Test Cases

```
"Rhode Island", 1 -> true
"Rhode Island", 2 -> true
"Rhode Island", 3 -> false
"California", 1 -> true
"California", 2 -> false
"California", 3 -> true
"South Dakota", 1 -> false
"South Dakota", 2 -> true
"South Dakota", 3 -> true

```

# Answer
# Python 2, ~~67~~ 63 bytes

```
lambda s,l:0x764d5443a33628366/3**(hash(s)%4560%1502%43)%3+1!=l

```

Try it online!

The states can be sorted into three disjoint categories, based on what class of senators they don't have. `hash(s)%4560%1502%43` generates a number \\$0 \le k \le 42 \\$ without mixing up the categories. This number is then used to get a single base-3 digit out of `0x764d5443a33628366`.
> 13 votes

# Answer
# JavaScript (ES6),  ~~98 ... 83~~  79 bytes

A regex solution.

Returns a non-zero value if the state has a senator of the given class.

```
s=>n=>n^=/Oh|gt|N.*D|t$|yl|[UYfv]|[Wdir]i/.test(s)?2:/^I|[ACGHKLOS]/.test(s)||3

```

Try it online!

### How?

The first regular expression matches the states with **class 1** and **class 3** senators:

```
 pattern    | states
------------+---------------------------------------------------------------------------
 Oh         | Ohio
 gt         | Washington
 N.*D       | North Dakota
 t$         | Connecticut, Vermont
 yl         | Maryland, Pennsylvania
 [UYfv]     | California, Nevada, New York, (Pennsylvania), Utah
 [Wdir]i    | Arizona, Florida, Hawaii, Indiana, Missouri, Wisconsin
```

The second regular expression matches the states with **class 2** and **class 3** senators:

```
 pattern    | states
------------+---------------------------------------------------------------------------
 ^I         | Idaho, Illinois, (Indiana<sup>1</sup>), Iowa
 [ACGHKLOS] | Alabama, Alaska, (Arizona<sup>1</sup>), Arkansas, (California<sup>1</sup>), Colorado,
            | (Connecticut<sup>1</sup>), Georgia, (Hawaii<sup>1</sup>), Kansas, Kentucky, Louisiana,
            | New Hampshire, North Carolina, (Ohio<sup>1</sup>), Oklahoma, Oregon, South Carolina,
            | South Dakota
```

<sup>*1: These states belong to the first group. But if they've already been identified as such by the first regular expression, this one will not be executed anyway.*</sup>

The states with **class 1** and **class 2** senators are matched by neither of them:

```
Maine, Nebraska, Massachusetts, Michigan, Delaware, Minnesota, New Jersey, Tennessee,
West Virginia, Mississippi, Virginia, Wyoming, Montana, Rhode Island, New Mexico, Texas

```
> 6 votes

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

Returns a non-zero value if the state has a senator of the given class.

```
s=>n=>0x3A27C2823007F077n.toString(3)[parseInt(s[8]+5+s,35)%462%255%113%56]^~-n

```

Try it online!

The method used to transform the input string is similar to the one described in my answer to this related challenge. Its purpose is to solve the 3 problems we have in JS:

* no built-in hash function
* `parseInt()` breaks on non-alphanumeric characters
* only 52 bits of mantissa for Numbers (i.e. 2 distinct strings sharing the same prefix may be parsed the same way)
> 4 votes

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


title: Read an ASCII clock

text:
# Question
Title: Read an ASCII clock
*Related to, but not a duplicate of, this challenge.*

## Basics

This is a clock:

```
              ******
          **     |    **
      **         |        **
    *            |           *
    *            |           *
  *              |             *
  *              |             *
*                |               *
*                |               *
*                |_______        *
*                                *
*                                *
*                                *
  *                            *
  *                            *
    *                        *
    *                        *
      **                  **
          **          **
              ******

```

Let's note some of the basic properties:

1. It's a circle, 40\*20 (width\*height) characters, made up of asterisks.
2. There are two hands: a minute hand made of 9 pipe characters (`|`); and an hour hand made of 7 underscores (`_`). I.e., in this example the time is 3:00

If a clock weren't arranged in right angles, it might look something like this:

```
              ******
          **          **
      **  |               **
    *      |                 *
    *       |                *
  *          |                 *
  *           |                *
*              |                 *
*               |                *
*                |_              *
*                   _            *
*                     _          *
*                       _        *
  *                            *
  *                            *
    *                        *
    *                        *
      **                  **
          **          **
              ******

```

This represents 4:55.

What's happened here is:

1. We determine the destination (see the diagram below).
2. We determine the number of spaces to delimit by. This will either be 0, 1, or 2 (see the table below).
3. We draw the line by using the respective character (`|` for minute, `_` for hour).
4. We then cut off the line at the number of characters (9 for minute, 7 for hour), including spaces, from the center of the circle along the x-axis. If we reach the edge of the clock, we stop anyway:

```
              ******
       |  **          **
      *|  |               **
    *  |   |                 *
    *  |    |                *
  *    |     |                 *
  *    |      |                *
*      |       |                 *
*      |        | 1234567|       *
*      |         |_      |       *
*      |987654321   _    |       *
*                     _  |       *
*                       _|       *
  *                            *
  *                            *
    *                        *
    *                        *
      **                  **
          **          **
              ******

```

For the sake of completeness, here's a diagram of all possible angles. This applies to minute-hands too: they won't go more specific than 5-minute intervals.

```
              **→0←*
          ↓*          ** ↓
      ** →11             1←*
    *                        *
    *↓                      ↓*
  * →10                     2← *
  *                            *
*                                *
*                                ↓
↓               •                3
9                                ↑
↑                                *
*                                *
  *                            *
  * →8                      4← *
    *↑                      ↑*
    *                        *
      ** →7              5←*
          ↑*          ** ↑
              *→6←**

```

The number of spaces to reach each point is as follows:

```
+-------+----------------------------------------+
| Point | No. of spaces to delimit with to reach |
+-------+----------------------------------------+
| 1     | 1                                      |
+-------+----------------------------------------+
| 2     | 2                                      |
+-------+----------------------------------------+
| 3     | 0                                      |
+-------+----------------------------------------+
| 4     | 2                                      |
+-------+----------------------------------------+
| 5     | 1                                      |
+-------+----------------------------------------+
| 6     | 0                                      |
+-------+----------------------------------------+
| 7     | 1                                      |
+-------+----------------------------------------+
| 8     | 2                                      |
+-------+----------------------------------------+
| 9     | 0                                      |
+-------+----------------------------------------+
| 10    | 2                                      |
+-------+----------------------------------------+
| 11    | 1                                      |
+-------+----------------------------------------+
| 0     | 0                                      |
+-------+----------------------------------------+

```

Note that it is asymmetrical. However, if you wish, you can also take input with the clock flipped vertically, horizontally or both, e.g.

```
              *→○←**
         ↓**          **↓
      **→○              ○←**
    *                        *
    *↓                      ↓*
  * →○                      ○← *
  *                            *
*                                *
*                                ↓
↓                •               ○
○                                ↑
↑                                *
*                                *
  *                            *
  * →○                      ○← *
    *↑                      ↑*
    *                        *
      **→○              ○←**
         ↑**          **↑
              **→○←*

```

(flipped horizontally)

Similarly, when two hands overlap (see below) both hands would usually be aligned to the top of the top-left of the four centre squares. When requesting a flipped input, the centre location will also be flipped accordingly. Note that you cannot mix the two: if you want a flipped input, all aspects, including the centre-point *and* the angle anchors, will be flipped. (On these example diagrams, the centre-point is represented with the centre dot )

For this challenge:

* The minute hand will always be a multiple of five
* The hour hand will always be on the base of the hour (e.g. even if it is 5:59, the hour hand will be exactly on 5)
* Only valid times will be given, and the size of the clock will be constant
* If the hour hand and minute hand are on the same line, the hour hand (`_`) will be used for the first seven characters, followed by `|` for two more, e.g.:

```
              ******
          **          **
      **                  **
    *                        *
    *                        *
  *                            *
  *                            *
*                                *
*                                *
*               _                *
*             _                  *
*           _                    *
*         _                      *
  *     |                      *
  *                            *
    *                        *
    *                        *
      **                  **
          **          **
              ******

```

would represent 8:40.

## Challenge

Given a clock in this format, output the time displayed on the clock. The time should be in 12-hour format (i.e. not starting at 12), but the top number can be 0 or 12, as you wish.

## Rules

* You can return the time as an array of `[hours, minutes]`, a string delimited by some character, or any other reasonable format. You must return pure, base-10 numbers, though: hex representations (0-A instead of 0-11) or other replacements for numbers are disallowed.
* Results can be padded by whitespace or zeros if you wish (e.g. 01:12 instead of 1:12)
* The characters mentioned here must be the ones used by your program. Your submission cannot require substitution of these characters for something else, e.g. take a clock with '`#`' for the hour hand. Further, the input will always contain the spaces at the start of lines, but spaces after the clock (on the right of the diagram) are optional, e.g.:

```
              ******
          **     |    **
      **         |        **
    *            |           *
    *            |           *
  *              |             *
  *              |             *
*                |               *
*                |               *
*                |_______        *
*                                *
*                                *
*                                *
  *                            *
  *                            *
    *                        *
    *                        *
      **                  **
          **          **
              ******

(select this!)

```

# Answer
# 05AB1E (legacy), ~~51~~ 50 bytes

```
•4D-aÕΩ/È°øcû'a•žAвè'_kI•5₁¦M5₅Ï¶ÊäÄVd‰•558вè'|k5*‚

```

Input as a single multi-line string without trailing spaces; output as a pair of `[hours, minutes]`.

-1 byte by switching to the legacy version, where the max/min works on character-lists, based on the ordinal codepoint values of the characters. (In the new version it will simply return the first character instead..)

Try it online or verify all test cases.

Assumes these below are all the clock arms:

```
              ******
          **     |    **
      **  |      |      | **
    *      |     0     1     *
    *       B    0    1      *
  *     |    B   0   1   |     *
  *       A   B  0  1  2       *
*           A  B 0 1 2           *
*             A B012             *
*               yx333333||       *
*      ||99999##z 5 4            *
*           8 7 6  5  4          *
*         8  7  6   5   4        *
  *     |   7   6    5    |    *
  *        7    6     5        *
    *     7     6      5     *
    *    |      6       |    *
      **        |         **
          **    |     **
              ******

```

Where:

* `0-B` represents the hour-arms for the hours `0` to `11`;
* `|` represents the tips of the minute-arms;
* `xyz` represents the -multiple- cents, where `x` is the center for `0,1,2,3,4,5,11`; `y` is the center for `7,8,10`; and `z` is the center for `6,9`;
* `#` are overlapping hour-numbers (for 7&9 and 8&9 respectively).

If they are incorrect (which is likely, since I have multiple centers, and the challenge description is a bit confusing tbh..), the code can easily be modified to correct the arms. The approach will remain the same, I'd just have to adjust the indices in the compressed lists in that case.

**Explanation:**

Checks at the following positions in the input-string:

```
              ******
          **          **
      **  l      a      b **
    *                        *
    *       L    A    B      *
  *     k                c     *
  *       K            C       *
*                                *
*                                *
*                      D d       *
*      j J                       *
*                                *
*         I             E        *
  *     i                 e    *
  *                            *
    *     H     G      F     *
    *    h              f    *
      **        g         **
          **          **
              ******

```

It will first get a list of all characters in the uppercase positions of the graph above (in alphabetical/clock order), and will use the first 0-based index in this list where it finds a '\_' as the hour. It will do the same with the lowercase positions and '|', after which it will multiply this by 5 as the minutes.

```
•4D-aÕΩ/È°øcû'a•  '# Push compressed integer 78119436285968343280298302466166
  žAв              # Converted to base-512 as list: [123,128,193,296,402,502,495,489,388,317,180,118]
     è             # Get the characters at those indices in the (implicit) input-string
      '_k         '# Get the first index of an '_'
•5₁¦M5₅Ï¶ÊäÄVd‰•   # Push compressed integer 103082336338078574425677583851482
  558в             # Converted to base-558 as list: [63,70,162,298,439,534,557,519,421,315,145,56]
I     è            # Get the characters at those indices in the input-string
       Z           # Get the maximum character in this list (without popping the list),
                   # which will always be the '|'
        k          # Get the index of this '|' in the list
         5*        # Multiply that by 5
‚                  # And pair both integers together
                   # (after which it is output implicitly as result)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `•4D-aÕΩ/È°øcû'a•` is `78119436285968343280298302466166`; `•4D-aÕΩ/È°øcû'a•žAв` is `[123,128,193,296,402,502,495,489,388,317,180,118]`; `•5₁¦M5₅Ï¶ÊäÄVd‰•` is `103082336338078574425677583851482`; and `•5₁¦M5₅Ï¶ÊäÄVd‰•558в` is `[63,70,162,298,439,534,557,519,421,315,145,56]`.
> 2 votes

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


# Question
Title: Verify a solution for Conway Immobilizer
## Background

**Conway immobilizer problem** is a puzzle that reads like the following:

> Three positions, "left," "middle," and "right," are marked on a table. Three cards, an ace, a king, and a queen, lie face up in some or all three of the positions. If more than one card occupies a given position then only the top card is visible, and a hidden card is completely hidden; that is, if only two cards are visible then you don't know which of them conceals the missing card.
>
> Your goal is to have the cards stacked in the left position with the ace on top, the king in the middle, and the queen on the bottom. To do this you can move one card at a time from the top of one stack to the top of another stack (which may be empty).
>
> The problem is that you have no short-term memory, so **you must design an algorithm that tells you what to do based only on what is currently visible.** You can't recall what you've done in the past, and you can't count moves. An observer will tell you when you've succeeded. Can you devise a policy that will meet the goal in a bounded number of steps, regardless of the initial position?

The puzzle has got its name because it's said to have immobilized one solver in his chair for six hours.

The link above gives one possible answer (marked as spoiler for those who want to solve it by themselves):

> * If there’s an empty slot, move a card to the right (around the corner, if necessary) to fill it. Exception: If the position is king-blank-ace or king-ace-blank, place the ace on the king.
> * If all three cards are visible, move the card to the right of the queen one space to the right (again, around the corner if necessary). Exception: If the queen is on the left, place the king on the queen.

All solutions to the Immobilizer Problem (pdf) uses graph theory to show that there are 14287056546 distinct strategies that solve the problem.

## Task

Given a strategy for Conway Immobilizer, **determine if the strategy actually solves it**, i.e. given *any* initial configuration, repeating the strategy will eventually place all cards into the winning state.

A strategy (the input) can be in any format that represents a set of pairs `current visible state -> next move` for every possible `current visible state`. A **visible state** represents what is visible on each of three slots (it can be one of A/K/Q or empty). A **move** consists of two values `A, B` which represents a move from slot A to slot B.

The input format can be e.g. a list of pairs, a hash table, or even a function, but it should not involve any external information, e.g. you cannot encode a "move" as a function that modifies the full game state (entire stacks of cards). You can use any four distinct values for A/K/Q/empty (the visible state of each slot) and three distinct values for left/middle/right (to represent a move from a slot to another).

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
Input: the solution above
Output: True

Input: the solution above, but the exception on 'K.A' is removed
       (at 'K.A', move K to the right)
Output: False ('QKA' -> 'K.A' -> 'QKA')

Input: if only one card is visible, move it to the right
       if Q and K are visible, move K on the top of Q
       if K and A are visible, move A on the top of K
       otherwise, move A to the empty slot
Output: False ('..A' where Q, K, A are stacked -> 'A.K' -> '..A')

```

# Answer
> 3 votes
# JavaScript (ES7),  ~~229 224~~  213 bytes

**Input:** a function (the solver) expecting an array of 3 values among `'Q'`, `'K'`, `'A'` or *undefined* for empty, and returning a move as a pair `[from, to]` (0-indexed)

**Output:** 0 or 1

```
f=(F,n=162)=>!n--||(g=s=>(s[k=s.join`/`]^=1)?/A,K,/.test(k)|g(s,[x,y]=F(s.map(a=>a[0])),s[y].unshift(s[x].shift())):0)([0,1,2].map(i=>s[n/3**i%3|0].push('QKAKQAAQKQAKKAQAKQ'[3*~~(n/27)+i]),s=[[],[],[]])&&s)&f(F,n)

```

Try it online!

# Answer
> 0 votes
# Charcoal, ~~120~~ 114 bytes

```
≔Ｅ³³ＳθＦφＦ⁼Σι³Ｆ⪪”{“±¿U+*～T”³«≔⪪λ¹λ≔Ｅ◧Ｉι³ＥΣμ⊟λλ≔⊟Φθ⬤λ⁼§μπ§∨ξ.⁰ζ≔Ｅλ⮌μη⊞§ηＩ§ζ⁴⊟§ηＩ§ζ³⊞υ⁺λＥη⮌μ»≔⊟υθＷΦυ¬№Ｅυ…μ³✂κ³≔⁻υιυ¬υ

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for verified, nothing for failed. Explanation:

```
≔Ｅ³³Ｓθ

```

Read in the 33 instructions, comprising strings of 5 characters, the three visible cards and the source and destination of the move (0-indexed).

```
ＦφＦ⁼Σι³

```

Loop over all 3-digit numbers with a digit sum of 3.

```
Ｆ⪪”{“±¿U+*～T”³«

```

Loop over the permutations of `AKQ` by taking a compressed string of all six permutations and splitting it into substrings of length 3.

```
≔⪪λ¹λ≔

```

Split the `AKQ` into an array.

```
Ｅ◧Ｉι³ＥΣμ⊟λλ

```

Move the `AKQ` into one of three lists depending on the digits of the outer loop variable. For instance, if the variable is `111` then the resulting list is a list of lists of reverse of the array, while if it is `300` then the resulting list has the reverse of the array as its first element and two empty lists. This represents the real positions of the three cards.

```
≔⊟Φθ⬤λ⁼§μπ§∨ξ.⁰ζ

```

Calculate the visible cards and find the move for that set of cards.

```
≔Ｅλ⮌μη

```

Make a reversed copy of the card positions.

```
⊞§ηＩ§ζ⁴⊟§ηＩ§ζ³

```

Perform the move on the copy. The reversal, in addition to resulting in a deep copy, also allows the moved card to be popped and pushed.

```
⊞υ⁺λＥη⮌μ

```

Unreverse the move result and save the cards and the move result to an empty list.

```
»≔⊟υθ

```

Remove the winning position from the list of all card positions.

```
ＷΦυ¬№Ｅυ…μ³✂κ³

```

Repeat while there are positions whose move reaches a winnable position.

```
≔⁻υιυ

```

Remove all of the now winnable positions.

```
¬υ

```

Are there no unwinnable positions left?

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


# Question
Title: Test a polyomino against Conway criterion
## Background

**Conway criterion** is a method to test if a given polygon can tile (i.e. cover without overlapping) an infinite plane. It states that a polygon can tile the plane if the following conditions are met:

* The given polygon does not have any holes in it.
* It is possible to choose six consecutive1 points \\$A,B,C,D,E,F\\$ on its perimeter, so that
    + The boundary part of \\$A\\$ to \\$B\\$ must be equal to that of \\$E\\$ to \\$D\\$ in its size, shape, and orientation;
    + Each of the boundary parts \\$BC\\$, \\$CD\\$, \\$EF\\$, and \\$FA\\$ must have 180-degrees rotational symmetry; and
    + At least 3 out of the six points must be distinct from each other.

1) By *consecutive*, the six points must appear in the given order if you walk around the shape in one direction (either CW (clockwise) or CCW (counter-clockwise)). A boundary part between two consecutive points may contain zero, one, or multiple line segments.

If all the conditions are met, the given shape can tile the plane using only translation and 180-degree rotation. However, failing the condition doesn't mean the piece can't tile the plane. This happens when the tiling involves 90-degree rotations and/or reflections, or the tiling does not use 180-degree rotation at all.

The following is one example that satisfies Conway criterion:

with its plane tiling:

## Task

Given a polyomino without holes as input, determine if it satisfies Conway criterion.

You can take the input in any sensible ways, including but not limited to

* a 2D grid;
* a list of coordinates of the cells;
* a list of coordinates on the boundary (including non-vertices or not);
* a list of steps starting from some point on the perimeter in NSEW notation, ...

If you use the input format that describes the perimeter (e.g. the last two formats above), you can assume that the input (the sequence of points or steps on the perimeter) is given in certain direction (either CW or CCW), but you *cannot* assume that it starts at any certain position.

Standard rules apply. The shortest code in bytes wins.

## Test cases

The test cases are given as 2D grid, where `O` is a part of the polyomino and `.` is an empty space.

### True

```
the example above
OO........
OOOOOOOOOO
OOOOOOOOOO
....OOOOOO
....OOOOOO
....OOOOOO
....OOOOOO
....OOOOOO

the F pentomino
.OO
OO.
.O.
one possible set of points:
  A---E=F
  |   |
+-+ +-+
|   |
B-+ D
  | |
  +-C

OOO.
O.OO
E---D-C
|     |
F +-+ +-+
| | |   |
+-+ A---B

a nonomino that can tile with or without 180 degrees rotation
.O..
.OOO
OOO.
.OO.
.O..

can you spot ABCDEF here? (hint: two points out of ABCDEF are not on the vertices)
OOOO...
.OOOO..
OO.O...
O..OOOO

how about this? (hint: AB and DE are zero-length)
...OOOO.
OO.OO...
O..OOO..
OOOO....
..OOOOOO
..OO....

```

### False

```
can tile the plane, but needs 90 deg rotation
.OOO.
OO.OO

cannot tile the plane at all
OOOO
O...
O.OO
OOO.

can tile with only translation, but not with 180 degrees rotation
...O
.OOO
OOO.
..OO

```

# Answer
# Python 3.8 (pre-release), ~~371 ... 338~~ 336 bytes

Takes as input a list of complex numbers, denoting the boundary coordinates in counterclockwise order.

*-9 bytes thanks to @ovs*
*-2 bytes thanks to @Bubbler*

```
import itertools as Z
def f(P):Q=P*2;I=Q.index;L=len;return any(L({*map(complex.__sub__,T:=(J:=lambda x,y:Q[(j:=I(p[x])):I(p[y],j)+1])(0,1),U:=J(3,4)[::-1])})<2<L({*p})and(L(T)==L(U))&all((B:=J(a,-~a%6))==[B[L(B)//2]-E+B[~L(B)//2]for E in B][::-1]for a in[1,2,4,5])for S in zip(*[Q[I(i):]for i in P])for p in eval('Z.'+dir(Z)[11])(S,6))

```

Try it online!
> 12 votes

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