# Four weights to produce integer scale differences from 0 through 40 pounds

Just-in-time edit: I decided to reveal part of the answer and highlight a single aspect of the challenge.

Show how 4 weights, of 1, 3, 9, and 27 lbs. can be used to produce "weight differences" from 0 to 40 lbs.

You have a two - pan balance scale.

We define the difference in pan weights as the total weight placed on the left pan minus the total weight on the right pan.

The difference in pan weights for the empty scale is 0 lbs.

You have 4 rocks, a,b,c, and d, weighing 1, 3, 9 and 27 lbs respectively

Show how you can produce all integer weight differences from 0 to 40 lbs.

Simpler example:

Problem: With weights of 1 and 3 lbs. show how you can generate all weight differences from 0 to 4 lbs.

Output: for a=1, b=3; For the 4 weight, 40 pound version, your output should consist of a table with columns displaying the weight difference, the symbolic amounts in each pan, and the absolute weights in each pan.

You may format the table in a way congenial to the language you are coding in.

Scoring: Shortest code wins

Bonus: 50% of your score if the same code can present the results for the case where 3, 4, and 5 weights are used (for 13, 40, and 121 lbs.)

• The thing I (with my moderator cap taken off) don't like about this is that there is only one correct solution (1,3,9,27) as opposed the correct output depending on some input. The bonus is a nod in the right direction, but.. Can it be generalized? That would make a better task, IMO. Dec 6, 2012 at 22:41
• @dmckee I decided to reveal the weights and focus on the table. Dec 6, 2012 at 23:32
• u[x_] := (b = Array[n, x]; Table[FindInstance[b.Array[3^#/3 &, x] == s && b.b <= x, b, Integers], {s, 0, (3^x 3 - 1)/6}]); u Dec 10, 2012 at 1:03
• @belisarius Nice, and elegant. Why don't you submit it as an answer? [If you can spare the bytes, You might want to wrap the output in MatrixForm. for legibility.] Dec 10, 2012 at 1:38
• @dmckee Thanks for your input. Next time I'm developing a question, I'll first submit it to Meta for comments. Dec 10, 2012 at 2:52

## APL 198 * 50% = 99

z←W n
l←⍉(n⍴3)⊤w←0,⍳+/b←3*0,⍳n-1
r←(⍴l)⍴0
:while 0≠+/+/l>1
r←r+l>1
l←((l≤1)×l)+1⌽l>1
:end
a←' ',⌽⎕av[97+⍳n]
c←(⍴l)⍴⍳n
b←0,⌽b
z←l≠r
l←z×l
r←z×r
l←1+l×c
r←1+r×c
z←w,'{',a[l],'}','{',a[r],'}','{',b[l],'}','{',b[r],'}'


As we are effectively working in base three the arithmetic is fairly trivial and is complete by the end of the while loop where the arrays l and r are the contents of the left and right scale pans respectively in base three. This takes about 80 characters. The rest is formatting the output which I am sure can be improved.

To run simply type W followed by the number of weights you want to use. Below is a sample output for n=3:

 W 3
0 {   }{   }{ 0 0 0 }{ 0 0 0 }
1 {  a}{   }{ 0 0 1 }{ 0 0 0 }
2 { b }{  a}{ 0 3 0 }{ 0 0 1 }
3 { b }{   }{ 0 3 0 }{ 0 0 0 }
4 { ba}{   }{ 0 3 1 }{ 0 0 0 }
5 {c  }{ ba}{ 9 0 0 }{ 0 3 1 }
6 {c  }{ b }{ 9 0 0 }{ 0 3 0 }
7 {c a}{ b }{ 9 0 1 }{ 0 3 0 }
8 {c  }{  a}{ 9 0 0 }{ 0 0 1 }
9 {c  }{   }{ 9 0 0 }{ 0 0 0 }
10 {c a}{   }{ 9 0 1 }{ 0 0 0 }
11 {cb }{  a}{ 9 3 0 }{ 0 0 1 }
12 {cb }{   }{ 9 3 0 }{ 0 0 0 }
13 {cba}{   }{ 9 3 1 }{ 0 0 0 }

• I like the two-pan output. Dec 7, 2012 at 23:10
• Why are you doing things like l×l=0? That always evaluates to 0. if l=0, it's 0×1, which is 0; if l≠0, it's l×0, which is also 0. (Or you're using a weird APL). Dec 8, 2012 at 2:16
• Thanks @marinus - Old age?! Unfortunately there is still a problem with the table which can be seen on the 8 line. I will have another look. Dec 8, 2012 at 10:21
• I have corrected problem whereby the same weight could occur on both sides of the scales e.g. 8 was being shown as {9 3 0}{0 3 1} Dec 8, 2012 at 11:44
• @Graham You forgot to update the corresponding abc pans. For 8, it still shows {cb }{ ba}. Dec 10, 2012 at 5:18

## Python, 160 * 50% = 80

def f(n):
for i in range(3**n/2+1):g=lambda z:'+'.join(3**xfor x in range(n)if(i+3**x/2)/3**x%3==z)or'0';print i,'[%s, %s]'%(g(1),g(2)),map(eval,(g(1),g(2)))


Shows how each weight difference can be produced, given 'n' different weights.

## Python 124 107 bytes * 50% = 53.5

f=lambda i,e=1:i and[e]*(i%3>1)+f(-~i/3,e*3)or[]
for i in range(3**4/2+1):r=f(-i),f(i);print i,map(sum,r),r


For different numbers of stones, replace the 4 in range(3**4/2+1) with any positive integer.

Sample output:

0 [0, 0] ([], [])
1 [1, 0] (, [])
2 [3, 1] (, )
3 [3, 0] (, [])
4 [4, 0] ([1, 3], [])
5 [9, 4] (, [1, 3])
6 [9, 3] (, )
7 [10, 3] ([1, 9], )
8 [9, 1] (, )
9 [9, 0] (, [])
10 [10, 0] ([1, 9], [])
11 [12, 1] ([3, 9], )
12 [12, 0] ([3, 9], [])
13 [13, 0] ([1, 3, 9], [])
14 [27, 13] (, [1, 3, 9])
15 [27, 12] (, [3, 9])
16 [28, 12] ([1, 27], [3, 9])
17 [27, 10] (, [1, 9])
18 [27, 9] (, )
19 [28, 9] ([1, 27], )
20 [30, 10] ([3, 27], [1, 9])
21 [30, 9] ([3, 27], )
22 [31, 9] ([1, 3, 27], )
23 [27, 4] (, [1, 3])
24 [27, 3] (, )
25 [28, 3] ([1, 27], )
26 [27, 1] (, )
27 [27, 0] (, [])
28 [28, 0] ([1, 27], [])
29 [30, 1] ([3, 27], )
30 [30, 0] ([3, 27], [])
31 [31, 0] ([1, 3, 27], [])
32 [36, 4] ([9, 27], [1, 3])
33 [36, 3] ([9, 27], )
34 [37, 3] ([1, 9, 27], )
35 [36, 1] ([9, 27], )
36 [36, 0] ([9, 27], [])
37 [37, 0] ([1, 9, 27], [])
38 [39, 1] ([3, 9, 27], )
39 [39, 0] ([3, 9, 27], [])
40 [40, 0] ([1, 3, 9, 27], [])


The basic operating principle, is that the problem is analog to converting a number into ternary. In Python, this is a one liner:

f=lambda i:i and i%3+f(i/3)*10


Of course, we're working in a slightly different base. Instead of the values 0, 1, 2 we use -1, 0, 1. This means when i%3 == 2, this should really be -1 (calculated by (i+1)%3-1 or -~i%3-1), and the value of the i sent to the next iteration needs to be adjusted accordingly.

More specifically, if d=(i+1)%3-1, then the value of i sent to the next iteration should be (i-d)/3. However, this calculaion can be simplified greatly using integer division, to just (i+1)//3. Rationale: if d == 0, then i was already a multiple of 3, and adding one won't change the integer quotient. If d == 1, then we should be subtracting 1 to make i a multiple of 3, but if we add 1 instead, it will now be 2 (mod 3), which won't change the integer quotient either. If however d == -1, then we do in fact need to add 1 to reach the next multiple of 3. Therefore, by using integer division, all three cases can be simplified to adding 1.

One thing that makes this problem interesting is that the negative and positive values need to be separated into different baskets. I decided the best way to accomplish this is to only collect the positive values, and then call the function again with -i, which will obviously have its stones reversed. This also allows me to save the -~i%3 calculation entirely, since I know what its value will be.

• Nice explanation. Dec 9, 2012 at 17:22

## Perl, 201 (or 166) chars + 50% bonus = 100.5 (or 83)

eek, brute forcing this turned out to be more complex than i anticipated. im interested to see others' certainly more analytical approaches

change the problem size by modifying the value of $j defined at the top to 3, 4, or 5. this will demonstrate all ways to generate the differences, not any pairs in particular. some additional characters are used to print the differences in order. otherwise, you can remove the outer for$n(0..$s){} loop and the $$x[j]-$$_[$j]==$n test to save 14+21 chars for a total of 166 chars. $k=($j=4)-1;@a=map{$s=0;$s+=$_ for@$_;[@$_,$s]}map{$c=$_;[map{$c&1<<$_&&3**$_}0..$k]}0..2**$j-1;for$n(0..$s){for$x(@a){$$x[j]-$$_[$j]==$n&&print"$n {@$x[0..$k],@$_[0..$k]} {$$x[j],$$_[$j]}",$/for@a}}


or slightly more formatted (no more readable):

# set $j to the problem domain size$k = ($j = 4) - 1; # gather up all possible combinations and their sums @a = map{$s=0; $s+=$_ for @$_; [@$_,$s] } map {$c=$_; [map {$c & 1<<$_ && 3**$_ } 0..$k] } 0 .. 2**$j-1;

# walk through the pairs of combinations and find the differences
for $n (0..$s)
{
for $x (@a) { $$x[j] -$$_[$j] == $n && print "$n {@$x[0..$k],@$_[0..$k]} {$$x[j],$$_[$j]}",$/ for @a
}
}

• Would you show a few lines of the output? Dec 7, 2012 at 14:13
• @DavidCarraher it produces this output: codepad.org/NCf1KIMN Dec 9, 2012 at 13:51
• Perhaps I didn't make it clear: there are only 4 stones, so you cannot use the same stone on both sides of the two-pan balance scale. This constraint leaves only one way to solve each weight difference. Dec 9, 2012 at 14:13