#toyprogrammingchallenge #python #lisp #c #c++ #cpp #coding #programming
Ready for the next challenge?
"5 Guys and a Bunch of Coconuts"
Here is a link to the text description of the problem.
https://git.qoto.org/Absinthe/coconuts/blob/master/coconuts.txt
That link is to the repo, and my solution is in it as well.
🇳🇱
I decided to take a stand at finding this solution mathematically without the brute Force approach applied in the source. I want to solve for the answer (the most efficient answer).
So far I framed the question mathematically and reduced. All I need to do is find the smallest value of T_R that produces Integer solutions for the following 5 equations and I will have a solution... I'll be finished soon hopefully.
@freemo surely it should be doable, as I proved out the result using 'bc' on the command line.
My work friend tried it in his head while doing a run the other day, and came up with a result far larger than appropriate.
Another friend solved it as a function that is nested 5 deep, and at the bottom it takes 5x as a starter.
f(f(f(f(f(5x)))))
With the function being f(i) {5/4 * i + 1}... Something like that. I think there was more to it than that, but once you found the right value for x it should all balance out. In that case I think you still had to figure out the x such that 5/4 x was equally divisible by 5. I guess that would still require some brute force testing.
@Absinthe @freemo I forked the repo and added my solution here: https://git.qoto.org/zingbretsen/coconuts/blob/master/coco.py
It should solve the 5 person problem when run as-is, but it could be run for any number of people. I should probably have added that as a command line argument.
It works backwards from possible ending amounts, but is somewhat selective in the numbers it tries. e.g., for the 5 person case, we know that the ending pile must be divisible by both 4 and 5, so the final pile will be a multiple of 20. In addition to that, we know that 5/4 + 1 of the ending pile must be divisible by 5, so 60 is the lowest number that would work for the first round of stepping backwards.
There is a regular pattern that seems to work for all of the numbers of people I tested, not just 5, so we can reduce the search space pretty significantly. For the 5 person problem, I only have to test 13 numbers before finding the answer.
very cool, I like how you try to limit the problem space for efficiency. Reminds me of common examples of primality checkers that use a sort of smart-brute force to reduce the problem space :)
