Fun Coding Challenges / Questions

[altenbach]

Starting with Bowen's and doing some experiementing, I got it down to well sub-microseconds up to N=15

(result for 15 Sailors is 437893890380859361 coconuts. We cannot go higher than 15 because of U64 overflow).

I also found a direct equation, which takes even faster (flickering between 0 and a few hundred ns using high resolution relative seconds).

Might be interesting to go to higher N using custom datatypes... 😄

[Intaris]

Yeah. There is a direct computation but that takes all the fun out of it.

[Intaris]

I also have a method to significantly speed up my method
Recognising repeating patterns is key.

[altenbach]

Since there is a real danger of overflow, here's a list of correct results as a function of N.

[Intaris]

---

@altenbach wrote:

Hmm, noticed some patterns and do 8 in under 2us. Have to work out the theory.... 😉

---

Regarding working out the theory.... I did it empirically.

I actually have my versions at home, so I can't post them quite yet but here's how I went about it.  I initially wrote a Reentrant VI  to recursively check step-by-step (one step for each sailor) if the answers at each stage were divisible by Sailors-1 (otherwise the reverse of "sailor takes his share" wouldn't work).  All arithmetic was done with integers only.  I stopped the recursion if the answer is non-integer or the total number of saolirs ahve been "processed".  Observing the pattern of "Recursion depth before failure" each iteration gives rise to a very clear pattern which allows some very obvious optimisations to be made (even without being totally sure on the maths of the whole thing).  One could adjust the step size in the search according to the last recursion depth and reduce the problem from an exponential time to a linear time problem with increasing number of sailors.  It's still a search but it comes relatively close to the direct methods.  Doing it this way, each new step actually automatically shifts to the next recursion depth, making the number of iterations required for the job to be approximately equal to the number of sailors instead of being hugely non-linear (more than 1000 times faster for calculating 11 sailors for example).  It was interesting how quickly the solution finding could be optimised on purely empirical observation.  Once I studied the sources in the internet, it was clear that even this approach was relatively inefficient, even though it's several orders of magnitude better than simple brute force methods.

I'll post more details later when I get home.  It was an interesting puzzle for a friday afternoon.  The fun part was seeing how far I could get without resorting to sources in the internet.

[altenbach]

---

Intaris wrote:. I did it empirically.

---

 Yup, same thing here. 😄 I started with Bowen's, but used a conditional inner FOR loop to break early, then graphed how many itertions it actually took. It was clear that only a few regularly spaced inputs were such candidates. By looking at the inputs, a few well recognized numbers appeared, so the offset and multipliers could be generated from first principles (different formula for odd vs even N). Then I also noticed that the number of while loop iterations to get there was also a linear function of the input, so it was possible to create code that immediately ended up at the correct value and I was able to eliminate the outer while loop. Well, sub-microseconds.

Whiile my calculation is actually quite different from the direct formula, it basically only takes one look and gets there. 😄

[altenbach]

Here's my empirical attempt. It is a bit circuitous. The other case contains the direct formula for comparison.

Both fail for N>15 due to limitations of U64, so it might be interesting to create a solution that can deal with higher digit counts.

[Darin.K]

Just using altenbach's code as a test point for my math library....

I didn't count all of the 9's but it looks right to my eye.  For 1000 sailors there are just a bunch more 9's in the middle.

[altenbach]

---

@Darin.K wrote:

Just using altenbach's code as a test point for my math library.....

---

Cool! You should use the code in the FALSE case instead....(algorithm)

(However, since the world harvest of coconuts is limited (1.44kg/nut, 62 millions tonnes/year), we will run out of coconuts much faster than we run out of sailors (or monkeys) :D. Then there is also the limiting factor of transporting and hiding coconuts in a single night.)

And yes, you even caught the duplicate effort of subtracting 1 from a number. (I assume the compiler will at least take it out of the FOR loop (loop invariant code elimination) but we still do it once too many. :D. It would be more hurful in your code...)

Oh, and wow, such a library would be great addition to LabVIEW!!! How complete is it?

[Darin.K]

---

@altenbach wrote:

Oh, and wow, such a library would be great addition to LabVIEW!!! How complete is it?

---

The integer part of the library is fairly complete, to the point I need to break up the class into separate libraries.  I have most of the basic operations covered, along with comparisons and bitwise operations.  A lot of number theory as well (prime testing GCD, modular exponentiation and the like).  

Mine is written in pure G because I am funny that way, but if this were to be built in I would probably put the guts 'under the hood' and leverage GMP.  I agree that arbitrary precision math as a first-class citizen would be awesome.  I like how ints in Python do their integery thing with no worries about overflow and such unless you deliberately bind them to a fixed representation.