#then tested the work I��ve been debugging all week and guess what… it works now and i didn’t do anything.?

[oliverpdaniel]

Advent of Code 2020: A (very timely and not late at all) Reflection on Days 15-25

...Um. Oops?

Honestly, everything has been happening so much lately, I'm not super frustrated that it's been a clean month between finishing these puzzles and commenting on them. During these weeks, along with finally finishing my first-ever Advent of Code (as did my roommate! Well done, buddy.), I also wrapped up my second semester in quarantine, including a few brutal final projects and exams. After a nail-biting few weeks of awaiting grades, I finally had the confidence to withdraw for the second semester, and to begin hunting for work. (If you're reading this and I'm not hired yet, hire me!)

Anyway, the obvious downside to the sheer magnitude of the delay is that most of these puzzles aren't super fresh in my head, and thus my commentaries may not be as detailed as I would like. Hey - if I ever get such a massive executive-dysfunction-killing buzz as I did over the winter break to finally clean and redecorate my room, maybe I'll revisit these too.

Day 15: Now we're seeing some REAL slowness! The primary data structure for both parts here was the dictionary, mapping "seen" (spoken) numbers to the last turn on which they were spoken. That being said, I don't know what I was thinking in Part 1, with code like this:

Code ``` for k in seen.keys(): seen[k] += 1 ```

As soon as I saw the spicy thirty million in Part 2, I knew my naive solution wouldn't even touch it. [1] I had to do my least favourite thing - off-by-one debugging, but I ultimately came up with a relatively clever insight:

Spoilers Storing not just the last turn on which a number was spoken, but the last *two* numbers (if they exist). Doing this allows for a three-case scenario, for some current number `curr`: 1. `seen[curr]` is empty or doesn't exist. This is the base case of a new number; output 0, as stated in the problem. 2. `seen[curr]` has 1 value. It's only been seen once, so we can calculate the number of turns since it was last seen. 3. `seen[curr]` has 2 values. This number has been seen twice, so we can simply subtract the first- and second-most recent turn numbers to get the gap between them!

This problem took a bit of fiddling, but runs okay. Python really shows its ugly side here, as even a fairly efficient solution like this one, using efficient data structures, takes quite a while on Part 2.

Day 16: Boy oh boy. I spent far too long on this one, and perhaps if there are any to revisit for a future post, it's this one. My solution for this one features no less than:

regex;

closure functions;

constraint satisfaction;

functions that return tuples of variable length; and

walrus operators.

I consider this problem a 'sweat' for future years; I learned a lot about what makes constraint-satisfaction engines tick, and how it's important to assign constraints to the smallest possible element of a search space (here a column, rather than an entire permutation of columns). I think there's a much more concise and semantic way of outlining this problem, that lets the solver do much more of the work than I did.

Day 17: Not much to say here; it's a cellular automaton with extra for loops. I'll share two cute things that I'm proud of:

Spoilers 1. I experimented with various thresholds for the size of the 'infinite' space, making specifically sure not to to index checks, so that I could have the smallest possible subspace to check over. I ended up settling on a value of `20` units in each direction from: 2. the origin I specified, which is simply `LIMIT // 2 - H // 2` (where `H` is just the dimension of the input grid).

My roommate complained that it took him a long time to parse and understand the problem; I'll confess that I barely read it. I guess that's the advantage of experience, in that I saw "Conway" and "space" and knew immediately what needed to be done.

I didn't do anything special for Part 2; it's just my Part 1 code, copied and pasted, with an extra for loop here and a variable there. sum(sum(sum(sum())))s for everyone!

Day 18: I think that, out of all 49 unique problems in this year's Advent of Code, I'm most proud of my solution to this one. It's (relatively) fast; the code is pretty easy to read and works for both parts (and more! [2]); and I came up with a solution before knowing the name for what I had built. (Update: it's a shift-reduce parser. Hooray for stacks!) One especially cute thing, that incidentally ended up defining my approach to a lot of the later problems, was

Spoilers creating a lookup table between a certain input symbol, here math operators, and an internal function, here the builtin `int` math functors. This allowed for a dead-simple evaluator function, for when the top of the stack was ready to be converted from an expression to a workable number. Also, I had the bright idea to recursively evaluate bracketed expressions, in such a way that an expression like `(((1 + 2)))` would quickly reduce down to `1 + 2` before the rest of the parser got to it.

Day 19: Aaaaaaaaargh! Herein begin the Two Days of Terror - the two hardest problems. Lucky I had returned from my partner's by now, as I think they would have been quite upset with how much I was ignoring them to code. After solving Part 1 in the morning I finally finished Part 2 at around 7pm, having forgotten to otherwise eat or attack my household responsibilities, and only after my roommate sat down with me and pair-programmed for a while. This one stung the most, because... I'm a linguist, for crying out loud! No generative grammar problem, especially ones over a finite search space like this, should be causing me such grief.

Day 20: I am still emotionally recovering from this problem. My roommate somehow managed to get both parts to run instantly, using the most cursed CSP setup I've ever seen. I still need to study his code better to understand just how he did it. Also, his usage of scientific Python packages finally shows its rewards, as convolution over a matrix is a friggin' builtin function. Grr.

Day 21: I consider this day an apology for the previous Days of Terror. Some fun, but not terribly difficult, set-fu. My relative inexperience with set theory shows its stripes here; I'm sure there are much more semantically sound ways of accomplishing what I tried to do here (e.g., manually removing an allergen from each ingredient's list of hypotheses once it was confirmed to go with a certain ingredient).

Day 22: Spicy spicy numbers! It would have served me much better to read the instructions before starting, as then I would have known that

Spoilers in Part 2, players don't take their entire deck with them. Since, y'know, that would just cause an infinite race to the bottom.

Day 23: Even spicier numbers! If you're going to be cute like me and establish 9 as a constant, make sure that you don't use it in Part 2 when constructing the initial circle, or you'll wonder why 9,999,990 of the cups aren't attached to anything.

Day 24: I couldn't sleep, so I solved this problem at 3 in the morning. Not going to lie, a little disappointing for a penultimate problem, especially Part 2. Part 1 required at least a modicum of cleverness to develop a meaningful coordinate system, but then Part 2 just felt like a relative rehash of the Conway Cubes problem. 3 cellular automaton problems out of 25 is a little bit much, considering how formulaic they can be.

Day 25: As true evidence of how much I learned over this Advent of Code, I was able to finish Day 25 on the couch without even bothering my partner. Utilizing what I had learned about pow made defining the transform (i.e., repeated multiplication and mod) incredibly easy. Though, I did get a little bit lucky, due to a small oversight in problem setting...

Spoilers Rather than having to generate and test a whole bunch of different pairs of loop sizes for the card and the door, it turns out that if you `zip` together two streams of all such valid loop sizes for the card and door, respectively, the correct size for both (i.e, the solution) appears at the same time; for me, just the second such pair of sizes.

Day 25 Part 2, as always, was a delight and a pleasure. If you've never clicked that final button before, crack open a text editor and start solving challenges until you can. It's deeply satisfying.

I cannot sufficiently express my gratitude to the entire AoC team, setters, testers, and maintainers alike, for all that they do. A daily stream of bite-sized (or, sometimes, sea-monster-sized) challenges is just what I need to keep me going, and my skills sharp, over the dreary holiday season. Especially in a year like this, it was just what I needed to keep me moving, motivated, and thinking about code. I can't wait for next year's challenges and, hopefully, I'll convince the roomies to do it with me again.

Sorry about the little delay, and the relative lack of detail. But, the enemy of perfect is good enough. If you're reading these at some point in the distal future, I hope you've enjoyed watching my journey through these problems, and maybe learned a little bit about what it means to think like a programmer. Thanks for tuning in!

[1]: I tried it anyway; it obviously didn't work. And, once my roommate turned me onto tqdm, I was able to see just how long before the Heat Death of the Universe for it to run. It was about 3 days. Lol.

[2]: The way I constructed the code, it would be extremely easy to add in the remaining integer operations.

[impurelight]

Two Weeks With Flutter

For the two last weeks I've been playing around with Flutter which is a framework for building Android and iOS apps (it also has Web/Windows/Mac/Linux/ChromeOS support in development). And I really like it. I mean, I didn't always like it. When I first picked it up I thought it was needlessly complicated and frustrating. But as I started to learn what the things actually did I started to think it wasn't so bad. It might even be fun. But I guess that's the way with most programming frameworks.

So Flutter makes Android and iOS apps. How'd you expect it to do this? Probably something like HTML, right? Nope. Flutter uses Dart. The way it knows what to build is you have to override the the build() method and make it return your entire UI. The entire UI in one method. Yeah... that's going to get messy fast. Just take a look at one of my build() methods.

Widget build(BuildContext context) { return Scaffold( body: SafeArea( child: Stack( children: <widget>[ FutureBuilder<list>>( future: DatabaseManager.getAllTasksAsTasks(), builder: (BuildContext context, AsyncSnapshot<list>> tasks) { if (tasks.hasData) { return ReorderableListView( children: createWidgets(tasks.data), onReorder: (int start, int current) {}, ); } else { return Center(child: CircularProgressIndicator()); } }, ), Container(color: Color.fromRGBO(0, 0, 0, 0.4)), Hero( tag: "TaskCreate", child: new AlertDialog( title: const Text('Create Task'), content: new TextField( controller: textController, autofocus: true, ), actions: <widget>[ new FlatButton( onPressed: () { Navigator.of(context).pop(); }, textColor: Theme.of(context).primaryColor, child: const Text('Create'), ), ], )), ]// This trailing comma makes auto-formatting nicer for build methods. ) ) ); }

Yeah, I tried to move some things to their own methods (or classes which is more performant but you really only have to worry about that once you call setState()) but there's only so much you can do and so much you have time to do. If some normal person saw this they would probably say it's ugly. And to be honest when I first saw something like this I thought it was ugly too. It's even more messy if you try adding something to it. Paste your text, watch the entire thing go red, then try to add the end bracket in just the right spot (although a better way appears to be cut the old code, create the old container, and paste the old code). But as I got to know how it worked there was something actually pretty elegant about this.

It's sort of like designing something with Legos. You have your root UI, your scaffold, and that can have a child which is a list view and a floating action button. Only instead of Legos they're widgets. There's widgets for almost everything: list views, cards, centered content, images, text, etc. And if you can't find a widget that serves your purposes you can find one on pub.dev or code your own.

So apart from Widgets there's scenes... no views... I mean routes. OK, different frameworks call them different things. Basically just a page of your app. In Flutter they're called routes. In Unity they're called scenes. And the way Flutter handles routes is pretty interesting. It's like a stack of routes. When you go to a new route you call .push() and when you want to go back or if someone hits the back button .pop() is called.

It's pretty simple. But the code to create one of these routes is not. Like look at this:

class TaskRoute extends StatefulWidget { TaskState createState() => TaskState(); } class TaskState extends State<taskroute> { ... }

Every single time we want to create a new route/widget class. Why do we need all this boilerplate? Why do we need Stateful/State/Stateless (not pictured). I think it's for optimization or something but it's still annoying.

So now I should probably talk about the language Dart. Oh, Dart. It's not a bad language. Not as bad as Javascript anyways. The best way to describe Dart is to say it's a modern COOL (C-like Object Oriented Language) similar to other COOL's like C# and Java. Emphasis on modern. So as languages mature there's a tendency of adding random syntactic 'sugar' that no one really needs or asked for that only serve to alienate newcomers to the language. Like take C++. C with classes, right? Nope. Now it's this giant behemoth of a language that takes ages to compile. And I've noticed the same thing with C#. In fact most of the newer syntactic sugar additions to C# are in Dart. Almost as if the Dart team is copying from C#. Hmm...

And this is a particular sore spot for Dart which has a million ways to do everything.

So take typing. There is static typing which means the compiler knows the types of everything at compile time and can alert you of any problems. Then there's hipster typing which means you're going to get a nasty surprise when you run that line of code you haven't tested yet. So which one do you expect Dart to choose? Trick question, Dart uses both. And different tutorials use one or the other. It can make it seem like a tutorial is written in a different language.

And it's not even like some dedicated keyword. This is the difference between static typing and hipster typing in Dart:

// Statically typed; will not compile var myVar = "Hi"; myVar = 5; // Hipster typed; will compile var myVar; myVar = "Hi"; myVar = 5;

Also: allocating new object. You can define new objects (oh, and by the way everything is a reference type in Dart) using the new keyword. But you don't have to use the keyword. It's completely optional. Which, why even have the keyword? Also it's possible to define a method that returns something without actually returning. I mean, you get a warning if you do that but it'll compile just fine. There's also a bunch of weird syntax like Dog({this.id, this.name, this.age}). This is basically the same as saying:

Dog(int id, String name, int age) { this.id = id; this.name = name; this.age = age; }

And there's a large amount of using functional map-like syntax instead of for loops. You know, the standard syntactic sugar stuff.

So syntactic sugar isn't in and of itself bad. The problem is when you have so much syntactic sugar it gives you syntactic diabetes meaning the language gets so inconsistent that it is difficult for new comers to learn. This is definitely a problem for Dart: one tutorial might use the new keyword and explicitly type all their variables. Then the next tutorial might not do any of that and it gets very confusing very fast.

But it's not all bad. There are a few neat things you can do in Dart. For one there's no public or private. To make something private by starting it with an _. It sort of reminds me of Python where you make a function by just indenting. I think it's pretty neat. Also you can have named constructors. It's pretty cool as you can name a constructor something like FromDatabase(Map<string dynamic>) if you just read from a database.

There's also two type of exceptions: error and exception. Error is bad, you should not be getting errors. Exceptions are, well, exceptions. So just catch them normally. I don't really know the difference between these two though. There are assert which is only called in debug builds. Oh, yeah, Flutter compiles to a debug build by default but there are also release and profiling builds.

Also when defining a list, which you'll do a lot in Flutter, every element can end in a comma, even the last one. This is something I've been thinking about whenever I code outside of an IDE. Adding a comma when there shouldn't be one results in a lot of compiler bugs (or in the case of hipster languages runtime bugs). So I think putting a comma after every item, even the last item is the way to go.

Lastly there is Future and async. A function signature that implements these is something like:

Future<list>> getTasks() async

and then you call it like:

tasks = await getTasks();

This is a major thing in Flutter. The main way I use it is when I push another route. I say something like await push() and that stops executing until the route being pushed calls pop(). And then I can do whatever management I need to make sure the data is saved.

Another way this comes into play is I can use an async method to load a database.

Although, to be honest, I sort of think this feature is a little superfluous. Especially in the database example. Reading from the database is so fast that stopping the whole app as the database returns its results is likely good enough. And the poping of pages could be done with a callback instead.

So how is it to actually develop for Flutter? Pretty good, actually. The first major feature of Flutter is the hot reload feature. Everytime you save your app it is instantly recompiled and sent to your phone (if it is already plugged in and the app is started) so the app updates faster than you can turn your head to look at it. It's pretty cool. It sure is a big shift from Unity's builds that can take minutes just to get an APK that you then have to install. Although it can fail sometimes. Usually when you rename something, but that rarely happens. I should probably mention here that I use my phone to test. You can also get a virtual device but that's like a 1GB download and I don't want to do that.

As for debugging instead of crashing flutter will give you a red screen of death.

Which, I mean, looks pretty ominous. Couldn't they have put a smily face on it or something like Windows?

There's also the call stacks when you get an error. They're not as compact as Unity and there's a lot of scrolling and they usually contain tons of information about Flutter's internal calls I don't care about before and after the relevant parts of the callstack. But I mean it's serviceable. Better than not having a callstack at all or a callstack that rarely points to the right thing like... some other languages.

Now there's Android Studio. It's basically a less good version of a JetBrains IDE. There's no telling you how many times something is called, there's no refactoring tools, it doesn't tell you to import packages to fix errors, it takes an extra click to get into the search all screen (Ctrl+N vs Ctrl+T), and it doesn't alert you if something isn't used. And it still takes more RAM than Chrome. Like, what are you doing? But at least it supports the Material theme I'm using on Rider. Like, it doesn't matter if the IDE sucks, as long as it looks good, right?

The only thing it really has over Rider (which I was using for Unity C#) is that it automatically inserts a comment telling you that this end brace corresponds to a particular widget. Which given the nested nature of build() method is quite useful. Not useful enough to get me to not jump ship to IntelliJ though.

So last but not least: the problems I have with Flutter. And there are a lot of them. The biggest one is the documentation. You know, for something made by Google that is almost 3 years old you'd think it would have better documentation. But no. You still see things like: "Enables the form to veto attempts by the user to dismiss the ModalRoute that contains the form." In all fairness this is the exception rather than the rule. Most of the commonly used widgets do have good documentation. But when you click to what a class is you still get this nonsense.

And there are a few bugs still. I encountered one where if you use Navigator.pop() it does not trigger the onPop callback. You need to use Navigator.maybePop() instead.

So all in all Flutter is a fine framework and pretty fun to program for. The foundation is pretty solid, it's just some of the documentation that is not quite up to snuff and some things can be hard to do due to not having the proper widget. Two problems that I'm sure will be solved soon. And once they are I think Flutter has a pretty good shot at being the most popular framework in the world due to its ability to run on Android, iOS, Web, Windows, Mac, Linux, and ChromeOS with an identical experience on all platforms.

[getaether]

Aether grows past 500 concurrent nodes

It's been a pretty fun week so far.

After I posted Aether for Redditors, Aether ended up on the front page of Hacker News again. (Link)

The drill is familiar by now. Just keep everything working, and it'll pass in a couple days. This time around, I've gotten about 6,600 unique visitors on the main site or so — which is normal, since the HN link was towards the blog, and not the main site.

There's one more benefit in these things — it pushes the system to the next order of magnitude scaling, and it gives you a glimpse of where the next set of scaling issues are going to come from. This is indeed what happened when Aether broke through 500 concurrent nodes online. If you've been on the network for the past few days, you might have been having some trouble seeing new posts from other people. I'm writing to give a little bit of an educated guess on why, and what I'm doing to improve things. The stuff I've mentioned in this one is going to come in an update in the next few days or so.

In general, this is a great position to be in — Aether is picking up steam at a pretty steep pace, so when these 10x whale events happen, it's always insightful. The reason I can be working these issues right now, early as possible, is because you guys came in all at the same time and stressed out the algorithm that chooses which nodes to connect to. So thanks for being here and using it. 🙂

What I thought it was

I had released an update one day earlier, and I thought that was the cause for the connectivity problems. So far as I can see, it wasn't. I reverted that update, and it seems it's pretty much still the same.

There are some users in Windows where because of some sort of antivirus or some other external issue, the app is not able to write cache files. After some debugging with some folks at the meta forum we've ruled that out as the culprit. (Thanks!)

What was happening

Aether is a flood network. For this to work effectively, every node has to choose who to connect to at any point in time. These connections happen every minute or two. These are all outbound connections.

You also receive inbound connections. There is a limit on how many inbound connections you can receive simultaneously at any one time, to respect your internet connection and not to tax your machine. In essence, your node has a defined number of 'slots' that other nodes can connect to. When your node runs out of slots, it starts to tell other nodes: "I'm too busy, connect back later".

An Aether node, to determine which nodes to connect to, does a 'network scan'. This is, in very simple terms, a process to check some nodes that have the highest likelihood of being online.

This network scan uses the first two steps of a full sync. So it's much lighter than a regular sync. It's just a ping.

Unfortunately, what happens is that these pings also take a slot. These slots take 60 seconds to clear, to allow for continued requests on the same slot if needed.

When we had fewer active nodes, network scans and regular syncs were both able to fit the given number of slots at any point in time.

When we came close to the 500 concurrent nodes, that was no longer true. Since syncs hit one node, but scans hit multiple nodes, the scan traffic grew much faster than the sync traffic, clogging the slots that were actually meant for syncs. This is why the updates slowed down.

The sync logic was a little too soft: when it failed a small number of times, it stopped trying to sync in that cycle, and left it for a future cycle. Since the large majority of the nodes in the network were saturated by scans, this meant it kept sitting around a lot. This was a means to reduce the number of scans, since every sync attempt would mean a new scan, but combined with other effects mentioned above, it backed itself into a corner.

What's the fix?

Bunch of things.

The scans will be rate-limited. Now a node can do one scan every ten minutes, instead of being able to trigger a scan every time it wants. This should reduce the slots used by scans. (They are a tiny portion of the traffic—since they're essentially pings—but since they're indistinguishable from a sync starting, they took a full slot.)

There'll be separate slots, only for scans. This makes it so that the syncs will never be blocked by scans.

Sync logic is more aggressive, since it no longer implies a full scan for every retry. It will keep retrying with different nodes using the existing scan data from up to 10 minutes ago, until it can find one that it can sync with, or it exhausts the addresses database. The cooldown for each address is increased from 3 to 10 minutes, so at any point in time, a node will only hit another specific node only every 10 minutes, at most.

In short, we are separating the scans from the actual sync, and it will just be something that happens every 10 minutes, and no longer a service other parts of the app can call at any time they want. The goal is to make scans a little less chatty and dominant, since scanning every attempts vs every 10 minutes does not appreciably diminish the value of scans (far as preliminary testing shows).

This makes it so that the other parts of the app that relies on this addresses table can now be more aggressive, since they are released from having to update this table themselves.

Lastly, having separate, dedicated slots for scans makes it so that we can give 10x the slot count only for scans, since they are effectively close-to-free to respond to.

Why did it work before, and why it didn't work when it grew?

Because the traffic used for scans grew faster than the traffic used for syncs, since syncs are 1:1, but scans are 1:N. So the scan requests grew to be larger than the network's overall capacity growth via new nodes joining. The changes to rate-limit the scans and give them separate slows brings them back to a more linear growth with the network's overall capacity as new nodes are added.

These changes involve some backend changes, therefore it's going to be a few days, and I'll continue to work on and improve the stability in the coming weeks as my work schedule on the business version allows. I'm writing to shed some light on what I'm doing and what's happening behind the scenes.

You should see see a steady stream of updates coming in - the changelog will carry more details. They'll be focused on improving the scalability of the system as it gets bigger.

Growing pains y'all. Cheers!