Advent of Code in Go: #2

6 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

The puzzle today was about checksumming a spreadsheet. As with all they days the puzzle has 2 parts. The workers in the machine give us some instructions:

The spreadsheet consists of rows of apparently-random numbers. To make sure the recovery process is on the right track, they need you to calculate the spreadsheet’s checksum. For each row, determine the difference between the largest value and the smallest value; the checksum is the sum of all of these differences.

I also get some sample data to prepare my testcases with.

Given the following spreadsheet:

5 1 9 5
7 5 3
2 4 6 8
  • The first row’s largest and smallest values are 9 and 1, and their difference is 8.
  • The second row’s largest and smallest values are 7 and 3, and their difference is 4.
  • The third row’s difference is 6.

Using the same test setup as yesterday I setup my tests.

type puzzle2 struct {
	values string
	result int
}

var p2test = []puzzle2{
	{"5 1 9 5", 8},
	{"7 5 3", 4},
	{"2 4 6 8", 6},
}

func TestRowChecksum(t *testing.T) {
	for _, pair := range p2test {
		result := rowchecksum(pair.values)

		if result != pair.result {
			t.Error(
				"For", pair.values,
				"expected", pair.result,
				"Got", result,
			)
		}
	}
}

In the input for our puzzle I see each cell of a row can have a number larger then 9 (a single digit number), so the conversion I used yesterday does not really work. In the documentation I found strings.Fields() which will actually split a string based on one or more whitespace characters, such as space or tab.

So I put the input values in a text file and adjust my convert function.

func convert(s string) []int {
	fields := strings.Fields(s)
	output := make([]int, len(fields))

	for i, e := range fields {
		output[i] = atoi(string(e))
	}

	return output
}

Now we need to find the min and max values in each row. I would’ve thought there was some builtin function to do this on arrays, but I could not find any. So I wrote the following functions

func MinIntArray(v []int) (m int) {
	if len(v) > 0 {
		m = v[0]
	}
	for i := 1; i < len(v); i++ {
		if v[i] < m {
			m = v[i]
		}
	}
	return
}

func MaxIntArray(v []int) (m int) {
	if len(v) > 0 {
		m = v[0]
	}
	for i := 1; i < len(v); i++ {
		if v[i] > m {
			m = v[i]
		}
	}
	return
}

With the basic functionality there, lets combine it into a single function which returns multiple values.

func minmax(v []int) (int, int) {
	min := MinIntArray(v)
	max := MaxIntArray(v)
	return min, max
}

I can now calculate the checksum for a single row of data.

func rowchecksum(s string) int {
	cells := convert(s)

	min, max := minmax(cells)

	return max - min
}

But the actual data is in a file on the filesystem, so how do we get that? So the bufio.NewScanner seems to be the way to go. I also learned that you can create a defer, to close resources, which will be called when the function returns.

So I loop over the file, each line being appended to the lines array. append will actually grow an array, so you don’t need to define it with a static length.

func readLines(path string) ([]string, error) {
	file, err := os.Open(path)
	if err != nil {
		return nil, err
	}
	defer file.Close()

	var lines []string
	scanner := bufio.NewScanner(file)
	for scanner.Scan() {
		lines = append(lines, scanner.Text())
	}
	return lines, scanner.Err()
}

In the main function I can now read the file, then iterate over each entry in lines and add the row checksum to the running sum value.

lines, err := readLines("puzzle2.txt")

if err != nil {
	panic("Failed to read input file")
}

sum := 0
for _, v := range lines {
	sum += rowchecksum(v)
}

fmt.Printf("Puzzle 1 answer: %d\n", sum)

The answer is correct and I am presented with the next step in the puzzle.

Part 2

Based on what we’re seeing, it looks like all the User wanted is some information about the evenly divisible values in the spreadsheet. Unfortunately, none of us are equipped for that kind of calculation - most of us specialize in bitwise operations.

Given the following spreadsheet:

5 9 2 8
9 4 7 3
3 8 6 5
  • In the first row, the only two numbers that evenly divide are 8 and 2; the result of this division is 4.
  • In the second row, the two numbers are 9 and 3; the result is 3.
  • In the third row, the result is 2.

In this example, the sum of the results would be 4 + 3 + 2 = 9.

So, how do you go about calculating evendly divisible numbers? Obviously if you would divide 8 with 3 you would get numbers in the decimal. What we are actually asking is “can you fit a number within this number?”. This is also known as the remainder, so the modulo (%) is what we need here. If the numbers are evenly divisible you will be left with exactly 0 remainder.

For each row I can calculate a checksum. I will iterate over the fields in a row, for each field I will check if the modulo of it against the other results in 0, this means they are evenly divisible. The puzzle states there are exactly 2 on each row.

The only thing to keep in mind is that I should not compare against the same value in the second iteration. Returning the values I take care to ensure that they are from high to low. This seems to be an implicit requirement in the sample data.

func solveRow(row []int) (int, int) {
	for i := 0; i < len(row); i++ {
		for j := 0; j < len(row); j++ {
			if i == j {
				continue
			}
			r := row[j] % row[i]
			if r == 0 {
				if row[i] > row[j] {
					return row[i], row[j]
				} else {
					return row[j], row[i]
				}
			}
		}
	}
	return 0, 0
}

In main I reset the sum value and then iterate over each line again, perform the checksum calculation and update the sum to hold the new checksum.

sum = 0
for _, v := range lines {
	c := convert(v)

	first, second := solveRow(c)
	sum += (first / second)
}

fmt.Printf("Puzzle 2 answer: %d\n", sum) 

Emacs and Go

I also found some enhancements to the Go mode in Emacs.

First I found several go utilities that are prerequisites to the packages:

go get -u github.com/nsf/gocode
go get -u github.com/rogpeppe/godef
go get -u golang.org/x/tools/cmd/guru
go get -u golang.org/x/tools/cmd/goimports

Then I setup auto completion. For this I choose to use company-mode and the gocode package has support for this.

(use-package company-go
    :ensure t
    :config
    (setq company-tooltip-limit 20)
    (setq company-idle-delay .3)
    (setq company-echo-delay 0) 
    (setq company-begin-commands '(self-insert-command))
    (add-hook 'go-mode-hook 
              (lambda ()
                (set (make-local-variable 'company-backends) '(company-go))
                (company-mode))))

Finally I found several go packages to install. For go-mode I actually change it to use goimports instead of gofmt as goimports will actually update the imports section of your go file. This is extremely usefull as you don’t need to remove unused packages yourselves.

(use-package go-mode
  :ensure t
  :config
  (setq gofmt-command "goimports")
  (add-hook 'before-save-hook 'gofmt-before-save))

(use-package go-guru
  :ensure t)

(use-package go-errcheck
  :ensure t)

;; Yasnippets
(use-package go-snippets
  :ensure t)

;; eldoc integration
(use-package go-eldoc
  :ensure t)

(use-package gocode
  :ensure t)

(use-package godef
  :ensure t)

(use-package gotest
  :ensure t)

Together the editing experience gets a boost as auto completion works, the code is formatted on save, you can jump around nicely and run tests from within your buffer.

Tags: , ,

Updated: