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 meta, rant, opinion

[Rant?] Managing Frustrations Is More Important Than Managing Expectations

Every year, I see a plethora of books and articles affirming they can teach you how to manage your expectations - most of the time lowering them - because it's a source of unhappiness, and frustration.

In the current "mindfullness" boom, coupled with a pandemic that stresses everyone, it's not really a surprise that telling people to aim for attainable goals is popular. Why should a person add stress on top of stress by picking objectives they can't actually reach?

It irks me.

Now, of course no one should pursue truly impossible goals. But being told to "manage your expectations" puts squarely on your shoulders all the blame for being stressed, while failing to address the problem with your place in society. It reeks of "know your place" or "don't dream too big".

Most of the "expectations" aren't yours 🌍

We have customers, bosses, employees, colleagues, friends, and family who have expectations of us.

My current job is to make sure students that come into my care will leave it better prepared to work in the tech industry.

My expectations:

  • the students will trust me to know what's best for them, and (reluctantly, maybe) do what I suggest they do
  • the teachers working with me will trust me that I know what I'm doing
  • everyone involved will deal with the various inconveniences with good graces (the students will do their homework and be curious, and the teachers will be fair and uplifting)
  • I will have enough time in a day's work to deal with most emergencies

Everyone else's expectations:

  • the government, school staff, students (and their families) want me to design the classes in such a way that getting a job at the end is a guarantee
  • the school wants me to make sure the curriculum is attractive enough for prospects to sign up
  • the teachers want to have a decent environment, pay, and freedom to be flexible, so that they can impart their knowledge and experience to the next generation
  • the teachers want students prepared in advance to learn what they have to teach
  • the students want actionable knowledge - none of that philosophy and what-ifs - so that they can earn a living
  • the students want to have as much free time as possible, while being paid as much as possible
  • "the market" wants to be able to put ex-students to work as fast as possible, for a pay that's as low as possible
  • governmental rules want me to enforce regulations, such as attendance and other disciplinary actions
  • the students want me to bend the rules in their favor
  • "the market", and the students, and the school, want me to make sure that the curriculum in unmarred, and that only the "deserving" get their diploma
  • and
  • so
  • many
  • more

These are all high-level expectations, the nitty gritty is way more involved. And it's obvious that respecting all these is akin to squaring the circle.

So, "managing my expectations", in the way people have been explaining it to me over the last decades, would be to forego my expectations, or at least lower them enough, in order to make sure I can actually turn them into a reality. It says nothing about bucking against everyone else's expectations. I'm supposed to try and accomplish the goals that have been set for me by my superiors, and force people I have power over to do what they are supposed to, revising their expectations lower.

That definitely looks like a self-sustaining power structure to me, reinforced by a philosophy of "don't expect too much or you'll be sad". The higher up the chain, the more you can dream, because your dreams will become orders for others. "Manage your expectations" if you are not in a position of power.

Manage your frustrations 😤

You can't absolutely control others. My students will sometimes be "unable" to hand in homework. My teachers will sometimes be overwhelmed and forget to grade some papers. My hierarchy will sometimes forget that life outside of school exists for me too. My family will sometimes take affront at the time I devote to the pupils or the teachers.

It is frustrating, because a very large majority of people feel like they are already giving 110%, and my priorities aren't theirs.

An easy way out of that frustration is, indeed, to lower my expectations, and respect the letter of whatever law, rule, or guideline, I have to enforce. Passing the buck in terms of personal responsibility (I'm just "following orders"). I can also lower my expectations by leaving aside anything that would cost me extra energy, that isn't strictly mandated by someone in power.

And therein lies, for me, the crux of the semantics problem. By saying people should take upon themselves to "manage their expectations", even if your intention is pure and you are trying to protect their mental health, you are in essence telling them not to dream too big. It's a race to the bottom.

Collaboration doesn't work like that. Sure, personal goals rarely align perfectly, and everyone has goals outside of whatever we're working together on. But whenever humans are involved, compromise is the norm, and that means that everyone has to deal with a little bit of frustration.

Let's take a practical example: teaching a class about program design. It's one of these things that can be seen as a waste of time by a lot of people. Except, of course, by people who've learned the hard way that if a program isn't designed first, the future holds a metric ton of headaches.

  • the students don't have that experience, so they have no practical reason to spend hours learning something that goes contrary to what they know: a program either works or doesn't. Who cares if it's elegant?
  • "the market" wants them to be operational, which to them usually means fast, not spending hours seemingly doing nothing about writing code.
  • the school system isn't properly equipped for evaluating "grey area" skills. Since there is no "best" way to do something, how can anyone grade something like this?

The easy way out of this pickle is to remove that course entirely. The students are happy, "the market" is satisfied enough, the school system churns along.  Lower my expectations, right? Sure, the next generation will make the same mistakes over and over again, but they will eventually learn, graduating to senior positions in the process.

And my frustration about seeing and sometimes using badly designed software, about seeing good developers burnt out by constantly running after technical debt, about people who should have no business making technical decisions forcing bad ones on people for expediency's sake, and about users having to work around the products they use, is ultimately irrelevant. Because everyone will friggin manage their expectations.

Oooooooor... I use my frustration, and use it constructively to educate people about all that. I teach them that they should definitely not lower their expectations but demand better, even if they might not get it. I try to teach them that a little bit of frustration can be the impetus towards a better world. You're unsatisfied? Do better.

The Karen Paradox 🤬

People will point out that this is exactly what the Karens of the world do: they demand better than what they get.

That is true enough. They strive for better, which is a good thing, if you ignore everything that has to do with a context. But I would argue it's because they cannot manage their frustrations. They put their want of not having any frustration whatsoever before any other consideration, especially the frustrations of others.

This is different from having unwarranted frustrations. Sometimes, a Karen forces us to see a problem we weren't aware of, even if the problem in question is dealing with Karens.

By the way, I find it hilarious that a first name is used as a label. I apologize wholeheartedly to good-natured Karens out there... It's not your fault, I know. But it's also not the first time a first name has gathered a reputation for malice. It'll sort itself out in the end, we love the "Good Karens" still.

Manage your frustrations 😓

And so we come full circle: yes, managing your frustration does involve managing your expectations. Being frustrated at not being an astronaut, or rich, or famous, or whatever we feel we deserve shouldn't be that big of a deal, and maybe in some instances, managing expectations are a good way to manage our frustration.

But it lacks ambition. Exploration, research, innovation, charity, support, everything that's good about the human species stems from looking at a situation, being frustrated by it, and trying something else.

Mind you, a lot of things that are bad about the human species, such as greed, oppression, and the like, also stems from frustration (see the Karen Paradox above), but that's humans for you. They are complicated, and as much as the say they'd like everything to fit in neat boxes with clear delineations, they'll do their damned best to blur the lines the first opportunity they get.

As a long time player of various role playing games (pen and paper too, yes, you irreverent youngins), I like to think of my frustrations as belonging to two very distinct categories: those that stack, and those that don't.

Frustrations that stack tend to amplify each other, being connected to one another, and are usually harder to "fix". Frustrations that don't stack contribute to the overall level of stress and dissatisfaction, but are independent, and the "fix" can be anything from super easy to super hard to impossible. Factor in the "what can I do about it" part, and there's something of a path towards a better tomorrow that doesn't involve quitting or blindly following directives. It's never as well delineated as that.

Let's take an example: I'm late for a class, because the subway is stuck. I know that it means my class will be shorter, and since a good portion of the students haven't spent the necessary time to understand fully the last one (or indeed hand their homework in), it will be even shorter because of all the time we'll spend rehashing the same things. That, in turn, will mean they won't be as well prepared as I hoped for the rest of their studies, or indeed their professional lives.

First frustration: I'm late. People around me behave in a way that make me cringe because they are frustrated. The whole situation is really, really, annoying. I'm not going to yell at the driver or the subway staff (even if they might be able to do a better job at handling the situation, I'm sure they have their own set of things to deal with that I'm unaware of, not being, you know, educated in the art of making trains run on time). I could tell the guy next to me that him yelling in his phone that he'll be late prevents me from doing the same. Should I? Maybe, if the call lasts for ever, or if in a stroke of bad luck he actually starts running the meeting by yelling into his phone. Will it solve the problem, or create a new one?

I want to make sure the tardiness won't impact the class too much. Should I send a message to the class asking them to start working without me? Without guidance, it could be a waste of time, either because they won't do it seriously, or they won't know how to do it properly. If I flex my power and tell them it's going to be graded to ensure compliance, is it getting me closer to my goal? Will they be better professionals, and/or will they think that sometimes, people in power dish out punishment because they are frustrated? What if they all do it diligently but fail? If I keep the grade in their record, it can be really unfair to them, and they won't trust me much after that. And if I don't, don't I show them that it was just a power flex, and they can safely ignore the next one?

This is not one frustration, but a conflation of two. One that stacks (the impact on my students) and one that doesn't (the fact the subway is late). Recognizing that some things are beyond my control and therefore that the frustration I feel towards those things have to be endured is a good thing, in my mind. Maybe next time, I'll have a bigger margin for transport, or a good book to pass the time, or noise-cancelling ear pieces. But that frustration will come and go, and I refuse to let it affect my decisions towards the rest.

Second frustration: I need to get my students more curious, more involved, more industrious about the topic so that if I am unavailable for 15 minutes, it doesn't matter that much. This has nothing to do with the subway being late.

I want them to want to research the topic. I am frustrated that they don't see the point. Is it their fault? Probably to some extent, so I need to coerce them a bit, because I know they won't have a glorious revelation with a ticker-tape parade, lights and fanfare, out of the blue. But it's also my responsibility. Why don't they trust me that this is important? Have I not given enough proofs of that? Were they unconvincing ones? Maybe it's because this class is among many many others, and everyone is vying for their attention? Maybe it's because I keep telling them it's important, but I'm not showing why often enough?

This is a frustration that stacks: it has a direct impact on many other tasks that I have to do, will have an effect on the extra time I set aside for preparing classes, preparing exams and grading them, will impact how the colleagues see my work, my relationship with other teachers and school staff.

This is a frustration that should drive me to do better. I should treasure it as an engine of change. And, sure, if I lower my expectations, it'll go away, just like the memory that I was late once because the subway was not moving. And maybe I'll be happier. Or at least less stressed.

We progress by being unhappy about our current situation and doing something about it. Not by shifting the responsibility onto someone else fully (as opposed to Karens), and definitely not by going all fatalistic and aiming only for what we're guaranteed of getting.

Frustration is a good thing (in moderation) 🤔

Look, we all know the rush of being validated, of having things go our way, of being right.

Some of us know that the pleasure of gratification is even better if we had to overcome something in order to get it. We're not talking sexual kinks here, although they are definitely a good indicator that this is a real thing.

There is a reason why so many people like brain teasers, word games, sports competitions, etc. There is a reason why the 3 acts are such a staple of stories in every culture. Without obstacles, where is the reward?

I tell the students that there are very few pleasures more satisfying than working on a bug for a few hours or days and suddenly finding a solution. You feel smart, tall, handsome and powerful, afterwards.

That satisfaction doesn't happen if the process is:
- realizing there is a problem
- looking the solution up
- applying the solution blindly
- end of the problem

I mean, a lot of life is like that, and that's ok, but I don't think it gives pleasure to people. It is frustration without a satisfactory ending. Sure, the job gets done, but machines will do that better than us, eventually.

on swift, coding, CS, opinion, oss

[Dev Diary] Vanilla Is The Best Flavor

I have a weird thing with the multiplication of command-line tools and gizmos: I forget them.

Do I want to run supercool gitlab commands? Hell yea! Do I need to install 12 utilities (or code a new one) to archive every project older than a year? I hope not...

The setup

I am a sucker for well documented fully linted code. But the thing is, all the gizmos that help me do that have to be installed in the system or in my ~/bin and I have to remember to update them, and I have to install them on my CD machine, and on every new environment I setup, and make sure they are still compatible with the toolchain, and it freaks me out, ok?

Plus,watching the students try to do it is painful.

So, given a 100% vanilla swift-capable environment, can I manage to run documentation and linting?

The idea

We have Swift Package Manager, which is now a first-class citizen in XCode, but it can't run shell script phases without some nasty hacks.

What if some targets were (wait for it) built to do the documentation and the linting?

Linting

One of the most popular linters out there is swiftlint, and it supports SPM. It can also build a library instead of an executable, which means one of my targets could just run the linting and output it in the terminal.

In the Package.swift file, all I needed to do was add the right dependency, and the right product and voila!

let package = Package(
	name: "WonderfulPackage",
    products: [
    	// ...
         .executable(name: "Lint", targets: ["Lint"])
   	],
    dependencies: [
        // Dependencies declare other packages that this package depends on.
        // .package(url: /* package url */, from: "1.0.0"),
		// ... normal dependencies
        .package(url: "https://github.com/realm/SwiftLint", from: "0.39.0")
    ],
    targets: [
    	// ... normal targets
        .target(
            name: "Lint",
            dependencies: ["SwiftLintFramework"]),
	]
)
Package.swift

Now, SPM is very strict with paths, so I had to put a file named main.swift in the Sources/<target>/ directory, in this case Sources/Lint.

Running the linter is fairly straightforward, and goes in the main.swift file:

// Lint command main
// runs SourceDocs
import Foundation
import SwiftLintFramework

let config = Configuration(path: FileManager.default.currentDirectoryPath+"/.swiftlint.yml",
                           rootPath: FileManager.default.currentDirectoryPath,
                           optional: true,
                           quiet: true,
                           enableAllRules: false,
                           cachePath: nil,
                           customRulesIdentifiers: [])

for lintable in config.lintableFiles(inPath: FileManager.default.currentDirectoryPath, forceExclude: false) {
    let linter = Linter(file: lintable, configuration: config)
    let storage = RuleStorage()
    let collected = linter.collect(into: storage)
    let violations = collected.styleViolations(using: storage)
    if !violations.isEmpty {
        print(EmojiReporter.generateReport(violations))
    }
}

print("🎉 All done!")
Sources/Lint/main.swift

Setup the .swiftlint file as usual, and run the command via swift run Lint

Sources/WonderfulPackage/main.swift
⛔️ Line 15: Variable name should be between 3 and 40 characters long: 'f'
⚠️ Line 13: Arguments can be omitted when matching enums with associated types if they are not used.
⚠️ Line 12: Line should be 120 characters or less: currently 143 characters

Documentation

Documentation is actually trickier, because most documentation tools out there aren't built in swift, or compatible with SPM. Doxygen and jazzy are great, but they don't fit my needs.

I found a project that was extremely promising called SourceDocs by Eneko Alonso, but it isn't a library, so I had to fork it and make it into one (while providing a second target to generate the executable if needed). One weird issue is that SPM doesn't like subtargets to bear the same name so I had to rename a couple of them to avoid conflict with Swift Argument Parser (long story).

I finally found myself in the same spot than with the linter. All I needed to do was create another target, and Bob's you're uncle. Well actually he was mine. I digress.

let package = Package(
	name: "WonderfulPackage",
    products: [
    	// ...
         .executable(name: "Docs", targets: ["Docs"])
   	],
    dependencies: [
        // Dependencies declare other packages that this package depends on.
        // .package(url: /* package url */, from: "1.0.0"),
		// ... normal dependencies
        .package(url: "https://github.com/krugazor/SourceDocs", from: "0.7.0")
    ],
    targets: [
    	// ... normal targets
        .target(
            name: "Docs",
            dependencies: ["sourcedocslib"])
	]
)
Package.swift

Another well-placed main file:

// Docs command main
// runs SourceDocs
import Foundation
import SourceDocs

do {
    switch try SourceDocs().runOnSPM(moduleName: "WonderfulPackage",
                                     outputDirectory: FileManager.default.currentDirectoryPath+"/Documentation") {
    case .success:
        print("Successful run of the documentation phase")
    case .failure(let failure):
        print(failure.localizedDescription)
    }
} catch {
    print(error.localizedDescription)
}
Sources/Docs/main.swift

Now, the command swift run Docs generates the markdown documentation in the Documentation directory.

Parsing main.swift (1/1)
Removing reference documentation at 'WonderfulPackage/Documentation/KituraStarter'... ✔
Generating Markdown documentation...
  Writing documentation file: WonderfulPackage/Documentation/WonderfulPackage/structs/WonderfulPackage.md ✔
  Writing documentation file: WonderfulPackage/Documentation/WonderfulPackage/README.md ✔
Done 🎉
Successful run of the documentation phase

Conclusion

✅ Vanilla swift environment
✅ No install needed
✅ Works on Linux and MacOS
✅ Integrated into SPM
⚠️ When running in XCode, the current directory is always wonky for packages

on rant, opinion, oss

DocumentDB vs MongoDB

From AWS gives open source the middle finger:

Bypassing  MongoDB’s licensing by going for API comparability, given that  AWS  knows exactly why MongoDB did that, was always going to be a   controversial move and won’t endear the company to the open-source   community.

MongoDB is hugely popular, although entirely  for the wrong reasons in my mind, and it's kind of hard to scale it up  without infrastructure expertise, which is why it makes sense for a  company to offer some kind of a turnkey solution. Going for  compatibility rather than using the original code also makes a lot of  sense when you're an infrastructure-oriented business, because your own  code tends to be more tailored to your specific resources.

But in  terms of how-it-looks, after having repeatedly been accused of leeching  off open-source, this isn't great. One of the richest services divisions  out there, offloading R&D to the OSS community, then, once the  concept proves to be a potential goldmine, undercutting the original?

The  global trend of big companies is to acknowledge the influence of  open-source in our field and give back. Some do it because they believe  in it, some because they benefit from fresh (or unpaid) eyes, some  because of "optics" (newest trendy term for "public relations"). I'm not  sure that being branded as the only OSS-hostile name in the biz' is a  wise move.