Skip to content

Commit 46f0b49

Browse files
NekitCorpNekitCorp
committed
Day 24.
1 parent 7c044f8 commit 46f0b49

File tree

1 file changed

+331
-0
lines changed

1 file changed

+331
-0
lines changed

‎2024/day-24.ts

Lines changed: 331 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,331 @@
1+
import { Expect, Equal } from "../test";
2+
3+
/**
4+
* **Parser Combinators: The Final Frontier**
5+
*
6+
* [🎅Santa] First the elves needed a code parser, then we had that JSON situation... I'm starting to see a pattern here.
7+
*
8+
* [🎩Bernard] We keep building one-off parsers for everything! Maybe we should create a reusable parsing system?
9+
*
10+
* [🎅Santa] Like some sort of parser factory? That's brilliant! We could use it for everything - toy specs, route planning... uh... everything!
11+
*
12+
* [🎩Bernard] Right... I'll get started on the design.
13+
*
14+
* The elves need your help building a type-safe parser combinator system! Instead of creating individual parsers for each format, you'll create building blocks that can be combined to parse anything.
15+
*
16+
* Here's how the elves want to use it:
17+
* ```ts
18+
* // define simple parsers
19+
* type DigitParser = Parse<Just, Digit>;
20+
*
21+
* // combine into more complex parsers
22+
* type IntParser = Parse<
23+
* MapResult,
24+
* [Parse<Many1, DigitParser>, Join, StringToNumber]
25+
* >;
26+
*
27+
* // parse!
28+
* type Parsed = Parse<IntParser, "123.4ff">["data"]; // 123
29+
* ```
30+
*
31+
* Implement all of these core parser combinators:
32+
* - `Choice` - Tries each parser in order until one succeeds
33+
* - `EOF` - Matches the end of input
34+
* - `Just` - Matches exactly one character/token
35+
* - `Left` - Matches the left parser
36+
* - `Many0` - Matches zero or more of the parser
37+
* - `Many1` - Matches one or more of the parser
38+
* - `MapResult` - Maps the parsed data using the provided mapper
39+
* - `Mapper` - A mapper is a function that transforms the parsed data
40+
* - `Maybe` - Matches zero or one of the parser
41+
* - `MaybeResult` - A result type for parsers that may fail
42+
* - `NoneOf` - Matches none of the characters/tokens
43+
* - `Pair` - Matches two parsers in sequence
44+
* - `Parse` - The core parser type
45+
* - `Parser` - A parser is a function that attempts to parse an input string
46+
* - `Right` - Matches the right parser
47+
* - `SepBy0` - Matches zero or more of the parser separated by the separator parser
48+
* - `Seq` - Matches two parsers in sequence
49+
*
50+
* Each parser should return a result type containing:
51+
* - `success`: Whether the parse succeeded
52+
* - `data`: The parsed data
53+
* - `rest`: The remaining unparsed input
54+
*
55+
* Hint
56+
*
57+
* Your solution from Day 23 might be helpful here. Start with the simplest parsers and build up to more complex ones. Make use of anything that has already been implemented for you.eneric types like `Array` let you abstract over the type of the element (`T`) in the container (`Array`). But what if you need to abstract over the type of the container itself?
58+
*/
59+
type Solution = unknown;
60+
61+
// *************************************************************************************
62+
// *** Tests ***
63+
// *************************************************************************************
64+
65+
type t0_actual = Parse<JSONParser, '"hello"'>["data"];
66+
type t0_expected = "hello";
67+
type t0 = Expect<Equal<t0_actual, t0_expected>>;
68+
69+
type t1_actual = Parse<JSONParser, '"hello\nworld"'>["data"];
70+
type t1_expected = "hello\nworld";
71+
type t1 = Expect<Equal<t1_actual, t1_expected>>;
72+
73+
type t2_actual = Parse<JSONParser, '{"hello": "world"}'>["data"];
74+
type t2_expected = { hello: "world" };
75+
type t2 = Expect<Equal<t2_actual, t2_expected>>;
76+
77+
type t3_actual = Parse<JSONParser, '[1, "hello", null, 4, "world"]'>["data"];
78+
type t3_expected = [1, "hello", null, 4, "world"];
79+
type t3 = Expect<Equal<t3_actual, t3_expected>>;
80+
81+
type t4_actual = Parse<JSONParser, '{ "a": { "b": "c" } }'>["data"];
82+
type t4_expected = { a: { b: "c" } };
83+
type t4 = Expect<Equal<t4_actual, t4_expected>>;
84+
85+
type t5_actual = Parse<JSONParser, '[{ "foo": "bar" }, { "foo": "baz" }, { "foo": 123 }]'>["data"];
86+
type t5_expected = [{ foo: "bar" }, { foo: "baz" }, { foo: 123 }];
87+
type t5 = Expect<Equal<t5_actual, t5_expected>>;
88+
89+
type t6_actual = Parse<JSONParser, "[1, 2, 3">["success"];
90+
type t6_expected = false;
91+
type t6 = Expect<Equal<t6_actual, t6_expected>>;
92+
93+
type t7_actual = Parse<JSONParser, "{ foo: 123 }">["success"];
94+
type t7_expected = false;
95+
type t7 = Expect<Equal<t7_actual, t7_expected>>;
96+
97+
type t8_actual = Parse<JSONParser, "{">["success"];
98+
type t8_expected = false;
99+
type t8 = Expect<Equal<t8_actual, t8_expected>>;
100+
101+
type t9_actual = Parse<JSONParser, "[1, 2, 3,]">["success"];
102+
type t9_expected = false;
103+
type t9 = Expect<Equal<t9_actual, t9_expected>>;
104+
105+
type t10_actual = Parse<JSONParser, "\\,">["success"];
106+
type t10_expected = false;
107+
type t10 = Expect<Equal<t10_actual, t10_expected>>;
108+
109+
// base parsers
110+
type Whitespace = " " | "\t" | "\n";
111+
112+
type Whitespace0 = Parse<Many0, Parse<Just, Whitespace>>;
113+
114+
type Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
115+
116+
type Digits0 = Parse<Many0, Parse<Just, Digit>>;
117+
type Digits1 = Parse<Many1, Parse<Just, Digit>>;
118+
119+
type Between<L extends Parser, R extends Parser, P extends Parser> = Parse<
120+
Left,
121+
[Parse<Right, [L, P]>, R]
122+
>;
123+
124+
type Str<T extends string, Acc extends Parser[] = []> = T extends `${infer Head}${infer Rest}`
125+
? Str<Rest, [...Acc, Parse<Just, Head>]>
126+
: Parse<MapResult, [Parse<Seq, Acc>, Join]>;
127+
128+
type Padded<P extends Parser> = Parse<Left, [P, Whitespace0]>;
129+
130+
type Sym<T extends string> = Padded<Str<T>>;
131+
132+
type JSONParser = Between<Whitespace0, EOF, JSONValueParser>;
133+
134+
type JSONValueParser = () => Padded<
135+
Parse<
136+
Choice,
137+
[
138+
JSONNullParser,
139+
JSONBooleanParser,
140+
JSONStringParser,
141+
JSONNumberParser,
142+
JSONArrayParser,
143+
JSONObjectParser
144+
]
145+
>
146+
>;
147+
148+
// `null`
149+
type JSONNullParser = Parse<MapResult, [Str<"null">, ToLiteral<null>]>;
150+
151+
// boolean
152+
type JSONBooleanParser = Parse<
153+
Choice,
154+
[
155+
Parse<MapResult, [Str<"true">, ToLiteral<true>]>,
156+
Parse<MapResult, [Str<"false">, ToLiteral<false>]>
157+
]
158+
>;
159+
160+
// string
161+
type JSONStringParser = Parse<
162+
MapResult,
163+
[
164+
Between<
165+
Parse<Just, '"'>,
166+
Parse<Just, '"'>,
167+
Parse<
168+
Many0,
169+
Parse<
170+
Choice,
171+
[
172+
Parse<NoneOf, '"' | "\\">,
173+
Parse<
174+
Right,
175+
[
176+
Parse<Just, "\\">,
177+
Parse<
178+
Choice,
179+
[
180+
Parse<Just, "\\">,
181+
Parse<Just, "/">,
182+
Parse<Just, '"'>,
183+
Parse<MapResult, [Parse<Just, "b">, ToLiteral<"\u0008">]>,
184+
Parse<MapResult, [Parse<Just, "f">, ToLiteral<"\u000c">]>,
185+
Parse<MapResult, [Parse<Just, "n">, ToLiteral<"\n">]>,
186+
Parse<MapResult, [Parse<Just, "r">, ToLiteral<"\r">]>,
187+
Parse<MapResult, [Parse<Just, "t">, ToLiteral<"\t">]>
188+
]
189+
>
190+
]
191+
>
192+
]
193+
>
194+
>
195+
>,
196+
Join
197+
]
198+
>;
199+
200+
// number
201+
type JSONNumberParser = Parse<
202+
MapResult,
203+
[
204+
Parse<
205+
Seq,
206+
[
207+
Parse<Maybe, Parse<Just, "-">>,
208+
Parse<
209+
Choice,
210+
[Parse<Just, "0">, Parse<Pair, [Parse<Just, Exclude<Digit, "0">>, Digits0]>]
211+
>,
212+
Parse<Maybe, Parse<Pair, [Parse<Just, ".">, Digits1]>>
213+
]
214+
>,
215+
UnwrapMaybe,
216+
Flatten,
217+
Join,
218+
StringToNumber
219+
]
220+
>;
221+
222+
// array
223+
type JSONArrayParser = Between<Sym<"[">, Sym<"]">, Parse<SepBy0, [JSONValueParser, Sym<",">]>>;
224+
225+
// object
226+
type JSONObjectParser = Between<
227+
Sym<"{">,
228+
Sym<"}">,
229+
Parse<
230+
MapResult,
231+
[
232+
Parse<
233+
SepBy0,
234+
[
235+
Parse<
236+
MapResult,
237+
[
238+
Parse<
239+
Pair,
240+
[Parse<Left, [Padded<JSONStringParser>, Sym<":">]>, JSONValueParser]
241+
>,
242+
MakeObject
243+
]
244+
>,
245+
Sym<",">
246+
]
247+
>,
248+
IntersectAll
249+
]
250+
>
251+
>;
252+
253+
// mappers
254+
interface ToLiteral<T> extends Mapper {
255+
map: () => T;
256+
}
257+
258+
interface Flatten extends Mapper {
259+
map: (data: this["data"]) => typeof data extends unknown[] ? DoFlatten<typeof data> : never;
260+
}
261+
262+
type DoFlatten<Array extends readonly unknown[]> = Array extends [infer Head, ...infer Rest]
263+
? Head extends readonly unknown[]
264+
? [...DoFlatten<Head>, ...DoFlatten<Rest>]
265+
: [Head, ...DoFlatten<Rest>]
266+
: [];
267+
268+
interface UnwrapMaybe extends Mapper {
269+
map: (data: this["data"]) => typeof data extends unknown[] ? DoUnwrapMaybe<typeof data> : never;
270+
}
271+
272+
type DoUnwrapMaybe<T extends unknown[], Acc extends unknown[] = []> = T extends [
273+
infer Head,
274+
...infer Rest
275+
]
276+
? DoUnwrapMaybe<
277+
Rest,
278+
Head extends MaybeResult
279+
? Head extends { success: true; data: infer Data }
280+
? [...Acc, Data]
281+
: Acc
282+
: [...Acc, Head]
283+
>
284+
: Acc;
285+
286+
interface StringToNumber extends Mapper {
287+
map: (data: this["data"]) => typeof data extends string ? DoStringToNumber<typeof data> : never;
288+
}
289+
290+
type DoStringToNumber<T extends string> = T extends `${infer N extends number}` ? N : never;
291+
292+
interface MakeObject extends Mapper {
293+
map: (
294+
data: this["data"]
295+
) => typeof data extends [PropertyKey, unknown]
296+
? { [Key in (typeof data)[0]]: (typeof data)[1] }
297+
: never;
298+
}
299+
300+
interface IntersectAll extends Mapper {
301+
map: (data: this["data"]) => typeof data extends object[] ? DoIntersectAll<typeof data> : never;
302+
}
303+
304+
type DoIntersectAll<T extends object[], Acc extends object = {}> = T extends [
305+
infer Head,
306+
...infer Rest extends object[]
307+
]
308+
? DoIntersectAll<Rest, Acc & Head>
309+
: Omit<Acc, never>;
310+
311+
export interface Join extends Mapper {
312+
map: (data: this["data"]) => typeof data extends string[] ? DoJoin<typeof data> : never;
313+
}
314+
315+
type DoJoin<T extends string[], Acc extends string = ""> = T extends [
316+
infer Head extends string,
317+
...infer Rest extends string[]
318+
]
319+
? DoJoin<Rest, `${Acc}${Head}`>
320+
: Acc;
321+
322+
type DigitParser = Parse<Just, Digit>;
323+
type IntParser = Parse<MapResult, [Parse<Many1, DigitParser>, Join, StringToNumber]>;
324+
325+
type t11_actual = Parse<IntParser, "123.4ff">;
326+
type t11_expected = {
327+
data: 123;
328+
rest: ".4ff";
329+
success: true;
330+
};
331+
type t11 = Expect<Equal<t11_actual, t11_expected>>;

0 commit comments

Comments
 (0)