adventofcode2022

= Advent of Code 2022
:doctype: book
:toc:

image:https://godoc.org/gitlab.com/jhinrichsen/adventofcode2022?status.svg["godoc", link="https://godoc.org/gitlab.com/jhinrichsen/adventofcode2022"]
image:https://goreportcard.com/badge/gitlab.com/jhinrichsen/adventofcode2022["Go report card", link="https://goreportcard.com/report/gitlab.com/jhinrichsen/adventofcode2022"]
image:https://gitlab.com/jhinrichsen/adventofcode2022/badges/main/pipeline.svg[link="https://gitlab.com/jhinrichsen/adventofcode2022/-/commits/main",title="pipeline status"]
image:https://gitlab.com/jhinrichsen/adventofcode2022/badges/main/coverage.svg[link="https://gitlab.com/jhinrichsen/adventofcode2022/-/commits/main",title="coverage report"]


My take on https://adventofcode.com/2022/ in Go. As usual, i don't particularly
care if i provide my solutions _fast_, i try to be _correct_ on the first
answer, and care for being runtime efficient.
Most, if not all, puzzles are backed by unit testing the examples, and by some
benchmarks.

Expected results are hard coded into the unit tests, so unless you are peeking
for a solution avoid looking at those.


Number of tries for a correct answer:

|===
| Day | part 1 | part 2
| 1   | 1      | 1
| 2   | 1      | 1
| 3   | 1      | 1
| 4   | 2      | 1
| 5   | 1      | 1
| 6   | 1      | 1
| 7   | 2      | 1
| 8   | 1      | 1
| 9   | 1      | 1
| 10  | 1      | 1
| 11  | 1      |
| 12  | 1      | 1
| 13  |        |
| 14  |        |
| 15  |        |
| 16  |        |
| 17  | 1      | - (+1)
| 18  | 1      | - (+1)
| 19  |        |
| 20  | - (+2) |
| 21  | 1      |
| 22  | 2 |
| 23  |  |
| 24  |  |
| 25  | 1      |
|===

Benchmark summary
----
name            time/op
Day01Part2-8    55.5µs ± 8%
Day02-8         63.7µs ±20%
Day03Part1-8    51.7µs ±14%
Day03Part2-8     134µs ± 6%
Day04Part1-8     598µs ±10%
Day04Part2-8     575µs ±16%
Day05-8         3.33µs ± 3%
Day06Part1-8    8.59µs ±26%
Day06Part2-8    33.4µs ±19%
Day06Hashmap-8   236µs ±17%
Day10-8         2.16µs ± 8%

name            alloc/op
Day01Part2-8    4.14kB ± 0%
Day02-8          0.00B
Day03Part1-8    2.40kB ± 0%
Day03Part2-8    6.19kB ± 0%
Day04Part1-8    96.0kB ± 0%
Day04Part2-8    96.0kB ± 0%
Day05-8         4.14kB ± 0%
Day06Part1-8     0.00B
Day06Part2-8     0.00B
Day06Hashmap-8    653B ± 0%
Day10-8         2.30kB ± 0%

name            allocs/op
Day01Part2-8      11.0 ± 0%
Day02-8           0.00
Day03Part1-8       300 ± 0%
Day03Part2-8       368 ± 0%
Day04Part1-8     3.00k ± 0%
Day04Part2-8     3.00k ± 0%
Day05-8           3.00 ± 0%
Day06Part1-8      0.00
Day06Part2-8      0.00
Day06Hashmap-8    5.00 ± 0%
Day10-8           1.00 ± 0%
----


== Day 1

Benchmark:
----
CGO_ENABLED=0 go test -bench=. -run="" -benchmem
goos: linux
goarch: amd64
pkg: gitlab.com/jhinrichsen/adventofcode2022
cpu: AMD Ryzen 5 3400G with Radeon Vega Graphics
BenchmarkDay01Part2-8   	   19648	     66464 ns/op	    4144 B/op	      11 allocs/op
PASS
ok  	gitlab.com/jhinrichsen/adventofcode2022	1.934s
----

== Day 2

Implementation of a map based lookup took 25 min for part1.

Benchmark for map inside function:
----
BenchmarkDay02Part1-8   	   20312	     60303 ns/op	     416 B/op	       1 allocs/op
----

Benchmark for static map outside of function:

----
BenchmarkDay02Part1-8   	   20782	     55999 ns/op	       0 B/op	       0 allocs/op
----

56 ms for 2.500 draws, i.e. 22 ns for one draw or 45 MHz.
We are churning draws at three times the CPU frequency of an Arduino.

== Day 3

----
BenchmarkDay03-8   	   22658	     48739 ns/op	       0 B/op 0 allocs/op (1)
----
(1) Go 1.18

48739 ns/op for 300 op is 162 ns/op or 6 MHz.

Coming back for part 2.
Slightly rearranging my code to separate the intersect() and prio() part.
Haskell teaches you that there is no such thing as f(a, b).
Karma is to be found within functional composition.
`intersect(a, b, c) === intersect(intersect(a, b), c)`

Although slightly more generic, part 1 shows

----
BenchmarkDay03Part1-8   	   26200	     43238 ns/op	    2400 B/op	     300 allocs/op (1)
BenchmarkDay03Part2-8   	   10000	    150718 ns/op	    6192 B/op	     368 allocs/op
----
(1) Go 1.19

When intersecting, the outer `intersect()` can stop after the first match (as
does part 1).

----
name          old time/op    new time/op    delta
Day03Part1-8    47.7µs ± 7%    48.2µs ±10%     ~     (p=0.481 n=10+10)
Day03Part2-8     162µs ±10%     131µs ±15%  -19.41%  (p=0.000 n=10+10)
----


== Day 4

First try failed, stupid error in `Contains()` predicate.
The bad code below will mark the two ranges as fully contained, but they are
not.
----
	// Error: [4-94] [3-3] marked as fully contained. Spot the error?
	return b1 <= a1 && b2 <= a2 || a1 <= b1 && b2 <= a2
----

Benchmark results:
----
name          time/op
Day04Part1-8   604µs ±12%
Day04Part2-8   621µs ±10%

name          alloc/op
Day04Part1-8  96.0kB ± 0%
Day04Part2-8  96.0kB ± 0%

name          allocs/op
Day04Part1-8   3.00k ± 0%
Day04Part2-8   3.00k ± 0%
----


== Day 5
During unit testing, i corrected these two errors:

- Stacks are 1-based, not 0-based
- The result consists of the _last_ crate of each stack, not the _first_

----
BenchmarkDay05-8   	  529513	      2985 ns/op	    4145 B/op	       3 allocs/op
----

== Day 6

Benchmark for puzzle input 1, 4 KB/ 4096 Bytes per op:
----
BenchmarkDay06-8   	   10000	    105913 ns/op	       0 B/op	       0 allocs/op
----

Generic hashmap based implementation for part 1 and part 2:
----
BenchmarkDay06Part1-8   	   10270	    131068 ns/op	       0 B/op	       0 allocs/op
BenchmarkDay06Part2-8   	    5142	    199927 ns/op	     653 B/op	       5 allocs/op
----

26 ns per byte, equals 39 MHz. At a marker size of 14, garbage collection seems
to kick in because of the hashmap being larger than default.

Retry the bits.OnesCount() approach, this time using a fresh window for each
step and _not_ trying to slide:

----
BenchmarkDay06Part1-8   	  156498	      7430 ns/op	       0 B/op	       0 allocs/op
BenchmarkDay06Part2-8   	   40934	     27027 ns/op	       0 B/op	       0 allocs/op
----

Much better. Want to know what happens under the hood?

----
00079 (day06.go:49)	MOVBQZX	runtime.x86HasPOPCNT(SB), DX   ; check if CPU supports POPCNT instruction
00087 (day06.go:49)	TESTL	DX, DX
00089 (day06.go:52)	JEQ	98                             ; no, continue at 98
00091 (day06.go:52)	POPCNTL	DI, DI                         ; yes, execute
00095 (day06.go:52)	NOP
00096 (day06.go:52)	JMP	151                            ; continue next command
00098 (day06.go:47)	MOVQ	BX, ""..autotmp_8+24(SP)       ; prepare stack based function call
00103 (day06.go:49)	MOVQ	R8, ""..autotmp_9+16(SP)
00108 (day06.go:52)	MOVL	DI, AX
00110 (day06.go:52)	PCDATA	$1, $0
00110 (day06.go:52)	CALL	math/bits.OnesCount32(SB)      ; call Go based implementation
00115 (day06.go:52)	MOVQ	"".size+64(SP), CX
----

== Day 07

Ok, pretty straightforward, but unit tests fail because of 'total size of at
most 100000. I misread as "larger than 100000", because we are searching for big
ones, no?

First try fails miserably.
A couple of checks all look good.
In the end, i search for a working implementation, and trace back my error.
I do not cater for empty intermediate directories, i.e. i don't account for `b`
in `/a/b/c/d.ext` if `b` has no files in it.
Second try works.

Second puzzle unit tests ran successfully the first time.

== Day 8

For the first time, personal leaderboard shows me in 5 digit position.

----
      --------Part 1---------   --------Part 2---------
Day       Time    Rank  Score       Time    Rank  Score
  8       >24h   75414      0          -       -      -
  7       >24h   79816      0       >24h   78203      0
  6       >24h  112214      0       >24h  111265      0
  5       >24h  115470      0          -       -      -
  4       >24h  133385      0          -       -      -
  3       >24h  142512      0          -       -      -
  2       >24h  167617      0       >24h  161452      0
  1       >24h  197787      0       >24h  190653      0
----

== Day 10

Upgraded to Fedora 37, which brings Go 1.19.3.

Took me a while (40 min) to figure out that the register changes _after_ the
second cycle.
Interestingly, no off-by-one error this time.

----
BenchmarkDay10-8   	  692694	      2291 ns/op	    2304 B/op	       1 allocs/op
----

2300 ns/op for 138 instructions is 17 ns per instruction, i.e. 60 MHz.

When checking which instruction to execute, comparing the command like `op ==
"noop"` is the same speed as `op[0] == 'n'`.

Rolling our own strconv.Atoi() parser:
----
BenchmarkDay10-8   	  964717	      1665 ns/op	    2304 B/op	       1 allocs/op
----

Nice, shaved 30% off.
1665 ns/op for 138 instructions is 17 ns per instruction, i.e. 83 MHz.

----
$ benchstat day10_atoi.txt day10_custom.txt
name     old time/op    new time/op    delta
Day10-8    2.92µs ± 3%    2.05µs ± 6%  -29.72%  (p=0.000 n=19+17)

name     old alloc/op   new alloc/op   delta
Day10-8    2.30kB ± 0%    2.30kB ± 0%     ~     (all equal)

name     old allocs/op  new allocs/op  delta
Day10-8      1.00 ± 0%      1.00 ± 0%     ~     (all equal)
----

Our virtual CPU at 83 MHz is at least half as fast as the clock on an Espressif
32-Bit-RISC-V-MCU at 160 MHz.

I just realized everything i contributed so far has been on my reddit account,
not my google account as in previous years. I just lost 7000 places, but i am at
91% do that should not matter.

----
      --------Part 1---------   --------Part 2---------
Day       Time    Rank  Score       Time    Rank  Score
 10   19:12:40   50125      0          -       -      -
  9       >24h   61568      0          -       -      -
  8       >24h   80585      0          -       -      -
  7       >24h   84244      0       >24h   82424      0
  6       >24h  118055      0       >24h  117019      0
  5       >24h  121567      0       >24h  119444      0
  4       >24h  143620      0       >24h  141247      0
  3       >24h  161404      0       >24h  153837      0
  2       >24h  187765      0       >24h  179743      0
  1       >24h  224250      0       >24h  215380      0
----

Well worth switching, my google account looks so much nicer.

=== Part 2

Part 2 requires human intervention to parse the generated CRT like output.
We already had some of these puzzles, if i remember correctly in 2017.
My eyeballs always have trouble deciphering these ASCII art images.
It is a little bit better when using the unicode block character `█` instead of
the original `#`.
Or, when using an editor that interactively shows search patterns, such as
`vim`.
Just highlight the CRT image (vim visual block) and search for `# ` using `:%s/#
/`.
As an example, here's the output of a sample Plain PBM (portable Bit Map).
Can you spot the text? I can't.

----
P1
# feep.pbm
24 7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0
0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
----

However, selecting the block in vim, and applying `:%s/1 /` reveals the text.

image::feep.png[]

Once we get this, we can run it through an OCR, e.g. tesseract, to automatically
test for the correct results (day10_test.go, TestDay10Part2Tesseract()).

== Day 11

`Monkey` parsing was a bit of an typing effort, but a no-brainer.
Looking at Monkey #0 and #1, and their Operations (`* 19` and `+ 6`) make me
start a simple handrolled parser.
For Monkey #3 (`new = old * old`) i switched from this basic parser to the Go
internal `eval()` equivalent.
While every Python programmer is familiar with `eval()`, the Go equivalent is
rather unknown.

But yes, Go is self hosted, which means its compiler is written in Go.
So you can use Go to parse *and evaluate* an expressions.
Remember that `new = old * old` is a statement, and `old * old` an expression.

----
// Eval uses Go's internal compiler to evaluate an expression.
func Eval(expr string, m map[string]float64) float64 {
	// wipe global scope
	types.Universe = types.NewScope(nil, token.NoPos, token.NoPos, "universe") (1)

	for k, v := range m {
		c := types.NewConst(
			token.NoPos,
			nil,
			k,
			types.Typ[types.Float64],
			constant.MakeFloat64(float64(v)))
		types.Universe.Insert(c)
	}

	fs := token.NewFileSet()
	tv, err := types.Eval(fs, nil, token.NoPos, expr)
	if err != nil {
		panic(err)
	}
	n, _ := constant.Float64Val(tv.Value)
	return n
}
----
(1) Do not forget to redeclare global between calls, otherwise `old` will be
evaluated once, and the cached value returned for the next call.

For part #2, this approach blows miserably.
I started using an `int` based implementation, but it resulted in integer
overflow.
Switching from `int` to `float64` did not improve the situation, somewhere up
and above `1e376` even float64 reaches its end of precision.

In earlier years, i would have switched to arbitrary precision library.
But all in all the number crunching part of AOC has vanished.
I remember years 201x when CPU and fan went ballistic for 15 minutes to
calculate a solution, but nowadays typical runtimes are usually subsecond.
In addition, all four divisors in the example are primes, and you don't fight
primes with CPU.
So, obviously, switching to https://pkg.go.dev/math/big[arbitrary-precision
arithmetic]
(big numbers) seems a dead end.

I took a peek at the reddit hint channel, where people talked about abstract
number theory, and x^2^ divided by n can be reduced to mumble mumble mumble.

So here's why i don't do part 2:

* It seems you need to look at the actual expressions to derive a solution to
  keep your worry levels low
* I understand the division part, and taking a short circuit on the expression,
  but the result is passed to the next monkey, and this result is different. I
  accept you can bring down worry level `1e376` to, say, `15`, but then this is
  passed to the next monkey, and `1e376+3` is definitely different from `15+3`.
* I do not know how to write an abstract algebraic resolver
* I do not want to know how to write one

Please go ahead and read about the Xerox JBIG2 problem, and optimization issues.

So for now, another unsolved puzzle in a long line of unresolved puzzles.

----
[2022] 18*
[2021] 18*
[2020] 45*
[2019] 26*
[2018] 14*
[2017] 13*
[2016] 32*
[2015] 50*

Total stars: 216*
----

Time to apply the `¯\_(ツ)_/¯` pattern.

== Day12

Looks like a path finding problem, Dijkstra to the rescue.
I grep'ed my old AOCs, and 2016's day 13 was the same category.
Back then i used an https://github.com/beefsack/go-astar[external A* library].
Although only 2 contributors, i picked it because of its nice examples that fit
well.
This time, none of the standard examples worked out, so i had to dive deeper
into the library.

=== beefsack's go-astar library

The function signature to calculate a path is

----
func Path(from, to Pather) (path []Pather, distance float64, found bool)
----

No surprises so far. Pather is an dominant interface

----
type Pather interface {
	// PathNeighbors returns the direct neighboring nodes of this node which
	// can be pathed to.
	PathNeighbors() []Pather

----

Of course, Pather need to find their neighbors somehow.
But this single interface signature leads to a problem.
In path finding, you usually have an area, often a grid, and cells.
In our Day 13 puzzle, the puzzle input is the area, and S (the starting point),
and E (the end point) are two cells in this area.
Now, should area or cell implement the Pather interface?
Obviously, only cells have neighbours.
But cells need access to the world to find their neighbors.

In the library examples, the area is called World, and a cell is called Tile.
The world has references to Tiles, and each and every Tile has a backref to the
world.
On top, you have the Day 13 grid itself, so we are housekeeping three data
lakes.
Anyway, we need to ship this thing out the door, so why bother.
Go being a statically typed language and everything, both `go build` and `go
vet` agree we have made it.

But.

CAUTION: panic() somewhere deep inside the guts of the external library.

=== Workaround #1

The library keeps track of the Day 13 struct that implements Pather.
It does so by storing cells in an internal map.
And Go's map has some limitations when it comes to storing.
Long story short you can only store something that is comparable by ==.
And channels, slices, and functions (just to name a few) cannot be compared
using ==.
Our Day12 struct has a slice to all of its navigatable neighbors.

Slices cannot be compared, but arrays can.
So, instead of an undefined number of []neighbors, we know that we can move only
left, right, top, or down, so [4]neighbors, returning the array as a slice as
dicated by the Pather interface: neighbors[:].

CAUTION: runtime error: invalid memory address or nil pointer dereference

=== Workaround #2

The panic() is again buried deeply inside the guts of the external library.
Ok, seems as if  2 passengers in a car built for 4 is not going to happen.
Hand peeling off unused neighbors, and returning the slice neighbors[0:n].

CAUTION: panic: runtime error: hash of unhashable type

Seems as if we made it past the initial stage, but when applying the heuristic
part of A*, the priority queue reads

----
func (pq *priorityQueue) Push(x interface{}) {
----

Well, one of my personal don'ts.
https://www.youtube.com/watch?v=PAAkCSZUG1c&t=456s[interface{} says nothing]
Even in C, the void * carries more information than interface{}.
You know it is a pointer, at least.
interface{} in Go has about the same information as void in C.
Nothing.
Anything.
Both.
One or the other.
I never use it, because i am stupid and i NEED the compiler, its type checker,
and go vet.

=== Workaround #3

Throw the beefstack library out of the window and migrate to a library that has
a better user interface.

=== gonum to the rescue

https://pkg.go.dev/gonum.org/v1/gonum/graph/path[gonum] seems like a reasonable
choice.
489 forks, 6.2k stars.
A* by Peter Hart, Nils Nilsson and Bertram Raphael.
Dijkstra, Floyd-Warshall, Joseph Kruskal, Jin Y. Yen, the who-is-who of path
finding.

The signature for A* reads
----
func AStar(s, t graph.Node, g traverse.Graph, h Heuristic) (path Shortest, expanded int)
----

s source, t target node, our cell.

g traverse Graph, our world.

h, the add-on compared to Dijkstra, and a default
https://github.com/gonum/gonum/blob/v0.12.0/graph/path/a_star.go#L99[
NullHeuristic].

Plus, i still have an open position for a good DAG lib, so i'll try gonum.

gonum lacks some example documentation, but other than that it works like a
charm.

== Day 17

Got part 1 right on first try.
For part 2, 1_000_000_000_000 cycles does not sound reasonable, even in Go.

TODO: There must be some sort of cycle.
I'd keep the surface of the tower as a 7 numbers wide pattern, plus the shape
ID, plus the resulting surface, plus the increase in height.


== Day 18

Got part 2 wrong, i think i need to cater for interior air holes that stick
together.

TODO: move from 0,0,0 to maxX, maxY, maxZ until the first non-empty cube is
reached.
Then, keeping left hand on the object, flood-fill along the border to count
surface elements.

== Day 19

TODO: need to maxmize the throughput. Keep a list of quotients for each factory,
and build new stuff to minimize current quotients against optimal quotient.

== Day 20

So easy the problem, so nasty the implementation.
I started copy()ing slices around, using an working buffer in analogy to a
offscreen image, and filling like

----
count int

add = func(is []int) {
    count += copy(dst[count:], is)
}
----

Unfortunately, i never got the indexes and the wrapping and the left/right
correct.

For a second strategy, i projected the mix to a bubble sort, i.e. the number is
swapped with it immediate neighbour to the left or to the right N times.

When wrapping would occur, it is replaced with swapping to the other direction.

TODO: Got the example right, but part 1 fails for the second time.

== Day 21

Nice example for channels.
Reading from a close()d channel returns the empty value without blocking.

----
$ go test -run=xxx -bench=Day21 -benchmem -count=10
goos: darwin
goarch: amd64
pkg: gitlab.com/jhinrichsen/adventofcode2022
cpu: Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz
BenchmarkDay21Part1-16    	     718	   1622373 ns/op	  930030 B/op	    9248 allocs/op
BenchmarkDay21Part1-16    	     742	   1601952 ns/op	  929759 B/op	    9245 allocs/op
BenchmarkDay21Part1-16    	     744	   1598219 ns/op	  929678 B/op	    9244 allocs/op
BenchmarkDay21Part1-16    	     736	   1600565 ns/op	  929125 B/op	    9238 allocs/op
BenchmarkDay21Part1-16    	     717	   1606044 ns/op	  929628 B/op	    9244 allocs/op
BenchmarkDay21Part1-16    	     744	   1607683 ns/op	  929422 B/op	    9241 allocs/op
BenchmarkDay21Part1-16    	     746	   1599818 ns/op	  929315 B/op	    9240 allocs/op
BenchmarkDay21Part1-16    	     734	   1620898 ns/op	  930152 B/op	    9249 allocs/op
BenchmarkDay21Part1-16    	     741	   1610202 ns/op	  929156 B/op	    9239 allocs/op
BenchmarkDay21Part1-16    	     718	   1601254 ns/op	  929563 B/op	    9243 allocs/op
----

Around 1.6 ms for 2.265 monkeys.

== Day 22

Got caught in triple logic (wall, walk, wrap) in a map[complex128]bool.

== Day 25

Trying a + operator in the Snafu domain, i.e. without conversion to decimal.
Got it right on the first try.
The algorithm is pretty slow, about 15 times slower as a conversion to dec and
then using the CPU's ADD operation.