Keith's Electronics Blog

Day 7 introduces a card game with hand values loosely based on poker: 5 of a kind, 4 of a kind, full house, 3 of a kind, 2 pair, 2 of a kind, nuffin’. A tie on the type of hand is resolved by the rank of the cards in order dealt (not in order of rank), with ordering AKQJT98765432. Given these rules, rank your hands, then multiply the ordinal value of the resulting list by a unique coefficient for that hand.

32T3K 765
T55J5 684
KK677 28
KTJJT 220
QQQJA 483


This sort is going to require a fair number of comparisons, each involving rank of types of hands and each potentially involving rank of cards. These comparisons are computationally-intensive enough that I’m leery about executing them during each comparison of the sort, so I calculated and cached them up front.

Read the rest of this entry »

Day 6 problem 1 asks us to consider a series of toy boat races. The longer you have the boat on the charger, the faster it’ll travel during the remaining units of time. With how many different integer charge times can you beat the record distance in that race?

The distance traveled is (ignoring units) t_charge ( t_total – t_charge); so the answer to the problem can be found directly by using your favorite quadratic solver on t_charge² – t_total t_charge + d_record = 0, which will have zero, one, or two real solutions. If it has zero solutions, one solution that’s non-integer, or two non-integer solutions between two consecutive integers, then there are zero integer charge times that beat the record. Otherwise count the number of integers from the floor of the lower solution plus one to the ceiling of the upper minus one. (That sounds weird but math it out — it ensures not merely tying the record but beating it.)

Anyone who remembers algebra and has dignity and self-respect would use this trivial approach.

I wrote a program to count winning charge times by iteration.

Read the rest of this entry »

Day 5 part 2 reveals that the seed list does not actually denote individual seed values; it is pairs of numbers denoting ranges of seeds. Run each range through the translations and find the lowest value in any resulting range.

After the way I wrote the first program, this made me feel like Obi-Wan just told me to go home and rethink my life. I could enumerate each range of seeds and run them all through the translations … for certain values of “could” that include more processing power, electricity, and time than I have remaining in my years on this planet.

It was obvious that I was going to have to treat ranges as data structures, intersect them with ranges in translation rules, translate them accordingly, and be prepared to split seed ranges that overlapped translation ranges to apply the translation to only a portion of the input range. Afflicted with a serious case of I don’t wanna, I pretended to be too busy with other things to get around to writing this yesterday.

But early this morning I cured my case of I don’t wanna in the way I’ve learned to cure any case related to programming: Write the utilitarian loops that do the boring work of the program; and once they’re done, there’s so little of the program left to write that I’m ready to go ahead and do it.

20231207 edit: I omitted handling one way that intervals can intersect and it was accidental that my program handles that case correctly. More below.

Read the rest of this entry »

Advent of Code day 5 has us processing ranges of integers. Given seed values and lists of translations in the form dest src length, find the lowest value after applying all the translations.

seeds: 79 14 55 13

...


I went over the top on this problem, loading all of the translations into memory as though they were important, then iterated through seeds in my outer loop and translations looping inside that on each seed.

Read the rest of this entry »

Day 4 part 2 asks us to find the number of winning entries on each line and use that to duplicate the succeeding n lines; and a duplicated line with winning entries multi-duplicates its succeeding lines; all with a promise not to overflow the end of the input list; and then count the total number of instances that occurred.

It would be vaguely entertaining to implement this using a queue of the coefficients of upcoming lines, or using recursion; but I chose simply to build an array of the multipliers that I prepopulate for lines I haven’t seen yet.

Read the rest of this entry »

Day 4′s problem asks us to find, on each line of input, how many members of the second list are members of the first list:

Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3: 1 21 53 59 44 | 69 82 63 72 16 21 14 1
Card 4: 41 92 73 84 69 | 59 84 76 51 58 5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11


O’Reilly’s Perl Cookbook has concise code for finding the union and intersection of two lists, but it requires that each list has unduplicated entries. I suspect that’s going to be the case here but I’m not sure I should presume, so I’ll do my own thing.

Read the rest of this entry »

Day 3 part 2 asks us to find only numbers adjacent to * characters, and only when exactly two numbers are adjacent to * characters.

I could trivially update my flood fill to prime the stencil only with * characters and then it would find only numbers adjacent to them; but I’d still have to write new code to count the quantity of numbers adjacent to * characters; and by the time I’ve done that, I might as well use it in the main loop also.

Because


..123...
...*....
456.....


that star has a whole lot of digits adjacent to it but only two numbers.

New approach: Look for stars; find adjacent digits; immediately find the full string of digits and cache it; flag every position filled by those digits so it’s not picked up again in this particular scan for neighbors; count the cache length.

Read the rest of this entry »

Day 3′s first problem asks us to find numbers that are horizontally, vertically, or diagonally adjacent to symbols in input like this (with dots being blank space):

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..


As the sample logic states, in the sample input, only 114 and 58 aren’t adjacent to any symbols.

I thought for a while about a couple of ways to do this and settled on a flood fill. This was an incorrect choice that happened to work on my particular input but is not a proper solution, so I got unreasonably lucky.

Read the rest of this entry »

In day 2 part 2, rather than verify whether each game / bag has no more than the specified number of cubes of each color, we’re to determine the number (maximum) cubes of each color that we see in across any pull from each game / bag.

my %max = ( red => 12, green => 13, blue => 14);

We no longer need to set the maximum permissible count.

my %max = ( red => 0, green => 0, blue => 0);

Instead, within each row of input, accumulate the maximum count of each color seen on any pull of this game.

Perl doesn’t require initializing hashes that will be used to accumulate information and it’s idiomatic not to; but with strict/warnings, my later comparisons will fail against uninitialized hash buckets; and it’s easier to initialize them than to add logic to check whether they’re already defined.

$max{$color} = $count if $count > $max{$color};

Then in the innermost loop when processing each color, set the new max for this game / bag to that count if the count exceeds the previously-seen maximum.

$sum += $max{red} * $max{green} * $max{blue};

Finally, we’re to sum the product of RGB counts from each line (rather than the game ID as in p1).

Read the rest of this entry »

Day 2′s problem 1 requires parsing this format:

Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green


to determine which rows have no more than 12 red, 13 green, and 14 blue cubes in the bag, then summing the game ID of those rows. In other words, interpreting lists of colors from lists of pulls from a list of games.

Read the rest of this entry »