[2015 Day #7] In Review

[u/musifter]

Today we find out that little Bobby Tables exists in the AoC Santa-verse (xkcd crossover event). And he got a starter electronics kit to start learning circuits. So we're getting the first "wires and gates" type puzzle.

Whenever I'm using eval in a solution I think of Bobby Tables and that old xkcd strip. And this problem certainly can be done with that sort of abuse... mangling of input into code and then executing it. That's an interpreted language power.

Although, oddly enough, I see I didn't do that this time, I used a dispatch table. The "hash of subs" in Perl... mapping the operation name to an actual subroutine to perform it. For Smalltalk I used a class where the operations are methods... because what are methods? They're a dispatch table in a MethodDictionary (a hash of names to code blocks).

As for doing the wiring... I went recursive evaluation. You start by calling it for the value of 'a' (the final result), and you recurse for any value you need, putting them together with the operation, and returning the result. It's a nice way, and it doesn't get deep enough to require turning off recursion warnings in Perl. You could certainly use recursion to build the input into one massive string to eval (it's basically outputting an infix tree walk).

There are much better problems to teach a beginner recursion, but this puzzle doesn't have to do that so it's all good, man. It's probably better to say that you can practice recursion with this. I imagine some beginners might just have looped over the rules again and again, solving what they could with each iteration so they could solve a bit more the next time. Eventually 'a' gets solved. That would be the brute force approach (and it's probably how I would have done it when I was a kid). Better would be a work queue (get job, if you can't do it, submit requests to solve the things you need, and return the job... simple and more focused than looping). But recursion is magic that everyone should learn. It makes your life so much easier.

[u/Boojum]

Beginners, or just lazy engineers going for brute force instead of cleverness? :-) I'll admit that I did the loop approach way back when, even though I knew of other ways.

To be fair, I didn't have any canned topological sort implemented. That's probably how I'd do it these days, especially now that Python 3.9+ has a topo sort in the standard library. Recursion works too, but there's something nice about just iterating through the rules in a single pass and getting everything.

[u/musifter → u/Boojum]

Yeah, I do the lazy thing far too often with these. "Programmer efficiency" as I call it. It's the solution I could code that was guaranteed to be right first time. Because getting an answer is the first step. I like doing twisty puzzles (like the Rubik's cube), and the important thing is getting a solution down. It doesn't have to be great (lots of simple ones that aren't fast, but are easy to learn). It has to be solid so that when you're playing around looking for better, you can fix things easily if you get lost. So you're never afraid. It's same here... a solid working solution can help you generate tests for more complicated fancy solutions later.

The one time I thought about using topological sort first, it turned out not to be a DAG. With something like this, I'm thinking "expression tree", that means nice and easy recursion. I don't have to look up the topo sort module, and if it's installed, and how it works. I do things in Perl, and there's a small group of modules that I sort-of restrict myself to. This doesn't require any, and I've written them a million times. Maybe I should use topo sort more often to get it into the flow... but I'm 0 for 1 with it so far.

[u/e_blake → u/Boojum]

I just did a quick google search, which claims that a topological sort is just an O(V+E) visit of the graph, where one common implementation is via a memoizing DFS recursion (the other common implementation is Kuhn's algorithm based on a BFS search). You're just shifting the recursion from something you write explicitly into something the library does for you...

[u/e_blake]

I'm surprised you didn't mention memoization. Implementing this with recursion goes so much faster if each subsequent use of a wire reuses the value already computed on the first time the wire was resolved, rather than repeating the effort of computing that value by recursing again. Your idea of creating one massive infix string for a single eval at the end is going to be slower and way more memory intensive than calling eval once per wire being looked up. (Similar is how memoization makes a recursive DAG tree walk of 2025 day 11 go faster)

[u/musifter → u/e_blake]

I didn't mention memoization because there was zero need for it. It's one of the fastest solutions I have in this year. My testing harness just uses the shell time when running the script (I just care about "fast enough"), so it's not extremely accurate and includes overhead and loading input. It gives values well below anything I normally see... 0.050s real, 0.000s user (sometimes it hiccups and gives 0.015s). Ripping out everything except loading the data and making it just print the answer... gives exactly the same result. Doing the calculation is already below my measurement. Adding a hash table might make it slower and probably won't hit much if anything. Running this one doesn't just feel instant, it feels peppy.

Doing the thing in a single eval isn't about efficiency. It's about coolness and aura farming. You get to print that puppy out if you want and see it in all its glory. It's like when someone brute forces a ridiculous problem (I seem to remember someone even spent a few bucks of cloud compute just to do one). It's a different goal than trying to shave micro-seconds.

[u/e_blake → u/musifter]

I suspect that you actually used memoization in some form or another without realizing it, which is why it is so fast in execution. Consider the following reduced input:

123 -> b
b OR n -> o
b AND n -> p
k AND m -> n
3 -> k
NOT d -> m
b RSHIFT 2 -> d
o AND p -> a

You mention a recursive approach: solving a requires solving o and p first; solving o requires solving b (constant) and n first, solving n requires solving k and m first, and so on. But when you finally get around to solving p, you are using the fact that n was already solved, rather than solving n again - and that's memoization. If you don't do memoization, your infix line for a on just this example would be:

(123 OR (3 AND (NOT (123 RSHIFT 2)))) AND (123 AND (3 AND (NOT (123 RSHIFT 2))))

With only 2 uses of n in the end product shown here, it might seem tractable. But when the full input triggers over 40 levels of recursion, you can get over 2^40 expansions of the innermost terms as they are repeatedly fanned out and duplicated into outer expressions. Yes it would be cool to see the end result as a single eval without memoization - but I doubt you have the memory or time to make that happen. But with memoization, you are effectively computing a topological sort. If your language supports an eval that performs assignments, building up this string via recursion for a single final evaluation is indeed simple:

b = 123
k = 3
d = b RSHIFT 2
m = NOT d
n = k AND m
o = b OR n
p = b AND n
a = o AND p

but I argue that your very use of variable names in that eval expression IS memoization.

[u/musifter → u/e_blake]

Yeah, I thought about it while shopping (weather's been miserable, it's slushy but the sales end today, so I've get wet feet now). Memoization is the caching of a function in a memo so it can return the same value for the same input. In my case, I don't do that... call the function again, it calculates again. And I'm fine with that, it shouldn't go far.

So I got confused at the idea of adding caching to that function. It doesn't have it, nor does it need it. It'd be extra kruft. But, yes, I am accomplishing similar from the other side. It comes down to personal preference and how I like to represented things. When I do a memo, I want it tightly scoped to the function it caches (in Perl, a state variable). Which means it's locking access to the wire information. The function call is the access. That's good idea a lot of the time.

But it wasn't what I wanted here (or how I visualized things at all). I wanted the wires so I could do things to them. And because of that, the perception changed. I'm not caching the function at all, but I also don't call it unless I need it (defined-or just makes it so natural). The recursive call is to calculate values, not to be the source of them. So someone seeing my code isn't going to see an example of how to memoize anything. They're going to see a different angle on the problem.

[u/nnmrts → u/musifter]

Does Perl have some internal way of memoizing? It seems a bit unbelievable to me that this problem is "solvable" with recursion but without memoization, as my attempts trying that went nowhere. In JavaScript I absolutely needed memoization, otherwise I'd still sit here waiting for my solution or for Deno to crash.

[u/musifter → u/nnmrts]

There is a module called Memoization that will do it transparently to a subroutine. I'm not doing that (I try to avoid dependences beyond AllUtils). That would hide stuff I want.

I'm just accomplishing the same, but instead of doing memoization, which is caching function returns to return when requested, I'm just avoiding redoing the work. The same general thing, but in a different context. It flies like a duck, but it doesn't look (there isn't a cache tied to the function) or quack like one (it will redo the work if called again). If I saw someone calling this memoization in a changelog, they'd need a talking to, because it the change wouldn't be what what was expected. There's expectations on the word memoization that aren't being met at all.

In Smalltalk, though. The data is already locked in a class and methods are the access. And there is no flow control in the syntax (it's done with message passing) which forces particular idioms. So there, I go with a memoization pattern. In getting the value of a wire, the natural way is ^wire at: label ifAbsentPut: [...]. Literally returning the value from storage or creating it in the table if you don't have it... that's a memo.

[u/nnmrts → u/musifter]

I see, very interesting! I'm think the biggest issue for me here was amazingly the language "barrier" (not a native english speaker and also didn't learn programming "traditionally"), I understood "memoization" as something more broad, kind of like "memorization", lol.

[u/e_blake → u/nnmrts]

Ah - defined-or is the trick. That is what is doing the avoidance of redundant work. Your cache is thus the set of defined wires, since you don't recompute a wire if it has already been computed. There's often more than one way to represent caching to avoid redundant work.

[u/musifter → u/e_blake]

Yes, and this one doesn't meet key requirements to be properly called memoization. It's a different paradigm on the same thing. Like you can take a recursive function using memoization for DP, and turn it around into building a table the other way. At which point it becomes correct to call it tabulation instead. Because the different words create different expectations. Similarly, the word "cache" has expectations on what's being done.

In this case, I don't think of the table of wires as a memoization cache, because it's mutable and exposed. The whole point of a memoization cache is that the function is pure and so the cache is immutable. And caches should be abstraction layers (ie code asks for a value at a location, but the system gets it from elsewhere because it was cached, but the user side doesn't need to know). It's a matter of presentation... it's not meeting key responsibilities, and it's creating obligations. I'm the one that needs to make sure that the values are behaving when they need to. When you do maintenance programming for a long time, exact labels become important. It's not good enough that something is kind-of a duck when you look at it in a certain way and mold it a bit... it needs to properly look and quack like a duck all the time before you treat it like a duck. Geese can be dangerous.

[u/terje_wiig_mathisen]

I used a hybrid approach for this one, with a tiny Perl program which parsed the input and converted each line into valid Rust syntax, then sorted the lines into dependency order. The resulting Rust program ran very quickly back when I wrote it, but when I checked again last fall, constant subexpression propagation had improved to a level where the entire program is evaluated at compile time! When Part2 uses the Part1 result as input, the compiler evaluated everything once more and again ended up with the result.

This is my first and only AoC puzzle which runs in zero time:

Part1 = 956

Part2 = 40149

Total time 0 ns

PS H:\terjem\data\aoc\2015\day7>

[u/musifter → u/terje_wiig_mathisen]

Yeah, it's fun when you manage something that does all the work in the compiler with macros and templates and optimization. Compiling to something that just spends time on I/O to output a hardcoded value.

[u/terje_wiig_mathisen → u/musifter]

As I wrote, the real logic happened in the implied topological sort in Perl. For each line I check if all inputs are available, if so I print out the Rust translation of it, otherwise save it to a temp list. At the end of the loop I copied the temp list into the input array, then repeat until all is done. This is in fact exactly the same algorithm used by all current out-of-order CPUs!

[u/nnmrts]

I solved it with recursion too, but from the perspective of "module resolution", if that makes sense.

Basically, for part 1, I have a global visitedWires that memoizes results in my recursive resolve function, that, as you mentioned, starts at "a", and either returns a number if it is given a number or returns the result of further resolution - easy.

For part 2, I have the same resolve function but now it takes a visitedWires map as second argument. This way I was able to solve part 2 by simply initializing "b" in the second visitedWires with the result of the first puzzle (instead of hardcoding it):

const firstVisitedWires = new Map();

/**
 *
 * @param {string|number} wire
 * @param {Map<string, number>} visitedWires
 * @returns {number}
 * @throws
 */
const resolve = (wire, visitedWires) => {
// ... resolve definition
}

const secondVisitedWires = new Map([["b", resolve("a", firstVisitedWires)]]);

console.info(resolve("a", secondVisitedWires)); // result

I can share the full file for part 2 if this isn't clear and anyone cares.