La FÊe Verte
#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.
đ Dr. Freemo :jpf: đŗđą
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.
đ Dr. Freemo :jpf: đŗđą
@Absinthe
This was a lot of fun decided to do the problem by hand using non brute Force techniques. Attached are all the steps unused to solve the problem including the final solution on the last page.
Total number of coconuts is 3,121 at the start. The number of coconuts they ended up with was the following: 828, 703, 603, 523, 459
If your following the pages I attached the order in which you follow them is "knowns" then "reduce" then "final solution"
đ Dr. Freemo :jpf: đŗđą
Its the modulo math most people dont know. Once you understand how to solve for mosulo equations then the rest is actually kinda simple.
đ Dr. Freemo :jpf: đŗđą
Its the modulo math most people dont know. Once you understand how to solve for modulo equations then the rest is actually kinda simple.
đ Dr. Freemo :jpf: đŗđą
@Absinthe
This was a lot of fun decided to do the problem by hand using non brute Force techniques. Attached are all the steps I used to solve the problem including the final solution on the last page.
Total number of coconuts is 3,121 at the start. The number of coconuts they ended up with was the following: 828, 703, 603, 523, 459
If your following the pages I attached the order in which you follow them is "knowns/reduce" then "All valid values" then "final solution"
đ Dr. Freemo :jpf: đŗđą
I used to think the same, now im not so sure.
đ Dr. Freemo :jpf: đŗđą
@Absinthe They are readable here, should be good. Let me know if you have any questions on the math
zingbretsen
@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.
đ Dr. Freemo :jpf: đŗđą
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 :)
Bobinas P4G is a social network. It runs on GNU social, version 2.0.1-beta0, available under the GNU Affero General Public License.
All Bobinas P4G content and data are available under the Creative Commons Attribution 3.0 license.