1

There are 70 coins and out of which there is one fake coin. Need to detect the fake coin in minimum number of weighing. You have only a weighing scale and you know that the fake coin is lighter.

I am not sure if the below simulation of the problem is right or wrong i.e. representing it in a array and doing the comparison as i have done in my code. I am trying to simulate it with a array with all one's except one zero which is considered as fake coin. Below is my code. Please let me know if i have got it wrong.

It would be really be helpful if someone can prove/explain why 3 way division is better in simple maths.

Pseudo code for the below code:

INPUT    : integer n

if n = 1 then
   the coin is fake
else
   divide the coins into piles of A = ceiling(n/3), B = ceiling(n/3),
       and C = n-2*ceiling(n/3)
   weigh A and B
   if the scale balances then
      iterate with C
   else
      iterate with the lighter of A and B

Code:

import random

def getmin(data, start, end, total_items):
    if total_items == 1:
        #for sure we have a fake coin
        return (0, start)
    elif total_items == 2:
        if data[start] > data[end]:
            return (1, end)
        elif data[start] < data[end]:
            return (1, start)
    else:
        partition = total_items/3
        a_weight = sum(data[start:start+partition])
        b_weight = sum(data[start+partition:start+2*partition])
        c_weight = sum(data[start+2*partition:end])
        if a_weight == b_weight:
            result = getmin(data, start+2*partition, end, end-(start+2*partition))
            return (1+result[0], result[1])
        else:   
            if a_weight > b_weight:
                result = getmin(data, start+partition, start+2*partition, partition)
                return (1+result[0], result[1])
            else:
                result = getmin(data, start, start+partition, partition)
                return (1+result[0], result[1])

n = int(raw_input())
data = [1]*n
data[random.randint(0, n-1)] = 0
total_weighing, position = getmin(data, 0, len(data), len(data))
print(total_weighing, position)
newbie_old
  • 500
  • 5
  • 19
  • If you haven't yet determined whether you have a problem, you shouldn't post yet. Testing your program for you is not within the scope of SO. Simple code review belongs on the codereview site. – Prune Sep 26 '16 at 17:00
  • @Prune I am not looking to check my program. I am checking if my simulation with arrays is the right way of solving the fake coin problem. Code was given to just illustrate my problem in a better way. – noman pouigt Sep 26 '16 at 17:10
  • Got it; thanks. I retracted my close vote, and I'll edit that part out of my answer. – Prune Sep 26 '16 at 17:15

2 Answers2

3

The complexity of this algorithm is O(log3N) because you reduce your problem size to 1/3 in each iteration. Complexity-wise O(log3(n)) == O(log2(n)) == O(log10(n)) so it doen't matter if you divide your problem size by 3 or by 10. The only better complexity is O(1) and that means regardless of size of the problem you can find the fake coin in a fixed number of operations, which is quite unlikely.

Note that in this algorithm we assume that we can find the sum of a range of elements in O(1), Otherwise the algorithm's complexity is O(n).

Saeid
  • 4,147
  • 7
  • 27
  • 43
  • you just talked about complexity but what about simulating it with array and the code? Do you think i have got it right? – newbie_old Sep 25 '16 at 18:18
  • It seems fine. But to be sure you need to test it against lots of different tests. – Saeid Sep 25 '16 at 18:24
  • 1
    A minor nit -- it's not true that "the only better complexity is O(1)." See http://stackoverflow.com/a/16472013/2166798 for a counterexample. – pjs Sep 26 '16 at 02:02
1

You ask "why 3-way division is better in simple maths." Better than what? In this problem, it's the best solution because it achieves the answer in the fewest weighings. The properties of a trivial balance scale yield three basic results: left is heavier, right is heavier, and equal weights. That's a 3-way decision, so information theory yields that the best algorithm is to divide the objects in three (if you can practically achieve it) at each phase.

You need 4 weighings for 28-81 coins.

Fortunately, your problem allows for exhaustive testing. The code above performs one trial of random testing. That's okay for starters, but with only 70 cases to check, I recommend that you try them all. Wrap your main program in a loop over range(70), something like this:

n = 70
for bad_coin in range(70):
    data = [1]*n
    data[bad_coin] = 0
    total_weighing, position = getmin(data, 0, n, n)
    print ("trial", bad_coin)
    if total_weighing != 4:
        print ("Wrong number of weighings:", total_weighing)
    if position != bad_coin:
        print ("Wrong ID:", position)

This will quickly show any error in your program for the assigned 70 coins.

BTW, replace the if statements with assert, if you're comfortable with that feature.

Prune
  • 76,765
  • 14
  • 60
  • 81
  • Thanks but i have already tested it and it works in all cases. I was just looking to confirm if my solution with arrays is the right way of simulating the fake and genuine coins. http://puzzling.stackexchange.com/questions/18/learning-to-solve-a-river-crossing-puzzle if you see graph theory is used to simulate the problem and solve it. Same way i was wondering if my simulation with arrays is the best way to approach it. – newbie_old Sep 26 '16 at 17:58
  • It works, it's easy to understand and maintain, and it's reasonably efficient. Yes, this is an effective way to approach the problem. – Prune Sep 26 '16 at 18:35