You say "the internet", I say "the Internet"...

My friend Nick Feamster recently twote something that resonated with me:

I still bristle whenever I read Internet with a lowercase "i".  The Internet is one specific instance of an "internetwork". People who write editorial style guides for tech should be required to take a networking class, or at least a history of networking class.

(The perspicacious reader will note that this happened after the 280calypse)
Having been involved for many years with the Internet, and the Internet Engineering Task Force, and the Internet Society, my first thought was "YES! Exactly this happens to me all the time."
But then I read the whole tweet, and much of the discussion, and found that I agree even more with Heather E. Merrick, who responded:

The AP Style Guide used to call for this but they grew up in 2016.

...especially after she countered Nick's remark that AP's editors "should clue up on history, and the use of proper nouns" with this explanation:

They used to, and then they wised up to the reality that language is not in the hands of any one person or industry but The People, who enjoy using a lowercase "i," hence the update to the Stylebook.

 Ratul Mahajan put it more succinctly (adding a friendly health tip):

inevitable success disaster

So you built the "Internet", and other people write about the "internet". My pro tip: Take it as a huge compliment: The thing you built has become an important part of their environment. Too vital to be considered some brand name anymore. But of course if you want to be sad about people "minimizing" your invention, that's your choice. Here's a kleenex for you!
Yes, I'll continue to write Internet with a capital I. Just like I write the name of my employer as "SWITCH" as we're told to, even though everybody always does it wrong and writes "Switch". But I stopped getting mad at those people, it's just not helpful. Instead I thank them for letting me continue to use the "correct" spelling.
When they tell me I have to stop, I'll just turn their internet off, that'll show them.

"...let's turn the turning off off", OK?

Google Code Jam 2017 in Lisp: Round 1B/1C

Online round 1 was done on three dates again this year. The first (1A) fell in the middle of the night so I skipped it.

Round 1B Problem A: Steed 2: Cruise Control

I attempted the second, 1B, but I was distracted by important household chores. That's also why I didn't make any sketches. The first problem was easy enough, and I found a solution while fixing a meal for a kid who'd just returned from boy scout camp. The basic idea is that the horses all queue up behind the slowest one, so the arrival time is the latest arrival time at the destination point for all horses. The solution (A.lisp) worked fine on the first attempt of the small dataset, and also on the large one.

Round 1B Problem B: Stable Neigh-bors

The large dataset, where the unicorn's mane can have mixed colors, looked significantly more complex than the small one, where there are only three colors. I attempted a straightforward greedy algorithm, but somehow got it wrong. Because I didn't feel in a good state of mind, I decided to give up at that point. Otherwise I would have attempted the small dataset of Problem C: Pony Express. The "large dataset" cases of both problem B and problem C looked just too difficult to me.

Round 1C Problem A: Ample Syrup

A quick analysis suggested to me that the radius of the pancakes isn't relevant, because only the bottom (largest) one "counts", so I need to pick the pancakes with the largest lateral surface. Of course that reasoning was wrong, because we also need to pick which will be the bottom pancake. This error cost me two bad attempts, but I managed to reuse most of the initial code by adding a loop around it that tries various base pancakes. The code is in A.lisp and, again, worked fine for both the small and the large dataset.

Round 1C Problem B: Parenting Partnering

The optimization problem looked a bit tricky (but doable) in the general case, but the "small dataset" case was very specialized and easy enough to attack. There are only 1 or 2 activities in total. Either each partner has one, or one partner has all 1 or 2. If each partner has one, then the optimal solution always involves two exchanges. If one partner has the only one activity, the solution is even more trivially two exchanges. If one partner has (all) two activities, then the optimal solution is two if those activities can be arranged on the same "half-circle" (12 hours or 720 minutes) of the day, otherwise four. I coded these cases in B.lisp and was successful on the small dataset. In hindsight I'm surprised that it took me so long, more than 45 minutes between my submissions for A and for B-small.

Round 1C Problem C: Core Training

Next, I decided to try the small dataset of problem C. While I thought B-large might be in reach for me, I was sure that C-small was easy and could be coded quickly. (I had and still have no idea how I could successfully approach C-large.)

In particular, I thought that the training budget should always be spent on the worst (lowest-p) cores first. So I wrote this trivial loop, ahem, recursion, that spends as much as possible on those worst cores until either the budget is used up, or the worst cores become improved enough to be as good as the next-better core, or the cores reach p=1. But all my attempts were rejected,  and embarrassingly I still don't know why. Probably my reasoning was again oversimplified. Or it was something about the Lisp representation of floating point numbers. Anyway, the non-functioning code is in C.lisp.

Conclusion

This was the end of my participation in Google Code Jam 2017, because with rank #1850 I didn't make the cut—only the top 1000 in each of the round 1 sub-rounds make it to round 2. Even if I had been successful with the small dataset of C, I wouldn't have made the top 1000. Had I successfully solved the large dataset of B with some time to spare, then it might have worked.

It was mostly fun to code these small problems in Lisp. My Lisp skills are getting a bit rusty though. And I'm still not as comfortable with the SBCL/SLIME combination as I am with Allegro Common Lisp and its Emacs interface, but as I had mentioned in previous posts, I wanted to use completely free/open source software. And the awesome Allegro debugger wouldn't have been of much help here anyway.

And I love the problems! Kudos to the Googlers who come up with them.

How did the other Lispers fare? Badly as far as I can see. There haven't been many Lisp submissions in 2017 anyway, compared with 2016.

Enabling BBR on Ubuntu Xenial

BBR (Bottleneck Bandwidth and RTT) is a novel congestion control scheme for TCP. It was developed by several Google engineers and has been in use on Google.com and Youtube. See the PERT KB for more background.
Here's how you can enable it on a machine running Ubuntu 16.04 LTS "Xenial Xerus".
Note: This is mostly useful for systems that send fairly large TCP flows. And the configuration is incompatible with other packet schedulers such as fq_codel, so consider the tradeoff.

Upgrade Linux Kernel to ≥4.9

The BBR implementation was merged into the master branch of the Linux kernel before the 4.9 release. Xenial uses the 4.4 kernel by default, but you can install a newer one (4.10 as of this writing) from a preview repository of the "hardware enablement" kernel provided by Canonical:

sudo apt install -y --install-recommends \
  linux-generic-hwe-16.04-edge

Enable fq Packet Scheduler

BBR fundamentally requires a packet scheduler that can "pace" outgoing packets per flow.  Enable this by adding an "up" clause (shown in boldface below) to each interface in its corresponding configuration file, e.g. /etc/network/interfaces.d/eth0.cfg:

auto eth0
iface eth0 inet dhcp
  up tc qdisc replace dev $IFACE root fq pacing
iface eth0 inet6 auto

Make BBR the Default Congestion Control Algorithm for TCP

echo net.ipv4.tcp_congestion_control=bbr | \
  sudo tee /etc/sysctl.d/90-bbr

Activate by Rebooting

A reboot should now enable all necessary components: the recent kernel, a pacing-capable packet scheduler, and BBR as the default.

You can check whether BBR is actually in effect by using the ss -i command while having at least one TCP connection open—which is already guaranteed to be the case if you are logged in over SSH.

$ ss --tcp -i
State       Recv-Q Send-Q                                               Local Address:Port                                                                Peer Address:Port
ESTAB       0      1848                         2001:620:5ca1:2f0:f816:3eff:fe9c:71af:ssh                                                           2001:620:0:69::107:57795
  bbr wscale:5,7 rto:208 rtt:6.078/0.237 ato:48 mss:1182 cwnd:12 bytes_acked:156685 bytes_received:10033 segs_out:851 segs_in:977 send 18.7Mbps lastrcv:4 lastack:4 pacing_rate 87.2Mbps unacked:4 retrans:0/13 rcv_rtt:12 rcv_space:28560
ESTAB       0      0                            2001:620:5ca1:2f0:f816:3eff:fe9c:71af:ssh                                                           2001:620:0:69::107:61315
  bbr wscale:5,7 rto:220 rtt:18.674/25.752 ato:40 mss:1182 cwnd:11 bytes_acked:8025 bytes_received:5125 segs_out:86 segs_in:122 send 5.6Mbps lastsnd:470176 lastrcv:480332 lastack:470068 pacing_rate 60.5Mbps rcv_rtt:12 rcv_space:28560

The "-i" part of the output mentions "bbr" and includes some BBR-specific metrics as well as the pacing rate applied to each outbound TCP flow.

Google Code Jam 2017 in Lisp: Qualification Round

In 2016 I was quite happy with my performance in GCJ, even though I didn't make it past Round 1. So despite being quite busy, I registered for the 2017 edition as well. The Qualification Round happened yesterday. It lasted for 27 hours, starting at 1AM in my time zone. I looked at the puzzles after breakfast, and as usual found them intriguing. I initially skipped the first one (Oversized Pancake Flipper) because I knew it must be easy but I didn't find an obvious approach right away. The general approach I took was to first read the problem (out loud if a family member would be willing to listen :-), then think about it while scribbling in a notebook, then when I thought I had an efficient (should be "efficient enough") solution code it up in Lisp more or less top-down. For your amusement, I'm sharing the entirety of my this year's notes, including errors and culs-de-sac.

B. Tidy Numbers

This seemed easy and linear, and I didn't have to do much scribbling. We're looking for the largest Tidy Number that's less than or equal to the input number. We represent the input as a vector of digits. Then we start from the left and look at consecutive pairs of numbers. As long as d_i≤d_i+1 we're happy. If d_i>d_i+1, we need to "fix it up". Fixing it up means usually means changing d_i to d_i-1 and replacing everything to the right with nines. We cannot run into d_i=0, because there are no leading zeroes and we have already checked that the prefix of the number up to and including digit i is Tidy, so the digits cannot become lower. The local fixup may result in the overall number not being Tidy anymore, i.e. we may have made d_i<d_i-1. So we need to recurse (or reiterate, but hey we're thinking in Lisp, right?) on the result. We also may have introduced a leading zero that should be removed. So we remove those. The resulting code is in B.lisp. The code is recursive but not purely functional, because it munches the array using (setf (aref ...) ...). That's ugly and might have made debugging harder, but then the code should be easy enough to not need debugging. And probably this (half-) destructive approach saves a few cycles...

C. Bathroom Stalls

This was definitely the one I had the most (and longest) fun with. It took me several hours (mostly unfocused/doing other things) to get to the breakthrough, which would of course have killed me in a "real" time-limited round.

At first I drew up some simple/small examples. Starting from initial settings with (N=) 7, 6, 5, or 4 spaces, I added all N respective occupants K in order, to get an intuitive picture of how the game plays out. But I didn't find the general pattern.

Pretty quickly, I had a complete understanding of the case where N=2ⁱ-1: The first person (K=1=2⁰) has 2^i-1-1 space to the left and to the right, the next two (2¹) persons each have 2^i-2-1 space to the left and right, and so on. But how to generalize this to Ns that do not have this form?
At any "round of the game" (K), there is a set of "extents" of free space. In each round, the largest of the current extents is "split": If the size of this largest extent is odd and larger than one, that is, of the form 2x+1, then it will be split into two extents of size x. That was the "easy" case that covers the problem completely when N=2ⁱ-1.

But for other kinds of N, I still had no good idea of the pattern how the overall set of extents develops. In a desperate attempt, I tried to draw this up as a tree for N=6. That looked somewhat promising, but I still couldn't figure out the general pattern. At least it shows the special case of the size-2 extent, which doesn't really get split into two extents but degenerates into a single size-1 extent. Hm, this seems complicated.

In an even more desperate attempt, I decided that I needed to look at a bigger example and started drawing up the tree for N=230. Nothing very particular about that number, except that I wanted to start with an even number because that seems to be the more complicated case.
Now that led to the breakthrough. In this non-trivial example, I saw that each level of the tree only contained (a maximum of) two different values with a difference of one.
So a complete and useful description of a given level of the tree is the distribution between these two different values. This is what I wrote up in the right-hand column: On level 1 (after the first split) we have extents of 1x114 and 1x115, on level 2, 1x56 and 3x57, on level 3, 1x27 and 7x28, on level 4, 9x13 and 7x14, and so on. Generalizing to level 0, we can say that we start with 1x230 (1xN) and 0x231.
But how does one get from level j to level j+1? Well, each odd extent splits into two equal extents, and each even one splits into one that's half the original number and one that's one lower. That leads to the two cases below the large (partially written-out) tree. (I started writing the cases with m and n and then replaced that with a and b, respectively, but didn't do so all the way because I had enough to write the code.) The code is in C.lisp, and I'm quite happy with it. Initially I had switched the even and odd cases, which led to wrong results on the tiny example under the problem description. First I panicked, but by simply running a few examples under (trace minmax-1) I could locate the error. I knew the code was O(log(N)) efficient, so I fed it the small, still-small, and large cases with confidence, and each was processed in less than 10 milliseconds.

A. Oversized Pancake Flipper

At this point I was fairly certain to have passed the mark with just two problems done, assuming that at least one of my "large" data set solutions were correct. But it nagged me that I hadn't turned in A, which was supposedly the easiest puzzle. I thought about it again and came up with the following reasoning: The basic operator (multi-pancake flip) is commutative—it doesn't matter whether I flip 4–6 and then 3–5, or the other way round. That means we should be able to strictly process the pancakes in some order, e.g. from left to right. The operator is also an inversion... applying it twice returns the original state and, because of the commutative property, never makes sense.

So we can just go to the row of pancakes left-to-right. If the current pancake is –, we turn it and the others to its right. If the current pancake is + we leave it. Then we shift one place to the right and repeat. When we're at the end of the row (which is K places before the end because of the flipper restriction), we're done. The last pancakes must then all be + or we lose.

The code is in A.lisp. Again, this is written recursively but destructively: The flipping is done by modifying elements in the vector (string). Probably the code would be more elegant if rewritten using a list instead of a vector, and constructing a fresh list when flipping.

When reading the initial state of pancakes, I skipped the reverse (or nreverse) step because it really doesn't matter whether we operate on a mirror image.

D. Fashion Show

Wow, that problem sure seemed from a different league. Fewer than 1'000 contestants even got the small solution right, whereas all other problems had at least 13'000 correct solutions. My mental analysis and scribbling didn't get me very far. You cannot have more than one non-+ in the same row or column, not more than one non-x in the same diagonal. If you want to have an o (twice the value of a + or x), then all the other non-empty models in the same row/column need to be +, all on the same diagonal need to be x.

There's also a parallel to the N-queens problem, in that in both cases you cannot have more than one "thing" (where thing means "queen" or "non-+/x") per row/column/diagonal. But where N-queens only has one "thing", the queen, in this case the things are different (non-+/non-x), and what's more we need to maximize some value.

So I couldn't figure out a useful approach, and the fact that some initial models have been placed makes the reasoning even harder. So I gave up before even trying very hard.

Conclusion

The next morning I checked my results for the large data sets and found them all correct. I ranked in the 4'400s, but then I started late. My 65 points would have been sufficient to enter the top 1000 if I had finished everything in 2h15. That would have been somewhat unlikely, even if I had started immediately and had been fully focused. The first sub-round of round 1 will start at 3AM local time, so I'll probably skip it and try 1B a week later, and then probably 1C. Let's see!

I didn't have too much trouble with the SLIME/SBCL combination; for more than 25 years I have mostly been using Allegro and its Emacs interface when programming, and this is still much easier for me, especially when debugging. But for the contest I really wanted to use a Free/Open Source Lisp.