It’s been a while since I offered a coding challenge, so let’s remedy this.

This one comes from this week’s Car Talk’s puzzler. Here is the short version of it:

A farmer has a forty pound stone that he uses to weigh food for his animals on a scale. One day, he loans the stone to his neighbor. A few days later, the neighbor returns the stone and apologizes to the farmer because his stone is now broken in four pieces. The farmer responds “Please don’t apologize, you have actually made my life easier because with these four pieces, I can now measure any weight between one and forty pounds”.

The question is: how much do these four individual pieces weigh?

I’m adding a few clarifications, which are not necessarily what the Car Talk guys meant (I don’t have the solution and I haven’t looked at any discussion on the subject):

- The four weights are integers.
- The weights we can measure between one and forty pounds are in one pound increment.
- They are measured in one session (otherwise, you could measure forty pounds with a one pound stone by performing forty measurements).
- If there is no solution (the farmer might be bad at math), show the four weights that allow to measure the most weights between one and forty pounds.

The challenge? Write a brute force solution to this puzzler in any language that you want. I don’t care if your solution is slow, fast, ugly or elegant as long as it works, and I suspect that certain languages will be very good for this puzzler

Bonus questions:

- Your solution should explain how exactly you use the stone pieces to measure each weight.
- Is there a formal way to solve this problem without using brute force?

#1 by

Lawrence Kestelooton October 30, 2011 - 12:02 pmHere’s my write-up of this puzzle from a few years ago:

http://www.teamten.com/lawrence/puzzles/balance.html

It doesn’t use programming to solve it, but it does show that you can measure up to 81 pounds, not 40, if you’re willing to measure in two sessions instead of one.

#2 by

Dhananjay Neneon October 30, 2011 - 3:02 pmhttps://gist.github.com/1326624

#3 by

David Nolenon October 30, 2011 - 3:19 pmSolved efficiently and with very little code using cKanren, the constraint logic programming system designed by Dan Friedman, William Byrd.

http://dosync.posterous.com/a-taste-of-ckanren

#4 by

Leonon October 30, 2011 - 5:06 pmAs brute force as it gets, Java, no libraries, can be ported pretty much directly into straight C: https://gist.github.com/1326736

#5 by

Chris Dolanon October 30, 2011 - 5:19 pmHere’s a Perl solution. The answer is fairly clear in retrospect… My brief analysis is in the gist comments. I added a human-readable output of the left/right scale distribution for each target weight to help visualize the problem.

https://gist.github.com/1326753

#6 by

Lucianon October 30, 2011 - 5:25 pmLet’s try to see what the maximum number of weights we would be able to measure with 4 stones.

In the maximum case, let’s assume any combination will sum up to a different weight.

We have:

– C(1,4) = 4 – combinations when we take each stone alone

– C(2,4) = 6 – combinations when we take two stones

– C(3,4) = 4 – combinations when we take three stones

– C(4,4) = 1 – when we use all stones at the same time

=> 15 different weights max => impossible to solve the problem even with our very generous assumptions.

In general: Sum(C(k,n)) for k in 1..n = 2^n-1

But here we made an assumption: we put the scales on the same part of the scale. But we can do better than that!

If we can put them on either side of the scale we can model the problem like this: we have four weights x0, x1, x2, x3 each in [1,40] and we need to find out how many combinations we can make with them on either side of the scale: each can be off the scale, on the left and on the right => 3^4=81 combinations. OK, no answer but we know we must look further.

We need to find those x0..3 such that for each w in [1,40] we have four ai in {-1,0,1} such that

w=sum(xi*ai)

We can simplify the problem further all weights must have as a sum 40 to measure a weight of 40, so x3 = 40 – x0 – x1 – x2, and to remove repetitions we can asset x3>=x2=>x1=>x0.

Lets build the solution from N=2, N=3 and N=4.

N=2: x0=1, x1=3 gives us our widest range: 1,2,3,4

N=3:

– we need to get a 5 to continue the range, but we’ll get it by setting x0,x1 on one side of the scale and x2=5+x0+x1 on the other side => x2=9

– we can get 6,7,8 by removing something from the x0,x1 part of the scale

– we have 9

– we can get everything from 9 to 9 + 4=13 by combining with x0, x1

– => 1..13

N=4:

– we need 14 and we get it by setting x0,x1,x2 on one side and x3=14+x0+x1+x2 on the other side => x3=27

– we can get everything from [15..27] = [14+1..14+13] by removing elements from the x0,x1,x2 side as seen in N=3

– we can get everything from in [27..27+13=40] as by combining x3 with x0,x1,x2 as seen in N=3

Solution 1,3,9,27.

Generalized:

N=n: we can measure every weight from 1 to sum(3^k) for k in [0..n]=3^(n+1)/(3-1) and the stones weigh 3^k.

#7 by

AnotherCedon October 30, 2011 - 5:39 pmQuick’n’dirty Java solution (Some Emacs magic mainly wrote that code ðŸ˜‰

It’s not ‘short’. It’s brute force (but it’s basically instantaneous).

I’m not sure I got the problem right. It writes 1,3,9,27 as the solution.

@Test

public void doIt() {

final int n = 40;

int[] max = new int[5];

for (int i = 1; i < n; i++) {

for (int j = i + 1; j < n; j++) {

for (int k = j + 1; k < n; k++) {

for (int l = k + 1; l max[0] ) {

max = new int[] {v,i,j,k,l};

}

}

}

}

}

System.out.println( ” max: ” + max[0] + ” (” + max[1] + “, ” + max[2] + “, ” + max[3] + “, ”

+ max[4] + “)” );

}

public int cnt( final int[] a ) {

int cnt = 0;

for (int p = 1; p <= 40; p++) {

boolean b = false;

for (int i = 0; i < 4; i++) {

b = b || p == a[i];

}

for (int i = 0; i < 4; i++) {

for (int j = i + 1; j < 4; j++) {

b = b || p == a[i] + a[j];

b = b || p == a[i] – a[j];

b = b || p == a[j] – a[i];

}

}

for ( int i = 0; i < 4; i++ ) {

for ( int j = i + 1; j < 4; j++ ) {

for ( int k = j + 1; k < 4; k++ ) {

b = b || p == +a[i]+a[j]+a[k];

b = b || p == +a[i]+a[j]-a[k];

b = b || p == +a[i]-a[j]+a[k];

b = b || p == -a[i]+a[j]+a[k];

b = b || p == -a[i]-a[j]+a[k];

b = b || p == -a[i]+a[j]-a[k];

b = b || p == +a[i]-a[j]-a[k];

}

}

}

b = b || p == +a[0]+a[1]+a[2]+a[3];

b = b || p == -a[0]+a[1]+a[2]+a[3];

b = b || p == +a[0]-a[1]+a[2]+a[3];

b = b || p == +a[0]+a[1]-a[2]+a[3];

b = b || p == +a[0]+a[1]-a[2]-a[3];

b = b || p == -a[0]-a[1]+a[2]+a[3];

b = b || p == -a[0]+a[1]-a[2]+a[3];

b = b || p == -a[0]+a[1]+a[2]-a[3];

b = b || p == +a[0]-a[1]-a[2]+a[3];

b = b || p == +a[0]-a[1]+a[2]-a[3];

b = b || p == +a[0]+a[1]-a[2]-a[3];

b = b || p == +a[0]-a[1]-a[2]-a[3];

b = b || p == -a[0]+a[1]-a[2]-a[3];

b = b || p == -a[0]-a[1]+a[2]-a[3];

b = b || p == -a[0]-a[1]-a[2]+a[3];

cnt += b ? 1 : 0;

}

#8 by

AnotherCedon October 30, 2011 - 5:40 pmSame Java code but nicely formatted by pastebin:

http://pastebin.com/qw76rGHX

(saw this late at night, too late to answer the other questions ðŸ˜‰

#9 by

Jim Whiteon October 30, 2011 - 6:11 pmHaven’t checked out the answer but I’m guessing it’s right:

weights = [1..10, 1..20, 1..20, 1..40].combinations().grep { it.sum() == 40 }.collect { it.sort() }.unique()

println (weights.grep { it.inject([0], { a, v -> a + a*.plus(v) + a*.plus(-v) }).containsAll ( 1..40 )})

Gives:

[[1, 3, 9, 27]]

See it in action with the Groovy Web Console: http://groovyconsole.appspot.com/script/582001

#10 by

Vijayon October 30, 2011 - 7:17 pmSolution in Groovy at http://vijay-nathani.blogspot.com/2011/10/solution-to-coding-challenge.html

The first solution found is 1, 3, 9, 27.

#11 by

Igoron October 30, 2011 - 11:54 pmJava solution

Output: 1 3 9 27

public class StonePuzzle {

public static final int N = 40, signum[] = {-1, 0, 1};

public static void main(String[] args) {

long success = (long) Math.pow(2, N) – 1;

for (int p1 = 1; p1 < N; p1++)

for (int p2 = p1; p2 < N; p2++)

for (int p3 = p2; p3 < N; p3++) {

int p4 = N – p1 – p2 – p3;

if (p4 0 && result <= N) mask |= (long) 1 << (result – 1);

}

return mask;

}

}

#12 by

Igoron October 31, 2011 - 12:01 amWeird, this is not what I wanted to submit.

Here is a nicely formatted version.

http://pastebin.com/WZ97t029

#13 by

Pepijn de Voson October 31, 2011 - 2:40 amCan we use stones on both sides of the weight?

Vijay seems to assume this, while David Nolen doesn’t seem to do that.

#14 by

SKroahon October 31, 2011 - 3:56 amThanks Lucien for reminding everyone that these are math problems not brute force coding problems.

#15 by

Chrison October 31, 2011 - 6:56 amBut can you run it in a browser:

http://jsfiddle.net/RfpPU/

#16 by

zerologyon October 31, 2011 - 7:10 am(Beginners Haskell)

import Data.List

allStones = [[a,b,c,d]| a <- [1..39], b <- [a..39], c <- [b..39], d [w-x, w, w+x]) (combineWeights xs)

result = filter (\x -> ((sort $ filter (>0) $ nub $ map abs (combineWeights x)) == [1..40])) allStones

#17 by

zerologyon October 31, 2011 - 7:11 am(Beginners Haskell. The first post seems to miss something)

import Data.List

allStones = [[a,b,c,d]| a <- [1..39], b <- [a..39], c <- [b..39], d [w-x, w, w+x]) (combineWeights xs)

result = filter (\x -> ((sort $ filter (>0) $ nub $ map abs (combineWeights x)) == [1..40])) allStones

#18 by

zerologyon October 31, 2011 - 7:14 amWell then

https://gist.github.com/1327860

Beginners Haskell.

#19 by

Fun problemon October 31, 2011 - 7:45 amThanks for the fun problem! I did it on paper and found the first two numbers (1,3) by looking at what I would need to weigh 39 (an edge case) -> this implies one of the weights has to be 1 pound. Then I looked at 37 and figured I needed a 3, then I just leapt to a “base 3” number system since a given weight is either on the left, on the right or on neither (3 possibilities).

#20 by

Cedricon October 31, 2011 - 7:58 amHi “Fun Problem”,

Actually, your assumption is wrong: 1 doesn’t have to be one of the weights since you can measure one pound with, for example, two weights of two and three pounds respectively.

As it turns out, a 1 pound weight ends up being part of the solution, but it’s merely a coincidence (e.g. you got lucky :-)).

Edit: I’m wrong, Mike correctly pointed out that you can’t measure 39 pounds without a 1 pound stone.

#21 by

Martinon October 31, 2011 - 8:41 amhttps://gist.github.com/1328114

A faster version of Dhananjay Nene’s solution (post #2)

#22 by

David Gageoton October 31, 2011 - 9:49 amA (slow) solution using Ioke. https://gist.github.com/1328433

#23 by

Alex Shneydermanon October 31, 2011 - 2:35 pmFun. Here is Erlang solution in about 4 lines of useful code:

#!/usr/bin/env escript

main(_Args) ->

% Generate all combinations of weights that add up to 40

StoneWeights = [ {St1,St2,St3,St4} || St1 <- lists:seq(1,37),

St2 <- lists:seq(1,37),

St3 <- lists:seq(1,37),

St4 <- lists:seq(1,37),

(St1 + St2 + St3 + St4) == 40 ],

% Find all the weight combinations that could be our solutions

Solutions = [ Weights || Weights

lists:all( fun(X) ->

length( [{Sgn1,Sgn2,Sgn3,Sgn4} || Sgn1 <- [1, 0, -1],

Sgn2 <- [1, 0, -1],

Sgn3 <- [1, 0, -1],

Sgn4 <- [1, 0, -1],

(X + Sgn1 * St1 + Sgn2 * St2 + Sgn3 * St3 + Sgn4 * St4) == 0 ] ) /= 0

end, lists:seq(1,40) ).

#24 by

Alex Shneydermanon October 31, 2011 - 2:49 pmAhh, formatting in these comments is messing things up. Here is a well formatted Erlang version http://bit.ly/scLAPQ

#25 by

Stephane Geneixon October 31, 2011 - 3:38 pmI heard it some time ago as a logical problem more than as a coding problem (coding is pretty trivial here once you get that you could put stones on either edge of the scale).

As the non-bruteforce solution, I’ll try to explain mine here :

let’s call the stones x, y, z and t (x being the lightest, t the heaviest)

let’s say that the position of a stone on the balance can be identified by a number : -1 (on the left side, with the weight to mesure), (0 : not on the scale) and +1 (on the right side).

if you can mesure all values from 1 to 40, you can mesure also from -1 to -40 (whatever value you are currently mesuring, you transform all the -1 in +1).

also, you can mesure 0 (by not putting anything on the scale).

in other words, you have to be able to mesure 81 values with 4 stones.

now, let’s look at how many vlaues we can mesure with 4 stones :

every single one of them can be in 3 states independantly from each other (-1, 0, +1). Which means we have a total of 3^4 different states. Which is 81. So 81 is also the max number of weights you can mesure with 4 stones…

so, now, let’s revert the problem : what’s the max number of consecutive weights we can mesure with 3 stones ? with 2 stones ? with 1 ? Easy answer : 27 9 and 3.

with one stone you can mesure 3 weights (from -1 to +1) with one stone of 1lb.

with 2 stones, you can go from -4 to +4 with x = 1 and y = 3 (bc 1+3 = 4).

with 3 stones, you can go from -13 to +13 with x=1, y=3 and z=9 (bc 1+3+9 = 23).

and with 4 stones you have x=1, y=3, z=9 and t=27.

i’m sure there’s a better way to explain it but you get how I arrived to the correct answer without coding anything ðŸ™‚

#26 by

Aaron Brookson October 31, 2011 - 4:03 pmThis problem is related to Optimal Golomb Rulers ( http://en.m.wikipedia.org/wiki/Golomb_ruler ), though I believe less constrained. I’d post a solution but the surprise snowstorm in the Northeast has left me without power for the last several days and, while I still have my phone, I wouldn’t relish trying to write a solution using the Android Clojure REPL. ðŸ™‚

#27 by

David Nolenon October 31, 2011 - 6:44 pmHere’s a correct solution using cKanren that solves the puzzle in ~12ms under Racket on my machine. http://dosync.posterous.com/another-taste-of-ckanren

#28 by

Mockyon November 1, 2011 - 3:25 amHere’s my solution that uses clojure.contrib.combinatorics

(defn trinary

“Returns a sequence containing x, -x and zero”

[x] (list x (- x) 0))

(defn cartesian-sum

“Returns a sequence of the sum of each cartesian product”

[col] (map #(apply + %) (apply cartesian-product col)))

(defn weights

“Returns all unique positive weights measurable by items in col”

[col] (filter pos? (into #{} (cartesian-sum (map trinary col)))))

(defn by-weight-counts

“Comparable for sorting based on the count of measureable weights”

[col1 col2] ( (last (sort by-weight-counts combos))

(1 3 9 27)

#29 by

Filip Deleersnijderon November 1, 2011 - 4:11 am1, 3, 9, 27 is only one of the solutions.

What the above solutions forget is exploiting the fact that when the stones allow you to weight an object with weight X and they allow you to weight an object with weight X+2, you can implicitly weigh something with weight X+1 by stating that it is heavier then X but lighter then X+2 ( And it must be integer ).

This leads to the following solutions :

16, 16, 6, 2

17, 15, 6, 2

17, 16, 5, 2

18, 14, 6, 2

18, 15, 5, 2

19, 13, 6, 2

19, 14, 5, 2

20, 12, 6, 2

20, 13, 5, 2

20, 14, 4, 2

21, 11, 6, 2

21, 12, 5, 2

21, 13, 4, 2

22, 10, 6, 2

22, 11, 5, 2

22, 12, 4, 2

23, 9, 6, 2

23, 10, 5, 2

23, 11, 4, 2

23, 12, 4, 1

24, 8, 6, 2

24, 9, 5, 2

24, 10, 4, 2

24, 11, 4, 1

25, 7, 6, 2

25, 8, 5, 2

25, 9, 4, 2

25, 10, 4, 1

26, 6, 6, 2

26, 7, 5, 2

26, 8, 4, 2

26, 9, 4, 1

27, 6, 5, 2

27, 7, 4, 2

27, 8, 4, 1

#30 by

David Gageoton November 1, 2011 - 7:13 amFilip, great idea. However using this strategy, I find more combinations than you do. 44 instead of 36

#31 by

Cedricon November 1, 2011 - 7:18 amFilip: true but you need more than one measurement to measure such a weight, so it doesn’t qualify for this problem.

#32 by

Laurent Petit (@petitlaurent)on November 1, 2011 - 12:55 pmHere is a clojure solver, using clojure.contrib.combinatorics’s subset & cartesian product helper functions.

This solution is “general” : works for searching solutions for N pieces of stone and a maximum weight of M pounds.

https://gist.github.com/1332020

It also prints out how to check the 1..M weights with a balance.

Not bad for 38 lines, but I’m pretty sure it could be shortened without compromising lisibility (I’m pretty sure it could help lisibility by avoiding reinventing the wheel or using an improved algorithm).

Uses brute force algorithm.

#33 by

Horiaon November 1, 2011 - 3:44 pmCedric, how do you define a measurement?

For instance, to weight X=2 pounds with the weights (27,9,3,1) you may have to do:

1. start with 1, find that X is heavier.

2. add 3, X is lighter.

3. remove 1, X is still lighter. We could determine X=2 and end up here.

4. add 1 on the X side, X=2;

With Filip’s combination (27,8,4,1) you may have to do:

1. start with 1, X is heavier

2. Add 4, X is lighter

3. remove 1, X is still lighter

4. add 1 on the X side, X is still lighter, thus X=2;

In both cases stones have to be added and removed from plates. The main difference is that in Filip’s case some combinations cannot end with balanced plates.

Two additional questions:

1. What (if any) is the weighting strategy that requires the smallest number of stone movements when weights between 1 and 40 (or 1 to (3^N – 1)/2 for the general case ) are presented in random order?

2. Is there any change if N is relatively large but the number of unknown weights is small?

#34 by

Filip Deleersnijderon November 2, 2011 - 2:06 am@David, there was a small mistake in my code, there are indeed 44 solutions.

@Cedric. I think that constraint in the problem definition should be interpreted as : “It is not allowed to divide the food that must be weighted and weigh the different parts”

#35 by

Raghavon November 2, 2011 - 2:56 amMy brute-force clojure solution: http://ragstorooks.wordpress.com/2011/11/02/coding-challenge/

#36 by

pyritschardon November 3, 2011 - 11:40 pmHere’s my solution in clojure: https://gist.github.com/1338927

#37 by

Ben Engon November 4, 2011 - 6:18 pmint total = 40

def result = []

int next = 1

int sum = next

while( sum <= 40 ) {

result << next

next = 2 * sum + 1

sum += next

}

println result

#38 by

Cedricon November 4, 2011 - 7:01 pmWell… yes, that’s a big cheat. What if the total is 41? Might as well “return new int[] { the solution }” ðŸ™‚

#39 by

Ben Engon November 7, 2011 - 2:37 pm@Cedric I am guessing the solution works in general to measure the most weights, based on how the combinations give coverage of the possible weights without overlap. I’m assuming a fix to the typo in the code to say “while( sum <= total )".

#40 by

AnotherCedon November 16, 2011 - 4:42 amI don’t understand why you say that Filip’s *solutions* don’t qualify. Where was it written in the original problem (or in your version) that it’s not allowed to weight vs ‘x’ and vs ‘x + 2’ and infer the weight is ‘x+1’. How would all the other solutions (the ones finding only one solution) weight ‘x+1’: by magically putting the correct number of stones at left and the correct number of stones at right? To me Filip’s solving not only solving the problem: he’s also solving a much, much more interesting problem.

#41 by

Dhawal Jaiswalon November 26, 2011 - 12:21 pmCan’t we just wait three stone pieces and subtract it from total to get one stone weight and so on.

#42 by

taoon February 21, 2012 - 9:08 pmbut who can write it in as a clear and concise programming solution!

#43 by

Tarek Abdelmaguidon February 22, 2012 - 8:52 pmHere is a solution in scala:

https://gist.github.com/1890672

Pasting here for easy reference, though the format may not be as nice:

import scala.math._

def stone_weights(w: Int) : List[Int] = w match {

case 1 => List(1)

case _ =>

val one_third : Int = ceil((w-1).toDouble/3).toInt

w – one_third :: stone_weights (one_third)

}

println(stone_weights(40));

This function should work for any given positive parameter.

The solution relies on the function stone_weights to return a list of the minimum number of stone weights, that can make up to all weights between 1 and w.

The function itself calculates the list using the following logic:

1. if w = 1, the answer is the list [1]

2. otherwise, the answer is the number at 2 thirds of w, appended to a list of the stone_weights of (one third of w)

Think of the solution as dividing the target weight into 3 portions. If we had a set of stone pieces that represent all the weights up to a third of that weight, then we can combine this set with a stone weighing two thirds of the target weight, to be able to represent all the wights up to the desired weight.

The solution requires a bit of rounding and +/- 1, to provide the exact coverage.

Feedback welcome.

#44 by

Tarikon May 19, 2012 - 3:01 amThis problem is related to a base 3 numbering system with -1, 0, 1 as possible digit at each position. -1 = put weight on left side, 1 = put weight on the right side, 0 = do not use the weight. Following is an exhaustive enumeration which when multiplied respectively by 27, 9, 3, 1 produces the result on the right most column.

The problem is symmetric in the sense that you could do the same weighing by flipping the weights at the two sides.

Solutions such as (16, 16, 6, 2) and (17, 15, 6, 2) and 42 others provided by Filip and David seem incorrect.

0 -1 -1 -1 -1 -40

1 -1 -1 -1 0 -39

2 -1 -1 -1 1 -38

3 -1 -1 0 -1 -37

4 -1 -1 0 0 -36

5 -1 -1 0 1 -35

6 -1 -1 1 -1 -34

7 -1 -1 1 0 -33

8 -1 -1 1 1 -32

9 -1 0 -1 -1 -31

10 -1 0 -1 0 -30

11 -1 0 -1 1 -29

12 -1 0 0 -1 -28

13 -1 0 0 0 -27

14 -1 0 0 1 -26

15 -1 0 1 -1 -25

16 -1 0 1 0 -24

17 -1 0 1 1 -23

18 -1 1 -1 -1 -22

19 -1 1 -1 0 -21

20 -1 1 -1 1 -20

21 -1 1 0 -1 -19

22 -1 1 0 0 -18

23 -1 1 0 1 -17

24 -1 1 1 -1 -16

25 -1 1 1 0 -15

26 -1 1 1 1 -14

27 0 -1 -1 -1 -13

28 0 -1 -1 0 -12

29 0 -1 -1 1 -11

30 0 -1 0 -1 -10

31 0 -1 0 0 -9

32 0 -1 0 1 -8

33 0 -1 1 -1 -7

34 0 -1 1 0 -6

35 0 -1 1 1 -5

36 0 0 -1 -1 -4

37 0 0 -1 0 -3

38 0 0 -1 1 -2

39 0 0 0 -1 -1

40 0 0 0 0 0

41 0 0 0 1 1

42 0 0 1 -1 2

43 0 0 1 0 3

44 0 0 1 1 4

45 0 1 -1 -1 5

46 0 1 -1 0 6

47 0 1 -1 1 7

48 0 1 0 -1 8

49 0 1 0 0 9

50 0 1 0 1 10

51 0 1 1 -1 11

52 0 1 1 0 12

53 0 1 1 1 13

54 1 -1 -1 -1 14

55 1 -1 -1 0 15

56 1 -1 -1 1 16

57 1 -1 0 -1 17

58 1 -1 0 0 18

59 1 -1 0 1 19

60 1 -1 1 -1 20

61 1 -1 1 0 21

62 1 -1 1 1 22

63 1 0 -1 -1 23

64 1 0 -1 0 24

65 1 0 -1 1 25

66 1 0 0 -1 26

67 1 0 0 0 27

68 1 0 0 1 28

69 1 0 1 -1 29

70 1 0 1 0 30

71 1 0 1 1 31

72 1 1 -1 -1 32

73 1 1 -1 0 33

74 1 1 -1 1 34

75 1 1 0 -1 35

76 1 1 0 0 36

77 1 1 0 1 37

78 1 1 1 -1 38

79 1 1 1 0 39

80 1 1 1 1 40