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

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.

That One Thing (2018 Q3 Review)

Monomania refers to a mental disorder where one pathologically focuses on a single thing (naturally, at the expense of others, as one’s attention is limited). To some extent, I may have experienced this in my second year at Imperial, where for some reason I became fixated on my academic performance. I remember studying almost 100 hours per week when preparing for my exams then (typically achieved by a very strict 9am-11pm schedule everyday for about five to six weeks). I’m not sure how I managed at the time. In terms of grades, I think one should aim at 60 + epsilon, 70 + epsilon or 100, and I chose the last of these.

Things have changed since. I now evaluate how things have changed over a variety of facets. Even professionally, the metrics are a bit more multi-dimensional now. I’m not sure if it was the Palantir internship or something else, but in fourth year I made some decisions that clearly weren’t optimal as far as academic performance was concerned (working 15-20 hours a week). At that time, my main goals were get an average of 90% and submit twenty pull requests as a part-time software engineer. After I graduated the metrics became writing papers and pull requests; the latter quickly changed to patents as, all other things held equal, I find developing two or three innovative systems far more interesting and probably more meaningful than fifty rudimentary changes.

In terms of development, I’ve certainly found my recent work to be challenging (which is a good thing!). I’ve been continuing my focus on performance work, though now that many easy wins have been taken the features are getting more complex. I’m also starting to have more clarity on the kind of work that motivates me (and discussing this with my lead and others); having such discussions feels relevant and good.

I presented the LDLK on finite traces paper at AAMAS’18 (and it seems I now have a h-index of 2). It’s unlikely there’ll be another conference paper for a while though, as I’m currently diverting my computer-science energies towards writing a journal paper which summarises and extends the three conference papers to some extent.

A highlight of the quarter was receiving the VCLA award for an outstanding Masters’ thesis as well (Imperial article). In terms of raw computer science difficulty, MCMAS-Dynamic is probably the most complicated project I’ve delivered (there are a couple I’ve done since that I’m also proud of, but I’m pretty sure MCMAS still wins). Some recognition is always nice; too much ego-stroking can be unhealthy, but the odd bit is enjoyable.

In terms of finance, I didn’t really pay much attention to things this quarter. I was aware of the Turkish and Argentinian currency troubles as well as the US-China trade spat, but things on my end are still largely business-as-usual. In fact I thought this quarter was not going to be good, but looking at things it’s largely an effect of recency bias; while performance in September was indeed weak, July and August were actually very good.

Disclaimer: I hold my own portfolio, which includes the Fidelity index, VLS 80, iShares emerging markets fund, the REIT, the inflation-linked gilts fund, BTC and USD.

The high expenses of Q2 have actually snowballed further in Q3, though most of this is explainable by six-month periodic expenses and booking travel for the end of the year. Discretionary expenses have actually fallen a fair amount, which is unsurprising as Q2 expenses included Stockholm travel as well as renewing my web server. Savings rate is down, though still on track to be in a good place this year.

Work on dealing with logical puzzles has continued, and I think I’ve managed to find a source of metrics; Logic Masters India has a good selection of past contests along with a rating system. Based on a few of these, my Puzzle skills are currently around the low to middle 600s, while my Sudoku skills are in the high 700s. Individual contests may vary in difficulty, so normalisation is used. Interestingly, this is done on two axes, comparing both one’s score relative to the top scorer and one’s ranking relative to all participants.

I’ve also started to take an interest in cryptic crosswords, though I’m certainly nowhere as competitive at these; my general knowledge is not sufficiently broad. “Logical puzzles” are designed with the intention of being culture-neutral; these often demand a wide vocabulary (which I think I have) and broad general knowledge (less so). It helps that there is a group at Palantir that attempts these recreationally; I’m not aware of a similar group for general logic puzzles.

When one is investigating a search problem, one typically needs to balance exploration (searching prospectively for additional solutions) and exploitation (locally refining good known solutions). Historically when managing my own decisions I’ve largely been pushing exploitation for quite some time. I first discovered an interest in mathematics when I was around six; while this isn’t quite computer science or software engineering, that was near-by. I started programming at 15, and when choosing my degree looked at CS which I felt balanced my interests, skills and prospects well. When I was at university, I had the aforementioned monomaniac episode; since then I’ve branched out a little.

I’ve been behind the times (the song was released in 2017, apparently), but I’ve been listening to Meant to Be (Bebe Rexha and Florida Georgia Line) a fair bit this quarter. I don’t particularly enjoy the vocals in the original, but it’s been covered well; this one is better polished, while this one has the approach I go for when I try to sing it!

It’s enjoyable for me to (try to) sing along to, including the high vocal line in the chorus; it quickly becomes a question of hitting the tenor Bb4 repeatedly. Listening to the song certainly does make me thing of search space exploration problems, specifically genetic/evolutionary algorithms. The lyrics in the chorus sound very much like evaluating a fitness function on a candidate solution and then deciding whether to accept it:

So won’t you ride with me, ride with me?
See where this thing goes?
If it’s meant to be, it’ll be, it’ll be; baby if it’s meant to be.

The first verse has elements of not being too pressured with exploitation as well, and thematically echoes bits of Good Things Come To Those Who Wait which I looked at last quarter. The second verse reflects a degree of caution after being burned by poor approaches in the past. As I plan for what I might want to try to achieve (God willing) on a timescale of months or years, it’s important to not index too heavily on past experiences or initial reads of how a given path may turn out.

Algorithmic Modelling – Alphabear 2

Alphabear 2 is a word game where players are given a two-dimensional grid of tiles. Some of these tiles show letters, along with timers; others are concealed and must first be exposed by using an adjacent letter in a word. Players use letter tiles (anywhere on the grid) to form a word. When a player makes a word, he/she scores points equivalent to the sum of the timers on the tiles that are used. The timers on all tiles that aren’t used then count down by 1; tiles that reach zero become unusable stone blocks.

Usually, this means that you want to form long words that incorporate tiles that have shorter timers; for example, there is a ten letter word on the above board (PEDESTALED), but it doesn’t use the F. After playing this word, the timers on the remaining letters will count down by 1; the P will now have a timer of 2, the first E 10, and so on.

However, the game does have various mechanics that mean this isn’t always the best strategy. For example, one needs to ensure that there are actually enough letter tiles to work with, and that the distribution of letter tiles allows reasonable words to be formed. The game also has players choose bears for each mission which have special abilities such as awarding additional points for certain words. Actually, in hindsight FEASTED might have been a better choice than DEADLIFTS, as I was using a bear that gives a point bonus for words ending in ED.

In addition to scoring points by making words, players also receive bonus points for the largest fully cleared rectangular area. The game identifies this for you. I’m not sure how this is actually implemented, though there are large enough boards (15 by 15?) that it’s probably not the naive algorithm of generating and testing all rectangles; where N is the width of the board that would be O(N^6). There is a DP-based approach where one can keep track of the number of stone blocks that slashes this to O(N^4) which would probably be enough. With more clever approaches it’s possible to knock the time complexity down to O(N^2) – and that’s probably optimal as any less would involve not actually reading some parts of the grid.

Most of the time, this isn’t something to worry about too much. I’m able to clear most levels with no stones at all. However, if we need to take a stone, ideally it should be as far away from the center of the board as possible (note that only the largest rectangular area counts).

Defining optimal play in general is difficult, owing to the spatial reasoning required by the largest clear area bonus, uncertainty of tiles that are yet to be revealed and sheer breadth of options when faced with many open tiles.

Before starting a round, the player has to select bears to use. Optimal decisions here largely depend on the specific challenge being played. A bear that scores bonus points for six-letter words isn’t particularly useful on a tight board where one has only a few open tiles at a time; some bears add time to timed boards, which isn’t useful if the board has no time limit. Furthermore, players select up to three bears each round; these bears can have useful synergies. In particular, I like a combination of “summon three Zs” and “score triple points for words including JQXZ (not stacking, unfortunately)”; “summon ING” or “summon ED” goes quite well with these two as well. I’ve used these to complete a mission deemed “impossible” given the strength of my bears at the time.

We can perhaps begin by focusing more narrowly on optimal play of an Alphabear endgame (where all tiles have been revealed), ignoring special abilities bears may have for now and assuming that the board has a solution. Here is an example:

From this point on, there is no more uncertainty as to what letters we have to use. Interestingly, this board shows that a greedy algorithm where one tries to play the longest possible words doesn’t work. One could begin WORKSHOPPED, leaving RAII, but this is actually an unwinnable state. There are several two-turn solutions, like ROADWORKS + HIPPIE, or WORSHIPPED + KORAI. (Obviously, this is very high-level play; I think I played SKIPPER with this board. That leaves RODIAHWO, for which I’d probably have played something like RADIO + HOW, though HAIRDO + WO is better.)

Given a multiset of pairs of letters and timers L = (l,t)^+, we want to return a suitably ordered list of words S = \left[ l^+ \right] , that satisfies the following properties:

  • legitimacy: every word s \in S is included in the game’s dictionary.
  • resourcing: words do not use tiles that aren’t in L.
  • timing: for each pair (l, t) \in L, l is used in a word before or on position t.

The above set of properties is not correctly specified without a refinement to deal with duplicate letters. There are several ways to deal with this; assuming low cardinality, one approach could be to recognise all duplicate instances of letters as separate letters, and suitably expand the dictionary to allow this. Our list is then L = \left[ (A,3), (B_1,1), (B_2,1), (E, 1) \right], and the dictionary recognises both B_1 E and B_2 E.

I don’t have a good way of finding an optimal solution; I suspect the problem is actually NP-complete; it feels like SAT or 3SAT may be reducible to this problem, though I haven’t worked through the details. Nonetheless, there are several search heuristics we can try. Clearly, on a given turn we must use everything which now has a timer of 1. Also, although this board is an example of why you don’t want to be greedy, in general it probably makes sense to do some kind of ordered backtracking, where one expands the most promising nodes first. I can imagine an A* search could actually work well, though finding an admissible heuristic could be hard.

There’s a fourth property we want as well:

  • optimality: the score produced by the words is maximal.

Going back to our sample board, WORSHIPPED and KORAI will score one more point than ROADWORKS and HIPPIE, because there is one fewer timer tick. In general, we want to minimise the number of timer ticks by playing longer words upfront where possible, as this reduces the number of timers that are still ticking. Once one has devised a feasible solution, it may make sense to perform some iterative optimisation by seeing if it’s possible to bring letters forward. Of course, that approach may get us stuck in a local optimum. I could see some kind of iterative hill-climbing algorithm from the top-n admissible solutions (as found by our ordered backtracking) yielding decent results.

Unfortunately my vocabulary and anagram skills are far from good enough to handle the required complexity, especially under time pressure. Most of the time, successfully playing every letter on the board is enough to complete the mission’s objectives. Interestingly, it looks like the game wasn’t really programmed to deal properly with successfully using every letter but failing the mission. The game claims that there’ll be an additional reward on the reward screen when identifying the board as clear; yet, there is no reward screen as the mission was failed.