1. import scala.collection.mutable.{Map => MMap}
  2. import scala.collection.mutable.{Set => MSet}
  3. object Wrapper {
  5. type Image = Array[Array[Char]]
  7. val lines = scala.io.Source.fromFile("input").getLines.toArray
  9. // Main source of data, the tile and it Flips.
  10. // Flips includes the rotation and what nots.
  11. val tileFlipsMaps = MMap[Int, Array[Image]]()
  13. // number of tiles 9 in small 144 in large
  14. val nT = lines.filter(_.contains("Tile")).size
  15. // size of board 3x3 small 12x12 big
  16. val nB = Math.sqrt(nT).toInt
  18. // Read image from start line
  19. def readImage(start: Int) = {
  20. val id = lines(start).replaceAll("\\D+","").toInt
  21. val cur: Image = Array.ofDim[Char](10,10)
  22. for(idx <- 0 until 10){
  23. cur(idx) = lines(start+1+idx).toCharArray
  24. }
  25. tileFlipsMaps(id) = expand(cur)
  26. }
  28. // Every image is 10 lines + Tile + blank
  29. (0 until nT).foreach(t => readImage(t*12))
  32. def debug(a: Image) = {println;a.map(_.mkString(" ")).foreach(println)}
  34. // Flips operations§
  35. def hFlip(m: Image) = {
  36. val res = m.map(_.clone)
  37. val M = m.length
  38. for(i<-0 until M){
  39. res(i)= m(M-i-1)
  40. }
  41. res
  42. }
  43. def vFlip(m: Image) = {
  44. val res = m.map(_.clone)
  45. val M = m.length
  46. for(i<-0 until M;j<-0 until M){
  47. res(i)(j)= m(i)(M-j-1)
  48. }
  49. res
  50. }
  51. def r1(m: Image) = {
  52. val res = m.map(_.clone)
  53. val M = m.length
  54. for(r <- 0 until M; c <- 0 until M){
  55. res(r)(c) = m(c)(M-r-1)
  56. }
  57. res
  58. }
  59. def r2(m:Image) = r1(r1(m))
  60. def r3(m:Image) = r1(r2(m))
  62. // Edges operations
  63. def top(m:Image) = m(0)
  64. def bot(m:Image) = m(9)
  65. def left(m:Image) = top(m.transpose)
  66. def right(m:Image) = bot(m.transpose)
  68. // Expand all possible flips and rotates of this image, we call it the Flips
  69. def expand(cur: Image) : Array[Image] = {
  70. Array(cur, r1(cur), r2(cur), r3(cur), vFlip(cur), hFlip(cur), cur.transpose )
  71. }
  73. // Which tile we pick for the board
  74. val tileBoard = Array.ofDim[Int](nB, nB)
  75. // Which incarnation
  76. val flipBoard = Array.ofDim[Int](nB, nB)
  78. var goodArrangement = false
  79. // Main result for part 1
  80. var cornersMultiplied = 0L
  82. // Tiles can't be reused
  83. val usedTiles = MSet[Int]()
  85. // Keep track proper arrangements for second part
  86. var foundTiles = Array.ofDim[Int](nB, nB)
  87. var foundFlips = Array.ofDim[Int](nB, nB)
  88. // Here is the search for the proper tile flips and arrangements.
  89. // Start from top left all the way to bottom right (linear)
  90. // Always look back to top and left, only proceed if match
  91. def rearrangeTiles(rc: Int): Unit = {
  92. if(!goodArrangement)
  93. if(rc == nT){
  94. cornersMultiplied = (tileBoard(0)(0).toLong * tileBoard(0)(nB-1).toLong * tileBoard(nB-1)(0).toLong * tileBoard(nB-1)(nB-1).toLong)
  95. println(s"Part 1: $cornersMultiplied")
  97. // Transpose^2 ==> deep clone, keep for part2
  98. foundTiles = tileBoard.transpose.transpose
  99. foundFlips = flipBoard.transpose.transpose
  100. goodArrangement = true
  101. } else {
  102. // Linear RC to rows and cols
  103. val r = rc / nB
  104. val c = rc % nB
  106. // Right most edge of the left or nothing
  107. val leftCheck = if(c > 0) right(tileFlipsMaps(tileBoard(r)(c-1))(flipBoard(r)(c-1))) else Array()
  108. // Bottom edge of the top or nothing
  109. val topCheck = if(r > 0) bot(tileFlipsMaps(tileBoard(r-1)(c))(flipBoard(r-1)(c))) else Array()
  110. // Make sure not to reuse tiles.
  111. val unusedTiles = tileFlipsMaps -- usedTiles
  113. unusedTiles.foreach { case (tile, flips) =>
  114. usedTiles += tile
  115. for(flip <- 0 until flips.size){
  116. val cur = tileFlipsMaps(tile)(flip)
  117. val curLeft = left(cur)
  118. val curTop = top(cur)
  119. if( (leftCheck.isEmpty || (leftCheck sameElements curLeft)) &&
  120. (topCheck.isEmpty || (topCheck sameElements curTop))) {
  121. tileBoard(r)(c) = tile
  122. flipBoard(r)(c) = flip
  123. rearrangeTiles(rc+1)
  124. }
  125. }
  126. usedTiles -= tile
  127. }
  128. }
  129. }
  131. val RC = nB*8
  132. val monster : Image = scala.io.Source.fromFile("monster").getLines.toArray.map(_.toCharArray)
  134. val mR = monster.size
  135. val mC = monster(0).size
  137. def countMonster(img : Image) = {
  138. var nMonster = 0
  139. for(r <- 0 to RC - mR; c <- 0 to RC-mC){
  140. var found = true
  141. for(rr <- 0 until mR;cc <- 0 until mC){
  142. if(monster(rr)(cc) == '#' && img(r+rr)(c+cc) != '#') found = false
  143. }
  144. if(found) {
  145. // Mark monster
  146. for(rr <- 0 until mR;cc <- 0 until mC){
  147. if(monster(rr)(cc) == '#') img(r+rr)(c+cc) = 'O'
  148. }
  149. nMonster += 1
  150. }
  151. }
  152. nMonster
  153. }
  155. def key(img: Image) = img.map(_.mkString(":")).mkString(".")
  156. val visited = MSet[String]()
  157. def searchMonster(img: Image): Unit = {
  158. val kImg = key(img)
  159. if(!visited.contains(kImg)){
  160. visited += kImg
  161. val nMonster = countMonster(img)
  162. if(nMonster > 0) {
  163. debug(img)
  164. println(s"$nMonster monsters found")
  165. // Monster are marked with O so we count the rest
  166. println(s"Part 2: ${img.flatten.filter(_ == '#').size}")
  168. }
  169. val next = expand(img).filter(i => !visited.contains(key(i)))
  170. next.foreach(searchMonster)
  171. }
  172. }
  174. def removeEdges(): Image = {
  175. val result = Array.ofDim[Char](nB*8, nB*8)
  176. for(t <- 0 until nB; u <- 0 until nB){
  177. val tile = tileFlipsMaps(foundTiles(t)(u))(foundFlips(t)(u))
  178. for(r <- 1 to 8; c<- 1 to 8)
  179. result(t*8 + r-1)(u*8 + c-1) = tile(r)(c)
  180. }
  181. result
  182. }
  184. def solve() = {
  185. rearrangeTiles(0)
  186. searchMonster(removeEdges())
  187. }
  188. }
  190. Wrapper.solve()