Le blog d'Archiloque

Advent of code 2020 in Nim

For a third year I did some advent of code.

The advent of code is a set of not too long (hopefully) coding exercises covering various subjects.

They tend to lean heavy on data manipulation algorithms (processing lists of lists, tree traversals…) so they are good to learn or practice standard libraries.

As implied by its name, it’s supposed to be done during the advent: a two-parts problem is published each day so there’s a pace to follow, and you can even compete on solving them as fast as possible. This helps some people to keep their motivation all along the 25 days, and people create team for help or to discuss their code.

I hate the soft peer pressure and the idea of self-imposed mandatory homework to do everyday, so as each year I wait at least a few weeks so I can choose my pace to work on them.

This year’s advent of code

Compared to last year, the problems were much more aligned with my tastes:

  • The samples provided were much more comprehensive, so I didn’t have to look at solutions to be able to figure what was wrong in my code.

  • Less problems that required to implement math-heavy solutions, the only one this year was the day 13

As a consequence I’ve solved all the problems \o/.

Nim

This year I’ve decided to use the advent of code to learn Nim.

Ruby is still my language of choice, but I needed another tool for specific personal projects I want to try. Since a few years I was looking for a programming language with these requirements:

  • Statically-typed at build-time

  • Garbage-collected

  • Easy to integrate with C so I can use binding with things like Dear ImGui to write graphical standalone applications

  • Mature enough to not require too much work to keep my code up to date

  • No hype

  • No strong link to a large corporation with terrible practices

  • A welcoming community free of obnoxious people

And so far Nim seem to meet all the requirements, I should have looked at it earlier.

It’s is an interesting tool, to me it looks like Python vored C a mix of Python and C, where you can have Python expressivity with C-level performance. It means that you have to have a high-level understanding of how the memory models works, which is a kind of thing I never had to deal with with any of languages I used.

I enjoy the mix of minimal OOP and functional style, even if I know that other people hate this kind of multi-paradigm approach.

The advent of code problems didn’t required me to learn about the macros system but as it looks cool I hope I’ll be able to use them in a real project.

If you want to have a look at Nim, the Nim in action was a great resource. I specially liked that the text explain not only what is possible to do but also what is idiomatic in Nim. When you learn a programming language on your own, there’s a risk to inadvertently create your own personal style that doesn’t look like mainstream code and learning what is idiomatic helps to mitigate this.

My main gripe so far is the very limited support in IntelliJ, having to use Visual Studio Code is not a deal breaker but it’s not my preferred editor. (As I work with very nice Python people, I won’t mention my opinion on significant indentation, but 🙄.)

Disclaimers:

  1. The bellow code is the first code I’ve written in Nim after reading the book, so it’s probably not a example of good Nim code.

  2. If you have a look at Nim because of me and you want to use it for your personal or professional projects (I want only to use it for personal ones, at least so far) and it goes badly, in no event shall I be liable for any claim, damages or other liability because of it.

The code

Day 1

Part one

day011.nim
import strutils
import sequtils
import os

let input: seq[int] = readFile(paramStr(1)).splitLines().map(parseInt)

for i, first in input:
  for second in input[i + 1 .. ^1]:
    if first + second == 2020:
      echo(first, " ", second, " ", (first * second))
      quit()

Part two

day012.nim
import strutils
import sequtils
import os

let input: seq[int] = readFile(paramStr(1)).splitLines().map(parseInt)

for i, first in input:
  for j, second in input[i + 1 .. ^1]:
    for third in input[j + 1 .. ^1]:
      if first + second + third == 2020:
        echo(first, " ", second, " ", third, " ", (first * second * third))
        quit()

Day 2

Part one

day021.nim
import strutils
import sequtils
import os
import re

let passwordRegex = re(r"^(\d+)-(\d+) ([a-z]{1}): ([a-z]+)$")

proc validPassword(line: string): bool =
  var matches: array[4, string]
  if line.match(passwordRegex, matches):
    let min = matches[0].parseInt()
    let max = matches[1].parseInt()
    let c = matches[2]
    let password = matches[3]
    let count = password.count(c)
    (count >= min) and (count <= max)
  else:
    raise newException(ValueError, "Can't parse [" & line & "]")

let count = readFile(paramStr(1)).splitLines().filter(validPassword).len()
echo(count)

Part two

day022.nim
import strutils
import sequtils
import os
import re

let passwordRegex = re(r"^(\d+)-(\d+) ([a-z]{1}): ([a-z]+)$")

proc validPassword(line: string): bool =
  var matches: array[4, string]
  if line.match(passwordRegex, matches):
    let first = matches[0].parseInt()
    let second = matches[1].parseInt()
    let c = matches[2][0]
    let password = matches[3]
    ((password[first - 1] == c) and (password[second - 1] != c)) or ((password[
        first - 1] != c) and (password[second - 1] == c))
  else:
    raise newException(ValueError, "Can't parse [" & line & "]")

let count = readFile(paramStr(1)).splitLines().filter(validPassword).len()
echo(count)

Day 3

Part one

day031.nim
import strutils
import os

let input: seq[string] = readFile(paramStr(1)).splitLines()
let boardWidth = input[0].len()
let boardHeight = input.len()

const slopeLine = 1
const slopeColumn = 3

var currentLine = 0
var currentColumn = 0

var treesNumber = 0
while(currentLine < (boardHeight - 1)):
  currentLine += slopeLine
  currentColumn = (currentColumn + slopeColumn).mod(boardWidth)
  let currentPositionContent = input[currentLine][currentColumn]
  echo("(", currentLine, ",", currentColumn, ") ", currentPositionContent)
  if currentPositionContent == '#':
    treesNumber += 1

echo(treesNumber)

Part two

day032.nim
import strutils
import os

let input: seq[string] = readFile(paramStr(1)).splitLines()
let boardWidth = input[0].len()
let boardHeight = input.len()

type Slope = tuple
  slopeLine, slopeColumn: int

const slopeLine = 1
const slopeColumn = 3

const slopes: array[5, Slope] = [
  (slopeLine: 1, slopeColumn: 1),
  (slopeLine: 1, slopeColumn: 3),
  (slopeLine: 1, slopeColumn: 5),
  (slopeLine: 1, slopeColumn: 7),
  (slopeLine: 2, slopeColumn: 1),
]

var totalTreesNumber = 1
for slope in slopes:
  echo("Slope ", slope)
  var treesNumberCurrentSlope = 0
  var currentLine = 0
  var currentColumn = 0
  while(currentLine < (boardHeight - 1)):
    currentLine += slope.slopeLine
    currentColumn = (currentColumn + slope.slopeColumn).mod(boardWidth)
    let currentPositionContent = input[currentLine][currentColumn]
    echo("(", currentLine, ",", currentColumn, ") ", currentPositionContent)
    if currentPositionContent == '#':
      treesNumberCurrentSlope += 1
  totalTreesNumber *= treesNumberCurrentSlope

echo(totalTreesNumber)

Day 4

Part one

day041.nim
import strutils
import sequtils
import os

const allowedPassportFields = ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid", "cid"]
const requiredPassportFields = ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"]

let input: seq[string] = readFile(paramStr(1)).splitLines()
var validPassportNumber = 0
var currentPassportFields = newSeq[string]()
for passportLine in input:
  echo("[", passportLine, "]")
  if passportLine == "":
    if requiredPassportFields.allIt(it in currentPassportFields):
      validPassportNumber += 1
    currentPassportFields = newSeq[string]()
  else:
    for field in passportLine.split(" "):
      let fieldName = field.split(":")[0]
      if not allowedPassportFields.contains(fieldName):
        raise newException(ValueError, "Unknown field [" & fieldName & "]")
      elif currentPassportFields.contains(fieldName):
        raise newException(ValueError, "Duplicated field [" & fieldName & "]")
      currentPassportFields.add(fieldName)

if requiredPassportFields.allIt(it in currentPassportFields):
  validPassportNumber += 1

echo(validPassportNumber)

Part two

day042.nim
import strutils
import sequtils
import os
import re

const allowedPassportFields = ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid", "cid"]
const requiredPassportFields = ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"]

let yearRegex = re(r"^(\d{4})$")
let sizeRegex = re(r"^(\d{2,3})(cm|in)$")
let hairColorRegex = re(r"^#([\da-f]{6})$")
const hairColors = ["amb", "blu", "brn", "gry", "grn", "hzl", "oth"]
let passportIdRegex = re(r"^(\d{9})$")

proc validValue(fieldName: string, fieldValue: string): bool =
  case fieldName:
    of "byr":
      if fieldValue.match(yearRegex):
        let yearValue = fieldValue.parseInt()
        if (yearValue >= 1920) and (yearValue <= 2002):
          return true
    of "iyr":
      if fieldValue.match(yearRegex):
        let yearValue = fieldValue.parseInt()
        if (yearValue >= 2010) and (yearValue <= 2020):
          return true
    of "eyr":
      if fieldValue.match(yearRegex):
        let yearValue = fieldValue.parseInt()
        if (yearValue >= 2020) and (yearValue <= 2030):
          return true
    of "hgt":
      var matches: array[2, string]
      if fieldValue.match(sizeRegex, matches):
        let heightValue = matches[0].parseInt()
        case matches[1]:
          of "cm":
            if (heightValue >= 150) and (heightValue <= 193):
              return true
          of "in":
            if (heightValue >= 59) and (heightValue <= 76):
              return true
    of "hcl":
      if fieldValue.match(hairColorRegex):
        return true
    of "ecl":
      if hairColors.contains(fieldValue):
        return true
    of "pid":
      if fieldValue.match(passportIdRegex):
        return true
    of "cid":
      return true
  return false

let input: seq[string] = readFile(paramStr(1)).splitLines()
var validPassportNumber = 0
var currentPassportFields = newSeq[string]()
for passportLine in input:
  echo("[", passportLine, "]")
  if passportLine == "":
    if requiredPassportFields.allIt(it in currentPassportFields):
      echo("Valid")
      validPassportNumber += 1
    else:
      echo("Invalid")
    currentPassportFields = newSeq[string]()
  else:
    for field in passportLine.split(" "):
      let splittedField = field.split(":")
      let fieldName = splittedField[0]

      if not allowedPassportFields.contains(fieldName):
        raise newException(ValueError, "Unknown field [" & fieldName & "]")
      elif currentPassportFields.contains(fieldName):
        raise newException(ValueError, "Duplicated field [" & fieldName & "]")
      let fieldValue = splittedField[1]
      echo("[", fieldName, "] [", fieldValue, "]")
      if validValue(fieldName, fieldValue):
        echo(true)
        currentPassportFields.add(fieldName)
      else:
        echo(false)

if requiredPassportFields.allIt(it in currentPassportFields):
  validPassportNumber += 1

echo(validPassportNumber)

Day 5

Part one

day051.nim
import strutils
import sequtils
import os
import math

proc calculateSeatId(boardingPass: string): int =
  var value: int = 0
  for index, c in boardingPass:
    case c:
      of 'F', 'L':
        discard
      of 'B', 'R':
        value += 2 ^ (9 - index)
      else:
        raise newException(ValueError, "Unknown value [" & c & "]")
  return value

let input: seq[string] = readFile(paramStr(1)).splitLines()
var max = input.map(calculateSeatId).max
echo(max)

Part two

day052.nim
import strutils
import sequtils
import os
import math

proc calculateSeatId(boardingPass: string): int =
  var value: int = 0
  for index, c in boardingPass:
    case c:
      of 'F', 'L':
        discard
      of 'B', 'R':
        value += 2 ^ (9 - index)
      else:
        raise newException(ValueError, "Unknown value [" & c & "]")
  return value

let input: seq[string] = readFile(paramStr(1)).splitLines()
var seats = input.map(calculateSeatId)
for seat in seats:
  if ((not seats.contains(seat + 1)) and seats.contains(seat + 2)):
    echo(seat + 1)
    quit()

Day 6

Part one

day061.nim
import strutils
import os
import sets

let input: seq[string] = readFile(paramStr(1)).splitLines()

var sumCounts = 0
var currentGroupLetters = initHashSet[char]()
for line in input:
  if line.len == 0:
    sumCounts += currentGroupLetters.len()
    currentGroupLetters = initHashSet[char]()
  else:
    for c in line:
      currentGroupLetters.incl(c)

sumCounts += currentGroupLetters.len()
echo(sumCounts)

Part two

day062.nim
import strutils
import sets
import os

let input: seq[string] = readFile(paramStr(1)).splitLines()

var sumCounts = 0
var newGroup = true
var currentGroupLetters = initHashSet[char]()
for line in input:
  if line.len == 0:
    sumCounts += currentGroupLetters.len()
    var currentGroupLetters = initHashSet[char]()
    newGroup = true
  elif newGroup:
    newGroup = false
    currentGroupLetters = toHashSet(line)
  else:
    currentGroupLetters = currentGroupLetters * toHashSet(line)

sumCounts += currentGroupLetters.len()
echo(sumCounts)

Day 7

Part one

day071.nim
import strutils
import os
import re
import tables
import sets

let noBagContainRegex = re(r"^([a-z ]+) bags contain no other bags\.$")
let bagContain = re(r"^([a-z ]+) bags contain (.+)\.$")
let bagContained = re(r"^(\d+) ([a-z ]+) bag(|s)$")

let input: seq[string] = readFile(paramStr(1)).splitLines()
let targetColor = paramStr(2)

var bagsColorToContainers = initTable[string, seq[string]]()

for line in input:
  if line.match(noBagContainRegex):
    discard
  else:
    var bagContainerMatch: array[2, string]
    if line.match(bagContain, bagContainerMatch):
      let containerBagColor: string = bagContainerMatch[0]
      for contineedBag in bagContainerMatch[1].split(", "):
        var bagContainedMatch: array[3, string]
        if contineedBag.match(bagContained, bagContainedMatch):
          let containedBagColor: string = bagContainedMatch[1]
          if bagsColorToContainers.hasKey(containedBagColor):
            bagsColorToContainers[containedBagColor].add(containerBagColor)
          else:
            bagsColorToContainers[containedBagColor] = @[containerBagColor]
        else:
          raise newException(ValueError, "Can't parse [" & contineedBag & "]")
    else:
      raise newException(ValueError, "Can't parse [" & line & "]")

echo(bagsColorToContainers)

var alreadyKnowColors = initHashSet[string]()

var knewlyKnowColors: HashSet[string] = bagsColorToContainers[
    targetColor].toHashSet()

while (knewlyKnowColors.len() != 0):
  var knewlyKnewlyKnowColors = initHashSet[string]()
  for knewlyKnowColor in knewlyKnowColors:
    if bagsColorToContainers.hasKey(knewlyKnowColor):
      for colorCandidate in bagsColorToContainers[knewlyKnowColor]:
        if (not alreadyKnowColors.contains(colorCandidate)):
          knewlyKnewlyKnowColors.incl(colorCandidate)
    alreadyKnowColors.incl(knewlyKnowColors)
  knewlyKnowColors = knewlyKnewlyKnowColors

echo(alreadyKnowColors.len, " ", alreadyKnowColors)

Part two

day072.nim
import strutils
import os
import re
import tables
import sets

let noBagContainRegex = re(r"^([a-z ]+) bags contain no other bags\.$")
let bagContain = re(r"^([a-z ]+) bags contain (.+)\.$")
let bagContained = re(r"^(\d+) ([a-z ]+) bag(|s)$")

let input: seq[string] = readFile(paramStr(1)).splitLines()
let targetColor = paramStr(2)

type
  ContainedBag = ref object
    bag: Bag
    quantity: int
  Bag = ref object
    name: string
    containedBags: ref seq[ContainedBag]
    containedQuantity: int

var bagsColorToBag = initTable[string, Bag]()

for line in input:
  var noBagContainMatch: array[1, string]
  if line.match(noBagContainRegex, noBagContainMatch):
    let containerBagColor: string = noBagContainMatch[0]
    if bagsColorToBag.hasKey(containerBagColor):
      bagsColorToBag[containerBagColor].containedQuantity = 0
    else:
      bagsColorToBag[containerBagColor] = Bag(name: containerBagColor,
          containedQuantity: 0, containedBags: new seq[ContainedBag])
  else:
    var bagContainerMatch: array[2, string]
    if line.match(bagContain, bagContainerMatch):
      let containerBagColor: string = bagContainerMatch[0]
      var containerBag: Bag
      if bagsColorToBag.hasKey(containerBagColor):
        containerBag = bagsColorToBag[containerBagColor]
      else:
        containerBag = Bag(name: containerBagColor, containedQuantity: -1,
            containedBags: new seq[ContainedBag])
        bagsColorToBag[containerBagColor] = containerBag

      let containedBags: ref seq[ContainedBag] = containerBag.containedBags

      for containedBag in bagContainerMatch[1].split(", "):
        var bagContainedMatch: array[3, string]
        if containedBag.match(bagContained, bagContainedMatch):
          let containedBagColor: string = bagContainedMatch[1]
          let containedBagQuantity: int = bagContainedMatch[0].parseInt()
          var containedBag: Bag
          if bagsColorToBag.hasKey(containedBagColor):
            containedBag = bagsColorToBag[containedBagColor]
          else:
            containedBag = Bag(name: containedBagColor, containedQuantity: -1,
                containedBags: new seq[ContainedBag])
            bagsColorToBag[containedBagColor] = containedBag
          containedBags[].add(ContainedBag(bag: containedBag,
              quantity: containedBagQuantity))
        else:
          raise newException(ValueError, "Can't parse [" & containedBag & "]")
    else:
      raise newException(ValueError, "Can't parse [" & line & "]")

var bagsColorsToExplore: seq[string] = @[targetColor]
while bagsColorsToExplore.len() != 0:
  let lastColorToExplore = bagsColorsToExplore[ ^ - 1]
  let lastBagToExplore: Bag = bagsColorToBag[lastColorToExplore]
  var canComputeBag = true
  var numberOfBags = 0
  for containedBag in lastBagToExplore.containedBags[]:
    if containedBag.bag.containedQuantity == -1:
      bagsColorsToExplore.add(containedBag.bag.name)
      canComputeBag = false
    else:
      numberOfBags = numberOfBags + (containedBag.bag.containedQuantity + 1) *
          containedBag.quantity
  if canComputeBag:
    lastBagToExplore.containedQuantity = numberOfBags
    bagsColorsToExplore.delete(bagsColorsToExplore.len() - 1)
echo(bagsColorToBag[targetColor].containedQuantity)

Day 8

Part one

day081.nim
import strutils
import os
import re
import sets

const NOP_OPERATION = "nop"
const JUMP_OPERATION = "jmp"
const ACC_OPERATION = "acc"
const OPERATIONS = [NOP_OPERATION, JUMP_OPERATION, ACC_OPERATION]
let instructionRegex = re(r"^(" & OPERATIONS.join("|") & r") ([+-]{1}\d+)$")

type
  Instruction = ref object
    operation: string
    operand: int

let input: seq[string] = readFile(paramStr(1)).splitLines()
var program: seq[Instruction] = @[]

for line in input:
  var instructionMatch: array[2, string]
  if line.match(instructionRegex, instructionMatch):
    let instruction: Instruction = Instruction(operation: instructionMatch[0],
        operand: instructionMatch[1].parseInt())
    program.add(instruction)
  else:
    raise newException(ValueError, "Can't parse [" & line & "]")

var currentInstructionIndex: int = 0
var accumulator: int = 0
var exploredInstructions: HashSet[int] = initHashSet[int]()

while true:
  exploredInstructions.incl(currentInstructionIndex)
  let currentInstruction = program[currentInstructionIndex]
  case currentInstruction.operation:
    of NOP_OPERATION:
      currentInstructionIndex += 1
    of JUMP_OPERATION:
      currentInstructionIndex += currentInstruction.operand
    of ACC_OPERATION:
      accumulator += currentInstruction.operand
      currentInstructionIndex += 1
    else:
      raise newException(ValueError, "Unknown operation [" &
          currentInstruction.operation & "]")
  if exploredInstructions.contains(currentInstructionIndex):
    echo(accumulator)
    quit()

Part two

day082.nim
import strutils
import os
import re
import sets
import options

const NOP_OPERATION = "nop"
const JUMP_OPERATION = "jmp"
const ACC_OPERATION = "acc"
const OPERATIONS = [NOP_OPERATION, JUMP_OPERATION, ACC_OPERATION]
let instructionRegex = re(r"^(" & OPERATIONS.join("|") & r") ([+-]{1}\d+)$")

type
  Instruction = ref object
    operation: string
    operand: int

let input: seq[string] = readFile(paramStr(1)).splitLines()
var program: seq[Instruction] = @[]

for line in input:
  var instructionMatch: array[2, string]
  if line.match(instructionRegex, instructionMatch):
    let instruction: Instruction = Instruction(operation: instructionMatch[0],
        operand: instructionMatch[1].parseInt())
    program.add(instruction)
  else:
    raise newException(ValueError, "Can't parse [" & line & "]")

proc evaluateProgram(program: seq[Instruction], instructionIndexToSwitch: int) =
  var currentInstructionIndex: int = 0
  var accumulator: int = 0
  var exploredInstructions: HashSet[int] = initHashSet[int]()
  while true:
    exploredInstructions.incl(currentInstructionIndex)
    let currentInstruction = program[currentInstructionIndex]
    case currentInstruction.operation:
      of NOP_OPERATION:
        if instructionIndexToSwitch == currentInstructionIndex:
          currentInstructionIndex += currentInstruction.operand
        else:
          currentInstructionIndex += 1
      of JUMP_OPERATION:
        if instructionIndexToSwitch == currentInstructionIndex:
          currentInstructionIndex += 1
        else:
          currentInstructionIndex += currentInstruction.operand
      of ACC_OPERATION:
        accumulator += currentInstruction.operand
        currentInstructionIndex += 1
      else:
        raise newException(ValueError, "Unknown operation [" &
            currentInstruction.operation & "]")
    if exploredInstructions.contains(currentInstructionIndex):
      return
    elif (currentInstructionIndex >= program.len()):
      echo(accumulator)
      quit()

for index, instruction in program:
  if ((instruction.operation == NOP_OPERATION) or (instruction.operation ==
      JUMP_OPERATION)):
    evaluateProgram(program, index)

Day 9

Part one

day091.nim
import strutils
import os
import sequtils

let input: seq[int] = readFile(paramStr(1)).splitLines().map(parseInt)
let preambleSize = paramStr(2).parseInt()

proc findNumber(input: seq[int], preambleSize: int,
    currentNumberIndex: int): bool =
  let currentNumber = input[currentNumberIndex]
  for firstIndex in countup(currentNumberIndex - preambleSize,
      currentNumberIndex - 1):
    for secondIndex in countup(currentNumberIndex - preambleSize,
        currentNumberIndex - 1):
      if (firstIndex != secondIndex) and ((input[firstIndex] + input[
          secondIndex]) == currentNumber):
        return true
  return false

for currentNumberIndex in countup(preambleSize, input.len() - 1):
  let currentNumber = input[currentNumberIndex]
  if(not findNumber(input, preambleSize, currentNumberIndex)):
    echo("Failed to find value for ", currentNumber)
    quit()

Part two

day092.nim
import strutils
import os
import sequtils
import options

let input: seq[int] = readFile(paramStr(1)).splitLines().map(parseInt)
let preambleSize = paramStr(2).parseInt()

proc findNumber(input: seq[int], preambleSize: int,
    currentNumberIndex: int): bool =
  let currentNumber = input[currentNumberIndex]
  for firstIndex in countup(currentNumberIndex - preambleSize,
      currentNumberIndex - 1):
    for secondIndex in countup(currentNumberIndex - preambleSize,
        currentNumberIndex - 1):
      if (firstIndex != secondIndex) and ((input[firstIndex] + input[
          secondIndex]) == currentNumber):
        return true
  false

proc findSum(input: seq[int], numberToFind: int, setSize: int): Option[seq[int]] =
  for index in countup(0, input.len() - (1 + setSize)):
    let sequence: seq[int] = input[index .. (index + setSize - 1)]
    if sequence.foldl(a + b) == numberToFind:
      return some(sequence)
  none(seq[int])

for currentNumberIndex in countup(preambleSize, input.len() - 1):
  let currentNumber = input[currentNumberIndex]
  if(not findNumber(input, preambleSize, currentNumberIndex)):
    echo("Failed to find value for ", currentNumber)
    for setSize in countup(2, input.len):
      let possibleSeq = findSum(input, currentNumber, setSize)
      if possibleSeq.isSome():
        echo("Found sum ", possibleSeq)
        echo(possibleSeq.get().min() + possibleSeq.get().max())
        quit()

Day 10

Part one

day101.nim
import strutils
import os
import sequtils
import algorithm
import tables

var input: seq[int] = readFile(paramStr(1)).splitLines().map(parseInt)
input.sort(system.cmp[int])

var joltsDelta: Table[int, int] = initTable[int, int]()
for adapterIndex in countup(0, input.len() - 2):
  var delta = input[adapterIndex + 1] - input[adapterIndex]
  if joltsDelta.contains(delta):
    joltsDelta[delta] += 1
  else:
    joltsDelta[delta] = 1

joltsDelta[input[0]] += 1
joltsDelta[3] += 1
echo(joltsDelta[1], " ", joltsDelta[3], " ", joltsDelta[1] * joltsDelta[3])

Part two

day102.nim
import strutils
import os
import sequtils
import algorithm
import tables

var input: seq[int] = readFile(paramStr(1)).splitLines().map(parseInt)
input.sort(system.cmp[int])

var pathes: Table[int, int] = initTable[int, int]()

pathes[input[ ^ -1]] = 1
for currentAdapterIndex in countdown(input.len() - 2, 0):
  let currentAdapterValue = input[currentAdapterIndex]
  var pathesToCurrentAdapter = 0
  for possibleTargetValue in countup(currentAdapterValue + 1,
      currentAdapterValue + 3):
    if pathes.hasKey(possibleTargetValue):
      pathesToCurrentAdapter += pathes[possibleTargetValue]
  pathes[currentAdapterValue] = pathesToCurrentAdapter

var totalPathes = 0
for possibleFirstStep in countup(1, 3):
  if pathes.hasKey(possibleFirstStep):
    totalPathes += pathes[possibleFirstStep]

echo(totalPathes)

Day 11

Part one

day111.nim
import strutils
import os
import sequtils
import algorithm
import tables

var currentLayout: seq[seq[char]] = readFile(paramStr(1)).splitLines().map(proc(
    s: string): seq[char] = toSeq(s.items))

const EMPTY_SEAT = 'L'
const OCCUPIED_SEAT = '#'
const FLOOR = '.'

let height = currentLayout.len()
let width = currentLayout[0].len()

proc countOccupiedAround(layout: seq[seq[char]], lineIndex: int,
    columnIndex: int, height: int, width: int): int =
  result = 0
  for l in countup([0, lineIndex - 1].max(), [lineIndex + 1, height - 1].min()):
    for c in countup([0, columnIndex - 1].max(), [columnIndex + 1, width -
        1].min()):
      if ((l != lineIndex) or (c != columnIndex)) and (layout[l][c] ==
          OCCUPIED_SEAT):
        result += 1

var anythingChangedInLastIteration = true
while(anythingChangedInLastIteration):
  anythingChangedInLastIteration = false
  var newLayout: seq[seq[char]] = newSeq[seq[char]](height)
  for lineIndex in countup(0, height - 1):
    var newLine: seq[char] = newSeq[char](width)
    for columnIndex in countup(0, width - 1):
      let currentTile = currentLayout[lineIndex][columnIndex]
      case currentTile:
        of FLOOR:
          newLine[columnIndex] = FLOOR
        of EMPTY_SEAT:
          let occupiedAround = countOccupiedAround(currentLayout, lineIndex,
              columnIndex, height, width)
          let result = if (occupiedAround == 0): OCCUPIED_SEAT else: EMPTY_SEAT
          if result == OCCUPIED_SEAT:
            anythingChangedInLastIteration = true
          newLine[columnIndex] = result
        of OCCUPIED_SEAT:
          let occupiedAround = countOccupiedAround(currentLayout, lineIndex,
              columnIndex, height, width)
          let result = if (occupiedAround >= 4): EMPTY_SEAT else: OCCUPIED_SEAT
          if result == EMPTY_SEAT:
            anythingChangedInLastIteration = true
          newLine[columnIndex] = result
        else:
          raise newException(ValueError, "Unknown tile [" & currentTile & "]")
      newLayout[lineIndex] = newLine
  currentLayout = newLayout
let occupiedSeatCount = currentLayout.map(proc(
    s: seq[char]): int = s.count(OCCUPIED_SEAT)).foldl(a + b)
echo(occupiedSeatCount)

Part two

day112.nim
import strutils
import os
import sequtils
import algorithm
import tables

var currentLayout: seq[seq[char]] = readFile(paramStr(1)).splitLines().map(proc(
    s: string): seq[char] = toSeq(s.items))

const EMPTY_SEAT = 'L'
const OCCUPIED_SEAT = '#'
const FLOOR = '.'

let height = currentLayout.len()
let width = currentLayout[0].len()

proc hasOccupiedSeatInDirection(layout: seq[seq[char]], lineIndex: int,
    columnIndex: int, height: int, width: int, deltaLine: int,
        deltaColum: int): bool =
  var currentLine = lineIndex
  var currentColumn = columnIndex
  while(true):
    currentLine += deltaLine
    if (currentLine < 0) or (currentLine > (height - 1)):
      return false
    currentColumn += deltaColum
    if (currentColumn < 0) or (currentColumn > (width - 1)):
      return false
    let currentTile = currentLayout[currentLine][currentColumn]
    case currentTile:
      of FLOOR:
        discard
      of EMPTY_SEAT:
        return false
      of OCCUPIED_SEAT:
        return true
      else:
        raise newException(ValueError, "Unknown tile [" & currentTile & "]")

const directions: array[0..7, array[0..1, int]] = [
  [-1, -1],
  [-1, 0],
  [-1, 1],
  [0, -1],
  [0, 1],
  [1, -1],
  [1, 0],
  [1, 1],
]

proc countOccupiedAround(layout: seq[seq[char]], lineIndex: int,
    columnIndex: int, height: int, width: int): int =
  return directions.map(proc(s: array[0..1,
      int]): bool = hasOccupiedSeatInDirection(layout, lineIndex, columnIndex,
      height, width, s[0], s[1])).count(true)

var anythingChangedInLastIteration = true
while(anythingChangedInLastIteration):
  anythingChangedInLastIteration = false
  var newLayout: seq[seq[char]] = newSeq[seq[char]](height)
  for lineIndex in countup(0, height - 1):
    var newLine: seq[char] = newSeq[char](width)
    for columnIndex in countup(0, width - 1):
      let currentTile = currentLayout[lineIndex][columnIndex]
      case currentTile:
        of FLOOR:
          newLine[columnIndex] = FLOOR
        of EMPTY_SEAT:
          let occupiedAround = countOccupiedAround(currentLayout, lineIndex,
              columnIndex, height, width)
          if (lineIndex == 0) and (columnIndex == 8):
            echo("! ", occupiedAround)
          let result = if (occupiedAround == 0): OCCUPIED_SEAT else: EMPTY_SEAT
          if result == OCCUPIED_SEAT:
            anythingChangedInLastIteration = true
          newLine[columnIndex] = result
        of OCCUPIED_SEAT:
          let occupiedAround = countOccupiedAround(currentLayout, lineIndex,
              columnIndex, height, width)
          let result = if (occupiedAround >= 5): EMPTY_SEAT else: OCCUPIED_SEAT
          if result == EMPTY_SEAT:
            anythingChangedInLastIteration = true
          newLine[columnIndex] = result
        else:
          raise newException(ValueError, "Unknown tile [" & currentTile & "]")
      newLayout[lineIndex] = newLine
  echo(newLayout.map(proc(
    s: seq[char]): string = s.join()))
  currentLayout = newLayout
let occupiedSeatCount = currentLayout.map(proc(
    s: seq[char]): int = s.count(OCCUPIED_SEAT)).foldl(a + b)
echo(occupiedSeatCount)

Day 12

Part one

day121.nim
import strutils
import os
import tables
import re

const NORTH = 'N'
const SOUTH = 'S'
const EAST = 'E'
const WEST = 'W'
const RIGHT = 'R'
const LEFT = 'L'
const FORWARD = 'F'

const TURN_RIGHT = {
  NORTH: WEST,
  WEST: SOUTH,
  SOUTH: EAST,
  EAST: NORTH
}.toTable

const TURN_LEFT = {
  NORTH: EAST,
  WEST: NORTH,
  SOUTH: WEST,
  EAST: SOUTH
}.toTable

let input: seq[string] = readFile(paramStr(1)).splitLines()

let instructionRegex = re(r"^([" & NORTH & SOUTH & EAST & WEST & LEFT & RIGHT &
    FORWARD & r"])(\d+)$")

var facing: char = EAST
var linePosition: int = 0
var columnPosition: int = 0

for line in input:
  var instructionMatch: array[2, string]
  if line.match(instructionRegex, instructionMatch):
    var action: char = instructionMatch[0][0]
    var value: int = instructionMatch[1].parseInt()
    case action:
      of NORTH:
        linePosition += value
      of SOUTH:
        linePosition -= value
      of EAST:
        columnPosition += value
      of WEST:
        columnPosition -= value
      of LEFT:
        if value.mod(90) != 0:
          raise newException(ValueError, "Unknown angle [" & $value & "]")
        for i in countup(1, value.div(90)):
          facing = TURN_LEFT[facing]
      of RIGHT:
        if value.mod(90) != 0:
          raise newException(ValueError, "Unknown angle [" & $value & "]")
        for i in countup(1, value.div(90)):
          facing = TURN_RIGHT[facing]
      of FORWARD:
        case facing:
          of NORTH:
            linePosition -= value
          of SOUTH:
            linePosition += value
          of EAST:
            columnPosition += value
          of WEST:
            columnPosition -= value
          else:
            raise newException(ValueError, "Unknown action [" & facing & "]")
      else:
        raise newException(ValueError, "Unknown action [" & action & "]")
  else:
    raise newException(ValueError, "Can't parse [" & line & "]")
echo(linePosition.abs() + columnPosition.abs())

Part two

day122.nim
import strutils
import os
import re
import math

const NORTH = 'N'
const SOUTH = 'S'
const EAST = 'E'
const WEST = 'W'
const RIGHT = 'R'
const LEFT = 'L'
const FORWARD = 'F'

let input: seq[string] = readFile(paramStr(1)).splitLines()

let instructionRegex = re(r"^([" & NORTH & SOUTH & EAST & WEST & LEFT & RIGHT &
    FORWARD & r"])(\d+)$")

var waypointLine: int = 1
var waypointColumn: int = 10
var boatLine: int = 0
var boatColumn: int = 0

proc newColumn(line: int, column: int, angle: float): int =
  return column * (angle.degToRad().cos()).toInt() - line * angle.degToRad().sin().toInt()
proc newLine(line: int, column: int, angle: float): int =
  return column * (angle.degToRad().sin()).toInt() + line * angle.degToRad().cos().toInt()

for line in input:
  var instructionMatch: array[2, string]
  if line.match(instructionRegex, instructionMatch):
    var action: char = instructionMatch[0][0]
    var value: int = instructionMatch[1].parseInt()
    case action:
      of NORTH:
        waypointLine += value
      of SOUTH:
        waypointLine -= value
      of EAST:
        waypointColumn += value
      of WEST:
        waypointColumn -= value
      of LEFT:
        if value.mod(90) != 0:
          raise newException(ValueError, "Unknown angle [" & $value & "]")
        var oldWaypointLine = waypointLine
        var oldWaypointColumn = waypointColumn
        waypointColumn = newColumn(oldWaypointLine, oldWaypointColumn,
            value.toFloat())
        waypointLine = newLine(oldWaypointLine, oldWaypointColumn,
            value.toFloat())
      of RIGHT:
        if value.mod(90) != 0:
          raise newException(ValueError, "Unknown angle [" & $value & "]")
        var oldWaypointLine = waypointLine
        var oldWaypointColumn = waypointColumn
        waypointColumn = newColumn(oldWaypointLine, oldWaypointColumn, -
            value.toFloat())
        waypointLine = newLine(oldWaypointLine, oldWaypointColumn, -
            value.toFloat())
      of FORWARD:
        boatLine += waypointLine * value
        boatColumn += waypointColumn * value
      else:
        raise newException(ValueError, "Unknown action [" & action & "]")
  else:
    raise newException(ValueError, "Can't parse [" & line & "]")
  echo("Boat: (", boatLine, ", ", boatColumn, ") waypoint (", waypointLine,
      ", ", waypointColumn, ")")
echo(boatLine.abs() + boatColumn.abs())

Day 13

Part one

day131.nim
import strutils
import os
import sequtils

let input: seq[string] = readFile(paramStr(1)).splitLines()

let initialTimeStamp = input[0].parseInt()
let busses = input[1].split(",").filter(proc(s: string): bool = s !=
    "x").map(proc(s: string): int = s.parseInt())
var currentTimeStamp = initialTimeStamp
while(true):
  for bus in busses:
    if currentTimeStamp.mod(bus) == 0:
      let waitTime = currentTimeStamp - initialTimeStamp
      echo("Timestamp: ", currentTimeStamp, " bus ", bus, " wait time ",
          waitTime, " result ", (bus * waitTime))
      quit()
  currentTimeStamp += 1

Part two

day132.nim
import strutils
import os

var busses: seq[array[2, int]] = @[]

let input: seq[string] = readFile(paramStr(1)).splitLines()[1].split(",")

for busIndex, busId in input:
  if busId != "x":
    busses.add([busId.parseInt(), busIndex])

var currentStepSize = busses[0][0]
var currentTime = 0
for bus in busses[1 .. ^1]:
  let busIndex = bus[0]
  let busId = bus[1]
  while (currentTime + busId).mod(busIndex) != 0:
    currentTime += currentStepSize
  currentStepSize *= busIndex
echo(currentTime)

Day 14

Part one

day141.nim
import strutils
import os
import tables
import re

const MEMORY_SIZE = 36
let MASK_INSTRUCTION_REGEX = re(r"^mask = ([X01]{" & $MEMORY_SIZE & r"})$")
let WRITE_INSTRUCTION_REGEX = re(r"^mem\[(\d+)\] = (\d+)$")

let program: seq[string] = readFile(paramStr(1)).splitLines()

var memory = initTable[int, BiggestInt]()
var currentMask: string = ""

for line in program:
  var maskMatch: array[1, string]
  if line.match(MASK_INSTRUCTION_REGEX, maskMatch):
    currentMask = maskMatch[0]
    discard
  else:
    var writeMatch: array[2, string]
    if line.match(WRITE_INSTRUCTION_REGEX, writeMatch):
      let valueParameter = writeMatch[1].parseInt().toBin(MEMORY_SIZE)
      var result: string = '0'.repeat(MEMORY_SIZE)
      for i in countup(0, MEMORY_SIZE - 1):
        case currentMask[i]:
        of '0':
          result[i] = '0'
        of '1':
          result[i] = '1'
        of 'X':
          result[i] = valueParameter[i]
        else:
          raise newException(ValueError, "Unknown action [" & currentMask[i] & "]")
      let resultAsInteger = fromBin[BiggestInt](result)
      memory[writeMatch[0].parseInt()] = resultAsInteger
    else:
      raise newException(ValueError, "Can't parse [" & line & "]")
echo(memory)

var sum: BiggestInt = 0
for address, value in memory:
  sum += value
echo(sum)

Part two

day142.nim
import strutils
import os
import tables
import re

const MEMORY_SIZE = 36
let MASK_INSTRUCTION_REGEX = re(r"^mask = ([X01]{" & $MEMORY_SIZE & r"})$")
let WRITE_INSTRUCTION_REGEX = re(r"^mem\[(\d+)\] = (\d+)$")

let program: seq[string] = readFile(paramStr(1)).splitLines()

var memory = newTable[BiggestInt, BiggestInt]()
var currentMask: string = ""

proc processWrite(memoryAddress: string, value: BiggestInt, memory: ref Table[
    BiggestInt, BiggestInt]) =
  let xIndex = memoryAddress.find('X')
  if xIndex == -1:
    let memoryAddressAsInteger: BiggestInt = fromBin[BiggestInt](memoryAddress)
    memory[memoryAddressAsInteger] = value
  else:
    var memoryAddress0 = memoryAddress
    memoryAddress0[xIndex] = '0'
    processWrite(memoryAddress0, value, memory)
    var memoryAddress1 = memoryAddress
    memoryAddress1[xIndex] = '1'
    processWrite(memoryAddress1, value, memory)

for line in program:
  var maskMatch: array[1, string]
  if line.match(MASK_INSTRUCTION_REGEX, maskMatch):
    currentMask = maskMatch[0]
    discard
  else:
    var writeMatch: array[2, string]
    if line.match(WRITE_INSTRUCTION_REGEX, writeMatch):
      let memoryAddress = writeMatch[0].parseInt().toBin(MEMORY_SIZE)
      var result: string = '0'.repeat(MEMORY_SIZE)
      for i in countup(0, MEMORY_SIZE - 1):
        case currentMask[i]:
        of '0':
          result[i] = memoryAddress[i]
        of '1':
          result[i] = '1'
        of 'X':
          result[i] = 'X'
        else:
          raise newException(ValueError, "Unknown action [" & currentMask[i] & "]")
      let valueToWrite = writeMatch[1].parseBiggestInt()
      processWrite(result, valueToWrite, memory)
    else:
      raise newException(ValueError, "Can't parse [" & line & "]")

echo(memory)

var sum: BiggestInt = 0
for address, value in memory:
  sum += value
echo(sum)

Day 15

Part one

day151.nim
import strutils
import os
import sequtils
import tables

var initialNumbers: seq[int] = readFile(paramStr(1)).split(',').map(parseInt)

var game = newTable[int, int]()

for index in countup(0, initialNumbers.len() - 2):
  let number = initialNumbers[index]
  game[number] = index + 1

proc nextNumber(game: ref Table[int, int], turnNumber: int,
    lastNumber: int): int =
  if game.hasKey(lastNumber):
    result = turnNumber - game[lastNumber]
  else:
    result = 0
  game[lastNumber] = turnNumber

var turnNumber = initialNumbers.len()
var lastNumber = initialNumbers[ ^ -1]
while (turnNumber < 2020):
  lastNumber = nextNumber(game, turnNumber, lastNumber)
  turnNumber += 1

echo(lastNumber)

Part two

day152.nim
import strutils
import os
import sequtils
import tables

var initialNumbers: seq[int] = readFile(paramStr(1)).split(',').map(parseInt)

var game = newTable[int, int]()

for index in countup(0, initialNumbers.len() - 2):
  let number = initialNumbers[index]
  game[number] = index + 1

proc nextNumber(game: ref Table[int, int], turnNumber: int,
    lastNumber: int): int =
  if game.hasKey(lastNumber):
    result = turnNumber - game[lastNumber]
  else:
    result = 0
  game[lastNumber] = turnNumber

var turnNumber = initialNumbers.len()
var lastNumber = initialNumbers[initialNumbers.len() - 1]
while (turnNumber < 30000000):
  lastNumber = nextNumber(game, turnNumber, lastNumber)
  turnNumber += 1

echo(lastNumber)

Day 16

Part one

day161.nim
import strutils
import os
import re
import sequtils
import sets

var setup: seq[string] = readFile(paramStr(1)).splitLines()

let ruleRegex = re(r"^([^:]+): (\d+)-(\d+) or (\d+)-(\d+)$")
var values = initHashSet[int]()

var currentLineIndex = 0
var ruleMatch: array[5, string]

while setup[currentLineIndex].match(ruleRegex, ruleMatch):
  for i in countup(ruleMatch[1].parseInt(), ruleMatch[2].parseInt()):
    values.incl(i)
  for i in countup(ruleMatch[3].parseInt(), ruleMatch[4].parseInt()):
    values.incl(i)
  currentLineIndex += 1

while setup[currentLineIndex] != "nearby tickets:":
  currentLineIndex += 1
currentLineIndex += 1

var errorsSum = 0

while currentLineIndex < setup.len():
  for value in (setup[currentLineIndex].split(",").map(parseInt)):
    if not values.contains(value):
      errorsSum += value
  currentLineIndex += 1
echo(errorsSum)

Part two

day162.nim
import strutils
import os
import tables
import re
import sequtils
import sets

var setup: seq[string] = readFile(paramStr(1)).splitLines()

let ruleRegex = re(r"^([^:]+): (\d+)-(\d+) or (\d+)-(\d+)$")

var validValuesAnyField = initHashSet[int]()
var validValuesPerField = initTable[string, HashSet[int]]()

var currentLineIndex = 0
var fieldsNames: seq[string] = @[]
var ruleMatch: array[5, string]

while setup[currentLineIndex].match(ruleRegex, ruleMatch):
  let fieldName = ruleMatch[0]
  fieldsNames.add(fieldName)
  var validValuesCurrentField = initHashSet[int]()
  for i in countup(ruleMatch[1].parseInt(), ruleMatch[2].parseInt()):
    validValuesAnyField.incl(i)
    validValuesCurrentField.incl(i)
  for i in countup(ruleMatch[3].parseInt(), ruleMatch[4].parseInt()):
    validValuesAnyField.incl(i)
    validValuesCurrentField.incl(i)
  validValuesPerField[fieldName] = validValuesCurrentField
  currentLineIndex += 1

var possibleFieldsPerIndex: Table[int, seq[string]] = initTable[int, seq[string]]()
for i in countup(0, validValuesPerField.len() - 1):
  possibleFieldsPerIndex[i] = fieldsNames

while setup[currentLineIndex] != "your ticket:":
  currentLineIndex += 1
currentLineIndex += 1
let myTickets = setup[currentLineIndex].split(",").map(parseInt)

while setup[currentLineIndex] != "nearby tickets:":
  currentLineIndex += 1
currentLineIndex += 1

var validTickets: seq[seq[int]] = @[]

while currentLineIndex < setup.len():
  let currentTicket = setup[currentLineIndex].split(",").map(parseInt)
  if currentTicket.all(proc (v: int): bool = validValuesAnyField.contains(v)):
    validTickets.add(currentTicket)
  currentLineIndex += 1

for validTicket in validTickets:
  for index, value in validTicket:
    var possibleFields = possibleFieldsPerIndex[index]
    possibleFields.keepIf(proc(fieldName: string): bool = validValuesPerField[
        fieldName].contains(value))
    possibleFieldsPerIndex[index] = possibleFields

var fieldNames: Table[int, string] = initTable[int, string]()

while(possibleFieldsPerIndex.len() > 0):
  for fieldIndex, fieldPossibleNames in possibleFieldsPerIndex:
    if fieldPossibleNames.len() == 1:
      let fieldName = fieldPossibleNames[0]
      fieldNames[fieldIndex] = fieldName
      possibleFieldsPerIndex.del(fieldIndex)
      for i, f in possibleFieldsPerIndex:
        var names = f
        names.keepItIf(it != fieldName)
        possibleFieldsPerIndex[i] = names
      break

var departureValue = 1

for index, fieldName in fieldNames:
  if fieldName.find("departure ") == 0:
    departureValue *= myTickets[index]
echo(departureValue)

Day 17

Part one

day171.nim
import sets
import strutils
import os
import sequtils

type
  Cube = ref object
    elements: HashSet[string]
    minX: int
    maxX: int
    minY: int
    maxY: int
    minZ: int
    maxZ: int

proc toCoordinates(x: int, y: int, z: int): string =
  $x & " " & $y & " " & $z

proc contains(elements: HashSet[string], x: int, y: int, z: int): bool =
  elements.contains(toCoordinates(x, y, z))

proc cubeElementAsChar(c: bool): char =
  if c:
    '#'
  else:
    '.'

proc countAround(elements: HashSet[string], x: int, y: int, z: int): int =
  var count = 0
  for calcX in countup(x - 1, x + 1):
    for calcY in countup(y - 1, y + 1):
      for calcZ in countup(z - 1, z + 1):
        if ((x != calcX) or (y != calcY) or (z != calcZ)) and contains(elements,
            calcX, calcY, calcZ):
          count += 1
  count

proc printCube(cube: Cube) =
  for z in countup(cube.minZ, cube.maxZ):
    echo("z=", z)
    for x in countup(cube.minX, cube.maxX):
      let line = toSeq(cube.minY .. cube.maxY).map(proc(
          y: int): char = cubeElementAsChar(cube.elements.contains(x, y,
              z))).join("")
      echo(line)
    echo("")

var setup: seq[string] = readFile(paramStr(1)).splitLines()

var initElements = initHashSet[string]()

for lineIndex, line in setup:
  for columnIndex, columnValue in line:
    if columnValue == '#':
      initElements.incl(toCoordinates(lineIndex, columnIndex, 0))
echo(initElements)

var currentCube = Cube(elements: initElements, minX: 0, maxX: setup.len() - 1,
    minY: 0, maxY: setup[0].len() - 1, minZ: 0, maxZ: 0)

printCube(currentCube)

for roundIndex in countup(0, 5):
  var newElements = initHashSet[string]()
  for calcX in countup(currentCube.minX - 1, currentCube.maxX + 1):
    for calcY in countup(currentCube.minY - 1, currentCube.maxY + 1):
      for calcZ in countup(currentCube.minZ - 1, currentCube.maxZ + 1):
        let cubesAround = countAround(currentCube.elements, calcX, calcY, calcZ)
        if contains(currentCube.elements, calcX, calcY, calcZ):
          if (cubesAround == 2) or (cubesAround == 3):
            newElements.incl(toCoordinates(calcX, calcY, calcZ))
        else:
          if (cubesAround == 3):
            newElements.incl(toCoordinates(calcX, calcY, calcZ))
  currentCube = Cube(elements: newElements, minX: currentCube.minX - 1,
    maxX: currentCube.maxX + 1,
    minY: currentCube.minY - 1, maxY: currentCube.maxY + 1,
    minZ: currentCube.minZ - 1, maxZ: currentCube.maxZ + 1)
  printCube(currentCube)
echo(currentCube.elements.len())

Part two

day172.nim
import sets
import strutils
import os
import sequtils

type
  Cube = ref object
    elements: HashSet[string]
    minX: int
    maxX: int
    minY: int
    maxY: int
    minZ: int
    maxZ: int
    minW: int
    maxW: int

proc toCoordinates(x: int, y: int, z: int, w: int): string =
  $x & " " & $y & " " & $z & " " & $w

proc contains(elements: HashSet[string], x: int, y: int, z: int, w: int): bool =
  elements.contains(toCoordinates(x, y, z, w))

proc cubeElementAsChar(c: bool): char =
  if c:
    '#'
  else:
    '.'

proc countAround(elements: HashSet[string], x: int, y: int, z: int, w: int): int =
  var count = 0
  for calcX in countup(x - 1, x + 1):
    for calcY in countup(y - 1, y + 1):
      for calcZ in countup(z - 1, z + 1):
        for calcW in countup(w - 1, w + 1):
          if ((x != calcX) or (y != calcY) or (z != calcZ) or (w != calcW)) and
              contains(elements, calcX, calcY, calcZ, calcW):
            count += 1
  count

proc printCube(cube: Cube) =
  for w in countup(cube.minW, cube.maxW):
    for z in countup(cube.minZ, cube.maxZ):
      echo("z=", z, " w=", w)
      for x in countup(cube.minX, cube.maxX):
        let line = toSeq(cube.minY .. cube.maxY).map(proc(
            y: int): char = cubeElementAsChar(cube.elements.contains(x, y,
                z, w))).join("")
        echo(line)
      echo("")

var setup: seq[string] = readFile(paramStr(1)).splitLines()

var initElements = initHashSet[string]()

for lineIndex, line in setup:
  for columnIndex, columnValue in line:
    if columnValue == '#':
      initElements.incl(toCoordinates(lineIndex, columnIndex, 0, 0))
echo(initElements)

var currentCube = Cube(elements: initElements, minX: 0, maxX: setup.len() - 1,
    minY: 0, maxY: setup[0].len() - 1, minZ: 0, maxZ: 0, minW: 0, maxW: 0)

printCube(currentCube)

for roundIndex in countup(0, 5):
  var newElements = initHashSet[string]()
  for calcX in countup(currentCube.minX - 1, currentCube.maxX + 1):
    for calcY in countup(currentCube.minY - 1, currentCube.maxY + 1):
      for calcZ in countup(currentCube.minZ - 1, currentCube.maxZ + 1):
        for calcW in countup(currentCube.minW - 1, currentCube.maxW + 1):
          let cubesAround = countAround(currentCube.elements, calcX, calcY,
              calcZ, calcW)
          if contains(currentCube.elements, calcX, calcY, calcZ, calcW):
            if (cubesAround == 2) or (cubesAround == 3):
              newElements.incl(toCoordinates(calcX, calcY, calcZ, calcW))
          else:
            if (cubesAround == 3):
              newElements.incl(toCoordinates(calcX, calcY, calcZ, calcW))
            discard
  currentCube = Cube(elements: newElements, minX: currentCube.minX - 1,
    maxX: currentCube.maxX + 1,
    minY: currentCube.minY - 1, maxY: currentCube.maxY + 1,
    minZ: currentCube.minZ - 1, maxZ: currentCube.maxZ + 1,
    minW: currentCube.minW - 1, maxW: currentCube.maxW + 1)
  printCube(currentCube)
echo(currentCube.elements.len())

Day 18

Part one

day181.nim
import strutils
import os
import re

var formulas: seq[string] = readFile(paramStr(1)).splitLines()

let calculationRegex = re(r"^(\d+) ([\+\*]) (\d+)(.*)$")
let parenthesisRegex = re(r"^(.*)\(([^\(\)]+)\)(.*)$")

proc calculateFormulaWithoutParenthesis(formula: string): string =
  var calculationMatch: array[4, string]
  var innerFormula = formula
  while innerFormula.match(calculationRegex, calculationMatch):
    let first = calculationMatch[0].parseInt
    let second = calculationMatch[2].parseInt
    var calculationResult: int
    case calculationMatch[1]:
      of "*":
        calculationResult = first * second
      of "+":
        calculationResult = first + second
      else:
        raise newException(ValueError, "Unknown operation [" & calculationMatch[
            1] & "]")
    innerFormula = $calculationResult & calculationMatch[3]
  innerFormula

proc simplifyParenthesis(formula: string): string =
  var parenthesisMatch: array[3, string]
  if formula.match(parenthesisRegex, parenthesisMatch):
    return parenthesisMatch[0] & calculateFormulaWithoutParenthesis(
        parenthesisMatch[1]) & parenthesisMatch[2]
  else:
    raise newException(ValueError, "Can't parse [" & formula & "]")

var total = 0
for formula in formulas:
  var currentFormula = formula
  while currentFormula.find('(') != -1:
    currentFormula = simplifyParenthesis(currentFormula)
  var formulaResult = calculateFormulaWithoutParenthesis(
      currentFormula).parseInt
  total += formulaResult
echo(total)

Part two

day182.nim
import strutils
import os
import re

var formulas: seq[string] = readFile(paramStr(1)).splitLines()

let additionRegex = re(r"^(.*?)(\d+) \+ (\d+)(.*?)$")
let multiplicationRegex = re(r"^(.*?)(\d+) \* (\d+)(.*?)$")
let parenthesisRegex = re(r"^(.*)\(([^\(\)]+)\)(.*)$")

proc calculateFormulaWithoutParenthesis(formula: string): string =
  var calculationMatch: array[4, string]
  var innerFormula = formula
  var lastPassDidSomething = true
  while lastPassDidSomething:
    lastPassDidSomething = false
    if innerFormula.match(additionRegex, calculationMatch):
      lastPassDidSomething = true
      let first = calculationMatch[1].parseInt
      let second = calculationMatch[2].parseInt
      var calculationResult = first + second
      innerFormula = calculationMatch[0] & $calculationResult &
          calculationMatch[3]
    elif innerFormula.match(multiplicationRegex, calculationMatch):
      lastPassDidSomething = true
      let first = calculationMatch[1].parseInt
      let second = calculationMatch[2].parseInt
      var calculationResult = first * second
      innerFormula = calculationMatch[0] & $calculationResult &
          calculationMatch[3]
  innerFormula

proc simplifyParenthesis(formula: string): string =
  var parenthesisMatch: array[3, string]
  if formula.match(parenthesisRegex, parenthesisMatch):
    return parenthesisMatch[0] & calculateFormulaWithoutParenthesis(
        parenthesisMatch[1]) & parenthesisMatch[2]
  else:
    raise newException(ValueError, "Can't parse [" & formula & "]")

var total = 0
for formula in formulas:
  var currentFormula = formula
  while currentFormula.find('(') != -1:
    currentFormula = simplifyParenthesis(currentFormula)
  var formulaResult = calculateFormulaWithoutParenthesis(
      currentFormula).parseInt
  total += formulaResult
echo(total)

Day 19

Part one

day191.nim
import strutils
import os
import re
import tables
import sequtils

var input: seq[string] = readFile(paramStr(1)).splitLines()

let ruleSingleLetterRegex = re("""^(\d+): "([a-z])"$""")
let ruleCompositionRegex = re(r"^(\d+): ([\d |]+)$")

type
  Rule = ref object
    index: int
    content: string
    singleChar: bool

proc calculateSubRule(subRule: string): string =
  "(" & subRule.strip().split(" ").map(proc(
      element: string): string = "(?&rule_" & element & ")").join(
          "") & ")"

proc calculateRule(rule: Rule): string =
  result = "(?<rule_" & $rule.index & ">"
  if rule.singleChar:
    result &= rule.content
  else:
    result &= rule.content.strip().split("|").map(proc(
      subRule: string): string = calculateSubRule(subRule)).join("|")
  result &= ")"

let rulesById = newTable[int, Rule]()

var ruleSingleLetterMatch: array[2, string]
var ruleCompositionMatch: array[2, string]

var inputLineIndex = 0
while input[inputLineIndex] != "":
  let currentLine = input[inputLineIndex]
  if currentLine.match(ruleSingleLetterRegex, ruleCompositionMatch):
    let ruleIndex = ruleCompositionMatch[0].parseInt()
    let letter = ruleCompositionMatch[1]
    let rule = Rule(index: ruleIndex, content: letter,
        singleChar: true)
    rulesById[ruleIndex] = rule
  elif currentLine.match(ruleCompositionRegex, ruleCompositionMatch):
    let ruleIndex = ruleCompositionMatch[0].parseInt()
    let rule = Rule(index: ruleIndex, content: ruleCompositionMatch[1],
        singleChar: false)
    rulesById[ruleIndex] = rule
  else:
    raise newException(ValueError, "Can't parse [" & currentLine & "]")
  inputLineIndex += 1

var regex = "(?(DEFINE)"
for ruleIndex, rule in rulesById:
  if ruleIndex != 0:
    regex &= rule.calculateRule()
regex &= ")^" & rulesById[0].calculateRule() & "$"

echo(regex)
var ruleRegex = re(regex)

var validRules = 0
for inputLineIndex in countup(inputLineIndex + 1, input.len() - 1):
  let currentLine = input[inputLineIndex]
  if currentLine.match(ruleRegex):
    validRules += 1
echo(validRules)

Part two

day192.nim
import strutils
import os
import re
import tables
import sequtils

var input: seq[string] = readFile(paramStr(1)).splitLines()

let ruleSingleLetterRegex = re("""^(\d+): "([a-z])"$""")
let ruleCompositionRegex = re(r"^(\d+): ([\d |]+)$")

type
  Rule = ref object
    index: int
    content: string
    singleChar: bool

proc calculateSubRule(subRule: string): string =
  "(" & subRule.strip().split(" ").map(proc(
      element: string): string = "(?&rule_" & element & ")").join(
          "") & ")"

proc calculateRule(rule: Rule): string =
  result = "(?<rule_" & $rule.index & ">"
  if rule.singleChar:
    result &= rule.content
  else:
    result &= rule.content.strip().split("|").map(proc(
      subRule: string): string = calculateSubRule(subRule)).join("|")
  result &= ")"

let rulesById = newTable[int, Rule]()

var ruleSingleLetterMatch: array[2, string]
var ruleCompositionMatch: array[2, string]

var inputLineIndex = 0
while input[inputLineIndex] != "":
  let currentLine = input[inputLineIndex]
  if currentLine.match(ruleSingleLetterRegex, ruleCompositionMatch):
    let ruleIndex = ruleCompositionMatch[0].parseInt()
    let letter = ruleCompositionMatch[1]
    let rule = Rule(index: ruleIndex, content: letter,
        singleChar: true)
    rulesById[ruleIndex] = rule
  elif currentLine.match(ruleCompositionRegex, ruleCompositionMatch):
    let ruleIndex = ruleCompositionMatch[0].parseInt()
    let rule = Rule(index: ruleIndex, content: ruleCompositionMatch[1],
        singleChar: false)
    rulesById[ruleIndex] = rule
  else:
    raise newException(ValueError, "Can't parse [" & currentLine & "]")
  inputLineIndex += 1

var regex = "(?(DEFINE)"
for ruleIndex, rule in rulesById:
  if ruleIndex != 0:
    regex &= rule.calculateRule()
regex &= ")^" & rulesById[0].calculateRule() & "$"

echo(regex)
# Nim doesn't support PCRE Regex so I used perl for the answer :
# perl -ne 'while(/THE_REX/g){print "$&\n";}' FILE_NAME | wc -l

Day 20

Part one

day201.nim
import strutils
import os
import re
import tables
import sets
import math
import algorithm
import sequtils

var input: seq[string] = readFile(paramStr(1)).splitLines()

type
  Tile = ref object
    id: int
    position: int
    bottomBorder: int
    rightBorder: int

proc countPixels(pixels: HashSet[int], initValue: int, delta: int): int =
  result = 0
  for index in countup(0, 9):
    if pixels.contains(initValue + (index * delta)):
      result += 2 ^ (9 - index)

proc initTile(pixels: HashSet[int]): seq[seq[int]] =
  let top = countPixels(pixels, 0, 1)
  let iTop = countPixels(pixels, 9, -1)

  let bottom = countPixels(pixels, 90, 1)
  let iBottom = countPixels(pixels, 99, -1)

  let left = countPixels(pixels, 0, 10)
  let iLeft = countPixels(pixels, 90, -10)

  let right = countPixels(pixels, 9, 10)
  let iRight = countPixels(pixels, 99, -10)

  @[
    @[top, right, bottom, left],
    @[iLeft, top, iRight, bottom],
    @[iBottom, iLeft, iTop, iRight],
    @[right, iBottom, left, iTop],

    @[iTop, left, iBottom, right],
    @[iRight, iTop, iLeft, iBottom],
    @[bottom, iRight, top, iLeft],
    @[left, bottom, right, top],
  ]

var tilesContents = initTable[int, seq[string]]()

var allTiles: seq[Tile] = @[]
var tilesByTopBorder = initTable[int, seq[Tile]]()
var tilesByLeftBorder = initTable[int, seq[Tile]]()
var tilesByTopAndLeftBorder = initTable[string, seq[Tile]]()

let tileIdRegex = re(r"^Tile (\d+):$")
var tileIdMatch: array[1, string]

var tilesNumber = (input.len() / 12).toInt()
for tileIndex in countup(0, tilesNumber - 1):
  if input[tileIndex * 12].match(tileIdRegex, tileIdMatch):
    let tileId = tileIdMatch[0].parseInt()
    var pixels = initHashSet[int]()
    for lineIndex in countup(0, 9):
      let line = input[tileIndex * 12 + lineIndex + 1]
      for pixelIndex, pixel in line:
        case pixel:
        of '#':
          pixels.incl(lineIndex * 10 + pixelIndex)
        of '.':
          discard
        else:
          raise newException(ValueError, "Unknown value [" & pixel & "]")
    for position, border in initTile(pixels):
      let topBorder = border[0]
      let leftBorder = border[3]
      let leftTopBorder = $topBorder & "x" & $leftBorder
      let tile = Tile(id: tileId, bottomBorder: border[2],
          rightBorder: border[1], position: position)
      allTiles.add(tile)

      if tilesByTopBorder.hasKeyOrPut(topBorder, @[tile]):
        tilesByTopBorder[topBorder].add(tile)

      if tilesByLeftBorder.hasKeyOrPut(leftBorder, @[tile]):
        tilesByLeftBorder[leftBorder].add(tile)

      if tilesByTopAndLeftBorder.hasKeyOrPut(leftTopBorder, @[tile]):
        tilesByTopAndLeftBorder[leftTopBorder].add(tile)
    tilesContents[tileId] = input[(tileIndex * 12 + 1) .. (tileIndex * 12 + 10)]
  else:
    raise newException(ValueError, "Unknown operation [" & input[tileIndex *
        12] & "]")

let photoLength = tilesNumber.toFloat.sqrt().toInt()

proc exploreSolutions(tiles: seq[Tile])

proc tileContentAt(tileContent: seq[string], line: int, column: int,
    position: int): char =
  case position:
    of 0:
      tileContent[line][column]
    of 1:
      tileContent[9 - column][line]
    of 2:
      tileContent[9 - line][9 - column]
    of 3:
      tileContent[column][9 - line]
    of 4:
      tileContent[line][9 - column]
    of 5:
      tileContent[9 - column][9 - line]
    of 6:
      tileContent[9 - line][column]
    of 7:
      tileContent[column][line]
    else:
      raise newException(ValueError, "Unknown position [" & $position & "]")

proc printResult(tiles: seq[Tile]) =
  for line in countup(0, photoLength - 1):
    echo(tiles[(line * photoLength) .. ((line + 1) * photoLength -
        1)].map(proc (t: Tile): string = $t.id & " (" & $t.position & ")").join(" "))
  var resultDisplay: seq[string] = @[]
  for i in countup(0, (11 * photoLength) - 1):
    resultDisplay.add(' '.repeat((11 * photoLength) - 1))

  for lineGroup in countup(0, photoLength - 1):
    for columnGroup in countup(0, photoLength - 1):
      let tile = tiles[(lineGroup * photoLength) + columnGroup]
      let tileContent: seq[string] = tilesContents[tile.id]
      for line in countup(0, 9):
        let resultLine = (11 * lineGroup) + line
        let resultColumn = (11 * columnGroup)
        for column in countup(0, 9):
          resultDisplay[resultLine][resultColumn + column] = tileContentAt(
              tileContent, line, column, tile.position)
  for line in resultDisplay:
    echo(line)
  quit()

proc exploreNext(tiles: seq[Tile], tile: Tile) =
  if not tiles.any(proc (t: Tile): bool = t.id == tile.id):
    var newTiles = tiles
    newTiles.add(tile)
    if newTiles.len() == tilesNumber:
      printResult(newTiles)
    else:
      exploreSolutions(newTiles)

proc exploreSolutions(tiles: seq[Tile]) =
  let tileNumber = tiles.len()
  var firstColumn = tileNumber.mod(photoLength) == 0
  var firstLine = tileNumber < photoLength
  if firstLine:
    if firstColumn:
      for tile in allTiles:
        exploreSolutions(@[tile])
    else:
      let previousRight = tiles[tileNumber - 1].rightBorder
      for tile in tilesByLeftBorder.getOrDefault(previousRight, @[]):
        exploreNext(tiles, tile)
  else:
    if firstColumn:
      let previousBottom = tiles[tileNumber - photoLength].bottomBorder
      for tile in tilesByTopBorder.getOrDefault(previousBottom, @[]):
        exploreNext(tiles, tile)
    else:
      let previousBottom = tiles[tileNumber - photoLength].bottomBorder
      let previousRight = tiles[tileNumber - 1].rightBorder
      let bottomRightKey = $previousBottom & "x" & $previousRight
      for tile in tilesByTopAndLeftBorder.getOrDefault(
          bottomRightKey, @[]):
        exploreNext(tiles, tile)

exploreSolutions(@[])

Part two

day202.nim
import strutils
import sequtils
import os

var input: seq[string] = readFile(paramStr(1)).splitLines()
var photoLength = (input.len() / 11).toInt()

var picture: seq[string] = @[]
for pictureLineIndex in countup(0, photoLength - 1):
  for lineIndex in countup(0, 7):
    var sourceLine: int
    if pictureLineIndex == 0:
      sourceLine = lineIndex + 1
    else:
      sourceLine = (pictureLineIndex * 11) + 1 + lineIndex

    var currentLine = ' '.repeat(8 * photoLength)

    for pictureColumnIndex in countup(0, photoLength - 1):
      for columnIndex in countup(0, 7):
        var sourceColumn: int
        if pictureColumnIndex == 0:
          sourceColumn = columnIndex + 1
        else:
          sourceColumn = (pictureColumnIndex * 11) + 1 + columnIndex
        currentLine[(8 * pictureColumnIndex) + columnIndex] = input[sourceLine][sourceColumn]
    picture.add(currentLine)
echo(picture.join("\n"))

const seaMonster = """                  #
#    ##    ##    ###
 #  #  #  #  #  #   """.split("\n")

echo("")

proc paintSeaMonster(picture: var seq[string], pictureLineIndex: int,
    pictureColumnIndex: int) =
  for monsterLineIndex in countup(0, seaMonster.len() - 1):
    for monsterColumnIndex in countup(0, seaMonster[0].len() - 1):
      if (seaMonster[monsterLineIndex][monsterColumnIndex] == '#'):
        picture[pictureLineIndex + monsterLineIndex][pictureColumnIndex +
          monsterColumnIndex] = 'O'

proc checkSeaMonster(picture: seq[string], pictureLineIndex: int,
    pictureColumnIndex: int): bool =
  for monsterLineIndex in countup(0, seaMonster.len() - 1):
    for monsterColumnIndex in countup(0, seaMonster[0].len() - 1):
      if (seaMonster[monsterLineIndex][monsterColumnIndex] == '#') and (
          picture[pictureLineIndex + monsterLineIndex][pictureColumnIndex +
          monsterColumnIndex] == '.'):
        return false
  return true

proc tileContentAt(picture: seq[string], line: int, column: int,
    position: int): char =
  case position:
    of 0:
      picture[line][column]
    of 1:
      picture[picture.len() - 1 - column][line]
    of 2:
      picture[picture.len() - 1 - line][picture.len() - 1 - column]
    of 3:
      picture[column][picture.len() - 1 - line]
    of 4:
      picture[line][picture.len() - 1 - column]
    of 5:
      picture[picture.len() - 1 - column][picture.len() - 1 - line]
    of 6:
      picture[picture.len() - 1 - line][column]
    of 7:
      picture[column][line]
    else:
      raise newException(ValueError, "Unknown position [" & $position & "]")

for position in countup(0, 7):
  var positionedPicture: seq[string] = @[]
  for lineIndex in countup(0, picture.len() - 1):
    var positionedPictureLine = ' '.repeat(picture.len())
    for columnIndex in countup(0, picture.len() - 1):
      positionedPictureLine[columnIndex] = tileContentAt(picture, lineIndex,
          columnIndex, position)
    positionedPicture.add(positionedPictureLine)

  var monsterFound = false
  for pictureLineIndex in countup(0, picture.len() - seaMonster.len()):
    for pictureColumnIndex in countup(0, picture[0].len() - seaMonster[0].len()):
      if checkSeaMonster(positionedPicture, pictureLineIndex,
          pictureColumnIndex):
        monsterFound = true
        paintSeaMonster(positionedPicture, pictureLineIndex, pictureColumnIndex)
        echo("Found monster at (", pictureLineIndex, ", ", pictureColumnIndex, ")")
  if monsterFound:
    echo(positionedPicture.join("\n"))
    var hashes = positionedPicture.map(proc (l: string): int = l.count(
        '#')).foldl(a + b)
    echo(hashes)
    quit()

Day 21

Part one

day211.nim
import strutils
import os
import re
import tables
import sets
import math
import algorithm
import sequtils

type
  Recipe = ref object
    ingredients: HashSet[string]
    allergens: HashSet[string]

var recipes: seq[Recipe] = @[]

let recipeRegex = re(r"^(.+) \(contains (.+)\)$")

var allAllergens = initHashSet[string]()
var allIngredients = initHashSet[string]()

var recipeMatch: array[2, string]
for currentLine in readFile(paramStr(1)).splitLines():
  if currentLine.match(recipeRegex, recipeMatch):
    let allergens = recipeMatch[1].split(", ")
    for allergen in allergens:
      allAllergens.incl(allergen)
    let ingredients = recipeMatch[0].split(" ")
    for ingredient in ingredients:
      allIngredients.incl(ingredient)
    recipes.add(Recipe(ingredients: ingredients.toHashSet(),
        allergens: allergens.toHashSet()))
  else:
    raise newException(ValueError, "Can't parse [" & currentLine & "]")

var possibleIngredientsForAllergens = initTable[string, HashSet[string]]()

for allergen in allAllergens:
  var possibleIngredientsForAllergen = allIngredients
  for recipe in recipes:
    if recipe.allergens.contains(allergen):
      possibleIngredientsForAllergen = possibleIngredientsForAllergen.intersection(
          recipe.ingredients)
  possibleIngredientsForAllergens[allergen] = possibleIngredientsForAllergen

var foundIngredient = true
while foundIngredient:
  foundIngredient = false
  for allergen, possibleIngredients in possibleIngredientsForAllergens:
    if possibleIngredients.len() == 1:
      let ingredient = possibleIngredients.toSeq()[0]
      foundIngredient = true
      allAllergens.excl(allergen)
      allIngredients.excl(ingredient)
      possibleIngredientsForAllergens.del(allergen)
      for recipe in recipes:
        recipe.ingredients.excl(ingredient)
        recipe.allergens.excl(allergen)
      for a, i in possibleIngredientsForAllergens:
        if i.contains(ingredient):
          var iWithoutIngredient = i
          iWithoutIngredient.excl(ingredient)
          possibleIngredientsForAllergens[a] = iWithoutIngredient
      break

var ingredientsCount = 0
for currentLine in readFile(paramStr(1)).splitLines():
  if currentLine.match(recipeRegex, recipeMatch):
    let ingredients = recipeMatch[0].split(" ")
    for ingredient in ingredients:
      if allIngredients.contains(ingredient):
        ingredientsCount += 1
  else:
    raise newException(ValueError, "Can't parse [" & currentLine & "]")
echo(ingredientsCount)

Part two

day212.nim
import strutils
import os
import re
import tables
import sets
import algorithm
import sequtils

type
  Recipe = ref object
    ingredients: HashSet[string]
    allergens: HashSet[string]

var recipes: seq[Recipe] = @[]

let recipeRegex = re(r"^(.+) \(contains (.+)\)$")

var allAllergens = initHashSet[string]()
var allIngredients = initHashSet[string]()

var recipeMatch: array[2, string]
for currentLine in readFile(paramStr(1)).splitLines():
  if currentLine.match(recipeRegex, recipeMatch):
    let allergens = recipeMatch[1].split(", ")
    for allergen in allergens:
      allAllergens.incl(allergen)
    let ingredients = recipeMatch[0].split(" ")
    for ingredient in ingredients:
      allIngredients.incl(ingredient)
    recipes.add(Recipe(ingredients: ingredients.toHashSet(),
        allergens: allergens.toHashSet()))
  else:
    raise newException(ValueError, "Can't parse [" & currentLine & "]")

var possibleIngredientsForAllergens = initTable[string, HashSet[string]]()

for allergen in allAllergens:
  var possibleIngredientsForAllergen = allIngredients
  for recipe in recipes:
    if recipe.allergens.contains(allergen):
      possibleIngredientsForAllergen = possibleIngredientsForAllergen.intersection(
          recipe.ingredients)
  possibleIngredientsForAllergens[allergen] = possibleIngredientsForAllergen

var ingredientByAllergen = initTable[string, string]()

var foundIngredient = true
while foundIngredient:
  foundIngredient = false
  for allergen, possibleIngredients in possibleIngredientsForAllergens:
    if possibleIngredients.len() == 1:
      let ingredient = possibleIngredients.toSeq()[0]
      ingredientByAllergen[allergen] = ingredient
      foundIngredient = true
      allAllergens.excl(allergen)
      allIngredients.excl(ingredient)
      possibleIngredientsForAllergens.del(allergen)
      for recipe in recipes:
        recipe.ingredients.excl(ingredient)
        recipe.allergens.excl(allergen)
      for a, i in possibleIngredientsForAllergens:
        if i.contains(ingredient):
          var iWithoutIngredient = i
          iWithoutIngredient.excl(ingredient)
          possibleIngredientsForAllergens[a] = iWithoutIngredient
      break

var alergens: seq[string] = toSeq(ingredientByAllergen.keys)
alergens.sort()
echo(alergens.map(proc(a: string): string = ingredientByAllergen[a]).join(","))

Day 22

Part one

day221.nim
import strutils
import os

var player1Deck: seq[int] = @[]
var player2Deck: seq[int] = @[]

var input: seq[string] = readFile(paramStr(1)).splitLines()

var lineIndex = 1
while input[lineIndex] != "":
  player1Deck.add(input[lineIndex].parseInt())
  lineIndex += 1

lineIndex += 2

while lineIndex < input.len():
  player2Deck.add(input[lineIndex].parseInt())
  lineIndex += 1

while (player1Deck.len() != 0) and (player2Deck.len() != 0):
  let player1Card = player1Deck[0]
  player1Deck.delete(0)
  let player2Card = player2Deck[0]
  player2Deck.delete(0)
  if player1Card > player2Card:
    player1Deck.add([player1Card, player2Card])
  elif player2Card > player1Card:
    player2Deck.add([player2Card, player1Card])
  else:
    raise newException(ValueError, "Both players have a [" & $player1Card & "]")

var score = 0
for cardIndex in countup(1, player1Deck.len()):
  score += cardIndex * player1Deck[ ^ cardIndex]
for cardIndex in countup(1, player2Deck.len()):
  score += cardIndex * player2Deck[ ^ cardIndex]
echo(score)

Part two

day222.nim
import strutils
import os
import sets

var player1Deck: seq[int] = @[]
var player2Deck: seq[int] = @[]

var input: seq[string] = readFile(paramStr(1)).splitLines()

var lineIndex = 1
while input[lineIndex] != "":
  player1Deck.add(input[lineIndex].parseInt())
  lineIndex += 1

lineIndex += 2

while lineIndex < input.len():
  player2Deck.add(input[lineIndex].parseInt())
  lineIndex += 1

proc calculateScore(player1Deck: seq[int], player2Deck: seq[int]) =
  var score = 0
  for cardIndex in countup(1, player1Deck.len()):
    score += cardIndex * player1Deck[ ^ cardIndex]
  for cardIndex in countup(1, player2Deck.len()):
    score += cardIndex * player2Deck[ ^ cardIndex]
  echo(score)

proc playCombat(player1Deck: seq[int], player2Deck: seq[int], depth: int): int =
  var player1Deck = player1Deck
  var player2Deck = player2Deck
  var playedDecks = initHashSet[string]()
  while true:
    if playedDecks.containsOrIncl($player1Deck & $player2Deck):
      if depth == 1:
        calculateScore(player1Deck, player2Deck)
      return 1
    let player1Card = player1Deck[0]
    player1Deck.delete(0)
    let player2Card = player2Deck[0]
    player2Deck.delete(0)

    var winner: int
    if (player1Deck.len() >= player1Card) and (player2Deck.len() >= player2Card):
      winner = playCombat(player1Deck[0 .. player1Card - 1], player2Deck[0 ..
          player2Card - 1], depth + 1)
    else:
      if player1Card > player2Card:
        winner = 1
      elif player2Card > player1Card:
        winner = 2
      else:
        raise newException(ValueError, "Both players have a [" &
            $player1Card & "]")
    if winner == 1:
      player1Deck.add([player1Card, player2Card])
    elif winner == 2:
      player2Deck.add([player2Card, player1Card])
    else:
      raise newException(ValueError, "Unknown player " & $winner)
    if (player1Deck.len() == 0) or (player2Deck.len() == 0):
      if depth == 1:
        calculateScore(player1Deck, player2Deck)
      return winner

discard playCombat(player1Deck, player2Deck, 1)

Day 23

Part one

day231.nim
import strutils
import os
import sequtils

var cups: seq[int] = readFile(paramStr(1)).map(proc(s: char): int = (
    $s).parseInt())
var currentCupIndex = 0

for currentTurn in countup(1, 100):
  var pickedUpCups: seq[int] = @[]
  for pickedUpCupsIndex in countup(1, 3):
    if currentCupIndex == cups.len() - 1:
      pickedUpCups.add(cups[0])
      cups.delete(0)
      currentCupIndex -= 1
    else:
      pickedUpCups.add(cups[currentCupIndex + 1])
      cups.delete(currentCupIndex + 1)
  var destinationCupLabel = cups[currentCupIndex] - 1
  while not cups.contains(destinationCupLabel):
    destinationCupLabel -= 1
    if destinationCupLabel < 0:
      destinationCupLabel = cups.max()
  let destinationIndex = cups.find(destinationCupLabel)
  cups.insert(pickedUpCups, destinationIndex + 1)
  if destinationIndex < currentCupIndex:
    currentCupIndex += pickedUpCups.len()
  currentCupIndex += 1
  if currentCupIndex >= cups.len():
    currentCupIndex -= cups.len()

let index1 = cups.find(1)
var finalLabels = ""
if index1 != cups.len() - 1:
  finalLabels &= cups[index1 + 1 .. cups.len() - 1].map(proc(s: int): string = (
      $s)).join("")
if index1 != 0:
  finalLabels &= cups[0 .. index1 - 1].map(proc(s: int): string = ($s)).join("")
echo(finalLabels)

Part two

day232.nim
import strutils
import os
import sequtils
import lists
import tables

var initialCups: seq[int] = readFile(paramStr(1)).map(proc(s: char): int = (
    $s).parseInt())

var maxCupNumber = 0
var cupsRing = initSinglyLinkedRing[int]()
var nodesByValue = initTable[int, SinglyLinkedNode[int]]()
for cupValue in initialCups:
  let node = newSinglyLinkedNode[int](cupValue)
  cupsRing.append(node)
  nodesByValue[cupValue] = node
  if cupValue > maxCupNumber:
    maxCupNumber = cupValue

for cupValue in (maxCupNumber + 1 .. 1_000_000):
  let node = newSinglyLinkedNode[int](cupValue)
  cupsRing.append(node)
  nodesByValue[cupValue] = node

maxCupNumber = 1_000_000

var currentCup: SinglyLinkedNode[int] = cupsRing.head
for currentTurn in countup(1, 10000000):
  let pickedOne = currentCup.next
  let pickedTwo = pickedOne.next
  let pickedThree = pickedTwo.next

  currentCup.next = pickedThree.next

  var foundDestination = false
  var label = currentCup.value - 1
  while not foundDestination:
    if label == 0:
      label = maxCupNumber
    if (pickedOne.value == label) or (pickedTwo.value == label) or (
        pickedThree.value == label):
      label -= 1
    else:
      foundDestination = true
  let destinationCup = nodesByValue[label]
  pickedThree.next = destinationCup.next
  destinationCup.next = pickedOne
  currentCup = currentCup.next

echo(nodesByValue[1].next.value * nodesByValue[1].next.next.value)

Day 24

Part one

day241.nim
import strutils
import os
import sequtils
import tables
import sets

var input: seq[string] = readFile(paramStr(1)).splitLines()

proc decreaseMovement(path: TableRef[string, int], movement: string, value: int) =
  if path[movement] == value:
    path.del(movement)
  else:
    path[movement] -= value

proc removeCircles(path: TableRef[string, int], directions: seq[string]): bool =
  if directions.all(proc(direction: string): bool = path.hasKey(direction)):
    let value: int = directions.map(proc(direction: string): int = path[
        direction]).min()
    for direction in directions:
      decreaseMovement(path, direction, value)
    true
  else:
    false

proc simplifyDirections(path: TableRef[string, int], direction1: string,
    direction2: string, equivalentDirection: string): bool =
  if path.hasKey(direction1) and path.hasKey(direction2):
    let value: int = [path[direction1], path[direction2]].min()
    decreaseMovement(path, direction1, value)
    decreaseMovement(path, direction2, value)
    if path.hasKey(equivalentDirection):
      path[equivalentDirection] += value
    else:
      path[equivalentDirection] = value
    true
  else:
    false

var pathes: HashSet[string] = initHashSet[string]()

for line in input:
  var tile = newTable[string, int]()
  var cursorIndex = 0
  while cursorIndex < line.len():
    var currentDirection: string
    if (line[cursorIndex] == 'n') or (line[cursorIndex] == 's'):
      currentDirection = line[cursorIndex .. cursorIndex + 1]
      cursorIndex += 2
    else:
      currentDirection = line[cursorIndex .. cursorIndex]
      cursorIndex += 1
    if tile.hasKeyOrPut(currentDirection, 1):
      tile[currentDirection] += 1

  var s = true
  while(s):
    s = simplifyDirections(tile, "ne", "se", "e")
    s = s or simplifyDirections(tile, "nw", "sw", "w")
    s = s or simplifyDirections(tile, "se", "ne", "e")
    s = s or simplifyDirections(tile, "sw", "nw", "w")

    s = s or simplifyDirections(tile, "se", "w", "sw")
    s = s or simplifyDirections(tile, "sw", "e", "se")
    s = s or simplifyDirections(tile, "ne", "w", "nw")
    s = s or simplifyDirections(tile, "nw", "e", "ne")

    s = s or removeCircles(tile, @["e", "w"])
    s = s or removeCircles(tile, @["se", "nw"])
    s = s or removeCircles(tile, @["ne", "sw"])
  var path = ["e", "w", "se", "sw", "ne", "nw"].map(proc(
      direction: string): string = $ tile.getOrDefault(direction, 0)).join(",")
  if pathes.contains(path):
    pathes.excl(path)
  else:
    pathes.incl(path)
echo(pathes.len())

Part two

day242.nim
import strutils
import os
import sequtils
import sets
import hashes

type Direction = enum
  east, southeast, southwest, west, northwest, northeast

type
  Path = ref object
    elements: seq[int]
proc hash(path: Path): Hash =
  var h: Hash = 0
  h = h !& hash(path.elements)
  result = !$h
proc `==`(a, b: Path): bool =
  a.elements == b.elements

proc removeCircles(path: Path, directions: seq[Direction]): bool =
  let value: int = directions.map(proc(direction: Direction): int = path.elements[
      direction.ord]).min()
  if value > 0:
    for direction in directions:
      path.elements[direction.ord] -= value
    true
  else:
    false

proc simplifyDirections(path: Path, direction1: Direction,
    direction2: Direction, equivalentDirection: Direction): bool =
  let value: int = [path.elements[direction1.ord], path.elements[
      direction2.ord]].min()
  if value > 0:
    path.elements[direction1.ord] -= value
    path.elements[direction2.ord] -= value
    path.elements[equivalentDirection.ord] += value
    true
  else:
    false

proc simplify(path: Path) =
  var s = true
  while(s):
    s = path.simplifyDirections(Direction.northeast, Direction.southeast,
        Direction.east)
    s = s or path.simplifyDirections(Direction.northwest, Direction.southwest,
        Direction.west)
    s = s or path.simplifyDirections(Direction.southeast, Direction.northeast,
        Direction.east)
    s = s or path.simplifyDirections(Direction.southwest, Direction.northwest,
        Direction.west)

    s = s or path.simplifyDirections(Direction.southeast, Direction.west,
        Direction.southwest)
    s = s or path.simplifyDirections(Direction.southwest, Direction.east,
        Direction.southeast)
    s = s or path.simplifyDirections(Direction.northeast, Direction.west,
        Direction.northwest)
    s = s or path.simplifyDirections(Direction.northwest, Direction.east,
        Direction.northeast)

    s = s or path.removeCircles(@[Direction.east, Direction.west])
    s = s or path.removeCircles(@[Direction.southeast, Direction.northwest])
    s = s or path.removeCircles(@[Direction.northeast, Direction.southwest])

proc toDirection(s: string): Direction =
  case s:
    of "e":
      Direction.east
    of "se":
      Direction.southeast
    of "sw":
      Direction.southwest
    of "w":
      Direction.west
    of "nw":
      Direction.northwest
    of "ne":
      Direction.northeast
    else:
      raise newException(ValueError, "Unknown value [" & s & "]")

var input: seq[string] = readFile(paramStr(1)).splitLines()

var pathes: HashSet[Path] = initHashSet[Path]()

for line in input:
  var path = Path(elements: newSeq[int](Direction.high.ord + 1))
  var cursorIndex = 0
  while cursorIndex < line.len():
    var currentDirection: string
    if (line[cursorIndex] == 'n') or (line[cursorIndex] == 's'):
      currentDirection = line[cursorIndex .. cursorIndex + 1]
      cursorIndex += 2
    else:
      currentDirection = line[cursorIndex .. cursorIndex]
      cursorIndex += 1
    path.elements[currentDirection.toDirection().ord] += 1
  path.simplify()

  if pathes.contains(path):
    pathes.excl(path)
  else:
    pathes.incl(path)

proc createPath(path: Path, direction: Direction): Path =
  var newPath = Path(elements: path.elements)
  newPath.elements[direction.ord] += 1
  newPath.simplify()
  newPath

proc neighbour(path: Path, direction: Direction, pathes: HashSet[Path]): bool =
  pathes.contains(createPath(path, direction))

proc neighbours(path: Path, pathes: HashSet[Path]): int =
  toSeq(Direction).filter(proc(direction: Direction): bool = neighbour(path,
      direction, pathes)).len()

for day in countup(1, 100):
  var newPathes: HashSet[Path] = initHashSet[Path]()
  var processedPathes: HashSet[Path] = initHashSet[Path]()
  for path in pathes:
    let n1 = neighbours(path, pathes)
    if (n1 == 1) or (n1 == 2):
      newPathes.incl(path)
    else:
      discard
    processedPathes.incl(path)
  for path in pathes:
    for direction in Direction:
      var newPath = createPath(path, direction)
      if not processedPathes.containsOrIncl(newPath):
        let n2 = neighbours(newPath, pathes)
        if n2 == 2:
          newPathes.incl(newPath)
  echo("Day ", day, " ", newPathes.len())
  pathes = newPathes

Day 25

Part one

day251.nim
import strutils
import os
import tables

var cardPublicKey: int = paramStr(1).parseInt()
var doorPublicKey: int = paramStr(2).parseInt()

var tranformationsResults = initTable[int, int]()

proc calculateLoopSize(publicKey: int): int =
  var loopIndex = 0
  var currentValue = 1
  while true:
    loopIndex += 1
    if tranformationsResults.hasKey(loopIndex):
      currentValue = tranformationsResults[loopIndex]
    else:
      currentValue = (currentValue * 7).mod(20201227)
      tranformationsResults[loopIndex] = currentValue
    if currentValue == publicKey:
      return loopIndex

proc transform(subjectNumber: int, times: int): int =
  var currentValue = 1
  for loopIndex in countup(0, times - 1):
    currentValue = (currentValue * subjectNumber).mod(20201227)
  currentValue

var cardLoopSize = calculateLoopSize(cardPublicKey)
var doorLoopSize = calculateLoopSize(doorPublicKey)
echo("cardLoopSize ", cardLoopSize)
echo("doorLoopSize ", doorLoopSize)

var cardEncryptionKey = transform(doorPublicKey, cardLoopSize)
var doorEncryptionKey = transform(cardPublicKey, doorLoopSize)
echo("cardEncryptionKey ", cardEncryptionKey)
echo("doorEncryptionKey ", doorEncryptionKey)