Keith's Electronics Blog

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 »

I can’t link to part two of today’s problem because you have to solve part 1 to unlock the second half of the web page; but I’m sure it’s been countlessly reposted by now and I’ll summarize it:

Oops, some of the digits that we want to add up have been written as English words instead of numerals. Recognize the words one, two, three, four, five, six, seven, eight, and nine as digits also. And we have new sample input:

two1nine
eightwothree
abcone2threexyz
xtwone3four
4nineeightseven2
zoneight234
7pqrstsixteen


Which yields 29 + 83 + 13 + 14 + 42 + 14 + 76 = 281.

Read the rest of this entry »

As with most Advent of Code problems, today’s first problem has a lot of cute story and some ambiguity in the phrasing that needs to be teased out and disambiguated.

It works out to: Extract the first and last digits on each line of text, use them to construct a two-digit number, and sum those numbers. Unstated but visible in the example is that if a line has a single digit in it, you use that for both digits of that line’s contribution.

Read the rest of this entry »

My day job doesn’t (normally) involve programming; (as is obvious) I don’t have as much time these days for hobby electronics and programming as I used to; and I really miss it.

So I was delighted when Kip introduced me to Advent of Code a few years ago. It’s a programming contest that releases a new puzzle each midnight (US eastern time; 23:00 my time) on the night that becomes December 1 through the night that becomes December 25. You work the puzzles at your own pace in whatever programming language you want (a few years ago, I did one puzzle’s heavy lifting in software and evaluated the dozen remaining results by eye) and the site checks your answers for correctness and shows you stats about your ranking within the global participants and within personal leaderboards of which you’re a member.

The puzzles are cute word problems and come with examples of input, logic, and output. Each participant is given a randomly- or algorithmically-generated input file, therefore a different correct output from other participants. (The algorithmic and programming expertise of the AoC creator/maintainer is hard to overstate.) When you upload a correct output to the first part of the puzzle, you’re given the problem for the second part of the puzzle to run on the same input — which often as not causes a rewrite if you used inadvisable programming shortcuts in your solution to the first part.

As always, I’ll be doing this year’s puzzles in Perl. I’m reasonably fluent in it; and of the languages in which I’m reasonably fluent, Perl is very, very good at processing input in the kinds of formats used in these puzzles. (But so is _____ ! Yes, but I’m not fluent in _____ !)

And I’ll be posting them here, discussing both the algorithmic approach I take to the puzzle and the Perl code that accomplishes it.

You might find the puzzles interesting. You might find my algorithms interesting. You might want to learn more Perl (although I doubt it). You might want to trash-talk Perl (and I just won’t approve your comments). You might want to elevate my Perl programming by showing me more concise, more idiomatic, faster, or more elegant ways of writing the same code (and I’ll be thrilled).

See you Friday evening or Saturday morning, when I have time to post Friday’s code.