AoC 2023 D8P1: Traversing a Digraph

December 9th, 2023 by Keith Neufeld

Day 8 part 1 gives us a directed graph of nodes with links to two (hopefully other) nodes and a set of dance moves to perform through the graph; how many steps to get from AAA to ZZZ at the end of a dance pattern? (A lot more steps if you stray into DDD, EEE, or GGG.)

RL

AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)

All one need do is make a hash of the nodes with their branches, then dance through it.

Read the rest of this entry »

AoC 2023 D7P2: Pseudo-Poker Hands with Wildcards

December 9th, 2023 by Keith Neufeld

Part 2 redefines J from jack to joker, making jokers wildcards when determining type of hand but the lowest value when comparing individual cards. This requires very little modification to the part 1 program:

my $cardlist = "AKQT98765432J";

Change the card sort order;

my $jokers = grep { $_ eq "J" } @cards;

count the jokers;

++ $tally{$_} foreach grep { $_ ne "J" } @cards;

omit the jokers when counting cards for type of hand;

$ofakind[0] += $jokers;

and in this poker variant, simply add the count of jokers to the count of the most-frequent card when determining type of hand.

Read the rest of this entry »

AoC 2023 D7P1: Pseudo-Poker Hands

December 9th, 2023 by Keith Neufeld

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 »

AoC 2023 D6P1, P2: Quadratic Formula or Count

December 6th, 2023 by Keith Neufeld

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) tcharge ( ttotal – tcharge); so the answer to the problem can be found directly by using your favorite quadratic solver on tcharge2 – ttotal tcharge + drecord = 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 »

AoC 2023 D5P2: Interval Intersections

December 6th, 2023 by Keith Neufeld

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 »

AoC 2023 D5P1: Integer Ranges

December 6th, 2023 by Keith Neufeld

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

seed-to-soil map:
50 98 2
52 50 48

soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15

...

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 »

AoC 2023 D4P2: Caching Coefficients of Future List Elements

December 4th, 2023 by Keith Neufeld

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 »

AoC 2023 D4P1: List Searching

December 4th, 2023 by Keith Neufeld

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 »

AoC 2023 D3P2: 2D Adjacencies Again

December 3rd, 2023 by Keith Neufeld

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 »

AoC 2023 D3P1: 2D Adjacencies

December 3rd, 2023 by Keith Neufeld

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 »