day14.go

package main

import (
    "crypto/md5"
    "fmt"
    "strconv"
    "time"
)

const salt = "zpqevtbw"

type buffer struct {
    cache  []node
    base   []byte
    rounds int
}

func (b *buffer) get(n int) *node {
    i := n % len(b.cache)
    if b.cache[i].index != n {
        b.hash(i, n)
        b.cache[i].index = n
    }
    return &b.cache[i]
}

func newBuffer(size int, base []byte, extra int) *buffer {
    b := &buffer{
        cache:  make([]node, size),
        base:   append([]byte(nil), base...),
        rounds: extra,
    }
    // get(0) would return an empty hash, since the index would match
    // so initialize it manually
    b.hash(0, 0)

    return b
}

type node struct {
    index int
    hash  [2 * md5.Size]byte
    wide  uint16
}

func (b *buffer) hash(idx, n int) {
    buf := b.cache[idx].hash[:]

    copy(buf, b.base)

    sum := md5.Sum((strconv.AppendInt(buf[:len(b.base)], int64(n), 10)))
    encode(buf, sum[:])
    for i := 0; i < b.rounds; i++ {
        sum = md5.Sum(buf)
        encode(buf, sum[:])
    }

    // scan through the entire hash string now, and setup a bitmap that can
    // just be indexed each time
    // NOTE: this turns out to not be that significant
    b.cache[idx].wide = 0
    for i := 0; i+4 < len(buf); i++ {
        if buf[i] == buf[i+1] && buf[i] == buf[i+2] && buf[i] == buf[i+3] && buf[i] == buf[i+4] {
            b.cache[idx].wide |= 1 << hexLookup[buf[i]]
        }
    }
}

// shaves tiny amounts of time off of 'hex.Encode' by pre-calculating the bit manipulations
func encode(dst, src []byte) {
    for i, b := range src {
        dst[2*i] = hexBytes[b][0]
        dst[2*i+1] = hexBytes[b][1]
    }
}

var hexBytes [256][2]byte

func init() {
    chars := []byte("0123456789abcdef")
    for i := 0; i < 256; i++ {
        hexBytes[i] = [2]byte{chars[i>>4], chars[i&0xf]}
    }
}

// trip looks for a triple-character, and returns the integer value of the hex character
func trip(s []byte) int {
    for i := 0; i+2 < len(s); i++ {
        if s[i] == s[i+1] && s[i] == s[i+2] {
            return int(hexLookup[s[i]])
        }
    }

    return -1
}

// tried [256]int instead of the map, didn't seem to change much
var hexLookup = make(map[byte]uint, 16)

func init() {
    for c := '0'; c <= '9'; c++ {
        hexLookup[byte(c)] = uint(c - '0')
    }
    for c := 'a'; c <= 'f'; c++ {
        hexLookup[byte(c)] = uint(c - 'a' + 10)
    }
}

func main() {
    parts := []int{0, 2016}
    answers := make([]int, len(parts))
    times := make([]time.Duration, len(parts))
    bufSize := 1000

    for p, x := range parts {
        begin := time.Now()
        buf := newBuffer(bufSize, []byte(salt), x)
        count := 0

        var recentList [16]int
        var startList [16]int

        i := 0
        for ; count < 64; i++ {
            if five := trip(buf.get(i).hash[:]); five >= 0 {
                if n := recentList[five]; n > i {
                    // we've encountered a 5-wide segment of this same character
                    // within our buffer (also our scan limit) count it and move on
                    count++
                    //fmt.Printf("recent %2d %6d %6d\n", count, i, n)
                    continue
                }
                n := 1
                if l := startList[five]; l > i {
                    // we've searched for a 5-wide segment of this same character
                    // up-to, but not including 'l', so start search from there
                    n = l - i
                }
                for ; n <= bufSize; n++ {
                    if buf.get(i+n).wide&(1<<uint(five)) != 0 {
                        // record this 5-wide segment for future lookups
                        recentList[five] = i + n
                        count++
                        //fmt.Printf("scan   %2d %6d %6d\n", count, i, i+n)
                        break
                    }
                }
                // no match, we've searched up to (i + n - 1), so we'll start
                // at (i + n) next time when looking for this character
                startList[five] = i + n
            }
        }

        answers[p] = i - 1
        times[p] = time.Since(begin)
    }

    for i, n := range answers {
        fmt.Printf("Part %d: %d (%v)\n", i+1, n, times[i])
    }
}