[Community puzzle] Magic stones

This topic is about the puzzle Magic stones.

Feel free to send your feedback or ask some help here!

1 Like

There is a one trailing space in last test & validator. This is not a big problem, but it would be nice to fix it to avoid surprises in languages in which string.split() includes empty entries by default

For my Python and Javascript solutions, validators 1, 2, 3 and 5 are failing, while the test cases work fine. My C++ solution using the exactly same algorithm does pass the validators with 100% though. Maybe there is an issue with the validator input data?

Maybe your solution is not correct.
My Python 3 solution is 100% valid.

1 Like

Indeed, my solution was not correct. Now I also have 100% with the Python3 version, my dictionary approach didn’t work as expected, so I switched to a simple list.

I got 100% with python using a list, but I was worried that because I had to re-sort the list every time a stone was incremented that it would be to inefficient. I wonder if the dict approach is more efficient? I may go back and try it to find out.

Dict solution is much more efficient when n==10000

1 Like

In python3, the solution was already written when i opened the puzzle… sad for me…

I haven’t checked for all languages but it looks like only python3 was concerned.

Any stub will pass the first two tests as the expected output is 1. But the other tests will fail. Maybe 2 first test cases could be changed

I don’t understand the problem statement.
I thought, for instance, when I have two stones with value i = 1, then I can combine them to get a stone of level 2. - combining two stones of i = 3, it would be 4 etc. But that is not how it works, when I look at the tests:

The first test case gives two stones one with level 1 and one with level 11. So how can I combine them, so that I get only one stone - as this is the expected answer?

This is the input for test case 1:

2
1 1

2 stones of level 1 . You understood the problem statement the right way.

blush I see, thank you, I had an error in my logging.[quote="_CG_Thibaud, post:11, topic:2412, full:true"]
This is the input for test case 1:

2
1 1

2 stones of level 1 . You understood the problem statement the right way.
[/quote]

Currently this puzzle can be solved without list or dict, by adding powers of 2 with the stones levels as exponents: these powers properties will handle the “fusion” of levels, and the final number of stones equals the nb of ‘1’ in the binary decomposition of the final sum.
Such a solution is obviously not available as soon as the resulting sum exceeds the max representable integer.
Test cases & validators should then be updated with higher values to exclude such an approch (which was probably not desired)

There is no such limit in Python.

But since there is in some other languages, test cases should be updated to take it into account and exclude this kind of invalid solution.

Sounds like a job for BigInteger. I think most languages have something like that.

Not natively in C++ (or not that I know of), even though there are plenty of libs for this out there.
But thx for the hint, I’ll do a Java version then :slight_smile:

if input is
1 2 1 2
out must be
2
not 1
or i didn’t understand

shosha, I think you are correct.
1 and 1 combine as 2.
2 and 2 combine as 3.
So the stones left will be 2 and 3.