zachhardesty7 · February 4, 2022 00:04
diff --git a/index.ts b/index.ts
 // copyright 2022 Zach Hardesty

 // want to check this out in the TypeScript playground?
 // visit the following link to automatically see the latest version!
 // https://www.typescriptlang.org/play?jsx=0#gist/2bc7327353adb13e7b443f8c85113ba0

 // eventually a solution to day 16 of Advent of Code 2021 using only the compile-time
 // type system of TypeScript.
 // https://adventofcode.com/2021/day/16

 // TODO: implement proper subpacket parsing
 // TODO: implement solution for non binary inputs for operations

 // TODO:
 // test out using `& {}` to brand a primitive
 // i.e. prevent subtype reduction
 // e.g. prevent eating nevers

 // TODO:
 // test out using `{} &` to force TS to expand out recursive types

 // DEBUGGING HELP
 // https://blog.andrewbran.ch/debugging-the-type-script-codebase/
 // https://www.typescriptlang.org/docs/handbook/compiler-options.html
 // https://medium.com/jspoint/typescript-compilation-the-typescript-compiler-4cb15f7244bc
 // https://servingniches.org/posts/2019-05-28___debugging_serverside_typescript_with_webstorm/
 // https://github.com/microsoft/TypeScript/pull/45711 // recursive tail call optimization PR

 // DEBUGGING AST - maybe helpful, untested if it even works
 // https://mihailik.github.io/teapo/
 // https://astexplorer.net/

 type INPUT_0 = "D"
 type INPUT_1 = "D2FE28"
 type INPUT_2 = "NOT_HEX"

 type binaryMap = {
  "0": "0000"
  "1": "0001"
  "2": "0010"
  "3": "0011"
  "4": "0100"
  "5": "0101"
  "6": "0110"
  "7": "0111"
  "8": "1000"
  "9": "1001"

  A: "1010"
  B: "1011"
  C: "1100"
  D: "1101"
  E: "1110"
  F: "1111"
 }

 /**
 * v1 convert string literal of hex chars to binary string literal
 *
 * technically doesn't fail if last char isn't hex
 *
 * max length - 999 hex chars
 */
 // type hexToBin<
 //   S extends string,
 //   Out extends string = ""
 // > = S extends `${infer S0}${infer Rest}`
 //   ? S0 extends keyof binaryMap
 //     ? hexToBin<Rest, `${Out}${binaryMap[S0]}`>
 //     : never
 //   : Out

 /** v2 also checks last char is hex, thought this would give 1 extra max char but no difference */
 // type hexToBin<
 //   S extends string,
 //   Out extends string = ""
 // > = S extends `${infer S0}${infer Rest}`
 //   ? S0 extends keyof binaryMap
 //     ? Rest extends ""
 //       ? `${Out}${binaryMap[S0]}`
 //       : hexToBin<Rest, `${Out}${binaryMap[S0]}`>
 //     : never
 //   : never

 /**
 * v3 process 2 chars at the same time, half as much recursion
 *
 * max length - 1999 hex chars
 */
 type hexToBin<
  S extends string,
  Out extends string = "",
 > = S extends `${infer S0}${infer S1}${infer Rest}`
  ? S0 extends keyof binaryMap
    ? S1 extends keyof binaryMap
      ? hexToBin<Rest, `${Out}${binaryMap[S0]}${binaryMap[S1]}`>
      : never
    : never
  : S extends keyof binaryMap // only 0 or 1 chars left in input string
  ? `${Out}${binaryMap[S]}`
  : Out

 type INPUT_0_bin = Expect<hexToBin<INPUT_0>, "1101">
 type INPUT_1_bin = Expect<hexToBin<INPUT_1>, "110100101111111000101000">
 type INPUT_2_bin = Expect<hexToBin<INPUT_2>, never>

 //
 // #region - packet parsing
 //

 type Zero = "0"
 type One = "1"
 type Bit = Zero | One
 type Nibble = `${Bit}${Bit}${Bit}${Bit}`
 type Version = `${Bit}${Bit}${Bit}`

 type PacketTypeAny = `${Bit}${Bit}${Bit}`

 /** @version 1 */
 // type parseLitPacketBodyDebug<
 //   V extends string,
 //   Out extends string = ""
 // > = V extends `${infer More}${infer N0}${infer N1}${infer N2}${infer N3}${infer Rest}`
 //   ? More extends Zero
 //     ? [`${Out}${N0}${N1}${N2}${N3}`, Rest]
 //     : More extends One
 //     ? parseLitPacketBodyDebug<Rest, `${Out}${N0}${N1}${N2}${N3}`>
 //     : never
 //   : never

 /** @version 2 - use `Nibble`, maybe double infer at once is bad, but lazy match works here */
 // type parseLitPacketBodyDebug<
 //   V extends string,
 //   Out extends string = ""
 // > = V extends `${Bit}${Nibble}${infer Rest}`
 //   ? V extends `${infer More}${infer N}${Rest}`
 //     ? More extends Zero
 //       ? [`${Out}${N}`, Rest]
 //       : More extends One
 //       ? parseLitPacketBodyDebug<Rest, `${Out}${N}`>
 //       : never
 //     : never
 //   : never

 /** @version 3 - no `More`, nests better but 1 more `infer` */
 // type parseLitPacketBodyDebug<
 //   V extends string,
 //   Out extends string = "",
 // > = V extends `0${Nibble}${infer Rest}`
 //   ? V extends `0${infer N}${Rest}`
 //     ? [`${Out}${N}`, Rest]
 //     : never
 //   : V extends `1${Nibble}${infer Rest}`
 //   ? V extends `1${infer N}${Rest}`
 //     ? parseLitPacketBodyDebug<Rest, `${Out}${N}`>
 //     : never
 //   : never

 /** @version 4 - back to long infer list */
 type parseLitPacketBodyDebug<
  V extends string,
  Out extends string = "",
 > = V extends `0${infer N0}${infer N1}${infer N2}${infer N3}${infer Rest}`
  ? [`${Out}${N0}${N1}${N2}${N3}`, Rest]
  : V extends `1${infer N0}${infer N1}${infer N2}${infer N3}${infer Rest}`
  ? parseLitPacketBodyDebug<Rest, `${Out}${N0}${N1}${N2}${N3}`>
  : never

 type parseLitPacketDebug<B extends string> = B extends `${Version}100${infer Rest}`
  ? parseLitPacketBodyDebug<Rest>
  : never

 type INPUT_1_literal = Expect<parseLitPacketDebug<INPUT_1_bin>[0], "011111100101">

 type FourBit = `${Bit}${Bit}${Bit}${Bit}`
 /** NOTE: DON'T USE, forces subtype expansion of union of 35k str literals, 15 bits, follows a `0` */
 type LengthTypeTotal = `${FourBit}${FourBit}${FourBit}${Bit}${Bit}${Bit}`
 // might be some merit to some other approach like making a giant tuple or even a temporary one
 // to simplify having to see `Bit` so many times
 // type LengthTypeTotal2 = [Bit,Bit,Bit,Bit,Bit,Bit,Bit,Bit];
 // type LengthTypeTotal3 = [string, string, string];
 // type Test = "11100101" extends LengthTypeTotal2 ? "yes" : "no"
 // type Tester2<Bin> = Bin extends [...LengthTypeTotal3, ...infer U] ? "yes" : "no"
 // type Test2 = Tester2<["1","1","1","0","0","1","0","1"]>
 // type Tester3<Bin> = Bin extends [...LengthTypeTotal3, ...infer U] ? "yes" : "no"
 // type Test3 = Tester2<["1","1","1","0","0","1","0","1"]>

 /** NOTE: DON'T USE, forces subtype expansion of union of 35k str literals, 11 bits, follows a `1` */
 type LengthTypeChildren = `${FourBit}${FourBit}${Bit}${Bit}${Bit}`

 /** v1 */
 // type parseOpPacketBodyDebug<
 //   Val extends string
 //   // Out extends string = ""
 // > = Val extends `${infer LT}${infer Rest}`
 //   ? // > = Val extends `${infer LT}${L1 | L2}${infer Rest}`
 //     // ? L1 extends LengthTypeTotal
 //     LT extends Zero
 //     ? Rest extends `${infer B0}${infer B1}${infer B2}${infer B3}${infer B4}${infer B5}${infer B6}${infer B7}${infer B8}${infer B9}${infer B10}${infer B11}${infer B12}${infer B13}${infer B14}${infer RestRest}`
 //       ? [
 //           `${B0}${B1}${B2}${B3}${B4}${B5}${B6}${B7}${B8}${B9}${B10}${B11}${B12}${B13}${B14}`,
 //           RestRest
 //         ]
 //       : LT extends One
 //       ? Rest extends `${infer B0}${infer B1}${infer B2}${infer B3}${infer B4}${infer B5}${infer B6}${infer B7}${infer B8}${infer B9}${infer B10}${infer RestRest}`
 //         ? [
 //             `${B0}${B1}${B2}${B3}${B4}${B5}${B6}${B7}${B8}${B9}${B10}`,
 //             RestRest
 //           ]
 //         : never
 //       : never
 //     : never
 //   : never

 /**
 * v2 upgrade readability - using double extend trick to
 * minimize long template literal `infer`
 * UPDATE: bad idea, forces TS to expand the subtype union of 35k string literals
 */
 // type parseOpPacketBodyDebug<
 //   Val extends string
 // > = Val extends `${infer LT}${infer Rest}`
 //   ? LT extends Zero
 //     ? Rest extends `${LengthTypeTotal}${infer RestRest}`
 //       ? Rest extends `${infer B}${RestRest}`
 //         ? [B, RestRest]
 //         : never
 //       : never
 //     : LT extends One
 //     ? Rest extends `${LengthTypeChildren}${infer RestRest}`
 //       ? Rest extends `${infer B}${RestRest}`
 //         ? [B, RestRest]
 //         : never
 //       : never
 //     : never
 //   : never

 /** v3 upgrade readability - eliminate extra `Rest`, inline and don't return single bit check */
 // type parseOpPacketBodyDebug<Val extends string> =
 //   Val extends `0${LengthTypeTotal}${infer Rest}`
 //     ? Val extends `0${infer Len}${Rest}`
 //       ? [Len, Rest]
 //       : never
 //     : Val extends `1${LengthTypeChildren}${infer Rest}`
 //     ? Val extends `1${infer Len}${Rest}`
 //       ? [Len, Rest]
 //       : never
 //     : never

 /** v4 back to long bit infer to prevent expansion of subtype into 35k str literals */
 type parseOpPacketBodyDebug<Val extends string> =
  Val extends `0${infer B0}${infer B1}${infer B2}${infer B3}${infer B4}${infer B5}${infer B6}${infer B7}${infer B8}${infer B9}${infer B10}${infer B11}${infer B12}${infer B13}${infer B14}${infer Rest}`
    ? [
        `${B0}${B1}${B2}${B3}${B4}${B5}${B6}${B7}${B8}${B9}${B10}${B11}${B12}${B13}${B14}`,
        Rest,
      ]
    : Val extends `1${infer B0}${infer B1}${infer B2}${infer B3}${infer B4}${infer B5}${infer B6}${infer B7}${infer B8}${infer B9}${infer B10}${infer Rest}`
    ? [`${B0}${B1}${B2}${B3}${B4}${B5}${B6}${B7}${B8}${B9}${B10}`, Rest]
    : never

 /** v1 */
 // type parseFirstPacketDebug<
 //   Bin extends string
 // > = Bin extends `${infer V0}${infer V1}${infer V2}${infer T0}${infer T1}${infer T2}${infer Rest}`
 //   ? `${T0}${T1}${T2}` extends "100"
 //     ? [`${V0}${V1}${V2}`, `${T0}${T1}${T2}`, ...parseLitPacketBodyDebug<Rest>]
 //     : `${T0}${T1}${T2}` extends PacketTypeAny
 //     ? [`${V0}${V1}${V2}`, `${T0}${T1}${T2}`, ...parseOpPacketBodyDebug<Rest>]
 //     : never
 //   : never

 /** v2 removes long `infer` template in favor of extra levels of nesting. good? bad? */
 // type parseFirstPacketDebug<
 //   Bin extends string
 // > = Bin extends `${Version}${infer Rest1}`
 //   ? Bin extends `${infer V}${Rest1}`
 //     ? Rest1 extends `${PacketTypeAny}${infer Rest2}`
 //       ? Rest1 extends `${infer T}${Rest2}`
 //         ? T extends "100"
 //           ? [V, T, ...parseLitPacketBodyDebug<Rest2>]
 //           : T extends PacketTypeAny
 //           ? [V, T, ...parseOpPacketBodyDebug<Rest2>]
 //           : never
 //         : never
 //       : never
 //     : never
 //   : never

 /** v3 drops 1 level of nesting for potentially less recursion depth or maybe much slower */
 type parseFirstPacketDebug<Bin extends string> =
  Bin extends `${infer V0}${infer V1}${infer V2}${infer T0}${infer T1}${infer T2}${infer Rest}`
    ? `${T0}${T1}${T2}` extends "100"
      ? [`${V0}${V1}${V2}`, `${T0}${T1}${T2}`, ...parseLitPacketBodyDebug<Rest>]
      : `${T0}${T1}${T2}` extends PacketTypeAny
      ? [`${V0}${V1}${V2}`, `${T0}${T1}${T2}`, ...parseOpPacketBodyDebug<Rest>]
      : never
    : never

 /** optimize */

 type INPUT_1_debug_first_packet = Expect<
  parseFirstPacketDebug<INPUT_1_bin>,
  ["110", "100", "011111100101", "000"]
 >

 type INPUT_3 = "38006F45291200"
 type INPUT_3_bin = Expect<
  hexToBin<INPUT_3>,
  "00111000000000000110111101000101001010010001001000000000"
 >
 type INPUT_3_debug_first_packet = Expect<
  parseFirstPacketDebug<INPUT_3_bin>,
  ["001", "110", /* "0", */ "000000000011011", "1101000101001010010001001000000000"]
 >
 type INPUT_3_debug_first_packet2 = Expect<
  parseFirstPacketDebug<INPUT_3_debug_first_packet[3]>,
  ["110", "100", "1010", "01010010001001000000000"]
 >
 type INPUT_3_debug_first_packet3 = Expect<
  parseFirstPacketDebug<INPUT_3_debug_first_packet2[3]>,
  ["010", "100", "00010100", "0000000"]
 >
 type INPUT_3_debug_first_packet4 = Expect<
  parseFirstPacketDebug<INPUT_3_debug_first_packet3[3]>,
  never
 >

 /** only useful for small inputs, TS doesn't print the full output */
 type parseAllPacketsDebug<Bin extends string> = Bin extends never
  ? []
  : [...parseFirstPacketDebug<Bin>, parseAllPacketsDebug<parseFirstPacketDebug<Bin>[3]>]

 type INPUT_3_debug = parseAllPacketsDebug<INPUT_3_bin>

 //
 // #region - MATH - started this since version numbers need to be added together for part 1
 //
 type AddBit<Bit1 extends string, Bit2 extends string> = Bit1 | Bit2 extends Zero
  ? Zero
  : Bit1 | Bit2 extends One
  ? "?"
  : One

 type AddBinary<Bin1 extends string, Bin2 extends string, Out extends string = ""> =
  | Bin1
  | Bin2 extends ""
  ? Out
  : Bin1 extends `${infer Rest1}${Bit}`
  ? Bin1 extends `${Rest1}${infer B1}`
    ? Bin2 extends `${infer Rest2}${Bit}`
      ? Bin2 extends `${Rest2}${infer B2}`
        ? AddBinary<Rest1, Rest2, `${AddBit<B1, B2>}${Out}`>
        : never
      : never
    : never
  : never

 type TEST_ADD_00 = Expect<AddBinary<"001", "010">, "011">
 /** carry not implemented */
 // @ts-expect-error
 type TEST_ADD_01 = Expect<AddBinary<"100", "100">, "1000">

 /**
 * lots of `Zero` & `One` use here. undecided if I like it. this way makes it quicker
 * to write, but maybe a bit harder to read
 */
 type AddBitCarry<
  Bit1 extends string,
  Bit2 extends string,
  Carry extends string = Zero,
 > = Bit1 | Bit2 | Carry extends Zero // all Zero
  ? [Zero, Zero]
  : Bit1 | Bit2 | Carry extends One // all One
  ? [One, One]
  : (Bit1 | Bit2) & (Bit1 | Carry) & (Bit2 | Carry) extends One // One in any 2 out of the 3 positions
  ? [Zero, One]
  : [One, Zero]

 /** v1 does hiding the internal accumulators really matter? */
 // type _AddBinaryCarry<
 //   Bin1 extends string,
 //   Bin2 extends string,
 //   // internal
 //   Out extends string = "",
 //   Carry extends string = "0"
 // > = Bin1 | Bin2 extends "" // base case, both are empty, terminate recursion and return
 //   ? Carry extends "1"
 //     ? `1${Out}`
 //     : Out
 //   : Bin1 extends `${infer Rest1}${Bit}` // pick off the last bit of each binary string
 //   ? Bin1 extends `${Rest1}${infer B1}`
 //     ? Bin2 extends `${infer Rest2}${Bit}`
 //       ? Bin2 extends `${Rest2}${infer B2}`
 //         ? _AddBinaryCarry<
 //             Rest1,
 //             Rest2,
 //             `${AddBitCarry<B1, B2, Carry>[0]}${Out}`,
 //             AddBitCarry<B1, B2, Carry>[1]
 //           >
 //         : never
 //       : never
 //     : never
 //   : never

 // /** v2 handle sparse bit patterns */
 // type _AddBinaryCarry<
 //   Bin1 extends string,
 //   Bin2 extends string,
 //   // internal
 //   Out extends string = "",
 //   Carry extends string = "0"
 // > = Bin1 | Bin2 extends "" // base case, both are empty, terminate recursion and return
 //   ? Carry extends "1"
 //     ? `1${Out}`
 //     : Out
 //   : Bin1 extends `${infer Rest1}${Bit}` // pick off the last bit of each binary string
 //   ? Bin1 extends `${Rest1}${infer B1}`
 //     ? Bin2 extends `${infer Rest2}${Bit}`
 //       ? Bin2 extends `${Rest2}${infer B2}`
 //         ? _AddBinaryCarry<
 //             Rest1,
 //             Rest2,
 //             `${AddBitCarry<B1, B2, Carry>[0]}${Out}`,
 //             AddBitCarry<B1, B2, Carry>[1]
 //           >
 //         : never
 //       : _AddBinaryCarry<
 //             Rest1,
 //             Bin2,
 //             `${AddBitCarry<B1, "0", Carry>[0]}${Out}`,
 //             AddBitCarry<B1, "0", Carry>[1]
 //           >
 //     : never
 //   : Bin2 extends `${infer Rest2}${Bit}`
 //       ? Bin2 extends `${Rest2}${infer B2}`
 //         ? _AddBinaryCarry<
 //             Bin1,
 //             Rest2,
 //             `${AddBitCarry<Zero, B2, Carry>[0]}${Out}`,
 //             AddBitCarry<Zero, B2, Carry>[1]
 //           >
 //         : never
 //         : never

 type Bitify<Bit extends string> = Bit extends "" ? Zero : Bit

 /** v3  */
 /**
 * recursive depth might be pretty limited but fine for now. `Add2Bit` inline would double depth
 *
 * mismatched binary length inputs are invalid, but could be left padded with zero
 *
 * @todo optimization
 *
 * @version 3 handle sparse bit patterns better
 */
 type AddBinaryCarry<
  Bin1 extends string,
  Bin2 extends string,
  // internal
  Out extends string = "",
  Carry extends string = "0",
 > = Bin1 | Bin2 extends "" // base case, both are empty, terminate recursion and return
  ? Carry extends "1"
    ? `1${Out}`
    : Out
  : Bitify<Bin1> extends `${infer Rest1}${Bit}` // pick off the last bit of each binary string
  ? Bitify<Bin1> extends `${Rest1}${infer B1}`
    ? Bitify<Bin2> extends `${infer Rest2}${Bit}`
      ? Bitify<Bin2> extends `${Rest2}${infer B2}`
        ? AddBinaryCarry<
            Rest1,
            Rest2,
            `${AddBitCarry<B1, B2, Carry>[0]}${Out}`,
            AddBitCarry<B1, B2, Carry>[1]
          >
        : never
      : never
    : never
  : never

 type A = Zero
 // type A = One

 type B = Zero
 // type B = One

 // type C = Zero
 type C = One

 // logic used for carry bit. true if any 2 of 3 inputs are both One
 type TEST_ADD_1 = (A | B) & (A | C) & (B | C) extends One ? true : false

 type TEST_ADD_20 = Expect<AddBinaryCarry<"001", "010">, "011">
 type TEST_ADD_21 = Expect<AddBinaryCarry<"001", "001">, "010">
 type TEST_ADD_22 = Expect<AddBinaryCarry<"001", "011">, "100">
 type TEST_ADD_23 = Expect<AddBinaryCarry<"011", "011">, "110">
 type TEST_ADD_24 = Expect<AddBinaryCarry<"100", "100">, "1000">
 type TEST_ADD_25 = Expect<AddBinaryCarry<"111", "111">, "1110">
 type TEST_ADD_26 = Expect<
  AddBinaryCarry<"01010101010101010101", "10101010101010101010">,
  "11111111111111111111"
 >
 type TEST_ADD_27 = Expect<
  AddBinaryCarry<"11000000000000000001", "10000000000000000000">,
  "101000000000000000001"
 >

 type TEST_ADD_30 = Expect<AddBinaryCarry<"1", "0000">, "0001">
 type TEST_ADD_31 = Expect<AddBinaryCarry<"0000", "1">, "0001">
 type TEST_ADD_32 = Expect<AddBinaryCarry<"", "1">, "1">
 type TEST_ADD_33 = Expect<AddBinaryCarry<"1", "">, "1">
 type TEST_ADD_34 = Expect<AddBinaryCarry<"", "">, "">

 // #region - meta helpers

 /**
 * passes thru passing test input, errors with inputs that are not equal
 *
 * can be used in the middle of an expression and composed to check each step
 *
 * @todo check for perf issues with recursion
 */
 type Expect<
  Input extends Intersect,
  Expected extends Intersect,
  Intersect = Expected & Input,
 > = Input

 // const RENDER_TESTER2 = "RENDER_TESTER"

 // @ts-expect-error
 type expect_chain_test_0 = Expect<42, Expect<number, 42> | 0>
 // @ts-expect-error
 type expect_chain_test_1 = Expect<Expect<number, 42> | 0, 42>
 type expect_chain_test_2 = Expect<Expect<42 | number, number> | 0, number>
 type expect_chain_test_3 = Expect<number, Expect<number, 42 | number> | 0>

 //
 // #region - VERSION OPTIMIZED FINAL
 //

 type parseAllPacketsVersionsDebug<
  Bin extends string,
  Out extends Array<any> = [],
 > = Bin extends never
  ? Out
  : parseFirstPacketDebug<Bin> extends never
  ? Out
  : parseAllPacketsVersionsDebug<
      parseFirstPacketDebug<Bin>[3],
      [...Out, parseFirstPacketDebug<Bin>[0]]
    >

 /** v1 */
 // type parseLitPacketBodyVersions<Body extends string> =
 //   Body extends `0${Nibble}${infer RestD}`
 //     ? RestD
 //     : Body extends `1${Nibble}${infer RestE}`
 //     ? parseLitPacketBodyVersions<RestE>
 //     : never

 /** @version 2 - eliminate `Nibble` as it causes excessive subtype expansion */
 type parseLitPacketBodyVersions<Body extends string> =
  Body extends `0${infer B0}${infer B1}${infer B2}${infer B3}${infer RestD}`
    ? RestD
    : Body extends `1${infer B0}${infer B1}${infer B2}${infer B3}${infer RestE}`
    ? parseLitPacketBodyVersions<RestE>
    : never

 type parseOpPacketBodyVersions<Body extends string> =
  Body extends `0${infer B0}${infer B1}${infer B2}${infer B3}${infer B4}${infer B5}${infer B6}${infer B7}${infer B8}${infer B9}${infer B10}${infer B11}${infer B12}${infer B13}${infer B14}${infer RestB}`
    ? [RestB]
    : Body extends `1${infer B0}${infer B1}${infer B2}${infer B3}${infer B4}${infer B5}${infer B6}${infer B7}${infer B8}${infer B9}${infer B10}${infer RestC}`
    ? [RestC]
    : never

 /** @version 1 */
 // type parseFirstPacketVersions<BinPacket extends string> =
 //   BinPacket extends `${Version}${PacketTypeAny}${infer RestA}`
 //     ? BinPacket extends `${infer V}${PacketTypeAny}${RestA}`
 //       ? BinPacket extends `${Version}${infer T}${RestA}`
 //         ? T extends "100"
 //           ? [V, ...[parseLitPacketBodyVersions<RestA>]]
 //           : [V, ...parseOpPacketBodyVersions<RestA>]
 //         : never
 //       : never
 //     : never

 /**
 * @version 2 - sigh, back to goofy bit pattern, slightly faster
 */
 type parseFirstPacketVersions<BinPacket extends string> =
  BinPacket extends `${Version}${PacketTypeAny}${infer RestA}`
    ? BinPacket extends `${infer V}${PacketTypeAny}${RestA}`
      ? BinPacket extends `${Version}${infer T}${RestA}`
        ? T extends "100"
          ? [V, ...[parseLitPacketBodyVersions<RestA>]]
          : [V, ...parseOpPacketBodyVersions<RestA>]
        : never
      : never
    : never

 /** v1 perf: supports ~270 hex chars, or 9 repeats of A0016C880162017C3686B18A3D4780 */
 // type parseAllPacketsVersionsSum<
 //   Bin extends string,
 //   Sum extends string = ""
 // > = Bin extends never
 //   ? Sum
 //   : parseFirstPacketVersions<Bin> extends never
 //   ? Sum
 //   : parseAllPacketsVersionsSum<
 //       parseFirstPacketVersions<Bin>[1],
 //       AddBinaryCarry<parseFirstPacketVersions<Bin>[0], Sum>
 //     >

 /**
 * @version 2 - same recursion, but faster
 */
 type _parseAllPacketsVersionsSum<
  Packet extends [string, string],
  Sum extends string,
 > = Packet[1] extends ""
  ? Sum
  : _parseAllPacketsVersionsSum<
      parseFirstPacketVersions<Packet[1]>,
      AddBinaryCarry<Packet[0], Sum>
    >

 /**
 * kick off recursion
 * perf: supports ~270 hex chars, or 9 repeats of A0016C880162017C3686B18A3D4780
 * @version 2
 */
 type parseAllPacketsVersionsSum<Bin extends string> = _parseAllPacketsVersionsSum<
  parseFirstPacketVersions<Bin>,
  ""
 >

 type INPUT_3_versions = Expect<
  parseAllPacketsVersionsDebug<INPUT_3_bin>,
  ["001", "110", "010"]
 >
 type INPUT_3_versions_sum = Expect<parseAllPacketsVersionsSum<INPUT_3_bin>, "1001">

 type INPUT_4 = "EE00D40C823060"
 type INPUT_4_bin = Expect<
  hexToBin<INPUT_4>,
  "11101110000000001101010000001100100000100011000001100000"
 >
 // type INPUT_4_debug = parseAllPacketsDebug<INPUT_4_bin>
 type INPUT_4_versions = Expect<
  parseAllPacketsVersionsDebug<INPUT_4_bin>,
  ["111", "010", "100", "001"]
 >
 type INPUT_4_versions_sum = Expect<parseAllPacketsVersionsSum<INPUT_4_bin>, "1110">

 type INPUT_5 = "8A004A801A8002F478"
 type INPUT_5_bin = hexToBin<INPUT_5>
 // type INPUT_5_versions = parseAllPacketsVersionsDebug<INPUT_5_bin>
 type INPUT_5_versions_sum = Expect<parseAllPacketsVersionsSum<INPUT_5_bin>, "10000">

 type INPUT_6 = "620080001611562C8802118E34"
 type INPUT_6_bin = hexToBin<INPUT_6>
 // type INPUT_6_versions = parseAllPacketsVersionsDebug<INPUT_6_bin>
 type INPUT_6_versions_sum = Expect<parseAllPacketsVersionsSum<INPUT_6_bin>, "1100">

 type INPUT_7 = "C0015000016115A2E0802F182340"
 type INPUT_7_bin = hexToBin<INPUT_7>
 // type INPUT_7_versions = parseAllPacketsVersionsDebug<INPUT_7_bin>
 type INPUT_7_versions_sum = Expect<parseAllPacketsVersionsSum<INPUT_7_bin>, "10111">

 type INPUT_8 = "A0016C880162017C3686B18A3D4780"
 type INPUT_8_bin = hexToBin<INPUT_8>
 // type INPUT_8_versions = parseAllPacketsVersionsDebug<INPUT_8_bin>
 type INPUT_8_versions_sum = Expect<parseAllPacketsVersionsSum<INPUT_8_bin>, "11111">

 type INPUT_FINAL =
  "420D74C3088043390499ED709E6EB49A5CC4A3A3898B7E0F44011C4CC48AC0119D049B0C500265EB8F615900180910C88129B2F0007C61C4B7F74ED7396B20020A44A4C014D005E5A72E274B4E5C4B96CC3793410078C01D82F1DA08180351661AC1920042A3CC578BA6008F802138D93352B9CFCEF61D3009A7D2268D254925569C02A92D62BF108D52C1B3E4B257B57FAE5C54400A84840267880311D23245F1007A35C79848200C4288FF0E8C01194A4E625E00A4EFEF5F5996486C400C5002800BFA402D3D00A9C4027B98093D602231C00F001D38C009500258057E601324C00D3003D400C7003DC00A20053A6F1DBDE2D4600A6802B37C4B9E872B0E44CA5FF0BFB116C3004740119895E6F7312BCDE25EF077700725B9F2B8F131F333005740169A7F92EFEB3BC8A21998027400D2CDF30F927880B4C62D6CDFFD88EB0068D2BF019A8DAAF3245B39C9CFA1D2DF9C3DB9D3E50A0164BE2A3339436993894EC41A0D10020B329334C62016C8E7A5F27C97D0663982D8EB23C5282529CDD271E8F100AE1401AA80021119E3A4511006E1E47689323585F3AEBF900AEB2B6942BD91EE8028000874238AB0C00010B8D913220A004A73D789C4D54E24816301802538E940198880371AE15C1D1007638C43856C00954C25CD595A471FE9D90056D60094CEA61933A9854E9F3801F2BBC6131001F792F6796ACB40D036605C80348C005F64F5AC374888CA42FD99A98025319EB950025713656F202200B767AB6A30E802D278F81CBA89004CD286360094FC03A7E01640245CED5A3C010100660FC578B60008641C8B105CC017F004E597E596E633BA5AB78B9C8F840C029917C9E389B439179927A3004F003511006610C658A200084C2989D0AE67BD07000606154B70E66DC0C01E99649545950B8AB34C8401A5CDA050043D319F31CB7EBCEE14"
 type INPUT_FINAL_bin = hexToBin<INPUT_FINAL>
 // type INPUT_FINAL_versions = parseAllPacketsVersions<INPUT_FINAL_bin>

 /** gotta manually convert to decimal unfortunately (`895`) */
 type INPUT_FINAL_versions_sum = Expect<
  parseAllPacketsVersionsSum<INPUT_FINAL_bin>,
  "1101111111"
 >

 /**************************
 * #region - START PART 2
 **************************/

 type Trim<Bin> = Bin extends ""
  ? "0"
  : Bin extends `${infer B0}${infer Rest}`
  ? B0 extends "0"
    ? Trim<Rest>
    : Bin
  : Bin

 type _MultBin<
  Bin1 extends string,
  Bin2 extends string,
  // internal
  Count extends string = "1",
  Orig extends string = Bin1,
 > = Trim<Bin2> extends Count
  ? Bin1
  : _MultBin<AddBinaryCarry<Bin1, Orig>, Bin2, AddBinaryCarry<Count, "1">, Orig>

 type MultBin<Bin1 extends string, Bin2 extends string> = "0" extends
  | Trim<Bin1>
  | Trim<Bin2>
  ? "0"
  : _MultBin<Bin1, Bin2>

 type TEST_MULT_00 = Expect<MultBin<"001", "010">, "010">
 type TEST_MULT_01 = Expect<MultBin<"001", "001">, "001">
 type TEST_MULT_02 = Expect<MultBin<"001", "011">, "011">
 type TEST_MULT_03 = Expect<MultBin<"011", "011">, "1001">
 type TEST_MULT_04 = Expect<MultBin<"100", "100">, "10000">
 type TEST_MULT_05 = Expect<MultBin<"111", "111">, "110001">
 type TEST_MULT_06 = Expect<MultBin<"011", "010">, "110">
 type TEST_MULT_07 = Expect<MultBin<"010", "011">, "110">
 type TEST_MULT_20 = Expect<MultBin<"1", "0000">, "0">
 type TEST_MULT_21 = Expect<MultBin<"0000", "1">, "0">
 type TEST_MULT_22 = Expect<MultBin<"", "1">, "0">
 type TEST_MULT_23 = Expect<MultBin<"1", "">, "0">
 type TEST_MULT_24 = Expect<MultBin<"", "">, "0">

 type Equal<A, B> = [A] extends [B] ? ([B] extends [A] ? true : false) : false

 type MinBin<
  Bin1 extends string,
  Bin2 extends string,
  Orig1 extends string = Bin1,
  Orig2 extends string = Bin2,
 > = Equal<Trim<Bin1>, Trim<Bin2>> extends true
  ? Bin1
  : Bin1 extends `${infer B1}${infer Rest1}`
  ? Bin2 extends `${infer B2}${infer Rest2}`
    ? Equal<B1, B2> extends true
      ? MinBin<Rest1, Rest2, Orig1, Orig2>
      : B1 extends "0"
      ? Orig1
      : B2 extends "0"
      ? Orig2
      : never
    : never
  : never

 type TEST_MIN_00 = Expect<MinBin<"001", "010">, "001">
 type TEST_MIN_01 = Expect<MinBin<"001", "001">, "001">
 type TEST_MIN_02 = Expect<MinBin<"001", "011">, "001">
 type TEST_MIN_03 = Expect<MinBin<"011", "011">, "011">
 type TEST_MIN_06 = Expect<MinBin<"011", "010">, "010">
 type TEST_MIN_07 = Expect<MinBin<"010", "011">, "010">
 type TEST_MIN_20 = Expect<MinBin<"1", "0000">, "0000">
 type TEST_MIN_21 = Expect<MinBin<"0000", "1">, "0000">
 // @ts-expect-error - empty string not implemented
 type TEST_MIN_22 = Expect<MinBin<"", "1">, "0">
 // @ts-expect-error - empty string not implemented
 type TEST_MIN_23 = Expect<MinBin<"1", "">, "0">
 // @ts-expect-error - empty string not implemented
 type TEST_MIN_24 = Expect<MinBin<"", "">, "0">

 type MaxBin<
  Bin1 extends string,
  Bin2 extends string,
  Orig1 extends string = Bin1,
  Orig2 extends string = Bin2,
 > = Equal<Trim<Bin1>, Trim<Bin2>> extends true
  ? Bin1
  : Bin1 extends `${infer B1}${infer Rest1}`
  ? Bin2 extends `${infer B2}${infer Rest2}`
    ? Equal<B1, B2> extends true
      ? MaxBin<Rest1, Rest2, Orig1, Orig2>
      : B1 extends "1"
      ? Orig1
      : B2 extends "1"
      ? Orig2
      : never
    : never
  : never

 type TEST_MAX_00 = Expect<MaxBin<"001", "010">, "010">
 type TEST_MAX_01 = Expect<MaxBin<"001", "001">, "001">
 type TEST_MAX_02 = Expect<MaxBin<"001", "011">, "011">
 type TEST_MAX_03 = Expect<MaxBin<"011", "011">, "011">
 type TEST_MAX_06 = Expect<MaxBin<"011", "010">, "011">
 type TEST_MAX_07 = Expect<MaxBin<"010", "011">, "011">
 type TEST_MAX_20 = Expect<MaxBin<"1", "0000">, "1">
 type TEST_MAX_21 = Expect<MaxBin<"0000", "1">, "1">
 // @ts-expect-error - empty string not implemented
 type TEST_MAX_22 = Expect<MaxBin<"", "1">, "1">
 // @ts-expect-error - empty string not implemented
 type TEST_MAX_23 = Expect<MaxBin<"1", "">, "1">
 // @ts-expect-error - empty string not implemented
 type TEST_MAX_24 = Expect<MaxBin<"", "">, "??">

 type GTBin<
  Bin1 extends string,
  Bin2 extends string,
  Orig1 extends string = Bin1,
  Orig2 extends string = Bin2,
 > = Equal<Trim<Bin1>, Trim<Bin2>> extends true
  ? Zero
  : Bin1 extends `${infer B1}${infer Rest1}`
  ? Bin2 extends `${infer B2}${infer Rest2}`
    ? Equal<B1, B2> extends true
      ? GTBin<Rest1, Rest2, Orig1, Orig2>
      : B1 extends "1"
      ? One
      : Zero
    : never
  : never

 type TEST_GT_00 = Expect<GTBin<"001", "010">, "0">
 type TEST_GT_01 = Expect<GTBin<"001", "001">, "0">
 type TEST_GT_06 = Expect<GTBin<"011", "010">, "1">
 type TEST_GT_07 = Expect<GTBin<"010", "011">, "0">
 type TEST_GT_20 = Expect<GTBin<"1", "0000">, "1">
 type TEST_GT_21 = Expect<GTBin<"0000", "1">, "0">
 // @ts-expect-error - empty string not implemented
 type TEST_GT_22 = Expect<GTBin<"", "1">, "1">
 // @ts-expect-error - empty string not implemented
 type TEST_GT_23 = Expect<GTBin<"1", "">, "1">
 // @ts-expect-error - empty string not implemented
 type TEST_GT_24 = Expect<GTBin<"", "">, "??">

 type LTBin<
  Bin1 extends string,
  Bin2 extends string,
  Orig1 extends string = Bin1,
  Orig2 extends string = Bin2,
 > = Equal<Trim<Bin1>, Trim<Bin2>> extends true
  ? Zero
  : Bin1 extends `${infer B1}${infer Rest1}`
  ? Bin2 extends `${infer B2}${infer Rest2}`
    ? Equal<B1, B2> extends true
      ? LTBin<Rest1, Rest2, Orig1, Orig2>
      : B1 extends "0"
      ? One
      : Zero
    : never
  : never

 type TEST_LT_00 = Expect<LTBin<"001", "010">, "1">
 type TEST_LT_01 = Expect<LTBin<"001", "001">, "0">
 type TEST_LT_06 = Expect<LTBin<"011", "010">, "0">
 type TEST_LT_07 = Expect<LTBin<"010", "011">, "1">
 type TEST_LT_20 = Expect<LTBin<"1", "0000">, "0">
 type TEST_LT_21 = Expect<LTBin<"0000", "1">, "1">
 // @ts-expect-error - empty string not implemented
 type TEST_LT_22 = Expect<LTBin<"", "1">, "1">
 // @ts-expect-error - empty string not implemented
 type TEST_LT_23 = Expect<LTBin<"1", "">, "0">
 type TEST_LT_24 = Expect<LTBin<"", "">, "0">

 type EQBin<Bin1 extends string, Bin2 extends string> = Equal<
  Trim<Bin1>,
  Trim<Bin2>
 > extends true
  ? One
  : Zero

 type TEST_EQ_00 = Expect<EQBin<"001", "010">, "0">
 type TEST_EQ_01 = Expect<EQBin<"001", "001">, "1">
 type TEST_EQ_06 = Expect<EQBin<"011", "010">, "0">
 type TEST_EQ_07 = Expect<EQBin<"010", "011">, "0">
 type TEST_EQ_08 = Expect<EQBin<"00001", "1">, "1">
 type TEST_EQ_20 = Expect<EQBin<"1", "0000">, "0">
 type TEST_EQ_21 = Expect<EQBin<"0000", "1">, "0">
 type TEST_EQ_22 = Expect<EQBin<"", "1">, "0">
 type TEST_EQ_23 = Expect<EQBin<"1", "">, "0">
 type TEST_EQ_24 = Expect<EQBin<"", "">, "1">

 /*****************
 * PART II FINAL
 *****************/

 type IPacketTypeId = {
  sum: "000"
  product: "001"
  min: "010"
  max: "011"
  literal: "100"
  gt: "101"
  lt: "110"
  eq: "111"
 }

 type IPacketTypeName = {
  [K in keyof IPacketTypeId as IPacketTypeId[K]]: K
 }

 namespace PacketTypeId {
  export type sum = "000"
  export type product = "001"
  export type min = "010"
  export type max = "011"
  export type literal = "100"
  export type gt = "101"
  export type lt = "110"
  export type eq = "111"
 }

 /** @version 1 */
 type parseLitPacketBodyOut<
  Body extends string,
  Out extends string = "",
 > = Body extends `0${infer B0}${infer B1}${infer B2}${infer B3}${infer RestD}`
  ? [`${Out}${B0}${B1}${B2}${B3}`, RestD]
  : Body extends `1${infer B0}${infer B1}${infer B2}${infer B3}${infer RestE}`
  ? parseLitPacketBodyOut<RestE, `${Out}${B0}${B1}${B2}${B3}`>
  : never

 /** @version 1 */
 type parseOpPacketLengthOut<Bin extends string> =
  Bin extends `0${infer B0}${infer B1}${infer B2}${infer B3}${infer B4}${infer B5}${infer B6}${infer B7}${infer B8}${infer B9}${infer B10}${infer B11}${infer B12}${infer B13}${infer B14}${infer RestB}`
    ? [
        `${B0}${B1}${B2}${B3}${B4}${B5}${B6}${B7}${B8}${B9}${B10}${B11}${B12}${B13}${B14}`,
        RestB,
      ]
    : Bin extends `1${infer B0}${infer B1}${infer B2}${infer B3}${infer B4}${infer B5}${infer B6}${infer B7}${infer B8}${infer B9}${infer B10}${infer RestC}`
    ? [`${B0}${B1}${B2}${B3}${B4}${B5}${B6}${B7}${B8}${B9}${B10}`, RestC]
    : never

 /** @todo support unary and n-ary inputs */
 type parseSumPacketBodyOut<Body extends string> = [
  AddBinaryCarry<
    parseFirstPacketOut<Body>[0],
    parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[0]
  >,
  parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[1],
 ]
 /** @todo support unary and n-ary inputs */
 type parseMultPacketBodyOut<Body extends string> = [
  MultBin<
    parseFirstPacketOut<Body>[0],
    parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[0]
  >,
  parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[1],
 ]
 /** @todo support unary and n-ary inputs */
 type parseMinPacketBodyOut<Body extends string> = [
  MinBin<
    parseFirstPacketOut<Body>[0],
    parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[0]
  >,
  parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[1],
 ]
 /** @todo support unary and n-ary inputs */
 type parseMaxPacketBodyOut<Body extends string> = [
  MaxBin<
    parseFirstPacketOut<Body>[0],
    parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[0]
  >,
  parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[1],
 ]
 type parseLTPacketBodyOut<Body extends string> = [
  LTBin<
    parseFirstPacketOut<Body>[0],
    parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[0]
  >,
  parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[1],
 ]

 type parseGTPacketBodyOut<Body extends string> = [
  GTBin<
    parseFirstPacketOut<Body>[0],
    parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[0]
  >,
  parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[1],
 ]

 type parseEQPacketBodyOut<Body extends string> = [
  EQBin<
    parseFirstPacketOut<Body>[0],
    parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[0]
  >,
  parseFirstPacketOut<parseFirstPacketOut<Body>[1]>[1],
 ]

 /** switch statement for picking operation */
 type parseOpPacketOut<
  Type extends string,
  Length extends string,
  Body extends string,
 > = Type extends PacketTypeId.lt
  ? parseLTPacketBodyOut<Body>
  : Type extends PacketTypeId.gt
  ? parseGTPacketBodyOut<Body>
  : Type extends PacketTypeId.eq
  ? parseEQPacketBodyOut<Body>
  : Type extends PacketTypeId.sum
  ? parseSumPacketBodyOut<Body>
  : Type extends PacketTypeId.product
  ? parseMultPacketBodyOut<Body>
  : Type extends PacketTypeId.min
  ? parseMinPacketBodyOut<Body>
  : Type extends PacketTypeId.max
  ? parseMaxPacketBodyOut<Body>
  : never

 /**
 * @version 1
 */
 type parseFirstPacketOut<BinPacket extends string> =
  BinPacket extends `${infer V0}${infer V1}${infer V2}${infer T0}${infer T1}${infer T2}${infer RestA}`
    ? `${T0}${T1}${T2}` extends PacketTypeId.literal
      ? parseLitPacketBodyOut<RestA>
      : Trim<
          parseOpPacketOut<
            `${T0}${T1}${T2}`,
            parseOpPacketLengthOut<RestA>[0],
            parseOpPacketLengthOut<RestA>[1]
          >[0]
        >
    : never

 /**
 * @version 1
 */
 type _parseAllPacketsOut<
  Packet extends [string, string],
  Res extends string,
 > = Packet[1] extends ""
  ? Packet[0]
  : _parseAllPacketsOut<
      parseFirstPacketOut<Packet[1]>[1],
      parseFirstPacketOut<Packet[1]>[0]
    >

 /**
 * kick off recursion
 * @version 1
 */
 type parseAllPacketsOut<Bin extends string> = _parseAllPacketsOut<
  parseFirstPacketOut<Bin>,
  ""
 >

 // #region printers

 type printOPPacketBodyOut<Body extends string> = [
  [printFirstPacketOut<Body>, printFirstPacketOut<printFirstPacketOut<Body>[2]>],
  printFirstPacketOut<printFirstPacketOut<Body>[2]>[2],
 ]

 type printOpPacketOut<
  Type extends string,
  Body extends string,
 > = Type extends keyof IPacketTypeName
  ? [IPacketTypeName[Type], ...printOPPacketBodyOut<Body>]
  : never

 /**
 * @version 1
 */
 type printFirstPacketOut<BinPacket extends string> =
  BinPacket extends `${infer V0}${infer V1}${infer V2}${infer T0}${infer T1}${infer T2}${infer RestA}`
    ? `${T0}${T1}${T2}` extends PacketTypeId.literal
      ? ["lit", ...parseLitPacketBodyOut<RestA>]
      : printOpPacketOut<`${T0}${T1}${T2}`, parseOpPacketLengthOut<RestA>[1]>
    : never

 /** sum */
 type INPUT_20 = hexToBin<"C200B40A82">
 type INPUT_20_DEBUG = printFirstPacketOut<INPUT_20>
 type INPUT_20_OUT = Expect<parseFirstPacketOut<INPUT_20>, "11">

 /** product */
 type INPUT_21 = hexToBin<"04005AC33890">
 type INPUT_21_DEBUG = printFirstPacketOut<INPUT_21>
 type INPUT_21_OUT = Expect<parseFirstPacketOut<INPUT_21>, "110110">

 /** min */
 type INPUT_22 = hexToBin<"880086C3E88112">
 type INPUT_22_DEBUG = printFirstPacketOut<INPUT_22>
 // type INPUT_22_OUT = Expect<parseAllPacketsOut<INPUT_22>, "111">

 /** max */
 type INPUT_23 = hexToBin<"CE00C43D881120">
 type INPUT_23_DEBUG = printFirstPacketOut<INPUT_23>
 // type INPUT_23_OUT = Expect<parseAllPacketsOut<INPUT_23>, "1001">

 /** lt */
 type INPUT_24 = hexToBin<"D8005AC2A8F0">
 type INPUT_24_DEBUG = printFirstPacketOut<INPUT_24>
 type INPUT_24_OUT = Expect<parseFirstPacketOut<INPUT_24>, "1">

 /** gt */
 type INPUT_25 = hexToBin<"F600BC2D8F">
 type INPUT_25_DEBUG = printFirstPacketOut<INPUT_25>
 type INPUT_25_OUT = Expect<parseFirstPacketOut<INPUT_25>, "0">

 /** eq */
 type INPUT_26 = hexToBin<"9C005AC2F8F0">
 type INPUT_26_DEBUG = printFirstPacketOut<INPUT_26>
 type INPUT_26_OUT = Expect<parseFirstPacketOut<INPUT_26>, "0">

 /** combo */
 type INPUT_27 = hexToBin<"9C0141080250320F1802104A08">
 type INPUT_27_DEBUG = printFirstPacketOut<INPUT_27>
 // type INPUT_27_OUT = Expect<parseFirstPacketOut<INPUT_27>, "1">

 /** toggle comment on me to see how long it takes to render */
 const RENDER_TESTER = "RENDER_TESTER"