#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.
I do like the solution, and to my eye the code looks great. I could not get it to compile on :
https://rextester.com/l/python3_online_compiler
I might be doing something wrong though.
@zingbretsen @freemo that might do it :) Yep, works on 3.7 that will teach me to try a shortucut! :)
@zingbretsen @freemo Also, I think we need to include #toyprogrammingchallenge hashtag in the conversational posts of they are lost on other instances
@zingbretsen @freemo Things that sound dirty, but aren't...
Of course, everything is dirty if you just add "...if you know what I mean..." after you say it. :D
@zingbretsen
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 :)
@Absinthe