2019-12-03
I got tired of dinky RISC-V boards with too-small memory (even my Z80 has more memory than these boards, just saying), so I started trying to resurrect my project to get xv6 working on the MAix BiT which doesn't skimp on memory. It also happens to have a neural network hardware accelerator which is cool and all but not really what I need right now.
So.... compiling the toolchain. It's a pain. Takes a long time. We'll get through this. I'm taking notes.
I've been doing the advent of code again. I got day 3 done in a record (for me) 37 minutes, so that was cool. I was also pretty happy with my day 2 intcode VM.
I've been fortunate to be a part of a mailing list that's participating in this and it's a lot of fun to see how everyone else is approaching it.
Here's my write up so far:
Day 1
Pretty straightforward, nothing to write home about. It's a great warmup, though.
Day 2
One of the things that often sucks to do in these challenges is writing the parsing code; today I started trying to just hardcode my actual inputs in (and I can use the unit tests too).
I started with a VM struct (and that's how I solved it at first) but I wasn't really happy with that - so I simplified things a little bit, expecting that an intcode interpreter would be used again in the future. At first, I wanted to increment the instruction pointer the as I went along, but Go makes that rather unpleasant to do that way.
One key feature I wanted was to be able to make modifications easy to do, so I added a way to do that inline.
Here's my intcode interpreter, packaged in ic/intcode.go:
// intcode.go
// ...
const (
OpAdd = 1
OpMul = 2
OpHalt = 99
)
type mod struct {
Pos int
Val int
}
// A mod encodes a change to the program to be made at runtime.
func Mod(pos, val int) mod {
return mod{
Pos: pos,
Val: val,
}
}
// Run copies the program to a new memory space, applies any mods, and
// the runs it, returning the program. For Day 2, all of the results
// are in memory position 0, but I don't want to make that assumption
// for the future.
func Run(prog []int, mods ...mod) ([]int, error) {
mem := make([]int, len(prog))
copy(mem, prog)
for _, mod := range mods {
mem[mod.Pos] = mod.Val
}
ip := 0
run := true
for {
if !run {
break
}
op := mem[ip]
switch op {
case OpAdd:
arg1 := mem[ip+1]
arg2 := mem[ip+2]
dest := mem[ip+3]
mem[dest] = mem[arg1] + mem[arg2]
ip += 4
case OpMul:
arg1 := mem[ip+1]
arg2 := mem[ip+2]
dest := mem[ip+3]
mem[dest] = mem[arg1] * mem[arg2]
ip += 4
case OpHalt:
run = false
default:
return mem, fmt.Errorf("VM: invalid opcode [ip=%d]", ip)
}
}
return mem, nil
}
And the corresponding solution file:
// day02.go
func part1() {
// Part 1
prog, err := intcode.Run(
gravityAssistProgram,
intcode.Mod(1, 12),
intcode.Mod(2, 2),
)
if err != nil {
fmt.Fprintf(os.Stderr, "[!] %s\n", err)
os.Exit(1)
}
fmt.Println(prog[0])
}
func part2() {
for noun := 0; noun < 99; noun++ {
for verb := 0; verb < 99; verb++ {
prog, err := intcode.Run(
gravityAssistProgram,
intcode.Mod(1, noun),
intcode.Mod(2, verb),
)
if err != nil {
continue
}
result := prog[0]
if result == 19690720 {
fmt.Println(noun, verb)
}
}
}
}
It took me two tries for part 2 because I was looking for 19690702 at first...
Day 3
I did this right as it happened, and my goal was to see how quick I could do it in:
| --------Part 1-------- --------Part 2--------
| Day Time Rank Score Time Rank Score
| 3 00:25:54 784 0 00:36:25 722 0
As such, this is code that I'm really not proud of (the commit message is 'forgive me father for i have sinned').
Instead of writing file parsing stuff, I just hardcoded my inputs in again.
I solved the first part by creating a set of visited points (map[point]bool) for each wire, then finding the common points. Then I picked the point with the closest manhattan distance.
For the second part, I changed my set to a map[point]int, where each entry was the number of steps to get to that point.
I'm not proud of the quality, but I'm happy with the overall time it took. And, bonus, I got each part right on the first try:
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func manhattan(x1, y1, x2, y2 int) int {
return abs(x1-x2) + abs(y1-y2)
}
type point struct {
x int
y int
}
func (p point) distance(o point) int {
return manhattan(p.x, p.y, o.x, o.y)
}
func move(m *map[point]int, from point, step string, z int) (point, int) {
dir := step[0]
dist, err := strconv.Atoi(step[1:])
if err != nil {
panic(err)
}
p := point{from.x, from.y}
switch dir {
case 'D':
for from.y-p.y < dist {
p.y--
(*m)[p] = z
z++
}
case 'L':
for p.x-from.x < dist {
p.x++
(*m)[p] = z
z++
}
case 'R':
for from.x-p.x < dist {
p.x--
(*m)[p] = z
z++
}
case 'U':
for p.y-from.y < dist {
p.y++
(*m)[p] = z
z++
}
}
return p, z
}
func buildPath(steps []string) map[point]int {
m := map[point]int{}
p := point{}
z := 0
for _, step := range steps {
p, z = move(&m, p, step, z)
}
return m
}
type intersect struct {
point
z int
}
func intersections(m1, m2 map[point]int) []intersect {
isects := []intersect{}
for p, z := range m1 {
if z2, ok := m2[p]; ok {
// +2 because the intersection counts as a
// step for both wires, this is the one thing
// that tripped me up
isects = append(isects, intersect{p, z + z2 + 2})
}
}
return isects
}
func closest(points []intersect) (point, int) {
central := point{}
clopt := point{}
clodst := -1
for _, point := range points {
mdist := point.distance(central)
if clodst == -1 || mdist < clodst {
clodst = mdist
clopt = point.point
}
}
return clopt, clodst
}
func fastest(points []intersect) (point, int) {
clop := point{}
cloz := -1
for _, point := range points {
if cloz == -1 || point.z < cloz {
cloz = point.z
clop = point.point
}
}
return clop, cloz
}
func part1() {
_, dst := closest(intersections(buildPath(wire1), buildPath(wire2)))
fmt.Println(dst)
}
func part2() {
_, z := fastest(intersections(buildPath(wire1), buildPath(wire2)))
fmt.Println(z)
}
func main() {
part1()
part2()
}
Profiling code
I made a little Go package that instruments my functions; it works because I write my code with top-level part1() and part2() functions. This means that my main function now looks like this:
func main() {
inst.Run("day01p1", part1)
inst.Run("day01p2", part2)
}
The package, inst, has a single file:
// Package inst contains tracing and monitoring code for instrumenting
// code.
package inst
import (
"log"
"runtime"
"time"
)
// Run executes function f, printing total runtime and allocation
// sizes at the end.
func Run(label string, f func()) {
var start, end int64
var mem runtime.MemStats
start = time.Now().UnixNano()
f()
end = time.Now().UnixNano()
runtime.ReadMemStats(&mem)
runtime := (end - start) / 1000
tAlloc := mem.TotalAlloc / 1024
alloc := mem.HeapAlloc / 1024
log.Printf("%s: complete in %dus, total allocated %d kB, current heap allocation %d kB",
label, runtime, tAlloc, alloc)
}
For grins, here's my runtimes:
~/code/aoc/advent2019
(0) <phobos:kyle> $ gmake
for day in day01 day02 day03 ; \
do \
( cd $day && go run $day.go ); \
done
3252897
2019/12/03 19:24:54 day01p1: complete in 199us, total allocated 69 kB, current
heap allocation 69 kB
4876469
2019/12/03 19:24:54 day01p2: complete in 24us, total allocated 81 kB, current
heap allocation 81 kB
3562624
2019/12/03 19:24:54 day02p1: complete in 68us, total allocated 63 kB, current
heap allocation 63 kB
82 98
2019/12/03 19:24:54 day02p2: complete in 21583us, total allocated 10344 kB,
current heap allocation 2867 kB
768
2019/12/03 19:24:55 day03p1: complete in 78183us, total allocated 30808 kB,
current heap allocation 20413 kB
8684
2019/12/03 19:24:55 day03p2: complete in 86672us, total allocated 61526 kB,
current heap allocation 20416 kB
You can see the effect on memory of my solution to today's problem - fast to write, not so elegant.