Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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;

table


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

share|improve this question
1  
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. –  dmckee Dec 6 '12 at 22:41
    
@dmckee I decided to reveal the weights and focus on the table. –  David Carraher Dec 6 '12 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[4] –  belisarius Dec 10 '12 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.] –  David Carraher Dec 10 '12 at 1:38
    
@dmckee Thanks for your input. Next time I'm developing a question, I'll first submit it to Meta for comments. –  David Carraher Dec 10 '12 at 2:52
show 1 more comment

4 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
Nice explanation. –  David Carraher Dec 9 '12 at 17:22
add comment

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 }
share|improve this answer
    
I like the two-pan output. –  David Carraher Dec 7 '12 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). –  marinus Dec 8 '12 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. –  Graham Dec 8 '12 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} –  Graham Dec 8 '12 at 11:44
    
@Graham You forgot to update the corresponding abc pans. For 8, it still shows {cb }{ ba}. –  primo Dec 10 '12 at 5:18
show 1 more comment

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.

share|improve this answer
add comment

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
  }
}
share|improve this answer
    
Would you show a few lines of the output? –  David Carraher Dec 7 '12 at 14:13
    
@DavidCarraher it produces this output: codepad.org/NCf1KIMN –  primo Dec 9 '12 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. –  David Carraher Dec 9 '12 at 14:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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