Skip to content

Instantly share code, notes, and snippets.

@Tsukina-7mochi
Last active February 22, 2025 08:19
Show Gist options
  • Save Tsukina-7mochi/181bc612b8633f0f5d84cee7c03c866f to your computer and use it in GitHub Desktop.
Save Tsukina-7mochi/181bc612b8633f0f5d84cee7c03c866f to your computer and use it in GitHub Desktop.
Brainf*ck Implementation on TypeScript Types
// deno-fmt-ignore
type AsciiTable = { 32: " ", 33: "!", 34: "\"", 35: "#", 36: "$", 37: "%", 38: "&", 39: "'", 40: "(", 41: ")", 42: "*", 43: "+", 44: ",", 45: "-", 46: ".", 47: "/", 48: "0", 49: "1", 50: "2", 51: "3", 52: "4", 53: "5", 54: "6", 55: "7", 56: "8", 57: "9", 58: ":", 59: ";", 60: "<", 61: "=", 62: ">", 63: "?", 64: "@", 65: "A", 66: "B", 67: "C", 68: "D", 69: "E", 70: "F", 71: "G", 72: "H", 73: "I", 74: "J", 75: "K", 76: "L", 77: "M", 78: "N", 79: "O", 80: "P", 81: "Q", 82: "R", 83: "S", 84: "T", 85: "U", 86: "V", 87: "W", 88: "X", 89: "Y", 90: "Z", 91: "[", 92: "\\", 93: "]", 94: "^", 95: "_", 96: "`", 97: "a", 98: "b", 99: "c", 100: "d", 101: "e", 102: "f", 103: "g", 104: "h", 105: "i", 106: "j", 107: "k", 108: "l", 109: "m", 110: "n", 111: "o", 112: "p", 113: "q", 114: "r", 115: "s", 116: "t", 117: "u", 118: "v", 119: "w", 120: "x", 121: "y", 122: "z", 123: "{", 124: "|", 125: "}" 126: "~" }
type Decoded<T extends number[]> = T extends [infer V, ...infer A] ? A extends number[] ? (V extends keyof AsciiTable ? `${AsciiTable[V]}${Decoded<A>}` : `?${Decoded<A>}`) : never : '';
type Length<T extends unknown[]> = T extends { length: infer N } ? N extends number ? N : never
: never;
type AtoN<Arr extends unknown[]> = Length<Arr>;
type NtoA<Num extends number, Arr extends unknown[] = []> = Length<Arr> extends Num ? Arr
: NtoA<Num, [...Arr, unknown]>;
type Add<N extends number, M extends number> = AtoN<[...NtoA<N>, ...NtoA<M>]>;
type Sub<N extends number, M extends number> = NtoA<N> extends [...NtoA<M>, ...infer A] ? AtoN<A> : never;
type Tail<Arr extends unknown[]> = Arr extends [infer _, ...infer A] ? A : never;
type TakeN<Arr extends unknown[], N extends number> = Arr extends [...infer A, ...NtoA<Sub<Length<Arr>, N>>] ? A
: never;
type DropN<Arr extends unknown[], N extends number> = Arr extends [...NtoA<N>, ...infer A] ? A
: never;
type ZeroArr<N extends number, Arr extends 0[] = []> = Length<Arr> extends N ? Arr : ZeroArr<N, [...Arr, 0]>;
type MemWrite<Mem extends number[], Ind extends number, Val extends number> = [
...TakeN<Mem, Ind>,
Val,
...DropN<Mem, Add<Ind, 1>>,
];
type JumpForward<Prg extends Operation[], PC extends number, Depth extends number = 0> = PC extends never ? never
: PC extends Length<Prg> ? never
: Prg[PC] extends "]" ? (Depth extends 1 ? PC : JumpForward<Prg, Add<PC, 1>, Sub<Depth, 1>>)
: Prg[PC] extends "[" ? JumpForward<Prg, Add<PC, 1>, Add<Depth, 1>>
: JumpForward<Prg, Add<PC, 1>, Depth>;
type JumpBackwards<Prg extends Operation[], PC extends number, Depth extends number = 0> = PC extends never ? never
: Prg[PC] extends "[" ? (Depth extends 1 ? PC : JumpBackwards<Prg, Sub<PC, 1>, Sub<Depth, 1>>)
: Prg[PC] extends "]" ? JumpBackwards<Prg, Sub<PC, 1>, Add<Depth, 1>>
: JumpBackwards<Prg, Sub<PC, 1>, Depth>;
type Operation = "+" | "-" | ">" | "<" | "." | "," | "[" | "]";
type Lex<Str extends string> = Str extends `${infer R}${infer S}` ? (R extends Operation ? [R, ...Lex<S>] : Lex<S>)
: [];
type Evaluate<
Prg extends Operation[],
PC extends number,
Mem extends number[],
Ptr extends number,
Out extends number[],
In extends number[],
> = PC extends Length<Prg> ? Out
: Prg[PC] extends "+" ? Evaluate<Prg, Add<PC, 1>, MemWrite<Mem, Ptr, Add<Mem[Ptr], 1>>, Ptr, Out, In>
: Prg[PC] extends "-" ? Evaluate<Prg, Add<PC, 1>, MemWrite<Mem, Ptr, Sub<Mem[Ptr], 1>>, Ptr, Out, In>
: Prg[PC] extends ">" ? Evaluate<Prg, Add<PC, 1>, Mem, Add<Ptr, 1>, Out, In>
: Prg[PC] extends "<" ? Evaluate<Prg, Add<PC, 1>, Mem, Sub<Ptr, 1>, Out, In>
: Prg[PC] extends "." ? Evaluate<Prg, Add<PC, 1>, Mem, Ptr, [...Out, Mem[Ptr]], In>
: Prg[PC] extends "," ? Evaluate<Prg, Add<PC, 1>, MemWrite<Mem, Ptr, In[0]>, Ptr, Out, Tail<In>>
: Prg[PC] extends "[" ? (Mem[Ptr] extends 0 ? Evaluate<Prg, Add<JumpForward<Prg, PC>, 1>, Mem, Ptr, Out, In>
: Evaluate<Prg, Add<PC, 1>, Mem, Ptr, Out, In>)
: Prg[PC] extends "]" ? (Mem[Ptr] extends 0 ? Evaluate<Prg, Add<PC, 1>, Mem, Ptr, Out, In>
: Evaluate<Prg, Add<JumpBackwards<Prg, PC>, 1>, Mem, Ptr, Out, In>)
: never;
type Executed<Prg extends string, Input extends number[] = []> = Decoded<Evaluate<Lex<Prg>, 0, ZeroArr<10>, 0, [], Input>>;
// Prints input binary number as string with format `=${num}`
export type Result = Executed<"++++++[>++++++++++<-]>+.,<++++++[>++++++++<-]>.", [3]>;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment