[Community Puzzle] Gravity Centrifuge Tuning

Puzzles
#1

https://www.codingame.com/training/medium/gravity-centrifuge-tuning

Send your feedback or ask for help here!

#2

A post was merged into an existing topic: Community Puzzle - Gravity Centrifuge Tuning calcul

#3

Gravity Centrifuge Tuning is very instructive. I suggest everyone to read the titles of the tests to get a clue.

There is one test that is at odds with the puzzle description though. The “Constraints” section states that “N > 0”, but the “Wait, what?” test sets N to 0. It’s probably easier to amend the constraint. If you solve it before the text is changed… be aware of that.

2 Likes
#4

I have just updated the constraints section.
Thanks for your carefulness.

2 Likes
#5

Hihi,

If you finished the puzzle “Gravity Centrifuge Tuning” (Coding Games and Programming Challenges to Code Better)
would you mind explaining me the calcul method since i dont get it !!
From what i understood the “tumbles potential” of each bit is:
0 ->1
10 ->1+1=2
100 → 1+2=3
1000 → 2+3=5
10000-> 3+5=8
100000 → 8+5=13
and so on.
So, for the input 9, i guess that the output should be 9=8+1(1001) but the testcase expect me to answer 21(10101) ??!!
I am a bit lost …
Thanks for your help !!

#6

Have a look at the name of that testcase :wink:

1 Like
#7

Beautiful puzzle. I enjoyed it a lot :slight_smile:

Zeckendorf can indeed be proud

Kudos to the puzzle writer. Very very elegant.

2 Likes
#8

Hi, I’m trying to solve this puzzle with javascript,
Any clue how to manage the integer overflow?

Seems there is no BigInt() library (on spidermonkey compiler), how I’m supposed to save N (number of tumbles) like on the last test:
"Zeckendorf would be proud of you"?

Even if somehow I managed to work on it’s string representation, and find the binary bitstream (as string), how I can convert the bitstream to octal without overflow?

#9

You are correct that this is much harder in some languages due to the lack of bignum support . For the conversion at the end you can work a single character at a time - every 3 binary bits is one octal character.

#10

Well ok it’s harder (and honestly, why would you use such languages when there are alternatives available? I digress), but I take offense at the “much harder” distinction: if your algorithm is sound, you don’t need any of the “hard” operations, and you can trivially implement them all on a string or bitfield or whatever.

That’s supposed to be way easier than the initial conversion from decimal to your internal representation, whatever it is.

#11

You don’t think it’s a bug that I can’t use BigInt()? (there is BigInt() in node but not in spidermonkey).

How is it possible to find the N tumbles if I can’t reach the number due the overflow?

You can see that the puzzle starts with var N = BigInt(readline()); example:

But you get

Errors
ReferenceError: BigInt is not defined
at Answer.js.null on line 6

image.png1426×728 229 KB

I’ll try explain the problem:

The way I’m trying to solve is building N, from then is just binary to octal.
but I can’t get to N (in node.js I can) due the overflow.

#12

I see three ways do solve that:

  • Find a smarter solution that doesn’t rely on big integers (for this problem I don’t think there is one)
  • Write your own BigInteger functions
  • Use another language that supports it (C# and Java have BigInteger libraries for example, Python supports them natively)
#13

I don’t get the point with this ‘octal’ conversion.
And the following extra rule just add more to the confusion:

Damaged Gravity Centrifuges
The Gravity Centrifuge you’ve got access to has a cooling issue that hasn’t been fixed yet. On your damaged Gravity Centrifuge, if two consecutive bits in the bitstream are set, the twin inertial drive overheats and burns down.
So don’t do that.

As far as I understand the solution is to insert a ‘0’ bit between each pair of ‘1’ consecutive bits, Am I right ?

Any help will be greatly appreciated

#14

It’s not strictly needed to understand it to solve the puzzle. It’s just there as an extra optimization enabler… for those who see it.

No, no, that’s not the idea It’s not an “extra rule” to confuse people, it’s there as an additional constraint to the allowed solutions. (as a problem setter, I needed because without it I can’t have a unique validator output).

See it this way: among the possible solutions to the problem, only output one that wouldn’t overheat.

1 Like
#15

For people who are not into maths, “medium” difficulty can be misleading.
This puzzle is based on a theorem and a method you’ll have to lookup if you don’t know it already. Trying to come up with a solution by trial and error is a total waste of time.
The needed keyword is hidden somewhere. Look closely and you’ll find it.

#16

Once the trick is found, 98% of the code is already done.
How disappointing…

#17

I really enjoyed this one.

There was a potential greedy solution but I didn’t try it cause I thought that it wasn’t guaranteed to work all the time so I went for a systematical recursive search.
And then I checked others solutions and saw that most of them used the greedy solution I was thinking of.
So I wondered if it was luck or not, if the greedy solution was always successful, and ended up demonstrating that it was indeed always successful.

It’s always nice to see that an intuitive solution has actually solid foundations.

2 Likes
[Community Puzzle] Gravity Centrifuge Tuning