7
\$\begingroup\$

The twelve-balls problem is a famous problem where you are given twelve balls, one of which is a different weight, but you don't know whether it is heavier or lighter than the other balls. Using only three weighings of a two-sided scale, it is possible to find the differently weighted ball, and determine whether it is heavier or lighter.

Your task is to build a program that does the following:

  • Accept a number of balls N to be compared, from 8 to 100. (In the traditional problem, N = 12.)

  • Produce two lists of numbers, representing the balls to be placed on each side of the balance. An equal number of balls must be placed on each side.

  • Accept an input signifying whether the left side of the scale is heavier, the right side is heavier, or the two sides are equal (this can be represented any way you want to: e.g. -1 for left, 0 for equal, 1 for right, or 1 for left, 2 for right, and 3 for equal), and in response, either produce another pair of lists of balls to be weighed, or a guess as to which ball is the different one and whether it is heavier or lighter.

Your score is the sum of the maximum number of weighings for each value of N from 8 to 100 that it took to figure out the right answer for N balls using your algorithm (each case of "ball x is heavier/lighter" must be tested). Lowest score wins.

For example, if for N = 12, your algorithm managed to get 3 weighings for every case except "ball 8 is heavy" where it took 4 weighings, your score for N = 12 is 4. If your maximum score was 10 weighings for each N from 8 to 100, your final score would be 930.

Your algorithm must return the correct answer for all possible test cases (for any N, there are 2N possible test cases, which is a total of 10,044). In addition, the source code of your solution may not exceed 51,200 bytes (50 KB) in size.

\$\endgroup\$
  • \$\begingroup\$ To me it seems like the n=12 problem requires at least 4 weighings \$\endgroup\$ – Cruncher Nov 20 '13 at 21:35
  • \$\begingroup\$ Actually, it seems much harder than that... I can determine IF it's heavier or lighter in 3, but not the actual ball.. The quickest I can think of for finding the ball would be 5. In general it looks like 3 + log2(n/3) to be \$\endgroup\$ – Cruncher Nov 20 '13 at 21:40
  • \$\begingroup\$ Probably even harder for n not divisible by 3 \$\endgroup\$ – Cruncher Nov 20 '13 at 21:46
  • 1
    \$\begingroup\$ Nope. It's possible for 3 weighings: primepuzzle.com/leeslatest/12_ball_solution.html \$\endgroup\$ – Joe Z. Nov 20 '13 at 22:15
  • \$\begingroup\$ Also, I think I know what your basic method is - and determining whether the ball is heavier or lighter without finding out which ball it is actually only takes two weighings (if it's divisible by 3). So it's 2 + log3(n/3), not 3 + log2(n/3). \$\endgroup\$ – Joe Z. Nov 21 '13 at 1:34
1
\$\begingroup\$

Tcl, 455 426

proc weight n {
   set num [expr {int(log($n*2-1)/log(3))+1}]
   set len [expr {$n/3}]
   set pn 0
   set pri {2 5 7 11 13 17 19 23 29 31 37 41 43 59 61 67}
   for {set i 0} {$i < $num} {incr i} {
       set a {}
       while {![llength $a]} {
           set a {}
           set b {}
           set c {}
           while {
               ($n+1)%[lindex $pri $pn]==0
             ||($n-1)%[lindex $pri $pn]==0
             ||$n%[lindex $pri $pn]==0} {incr pn; puts $pn}
           set cpn [lindex $pri $pn]
           for {set j 0} {$j < $len} {incr j} {
               set tmp [expr {($j*$cpn)%$n}]
               lappend a $tmp
               incr tmp 1
               if {$tmp in $a} {set a {}; break}
               lappend b $tmp
           }
           incr pn
       }
       for {set j 0} {$j < $n} {incr j} {
           if {$j ni $a && $j ni $b} {lappend c $j}
       }
       puts "[lsort -integer $a] VS [lsort -integer $b] - Which is havier? -1 = left, 0 = equal, 1 = right"
       set idx [expr {[gets stdin] + 1}]
       if {$i == 0} {
           if {$idx == 1} {
               set p1 $c
               set p2 $c
           } elseif {$idx == 0} {
               set p1 $a
               set p2 $b
           } else {
               set p1 $b
               set p2 $a
           }
       } else {
           set lists [list $a $c $b]
           set p1 [lmap it [lindex $lists $idx] {if {$it ni $p1} continue; set it}]
           set p2 [lmap it [lindex $lists 2-$idx] {if {$it ni $p2} continue; set it}]
       }
   }
   if {[llength $p1]} {puts "Result $p1"} {puts "Result $p2"}
}
puts "Number of balls?"
weight [gets stdin]

No matter what you choose, the next question is always the same.

\$\endgroup\$
  • \$\begingroup\$ Note that this might not work for larger numbers than 100 (I'd have to add a prime factor generator, which I didn't do yet - the prime numbers are hardcoded.) \$\endgroup\$ – Johannes Kuhn Nov 21 '13 at 10:23
  • \$\begingroup\$ Ohh, and found a bug: Try to get 16 or 0 with 28 balls. \$\endgroup\$ – Johannes Kuhn Nov 21 '13 at 10:33
  • \$\begingroup\$ The optimal answer should be 428. Does your solution actually work for 13 or 40 balls? \$\endgroup\$ – Joe Z. Mar 28 '15 at 16:44
0
\$\begingroup\$

Python - 4929 weighings

A sketch of a trivial, last-place solution:

N = input("Enter number of balls: ")
a = 1
b = 2

print a, "|", b
first_result = input("Is left side heavy (1), right side heavy (2), or both equal (3)? ")

while(True):
    b += 1
    print a, "|", b
    result = input("Is left side heavy (1), right side heavy (2), or both equal (3)?")
    if result == first_result and result != 3:
        # ball 1 is our culprit.
        print "Ball 1 is %s." % ("heavier" if first_result == 1 else "lighter")
        break
    elif result != first_result and result == 3:
        # ball 2 is our culprit.
        print "Ball 2 is %s." % ("heavier" if first_result == 2 else "lighter")
        break
    elif result != first_result and first_result == 3:
        # ball b is our culprit.
        print "Ball %d is %s." % (b, "heavier" if result == 2 else "lighter")
        break

This solution simply continuously puts the first ball on the left side and a different ball on the right side, until it's found out that either the first ball is of a different weight, or one of the others is.

This takes a maximum of N-1 weighings for N balls (in any case where the last ball is the different one, N-1 weighings are required), which is 4929 weighings total.

\$\endgroup\$
  • \$\begingroup\$ This definitely looks like a sketch: you use Python 3.x's input() but Python 3.x uses print() instead of print \$\endgroup\$ – Justin Nov 20 '13 at 17:38
  • \$\begingroup\$ Hmm. It worked when I ran it through my Python 2 interpreter. \$\endgroup\$ – Joe Z. Nov 20 '13 at 20:22
  • \$\begingroup\$ I must be wrong... \$\endgroup\$ – Justin Nov 21 '13 at 1:06
  • \$\begingroup\$ @Quincunx input() in Python2 is the same as eval(input()) in Python3. \$\endgroup\$ – seequ Mar 28 '15 at 22:13
0
\$\begingroup\$

Tcl, 369

proc weight balls {
    if {[llength $balls] == 1 || [llength $balls] == 0} {return [lindex $balls 0]}
    set len [expr {([llength $balls]+1)/3}]
    set a [lrange $balls 0 ${len}-1]
    set b [lrange $balls $len [expr {$len*2-1}]]
    set c [lrange $balls [expr {$len*2}] end]
    puts "$a VS $b (0 = left side is havier, 1 = right side is havier, 2 = equal)"
    tailcall weight [lindex [list $a $b $c] [gets stdin]]
}
puts "Number of balls"
for {set i 1} \$i<=[gets stdin] {incr i} {lappend balls $i}
puts [weight $balls]

The algorithm is very simple: (try to) split the list in 3 equal parts (last can be different), weight the first 2, and do that again for the selected part (if equal, use the 3rd part)

\$\endgroup\$
  • \$\begingroup\$ Can you explain what your algorithm does? \$\endgroup\$ – Joe Z. Nov 20 '13 at 22:58
  • 2
    \$\begingroup\$ Sorry, forget it, I overread the you don't know whether it is heavier or lighter \$\endgroup\$ – Johannes Kuhn Nov 20 '13 at 23:15
  • \$\begingroup\$ Haha, yeah, if that's removed then the problem is trivial. \$\endgroup\$ – Joe Z. Nov 21 '13 at 0:04
0
\$\begingroup\$

JavaScript 1281

// Weigh function
function weigh(a,b) {
    weigh.count++;
    var len = a.length;
    if (len !== b.length) {
        throw({name:"NotEqual",message:"Can not compare."});
    }
    var wa, wb;
    wa = wb = 0;
    for(var i = 0; i < len; i++) {
        wa += a[i];
        wb += b[i];
    }
    return (wa === wb) ? 0 : (wa > wb) ? -1 : 1;
}
weigh.count = 0;

function findOddBall(arr) {
    var s = [arr];
    var isHeavy = true;
    var priorR = null;
    var left = null;
    var right = null;
    //console.log(arr);
    while(k=s.pop()) {
        //console.log('isHeavy:' + isHeavy + ' ' + k.slice(0));
        var len = k.length;

        if (len === 1) {

            if (priorR !== 0) {
                return [k[0], isHeavy]
            }

            var r = priorR = weigh([left[0]],k);

            if (r !== 0) {
                // we know that the oddball is one of these.. but which one?
                // we need to do a final comparison with the right side.
                priorR = r;
                r = weigh([right[0]],k);

                if (r === 0) {
                    // prior heavy/light
                    isHeavy = (priorR === -1)?true:false;
                    return [left[0],isHeavy]
                } else if(r === 1) {
                    return [k[0], true] // heavy
                }

                return [k[0], false] //light
            }           

            continue;
        }

        x = (len % 2 === 0) ? len : len-1;
        right = k.splice(0,x);

        if(k.length !== 0) {
            s.push(k); // remainder
        }

        left = right.splice(0,x/2);
        var r = priorR = weigh(left, right);
        if (r === 0) {
            // We chose a normal side. Test the other side.
            isHeavy = !isHeavy;             
        } else if ((r === -1 && isHeavy)|| (r === 1 && !isHeavy)) {
            s.push(right);
            s.push(left); // left is heavier / lighter
        } else if((r === 1 && isHeavy)|| (r === -1 && !isHeavy)) {
            s.push(left);
            s.push(right); // right is heavier / lighter
        }
    }
    throw({name:"NotFound",message:"Can not find oddball."});
}

function main() {

    var total = 0;
    var variations = 0;
    var start = 8;
    var end = 100;

    function test(isHeavy) {
        var normal = (isHeavy) ? 0 : 1;
        var oddball = (isHeavy) ? 1 : 0;
        var score = 0;
        var base = [];

        for (var i=0; i < start;i++) {
            base.push(normal);
        }

        for (var i=start; i <=end; i++) {
            base.push(normal);
            var max = 0;
            for (var j=0; j<i; j++) { // try each placement
                var arr = base.slice(0);
                arr[j]=oddball;
                variations++;
                weigh.count = 0; // reset the scale
                var result = findOddBall(arr);
                if (result[0] !== oddball || result[1] !== isHeavy) {
                    console.log(i);
                    throw({name:"WrongAnswer",message:"Returned wrong answer."});
                }
                if (weigh.count > max) {
                    max = weigh.count;
                }
                //console.log(variations);  
            }
            total+=max;
        }
    }

    test(true);
    test(false);

    console.log(variations);
    console.log(total);
}

main();
\$\endgroup\$
0
\$\begingroup\$

Python - ?

#recursive weighing method
def weigh(list, heavy):
    l=len(list)
    if l==1:
        return list[0]
    list1=list[0::3]
    list2=list[1::3]
    list3=[]
    if len(list1)>len(list2):
        list3.append(list1.pop())
    print("%s|%s"%(list1,list2))
    side=input("(0,1,2) for (neither,left,right) is %s"%heavy)
    if side==2:
        return weigh(list2, heavy)
    if side:
        return weigh(list1, heavy)
    for i in list[2::3]:
        list3.append(i)
    return weigh(list3, heavy)
#End Function, begin rest of program
#This part of the program is long because I need to determine whether the odd ball
#is heavy or light
list=range(input("Number of Balls: "))
#split the list into 3
list1=list[0::3]
list2=list[1::3]
list3=list[2::3]
#make list3 the odd man out, if there is one
if len(list1)>len(list2):
    list1,list3=list3,list1
print("%s|%s"%(list1,list2))
side=input("(0,1,2) for (neither,left,right) is heavier")
#if side==0
if not side:
    heavy="heavier"
    if len(list3)<len(list1):
        list3.append(list2.pop())
    elif len(list3)>len(list1):
        list2.append(list3.pop())
    print("%s|%s"%(list1,list3))
    side2=input("(0,1,2) for (neither,left,right) is heavier")
    if side2==1:
        heavy="lighter"
    print("%s: %s"%(weigh(list3, heavy),heavy))
else:
    if side==2:
        list1,list2=list2,list1
    if len(list3)!=len(list2):
        if len(list3)<len(list1):
            list3.append(list1.pop())
        if len(list3)>len(list2):
            list1.append(list3.pop())
        print("%s|%s"%(list2,list3))
        side2=input("(0,1,2) for (neither,left,right) is heavier")
        if not side2:
            print("%s: heavier"%weigh(list1, "heavier"))
        else:
            possibleAns = list3.pop()
            list3.append(list1.pop())
            print("%s|%s"%(list2,list3))
            side3=input("(0,1,2) for (neither,left,right) is heavier")
            if not side3:
                print("%s: heavier"%possibleAns)
            else:
                print("%s: lighter"%weigh(list2,"lighter"))
    else:
        print("%s|%s"%(list2,list3))
        side2=input("(0,1,2) for (neither,left,right) is heavier")
        if not side2:
            print("%s: heavier"%weigh(list1,"heavier"))
        else:
            print("%s: lighter"%weigh(list2,"lighter"))

This program works by dividing the balls into three lists, comparing them to see which of heavier or lighter the ball is, then recursively finds it.

\$\endgroup\$
  • \$\begingroup\$ I tried testing with 10 is heavier, but after the third weighing it threw an error involving a NoneType. The inputs that I put in were 2 0 0. \$\endgroup\$ – Joe Z. Nov 21 '13 at 1:19
  • \$\begingroup\$ @JoeZ. Should be fixed now. Have to laugh at the 50kb limit. I thought this file was big, but it is only 4kb. \$\endgroup\$ – Justin Nov 21 '13 at 6:14
  • \$\begingroup\$ The 50 KB limit is mostly to prevent blatant hardcoding solutions. Any actual algorithm (unless it's ridiculously complex) shouldn't get anywhere near that. \$\endgroup\$ – Joe Z. Nov 21 '13 at 6:18
  • \$\begingroup\$ Also, nope. The same inputs still throw the same NoneType error. Have you tried inputting 12 2 0 0? \$\endgroup\$ – Joe Z. Nov 21 '13 at 6:24
  • \$\begingroup\$ @JoeZ. I'm trying to get Python working on my computer so I can test it, so no, I have not. \$\endgroup\$ – Justin Nov 21 '13 at 6:32

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.