Tuesday, September 25, 2012

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 RU. Turning the next lower layer to the left is Lu. Turning the right-most layer down is DR and turning the middle-left layer up is Ul. To name the final axis, we use the right-hand-rule: a counter-clockwise rotation of the front layer is FF since this is a right-hand rotation through the F-axis. A clockwise rotation of the middle-front layer is Bf. 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 Dr affects 12 on four separate faces, which is a bit unwieldy. If we follow it up with Rd we've now affected 22 blocks, touching all the faces: even worse. But if we continue with Ur and then Ld, 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 DrRDUrLD. [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: OF, OB, OU, OD, OL, and OR, again using the right-hand rule to determine rotation direction. Note that these are effectively just relabelings: OFUrOB is equivalent to just Ld. 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.

Monday, September 24, 2012

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!)6)×(24!/(2!)12×224)×(8!×38)/48 ≈ 4.5×1049,
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.

Tuesday, March 15, 2011

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.

Monday, March 14, 2011

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

Sunday, November 21, 2010

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.

Sunday, March 14, 2010

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.

Sunday, January 24, 2010

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.