title: Rotate every 2x2 block in a matrix

text:
# Question
Title: Rotate every 2x2 block in a matrix
# The Challenge

Given a `n x m` matrix with `n > 1` and `m > 1` filled with integers

```
1 2 3
4 5 6

```

and a list of integers with exactly as many values as `2x2` blocks in the matrix (`(n-1)*(m-1)` if you need the exact number)

```
[1, 2]

```

Output the matrix with every `2x2` block rotated by the current value in the list in the given order. The example above would yield

```
4 6 2
5 3 1

```

The first block gets rotated one time to the right and the second block gets rotated two to the right.

## Notes

* A positive integer means you rotate right by that many steps.
* A negative integer means you rotate left by that many steps.
* A zero means that you don't rotate.
* You rotate the blocks row-wise. That means that you start in the first row and go to the right. Once you rotated every block in that row you go to the next one. At the end every block was rotated exactly once.
* Keep in mind that the blocks overlap each other. The first matrix above has the blocks `[[1,2],[4,5]]` and `[[2,3],[5,6]]` for example.
* Each rotation of a block affects the rotation on the adjacent blocks. This is why you have to do the rotations in the pattern described above.

# Rules

* You may take the input in the most convenient format. Please specify in your answer which one you use. This does **not** allow you to read the matrix block-wise though.
* Function or full program allowed.
* Default rules for input/output.
* Standard loopholes apply.
* This is , so lowest byte-count wins. Tiebreaker is earlier submission.

# Test cases

Input format here is a list of lists for the matrix and a normal list for the values.

```
[[1,2],[3,4]], [-3] -> [[4,1],[3,2]]
[[1,1,1],[1,1,1]], [-333, 666] -> [[1,1,1],[1,1,1]]
[[1,2,3],[4,5,6]], [1,2] -> [[4,6,2],[5,3,1]]
[[1,2,3],[4,5,6],[7,8,9]], [4,0,12,-20] -> [[1,2,3],[4,5,6],[7,8,9]]
[[1,2,3,4,5],[5,4,3,2,1],[1,2,3,4,5]], [2,-3,4,1,6,24,21,-5] -> [[4,1,5,2,4],[2,1,3,5,5],[3,2,4,3,1]]

```

**Happy Coding!**

# Answer
## CJam (42 40 bytes)

```
{(\@2$,(/.{@a@a+z(\@.{4,={+2/zW%~}*}z~}}

```

Online demo

Basically this applies the same technique twice in order to fold the block

```
{4,={+2/zW%~}*}

```

which operates on a 2x2 matrix and a number of times to rotate.

```
[first row] [[second row] [third row] ... [last row]] [value_0 value_1 ... value_n]

```

can be processed with

```
.{block}

```

and has the effect of

```
[first row]
[second row] value_0 {block}~
[third row] value_1 {block}~
...

```

because `.` (like `%` in CJam) doesn't gather the results into an array until it's finished.
> 4 votes

# Answer
# APL (Dyalog Unicode), ~~37~~ 35 bytes

```
{⌽∘⍉@⍺⊢⍵}/⌽(⊂,{(4|⎕)/,⊢∘⊂⌺2 2⍳⍴⍵})⎕

```

Try it online!

Switched to a more straightforward method after I realized `@` also accepts a matrix of coordinates. Then we don't need to fiddle with the coordinate order; we extract the submatrix coordinates with `⊢∘⊂⌺2 2`, and just rotate them directly using `⌽∘⍉`.

---

# APL (Dyalog Unicode), 37 bytes

```
{1⌽@⍺⊢⍵}/⌽(⊂,{(4|⎕)/,2,∘⌽/2,⌿⊂¨⍳⍴⍵})⎕

```

Try it online!

A full program that takes the matrix, then the vector of rotation amounts. Prints the resulting matrix with a leading space.

`@` can extract the elements at certain positions, manipulate them, and place them back into the original matrix, which is great for 2×2 rotation. In particular, `1⌽@(1 1)(2 1)(2 2)(1 2)` extracts the top left submatrix `[a b][c d]` into a vector `a c d b`, rotates once to the left (`1⌽`) into `c d b a`, then puts the values back so that the submatrix becomes `[c a][d b]`. This achieves rotating the submatrix exactly once.

```
{1⌽@⍺⊢⍵}/⌽(⊂,{(4|⎕)/,2,∘⌽/2,⌿⊂¨⍳⍴⍵})⎕

⍝ Read from right:
     ⎕  ⍝ Take the matrix from stdin
{...}   ⍝ Pass to the dfn as ⍵
          ⍳⍴⍵  ⍝ Matrix of 2D coordinates of ⍵
     2,⌿⊂¨     ⍝ Pair vertically adjacent coordinates
2,∘⌽/          ⍝ Catenate horizontally adjacent coordinate pairs,
               ⍝ flipping the right one so that it looks like (1 1)(2 1)(2 2)(1 2)
      ,  ⍝ Flatten the matrix of lists of coordinates
(4|⎕)/   ⍝ Copy each (Rotations modulo 4) times
⌽(⊂,...)  ⍝ Prepend the original matrix enclosed and reverse the entire array,
          ⍝ so that it is suitable for RTL reduce
{      }/  ⍝ RTL reduce by...
 1⌽@⍺⊢⍵    ⍝ Take the matrix ⍵ and rotate once at coordinates ⍺

```
> 4 votes

# Answer
## CJam, ~~65~~ ~~63~~ ~~60~~ 55 bytes

There *must* be a better way to do this...

```
{_e_\z,:N(@/Ta*ee{~4,=,f{;1$,,\[XTN_)]f+_(+er\f=}~}/N/}

```

This is an unnamed function that expects the instructions and the matrix (in that order) on the stack and leaves the resulting matrix in their place.

Test it here.

### Explanation

I don't feel like writing the full breakdown for the code right now, so here is a rough overview:

* 2D array manipulation is a pain in CJam, so I'm instead unrolling the matrix, compute each rotation as a permutation of the elements at specific positions and then split the array into rows again at the end. The width of the matrix is stored in `N`.
* A rotation at position `k` in the unrolled array changes four indices: `k <- k+1`, `k+1 <- k+1+N`, `k+N <- k`, `k+1+N <- k+1`. For each index `k` along the instruction list, I compute a permutation corresponding to this, and apply it to the unrolled input array.
* This leaves the problem, that in the linear array some rotations will be positioned with its top left corner in the last column of the input. To skip these, I riffle zeroes into the instruction list, such that these invalid 2x2 sub-blocks *are* technically processed, but with a no-op.
> 2 votes

# Answer
# Python 2, ~~166~~ 159 bytes

```
A,R=input();m=~-len(A[0])
for j,r in enumerate(R):exec r%4*"a,b,c,d=A[j/m][j%m:][:2]+A[j/m+1][j%m:][:2];A[j/m][j%m:j%m+2]=c,a;A[j/m+1][j%m:j%m+2]=b,d;"
print A

```

Try it online!
> 1 votes

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


title: Is it a uniform polyhedron?

text:
# Question
Title: Is it a uniform polyhedron?
# Objective

Given a vertex figure consisting of regular convex polygons, determine whether it represents a convex uniform polyhedron.

# What is a uniform polyhedron?

A uniform polyhedron is a polyhedron whose faces are regular polygons, while having the same vertex figure for each vertices. Generally a uniform polyhedron can be nonconvex, but only convex polyhedra will be considered in this challenge. (More precisely, the polyhedron is required to be vertex-transitive, but that's just another detail.)

# What is a vertex figure?

In the context of a convex uniform polyhedron, a vertex figure is a list of the number of edges of polygons (in order) around a vertex. For example, a cube has vertex figure of (4.4.4).

# Truthy inputs

> (3.3.3) – Tetrahedron
> (4.4.4) – Cube
> (3.3.3.3) – Octahedron
> (5.5.5) – Dodecahedron
> (3.3.3.3.3) – Icosahedron
> (4.4.N) for every N≥3 – N-gonal prism (It is a cube for N=4)
> (3.3.3.N) for every N≥4 – N-gonal antiprism (It is an octahedron for N=3)
> (3.6.6) – Truncated tetrahedron
> (3.4.3.4) – Cuboctahedron
> (3.8.8) – Truncated cube
> (4.6.6) – Truncated octahedron
> (3.4.4.4) – Rhombicuboctahedron
> (4.6.8) – Truncated cuboctahedron
> (3.3.3.3.4) – Snub cube
> (3.5.3.5) – Icosidodecahedron
> (3.10.10) – Truncated dodecahedron
> (5.6.6) – Truncated icosahedron
> (3.4.5.4) – Rhombicosidodecahedron
> (4.6.10) – Truncated icosidodecahedron
> (3.3.3.3.5) – Snub dodecahedron

Rotations and reversions (generally, all dihedral permutations) of these lists are also truthy. For example, (4.6.8), (4.8.6), (6.4.8), (6.8.4), (8.4.6), (8.6.4) are all truthy.

# Falsy examples

> (3.3.3.3.3.3) – Triangular tiling; not a polyhedron.
> (5.5.5.5) – Order-4 pentagonal (hyperbolic) tiling; not a polyhedron.
> (3.3.4.4) – Cannot be uniform. Note that this is different from (3.4.3.4).

# *Don't care* situations

An input is expected to have at least 3 entries, and to consist of integers that are at least 3. Otherwise, the challenge falls in *don't care* situation.

> (5/2.5/2.5/2) – Great stellated dodecahedron; not convex.
> (3.3) – Triangular dihedron; not Euclidean.
> (2.2.2) – Triangular hosohedron; not Euclidean.
> (3/2.3/2.3/2) – Retrograde tetrahedron.
> (1)
> (-3)
> ()

# Answer
> 1 votes
# Jelly,  ~~54~~  51 bytes

```
2×þ5o6R¤
“EḶ¤ẊƓW4mð,’b6ṣ5ịþ¢Ẏṙ€Ƭ1Ẏ;U$e@
ṢṖ’Ḍe“!ṛ‘ȯÇ

```

A dyadic Link accepting a list of integers (each greater than two) which yields `1` if that list is a vertex figure which represents a uniform polyhedron, or `0` otherwise.

**Try it online!** Or see the test-suite.

### How?

First, check if the input is any rotation or reflection of either `4,4,N` or `3,3,3,N` (using `ṢṖ’Ḍe“!ṛ‘`) - the prisms or antiprisms.

If not, build a table containing all the other un-permuted, possibilities - the Platonic and Archimedean solids. Then get all dihedral-permutations of that table's values (`Ẏṙ€Ƭ1Ẏ;U$`) and then check for the existence of the input (`e@`).

Note: The table actually built includes two redundant rows containing only lists which either contain some value(s) less than 3 or are of the form `4,4,N` in some rotation.

To build the table an outer-product using 1-based indexing is made between "items" vectors (of the form `r,2r,3,4,5,6`, where `r` is the row) and "indexes" vectors.

```
  | items        | indexes
--+--------------+----------------------------------------------------------------
r | r,2r,3,4,5,6 | 1,1,1 | 3, 2, 2 | 3,1,3,1 | 1,0,0 | 3,4,1,4 | 4,0,2 | 3,3,3,3,1
--+--------------×-------+---------+---------+-------+---------+-------+----------
1 | 1, 2,3,4,5,6 | 1,1,1 | 3, 2, 2 | 3,1,3,1 | 1,6,6 | 3,4,1,4 | 4,6,2 | 3,3,3,3,1
2 | 2, 4,3,4,5,6 | 2,2,2 | 3, 4, 4 | 3,2,3,2 | 2,6,6 | 3,4,2,4 | 4,6,4 | 3,3,3,3,2
3 | 3, 6,3,4,5,6 | 3,3,3 | 3, 6, 6 | 3,3,3,3 | 3,6,6 | 3,4,3,4 | 4,6,6 | 3,3,3,3,3
4 | 4, 8,3,4,5,6 | 4,4,4 | 3, 8, 8 | 3,4,3,4 | 4,6,6 | 3,4,4,4 | 4,6,8 | 3,3,3,3,4
5 | 5,10,3,4,5,6 | 5,5,5 | 3,10,10 | 3,5,3,5 | 5,6,6 | 3,4,5,4 | 4,6,T | 3,3,3,3,5

```

The "indexes" vectors are encoded as a single base-6 integer which is split at its `5` digits (see the start of Link 2).

```
2×þ5o6R¤ - Link 1, Get the five "items vectors": no arguments
2        - two
   5     - five
  þ      - (implicit [1..2]) table (implicit [1..5]) using:
 ×       -   multiplication  -> [[1,2],[2,4],[3,6],[4,8],[5,10]]
     6R¤ - range of six -> [1,2,3,4,5,6]
    o    - logical OR (vectorises) -> [[1,2,3,4,5,6],[2,4,3,4,5,6],[3,6,3,4,5,6],[4,8,3,4,5,6],[5,10,3,4,5,6]]

“EḶ¤ẊƓW4mð,’b6ṣ5ịþ¢Ẏṙ€Ƭ1Ẏ;U$e@ - Link 2, Platonic or Achimedian?: list of integers (>2), V
“EḶ¤ẊƓW4mð,’                   - base 250 number = 269760427146828960006295
            b6                 - in base 6 = [1,1,1,5,3,2,2,5,3,1,3,1,5,1,0,0,5,3,4,1,4,5,4,0,2,5,3,3,3,3,1]
              ṣ5               - split at fives = [[1,1,1],[3,2,2],[3,1,3,1],[1,0,0],[3,4,1,4],[4,0,2],[3,3,3,3,1]]
                  ¢            - call Link 1 as a nilad = [[1,2,3,4,5,6],[2,4,3,4,5,6],[3,6,3,4,5,6],[4,8,3,4,5,6],[5,10,3,4,5,6]]
                 þ             - table using:
                ị              -   index into -> the 5 by 7 table shown above
                   Ẏ           - tighten (to a list of the unpermuted lists)
                      Ƭ        - collect up until repetition applying:
                    ṙ€ 1       -   rotate each left one place
                        Ẏ      - tighten (to a list of all the rotations)
                           $   - last two links as a monad:
                          U    -   upend (reverse each list)
                         ;     -   concatenate (to the forward ones)
                            e@ - does (the input, V) exist in that list of lists?

ṢṖ’Ḍe“!ṛ‘ȯÇ - Main Link: list of integers (each >2), V
Ṣ           - sort V
 Ṗ          - remove the rightmost (maximal)
  ’         - decrement (each)
   Ḍ        - convert from base ten
     “!ṛ‘   - list of code page indices = [33,222]
    e       - exists in? (i.e. was V some rotation of [4,4,n] or [3,3,3,n]?)
          Ç - call Link 2 as a monad - f(V)
         ȯ  - logical OR

```

# Answer
> 3 votes
# Python 3, 190 bytes

```
def f(F):s="".join(hex(k)[2]for k in F);F[1:]in[[4,4],[3]*3]or{s,s[::-1]}&{*"555 333 366 388 3aa 466 566 468 46a 3434 3444 3454 3535 33333 33334 33335".split()}and max(F)<16or f(F[1:]+F[:1])

```

Try it online!

Takes input as a list of integers representing the vertex figure. The function errors (`RecursionError`) if the vertex figure is *not* a uniform polyhedron, otherwise there is no error.

I tried several schemes of organizing the finite classes into a smart way that takes advantage of patterns, but hardcoding all possibilities reigned superior since it is a relatively small set.

### Explanation

```
def f(F):
    # F is a rotation of the input vertex figure; initially is the input vertex figure
    # Convert to string for easier comparison later in the code
    s="".join(hex(k)[2]for k in F)
    # Test true if the permutation is N.4.4.4 or N.3.3.3
    (F[1:]in[[4,4],[3]*3]or
    # Test truthy if permutation (or its reverse) is in
    #   3.3.3, 3.6.6, 3.8.8, 3.10.10, 4.6.6, 5.6.6, 4.6.8, 4.6.10,
    #   3.3.3.N, 3.4.3.4, 3.4.4.4, 3.4.5.4, 3.5.3.5
    #   3.3.3.3.3, 3.3.3.3.4, 3.3.3.3.5
    {s,s[::-1]}&{*"555 333 366 388 3aa 466 566 468 46a 3434 3444 3454 3535 33333 33334 33335".split()}
    # Numbers greater than 15 would convert into the most-significant hexit when converted to a string,
    # causing 0x43 to match the same as 0x4,
    # so we need to check that none of this happened if we want a bugfree string search
    and max(F)<16
    # If we tested truthy, then terminate
    # Otherwise, recurse with the vertex figure cyclically rotated left one
    or f(F[1:]+F[:1]))

```

# Answer
> 1 votes
# Retina, 142 bytes

```
$
,$",
^`\G\d+,
$&
%L$`,
$'$>`
N^$`.+,(.+),
$1
N`
^(3,(3,3(,(\d+|3,[3-5]))?|4,([3-5],)?4|5,3,5|(6|8|10),\6)|4,4,\d+|4,6,(6|8|10)|5,(5|6),\8),¶

```

Try it online! Link includes test cases. Explanation:

```
$
,$",

```

Duplicate the list and suffix a comma to each copy.

```
^`\G\d+,
$&

```

Reverse the first copy of the list.

```
%L$`,
$'$>`

```

Generate all rotations of both the list and its reverse.

```
N^$`.+,(.+),
$1

```

Sort the last number in descending order.

```
N`

```

Sort in ascending numeric order. (For the truthy cases, these two sorts ensure that the resulting first list is also the first list in list order.)

```
^(...),¶

```

Ensure the first list matches one of the truthy cases:

```
3,(3,3(,(\d+|3,[3-5]))?|4,([3-5],)?4|5,3,5|(6|8|10),\6)

```

Handle those cases with a `3`: `3,3,3`, `3,3,3,N` (`N>=3`), `3,3,3,3,3`, `3,3,3,3,4`, `3,3,3,3,5`, `3,4,4` (this is `4,4,N` with `N=3` of course), `3,4,3,4`, `3,4,4,4`, `3,4,5,4`, `3,5,3,5`, `3,6,6`, `3,8,8`, and `3,10,10`.

```
|4,4,\d+|4,6,(6|8|10)|5,(5|6),\8

```

Handle `4,4,N` (`N>=4`), `4,6,6`, `4,6,8`, `4,6,10`, `5,5,5` and `5,5,6`.

# Answer
> 1 votes
# 05AB1E, ~~68~~ 61 bytes

```
Ž‚ÃS2äI{¨.å•3É≠ÞÌδ)Ö“JhG•твŽ6ð9ǝ11Ž
¤š«.¥Ƶ_+ε5L._Dí«}˜€S>I.å~

```

Input as a list of integers.

Try it online or verify all test cases.

**Explanation:**

Hard-coded approach.

Step 1: Check if the input is of the type `3.3.3.N` or `4.4.N`:

```
Ž‚Ã         # Push compressed integer 33344
   S        # Split it into a list of digits: [3,3,3,4,4]
    2ä      # Try to split it into 2 equal-sized parts: [[3,3,3],[4,4]]
      I     # Push the input-list
       {    # Sort it from lowest to highest
        ¨   # Remove the last/highest item
         .å # Check if this modified input-list is in the [[3,3,3],[4,4]] list of lists

```

Step 2: Check if the input is in the hard-coded list of truthy polyhedrons including their rotations and reflections (minus the `4.4.4` and `3.3.3.3`, which are already covered by the `3.3.3.N` and `4.4.N` check):

```
•3É≠ÞÌδ)Ö“JhG•
            # Push compressed integer 1122222256020285110099101081
 тв         # Convert it to base-100 as list:
            #  [11,22,22,22,56,2,2,85,11,0,99,10,10,81]
Ž6ð         # Push compressed integer 1769
   9ǝ       # Insert it at index 9:
            #  [11,22,22,22,56,2,2,85,11,1760,99,10,10,81]
11          # Push 11
  Ž\n¤      # Push compressed integer 19798
      š     # Convert the 11 to a list [1,1] and prepend the 19798: [19798,1,1]
       «    # Merge it to the other list:
            #  [11,22,22,22,56,2,2,85,11,1769,99,10,10,81,19798,1,1]
.¥          # Undelta it:
            #  [0,11,33,55,77,133,135,137,222,233,2002,2101,2111,2121,2202,22000,22001,22002]
  Ƶ_        # Push compressed integer 222
    +       # Add it to each value:
            #  [222,233,255,277,299,355,357,359,444,455,2224,2323,2333,2343,2424,22222,22223,22224]
 ε          # Map each value to:
  5L        #  Push list [1,2,3,4,5]
    ._      #  Rotate the current integer that many times towards the left:
            #   i.e. acbde → [bcdea,cdeab,deabc,eabcd,abcde]
            #   i.e. abc → [bca,cab,abc,bca,cab]
      D     #  Duplicate that list
       í    #  Reverse each inner integer
            #   i.e. → [aedbc,caedb,bcaed,dbcae,edbca]
            #   i.e. → [acb,bac,cba,acb,bac]
        «   #  Merge the two lists together
 }˜         # After the map: flatten the list of lists
   €S       # Split each integer into a list of digits
     >      # Increase each by 1
      I.å   # Check if the input-list is in this list of lists

```

Step 3: Check if either of the two checks is truthy, and output the result:

```
~           # Bitwise-OR to check if either of the two is truthy
            # (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 why `Ž‚Ã` is `33344`; `•3É≠ÞÌδ)Ö“JhG•` is `1122222256020285110099101081`; `•3É≠ÞÌδ)Ö“JhG•тв` is `[11,22,22,22,56,2,2,85,11,0,99,10,10,81]`; `Ž6ð` is `1769`; `Ž\n¤` is `19798`; and `Ƶ_` is `222`.

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


# Question
Title: Recover boolean cells from windowed sums
## Background

In Minesweeper, you will often encounter a horizontal or vertical wall of one's and two's (not yet revealed cells are marked as `?`):

```
... 1 1 1 1 2 2 2 1 2 1 1 ...
... ? ? ? ? ? ? ? ? ? ? ? ...
... A B C D E F G H ...

```

It is equivalent to a problem of recovering zeros and ones in a boolean array when only windowed sums of size 3 are given, where a zero means a safe cell and a one means a mine:

```
A + B + C = 1
B + C + D = 1
C + D + E = 1
D + E + F = 2
E + F + G = 2
F + G + H = 2
...

```

If you focus on `CDEF`, you can logically determine that `C` should be zero and `F` should be one. If `C` were 1, it would mean `D + E = 0`, which is impossible due to `D + E + F = 2`. (Remember that all variables are booleans.)

## Challenge

This challenge is an extension of this problem to arbitrary window size.

Given `n` windowed sums with window size `k`, recover the `n+k-1` boolean cells in the original array as much as possible. It is possible that some cells cannot be determined by the given information; those cells should be marked as such in the output.

The input is the number `k` and an array (or any ordered collection) of `n` integers between 0 and `k` inclusive. The output is an array of zeros, ones, and unknowns, which can be represented as any three distinct values of your choice. You can assume the input is valid, `n` and `k` are at least 2, and it has at least one corresponding boolean array.

Standard rules apply. The shortest code in bytes wins.

## Test cases

The output format uses `?` for unknown.

```
k = 2

sums   =  0 0
answer = 0 0 0

sums   =  0 1 2 1 0
answer = 0 0 1 1 0 0

sums   =  1 1 1 1 1 1 1
answer = ? ? ? ? ? ? ? ?

sums   =  1 1 1 1 1 1 0 1 1
answer = 0 1 0 1 0 1 0 0 1 0

sums   =  1 1 2 1 1 1
answer = 1 0 1 1 0 1 0
---

k = 3

sums   =   1 1 1 2 2 2
answer = ? ? 0 ? ? 1 ? ?

sums   =   3 2 1 0 1 2 3
answer = 1 1 1 0 0 0 1 1 1

sums   =   1 1 1 2 2 2 2 1 1
answer = 1 0 0 1 0 1 1 0 1 0 0

sums   =   2 2 2 2 2 2 2 1
answer = 1 ? ? 1 ? ? 1 ? ? 0

sums   =   2 1 2
answer = 1 0 1 0 1
---

k = 4

sums   =    1 2
answer = 0 ? ? ? 1

sums   =    3 2 1
answer = 1 1 ? ? 0 0

sums   =    1 1 2 1 1
answer = 0 0 1 0 0 1 0 0

sums   =    1 1 2 2 2 3
answer = 0 0 ? ? 0 1 ? ? 1

```

# Answer
# Jelly, ~~23~~ 18 bytes

```
L+’Ø.ṗ+⁴\⁼¥Ƈ⁸ZṢ€Q€

```

Try it online!

*-5 bytes thanks to @Jonathan Allan*

Uses `[0,1]` as `?`, `[0]` as `0`, and `[1]` as `1`.

### How?

Brute force of all possible boolean matrices.

```
L+’Ø.ṗ+⁴\⁼¥Ƈ⁸ZṢ€Q€
   Ø.               # [0,1]
     ṗ              # Cartesian power:
L+’                 # Length of answer = length of sums + k - 1
           Ƈ          # Filter by:
      +⁴\⁼¥             # n-wise overlapping sums are equal to
            ⁸           # the given sums
             Z      # Get the lists of all possibilities for each position (some binary list)
              Ṣ€    # Sort each possibility list (0s then 1s)
                Q€  # Take unique entries from every possibility ([0],[1],or [0,1])

```
> 5 votes

# Answer
# Brachylog, 39 bytes

Bit frustrating, as a nice attempt that inverts the moving window with `~{sᶠ↙L}` does not work. So this is basically just brute-force.

```
{tL&lʰ+-₁~l.{0|1}ᵐsᶠ↙L+ᵐ~h?∧}ᶠ\{=h|∧2}ᵐ

```

Try it online!

### How it works

```
{tL&lʰ+-₁~l.{0|1}ᵐsᶠ↙L+ᵐ~h?∧}ᶠ
{                           }ᶠ find all solutions:
 tL&                           store the window size as L
    lʰ+-₁                      length of input + window size - 1
         ~l.                   the output has this as length
            {0|1}ᵐ             and contains only 0's and 1's
                  sᶠ↙L         get all windows of length L
                      +ᵐ       that summed
                        ~h?    result in the input array
                           ∧   return the output defined earlier
\{=h|∧2}ᵐ
\                              transpose the solutions
 {     }ᵐ                      map over each position
  =h                           either all solutions are equal, then return first
    |∧2                        or return 2 (should be equivalent to ∨2 but isn't)

```
> 4 votes

# Answer
# Dyalog APL, ~~48~~ 44 43 bytes

```
{0 1⍳(+/÷≢)¨↓s[;⍸⍵≡⍤1⍉⍺+⌿s←2⊥⍣¯1⍳2*⍺+≢1↓⍵]}

```

Try it online!

This program uses `2` to represent `?`, and this program is run using `⎕IO←0`. This is basically a brute force algorithm, and could probably be golfed.
> 3 votes

# Answer
# Python 3, 168 bytes

```
import itertools
lambda k,s:[[q[0],"?"][len(set(q))>1]for q in zip(*[z for z in itertools.product((0,1),repeat=len(s)+k-1)if[sum(z[i:i+k])for i in range(len(s))]==s])]

```

Fairly straightforward: brute forces over all possible binary sequences of length `n+k-1`, collecting all the results, and then aggregating by position, replacing with a "?" if there's multiple possibilities for a given position.

The only clever saving here is in the last step where I use `zip()` to join all the results together by position, and then using `len(set(q))>1` to tell whether or not there's multiple possibilities for a position.

**Ungolfed:**

```
import itertools

def recover(k,sums):
  def window_sum(seq):
    return [sum(seq[i:i+k]) for i in range(len(sums))]
  valid = []
  for poss in itertools.product((0,1), repeat=(len(sums)+k-1)):
    if window_sum(poss) == sums:
      valid.append(poss)
  ans = []
  for by_position in zip(*valid):
    if len(set(by_position)) == 1:
      ans.append(by_position[0])
    else:
      ans.append("?")
  return ans

```
> 2 votes

# Answer
# Charcoal, 45 bytes

```
≔⁺⊖θＬηζ⭆ＥζＥΦＥＸ²ζ◧⍘λ²ζ⬤η⁼ν№✂λξ⁺θξ¹1Σ§λι∧⌈ι∨⌊ι?

```

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

```
≔⁺⊖θＬηζ

```

Calculate the length of the result up-front, saving a byte.

```
⭆Ｅζ

```

Loop over each desired output.

```
ＥΦＥＸ²ζ

```

Count all possible binary patterns...

```
◧⍘λ²ζ

```

... generating padded base 2 strings...

```
⬤η⁼ν№✂λξ⁺θξ¹1

```

... keeping only those with the correct window totals...

```
Σ§λι

```

... keep only the current bit. (Yes, we throw away all of the other results each time. That's code golf for you. If you want efficiency, well I guess you're looking at more like 57 bytes.)

```
∧⌈ι∨⌊ι?

```

Of those bits, if their maximum is 0 or minimum is not 0 then print that otherwise print `?`.
> 1 votes

# Answer
# 05AB1E, 24 bytes

```
1ÝDIgI+<ãʒ'üI«.VO¹Q}øÅAk

```

Port of *@fireflame241*'s Jelly answer, so make sure to upvote him!

Outputs `-1` for `?`.

Try it online or verify all test cases. (Feel free to remove the `1('?:ï` in the footer of the test suite - which converts all `-1` to `"?"` \- to see the actual output.)

**Explanation:**

```
1Ý         # Push a list [0,1]
  D        # Duplicate it
   Ig      # Push the first input-list, and pop and push its length
     I+    # Add the second input-integer `k`
       <   # Decrease it by 1
        ã  # Get the cartesian product of [0,1] with the length+k-1
ʒ          # Filter this list of potential windows by:
 'ü       '#  Push character "ü"
   I«      #  Append the input `k` to it
     .V    #  Execute it as 05AB1E code
           #   `üN` creates overlapping sublists of size `N`
       O   #  Sum each overlapping sublist
        ¹Q #  And check if it's equal to the first input-list
}ø         # After the filter: zip/transpose the remaining lists
  ÅA       # Get the arithmetic mean of each inner list
    k      # Use it to index into the [0,1] list, which results in -1 if it isn't in the
           # list for the decimal values
           # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Ruby, ~~113~~ 112 bytes

```
->k,n{(a=0,1).product(*[a]*z=n.size+k-2).select{|x|n==x.each_cons(k).map(&:sum)}.transpose.map{|x|x.minmax.sum}}

```

Try it online!

Returns false cells as 0, unknowns as 1, and true cells as 2.

Also, this doesn't use new fancy numerical block variables from Ruby 2.7, so that it's still runnable on TIO.
> 1 votes

# Answer
# JavaScript (ES6),  ~~127 126~~  121 bytes

Expects `(k)(array)`. Returns a string, using `123` instead of `01?`.

```
k=>F=(a,i=w=a.length+k-1)=>i--?F(a,i)+(g=n=>n--&&!a.some(h=(v,j)=>++x%~k?h(v-=n>>j&1,j+1):v,x=0)<<(n>>i&1)|g(n))(2<<w):''

```

Try it online!

### Commented

```
k =>                         // outer function taking k
F = (                        // main function taking:
  a,                         //   a[] = input array
  i =                        //   i = counter initialized to ...
  w = a.length + k - 1       //   w = length of output array
) =>                         //
i-- ?                        // decrement i; if it was not equal to 0:
  F(a, i) +                  //   prepend the result of a recursive call to F
  ( g = n =>                 //   g is a recursive function taking a counter n:
      n-- &&                 //     decrement n; stop if it was equal to 0
      !a.some(h = (v, j) =>  //     otherwise, for each v at position j in a[]:
        ++x % ~k ?           //       increment x; if it's not equal to 0 modulo k + 1:
          h(                 //         do a recursive call to the callback of some():
            v -= n >> j & 1, //           subtract the j-th bit of n from v
            j + 1            //           increment j
          )                  //         end of recursive call
        :                    //       else:
          v,                 //         stop recursion and return v
        x = 0                //       start with x = 0
      ) << (n >> i & 1)      //     end of some(); turn true into 0; turn false into 2
                             //     if the if i-th bit of n is set, or 1 otherwise
      | g(n)                 //     bitwise OR with the result of a recursive call to g
  )(2 << w)                  //   initial call to g with n = 2 ** (w + 1)
:                            // else:
  ''                         //   end of recursion on F: return an empty string

```
> 1 votes

---
Tags: code-golf, puzzle-solver, minesweeper
---


title: When does hh:mm = mm.ss?

text:
# Question
Title: When does hh:mm = mm.ss?
Let's begin with a thought experiment. You have a clock and a timer, in which you start the timer when the clock shows exactly `hh:mm.00`.

* Clock: The clock employs 24-hour time. So the range of `hh` is `0<=h<23`. (Because `23` inputs are unsolvable, you aren't required to handle that)
* Timer: It starts exactly on `00.00`. The number to the right of `.` isn't milliseconds; it's seconds.

What you need to do is to find out when the two numbers represented by clock time (hh:mm) is respectively equal to the timer time (mm.ss); e.g. 13:24 is "respectively equal" to 13.24. There can potentially be more than one time.

## An example

Say the input is `1:59`.

```
Clock: 1:59
Timer: 0.00   (The timer just started)

...
Clock: 1:59
Timer: 0.59   (59 seconds later...)

...

Clock: 2:00
Timer: 1.00   (As the timer's second section rounds up to the minute section, the clock time gets incremented by a minute. And the 59 minutes in the clock section gets rounded up to the hour section, hence the 2:00.)

...
Clock: 2:00
Timer: 1.59 (59 seconds later...)

...
Clock: 2:01
Timer: 2.00 (The timer minute gets rounded up, as the clock time increments by a minute)

...
Clock: 2:01
Timer: 2.01 (Now the clock time is "respectively equal" to the timer time)

```

Therefore you need to output `2:01` for the `1:59` input.

## Examples

Here is a sample program I use to check my test cases.

```
0:59 -> 0:59 (or 1:00, if your answer supports that)
1:30 -> 1:31
2:59 -> 3:02
1:59 -> 2:01
3:58 -> 4:02
22:01->22:23

```

## Specifications

* Although in the test cases, the input is taken as `hh:mm`, you can nevertheless take input in a list, e.g. `[hh,mm]`, or any format suitable for your answer.
* You can output the time in the format `[mm,ss]`.
* You *could* start two physical timers, but you need to optimize their speed somehow. Your code running all of the test cases must terminate in 60 seconds.
* You are allowed to take input/output as base 60.
* You don't need to handle unsolvable inputs. I.e. The hour section in the clock will never be `23`.
* If you find more than one time for a specific test case, you can output any of them.

# Answer
> 4 votes
# MathGolf, ~~11~~ 9 bytes

```
+α_╙╟/+╟%

```

Port of the approach used in *@ovs*' Python answer.

Input as two loose integers. Output as a pair.

Try it online.

**Explanation:**

```
+         # Add the two (implicit) inputs together: h+m
 α        # Wrap two items in a list, which will use the (implicit) first input: [h,h+m]
  _╙      # Duplicate it, and pop and push the maximum: h+m
    ╟/    # Integer-divide it by 60: (h+m)//60
      +   # Add it to both values in the list: [h+(h+m)//60,h+m+(h+m)//60]
       ╟% # Take modulo-60 on both: [(h+(h+m)//60)%60,(h+m+(h+m)//60)%60]
          # (after which the entire stack joined together is output implicitly as result)

```

# Answer
> 15 votes
# Raku, ~~14 12~~ 11 bytes

```
0+|*/.98334

```

Try it online!

Since we know the bounds of the input, we can substitute a constant operation and a floor on the input in base 60. That number by the way is around `1358/1381`, which is the maximum the input differs from the output in base 60. There may be a smaller constant, or at least a smaller way to represent it. For reference, the shortest constant you can multiply by, rather than divide, is `1.01694`.

# Answer
> 9 votes
# Python 3.8, ~~40~~ 36 bytes

```
lambda h,m:(d:=h+(h+m)//60,(d+m)%60)

```

Try it online!

# Answer
> 4 votes
# , 42 bytes

```
function(h,m)c(t<-(h*60+m)/59,60*t%%1)%/%1

```

Try it online!

Version 2: -3 bytes thanks to clarification that we don't need to output the **first** match when the timer & clock show the same numbers.
So this version outputs the second match for an input of `0:59` (in other words, `1:00`instead of the first match at `0:59`), and similarly for all other outputs that can end with `:59` or `:00`.

# , Version 1: ~~49~~ 45 bytes

```
function(h,m)c(t<-(h+m/60)*6/5.9,60*t%%1)%/%1

```

Try it online!

Outputs the **first** timer-clock match (so, always a match ending `0:59` instead of a subsequent match ending `:00`).

This exploits the floating-point rounding of `*6/5.9` to slightly less than `*60/59`, but using the same number of characters. This effectively gives us a floor-like result that rounds-down exact integers in the output (the desired behaviour). Using `*60/59` gives an exact floating-point result and so doesn't do this.

~~(Frustratingly, though, it still isn't as short as simply porting ovs's approach for 43 bytes).~~ Version 2 (above) is shorter.

# Answer
> 4 votes
# 05AB1E, ~~13~~ 10 bytes

```
ηO¤60÷+60%

```

Port of the approach used in *@ovs*' Python answer.

I/O as a pair of integers.

Try it online or verify all test cases.

**Explanation:**

```
η          # Get the prefixes of the (implicit) input-pair: [h,m] → [[h],[h,m]]
 O         # Take the sum of each inner list: [h,h+m]
  ¤        # Push the last item (without popping): h+m
   60÷     # Integer-divide it by 60: (h+m)//60
      +    # Add it to both values: [h+(h+m)//60,(h+m)+(h+m)//60]
       60% # Take modulo-60 on both: [(h+(h+m)//60)%60,((h+m)+(h+m)//60)%60]
           # (after which the result is output implicitly)

```

# Answer
> 3 votes
# Retina 0.8.2, 69 bytes

```
\d+
$*
^
$'
+`:1{60}
1:
(1*):1*:
$.1:$1
:(1{60})?(1{10})*(1*)
:$#2$.3

```

Try it online! Link includes test cases. Uses @ovs' formula. Explanation:

```
\d+
$*

```

Convert to unary.

```
^
$'

```

Duplicate the input, which effectively sums the two values together.

```
+`:1{60}
1:

```

Add a sixtieth of the sum to the first value.

```
(1*):1*:
$.1:$1

```

Delete the remainder of the sum, convert the first value to decimal, and also add it to the second value (still in unary).

```
:(1{60})?(1{10})*(1*)
:$#2$.3

```

Convert the second value modulo sixty to two decimal digits.

# Answer
> 3 votes
# Japt, 11 (10?) bytes

Port of Jo's Raku solution

```
ì60'*1.0#©4

```

Try it

This *might* work for 10 but I haven't fully tested it:

```
ì60'*6/5.9

```

Try it

```
ì60'*1.0#©4     :Implicit input of integer array
ì60             :Convert from base-60
   '*           :Multiply by
     1.0#©4     :  1.01694
                :Implicitly convert back to base-60 and output

```

# Answer
> 2 votes
# Javascript, ~~43~~ 42 bytes

```
h=>m=>[~~(h+(i=h+m)/60)%60,~~(61*i/60)%60]

```

Port of the approach used in *@ovs*' Python answer.

Input: two integers, output: List of \[mm,ss\]

Try it online.

# Answer
> 2 votes
# JavaScript (V8), ~~28~~ 26 bytes

```
h=>m=>[h+=h+m>59,(h+m)%60]

```

Based off of SomoKRoceS' JavaScript answer

Input: two integers, output: List of \[mm,ss\]

Try it online!

# Answer
> 1 votes
# , 23 bytes

Based on Jo King's Raku answer. Input and output is in the form of 2-vectors.

```
<.@(1.01694&*)&.(60&#.)

```

Explanation:

```
              &.(60&#.) NB. Under base 60,
   (1.01694&*)          NB. multiply by the magic number,
<.@                     NB. then floor the result.

```

Try it online!

---
Tags: code-golf, date, restricted-time
---


# Question
Title: Will Mario fall into the Shrinking Satellite? (Diagram added)
*Super Mario Galaxy* features two rhombicuboctahedron-shaped\* planets tiled with platforms that shrink as Mario runs across. Should Mario fall into a triangular hole or a gap left by a tile he previously touched, he will be consumed by the black hole at the core. (Watch: Hurry-Scurry Galaxy, Sea Slide Galaxy)

Image: MarioWiki.com

(You can think of the planet as a 2x2x2 cube whose faces have been detached and connected to each other by 2x3 "bridges".)

Unfortunately, since my controller is very broken, Mario cannot jump and is limited to the four cardinal directions. Additionally, Mario moves very slowly and cannot retrace even one step without first having the platform behind him disappear.

Let's assume the camera is always above Mario's head and he starts at the bottom right of a 2x2 face:

```
      ■ ■
      ■ ■
      ■ ■
■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ M ■ ■ ■
      ■ ■
      ■ ■
      ■ ■

```

Your program will take a list or string of directions, `U` `D` `L` `R` (up, down, left, right), representing Mario's walk around the planet so far as a series of steps. The program can output one of two distinct outputs: one representing that Mario is still alive and walking, and the other representing that somewhere along his walk, Mario has fallen into the Shrinking Satellite.

```
RR:   ■ ■                 RRD:  ■ ■                 RRL:  ■ ■
      ■ ■                       ■ ■                       ■ ■
      ■ ■                       ■ ■                       ■ ■
■ ■ ■ ■ ■ ■ ■ ■           ■ ■ ■ ■ ■ ■ ■ ■           ■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ □ □ M ■           ■ ■ ■ ■ □ □ □ ■           ■ ■ ■ ■ □ M □ ■
      ■ ■    \                  ■ ■   M                   ■ ■  \
      ■ ■     Let's-a go!       ■ ■    \                  ■ ■   W-aaaaaaaaaahh!
      ■ ■                       ■ ■     W-aaaaaaaaaahh!   ■ ■

```

Of course, unlike the above diagrams, you'll have to take the 3D into account. Here's a diagram that might help you visualize the scenario better:

```
                Top 2x2 face
   <- clockwise           anticlockwise ->
   -   ■    -    ■    -    ■    -    ■   -
     /   \     /   \     /   \     /   \
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■    Left and right
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ M ■ ■ ■ ■ ■ ■ ■ ■ ■    edges wrap around.
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
     \   /     \   /     \   /     \   /
   -   ■    -    ■    -    ■    -    ■   -
   <- anticlockwise           clockwise ->
               Bottom 2x2 face

```

So according to this diagram, `UUUUURRRR` might look like this:

```
   -   ■    -    ■    -    □    -    ■   -
     /   \     /   \     /   \     /   \
   ■       ■ ■       ■ □       □ ■       ■
   ■       ■ ■       ■ □       □ ■       ■
   ■       ■ ■       ■ □       □ ■       ■
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ M ■ ■ ■ ■ ■
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
     \   /     \   /     \   /     \   /
   -   ■    -    ■    -    ■    -    ■   -

```

And `UUUUUUUUULURRRRRR` might look like this:

```
   -   ■    -    ■    -    □    -    □   -
     /   \     /   \     /   \     /   \
   ■       ■ ■       ■ □       ■ ■       □
   ■       ■ ■       ■ □       ■ ■       □
-> □       ■ ■       ■ □       ■ ■       □ ->
<- □ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ M □ □ □ □ □ <-
   ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
   ■       ■ ■       ■ ■       ■ ■       ■
     \   /     \   /     \   /     \   /
   -   ■    -    ■    -    ■    -    ■   -

```

May the shortest program in bytes w-aaaaaaaaaahh!

## Test Cases

### Output 1: Still Alive

`DDDDDLUUUUU` \- Mario walks across a bridge and back.

`RRRRDDDDLLL` \- Mario walks in a triangle.

`LLLLLLUUUUUURRRRR` \- Mario walks in a bigger triangle.

`ULLDRDDDRU` \- Mario puts himself in peril.

`RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRR` \- Mario takes an unconventional route... and puts himself in peril.

Mario crosses every tile exactly once. `DDDDLUUUULLLLDDDLUUULLLLDDDDLUUUULLLLDDDLUUULLLURRRUUURDDDRRRRUUURDDDRRRRUUURDDDRRRRUUUUURDDDDD` `DLDRDLDLLLDRRRDDDDLLLLLLLLLDRRRRRRRRRDDDDLLLDRRRDDDRUUURRRRULLLLUUUURRRULLLUUUUURDRURDRUURULURU`

### Output 2: W-aaaaaaaaaahh!

`LLR` \- Mario attempts to retrace a step and falls off.

`UULDR` \- Mario attempts to cross a tile twice and steps into air.

`RRDDDDD` \- Mario walks off a bridge at the first D (ignore any following steps).

`RRRRDDDDLLLL` \- Mario walks in a triangle and falls through the starting tile.

`LLLLLLUUUUUURRRRRR` \- Mario walks in a bigger triangle and falls through the starting tile.

`UUUUUUUUUUUUUUUUUUUU` \- Mario walks all the way around the planet and falls through the starting tile.

`RURDRURDRDLDRDLDLDLULDLLUU` \- Mario takes an unconventional route and becomes disoriented.

Mario, realizing the peril he is in, is left with no choice.

`ULLDRDDDRUUU` `ULLDRDDDRUUL` `ULLDRDDDRUUR` `ULLDRDDDRUUD` `RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRR` `RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRU` `RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRL` `RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRD`

Finally, copy any test case from "Mario crosses every tile exactly once" and change or add one step at random. Mario should fall. (If you add a step to the end, Mario falls to grab the Power Star!)

*Cantellated cube would be a more correct term as some faces aren't square, but you've got to admit - "rhombicuboctahedron" flows nicer.

# Answer
# APL (Dyalog), ~~457~~ 441 bytes (Classic Dyalog Character Set)

```
r←'RULD'
S←{(r⍳⍵)⌷4 4⍴2 3 4 1 4 3 1 2 4,(⍳3),3 4 2 1}
C←{(⊂⍺)⌷⍵}
P←,⍉0 1 2 3∘.{2 4 1 3(C⍨⍣⍺)⍵}(⊂⍳4),C\S¨'LUULU'
v←6 6⍴(3⍴0),2(⊥⍣¯1)4512674568
a←1 4 4
N←{s y x←⍵+0,(r⍳⍺)⌷4 2⍴0 1 ¯1 0 0 ¯1 1 0
t Y X←⊃(1+(7<y+x)(0<y-x))⌷2 2⍴('U'5 0)('L'0 5)('R'0 ¯5)('D'¯5 0)
⊃(1+(1+y x)⌷(¯2⊖¯2⌽8 8↑4 4⍴1)∨¯1⊖¯1⌽8 8↑v)⌷((P⍳⊂(⊃s⌷P)C(S t)),(Y X+y x))(s y x)}
M←{T←24 6 6⍴0
~∨/,0>(6 6 6⍴v)-+/[2]6 4 6 6⍴↑(24⍴⍳4){{⊖⍉⍵}⍣⍺⊢⍵}¨⊂[2 3]T⊣{T[⊂⍵]+←1}¨(⊂a),{⊃N/(⌽⍵),⊂a}¨,\⍵}

```

*Thanks, Bubbler, for helping me shave off several bytes!*

Try it online!

To see how this works, let's learn some group theory! First, observe that the entire cuboid structure can be realized as the following shape, tessellated onto the six faces of a cube.

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

```

Now, in our case, I won't be using just six faces. Because Mario's position doesn't just depend on which face he's on; it also depends on his current orientation (i.e. the direction he's facing). So I'll be using 24 states to represent his current state (24 = 6 faces × 4 orientations). Since this is APL, we'll do the calculation in a massive array. Specifically, we'll use a 24×6×6 array to store every position Mario steps on, and how many times he's been there. So Mario's position at a given moment with be a 3-vector `s y x`, where `s` is the cuboid state (face times orientation) and `y`, `x` are the coordinates within that face.

Now, if Mario is in the middle of a face, then when he moves we simply update the position vector accordingly. So a movement `U` (up) would add `0 ¯1 0` to his position. A movement `R` (right) would add `0 0 1`, etc., etc.

The tricky case comes into play when Mario is at an edge. So if we're here

```
      M
    . .
. . . . .
  . . . . .
    . .
    .

```

and we move up, what do we do? We end up moving four down (effectively wrapping around) and to some other cuboid state. So if we started as `s y x`, our new position will be `t (y + 4) x`. But what is `t`? To figure that out, we need to look at rotations of a cube.

As I already mentioned, there are 24 rotations of a cube. Let's try to represent the vertices of a cube numerically.

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

```

Okay, neat. But that's not all of the information we have. In particular, any rotation of a cube will take opposite vertices to opposite vertices. So, in the above diagram, 1 and 8 are at opposite sides. No matter which way I rotate this cube, 1 and 8 will still be opposites. So we really only have four points we care about, as the other four can be calculates from those.

```
  4--3
 /| /|
1--2 |
| 2|-1
|/ |/
3--4

```

As it turns out, this is all of the information we need. If we look at the cube head-on so that the above cube looks like

```
1--2
|  |
|  |
3--4

```

Then every permutation of those four points is a rotation of the cube, and every rotation of the cube can be represented as a permutation of those four points. You can read more about that on Wikipedia, but the basic idea is that rotations of the cube can be represented using the symmetric group S4, which has 24 elements. We'll represent it this way, since APL has some nice built-in functions to apply permutations.

Now, how does this help us? Well, we wanted to know, given a state `s` and a side of the screen we went off (say, to the right, for this example), what is our new state `t`? If we can enumerate the 24 elements of S4 in a nice order, then `s` is simply some element of that enumeration. Then we figure out what the permutation for "go off the screen to the right" is, and compose the two to get `t`. So, if our cube is

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

```

Then, if we go off the screen to the right, we rotate the cube so the face Mario is now on is facing frontward. We get

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

```

Remember that we're identifying opposite vertices, so

```
  1--4
 /| /|
2--3 |
| 3|-2
|/ |/
4--1

```

Looking from the front, we turned a `1 2 3 4` cube into a `2 3 4 1` cube. So our permutation group element is `2 3 4 1`. This works whenever we move right. If we take our current cuboid state (which is an element of S4), and compose it with `2 3 4 1`, we get the new state. A pencil and a bit of effort, and we can calculate the element of S4 representing right, up, left, and down movements.

```
Right 2 3 4 1
Up    4 3 1 2
Left  4 1 2 3
Down  3 4 2 1
*     2 4 1 3

```

That last one (with the `*`) is a rotation of the current face that doesn't change which face Mario is on. So it corresponds to Mario just facing a different direction without walking. In the problem statement, it's not possible for Mario to do that, but we'll need that permutation later for our calculations.

Alright, that should be all the background we need. Let's dig into the code.

```
r←'RULD'

```

Nothing to see here. We use the string `'RULD'` a few times, so it saves us a couple characters to store it.

```
S←{(r⍳⍵)⌷4 4⍴2 3 4 1 4 3 1 2 4,(⍳3),3 4 2 1}

```

`S` is the function which takes R, U, L, or D and converts it to the corresponding permutation we found above.

```
C←{(⊂⍺)⌷⍵}

```

Like I mentioned earlier, APL has nice built-ins for applying permutations. `C` composes two elements of S4. This is how we model multiple steps, like "go right, then go right again".

```
P←,⍉0 1 2 3∘.{2 4 1 3(C⍨⍣⍺)⍵}(⊂⍳4),C\S¨'LUULU'

```

`P` consists of all permutations of `1 2 3 4`, i.e. all elements of the group S4. Let's break it down.

```
(⊂⍳4),C\S¨'LUULU'

```

From the starting orientation, `LUULU` will visit each face of the cube exactly once. So the above expression consists of one permutation representing each face of the cube, ignoring rotations for the moment. We manually tack on the identity `1 2 3 4`, which is our starting state.

```
{2 4 1 3(C⍨⍣⍺)⍵}

```

I mentioned earlier that `2 4 1 3` corresponds to Mario turning his head 90 degrees. We have each face, so we'll want to rotate the faces to get every possible state. This function rotates a face once.

```
0 1 2 3∘.{2 4 1 3(C⍨⍣⍺)⍵}(⊂⍳4),C\S¨'LUULU'

```

Now we rotate every face zero times, once, twice, and thrice, to get every possible permutation.

```
,⍉0 1 2 3∘.{2 4 1 3(C⍨⍣⍺)⍵}(⊂⍳4),C\S¨'LUULU'

```

will transpose the result, which gives us the permutations in a nice order (namely, every cube is represented contiguously, by its four rotations in a sequence in the array). Then we ravel `,` the array to get one nice, flat vector of vectors.

```
v←6 6⍴(3⍴0),2(⊥⍣¯1)4512674568

```

`v` is a representation of the below valid positions grid, encoded in base 10 for compactness.

```
0 0 0 1 0 0
0 0 1 1 0 0
1 1 1 1 1 0
0 1 1 1 1 1
0 0 1 1 0 0
0 0 1 0 0 0

```

```
a←1 4 4

```

Mario's starting state. Again, we use this twice, so it's just barely shorter to assign it to a variable.

```
N←{...}

```

`N` is a big one. Given a direction  (one of the letter RULD) and a position , this moves Mario in that direction. Remember, our position is a 3-vector `s y x`, so we'll be moving in 3-dimensional space, where the third dimension is our state space.

```
s y x←⍵+0,(r⍳⍺)⌷4 2⍴0 1 ¯1 0 0 ¯1 1 0

```

In the easy case, we simply shift `y` and `x` and leave `s` alone. This is fine as long as we don't run off the edge. If we don't, then `s y x`, as declared above, is the correct answer. If we do, then we need to do some more work.

```
2 2⍴('U'5 0)('L'0 5)('R'0 ¯5)('D'¯5 0)

```

On the other hand, if we do run off the edge, this tells us what we have to do. In the first case, we shift the cube up and move Mario down 5. In the second case, we shift the cube left and shift Mario to the right 5, and so on.

```
t Y X←⊃(1+(7<y+x)(0<y-x))⌷...

```

To figure out which case we're in, we draw two diagonal lines along the grid as follows

```
\     .   /
  \ . . /
. . \ / .
  . / \ . .
  / . . \
/   .     \

```

This partitions our grid space into four sections. The lines are determined by `7<y+x` and `0<y-x`. Then we look up our cases in the previous 2×2 array. Note that if we're in the easy case, then this calculation is pointless but ultimately harmless. We'll determine which case we're in next.

```
(¯2⊖¯2⌽8 8↑4 4⍴1)∨¯1⊖¯1⌽8 8↑v

```

This expression uses `v` above and produces the array below

```
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 1 1 1 0 0
0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0
0 0 1 1 1 1 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0

```

Then, if Mario ends up on a `0`, we need to change cuboid state. If not, then we're good. Note that I include a few "out of bounds" points here where there aren't platforms. This prevents Mario from warping to out of the array bounds if he walks off the edge.

```
(1+y x)⌷(...)

```

Look at Mario's position and see if it's a zero in the above array.

```
⊃(1+(1+y x)⌷(¯2⊖¯2⌽8 8↑4 4⍴1)∨¯1⊖¯1⌽8 8↑v)⌷(...)(s y x)

```

We use the above `0` or `1` to index into our two cases. If it's a `1`, simply return `s y x`. If not, then we have more work to do.

```
(P⍳⊂(⊃s⌷P)C(S t)),(Y X+y x)

```

The Y and X coordinates are simply `y x` added to our shift amount we calculated earlier. As for the new cuboid state, we have our direction `t`. Then `S t` is the permutation, which we compose with our permutation for our current state `⊃s⌷P`, then we convert the permutation back to an index in state space `P⍳⊂`.

```
M←{...}

```

Now, `M` is the final piece. It's the function that, given a sequence of inputs, actually determines whether or not Mario falls. It will return `1` on success and `0` if he falls off.

```
T←24 6 6⍴0

```

Our initial state is a 24×6×6 state space, consisting of all zeroes, since Mario hasn't been anywhere yet.

```
(⊂a),{⊃N/(⌽⍵),⊂a}¨,\⍵

```

Now we take all of the prefixes of our input (`,\⍵`) and we move Mario along those paths (`{⊃N/(⌽⍵),⊂a}¨`). Then we tack on the initial state (`(⊂a),`), since Mario clearly starts off by visiting the initial position. Now we have a vector of all of Mario's positions at every moment.

```
{T[⊂⍵]+←1}¨...

```

For each position Mario ever visits, go to that place in the array `T` and add one to it.

```
(24⍴⍳4){{⊖⍉⍵}⍣⍺⊢⍵}¨⊂[2 3]T

```

We have 24 faces on our "cube". In reality, our cube only has 6 faces. So it's time to account for which faces are rotations of which others. Remember, we enumerated our permutations earlier so that the first four states are rotations of one another, then the next four are rotations of one another, and so on. So we'll take `T` (a 24×6×6 array) and, along the first axis (state space), we rotate. We'll rotate the first 6×6 once, the second twice, the third three times, then four times, then once, then twice, and so on. The actual rotation is done by `{⊖⍉⍵}`, which is a transpose followed by a flip. This corresponds to a 90 degree rotation. Now everything is oriented correctly.

```
+/[2]6 4 6 6⍴↑...

```

Now that everything has the right orientation, we want to add together the faces that are actually the same. So reshape the array to a 6×4×6×6 (where the dimensions are, respectively: face, orientation, y, x). Then we sum along the second axis, which represents orientation, giving us a 6×6×6 array of all of the actual positions on the grid.

```
(6 6 6⍴v)-...

```

`v` tells us which positions Mario is allowed to visit. So we subtract the ones we actually visited from this. If we ever end up with a negative number, that means Mario either went somewhere he shouldn't have or he revisited the same space twice.

```
R←~∨/,0>...

```

See if any positions are less than zero. Then invert the result (since success means they're all greater than zero, and failure means there is one which is less).

And that's all there is to it. If you actually read this dissertation of mine, then congratulations! This is my first APL golf, so I'm sure there's room for improvement. But I enjoyed the opportunity to use a bit of math in my answer as well.
> 7 votes

# Answer
# Ruby, golfed, ~~244~~ 230 bytes

Seems to work fine, will test a bit more.

```
->s{a=[8**8/5]*8
v=[-1,x=d=0,1,0]
y=m=4
s.chars{|c|a[y]&=~(1<<x)
y+=v[e="URDL".index(c)+d&3]
x+=v[e-1]
r= ~0**q=x/4
i=q+x&1
j=q+y&1
y%9>7&&(y=4-i;x+=4-j*11-x%2;d+=r)
x&2>0&&-y/2==-2&&(y=i*7;x+=6-x%2*9+j;d-=r)
m*=1&a[y]>>x%=24}
m}

```

# Ruby, first working version, 260 bytes

Try it online

Lambda function taking a string argument. Returns 4 for alive, 0 for dead.

```
->s{a=[0x333333]*8
v=[0,-1,0,1]
x=d=0
y=m=4
s.chars{|c|a[y]&=~(1<<x)
e="URDL".index(c)+d
x+=v[e%4]
y+=v[-~e%4]
p=x&-2
q=x/4%2
y%9>7&&(d-=q*2-1;y,x=4-(q+x)%2,(p+4-(q+y)%2*11)%24)
x&2>0&&-y/2==-2&&(y,x=(q+x)%2*7,(p+6-x%2*8+(q+y)%2)%24;d+=q*2-1)
m*=a[y]>>x&1}
m}

```

**Explanation**

The board is unfolded into 6 strips of size 2x8, represented by the `/\` and `O` characters below. These are mapped onto a 24\*8 2D map, where x=(strip number)\*4+(horizontal position on strip) and y=vertical position on strip.

```
       Map        4         2         0          Initial state of array a
                 /         /         /
                / /       / /       / /          1100110011001100110011
               / /       / /       / /           1100110011001100110011
              O /       O /       O /            1100110011001100110011
             O O       O O       O O             1100110011001100110011
      \     / O \     / O \     / X              110011001100110011001X
     \ \   / / \ \   / / \ \   / /               1100110011001100110011
      \ \ / /   \ \ / /   \ \ / /                1100110011001100110011
       \ O /     \ O /     \ O /                 1100110011001100110011
        O O       O O       O O
         O \       O \       O \                 X=Mario's start point
          \ \       \ \       \ \
           \ \       \ \       \ \
            \         \         \
             5         3         1

```

These are stored in an array of 8 binary numbers, so x increases going left and y increases going down.

The array is intialized with 8 copies of the number `0x33333333`. This forms the squares Mario is allowed to step on. As Mario moves around the square he is on is set to zero, and the square he is moving to is tested - he lives it contains a 1, and dies if it contains a 0.

If Mario walks off the top or bottom of the strip he is on, he moves to another strip. If he walks off the side of the strip he is on, if he is on a square with y=3 or y=4 he moves to another strip. If y is not 3 or 4, he does not move to another strip and ends up on a square which had 0 in it from the outset of the game, so he dies.

Because the camera is always above Mario's head, whenever Mario changes strip, the reference for the directions must be rotated by 90 degrees.

**Ungolfed in test program**

```
f=->s{                             #Move sequence is taken as string argument s.
  a=[0x333333]*8                   #Setup board as an array of 8 copies of 1100110011001100110011.
  v=[0,-1,0,1]                     #Displacements for moving.
  x=d=0                            #Mario starts at 0,4.
  y=m=4                            #d=offset for directions. m=4 when Mario is alive (value chosen for golfing reasons) 0 when dead.

  s.chars{|c|                      #For each character c in s
    a[y]&=~(1<<x)                  #Set the square where Mario is to 0.

    e="URDL".index(c)+d            #Decode the letter and add the offset
    x+=v[e%4]                      #x movement direction is v[e%4]
    y+=v[-~e%4]                    #y movement direction is v[(e+1)%4]
    p=x&-2                         #p is a copy of x with the last bit set to zero (righthand edge of strip).
    q=x/4%2                        #q is 0 for an even number strip, 1 for an odd number strip.
    y%9>7&&(                       #If y out of bounds (8 or -1)
      d-=q*2-1;                    #Adjust d so directions will be interpreted correctly on the next move.
      y,x=
        4-(q+x)%2,                 #y becomes 3 or 4 depending on the values of q and x.
        (p+4-(q+y)%2*11)%24        #If q+y is even, move 1 strip left. if even, move 2 strips right. Take x%24.
    )
    x&2>0&&-y/2==-2&&(             #If x&2>0 Mario has walked sideways off a strip. If y is 3 or 4, move him to a different strip.
      y,x=
        (q+x)%2*7,                 #y becomes 0 or 7, depending on the values of q and x.
        (p+6-x%2*8+(q+y)%2)%24;    #If x%2 is even, move 2 strips left. If odd, move 1 strip right*. Pick the left or right column of the strip depending on (q+y)%2. Take x%24
        d+=q*2-1                   #Adjust d so directions will be interpreted correctly on the next move.
    )

    m*=a[y]>>x&1                   #Multiply m by the value (0 or 1) of the current square. Mario is either alive (4) or dead (0).
    #puts x,y,m,a.map{|i|"%022b"%i}#Uncomment this line for diagnostics.
  }
m}                                 #Return value of m.

#Still alive, return value 4
puts f["DDDDDLUUUUU"] # Mario walks across a bridge and back.
puts f["RRRRDDDDLLL"] # Mario walks in a triangle.
puts f["LLLLLLUUUUUURRRRR"] # Mario walks in a bigger triangle.
puts f["ULLDRDDDRU"] # Mario puts himself in peril.
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRR"] # Mario takes an unconventional route... and puts himself in peril.
puts f["DDDDLUUUULLLLDDDLUUULLLLDDDDLUUUULLLLDDDLUUULLLURRRUUURDDDRRRRUUURDDDRRRRUUURDDDRRRRUUUUURDDDDD"]
puts f["DLDRDLDLLLDRRRDDDDLLLLLLLLLDRRRRRRRRRDDDDLLLDRRRDDDRUUURRRRULLLLUUUURRRULLLUUUUURDRURDRUURULURU"]

#Dead, return value 0

puts f["LLR"] #  Mario attempts to retrace a step and falls off.
puts f["UULDR"] #  Mario attempts to cross a tile twice and steps into air.
puts f["RRDDDDD"] #  Mario walks off a bridge at the first D (ignore any following steps).
puts f["RRRRDDDDLLLL"] #  Mario walks in a triangle and falls through the starting tile.
puts f["LLLLLLUUUUUURRRRRR"] #  Mario walks in a bigger triangle and falls through the starting tile.
puts f["UUUUUUUUUUUUUUUUUUUU"] #  Mario walks all the way around the planet and falls through the starting tile.
puts f["RURDRURDRDLDRDLDLDLULDLLUU"] #

puts f["ULLDRDDDRUUU"]
puts f["ULLDRDDDRUUL"]
puts f["ULLDRDDDRUUR"]
puts f["ULLDRDDDRUUD"]
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRR"] #text case in q is wrong. one more R added to make the kill.
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRU"]
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRL"]
puts f["RURDRURDRDLDRDLDLDLULDLLLLLLLLLLLLLLLLURRRRRRRRRRRRRD"]

```
> 6 votes

---
Tags: code-golf, decision-problem, game, 3d
---


# Question
Title: Squaring Off (fit to smallest possible square)
### Intro

More complex than A square of text since this requires padding and input has unknown data type.

Every year, Dyalog Ltd. holds a student competition. The challenge there is to write *good* APL code. This is a language agnostic edition of this year's tenth problem.

I have explicit permission to post this challenge here from the original author of the competition. Feel free to verify by following the provided link and contacting the author.

### Problem

Write a program/function that will reshape a given string or numeric list into the smallest square that will contain all the elements of the input, padding with additional elements if necessary. The pad element should be the default fill element for the given data type, or any one element of your choice. The elements of the square should be in such order that flattening it will give the original order of input data (with trailing padding elements, if any).

### Test cases

`[1,2,3,4]`

```
[[1,2],
 [3,4]]

```

---

`[1,2,3,4,5]`

```
[[1,2,3],
 [4,5,0],
 [0,0,0]]

```

---

`"Dyalog APL"`

```
[["Dyal"],       [["D","y","a","l"],
 ["og A"],   or   ["o","g"," ","A"],
 ["PL  "],        ["P","L"," "," "],
 ["    "]]        [" "," "," "," "]]

```

---

`[100]`

```
[[100]]

```

---

`[]`

your language's closest equivalent to an empty matrix, e.g. `[]` or `[[]]`

---

# Answer
> 4 votes
# MATL, ~~12~~ 9 bytes

Saved three bytes thanks to Luis. `he` instead of `UGwewe`, but adding a `t` in the beginning.

```
tnX^Xkthe

```

Try it online!

This returns the results, but transposed compared to the result in OPs post (which is OK).

**Explanation:**

This works the same way for both numeric and string input, as MATL treats them the same way.

Assume the input is `'Dyalog APL'`

```
                % Implicit: Take string or numeric array as input
                % Stack: 'Dyalog APL'
t               % Duplicate
                % Stack: 'Dyalog APL'
                %        'Dyalog APL'
 n              % Number of elements in last element.
                % Stack: 'Dyalog APL'
                %        10
  X^            % Take the square root of the number of elements
                % Stack: 'Dyalog APL'
                % Stack: 3.16...
    Xk          % Ceil last number
                % Stack: 'Dyalog APL'
                %        4
      t         % Duplicate element
                % Stack: 'Dyalog APL'
                %        4
                %        4
       h        % Concatenate the last to elements horizontally
                % Stack: 'Dyalog APL'
                %        4  4
        e       % reshape into 4 rows, and 4 columns. Pads the input with zeros or spaces
                % if necessary.
                % Stack: (Note that there's a trailing column not shown below)
                %        DoP
                %        ygL
                %        a
                %        lA

```

This outputs nothing for empty input, which happens to be way MATL outputs empty matrices / strings.

# Answer
> 3 votes
## JavaScript (ES7), 70 bytes

```
a=>[...Array((a.length-1)**.5+1|0)].map((_,$,b)=>b.map(_=>a[i++]),i=0)

```

Returns `[]` for an empty array/string. Uses `undefined` as the fill value. For ES6 replace `(...)**.5` with `Math.sqrt(...)` (+5 bytes).

# Answer
> 2 votes
# R, 91 bytes

```
function(x){if(!is.double(x))x=strsplit(x,'')[[1]];matrix(x,r<-ceiling(sqrt(length(x))),r)}

```

By default, R pads matrices by recycling elements of the input vector and encodes matrices in column-major order. Will return a `0x0` matrix for an input of `double(0)` (an empty double array) or `''`.

The first line (the `if` statement) splits a string into a vector of its constituent characters; if I can take that vector in instead, that line can be removed.

Try it online!

# Answer
> 2 votes
# Brachylog, 10 bytes

```
;Ac~c.\l~l

```

Try it online!

Takes strings as lists of characters (the asker has confirmed that this is OK).

This is *very* inefficient on longer inputs, because it brute-forces all possible reshapings of the input, trying progressively more padding, until it finds one that happens to be square.

## Explanation

```
;Ac~c.\l~l
;Ac         Append {the shortest list possible}.
   ~c       Split into a list of lists
      \l    such that it's rectangular, and the number of columns
     .  ~l  equals the number of rows

```

The padding elements used are Prolog's "any value" value `_`, which is normally rendered as `_G` plus some random digits on output (to make it possible for the Prolog engine to express relationships between those general-purpose values).

Incidentally, there was a bug fix to SWI-Prolog only a few days ago that makes this program possible (although it still appears to work on older, buggy versions); the "it's rectangular" constraint implied by `\` was previously broken, but it got fixed in time for the challenge.

# Answer
> 2 votes
# , 18 bytes

```
,~@>.@%:@#$]{.~#*#

```

Try it online!

# Answer
> 1 votes
# Python 2, 105 bytes

```
def f(a):b=len(a)and int((len(a)-1)**.5)+1;return[(a+[[0],' ']["'"in`a`]*b*b)[b*i:][:b]for i in range(b)]

```

Try it online!

# Answer
> 1 votes
## Haskell, 87 bytes

```
import Data.Lists
f x|c:_<-[n|n<-[1..],n^2>=length x]=take c$chunksOf c$x++(error[]<$x)

```

Try it online!

The fill element is `error[]`, the shortest value that is of any type (`undefined` is a little bit longer).

Notes on the TIO link:

* you cannot print `error`, so I concatenate matrices with fill elements back to a list and print its length
* TIO doesn't have `Data.Lists`, only `Data.List.Split` so it shows 5 more bytes.

How it works: calculate the length `c` of the c-by-c matrix. Take the first `c` elements of the list of chunks of length `c` of the input list followed by a list of fill elements which has the same length as the input list. E.g. :

```
[1,2,3,4,5]                                        -- Input
[1,2,3,4,5,error,error,error,error,error]          -- fill elements appended
[[1,2,3],[4,5,error],[error,error,error],[error]]  -- chunks of length 3
[[1,2,3],[4,5,error],[error,error,error]]          -- take 3

```

# Answer
> 1 votes
# PHP, 139 Bytes

Output string as 2D char array

works with `[]` as empty array

```
$r=[];for($z=ceil(sqrt($n=(($b=is_array($g=$_GET[0]))?count:strlen)($g)));$c<$z*$z;$c++)$r[$c/$z^0][]=$c<$n?$g[+$c]:($b?0:" ");print_r($r);

```

Try it online!

# PHP, 143 Bytes

needs `[[]]` as empty array

Output string as 1D string array

```
$z=ceil(sqrt((($b=is_array($g=$_GET[0]))?count:strlen)($g)));print_r($b?array_chunk(array_pad($g,$z**2,0),$z):str_split(str_pad($g,$z**2),$z));

```

Try it online!

# Answer
> 1 votes
# Jelly, 13 bytes

```
L½Ċẋ€`
0ṁ;@ṁÇ

```

A monadic link taking a flat list and returning a list of lists.

Test suite at **Try it online!**

### How?

Appends as many zeros (the padding element) as there are elements in the input and then reshapes to a square, dropping any zeros excess to requirements in the process.

```
L½Ċẋ€` - Link 1, create a square list of lists of the required size: list a
L      - length of a
 ½     - square root
  Ċ    - ceiling (the required side length, S)
     ` - repeat argument (S) for the dyadic operation:
   ẋ€  -   repeat list for €ach (implicit range [1,2,...,S] on both its left and right)
       -   note: if the input list has no length then an empty list is yielded here

0ṁ;@ṁÇ - Main link: list a (strings are lists of characters in Jelly)
0      - literal zero
 ṁ     - mould like a (makes a list of zeros of the same length as the flat list a)
  ;@   - concatenate a with that
     Ç - call the last link (1) as a monad with argument a
    ṁ  - mould the (possibly oversized) flat array with extra zeros like the square array

```

# Answer
> 0 votes
# Bash, ~~91~~ ~~77~~ ~~69~~ 67 bytes

```
L=`dc -e${#1}\ 1-v1+p`
[ -z "$1"]||printf %-$[$L*$L]s "$1"|fold -$L

```

Try it online!

Formats text, pads with spaces. Outputs nothing to stdout on empty input.

**Update**: stole some tricks from answers here.

# Answer
> 0 votes
# Dyalog APL, ~~20~~ 19 bytes

```
{(,⍨⍴⍵↑⍨×⍨)⌈.5*⍨≢⍵}

```

-1 Byte thanks to @Adám!

Try it online!

---
Tags: code-golf, string, array, data-structures
---


title: Crazy Blazin' DOM Injection

text:
# Question
Title: Crazy Blazin' DOM Injection
# Introduction

This problem is a challenge that has to do with DOM manipulation at scale and overcoming some issues that may be inherent in dealing with the DOM.

* This challenge is interesting because limitations push us to think through things differently and lean on the strengths of languages different than what we usually use.
* I created this challenge myself based on a real world problem I ran into myself (details can be provided if needed). If this challenge has any relation to a differently know problem, those similarities are coincidental.

This challenge will be scored based on fastest execution.

# Challenge

You must render one of the challenge levels in the Chrome web browser (84.0.4147.89 for standardization purposes) (submissions will need to be JavaScript functions for timing purposes):

Using JavaScript please complete the following:

1. Get each table displayed and add a class `table-n` to each table where `n` is a zero based index of order of the table on the screen. If a table is nested within a table the parent would be N and the child would be N+1 with the next table being N+2.
2. Get each row displayed in each table and add a class of `table-n-row-r` where `r` is a zero based index of rows in the table represented by `table-n`.
3. Get each cell displayed in each table and add a class of `table-n-row-r-cell-c` where `c` is a zero based index of cells in a row represented by `table-n-row-r`.

At the end of the challenge the web page should still be able to be interacted through in the browser, and a call to `document.getElementsByClassName('table-n-row-r-cell-c');` should return one and only one cell from the DOM.

Any method available to you as valid as long as:

1. Access to one of the difficulty levels has been done through Chrome (84.0.4147.89)
2. The URL of the browser and the page displayed doesn't change
3. A call to `document.getElementsByClassName('table-n-row-r-cell-c');` returns only one element

# Output Examples

For this example we're using the easy level as input.

The abbreviated output in the DOM should be.

```
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Code Golf Challenge</title>
</head>
<body>
    <table class="table-0">
        <thead>
            <tr class="table-0-row-0">
                <th class="table-0-row-0-cell-0">1</th>
                ...
            </tr>
        </thead>
        <tbody>
            <tr class="table-0-row-1">
                <td class="table-0-row-1-cell-0">11</td>
                <td class="table-0-row-1-cell-1">12</td>
                ...
            </tr>
            ...
    </table>
</body>
</html>

```

There are only `<td>` and `<th>` elements used as cell elements for the challenge.

As long as `document.getElementsByClassName('table-n-row-r-cell-c');` returns an element with this class, we're good to go.

# Qualifying Entries

All entries need to have an execution speed of under 40 seconds for at least one difficulty level to qualify.

Timing starts when your algorithm starts, but after the page has loaded completely as all elements must be available (the browser spinner has stopped spinning).

Calculate the runtime for your method by calling `performance.now()` before and and after your injection method, and subtracting the first from the second as in the example below.

```
let t0 = performance.now();
doSomething()   // <---- The function you're measuring time for
let t1 = performance.now();
let totalTime = t1 - t0;

```

# Winner

The entry that handles the highest difficulty within 40 seconds wins. Ties are broken by execution time at that difficulty.

# Answer
# About 200 ms

```
function mark() {
  var t = 0, tp = '';
  var c = [], i = { r: 0, p: '', c: 0 };
  var elements = document.body.getElementsByTagName('*');
  var length = elements.length, index, v;
  for (index = 0; index < length; ++index) {
    v = elements[index];
    switch (v.tagName) {
      case 'TH':
      case 'TD':
        v.className = i.p + i.c++;
        if (i.c == 10 && i.r == 10) {
          i = c.pop();
        }
        continue;
      case 'TR':
        v.className = i.p = i.t + i.r++;
        i.c = 0;
        i.p += '-col-';
        continue;
      case 'TABLE':
        v.className = tp = 'table-' + t++;
        tp += '-row-';
        c.push(i);
        i = { t: tp, r: 0, p: '', c: 0 };
    }
  }
}

```

If your code runs more than 2s, you must do something wrong. I believe.
> 1 votes

---
Tags: grid, fastest-code, javascript, css, browser
---


title: Cleaning up decimal numbers

text:
# Question
Title: Cleaning up decimal numbers
# Background

Sometimes in calculus you're expected to calculate the sum of an infinite series. Sometimes these series are very friendly, like a geometric series, but add anything else onto it and it can quickly get complicated to solve by hand.

Sometimes I like to be lazy - a lot of sums can be found simply by adding the first few terms then making an approximation. Say the sum of the first ten terms is 0.199999983, and the future terms are approaching zero. We can say with a fair degree of certainty that our final answer will be 0.2, or 1/5.

# The Challenge

Given a decimal number and an integer as inputs, calculate the best (fully simplified) fractional approximation of the decimal number for all fractions up to a denominator of the given integer. The best fractional approximation will be that which is closest to the decimal number in absolute value.

You may take these inputs any way you like and you may output the numerator and denominator any way you like. The numerator and denominator must always be integers, and you may assume we will deal with only positive numbers because adding a negative sign is trivial.

# Test Cases

```
Input | Output

1.21, 8 | 6/5

3.14159265359, 1000000 | 3126535/995207

19.0, 10000000 | 19/1

3.14159265359, 12 | 22/7

2.7182818, 100 | 193/71

0.8193927511, 22 | 9/11

0.2557463559, 20 | 1/4

0.2557463559, 100 | 11/43

0.0748947977, 225 | 14/187

```

# Scoring

This is . Shortest code wins!

# Answer
# Python 3, ~~66~~ 61 bytes

```
lambda x:Fraction(x).limit_denominator
from fractions import*

```

Try it online!

The above function takes a floating point number and returns a bound function `Fraction.limit_denominator` which, in turn, takes the upper bound for the denominator to return a simplified, approximated fraction as requested.

As you can tell, I’m more of an API reader than a golfer.

---
> 14 votes

# Answer
# Python 3.8 (pre-release), ~~77~~ 71 bytes

*-6 bytes thanks to @ovs !*

```
lambda x,n:min([abs(x-(a:=round(x*b))/b),a,b]for b in range(1,n+1))[1:]

```

Try it online!

Simply try all denominators from `1` to `n`, saving all results into a list where each element has the form `[error, numerator, denominator]`. By taking the min of the list, the fraction with the smallest error is selected.
> 13 votes

# Answer
# Python 2, ~~168, 135~~, 87 bytes

```
z=i=1
def f(x,y):exec"r=round(x*i);q=abs(r/i-x)\nif q<z:z=q;t=r;u=i\ni+=1;"*y;print t,u

```

Try it online!

Thank you all for your recommendations on my first golf!
> 10 votes

# Answer
# 05AB1E, 11 bytes

```
î*LãΣ`/¹α}н

```

Try it online or verify all test cases (except for the two `1000000` test cases, which take too long).

**Explanation:**

```
î          # Ceil the (implicit) input-decimal
 *         # Multiply it by the (implicit) input-integer
  L        # Pop and push a list in the range [1, ceil(decimal)*int]
   ã       # Create all possible pairs of this list by taking the cartesian product
    Σ      # Sort this list of pairs by:
     `     #  Pop and push both values separated to the stack
      /    #  Divide them by one another
       ¹α  #  Get the absolute difference with the first input-decimal
    }н     # After the sort: leave only the first pair
           # (after which it is output implicitly as result)

```
> 7 votes

# Answer
# Python 3.8, 169 bytes

Maybe the reason why there was no submissions using Farey sequences is that the code appears rather lengthy.

In short, every proper fraction \\$\frac{m}{k}\\$ in lowest terms appears in Farey sequence of order \\$d\\$ if and only if \\$k\le d\\$.
Farey sequences are constructed by taking mediant of neighboring terms of lower order: \\$\left(\frac ab,\frac cd\right)\to\frac{a+c}{b+d}\\$, starting from \\$\left(\frac 01,\frac 11\right)\\$. And the target number is within one of the intervals \\$\left\[\frac ab,\frac{a+c}{b+d}\right\]\\$, \\$\left\[\frac{a+c}{b+d},\frac cd\right\]\\$, then we take the interval as a current one.

So the algorithm is:

1. Take \\$\left(\frac ab,\frac cd\right):=\left(\frac 01,\frac 11\right)\\$.
2. Take \\$\frac{m}{k}:=\frac{a+c}{b+d}\\$ and compare with target.
3. If \\$\frac{m}{k}\>\\$ target, replace \\$\frac{a}{b}\\$ by \\$\frac{m}{k}\\$,
4. Else replace \\$\frac{c}{d}\\$ by \\$\frac{m}{k}\\$.
5. If the next denominator \\$b+d\\$ is no more than denominator limit, repeat from 2.
6. Else return nearest from \\$\frac ab,\frac cd\\$ to the target.

```
def f(e,n,g,j):
	if n==0:return e,1
	x=[(0,1),(1,1)]
	while True:
		(a,b),(c,d)=x
		if b+d>j:break
		m,k=a+c,b+d
		x[m*g>n*k]=(m,k)
	m,k=x[2*n/g-a/b>c/d]
	return m+e*k,k

```

Try it online!

Eats (entire\_part,proper\_numerator,proper\_denominator,denominator\_limit) and produces (numerator,denominator), like

```
>>> f(3,141592653589793,10**len('141592653589793'),57)
(179, 57)
```

P.S. Recursive version is nothing but shorter, even with all whitespace removed:

```
f=(lambda e,n,g,j,a=0,b=1,c=1,d=1:
   n and(
       b+d>j and(lambda x,y:(x+e*y,y))(*([(a,b),(c,d)][2*n/g-a/b>c/d]))
       or((m:=a+c)*g>n*(k:=b+d))and f(e,n,g,j,a,b,m,k)or f(e,n,g,j,m,k,c,d)
       )or(e,1)
   )

```

Try it online!
> 6 votes

# Answer
# Charcoal, 31 bytes

```
Ｎθ⪫…⮌⌊ＥＥＮ⌊⁺·⁵×θ⊕κ⟦↔⁻θ∕ι⊕κ⊕κι⟧²/

```

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

```
Ｎθ                              Input decimal as a number
        Ｎ                       Input maximum denominator
       Ｅ                        Map over implicit range
                κ               Current index (0-indexed)
               ⊕                Increment (i.e. 1-indexed)
             ×                  Multiplied by
              θ                 Input decimal
         ⌊⁺·⁵                   Round to nearest integer
      Ｅ                         Map over results
                      ι         Current numerator
                     ∕          Divided by
                       ⊕κ       Current denominator
                    θ           Input decimal
                  ↔⁻            Absolute difference
                         ⊕κ     Current denominator
                           ι    Current numerator
                 ⟦          ⟧   Make into list
     ⌊                          Take the minimum (absolute difference)
    ⮌                           Reverse the list
   …                         ²  Take the first two entries
  ⪫                           / Join with literal `/`
                                Implicitly print

```

I'm not 100% sure that the algorithm is correct, so just in case, here's a 34-byte brute-force solution:

```
ＮθＦＮＦ⊕⌈×θ⊕ι⊞υ⟦↔⁻θ∕κ⊕ι⊕ικ⟧Ｉ⊟⌊υ/Ｉ⊟⌊υ

```

Try it online! Link is to verbose version of code. Very slow, so test case is limited to a denominator of `1000`. Explanation:

```
Ｎθ

```

Input the decimal.

```
ＦＮ

```

Loop over the possible denominators (except 0-indexed, so all of the references to the loop variable have to be incremented).

```
Ｆ⊕⌈×θ⊕ι

```

Loop until the nearest numerator above.

```
⊞υ⟦↔⁻θ∕κ⊕ι⊕ικ⟧

```

Save the fraction difference and the denominator and numerator.

```
Ｉ⊟⌊υ/Ｉ⊟⌊υ

```

Print the numerator and denominator of the fraction with the minimum difference.
> 5 votes

# Answer
# Japt v2.0a0 `-g`, 15 bytes

```
mc ×õ ï ñ@ÎaXr÷

```

Try it

```
mc ×õ ï ñ@ÎaXr÷     :Implicit input of array U
m                   :Map
 c                  :  Ceiling
   ×                :Reduce by multiplication
    õ               :Range [1,result]
      ï             :Cartesian product with itself
        ñ           :Sort by
         @          :Passing each pair X through the following function
          Î         :  First element of U
           a        :  Absolute difference with
            Xr÷     :  X reduced by division
                    :Implicit output of first pair

```
> 4 votes

# Answer
# Zig 0.6.0, 149 bytes

```
fn a(e:f64,m:f64)[2]f64{var n:f64=1;var d=n;var b=d;var c=b;while(d<m){if(n/d>e)d+=1 else n+=1;if(@fabs(n/d-e)<@fabs(b/c-e)){b=n;c=d;}}return.{b,c};}

```

Try it

Formatted:

```
fn a(e: f64, m: f64) [2]f64 {
    var n: f64 = 1;
    var d = n;
    var b = d;
    var c = b;
    while (d < m) {
        if (n / d > e) d += 1 else n += 1;
        if (@fabs(n / d - e) < @fabs(b / c - e)) {
            b = n;
            c = d;
        }
    }
    return .{ b, c };
}

```

Variable declarations are annoying.
> 4 votes

# Answer
# Perl 5 `-p -MList::Util=min`, ~~65~~, 61 bytes

-4 bytes thanks to DomHastings

```
/ /;$_=min map abs($`-($-=.5+$_*$`)/$_)." $-/$_",1..$';s;.* ;

```

Try it online!
> 4 votes

# Answer
# , ~~61~~ 60 bytes

With a byte saved by Dominic van Essen.

```
function(x,d,n=round(1:d*x))c(m<-order((x-n/1:d)^2)[1],n[m])

```

Try it online!
> 3 votes

# Answer
# Jelly, 11 bytes

```
Ċ×⁹p÷/ạ¥Þ⁸Ḣ

```

A dyadic Link accepting the decimal \[evaluated as a float\] on the left and the denominator limit on the right which yields a pair `[numerator, denominator]` representing the simplified fraction.

**Try it online!** Or see the test-suite (big denominator limit cases removed due to inefficiency.)

### How?

```
Ċ×⁹p÷/ạ¥Þ⁸Ḣ - Link: v, d
Ċ           - ceil (of the decimal value, v)
 ×⁹         - multiplied by chain's right argument (denominator limit, d)
   p        - Cartesian power (d) -> all pairs [[1,1],...,[1,d],[2,1],...,[Ċ×⁹,d]]
                  (note that any pair representing a non-simplified fraction is to
                   the right of its simplified form)
        Þ   - (stable) sort by:
       ¥    -   last two links as a dyad:
     /      -     reduce by:
    ÷       -       division (i.e. evaluate the fraction)
      ạ  ⁸  -     absolute difference with the chain's left argument (v)
          Ḣ - head

```
> 2 votes

# Answer
# Io, 78 bytes

Port of Surculose Sputum's answer.

```
method(x,y,Range 1to(y)map(a,list((x-(b :=(a*x)round)/a)abs,b,a))min slice(1))

```

Try it online!

# Io, 93 bytes

```
method(x,y,list(((q :=(r :=Range 0to(y)map(a,(x-(a*x)round/a)abs))indexOf(r min))*x)round,q))

```

Try it online!

## Explanation (ungolfed):

```
method(x, y,                   // Take two operands
    r := Range 0 to(y) map(a,  // Map in range 0..y (set to r):
        (x-(a*x)round/a)abs    //     |x-round(a*x)/a|
    )                          //     (Aka find the appropriate numerator)
    q :=r indexOf(r min)       // Set q as the 0-index of the smallest number of r
    list((q*x)round,q)         // Output [numerator,denominator]
)                              // End function

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 26 bytes

```
⌊.5+(⊃∘⍋1+|⍨⌊⊢-|⍨)∘÷∘⍳×1,⊣

```

Try it online!

A dyadic tacit function that takes the decimal number on its left and the max denominator on its right, and gives a 2-element vector of `[denominator, numerator]`.

### How it works

```
⌊.5+(⊃∘⍋1+|⍨⌊⊢-|⍨)∘÷∘⍳×1,⊣  ⍝ Left: x, Right: d
                  ∘÷∘⍳      ⍝ v←[1, 1/2, ..., 1/d]
    (          |⍨)          ⍝ Remainder of x divided by each of v
          |⍨⌊⊢-             ⍝ Min distance from x to some integer multiple of v
        1+                  ⍝ Add 1 to treat close enough numbers as same
                            ⍝ Otherwise it gives something like 5/20 due to FP error
     ⊃∘⍋                    ⍝ D←The index of minimum (the optimal denominator)
                      ×1,⊣  ⍝ Exact fraction (D,Dx)
⌊.5+                        ⍝ Round both

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), 60 bytes

```
(t=s=1;While[Denominator[s=Rationalize[#,1/t++]]<#2,j=s];j)&

```

Try it online!
> 1 votes

# Answer
# Julia, 66 bytes

```
r(x,m)=minimum((n=Int(round(x*d));(abs(x-n/d),n//d)) for d=1:m)[2]

```

or

```
(x,m)->minimum((n=Int(round(x*d));(abs(x-n/d),n//d)) for d=1:m)[2]

```
> 1 votes

# Answer
# , 75 bytes

```
function(x,d)c((n=rep(0:1,e=d)+(1:d*x)%/%1)[f<-order((x-n/1:d)^2)[1]],f%%d)

```

Try it online!

Not a competitive answer as it's already beaten by Kirill, but posting for fun anyway.

I didn't think of the `round()` function, so this approach rounds down & then up to generate a double-length list of candidate numerators, and then finds the index of the closest fraction. Since the index might be in the second (rounded-up) part of the list, the denominator is the index *mod* the length of the single-length list.

I think it's fair to conclude that the `round()` function indeed serves a useful role...
> 1 votes

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


title: Cantor Function, Cruel

text:
# Question
Title: Cantor Function, Cruel
A ripoff of this challenge. Go upvote it!

# Objective

Given a rational number amongst \\$\[0,1\]\\$, apply the Cantor function to it and output the rational number that's produced.

# The Cantor function

The Cantor function is continuous everywhere and constant almost everywhere, but has an average slope of 1:

The Cantor function \\$f(x)\\$ can be expressed as a limit \\$f(x)=\lim\limits\_{n\to\infty} f\_n(x)\\$ of a sequence of functions \\$f\_0, f\_1, f\_2, \dots\\$, which are defined recursively as:

\\$f\_0(x)=x\\$

\\$f\_{n+1}(x)=\left\\{\begin{matrix}\frac{1}{2}f\_n(3x)&x\in\[0,\frac{1}{3})\\ \frac{1}{2}&x\in\[\frac{1}{3},\frac{2}{3})\\ \frac{1}{2}+\frac{1}{2}f\_n(3x-2)&x\in\[\frac{2}{3},1\] \end{matrix}\right.\\$

Your task is to compute \\$f(x)\\$ for the rational \\$x \in \[0,1\] \cap \mathbb{Q}\\$ given as input.

# How?

Though this task might seem *impossible*, this is actually possible, for the Cantor function is computable.

A step-by-step solution for \\$x \in \mathbb{R}\\$:

1. Ternary-expand \\$x\\$ to \\$0.t\_1t\_2t\_3\cdots\\$.
2. Write "0.".
3. Set \\$n=1\\$.
4. If \\$t\_n = 1\\$, write "1" and halt.

* Otherwise, if \\$t\_n = 0\\$, write "0", increment \\$n\\$, then continue doing step #4.
* Otherwise (\\$t\_n = 2\\$), write "1", increment \\$n\\$, then continue doing step #4.

5. Parse the resulting string as a binary expansion of a real number.

As \\$x\\$ actually is in \\$\mathbb{Q}\\$ in this challenge, you should exploit the fact that the ternary expansion of \\$x\\$ repeats. It follows that the output is also in \\$\mathbb{Q}\\$.

# Examples

$$ \begin{array}{r|c|c|c|c|c|c|c|c|c|c} x & 0 & ½ & ⅓ & ¼ & ⅕ & ⅚ & 1 \\ \hline \text{Ternary expansion of }x & 0.\overline{0} & 0.\overline{1} & 0.1\overline{0} & 0.\overline{02} & 0.\overline{0121} & 0.2\overline{1} & 0.\overline{2} \\ \hline \text{Binary expansion of } f(x) & 0.\overline{0} & 0.1 & 0.1 & 0.\overline{01} & 0.01 & 0.11 & 0.\overline{1} \\ \hline f(x) & 0 & ½ & ½ & ⅓ & ¼ & ¾ & 1 \end{array} $$

# Rules

* Invalid inputs fall in *don't care* situation. In particular, you don't need to deal with numbers outside of \\$\[0,1\]\\$.
* Input and output must be exact rational numbers. If your language doesn't natively support rational number arithmetic, use a pair of integers.

# Answer
> 8 votes
# Wolfram Language (Mathematica), 15 bytes

```
CantorStaircase

```

Try it online! Just a built-in function.

# Answer
> 9 votes
# JavaScript (ES7),  ~~141 ... 128~~  125 bytes

*Saved 2 bytes thanks to @Ada*

Expects the fraction \\$p/q\\$ as `(p)(q)`. Returns \\$P/Q\\$ as `[P,Q]`.

```
p=>q=>(k='0b'+(n=0,g=p=>(r=n-g[p])?'':p/q&1||[p/q>>1]+g(p%q*3,g[p]=n++))(p),r?[((k>>r)*(m=2**r-1)+(k&m))*2,m<<n-r]:[+k,1<<n])

```

Try it online!

## How?

### Ternary and binary expansions

```
k =                    // build a binary string
  '0b' + (             // append the binary prefix
    n = 0,             // n is a bit counter
    g = p =>           // g is a recursive function taking the numerator p
      (r = n - g[p]) ? //   if p was already encountered, we have a repeating
                       //   pattern, whose length is stored in r; in that case:
        ''             //     stop the recursion
      :                //   else:
        p / q & 1 ||   //     if p/q = 1, append a '1' and stop the recursion
        [p / q >> 1] + //     otherwise, append '1' if p/q = 2 or '0' if p/q = 0
        g(             //     append the result of a recursive call to g:
          3 * (p % q), //       update p to 3 * (p modulo q)
          g[p] = n++   //       store the position of p in g and increment n
        )              //     end of recursive call
  )(p)                 // initial call with the numerator provided in the input

```

### Turning the binary expansion into a decimal fraction

If \\$r\\$ is *NaN* after the first step, it means that the binary expansion has no repeating pattern. In that case, the numerator is \\$k\\$ and the denominator is \\$2^n\\$.

If \\$r\\$ is defined, we compute the following bitmask:

```
m = 2 ** r - 1

```

The numerator is:

```
((k >> r) * m + (k & m)) * 2

```

and the denominator is:

```
m << n - r

```

# Answer
> 5 votes
# Python 3.8 (pre-release), ~~120 119~~ 117 bytes

*-2 bytes thanks to @Neil!*

```
f=lambda p,q,P=0,Q=1,*R:p in R and(P-P//(i:=1<<R.index(p)+1),Q-Q//i)or f((d:=p*3//q+1)%2*(p*3%q),q,P*2+d//2,Q*2,p,*R)

```

Try it online!

Same idea as below, but as a lambda function instead.

---

# Python 2, ~~133 131 125~~ 122 bytes

*-3 bytes thanks to @Neil!*

```
def f(p,q,P=0,Q=1,*R):
 if p in R:i=1<<R.index(p)+1;return P-P/i,Q-Q/i
 d=p*3/q+1;return f(d%2*(p*3%q),q,P*2+d/2,Q*2,p,*R)

```

Try it online!

A recursive function that takes input as 2 integers `p` and `q`. Outputs 2 integers `(P,Q)` representing the fraction \\$P/Q\\$ (might not be reduced to lowest term).

### Explanation

This solution follows the suggested algorithm in the question.

**Ternary expansion**

To ternary expand `p/q`, we divide `3p` by `q`, resulting in the quotient `d` and remainder `r`. `d` is the next ternary digit. To get the digits after that, we simply recurs on `r/q`.

```
d, r = p*3/q, p*3%q

```

**Get the binary result**

`P/Q` represents the current result, with `Q` always be a power of 2.

* If `d == 1`, we append 1 to the result, aka `(P*2+1, Q*2)`. To stop the recursion, we set the remainder to 0: `f(0, q, P*2+1, Q*2, ...)`
* If `d == 0`, we append 0 to the result and continue: `f(r, q, P*2, Q*2, ...)`
* If `d == 2`, we append 1 to the result and continue: `f(r, q, P*2+1, Q*2, ...)`

We can compress all cases into a single expression. For additional golf, first we increase `d` by 1: `d=p*3/q+1`. The 4 cases above become:

```
return f(
  d%2*r,     # 0 if d==2, else r
  q,
  P*2+d/2,   # P*2 if d==1, else P*2+1
  Q*2,
  ...)

```

This happens to also work for when the input fraction is 1 (`p == q`), in which case `d == 4`, and `f(0, q, 2, 2, ...)` is called, which results in the fraction `4/4`.

**Termination**

The function has to terminate once it finds a repeating block of digits in the ternary expansion. In order to do this, we keep track of all previous numerators in the tuple `R`. After each iteration, we prepend `p` to the list of seen numerators: `f(..., p, *R)`.

At the start of each iteration, we check if `p` is in `R`. If so, every digit after that will be repeated. The length of the repeated block of ternary digits can be calculated from the position of the previous occurrence of `p`: `n = R.index(p)+1`

Let's say that currently, the binary form of `P` is \\$XXXabc\\$, where \\$abc\\$ is the repeated block of digits (aka `n = 3`). Then $$P' = XXXabc.abcabc... = \left(P- \left\lfloor{\frac{P}{2^n}}\right\rfloor \right)\frac{2^n}{2^n-1}$$

and the final result is: $$\frac{P'}{Q} = \frac{\left( P- \left\lfloor{\frac{P}{2^n}}\right\rfloor \right) 2^n}{Q(2^n-1)}$$

Edit: @Neil found a better simplification: $$\frac{P-\left\lfloor\frac{P}{2^n}\right\rfloor}{Q-\left\lfloor\frac{Q}{2^n}\right\rfloor}$$

# Answer
> 4 votes
# Python 2, ~~347~~ 337 bytes

```
exec"B=L,d:B(x/3,d-1)+[x%3]if d else[];V=L:0if x%3else 1+V(x/3);r=L,b,n=1:(3**n-1)%b and r(x,b,n+1)or[n,B((3**n-1)*x/b,n)];F=L:x>[]and(x[-1]>0)+2*F(x[:-1])".replace("L","lambda x")
def c(a,b):
 v=V(b);b/=3**v;N=B(a/b,v);n,R=r(a%b,b);D=N+R
 if 1in D:d=D[:D.index(1)+1];print F(d),2**len(d)
 else:print F(N)*(2**n-1)+F(R)or a,2**v*(2**n-1)

```

Try it online! (modified to return statements for verification)

Takes and returns pairs of integers (numerator, denominator). The input pair must be relatively prime.

### How it works

The program separately identifies the repeating and non-repeating portions of the ternary representation of `a/b`, then splits into 2 cases:

1. If there is a 1 in either portion, then the numerator is (converted from binary with `2``1`) the concatenation of the two portions up to the 1, and the denominator is 2 to the power of the length of that section
2. If there is no 1, then the number retains the repeating portion, so in base 2 (after converting 2s to 1s),

$$\frac{a}{b}=0.x\_1x\_2\ldots x\_k\overline{y\_1y\_2\ldots y\_n}=0.\mathbb{x}\overline{\mathbb{y}}$$

Then $$\frac{a}{b}=\frac{1}{2^k}\left(\mathbb{x} + \frac{1}{2^n-1}\mathbb{y}\right)=\frac{(2^n-1)\mathbb{x}+\mathbb{y}}{(2^n-1)(2^k)}$$

```
# Most-significant ternary digit first
base3 = lambda x, d: base3(x//3, d-1)+[x%3] if d else []
# Largest exponent of a power of 3 that divides x
v3 = lambda x: 0 if x%3 else 1+v3(x//3)
# Base 3 representation of a/b as 0.xyz repeating, where b contains no factors of 3
def rep3(a,b,n=1):
    if (3**n-1)%b==0:
        return n, base3((3**n-1)*a//b,n)
    else:
        return rep3(a,b,n+1)

# Base 2 to int, including converting '2's to '1's
from_base2 = lambda l: eval('0b0'+''.join(map(str,l)).replace('2','1'))

def cantor(a, b):
    # Extract the non-repeating portion of the ternary expansion of a/b
    v = v3(b)
    b //= 3**v
    non_repeating = base3(a//b,v)
    # Repeating portion
    n, repeating = rep3(a%b, b)
    digs = non_repeating + repeating
    if 1 in digs:
        # Take only the part up to/including the first 1, and use it as a binary decimal
        d = digs[:digs.index(1)+1]
        return from_base2(d), 2**(len(d))
    else:
        x = from_base2(non_repeating)
        y = from_base2(repeating)
        # `or a` accounts for the a=b=1 case, which gets treated otherwise as 0.0
        return y+x*(2**n-1) or a, 2**v*(2**n-1)

```

# Answer
> 3 votes
# Charcoal, ~~92~~ ~~77~~ 62 bytes

```
ＮθＮη≔⟦⟧ζＷ¬№ζθ«⊞ζθ≧×³θ⊞υ÷⊕÷θη²≔∧⊖÷θη﹪θηθ»ＩＥ⟦↨υ²Ｘ²Ｌυ⟧⁻ι÷ιＸ²⊕⌕⮌ζθ

```

Try it online! Link is to verbose version of code. I/O is a pair of integers. Does not reduce the output to lowest terms, in particular `1 1` outputs as `2 2` as that needed fewer hacks than before, which helped to save 15 bytes. Explanation:

```
ＮθＮη

```

Input the numerator and denominator.

```
≔⟦⟧ζ

```

Start a list of partial remainders.

```
ζＷ¬№ζθ«

```

Repeat while the current partial remainder has not been seen before.

```
⊞ζθ

```

Push the current partial remainder to the list.

```
≧×³θ

```

Triple it.

```
⊞υ÷⊕÷θη²

```

Push the next bit of the result. (Note that an input of `1` is treated as the illegal ternary `0.3` and massaged into the illegal binary `0.2`.)

```
≔∧⊖÷θη﹪θηθ

```

Get the next partial remainder, unless the current ternary digit is `1`, in which case the next partial remainder is zero.

```
»ＩＥ⟦↨υ²Ｘ²Ｌυ⟧

```

Get the raw binary fraction.

```
⁻ι÷ιＸ²⊕⌕⮌ζθ

```

Adjust it for the recurring part of the binary fraction. (In the case of a terminating fraction, this is detected a bit after the fraction terminates, effectively doubling the numerator and denominator, but the adjustment here simply halves both values again.)

---
Tags: code-golf, math, rational-numbers
---