On Set Collecting

When I hear the word ‘set’, the first thing I think of is the computing data structure, and then the mathematical construct that that data structure is trying to model. Essentially, a set is an unordered collection of distinct objects. I’d probably then think of the Egyptian deity before thinking of the card game, or failing at a contract in bridge. That said, we recently had some interesting discussions about the card game over lunch at work.

The game consists of a deck of 81 distinct cards which each show a number of shapes. Each card has four attributes, and each of these attributes can take on three values – number of shapes (one, two or three), colour (red, purple or green), shading (shaded, striped or unshaded) and shape (diamond, rounded rectangle, ‘S’).

Initially, twelve cards are dealt to the table; players compete in real-time to identify a set of three cards where, for each attribute, the cards are either all the same or all different. The player collects these cards, and the dealer replenishes the cards on the table.

It is possible that no set is possible with twelve cards. In physical games, the dealer will, after a while, deal three more cards to the table if no one can identify a Set. We were playing on an app, though; this app waits for players to claim that there is no set available, and penalises players if they make an erroneous claim. More often than not, even though all of us were looking carefully at the board, we were too quick to declare no-set with 12 cards. However, we had one round where even with 15 cards (after one declaration of no-set), no one found anything. After a long while, someone pressed the no-set button, and indeed there wasn’t a set!

After the game, discussion turned towards finding the maximum number of cards where no set was possible. We quickly settled on 16 as a lower bound; this is possible if you only use two of the values for each of the four attributes (e.g. by throwing out all cards that have three symbols, are red, are shaded or are diamonds). Now it becomes impossible to perform matches along any attributes being different, since you need one occurrence of each of the three values; also, because cards are unique there is no set of three cards where all four attributes are the same (that would be three copies of the same card). This arrangement has 2^4 = 16 cards.

Going beyond this is tricky, mainly because the number of possible groups of cards you have to pick from is large. There are 81 ways of selecting the first card, and 80 ways of selecting the second. The third would have 78 ways, since there is one specific card that won’t go with the first and second. However, later on you can’t just deduct one card for each already selected card; for a simple counterexample, suppose I have already selected:

  • (1) one red shaded diamond
  • (2) one green shaded rectangle
  • (3) one green shaded S

Now suppose I try and add the card (4) with one red shaded rectangle. This means that the card with one purple shaded rectangle would now become ineligible for selection, because it would form a set with (2) and (4). However, we have already eliminated this card from consideration, because it would form a set anyway with (1) and (3).

I turned to writing a quick program here. This is a standard algorithm based on depth-first search.

  • Each card is represented as a vector with four components.
  • There is an initial set of 81 vectors created.
  • To guide our search, whenever we consider adding a card to a working set, we iterate over the elements of the existing working set and determine which cards would, together with the new card, create a set. This relies on an observation that for any pair of (distinct) cards, there is one and only one card that would form a set with the first two. We then prune these set-creating cards from the search tree.

This found sets of size 17 quite quickly, but knowing that the bound was 20, I knew that wasn’t good enough. There were several implementation tricks that I used to help speed up the search.

  • This search is easily parallelisable; each branch of the search tree may be explored in parallel. A simple implementation (and what I used) could rely on Java’s parallel streams when doing the recursion, for instance. The orchestration around keeping track of the best answer needs a few small changes to be thread-safe, of course.
  • If the goal is merely to find some set of size 20, then we can exploit the symmetry of the problem and fix the first card to be any card (I used 0,0,0,0), since any cap set could be re-expressed as one that contains 0,0,0,0 by permuting the assignment of attributes to variable values. There may be more clever symmetry to exploit here than what I did.
  • Computing the last element of a set involves a bunch of jumps, branches and math; the result of this computation is deterministic, and can be cached so that it can be reused along different branches of the search tree. There’s probably something more clever I can do regarding overlapping sub-problems (this improves the runtime only by a constant factor).

This was sufficient to get the tool to spit out many sets of size 20, though I unfortunately didn’t churn through every possible selection, so this doesn’t show that 20 is an optimum.

Notes from a Nervous Engineer (2019 Q1 Review)

I think the first time I came across the concept of a scarcity mindset (where one approaches problems believing resources are finite) when I was around 14 or so. This was in The 7 Habits of Highly Effective People. To quote Covey:

Most people are deeply scripted in what I call the Scarcity Mentality. They see life as having only so much, as though there were only one pie out there. And if someone were to get a big piece of the pie, it would mean less for everybody else.

Covey recommends its counterpart, the abundance mindset, which is the idea that there are enough resources out there for everyone. That said, I don’t buy in to the idea of abundance being superior, because resources and opportunities often are scarce. I’d bring in the Bruce Lee “I fear the man who has practiced one kick 10,000 times” quote here; bearing scarcity in mind forces prioritisation, and that if done well is really useful. This may be dangerous, but I’d hazard that scarcity can lead to fear that one is stagnating. This, if managed well, can drive one to, to use Covey’s terms, aggressively “sharpen the saw” (pursue self-improvement) as well.

There are sides of the scarcity mindset that are certainly dark. There is a danger of casting things that are not zero-sum games as zero-sum games. Aggressively focusing on scarcity can lead to excessive stress and blind short-term optimisation (manifesting in things like money dysmorphia as described in this Guardian article). I’m also somewhat guilty of this, but it can lead to hoarding. That said, in my experience a scarcity mindset is often unfairly tarred and feathered – it indeed can often be dangerous, but it has its uses.

Software Engineering

Things changed direction; I expected to move off AtlasDB, but instead became the tech lead (admittedly with a bit of dithering and some convincing from other storage experts – and a few non-storage ones too). My responsibilities have changed somewhat in that I have been spending more time maintaining context and reviewing code. I don’t think there are benchmarks, but I suspect the amount of individual development work that I do is still high relative to other TLs (in any case it’s a spectrum – I’ve worked with one in the past who did more work than I did).

I also got started on studying Designing Data-Intensive Applications after recommendation from some engineers whom I respect. Having spent almost two and a half years on AtlasDB, most of the material is not particularly new to me – that said, this would have been an excellent read when I just started on the team. I’d recommend the book for people working with distributed systems (even if they’re not necessarily working directly on distributed systems – e.g. if doing support).

Finances

With Brexit looming, the pound has been extremely volatile. I was a bit of an uneasy Remainer during the 2016 referendum. In any case, the way things have panned out since has sent me very firmly in the Remain direction now. I’d say my exposure to sterling cash is at relatively low levels. I tend to be somewhat risk-averse, and although GBP is probably undervalued, the danger of no-deal is there.

I haven’t been tracking the markets very closely; from what I remember things went up in January (after getting smashed at the end of December) and then have mostly gone sideways. It’s also coming to the end of the 2018/2019 tax year; I’ve seen the ISA ads around, though not so many for ‘use your capital gains allowance’ which is something I should look at this week.

Expenses-wise, Q1 has been awkwardly high; some of this is because of one-off expenses for activities that’ll actually take place in Q2 (travel and holidays). My overall savings rate is still decent, as income was higher because of bonuses.

Travelling

I had just two trips out of the UK this quarter, and interestingly both were to visit specific friends in the context of specific events. I went back to Singapore in January for Isaac’s wedding – that was a very short trip as I only had close to a day or so to actually spend with family. The other trip was to Zurich for a weekend trip in February to meet Stan.

Hobbies

The logic puzzle train has been chugging along. I took part in most of the WPF Sudoku and Puzzle GPs, though I missed one round of the puzzles as I was in Zurich that weekend. I’ve always been stronger at sudoku and it shows – I’m on overall rank 60/774, with rankings 82/599, 139/598 and 47/541 in the three rounds. I thought round 2 went pretty well, though I broke an easy Classic Sudoku and, more significantly, a (I think still easy) Braille Sudoku that was worth a lot of points. Round 3 was good – all three of the ‘weird’ variants at the end were disposed of quickly. For puzzles I’m on overall 167/557, with rankings of 102/434 and 93/405 in the two rounds I participated in. We’ll see how Sudoku Round 4 goes, though I think it went poorly for me.

I’ve been reading a fair bit too – some readers may recognise that the title of this post is inspired by Matt Haig’s Notes on a Nervous Planet. I first came across his earlier work Reasons to Stay Alive randomly in a Popular bookshop in Singapore late last year, when waiting to meet a friend. I found the book pretty captivating, though I didn’t buy it then – instead, I placed an order for the book to be delivered to me in London. Both of the books held my interest; the former was raw and pretty compelling, while the latter is more familiar territory for me and I think I could to some extent identify with his perspectives.

I also found James Clear’s Atomic Habits to be a very practical read; I’ve been following his emails for a while. I appreciated the principled approach the book presents. He first establishes that things that become habits tend to be obvious, attractive, easy and satisfying; he then explores how to influence behaviours to increase or decrease how much they show each of these traits.

General Thoughts

It’s been a stressful quarter; there has been a lot of change at work, unease in my financial situation, and discontent with things in general. Perhaps this is something worth thinking about; there’s a passage near the end of Notes on a Nervous Planet on diminishing returns, where Haig observes that many people have tendencies to repeatedly move the goalposts when successful. For me, “be good at math” became “top my class in math”, then “top my cohort in high school in math” (I failed this one, though unexpectedly got Physics instead), then “get a first at Imperial”, then “get the first at Imperial”… “with a 90 average”… “while running a club and working part time 20 hours per week”. Similarly, “be a good dev”… can quickly spiral into “with patents”, “building large features”, “be a principal engineer” and so on. It’s important to maintain perspective as to whether the repeated escalation of these goals is something one really wants to do.

There’s usually a song I associate with each quarter. This time around I’ve been listening a fair bit to Drunk Me by Mitchell Tenpenny. He’s a country artist and I don’t listen to country very much, but this is pretty much a straightforward pop song. There are some awkward metaphors in there, but generally I find the production pleasant, and the A4s he hits in the chorus are nice enough. The message involves giving up habits that are likely to lead the singer back to his ex, which is a pretty logical response.

I’ve been sober
‘Cause there ain’t no hangover like you girl
“Baby, can you come over?”
I always find those words at the bottom of a hundred proof

I don’t drink much alcohol, though I do drink quite a bit of coffee and chocolate. In a sense, my ‘alcohol’ would be activities or behaviours I find addictive that are likely to lead to ruin or negative consequences. This could include things like obsessive fear over how the markets are doing or how Brexit is going, or spending time procrastinating. I don’t think there is an object of spite here, unlike in the song, but nonetheless the idea that one may find value in cleaning up one’s life is something I can get behind.

Algorithmic Modelling – Achievement Hunting (Slay the Spire, Part 2)

Many modern video games feature an achievements system. Achievements are typically awarded for completing specific tasks; typically achieving all of these requires doing substantially more than just what is required to finish the game. In many cases, it’s not even possible to complete all of the achievements on one playthrough.

In a previous post, I wrote about Slay the Spire, an RPG where combat is driven by a deckbuilding mechanic. The game also features an achievements system. I finished getting 100% completion on these achievements this week – this took quite a long time. If I wanted to start from the beginning and accomplish these as quickly as possible, I would need to plan carefully. The main issue here is that achievements are not independent. For example, there are chains of achievements where the final achievement subsumes all previous ones (e.g. “have 99 block, have 999 block” or “unlock ascension mode, finish ascension 10, finish ascension 20”). Furthermore, some achievements can be achieved using the same strategy (e.g. “play 25 cards in a single turn” and “defeat a boss before it takes a turn”, which can both be achieved by building an infinite combo). Other achievements can often be significant handicaps (e.g. “beat the game with a deck that has no uncommons or rares”, “beat the game with only 1 relic”) and I thus think it’s a lot harder to combine these with other achievements.

The game is played in distinct runs, and a majority of the achievements involve performing specific feats on individual runs. We can model this by identifying strategies that unlock one or more achievements. If we try to use the fewest number of distinct approaches, this becomes what’s called a set cover problem. There are achievements A = \lbrace 1, 2, \ldots N \rbrace and strategies S = \lbrace S_1, S_2, \ldots S_M \rbrace with each S_i being non-empty and a subset of A. We also require that \bigcup_{i=1}^M S_i = A, otherwise not all achievements are achievable. The goal is to identify some set of strategies we need to deploy S' \subseteq S such that \bigcup_{s' \in S'} s' = A. Trivially, picking everything is possible, but it’s very unlikely that that’s going to be minimal.

This problem is known to be NP-hard; the decision version (does there exist a solution using k strategies or fewer?) is NP-complete. Clearly, we can obtain a solution that is worst-case exponential in |S| \times |A| by iterating through each possible subset of S, checking if it satisfies the criteria and remembering the best solution we’ve seen so far. There’s a little dynamic programming trick we can do to memoise partial achievement states (e.g. I can get to the state where I have the first 8 achievements and no others using two runs with one strategy but three with another; I’ll always pick the first). This achieves a solution exponential in |A| but linear in |S|, which is an improvement. We can also try to pre-process the input for A and S a little, by eliminating any achievements that are subsumed by harder achievements, and by eliminating any strategies that are strictly dominated by others.

If this is unacceptable, we can either try to use approximation algorithms (for example, a standard ‘greedy algorithm’ which picks the subset with the most outstanding items doesn’t always fare too poorly). We can also attempt to leverage constraint solving systems; these don’t deal with the exponentiality of the problem directly, but they often have good heuristics to deal with this.

That said, this isn’t a very good model, as some strategies are riskier to implement than others. For example, it may be theoretically possible to combine “beat the game with one relic” and “beat the game without uncommon or rare cards”, but that seems unlikely. For example, if each of these individually has a 1% chance of being completed but attempting them together has just a 0.1% chance, doing the achievements separately will take an expected 200 runs while the combined approach has an expectation of 1000.

A natural extension to this is to consider the weighted version of the problem. We change the formulation slightly, so each strategy has a weight w_s and we seek to minimise the total weight of the strategies we pick. If we assign a strategy a given probability of success p, since runs are (mostly) independent, the expected number of runs it takes to attain a successful outcome would be 1/p following standard geometric distribution results. The dynamic programming based algorithm still works if we keep track of weights instead of number of sets.

This is better, but there are still a few issues with the model. Firstly, partial successes haven’t been considered in this model; we might try a risky strategy for three achievements and fail, but still complete two of them. We could try to account for these by figuring out some kind of state transition between achievement states – it wouldn’t be a set cover problem any more. We would be building some kind of a discrete-time Markov chain on-the-fly.

Modelling this as a set cover problem also seems to imply that our algorithm is offline; that is, it formulates a strategy and then executes it. However, Slay the Spire has a significant luck element, especially if one is trying for specific achievements, and thus an offline algorithm doesn’t work so well. For example, one achievement requires “play 10 shivs on a single turn” and another “have an enemy reach 99 poison”; the cards and relics that support these are quite different, and depending on what cards are offered as the game progresses, one achievement or the other could become easy or nigh-impossible. If both achievements remain to be unlocked, it seems suboptimal to commit early on.

Algorithmic Modelling – The Game: Extreme

I had a weekend break in Zurich to meet up with a friend who works there. We often play board games when we meet, so I brought Hanabi and FUSE (very compact games, suitable for travelling – especially since I almost always travel HLO) but my friend was thinking of getting something different. We thus headed down to a game shop, and picked up The Game: Extreme (Board Game Geek).

The rules are fairly simple. There is a deck of 98 cards – one copy each of the integers from 2 to 99, inclusive. Players will have some number of cards in their hand (eight for a solo game, seven for 2 players), and play them to the table; the game ends in a loss if a player must play, but is unable to (or if all cards are played, which is a win). It is a cooperative game; players all win or lose together. The rulebook also mentions a half-win if players finish with ten cards or fewer remaining.

There are four communal piles that players can play cards to. On two of these, cards played should be numerically increasing; on the other two, they should be numerically decreasing. However, one may also go against the direction of a pile – this can only be done if the jump is exactly 10. Thus, for example, if an increasing pile has a 57 on top, one may play a 59 (increasing) or a 47 (ten less), but may not play a 49 (not increasing, and not ten less). Of course, if a player has both the 59 and 49, the player may play the 59, after which the 49 becomes legal.

One can probably write some search-based algorithm to figure out what the best possible outcome is for a given hand and individual pile, or even set of piles given some fitness function. There’s also a straightforward dynamic programming optimisation, and for certain classes of fitness functions there might be better principles one can leverage.

Players must typically play two cards on their turn, though they may play more (for example, if they have a chain of cards that involves several reverse jumps) while there are still cards in the deck; once that is emptied, they only need to play one. Once they have played all of their cards, they draw back to their hand size and play passes to the next player.

The Extreme version adds special effects to some of the number cards. These may either restrict the current player’s turn (requiring that they stop immediately, play exactly three cards, or immediately cover up the card that was played) or affect all players while they are exposed (requiring players keep quiet, play all the cards in their turn to the same pile, not do reverse jumps or only draw 1 card at the end of their turn). Apart from the stop card, all of these make the rules for playing more restrictive (and thus I’d say this is somewhat harder than the base game).

The solo game doesn’t generally seem too difficult as one can plan and execute sequences of reverse jumps without interference from others. The keep-quiet special effect no longer really matters, and the stop cards actually become positive as they allow for drawing cards back up earlier. I’m not sure how one might formulate an algorithm for determining optimal moves, but I can generally see the following principles:

  • Play the minimum number of cards needed per turn, and then draw back up. This lets you see more options, which is useful. Normally in a multiplayer game you may want to play more than the minimum to ensure that no one interferes with your plan, but in single player no one will anyway.
  • Plan and aggressively use reverse jumps. These often get thwarted in multiplayer games (you might draw a card that allows a reverse jump, but someone might need to play on the relevant pile before it gets to your turn).

Playing with more than one player gets trickier, as communication between players is permitted but precise numerical information is not. I would say things that imply precise numerical information (e.g. “I can jump this pile”) are also bad. There are edge cases which are probably acceptable (e.g. “it makes no difference to me; which of these would you prefer I play to?” with an up-65 and down-67 suggesting I hold the 66). Still, talk of “small/large jumps” and actively saying “stop” after interesting cards are played is very useful.

Cooperating well involves looking ahead to other players’ turns as well; it’s not always optimal to, on each player’s turn, individually minimise “damage” to the piles. There have been times where being forced to jump a pile by 30 or so, I’ve encouraged my teammate to play more cards there since it would be destroyed on my turn anyway. We only played with two players, but I imagine the dynamics get more interesting with larger groups.

The Game: Extreme is a very light game; while there is some minor logic involved it’s not particularly complex. It’s fairly fun and witnessing successful chains can be enjoyable; the special effect cards can also cause annoying obstacles (while blocking reverse jumps is probably the most damaging, the keep-quiet one is interesting as it changes the game for a while). It’s certainly a fun thing to play while passing time and discussing other things, and hard enough to provide a good challenge without being frustrating.

Evolving Robots to Cut Stocks: A Coding #10YearChallenge

Ten years ago, I was in high school. I had some experience with coding, mostly through computer science lessons in school; I did Computer Science HL for the IB diploma programme, which had a sizable Java component. As part of the IB programme, students need to write an extended essay, which is basically a research paper.

I worked on Application of Evolutionary Algorithms to Solve the One-Dimensional Cutting Stock Problem. There are two terms to unpack here. First, “evolutionary programming” is a biologically inspired heuristic for solving optimisation problems. The idea is that we first randomly generate a pool solutions that are feasible. We then create ‘related’ solutions by permuting the existing solutions in some way, assess their quality using a function and then replace the old population by selecting randomly from the old and new, with bias towards better solutions. In this way, the theory is that the population of solutions increases in fitness/quality over time.

Second, the “cutting stock problem” is an operations research problem in manufacturing, where raw materials are supplied in finite sizes (e.g. rolls of paper) and one needs to cut them to fixed specifications. The assumption here is that it’s not possible to glue together parts that don’t correspond to any request to fulfill one – any pieces that are too small are lost (this is called ‘trim loss’).

In hindsight this seems decently ambitious for a high-school project. I did well, and got an A (which is the highest grade for these), though I remember how long it took me to write a (in hindsight absolutely terrible) working implementation.

Implementation

The project was implemented in Java, which the IB programme focuses on in its Computer Science course.

Looking back at how my code was structured, it was rather unsurprisingly amateurish and messy. There were just four source files for the entire project, including one 700-liner. That said, there was some semblance of organisation, at least in the sense of abstraction and factoring out logical units into functions. The main loop body of the runOneIteration() method I had was just four statements that ran the major steps of the evolutionary algorithm – clone the current generation, perform mutation, evaluate the new generation’s fitness, select the next generation.

My Java knowledge was poor at the time. Some of this was not knowing about the possibility of using external libraries – I had my own implementation of deep copying objects. Some of this wasn’t even external libraries; I had implementations of median-of-three quicksort and the Fisher-Yates shuffle, which seems unnecessary (these are Collections.sort() and shuffle() respectively).

I seem to have had near zero knowledge of the Collections APIs. I also used a lot of primitives and arrays of primitives, which made things hard to read. This could be argued as having better performance (by avoiding function calls, boxing when performing math and so on), but there wasn’t such a discussion in the paper or comments anywhere, so I’d chalk it up to lack of knowledge.

For an example, we can look at the implementation of a deep-copying routine I wrote back then.

If I was to review this code, there were quite a few things I’d highlight:

  • I’m not sure Java serialization and deserialization is the best way to do this. The general serialize/deserialize approach makes sense, but there are more user-friendly and performant serialization libraries out there. I’d probably use Jackson now.
  • There are no tests! Amazingly I didn’t have any automated tests for my implementation at all. (Contrast with MCMAS, where one of the first things I did when working on that codebase was introducing an automated test framework.)
  • Swallowing exceptions and returning a potentially null object seems like an error-prone pattern. I’d prefer to have clients check for errors by catching (possibly unchecked) exceptions, rather than checking if the reference is null.
  • The ObjectOutputStream can be leaked if writeObject() or flush() throws. We should use something like try with resources (though at the time that didn’t exist – in that case we would put close() in a finally block).
  • The class is a utility class, but it has a public constructor (default in Java). It’s silly, but someone could instantiate instances of this class, which shouldn’t be allowed.
  • Using Object directly for the return type can be troublesome, especially since we know the object that’s being returned has the same type as the input.
  • The reason we have to assign null to obj on line 3 is because it may not be assigned when referenced on line 21. If we wanted to keep this contract (don’t throw, and return null on failures) we can avoid this by returning in.readObject() directly in 13 and null directly in the catch blocks, which is probably more readable.
  • This is not a fair criticism in 2008 (as the feature in question was introduced in Java 7), but nowadays if we want to handle different types of exceptions in the same way we should use the multi-catch syntax to be concise.

Algorithms

The cutting stock problem is difficult (it’s in FNP, and the decision version of “is there a better solution than some number of stocks” is NP-hard), hence heuristic-based algorithms like this seem reasonable. The mutations I used then were swaps, which probably makes sense for this problem as it preserves feasibility (the orders can’t be changed).

The algorithm was probably a bit too greedy in terms of how much it prioritised already-good solutions. I’m not sure if I had heard of the words simulated annealing then, but I interestingly seem to have suggested something like it when discussing possible future work! Those words weren’t mentioned anywhere in the essay and the paragraph in question has no references, so it might well have been a thought from first principles.

The approach of selecting stocks with high wastage to swap pieces from is initially effective in reducing trim loss; yet, this also caused the algorithm to converge at local optima frequently. Conversely, selecting stocks with low wastage to swap pieces from seems to encourage the algorithm to search for the global optimum, though this may require significant amounts of time. A conditional approach, more biased towards swapping stocks with more wastage at the beginning than at the end might prove effective.

Documentation

The obvious difference was that this was written in Word while nowadays I’d almost certainly use Latex for a document like this. Some of the formulas were awkwardly typeset, and rather frustratingly there wasn’t a consistent theme to the diagrams (I see Arial, Calibri, Times New Roman and LM Roman!)

There were some fair points that I made then; for example, the algorithm is flexible with resource constraints, in that terminating at any point will spit out a feasible solution, and much of the gain is obtained early on.

Conclusion

More generally, it’s good to see that things have changed, and that there has been real and significant improvement. I’m often frustrated about my learning and development as an engineer, and in the moment it’s often hard to see any improvement. Yet, viewed over a larger time-scale, across the Imperial degree (shout-out to Software Engineering Design), multiple internships and a battery of research papers and patentable work, things have improved quite a fair bit, which is somewhat gratifying.

Boundary of Lines and Gradients

In The 7 Habits of Highly Effective People, Stephen Covey introduces the notion that things we encounter in life may be classified as irrelevant or relevant to us (whether they are in our circle of concern), and then of the things that are relevant, whether they are things we can influence (hence circle of influence).

This idea is introduced in the context of arguing that highly effective people are proactive. The book claims that there’s a risk that one spends too much time focusing on things within one’s circle of concern, but external to one’s circle of influence. By definition, these can’t be meaningfully changed by one’s actions, so one logically should not focus on these; yet, there is a tendency for one to index too heavily on these, perhaps because they are worrying to look at.

I remember some concern over my work visa application process when I was still studying at Imperial; at the time, the UK Migration Advisory Committee was actively reviewing the Tier 2 scheme with a specific focus on post-study work. Obviously, that was within my circle of concern, but was out of my circle of influence. I was quite concerned about it then, and spent a good amount of time researching how Tier 2 visas looked like and what changes might have occurred.

I also took positive action to hedge these risks (which was within my circle of influence). This included investigating opportunities elsewhere, restricting my internships to places that were willing and able to sponsor Tier 2 visas, and trying to be “so good they can’t ignore you”. Looking back, I think the hedging was valuable; poring over visa rules was less so.

So far, so good. However, there is some difficulty in applying this idea. Two challenges I’ve thought about recently are accurately identifying the boundaries of one’s circle of influence, as well as figuring out when one should exercise one’s ability to influence things in one’s circle of influence.

In terms of identifying boundaries, one may incorrectly identify things as within one’s circle of influence, owing to overconfidence or excessive optimism – a classical example being what other people, especially other people we don’t know choose to do. The inverse would be identifying things as outside from fear; I’ve done this before in terms of some aspects of how I’d been investing my free time (in particular, a commitment to over-studying).

Errors in both directions may also stem from ignorance; for example, one may (correctly) think that the spot GBPUSD exchange rate is mostly not in one’s circle of influence, and then extend that to say that the number of pounds one must pay for a known upcoming dollar expense is out of one’s circle of influence (wrong; forward contracts and other hedging methods exist).

Some authors make further distinction between things one can influence and things one can control, which usually implies personal ability to decide the outcome (for example, one can control one’s own decisions, but can probably only influence another person’s behaviour). I find this a fairly useful distinction to make.

We then move to figuring out if things within our circle of influence are actionable. They can be, but aren’t always. For example, I’ve thought about how to insulate my portfolio from the storms of Brexit and the recent market turbulence. On one hand, my asset allocation is clearly within my circle of influence. I can sell everything and go to cash (or, if one’s worried about the pound, to the US dollar or yen). I’d say it’s even stronger than that – it’s something I can directly control in that I know I am able to execute the relevant transactions if I want to.

Yet, I don’t necessarily know how changes in my asset allocation will affect the returns I will get and the risk I’ll be taking on. I can make some estimates based on past distributions, but those will suppose that at least to some extent past performance is indicative of future returns; there might be ‘black swans’ which can mess with this and by definition are not foreseeable (and thus outside of my circle of influence). In a sense, I know I can change things, but I don’t know as well what impacts my changes will actually have; there is also a cost to implementing changes (both in terms of tax and dealing fees). Making repeated portfolio changes that individually make sense if one thinks one can significantly influence returns or risk could turn out being very costly.

A variant of this is that we may loses sight of actions we should probably take that contribute towards progress on a goal in our circle of concern, even if we (correctly) identify it as mostly outside our circle of influence. This might include the broader state of the economy, environment or public health – it’s probably reasonable to think of these as not things we can directly influence, but that shouldn’t be a reason to ignore them altogether. These behaviours should be accounted for by related things within our circle of influence, possibly at a finer resolution (e.g. “I will continue to work, earn, invest and spend” because I am concerned about my own personal economy and living standards), but they might not necessarily be.

I agree that we should focus our energies on things that we can influence; that said, we need to be careful to identify these correctly (or for things that are large, identify what we can influence), and also to be aware that being able to influence something doesn’t mean we should.

Report Cards (2018 Review)

We are just over an hour into 2019 where I am (Singapore), though it is still 2018 in the UK. For me, the highlight of the year was probably receiving the VCLA Outstanding Masters’ Thesis award in August; the worst part of the year would probably be around April, when I had a month or so of doing primarily reactive tasks and managing technical debt. Nonetheless, every year will have positive experiences (hopefully) and negative ones as well; I’d say my main takeaway from 2018 is that optimisation can be dangerous if one picks the wrong variables.

I set some targets at the beginning of the year. While setting targets without subsequently revisiting them can already spur improvement, it’s useful to consider how one has performed as it informs drafting next year’s goals (in particular, figuring out what is realistic, and what would be too comfortable). The grading system I’m using here is similar to the OKR system – each task receives a score between 0.0 and 1.0, and a straight success (with no extensions or bonuses) scores 0.7. For quantifiable tasks, I usually do a pretty straightforward linear interpolation with zero at 0.0, and 10/7 of the target at 1.0; usually a 1.0 means that the goal either wasn’t ambitious enough, or the relevant area became more important during the year.

A1: Software Engineering: 0.5

Not quantitative. Progress this year, while significant, felt largely incremental (which is maybe unsurprising as I’ve been focusing on similar work in terms of distributed systems and back-end performance).

I’d say most of the “progress” here is in the form of a considerably more principled approach to pursuing performance improvements and building new features. It’s difficult to evaluate improvement in Java skills; I spent some time this year studying Java performance (especially garbage collection algorithms and concurrency). There were a few bugs I remember this year where Java Memory Model knowledge was useful, which I wouldn’t have known as well this time last year.

A2: Logic in Computer Science: 0.9

The original goal here was arguably quantitative, in that it was to present one paper at a logic conference. This was presented – see this AAMAS18 page. I decided to bump the score up from 0.7 to 0.9 as a somewhat related highlight of the year was receiving the VCLA Outstanding Masters’ Thesis award for my work on MCMAS-Dynamic. This was mostly based on past work, though I had to write up a summary of the work that had been done.

This target was intentionally not too ambitious. I do want to finish up one more paper from the thesis – I think four is about the limit of where we can take this (the third paper already had a decent amount of original content) but I don’t anticipate presenting that until possibly 2020.

A3: Innovation in Engineering: 0.7

The goal here was to get two patents in the pipeline, and this was achieved exactly. There might be a third coming from my winter hack-week project, but I prefer not to count things that aren’t done yet.

This goal was conceived as an alternative to the pull-requests goal I had in 2016, as I find a small number of substantive changes to usually be far more motivating than many smaller incremental changes. (A possible danger of this is that I might discount the value of said incremental changes too much!) I’ll probably keep some version of this in 2019, as I find this kind of innovation enjoyable and motivating.

B1: Writing and Blogging: 0.4

The goal was 52 and I think this puts me on 27; I’ll be generous and round up. It seems a weekly schedule is pretty challenging, particularly around holidays and busy periods at work. I do still want to maintain somewhat regular updates here, but a lower target (40, perhaps, to allow for some of these) could be more reasonable.

B2: Travelling: 0.3

The goal was to visit 12 countries, considering the UK as my home base. I’m writing this from Singapore, and have also visited Switzerland, Germany, Norway, Sweden and the US, so this puts me on 6. That would be 0.35 – this rounds to 0.4 by standard conventions, but I’ll round down considering how work-dependent most of these trips were. I do enjoy visiting new places and learning more about them; however spending time with friends and family is also important to me, and in some ways travel allows me to do that. I think some kind of travel-related goal is likely to feature next year, though I’m not sure yet what form that should take.

B3: Walking: 0.7

The goal was to walk an average of 10,000 steps per day. I’m at 10,131 and I can add one more to that average for every 365 steps I walk today. Bumping this to 0.8 would require 213,160 steps today, so I’m fairly confident 0.7 is right.

I commute to and from work by walking most of the time. This provides a form of exercise and also saves money on transport (tube fares in London are expensive). That accounts for around 7-8,000 steps; the rest are accumulated walking around the office, or on weekends exploring. I don’t think this was sufficient in terms of physical fitness.

B4: Music: 0.5

There is some progress; I’m able to hit Bb4 quite a bit more consistently than I used to, but B4 remains difficult and elusive. I came across Meant to Be this year and attempted to sing it – I can just about manage the song (including the female vocal line) which requires consistent Bb4; trying it at a +1 key has not worked. I would not have been able to land consistent A4s even at this time last year, so the improvement could be considered as two semitones out of three.

C1: Gross Savings Rate: 0.8

The goal was a gross savings rate (Savings Rate #1 in this post from Early Retirement Now) of 50 percent, and this ended up at 54.2 percent for this year. I think this is good given that UK taxes can be quite high. This is a difficult chord to play, as one needs to determine how to discount future utility from money put into savings and investments. I think this was slightly higher than expectations.

C2: Minimum Income Standard: 0.8

The goal was to have non-housing expenditures of at least £10,800 for the year; this reached £12,000. This may seem somewhat antithetical to C1, though the issue with savings rate is that higher isn’t necessarily better; I’d prefer a sufficient budget at SR 50% over a tight one at SR 65%. It’s also not impossible to score highly on both goals (by earning more).

D1: Communications and Maintenance: 0.6

This goal is non-quantitative. I think I’ve made reasonable efforts to keep in touch with friends from both Imperial and Singapore. For the most part this has gone well, though there have been some lapses where I haven’t been as responsive as I’d have liked, hence just under the target sounds about right.

2018 in Graphs and Charts, Part 1

When most people think of graphs, they would probably think back to mathematics lessons in middle or high school, where it typically refers to a plot of how quantities change in relation to one another. Graph sketching was for some reason a large part of the university admission process for mathematics and computer science related courses, even if many of the curves that candidates were tasked to sketch could be approached in a rather uninspired algorithmic way.

There is a looser definition, which is closer to what I’d call a chart, which is a graphical representation of data. Some people do say things like “line graph” or “bar graph” (interestingly, “pie graph” is rare).

Moving away from mathematics and data representation, a graph also refers to a glyph or character in terms of typography, leading to terms like digraph for pairs of letters that make a single sound, though I don’t think usage of the term by itself is common.

As a software engineer, there is a fourth definition – a graph is also a structure comprising a set of nodes and a set of edges that connect these nodes. This structure is very useful for modelling many things with network-like structure, such as in communications, path-finding, or reasoning about state machines. You could say the core of my Masters’ thesis about MCMAS-Dynamic was a novel algorithm for exploring certain types of graphs quickly; one of what I’d call my flagship projects at Palantir also revolves around graph algorithms.

There is a risk of shoehorning all kinds of problems as problems solvable with graphs, in this sense (I remember some jokes I had with a couple of friends at university on trees, a specific subset of graphs, applying to everything). Nonetheless, graphs are very useful. I’ll use both the computer-science graphs and the looser ‘graphical data representation’ as I recap some of the things that I did (or happened to me) in 2018.

Travel

There was quite a bit less travel this year, and you could say the destinations involved were maybe a little less exotic (though I still maintain that the trips were good). One thing this map doesn’t quite show is the frequency each route was taken (though looking at this it seems that each path was actually taken once; I’ve made two trips to Singapore, one through Frankfurt and one direct).

I think most of this is just a decrease in travel for work, which was lower than normal. Leisure travel remained about where it has generally been (a total of 32 days this year, though that does include quite a few weekends). I don’t know if this is because of Brexit making my pounds buy less meaning I’m less likely to think about travelling. This could be relevant to the US or Zurich, but not necessarily elsewhere where the cost of living tends to be lower. Writing this, I remember my restaurant-quality six-euro dinner in Croatia…

Going forward, I hope to have a more interesting graph/network in 2019. Hopefully Brexit won’t get too much in the way of that – you might think that as a Singaporean I won’t be directly affected, but I will be. The pound might depreciate, making overseas travel expensive, and the length of the non-EU queues might increase. There is also talk of the Schengen version of ESTA coming up as well.

Logic Puzzles

I joint-set one of the puzzles for Palantir’s 2018 puzzlehunt, and have also been doing quite a few logic puzzles, including sudoku; I placed pretty decently at this year’s UK sudoku championship, and a bit more weakly in the puzzle division. Considering puzzles more broadly, they can be classified into a variety of types. Sudoku probably counts specifically as its own class, but there are also more general ‘number placement’ puzzles – you might have heard of Kakuro. There are other genres – ‘loops’ like Slitherlink; ‘object placement’ like Battleship and ‘shading’ like Nurikabe, among others.

I had the impression I was substantially better at sudoku than most general puzzles (a good chunk of this might just be experience-related), and probably better at number placement too. Conversely, I always struggled a lot with spatial reasoning in school and at Math Olympiads, so I thought my skills with loops would be weak.

One of the sites that hosts these puzzle contests is Logic Masters India. They ran a series of puzzle contests in 2015 that were split by genre. They also have a rating system, to facilitate comparison of skill across contests. A player’s overall rating is an aggregation of rating events; the computation of this aggregation is a little complex, but figuring out the score at an individual rating event isn’t too hard.

  • An event has a raw score, computed from individual puzzles – raw scores are compared to determine overall ranking.
  • Define ranking score (RS) as one’s percentile performance in the contest multiplied by 10. In other words, the top contestant scores 1000, and the median contestant scores 500.
  • Define point score (PS) as the ratio of one’s score relative to the top scorer, multiplied by 1000. The top scorer thus scores 1000; someone who scored half as much as the top scorer scores 500.
  • The overall rating score is a weighted average of the two: 0.75 * RS + 0.25 * PS.

I tried out each of the contests in the set, along with a sudoku contest, and calculated my overall rating scores for each, which are reflected in the graph above. Expectedly, sudoku is strongest (experience, probably). I didn’t realise drawing snakes was considered a genre by itself, though given it is I knew I would be terrible at those as I usually approach those with mainly intuition. I don’t know what the intended standard deviation of ratings are, so it’s difficult to comment on the significance of the differences.

Stock Market

The price over time of a security is a good example of a time series. This naturally lends itself well to a line graph, with price as the vertical axis and time as the horizontal axis.

One can similarly graph the size of a portfolio; the above reflects the value of my workplace pension, re-based to 100 at the start of this year. However, this is for the most part only sampled monthly (or sometimes bi-monthly, depending on whether there were other events that made me look at my portfolio), so the resolution of the data is very limited.

This year has (and it’s good) reminded me why there is an equity risk premium. Consider that a zero-growth environment would mean a straight increasing line, as additional contributions are coming in. Hence, the small decline from January to February or stagnation in October actually refer to periods where the market went down; the steeper-than-normal gain in May and August refer to periods where the market went up. This makes a fair bit more sense if one also looks at the performance of an accumulating world index tracker.

Source: Morningstar. Disclaimer: I do hold as part of my portfolio the Fidelity World Index P fund.

As expected, prices slumped in February and October, while rallying in May and July. Interestingly, there is a rather pronounced late-March to early-April decline that isn’t reflected in our original graph. This is an artifact of sampling – the March reading was taken on the 21st of March, and the April reading on the 23rd of April, by which time prices had already mostly recovered.

Reactions to the Red Box (UK Budget 2018)

I’ve noticed that there has ended up being a string of primarily financial posts. This was not intentional, but there happened to be lots of interesting material related to finance that has come up over the past few weeks. Also, a disclaimer: I am not a financial advisor and am not offering professional financial advice. Conduct your own due diligence or seek an advisor if necessary.

The UK government announced its Budget for 2018/2019, though with the caveat that it might be subject to change in the event of a no-deal Brexit (which looks a bit more of a risk each day). I’m a UK taxpayer, and thus changes in relation to tax and relevant allowances interests me; tax is my largest expense every year. As an expatriate I don’t have recourse to public funds, so I’m less aware of the changes pertaining to benefits and universal credit. The list below is far from exhaustive; readers should consult a more detailed guide like MoneySavingExpert or even the Budget itself if they want more details, or this Which? article if they’re considering optimising their tax affairs.

Income and Take-Home Pay

  • Personal allowance has increased from £11,600 to £12,500 and the higher rate (40%) band has increased from £46,350 to £50,000.
  • National insurance thresholds have risen; the start of the 12% band has increased from £8,424 to £8,632 (by £208), while its end has increased from £46,834 to £50,024 (by £3,190).

I was aware that the Conservative manifesto had pledged to bump the personal allowance and higher rate thresholds to these levels by 2020, so this is one year early. These increases seemed fairly generous – although I will be paying more in NI (notice that £2,982 is now taxed an extra 10 percent and £208 is now taxed 2 fewer percent – in other words I’m paying £294 more) the income tax saving looks pretty good, especially in nominal terms. (Whether Brexit wrecks the value of the pound further is another separate concern.)

A separate consequence of this is that the 62% marginal band has extended to £125,000 as well, as there’s more personal allowance to lose. Regardless, the changes are certainly positive.

In general, with inflation being positive, the value of a pound decreases over time. Thus, thresholds should be increased nominally at least in line with inflation if the goal is to implement a ‘neutral’ policy. I haven’t been keeping track of the history of these levels, but the roughly 7.75% bump in the thresholds is certainly well above inflation (and hopefully above two years of inflation – since the thresholds will be frozen next year).

Other Income Sources

  • The Personal Savings Allowance remains at £1,000 for basic rate taxpayers, £500 for higher rate and £0 for additional rate.
  • The Dividend Allowance remains at £2,000 – note that dividends in a pension or ISA do not count against this limit. Dividend tax rates are unchanged.
  • The Trading and Property Allowances remain at £1,000.
  • The Rent-a-Room scheme threshold remains at £7,500.

Most things held pretty steady in nominal terms (which means they’ve gone down slightly in real terms). That said, if interest rates continue to go up the savings allowance thresholds might quickly become relevant to me (obligatory hello to Marcus). I’m considerably further from the dividend allowance threshold, though again that’s something to watch out for if the markets decide to be exuberant. I haven’t been using the other allowances, though if an opportunity comes up that could be a possibility.

Securities and Assets

  • The ISA (tax-advantaged savings account) limit remains at £20,000.
  • The Capital Gains Allowance was increased slightly, from £11,700 to £12,000. Tax on capital gains is unchanged.
  • The Lifetime Allowance for pensions was increased in line with inflation, from £1.03M to £1.055M.

Not too much to say here. The markets haven’t been so friendly so there’s certainly no extravaganza of crystallising significant capital gains this time around. To be fair, much of my gains in the 2016/17 tax year centered around massive pound weakness. ISA allowance being held where it is is a bit of a damp squib as I max it, but to be fair it is still very generous.

Consumption Taxes

  • VAT standard rate remains at 20%.
  • Air Passenger Duty (APD) remains flat for short-haul flights, but rises by RPI for long-haul flights (roughly £2 for Y, £4 for premium cabins).
  • Fuel duty is frozen.
  • Alcohol duty is frozen for beer, “most cider” and spirits. Duty on wine and higher-strength cider increases by RPI.
  • Tobacco duty increases by RPI + 2%. I don’t smoke, so don’t know too much.

Owing to how it’s calculated RPI tends to be higher – and it’s a little frustrating / naughty that most payments coming out of the Treasury (e.g. planned bumps in income tax/pension allowances) seem to be CPI indexed while those going in tend to be RPI indexed. The main reason suggested for the double standards is legacy technical debt, but that doesn’t seem to explain why the inconsistencies seem to consistently resolve in favour of the exchequer.

The APD change garners revenue for the Treasury, though it’s a little sad as APD is already incredibly high compared to aviation duties in other countries. That might actually increase the attractiveness of routing through Zurich or one of the German hubs when I fly the London-Singapore route.

For comparison, long-haul premium cabin APD ex-UK will be £172. Singapore’s duty is about S$47 (about £27); Zurich weighs in at CHF 35 (also about £27) and Munich at EUR 42 (about £37).

I guess I’m mildly affected by the alcohol duty change as I do drink wine, but I don’t drink a lot so the impact is very minimal. I’m not currently affected by the fuel or tobacco duty changes.

50p Coin

  • The Royal Mint will produce a 50p coin to mark Brexit.

I’m somewhat of a Brexit bear and remain one (pun not intended). Taken at face value, the inscription (“peace, prosperity and friendship with all nations”) is at least one way in which I could see it possibly having a shot at working out – and assuming Brexit does go ahead is what I hope the government will do.

However, the quote is adapted from Thomas Jefferson’s inauguration speech as US President. The continuation is “entangling alliances with none”, which is in some ways apt if the UK is concerned with the EU’s ever closer union – though I’d think the US and UK in a modern-day context certainly are allies!

Conclusion

In terms of personal impact, the Budget felt very much like a constructive or at least benign continuation of previous Budgets. That said, I realise I say that from a point of privilege in that I view the status quo as manageable. I’m aware that there have been changes to benefits (notably, universal credit) which have made some worse off.

The Problem of the Golden Basket

Somewhat related to the previous post on paydays, I had lunch and then coffee with another friend, and for some reason our discussion turned to personal finance as well. Unlike the last time, I was the one starting with the view that deviates from conventional theory this time.

Suppose you have a choice between two savings accounts. One account pays 2% AER and the other pays 1% AER – so £10000 invested for a year would earn £200 in the first account but only £100 in the second. Should you allocate 100% of your savings to the account that pays 2% AER?

In general, if all other things were held equal, there probably isn’t much of a reason not to allocate everything to the 2% account. However, the standard for all other things has to be high. In practice, I can see quite a few scenarios where there may be legitimate reasons to allocate some money to the 1% account.

One possible reason could be terms of access. Clearly, if the 2% account is a fixed rate bond only allowing access to the money after some amount of time while the 1% is an easy-access account, that provides a clear reason. If one wishes to maintain an emergency fund, for example, the fixed rate bond is probably best avoided even if it pays higher interest. Some savings accounts, while not having a fixed term, place restrictions on withdrawals in terms of frequency or advance notice in exchange for higher rates – again, be careful about using these accounts to park an emergency fund.

Another reason could involve how the accounts compound. The annual equivalent rate (AER) refers to how much money one will have after a year. However, if one wants the funds together with some interest before one full year, then precisely how the accounts pay interest becomes significant. If the 1% account compounds monthly while the 2% account compounds annually only, then between one month and one year after the start date the 1% account has more withdrawable interest. This is a variant of the access problem, though this focuses on access to interest as opposed to the principal. This may seem a little short-term minded, but could be interesting if one is engaging in stoozing or has other pressing financial commitments.

The amount of money one has is also relevant. Financial institutions can fail; in this case, the UK’s Financial Services Compensation Scheme (FSCS) guarantees up to £85,000 per depositor per authorised bank/building society. There is thus certainly a case for keeping not more than that amount with each bank; if one was fortunate enough for one’s savings to exceed £170,000, finding a third bank seems reasonable. I’ve never seen cash as doing the heavy lifting as far as growing my portfolio was concerned. I’d collect interest as available, but would prioritise safety. If the accounts were held with the same provider, of course, then this argument falls down – even if one has multiple accounts, the FSCS limit is on a per-bank basis. In fact, one has to be careful as some bank brands do share authorisations – meaning that an individual will only get the protection once even if several of these banks fail.

In general, the inconvenience that might be caused by failures is something worth considering as well. The FSCS compensation only applies if the bank is suitably authorised; even if one’s balance is fully covered by the FSCS, claims can take one to four weeks to process. I think I’d be much more comfortable having at least a nontrivial amount in a separate account (two to three months’ expenses, ideally) if possible.

Customer service is another factor. I’d probably prioritise that more significantly for more complex products – however, for a savings account it would still be useful.

Furthermore, there are other principles which individuals might find important. MoneySavingExpert on its savings account best buy tables has a section for highly-rated ‘ethical savings accounts’. The criteria Ethical Consumer (which MSE works with) include concerns like tax avoidance and funding of climate change, though I don’t necessarily agree with all of them (“excessive director’s remuneration”, in particular – if someone is that valuable it seems unethical to me to artificially depress their salary). Similarly, Islamic banking is necessary for adherents, since interest is forbidden in Islam.

To conclude, there are quite a number of reasons why one might not actually want to put 100% in the higher interest bearing account. Of course it makes sense ceteris paribus (if all other things were held equal), but that seems unlikely in practice. The standard for all other things being held equal here is high – the access conditions, compounding conventions and bank account provider all need to match (and that isn’t even an exhaustive list).