The Rule 110 Elementary Cellular Automata in TypeScript’s Type-Level Functions

rule110.ts

// TypeScript Playground link:
//
// https://www.typescriptlang.org/play/?#code/C4TwDgpgBAogHpAxsAPAFShOwIDsAmAzlMAE4CuEAfFALxRoDcAUKJLAI7kCGANigA0ANFACaNegAp0VSQEo6NDFhwFiAqAH4oARigAuKACYFKvESgz5ihpmzniorboPHmUZ2UrvXAMz6EECxs0AByAPaoyvZqUABG4eG8ENy4ErZmsf68gZ4U0IbZgSys4NAAysDcOHRQAEQ6dVAAPvUADHUlIVAASuTJOjpttQDePnVtk3WGE3VC45ONM43zHhND0-UrC4ObDXPjQx0zHatbbUtbB2uDx1dnDbsnBwC+XWVQoSoA4ngQpNUAJbhXDoOyqCyEMiA3AAcxEAEEAMJI8EOKBQ0gw2G1Op1CQ+aIQ4h4lpQSrVaCtAAGABIRhScC96YyIC9qT5tMikT5DET0XSRjDfP8oAAJFL4PSZCys5lC3Ai0jiyVGNGxOX04WiiXcfAAZnVsqqTK1itFPQgUPZPg82i+2F+uH+QJBKEFuvwRnlnv18st1upIkF3P9-QgtwA2h7JTofar43q-dSALrsqi21zOgBu-3e7AA+kZhvR4EhUDAuHwULMRA7gE6XcBgaCJlMqB3gh8i3pSwgIMgUJWePx9nWfn8Ac23W3Gh2qF3C0Y1X3y0Oq6OVp8J86py2axcOvPF9Ai4bVwOKxua1v6429zOLnPO6UlwAWWply-rkcHubbx1J1dVsjnxF9uiLABWT9+0HYdqzHACGyA6cQIuMCF1fU8jAANhgtd4M3f87xQ-dHiPcDuyMAB2fDv0Iv9x0A3dgJvXZj2YLCoALfUS1gWCr1-NtiJ3JsyMmdtKMLfVe34gjr3WETmLEx9Fgwk9uP1Fc5PohTdiY5CWNQg9D3UriePPHS4L029RIfVtFmfTCIP1D8L2soSNgM+9WPWSTnO7fVoPcwSEP0pCfOMvynI0ni8JCn8wts5T7IPW4zJc2iEoYhpTgi0jH0GGLzP1AAOOiPIQqZvIKtD-Ni-UAE4KtC0d0JqoyyKOYqXIRFrEs3ZLDJUtCNg4lyACF+py8KSM6mchnYqTT31VFsr0vK5pGtj6pKgARaabKU4bUvInrApgQ6hPa-L5pA9LxsCgAxK6qs2uzfKK4quKe8hgHIUgIAAeV8MEZWITFsREAAFPV8GxI0IehOFcX-blEYxZHYUjFNahxgkPH5WI8UzLkUUzQxfv+wGQZQLbUrQKhg3pWH8HhuEXigIMoEjAA6fnuWZkZWfZ2F5TQeURexdkUwzcy3z4r9Kv4HGRCpgHgdBvFHsLN9ZKV1qUEjWYUzVv6Ndp2YddPN9tINgajf2U2oHVmmtfO3XLPthjjamZ3Xc1kyMu7N83Ksw3fcaf3zbdtLg914Lw4d42Nmj6nA9y+ObfipOfceOo04t93vogyDFYE5O2zypphgLs308tiSs+4yD9YrvO1JEJo9Drl2Y4ztTrZbu32+vSPq5cXuA8bsblpbr3R9-SOt27+pC9j9YPdPSCw+9sfcon2v14z0Ch4LSDE73pfcpXyfj8txbm-PnOr+rFOvPqO-66Lnan8grLc77yKv+Gua9v4b2ARxcyOFy7yWvhJQ+R9wEDybmfHCbc4FvyrrfC4YC+4Ny1hJLe3EcIj0wSrWcE9Bh4OnoQ0yaCF7kMdo5EBuge73zoUtAKhYcK70Xlgw8VCkH4J-n5Ci3DTw4Uvvwihh5b7UKnv3Ge6E0Evxkcw9KXc2E0KUYQh6c8Cw4QAa-WRwCtFDB0QQtKXDYo4XKuta+RxEGWNEU4p+OFmoOKwd1VhuDFFWIPsQwxfUvEUMWlQ9hyCH70IMThKaoTHaLXkZEkRECnzuLWoAxxoFzHCNoTtcRtiDoJPfjdbuKT8lnXcZdEpjwP41wqbotis8JEkJerUr6vi8lNLqSXbs1FYG6XgQgrptctFQGGC4jeCDCnmWohgoZAiiFdJ7uMvQUyUGDwMdRMhizZGLEPgotZawOEmRia0gs1FGF7OYSwrRT56jHI2Y3FhZ9qJ8KYb7QRrDbiPM-i4Z5nDdoQWotIz5lDkmrP+ZM-xoiDlBOomo8FjkIlQqaBMk5UTOEtNitRYx6ivlmM-r81hALYXTKfAi+xWSBFuNyWM6FmLUkDzcW8zxNLTGd2JX4p55KWVbIudREJHKNGmXMUcxlgK0rnNxfEkV49wrlLRR4GFpzooIsySYjROTiUWNJesvlM9T7bOKfKzeZS2HKoxVK81CKalmspUIq1Bq1WOqftRdpDrOn0r+ei1VWLrE2PMqVQZytEkjPuZMX1KqmWVKcbMiCpUFlhpTssyNzrY09KcUE0quyU2BMORmm13UE3dlKtc-N3UcESvRS6gNgSc0fJuamnV5SGW1szQE8JpbCylTBc2m+FqirRutYa92cin6lSRQOpJqKR3+uZdE-RFzSr4vBUk5J7aPB1sXeOyBBjSrUq1aU6q3Kt2jrVbcYFZb2XHvIkOnl-yd1xp8WfUqwq723HqZa+dnbXHhMnXKz9SSfk1pjcWkDb7NUErqaehp57n1ZqvZO01wHH73LA2Sy9X7J32rQ9+xYI7ENdqKj208pVPX4ZwVG0lC6X37swlxGAwAAAWop6C9OzSizoXFhUNo6BpAOwr8mCmY2x0g8oETyjE-8aTrHZPUkYxBRqobDacaISiqtlKr2CK-V9DTT48pCcjG0WWFzGrJrUxMg5hmvobp01puzBm9NQuMzoMzsVGp5qsxMlzDmHOaf0zZvzFi-nGaMB58yjUK0+ctVx2zgXSPBfs9mjwYX+4IkjPqSLymm1hvRSq3TKXtPxZC85tL6X06ZbfDl7sjV+35Yq2wkrRCAu2aC0V3BFX-zGcgrVwsjVp2Naa0lzrjmOvjeoU1nrGXIw4X66eRqa6bkFYq2N-TTnkstcmdN5BmXqILe4o1I96jVsVeK45UrF3DxNbSzNqrkZSoeaAA
//
// Matthew Cook’s paper proving that the Rule 110 elementary cellular automation is universal:
//
// https://raganwald.com/assets/rule-110-matthew-cook.pdf

type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
  ? true
  : false;
type Not<T extends boolean> = T extends false ? true : false;

type State = "1" | "0";

type Rule110 = {
  "000": "0",
  "001": "1",
  "010": "1",
  "011": "1",
  "100": "0",
  "101": "1",
  "110": "1",
  "111": "0",
};

type NextGeneration<T extends string, ACC extends string = ""> =
  T extends "" | State | `${State}${State}`
  ? ACC
  : T extends `${infer Head1 extends State}${infer Head2 extends State}${infer Head3 extends State}${infer Rest}`
    ? NextGeneration<`${Head2}${Head3}${Rest}`, `${ACC}${Rule110[`${Head1}${Head2}${Head3}`]}`>
    : never;

type _20 = Expect<Equal<"0", NextGeneration<"000">>>;
type _21 = Expect<Equal<"1", NextGeneration<"001">>>;
type _22 = Expect<Equal<"1", NextGeneration<"010">>>;
type _23 = Expect<Equal<"1", NextGeneration<"011">>>;
type _24 = Expect<Equal<"0", NextGeneration<"100">>>;
type _25 = Expect<Equal<"1", NextGeneration<"101">>>;
type _26 = Expect<Equal<"1", NextGeneration<"110">>>;
type _27 = Expect<Equal<"0", NextGeneration<"111">>>;

type _30 = Expect<Equal<"00", NextGeneration<"0000">>>;
type _31 = Expect<Equal<"01", NextGeneration<"0001">>>;
type _32 = Expect<Equal<"11", NextGeneration<"0010">>>;
type _33 = Expect<Equal<"11", NextGeneration<"0011">>>;
type _34 = Expect<Equal<"10", NextGeneration<"0100">>>;
type _35 = Expect<Equal<"11", NextGeneration<"0101">>>;
type _36 = Expect<Equal<"11", NextGeneration<"0110">>>;
type _37 = Expect<Equal<"10", NextGeneration<"0111">>>;
type _38 = Expect<Equal<"00", NextGeneration<"1000">>>;
type _39 = Expect<Equal<"01", NextGeneration<"1001">>>;
type _3A = Expect<Equal<"11", NextGeneration<"1010">>>;
type _3B = Expect<Equal<"11", NextGeneration<"1011">>>;
type _3C = Expect<Equal<"10", NextGeneration<"1100">>>;
type _3D = Expect<Equal<"11", NextGeneration<"1101">>>;
type _3E = Expect<Equal<"01", NextGeneration<"1110">>>;
type _3F = Expect<Equal<"00", NextGeneration<"1111">>>;

type FutureOf<T extends string, Padding extends string = "", ACC extends string[] = []> =
  T extends ""
    ? ACC
    : FutureOf<NextGeneration<T>, `${Padding} `, [...ACC, `${Padding}${T}${Padding}`]>

type _40 = Expect<Equal<[], FutureOf<"">>>;
type _41 = Expect<Equal<["0"], FutureOf<"0">>>;
type _42 = Expect<Equal<["1"], FutureOf<"1">>>;
type _43 = Expect<Equal<["00"], FutureOf<"00">>>;
type _44 = Expect<Equal<["01"], FutureOf<"01">>>;
type _45 = Expect<Equal<["10"], FutureOf<"10">>>;
type _46 = Expect<Equal<["11"], FutureOf<"11">>>;

type _50 = Expect<Equal<["000", " 0 "], FutureOf<"000">>>;
type _51 = Expect<Equal<["001", " 1 "], FutureOf<"001">>>;
type _52 = Expect<Equal<["010", " 1 "], FutureOf<"010">>>;
type _53 = Expect<Equal<["011", " 1 "], FutureOf<"011">>>;
type _54 = Expect<Equal<["100", " 0 "], FutureOf<"100">>>;
type _55 = Expect<Equal<["101", " 1 "], FutureOf<"101">>>;
type _56 = Expect<Equal<["110", " 1 "], FutureOf<"110">>>;
type _57 = Expect<Equal<["111", " 0 "], FutureOf<"111">>>;

type _60 = Expect<Equal<["0000", " 00 "], FutureOf<"0000">>>;
type _61 = Expect<Equal<["0001", " 01 "], FutureOf<"0001">>>;
type _62 = Expect<Equal<["0010", " 11 "], FutureOf<"0010">>>;
type _63 = Expect<Equal<["0011", " 11 "], FutureOf<"0011">>>;
type _64 = Expect<Equal<["0100", " 10 "], FutureOf<"0100">>>;
type _65 = Expect<Equal<["0101", " 11 "], FutureOf<"0101">>>;
type _66 = Expect<Equal<["0110", " 11 "], FutureOf<"0110">>>;
type _67 = Expect<Equal<["0111", " 10 "], FutureOf<"0111">>>;
type _68 = Expect<Equal<["1000", " 00 "], FutureOf<"1000">>>;
type _69 = Expect<Equal<["1001", " 01 "], FutureOf<"1001">>>;
type _6A = Expect<Equal<["1010", " 11 "], FutureOf<"1010">>>;
type _6B = Expect<Equal<["1011", " 11 "], FutureOf<"1011">>>;
type _6C = Expect<Equal<["1100", " 10 "], FutureOf<"1100">>>;
type _6D = Expect<Equal<["1101", " 11 "], FutureOf<"1101">>>;
type _6E = Expect<Equal<["1110", " 01 "], FutureOf<"1110">>>;
type _6F = Expect<Equal<["1111", " 00 "], FutureOf<"1111">>>;

type _70 = Expect<Equal<["00000", " 000 ", "  0  "], FutureOf<"00000">>>;
type _71 = Expect<Equal<["00001", " 001 ", "  1  "], FutureOf<"00001">>>;
type _72 = Expect<Equal<["00010", " 011 ", "  1  "], FutureOf<"00010">>>;
type _73 = Expect<Equal<["00011", " 011 ", "  1  "], FutureOf<"00011">>>;
type _74 = Expect<Equal<["00100", " 110 ", "  1  "], FutureOf<"00100">>>;
type _75 = Expect<Equal<["00101", " 111 ", "  0  "], FutureOf<"00101">>>;
type _76 = Expect<Equal<["00110", " 111 ", "  0  "], FutureOf<"00110">>>;
type _77 = Expect<Equal<["00111", " 110 ", "  1  "], FutureOf<"00111">>>;
type _78 = Expect<Equal<["01000", " 100 ", "  0  "], FutureOf<"01000">>>;
type _79 = Expect<Equal<["01001", " 101 ", "  1  "], FutureOf<"01001">>>;
type _7A = Expect<Equal<["01010", " 111 ", "  0  "], FutureOf<"01010">>>;
type _7B = Expect<Equal<["01011", " 111 ", "  0  "], FutureOf<"01011">>>;
type _7C = Expect<Equal<["01100", " 110 ", "  1  "], FutureOf<"01100">>>;
type _7D = Expect<Equal<["01101", " 111 ", "  0  "], FutureOf<"01101">>>;
type _7E = Expect<Equal<["01110", " 101 ", "  1  "], FutureOf<"01110">>>;
type _7F = Expect<Equal<["01111", " 100 ", "  0  "], FutureOf<"01111">>>;
type _80 = Expect<Equal<["10000", " 000 ", "  0  "], FutureOf<"10000">>>;
type _81 = Expect<Equal<["10001", " 001 ", "  1  "], FutureOf<"10001">>>;
type _82 = Expect<Equal<["10010", " 011 ", "  1  "], FutureOf<"10010">>>;
type _83 = Expect<Equal<["10011", " 011 ", "  1  "], FutureOf<"10011">>>;
type _84 = Expect<Equal<["10100", " 110 ", "  1  "], FutureOf<"10100">>>;
type _85 = Expect<Equal<["10101", " 111 ", "  0  "], FutureOf<"10101">>>;
type _86 = Expect<Equal<["10110", " 111 ", "  0  "], FutureOf<"10110">>>;
type _87 = Expect<Equal<["10111", " 110 ", "  1  "], FutureOf<"10111">>>;
type _88 = Expect<Equal<["11000", " 100 ", "  0  "], FutureOf<"11000">>>;
type _89 = Expect<Equal<["11001", " 101 ", "  1  "], FutureOf<"11001">>>;
type _8A = Expect<Equal<["11010", " 111 ", "  0  "], FutureOf<"11010">>>;
type _8B = Expect<Equal<["11011", " 111 ", "  0  "], FutureOf<"11011">>>;
type _8C = Expect<Equal<["11100", " 010 ", "  1  "], FutureOf<"11100">>>;
type _8D = Expect<Equal<["11101", " 011 ", "  1  "], FutureOf<"11101">>>;
type _8E = Expect<Equal<["11110", " 001 ", "  1  "], FutureOf<"11110">>>;
type _8F = Expect<Equal<["11111", " 000 ", "  0  "], FutureOf<"11111">>>;

type Ether = "11111000100110";
type A = "100110";
type FutureA = FutureOf<`${Ether}${A}${Ether}${Ether}`>;

type _90 = Expect<Equal<"111110001001101001101111100010011011111000100110", FutureA[0]>>;
type _91 = Expect<Equal<" 0001001101111101111100010011011111000100110111 ", FutureA[1]>>;
type _92 = Expect<Equal<"  01101111100011100010011011111000100110111110  ", FutureA[2]>>;
type _93 = Expect<Equal<"   111100010011010011011111000100110111110001   ", FutureA[3]>>;
type _94 = Expect<Equal<"    0010011011111011111000100110111110001001    ", FutureA[4]>>;
type _95 = Expect<Equal<"     11011111000111000100110111110001001101     ", FutureA[5]>>;
type _96 = Expect<Equal<"      111000100110100110111110001001101111      ", FutureA[6]>>;
type _97 = Expect<Equal<"       0100110111110111110001001101111100       ", FutureA[7]>>;
type _98 = Expect<Equal<"        10111110001110001001101111100010        ", FutureA[8]>>;