Advent of Code 2019, Day 4

Okay, new PR: 20:04 total time.

The challenge was again relatively straightforward: given some constraints on numbers, how we verify them?

For part 1, the goal is to generate 6-digit passwords given some minimum and maximum range given a couple of constraints. The first is that it has to be a six digit number within the range of values; by only generating candidates in this range this constraint is automatically satisfied. The second is that at least two adjacent numbers are equal (e.g. 122345), and the third is that the digits are monotically increasing.

Easy enough to model:

func twoAdjacent(n int) bool {
        s := fmt.Sprintf("%0d", n)
        for i := 1; i < 6; i++ {
                if s[i-1] == s[i] {
                        return true
                }
        }

        return false
}

func isMonotic(n int) bool {
        s := fmt.Sprintf("%d", n)
        for i := 1; i < 6; i++ {
                if s[i] < s[i-1] {
                        return false
                }
        }

        return true
}

func findCandidate1(min, max int) int {
        count := 0
        for i := min; i <= max; i++ {
                if twoAdjacent(i) && isMonotic(i) {
                        count++
                }
        }

        return count
}

func findCandidate2(min, max int) int {
        count := 0
        for i := min; i <= max; i++ {
                if onlyTwoAdjacent(i) && isMonotic(i) {
                        count++
                }
        }

        return count
}

Notably, I don't bother parsing ints in the isMonotic phase: the way ASCII works, the ASCII values will be the number + 0x30, so just comparing them directly works.

In the second part, the added constraint is that there's at least a character with a run length of 2. That is, 111122 and 112233 are valid, but 123444 is not.

func onlyTwoAdjacent(n int) bool {
        s := fmt.Sprintf("%0d", n)
        run := s[0]
        count := 1
        ok := false

        for i := 1; i < 6; i++ {
                if s[i] == run {
                        count++
                } else {
                        if count == 2 {
                                ok = true
                        }
                        run = s[i]
                        count = 1
                }
        }

        if count == 2 {
                ok = true
        }
        return ok
}

I'd been on the fence about the value of having unit tests for these, but in this case it caught the fact that at first I'd forgotten to include the test after the loop, so trailing runs wouldn't be picked up.

111 lines of code (74 source, 37 test); perf run with answers omitted:

2019/12/03 21:25:44 day04p1: complete in 104436us, total allocated 10424 kB,
current heap allocation 2693 kB
2019/12/03 21:25:44 day04p2: complete in 68517us, total allocated 20519 kB,
current heap allocation 987 kB

Further experiments

I tried two alternate approaches afterwards:

  • Having the candidacy checking functions operate directly on strings and computing the string in the number generator dropped allocations by 20-30% and decreased run time by about 17ms, or about ~20%.
  • I tried operating directly on a byte counter and that was incredibly slow; after 2m I killed it. It might have generated fewer allocations but the runtime hit was unacceptable.

Tags: ,