### Random Post

### Recent Posts

- Tantalizer 450: Marriage problems
- Enigma 1057: Recycled change
- Enigma 452: Figure out these letters
- Puzzle 46: I lose my specs
- Enigma 1058: A row of colours
- Enigma 451: Double halved
- Tantalizer 451: Death rates
- Enigma 1059: Century break
- Enigma 450: A pentagonal problem
- Puzzle 48: Verse on the island

### Recent Comments

Jim Randell on Tantalizer 450: Marriage … | |

Brian Gladman on Enigma 1057: Recycled cha… | |

Jim Randell on Enigma 1057: Recycled cha… | |

geoffrounce on Enigma 452: Figure out these… | |

Jim Randell on Enigma 452: Figure out these… |

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (50)
- teaser (3)

### Site Stats

- 184,975 hits

Advertisements

This isn’t the fastest program, but it is short and it does find the maximum score. It plays the game recursively, eliminating choices that cannot beat the current maximum. For N=35 it takes 6m14s to run to completion (although it does find the maximum score after a few seconds). It should be possible to write a more sophisticated program that has shorter run times.

Solution:The maximum score for N=35 is 145.One possible sequence is (17, 16, 15, 14, 13, 12, 10, 6, 9, 4, 2, 11, 3, 7, 5, 1).

Overall there are 75,600 different sequences that produce a maximum score.

This program is much faster. For the N=35 case it runs in 40ms.

It works by looking for a sequence that allows it to play all the numbers available. Clearly 1 must be played last, and we can’t play any number greater than N/2, so the only possible numbers that can be played before 1 are those from 2 to N/2. This program considers subsets of these numbers, in order of decreasing sum until it finds a playable sequence. And this is the maximum achievable total.

This one was very interesting and I wonder if Stephen Ainley was being kind to puzzlers since 35 is the largest value for which a simple startegy of minimising the sum of the values removed by the Angel in each step works.

Brute force recursion plus memoization: