Advent of Code in Go: #11

3 minute read

In this series I explore the Advent of Code, or AoC for short, with the Go programming language. Every day, as real life permits, I will be solving a puzzle from the series. I will document each day with a solution in Go and a walkthrough of the code.

You can find the previous walkthroughs here.

The puzzle

Today we are tracking a proces that is lost in an infinite grid. Not just any grid, a HEX grid. This is illustrated with the following high-end graphic:

  \ n  /
nw +--+ ne
  /    \
-+      +-
  \    /
sw +--+ se
  / s  \

As the input we get the path the proces has travelled and we need to figure out the number of steps the proces is away from us. Piece of cake I thought, thinking back to the Manhattan Distance from the 3rd puzzle. I figured I would take the starting point as 0,0 (a x/y grid) and then just increment/decrease depending on which way I am going. With ‘se’ I would do x + 1 and y - 1.

Sadly this did not work. I got close, but especially with the case of ‘se’ I failed miserably.

So, I started searching for some references. Hex grids seem to me to be used in games, so I thought I might find some game related articles on the matter. Then I found hexgrid, a go library for dealing with Hex Grids. Yay! This library also thought me about Axial Coordinates, which is key to a proper hex grid. The below illustration shows how to increase x and y depending on the steps taken. Take note of only the x+1 on ‘se’ here. Please see hex.go for a more thorough explanation about the algorithms.

          _ _
        /     \
   _ _ /(0,-1) \ _ _
 /     \  -R   /     \
/(-1,0) \ _ _ /(1,-1) \
\  -Q   /     \       /
 \ _ _ / (0,0) \ _ _ /
 /     \       /     \
/(-1,1) \ _ _ / (1,0) \
\       /     \  +Q   /
 \ _ _ / (0,1) \ _ _ /
       \  +R   /
        \ _ _ /

Basically using hexgrid.NewHex(x,y), where x and y are determined based on the above diagram you can then just do hexgrid.HexDistance(start,end) and you will get the distance between the 2 hexes.

I was not completely statisfied because I wanted to know how to do it myself. So I dug through the code and the following formula is what actually calculates the distance based on the x and y coordinates

abs(x) + abs(y) + abs(-x-y) / 2

So lets put this all together in some Go. First lets take our formula and make it a function.

func calculateDistance(x, y int) int {
	return int((math.Abs(float64(x)) + math.Abs(float64(y)) + math.Abs(float64(-x-y))) / 2.)
}

Then we can write our complete function to solve the path taken. Part 2 of the puzzle is to track the highst number of steps the proces was away from the centerpoint. Using the multi value return if functions we can easily wrap this up in a nice function.

func solve(input string) (distance int, maxdistance int, err error) {
	steps := strings.Split(input, ",")

	x, y := 0, 0

	for _, s := range steps {
		switch s {
		case "n":
			y--
		case "ne":
			x++
			y--
		case "se":
			x++
		case "s":
			y++
		case "sw":
			x--
			y++
		case "nw":
			x--
		default:
			log.Fatalf("Unknown direction %s\n", s)
		}

		distance = calculateDistance(x, y)
		if distance > maxdistance {
			maxdistance = distance
		}
	}

	return
}

To test it I can again utilize the table driven tests that seem to fit Go so nicely.

func TestSolve(t *testing.T) {
	tests := []struct {
		stream string
		score  int
	}{
		// stream, score
		{"ne,ne,ne", 3},
		{"ne,ne,sw,sw", 0},
		{"ne,ne,s,s", 2},
		{"se,sw,se,sw,sw", 3},
	}
	for _, test := range tests {
		distance, _, err := solve(test.stream)
		if err != nil {
			t.Error("Received an error: ", err)
			continue
		}

		if distance != test.score {
			t.Error(
				"Expected", test.score,
				"Got", distance)
		}
	}
}

All done for day 11!

Tags: , ,

Updated: