theburningmonk.com

Prob­lem

Some pos­i­tive inte­gers n have the prop­erty that the sum [ n + reverse(n) ] con­sists entirely of odd (dec­i­mal) dig­its. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such num­ber­sre­versible; so 36, 63, 409, and 904 are reversible. Lead­ing zeroes are not allowed in either n or reverse(n).

There are 120 reversible num­bers below one-thousand.

How many reversible num­bers are there below one-billion (10⁹)? 

Solu­tion

The solu­tion I have posted here solves the prob­lem but it takes a good 15 mins or so to run so doesn’t meet the 1 minute rule.. unfor­tu­nately brute force is the only way I know how to solve this problem :-(

Prob­lem

The num­ber 145 is well known for the prop­erty that the sum of the fac­to­r­ial of its dig­its is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Per­haps less well known is 169, in that it pro­duces the longest chain of num­bers that link back to 169; it turns out that there are only three such loops that exist:

169 363601 1454 169

871 45361 871

872 45362 872

It is not dif­fi­cult to prove that EVERY start­ing num­ber will even­tu­ally get stuck in a loop. For example,

69 363600 1454 169 363601 ( 1454)

78 45360 871 45361 ( 871)

540 145 ( 145)

Start­ing with 69 pro­duces a chain of five non-repeating terms, but the longest non-repeating chain with a start­ing num­ber below one mil­lion is sixty terms.

How many chains, with a start­ing num­ber below one mil­lion, con­tain exactly sixty non-repeating terms?

Solu­tion

The solu­tion I have here caches the pre­vi­ous results to avoid dupli­cated work, this com­pli­cates the code slightly but it should still be fairly easy to fol­low. The key thing here is the recur­sive func­tion process­Chain­Rec which recur­sively gen­er­ate the next num­ber in the chain until it hits one of two conditions:

1. you hit a num­ber already in the chain (hence the end of the non-repeating chain)

2. you hit a num­ber whose non-repeating chain length has been cached

In the first case, sup­pose you have [69, 363600, 1454, 169, 363601] in the list already, and then the next num­ber is 1454, which is in the list with index 2. At this point, you can work out the non-repeating chain length for 69, 363600 and 1454:

69 : list.length – index = 5 – 0 = 5

363600 : list.length – index = 5 – 1 = 4

1454 : list.length – index = 5 – 2 = 3

Hit three eggs with one stone? Awesome

For the sec­ond case, sup­pose you had already come across 1454 before and have already cal­cu­lated its non-repeating chain length, now you have [69, 363600] in the list and 1454 pop outs of the hat. So a quick look up in the cached data tells you that 1454 has a non-repeating chain of 3 terms, so to apply that knowl­edge to 69 and 363600:

69 : list.length – index + 3 = 2 – 0 + 3 = 5

363600 : list.length – index + 3 = 2 – 1 + 3 = 4

Voila!

Prob­lem

Peter has nine four-sided (pyra­mi­dal) dice, each with faces num­bered 1, 2, 3, 4.
Colin has six six-sided (cubic) dice, each with faces num­bered 1, 2, 3, 4, 5, 6.

Peter and Colin roll their dice and com­pare totals: the high­est total wins. The result is a draw if the totals are equal.

What is the prob­a­bil­ity that Pyra­mi­dal Pete beats Cubic Colin? Give your answer rounded to seven dec­i­mal places in the form 0.abcdefg

Solu­tion

Prob­lem

By count­ing care­fully it can be seen that a rec­tan­gu­lar grid mea­sur­ing 3 by 2 con­tains eigh­teen rectangles:

Although there exists no rec­tan­gu­lar grid that con­tains exactly two mil­lion rec­tan­gles, find the area of the grid with the near­est solution.

Solu­tion

This prob­lem looks more dif­fi­cult than it is, I’m not going to go into the details here but basi­cally the num­ber of rec­tan­gles inside a x by y grid can be cal­cu­lated as:

The rest is fairly easy, just pick a range of x and y val­ues you want to try and brute force it!

Prob­lem

In the 5 by 5 matrix below, the min­i­mal path sum from the top left to the bot­tom right, by only mov­ing to the right and down, is indi­cated in bold red and is equal to 2427.

Find the min­i­mal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file con­tain­ing a 80 by 80 matrix, from the top left to the bot­tom right by only mov­ing right and down.

Solu­tion

I took a sim­i­lar approach to the one I used for prob­lem 18 and iter­a­tively work out what’s the short­est path sum lead­ing up to each of the cells in the matrix.

Con­sid­er­ing that a brute force approach will need to walk through the 80 x 80 matrix a total of 92045125813734238026462263037378063990076729140 times…so that’s clearly not an option! So instead, for each cell (x, y) in the matrix, we con­sider the two possibilities:

1. the path has tra­versed down from cell (x-1, y)

2. the path has tra­versed right from cell (x, y-1)

the short­est path sum from top left to (x, y), let’s call it sps(x, y) will be equal to the lesser of sps(x-1, y) + (x, y) and sps(x, y-1) + (x, y). Obvi­ously there are some spe­cial cases, such as when x = 0 and when y = 0, as you can see the dif­fer­ent han­dling in the match pattern.