[Community puzzle] Magic stones

Puzzles
#1

This topic is about the puzzle Magic stones.

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

1 Like
#2

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

#3

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?

#4

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

#5

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.

#6

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.

#7

Dict solution is much more efficient when n==10000

1 Like
#8

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.

#9

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

#10

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?

#11

This is the input for test case 1:

2
1 1

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

#12

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]

#13

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)

#14

There is no such limit in Python.

#15

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.

#16

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

#17

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:

#18

if input is
1 2 1 2
out must be
2
not 1
or i didnā€™t understand

#19

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.

#20

I need a solution for C++ . Could you send me please ?