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

Question

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

Answer 1

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

Answer 2

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 }

Answer 3

Python, 160 * 50% = 80

def f(n):
 for i in range(3**n/2+1):g=lambda z:'+'.join(`3**x`for 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.

Answer 4

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