# Hackercup 2014 - Qualifier

I had some fun doing it last year so I thought I would have a go again. This weekend was the qualifier. You can see the questions here

### Square Detector

We basically find the bottom leftmost and top rightmost black cell and check that the count of black cells is the same as the area of the square they describe

If the input was bigger then I would have found min/max in a single reduce but I like the clarity here and naming things is good right?

Here we sort the players according to the rule, get the two teams using take-nth starting at the first or second. The order the players come onto the pitch is a bit tricky, the ones with lowest draft numbers are on first but then they leave in order of highest first then the people on the bench come on lowest first, so the list of players in the order they come on the pitch is (concat (reverse (take p team)) (drop p team)) which we cycle so it’s infinite then use (partition p 1 cycled-team-list) to get a sliding window of P players moving up in ones. A speedup I did not do would have been using modular arithmetic for large m (both cycles repeat in the team size so we could replace m with their LCM rather then taking the mth of the infinite list directly)

### Tennison

I did not get this one right, I thought the tree was too big to actually sum all of the different ways Tennison can win so tried a Monte Carlo approach which works but is too slow to converge on the precision required.

After looking at the solutions they suggest a nice dynamic programming approach, but still they do calculate every way tennison can win, here is a clojure version that I think is still a bit slow on the input. I could not find a way to use the memoize function for the recursive function.

Please let me know any improvements to tennison you can think of, code is on github

# Asynchronous Game of Life

I had the idea to do an asynchronous Game Of Life in the browser using clojurescript’s core.async. I thought it would be fun if there was no global state, no external time and no datastructures - have the cells be channels just signalling to their neighbours when they transitioned between dead and alive.

Go take a look at it here

I will assume you have seen my other post with resources to learn CSP and core.async

I think the implementation is true to the idea of Asynchronous cellular automata but fear it has bugs as the steady state often settles on something that is not a valid GoL position (in particular I often see clumps of alive cells with too many neighbours, all surviving)

The code is on github, you can play with it in cljsfiddle and see a full page version of it.

As it is only 100 lines I may as well walk through them here.

Fairly uninteresting initialisation, prob is the probability a cell is alive/dead at the beginning. I made width height and cell-size atoms because I reset them all on calling init later.

Standard canvas drawing stuff

I thought it neat to have the draw function as a channel too, the timeout here sets the velocity of the simulation via backpressure on the unbuffered channels

The hardest bit to explain (and probably where the remaining bugs are…)

cell takes an [x y] position and returns 2 channels, one for input that neighbours can use to inform it about their alive/dead transitions and one to be told of new neighbours, via passing in their input channel, so it’s a channel of channels :-)

Each cell creates a single go block that listens for new neighbours and state transitions from neighbours on it’s input channels. Whenever something comes from a neighbour (either 1 or -1 to signal it becoming alive or dead) it updates it’s neighbour count, works out if it’s state transitions and tells it’s neighbours if it did and also sends draw a signal too. It is all kicked off by the alive cells telling their new neighbours they are alive as they connect.

There is an asymmetry in the alive/dead transitions, 3 neighbours

Getting neighbours for a position

This is the loop that kicks everything off (OK I cheat and have a collection here). We loop through the [x y] positions and create a cell (ie an [input new-neighbour] pair) for each and store the result in the cells map. Then we look up the neighbours for each cell and then pass into their new-neighbour channel it’s input channel. This starts our cascade.

The init function just sets the atoms, grows the canvas to fill the space it is given, draws the empty grid then kicks off draw-loop

Hope you enjoyed it, let me know if I can clear up anything (and if you spot a bug).

# core.async and CSP Resources

I compiled a list of Communicating Sequential Processes / core.async links for a friend after my Great British Node Conf lightning talk so thought I would share them here too.

### Go talks

I still think the best intro to CSP is these talks from Rob Pike

Very interesting is this point of Rob’s IO talk.

The select statement is a control structure somewhat like a switch that lets you control the behaviour of your program based on what communications are able to procede at any moment. In fact this select statement is a key part of why concurrency is built into Go as features of the language rather than just a library. It’s hard to do control structures that depend on libraries

This is where the power of macros is apparent, we can (somewhat) easily add CSP to clojure as a first class citizen alongside all the other great concurrency models that have existed since it was created. It is amazing that core.async works on the JVM and in clojurescript.

### Example

I can’t resist including one example myself as it’s so neat a programming model

Here we create 2 channels and 3 go blocks that are to be thought of as acting concurrently, the first one is an infinite loop pulling off both channels and printing the message received (alts! gets whatever result is ready from the list of channels provided), the next two simply send (with the >! function) the strings “hi” and “there” into c1 and c2 respectively.

Enjoy!

# Genetic Programming in Clojure With Zippers

This post is another update to my Lisp In Summer Projects project. I blogged before (1 2) about warm-up exercises but I have not yet explained the goal, I intend writing an Artificial Life simulation where the organisms themselves are Lisp programs that runs (via clojurescript) inside peoples browsers.

You may also want to check out a video of a talk I gave (in part) about this stuff for the london clojurians, slides here

After doing Genetic Algorithms, both in Coffeescript and Clojurescript the next step was to look at Genetic Programming. GP is the same as GA except that the genome is the AST of a programming language (Lisp makes it easier as S-Expressions are directly manipulabele).

Take a look a the Wikipedia Article before we continue with how I did it in Clojure using zippers.

As I said in the other post about GA, the basic idea is to:

• find a way to encode a particular solution to the problem as a genome
• work out their ‘fitness’ (ie how well they perform some task)
• choose the next generation by selecting and ‘breeding’ them (with some mutation for novelty)
• repeat until a good solution appears

In the GP world the first step changes, the initial genomes are valid programs rather than fixed length byte sequences. The ‘breed’ function is more complicated too, where before we could get away with choosing a random ‘split point’ and taking the left part of one and the right part of its mate and vice versa we have to be careful about where we slit and how we join the S-Expressions, also the length is not bounded anymore.

## Enter The Zipper

In Clojure zippers are found in clojure.zip and I’ll quote the description given there:

A zipper is a data structure representing a location in a hierarchical data structure, and the path it took to get there. It provides down/up/left/right navigation, and localized functional ‘editing’, insertion and removal of nodes. With zippers you can write code that looks like an imperative, destructive walk through a tree, call root when you are done and get a new tree reflecting all the changes, when in fact nothing at all is mutated - it’s all thread safe and shareable. The next function does a depth-first walk, making for easy to understand loops.

# Securing Cloud Backups With EncFS

Assuming you are on Debian/Ubuntu, install encfs

# apt-get install encfs


Simply run

encfs ~/PATH/TO/ENCRYPTED_FOLDER ~/PATH/TO/FOLDER


to create an encrypted version of a folder

$encfs ~/ENCFS/ENC/ ~/ENCFS/CLEAR/ Creating new encrypted volume. Please choose from one of the following options: enter "x" for expert configuration mode, enter "p" for pre-configured paranoia mode, anything else, or an empty line will select standard mode. ?> p Paranoia configuration selected. Configuration finished. The filesystem to be created has the following properties: Filesystem cypher: "ssl/aes", version 3:0:2 Filename encoding: "nameio/block", version 3:0:1 Key Size: 256 bits Block Size: 1024 bytes, including 8 byte MAC header Each file contains 8 byte header with unique IV data. Filenames encoded using IV chaining mode. File data IV is chained to filename IV. File holes passed through to ciphertext. New Encfs Password: Verify Encfs Password:  Then copy a few files into CLEAR (the unencrypted folder), you can see there is the same number and size of files in the encrypted folder ./CLEAR: total 19M -rw-r----- 1 thattommyhall thattommyhall 5.5M Jul 17 17:10 Developing_Backbonedotjs_Applications.epub -rw-r----- 1 thattommyhall thattommyhall 5.2M Jul 17 17:10 Developing_Backbonedotjs_Applications.mobi -rw-r----- 1 thattommyhall thattommyhall 7.7M Jul 17 17:10 Developing_Backbonedotjs_Applications.pdf ./ENC: total 19M -rw-r----- 1 thattommyhall thattommyhall 5.5M Jul 17 17:10 3R4b6qteJLZmTzMGit2cWajhzkVG,rLw6xry2PujL4LSbtg3EgftaMWfhQk4fM5mc-C -rw-r----- 1 thattommyhall thattommyhall 7.7M Jul 17 17:10 EnMiuriWbkgXYz7F9GsAzRlCBSpmHub7kvObd8fyFswVkhlUi-FzHaT7twrIHXsEOy5 -rw-r----- 1 thattommyhall thattommyhall 5.2M Jul 17 17:10 Z8izkCiMcMqBf,9a3a2smF3C6RAHQmicTi8UIgl7eCZfcRnOUVtwDq4kxrLM61Yc-n6   Getting md5 sums for the files. ~/ENCFS/ENC$ md5sum *
027a7ff02f785dbe211a91e9f218bea7  3R4b6qteJLZmTzMGit2cWajhzkVG,rLw6xry2PujL4LSbtg3EgftaMWfhQk4fM5mc-C
bd2635929cfab11349ba5dde73e0b303  EnMiuriWbkgXYz7F9GsAzRlCBSpmHub7kvObd8fyFswVkhlUi-FzHaT7twrIHXsEOy5
08786c915984a10532a2485f0e21ee4e  Z8izkCiMcMqBf,9a3a2smF3C6RAHQmicTi8UIgl7eCZfcRnOUVtwDq4kxrLM61Yc-n6


If you edit one file, just one changes

~/ENCFS/ENC$md5sum * 73a2f5ec8389aba5806b5b3eb267ed72 3R4b6qteJLZmTzMGit2cWajhzkVG,rLw6xry2PujL4LSbtg3EgftaMWfhQk4fM5mc-C bd2635929cfab11349ba5dde73e0b303 EnMiuriWbkgXYz7F9GsAzRlCBSpmHub7kvObd8fyFswVkhlUi-FzHaT7twrIHXsEOy5 08786c915984a10532a2485f0e21ee4e Z8izkCiMcMqBf,9a3a2smF3C6RAHQmicTi8UIgl7eCZfcRnOUVtwDq4kxrLM61Yc-n6  If you create a directory structure, it is recreated in the encrypted folder with an obfuscated name ~/ENCFS/CLEAR$ mkdir -p one/two/three
~/ENCFS/CLEAR$mv Developing_Backbonedotjs_Applications.epub one/two/three/ ~/ENCFS/CLEAR$ cd ..
~/ENCFS$tree ENC/ ENC/ ├── EnMiuriWbkgXYz7F9GsAzRlCBSpmHub7kvObd8fyFswVkhlUi-FzHaT7twrIHXsEOy5 ├── ViMb6X99i1TkJiAoyT-FHKTE │ └── 7EVvTVP53WUQF0SiJFhG-jzO │ └── azretaLwQ40MO38NDhqOlNXJ │ └── mpIK4ZSAq0gRwTeQWOaJRE,rbxSAAW0V4Cp8VdGXFj37q6IRkHVqdwPeSU0sq0JGQi4 └── Z8izkCiMcMqBf,9a3a2smF3C6RAHQmicTi8UIgl7eCZfcRnOUVtwDq4kxrLM61Yc-n6  This fact means that it will play nice with file based backups, except if they do a diff style copy as the whole file is likely to look changed with each update. To remount, simply run the same command as before and enter your password $ encfs ~/ENCFS/ENC/ ~/ENCFS/CLEAR/


You can put the encrypted folder in your Dropbox, copy it to S3, rsync/scp it to a VPS somewhere and they will never be able to see your data, neither will the NSA.

## OSX

Of course, if you use OSX - it’s easier. According to Emmanuel Bernard you just have to remember that the encfs in homebrew uses fuse4x which is now deprecated in favour of OSXfuse and simply do

brew install https://raw.github.com/jollyjinx/encfs.macosx/master/encfsmacosxfuse.rb
`

from a random github repo and wait while it compiles.

## Windows

I did not know that fuse has been ported to windows as dokan and has encfs available here, should be easy enough to set up.

## Android

Cryptonite looks good, but will not be as easy to set up as the others

# Heml.is Snakeoil

I have been meaning for a while to post about using public key crypto to secure cloud backups on services you can’t trust (ie all of them) but the recent launch of Heml.is made me get nerd-rage the other day and I just have to say something.

To quote them a little:

### Open Source

We have all intentions of opening up the source as much as possible for scrutiny and help! What we really want people to understand however, is that Open Source in itself does not guarantee any privacy or safety. It sure helps with transparency, but technology by itself is not enough. The fundamental benefits of Heml.is will be the app together with our infrastructure, which is what really makes the system interesting and secure.

Yes! The way to make the system secure is that we can control the infrastructure. Distributing to other servers makes it impossible to give any guarantees about the security. We’ll have audits from trusted third parties on our platforms regularly, in cooperation with our community.

Technology like public key crypto does not rely on particular servers, that it works on insecure transports is kind of the point (unless they know better than 1000s of mathematicians and security experts over the last 4 decades)

I’m glad to see they use some of the existing work (PGP and XMPP), and good on them for raising 150k to build a pretty messaging app, but until they explain how only their servers can successfully pass around PGP encrypted messages then I’m calling bullshit.

If you want secure IM encryption now just use libotr with XMPP and be interoperable

Take a look at the brilliant (and superbly named, I so wish I thought of it) Prism Break for more ways to protect yourself from snooping, not as colourful as Heml but ready to install on any operating system, for free, right now.

# Moving on From Forward

After 2.5 years at Forward I am moving on.

The time there has been great, I worked with some of the smartest people I know on some interesting projects. Things that are now core to me I used for the first time there - Hadoop, Hive, HBase, Node.js, Puppet, Clojure and I got a lot of exposure to ideas that have changed the way I think about solving problems. Working on a system handling 100s of millions of requests a day in pretty much all regions of EC2, merging 2 VMware infrastructures, trying to make sense of terabytes of data in Hadoop, speeding up and moving a bunch of high traffic action sports sites to EC2 in dealing with what was nicknamed the Greek bailout of tech debt, stream processing in Esper and Storm, being able to host DevOps meetups and the Clojure Dojos there, getting involved in the Coder Dojo, becoming a trustee of the Forward Foundation, plus the sum of all those tiny interactions that being in a place full of people who know more than you and are keen to share permits. My team in particular - fierce smart, results focused, metrics driven and with a wonderful shared simplicity aesthetic. I will miss it.

I am moving to FutureLearn, not much to see at the moment but an exciting take on the MOOC (Massive Open Online Course) concept. Owned by the Open University and building on their 40+ years of distance learning experience, partnering with the British Museum, the British Library and dozens of our top universities. I think it has a good chance to be a big part of the growing MOOC ecosystem. Anyone that knows me will know this is exciting and massively aligned with my values and interests. At the interview they spoke about pedagogy and engagement and really impressed me with their ambition, I will work hard to help realise it.

MOOC kind of started with the AI and ML courses last year and the two companies that came from them, Coursera and Udacity, are doing a great job, as is EdX but I’ve been following along with things from MIT’s OpenCourseware for years and lots of universities have always shared resources online. I think there is space to make something a little different, increase engagement and we have some amazing partners so keep an eye on us.

# 101 Goals in 1001 Days, Again

Some of you will remember my last 101 Goals In 1001 Days, it led to quite a lot of fun, gave me something to aim at over an extended period and completely transformed my fitness. People laughed when I said I would do a marathon and now I’ve done 2, I’m glad I surprised them.

I like that now people ask me “What adventures have you got planned?” and have been a bit sad about not having so much on the horizon and have been thinking about doing another 101 goals almost as soon as the last finished.

I held off officially starting as I have an ankle injury and a few of them are running and triathlon goals and I was still finalising the list, but I’ve decided to stop putting it off and just announce it. Let me know if you want to join in any.

I didn’t want to carry over any that I failed to do last time, but 3 on there are repeats I could not resist trying for again. I think the list is more realistic this time - less long and expensive trips on there, more ‘stepping stone’ type goals towards bigger ones.

1 - Read King James Bible
5 - Memorise opening of Beowulf
7 - Read 5 old english poems

## German

11 - Learn every day for 6 months

## Fitness

12 - Attend MMA Classes for 6 months
13 - Fight in a cage
14 - Squat 150kg
16 - Press 150kg
17 - 100 press ups
18 - 10 pullups

## Nature/Travel

19 - Trans Siberian Railway
20 - Meet David Attenborough
21 - See bears in the wild
22 - Okavango Delta

## Running

23 - 20 min 5k
24 - 45 min 10k
25 - 2h Half Mara
26 - 4h30 Mara

## Learning

27 - A Student’s Introduction to English Grammar
28 - Watch all Teaching Company Linguistics Courses
29 - Finish 10 online courses
30 - Fill all country names on a blank world map from memory
31 - Learn to dance
32 - Get some sort of postgrad qualification
33 - Learn To Read Hieroglyphs
34 - Learn to tapdance

## Ancient Civilisations

35 - Visit Çatalhöyük
36 - Cork Megaliths / Brú na Bóinne / Skellig Michael
37 - Skara Brae
38 - Uffington White Horse

## Hacking

39 - Finish 4clojure
40 - Seasoned Schemer
41 - Reasoned Schemer
42 - AIMA in clojure
43 - Build a robot
44 - Write a Go AI using Monte Carlo Tree Search
45 - Start using paredit
46 - Start using org-mode
47 - Write me a scheme in 48h
48 - Purely Functional Data Structures
49 - Structure And Interpretation Of Classical Mechanics
50 - Take part in Lisp In Summer Projects
51 - Write a goal tracking site
52 - Get something on KickStarter

## Cycling

53 - Long distance cycle
54 - London -> Brighton
55 - Hardknott Pass
56 - Cycle to Amsterdam

## Swimming

57 - Quarterly Wild Swim
58 - Swim 100
59 - Swim 500m
60 - Swim 1 mile
61 - Swim the Hellespont
OK this is a bit of a ‘stretch’ goal :-D

## Random

62 - Visit Mosslands (my secondary school)
63 - Visit 24th Wallasey (my old Scout troup)
64 - Visit Highclere Castle
65 - Play the harmonica
66 - Complete every Mario Game
67 - Write a book on infinity
68 - See Electric Six again

## Triathlon

69 - Sprint
70 - Olympic
71 - Half Ironman
72 - Ironman

## Outdoors

73 - Do bigish multi-pitch climb
74 - Get Single Pitch Award
75 - Climb HVS
76 - Ice climb
77 - Mountaineer a good grade
78 - Mt Blanc
79 - Elbrus
80 - Nehru Institute Of​​ Mountaineering
This was on last time but I so so want to do it
81 - Multi-day canoe trip
82 - Sea kayaking
83 - Summer ML
84 - Winter ML
85 - Horseriding
86 - Catch and cook something
87 - Spend a night in a snow hole

## Walking

88 - Walk London Loop
89 - Walk Capital Ring
90 - Yorkshire 3 peaks
91 - Do 20 munroes
92 - Do a UK long distance path at >30miles/day
93 - Walk 50 miles in a day
94 - Walk 75 miles in a day
95 - Walk 100 miles in a day
96 - Write an ebook on UK ultralighting
97 - Irish 3000ers
98 - Welsh 3000ers

## Lifestyle

99 - Start a not (just) for profit venture
Being a trustee of the Forward Foundation I have been impressed by people doing amazing work in London and Africa and want to do something myself.

100 - No internet for a month or a day a week for 6 months
101 - Have a 3 month break from work
I am tempted by Hacker School but will see what I wind up doing, plan is to let side projects be the only projects for a while.

There it is then, any you want to join in on let me know.

# Evolving Cellular Automata - the Code

My last post about automata was light on code, mostly because I got tired and lost some time doing the simulations inside the post in a way that worked in Firefox and Chrome.

This was as a warmup exercise for Lisp In Summer Projects, if you like Lisp - get involved!

Just after starting on it I noticed David Nolen had ported a demo of Minecraft in Javascript by @notch to clojurescript, keeping it fast using a few macros and sticking to using straight-up JS datatypes while staying as functional as possible, check it out. Particularly impressive is the output code being ~400 lines due to the Google Closure compiler.

You may want to read up on Genetic Algorithms in general first, but in short you

• find a way to encode a particular solution to the problem as a genome
• work out their ‘fitness’ (ie how well they perform some task)
• choose the next generation by selecting and ‘breeding’ them (with some mutation for novelty)
• repeat until a good solution appears

Remember the goal is to evolve a strategy to solve the Majority Problem using a 1D cellular automata with radius 3. I opted to have the main population on the server, do the selection and breeding there but have the fitness simulations (hopefully most of the computation needed) in browsers. This meant I had to fudge the generations thing a bit: So no results are wasted the workers get a sample of the population and post back the fitnesses and the population grows until at some point I shrink it, using the same selection method (Fitness proportionate selection)

Go here and help it evolve if you have not already

# Evolving Cellular Automata

This post is about evolving Cellular Automata to perform computation. The example I use is from the book Complexity - A Guided Tour

The most famous cellular automata is Conway’s Game of Life, a 2D automaton with simple rules to determine whether each cell lives or dies on each iteration based on the adjacent cells.

Above is the well known Glider Gun that is at the heart of many complex Life configurations, including a Universal Computer. A perfect example of complex results arising from simple rules.

The automata we are looking at today are much simpler and one dimensional.

Above is ‘rule 30’, so called because of its Wolfram Code (see here on the Mathworld site for more information). It is a binary (has two states), nearest-neighbour (each cell can “see” its 2 neighbours), one-dimensional automaton. As you can see it can be in 8 ($2^{3}$) different states and the binary below it is equal to 30. The bottom half of the picture is a ‘space-time’ diagram, the top row is the initial configuration and each row beneath represents the next step after each cell lives or dies according to its rule.

## The Majority Problem

The 1D automata I am interested in are binary also, but each cell’s neighbourhood includes its 3 adjacent neighbours on both sides (ie $2^{7} = 128$ different states as it can see itself and 6 neighbours). The world wraps like a torus so the 0th cell is adjacent to the 100th in our 101 cell world. The problem that we want to solve is the Majority Problem, ie if the initial configuration is mostly alive/dead after some number of steps all should be alive/dead, if so then the rule has successfully performed the task.

Go here and watch it evolve if you have not already.