title: Implement Strassen's algorithm

text:
# Question
Title: Implement Strassen's algorithm
Strassen's algorithm was the first method of matrix multiplication in subcubic time complexity, namely `O(n**log2(7))` for a pair of `n*n` matrices (assuming the numbers therein are large enough that their `O(n*log2(n))` exact multiplication has become the constraint on your performance, and any nested structures and function calls are negligible in comparison).

For a `2*2` matrix, it is defined as

```
lambda a,b: (lambda a,b,c,d,e,f,g: (a+d-e+g,c+e,b+d,a-b+c+f))((a[0]+a[3])*(b[0]+b[3]),(a[2]+a[3])*b[0],a[0]*(b[1]-b[3]),a[3]*(b[2]-b[0]),(a[0]+a[1])*b[3],(a[2]-a[0])*(b[0]+b[1]),(a[1]-a[3])*(b[2]+b[3]))

```

And for larger square ones, as splitting them into quarters and then calling this but with numbers' addition, negation and multiplication methods substituted for matrices' (notably using itself for the latter, its seven self-calls per doubling of the width and height being the reason for the exponent).

For simplicity (so you won't need to deal with implementing standard matrix multiplication and subdividing into Strassen-able ones), your inputs will be two `2**n*2**n` matrices of integers, represented as length-`2**(2*n)` tuples (or lists or your language's equivalent), encoded with elements in reading order, and you will return another such tuple. For instance, when inputted with these two

```
(5,2,0,0,
 4,0,5,2,
 3,4,5,0,
 3,1,4,2)

(7,4,5,3,
 4,0,2,7,
 1,4,1,1,
 0,5,3,5)

```

, it should return

```
(43,20,29,29,
 33,46,31,27,
 42,32,28,42,
 29,38,27,30)

```

# Answer
> 0 votes
# One-line Python (1027 bytes)

(explained in this gist, would be greatly reducible if you were to be less pedantic about it all being one line)

```
from functools import reduce
from math import isqrt
from random import random
lap=(lambda f,*a: list(map(f,*a)))
strassen=(lambda a,b: tuple((lambda f: f(a,b) if len(a)==4 else (lambda m: (lambda m,d: ((m[y*2+x][d*j+i] for y in range(2) for j in range(d) for x in range(2) for i in range(d))))(m,isqrt(len(m[0]))))(f(*(map((lambda m: (lambda m,d: tuple((tuple((m[i*d+j] for i in range(d//2*y,d//(2-y)) for j in range(d//2*x,d//(2-x)))) for y in range(2) for x in range(2))))(m,isqrt(len(m)))),(a,b))))))((lambda a,b: (lambda s,n,o,m: (lambda a,b,c,d,e,f,g: lap(s,((a,d,n(e),g),(c,e),(b,d),(a,n(b),c,f))))(*map(m,*map(lambda x: map(o,x),(((a[0],a[3]),(a[2],a[3]),(a[0],),(a[3],),(a[0],a[1]),(a[2],n(a[0])),(a[1],n(a[3]))),((b[0],b[3]),(b[0],),(b[1],n(b[3])),(b[2],n(b[0])),(b[3],),(b[0],b[1]),(b[2],b[3])))))))(*((sum,int.__neg__,sum,int.__mul__) if type(a[0])==int else ((lambda x: reduce(lambda a,b: lap(int.__add__,a,b),x)),(lambda x: map(int.__neg__,x)),(lambda t: t[0] if len(t)==1 else lap(int.__add__,*t)),strassen)))))))

```

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


title: Make all the squares explode

text:
# Question
Title: Make all the squares explode
You are given a square matrix of width \\$\ge2\\$, containing square numbers \\$\ge1\\$.

Your task is to make all square numbers 'explode' until all of them have disappeared. You must print or return the final matrix.

More specifically:

1. Look for the highest square \\$x^2\\$ in the matrix.
2. Look for its smallest adjacent neighbor \\$n\\$ (either horizontally or vertically and without wrapping around).
3. Replace \\$x^2\\$ with \\$x\\$ and replace \\$n\\$ with \\$n\times x\\$.

Repeat the process from step 1 until there's no square anymore in the matrix.

### Example

Input matrix:

$$\begin{pmatrix} 625 & 36\\ 196 & 324 \end{pmatrix}$$

The highest square \\$625\\$ explodes into two parts of \\$\sqrt{625}=25\\$ and merges with its smallest neighbor \\$36\\$, which becomes \\$36\times 25=900\\$:

$$\begin{pmatrix} 25 & 900\\ 196 & 324 \end{pmatrix}$$

The highest square \\$900\\$ explodes and merges with its smallest neighbor \\$25\\$:

$$\begin{pmatrix} 750 & 30\\ 196 & 324 \end{pmatrix}$$

The highest square \\$324\\$ explodes and merges with its smallest neighbor \\$30\\$:

$$\begin{pmatrix} 750 & 540\\ 196 & 18 \end{pmatrix}$$

The only remaining square \\$196\\$ explodes and merges with its smallest neighbor \\$18\\$:

$$\begin{pmatrix} 750 & 540\\ 14 & 252 \end{pmatrix}$$

There's no square anymore, so we're done.

### Rules

* The input matrix is **guaranteed** to have the following properties:
    + at each step, the highest square will always be unique
    + at each step, the smallest neighbor of the highest square will always be unique
    + the sequence will not repeat forever
* The initial matrix may contain \\$1\\$'s, but you do not have to worry about making \\$1\\$ explode, as it will never be the highest or the only remaining square.
* I/O can be processed in any reasonable format
* This is

### Test cases

```
Input : [[16,9],[4,25]]
Output: [[24,6],[20,5]]

Input : [[9,4],[1,25]]
Output: [[3,12],[5,5]]

Input : [[625,36],[196,324]]
Output: [[750,540],[14,252]]

Input : [[1,9,49],[1,4,1],[36,25,1]]
Output: [[3,6,7],[6,2,7],[6,5,5]]

Input : [[81,4,64],[16,361,64],[169,289,400]]
Output: [[3,5472,8],[624,323,1280],[13,17,20]]

Input : [[36,100,1],[49,144,256],[25,49,81]]
Output: [[6,80,2],[42,120,192],[175,21,189]]

Input : [[256,169,9,225],[36,121,144,81],[9,121,9,36],[400,361,100,9]]
Output: [[384,13,135,15],[24,1573,108,54],[180,11,108,6],[380,209,10,90]]

Input : [[9,361,784,144,484],[121,441,625,49,25],[256,100,36,81,529],[49,4,64,324,16],[25,1,841,196,9]]
Output: [[171,19,700,4032,22],[11,210,525,7,550],[176,60,6,63,23],[140,112,1152,162,368],[5,29,29,14,126]]

```

# Answer
# , ~~301~~ ~~287~~ ~~277~~ ~~274~~ ~~222~~ ~~217~~ ~~195~~ ~~186~~ ~~178~~ 174 bytes

Nothing particularly creative, including the zero buffering of the peripheral elements of the entry matrix, an earlier version later improved by Robin:

```
function(x){w=which.max
if(any(s<-!x^.5%%1)){
y=cbind(NA,rbind(NA,x,NA),NA)
z=y[i]=y[i<-w(y*y%in%x[s])]^.5
m=i+c(r<--c(1,nrow(y)),-r)
y[j]=y[j<-m[w(-y[m])]]*z
x=p(y[r,r])}
x}

```

Try it on-line

Using a sequence of numbers as its entry, and hence removing the call to a function, Nick Kennedy earlier managed a 186 bytes version of the algorithm as follows (with -10 bytes by Robin):

```
w=which.max;`~`=cbind;x=scan();while(any(s<-!x^.5%%1)){y=NA~t(NA~matrix(x,n<-length(x)^.5)~NA)~NA;i=w(y*y%in%x[s]);=i+c(r<--c(1,n+2),-r);y[j]=y[j<-m[w(-y[m])]]*(y[i]=y[i]^.5);x=y[r,r]};x

```

avoiding the definition of a (recursive) function, plus other nice gains.

Try it on-line
> 5 votes

# Answer
# Ruby, ~~140~~ 135 bytes

Takes a flat list as input, outputs a flat list.

```
->m{i=1;(i=m.index m.reject{|e|e**0.5%1>0}.max
m[i+[1,-1,l=m.size**0.5,-l].min_by{|j|i+j>=0&&m[i+j]||m.max}]*=m[i]**=0.5if i)while i;m}

```

Try it online!

Explanation:

```
->m{                                # Anonymous lambda
    i=1;                            # Initialize i for the while loop
        (                           # Start while loop

i=m.index                           # Get index at...
    m.reject{|e|          }         # Get all elements of m, except the ones with...
                e**0.5%1>0          # a square root with a fractional component
                           .max     # Get the largest of these

m[i+                                # Get item at...
    [1,-1,l=m.size**0.5,-l]         # Get possible neighbors (up, down, left, right)
        .min_by{|j|i+j>=0&&m[i+j]|| # Find the one with the minimum value at neighbor
                            m.max}  # If out of range, return matrix max so
                                    #   neighbor isn't chosen
    ]
    *=m[i]**=0.5                    # Max square becomes its square root, then multiply
                                    #   min neighbor by it

)while i                            # End while loop. Terminate when index is nil.
m}                                  # Return matrix.

```
> 2 votes

# Answer
# MATL, ~~49~~ 48 bytes

```
`ttX^tt1\~*X>X>XJt?wy=(tt5M1Y6Z+*tXzX<=*Jq*+w}**

```

Try it online! Or verify all test cases.

### How it works

```
`           % Do...while
  tt        %   Duplicate twice. Takes a matrix as input (implicit) the first time
  X^        %   Square root of each matrix entry
  tt        %   Duplicate twice
  1\~       %   Modulo 1, negate. Gives true for integer numbers, false otherwise
  *         %   Multiply, element-wise. This changes non-integers into zero
  X>X>      %   Maximum of matrix. Gives maximum integer square root, or zero
  XJ        %   Copy into clipboard J
  t         %   Duplicate
  ?         %   If non-zero
    wy      %     Swap, duplicate from below. Moves the true-false matrix to top
    =       %     Equals, element-wise. This gives a matrix which is true at the
            %     position of the maximum that was previously identified, and
            %     false otherwise
    (       %     Write the largest integer square root into that position
    tt      %     Duplicate twice
    5M      %     Push again the matrix which is true for the position of maximum
    1Y6     %     Push matrix [0 1 0; 1 0 1; 0 1 0] (von Neumann neighbourhood)
    Z+      %     2D convolution, keeping size. Gives a matrix which is 1 for the
            %     neighbours of the value that was replaced by its square root
    *       %     Multiply. This replaces the value 1 by the actual values of
            %     the neighbours
    t       %     Duplicate
    XzX<    %     Minimum of non-zero entries
    =       %     Equals, element-wise. This gives a matrix which is true at the
            %     position of the maximum neighbour, and zero otherwise
    *       %     Multiply, element-wise. This gives a matrix which contains the
            %     maximum neighbour, and has all other entries equal to zero
    J       %     Push the maximum integer root, which was previously stored
    q       %     Subtract 1
    *       %     Multiply element-wise. This gives a matrix which contains the
            %     maximum neighbour times (maximum integer root minus 1)
    +       %     Add. This replaces the maximum neighbour by the desired value,
            %     that is, the previously found maximum integer square root
            %     times the neighbour value
    w       %     Swap
  }         %   Else. This means there was no integer square root, so no more
            %   iterations are neeeded
  **        %   Multiply element-wise twice. Right before this the top of the
            %   stack contains a zero. Below there are the latest matrix with
            %   square roots and two copies of the latest matrix of integers,
            %   one of which needs to be displayed as final result. The two
            %   multiplications leave the stack containing a matrix of zeros
            %   and the final result below
            % End (implicit). The top of the stack is consumed. It may be a
            % positive number, which is truthy, or a matrix of zeros, which is
            % falsy. If truthy a new iteration is run. If falsy the loop exits
            % Display (implicit)

```
> 2 votes

# Answer
# Perl 6, 236 bytes

```
{my@k=.flat;my \n=$_;loop {my (\i,\j)=@k>>.sqrt.grep({$_+|0==$_},:kv).rotor(2).max(*[1]);last if 0>i;$/=((0,1),(0,-1),(1,0),(-1,0)).map({$!=i+n*.[0]+.[1];+$!,n>.[0]+i/n&.[1]+i%n>=0??@k[$!]!!Inf}).min(*[1]);@k[i,$0]=j,j*$1};@k.rotor(+n)}

```

Try it online!
> 2 votes

# Answer
# Python 2, 188 bytes

```
M=input()
l=int(len(M)**.5)
try:
 while 1:m=M.index(max(i**.5%1or i for i in M));_,n=min((M[m+i],m+i)for i in m/l*[-l]+-~m%l*[1]+[l][:m/l<l-1]+m%l*[-1]);M[m]**=.5;M[n]*=M[m]
except:print M

```

Try it online!

Full program. Takes input and prints as a flat list.
> 2 votes

# Answer
# JavaScript (ES6), ~~271~~ ~~259~~ ~~250~~ 245 bytes

```
m=>{for(l=m.length;I=J=Q=-1;){for(i=0;i<l;i++)for(j=0;j<l;j++)!((q=m[i][j]**.5)%1)&&q>Q&&(I=i,J=j,Q=q);if(I<0)break;d=[[I-1,J],[I+1,J],[I,J-1],[I,J+1]];D=d.map(([x,y])=>(m[x]||0)[y]||1/0);[x,y]=d[D.indexOf(Math.min(...D))];m[x][y]*=Q;m[I][J]=Q}}

```

Thanks to Luis felipe De jesus Munoz for −14 bytes!

Explanation:

```
m => { // m = input matrix
  // l = side length of square matrix
  // I, J = i, j of largest square in matrix (initialized to -1 every iteration)
  // Q = square root of largest square in matrix
  for (l = m.length; (I = J = Q = -1); ) {
    // for each row,
    for (i = 0; i < l; i++)
      // for each column,
      for (j = 0; j < l; j++)
        // if sqrt of m[i][j] (assigned to q) has no decimal part,
        // (i.e. if m[i][j] is a perfect square and q is its square root,)
        !((q = m[i][j] ** 0.5) % 1) &&
          // and if this q is greater than any previously seen q this iteration,
          q > Q &&
          // assign this element to be the largest square in matrix.
          ((I = i), (J = j), (Q = q));
    // if we did not find a largest square in matrix, break loop.
    if (I < 0) break;
    // d = [i, j] pairs for each neighbor of largest square in matrix
    d = [[I - 1, J], [I + 1, J], [I, J - 1], [I, J + 1]];
    // D = value for each neighbor in d, or Infinity if value does not exist
    D = d.map(([x, y]) => (m[x] || 0)[y] || 1 / 0);
    // x = i, y = j of smallest adjacent neighbor of largest square
    [x, y] = d[D.indexOf(Math.min(...D))];
    // multiply smallest adjacent neighbor by square root of largest square
    m[x][y] *= Q;
    // set largest square to its square root
    m[I][J] = Q;
  } // repeat until no remaining squares in matrix
  // no return necessary; input matrix is modified.
};

```
> 1 votes

# Answer
# Jelly, ~~70~~ 67 bytes

```
’dL½$}©+Ø.,U$;N$¤%®‘¤<®Ạ$Ƈæ.®‘ịÐṂḢ;ḷ;€ị½¥×÷ƭ⁹Ḣ¤¦Ṫ}¥ƒ
×Æ²$MḢçɗ⁸Ẹ?ƊÐL

```

Try it online!

I’m sure this can be done much more briefly, but I found this harder than it first appeared. Explanation to follow once I’ve tried to golf it better.

A full program that takes a list of integers corresponding to the square matrix and returns a list of integers representing the final exploded matrix.l
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 220 bytes

```
n=>l=>{for(int g;n.Any(x=>Math.Sqrt(x)%1==0);n[n.Select((a,b)=>(x:Math.Abs(b/l-g/l)+Math.Abs(b%l-g%l)==1?a:1<<30,y:b)).OrderBy(x=>x).First().y]*=n[g])n[g=n.IndexOf(n.Max(x=>Math.Sqrt(x)%1==0?x:0))]=(int)Math.Sqrt(n[g]);}

```

Try it online!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 224 bytes

```
(l=#;While[(c=Length)[m=Select[Join@@l,IntegerQ[Sqrt@#]&]]>0,t=##&@@#&@@SortBy[Select[(g=#&@@Position[l,f=Max@m])+#&/@{{1,0},{0,1},{-1,0},{0,-1}},Min@#>0&&Max@#<=c@l&],l[[##]]&@@#&];l[[##&@@g]]=(n=Sqrt@f);l[[t]]=l[[t]]n];l)&

```

Try it online!
> 1 votes

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

```
a=>g=(l,m=n=i=j=0)=>a.map((o,k)=>m>o||o**.5%1||[m=o,i=k])|m&&a.map((o,k)=>n*n<o*n|((i/l|0)-(k/l|0))**2+(i%l-k%l)**2-1||[n=o,j=k])|[a[i]=m**=.5,a[j]=m*n]|g(l)

```

Try it online!

-14 bytes thanks the @Arnauld who also wrote a nice test harness :)

Anonymous function that takes a 1-dimensional array as input and a length parameter specifying number if columns/rows.

Curried input is specified as `f(array)(length)`.

```
// a: 1-dimensional array of values
// g: recursive function that explodes once per recursive call
// l: number of columns, user specified
// m: max square value
// n: min neighbor
// i: index of max square
// j: index of min neighbor
a=>g=(l,m=n=i=j=0)=>
  // use .map() to iterate and find largest square
  a.map((o,k)=>
    // check size of element
    m>o||
    // check if element is a square
    o**.5%1||
    // new max square found, update local variables
    [m=o,i=k])|
  // after first .map() is complete, continue iff a square is found
  // run .map() again to find smallest neighbor
  m&&a.map((o,k)=>
    // check size of element
    n*n<o*n|
    // check relative position of element
    ((i/l|0)-(k/l|0))**2+(i%l-k%l)**2-1||
    // a new smallest neighbor found, update local variables
    [n=o,j=k])|
  // update matrix in-place, largest square is reduced,
  // smallest neighbor is increased
  [a[i]=m**=.5,a[j]=m*n]|
  // make recursive call to explode again
  g(l)

```
> 1 votes

# Answer
# Java 8, ~~299~~ ~~297~~ ~~289~~ 279 bytes

```
m->{for(int l=m.length,i,j,I,J,d,M,t,x,y;;m[x][y]*=d){for(i=l*l,I=J=d=0;i-->0;)d=Math.sqrt(t=m[i/l][i%l])%1==0&t>d*d?(int)Math.sqrt(m[I=i/l][J=i%l]):d;if(d<1)break;for(M=-1>>>1,m[x=I][y=J]=d,t=4;t-->0;)try{M=m[i=I+t/2-t/3*2][j=t<1?J-1:1/t+J]<M?m[x=i][y=j]:M;}finally{continue;}}}

```

-18 bytes thanks to *@ceilingcat*.

Modifies the input-matrix instead of returning a new one to save bytes.

Try it online.

**Explanation:**

```
m->{                          // Method with integer-matrix input and no return-type
  for(int l=m.length,         //  Dimension-length `l` of the matrix
      i,j,I,J,d,M,t,x,y;      //  Temp integers
      ;                       //  Loop indefinitely:
       m[x][y]*=d){           //    After every iteration: multiply `x,y`'s value with `d`
    for(I=J=d=0,              //   (Re)set `I`, `J`, and `d` all to 0
        i=l*l;i-->0;)         //   Loop over all the cells:
      d=                      //    Set `d` to:
        Math.sqrt(t=m[i/l][i%l])%1==0?
                              //     If the current value is a perfect square
        *t>d*d?               //     And if it's larger than `d` squared:
          (int)Math.sqrt(m[I=i/l][J=i%l])
                              //      Set `I,J` to the current coordinate
                              //      And `d` to the square-root of the current value
        :d;                   //     Else: leave `d` the same
    if(d<1)                   //   If `d` is still 0 after the nested loop
                              //   (which means there are no more square-numbers)
      break;                  //    Stop the infinite loop
    for(M=-1>>>1,             //   (Re)set `M` to Integer.MAX_VALUE
        m[x=I][y=J]=d,        //   Replace the value at `I,J` with `d`
        t=4;t-->0;)           //   Loop `t` in the range (4, 0]:
      try{M=                  //    Set `M` to:
            m[i=I+t/2-t/3*2]  //     If `t` is 3:
                              //      Go to the row above
                              //     Else-if `t` is 2:
                              //      Go to the row below
                              //     Else (`t` is 0 or 1):
                              //      Stay in the current row
                              //     (and save this row in `i`)
             [j=t<1?J-1:1/t+J]//     If `t` is 0:
                              //      Go to the column left
                              //     Else-if `t` is 1:
                              //      Go to the column right
                              //     Else (`t` is 2 or 3):
                              //      Stay in the current column
                              //     (and save this column in `j`)
             <M?              //     And if the value in this cell is smaller than `M`:
                m[x=i][y=j]   //      Set `x,y` to `i,j`
                              //      And `M` to the current value in `i,j`
               :M;            //     Else: leave `M` the same
      }finally{continue;}}}   //    Catch and ignore IndexOutOfBoundsExceptions

```
> 1 votes

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

```
f=(a,I,J,r)=>a.map((x,i)=>x.map((y,j)=>(1+J?(i-I)**2+(j-J)**2-1|r<y:y**.5%1||r>y)||(P=i,Q=j,r=y)))|1+J?f(a,a[P][Q]*=a[I][J]**=.5):r&&f(a,P,Q)

```

Try it online!

Take input 2D array
> 1 votes

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


title: Clutch Wordle solver with known inputs

text:
# Question
Title: Clutch Wordle solver with known inputs
Sometimes when you're playing Wordle, you get to your fifth guess and you can't figure out the word any more, so you start mentally running through the list of remaining iterations, both sensical and nonsensical trying to figure out what those last few letters are.

The task here is to create all permutations of a final Wordle guess to save me from having to do it in my head, with the following rules:

### General rules:

* Wordle rules apply (similar to codebreaker game).
    + Guess an unknown five-letter word.
    + Guesses will return an indication of whether the letter is in the word such that:
        - If a letter is in the correct position, it will be green
        - If a letter appears in the word but is not in the correct position, it will be yellow
        - If a letter does not appear in the word, it will be black.
        - Letters can appear more than once in the solution (provided the solution is still a valid word)
        - If a letter is guessed twice in the same guess (such as "guess") but is in the correct word fewer times than guessed, only the number of the repeated letters will be green or yellow. If the position is correct for one of the placements, that will appear green, regardless of the position in the sequence. If the positions are all wrong, the earliest occurence/s will be marked yellow and the following one/s black.
* Inputs should be solvable, even if no solutions are "real" words.
* Since Wordle only uses valid English words, only letters that appear on a standard English keyboard (a-z) need to be tested. **However, you should include all valid permutations, not just valid English words, in your output**.
* Solution is case insensitive.

### Input:

* A list of letters and indices (0 or 1 indexed, your choice), indicating the location of confirmed/green letters - **indicate the index you chose**;
* A list of letters and indices (consistently indexed), indicating yellow letters (i.e. the letter is known to not be at that index);
* A list/string of letters that are yet to be guessed.

Note, **green and yellow letters may still appear in more than the known positions**. For example, if the input for green is `[('E', 1)]`, there may still be an `E` in an index other than `1` as well.

### Output:

All potential "words" of exactly 5 letters, such that the green letters are in the indicated indexes, the yellow letters are not in the indicated indexes (but must appear at least once in the output), and the words consist of only the green, yellow, and remaining letters. The output may be in any order.

What's the shortest way to solve this problem? You may take input and output in any convenient method or format, and the shortest code in bytes wins.

---

### Example:

1. **Green Guesses** (1 indexed): O=2, E=4, N=5
2. **Yellow Guesses**: N!=3 (E!=5 is excluded because we know N=5)
3. **Unguessed Letters**: Q, W, I, P, F, J, K, X, B

All other letters (A, C, D, F, G, H, L, M, R, S, T, U, V, Y, Z) have been guessed and cannot occur in the result.

Output would be a list of all possible permutations given the known information, such as:

```
["BOBEN", "BOEEN", "BOFEN", "BOIEN", "BOJEN", "BOKEN", "BOOEN", "BOPEN", "BOQEN", "BOWEN", "BOXEN", "EOBEN", "EOEEN", "EOFEN", "EOIEN", "EOJEN", "EOKEN", "EOOEN", "EOPEN", "EOQEN", "EOWEN", "EOXEN", "FOBEN", "FOEEN", "FOFEN", "FOIEN", "FOJEN", "FOKEN", "FOOEN", "FOPEN", "FOQEN", "FOWEN", "FOXEN", "IOBEN", "IOEEN", "IOFEN", "IOIEN", "IOJEN", "IOKEN", "IOOEN", "IOPEN", "IOQEN", "IOWEN", "IOXEN", "JOBEN", "JOEEN", "JOFEN", "JOIEN", "JOJEN", "JOKEN", "JOOEN", "JOPEN", "JOQEN", "JOWEN", "JOXEN", "KOBEN", "KOEEN", "KOFEN", "KOIEN", "KOJEN", "KOKEN", "KOOEN", "KOPEN", "KOQEN", "KOWEN", "KOXEN", "NOBEN", "NOEEN", "NOFEN", "NOIEN", "NOJEN", "NOKEN", "NOOEN", "NOPEN", "NOQEN", "NOWEN", "NOXEN", "OOBEN", "OOEEN", "OOFEN", "OOIEN", "OOJEN", "OOKEN", "OOOEN", "OOPEN", "OOQEN", "OOWEN", "OOXEN", "POBEN", "POEEN", "POFEN", "POIEN", "POJEN", "POKEN", "POOEN", "POPEN", "POQEN", "POWEN", "POXEN", "QOBEN", "QOEEN", "QOFEN", "QOIEN", "QOJEN", "QOKEN", "QOOEN", "QOPEN", "QOQEN", "QOWEN", "QOXEN", "WOBEN", "WOEEN", "WOFEN", "WOIEN", "WOJEN", "WOKEN", "WOOEN", "WOPEN", "WOQEN", "WOWEN", "WOXEN", "XOBEN", "XOEEN", "XOFEN", "XOIEN", "XOJEN", "XOKEN", "XOOEN", "XOPEN", "XOQEN", "XOWEN", "XOXEN"]

```

Output may be in any order.

In this case:

* There are 12 possibilities for the first letter (any of "BEFIJKNOPQWX")
* There is 1 possibility for the second letter ("O")
* There are 11 possibilities for the third letter (any of "BEFIJKOPQWX", excluding N)
* There is 1 possibility for the fourth letter ("E")
* There is 1 possibility for the fifth letter ("N")

So the result should contain a total of 12 * 1 * 11 * 1 * 1 = 132 items.

In code terms, the inputs may be given as:

* `[['O', 2], ['E', 4], ['N', 5]]` or `[["O", "E", "N"], [2, 4, 5]]` or similar
* `[['N', 3]]` or `[["N"], [3]]` or similar
* `"QWIPFJKXB"` or `["Q","W","I","P","F","J","K","X","B"]` or similar

and the output as:

```
['BOBEN', 'EOBEN', 'FOBEN', 'IOBEN', 'JOBEN', 'KOBEN', 'NOBEN', 'OOBEN', 'POBEN', 'QOBEN', 'WOBEN', 'XOBEN', 'BOEEN', 'EOEEN', 'FOEEN', 'IOEEN', 'JOEEN', 'KOEEN', 'NOEEN', 'OOEEN', 'POEEN', 'QOEEN', 'WOEEN', 'XOEEN', 'BOFEN', 'EOFEN', 'FOFEN', 'IOFEN', 'JOFEN', 'KOFEN', 'NOFEN', 'OOFEN', 'POFEN', 'QOFEN', 'WOFEN', 'XOFEN', 'BOIEN', 'EOIEN', 'FOIEN', 'IOIEN', 'JOIEN', 'KOIEN', 'NOIEN', 'OOIEN', 'POIEN', 'QOIEN', 'WOIEN', 'XOIEN', 'BOJEN', 'EOJEN', 'FOJEN', 'IOJEN', 'JOJEN', 'KOJEN', 'NOJEN', 'OOJEN', 'POJEN', 'QOJEN', 'WOJEN', 'XOJEN', 'BOKEN', 'EOKEN', 'FOKEN', 'IOKEN', 'JOKEN', 'KOKEN', 'NOKEN', 'OOKEN', 'POKEN', 'QOKEN', 'WOKEN', 'XOKEN', 'BOOEN', 'EOOEN', 'FOOEN', 'IOOEN', 'JOOEN', 'KOOEN', 'NOOEN', 'OOOEN', 'POOEN', 'QOOEN', 'WOOEN', 'XOOEN', 'BOPEN', 'EOPEN', 'FOPEN', 'IOPEN', 'JOPEN', 'KOPEN', 'NOPEN', 'OOPEN', 'POPEN', 'QOPEN', 'WOPEN', 'XOPEN', 'BOQEN', 'EOQEN', 'FOQEN', 'IOQEN', 'JOQEN', 'KOQEN', 'NOQEN', 'OOQEN', 'POQEN', 'QOQEN', 'WOQEN', 'XOQEN', 'BOWEN', 'EOWEN', 'FOWEN', 'IOWEN', 'JOWEN', 'KOWEN', 'NOWEN', 'OOWEN', 'POWEN', 'QOWEN', 'WOWEN', 'XOWEN', 'BOXEN', 'EOXEN', 'FOXEN', 'IOXEN', 'JOXEN', 'KOXEN', 'NOXEN', 'OOXEN', 'POXEN', 'QOXEN', 'WOXEN', 'XOXEN']

```

# Answer
# Charcoal, 55 bytes

```
ＵＭθ∨ι⁻⪪α¹⁺⪪§ηκ¹⁻⪪α¹⁺θ⪪⁺ζΣη¹ΦＥΠＥθＬι⭆θ§λ÷ιΠ∨Ｅ…θμＬν¹⬤Ση№ιλ

```

Try it online! Link is to verbose version of code. Takes input in the `["", "O", "", "E", "N"]`, `["", "", "N", "", ""]`, `"QWIPFJKXB"` formats, i.e. multiple letters unguessed or in a given yellow position should be concatenated into a string rather than being a subarray. Explanation:

```
ＵＭθ∨ι⁻⪪α¹⁺⪪§ηκ¹⁻⪪α¹⁺θ⪪⁺ζΣη¹

```

Fill in the gaps in the green guesses by taking the set union of all of the input and subtracting the yellow guesses for that position. (Charcoal doesn't actually do set union so I have to fake it by set difference with the whole alphabet twice.)

```
ＥΠＥθＬι⭆θ§λ÷ιΠ∨Ｅ…θμＬν¹⬤Ση№ιλ

```

Calculate the number of potential words and map each to a string by mixed base conversion using the lists of possible letters (which again Charcoal has to emulate, although at least it has cyclic indexing to help). Ensure those words contain at least one of all of the yellow guesses.

50 bytes using the newer version of Charcoal on ATO that can take the product of an empty list and flatten a list of lists:

```
ＵＭθ∨ι⁻⪪α¹⁺§ηκ⁻⪪α¹⁺Σθ⁺ζΣηΦＥΠＥθＬι⭆θ§λ÷ιΠＥ…θμＬν⬤Ση№ιλ

```

Attempt This Online! Link is to verbose version of code. Takes input in the `["", "O", "", "E", "N"]`, `[[], [], ["N"], [], []]`, `["Q", "W", "I", "P", "F", "J", "K", "X", "B"]` formats, i.e. letters unguessed or in a given yellow position need to be a subarray (both formats work for the green letters).
> 3 votes

# Answer
# Python 3, ~~198 176 205 166 152~~ 138 bytes

```
lambda g,y,u:{m for m in product(*[x or u+''.join(g+[a for a,b in y])for x in g])if all(m[q]!=p in m for p,q in y)}
from itertools import*

```

### Try it online!

* -22, -39, -14 thanks to Steffan
* Thanks to Kamil Drakari for pointing out some bugs in the code

So, it didn't work before. I've now fixed it (I think).

Other test cases here, here and here.

# Python 3 \+ `golfing-shortcuts`, ~~131~~ 121 bytes

```
lambda G,Y,U:{M for M in Ip(*[X or U+sj('',G+[A for A,B in Y])for X in G])if j(M[Q]!=P in M for P,Q in Y)}
from s import*

```
* -10 thanks to Steffan

---

**Input:**

* `g`: The green letters, as a list, e.g. `['', 'O', '', 'E', 'N']`
* `y`: The yellow letters, in tuples with their positions, e.g. `[('N', 2)]`
* `u`: The unguessed letters, as a string: e.g. `'QWIPFJKXB'`

**Output:**

As letter tuples, e.g. `('Q', 'O', 'Q', 'E', 'N')`
> 3 votes

# Answer
# Japt, 38 bytes

```
5ÆgX ªNc kVgX)fÃrÈï[Y]c '+Ãf@Vc e!øXÃâ

```

Try the original test case, or check that it's right

Try my proposed test case

Try another case demonstrating multiple yellow letters in the same position

Try a fourth test case with a yellow letter in the same position as a green letter

Input format in order:

* Green letters as an array with `""` for unkown, e.g. `["", "O", "", "E", "N"]`
* Yellow letters as an array of arrays of letters for each position, e.g. `[[], [], ["N"], [], []]`
* Unguessed letters as an array of letters, e.g. `["Q","W","I","P","F","J","K","X","B"]`

High-level explanation:

```
5ÆgX ªNc kVgX)fÃrÈï[Y]c '+Ãf@Vc e!øXÃâ
5ÆgX ªNc kVgX)fÃ                       # Find the valid letters for each position
                rÈï[Y]c '+Ã            # Generate words from the possible letters
                           f@Vc e!øXÃ  # Ensure that all yellow letters are used
                                     â # Remove duplicates

```

Details:

```
5ÆgX ªNc kVgX)fÃ
5Æ             Ã # For each X in range [0...4]:
  gX             #  Return the green letter at index X if possible
     ª           #  Otherwise
      Nc         #  Get all letters from the three inputs
         k   )   #  Remove:
          VgX    #   The yellow letters at index X
              f  #  Remove empty strings

rÈï[Y]c '+Ã
r         Ã      # Reduce the array of valid letters in steps:
 È               #  Current array of prefixes
   [Y]c          #  Possible next letters (converted to array if needed)
  ï              #  Cross product of those two arrays
        '+       #  Concatenate each prefix and letter

f@Vc e!øXÃ
f@       Ã       # Remove any word X where this is false:
  Vc             #  Flatten yellow letters to a single array
     e           #  Return true only if every letter:
      !øX        #   is contained in X

```
> 2 votes

# Answer
# Ruby, 117 bytes

```
->g,y,u{a,*b=g.map{|x|(x>''?x:u+(g+y.map{_1[0]})*'').chars};a.product(*b).select{|m|y.all?{m[_2]!=_1&&m!=m-[_1]}}|[]}

```

Attempt This Online!
> 1 votes

# Answer
# Japt, ~~26~~ 24 bytes

Takes input as 3 arrays of character strings, or empty strings for blanks, in the order: yellow, green, unguessed. Outputs an array of character arrays

```
c@NcfÃá5 £VíªXÃâ fÈíÀU e

```

Try it \- modified to run in a reasonable amount of time without crashing your browser by not allowing letters to be used more than once in each guess.

```
c@NcfÃá5 £VíªXÃâ fÈíÀU e     :Implicit input of arrays U=yellow, V=green & W=unguessed
c                            :Flat map U by
 @                           :Passing each element through the following function
  N                          :  Array of all inputs
   c                         :  Flat map
    f                        :    Filter empty strings
     Ã                       :End map
      á5                     :Permutations of length 5
         £                   :Map each X
          Ví X               :  Interleave V with X
            ª                :  Reducing each pair by Logical OR
              Ã              :End map
               â             :Deduplicate
                 f           :Filter by
                  È          :Passing each through the following function
                   í U       :  Interleave with U
                    À        :  Reducing each pair by testing for inequality
                       e     :  All true?

```
> 1 votes

---
Tags: code-golf, string, word-puzzle
---


title: Is this number Loeschian?

text:
# Question
Title: Is this number Loeschian?
A positive integer \\$k\\$ is a **Loeschian number** if

* \\$k\\$ can be expressed as \\$i^2 + j^2 + i\times j\\$ for \\$i\\$, \\$j\\$ integers.

For example, the first positive Loeschian numbers are: \\$1\\$ (\\$i=1, j=0\\$); \\$3\\$ (\\$i=j=1\\$); \\$4\\$ (\\$i=2, j=0\\$); \\$7\\$ (\\$i=2, j=1\\$); \\$9\\$ (\\$i=-3, j=3\\$); ... Note that \\$i, j\\$ for a given \\$k\\$ are not unique. For example, \\$9\\$ can also be generated with \\$i=3, j=0\\$.

Other equivalent characterizations of these numbers are:

* \\$k\\$ can be expressed as \\$i^2 + j^2 + i\times j\\$ for \\$i, j\\$ non-negative integers. (For each pair of integers \\$i, j\\$ there's a pair of non-negative integers that gives the same \\$k\\$)
* There is a set of \\$k\\$ contiguous hexagons that forms a tesselation on a hexagonal grid so that corresponding cells are the same distance apart (see illustrations for \\$k = 4\\$ and for \\$k = 7\\$). (Because of this property, these numbers find application in mobile cellular communication networks.)
* See more characterizations in the OEIS page of the sequence.

## The challenge

Given a **positive integer**, output a truthy result **if it is a Loeschian number**, or a falsy result otherwise.

The program or function should handle (say in less than a minute) inputs up to \\$1000\\$, or up to data type limitations.

Code golf. Shortest wins.

## Test cases

The following numbers should output a truthy result:

```
1, 4, 7, 12, 13, 108, 109, 192, 516, 999

```

The following numbers should output a falsy result:

```
2, 5, 10, 42, 101, 102, 128, 150, 501, 1000

```

# Answer
> 26 votes
# Jelly, ~~11~~ 9 bytes

```
ÆF‘%3,2ḄȦ

```

Try it online! or verify all test cases.

### Background

In Elementary results on the binary quadratic form *a² + ab + b²*, the author proves the following theorem about Löschian numbers.

> **Theorem 16.** *The necessary and sufficient condition of any non-negative integer to be in the form* a² + ab + b² *is that, in its prime factorization, all primes other than* 3 *that are not in the form* (6k + 1) *have even exponents.*

As noted on the relevant OEIS page, since all integers are are congruent to **0**, **1** or **2** modulo **3**, the number **3** is the only prime that is congruent to **0**, and all numbers of the form **(6k + 1)** are congruent to **1**, the theorem can be stated alternatively as follows.

*A non-negative integer* n *is a Löschian number if and only if all prime factors of* n *that are congruent to* 2 *modulo* 3 *have even exponents.*

### How it works

```
ÆF‘%3,2ḄȦ  Main link. Argument: n (integer)

ÆF         Yield the prime factorization of n, as prime-exponent pairs.
  ‘        Increment all primes and exponents, turning primes of the form 3k - 2
           into multiples of 3 and odd exponents into multiples of 2.
   %3,2    Reduce all incremented primes/exponents modulo 3/2.
           n is Löschian if and only if this does not result in a [0, 0] pair.
           Due to Jelly's form of vectorization, this yields [3, 2] if n = 1.
       Ḅ   Unbinary; convert each pair from base 2 to integer.
           Note that [x, y] = [0, 0] if and only if 2x + y = 0.
        Ȧ  All; return 1 if the result contains no zeroes, 0 otherwise.

```

# Answer
> 19 votes
## Retina, ~~66~~ ~~63~~ ~~45~~ ~~43~~ 36 bytes

```
^()(\1(?<1>.\1))+(\1(.(?(4).\4)))*$

```

Despite the title saying Retina, this is just a plain .NET regex which accepts unary representations of Loeschian numbers.

Inputs 999 and 1000 take well under a second.

Try it online! (The first line enables a linefeed-separated test suite, and the next two take care of the conversion to unary for convenience.)

### Explanation

The solution is based on the classification that the input can be written as `i*i + j*(i + j)` for positive `i` and non-negative `j` (since we don't have to handle input `0`), and that `n*n` is just the sum of the first `n` odd integers. Golfing this was an interesting exercise in forward references.

A "forward reference" is when you put a backreference inside the group it refers to. Of course that doesn't work when the group is used the first time, since there is nothing to be backreferenced yet, but if you put this in a loop, then the backreference gets the previous iteration's capture each time. This in turn, let's you build up a larger capture with each iteration. This can be used to craft very compact patterns for things like triangular numbers, squares and Fibonacci numbers.

As an example, using the fact that squares are just sums of the first `n` odd integers, we can match a square input like this:

```
(^.|..\1)+$

```

On the first iteration, `..\1` can't work, because `\1` doesn't have a value yet. So we start with `^.`, capturing a single character into group `1`. On subsequent iterations, `^.` no longer matches due to the anchor, but now `..\1` is valid. It matches two more characters than the previous iteration and updates the capture. This way we match increasing odd numbers, getting a square after each iteration.

Now unfortunately, we can't use this technique as is. After matching `i*i`, we need to get `i` as well, so that we can multiply it by `j`. A simple (but long) way to do this is to make use of the fact that matching `i*i` takes `i` iterations, so that we've captured `i` things in group `1`. We could now use balancing groups to extract this `i`, but like I said that's expensive.

Instead, I figured out a different way to write this "sum of consecutive odd integers" that also yields `i` in a capturing group at the end. Of course the `i`th odd number is just `2i-1`. This gives us a way to increment the forward reference only by 1 on each iteration. That's this part:

```
^()(\1(?<1>.\1))+

```

This `()` just pushes an empty capture onto group `1` (initialising `i` to `0`). This is pretty much equivalent to the `^.|` in the simple solution above, but using `|` in this case would be a bit trickier.

Then we have the main loop `(\1(?<1>.\1))`. `\1` matches the previous `i`, `(?<1>.\1)` then updates group `1` with `i+1`. In terms of the *new* `i`, we've just matched `2i-1` characters. Exactly what we need.

When we're done, we've matched some square `i*i` and group `1` still holds `i` characters.

The second part is closer to the simple square matching I showed above. Let's ignore the backreference to `1` for now:

```
(.(?(4).\1))*

```

This is basically the same as `(^.|..\4)*`, except that we can't make use of `^` because we're not at the start of the string. Instead we make use of a conditional, to match the additional `.\1` only when we've already used group `4`. But in effect this is exactly the same. This gives us `j*j`.

The only thing that's missing is the `j*i` term. We combine this with the `j*j` by making use of the fact that the `j*j` computation still takes `j` iterations. So for each iteration we also advance the cursor by `i` with `\1`. We just need to make sure not to write that into group `4`, because that would mess with matching consecutive odd numbers. That's how we arrive at the:

```
(\1(.(?(4).\1)))*

```

# Answer
> 14 votes
## CJam (16 15 bytes)

```
{mF{~\3%2=&},!}

```

Online demo

This is a block (an "anonymous function") which takes input on the stack and leaves `0` or `1` on the stack. It uses the characterisation that a number is Loeschian iff it has no prime factor equal to 2 mod 3 with odd multiplicity.

Thanks to Dennis for a one-byte saving.

# Answer
> 7 votes
# Python 2, 49 bytes

```
lambda n:0in[(n-3*i*i+0j)**.5%1for i in range(n)]

```

Try it online!

Uses the equivalent quadratic form given on OEIS of `n == 3*i*i+j*j`. Check whether `n-3*i*i` is a perfect square for any `i` by taking its square root and checking if it's an integer, i.e. equals 0 modulo 1. Note that Python computes square roots of perfect squares exactly, without floating point error. The `+0j` makes it a complex number to avoid an error on the square root of a negative.

# Answer
> 6 votes
## Haskell, 42 bytes

```
f k=or[k==i*i+j*j+i*j|i<-[0..k],j<-[0..i]]

```

Usage example: `f 501` -\> `False`.

Tries all combinations of `i` from `0` to `k` and `j` from `0` to `i` . `or` returns `True` if the equality `k==i*i+j*j+i*j` holds for at least one of the combinations.

@flawr found a slightly different version with the same byte count:

```
f k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]

```

# Answer
> 6 votes
# Python 2, 56 bytes

```
lambda n:any(n==i*i%n+i/n*(i/n+i%n)for i in range(2*n*n))

```

# Answer
> 5 votes
## Java 8, 81 bytes

```
k->{for(int i=0,j;i<=k;i++)for(j=0;j<=k;)if(i*i+j*j+i*j++==k)return 1;return 0;};

```

simple, naïve implementation. coincidentally same code as C# but uses `->` rather than `=>`.

# Answer
> 5 votes
# Jellyfish, ~~56~~ ~~43~~ ~~41~~ ~~29~~ 28 bytes

**2 bytes thanks to Zgarb**

```
p
n    <
+`/
`1*
/
+
&*r&;>i

```

Try it online!

A fork of my Jelly answer.

# Answer
> 4 votes
# Jelly, ~~15~~ ~~14~~ ~~13~~ 12 bytes

**1 byte thanks to miles.**

```
²S+P
‘ṗ2’Ç€i

```

Try it online!

Verify the smaller testcases.

A word of advice when testing for large numbers (bigger than 50): don't.

Truthy is a positive number. Falsey is zero.

### Explanation

```
‘ṗ2’Ç€i   main chain, argument: z
‘ṗ2’      generate all pairs of numbers between 0 and z inclusive
    Ç€    apply the helper link to each pair
      i   find the index of z in the result

²S+P   helper link, argument: [x,y] (a pair of numbers)
²      compute [x*x, y*y]
 S     x*x+y*y
  +P   x*x+y*y+x*y

```

# Answer
> 4 votes
# MATL, ~~14~~ 13 bytes

```
t:0hU&+HM&*+m

```

Try it online! Or verify all test cases.

Outputs `1` or `0`.

### Explanation

```
t:    % Implicitly input number k. Duplicate. Generate vector [1 2 ...k]
0h    % Concatenate a 0. Gives [1 2 ... k 0]
U     % Square, element-wise. Gives [1 4 ... k^2 0]
&+    % Sum of all pairs from this vector. Gives a (k+1)×(k+1) matrix
HM    % Push [1 2 ... k 0] again
&*    % Product of all pairs from this vector. Gives a (k+1)×(k+1) matrix
+     % Add the two matrices
m     % True if k is a member of the resulting matrix. Implicitly display

```

# Answer
> 4 votes
## Python, 67 bytes

```
lambda k,r=range:any(i*i+j*j+i*j==k for i in r(k+1)for j in r(k+1))

```

https://repl.it/Cj6x

# Answer
> 4 votes
# Brachylog, 13 bytes

```
ḋḅ{h%₃<2|~j}ᵐ

```

Try it online!

### Explanation

Uses the prime factors approach.

```
ḋḅ{h%₃<2|~j}ᵐ
ḋ              Prime factorization: gives a list like [7, 3, 2, 2]
 ḅ             Analyze into blocks of the same value: [[7], [3], [2, 2]]
  {        }ᵐ  This predicate must succeed for each block:
   h            The head (first number in the list, i.e. the prime factor)
    %₃           mod 3
      <2         is less than 2
        |       Or
         ~j      the list can be considered the result of joining two identical sublists
                 (i.e. its length is even, i.e. that prime factor has an even exponent)

```

# Answer
> 3 votes
# C (gcc), 71 69 bytes

```
i,j,r;f(n){for(r=i=n+1;i--;)for(j=n;j--;)r*=n!=i*i+j*j+i*j;return!r;}

```

# Answer
> 3 votes
## VBA, ~~68~~ 67 bytes

```
Function L(N):For a=0To N:For b=0To a:L=L+(N=a^2+a*b+b^2):Next b,a

```

Naive search, starting to slow down slightly for n=1000. Excel recognizes zero return as falsy, all other returns as truthy.

Note that investigation of negative *i* and *j* is not needed, since given *i\>j\>=0* :

> *(-i)2 \+ (-i)(-j) + (-j)2 = i2 \+ ij + j2*

(the same result as for *i* and *j*)

> *(-i)2 \+ (-i)j + j2 = i2 \- ij + j2*
>
> *i2 \+ i(-j) + (-j)2 = i2 \- ij + j2*

(if one is negative, it doesn't matter which one), and then

> *(i-j)2 \+ (i-j)j + j2 = (i2 \- 2ij + j2) + (ij - j2) + j2 = i2 \- ij + j2*

And since both *(i-j)* and *j* are non-negative, any generation of Loeschian numbers involving a negative number can be achieved using non-negative numbers.

---

*Saved a byte, `Next:Next` -\> `Next b,a` thanks to Taylor Scott.*

# Answer
> 2 votes
## C#, ~~84~~ ~~82~~ 81 bytes

```
k=>{for(int i=0,j;i<=k;++i)for(j=0;j<=k;)if(i*i+j*j+i*j++==k)return 1;return 0;};

```

A naïve solution. 1 = true, 0 = false

# Answer
> 2 votes
# 05AB1E, 10 bytes

```
ÝãDnOsP+Iå

```

Try it online or verify all test cases.

**Explanation:**

```
Ý           # Push a list in the range [0, (implicit) input]
 ã          # Create all possible pairs by taking the cartesian product on itself
  D         # Duplicate this list of pairs
   n        # Square each inner value in the pairs: [i²,j²]
    O       # Sum each inner pair together: i²+j²
     s      # Swap so the original list of pairs is at the top of the stack again
      P     # Take the product of each inner pair: i*j
       +    # Sum the values in the list at the same positions: i²+j²+i*j
        Iå  # And check if the input-integer is in this list
            # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Desmos, ~~62~~ 60 bytes

```
f(k)=\prod_{n=0}^k\prod_{m=0}^k\left\{mm+nn+mn=k:0,1\right\}

```

Outputs \\$0\\$ for truthy and \\$1\\$ for falsey

Try It On Desmos!

Explanation:
The products(\\$\prod\\$) iterate through \\$0\\$ through \\$k\\$ inclusive for both \\$m\\$ and \\$n\\$. It then tests if \\$m^2+n^2+mn=k\\$. If it does, then we know that \\$k\\$ is a Loeschian number, and we multiply by \\$0\\$. Else, we multiply by \\$1\\$. So if we don't encounter any pairs of \\$m\\$ and \\$n\\$ that satisfy \\$m^2+n^2+mn=k\\$, it will keep on multiplying \\$1\\$, and therefore it will stay at \\$1\\$ at the end. So the falsey value is \\$1\\$. But if a pair does satisfy \\$m^2+n^2+mn=k\\$, then it multiplies by \\$0\\$, and because \\$0\\$ times anything is \\$0\\$, and we are essentially just multiplying over and over again, it is guaranteed that once we multiply by \\$0\\$, it will stay at \\$0\\$. Hence, the truthy value is \\$0\\$.

# Answer
> 1 votes
## PowerShell v2+, ~~63~~ ~~56~~ 55 bytes

```
param($k)(0..$k|%{0..($i=$_)|%{$i*($i+$_)+$_*$_}})-eq$k

```

Takes input `$k`, loops upwards twice (outer loop `$i = 0 to $k`, inner loop `$j = 0 to $i`), each iteration generates the result of `i*i + j*j + i*j` (shortened to `i*(i+j) + j*j`). Those results are encapsulated in parens, and passed as an array to `-eq$k`. This acts as a filter to select only elements that equal the input. Outputs a nonzero (the number back) for truthy, or nothing (empty) for falsey. Processes `1000` in about 15 seconds on my machine.

### Test Cases

```
PS C:\Tools\Scripts\golfing> (1,4,7,12,13,108,109,192,516,999|%{.\loeschian-numbers.ps1 $_})-join','
1,4,7,12,13,108,109,192,516,999

PS C:\Tools\Scripts\golfing> (2,5,10,42,101,102,128,150,501,1000|%{.\loeschian-numbers.ps1 $_})-join','

PS C:\Tools\Scripts\golfing>

```

# Answer
> 1 votes
# Javascript (using external library - Enumerable) (63 bytes)

```
k=>_.Range(0,k+1).Any(i=>_.Range(0,k+1).Any(j=>i*i+j*j+i*j==k))

```

Link to library: https://github.com/mvegh1/Enumerable Code explanation: Create a range of integers from 0 to k (call this the "i" range), and test if any "i" satisfies a certain predicate. That predicate creates a range from 0 to k (call this the "j" range), and tests if any "j" satisfies a certain predicate. That predicate is the loeschian formula

# Answer
> 1 votes
## Matlab, ~~53~~ 52 bytes

```
n=input('');[a b]=ndgrid(0:n);find((a+b).^2-a.*b==n)

```

Simple search over all possibilities.
Outputs empty array as falsy and a non-empty vector as truthy value.

Considering all-zeros matrix as falsy and not-all-zeros matrix as truthy we can get rid of the `find` function resulting in **~~47~~ 46 bytes** solution:

```
n=input('');[a b]=ndgrid(0:n);(a+b).^2-a.*b==n

```

*One byte saved thanks to @flawr*

# Answer
> 1 votes
# Perl 6,  ~~52 51~~  50 bytes

```
->\k{?first ->(\i,\j){k==i*i+j*j+i*j},(0..k X 0..k)}
->\k{?grep ->(\i,\j){k==i*i+j*j+i*j},(0..k X 0..k)}

{?grep ->(\i,\j){$_==i*i+j*j+i*j},(0..$_ X 0..$_)}

```

### Explanation:

```
{
  # Turn the following into a Bool
  # ( Technically not necessary as a list of 1 or more values is truthy )
  ?

  # find all where the code block returns a truthy value
  grep

  # pointy block that takes one value (list of 2 values)
  # and gives each of the values in it a name
  ->
    $ ( \i, \j )
  {
    # return true if the definition matches
    $_ == i*i + j*j + i*j
  },

  # a list of 2 element lists (possible i and j values)
  ( 0..$_ X 0..$_ )
}

```

### Test:

```
use v6.c;
use Test;

my @true = 0, 1, 4, 7, 12, 13, 108, 109, 192, 516, 999;
my @false = 2, 5, 10, 42, 101, 102, 128, 150, 501, 1000;

plan (@true + @false) * 2;

my &is-loeschian = {?grep ->(\i,\j){$_==i*i+j*j+i*j},(0..$_ X 0..$_)}

for |(@true X True), |(@false X False) -> ( $input, $expected ) {
  my ($result,$seconds) = $input.&time-it;
  is $result, $expected, ~$input;
  cmp-ok $seconds, &[<], 60, "in $seconds seconds"
}

sub time-it ( $input ) {
  my $start = now;
  my $result = $input.&is-loeschian;
  my $finish = now;
  return ( $result, $finish - $start )
}

```

```
1..42
ok 1 - 0
ok 2 - in 0.00111763 seconds
ok 3 - 1
ok 4 - in 0.00076766 seconds
...
ok 19 - 516
ok 20 - in 0.19629727 seconds
ok 21 - 999
ok 22 - in 0.1126715 seconds
ok 23 - 2
ok 24 - in 0.0013301 seconds
ok 25 - 5
ok 26 - in 0.00186610 seconds
...
ok 37 - 150
ok 38 - in 0.83877554 seconds
ok 39 - 501
ok 40 - in 9.2968558 seconds
ok 41 - 1000
ok 42 - in 37.31434146 seconds

```

# Answer
> 1 votes
# Perl, 54 + 1 (`-n` flag) = 55 bytes

```
for$i(0..$_){for$j(0..$_){$i*$i+$j*$j+$i*$j-$_?1:say}}

```

Needs `-n` and `-M5.010` flags to run :

```
perl -nE 'for$i(0..$_){for$j(0..$_){$i*$i+$j*$j+$i*$j-$_?1:say}}'

```

Outputs some stuffs if the number is a Loeschian number, and nothing otherwise.

This implementation is quite boring, so here is another one, for 87 bytes, regex-based, just for the eyes :

```
perl -pE '$_=(1 x$_)=~/^(.*)(??{$1x(-1+length$1)})(.*)(??{$2x(-1+length$2)})(??{$1x length$2})$/'

```

Carefull with this one, as the backtracking will use a lot of memory, so don't try to test numbers too big! (especially numbers that aren't Loeschians)

# Answer
> 1 votes
# Dyalog APL, 19 bytes

```
⊢∊(∘.(×-⍨2*⍨+)⍨0,⍳)

```

Checks if *k* ∊ (*i* \+ *j*)² – *ij*, for any 0 ≤ *i*, *j**k*.

is *k*
a member of
`∘.` all combinations of
`×` *i* times *j*
`-⍨` subtracted from
`2*⍨` the square of
`+` *i* plus *j*
for all *i* **and** *j* in
`0,` zero prepended to
the integers 1 through *k*

1000 takes 3.3 seconds on my M540 and even less on TryAPL.

# Answer
> 1 votes
# C, 66 bytes

Call `f()` with the number to test. The function returns the number of solutions it found.

```
q,r;f(n){for(r=q=0;q++<n*n;r+=n==q%n*(q%n+q/n)+q/n*q/n);return r;}

```

Try it on ideone.

# Answer
> 1 votes
# Mathematica, 44 bytes

```
MemberQ[(+##)^2-##&@@@0~Range~#~Tuples~2,#]&

```

Unnamed function taking an integer as input and returning `True` or `False`. The command `0~Range~#~Tuples~2` creates all ordered pairs of integers both between `0` and the input `#`. The function `(+##)^2-##&` computes the square of the sum of its arguments minus the product of its arguments; when called on two arguments `i` and `j`, this is exactly `i^2+j^2+ij` as desired. So that function is called on all the tuples, and then `MemberQ[...,#]` checks whether the input is one of the resulting values.

# Answer
> 1 votes
# ASP, 39 + 4 = 43 bytes

```
o:-k=I*I+J*J+I*J;I=1..k;J=1..k.:-not o.

```

Output: the problem is satisfiable iff k is Loeschian.

Answer Set Programming is a logical language, similar to prolog. I use here the Potassco implementation, *clingo*.

Input is taken from parameters (`-ck=` is 4 bytes long). Call example:

```
clingo -ck=999

```

Output sample:

```
SATISFIABLE

```

Tried with 1000:

```
clingo -ck=1000

```

Output sample:

```
UNSATISFIABLE

```

You can try it in your browser ; unfortunately, this method doesn't handle call flags, so you need to add the line `#const k=999` in order to make it work.

---

Ungolfed & explained code:

```
v(1..k).  % predicate v(X) holds for any X in [1..k]
o:- k=I*I+J*J+I*J ; v(I) ; v(J).  % o holds if k is Loeschian.
:- not o.  % discard models where o doesn't holds (make problem unsatisfiable)

```

# Answer
> 1 votes
# PHP, 70 bytes

```
for(;$i++<$k=$argv[1];)for($j=$i+1;$j--;)$i*$i+$j*$j+$i*$j-$k?:die(1);

```

takes input from command line argument; exits with `1` for Loeschian number, with `0` else.
Run with `-nr`.

**breakdown**

```
for(;$i++<$k=$argv[1];)     # loop $i from 1 to $k
    for($j=$i+1;$j--;)      # loop $j from $i to 0
        $i*$i+$j*$j+$i*$j-$k?   # if $i,$j,$k do not satisfy the equation, do nothing
        :die(1);                # else exit with return code 1
                            # implicit: exit with code 0

```

---

# revisited, 67 bytes

by merging the loops to one:

```
for($b=1+$a=$n=$argv[1];$b--||$b=--$a;)$a*$a+$b*$b+$a*$b-$n||die(1);

```

not tested, though

pushed it a little further ...

## 57 bytes:

```
while($a*$a+$b*$b+$a*$b-$argn)$b++<$a||$b=1/($a++<$argn);

```
* takes input from pipe; run with -nR
* no output if input is Loeschian, division by zero error if not
* not tested either

Haven´t been here for a while. I thought I remembered that deliberate errors were forbidden; but I couldn´t find it. What I found instead was a deleted post in the loopholes thread that requested to forbid output to STDERR. Could someone refresh my memory?

**breakdown**

```
# $a and $b are implicitly initialized with NULL, which increments to 1
while($a*$a+$b*$b+$a*$b-$argn)      # while solution not found
    $b++<$a                         # inner loop: $b from 1 to $a
    ||$b=1/($a++<$argn);            # outer loop: $a from 0 to $argn(=input)
    # $a<$argn: 1/true -> 1
    # else: 1/false -> division by zero

```

# Answer
> 1 votes
# Add++, ~~28~~ 26 bytes

```
D,g,@@,*aaz€b*Fs
L,0rd‽gAe

```

Try it online! or verify the test cases

Takes a long time for large inputs. Times out on TIO for the `501` and larger test cases.

## How it works

```
D,g,@@,		; Define a helper function that takes 2 arguments, i and j
		; Example: i = 0, j = 2			STACK = [0 2]
	*	; Multiply				STACK = [0]
	aaz	; Push [i i] and [j j]			STACK = [0 [0 0] [2 2]]
	€b*	; Take their products			STACK = [0 [0 4]]
	Fs	; Flatten and return the sum		STACK = [0 0 4 4]
		; Returns i*i + i*j + j*j		Returns 4

L,		; Main function, takes 1 argument, k
		; Example: k = 4			STACK = [4]
	0r	; Range from 0				STACK = [[0 1 2 3 4]]
	d	; Duplicate				STACK = [[0 1 2 3 4] [0 1 2 3 4]]
	‽	; Across all pairs...			STACK = [[[0 0] [0 1] [0 2] ... [4 2] [4 3] [4 4]]]
	    g	;   run the helper function		STACK = [[0 1 4 ... 28 37 48]]
	Ae	; Is k in the array?			Returns 1

```

# Answer
> 1 votes
# GAP 4.7.9, 75 bytes

```
k->Filtered(Collected(FactorsInt(k)),d->RemInt(d[2],2)+RemInt(d[1],3)=3)=[]

```

Every positive integer \\$k\\$ has a unique representation as the product of powers of distinct primes, \\$p\_1^{e\_1}\dots p\_s^{e\_s}\\$. \\$k\\$ is Loeschian iff no prime \\$p\_i\\$ occurs to an odd power \\$e\_i\\$ if \\$p\_i=2\\$ modulo 3.

The above GAP code is for a lambda-expression which returns `true` if `k` is Loeschian and `false` if not.

Try it online!

Its algorithm is nice and simple but the long names for some of those GAP functions make for poor golf, unfortunately.

# Answer
> 1 votes
# Japt, 13 bytes

```
ô ï d@¶Xx²+X×

```

Try it

# Answer
> 1 votes
# Husk, 11 bytes

```
€¹m§+Πṁ□π2ṡ

```

Try it online!

# Answer
> 1 votes
# Jelly, ~~9~~ 8 bytes

```
Żp`ḋÄ$€i

```

Try it online!

Returns a non-zero integer for Loeschian numbers and \\$0\\$ for non-Loeschian numbers

-1 byte thanks to Sisyphus

May be a little cheeky to post, as the only reason this is shorter than Leaky's and Dennis’ Jelly answer is due to newer features, but it's different enough from the existing Jelly answers.

## How it works

```
Żp`ḋÄ$€i - Main link. Takes k on the left
Ż        - Yield [0, 1, 2, ..., k]
  `      - Use this as both left and right argument for:
 p       -   Cartesian power
     $€  - Over each pair, [i, j], run the previous two commands:
    Ä    -   Cumulative sum; [i, i+j]
   ḋ     -   Dot product with [i, j]; Yields i×i+j×(i+j) = i×i + i×j + j×j
           This yields all Loeschian numbers below 3k²
       i - Index of k in this list, or 0 if not found

```

# Answer
> 1 votes
# Pyth, 17 bytes

```
.Am+%hd3%h/PQd2{P

```

Try it online! Test cases

Translation of Dennis's Jelly answer.

# Answer
> 1 votes
# Perl 5 `-pal`, 50 bytes

```
$_=grep{//;grep$'*$'+$_*$_+$'*$_=="@F",0..$_}0..$_

```

Try it online!

# Answer
> 1 votes
# Jellyfish, 26 bytes

```
p
c-&*+S
i*  R
 E  E,r&;32

```

Try it online!

Judge if the input value is in { (x+y)^2-xy | 0\<=x,y\<32 } with `c`

# Answer
> 1 votes
# JavaScript (Node.js), 51 bytes

```
k=>g=(z=k*k,i=z/k|0)=>z&&(i+z%k)**2-z%k*i==k|g(z-1)

```

Try it online!

n^2 time

# JavaScript (Node.js), 59 bytes

```
k=>g=(i=k,j=k)=>i<0|j<0?0:i*i+j*j+i*j-k?g(i-1,j)|g(i,j-1):1

```

Try it online!

C(2k,k) time

---
Tags: code-golf, math, number, number-theory, decision-problem
---


title: Divide by an odd number, 2-adically

text:
# Question
Title: Divide by an odd number, 2-adically
Given \\$a\\$ and \\$b\\$, both odd \\$n+1\\$-bit integers, compute \\$a/b\\$ to a precision of \\$n+1\\$ bits in the 2-adic integers. That is, compute \\$c\\$ such that \\$a = bc\\, (\mathop{\rm mod} 2^{n+1})\\$. \\$n\\$ should be your language's native integer size, or if native integers are bigints, take it as a parameter. If your language uses trits (and presumably is either Setun assembly, TriINTERCAL, or Malbolge), you may instead compute in the 3-adics, in which case \\$a\\$ and \\$b\\$ should be multiples of 3 plus 1.

Inputs should be \\$(a-1)/2\\$ and \\$(b-1)/2\\$ (trits: \\$(x-1)/3\\$).

This is , so shortest answer in bytes (per language) wins.

**Test cases:**

All test cases are truncatable; if the last \\$n\\$ bits match the inputs, the last \\$n\\$ bits of the outputs match.
Test cases (in hex, 32bit): (apologies for poor vinculum placement)

```
|  (a-1)/2  |  (b-1)/2  | (a/b-1)/2 |
|-----------+-----------+-----------|
| …00000000 | …00000001 | …55555555 | (1/3 = A̅B)
| …00000000 | …00000002 | …66666666 | (1/5 = C̅D)
| …00000001 | …00000002 | …33333333 | (3/5 = 6̅7)
| …00000000 | …00000003 | …DB6DB6DB | (1/7 = 6̅D̅B̅7)
| …FFFFFFFF | …00000003 | …24924924 | (-1/7 = 2̅4̅9̅)
| …4620BA27 | …1876DCBC | …48CAF903 | (random)

```

More test cases may be generated by multiplying random \\$n+1\\$-bit odd integers and taking the last \\$n+1\\$ bits of the result (then shifting right by 1).

A few test cases for ternary computers (nonary this time):

```
|  (a-1)/3  |  (b-1)/3  | (a/b-1)/3 |
|-----------+-----------+-----------|
| …00000000 | …00000002 | …51251251 | (1/7 = 3̅7̅6̅4)
| …23472148 | …12435871 | …65732854 | (random again)

```

Similarly, do the same with \\$n+1\\$-trit integers ending with a 1 trit.

# Answer
# Python, 45 bytes

```
lambda a,b,n:(a-~a)*pow(b-~b,-1,2<<n)//2%2**n
```

Attempt This Online!

Beginning with Python 3.8 the builtin `pow` can directly compute the modular inverse.
> 4 votes

# Answer
# PARI/GP, 32 bytes

```
f(a,b,n)=(2*a+1)/(2*b+1)%2^n++\2
```

Attempt This Online!

PARI/GP has a built-in p-adic type, but using the `%` operator is shorter.
> 3 votes

# Answer
# C (gcc), 48 bytes

```
c;i;f(a,b){for(i=32;i;--i)c=a-b-2*b*c;return c;}

```

Try it online!

Explanation: since \\$(2b+1) (2c+1) = 2(2bc+b+c)+1\\$ should end up equal to \\$2a+1\\$, we want to find a root of \\$f(c) = 2bc+b+c-a\\$. We do so using Newton's method (as in the proof of Hensel's lemma), with the optimization that \\$f'(c) = 2b+1 \equiv 1\pmod{2}\\$, so it suffices to divide by 1 instead of by \\$f'(c)\\$. So, we iterate to find a fixed point of \\$c \mapsto c - \frac{f(c)}{1} = a-b-2bc\\$. (And since each iteration increases the number of correct binary digits by at least one, and we are working with 32-bit integers, then 32 iterations suffices.)

Note that it's interesting we do not need to initialize `c` to any particular starting value, since whatever the starting value is, we converge to the unique fixed point anyway.
> 3 votes

# Answer
# C (gcc), 41 bytes

```
f(a,b){return b?f(2*a*b+a+b,b*b+b<<1):a;}

```

Try it online!

This uses the same method as my previous answer: apply \\$a/b = ab/b^2\\$ repeatedly until \\$b=1\\$, and then \\$a/1=a\\$. Because \\$(\mathbb{Z}/2^{33}\mathbb{Z})^{\times}\\$ is a group of order \\$2^{32}\\$, this finishes after at most 32 iterations.
> 2 votes

# Answer
# x86 opcode, 17 bytes

```
f:  sub edi, esi
    lea esi, [esi*2+1]
.a: inc ecx
    mov eax, ecx
    mul esi
    cmp eax, edi
    jnz .a
    xchg eax, ecx
    ret

```

Try it online!

# x86 opcode, 19 bytes

```

	xchg eax, edi
f:	lea ecx, [esi+1]
	lea eax, [esi+ecx]
	mul edi
	add eax, esi
	imul esi, ecx
	shl esi, 1
	jnz f-1
	ret

```

# C (gcc), 41 bytes

```
i;f(a,b){for(;a-b+--i*(~b-b););return i;}

```

Try it online!

To make it comparable with the other a few
> 2 votes

# Answer
# , 36 bytes

```
\(a,b){while((b*F)%%2^32-a)F=F+1;+F}
```

Attempt This Online! or try the first few test-cases with `n` set to 15

Input `a` and `b`, outputs `c` = `a/b`(modulo `2^32`).

Uses floating-point calculations to try each multiple of `b` until it finds the first one that equals `a` mod `2^32` (corresponding to R's integer size). Note that this means that some inputs may be subject to floating-point rounding errors when `c*b` exceeds `2^53`.

---

# , 40 bytes

```
\(a,b){while((F=(F+b)%%2^32)-a)T=T+1;+T}
```

Attempt This Online! or try the first 2 test-cases with `n` set to 15

This also uses floating-point calculations to successively increment by `b` until the total mod `2^32` equals `a`, but here they are limited to a maximum of `2^33`, which is easily within the range that is representable without loss-of-precision, so output for all inputs is exact.
It's *much* slower, though.
> 1 votes

# Answer
# Husk, 11 bytes

```
€Mo%`^2→⁰*N

```

Try it online! or try the first test-case with `n` set to 15

Input is `n`, `b`, `a`; output is `c` = `a/b` (modulo `2^(n+1)`).

One byte less (remove the ) it it's acceptable to input the number of bits of the modulus (`n+1`) directly. 4 bytes less if it's acceptable to input the modulus itself directly.
> 1 votes

# Answer
# ARM T32 machine code, 16 bytes

```
004a 3201 4350 1840 3201 4351 d1f8 4770

```

In assembly:

```
f:  lsls r2, r1, #1 @ Set r2 to b-1 ((b-1)/2 is in r1).
    adds r2, #1     @ r2 becomes b.
    muls r0, r2     @ r0 (which was (a-1)/2) becomes b(a-1)/2.
    adds r0, r1     @ r0 becomes b(a-1)/2 + (b-1)/2 = (ab-1)/2.
    adds r2, #1     @ r2 becomes b+1.
    muls r1, r2     @ r1 becomes (b+1)(b-1)/2 = (b²-1)/2.
    bne.n f         @ Jump back if that is nonzero.
    bx lr           @ Return.

```

This applies \\$a/b = ab/b^2\\$ repeatedly until \\$b=1\\$, and then \\$a/1=a\\$.
Because \\$(\mathbb{Z}/2^{33}\mathbb{Z})^{\times}\\$ is a group of order \\$2^{32}\\$, this finishes after at most 32 iterations.
> 1 votes

# Answer
# Z80, 14 bytes (n=8)

Input is \\$(a-1)/2\\$ in `a`, \\$(b-1)/2\\$ in `c`; output is in `d`. Trashes `a`, `b`, `f`. (Well, everything trashes `f`.)

```
91 06 08 CB 38 1F 30 03
91 CB FA 10 F6 C9

```

Disassembled:

```
f:
    sub c       // 91       r = n - d
    ld b,8      // 06 08    do 8 times:
l:
    srl d       // CB 38    q >>= 1
    rra         // 1F       r >>= 1
    jr nc,ns    // 30 03    Was r even?
    sub c       // 91       N: r -= d
    set 7,d     // CB FA    N: q |= 1 << 7
ns:
    djnz l      // 10 F6    in any case: jump back first 7 times.
    ret         // C9       return

```
> 0 votes

# Answer
# Charcoal, 29 bytes

```
ＮθＮηＦＮ«⊞υ﹪θ²≧⁻×η﹪θ²θ≦⊘θ»Ｉ↨⮌υ²

```

Try it online! Link is to verbose version of code. Takes `a`, `b` and `n+1` as input and outputs `c=a/b`. Explanation: This is like long division in reverse; to get the `i+1`th bit you compute `c` to `i` bits and see whether you want to add a `0` or `1` bit to `c`. Rather than calculating `b*c` each time, `a` is reduced each time a `1` bit is added to `c`, and also a power of `2` is eliminated by dividing `a` by `2` each step.

```
ＮθＮηＦＮ«

```

Input `a`, `b` and `n+1` and repeat that many times.

```
⊞υ﹪θ²

```

Save the LSB of `a` into `c`.

```
≧⁻×η﹪θ²θ

```

If `a` was odd then subtract `b` from it.

```
≦⊘θ

```

Divide `a` by `2`.

```
»Ｉ↨⮌υ²

```

Convert `c` from binary.
> 0 votes

# Answer
# MMIX, 44 bytes (11 instructions) (n = 64)

Call sequence: get \\$a\\$ in `$(X+1)`, \\$b\\$ in `$(X+2)`, `PUSHJ $X,div2ad`, quotient is now in `$X`, and as a bonus `$(X+2)` is unchanged and `$(X+1)` contains a sort of remainder that can be used again starting an instruction later to get more bits.

Hexdump (jxd -T):

```
00000000: 26000001 e3020000 e3030001 76ff0003  &¡¡¢ẉ£¡¡ẉ¤¡¢v”¡¤
00000010: 3b030301 c00202ff 76ff0001 3f000001  ;¤¤¢Ċ££”v”¡¢?¡¡¢
00000020: 260000ff 5b03fffa f8030000           &¡¡”[¤”«ẏ¤¡¡

```

Dissassembled:

```
div2ad  SUBU $0,$0,$1   // r = a - b
        SET  $2,0       // q = 0
        SET  $3,1       // holds 2^i
0H      ZSOD $255,$0,$3 // loop: tmp = (r&1)? 2^i : 0
        SLU  $3,$3,1    // increment i
        OR   $2,$2,$255 // q |= tmp
        ZSOD $255,$0,$2 // tmp = (r&1)? b : 0
        SRU  $0,$0,1    // r >>= 1
        SUBU $0,$0,$255 // r -= tmp
        PBNZ $3,0B      // if(i <= 64) goto loop (that 1 bit got shifted off the high end)
        POP  3,0        // return q,r,b in that order

```
> 0 votes

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


title: CGAC2022 Day 21: Present stack headache

text:
# Question
Title: CGAC2022 Day 21: Present stack headache
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

*challenge idea by emanresu A*

Santa has a bunch of presents wrapped in cuboid boxes of various sizes. As his sled flies above a chimney, a stack of presents will be automatically dropped through it. Santa wants to carefully choose the presents so that all of them fit into a rectangular chimney.

All presents must be center-aligned due to *magical physics* issues (i.e. placing two small presents side-by-side is not allowed). The presents can be rotated, but four of the faces must be parallel to that of the chimney. A present fits in the chimney if both its width and length are `<=` those of chimney after rotation.

## Task

Given the dimensions of the presents and the chimney, determine the maximum number of presents that fit in the chimney (i.e. sum of the presents' heights is `<=` that of the chimney). All dimensions are positive integers.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Presents and chimney are given as `[width, length, height]`.

```
Presents: [[6, 6, 4], [2, 2, 2], [2, 2, 2], [2, 2, 2]]
Chimney: [6, 6, 6]
Answer: 3
Explanation: Use three small cubes.
(Placing two or more cubes above or below the single large box is not allowed)

Presents: [[6, 10, 9], [10, 7, 6], [10, 7, 5], [10, 7, 4], [5, 10, 10]]
Chimney: [6, 5, 999]
Answer: 0
Explanation: No present fits in the chimney

Presents: [[1, 2, 6], [1, 6, 2], [2, 1, 6], [2, 6, 1], [6, 1, 2], [6, 2, 1]]
Chimney: [2, 6, 6]
Answer: 6
Explanation: All six presents can be rotated to [2, 6, 1],
which fits the chimney and takes up only 1 unit of height

Presents: [[1, 2, 6], [1, 6, 2], [2, 1, 6], [2, 6, 1], [6, 1, 2], [6, 2, 1]]
Chimney: [1, 6, 6]
Answer: 3
Explanation: All six presents can be rotated to [1, 6, 2]

Presents: [[1, 2, 6], [1, 6, 2], [2, 1, 6], [2, 6, 1], [6, 1, 2], [6, 2, 1]]
Chimney: [1, 3, 13]
Answer: 2
Explanation: All six presents can be rotated to [1, 2, 6]

```

# Answer
> 5 votes
# Python 3, 130 bytes

```
lambda W,L,H,a:sum(0<=(H:=H-i)for i in sorted(min(h+H*(w>W or l>L)for h,w,l in permutations(b))for b in a));from itertools import*

```

Try it online!

# Answer
> 3 votes
# Python3, 217 bytes:

```
lambda c,p:max(max(f(c,[*i]))for i in P(p,len(p)))
from itertools import*
P=permutations
def f(c,p,H=0,k=0):
 yield k
 if p:
  for w,l,h in P(p[0],3):
   if c[0]>=w>0<l<=c[1]and H+h<=c[2]:yield from f(c,p[1:],H+h,k+1)

```

Try it online!

# Answer
> 2 votes
# Charcoal, 72 bytes

```
Ｆθ«≔Ｅ³Ｅ³§ι⁺κμι≔Φ⁺ιＥι⮌κ⬤κ¬›μ§ηνι¿ι⊞υ⌊Ｅι⊟κ»≔⟦⟧ζＷ⁻υζＦ№υ⌊ι⊞ζ⌊ιＩＬΦζ¬›Σ…ζ⊕κ↨η⁰

```

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

```
Ｆθ«

```

Loop over the presents.

```
≔Ｅ³Ｅ³§ι⁺κμι

```

Rotate them 120° and 240° around a corner.

```
≔Φ⁺ιＥι⮌κ⬤κ¬›μ§ηνι

```

Also rotate them 180° around their length axis, then filter on which orientations fit in the chimney.

```
¿ι⊞υ⌊Ｅι⊟κ

```

If there were any then push the shortest such orientation to the predefined empty list.

```
»≔⟦⟧ζＷ⁻υζＦ№υ⌊ι⊞ζ⌊ι

```

Sort the list of heights.

```
ＩＬΦζ¬›Σ…ζ⊕κ↨η⁰

```

Find the maximum number of presents that will fit.

# Answer
> 2 votes
# JavaScript (Node.js)<sup>*</sup>, 128 bytes

** This code relies on a specific implementation of `sort()`. The engine used on TIO is Node 11.6.0. This was also succesfully tested with Node 16.14.0.*

*-4 thanks to @tsh*

Expects `(w,l,h,a)` where `w,l,h` are the dimensions of the chimney and `a` is the list of dimensions for the presents.

```
(w,l,h,a)=>a.map(a=>(g=H=>m=n?([W,L,H]=a.sort(_=>-40%n--),W>w|L>l|H>g()?m:H):1/0)(n=42)).sort((a,b)=>a-b).map(v=>n+=(h-=v)>=0)|n

```

Try it online!

### How?

The way we generate the 6 possible rotations of a present is very hackish but pretty short. It basically goes like that:

```
for(let n = 42; n;) {
  a.sort(_ => -40 % n--);
}

```

The callback function of `sort()` ignores its arguments, making the sort independent of the content of the array. The result is solely based on the current value of \\$n\\$, which is decremented after each iteration. More specifically, we get either \\$0\\$ if \\$n\in\\{1,2,4,5,8,10,20,40\\}\\$ or a negative integer otherwise.

The constants \\$-40\\$ and \\$42\\$ were chosen such that all distinct rotations are eventually generated *and* we end up with exactly \\$n=0\\$ when the last one has been processed.

You can follow this link to see the different steps of the process.

# Answer
> 2 votes
# 05AB1E, 21 bytes

```
εœʒ@¨P}€θß}²Oª{ηÅΔO‹θ

```

Try it online!

*+2 bytes: fixed a bug found by Jonathan Allan*

Assumes that all chimney dimensions are positive.

```
εœʒ@¨P}€θß}
ε         } # map over boxes
 œ          #   permutations (all possible rotations)
  ʒ   }     #   filter:
   @¨P      #     first two dimensions are less than or equal to the
                  first two dimensions of the chimney
       €θ   #   for each get last element (the height)
         ß  #   minimum

```

This gets a list of the smallest height you can get by rotating the box in a way that fits the chimney or "" if it doesn't fit at all.

```
²Oª{ηÅΔO‹θ
²Oª        # append sum of the second input to the list
   {       # sort
    η      # prefixes
     ÅΔ    # get the index of the first element such that:
       O‹θ #   the sum is greater than the last element of second input

```

The sum of the second input is there to guarantee that there is a prefix with larger sum than the height of the chimney.

# Answer
> 0 votes
# Japt `-h`, 28 bytes

```
Ëá fÈÅí§NÅ eÃmÎÍÎÃÍËT±Z§(XµD

```

Try it

```
Ëá fÈÅí§NÅ eÃmÎÍÎÃÍËT±Z§(XµD     :Implicit input of array U=presents and integers V=width, W=depth & X=height
Ë                                :Map U
 á                               :  Permutations
   f                             :  Filter by
    È                            :  Passing each through a function
     Å                           :    Slice off first element
      í                          :    Interleave with
        N                        :      Array of all inputs
         Å                       :      Slice off first element (X is ignored)
       §                         :      Reducing each pair by <=
           e                     :    All true?
            Ã                    :  End filter
             m                   :  Map
              Î                  :    First element (present height)
               Í                 :  Sort
                Î                :  First element
                 Ã               :End map
                  Í              :Sort
                   Ë             :Map each D
                    T±           :  Increment T (initially 0) by
                      Z          :    0
                       §(        :    <=
                         XµD     :    X, decremented by D
                                 :Implicit output of last element

```

# Answer
> 0 votes
# Pyth, 29 bytes

```
K_EsmghK=+Zhhd_#SmSf.AtgVKT.p

```

Try it online!

### Explanation

Uses a simple greedy algorithm, always choosing the shortest present until no more fit.

```
K_EsmghK=+Zhhd_#SmSf.AtgVKT.pdQ    # implicitly add dQ to the end
                                   # implicitly assign Q = eval(input())
K_E                                # assign K to the second input reversed
                 m            Q    # map Q over lambda d
                   f       .pd     # filter permutations of d over lambda T
                       gVKT        # vectorize >= over K and T
                    .At            # true if the last two element are true (we've now filtered out orientations which don't fit in the chimney)
                  S                # sort (this orders the orientations from shortest to tallest)
                S                  # sort (this orders our presents shortest to tallest)
              _#                   # filter out empty lists (avoids indexing errors)
   s                               # sum of
    m                              # map over lambda d
     ghK                           # first element of K is greater than or equal to
        =+Zhhd                     # Z, assigned to Z + first element of the first element of d

```

---
Tags: code-golf, 3d, packing
---


# Question
Title: CGAC2022 Day 22: Present stack headache, Part 2
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

Santa has a bunch of presents wrapped in cuboid boxes of various sizes. As his sled flies above a chimney, a stack of presents will be automatically dropped through it. Santa wants to carefully choose the presents so that all of them fit into a rectangular chimney.

All presents must be center-aligned due to *magical physics* issues (i.e. placing two small presents side-by-side is not allowed). The presents can be rotated, but four of the faces must be parallel to that of the chimney. A present fits in the chimney if both its width and length are `<=` those of chimney after rotation.

On second thought, Santa decides that choosing the maximum number of presents is not great, because a single large present is more valuable than a bunch of tiny ones.

## Task

Given the dimensions of the presents and the chimney, determine the maximum **volume** of presents that fit in the chimney (i.e. sum of the presents' heights is `<=` that of the chimney). All dimensions are positive integers.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Presents and chimney are given as `[width, length, height]`.

```
Presents: [[6, 6, 4], [2, 2, 2], [2, 2, 2], [2, 2, 2]]
Chimney: [6, 6, 6]
Answer: 152
Explanation: Use the large box and a small cube.

Presents: [[6, 10, 9], [10, 7, 6], [10, 7, 5], [10, 7, 4], [5, 10, 10]]
Chimney: [6, 5, 999]
Answer: 0
Explanation: No present fits in the chimney

Presents: [[1, 2, 6], [1, 6, 2], [2, 1, 6], [2, 6, 1], [6, 1, 2], [6, 2, 1]]
Chimney: [2, 6, 6]
Answer: 72 (=6*(1*2*6))
Explanation: All six presents can be rotated to [2, 6, 1],
which fits the chimney and takes up only 1 unit of height

Presents: [[1, 2, 6], [1, 6, 2], [2, 1, 6], [2, 6, 1], [6, 1, 2], [6, 2, 1]]
Chimney: [1, 6, 6]
Answer: 36
Explanation: All six presents can be rotated to [1, 6, 2]

Presents: [[1, 2, 6], [1, 6, 2], [2, 1, 6], [2, 6, 1], [6, 1, 2], [6, 2, 1]]
Chimney: [1, 3, 13]
Answer: 24
Explanation: All six presents can be rotated to [1, 2, 6]

```

# Answer
# Python 3, 180 bytes

```
lambda W,L,H,c:max(sum(h*w*l for h,w,l in a[::2])for a in P(c+[[0]*3]*len(c))if sum(min(h+H*(w>W or l>L)for h,w,l in P(b))for b in a[::2])<=H)
from itertools import*
P=permutations

```

Try it online!

It works on first two testcases. But It sadly timeout for third one.

\\$O((2N+1)!)\\$ solution, where \\$N\\$ is the number of presents.
> 3 votes

# Answer
# JavaScript (Node.js)<sup>*</sup>, 153 bytes

** This code relies on a specific implementation of `sort()`. The engine used on TIO is Node 11.6.0. This was also succesfully tested with Node 16.14.0.*

Expects `(w,l,h,a)` where `w,l,h` are the dimensions of the chimney and `a` is the list of dimensions for the presents.

```
f=(w,l,h,a,V=o=0)=>a.map((b,i)=>f(w,l,h-(g=H=>m=n?([W,L,H]=b.sort(_=>-40%n--),W>w|L>l|H>g(v=W*L*H)?m:H):1/0)(n=42),a.filter(_=>i--),V+v),h<0|V<o?0:o=V)|o

```

Try it online!

Just like my answer to the previous challenge, this is sponsored by the Ministry of Silly Sorts.
> 3 votes

# Answer
# Python3, 221 bytes:

```
lambda c,p:max(max(f(c,[*i]))for i in P(p,len(p)))
from itertools import*
P=permutations
def f(c,p,H=0,v=0):
 yield v
 if p:
  for w,l,h in P(p[0],3):
   if c[0]>=w>0<l<=c[1]and H+h<=c[2]:yield from f(c,p[1:],H+h,w*l*h+v)

```

Try it online!
> 1 votes

# Answer
# Charcoal, 80 bytes

```
Ｆθ«≔Ｅ³Ｅ³§ι⁺κμζ≔Φ⁺ζＥζ⮌κ⬤κ¬›μ§ηνζ¿ζ⊞υ⟦Πι⌊Ｅζ⊟κ⟧»Ｉ⌈ＥΦＥＸ²ＬυΦυ﹪÷ιＸ²μ²¬›↨Ｅι⌊λ¹↨η⁰↨Ｅι⌈λ¹

```

Try it online! Link is to verbose version of code. Explanation: Based on my answer to CGAC2022 Day 21: Present stack headache.

```
Ｆθ«

```

Loop over the presents.

```
≔Ｅ³Ｅ³§ι⁺κμι

```

Rotate them 120° and 240° around a corner.

```
≔Φ⁺ιＥι⮌κ⬤κ¬›μ§ηνι

```

Also rotate them 180° around their length axis, then filter on which orientations fit in the chimney.

```
¿ζ⊞υ⟦Πι⌊Ｅζ⊟κ⟧

```

If there were any then push the shortest such orientation to the predefined empty list along with the volume of the present.

```
»Ｉ⌈ＥΦＥＸ²ＬυΦυ﹪÷ιＸ²μ²¬›↨Ｅι⌊λ¹↨η⁰↨Ｅι⌈λ¹

```

Generate the powerset of the list of presents that fit, filter on those whose height fits in the chimney, and output the maximum volume.
> 1 votes

# Answer
# Pyth, 38 bytes

```
K_EeSmsm*FkdfghKshMTyhM_#SmSf.AtgVKT.p

```

Try it online!

### Explanation

Picks the shortest orientation for each present, then looks at all possible sets of presents and picks the highest volume one which fits.

```
K_EeSmsm*FkdfghKshMTyhM_#SmSf.AtgVKT.pdQ    # implicitly add dQ to the end
                                            # implicitly assign Q = eval(input())
K_E                                         # assign K to the second input reversed
                          m            Q    # map Q over lambda d
                            f       .pd     # filter permutations of d over lambda T
                                gVKT        # vectorize >= over K and T
                             .At            # true if the last two element are true (we've now filtered out orientations which don't fit in the chimney)
                           S                # sort (this orders the orientations from shortest to tallest)
                         S                  # sort (this orders our presents shortest to tallest)
                       _#                   # filter out empty lists (avoids indexing errors)
                     hM                     # map each element to the first element of itself
            f       y                       # filter the power set over lambda T
             ghKshMT                        # first element of K >= sum of the first element(s) of T (leaving only sets of presents that fit)
     m                                      # map over lambda d
      s                                     # sum of
       m   d                                # map d over lambda k
        *Fk                                 # k reduced on multiplication (we've now mapped the sets to their volumes)
   eS                                       # take the largest element

```
> 0 votes

---
Tags: code-golf, 3d, packing
---


title: How predictable is popular music?

text:
# Question
Title: How predictable is popular music?
The McGill Billboard Project annotates various audio features of songs from a random sample of the Billboard charts. I scraped this data to produce the following file of chord progressions:

`chords.txt`

Write the shortest code that outputs the above file (or its contents).

**Edit:** Here's a quick description of the notation to get you started:

* `N` denotes no chord.
* `A:min` denotes the A minor triad chord.
* `C#:sus4(b7,9)` and other spicy chords are completely described here.

# Answer
# Java (JDK), ~~295709~~ 47044 (gzipped file) + 943 (code) + 1 (file) + 67 (imports) = 48055 bytes

Examining the file manually (with some help from notepad++), I found that there were 976 unique entries in the file, formed of 36 unique characters (plus newlines):

`#(),/123456789:ABCDEFGNXabdghijmnsu`

I then looked for common patterns, and created a dictionary as follows (key = value):

> `:maj = ¬`
> `:min = ``
> `\r\nA = "`
> `\r\nB = £`
> `\r\nC = $`
> `\r\nD = %`
> `\r\nE = ^`
> `\r\nF = &`
> `\r\nG = *`
> `\r\nN = _`
> `\r\nX = -`
> `:sus = +`
> `:hdim = =`
> `:dim = [`
> `(9) = }`
> `(#9) = ]`
> `:7 = {`
> `:5 = ~`
> `:aug = ;`
> `#11 = @`
> `b7 = '`
> `maj7 = <`
> `b13 = >`
> `:11 = ?`
> `(11) = \`
> `b:9 = Z`
> `¬^¬ = H`
> `¬%¬ = I`
> `¬$¬ = J`
> `¬"¬ = K`
> `£b¬ = L`
> `¬*¬ = M`
> `b¬"b = O`
> `¬&¬ = P`
> `b¬^b = Q`
> `+4(', = R`
> `¬£ = S`
> `+4(') = T`
> `%b¬ = U`
> `£`£ = V`
> ``7%`7 = W`
> `7"` = Y`
> `"b{] = c`
> `*`7 = e`
> `:13^b = f`
> ``7$ = k`
> `%` = l`
> `^` = o`
> `"` = p`
> `b`7^ = q`
> `b{% = r`
> `cc = t`
> `oo = v`
> `&#~ = w`
> `__ = x`
> `YY = y`
> `&#¬ = z`

I then find-and-replace using those items in order:

```
()->{String s = "A LONG STRING THAT I CAN'T PASTE HERE - SEE TIO LINK";
		String[] d=new String[]{"&#¬","z","YY","y","__","x","&#~","w","oo","v","cc","t","b{%","r","b`7^","q","\"`","p","^`","o","%`","l","`7$","k",":13^b","f","*`7","e","\"b{]","c","7\"`","Y","`7%`7","W","£`£","V","%b¬","U","+4(')","T","¬£","S","+4(',","R","b¬^b","Q","¬&¬","P","b¬\"b","O","¬*¬","M","£b¬","L","¬\"¬","K","¬$¬","J","¬%¬","I","¬^¬","H","b:9","Z","(11)","\\",":11","?","b13",">","maj7","<","b7","'","#11","@",":aug",";",":5","~",":7","{","(#9)","]","(9)","}",":dim","[",":hdim","=",":sus","+","\r\nX","-","\r\nN","_","\r\nG","*","\r\nF","&","\r\nE","^","\r\nD","%","\r\nC","$","\r\nB","£","\r\nA","\"",":min","`",":maj","¬"};
		for (int i=0;i<d.length;i+=2){s=s.replace(d[i+1],d[i]);}return s;}

```

TIO (sort of).

**EDIT**

By compressing the string, as suggested in the comments, this answer can then be made shorter.

Using the GZIPped version of the string in a file "f" (size 45708 bytes), the code can then be as follows:

`import java.io.*;
import java.nio.file.*;
import java.util.zip.*;
()->{String s="",l;try{BufferedReader b=new BufferedReader(new InputStreamReader(new GZIPInputStream(new ByteArrayInputStream(Files.readAllBytes(Paths.get("f"))))));while((l=b.readLine())!=null){s+=l;}}catch(Exception e){}String[] d=new String[]{THE SAME DICTIONARY AS THE PREVIOUS CODE - REDACTED HERE TO MAKE ANSWER SHORT ENOUGH};for (int i=0;i<d.length;i+=2){s=s.replace(d[i+1],d[i]);}return s;}`
> 4 votes

# Answer
# Python 3, 969 + 36208 (size of data file) = 37177 bytes

A mix of encoding and traditional compression. I store each of the roots (the "letters") and index into an array to find them, then, if it's not N, X or the empty string (which don't have a "chord type" (combination of the quality and other stuff tacked on the end) and are immediately followed by a newline), I use the next byte to index a table of the "chord types".

The data file (named "b") is available on my GitHub.

```
import base64,zlib,io
x,y=eval(zlib.decompress(base64.decodebytes(b"eNocyAEGgEAYBtGrxIc/7CWqKiAAsYLuf4jsg2dM71VtqgXhN1whN4TGjtA4IE+ExoXQuAdPva3XnJ+q+sAVI4SBAHqXdCQkC4xxOM53eu/3T3axB0dl5w3bu5SrvWgtsi4XF5q3uHhQD/BG1T3LOLKaFjI9rZ4tmvwroGnl/wuZ7K4+jk01anfsKV9TuSfXUW7YkR5QP+RDcWIH4gvS2CE75o69zJ68eNxacS0HRvwgXMRwxbKWQHw4DuXQerKGqx/DLtgp9R28Y+yQHXOHdU/2HJ7iqVeue+KneqkxUM+oxTDxDrni4c87jxdaQgsyzSQ+pWKhvaHXH7547D1t0+MR0oB1iCGB1IWkDu0V3l8GaBwaJwvsG/3y8NHDL5Z7gT7qpJGLabRVjqgnc7IkT7jmHdsK0uMR6gEOjIAEZkAD1iGGBiTQhBTCYGPHjHyh5dAP3uvKJM5FUExLcs3r24KpQwwNSKAJXafkUh9E4u6iEJ8q5Xgdm6alqEMMDUggda3IvG9/E+Ga5xFD49aHrx77KQRp5KK5WGp1YaUskuSZrMmGYo2Lm3qAAyMggRnQgDE0IYVeQhhsDSA5NE7WMDtmpF9wLwrmc5/UIYGwA41MV17zpVDq0IAEmpD1Qz5U54rMW1/UoQEJZHyozv24g1j6PJS//vzqkX6NvJjC1CGGxDUi/YFykqJY42pa0LPxP0cbuWEvu5mi4teChg2hS+74qKaRxhigDg1IIIVM/049NpYLAINXQ3I=")))
f=io.BytesIO(zlib.decompress(open("b","rb").read()))
while 1:
 a=x[f.read(1)[0]];print(a if not a or a in"NX"else a+y[f.read(1)[0]])

```

Edit: I decided not to be lazy after all and go Google correct music terms.
> 3 votes

# Answer
# Python 3, 23 + 802213 (size of file we want to reproduce) + 1

Quite a naïve answer IMO

```
lambda s:open(s).read()

```

This function takes as argument the file we want to reproduce and then prints it xD

Scoring as per this meta answer, linked by @Arnauld
> 1 votes

# Answer
# MATLAB, 55935 = 10 + 55924 + 1

Compress the text file as a 55924-byte zip file `c` and then run the code

`unzip('c')`

We add a byte to the score to account for the extra file.
> 1 votes

# Answer
## Python 3: 93943 = 91,752 + 1990 + 1

This is my messy attempt at a compression. Sadly still worse than simply zipping the file though XD.

The information density of the file is not as great as it seems and there were several observable redundancies. Because of that I have doubts that there is a reasonable way to predict the data. I am prepared to be wrong though :-). The code by itself is not golfed that much, since the main portion of the cost is the size of the compressed files. The decompressor is only 1990 bytes long. The compression itself is done by Two separate huffman trees, implied ":" between them and two one-bit streams that act as a guides. Also there are few simple substitutions in place.

1. First huffman tree codes the first letter
2. Second huffman tree codes the portion that follows the ":"
3. First bit file (a) codes whether the line before the ":" consists of 0-1 or 2 characters
4. Second bit file (u) codes whether the second character before : is "b" or "#"

Lastly, all the files are compressed via zip since on my work computer we don't have anything else. Might try other compressors later on. zip-input This archive has to be in programs working directory.

The code itself is tied tightly to the file. It does not cover full format specifications listed by the author of the question. (Also, I have hard-coded the input file size into the decoder - after I missed the proper termination one times too many.) There is definitely a room for improvements - for example few more substitutions tied to the numbers in brackets.

There might be a missing trailing newline in the output, that I somehow keep missing while trying to debug.

**Huffman tree generator:**

```
import heapq as h
import numpy as np
from bitarray import bitarray

class List:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.leftSon = None
        self.rightSon = None

    def __lt__(self, other):
        return self.freq < other.freq

    def check(self,arr,  prefix):
        if self.char is not None:
            arr.append((self.char, prefix))
        else:
            self.leftSon.check(arr, prefix + "0")
            self.rightSon.check(arr, prefix + "1")

    def encode(self):
        if self.char is None:
            toRet = "0"
            toRet += self.leftSon.encode()
            toRet += self.rightSon.encode()
        else:
            toRet = "1" + np.binary_repr(ord(self.char), 8)
        return toRet

class HuffmanTree:
    def __init__(self, inputList):
        a = []
        for x in inputList:
            h.heappush(a, List(x[0], x[1]))
        while len(a) > 1:
            first = h.heappop(a)
            second = h.heappop(a)
            new = List(None, first.freq + second.freq)
            new.leftSon = first
            new.rightSon = second
            h.heappush(a, new)
        self.root = a[0]
        self.encodeArray = []
        self.root.check(self.encodeArray, "")
        encodeDict = {}
        for x in self.encodeArray:
            encodeDict[x[0]] = x[1]
        self.encodeDict = encodeDict
        print(self.encodeArray)

    def encodeSelf(self):
        head = self.root
        bits = head.encode()
        x = bitarray()
        for b in bits:
            if b == "0":
                x.append(0b0)
            else:
                x.append(0b1)
        return x

```

**The code to generate the support files:**

```
import huffman
from bitarray import bitarray

a = ""
with open("chords.txt") as chr:
    a = chr.read()

def getCounts(l):
    counts = {}
    for x in l:
        if x in counts.keys():
            counts[x] += 1
        else:
            counts[x] = 1
    res = []
    for x in counts.keys():
        res.append((x, counts[x]))
    return res

def stringToBits(string):
    ret = bitarray()
    for x in string:
        if x =="0":
            ret.append(0b0)
        else:
            ret.append(0b1)
    return ret

lines = a.split("\n")
firstPart = []
secondPart = []
for i in lines:
    a = i.split(":")
    firstPart.append(a[0])
    if len(a) > 1:
        secondPart.append(a[1] + "\n")

###First part
Afile = ""
huffFile = ""
sharpFile = ""

firstPartChars = ""
fChar = []
sChar = []
for x in firstPart:
    firstPartChars += x
    if len(x) == 0:
        fChar.append("\n")
        Afile += "0"
    else:
        fChar.append(x[0])
    if len(x) == 1:
        Afile += "0"
    if len(x) == 2:
        Afile += "1"
        sChar.append(x[1])

print([x for x in set(fChar)])
print([x for x in set(sChar)])

fCharCount = getCounts(fChar)
sCharCount = getCounts(sChar)
firstHuff = huffman.HuffmanTree(fCharCount)
for char in fChar:
    code = firstHuff.encodeDict[char]
    huffFile += code

for char in sChar:
    if char == "b":
        sharpFile += "0"
    elif char == "#":
        sharpFile += "1"
    else:
        raise Exception("error in sharp file")

#######
#####Second part
sPartFile = ""
subs = {}
subs["maj"] = "~"
subs["min"] = "&"
subs["sus"] = "^"
subs["aug"] = "%"
subs["dim"] = "$"
subs["hdi"] = "@"
spPart = []
secSubPart = ""
for x in secondPart:
    c = x.replace("maj", "~").replace("min", "&").replace("sus", "^").replace("aug", "%")\
        .replace("dim", "$").replace("hdim", "@")
    spPart.append(c)
    secSubPart += c
secPartCounts = getCounts(secSubPart)
secondHuff = huffman.HuffmanTree(secPartCounts)
for x in secSubPart:
    sPartFile += secondHuff.encodeDict[x]

aBits = stringToBits(Afile)
huffBits = stringToBits(huffFile)
sharpBits = stringToBits(sharpFile)
sPartBits = stringToBits(sPartFile)
print("test")
with open("a", "wb") as t:
    aBits.tofile(t)
with open("h", "wb") as t:
    huffBits.tofile(t)
with open("u", "wb") as t:
    sharpBits.tofile(t)
with open("f", "wb") as t:
    sPartBits.tofile(t)

with open("i", "wb") as t:
    a = firstHuff.encodeSelf()
    a.tofile(t)
with open("j", "wb") as t:
    b = secondHuff.encodeSelf()
    b.tofile(t)

```

**Finally the code itself:**

```
from bitarray import bitarray as b
import zipfile
with zipfile.ZipFile("h.zip", 'r') as z:
    z.extractall(".")

class N:
    def __init__(s):
        s.c = None
        s.l = None
        s.r = None
    def i(s):
        return s.l == None
    def d(s, r):
        if s.i():
            return s.c
        else:
            if r.b() == 0:
                return s.l.d(r)
            else:
                return s.r.d(r)
class R:
    def __init__(s, bits):
        s.d = bits
        s.i = 0

    def b(s):
        t = s.d[s.i]
        s.i += 1
        return t

    def B(s):
        toRet = s.d[s.i:s.i + 8]
        s.i += 8
        return toRet

def rn(r):
    if r.b() == 1:
        n = N()
        n.c = r.B().tostring()
    else:
        left = rn(r)
        right = rn(r)
        n = N()
        n.l = left
        n.r = right
    return n

def bff(i):
    with open(i, "rb") as f:
        c = b()
        c.fromfile(f)
        return c

def huffRead(a):
    c = bff(a)
    r = R(c)
    n = rn(r)
    return n

fh = huffRead("i")
fp = R(bff("h"))
sh = huffRead("j")
sp = R(bff("f"))
af = R(bff("a"))
bp = R(bff("u"))

ft = ""
test = open("test", "w")
i=0
while i < 125784:
    i += 1
    tp = ""
    n = "\n"
    s = "#"
    b = "b"
    t = fh.d(fp)
    spr = True
    if af.b() == 0:
        if t == n:
            tp += t
            spr = False
        elif t == "N" or t == "X":
            tp += t + n
            spr = False
        else:
            tp += t + ":"
    else:
        tp += t
        if bp.b() == 1:
            tp += s + ":"
        else:
            tp += b + ":"
    if spr:
        x = sh.d(sp)
        while x != n:
            tp += x
            x = sh.d(sp)

        tp += x
    tp = tp.replace("~", "maj").replace("&", "min").replace("^", "sus")\
        .replace("%", "aug").replace("$", "dim").replace("@", "hdim")
    ft += tp
print(ft)

```
> 1 votes

# Answer
# bash, 802213 + 5 + 1 = 802219 bytes

```
cat<b

```

With a file named `b` containing the contents of `chords.txt`.
> 0 votes

# Answer
# Bash, 39098 bytes

```
xz -c -d a

```

Try it online!

General compressing tool, also make them able to find source
> 0 votes

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