Book Review: Designing Data-Intensive Applications

This textbook is excellent and I wish I had read it sooner.

In particular, I have spent most of my career so far focused on gaining experience at work and on projects. That hands-on experience is key, but getting a larger overall picture of the world is also really important. Designing Data-Intensive Applications came out in 2017, which means I had been out of school for a while where, presumably, this book is more well known.

Many STEM careers can place you in a more academic position where I think reading the most up-to-date textbooks and papers is more common sense. But engineers in the private sector can obviously benefit from some textbook exposure as well to learn about the latest best practices and accumulated knowledge. What’s more, there are clearly benefits to the private firms whose employees would read this book! I’m fairly certain my old job had O’Reilly subscriptions, but I just didn’t know this was the thing to read.

As far as content, this book really focuses on everything you need to know about data backends. I’ve done a fair amount of work on front-end systems and building microservices, but ultimately my data systems exposure has been limited to fairly straightforward implementations. This book teaches you about replication, sharding, consensus and reliability, and also how to think about batch processing vs more static data. The O’Reilly site for the book contains the entire (extensive!) table of contents and I honestly recommend reading that if you have even the slightest interest in software, computer hardware, data systems, or the modern internet.

The detail is tremendous. At the risk of repeating myself, I really didn’t understand what I was missing or what I was getting into. I had thought about this as just another nonfiction book I was reading, but it really is a textbook which means it’s large (not just 500 pages, but textbook sized pages!) and dense. Taking notes, it was hard not to write something down for every paragraph, and so even my notes taken are intensely long.

The book is also quite clear in explaining everything so that it’s understandable. The only tiny quibble I had in the 550+ pages was that the author Martin Kleppmann has obviously not read Paul Sztorc’s “Nothing is Cheaper Than Proof of Work” despite it being written in 2015. But at least this was restricted to the speculative and opinionated final chapter, so I can’t fault it too much.

So of course, I would highly recommend it. I’m also somewhat excited as I’m wondering what other important texts I’ve been missing. I also think I’ve got a slightly better system for finding out what people at my current employer (Facebook) think are good programming/software books, so I’m hopeful it won’t be another 7 years before I read another important text!

Deep Rock Galactic

Deep Rock Galactic is a cooperative first person shooter in early access from indie developer Ghost Ship Studios. Players are galaxy-fairing mining dwarves sent on dangerous missions on a hostile alien planet. The missions contain a variety of objectives and types of enemies, and allow for up to four players to play together.

This past year saw a slight uptick in the number of videogames I was able to play. This was particularly possible because I started talking with a couple old friends who often gamed together and they invited me to join them in playing specifically co-op games.

Multiplayer games aren’t exactly foreign to me, as I played World of Warcraft on and off since 2005. However, back then, I didn’t have great internet and I played very casually. I never got into raiding, and so I never really chatted with people on VoIP. I did often do multiplayer with people in the same physical location, and in fact I had a WoW arena team with my brother in high school as we played in the same room, negating the need for voice chat. Since then, I just didn’t play that many videogames cooperatively, and I didn’t have a consistent group. I still played a bunch of single player games, but I tried something new with Overwatch, as I wrote about a couple years ago. That was a lot of fun, but my lack of consistent playing group meant that after Overwatch, I went back to single player games…or Netflix.

This new group opened the door to Deep Rock, and it is spectacular. With the major caveat that I’ve only played the game with people I like hanging out with, Deep Rock seems to check every box you could have for this genre. The gameplay is pretty simple to learn; you shoot aliens and you mine rocks. But once you know the basics, you can start exploring the complexity of the game. There are multiple classes with different guns and abilities. They allow for grappling across levels, creating instant platforms on walls, permanent moving cables, or digging out tunnels through rock. More stuff is being added every month as it is still in early acess. Each class can now undertake quests to upgrade their various weapons which can be swapped out. There is quite a lot of firepower to choose from, with a big rotary machine gun, flamethrower (or ice thrower), shotgun, or even automated turrets, depending on your class.

There are also multiple types of alien bug creatures. Some are pretty standard enemies that run up and attack you. Others are suicide bombers that will stand next to you and detonate. If you know where they are coming from, you pick them off from a distance, but if you let them get close, you better call them out to your teammates who are busy mining rocks or trying to stop other bugs from eating their face off. There are also flying bugs, some that will try and pick you up and drop you far away from your teammates, ranged acid spitters, and giant armored beasts. Some bugs are even attached to shadowy cave ceilings waiting for you to drop under them, where they grab you and pull you helplessly away. Your only hope is for your teammates to blast the leach before you expire. These make for some hilariously chaotic battles.

And that’s not even counting the various types of levels you can play in. Each “ecosystem” on the planet has its own quirks and difficulties, from poison shooting mushrooms to radioactive crystals to giant sand storms that blind you for a short period of time–even in the midst of an enemy wave. The level design itself is beautiful even though I believe every level is algorithmically generated. There are several different missions types, including simple mining missions, missions to collect rare alien eggs, salvage operations where you recover equipment and then use it to escape the planet, and others. My favorite is extraction point missions where you are dropped in an area with many large crystals you must dig out and return to a central location while surviving waves of enemies. Then you have to protect the outpost until the your cargo is rocketed away, and finally battle your way to a rendezvous point.

The cooperative nature of the levels really makes the game for me. Putting up a good fight as aliens slowly surround you is tense, but when one of your teammates is suddenly picked up by a grabber and flown away, the panic starts to set in. There is intensity when making a daring run for one of your downed teammates, throwing up a temporary shield and reviving them while swarms of bad guys surround your bubble waiting for it to disappear. Another fun moment was at the end of a level where we had completed all the objectives, we now had to make it to the extraction rocket they sent. Somehow, the only way over to that part of the cave seemed to include narrow bridges of unavoidable enemies and it was taking too long to deal with them. It didn’t look like we could make it to the rocket before the level ended, meaning all of our work would be for nothing. With 90 seconds left, The digger thought he might be able to burrow straight through 60 or 70 meters or solid rock to get the chamber with the rocket, so we covered him, as tons of giant bugs tried to crawl into our tunnel while he slowly dug it out. We popped out right next to the rocket and got inside before time expired.

I recommend Deep Rock for its fun collaborative environment and interesting gameplay. Its level and mission design is really cool and it’s a pretty fun alien shoot ’em up, too. But the biggest personal takeaway from this game is that adults need to look at cooperative videogames as a medium for social gatherings. Modern society, and the internet in particular, has created a somewhat isolating social landscape. Netflix and HBO and YouTube mean that we live in an golden age of television and creativity, but also that we don’t need to interact with others in person in order to experience it; it comes directly to our devices in our bedrooms or living rooms. Cooperative gaming can act as a virtual social room, placing you at least ear to ear with your friends as you share an interactive experience and challenge. When I play Deep Rock, I don’t think of the time spent as “entertainment”, I think of it as “social interaction”. Even though my friends are thousands of miles away, we are talking about life and hanging out. I see this as a fulfillment of what people thought the internet could be; a place to allow people to connect in ways they could not before.

The Last of Us

The Last of Us is a videogame developed by famed studio Naughty Dog, which also developed the Crash Bandicoot series as well as the various Uncharted games. The Last of Us was released in 2013 to extremely positive reviews and is often placed into conversation as one of the best videogames of all time. I didn’t own a PlayStation 3 so I didn’t get a chance to play this game until recently. Despite it coming out 5 years ago, I think it’s still worth writing about because it was just that good.

My favorite high school English teacher used to tell us that what made great authors and artists was their ability to build transformational art. By that he meant great artists could simultaneously do the well known and expected approach extremely well while also building on that and incorporating the new and avant-garde to seamlessly bring the audience towards new ideas. He would always use the Beatles as an example, pointing to their earlier generic pop sound which gave way to their more experimental later albums, but it’s a nice approach to use for almost any analysis of art.

For example, I’ve noticed that many of my favorite superhero movies aren’t really superhero movies at all; The Dark Knight is a detective movie disguised as a superhero movie, The Winter Soldier is a spy thriller disguised as a superhero movie, and Logan is a western disguised as a superhero movie. These movies are interesting because they pushed the boundaries of what was possible with their genre. The Last of Us pushes the boundaries of what counts as a videogame.

Taken solely on its merits as a game, The Last of Us is excellent. It takes aspects of games that are quite familiar to anyone designing a shooter in the early 2010s and does them really well: it’s a survival shooter that takes place in a post-apocalyptic world with zombies. Zombies are a somewhat common trope in horror films but they are heavily represented in videogame media. The zombies in The Last of Us are properly horrifying, varied, and challenging to deal with.  It also has you teaming up, or at least working with, a rebel group in this post apocalyptic society against the government’s military rule. There are specific gameplay mechanics that are familiar, such as sneaking around to remain unseen from enemies, various guns that are upgradeable over time, and physical puzzles or obstacles that must be overcome. The “survival” aspect of the game is particularly well done though.

Many videogames have good stories. Half-Life 2 and both Portal games are some of my favorites, but they still have a pretty strict boundary between gameplay and story. It’s fun to check out the story elements and much of it is told through cutscenes, but The Last of Us brings the story in close to the gameplay. You are constantly aware of the post-apocalyptic world around you, and not just through the beautiful level designs of real American cities in ruins, but also because you are constantly running out of materials. You find a shotgun, blast some zombies triumphantly, and then quickly realize you are out of ammo and have to switch to a low power handgun. Maybe you have time to duck behind some cover and swap out the hunting rifle so you can use those last three bullets before you’re forced to start bashing heads in with metal pipes or scraps of wood you find, which also eventually break. It’s almost always a good idea to stealthily dispatch as many enemies as possible, both to reduce the number of enemies and to conserve ammunition. Even other items like shivs and health packs are all constructed from collected materials, and making more of one might preclude you from making more of others. The feeling of scarcity is omnipresent, and improvisation is vital to complete most levels.

The gameplay is also well varied. The story of The Last of Us revolves around Joel, a deadly smuggler, transporting Ellie, a girl who is immune to the zombie disease, to the underground resistance. Throughout this journey, there are different types of enemies which require different strategies, but also different types of encounters. There are areas where you are alone, areas where you have a support, and areas with other characters who you must protect while they are somewhat unhelpful to you. These are well incorporated into the story, as early on, Ellie is unknown and not given any weapons. Her presence on levels is not very helpful, and the gameplay helps to contribute to the player’s slight resentment. Eventually she gets a rifle and starts helping you, which makes the player appreciate her more. Other interesting levels include the first level, where you play as Joel’s daughter on the night the outbreak gets out of control. This is also the first big twist (spoilers ahead), as she is unceremoniously killed once you finish the level, taking a page out of Game of Thrones‘ script. This makes you pretty sympathetic with Joel’s character as you feel his helplessness, after all, you were just controlling his daughter and there was nothing you could do to save her.

Other interesting levels include one where you have to avoid a sniper, sneak around with very limited cover, dispatch men as they charge your position, all while advancing on the sniper as you slowly run out of ammo and materials. Then you take the sniper position and cover the advance of your friends as more enemies swarm them. There’s also a situation where you accidentally trigger a trap meant for zombies and have to protect Ellie while hanging upside down from your ankles.

As I’ve stated, the story benefits well from the integration with the gameplay. But the storytelling itself is one of the best cinematic experiences I’ve seen. It changed how I imagined a videogame could tell a story. The voice acting creates emotional and broken characters who you want to see triumph. And while the gameplay helps to emphasize the desperation and difficulty the characters face, the story is brutally dark in its outlook, constantly putting the characters in harsh situations or even killing them off. Joel’s difficulty in making himself emotionally attached to anyone after the death of his daughter is explored really well. Additionally, the sound design and music is also excellent.

But of course, the most interesting part of this game was the ending. Joel and Ellie go through a lot in their adventure. They lose a lot of friends, and they are hunted by people of all sorts. Nonetheless, if you take the gritty realism of the game seriously, you murder dozens of people over the course of the game. These others are often pretty gross people. In Pittsburgh, they are set on by “hunters” who try to ambush them. You then proceed through several levels and likely kill about 30 people. Is this proportionate? Is this ok because it’s a videogame? It’s not like you have much choice, even if you sneak by people, you’ll still have to take out a lot of others, all of whom will kill you on sight. But towards the end of the game, Joel is injured, and you have to play as Ellie to try and save him. Again, Ellie is trapped and has to fight her way out. She’s faced with being captured, possibly raped or eaten by cannibals, so anyone she kills is probably justified, but it’s pretty dark.

Finally Joel and Ellie make it to Salt Lake City and find the Fireflies (the resistance). Of course, the Fireflies believe they can create a vaccine for the zombie infection…which they would need to kill Ellie to obtain. Upon hearing this, Joel cannot bear to lose the one person he has finally allowed himself to care about, and fights his way back to Ellie. It’s possible to do this level while only killing a couple Fireflies (but you always kill their leader at the end). I was not great at stealth, so I ended up killing about 20. Mostly with the flame thrower. Joel takes Ellie back to his brother’s compound, and lies to her about the Fireflies when she wakes up, saying they didn’t need her help and they couldn’t find a cure.

Joel isn’t a hero. Yet his actions are at least understandable to the player and we’re left wondering what we would have done in a similar situation. And while it’s uncertain whether the Fireflies could have found a cure, they were not interested in Ellie’s consent or buy in; Marlene (the leader of the Fireflies) was Ellie’s friend and ordered her killed for the greater good. Of course, Joel didn’t ask Ellie what she wanted to do either, he just lied to her. And having already killed Marlene perhaps he felt he couldn’t go back even if Ellie was willing to sacrifice herself. Ellie is also only 14, so should she have the ability to make this decision? It would be questionably ethical to let a teenager make such a decision today, but who knows what rules to apply in the apocalyptic world of The Last of Us. This ending is remarkable and differs from the videogame tropes we are used to seeing. It is truly ambiguous, and emphasizes there are no heroes and villains, there are just people trying to survive.

In the sci-fi novel Ready Player One, there’s a proposed technology that would allow you to play a film as a first person character in virtual reality. The hero plays through both Wargames as Matthew Broderick’s character and Monty Python and the Holy Grail as King Arthur. While amusing for the audience, this would seem to a highly limited and uncreative use of such VR technology. After all, art made for a certain medium is probably best in that medium; a first person VR cinematic experience would probably be much better if the scripting and events were made specifically for a VR platform.  The Last of Us is a real life example of this science fiction concept: a story-driven experience with many aspects of a film, yet tailor made for the videogame medium. It isn’t the first “movie as a videogame” but it is the most impressive exercise in expanding how interactive stories are told. It is transformational and is changing the way we consume media; there’s no longer a stark difference between a long YouTube video, a TV series, and a feature film. Netflix hosts all kinds of shows from Comedians in Cars Getting Coffee (about 15 minutes an episode), to Ken Burns’ The Vietnam War, which is 10 episodes ranging from 82 to 114 minutes each. The future will include the telling of stories in many genres and media, and I’m excited to see how videogames continue to contribute to that storytelling.

2018 Predictions

Untestable knowledgeable cannot be scientific.  To avoid the problems of retroactively placing events into your narrative of the world, predictions must be laid out before events happen. If you try to use your model of the world to create testable predictions, those predictions can be proven right or wrong, and you can actually learn something. Incorrect predictions can help update our models.

This is, of course, the basis for the scientific method, and generally increasing our understanding of the world. Making predictions is also important for making us more humble; we don’t know everything and so putting our beliefs to the test requires us to reduce our certainty until we’ve researched a subject before making baseless claims.  Confidence levels are an important part of predictions, as they force us to think in the context of value and betting: a 90% confidence level means I would take a $100 bet that required me to put up anything less that $90. Moreover, it’s not just a good idea to make predictions to help increase your knowledge; people who have opinions but refuse to predict things with accompanying confidence levels, and therefore refuse to subject their theories to scrutiny and testability, must be classified as more fraudulent and intellectually dishonest.

First let’s take a look at how I did this past year, and see if my calibration levels were correct. Incorrect predictions are crossed out.

Predictions for 2017:

World Events

  1. Trump Approval Rating end of June <50% (Reuters or Gallup): 60%
  2. Trump Approval Rating end of year <50% (Reuters or Gallup): 80%
  3. Trump Approval Rating end of year <45% (Reuters or Gallup): 60%
  4. Trump 2017 Average Approval Rating (Gallup) <50%: 70% (reference)
  5. ISIS to still exist as a fighting force in Palmyra, Mosul, or Al-Raqqah: 60%
  6. ISIS to kill < 100 Americans: 80%
  7. US will not get involved in any new major war with death toll of > 100 US soldiers: 60%
  8. No terrorist attack in the USA will kill > 100 people: 90% (reference)
  9. France will not vote to leave to the EU: 80%
  10. The UK will trigger Article 50 this year: 70% (reference)
  11. The UK will not fully leave the EU this year: 99%
  12. No country will leave the Euro (adopt another currency as their national currency): 80%
  13. S&P 500 2017 >10% growth: 60%
  14. S&P 500 will be between 2000 and 2850: 80% (80% confidence interval)
  15. Unemployment rate December 2017 < 6% : 70%
  16. WTI Crude Oil price > $60 : 70%
  17. Price of Bitcoin > $750: 60%
  18. Price of Bitcoin < $1000: 50%
  19. Price of Bitcoin < $2000: 80%
  20. There will not be another cryptocurrency with market cap above $1B: 80%
  21. There will not be another cryptocurrency with market cap above $500M: 50%
  22. Sentient General AI will not be created this year: 99%
  23. Self-driving cars will not be available this year for general purchase: 90%
  24. Self-driving cars will not be available this year to purchase / legally operate for < $100k: 99%
  25. I will not be able to buy trips on self-driving cars from Uber/Lyft in a location I am living: 80%
  26. I will not be able to buy a trip on a self-driving car from Uber/Lyft without a backup employee in the car anywhere in the US: 90%
  27. Humans will not land on moon by end of 2017: 95%
  28. SpaceX will bring humans to low earth orbit: 50%
  29. SpaceX successfully launches a reused rocket: 60%
  30. No SpaceX rockets explode without launching their payload to orbit: 60%
  31. Actual wall on Mexican border not built: 99%
  32. Some increased spending on immigration through expanding CBP, ICE, or the border fence: 80%
  33. Corporate Tax Rate will be cut to 20% or below: 50% (it was 21%)
  34. Obamacare (at least mandate, community pricing, pre-existing conditions) not reversed: 80%
  35. Budget deficit will increase: 90% (Not if you go by National Debt increase January to January)
  36. Increase in spending or action on Drug War (e.g. raiding marijuana dispensaries, increased spending on DEA, etc): 70% (hard to say: Rohrbacher Amendment, FY2018 DoJ changes)
  37. Some tariffs raised: 90% (reference)
  38. The US will not significantly change its relationship to NAFTA: 60%
  39. Federal government institutes some interference with state level legal marijuana: 60%
  40. At least one instance where the executive branch violates a citable civil liberties court case: 70% (I made this too broad as I can cite Berger v New York and the NSA violates it every day)
  41. Trump administration does not file a lawsuit against any news organization for defamation: 60%
  42. Trump not impeached (also no Trump resignation): 95%

Sports

  1. Miami Heat do not make playoffs:  95%
  2. Miami Heat get top 6 draft pick: 60%
  3. Duke basketball wins 1 game or more against UNC: 80%
  4. Duke basketball makes it to Round of 32 in NCAA Tournament: 90%
  5. Duke basketball makes Final Four: 50%
  6. Duke basketball does not win NCAA tournament: 80%
  7. Warriors or Cavs will win the NBA title: 60%
  8. Lebron James will not be highest paid NBA player during 2017-18 season: 70%

Personal

  1. Employed in current job:  90%
  2. I will have less than 300 Twitter followers: 60%
  3. I will change my registered party from Republican to Libertarian: 70%
  4. I will have authored > 14 more blog posts (not just on this blog) by June 30, 2017: 90%
  5. I will have authored > 30 more blog posts (not just on this blog) by December 31, 2017: 80%
  6. michaelelgart.com to have >3,000 page loads 2017: 70%
  7. These predictions are under-confident: 70%

I missed all the ones I marked as 50% confident, but I’ve realized that 50% predictions do not convey any information. I could have also listed the predictions as simultaneously saying that there was a 50% chance the exact opposite of the statement occurred, so actually, I got exactly half of them right, and I will always get exactly half of them right. This makes the category completely useless, and so I have decided to avoid posting any predictions of exactly 50% accuracy for next year.

In the other categories:

  • Of items I marked as 60% confident, 11 were correct out of 13.
  • Of items I marked as 70% confident, 8 were correct out of 9.
  • Of items I marked as 80% confident, 10 were correct out of 13.
  • Of items I marked as 90% confident, 6 were correct out of 8.
  • Of items I marked as 95% confident, 3 were correct out of 3.
  • Of items I marked as 99% confident, 4 were correct out of 4.

2017 Predictions

This doesn’t look that impressive or well-calibrated, although one point I will make is that one of the 90% confidence predictions I missed was a personal goal to blog more. I only missed this by one blog post, and it makes sense that I was overconfident in it. Taking that one out, my 90% predictions come in at 87.5%, which is pretty good.

I did better than I should have on my 60% confidence predictions. In retrospect, predictions about the number of Twitter followers I would have, and about Trump’s approval rating were really under-confident (affected my 70% predictions as well). I severely cut the number of tweets on my personal twitter account in favor of one with more anonymity, and Trump never really recovered from his initial approval ratings, information I had pretty readily available. Additionally, my 60% confidence that Bitcoin’s price would be above $750 seems woefully incorrect, and it’s clear in this case, that I really had no idea what Bitcoin was going to do.

Predictions for 2018:

World Events

  1. Trump Approval Rating end of year <50% (Gallup): 95%
  2. Trump Approval Rating end of year <45% (Gallup): 90%
  3. Trump Approval Rating end of year < 40% (Gallup): 80%
  4. US will not get involved in any new major war with death toll of > 100 US soldiers: 60%
  5. No single terrorist attack in the USA will kill > 100 people: 95%
  6. The UK will not fully leave the EU this year: 99%
  7. No country will leave the Euro (adopt another currency as their national currency): 80%
  8. North Korea will still be controlled by the Kim dynasty: 95%
  9. North Korea will conduct a nuclear test this year: 70%
  10. North Korea will conduct a missile test this year: 95%
  11. Yemeni civil war will still be happening: 70%
  12. S&P 500 2018 >10% growth: 60%
  13. S&P 500 will be between 2500 and 3200: 80% (80% confidence interval)
  14. Unemployment rate December 2018 < 6%: 80%
  15. Unemployment rate December 2018 < 5%: 60%
  16. WTI Crude Oil price up by 10%: 60%
  17. Price of Bitcoin > $10,000: 70%
  18. Price of Bitcoin < $30,000: 60%
  19. Price of Bitcoin < $100,000: 70%
  20. Lightning Network available (I can complete a transaction on LN): 80%
  21. Drivechain development “complete”: 70%
  22. Drivechain opcodes not soft-forked into Bitcoin: 70%
  23. No drivechains soft-forked into existence: 95%
  24. US government does not make Bitcoin ownership or exchange illegal: 90%
  25. Self-driving cars will not be available this year for general purchase: 95%
  26. Self-driving cars will not be available this year to purchase / legally operate for < $100k: 99%
  27. I will not be able to buy trips on self-driving cars from Uber/Lyft in a location I am living: 95%
  28. I will not be able to buy a trip on a self-driving car from Uber/Lyft without a backup employee in the car anywhere in the US: 90%
  29. Humans will not be in lunar orbit in 2018: 95%
  30. SpaceX Falcon Heavy rocket will attempt to launch this year (can fail on launch): 95%
  31. SpaceX will bring humans to low earth orbit: 70%
  32. No SpaceX rockets explode without launching their payload to orbit: 60%
  33. Mexican government does not pay for wall: 99%
  34. Border wall construction not complete by end of 2018: 99%
  35. Some increased spending on immigration through expanding CBP, ICE, or the border fence: 80%
  36. No full year US government budget will be passed (only several months spending): 90%
  37. US National Debt to increase by more than 2017 increase (~$500B): 70%
  38. Increase in spending or action on Drug War (e.g. raiding marijuana dispensaries, increased spending on DEA, etc): 70%
  39. Some tariffs raised: 90%
  40. The US will not significantly change its relationship to NAFTA: 70%
  41. Federal government institutes some interference with state level legal marijuana: 70%
  42. Trump administration does not file a lawsuit against any news organization for defamation: 90%
  43. Mexican government does not pay for wall 99%
  44. Trump not removed from office (also no Trump resignation): 95%
  45. Democrats do not win control of Senate: 60%
  46. Democrats win control of House: 60%

Sports

  1. Miami Heat make playoffs: 80%
  2. Miami Heat do not make it second round of playoffs: 80%
  3. Duke basketball wins 1 game or more against UNC: 90%
  4. Duke basketball makes it to Round of 32 in NCAA Tournament: 90%
  5. Duke basketball does not make Final Four: 80%
  6. Duke basketball does not win NCAA tournament: 95%
  7. Warriors or Cavs will win the NBA title: 60%
  8. Steph Curry will be highest paid NBA player during 2017-18 season: 60%

Personal

  1. Employed in current job:  90%
  2. I will vote this year in the general election: 80%
  3. I will have authored > 12 more blog posts (not just on this blog) by June 30, 2018: 90%
  4. I will have authored > 25 more blog posts (not just on this blog) by December 31, 2018: 80%
  5. I will have read 6 additional books this year: 80%
  6. These predictions are under-confident: 70%

Python Partition Calculator

I had been looking to do a little bit more hobby-coding, and I came across this simple math problem which can be solved with a cool recursive Python script.

A partition is a concept in number theory where a positive integer is written as a sum. For example, the only partition of 1 is (1). 2 has (2) and (1+1). 3 has (1+2), (1+1+1), and (3), and so on. Because it’s a sum, order is not important.

The problem of figuring out partitions is not difficult, but it is time-consuming and repetitive once you go beyond calculating all partitions for 4 or 5. Something that makes it a good candidate for automation. It also can be done with some recursion.

The first thing that needs to be done is a recursive call to calculate all the combinations of numbers that would form a partition. I’m going to return a list of lists, where each sublist is a partition. The obvious part to take care of first is the base case:

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])

Next, let’s take a look at when the partition_goal is some number larger than one. The first thing we’d need is to add a list consisting of just that number:

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])

Now we need to loop over all the cases where the lists are more complicated. Let’s take 3, because it’s pretty simple. Once we’ve added the single item list [3] in the step above, we need to add the integer 1 to all lists that add up to 3 – 1, the integer 2 to all lists that add up to 3 – 2 and so on.

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])
        for i in range(1,partition_goal):
            for j in recursive_partition(partition_goal - i):
                j.append(i)
                return_list.append(j)
    return return_list

So for each of the numbers in the i range, we are adding that number to every list we can create recursively (j) where that list sums to partition_goal – i. Lastly, we need to call our recursive method, and then remove all the sublists which are identical when unordered ([1,1,2] and [1,2,1] are just one partition of 4). We do this using the Counter module.

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])
        for i in range(1,partition_goal):
            for j in recursive_partition(partition_goal - i):
                j.append(i)
                return_list.append(j)
    return return_list

list_of_lists = recursive_partition(n)

counted = Counter(tuple(sorted(entry)) for entry in list_of_lists)

print(list(counted.keys()))

The variable counted actually gets a dictionary Python object, so I turned it into a list in the print statement. The keys of a Counter are tuples, so the end result is a list of tuples where every tuple is a partition. Lastly let’s make some interface changes so we can take command line arguments or ask the user for input.

from collections import Counter
import sys

n = 1
# partition goal
if len(sys.argv) > 1:
    n = sys.argv[1]
else:
    n = int(input("What number do you want the partitions for?"))

#returns a list of lists. Each sublist sums to the partition_goal 
def recursive_partition(partition_goal):
    return_list =[]
    if partition_goal==1:
        return_list.append([1])
    else:
        return_list.append([partition_goal])
        for i in range(1,partition_goal):
            for j in recursive_partition(partition_goal - i):
                j.append(i)
                return_list.append(j)
    return return_list

list_of_lists = recursive_partition(n)

counted = Counter(tuple(sorted(entry)) for entry in list_of_lists)

print(list(counted.keys()))

And remember this is Python 3 notation. You can find this little project on Github here.