title: Is this a shift matrix?

text:
# Question
Title: Is this a shift matrix?
A Shift matrix is a binary matrix with one superdiagonal or subdiagonal formed by only ones, everything else is a zero.
A superdiagonal/subdiagonal is a diagonal parallel to the main diagonal, which is not the main diagonal, i.e. all entries \\$a\_{ij}\\$ where \\$i=j+k\\$ and \\$k \neq 0\\$.
The main diagonal is defined to be all entries \\$a\_{ij}\\$ where \\$i=j\\$.

## Specs

* The matrix is *not* guaranteed to be square and will consist of only zeros and ones
* Take a nested list or a matrix as the input
* Output a truthy/falsy result or use two distinct values to represent truthy and falsy results
* This is , the shortest answer wins!

## Examples

```
[[1]] -> 0

[[0, 1],
 [0, 0]] -> 1

[[0, 0, 0],
 [1, 0, 0],
 [0, 1, 0]] -> 1

[[0, 1, 0],
 [1, 0, 0],
 [0, 0, 0]] -> 0

[[0, 1, 0],
 [0, 0, 1]] -> 1

[[0, 0],
 [0, 0]] -> 0

[[0, 0, 0, 0],
 [1, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 1, 0]] -> 0

[[1, 1],
 [1, 1]] -> 0

[[0,1,0,0],
 [1,0,1,0],
 [0,1,0,1],
 [0,0,1,0]] -> 0

[[0,1,0],
 [1,0,0],
 [0,1,0]] -> 0

[[0,1,0],
 [0,0,1],
 [1,0,0]] -> 0

[[1,0,0],
 [0,1,0]] -> 0

[[0,0,0],
 [0,0,0],
 [0,0,0],
 [0,0,0],
 [0,0,0],
 [1,0,0]] -> 1

[[1,0,1],
 [0,1,0],
 [0,0,1]] -> 0

[[0,1,0],
 [1,0,0]] -> 0

```

# Answer
> 6 votes
# , 37 bytes

```
1=1#.([:(+./*[:*/%)/.|."1),_*<@0 1|:]

```

Try it online!

*Thanks to AndrovT for catching a bug*

* `,<@0 1|:]` Append `,` items along main diagonal (works for non-square) multiplied by infinity to...
* `([:(+./*[:*/%)/.|."1)` Product of reciprocals of every diagonal, multipled by "is there at least a single 1". This will return 1 for all ones, infinity for partial ones, and 0 for all zeros. To get the diagonals, we combine J's built-in for anti-diagonals `/.` with a flip about the y-axis `|."1`.
* `1#.` Sum of those catted lists
* `1=` Is the sum 1?

# Answer
> 6 votes
# Jelly, 11 bytes

```
ŒDµẒ¬ṛ¦ⱮJḊċ

```

A monadic Link that accepts a matrix of ones and zeros and yields `1` if it's a shift matrix or `0` otherwise.

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

### How?

Constructs all diagonalised representations of shift matrices of the same dimensions as the input and counts occurrences of a diagonalised version of the input.

```
ŒDµẒ¬ṛ¦ⱮJḊċ - Link: matrix of [0,1], M    e.g. [[0,1,0],[0,0,1],[0,0,1]]
ŒD          - diagonals (main first)           [[0,0,1],[1,1],[0],[0],[0,0]]
  µ         - start a new monadic chain - f(D=those diagonals)
   Ẓ        - is prime? (D) (used as a zero-all entries function)
        J   - (set the right argument to) range of length (D)
       Ɱ    - map with:
      ¦     -   sparse application (to elements of D)...
     ṛ      -   ...at indices: right argument (i.e. one of [1..length(D)])
    ¬       -   ...apply: logical NOT (making that single diagonal all ones)
         Ḋ  - dequeue (removing the only non-shift matrix (main diagonal one))
          ċ - count occurrences of (D)

```

# Answer
> 6 votes
# JavaScript (Node.js), 59 bytes

```
m=>m.every((r,y)=>r.every((c,x)=>+m?x-y==m==c:c?m=x-y:1))*m

```

Try it online!

Output falsy (`0`, `-0`, `NaN`) if input is not a shift matrix, output truthy (\\$k\\$) otherwise.

# Answer
> 5 votes
# MATL, 14 bytes

```
&fyh!dt&=bd1=v

```

Outputs a truthy or falsy column array.

Try it online! (includes truthy/falsy test; delete footer to see actual output). Or verify all test cases.

### How it works

Consider `[0 0 0 0; 1 0 0 0; 0 0 0 0; 0 0 1 0]` as example input.

```
&f    % Implicit input. Two-output find: row and column indices of non-zeros
      % STACK: [2; 4], [1 ;3]
yh    % Duplicate from below. Concatenate horizontally
      % STACK: [2; 4], [1 2; 3 4]
!     % Transpose
      % STACK: [2; 4], [1 3; 2 4]
d     % Vertical onsecutive differences
      % STACK: [2; 4], [1 1]
t&=   % Duplicate. All pairwise equality comparisons
      % STACK: [2; 4], [1 1], [1 1; 1 1]
bd    % Bubble up third-topmost entry. Consecutive differences
      % STACK: [1 1], [1 1; 1 1], 2
1=    % Equal to 1?, element-wise
      % STACK: [1 1], [1 1; 1 1], 0
v     % Concatenate vertically, converting to column vectors if non-matching sizes
      % STACK: [1; 1; 1; 1; 1; 1; 0]

```

# Answer
> 5 votes
# Vyxal, 10 bytes

```
ÞD₌~aḢ~AẊ₃

```

Try it online or verify all test cases.

```
ÞD         # list of all diagonals
  ₌        # apply the next two elements in parallel:
   ~a      #   filter by Any
     Ḣ     #   remove head (removes the main diagonal)
      ~A   # filter by All
           # Now the stack has the the list of diagonals that have at least one 1
             and list of all sub/superdiagonals that don't contain 0
        Ẋ  # cartesian product
         ₃ # is length equal to 1?

```

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

```
A=>A.map((B,i)=>B.map((C,j)=>N-=i*j?A[i-1][j-1]-C&&9:i-j?C:2*C),N=1)&&!N

```

Try it online!

# Answer
> 3 votes
# 05AB1E, 29 bytes

```
εI˜d·«NFÀ]øJ2мõK€SDPsOĀ+ćÌL¢J

```

Outputs a 05AB1E truthy/falsey result (only `1` is truthy in 05AB1E): `01` if truthy; anything else (e.g. `0000`, `20`, `11`, `0100`, etc.) if falsey.

Try it online or verify all test cases.

**Explanation:**

05AB1E lacks a builtin to get all (anti-)diagonals, so the first 18 bytes of the code is to do just that..

Step 1: Get a list of all diagonals, starting with the main diagonal:

```
ε       # Map over each row of the (implicit) input-matrix:
 I˜     #  Push the input-matrix again, and flatten it
   d    #  Transform every 0 to a 1 as well, so we have a list of 1s
    ·   #  Double each to a list of 2s
     «  #  Merge it to the current row
 NF     #  Loop the 0-based map-index amount of times:
   À    #   Rotate the row-list once towards the left
]       # Close both the inner loop and outer map
 ø      # Zip/transpose; swapping rows/columns
  J     # Join each inner row together
   2м   # Remove all 2s in every string
     õK # Remove all empty strings from the list
  €S    # Convert each inner string back to a list of digits

```

For a matrix `[[a,b,c],[d,e,f],[g,h,i]]`, the order of the list of diagonals will be `[[a,e,i],[b,f],[c],[g],[d,h]]`.

Try just step 1 online.

Step 2: Check whether it's a valid Shift Matrix, so there is exactly one diagonal consisting solely of 1s without any 1s in another diagonal, and it's not the first main diagonal:

```
D       # Duplicate the list of diagonals
 P      # Get the product of each, to check which diagonals consists solely of 1s
s       # Swap so the list of diagonals is at the top again
 OĀ     # Sum and Python-style truthify (!=0), to check which diagonals contain a 1
+       # Add the two list of checks together
ć       # Extract the head; push remainder-list and first item separately
 Ì      # Increase this first item (check of the main diagonal) by 2
  L     # Pop and push a list in the range [1,value]
   ¢    # Count for each value in this list how many times it occurs
    J   # Join these counts together
        # (after which the result is output implicitly)

```

Try both steps online, with added debug-lines.

# Answer
> 3 votes
# , ~~76~~ ~~69~~ 66 bytes

*Edit: -3 bytes thanks to pajonk*

```
\(m)all(d<-diff(t(which(m>0,T))),d==max(dim(m)-sum(m))*sign(d[1]))

```

Attempt This Online!

# Answer
> 2 votes
# Python, 138 bytes

```
lambda d:any(i for i in range(-len(d)-len(d[0]),len(d)+len(d[0]))if all(d[j][k]==(j-k==i)for j in range(len(d))for k in range(len(d[0]))))

```

Attempt This Online!

# Answer
> 2 votes
# Julia 1.0, 118 bytes

```
using LinearAlgebra
~A=((m,n)=size(A);X=map(i->diag(A,i),1-m:n-1);!i=sum(all.(==(i),X));A[1]<1&&!1>0&&!0==length(X)-1)

```

Try it online!

The function `~A` returns `true` if `A[1,1]` is not 1 (main diagonal check), one diagonal contains all 1's, and all but one diagonal contains all 0's. Otherwise, it returns `false`. The intermediate value `X` is a vector of all `A`'s diagonals, and the intermediate function `!i` determines if all elements in a diagonal equal the value `i`.

Note: As in a somewhat related answer, `LinearAlgebra` is imported only for the function `diag(A,k)`, which returns the `k`th diagonal of A. If the diagonal `k` doesn't exist, no error results, but an empty set is returned. If these are filtered out, the bounds don't need to be specified precisely; using the range `-9:9` would work for all test cases and eliminate the need for calculating `size(A)`.

# Answer
> 2 votes
# PHP, 139 bytes

```
fn($m)=>$m[0][0]?!1:(count($f=array_merge(...array_map(fn($v)=>array_keys($v,1),$m)))>1?$f==range(min($f),max($f)):end($m)[0]||end($m[0]));

```

Try it online!

**Ungolfed**

```
fn($m) =>
  $m[0][0] ? !1 :
  (count($f = array_merge(...array_map(fn($v) => array_keys($v, 1), $m))) > 1
  ? $f == range(min($f), max($f))
  : end($m)[0] || end($m[0]));

```

# Answer
> 0 votes
# Charcoal, 38 bytes

```
ＷＳ⊞υι≔ΣＥυ⁻⌕Ａι1κθ¿⌈θ¿⁼⌈θ⌊θ¬№ΣＥυ⁻⌕Ａι0κ⌈θ

```

Attempt This Online! Link is to verbose version of code. Takes input as a list of newline-terminated binary strings and outputs a Charcoal boolean i.e. `-` for a shift matrix, nothing if not. Explanation:

```
ＷＳ⊞υι

```

Input the matrix.

```
≔ΣＥυ⁻⌕Ａι1κθ

```

Find the diagonals of all of the `1`s in the matrix.

```
¿⌈θ

```

If there is at least one `1` not on the main diagonal\*, and ...

```
¿⁼⌈θ⌊θ

```

... if all of the `1`s are on the same diagonal, ...

```
¬№ΣＥυ⁻⌕Ａι0κ⌈θ

```

... check whether there are any `0`s on that diagonal.

\*Strictly speaking this tests that either at least one `1` is above the diagonal or there are `1`s that are only below the diagonal.

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


title: Change the subject

text:
# Question
Title: Change the subject
Sometimes I feel like the conversation is going down the wrong path and take it upon myself to steer it in another direction. And this conversation is going wrong real fast, so I need to change the subject in as few characters as possible.1

## Task

Given a list of sentences, return the sentences ordered such that each sentence "connects" to the next.

For the purposes of this challenge, a sentence is a string, starting with a capital letter, containing words separated by spaces (there won't be punctuation between words), and ending with a period.

Two sentences "connect" if they share at least two common words. For example, the sentences "Once upon a time giraffes roamed the land freely." and "Another species that roamed freely were elephants." connect because they share the words "roamed" and "freely", while the latter sentence does not connect with "I love eating sandwiches." because they do not share any words. Note that the first and last words of the sentence can be compared with the others as well, and the first word starts with a capital letter while the last word ends with a period.

The input is guaranteed to have a valid output. Both an output and its reverse will be valid, so you may output either or both. The input may have multiple valid orders.

This is , so shortest answer in bytes wins.

## Test cases:

You must output the sorted list, but for the sake of brevity I will write the test cases as returning a list of zero-based indices of the original list.

```
"Once upon a time giraffes roamed the land freely."
"An awful lot of stories start with the phrase once upon a time."
"Another species that roamed freely were elephants."
-> [1, 0, 2] or [2, 0, 1]

"I hear that he is the worst."
"Did you hear that Mr. Jones is running for president."
"He should not be in charge of making our sandwiches."
"The worst sandwiches in the world."
-> [1, 0, 3, 2] or [2, 3, 0, 1]

Please comment suggested test cases, I suck at this.

```

---

1 This is a totally logical explanation for why this is .

# Answer
# Vyxal, 11 bytes

```
Ṗ'ɽ⌈Ǎ¨p‡↔ḢA

```

Try it Online!

Inputs list of all sentences, outputs all ways the sentences could be joined together as sentences.

## Explained

```
Ṗ'ɽ⌈Ǎ¨p‡↔ḢA
Ṗ'           # Keep permutations of the input where:
  ɽ⌈Ǎ        #   Each lowercased sentence split on spaces with punctuation removed
       ‡     #   With:
        ↔Ḣ   #     Set intersection and head remove (which can be used as a len(x) > 1 check)
     ¨p      #   Applied to all overlapping pairs
          A  #   Is all truthy.

```
> 8 votes

# Answer
# 05AB1E, 13 bytes

```
œʒεl¨#}üåO2@P

```

Input as a list of sentences. Outputs all possible results as a list of lists of sentences.

Try it online or verify all test cases.

**Explanation:**

```
œ         # Get all permutations of the (implicit) input-list of sentences
 ʒ        # Filter it by:
  ε       #  Map over each sentence in the current list:
   l      #   Convert it to lowercase
    ¨     #   Remove the trailing period
     #    #   Split it by spaces to a list of words
  }ü      #  After the map: loop over overlapping pairs of lists of words:
    å     #   Check for each word in the second list if it occurs in the first list
     O    #  Sum each inner list of truthy/falsey results together
      2@  #  Check for each inner sum whether it's >= 2
        P #  Product to check whether it's truthy for every overlapping check
          # (after which the filtered list is output implicitly as result)

```
> 7 votes

# Answer
# JavaScript (V8), 131 bytes

Prints all valid solutions.

```
f=(a,o,p)=>a.map((s,i)=>s.split` `.map(q=w=>q[v=parseInt(w,36)]=v).filter(v=>p?p[v]:1)[1]&&f(a.filter(_=>i--),[o]+s,q))+a||print(o)

```

Try it online!

### How?

The good thing about `parseInt(s, 36)` is that the strings `"abc"`, `"Abc"` and `"abc."` are seen as three variants of the same base-36 number and therefore evaluate to the same value (`13368` in that case).

### Commented

```
f = (                 // f is a recursive function taking:
  a,                  //   a[] = list of sentences
  o,                  //   o = output string
  p                   //   p = lookup object for the words in the previous
) =>                  //       selected sentence
a.map((s, i) =>       // for each sentence s at index i in a[]:
  s.split` `          //   turn s into an array of words
  .map(q =            //   let q be an object
  w =>                //   for each word w:
    q[                //
      v =             //     v = result of ...
      parseInt(w, 36) //         ... base-36 parsing of w
    ] = v             //     save it in q
  )                   //   end of map()
  .filter(v =>        //   filter the result:
    p ?               //     if this is not the first iteration:
      p[v]            //       see if v was defined in the previous sentence
    :                 //     else:
      1               //       keep all entries
  )[1] &&             //   end of filter; if we have at least 2 matches:
    f(                //     do a recursive call:
      a.filter(_ =>   //       pass a copy of a[] where
        i--           //       the i-th entry is removed
      ),              //
      [o] + s,        //       append s to o
      q               //       set p = q
    )                 //     end of recursive call
) + a ||              // end of map(); if a[] was empty:
  print(o)            //   print the output string

```
> 5 votes

# Answer
# Japt `-g`, 18 bytes

```
á f_Ë¸mn36Ãäf mÅeÊ

```

Try it
> 4 votes

# Answer
# Python, ~~181~~ 157 bytes

```
lambda l:[p for p in permutations(l)if(z:=[s.lower()[:-1].split()for s in p],all(sum(k in i for k in j)>1for i,j in zip(z,z[1:])))[1]]
from itertools import*

```

Attempt This Online!

Returns all valid orders.

* -14 thanks to Steffan

## Python, ~~165 163~~ 159 bytes

```
def f(l):
 for p in permutations(l):m=[s.lower()[:-1].split()for s in p];any(sum(k in i for k in j)<2for i,j in zip(m,m[1:]))or print(p)
from itertools import*

```

Attempt This Online!

Based off Kevin Cruijssen's 05AB1E answer. Prints all valid orders.

* -4 thanks to Steffan
> 3 votes

# Answer
# Factor \+ `math.combinatorics math.unicode`, ~~76~~ 73 bytes

```
[ [ [ " "split ] map 2 clump [ last2 ∩ { } = ] ∄ ] find-permutation ]

```

Try it online!

* `[ ... ] find-permutation` Find the first permutation of the input that...
* `[ " "split ] map` ...when all sentences are split into words...
* `2 clump` ...and grouped into overlapping pairs...
* `[ last2 ∩ { } = ] ∄` ...none of the intersections between pairs of sentences are empty.
> 2 votes

# Answer
# Rust, 375 bytes

```
|a:Vec<&str>|{let b=a.iter().map(|i|&i[..i.len()-1]).collect::<Vec::<_>>();f(&b.join(" "),b)};fn f(w:&str,p:Vec<&str>)->bool{p.len()<1||match p.iter().find(|k|{w.split(" ").collect::<HashSet<_>>().intersection(&k.split(" ").collect()).count()>1&&f(k,p.clone().into_iter().filter(|d|d!=*k).collect::<Vec<_>>())}){Some(u)=>print!("{u}.
")==(),_=>false}}use std::collections::*;

```

Attempt This Online!
> 2 votes

# Answer
# Pip, 41 bytes

```
PMgFI{$&((LC(aM H_^s)MP{YbaM_Ny})M1N_>1)}

```

Very golfable, but I'm happy with it.

Attempt This Online!

**Explanation**:

```
PMgFI{$&((LC(aM H_^s)MP{YbaM_Ny})M1N_>1)}
PMgFI{                                  } Filter out permutations of the input by ...
          LC(aM H_^s)                     Remove dot, split by space and lowercase each sentence
                     MP{       }          For consecutive pairs of all sentences,
                        YbaM_Ny           Does each word of the first pair appear in the second pair?
                                 M1N_>1   Is the count of 1s greater than 1 (>= 2)
      $&                                  Are all elements truthy?

```
> 1 votes

---
Tags: code-golf, string, array, sorting
---


# Question
Title: Toggle some bits and get an actual square
Inspired by the title of the *Toggle some bits and get a square* challenge.
In that challenge you output how many bits should be toggled, in order for the base-10 representation of the binary to become a square number.

## Challenge:

In this challenge, you'll be given a bit-matrix \\$M\\$ and an integer \\$n\\$ as inputs.
Output the edge-size of the largest square you can make by toggling at most \\$n\\$ bits in the grid. A square is defined as having a border of `1`s, with an irrelevant inner body.
E.g., these all contain valid squares of size 4x4, highlighted below with `X`:
<sup>(for the third example, more than one 4x4 square is possible)</sup>

```
1111  1111  11111111  010110
1001  1011  11111111  001111
1001  1101  11111111  101011
1111  1111  11111111  111001
                      011111

XXXX  XXXX  XXXX1111  010110
X00X  X01X  X11X1111  00XXXX
X00X  X10X  X11X1111  10X01X
XXXX  XXXX  XXXX1111  11X00X
                      01XXXX

```

**Example:**

So let's say the inputs are \\$n=4\\$ and \\$M=\\$

```
010110
001011
101010
111001
011110

```

You could toggle these three bits (highlighted as `T`):

```
010110
001T11
10101T
111001
01111T

```

to get the 4x4 square of the fourth example above. So the output is `4`.

## Challenge rules:

* You can take the input-grid in any reasonable format. Can be a matrix of integers; matrix of booleans; list of strings; list of integers for which their binary representation (with leading 0s) is the binary grid; etc.
* You toggle at most \\$n\\$ bits, not exactly \\$n\\$ bits.
* The input-matrix \\$M\\$ is not guaranteed to be a square, but it is guaranteed to be a (non-empty) rectangle.
* The input-integer \\$n\\$ is guaranteed to be non-negative (\\$n\geq0\\$).

## General Rules:

* This is , so the shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (e.g. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test Cases:

| Inputs: | Output: |
| --- | --- |
| \\$n\\$=`4` and \\$M\\$= ``` 010110<br>001011<br>101010<br>111001<br>011110 ``` | 4 |
| \\$n\\$=`8` and \\$M\\$= ``` 00101<br>01010<br>11011<br>10010<br>01001 ``` | 4 |
| \\$n\\$=`0` and \\$M\\$= ``` 000<br>000<br>000<br>000 ``` | 0 |
| \\$n\\$=`0` and \\$M\\$= ``` 111<br>111 ``` | 2 |
| \\$n\\$=`1` and \\$M\\$= ``` 101<br>010<br>101 ``` | 1 |
| \\$n\\$=`1000` and \\$M\\$= ``` 100010<br>010010<br>100101<br>100011<br>110110<br>110101<br>010010<br>101001<br>101011 ``` | 6 |

# Answer
> 7 votes
# JavaScript (ES6), 139 bytes

Expects `(n)(matrix)`.

```
n=>m=>m.map(W=h=(X,w,k,Y)=>m.map((r,y)=>r.map((v,x)=>k?h(x,w,q=t=0,y):(x-X)%w&&(y-Y)%w||x<X|x>X+w|y<Y|y>Y+w||++q<w*4|(t+=!v)>n?0:W=w+1)))|W

```

Try it online!

### Commented

```
n =>                    // n = max. number of times we can toggle bits
m =>                    // m[] = binary matrix
m.map(W =               // initialize W to a zero'ish value
h = (X, w, k, Y) =>     // for each entry in m[], using a recursive callback h:
  m.map((r, y) =>       //   for each row r[] at index y in m[]:
    r.map((v, x) =>     //     for each value v at index x in r[]:
      k ?               //       if this is the first pass:
        h(              //         do a recursive call:
          x,            //           set X = x
          w,            //           pass w unchanged
          q = t = 0,    //           set k = q = t = 0
          y             //           set Y = y
        )               //         end of recursive call
      :                 //       else (2nd pass):
        (x - X) % w &&  //         do nothing if we're not located on the grid
        (y - Y) % w ||  //         of width w
        x < X |         //         or x is too low
        x > X + w |     //         or x is too high
        y < Y |         //         or y is too low
        y > Y + w       //         or y is too high
        ||              //         otherwise:
          ++q < w * 4 | //           increment q
          (t += !v) > n //           increment t if v = 0
          ?             //           if q < w * 4 (not a complete square)
                        //           or t > n (too many bits must be toggled):
            0           //             do nothing
          :             //           else:
            W = w + 1   //             success: update W
    )                   //     end of map()
  )                     //   end of map()
) | W                   // end of map(); return W

```

# Answer
> 5 votes
# MATL, 30 bytes

```
xZyP:"0&G@qWQB&+gZ++7Mz<m@*vX>

```

It uses convolution \o/

Inputs are `n`, then `M`.

Try it online! Or verify all test cases.

### Explanation

```
x        % Implicit input: n. Delete
Zy       % Implicit input: M. Size as a length-two vector, [R, C]
P        % Sort. Gives [S, L], where S = min(R, C) is the smallest dimension of A
:        % Range from 1 to the first entry of the vector, that is, A
"        % For each k in [1, 2, ... , A]
  0      %   Push 0
  &G     %   Push the two inputs again: n, then M
  @      %   Push k
  qWQB   %   Subtract 1, 2 raised to that, add 1, binary: gives [1 0 0 ··· 0 1] of
         %   length k
  &+g    %   2D array of pairwise additions. Convert to logical. This gives a binary
         %   k×k array with a frame of ones: [1 1 ··· 1 1;
         %                                    1 0 ··· 0 1;
         %                                    ··· ··· ···
         %                                    1 0 ··· 0 1;
         %                                    1 1 ··· 1 1]
  Z+     %   2D convolution with M, maintaining size. This counts the number of ones
         %   in M along all sliding frames of the above form. The result is a 2D array
  +      %   Add the above with n, element-wise.
  7M     %   Push the 2D array defining the frame again. Number of nonzeros. This
         %   gives the frame "length", that is, the number of ones (which is 4*(k-1))
  <      %   Less than?, element-wise. An entry equal to 0 indicates that a frame
         %   exists such that the number of ones in M along that frame plus n is at
         %   least the frame length
  m      %   Ismember. This checks if 0 is indeed present in the above result
  @*     %   Multiply the above by k. This will give either 0 or k
  vX>    %   Concatenate stack contents, then maximum. This computes a cumulative
         %   maximum of the results for all k (each result being either 0 or k)
         % End (implicit). Display (implicit)

```

# Answer
> 4 votes
# JavaScript (Node.js), 133 bytes

```
n=>m=>m.map(W=h=(X,w,Y,t)=>m.every((r,y)=>[...r,0].every((v,x)=>t?x%w&&y%w||x>w|y>w||(t+=1-(m[y+Y]||0)[x+X]):h(x,w,y,~n)?W=w+1:1)))|W

```

Try it online!

# JavaScript (Node.js), 134 bytes

```
n=>m=>m.map(W=h=(X,w,k,Y)=>m.map((r,y)=>r.map((v,x)=>k?h(x,w,q=t=0,y):x%w&&(y-Y)%w||x>w|y<Y|y>Y+w||++q<w*4|(t+=!r[x+X])>n?0:W=w+1)))|W

```

Try it online!

Modified from Arnauld's

# JavaScript (Node.js), 156 bytes

```
M=>n=>M.map((_,i)=>M.map((N,y)=>N.map((c,x)=>R=M.map((_,j)=>W-=j<i&&N[x+j]+M[y+i][x-~j]+M[y-~j][x]+M[y+j][x+i],W=4*i+!i*!c)&&W<=n?i+1:R),M.push([])),R=0)&&R

```

Try it online!

I don't know what I'm doing...

```
M=>n=> // Unupdated
M.map((_,i)=>
  M.map((N,y)=>N&&
    N.map((c,x)=>
      R=M.map((_,j)=>
        W-=j<i&&
          N[x+j]+
          M[y+i][x-~j]+
          M[y-~j][x]+
          M[y+j][x+i],
        W=4*i)|i|c|n&&    // When i=0
                          // Special consider:
                          // Here is 1, or
                          // n>0
        W<=n?i+1:R),M.push(0)),R=0)&&R
                 // So Z[y+i] isn't undefined

```

# Answer
> 3 votes
# Pyth, 63 bytes

```
KEVUQVUhQVhS,-lQN-lhQHIgKsm!|*F*V-Rbdd@@Q+Nhd+Hed^Uhb2=eS,Zhb;Z

```

Try it online!

Expects array of arrays of booleans and \\$n\\$ in that order.

### Explanation

```
                                                                   # implicitly assign Q = eval(input())
KE                                                                 # assign K = eval(input())
  VUQ                                                              # for N in range(len(Q)):
     VUhQ                                                          #   for H in range(len(Q[0])):
         VhS,-lQN-lhQH                                             #     for b in range(1+max(len(Q)-N, len(Q[0])-H)):
                          m                      ^Uhb2             #       map range(b+1) x range(b+1) to lambda d  (look at coordinates in a square of size b+1)
                           !|                                      #         neither of the following are true
                             *F*V-Rbdd                             #         d[0]*d[1]*(d[0]-b)*(d[1]-b)  (coordinates are in the middle of the square)
                                      @@Q+Nhd+Hed                  #         Q[N+d[0]][H+d[1]]  (coordinates are already a 1 in Q)
                      IgKs                                         #       if K >= (the sum of this map):
                                                      =eS,Zhb      #         Z = max(Z, b+1)
                                                             ;Z    # after all loops complete, output Z

```

# Answer
> 3 votes
# Jelly,  ~~27~~  25 bytes

```
¬ẆZṡLƊ€Ẏ.ị$€JṖḊƊ¦FS>ʋÐḟẈṀ

```

A dyadic Link that accepts the matrix, \\$M\\$, on the left and the maximal toggle count, \\$n\\$, on the right and yields the side length of the largest attainable square.

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

### How?

Toggles all bits of \\$M\\$ and extracts all possible square sub-matrices. Filters out any which have more than \\$n\\$ ones in their border, and then gets the length of the longest remaining one (or zero).

```
¬ẆZṡLƊ€Ẏ.ị$€JṖḊƊ¦FS>ʋÐḟẈṀ - Link: list of lists of 1s and 0s; M, integer, n
¬                         - logical NOT (M) -> toggle all bits of M
 Ẇ                        - get all contiguous sublists of rows of that
      €                   - for each (sublist, s, of rows):
     Ɗ                    -   last three links as a monad - f(s):
  Z                       -     transpose (s)
    L                     -     length (s)
   ṡ                      -     all sublists of (transposed s) of length (length (s))
                              -> all full height square sub-matrices from s
       Ẏ                  - tighten to a list of all square-submatrices
                     Ðḟ   - filter discard those for which:
                    ʋ     -   last four links as a dyad - f(sub-matrix, n)
           €    ¦         -     sparse application...
               Ɗ          -     ...to indices: last three links as a monad - f(sub-matrix):
            J             -                      range of length
             Ṗ            -                      pop
              Ḋ           -                      dequeue -> [2,3,...,length-1]
          $               -     ...action: last two links as a monad - f(sub-matrix):
        .                 -                  0.5
         ị                -                  index into (sub-matrix) -> last and first entries
                 F        -     flatten
                  S       -     sum
                   >      -     is greater than (n)?
                       Ẉ  - length of each (remaining sub-matrix)
                        Ṁ - maximum (or 0 if empty)

```

---

Note: the second  is necessary, even though all of the test cases pass without it (e.g. this should return `2` not `3`).

# Answer
> 2 votes
# Charcoal, 61 bytes

```
ＮθＷＳ⊞υι≔ＬυζＷ⬤υ⬤κ›⁻∨×⁴⊖ζ¹θΣ⭆υ⎇№…λ⁺λζπ✂ξν⁺νζ∨∨⁼πλ⁼π⁺λ⊖ζ⊖ζω≦⊖ζＩζ

```

Try it online! Link is to verbose version of code. Takes `n` as the first input and then the binary matrix `M` as a list of newline-terminated strings. Explanation:

```
Ｎθ

```

Input `n`.

```
ＷＳ⊞υι

```

Input `M`.

```
≔Ｌυζ

```

Start with the height of `M` as the current square size.

```
Ｗ⬤υ⬤κ›⁻∨×⁴⊖ζ¹θΣ⭆υ⎇№…λ⁺λζπ✂ξν⁺νζ∨∨⁼πλ⁼π⁺λ⊖ζ⊖ζω

```

For each possible cell of `M`, try to slice a square of the current size out of `M`, count the number of `1`s on its border, and while none of the candidate squares have enough `1`s...

```
≦⊖ζ

```

... decrement the square size.

```
Ｉζ

```

Output the final square size.

# Answer
> 2 votes
# PARI/GP, 116 bytes

```
f(a,n)=for(k=l=0,min(#a,#a~),matrix(#a~-k,#a-k,i,j,sum(s=0,k,sum(t=0,k,!(s*t*(k-s)*(k-t)+a[i+s,j+t])))<=n)&&l=k+1);l

```

Attempt This Online!

# Answer
> 1 votes
# 05AB1E, 40 bytes

```
U˜āR.Δ…€üÿD'øý.V€`ε4Fćˆíø}¯˜_OXs@´}à}Dd*

```

Since there isn't a 05AB1E answer yet, I'll just create my own.

Inputs in the order \\$n,M\\$.

Try it online or verify all test cases.

**Explanation:**

```
U                  # Pop and store the first (implicit) input-integer in variable `X`
˜                  # Flatten the second (implicit) input-matrix
 ā                 # Push a list in the range [1,length]
  R                # Reverse it to [length,1]
   .Δ              # Pop and find the first value that's truthy for
                   # (or -1 if none are truthy):
     …€üÿD'øý.V€` '#  Get a list of all overlapping block of size y×y
                   #  (where `y` is the current integer):
     …€üÿ          #   Push string "€üÿ",
                   #   where `ÿ` is automatically replaced with the current integer
         D         #   Duplicate it
          'øý     '#   Join the two strings on the stack with "ø" delimiter
             .V    #   Evaluate and execute it as 05AB1E code:
      €            #    Map over each row of the (implicit) input-matrix
       üy          #     Get all overlapping lists of this row of size `y`†
         ø         #    Zip/transpose; swapping rows/columns
          €        #    Map over each list of lists
           üy      #     Get all overlapping lists of these row of size `y`†
             €`    #    Flatten this list of lists of blocks one level down
     ε4Fćˆíø}¯´˜   #  Leave just the borders of each y×y block:
     ε             #   Map over each block:
      4F           #    Inner loop 4 times:
        ć          #     Extract head; pop and push remainder-matrix and first row
                   #     separately to the stack
         ˆ         #     Pop and add this first row to the global array
          íø       #     Rotate the matrix once clockwise:
          í        #      Reverse each inner row
           ø       #      Zip/transpose; swapping rows/columns
       }¯          #    After the loop: push the global array
         ˜         #    Flatten it
          _        #    ==0 check (0 becomes 1; everything else becomes 0)
           O       #    Sum to get the amount of 0s in this block's borders
            X      #    Push the first input from variable `X`
             s@    #    Check amountOfZeros <= `X`
        ´          #    Empty the global array for the next iteration
     }à            #   After the map, do an `any` check by popping and pushing the max
   }Dd*            #  After the find first: fix a potential -1 to 0†:
    D              #   Duplicate the integer
     d             #   Pop the copy and do a non-negative check (1 if >=0; 0 if <0)
      *            #   Multiply the two together
                   # (after which the result is output implicitly)

```

We have to do the `}Dd*` instead of just lowering the `[length,1]` ranged list to `[length,0]`, because `ü0` would give an error.

---
Tags: code-golf, number, grid, binary-matrix
---


title: Chaining autograms

text:
# Question
Title: Chaining autograms
Write a program that takes one integer input *n* and one format letter and outputs *n* autograms in the format `This sentence contains ? "A"s, ? "B"s ... and ? "Z"s.`

* Each question mark `?` represents the number of times the the following letter appears in the text
* All numbers will be written as text. To make it equally unfair for Americans and Brits your program has to be able to print either system! Pass a format letter in to choose which system, `A` for American and `B` for British. This will not matter for the first few sentences as they will have fewer than one hundred of each letter but will definitely be needed by the time you get to ten sentences
    + American: `one hundred twenty three`, etc.
    + British: `one hundred and twenty three`, etc.
* The integer (let's call it *n*) is used to vary the number of sentences produced. When *n* is greater than `1` each subsequent sentence will start with two newlines and then the following text: `The preceding text plus this sentence contain ...` where the ellipsis `...` represents the count of each letter that appears
* You do not have to include a letter if it doesn't otherwise appear, although if you do choose to, it might simplify the challenge. I don't know, though, it might make it harder so it's your call! If you include all twenty six letters your answer will also be a pangram!
* You can't say `zero "Y"s` because you have to use a `Y` to say it!
* You can only say `one "Y"` if `Y` doesn't appear anywhere else in the text
* You can't repeat a letter and its count within each sentence, i.e. `three "N"s, three "N"s` is not allowed
* Your output must use good English! Any appearance of `... "X"s, one "Y"s...`, for example, will invalidate your answer!
* In each sentence you must enumerate the letters in alphabetical order
* Only letters `A-Z` will be counted, not symbols, punctuation or spaces
* The letters will be counted case-insensitively, i.e. `A` will be equivalent to `a`

Since the level *n* output also contains the output for each lower level to *n-1* you only need to show your source code and the output for level 10. There may be multiple solutions so your answer might be different from someone else's answer!

An example (*n*=1) is:

```
This sentence employs two a’s, two c’s, two d’s, twenty-eight e’s, five f’s, three g’s, eight h’s, eleven i’s, three l’s, two m’s, thirteen n’s, nine o’s, two p’s, five r’s, twenty-five s’s, twenty-three t’s, six v’s, ten w’s, two x’s, five y’s, and one z.

```

Note, however, that my requirements are slightly different! You must use `contains`, not `employs` and surround each letter (in capitals) with double quotes `"`. It's your choice whether you use hyphens `-` or not between the words of the numbers.

Your final output will look something like this. Note that the first sentence uses `contains` but the subsequent sentences use `contain`:

```
This sentence contains ten "A"s, ...

The preceding text plus this sentence contain twenty "A"s, ...

The preceding text plus this sentence contain thirty "A"s, ...

...

The preceding text plus this sentence contain one hundred "A"s, ...

```

You can use the following snippet to check your output.

```
// Apologies for the hugeness of this snippet. It's my first!
word = {
  1: 'one',
  2: 'two',
  3: 'three',
  4: 'four',
  5: 'five',
  6: 'six',
  7: 'seven',
  8: 'eight',
  9: 'nine',
  10: 'ten',
  11: 'eleven',
  12: 'twelve',
  13: 'thirteen',
  14: 'fourteen',
  15: 'fifteen',
  16: 'sixteen',
  17: 'seventeen',
  18: 'eighteen',
  19: 'nineteen',
  20: 'twenty',
  30: 'thirty',
  40: 'forty',
  50: 'fifty',
  60: 'sixty',
  70: 'seventy',
  80: 'eighty',
  90: 'ninety',
  100: 'hundred',
  1000: 'thousand',
}

var format;

function count_letters() {
  var check_text = [];
  var text = document.getElementById("golf").value;
  text = text.replace(/-/g, " ");
  text = text.replace(/\r\n?/g, "\n");
  format = text.match(/\w\w and /)? 'B': 'A';
  var lines = text.split(/\n\n/);
  var let_count = {};
  for (n = 0; n < lines.length; ++n) {
    var keys = [];
    var sentence = '';
    var letters = lines[n].toUpperCase().match(/[A-Z]/g);
    for (var i = 0; i < letters.length; ++i) {
      if (!(letters[i] in let_count)) {
        let_count[letters[i]] = 0;
      }
      let_count[letters[i]]++;
    }
    for (i in let_count) {
      if (let_count.hasOwnProperty(i)) {
        keys.push(i);
      }
    }
    keys.sort();
    for (i = 0; i < keys.length - 1; ++i) {
      if (sentence) {
        sentence += ", ";
      }
      var num_text = number(let_count[keys[i]], format);
      sentence += num_text + ' "' + keys[i] + '"';
      if (let_count[keys[i]] > 1) {
        sentence += "s";
      }
    }
    num_text = number(let_count[keys[i]], format);
    sentence += " and " + num_text + ' "' + keys[i] + '"';
    if (let_count[keys[i]] > 1) {
      sentence += "s";
    }
    sentence = check_text.length == 0? "This sentence contains " + sentence + ".": "The preceding text plus this sentence contain " + sentence + ".";
    check_text.push(sentence);
  }
  document.getElementById("output").value = check_text.join("\n\n");

  for (n = 0; n < lines.length; ++n) {
    if (check_text[n] != lines[n]) {
      break;
    }
  }
  document.getElementById("correct").innerText = n;
}

function number(num, format) {
  num = (num + "").split("").reverse().join("");
  digit = num.match(/\d/g);
  text = "";

  // Thousands
  if (digit[3]) {
    text += word[digit[3]] + " " + word[1000];
    // Hundreds
    if (digit[2] > 0) {
      text += " ";
    }
    // Tens and units
    else if ((digit[1] + digit[0]) * 1 > 0) {
      text += " and ";
    }
  }

  // Hundreds
  if (digit[2] > 0) {
    text += word[digit[2]] + " " + word[100];
    // Tens and units
    if ((digit[1] + digit[0]) * 1 > 0) {
      text += " and ";
    }
  }
  if (typeof(digit[1]) == "undefined") {
    digit[1] = 0;
  }
  if (digit[1] < 2) {
    if ((digit[1] + digit[0]) * 1) {
      text += word[(digit[1] + digit[0]) * 1];
    }
  }
  else {
    text += word[digit[1] * 10];
    if (digit[0] > 0) {
      text += " " + word[digit[0]];
    }
  }

  if (format != 'B') {
    text = text.replace(/ and /g, format == 'A'? " ": " ! ");
  }

  return text;
}
```

```
<textarea id="golf" cols="80" rows="25">
This sentence employs two "A"s, two "C"s, two "D"s, twenty-eight "E"s, five "F"s, three "G"s, eight "H"s, eleven "I"s, three "L"s, two "M"s, thirteen "N"s, nine "O"s, two "P"s, five "R"s, twenty-five "S"s, twenty-three "T"s, six "V"s, ten "W"s, two "X"s, five "Y"s, and one z.</textarea><br/>
<input type="button" value="Count the letters!" onclick="count_letters()"/><br/>
<textarea id="output" cols="80" rows="10">
</textarea><br/>
Number of correct sentences: <span id="correct"></span>
```

# Answer
> 2 votes
# Haskell, 2161 bytes

```
-- https://codegolf.stackexchange.com/questions/51264/chaining-autograms
-- https://www.leesallows.com/files/Reflexicons%20NEW(4c).pdf

import Data.Char
import Data.List
import Data.Array

import System.IO.Unsafe
import System.Random

pick []=[]
pick pool=[pool!!(unsafePerformIO.randomRIO)(0,length pool-1)]

instance (Num a, Ix i) => Num(Array i a) where
 a+b=accum(+)a(assocs b)
 a-b=accum(-)a(assocs b)
 (*)=undefined;fromInteger=undefined;signum=undefined;abs=undefined

azarra=accumArray(+)0('A','Z')::[(Char,Int)]->Array Char Int
squeeze=azarra.map(\c->(toUpper c,1)).filter isLetter

autogram n b = let
 band
  |b=='B'=" and "
  |b=='A'=" "
 name 0="zero";
 name 1="one"
 name 2="two"
 name 3="three"
 name 4="four"
 name 5="five"
 name 6="six"
 name 7="seven"
 name 8="eight"
 name 9="nine"
 name 10="ten"
 name 11="eleven"
 name 12="twelve"
 name 13="thirteen"
 name 14="fourteen"
 name 15="fifteen"
 name 16="sixteen"
 name 17="seventeen"
 name 18="eighteen"
 name 19="nineteen"
 name 20="twenty"
 name 30="thirty"
 name 40="forty"
 name 50="fifty"
 name 60="sixty"
 name 70="seventy"
 name 80="eighty"
 name 90="ninety"
 name n|n<100=name(10*div n 10)++'-':name(mod n 10)
 name n|n<1000&&mod n 100==0=name(div n 100)++" hundred"
 name n|n<1000=name(100*div n 100)++band++name(mod n 100)
 name n|mod n 1000==0=name(div n 1000)++" thousand"
 name n=name(1000*div n 1000)++" "++name(mod n 1000)

 endr=9999
 nam2 0=""
 nam2 i='s':name(1+i)
 wtwo(i,v)=if v>0 then tail$nam2 v++" \""++[i]++"\"s" else ""
 repr=listArray(0,endr)$map(squeeze.nam2)[0..endr]
 self=foldl1(+).map(repr!).filter(>0).elems

 solv pret=let
  fixall guess=pret+self guess
  deficit guess=fixall guess-guess
  fixone guess=accum(+)guess$pick.filter((/=0).snd).assocs.deficit$guess
  terminate(a:b:c)|a==b=a|True=terminate(b:c)
  in terminate$iterate(fixone.fixall)pret

 solve prepent=
  (prepent++).(++".\n").
  intercalate", ".(\s->init s++["and "++last s]).map wtwo.
  filter((>0).snd).assocs.solv.squeeze$prepent++"and"

 in solve$if n==1 then "This sentence contains "
  else autogram(n-1)b++"The preceding text plus this sentence contain "

main=putStrLn $ autogram 2 'B'

```

Try it online!

```
This sentence contains three "A"s, three "C"s, two "D"s, twenty-seven "E"s, four "F"s, two "G"s, ten "H"s, eight "I"s, thirteen "N"s, six "O"s, ten "R"s, twenty-five "S"s, twenty-three "T"s, three "U"s, three "V"s, six "W"s, three "X"s, and four "Y"s.
The preceding text plus this sentence contain six "A"s, seven "C"s, five "D"s, sixty-four "E"s, thirteen "F"s, six "G"s, eighteen "H"s, twenty-six "I"s, four "L"s, thirty-three "N"s, eleven "O"s, three "P"s, nineteen "R"s, fifty-five "S"s, forty-five "T"s, seven "U"s, eleven "V"s, eight "W"s, nine "X"s, and ten "Y"s.
The preceding text plus this sentence contain ten "A"s, eleven "C"s, eleven "D"s, one hundred and fourteen "E"s, nineteen "F"s, ten "G"s, twenty-six "H"s, forty-two "I"s, nine "L"s, sixty-seven "N"s, eighteen "O"s, six "P"s, twenty-five "R"s, eighty-six "S"s, seventy-one "T"s, eleven "U"s, nineteen "V"s, thirteen "W"s, fifteen "X"s, and seventeen "Y"s.
The preceding text plus this sentence contain seventeen "A"s, fifteen "C"s, twenty-six "D"s, one hundred and sixty-three "E"s, twenty-eight "F"s, fifteen "G"s, thirty-nine "H"s, sixty-two "I"s, twelve "L"s, one hundred and eight "N"s, twenty-seven "O"s, nine "P"s, thirty-five "R"s, one hundred and fifteen "S"s, one hundred and nine "T"s, eighteen "U"s, twenty-four "V"s, twenty-two "W"s, twenty "X"s, and twenty-nine "Y"s.
The preceding text plus this sentence contain twenty-four "A"s, nineteen "C"s, forty-one "D"s, two hundred and eight "E"s, forty-five "F"s, nineteen "G"s, fifty-two "H"s, seventy-eight "I"s, fifteen "L"s, one hundred and forty-two "N"s, forty-seven "O"s, twelve "P"s, fifty-four "R"s, one hundred and forty-three "S"s, one hundred and forty-seven "T"s, twenty-six "U"s, thirty-one "V"s, thirty-one "W"s, twenty-three "X"s, and forty-five "Y"s.
The preceding text plus this sentence contain thirty-two "A"s, twenty-three "C"s, fifty-nine "D"s, two hundred and fifty-six "E"s, fifty-nine "F"s, twenty-seven "G"s, seventy-two "H"s, one hundred and six "I"s, seventeen "L"s, one hundred and eighty-one "N"s, fifty-eight "O"s, fifteen "P"s, sixty-eight "R"s, one hundred and seventy-five "S"s, one hundred and eighty-nine "T"s, thirty-four "U"s, thirty-eight "V"s, thirty-eight "W"s, twenty-nine "X"s, and sixty-three "Y"s.
The preceding text plus this sentence contain forty "A"s, twenty-seven "C"s, seventy-seven "D"s, three hundred and eight "E"s, sixty-seven "F"s, thirty-five "G"s, ninety "H"s, one hundred and twenty-five "I"s, nineteen "L"s, two hundred and eighteen "N"s, seventy "O"s, eighteen "P"s, eighty-four "R"s, two hundred and eight "S"s, two hundred and twenty-eight "T"s, forty-two "U"s, forty-seven "V"s, forty-six "W"s, thirty-three "X"s, and seventy-nine "Y"s.
The preceding text plus this sentence contain fifty-one "A"s, thirty-one "C"s, one hundred and four "D"s, three hundred and forty-nine "E"s, eighty-five "F"s, forty "G"s, one hundred and eight "H"s, one hundred and forty-nine "I"s, twenty-one "L"s, two hundred and sixty-one "N"s, ninety-two "O"s, twenty-one "P"s, one hundred and four "R"s, two hundred and thirty-six "S"s, two hundred and sixty-five "T"s, fifty-five "U"s, fifty-two "V"s, fifty-four "W"s, thirty-eight "X"s, and ninety-seven "Y"s.
The preceding text plus this sentence contain sixty-four "A"s, thirty-five "C"s, one hundred and thirty-seven "D"s, four hundred and six "E"s, ninety-four "F"s, forty-three "G"s, one hundred and twenty-nine "H"s, one hundred and sixty-seven "I"s, twenty-five "L"s, three hundred and eleven "N"s, one hundred and eleven "O"s, twenty-four "P"s, one hundred and twenty-eight "R"s, two hundred and seventy "S"s, three hundred and two "T"s, seventy-one "U"s, sixty-one "V"s, sixty-two "W"s, forty-six "X"s, and one hundred and thirteen "Y"s.
The preceding text plus this sentence contain seventy-eight "A"s, thirty-nine "C"s, one hundred and seventy-three "D"s, four hundred and seventy "E"s, one hundred and seven "F"s, fifty-one "G"s, one hundred and fifty-five "H"s, one hundred and eighty-eight "I"s, twenty-seven "L"s, three hundred and sixty-two "N"s, one hundred and twenty-eight "O"s, twenty-seven "P"s, one hundred and fifty-one "R"s, three hundred and four "S"s, three hundred and forty-three "T"s, eighty-six "U"s, seventy "V"s, sixty-eight "W"s, fifty-one "X"s, and one hundred and thirty-two "Y"s.

```

---
Tags: code-golf
---


# Question
Title: Print the notes of an increasing octave-repeating scale
## Challenge

To quote Wikipedia:

> An octave-repeating scale can be represented as a circular arrangement of pitch classes, ordered by increasing (or decreasing) pitch class. For instance, the increasing C major scale is C–D–E–F–G–A–B–\[C\], with the bracket indicating that the last note is an octave higher than the first note.

Major scales are defined by their combination of semitones and tones (whole steps and half steps):

```
Tone – Tone – Semitone – Tone – Tone – Tone – Semitone

```

Or in whole steps and half steps, it would be:

```
Whole – Whole – Half – Whole – Whole – Whole – Half

```

So, for example, in the C major scale, we first start with the C note.  Then we go up a tone (whole step) to a D  Another tone (whole step) to an E  Now a semitone (half step) to an F  Tone (whole step) to a G  Tone (whole step) to an A  Tone (whole step) to a B  And finally, a semitone (half step) to a C again  A minor scale (I'm talking about the natural minor scale as opposed to the harmonic minor scale and the melodic minor scale) follows the following formula

```
Tone – Semitone – Tone – Tone – Semitone – Tone – Tone

```

or

```
Whole – Half  – Whole – Whole – Half – Whole – Whole

```

So, the C minor scale will look like  or, as letters: `C, D, D#, F, G, G#, A#`

So, your job today is: given a major or minor scale, print the notes.

## Input/Output

* Input/Output can be taken in any reasonable format for taking the name of the scale and returning the set of the increasing octave-repeating notes of that scale.
* You don't need to print out the last note.
* If the *notes* are enharmonic equivalent (same note but different names, eg A#/Bb), you can print either of them, but you can't print C as B# or E as Fb)
* If the *scales* are enharmonic equivalent (same scale but different names eg G#m and Abm), you have to handle both of them.

```
Input -> Output
C -> [C, D, E, F, G, A, B]
Cm -> [C, D, Eb (D#), F, G, Ab (G#), Bb (A#)]
G -> [G, A, B, C, D, E, F# (Gb)]
F#m -> [F# (Gb), G# (Ab), A, B, C# (Db), D, E]

```

This is , so the shortest answer (in bytes) wins!

# Answer
> 8 votes
# Vyxal, 27 bytes

*-1 byte thanks to AndrovT*

First input is the note, second is the scale; 0 for minor and 1 for major.

`kA7Ẏ:\#ẊY3⟇8⟇~ḟǓ»°f»b⁰9*ǔ*ꜝ`

I'm a bit rusty.

Try it Online! | 35 bytes if you have to handle flats

**Explanation:**

```
kA7Ẏ:\#ẊY3⟇8⟇~ḟǓ»°f»b⁰9*ǔ*ꜝ
kA7Ẏ                           Uppercase alphabets A-H
    :\#ẊY                      Duplicate, take cartesian product with "#", interleave
         3⟇8⟇                  Remove third and remove eight char (I know, very cringe)
             ~ḟǓ               Find index of note, rotate list by index
                »°f»b          Compressed number 2906, binary "101101011010"
                     ⁰9*       Multiply scale by 9, pushes 9 for major and 0 for minor
                        ǔ      Rotate "101101011010" by 0 or 9
                         *ꜝ    Filter out list by binary string

```

# Answer
> 6 votes
# JavaScript (Node.js), 137 bytes

```
(B,[E]=B.split`m`,h=E=>E[1]>{}?E[0]:E[1]||{B,E}[E]?'ABCDEFG'['0x'+E[0]-9|0]:E+'#',g=k=>[E,...k?g(k>>1,E=h(k&1?h(E):E)):[]])=>g(E<B?45:59)

```

Try it online!

# JavaScript (Node.js), 140 bytes

```
f=(x,i,g=k=>[R[i%12],...k?g(k>>1,i+=7-k%2*5):[]])=>x==R[i]?g(59):x==R[i]+'m'?g(45):f(x,-~i)
R='BGbDbAbEbBbFCGDAEBF#C#G#D#A#'.match(/.#?b?/g)

```

Try it online!

---

# JavaScript (Node.js), 119 bytes

```
m=>E=>(B=a=>[E,...a?B(a>>1,E=(h=E=>E[1]>B?E[0]:E[+!{B,E}[E]]?'ABCDEFG'['0x'+E[0]-9|0]:E+'#')(a&1?h(E):E)):[]])(m?45:59)

```

Try it online!

taking minor as argument

As reference since others do this

```
m=>E=>(
h=E=>E[1]>B?     // B == 'a=>...', >B is 'b'
  E[0]           // remove 'b'
:
  E[+!{B,E}[E]]? // if E=='B' or E=='E'
                 // then +!truthy=0 aka len>=1
                 // else +!falsy=1 aka len>=2
    'ABCDEFG'['0x'+E[0]-9|0]
                 // 0xA-9==1 0xF-9==6 0xG-9==NaN
  :E+'#',        // Else sharpen
B=a=>[
  E,             // This
  ...a?B(        // Loop through
    a>>1,
    E=h(a&1?h(E):E)
  ):[]]          // twice for set bit
)(m?45:59)

```

# Answer
> 5 votes
# 05AB1E, 29 bytes

```
Au'#æâJŽyhbÏDIkƵ;ºŽ∍ÁĆ‚Iè.¥+è

```

Two loose inputs, where the first input is the note and second is the scale as `1` for major and `0` for minor. Output as a list of notes. I/O uses high-pitched notes (with `#`).

Try it online or verify all test cases.

**Explanation:**

```
Au'#æâJŽyhb '# Push notes-list ["A","A#","B","C","C#","D","D#","E","F","F#","G","G#"]:
Au           #  Push the uppercase alphabet
  '#        '#  Push character "#"
    æ        #  Pop and push its powerset to pair it with an empty string: ["","#"]
     â       #  Take the cartesian product with the alphabet
      J      #  Join each inner pair together to a string
       Žyh   #  Push compressed integer 15343
          b  #  Convert it to binary: 11101111101111
           Ï #  Keep the strings at the truthy (==1) indices
D            # Duplicate the list of notes
 Ik          # Pop the copy, and get the index of the first input-note
Ƶ;           # Push compressed integer 212
  º          # Mirror it to 212212
Ž∍Á          # Push compressed integer 22122
   Ć         # Enclose; append its own head: 221222
    ‚        # Pair them together: [212212,221222]
     Iè      # Keep the one at the second input-scale's index
       .¥    # Undelta with leading 0 (212212→[0,2,3,5,7,8,10]; 221222→[0,2,4,5,7,9,11])
         +   # Add the index of the input-note to each
          è  # Use that list to index into the notes-list
             # (after which the resulting list of notes is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Žyh` is `15343`; `Ƶ;` is `212`; and `Ž∍Á` is `22122`.

# Answer
> 5 votes
# JavaScript (Node.js), 108 bytes

*-3 thanks to @l4m2*

Expects `(m, s)`, where `m` is a binary flag (0 for major, 1 for minor). Returns a comma-separated string of notes.

```
f=(m,s,n=59-14*m)=>n?s+[,f(B=Buffer,B((h=([a,b])=>a%3*!b?[a,35]:[b%5?a:~-a%7+65])((n&1?h:B)(B(s)))),n>>1)]:s

```

Try it online!

### How?

The algorithm is designed to go directly from one note to the next by adding a semitone. Depending on the scale structure, this is done either once or twice per iteration.

### Commented

```
f = (                 // f is a recursive function taking:
  m, s,               //   m = 'minor' flag, s = note string
  n = 59 - 14 * m     //   n = scale bitmask (major: 111011, minor: 101101)
) =>                  //
n ?                   // if n is not equal to 0:
  s + [,              //   append s, followed by a comma, followed by ...
    f(                //   ... the result of a recursive call:
      B = Buffer,     //     B = alias for Buffer (m is not needed anymore)
      B(              //     turn back into a string ...
        ( h =         //       ... the result of the helper function h
          ([a, b]) => //       taking (a, b) = (note, symbol) as ASCII codes
          a % 3 *     //         if the note is neither 'B' nor 'E'
          !b ?        //         and there's no symbol:
            [ a, 35 ] //           leave the note unchanged and append a '#'
          :           //         else:
            [ b % 5 ? //           if the symbol is 'b':
                a     //             just remove the 'b'
              :       //           else:
                ~-a   //             advance to the next note
                % 7   //             (make sure to wrap from 'G' to 'A')
                + 65  //             and don't put any symbol
            ]         //
        )(            //       invoke h:
          ( n & 1 ? h //         twice if the LSB of n is set --> h(h(B(s))
                  : B //         or just once otherwise --> h(B(B(s))
          )(B(s))     //         note that B(B(s)) is equivalent to B(s)
        )             //
      ),              //     end of Buffer()
      n >> 1          //     right-shift n by 1 position
    )                 //   end of recursive call
  ]                   //
:                     // else:
  s                   //   append the last note and stop the recursion

```

---

# JavaScript (Node.js), 131 bytes

Supporting the format used in the test cases (e.g. `F#m`) is rather costly.

```
f=(n,s=n.replace(/m/,_=>(n=45,''),n=59))=>n?s+[,f(n>>1,(B=Buffer)((h=([a,b])=>a%3*!b?[a,35]:[b%5?a:~-a%7+65])((n&1?h:B)(B(s)))))]:s

```

Try it online!

# Answer
> 5 votes
# Charcoal, 63 bytes

```
≔FCGDAEBηＦ⁺⁻⁵Ｉ⪪§⪪”)¶▶↷“Mν&”⁷№θm¹⁺⌕η§θ⁰×⁷⁻№θ#№θb«§ηι×#÷ι⁷×b±÷ι⁷→

```

Try it online! Link is to verbose version of code. Explanation: Based on my answer to Output the 12 Bar Blues so has all of the caveats of that answer i.e. it uses strict music theoretical scales and works with any number of sharps or flats except that it uses `##` instead of `x`.

```
≔FCGDAEBη

```

Get the list of fifths.

```
Ｆ⁺⁻⁵Ｉ⪪§⪪”)¶▶↷“Mν&”⁷№θm¹⁺⌕η§θ⁰×⁷⁻№θ#№θb«

```

Split the compressed string `53164205386497` into digits, taking the first or second half depending on whether a major or minor scale is required, subtract each digit from `9`, and add on the index of the input in the list of fifths, adding `7` for each `#`, and subtracting `7` for each `b`. Loop over the resulting list.

```
§ηι

```

Output the appropriate note by cyclic indexing.

```
×#÷ι⁷×b±÷ι⁷

```

Output the appropriate number of sharps or flats.

Leave a space between notes.

# Answer
> 4 votes
# C (gcc), ~~211~~ ~~209~~ 203 bytes

* -6 thanks to ceilingcat

Takes a key in note\[accidental\]\[minor\] form: e.g. `C`, `Bb`, `G#m`

```
char*a="A#BC#D#EF#G#",*d="b-#",*u;t,l,v;f(char*s){t=index(a,*s++)-a;(u=index(d,*s))&&*u&&(s++,t=(t+u-d+11)%12);l=*s?180:236;for(t--;l/=2;printf("%c%c ",a[v-35?t:(t+11)%12],v-35?32:v))v=a[t=(l%2-~t)%12];}

```

Try it online!

```
char*a="A#BC#D#EF#G#", // Notes (ignoring sharps/flats)
    *d="b-#", // Sharp/nothing/flat (used to adjust a note)
    *u; // Used for determining the existence of a sharp/flat
t,l,v; // Index into notes, scale pattern, current note when doing scale
f(char*s){
  t=index(a,*s++)-a; // Find base note
  (u=index(d,*s))&&*u&&(s++,t=(t+u-d+11)%12); // Find sharp/flat: adjust index accordingly
  l=*s?180:236; // Find major/minor pattern (each has a starting +1 to help the upcoming loop)

  for(t--; // Decrement the starting index to allow the code to do the printing stuff once in the loop
      l/=2; // Keep printing the scale until done
      printf("%c%c ",
        a[v-35?t:(t+11)%12], // Adjust to the base note if needed
        v-35?32:v)) // Print a sharp if needed
    v=a[t=(l%2-~t)%12]; // Get the next note
}

```

# Answer
> 1 votes
# Thunno, \\$ 70 \log\_{256}(96) \approx \\$ 57.62 bytes

```
AZ7RAI'#d""TrsZ!.J15343bZZgAJ'1=k.AKDz0sAh212212 221222ZPz1AIdz(0ZN+AI

```

Attempt This Online!

A very long port of Kevin Cruijssen's 05AB1E answer.

#### Explanation

```
AZ7RAI     # The first 7 letters of the alphabet, A to G
      '#d '# The list ['#']
""T        # With "" appended to it
   r       # Reversed
    sZ!    # Then take the cartesian product of that and A-G
       .J  # Join each inner list
15343bZZ   # Zipped with the binary representation of 15343
        g  # Filtered of where:
AJ         #   the first element
  '1=     '#   is a 1
     k     # (End filter)
      .AK  # Last element of each
         D # Duplicate this
z0sAh      # Get the index of the first input in this list
212212     # The number 212212
221222     # And the number 221222
      ZP   # Paired together
z1AI       # Index the second input into this list
    dz(    # Cumulative sums of this number
       0ZN # With a 0 prepended
+          # Added to the index of the first input in the list
 AI        # Indexed into that list
           # Implicit output

```

---
Tags: code-golf, music
---


# Question
Title: What is the simplest reversible circuit that computes conjugacy of transpositions?
Reversible computation refers to computation in which little or no information is deleted. Reversible computation a major component of quantum computation, and reversible computation is potentially many times more energy efficient than conventional computation. I want to know how easy it is to compute the conjugacy of transpositions reversibly?

# Challenge

Let `T5` be the set of all transpositions on the set `{1,2,3,4,5}`. Let  *be the conjugacy operation on `T5` defined by `x * y=xyx^(-1)` (here concatenation denotes the symmetric group operation). In other words, the underlying set of `T5` consists of all 10 pairs `(a,b)` of distinct numbers from `{1,2,3,4,5}` and where we declare `(a,b)=(b,a)`. The operation*  is the unique operation on the underlying set that satisfies

* `(a,b) * (c,d)=(c,d)`,
* `(a,b) * (b,c)=(a,c)`,
* `(a,b) * (a,b)=(a,b)`

whenever `a,b,c,d` are distinct.

What is the simplest `n` bit input reversible circuit `C` along with an injective function `R:T5->{0,1}^(n/2)` such that `C(R(x)||R(y))=R(x)||R(x*y)` for all `x,y` in `T5`?

The gate cost of a reversible circuit shall be the sum of the costs of every individual logic gate in the reversible circuit.

Here is the price chart per logic gate (see this link for a description of the logic gates) along with a description of the reversible gates.

Each SWAP gate `(x,y)->(y,x)` will have a cost of `0`.

Each NOT gate `x-> NOT x` shall have a cost of `1`.

Each CNOT gate `(x,y)->(x,x XOR y)` shall have a cost of `2`.

Each Fredkin gate `(x,y,z)->(x,(NOT x AND y) OR (x AND z),(x AND y) OR (NOT x AND z))` shall have a cost of `4` (the Fredkin gate can also be described as the reversible logic gate where `(0,x,y)->(0,x,y)` and `(1,x,y)->(1,y,x)`).

Each Toffoli gate `(x,y,z)->(x,y,(x AND y) XOR z)` shall have a cost of `5`.

No other gates are allowed.

Observe that each reversible gate has the same number of inputs as it has outputs (this feature is required for all reversible gates).

The complexity of your circuit will be the product of the gate cost or your circuit with the number `n` which you choose. The goal of this challenge will be to minimize this measure of complexity.

# Format

Complexity: This is your final score. The complexity is the product of the number `n` with your total gate cost.

Space: State the number `n` of bits that your circuit `C` acts on.

Total gate cost: State the sum of the costs of each of the individual gates in your circuit `C`.

NOT gate count: State the number of NOT gates.

CNOT gate count: State the number of CNOT gates.

Toffoli gate count: How many Toffoli gates are there?

Fredkin gate count: How many Fredkin gates are there?

Legend: Give a description of the function `R`. For example, you may write

`(1,2)->0000;(1,3)->0001;(1,4)->0010;(1,5)->0011;(2,3)->0100;
(2,4)->0101;(2,5)->0110;(3,4)->0111;(3,5)->1000;(4,5)->1001`.

Gate list: Here list the gates in the circuit `C` from first to last. Each gate shall be written in the form \[Gate type abbreviation,lines where the gates come from\]. For this problem, we shall start with the 0th bit. The following list specifies the abbreviations for the type of gates.

`T`-Toffoli gate `S`-Swap gate `C`-CNOT gate `F`-Fredkin gate `N`-Not gate.

For example, `[T,1,5,3]` would denote a Toffoli gate acting on the 1st bit, the 5th bit, and the 3rd bit. For example, `[T,2,4,6]` produces the transformation `01101010->01101000` and `[C,2,1]` produces `011->001,010->010` and `[N,3]` produces `0101->0100`. For example, one could write `[S,7,3],[N,2],[T,1,2,3],[F,1,2,5],[C,7,5]` for the gate list.

The gates act on the bit string from left to right. For example, the gate list `[C,0,1],[C,1,0]` will produce the transformation `01->11`.

# Sample answer format

Complexity: `128`

Space: `8`

Total gate cost: `16`

NOT gate count: `3`

CNOT gate count: `2`

Toffoli gate count: `1`

Fredkin gate count: `1`

Legend: `(1,2)->0000;(1,3)->0001;(1,4)->0010;(1,5)->0011;(2,3)->0100;
(2,4)->0101;(2,5)->0110;(3,4)->0111;(3,5)->1000;(4,5)->1001`

Gate list: `[N,1],[N,0],[N,3],[S,1,2],[S,2,3],[C,0,1],[C,2,3],[T,3,2,1],[F,2,3,1]`

The sample answer format is not a solution to the problem but is a template for the format for a solution.

# Answer
> 2 votes
# ~~640~~ 480

```
Complexity: 480
CSWAP count: 12
Legand: (1,2)->11000, (1,3)->10100, ..., (4,5)->00011
Gate:
[1,6,7],
[3,6,8],[3,6,7],
[4,6,9],[4,6,7],
[5,6,10],
[SWAP,6,7],
[5,6,10],
[4,6,7],[4,6,9],
[3,6,7],[3,6,8],
[1,6,7]

```

Use 6 and 7 as a stack to push the two mentioned pairs, then swap them and pop back. the chosen one of 6 or 7 is initially on stack top, if the other isn't

---
Tags: math, code-challenge, permutations, logic-gates
---


# Question
Title: Weighted average - the pressup trend problem
Let's say that this array is how many press-ups I've achieved each day in the last 28 days:

```
[
  20,20,20,30,30,30,30,
  35,35,40,40,40,45,45,
  50,50,50,50,50,50,50,
  60,70,80,90,100,110,120
]

```

As you can see, it's taken a steep upward trend in the last week, and that's the part of this data I'm most interested in. The further in the past it is, the less I want that data to feature in my 'average' number of press-ups.

To that end, I want to work out an 'average' where each week is worth more than the previous week.

---

Background information, not part of this problem.

Normal average:

The sum of all values / the number of values

For above:

1440 / 28 = 51.42857142857143

---

Weighted average:

Split the array into 4 groups of 7, and start up a new array.

* Add the first group to the array.
* Add the second group to the array twice.
* Add the third group to the array thrice.
* Add the fourth group to the array four times.

Sum all of the new array, and divide by the length of the *new* array.

For above:

Convert the array to this:

```
[
  20,20,20,30,30,30,30, # first week once
  35,35,40,40,40,45,45,
  35,35,40,40,40,45,45, # second week twice
  50,50,50,50,50,50,50,
  50,50,50,50,50,50,50,
  50,50,50,50,50,50,50, # third week thrice
  60,70,80,90,100,110,120,
  60,70,80,90,100,110,120,
  60,70,80,90,100,110,120,
  60,70,80,90,100,110,120 # Fourth week four times
]

```

Then run a normal average on that array.

4310 / 70 = 61.57142857142857

Note that it's higher than the normal average value because of the upward trend in the last week.

---

The rules:

* The input is a flat array of 28 nonnegative integers.
* Any language you'd like to write in.
* Output a number.
* I always like to see TIO links.
* Try to solve the problem in the smallest number of bytes.
* The result should be a decimal accurate to at least 4 decimal places (either truncated or rounded up from the test case values is fine) or an exact fraction.

---

Test cases:

# Case 1: Upward trend

```
[
  20,20,20,30,30,30,30,
  35,35,40,40,40,45,45,
  50,50,50,50,50,50,50,
  60,70,80,90,100,110,120
]

```

Normal average: 51.42857142857143 Weighted average: 61.57142857142857

# Case 2: Leaving the lull behind

(I had a bad week, but it was a while ago)

```
[
  50,50,50,50,50,50,50,
  10,10,10,10,10,10,10,
  50,50,50,50,50,50,50,
  50,50,50,50,50,50,50
]

```

Normal average: 40 Weighted average: 42

# Case 3: Giving up

I had a bad week, it's pulling my average down fast.

```
[
  50,50,50,50,50,50,50,
  50,50,50,50,50,50,50,
  50,50,50,50,50,50,50,
  10,10,10,10,10,10,10
]

```

Normal average: 40 Weighted average: 34

# Case 4: Averaging out

Okay, so I'm just playing around here, I thought it might be the same value for the normal and weighted averages, but, of course, it was not.

```
[
  60,60,60,60,60,60,60,
  30,30,30,30,30,30,30,
  20,20,20,20,20,20,20,
  15,15,15,15,15,15,15
]

```

Normal average: 31.25 Weighted average: 24.0

---

## Bonus problem:

What combination of 28 values would have the same normal average and weighted average?

---

Happy golfing!

# Answer
> 3 votes
# Husk, 6 bytes

```
AΣΣṫC7

```

Try it online!

Uses the trick Dennis used to outgolf my Jelly submission. Instead of repeating each chunk **N** times, it retrieves the suffixes of the list of chunks, which after flattening will yield the same result, except for the order.

# Answer
> 10 votes
# Python 3, 38 bytes

```
lambda x:sum(x+x[7:]+x[14:]+x[21:])/70

```

Try it online!

# Answer
> 5 votes
# 05AB1E, ~~8~~ 7 bytes

Saved 1 byte thanks to *Mr. Xcoder*

```
7ô.s˜ÅA

```

Try it online!

**Explanation**

```
7ô         # split list into groups of 7
  .s       # push suffixes
    ˜      # flatten
     ÅA    # arithmetic mean

```

# Answer
> 4 votes
# +pryr, ~~32~~ 28 bytes

and the same average score week over week would result in equality of the means.

```
pryr::f(s%*%rep(1:4,e=7)/70)

```

Try it online!

Saved 4 bytes by using dot product thanks to Giuseppe.

Pure R would have two more bytes using `function`

# Answer
> 4 votes
# Jelly, 7 bytes

```
s7ṫJFÆm

```

Try it online!

### How it works

```
s7ṫJFÆm  Main link. Argument: A (array of length 28)

s7       Split the array into chunks of length 7.
   J     Indices; yield [1, ..., 28].
  ṫ      Tail; yield the 1st, ..., 28th suffix of the result to the left.
         Starting with the 5th, the suffixes are empty arrays.
    F    Flatten the resulting 2D array.
     Æm  Take the arithmetic mean.

```

# Answer
> 4 votes
# MATL, 10 bytes

```
7es4:*s70/

```

Try it online!

I haven't posted a MATL answer in ages! Figured I might participate as part of LOTM May 2018!

Explanation:

```
7e          % Reshape the array into 7 rows (each week is one column)
  s         % Sum each column
   4:       % Push [1 2 3 4]
     *      % Multiply each columnar sum by the corresponding element in [1 2 3 4]
      s     % Sum this array
       70/  % Divide by 70

```

# Answer
> 3 votes
# Jelly, 9 bytes

```
s7x"J$FÆm

```

Try it online!

### How it works

```
s7x"J$FÆm – Takes input from the first command line argument and outputs to STDOUT.
s7        – Split into groups of 7.
   "      – Apply vectorised (zipwith):
  x J$    – Repeat the elements of each list a number of times equal to the list's index.
      F   – Flatten.
       Æm – Arithmetic mean.

```

# Answer
> 2 votes
# JavaScript (Node.js), 49 bytes

```
a=>a.map((x,i)=>(I+=d=-~(i/7),s+=x*d),s=I=0)&&s/I

```

Try it online!

---

Non generics solution

# JavaScript (Node.js), 39 36 bytes

```
a=>a.reduce((s,x,i)=>s+x*-~(i/7))/70

```

Try it online!

# Answer
> 2 votes
# Haskell, 35 bytes

```
(/70).sum.zipWith(*)([1..]<*[1..7])

```

Bonus: if `a,b,c,d` are the weekly sums, normal average is the same as weighted average iff:

```
(a + b + c + d)/4 = (a + 2b + 3c + 4d)/10  <=>
10(a + b + c + d) = 4(a + 2b + 3c + 4d)    <=>
5(a + b + c + d)  = 2(a + 2b + 3c + 4d)    <=>
5a + 5b + 5c + 5d = 2a + 4b + 6c + 8d      <=>
3a + b - c - 3d   = 0

```

One solution is when first and last week have same sums, and likewise second and third weeks have the same sum, but there are infinitely many solutions if your biceps are up to it. Example: \[15,10,10,10,10,10,5,20,20,20,25,25,20,20,30,20,20,20,20,20,20,10,10,20,0,10,10,10\]

Try it online!

# Answer
> 2 votes
# Stax, ~~10~~ 8 bytes

```
äΔ6◙█µøΓ

```

Run and debug it

Explanation (unpacked):

```
7/4R:B$:V Full program, implicit input
7/        Split into parts of length 7
  4R      Push [1, 2, 3, 4]
    :B    Repeat each element the corresponding number of times
      $   Flatten
       :V Average

```

# Answer
> 2 votes
# Stax, 6 bytes

```
ñI"%"╟

```

Run and debug it at staxlang.xyz!

### Unpacked (7 bytes) and explanation:

```
7/|]$:V
7/         Split into groups of seven.
  |]       Suffixes
    $:V    Flatten and average. Implicit print as fraction.

```

# Answer
> 2 votes
# Japt, ~~11~~ 10 bytes

```
xÈ/#F*ÒYz7

```

Try it

---

## Explanation

```
 È             :Pass each element at index Y through a function
  /#F          :  Divide by 70
       Yz7     :  Floor divide Y by 7
      Ò        :  Negate the bitwise NOT of that to add 1
     *         :  Multiply both results
x               :Reduce by addition

```

# Answer
> 2 votes
# Octave, 33 bytes

```
@(x)sum(reshape(x,7,4)*(1:4)')/70

```

Try it online!

# Answer
> 2 votes
# K4 / K (oK), ~~19~~ ~~16~~ 14 bytes

**Solution:**

```
+/(1+&4#7)%70%

```

Try it online!

**Example:**

```
+/(1+&4#7)%70%50 50 50 50 50 50 50 10 10 10 10 10 10 10 50 50 50 50 50 50 50 50 50 50 50 50 50 50
42

```

**Explanation:**

Evaluation is perform right-to-left. Divide 7 1s, 7 2s, 7 3s and 7 4s by 70 divided by the input; then sum up.

```
+/(1+&4#7)%70% / the solution
           70% / 70 divided by the input
  (      )%    / the stuff in brackets divided by this...
      4#7      / draw from 7, 4 times => 7 7 7 7
     &         / 'where' builds 7 0s, 7 1s, 7 2s, 7 3s
   1+          / add one
+/             / sum (+) over (/) to get the total

```

# Answer
> 2 votes
# Charcoal, 14 bytes

```
Ｉ∕ΣＥ⪪Ａ⁷×Σι⊕κ⁷⁰

```

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

```
     Ａ          Input array
    ⪪ ⁷         Split into subarrays of length 7
   Ｅ            Loop over each subarray
         ι      Subarray
        Σ       Sum
           κ    Loop index
          ⊕     Incremented
       ×        Product
  Σ             Sum results
            ⁷⁰  Literal 70
 ∕              Divide
Ｉ               Cast to string
                Implicitly print

```

# Answer
> 2 votes
Excel: 33 bytes

(3 bytes saved from @wernisch's answer by running data on 2 lines from A1:N1 and A2:N2)

```
=AVERAGE(A1:N2,H1:N2,A2:N2,H2:N2)

```

Apologies for not including this as a comment. I don't have enough reputation to do so.

# Answer
> 2 votes
# Arturo, 40 bytes

```
$[a][i:0(sum map a'x[x*1+i/7i:i+1])//70]

```

Try it

# Answer
> 1 votes
# APL+WIN, 13 bytes

Prompts for array as a vector of integers:

```
(+/⎕×7/⍳4)÷70

```

Explanation:

```
7/⍳4) create a vector comprising 7 1s, 7 2s, 7 3s and 7 4s

+/⎕× prompt for input, multiply by the vector above and sum result

(....)÷70 divide the above sum by 70

```

# Answer
> 1 votes
# Triangularity, 49 bytes

```
....)....
...D7)...
..14)21..
.WM)IEtu.
}u)70s/..

```

Try it online!

### Explanation

```
)D7)14)21WM)IEtu}u)70s/ – Full program.
)D7)14)21               – Push the literals 0, 7, 14, 21 onto the stack.
         WM     }       – Wrap the stack to a list and run each element on a separate
                          stack, collecting the results in a list.
           )IEt         – Crop the elements of the input before those indices.
               u        – Sum that list.
                 u      – Then sum the list of sums.
                  )70   – Push the literal 70 onto the stack.
                     s/ – Swap and divide.

```

# Answer
> 1 votes
# Perl 5 `-pa`, 28 bytes

```
$\+=$_/70*int$i++/7+1for@F}{

```

Try it online!

Input is space separated rather than comma separated.

# Answer
> 1 votes
# Java 8, 57 bytes

```
a->{int r=0,i=35;for(;i-->7;)r+=i/7*a[i-7];return r/70d;}

```

Try it online.

**Explanation:**

```
a->{              // Method with integer-array parameter and double return-type
  int r=0,        //  Result-sum, starting at 0
      i=35;       //  Index-integer, starting at 35
  for(;i-->7;)    //  Loop `i` downwards in the range (35,7]
    r+=           //   Add the following to the result-sum:
       i/7        //    `i` integer-divided by 7,
       *a[i-7];   //    multiplied by the item at index `i-7`
  return r/70d;}  //  Return the result-sum, divided by 70.0

```

# Answer
> 1 votes
## Clojure, ~~48~~ 46 bytes

```
#(/(apply +(for[i[0 7 14 21]v(drop i %)]v))70)

```

This ended up being shorter than mapcat + subvec combination.

# Answer
> 1 votes
# , 16 bytes

```
70%~1#.]*7#4{.#\

```

## Explanation:

```
              #\           finds the lengths of all successive prefixes (1 2 3 4 ... 28)
           4{.             takes the first 4 items (1 2 3 4)
         7#                creates 7 copies of each element of the above list
       ]*                  multiplies the input by the above
    1#.                    sum
70%~                       divide by 70

```

Try it online!

# Answer
> 1 votes
# Excel, ~~36~~ 33 bytes

-3 bytes thanks to @tsh.

```
=SUM(1:1,H1:AB1,O1:AB1,V1:AB1)/70

```

Input in first row (`A1` to `AB1`).

# Answer
> 1 votes
# TI-Basic, 25 bytes

```
mean(Ansseq(sum(I>{0,7,21,42}),I,1,70

```

Alternate solution, 39 bytes

```
Input L1
For(I,1,70
Ans+L1(I)sum(I>{0,7,21,42
End
Ans/70

```

# Answer
> 1 votes
# Ruby, 65 bytes

```
->r{(b=(0..r.size/7).map{|a|r[a*7..-1]}.flatten).sum/b.size.to_f}

```

Try it online!

# Answer
> 1 votes
# Julia 0.6, 27 bytes

```
p->repeat(1:4,inner=7)'p/70

```

Try it online!

The `repeat` call forms a column matrix of 28 values, containing seven 1's, then seven 2's, etc. We then transpose it with `'`, then do a matrix multiplication with the input (mutiplication is implicit here). Since it's a matrix multiplication of a 1x28 matrix with a 28x1 matrix, we end up with a single value, which is the weighted sum we need. Divide that by `70` to get our weighted mean.

# Answer
> 1 votes
# Factor \+ `math.unicode`, 36 bytes

```
[ [ 7 /i 1 + * ] map-index Σ 70 / ]

```

Try it online!

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


# Question
Title: Laver table computations and an algorithm that is not known to terminate in ZFC
The Laver tables provide examples of programs which have not been shown to terminate in the standard axiomatic system of mathematics ZFC but which do terminate when one assumes very large cardinal axioms.

**Introduction**

The classical Laver tables `A<sub>n</sub>` are the unique finite algebras with underlying set `{1,...,2<sup>n</sup>}` and an operation `*` that satisfies the identity `x * (y * z)=(x * y) * (x * z)` and where `x*1=x+1` for `x<2<sup>n</sup>` and where `2<sup>n</sup>*1=1`.

More information about the classical Laver tables can be found in the book Braids and Self-Distributivity by Patrick Dehornoy.

**Challenge**

What is the shortest code (in bytes) that calculates `1*32` in the classical Laver tables and terminates precisely when it finds an `n` with `1*32<2<sup>n</sup>`? In other words, the program terminates if and only if it finds an `n` with `1*32<2<sup>n</sup>` but otherwise it runs forever.

**Motivation**

A rank-into-rank cardinal (also called an I3-cardinal) is an extremely large level of infinity and if one assumes the existence of a rank-into-rank cardinal, then one is able to prove more theorems than if one does not assume the existence of a rank-into-rank cardinal. If there exists a rank-into-rank cardinal, then there is some classical Laver table `A<sub>n</sub>` where `1*32<2<sup>n</sup>`. However, there is no known proof that `1*32<2<sup>n</sup>` in ZFC. Furthermore, it is known that the least `n` where `1*32<2<sup>n</sup>` is greater than `Ack(9,Ack(8,Ack(8,254)))`(which is an extremely large number since the Ackermann function `Ack` is a fast growing function). Therefore, any such program will last for an extremely long amount of time.

I want to see how short of a program can be written so that we do not know if the program terminates using the standard axiomatic system ZFC but where we do know that the program eventually terminates in a much stronger axiomatic system, namely ZFC+I3. This question was inspired by Scott Aaronson's recent post in which Aaronson and Adam Yedidia have constructed a Turing machine with under 8000 states such that ZFC cannot prove that the Turing machine does not terminate but is known not to terminate when one assumes large cardinal hypotheses.

**How the classical Laver tables are computed**

When computing Laver tables it is usually convenient to use the fact that in the algebra `A<sub>n</sub>`, we have `2<sup>n</sup> * x=x` for all `x` in `A<sub>n</sub>`.

The following code calculates the classical Laver table `A<sub>n</sub>`

```
# table(n,x,y) returns x*y in A<sub>n</sub>
table:=function(n,x,y)
if x=2^n then return y;
elif y=1 then return x+1;
else return table(n,table(n,x,y-1),x+1); fi; end;

```

For example, the input `table(4,1,2)` will return `12`.

The code for `table(n,x,y)` is rather inefficient and it can only compute in the Laver table `A<sub>4</sub>` in a reasonable amount of time. Fortunately, there are much faster algorithms for computing the classical Laver tables than the ones given above.

# Answer
> 6 votes
**Binary Lambda Calculus, 215 bits (27 bytes)**

```
\io. let
  zero = \f\x. x;
  one = \x. x;
  two = \f\x. f (f x);
  sixteen = (\x. x x x) two;
  pred = \n\f\x. n (\g\h. h (g f)) (\h. x) (\x. x);
  laver = \mx.
    let laver = \b\a. a (\_. mx (b (laver (pred a))) zero) b
    in laver;
  sweet = sixteen;
  dblp1 = \n\f\x. n f (n f (f x)); -- map n to 2*n+1
  go2 = \mx. laver mx sweet mx (\_. mx) (go2 (dblp1 mx));
in go2 one

```

compiles to (using software at https://github.com/tromp/AIT)

```
000101000110100000010101010100011010000000010110000101111110011110010111
110111100000010101111100000011001110111100011000100000101100100010110101
00000011100111010100011001011101100000010111101100101111011001110100010

```

This solution is mostly due to https://github.com/int-e

# Answer
> 4 votes
## CJam (36 32 bytes)

```
1{2*31TW$,(+a{0X$j@(@jj}2j)W$=}g

```

In practice, this errors out quite quickly because it overflows the call stack, but on a theoretical unlimited machine it is correct, and I understand that to be the assumption of this question.

> The code for `table(n,x,y)` is rather inefficient and it can only compute in the Laver table A4 in a reasonable amount of time.

is not actually correct if we cache computed values to avoid recomputing them. That's the approach I've taken, using the `j` (memoisation) operator. It tests A6 in milliseconds and overflows the stack testing A7 \- and I've actually *deoptimised* `table` in the interests of golfing.

### Dissection

If we assume that `n` is understood from the context, instead of

```
f(x,y) =
    x==2^n ? y :
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

```

we can remove the first special case, giving

```
f(x,y) =
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

```

and it still works because

```
f(2^n, 1) = 2^n + 1 = 1

```

and for any other `y`,

```
f(2^n, y) = f(f(2^n, y-1), 1) = f(2^n, y-1) + 1

```

so by induction we get `f(2^n, y) = y`.

For CJam it turns out to be more convenient to reverse the order of the parameters. And rather than using the range `1 .. 2^n` I'm using the range `0 .. 2^n - 1` by decrementing each value, so the recursive function I'm implementing is

```
g(y,x) =
    y==0 ? x+1
         : g(x+1, g(y-1, x))

```

---

```
1           e# Initial value of 2^n
{           e# do-while loop
  2*        e#   Double 2^n (i.e. increment n)
  31T       e#   table(n,1,32) is g(31,0) so push 31 0
  W$,(+a    e#   Set up a lookup table for g(0,x) = x+1 % 2^n
  {         e#   Memoisation function body: stack is 2^n ... y x
    0X$j    e#     Compute g(0,x) = x+1 % 2^n
            e#     Stack is 2^n ... y x (x+1%2^n)
    @(      e#     Bring y to top, decrement (guaranteed not to underflow)
            e#     Stack is 2^n ... x (x+1%2^n) (y-1%2^n)
    @jj     e#     Rotate and apply memoised function twice: g(x+1,g(y-1,x))
  }
  2j        e#   Memoise two-parameter function
            e#   Stack: 2^n g(31,0)
  )W$=      e#   Test whether g(31,0)+1 is 2^n
}g          e# Loop while true

```

# Answer
> 1 votes
# Pyth, 33 bytes

```
.N?qT^2NY?tY:N:NTtYhThT<:T1 32^2T

```

Try it online! (Obviously the testing part is not included here.)

# Answer
> 0 votes
# Javascript, 53 bytes

```
for(M=0;!g(1,31);M-=~M)g=(x,y)=>y?g(g(x,y-1),x):x+1&M

```

Define `g(x,y)=x*(y+1)` on \\$F\_{2^n}\\$, aka. \\$2^n\\$ is written as 0

---
Tags: code-golf, math, set-theory
---


title: Solve Hitori Puzzles

text:
# Question
Title: Solve Hitori Puzzles
# Introduction

Write a solver for the Hitori puzzles using least bytes.

# Challenge

Your task is write a solver for the Hitori (ひとり, the word for "alone" in Japanese; the meaning of the game name is "Leave me alone") logical puzzles. The rules are as follows:

* You are presented with a n-by-n grid of cells, each cell contains an integer between 1 and n (inclusive).
* Your goal is to make sure that no number appear more than once in each row and each column of the grid, by removing numbers from the given grid, subject to the restriction indicated in the next two rules,
* You cannot remove two numbers from two adjacent (horizontally or vertically) cells.
* The remaining numbered cells must be all connected to each other. It means that any two remaining numbered cells can be connected with a curve that is composed solely of segments connecting adjacent remaining numbers (horizonally or vertically). (Thanks to @user202729 for pointing out that this is missing)

I hope the rules are clear by now. If there is anything unclear about the rules, check the Wikipedia page.

# Test Cases

The cells from which the numbers are removed are represented with 0s.

```
Input  ->  Output

4
2 2 2 4      0 2 0 4
1 4 2 3  ->  1 4 2 3
2 3 2 1      2 3 0 1
3 4 1 2      3 0 1 2

4
4 2 4 3      0 2 4 3
4 1 1 2  ->  4 1 0 2
3 1 2 1      3 0 2 1
4 3 1 3      0 3 1 0

5
1 5 3 1 2      1 5 3 0 2
5 4 1 3 4      5 0 1 3 4
3 4 3 1 5  ->  3 4 0 1 5
4 4 2 3 3      4 0 2 0 3
2 1 5 4 4      2 1 5 4 0

8
4 8 1 6 3 2 5 7      0 8 0 6 3 2 0 7
3 6 7 2 1 6 5 4      3 6 7 2 1 0 5 4
2 3 4 8 2 8 6 1      0 3 4 0 2 8 6 1
4 1 6 5 7 7 3 5  ->  4 1 0 5 7 0 3 0
7 2 3 1 8 5 1 2      7 0 3 0 8 5 1 2
3 5 6 7 3 1 8 4      0 5 6 7 0 1 8 0
6 4 2 3 5 4 7 8      6 0 2 3 5 4 7 8
8 7 1 4 2 3 5 6      8 7 1 4 0 3 0 6

9
8 6 5 6 8 1 2 2 9      8 0 5 6 0 1 2 0 9
5 6 2 4 1 7 9 8 3      5 6 2 4 1 7 9 8 3
5 8 2 5 9 9 8 2 6      0 8 0 5 0 9 0 2 0
9 5 6 6 4 3 8 4 1      9 5 6 0 4 3 8 0 1
1 1 6 3 9 9 5 6 2  ->  0 1 0 3 9 0 5 6 2
1 1 4 7 3 8 3 8 6      1 0 4 7 0 8 3 0 6
3 7 4 1 2 6 4 5 5      3 7 0 1 2 6 4 5 0
3 3 1 9 8 7 7 4 5      0 3 1 9 8 0 7 4 5
2 9 7 5 3 5 9 1 3      2 9 7 0 3 5 0 1 0

```

These test cases are taken from Concept Is Puzzles, PuzzleBooks, Concept Is Puzzles, Wikipedia, and Youtube, respectively.

# Specs

* No need to worry about exception handling.
* You **can** assume that the input is always a valid puzzle with a **unique** solution and you can take advantage of this in writing your code.
* This is , the lowest number of bytes wins.
* 4 \<= n \<= 9 (16 originally, changed to 9 following Stewie Griffin's suggestion, also save some trouble in IO)
* You can take input and provide output through any standard form, and you are free to choose the format.
* Some suggestions for the output format are (but you are not restricted to these)

+ Outputting the final grid
    + Outputting the grid containing all removed numbers
    + Output a list of coordinates of one of the above
* As usual, default loopholes apply here.

---

 Related(inspired by this challenge): Check if All Elements In a Matrix Are Connected

 My last challenge: Extension of the Game of Sevens

# Answer
> 6 votes
# Haskell, 374 bytes

```
import Data.Array;import Data.List;r=range;p=partition
c(e,f)=p(\(b,p)->any(==1)[(b-d)^2+(p-q)^2|(d,q)<-e])f
n#g=[s|(o,(e:f))<-[p((==0).(g!))$indices g],
 null.fst$c(o,o),null.snd$until(null.fst)c([e],f),
 s<-case[((l,c),d)|((l,c),h)<-assocs g,h>0,
 d<-[filter((==h).(g!))$r((l,c+1),(l,n))++r((l+1,c),(n,c))],d/=[]]
 of[]->[g];((c,d):_)->n#(g//[(c,0)])++n#(g//[(c,0)|c<-d])]

```

Try it online!

# Answer
> 4 votes
# APL (Dyalog Unicode), 133 bytesSBCS

```
{q←{⊢/4 2⍴⍵}⌺3 3⋄g←⍵=⊂∪,⍵⋄⍵×~1⊃{((⌈/q b)⌈b<{2<≢∪0,,(⍵×⊢⌈⌈/∘q)⍣≡⍵×(⍴⍵)⍴1+⍳≢,⍵}¨~b∘⌈¨⊂⍤2∘.≡⍨⍳⍴b)(+/↑w<g×⌈.⌈⍨w×g)⌈w b←⍵}⍣≡×\(⌈/=∘⌽⍨q⍵)0}

```

Try it online!

My implementation of rule #4 (cells must form a single connected component) is rather wasteful, but still this passes all tests in about 10 seconds on TIO.

---

The overall algorithm: Store two boolean matrices `b` and `w` for cells that are certain to be black and white respectively. Initialise `b` as all-zero. Initialise `w` as 1 only for those cells that have opposite matching neighbours.

Repeat until `b` and `w` settle down:

* add to `b` cells that are on the same line (horizontal or vertical) and of the same value as a cell in `w`
* add to `w` the immediate neighbours of all cells in `b`
* add to `w` all cutpoints - cells whose removal would split the graph of non-black cells into multiple connected components

Finally, output `not(b)` multiplied by the original matrix.

# Answer
> 3 votes
# Jelly, 62 bytes

Uses user202729's isConnected monadic link from another question.

---

```
FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3
ḟ0ĠḊ€
¬T€œ&2\;Ç€FȦ
ZÇȯÇ_1Ŀ
2ḶṗLṗLa⁸ÇÞḢ

```

A full program printing a representation of a list of lists.
Works by brute force and is stupidly inefficient.

**Try it online!** \- a 3 by 3, since it is too inefficient to run even a size 4 within the 60 second TIO limit!

### How?

```
FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3 - Link 1 isConnected? List of lists
...                     - 1 if connected 0 if not -- see linked answer in the header

ḟ0ĠḊ€ - Link 2, helperFor-AnyRepeatedValues: list
ḟ0    - filter out zeros
  Ġ   - group indices by value (i.e. [[indices of min],...,[indices of max]]
   Ḋ€ - dequeue €ach -- leaving a list of empty lists iff no repeated values
      -                 any remaining values are non-zero (1-based indexing in Jelly)

¬T€œ&2\;Ç€FȦ - Link 3, columnwiseAnyAdjacentZerosOrRowwiseAnyRepeatedValues: list of lists
¬            - logical not (convert all zeros to ones and all others to zeros)
 T€          - for €ach row get a list of truthy indexes (i.e. indexes of original zeros)
     2\      - pairwise reduction (i.e. for neighbouring rows) with:
   œ&        -   intersection (empty if no columnwise adjacent original zeros
             -                 any remaining values are non-zero due to 1-based indexing)
        Ç€   - call last link (1) as a monad for €ach row
       ;     - concatenate
          F  - flatten into a single list (empty iff no columnwise adjacent original zeros
             -                                   AND no rowwise repeated values)
           Ȧ - any and all (0 if empty [or contains any zero -- never] else 1)

ZÇȯÇ_1Ŀ - Link 4, validity check? list of lists
Z       - transpose
 Ç      - call last link (2) as a monad rowwiseAnyAdjacentZerosOrColumnwiseAnyRepeatedValues?
   Ç    - call last link (2) as a monad columnwiseAnyAdjacentZerosOrRowwiseAnyRepeatedValues?
  ȯ     - logical OR
     1Ŀ - call link 1 as a monad (isConnected?)
    _   - subtract
        - this yields -1 for valid, while it yields 0 or 1 if not.

2ḶṗLṗLa⁸ÇÞḢ - Main link: list of lists
2Ḷ          - lowered range of 2 -> [0,1]
   L        - length (number of rows in the input)
  ṗ         - Cartesian power (all lists of zeros and ones of length L)
     L      - length (number of rows in the input again)
    ṗ       - Cartesian power (all grids of zeros and ones of same shape as the input)
       ⁸    - the input
      a     - logical AND -- effectively uses each of the formed grids as a mask
         Þ  - sort by:
        Ç   -   last link (3) as a monad
          Ḣ - head
            - implicit print

```

# Answer
> 1 votes
# Python3, 567 bytes:

```
E=enumerate
M=[(0,1),(0,-1),(1,0),(-1,0)]
V=lambda b:[(x,r,y,v)for x,r in E(b)for y,v in E(r)]
J=list.count
def C(b,x,y,s):
 b=eval(str(b));b[x][y]=0
 if b in s:return
 t=[(x,y)for x,_,y,v in V(b)if v]
 q=[t.pop()]
 while q:
  x,y=q.pop(0)
  for X,Y in M:
   if(N:=(x+X,y+Y))in t:q+=[N];t.remove(N)
 if[]==t:return b
def f(b):
 q,s=[b],[]
 while q:
  b=q.pop(0)
  F=1
  for x,r,y,v in V(b):
   if v and(J(r,v)>1 or J([*[*zip(*b)][y]],v)>1):
    F=0
    if all(b[x+X][y+Y]for X,Y in M if 0<=x+X<len(b)and 0<=y+Y<len(r))and(B:=C(b,x,y,s)):q+=[B];s+=[B]
  if F:return b

```

Try it online!

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