DEV Community

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

Advent of code - Day 24

qmenoret profile image Quentin Ménoret ・3 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.


Another game of life, but with hexagons this time! The trick here was to make sure you only process the black tiles and their adjacent tiles. Just drop all white tiles, they are useless! Once I figured that out, performance dropped to a ok level (this code runs in about 10 seconds).

Here is my solution for day #24:

interface Position {
  e: number
  se: number
  sw: number
  w: number
  nw: number
  ne: number
}

export function extract(str: string): (keyof Position)[] {
  if (str.length === 0) return []
  if (['e', 'w'].includes(str[0])) return [str[0] as keyof Position, ...extract(str.slice(1))]
  return [str.slice(0, 2) as keyof Position, ...extract(str.slice(2))]
}

function count(position: (keyof Position)[]): Position {
  return position.reduce(
    (acc, value) => {
      acc[value] += 1
      return acc
    },
    {
      e: 0,
      se: 0,
      sw: 0,
      w: 0,
      nw: 0,
      ne: 0,
    },
  )
}

interface Tile {
  position: Position
  state: State
}

enum State {
  Black,
  White,
}

const opposition: Record<keyof Position, keyof Position> = {
  e: 'w',
  w: 'e',
  nw: 'se',
  se: 'nw',
  sw: 'ne',
  ne: 'sw',
}

const complementaries: Record<keyof Position, (keyof Position)[]> = {
  e: ['se', 'ne'],
  w: ['sw', 'nw'],

  se: ['sw', 'e'],
  sw: ['se', 'w'],
  nw: ['ne', 'w'],
  ne: ['nw', 'e'],
}

function rationalize(position: Position): Position {
  for (let key of (Object.keys(opposition) as unknown) as (keyof Position)[]) {
    if (position[key] < 0) {
      return rationalize({
        ...position,
        [key]: 0,
        [opposition[key]]: position[opposition[key]] - position[key],
      })
    }
    if (position[key] > 0 && position[opposition[key]] > 0) {
      return rationalize({
        ...position,
        [key]: position[key] - 1,
        [opposition[key]]: position[opposition[key]] - 1,
      })
    }
  }
  for (let key of (Object.keys(complementaries) as unknown) as (keyof Position)[]) {
    if (complementaries[key].every((comp) => position[comp] > 0)) {
      return rationalize({
        ...position,
        [complementaries[key][0]]: position[complementaries[key][0]] - 1,
        [complementaries[key][1]]: position[complementaries[key][1]] - 1,
        [key]: position[key] + 1,
      })
    }
  }
  return position
}

function print(position: Position): string {
  return `${position.e},${position.se},${position.sw},${position.w},${position.nw},${position.ne}`
}

export function moveTo(newCenter: Position, tile: Position): Position {
  return rationalize(
    ((Object.keys(tile) as unknown) as (keyof Position)[]).reduce(
      (acc: Position, key) => {
        acc[key] = tile[key] - newCenter[key]
        return acc
      },
      {
        e: 0,
        se: 0,
        sw: 0,
        w: 0,
        nw: 0,
        ne: 0,
      },
    ),
  )
}

interface PotentialTile {
  adjacentBlacks: number
  position: Position
}

export function areAdjacent(tile: Tile, adjacent: Tile) {
  const newPosition = moveTo(tile.position, adjacent.position)
  const keys = (Object.keys(newPosition) as unknown) as (keyof Position)[]
  return keys.filter((key) => newPosition[key] === 1).length === 1 && keys.every((key) => newPosition[key] <= 1)
}

export function findAdjacent(tile: Tile): Position[] {
  return ((Object.keys(tile.position) as unknown) as (keyof Position)[]).map((key) => {
    return {
      ...tile.position,
      [key]: tile.position[key] + 1,
    }
  })
}

function runTurn(allTiles: Tile[]) {
  const potentialNewTiles: Record<string, PotentialTile> = {}
  const processed = new Set()

  const indexedTiles = allTiles.reduce((acc: Record<string, Tile>, v) => {
    acc[print(v.position)] = v
    return acc
  }, {})

  const existingTiles = allTiles
    .map((tile) => {
      processed.add(print(tile.position))

      const adjacents = findAdjacent(tile)
      adjacents.forEach((adjacentPosition) => {
        const actualPosition = rationalize(adjacentPosition)
        const printedPosition = print(actualPosition)
        if (processed.has(printedPosition)) return
        potentialNewTiles[printedPosition] = potentialNewTiles[printedPosition] || {
          position: actualPosition,
          adjacentBlacks: 0,
        }
        potentialNewTiles[printedPosition].adjacentBlacks += 1
      })

      const numberOfBlackAdjacents = adjacents
        .map((position) => indexedTiles[print(rationalize(position))])
        .filter(Boolean)
        .filter((adjacent) => adjacent.state === State.Black).length

      return {
        ...tile,
        state: numberOfBlackAdjacents === 1 || numberOfBlackAdjacents === 2 ? State.Black : State.White,
      }
    })
    .filter((tile) => tile.state === State.Black)

  const newTiles = Object.keys(potentialNewTiles)
    .filter((key) => !processed.has(key))
    .filter((key) => potentialNewTiles[key].adjacentBlacks === 2)
    .map((key) => {
      return {
        position: potentialNewTiles[key].position,
        state: State.Black,
      }
    })

  return [...existingTiles, ...newTiles]
}

const positions = input
  .split('\n')
  .map(extract)
  .map(count)
  .map(rationalize)
  .reduce((acc: Record<string, Tile>, value) => {
    acc[print(value)] = acc[print(value)] || { position: value, state: State.White }
    acc[print(value)].state = acc[print(value)].state === State.Black ? State.White : State.Black
    return acc
  }, {})

const tiles = Object.keys(positions)
  .map((key) => positions[key])
  .filter((tile) => tile.state === State.Black)
let currentTiles = tiles

for (let i = 0; i < 101; i++) {
  console.log(`Turn: ${i}: ${currentTiles.filter((t) => t.state === State.Black).length}`)
  currentTiles = runTurn(currentTiles)
}

Enter fullscreen mode Exit fullscreen mode

Feel free to share your solution in the comments!


Photo by Markus Spiske on Unsplash

Discussion (0)

Forem Open with the Forem app