Static Single Assignments (January Haskell Tests 2018 – Part 2)

Second in a two-part series; see Constant Propagation (January Haskell Tests 2018 Part 1) for the first part, which covered the assessed portion of the test.

In January this year, Imperial College’s first-year computing students were tasked with implementing a tool to handle constant propagation for statements in static single assignment (SSA) form. In particular, this means that each variable is only assigned to once, and there are no compound expressions. This is useful for optimising compilers to simplify the machine code that a program compiles down to.

Of course, being required to write everything in SSA form is painful; as much as I like immutable objects, mandating their use can be costly (consider a large set, for instance, that periodically receives updates). Banning compound statements can also be troublesome; hence, SSA compilation is typically automated.

The test concluded with a challenge tasking students to implement support for converting a more general program into SSA form. The students had been working with a simple imperative language with statements to assign values to integer variables (possibly doing mathematical operations), conditional statements (if-then-else) and do-while loops.

This problem naturally decomposes into three sub-tasks: supporting SSA translation for basic blocks, conditionals and then loops. The first problem can also readily be split into two sub-problems: ensuring variables are immutable and then handling compound expressions.

Basic Blocks

Immutable Variables

I opted to begin with immutability here, as this would allow for easy testing. This is done by creating multiple versions of a variable. For example,

could become

Essentially, one could implement this by keeping track of the latest version of each variable used, and incrementing the version whenever processing an assignment. Whenever handling the right-hand side of an assignment, one needs to be able to know how to reference the latest version of a variable.

I’m pretty sure I wouldn’t have bothered to write a specific UsageMap type when I was still in university, though working in industry seems to have made me think more carefully about typing.

Compound Statements

The version of SSA in the paper also doesn’t allow compound statements (e.g. a = ((b * c) + 5) / d). However, this could be handled reasonably as arithmetic expressions can be represented in tree form.

We can create temporary variables for each non-leaf node of the expression tree. For example, we define k1 = b * c, k2 = k1 + 5 and k3 = k2 / d. Some care is needed in cases where the tree is a bit more balanced (we need to know that the first argument of our plus above is k1).

Also, of course, k is only used for illustration above, as real functions could have a value actually called k! It makes sense to have a counter separate from the rest of the UsageMap, though I relied on some limits on the variable names that were mentioned in the specification. I’m not sure if I would have worked this out in first year!

Conditional Expressions

One needs to consider which versions of a variable are in scope. Let’s consider the following block:

After reaching the end of the if block, we can’t just use the UsageMap we have obtained from that to pass into the else block (since on an execution where we’re going in to the else block, the if block must never have run). Similarly, after reaching the end of else we can’t just use the UsageMap from that (we don’t know if the else block has run).

It is probably easier to visualise this block of code as a tree. Each node represents a possible linear execution path that we may run.

The versions of variables each of the blocks read upon branching should be the version before we entered that block. Thus, we should reference the state of the UsageMap from before we entered the if block when entering the else block. We actually want something like this.

When returning, we somehow need to pick one of the final values for variables that were possibly modified. This is difficult to express, but we can approximate it with a phi function, where \phi(a, b) nondeterministically returns either a or b. We can thus simply pick a4 = \phi(a2, a3) and b4 = \phi(b2, b3), and add these statements. Finally, we would want to return a4 + b4. Some care needs to be taken with the implementation (for example, one must handle the case where a variable is only possibly modified correctly). This should, for the above block of code, yield:

During the implementation I was running out of time, which unfortunately led to this monster of a helper function. It could probably be cleaned up by perhaps making a type for ‘return values of a traversal’. It’s also probably reasonable to do some kind of higher-order function on the mod-set of variables (which I computed elsewhere).

Do-While Loops

Finally we also need to support loops. We could use a call graph structure, similar to what we had for the if-then-else conditional, except that there is a cycle.

At first glance, this looks tricky. We don’t know the number of times the loop will execute, though we do know it’s at least once.

Which value of a are we reading in the loop body? Well, this is either the value from the initial set-up, or the value the previous loop left at its end. We could thus try to introduce phi-functions:

This program is impossible to execute, of course; the definitions are cyclic. However, we’re not actually trying to execute it. We’re only using this as an intermediate representation to try to statically optimise our code. Of course, if the two arguments to a phi-function are the same, we can eliminate it, mark that value as a constant if known, and then use the information about it being a constant to drive further optimisations.

Synthesis

I think this could be a fairly challenging question in and of itself for first-year computing students, though some degree of hand-holding would likely be required (in particular, the tree traversal for splitting out intermediate assignments can be quite fiddly to work with). It would also be worth introducing the concept of basic blocks early on, as reasoning about them is more useful in handling conditions and loops. It was a rather solid and satisfying conclusion to the original 2017 test.

Constant Propagation (January Haskell Tests 2018 – Part 1)

The latest iteration of the January Haskell Tests is out (see Dr Tony Field’s page, and my post on the 2017 test). I think the last time I wrote any Haskell was eleven months ago when taking the 2017 test for a spin; nonetheless I was able to pick things up quickly. I guess the syntax (outside of monads) is pretty intuitive.

This test in some ways felt a fair bit easier than the last, at least in terms of the assessed portion (the last time round, it took me up to just past the two-hour mark to clear that; this time round, I was done with the questions that were actually worth marks by 1:15). However, the ‘bonus’ unassessed Part 4 seemed hard; finishing it in time looked to be a pretty tall order. Part 4 itself could be decomposed into three fairly chunky parts, and could even be a reasonable basis for a separate test!

The test dealt with optimising code that was already in static single assignment (SSA) form. I’d covered this topic before in a course on software reliability (within the context of static program verification), though I don’t remember covering it within the context of (possibly optimising) compilers. SSA form is fairly restrictive:

  • Each variable can only be assigned to once.
  • Operator arguments can only comprise constants and direct variable references.

For example, the assignment  x = 4 * y + 7 * z is clearly not in SSA form; but it can be rewritten as  a = 4*y; b = 7*z; x = a + b where each statement is. In most programming languages variables can be assigned to multiple times; as part of conversion, we tend to add suffixes to variables for versioning. A more involved example follows:

SSA also allows for the concept of a phi function, which has two expressions, and non-deterministically returns one or the other. This is useful for performing optimisations regarding control flow. For example, consider this function:

We can rewrite this using a phi function; after an if-block, the final value of a variable could be the value at the end of either branch.

Although one had to work with phi functions as early as Part 2 (the function written at the end of part 2 should be able to simplify the above function significantly), thinking about the purpose of phi functions certainly wasn’t important until Part 4.

Part 1 involved writing an interpreter to execute statements in a (very) simple subset of C, where code has already been parsed into tokens. I think this was intended to set a baseline for students who were struggling with the material; I knocked through the 14 marks worth (which is enough for a pass; that’s 47%) in just 17 minutes.

Things got somewhat tougher in part 2. The opening was easy, with two 3-mark questions inviting candidates to implement simple constant folding optimisations (in particular, that  0 + x = x and \phi(x, x) = x , along with calculating out results) and then determining the value of an expression given knowledge of some variable values.

The tricky part then began, with a task to implement constant propagation and folding to actual code blocks in SSA form. Conceptually, this is not difficult – once the value of a variable is known, it can be substituted into all subsequent occurrences. A fix-point approach fits naturally, since knowing something about some variables can lead to knowledge about more variables. Nonetheless, I struggled for a while with implementing the suggested worklist algorithm; the aforementioned fix-point approach was suggested too, and would probably have been more elegant, if harder to implement. I finished this part at 1:01.

Part 3 involved removing phi functions if it was not possible to clean them up as part of the SSA optimisation, by pushing the variable assignments back into code. It seems a decision was made to state the rules for these explicitly in the specification, for some reason (to be fair, as Tony notes it is straightforward), which seemed to make for a pretty tame last assessed part. There was some tricky thinking required here, nonetheless; I think one has to be very careful with handling multiple phis!

Finally, Part 4 tasked students with translating a function to SSA form. This itself is weighty enough that I think another test could easily be written on it. This part can be decomposed into three (maybe four) separate challenges:

  1. Translate basic blocks to SSA form correctly.
    1. Maintain correct information about versioning of variables.
    2. Decompose compound statements (like x = 3 * y + 5 * z).
  2. Add support for conditionals.
  3. Add support for loops (do-while was a part of the simple C subset used).

Squeezing all of that into the remainder of the time after finishing the first three parts would have been tough; I finished the first two full tasks (basic blocks at 2:07 and conditionals at 2:46) and squeezed out a comment on what to do for the last sub-task. The last part of task 2 was also written rather hackily as I was racing the clock. For a quick preview:

To be fair, I could probably have churned all three main and three bonus parts out in Java within the time-limit; it’s nonetheless useful to engage a different set of programming skills.

Last year, I wrote that I enjoyed revisiting Haskell; I enjoyed this year’s task too. I think I actually enjoyed this installment more, probably because of the outsize difficulty in Part 4! Although I haven’t written professional Haskell, I often find myself writing functional-style code in Java, and I’d still give it an enthusiastic thumbs-up for a choice of first language to teach at university. There are some influences from professional development coming in here, too; a year ago I probably wouldn’t have batted an eye at using types like a Haskell [(Str, [Int])] or Java Map<String, List<Integer>>, while I’ll tend to give structures types more quickly. My tolerance for long functions (without good reason, in non performance-critical scenarios) has also certainly decreased.

This post is Part 1… I’ll take a more in depth look at Part 4 of the exam in Part 2.

Should Exams Be Graded Out Of 137?

I reviewed Misbehaving a couple of weeks ago, and in the introduction the author (Richard Thaler) relates an interesting tale about grading exams. He mentions that setting the maximum score to be 137 instead of 100 in a US college context was useful, in that it allowed him to gain a better understanding of students’ performance without drawing too much complaint [1].

Thaler finds that exams can be made a lot more difficult, without hurting students’ confidence too much. The actual percentages students obtain are immaterial (because how raw scores translate to actual grades is done on a curve); yet, in a US college context where A grades often start at 90% or above, suddenly getting a 72 (even if it is an A+) could be unnerving. Making exams difficult allows students to show that they haven’t just learned the material but have understood the logic and thinking behind it. For a first year logic course, say, I wouldn’t be opposed to the exam including unseen extensions of the material covered in class (for example, branching into monadic second-order logic or simple temporal logics); for a final year course, I’d expect students to be able to understand papers on the subject (even if unseen) and apply knowledge from said papers. This may be related to my work and interests, but the courses I remember best at Imperial include disproportionately many with difficult exams (Software Engineering (Design), Complexity and Intelligent Data and Probabilistic Inference come to mind).

There is a risk of stressing students out if they do the math, of course. A few quick presses on a keyboard or calculator should reveal that, say, a 96/137 is just about 70 percent. However, one has to be fairly deliberate about doing such calculations, as 137 is a rather awkward number to mentally calculate percentages with. If you asked me to estimate what a mark out of 137 corresponded to in a 100-point scale, I would probably engage in some kind of iterative search algorithm where I added 13.7s, and then 1.4s. However, apparently people are generally lazy enough that they won’t bother with computing the percentage of their raw score. They’d simply look at the grade itself (which largely depends on where the raw score stands in relation to others, not so much on its absolute value).

Would this system be applicable or useful in the UK? I’ll acknowledge it was indeed a very clever solution in a US context, though I’m not sure it’s necessarily as useful in the UK. This mainly stems from the fact that grades in the UK are generally numerically lower; an A (a First) typically starts at 70 percent rather than 90. There’s thus already quite a fair bit of room to separate students that have merely learned the material from those that have engaged and understood it. Thaler mentions that students scored an average of 72 out of 100 on his initial exam (which caused an uproar among his students); that’s on the high side in the UK! Typically, exams at Imperial would have a fairly difficult ‘tail end’ for the last 30 percent; I could see a case for a really hard ‘last stretch’ (10 percent) which tended to occur in some of the programming tests, but I think most exams have had enough discriminatory power. Generally, you’d want to use research projects and other forms of work over longer periods of time to sift out the top students (as those are probably more similar to both industry and postgraduate academia).

Another difference is that UK universities typically aggregate course grades by a percentage system, rather than by GPA. This does make sense; I would generally consider a student scoring 90 and 65 in two modules (77.5 average) to be far superior to one scoring a pair of 72s, while the GPA system would say otherwise. I’d be inclined to think I’d prefer the 90/65 student to one with a pair of 78s, even. This is not a problem for using a raw limit of 137, as they can always be translated (non-linearly, if need be) to percentage grades.

One benefit of this system is psychological; even if the raw score might well be just 60 percent, scoring an 82 sounds much better. However, at Imperial at least, exam scripts generally aren’t returned to students. Also, this relies on most exams being graded out of 100 points (or less); if one is accustomed to 200-point exams, then being confronted with a score in the 80s might feel terrible (even though it is percentage-wise better than a 110 in a 200-point exam!)

There is also one minor objection I have, speaking more generally. Unless the exam being set is really, really hard, it’s likely that some students are likely to score above 100. Thaler claims this “(generated) a reaction approaching ecstasy” – I’m not sure I’d feel the same way as it would once again become front and center that the raw score is not a percentage, unlike most exams! The illusion would be clearly broken. Nonetheless, these students can probably take comfort in the fact (if they need to) that they’re probably well ahead of the rest of the class.

In general, I think grading out of 137 (in raw scoring terms) can be pretty useful if (1) existing mandated grade boundaries or expectations are too high, so that one can’t distinguish students’ command of material; (2) one can control how raw scores are actually translated into grades that the students receive; (3) students get to view the raw scores, and (4) most exams are graded out of 100 (or possibly less).

All four appear to be true in the US system. While (2), (4) and maybe (1) are true at Imperial at least, (3) was not – and I’d say without (3) it probably wouldn’t be worth the effort.

Reading List: ‘Misbehaving’ (Richard Thaler)

I spent a good amount of time thinking about whether I should register in the UK Registered Traveller Scheme (costs £70). In total, I easily spent more than seven hours thinking through this, modelling a few scenarios, and trying to estimate the value of my time relative to data about airport immigration queue timings. I earn more than £10 an hour.

In hindsight, I tried to make a good decision above, but the decision to try (at least as hard as I did) was probably a bad one. I’ve generally always been interested in making better decisions, and these decisions often involve managing resources that are finite. I’m not sure exactly when I first came across the field of behavioural economics, though. The notion of an Econ (a fully rational agent that maximises self-interest) is certainly something I’d come across in high school economics classes. I remember also familiarising myself with quite a number of these cognitive biases when attending talks on personal finance during various past internships – and certainly when reading up on personal finance online.

Misbehaving describes a wide variety of historical research events concerning behavioural economics. This covers its growth from infancy to becoming relatively widely accepted in the mainstream. While some rudimentary knowledge of mathematics is needed to follow the text, I wouldn’t say much background is required. I was fairly familiar with quite a large number of the experiments described, so I would imagine that there might not be that much new content for readers already interested in the field. Nonetheless, there were quite a few new things I came across; I hadn’t heard of the mug experiment [1] used to demonstrate the endowment effect. The analyses of closed-end mutual funds [2] and NFL draft picks were also interesting to read – it was nice to be able to relate knowledge to concrete application.

The book begins with an introduction to how the field came about, describing the author’s observations about human behaviour in practice that contradicted the true behaviour of a rational Econ. These include considering supposedly irrelevant factors (SIFs) like one’s current feelings as relevant; valuing things that one owns (one’s endowment) higher than things one could own, and an imbalance between preference for gains and losses. There was also a relatively more anecdotal list of observations the author made too. I’ve made my own list for things I’ve done in the past, and clearly do suffer from a number of these inconsistencies as well:

  • The introductory example. (What’s the value of an hour?)
  • The returns from my mutual funds come from both capital gains and dividends. So far at least, I’ve always been reinvesting all dividends. Yet, I feel happy when a dividend comes in. (Dividends are taxed more harshly than capital gains.)
  • I’m much happier receiving a gift that someone has picked out for me than if the person gave me the cash and suggested that I might be interested in buying the gift with the cash. (I can replicate the first scenario in the second, and I also have more choices.)

From there, a variety of topics are presented in a largely topical and somewhat vaguely chronological idea. I think my complaint that I found a substantial portion of the material to already be familiar was largely in sections II (“Mental Accounting”) and III (“Self-Control”), perhaps because these are the relatively common examples people with some interest in the field are likely to come across first. The later sections get more interesting. Section VI (“Finance”) played well with my own interest in personal finance; Section VII (“Helping Out”) discusses practical applications of using insights from behavioural finance to ‘nudge’ people to make better decisions regarding their own finances… or complying with tax law.

The book ends with the author outlining hopes for how behavioural economics could continue to grow in relevance, discussing fledgling work in education. There is also an interesting section where the author dispenses some advice for life in general, based on his work in behavioural economics (specifically: make observations, collect data, and be willing to speak up).

While models should indeed account for important variables, I’m not sure I necessarily agree that these factors should be consistent over time, mainly because I think individuals can learn and within certain bounds optimise their own behaviour, though not to the point of being a hyper-rational Econ. Although in chapter 6 (“The Gauntlet”) it is claimed that learning how to make many high-stakes decisions is difficult because we don’t get many attempts at them, I think some of the decision-making skills are transferable. I might not get to make many decisions buying houses, and there certainly are aspects about buying a house that are peculiar to the task itself – yet, learning to learn about relevant considerations for the domain (as I already do with consumer electronics), plan how one’s cash flow is going to work (as I already do with regular investment into mutual funds) and being more aware of possible cognitive biases (relevant in almost all decisions) all seem to be helpful.

I enjoyed the book as a whole; it was a pretty engrossing read on my flight from Singapore to London. It held my attention for at least a good three or four continuous hours on that plane, and I was eager to finish reading the book when I landed in London. I’d recommend it as a good read, though as this is written to a fairly general audience readers who already have substantial knowledge of the field might find there not to be as much fresh content.

Retirement by 40?

I overheard a conversation a few days ago on the near-impossibility of retiring by forty. It is understandable (consider 40 in relation to standard benchmarks for retirement – a private pension can be withdrawn at 55 and the state pension is given at 65, and these numbers are trending upwards). I’m not sure I agree, though; there exist quite a number of examples of people that have done this [1, 2]. Meta-analyses disagree (against: [3], in favour: [4]). It’s true that internet and media sources may perhaps not be reliable, but in any case one can perform the relevant analysis.

Even given the option, I’m not certain I would take it. It’s arguable that I had a taste of retirement for the two-odd months in between submitting my Masters thesis at Imperial and starting full-time at Palantir, and I didn’t find it that easy to fill my time after a while. I’d probably stand a better chance now, having reignited a couple of interests in things apart from computer science.

Anyway, let’s get to analysis. One simple way of decomposing this problem can involve

  1. Figuring out the amount required before retirement is feasible, and
  2. Figuring out the required savings rate to reach the result obtained in step 1.

For the first point, there is a well-known 4% rule. Suppose you withdraw 4% of your portfolio in the year when you retire, and then adjust your withdrawals for inflation every year. Then, your portfolio will last for at least 30 years in 96% of historical scenarios. I have some issues with this, biasing in both directions.

I think 4% seems lower than is reasonable, for several reasons:

  • The idea that one blindly draws the stipulated salary even when the market is down seems absurd. Really, one should factor in market returns when making one’s decisions about income, as in [5 – note, technical!].
  • The study assumes that the portfolio alone supports the retiree; yet, a side hustle of some kind may be relevant, and at least in the UK the state pension could kick in once the retiree reaches 65 (or whatever the age is at that time).

Yet, there are certain reasons to adjust the figure upwards too:

  • The life expectancy of someone who’s 40 is probably higher than 30 more years (especially one who’s considering retirement at 40!), hence that’s not enough as a baseline.
  • The study used the US markets, which have been performing very well. Of course, one can decide to use exclusively the US markets, but that tends to introduce currency risks too.
  • The study in question does not account for fund and platform fees. These can be kept quite low (I estimate my own portfolio operates at about 0.22%, and some of this is by choice because I hold some active and smart-beta funds, along with indices that are a bit more exotic) but invariably chew into returns.

It seems like it’s a reasonable rule of thumb, though I wouldn’t treat the figure as authoritative.

One needs to estimate asset returns and inflation for both parts 1 and 2; this can be partially simplified by working everything in real terms, though there is a risk that owing to high inflation increasing one’s savings in line with inflation can prove untenable. Typically, one relies on historical data; for instance, UK stocks have returned about a CAGR of 5.2% from 1900 to 2011 [6]. Post-retirement sequence of returns risk can prove troublesome, although the variance might indeed be smoothed out over a longer period.

Notice that assuming one starts from zero and using the 4% or any constant-percentage model, the only factor after the asset returns and inflation rate have been factored in would be your savings rate – the level of expenditure needed is a function of this. I guess one could introduce another factor for decreased spending upon retirement! An example of a concrete calculation (inclusive of a link to a spreadsheet) can be found in [7]. Using the examples there (5% real returns, 4% withdrawal rate) and bearing in mind that I have 14 years till I’m 40, that clocks in at a smidge above 55 percent.

For an individual, though, there’s probably a somewhat easier method to determine if a retirement by 40 or early retirement is feasible:

  1. As above – figure out the amount required.
  2. Given one’s past saving and investment patterns, estimate the amount one is likely to have at 40 if one continues to behave in the same way.

Of course, we need to make the same assumptions involved in figuring out the value computed in step 1. We also still can’t get away from estimating inflation or market returns in step 2. However, the previous calculation for step 2 assumes a constant savings rate; with this method it is a lot simpler to adjust the model to account for events peculiar to one’s own situation (such as long CDs maturing, stock options, vesting of bonuses, known large expenses etc.).

We then compare the figures in steps 1 and 2; there is of course some wiggle room. I think there’s a distinction to be drawn between deciding that one is financially independent and pulling the retirement trigger, though that’s perhaps a separate discussion topic. [8] I certainly would be interested in the first, but not the second at this time (and, hopefully, even at 40).

One can even switch the method up a bit further:

  1. Figure out the amount one is likely to have at 40 (step 2 above)
  2. Figure out the withdrawal amount one can derive from that. Decide if that’s feasible.

Again, we don’t get away from assumptions concerning inflation or market returns. Deriving values in step 2 gets tricky; one can always use the 4% rule or assume some other constant factor. It’s worth saying (for all of the methods) that building in fudge factors to leave some leeway for underwhelming market returns is probably a good idea, since getting back into the workforce after a long spell of early retirement might prove difficult.

Personally I’m very fortunate that this should be possible if I decide to push hard on it. It’s difficult to say though – past performance is not an indicator of future performance, and I’m at a point where I’d say my past spending is also not an indicator of future spending. I think I’m pretty frugal, but don’t entirely fancy maintaining the same degree of strictness I’ve been running with in my university years throughout. It’s certainly possible, but also definitely not easy, and I’m not sure it’s what I’d want to do.

This Side of Town (Goals for 2018)

I’m back in London, though I still think I’m on holiday. While that’s not a bad thing in and of itself, it doesn’t quite feel like 2018 has fully started yet. I have an annual exercise in goal-setting after the year-end reviews, to help me figure out what I should be focusing on in the year ahead.

Software Development

A1. Grow rapidly as a software engineer.

In 2017 I’d say progress was certainly made here. I see this as measurable by considering the change in range, scope and depth of issues and questions I receive and am able to answer/fix/address. Nonetheless, setting a benchmark is pretty difficult. In previous years I’ve written this as “be a strong engineer”, but for me at least I know that’s going to end in failure. I won’t be surprised if I end up complaining at the end of the year that I didn’t grow rapidly enough; while understandable, I think that’s something I’m less likely to berate myself for.

When I was in Singapore, I met up with a close friend, and for both of us it turned out that 2017 was a year largely centered around the pursuit of technical and career development – to the point that we struggled to think of other things to remember the year by. While growing technically is definitely something I want to do (it is target A1, after all), it shouldn’t be at the expense of all else.

A2. Present a paper on computational logic.

We had two papers in 2017 based on the work done as part of my Masters’ thesis. Things are getting a little trickier here now, as writing more will require some original extension of the work that was already done (as opposed to merely tightening up existing work). Nonetheless, I

A3. Get at least two patents in the pipeline.

I enjoy the creative parts of my job – while some of it is indeed cobbling together glue code to ensure that other pieces of code interface correctly, there are many more interesting bits involving designing and building new systems, whether as part of normal work or otherwise. These more… creative projects can be filed as patents, and setting this targets serves as encouragement to look beyond the day-to-day on my team and think more carefully about what can be improved.

Skill Development and Experiences

B1. Write 52 full-length blog-posts on this blog.

I failed this last year; in the end I wrote just 37. I have a few ideas for how I can do things differently this year to give myself a greater probability of success at this one, such as having a series of book or paper reviews, which should also get me to read more widely.

Of course a once-per-week cadence is the target here, though I’ll consider this successful regardless of the actual temporal distribution of the posts. I define full-length as requiring at least an hour of thinking and writing. I won’t assign a word limit (in case I write a poem, or some kind of “Explain Like I’m 5”) though for standard non-fiction prose I’d say it tends to be somewhere between 700 and 1500.

B2. Visit 12 distinct countries this year.

The point of this is that I’d like to spend a bit more time travelling while I still can*. Trips as part of work do certainly count. In terms of edge cases, I’ll allow Scotland, Wales and NI to each count as one (I probably wouldn’t allow it if I’d been before); trips for work count, but airside transits do not. If I ever do a mileage run (i.e. fly purely to preserve airline elite status), that doesn’t count either. There is no requirement for novelty (so Singapore does count, as would a likely trip to the US at some point).

*for health / work / other commitment reasons, not because of Brexit! Since the UK isn’t a part of Schengen I don’t think I really benefit that much from residing in the UK for this, other than proximity and less fettered imports.

B3Walk 3,650,000 steps this year.

This is 10,000 per day and I wouldn’t have managed it last year (I hardly ever broke 10,000 – let alone an average of 10,000). Walking to work helps, but by itself that’s not enough.

This target can be accomplished by walking in circles around my room, though I hope it also encourages me to get out more and try out more different routes.

B4. Be able to sing a B4 consistently, and complete three studio recordings.

This looks like two targets, but I’m pairing them up because they are both related to singing and the alternative of giving music its own section seems a bit excessive.

B4 is a pretty high note (think the high notes in verse 2 of Journey’s Don’t Stop Believin’ – “find” in “living just to find emotion” and “night” in “hiding, somewhere in the night” are both B4s). I’m somewhat more confident of my A4s and Bb4s. I’m able to hit B4s sometimes, but I really wouldn’t go above Bb4 if I had to perform (in fact, I’d prefer to stick with A4s, even).

Obviously, there is no requirement for the B4s to be as bright or sustained as the ones in the Journey song. I’m looking more for reliability here.

The studio recording target is because I have been practicing to maintain my vocal range and to some extent accuracy, but I don’t remember when the last time I actually tried to learn a song was.

Financial Responsibility

C1Maintain a savings rate of 50 percent or higher. This is computed by

SR = \dfrac{\text{savings} + \text{investments} + \text{pre-tax pension contribs.}}{\text{net salary} + \text{pre-tax pension contribs.} + \text{dividends} + \text{other income}}

I’ve been thinking about maxing out my pension contributions, but I’m not so keen to do that because of the Lifetime Allowance and also the lack of flexibility in that the money is tied up till I’m 55. This could make sense if I wanted to pursue an early-retirement path, but I’m not currently thinking about that.

This is a pretty ‘vanilla’ target and existed last year. It’s certainly not easy, though I wouldn’t say it’s that unreasonable either. I’m quite a fair bit above this mark in 2017. However, one thing I’m tracking for 2018 is that super-hard saving and investing can also be irresponsible; see this post on Monevator

C2Live at at least the UK Minimum Income Standard in 2018.

Without considering rent, for a single person that clocks in at £207.13 per week (so about £10,800 per year). That’s still a substantial bump from my expenditure last year.

It’s very easy for me to be very strict with spending, but sometimes this becomes counterproductive. I’ve spent hours agonising over a £20 decision; even if I made the right choice (which is likely to have value less than £20; assuming that paying more yields a better product/service), that’s still way below minimum (or my) wage. I’m rather well taken care of, and sometimes my monthly budgets can be eye-wateringly tight as a result.

Relationships

D1. Maintain clear and regular communications.

In 2017 I did reasonably well here, so there’s not much to say here other than to keep on keeping on. In practice this goal could probably be split into several sub-goals corresponding to people or groups of people, though that information is a little less public.

Highlights and Lowlights (2017 Review)

I did four reviews at the end of each quarter (see: Q1, Q2, Q3, Q4). Typically, I link each of these reviews to a song I’d been listening to a lot during the quarter. This is usually based on whether I empathise with the singer’s persona, as I find these more ‘sticky’ than merely good instrumentals or well-executed pieces. For a quick recap, the songs were:

  • Q1: “Back from the Edge”, James Arthur
  • Q2: “7 Years”, Ben Schuller (this is a Lukas Graham cover)
  • Q3: “Mercy”, Shawn Mendes
  • Q4: “Back to You”, Louis Tomlinson and Bebe Rexha

This selection makes it seem like it’s been a rather turbulent year. It has been, but looking back on things I think it’s certainly been decent enough too. Of course, variance and volatility don’t necessarily imply growth, but it certainly feels like the problems and struggles I’ve had have been beneficial. Here’s a quick rundown of some of the more notable things that have happened to me this year.

Commuting on Foot

I started walking to and from work instead of taking the tube. In an earlier post, I calculated that I was being paid an effective wage of £27.59 an hour to do this. I think I kept up with this through most of the year; that walk while initially taxing feels quite normal now. It’s a good bit of morning exercise for me to clear my head before starting work, and I find it a convenient time to call home too. Furthermore, the amount of money saved is quite substantial; I’d imagine I’d spend £126.80 a month for the monthly travelcard, but in practice my monthly transport expenses are more in the range of £20, so that’s an extra £1200 per year.

To be fair, I’ve noticed that I’ve worn through shoes much quicker this year (the route is about 2.5 km each way), so maybe depreciation should additionally be factored in to the cost. Even then, I’ve been disciplined about intelligently shopping sales for walking/running shoes; I’ve spent less than £100 on shoes this year, so factoring that in we’re still looking at more than £1000 in savings.

AI Down Under

I took two weeks out in late August to present at IJCAI 2017 in Melbourne, Australia (plus a short holiday, and a stop-over in Singapore). I do have a bit of a soft spot for pure, hard theoretical computer science, and this certainly allowed me to show off some of that. Besides actually giving the LDLK talk, the non-technical programme was also very interesting; I managed to meet quite a number of interesting researchers whom I only recognised from their papers, there were a variety of interesting venues, and there was also an exhibition where some robots attempted to compete in football.

My own non-technical programme was great too – I enjoyed touring parts of Melbourne, the hotel (the Crown Metropol) was very comfortable, and of course returning home was good, even if only for a short while. The 24-hour flight was pretty intense, but there wasn’t really a compelling alternative.

Greed and Fear

Cryptocurrencies are, of course, a highly volatile asset class. I’ve been maintaining modest long positions in a couple of them; the extreme swings have certainly highlighted the presence of these ‘primal forces’; while I did buy into BTC under $5000, there’s a part of me that’s still a bit miffed that I didn’t initiate a larger position then. I extracted my cost basis at $17000 and will probably let the rest ride.

In total, my portfolio gained about 18 percent this year. I’ve never actually been through a bear market (well, at least with a large investment holding). There was the correction in early 2016, but my portfolio is substantially larger now. While I’m of course familiar with Buffett’s well known hamburger analogy – since I’m a net buyer of stocks I should be happy when they go on sale – I’m in a position where I could at least on paper lose half a year’s salary if things get ugly (or even more – during the Great Depression, stocks crashed by roughly 90%).

Cross-Border Connections

It has been more than a year since my cohort at Imperial graduated. The one-year mark is significant for a few of my friends, because one year is a common requirement for intra-company transfer visas (at least in the UK and in the US). I’ve also had friends who started outright overseas (much like what I did). Keeping in touch has been somewhat tricky, especially bearing in mind timezones – but I think it has been going fine.

I’m starting to see what I thought was the most likely scenario as far as maintaining these connections post-university pan out. I got pretty stressed last year thinking that it would be difficult to keep these ticking over. I’m aware I have a tendency to inaccurately amplify small risks, and this turned out to be the case here.

Builders

I always had a bit of skepticism about 24-hour hackathons whilst in university (bad work practices, too many flashy demos without actual reasonable implementation); that said, I do like the concept of hack weeks and have participated actively in every one of them that’s been on whilst I’ve been at Palantir. Five to nine days is long enough that people aren’t generally going to be working too unsustainably (though I have certainly felt the burn from pushing hard on these – even then it’s 80 hours a week hard, nothing near 168). I’d definitely classify the hackweek we had in summer as a major highlight of the year, and the one in winter as something nice too.

It’s a nice occasional reminder of the ‘core’ parts of my job I like (that said I do also enjoy interviewing and tech-talks). I enjoy many of the projects I do for these hackweeks because I get to apply fancy CS things that I’ve read about or otherwise worked on while also testing my engineering and rapid-iteration skills. There is a claim that if one wishes to go fast, one should go alone; if one wishes to go far, one should go in a group – and while the hack-week form of many of the things I’ve worked on doesn’t make it into production, the rush of rapid development is exciting and some form of what I work on tends to, indeed, make it to production.

Inverse Boiling a Frog (2017 Q4 Review)

Q4 hasn’t ended yet, but this will probably be the last post I write before doing a more general overall review for the year.

There’s a part of me that looks back at Q4 and complains that there hasn’t been much growth or development at all; stacking this with the opening thesis of the Q3 review, it’s very easy for me to be harsh on myself for all this.

Some of this is because much of the improvement has probably been gradual – there weren’t large one-shot spurts and/or reminders that progress was being made, unlike in Q2 (which had a strong hackweek project and a paper acceptance at IJCAI, for instance). I can find it easy to discount growth as I don’t always remember difficulties experienced in the past that clearly. Nonetheless, it’s well known that the aggregation of marginal gains can and often does deliver big wins over time. Although the period does not feel like it was a high-growth period, looking back 4 or 6 months does reveal several larger differences in terms of knowledge about AtlasDB, Java and other projects at Palantir too. It’s kind of an inverse to the often told story of a frog being boiled alive.

The GitHub pull-request count for this quarter is 21, which is a significant drop from previous quarters (we were at 30 in Q3). Some of this is because I’ve spent more time reviewing others’ code; some of this has been looking at development work elsewhere too. Other professional goals have been going reasonably well too, and usefully I now have concrete things to think about as far as growth is concerned.

On the academic front things have quietened down a little. We’ve written and submitted another paper, but after this the next target would probably be a journal paper (there isn’t really that much more material in the thesis, unfortunately!). This was probably the hardest paper to write, mainly because it was based on the last part of the thesis and I waved my hands a lot in the original proofs I wrote – these needed to be formalised, and some of this formalisation was difficult!

Financially, at least up to this point in the year, things seem to have gone well, maybe even too well. The REITs (even though global) and expectedly the bonds have been slowing things down a bit, but I guess that’s the price one pays for diversification. I remember reading an article on the Permanent Portfolio on Monevator that claimed that many investors fail to diversify into assets that actually have negative correlations.

(N.B. I hold the JK portfolio, of course, and also the Fidelity world index, LS80, iShares property fund, BTC and GBP.)

There is a more complete visualisation of the performance of varying asset classes called the Callan periodic table – I think what spooks me somewhat is seeing everything in the black (well, at least in nominal terms; in the UK at least cash in large quantities would probably fail to deliver above the roughly 3 percent inflation we’re dealing with, and the 1.8 percent from the property fund is clearly below that too).

Spending this quarter was fairly normal. It was higher than a real base-line level, though mainly because I decided to splurge a little to exploit some Black Friday deals when I was visiting Palo Alto. Food expenses – specifically eating out with friends went up significantly this quarter too. December also always tends to be spendy, for various reasons (birthday, Christmas…)

Looking at comms, things have gone pretty well this time around. As always, there are a couple of lapses, but I’ve been able to dedicate time to coordinating meetups, and done this quite a few times.

Last quarter I mentioned that I find that I have an inner voice that tends to berate me for underperformance, though the standards said voice sets are often too high. I’ve started thinking a bit more around the rationale behind said high standards, though. Think of it as moving from “why are you failing to save 70 percent of your income?”, or “why aren’t you working a 65 hour work week?”, say, to “why do you want to save 70 percent of your income?” or “why do you want to work a 65 hour work week?”. Back in university, these targets were often natural consequences of regular work for me – I like to do things well, generally – and so I’d easily accept “because it’s hard” and because it was in general alignment with my goals at the time. In the long run, however, it’s probably a bad idea; the cost is real. It’s a powerful tool, and I do recognise the drive it provides as far as improvement is concerned, though.

In a sense, while I still seek relief and mercy from the criticism of said inner voice (as in the Q3 review), I’ve also started questioning its purpose while still trying to appreciate its importance as far as overall personal development is concerned. Killing this perpetual hunger for continuous improvement would be a bad idea, so…

I love it, I hate it, and I can’t take it
But I keep on coming back to you

(Yes, another alternative interpretation – this time of this song though substantially more creative liberty has been taken this time around. I’m… pleasantly surprised; I think of the members of One Direction I was probably only expecting material from Zayn Malik and Harry Styles post-breakup, but the others have put out good work, and I’d say more in line with my tastes than those two.)

Balloon Battle (Hotseat: UKIEPC 2017, Part 1)

Overview

The United Kingdom and Ireland Programming Contest (UKIEPC) 2017 took place a few weeks ago. I used to participate semi-actively and had a rather annoyingly consistent habit of finishing in third place at Imperial. I haven’t done contest programming for quite a good amount of time, though some of my experience from interviewing candidates at Palantir might have helped.

Teams are given five hours to solve somewhere from eleven to thirteen problems. These problems involve submitting a program (the source will do) to an online judge, which typically runs said program against multiple test cases and evaluates the output of the user’s program in some way. This can entail simply checking strings, or alternatively checking if the given solution achieves some task (consider problem D in this set).

This time round I managed to figure out 9 problems, rather coincidentally with a total “penalty time” of 999 minutes. When teams are ranked, the number of problems solved is compared first; to break ties, teams are given penalty time, where solving a problem T minutes since the start of the contest, with F failed attempts, scores T + 20F penalty time. The penalty for failed attempts does not accrue until the relevant problem is actually solved. It’s still in one’s interest to finish solving any questions – even though it may give you arbitrary amounts of penalty time, it will not hurt your ranking. This score would have placed second at Imperial (maybe because some of the members of the usual team number 2 have graduated?) and, at time of writing, 51st out of 522 overall.

Problems

This half of my write-up (I intend to discuss this in two parts) covers what I think are the easier seven problems in the contest, in the order I tackled them. Looking at the metadata on Codeforces, there is a pretty clear drop-off after this. Interestingly, F was actually considered the hardest problem of the ones I’ve listed here (in that fewest teams solved it), but I was able to place it third in difficulty; I struggled more with D than some of the later ones, even, though mainly for implementation reasons.

C: Cued Up

Wrong answer at 9 minutes; correct answer at 18 minutes (10 minutes spent total).

Given a description of the number of snooker balls still on a table, determine the maximum number of possible points remaining to be scored. Initially any ball can be hit (it isn’t known whether the red or coloured balls are “on”), but thereafter players can’t pot 2 consecutive reds, and if a non-red is potted and reds remain on the table, the next ball potted must be red. Assume that only one ball is potted per shot.

This is mainly a straightforward implementation – the main snag is that if you have only red balls, then regardless of how many there are the right answer is 1. I think I messed up the first time because I fixed this edge case (which is the last of the sample tests), but accidentally ended up printing “1” before the correct answer on all of the other tests…

I: I Work All Day

Correct answer at 13 minutes (4 minutes spent).

This was basically decoding the problem statement and figuring out that “what’s left over after repeated subtraction” refers to the modulo operator. I probably could have got this one out faster if I was still comfortable with C++.

J: Just a Minim

Correct answer at 17 minutes (4 minutes spent).

Figure out the length of a tune given the length of note values. Again, raw implementation. I’m surprised this even took 4 minutes, though that might well have been because I went through all the sample tests, and also did the “hacky” approach of hardcoding the strings. There was a slightly faster to write up solution that involved special casing 0, and then writing 1/x for the others. I also might have wasted some time because I was concerned about floating point rounding errors and so calculated things in terms of sixteenths. (That’s not needed because these numbers have exact binary representations, and the problem limits would be very unlikely to result in a loss of precision.)

F: Flipping Coins

Correct answer at 26 minutes (8 minutes spent).

You have n coins, all initially tails up, and k coin flips which you are obliged to exercise – but you can choose which coin to flip. At the end of the game you keep all coins that are heads up. What’s the expected number of coins you can keep (with optimal play)?

This one is figuring out the right strategy (pretty simple – always flip something that’s tail side up if you can) and then writing a recurrence relation. There are overlapping subproblems, so a quick bit of memoisation is needed, but it is not hard to implement. I’m surprised how much candidates appeared to struggle with this problem. I guess it requires a little bit more familiarity with thinking in terms of probabilities, which has tended to be one of my stronger points at contests like these.

D: Deranging Hat

Wrong answers at 50, 53, 61 minutes. Correct answer at 89 minutes (63 minutes total spent).

A sorting network consists of comparators; given two indices i and j (importantly, in that order), if i is greater than j, then the letters at those indices are swapped. Given a string, build the sorting network that would “sort” the traditionally sorted version of that string back into the original string. For example, given the string “dude”, you would need to transform “ddeu” to “dude”, perhaps by comparing 4 and 2 and swapping them, and then 3 and 4 (and then swapping them). The sorting network can’t be more than ~10X the length of the string, in the worst case.

It took me quite a while to figure out what the problem statement meant. I came up with a reasonable idea (swap each letter into its right place, iterating through the string once), but was needlessly worried about performance and started doing a lot of fiddly book-keeping with Maps of SortedSets; there was a difficult-to-trace bug in there. I then gave up some time after 61 minutes and reimplemented things with a much simpler temporary char-array solution, which worked.

A: Alien Sunset

Correct answer at 104 minutes (15 minutes spent).

Given day lengths on multiple planets and times of sunrise/sunset, find the first time within a given time window where it is dark everywhere.

I avoided this at first because it looked like an Interval Tree kind of problem. Though seeing that many people solved it, I had a closer look and it looked like writing something in O(planets * allowed time window) would work. Thus, simply start from 1 and test each possible time interval to see if it is indeed dark everywhere, and if it is return. There was a bit of a snag with some planets having daylight hours crossing zero, but nothing too difficult to manage.

E: Education

Correct answer at 140 minutes (36 minutes spent).

A school has N departments, each with some number of students Si; they need to move to a new set of buildings, which each have capacity Ti and cost Ci (but they cannot share buildings). Minimise the total cost of all buildings, while fitting all of the students in (if possible).

I figured to sort the departments in descending order of size and then thought of some kind of dynamic programming based solution. I then realised I could do better; a greedy solution which picked the cheapest available building could actually work, if one was considering departments in descending order of size. This led rather quickly to one possible solution: sort the departments in descending order of size, and then populate a priority queue (highest priority = lowest cost) with permissible buildings. As larger departments are housed, smaller buildings can be added to the permissible pool, though we still want to ensure that large but cheap buildings would be used first. If the queue ever ran dry, the assignment would be impossible.

Five problems remain that are somewhat more difficult (at least in my opinion).

Thoughts

There are certain skills that I’m still reasonably comfortable with, like mathematics in terms of computation. There are others like computational geometry that I don’t remember too well (as we’ll see in part 2). The first part of these contests is typically a speedy rush to get credit for as many problems as possible; usually somewhere between the 5 and 7 problem mark things slow down a bit. The second part for me tends to be more interesting, though I find that the focus changes from speed to actually thinking hard about algorithms – and very often fretting over implementation as well.

Unwinding Logical Threads (Hotseat: WPF Puzzle GP 2017, Round 1C)

Background

The World Puzzle Federation is an international organisation which, among other things, organises annual puzzle contests. These involve solving puzzles that rely on logical deduction and observation. That said, maybe because I’m pretty new to these, sometimes backtracking algorithms are the order of the day!

The Puzzle GP is a series of distributed puzzle competitions run throughout the year. The GP is split into three series: C, B and A (in increasing order of difficulty). Puzzles in group C are likely to be largely accessible to general audiences (and that’s what I’m covering today); group B puzzles are typically drawn from a selection of “well-known” puzzle types, and group A puzzles often feature extensions of group B puzzles in unusual ways.

Contestants are given 60 minutes for each set of puzzles. I have very little experience with these puzzles, so I think I’ll start with group C.

(The puzzle set can be found here.)

Performance

I started off with the Darts puzzles, for which I had a strategy in mind. I then struggled with the Matches puzzles, only solving C7, before moving on to the Arithmetic Squares, both of which were solved quickly. I then spent probably a good ten minutes digging through the Word Search. I finished the easy Scrabble task and almost finished the harder one, though I failed to see a simple move near the end of the puzzle. I then started on Products, which I probably should have prioritised more highly as I think I figured out the mathematical logic behind it. I solved the 120-pointer C18 after the contest, and it was actually not too hard. With three minutes left to go after finishing C17, I took a stab at the Fill in the Blank series and managed to solve two of them.

I solved the remaining puzzles after the time ran out, apart from C3. Elastic Bands was actually very easy. I have a bit of an aversion to spatial reasoning puzzles, but recognised the problem as graph isomorphism and had some techniques for it based on that. Old Maid was also easy; I didn’t get round to it in time. The last Fill in the Blank and both instances of Count the Shapes both gave me headaches.

Selected Problems in Depth

C5-C6: Darts

Given a dartboard which has several regions with k point values and m darts, find a way to throw the darts on the dartboard such that the darts add up to a target value. Each dart must score, and each region can have only up to 1 dart. For example, with regions [4, 21, 8, 11, 13], two darts and a target of 19, the correct answer is [8, 11].

To solve this for two darts, one good solution could be to iterate through the list. On a computer, using a hash-set could be a good solution; when we look at a number, if it’s in our “target set” we’re done – otherwise we add the number we would need to make up the target to the target set. It’s a simple O(n) solution.

I think implementing a hash set on paper for me would be too troublesome. There’s an alternative which I used: sort the array in O(n \log n) and then, use a pair of pointers, one starting at the beginning and one at the end of the array. Adding the numbers up, if we’re over the target we bring the pointer at the end back, and if we’re under the target we push the pointer at the start forward.

The problem had three darts; I simply picked the overall largest number and solved the appropriately reduced target with the two-dart algorithm above, backtracking where needed to smaller largest numbers. Binary insertion sort is probably pretty reasonable to do by hand.

C10: Elastic Bands

Given a network with nodes marked with letters, and another network with edges provided, give a labelling of the nodes such that the networks are identical. This is basically finding what’s called a graph isomorphism in discrete mathematics.

I didn’t solve this in the contest, but probably should have. I split the nodes by degree, and then tried to identify relationships between these. For example, there was a single degree 4 node in the puzzle that wasn’t connected to any of the other degree 4 nodes, so I was able to uniquely identify it quickly.

C16-C18: Products

Given an N \times N grid, place the numbers from 1, 2, \ldots, 2N in the grid once each. Each row and column must contain two numbers, and numbers cannot share a cell. Clue numbers are given by the side of the grid and sometimes on diagonals. Where given, the product of numbers in the relevant row, column or diagonal must equal the clue.

The first two puzzles had N=10; the third had N=15. I think my main strategy here involved searching for prime factors that would uniquely identify numbers along the rows and columns. For N=10 this would be [11, 13, 17, 19]; for N=15 this included [17, 19, 23, 29]. I also usually started looking for very large numbers (because they might have a unique factorization in the allowed range) or small ones (e.g. in the first puzzle, there was only one column and one row with a product less than or equal to 20, implying that the 1 had to be in that column/row).

I also considered the places where a given number might fit, and in the later puzzles noticed when multiple columns could definitively use certain numbers. For example, if 5 was already used in an N=10 puzzle, and there were two 20 row hints, I could eliminate 1, 20, 2 and 10 from consideration for the other rows.

This wasn’t too difficult, though I can imagine that puzzles with only partial hints might be substantially more challenging!

Meta-Analysis

A score of 262 would have placed 12th out of 215 contestants (2nd out of 139 for contestants not in higher divisions). To be fair, this is in part because many top solvers don’t participate in the division C contests at all. Some of this might also be because there would have been less pressure as I was doing this on my own, not as part of a real contest.

Looking at the top end of the scoreboard, the Darts, Arithmetic Square, first instance of Matches and first instance of Products were solved by most of the leaders. Elastic Bands and Old Maid (I didn’t solve either of these two), as well as the Word Search were also fairly common. Thereafter, contestants varied quite a bit in what they solved. As might be expected, the contestants that solved the final instance of Products generally did very well (it was worth 120 points by itself).