rbeltran / binary_vs_trinary Goto Github PK

Searching for the lightweight coin binary vs trinary

Details:

You are give X coins. And You know all the coins weigh the same except one. One coin is lighter than all the rest. All you have is the coins and an old balance scale that tells if you either one side is heavier or they weights are equal. How do you find the light coin?

Binary search is fast right? You would think so. Either my code is bad or Trinary is the way to go here.

Run it like so:

ruby coin_finder.rb

Sample Output:

Binary search averaged 2 moves for 10 coins

Binary search averaged 8 moves for 100 coins

Binary search averaged 17 moves for 1000 coins

Binary search averaged 30 moves for 10000 coins

Binary search averaged 46 moves for 100000 coins

Trinary search averaged 2 moves for 10 coins

Trinary search averaged 6 moves for 100 coins

Trinary search averaged 12 moves for 1000 coins

Trinary search averaged 21 moves for 10000 coins

Trinary search averaged 31 moves for 100000 coins