Blog postings

I recently discovered Advent of Code, a bunch of puzzles with a Christmas theme that need to be solved by programming solutions. What I like is that the initial problem comes with a Part 2 which is either easy (if you did Part 1 sensibly) or a nightmare.

So here is what I thought of 2022's edition. Other ones as and when I complete them... 

I did 2022 in C, with a lot of flex and bison written to handle the inputs. Often flex actions were enough to do the puzzle, 

Day 1: Calorie Counting

Very simple. Add up some numbers with blank lines meaning take a subtotal and start again. You'll need to do a little sum for part 2. 

Day 2: Rock Paper Scissors

Again this is straightforward although the problem statement is a little tricky needing close attention. Again barely 20 lines of flex.

Day 3: Rucksack Reorganization

This involves splitting a string into two, identifying characters in common, assigning a score, and summing. Part 2 involves counting common items across lines which is a little tricky. 

Day 4: Camp Cleanup

I thought this was straightforward. Do you know what a proper subset is? And also what a non null intersection is? 

Day 5: Supply Stacks

The first one that needed some thought and resulted in a long solution, although most of that was due to me sticking with C so a hundred lines of malloc() and pointer chasing. The actual algo is very simple, and part 2 wasn't hard. 

First time I think C was a problem, as all I did was have list of pointers and easy to blow up. This will be a recurring theme. 

Day 6: Tuning Trouble

This was relatively easy. Scan through the text and determine whether the mild conditions on non repeating characters have been met. Didn't even need flex just in raw C.

Day 7: No Space Left On Device

Haha I remember this one. Basically build a tree and seek through it finding appropriate nodes. 

Difficulty is, of course, using C, so there's a lot of mallocing to do and some of the answers are filename sensitive. Very irritating. 

Also, of course, in the real world directories take up space themselves to store the linked list of contents (or however they store it depending on filesystems). A nice little puzzle all the same.

Day 8: Treetop Tree House

Oh this was fun. Form a map and determine running totals of where things can be seen in straight lines. I ended up doing a whole bunch of loops for this, and I'm sure there is a nice functional solution. 

Probably half my code is malloc(), free() and pointer chasing. 

Not too difficult thinking about it. 

Day 9: Rope Bridge

I really enjoyed this one, because it is how a whole bunch of computer games involving things like snakes and so on are implemented. Move a chain around and how often do certain links occupy certain spots?

Also I used flex to read the inputs, so it was a case of reading a line, doing it, and then reading the next one. 

I recall this being quite tricky. 

Day 10: Cathode-Ray Tube

Oh this was great. Inspired by how ancient console games wrote to the TV by timing the position of the CRT beam - they'd literally write bits to be immediately displayed or not. I don't know how they managed it. Doing dumb desktop stuff is hard enough. 

Solution was ultimately very short as you're either moving a dot or turning a pixel on but it is very precise. 

Part 1 was logging values at certain points; part 2 was drawing the screen. I didn't like the font he used. 

I did really enjoy this. Such a neat puzzle. 

Day 11: Monkey in the Middle

Ah. This. Actually wasn't too bad. A very annoying lex to set up the initial objects and then you are literally just doing what the instruction say. 

Also rediscovered how annoying C's qsort is. Pass in a function pointer... 

Day 12: Hill Climbing Algorithm

This was an exercise in 'do you know Dijkstra's Algorithm'? There are others like A* but the original and best works in essentially no time at all. 

Part 2 was a little trickier and needed an adapted approach 'Reverse Dijkstra' where you work back from the goal to the start. 

Again satisfying especially if you don't already know these things. 

Day 13: Distress Signal

This involved an actual parse so I brought out Bison to form the structure of the lists in the input file. Then some rudimentary tree walking to come up with the answer. For part 2 I cheated and just added the two additional nodes to the input. Worst bit was figuring out how to create a sort function for qsort but I already kind of had it from part 1. 

Day 14: Regolith Reservoir

Ah this one. Again much like computer games from the past letting gravity do stuff to falling particles. 

Wasn't too bad in the end. According to The Internet this is ackshually a delicate finite automata problem that is dead easy to solve if you are versed in such things. I did it grain by agonising grain instead. 

Day 15: Beacon Exclusion Zone

An irritating geometrical one. I didn't like it.

Day 16: Proboscidea Volcanium

The valves. Basically set up a graph and do a search for the optimal solution. 

Part 2 was rotten as you now had another entity and its actions to track. Rotten. 

Day 17: Pyroclastic Flow

This is just Tetris. However I cheated and eyeballed what the cycle length was and hard coded it. Doing it properly would involve saving state and I couldn't bring myself to do it. 

Day 18: Boiling Boulders

Flood filling for part 2, part 1 was almost like diffusion limited aggregation. Not too hard overall. But then...

Day 19: Not Enough Minerals

Horrible NP complete breadth first search. There are a couple of filters you can put in to trim the search space e.g. don't explore making a new factory if you couldn't possibly consume its output. But nasty

Day 20: Grove Positioning System

This was just permuting an input vector. Not too bad... 

Day 21: Monkey Math

Haha. Well. This was basically building an expression tree and evaluating it for part 1, so I broke out a calculator I had written in bison and adapted it slightly (needed lazy evaluation). 

Part 2 was essentially find an inverse operation. I didnt. I used binary search. Reset all nodes, adjust the input node based on the previous iteration, iterate until the output node is the desired value. Inverse operations have some delicacies with division of negative numbers and I didn't want to deal with it. 

I really enjoyed this one, mainly as I already had the answer written somewhere else.

Day 22: Monkey Map

Oh. Oh no.

This one. 

You basically have a cube mesh and you're following a point on it. 

But of course this is 3D. 

getting the mesh set up was absolutely, unbeliveably abysmal. Full of tricky off by one errors absolutely everywhere. Hardcoded edge mappings. 

Broke the part 1 answer solving it and, frankly, I don't care. Horrible. Glad it's over. Got a little paper cube still as a horrible memento. 

Day 23: Unstable Diffusion

Ah. This was easy after the brutality of day 22. Barely worth mentioning. 

Day 24: Blizzard Basin

Pathfinding again although with a constantly updating map. I ended up iterating the map with additional marks for "this cell can be occupied at this step somehow".

Part 2 was a bit of a pig but not too bad. Change the bool for a set of three states OUT, RETURN, FINAL and cease when the goal cell is FINAL. 

Day 25: Full of Hot Air

The last. A straightforward thing where numbers are expressed in powers of five, but using -2 -1 0 1 2 not 0 1 2 3 4. 

Overall - well I enjoyed it. 

 

This site used to be hosted on Heroku. I liked it as any changes could be put in via git push heroku master. However, they moved from having a free tier to charging even for very basic web apps. (No one reads this blog so the bandwidth and compute needed are trivial). I didn't mind paying $7 a month for some cloud based compute, until suddenly I did. I thought there must be other services around.

Ended up settling on fly.io. Took an hour or so to figure it out. fly.io still charges if you exceed a free amount of resources, which I won't, because noone reads this. 

Basically what you do is

• Read the instructions on fly.io about launching an app
• There is one gotcha: environment variables. Fly uses some different kind of container technology compared to what heroku does, so getting your variable to appear in the right place is different. Fly calls these secrets, but all secrets referenced in config.py need to be a thing called a build secret, otherwise fly complains it cannot see it. 
  
  Build secrets are documented. I needed quite a few of them for various reasons, so the dockerfile had a lot of them put in and I had to write a short shell script to call fly deploy. 
  
  Every secret needs two lines in the docker file, a local file that can be cat with the secret in it (ADD TO IGNORE FILES!!!), and a line in a deployment shell script. 

It's a bit clunkier but to save £60 a year I can deal with it. 

I'm still not quite sure why there needs to be two kinds of secrets. I prefered pushing to git to deploy rather than what fly has as well. 

 

I'll post more later. But here's an image 

This is from a hotel in Tenby. Busy man

 

Given everything that is going on at the minute, I've been spending more time talking about mortgages than I normally would. Part of this is just the terrors of middle age. But one thing stuck out:

You know, if you pay an extra payment right at the start of the mortgage, you knock an entire year off the term

Seemed mad to me. But lets work out. Maybe it isn't. 

The Theory of Interest

Now you should have been taught this in school. But if you weren't I will go over the very basics. It is not that hard. 

Interest rates are normally quoted as an Annual Percentage Rate (APR) for borrowing or an Annual Effective Rate (AER) for savings. There are very precisely defined rules about how these are calculated and displayed - e.g., if you see an APR of 3.2% it could mean you need to use 3.1999% in your calculations. I will inaccurately use the terms interchangeably. 

So. Interest. If someone says you have an interest rate of \(i\) then what does this actually mean? Well it means if you put some money away for a year it will grow by that much (or the amount you owe will grow by that much if you are a borrower). \(i = 5\%\) means you can put £100 away and end up with £105 in a year. That's it.

Interest is just the idea that a bird in the hand is worth two in the bush, with money instead of avians. Do you prefer £100 now or £105 in a year? If the interest rate is 5% then they are the same thing. If the interest rate is 6% then £100 now is better; if the interest rate is 4% then £105 in a year is better. Interest rates on mortgages and so on are actually set in this way. Major institutional lenders are constantly borrowing and lending vast sums, in complicated ways with derivative financial instruments, with the prices of deals between each other filtering down to the interest rate offered to mere mortals like us. 

So we know how to use i to go from one year to the next. But in the real world you would borrow £1,000 today and pay it back over several years. To understand this is where compound interest comes into play. It's not too hard I promise. £100 today, at a rate of 5%, is the same as £105 in a year; what about two years? We just have 

\(£100 \text{ today}\equiv£100\times(1 + 5\%)^2 = £110.25\)

And for three years it is

\(£100 \text{ today} \equiv £100 \times(1+5\%)^3 = £115.76\)

and so on. Thus, you can make £300 by having £105 returned in one year, £110.25 returned in two and £115.76 in three. But people prefer level payments. So we come to the real question: if I want to pay back £300 in three annual instalments at 5%, how much is each instalment? You would expect something like £110. But exactly? 

Annuity Factors

This is where some algebra comes in. One thing we always want is the value today of £1 in one (or two, or three, or...) years time. To save ink we introduce a special letter for this:

\(v^n = \frac 1 { (1+i)^n}\)

This also works for non annual periods. So the value of £1,234 at 5% in two and a half years is 

\(\text{value} = £1234 v^{2.5} = £1234 / \left(1.05^{2.5}\right) = £1092.30\)

That is, you could put £1,092.30 in a savings account that pays 5% for two and a half years and you would have £1,234 at that point. 

To figure out what our annual payment is, we want to solve the following equation:

\(£300 = P \left(v^1 + v^2 + v^3\right)\)

This is easy enough. Evaluate the thing in the brackets at 5% and divide £300 by it:

\(£300 = P( 0.95238 + 0.90703 + 0.86384) \\ P = £300 / 2.7232 \\ P = £110.16\)

There we go. Three payments of £110.16 a year apart is worth £300 today. 

Doing that tedious thing with the vs is impractical if you have very many (say six hundred monthly repayments on a fifty year mortgage). Fortunately you can use a thing called a geometric series to do the hard work for you. First thing - notice that we can write \(\frac v {1-v}\) as \(\frac1i\). We can do a summing up as:

\(\require{enclose} \text{value} =a_\enclose{actuarial} n = v + v^2 + v^3 + \cdots + v^n \)

So,

\(\require{enclose} a_\enclose{actuarial} n - va_\enclose{actuarial} n = v\left (1 - v^n\right) \\ a_\enclose{actuarial} n(1-v) = v\left (1 - v^n\right) \\ a_\enclose{actuarial} n = \frac{1-v^n}{i}\)

Great. So if we are paying £10,000 at the end of every year, for 25 years, at 5%, this is worth 

\(\require{enclose} 10000 a_\enclose{actuarial}{25} = 10000\frac{1 -v^{25}}{i} = 140,039\)

This is quite roughly how a mortgage works. You borrow £140k and you pay back £833.33 a month (it's complicated - see next section) for 25 years. The expression \(\require{enclose} a_\enclose{actuarial}n\) is called the annuity for n years. The funny angle bracket thing means it is for n years. Without the bracket it means something very different. 

Payments in advance and monthly

There are other things we can do. Often payments are made at the start, not end, of a period. There is a sum for that. Observe: 

\(\require{enclose} \ddot a_\enclose{actuarial} n = 1 + a_\enclose{actuarial}{n-1} =1 + \frac{1-v^{n-1}}{i} \\ = \frac{(i+1)-v^{n-1}}{i} \\ = \frac{1-v^n}{iv}\\ =\frac{1-v^n}{d}\)

where we have introduced d=iv the discount rate. If you get £1 in a year's time at a rate i, you put (1-d) into an account. 

Two more headaches. You usually see interest quoted annually but you pay monthly (or your investment pays interest every three months, or semi-annually). This needs you to use convertible interest rates. If you earn 1% every month and say this is 12% a year, you are really using an annual rate convertible monthly. This is notated as

\(\left(1 + \frac{i^{(12)}}{12}\right)^{12} = (1+i); \\ i^{(12)} = 12\left((1+i)^{1/12} - 1\right)\)

This seems arcane, but if you are paying your mortgage monthly and not annually then you can use 

\(\require{enclose} a_\enclose{actuarial}n^{(12)} = \frac{1-v^n}{i^{(12)}}\)

in your calculations and it will work. Similarly, for monthly payments at the start of the month, you can use a discount rate convertible monthly: 

\(\left(1-\frac{d^{(12)}}{12}\right)^{12} = (1-d); \\ 1-\frac{d^{(12)}}{12} = (1-d)^{1/12}; \\ \frac{d^{(12)}}{12} = 1 - (1-d)^{1/12}; \\ d^{(12)} = 12\left(1 - (1-d)^{1/12}\right)\)

and then use 

\(\require{enclose} \ddot a_\enclose{actuarial}n^{(12)} = \frac{1-v^n}{d^{(12)}}\)

in your sums and have it work. 

Final thing: if you are making payments so frequently they might as well be continuous, you can use the force of interest

\(\require{enclose} \delta = \ln(1+i);\\ \bar a_\enclose{actuarial}{n} = \frac{1-v^n}{\delta}\)

Shortening mortgage lengths

Phew. Now we can actually do some stuff. 

I want to know the following. I take out a mortgage, payable monthly in advance, for 25 years. My very first payment will be double because I found some cash down the back of the sofa. Just the first one. At what rate of interest will this reduce the term to 24 years? 

First thing is "what is my monthly payment". This is quite easy. We have borrowed P as the principal, so my monthly repayment is 

\(\require{enclose} P = 12R\ddot a^{(12)}_\enclose{actuarial}{25}; \\ R = P\, /\, 12\ddot a^{(12)}_\enclose{actuarial}{25}\)

We then pay this at the start, and knock a year off the term:

\(\require{enclose} P - R = 12R\ddot a^{(12)}_\enclose{actuarial}{24}\)

Unfortunately you just have to do this by trial and error. But I can tell you, for a 25 year mortgage, an interest rate of 10.7% means you can knock a year off the term by making a double payment at the start.

Principal: £250,000

Interest rate: 10.7%

Annuity factor \(\require{enclose} \ddot a^{(12)}_\enclose{actuarial}{25} = 9.10348\)

Monthly payment: £2,288.50

So pay this immediately at the start, and it comes off the principal, so our mortgage is really £247,711.50.

Annuity factor with one year off: \(\require{enclose} \ddot a^{(12)}_\enclose{actuarial}{24} = 9.02016\)

Value of 24 years of repayments is \(\require{enclose} 12R\ddot a^{(12)}_\enclose{actuarial}{24} = 9.02016 \times 12 \ £2,288.50 = £247,711,63 \)

So actually we over pay by 13p. 

This is only a rough calculation - mortgage firms do things like allow for different numbers of days in each month, leap years etc and I've just gone a month is exactly 1/12 of a year with no bank holidays to worry about. But yes - if your 25 year mortgage APR is 10.7% you can knock a year off it with a double payment right at the start.

If you have a 30 year mortgage you need 8.81% for this to work, and for a 35 year term you need 7.5%, which I think some people might actually be on. 

 

I recently looked at my State Pension Forecast. There was a reasonably alarming statement 

• Contracted Out Pension Equivalent (COPE)
• Your COPE estimate is £x.yz a week

What is this? Well there was a bit of archaeology to do here. Below are my working notes. 

New State Pension

On 06 April 2016 the New State Pension came into force. You earn 1/35 of the full amount for every Qualifying Year (broadly, complete National Insurance year) you have after that date. Neat. But what about the older stuff? Well first you need to understand how the old stuff was calculated. This is the "starting amount" on to which very simple 1/35ths are added. 

Old State Pension

There was a myriad of older state pensions.

• Basic State Pension - similar to New State Pension, pay NI for a year to get get an increment of this (was recently 30y for full accrual)
• Graduated Retirement Benefit - ancient top-up pension that basically no-one gets and is so old I won't mention it again
• State Earnings Related Pension Scheme - here is where it gets interesting. From 1978 through 2002, you earned, over a full working life, a 20% top up based on a band of earnings. A full working life was from age 16 to state pension age. 
• State Second Pension - from 2002 through 2016, this was similar to SERPS but with different rules - e.g. a banded 40% / 10% / 20% accrual designed to make it more valuable for lower earners, eventually with flat rate accrual at the lower bands. 

You got NI Credits for some circumstances (e.g. staying in school for up to 3y after age 16). Also, you could "contract out" of SERPS and S2P in some circumstances, normally if you were in a defined benefit pension, where you paid lower NI and accrued no SERPS/S2P. This was the state subsidising your DB pension. 

To value your pre 06 Apr 2016 NI credits for state pension purposes, a few calculations are made. 

• First, your old state pension + S2P + SERPS entitlements are calculated.
• Second, your old state pension + S2P + SERPS entitlement is calculated as if you never contracted out and paid full NI instead. This is usually a bigger number. The difference between the first and second numbers is the COPE.
• Third, your old years are applied to the new rules. So if you had 20 years prior to 2016, you get 20/35 as the old pension amount. The COPE is deducted as well. 

The larger of the first and third numbers is used. So, if you contracted out (you usually didn't have a choice), you paid less NI and the value of your pre 2016 NI years is lower than your post 2016 NI years. 

Combined

You have post 2016 years which give you 1/35 of the full new state pension amount. Your pre 2016 years can be worth more or less than 1/35 depending on whether you were paying lower NI via contracting out (but see your DB pension you got in exchange). If you were contracted in you could have old years worth more than 1/35 as you get additional credits for SERPS and S2P. 

The COPE, as far as I can tell, only applies to the pre 2016 years. It is an adjustment applied to the starting amount for the years you were paying less NI. You can still earn up to the max by adding more qualifying years of NI. 

I tried calculating my COPE from my own incomplete records. Remarkably I get very close (within 1%). Issues:

Gotchas

The NI rebate for contracting out was flat rate but the S2P foregone was not. So if you earned below the breakeven point, you actually accrued a sliver of S2P to reflect that S2P was proportionately more valuable than the NI rebate below this level of earnings. The level of the sliver is the gap between SERPS style 20% accrual and S2P nonlinear accrual.

After some point the percentage of earnings accruals were replaced by flat rate accruals for the benefit of low earners and the scheme overall became less generous. 

You have to look up the revlaution of earnings order to adjust from the 2015/16 value to the latest value if you want to match the number shown on the state pension forecast. 

I've put together the following table of magic numbers you can use if you want for S2P calcs. 

Tax year	LEL	LET	SET	UEL	UAP	Flat Rate
2002/03	3,900	10,800	24,600	30,420
2003/04	4,004	11,200	25,600	30,940
2004/05	4,108	11,600	26,600	31,720
2005/06	4,264	12,100	27,800	32,760
2006/07	4,368	12,500	28,800	33,540
2007/08	4,524	13,000	30,000	34,840
2008/09	4,680	13,500	31,100	40,040	40,040
2009/10	4,940	13,900	31,800	43,875	40,040
2010/11	5,044	14,100	32,200	43,875	40,040
2011/12	5,304	14,400	32,600	42,475	40,040
2012/13	5,564	14,700	33,000	42,475	40,040	88.40
2013/14	5,668	15,000	33,700	41,450	40,040	91.00
2014/15	5,772	15,100	33,800	41,865	40,040	92.00
2015/16	5,824	15,300	34,300	42,385	40,040	93.60

Up to 2010, you got 40% on LEL to LET, 10% on LET to SET and then 20% on SET to UEL (UAP for last two years). For 2010/11 and 2011/12, you got 40% for LEL-LET and 10% up to the UAP. For the last stretch, you got the flat rate for any earnings above LEL and then 10% on LET-UAP. This is based on lifetime earnings, which are from age 16 to state pension age. You get 1/(state pension age - 16) times accrual.

There are arcane indexing rules - you need to revalue to 2015/16 amounts, calculate, and then revalue to current tax year.