Advent of Code

[Diver300]

Day 6

(click to show/hide)

There is no need to keep tabs on individual fish. A small array of how many fish of each age there are is all that's needed. Then the number of calculations don't increase as the fish multiply.

(click to show/hide)

Or buy a bigger computer. But your approach was faster for me as well!

(click to show/hide)

Lots of puzzles from previous years started with something that could be solved with brute force, but then part 2 took amount of computing power needed beyond my PC. Therefore from the start I was on the lookout for something that took less computing power. The final answer for day 6 was around 1.6 million million, so having to have arrays that big is a large fraction of a PC's power. Simply having an array of nine numbers that are each that big is much quicker.

My day job tends to call on that kind of optimization, so i had a similar predisposition

In contrast, my solution for today's feels quite clunky. Though coding before coffee might be an issue.

Day 8
Even though today's was a bit clunky, the only solution that I saw didn't involve going round anything more than a handful of times.

(click to show/hide)

To work out which segment was which, all the possibles were there, so it was a matter of doing stuff like "find the segments in the 4 that aren't in the 1, and find which of those is missing from one of the instances of 6 segments lit".
I looked up how to put the results into alphabetical order in Javascript in order to compare against  a standard list of which letters are lit for 0 - 9 in seven segement.

[Pingu]

Day 6

(click to show/hide)

There is no need to keep tabs on individual fish. A small array of how many fish of each age there are is all that's needed. Then the number of calculations don't increase as the fish multiply.

(click to show/hide)

Or buy a bigger computer. But your approach was faster for me as well!

(click to show/hide)

Lots of puzzles from previous years started with something that could be solved with brute force, but then part 2 took amount of computing power needed beyond my PC. Therefore from the start I was on the lookout for something that took less computing power. The final answer for day 6 was around 1.6 million million, so having to have arrays that big is a large fraction of a PC's power. Simply having an array of nine numbers that are each that big is much quicker.

My day job tends to call on that kind of optimization, so i had a similar predisposition

In contrast, my solution for today's feels quite clunky. Though coding before coffee might be an issue.

(click to show/hide)

I eventually found a fairly simple spreadsheet solution for day 6

 

[Diver300]

Day 12
Part 1

(click to show/hide)

For this I had an array of routes though the caves. The array started with a single entry of "start". For each route that didn't finish with "end", the code would look for a possible next cave, that wasn't a duplicate if it was lower case. If none were found, the route would be deleted. The first possible next cave would be added to the route. If more than one were found, additional routes would be added to the array, each copying the parent route up to the new final step. It worked first time, after a couple of syntax errors were found

Part 2

(click to show/hide)

I added another array, of the same size as the array of routes. The second array simply flagged whether the route had visited a lower case cave. It should have been a quick change, but I made a syntax error that wasn't flagged as such

if (a == 1);
   {
   b = 2;
   }

when I should have written:-

if (a == 1)
   {
   b = 2;
   }

Once I had sorted that, it took me ages to spot that I hadn't deleted an entry to the second array at the same place where I deleted an entry to the main array. 

[perpetual dan]

Day 12 I got the first bit done ok, then had stuff to do.

Part two broke my previous (learning a new library) approach. Starting again with something simpler got me there.

Deliberate loops in a routing algorithm as part of the spec was quite upsetting though.

[Diver300]

Day 14

(click to show/hide)

Having spotted the bear trap in day 6, I proceeded to fall into the same trap in day 14.
Part 1 has a reasonable length of the polymer. With a start of 20, and approximately doubling ten  times, it's under 20000 long, and a program can keep track of each item.
Part 2 calls for 40 steps of approximately doubling, ending up with something huge and my attempt that solved part 1 in an instant would take years to do part 2 and I probably wouldn't have enough memory on my PC.
There was never any need to keep track of each item in the polymer. It's much quicker to count the pairs. I had an array 26x26 of pairs of letters, and each entry is the number of such pairs.

[perpetual dan]

Day 14

(click to show/hide)

Having spotted the bear trap in day 6, I proceeded to fall into the same trap in day 14.
Part 1 has a reasonable length of the polymer. With a start of 20, and approximately doubling ten  times, it's under 20000 long, and a program can keep track of each item.
Part 2 calls for 40 steps of approximately doubling, ending up with something huge and my attempt that solved part 1 in an instant would take years to do part 2 and I probably wouldn't have enough memory on my PC.
There was never any need to keep track of each item in the polymer. It's much quicker to count the pairs. I had an array 26x26 of pairs of letters, and each entry is the number of such pairs.

I took a couple of dead ends before getting it working in reasonable time today, but I still got my best part two position so far without any alarm clock shenanigans.

(click to show/hide)

Your approach is neat. I like it.

I broke out the cache and still got an answer in about 0.3s.
I wrote recursive depth first application of rules, then there's enough repeating of pair and depth to break the bottleneck. It's a fairly small and repetitive value space after all.

[Diver300]

Day 15
My code works for the demo, parts 1 and 2, and for my puzzle input part 1, and it appears to work for my puzzle input in part 2, but it gives the wrong answer. I am a bit stuck now.

Edit. Found the problem.

(click to show/hide)

The searching for better routes has to look up and left as well as down and right. I had stopped looking up and left at 100, and forgot to increase that when the map was 5 times larger.

[perpetual dan]

(click to show/hide)

My head wasn't really in it today, so I looked up Dijkstra with a priority queue and did that.
I still have a sense that I've missed some optimization, but ought to do some work

[Diver300]

Day 23 was solved with (effectively) pencil and paper.

I did use a computer to spot my stupid adding up mistake.

[Morat]

gentle nudge?

[Diver300]

The countdown has started.

[freeflow]

I've been doing advent of code in VBA for the past few years, but I've now upgraded to twinbasic.  Over the years I've developed a library to help eliminate a lot of the VBA boilerplate code needed to solve AoC problems.  So this morning I was delighted (and astonished) when my library worked well in solving the day 1 problem.

(click to show/hide)

Code: [Select]

Dim myResult As Long = Seq.Deb(Filer.GetFileAsArrayOfStrings(AoC & Today, vbCrLf & vbCrLf)) _
            .MapIt(mpSplitToSubStr(ToSeq, vbCrLf)) _
            .MapIt(mpInner(mpConvert(ToLong))) _
            .ReduceIt(rdInner(rdSum)) _
            .sort _
            .last

[Pickled Onion]

I had to look up TwinBasic, and found:

twinBASIC is an exciting new project that aims to provide a full replacement IDE and compiler for VB6

For the love of $Deity WHY??

[Pickled Onion]

Well day 9 pt 2 got me. The test data got the right answer, and printing out the visited points exactly matched the example, but the final answer was wrong. Only comparing the intermediates showed that I'd misunderstood the rules.

Bah! This is not the first one this year where the tests have passed for the wrong implementation.

[Diver300]

Well day 9 pt 2 got me. The test data got the right answer, and printing out the visited points exactly matched the example, but the final answer was wrong. Only comparing the intermediates showed that I'd misunderstood the rules.

Bah! This is not the first one this year where the tests have passed for the wrong implementation.

I had the same.

I got program to draw out the path of the last knot in the rope, and realised that my first attempt had gaps in the path.

[freeflow]

One of the joys of advent of code is teaching folks about how assumptions are made.  The problems need very careful reading to ensure you have eliminated stuff that has been included unnecessarily and stuff which is implicit - usually hidden in plain view in the details of the examples.  God knows how people who don't have English as a first language cope, or maybe its easier as things are read properly rather than quickly scanned for 'salient' points.

[Diver300]

Day 11 needed a trick so that the solution didn't become unmanageable for a normal computer.

(click to show/hide)

The "levels of worry" get to be extremely large numbers.
The tests each monkey does are whether the "levels of worry" is divided by a prime number.
The "levels of worry" only increase by multiplying by integers or adding integers.
The "levels of worry" can be reduced by taking their modulus using the product of all the primes used by all the monkeys. In my case that was the first 8 primes, so the numbers could be kept down to less than 10 million.
After that the sequence could be run in a few seconds in javascipt.

[Diver300]

For Day 15, the scale is too large for a brute-force solution.

(click to show/hide)

I divided the possible 4 million x 4 million grid into 10,000 squares of side 40,000.
I worked out if the midpoint of each square was more or less than 40,000 away from a point that could not be detected by a sensor.
If the midpoint was more than 40,000 away from a point that could be detected, the whole square could be discounted. That only left me with 50 squares.
Then each of the 50 squares was divided into 40,000 smaller squares of 200 x 200.
Then I used a brute-force attack to check every single point in each one of the smallest squares that couldn't be discounted. There were 3185 to check.
In all the program checked how close a point was to a point that could be detected 129,410,000 times, so it only needed to check one in every 123,000 points. It took about 20 seconds to run in Javascript.
 

[Diver300]

Day 16, part 2.
The code that got the right answer for me needed to try 8,142,958,394 possibilities and took something like an hour to run.
The same code run on the example only needed 37,623 possibilities and runs almost instantly.

(click to show/hide)

I first worked out the distances from each cave to each other cave, then I removed the caves with valves with no flow from the possibilities.
The final answer was 6 valves opened by the person, and 5 by the elephant. With 15 valves there are an enormous number of possibilities.

I have tried to make sure that a pair of routes was only checked once, rather than once with the person doing the first, and once with the elephant doing the first, but I'm not sure if I succeeded, but that would have only doubled the number of routes checked.

Edit:- With a robust way of checking for duplicates, it only took 40 mins to run (Javascript on Chrome) and it tried 4,106,390,647 possibilities.

I can't see any more optimisations that could be done.

[Diver300]

Day 22: Monkey Map Part 2
The statistics show that quite a low proportion of the solutions of the first part got converted into solutions of the second part.

The YACF private leaderboard has 5 solutions to the first part and only 3 to the second part. There are only 4 first part only solutions for the whole of the private leaderboard, and two of those are for Day 22.

(click to show/hide)

The puzzle input is to be folded into a cube, and the path traced over the edges.

I don't know if others are trying to find a general solution, but I found a solution specific to the layout in my puzzle input.

Code: [Select]

     C  D
    ######
   B######F
    ######
    ### G
   A###g
  a ###
 ######
b######f
 ######
 ### E
c###e
 ###
  d
That is the layout of my puzzle input with each square of 9 #'s  representing a square of 50 x 50 of my puzzle input.
The letters indicate where the edges of the cube join.

My solution would only work for the same layout, but for any content within each 50 x 50 square.

There are 12 edges in cube. 5 of those edges are already joined in the puzzle input, so there are 7 edges, each of which can be approached from two directions, so that is 14 rules for crossing edges.

I just wrote out and coded each of the 14 rules by hand. Each was a couple of conditions and a couple of equations. For me that was a lot quicker than trying to write the code to write those rules.

[Diver300]

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"

[R_nger]

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"

That’s plain greedy 

[Pickled Onion]

That was a bit sneaky for a day 1. Depending on your approach it would have been quite easy to pass a test on the sample but get the wrong answer on the puzzle.

I see quite a few people in the private leaderboard haven't bothered completing part 2 yet.

[Diver300]

That was a bit sneaky for a day 1. Depending on your approach it would have been quite easy to pass a test on the sample but get the wrong answer on the puzzle.

Only for part 2, but yes, the sample was no help at all for the difference between part 2 and part 1

I see quite a few people in the private leaderboard haven't bothered completing part 2 yet.

Part 2 needs to detect several characters to get a match, while part one only needs to detect a single character.

I was pleasantly surprised when my additions for part 2 worked first time (after the errors that wouldn't compile had been sorted)

[jwo]

Only for part 2, but yes, the sample was no help at all for the difference between part 2 and part 1

Except that some of the words in the sample did give a clue about the main gotcha with part 2, even if it didn't actually have an effect when processing the sample.