Friday, 2021-12-31

December

Årets gran

Dec 2020 | Dec 2019 | Dec 2018 | Dec 2017 | Dec 2016 | Dec 2015 | Dec 2014 | Dec 2013 | Dec 2012 | Dec 2011 | Dec 2010

Saturday, 2021-12-25

HOWTO AoC

Some tips about participating in Advent of Code.

AoC is not a competition

If you were to go with online opinion, AoC is all about getting the solutions as fast as possible. This is actually not true, apart from the top 100 scorers every day[1]. Many people post their full solution online on the AoC subreddit as soon as the top 100 slots have been filled. So if you want to get 50 stars, you pick a popular language (like Python), hang out in the solutions megathread, and run the first posted solution on your input to get the correct results.

If your organization has a “competition” where the top scorers in their leaderboard get some reward, don’t participate. It’s too easy to suspect someone of “cheating” for it to be fun.

Instead, focusing on using the event to expand your skills.

You don’t need to finish each puzzle the day it is released, or within the 25 first days of December

The puzzles can be completed at any time and in any order.

Don’t let trivial mistakes trip you up

In almost every puzzle, your personalized input will be provided as a text file. Set up your environment to deal with this consistently.

For example, for every puzzle, I make a new subdirectory. The puzzle input goes into a file called input.txt. The example input goes into another file, test.txt. I then open a new file for my code, and enter a canned template that reads the content of a file into an array, one line per entry. It takes care of newlines and carriage returns (but preserves empty lines).

Then, when it comes to dealing with the input meaning, I can operate on an abstract array instead of a file.

In a similar manner I also set up some modules for dumping variables, running simple tests, etc.

You can see my (Perl) template here.

Use the examples

The puzzle text is clearly written, and any questions you might have regarding the rules of the puzzle are answered in the text or in the example. Once you get the example to run correctly, it’s generally just a question of changing the in-data to “live” to get your answer.

Generally. At higher levels there can be “twists” in how the real data is presented as compared to the examples. Also look out for edge cases. The example data might not include negative numbers, but the real input does. Have you taken that into account?

Puzzles start out easy but get harder

And weekends are generally tougher than weekdays.

Some problem classes tend to make an appearance every event

These include

  • Conway’s Game of Life
  • Register Rodeo - this is my term for a class of problem where you’re given a long list of statements, some of which are data and some of which are instructions, and you need to decode them
  • pathfinding through a maze
  • finding the lowest cost for some complicated series of actions (generalized Dijkstra’s)

Having a basic knowledge about these is beneficial, but not required.

Remember to have fun!

[1] if you want to try to crack the top 100, this guide is not for you.

Thursday, 2021-12-16

Beyond the Hallowed Sky by Ken MacLeod

First book in a new trilogy. MacLeod treads familiar ground for him - near future, socialist Europe vs. extrapolated USA “after the return of democracy”. I am looking forward to the rest of the books.

Friday, 2021-12-03

Gemini in November

Not quite as much as last month but still keeping up a decent pace.

Link to portal.

Wednesday, 2021-12-01

Advent of Code 2021

Project website: Advent of Code 2021.

Previous years: 2015, 2016, 2017, 2018. 2019. 2020.

I use Perl for all the solutions.

Most assume the input data is in a file called input.txt in the same directory as the file.

Ratings

I’m giving each puzzle a subjective rating between 1 and 5. This is based on difficulty, “fiddliness” and how happy I am with my own solution.

A note on scoring

I score my problems to mark where I’ve finished a solution myself or given up and looked for hints. A score of 2 means I solved both the daily problems myself, a score of 1 means I looked up a hint for one of the problems, and a zero score means I didn’t solve any of the problems myself.

My goals for this year (in descending order of priority):

  • get a total score of 40 or more (75%)
  • solve all problems up until day 15 without any external input - not fulfilled
  • solve all problems within 24 hours of release - not fulfilled

Link to Github repo.

Final status: score of 46/50.

Day 1 - Day 2 - Day 3 - Day 4 - Day 5 - Day 6 - Day 7 - Day 8 - Day 9 - Day 10 - Day 11 - Day 12 - Day 13 - Day 14 - Day 15 - Day 16 - Day 17 - Day 18 - Day 19 - Day 20 - Day 21 - Day 22 - Day 23 - Day 24 - Day 25 - Day 31

Day 1 - Sonar Sweep

Day 1 - complete solution

And we’re off!

I wonder if I got a bit too clever by half in this solution, as I’ve been looking over older solutions and can’t even remember solving them. But that’s how it goes I guess.

Puzzle rating: 3/5

Score: 2

Day 2 - Dive!

Day 2 - complete solution

A “standard” Perlish solution (well, my kind of Perl, anyway): a dispatch table for the else/if “switch” construct, and a compact hash containing the state of the two solutions.

Puzzle rating: 3/5

Score: 2

Day 3 - Binary Diagnostic

Day 3 - complete solution

I was honestly surprised that the canonical solution to this wasn’t some esoteric bit-twiddling trick that reduces it to a one-liner.

In part 2, the naive solution is to loop through each “column” to determine which values to count so as to determine whether they are most frequent or not. I used an index for each “set” to keep track of the values already assigned to that set.

Puzzle rating: 3/5

Score: 2

Day 4 - Giant Squid

Day 4 - complete solution

Fairly straight-forward, although part 2 threw me for a loop. I didn’t find a good way to determine the exit condition.

Puzzle rating: 4/5

Score: 2

Day 5 - Hydrothermal Venture

Day 5 - complete solution

Finally ok with my solution.

The first attempt got the job done, but was super-scruffy. I realized after I’d finished that I could treat the direction as unit vectors and work from there, so I re-wrote my solution, but only in as so far as to use the direction as a “selector” to chose which subroutine to call to “paint” the map.

After adding that to the repo, I finally remembered what I’d decided before the rewrite - to use the value of the vector in the paint routine itself.

Note that just using atan2 blindly to determine the direction will point the Y axis incorrectly. It’s probably only an issue if you’re printing the results, but I found that very helpful in debugging.

If anything good can be said about this method is that I eliminated a lot of weirdness along the way. It wasn’t all wasted effort.

Puzzle rating: 3/5

Score: 2

Day 6 - Lanternfish

Day 6 - complete solution

I got off on a bad start with this puzzle, because it worked perfectly for the test input but failed for my puzzle input. I whinged about it on IRC, mentioning I had a very old fish (41 days!). Turns out that was a mispaste and fixing that gave me the correct solution.

I got the answer to the second part 40 seconds later.

Puzzle rating: 4/5, just because my solution was so smooooth

Score: 2

Day 7 - The Treachery of Whales

Day 7 - complete solution

A quite fun one, and the first this year I managed to solve within 1hr of release. This might be TMI but I usually perform my morning ablutions and brew a pot of coffee before starting on a puzzle.

Thinking about this led me to try the average (mean) of the values as the natural solution, but that gave incorrect values. So I just checked the fuel consumption for each and every possible end point, selecting the minimum value. This went plenty fast, as did part 2 once I didn’t actually step through each distance calculating fuel as I went (hint: google “Gauss sum 100”).

When I had both solutions, I checked the various IRC chats and subreddits and discovered a raging debate on whether taking the median for part 1 and the average for part 2 always gave the correct result for every input. For me they did, so I just restricted by search space to the span of these values, plus a few extra integers for safety. This shaved a couple more milliseconds off the run time.

Puzzle rating: 4/5, I like grade school math

Score: 2

Day 8 - Seven Segment Search

Day 8 - complete solution

Today was a tough one - not the problem, per se, but commitments that made it hard to me to get to a solution that I was happy with.

In the end I just went for brute-forcing every possible permutation, which is 7! or 5,040. The solution takes around 2s to run on my VPS.

Puzzle rating: 3/5, bit fiddly

Score: 2

Day 9 - Smoke Basin

Day 9 - complete solution

This was a straight-forward problem.

I’m a bit surprised my BFS solution worked first time.

Puzzle rating: 3/5

Score: 2

Day 10 - Syntax Scoring

Day 10 - complete solution

Not the most elegant solution but it gets the job done.

Puzzle rating: 3/5

Score: 2

Day 11 - Dumbo Octopus

Day 11 - complete solution

Nice and easy, got 2 stars within one hour of downloading the input.

I don’t think my handling of some flags ($has_changed, $has_synced) is the most elegant. I’m pretty sure I’m doing an extra scan of the entire map every step to ensure everything has settled down. But I get a result within 1s (just) so let’s do some weekend chores instead.

I suspect tomorrow will be… more challenging.

Puzzle rating: 3/5

Score: 2

Day 12 - Passage Pathing

Day 12 - complete solution

I had to look up a solution for this, which was kind of embarrasing for such an early problem.

Full credit in source.

Puzzle rating: 3/5

Score: 0

Day 13 - Transparent Origami

Day 13 - complete solution

As usual, a breather after the weekend.

I was tearing my hair out, running spot checks on my code, before I realized I had coded my output incorrectly.

The rest of my issues was making it read the right way up…

“Best” result so far, around rank 6,500 for part 1…

Puzzle rating: 3/5

Score: 2

Day 14 - Extended Polymerization

Day 14 - complete solution Day 14 - part 1

A tough but fun problem.

Part 1 only for now.

Update 2021-12-15: finished both parts.

Puzzle rating: 4/5

Score: 2

Day 15 - Chiton

Day 15 - part 2

I think I finally figured out A*Dijkstra’s. With the help of a lot of cribbing from previous solutions (like 2018 day 22).

I’ve only included part 2 because I can’t be bothered bounding the box for part 1 so it doesn’t choose a cheaper solution outside those limits.

Puzzle rating: 4/5

Score: 2

Day 16 - Packet Decoder

Day 16 - complete solution Day 16 - part 1

Many people went “BERR” when they saw this: Binary Encoded Register Rodeo!

I had a lot of problems with this, mostly because I managed to get the correct solution for part one a bit by accident, which didn’t help solving part 2.

After a day of tearing my hair trying to pass data between recursion levels I managed to solve it.

Puzzle rating: 4/5 - tough, but fair

Score: 2

Day 17 - Trick Shot

Day 17 - complete solution

Suspiciously easy.

This year’s last weekend is coming up.

Brace yourselves.

Puzzle rating: 3/5

Score: 2

Day 18 - Snailfish

Day 18 - complete solution Day 18 - testing

Completed 2021-12-31

Actually less complicated then at first glance. The main issue was figuring out how to implement the rules where “explode” had higher precedence than “split”, but I managed that with a stack.

Puzzle rating: 4/5

Score: 2

Day 19 - Beacon Scanner

Day 19 - complete solution

Completed 2021-12-28

A fun problem. I found a list of all possible rotation transforms and used them to generate the set of rotations to try, then just compared each and every one to find offsets. Runtime is around 15s.

Puzzle rating: 4/5

Score: 2

Day 20 - Trench Map

Day 20 - complete solution

Back on track after a tough weekend - which I had to skip due to travel.

This was a fun problem once you figured out the trick.

Puzzle rating: 4/5

Score: 2

Day 21 - Dirac Dice

Day 21 - complete solution

A fun problem, but part 2 was too tough for me. I copped out and took a “free” star. Full credit in source!

Puzzle rating: 4/5

Score: 1

Day 22 - Reactor Reboot

Day 22 - part 1 Day 22 - part 2

Cubes - IN SPACE!!

I only had time for part 1 on release day.

Part 2 completed on 2021-01-04.

Puzzle rating: 4/5

Score: 2

Day 23 - Amphipod

Day 23 - complete solution

Completed 2021-12-26

A fun problem but one I had to skip on release day due to preparations for Christmas.

We’ve seen this sort of thing before, I solved it using Dijkstra’s.

In general, we have a start state and an end state, and we can generate new states based on the given rules. These intermediate states can be seen as nodes in a graph we’re constructing on the fly. Applying the movement costs for each amphipod gives the total cost for moving form start to end, and Dijkstra’s algorithm gives the lowest cost.

Puzzle rating: 4/5

Score: 2

Day 24 - Arithmetic Logic Unit

Day 24 - complete solution

I had to crib a solution (credit in source, of course) but I gave myself a point because it was Christmas Eve and that’s when we get presents here, damnit.

Puzzle rating: 4/5

Score: 1

Day 25 - Sea Cucumber

Day 25 - complete solution

And… it’s a wrap.

Not the most elegant solution but it’s a star. I’ll take it.

Puzzle rating: 3/5

Score: 2 (assuming I fix the missing stars!)

Day 31 - Template

Day 31 - commented template

Related to this entry.

Tuesday, 2021-11-30

November

S:a Clara Mr. Walker

Nov 2020 | [Nov 2019] | Nov 2018 | Nov 2017 | Nov 2016 | Nov 2015 | Nov 2014 | Nov 2013 | Nov 2012 | Nov 2011

Friday, 2021-11-12

Four books by Isaac Asimov

  • A Pebble in the Sky
  • Foundation 🚀☀️ Foundation and Empire 🚀☀️ Second Foundation

A Pebble in the Sky

This is Asimov’s first published novel but unlike the Foundation series itself it’s not a fix-up from earlier short stories.

There are some good nuggets here, I enjoyed it more than I thought I would. Far-future Earth under the Galactic Empire is a radioactive hell-hole, and Earthmen (emphasis very much in the original) are despised throughout the Galaxy as diseased and bigoted primitives. The planet can only support 20M people and this is enforced by mandatory euthanasia at the age of sixty. The world is ruled by a figurehead assisted by a sinister Secretary - the real power behind the throne.

So far, so 1950s era anti-Soviet. The devious Earthlings plan on unleashing their native viruses on the rest of the Galaxy, thereby killing everyone without their native immunity. But our heroes - a rock-ribbed Galactic citizen, his Earth-born love interest, and an elderly tailor transported through time from our own age, foil the plot, despite the Secretary’s machinations and the Empire’s prejudices.

The Foundation trilogy

Foundation is better than I remembered. I first read it in Swedish translation back in the 80s when I started reading SF, and I made an effort to “re-read” them via audiobook about 7 years ago but had to give up because the prose was so clunky.

If you’re writing a story inspired by the fall of the Roman Empire, you can do worse than crib from Gibbon - but you can do better, too. Asimov obviously knew his audience, and his generation’s attention to “tech detail” is quite amusing, mixing in as it does wild speculation with assumptions that some thing will never change.

Take this passage for example from the beginning of the novel, when the “prophet” Hari Seldon reveals his plans to his new employee Gaal:

It was not a large office, but it was quite spy-proof and quite undetectably so. Spy-beams trained upon it received neither a suspicious silence nor an even more suspicious static. They received, rather, a conversation constructed at random out of a vast stock of innocuous phrases in various tones and voices.

[Seldon] put his fingers on a certain spot on his desk and a small section of the wall behind him slid aside. Only his own fingers could have done so, since only his particular print-pattern could have activated the scanner beneath.

[…]

“You will find several microfilms inside,” said Seldon. “Take the one marked with the letter T.”

Gaal did so and waited while Seldon fixed it within the projector and handed the young man a pair of eyepieces. Gaal adjusted them, and watched the film unroll before his eyes.”

Quite the mix of spot-on prediction and … stuff that will probably not last 15,000+ years into the future.

And then we have anachronisms that are not quite as charming:

“All my project; my thirty thousand men with their wives and children, are devoting themselves to the preparation of an “Encyclopedia Galactica.”

(my emphasis)

There is not a single female character in Foundation who has a name.

Foundation is put together from short stories, and that’s quite a good thing. It keeps the action (such as it is) contained and the tale is quite snappy. It’s classic sub-Whig history in which the decadent Empire gets replaced first by technology masking as religion, and then by hard-nosed “Yankee” traders.

Foundation and Empire comes alive when the Mule is introduced. We also get our first named female character, who saves the day by being, well, kind and beatiful and motherly.

Second Foundation is a slog. Asimov can’t decide whether the Second Foundation (who can control people’s minds, and even themselves say they have to potential to create a Master Race) are a promise or a threat. In the end they’re succesful in hiding themselves from the masses of humanity (with the help of the most cringe-worthy depiction of a female teenager imaginable) so the Seldon Plan can continue. Yay? Maybe Asimov expands on this in the prequels and sequels but someone would have to gift me a hell of a lot of money for me to read those.


Part of the reason I read these works was this HN thread referencing a New Yorker review of the recent screen adaptation.[1] I was honestly surprised to see someone presumably my age or less who actually rated Foundation. I mean, it’s a 70-year old work, and of course SF like most genre literature is in constant dialog with the stuff that came before. But maybe SF is unique in that its foundational[2] texts are still “what SF is” to a worrying number of people.

Compare and contrast Foundation to Alfred Bester’s The Stars My Destination with its criminal antihero protagonist, or Harrison’s Bill, The Galactic Hero, which mercilessly skewers the very idea of a Galactic Empire, or Charles Stross’ Neptune’s Brood which basically declares humans will never colonize space - but our android descendants might. And of course, Ann Leckie paints the Empire where everyone is technically a female protagonist…

[1] Hacker News is bad at a lot of things but they’re almost uniquely bad concerning SF
[2] see what I did there?

Tuesday, 2021-11-02

Heretics and Believers: A History of the English Reformation by Peter Marshall

I tweeted while reading this book:

can’t wait to quit work so I can continue reading about the English Reformation

It sounds weird, but a narrative history about the English reformation is just that good. Marshall keeps the story moving along briskly through the decades and scores of characters. Highly recommended.

Sunday, 2021-10-31

Wednesday, 2021-10-27

15,000 dead in Sweden

Wednesday, 2021-10-20

30 minute offset

Some hacker tried to interest us in their new project, and was quickly torn to pieces corrected on HN.

This got me thinking, how large a percentage of the world’s population can’t use this tool?

  • Afghanistan, pop. 32.9M on UTC+04:30
  • Central Australia (Northern Territory and South Australia), pop. 2.017M on UTC+09:30
  • Central Western Standard Time (Eucla, Australia), pop. ~100 on UTC+08:45
  • Chatham Islands, pop. ~600 on UTC+12:45
  • India, pop. 1.353B on UTC+05:30
  • Iran, pop. 83.1M on UTC+03:30
  • Myanmar, pop. 55.6M on UTC+06:30
  • Nepal, pop. 28M on UTC+05:45
  • Newfoundland and Labrador, pop. 520k on UTC-03:30

That’s a total of 1.556B people, which is around 20% of the world’s population.

Needs more work.

Bonnie Prince Charlie: Charles Edward Stuart by Frank McLynn

A great biography, even if it’s showing its age (published in 1988). There’s a bit too much pop psychology and hidebound attitudes towards homosexuality for my taste. That said, even if the women in Charles Edward’s life are routinely described as “calculating” and “coquetteish”, the book does acknowledge that their situation was a difficult one.

There’s rarely a dull moment in this book, even if you’d think that after the excitement of the ‘45 and the “prince in the heather” things would get boring. On the contrary, it’s Stuart’s precipitous fall in health and wealth that grips you the most.

I also enjoyed reading about Gustav III of Sweden basically cajoling Charles Edward for the title of Grand Master of the Masons, something he really didn’t have the authority to give away. Masonry, like Jacobitism, was way bigger back then apparently.

Thursday, 2021-10-14

“Sweden didn’t have lockdowns” and other COVID myths

During the height of the COVID-19 pandemic it was common to see Sweden singled out as “not implementing lockdowns”. It was as if Sweden didn’t take any action against the spread of the virus. This was used both as praise and condemnation, depending on the views of the person saying this.

The truth is a bit more nuanced.

First, “lockdown” is a slippery term, but I’ll define it as a situation where a citizen is not allowed to leave their homes except to get groceries, medicine or other essential supplies, and the authorities have a legal way to enforce this.

Sweden lacked the legal framework in the beginning of the pandemic to enforce anything like this. The constitution adopted in 1971 explicitly avoided implementing a “state of emergency” clause because it was seen as a gateway to tyranny. Any emergency legislation would have to be implemented by the Riksdag.

Sweden implemented a number of voluntary measures to enforce social distancing:

  • everyone who could work from home was encouraged to do so
  • the normal 1-day sick day without pay (karensdag) was waived
  • the state took over the payment of the first fortnight of sick leave from employers

(Sick pay is generally 80% of take-home pay up to a limit.)

Restaurants, theaters and sports venues were regulated by public health laws that were implemented to restrict attendance. But these laws do not extend to other venues such as hairdressers or general stores.

Controversially, this also applied to political demonstrations.

The net result was a marked decrease in the number of people traveling to work, going out to lunch, etc.

After a few months, legislation was passed that enabled the authorities to restrict opening hours in restaurants and bars.

As of Oct 2021, all restrictions have been lifted.

What all this didn’t really help with was with Sweden’s total deaths, which I personally believe had more to do with the shameful lack of preparation and protection of elderly people in care homes. But I do believe it helped limit the spread of the disease, thereby preventing health care resources from being overwhelmed.

Did this help Swedish businesses? Its hard to say. Those that relied on people coming in like restaurants, hotels, travel in general suffered a lot. Hardware stores and places that could deliver probably saw increased business.

Sweden’s per capita death rate is about average compared to other EU countries (and lower than Belgium’s which had famously strict lockdowns), but much higher compared to other Nordic countries like Denmark, Norway and Finland. This has been a source of great debate and is, I believe, attributable to different handling of the very old and infirm.

Sunday, 2021-10-10

Proposal for healthy webforums

This archived Kuro5hin post by user ‘anaesthetica’ poses a number of provocative questions, and although dated (posted 2009) still has relevance for today’s fora.

It’s a long read, I’ve reproduced the conclusion below.


Conclusion

There are serious problems with existing web forums’ institutional capacity to sustain constructive interaction over the long term. The foregoing has been an attempt to rethink what constitutes community and society on the web, and what the requirements for sustaining them are in an environment of rapid scaling.

The conclusions reached about the weaknesses of current forums are:

  • Eternal September presents web forums with an inability to avoid the dilemma that scaling creates for socialization.
  • Community and society, as forms of interaction, are not just different in scale but also different in kind.
  • Community doesn’t scale, and society is difficult to enforce.
  • User registration and barriers to participation do not prevent community-destroying behavior.
  • Scale quickly outpaces moderators’ ability to enforce socialization of new users.
  • Current forms of user moderation and trust ratings are vulnerable to gaming and attack.

Recommendations for a hypothetical forum structure are summarized as follows:

  • Forced anonymity fosters society by countering vanity, making users modular, and placing the focus on the content/comments.
  • Moderation can be improved by making it passive, scarce, and focused on comment quality rather than agreement with the substance of the comment.
  • Conversation, not isolated comments or voting scores, must be the central criterion of user interaction.
  • Communal groupings can emerge organically from society based on demonstrated constructive conversation.
  • Forums should discriminate between original content, link-n-blurb content, and personal content.
  • Story promotion and front page position should be determined by quality of conversation not voting.

It should be stressed that none of these are radical innovations. Most are already implemented piecemeal in some form or another in the various web forums, bulletin boards, chat rooms, and newsgroups throughout the internet. But there is no forum providing a coherent combination of these elements. I believe that these factors will provide the institutional foundation for a web forum that can achieve a greater scale-free status than any that we currently possess.