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
 Provide a library of simple, primitive functions (e.g.
Split
,Sum
,Max
)  Chain these simple functions together successively to transform input > output step by step
 Do a guided breadthfirst search of the tree of all possible chains of transformations
 Constrained by type signatures (cool somewhatrelated talk on Youtube: TypeDirected 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 toSlice
)
Philosophy
Simple breadthfirst 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.
Handwritten solution
Spoiler alert: here's a slightly ugly oneliner 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 copypasting the 100+ line puzzle input inline into this oneliner 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 higherorder 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
:

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. 
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 shortcircuiting as soon as we have a few good potential candidates.  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.

Lastly, but most importantly of all  it is extremely likely to be a commonlyused, 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 handwavey compared to the bruteforce 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 breadthfirst 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 hardtopindown 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 endtoend 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 treesearch in "Opspace", just like we are searching in "Valuespace" for a chain of transformations that ends in the correct value. We can apply Combinators to each of our firstclass 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 breadthfirst and typeconstrained 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 innernested 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 heuristicbased parameter binding works from that point forward.
Putting it all together
To summarize, we are:
 searching breadthfirst
 constraining the search to only matching type signatures
 making educated guesses for free/unbound parameters like
split
delimiter  augmenting our library of Ops by deriving new ones from Combinators any time we hit a dead end
 Continuing until we reach the solution, or hit a preset depth limit (10k100k 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 vitenode days/1/11.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 vitenode days/1/12.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 "steppingstones" 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 steppingstone 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 testdriven 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/adventofcode2022/blob/main/days/1/11.ts
Pull requests, comments, and discussion are welcome.
Top comments (0)