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.


Tags: ,