topic Round 5 in BreakPoint

Fun Coding Challenges / Questions

BowenM — Thu, 11 Feb 2016 16:09:52 GMT

As I go through the forums or even work on my own projects I occasionally run across something that, after writing it up, I think "That was fun!" or "That was harder than I thought it would be".

So, let's post interesting questions or problems that you come across and let others see what answers they come up with.

Re: Fun Coding Challenges / Questions

BowenM — Thu, 11 Feb 2016 19:16:15 GMT

OK, so I meant to get this started earlier but got busy. I'll also admit that I shamelessly stole the idea from reddit, and so I am going to shamelessly steal the first puzzle. I don't expect later submissions to be this well written or extensive, but this one looked fun.

This exercise is inspired by a Numberphile video (no need to watch past 2:00).

Description

A number of sailors (let's call it N) are stranded on an island with a huge pile of coconuts and a monkey. During the night, each sailor (in turn) does the following without the others knowing:

He takes one N'th (e.g. if N=5, one fifth) of the coconuts in the pile and hides them
The division leaves one coconut left over, which is given to the monkey.

In the morning, they split the remaining coconuts between them. This time the split is even. There's nothing left over for the monkey.

Your task: Given the number of sailors (N), how many coconuts were in the pile to begin with (lowest possible number)?

Formal inputs/outputs Input

The input is a single number: N, the number of sailors. This number is a whole number that is greater than or equal to 2.

Output

The output is a single number: the number of coconuts in the original pile.

Sample input/output

Input:

Output:

Sample solution for 5 sailors: https://jsfiddle.net/722gjnze/8/

Credit

This challenge was originally suggested on /r/dailyprogrammer_ideas by /u/TinyLebowski (prior to some changes by me). Have a cool challenge idea? Hop on over to /r/dailyprogrammer_ideas to tell everyone about it!

Edit: Source: https://www.reddit.com/r/dailyprogrammer/comments/43ouxy/20160201_challenge_252_easy_sailors_and_monkeys/

Re: Fun Coding Challenges / Questions

bsvare — Thu, 11 Feb 2016 19:40:01 GMT

It's not an individual challenge, but I've fount the https://projecteuler.net/ website, and I've been attempting to go through all the puzzles here and attempt to solve in LabVIEW (only). They can get tough very quickly.

Re: Fun Coding Challenges / Questions

Darren — Thu, 11 Feb 2016 19:47:15 GMT

That was fun, I needed a break this afternoon. Once you get to 8 sailors it takes a while. 🙂

Re: Fun Coding Challenges / Questions

Ben — Thu, 11 Feb 2016 20:32:28 GMT

Funny you start his thread today because I was thinking about irational numbers.

I have a seven year old G-daughter that I have been sneaking in math lesson when she is not looking.

Is it even possible to contrive a test of irrationality in a computer environment where everything has to be entered as a rational number?

Ben

Re: Fun Coding Challenges / Questions

BowenM — Thu, 11 Feb 2016 21:45:16 GMT

Here is my attempt.

Re: Fun Coding Challenges / Questions

jcarmody — Fri, 12 Feb 2016 13:36:12 GMT

@Ben wrote:
Funny you start his thread today because I was thinking about irational numbers. [...]

Ben

Are irrational numbers the numbers engineers get from managers? Budgets, deadlines...

Re: Fun Coding Challenges / Questions

Intaris — Fri, 12 Feb 2016 20:12:51 GMT

I have a VI (it's actually two VIs, is that breaking some rules?) that computes the answer for 9 sailors in 10.8ms. Answer for 8 sailors takes 4.5ms.

I'll post them on Monday.

Re: Fun Coding Challenges / Questions

Intaris — Fri, 12 Feb 2016 23:50:35 GMT

Hmm, removing a recursive VI call and replacing it with a for loop gets my timing for the 8 sailor solution down to 0.4ms..... Funnily enough the 9 sailor solution only takes 1.4ms. Seems like the Recursive VI call overhead was pretty significant in the previous example. I'll tidy up the code and post both versions next week. I think I'll implement an I64 version to get to higher numbers.

Re: Fun Coding Challenges / Questions

altenbach — Sat, 13 Feb 2016 00:34:57 GMT

@Intaris wrote:
I have a VI (it's actually two VIs, is that breaking some rules?) that computes the answer for 9 sailors in 10.8ms. Answer for 8 sailors takes 4.5ms.

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

Re: Fun Coding Challenges / Questions

altenbach — Sat, 13 Feb 2016 05:27:51 GMT

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... 😄

Re: Fun Coding Challenges / Questions

Intaris — Sat, 13 Feb 2016 12:48:20 GMT

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

Re: Fun Coding Challenges / Questions

Intaris — Sat, 13 Feb 2016 12:49:46 GMT

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

Re: Fun Coding Challenges / Questions

altenbach — Sat, 13 Feb 2016 20:36:48 GMT

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

Re: Fun Coding Challenges / Questions

Intaris — Mon, 15 Feb 2016 10:47:41 GMT

@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.

Re: Fun Coding Challenges / Questions

altenbach — Mon, 15 Feb 2016 16:22:17 GMT

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. 😄

Re: Fun Coding Challenges / Questions

altenbach — Mon, 15 Feb 2016 16:58:17 GMT

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.

Re: Fun Coding Challenges / Questions

Darin.K — Mon, 15 Feb 2016 18:42:06 GMT

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.

Re: Fun Coding Challenges / Questions

altenbach — Mon, 15 Feb 2016 21:40:27 GMT

@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?

Re: Fun Coding Challenges / Questions

Darin.K — Tue, 16 Feb 2016 00:11:59 GMT

@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.