All posts by jonathan zingale

Umeboshi – A Haskell Drum Machine

umeboshi

Umeboshi – A Haskell Drum Machine

Umeboshi is a drum machine written in Haskell and built from a Roland 808 sound bank. The drum machine is designed to facilitate poly-rhythmic percussion in non-standard time signatures. It relies heavily on Unboxed Vector types and the Data.WAVE library.

By design, most drum machines facilitate writing drum patterns in common 3/4 and 4/4 time signatures and render the ability to have more unusual rhythms such as an even pentuplet over three quarter notes nearly impossible. This limitation has a coercive effect on the forms of music typically made with drum machines. Umeboshi is an attempt to fill the gap left by such design choices.

Methods such as buildMeasure allow users to write a pentuplet over a three quarter note measure as easily as:

buildMeasure 122 (Time 3 4) [("xxxxx", conga)]

By passing a length five string of either '.' or 'x' and instrument type conga, umeboshi determines that a conga should be played evenly five times over the 3/4 measure. The function makeWavFile (thanks to the wonderful Data.WAVE library) then can produce a wav file of the constructed rhythm.

For a more elaborate example, let’s take a measure of 5/4 and layer a hi tom triplet evenly over the measure, a snare tuplet and otherwise maracas on every other of the underlying quarter notes:


layeredExample = do
  [hiTom, maracas, snare] <- roland808
  let ensemble1 = [("xxx", hiTom),("xx", snare),("x.x.x", maracas)]
  let measure = buildMeasure 122 (Time 5 4) ensemble1

  makeWavFile measure

For the gritty details see this project on GitHub: Umeboshi

Haskell Test Framework

Haskell Test Framework:

The Haskell Test Framework (HTF) supplies unit tests via HUnit and
property tests via QuickCheck. The following code describes some of the
functionality one may find in the test suite for the Attenuations project.
Some other useful tutorials can be found here:

At the top level one can safely disentangle functionality from testing
by creating a RayTracer directory for the former and a Tests directory
for the latter. Now by creating a TestMain.hs with the following lines,
one can import the tests and the modules independently as-well-as define
sub-suites to run individually.

{-# OPTIONS_GHC -F -pgmF htfpp #-}

module AttenuationTest where
import RayTracer.RayLength
import RayTracer.Lattice
import RayTracer.Rhythm
import Test.Framework

import {-@ HTF_TESTS @-} Tests.IndexerTests
import {-@ HTF_TESTS @-} Tests.SymmetryTests
import {-@ HTF_TESTS @-} Tests.XRegionTests

main = htfMain htf_importedTests

symmetryTests = htfMain htf_Tests_SymmetryTests_thisModulesTests
indexerTests = htfMain htf_Tests_IndexerTests_thisModulesTests
xRegionTests = htfMain htf_Tests_XRegionTests_thisModulesTests

Some Subtleties.

QuickCheck versus HUnit:

From ghci one can perform a quickCheck on any property test, prop_ prefixed,
by running something akin to quickCheck prop_someProperty. To run a specific unit
test, simply call the test method directly:

test_rabbits :: IO ()
test_rabbits = do
  let rhythm = take 15 $ rabbits (5,3)
  assertEqual rhythm ".rLrrLr.rLrrLr."

In some cases, one may wish to build a small unit test suite:

import Test.HUnit

test1 = TestCase test_rabbits
test2 = TestCase test_someotherFunction

tests = TestList [TestLabel "rabbits" test1,
                  TestLabel "another" test2]

runSmallSuite = runTestTT tests

Which then returns something like:

Cases: 2  Tried: 2  Errors: 0  Failures: 0
Counts {cases = 2, tried = 2, errors = 0, failures = 0}

Limiting the Range of Test Data:

It may often be the case that a functions domain of validity is limited
to a small subset of its range and testing outside of that range isn’t
very useful. The choose function makes it possible to limit the range
of test values while maintaining statistical randomness. For instance,
verifying that cos (π/2-θ) is the same as sin θ for values between
0 and 2π can be tested:

tol :: Double -> Integer
tol d = round $ d * 10^12

prop_cosToSin = do
  θ <- choose (0, 2*pi)
  return $ (tol.cos) (pi/2 - θ) == (tol.sin) θ

where tol allows for some wiggle room in the approximation.

Playing and then Replaying a test.

Occasionally a test will fail. Along with the error when a test fails
will be a Replay string allowing intentional seeding when replaying
a given test.

replayArg = "Just (TFGenR 15067B55359906C0776B9C0A73ACEE7D9C124B4AE3DAC3AFCB451E04B1EF7BD1 0 31 5 0,28)"

Now, to replay the failed prop_cosToSin test above one only needs to supply
the replayArg above in a new method, prop_cosToSinReplay:

prop_cosToSinReplay =
  withQCArgs (\a -> a { replay = read replayArg })
  prop_cosToSin

main = htfMain htf_Tests_SymmetryTests_thisModulesTests

Fairly General Algebraic Testing:

One of the coolest examples I have seen this far concerns testing
algebraic properties like the associativity of function composition
By importing Text.Show.Functions one can even test this property
with amazingly clean style:

import Text.Show.Functions

prop_ComposeAssoc f g h x =
  ((f . g) . h) x == (f . (g . h)) x
  where types = [f, g, h] :: [Int->Int]

Havel-Hakimi Graphs

Graph: a library for Havel Hakimi Tournaments

The Graph module offers data structures and methods for working with
direct graphs in Haskell. The library is then extended to working examples
of the Havel-Hakimi algorithm.

:l ./../Helpers -- mostly for hhsort

data Vertex = V { name::String, degree::Int} deriving Eq
data Edge = E { source::Vertex, target::Vertex } deriving Eq
data Graph = G { edges::[Edge] } | BadGraph deriving (Eq, Show)
type Degrees = [Int]

vertices :: Graph -> [Vertex]
vertices (G es) = let totV = [target, source] <*> es in f totV []
  where
    f [] acc = acc
    f ((V n d):vs) acc | any (\v -> name v == n) acc = f vs acc
                       | otherwise = f vs ((V n d):acc)

degreesToVerts :: Degrees -> [Vertex]
degreesToVerts ds =  [V (show ss) d | (ss, d) <- zip [1..] ds]

instance Show Vertex where
  show (V a b) = a
instance Show Edge where
  show (E a b) = show a ++ "->" ++ show b

instance Ord Vertex where
  (<=) (V ss n) (V tt m) = n <= m
  (>=) (V ss n) (V tt m) = n >= m

The above data types VertexEdge and Graph are the heart of Graph module.
Each comes with some default methods for accessing sub-types. Being defined explicitly,
vertices :: Graph -> [Vertex] and degreesToVerts :: Degrees -> [Vertex]
appear to be the odd methods out. vertices returns the vertices for a graph,
while degreesToVerts allows us to build a vertex set with expectations for the degree
of each vertex. Next, Some instances of Show are a included to keep things pretty.
Lastly, Ord is extended to Vertex so that we can sort on them.

Now the work horse functions:

havelHakimi :: [Int] -> Bool
havelHakimi (a:[]) = a == 0
havelHakimi (a:as) = havelHakimi.hhsort $
  map (subtract 1) (take a as) ++ drop a as

vertsToGraph :: [Vertex] -> Graph
vertsToGraph verts = rebuildDegs.G $ hh verts []
  where
    havel ((V ss n):as) =
        hhsort $ snd_map (+ (-1)) (take n as) ++ drop n as
    toEdges ((V ss n):as) = [E (V ss n) vert | vert <- take n as]
    snd_map f xs = [V a (f b) | (V a b) <- xs]

    hh [] edgeAccum = edgeAccum
    hh verts edgeAccum =
      let sorted = hhsort verts in
      hh (havel sorted) (edgeAccum ++ toEdges sorted)

rebuildDegs :: Graph -> Graph
rebuildDegs (G es) = G $ map (buildE es) es
  where
    buildV (V n d) tars = V n $ (length.filter (== n)) tars
    buildE es (E v1 v2) =
      let totalV = [name.target, name.source] <*> es in
      E (buildV v1 totalV) (buildV v2 totalV)

degreesToGraph :: Degrees -> Graph
degreesToGraph degs | havelHakimi degs = 
                        vertsToGraph.degreesToVerts $ degs
                    | otherwise = BadGraph

vertsToGraph relies on some not so obvious methods, hhsort and rebuildDegs.
The first is a specialized quicksort which orders vertices from largest degree
to smallest. The algorithm deincrements on the degrees given for the vertices, and so
rebuildDeg is needed to rebuild the degrees of each vertex.
The method degreesToGraph checks that a given set of degrees is graphic in the sense of
Erdős–Gallai, via the Havel-Hakimi algorithm. BadGraph is returned if the given set
of degrees is not graphic, and returns a realization if the set of degrees is graphic.
For example a list of n+1 n’s ought to represent an n-simplex in our scheme.

simplex n = degreesToGraph.take (n+1) $ repeat n
simplex 4
G {edges = [1->2,1->3,1->4,1->5,2->3,2->4,2->5,3->4,3->5,4->5]}

We then see that a 4-simplex is in fact graphic.

Abelian Actions

Abelian Actions on a Zipper

The goal here is to write an Action class which depends on an Abelian data type
and acts on a Zipper type. Composition of left Abelian actions Ab x G -> G and
evaluation are then given in the instance declaration for Action (Zipper v).

I begin by importing some useful modules and then defining a Zipper.

import System.Random
import Text.Printf
import Data.Char

data Zipper a = Z {left :: [a], focus :: a, right :: [a]} deriving (Eq, Ord)

shiftLeft :: Zipper a -> Zipper a
shiftLeft (Z (a:as) b cs) = Z as a (b:cs)

shiftRight :: Zipper a -> Zipper a
shiftRight (Z as b (c:cs)) = Z (b:as) c cs

instance Show a => Show (Zipper a) where
   show (Z a b c) = printf format (ff reverse a) (show b) (ff id c)
    where
      format = "[..%s { %s } %s..]\n"
      ff f = unwords.(map show).f.(take 10)

Notice that we can shiftLeft and shiftRight along our Zipper and further
there is a homespun Show instance so that these potentially infinite Zippers
can be displayed easily.

integers :: Zipper Integer
integers = Z (map negate [1..]) 0 [1..]

alphabet :: Zipper Char
alphabet = Z sahpla 'a' (tail alphas)
  where
    alphas = [chr $ mod n 26 + 97  | n<- [0..]]
    sahpla = [chr $ 122 - mod n 26 | n<- [0..]]
alphabet
[..'u' 'v' 'w' 'x' 'y' 'z' { 'a' } 'b' 'c' 'd' 'e' 'f' 'g' 'h'..]

Ok, so now there are Zippers. Now for an Abelian data type which can be extended
naturally to the Monoid class.

data Abelian = P Int | N Int

instance Eq Abelian where
  (==) (P n) (N m) = (n==m) && (n==0)
  (==) (P n) (P m) = n == m
  (==) (N n) (N m) = n == m

instance Monoid Abelian where
  mappend (P n) (P m) = P $ n + m
  mappend (P n) (N m) | n - m >= 0 = P $ n - m
                      | otherwise = N $ n - m
  mappend (N n) (P m) | m - n >= 0 = P $ m - n
                      | otherwise = N $ m - n
  mappend (N n) (N m) = P $ n + m
  mempty = P 0

Underlying Abelian is the type Int, which can be immediately recognized
as the de facto Abelian Object. Abelian is first extended to the Eq class
so that we can tell when two elements are the same. Next, instances for what is
meant by mempty and mappend are given for Abelian objects. mappend is really
just addition and mempty just 0.

Next, the Action class is defined so that given some Action v one can
compose Abelian operations and evaluate with respect to v. In other words,
the Action class characterizes left actions on v.

Lastly, I give an instance of Action Zipper.

class Action v where -- actions: Ab x G -> G
  compose :: [Abelian] -> v a -> v a
  eval :: Abelian -> v a -> v a

instance Action Zipper where
  compose abs = eval (foldr mappend mempty abs)
  eval (P n) = (!! n).iterate shiftRight
  eval (N n) = (!! n).iterate shiftLeft

Now to test it out! Let’s apply shortRandomWalk :: [Abelian], a list of random Abelian operations, to alphabet and return the zipper’s focus.

shortRandomWalk :: [Abelian]
shortRandomWalk = take (2^15) $ run.(randomRs (-10, 10)).mkStdGen $ 32
  where
    run (x:xs) | x >= 0 = P x : run xs
               | otherwise = N (abs x) : run xs

focus.compose shortRandomWalk $ alphabet
'j'

nice.

Sortable

From Listable to Sortable

Once there is a notion of Listable with its methods acting on its instances like lists,
the notion of Sortable is a natural extension. Here I extend Listables to have behaviors such as sort and shuffle. The sort is a quicksort and the shuffle is a key shuffle.

import System.Random
:l Listable

System.Random is imported here as a method for producing a stream of random numbers is required for a key shuffle.

The next few lines gives a function which produces such a stream. Notice, I am not yet concerned about a random seed.

randos :: [Integer]
randos = randomRs (0, 10^6) $ mkStdGen 32

take 10 randos
[279768,3864,196758,671882,495589,457372,652070,194519,28935,96049]

Next, I introduce the class Sortable. Notice that most ‘special’ methods are supplied by Listable. The Sortable methods are gotten ‘for free’. Lastly, instances of Sortable [a] and Integers are given. The one caveat being that Ord a => [a].

class (Ord s, Listable s) => Sortable s where
  sort, shuffle :: s -> s

  sort ns | ns == unit = unit
          | otherwise = branch smaller ns +++ headL ns +++ branch larger ns
    where
      branch f xs = sort.f (headL xs) $ tailL xs
      smaller n = filterL (<= n)
      larger  n = filterL (>  n)

  shuffle = eval . map snd . sort . zipS randos
    where
      eval = foldr cons unit
      zipS [] s = []
      zipS (x:xs) s | s == unit = []
                    | otherwise = (x, headL s) : zipS xs (tailL s)
                    
instance Sortable Integer where
instance Ord a => Sortable [a] where
sort 23478662345
shuffle 23423423
shuffle [1..10]
sort.shuffle $ [1..10]
22334456678
33243422
[2,9,8,3,1,6,5,7,4,10]
[1,2,3,4,5,6,7,8,9,10]

 

Haskell on Jupyter

HaskellToSpreadsheet

Haskell on Jupyter

Recently, I have found myself leading a Haskell programming meet-up in Santa Fe, New Mexico. We meet downtown at HQ or at Desert Dogs, Mondays around 6pm. This meet-up has been a great opportunity to actually learn to program Haskell well. In an effort to archive our work as a group, I am publishing meet-up notes here.

Haskell Test Framework.

Having a reliable test framework is an amazing thing. Here is a brief collection of notes describing some of the features and organizational structure of the Haskell Test Framework​ (HTF). Most of the examples are designed for my recent work developing a ray tracing algorithm.

Listable.

Here we write some methods for treating Integers as lists in the sense that
we can define notions of take, drop, (:), (++), and unit on Integers. From these we derive further functionality, namely: length, reverse, head, tail, and (!!). Since clearly both Integers and Lists are both instances of the same functionality, we define a class Listable handling both.

Sortable.

Now that there is a Listable class, we extend Listable things to be Sortable things. Put another way, given (Ord a, Listable a) => a we define a class whose instances can be sorted via sort and shuffled via shuffle. The sort is a quick-sort and the shuffle is a key-shuffle.

Vector.

Vector is a module designed to facilitate mathematical vector operations in the hermitian-style. For simplicity, I model only 3 dimensional vectors but allow the underlying fields to be arbitrary. Complex and Double serve as example fields throughout.

Abelian Actions on a Zipper.

The goal here is to write an Action class which depends on an Abelian data type
and acts on a Zipper type. Composition of left Abelian actions Ab x G -> G and
evaluation are then given in the instance declaration for Action (Zipper v).

Havel Hakimi Graphs.

The Swiss-McMahon tournament can be seen as a special case of the Erdős–Gallai theorem and as such, the Havel-Hakimi algorithm can be used to produce graphic tournaments. This module is designed to facilitate the production of these graphs.

Umeboshi – A Haskell Drum Machine.

Umeboshi is a drum machine written in Haskell and built from a Roland 808 sound bank. The drum machine is designed to facilitate poly-rhythmic percussion in non-standard time signatures. It relies heavily Unboxed Vector types and the Data.WAVE library.

Vector

Vector

Vector is a module designed to facilitate mathematical vector operations in the hermitian-style. For simplicity, I model only 3 dimensional vectors but allow the underlying fields to be arbitrary. Complex and Double serve as example fields throughout. The data type ThreeVector has a vector constructor: V3 x x x and a scalar constructor: S xThreeVector then extends the Functor class with fmap mapping over the components in the obvious way.

import Data.Complex

data ThreeVector a = V3 a a a | S a deriving (Eq, Show)

instance Functor ThreeVector where
  fmap f (V3 x y z) = V3 (f x) (f y) (f z)
  fmap f (S x) = S $ f x

The Comp class introduces conjugation for ThreeVectors. Complex types are conjugated while Double types are left invariant.

class Comp c where
    conj :: c -> c

instance Num a => Comp (Complex a) where
    conj = conjugate

instance Comp Double where
    conj = id

instance Comp a => Comp (ThreeVector a) where
  conj = fmap conj
conj (2 :+ 3)
conj $ V3 (1 :+ 2) (3 :+ (-3)) (0 :+ 1)
conj $ V3 1 2 3
2 :+ (-3)
V3 (1 :+ (-2)) (3 :+ 3) (0 :+ (-1))
V3 1.0 2.0 3.0

Now for the heart and soul of any module daring enough to call itself Vector.

The class Vector provides for the four base methods:

  • innerproduct, ()
  • norm, norm
  • evaluation, eval
  • projections, prs

Simultaneously, I extend Num to include ThreeVector. Extending provides meaning for summing, differencing, multiplying and taking the absolute value wrt ThreeVector. Notice that abs relies on and norm relies and abs. This mutual dependency simplifies the code, but requires that both extensions are present at the time of compilation.

instance (Floating a, Num a, Comp a) => Num (ThreeVector a) where
  (+) (V3 a b c) (V3 x y z) = V3 (a+x) (b+y) (c+z)
  (-) (V3 a b c) (V3 x y z) = V3 (a-x) (b-y) (c-z)
  (*) (V3 a b c) (S x) = V3 (a*x) (b*x) (x*x)
  (*) (S x) (V3 a b c) = V3 (a*x) (b*x) (x*x)
  abs vect = fmap sqrt (vect  vect)

class Vector v where
  (<|>) :: (Num a, Comp a) => v a -> v a -> v a
  norm :: (Floating a, Comp a) => v a -> v a
  eval :: Num a => v a -> v a
  prs :: v a -> [a]

instance Vector ThreeVector where
  (<|>) (V3 a b c) (V3 x y z) = V3 (conj a *x) (conj b *y) (conj c*z) -- Hermitian
  eval (V3 a b c) = S $ a + b + c
  prs (V3 a b c) = [a, b, c]
  norm = eval.abs

Now we can take the Hermitian innerproduct of two complex vectors and return their evaluation.

x = V3 (1 :+ 2) (3 :+ (-3)) (0 :+ 1)
y = V3 (3 :+ 2) (1 :+ 2) (5 :+ (-2))
eval $ x <|> y
S (2.0 :+ 0.0)

 

Listable

 

Listable

Listable is a module which contains the Listable class. The Listable class allows a user to create instances of types which can be treated as lists. Given a minimal description:

  • takeL :: Integer -> m -> m
  • dropL :: Integer -> m -> m
  • cons :: m -> m -> m
  • (+++) :: m -> m -> m
  • unit :: m

one gets the following functions for free:

  • filterL :: (m -> Bool) -> m -> m
  • (!!!) :: m -> Integer -> m
  • lengthL :: m -> Integer
  • reverseL :: m -> m
  • headL :: m -> m
  • tailL :: m -> m

Notice below that each of the Free functions are defined in terms of the required ones.
By indenting these definitions, placing them under the class banner, the haskell compiler expects the function definitions to be self-contained and defined purely in terms of the Listable class and standard functions given by Prelude. Additionally, Listable demands that its instances be comparable via the Equality class, Eq. Without being able to compare two values, there is no way to identify when a base case, unit, is reached. lengthL and reverseL rely upon this in their recursion.

In [1]:
class Eq m => Listable m where
  takeL :: Integer -> m -> m
  dropL :: Integer -> m -> m
  cons :: m -> m -> m
  (+++) :: m -> m -> m
  unit :: m

  (!!!) :: m -> Integer -> m
  lengthL :: m -> Integer
  reverseL :: m -> m
  headL :: m -> m
  tailL :: m -> m

  headL = takeL 1
  tailL = dropL 1
  (!!!) ls n = headL.dropL n $ ls

  lengthL ls | unit == ls = 0
             | otherwise = 1 + (lengthL.dropL 1) ls

  reverseL ns = ff ns unit
    where
      ff ns accum | ns == unit = accum
                  | otherwise = ff (tailL ns) $ headL ns `cons` accum
 
  filterL b ns = f b ns unit
    where
      f b js accum | js == unit = accum
                 | (b.headL) js = f b (tailL js) $ headL js +++ accum
                 | otherwise = f b (tailL js) accum

Now for some instances. Since [a] is essentially the defacto model of our class, it seems most obvious to begin with this instance. Above, the Listable type of cons is slightly different than one usually expects for (:).

Here, cons is constrained as: cons :: m -> m -> m

where (:) is usually constrained as: (:) :: a -> [a] -> [a].

This difference will ultimately have an impact on how a Listable cons behaves.

In [2]:
instance Eq a => Listable [a] where
  dropL = drop.fromIntegral
  takeL = take.fromIntegral
  cons [n] ns = n : ns -- wrap the left argument with [].
  (+++) = (++)
  unit = []
In [3]:
[2] `cons` dropL 3 [1..9]
[2,4,5,6,7,8,9]

Next, something less trivial. We can in fact treat numbers of type Integer as Listable as well. Best of all, all one needs to do is write instances for the necessary functions: takeL, dropL, cons, (+++) and unit.

In [19]:
instance Listable Integer where
  (+++) ns ms = ns * 10^lengthL ms + ms
  dropL n zs = div zs (10^n)
  takeL n zs = mod zs (10^n)
  cons n ns = ns * 10 + n
  unit = 0
In [20]:
2 `cons` dropL 3 987654321
9876542

It is probably worth mentioning that the Listable behavior of [a] and of Integer are noticeably different. Listable treats an Integer type as a list whose order is opposite to the order of a Listable [a]. This choice is arbitrary in that the Integer instance could likely have been written so that the two types have the same direction, though I am not entirely sure how to do it purely arithmetically. Additionally note, that since zero is defined as the monoidal unit, it behaves more similarly to [] than it does to the actual number 0.

In [37]:
[takeL 1 1000002 == reverseL 20, lengthL 0 == lengthL 1]
[True,False]

 

Two World of Warcraft puzzles, one solution.

Though online gaming isn’t usually my thing, my friend Alec has been a World of Warcraft nerd for many years. One day, after spending the night chatting with a fellow guildy, Alec presented me with a lights game puzzle. He writes:

I was hanging out in World of Warcraft one day, and a guildy was looking for the blue mechanowolf (Friender) pet for his Hunter. He came across the lights puzzle in Gnomeregan which summons Friender for you to tame, and was having trouble solving it. He asked for help in guild chat, and being a lover of puzzles, I decided I wanted to take a look.

The puzzle is pretty simple. You have a set of 8 lights, some of which are on, and some of which are off. If you click on a light, it toggles that light and the ones next to it. The object is to get all of the lights to be turned on. For instance, if the lights are currently set up like this:

first_lights

You could click the second light, which would change the puzzle to look like this:
second_lights

Unfortunately we were struggling to solve it. In fact, if you attempt to solve the example I’ve given you, you’ll find it’s impossible. Surprised that I couldn’t solve this when it seemed so simple, I took the puzzle to bed with me on a notebook, using binary representation to write out steps. Using the above example, I would have written 10110000 on my notebook with 01010000 underneath it to indicate the new sequence after clicking the second light. I finally gave up around 3:00 AM, extremely frustrated.

The next morning, I went into work and decided I was going to ask my co-worker Jon about this. I was fairly certain that there was no solution to the puzzle, but I wanted to ask him if there was a way to prove mathematically that the starting sequence I was working with (say 10110000) was impossible to manipulate to 11111111 given the rules of the puzzle.

After thinking about the problem for a while, I found that Alec was indeed correct. In particular, 1/2 of the starting configurations for the lights game have no solution! My reasoning is as follows:

Imagining each light to be independent of any other,
the 8 lights can be in any of 256 configurations, 2^8.
I aim to show that the 8 light operations in the light
game are dependent on one another and therefore not all
256 configurations can be reached from any other.
Further, from any starting configuration, only half of
the configurations, 2^7 = 128, can be reached.

Let us begin by considering the independent case.
Each light can be in any of two states, either on
or off. For modeling purposes let us assign the
number 1 to an on state and 0 to an off state.
Also, let us assign the function `add 1 modulo 2`,
which we will denote (+ 1), to the act of changing a single
light from its current state to its other state. In other
words we are mathematically representing the actions on a
single light as the cyclic group Z/2Z generated by (+ 1).
Effectively this means:

(a) performing (+ 1) an odd number of times affects the same
change on a light as just performing (+ 1) once. Let us denote
any performance like this with an ‘a’ for action. By parallel,
we notice that performing (+ 1) an even number of times effects
no change at all. Let us denote this trivial change by ‘e’.
Performing either ‘a’ or ‘e’ are the only two actions we can
perform on a given light, a(1) = 0 for instance.

(b) Both actions are self inverse and thus performing either
of them an even number of times is a trivial action,
a.a = e or e.e = e. This means that pairs of the same action
can be `cancelled` from a performance, ie.
(a.e.a.a.e.e.e.a)
(a.e.e.e.e.a)
(a.e.e.a)
(a.a)
(e)

(c) Possibly most crucially, performing the same actions in one
order versus another makes no difference to the outcome, ie.
(a.e.a.a.e.e.e.a) = (a.a.a.a.e.e.e.e). This last property of the
group is called the Abelian property.

Now for a leap of abstraction. While any one light can be
represented by one of our cyclic groups Z/2Z, we can also
consider pairs of Z/2Zs to represent pairs of lights (or more
generally n copies of Z/2Z can represent n many lights).
Now where elements of Z/2Z are either 1 or 0, elements of
pairs of Z/2Z can be written (0, 0), (0, 1), (1, 0), or (1, 1),
corresponding to the 4 configurations the pair of lights can
be found. Similarly, actions on these states can be written
(e, e), (e, a), (a, e), or (a, a). The act of performing paired
operations like (e, a) on paired states like (1, 1) can be
defined pairwise giving (e, a) (1, 1) = (e(1), a(1)) = (1, 0).
Notice how the nice properties (a)…(c) above extend in a rather
nice way.

(a’) Performing either (e, e), (e, a), (a, e), or (a, a) are the
only actions we can perform on a given pair of lights. Further,
(e, a) and (a, e) are generators in that combinations of these two
can be used to get to any other possible state.

(b’) Each action is self inverse.

(c’) This newly formed group of pairs has the Abelian property.

This suggests more generally that for n lights we can construct
an n-fold Abelian group whose elements (a1 … an) designate
any of 2^n possible light configurations and whose actions
(f1 … fn) designate any of 2^n possible ways to effect n lights.
Notice, that this model preserves the independence of any given
light. In other words, the only way to change the light in the jth
place in the a list, (a1…aj…an) is by having fj be an ‘a’.
pictorially,

abelian addtion

This fact has far-reaching consequences for us. If we are to write
out each of the n generators for the n-fold Abelian group,
f1 = (a e e … e)
f2 = (e a e … e)
f3 = (e e a … e)

fn = (e e e … a)

Not one of them can be expressed as the combination of any of
the others. Changing the jth and kth light has no effect on the mth.
These n independent actions form what is called a basis for our group.
That no action can be written as the sum of any others also means
that from any configuration on n lights we can get to any of 2^n
light configurations by applying combinations of the n actions.
With 8 lights, for instance, we can get to any of 2^8 = 256
configurations via combinations of the 8 basis actions.

If, on the other hand, the actions were dependent so that some
action, fj, could be performed as the combination of any of the
others, fj = f1.f3.f2 say, so would any performance involving fj
be dependent on a combination of f1.f3.f2. This means that we
could only reach 2^(n-1) possible configurations, 2^7 = 128 in
our example.

Now for the punchline (no longer the independent case but rather
the actual case). The light game has 8 possible actions. Each action
effects a small handful of lights. Changing the leftmost light, for
example, also effects its next closest neighbor to the right.
Generally, changing any light also effects that lights nearest adjacent
lights. If these actions were independent, they could be used to
reach any of 256 configurations for any starting configuration.
If instead we can perform any action as the combination of any others,
we can then only reach 128 configurations, ie half of the possible
configurations.

Notice, that performing (f1.f5.f4.f2.f7) as above, is the same as
performing f8. This means that f8 is dependent on f1, f5, f4, f2,
and f7. Via the reasoning above, this means that f8 does not contribute
uniquely to arriving at any configurations we otherwise could get to using
the other actions and therefore the total number of configurations
we can arrive at with f1 through f7 is 128, ie. less than 256.

Of course we could have instead thought of the 8 operations as being a basis for a vector space and considered them as the rows of a matrix. Then by computing Gaussian elimination we would see that only 7 of these vectors form a basis, ie. one of the rows would be zero. Further, the 7 vectors form a basis for a space with 128 elements. This means that for any given initial configuration, only 1/2 of the total configurations can be reached, as is intended to be shown.

Lastly, this particular puzzle reappears in a different form later on in the game. There it appears as the Shaman’s Totem puzzle. Though the game pictorially has been extended to a 2-dimensional playing field, the mathematics works out the same. Here instead of 8 lights there are 25 lights. Encoding these as binary vectors and computing Gaussian elimination gives the basis for the space of accessible light configurations, which btw IS fully accessible for any starting configuration 😉

  • Conjecture: Light games with n lights where n is congruent to 0 or 1 modulo 3 are completely solvable.

Ring Homomorphisms & Z/(3^k)Z

 

This slideshow requires JavaScript.

Rings like the Integers and Z/10Z (the ring of integers modulo 10) are ubiquitous. The slideshow above demonstrates how the rings Z/243Z, Z/81Z, Z/27Z, Z/9Z, Z/3Z, and the trivial ring are related via modding out by the prime ideal [3] . Each image represents a multiplication table where each color represents some member of a congruence class in Z/p^kZ.

Z_9
For instance, here is a multiplication table for Z/9Z written in colored numbers. The hues for Z/243Z are chosen so as to be as far apart from each other as possible and all of the colors are chosen to have full saturation values. At each step in the slideshow, elements which belong to the same coset, x + [3] , are blended together. For instance, [3] in Z/9Z is composed of the elements 0, 3, and 6. Each of their associated colors are blended, inevitably introducing bleaching in the saturation values. By the time the trivial ring is reached, all colors are equally mixed giving a single white element.

The initial colors assigned to each element are very important to how the colors blend under each homomorphism. In the slideshow below, the initial colors are reordered so that elements which belong to the same coset are similar in hue. Here instead of the colors ‘bleaching’ we see far away colors becoming more distinct until finally blending into white at the trivial ring.

 

This slideshow requires JavaScript.