Mary Rose Cook

A documentary by Nikolaus Geyrhalter. Notionally, it shows a series of things that happen at night: monitoring of borders, conventions of EU sub-committees, care for the elderly and prematurely born, parties, news broadcasting, pornographic broadcasting, food production, policing, counseling for the suicidal. Reviewers have noted different themes. Surveillance. Protection. The service industry. But these notes tell you more about the commentator than the theme of the film.

My own conclusions on the theme changed as I watched: being on or off stage, activities that happen at night, people who are working surrounded by people who are not, the services people provide to others.

By the end, I had arrived at: jobs that must be done at night. But distilling it down to that is a trivialisation. It is more worthwhile to think, “There are jobs that can’t wait until morning”, and take that as a jumping off point. Some general questions arise. What do these jobs entail? Why can’t they wait? Who does them? How? Then, more specific questions arise. Why does the night nurse clean the hand rails in the care home as well as attending to the patients? How does one talk to a stranger who is suicidal? Why are parcels sorted separately from letters?

In the film, there are many moments of distance and alienation. But, there are moments of human connection, too - a nurse tenderly feeding an old woman from a beaker, two people taking turns to shower after having sex, the film’s poster showing a network of street lights strung through the darkness of Europe.

Unsleeping people connected in the night.

Here, according to Last.fm, are the bands I have listened to the most over the last seven years. I have put in bold the bands that feel like a part of my identity. When I think about these bands, I get a warm glow. When I talk about them, I say “I fucking love”.

Dear and the Headlights
Sunset Rubdown
Bob Dylan
Des Ark
Women
The Paper Chase
The Mars Volta
Animal Collective
Meshuggah
The Blood Brothers
Converge
The Acorn
Xiu Xiu
Joanna Newsom
Beach House
Arcade Fire
Hurray for the Riff Raff
A Silver Mt. Zion

These identity bands have some common traits.

One. I love at least two of their records. Dear and the Headlights: both of their albums. Sunset Rubdown: all of their albums. Women: both of their albums. Des Ark: all of their live acoustic records. The Paper Chase: Now You Are One of Us and God Bless Your Black Heart. A Silver Mt. Zion is the exception, here. Horses in the Sky is one of my top ten records, ever. The rest of their albums probably aren’t even in my top fifty.

Two. I admire the aesthetic they achieve. Dear and the Headlights. The most beautiful melodies by anyone, ever. Bob Dylan. The deeper you go into his lyrics, the more you find. Women. The Beach Boys as a noise rock band. The Paper Chase. Find the most beautiful melody, then destroy it with how hard you feel it. Des Ark. Equate the art with the artist. Aimée Argote puts no distance between her manifestation in real life and her manifestation in her art. She makes music that, when heard, might be detrimental to her actual life.

Three. I find pieces of their music very meaningful. It is hard for me to cite examples, because music is so far from words. Not only is it impossible for me to explain why I love Bob Dylan’s line, “Let me dance beneath the diamond sky with one hand waving free”, but it’s precisely because of its wordless meaning that I like it, and it was Dylan who taught me that alogical emotion is worthy of trust.

Four. I admire (my conception of) the song-writer as a person. Sunset Rubdown’s Spencer Krug has a solo project, Moonface. The Pitchfork review of the Moonface record, Organ Music Not Vibraphone Like I’d Hoped, said Sunset Rubdown’s Dragonslayer is “A personal record about the toll that the worlds inside someone’s head takes on his relationships.” Des Ark. Aimée Argote sings about being a broken, high-functioning person. She sings about immovable, incidental, unpolitical queerness. Bob Dylan. He constantly moves on from his previous successes. As seen in the documentaries, Dont Look Back, and No Direction Home: he lives this life on the road half in love with Joan Baez, half in love with his own head.

But, most of the entries in that list are unbolded. These others are the bands that I simply listen to a lot. And I have listened to De-Loused in the Comatorium and Frances the Mute an awful lot.

I can’t identify with The Mars Volta’s music. Cedric Bixler-Zavala’s lyrics mean nothing. He chooses words that are one, impressionist remove from their actual meaning, rather than assembling a rich, internally consistent network from a few versatile base operators. Omar Rodríguez-López’s approach to arrangement is to chuck everything in. By saying everything, you say nothing.

I really like the Tony Scott film, Enemy of the State. It is a thriller that is brilliantly thrilling. In the same way, The Mars Volta’s music cuts in on a primal level and makes me want to sing and dance, which is kind of what music is supposed to be all about.

In Spelunky, you go through a learning experience that is like the learning experience you go through in the real world. First, you become familiar with the behaviour of the elements of the game. The arc described by a projectile. The beat walked by a cave man. The activation perimeter of the spikes in a totem pole. Second, you learn strategies for overcoming these elements. Land your jump on top of that totem pole. Strike a cave man three times with your boomerang to kill him. Third, you learn back-up strategies for the moments when your primary strategies won’t work. Activate the totem pole spikes by passing near them. Just as they are withdrawing, jump, hang onto the edge of the pole and haul yourself up. Jump on the cave man’s head to stun him. Throw him somewhere else. Fourth, you learn to combine the behaviours of elements. Whip a cave man until he sees stars. Throw him at the foot of a totem pole. Watch him get spiked to death.

But Spelunky is better than the real world, because it is simpler. There are fewer active elements, and no redundant elements. This makes the rules of the world easier to understand. It makes it easier to concoct a plan. It makes it easier to understand why the plan went wrong.

In Spelunky, you are always having fun. What type of fun? You are always on the edge of your seat because you lose everything when you die. You are never frustrated because the levels are randomly generated, so you need never replay any part of the game. You are always in an intellectually stimulating situation. Each level gives you a new combination of obstacles. And you can make the game as hard as you like. You can go for the riskily placed bars of gold, or the valuable artifacts that set off traps when you pick them up, or the items that you are too poor to buy and that must be stolen.

In Spelunky, you must balance risk and reward. Do you jump into that pit to try and grab those bars of gold, knowing that you might get unlucky, miss the jump out and get eaten by that man trap? This decision has multiple dimensions. The amount of gold you have determines your score, which might be important to you. But it also determines what you can buy. What you can buy affects your options for dealing with situations. You can buy more ropes and bombs. You can buy items with specific uses like ice guns, springs for your shoes, parachutes, and sticky gloves. Having extra things makes you more adaptable.

And what you can buy affects concerns outside your current life. Each death resets everything, besides the experience and skills you (not your avatar) have acquired on this go-round. But, very occasionally, there will be an artifact of your life that survives you. There are four worlds. Surviving the first leads you to the second. Surviving the second leads you to the third. Usually, death means starting right back at the beginning of the first world. But, if you make it through a world bearing particular gifts - a sizeable amount of gold, a bomb, a rope, it depends - someone called the Tunnel Man will dig you a permanent short cut to the beginning of that world. And purchase is one of the ways you can get hold of these gifts.

I have spent most of my game time this Christmas trying to make it to the end of world two with a shotgun for the Tunnel Man. To do this, I must battle through the jungle, at some point lay my hands on a shotgun, then make it to the end of the world alive.

Purchasing a shotgun is one of the options at my disposal. But shotguns are expensive and rarely in stock. In practice, I find myself making my way through the jungle, hoping to stumble across one of the two beings who carry shotguns: the shop keeper and the man guarding treasure. As I go, I try and accrue gold, bombs, extra health and some sort of projectile weapon.

If I see a mark, I do one of a range of colossally stupid things that will, almost certainly, end in my death. The least terrible plan is to use bombs to blast my way down into the shop or treasure trove, then keep throwing bombs in, hoping to kill the target. If I don’t have enough bombs, and I have a boomerang, I might try and stun the keeper/hoarder and then kill him with his own shotgun. If I have no boomerang, I will resort to doing the stunning with a lobbed rock, skull or damsel in distress.

The day before yesterday, I managed to get a shotgun. Afterwards, I proceeded very carefully. I made a beeline for each level exit. I collected no gold. I stayed back and shotgunned enemies.

I reached a row of vines hanging above spikes (instant death). These vines separated me from the world exit and the Tunnel Man. I drew a preparatory breath (in my actual lungs, not my explorer avatar’s lungs - breathing is not modelled in Spelunky) and thought, “Now, Mary, be careful. You’re not very good at these vines. You sometimes forget you have to hold up on the controller to cling on.” I leapt out over the pit, forgot to hold up and died.

I’ve just told you a gaming story, a monologue that tries to connect a series of disparate events into a causal, meaningful narrative. People attempt to turn the events in their own lives into narratives in the same way. We try and find causality in a world far too complex for our tiny brains to understand. I say, “I keep on moving from city to city, from country to country, because I can’t stand easiness.” We try to find meaning in causality. I say, “I can’t stand easiness because I’m searching for something that I feel is missing.”

Connecting events together into a narrative to find causality takes us a step from alarming randomness into delicious patterns. Using narrative devices - revelation, symmetry, ellipsis - to create meaning takes us another reassuring step into even more delicious, higher level patterns.

The Pitchfork review of Moonface’s record, Organ Music Not Vibraphone Like I’d Hoped, said Sunset Rubdown’s record, Dragonslayer, is “A personal record about the toll that the worlds inside someone’s head take on his relationships.”

Spencer Krug, the songwriter for Moonface and Sunset Rubdown, expresses patterns in his art that he cannot adequately communicate to the people in his life. This type of communication failure can also occur when reacting to art by another. I’ve tried so many times to explain to people what I like about Sunset Rubdown, how the corridors of the basement of the House of Leaves make me feel, what I see in Al Pacino’s eyes when Frank Serpico realises that his girlfriend is about to leave. But I can’t make myself understood.

With games, it’s even worse. I have some hope that I could make the people I care for understand why I like Hoop Dreams, because they know how documentaries work. But the structure and tropes of games are a mystery to my beloveds. We do not even have a common ground from which to start. So the things I learn from games, the feelings I get, the experiences I have, are locked up inside me, inexpressible.

I tried to find a still to illustrate this post. A still to illustrate the film. This is impossible. It can’t be the shot of Lisa shouting at her mum. It can’t be the shot of the bus driver bluffing his way through his interview with Lisa. It can’t be the shot of Darren crying. It can’t be the shot of the class debate blowing up. Margaret is just people talking. The shots are designed to show these conversations. As stills, they convey no information. There is little artistic observation in the locations, the colours, the montage, the framing. All there is are the words and the characters’ tones and expressions as they say them.

The most appropriate frame would come from the opening credits. These show New York crowds crossing streets in slow motion. They show the people lit up who are on stage and the people in darkness who are not. They make the ordinary lives of ordinary people as fascinating as those of fictional characters.

Margaret is a mess. It has too many side plots. It overdoes its crescendos. It has a strange mix of oblique emotional observation that is almost as good as Anna Karenina and characters that foghorn the director’s thoughts for him. Some characters feel like real people, others made up.

But it’s a very good film.

Press coverage of my latest game:

Kill Screen, PC Gamer, Chrome Experiments, Reddit, Indie Games, The Next Web, Creative Applications, AQNB, Kongregate, JS.gd, Bonte Games, HTML5Games.com, HTML5Games.net, I Can Has Cheezeburger, Ecrans, Bart Bonte’s best browser games of 2012.

I was interviewed for this Huffington Post piece about why programming should be taught in schools.

n. eye

I have just released Glazz, my new JavaScript library. It models vision in a 2D world. It has a built in raytracer that will tell you if one object in the world can see another object in the world. I used it in Empty Black and a game I will never release called Death Squad. It worked pretty well.

The code is open source under the MIT license. You can get it from Github or npm.

Last week, I released Empty Black, my 2D shooter/puzzler/platformer. In this article, I’ll describe how I made the player movement deft and intuitive. Play the game before you read on, so you’ll know what I’m talking about.

My general approach was to change something, then try it out. I took the ideas for adjustments from several sources.

One. I examined the parameters affecting the movement of the player characters in other 2D platformers. Is the floor slippy? What is the ratio of sideways movement to jump height? Does the character accelerate as it moves? Is the character’s jump height affected by the length of time the player holds the jump button? Is the character slowed when it bumps into a moveable object?

Two. I examined the unusual behaviours of the player characters in other 2D platformers. Super Meat Boy makes the character leap away from the wall automatically when wall-jumping. Spelunky lets the character pull himself up and over ledges. In Castlevania, the character can do an extra jump while in mid-air.

Three. I got people to play test. Kemal told me that the character movement should be effortless. Specifically, if the character hits a wall near the top, it should slip up and over. Ricky told me it was weird that the player had no control over the height of the character’s jump. He showed me how, when hopping over an obstacle in a room with a low ceiling, he bumped his head. Ricky also pointed out the jarring effect of the initial slow down of the character when it lands after a jump. Everyone told me that airborne movement was too sensitive. Everyone told me that wall-jumping was too finicky.

Four. I read pieces written by programmers about their character movement algorithms. These pieces were mostly confined to short comments, rather than in-depth analyses. Hence, this article.

To the algorithm.

The short version: a pile of hacks.

The long version:

The player presses the jump key. The first question is: can the character jump? Which means: is the character in contact with anything that can be used as a place to jump from?

Empty Black uses Box2D to control the physics of the game world. Any movements are subject to Box2D’s models of the forces of friction and gravity. Further, Box2D handles the reactions of objects that collide: bounces, shoves, spins and slides. The game can interrogate Box2D and ask what objects a particular object is touching. If the character is currently touching something solid, the character may jump.

Except, it’s not quite that simple. As well as leaping from the ground, the character can wall-jump. This means landing and clinging onto a wall, then jumping again, away from the wall.

This technique is used frequently as a way for the player to get the character up a narrow shaft. They jump it back and forth between the vertical, parallel walls of the shaft, ascending with each jump.

This ability is bounded. The player may jump the character out from a wall and land it on the same wall. At this point, it may not jump again. If the player tries to make it jump, the character will fall. This bound is there to improve the gameplay. It is easier to design fun levels if I can rely on the unscalable nature of a solitary wall.

The bound makes it harder to decide if the character has a solid footing. The character should be able to jump from the ground as many times as the player likes. But it should not be able to jump from the same wall twice in a row.

Fortunately, Box2D has a metaphysical object that complements the corporeal walls, enemies and bullets: the sensor. This spiritual creature has no physical presence. It has a location in the world and it registers collisions. The programmer can interrogate it about such collisions, just as with physical objects.

What I did was to attach a wide, short sensor to the bottom of the character. It would look like this, if you could see it:

Notice how the sensor overlaps the ground.

Now, instead of asking the character object about collisions, the game asks the character’s bottom sensor.

How does that help? It doesn’t. But I can attach two more sensors to the character, one on each of its sides.

This means that the game can ask each sensor if it is touching anything. If the bottom sensor is touching some solid footing, jumps are always allowed. If only a side sensor is touching a solid footing, the game must investigate further.

Jumps will be allowed in all cases but two.

One. The character lands against the wall it has just jumped from.

The game keeps a record of the last sensor that registered the solid footing for a jump. If it was a side sensor, and the character is using the same sensor for registration of the current solid footing, the jump is not allowed.

If the player loses control during a wall-jump ascent, the character will begin to fall. The player might manage to press jump as it hits a wall on its way down. It is possible that this wall will be the one they most recently jumped from. If it is, the jump would be prevented. However, there is an exception that permits the jump if the character is lower than it was when it jumped the time before. This exception allows the player to recover from their mistake. It makes the controls more forgiving.

Two. The character lands and sticks to the wall. The player continues to press the direction key that holds the character against the wall. They press jump again. The jump is not allowed. If it were, the character would slide up the wall like this:

To stop this, the game only allows the jump if the player is not pressing the character into the wall.

There is an exception. If the character is near the top of a wall, it may jump. This lets it slip up and over the wall.

The game now knows if the character is allowed to jump. To enact the jump, upward force is applied for a single instant. The character’s velocity is high when it first starts moving. It is progressively attenuated by gravity. Some distance into the air, all the character’s momentum will be gone and it will begin falling.

If the player releases the jump button before the character has reached its peak in the jump, the character will immediately begin falling. I stole this idea from Super Meat Boy. The effect is that of a glass ceiling being inserted above the character’s head. This allows the player to control the height of the jump. It stops Ricky getting a sore head.

The magnitude of the force of the jump is usually constant. However, it is increased in two situations.

First, when the character is carrying a crate. This stops the weighted character’s jumps turning into lame little bunny hops.

Second, when the character is falling faster than usual. Imagine the character is wall-jumping and, because of a player fumble, it hits the next wall at a point lower than the point it jumped from. To help the player recover, their next attempt at a jump from a wall will lift the character with a force greater than normal. The difference from the normal force is proportional to the disparity between the normal and actual force of falling.

Now: sideways movement.

The player presses the left arrow key. What happens?

A leftward force is continually applied until the player releases the key. The magnitude of the force depends on how fast the character is currently moving. If it is at top speed, no force is applied. If it is stationary, a large force is applied. The idea is to get the character to top speed as fast as possible, then hold it at that speed. This makes the movement more predictable. It also solves Ricky’s second problem. The character immediately regains top speed after it lands a jump.

The player releases the key that moves the character left. What happens?

The character immediately stops. There is no slippiness. Thus, the character is easier to control.

When I was designing the character movement, it was hard to keep the code tidy. I tried to find the smallest number of rules that required the least subsequent modification with hacks.

Two examples.

One. I tried to eliminate the slippiness of the floor by setting the friction very high. But this had many undesired consequences. It was hard to get the player moving sideways at top speed without also making airborne movement too sensitive. Crates could no longer be shoved, and mis-throws would leave them perched on ledges. I added code to immediately stop the character upon release of the move key.

Two. Slipping up and over a ledge was just a matter of the player pressing the jump key near the top of a wall. But if the character was only half way up a wall, such a jump would mean it slid upwards and got stranded. I could have left that behaviour as it was. But that would have made wall-jumping harder. I could have automatically jumped the character away from the wall. But that seemed too nannyish. So, I prevented jumps when the player was pressing into the wall but was not near the top of it.

In both cases, it was worth slightly modifying a generally correct behaviour with an ugly but small hack that had no repercussions.

The general approach was to try stuff to explore the options. But the goal was a few broad rules. I did this by only deciding on a permanent change after a careful check of the ramifications. And I sometimes entirely remade the rules, as with the addition of the sensors to the character.

Here is a pocket-sized summary for you.

Examine the overall behaviours and specific parameters of other games. Get as much player feedback as you can. Make many changes. Tidy up after yourself.

A couple of Sundays ago, I wrote an implementation of Dijkstra’s algorithm in Clojure. The core algorithm came to twenty-five lines. I banged out the code as I sat in a coffee shop with some other people from the Recurse Center. I ran my program on a data set that has two-hundred nodes in a densely interconnected graph. The program produced best paths from a start node to all other nodes in the graph in about 200 milliseconds.

I closed my laptop, finished my peanut butter, banana and honey sandwich, said goodbye to my friends and spent the rest of the afternoon wandering around the Lower East Side in the dusty sunlight.

By Monday evening, my life had begun falling apart.

Dijkstra’s algorithm is a way to find the shortest route from one node to another in a graph. If the cities in Britain were the nodes and the roads were the connections between the nodes, Dijkstra could be used to plan the shortest route from London to Edinburgh. And plan is the key word. The algorithm does reconnaissance. It does not go on a road trip.

Imagine you are the algorithm. You examine all the cities directly connected to London. That is, all the cities connected to London by a single stretch of road. You record the distance between London and each city. You note that you have now explored London. You focus on the city that is the closest to London by road. Let us say Brighton. You examine each of the cities directly connected to Brighton. You ignore London because you have already explored it. For each city, you record the distance from London to Brighton to the city. You note that you have explored Brighton. You now focus on the next unexplored city nearest to London. You continue like this until your destination comes up as the next city to focus on. When this happens, you have found the shortest distance to Edinburgh.

On Monday, at the Recurse Center morning check-in meeting, I blithely reported that I was going to spend the next couple of days implementing a Fibonacci heap in Clojure.

I had read on the Dijkstra Wikipedia article that two men had reduced the running time of Dijkstra by inventing the Fibonacci heap and using it for node selection. Dijkstra’s algorithm still did the route planning. The Fibonacci heap just helped out by quickly finding the city to explore next.

This search is a time-consuming procedure. You must go through the list of all the unexplored cities in Britain and find the one for which you have noted the shortest distance from London. When I had implemented Dijkstra in the coffee shop, my code had just gone through the whole list and returned the one with the shortest distance. This was slow.

The Fibonacci heap solves this problem in a different way. It orders the cities by their distance from London. Therefore, when you want to get the next city to explore, you just take the first one.

To explain, I must set aside the cities and roads metaphor. To my great regret, I cannot take up a new metaphor as a replacement. Heaps are not quite like family trees, nor quite like green trees that grow. So, instead, a figure:

This is an ordinary heap. The Fibonacci heap is a little more complicated, but the idea is the same. Each circle - each node - has zero or more child nodes. Further, each node includes a numerical annotation. This is its sorting value, or key. The nodes are connected into a tree where the one with the lowest key is at the root.

I started by producing diagrams showing examples of the core Fibonacci heap operations being applied to imaginary Fibonacci heaps. With the help of multiple reads through the Wikipedia article, I drew out each operation.

By the end of Monday, I had a forest of trees drawn out. I had mastered the algorithm and I could confidently explain it to Vera and Pepijn.

That night, as I was lying in bed, waiting to fall asleep, I realised that I was thinking about Fibonacci heaps. My downfall had begun.

I came into the Recurse Center on Tuesday and spent another day just writing in my notebook. This time, I produced rough blocks of pseudocode for the core algorithms.

In the morning, I had taken the G train to the C train to school. I’d been reading How to Solve It, a classic mathematical text that lays out an informal method for solving any problem. I had also been half thinking about Introduction to Algorithms, an exploration of algorithms for manipulating lists, trees, heaps and graphs.

It is one of the most glorious feelings to look back on a period and realise that it is suffused with what you were working on at the time. To realise that your work seeped into your journeys, your conversations, your relationships. I don’t mean that you looked up at the trees rattling in the wind and saw upended Fibonacci heaps. It’s much simpler than that. You were thinking about your work as you stood on the pinchingly hot pavement outside The Sunburnt Cow, as you discussed with your dad how the brush strokes for the sandstone in Roadway with Underpass somehow suggest the sparklyness of the sun. Your work was just gently present with you, providing a back story, or an invisible friend.

Thus, the next two weeks were steeped in maths and heaps. I thought about them in the shower. I thought about them on the G train. I thought about them in this bar that I and some other Recursers ended up in following an attempt to go to a bossa nova night after I had been disabused of the notion that bossa nova is drum-heavy salsa-ish music by a few minutes plugged into James’s iPod as we waited for the train and had discovered that it is actually much lighter and more deft and sounds like a skittering barbershop quartet.

I spoke about this interleaving of code and life in my talk on Pistol Slut at JSConf US in 2011. But, this time, I worried about the code. I started sleeping badly and fretting about how long things were taking to get finished. Instead of the nasty problems being spaced out over months, they were compressed into a couple of weeks. Instead of the code being a side project, I was working on it full time. Instead of writing in JavaScript, a relatively simple language, I was writing in Clojure, tearing dense, richly meaningful lines of code out of my brain.

I began writing code. Immediately, I discovered that tree structures are more complicated in languages like Clojure that have immutable state. This is because changing a node requires rebuilding large parts of the tree. Imagine you want to give a new child to a node that is somewhere far down the tree. You must duplicate all the nodes and branches that comprise the ancestory of the parent node. This is time consuming and takes up a lot of memory.

Pepijn pointed me towards a solution: a concept called the zipper. This structure expresses a tree as the node you are currently focused on, and the rest of the tree as viewed from the current node. For example, for this tree:

a zipper focused on node J would look like this:

Recall that expectant mother node. Now that the tree is modelled as a zipper, giving birth is much easier. I am going to create a new zipper that is an amalgamation of the reusable parts of the pre-child zipper and the new pieces I must create to represent the modification. The time and memory required depend on how much of the original I can use. In this case, I can reuse the path and the left and right contexts. So, the only new thing I must create is a new focus that consists of the new child, L, attached to its parent, J:

If you want to learn more about zippers, I recommend reading this excellent article, from which I adapted the previous example.

On with the story.

Vera and I spent the next two days buried in code. By the time the Recurse Center demo day came, we had nothing finished that we could show. We could only talk about the way the Fibonacci heap algorithm works.

Vera explained that a Fibonacci heap is not one heap (tree), but a list of self-contained sub-heaps (trees). She said there is a minimum pointer which indicates the sub-heap root node with the smallest sorting value. I can’t remember if she used a metaphor of cities on a map, and if she explained that, in this metaphor, the keys on the nodes are the distances of the nodes from the starting city.

She explained the core Fibonacci heap operations.

She said that merge is the way that a new node is added to the Fibonacci heap. The node is inserted as the root of a new sub-heap in the list of sub-heaps. If the new node’s sorting value is smaller than the node currently indicated by the minimum pointer, the pointer is updated.

She said that find min takes the pointer to the smallest root node, follows it and returns the node itself.

She said that extract min takes the pointer to the smallest root node, follows it and removes the node from the sub-heap to which it belongs.

She showed how extract min tidies up by going through the former children of the node and making each one into a new stand-alone heap in the list of sub-heaps.

She showed how extract min tidies up further by consolidating the list of sub-heaps, combining pairs of sub-heaps that have the same number of direct descendents.

She explained how the decrease key operation works. She said that the first step is simply reducing the sorting value of a node. She said that, if this reduction makes the key smaller than the key of the node’s parent, the node must be removed from the sub-heap and made into the root of a new sub-heap. She also said that the minimum pointer might need to be updated to point at a new minimum root node.

She explained that, if any node loses more than one child to a decrease key operation, it, too, must be made into a new sub-heap.

The day following, a Sunday, I spent the afternoon sat in a coffee shop in a beam of sunlight, finding some respite from the turmoil. I wrote code that was isolated from the main problem. It produces the Fibonacci heap corresponding to a terse definition of a tree structure. This made writing tests much easier, because it made it easier to produce Fibonacci heaps that reflect a scenario to be tested.

On Monday and Tuesday of week two, Vera and I dived back into the chaos and implemented decrease key, thus completing the Fibonacci heap. We worked on Saturday - demo day - to wire it into my implementation of Dijkstra’s algorithm. Slowly, a horrible realisation dawned upon us. A Fibonacci heap written in a language with immutable state is, as far as we could tell then, and as far as I can tell now, incompatible with Dijkstra’s algorithm. In fact, it is incompatible with any algorithm that relies on a data structure that is distinct from the Fibonacci heap, but that also shares the same information. Pepijn has written on his blog about a generalised version of this difficulty, naming it the double index problem.

In Dijkstra with Fibonacci heap, there are two data structures. First, the Fibonacci heap. Second, the graph of nodes that tells you which node is connected to which (fuck it we’re going back to the map metaphor) city. Examining the neighbour of the city you are currently focusing on may neccessitate decreasing the best route distance you have stored for the neighbour. But, this is not so easy. When you get the list of neighbouring cities, you are looking at the graph data structure, which means you have graph nodes in your hands. Though these graph nodes represent the same cities as the nodes in the Fibonacci heap, they are distinct entities inside the computer. Thus, to call decrease key (distance) on a city (heap node), you must get hold of the node that represents the city in the heap. This is a time-consuming operation that involves searching through the heap.

I’m going to stage a little mock Q&A between an imaginary version of you and the actual version of me.

You: Why is this not a problem in languages with mutable values?

Me: Because the nodes in the graph can just contain a pointer to their counterpart in the Fibonacci heap.

You: What is a pointer?

Me: It’s like an arrow that gives you a direct, quick route to a computer’s representation of something.

You: Why could you not use use such pointers?

Me: We could, but they would not have the desired effect.

You: Why?

Me: Because, in an immutable language, when you change a piece of data, you get a whole new copy back.

You: Gosh, it’s annoying how you won’t go into any detail unless I ask. Why is the whole new copy thing a problem?

Me: Sorry. It’s a problem because when you update a node with a new distance, you copy that node as part of the change. Other pieces of data may have pointers to the node, but they now only have pointers to the old version. In a mutable language, you would have just updated a shared piece of data and not copied anything. Thus, all pointers to that data would have remained valid.

You: I see.

We implemented the find operation in the Fibonacci heap. This operation is given a node and finds it in the Fibonacci heap. This operation is antithetical to the point of the Fibonacci heap. When we used it, this operation was so time consuming that the original version of Dikstra’s algorithm ran twice as fast as the version with the Fibonacci heap.

Showing these results at the Recurse Center demo day was kind of disappointing and kind of funny. However, both these feelings were tempered - no, obliterated - by the warm, relieved afterglow of finishing the Fibonacci heap.