# Question
Title: Impress Donald Knuth by counting polyominoes on the hyperbolic plane
This challenge is inspired by a talk about Schläfli symbols, etc that I gave in a Geometry seminar. While I was putting together this challenge, I saw that Donald Knuth himself was interested in (some subset of) this problem. In October 2016, he commented on a related OEIS sequence:

> If \[the OEIS author\] is wrong about the hyperbolic {4,5} pentominoes, the next number is probably mistaken too. I don't have \[time\] right now to investigate further.

Successful completion of this challenge will have you investigating something that Donald Knuth might have investigated if only he had more time, and will result in new additions (and perhaps a rare correction) to the On-Line Encyclopedia of Integer Sequences.

---

# Challenge

This challenge will have you create a function that counts "free polyforms" on the hyperbolic plane. In particular, you will write a function that takes three positive integer parameters `p`, `q`, and `n` and counts the number of \\$n\\$-cell "free polyforms" on the tiling of the hyperbolic plane given by the Schläfli symbol \\$\\{p,q\\}\\$.

Shortest code wins.

---

# Definitions

The Schläfli symbol \\$\\{p,q\\}\\$ describes a tiling of the hyperbolic plane by \\$p\\$-gons, where each vertex touches exactly \\$q\\$ of the polygons. As an example, see the Wikipedia page for the \\$\\{4,5\\}\\$ tiling that Donald references above.

A free polyform is a collection of regular polygons that meet at their edges, counted up to rotation and reflection.

---

# Input

You can assume that the values of `p` and `q` which define the tiling indeed describe an actual tiling of the hyperbolic plane. This means that \\$p \geq 3\\$, and

* when \\$p = 3\\$, \\$q \geq 7\\$,
* when \\$p = 4\\$, \\$q \geq 5\\$,
* when \\$p = 5\\$, \\$q \geq 4\\$,
* when \\$p = 6\\$, \\$q \geq 4\\$, and
* when \\$p \geq 7\\$, \\$q \geq 3\\$.

---

# Data

OEIS sequence A119611 claims that `f(4,5,n) = A119611(n)`, but Donald Knuth disputes the reasoning for the value of \\$A119611(5)\\$. (When I counted by hand, I got Knuth's answer, and I've included it in the table below.)

| \\$p\\$ | \\$q\\$ | \\$n\\$ | \\$f(p,q,n)\\$ |
| --- | --- | --- | --- |
| 3 | 7 | 1 | 1 |
| 3 | 7 | 2 | 1 |
| 3 | 7 | 3 | 1 |
| 3 | 7 | 4 | 3 |
| 3 | 7 | 5 | 4 |
| 3 | 7 | 6 | 12 |
| 3 | 7 | 7 | 27 |
| 3 | 9 | 8 | 82 |
| 4 | 5 | 3 | 2 |
| 4 | 5 | 4 | 5 |
| 4 | 5 | 5 | 16 |
| 6 | 4 | 3 | 3 |
| 7 | 3 | 1 | 1 |
| 7 | 3 | 2 | 1 |
| 7 | 3 | 3 | 3 |
| 8 | 3 | 3 | 4 |
| 9 | 3 | 3 | 4 |

Note: these values are computed by hand, so let me know if you suspect any mistakes.

# Final notes

The output of this program will result in quite a lot of new, interesting sequences for the OEIS. You are of course free to author any such sequences—but if you're not interested, I'll add the values you compute to the Encylopedia with a link to your answer.

# Answer
# GAP and its kbmag package, ~~711 682~~ 658 bytes

Note that the `kbmag` package consists not only of GAP code, it contains C programs that have to be compiled (see the package's `README` file).

```
LoadPackage("kbmag");I:=function(p,q,n)local F,H,R,r,s,x,c;F:=FreeGroup(2);s:=F.1;r:=F.2;R:=KBMAGRewritingSystem(F/[s^2,r^p,(s*r)^q]);AutomaticStructure(R);H:=SubgroupOfKBMAGRewritingSystem(R,[r]);AutomaticStructureOnCosets(R,H);x:=w->ReducedCosetRepresentative(R,H,w);c:=function(n,U,S,P)local N,Q,Z;if n=0 then Z:=Set(U,t->Set(U,p->(p/t)));return 1/Size(SetX(Union(Z,Set(Z,Q->Set(Q,q->(MappedWord(q,[s,r],[s,r^-1]))))),[1..p],{Q,i}->Set(Q,q->x(q*r^i))));fi;if P=[]then return 0;fi;N:=P[1];Q:=P{[2..Size(P)]};Z:=Filtered(Set([1..p],i->x(s*r^i*N)),w->not w in S);return c(n,U,S,Q)+c(n-1,Union(U,[N]),Union(S,Z),Union(Q,Z));end;return c(n,[],[r/r],[r/r]);end;

```

This is the result of removing indentation and newlines from this version, and some inlining:

```
LoadPackage("kbmag");
I:=function(p,q,n)
  local F,G,H,R,r,s,x,c;
  F:=FreeGroup(2);
  s:=F.1;r:=F.2;
  G:=F/[s^2,r^p,(s*r)^q];
  R:=KBMAGRewritingSystem(G);
  AutomaticStructure(R);
  H:=SubgroupOfKBMAGRewritingSystem(R,[r]);
  AutomaticStructureOnCosets(R,H);
  x:=w->ReducedCosetRepresentative(R,H,w);
  c:=function(n,U,S,P)
    local N,Q,Z;
    if n=0 then
      Z:=Set(U,t->Set(U,p->(p/t)));
      Z:=Union(Z,Set(Z,Q->Set(Q,q->(MappedWord(q,[s,r],[s,r^-1])))));
      Z:=SetX(Z,[1..p],{Q,i}->Set(Q,q->x(q*r^i)));
      return 1/Size(Z);
    fi;
    if P=[]then return 0;fi;
    N:=P[1];Q:=P{[2..Size(P)]};
    Z:=Filtered(Set([1..p],i->x(s*r^i*N)),w->not w in S);
    return c(n,U,S,Q)+c(n-1,Union(U,[N]),Union(S,Z),Union(Q,Z));
  end;
  return c(n,[],[r/r],[r/r]);
end;

```

If the line containing `{Q,i}->` doesn't work, your GAP is too old. You can then replace that line with:

```
Z:=SetX(Z,[1..p],function(Q,i)return Set(Q,q->x(q*r^i));end);

```

Several of the `Set` operations could be slightly faster `List` operations (the improved version at least uses that it is a set for even more golfing *and* a little speed compensation), but that would cost one byte each time.

And yes, Knuth's and your result is confirmed:

```
gap> Read("i.gap");
─────────────────────────────────────────────────────────────────────────────
Loading  kbmag 1.5.9 (Knuth-Bendix on Monoids and Automatic Groups)
by Derek Holt (https://homepages.warwick.ac.uk/staff/D.F.Holt/).
Homepage: https://gap-packages.github.io/kbmag
─────────────────────────────────────────────────────────────────────────────
gap> I(4,5,5);
16
gap> I(4,5,6);
55
gap> I(4,5,7);
224
gap> I(4,5,8);
978
gap> I(4,5,9);
4507
gap> I(4,5,10);
21430

```

The \\$n=7\\$ computation already takes several minutes. My computations also agree with the other results in the table.
> 11 votes

# Answer
# bc, ~~673~~ 670 bytes

-3 bytes thanks to *@ceilingcat*

```
define y(){t[z=u[x[++n]=e]/p]=1;for(o=p;o--;){if(!u[a=z*p+o]){v(u[u[a]=c=s]=a);s+=p;v(c)}}}define j(e,i){return(e%p+p+i)%p+e/p*p}define v(e){auto l;for(l=j(e,b=1);y=u[e];++b){e=j(y,-1)};for(;y=u[l];++b){l=j(y,1)};if(b==q)v(u[u[l]=e]=l)}p=read();q=read();g=read();u[e=s=2*p]=p;y();e=p;for(y();e==p;){while(n-1){if(t[e/p]*!t[u[e]/p]){c=y();for(o=6;o-=2;){for(d=s;d--;){i[a=w=2]=f=u[d];if(t[d/p]*t[f/p]){i[b=1]=d;m[d/p]=m[f/p]=++r;for(z=0;w-z++;){for(f=i[z];f=j(f,o-3)!=i[z];a*=2){if(t[y=u[f]/p]){b+=a;if(m[y]<r){i[++w]=u[f];m[y]=r}}}};if(c<b)c=b}}};for(k[h]=c;k[o++]-c;){};if(o>h){++h;if(n<g){e=p;break};++l};t[u[e]/p]=0;--n};while(++e>s){t[u[e=x[n--]]/p]=0}}};l;if(g<3)1

```

Try it online!

This is a golfed version of the C code I'm about to post. Here, you have to supply the parameters (p, q and n) on standard input when bc is running. The code spits out lots of numbers while it calculates (because statements such as i+=1 are silent, but ++i is a value and is printed) -- the answer is the final number.

n\<3 has to be handled as a special case. Infinite planar grids are handled OK (which gives us lots of test cases). Finite grids (the Platonic solids, but also p=2 and/or q=2) are not handled reliably.

Here we are counting "free" polyominoes, unique up to translation, rotation and reflection. If you had asked the same question but disallowing reflection, I could have saved a few bytes and even beaten Christian's excellent answer as it stands. (I don't know if that answer would be shorter for the not-free question.) Here's the not-free code: Try it online! (~~655~~ 652 bytes, answering a different question).

Here's the main code unwrapped:

```
 define y(){
 t[z=u[x[++n]=e]/p]=1;
 for(o=p; o--;){
  if(!u[a=z*p+o]){
   v(u[u[a]=c=s]=a);
   s+=p;
   v(c)
  }
 }
}
define j(e,i){
 return(e%p+p+i)%p+e/p*p
}
define v(e){
 auto l;
 for(l=j(e,b=1); y=u[e]; ++b){
  e=j(y,-1)
 };
 for(; y=u[l]; ++b){
  l=j(y,1)
 };
 if(b==q)v(u[u[l]=e]=l)
}
p=read();
q=read();
g=read();
u[e=s=2*p]=p;
y();
e=p;
for(y(); e==p;){
 while(n-1){
  if(t[e/p]*!t[u[e]/p]){
   c=y();
   for(o=6; o-=2;){
    for(d=s; d--;){
     i[a=w=2]=f=u[d];
     if(t[d/p]*t[f/p]){
      i[b=1]=d;
      m[d/p]=m[f/p]=++r;
      for(z=0; w-z++;){
       for(f=i[z]; f=j(f,o-3)!=i[z]; a*=2){
        if(t[y=u[f]/p]){
         b+=a;
         if(m[y]<r){
          i[++w]=u[f];
          m[y]=r
         }
        }
       }
      };
      if(c<b)c=b
     }
    }
   };
   for(k[h]=c; k[o++]-c;){
   };
   if(o>h){
    ++h;
    if(n<g){
     e=p;
     break
    };
    ++l
   };
   t[u[e]/p]=0;
   --n
  };
  while(++e>s){
   t[u[e=x[n--]]/p]=0
  }
 }
};
l;
if(g<3)1

```
> 3 votes

# Answer
# C (gcc), ~~753~~ ~~745~~ 705 bytes

-8 bytes thanks to *@ceilingcat*

-40 bytes, *@ceilingcat* strikes again!

```
#define X[99999]
#define S o=p;F[z=N[O[++n]=e]/p]=1 W o--)N[a=z*p+o]||v(c,s+=p,v(N[N[a]=c=s]=a))
#define W;while(
#define T atoi(*++V)
long C X,a,b,c,p,q,o,N X,F X,s,O X,A,n,P,e,m X,Q X,d,f,j,w,z,r;I(e,i){return(e%p+p+i)%p+e/p*p;}v(e,l){l=I(e,b=1)W N[e])++b,e=I(N[e],-1)W N[l])l=I(N[l],1),++b;b-q||v(N[N[l]=e]=l);}main(M,V)int**V;{p=T;q=T;M=T;N[e=s=2*p]=S;e=S;G:e=p W~-n){if(F[e/p]&!F[N[e]/p]){S;c=0;o=4 W o){d=s W d--)if(F[d/p]&F[(Q[a=w=2]=j=N[d])/p]){Q[b=1]=d;m[d/p]=m[j/p]=++r;z=0 W w-z++){f=Q[z]W(f=I(f,o-3))-Q[z])j=N[f],F[j/p]&&m[b+=a,j/p]<r?Q[++w]=j,m[j/p]=r:0,a+=a;}c=c<b?b:c;}o-=2;}C[P]=c W C[o++]-c);if(o>P){++P;if(n<M)goto G;++A;}F[N[e]/p]=0;--n;}W++e>s)F[N[e=O[n--]]/p]=0;}printf("%d",M<3?:A);}

```

Try it online!

Parameters p, q and n are supplied as command-line arguments.

The array C\[99999\] contains a characteristic value for each polyomino found, of the specified size and all smaller (down to n=2). For p less than 7 or 8 or so, this is probably the limit on how far you can go up a sequence. For larger p, you might well run out of edges, for example in the array N\[99999\]. There is also a constraint that the characteristic values need (p-1)\*n bits, and here we are using 63ish bits. If we stick to unambitious values of p, q and n, I could save a handful of bytes with int and 9999. If you exceed any of the limits, there is no error trapping.

Here's the code unwrapped, but it's still fairly dense:

```
#define X[99999]
#define S o=p;F[z=N[O[++n]=e]/p]=1;while(o--)N[a=z*p+o]||v(c,s+=p,v(N[N[a]=c=s]=a))
#define T atoi(*++V)
long C X,a,b,c,p,q,o,N X,F X,s,O X,A,n,P,e,m X,Q X,d,f,j,w,z,r;
I(e,i){
  return(e%p+p+i)%p+e/p*p;
}
v(e,l){
  l=I(e,b=1);
  while(N[e])++b,e=I(N[e],-1);
  while(N[l])l=I(N[l],1),++b;
  b-q||v(N[N[l]=e]=l);
}
main(M,V)int**V;
{
  p=T;
  q=T;
  M=T;
  N[e=s=2*p]=S;
  e=S;
G:e=p;
  while(~-n){
    if(F[e/p]&!F[N[e]/p]){
      S;
      c=0;
      o=4;
      while(o){
        d=s;
        while(d--)if(F[d/p]&F[(Q[a=w=2]=j=N[d])/p]){
          Q[b=1]=d;
          m[d/p]=m[j/p]=++r;
          z=0;
          while(w-z++){
            f=Q[z];
            while((f=I(f,o-3))-Q[z])
              j=N[f],F[j/p]&&m[b+=a,j/p]<r?Q[++w]=j,m[j/p]=r:0,a+=a;
          }
          c=c<b?b:c;
        }
        o-=2;
      }
      C[P]=c;
      while(C[o++]-c);
      if(o>P){
        ++P;
        if(n<M)goto G;
        ++A;
      }
      F[N[e]/p]=0;
      --n;
    }
   ;
    while(++e>s)F[N[e=O[n--]]/p]=0;
  }
  printf("%d",M<3?:A);
}

```

This post seems rather long already, so I'll link to TIO with a copy of ungolfed code with comments. The golfed code uses basically the same approach: Try it online!

In the ungolfed code, if you supply p, q, and n, it will try the size-n problem, then size-(n+1) and so on until something breaks. If limits are exceeded, the program is meant to terminate with a message. You can supply a fourth parameter to cap n.

The ungolfed code should handle finite grids (Platonic solids, or p=2 and/or q=2).

If you want to look at the different question of counts up to translation and rotation only, compile the ungolfed code with -DNOTFREE.

The golfed code can be checked against existing planar values as well as the values in the question. For example:

```
p=4,q=4,    n=11: a000105(11)=17073
p=3,q=99999,n=13: a000207(13)=24834
p=6,q=3,    n=10: a000228(10)=30490
p=3,q=6,    n=14: a000577(14)=26166
p=4,q=99999,n=10: a005036(10)=32721
p=4,q=5,    n=10: a119611(10)=21430

```

Most of these run within TIO's timeout of 60s. In other sequences, such as a330659 {3,7}, the golfed code can replicate and extend the current known values in OEIS:

```
p=3,q=7,    n=10: a330659(10)=  637
p=3,q=7,    n=11: a330659(11)= 1870
p=3,q=7,    n=12: a330659(12)= 5797
p=3,q=7,    n=13: a330659(13)=17866
p=3,q=7,    n=14: a330659(14)=56237

```

The ungolfed code has more checks, uses more memory and runs quicker (because, for example, it uses a hash table rather than a flat array for storing characteristics), so I'll add to the OEIS using that code. For example, extending a330659 to n=19 takes around 1000 seconds:

```
p=3,q=7,    n=14: a330659(14)=56237
p=3,q=7,    n=15: a330659(15)=177573
p=3,q=7,    n=16: a330659(16)=566904
p=3,q=7,    n=17: a330659(17)=1818527
p=3,q=7,    n=18: a330659(18)=5874180
p=3,q=7,    n=19: a330659(19)=19065038

```
> 1 votes

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


title: String-wise calculus (i)

text:
# Question
Title: String-wise calculus (i)
*This will turn into a series involving other aspects of calculus, including using the "derivative" of a string to find "stationary points" etc, as well as "integration" of sentences*

## Introduction

If y'all have ever studied calculus, you'll most likely know that differentiation is limited to differentiable functions.

Not that there's anything wrong with that, but have you ever wondered what it'd be like to take the first (or second) derivative of a word? Or how about a sentence? You probably haven't, so let me explain my theory of string based differentiation.

## The Basics

*If you already know how differentiation works, feel free to skip this part*

When being introduced to the concept of differential calculus, most beginners are taught about the concept of *differentiation from first principles*. This is based on the concept of finding the gradient of a tangent to a curve via the gradient formula:

$$ m = \frac{y\_2 - y\_1}{x\_2 - x\_1} $$

On the tangent, we say that we have two points: \\$(x, f(x))\\$ and \\$(x + h, f(x + h))\\$, where \\$h\\$ is an infinitesimal number. Plugging this into the gradient formula gives:

$$ m = \frac{f(x+h)-f(x)}{x+h-x} = \frac{f(x+h) - f(x)}{h} $$

In order to eliminate any inaccuracies from the tangent's gradient, we take the limit of the above equation as \\$h\\$ approaches `0`, giving us:

$$ \frac{d}{dx}(f(x)) = \lim\_{h\to 0}\left(\frac{f(x+h)-f(x)}{h}\right) $$

Now, you may be asking "how on earth does that apply to string calculus? First-principles uses functions and numbers, not characters!"

Well, for this challenge, I've devised a slightly modified version of the first principles concept. The "formula" we'll be using is:

$$ \frac{d}{dx}(y) = \sum\_{h=-1}^{1}\left(h\left\[y\left\[x+h\right\]-y\left\[x\right\]\right\]\right) = y\left\[x+1\right\]-y\left\[x-1\right\] $$

## The Formula Explained

One of the major differences here is that there is no longer a limit being taken of the equation. That's because it doesn't quite make sense having something approaching 0 for the whole string. Rather, we use a \\$\sum\\$ to inspect the characters to the left and right of the character in question.

Also, inside the sum, the first \\$y\\$ is now being multiplied by the \\$h\\$. This is to ensure that the result is balanced, as without it, the results weren't very reflective of the string.

To evaluate this formula for a certain index \\$x\\$, you:

* Evaluate \\$-y\[x-1\] + y\[x\]\\$
* Evaluate \\$0\\$
* Evaluate \\$y\[x+1\] - y\[x\]\\$
* Summate the above three items.

Essentially, you are calculating the following:

$$ y\[x+1\]-y\[x-1\] $$

Note that when subtracting things, the ordinal values are used. E.g. `c - a` = `99 - 97` = 2

If any position becomes negative, it starts indexing from the back of the string (like python does). If any position becomes greater than the length of the string, the character is ignored.

## Applying Differentiation to the Whole String

By now, you may have noticed that the first principles formula only works on individual characters, rather than the whole string. So, in this section, we will develop a more generalised approach to using the formula.

To apply the formula to the whole string, we get the derivative of each character in the string, convert those numbers to characters based on code point conversion (like python's `chr()` function) and concatenate the results into a single string. Now, the problem here is that results may sometimes be negative. To solve this problem, we will introduce a second string to store information: the sign string.

This string will consist of a combination of any two letters of your choice, representing whether or not a character is positive.

## Worked Example

Let's take a look at what would happen with the word `Code`:

* We start at position `0` (`C`). The three parts for this character are `-(e + C)`, `0` and `o - c`. These evaluate to `-34`, `0` and `44`. The sum of these is `10` and the sign is `+`. So a newline is added to the main string, and a `+` is added to the sign string.
* We then move to position `1` (`o`). The three parts are: `-(o + C)`, `0` and `d - o`. These evaluate to `44`, `0` and `-11`. The sum of these is `33`, so a `!` is added to the main string and a `+` is added to the sign string.
* We then move to position `2` (`d`). The three parts are: `-(o + d)`, `0` and `e - d`. These evaluate to `-11`, `0` and `1`. The sum of these is `-10`, so a new line is added to the main string and a `-` is added to the sign string.
* We finally move to position `3` (`e`). The position `3 + 1` is longer than the length of the string, so therefore, the process ends.

Therefore, the final result is `["\n!\n", "++-"]`

## Test Cases

Format is `input`, newline, `output`. These test cases were generated using Python, and uses UTF-8.

```
Code
('\n!\n', 'ppn')
Code Golf
('\t!\nD\x1eO%\t', 'ppnnnppn')
Cgcc
('\x04 \x04', 'ppn')
Lyxal
('\r,\x18\x0c', 'ppnn')
3 - 3 = 0
('\x10\x06\x00\x06\x00\n\x00\r', 'nnpppppn')
Lim x -> 0
('9!I\x0b\x00K\x1e\r\x0e', 'ppnppnpnn')
lim x -> 0
('9\x01I\x0b\x00K\x1e\r\x0e', 'ppnppnpnn')

('', '')
afanfl;aknsf
('\x00\x00\x08\x05\x02+\x0b0\r\x08\x08', 'ppppnnnpppn')
nlejkgnserg
('\x05\t\x02\x06\x03\x03\x0c\t\x01\x02', 'pnnpnppnnp')
38492
('\x06\x01\x01\x02', 'pppn')
abcdefghijklmnopqrstuvwxy
('\x17\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02', 'nppppppppppppppppppppppp')
KLJBFD
('\x08\x01\n\x04\x02', 'pnnnp')
::::::::::::
('\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00', 'ppppppppppp')
aaa
('\x00\x00', 'pp')
aaaaa
('\x00\x00\x00\x00', 'pppp')

```

## Rules

* Input will be restricted to printable ASCII
* You can use any codepage you like for the output, just so long as it is consistently used. This means that UTF-8, CP437, etc. are fair game.
* Input can be taken in any convenient and reasonable format
* Output can be given in any convenient and reasonable format. Suggested formats include: a list of both strings, each string on a newline, both strings joined together. It's up to you really how you want to output the result.
* Unicode sequences (like `\x00` or `\x05`) can be used in the output if wanted. In other words, both real representations and Unicode control sequences are valid output given they are applied consistently.
* You can use *any* two characters for the string sign. That's right! It doesn't have to be `+` and `-`... it could be `p` and `n` or `3` and `'`. It really doesn't matter as long as you use two distinct characters.
* For this challenge, `0` is considered positive.
    + Both full programs and functions are allowed.

## Scoring

Of course, this is code-golf, so the shortest answer wins!

## Reference Program

Try it online!

## Special Thanks

I'd just like to say a huge thanks to @xnor and @FryAmTheEggman for showing me that my original model of string differentiation was not the best way of doing things. I'm much happier with this new method that you see here!

# Answer
> 3 votes
# 05AB1E, ~~12~~ 11 bytes

```
Ç¤š¥ü+Dd‚Äç

```

-1 byte thanks to *@ExpiredData*.

Uses I/O with UTF-8 encoding like the challenge description, and uses characters `\0` for negative and `\1` for 0 or positive. Outputs as a list of list of characters.

Try it online or verify all test cases (the `J`oin is added to pretty-print the character-lists to strings, but feel free to remove it to see the actual output).

**Explanation:**

```
Ç            # Convert the characters in the (implicit) input-string to their unicode values
             #  i.e. "Code!!!" → [67,111,100,101,33,33,33]
 ¤š          # Prepend its own trailing item (without popping it)
             #  → [33,67,111,100,101,33,33,33]
   ¥         # Pop and push the deltas (forward differences) of this list
             #  → [34,44,-11,1,-68,0,0]
    ü        # For each overlapping pair of differences:
             #   → [[34,44],[44,-11],[-11,1],[1,-68],[-68,0],[0,0]]
     +       #  Sum them together
             #   → [78,33,-10,-67,-68,0]
      D      # Duplicate this list
       d     # Check for each whether it's >=0 (0 if negative; 1 if 0 or positive)
        ‚    # Pair those two lists together
             #  → [[78,33,-10,-67,-68,0],[1,1,0,0,0,1]]
         Ä   # Take the absolute value of each
             #  → [[78,33,10,67,68,0],[1,1,0,0,0,1]]
          ç  # And convert all integers to ASCII characters
             #  → [["N","!","\n","C","D","\0"],["\1","\1","\0","\0","\0","\1"]]
             # (after which this pair of character-lists is output implicitly as result)

```

# Answer
> 2 votes
# Burlesque, 39 bytes

```
)**iRrtm{{0 2}sip^.-}~]Jm{0>=}j{abL[}\m

```

Try it online!

```
)**       # Map ord() on string
iR        # Generate all rotations
rt        # Rotate once to put deriv[0] to first pos
m{        # Map
 {0 2}si  # Take the 0th and 2nd chars (either side)
 p^       # Push (un-array)
 .-       # Difference
}
~]        # Discard last (i.e. deriv[-1])
J         # Duplicate
m{0>=}    # Create pos/neg list as 0,1
j         # Swap
{
 ab       # Abs
 L[       # Chr()
}\m       # Map and concat to str

```

# Answer
> 2 votes
# Jelly, 13 bytes

```
LŻịOI+Ɲµ>-,AỌ

```

Try it online!

Uses `\0` and `\1` for the sign string, the Footer converts the output into code points to be clearer

## How it works

Just a refresher on Jelly's indexing rules: 1-indexed, wrapping modularly. That means that `0 ị “1234”` returns `4`.

```
LŻịOI+Ɲµ>-,AỌ - Main link. Takes a string s on the left
L             - Length of s
 Ż            - [0, 1, 2, ..., len(s)]
   O          - Yield the code points of s
  ị           - Index into the code points with the range
                This is equivalent to prepending the last character of s
    I         - Forward differences
     +Ɲ       - Sums of overlapping pairs
       µ      - Call these sums S and use as the left and right arguments
        >-    - Is each sum greater than -1?
           A  - Yield the absolute values of each sum
          ,   - Pair
            Ọ - Convert to characters

```

# Answer
> 1 votes
# Python 3, <sup>~~119~~ \\$\cdots\\$ ~~92~~</sup> 91 bytes

Saved 6 bytes thanks to Kevin Cruijssen!!!
Added 6 bytes to handle empty string input.

```
lambda s:zip(*[(chr(abs(S)),S<0)for S in(ord(s[i+1])-ord(s[i-1])for i in range(len(s)-1))])

```

Try it online!

Outputs a sequence of: a tuple of characters and a tuple of `True`/`False` for negative/positive values.

# Answer
> 1 votes
# Charcoal, 28 bytes

```
≔Ｅ⊖Ｌθ⁻℅§θ⊕ι℅§θ⊖ιθ⟦⭆θ‹ι⁰⭆θ℅↔ι

```

Try it online! Link is to verbose version of code. Outputs the signs first (`0=+,1=-`) as otherwise the default print format will mangle the newlines. Explanation:

```
≔Ｅ⊖Ｌθ⁻℅§θ⊕ι℅§θ⊖ιθ

```

Compute the pairs of ordinal differences, excluding the last pair (which in Charcoal would normally wrap around to `0`).

```
⟦⭆θ‹ι⁰⭆θ℅↔ι

```

Print the signs of the differences and the characters of the absolute values of the differences.

# Answer
> 1 votes
# Ruby, ~~87~~ ~~85~~ 82 bytes

```
->s{d=n='';i=0;loop{k=s[i+=1].ord-s[i-2].ord;n+="++-"[k<=>0];d<<k.abs}rescue[d,n]}

```

Try it online!

---
Tags: code-golf, string, calculus
---


title: Verify Magic Square

text:
# Question
Title: Verify Magic Square
A magic square is a square array of numbers with side n consisting of the distinct positive integers 1, 2, ..., *n*² arranged such that the sum of the *n* numbers in any horizontal, vertical, or main diagonal line is always the same number, which is known as the magic constant.

Your program must input, through std-in, a number specifying the length of the side of your square, then the numbers in the square. No numbers may be used more than once, no number greater than *n*² may be used, and all numbers must be greater than 0. The program must determine whether that combination of numbers is a magic square.

# Answer
> 4 votes
## CJam, ~~47 39 35 33~~ 31 bytes

```
l~/{_1fb_,Y${\(_@=\}%:++\z}2*;=

```

Takes input like

```
4 [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]

```

Outputs `1` if magic square, `0` otherwise.

**How it works**:

```
l~/                               "Evaluates the input and split the array into chunks"
                                  "of size N where N is the first integer";
   {                      }2*     "Run this code block 2 times";
    _1fb                          "Copy the 2D array and calculate sum of each row of copy";
        _,                        "Copy the array containing sum of each row and get"
                                  "its length. This is equal to N";
          Y${      }%             "Run this code block for each array of the original"
                                  "2D array that we copied from stack";
             \(_                  "Put the length number to top of stack, decrement and"
                                  "copy that";
                @=\               "Take the element at that index from each row and put"
                                  "N back behind at second position in stack";
                     :+           "Take sum of elements of the array. This is sum of"
                                  "one of the diagonals of the 2D array";
                       +          "Push diagonal sum to row sum array";
                        \z        "Bring original array to top and transpose columns";
                             ;    "At this point, the stack contain 3 arrays:"
                                  "  Array with sum of rows and main diagonal,"
                                  "  Array with sum of columns and secondary diagonal and"
                                  "  The original array. Pop the original array";
                              =   "Check if sum of rows + main diagonal array is equal to ";
                                  "sum of columns + secondary diagonal array";

```

This can be golfed further.

Try it online here

# Answer
> 6 votes
## Python 2: 132 chars

```
n,l=input()
r=range
print r(1,n*n+1)==sorted(l)*len({sum(l[i::j][:n])for(i,j)in zip(r(n)+r(0,n*n,n)+[0,n-1],[n]*n+[1]*n+[n+1,n-1])})

```

An example run:

```
STDIN: 4,[16,3,2,13,5,10,11,8,9,6,7,12,4,15,14,1]
Output: True

```

The are two things to check:

1. The sums are the rows, columns, and diagonals are all equal
2. The elements are a permutation of `[1,2,...,n*n].`

The first is checked by taking sums of slices corresponding to these subsets. Each row, column, or diagonal is described by its starting value and its displacement. We take the list corresponding slice, truncate to `n` elements, and sum it. In Python's `[start:end:step]` notation, rows are `[r*n::1]`, columns are `[c::n]` and the two diagonals are `[0::n+1]` and `[n-1::n-1]`. These are stored as a list of `2*n+2` pairs produced by `zip`.

We take the sets of sums and check that it has length 1. Also, we sort the input and check that it is the list `[1,2,...,n*n].` Actually, we combine both into one check by multiplying `sorted(l)` by the length of the sum-sets, a check that always fails unless the sum-set has length 1.

# Answer
> 6 votes
## APL, 35

```
∧/2=/(+⌿x,⍉x),+/↑1 1∘⍉¨x(⌽x←⎕⍴⍨,⍨⎕)

```

**Explanation**
`x←⎕⍴⍨,⍨⎕` prompts for input, shape it into a matrix, and assign to `x`
Reverses the matrix left-to-right
`x(...)` Create a array of matrices: `x` and `x` reverse
`1 1∘⍉¨` For each of those matrices, take the diagonal
`+/↑` form a 2×n matrix of the numbers on those diagonals and sum the rows

`⍉x` Transpose `x`
`x,` then concatenate with `x` to form a n×2n matrix
`+⌿` and sum the columns

`(+⌿x,⍉x),+/↑1 1∘⍉¨x(⌽x←⎕⍴⍨,⍨⎕)` concatenate to form an array of the sums
`2=/` check if consecutive pairs equal
`∧/` and AND together all those results

# Answer
> 4 votes
**APL ~~47~~ 32**

Using TwiNight's excellent solution and applying some more tweaking:

```
∧/2=/+⌿(1 1∘⍉∘⌽,1 1∘⍉,⍉,⊢)⎕⍴⍨,⍨⎕

```

**Explanation:**

This uses function trains, which were introduced in v14 of the Dyalog interpreter. APL is executed from right to left, ⎕'s are inputs, so first the dimensions, then the vector of numbers.

⎕⍴⍨,⍨⎕ creates the matrix NxN

After that comes the function train which are basically just a sequence of functions (between brackets) applied to the right argument. The functions are:

⊢ Returns just right argument (that is the matrix)

⍉ Transposes the right argument matrix

1 1∘⍉ Returns the diagonal

1 1∘⍉∘⌽ Returns the diagonal of the reversed (horizontally) matrix

All the results are concatenated with the function ","

At this point, the result is a matrix whose columns are then summed (+⌿). The values obtained this way are then checked to be the same with ∧/2=/

I'll leave my old solution here too:

```
{M←⍺ ⍺⍴⍵⋄d←M=⍉M⋄(⊃≡∪)((+/,+⌿)M),+/∘,¨d(⌽d)×¨⊂M}

```

takes dimension as left argument, vector of elements as right argument, for example:

```
4{M←⍺ ⍺⍴⍵⋄d←M=⍉M⋄(⊃≡∪)((+/,+⌿)M),+/∘,¨d(⌽d)×¨⊂M}16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1
1

```

Can be tried online here: www.tryapl.org

# Answer
> 3 votes
# Mathematica ~~128~~ 125

```
d = Diagonal; r = Reverse; i = Input[];
Length@Union[Tr /@ Join[p = Partition[i[[2]], i[[1]]],
t = Transpose@p, {d@p}, {d@t}, {d@r@p}, {d@r@t}]] == 1

```

Takes input such as

```
{4,{16, 3, 2, 13, 5, 10, 11, 8, 9, 6, 7, 12, 4, 15, 14, 1}}

```

> True

# Answer
> 2 votes
# JavaScript (E6) 194

Using prompt to read input and display output.
Test in console with FireFox \>31 (Array.fill is very new)

```
z=(p=prompt)(n=p()|0).split(' '),u=Array(2*n).fill(e=d=n*(n*n+1)/2),z.map((v,i)=>(r=i/n|0,u[r+n]-=v,u[c=i%n]-=v,d-=v*(r==c),e-=v*(r+c+1==n))),o=!(e|d|u.some(v=>v)),z.sort((a,b)=>a-b||(o=0)),p(o)

```

**Less golfed**

```
n = prompt()|0; // input side length
z = prompt().split(' '); // input list of space separeted numbers
e = d = n*(n*n+1)/2; // Calc sum for each row, column and diagonal
u = Array(2*n).fill(e), // Init check values for n rows and n columns

z.map( (v,i) => { // loop on number array
  r = i / n | 0; // row number
  c = i % n; // column number
  u[r+n] -= v; // subtract current value, if correct it will be 0 at loop end
  u[c] -= v;
  if (r==c) d -= v; // subtract if diagonal \
  if (r+c+1==n) e -=v; // subtract if diagonal /
}),
o=!(e|d|u.some(v=>v)); // true if values for rows, cols and diags are 0
z.sort((a,b)=>a-b||(o=0)); // use sort to verify if there are repeated values in input
alert(o);

```

# Answer
> 2 votes
## GolfScript 67 (demo)

```
~]:q(/q(/zip+[q()/{(\;}%]+[q((/);(;{(\;}%]+{{+}*}%.&,2<q(2?,{)}%-!*

```

# Answer
> 2 votes
# Pyth, ~~24~~ 30 bytes

```
&q1l{sM++JcEQCJm.e@bkd_BJqSlQS

```

Try it online here.

```
&q1l{sM++JcEQCJm.e@bkd_BJqSlQSQ   Implicit: Q = evaluated 1st input (contents), E = evaluated 2nd input (side length)
                                  Trailing Q inferred
          cEQ                     Chop E into pieces or length Q
         J                        Store in J
                      _BJ         Pair J with itself with rows reversed
               m                  Map the original and it's reverse, as d, using:
                .e   d              Map each row in d, as b with index k, using:
                  @bk                 Get the kth element of b
                                  The result of this map is [[main diagonal], [antidiagonal]]
        +J                        Prepend rows from J
       +     CJ                   Prepend columns from J (transposed J)
     sM                           Sum each
    {                             Deduplicate
   l                              Length
 q1                               Is the above equal to 1?
&                                 Logic AND the above with...
                          SlQ     ... is the range [1-length(Q)]...
                         q        ... equal to...
                             SQ   ... sorted(Q)

```

*Edit: fixed a bug, thanks to @KevinCruijssen for letting me know :o)*

# Answer
> 1 votes
**LUA 186 Chars**

```
s=io.read(1)v=io.read(2)d=0 r=0 for i=1,#s do t=0 for j = 1, #s do t=t+s[i][j]end d=d+s[i][i] r=r+s[i][#s-i+1]if t ~= v then o=true end end if d~=v and r~= v then o=true end print(not o)

```

# Answer
> 1 votes
# 05AB1E, ~~24~~ 21 bytes

```
ôD©ø®Å\®Å/)O˜Ë²{¹nLQ*

```

Input format: `4\n[2,16,13,3,11,5,8,10,7,9,12,6,14,4,1,15]`. Outputs `1`/`0` for truthy/falsey respectively.

Try it online or verify some more test cases.

**Explanation:**

```
ô      # Split the 2nd (implicit) input into parts of a size of the 1st (implicit) input
       #  i.e. [2,16,13,3,11,5,8,10,7,9,12,6,14,4,1,15] and 4
       #   → [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]]
 D     # Duplicate it
  ©    # And store it in the register (without popping)
ø      # Zip/transpose; swapping rows/columns
       #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]]
       #   → [[2,11,7,14],[16,5,9,4],[13,8,12,1],[3,10,6,15]]
®      # Push the matrix from the register again
 Å\    # Get the top-left to bottom-right main diagonal of it
       #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]] → [2,5,12,15]
®      # Push the matrix from the register again
 Å/    # Get the top-right to bottom-left main diagonal of it
       #  i.e. [[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]] → [3,8,9,14]
)      # Wrap everything on the stack into a list
       #  → [[[2,16,13,3],[11,5,8,10],[7,9,12,6],[14,4,1,15]],
       #     [[2,11,7,14],[16,5,9,4],[13,8,12,1],[3,10,6,15]],
       #     [2,5,12,15],
       #     [3,8,9,14]]
 O     # Take the sum of each inner list:
       #  → [[34,34,34,34],[34,34,34,34],34,34]
 ˜     # Flatten this list
       #  i.e. [[34,34,34,34],[34,34,34,34],34,34] → [34,34,34,34,34,34,34,34,34,34]
  Ë    # Check if all values are equal to each other
       #  i.e. [34,34,34,34,34,34,34,34,34,34] → 1 (truthy)
²      # Push the second input again
 {     # Sort it
       #  i.e. [2,16,13,3,11,5,8,10,7,9,12,6,14,4,1,15]
       #  → [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
  ¹n   # Push the first input again, and take its square
       #  i.e. 4 → 16
    L  # Create a list in the range [1, squared_input]
       #  i.e. 16 → [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
     Q # Check if the two lists are equal
       #  i.e. [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
       #   and [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] → 1 (truthy)
*      # Check if both checks are truthy by multiplying them with each other
       #  i.e. 1 and 1 → 1
       # (and output the result implicitly)

```

# Answer
> 1 votes
# K (ngn/k), ~~36~~ 33 bytes

-3 bytes from improvements by @ngn

```
{1=#?{+/x,'x@'!#x}'(|+:)\(x,x)#y}

```

Try it online!

May be non-qualifying, as this is a function taking two args; the length of the square, and a list of the square's values.

* `(x,x)#y` build `x`-by-`x` matrix of the values from `y`
* `(|+:)\` build list of all rotations of the matrix
* `{...}'` inner lambda, called on each rotation
    + `x@'!#x` get the main diagonal elements
    + `x,'x` zip them with the original values
    + `+/` take the column-wise sum (the last column being the main diagonal)
* `1=#?` is there only one distinct sum?

# Answer
> 0 votes
# Husk, 27 bytes

```
&=O¹ḣ□³Λ=mΣ+mo►L∂Se↔C³¹S+TC

```

Try it online!

I don't know any other techniques to golf this further, but it would be really cool if I could get it any lower.

Explanation coming later.

Takes inputs as 2 command line args, since Husk does not have the feature of taking from STDIN.

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


title: Bedevil your hangman opponent

text:
# Question
Title: Bedevil your hangman opponent
## Task

You are playing Hangman, and your opponent uses a simple but effective strategy: Each turn, from the remaining letters, they guess the letter that appears most frequently across all possible words. When multiple letters appear with the same maximum frequency, your opponent selects randomly among them.

That is, your opponent knows which dictionary (list of words) you've chosen your word from, and has computed a table showing how many times each letter of the alphabet appears in this dictionary. Your opponent always chooses letters with higher frequency counts before letters with lower frequency counts.

Your goal is to write a program that will select a word that maximizes their average number of guesses.

This is code golf.

## Input / Output

The input will be a list of words in any convenient format, per standard site IO rules (comma delimited string, array, lines of a file, etc).

The output will be a single word from that list that maximizes your opponent's average number of guesses. If there is more than one such word, you may return any one of them.

## Worked Example

If the input word list is:

```
one
wont
tee

```

The letter frequency table will be:

```
┌─┬─┬─┬─┬─┐
│e│t│o│n│w│
├─┼─┼─┼─┼─┤
│3│2│2│2│1│
└─┴─┴─┴─┴─┘

```

Your opponent will always guess `e` first, since it occurs most frequently. Their second, third, and fourth guesses will be split randomly among the letters `t`, `o`, and `n`, and `w` will always be guessed last.

Thus the word `wont` will always be completed last, on the 5th guess, and is the sole correct answer for this word list.

## Notes

* Words will contain only the 26 letters `a` through `z`.
* If you want, you can use the uppercase alphabet instead.
* When there is more than one correct answer, you may return any of them. If you want, you can return all of them, but this is not required.

## Test Cases

Each test case consists of two lines:

1. An input word list of space-separated words.
2. The expected output. This will be a single word when there is only one correct answer, and a space-separated list when there is more than one. Note that your program only needs to return one correct answer when there are multiple correct answers.

```
one wont tee
wont

aaa bbb ccc
aaa bbb ccc

oneword
oneword

thee lee
thee

tee lee
tee lee

three eon one holt
three holt

xeon threes eon one holt
threes

xeon threes eon one holt apple mango george any fine
fine

```

# Answer
> 5 votes
# Stax, <sup>~~20 18 10~~</sup> 9 bytes

```
·╦Eà3ΩQù»

```

Run and debug it

~~Explanation coming next year™.~~ Happy new Year!

-8 bytes from recursive using the surprisingly fitting `multi-anti-mode` builtin.

-1 more byte from recursive with an insane compression hack.

Replacing `H` from this version with `E`(a lower codepoint), results in -1 byte due to packing magic.

## Explanation

```
$|!x{n|&%oE
$           join the input together
 |!         get the rarest characters(anti-mode)
   x        push the input again
    {    o  and order by the following:
     n|&    intersect with the anti-mode
        %   and take the length
          E push all the elements onto stack
            implicitly print the last element

```

# Answer
> 9 votes
# Python 2, 60 bytes

```
lambda l:min(l,key=lambda x:sorted(map(`l`.count,set(x)))+l)

```

Try it online!

### Explanation

The idea is much like every other answer. In every word, we compute the frequency of each character. Then we take the word whose least frequent character occurs most often.

In the code, we sort the array as opposed to finding the minimum. Here is an example to show how this works: `Input: thee lee baa`. For each word, we compute a frequency table (duplicates are ignored): `[(1, 1, 4), (1, 4), (1, 2)]`. After sorting, the lexiocgraphically smallest list is `(1, 1, 4)`, therefore the answer is `thee`.

There is also an edge case to consider: `Input: a bc`, which gives the following frequency table: `[(1), (1, 1)]`. The lexicographically smallest list would be `(1)`, which is incorrect since the second list contains more `1`s. I'll leave out the specifics of how the code resolves this issue

# Answer
> 6 votes
# 05AB1E, ~~25~~ ~~16~~ ~~13~~ ~~11~~ ~~13~~ 12 bytes

-3 thanks to @pxeger

-2 thanks to @ovs

+2 for bug fix (for input `acb abc cb` and `aa ab bcc bcc`)

-1 for another bug fix, noticed by @ovs

```
ΣISÐ¢WQÏ¢O}θ

```

Try it online!

# Legacy version, 10 bytes, thanks to @ovs

```
ΣIS.m¢O(}н

```

Try it online!

# Answer
> 6 votes
# K (ngn/k), ~~35~~ ~~33~~ ~~28~~ ~~27~~ 20 bytes

-2 bytes from shuffling things around

-5 bytes from @Traws' improvement

-1 byte from @bstrat's improvement

-7 bytes from new approach

```
{*>+/'x#=/&/\#'=,/x}

```

Try it online!

Modeled after @xash's J answer.

* `#'=,/x` build a dictionary mapping characters to the number of times they appear across the entire input
* `=/&/\` identify the least frequent character(s)
* `+/'x#` sum up the number of times the most infrequent characters appear in each word of the input
* `*>` filter the input down to the first word with the most infrequent character(s)

# Answer
> 5 votes
# , 32 bytes

```
{.@\:(~.(#~<./=])#/.~)@;+/@e."1>

```

Try it online!

* `;` words razed to letters
* `#/.~` number of occurrences of each letter
* `~.` the letters deduplicated
* `(#~<./=])` take only the most infrequent letters
* `+/@e."1>` how many of these letters occur in each word?
* `{.@\:` sort the words based on the amount and return the first one (the one with most infrequent letters)

# Answer
> 3 votes
# , ~~111~~ 110 bytes

-1 byte thanks to Giuseppe

```
function(s)s[which.max(colSums(outer(names(x<-table(unlist(strsplit(s,""))))[x==min(x)],s,Vectorize(grepl))))]

```

Try it online!

Computes the table of number of occurrences of each letter, then the vector of letter(s) which occur the least often. These rare letters will be tried last (in random order), so we pick the word which maximises the number of distinct rare letters.

If there are several optimal words, this returns the first one. We can return all of them at a cost of 1 byte.

# Answer
> 3 votes
# Charcoal, 38 bytes

```
ＷＳ⊞υι≔Ｅβ№⪫υωιη≔ＥυＬΦ⌕Ａη⌊Φηλ№ι§βλζ§υ⌕ζ⌈ζ

```

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

```
ＷＳ⊞υι

```

Input the words.

```
≔Ｅβ№⪫υωιη

```

Get frequencies for all of the letters.

```
≔ＥυＬΦ⌕Ａη⌊Φηλ№ι§βλζ

```

Find the letters with the lowest positive frequencies, then for each word count how many of those letters are contained.

```
§υ⌕ζ⌈ζ

```

Output the word with the highest count.

Previous 84-byte longhand solution:

```
ＷＳ⊞υι≔υθ≔Ｅβ№⪫υωιη≔Ｅυ⁰ζＷ⌈η«≔⌕ＡηιεＦε§≔ηκ⁰ＵＭε§βκ≔ＥθΦκ¬№εμδＵＭζ⁺κ⎇§δλＬεＬΦε№§θλμ≔δθ»§υ⌕ζ⌈ζ

```

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

```
ＷＳ⊞υι

```

Input the words.

```
≔υθ

```

Make a copy of the list. The letters will be removed from these words as they are guessed.

```
≔Ｅβ№⪫υωιη

```

Get frequencies for all of the letters.

```
≔Ｅυ⁰ζ

```

Start off with 0 guesses for all of the words.

```
Ｗ⌈η«

```

Repeat while there are still letters to guess.

```
≔⌕Ａηιε

```

Find the positions of the most frequent letters.

```
Ｆε§≔ηκ⁰

```

Remove them from the list of frequencies.

```
ＵＭε§βκ

```

Get the letter characters at those positions.

```
≔ＥθΦκ¬№εμδ

```

Make a temporary copy of the words with all of those letters removed.

```
ＵＭζ⁺κ⎇§δλＬεＬΦε№§θλμ

```

For words which still have some letters left, count all of the letters as guesses, otherwise just count the number of matching letters. This is the minimum number of guesses rather than the average but the sort order is the same.

```
≔δθ

```

Update the list of words with the removed letters.

```
»§υ⌕ζ⌈ζ

```

Print the word that took the most guesses.

# Answer
> 2 votes
# Wolfram Language (Mathematica), ~~60~~ 56 bytes

```
#~MaximalBy~Union/*Map[c=Counts[Join@@#]]/*Count[Min@c]&

```

Try it online!

Input a list of character lists.

# Answer
> 1 votes
# Ruby 2.7, 61 bytes

```
->w{w.min_by{_1.chars.uniq.map{|c|(w*"").count c}.sort<<1e9}}

```

Try it online!

Expects an array of words. Outputs the one with most rarest chars. TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves two bytes.

# Answer
> 1 votes
# Japt `-m`, 29 bytes

```
Ë¬x@¬Ê/U¬èX p
VíU nÏÎ-XgÃÎg1

```

Try it

Not a great answer but a bit different approach.

`Ë¬x@¬Ê/U¬èX p` \\$\to\\$ map each word by summing the weight of each letter.

* Weight is number of all letters divided by occurrences of letter raised to a power (\\$2\\$) we can increase the power to get a more precise output at the cost of one byte.

`VíU nÏÎ-XgÃÎg1` \\$\to\\$ sorts the input based on weights

# Answer
> 1 votes
# , 100 bytes

```
function(s,S=colSums)s[order(S(t(a<-matrix(sapply(letters,grepl,s),,26))*(b=S(a))!=min(b[b>0])))][1]

```

Try it online!

**How?** \- ungolfed version:

```
f=function(s){
a<-sapply(letters,grepl,s)  # a = matrix indicating which letters (columns) are present in which words (rows)
a<-matrix(a,,26)            # (force 'a' as a matrix in case there was only one word in the input)
b<-colSums(a)               # b = for each letter, the count of the words that it is in
c<-t(a)*b                   # c = replace 'TRUE' elements of 'a' with the word counts from 'b'
d<-colSums(c==min(b[b>0]))  # d = the number of different letters in each word with the lowest overall nonzero word count
s[which.max(d)]             # output the (first) word that maximises d
}

```

# Answer
> 1 votes
# Pyth, 15 bytes

```
.Mms/L.m/sQbsQZ

```

Try it online!

---
Tags: code-golf
---


# Question
Title: Shorter way to assign a default value to the standard output stream
I have this code :

```
tr ' ' '\n'|sort -n|head -1

```

The code is pretty simple, it takes a list of integer in the standard input stream (like `5 9 8 7 5 2 -12 -30`), it sort the integers and display only the first integer. But i need to ouput `0` if the given list is empty. And i can't find a short way to that. I have a solution with a ternary operator and a `echo 0`, but i feel i can do far better. I just need to replace the input stream by `0` if this stream is empty.

Sidenote : I don't need to call read to get the user input. The program is called with the input stream directly like `cmd < 1 5 6 -20 45`

Here my current code :

```
read l
[ -n "$l" ]&&echo $l|tr ' ' '\n'|sort -n|head -1||echo 0

```

# Answer
> 4 votes
## ~~37~~ ~~33~~ 32 bytes

```
tr \  \\n|sort -n|sed s/^$/0/\;q

```

Edit: Saved 4 bytes thanks to @DigitalTrauma.

# Answer
> 5 votes
# 34 bytes

```
a=($(tr \  \\n|sort -n))
echo $[a]

```

The first line saves the sorted input values in an array `a`.

This avoids using `head -1`, since referencing the array as `$a` will yield its first value.

The second line uses `a` in the arithmetic expansion `$[a]`. In this context, an empty string is interpreted as **0**.

For a different default value, parameter substitution could be used instead. For example, the last line could become

```
echo ${a:-puppies}

```

# Answer
> 1 votes
## 42 bytes

Two different ways that have the same byte-count Use `awk` as the last command

```
tr ' ' '\n'|sort -n|awk 'NR==1{print $1+0}'

```

Or do all the computations in `awk`

```
awk -v RS=" " '{m=m>$1?m:$1}END{print m+0}'

```

# Answer
> 1 votes
# Pure : 41 bytes.

No requirement of any `tr`, `sort`, `head`...

```
t=${1:-0};for i;{ ((t=i<t?i:t));};echo $t

```

In a function you could use `local -i` for integer variables:

```
f() { local -i t=$1;for i;{ ((t=i<t?i:t));};echo $t;}

```

Then

```
f 5 9 8 7 5 2 -12 -30
-30

f
0

```

### Note: If you **need** to read them from stdin

```
read l
f $l

```

will do the job.

As:

```
read l;for i in ${l:-0};{ ((t=i<t?i:t));};echo $t;}

```

## Another version 58 bytes.

Something longer, but could be quicker, as there is no loop.

```
. <(printf v[%d+99**9]=\  $@);v=(${!v[@]});echo $[v-99**9]

```

In a function:

```
f() { local v;. <(printf v[%d+99**9]=\  $@)
      v=(${!v[@]});echo $[v-99**9];}

```

Then

```
f 34 56 1000 12  -156 53 -12 -21 321 3221
-156

f
0

```

---
Tags: code-golf, tips, bash
---


title: Possible binaries sum

text:
# Question
Title: Possible binaries sum
This challenge is inspired by the AoC 2020, Day 14 - Part II, created by Eric Wastl and his team, which asks to output the possible binary values from a bitmask.

Let's say we've a bitmask like `"10X0X0"`, then we've to find the possible binary values that can be generated by replacing an `X` with either `0` or `1`. Here I've taken `X`, but you could take anything except `0` and `1`, of course.

So, the possible binaries are `["100000", "100010", "101000", "101010"]`.
When each of them are converted in decimal, then these are `[32, 34, 40, 42]` respectively.
And, finally the sum is `148`.

# Test cases

```
INPUT: "X"
["0", "1"]
[0, 1]
OUTPUT: 1

INPUT: "0"
OUTPUT: 0

INPUT: "1"
OUTPUT: 1

INPUT: "1X0"
["100", "110"]
[4, 6]
OUTPUT: 10

INPUT: "1X0X1"
["10001", "10011", "11001", "11011"]
[17, 19, 25, 27]
OUTPUT: 88

INPUT: "X0X0X0X"
["0000000", "0000001", "0000100", "0000101", "0010000", "0010001", "0010100", "0010101",
"1000000", "1000001", "1000100", "1000101", "1010000", "1010001", "1010100", "1010101"]
[0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85]
OUTPUT: 680

INPUT: "1X1X1X1X1X1X1X1X1X1X1"
OUTPUT: 1789569024

INPUT: "1X01X01X01X01X01X01X01X01X01X01X01X0"
OUTPUT: 201053554790400

INPUT: "X000X000X000X000X000X000X000X000X000X000X000X000"
OUTPUT: 307445734561824768

INPUT: "101"
["101"]
[5]
OUTPUT: 5

INPUT: "XXX"
["000", "001", "010", "011", "100", "101", "110", "111"]
[0, 1, 2, 3, 4, 5, 6, 7]
OUTPUT: 28

```

# Rules

* It is guaranteed that \\$ 0 \leq \text{count}(X) \leq 12 \\$ and \\$ 1 \leq \text{length(mask)} \leq 48 \\$.
* Input can be either a string, or an array of chars (non-empty).
* I have chosen `X` in bitmask, however you can replace it with any other character of your choice.
* Output will be the sum of the binaries in decimal.
* This is a , so fewest bytes will win!

---

Sandbox link.

# Answer
# Python 2, 61 bytes

```
k=n=0
for c in input():n=n*2+-ord(c)%3;k+=c>"1"
print(n<<k)/2

```

Try it online!

Implements this algorithm:

1. Convert the input from binary, treating X as \\$\frac{1}{2}\\$.
2. Double the result for each X in the input.

Why does this work? If X appears \\$k\\$ times in the input, we're adding up \\$2^k\\$ near-copies of its binary value. Among these near-copies, each X in any position appears as 0 half the time and 1 half the time for an average of \\$\frac{1}{2}\\$, so we can treat X as the digit \\$\frac{1}{2}\\$.

In the code, we actually convert `0,X,1` to doubled values `0,1,2`, then halve the result before doubling for `X`'s. And, we use `_` for `X`, since we're allowed to use a different character -- anything with the same ASCII code modulo 3 would work, such as the digit `2`.

**63 bytes**

```
lambda s:(reduce(lambda n,c:2*n+-ord(c)%3,s,0)<<s.count('_'))/2

```

Try it online!
> 10 votes

# Answer
# Haskell, ~~56~~ 55 bytes

```
n!(a:x)|a<'X'=(2*n+read[a])!x|m<-4*n=m!x+1!x
n!x=n
(0!)

```

Try it online!

## Explanation

Start with a simple recursive algorithm to convert binary to an integer:

```
n!(a:x)=(2*n+read[a])!x
n!x=n
(0!)

```

From here we add an extra rule if we hit an `X` which just adds the results for the X being 0 and 1 together:

```
n!('X':x)=n!('0':x)+n!('1':x)
n!(a:x)=(2*n+read[a])!x
n!x=n
(0!)

```

We can unroll the applications in that:

```
n!('X':x)=(2*n)!x+(2*n+1)!x
n!(a:x)=(2*n+read[a])!x
n!x=n
(0!)

```

We can move a `2*n` over to the other side since `(!x)` is affine

```
n!('X':x)=(4*n)!x+1!x
n!(a:x)=(2*n+read[a])!x
n!x=n
(0!)

```

From here we combine the pattern matches to save bytes.
> 8 votes

# Answer
# JavaScript (ES6), 55 bytes

```
f=(s,g=d=>f(s.replace('X',d)))=>1/s?+('0b'+s):g(0)+g(1)

```

Try it online!

### Commented

```
f = (                   // f is a recursive function
  s,                    // taking the input string s
  g = d =>              // g is a helper function taking a digit d
    f(                  // and doing a recursive call to f
      s.replace('X', d) // with the first 'X' in s replaced with d
    )                   //
) =>                    //
  1 / s ?               // if s looks like a number (i.e. does not contain any 'X'):
    +('0b' + s)         //   convert it from binary to decimal
  :                     // else:
    g(0) +              //   invoke g a 1st time to replace the first 'X' with '0'
    g(1)                //   invoke g a 2nd time to replace the first 'X' with '1'

```
> 7 votes

# Answer
# Bash, 38

```
echo $[`eval echo +2\#${1//X/{0,1\}}`]

```

Try it online!
> 6 votes

# Answer
# , 47 bytes

```
1#.#.@(]`(_ I.@E.[)`[}"#.[:#:@i.@(**2&^)1#._&=)

```

Try it online!

Not super happy with this one...
> 5 votes

# Answer
# , ~~156~~ ~~142~~ ~~78~~ ~~61~~ ~~56~~ ~~52~~ ~~51~~ 50 bytes

In the entry of the bitmask, `2` replaces `X`.

Thanks to Giuseppe, came a reduction in unnecessary brackets in an earlier version recreating the binary duplications.

However, a more condensed version can be found by realising that the sum is the sum of the inverse of the non-zero digits, times 2 to the power of the number of 2's, ie

which actually happens to be the solution earlier worked out by xnor. With improvements from Dominic achieving the same score as this earlier solution and more from Giuseppe!

```
function(x)2^sum(a<-x>1)*rev(x/4^a)%*%2^(seq(x)-1)

```

Try it online!
> 5 votes

# Answer
# 05AB1E, ~~14~~ 12 bytes

```
Y1ÝI2¢ãδ.;CO

```

Uses `2` instead of `X`.

Try it online.

**Explanation:**

```
 1Ý           # Push the list [0,1]
   I2¢        # Count the amount of 2s in the input-string
      ã       # Take the cartesian product of [0,1] with this count
       δ      # Map over each inner list of 0s and 1s:
Y       .;    #  Replace every 2 in the (implicit) input-string one by one with the 0s
              #  and 1s in the current list
          C   # Convert each binary string to a base-10 integer
           O  # Sum the list together
              # (after which the result is output implicitly)

```

---

Fun alternative that's unfortunately a byte longer (**13 bytes**):

```
TIgãʒøþ€ËP}CO

```

Uses `X`.

Try it online.

**Explanation:**

```
T           # Push 10
 Ig         # Push the length of the input-string
   ã        # Take the cartesian product of "10" with this count
    ʒ       # Filter this list of binary strings by:
     ø      #  Zip/transpose it with the (implicit) input, creating pairs
      þ     #  Remove all "X" from each pair by only leaving digits
       €Ë   #  Check for each if all digits are the same
            #  (this checks if the 1s and 0s are at the same positions between the
            #   current binary string and input; and since we've removed all "X" those
            #   single digits are truthy by default)
         P  #  Check if this is truthy for all of them with the product
    }C      # After the filter: convert any remaining binary string to a base-10 integer
      O     # Sum the list together
            # (after which the result is output implicitly)

```
> 4 votes

# Answer
# Haskell, 53 bytes

```
sum.foldl(%)[0]
l%c=[2*a+1-read[b]|a<-l,b<-"01",b/=c]

```

Try it online!

Implements the spec somewhat directly, using a modified from-binary conversion that works on lists of digits to produce lists of possible outcomes. Any character can be used for `X` except of course for `0` and `1`.
> 4 votes

# Answer
# Husk, 11 bytes

```
*ΠfI¹ḋm?I\ε

```

Try it online!

Port of xnor's approach. Input is list of binary digits (`0` or `1`), with `2` to represent the bitmask.
13 bytes to accept input as an integer instead of a list.

```
*               # multiply
 Π              # product of
  fI¹           # non-zero elements of input
     ḋ          # by binary number with digits given by
      m         # mapping over all digits of input
       ?  ε     # if digit is equal to at most 1
        I       # leave it alone
         \      # otherwise take reciprocal

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), 67 bytes

```
Distribute@StringReplace[#,"X"->"0"+"1"]/.s_String:>s~FromDigits~2&

```

Try it online!

-1,2,...50...61 bytes from @att
> 2 votes

# Answer
# Perl 5 `-p`, 35 bytes

```
s/X/{0,1}/g;map$\+=oct"0b$_",glob}{

```

Try it online!
> 2 votes

# Answer
# MATLAB, 55 46 bytes

```
@(x)2.^(nnz(x):-1:1)*mod(x'*2,3)/4*2^nnz(x>49)

```

Inspired by the Python solution of xnor. But here we don't use a loop, we work with array operators.

Thanks to Luis Mendo for replacing the sum of element-wise products by the dot product (-5 bytes).

Instead of `X`, it expects `_` as input:

```
ans('1_0_1')
ans =
    88

```

etc.
> 2 votes

# Answer
# K (oK), 37 bytes

```
{(*/(+/t)#2)*{y+2*x}/x-48+1.5*t:x=50}

```

Try it online!

Inspired by xnor's Python solution.
> 2 votes

# Answer
# Jelly, (9?) 12 bytes

9 if we may accept a list of integers (e.g. `"0X1X0"` as `[0,2,1,2,0]`) - remove the leading `V€µ`.

```
V€µẹ2ŒPṬạḂḄS

```

A monadic Link accepting a list of characters from `"012"` (`'2'` representing an unknown bit) which yields the sum.

**Try it online!**

### How?

```
V€µẹ2ŒPṬạḂḄS - Link: list of characters, S    e.g. "022001"
V€           - convert (S) to a list of integers   [0,2,2,0,0,1]
  µ          - start a new monadic chain, f(A=that)
   ẹ2        - indices of 2                        [2,3]
     ŒP      - power-set                           [[],[2],[3],[2,3]]
       Ṭ     - un-truth                            [[],[0,1],[0,0,1],[0,1,1]]
         Ḃ   - mod-2 (A)                           [0,0,0,0,0,1]
        ạ    - absolute difference                 [[0,0,0,0,0,1],[0,1,0,0,0,1],[0,0,1,0,0,1],[0,1,1,0,0,1]]
          Ḅ  - convert from binary                 [1,17,9,25]
           S - sum                                 52

```
> 2 votes

# Answer
# C (gcc), 71 bytes

```
c,s;f(char*m){for(c=1,s=0;*m;88-*m++||(s++,c*=2))s+=s+=*m==49;c=c*s/2;}

```

Try it online!

* Saved 2 bytes thanks to @Ceilingcat
* Works only for small numbers (int) added unsigned long in header to test 1X1X1X1X1X1X1X1X1X1X1

We iterate a char array: `s` is sum
`c` is number of masks, initially 1

```
s+=*m==49  - we add 1 if we have '1'
s*=2       - then we multiply by 2
88-*m++||  - if we have a 'X'
(s++,c*=2) - we add 1 and we double number of possible masks.

c=c*s/2    - finally we multiply sum by c and divide by 2 because we multiplied sum one time more than needed.

```
> 2 votes

# Answer
# K (ngn/k), ~~27~~ 20 bytes

```
{_2/0.5^x,&+/^x:.'x}

```

Try it online!

Modeled after @Galen Ivanov's oK answer. Uses `" "` in place of `"X"` in the input.

* `x:.'x` convert input string to a list of integer digits, updating variable `x` (spaces in the input become `(::)`s, i.e. null functions)
* `&+/^` generate n 0's, where n is the number of blanks in the input
* `x,` append these 0's to the end of the digit-ified input
* `0.5^` fill nulls with 0.5's
* `_2/` convert from base-2 and take the floor
> 2 votes

# Answer
# Stax, 20 bytes

```
år╢T>∩E%>►ΣD"╬@☼≡ ╫^

```

Run and debug it

Shortened from 32 by borrowing the idea from Kevin Cruijssen's answer.
> 1 votes

# Answer
# Octave, ~~66~~ 59 bytes

```
@(x)(t=0:2^nnz(x)-1)*all(abs(dec2bin(t)*2-mod(2*x,99))<2,2)

```

Uses character `b` instead of `X`. Runs out of memory for the two longest test cases.

**Try it online!**
> 1 votes

# Answer
# Wolfram Language (Mathematica), 43 bytes

```
d[c=0;d/@#/. 2:>++c^0/2,2]2^c&
d=FromDigits

```

Try it online!

Input a list of characters. Uses `2` instead of `X`.
> 1 votes

# Answer
# Retina 0.8.2, ~~41~~ 29 bytes

```
+%1`X
0$'¶$`1
1
01
+`10
011
1

```

Try it online! Link includes smaller test cases (code uses unary arithmetic so large numbers won't work on TIO). Explanation:

```
+%1`X
0$'¶$`1

```

Repeatedly replace each line containing an `X` with two copies of that line, one with a `0` and one with a `1` in place of the first `X`.

```
1
01
+`10
011

```

Convert each line from binary to unary.

```
1

```

Take the sum and convert to decimal.
> 1 votes

# Answer
# Charcoal, 18 bytes

```
Ｉ÷×↨Ｅθ⌕0X1ι²Ｘ²№θX²

```

Try it online! Link is to verbose version of code. Explanation: Based on @xnor's algorithm.

```
     θ              Input string
    Ｅ               Map over characters
      ⌕             Find index of
          ι         Current character
       0X1          In literal string `0X1`
   ↨       ²        Convert from "binary"
  ×                 Multiply by
             ²      Literal `2`
            Ｘ       Raised to power
              №     Count of
                X   Literal string `X`
               θ    In input string
 ÷                  Integer divide by
                 ²  Literal `2`
Ｉ                   Cast to string
                    Implicitly print

```
> 1 votes

# Answer
# Scala, 61 bytes

```
_./:(Set(0)){(a,c)=>for(s<-a;d<-Set(c%2,c%3))yield s*2+d}.sum

```

Try it online!

Turns out `X`'s value of 88 is perfect for this algorithm.

A simple binary-to-decimal conversion would look like this in Scala. `/:` is the fold operator. Starting with `0`, you multiply 0 by 2 and add the first digit. Then you multiply that by 2 again and add the next digit, and so on.

```
(0 /: listOfInts)((a, c) => 2 * a + c)

```

This is very similar, except now we're folding with multiple integers, and we're taking the sum at the end. In the lambda used for folding, `a` is all the accumulated sums, and `c` is the next character. For every sum `s` in `a` (`for(s<-a`), for every possible digit `d` that `c` could represent `d<-Set(c%2,c%3)`, we do the same thing as above - double the accumulator and add the next digit (`d`) to it, doubling the size of our set of accumulators each time.

`Set(c%2,c%3)` works because `'0'%2` and `'0'%3` both return `0` and `'1'%2` and `'1'%3` both return `1`. Even though there's two of them, since we're using a `Set`, the duplicate is automatically removed. If, however, `c` is `'X'` (88), then `'X'%2` is `0` and `'X'%3` is `1`, giving us two different possible values, which is pretty nice.
> 1 votes

# Answer
# Icon, ~~85~~ 77 bytes

```
procedure f(s)
b:=n:=0
c:=!s&{c=2&{c:=.5;n+:=1};b:=2*b+c}&\z
return b*2^n
end

```

Try it online!

Uses `2` instead of `X`.

Inspired by xnor's Python solution.
> 1 votes

# Answer
# Factor, 46 bytes

```
[ [ 48 - >bin ] map [ bin> ] product-map sum ]

```

Try it online!

Takes an array of charcodes (the character `2` is used for X) and returns the sum. Uses the built-in that generates the Cartesian product of multiple sequences. (I think it's already done in many answers.)

```
[
  [ 48 - >bin ] map     ! map '0', '1', '2' to "0", "1", "10" respectively
  [ bin> ] product-map  ! compute cartesian product of all strings,
                        ! and convert from binary to integer
  sum                   ! sum
]

```
> 1 votes

# Answer
# , 21 bytes

```
1#.2#.[:>@,@{#:@".&.>

```

Try it online!

Exact same algorithm as my Factor answer. Takes a string, with `2` in the place of X. If a plain integer vector is allowed, remove `@".` to get 18 bytes.

```
1#.2#.[:>@,@{#:@".&.>
                  &.>  NB. Apply to each character and enclose...
             #:@".     NB. Eval and convert to binary (0 -> 0, 1 -> 1, 2 -> 1 0)
           @{  NB. Take cartesian product of all boxed vectors
         @,    NB. Remove unnecessary outer array shape
      [:>      NB. Unbox the result vectors
   2#.         NB. Convert from binary to integer for each row
1#.            NB. Sum

```
> 1 votes

---
Tags: code-golf, number, base-conversion
---


title: Golfing Advent of Code 2020, Day 3

text:
# Question
Title: Golfing Advent of Code 2020, Day 3
I thought it'd be interesting to turn AoC day 3 puzzle into a Golfing Challenge, so here it is.

### Task

Find the number of `#` you'd encounter in an 11x11 grid (consisting of `#` and `.`) that repeats itself (to the right side), starting at the top left corner, which is always a `.`. You will need to check the position that is \\$x\\$ right, \\$y\\$ down, then the position that is \\$x\\$ right, \\$y\\$ down from there and so on until you reach one of the bottom `#` or `.`.

### Input

Two arguments:

* `3,1`
* ```
..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

```

means that you should traverse the grid going 3 right and 1 down. The output should be `7` (see the example in the AoC link above).

Without changing the grid but only the positions, here are some example inputs and outputs:

* \\$x=1, y=1 \to 2\\$.
* \\$x=5, y=1 \to 3\\$.
* \\$x=7, y=1 \to 4\\$.
* \\$x=1, y=2 \to 2\\$.

---

* `1,1`
* ```
.........##
.#.#.......
#.......#..
.........#.
.....#.....
...##...#..
#.#..#....#
........##.
......#....
...####...#
.........#.

```

means traversing the grid going 1 right, 1 down each time. You'd encounter only 1 `#` in this example, so the output should be `1`.

### Rules

* \\$x\\$ (right) and \\$y\\$ (down) will be positive integers, where \\$y \< 3\\$ (no limits for \\$x\\$).
* The grid can be repeated unlimited times.
* You can replace `.` and `#` with whatever you like in the grid (e.g. `0`/`1`). Just mention which corresponds to which.
* You can receive input through any of the standard IO methods.
* This is , so shortest code in bytes wins!

# Answer
# , ~~30 26 23~~ 22 bytes

```
0{0{[:+/|.^:(<@%&{.~$)

```

Try it online!

*Note: This solution works for any grid*

J supports multi-dimensional rotation, which reduces the problem almost to a single summation. To clarify what's happening, assume the board looks like this:

```
 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29
30 31 32 33 34
35 36 37 38 39

```

Now we rotate the columns left and the rows up `|.` by `1 3`, iteratively, 3 times:

```
┌──────────────┬──────────────┬──────────────┐
│ 0  1  2  3  4│ 8  9  5  6  7│11 12 13 14 10│
│ 5  6  7  8  9│13 14 10 11 12│16 17 18 19 15│
│10 11 12 13 14│18 19 15 16 17│21 22 23 24 20│
│15 16 17 18 19│23 24 20 21 22│26 27 28 29 25│
│20 21 22 23 24│28 29 25 26 27│31 32 33 34 30│
│25 26 27 28 29│33 34 30 31 32│36 37 38 39 35│
│30 31 32 33 34│38 39 35 36 37│ 1  2  3  4  0│
│35 36 37 38 39│ 3  4  0  1  2│ 6  7  8  9  5│
└──────────────┴──────────────┴──────────────┘

```

We are bringing the sled's "new position" to the top-left corner every time, rather than moving a pointer within a fixed grid and adjusting indexes with modular arithmetic.

Once we have every iteration like this, we need only "sum the planes" element-wise `[:+/`, and then our answer will the number in the top left corner of the resulting matrix `0{0{`.

The only piece left is to determine how many times we need to iterate. This amounts to dividing the first element of our "step" vector (the down part) into the height of the input matrix: `%&{.~$`.

## old approach, 26 bytes

```
1#.]{~[:;/$@]|"1#\@]*($~#)

```

Try it online!
> 6 votes

# Answer
# 05AB1E, 9 bytes

Takes `y`, `grid` and `x` as seperate inputs where grid is a 2d-list of `0/1`.

```
ιнε³N*è}O

```

Try it online! Convert a grid into the required format with this Retina script.

```
ι          # un-interleave the grid with step y
 н         # take the first element grid[0::y]
  ε    }   # map over each row
   ³N*     #   multiply x with 0-based iteration index N
      è    #   index into row (modular)
        O  # sum the values

```
> 4 votes

# Answer
# Scala, ~~47~~ 44 bytes

*-3 bytes thanks to user!*

When replacing the `.`/`#` grid with a `0`/`1` one:

```
(x,y,z)=>1 to 10/y map(i=>z(i*y)(i*x%11))sum

```

Try it online!

---

## ~~77..62~~ 60 bytes

using a `.`/`#` grid:

```
(x,y,z)=>1 to 10/y map(i=>if(z(i*y)(i*x%11)==35)1 else 0)sum

```

Try it online!

**Explanation**:

```
(x, y, z) =>                  // x: steps to the right, y: steps to the bottoms, z: grid as a String sequence
  (1 to 10 / y)               // range r := [1;10/y]
    .map (                    // override every entry in r
      i => if (               // every entry i in r if
        z(i * y)(i * x % 11)  // the character from the grid that is at the position (i * y, i * x),
                              // because i * x can get bigger than the number of columns modulo (%) it by 11
                              // so the correct position is: (i * y, i * x % 11)
          == 35               // is equal to 35 (ASCII numeric value for '#')
      ) 1 else 0              // with 1 else 0
    ) sum                     // sum over all entries

```

**Example**: (5, 3, grid):

```
  val grid = Seq(
    "..##.......",
    "#...#...#..",
    ".#....#..#.",
    "..#.#...#.#",
    ".#...##..#.",
    "..#.##.....",
    ".#.#.#....#",
    ".#........#",
    "#.##...#...",
    "#...##....#",
    ".#..#...#.#"
  )

```

```
   Steps                   | Sequence
   ------------------------|---------
   init                    | [1, 2, 3]
   i = 1; z(3)(5)  == '.'  | [0, 2, 3]
   i = 2; z(6)(10) == '#'  | [0, 1, 3]
   i = 3; z(9)(4)  == '#'  | [0, 1, 1]
   sum == 2

```
> 3 votes

# Answer
# Ruby, 50 bytes

```
->x,y,m,r=c=t=0{t+=m[r][(c+=x)%11]while m[r+=y];t}

```

Try it online!

Expects a matrix of \\$0\\$s and \\$1\\$s. It is given that `m[0][0]` is never a tree, so I always skip it.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 39 bytes

```
#[[i+1,Mod[i#2,11]+1]]~Sum~{i,0,10/#3}&

```

Try it online!

Input `f[grid, x, y]`, where `#`s are `1` and `.`s are 0.
> 2 votes

# Answer
# Haskell, ~~60~~ 54 bytes

```
f x y g=sum[cycle(g!!b)!!a|(a,b)<-zip[0,x..][0,y..10]]

```

Try it online!

* saved 6 using 1 and 0 as '#' and '.'
> 2 votes

# Answer
# Python 3, ~~71~~ \\$\cdots\\$ ~~54~~ 53 bytes

Saved 11 bytes thanks to Command Master!!!
Saved 4 bytes thanks to ovs!!!
Saved a byte thanks to dingledooper!!!!

```
lambda g,r,d:sum(g[i*d][i*r%11]for i in range(11//d))

```

Try it online!

Inputs the grid as a list of lists of \\$1\\$s and \\$0\\$s (representing the number of trees at each place) along with the right and down moves and returns the number of trees hit.
> 1 votes

# Answer
# Jelly, ~~11~~ 10 bytes

```
mLḶ×⁵‘ị"mS

```

Try it online!

-1 byte mostly thanks to caird coinheringaahing

Takes a grid of 1 for `#` and 0 for `.` as the first argument, y as the second argument, and x as the third argument.

```
m             Take every yth row of the grid (starting from the first).
 LḶ           For the range from 0 to its length minus 1,
   ×⁵         multiply each of those numbers by x,
     ‘ị       and 0-index into
       "      corresponding items from
        m     every yth row of the grid.
         S    Sum the retrieved items.

```
> 1 votes

# Answer
# APL+WIN, 40 bytes

Prompts for y, x and the rows of the grid as a nested vector `1=#` and `0=.`:

```
+/(∊n⍴¨⎕)[((n←⌈/n)×y×m)+n←1+⎕×m←⍳10÷y←⎕]

```

Try it online! Thanks to Dyalog Classic
> 1 votes

# Answer
# Charcoal, ~~22~~ 21 bytes

```
ＮθＮηＳζＩΣ⭆÷χη§⊟ＥηＳ×θ⊕ι

```

Try it online! Link is to verbose version of code. Edit: Saved 1 byte by using @Razetime's suggestion of taking input in an alternate format. Input is as a list of `[x, y, ...rows]` where each row is either a numeric or character array or string of digits representing the number of trees in each cell. In the case where each row is a string, the input does not need to be JSON encoded. Explanation:

```
ＮθＮη

```

Input `x` and `y`.

```
Ｓζ

```

Ignore the first line of the grid as we know it always begins with a `.`.

```
⭆÷χη

```

Repeat `10/y` times (joining the results together)...

```
⊟ＥηＳ

```

... input `y` lines of the grid but keeping only the last...

```
§...×θ⊕ι

```

... and cyclically index its column.

```
ＩΣ...

```

Sum the number of trees.

Previous 22-byte version used the original `#` and non-`#` characters:

```
ＮθＮηＳζＩ№Ｅ÷χη§⊟ＥηＳ×θ⊕ι#

```

Try it online! Link is to verbose version of code. There are two differences, the first is that this version works just as will with a regular `Map` instead of a `StringMap`, and the second is that it counts `#`s instead of summing trees.
> 0 votes

# Answer
# Ruby 2.7, 42 bytes

```
->r,y,m{((0..10)%y).count{m[_1][_1*r%11]}}

```

Try it online!

Expect inputs as \\$r = \frac xy\\$, \\$y\\$ and a matrix of `true` and `false` values indicating the presence of a tree at that place. This solution uses a different approach from my previous one. TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters and `Enumerable#%` method, which saves five bytes.
> 0 votes

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


title: Compute all close strings quickly

text:
# Question
Title: Compute all close strings quickly
## Input

A string S of length between 10 and 16 inclusive. The characters are taken from the 95 printable ASCII characters, byte values `32` (`0x20`) to `126` (`0x7E`) ( to `~`)

## Output

Your code must compute and output all strings within Levenshtein distance 2 of S. You can have duplicates as long as you also have all the different strings and the output can be in any order.

## Scoring

I will generate a set of 5 strings of random lengths between 10 and 16, each consisting of a selection of printable ASCII characters. Each answer will be tested on the same set of strings, and your score is the total runtime over all 5, when run on my computer (spec details below). This means you need to give me simple and complete instructions on how to compile and run your code in Linux.

## Example

Input string `obenquillo`. Using my test code the first output string is `8benquifllo` and the last is `o^be9quillo`. There are 1871386 different strings in the output.

## My PC

I have an AMD Ryzen 5 3400G running Ubuntu 20.04.

## Winning

The fastest code wins.

# League table

* My test Python code. 14.00s
* **C++** by the default. 0.15s. Bounty awarded.
* **C** by ngn. 0.07s
* **Python** by ReedsShorts sped up by ovs. 10.5s
* **Rust** by wizzwizz4 . 2.45s

# Answer
> 11 votes
# C

```
cat >a.c <<.
#define _(a...) {return({a;});}
#define F(i,x,n,a...) for(I i=(x),n_=(n);i<n_;i++){a;}
#define i(a...) F(i,0,a)
#define j(a...) F(j,0,a)
#define k(a...) F(k,0,a)
#define I(a...) F(i,a)
#define S static
#define O const
#define mc __builtin_memcpy
#define sl __builtin_strlen
typedef void V;typedef char C;typedef int I;

#include<sys/syscall.h>
#define M1(x) #x
#define M2(x) M1(x)
#define h(x,a...) ".globl "#x";"#x":"a"mov $"M2(SYS_##x)",%rax;syscall;ret;"
asm(".globl _start;_start:pop %rdi;mov %rsp,%rsi;call main;"h(write)h(exit));I write(I,C*,I);V exit(I);
V*memcpy(V*x,O V*y,I n)_(C*a=x;O C*b=y;i(n,a[i]=b[i])a)I strlen(O C*s)_(I r=0;while(*s++)r++;r)

S O C A0=32,A1=126+1,AN=A1-A0;S C o0[1<<20],*o=o0;
S V rpt(C*a,I n,I m){m*=n;while(2*n<m){mc(a+n,a,n);n+=n;}mc(a+n,a,m-n);}
S I fd(C*s,I n,I p)_(i(p,j(n,*o++=s[j+(i<=j)]))p)
S I fc(C*s,I n,I p)_(mc(o,s,n+1);rpt(o,n+1,p*AN);I(A0,A1,j(p,o[j]=i;o+=n+1))p)
S I fi(C*s,I n,I p)_(p++;i(p,j(n+2,o[i*(n+2)+j]=s[j-(i<j)]))rpt(o,p*(n+2),AN);I(A0,A1,j(p,o[j]=i;o+=n+2))p)
I main(I c,C**v)_(S C s[32];I n=sl(v[1]);mc(s,v[1],n);s[n]=10;S typeof(fd)*f[]={fd,fc,fi};
 i(3,o=o0;I g=f[i](s,n,n);j(g*(i?AN:1),C*b=o;k(3,f[k](o0+(n+i)*j,n+i-1,j%g))write(1,b,o-b);o=b))
 exit(0);0)
.
clang -O3 -march=native -nostdlib -ffreestanding a.c && strip a.out -R .comment
time ./a.out abcdefghijklmnop >/dev/null

```

Try it online!

for the record, here's why this answer didn't win the bounty: https://chat.stackexchange.com/transcript/message/56646474#56646474

# Answer
> 4 votes
# C++ ('C with operator overloading')

edit: no longer outputs any duplicates if the set of characters allowed for insertions and substitutions doesn't intersect with the string's character set! (further improvement will probably require something smarter)
edit2: now even less duplicates: doesn't consider cases like inserting `abcd` -\> `abbcd` twice
edit3: tiny optimization in bufprint. I don't know how to optimize it further :(
edit4: optimized bufprint some more; edit5: found a better bufsize

```
#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>

const char rStart = 32; //for testing purposes, I often set these to 48 and 49
const char rEnd = 126;
const bool enableio = true;
const int bufsize = 524288;
//char printbuf[bufsize];
int printbuf[bufsize / 32][8]; //using a size of 24 bytes per fixed-length string caused a SIMD unaligned store and was slightly slower
int printbufi = 0;
void bufflush()
{
    if(enableio) fwrite(printbuf, 32, printbufi, stdout);
    printbufi = 0;
}
void bufprint(const char* x) //not confusing because printbuf is the print buffer and bufprint prints using the buffer
{
    //most of the time is spent in this function
    if(printbufi >= bufsize/32 - 1)
        bufflush();
    __builtin_memcpy(&printbuf[printbufi], x, 20);
    //printbuf[printbufi][5] = 0x0a0a0a0a; //not necessary! it's possible to just set these newlines in the beginning and never change them again
    printbufi++;
    //bufflush();
}
struct string //not null-terminated
{
    char data[20] = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 };
    int len;
    bool operator < (const string& rhs) const
    {
        return memcmp(data, rhs.data, 24) < 0;
    }
    bool operator == (const string& rhs) const
    {
        const uint64_t* p1 = (const uint64_t*)this, *p2 = (const uint64_t*)&rhs;
        bool eq = p1[0] == p2[0] && p1[1] == p2[1] && p1[2] == p2[2];
        return eq;
    }
    string insert(int i, char c) const
    {
        string copy;
        copy.len = len + 1;
        for(int j = 0; j < i; j++)
            copy[j] = data[j];
        for(int j = i; j < len; j++)
            copy[j+1] = data[j];
        copy[i] = c;
        return copy;
    }
    string prepend(char c) const
    {
        string copy;
        copy.len = len + 1;
        for(int j = 0; j < len; j++)
            copy[j+1] = data[j];
        copy[0] = c;
        return copy;
    }
    string pop_front() const
    {
        string copy;
        copy.len = len - 1;
        for(int j = 0; j < len-1; j++)
            copy[j] = data[j+1];
        return copy;
    }
    string erase(int i) const
    {
        string copy;
        copy.len = len - 1;
        for(int j = 0; j < i; j++)
            copy[j] = data[j];
        for(int j = i; j < len; j++)
            copy[j] = data[j+1];
        return copy;
    }
    inline char& operator[](int i)
    {
        //if(i >= len) while(true) throw "abc";
        return data[i];
    }
    void print() const
    {
        bufprint(data);
    }
};
void changeloop(string x, int skip = -2) //all strings exactly 1 change away
{
    for(int i = 0; i < x.len; i++)
    {
        if(i == skip || i == skip+1) continue;
        char oc = x[i];
        for(int nc = rStart; nc <= rEnd; nc++)
        {
            if(nc == oc) continue;
            x[i] = nc, x.print();
        }
        x[i] = oc;
    }
}
void changeloop2(string x, int skip = -2) //same with different skip
{
    for(int i = 0; i < x.len; i++)
    {
        if(i == skip) continue;
        char oc = x[i];
        for(int nc = rStart; nc <= rEnd; nc++)
        {
            if(nc == oc) continue;
            x[i] = nc, x.print();
        }
        x[i] = oc;
    }
}
void insertloop(string x, int max = INT_MAX) //all strings exactly 1 insertion away
{
    //example:
    //?abcd
    //a?bcd
    //ab?cd
    //abc?d
    //abcd?
    //it can be observed that each character simply iterates over all possible values, and then gets set to the ith character of the string
    string s = x.prepend(x[0]);
    max = std::min(max, s.len);
    for(int i = 0; i < max; i++)
    {
        for(char nc = rStart; nc <= rEnd; nc++)
        {
            if(i != 0 && x[i-1] == nc) continue;
            s[i] = nc, s.print();
        }
        if(i < x.len) s[i] = x[i];
    }
}
void deleteloop(string x, int max = INT_MAX)
{
    //example:
    //bcde
    //acde
    //abde
    //abce
    //abcd
    //erase first character, print and then copy the original character n-1 times
    string s = x.pop_front();
    s.print();
    max = std::min(max, x.len - 1);
    for(int i = 0; i < max; i++)
    {
        s[i] = x[i];
        s.print();
    }
}
void dist1(string x)
{
    x.print();
    changeloop(x);
    insertloop(x);
    deleteloop(x);
}
//options:
//insert
//insert, change
//insert, insert
//change
//change, change
//delete
//strings with distance at most 1 from delete
void dist2(string x)
{
    string s = x.prepend(x[0]);
    for(int i = 0; i < x.len+1; i++)
    {
        for(char nc = rStart; nc <= rEnd; nc++)
        {
            //string s = x.insert(i, nc);
            if(i != s.len-1 && s[i+1] == nc) continue;
            s[i] = nc;
            //s[s.len] = 0;
            s.print(); //insert
            insertloop(s, i+1); //insert, insert. only do the second insert before this one
            changeloop(s, i); //insert, change. the change can be anywhere except i and i+1
        }
        if(i < x.len) s[i] = x[i];
    }
    //changeloop(x); //change. can always be replaced by delete->reinsert
    for(int i = 0; i < x.len; i++)
    for(int j = i+1; j < x.len; j++)
    {
        char oci = x[i], ocj = x[j];
        for(int nci = rStart; nci <= rEnd; nci++)
        for(int ncj = rStart; ncj <= rEnd; ncj++)
        {
            if(nci == oci) continue;
            if(ncj == ocj) continue;
            x[i] = nci; x[j] = ncj;
            x.print(); //change, change
        }
        x[i] = oci; x[j] = ocj;
    }
    s = x.pop_front();
    s.print();
    changeloop(s);
    insertloop(s);
    for(int i = 0; i < x.len-1; i++)
    {
        s[i] = x[i];
        //s[s.len] = 0;
        s.print();
        changeloop2(s, i);
        insertloop(s);
        deleteloop(s, i); //deletion must be before i
    }
}

int main(int argc, char*argv[])
{
    if(argc < 2)
    {
        printf("input the string as a command line argument! :(\n");
        return 1;
    }
    memset(printbuf, 0x0a, sizeof(printbuf));
    string s; strcpy(s.data, argv[1]); s.len = strlen(argv[1]);
    s.data[s.len] = 10; //fix the null byte that should not be there
    //for(int i = 0; i < 200; i++)
    //{
    //  dist2(s);
    //  fprintf(stderr, "%d\r", i);
    //}
    dist2(s);
    bufflush();
}

```

This outputs many empty lines between strings (to avoid unaligned memory writes to the IO buffer). This outputs much fewer duplicates than the C answer: for `abcdefghijklmnop` the C answer outputs 10237362 lines, and my answer outputs only ~~4920334~~ ~~4774446~~ 4724312 non-empty lines, while only 4720038 are necessary. I compile with `g++ a.cpp -std=c++17 -march=native -Ofast -no-pie -fno-stack-protector`.

# Answer
> 3 votes
# Python 3

```
cat >a.py <<.
strs=[input()]
def a(b):
    new = []
    for x in range(32, 127):
        c = chr(x)
        for strn in b:
            for y in range(0, len(strn)):
                start = strn[:y]
                end = strn[y+1:]
                new.append(start + c + end)
                new.append(start + end)
                new.append(start + c + strn[y:])
            new.append(strn + c)
    return new
print(len(a(set(a(strs)))))
.
time python3 a.py <<<abcdefghijklmnop

```

Try it online!

Optimized by ovs, thanks.

# Answer
> 3 votes
# Rust

Tested with `rustc 1.51.0-nightly (e22670468 2020-12-30)`.
Must be compiled with `-O1` (or above) so functions are properly inlined, or it segfaults.

Please build with `cargo build`, then time the binary in `target/debug/q216902`. It's segfaulting in release mode at the moment, and I don't know why.

## `Cargo.toml`

```
[package]
name = "q216902"
version = "0.1.0"
authors = ["wizzwizz4"]
edition = "2018"

[dependencies]
rlibc = "1.0.0"

[profile.dev]
debug-assertions = true
opt-level = 1
panic = "abort"

[profile.release]
panic = "abort"
# debug = 2

```

## `main.rs`

```
#![feature(asm)]
#![feature(const_in_array_repeat_expressions)]
#![feature(const_maybe_uninit_assume_init)]
#![feature(link_args)]
#![feature(naked_functions)]
#![feature(test)]
#![no_std]
#![no_main]

#[allow(unused_attributes)]
#[link_args = "-nostartfiles"]
extern "C" {}

extern crate rlibc;

use core::convert::TryInto;
use core::hint::{black_box, spin_loop, unreachable_unchecked};
use core::panic::PanicInfo;
use core::ptr;
use core::slice;
use core::sync::atomic::{AtomicUsize, fence, Ordering};
use core::mem::MaybeUninit;

static PRINTABLES: [u8; 95] = *b" !\"#$%&'()*+,-./0123456789:;<=>?\
                                  @ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_\
                                  `abcdefghijklmnopqrstuvwxyz{|}~";
const FRAMECOUNT: usize = 4;
static mut FRAMES: [Frame; FRAMECOUNT] = [
    unsafe { MaybeUninit::<Frame>::uninit().assume_init() }; FRAMECOUNT
];

static FRAMELENS: [AtomicUsize; FRAMECOUNT] = [
    AtomicUsize::new(0); FRAMECOUNT
];

#[repr(C)]
struct iovec {
    iov_base: *const u8,
    iov_len: usize
}

const FRAMESIZE: usize = 256;
#[repr(C)]
struct Frame {
    iovecs: [MaybeUninit<iovec>; FRAMESIZE]
}

#[no_mangle]
#[naked]
pub unsafe extern "C" fn _start() -> ! {
    // Escape naked without clobbering stack pointer
    // https://fasterthanli.me/series/making-our-own-executable-packer/part-12
    asm!(
        "mov rdi, rsp",
        "call main",
        options(noreturn)
    );
}

#[no_mangle]
pub extern "C" fn main(stack: *const u8) -> ! {
    let input: &'static [u8] = unsafe {
        let arg1 = *stack.offset(16).cast();
        slice::from_raw_parts(arg1, cstr_strlen_cheat(arg1))
    };
    unsafe {
        spawn_printer();
    }

    let mut frame_i = 0;
    let mut frame_j = 0;
    let mut frame = unsafe { get_frame(0) };

    macro_rules! main_write {
        (@iovec $iov: expr) => {{
            frame.iovecs[frame_j] = MaybeUninit::new($iov);
            frame_j += 1;
            if frame_j > FRAMESIZE {
                unsafe { unreachable_unchecked(); }
            }
            if frame_j == FRAMESIZE {
                unsafe { write_frame(frame, frame_i, FRAMESIZE); }
                frame_j = 0;
                frame_i += 1;
                frame_i %= FRAMECOUNT;
                frame = unsafe { get_frame(frame_i) };
            }
        }};

        (@single $slice: expr) => {{
            main_write!(
                @iovec
                iovec {
                    iov_base: &$slice[0],
                    iov_len: $slice.len()
                }
            );
        }};

        ($($x: expr),*) => {{
            $(
                main_write!(@single $x);
            )*
        }};
    }

    macro_rules! main_writeln {
        ($($x: tt)*) => {{
            main_write!($($x)*);
            main_write!(b"\n");
        }};
    }

    ///////////
    // No-op ///
    //   No-op
    // Insert //
    //   I.
    //   .I.
    //   .I
    // Delete /////////
    //   Predel
    //   Delete
    //   Appdel
    // Insert insert //
    //   II.
    //   I.I.
    //   I.I
    //   .II.
    //   .I.I.
    //   Insert append
    //   Append append
    // Insert delete ////// (also includes Substitute)
    //   Prepend predel
    //   Prepend delete
    //   I.D
    //   Insert predel
    //   Insert delete
    //     .I.D.
    //     .S.
    //     .D.I.
    //   Insert appdel
    //   D.I
    //   Append delete
    //   .S
    // Insert substitute //////
    //   IS.
    //   I.S.
    //   Prepend substappend
    //   S.I.
    //   .SI.
    //   .S.I.
    //   Insert substitute
    //   .I.S
    //   Subsprepend append
    //   .S.I
    //   .SI
    // Substitute substitute //
    //   SS.
    //   .SS.
    //   .SS
    //   S.S
    //   S.S.
    //   .S.S.
    //   .S.S
    // Delete delete //////////
    //   Del2 XX.
    //   Del2 .XX.
    //   Del2 .XX
    //   Del2 X.X
    //   Del2 X.X.
    //   Del2 .X.X.
    //   Del2 .X.X
    // Delete substitute //
    //   DS.
    //   .DS.
    //   .DS
    //   D.S
    //   S.D
    //   D.S.
    //   S.D.
    //   .D.S.
    //   .S.D.
    //   .D.S
    //   .S.D
    ///////////////////////

    let len = input.len();

    main_writeln!(input);  // No-op
    main_writeln!(input[1..]);  // Predel
    main_writeln!(input[2..]);  // Del2 XX.
    main_writeln!(input[.. len-1]);  // Appdel
    main_writeln!(input[.. len-2]);  // Del2 .XX
    main_writeln!(input[1 .. len-1]);  // Del2 X.X

    for i in 1 .. len-1 {
        main_writeln!(input[..i], input[i + 1..]);  // Delete
    }

    for i in 1 .. len-2 {
        main_writeln!(input[..i], input[i+2 ..]);  // Del2 .XX.
        main_writeln!(input[1 .. i+1], input[i+2 ..]);  // Del2 X.X.
        main_writeln!(input[..i], input[i+1 .. len-1]); // Del2 .X.X

        for j in i+2 .. len-1 {
            // Del2 .X.X.
            main_writeln!(input[..i], input[i+1 .. j], input[j+1 ..]);
        }
    }

    for ai in 0..PRINTABLES.len() {
        let a = &PRINTABLES[ai .. ai+1];

        main_writeln!(a, input);  // I.
        main_writeln!(input, a);  // .I

        for i in 1..len {
            main_writeln!(input[..i], a, input[i..]);  // .I.
        }

        for bi in 0..PRINTABLES.len() {
            let b = &PRINTABLES[bi..bi + 1];

            main_writeln!(a, b, input);  // II.
            main_writeln!(a, b, input[1..]);  // IS.
            main_writeln!(a, b, input[2..]);  // SS.
            main_writeln!(a, input, b);  // I.I
            main_writeln!(a, input[.. len-1], b);  // Prepend substappend
            main_writeln!(a, input[1 ..], b); // Subsprepend append
            main_writeln!(a, input[1 .. len-1], b); // S.S
            main_writeln!(input, a, b);  // Append append
            main_writeln!(input[.. len-1], a, b);  // .SI
            main_writeln!(input[.. len-2], a, b);  // .SS

            for i in 1..len {
                main_writeln!(a, input[..i], b, input[i..]);  // I.I.
                main_writeln!(input[..i], a, input[i..], b);  // Insert append
                main_writeln!(input[..i], a, b, input[i..]);  // .II.
            }

            for i in 1 .. len-1 {
                main_writeln!(a, input[..i], b, input[i+1 ..]);  // I.S.
                main_writeln!(a, input[1 .. i+1], b, input[i+1 ..]); // S.I.
                main_writeln!(input[..i], a, input[i .. len-1], b); // .I.S
                main_writeln!(input[..i], a, b, input[i+1..]);  // .SI.

                for j in i+1 .. len {
                    // .I.I.
                    main_writeln!(input[..i], a, input[i..j], b, input[j..]);
                }

                for j in i+2 .. len {
                    // .S.I.
                    main_writeln!(
                        input[..i], a, input[i+1 .. j], b, input[j..]
                    );
                }

                for j in i+2 .. len-1 {
                    // .S.S.
                    main_writeln!(
                        input[..i], a, input[i+1 .. j], b, input[j+1 ..]
                    );
                }

                for j in 1..i {
                    // Insert substitute
                    main_writeln!(input[..j], a, input[j..i], b, input[i+1..]);
                }

                main_writeln!(input[..i], a, input[i+1 ..], b);  // .S.I
            }

            for i in 1 .. len-2 {
                main_writeln!(input[..i], a, b, input[i+2 ..]);  // .SS.
                main_writeln!(a, input[1 .. i+1], b, input[i+2 ..]);  // S.S.
                main_writeln!(input[..i], a, input[i+1 .. len-1], b);  // .S.S
            }
        }

        main_writeln!(a, input[1..]);  // Prepend predel
        main_writeln!(a, input[2..]);  // DS.
        main_writeln!(a, input[.. len-1]);  // I.D
        main_writeln!(a, input[1 .. len-1]);  // S.D
        main_writeln!(input[1..], a);  // D.I
        main_writeln!(input[1 .. len-1], a);  // D.S
        main_writeln!(input[.. len-1], a);  // .S
        main_writeln!(input[.. len-2], a);  // .DS

        for i in 1..input.len() - 1 {
            main_writeln!(a, input[..i], input[i+1 ..]);  // Prepend delete
            main_writeln!(input[..i], input[i+1 ..], a);  // Append delete
            main_writeln!(input[1 .. i+1], a, input[i+1 ..]); // Insert predel
            main_writeln!(input[..i], a, input[i .. len-1]);  // Insert appdel
            main_writeln!(input[..i], a, input[i+1 ..]);  // .S.

            for j in 1..i {
                // .I.D.
                main_writeln!(input[..j], a, input[j..i], input[i+1 ..]);
            }

            for j in i+2..len {
                // .D.I.
                main_writeln!(input[..i], input[i+1 .. j], a, input[j..]);
            }
        }

        for i in 1 .. len-2 {
            main_writeln!(input[..i], a, input[i+2 ..]);  // .DS.
            main_writeln!(input[1 .. i+1], a, input[i+2 ..]);  // D.S.
            main_writeln!(a, input[1 .. i+1], input[i+2 ..]);  // S.D.
            main_writeln!(input[..i], input[i+1 .. len-1], a);  // .D.S
            main_writeln!(input[..i], a, input[i+1 .. len-1]); // .S.D

            for j in i+2 .. len-1 {
                // .D.S.
                main_writeln!(input[..i], input[i+1 .. j], a, input[j+1 ..]);

                // .S.D.
                main_writeln!(input[..i], a, input[i+1 .. j], input[j+1 ..]);
            }
        }
    }

    unsafe { write_frame(frame, frame_i, frame_j); }

    while FRAMELENS[frame_i].load(Ordering::SeqCst) > 0 {
        sched_yield();
    }
    unsafe { exit_group(0); }
}

/// strlen, if the string's length is >= 10 and <= 16.
#[inline]
unsafe fn cstr_strlen_cheat(ptr: *const u8) -> usize {
    for i in 10..=16 {
        if *ptr.offset(i) == 0 {
            match i.try_into() {
                Ok::<usize, _>(i) => return i,
                Err(_) => unreachable_unchecked()
            }
        }
    }
    unreachable_unchecked();
}

/// Gets a frame for writing, assuming nobody else has it.
#[inline]
unsafe fn get_frame(i: usize) -> &'static mut Frame {
    loop {
        let count = FRAMELENS[i].load(Ordering::SeqCst);
        if count == 0 {
            break;
        }
        sched_yield();
    }
    &mut FRAMES[i]
}

#[inline]
unsafe fn write_frame(_frame: &'static mut Frame, i: usize, count: usize) {
    FRAMELENS[i].store(count, Ordering::SeqCst);
}

#[inline(never)]  // for correctness
unsafe extern "C" fn spawn_printer() {
    let stack_pointer: *const u8;
    asm!(
        "mov {0}, rsp",
        out(reg) stack_pointer
    );
    let new_stack = stack_pointer.offset(-0x1000);
    let spawn_addr = (new_stack as *mut (extern "C" fn() -> !)).offset(1);
    ptr::write(spawn_addr, printer);
    clone(new_stack)
}

extern "C" fn printer() -> ! {
    loop {
        for i in 0..FRAMECOUNT {
            let mut count;
            loop {
                count = FRAMELENS[i].load(Ordering::SeqCst);
                if count > 0 {
                    break;
                }
                // sched_yield();
            }
            fence(Ordering::SeqCst);
            unsafe {
                writev((&FRAMES[i].iovecs[0]).as_ptr().cast(), count);
            }
            FRAMELENS[i].store(0, Ordering::SeqCst);
        }
    }
}

// https://thevivekpandey.github.io/posts/2017-09-25-linux-system-calls.html
#[inline]
unsafe fn writev(iovecs: *const iovec, count: usize) {
    asm!(
        "syscall",
        in("rax") 20,
        in("rdi") 1,
        in("rsi") iovecs,
        in("rdx") count,
        options(nostack)
    );
}

#[inline]
fn exit(code: i32) -> ! {
    unsafe {
        asm!(
            "syscall",
            in("rax") 60,
            in("rdi") code,
            options(nostack, noreturn)
        );
    }
}

#[inline]
unsafe fn exit_group(code: i32) -> ! {
    asm!(
        "syscall",
        in("rax") 231,
        in("rdi") code,
        options(nostack, noreturn)
    );
}

#[inline]
unsafe fn just_exit() -> ! {
    asm!(
        "syscall",
        in("rax") 231,
        options(nostack, noreturn)
    )
}

#[inline]
fn sched_yield() {
    unsafe {
        asm!(
            "syscall",
            in("rax") 24,
            options(nostack)
        )
    }
}

/// Wait for signal.
#[inline]
fn pause() {
    unsafe {
        asm!(
            "syscall",
            in("rax") 34,
            options(nostack)
        )
    }
}

#[inline(always)]  // for correctness
unsafe fn clone(new_stack: *const u8) {
    const CLONE_FILES: u64 = 0x400;  // Keep stdout as fd 1
    const CLONE_FS: u64 = 0x200;
    const CLONE_IO: u64 = 0x80000000;  // I/O scheduling efficiency
    const CLONE_PARENT: u64 = 0x8000;
    const CLONE_SIGHAND: u64 = 0x800;
    const CLONE_THREAD: u64 = 0x10000;  // Same thread group
    const CLONE_VM: u64 = 0x100;  // Same memory map

    const flags: u64 = CLONE_FILES | CLONE_IO
                       | CLONE_VM
                       | CLONE_THREAD
                       | CLONE_FS | CLONE_PARENT | CLONE_SIGHAND;
    asm!(
        "syscall",
        in("rax") 56,
        in("rdi") flags,
        in("rsi") new_stack,
        options(nostack)
    );
    return;
}

#[panic_handler]
fn panic(_info: &PanicInfo) -> ! {
    unsafe {
        if cfg!(debug_assertions) {
            // just_exit();
        }
        // unreachable_unchecked();
        asm!(
            "ud2",
            options(nostack, noreturn)
        )
    }
}

```

This is cleaner code; I'm making a better version, hopefully less segfaulty in release mode. I also haven't tweaked the `FRAMECOUNT` and `FRAMESIZE` parameters for optimal speed.

---
Tags: string, fastest-code
---