# 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.

public class DeepCopy {
public static Object copy(Object a) {
Object obj = null;
try {
ByteArrayOutputStream bos = new ByteArrayOutputStream();
ObjectOutputStream out = new ObjectOutputStream(bos);
out.writeObject(a);
out.flush();
out.close();

ObjectInputStream in = new ObjectInputStream(
new ByteArrayInputStream(bos.toByteArray()));
}
catch(IOException e) {
e.printStackTrace();
}
catch(ClassNotFoundException e) {
e.printStackTrace();
}
return obj;
}
}

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).

# Moving Cash Flows

I met a friend for a meal on the weekend, and among other things my friend mentioned that at his company, there was an internal debate over whether payday should be moved forward. This wasn’t a debate on the financial ability or willingness of the company to do this, but was instead focused on individual workers’ preferences.

My initial reaction was a bit of surprise. I wondered why this was even a debate, as I believed the answer should almost always be yes. This reminded me of the standard time-value-of-money question that I wrote about just over a year ago; being paid the same amount of money slightly earlier, mathematically, seems like an outright win. The UK hasn’t had negative interest rates yet – and even in a place like Switzerland where bank rate is negative, this isn’t typically passed on to most depositors.

Cash flow might be a problem if one considers the dollar-today-or-more-tomorrow question; however, this shouldn’t be an issue in this set-up. Valid cash-flow scenarios remain valid even if payday is brought forward. In a sense, an early payday creates additional options; it shouldn’t invalidate any existing ones.

With a bit more discussion and thought, though, we found that there were indeed valid reasons as to why one might not want payday to be shifted forward.

First, although the mathematical argument makes sense, there are some edge cases around tax liability. If one’s salary is close to a marginal rate change and a payment is pushed across a tax year boundary, the amount of tax one pays might change (and can increase).

Also, although we speak of interest as an upside, how much benefit an individual can actually realise may be significantly limited. Some bank accounts pay interest based on the lowest balance on any day in the month, meaning that being paid a few days early yields no benefit. Even if interest is based on the average daily balance, the upside is also in most cases small. For a concrete example, 2017 median UK post-tax earnings would be about £1,884.60 per month. If one was getting paid three days early and storing that into a high-interest current account yielding 5% APR, the additional interest wouldn’t be more than about 30 pence.

Moving away from purely numerical considerations, there are many other plausible reasons too. Clearly, departing from an existing routine may affect one’s own financial tracking. I find this alone to be a little flimsy (surely one’s tracker should be adaptable to variations arising from December and/or weekends?). That said, if one is unlikely to derive much benefit from the money coming early (and it seems like in most cases there indeed wouldn’t be much benefit), the change would likely seem unnecessary.

Another scenario could be if one has many bills or other payments paid by direct debit, and cannot or does not want to pay all of them. In that case, deciding precisely where the money goes could be significant – for example, if one is faced with a decision to lose fuel or premium TV in winter. This is probably not the right system to handle a situation like that, but if one wishes to only make some payments then an unexpected early payday could mess the schedule up. Somewhat related might be joint accounts in households where there are financial disputes.

Taking advantage of an early payday also requires self-control. Consider that if one is living paycheck-to-paycheck, while an early payday might ease financial pressure, it also means that the time to the next paycheck is longer than normal (unless that is also shifted forward). This needs to be dealt with accordingly.

If you’d ask me whether I’d like payday to be shifted forward, I’d almost certainly say yes. Our discussion went to a further hypothetical – would you take a 1% pay cut to have your entire salary for the year paid on January 1st?

From a mathematical point of view, you would be comparing a lump sum of $0.99N$ dollars paid now, or (for simplicity) twelve payments of $N/12$ dollars paid $1/12, 2/12, \ldots, 12/12=1$ years from now. Assuming that you can earn interest of $r$% per month and using monthly compounding, after one year we have

$Value_{\text{LumpSum}} = 0.99N (1+r)^{12}$

$Value_{\text{Normal}} = \sum_{i=1}^{12} \left( \frac{N}{12} (1+r)^{12 - i} \right)$

If we set these two to be equal and solve for $r$, we get a break even point of $r = 0.00155$. This computes out to an APR of about $1.87\%$. This is higher than best-buy easy access accounts at time of writing (MoneySavingExpert identifies Marcus at 1.5%). You can beat this with fixed-rate deposits, and probably beat this through P2P loans, REITs and equities – though more risk is involved.

I think I could see that being a yes for me, though I’m not entirely sure I’d have the self control required to manage it properly!

# Chips on the First Floor

Every so often, I spend some time filling out a crossword puzzle. There are quick crosswords where only definitions of terms are given, and cryptic crosswords which include both a definition and some wordplay. Especially for quick crosswords, these clues can be ambiguous – for instance, Fruit (5) could be APPLE, MELON, LEMON, GUAVA or GRAPE; OLIVE if one wants to be technical, and YIELD if one wishes to be indirect.

To resolve this ambiguity, about half of the letters in a quick crossword are checked. This means that their cells are at the intersection of two words, and the corresponding letters must match.

With a recent puzzle I was attempting, I had a clue with a definition for ‘show impatience (5, 2, 3, 3)’. I didn’t get this immediately, but with a few crossing letters in the middle I quickly wrote down CHOMP AT THE BIT. This was fine until I had a down clue with definition ‘problem (7)’ which was D_L_M_O. This should clearly be DILEMMA. It was a cryptic crossword, so I was able to check CHAMP AT THE BIT with the wordplay part, and it made sense. (The clue was “show impatience in talk about politician with silly hat, I bet” – which is CHAT around (an MP and then an anagram of HAT I BET).) The “original” expression is actually CHAMP, though I’ve only heard of the CHOMP version before.

I sometimes have difficulty with crosswords in the UK (and sometimes with crosswords from the US as well) owing to regional variations in English. Singaporean English follows the UK in terms of spelling. However, in terms of definitions, things vary. For example:

• Common with UK usage:
• Tuition refers to additional small-group classes (like in the UK), not the fees one might pay at university (US).
• biscuit is a baked good that’s usually sweet (like in the UK) and probably shouldn’t be eaten with gravy; an American biscuit is a bit more scone-like.
• Common with US usage:
• Chips are thin fried slices of potato (same as US). The word refers to fried strips of potato in the UK (which themselves are fries in both Singapore and the US); the thin slices are called crisps in the UK.
• The first floor of a building is the ground floor (same as US); in the UK that’s the first floor above ground (which is the second floor in Singapore and the US).

Without venturing into Singlish (which incorporates terms from Chinese, Hokkien, Malay and several other languages), there are also terms that aren’t in common with either American or British English. Some of these pertain to local entities. Economy rice is a type of food served in food courts, and the MRT is Singapore’s subway network – though I’ve heard several uses of it as a generic term, much like Xerox for copying.

Others seem a little more random. Sports shoes refer to trainers specifically, and don’t refer to water shoes or hiking boots which are used for sport. The five Cs refer to cash, cars, credit cards, country club memberships and condominiums – five things starting with the letter C that materialistic Singaporeans often chase.

I’ve been resident in the UK for around six years now. This is obviously fewer than the number I’ve spent in Singapore (about 21), though the years in the UK are more recent. I’ve gotten used to the British expressions, especially for life in the UK (I generally like chunky chips more than crisps, and correctly distinguishing the first and ground floors is important for getting around). I don’t think I’ve had too many issues with remembering the correct versions of terms to use when in Singapore or in the US – having had to deal with these inconsistencies has helped here.