-
Notifications
You must be signed in to change notification settings - Fork 1
/
Day18.kt
98 lines (79 loc) · 2.89 KB
/
Day18.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*
* Copyright (c) 2018 by Todd Ginsberg
*/
/**
* Advent of Code 2018, Day 18 - Settlers of The North Pole
*
* Problem Description: http://adventofcode.com/2018/day/18
* Blog Post/Commentary: https://todd.ginsberg.com/post/advent-of-code/2018/day18/
*/
package com.ginsberg.advent2018
import java.util.Arrays
typealias Forest = Array<CharArray>
class Day18(rawInput: List<String>) {
private val forest: Forest = rawInput.map { it.toCharArray() }.toTypedArray()
fun solvePart1(): Int =
growTrees().drop(9).first().value()
fun solvePart2(find: Int = 1_000_000_000): Int {
val seen = mutableMapOf<Int, Int>()
var generation = 0
val firstRepeating = growTrees().dropWhile { tree ->
val treeHash = tree.hash()
generation++
if (treeHash in seen) {
false
} else {
seen[treeHash] = generation
true
}
}.first()
val cycleLength = generation - seen[firstRepeating.hash()]!!
val remainingSteps = (find - generation) % cycleLength
// Fast forward to the target
return growTrees(firstRepeating).drop(remainingSteps - 1).first().value()
}
private fun growTrees(initial: Forest = forest): Sequence<Forest> = sequence {
var current = initial
while (true) {
current = current.nextGeneration()
yield(current)
}
}
private fun Forest.nextGeneration(): Array<CharArray> =
this.mapIndexed { y, row ->
row.mapIndexed { x, _ -> this.nextGenerationSpot(Point(x, y)) }.toCharArray()
}.toTypedArray()
private fun Forest.nextGenerationSpot(at: Point): Char {
val neighborMap = this.countNeighbors(at)
return when (val space = this[at]) {
OPEN -> if (neighborMap.getOrDefault(TREE, 0) >= 3) TREE else OPEN
TREE -> if (neighborMap.getOrDefault(LUMBERYARD, 0) >= 3) LUMBERYARD else TREE
LUMBERYARD -> if (neighborMap.getOrDefault(LUMBERYARD, 0) >= 1 &&
neighborMap.getOrDefault(TREE, 0) >= 1) LUMBERYARD else OPEN
else -> space
}
}
private fun Forest.countNeighbors(at: Point): Map<Char, Int> =
at.neighbors(false)
.filterNot { it.x >= this[0].size }
.filterNot { it.y >= this.size }
.map { this[it] }
.groupingBy { it }
.eachCount()
private fun Forest.value(): Int =
this.flatMap { row ->
row.map { it }
}
.groupingBy { it }
.eachCount()
.run {
getOrDefault(TREE, 0) * getOrDefault(LUMBERYARD, 0)
}
private fun Forest.hash(): Int =
Arrays.deepHashCode(this)
companion object {
private const val OPEN = '.'
private const val LUMBERYARD = '#'
private const val TREE = '|'
}
}