[Coco] Minesweeper

[Mark McDougall]

Mark McDougall wrote:

> Trouble is, shifting numbers takes time, although one can use mempcy for 
> example. But at least it's deterministic and order N, unlike re-throwing 
> 'darts' as your remaining squares diminish.

Actually, now that I've had a few more minutes to think about it...

You wouldn't actually need to store the numbers in an array. When you 
generate a new number, you only need to know how many numbers already 
chosen are numerically less than or equal to that number, and add that 
count to get the actual value you'll use.

So you need only to keep a (sorted?) list of numbers already chosen.

For example, suppose the 1st number is 42. Store that in the list. The 
2nd random number generated is 6. Since there are no chosen numbers 
below that, store 6 in the list. The 3rd random number is 78. Since we 
already have 2 numbers in the list below 78, we add 2 and store 80 as 
our 3rd number (since 80 would've been shifted down twice in our array).

Obviously, as the list length increases it takes longer to count the 
entries below the random number, but there are ways to speed the search, 
such as storing sorted lists, trees and/or using binary chop etc. But at 
some point, it's going to be quicker to use an array as I first 
suggested. It all depends on your worst-case scenario.

Regards,
Mark