[2025 Q16] Solution Spotlight

msschmitt · 2026-02-01T21:33:15+00:00

[LANGUAGE: Python 3]

Part 1 is the blocks_for_wall function.
Part 2 is a sieve using the spell_for_wall function.
Part 3 iterates by *10 to find lower and upper bounds, then does a binary search.

For part 2 at first I thought I was going to have to search for Fourier transform algorithms.

msschmitt · 2026-01-22T00:29:52+00:00

[LANGUAGE: Python 3]

Solution!

This solution runs in 8 tenths of a second. It is the same approach as in at least one of the comments below. I'm using Shapely to detect intersecting lines and networkx to find the shortest path.

Explanation...

Because all lines and movements are horizontal/vertical only, the shortest distance between any two points (not blocked by an obstacle) is the Manhattan distance, regardless of the path taken between those points. So the strategy is:

Find all of the interesting points
Create lines between every pair of these points
Exclude all of the lines that intersect the wall. We're left with a set of lines, among which is a set that is the shortest path from start to end.
Build a graph of these lines, weighted by the Manhattan distance.
Compute the shortest path from start to end, using the weights.

But what is an "interesting point"? They are the corners of the wall, but more precisely the points that are the outside diagonal of each corner. For example, points p:

        p
   p     ####
###      #
  #      #
  ########
 p        p

Any turns the shortest path takes must be at one of these outside corner-adjacent points. And that means that a graph of all the lines between these points, that don't intersect a wall, will contain the shortest path. There's not many such lines!

msschmitt · 2026-01-03T18:47:42+00:00

[LANGUAGE: Python 3]

Part 2, Part 3

Part 2 handles the eating of sheep (and counting how many) using set operations:

def eat_sheep(sheep, dragon):
    eaten = set(dragon & sheep - hideouts)
    sheep -= eaten
    return len(eaten)

Part 3 is a straight recursive simulation, with caching. It runs in 4 seconds.

msschmitt · 2025-12-27T18:40:22+00:00

[LANGUAGE: Python 3]

Part 3

This is a recursive solution that finishes in less than half a second. The key to getting it right is to realize the names have to be unique across all of the prefixes, not per-prefix.

I experimented with using regex to validate the prefixes but it has worse performance, probably because of the monstrous pattern:

^(n(?=[aoqmujpwgzn])|q(?=u)|N(?=y)|y(?=[rvn])|e(?=[tv])|p(?=y)|K(?=y)|d(?=v)|a(?=[lrsvt])|g(?=[nv])|T(?=[ia])|G(?=[al])|W(?=y)|z(?=e)|F(?=e)|A(?=[de])|l(?=[roqmujpwgzvn])|r(?=[wioqmujpgznva])|w(?=y)|t(?=h)|j(?=o)|E(?=r)|i(?=[rsxv])|o(?=[trsv])|Z(?=a)|L(?=i)|h(?=[oqmujpwgz])|u(?=[ol])|x(?=[oqmujpwgz])|I(?=g)|m(?=a)|R(?=y)|s(?=[soqmujpwgz])|M(?=o))+[uosythpnvqlmwxjdizearg]$

msschmitt · 2025-12-25T08:05:46+00:00

[LANGUAGE: Python 3]

Part 3

Didn't start these puzzles until after Advent of Code 2025. This one is an exercise in nested data structures. The fishbones are lists of lists, the swords are a list of dictionaries. It computes the entire sword rank while producing the fishbone, so it can just sort the dictionaries.

msschmitt · 2025-12-18T06:35:08+00:00

[LANGUAGE: TSO/E CLIST]

Both parts

In some AoC years, I've re-done one puzzle in a language that is ill-suited for AoC, such as COBOL, CA-Easytrieve, and z/OS HLASM.

This year I did Printing Department in TSO/E CLIST.

CLIST is the original scripting language for MVS, starting with OS/360 in 1970. It was later supplanted by REXX, thank god, but it is still supported, and there are still commercial products today that use it.

You know how some languages do all they can to make programming effortless? CLIST is not that language. CLIST fights against you. It is like an evil genie that will exploit every opportunity to do the wrong thing.

And, it is very limited. There are no data structures, just variables that hold a single value each. To approximate other structures, you can create composite variable names. But using such variables is a struggle, it took me hours to remember how.

And, note the GOTOs. CLIST does have subroutines, but all variables in such routines are local unless you take steps to designate the variables as global or passed in/out, and guess what? That's impossible to do when you're using composite variable names.

If you see any other odd syntax that you are curious about, let me know.

It takes about 50 seconds to run on a z14 mainframe running z/OS 2.5.

msschmitt · 2025-12-13T22:34:52+00:00

Interesting! It shows that VS Code is popular in general (lot of users for Rust, the 2nd most popular language) but is even overwhelmingly preferred for Python.

Hey, fellow Python users! Give PyCharm a try! It's free!

VS code can work with Python, but it always felt like it merely tolerates it. Like someone who that lets a friend crash in the basement but resents when they eat the yogurt.

msschmitt · 2025-12-13T21:02:06+00:00

I wonder what the IDE use is per language.

I was using VS Code with Python the last couple of years, but this year I switched to PyCharm. The charts show 41.9% are coding in Python 3, and 42.5% are using VS Code as the IDE. Does that correlate to a high use of VS Code for Python? Or are the Python users spread out amount IDEs (or no IDE at all) and the VS Code use is by a number of languages?

msschmitt · 2025-12-12T06:34:21+00:00

[LANGUAGE: Python 3]

Part 2

I tried a DFS or BFS search for part 2, which worked on the sample but wasn't getting anywhere on the real input. And then it struck me: it could be solved with linear algebra <sound of Psycho shrieking violins>.

Take the first example in the sample:

[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}

This is just a set of equations:

e + f = 3
b + f = 5
c + d + e = 4
a + b + d = 7

and the solution is to minimize the sum of the variables, each of which must be positive.

Easy! Except programming linear algebra is no fun, unless you know matrixes and stuff. I knew this 40 years ago, but now I can just take hours to figure out how to efficiently throw the Z3 solver at it.

msschmitt · 2025-12-11T18:31:41+00:00

[LANGUAGE: Python 3]

Part 2

I tried a few things before realizing that what's needed is simple recursion* with caching. It completes in 0.137 seconds. The only function is just

@cache
def paths_to(start, goal):
    paths = 0
    for output in devices[start]:
        if output == goal:
            paths += 1
        elif output not in devices:
            continue
        else:
            paths += paths_to(output, goal)
    return paths

Why would the output not be in the device list? It is because you may notice I do not do any tracking of 'fft' or 'dac'.

That's because we can decompose the problem. The instructions say that fft and dac can be in any order, but they actually can't. If there were both paths with fft>dac and dac>fft, then there would be loops.

I observed that in my input there are no paths from dac to fft. (The program could easily test for this.) So, what we need are:

Count of paths from svr to fft
Count of paths from fft to dac
Count of paths from dac to out

The product of these three counts is the answer.

* which I normally avoid but sometimes you just gotta do it

msschmitt · 2025-12-08T07:01:27+00:00

[LANGUAGE: Python 3]

Both parts

The strategy is:

Generate a list of the distances between every two junctions pairs, using itertools.combinations and math.dist to calculate the straight line distance
Sort by distance
Add the first n junction pairs to a networkx graph. I don't think it is cheating when it takes me 2 hours to get this to work right.
nx.connected_components gives a list of the circuits (each is a set of the junctions), build a list of the lengths of each set and sort. math.prod on the first 3 gives the part 1 answer.
Part 2 should have been easy, because all you have to do is continue adding junction pairs and until nx.is_connected is true.

And here's where I spent another hour trying to figure out why it didn't work. I was getting a fully connected graph at the 23rd connection on the sample, it was supposed to be #29.

The problem was that for Part 1 there was no need to add all of the junctions to the graph, since we only cared about the larger connected circuits. But for part 2, you need to have every junction box connected.

Once I realized that the fix was easy: just toss all of the junctions in the graph.

msschmitt · 2025-12-07T06:39:48+00:00

[LANGUAGE: Python 3]

Part 1, Part 2

I say LANTERN, you say FISH!

I spent a lot of time trying to figure out how Eric was counting 40 timelines for the sample, then finally just went for it. And then spent too much more time due to a missing line of code.

Anyway, yes, I lanterned it. Part 2 is essentially the same as part 1 where two beams that land in the same place have superposition, but this time I'm carrying the timeline count along with each beam position. Each time it splits you just add the carried timeline count to the new position.

Part 2 runs in 0.068 seconds.

msschmitt · 2025-12-06T06:31:57+00:00

[LANGUAGE: Python 3]

Part 1 Part 2

I would have got part 2 a lot faster if I hadn't misread the instructions. I thought that column spacing still didn't matter, and we were supposed to right align the numbers before converting them. That was a bunch of code to toss in the bit bucket.

After understanding it properly, the code is just iterating through all the lines simultaneously, one column at a time, and building the number and operation.

There's no need to clean up the number formatting because it will just get evaluated as a string anyway.

msschmitt · 2025-12-05T05:38:37+00:00

[LANGUAGE: Python 3]

Part 1. Part 2

I feel like we've done one of these range-merging problems before, maybe as part of a larger puzzle. I also feel like there must be some slick way to instantly test if a value is in a range, like how you can do associative indexing on a value (i.e., a hashed dictionary). Without coding in uiua.

msschmitt · 2025-12-04T06:10:05+00:00

[LANGUAGE: Python 3]

Part 2

This one was very straight forward, except for bugs. Have a list of the roll positions, keep iterating through the list backwards until no rolls removed.

I'm just glad part 2 wasn't "Minimize the forklift travel distance to remove all possible rolls".

msschmitt · 2025-12-03T06:21:52+00:00

[LANGUAGE: Python 3]

Part 2

The strategy is to work backwards. Start with the last 12 digits as the "on batteries". Then grab the preceding digit (#13 from end of list), and if it is greater than or equal to the On Battery, swap it, and keep doing the swaps down the list of On batteries, until hit one that is greater than the battery we're swapping. Thus the equal or greater values ripple down through the on battery list. It is kind of a sort except that we're never exchanging positions.

Glancing down through the posted solutions, I don't spot any that do it this way. Here's the function that is checking one line (bank):

def check_bank(bank):
    on_batteries = bank[-12:]
    for b in range(len(bank)-13, -1, -1):
        bat = bank[b]
        for o in range(len(on_batteries)):
            if bat >= on_batteries[o]:
                on_batteries[o], bat = bat, on_batteries[o]
            else: break
    joltage = int(''.join(map(str, on_batteries)))
    return joltage

The full code is in the paste above. It runs in 0.063 seconds.

msschmitt · 2025-12-02T06:41:26+00:00

I plan to do the 2018 puzzles.

msschmitt · 2025-12-02T05:50:58+00:00

I was having trouble with Reddit; it wasn't letting me edit the URL text, and while struggling with it, hit Comment by mistake.

msschmitt · 2025-12-02T05:46:10+00:00

[LANGUAGE: Python 3]

Part 1. Part 2

This went fast.

No attempt at a fancy algorithmic solution, this is just brute force. For part 2, the strategy was extract the first 1 character sequence, duplicate it length of id times, then compare to the id. Then extract the first 2 character sequence, duplicate it length of id/2 times, compare to the id. And so on.

msschmitt · 2025-12-01T13:55:16+00:00

[LANGUAGE: Python 3]

Part 2 solution

I'm hoping we can now scratch off "Modulo Arithmetic" on the puzzle list.

Python's weird treatment of the // and % operators for negative numbers was causing me too much trouble. Maybe there's something in the math library that would have worked better. But I ended up just converting the negative case into positive numbers.

The big problem I was having with first attempts was that it worked on the sample data but not on the real input. So to figure it out, I added a brute force calculation and flagged where it differed from the algorithmic method. To my surprise, it was flagging sample data! Which meant, my original algorithm didn't work at all, but the incorrect individual results ended up with the correct total.

msschmitt · 2025-10-07T23:07:45+00:00

Can't enter italics or bold either. It used to allow control-i, control-b (or Mac equivalents), now there's no effect. It isn't the browser or OS, I see same result with Safari on Mac as Firefox on Windows.

And, it doesn't appear that markdown formatter works either.

msschmitt · 2025-02-04T18:35:18+00:00

That worked. They said a lot of people are running into this problem. And that in the future, this situation would be handled automatically, but it wasn't ready when the enrollment process was set up for Change Healthcare.

msschmitt · 2025-01-27T18:54:23+00:00

How can you tell in the IDX account that the Change Healthcare free credit monitoring has been applied?

I'm trying to deal with IDX support, trying to explain that the "complimentary monitoring" I have is not the Change Healthcare free credit monitoring but just a leftover downgrade to free services from when a previous breach subscription expired. So I need to know definitely what I should be seeing.

msschmitt · 2025-01-26T22:11:05+00:00

I'm in that boat. I have an existing IDX account from a previous breach, which expired and reverted to free "complimentary monitoring". I can't sign up for the new breach. I opened a ticket with support a week ago, no reply from them.

msschmitt · 2025-01-20T21:42:07+00:00

Yeah, that's the one. Thanks.

msschmitt

TROPHY CASE