Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)
Advent of Code 2016 Day 10 (OcaML)
Advent of Code 2016 Day 9 (Factor)
Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)
Advent of Code 2016 – Day 4 (Perl 6)
Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)
Day 14
Start: 12/19/2016
Finish 12/20/2016
Language: Go
SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST. DO NOT LOOK AT MY GITHUB PROJECT. It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer. This blog post is not to give away the answer, but instead, is there for people to learn from.
As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016
The Challenge
This was another problem involving MD5 hash properties. The goal was to find 64 MD5 hashes of an ever incrementing salt which had a triplet of characters in it (like aaa). Furthermore, one of the next 1000 hashes had to have the same character repeated 5 times in a row.
I tackled this one with Go, and after a few mis-starts with regex (no backreferences in Go), I was off to the races
Part 1
For writing in a language that I’ve never touched before, I actually had this come together in a few hours. My main algorithm was to memoize hashes as I saw them, as well as saving off the first triplet and all the quintuplets. I figured the hash was the expensive operation, so I wanted to reduce the time as much as possible.
Here’s all the code
package main
import "crypto/md5"
import "encoding/hex"
import "fmt"
import "regexp"
import "strconv"
type Hash struct {
hash string
triplet string
quintuplets []string
}
var md5s map[int]Hash = make(map[int]Hash)
var salt = "zpqevtbw"
var re3 = regexp.MustCompile(`(aaa|bbb|ccc|ddd|eee|fff|000|111|222|333|444|555|666|777|888|999)`)
var re5 = regexp.MustCompile(`(aaaaa|bbbbb|ccccc|ddddd|eeeee|fffff|00000|11111|22222|33333|44444|55555|66666|77777|88888|99999)`)
func getHash(x int) Hash {
if val, ok := md5s[x]; ok{
return val
}
hasher := md5.New()
hasher.Write([]byte(salt+strconv.Itoa(x)))
hash := hex.EncodeToString(hasher.Sum(nil))
triplet := re3.FindString(hash)
t := ""
if triplet != "" {
t = string(triplet[0])
}
q := make([]string, 0)
quintuplets := re5.FindAllString(hash, -1)
for i := range quintuplets {
q = append(q, string(quintuplets[i][0]))
}
md5s[x] = Hash{hash, t, q}
return md5s[x]
}
func hasQuintuplet(x int, triplet string) bool {
for i:= x+1; i <= x+1000; i++ {
hash := getHash(i)
for j:= range hash.quintuplets {
if triplet == hash.quintuplets[j] {
return true
}
}
}
return false
}
func main() {
counter := 1
for numberOfPads := 0; numberOfPads < 64; {
hash := getHash(counter)
if hasQuintuplet(counter, hash.triplet) {
numberOfPads += 1
}
counter+=1
}
fmt.Println(counter-1)
}
Here’s the memoization that I was doing:
func getHash(x int) Hash {
if val, ok := md5s[x]; ok{
return val
}
hasher := md5.New()
hasher.Write([]byte(salt+strconv.Itoa(x)))
hash := hex.EncodeToString(hasher.Sum(nil))
triplet := re3.FindString(hash)
t := ""
if triplet != "" {
t = string(triplet[0])
}
q := make([]string, 0)
quintuplets := re5.FindAllString(hash, -1)
for i := range quintuplets {
q = append(q, string(quintuplets[i][0]))
}
md5s[x] = Hash{hash, t, q}
return md5s[x]
}
Then in my main loop, I would just try to get each hash from an ever increasing counter, and then check if its triplet was in any of the next 1000 hashes.
func hasQuintuplet(x int, triplet string) bool {
for i:= x+1; i <= x+1000; i++ {
hash := getHash(i)
for j:= range hash.quintuplets {
if triplet == hash.quintuplets[j] {
return true
}
}
}
return false
}
func main() {
counter := 1
for numberOfPads := 0; numberOfPads < 64; {
hash := getHash(counter)
if hasQuintuplet(counter, hash.triplet) {
numberOfPads += 1
}
counter+=1
}
fmt.Println(counter-1)
}
Part 2
Part 2 was using key-stretching, which just meant that we were running the hash function 2017 times. Putting my code in a loop made it simple
func applyHash(input string) string {
hash := ""
for i:=0; i< 2017; i ++ {
hasher := md5.New()
hasher.Write([]byte(input))
hash = hex.EncodeToString(hasher.Sum(nil))
input = hash
}
return hash
}
func getHash(x int) Hash {
if val, ok := md5s[x]; ok{
return val
}
hash := applyHash(salt+strconv.Itoa(x))
triplet := re3.FindString(hash)
t := ""
if triplet != "" {
t = string(triplet[0])
}
q := make([]string, 0)
quintuplets := re5.FindAllString(hash, -1)
for i := range quintuplets {
q = append(q, string(quintuplets[i][0]))
}
md5s[x] = Hash{hash, t, q}
return md5s[x]
}
Wrap-up
This came together quickly (which is much appreciated when I have a 9-5 job and a family to care for), and I learned a bit of Go in the process. I got to play with slicing and maps, which is core to most Go programming. I didn’t get a chance to play with Go Channels, which is where Go shines apparently. In the end, it was easy to find resources (docs were good), but I didn’t think the language was expressive to become one of my favorites. I only briefly touched upon the ecosystem.
I give myself a B+ for this one. I learned enough to solve the problem, wrote some simple code, and got the answer quickly.
Next up, Day 15 looks a little more challenging, and I’ll be tackling it in another completely new language -> Typescript
Pat Viafore 