# Question
Title: AoCG2021 Day 9: Spiral memory stress test
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

Related to AoC2017 Day 3, Part 2.

---

You come across an experimental new kind of memory stored on an infinite two-dimensional grid.

Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated like this:

```
17  16  15  14  13
18   5   4   3  12
19   6   1   2  11
20   7   8   9  10
21  22  23---> ...

```

As a stress test on the system, the programs here clear the grid and then store the value 1 in square 1. Then, in the same allocation order as shown above, they store the sum of the values in all adjacent squares, *not* including diagonals.

So, the first few squares' values are chosen as follows:

* Square 1 starts with the value 1.
* Square 2 has only one adjacent filled square (with value 1), so it also stores 1.
* Square 3 is the same (diagonal neighbors don't count), so it also stores 1.
* Square 4 has squares 1 and 3 as neighbors and stores the sum of their values, 2.
* Square 5 has square 4 as its only neighbor, so it gets the value 2.

Once a square is written, its value does not change. Therefore, the first few squares would receive the following values:

```
 12   12   10    8    7
 14    2    2    1    7
 17    3    1    1    6
 20    3    4    5    5
 20   23   27--->   ...

```

What is the first value written that is at least as large as the input (a positive integer)?

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
1 -> 1
2 -> 2
9 -> 10
18 -> 20
50 -> 55
100 -> 111
200 -> 214
500 -> 552
1000 -> 1070
1070 -> 1070

```

# Answer
> 9 votes
# Charcoal, 49 bytes

```
Ｎθ≔⟦¹⟧ηＷ‹⌈ηθ«⊞υη≔ＥηＥ⮌υ§μλυ≔Ｅ§υ⁰Σ…§υ±¹⊕λη»Ｉ⌊Φη¬‹ιθ

```

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

```
Ｎθ

```

Input the target.

```
≔⟦¹⟧η

```

Start with the middle cell.

```
Ｗ‹⌈ηθ«

```

Repeat until the target is reached.

```
⊞υη

```

Add the latest row to the grid.

```
≔ＥηＥ⮌υ§μλυ

```

Rotate the grid.

```
≔Ｅ§υ⁰Σ…§υ±¹⊕λη

```

Take the cumulative sum of the new last row.

```
»Ｉ⌊Φη¬‹ιθ

```

Output the smallest value not lower than the target.

# Answer
> 5 votes
# , 39 37 bytes

```
{{y(<:<./@#]),|:@|.@(,+/\@{:)^:y,.1}}

```

*-2 thanks to Olius's idea of using direct definition `{{ }}` instead of a tacit verb*

YAPONA - Yet Another Port of Neil's Answer.

To save bytes, we repeat the iteration `<input>` times -- which is always enough, and usually returns much more than we need -- then find the first valid number within that result.

No TIO for this one because the TIO J version is too old and doesn't have `{{ }}` yet. I tested locally though and it works. TIO'd tacit version below.

# , 39 bytes tacit solution with TIO

```
(<:<./@#&,])]1&(](,~+/\.@{.)@|:@|.),.@1

```

Try it online!

# Answer
> 5 votes
# Ruby, ~~80 78 75~~ 66 bytes

```
->n,*r{(n+a=1).times{|x|r<<a;(1..x/2).map{a<n&&r<<a+=r[1-x-x]}};a}

```

Try it online!

### Explanation (if it still matters):

* We need at most (n+1) segments to find the number (n=2,3,4 can't be found on the 2nd 3rd and 4th segment).
* Length of segments (removing corners) is 0, 0, 1, 1, 2, 2, 3, 3 ...
* In the corners we can reuse the previous value: x\[n\]=x\[n-1\]
* For the other cells: x\[n\]=x\[n-1\]+x\[n-m\] where m is increased by 2 for every side.

Maybe there is a way to skip the corners? we don't need the repeated values to find the final result, only to calculate the other intermediate values.

# Answer
> 4 votes
# Python 3.8 (pre-release), 96, 94, 92 (@dingledooper), 90 bytes (@xnor)

```
def f(i):
 *T,s=1,;t=T,[1],[1]
 while i>s:T,*t=*t,[s:=s+x*(i>s)for x in[0,*T,0]]
 return s

```

Try it online!

Older versions

Try it online!

Try it online!

Try it online!

This keeps a running sum `s` and the four sides of the growing rectangle/spiral double accounting for corners. `T` holds the "active" side, `t` the three others.

# Answer
> 4 votes
# JavaScript (ES6), 73 bytes

```
n=>eval("for(j=k=0,a=[t=q=1];q<n;)a.push(q+=j--?a[++t-k]:![j=++k>>1]);q")

```

Try it online!

### Commented

This is a version without `eval()` for easier formatting.

```
n => {               // n = input
  for(               // main loop:
    j =              //   j is the length of the current segment minus 1
    k = 0,           //   k is incremented after each segment
                     //   (which means that it holds the number of turns)
                     //   the length of the next segment is floor((k+1)/2)
    a = [            //   a[] is used to store the sequence
      t =            //   t+1-k is the index of the neighbor cell in the
                     //   previous layer of the spiral
      q = 1          //   q is the current value of the sequence
    ];               //
    q < n;           //   we keep going until q >= n
  )                  //
    a.push(          //   append to a[]:
      q +=           //     the updated value of q
        j--          //     decrement j
        ?            //     if we haven't reached the end of the segment:
          a[++t - k] //       increment t and add the value of the
                     //       neighbor cell in the previous layer
        :            //     else (this is a corner):
          ![         //       leave q unchanged
            j =      //       increment k and update j to
            ++k >> 1 //       floor(k/2)
          ]          //
    );               //   end of push()
  return q           // end of for(); return q
}                    //

```

# Answer
> 3 votes
# Pari/GP, 87 bytes

```
n->a=Mat(1);until(d=[b|b<-c,b>=n],s=0;a=Mat(Vecrev(concat(c=[s+=b|b<-a[,1]],a~))));d[1]

```

Try it online!

A port of @Neil's answer.

# Answer
> 3 votes
# JavaScript (Node.js), 91 bytes

```
f=(n,o=p=[X=x=y=0,Y=v=1])=>n>(o[[x+=o[p]?X:X+=Y+(Y=-X),y+=Y]]=v+=o[p=[x+Y,y-X]]|0)?f(n,o):v

```

Try it online!

# Answer
> 3 votes
# 05AB1E, 18 bytes

```
1¸¸IFøí¤ηOª}˜ʒI@}ß

```

Port of *@Neil*'s Charcoal answer.

Try it online or verify all test cases (the test suite loops until the result is found (`IF` replaced with `[ZI@#`), since looping \\$n\\$ times will time out for the larger test cases).

**Explanation:**

```
1¸¸         # Start matrix at center [[1]]
   IF       # Loop the input amount of times:
     øí     #  Rotate the matrix once clockwise:
     ø      #   Zip/transpose; swapping rows/columns
      í     #   Reverse each row
       ¤    #  Get the last row (without popping the matrix)
        ηO  #  Get the cumulative sum:
        η   #   Pop and push a list of its prefixes
         O  #   Sum each inner list
          ª #  Add this row to the matrix
    }˜      # After the loop: flatten the matrix to a list
      ʒ     # Filter this list of integers by:
       I@   #  Keep those larger than or equal to the input
      }ß    # After the filter: pop and push the minimum
            # (which is output implicitly as result)

```

`ʒI@}ß` could alternatively be `I<LKß` (push list \\$\[1,input)\\$, remove those values, minimum) or `{.Δ>‹` (sort, find first \\$n\\$ which is \\$input\lt n+1\\$) for the same byte-count.

# Answer
> 1 votes
# Rust, 155 151 bytes

```
|a|{let(mut s,mut v)=(1,vec![0,1,1]);for i in(0..).flat_map(|i|{s+=i/2;(0..1).chain(s-i/2..=s)}){let r=v[i]+v[v.len()-1];v.push(r);if r>=a{return r}}0}

```

Try it online!

This works by generating A334742 (the actual numbers in the spiral) using A265400 (indices of adjacent squares), which is generated using A004526 (length of each corner, which increases every two rotations).

* -4 bytes by replacing the outer iterator with `for`

# Answer
> 1 votes
# BQN, 31 bytes SBCS

```
{⊑≥⟜⊸/∧⥊{⌽˘⍉∾+`⊏⌽}⍟≍≍1}

```

Run online!

Similar idea to Neil's answer. Some combinators come in really handy here.

# Answer
> 1 votes
# TypeScript Types, 389 bytes

```
//@ts-ignore
type a<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type b<T,N=[],U=[]>=T extends[infer A,...infer T]?b<T,[...N,...A],[...U,[...N,...A]]>:U;type c<N,A=[[0]],B=A,C=A,D=A,E=b<A>,F=E[number]>=1 extends(F extends N?1:0)?a<Extract<F,N>>:E extends[...{}[],infer L]?c<N,[L,...B],C,[...D,A[0]],E>:0;type M<N,m=[]>=N extends m["length"]?c<[...m,...0[]]>["length"]:M<N,[...m,0]>

```

Try It Online!

## Ungolfed / Explanation

```
// Filters a union of tuples for those with the shortest length
type Shortest<T, K = keyof T> = T extends T ? keyof T extends K ? T : never : 0

// Turns [a, b, c, d] into [a, a+b, a+b+c, a+b+c+d]
type CumSum<T, N=[], U=[]> = T extends [infer A,...infer T] ? CumSum<T, [...N, ...A], [...U, [...N, ...A]]> : U

// Extends the spiral one side at a time until one of the numbers is matches N
// If the spiral is
//   a b c d
//   e f g h
//   i j k l
//   '->
// (where g was the start)
// It will be represented as A=[i,j,k,l] ; B=[l,h,d] ; C=[d,c,b,a] ; D=[a,e,i]
// The next iteration will be
//   a b c d
//   e f g h
//   i j k l ^
//   m n o p-'
// Where m=i ; n=m+j ; o=n+k ; p=o+l
// And is represented as A=[p,l,h,d] ; B=[d,c,b,a] ; C=[a,e,i,m] ; D=[m,n,o,p]
// The spiral starts as A=B=C=D=[1] ([[0]] in tuple form)
type Iterate<Cond, A=[[0]], B=A, C=A, D=A, New=CumSum<A>, NewNums=New[number]> =
  1 extends (NewNums extends Cond ? 1 : 0)
    // If any of NewNums match Cond, return the shortest of those that do
    ? Shortest<Extract<NewNums, Cond>>
    : New extends [...{}[],infer L]
      // Get the last element of New, and update the spiral sides
      ? Iterate<Cond, [L,...B], C, [...D, A[0]], New>
      // Unreachable
      : 0

type Main<N,M=[]> =
  N extends M["length"]
    // If M's length is N, return Iterate where Cond is >= M
    ? Iterate<[...M,...0[]]>["length"]
    // Increment M and repeat
    : Main<N, [...M, 0]>

```

# Answer
> 0 votes
# Wolfram Language (Mathematica), 76 bytes

```
Min@Cases[Nest[Reverse@Append[#,Accumulate@Last@#]&,{{1}},#],b_/;b>=#,2]&

```

Try it online!

A port of @Neil's answer.

# Answer
> 0 votes
# Python3, 261 bytes

```
f=lambda n,c=[[1],[1],[1]]:c[-1][-1]if c[-1][-1]>=n else(f(n,c[:-1]+[(c[-1]+[c[-1][-1]+k[len(c[-1])-1]if len(k:=c[len(c)>4 and -5]+([]if len(c)<4 else[c[-4][0]]))>=len(c[-1])else c[-1][0]])])if all(len(c[-1])<= len(i)for i in c[-3:-1])else f(n,c+[[c[-1][-1]]]))

```

Not a very fancy solution, at each recursive call, builds a side of the spiral square.

Try it online!

# Answer
> 0 votes
# , 91 bytes

```
function(x,m=t(1)){while(x>max(m))m=rbind(cumsum((m=t(m[,ncol(m):1]))[1,]),m);min(m[m>=x])}

```

Try it online!

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


# Question
Title: AoCG2021 Day 10: Memory reallocation routine
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

Related to AoC2017 Day 6.

---

A debugger program here is having an issue: it is trying to repair a memory reallocation routine, but it keeps getting stuck in an infinite loop.

In this area, there are `n` memory banks; each memory bank can hold any number of blocks. The goal of the reallocation routine is to balance the blocks between the memory banks.

The reallocation routine operates in cycles. In each cycle, it finds the memory bank with the most blocks (ties won by the lowest-numbered memory bank) and redistributes those blocks among the banks. To do this, it removes all of the blocks from the selected bank, then moves to the next (by index) memory bank and inserts one of the blocks. It continues doing this until it runs out of blocks; if it reaches the last memory bank, it wraps around to the first one.

For example, if there are initially four banks with `[0, 2, 7, 0]` memory blocks:

* The third bank is freed, and starting with the next (fourth) bank, the 7 blocks are cyclically spread out over the memory banks. After one cycle, the result looks like `[2, 4, 1, 2]`:

```
 0   2   0   0
            +1
+1  +1  +1  +1
+1  +1
--------------
 2   4   1   2

```
* In the next cycle, the second bank is freed and redistributed, resulting in `[3, 1, 2, 3]`.
* In the next cycle, the first bank is freed (when there are ties, the first bank is chosen), giving `[0, 2, 3, 4]`.
* Next cycles give `[1, 3, 4, 1]`, then `[2, 4, 1, 2]`, where the sequence forms a loop.

Your job is to simulate one cycle of memory reallocation.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
[0, 2, 7, 0] -> [2, 4, 1, 2] -> [3, 1, 2, 3] -> [0, 2, 3, 4]
-> [1, 3, 4, 1] -> [2, 4, 1, 2]
[3, 1, 4, 1, 5, 9, 2] -> [5, 2, 5, 2, 6, 1, 4]
-> [6, 3, 6, 3, 0, 2, 5] -> [0, 4, 7, 4, 1, 3, 6]
-> [1, 5, 1, 5, 2, 4, 7] -> [2, 6, 2, 6, 3, 5, 1]
-> [3, 0, 3, 7, 4, 6, 2] -> [4, 1, 4, 1, 5, 7, 3]
-> [5, 2, 5, 2, 6, 1, 4]

```

# Answer
> 6 votes
# BQN, 33 bytes

```
{+˝↑‿(≠)⥊∾(⥊⟜0∾(-∾⥊⟜1)∘⊑⟜)⊑⍒}

```

Try it online!

```
{+˝↑‿(≠)⥊∾(⥊⟜0∾(-∾⥊⟜1)∘⊑⟜)⊑⍒} # Example input:  = 0 2 7 0
                                ⊑⍒  # The first index of the maximum value  2
                           ⊑⟜      # The value at that index               7
                    -∾⥊⟜1           # negative value, value many 1's
                                     # ¯7 1 1 1 1 1 1 1
             ⥊⟜0∾                   # Prepend index many 0's
                                     # 0 0 ¯7 1 1 1 1 1 1 1
          ∾                         # 0 2 7 0 0 0 ¯7 1 1 1 1 1 1 1
   ↑‿(≠)⥊                           # Reshape into a matrix with length() columns, padding the last row with 0's
 +˝                                  # sum the columns

```

# Answer
> 5 votes
# , 37 bytes

```
(0:`]`[}+/@,-@#@[]\0,0 1#~],{~)]i.>./

```

Try it online!

Consider input `0 2 7 0`:

* `(...)]i.>./` Entire verb is a hook giving the verb in parens the original input as a left arg, and the max value's index `i.>/.` as the right. It evaluates like:

```
0 2 7 0 (...) 2  NB. 2 is the index of 7.

```
* `(0 1#~],{~)` Append the max's index to the max `],{~` and copy `0 1` elementwise that many times:

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

```
* `0,` Prepend another 0:

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

```
* `-@#@[]\` Fold that into original-input-sized chunks, filling empty slots in the last row with 0:

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

```
* `0:`]`[}...,` Prepend to that the original list, with the max value zeroed out:

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

```
* `+/@` And sum the rows:

```
2 4 1 2

```

# Answer
> 4 votes
# , 84 bytes

```
function(a){v=a[i<-which.max(a)]+1;a[i]=0;while(v<-v-1)a[i]=a[i<-i%%sum(a|1)+1]+1;a}

```

Try it online!

Note that in `a[i]=a[i<-i%%sum(a|1)+1]+1`, `i` is first updated on the RHS and then substitution is performed with the same index on LHS and RHS.

# Answer
> 3 votes
# JavaScript (ES6), 66 bytes

Updates the input array.

```
a=>{for(a[i=a.indexOf(m=Math.max(...a))]=0;m--;)a[++i%a.length]++}

```

Try it online!

# Answer
> 3 votes
# Pari/GP, 65 bytes

```
a->for(i=1,c=a[m=vecsort(-a,,1)[1]],a[(m+i-1)%#a+1]+=1);a[m]-=c;a

```

Try it online!

---

# Pari/GP, 69 bytes

```
a->c=a[m=vecsort(-a,,1)[1]];a+Vecrev((x^c\(x-1)-c/x)*x^m%(1-x^#a),#a)

```

Try it online!

Longer but more interesting.

See the input as a polynomial, e.g. `[0, 2, 7, 0]` becomes \\$2x+7x^2\\$. Let \\$c\ x^{m-1}\\$ be its term with the largest coefficient (in this case, \\$c=7,m=3\\$). Then we subtract \\$c\ x^{m-1}\\$ from the polynomial, and then add \\$(x^m+x^{m+1}+\cdots+x^{m+c-1}) \bmod (x^n-1)\\$, where \\$n\\$ is the length of the input.

# Answer
> 3 votes
# Ruby, 59 bytes

```
->a{a[i=a.index(m=a.max)]=0;m.times{a[a[i+=1]?i:i=0]+=1};a}

```

Try it online!

# Answer
> 3 votes
# , ~~78~~ 77 bytes

*Edit: -1 byte and re-arranged to an almost-readable format thanks to pajonk*

```
function(x){x[m<-match(n<-max(x),x)]=0;a=x%*%t(!1:n);a[m+1:n]=1;rowSums(a)+x}

```

Try it online!

First we construct a matrix `a` of length(`x`) rows and `n`=max(`x`) zeros (using a golfy trick: `x%*%t(!1:n)`).
fills matrices row-first if we use 1-dimensional indices, so we can fill the matrix with `1`s at positions from `m+1` up to `m+n`, where `m` is the position of the maximum element of `x`, and the row sums will give the amounts we need to add to each index of `x`.
So now we just need to set the `m`-th element of `x` to zero, and add the row sums of `a`.

# Answer
> 2 votes
# C (clang), 78 bytes

```
h;m;i;f(*b,n){for(i=m=0;i<n;++i)m=m<b[i]?b[h=i]:m;for(b[h]=0;m--;)++b[++h%n];}

```

Try it online!

Inputs a pointer to an array of memory banks and its length (because pointers in C carry no length info).
Reallocates the memory in place - of course!!! :)))

# Answer
> 2 votes
# Charcoal, 27 bytes

```
ＩＥθ⁺∧⁻⌕θ⌈θκι÷⁺⌈θ﹪⁻⌕θ⌈θκＬθＬθ

```

Try it online! Link is to verbose version of code. Explanation: The number to be added to each cell (or replacing the maximum cell) equals the maximum cell divided by the length of the array, but adjusting for the cyclic difference between the two cells, which distributes the remainder.

```
  θ                         Input array
 Ｅ                          Map over elements
       θ                    Input array
      ⌕                     Find index of
         θ                  Input array
        ⌈                   Maximum value
     ⁻                      Minus
          κ                 Current index
    ∧                       Logical And
           ι                Current value
   ⁺                        Plus
               θ            Input array
              ⌈             Maximum value
             ⁺              Plus
                   θ        Input array
                  ⌕         Find index of
                     θ      Input array
                    ⌈       Maximum value
                 ⁻          Minus
                      κ     Current index
                ﹪           Modulo
                        θ   Input array
                       Ｌ    Length
            ÷               Integer divided by
                          θ Input array
                         Ｌ  Length
Ｉ                           Cast to string
                            Implicitly print each value on its own line

```

I misread the question, so I originally wrote a 43 byte program to find the loop:

```
Ｗ¬№υθ«⊞υ✂θＵＭθ⁺∧⁻⌕θ⌈θλκ÷⁺⌈θ﹪⁻⌕θ⌈θλＬθＬθ»⊞υθＩυ

```

Try it online! Link is to verbose version of code. Outputs using Charcoal's default array format, which is each element on its own line and rows double-spaced.

# Answer
> 2 votes
# 05AB1E (legacy), ~~19~~ 18 bytes

```
DZ©kÅ0®(®Å1)˜IgôζO

```

-1 byte by switching to the legacy version of 05AB1E, where the sum ignores strings inside integer-lists.

Try it online or verify all test cases.

Luckily we don't have to find the cycle, since that would have been 30 bytes (and very slow) due to 05AB1E's lack of get\_index builtin for sublists.

**Explanation:**

```
               #  e.g. input = [0,2,7,0]
D              # Duplicate the (implicit) input-list
               #  STACK: [0,2,7,0],[0,2,7,0]
 Z             # Push its maximum (without popping the list)
               #  STACK: [0,2,7,0],[0,2,7,0],7
  ©            # Store this maximum in variable `®` (without popping)
   k           # Get the 0-based index of this maximum in the list
               #  STACK: [0,2,7,0],2
    Å0         # Pop and push a list of that many 0s
               #  STACK: [0,2,7,0],[0,0]
 ®             # Push the maximum from variable `®`
  (            # Negate it
               #  STACK: [0,2,7,0],[0,0],-7
 ®             # Push the maximum from variable `®` again
  Å1           # Pop and push a list of that many 0s
               #  STACK: [0,2,7,0],[0,0],-7,[1,1,1,1,1,1,1]
      )        # Wrap everything on the stack into a list
       ˜       # Flatten it
               #  STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1]
        Ig     # Push the input-length
               #  STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1],4
          ô    # Split the list into parts of that size
               #  STACK: [[0,2,7,0],[0,0,-7,1],[1,1,1,1],[1,1]]
           ζ   # Zip/transpose; swapping rows/columns,
               # using a space as default filler-item if the matrix is irregular
               #  STACK: [[0,0,1,1],[2,0,1,1],[7,-7,1," "],[0,1,1," "]]
            O  # Sum each inner list, ignoring the spaces
               #  STACK: [2,4,1,2]
               # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Python 3.8, ~~81~~ ~~79~~ 77 bytes

```
def f(a):
 k=a.index(m:=max(a))
 for i in range(k,m-~k):a[i%len(a)]+=i>k or-m

```

-2 bytes thanks to *@loopyWalt*.

Modifies the input-list.

Try it online.

**Explanation:**

```
def f(a):     # Function with list parameter:
 k=a.index(m:=max(a))
              #  Set `m` to the maximum of the list
              #  And set `k` to the first 0-based index of this maximum
 for i in range(k,m-~k):
              # Loop `i` in the range [k,m+k]:
   a[i%len(a) #  `i` modulo the list-length to prevent IndexErrors
    ]+=       #  And increase the value at this modular index by:
       i>k    #   1 if `i` is larger than `k`
        or-m  #   or the negative maximum otherwise (if i==k in the first iteration)

```

# Answer
> 1 votes
# Java 8, 85 bytes

```
a->{int l=0,m=0,j=0;for(int i:a){if(i>m){m=i;j=l;}l++;}for(a[j]=0;m-->0;)a[++j%l]++;}

```

Modifies the input-array.

Try it online.

**Explanation:**

```
a->{              // Method with integer-array parameter and no return
  int l=0,        //  Length, starting at 0
      m=0,        //  Max, starting at 0
      j=0;        //  Max-index, starting at 0
  for(int i:a){   //  Foreach over the integers of the input:
    if(i>m){      //   If the current integer is larger than the max
      m=i;        //    Replace the max with this integer
      j=l;}       //    And replace the max-index with the 'length' thus far
    l++;          //   At the end of the iteration, increase the length by 1
  }               //  After the first loop:
  for(a[j]=0;     //  Replace the max at the max-index with 0
      m-->0;)     //  Loop the max amount of times:
    a[++j         //   Increase the max-index by 1 first
         %l       //   Then modulo it by the determined array-length
           ]++;}  //   And increase the integer at that index by 1

```

# Answer
> 1 votes
# MathGolf, 30 bytes

```
╙`=º*\ª*hb*\Γ─h(?£/{\;\£‼≥<^mΣ

```

Try it online.

Sometimes this language can be so annoying to program in.. MathGolf lacks a builtin to split integer-lists into sublists; it also lacks a transpose builtin for matrices; the (do-)while builtins only work for everything before it, not for portions near the end; and it lacks a builtin to push an implicit input-list (so those can only be accessed again by swapping) - using an explicit input-list is also 30 bytes. Because of that, the trailing `h(?£/{\;\£‼≥<^mΣ` does what we we want to do manually (it basically accomplishes the same as `IgôζO` in my 05AB1E answer, but a lot more hacky..)

**Explanation:**

```
                #  e.g. input = [0,2,7,0]
╙               # Push the maximum of the (implicit) input-list
                #  STACK: 7
 `              # Duplicate the top two items
                #  STACK: [0,2,7,0],7,[0,2,7,0],7
  =             # Get the 0-based index of this maximum in the list
                #  STACK: [0,2,7,0],7,2
   º*           # Multiply this index by [0]
                #  STACK: [0,2,7,0],7,[0,0]
     \          # Swap the two two items so the max is at the top
                #  STACK: [0,2,7,0],[0,0],7
      ª*        # And multiply this max by [1]
                #  STACK: [0,2,7,0],[0,0],[1,1,1,1,1,1,1]
        h       # Push its length (without popping)
                #  STACK: [0,2,7,0],[0,0],[1,1,1,1,1,1,1],7
         b*     # Multiply it by -1 to negate it
                #  STACK: [0,2,7,0],[0,0],[1,1,1,1,1,1,1],-7
           \    # Swap the top two items
                #  STACK: [0,2,7,0],[0,0],-7,[1,1,1,1,1,1,1]
            Γ─  # Wrap the top four items into a list, and flatten
                #  STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1]

```

```
h               # Push the length (without popping)
                #  STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1],14
 (              # Decrease it by 1
                #  STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1],13
  ?             # Triple-swap to push the (implicit) input-list
                #  STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1],13,[0,2,7,0]
   £            # Pop and push its length
                #  STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1],13,4
    /           # Integer-division
                #  STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1],3
     {          # Loop that many times:
      \         #  Swap to unfortunately get the implicit loop-index at the top
                #   STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1],0
       ;        #  Discard the top of the stack
                #   STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1]
        \       #  Swap again to push the (implicit) input-list
                #   STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1],[0,2,7,0]
         £      #  Pop and push its length
                #   STACK: [0,2,7,0,0,0,-7,1,1,1,1,1,1,1],4
          ‼     #  Apply the following two builtins separated:
           ≥    #   Slice to get the items in the range [input-length,list-length)
           <    #   Slice to get the items in the range [0,input-length)
                #    STACK: [0,0,-7,1,1,1,1,1,1,1],[0,2,7,0]
            ^   #  Zip to create pairs
                #   STACK: [[0,0],[0,2],[-7,7],[1,0],[1],[1],[1],[1],[1],[1]]
             mΣ #  Map, and sum each inner list
                #   STACK: [0,2,0,1,1,1,1,1,1,1]
                # (after the loop, the entire stack joined is output implicitly)

```

# Answer
> 1 votes
# PHP, 76 bytes

```
for($a[$i=array_keys($a=&$argv,$m=max($a))[0]]=0;$m--;)$a[++$i%count($a)]++;

```

Try it online!

Modifies the input array in place. Now this answer troubles me. In PHP we can take arguments as an array in `$argv`, but the first entry is the file name (`".code.tio"` in TIO), which forces me to do `array_shift($argv)` to get rid of this entry. After verifying on meta, we can take the input by reference and change it in place even for a full program, but cannot assume the input is stored in predefined variables. If I leave the `array_shift($argv)` as part of the program, it would mean that I consider the input format as different from the question (a string followed by our numeric values), and we cannot loop over it of else the array would shrink with each iteration.. so here are all the versions.. Anyone can rule this out?

# PROBABLY INVALID: PHP, 69 bytes

```
for($a[$i=array_keys($a,$m=max($a))[0]]=0;$m--;)$a[++$i%count($a)]++;

```

Try it online!

**If I had to include the `array_shift($argv)` in the code, it would be shorter to use a function (note that I can't use a loop in a PHP arrow function):**

# PHP, 84 bytes

```
function(&$a){for($a[$i=array_keys($a,$m=max($a))[0]]=0;$m--;)$a[++$i%count($a)]++;}

```

Try it online!

# Answer
> 1 votes
# TypeScript Types, 584 bytes

```
//@ts-ignore
type a<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type b<T,U=T>=T extends T?Exclude<T,Partial<Exclude<U,T>>>:0;type c<T,N=[]>=`${T}`extends`${N["length"]}`?N:c<T,[...N,0]>;type d<A,B,N=[]>=A extends[...B,...infer A]?d<A,B,[...N,0]>:[N,A];type M<A,T={[K in keyof A]:c<A[K]>},i=a<{[K in keyof T]:T[K]extends b<T[number]>?c<K>:never}[number]>,I=i["length"],X=d<T[I],c<T["length"]>>>={[K in keyof T]:(K extends`${I}`?X[0]:[...X[0],...T[K],...c<K>extends[...i,...Partial<X[1]>]|Partial<[...i,...X[1]]extends[...c<T["length"]>,...infer A]?A:never>?[0]:[]])["length"]}

```

Try It Online!

## Ungolfed / Explanation

<pre><code>// Filters a union of tuples for those with the shortest length
type Shortest<T, K = keyof T> = T extends T ? keyof T extends K ? T : never : 0

type Max<T, U = T> = T extends T ? Exclude<T, Partial<Exclude<U, T>>> : 0

// Converts a number to a tuple of equal length (this version also supports strings)
type NumToTuple<T, N = []> = `${T}` extends `${N["length"]}` ? N : NumToTuple<T, [...N, 0]>

// Returns [A / B, A % B]
type DivRem<A, B, N = []> = A extends [...B, ...infer A] ? DivRem<A, B, [...N, 0]> : [N, A];

type Main<
  _Banks,
  // Convert every number in the input to a tuple
  Banks = { [K in keyof _Banks]: NumToTuple<_Banks[K]> },
  FreeIndTup = Shortest<
    // Find the indices of Input where the value is equal to the max
    { [K in keyof Banks]: Banks[K] extends Max<Banks[number]> ? NumToTuple<K> : never }[number]
  >,
  FreeIndNum = FreeIndTup["length"],
  // The first number is the number of blocks every bank recieves (NewBlockMin)
  // The second is the number of banks that recieve one extra bank (ExtraCount)
  BlockDist = DivRem<Banks[FreeIndNum], NumToTuple<Banks["length"]>>
  // @ts-ignore
> = {
  // Map over Banks:
  [K in keyof Banks]: (
    K extends `${FreeIndNum}`
      // If this Bank is the one being freed, return NewBlockMin
      ? BlockDist[0]
      // Otherwise, sum:
      : [
          // The old value
          ...Banks[K],
          // NewBlockMin
          ...BlockDist[0],
          // 1 if the index meets one of the following critera, or 0 otherwise:
          ...NumToTuple<K> extends
            // Between FreeInd and FreeInd + ExtraCount
            | [...FreeIndTup, ...Partial<BlockDist[1]>]
            // Or, if FreeInd + ExtraCount > Banks.length, less than (FreeInd + ExtraCount) - Banks.length
            | Partial<
                [...FreeIndTup, ...BlockDist[1]] extends [...NumToTuple<Banks["length"]>, ...infer A]
                  ? A
                  : never
              >
            ? [0]
            : []
        ]
  )["length"];
};
```
</code></pre>

# Answer
> 1 votes
# Rust, 205 bytes

```
|x:&[_]|{let(mut r,mut v)=(vec![],x.to_vec());while!r.contains(&v){r.push(v.to_vec());let(n,i)=(0..).zip(r.last()?).map(|a|(a.1,!a.0)).max()?;v[!i]=0;for j in!i+1..=!i+n{v[j%x.len()]+=1}}r.push(v);Some(r)}

```

Try it online!

# Answer
> 0 votes
# Python3, 162 bytes :

```
f=lambda b,c=0,i=0,k=[]:k+[b]if b in k else(f(b[:(i:=b.index((m:=max(b))))]+[0]+b[i+1:],m,i+1,k+[b])if not c else f(b[:(j:=i%len(b))]+[b[j]+1]+b[j+1:],c-1,j+1,k))

```

Try it online!

# Answer
> 0 votes
# Wolfram Language (Mathematica), 78 bytes

```
(a=#;a[[Mod[m+i,Tr[1^a],1]]]++~Do~{i,c=a[[m=Tr@Ordering[-a,1]]]};a[[m]]-=c;a)&

```

Try it online!

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


title: AoCG2021 Day 12: Oct's Fool

text:
# Question
Title: AoCG2021 Day 12: Oct's Fool
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

The story continues from AoC2017 Day 11.

Obligatory why me and not Bubbler link

---

After having rescued a child process lost on a hexagonal infinite grid, you hear someone else screaming for help. You turn around, and unsurprisingly, there is another program looking for its *own* child process. "Help! It's gotten lost in an infinite octagonal grid!"

Well, it's not *all* octagonal, obviously. Instead, it's actually a 4-8-8 tiling:

An octagonal tile (X) has eight neighbors, indicated by eight directions (N, NE, E, SE, S, SW, W, NW). A square tile (Y) has only four neighbors in cardinal directions (N, E, S, W).

The program gives you the path taken by the child process. The initial tile is an octagon. You try following the directions one by one, and ... something's wrong in the middle. "Look, it can't move diagonally from a square tile, you see?"

Given a sequence of movements, determine if it is valid on the 4-8-8 grid, assuming the initial position of an octagon.

**Input:** A list of strings entirely consisting of `N`, `NE`, `E`, `SE`, `S`, `SW`, `W`, `NW`. Or a single string containing these strings with a single delimiter (space, comma, newline, or any other char that is not one of `NESW`) in between. (If the input is `["N", "E", "NW", "NE", "E", "SE"]` then you can take it as e.g. `"N,E,NW,NE,E,SE"`)

**Output:** A value indicating whether it is valid or not. You can choose to

* output truthy/falsy using your language's convention (swapping is allowed), or
* use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Truthy:

```
[]
["S"]
["SW"]
["N", "E", "NW", "NE"]
["NE", "SE", "SW", "NW", "N", "E", "S", "W"]

```

Falsy:

```
["N", "E", "NW", "NE", "E", "SE"]
["NE", "SE", "N", "E", "S", "SW", "NW", "W"]
["N", "NW"]

```

# Answer
# Regex (any), 27 bytes

```
^((.\n.\n)*..\n?)*(.\n)*.?$

```

Matches valid strings, taking input as a newline-separated string. There's probably a way to golf this regex. This version thanks to @AnttiP.

# Javascript, 34 bytes

```
/^((.\n.\n)*..\n?)*(.\n)*.?$/.test

```

Try it online!

```
^                          From the start...
 (             )*          Match 0+ times...
  (      )*                Match 0+ times...
   .\n.\n                  A pair of 1-char strings
           ..\n?           Followed by a 2-char string with possible separator (in case this is the end)
 (             )*          This block will match 2-char strings until the end as long as the 1-char strings are paired
                 (.\n)*    Match any amount of . after this
                       .?$ Match possible trailing . at the end

```

This relies on the fact that length 1 strings modify the parity of whether we're on an octagon or square, and whether diagonal (length-2 strings) are valid.

## Old version, 35 bytes

```
^(((\S\S )*\S ){2})*(\S\S )*\S \S\S

```

Matches invalid strings, taking input space-separated.

```
^                                   From the start...
 ((           ){2})*                Match an even number of times...
   (\S\S )*                         Possibly any amount of length-2 strings
           \S                       Followed by a length-1 string
                    (\S\S )*        Possibly match any amount of length-2 strings
                            \S \S\S Match a length-1 string followed by a length-2 string.

```
> 8 votes

# Answer
# Python 2, 45, 44, 36 bytes (@Jonathan Allan)

```
lambda a:`a.title()`[1::2]>`a`[1::2]

```

Try it online!

#### Older versions

```
lambda a:repr(a.title())[1::2]>repr(a)[1::2]

```

Try it online!

```
lambda a:(A:=repr(a.title())[1::2])>A.upper()

```

Try it online!

#### Explanation (all versions)

This expects a backslash- (or tab- or newline-) separated string and returns True for invalid and False for valid paths.

It works by detecting odd-length stretches of single-character commands followed by at least one double-character command.

The idea is essentially: if we had `X` for principal directions and `XY` for the others we could just concatenate take every other character and check for `Y`s.

Almost as good is to `title`-case the input string which puts a capital instead of `X` and a small instead of `Y`.

Now, I found no cheap way of getting rid of the delimiter, but almost as good we use backslash or tab or newline and apply `repr`. This replaces each separator with its two-character escaped representation such that they do not interfere with parity.

It remains to check for any lowercase letters which we do by comparing with `upper` whether any differences with the non title cased inputs have survived the skipping step.
> 8 votes

# Answer
# , ~~46~~ ~~43~~ 42 bytes

*Edit: -1 byte thanks to pajonk*

```
function(s)any(cumsum(x<-nchar(s))%%2&x>1)

```

Try it online!

Function `notvalid`: outputs `TRUE` if the path is not valid, `FALSE` if it's a valid path.

**How?**
If the path is valid, then 2-character moves (that can only be from an octagon) always move to an octagon; 1-character moves flip between octagons & squares. So, we're in a square if we've had an odd number of 1-character moves.
Invalid moves are attempted 2-character moves from squares, so we need to check if any of these co-incide with positions after an odd number of 1-character moves.

`any(...)` = is this question TRUE value at any position:
`cumsum(x)%%2` = have we had an odd number of 1-character moves?
`&x>1` = and, if so, is x currently 2?
> 7 votes

# Answer
# Jelly, 6 bytes

```
ẈÄPƝḂẸ

```

A mondadic Link that accepts a list of lists of characters and yields `0` if valid or `1` if invalid.

**Try it online!**

### How?

The only way to reach a square is via a sequence of an odd number of cardinal directions, after which if a diagonal direction is given the input is invalid. The cardinal directions are length one, while diagonal ones are length two. Thus if the cumulative sum of lengths of the input contains two odd numbers in a row it is an invalid instruction.

```
ẈÄPƝḂẸ - Link: instuctions
Ẉ      - length of each instruction
 Ä     - cumulative sums -> odd when taken to a square given a valid prefix
   Ɲ   - for neighbours:
  P    -   product (only odd * odd is odd)
    Ḃ  - is odd? (vectorises)
     Ẹ - any?

```
> 6 votes

# Answer
# Ruby, ~~33 32~~ 29 bytes

```
->l{l.all?{|y|y[1]?l:[l=!l]}}

```

Try it online!

Look ma, no regex!

### How?

Reuse l as a flag that is initialized with a truthy value, and translates as true-\>octagon, false-\>square. The sequence is invalid if we have to move diagonally (y\[1\] is true when y is 2 characters long) from a square (l is false). If y is only 1 character, we are moving from an octagon to a square or viceversa, so we have to flip the flag. This is enclosed in an array to make the operation return a truthy value.
> 5 votes

# Answer
# Vyxal, 9 bytes

```
vL:‹$¦∷*a

```

Try it Online!

There's got to be a better way to do this. Outputs reversed - 1 for invalid, 0 for valid,

```
vL        # Lengths
     ¦∷   # Cumulative sums modulo 2, tracking when on a square and when not
    $  *  # Multiplied by
  :‹      # Those same lengths decremented
          # Each one is only true when on a square *and* trying to move diagonally
          # Which is invalid
        a # Are any true? If so, there's an invalid one somewhere.

```
> 4 votes

# Answer
# Retina 0.8.2, 20 bytes

```
^(\w,?($|\w($|,)))*$

```

Try it online! Link includes test cases. Explanation: The regular expression only matches valid movements, i.e. those that only contain paired or trailing orthogonal directions. 18 bytes if newlines are allowed as separators:

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

```

Try it online! Link includes test suite that splits on comma for convenience.
> 4 votes

# Answer
# Charcoal, 15 bytes

```
⬤θ›³⁺﹪Ｌ⪫…θκω²Ｌι

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean i.e. `-` for valid, nothing for invalid. Explanation: An input is valid if the cumulative length modulo 2 plus the length of the current item never exceeds 2.
> 4 votes

# Answer
# Pari/GP, 32 bytes

```
a->t=0;[t=[1-t,t*x][#d]|d<-a];t'

```

Try it online!

Here `t` is the state of the current tile: `0` means octagon, `1` means square.

When the direction has length 1, we just set `t` to `1-t`. If the length is 2, we multiply `t` by `x`, so `0` remains `0`, while `1` becomes a polynomial. If `t` is a polynomial, `1-t` and `t*x` are also polynomials. So invalid states are represented by polynomials.

Finally, we take the derivative of `t`. The derivative of a constant is `0`, which is falsy. The derivative of non-constant polynomials are truthy.
> 3 votes

# Answer
# Python,  ~~48~~  47 bytes

```
f=lambda a,o=1:o>1or a and f(a[1:],len(a[0])-o)

```

A recursive function that accepts a list of strings and returns an empty list (`[]`) if the input is valid or `True` if not.

**Try it online!**

### How?

`a` is our list of instructions.

`o` starts off as `1` (`,o=1`) and is a flag that indicates whether we are on an octagon (`1`) or square (`0`), this is updated for the next iteration by subtracting the current flag value from the current instruction length (`len(a[0])-o`).

If we try to go diagonally from a square then `o` becomes `2` (since \\$2-0=2\\$) and then the next iteration's evaluation of `o>1` causes a return value of `True`.

We drop the first (now executed) instruction from `a` (`a[1:]`) in order to perform the next iteration and if we find ourselves with an empty list the instructions were valid and `or a` causes this empty list to be returned.
> 3 votes

# Answer
# , 55 bytes

```
f=function(x,o=1)o>1||length(x)&&f(x[-1],nchar(x[1])-o)

```

Try it online!

Port of @Jonathan Allan's recursive answer.

Outputs flipped `TRUE/FALSE`.
> 3 votes

# Answer
# Rust, 80 56 bytes

```
|p:&[&str]|p.iter().fold(0,|a,b|a+a%b.len()^b.len()&1)<2

```

Try it online!

* -24 bytes by using fold and boolean operations (thanks @AnttiP)
> 3 votes

# Answer
# Python3, 82 bytes:

```
f=lambda x,s=0:((b:=len(x[0])==1)or s%2==0)and f(x[1:],s+b)if x else s%2==0 or s<2

```

Try it online!
> 2 votes

# Answer
# BQN, 13 bytesSBCS

```
∨˝2|·×⟜»·+`≠¨

```

Run online!

Exact port of Jonathan Allan's Jelly answer. There are a few things that can be varied, e.g. `1∊1‿1⍷·≠`2|≠¨` works at the same length, but I couldn't find anything shorter.
> 2 votes

# Answer
# Ruby, ~~39~~ 34 bytes

```
->i{/^((.,){2}*(.\w,)*)*.,.\w/!~i}

```

Try it online!

Method takes string with commas and returns true if the path is valid. The regexp looks for invalid path which is essentially an odd one-letter direction followed by a two-letter.

Thanks to ovs for very useful suggestions and -5 bytes!

Another less golfy but more interesting for me version doesn't work on TIO but takes arrays instead of strings and is 54 bytes:

```
f=->t{c=0;t.chunk{_1[1]?1:2}.all?{2>c+=_1*c+_2.size%_1}}

p f[[]]
p f[["S"]]
p f[["SW"]]
p f[["N", "E", "NW", "NE"]]
p f[["NE", "SE", "SW", "NW", "N", "E", "S", "W"]]
# falsy
p f[["N", "E", "NW", "NE", "E", "SE"]]
p f[["NE", "SE", "N", "E", "S", "SW", "NW", "W"]]
p f[["N", "NW"]]

```
> 2 votes

# Answer
**Turing Machine Code, ~~97~~ 77 bytes**

```
0 _ _ r halt
0 * * r 1
1 _ _ r 2
1 * * r 3
2 * * r 3
3 _ _ r 0
3 * * r halt-r

```

Try it online

Takes space-separated input, thanks to AntiP for saving 20 bytes

Haven't tested on my Java implementation yet
> 2 votes

# Answer
# Husk, 8 bytes

```
ṁ%2Ẋ*∫mL

```

Try it online!

Approach based on Jonathan Allan's Jelly answer. Outputs zero (falsy) for valid paths, non-zero (truthy) for non-valid paths.

```
      mL  # get the lengths of the input strings
     ∫    # and calculate the cumulative sum
          # (so odd numbers indicate we're in a square)
   Ẋ*     # product of all adjacent pairs
          # (so odd numbers indicate a 2-character move
          # attempted from within a square)
ṁ%2       # map 'modulo 2' to all elements (gets odd numbers)
          # and output sum (non-zero if any elements were odd)

```
> 2 votes

# Answer
# Thue, 84 bytes

```
@::=:::
S::=N
E::=N
W::=N
aN,::=b
aNN,::=a
bN,::=a
a,::=~1
b,::=~1
bNN::=~0
::=
a@,,

```

Takes comma-separated input
> 2 votes

# Answer
# Wolfram Language (Mathematica), 41 bytes

```
FreeQ[Or@@StringLength@#/. 1||1->3,1||2]&

```

Try it online!
> 1 votes

# Answer
# TypeScript Types, 107 bytes

```
type M<T,A=1,B=0,D="N"|"S"|"E"|"W">=T extends[infer C,...infer T]?C extends D?M<T,B,A>:A extends 1?M<T>:0:1

```

Finally, one that didn't benefit from `//@ts-ignore`!

Try It Online!

## Ungolfed / Explanation

```
// DiagA: whether non-orthogonal moves are currently allowed
// DiagB: wtherer non-orthogonal moves are allowed in the other type of cell
type Main<Arr, DiagA = 1, DiagB = 0, OrthoDir = "N" | "S" | "E" | "W"> =
  // Check the first string in Arr
    Arr extends [infer Dir, ...infer Rest]
        ? Dir extends OrthoDir
      // If it's orthogonal, switch the type of cell
      ? Main<Rest, DiagB, DiagA>
      : DiagA extends 1
        // Otherwise, if diagonals are allowed, move into an octagonal cell (the default)
        ? Main<Rest>
        // Otherwise, return false
        : 0
    // The array is empty; return true
    : 1

```
> 1 votes

# Answer
# 05AB1E, 8 bytes

```
ηJ€gü*Éà

```

Input as a list of strings. Outputs `1` for invalid grids and `0` or an empty string `""` for valid grids (only `1` is truthy in 05AB1E, so this falls under the "*output truthy/falsy using your language's convention (swapping is allowed)*" rule).

Port of *@JonathanAllan*'s Jelly answer.

Try it online or verify all test cases.

**Explanation:**

```
η         # Get the prefixes of the (implicit) input-list
 J        # Join each inner prefix-list together to a single string
  €g      # Get the length of each string
    ü     # For each overlapping pair:
     *    #  Multiply them together
      É   # Check for each whether it's odd
       à  # And check if any were odd by leaving the maximum
          # (after which the result is output implicitly)

```

Empty or single-item inputs are `[]` after the `ü*`, which is why they result in an empty string `""`.
> 1 votes

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


title: Fully matched numbers

text:
# Question
Title: Fully matched numbers
For the context of this challenge, a *matched group* is a digit \\$n\\$, followed by \\$n\\$ more matched groups. In the case of \\$n = 0\\$, that's the whole matched group. Digits only go up to 9.

For example, 3010200 is a valid matched group, as:

```
3       # 3, capturing three elements...
 0      # a 0 (group 1)
 1      # a 1 (group 2), capturing...
  0     # a 0
 2      # And a 2 (group 3), capturing...
  0     # a 0
  0     # and another 0.

```

A *fully matched number* is simply any valid matched group.

The list begins:

```
0, 10, 110, 200, 1110, 1200, 2010, 2100, 3000, 11110, 11200, 12010, 12100, 13000, 20110, 20200, 21010, 21100, 22000, 30010, 30100, 31000, 40000

```

(As usual, these are hand-generated :P)

Your task is to implement this sequence.

Standard and rules apply.

## Testcases

These are zero-indexed. Last testcase thanks to tjjfvi.

```
0 -> 0
1 -> 10
4 -> 1110
6 -> 2010
9 -> 11110
13 -> 13000
18 -> 22000
22 -> 40000
64 -> 500000

```

# Answer
# APL (Dyalog Unicode), ~~29~~ 25 bytes

```
1+⍣{1∧.=⌊\⌽+\1-⌽⍎¨⍕⍺}⍣⎕⊢0

```

Try it online!

`⍣⎕⊢0`: Starting at 0, iterate input times:
`1+⍣{ ... }`: Increment until the new value is fully matched.

The number  is fully matched if:
`⍎¨⍕⍺`: base-10 digit list
`1-⌽`: 1 minus each digit in the reversed list
`+\`: cumulative sums of this list
`⌊\⌽`: minimum of each suffix
`1∧.=`: All minima are equal to `1`
> 8 votes

# Answer
# Jelly, 11 bytes

```
DCSÐƤ«\ỊƑø#

```

Try it online!

Port of ovs's APL solution. Full program.

```
         ø#    Starting from 0, collect the first [input] integers satisfying:
DC             Subtract each decimal digit from 1.
  SÐƤ          Take the sum of each suffix.
     «\        Are the cumulative minima
       ỊƑ      all equal to 1?

```

`ø#` works by placing `#` in a niladic chain with no leading nilad, supplying it `0` as a starting value (note that it takes the number of values to gather from the last argument to the program, rather than anything within the link). The condition that the cumulative minima of the suffix sums are all 1 is equivalent to that the sum of the entire list is 1 and no suffix sum is less than 1.
> 7 votes

# Answer
# Pip, 31 bytes

```
W1i:SNUQ$AL:{aRA_1+B.0MEa}M P*i

```

Outputs fully matched numbers indefinitely. Try it online!

### Explanation

Observe that every fully matched number (other than 0) can be generated from a shorter fully matched number by taking a digit from the shorter number, incrementing it, and inserting a 0 after it: for example, `1**0** -> 1**10**`; `**1**0 -> **20**0`. If we apply this procedure to every f.m. number of length N, we generate a list of all f.m. numbers of length N+1; but the list will contain some duplicates.

```
W1i:SNUQ$AL:{aRA_1+B.0MEa}M P*i
                                 i is 0 (implicit); we're going to use it to store
                                 the list of all f.m. numbers of a given length
W1                               While 1 (infinite loop):
                            P*i   Print each element of i
            {            }M       Map this function to each f.m number in i:
                      MEa          Map this function to each index and corresponding
                                   digit of the number:
             a                      The number
              RA_                   Replace at the current index
                 1+B                with 1 plus the digit
                    .0              concatenated to 0
        $AL:                      Flatten the resulting list
      UQ                          Uniquify
    SN                            Sort in numeric order
  i:                              Assign back to i

```
> 5 votes

# Answer
# Ruby, 53 bytes

```
0.step{|x|i=0;x.digits.all?{|d|0<i+=1-d}&&i==1&&p(x)}

```

Try it online!
> 5 votes

# Answer
# Python 2, 76 bytes

Inspired by ovs's Ruby answer.

```
n=0
while 1:
 i=t=1
 for d in`n`:t*=i>0;i+=int(d)-1
 if t>0==i:print n
 n+=1

```

Try it online!

### Explanation

For each number `n`, we loop over each digit `d` in its string representation. Let `i` begin at 1; at each digit, add that digit to `i` and subtract 1. Then for a number to be fully matched, `i` should never drop below 1 until after the last digit, when it should be exactly 0.

```
d:  2 0 1 0
i: 1 2 1 1 0

```

The `for` loop on the fourth line performs these calculations, tracking whether `i` is always greater than 0 in `t`. After the loop, if `t` is still 1 and `i` is 0, we print the number.
> 5 votes

# Answer
# TypeScript Types, 295 bytes

```
//@ts-ignore
type a<T,N=[]>=T extends`${N["length"]}`?N:a<T,[...N,0]>;type b<T,N="1",M=[]>=N extends`${M["length"]}`?T:b<T extends`${infer C}${infer T}`?b<T,C>:0,N,[...M,0]>;type M<I,J=[],N=[]>=b<`${N["length"]}`>extends""?I extends J["length"]?N["length"]:M<I,[...J,0],[...N,0]>:M<I,J,[...N,0]>

```

Try It Online!

Works for 0, 1, 2, and 3, and hits the recursion limit after that.

---

# TypeScript Types, 319 bytes

```
//@ts-ignore
type a<T,N=[]>=T extends`${N["length"]}`?N:a<T,[...N,0]>;type b<T,N="1",M=[]>=N extends`${M["length"]}`?T:b<T extends`${infer C}${infer T}`?b<T,C>:0,N,[...M,0]>;type M<I,J=[0],N=[]>=I extends 0?"0":b<`${N["length"]}0`>extends""?I extends J["length"]?`${N["length"]}0`:M<I,[...J,0],[...N,0]>:M<I,J,[...N,0]>

```

Try It Online!

Works for 0-8.
> 3 votes

# Answer
# Vyxal, 14 bytes

```
λfḂ⌐¦ḂKv↓1=Π;ȯ

```

Try it Online!

Takes an integer `n` and returns first `n` elements of the sequence.

-1 thanks to @lyxal
> 3 votes

# Answer
# Retina, 62 bytes

```
K`0
"$+"{`$
¶
/¶/{s`.+
2*$($.(*__)¶
+T`d`_d`[1-9]0(?=.*$)
¶0¶

```

Try it online! No test suite due to the way the program uses history. Outputs the `n`th fully matched number. Explanation:

```
K`0

```

Replace the input with zero.

```
"$+"{`

```

Repeat the script `n` times.

```
$
¶

```

Append a newline to make a working area to verify fully matched numbers.

```
/¶/{`

```

Repeat while the working area contains a newline.

```
s`.+
2*$($.(*__)¶

```

Increment the current value and duplicate it into the working area, deleting any previous content.

```
+T`d`_d`[1-9]0(?=.*$)

```

Attempt to reduce the working area to a single `0`; any zero after a non-zero digit can be removed and the preceding digit decremented.

```
¶0¶

```

If the current value was fully matched then delete the working area, needed to avoid cluttering up the output, but also causing the inner loop to terminate.
> 2 votes

# Answer
# Husk, 13 bytes

```
¥1mödm¬Go←+dN

```

Try it online!

Inspired by DLosc's and ovs's answers.

```
  mö        N  # for all natural numbers:
           d   # get the decimal digits,
       Go←+    # subtract one, & get the cumulativ sum;
               # now we want those with a final zero, and
               # no preceding zero:
     m¬        # logical not of all elements (zeros become 1s)
    d          # convert digits to decimal number;
¥1             # finally output whenever the answer is 1.

```
> 2 votes

# Answer
# Haskell, ~~70~~ 69 bytes

```
filter(0#)[0..]
a#x=a!divMod x 10
a!(d,m)|d<1=a==m|c<-a-m+1=m<=a&&c#d

```

Try it online!

* Thanks to @Unrelated String for saving 1 by using filter instead of list comprehension.
* *k* is an infinite sequence

We start from the end checking if the last digit(m) doesn't consume more groups than available `a` *a-m\>=0*

Then we remove `m` groups and add 1 *a=a-m+1* and move backwards.

At the end we must have exactly one group *a-m+1==1*

```
3010200
      m  a   a=a-m+1
      0  0   1
     0   1   2
    2    2   1
   0     1   2
  1      2   2
 0       2   3
3        3   1

```
> 2 votes

# Answer
# 05AB1E (legacy), 14 bytes

```
µ1NS-.sO.s€ßΘP

```

Given \\$n\\$, it outputs the 0-based \\$n^{th}\\$ value.

Uses the legacy version of 05AB1E, which outputs `N` implicitly after a while-loop. In the new version of 05AB1E, this program required an additional trailing `}N` to work.

Port of *@ovs*' APL answer.

Try it online or verify outputs until it times out on TIO.

**Explanation:**

```
µ              # While the counter_variable is not equal to the (implicit)
               # input-integer (the counter_variable is 0 by default):
  N            #  Push the current 0-based loop-index
   S           #  Convert it to a list of digits
 1  -          #  Subtract each from 1
     .s        #  Get the suffices of this list
       O       #  Sum each inner suffix-list
        .s     #  Get the suffices of this list again
          €ß   #  Get the minimum of each inner suffix-list
            Θ  #  Check for each that they're equal to 1
             P #  And check if this is truthy for all of them
               #  (if this is 1: implicitly increase the counter_variable by 1)
               # (after the while-loop, the resulting index is output implicitly)

```
> 2 votes

# Answer
# JavaScript (ES6), 71 bytes

Returns the n-th term, 1-indexed.

Based on ovs' Ruby answer.

```
n=>eval("for(k=-1;n-=!(i=g=n=>n?(i=-~i-n%10)<1|g(n/10|0):i-1)(k);)++k")

```

Try it online!
> 1 votes

# Answer
# Python3, 182 bytes:

```
f,n=lambda x,c=[1]:f(x,c[:-2]+[c[-2]-1])if c[-1]==0 and len(c)>1 else(len(c)==1 and c[0]==0if not x else f(x[1:],c+[x[0]])),0
while(n:=n+1):
 if f(list(map(int,str(n-1)))):print(n-1)

```

Try it online!
> 1 votes

# Answer
# Vyxal, 15 bytes

```
λf⌐ṘKṠ₍tg1=A;ȯt

```

Try it Online!

Mmm yes apl porting. Outputs nth fully matched number 0 indexed
> 1 votes

# Answer
# Charcoal, 34 bytes

```
≔⁰ηＦＮ«⟦Ｉη⟧≦⊕ηＷ∨⁻Ση⊖Ｌη⊙Ｉη‹Σ…Ｉημμ≦⊕η

```

Try it online! Link is to verbose version of code. Outputs the first `n` numbers (could be trivially modified to output the 0-indexed `n`th number for the same byte count). Explanation:

```
≔⁰η

```

Start with `0`.

```
ＦＮ«

```

Loop `n` times.

```
⟦Ｉη⟧

```

Output the found fully matched number.

```
≦⊕η

```

Try the next number.

```
Ｗ∨⁻Ση⊖Ｌη⊙Ｉη‹Σ…Ｉημμ≦⊕η

```

Keep trying the next number until a fully matched number is found. This is identified as a number having a digit sum of one less than its length but none of whose prefixes are a fully matched number.
> 1 votes

---
Tags: code-golf, sequence, parsing
---


title: Define the finite field GF(9)

text:
# Question
Title: Define the finite field GF(9)
\\$GF(9)\\$ or \\$GF(3^2)\\$ is the smallest finite field whose order isn't a prime or a power of two. Finite fields of prime order aren't particurlarly interesting and there are already challenges for \\$GF(2^8)\\$ (link) and \\$GF(2^{64})\\$ (link).

### Challenge

First define nine elements of the field. These must be *distinct integers from 0 to 255,* or the one-byte characters their code points represent. State in your answer which representation you choose.

Then implement two binary operations, addition and multiplication, satisfying the field axioms:

* Both operations must be commutative and associative.
* Addition has the identity element \\$0\\$ and an additive inverse for each element.
* Multiplication has the identity element \\$1\\$ and a multiplicative inverse for each element except \\$0\\$.
* Multiplication distributes over addition: \\$a·(b+c) = (a·b)+(a·c)\\$

Addition and multiplication can be implemented as functions or programs taking two field elements and producing one field element.

Since the field is really small, you can test the axioms exhaustively to check your implementation or verify the addition and multiplication tables.

### Mathematical construction

Elements of \\$GF(3^2)\\$ can be interpreted as polynomials of the form \\$P(x)=a x+b\\$ over \\$GF(3)\\$. (Addition and multiplication in \\$GF(3)=\\{0,1,2\\}\\$ are the standard integer operations modulo 3.)

Then addition in \\$GF(3^2)\\$ is simply the addition of two polynomials. Multiplication is defined by the product of two polynomials, reduced modulo a polynomial of degree 2 which is irreducible over \\$GF(3)\\$.

### Example

Mapping polynomials to integers with \\$n=3a+b\\$ and using the irreducible polynomial \\$x^2+1\\$ yields the following addition and multiplication tables. Note that there are other possible isomorphisms of these tables.

```
+   0 1 2 3 4 5 6 7 8   *   0 1 2 3 4 5 6 7 8
   ------------------      ------------------
0 | 0 1 2 3 4 5 6 7 8   0 | 0 0 0 0 0 0 0 0 0
1 | 1 2 0 4 5 3 7 8 6   1 | 0 1 2 3 4 5 6 7 8
2 | 2 0 1 5 3 4 8 6 7   2 | 0 2 1 6 8 7 3 5 4
3 | 3 4 5 6 7 8 0 1 2   3 | 0 3 6 2 5 8 1 4 7
4 | 4 5 3 7 8 6 1 2 0   4 | 0 4 8 5 6 1 7 2 3
5 | 5 3 4 8 6 7 2 0 1   5 | 0 5 7 8 1 3 4 6 2
6 | 6 7 8 0 1 2 3 4 5   6 | 0 6 3 1 7 4 2 8 5
7 | 7 8 6 1 2 0 4 5 3   7 | 0 7 5 4 2 6 8 3 1
8 | 8 6 7 2 0 1 5 3 4   8 | 0 8 4 7 3 2 5 1 6

```

Test of distributivity using the tables above:

$$5 · (2 + 7) = 5 · 6 = 4$$ $$(5 · 2) + (5 · 7) = 7 + 6 = 4$$

*Note that simply using addition and multiplication modulo 9 won't work.*

### Scoring

This is code golf. Your score is the sum of bytes of the functions (or programs) for addition and multiplication. Lowest number of bytes wins.

# Answer
# 05AB1E, ~~24~~ ~~17~~ 16 bytes

Uses 0, 1, 2, 10, 11, 12, 20, 21, 22 as the 9 field elements.

Addition, 5 bytes:

```
OS3%J

```

Try it online! or print the entire table.

```
O             # sum of the inputs
 S            # split to a list of digits
  3%          # mod 3 each digit
    J         # join

```

Multiplication, 11 bytes:

```
PƵÈ%98%S3%J

```

Try it online! or print the entire table.

```
P             # product of the inputs
 ƵÈ%          # mod 300
    98%       # mod 98
       S3%J   # split, mod 3 each digit, join

```
> 8 votes

# Answer
# Haskell, ~~118 112~~ 107 bytes

Here I use the numbers \\$n= 0,1,2,\ldots,8\\$ to represent the field elements. Internally these are converted to a list \\$\[a,b\]\\$ that represents a polynomial \\$aX+b\\$, (using \\$a = \lfloor n/3 \rfloor\\$ and \\$b = n \bmod 3 \\$, or \\$n=3a+b\\$), and we then proceed using the usual arithmetic using these polynomials in \\$(\mathbb Z / 3\mathbb Z)\[X\]/(X^2+1)\\$. In this case we have

$$(aX+b) + (cX+d) = (a+c)X + (b+d)$$

and similarly

$$\begin{align\*} (aX+b) \cdot (cX+d) &= acX^2+(ad+bc)X + bd \\ & \equiv ac(-1) +(ad+bc)X + bd \pmod {X^2+1} \\ & \equiv (ad+bc)X+(bd-ac) \end{align\*}$$

Thanks for -6 bytes @WheatWizard!

```
i x=[div x 3,x]                --conert integer to polynomial/list representation
j[a,b]=mod(a*3+mod b 3)9       --inverse of i
s=(.i).(j.).zipWith(+).i       --"sum"
m[a,b][c,d]=j[a*d+b*c,b*d-a*c] --core function of "product"
p=(.i).m.i                     --"product"

```

Try it online!
> 7 votes

# Answer
# Retina 0.8.2, ~~53 + 111 = 164~~ 23 + 61 = 84 bytes

Edit: Saved 80 bytes by switching to @Grimmy's I/O format. However, the provided links include a footer which converts the output back to `0-8` format and formats the results into a square.

Addition (~~53~~ 23 bytes):

```
\d+
$*
M`1
3$
0
T`34`_1

```

Try it online! Link includes test suite. Explanation:

```
\d+
$*

```

Convert both arguments to unary.

```
M`1

```

Take the sum and convert to decimal.

```
3$
0
T`34`_1

```

Modulo the last digit by 3, and modulo by 30.

Multiplication (~~111~~ 61 bytes):

```
\d+
$*
1(?=1*;(1*))|.
$1
1{300}|1{98}|1{30}

M`1
T`3-8`012012

```

Try it online! Link includes test suite. Explanation:

```
\d+
$*

```

Convert to unary.

```
1(?=1*;(1*))|.
$1

```

Take the product.

```
1{300}|1{98}|1{30}

```

Modulo by 300, 98 and 30.

```
M`1

```

Convert to decimal.

```
T`3-8`012012

```

Modulo the last digit by 3.
> 4 votes

# Answer
# MATLAB, ~~106~~ ~~104~~ 102 bytes

We encode \\$\operatorname{GF}(9)\\$ as \\$\\{0,\ldots,8\\}\\$ and map to \\$\mathbb{Z}\[i\]/\langle 3\rangle\\$ in order to add and multiply:

```
e=@(x)mod(x,3)+i*fix(x/3)
d=@(x)[1 3]*mod([real(x);imag(x)],3)
a=@(x,y)d(e(x)+e(y))
m=@(x,y)d(e(x)*e(y))

```

@A.Rex pointed out this clever improvement:

```
e=@(x)mod(x,3)+i*round(x/3)
d=@(x)mod(real(x)^3+3*imag(x),9)
a=@(x,y)d(e(x)+e(y))
m=@(x,y)d(e(x)*e(y))

```
> 4 votes

# Answer
# Pari/GP, 88 bytes

Uses numbers 0 to 8 to represent the elements. Uses Pari/GP's built-in polynomial arithmetic.

```
f(a)=a%3+a\3*x
g(a)=Vecrev(a%(x^2+1),2)%3*[1,3]~
s(a,b)=g(f(a)+f(b))
p(a,b)=g(f(a)*f(b))

```

Try it online!

---

# Pari/GP, 86 bytes

Inspired by Dustin G. Mixon's answer.

```
f(a)=a%3+a\3*I
g(a)=[real(a),imag(a)]%3*[1,3]~
s(a,b)=g(f(a)+f(b))
p(a,b)=g(f(a)*f(b))

```

Try it online!
> 2 votes

# Answer
# x86 32-bit machine code, ~~21~~ 16 bytes

```
f7 e2 28 e0 01 d0 27 2c 03 a8 08 75 f9 d4 30 c3

```

-5 with another shorter way to reduce the coefficients modulo 3.

Uses polynomials modulo \\$X^2 + 1\\$, represented by integers by substituting \\$ X = 16 \\$. The selected values correspond to canonical forms \\$ aX + b\\$ for \\$a,b \in \\{0,1,2\\}\\$ – hexadecimal 00, 01, 02, 10, 11, 12, 20, 21, 22.

Uses the `regparm(2)` calling convention – arguments in EAX and EDX, result in AL. The multiplication function begins at the start of the code, and the addition function begins after the first four bytes.

Try it online!

## Explanation

```
gf9_multiply:
    mul edx

```

Multiply the given polynomials (which are in EAX and EDX). Put the product in EDX:EAX – the value is small enough to fit in EAX, so EDX becomes 0.

```
    sub al, ah

```

Subtract AH (the second-lowest byte of EAX) from AL (the lowest byte of EAX). This reduces the polynomial modulo \\$ X^2 + 1 \\$: AL now represents a polynomial equivalent to the result modulo 3, of the form \\$ aX+b \\$ for \\$ 0 \le a \le 8, -4 \le b \le 4 \\$.

```
gf9_add:
    add eax, edx

```

Here, the two functions merge.
For `gf9_add`, this adds EDX and EAX (the arguments), so that AH represents a polynomial equivalent to the result modulo 3, of the form \\$ aX+b \\$ for \\$ 0 \le a \le 4, 0 \le b \le 4 \\$.
For `gf9_multiply`, EDX will be 0 when we get here, and this instruction leaves EAX unchanged.

```
repeat:
    daa

```

This is one of several x86 instructions designed for handling numbers in binary-coded decimal.

`daa` stands for Decimal Adjust (AL) after Addition. "Decimal" in these instruction names refers to packed BCD, which puts one decimal digit in each nybble. As the instruction's name indicates, its intended purpose is to be used after a regular `add` or similar instruction, to correct the result for BCD.

So what correction is needed?
Consider the simple example of adding 2 (binary 00000010) and 8 (binary 00001000).
The result of regular addition is regular 10 (binary 00001010), but the BCD sum should be BCD 10 (binary 00010000). The result thus has to be increased by 6, to change 10 to 16. That is one of the things that `daa` does.

But how does it know whether this +6 should be applied? In this case, it is obvious from the value itself, because binary 1010 is not a valid BCD digit. But if the calculation were instead 8 plus 8, the result would be binary 00010000, which is valid BCD for 10, but the correct BCD sum is 16.

This is where the "auxiliary carry flag" (AF) comes in. It is set by the `add` instruction based on whether it results in a carry across the centre of the byte, which covers the cases where the low nybble reaches 16 or higher and wraps back around to a valid BCD digit. The instruction `daa` adds 6 to AL if the low nybble of AL is 10 to 15 or AF is 1.

`daa` also makes a similar adjustment for the high nybble of AL: if the high nybble's original value is 10 to 15, or the carry flag (CF) is 1 (which is based on carries off the top of the number), it adds 6 to the high nybble.

Here, the flags AF and CF come from the preceding `add`, which always sets them to 0 here. The low nybble is 10 to 15 iff, in the current polynomial \\$ aX+b \\$ (with \\$ 0 \le a \le 8, -4 \le b \le 4 \\$), \\$ b \\$ is -4 to -1, in which case adding 6 results in \\$ b \\$ being 2 to 5. The high nybble is 10 to 15 only if \\$ a \\$ is 0 in addition to \\$ b \\$ being negative, in which case adding 6 to the high nybble makes \\$ a \\$ 6.

Thus, after the `daa`, AL still represents a polynomial equivalent to the result modulo 3 of the form \\$ aX+b \\$, but now with \\$ 0 \le a \le 8, 0 \le b \le 5 \\$.

```
    sub al, 3

```

Subtract 3. Again, AL represents a polynomial equivalent to the result modulo 3 of the form \\$ aX+b \\$, and this time \\$ 0 \le a \le 8, -3 \le b \le 2 \\$.

```
    test al, 8

```

Look at the eights bit of AL, which is 1 if \\$ b \\$ is negative and 0 otherwise.

```
    jnz repeat

```

Jump back if \\$ b \\$ is negative (-3 to -1). If that is the case, next `daa` adds 6 to \\$ b \\$ while possibly changing \\$ a \\$ from 0 to 6, similarly to before, and then `sub` takes 3 from \\$ b \\$, leaving it with a net +3, which puts it in the range 0 to 2, and then `test` sees that the eights bit is 0, and the jump does not happen again.

In either case, AL now represents a polynomial equivalent to the result modulo 3 of the form \\$ aX+b \\$ with \\$ 0 \le a \le 8, 0 \le b \le 2 \\$.

If it were possible to jump conditionally based on AF, the `test` could have been omitted for -2 bytes.

```
    aam 0x30

```

This is another BCD instruction. In its default form, `aam` converts a regular number in AL to an unpacked BCD (one byte per decimal digit) number in AH and AL, which is done by setting AH and AL to the quotient and remainder, respectively, of AL divided by 10. However, the instruction allows that number 10 to be changed. We set it to 0x30; the important part is that AL is reduced modulo 0x30, which means \\$ a \\$ is reduced modulo 3.

At last, the polynomial has been reduced modulo 3 to its canonical form.

```
    ret

```

Return.

# Previous solution, also 16 bytes

```
f7 e2 d5 02 01 d0 99 d4 30 c0 c0 04 4a 7a f8 c3

```

Try it online!

Assembly:

```
.text
.global gf9_multiply
.global gf9_add
.intel_syntax noprefix

gf9_multiply:
    mul edx     # Multiply EAX by EDX, placing the product in EDX:EAX.
    aad 0x02    # AL := 2 * AH + AL (AL is the low byte of EAX; AH is the next byte.)
                # AH := 0             Reduces the polynomial modulo X^2 - 2.
gf9_add:        # When falling through, EDX=0; the next instruction will do nothing.
    add eax, edx# Add EDX to EAX. Coming from either start point,
                #  this produces in EAX a polynomial equivalent to the result mod 3.
    cdq         # Set each bit of EDX to the high bit of EAX, here 0.
repeat:
    aam 0x30    # (AH, AL) := (quotient, remainder) of AL / 0x30
                # Reduces the coefficient of X modulo 3.
    rol al, 4   # Rotate left by 4 places, swapping the positions of the coefficients.
                #   Next, we need to execute the same two instructions again,
                #    to reduce the other coefficient modulo 3 and swap them back.
                #   Simply repeating those instructions would take 5 bytes.
                #   It is instead done in 4 bytes, including the earlier cdq:
    dec edx     # Decrement EDX, to -1 the first time and -2 the second time.
    jpe repeat  # Jump back if the sum of the eight low bits is even.
                #  This is true for -1 (...11111111) but not for -2 (...11111110).
    ret         # Return.

```
> 2 votes

# Answer
# Haskell, 83 bytes

This is a straightforward adaptation of 05AB1E's answer. This function accepts 0, 1, 2, 10, 11, 12, 20, 21, and 22.

```
k=flip mod
q=l.k 30
l a=a-z+k 3 z where z=k 10 a
p=((q.k 98.k 300).).(*)
s=(q.).(+)

```
> 1 votes

---
Tags: code-golf, math, polynomials, abstract-algebra, open-ended-function
---


title: AoCG2021 Day 13: Defrag in action!

text:
# Question
Title: AoCG2021 Day 13: Defrag in action!
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

The story continues from AoC2017 Day 14.

---

To recap: The disk is a rectangular grid with \\$r\\$ rows and \\$c\\$ columns. Each square in the disk is either free (0) or used (1). So far, you have identified the current status of the disk (a 0-1 matrix), and the number of regions in it (a region is a group of used squares that are all adjacent, not including diagonals).

But we didn't actually defrag the disk yet! Since we identified the regions of used squares, let's assume the shape of each region should be kept intact. It makes it hard to compact the used space, but we can at least move each chunk to the left. Let's do it.

More formally, the algorithm would look like this:

* Identify the regions of used cells in the disk.
* Loop until there is nothing to move:
    + Select a region that can be moved 1 unit to the left without overlapping with another region.
    + Move it 1 unit to the left. (The regions do not fuse into one even if they become adjacent after such a move.)

**Input:** A rectangular array of zeroes and ones.

**Output:** A rectangular array of same size, which represents the result of the simple defrag operation.

For example, if the memory looks like this: (`#` is used, `.` is free)

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

```

then it has 12 distinct regions

```
00.1.2..
.0.1.2.3
....4.5.
6.7.44.8
.77.4...
77..4..9
.7...a..
77.b.aa.

```

which should be defragged in this way:

```
0012....
.0123...
...45...
6.7448..
.774....
77.49...
.7.a....
77baa...

```

resulting in the disk state of

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

```

Standard rules apply. The shortest code in bytes wins.

## Additional test cases

```
...#####
...#...#
...#.#.#
.....#..
########
->
..#####.
..#...#.
..#..##.
.....#..
########

.....#####..
.....#...#..
.....#.#.#.#
.......#...#
.......#####
->
#####.......
#...#.......
##..##......
.#...#......
.#####......

```

# Answer
# Wolfram Language (Mathematica), 109 bytes

```
#//.x_:>(x-#+RotateLeft/@#&)@ImageData@SelectComponents[Image@x,#BoundingBox[[1,1]]>0&,CornerNeighbors->1<0]&

```

Try it online!

Repeatedly select the components whose bounding box's `x_min` is greater than 0, and move these components 1 unit to the left.

The `SelectComponents` function has a bug: when it takes an array instead of an image as input, the `CornerNeighbors` option does not work. So we have to convert the input into an image.
> 4 votes

# Answer
# TypeScript Types, 804 bytes

```
//@ts-ignore
type a<T,N=[]>=T extends`${N["length"]}`?N:a<T,d<N>>;type b<T>={[I in keyof T]:{[J in keyof T[I]]:T[I][J]extends 1?[a<J>,a<I>]:never}[keyof T[I]]}[number];type c<T>=(T extends T?(x:()=>T)=>0:0)extends(x:infer U)=>0?U extends()=>infer V?V:0:0;type d<T>=[...T,0];type e<T>=T extends[0,...infer X]?X:[];type f<T>=T extends[infer A,infer B]?[e<A>,B]|[d<A>,B]|[A,e<B>]|[A,d<B>]:0;type g<P,T=c<P>,U=0>=[T]extends[U]?T:g<P,T|Extract<f<T>,P>,T>;type h<P,G=[]>=[P]extends[never]?G:h<Exclude<P,g<P>>,[...G,g<P>]>;type i<T>=T[0]extends[0,...0[]]?T extends T?[e<T[0]>,T[1]]:0:{};type j<T,U=0>=T extends U?T:j<{[K in keyof T]:Extract<Exclude<T[number],T[K]>,i<T[K]>>extends 0?i<T[K]>:T[K]},T>;type M<T,U=j<h<b<T>>>[number]>={[I in keyof T]:T[I]extends infer X?{[J in keyof X]:[a<J>,a<I>]extends U?1:0}:0}

```

Try It Online!

## Ungolfed / Explanation

```
// Converts a stringified number into a tuple
type StrNumToTuple<T, N = []> = T extends `${N["length"]}` ? N : StrNumToTuple<T, [...N, 0]>;

// Converts the input (e.g. [[0,0,1],[1,0,1],[0,1,1]])
// to a union of on cells ([2,0]|[0,1]|[2,1]|[1,2]|[2,2]) (where the numbers are represented by tuples)
type ToUnion<T> =
  // Map over the 2d array
  { [I in keyof T]: { [J in keyof T[I]]:
    T[I][J] extends 1
      // if the cell is on, add this tuple
      ? [StrNumToTuple<J>, StrNumToTuple<I>]
      : never
  // put the results into a union
  }[keyof T[I]] }[number]

// Retrieves an arbitrary element of a union
type PopUnion<T> = (T extends T ? (x: () => T) => 0 : 0) extends (x: infer U) => 0 ? U extends () => infer V ? V : 0 : 0;

type Inc<T> = [...T, 0];
type Dec<T> = T extends [0, ...infer X] ? X : [];

// Get the orthogonal neighbor positions of a position
type Neighbors<T> = T extends [infer A, infer B] ? ( ([Dec<A>, B] | [Inc<A>, B] | [A, Dec<B>] | [A, Inc<B>]) ) : 0;

type FindGroup<All, Group = PopUnion<All>, LastGroup = 0> =
  [Group] extends [LastGroup]
    // If the group didn't change last iteration, return it
    ? Group
    // Add to Group the Neighbors of Group that are in All
    : FindGroup<All, Group | Extract<Neighbors<Group>, All>, Group>

// Converts a union of positions into a tuple of unions of positions, grouped by connectedness
type Group<Ungrouped, Groups = []> =
  [Ungrouped] extends [never]
    // If there are no positions left in Ungrouped, return Groups
    ? Groups
    // Find a group, remove its elements from Ungrouped, and add it to Groups
    : Group<Exclude<Ungrouped, FindGroup<Ungrouped>>, [...Groups, FindGroup<Ungrouped>]>

// Shift a group to the left. Returns {} (a top type of sorts) if it's at the leftmost border
type ShiftLeft<Group> =
  Group[0] extends [0, ...0[]]
    // If all X coordinates are >= 1, map over the positions in Group
    ? Group extends Group
      // Decrement the X coordinate of this position
      ? [Dec<Group[0]>, Group[1]]
      // Unreachable
      : 0
    // Otherwise, return {}
    : {}

// The meat of the logic. Continually shifts groups left until it can't anymore
type Defrag<Groups, PrevGroups = 0> =
  Groups extends PrevGroups
    // If Groups == PrevGroups, return Groups
    ? Groups
    // Otherwise, recurse:
    : Defrag<
        {
          // Map over Groups
          [K in keyof Groups]:
            // If (Groups[number] (all live positions) - Groups[K]) shares no elements with ShiftLeft<Groups<K>>,
            Extract<Exclude<Groups[number], Groups[K]>, ShiftLeft<Groups[K]>> extends 0
              // Change this group to ShiftLeft<Groups[K]>
              ? ShiftLeft<Groups[K]>
              // Otherwise, leave it unchanged
              : Groups[K]
        },
        Groups
      >

type Main<Input, FinalLivePositions = Defrag<Group<ToUnion<Input>>>[number]> = {
  // Map over every row of Input
  [I in keyof Input]: Input[I] extends infer Row ? {
    // Map over every cell of Row
    [J in keyof Row]:
      // If this coordinate is in FinalLivePositions, set this cell to 1; otherwise, set it to 0
      [StrNumToTuple<J>, StrNumToTuple<I>] extends FinalLivePositions ? 1 : 0
  } : 0
}

```
> 3 votes

# Answer
# Python3, 519 bytes

```
import re
r=range
def f(b,x,y,t):
 b[x][y]=t
 for j,k in[[1,0],[0,1],[-1,0],[0,-1]]:
  try:
   if x+j>=0 and y+k>=0 and b[x+j][y+k]==1:f(b,x+j,y+k,t)
  except:1
def g(b):
 n=map(chr,r(97,123))
 while'1'in str(b):f(b,*[(x,y)for x in r(len(b))for y in r(len(b[x]))if b[x][y]==1][0],next(n))
 return re.sub('\w','#',(q:=lambda r:r if r==(t:=re.sub('\.\w+',lambda x:j if re.findall('^'+(j:=x.group())[1]+'|(?<=[^'+'\.'+j[1]+'])'+j[1],r)else j[1:]+'.',r))else q(t))('\n'.join(''.join(['.',i][bool(i)]for i in k)for k in b)))

```

Try it online!
> 3 votes

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

```
w=>g=a=>a.some((c,i)=>!a.some(n=_=>a.some((d,j)=>(r=~j%w?j+1:j,d-c)?d*n[r]:(n[j]=[j,j%w?j-1:j,r,j-w,j+w].some(k=>n[k]))*!(j%w)),n[i]=++t))?g(a.map((c,i)=>n[i+1]?t:!n[i]*c)):a.map(c=>c>0);t=1

```

Try it online!

Input as 1d array of boolean values and width as an integer. Output 1d array of boolean values.
> 2 votes

# Answer
# Charcoal, ~~120~~ 105 bytes

```
ＷＳ⊞υι≔⊕Ｌθθ≔⌕Ａ⪫υψ#η≔⟦⟧ζＷη«≔⟦⊟η⟧εＦεＦ⁺κ⟦θ¹±¹±θ⟧Ｆ№ηλ«⊞ελ≔⁻ηεη»⊞ζε»ＷΦζ⬤κ∧﹪μθ¬⊙ζ›№ξ⊖μ⁼ξκＦιＵＭκ⊖λＥυ⭆ι§.#⊙ζ№ν⁺×θκμ

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings of `.`s and `#`s and outputs a list of newline-separated strings. Explanation:

```
ＷＳ⊞υι

```

Input the cells.

```
≔⊕Ｌθ

```

Get the offset between each cell and the cell below. (This is one more than the width so a region at the end of a line doesn't inadvertently connect with the one at the start of the next line.)

```
≔⌕Ａ⪫υψ#η

```

Get the list of used cells.

```
≔⟦⟧ζ

```

Start with no regions.

```
Ｗη«

```

Repeat until all of the used cells have been allocated to a region.

```
≔⟦⊟η⟧ε

```

Start the region with the last (i.e. golfiest) used cell.

```
Ｆε

```

Perform a breadth-first search over the region.

```
Ｆ⁺κ⟦θ¹±¹±θ⟧

```

Enumerate the coordinates of the adjacent cells.

```
Ｆ№ηλ«⊞ελ≔⁻ηεη»

```

If this is a used cell, then add it to the region and remove it from the list of used cells.

```
⊞ζε

```

Save this region to the list of regions.

```
»ＷΦζ⬤κ∧﹪μθ¬⊙ζ›№ξ⊖μ⁼ξκ

```

Repeat while any regions can be defragmented...

```
ＦιＵＭκ⊖λ

```

... move all cells in those regions left by 1 cell. (Sadly `MapAssign` doesn't do what I want here.)

```
Ｅυ⭆ι§.#⊙ζ№ν⁺×θκμ

```

Output the original input updated with the new locations of all the used cells.

Previous 120-byte version did not require rectangular input:

```
≔⟦⟧θＷＳ«Ｆ⌕Ａι#⊞θ⟦Ｌυκ⟧⊞υι»≔⟦⟧ηＷθ«≔⟦⊟θ⟧ζＦζＦＥ⁴Ｅκ⁺ν∧⁼ξ＆¹λ⊖＆²λＦ№θλ«⊞ζλ≔⁻θζθ»⊞ηζ»ＷΦη⬤κ∧§μ¹¬⊙η›№ξＥμ⁻ρς⁼ξκＦιＦκＵＭλ⁻μνＥυ⭆ι§.#⊙η№ν⟦κμ

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings of `.`s and `#`s and outputs a list of newline-separated strings. Explanation:

```
≔⟦⟧θ

```

Start with no used cells.

```
ＷＳ«

```

Loop over the input strings.

```
Ｆ⌕Ａι#⊞θ⟦Ｌυκ⟧

```

Record the used cells in this string.

```
⊞υι

```

Save this string so that the output has the same shape as the input.

```
»≔⟦⟧η

```

Start with no regions.

```
Ｗθ«

```

Repeat until all of the used cells have been allocated to a region.

```
≔⟦⊟θ⟧ζ

```

Start the region with the last (i.e. golfiest) used cell.

```
Ｆζ

```

Perform a breadth-first search over the region.

```
ＦＥ⁴Ｅκ⁺ν∧⁼ξ＆¹λ⊖＆²λ

```

Enumerate the coordinates of the adjacent cells.

```
Ｆ№θλ«⊞ζλ≔⁻θζθ»

```

If this is a used cell, then add it to the region and remove it from the list of used cells.

```
⊞ηζ

```

Save this region to the list of regions.

```
»ＷΦη⬤κ∧§μ¹¬⊙η›№ξＥμ⁻ρς⁼ξκ

```

Repeat while any regions can be defragmented...

```
ＦιＦκＵＭλ⁻μν

```

... move all cells in those regions left by 1 cell.

```
Ｅυ⭆ι§.#⊙η№ν⟦κμ

```

Output the original input updated with the new locations of all the used cells.
> 2 votes

# Answer
# Python 3 \+ scipy, 162, 160 bytes

```
from scipy.ndimage import*
def f(A):
 B,J=label(A.T);j=1
 while~J+j:C=B==j;B[C]=0;D=C^C;D[:-1]=C[1:];d=C[0].any()|B[D].any();B[[D,C][d]]=j;j=d*j+1
 return B.T>0

```

Try it online!

#### Older versions:

```
from scipy.ndimage import*
def f(A):
 B,J=label(A.T);j=1
 while~J+j:C=B==j;B[C]=0;D=C^C;D[:-1]=C[1:];d=C[0].any()or B[D].any();B[[D,C][d]]=j;j=d*j+1
 return B.T>0

```

Try it online!

# Explanation

Leaves the heavy lifting (the segmentation) to a library function, `scipy.ndimage.label`.

The rest is relatively straight forward. Everything is done with transposed axes to save indexing clutter. We push one labelled component one unit a time until we run through all of them without being able to move anything anymore.

More specifically, `C` selects the pixels for label `l` and we immeditately zero them out; `D` shifts the selection. `d` decides based on whether there are labelled pixels (1) in the base column or (2) (after shifting) collisions with other labels. If `d` is set we write the erased pixels back and move to the next label, if `d` is not set we shift them and reset the label index.
> 2 votes

# Answer
# Java 10, ~~463~~ ~~459~~ ~~444~~ 443 bytes

```
int M[][],v;m->{int l=m[0].length,t=m.length*l,i,F=v=1,f,x,a,b;for(M=m;v++<t;)for(i=t;i-->0;)i=m[i/l][i%l]==1?f(i/l,i%l)-1:i;for(;F>0;)for(F=v=0;v++<t;F=f>0?1:F){for(f=-1,i=t;i-->0;)f&=m[a=i/l][b=i%l]==v&b>0?(x=m[a][b-1])<1|x==v&b>1?1:0:f;for(;f>0&++i<t;)m[a=i/l][b=i%l]-=m[a][b]==v&b>0?m[a][b-1]=v:0;}for(;t-->0;)m[t/l][t%l]=1/~m[t/l][t%l]+1;}int f(int x,int y){try{if(M[x][y]==1){M[x][y]=v;f(x+f(x,y+f(x-f(x,y-1),y)),y);}}finally{return 1;}}

```

-5 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
int M[][],             // Integer-matrix on class-level, uninitialized
    v;                 // Value-integer on class-level, uninitialized
m->{                   // Method with integer-matrix parameter & boolean return
  int l=m[0].length,   //  The amount of columns in the matrix
      t=m.length*l,    //  The total amount of cells in the matrix
      i,               //  Index-integer, starting uninitialized
      F=               //  Flag-integer, whether we can still move anything
        v=1;           //  Set it and the class-level value both to 1
      f,               //  Flag-integer, whether the current region can move
      x,a,b;           //  Temp-integers to save bytes, uninitialized
  for(M=m;             //  Set the class-level `M` to the input-matrix
      v++<t;)          //  Loop `v` in the range (1,t):
    for(i=t;i-->0;)    //   Inner loop over the cells:
      i=m[i/l][i%l]==1?//    If the current cell contains a 1:
         f(i/l,i%l,v)  //     Flood-fill the region with the current `v`
         -1            //     And break out of the inner loop
        :              //    Else:
         i;            //     Simply continue the loop
                       //  (now every region has its own positive integer)
  for(;F>0;)           //  Loop as long as `F` is still 1:
    for(F=v=0;         //   Reset `F` to 0
        v++<t          //   Inner loop `v` in the range (0,t):
        ;              //     After every iteration:
         F=f>0?        //      If `f` is 1:
            1          //       Set `F` to 1 as well
           :           //      Else:
            F){        //       Leave `F` the same
      for(f=-1,        //    Reset `f` to -1
          i=t;i-->0;)  //    Inner loop over the cells:
        f&=m[a=i/l][b=i%l]==v
                       //     If the current cell contains value `v`,
           &b>0?       //     and this is NOT the first column:
            (x=m[a][b-1])<1
                       //      If the cell at the left contains a 0
            |x==v      //      Or the cell at the left contains value `v`,
             &b>1?     //      and this is also not the second column:
             1         //       Bitwise-AND `f` with 1
            :          //      Else:
             0         //       Bitwise-AND `f` with 0 instead
                       //      (if the check is truthy: -1→1; 0→0; 1→1;
                       //       if the check is falsey: -1→0; 0→0; 1→0)
           :           //     Else:
            f;         //      Bitwise-AND `f` with itself to stay `f`
      for(;f>0&        //    If `f` is now 1, which means we can move the region
                       //    with value `v`:
          ++i<t;)      //     Do another inner loop over the cells:
        m[a=i/l][b=i%l]-=
                       //      Decrease the value in the current cell by:
          m[a][b]==v   //       If the current cell contains value `v`,
          &b>0?        //       and this is NOT the first column:
           m[a][b-1]=v //        Set the cell at the left to `v`
                       //        Set the current cell to 0 by decreasing by `v`
          :            //       Else:
           0;          //        Decrease by 0 to stay the same
                       //  After everything has been moved,
  for(;t-->0;)         //  loop one last time over the cells:
    m[t/l][t%l]=       //   Change the value in the current cell to:
                       //    Transform all positive values to 1,
                       //    while keeping any 0s the same:
      1/~m[t/l][t%l]+1;//     (1 integer-divided by (-value-1)) + 1

// Recursive method with coordinate as parameters & integer return-type
int f(int x,int y){
  try{if(M[x][y]==1){  //  If the current cell contains a 1:
    M[x][y]=v;         //   Fill the cell with the current value
       f(m,x,y-1)      //   Recursive call west
      f(m,x-...,y)     //   Recursive call north
     f(m,x,y+...)      //   Recursive call east
    f(m,x+...,y);}     //   Recursive call south
  }finally{            //  Catch and swallow any ArrayIndexOutOfBoundsExceptions
                       //  (shorter than manual if-checks)
           return 1;}  //  Always return 1, so we use it to our advantage to
                       //  save bytes

```
> 2 votes

# Answer
# Pari/GP, 157 bytes

```
m->while(a=0*m;a[,1]=m[,1];while(a!=b=matrix(#a~,#a,i,j,m[i,j]&&matrix(#a~,#a,k,l,abs(i-k)+abs(j-l)<2&&a[k,l])),a=b);m!=n=a+concat((m-a)[,^1],0*m[,1]),m=n);m

```

Try it online!
> 1 votes

# Answer
# Rust, 558 334 bytes

```
|p:&mut Vec<Vec<_>>|{fn k(x:usize,y:usize,p:&mut Vec<Vec<u8>>){if p[y][x]==1{p[y][x]+=2;if x>0{k(x-1,y,p)}if x<p[0].len()-1{k(x+1,y,p)}if y>0{k(x,y-1,p)}if y<p.len()-1{k(x,y+1,p)}}}loop{let q=p.clone();for j in 0..p.len(){k(0,j,p)}for i in 0..p[0].len(){for j in 0..p.len(){if p[j][i]==1{p[j].swap(i,i-1)}p[j][i]&=1}}if p==&q{break}}}

```

Try it online!

* -224 bytes (wow!) by changing the algorithm (Thanks @alephalpha)
> 1 votes

---
Tags: code-golf, array, grid, graph-theory, binary-matrix
---