Day 20 of Advent of Code is here! Wowza, this was a big one. Part 1 was quick, part 2 took the better part of two days to work through. It was a blast!

See all of my other solutions here. Please do check out what my colleagues at Slalom are doing with their Advent of Code! You can see this and my other solutions on github.

## Day 20: Jurassic Jigsaw

### Part I

I found this challenge fun as I imagined this is what an image recognition app might look like, if provided several photos and it has to splice it all together. Of course, images are WAY more advanced than our input

I have 144 tiles like the above, and the goal is to match them all to make an image, 12×12 tiles. They have to match on their edges, but the tiles could be flipped or rotated.

```const fs = require('fs');
let tiles = []
if(t) {
const lines = t.split('\n').filter(l => l.length > 0)
const tile = lines.slice(1)
const topEdge = tile
const bottomEdge = tile[tile.length - 1]
const leftEdge = tile.reduce((a, b) => `\${a}\${b.substring(0,1)}`,'')
const rightEdge = tile.reduce((a, b) => `\${a}\${b.substring(b.length - 1)}`,'')
tiles.push({ id: Number(lines.trim().replace(':','')), data: tile, edges: [topEdge, bottomEdge, leftEdge, rightEdge, reverseValue(topEdge), reverseValue(bottomEdge), reverseValue(leftEdge), reverseValue(rightEdge)] })
}
});
```

Given I knew what I needed from my data, I decided to process the input data immediately, instead of importing it and then processing it in another variable

• We first split the `input.txt` on the word `Tile`. This will create an array where each item is one tile
• Then we loop through that array using a map()
• We then split the tile by a line return to get all of the lines
• I grab the edges we need: `topEdge`, `bottomEdge`, `leftEdge`, and `rightEdge`.
• Top and bottom are easy, those are the top and bottoms of the array
• Left and right are a little trickier, as they span the edge of the array. I use a reduce() to loop through the `tile` array and grab the first character for the left edge and the last character for the right edge
• Finally, we push these edges, along with the tile id, into the array `tiles`
• You’ll see we’re pushing all tiles into one parameter called `edges`. The puzzle wants me to find the 4 corners of the image and process them, so I don’t need to know where every edge matches (until part 2)
• When inserting into the `edges` I include the 4 edges and the `reverseValue` of those edges, since they could be flipped
```const reverseValue = value => {
return value.split('').reverse().join('')
}
```

Super simple function that takes a string value, split() it on nothing (which creates an array of characters), reverse() them, and then join() them back to make the reversed string.

```tiles = tiles.map(tile => {
const matches = tiles.filter(t => t.id !== tile.id && tile.edges.some(e => t.edges.indexOf(e) > -1))
return { ...tile, matches }
})
```

Next we loop through all tiles, and find who matches its edges. We are filter()ing the tiles, where the tile doesn’t equal the tile we’re on now, and where this tile has some edges that match the filtered tile’s edges. This will get us an array of matching tiles in the array `matches`

```const total = tiles.reduce((a, b) => b.matches.length === 2 ? a * b.id : a, 1)

console.log(total)
```

Finally, we reduce our array, multiplying the tile’s `id`s, when there are only 2 matches (a corner can only have 2 matches). There’s our total!

### Part II

And here comes the fun part. Now we have to actually create the image and look for a pattern in it, looking for a sea monster specifically

I pictured something like this:

Anywhoo, back to “reality”. Part 2 blew up part 1, very little carried over.

```fs.readFileSync('./input.txt', 'utf-8').trim().split('Tile').map(t => {
if(t) {
const lines = t.split('\n').filter(l => l.length > 0)
const tile = lines.slice(1)
tiles.push(new Tile(Number(lines.trim().replace(':','')), tile))
}
});
```

Our data import simplified a lot. I had to move the edge checks out to simplify the code some. See `new Tile`? I created a new class object so we can easily update and reference them

```class Tile {
constructor(id, data) {
this.id = id
this.data = data
this.topEdge = null
this.bottomEdge = null
this.leftEdge = null
this.rightEdge = null
this.edges = []
this.topEdgeTile = null
this.bottomEdgeTile = null
this.leftEdgeTile = null
this.rightEdgeTile = null
this.matches = []
}
}
```

My `Tile` class as an `xxxEdge` which will store the edge value, the string of the edge, and a `xxxEdgeTile` which will be the actual tile on that edge.

```tiles.forEach(tile => {
tile = setEdges(tile)
})

const setEdges = (tile) => {
tile.topEdge = tile.data
tile.bottomEdge = tile.data[tile.data.length - 1]
tile.leftEdge = tile.data.reduce((a, b) => `\${a}\${b.substring(0,1)}`,'')
tile.rightEdge = tile.data.reduce((a, b) => `\${a}\${b.substring(b.length - 1)}`,'')
tile.edges = [tile.topEdge, tile.bottomEdge, tile.leftEdge, tile.rightEdge, reverseValue(tile.topEdge), reverseValue(tile.bottomEdge), reverseValue(tile.leftEdge), reverseValue(tile.rightEdge)]

return tile
}
```

Next we do a quick loop and set the edges, like we did in Part 1. I created a separate method for this as we need to call this anytime we rotate or flip a tile.

```tiles.forEach(tile => {
const edges = ['topEdge', 'rightEdge', 'bottomEdge', 'leftEdge']
edges.forEach(edge => {
const edgeTile = tiles.find(t => t.id !== tile.id && t.edges.indexOf(tile[edge]) > -1)
if(edgeTile){
tile.matches.push(edgeTile)
tile[`\${edge}Tile`] = edgeTile
}
})
})
```

Once all of the `edges` param are set, we then loop through, and start matching tiles to the edge, setting them to the `xxxEdgeTile` parameter. This will allow us to easily find our top left corner of our image

```const topLeftCorner = tiles.find(t => t.matches.length === 2 && t.rightEdgeTile && t.bottomEdgeTile)
```

Again, corners can only have 2 edges match, and to get the top left, I want the corner that has a right edge and a bottom edge.

```let theTile = topLeftCorner
let firstTileInRow = theTile
let ids = ''
// going horizontal first, then vertical
while(true) {
while(true) {
```

Now let’s get looping. Before we do, we set `theTile` to be `topLeftCorner`, `theTile` will be our object we iterate on in the loop. We also store `firstTileInRow` so that when we finish a row, we know the start of the next row. In this loop, we’re focused on doing it row by row, horizontally first.

```    ids += `\${theTile.id} `
let nextTile = tiles.find(t => t.id !== theTile.id && t.edges.indexOf(theTile.rightEdge) > -1)
```

We store the `id` in a string for logging purposes, I’ll show the output below. Then we grab the next tile to the right. Why requery for the tile? We set the edges above. Yes, we did, but once we start flipping and rotating tiles, the rightEdge is no longer the rightEdge that was once set. This ensures we’re always getting the current right edge we need.

```    if(nextTile) {
theTile.rightEdgeTile = nextTile
if(theTile.rightEdge === nextTile.leftEdge) {
// do nothing, they match, onto the next tile
}
if(theTile.rightEdge === reverseValue(nextTile.leftEdge)) {
nextTile = flipTile(nextTile, false)
}
if(theTile.rightEdge !== reverseValue(nextTile.leftEdge) && theTile.rightEdge !== nextTile.leftEdge) {
for(let r = 0; r < 4; r += 1) {
nextTile = rotateTile(nextTile)
if(theTile.rightEdge === reverseValue(nextTile.leftEdge) || theTile.rightEdge === nextTile.leftEdge) {
if(theTile.rightEdge === reverseValue(nextTile.leftEdge)) {
nextTile = flipTile(nextTile, false)
}
break
}
}
}
theTile = nextTile
} else {
theTile.rightEdgeTile = null
break
}
}
```

Assuming the `nextTile` is legit (too legit to quit), we process it.

• If `theTile`‘s `rightEdge` matches the `nextTile`‘s `leftEdge`, then we’re good! Move along.
• If they match, but `leftEdge` is reversed, then we just flip the tile
• If they don’t match at all, that means `theTile`‘s `rightEdge` matches another edge of `nextTile` so we rotate until we match it
• We rotate the `nextTile` and then check if the edges match. If not, rotate again
• If they do match, we then check if they matched because it was reversed. If so, we flip the tile to make them match. We’re flipping the tile vertically, so the bottom is the top, top is bottom and left and right are just reversed strings
• We set `theTile` to the `nextTile` and loop again.
• If the `nextTile` is empty, chances are we’re on an edge, so we `break` out of this inner while()

That wraps up the inner while(), but wait, there’s more!

```  ids += '\n'

let bottomTile = tiles.find(t => t.edges.indexOf(firstTileInRow.bottomEdge) > -1 && ids.indexOf(t.id) === -1)
if(bottomTile) {
if(firstTileInRow.bottomEdge === bottomTile.topEdge) {
// do nothing, they' match, onto the next tile
}
if(firstTileInRow.bottomEdge === reverseValue(bottomTile.topEdge)) {
bottomTile = flipTile(bottomTile, false)
}
if(firstTileInRow.bottomEdge !== reverseValue(bottomTile.topEdge) && firstTileInRow.bottomEdge !== bottomTile.topEdge) {
for(let r = 0; r < 4; r += 1) {
bottomTile = rotateTile(bottomTile)
if(firstTileInRow.bottomEdge === reverseValue(bottomTile.topEdge) || firstTileInRow.bottomEdge === bottomTile.topEdge) {
break
}
}
if(firstTileInRow.bottomEdge === reverseValue(bottomTile.topEdge)) {
bottomTile = flipTile(bottomTile, true)
}
}
firstTileInRow.bottomEdgeTile = bottomTile
firstTileInRow = bottomTile
theTile = firstTileInRow
// rotate/flip needed?
} else {
break
}
}
```

Once the first while() is done, that means we’re done with a row. Now let’s move to the next row

• Real quick, we throw a carriage return at the end of the row string `ids`
• Then we get the `bottomTile` from the `firstTileInRow`. We can’t get the bottom fo the last tile we processed since that’s the last tile in the row. I guess we could get the bottom of the last tile, and then iterate to the left, but that would be unnecessarily complex.
• If the `bottomTile` is legit, we process it, if not, we’re done and `break` out of this outer while()
• We have virtually the same rules here as we did in the above block:
• If the `bottomEdge` and the `topEdge` match, do nothing, move along
• If they match when one is reversed, flip the tile
• If they don’t match rotate and flip until they match (note the flip here is flipping horizontally, so left goes to right, and top and bottom are reversed)
• Then we set the new `firstTileInRow` and its `bottomTile`
• Then we loop again, going back up to the above code block and build out the row

This code processes my 144 tiles, creating a grid of tiles like so (this is what the `ids` is for)

This is not the final image, just the placement of all of the tiles, rotated and flipped properly. NOW let’s create an image.

```theTile = topLeftCorner
let allData = []
firstTileInRow = theTile
let rows = ''
```

We are going to do a similar loop as we did above, looping through rows and columns. I could’ve combined all of this in the above loops, but that would’ve made for a wee bit more complex code with no benefit. I like my code clean and understandable ;)

Above we’re setting `theTile` and `firstTileInRow` to be the `topLeftCorner` again.

```while(true){
// console.log(rows)
if(rows.indexOf(firstTileInRow.id) > -1) {
break
}
rows += `\${firstTileInRow.id} `
```

First we loop through the rows using while(). I am using `rows` just to store the first tile’s `id` to ensure we don’t loop. My data got a little funky along the way and caused a loop. This works well.

```  while(true){
const { data } = theTile
const newData = data.slice(1, data.length - 1).map(d => d.substring(1, d.length - 1))
for(let i = 0; i < newData.length; i += 1){
const rowidx = i + rowPad
allData[rowidx] = !allData[rowidx] ? newData[i] : allData[rowidx] + newData[i]
}

if(theTile.rightEdgeTile) {
theTile = theTile.rightEdgeTile
} else {
break
}
}

if(firstTileInRow.bottomEdgeTile) {
firstTileInRow = firstTileInRow.bottomEdgeTile
theTile = firstTileInRow
} else {
break
}
}
```

Next up we loop the row using a while() again.

• We are getting the `data` from `theTile` and processing it. The requirements are that the outer edge of the tile does not contain anything of value, it was only used for matching, so we can remove the outer edge. I am doing that and setting it to `newData`
• Then we loop through `newData` and appending the row’s string to a new array `allData`
• Since `allData` is an array, but we’re looping columns into it, we need this `rowPad` to know what “row” of data in `allData` to add it to. For instance, the first row goes into 0-7 of `allData`, the second row goes into `8-15` and so on.
• If there’s a `rightEdgeTile` we can continue looping through tiles for this row.
• When we hit the end, we add to the `rowPad` to start the next group of rows in `allData`
• Once we’re done with that row, we move to the next row
• We do the same check for the `bottomEdgeTile`. If we hit the bottom we `break` out of the while()

Now, `allData` is a large array, containing all of the rows of our image, and each row containing all of the text from their associated tiles.

So let’s find some sea monsters!

```for(let i = 0; i < 4; i += 1){
let finalImage = allData.join('\n')
if(findSeaMonster(finalImage)) break

const flippedHor = allData.map(d => reverseValue(d)).join('\n')
if(findSeaMonster(flippedHor)) break

const flippedVer = allData.reverse().join('\n')
if(findSeaMonster(flippedVer)) break

const flippedBoth = allData.map(d => reverseValue(d)).reverse().join('\n')
if(findSeaMonster(flippedBoth)) break

allData = rotateArray(allData)
}
```

We don’t know if the orientation of the image is right, so we have to check the image, flip it horizontally and vertically, and rotate it, until we find our sea monsters.

```const findSeaMonster = (image) => {
/* There be monsters:
>                  # <
>#    ##    ##    ###<
>#  #  #  #  #  #    <
*/
const seaMonsterCount = 15 // number of # in the sea dragon
const seaMonster = new RegExp('..................#(.)+\n(.)*#....##....##....###(.)+\n(.)*.#..#..#..#..#..#...', 'g');
const finds = new Set()
let attempt = seaMonster.exec(image)
while(attempt) {
seaMonster.lastIndex = attempt.index + 75
attempt = seaMonster.exec(image)
}

if(finds.size > 0) {
console.log(finds.size, 'sea monsters found!')
console.log(image.match(/#/g).length - (seaMonsterCount * finds.size), 'roughness')
return true
}
return false
}
```

The `findSeaMonster` method finds the monsters, and if they exist, then writes the answer out.

• The initial comments is what the monster looks like. There can be anything in the white spaces, but the `#` have to be in those locations
• I decided to use a regex to create the multilined dragon
• `.` is any character
• `#` is just that, a #
• `+` says at least 1 of the previous
• `*` says zero or more of the previous
• `\n` is a line return
• The trick here is we can’t just do a normal match() with the regular expression, since our monsters may be overlapping on the same lines. Instead, we’re going to use exec().
• A normal match will ignore if another sea monster is within the characters used to find a sea monster. So if a sea monster is to the right of one, on the same rows, a match() won’t find it.
• exec() allows us to find one at a time, and then reset the index after the one we found, to find the next one, even on the same row.
• Finally, this writes out our answer!

And for some eye candy, here’s what all of my tiles and sea monsters look like: