-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsolve.scala
130 lines (107 loc) · 4.11 KB
/
solve.scala
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
import scala.io.StdIn
import scala.collection.mutable.{Map => MMap, Set => MSet}
import scala.util.matching.Regex
object Types {
type Matrix[T] = Array[Array[T]]
}
object D4 extends Enumeration {
import Types._
def apply(m: Matrix[Char]): Seq[Matrix[Char]] = List(
m, // R0
m.reverse, // SH
m.map(_.reverse), // SV
m.transpose, // D1
m.reverse.map(_.reverse).transpose, // D2
m.transpose.reverse, // R1
m.reverse.map(_.reverse), // R2
m.reverse.transpose // R3
)
}
class Tile(val id: Int, val body: Types.Matrix[Char]) {
lazy val top = body.head.mkString
lazy val left = body.map(_.head).mkString
lazy val right = body.map(_.last).mkString
lazy val bottom = body.last.mkString
lazy val configs = D4(body).map(new Tile(id, _))
}
class Area(val tiles: Seq[Tile]) {
import Types._
val tileConfigs = tiles.flatMap(_.configs)
val tileConfigsById = tileConfigs.groupBy(_.id)
val mapSize = Math.sqrt(tiles.length).toInt
val tileSize = tileConfigs.head.body.length
val sideCount = tileConfigs
.groupBy(_.top).view.mapValues(_.map(_.id).toSet.size).toMap
def isUnique(side: String) = sideCount(side) == 1
def findCorners() = tileConfigs.filter(t => isUnique(t.top) && isUnique(t.left)).map(_.id).toSet
def fillMap(): Matrix[Char] = {
val map: MMap[(Int, Int), Tile] = MMap()
val pendingSet = MSet.from(tileConfigsById.keys)
val update = (i: Int, j: Int, t: Tile) => {
pendingSet.remove(t.id)
map.update((i, j), t)
}
// find a tile matching the criterias
val find: (Tile => Boolean) => Tile = (f) =>
pendingSet.flatMap(tileConfigsById).filter(f).head
for (i <- 1 to mapSize; j <- 1 to mapSize) {
val tile = (i, j) match {
// corners
case (1, 1) => find(t => { isUnique(t.top) && isUnique(t.left) })
case (1, `mapSize`) => find(t => isUnique(t.top) && isUnique(t.right) && t.left == map(i, j - 1).right)
case (`mapSize`, 1) => find(t => isUnique(t.left) && isUnique(t.bottom) && t.top == map(i - 1, j).bottom)
case (`mapSize`, `mapSize`) => find(_ => true)
// sides
case (1, _) => find(t => isUnique(t.top) && t.left == map(1, j - 1).right)
case (_, 1) => find(t => isUnique(t.left) && t.top == map(i - 1, 1).bottom)
case (`mapSize`, _) => find(t => isUnique(t.bottom) && t.left == map(i, j - 1).right)
case (_, `mapSize`) => find(t => isUnique(t.right) && t.top == map(i - 1, j).bottom)
// others
case _ => find(t => t.top == map(i - 1, j).bottom && t.left == map(i, j - 1).right)
}
update(i, j, tile)
}
val getRowMatrix: (Int) => Matrix[Char] = (row) =>
(1 to tileSize-2)
.map(i => (1 to mapSize).flatMap(col => map(row, col).body(i).slice(1, tileSize-1)).toArray)
.toArray
(1 to mapSize).flatMap(getRowMatrix(_)).toArray
}
def findOverlapping(text: String, pattern: Regex): Int = {
pattern.findFirstMatchIn(text) match {
case Some(m) => 1 + findOverlapping(text.substring(m.start+1), pattern)
case None => 0
}
}
def findMonsters(sea: Matrix[Char]): Option[Int] = {
val pattern = new Regex(s".{18}#.{${sea.length-19}}#....##....##....###.{${sea.length-19}}#..#..#..#..#..#...")
val text = sea.map(_.mkString).mkString
val found = findOverlapping(text, pattern)
if (found>0) Some(sea.map(_.count(_ == '#')).sum - found * 15) else None
}
}
object Main {
import Types._
def readTileBody(): Matrix[Char] =
Iterator.continually(StdIn.readLine())
.takeWhile(s => s != null && s.length() > 0).map(_.toArray).toArray
def readTile(): Option[Tile] = {
val reg = """Tile (\d+):""".r
StdIn.readLine() match {
case reg(id) => Some(new Tile(id.toInt, readTileBody()))
case c => None
}
}
def readInput(): Seq[Tile] = {
readTile() match {
case Some(t) => t +: readInput()
case None => Nil
}
}
def main(args: Array[String]): Unit = {
val area = new Area(readInput())
println(area.findCorners().map(_.toLong).reduce(_ * _))
val sea = area.fillMap()
println(D4(sea).map(area.findMonsters).flatten.head)
}
}