Advent of Code Metaprogramming: 2022, Day 1

Goal

Given only the simplified example in the problem
description, derive (at runtime) a
program that will correctly solve the full problem.

function deriveProgram(exampleInput, exampleOutput): Program {
  // todo: implement this...
}

// ...and then use it to solve the puzzle!
runProgram(program, realInput)

Strategy

1. Provide a library of simple, primitive functions (e.g. Split, Sum, Max)
2. Chain these simple functions together successively to transform input -> output step by step
3. Do a guided breadth-first search of the tree of all possible chains of transformations
   • Constrained by type signatures (cool somewhat-related talk on Youtube: Type-Directed Program Synthesis for RESTful APIs 🎥)
   • Provide heuristics and helper functions to select values for free parameters or arbitrary constants (such as what character to Split by, or how many array elements to Slice)

Philosophy

Simple breadth-first AST search guided by [heuristics, hunches, theories, assumptions, experience, symmetries, harmonies, rhythms, and patterns] -- in other words, INTUITION.

Investigate the boundaries between programming as science vs. art, by noticing which parts of the programming process are surprisingly difficult to formalize.

Sample transformations (Day 1, Part 1)

Start with the input given directly by the problem statement:

`1000
2000
3000

4000

5000
6000

7000
8000
9000

10000`

STEP 1: split (by double newlines)

[
  '1000\r\n2000\r\n3000',
  '4000',
  '5000\r\n6000',
  '7000\r\n8000\r\n9000',
  '10000',
]

Note that single newlines still appear within each array element. For now we have just grouped the data into "paragraphs" so to speak.

STEP 2: map(split) (by single newlines)

[
  ['1000', '2000', '3000'],
  ['4000'],
  ['5000', '6000'],
  ['7000', '8000', '9000'],
  ['10000'],
]

Since the top level data type is now array, we have to use map to access the inner array items, and split them into separate entries.

STEP 3: map(map(parse))

[
  [1000, 2000, 3000],
  [4000],
  [5000, 6000],
  [7000, 8000, 9000],
  [10000],
]

There's more than one valid ordering for this; we could have done parse at the very beginning and gotten an array with some NaN entries.

STEP 4: map(sum)

[6000, 4000, 11000, 24000, 10000]

Sum flattens the nested array to a single number (the sum of the array elements).

OUT: max

24000

Similarly max flattens an array into its maximum value. This is the final output specified by the puzzle's simplified sample.

Hand-written solution

Spoiler alert: here's a slightly ugly one-liner that follows this chain of transformations to solve Day 1 Part 1 of AOC 2022.

Solution

Math.max(
  ...input.split('\n\n').map(x => x
      .split('\n')
      .map(x => parseInt(x))
      .reduce((a, b) => a + b, 0)
  )
)

Just replace input with an inline string. I initially solved Part 1 by copy-pasting the 100+ line puzzle input inline into this one-liner in the browser dev tools console.

Ops: split, parse, sum, max, map(op)

We can collect the 5 very simple functions used in the sequence above. We'll call them "ops" (aka operations), just to set them apart from other functions.

These are the building blocks that the program synthesizer will use to construct an algorithm. Together, they form what we'll call a library. Their type signatures are as follows:

• split(string, string) -> array<string>
• parse(string) -> number
• sum(array<number>) -> number
• max(array<number>) -> number
• map(array<t>, op<array<t>, s>) -> array<s>

Strictly speaking these are pure functions (no side effects & deterministic; same input -> same output). They are chained together by passing the return value of the previous into the first argument of the next.

Free parameters

However, they may have additional parameters -- we'll call these "free" parameters (not bound to any particular value). These will need to be bound to some arbitrary, constant value when the program is derived.

Combinators

Make special note of the map op. It's a higher-order op, since it takes another op as a parameter. To designate this special case and others like it, we'll give it the name combinator.

Hurdle #1: Free parameters

Step 1 begins with a split op. This is one of the ones that takes an additional "free" parameter. We have to make a choice about what substring or character to split by. We can't try every possible string in the universe, so we need to make an educated guess, at least about a good starting point and ordering of potential guesses. It's okay if we need to try several, or several hundred, or even several hundred thousand.

Luckily there's some great heuristics we can use for the delimiter in split:

1. It must be a character or substring that appears in the input string. 'asdf'.split('z') is technically legal, but it just wraps the value in an array as ['asdf'] without splitting anything -- not really the intended use of the function.
2. It should probably be a char or substring that appears relatively often. Again, this is an educated guess, but a good rule of thumb. We could exhaustively calculate the most common substrings in O(n^2) time with some algorithm, or optimize it by short-circuiting as soon as we have a few good potential candidates.
3. It may appear in the input with a certain regularity. Imagine measuring the distance in between successive delimiters, and taking the standard deviation of that instance versus other substrings. But this could become very expensive.
4. Lastly, but most importantly of all -- it is extremely likely to be a commonly-used, standard delimiter. The usual suspects are -, _, ,, \n, and other similar special characters. It's a great bet to check these first (assuming they appear in the input string).

NOTE
This fuzzy/imprecise heuristic may seem hand-wavey compared to the brute-force exhaustive search through the tree of all possible Op chains. But it's one of the most important features of this approach.

Pure search, even breadth-first and constrained by compatible types, will hit limits of scale sooner rather than later, as the number (and generality) of Ops and Combinators increases, as with the size of the input.

Heuristics like this one, for choosing the parameter of split, are the black box which essentially serves to model the human intuition aspect of programming. If nothing else, this project serves to examine where that boundary line is -- which parts of programming are just playing "Type Tetris" (which a computer can do well), and which parts are subtle and hard-to-pin-down pattern recognition and experience.

The more a computer can fill this "intuitive" space, even in a crude or inefficient way, the more it will be able to generate end-to-end code.

One final method to bind the free parameter:

If you're running Copilot, type this and put your editor inside the parentheses.

'1000\r\n2000\r\n3000'.split()

It will suggest \r\n. It already knows.

Hurdle #2: Generating derived Ops from Combinators

Usually, searching for the next Op in the chain is simple. You just search the library for an Op who's input (first parameter) matches the return type of the previous one. This suffices to cover Step 1 in the example.

Step 2 poses a problem though: between Step 1 and 2 we need a function that takes a string[] and returns a string[][]. There's no Op in the library that has that signature. There's the map combinator, but it doesn't match the signature either. If this is the pathway we're hoping for the synthesis to discover, we'll need a way to bridge that gap.

This is where combinators show their strength. The key is to begin a tree-search in "Op-space", just like we are searching in "Value-space" for a chain of transformations that ends in the correct value. We can apply Combinators to each of our first-class Ops to produce nested versions of all of them, with their own type signatures.

We start with split, parse, sum, max, and then we generate the mapped versions map(split), map(parse), map(sum), map(max). They now each have a concrete type signature. The one we're looking for is either map(split) or map(parse), which both take a string[]. We can try both and see where they lead. The breadth-first and type-constrained direction of the search should (hopefully) ensure that we don't stray too far from the solution.

Every time we hit a dead end in generating new nodes, we can try another fresh batch of derived ops. We can even use other derived ops as a starting point. This solves Step 3 as well, where we apply map to map(parse) in order to obtain map(map(parse)) and access the inner-nested string array.

Hurdle #3: Combinators + free parameters

There's one more complication when combining Combinators with Ops that have free parameters. The free parameters need to be lifted into the type signature of the mapped function. In other words, map(split) takes two parameters (an array of strings, and a single delimiter). Luckily, the same heuristic-based parameter binding works from that point forward.

Putting it all together

To summarize, we are:

1. searching breadth-first
2. constraining the search to only matching type signatures
3. making educated guesses for free/unbound parameters like split delimiter
4. augmenting our library of Ops by deriving new ones from Combinators any time we hit a dead end
5. Continuing until we reach the solution, or hit a preset depth limit (10k-100k nodes)

Synthesized solution to Part 1

Here's the raw console output from running the synthesizer on Part 1. It's a bit messy, but in it you can see:

• The library including derived ops
• How many nodes it took to find the solution
• The program, as a sequence of ops (this matches our example from the very beginning)

$ npx vite-node days/1/1-1.ts
Library 📚 = 
[
  'split',
  'parse',
  'sum',
  'max',
  'map(split)',
  'map(parse)',
  'map(sum)',
  'map(max)',
  'map(map(split))',
  'map(map(parse))',
  'map(map(sum))',
  'map(map(max))'
]
looking for 24000
[...]
Solution found after 28 nodes checked
Program (length 6):
  🌱 -> "1000\r\n2000\r\n3000\r\n\r\n4000\r\n\r\n5000\r\n6000\r\n\r\n7000\r\n8000\r\n9000\r\n\r\n10000"
  split("\r\n\r\n") -> ["1000\r\n2000\r\n3000","4000","5000\r\n6000","7000\r\n8000\r\n9000","10000"]
  map(split)("\r\n") -> [["1000","2000","3000"],["4000"],["5000","6000"],["7000","8000","9000"],["10000"]]
  map(map(parse)) -> [[1000,2000,3000],[4000],[5000,6000],[7000,8000,9000],[10000]]
  map(sum) -> [6000,4000,11000,24000,10000]
  max -> 24000 🍃
Answer: 71124 ⭐

Synthesized solution to Part 2

To solve part 2, we only need to introduce two more Ops to the library: SortNums and Slice. Note that Slice has a free parameter, for the number of array elements to slice.

$ npx vite-node days/1/1-2.ts
Solution found after 974 nodes checked
looking for 45000
[...]
Solution found after 9 nodes checked
Program (length 8):
  🌱 -> "1000\r\n2000\r\n3000\r\n\r\n4000\r\n\r\n5000\r\n6000\r\n\r\n7000\r\n8000\r\n9000\r\n\r\n10000"
  split("\r\n\r\n") -> ["1000\r\n2000\r\n3000","4000","5000\r\n6000","7000\r\n8000\r\n9000","10000"]
  map(split)("\r\n") -> [["1000","2000","3000"],["4000"],["5000","6000"],["7000","8000","9000"],["10000"]]
  map(map(parse)) -> [[1000,2000,3000],[4000],[5000,6000],[7000,8000,9000],[10000]]
  map(sum) -> [6000,4000,11000,24000,10000]
  sort -> [24000,11000,10000,6000,4000]
  slice(3) -> [24000,11000,10000]
  sum -> 45000 🍃
Answer: 204639 ⭐

Stepping stones

If your eyes haven't glossed over by now, you might notice one difference in the output for part 2. There's 2 separate solutions. In this case, we provided multiple "stepping-stones" to guide the synthesis. The first program takes it halfway, and the second program continues where the first left off, through to the end.

This was necessary because going straight from the example input to the example output actually resulted in the wrong solution. That is -- it worked for the example dataset, in particular because the example values were presented in an already ascending sorted order. But it would not have worked for the real puzzle input.

Introducing one or more intermediate stepping-stone solutions helps the programmer communicate to the synthesizer what they're looking for. Further constraining the solution space with additional separate examples would accomplish the same thing.

Red, Green, Run

Taken to the extreme, program synthesis is like test-driven development, but the program is trivially derived from the tests (e.g. input + output) alone. In this paradigm, tests act as a kind of declarative language at a higher level of abstraction than the underlying synthesized implementation.

Open questions

• How does the synthesizer scale as the number (and generality) of OPS increases?
• How does the synthesizer scale as the size of the INPUT increases?
• How many INTERMEDIATE steps are needed to guide the search?
• Can some of the intermediate steps be parsed from the natural language description of the problem?

Repository

Github: https://github.com/nathanbabcock/advent-of-code-2022/blob/main/days/1/1-1.ts

Pull requests, comments, and discussion are welcome.