Failover Trigger: Strictly ordered concurrency

I've stumbled on this concurrency pattern a few times now, and figured it's worth a quick write-up. The basic setup is a number of tasks that must not run simultaneously, and later tasks are only triggered if/when an earlier task fails. With fully-nonblocking code it can be tricky to synchronize everything correctly. Enter the Failover Trigger.

void inputSucceeded(Input input) { /* cleanup... */ } void noInputSucceeded() { /* cleanup... */ } void runTask(Input input, SettableFuture<Void> failover) { // Calls either failover.set(null) or inputSucceeded(input). } final AtomicReference<ListenableFuture<Void>> failovers = new AtomicReference<>(immediateFuture(null)); void addInput(final Input input) { final SettableFuture<Void> failover = SettableFuture.create(); failovers.getAndSet(failover) .addListener(() -> runTask(input, failover)); } void noMoreInputs() { failovers.getAndSet(null) .addListener(() -> noInputSucceeded()); }

This now allows any number of addInputs to be run concurrently, but ensures that everything in runTask (up to the failover.set call, at least) is fully synchronized. Inputs are handled on a first-come-first-served basis. If noMoreInputs is called after all inputs are added, then exactly one of inputSucceeded or noInputSucceeded will run to perform whatever cleanup is necessary.

I call this the "failover trigger" pattern because it provides each task with a trigger it can use to optionally start the next task.

git ir: an alternative to git rebase --interactive

My name is Steve and I'm a gitaholic. Git it pervasive in my workflow, both in my job and in my hobby projects. I'm also addicted to rebasing. At work, I tend to have ten to twenty branches open at a time. Many of these are chained in a giant stack, waiting for code reviews one after another. A few are branched out directly from the master branch. When I sync my repository or submit one of my changes, I then go about rebasing all the rest of the outstanding branches on top of that.

Unfortunately, git rebase just doesn't cut it for this. A while back I wrote git rebase-tree that would rebase a whole branched tree from one root to another (bringing all the branches along with), but it had a black eye in conflict handling, requiring a prompt for "continue/skip/abort". So I would need to open up a second terminal to git status and resolve the conflict, etc (or more typically, run git conflicts in emacs). I had been meaning to redo git rebase-tree with its own --continue flag, but my experience with another custom function (git diff-mail, which I use at work to prevent the changelist mailer from counting all the earlier changes that were already counted in a previous changelist) taught me that this can cause problems, as I often needed to git rebase --continue; diff-mail --continue, plus --abort often got confusing and sometimes actually clobbered my real changes (fortunately they've been easy to reconstruct so far). But it occurred to me that git rebase already has a queue, and with some clever manipulation, I can make it do what I want.

Enter git ir.

This function takes a list of branches, a commit to rebase them onto, and optionally a commit to rebase them from (in case they're already on top of the destination). It sets up an interactive rebase session but completely ignores the plan git prepares, instead using its own plan that includes a few additional commands in the rebase plan.

# Extended Commands:
# !, exec!  = mandatory command (the rest of the line), reinserted on failure
# b, branch = sets the named branch to the current commit
# (, push   = pushes the current commit onto the stack
# ), pop    = pops the current commit from the stack

The initial plan is effectively equivalent to git rebase-tree (though slightly more permissive). But with some quick edits (adding or removing parentheses, for instance) a tree of single-commit branches all off the same base can be instantly converted into a chain of dependent branches, and vice versa.

Once the initial plan is complete, it's ordinary git rebase the rest of the way, so when conflicts arise, it's back to the normal git rebase --continue (or --skip or --abort) workflow to handle them! Aborting happens for free. Moreover, no branches are moved until all commits have been successful rebased, so aborting before that brings everything exactly back to where it started. Finally, if you don't want it to be interactive, just call it with :: (which I alias to 'EDITOR=: ').

Installing the Haskell Platform

It all started with the 2013 Christmas Tree Lecture. Professor Knuth challenged the audience to explore skew ternary trees and their relationship with a subclass of rooted planar graphs. I decided it might be fun to rewrite his SKEW-TERNARY-CALC program in Haskell, but in order to maximize its utility, it should target its front-end to the web browser. I learned out about the Fay monad and decided to give a try (see <future post>, hopefully). So as a first step, I tried to cabal install fay, only to find that I had a Dependency Mess™. Fine, I could use a fresh Haskell install. Unfortunately my laptop is currently stuck on Ubuntu 12.04, which is stuck at ghc-7.4. So I purged all my GHC and cabal data, temporarily installed a ghc-7.4 binary to bootstrap the new GHC, and went on building it. In light of the confusing package database issues, I figured it would be easiest to simply install everything to a user-writable directory, ~/local/opt/ghc-7.6.3 and ~/local/opt/haskell-platform-2013.2.0.0, so that I can then add --global as a default cabal-install option and operate out of a single package db.

$ cd ~/Downloads/ghc-7.6.3 $ sudo aptitude install ghc $ OPT=$HOME/local/opt $ ./configure --prefix=$OPT/ghc-7.6.3 $ make && make install

This went fine (though it took a few hours on my laptop), so I was now ready to install the Haskell platform. I eventually tracked down the right configure flags:

$ cd ~/Downloads/haskell-platform-2013.2.0.0 $ sudo aptitude purge ghc $ ./configure \ --prefix=$OPT/haskell-platform-2013.2.0.0 \ --enable-shared \ --enable-profiling \ --disable-user-install $ make && make install

Now the fun starts

Unfortunately, make failed. It turns out that scripts/build.sh sets GHC_PACKAGE_PATH in its build_pkg function when it builds with Cabal, and Cabal is incompatible with this option. Fine, we can fix that:

$ sed -i '/GHC_PACKAGE_PATH=/ s/^/#/' scripts/build.sh $ make && make install

Not surprisingly, this also fails, a little later in the process. This time, alex is failing to build without happy. But happy is supposed to be part of the Haskell platform, and it should be smart enough to build its dependencies in the right order. Indeed, there's a bug on this that's been open for a year (and the original reporter even included a patch!). I rearranged the dependencies and went on my way. Another error. Apparently happy also needs happy to build. Great, so there's no way around bootstrapping with a binary distribution. I found out right afterwards that alex has the same bootstrapping problem.

$ sudo aptitude install happy alex $ make && make install $ sudo aptitude purge happy alex

Now it looks like we're good to go. Cleaning things up a bit,

$ cd ~/local/opt $ ln -s ghc-7.6.3 ghc $ ln -s haskell-platform-2013.2.0.0 haskell-platform $ for a in ghc/bin/*; do ln -s ../opt/$a bin/ done $ echo PATH=$OPT/haskell-platform/bin:\$PATH \ >> ~/.bashrc $ . ~/.bashrc $ sed -i '/user-install/ s/.*/user-install: False/g' \ ~/.cabal/config

Installing Fay

Finally, it's time to actually install Fay.

$ cabal update $ cabal install fay

The first invocation of cabal update tells me to run cabal install cabal-install, but I'm a bit paranoid because ghc-pkg list tells me that Cabal-1.16.0 is installed, but the new cabal-install wants to bring in Cabal-1.18.0. Let's not start screwing up the dependencies just yet, thank you. However, there was a failure installing pretty-show. Cabal didn't give me a useful message, but attempting to install pretty-show directly reveals that it needs a higher version of happy. Happy doesn't need to install any libraries, so I'm not as worried about installing it.

$ cabal install happy $ cabal install fay

This works, but tells me I also need to install fay-base. No problem.

$ cabal install fay-base

Stay tuned for another post later about skew ternary trees!

Obfuscated Life

f=lambda g,r,n,s:s if n==0 else'\n'.join([s,'='*50
,g(g,r,n-1,r(s))]);l=lambda q:'\n'.join([''.join([
'*'if x in(5,6,7) else' 'for x in a])for a in [map
(sum,zip(*b))for b in zip(*[[z[x:]+z[:x]for z in [
[(2-(1-abs(x))*(1-abs(y)))*w for w in r]for c in[[
[1 if s == '*' else 0 for s in p] for p in q.split
('\n')]]for r in c[y:]+c[:y]]] for x in(-1,0,1)for
y in(-1,0,1)])]]); iters=65 ;print(f(f,l,iters,"""
**************************************************
*                                                *
*         ***      ** **      ***    **          *
*         *  *    *  *  *    *       **          *
*         ***      *   *      **     **          *
*         *  *      * *         *                *
*         ***        *       ***     **          *
*                                                *
**************************************************
""".strip()))  # LIFE # 2013/3/7 # Stephen Hicks #

You can fill in any initial position you want (but make sure it is a rectangle (i.e. the same number of characters on every line) and that the first and last characters are not spaces (any non-asterisk will do to signify an empty cell)).

Solving the Rubik's Cube, Part 2: Exploration

Now that we have a better idea what we're dealing with, we can start rotating things to see what happens.

Fortunately, these cubes come solved. When working with a solved cube, it's much more obvious what is the effect of any transformation, since you can immediately tell (roughly) where each block came from. In order to take advantage of the solved state as long as possible, we start by only making small excursions of 4-8 operations.

Before we can talk about these operations, we need to define a language for describing operations and positions on the cube. We'll start by naming the six directions with their unique first letters: Front, Back, Up, Down, Left, and Right. Each block can be described by three coordinates, using capitalization as follows: we write 'F' for front-most, 'f' for front-middle, 'b' for back-middle, and 'B' for backmost; and likewise for the other two axes. Thus, the front-top-left corner cube will be called 'FUL', the edge cube directly beneath it is 'FuL', and the face cube to the right of it is 'Ful'. Continuing diagonally right and down the same face we have 'Fdr' and finally the opposite corner 'FDR'. We always use the same order F/f/b/B, followed by U/u/d/D, followed by L/l/r/R, so that each block has a single unique name. Note that corner blocks are all caps, edge blocks are two caps and a lowercase, and face blocks are two lowercase and one capital. A block with all three lowercase is impossible as it would be on the inside of the cube.

We now name the elementary rotations by the direction of rotation, subscripted by which layer is turned. Thus, turning the top-most layer to the right is R_U. Turning the next lower layer to the left is L_u. Turning the right-most layer down is D_R and turning the middle-left layer up is U_l. To name the final axis, we use the right-hand-rule: a counter-clockwise rotation of the front layer is F_F since this is a right-hand rotation through the F-axis. A clockwise rotation of the middle-front layer is B_f. We could name the other four rotations by their axis, but I find the consistency to not be worth the increased confusion.

Now that we have names, what sort of explorations can we do? Our goal now is to build up a catalog of simple (and hopefully easy-to-remember) operations that make small changes to the cube that are easy to understand and reason about. For instance, a single rotation D_r affects 12 on four separate faces, which is a bit unwieldy. If we follow it up with R_d we've now affected 22 blocks, touching all the faces: even worse. But if we continue with U_r and then L_d, we arrive mostly back to where we started, but with six face blocks cycled a bit. If we repeat this series of four rotations three more times, we arrive back at a completely-solved cube. Another example is D_rR_DU_rL_D. [Note that I write compositions from left to right, which is unconventional from a mathematical point of view—i.e. if you wrote these as functions f and g operating on a state s then one might expect (fg)(s) to mean f(g(s)); but I find this more difficult to read and this leads to more errors in executing operations on an actual cube.] This operation also affects six blocks, but must be repeated more times to return to the initial state.

We've seen 6×4=24 named operations, to which we can add 6 more full-cube rotations: O_F, O_B, O_U, O_D, O_L, and O_R, again using the right-hand rule to determine rotation direction. Note that these are effectively just relabelings: O_FU_rO_B is equivalent to just L_d. In this way, one might consider them a sort of orthogonal (or unitary, for the physicists) transformation.

This is a small sampling of short excursions. In the next installment, we'll look at many more, and discuss some heuristics of how we come up with possible operations and how to represent their effects using cycle notation.

Solving the Rubik's Cube, Part 1: Introduction

I was given a 4x4x4 and 5x5x5 Rubik’s cube as a bachelor gift (“should be easier to figure out than your wife”) and recently began working on the smaller one. I was taught the algorithm for solving the original 3x3x3 cube as a teenager, and somewhat regret not having the chance to solve it completely myself.  Since then I have solved a few other puzzle cubes. As it turns out, there are a number of phases of solving Rubik-style puzzles, and the techniques are actually quite generalizable and are very mathematical. I thought it might be interesting to document the solution process in a blog series, from the point of view of one who has never solved this cube before, and on the way we'll explore the various concepts that arise.  I will not be providing a thorough solution, and will try to warn about specific spoilers, in case anyone wants to solve it themselves.

To get started, we’ll first look at the anatomy of a cube. As everyone should remember from geometry, all polyhedra have vertices, edges, and faces. In a standard Rubik’s cube, this gives us three distinct types of blocks: corner blocks, edge blocks, and face blocks. Note that this is not the only possible mapping: the Skewb (pictured left) has only two types of blocks—corner and face—due to its diagonal cuts. The importance of recognizing the component blocks is that no operation will ever exchange (for example) a corner block with an edge block, or any other mismatch. Even more importantly, it is critical to see the cube as an arrangement of blocks, and not just stickers. Every operation moves and reorients whole blocks: stickers do not move independently.

In the 4x4x4 cube, we have four face blocks on each of six faces, giving us 24 face blocks with four-fold degeneracy (degeneracy simply means that we can’t tell the difference if the “degenerate” blocks are exchanged: the cube is still solved if these are “out of place” from where they started). We have two blocks on each of 12 edges, giving us 24 edge blocks with two-fold degeneracy and two different possible orientations (conversely, the cube is not solved if a block is in the correct location but the wrong orientation). Finally, there are eight unique corner blocks, each of which has three different orientations. Thus the total number of distinguishable configurations is ostensibly

(24!/(4!)⁶)×(24!/(2!)¹²×2²⁴)×(8!×3⁸)/48 ≈ 4.5×10⁴⁹,

although a large number of these are impossible to actually achieve without disassembling and reassembling the cube. So the puzzle space is actually several orders of magnitude smaller.

In the next installment we'll look at some initial explorations of cube operations, and define some notation for referring to the different blocks and rotations.

Version controlling my home directory

I recently rearranged my home directories on my work machines and decided it was time to finally get my configuration under a proper version control. I found several blogs about this, but one was particularly useful. I've changed it a little, but here's the basic set up.

$ mkdir ~/.config.git
$ cd ~/.config.git
$ git init --bare
$ git config core.worktree ../

Now I have a git repository called ~/.config.git, but it needs special environment variables set so that accidentally calling git outside a normal repository won't trigger it to do things to my config repo. The next step is to make it easier to use this repo. I wrote the following to ~/bin/git-home:

#!/bin/bash
export GIT_DIR=$HOME/.config.git
export GIT_WORK_TREE=$HOME
git "$@"

Now calling "git home ..." explicitly sets the repository to my config repo. But this still isn't so convenient. So I added the following to my (now version-controlled) .bashrc file, at a point after completions are loaded:

alias hgit='git home'
complete -o bashdefault -o default -o nospace -F _git hgit 2>/dev/null \
        || complete -o default -o nospace -F _git hgit

This sets up hgit with completions. Finally, I don't want hgit status to show tons of untracked files. So I added the following ~/.config.git/info/exclude:

[^.]*
!.*/*
*~

Beneath that is a list of specific exclusions, which I'll keep expanding as I discover files and directories I don't want to track.

Happy Pi Day 2011!

                              \let~\catcode~`z0
                        ~`'01~`,02~`406~`@11~`=13zdef
                    =41'~`4113zgdef,=$$41'~`4113zcountdef
                 ,=++41'~`4113zlet,=AA'B!d6l;8p/Pa5Nr.eq3Ei[
              DSm@|H9c]o1M?TgJk-CF2*tnIj7Rf,=""'2d-NDDRIeMj|Nir
            -n-;.g./pjkCm1Bg;J7R3Ie!kmEae9djCEe6t8Dt@lpdCcM?or8m8
          rat]F3i.1m;[5M*agFiotMTml7a/Rd/pMe/|lB5-jca*iCIc!??9n.g!/
        mq2etc8MfSj8rmko-SSStB21plt?et5tNNT?BliPqi51Je8l|[-p.n.9/Tp[H
       a9[gkcTk[d/!ie5]F!iT[ri|kPDPHdaNrBp[Tp!.ra1j;.i8fd851i?BoS5||2m
      iE.F|Mq*.EcPq*-rB812?[C|MnCHnke|D13o|l3Rt/73p-[lf-/C3|kHan[Sqi!E2
     ltCiJEa*@]22dNng8RrpnoBk5DtH*9cH!rRdiEj|3tiBrPBBHEn8l|.e5593o3JPp;g
    i1pkS]Dp52SilElS-mt8l.2kgD]!ac]n-JPDReD@[JP?lNT6N-dEPNnNpIkNH/1@gNFCd
   e869SNnfCf9]*|6ni8BPeD7M519rq-;T3IPSt*6-F@@BP68D?-|/5DN?e5Hp3[BBHNk31|H
  9ge.maeERBqTc3tp@pNIpDtEqMeS.pe5FmHJ.-eDmpmC.8P;g1!1/[PDt/JDH1Bl]@1qmlPiJ
  N*PacC?1md;!!NE/k.S99I98gqpcn9c8NaEao[!1!kJfm99adfi1jp*/5Dea-R-1d8;I?|gPl
 ][ai-;8kgHlJ?cS3S-ic;ceE.EJn|nke2;Sa1!FIoadp1EBCig*[//9|55DJ.cqDB@6lERPP5-q
 cC.go-n3fE5;7-9faJf8Fo]gcEHa6.midi@f-/CHNHe/R7p|dqp|@do-q2qB3NEalCold3?*8B6
 D1jFq7-Ek@.icJ]l|F@-]n-HprI@pJNBCccN*;NR5lk.!5!M?M*ID;e@7ce/!Ef[ggt5jiHP/]N
 F-p1e[ESmS@g-kc;/p29[HE/MSnClCkMtn1ppHJ*g[f@Ilak6DeJM..o.;?P/19I-?!BE*]a!lq
 /an?5D7l9M]98d2M32|DJ2?5r|5Be|aa1J]|]Mn]TTqa?.k[ki2qrlfoHc@E;8R9Djime;J]M5S
 NiS;S[FPe91Ht-FR|aN..m6n99SeP7tT8qoRqecn97gHE/E!om?9]E9dPDTB*Pdt[dolk/kRj9o
 ]/RH9NfD8Rq2ra/2/N[H5J.aI3SkadJpfRDFT/mr]ECdPm|TTJDe1.;9.!mk-a.qCorTm*DfDp?
 Eqk2cI!JfNojFTPt@fSeCpaI!6C;TSd!|T?fFoNgJ@p|R8|aRHf16NPlrkiTnDgBdJ;Nn6D*ocn
  kC8?r2TgF?68PDF7aN*9.68|1gg31.B-k3-I;5]2kRplq..]j|Eq5JmeE7iSI;;fp/25|/-gE
  -Tdqf;D*S6RFg9@|n*mRJS?9orI/HNJiT|o!8,=[[',+]][$CC0C0$TT1T25+&&zadvance+*
   *zmultiply+//zdivide+##zifnum[[+))zfi+((zifx+||zelse[[+>>zexpandafter+;
    ;zxdef[[+::zgdef[[=z}}4142'>;zcsname41zendcsname'42,,[[=z{{41'zcsname
     41zendcsname,[[=!!41';]']41,,+z\\zthe[[=PP4142$'}41'\C,&C1:A'42,,=V
      V'>PA$(A]|>V),V=GG'TC/C10*C10&T-C/C10!'\T,,[=DD414243'>C{'43,*C50
       >T{'42,&CT*C50>T{'41,&CTGGGGGzfutureletAV,=YY41',:V'(A$>Y|>D),!
        3!.>D"$$RR2R38$YY3Y-R&Y1$XX5[[=SS4142$'41:]'42,,=OO'>S]$,[[=Q
          Q41'T41*T41&CT,=HH'C0QXQYC-CQR,=BB'#X<RH#C<0P|O)&X1>B),=L
            L'#Y<RX-Rzhbox'B,&Y2>L),=PP'zhskip0.5em,zvbox'zttL,[:
              Y41',;A'bYryYge,=::41i'>{>'A,,~`412:stephen.hicks
                 3.14159265358979323846264338327950288419716
                    9399375105820974944592307816406286208
                        99862803482534211706798214808
                              ..........kthxbai

For those who can't run TeX, the output is here

Manual dependency resolution

Sometimes the tools one has at one's disposal just aren't smart enough. I wanted to profile a Haskell program and found out that I needed to reinstall all my libraries with profiling support, and cabal-install just wasn't smart enough to do it very well. I would try compiling my program with profiling support and it would complain about library X. I would try reinstalling library X and it would complain about library Y, and so on, ad nauseum. I seem to recall having a similar problem bootstrapping cabal-install in the first place. Here are a few shell functions I wrote that should make this process not quite so painful:

push () { 
  STACK=("$1" "${STACK[@]}")
  pop
}
pop () {
  local TOP="${STACK[0]}";
  run "$TOP" && 
    unset STACK[0] &&
    STACK=("${STACK[@]}") &&
    if [ -n "${STACK[*]}" ]; then
      pop
    fi
}
run () {
  cabal install --reinstall -p "$1"
}

Obviously one would redefine "run" as appropriate. For instance, the initial cabal bootstrap might look like

run () {
  cd $1
  for cmd in configure build install; do
    runghc Setup.*hs $cmd
  done
}

and I would "push $PWD" after downloading and unzipping each package.

Happy Pi Day!

              \let~\catcode
          ~`z0~`'1~`,2~`q13~`z#
       14~`46zdefq41'~`4113zgdef,q
     QQ41'~`4113zlet,qBB415425'41-P#
    7427,QPPzexpandafterqAA414243'H#H
   42434341542415,qCC41742743'41i-D42#
  434343,qww',zedefw'PPPCPBAyap!,qEE',q
 6641'~`4113zcountdef,QNNzifnum6RR1R20E6
 YY2QAAzadvanceY-RAY1QMMzmultiply6XX3EqS
 S'Ezhskip0.5em,EQJJzjobnameEQmmwE6TT5qj
 j4142x'41zgdefm'42,,EQ!!zglobalE6CC7Eqr
 r41'T41MT41ACT,qHH'C0rXrYC-CrR,qOO'zifx
 mEPjwxEzelsePjmxzfi,qcc'NX<RHNC<0Szelse
  OEzfiAX1PczelseE!AY2zfi,EzedefzJ'J,qv
   v'@,zifxzJvQOO*zfiEqll'NY<RX-Rzhbox
    'c,Plzfi,zttl~`z612qii41h',~`zx0i
     3.14159265358979323846264338327
       950288419716939937510582097
          494459230781640628620
              899...kthxbye

There's even an Easter egg (try running with -jobname @).

For those who can't run TeX, the outputs are here and here.

Hostname mangling

Here's some bash code I wrote today for navigating my home network (the names have been changed to protect the innocent). I have three computers that live on my LAN, and I've instructed my router's DHCP server to assign each computer a fixed IP address. Thus, baley=192.168.1.10, gladia=192.168.1.11, and fastolfe=192.168.1.12. The goal is that I'd like to be able to access any of these computers from within the LAN, as well as from the outside (via a dyndns, sdh.yi.org).

First, I set up port forwarding on the router (essid solaria) to forward 2210 to baley, 2211 to gladia, and 2212 to fastolfe. I then added the respective ports to each host's /etc/ssh/sshd_config file (in addition to the regularly-scheduled port 22). Ideally I could simply add these names to my /etc/hosts file and be done with it, but because of the port issue, it's not quite that simple. Also, I have a different user name on fastolfe (steve) than I have on the others (sdh), and I'd rather not have to mess with that.

The solution I came up with is shell functions. I define ssh and scp to be functions, and parse the arguments to find any instances of these hostnames. I then do some work to figure out which LAN I'm on, so that I can short-circuit the router if possible. Without further ado, here's the functions:

WIRELESS=wlan0
function essid {
  iwconfig $WIRELESS |
    perl -ne 'print $1 if /ESSID:"([^"]*)"/' 2> /dev/null
}
function ssh {
  local args=()
  while [ -n "$*" ]; do
    case "$1" in
      baley)
        case "$(essid)" in
          solaria)
            args=("${args[@]}" sdh@192.168.0.10) ;;
          *)
            args=("${args[@]}" -p 2210 sdh.yi.org) ;;
        esac ;;
      gladia)
        case "$(essid)" in
           solaria)
             args=("${args[@]}" sdh@192.168.0.11) ;;
           *)
             args=("${args[@]}" -p 2211 sdh.yi.org) ;;
        esac ;;
      fastolfe)
        case "$(essid)" in
          solaria)
            args=("${args[@]}" steve@192.168.0.12) ;;
          *)
            args=("${args[@]}" -p 2212 sdh.yi.org) ;;
        esac ;;
      *) args=("${args[@]}" "$1") ;;
    esac
    shift
  done
  command ssh "${args[@]}"
}
function scp {
  local args=()
  while [ -n "$*" ]; do
    local arg="$1"
    case "$arg" in
      baley:*)
        case "$(essid)" in
          solaria)
            arg="${arg/baley/sdh@192.168.0.10}" ;;
          *)
            arg="${arg/baley/sdh@sdh.yi.org}"
            args=('-P' '2210' "${args[@]}") ;;
        esac ;;
      gladia:*)
        case "$(essid)" in
          solaria)
            arg="${arg/gladia/sdh@192.168.0.11}" ;;
          *)
            arg="${arg/gladia/sdh@sdh.yi.org}"
            args=('-P' '2211' "${args[@]}") ;;
        esac ;;
      fastolfe:*)
        case "$(essid)" in
          solaria)
            arg="${arg/fastolfe/steve@192.168.0.12}" ;;
          *)
            arg="${arg/fastolfe/steve@sdh.yi.org}"
            args=('-P' '2212' "${args[@]}") ;;
        esac ;;
    esac
    args=("${args[@]}" "$arg")
    shift
  done
  command scp "${args[@]}"
}

Now I can throw this onto any shell account I use (with appropriate modifications to the WIRELESS variable) and source it in my .bashrc to access any of my computers as if it had its own public IP address.

Fibonacci in Go

I've been playing around with Go a bit. Here's what I think is the most Go-like solution to producing the Fibonacci sequence.

package main

import "fmt"

func dup3(in <-chan int) (<-chan int,<-chan int,<-chan int) {
  a,b,c := make(chan int,2),make(chan int,2),make(chan int,2);
  go func() { for { x := <-in; a <- x; b <- x; c <- x } }();
  return a,b,c
}

func fib() <-chan int {
  x := make(chan int,2);
  a,b,out := dup3(x);
  go func() { x<-0; x<-1; <-a; for { x<- <-a + <-b } }();
  return out
}

func main() {
  x := fib();
  for i:=0; i<10; i++ { fmt.Println(<-x) }
}

I like it because I only ever declare a single integer variable, and the rest goes through chans. This solution is inspired by Haskell's concise "fib = 0:zipWith (+) fib (1:fib)". Any comments are most welcome. In particular, if there were a way to accomplish it (in the same style) without the buffered chans, that would be pretty cool (though I'd be a bit surprised, since it doesn't seem possible at first glance).

Oscilloscope Pong

This was originally my final project for my undergraduate electronics lab. Now that I've finally defended my PhD, I've got some free time and am getting around to posting it. I'd been meaning to write up for a long time (about 7 years!). Of course, after writing it up in LaTeX, that still doesn't help with blogging, since TeX/EPS/PDF isn't such a great format for web viewing. Fortunately, before I hunkered down to write my thesis I somehow converted all these figures into PNG (I haven't the slightest idea how I did it anymore - anything I try lately looks terrible). You can download the PDF version here.

Introduction

The very first arcade game was Pong, created in the late 1970s. In its time, it was the height of digital technology. We return to this historic video game from a slightly different point of view. In the following pages we will construct an entirely analog version of Pong that can be played using a modern oscilloscope with an X-Y setting (which draws channel 1 on the X axis and channel 2 on the Y axis).

Circuits

Here we look at the circuit from the top-down, starting with the big picture fitting all the subcircuits together, and then analyzing each individual subcircuit.

Big picture

In Pong, there are three objects which must be drawn: the ball and the two paddles. We select the object to draw using a very fast triangle wave. At the extents, either paddle is drawn. In the middle, the ball is drawn. This is represented in the figure below. The lines CB, CP₁, and CP₂ serve as controls, allowing the corresponding signals (B_x,y, P₁, and P₂, respectively) to pass on to the scope only when the control is high. Thus, at any time, we need exactly one of CB, CP₁, or CP₂ to be high.



The main circuit consists of two parts. We need to have an output for the scope x position and the scope y position, respectively, shown in "Scope Output" below.

Analog Switch

The main workhorse of an analog Pong is the analog switch, denoted in the above schematics as a crossed circle, as shown in the figure. Using a series of analog switches, we can draw multiple objects on the oscilloscope at once. The analog switch we use here is constructed from an op-amp and an nJFET shown in the figure "Analog Switch" below. It allows the input signal to pass if and only if the control lead is above +5V. The input is sufficiently blocked when the control is grounded. More discussion of this circuit is given in the next section. We can add the output from several analog switches using an op-amp addition circuit.

Control Signal

The control signals CB, CP₁, and CP₂ are generated from a master control signal C. This master control signal, as explained above, is simply a fast triangle wave (I've forgotten the frequency), generated by the circuit shown in "Output Control" below. We then generate CP1 and CP2 by comparing C to 5V, such that CP₁ is high when C<-5V and CP₂ is high when C>+5V. We must be very careful to prevent any possible overlap in the control signals. Thus, we generate CB as CP1+CP2, as shown below.

Ball Position

We generate the ball position from a pair of slow (1/3 to 3Hz) triangle waves, shown in "Ball Position" below. These circuits each have a pair of potentiometers: R₁ and R₃ adjust the y- and x-amplitudes of the ball's motion and should be adjusted so that the ball's motion fills the oscilloscope screen, currently designed to be ±4V vertically and ±5V horizontally. R₂ and R₄ adjust the y- and x-speeds.

Paddles

The vertical paddle positions are given by the lines P₁ and P₂, which we construct with a voltage divider, shown below in "Paddles". The potentiometers R₈ and R₉ should be large and easy to adjust (i.e., a joystick) and are used to move the paddles up and down. R₆ and R₇ control the vertical range of the paddles' motion (i.e. from -3V to +3V). Whlie there's no theoretical problem with using them, small potentiometers are hard to find, so we insert an op-amp buffer to decrease the output impedance instead.

In order to make the paddle appear as more than a point, we add a fast (about 10kHz, so that the entire length of the paddle is drawn each time CP_i is high) triangle wave signal LEN, shown also in "Paddles", to the Y output whenever we're drawing the paddles (i.e. when CB-bar is high). The potentiometer P₅ controls the size of the paddles (around ±1V).

The horizontal positions are fixed at ±5V, that is, either edge of the screen.

Power Supply

We assume that the breadboard setup includes ±12V and ground, but we may need to generate our own ±5V lines, which can be done cleanly with a simple voltage divider fed through a 411 op-amp buffer (shown in PDF only).

Improvements

Hit detection and scoring

The circuit shown so far is more of an interactive movie than a game. The controls can alter the size and position of the paddles, but can't react differently if the ball is hit or missed. I attempted to add logic to deal with this case using a D-type flip flop as shown in "Hit Detection" below, where B'_x and B'_y are sent to the scope instead of B_x and B_y. As the design currently stands, it simply hides the ball until a reset button is pressed. The inputs D_i must change when B_y is within a paddle length of the P_i, and the clock signals CLK_i should go off only at the very tips of the master control signal C. Finally, the "g" and "r" diodes should be green and red LEDs to show who missed.



Unfortunately, this addition caused some impedance problems and smeared the whole picture terribly, and I was never able to fix it.

Dynamic ball speeds

One other modification that would be nice would be to allow the ball speeds (at least the vertical speed) to change based on how the paddles hit it. If there was some way to lock-in a "resistance" based on, say, B_y-P_i at a certain point, rather than using semi-fixed potentiometer, then it might not be so difficult. Likely we'd want another sort of flip flop, but I never looked very far into how that might be accomplished.

ICFP Contest 2009

It's been just about a year and I haven't posted anything... I've got a few drafts of posts, so maybe I'll try to get one or two of them done this summer. Anyway, this weekend was the ICFP contest. I don't have near as much to say about it as last year, mainly since I only spent about 16 hours working on it, starting Sunday afternoon, along with David Roundy and some help from our friend Joanna.

The problem

It was an interesting problem this year. Teams were required to implement a virtual machine to run "OrbitVM" binaries provided by the contest organizers. Then the interesting part was writing a controller to perform certain tasks in orbital dynamics (in 2d), ranging from doing a simple Hohmann transfer to change the radius of a circular orbit, to flying around to collect a number of satellites. The physics seems like it would be interesting to work out, but we didn't really get around to it. Just thinking about it, though, an orbit about a single body in 2d has four parameters: the semimajor axis (for simplicity, I'll assume it's an ellipse), the eccentricity, the orientation of the major axis, and the phase along the orbit. These can be calculated from the position and velocity (x, y, v_x, and v_y) of a satellite. On the controls side, there are only two "knobs" we can control: the impulses in the tangential and radial directions. So we can see that it can't be trivial to transfer from any orbit to any other, and in fact we could probably define some sort of metric to describe how distant two particular orbits are (minimizing a cost function composed of total impulse and time required). Of course, even with just elliptical orbits, this is well beyond the realm of tractability, but if it were implementable, it would lead to some sort of traveling salesman problem, except that the distances varied with time in incommensrate ways. What a mess... (not to mention the real problem also had a moon to make the orbits less than elliptical, and was integrated with a large enough time step to make the integration error somewhat important)

Our solution

That's enough abstraction. I enjoyed working on the contest, although we only solved the first sub-problem of performing a Hohmann transfer. With only one day, there really wasn't any chance to outdo last year's performance, but we decided to have some fun with it anyway. The original plan was to do it in postscript, so our team name was "Paper Jam in Tray 3". But it turned out that rolling our own IEEE doubles was just too tedious (postscript only supports singles natively), and the extra precision was important (at least, in the Verlet integrator David wrote). So instead we implemented all of our logic in the OrbitVM virtual machine. It wouldn't have been completely terrible to write straight assembler, but I felt it would be more fun to write a compiler, so we embedded an OrbitVM a compiler into Haskell. It was a pretty simple compiler, and would have benefited greatly from more developed control structures (the VM itself was rather lacking in control structures: every instruction was executed and every mutable value in memory was written to exactly once per time step; the only control structure was a conditional copy that could copy from one of two memory locations, depending on the result of a comparison). We did implement a static data type, Vector, that simplified dealing with 2d coordinates and velocities, but the part that was most frustrating to deal with was maintaining state from one time step to the next; with some more thought I believe it could have been improved quite a bit.

We also had to find some way to connect these programs together. A perl script provided good plumbing and also allowed us to intercept the communication and visualize the trajectories with ghostscript, as well as allowing us to inspect some of the internal quantities to see what was going wrong.

I spent a number of hours, after we finally got some points on the scoreboard, trying to get the second problem, but without a more sophisticated development system, it was difficult to try new ideas and we never quite managed to catch any moving satellites, although I was able to fly by them briefly (just the velocities were all wrong by the time the positions matched up). The basic strategy I used (at least for the case of both satellites in circular orbits) was to calculate the required "phase difference" for when to start the transfer such that I landed on the second orbit just as the target was passing by. This got me close, but not quite close enough, and I never figured out how to do the tiny tweaks of the orbit to close in. It might be fun to make a "real-time" orbit simulator to get some intuition for how to do this. There would be some orbiting circle and the goal would be to pilot a spacecraft into an orbit within the circle using a combination of radial and tangential burns. Though maybe once you're looking at it in the rotating frame it would just be a piece of cake. We never actually looked at the rotating frame, which was maybe our problem...

Download

In case you're curious, our source tree is available at http://pages.physics.cornell.edu/~shicks/darcs/icfp09/.

ICFP Contest 2008

(Browse or download the code at http://www.physics.cornell.edu/~shicks/icfp08)

So, I just finished sleeping off a "double all-nighter" for the ICFP Programming Contest. The task this year was to write a controller for a Mars rover. The program would connect to a server which would send it periodic telemetry updates and then it would send back instructions, either Accelerate, Brake, Left, or Right. I had tried to get a team together for this contest, but it was apparently a busy weekend and all my programmer friends had other plans.

After thinking about the problem (and my situation as a solo entry) for a few minutes, I decided it would be interesting to see if I could write it in TeX. Lately I've been writing a whole lot of TeX for Andy Ruina, as well as for a macro package (inlinedef) I recently submitted to CTAN, so the idea didn't seem too crazy ("When all you've got is a hammer...").

Initial Work

The first problem that arose immediately after I decided on TeX was that TeX has no network access. So I had to make a small concession in writing a small Perl wrapper to do the networking. In the end, this file would be under a hundred lines, so I considered it a necessary, but minimal, evil. On one or two occasions I thought about farming some computation out to the Perl wrapper (such as trig), but in the end decided to stay pure. I learned about the IO::Socket::INET library and used the IPC::Open2 package to open a socket and a two-way pipe to a TeX process. Then we just read the TeX output and wait for special commands. Occasionally we'll write "WANT" which is a signal to Perl that TeX is ready for the next packet of information. Or else "HERE: " which tells Perl to send the following signal back to the server. I coded this up and found that it was really all that was needed to connect TeX to the world. Next, we needed to interpret the data. The server sent plain text data in the form of

  I 600.0 600.0 30000 60.0 ... ;

with a different number of mostly-numerical arguments depending on which letter came first (this determined what kind of datum it was). Since TeX can already parse this sort of thing, I figured the best bet would be to just make these letters all 'active characters' inside TeX so that they acted like control sequences. This worked well because occasionally multiple commands arrived on the same line, and so we'd need to do something special to account for this otherwise, but now it was automatic. More often, however, TeX's requests for data were more frequent than the packets were arriving (this is a good thing), but TeX's request (\read) is blocking, so we just sent an empty line in this case.

Math

If I were writing this in a real language like C++ or Haskell, one of the first things I would do would be to find or write a convenient data type for 2d vectors, since they're all over the place here. But TeX doesn't even really support things as simple as floating-point multiplication or (even worse) division. So I started by kyping some fixed-point multiplication and division macros I remembered seeing on comp.text.tex a while back (posted in the mid-90's by Donald Arseneau). I also kyped Kevin Hamlen's sqrt macro from his CDLabels package that I'd remembered him boasting about. These simple tools in hand, I was able to start making some real progress. I defined a bunch of counters (integer variables) and lengths (fixed-point numbers) and some booleans to keep track of what time it was, where we were and wanted to go, and which way we wanted to turn (wow, alliteration). Then, each time we received telemetry updates, I would turn towards the target if we were off by more than 20 degrees, brake if we were off by more than 90, and accelerate otherwise.

Of course, to figure out how far off from the target we were, I needed an arctangent function, and this is definitely not provided by TeX. So I set about to write \atan (I would have called it \atan2, since that's really what it was, but names can't have numbers normally). Really about the only thing that was feasible to do here was a polynomial expansion. I opened up Octave and plotted tan(x) next to x+x^3/3 (naturally) from 0 to pi/4, and it didn't look that great. But it looked like I could probably do a better job by just tweaking the cubic coefficient by hand. In the end, I settled on atan(x)~x-.2x^2 (sure, I could have optimized it without much difficulty - in fact I just did and it turns out that -.17297x^2 works slightly better, though I would have done really better with the cubic term -.26219x^3, which I've now implemented, or even better, -.05x^2-.18796x^3 -- thanks SciPy). So I coded this up and it seemed to get the job done, anyway. I downloaded the sample server and maps and watched how it worked on the simplest map, with no craters to crash into and die. It didn't quite work, but a little tweaking of the numbers made a big difference and I was able to get home. I went to bed Saturday morning around 7am (EDT) and got 7 hours sleep before I had to wake up for sailing and then having some people over to my apartment, all of which kept me busy until about 10pm.

An inverse heisenbug

According to the jargon file, a heisenbug is one that disappears when you try to debug it. In this case, my code worked okay, but when I tried to see what it was doing by turning on visualization, it suddenly stopped working as well. It wasn't too difficult to figure out that the visualization was slowing down the server so that it didn't deliver all the telemetry data in a timely way. so I decided that I needed better timing. It turns out that even turning on tracing to the log file in TeX is enough to reduce the resolution beyond workability, and in my final code, in later runs when there's a long list of obstacles, that starts slowing it down too much too. TeX doesn't have any sort of timing functions (\time returns the time to the minute that the typesetting began but is in fact constant). So again comes Perl to the rescue. Presumably I could have measured something like distance travelled at a known speed and backed out an estimate for the amount of time spent between iterations, but this would of course changed depending on the situation, so again, I felt justified in resorting to Perl here. Now whenever TeX asked Perl for data, we included a timestamp in the response to keep our own clock. This gave a much better resolution and we could then estimate where we were and make decisions about 10x as often. By 2am Sunday, the rover could make it home consistently on the easy map with no dangers, but usually fell into craters on the more complicated ones, so this was the next thing to be addressed.

Collision avoidance

By far the most difficult (and frustrating) part of the contest was collision avoidance. I tried a number of things to make it smarter, but they all failed miserably. They typically did worse than before I tried to do anything. Generally, I tried the logic that at any time we've got a target we're shooting for, and if at any time there was a known obstacle between the current position and the target, we'd move the target to a place that wasn't hindered (now that I'm writing this, I see the error here much more clearly). Then we issue commands to steer us toward that new target. If ever the path home was unblocked, we'd try to go there instead.

It took a long time to get this code to behave as I wanted. Often I'd find the rover turning the wrong direction entirely, driving straight into craters, driving straight for the outside edge of the map, or once, hitting the same boulder repeatedly until time ran out. If I knew how to do it, it would be neat to stitch together all these bloopers and make a 2-3 minute youtube video of the bloopers and then see them gradually improve to the final result (yay for darcs that that's even possible). Most helpful in this process was Octave (a free MATlab clone) - at one point I coded up a debugging message that printed out Octave code to plot a graph with lines from the current position to the target, the new trajectory, and the obstacle in question. Often the new trajectory was worse than the original one and I could go step-by-step to figure out why that was happening. Eventually when all these little errors were debugged, I had a code that did exactly what I wanted it to do, but it still did no better than if I'd done nothing at all to avoid the obstacles. This was the way it went for most of Sunday (I took an hour nap before church, but otherwise spent the whole time working). People on the IRC channel were talking about A*-algorithms and such, but that was much too smart for me - I had a hard enough time just getting to where I wanted to go when there weren't obstacles - so I just kept plugging away.

Around dinner time, Geoff called and suggested I go to his house to watch a movie. I was trying out a new idea I had, much simpler than many of the others: implement a two-state machine. The rover is either in the running state, where it's turning towards home, or else it's in the swerving state, where it's avoiding an object. If the rover sees an object in the way, closer than a certain distance (determined by the time it would take to turn 90 degrees at max speed, but this foolishly ignored the unknown turning acceleration, which turned out to be pretty important, and could probably have been discovered without too much difficulty... if only I had a team), then it would start swerving away from the object. The key point here was that we were looking ahead of us, rather than looking always toward home. So surprisingly we stopped running into things! I eventually converged on the logic that it would keep turning until it was no longer obstructed, and then it would go into a tunnel-vision mode, heading straight forward until the object it was swerving past was directly perpendicular with its direction, so that we know it's passed before trying to turn back home. This revealed all sorts more bugs as my dot product apparently just didn't work, but eventually I got it all worked out so that by the time I went over to Geoff and Erin's, I had a working version to show them, swerving back and forth and reaching the goal about 80% of the time. Around this time I also called up David Roundy and told him what I was up to. He suggested a few things, including the team name I finally settled on (actually, I think this was his sister-in-law), The Lone TeXnician, and a bit about what I should do with my README file.

The icing on top

By early Monday morning, all I had left to do was clean it up, package it, and make sure it worked on the LiveCD environment that would be used in judging. The latter part was actually a bit difficult and I had been working on and off the whole time to figure out how to install TeX on the system with neither internet connection (apt-get would have been too easy...) or sending in a 50MB tarball with all of the basic TeXLive ditribution in it. I eventually figured out how to get a 2MB portion of the distribution to work by copying files from my /usr/bin/ and /usr/share/texmf/ and running `texhash` over and over again. I spent most of the rest of my time on an extra feature I really wanted. I would use LaTeX's picture environment to draw a map of the planet and trace the path that the rover followed. It took a while to get this working - I started out trying to make a single picture per trial and had grouping issues. I switched to using a separate (but overlapping) picture for each thing I wanted to draw, but they didn't line up properly. I tried saving all the drawing commands to a token list so that I could draw the whole thing at once at the end of the trial, but token list operations are O(n) in the length, so I started lagging way behind and couldn't keep up with the server (it was real-time, remember). Ultimately, I tracked down all but a small issue which caused misalignment only later in the process. This was eventually fixed when I found the errors, both in the swerving code (as I should have realized when they started so late and the trajectory up until them was straight, but then it curved - if I had painted the two modes in different colors like I originally wanted to, it would have been even more blatantly obvious!). Both errors came from putting decimal numbers where an integer was expected (stupid non-typed languages...) resulting in the fractional part being typeset instead of used mathematically, and pushing the reference point away from where it belonged.

Conclusion

I ended up submitting code that I was very proud of. It ignored the ravenous martians entirely, and had a hard time in some tight situations (and some not-so-tight), but in general it made its way home about as well as (or better than) you might expect for 1200 lines of TeX. I ended up getting 8 hours of sleep over the course of three nights, and promptly crashed for 17 hours.

You can browse or download the code if you like. I've cleaned it up a little bit since submission, in particular using better trig approximations I worked out while writing this. If you want to run it, you'll probably need a *nix system. You'll also need to download the simulation server and maps (remember to use '-v' to get a visualization window). Pass the '-l' option to `texsocket` to run in LaTeX and get the PDF output. Unfortunately I don't deal with disconnecting servers very well in the version I submitted, so it doesn't actually produce the PDF (more than) half the time and never gives any hint as to why.

Edit: pictures and pdf documents

Edit 2: Shortly after the contest ended, I learned of pdftex's built-in timers, which one of the commenters noted. I also learned about /dev/tcp (although the contest LiveCD didn't have it compiled into bash anyway). With all that working together, I could presumably have written a completely TeX solution (although blocking vs. non-blocking network access would certainly be an issue... maybe if TeX forked an extra process of itself...). Also, since it's now public knowledge, I did indeed win the judges prize.

I've turned off comments because of spam. If you want to say something, feel free to email me.

PostScript libraries

I've been writing some PostScript lately, such as matrix multiplication routines: things that really belong in a library. So I spent a good chunk of time today writing some software for preparing postscript files to be libraries. I wrote a Perl script `curdle` which takes a PostScript file as input and compresses it to a binary encoding with no comments and minimal spaces. At some point I'll add a script which will rename long internal variable names (as directed by comments). Once the file is compacted, it can be run through encode85 (which I found on some random FTP site) and put into a resource file a big block of gibberish, which is then either included automatically by the PostScript viewer, or else pasted at the top of the PostScript file which includes it. In any case, it should help significantly with PostScript library version control. Especially when I automate the resource part and include a "built on" date in the header.

If you're interested you can get the most up-to-date version of it with darcs (or just browse to this directory):

darcs get http://www.physics.cornell.edu/~shicks/darcs/pslib/

Blogger pain

I get frustrated when Blogger wants to "Save as Draft" whenever I hit Ctrl+D. I usually expect this keystroke to ask as delete. So I hit it often, and get annoyed when it loads a new page. So I fixed it. Here's another Greasemonkey script.

Firefox + Google Scholar + Cornell Library

So, I was sick of having to go through the CU Library homepage for every journal article I wanted to download at home. And so I wrote a quick and dirty plugin to add a link to each Google Scholar result to access it through the CU Library proxy automatically, this saving gobs of time (maybe someday as much time as I spent writing it in the first place!).

One (small) issue with this is that it only works if you're logged into CUWebLogin, but checking for that each time is very slow. So I actually make two links - the "login" link goes through the official channels while the other link attempts to bypass them and go directly to the article, so it should be quicker if you're already logged in. It probably wouldn't be too tough to edit it to work for a different school with a little investigation.

To use the plugin, you need to have GreaseMonkey, which is a pretty standard Firefox plugin allowing you to use any of a multitude of "user scripts" which are basically scripts people write to post-process webpages.

I also wrote a standalone plugin to add a button to the (right-click) context menu to access a page through the library, in case it came from somewhere other than Google Scholar. This one is only the slow access method, although it could be configured to access it quicker with enough demand.

At some point, I may integrate all this into a standalone plugin. And I may look into adding a configuration tool so that other university libraries will be usable (although I'd need help from others for this to work). For now, if you're at a different school and would like to try using this, talk to me and I'll see if I can hack together a version for you.

Installation

1. Install Greasemonkey if you haven't already.
2. Install the userscript for Google Scholar links.
3. Install the browser plugin for the context menu:
   • firefox
   • chrome

EDIT(2010 Nov 23): Added Chrome extension.

Obfuscated TeX

I just came accross the following TeX program:

\let~\catcode~`76~`A13~`F1~`j00~`P2jdefA71F~`7113jdefPALLF
PA''FwPA;;FPAZZFLaLPA//71F71iPAHHFLPAzzFenPASSFthP;A$$FevP
A@@FfPARR717273F737271P;ADDFRgniPAWW71FPATTFvePA**FstRsamP
AGGFRruoPAqq71.72.F717271PAYY7172F727171PA??Fi*LmPA&&71jfi
Fjfi71PAVVFjbigskipRPWGAUU71727374 75,76Fjpar71727375Djifx
:76jelse&U76jfiPLAKK7172F71l7271PAXX71FVLnOSeL71SLRyadR@oL
RrhC?yLRurtKFeLPFovPgaTLtReRomL;PABB71 72,73:Fjif.73.jelse
B73:jfiXF71PU71 72,73:PWs;AMM71F71diPAJJFRdriPAQQFRsreLPAI
I71Fo71dPA!!FRgiePBt'el@ lTLqdrYmu.Q.,Ke;vz vzLqpip.Q.,tz;
;Lql.IrsZ.eap,qn.i. i.eLlMaesLdRcna,;!;h htLqm.MRasZ.ilk,%
s$;z zLqs'.ansZ.Ymi,/sx ;LYegseZRyal,@i;@ TLRlogdLrDsW,@;G
LcYlaDLbJsW,SWXJW ree @rzchLhzsW,;WERcesInW qt.'oL.Rtrul;e
doTsW,Wk;Rri@stW aHAHHFndZPqpa.rtMRrgeLinZ.irLtYer.W,:jbye

You'd never guess by looking at it that it prints the entire song of the 12 Days of Christmas. Amazing.