on algorithms, coding, CS, maths, meta, opinion, programming

[AoC 2022] Recap

TL;DR

I'm not as rusty as I thought I'd be. And YES that kind of challenge has a place in the coding world (see conclusion)

Just like every year, I had a blast banging my head on the Advent of Code calendar. It so happens that this year, I had a lot less brain power to focus on them due to the exam season at school and the ensuing panicky students, but it could also be because my brain isn't up to spec.

Some of my students are/were doing the challenges, so I didn't want to post anything that would help them, but now that the year is almost over, I wanted to go over the puzzles and give out impressions (and maybe hints).

Easing in

Days 1 to 7 were mostly about setting up the stage, getting into the habit of parsing the input and using the right kind of structure to store the data.

Nothing super hard, it was "just" lists, hashmaps, and trees, until day 4. Day 4 was especially funny to me, because I wrote HoledRange / Domain just for that purpose (disjointed ranges and operations on them). Except I decided to do this year's calendar in Julia, and the library I wrote is for Swift. Just for kicks, I rewrote parts of the library, and I might even publish it.

Days 5, 6 and 7 highlighted the use of stacks, strings, and trees again. Nothing too hard.

Getting harder

My next favorite is day 9. It's about a piece of rope you drag the head of, and have to figure out what the tail does. If you've ever played zig-zaging a shoelace you'll know what I mean. String physics are fun, especially in inelastic cases.

Many ways to do that, but once you realize how the tail catches up to the head when the latter is moved, multi-segmented chains are just a recursive application of the same.

I was waiting for a day 10-like puzzle, as there tends to be one every year, and I majored in compilers all those years ago. State machines, yuuuuuusssssssss.

A lot of puzzles involve path finding after that, which isn't my strong suit for some reason. But since the algorithms are already out there (it was really funny to see the spike in google searches for Dijkstra and A*), it's "just" a matter of encoding the nodes and the edges in a way that works.

Day 13 is fun, if only because it can be instantly solved in some language with eval, which will treat the input as a program. I still wrote my own comparison functions, because I like manipulating numbers, lists and inequalities.

Day 14 is "sand simulation", that is grains of sand that settle in a conical shape that keeps expanding laterally. Once you find the landing point on each ledge and the maximum width of the pile, there's a calculable result. Otherwise, running the simulation works too, there aren't that many grains. For part 2, I just counted the holes rather than the grains.

Day 15 is about union and intersections of disjointed ranges again, except in 2D. Which, with the Manhattan distance approximation, gets back to 1D fairly quickly.

Day 16 stumped quite a few people, because of the explosive nature of path searching. Combinatorics are pretty hard to wrap your head around. Personally, I went for "reachability" within the remaining time, constructed my graph, and explored. It was probably non optimal.

Day 17 make me inordinately proud. Nuff said.

Catching up

Because of the aforementioned  workload, I was late by that point, so I decided to take my time and not complete the challenge by Xmas. Puzzles were getting hard, work was time-consuming, so the pressure needed to go down.

Because of the 3D background that I had, I tackled day 18 with raytracing, which is way over-engineered, but reminded me of the good ole times. Part 2 was trickier with that method, because suddenly I had 2 kinds of "inside".

Day 19 was path finding again, the trick being how to prune paths that didn't lead in a good direction. Probably the one that used up the most memory, and therefore the one I failed the most.

Because of my relative newness to Julia, I had to go through many hoops to solve day 20. As it turns out, screw_dog over on mastodon gave me the bit I lacked to solve it simply, although way after I solved it using other means.

Day 21 goes back to my compiler roots and tree optimizations, and Julia makes the huge integer manipulation relatively easy, so, there. Pretty proud of my solution:

Part 1:   3.709 ms (31291 allocations: 1.94 MiB)
Part 2:   4.086 ms (31544 allocations: 1.95 MiB)

Which, on my relatively slow mac mini is not bad at all! Symbolic linear equation solving (degree one, okay) is a fun thing to think about. I even think that the algorithm I devised would work on trees where the unknown appears on both sides of the tree. Maybe I'll test it some day.

Day 22. Aaaaaaaah day 22. Linked lists get you all the way if and only if you know how to fold a cube from a 2D pattern. I don't so, as many of the other participants, I hardcoded the folding. A general solution just eluded me. It's on my todo list of reading for later.

Day 23 is an interesting variant of Conway's Game of Life, and I don't believe there is a way to simplify a straight up simulation, but I fully accept I could be wrong. So I used no trick, and let the thing run for 40s to get the result.

Day 24 was especially interesting for me, for all the wrong reasons. As I mentioned, graph traversal isn't my forte. But the problem was setup in a way that "worked" for me: pruning useless paths was relatively easy, so the problem space didn't explode too quickly. I guess I should use the same method on previous puzzles that I was super clumsy with.

Finally day 25 is a straight up algorithmic base conversion problem that's a lot of fun for my brain. If you remember how carry works when adding or subtracting numbers, it's not a big challenge, but thinking in base 5 can trip you up.

Conclusion

I honestly didn't believe I could hack it this year. I don't routinely do that kind of problem anymore, I have a lot of things going on at school, on top of dealing with the long tail of Covid and its effects on education. Family life was a bit busy with health issues (nothing life threatening, but still time consuming), and the precious little free time that I had was sure to be insufficient for AoC.

I'm glad I persevered, even if it took me longer than I wished it had. I'm glad I learned how to use Julia better. And I'm happy I can still hack it.

I see here and there grumblings about formal computer science. During and after AoC, I see posts, tweets, toots, etc, saying that the "l33t c0d3" is useless in practical, day-to-day, professional development. Big O notation, formal analysis, made up puzzles that take you into voluntarily difficult territories, all these things aren't a reflection of the skills that are needed nowadays to write good apps, to make good websites, and so on.

It's true. Ish.

You can write code that works without any kind of formal training. Today's computing power and memory availability makes optimization largely irrelevant unless you are working with games or embedded systems, or maybe data science. I mean, we can use 4GB of temporary memory for like 1/4 of a second to parse and apply that 100kB json file, and it has close to no impact on the perceived speed of our app, right? Right. And most of the clever algorithms are part of the standard library anyway, or easily findable.

The problem, as usual, is at scale. The proof-of-concept, prototype, or even 1.0 version, of the program may very well work just fine with the first 100 users, or 1000 or whatever the metric is for success. Once everything takes longer than it should, there are only 3 solutions:

  • rely on bigger machines, which may work for a time, but ultimately does not address the problem
  • scale things horizontally, which poses huge synchronization issues between the shards
  • reduce the technical debt, which is really hard

The first two rely on compute power being relatively cheap. And most of us know about the perils of infrastructure costs. That meme regularly makes the rounds.

It's not about whether you personally can solve some artificially hard problem using smart techniques, so that's ok if you can't do every puzzle in AoC or other coding challenges. It's not about flexing with your big brain capable of intuiting the bigO complexity of a piece of code. It's about being able to think about these problems in a way that challenges how you would normally do it. It's about expanding your intuition and your knowledge about the field you decided to work in.

It's perfectly OK for an architect to build only 1 or 2 level houses, there's no shame in it. But if that architect ever wants to build a 20+ stories building, the way to approach the problem is different.

Same deal with computer stuff. Learning is part of the experience.

on algorithms, CS, coding, maths, programming

[Dev Diaries] Advent of Code

I've been really interested in Julia for a while now, tinkering here and there with its quirks and capabilities.

This year, I've decided to try and do the whole of Advent of Code using that language.

First impressions are pretty good:
- map, reduce, and list/array management in general are really nice, being first-class citizens. I might even get over the fact that indices start at 1
- automatic multithreading when iterating over collections means that some of these operations are pretty speedy
- it's included in standard jupyterhub images, meaning that my server install gives me access to a Julia environment if I am not at my computer for some reason

Now it's kind of hard to teach old dogs new tricks, so I'm sure I misuse some of the features by thinking in "other languages". We'll see, but 4 days in, I'm still fairly confident.

on swift, algorithms, holedrange, oss

[HoledRange] Sequences and Transformations

HoledRange has reached v 0.1.3 with two additions:

  • Iterating over ranges (contributed by Hugo a.k.a. Zyigh)
  • Transforming ranges into other ranges
Transformations

Simple idea, full of tricks: how do I apply a function f to transform a domain?

  • It has to result to a possible bound value for the domain (ie Hashable & Comparable)
  • We need to check the ordering of the new values in case the transformation flips the sign (eg [0;1] -> [-1;0])
  • We need to optimize the storage as we go in case the transformation collapses holes

on algorithms, swift, CS

Algorithm Of The Day : Combinatory

So, I'd like to take x elements out of an array of n elements. I know from statistical analysis that there are a precise number of combinations:

$$ \frac{n!}{x!.(n-x)!} $$

But what are they? There are a few classic algorithms to do that, but most of them are recursive and use an accumulator, not exactly Swift's forte, especially if you don't know the right keyword. Cue inout

So here's the rough idea: every time we select an item in the array, we have only n-1 items to pick from, and x-1 items to pick. So it's recursive in nature. But we have an array, which means that we can make every possible combinations using the first item in the array first, then start again by removing the first item, and we should never repeat the combinations.

Here's an example: let's take 3 elements out of an array of 4

John Paul Ringo George

----------------------

John Paul Ringo
John Paul       George
John      Ringo George
     Paul Ringo George

It definitely looks like loops: We do all of John's first, then when we're done we do Paul's, and then we're done because we don't have enough people to start with Ringo.

Another way of looking at it is "I've selected John, now start again with the rest of the list and pick 2", then "I've selected Paul, now start again with the rest of the list and pick 1", then "I've started with Ringo, now start again with the rest of the list and pick 1". When we're done with the lists starting with John, we remove him, start with Paul, and there's only one choice.

In swift, because of the extension mechanism, it's easy to generalize to every array, but we still need that recursion that needs both where we are and what's left to work. Then all we need to manage is the special edge cases:

  • there is no element in the array (because it's easy to deal with)
  • there is less elements in the array than we want (ditto)
  • there is exactly as many elements in the array as we want (well duh, there's only one possibility)

So here is the algorithm, with accumulators passed with inout (to modify them in the callee and the caller):

extension Array { // combinatory
    fileprivate func recArrangements(len: Int, start: Int, cur: inout [Element], result : inout [[Element]]) {
        if len == 0 {
            result.append([Element](cur))
        } else {
            var i = start
            while i <= (self.count-len) {
                cur[cur.count - len] = self[i]
                recArrangements(len: len-1, start: i+1, cur: &cur, result: &result)
                i += 1
            }
        }
    }
    
    func arrangements(of number: Int) -> [[Element]]? {
        if self.count == 0 { return nil }
        else if number > self.count { return nil }
        else if number == self.count { return [self] }
        var buffer = [Element](repeating: self[0], count: number)
        var result = [[Element]]()
        recArrangements(len: number, start: 0, cur: &buffer, result: &result)
        return result
    }
}

Proofs that it works:

> ["John", "Paul", "Ringo", "George"].arrangements(of: 3)
$R0: [[String]]? = 4 values {
  [0] = 3 values {
    [0] = "John"
    [1] = "Paul"
    [2] = "Ringo"
  }
  [1] = 3 values {
    [0] = "John"
    [1] = "Paul"
    [2] = "George"
  }
  [2] = 3 values {
    [0] = "John"
    [1] = "Ringo"
    [2] = "George"
  }
  [3] = 3 values {
    [0] = "Paul"
    [1] = "Ringo"
    [2] = "George"
  }
}
["Potassium",
"Calcium",
"Scandium",
"Titanium",
"Vanadium",
"Chromium",
"Manganese",
"Iron",
"Cobalt",
"Nickel",
"Copper",
"Zinc",
"Gallium",
"Germanium",
"Arsenic",
"Selenium",
"Bromine",
"Krypton"].arrangements(of: 3).count
$R1: Int? = 43758

Which fits $$\frac{18!}{8!.10!}=43758$$

Unfortunately, as with most recursive algorithms, its complexity is fairly horrendous... It is equivalent to 3 nested for loops (the way to write that code is left as an exercise), which means a whopping n³... Then again, combinatory has a way of being exponential anyways. I wonder if there is a way to be more efficient.