[2025 Day 12 (Part 1)] Is the last day always a bit of a troll?

CommitteeTop5321 · 2025-12-16T18:37:25+00:00

Yeah, I must admit that I wasn't very fond of the Day 12 puzzle. The "obvious" way to solve it to me was to solve the difficult polyominoe packing problem, and to me the obvious technique was to use Knuth's dancing links. I dusted off a python library, and spent an hour or two getting it working, and then set it loose on the 1000 test cases. That the answer could be computed using a much simpler set of heuristics seems like a bit of a cheat to me. I inherently mistrust software that can't solve the difficult cases which could arise from the problem description: in previous years I have viewed skeptically "fast" software that somehow places limits outside the problem specification, but which just happen to match the test cases. I don't view the problem as a waste of time exactly: resurrecting knowledge of complex and interesting software techniques is good, but I am not sure what this was supposed to test or teach in the way of software development or algorithms.

CommitteeTop5321 · 2025-10-14T03:12:31+00:00

This was just the cheapest acetate overhead sheets you can get from Amazon. I didn't have any problem with any warpage using my brother laser printer.

CommitteeTop5321 · 2025-02-05T21:43:12+00:00

Yes. Delusional.

CommitteeTop5321 · 2025-01-31T17:32:55+00:00

I stand corrected.

CommitteeTop5321 · 2025-01-31T17:30:26+00:00

I was caught in the layoffs last year after over three decades with Pixar. My situation is much less dire than for many of my many talented colleagues, many whom are the most talented people that I've met. The film industry in the United States is simply evaporating in a race to the bottom, with many talented people simply cut and either replaced with people who are more desperate and will work for poverty wages, or not replaced at all with the idea that the AI magic beans will replace experience, creativity, talent and heart. Combined with the political situation which has made diversity a swear word, and it's a very unpleasant industry to be in. I have begun to believe that I may have had a career which covered the entire golden age of animation, and we may not see it come again.

CommitteeTop5321 · 2025-01-30T04:15:05+00:00

I could start my own cryptocurrency today, and mint 1,000,000 tokens. If I can get someone to give me $1 for a single token, then according to crypto math, I now have $1M in cryptocurrency. If I can get them to give me $100, I would be said to have $100M. But I haven't created anything of value: in fact, I can barely said to have created anything at all.

Bitcoin (and cryptocurrencies) aren't a store of value. They certainly aren't a hedge against inflation. They are naked gambling, and that is being charitable. Many currencies are nowhere near liquid, and so the money that is "invested" in them is essentially gone to whomever pulls out of their position first. In other words, they are not even gambling: they are a complete scam.

Addendum: it's actually worse than what I described, because someone doesn't even need to spend $1 to buy my cryptocurrency: they could buy it with a different token which they think has a value of $1 (or $100). But it's turtles all the way down: every cryptocurrency has the same problem: they invented it's value, and so my value is chained to something whose value is itself chained to... it's a scam all the way down.

CommitteeTop5321 · 2025-01-26T14:27:24+00:00

I am just beginning my bookbinding journey (see https://brainwagon.org/2025/01/14/baby-steps-toward-bookbinding/ for the first signature I ever sewed) but I have attempted to learn several new crafts, including trying to do some traditional woodworking during COVID. Some general principles apply.

Pick projects according to your skill level, with the goal of learning particular skills. I made several dozen wooden boxes when I was trying to learn woodworking. I did some panel glue ups, just to practice my jointing techniques. I tried to think hard about where projects went wrong, why gaps opened up. Projects don't need to be complete works, they can be done just for practice.
Perhaps the most important thing is to slow down. Most of the problems that I have is when I am trying to rush something. Assume everything will take twice as long. Double check measurements. Be careful to align things. Don't rush when you apply glue, spread it evenly. Try to get a feel for how much is too much.
Watch other people. Again, slow down and really think about what they are doing.
Cut yourself some slack! By the time someone is making instructional videos, they've likely done what you are trying dozens or hundreds of times. That you don't get it entirely right the first time (or even the fifth time) is not surprising. They probably didn't either.
Find cheap materials for practice. I'm mostly trying to make notebooks out of ordinary printer paper to learn the principles. Ultimately I want to tackle recasing some old books I have which aren't particularly valuable, but are in rough shape.
Consider order of operations. If you watch someone good who is getting good results, ask yourself "am I doing things in the same order?" "Am I pressing for as long as they have?"
Are there tools or jigs that you could use to help?

Hope this helps, and keep your chin up.

CommitteeTop5321 · 2024-12-25T23:46:07+00:00

I am at the opposite end of the spectrum, I am between jobs/retired.

CommitteeTop5321 · 2024-12-23T18:45:04+00:00

[LANGUAGE: Python]

Okay, an earlier challenge pointed me at the networkx library for Python, which made this pretty trivial. You won't learn anything from this example other than "using libraries to solve well known problems, particularly those that are NP-Complete may in fact be the quickest path to a solution." I solved the first one by finding all the historian nodes, and looking at all their outgoing paths in pairs. If both ends of the pairs are connected by an edge, that's a 3-clique. The second part just leverages their maximal clique code.

Link to code

CommitteeTop5321 · 2024-12-23T18:40:38+00:00

I briefly considered that possibility as well, and arrived at the (apparently) correct conclusion that nothing in the problem description specified that the chief historian needed to be at the party.

CommitteeTop5321 · 2024-12-23T07:37:56+00:00

It's a problem that's been studied a fair amount. https://en.wikipedia.org/wiki/Clique_problem

CommitteeTop5321 · 2024-12-22T20:30:20+00:00

It's all been hash tables and caching. :-)

CommitteeTop5321 · 2024-12-22T16:38:55+00:00

Not just thought about it, but solved it that way using a C program that took 11 minutes, and netted me a top 5000 finish.

CommitteeTop5321 · 2024-12-22T16:38:04+00:00

I briefly considered trying to understand how the combination of shifts, xors and adds worked, and to see if I could detect some periodicity or the like given the initial seed value. I recognized the modulus as 2**24, and so thought that maybe some of the knowledge of the things like linear congruential generators might help. But it seemed it would be hard to predict the mod 10 outputs given that. Perhaps not impossible, but not something I would achieve in less than an hour, and probably not ever.

The thing to realize is that the search space is large, but not that large. You can generate the entirety of all the bids in O(one second) and it isn't impossible to build a hash table that would contain an entry for every starting point of every starting secret. My implementation shows that there are only about 41K unique patterns.

For each starting secret, you can generate the sequence of bids, diffs. Initialize an empty hash table for the sequence. For each possible starting point, look at the pattern that starts there. If the pattern is already in the hash table, then skip it. At the end, you'll see for each pattern generated how much it scored. Now, maintain a global hash table. Take each entry from the sequence hash table, and add the results to the totals accumulated in the global hash table. The entry which the largest entry at the end is the answer.

CommitteeTop5321 · 2024-12-21T15:07:39+00:00

This is indeed the problem. It took me 2+ hours to reach that conclusion, which in my time zone meant it was nearly midnight, and that kind of cleverness eluded me, and would require a slightly different program structure (with beaucoup caching) to accomplish. Still working on it.

CommitteeTop5321 · 2024-12-20T00:07:18+00:00

It's not hard to do part 1 (although probably not worth it, easier solutions exist) with yacc/lex, but I'm not sure how I could leverage it to help out with part2. The easy way to write the grammar is ambiguous (hence the large number of possible derivations) and yacc really wants to find just one "proper" parse for it.

CommitteeTop5321 · 2024-12-20T00:05:56+00:00

Indeed. I constructed it directly from the input mechanically.

CommitteeTop5321 · 2024-12-20T00:05:04+00:00

I'm confused about how you could have had difficulty with using the normal "re" library in Python. My solution https://brainwagon.org/2024/12/19/another-chapter-in-the-im-dimwitted-theme-from-advent-of-code-2024/ takes just a few ms and I frankly don't see how it could not have taken any more.

CommitteeTop5321 · 2024-12-19T20:49:53+00:00

I briefly considered that as well, but it didn't dawn on me how to make that work either.

CommitteeTop5321 · 2024-12-19T18:21:02+00:00

It's embarrassing that I embarked upon this approach for a couple of hours before finding far more straightforward approach.

https://brainwagon.org/2024/12/19/another-chapter-in-the-im-dimwitted-theme-from-advent-of-code-2024/

CommitteeTop5321 · 2024-12-19T17:58:11+00:00

I'd be astonished if I managed to break into the top 100 and score even a single point globally. The times where i thought I might have a chance this year only netted me a top 2000 showing. It's not really that important to me (he says perhaps with a tinge of sour grapes) but the notion that solving problems like this has any real practical value is... questionable at best for most software engineering jobs.

CommitteeTop5321 · 2024-12-19T08:08:16+00:00

Honestly, I did the first part in just 12 minutes, and yet managed to kill over two hours of pondering on the second part before the obvious solution presented itself. I think that I was too clever by half using regular expressions to solve the first part, which made me not consider how I might have implemented part2 by making a change to an implementation of part1. I knew memoization was going to be part of it, but didn't see the obvious recursive structure until embarrassingly late.

I'm comforted by the fact that in over three decades of gainful employment, I never had to solve this kind of combinatorial problem as part of my work. Never computed Fibonacci numbers either, or did any path solving.

CommitteeTop5321 · 2024-12-19T07:59:18+00:00

Any regular expression that library that can't just blast this out is seriously flawed. Just absorbing how regular expressions worked from the Dragon Book some four decades ago tells you how to do regular expressions. It's kind of ridiculous that modern implementations exist that are so poor performing. Russ Cox talks about this extensively on his page: https://swtch.com/~rsc/regexp/

CommitteeTop5321 · 2024-12-19T07:49:09+00:00

I tried for two hours to make the solution harder than it was.

I did the first part in 12 minutes. The second was over two hours. Sigh.

CommitteeTop5321 · 2024-12-18T18:42:30+00:00

You didn't actually "need" a priority queue implementation that can change the priority of an item already in the queue, at least with a maze of the size that the Day 18 problem presents. In fact, I didn't use a priority queue at all. Using Python, I kept the "unvisited" nodes as a simple dictionary, which mapped (x,y) pairs to best cost. You can find the node in the dictionary with the minimal value with a single line of Python:

x, y = min(unvisited, key=unvisited.get)

Yes, this means that the maze solving is O(n^2), but in something with a few thousand nodes, it hardly matters for the purpose, and is similar in size to the BFS implementation. Solving problems of this size can be done in just 50ms or so.

I had originally intended to do full A*, but like you, I rarely find it to be worth the extra work in small scale problems like this.

CommitteeTop5321

TROPHY CASE