tag:blogger.com,1999:blog-29532338891710325982024-02-06T20:51:55.345-08:00for(;;);A programming blog for the strange and esoteric (and sometimes mundane, too).Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-2953233889171032598.post-34014811055507496462015-06-26T00:30:00.000-07:002015-06-26T00:31:15.239-07:00Failover Trigger: Strictly ordered concurrencyI'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.<br />
<br />
<div style="white-space:pre;border:1px solid black;padding:4px;margin:4px 0"><code
>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());
}
</code></div>
This now allows any number of <code>addInput</code>s to be run concurrently, but ensures that everything in <code>runTask</code> (up to the <code>failover.set</code> call, at least) is fully synchronized. Inputs are handled on a first-come-first-served basis. If <code>noMoreInputs</code> is called after all inputs are added, then exactly one of <code>inputSucceeded</code> or <code>noInputSucceeded</code> will run to perform whatever cleanup is necessary.<br />
<br />
I call this the "failover trigger" pattern because it provides each task with a trigger it can use to optionally start the next task.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com1tag:blogger.com,1999:blog-2953233889171032598.post-52984650746366994042014-03-11T21:12:00.001-07:002014-03-11T21:15:57.292-07:00git ir: an alternative to git rebase --interactiveMy 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.
<br/><br/>
Unfortunately, <code>git rebase</code> just doesn't cut it for this. A while back I wrote <code><a href="https://github.com/shicks/config/blob/master/bin/git-rebase-tree">git rebase-tree</a></code> 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 <code>git status</code> and resolve the conflict, etc (or more typically, run <code><a href="https://github.com/shicks/config/blob/master/bin/git-conflicts">git conflicts</a></code> in emacs).
I had been meaning to redo <code>git rebase-tree</code> with its own <code>--continue</code> flag, but my experience with another custom function (<code>git diff-mail</code>, 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 <code>git rebase --continue; diff-mail --continue</code>, plus <code>--abort</code> 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 <code>git rebase</code> already has a queue, and with some clever manipulation, I can make it do what I want.
<br /><br/>
<span style="font-size:108%; font-weight: bold;">Enter <code><a href="https://github.com/shicks/config/blob/master/bin/git-ir">git ir</a></code>.</span>
<br/><br/>
This function takes a list of branches, a commit to rebase them onto, and optionally a commit to rebase them <i>from</i> (in case they're already on top of the destination). It sets up an interactive rebase session but completely ignores the plan <code>git</code> prepares, instead using its own plan that includes a few additional commands in the rebase plan.
<pre>
# 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
</pre>
The initial plan is effectively equivalent to <code>git rebase-tree</code> (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.
<br/><br/>
Once the initial plan is complete, it's ordinary <code>git rebase</code> the rest of the way, so when conflicts arise, it's back to the normal <code>git rebase --continue</code> (or <code>--skip</code> or <code>--abort</code>) workflow to handle them! Aborting happens for free. Moreover, no branches are moved until <b>all</b> 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 <code>::</code> (which I alias to <code>'EDITOR=: '</code>).Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com4tag:blogger.com,1999:blog-2953233889171032598.post-38448431223754160552013-12-14T15:31:00.000-08:002013-12-14T15:31:30.776-08:00Installing the Haskell PlatformIt all started with the <a href="http://www-cs-faculty.stanford.edu/~knuth/musings.html">2013 Christmas Tree Lecture</a>. 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 <a href="http://www-cs-faculty.stanford.edu/~knuth/programs.html#skew-ternary"><code>SKEW-TERNARY-CALC</code></a> 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 <a href="https://github.com/faylang">Fay</a> monad and decided to give a try (see <future post>, hopefully). So as a first step, I tried to <code>cabal install fay</code>, only to find that I had a <a href="http://www.vex.net/~trebla/haskell/sicp.xhtml#pigeon">Dependency Mess</a>™. Fine, I could use a fresh Haskell install. Unfortunately my laptop is currently stuck on Ubuntu 12.04, which is stuck at <code>ghc-7.4</code>. So I purged all my GHC and cabal data, temporarily installed a <code>ghc-7.4</code> 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, <code>~/local/opt/ghc-7.6.3</code> and <code>~/local/opt/haskell-platform-2013.2.0.0</code>, so that I can then add <code>--global</code> as a default <code>cabal-install</code> option and operate out of a single package db.
<div style="white-space:pre;border:1px solid black;padding:4px;margin:4px 0"><code
>$ cd ~/Downloads/ghc-7.6.3
$ sudo aptitude install ghc
$ OPT=$HOME/local/opt
$ ./configure --prefix=$OPT/ghc-7.6.3
$ make && make install
</code></div>
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:
<div style="white-space:pre;border:1px solid black;padding:4px;margin:4px 0"><code
>$ 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
</code></div>
<h2>Now the fun starts</h2>
Unfortunately, <code>make</code> failed. It turns out that <code>scripts/build.sh</code> sets <code>GHC_PACKAGE_PATH</code> in its <code>build_pkg</code> function when it builds with Cabal, and Cabal is incompatible with this option. Fine, we can fix that:
<div style="white-space:pre;border:1px solid black;padding:4px;margin:4px 0"><code
>$ sed -i '/GHC_PACKAGE_PATH=/ s/^/#/' scripts/build.sh
$ make && make install
</code></div>
Not surprisingly, this also fails, a little later in the process. This time, <code>alex</code> is failing to build without <code>happy</code>. But <code>happy</code> 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 <a href="http://trac.haskell.org/haskell-platform/ticket/217">bug</a> 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 <code>happy</code> also needs <code>happy</code> to build. Great, so there's no way around bootstrapping with a binary distribution. I found out right afterwards that <code>alex</code> has the same bootstrapping problem.
<div style="white-space:pre;border:1px solid black;padding:4px;margin:4px 0"><code
>$ sudo aptitude install happy alex
$ make && make install
$ sudo aptitude purge happy alex
</code></div>
Now it looks like we're good to go. Cleaning things up a bit,
<div style="white-space:pre;border:1px solid black;padding:4px;margin:4px 0"><code
>$ 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
</code></div>
<h2>Installing Fay</h2>
Finally, it's time to actually install Fay.
<div style="white-space:pre;border:1px solid black;padding:4px;margin:4px 0"><code
>$ cabal update
$ cabal install fay
</code></div>
The first invocation of <code>cabal update</code> tells me to run <code>cabal install cabal-install</code>, but I'm a bit paranoid because <code>ghc-pkg list</code> tells me that <code>Cabal-1.16.0</code> is installed, but the new <code>cabal-install</code> wants to bring in <code>Cabal-1.18.0</code>. Let's not start screwing up the dependencies just yet, thank you. However, there was a failure installing <code>pretty-show</code>. Cabal didn't give me a useful message, but attempting to install <code>pretty-show</code> directly reveals that it needs a higher version of <code>happy</code>. Happy doesn't need to install any libraries, so I'm not as worried about installing it.
<div style="white-space:pre;border:1px solid black;padding:4px;margin:4px 0"><code
>$ cabal install happy
$ cabal install fay
</code></div>
This works, but tells me I also need to install <code>fay-base</code>. No problem.
<div style="white-space:pre;border:1px solid black;padding:4px;margin:4px 0"><code
>$ cabal install fay-base
</code></div>
Stay tuned for another post later about skew ternary trees!Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com0tag:blogger.com,1999:blog-2953233889171032598.post-43637571377739594452013-03-07T00:00:00.000-08:002013-03-07T09:38:45.759-08:00Obfuscated Life<pre>
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 #
</pre>
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)).Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com0tag:blogger.com,1999:blog-2953233889171032598.post-54010302445075197622012-09-25T11:53:00.000-07:002012-09-25T15:36:48.241-07:00Solving the Rubik's Cube, Part 2: Exploration<div style="text-align: justify;">
Now that we have a better idea what we're dealing with, we can start rotating things to see what happens.
<br />
<br />
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.
<br />
<br />
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: <b>F</b>ront, <b>B</b>ack, <b>U</b>p, <b>D</b>own, <b>L</b>eft, and <b>R</b>ight. 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.
<br />
<br />
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<sub>U</sub>. Turning the next lower layer to the left is L<sub>u</sub>. Turning the right-most layer down is D<sub>R</sub> and turning the middle-left layer up is U<sub>l</sub>. To name the final axis, we use the <a href="http://en.wikipedia.org/wiki/Right_hand_rule">right-hand-rule</a>: a counter-clockwise rotation of the front layer is F<sub>F</sub> since this is a right-hand rotation through the F-axis. A clockwise rotation of the middle-front layer is B<sub>f</sub>. We could name the other four rotations by their axis, but I find the consistency to not be worth the increased confusion.
<br />
<br />
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<sub>r</sub> affects 12 on four separate faces, which is a bit unwieldy. If we follow it up with R<sub>d</sub> we've now affected 22 blocks, touching all the faces: even worse. But if we continue with U<sub>r</sub> and then L<sub>d</sub>, 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<sub>r</sub>R<sub>D</sub>U<sub>r</sub>L<sub>D</sub>. [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.
<br />
<br />
We've seen 6×4=24 named operations, to which we can add 6 more full-cube rotations: O<sub>F</sub>, O<sub>B</sub>, O<sub>U</sub>, O<sub>D</sub>, O<sub>L</sub>, and O<sub>R</sub>, again using the right-hand rule to determine rotation direction. Note that these are effectively just relabelings: O<sub>F</sub>U<sub>r</sub>O<sub>B</sub> is equivalent to just L<sub>d</sub>. In this way, one might consider them a sort of <a href="http://en.wikipedia.org/wiki/Orthogonal_transformation">orthogonal</a> (or <a href="http://en.wikipedia.org/wiki/Unitary_transformation">unitary</a>, for the physicists) transformation.
<br/>
<br/>
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.
</div>Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com2tag:blogger.com,1999:blog-2953233889171032598.post-40316336156202522712012-09-24T01:21:00.000-07:002012-09-24T01:40:27.997-07:00Solving the Rubik's Cube, Part 1: Introduction<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgSHilrKagjTI6YDtemCtwv3ft8alwM9X5qDChC4ExeGMqRp8KAMnnNibz3buER2L26pLzXORojrt1f16_xEC4pE0WPhK2h9lqYkJjVkkKIYO_fbMIf71Lct_GI-98DaU9xhgfHl7OW-gY/s1600/000499.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="120" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgSHilrKagjTI6YDtemCtwv3ft8alwM9X5qDChC4ExeGMqRp8KAMnnNibz3buER2L26pLzXORojrt1f16_xEC4pE0WPhK2h9lqYkJjVkkKIYO_fbMIf71Lct_GI-98DaU9xhgfHl7OW-gY/s320/000499.jpg" width="120" /></a></div>
<div style="text-align: justify;">
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.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjPHo9yKZBQw-SPQFl1ifrAv5q2FNauQpm8g24x2ci-G2-V5T2VSsyfpHsvSYOh2UApdGmoGbnPFU8LufVSJ_kesM4-38RIPHF5h7qArq6P44LmYncDxHtAMp4cafGU_41pRl-sgVkpJPw/s1600/skewb.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="120" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjPHo9yKZBQw-SPQFl1ifrAv5q2FNauQpm8g24x2ci-G2-V5T2VSsyfpHsvSYOh2UApdGmoGbnPFU8LufVSJ_kesM4-38RIPHF5h7qArq6P44LmYncDxHtAMp4cafGU_41pRl-sgVkpJPw/s200/skewb.jpg" width="115" /></a></div>
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 <i>blocks</i>, and not just <i>stickers</i>. Every operation moves and reorients whole blocks: stickers do not move independently.
<br />
<br />
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 <i>not</i> 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
<br />
<div style="text-align: center;">
(24!/(4!)<sup>6</sup>)×(24!/(2!)<sup>12</sup>×2<sup>24</sup>)×(8!×3<sup>8</sup>)/48 ≈ 4.5×10<sup>49</sup>,</div>
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.
<br />
<br />
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.</div>
Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com0tag:blogger.com,1999:blog-2953233889171032598.post-15102812166865017632011-03-15T14:55:00.001-07:002011-03-15T15:48:48.836-07:00Version controlling my home directoryI 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 <a href='http://tensixtyone.com/perma/the-version-controlled-home-directory'>one</a> was particularly useful. I've changed it a little, but here's the basic set up.<!--<br /><br />--><pre>$ mkdir ~/.config.git<br />$ cd ~/.config.git<br />$ git init --bare<br />$ git config core.worktree ../<br /></pre><!--<br /><br />-->Now I have a git repository called <code>~/.config.git</code>, but it needs special environment variables set so that accidentally calling <code>git</code> 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 <code>~/bin/git-home</code>:<!--<br /><br />--><pre>#!/bin/bash<br />export GIT_DIR=$HOME/.config.git<br />export GIT_WORK_TREE=$HOME<br />git "$@"<br /></pre><!--<br /><br />-->Now calling "<code>git home ...</code>" 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) <code>.bashrc</code> file, at a point <i>after</i> completions are loaded:<!--<br /><br />--><pre>alias hgit='git home'<br />complete -o bashdefault -o default -o nospace -F _git hgit 2>/dev/null \<br /> || complete -o default -o nospace -F _git hgit<br /></pre><!--<br /><br />-->This sets up <code>hgit</code> with completions. Finally, I don't want <code>hgit status</code> to show tons of untracked files. So I added the following <code>~/.config.git/info/exclude</code>:<!--<br /><br />--><pre>[^.]*<br />!.*/*<br />*~<br /></pre><!--<br /><br />-->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.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com0tag:blogger.com,1999:blog-2953233889171032598.post-11492354472598026412011-03-14T12:14:00.001-07:002011-03-14T12:21:36.643-07:00Happy Pi Day 2011!<pre style='font-size:80%'><br /> \let~\catcode~`z0<br /> ~`'01~`,02~`406~`@11~`=13zdef<br /> =41'~`4113zgdef,=$$41'~`4113zcountdef<br /> ,=++41'~`4113zlet,=AA'B!d6l;8p/Pa5Nr.eq3Ei[<br /> DSm@|H9c]o1M?TgJk-CF2*tnIj7Rf,=""'2d-NDDRIeMj|Nir<br /> -n-;.g./pjkCm1Bg;J7R3Ie!kmEae9djCEe6t8Dt@lpdCcM?or8m8<br /> rat]F3i.1m;[5M*agFiotMTml7a/Rd/pMe/|lB5-jca*iCIc!??9n.g!/<br /> mq2etc8MfSj8rmko-SSStB21plt?et5tNNT?BliPqi51Je8l|[-p.n.9/Tp[H<br /> a9[gkcTk[d/!ie5]F!iT[ri|kPDPHdaNrBp[Tp!.ra1j;.i8fd851i?BoS5||2m<br /> iE.F|Mq*.EcPq*-rB812?[C|MnCHnke|D13o|l3Rt/73p-[lf-/C3|kHan[Sqi!E2<br /> ltCiJEa*@]22dNng8RrpnoBk5DtH*9cH!rRdiEj|3tiBrPBBHEn8l|.e5593o3JPp;g<br /> i1pkS]Dp52SilElS-mt8l.2kgD]!ac]n-JPDReD@[JP?lNT6N-dEPNnNpIkNH/1@gNFCd<br /> e869SNnfCf9]*|6ni8BPeD7M519rq-;T3IPSt*6-F@@BP68D?-|/5DN?e5Hp3[BBHNk31|H<br /> 9ge.maeERBqTc3tp@pNIpDtEqMeS.pe5FmHJ.-eDmpmC.8P;g1!1/[PDt/JDH1Bl]@1qmlPiJ<br /> N*PacC?1md;!!NE/k.S99I98gqpcn9c8NaEao[!1!kJfm99adfi1jp*/5Dea-R-1d8;I?|gPl<br /> ][ai-;8kgHlJ?cS3S-ic;ceE.EJn|nke2;Sa1!FIoadp1EBCig*[//9|55DJ.cqDB@6lERPP5-q<br /> cC.go-n3fE5;7-9faJf8Fo]gcEHa6.midi@f-/CHNHe/R7p|dqp|@do-q2qB3NEalCold3?*8B6<br /> D1jFq7-Ek@.icJ]l|F@-]n-HprI@pJNBCccN*;NR5lk.!5!M?M*ID;e@7ce/!Ef[ggt5jiHP/]N<br /> F-p1e[ESmS@g-kc;/p29[HE/MSnClCkMtn1ppHJ*g[f@Ilak6DeJM..o.;?P/19I-?!BE*]a!lq<br /> /an?5D7l9M]98d2M32|DJ2?5r|5Be|aa1J]|]Mn]TTqa?.k[ki2qrlfoHc@E;8R9Djime;J]M5S<br /> NiS;S[FPe91Ht-FR|aN..m6n99SeP7tT8qoRqecn97gHE/E!om?9]E9dPDTB*Pdt[dolk/kRj9o<br /> ]/RH9NfD8Rq2ra/2/N[H5J.aI3SkadJpfRDFT/mr]ECdPm|TTJDe1.;9.!mk-a.qCorTm*DfDp?<br /> Eqk2cI!JfNojFTPt@fSeCpaI!6C;TSd!|T?fFoNgJ@p|R8|aRHf16NPlrkiTnDgBdJ;Nn6D*ocn<br /> kC8?r2TgF?68PDF7aN*9.68|1gg31.B-k3-I;5]2kRplq..]j|Eq5JmeE7iSI;;fp/25|/-gE<br /> -Tdqf;D*S6RFg9@|n*mRJS?9orI/HNJiT|o!8,=[[',+]][$CC0C0$TT1T25+&&zadvance+*<br /> *zmultiply+//zdivide+##zifnum[[+))zfi+((zifx+||zelse[[+>>zexpandafter+;<br /> ;zxdef[[+::zgdef[[=z}}4142'>;zcsname41zendcsname'42,,[[=z{{41'zcsname<br /> 41zendcsname,[[=!!41';]']41,,+z\\zthe[[=PP4142$'}41'\C,&C1:A'42,,=V<br /> V'>PA$(A]|>V),V=GG'TC/C10*C10&T-C/C10!'\T,,[=DD414243'>C{'43,*C50<br /> >T{'42,&CT*C50>T{'41,&CTGGGGGzfutureletAV,=YY41',:V'(A$>Y|>D),!<br /> 3!.>D"$$RR2R38$YY3Y-R&Y1$XX5[[=SS4142$'41:]'42,,=OO'>S]$,[[=Q<br /> Q41'T41*T41&CT,=HH'C0QXQYC-CQR,=BB'#X<RH#C<0P|O)&X1>B),=L<br /> L'#Y<RX-Rzhbox'B,&Y2>L),=PP'zhskip0.5em,zvbox'zttL,[:<br /> Y41',;A'bYryYge,=::41i'>{>'A,,~`412:stephen.hicks<br /> 3.14159265358979323846264338327950288419716<br /> 9399375105820974944592307816406286208<br /> 99862803482534211706798214808<br /> ..........kthxbai<br /></pre><br />For those who can't run TeX, the output is <a href='http://pages.physics.cornell.edu/~shicks/pi2.pdf'>here</a>Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com2tag:blogger.com,1999:blog-2953233889171032598.post-82825826766929497462010-11-21T14:50:00.000-08:002010-11-21T15:01:52.716-08:00Manual dependency resolutionSometimes 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:<pre>push () { <br /> STACK=("$1" "${STACK[@]}")<br /> pop<br />}<br />pop () {<br /> local TOP="${STACK[0]}";<br /> run "$TOP" && <br /> unset STACK[0] &&<br /> STACK=("${STACK[@]}") &&<br /> if [ -n "${STACK[*]}" ]; then<br /> pop<br /> fi<br />}<br />run () {<br /> cabal install --reinstall -p "$1"<br />}</pre>Obviously one would redefine "<code>run</code>" as appropriate. For instance, the initial cabal bootstrap might look like <pre>run () {<br /> cd $1<br /> for cmd in configure build install; do<br /> runghc Setup.*hs $cmd<br /> done<br />}</pre> and I would "<code>push $PWD</code>" after downloading and unzipping each package.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com0tag:blogger.com,1999:blog-2953233889171032598.post-44153482352514057992010-03-14T17:14:00.000-07:002010-04-14T02:25:13.243-07:00Happy Pi Day!<pre> \let~\catcode<br /> ~`z0~`'1~`,2~`q13~`z#<br /> 14~`46zdefq41'~`4113zgdef,q<br /> QQ41'~`4113zlet,qBB415425'41-P#<br /> 7427,QPPzexpandafterqAA414243'H#H<br /> 42434341542415,qCC41742743'41i-D42#<br /> 434343,qww',zedefw'PPPCPBAyap!,qEE',q<br /> 6641'~`4113zcountdef,QNNzifnum6RR1R20E6<br /> YY2QAAzadvanceY-RAY1QMMzmultiply6XX3EqS<br /> S'Ezhskip0.5em,EQJJzjobnameEQmmwE6TT5qj<br /> j4142x'41zgdefm'42,,EQ!!zglobalE6CC7Eqr<br /> r41'T41MT41ACT,qHH'C0rXrYC-CrR,qOO'zifx<br /> mEPjwxEzelsePjmxzfi,qcc'NX<RHNC<0Szelse<br /> OEzfiAX1PczelseE!AY2zfi,EzedefzJ'J,qv<br /> v'@,zifxzJvQOO*zfiEqll'NY<RX-Rzhbox<br /> 'c,Plzfi,zttl~`z612qii41h',~`zx0i<br /> 3.14159265358979323846264338327<br /> 950288419716939937510582097<br /> 494459230781640628620<br /> 899...kthxbye</pre>There's even an Easter egg (try running with <code>-jobname @</code>).<br /><br />For those who can't run TeX, the outputs are <a href='http://www.physics.cornell.edu/~shicks/pi.pdf'>here</a> and <a href='http://www.physics.cornell.edu/~shicks/pi@.pdf'>here</a>.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com3tag:blogger.com,1999:blog-2953233889171032598.post-13147891415108519892010-01-24T00:47:00.001-08:002010-03-09T22:31:18.483-08:00Hostname manglingHere'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, <tt>baley</tt>=192.168.1.10, <tt>gladia</tt>=192.168.1.11, and <tt>fastolfe</tt>=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, <tt>sdh.yi.org</tt>).<br /><br />First, I set up port forwarding on the router (essid <tt>solaria</tt>) to forward 2210 to <tt>baley</tt>, 2211 to <tt>gladia</tt>, and 2212 to <tt>fastolfe</tt>. I then added the respective ports to each host's <tt>/etc/ssh/sshd_config</tt> file (in addition to the regularly-scheduled port 22). Ideally I could simply add these names to my <tt>/etc/hosts</tt> 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 <tt>fastolfe</tt> (steve) than I have on the others (sdh), and I'd rather not have to mess with that.<br /><br />The solution I came up with is shell functions. I define <tt>ssh</tt> and <tt>scp</tt> 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:<pre>WIRELESS=wlan0<br />function essid {<br /> iwconfig $WIRELESS |<br /> perl -ne 'print $1 if /ESSID:"([^"]*)"/' 2> /dev/null<br />}<br />function ssh {<br /> local args=()<br /> while [ -n "$*" ]; do<br /> case "$1" in<br /> baley)<br /> case "$(essid)" in<br /> solaria)<br /> args=("${args[@]}" sdh@192.168.0.10) ;;<br /> *)<br /> args=("${args[@]}" -p 2210 sdh.yi.org) ;;<br /> esac ;;<br /> gladia)<br /> case "$(essid)" in<br /> solaria)<br /> args=("${args[@]}" sdh@192.168.0.11) ;;<br /> *)<br /> args=("${args[@]}" -p 2211 sdh.yi.org) ;;<br /> esac ;;<br /> fastolfe)<br /> case "$(essid)" in<br /> solaria)<br /> args=("${args[@]}" steve@192.168.0.12) ;;<br /> *)<br /> args=("${args[@]}" -p 2212 sdh.yi.org) ;;<br /> esac ;;<br /> *) args=("${args[@]}" "$1") ;;<br /> esac<br /> shift<br /> done<br /> command ssh "${args[@]}"<br />}<br />function scp {<br /> local args=()<br /> while [ -n "$*" ]; do<br /> local arg="$1"<br /> case "$arg" in<br /> baley:*)<br /> case "$(essid)" in<br /> solaria)<br /> arg="${arg/baley/sdh@192.168.0.10}" ;;<br /> *)<br /> arg="${arg/baley/sdh@sdh.yi.org}"<br /> args=('-P' '2210' "${args[@]}") ;;<br /> esac ;;<br /> gladia:*)<br /> case "$(essid)" in<br /> solaria)<br /> arg="${arg/gladia/sdh@192.168.0.11}" ;;<br /> *)<br /> arg="${arg/gladia/sdh@sdh.yi.org}"<br /> args=('-P' '2211' "${args[@]}") ;;<br /> esac ;;<br /> fastolfe:*)<br /> case "$(essid)" in<br /> solaria)<br /> arg="${arg/fastolfe/steve@192.168.0.12}" ;;<br /> *)<br /> arg="${arg/fastolfe/steve@sdh.yi.org}"<br /> args=('-P' '2212' "${args[@]}") ;;<br /> esac ;;<br /> esac<br /> args=("${args[@]}" "$arg")<br /> shift<br /> done<br /> command scp "${args[@]}"<br />}</pre>Now I can throw this onto any shell account I use (with appropriate modifications to the <tt>WIRELESS</tt> variable) and source it in my .bashrc to access any of my computers as if it had its own public IP address.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com1tag:blogger.com,1999:blog-2953233889171032598.post-44598960332990213092009-12-01T23:46:00.000-08:002009-12-02T00:00:00.465-08:00Fibonacci in GoI've been playing around with Go a bit. Here's what I think is the most Go-like solution to producing the Fibonacci sequence.<pre>package main<br /><br />import "fmt"<br /><br />func dup3(in <-chan int) (<-chan int,<-chan int,<-chan int) {<br /> a,b,c := make(chan int,2),make(chan int,2),make(chan int,2);<br /> go func() { for { x := <-in; a <- x; b <- x; c <- x } }();<br /> return a,b,c<br />}<br /><br />func fib() <-chan int {<br /> x := make(chan int,2);<br /> a,b,out := dup3(x);<br /> go func() { x<-0; x<-1; <-a; for { x<- <-a + <-b } }();<br /> return out<br />}<br /><br />func main() {<br /> x := fib();<br /> for i:=0; i<10; i++ { fmt.Println(<-x) }<br />}</pre>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 "<tt>fib = 0:zipWith (+) fib (1:fib)</tt>". 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).Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com2tag:blogger.com,1999:blog-2953233889171032598.post-72128007428206540032009-11-17T17:16:00.000-08:002009-11-17T21:00:25.954-08:00Oscilloscope Pong<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5yHVoSWkaHi7JvPCG8ZJ1trD4garaWrXM5K-A5AEIJQ1TXUTUfVy3owFY6jsqfUQ6KqOYO-UjK6XdPjjr-cQlhrT7IZ4bir1i1l0GdU7xdMJcQxMmoBV4hDn_RtpgXziDCXTYXvQH2tE/s1600/scan0208.jpg"><img style="cursor:pointer; cursor:hand;width: 400px; height: 271px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5yHVoSWkaHi7JvPCG8ZJ1trD4garaWrXM5K-A5AEIJQ1TXUTUfVy3owFY6jsqfUQ6KqOYO-UjK6XdPjjr-cQlhrT7IZ4bir1i1l0GdU7xdMJcQxMmoBV4hDn_RtpgXziDCXTYXvQH2tE/s400/scan0208.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5405301623814183330" /></a><br />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 <a href='http://pages.physics.cornell.edu/~shicks/pong.pdf'>here</a>.<br /><h3>Introduction</h3>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).<br /><h3>Circuits</h3>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.<br /><h2>Big picture</h2>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<sub>1</sub>, and CP<sub>2</sub> serve as controls, allowing the corresponding signals (B<sub>x,y</sub>, P<sub>1</sub>, and P<sub>2</sub>, respectively) to pass on to the scope only when the control is high. Thus, at any time, we need exactly one of CB, CP<sub>1</sub>, or CP<sub>2</sub> to be high.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipqpSRUIjoIsGGU0mgqvbieR5FCFJI_9B8gczxKW8WDsLqWpDK7RNWm35afHN9B_0lhiIp9viSl6P57Hl3KCsUApv1yfLpReTJ5KyN0rBQaASV63XJOd_9K4ZvGneLFFQm7dI2KU4XR_M/s1600/controls.png"><img style="cursor:pointer; cursor:hand;width: 303px; height: 260px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipqpSRUIjoIsGGU0mgqvbieR5FCFJI_9B8gczxKW8WDsLqWpDK7RNWm35afHN9B_0lhiIp9viSl6P57Hl3KCsUApv1yfLpReTJ5KyN0rBQaASV63XJOd_9K4ZvGneLFFQm7dI2KU4XR_M/s400/controls.png" border="0" alt="Control signals"id="BLOGGER_PHOTO_ID_5405189231513642738" /></a><br /><br />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.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjH7C_7lVZ94imAgxG5BBm6NyX7qhaGg5h94PYb91CragGOL2UgtTINM7I-wx1w6Ty0W61ybNHrpuK6noK3IeT67xTwv429UvuHj15yBJ9d8u0vaSygYh35fixWP5V89Q5g5UMBJGgGP0/s1600/scopeoutput.png"><img style="cursor:pointer; cursor:hand;width: 363px; height: 400px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjH7C_7lVZ94imAgxG5BBm6NyX7qhaGg5h94PYb91CragGOL2UgtTINM7I-wx1w6Ty0W61ybNHrpuK6noK3IeT67xTwv429UvuHj15yBJ9d8u0vaSygYh35fixWP5V89Q5g5UMBJGgGP0/s400/scopeoutput.png" border="0" alt="Scope Output"id="BLOGGER_PHOTO_ID_5405189229308134418" /></a><br /><h2>Analog Switch</h2>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.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGsTW3bd9Ol49jkYpovAY9YpoBjcB4h-lOqaW84L2xHx_jcjWAJAxJLKFeBLr7OWUtaEvP23YS88dgNWIr2nIXBAwPvG2SKdSqjv78KHBMthPjSpez1vdq9E2-J8yxM87XJ_LHaeSn-gw/s1600/analogswitch.png"><img style="cursor:pointer; cursor:hand;width: 400px; height: 233px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGsTW3bd9Ol49jkYpovAY9YpoBjcB4h-lOqaW84L2xHx_jcjWAJAxJLKFeBLr7OWUtaEvP23YS88dgNWIr2nIXBAwPvG2SKdSqjv78KHBMthPjSpez1vdq9E2-J8yxM87XJ_LHaeSn-gw/s400/analogswitch.png" border="0" alt="Analog Switch"id="BLOGGER_PHOTO_ID_5405189233088188546" /></a><br /><h2>Control Signal</h2>The control signals CB, CP<sub>1</sub>, and CP<sub>2</sub> 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<sub>1</sub> is high when C<-5V and CP<sub>2</sub> 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.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgUcownN7N6wNgzOSUaTeRMIGH1DjX_8sXIA20gD9B71OHQfBN6fFJw0Blo9AwPKeXH1jPkoLDXUcFrsnHNCv3s6q48_SuyPeLlvi3Z-Z6uHWmxAXpVA9h_yO8zuhdqjbdavikFPu3MyME/s1600/outputcontrol.png"><img style="cursor:pointer; cursor:hand;width: 392px; height: 400px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgUcownN7N6wNgzOSUaTeRMIGH1DjX_8sXIA20gD9B71OHQfBN6fFJw0Blo9AwPKeXH1jPkoLDXUcFrsnHNCv3s6q48_SuyPeLlvi3Z-Z6uHWmxAXpVA9h_yO8zuhdqjbdavikFPu3MyME/s400/outputcontrol.png" border="0" alt="Output Control"id="BLOGGER_PHOTO_ID_5405189242969718786" /></a><br /><h2>Ball Position</h2>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<sub>1</sub> and R<sub>3</sub> 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<sub>2</sub> and R<sub>4</sub> adjust the y- and x-speeds.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhHuuKnWKSTIpA2Zhdoy_t1hMtifVSXH1GvWsdCcgFxA9qvYE2CWWmn8rDNRVUd5EVu_fnHnZeMLkDLEH1LZA48B3Ql7J3-5UClm8YqJk5DvVrcpnKBBrhAdd2dXUOTsIzXdCyECacjbKU/s1600/ballposition.png"><img style="cursor:pointer; cursor:hand;width: 400px; height: 334px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhHuuKnWKSTIpA2Zhdoy_t1hMtifVSXH1GvWsdCcgFxA9qvYE2CWWmn8rDNRVUd5EVu_fnHnZeMLkDLEH1LZA48B3Ql7J3-5UClm8YqJk5DvVrcpnKBBrhAdd2dXUOTsIzXdCyECacjbKU/s400/ballposition.png" border="0" alt="Ball Position"id="BLOGGER_PHOTO_ID_5405189248039851202" /></a><br /><h2>Paddles</h2>The vertical paddle positions are given by the lines P<sub>1</sub> and P<sub>2</sub>, which we construct with a voltage divider, shown below in "Paddles". The potentiometers R<sub>8</sub> and R<sub>9</sub> should be large and easy to adjust (i.e., a joystick) and are used to move the paddles up and down. R<sub>6</sub> and R<sub>7</sub> 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.<br /><br />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<sub><i>i</i></sub> 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<sub>5</sub> controls the size of the paddles (around ±1V).<br /><br />The horizontal positions are fixed at ±5V, that is, either edge of the screen.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMn2uZAAO3-OliDpSNJBaGvPWjBh-oq6PC7NhtAhAKL2OjJxp_Y57N7o9IOiy8XynDtbN0fk5JyQmGiPt2aAna-Gca761qo0I1LypX7iDOx8P4yeGWZwE0pypffkcTiszStNbrNwX-iek/s1600/paddles.png"><img style="cursor:pointer; cursor:hand;width: 400px; height: 399px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMn2uZAAO3-OliDpSNJBaGvPWjBh-oq6PC7NhtAhAKL2OjJxp_Y57N7o9IOiy8XynDtbN0fk5JyQmGiPt2aAna-Gca761qo0I1LypX7iDOx8P4yeGWZwE0pypffkcTiszStNbrNwX-iek/s400/paddles.png" border="0" alt="Paddles"id="BLOGGER_PHOTO_ID_5405189834366157426" /></a><br /><h2>Power Supply</h2>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).<br /><h3>Improvements</h3><h2>Hit detection and scoring</h2>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'<sub>x</sub> and B'<sub>y</sub> are sent to the scope instead of B<sub>x</sub> and B<sub>y</sub>. As the design currently stands, it simply hides the ball until a reset button is pressed. The inputs D<sub><i>i</i></sub> must change when B<sub>y</sub> is within a paddle length of the P<sub><i>i</i></sub>, and the clock signals CLK<sub><i>i</i></sub> 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.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKJU_TGFjrL-Lload9tolD4RQbDiiOcACdn-oDMvXy6kCT5K2B9g-0gsIXxHdRVikvO3KQ4tBwF4PdcfdAJfTot40_QvfY6XTgGA2kuNogRhMKMrfGVWwoDWknarDuJqL4pAgxvKIEatY/s1600/hitdetection.png"><img style="cursor:pointer; cursor:hand;width: 400px; height: 194px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKJU_TGFjrL-Lload9tolD4RQbDiiOcACdn-oDMvXy6kCT5K2B9g-0gsIXxHdRVikvO3KQ4tBwF4PdcfdAJfTot40_QvfY6XTgGA2kuNogRhMKMrfGVWwoDWknarDuJqL4pAgxvKIEatY/s400/hitdetection.png" border="0" alt="Hit Detection?"id="BLOGGER_PHOTO_ID_5405189837841150754" /></a><br /><br />Unfortunately, this addition caused some impedance problems and smeared the whole picture terribly, and I was never able to fix it.<br /><h2>Dynamic ball speeds</h2>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<sub>y</sub>-P<sub>i</sub> 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.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com2tag:blogger.com,1999:blog-2953233889171032598.post-55755069265836453792009-06-29T20:38:00.000-07:002009-06-29T21:30:02.999-07:00ICFP Contest 2009It'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.<br /><h3>The problem</h3><br />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<sub>x</sub>, and v<sub>y</sub>) 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)<br /><h3>Our solution</h3><br />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.<br /><br />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.<br /><br />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...<br /><h3>Download</h3><br />In case you're curious, our source tree is available at <a href='http://pages.physics.cornell.edu/~shicks/darcs/icfp09/'>http://pages.physics.cornell.edu/~shicks/darcs/icfp09/</a>.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com0tag:blogger.com,1999:blog-2953233889171032598.post-10863727662260298472008-07-16T13:12:00.000-07:002009-06-13T18:05:23.987-07:00ICFP Contest 2008(Browse or download the code at <a href='http://www.physics.cornell.edu/~shicks/icfp08/'>http://www.physics.cornell.edu/~shicks/icfp08</a>)<br /><br />So, I just finished sleeping off a "double all-nighter" for the <a href='http://www.icfpcontest.org/'>ICFP Programming Contest</a>. 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.<br /><br />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 (<a href='http://www.ctan.org/tex-archive/macros/latex/contrib/inlinedef/'>inlinedef</a>) I recently submitted to CTAN, so the idea didn't seem too crazy ("When all you've got is a hammer...").<!--<br /><br /><br />--><h3>Initial Work</h3><!--<br /><br />-->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<br /><pre> I 600.0 600.0 30000 60.0 ... ;</pre> 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.<!--<br /><br /><br />--><h3>Math</h3><!--<br /><br />-->If I were writing this in a <i>real</i> language like C++ or <a href='http://www.haskell.org/'>Haskell</a>, 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.<br /><br />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.<!--<br /><br /><br />--><h3>An inverse heisenbug</h3><!--<br /><br />-->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 <i>began</i> 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.<!--<br /><br /><br />--><h3>Collision avoidance</h3><!--<br /><br />-->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.<br /><br />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 <a href='http://www.darcs.net/'>darcs</a> 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 <i>weren't</i> obstacles - so I just kept plugging away. <br /><br />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 <i>acceleration</i>, 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.<!--<br /><br />--><h3>The icing on top</h3><!--<br /><br />-->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.<!--<br /><br /><br />--><h3>Conclusion</h3><!--<br /><br />-->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.<br /><br />You can <a href='http://www.physics.cornell.edu/~shicks/icfp08/'>browse or download the code</a> 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 <a href='http://smlnj.org/icfp08-contest/simulator.html'>simulation server and maps</a> (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.<br /><br />Edit: <a href="http://www.physics.cornell.edu/~shicks/icfp08/proof.png">pictures</a> and <a href="http://www.physics.cornell.edu/~shicks/icfp08/proof.pdf">pdf</a> <a href="http://www.physics.cornell.edu/~shicks/icfp08/random.pdf">documents</a><br /><br />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.<br /><br />I've turned off comments because of spam. If you want to say something, feel free to email me.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com12tag:blogger.com,1999:blog-2953233889171032598.post-62282725413198249862007-06-22T20:06:00.000-07:002007-06-22T23:08:10.496-07:00PostScript librariesI'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.<br /><br />If you're interested you can get the most up-to-date version of it with darcs (or just browse to this directory):<br /><br />darcs get <a href="http://www.physics.cornell.edu/~shicks/darcs/pslib/">http://www.physics.cornell.edu/~shicks/darcs/pslib/</a>Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com0tag:blogger.com,1999:blog-2953233889171032598.post-58285130644237707202007-05-29T11:40:00.000-07:002007-06-22T20:23:12.579-07:00Blogger painI 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 <a href="http://www.physics.cornell.edu/~shicks/bloggerkeys.user.js">Greasemonkey script</a>.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com0tag:blogger.com,1999:blog-2953233889171032598.post-26309885120569560212007-05-29T09:59:00.000-07:002010-11-23T18:35:22.266-08:00Firefox + Google Scholar + Cornell LibrarySo, 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!).<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />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.<br /><h3>Installation</h3><ol><li>Install <a href="https://addons.mozilla.org/en-US/firefox/addon/748&h=152ed4005314c60fb406228b1c854e55">Greasemonkey</a> if you haven't already.</li><li>Install the <a href="http://www.physics.cornell.edu/%7Eshicks/googlescholarviacornell.user.js">userscript</a> for Google Scholar links.</li><li>Install the browser plugin for the context menu:<ul><li><a href="http://www.physics.cornell.edu/~shicks/culibrary.xpi">firefox</a></li><li><a href="http://www.physics.cornell.edu/~shicks/culibrary.crx">chrome</a></li></ul></li></ol>EDIT(2010 Nov 23): Added Chrome extension.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com3tag:blogger.com,1999:blog-2953233889171032598.post-60408235700798293732006-10-11T08:50:00.000-07:002009-09-08T23:53:20.420-07:00Obfuscated TeXI just came accross the following TeX program:<br /><pre style='font-size:90%'>\let~\catcode~`76~`A13~`F1~`j00~`P2jdefA71F~`7113jdefPALLF<br />PA''FwPA;;FPAZZFLaLPA//71F71iPAHHFLPAzzFenPASSFthP;A$$FevP<br />A@@FfPARR717273F737271P;ADDFRgniPAWW71FPATTFvePA**FstRsamP<br />AGGFRruoPAqq71.72.F717271PAYY7172F727171PA??Fi*LmPA&&71jfi<br />Fjfi71PAVVFjbigskipRPWGAUU71727374 75,76Fjpar71727375Djifx<br />:76jelse&U76jfiPLAKK7172F71l7271PAXX71FVLnOSeL71SLRyadR@oL<br />RrhC?yLRurtKFeLPFovPgaTLtReRomL;PABB71 72,73:Fjif.73.jelse<br />B73:jfiXF71PU71 72,73:PWs;AMM71F71diPAJJFRdriPAQQFRsreLPAI<br />I71Fo71dPA!!FRgiePBt'el@ lTLqdrYmu.Q.,Ke;vz vzLqpip.Q.,tz;<br />;Lql.IrsZ.eap,qn.i. i.eLlMaesLdRcna,;!;h htLqm.MRasZ.ilk,%<br />s$;z zLqs'.ansZ.Ymi,/sx ;LYegseZRyal,@i;@ TLRlogdLrDsW,@;G<br />LcYlaDLbJsW,SWXJW ree @rzchLhzsW,;WERcesInW qt.'oL.Rtrul;e<br />doTsW,Wk;Rri@stW aHAHHFndZPqpa.rtMRrgeLinZ.irLtYer.W,:jbye</pre><br />You'd never guess by looking at it that it prints the entire song of the 12 Days of Christmas. Amazing.Stevehttp://www.blogger.com/profile/17764004568545705634noreply@blogger.com3