DEV Community

loading...
Cover image for Advent of code - Day 20

Advent of code - Day 20

qmenoret profile image Quentin Ménoret ・5 min read

Are you participating in the Advent of code this year?

If you don't know what the advent of code is, it's a website where you'll find a daily challenge (every day it gets harder). It's a really fun event, you should participate!

I try to solve the exercises using either JavaScript or TypeScript and will share my solutions daily (with one day delay so no one can cheat!). I only share the solution for the second part.


WHY??? WHYYYYY???? Seriously, this was one of the most painful coding experience I had this year. The problem on itself is not that complex. But wow, there is not proper way to debug this except printing the whole map and trying to understand where you messed up.

My solution is extremely long and painful (just like my experience), but I really don't want to go back to this code and improve it to be honest. I'm just happy that this is over, and that it was the last Sunday of this Advent of Code (seems like the Sundays are the hard ones).

Here is my solution for day #20:

export enum Side {
  Top = 'Top',
  Bottom = 'Bottom',
  Left = 'Left',
  Right = 'Right',
  ReversedTop = 'ReversedTop',
  ReversedBottom = 'ReversedBottom',
  ReversedLeft = 'ReversedLeft',
  ReversedRight = 'ReversedRight',
}

export const originSides = [Side.Top, Side.Bottom, Side.Left, Side.Right]
export const allSides = [
  Side.Top,
  Side.Bottom,
  Side.Left,
  Side.Right,
  Side.ReversedTop,
  Side.ReversedBottom,
  Side.ReversedLeft,
  Side.ReversedRight,
]

export class Tile {
  id: string
  content: string
  Top: string
  Bottom: string
  Left: string
  Right: string
  ReversedTop: string
  ReversedBottom: string
  ReversedLeft: string
  ReversedRight: string

  constructor(id: string, content: string) {
    this.id = id
    this.content = content
    const lines = this.content.split('\n')
    const [Left, Right] = lines.reduce(
      ([left, right], line) => {
        return [left + line[0], right + line[line.length - 1]]
      },
      ['', ''],
    )

    this.Top = lines[0]
    this.Bottom = lines[lines.length - 1]
    this.Left = Left
    this.Right = Right
    this.ReversedTop = lines[0].split('').reverse().join('')
    this.ReversedBottom = lines[lines.length - 1].split('').reverse().join('')
    this.ReversedLeft = Left.split('').reverse().join('')
    this.ReversedRight = Right.split('').reverse().join('')
  }

  get possibilities() {
    return allSides.map((side) => this[side])
  }

  reverseTopBottom() {
    const newContent = this.content.split('\n').reverse().join('\n')
    return new Tile(this.id, newContent)
  }

  reverseLeftRight() {
    const newContent = this.content
      .split('\n')
      .map((line) => line.split('').reverse().join(''))
      .join('\n')
    return new Tile(this.id, newContent)
  }

  rotateClock() {
    const splitContent = this.content.split('\n').map((line) => line.split(''))

    const newContent: string[][] = []

    for (let i = 0; i < splitContent.length; i++) {
      for (let j = 0; j < splitContent[i].length; j++) {
        newContent[j] = newContent[j] || []
        newContent[j][i] = splitContent[splitContent.length - i - 1][j]
      }
    }

    return new Tile(this.id, newContent.map((line) => line.join('')).join('\n'))
  }

  rotateUnclock() {
    const splitContent = this.content.split('\n').map((line) => line.split(''))

    const newContent: string[][] = []

    for (let i = 0; i < splitContent.length; i++) {
      for (let j = 0; j < splitContent[i].length; j++) {
        newContent[j] = newContent[j] || []
        newContent[j][i] = splitContent[i][splitContent[i].length - j - 1]
      }
    }

    return new Tile(this.id, newContent.map((line) => line.join('')).join('\n'))
  }

  placeAtBottom(side: Side) {
    if (side === Side.Bottom) return this.reverseTopBottom()
    if (side === Side.Top) return this
    if (side === Side.Right) return this.rotateUnclock()
    if (side === Side.Left) return this.rotateClock().reverseLeftRight()
    if (side === Side.ReversedBottom) return this.reverseTopBottom().reverseLeftRight()
    if (side === Side.ReversedTop) return this.reverseLeftRight()
    if (side === Side.ReversedLeft) return this.rotateClock()
    // if (side === Side.ReversedRight)
    return this.reverseTopBottom().rotateUnclock()
  }

  placeAtRight(side: Side) {
    if (side === Side.Bottom) return this.rotateClock()
    if (side === Side.Top) return this.rotateUnclock().reverseTopBottom()
    if (side === Side.Right) return this.reverseLeftRight()
    if (side === Side.Left) return this
    if (side === Side.ReversedBottom) return this.rotateClock().reverseTopBottom()
    if (side === Side.ReversedTop) return this.rotateUnclock()
    if (side === Side.ReversedLeft) return this.reverseTopBottom()
    // if (side === Side.ReversedRight)
    return this.reverseLeftRight().reverseTopBottom()
  }
}

export function getTilesFromInput(input: string) {
  return input.split('\n\n').map((tile) => {
    const [idPart, content] = tile.split(':\n')
    const [_, id] = idPart.split(' ')
    return new Tile(id, content)
  })
}

export function generateMap(tiles: Tile[]) {
  function findMatches(currentTile: Tile) {
    return tiles
      .filter((tile) => tile.id !== currentTile.id)
      .filter((tile) => currentTile.possibilities.some((p) => tile.possibilities.includes(p)))
      .map((tile) => {
        const attachPart = allSides.find((tileSide) =>
          originSides.some((originSide) => currentTile[originSide] === tile[tileSide]),
        )
        if (!attachPart) throw new Error('could not find an attach part')
        const attachSide = allSides.find((currentTileSide) => tile[attachPart] === currentTile[currentTileSide])
        if (!attachSide) throw new Error('could not find an attach side')

        return {
          tile,
          attachPart,
          attachSide,
        }
      })
  }

  const firstCorner = tiles.find((tile) => findMatches(tile).length === 2)
  if (!firstCorner) throw new Error('no corner found')
  const twoFirstPieces = findMatches(firstCorner)
  const sides = twoFirstPieces.map((p) => p.attachSide)

  function getOriginalCorner(sides: Side[], tile: Tile): Tile {
    if (!sides.length) return tile
    if (sides[0] === Side.Left) {
      return getOriginalCorner(sides.slice(1), tile.reverseLeftRight())
    }
    if (sides[0] === Side.Top) {
      return getOriginalCorner(sides.slice(1), tile.reverseTopBottom())
    }
    return getOriginalCorner(sides.slice(1), tile)
  }

  const originalCorner = getOriginalCorner(sides, firstCorner)

  const map: Tile[][] = [[originalCorner]]

  const usedTiles: string[] = []
  for (let i = 0; i < map.length; i++) {
    for (let j = 0; j < map[i].length; j++) {
      const current = map[i][j]
      if (!current) break
      usedTiles.push(current.id)
      const matches = findMatches(current).filter((match) => !usedTiles.includes(match.tile.id))
      const bottom = matches.find((m) => m.attachSide === Side.Bottom)
      if (bottom) {
        map[i + 1] = map[i + 1] || []
        map[i + 1][j] = bottom.tile.placeAtBottom(bottom.attachPart)
      }
      const right = matches.find((m) => m.attachSide === Side.Right)
      if (right) {
        map[i][j + 1] = right.tile.placeAtRight(right.attachPart)
        usedTiles.push(right.tile.id)
      }
    }
  }
  return map
}

export function getFullPicture(map: Tile[][]) {
  const picture: string[][] = []
  for (let i = 0; i < map.length; i++) {
    for (let j = 0; j < map[i].length; j++) {
      const current = map[i][j]
      const lines = current.content
        .split('\n')
        .map((l) => l.split('').slice(1, -1).join(''))
        .slice(1, -1)
      if (!picture[i]) {
        picture[i] = lines
      } else {
        picture[i] = picture[i].map((line, index) => line + lines[index])
      }
    }
  }
  return picture
}

Enter fullscreen mode Exit fullscreen mode

And then to calculate the number of elements:

import { input } from './input'
import { Tile, generateMap, getTilesFromInput, getFullPicture } from './Tile'

let tiles = getTilesFromInput(input)

const map = generateMap(tiles)

const picture: string[][] = getFullPicture(map)

const pictureByLines = picture.reduce((acc, lines) => [...acc, ...lines], [])

const regex1 = /..................#./g
const regex2 = /#....##....##....###/
const regex3 = /.#..#..#..#..#..#.../
function findSeeMonsters(content: string) {
  const lines = content.split('\n')
  const monsterCount = lines.reduce((acc, line, index) => {
    if (index > lines.length - 3) return acc
    let where: RegExpMatchArray | null = null

    while ((where = line.match(regex1))) {
      const potentialMonsterIndex = line.indexOf(where[0])
      const newIndex = lines[index + 1].length - line.length + potentialMonsterIndex
      const line2 = lines[index + 1].slice(newIndex, newIndex + 20)
      const line3 = lines[index + 2].slice(newIndex, newIndex + 20)
      if (line2.match(regex2) && line3.match(regex3)) {
        console.log({ index })
        acc++
      }
      line = line.slice(potentialMonsterIndex + 1)
    }

    return acc
  }, 0)
  const totalElement = content.split('').reduce((acc, c) => (c === '#' ? acc + 1 : acc), 0)
  console.log(totalElement - monsterCount * 15)
}

const fullTile = new Tile('regular', pictureByLines.join('\n'))

// I brute forced it, the first one
// with a number !== 0 is the one!
findSeeMonsters(fullTile.rotateClock().content)
findSeeMonsters(fullTile.rotateClock().rotateClock().content)
findSeeMonsters(fullTile.rotateClock().rotateClock().rotateClock().content)
findSeeMonsters(fullTile.reverseTopBottom().rotateClock().rotateClock().content)
findSeeMonsters(fullTile.reverseTopBottom().rotateClock().rotateClock().rotateClock().content)
findSeeMonsters(fullTile.reverseLeftRight().rotateClock().content)
findSeeMonsters(fullTile.reverseLeftRight().rotateClock().rotateClock().content)
findSeeMonsters(fullTile.reverseLeftRight().rotateClock().rotateClock().rotateClock().content)
Enter fullscreen mode Exit fullscreen mode

Feel free to share your solution in the comments!


Photo by Markus Spiske on Unsplash

Discussion (0)

pic
Editor guide