Last active
February 22, 2025 08:19
-
-
Save Tsukina-7mochi/181bc612b8633f0f5d84cee7c03c866f to your computer and use it in GitHub Desktop.
Brainf*ck Implementation on TypeScript Types
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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