Thursday, 2022-12-01

Advent of Code 2022

Project website: Advent of Code 2021.

This is a placeholder entry. Current progress can be tracked in the GitHub repo: https://github.com/gustafe/aoc2022#advent-of-code-2022. Comments for solutions are in Pod format in the individual solution files.

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

Related to this entry.

Friday, 2022-11-25

Parsing RFC 3339 timestamps using strptime in Perl

RFC 3339 is a subset[1] of ISO 8601 time formats for use in Internet communications.

An RFC 3339 timestamp can look like this: 2022-11-25T09:26:04+01:00.[2] This is the format required by the Atom and JSONfeed specifications.

Perl’s standard module Time::Piece has a simple string parsing functionality implementing the POSIX strptime format.

The problem is that the strftime directive %z does not match a timezone designation in the format +01:00, only +0100.

So to use Time::Piece to parse RFC 3339 dates, use the following Perl snippet:

my $string = "2022-11-25T09:26:04+01:00";  
$string =~ s/:(\d+)$/$1/; # strip last colon  
my $ts = Time::Piece->strptime($string, "%FT%T%z");   
# output Unix timestamp  
say $ts->epoch;

The %F directive represents the date %Y-%m-%d and is present as a GNU extension. It does not seem to be part of the original POSIX specification.


[1] For an exhaustive list of differences, see this page

[2] GNU date omits the separating T from its rfc-3339 output, but includes it in the iso-8601 version. Both indicate the timezone with a colon.

Thursday, 2022-07-07

A simple update queue for HN&&LO

HN&&LO is chugging along fine, almost three years after release.

One thing that’s bothered me for a while is that I don’t keep the score and comments for Hackernews entries up to date in a timely manner. So far, I’ve been going back and re-reading last month’s entries but this means that the daily view generally isn’t up-to-date.

The HN API is hosted on Firebase and thus has the ability to get real-time data, but there’s no Perl interface to it, and I really don’t have time to tinker with an entire async setup for a page that’s updated every hour at most.

Instead I’ve implemented a simple queue to keep items up to date.

Every time I read new entries from HN, I add them to the queue. I set a time about an hour in the future.

Every ten minutes or so, I check for items that are older than the current time. If there are items, I compare the data stored in my database to the current status in HN. If there’s a change, I update my datastore and re-submit the item into the queue about 2 hours in the future.

If an item is unchanged, I re-submit it 2 times in case it gets some attention.

If an item is “low score” (currently max 2 upvotes and no comments) it’s given on more chance before being removed from the queue entirely.

I’ve been working on a crude visualization of the queue, it can be seen here:

https://gerikson.com/hnlo/queue.html

I log items that are added to the DB here:

https://gerikson.com/hnlo/log.html

Hopefully this will make the main page a bit more informative than before, although just as slow.

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.

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.

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. ~200 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.

Wednesday, 2021-09-29

Setting up a Gemini server

I host my stuff on a Digital Ocean VPS.

I already have a webserver running, and my domain points to it.

I followed the steps in this instruction with some added wrinkles:

  • I could not get agate to start correctly, it would not bind to the ipv4 port 1965. After some desultory troubleshooting I used gemserv instead.
  • I didn’t bother compiling gemserv to use GGI, just static content.
  • The cert and key .pem files generated from the instructions worked great in gemserv
  • I used the systemd service example from the instructions, just replacing the call to agate with the call to gemserv

Update Wednesday, 2021-10-06

The main site can be reached on gemini://gerikson.com.

I’ve set up a gemlog using Blosxom on gemini://gerikson.com/gemlog/.

Update 2022-02-08

I’ve recently changed servers to Molly Brown due to this kerfuffle: gemini://gerikson.com/gemlog/gemini-sux/gemserv-update-woes.gmi

Thursday, 2021-01-14

719: Number splitting

I’m a bit fired up after Advent of Code, so thought I’d start by picking off some “easy” recent PE problems.

My first brute-force attempt found a solution after 4.5 hours, but access to the forum showed much smarter solutions so that’s what I’ve added to the repo.

Monday, 2021-01-04

Advent of Code 2020 wrapup

This was a good year, in my opinion. It was a return to the 2015-2017 era, before the unfortunate experiment in collective puzzle-making in 2018, and the “armature” of the intcode puzzles in 2019. These were fun, and impressive, but if you missed out on doing them there was ~45% of the puzzles gone.

I managed to solve all puzzles before the end of the year, with a personal score of 48 out of 50, which is the best I’ve done since 2016.

AoC has grown hugely, even compared to last year. Here’s how many solved both parts of day 1 and day 25 (essentially solving every puzzle):

Year 2 stars day 1 2 stars day 25 Personal best ranking
for 2 stars
2015 50 358 3 521 422 (day 16)
2019 101 125 3 137 2 111 (day 23)
2020 148 468 11 285 5 040 (day 18)

Favorite puzzle was probably day 20, where we had to do some image recognition. I didn’t finish this on the day it was released but had some fun polishing it later.

Tuesday, 2020-12-01

Advent of Code 2020

Completed all puzzles on 2020-12-30

Project website: Advent of Code 2020.

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

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 (new for 2020)

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 40 stars or more (75%)
  • solve all problems up until day 15 without any external input
  • solve all problems within 24 hours of release

Final score: 48/50

Link to Github repo.

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 1 - Report Repair

Day 1 - complete solution

Not much to say about this. I used a hash to keep track of the “rest” of the values when comparing.

Apparently this (or at least part 2) is the 3SUM problem which is considered “hard”. I accidentally implemented the standard solution in part 1 so props for that I guess.

I still believe firing up the Perl interpreter and loading the actual file takes longer than just solving part 2 with two nested loops.

Beginning programmer example: loops and hashes/dicts/maps.

Puzzle rating: 3/5

Score: 2

Day 2 - Password Philosophy

Day 2 - complete solution

Despite actually being awake and caffienated when the puzzle dropped, I still managed to mess this up. Extra annoying when it’s basically tailor-made for Perl.

Here’s a partial list

  • messed up the initial regex
  • assigned $min and $max to the same value
  • messed up the comparison range in part 1
  • off-by-one error in the indexing in part 2
  • in part 2, tried to use the sum() function from List::Utils but forgot to use parentheses around the array

Beginning programmer example: parsing input, exclusive OR.

Puzzle rating: 3/5

Score: 2

Day 3 - Toboggan Trajectory

Day 3 - complete solution Day 3 - alternative solution

Veterans of previous AoC’s will get pathfinding flashbacks from this problem’s description, but it turns out it’s a bit simpler - as can be expected for day 3.

I decided before coding to not store the map explicitely as individual coordinates, instead just storing the rows as a text string and unpacking via split when needed.

Another decision was to work with the test input first to confirm my algorithm. That way it would be easier to, for example, print out the rows in case I needed to visually debug.

Beginning programmer example: dealing with infinite repeats using mod.

Puzzle rating: 4/5

Score: 2

Day 4 - Passport Processing

Day 4 - complete solution

This is a “M4P” problem - Made for Perl.

Nothing really to say about this. Set the $/ variable to an empty string to import the records as paragraphs.

I used a dispatch table to avoid a giant if/then/else statement.

Beginning programmer example: regexps! (and handling mult-line input).

Puzzle rating: 3/5

Score: 2

Day 5 - Binary Boarding

Day 5 - complete solution

I have a massive binary blind spot, so I just knew there was going to be a CS-appropriate simple solution to this. But I just followed the instructions and got the right answer in the end anyway.

Beginning programmer example: binary.

Puzzle rating: 3/5

Score: 2

Day 6 - Custom Customs

Day 6 - complete solution

Another easy problem, and during the weekend too! <anxiety intensifies>

My first stab at part 1 contained one specific data structure, that I had to tear out for part 2. After submitting the solution I realized the first solution could work for both.

Puzzle rating: 4/5

Score: 2

Day 7 - Handy Haversacks

Day 7 - complete solution

As was expected, difficulty has ramped up a bit.

Can’t really explain what I did here … the main idea was using BFS to scan the “table”, but part 2 was basically me fiddling around with terms until the test cases passed.

Puzzle rating: 4/5

Score: 2

Day 8 - Handheld Halting

Day 8 - complete solution

This year’s register rodeo, but with a fun twist.

Part 2 was solved by brute forcing every solution, it still took only ~0.3s to find the answer.

Puzzle rating: 4/5

Score: 2

Day 9 - Encoding Error

Day 9 - complete solution

An ok puzzle. It pays to read what’s sought carefully…

Puzzle rating: 4/5

Score: 2

Day 10 - Adapter Array

Day 10 - complete solution

This was a tough one! I was too impatient to really start to optimize after making a solution that solved the two example files, so I “cheated” and looked for inspiration. Full credit in source.

As a bonus I learned about postfix dereferencing in Perl.

Puzzle rating: 4/5

Score: 1.

Day 11 - Seating System

Day 11 - complete solution Day 11 - part 1 Day 11 - part 2

Ugh, got burned by Perl’s negative indices on arrays which messed up part 2. I rewrote it using hashrefs instead.

Puzzle rating: 2/5, mostly because we’ve seen this sort of puzzle before and I don’t enjoy them that much.

Score: 2

Day 12 - Rain Risk

Day 12 - complete solution Day 12 - part 1 Day 12 - part 2

A not too taxing problem.

I don’t like having to re-write the guts of part 1 to solve part 2, however.

Update: after some perusal of the subreddit I realized it was easy enough to run both solutions in one pass, so I rewrote part 2 to handle that.

Puzzle rating: 3/5.

Score: 2

Day 13 - Shuttle Search

Day 13 - complete solution

A tough Sunday problem.

Everyone on the internet figured out that this was an implementation of the Chinese Remainder Theorem, but I followed the logic of a commenter on Reddit (credit in source) and I’m quite proud of the solution.

Puzzle rating: 4/5

Score: 2

Day 14 - Docking Data

Day 14 - complete solution Day 14 - part 1 Day 14 - part 2

A bit of a fiddly problem, which I solved by only dealing with strings and arrays. Bit manipulation is for CS weenies.

I got good help from today’s solutions megathread in the AoC subreddit.

Puzzle rating: 3/5

Score: 2

Day 15 - Rambunctious Recitation

Day 15 - part 1 Day 15 - part 2

This looked complicated at first glance but wasn’t hard to implement.

My part 1 code solves part 2, given a powerful enough computer (I had to use my Raspberry Pi 4). However it takes very long on my standard VPS, so I re-implemented a solution from /u/musifter on Reddit. Credit in source.

Puzzle rating: 3/5

Score: 2

Day 16 - Ticket Translation

Day 16 - complete solution

I realized this was basically the same as 2018D16, but I had a hard time wrapping my head around how to lay out the gathering of required info. A bit of a slog.

Puzzle rating: 3/5

Score: 2

Day 17 - Conway Cubes

Day 17 - part 1 Day 17 - part 2

What if Conway’s game of life - but in more dimensions?!

Not too hard, but not too entertaining either.

Puzzle rating: 3/5

Score: 2

Day 18 - Operator Order

Day 18 - complete solution

A CS staple. So I didn’t feel bad for googling “shunting-yard algorithm” and cribbing a solution from Rosettacode.org. Same for the RPN evaluation algorithm, but I found a much more straightforward implementation on Perlmonks. Credits in source.

I wonder how many CS grads nowadays have even seen a shunting-yard. The nerds in the MIT model railroad society had, of course, and Djikstra too.

Puzzle rating: 3/5

Score: 2

Day 19 - Monster Messages

Day 19 - part 1

For part 1, I tried using Parse::RecDescent and managed to get a kludgy solution, but without really knowing what I was doing.

Skipped part 2 for this one.

Puzzle rating: 3/5

Score: 1

Day 20 - Jurassic Jigsaw

Day 20 - complete solution

This year’s most involved problem. In the end it’s not that difficult, but there are a lot of moving parts.

I’m happy that the code I wrote first (to manipulate grids for part 1) was useful for part 2 too.

Puzzle rating: 4/5

Score: 2

Day 21 - Allergen Assessment

Day 21 - complete solution

Not my favorite puzzle this year. I had the right idea on how to go about it but had to look around for practical solutions.

Puzzle rating: 2/5, mostly because I’m cranky today.

Score: 2

Day 22 - Crab Combat

Day 22 - complete solution

I took a “free card” for part 2 today. Credit in source.

Puzzle rating: 3/5

Score: 1

Day 23 - Crab Cups

Day 23 - part 1 Day 23 - part 2

Part one saw me getting very fiddly with splice, an effort that was not appropriate for part 2…

Score: 2

Day 24 - Lobby Layout

Day 24 - complete solution

A fun little problem. I reused my hex grid logic from 2017D11 and the technique from this year’s day 17 to find the solution.

Puzzle rating: 4/5

Score: 2

Day 25 - Combo Breaker

Day 25 - complete solution

Nice and simple Christmas day puzzle.

I love the denoument of our hero’s journey. Luckily for him, I don’t have all the stars, so I guess I’ll have to stay in the resort until I can finish all the puzzles!

Puzzle rating: 3/5

Score: 2

Thursday, 2019-12-26

Advent of Code 2019 wrapup

I enjoyed this year’s edition more than last year’s.

It was a combination of being slightly easier, and having a better attitude to it coming in. In 2018, I was aiming for as good a result as I had in 2016, which was 49 stars out of 50. This left very little margin for bailing out of tough problems, and led to increased frustration when I didn’t have the time required to solve a problem within 24 hours.

I was thinking of not participating, but as time drew near, I got inspired, and even solved a couple of left-over problems from last year in preparation.

This year I gave myself more leeway for simply bailing on problems that didn’t seem fun. This turned out to be day 21. I also gave up on day 6, which was probably a mistake, and part 2 of day 22.

I also felt that this year was easier than 2018. In part, this was because of nearly half of the problems being intcode problems, where we first had to write an interpreter for a specific machine code, and then apply that interpreter to various fun follow-up questions, like playing Breakout or Adventure.

Then I had a lot of support from the dedicated IRC channel from lobste.rs. I’d like to thank regulars jjuran, wink, gthm and tumdum for encouragement and friendly competition.

I still have a number of stars to get, but unlike last year, I’m looking forward to solving those problems.

Sunday, 2019-12-01

Advent of Code 2019

This blog post is a work in progress

Project website: Advent of Code 2019.

Previous years: 2015, 2016, 2017, 2018.

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.

A note on scoring

Current score (2020-12-25): 46. I’m aiming for a final of 44+1.

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 38 stars or more (75%)
  • solve all problems within 24 hours of release

Link to Github repo.

TODO

  • complete day 18

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 19 - Day 20 - Day 21 - Day 22 - Day 23 - Day 24 - Day 25

Day 1 - The Tyranny of the Rocket Equation

Day 1 - complete solution

A nice and simple problem to kick off this year.

Score: 2

Day 2 - 1202 Program Alarm

Day 2 - complete solution

An earlier appearance of register rodeo than expected! I think we’ll see more of this going forward.

[intcode part 1]

Score: 2

Day 3 - Crossed Wires

Day 3 - complete solution

This took longer than it had to. I messed up adding the paths, and only managed to get the correct answer to part 1 by chance. Once I plotted the example data I could correct the code, then add the logic for part 2.

I’m not entirely happy with the duplicated direction subroutines. Some people have used complex numbers to simplify this but that would require a separate Perl module to implement.

Score: 2.

Day 4 - Secure Container

Day 4 - complete solution

I blanked on this one and dreaded combinatorics. Turns out brute force is eminently doable. Credits to /u/andreyrmg in the daily solutions thread, and A_D and sim642 in the IRC channels for help in inspiration.

I still think my solution is my own though (and pretty Perlish), so full score today.

Score: 2.

Day 5 - Sunny with a Chance of Asteroids

Day 5 - complete solution

After struggling with the convoluted problem description I was pleasantly surprised to find my code ran flawlessly first try. I still have some niggling issues with the test data, and need to clear that up before the inevitable next intcode problem.

[intcode part 2]

Score: 2.

Day 6 - Universal Orbit Map

Day 6 - complete solution

I bailed on this one and sought inspiration in the daily solutions subreddit. Credit in source!

Score: 0.

Day 7 - Amplification Circuit

Day 7 - part 1 Day 7 - part 2

A tough, but fun one. There were a lot of subtleties in the second part, and I got some pointers from the subreddit.

I got the chance to clean up my intcode implementation, and learned a new facet of Perl.

[intcode part 3]

Score: 2.

Day 8 - Space Image Format

Day 8 - complete solution

Defying expectations (and maybe fears), this Sunday problem was not that complicated.

Of course, it helps if you confirm that what you think is input actually is the same as the problem input. Not that I’d have anything other than theoretical knowledge of this situation…

Score: 2.

Day 9 - intcode test suite

Day 9 - complete solution Day 9 - complete solution

So the Intcode computer is done, and we’ve amassed a number of test cases to ensure it works. I’m kinda sorta happy with my code. It’s not the most elegantly put together but it works fine.

[intcode part 4]

Score: 2.

Day 10 - Monitoring Station

Day 10 - complete solution

This was a fun one, even though I got sidetracked by my incorrect assumptions and got lost in a hallway of indices, all alike.

Part 2 was found by inspecting the output, but hey, a star is a star.

Score: 2.

Day 11 - Space Police

Day 11 - complete solution

Ah, the return of Langton’s ant. Always nice to see an old friend.

Nothing too complex here, although I’m quite proud of the line noise for the dispatch table for movement:

my %directions = (
    '^'=>sub{!$_[0]?['<', 0,-1 ]:['>', 0, 1 ]},
    '<'=>sub{!$_[0]?['v', 1, 0 ]:['^',-1, 0 ]},
    'v'=>sub{!$_[0]?['>', 0, 1 ]:['<', 0,-1 ]},
    '>'=>sub{!$_[0]?['^',-1, 0 ]:['v', 1, 0 ]},
);

[intcode part 5]

Score: 2.

Day 12 - The N-Body Problem

Day 12 - complete solution

A fun little problem.

Score: 2.

Day 13 - Care Package

Day 13 - complete solution

I am in awe of what the creator of Advent of Code has wrought in the form of intcode.

[intcode part 6]

Score: 2.

Day 14 - Space Stoichiometry

Day 14 - complete solution

A hard problem that was satisfying to solve.

Score: 2.

Day 15 - Oxygen System

Day 15 - complete solution

Not my proudest moment. I’m happy my intcode implementation works well enough for this kind of application now, but my utter inability to code a BFS routine is humiliating. In the end I had to use a modified Djikstra’s that I cribbed for last year’s day 22.

[intcode part 7]

Score: 2.

Day 16 - Flawed Frequency Transmission

Day 16 - part 1 Day 16 - part 2

I had a lot of trouble with part 2, mostly due to indexing errors.

Runtime is 2m16s for part 2, which is just barely acceptable.

Score: 2

Day 17 - Set and Forget

Day 17 - complete solution

This one was a slog!

I was very worried that my intcode interpreter was incorrect, but it was actually just me not being able to read the input specification correctly.

[intcode part 8]

Score: 2.

Day 19 - Tractor Beam

Day 19 - complete solution

This was supposed to be a breather…

From the beginning I realized that this problem is best expressed as x in terms of y, instead of the more usual y in term of x, and I made a mental note not to mix them up.

Of course, many hours later I realized I had done that just that.

[intcode part 9]

Score: 2.

Day 20 - Donut Maze

Day 20 - part 1

Part 1 yields easily to a modified BFS approach.

Update 2020-12-26

Part 2 is similar, only adding the “dimension” of the recursive level. There some really scruffy code to figure out the “edges” of the transition.

Score: 1.

Day 21 - Springdroid Adventure

Day 21 - complete solution

I felt zero interest in trying to puzzle this out so found some closed forms on the subreddit.

[intcode part 10]

Score: 0.

Day 22 - Slam Shuffle

Day 22 - part 1

Part one only done for now, part 2 requires way too much weird (read modular) math for me. Damnit, Cap’n, I’m continuous, not discrete!

Score: 1.

Day 23 - Category Six

Day 23 - complete solution

A remarkably straight-forward puzzle.

[intcode part 11]

Score: 2.

Day 24 - Planet of Discord

Day 24 - part 1 Day 24 - part 2

An interesting problem.

Update 2020-12-25 I revisited this after the multiple Games of Life in 2020. Instead of trying to be clever figuring out how to calculate the neighbors, I just created a giant lookup table.

This Reddit post contains all iterations of the example input and was helpful for debugging.

Score: 2

Day 25 - Cryostasis

Day 25 - complete solution

A fitting end to a good edition of Advent of Code!

Score: 2.

Sunday, 2019-08-11

Introducing HN&&LO

HN&&LO is a web page that scrapes the APIs of Hacker News and Lobste.rs and collates those entries that share a URL.

This lets you easily follow the discussion on both sites for these links.

I wrote this tool because I’m much more active on Lobste.rs than on HN, but I would like to keep “tabs” on both sites. I’m especially interested in how the information is disseminated between the sites.

“Slow webapps”

I’ve long liked to grab stuff via a web API, stuff it into a DB, and output a web page based on the data. This project was a first attempt to use a templating engine in Perl, and I’m ashamed to say I’ve taken so long to understand the greatness of this approach.

The data updates hourly, there’s rarely more than a couple of new entries on Lobste.rs per hour.

In fact, this can illustrate the difference in scale between the two sites.

Time period: 5 Jul 2019 11:19 to 8 Aug 2019 23:59 (both times in UTC).

  • Number of submissions with URLS on Hacker News: 26,974
  • Number of submissions on Lobste.rs: 899

Average number of submissions per hour: 33 for HN, 1 for Lobste.rs.

Once updated, a static web page is generated. This keeps overhead low.

Differences between Hacker News and Lobste.rs

Coincidentally, while I was writing this post, an article was published in the New Yorker about the moderators (all two of them) of Hacker News. This sparked a discussion on HN (obviously) but also on Lobster.rs (see both linked here).

To me, what makes Lobste.rs better is that it’s much smaller (one can easily catch up with a day’s worth of comments), the editing tools are more sophisticated, and the tag system allows one to determine whether a post is interesting or not. HN is much harder to grasp.

I think the tendencies noted in the article are common to both sites - male, youngish software developers with a rationalist bent. But I think Lobste.rs is a bit more self-aware of this fact (or rather, critiques are more visible there). In some ways, Lobste.rs, being a reaction to HN, defines itself culturally both for and against the bigger site.

Source and TODO

If you’re interested in pedestrian Perl code, source is here.

TODO list is here

Tuesday, 2018-12-25

Advent of Code 2018 wrapup

This year was a tough one. I believe the abundance of week-ends this December added to the number of quite tough problems. Day 15 seems to have been a really big stumbling block for many people.

I’m still not finished at time of writing, I’m at 38 of 50 stars. The TODO list is at the main entry for this year’s contest.

Despite miserably failing in completing each challenge in the day it was released I’m still happy I have some problems remaining going forward.

Saturday, 2018-12-01

Advent of Code 2018

This blog post is a work in progress

Project website: Advent of Code 2018.

Previous years: 2015, 2016, 2017.

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.

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):

  • match or beat last year’s score of 49/50.
  • solve all problems within 24 hours of release

Link to Github repo.

TODO

This year’s todo list:

  • Not completed
    • Complete day 23 part 2
    • Complete day 20
    • Complete day 17
    • Complete day 15
  • Completed, not published
    • Publish day 21
  • Refine
    • Day 16 - solve part 2 without manual intervention.
    • Day 14 - faster part 2.
    • Day 12 - rewrite part 2 to find the answer programmatically.
    • Day 22 - rewrite part 2 to use A*.
  • General - implement blogging and listing publication using templates
    • Publish day 18
    • Day 8 - clean up and publish solution
    • Day 11 - faster solution

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 16 - Day 18 - Day 19 - Day 22 - Day 24 - Day 25

Day 1 - Chronal Calibration

Day 1 - complete solution

Capsule summary:

Investigate the properties of summing an infinite list of integers.

A nice start to this year’s puzzles.

I had planned on getting up at 6AM to start with this but I spent the night before playing Fallout 4 so that didn’t happen.

Score: 2.

Day 2 - Inventory Management System

Day 2 - complete solution

Capsule summary:

Investigate the properties of the strings given as input.

Another O(n^2) solution, but for the small sizes involved it barely matters.

Perl’s string munging is helpful as always.

Score: 2.

Day 3 - No Matter How You Slice It

Day 3 - complete solution

Capsule summary:

Investigate the properties of overlapping areas given as input.

Nice and clean. I was worried I’d have to do some complicated lookups to single out the correct swatch in part 2, but it turns out that there was only one possible solution in my input.

Score: 2.

Day 4 - Repose Record

Day 4 - complete solution

Capsule summary:

Given a list of activities, determine properties about the times these activities occur.

Getting the correct answer without resorting to an external run through sort -n was the hardest part of this problem!

There are some nice solutions using a Schwartzian transform out there but to be honest I’d rather have something straightforward and dumb that can understood later.

TODO: better variable naming.

Score: 2.

Day 5 - Alchemical Reduction

Day 5 - complete solution

Capsule summary:

Remove elements from a list, based on rules on which neighbors an element has.

A quick and simple problem.

Score: 2.

Day 6 - Chronal Coordinates

Day 6 - complete solution

Capsule summary:

Investigate areas on a grid, expressed in Manhattan coordinates.

Keywords: Voronoi diagram

This took some careful perusal of the text and example to figure out. I had a lot of problems with my solution when I tried to merge part 1 and part 2 into one solution. Unfortunately I had overwritten the code that actually gave me the first star, and I broke it.

I felt justified to check out other solutions and finally re-wrote using those (essentially using a representation of the board to keep track of the data). The day after I took the time to re-write it again into a version closer to my original idea.

Runtime is a dismal 16s.

Score: 2.

Day 7 - The Sum of Its Parts

Day 7 - part 1 Day 7 - part 2

Capsule summary:

Find a path through a graph, given that some steps must be done to proceed.

Keywords: DAG, directed acyclic graph, topological sort

I’m really happy with solving this. I’m graph-aphasic, as in I’ve never ever grokked them in code, and was dreading finding some random Perl module that I didn’t really understand. In the end I just found the “endpoints” and processed it using a queue.

This made part 2 reasonably easy to code.

Score: 2.

Day 8 - Memory Maneuver

Day 8 - complete solution

Capsule summary:

Investigate the properties of a tree structure given in the form of a string of integers.

Keywords: tree structure, recursive

I had a lot of trouble with this, which wasn’t helped by stuff like people coming over to visit, dinner to cook and eat, and wine to drink. After these distractions were done with I could revisit the problem with fresh eyes.

Score: 2.

Day 9 - Marble Mania

Day 9 - complete solution

Capsule summary:

A game is played by placing marbles in a circle. Investigate the end state given the puzzle input.

Keywords: double-ended circular list

This was a fun problem that was marred by some irritating off-by-one errors in the results. We were blessed with a wealth of example inputs, and I could make most of them work by taking the largest or the next largest value. This gave me my second star, but it was hardly repeatable.

Double-checking my logic against other solution revealed I was thinking correctly, but had a stupid overrun where I managed to take more marbles than were actually available…

Runtime for part 2 is 30s, but you need quite a lot of memory to run it. My wimpy VPS cannot run it natively.

Score: 2.

Day 10 - The Stars Align

Day 10 - complete solution

Capsule summary:

Given a number of points, their positions and velocities, investigate whether they form a coherent message when printed.

Keywords: visualization

A nice palate-cleanser after the horrors of the week-end.

Runtime: 4.6s.

Score: 2.

Day 11 - Chronal Charge

Day 11 - complete solution

Capsule summary:

Investigate the values of subsquares on a 300x300 grid.

Keywords: summed-area table

Trying to solve part 2 using brute force took 173 minutes. Implementing a summed-area table reduced it to 3s.

Score: 2.

Day 12 - Subterranean Sustainability

Day 12 - part 1 Day 12 - part 2

Capsule summary:

A number of plants grow in an infinite line of pots. The existance of a plant for the next generation depends on its neighbors. Investigate what plants remain after a number of generations.

Keywords: cellular automata

This was a fiddly one. I got bit by the shallow copying nature of Perl’s data structures, but implementing the Clone module took care of that.

Then is was just a question of dealing with the inevitable off-by-one errors.

Part 2 was found by reasoning that the pattern would stabilize, and after that is was just a matter of finding the pattern and identifying the offsets.

My Part 1 code can either give the answer to the question with no input, or output some useful metadata if given another argument.

Part 2 answers the question by default, and gives the value for an arbitrary input if that’s given as an argument.

Score: 2.

Day 13 - Mine Cart Madness

Day 13 - complete solution

Capsule summary:

Carts move along a track with turns and junctions. Determine whether they collide.

I’m both proud and ashamed of this one. Proud because my basic code determining how the carts move was correct from the get-go. Ashamed because it took me all day to figure out the collision detection.

Runtime: 0.4s

Score: 2.

Day 14 - Chocolate Charts

Day 14 - part 1 Day 14 - part 2

Capsule summary:

A list is generated programmatically. Investigate its properties as it grows.

Keywords: pattern matching, brute force

Not my favorite problem, not least because my brute-force solution is killed by my VPS.

Runtime for part 2: 2m14s.

Score: 2.

Day 16 - Chronal Classification

Day 16 - complete solution

Capsule summary:

An obfuscated register manipulation routine is presented. Solve the program.

Keywords: registers

This years Register Rodeo! It was fun apart from the horrid input parsing.

Score: 2.

Day 18 - Settlers of The North Pole

Day 18 - complete solution

Capsule summary:

Investigate the properties of a Game of Life setup.

Keywords: game of life

A scruffy solution. I had no problems with part 1, but part 2 was plagued by off-by-one errors.

Score: 2.

Day 19 - Go With The Flow

Day 19 - complete solution

Capsule summary:

Decompile a deliberately inefficient algorithm.

Keywords: registers, decompilation

Decompilation problems are not my favorite problems.

Score: 2.

Day 22 - Mode Maze

Day 22 - complete solution

Capsule summary:

Find the quickest path between two points on a graph.

After some struggle, I finally figured out a good way to conceptualize this.

Right now I’m using straight Djikstra’s which is way too slow.

Edit 2021-01-09 it turns out my issue wasn’t with the Dijkstra’s algo per se, but instead with my implementation of the required priority queue. After using a high-performance version from CPAN I got my runtime down from 15 minutes to around 2 seconds.

Score: 2.

Day 24 - Immune System Simulator 20XX

Day 24 - complete solution

Man, this was a slog. I coded it all myself, but got help online from working solutions to figure out where I was doing it wrong.

Part 2 was found manually.

Score: 2.

Day 25 - Four-Dimensional Adventure

Day 25 - complete solution

Capsule summary:

Investigate points in 4D space.

Keywords: union

Last problem this year. Figured this out through brute force.

Score: 1 (final star only awarded if all other solutions are done!)

Tuesday, 2018-10-16

351: Hexagonal orchards

Reused code from 577 to bruteforce a sequence that I could search for in Sloane.

Monday, 2018-10-15

407: Idempotents

Got a good way just by observing patterns. Could have used Sloane to find a sequence but forgot about it. Resolved to be more thorough in the future.

Sunday, 2018-10-14

323: Bitwise-OR operations on random integers

I suck at probalities so had to google for an answer.

Friday, 2018-10-12

297: Zeckendorf Representation

I learned some extra stuff about Fibonacci numbers, that’s always fun.

Thursday, 2018-10-11

577: Counting hexagons

I enjoyed this one. As before I confirmed the sequence using brute force and geometry, then tried to search OEIS (Sloane) for sequences.

The geometry was tricky, so I was glad to finally pull it off.

Sunday, 2018-10-07

138: Special isosceles triangles

Generating the first few terms in the sought sequence with brute force leads to integers that can be searched for in OEIS.

Saturday, 2018-10-06

587: Concave triangle

Quite easy as befits its difficulty ranking of 20%.

I recycled my code for finding a root via bisection from the Blancmange problem.

I looked up efficient numerical integration methods and found a Perl implementation of Romberg’s method. I didn’t quite trust it so installed a Perl module for it instead. It turns out the first one was sufficient so it’s in the code now. I don’t want too many weird modules as dependencies.

Friday, 2018-10-05

549: Divisibility of factorials

Another old problem that I took a new look at!

226: A scoop of blancmange

Yet another old problem I started working on in 2012.

It’s straightforward numerical integration but I was tripped up by the error threshold.

Wednesday, 2018-10-03

504: Square on the inside

Revisiting an old problem. I was messing around with symmetries etc but it turns out you don’t really need it.

3 minute runtime isn’t ideal though.

Monday, 2018-10-01

622: Riffle Shuffles

This is a fun problem!

Thursday, 2018-09-27

500: Problem 500!!!

After some attempts at a solution at the limit I went back to the Wikipedia page on the divisor function.

Implemented a priority queue for the first time, unfortunately the plethora of modules implementing this in Perl made it hard to choose. Finally went for the POE framework.

Tuesday, 2018-09-25

381: (prime-k) factorial

Returning to a problem after 3 years. This is slightly optimized brute-force and can be much quicker.

Friday, 2018-09-21

346: Strong repunits

Easing back into PE again. I’m picking off problems in ascending difficulty order.

Tuesday, 2018-01-09

607: Marsh crossing

A fun problem!

My initial idea was to utilize Snell’s law, which was indeed the right idea, but I didn’t have the right constraints.

After a while I rethought the problem to minimize a multi-variable function using the “downhill simplex” algorithm.

Thursday, 2018-01-04

301: Nim

Problem description.

Brute-forcing for 5 minutes gave the correct answer, and access to the forum and an even faster solution…

Wednesday, 2018-01-03

118: Pandigital prime sets

Problem description.

Pretty happy with this solution!

Tuesday, 2018-01-02

111: Primes with runs

Project description.

Algo adopted from this solution.

349: Langton’s Ant

Problem description.

I had to write some code for AoC 2017 day 22 which matched up with this pretty nicely.

Friday, 2017-12-01

Advent of Code 2017

Project website: Advent of Code 2017.

Previous years: 2015, 2016.

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. Some require extra modules from CPAN.

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.

The times are hours and minutes from the time of the puzzle release (00:00 EST) until I posted an announcement on Twitter.

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

  • match or beat last year’s score of 49/50.
  • solve all problems within 24 hours of release
  • be among the first 750 on each day’s leaderboard

Final score

  • Problems solved by myself: 47/50. Not really happy with this. I got caught up in the hunt for keeping my place on the local leaderboard, instead of taking the time to actually solve the problems.
  • 3 parts not solved within 24 hours.
  • Average finishing place: 1,801 for part 1, 2,151 for part 2.

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 1 — Inverse Captcha

Day 1 - complete solution

A nice little warmup problem. Eric pulls his usual trick of making you assume something in part 1 that you have to unassume in part 2.

Score: 2

Time: 47m

Leaderboard placement: 783 / 748

Day 2 — Corruption Checksum

Day 2 - complete solution

My suspicion that there’s going to be a lot of functional list-munging in this year’s edition is strengthening.

Score: 2

Time: 2h40m (it’s a Saturday, so I slept in!)

Leaderboard placement: 2,676 / 2,318

Day 3 — Spiral Memory

My solution for day 3: part 1, part 2

A nice headfake again. Of course you’re not going to brute-force the spiral, keeping track of the coordinates for each element, then taking the Manhattan distance of the element you want when you reach it!

Instead you use a solution from Project Euler to segment the search space and find the solution nice and quick.

Then you get to part 2 and discover you need to generate the spiral after all…

Score: 2

Time: 8h23m (first Advent Sunday, shopping for Christmas)

Leaderboard: 2,578 / 3,249

Day 4 — High-Entropy Passphrases

Day 4 - complete solution

A stark contrast to yesterday’s problem. Perl’s text processing features usually make parsing input a breeze but in this case it was almost too easy. I guess I have to be careful for what I wish for in the future.

Score: 2

Time: 37m

Leaderboard: 1,544 / 1,314

Day 5 — A Maze of Twisty Trampolines, All Alike

Day 5 - complete solution

Ah, the list of instructions! An AoC classic.

Wise to previous problems I decided to incorporate test input from the get-go, and to include a debug output. This was a nice addition for part 2, as I could just run the test input and instantly confirm my changes worked.

Runtime for part 2 is around 17.5s, which, as the answer is around 25M steps leads to a “MIPS” value of 1.4.

Score: 2

Time: 41m

Leaderboard: 1,865 / 1,712

Day 6 — Memory Reallocation

Day 6 - complete solution

I liked this puzzle, even if it was a bit on the easy side.

An interesting algorithm for detecting cycles was pointed out in the daily solutions thread: Floyd’s Tortoise and Hare. I don’t think it will give better performance for the limited data set of the puzzle, but part of the fun of AoC is learning new things.

TODO

If I get some time in the future I’d like to rework this problem using an iterator for generate the states and using the Floyd algorithm.

Score: 2

Time: 51m

Leaderboard: 1,553 / 1,433

Day 7 — Recursive Circus

Day 7 - complete solution

I was sure my lack of CS knowledge would bite me, but after 10 hours I’m not seeing any comments like “actually this is just algorithm X” on the subreddit daily thread. I guess most people solved this like I did.

A fun problem, all in all.

Score: 2

Time: 5h22m - solved part one before leaving for work, but part two was delayed by meetings and a reinstalled work computer.

Leaderboard: 1,518 / 2,406

Day 8 — I Heard You Like Registers

Day 8 - complete solution

As this is not my first register rodeo, I ran a quick check to make sure the input values were what I expected (comparison operators, whether a field was an integer or not). After that it was simply a matter of encoding the rules.

I could have used Perl’s eval to evaluate the expressions, but I’m not 100% comfortable with it so I just used a giant if/else statement instead.

I chose to write a specific function to read values from the register hash, which made inserting a statement to capture part 2 very simple.

TODO

Implement using dispatch table?

Score: 2

Time: 1h15m

Leaderboard: 1,667 / 1,639

Day 9 — Stream Processing

Day 9 - complete solution

This was a fun one!

After perusing other solutions for day 8 I decided to implement a dispatch table for handling the characters. I’m glad I did because it made adding further checks quite easy.

Part 2 threw me for a loop. I got the wrong answer for the number of garbage characters, and trying to find where my assumptions were wrong in the giant puzzle input felt impossible. However, there are a number of example inputs, and after running my code on them I found where I was mistaken…

Score: 2

Time: 5h35m (I’m not gonna get up at 6AM on a Saturday…)

Leaderboard: 2,604 / 2,850

Day 10 — Knot Hash

My solution for day 10: part 1, part 2

Difficulty is ramping up.

The biggest issue I had with this was the @#%&*! array manipulation in part 1.

Score: 2

Time: 5h09m

Leaderboard: 2,149 / 1,867

Day 11 — Hex Ed

Day 11 - complete solution

A fun problem. I didn’t know anything about hex grids but like everyone and their mom I googled and found this excellent site that explains them well.

Score: 2

Time: 1h02m

Leaderboard: 1,110 / 1,007

Day 12 — Digital Plumber

Day 12 - complete solution

I could probably have solved this in a more Perlish way but here I at least understand what’s going on.

Score: 2

Time: 2h47m

Leaderboard: 2,108 / 2,038

Day 13 — Packet Scanners

My solution for day 13: part 1, part 2

This was the first problem that has a significant runtime (without optimization). Even after some work I have a ~10m runtime for part 2.

TODO

Optimize for faster runtime.

Score: 2

Time: 13h23m

Leaderboard: 2,462 / 4,224

Day 14 — Disk Defragmentation

Day 14 - complete solution

A nice mix of difficulty and entertainment. Unreasonably proud of independently finding the four-way flood fill algorithm.

Score: 2

Time: 4h51m

Leaderboard: 1,096 / 1,636

Day 15 — Dueling Generators

Day 15 - complete solution

Brute force, baby!

I used an iterator for part 2, then wrangled both solutions into one using that technique.

The generators are well known.

Score: 2

Time: 3h06m

Leaderboard: 1,130 / 1,929

Day 16 — Permutation Promenade

Day 16 - complete solution

After the usual struggles with Perl’s lists I got this working.

I decided to go with a dispatch table from the start, which made part 2 easier to implement.

Score: 2

Time: 4h34m

Leaderboard: 1,682 / 1,370

Day 17 — Spinlock

My solution for day 17: part 1, part 2

Solving part 1 gave some data for how to solve part 2. It took some fiddling though!

Score: 2

Time: 8h52m

Leaderboard: 2,067 / 2,990

Day 18 — Duet

My solution for day 18: part 1, part 2

So far the most entertaining problem. Bravo!

Score: 2

Time: 4h33m

Leaderboard: 1,015 / 1,057

Day 19 — A Series of Tubes

Day 19 - complete solution

This was supposed to be a “breather” problem, instead it stymied me something fierce.

Score: 2

Time: 8h36m

Leaderboard: 2,744 / 2,688

Day 20 — Particle Swarm

My solution for day 20: part 1, part 2

Gratified to finally be among the first 1,000 to solve this problem, especially considering how relatively easy it was.

Update Day 20 - alternative part 1 - closed form

Score: 2

Time: 2h29m

Leaderboard: 913 / 984

Day 21 — Fractal Art

Day 21 - complete solution

What a fiddly problem!

Score: 2

Time: > 24h

Leaderboard: 2,426 / 3,035

Day 22 — Sporifica Virus

My solution for day 22: part 1, part 2

This puzzle is based on Langton’s ant which I’ve grappled with for Project Euler. I chose not to re-use any code though.

Runtime for part 2 is 31s which is just barely acceptable

Score: 2

Time: 2h47m

Leaderboard: 1,094 / 1,022

Day 23 — Coprocessor Conflagration

My solution for day 23: part 1, part 2

I had to give up on part 2, it wasn’t interesting enough to power through. Credt for part 2 in source.

Score: 1

Time: 11h31m

Leaderboard: 1,287 / 1,826

Day 24 — Electromagnetic Moat

Day 24 - complete solution

I just couldn’t get this to work so had to bail. Credit in source!

Score: 0

Time: >24h

Leaderboard: 3,057 / 3,012

Day 25 — The Halting Problem

Day 25 - complete solution

My solution runs in 30s which can surely be improved.

Score: 2 (really 1)

Time: 3h31m for part 1

Leaderboard: 1,197 / 2,340

Tuesday, 2017-11-07

New host

For a number of years my friend Thomas has graciously hosted this blog, a shell account, and a number of other things that are essential to the modern person (IMHO). However external circumstances will deprive me of this service, for which I am sorry, for Thomas has been the best sysadmin, and it’s been free!

I’ve shelled out a couple FIAT dollars a month for a “droplet” at Digital Ocean, and worked to transfer stuff from the old server to the new. These are some notes in case I have to do it again.

I chose Ubuntu as a distro because I like the Debian-based packaging.

Web hosting and Perl CGI

I installed Nginx because I’ve vaguely heard it’s “better”. Getting it to deal with CGI scripts in Perl was a bit fiddly but it worked out OK.

You need the fcgiwrap and spawn-fcgi packages.

The following addition was made to the server section of Nginx config for my site.

# we have separate htdocs and cgi-bin dirs under the gerikson.com dir
# this location is to make sure we can have a specific section for cgi-bin
location /cgi-bin/ {
    root /home/www/gerikson.com/;
    try_files $uri =404;
    gzip off;
    fastcgi_pass unix:/var/run/fcgiwrap.socket;
    fastcgi_index index.pl;
    fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name;
    include fastcgi_params;
}

Added packages

These are needed for some stuff I host

libcgi-pm-perl
libconfig-simple-perl
libdate-calc-perl
libdatetime-perl
libdbd-sqlite3-perl
libdbi-perl
libjson-perl
libnumber-format-perl
libstatistics-linefit-perl
libtext-csv-perl
libwww-perl
lynx
mutt
sqlite3
zip
perltidy
tree
cpanminus
perl-doc

These are needed for coding contests

libmath-bigint-gmp-perl
libmath-prime-util-gmp-perl

Python 3 stuff

python3
python-pip
virtualenv

Friday, 2017-01-13

493: Under The Rainbow

Project description

Based on the difficulty raiting of this problem I guessed it had an analytical solution, and indeed the answer can be easily expressed in binomial terms.

Thursday, 2017-01-12

214: Totient Chains

Problem description.

Another Math::Prime::Util example.

211: Divisor Square Sum

Problem description.

Another Math::Prime::Util example.

131: Prime cube partnership

Problem description.

Scrounged around in the documentation to Math::Prime::Util and found this under the examples section.

Tuesday, 2017-01-10

105: Special subset sums: testing

Problem description.

The idea to use a bitmask to represent the sets is from this page, as is the clever way to test rule 2.

Thursday, 2017-01-05

Wednesday, 2016-12-28

Project Euler cleanup

Fresh from Advent of Code 2016 I thought it would be nice if I organized my Project Euler solutions and cleaned them up a bit.

They’re being added to my Github repo as I go through them, verify they are working on newer Perls, and generally try to streamline the code.

I’ve found a few “solved” problems that don’t actually have any solutions, but where I do have access to the answer forums. I’ve used solutions there for some problems, and credited the source in the comments.

Thursday, 2016-12-01

Advent of Code 2016

Project website: Advent of Code 2016.

My solutions for AoC 2015.

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. Some require extra modules from CPAN.

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.

The times are hours and minutes from the time of the puzzle release (00:00 EST) until I posted an announcement on Twitter.

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

  • solve all problems myself (higher cumulative score than last year’s 43/50).
  • solve all problems within 24 hours of release
  • be among the first 1,000 on each day’s leaderboard

Final score

  • Problems solved by myself: 49 / 50 — a big improvement over last year’s 43/50.
  • 3 parts not solved within 24 hours. Shortest time for both parts: 40 minutes. Average time: 5h07m.
  • Average finishing place for each day: 677.8 for part 1, 747.6 for part 2.

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 1 — No Time for a Taxicab

My solution for day 1: part 1, part 2.

I managed to get the correct solution in part 1 despite not taking absolute values in consideration, fixed in code.

Part 2 was frustrating as I didn’t have time to re-think the problem, instead I kludged something on top of part 1.

Score: 2, 9h50m.

Day 2 — Bathroom Security

My solution for day 2: part 1, part 2.

Actually reading the Wikipedia article linked from day 1 helped me with part 2.

Alternate part 2, inspired by this solution.

Score: 2, 4h21m.

Day 3 — Squares With Three Sides

My solution for day 3: part 1, part 2.

The hardest part of this problem was cleaning up the input…

Score: 2, 3h59m.

Day 4 — Security Through Obscurity

My solution for day 4: part 1, part 2.

A fun problem!

Score: 2, 3h38m.

Day 5 — How About a Nice Game of Chess?

My solution for day 5: part 1, part 2.

I already had the required modules installed since 2015 day 4 and initially thought this was going to be straight repeat. While part 1 was indeed simple enough, part 2 threw me for a little loop due to the requirements to keep track of previous entries.

Score: 2, 2h32m.

Day 6 — Signals and Noise

My solution for day 6. Alternative with more map.

Decided to try to solve this over breakfast.

Score: 2, 0h40m.

This was the last of the warmup problems. Things will get tougher from now on.

Day 7 — Internet Protocol Version 7

My solution for day 7: part 1, part 2.

Not very proud of part 2, but at least I know what it does. Using regexps would be the obvious choice but I frankly lack the regex-fu to handle it.

Update: some quick googling revealed the existence of lookahead to deal with overlapping matches, so I whipped together an alternative part 2. This runs appreciably faster (although still within a second).

Just made the first 1,000 submitters for part 2.

Score: 2, 4h36m.

Day 8 — Two-Factor Authentication

My solution for day 8, both parts.

Really didn’t want to do this, it reeked of fiddly bit-flipping, but after thinking a bit the solution presented itself.

Again just squeeked in under the 1,000 first submitters for both parts.

Score: 2, 4h27m.

Day 9 — Explosives in Cyberspace

My solution for day 9: part 1, part 2.

I’m debating whether to award myself 2 points for this, as I had to look for hints for part 2.

The issue was that I was running a recursive solution, but instead of simply counting the characters of a single part and then multiplying by the number of repetitions, I actually created a new array that was the part repeated repetitions times! This led to horrendous execution times.

Score: 2, 5h11m.

Day 10 — Balance Bots

My solution for day 10, both parts.

I usually don’t forget to sort numerically but I did this time, which led to a wild goose chase trying to find out why real input differed from test.

Family commitments prevented a faster time but I still submitted in the first thousand.

Score: 2, 8h15m

Day 11 — Radioisotope Thermoelectric Generators

Finally a solution after almost 6 days.

Not fantastically proud of this, kept plugging away at some solutions even if I’d have had better luck taking a step back and reconsidering. But I solved it myself!

The most problems I had was with the shuffling stuff to and from floors. The last piece fell into place when I realized I had to keep track of the elevator too when considering already visited states.

Solves part 2 in around 11m, which is just barely acceptable.

Score: 2.

Day 12 — Leonardo’s Monorail

Day 12 - complete solution

Score: 2, 5h05m.

Day 13 — A Maze of Twisty Little Cubicles

My solution for day 13: part 1, part 2.

I’ve been thinking a lot about day 11, so the breadth-first search concept came in handy.

Score: 2, 4h39m.

Day 14 — One-Time Pad

My solution for day 14.

This was both tough and kind of boring.

Key insight was this throwaway comment by /u/askalski. Each candidate index is stored in a hash keyed on the duplicate character, and any hit of quintuples is checked

A lot of subtle off-by-one errors made this quite frustrating.

Performance is respectable, especially part 2. Example input:

$ time perl ./d14.pl
==>22728
real    0m0.601s

$ time perl ./d14.pl 2
==>22551
real    0m41.553s

Update 16 Dec 2016 alternative version with cleaner code.

Score: 2, 12h18m.

Day 15 — Timing is Everything

My solution for day 15.

Fast and simple brute-force solved this one.

Score: 2, 1h06m.

Day 16 — Dragon Checksum

My solution for day 16.

The nice and tidy recursive solution I coded for part one takes 1m34s to complete part two, but this is not a very interesting problem so I will just leave it at that.

Score: 2, 3h22m (this is day off for me).

Day 17 — Two Steps Forward

My solution for day 17.

Straight-forward application of techniques known so far. Key to part 2 is to realize BFS returns all solutions, not just the shortest.

Score: 2, submitted after 8h57m on a Saturday.

Day 18 — Like a Rogue

My solution for day 18: complete.

Quick and dirty fourth Advent Sunday breakfast solution. Part 2 runs in 2m30s using the same code as part 1, just many more rows. Brute force baby.

I might try to improve part 2 later.

Edit: here’s a a second attempt. Credit.

Part 2 runtime is 33s for this version.

Score: 2, 3h25m.

Day 19 — An Elephant Named Joseph

My solution for day 19 part 1: part 1.

Part 2 defeated me, this is part 2 with copied code, credit in source.

Update: this alternative is way more Perlish, credit in source!

This is the first problem I actually bailed on, which is a step up from last year. I liked it in a way that you simply couldn’t just run part 2 as a straight continuation of part 1, but had to rethink your strategy, but this problem was too boring for me to bother doing that.

Score: 1, 5h49m.

Day 20 — Firewall Rules

Day 20 - complete solution

Straightforward. Runtime 0.11s.

Score: 2, 4h18m.

Day 21 — Scrambled Letters and Hash

My solution for day 21: part 1, part 2.

A boring and fiddly part 1 led to a straight-forward brute-force solution for part 2. That part finishes in 40s on my machine.

At least I finally got to learn how splice works…

TODO: implement dispatch table?

Score: 2, 5h19m

Day 22 — Grid Computing

My solution for day 22: part 1, part 2.

For part 2, I took a chance that there was nothing hindering moving the empty slot in straight lines apart from the “walls”. A simple count of the needed steps gave the solution.

Score: 2, 4h22m.

Day 23 — Safe Cracking

Complete solution.

Entirely unoptimized, runtime for part 2 is 101 minutes!

I was sidetracked by the fact that my first attempt at part 1 gave the correct solution, but failed for part 2.

TODO: better performance?

Score: 2.

Day 24 — Air Duct Spelunking

Complete solution

I used BFS to compute the distances between all points, then used the technique from AoC 2015 day 9 to generate all possible permutations and print them out.

Part 2 runs in less than 2 seconds.

Score: 2, 8h52m on Christmas eve!

Day 25 — Clock Signal

Complete solution

All done! Quick and dirty solution using brute force with crappy pattern detection.

Score: 2, 4h24m.

Monday, 2015-12-14

Advent of Code 2015

Project website: Advent of Code.

I started on these puzzles on 7 Dec 2015. So far I’ve completed all of them, all but a few on the same day they were posted.

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. Some require extra modules from CPAN.

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.

Final score: 43 / 50.

Github link.

Days 1 to 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

Days 1 to 4

Day 5 — Doesn’t He Have Intern-Elves For This?

My solution: part 1 - part 2.

I had to get help with part 2 here, found a regexp in the daily solutions thread for this day.

Score: 1.

Day 6 — Probably a Fire Hazard

Part 1 - part 2.

These could definitely be faster, both run in around 30s.

Score: 2.

Day 7 — Some Assembly Required

Had to scrounge around for tips on how to solve this. I had the basic idea down but the problem was keeping track of the solutions as I iterated around.

Score: 0.

Day 7

Update 2017-12-28 Day 7 - alternative complete solution

Day 8 — Matchsticks

Easily the most boring of the problems so far.

Part 2 only.

Score: 2.

Day 9 — All in a Single Night

Essentially the travelling salesman problem but the number of destinations is small enough to brute-force easily. Uses the Algorithm::Combinatorics module. Output is a list of permutations with the total travelling distance prepended, so just use sort -n to find the answer from the output.

Update 2017-12-28 Day 9 - alternative complete solution. This solution removes the need to sort an output file.

Score: 2.

Day 09.

Day 10 — Elves Look, Elves Say

Another computationally expensive problem but even part 2 runs in under 1 minute for me.

Submitted 3h25m after puzzle release.

Update 2017-12-28 Day 10 - alternative complete solution. Much faster regex-based solution from Rosettacode.

Score: 2.

Day 10.

Day 11 — Corporate Policy.

Day 11 - complete solution

So far my favorite problem!

Submitted 5h56m after puzzle release.

Score: 2.

Day 12 — JSAbacusFramework.io.

Another good puzzle. Uses the JSON module.

Day 12 - complete solution

Submitted 9h25m after puzzle release (I blame family commitments on weekends!).

Score: 2.

Day 13 — Knights of the Dinner Table.

Day 13 - complete solution

This is a modified day 9 with bidirectionally. Even part 2 which adds another element to the permutation finishes very quickly using brute force.

Submitted 5h03m after puzzle release.

Score: 2.

Day 14 — Reindeer Olympics.

A troll! The immediate brute force approach is to simply advance time 1s at a time and check the “position” of each deer at that time. But this is “obviously” dumb so I used a quicker approach for part 1. Part 2 made me regret it…

Submitted for 2 stars 4h04m after puzzle release.

Day 14 - complete solution

Day 14 - complete solution with fancy scoreboard

Score: 2.

Day 15 — Science for Hungry People.

A combination of outside factors and frustration at getting my indexes right made this a tedious slog.

Submitted for 2 stars 9h45m after puzzle release.

Score: 2.

Day 15 - complete solution

Day 16 — Aunt Sue.

A fun one. Submitted for 2 stars after 2h37m.

Score: 2.

Day 16 - complete solution

Day 17 — No Such Thing as Too Much

Tried a recursive approach first, but got stuck for the part 2 and looked in the daily thread for inspiration. Figured out how to use combinations by looking at other’s code.

Submitted for 2 stars after 6h18m.

Score: 1.

Day 17 - complete solution

Day 18 — Like a GIF For Your Yard

Conway’s Game of Life! I’ve never coded this before so it was a fun exercise.

I tried using arrayrefs first but got tripped up by the deep copy (dclone in the code) and decided to go for a hash of hashes instead. I think this contributes to the slow execution time of ~15s.

Submitted for 2 stars after 6h00m.

Score: 2.

Day 18 - complete solution

Day 19 (Saturday) — Medicine for Rudolph

A tough one! I solved part 1 no problems but had to hunt around for hints for part 2.

Day 19 - part 1. Day 19 - part 2 alternative solution.

Score: 1.

Day 20 (Sunday) — Infinite Elves and Infinite Houses

Lack of time and impatience led me to look for hints for this. I had the right initial idea but thought looking for divisors of an integer without the PARI package would be too slow, and I have yet to find a way to install that on the machine I’m using.

In the end it didn’t matter but I wanted this done.

Full credits in source.

Day 20.

Score: 0.

Day 21 — RPG Simulator 20XX

I went for a straightforward solution of generating all combos of items and then running a simulated battle with each.

Day 21.

Score: 2.

Day 22 — Wizard Simulator 20XX

Not a very good solution, relies on brute force to simulate all possible spell casts and then prints out a win or loss. Note that I had to run it for 5M iterations to get the answer to part 2. This is the only problem I didn’t finish in the same day as it was released (apart from the 7 first ones).

Day 22.

Score: 2.

Day 23 — Opening the Turing Lock

Straightforward apart from the slightly ambigious jio instruction — read carefully what it means.

Day 23.

Score: 2.

Day 24 (Christmas eve) — It Hangs in the Balance

I tried to finesse the answer by hand first but it didn’t simply work to manually adjust the packages to get desired answer. Instead I checked valid combinations, but with the following assumptions/optimizations:

  1. I sorted the packages in descending order to check those combinations first.
  2. I assumed the answer wouldn’t contain more than 6 elements, so just checked combinations up to that value of k.
  3. I didn’t bother to confirm the remaining packages would sum correctly.

Runs in about 2s.

Day 24.

Score: 2.

Day 25 (Christmas day) — Let It Snow

Straightforward iterative solution. Runs in over half a minute, those with CS backgrounds used modular exponentiation and got much faster results.

Day 25.

Score: 2.

(un)License

The solution files are in the Public Domain.

Tuesday, 2015-11-17

315: Digital root clocks

Problem description.

This was a fiddly one. But once you get the actual state changes correct it’s simply a matter of extracting the values that will be displayed and calculate how much it’ll “cost” to display them.

Saturday, 2015-11-14

387: Harshad numbers

Problem description.

Another one off the list of unsolved problems in ascending difficulty. Perl string manipulation makes this one easy.

Wednesday, 2015-09-09

357: Prime generating integers

Problem description.

I had to try to solve this without access to my previous favorite Perl module: Math::Pari, and it took almost an hour to run.

Thursday, 2014-01-30

Poetry

John Gruber:

File Edit View Special

When I see those four words, they evoke not a thought but a feeling. Poetry, in the form of a menu bar.

I mention this in chat, and literally seconds later @varjag writes

< varjagg> roses are red
< varjagg> violets are blue
< varjagg> you are my special
< varjagg> as file edit view

Saturday, 2012-11-17

90: Cube digit pairs

An unexpected way of using two cubes to make a square.

The key to this is to handle the fact that 6 and 9 are equivalent. Once I’d handled that I had to eliminate duplicates. Otherwise it’s pretty straightforward.

Tuesday, 2012-10-16

188: Tetration

The hyperexponentiation of a number.

You get to the start of the trail by reading the Wikipedia article on tetration.

Monday, 2012-10-15

110: Diophantine reciprocals II

Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.

We know from problem 108 how the answer is formed. The trick is to generate a number of integers from the prime factors, to find which combination has the most divisors.

Thursday, 2012-10-11

148: Exploring Pascal’s triangle

Problem link.

This was a fun one, I did try a 2nd-order brute force approach after some research and realized it would break the 1-minute rule but let it run anyway for about 10 minutes and got the answer.

Wednesday, 2012-10-03

204: Generalised Hamming Numbers

Problem description.

Did quite some research on this but in the end extended a “classic” Hamming number generator (for 5-smooth numbers) that I found on Rosettacode.com. Bit of a cheat and runs in 2 minutes instead of the required 1.

Tuesday, 2012-10-02

121: Disc game prize fund

Investigate the game of chance involving coloured discs.

I suck at probabilities and had to google for hints for this one.

Monday, 2012-10-01

144: Investigating multiple reflections of a laser beam

Investigating multiple reflections of a laser beam.

This was fun, once I figured out the geometry. Another thing to watch out for is comparing 2 floats for equality.

Thursday, 2012-09-13

93: Arithmetic expressions

Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

Straightforward brute force, helped by the Perl Algorithm::Combinatorics module to find different permutations and so on.

Runs in about 36s with some debugging info.

Wednesday, 2012-09-12

174: Counting hollow square laminae

Counting the number of “hollow” square laminae that can form one, two, three, … distinct arrangements.

This was basically the same as 173, my code needed changes to 3 lines and some hash counting code.

Tuesday, 2012-09-11

173: Hollow Square Laminae

Using up to one million tiles how many different “hollow” square laminae can be formed?

On a roll today!

This wasn’t too hard once I sorted out all the fencepost errors.

101: Optimum polynomial

Investigate the optimum polynomial function to model the first k terms of a given sequence.

o/~ All by myself…

Pretty proud of this one. Used linear algebra to solve for the coefficients in each successive polynomial. Unfortunately the Perl Math::Matrix package didn’t let me easily extract the values so I had to copy-paste into a separate script to check against the correct values.

94: Almost equilateral triangles

Investigating almost equilateral triangles with integral sides and area.

The hinge for this is discovering that the solution can be expressed as a Pell’s equation, this puzzle is helpful.

Monday, 2012-09-10

88: Product-sum numbers

Fell for the spoiler urge, not proud of it.

Friday, 2012-09-07

84: Monopoly odds

In the game, Monopoly, find the three most popular squares when using two 4-sided dice.

This marks my return(?) to Eulering. I did a lot of research for this a long time ago, and was planning on implementing a Markov chain approach based on the results from this page but after falling for the trap of googling for solutions I found that most people simply simulate the dice rolls, counting the number of times the dice hits each cell.

I simulated 1 million throws and got a result in about 5 seconds.

Thursday, 2011-11-03

193: Squarefree numbers

Problem description.

Found searching for “project euler” in OEIS.

Saturday, 2011-10-29

Friday, 2011-10-28

187: Semiprimes

Problem description.

Easily done if you have a few million primes on hand.

There’s a sequence in Sloane that gives the answer directly, too!

Thursday, 2011-10-27

100: Arranged probability

Finding the number of blue discs for which there is 50% chance of taking two blue.

I started researching the hypergeometric distribution and thought about comparing it to a binomial distribution at large numbers before twigging that if you expand the problem it’s a quadratic Diophantine equation. There’s an online solver that provides factors for these equations and after that it was simply a matter of plugging them in.

Wednesday, 2011-10-26

203: Squarefree Binomial Coefficients

Problem description.

I had in mind optimisations in only calculating half the triangle, but in the end it didn’t signify. I used the Pari issquarefree() function.

Biggest issue was forgetting telling Perl to use arbitrary precision integers.

119: Digit power sum

Investigating the numbers which are equal to sum of their digits raised to some power.

I turned this over in my mind trying to find some limit so I didn’t have such an enormous search space. Then I found A023106 in Sloane which gives all but the last few terms, and then it was really fast to brute force.

To be quite honest this was a bit easy for this level.

Thursday, 2011-01-27

Monday, 2011-01-03

Keeping a FreeBSD system up to date

I like using FreeBSD compared to Linux (or “lulnix” as we cool kids say nowadays) but distros like RedHat and Ubuntu have the edge when it comes to making it easy to keep your system up to date with the latest patches.

You’d think there was a simple one-shot way of doing this, but so far I’ve settled for the following method. It’s documented here as much for my own memory as anything else.

  1. refresh your ports tree with cvsup: cvsup -g -L 2 /usr/local/etc/ports-supfile (you should edit the ports-supfile to reflect your geographical location).
  2. run the portupgrade command: portupgrade -a -PP -Rr -i.

The options I use for portupgrade are:

  • -a: all ports
  • -PP: use only packages (use a single P if you want to compile a port where a package isn’t available)
  • -Rr: both recursive and upwardly recursive
  • -i, for interactive. I run this because once when I ran without it my perl got upgraded to a new point release under me and broke my CPAN modules. YMMV.

Monday, 2010-11-29

On calculators

One of the sons in the house is in the last year of high school and as math is not his favorite subject he’s only now raised his need of a graphing calculator. I did a perfunctory research of the market and purchased a generic Texas Instruments model for around €70.

One thing that struck me is that today’s calculators aren’t that much different than the ones I remember when I was a first-year college student, lo so many years ago. We’re still looking at a plethora of multiply-labeled buttons, grayscale screens, and extremely limited memory. In an age where a basic calculator is practically disposable, memory is cheap and handheld UI innovation rampant thanks to cellphones and computers, it’s a bit weird to see a tech area looking so stable.

Part of the reason is of course that if you’re dealing with students, you don’t want them to be too connected or have too much computing at their disposal during exams. But that just raises another questions. Barring global catastrophe (in which case basic math skills would be nice to have, but knowledge of agriculture even more desirable) any pupil attending higher education will have a calculator within reach for the rest of their lives.

So, basic arithmetic has been automated, and in fact, even quite complicated algebra has been too, thanks to tools like Mathematica and Maple. In fact, as long as you have access to the web Wolfram Alpha will solve most equations faster than you can type them in.

Is it time to face the fact that doing arithmetic with pen and paper is like making pots on a pottery wheel? It’s a nice craft, probably will be quite popular for a small part of the population, but it’s essentially not needed in a modern society?

Please note I’m not saying mathematics is obsolete. It’s probably more important than ever. But I do think we need to find a better way of teaching it than just mechanically learning rules like long division and decomposition of factors. Leave the drudgery of math to the computers, and try to move on to teach the actual use of math in real life.

Friday, 2010-11-12

The obligatory iPhone post

So I have an iPhone now, as have 60% of Stockholm’s inhabitants. It’s no longer a very interesting thing to say.

I moved to the iPhone from the Nokia E61, which I still think is a really good phone for its time. Here’s some random thoughts on the differences.

The iPhone excels at music playing and gaming. I’m not that big a fan of differnt social networking apps, but the web browser is miles better. Basic stuff like alarms work better. SMS rocks.

I miss having a physical keyboard though, but this is something I think I’ll get used to in time.

What the E61 was better at was multitasking, and IRC and Twitter apps. I used WirelessIRC and Gravity both by Jan-Ole Suhr, and they rocked. I use Rooms for IRC and Echofon for Twitter, and neither app has the ease of access and navigation that WirelessIRC and Gravity has.

However, it should be noted that these were the only apps I purchased for the E61. Purchasing software is so much better and easier on the iPhone it’s not even possible to compare.

Another thing I miss is the ability to “remote control” the phone from the computer. While Nokia PC Suite and its successor Ovi are a horrible conglomeration of ugly little apps, at least they made it easy to browse content and most especially read and write text messages from the desktop. I can’t really complain about iTunes syncing but I do wish there was something for Messages on the desktop.

Monday, 2010-09-06

Some thoughts on Google Wave

When Google announced Wave the hype was immense, it was like everyone took Gmail and squared it and thought it would be that awesome! And basically that’s what the Wave developers thought too. Well I can’t remember what I did but I got an invite and hopped on, and right away realised that there was no-one there. The invite-only start (for performance reasons) limited the appeal and usefulness of Wave.

Because I think it was pretty useful, at least once they got the early kinks worked out. Me and some far-flung mates used it to plan some trips together, and Wave was pretty useful for that. It would have been better with a mobile interface but it was decent.

The thing is, Wave wasn’t the next coming of Gmail, it was the next coming of Microsoft Outlook. Outlook is merely the front-end to Exchange, which does all the boring and useful bits (routing email, planning calendars etc). And sure, it works, but not very well. At my current place of work we have Office Communicator Server (OCS) which is basically MS Live Messenger in a corporate suit. The nice thing about OCS is that it integrates into Exchange, so you can see whether a coworker is online, or in a meeting or whatever.

However, sometimes you want to start from the task, not the person. That’s where Wave began - you had a project, or a trip, or just a task involving some people. It could start with just you and then expand, like a lot of tasks do. However, instead of snowballing into a long mail thread, you actually had the option of keeping Waves clean and on topic.

Wave was flawed - it was before its time, it tried to solve problems that don’t often turn up in the wider world of the web, but which do turn up lots of times within organizations. Maybe Microsoft will learn from Wave and build better collaboration tools than Exchange.

Friday, 2010-04-09

Fear of an iPad planet

[Warning, this post contains profanity.]

There’s a lot of blogther[1] around these here tubes about the closed nature of the Apple iPad. Exhibits: Doctorow and Danny O’Brien.

Basically the the thesis is that if this closed platform takes over, all creativity is stifled by unaccountable gatekeepers and humanity is doomed.

That’s bollocks. Here’s why.

Primo. The iPad is a toy for rich people. Period. Only a tiny minority will buy it, and only a minority of that minority will use it as their only way to access the internet. For fuck’s sake, you need a computer (PC or Mac) to sideload content to it[2]. There’s zero chance that this will become the only fucking way to access the internet, because Apple doesn’t sell to everyone on the planet. They sell to people who can afford Apple products. So far, they’ve made a lot of money doing this, while companies like Lenovo and HP are struggling. Why should they change?

Secundo. Closed platforms are the fucking greatest for some things, like gaming. I happen to think that the console systems are better for gaming than the PC platform. And if you disagree with me on this, you’re per definition in the minority. Seriously, check out the sales figures. Money talks. And if we’re gonna get serious about tackling spyware and malware and shit, we should mandate that 99% of internet users only get to use a closed, locked down, Trusted Computing-verified internet appliance. The general-purpose PC is like a fucking chainsaw in these people’s hands.

Tertio. If you happen to raise a geek or feel a pressing need to make him or her learn to code fucking Haskell, there are literally MILLIONS of used PC’s that can run your choice of Lulnix, and he/she can spend their precious time coding blog platforms when they should be out in the sun, getting D vitamins.

Quarto. Who died and made Apple god? If the iPad succeeds in taking over the world, they’ll end up like IBM or Microsoft. This is not the end of computing history.

In closing, shut the fuck up already, you apocalyptic freetards.

Update 2010-04-14: the tone of this post has been inspired by the Angry Mac Bastards podcast, who go forth and rip Doctorow and Winer to shreds regarding their iPad views in episode 55. Listen to them for even more sound and fury, signifying nothing much!


[1] a portmanteau of “blog” and “blather”, and yes, I realise if you have to explain it’s not very good. Go invent your own term.

[2] Conveniently. I guess you can buy stuff OTA too. Do I look like I do research?

Thursday, 2010-03-25

Notes on Project Euler

Project Euler “is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve.” In other words, you need to get down and program to solve the problem[1].

I’ve recently reached Level 3 (solved over 100 problems) and thought I’d share some notes on what I’ve learned.

PE programming is “pure” programming, as in you’re working with algorithms and not systems. There’s rarely anything more complicated than file access needed. In fact, I’d say you need an aptitude for problem solving rather than programming, and the skills needed to solve PE problems are probably not really translatable to real work out in the real world, where you’re dealing with real people and real hardware and networks. To be sure, nowhere on PE do they say that this is programming in the wider sense, as opposed to Computer Science, but you’d be surprised how many CS grads think it does (I’m mocking you, Haskell nerds!).

The typical PE problem looks amenable to brute force, but it pays to research before jumping in. Wikipedia and Mathworld are great resources for a lot of the problems, often explaining the math behind them and sometimes having the algorithms you need.

Spoilers. I find it pretty hard to concentrate on a problem and not want to know the solution, especially when I’m into “grind” mode and just want to level up (this happens a lot with me and puzzle games too). There are plenty of spoilers around for the early problems (the ones that most people manage to solve) but as you move up they get sparser and sparser, and are usually in languages other than your chosen one. Often it’s enough for me to just get a hint. After you’ve solved a problem, you get access to a forum where others discuss their solutions. This can be an eye opener, but there’s no need to share your crappy solution if you don’t want to.

I use Perl. I thought of using PE to learn another language (Python), but finally I felt it was more fun to explore something I’m pretty proficient in than to learn something else. Perl has all the things you need for these problems (so far), especially as there are tons of libraries for specific applications. One of the more useful is Math::Pari, an interface to the Pari suite of numerical algorithms.

Perl is really nice for stuff like string manipulation and set operations. It’s also really easy to build ad-hoc data structures, although the syntax grows hairy really fast.

Python seems very popular among PE participants. Another popular language among the people who bother to post to answer threads is J), and of course Haskell has some vocal devotees.

I find it challenging and fun to work on these problems, and I encourage you to do the same!

[1] although there are some wizards who manage with pencil and paper, at least for the earlier problems.

Tuesday, 2009-04-07

Setting foreground and background colours in iTerm

Update 2011-09-03: I’ve just gotten my hands on an iMac running Lion, and Terminal.app now has built-in support for different colour schemes. This blog entry has a nice one.

iTerm white-on-black

The Mac has strangely few terminal emulators, unless you set up X and invoke the Deep Ones in other ways. So far, I’ve found iTerm to be the best one.

You cannot set iTerm to use black background and white text, but you can trick this with AppleScript. Put the following into your .bash_profile or similar:

setColor() {
  osascript -e "tell application \"iTerm\"
    set current_terminal to (current terminal)
    tell current_terminal
      set current_session to (current session)
      tell current_session
      set background color to \"black\"
      set cursor color to \"white\"
      set foreground color to \"white\"
    end tell
  end tell
end tell"
}
## now invoke the function, and clear the screen 
setColor
clear

When you start a new window, the background will be white but it will soon become white on black, as ghod intended.

Thanks Jedrek for helping me with this!

Thursday, 2009-04-02

Deleting an Outlook message via a filter

If you try to set the option “delete it” from the Outlook Rules and Alerts wizard, you’ll get a message that that particular rule is “client-side only”, which means that Outlook has to be running for the rule to work.

If you’re trying to set up rules for mobile use, for example, this is less than ideal.

One workaround is to choose “move to a folder”, and move to the folder “Deleted Items”. This achieves basically the same thing, with the added bonus of keeping the message for review if needed.

Monday, 2009-01-05

Ignoring idiots on IRC

Sure, IRC has the /ignore command, but it just removes all mention of a nick from a channel. Sometimes this is what you want, but Mike recently shared a little irssi script that will simply censor anything an idiot says. That way the conversation isn’t as disjointed as it could be otherwise.

I’ve modified the script so that more than one nick can be censored. My version is here. Basic knowledge of Perl is required to use this. It’s also easy to evade by changing nicknames, I’ll try to fix this in later versions.

To install in irssi, follow these instructions.

Monday, 2008-04-14

Dell Gold support — awesome. Their followup survey? Much less so

I recently had a spot of bother with my work lappy. The screen went all blurry after a short while of use. I didn’t mind this as it didn’t happen when the laptop was docked.

However I felt it needed to be fixed, so I called the Dell Gold support line in Sweden. Very professional service from them, a tech arrived the day after with a replacement motherboard and LCD screen. So far, so happy.

This morning I arrive to find an email from Dell asking me to participate in a survey about my experience. I’ve ignored these in the past, only to be spammed by reminders, and I thought that in this case I should take it as a I was very happy with the service I got.

So like a fool I click the link to some god-awful outsourced company (prognostics.com). A series of barely literate, badly sequenced survey questions pop up. Each takes about a minute to load. They are repetitive. They have no discernable order. They seem to reiterate the same damn point over and over again.

So I waste about 10 minutes of my time with this crap and feel obscurely that I’m more unhappy with the level of service I’ve received than before. This is the last time I’m answering these, I’ll be creating a filter to bin them from now on.

Saturday, 2008-01-12

Getting native 1400x1050 resolution with Xorg i810 drivers on a Dell Latitude D505

I’ve been using Ubuntu 7.10 on a Latitude D505 for a while now, and I’ve always been disappointed with the screen resolution. The max I could get was 1280x1024, while the native resolution is 1400x1050.

I recently had to reconfigure X on this machine (dpkg-reconfigure xserver-xorg) and chose the intel driver (recommended by the configure script). However, it turns out that this driver hangs the machine when you close the lid. The older driver i810 works in this regard, but the max resolution is too low.

The solution is to use the 915resolution application. This does some weird hacking of the video BIOS to allow Linux to use the full resolution.

Using it in Ubuntu is a breeze. Simply install the .deb package and reboot.

Thursday, 2007-11-01

Somewhere in the heavens… they are waiting

Instant nostalgia. Thanks to the Aleph One project and these instructions I was able to compile the Aleph One application on my Ubuntu lappy and play Marathon 2.

It’s a lot of fun, especially as I can point out “we had that in Marathon 13 years ago” while playing Halo 3 with Leo. This pisses him off no end.

Friday, 2007-09-28

Is it Friday?

The site isitfriday.net provided an essential service: answering the question “is it Friday today?”.

Apparently it wasn’t deemed essential enough, cause the service no longer exists.

David has stepped up to the breach with http://isitfriday.gnapp.org/. Here’s my contribution:

#!/usr/bin/perl -w
use strict;
use CGI qw(:standard);
my $wday = (gmtime( time ))[6];
my $msg = 'no';
if ( $wday == 5 ) {
    $msg = b( 'YES!' );
}
print header;
print start_html( 'Is it Friday?' );
print h1({-style=>"text-align: center"}, $msg );
print hr;

You can see it in action here.

N.B. this script is not tested for days other than Friday. Also, your timezone will have to be in the general vicinity of UTC for it to work for you.

Thursday, 2007-05-24

Scripts in Nautilus

I found out today that if you’ve installed a script in Nautilus, you won’t see it in the contextual menu until you’ve visited the script directory in Nautilus.

Install a script in ~/.gnome2/nautilus-scripts/ and making it executable.

Then visit that directory in Nautilus to “enable” it.

I’m not sure if you have to do this for every script you install, or only for the first one.

Sunday, 2007-05-13

For the love of $DEITY, check the return of system in Perl!

So there we were at work, wondering why part 2 of our home-brewed customer survey system[1] wasn’t sending the mails it should be sending.

Turns out that the perl script responsible read from one table in the database to find out the recipients of the emails. It then generated a form of authentication, updated the database to say that the mails had been sent, then called

system( "/usr/local/bin/email.pl" );

where email.pl was another script written by the same developer.

Note the lack of return value from that call to system.

So what happened was that in the distant mists of time (about 2 months ago) we switched source control systems. Apparently we lost our executable bits on some scripts, because email.pl was readonly and owned by Apache.

Had we checked the return value, we would at least have had a warning that something was wrong. But now the system apparently “worked” for a month or so, and we only realised that nothing was being sent when the responses dried up.

I’ve re-written the code to check if the call to email.pl was succesful, and only if it was would the database be updated.

Now we have to re-send all emails older than a month, which will probably put our server on a spam blacklist. Sigh.

Lesson: code defensively.

[1] Why we haven’t got a third-party solution for this is hard to understand, unless you worked there 2 years ago, when development time was considered free and maintainance was never factored in the cost equation.

Tuesday, 2007-04-03

[SvSe] 24-timmarsmyndigheten?

Screenshot from 24h.myndigheten.se

Monday, 2007-04-02

Variables in (s)printf formats

Here’s a fun thing I learned for the first time today: you can have variables in formats for printf or sprintf.

Here’s a contrived example:

#!/usr/bin/perl -w
use strict;

sub variable_format {
    my ( $in, $len ) = @_;
    printf( "%0${len}d\n", $in );
}

variable_format( 42, 3 );  # prints 042
variable_format( 42, 9 );  # prints 000000042

Interestingly, I can’t find any mention of this in Perl’s documentation for sprintf.

Tip of the hat to Linus.

Sunday, 2007-03-25

Twitter posting script in Perl

Here’s a stab at a script for posting to Twitter:

#!/usr/bin/perl -w
use strict;
use LWP::UserAgent;
use XML::Simple;
use URI::Escape;

my $username = 'your_twitter_username';
my $password = 'your_twitter_password';

my $message = shift or die "usage: $0 message\n";

if ( length $message >= 140 ) {
    $message = substr( $message, 0, 139 ); 
    warn "truncating message to: $message\n";
}
$message = uri_escape( $message );

my $ua = LWP::UserAgent->new();
# tell Twitter who we are
$ua->agent( "$0/0.1 " . $ua->agent );

my $req = HTTP::Request->new( POST =>
                  'http://twitter.com/statuses/update.xml');
$req->content_type( 'application/x-www-form-urlencoded' );
$req->authorization_basic( $username, $password );
$req->content( "status=$message" );

my $res = $ua->request( $req );

my $xml;
if ( $res->is_success ) {
    $xml = XMLin( $res->content );
} else {
    print "Posting failed " . $res->status_line . "\n";
}

my ( $created, $name, $screen_name, $id ) =
  ( $xml->{created_at},
    $xml->{user}->{name},
    $xml->{user}->{screen_name},
    $xml->{id} );

print << "EOF";
Your message

  $message

was succesfully posted at $created 
as user $name ($screen_name) with ID $id.
EOF

Thanks to Jim for the inspiration.

By the way, I’m gerikson at Twitter.

Update 2007-03-27: I removed the wget version as I don’t maintain it any more.

This Twitter API wiki is pretty helpful.

Sunday, 2007-01-28

FizzBuzz

Nearly flubbed this. Time constraints suck.

First implementation, aka bog-standard:

#!/usr/bin/perl -w
use strict;
my $i = 1;
while ( $i < 101 ) {
    if ( $i % 3 == 0 and $i % 5 == 0 ) {
    print "FizzBuzz\n";
    } elsif ( $i % 3 == 0 ) { 
    print "Fizz\n";
    } elsif ( $i % 5 == 0 ) {
    print "Buzz\n";
    } else {
    print "$i\n";
    }
    $i++
}

Maybe I’ll play a bit with this later… the online comments have degenerated into golfing in people’s favourite languages.

Check here for a funny-cause-it’s-true “example” in Java, everyone’s favourite enterprise language… (first comment).

Tuesday, 2006-08-15

Mounting LVM volumes from a USB disk

Quick start

  • attach the disk to the computer
  • Run the following commands as root or via sudo:

(The first command finds LVM volumes. The second one activates them.)

root@host:~# vgscan  
  Reading all physical volumes.  This may take a while...  
  Found volume group "foo" using metadata type lvm2  
root@host:~# vgchange -a y foo  
  2 logical volume(s) in volume group "foo" now active  
root@host:~# ls /dev/foo  
  root swap_1  
root@host:~# mount /dev/foo/root /mnt

Background

This may help others, I had a hell of a time getting it working, but that was just because I didn’t understand the concepts at all.

Background: a Linux laptop lost its video card recently. I was able to back up the most important files via FireWire to another machine before I couldn’t see the screen, but I felt I should have the entire hard drive handy in case I miss anything. So I removed the hard drive from the laptop and put it in a $40 USB enclosure.

An aside: this resulted in a very nice little wallet with 40G of storage, but with one big disadvantage. It gets its power entirely from the USB port, but unless you have powered port (generally one at the back of a tower PC) you need an external power brick. Most laptops cannot run the drive from their ports. Lugging a power brick around kinda negates the portability of the device. The point was moot in my case, as there was no power brick included in the package.

(In addition, el cheapo USB hubs can’t power this sucker either. I had a 3.5” enclosure with 3 USB ports that could, however.)

So, I plugged the drive to a laptop also running Linux (Ubuntu, same as the last one). The drive automounted and I could see the /boot partition. Obviously that’s formatted in some generic fashion that the automounter can recognise. A scan of /var/log/messages gave the device as /dev/sdb.

root@inspiron8600:~# fdisk /dev/sdb

The number of cylinders for this disk is set to 4864.
There is nothing wrong with that, but this is larger than 1024,
and could in certain setups cause problems with:
1) software that runs at boot time (e.g., old versions of LILO)
2) booting and partitioning software from other OSs
  (e.g., DOS FDISK, OS/2 FDISK)

Command (m for help): p

Disk /dev/sdb: 40.0 GB, 40007761920 bytes
255 heads, 63 sectors/track, 4864 cylinders
Units = cylinders of 16065 * 512 = 8225280 bytes

  Device Boot      Start         End      Blocks   Id  System
/dev/sdb1   *           1          31      248976   83  Linux
/dev/sdb2              32        4864    38821072+   5  Extended
/dev/sdb5              32        4864    38821041   8e  Linux LVM

(note that I’m root here, no mucking around with sudo when there’s a lot of commands to issue!)

OK, so the data is on /dev/sdb5, in a LVM volume. What the heck is that? Linus has this to say:

You don’t want to use LVM, it’s a source of confusion and headache. It’s a toy variant of VxFS but doesn’t work nearly as well.

Words to live by, but Ubuntu has helpfully stashed my data into an LVM volume and I needed to get it back.

The short answer is to run vgscan:

root@inspiron8600:~# vgscan
 Reading all physical volumes.  This may take a while...
 Found volume group "Ubuntu" using metadata type lvm2

OK, this is where I went off the rails. You see, I thought that the volume group “Ubuntu” was the one on the host hard drive. So I spent a lot of time googling for solutions (someone somewhere must have had this experience before!), reading about using Windows (ugh!) and how not to do stuff. Then I read what I should have from the the beginning, the LVM HOWTO.

In the section Common tasks it tells you about Creating a volume group. This could then be mounted.

Aha! I tried

# vgcreate usb_volume /dev/sdb5

but got the message that it was already a part of a volume group, namely “Ubuntu”!

Mounting /dev/Ubuntu to /mnt was a moments work. I was able to copy the needed data easily.

(Update: /dev/Ubuntu showed up because I ran vgchange before, not knowing what that command did.)

Caveat: In the course of writing this, I tried to recreate the steps I used. However, I got this message back:

root@inspiron8600:~# vgscan
  Reading all physical volumes.  This may take a while...
  /dev/Ubuntu/root: read failed after 0 of 4096 at 38168100864:
    Input/output error
  /dev/Ubuntu/root: read failed after 0 of 4096 at 0: Input/output error
  /dev/Ubuntu/swap_1: read failed after 0 of 4096 at 1581187072:
    Input/output error
  /dev/Ubuntu/swap_1: read failed after 0 of 4096 at 0: Input/output error
  Found volume group "Ubuntu" using metadata type lvm2

I couldn’t mount the partitions either.

Looks like I was in the nick of time!

I have no clue whether the act of mounting the LVM volume via USB ruined it, or if this was just a bad disk. Be careful!

Thanks to Stefan and Linus for helping me with this!

Saturday, 2006-05-20

Networking between Linux and Windows with FireWire (IEEE1394)

I wanted a quicker way to transfer files between two laptops than via wifi. One’s is running Ubuntu Linux, the other Windows XP.

Both machines have a 4-pin FireWire port (labeled 1394, apparently someone owns the rights to the “FireWire” name and someone else doesn’t want to pay royalties). I borrowed a 4-pin to 4-pin cable from my brother-in-law and set out to try to connect the machines.

I knew that Windows has built-in IP-over-1394 support, the clincher was enabling it under Linux. Ubuntu has the required modules installed and the kernel I use can use them. There is a project page for Linux1394 if you need to get the modules and install them by hand.

I loaded the network module eth1394 by running

$ sudo modprobe eth1394

(Maybe this isn’t strictly necessary, but I didn’t find any reference to the module in the dmesg output.) Checking /var/log/messages, I saw that the interface got the name eth2.

Then I connected the computers with the cable (after enabling the interface in Windows). I heard a “cable connected” sound in Windows. Running

C:\> ipconfig /all

showed me that the interface was up. After a while I got a private address (169.254.203.16, netmask 255.255.0.0). I configured a static address on the Linux side:

$ sudo ifconfig eth2 up 169.254.203.17 netmask 255.255.0.0

I then started an FTP client in Windows, pointed it to the address defined in Linux, and started transferring files. I’m getting about 2.5 MB/s which isn’t too shabby.

Update: some quick perusal of the transfer logs gave me a average transfer rate of 1.45 MB/s.

Friday, 2006-03-10

Outputting dates in RFC822 and ISO8601 formats in Perl

Correctly formatted date strings are needed for RSS generation, among other things RSS. Diego shows how to do this in Java. This is my version in Perl

 #!/usr/bin/perl -w

 use strict;
 use POSIX qw(strftime);

 my $now = time();

 # We need to munge the timezone indicator to add a colon between the hour and minute part
 my $tz = strftime("%z", localtime($now));
 $tz =~ s/(\d{2})(\d{2})/$1:$2/;

 # ISO8601
 print strftime("%Y-%m-%dT%H:%M:%S", localtime($now)) . $tz . "\n";
 # RFC822 (actually RFC2822, as the year has 4 digits)
 print strftime("%a, %d %b %Y %H:%M:%S %z", localtime($now)) . "\n";

The output is

 2005-01-05T01:35:08+01:00
 Wed, 05 Jan 2005 01:35:08 +0100

There are some small issues I haven’t found clarification for at this late hour of writing. The first is whether the day should be zero-padded in the RFC822 case. As it is now it’s space-padded. According to RFC822, the day is zero-padded.

The second is how to handle locale settings — RFC822 specifies that the weekdays and months be in the US locale. I’m pretty sure that you need extra magic in Perl for this not to work, but I’ll take a look at that tomorrow.

Yet another reason to standardize on ISO8601, I guess.

Update 2006-03-10: Eli Billauer was kind enough to mention this error to me, kudos to him.

Monday, 2006-02-20

Formatting FAT32 under Windows XP

Apparently you can’t format volumes larger than 32GB in FAT32 under WinXP. Anything larger will have to use NTFS. I’ve got a largish drive in a USB-connected enclosure that I’d like to use under Linux, so NTFS was out. As far as I know, the Linux support for it is still experimental.

Well, as the good book says, Google, and ye shall find. The first suggestions from MS was to boot into Win98/ME and use their FORMAT command to do this. This is akin to performing brain surgery with a butter knife dipped in pus.

But I also found Jens-Uwe Mager’s Windows port of the Linux command mkdosfs that worked like a charm.

So now I’m backing up the MP3’s on this machine. Can life get much better?

Tuesday, 2006-01-31

Converting from ISO-8859-1 to UTF-8 in Perl

When posting my observations via email any Swedish characters are converted to quoted-printable ISO-8859-1 by Gmail. However, this blog is in UTF-8. This is how I translated the input from the mail message.

#!/usr/bin/perl -w
use strict;
use MIME::QuotedPrint qw( decode_qp );
use Encode qw( decode encode );

# split the mail message
my ( $headers, $body );
{
    local $/ = undef;
    ( $headers, $body ) = split( "\n\n", <STDIN>, 2 );
}

# decode the qouted-printable input
$body = decode_qp( $body );
# decode to Perl's internal format
$body = decode( 'iso-8859-1', $body );
# encode to UTF-8
$body = encode( 'utf-8', $body );

print $body, "\n";

The result is piped into a second script that formats the actual posting.

Pretty basic, eh? But until you know how, it can be a bit frustrating getting this to work.

Friday, 2005-12-30

Perl tools for mp3s

I recently had to edit a bunch of mp3s. I found the following Perl modules helpful.

  • mp3cut. Contains a script mp3cat that concatenates mp3 files. Very simple to use.
  • MP3::Tag. For all your mp3 tagging needs. Contains a script mp3info2 that can read and update tags.

These modules work fine under Cygwin running in Windows.

Wednesday, 2005-12-28

iTunes “skip shuffle” and “remember playback” settings

I grabbed a bunch of audio books in mp3 format but was shocked, shocked I say! when the files weren’t bookmarkable (i.e. they didn’t remember where I stopped listening) and worse, the files were included in the shuffle. When you have 1,388 files, each a minute long, that kinda sucks.

I pecked around in iTunes a bit and saw that there was a setting in the Info->Options panel for a track that included the checkmarks

  • Remember playback position
  • Skip when shuffling

Perfectomento! BUT… you can only set these options one file at a time. Damn you Apple! Damn you to hell!!

(If you don’t use AppleScript. Which I don’t. Because I don’t have a Mac.)

I found 2 links on Google which offer some alternatives. The reason for this post is essentially that del.icio.us is down ATM and I need somewhere to post these:

Update 2005-12-29: basically there are two ways of handling this.

  • Convert to AAC format and rename

I tried this variant, but the resulting files were much larger than the files in mp3 format. I guess you can get around this by playing with the converting options, but I suspect they only apply to importing from CDs (see the second link above).

  • Merge the mp3 files and set the appropriate settings manually.

I went with this variant. A quick search of CPAN resulted in a bunch of utilities I could use. I merged the tiny files into chapters, then added what ID3v2 tags I could. The rest were added in iTunes, along with the required playback and shuffle options.

I will try to find out more about ID3v2 tag handling later, so as to automate this even more.

Saturday, 2005-11-12

Ubuntu rocks!

Due to a little accident, my wife’s standard laptop is hors de combat — basically, I dropped our son on it (from a small height, I hasten to add) and the power connection broke. So it boots, for about 5 seconds, before discovering that the battery is flatter than Kansas.

I have in my possession an elderly laptop with no more than 256M of RAM, much too little to run a modern Microsoft OS. So I decided to check Ubuntu out. This is supposed to be “Linux for human beings”, so I figured this would be OK for non-geeks.

I downloaded an install CD via BitTorrent and used it to install it. The installation went really well. I had to fight my old-skool Debian and OpenBSD instincts and just let things go as designed. Ubuntu has made a great product — it installed seamlessly on the lappy and presented a clean, workable graphical interface that I think will be acceptable for Linux-o-phobes.

The only thing that didn’t work out of the box was the wi-fi pc-card I bought expressedly for its OpenBSD compatibility. However, I discovered that I had no less than four wi-fi cards lying around, and the oldest 3Com card worked fine.

I’ve been using this laptop all day (in between re-stacking our woodpile) and I really enjoy it. Small stuff, like Alt-Tab window-switching and Alt-F4 window close work exactly like in Windows. But having a real Debian system underneath just feels sooo much better than Windows crap leavened with Cygwin goodness.

Wednesday, 2005-09-14

The good old days

Matthew: Generation VIC20.

Chris: So Dad, what’s a computer science class for at school?
Me: Well, you learn to program there for example.
Chris: Program?
Me: Yes, to write computer programs using a special language.
Chris: You mean like games?
Me: Well, yes I suppose.
Chris: Like Star Wars Knights of the Old Republic?
Me: Umm, no.

Classic.

I guess you could learn a lot by copying source code, even if it was just BASIC spaghetti code. With line numbers.

Tuesday, 2005-08-30

Date in another timezone

Cool hack in Unix: if you know the zonefile abbreviation for a timezone, you can use it to get the date there:

$ TZ=PST8PDT date
Tue Aug 30 05:07:39 PDT 2005

This also works:

$ TZ=America/Los_Angeles date
Tue Aug 30 05:08:17 PDT 2005

Timezone files are in /usr/share/zoneinfo on OpenBSD and Linux.

Monday, 2005-08-22

Screen quickstart

This is quick basic intro to GNU Screen.

If you haven’t installed screen, do so. It rocks.

Starting up

Start screen. You’ll get a splash screen. Hit space to make it go away.

Depending on your flavour of *nix, you’ll get between 1 and n screens. First one is numbered 0. Try to switch to screen 1: Ctrl-a 1. If you get a message, create screen 1 with Ctrl-a c (create). Now you can switch back and forth between 0 and 1 with Ctrl-a 0 and Ctrl-a 1.

Want a “real” Ctrl-a? (If you’re in Emacs, you do.) Type Ctrl-a a.

Detaching

Start an editor in one screen, load a file and start editing. Detach with Ctrl-a d (detach). Logout of the shell, then login again. Attach to the screen: screen -r (reattach). You should be back where you left. Continue editing.

Finally

Screen is perfect for flaky connections, you’ll be back where you left off even if you get a hangup.

You can use screen -r -d to cleanly reattach from another session.

If you want a bunch of screens at startup, edit your ~/.screenrc. Mine looks like this:

shell -$SHELL
screen -t SHELL0  0
screen -t ROOT    1
screen -t SHELL2  2
screen -t SHELL3  3
screen -t SHELL4  4
screen -t SHELL5  5

The first line starts the current $SHELL in login mode. The others set up six windows and gives them titles.

Type man screen for more info.

Happy screening!

Update: here’s a more full-featured tutorial. (Via NTK.)

Wednesday, 2005-08-17

Django CRUD

Matt has written a nice tutorial on how to use Django in a simple CRUD situation: Django Generic Views: CRUD.

(CRUD, by the way, stands for Create, Read, Update, Delete — basic database manipulation. The title of this post is in no way a reflection on Django on my part.)

Matt and others are very excited over Django — it’s Ruby on Rails for Python. I’ve been meaning to learn Python for a long time, but lately I’ve felt I’m too old a dog for new tricks. More on this in a later post, maybe.

Tuesday, 2005-03-08

OpenBSD wi-fi hardware

This list is here so that I can check out hardware in stores via the phone.

  • ADMtek ADM8211 based CardBus/PCI adapters (atw) (G)
  • Aironet Communications 4500/4800 ISA PnP, PCMCIA and PCI 802.11b adapters (an)
    • Aironet 4500/4800
    • Cisco 340/350
  • Atheros AR521x based CardBus 802.11a/b/g adapters (ath), including: (G)
    • 3Com 3CRPAG175
    • Aztech WL830PC
    • D-Link DWL-A650
    • D-Link DWL-AB650
    • D-Link DWL-AG650
    • D-Link DWL-G650B
    • Elecom LD-WL54AG
    • Elecom LD-WL54
    • Fujitsu E5454
    • Fujitsu FMV-JW481
    • Fujitsu E5454
    • I/O Data WN-AB
    • I/O Data WN-AG
    • I/O Data WN-A54
    • Linksys WPC51AB
    • Linksys WPC55AG
    • NEC PA-WL/54AG
    • Netgear WAB501
    • Netgear WAG511
    • Netgear WG511T
    • Orinoco 8480
    • Orinoco 8470WD
    • Proxim Skyline 4030
    • Samsung SWL-5200N
    • SMC SMC2735W
    • Sony PCWA-C700
    • Sony PCWA-C300S
    • Sony PCWA-C500
  • Atheros AR521x based PCI 802.11a/b/g adapters (ath), including: (G)
    • D-Link DWL-A520
    • D-Link DWL-AG520
    • D-Link DWL-G520
    • HP NC4000
    • Linksys WMP55AG
    • Netgear WAG311
    • Netgear WG311
    • Proxim Skyline 4032
    • Senao NL-5354MP
  • Atmel AT76C50x based USB 802.11b adapters (atu), including: (G)
    • Acer Peripherals AWL300
    • Acer Peripherals AWL400
    • Aincomm AWU2000B
    • Bluetake BW002
    • D-Link DWL-120
    • Geowave GW-US11S
    • Linksys WUSB11
    • Linksys WUSB11-V28
    • Netgear MA101 rev B
    • OQO model 01 builtin wireless
    • Ovislink AirLive WL-1120USB
    • OvisLink AirLive WL-1130USB
    • SMC 2662W-AR
    • SMC 2662W-V4
  • Intel PRO/Wireless 2100 802.11b adapters (ipw) (G)
  • Intel PRO/Wireless 2200BG/2225BG/2915ABG 802.11a/b/g adapters (iwi) (G)
  • Intersil PRISM-2-3 based 802.11b Compact Flash adapters (will be detected as PCMCIA adapters) (wi)
    • Buffalo AirStation
    • D-Link DCF-660W
    • ELSA XI800
    • Linksys WCF12
    • Netgear MA701
  • Intersil PRISM 2-3, Lucent Hermes and Symbol Spectrum 24 based PCMCIA 802.11b adapters (wi), including:
    • 3Com AirConnect 3CRWE737A
    • ACTIONTEC HWC01170
    • Addtron AWP-100
    • Agere Orinoco
    • ARtem Onair
    • BUFFALO AirStation
    • Cabletron RoamAbout
    • Compaq Agency NC5004
    • Contec FLEXLAN/FX-DS110-PCC
    • Corega PCC-11
    • Corega PCCA-11
    • Corega PCCB-11
    • Corega CGWLPCIA11
    • Dlink DWL650 revisions A1-J3
    • ELSA XI300
    • ELSA XI325
    • ELSA XI325H
    • EMTAC A2424i
    • Ericsson Wireless LAN CARD C11
    • Gemtek WL-311
    • Hawking Technology WE110P
    • I-O DATA WN-B11/PCM
    • Intel PRO/Wireless 2011
    • Intersil Prism II
    • Linksys Instant Wireless WPC11
    • Linksys Instant Wireless WPC11 2.5
    • Linksys Instant Wireless WPC11 3.0
    • Lucent WaveLAN
    • NANOSPEED ROOT-RZ2000
    • NEC CMZ-RT-WP
    • Netgear MA401
    • Netgear MA401RA
    • Nokia C020 Wireless LAN
    • Nokia C110/C111 Wireless LAN
    • NTT-ME 11Mbps Wireless LAN
    • Planex GW-NS11H Wireless LAN
    • Proxim Harmony
    • Proxim RangeLAN-DS
    • Samsung MagicLAN SWL-2000N
    • SMC 2632 EZ Connect
    • Symbol Spectrum24
    • TDK LAK-CD011WL
    • US Robotics 2410
    • US Robotics 2445
  • Intersil PRISM 2-3 and Symbol Spectrum24 based PCI 802.11b adapters (wi), including:
    • 3Com AirConnect 3CRWE777A PCI
    • Belkin F5D6000 PCI (a rebadged WL11000P)
    • Corega CGWLPCIA11 PCI
    • Eumitcom WL11000P PCI
    • Dlink DWL520 PCI revisions A and B
    • Global Sun Technology GL24110P PCI (untested)
    • Global Sun Technology GL24110P02 PCI
    • Intersil Mini-PCI
    • LinkSys WDT11 PCI (a rebadged GL24110P02)
    • NDC/Sohoware NCP130 PCI
    • Netgear MA301 PCI
    • Netgear MA311 PCI
    • US Robotics 2415 PCI (rebadged WL11000P)
    • Nortel E-mobility 211818-A
    • Symbol LA4123
  • Intersil PRISM 2.5/3 based USB 802.11b adapters (wi), including:
    • Acer Warplink USB-400
    • Actiontec HWU01170
    • AirVast WM168b
    • Ambit WLAN
    • Apacer Wireless Steno MB112
    • ASUS WL-140
    • Compaq W100
    • Corega WLUSB-11
    • Corega WLUSB-11 Key
    • D-Link DWL-120 (rev F)
    • D-Link DWL-122
    • I-O DATA WN-B11/USB
    • Intel PRO/Wireless 2011B
    • Intersil Prism 2X
    • JVC MP-XP7250
    • Linksys WUSB11 v3.0
    • Linksys WUSB12
    • Melco WLI-USB-KB11
    • Melco WLI-USB-KS11G
    • Melco WLI-USB-S11
    • Microsoft MN510
    • Netgear MA111 (version 1 only)
    • Pheenet WL-503IA
    • Planex GW-US11H
    • Siemens SpeedStream SS1022
    • Sitecom WL-022
    • Syntax USB-400
    • US Robotics 1120
    • Z-Com XI-725/726
    • Z-Com XI-735
    • ZyXEL ZyAIR B-200
  • Ralink RT2500 based CardBus 802.11b/g adapters (ral), including: (G)
    • MSI CB54G2
    • Surecom EP-9428-g
  • Ralink RT2500 based PCI 802.11b/g adapters (ral), including: (G)
    • ASUS WL-130g
    • Minitar MN54GPC-R
  • Raytheon Raylink and Aviator 2.4/PRO PCMCIA 802.11 FH adapters (ray)
  • Realtek RTL8180L based CardBus 802.11b adapters (rtw), including: (G)
    • Corega CG-WLCB11V3
    • Netgear MA521

(G): Drivers for hardware marked with (G) are only included in the GENERIC kernels, but are not included on the various distribution floppies (including the cd-rom boot image).

(Source: OpenBSD i386 hardware list.)

Saturday, 2005-02-05

Gnus and Microsoft Outlook

For a long time I have been having trouble sending mail to people using Microsoft’s mail clients Outlook and Outlook Express. I use Gnus, an all-singing, all-dancing news-mail-and-everything reader for use in Emacs.

The trouble was that if I included any 8-bit characters in the header of the message, Outlook would translate any 8-bit characters in the body of the message to an equal sign and two hex characters. This was intensely irritating, as I naturally assume that all free software is superior to commercial offerings, especially Microsofts.

The trouble is that the version of Gnus I’m using (v5.8.7) doesn’t encode the headers in quoted-printable, thus confusing Outlook no end.

The solutions is to place the following in your .emacs or .gnus file:

;; iso-8859-1 support for headers
(require 'gnus-msg)
(add-to-list 'gnus-group-posting-charset-alist
     '(message-this-is-mail 'iso-8859-1 (iso-8859-1)))

Thanks to Kai Großjohann for this info.

Keywords: Gnus, gnus newsreader, GNU/Emacs, Emacs, Xemacs, MIME, mime, quoted-printable, transfer-encoding, Microsoft Outlook, Outlook Express, mangled, 8-bit characters.

Note: this was originally posted on another server, I’m posting it here in an effort to clean up my online life.

Wednesday, 2005-01-12

Combining PDF files

Need to combine two or more PDF files into one under Unix? Use the following command:

  gs -q -dNOPAUSE -dBATCH -sDEVICE=pdfwrite -sOutputFile=merged.pdf \
  source1.pdf source2.pdf source3.pdf etc.pdf

Obviously, you’ll need Ghostscript for this to work.

(From macosxhints)

Tuesday, 2004-10-05

No Piker

For some reason (probably because I feel an itch to hack) I was thinking about Plan 9 today. So it seemed an omen that /. had a call for questions for Rob Pike, co-creator of Unix and Plan 9.

I read some of the links in the article, and this pessimistic view left me thinking. Pike’s point is that (academic) software research no longer matters. We’re in a sterile wasteland of Windows, Linux, and the Web. No new ideas are being explored.

Well, that’s fine as far as it goes, but a meme that’s brewing is the coming dominance of mobile devices and content — quite different from desktop or server computing.

These points from the article show some possible fields for research:

Only one GUI has ever been seriously tried, and its best ideas date from the 1970s. (In some ways, it’s been getting worse; today the screen is covered with confusing little pictures.) Surely there are other possibilities. (Linux’s interface isn’t even as good as Windows!)

Ties in nicely with this post.

There has been much talk about component architectures but only one true success: Unix pipes. It should be possible to build interactive and distributed applications from piece parts.

Again relevant in the mobile space.

The future is distributed computation, but the language community has done very little to address that possibility.

Who knows? Mobiles are getting more and more powerful. GPS, encryption need processing.

The Web has dominated how systems present and use information: the model is forced interaction; the user must go get it. Let’s go back to having the data come to the user instead.

Also very relevant from a user perspective. Data must come to you, when and where you want it, with a minimum of fuss.

Will academia pick up the thrown gauntlet? Lets hope someone does.

Monday, 2004-10-04

Teaching kids to code

Matthew asks how one goes about to teach kids to code. Viking is too small yet, but it’s an interesting question. I know Hanna is quite proficient in HTML, mostly by copying and pasting, but Leo has shown no interest whatsoever in coding.

Part of the problem is the polished and complex nature of todays computers. In our day, you could slavishly copy pages of code and get something that worked. Even if it was just copying, you got down and dirty with the code. Some of it stuck. A curious kid (which I was not) could explore further, learning more and more. Whether learning Basic and VIC-20 assembler was a good thing is another question…

But now? Who can feel that they can produce something like Doom 3 by themselves?

Having said that, I believe a programming environment should have a graphic component. A former co-worker’s son loves (loved? it’s been a while) a DOS-based program for scripting dungeon adventures. A language of that kind could introduce the building blocks of programming — loops, conditionals, events — in a fun way that gives instant feedback and makes debugging fun.

An OO component could make it easy to “clone” your succesful monster, trap, whatever, and re-use the code. Introducing test cases is perhaps overkill at this stage…

I haven’t seen Lego’s Mindstorm stuff, but if anyone can make IDEs for kids, it should be them.

Update: Bill Ward writes in a comment:

For me it was BASIC on the Commodore too. But today’s kids have options as well. I think Javascript may be a good choice. My wife is taking a Flash class at the local college, and teaching me what she is learning. That could be a good choice too, except for the fact that it’s rather expensive.

I remember someone prophesying that Windows Scripting would be the next “laymans programming language”, but I haven’t seen MS promoting it that way. Having an easy to learn powerful scripting language built into the OS would introduce lots of people to programming, not just kids.

Wednesday, 2004-05-26

why I know perl

I learned Perl in my first real consulting gig at Agero. A large business directory company in Sweden wanted to synchronise their print catalogue with the Web. Additionally, they wanted an interface for customers to create their own ads on the Web. This was the sexy part of the project. I wasn’t involved there.

The synchronisation didn’t work yet, so every Monday my colleague had to take a 650 MB XML-file and feed it to a Java program that inserted the contents into a big old Oracle database running on a Sun Starfire. She was much more billable than I was, so as I incautiously admitted to Un*x knowledge I was asked if I could take over this job.

The XML was full of errors, unescaped ampersands, invalid characters… The Java program choked if it couldn’t parse the file, so you had to manually search for the error and fix it, then try again. A successful run took about 9 hours.

I started by chopping up the file into the component entries and checking for bad stuff. This is trivial, just set $/ to whatever end element suits your fancy, but it took some reading of the Perl Cookbook before I had it nailed.

Then I started looking at how to automate this stuff. I eventually wrote a sophisticated run-control program that could be started with at, and that sent email when something went wrong.

Just when I had cut down the effective load time from three days to about 11 hours, the whole project got axed. I later learned that this was the third attempt to integrate the print version with an online database.

The contractor more or less blamed the whole debacle on us, even though it could be fairly laid at bad project management and unrealistic promises from the client to its customers. Oh well.

In the middle of my next project, I was cding up from a directory over a slow ssh link and accidentally rmd all my perl code. When I called the admins of the machine they helpfully informed me that as the machine wasn’t in production it didn’t have backups.

So now I know more Perl than I really want to. But I’m still learning more every day.

Wednesday, 2004-04-14

ordering email

After a tip from Rui, I’ve started to sort my work mail (mail addressed to me personally, and the support box) into quarterly archives.

Long experience has told me never to throw away mail, and the quarter seems to be a good time period in which to ask yourself “when did I get that mail?”

Wednesday, 2004-03-24

HTML typography

Learn about the fifteen spaces defined in Unicode at this page.