Advent of Code

[vorsprung]

Advent of code 2023 has started.

Day 1

(click to show/hide)

My puzzle input has 16 instances of "oneight" and 16 instances of "eightwo"

and once again i can't be arsed with it

[Diver300]

Day 5

(click to show/hide)

The second part takes a lot of calculations if you don't use subtlety. My puzzle took 1.8 billion calculations with absolutely no subtlety, but in javascript that took 15 minutes or so, faster than I could work out a more sophisticated algorithm and program it.

[Pickled Onion]

Not wanting to wait 15 mins, I spent an hour writing a recursive split which spat out the answer in 15 seconds.

Thinking I might be descending the same tree multiple times, I added a cache but it only knocked off a second. There is probably a better way, but it seems OK for < 100 lines of C#.

[Diver300]

I decided that there had to be an elegant solution, and what I have now written, in far more than 15 minutes, runs in less than a second. It's not recursive.

(click to show/hide)

The seeds are in ranges. Each time a range of seeds has a line of a map applied to it, either or both ends of the seed range can be split off because they are outside the scope of the line of the map. Parts of seed ranges that are split off become new seed ranges so the number of ranges increases.

Seed ranges were marked as transformed by the map or not, to prevent more than one line of any one map being applied to any seed.

My input started with 10 ranges of seeds. I ended up with 45 ranges of seeds. There may have been overlap in these ranges, but I didn't care.

The code ran for each map
for each line of the map
for each range of seeds
The innermost loop runs 6449 times.

[Pickled Onion]

Yes, spotted the range thing later.

Day 6 was a bit easy

(click to show/hide)

It was pretty obvious from the start it was a normal distribution, so Part 2 ran quicker than Part 1 with no changes.


    public long Part1()
    {
        return Races.Select(x=> x.Ways()).Aggregate(1L, (x, y) => x * y);
    }
    public long Part2()
    {
        return Single!.Ways();
    }

[jwo]

Day 6:

(click to show/hide)

Pickled O: I'm not really familiar with C#. What does Select(x=> x.Ways()) do? And isn't the distribution quadratic rather than normal?

Here's my solution / explanation that finds the roots of the quadratic to find the lower and upper bounds of the record beating boats.

[Diver300]

Yes, spotted the range thing later.

Day 6 was a bit easy

(click to show/hide)

It was pretty obvious from the start it was a normal distribution, so Part 2 ran quicker than Part 1 with no changes.


    public long Part1()
    {
        return Races.Select(x=> x.Ways()).Aggregate(1L, (x, y) => x * y);
    }
    public long Part2()
    {
        return Single!.Ways();
    }

jwo posted while I was writing this.

(click to show/hide)

I don't think it was a normal distribution at all. It was a quadratic equation.
I found both solutions to each of four quadratic equations for part 1, and both solutions for one equation for part 2, admittedly with some large numbers.

In fact, a 3-cell spreadsheet can do the second part. The formulae are:-
=CEILING((A9-SQRT(A9^2-4*A10))/2;1)
=FLOOR((A9+SQRT(A9^2-4*A10))/2;1)
=A12-A11+1

A9 is the time
A10 is the distance
A11 is  the first formula
A12 is the second

[Pickled Onion]

Symmetric rather than Normal. So you only need to find the lower bound.

[Pickled Onion]

Pickled O: I'm not really familiar with C#. What does Select(x=> x.Ways()) do?

It's Linq - Select takes an enumeration of races, and for each one asks it how many ways can that race be won, returning an enumeration of those. Aggregate takes an enumeration of numbers and applies the function on that number (y) and the previous result (x) with the seed (1) used as x for the first operation.

I'm seeing how far I can go writing all solutions in Linq. Eg, day 1 was quite neatly

    public long Part1()
    {
        return Lines.ElfinToNumber().Sum();
    }
    public long Part2()
    {
        return Lines.WordsToDigits().ElfinToNumber().Sum();
    }

[Pickled Onion]

And day 7 reads nicely with Linq

(click to show/hide)

    public long Part1()
    {
        return Hands.Order().Select((x, n) => x.Bid * (n + 1)).Sum();
    }
    public long Part2()
    {
        CardValue['J'] = 1;
        return Hands.WithJokers().Order().Select((x, n) => x.Bid * (n + 1)).Sum();
    }

It was fun writing the comparer.

[Pickled Onion]

Day 8, a bit of a cheat because I wrote GetSteps as normal function but the resulting Linq is still pleasing

(click to show/hide)

This really is a spoiler, don't click unless you really want a spoiler

(click to show/hide)

    public long Part1()
    {
        return Map.Keys.Where(x => x == "AAA").Select(GetSteps).Single();
    }
    public long Part2()
    {
        return Map.Keys.Where(x => x[2] == 'A').Select(GetSteps).Aggregate(LowestCommonMultiple);
    }

[Pickled Onion]

Day 9, that was interesting, I've never used Zip before

(click to show/hide)

    private long PreviousInSequence(IEnumerable<int> ints)
    {
        var diffs = ints.Zip(ints.Skip(1), (x, y) => y - x);
        return diffs.All(x => x == 0) ? ints.First() : ints.First() - PreviousInSequence(diffs);
    }

[Diver300]

Day 10 pt 2 started to be interesting.

(click to show/hide)

The question is to find the number of points inside a perimeter.

That can be done from any point by counting the number of times the perimeter is crossed (in any direction) to get from the point to the edge of the map. If that number is odd, the point was inside the perimeter.

The digital and grid based nature of the map, in typical AOC fashion, means that any direction from many points to the edge will end up going along the perimeter at some point, making the crossing happen over several positions.

As my code travelled from each point to the edge along a straight line, the code stored whether the perimeter had approached the straight line from the left or the right, and if the perimeter later left the line on the same side, that was not counted a crossing, but if it left on the opposite side, it was counted as a crossing.

[Greenbank]

Day 10 part 2:-

(click to show/hide)

...
The digital and grid based nature of the map, in typical AOC fashion, means that any direction from many points to the edge will end up going along the perimeter at some point, making the crossing happen over several positions.

As my code travelled from each point to the edge along a straight line, the code stored whether the perimeter had approached the straight line from the left or the right, and if the perimeter later left the line on the same side, that was not counted a crossing, but if if left on the opposite side, it was counted as a crossing.

Not every direction. I tested for inside/outside by moving diagonally (north west in my case). If you do this you don't have to worry about non-zero winding rule type things. The horizontal/vertical pipes count, as do two of the corner pipes, but not the other two corner pipes. Much simpler.

e.g. if moving NW then | and - count, as do F and J, but L and 7 don't.

[Greenbank]

Day 5 part 2:-

(click to show/hide)

I didn't do ranges, I tested the lowest seed number(s) and, as I worked through the mappings, took note of the maximum I could add to this n and still fall through all of the same rules. I could then skip all of those values (since they would always lead to a higher number if going through the same rules) and start on the next one that invoked a change in rules.

Takes 0.4 ms to parse the input (could probably improve that) and then under 0.1ms to do the calcs for part1 and part2. I could probably save a bit in part2 too given that it's already done some of the seed values in part 1. It only ever had to check 153 individual seed numbers in part 2.

Code: [Select]

dur=421.422µs
part1: 174137457
dur=444.062µs
part2: 1493866
dur=498.989µs


[Pickled Onion]

Day 10 part 2:-

(click to show/hide)

...
The digital and grid based nature of the map, in typical AOC fashion, means that any direction from many points to the edge will end up going along the perimeter at some point, making the crossing happen over several positions.

As my code travelled from each point to the edge along a straight line, the code stored whether the perimeter had approached the straight line from the left or the right, and if the perimeter later left the line on the same side, that was not counted a crossing, but if if left on the opposite side, it was counted as a crossing.

Not every direction. I tested for inside/outside by moving diagonally (north west in my case). If you do this you don't have to worry about non-zero winding rule type things. The horizontal/vertical pipes count, as do two of the corner pipes, but not the other two corner pipes. Much simpler.

e.g. if moving NW then | and - count, as do F and J, but L and 7 don't.

(click to show/hide)

I don't think you need to do either of those things. I imagined each tile not in the loop to be slightly to the right of its real position, then a vertical line would cross a boundary only at F, L or -
The only wiggle was not knowing what flavour of pipe the start was, but rather than coding that up, if an up line hit S I just went down instead.

[jwo]

Day 10 part 2:

(click to show/hide)

I think you can simplify further by just moving left or right and only looking for |, L, or J (the same would work if you looked for |, F, or 7). The nice thing about this approach is that you can then just process the grid rows individually with a simple one-line filter and  character count:

crossings = (row, col, grid) => grid[row].slice(col).filter((c) => c === "|" || c === "L" || c === "J").length;
 

[jwo]

Day 13

I enjoyed this one. Not so much in getting an answer, but in doing so efficiently.

(click to show/hide)

My first attempt for Part 2 tried every possible grid cell as the smudge location. Surprisingly this found the answer in around a second. But with bitwise representation and information theory to the rescue (Hamming distance), managed to get a speed-up of c. 1000x, giving an answer in under a millisecond.

Full workings here (JavaScript):

https://observablehq.com/@jwolondon/advent-of-code-2023-day-13

[Greenbank]

Day 13

(click to show/hide)

Didn't need full hamming distance. If two numbers differ then you can a xor b and then test if the result is a single bit set with one of my favourite CompSci tricks - the test for something being a power of two:-

(x & (x-1)) == 0

Helped get mine down to 193.284µs.

[jwo]

Day 13

(click to show/hide)

Didn't need full hamming distance. If two numbers differ then you can a xor b and then test if the result is a single bit set with one of my favourite CompSci tricks - the test for something being a power of two:-

(x & (x-1)) == 0

Neat. I think that shaves off another few milliseconds, but will leave the Hamming version up in my page as it better reflects my chain of thought. The kind of programming I do tends not to use these lower-level bitwise ops, but that power of 2 trick now logged in my brain for future use (along with swapping contents of two variables with three XORs).

[Greenbank]

Day 18

(click to show/hide)

First time I've used the Shoelace Formula. Utter goblinry. Brain can't compute how it works so I'm going to have to read up on it to make it sink in.

Total time for 2023 so far (up to and including day 18) is 0.378s, so still a few left to optimise (days 17, 16, and 14 take the longest).

[jwo]

Day 18

Total time for 2023 so far (up to and including day 18) is 0.378s, so still a few left to optimise (days 17, 16, and 14 take the longest).

Impressive. Are you still writing them in C?

I've just totalled mine (JavaScript) up to and including Day 18. I come out at 1.3 seconds total, with those same slow days being over 80% of that time.

Day 18 was my favourite so far.

(click to show/hide)

Nice example of misdirection in the puzzle instructions with the recent memory of Day 10 also helping to shove us in the wrong direction.

(click to show/hide)

I think the trapezoid formula makes more intuitive geometric sense, and I guess you can derive the shoelace from it.

[vorsprung]

Day 96

(click to show/hide)

there isn't a day 96.  I haven't wasted even 10 seconds on the Advent of Code this year!

[Greenbank]

I don't know how long I've spent on AoC over the years but all of the time isn't wasted (it's not all 100% productive/useful either though). I'd probably guess it's at least 40h each year.

Like jwo (and Ross and mTrak) I've got all of the stars (so far, for all years) and that represents a significant amount of time that has been put into it, but I'd count this as professional development - plus the fact that I enjoy solving these kinds of puzzles.

I'm using it as a challange but mostly to get more comfortable in a new language (Go). I did all of the previous years in a mixture of shell, C and predominantly perl. Now most of my professional coding is in Go and so that's what I'm doing 2023 in. In my Copious Free Time (TM) I'm also going back and redoing all of the previous years in Go (have about 90 days left to do). This helps me understand how I would implement certain things in this language, notably:
* Numbers > 2⁶⁴
* Number theory (modmul, modexp, lcm, gcd, crt, ...)
* Recursion, tail recursion
* Parsing, regexp, sorting
* Memoization and Dynamic Programming
* Sparse grids using maps, 2D, 3D, 4D+
* BFS/DFS
* Dijkstra/A* and using structures like a heap queue to implement an efficient priority queue
* Trees (binary, n-ary, red/black, etc)
etc

[jwo]

Wot Greenbank sed.

For me, over the years I've used AoC to improve my skills in Java, Elm, JavaScript and C++ as well as general data structures and algorithm competence. I also use it with students (from first year undergraduates to PhDs) to help them develop their algorithmic thinking, reasoning and communication. I didn't do a Comp Sci or Maths degree so AoC has been useful learning tool for me (and mostly fun).

I know Eric (the puzzle setter) creates these to help people learn, and some of the puzzles are very elegantly and subtly designed with that in mind. Clearly it's not for everyone, but for some (of us), a fun and rewarding activity.