Day 22: Monkey Market
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Go
Re-familiarizing myself with Go. The solution to Part 2 is fairly simply, the whole packing of the sequence into a single integer to save on memory was an optimization I did afterwards based on looking at other solutions. I thought it was cool.
package main import ( "bufio" "fmt" "os" "strconv" ) type SequenceMap struct { Data map[int32]int } func PackSeq(numbers [4]int8) int32 { var packed int32 for i, num := range numbers { packed |= int32(num+9) << (i * 5) } return packed } func UnpackSeq(packed int32) [4]int8 { var numbers [4]int8 for i := range numbers { numbers[i] = int8((packed>>(i*5))&0x1F) - 9 } return numbers } func NewSequenceMap() SequenceMap { return SequenceMap{make(map[int32]int)} } func (m *SequenceMap) Increment(seq [4]int8, val int) { pSeq := PackSeq(seq) acc, ok := m.Data[pSeq] if ok { m.Data[pSeq] = acc + val } else { m.Data[pSeq] = val } } func (m *SequenceMap) Has(seq [4]int8) bool { pSeq := PackSeq(seq) _, ok := m.Data[pSeq] return ok } type Generator struct { Secret int64 LastPrice int8 ChangeSequence []int8 } func NewGenerator(Secret int64) Generator { var ChangeSequence []int8 return Generator{Secret, int8(Secret % 10), ChangeSequence} } func (g *Generator) Mix(value int64) *Generator { g.Secret = g.Secret ^ value return g } func (g *Generator) Prune() *Generator { g.Secret = g.Secret % 16777216 return g } func (g *Generator) Next() { g.Mix(g.Secret * 64).Prune().Mix(g.Secret / 32).Prune().Mix(g.Secret * 2048).Prune() Price := int8(g.Secret % 10) g.ChangeSequence = append(g.ChangeSequence, Price-g.LastPrice) g.LastPrice = Price if len(g.ChangeSequence) > 4 { g.ChangeSequence = g.ChangeSequence[1:] } } func ParseInput() []int64 { if fileInfo, _ := os.Stdin.Stat(); (fileInfo.Mode() & os.ModeCharDevice) != 0 { fmt.Println("This program expects input from stdin.") os.Exit(1) } scanner := bufio.NewScanner(os.Stdin) var numbers []int64 for scanner.Scan() { line := scanner.Text() num, err := strconv.ParseInt(line, 10, 64) if err != nil { fmt.Printf("ERROR PARSING VALUE: %s\n", line) os.Exit(1) } numbers = append(numbers, num) } return numbers } func main() { numbers := ParseInput() m := NewSequenceMap() sum := int64(0) for i := 0; i < len(numbers); i += 1 { g := NewGenerator(numbers[i]) tM := NewSequenceMap() for j := 0; j < 2000; j += 1 { g.Next() if len(g.ChangeSequence) == 4 { if !tM.Has([4]int8(g.ChangeSequence)) { tM.Increment([4]int8(g.ChangeSequence), 1) if g.LastPrice > 0 { m.Increment([4]int8(g.ChangeSequence), int(g.LastPrice)) } } } } sum += g.Secret } fmt.Printf("Part One: %d\n", sum) var bestSeq [4]int8 bestPrice := 0 for pSeq, price := range m.Data { if price > bestPrice { bestPrice = price bestSeq = UnpackSeq(pSeq) } } fmt.Printf("Part Two: %d\n", bestPrice) fmt.Printf("Best Sequence: %d\n", bestSeq) }