4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – AdmBorkBork Sep 15 '16 at 20:41
  • \$\begingroup\$ Also related. \$\endgroup\$ – AdmBorkBork Sep 15 '16 at 20:41
  • 1
    \$\begingroup\$ If you know that exactly one supplier is cheating, and you know the exact weights involved, and you are allowed to use any number of coins per weighing, then I'm pretty sure you can identify the cheater in one weighing regardless of how many suppliers there are. \$\endgroup\$ – Greg Martin Sep 15 '16 at 21:01
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)

\$\endgroup\$
  • 1
    \$\begingroup\$ [i*10for i in range(n)] saves a byte. \$\endgroup\$ – mbomb007 Sep 15 '16 at 21:50
  • 1
    \$\begingroup\$ Better yet, range(0,10*n,10). \$\endgroup\$ – feersum Sep 15 '16 at 21:51
  • \$\begingroup\$ @feersum Oh, yeah. I wasn't even paying attention to the right half of the comprehension. \$\endgroup\$ – mbomb007 Sep 15 '16 at 21:52
  • \$\begingroup\$ Even if you didn't know about 3-argument range, def f(n,o):x=range(n);return(sum(x)-o(x))*10 would be much shorter so how did you conclude that multiplying by 10 in the input would be better? \$\endgroup\$ – feersum Sep 15 '16 at 21:56
  • \$\begingroup\$ @feersum because I didn't think that passing the range was an option :) \$\endgroup\$ – Jonathan Allan Sep 15 '16 at 21:57
1
\$\begingroup\$

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}]

\$\endgroup\$
1
\$\begingroup\$

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.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.