Advent of Code - adventofcode.com

Doing them in Go this year (first time round, rather than Perl first and Go second).

Goal is to keep up as long as I can until I run out of time and it starts to impinge on job. (Usually somewhere around day 17 Eric chucks a stinker in there that takes more than an hour.) From here I'll try and finish them all as close to Day 25 as I can, but usually I get the final stars sometime between then and Jan 1.

Second goal is to have each day run in under 1s elapsed (on my relatively quick laptop).

Third, eventual, goal is to have all days run in under 1s elapsed in total. Have done this for one year but not all.

(Another goal is to get my repo of solutions sorted out and timed properly with a good summary/totals page so I can see my progress for this last one. I've also not done all of the years in Go, and going back and doing that will definitely be a good learning exercise.)

Day 1 in Go: https://gist.github.com/alexgreenbank/19f63ed9c29316aefb1171bc558b8606

(No point tweaking that any further, runs in the lowest time I can reliably time and would be easier to extend to handle n highest rather than 3, etc.)

Doing it in Python again. Would've liked to try something new but realistically don't have time.

Day 1 done. Python here too. Been writing a lot of JS recently and have completely forgotten the syntax for most built-in functions.

Started writing conditionals today but quickly chose paper (heh) and figured it out all the scores by hand.

Yeah, I just smashed the input strings into a map, e.g.

        p1poss := map[string]int{
                "A X": 1 + 3, "A Y": 2 + 6, "A Z": 3 + 0,
                "B X": 1 + 0, "B Y": 2 + 3, "B Z": 3 + 6,
                "C X": 1 + 6, "C Y": 2 + 0, "C Z": 3 + 3,
        }

Didn't even have to parse/split the incoming string.

I thought about make a map of possibilities, ended up doing this:

def part2(game: list[str, str]) -> int:
    offset = ord("A")
    score_dict = {
        "X": ((ord(game[0]) - offset - 1) % 3) + 1,
        "Y": ord(game[0]) - offset + 4,
        "Z": ((ord(game[0]) - offset + 1) % 3) + 7,
    }
    return score_dict[game[1]]

Probably less readable overall though

Yeah, I prefer readability over code golf.

Here we go again, day 1 in jsonnet: https://github.com/rhowe/aoc/tree/main/2022/01

Day 4 getting us looking forward to geometry (which I do not look forward to)

local input = std.rstripChars(importstr 'input', '\n');

local sum = function(a, b) a + b;
local sumarray = function(arr) std.foldl(sum, arr, 0);
local splitlines = function(str) std.split(str, '\n');
local splitcsv = function(str) std.split(str, ',');
local splitrange = function(str) std.map(std.parseInt, std.split(str, '-'));

local is_pair_overlapping(pairs) =
  local p1_l = pairs[0][0];
  local p1_r = pairs[0][1];
  local p2_l = pairs[1][0];
  local p2_r = pairs[1][1];
  (p1_l <= p2_r && p1_r >= p2_l)
  || (p2_l <= p1_r && p2_r >= p1_l)
;

std.length(std.filter(is_pair_overlapping, std.map(function(line) std.map(splitrange, splitcsv(line)), splitlines(input))))

Caught up on day 3 and 4. Used sets for both.

Back to solving using Scala as it's the language I'm most comfortable with. Only using versions 2.12.* and 2.13.* in work projects, so it's nice to try the new version 3 features (particularly those relating to syntax). Making use of a test framework to run/split up scenarios rather than writing scripts/apps for each day so that I have everything just in one file and don't faff.

Got that usual feeling of a false sense of security when completing the last few days in a short space of time. Will hopefully have the willpower to keep going when things start taking more than 30 minutes to solve.

Day 4:

  "Day 4" - {
    case class Section(begin: Int, end: Int)

    def getElfPairs(assignmentInput: String): (Section, Section) =
      assignmentInput.split(",") match
        case Array(first, second) =>
          val Array(beginFirst, endFirst)   = first.split("-")
          val Array(beginSecond, endSecond) = second.split("-")
          (Section(beginFirst.toInt, endFirst.toInt), Section(beginSecond.toInt, endSecond.toInt))

    object PartA:
      def sectionContainsOther(thisSection: Section, thatSection: Section): Boolean =
        (thisSection.begin <= thatSection.begin && thisSection.end >= thatSection.end)
        ||
        (thatSection.begin <= thisSection.begin && thatSection.end >= thisSection.end)

    object PartB:
      def sectionOverlapsOther(thisSection: Section, thatSection: Section): Boolean =
        !((thisSection.end < thatSection.begin) || (thatSection.end < thisSection.begin))

    "sample part a" in:
      linesFor(Day.`4`, Input.sample, Part.a).use: lines =>
        IO.println(lines.map(getElfPairs).filter(PartA.sectionContainsOther).size)

    "part a" in:
      linesFor(Day.`4`, Input.real, Part.a).use: lines =>
        IO.println(lines.map(getElfPairs).filter(PartA.sectionContainsOther).size)

    "sample part b" in:
      linesFor(Day.`4`, Input.sample, Part.b).use: lines =>
        IO.println(lines.map(getElfPairs).filter(PartB.sectionOverlapsOther).size)

    "part b" in:
      linesFor(Day.`4`, Input.real, Part.b).use: lines =>
        IO.println(lines.map(getElfPairs).filter(PartB.sectionOverlapsOther).size)
  }

Part of the fun is seeing how other people approach each day.

Also seeing what people use as their measure of "done".

For some it is just a case of getting both stars and moving on to the next problem, but many are only happy when they have something that is relatively optimal in terms of CPU and/or memory (some times it's impossible to do both).

I have everything just in one file

Haven't done this for any of the previous years but I'm tempted to do this at the end, partly because it will make timing the entire run of the year much easier.

I mostly used emoji for day 2

I guess you could say it's Advent of Unicode

Haha, nice.

I tried to do something like this once in C++. You can use an emoji as a variable name or a function name. It'll compile but I think it shat the bed when you try to actually run it

Today's was one of those ones where making a nice generic function to parse the input is vastly slower than just manually pasting it in

Parser wasn't too bad, logic is going to be a pain for me: https://github.com/rhowe/aoc/blob/main/2022/05-supply-stacks/05part1.jsonnet

(logic not implemented at time of posting)

Also seeing what people use as their measure of "done".

Agreed - that's what I'm often most interested in when viewing how others approach the problem.

If my immediate approach to getting the answer is suboptimal - especially when compared to other clean, but efficient methods written by others - then I'll make a mental note of that better approach and take it with me to the next problem. I've found from previous years that if I'm too caught up in worrying about writing 'imperfect' solutions then I'll not get anything done, so I figure at least getting something which is not horrifically slow should suffice.

I figured I'd do a little bit of input modification for today's solution so that I didn't spend more than a few minutes on some regex which would invariably fail:

Lesson learned from today is to always verify my output from parsing before moving on to writing the solver. Was a right pain when I realised my initial parsing approach resulted in a shifted crate.

Day 5 solution (tried keeping this hidden/collapsible but well formatted and failing):

  "Day 5" - {

    enum CraneMoverModel:
      case `9000`, `9001`

    case class Instruction(from: Int, to: Int, number: Int)

    val crateRegex = """\[([A-Z-])\]""".r
    val instructionRegex = """^move\s(\d+)\sfrom\s(\d+)\sto\s(\d+)$""".r

    def gatherInstructions(instructionsInput: String): Array[Instruction] =
      instructionsInput.split("\\n").map {
        case instructionRegex(number, from, to) => Instruction(from.toInt, to.toInt, number.toInt)
      }

    def gatherCrates(cratesInput: String): Map[Int, Array[Char]] =
      cratesInput.split("\\n")
        .map: crate =>
          crateRegex.findAllMatchIn(crate).map(_.group(1)).toArray
        .transpose
        .map: crates =>
          crates
            .reverse
            .filterNot(_ == "-") // input blank crates have been changed to hyphens for convenience
            .map(_.charAt(0))
        .zipWithIndex.map { (crateArray, idx) =>
          (idx + 1, crateArray)
        }.toMap

    /*
        Following modifications made to input:
          - stack number line removed
          - empty crates have been relabelled as [-]
    */
    def parseInput(input: String): (Array[Instruction], Map[Int, Array[Char]]) =
      val Array(crateInfo, instructionInfo) = input.split("\\n\\n")
      (gatherInstructions(instructionInfo), gatherCrates(crateInfo))
      
    def solve(input: String, craneMoverModel: CraneMoverModel): String =
      val (instructions, cratesMap) = parseInput(input)
      val result = instructions.foldLeft(cratesMap) { (currentCrates, instruction) =>
        val from        = currentCrates(instruction.from)
        val to          = currentCrates(instruction.to)
        val valuesToAdd = from.takeRight(instruction.number)
        val add         = craneMoverModel match
          case CraneMoverModel.`9000` => valuesToAdd.reverse
          case CraneMoverModel.`9001` => valuesToAdd
        currentCrates
          .updated(instruction.from, from.dropRight(instruction.number))
          .updated(instruction.to, to ++: add)
      }
      result
        .toArray
        .sortBy: (idx, _) =>
          idx
        .flatMap: (_, crates) =>
          crates.lastOption
        .mkString

    "sample part a" in:
      inputStringFor(Day.`5`, Input.sample, Part.a).use: input =>
        IO.println(solve(input, CraneMoverModel.`9000`))

    "part a" in :
      inputStringFor(Day.`5`, Input.real, Part.a).use: input =>
        IO.println(solve(input, CraneMoverModel.`9000`))
    
    "sample part b" in:
      inputStringFor(Day.`5`, Input.sample, Part.b).use: input =>
        IO.println(solve(input, CraneMoverModel.`9001`))

    "part b" in :
      inputStringFor(Day.`5`, Input.real, Part.b).use: input =>
        IO.println(solve(input, CraneMoverModel.`9001`))  

  }

zip-based transpose is your friend:

stacks, moves = open("day05.input").read().split("\n\n")
moves = [tuple(map(int, move.split(" ")[1::2])) for move in moves.split("\n")]
stacks = [
    deque(filter(lambda x: x != " ", stack))
    for stack in islice(zip(*stacks.split("\n")[:-1]), 1, None, 4)
]

Nice. I also split on \n\n and reverse the lines that denote the crates, and after that it's not so bad. islice would've been handy, I need to dig into that itertools library at some point (although probably only for AOC purposes!)

The thing to note is that the "stack" part of the input has trailing whitespace, so you can go from line-by-line based input to column-based input with zip(*stacks.split("\n")), then it's just a question of picking out the bits you need.

jsonnet still, day 5:

local input = std.rstripChars(importstr 'input', '\n');

local lines = std.split(input, '\n');
local is_not_space = function(x) x != ' ';

local parsemove = function(move)
  local words = std.split(move, ' ');
  {
    from: words[3],
    to: words[5],
    qty: std.parseInt(words[1]),
  };

local stack = {
  items: [],
  pop:: function(x)
    local s = self;
    {
      values: s.items[0:x],
      stack: s {
        items: s.items[x:],
      },
    },
  push:: function(x)
    local curr = self.items;
    self {
      items: x + curr,
    },
};

{
  moves: [
    parsemove(line)
    for line in lines
    if std.length(line) > 0 && line[0] == 'm'
  ],
  stacks:
    local rows = [
      line
      for line in lines
      if std.length(line) > 0 && line[0] != 'm'
    ];
    local n_rows = std.length(rows);

    {
      [std.toString(col + 1)]:
        stack {
          items:
            std.filter(is_not_space, [
              row[col * 4 + 1]
              for row in rows[0:n_rows - 1]
            ]),
        }
      for col in std.range(0, std.length(rows[n_rows - 1]) / 4)
    },
  move(qty, from, to)::
    local src = self.stacks[from].pop(qty);
    local dest = self.stacks[to].push(src.values);
    self {
      stacks+: {
        [from]: src.stack,
        [to]: dest,
      },
    },
  do_moves()::
    std.foldl(function(acc, m) acc.move(m.qty, m.from, m.to), self.moves, self),
  get_message:: function()
    std.join('', [self.stacks[stack].pop(1).values[0] for stack in std.set(std.objectFields(self.stacks))]),
}.do_moves().get_message()

Another relatively simple one today. Still waiting for the first stinker...

It won't be long before I start looking at the leader board before starting to get an idea of how tricky it is.

local uniq = function(arr) std.length(arr) == std.length(std.set(arr));
local finduniqseq = function(arr, n) [
  uniq(arr[offset:offset + n])
  for offset in std.range(0, std.length(arr) - n)
];

std.find(true, finduniqseq(std.rstripChars(importstr 'input', '\n'), 14))[0] + 14

Always nice when solving part 2 involves changing a couple of numbers

Made the most of being woken up at 5.45am today.
Do like the ones where part 2 is the same as part 1, but makes you rewrite a naive/quick and dirty solution to part 1.

let n = 14
let i = 0
let found = false

while (!found) {
  if (new Set(str.slice(i, i + n)).size === n) {
    found = true
  } else {
    i++
  }
}

console.log(i + n)

Didn't use sets here, but enjoying reading the other approaches with that technique.

def findFirstMarker(input: String, distinctCount: Int): Int =
  @tailrec
  def markerIndexAtEndOfUniqueCharSequence(buffer: Array[Char], idx: Int = 0): Int =
    val current = input(idx)
    if (buffer.size == (distinctCount - 1) && !buffer.contains(current))
      idx
    else
      val (_, prunedBuffer) = buffer.splitAt(buffer.indexOf(current) + 1)
      markerIndexAtEndOfUniqueCharSequence(prunedBuffer :+ current, idx + 1)
  markerIndexAtEndOfUniqueCharSequence(Array.emptyCharArray, 0) + 1