Build a solver for the "N balls on a scale" problem

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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)

Answer 4

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.

Answer 5

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();