Counterfeit Coins on a Pointer Scale

Question

You sell gold coins. Each gold coin you sell is supposed to be 1 ounce. However, you find out that one of your coin suppliers is cheating you. By alloying the gold material with something else, their coins weigh only 0.9 ounces. With a help of a pointer scale (one that shows the exact weight of a quantity of matter set on it), you want to determine which of your coin suppliers is selling you the counterfeit coins.

Apparently, you are not the only one to have this problem - lots of gold sellers buy coins from this supplier, and the supplier knows that it is being dodgy and is changing their branding accordingly. All of these sellers have the same problem - 1 ounce coins that end up being 0.9 ounces from this supplier - and need to solve it, fast! How can you determine, out of n suppliers, which one is the cheating supplier with the minimum number of weighings on the pointer scale?

---

Your task is to write a program function that can solve this problem automatically for n suppliers. It's input includes:

• an integer number of suppliers, n,
• an oracle function that represents weighing a set of coins on the balance scale

It must take this information, calling this function a minimum number of times and returning, as output, the index number of the cheating supplier.

The oracle function has the following specifications:

• It takes as input an int->int mapping (as an array or dictionary, whichever your language prefers) mapping each supplier index (from 0 to n-1) to a number of gold coins that you want to try weighing on the scale.
• The returned output is the total weight, in ounces, of the coins put on the scale.
• The function is in whatever format your language prefers for passing procedures as data. For instance, functional languages will pass lambdas, C will take a function pointer, Java 7 and earlier will take a functional interface. Languages that support none of these, but do support string execution, will take these as strings.
• In those cases when the oracle can be stringified or otherwise inspected as data, you may assume that it is sufficiently obfuscated such that you cannot tell which supplier is cheating without executing it.

This is also code-golf: among the solutions that call the function the minimum number of times, the smallest solution in bytes is the winner!

---

NOTE: If your language does not support functions at all, but does support string execution, write your program as a standalone program - assume that the number of suppliers, followed by the oracle, will be passed into standard input. If your language does not support string execution, assume that a file path to a binary oracle will be provided instead.

Answer 1

Python, 33 bytes

lambda n,f:n*~-n*5-f(range(n))*10

Puts 0 coins from supplier 0, 1 coin from supplier 1, ... n-1 coins from supplier n-1. The deficit is then 0.1 for each coin sent to the cheating supplier, so i/10. We therefore subtract the oracle value from the fair sum n*(n-1)/2 and multiply by 10. Distributing the *10 saved on parens for a shorter expression.

Answer 2

Python 2, 56 48 44 bytes

Uses 1 weighing

-8 bytes thanks to @feersum (use range(0,10*n,10))

def f(n,o):x=range(n);return(sum(x)-o(x))*10

Example runs at ideone

Places i coins from each of the suppliers i in [0,n-1] on the scale, subtracts the weighing from the total number of coins weighed and multiplies by 10.

(Python 3 will return float values that start to differ)

Answer 3

Mathematica, 23 Byte

5#(#+1)-1-10#2@Range@#&

Same approach as xnor. In Mathematica Range starts with 1, which is equivalent to using n+1 coins from the nth supplier. Hence, the formula for the fair sum is n(n+1)/2 and we have to subtract 1 from the result to restore zero-based indexing.

5#(#+1)-1-10#2@Range@#&[5,oracle]

149 - 10 oracle[{1, 2, 3, 4, 5}]

Answer 4

Pyth, 9 bytes

-FsMlBm*T

As o cannot be used for the oracle in Pyth (it takes in a lambda itself), I instead defined the oracle as l. Any one-input function other than s should work as the oracle. Returns 0-indexed input.

Explanation (assuming the 3rd vendor is the faulty one):

      m*T        Map d*10 over all d in range(input): [0, 10, 20, 30] for input = 4
    lB           Bifurcate over the oracle function: [[0,10,20,30],58.0]
  sM             Map sum (for arrays, floors numbers): [60,58]
-F               Fold over subtraction: 2  
                 Implicitly print

Try it online! (first line sets up the oracle function)

Try changing the faulty vendor! (The faulty vendor is 0-indexed: from 0 to first input - 1. Any other value will cast the blame on the 0th vendor.)