7
\$\begingroup\$

You are the treasurer and you have received information that a counterfeit coin has entered the treasury. All you know is that the counterfeit coin is lighter than the original.

Knowing how many coins you have in total and using only a balance scale, you need to determine the minimum number of weighings to determine which coin is counterfeit before it disappears from the treasury.


Your function must accept only one integer (which will be more than 1) and must output 2 things:

  • the minimum number of weighings without lucky chances
  • steps on how to find counterfeit coin

Step - a moment when you use balance scale

Without lucky chances means that your number must be the maximum among the minimum steps required. For example let's say that you have 5 coins:

  1. You can split them to 3 groups by 2, 2 and 1 (this isn't a step)

  2. Weighing the groups 2 and 2 (this is a step)

    2.1 If they are equal then the remaining coin is counterfeit

    2.2. If one of the groups is lighter then the counterfeit coin is in that group

  3. Weigh each remaining coin (this is a step)

    3.1 The coin that is lighter is the counterfeit coin

So the minimum number of weighings without lucky chances is 2 but with lucky chances it is 1 because we can find the counterfeit coin at step 2.

The output steps must be easy to understand. Please add a detailed explanation of how to read the output steps. For example the previous example can be represented like this:

[5(2,2) 2(1,1)] - 2

Where the:

  • [] - means the possible scenarios
  • x(y,z) - x means remaining coins after previous step, (y,z) means how many coins (from x) on each side of balance scale I am weighing
  • 'space' - means the next step/scenario
  • - x - means the minimum number of weighings without lucky chances

Here is an example with 8. The output can be shown like this:

[8(3,3) [2(1,1)] [3(1,1)]] - 2

After first step we have two different scenarios because:

  1. if the 2 groups of 3 are equal then the counterfeit coin is in the group of 2 coins
  2. if the 2 groups of 3 aren't equal then the counterfeit coin is on one of the groups of 3

It is enough to to weigh only 2 different coins in each scenario to find the counterfeit coin. Regardless of the scenario, the minimum number of weighings without lucky chances is 2

Here are the possible outputs for 2 to 9 coins:

2 --> [2(1,1)] - 1

3 --> [3(1,1)] - 1

4 --> [4(2,2) 2(1,1)] - 2

5 --> [5(2,2) 2(1,1)] - 2

6 --> [6(2,2) 2(1,1)] - 2

7 --> [7(3,3) 3(1,1)] - 2

8 --> [8(3,3) [2(1,1)] [3(1,1)]] - 2

9 --> [9(3,3) 3(1,1)] - 2

You can output any of the possible steps of how to find the counterfeit coin. For example for 10 we have 5 different scenarios. You can output any of them:

10 --> [10(5,5) 5(2,2) 2(1,1)] - 3
10 --> [10(4,4) [2(1,1)] [4(2,2) 2(1,1)]] - 3
10 --> [10(3,3) [3(1,1)] [4(2,2) 2(1,1)]] - 3
10 --> [10(2,2) [2(1,1)] [6(3,3) 3(1,1)]] - 3
10 --> [10(1,1) 8(3,3) [2(1,1)] [3(1,1)]] - 3

The shortest code in each programming language wins!

\$\endgroup\$
3
  • \$\begingroup\$ Reminds me of this. :-) \$\endgroup\$
    – Arnauld
    Feb 14 at 10:06
  • \$\begingroup\$ Nice question! I've made a slightly extensive edit to improve grammar. If I somehow changed the intent of the question, feel free to revert it. \$\endgroup\$
    – Seggan
    Feb 14 at 16:00
  • \$\begingroup\$ @Seggan Your edits are amazing, I checked everything is okay. Thank you! \$\endgroup\$
    – EzioMercer
    Feb 14 at 16:02

4 Answers 4

3
\$\begingroup\$

Python, 77 bytes

-4 from @TheThonnu

f=lambda n:n<4and[1]or(m:=-~n//3,p:=n-2*m,f(m),f(p),max(f(m)[-1],f(p)[-1])+1)

Attempt This Online!

If input is 2 or 3, returns [1] meaning only one trivial weighing is required, otherwise returns a 5-tuple (number of coins to weigh on each side at this step, number of coins to set aside at this step, steps to follow with the lighter side of coins if there was a lighter side, steps to follow with the set-aside pile if the scale balanced, worst-case number of steps required). Naturally the third and fourth elements of the tuple recurse.

\$\endgroup\$
3
  • \$\begingroup\$ 77 \$\endgroup\$
    – The Thonnu
    Feb 16 at 9:19
  • \$\begingroup\$ Could you explain it? For 10 your output will be (3, 4, [1], (1, 2, [1], [1], 2), 3). Shouldn't the second [1] be [0]? Because if you weighing just 2 coins you don't need any other steps if there is lighter side \$\endgroup\$
    – EzioMercer
    Feb 17 at 3:10
  • \$\begingroup\$ @EzioMercer It merely indicates any trivial case. \$\endgroup\$ Feb 17 at 5:49
2
\$\begingroup\$

Charcoal, 44 bytes

⊞υNW⊖⌈υ«≔⊕÷⊖ι³θ≔⁺⁻υ⟦⊕ι⟧⟦θ⁻⊕ι⊗θ⟧υ⟦⪫⟦⊕ιθL↨ι³⟧ 

Try it online! Link is to verbose version of code. Outputs sets of three integers: coins left, coins to weigh (per side), worst case number of remaining weighings. Explanation: Inspired by @ParclyTaxel's Python answer.

⊞υN

Start with n coins.

W⊖⌈υ«

Repeat until there is only 1 coin left.

≔⊕÷⊖ι³θ

Calculate how many coins to weigh.

≔⁺⁻υ⟦⊕ι⟧⟦θ⁻⊕ι⊗θ⟧υ

Update the set of possible numbers of remaining coins.

⟦⪫⟦⊕ιθL↨ι³⟧ 

Output the coins left, coins to weigh and steps left.

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

Mathematica, 106 bytes

Modified from @Parcly Taxel's answer


Golfded version, try it online!

Module[{m,p,fm,fp,maxF},If[n<4,{1},m=-⌈BitNot[n]/3⌉;p=n-2*m;{m,p,f@m,f@p,Max[Last@*f@m,Last@*f@p]+1}]]

Ungolfed version

f[n_] := Module[
  {m, p, fm, fp, maxF},
  If[n < 4,
    {1},
    m = -Ceiling[BitNot[n]/3];
    p = n - 2*m;
    fm = f[m];
    fp = f[p];
    maxF = Max[Last[fm], Last[fp]] + 1;
    {m, p, fm, fp, maxF}
  ]
]


f[73]//Print
\$\endgroup\$
0
\$\begingroup\$

Python, 2551 bytes,

import math

def find_counterfeit_coin(num_coins):
    steps = []
    
    # Base case
    if num_coins == 2:
        steps.append((2, (1, 1)))
        return 1, steps
    
    # Determine the largest power of 3 less than num_coins
    power = math.floor(math.log(num_coins - 1, 3))
    group_size = 3 ** power
    
    # First weighing
    remaining_coins = num_coins
    while remaining_coins > 2 * group_size:
        steps.append((remaining_coins, (group_size, group_size)))
        remaining_coins -= 2 * group_size
    
    # Split remaining coins into groups of size group_size or less
    group_sizes = []
    while remaining_coins > group_size:
        group_sizes.append(group_size)
        remaining_coins -= group_size
    if remaining_coins > 0:
        group_sizes.append(remaining_coins)
    
    # Weigh each group
    for group in group_sizes:
        if group == group_size:
            steps.append((group, (group_size, group_size)))
        else:
            steps.append((group, (1, 1)))
    
    # Determine which group contains the counterfeit coin
    if len(group_sizes) == 1:
        num_weighings = power + 1
        return num_weighings, steps
    
    elif len(group_sizes) == 2:
        if group_sizes[0] == group_sizes[1]:
            num_weighings = power + 1
            return num_weighings, steps
        else:
            num_weighings = power + 2
            steps.append((group_sizes[0], (1, 1)))
            return num_weighings, steps
    
    else:
        # Combine two groups of equal size to create a larger group
        combined_group_size = group_size * 2
        combined_groups = [sum(group_sizes[i:i+2]) for i in range(0, len(group_sizes), 2)]
        
        # Recursively find the counterfeit coin in the larger group
        recursive_weighings, recursive_steps = find_counterfeit_coin(sum(group_sizes))
        num_weighings = power + recursive_weighings
        
        # Add steps for weighing the smaller groups
        for group in combined_groups:
            steps.append((group, (1, 1)))
        
        # Add steps from recursive call
        steps += recursive_steps
        
        # Weigh the two groups that produced the combined group
        for i in range(0, len(group_sizes), 2):
            if group_sizes[i] == group_sizes[i+1]:
                steps.append((combined_group_size, (group_sizes[i], group_sizes[i+1])))
            else:
                steps.append((combined_group_size, (group_sizes[i], combined_group_size - group_sizes[i])))
        
        return num_weighings, steps

Attempt This Online!


Though it can be considered as an algorithm, it is a pathway for others to write short code from it.

This solution uses a recursive approach to find the minimum number of weighings required to find the counterfeit coin. The algorithm works by dividing the coins into groups and weighing the groups against each other, gradually reducing the number of remaining coins until the counterfeit coin is found. The number of groups and their sizes are chosen so that the maximum number of coins are weighed at each step.

The output of the function is a tuple containing the minimum number of weighings and a list of tuples representing the steps taken to find the counterfeit coin. Each tuple in the list represents a weighing, and contains the number of coins weighed and the sizes of the groups weighed against each other. The steps can be interpreted as a tree, where each level represents

\$\endgroup\$
9
  • \$\begingroup\$ The program works and I am not Tony Stark with a nano-tech equipped, rather being a 16 years old kid so I could not write shortest answer. Sorry :) \$\endgroup\$
    – user116868
    Feb 14 at 14:35
  • 6
    \$\begingroup\$ You can :) Remove the all comments, change the all variable names and functions names to one letters, remove all unnecessary spaces. It will reduce the size of your code \$\endgroup\$
    – EzioMercer
    Feb 14 at 14:56
  • \$\begingroup\$ For the 20 coins it is only need 3 weightings and you output 3 - it is correct. But not all steps are displayed. Your output is [(20, (9, 9)), (2, (1, 1))] there are no steps how to find the counterfeit coin in 9 coins \$\endgroup\$
    – EzioMercer
    Feb 14 at 15:00
  • \$\begingroup\$ In the footer, I created a function, find_counterfeit_coin(), where you can enter any coin number \$\endgroup\$
    – user116868
    Feb 14 at 15:45
  • 3
    \$\begingroup\$ Please keep in mind that there's no reason you can't also maintain an ungolfed solution. Site policy just requires your solution itself to have some minimal amount of golfing effort put in. \$\endgroup\$ Feb 15 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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