4
\$\begingroup\$

This question already has an answer here:

Mr Seckington is a mobile grocer. He drives his van door-to-door selling his produce all around the nearby villages. Mr Seckington needs a method to weigh the produce he is selling so he knows how much to charge his customers. Because space is at such a premium on his van, he uses an interesting sequence of weights on his scale that minimizes the amount weights he needs to measure any integer number of grams.

enter image description here

The weights (in grams) are all powers of 3, i.e 1, 3, 9, 27, 81... He puts what he is weighing on the left side of the scale and he can put weights on either side of the scale to measure a desired weight with integer granularity.

For example if he wants to weigh out 2 grams of peppercorns, he will put a 1g weight on the left side, a 3g weight on the right side, and then he can load the peppercorns onto the left side until the scale balances.

Similarly if he wants to weigh out 30g of chocolate chips, he'll put 3g + 27g weights on the right side and load chocolate chips onto the left side until the scale balances.

Given a positive integer weight as input, output two lists - one with the weights that must go on the left side of the scale and the other with the weights that must go on the right side.

It should be clear from the output which is the left-side list and which is the right-side list. E.g. always ordering left, then right is fine.

The ordering within the lists doesn't matter.

You should be able to support inputs at least up to 88,573 (31+32+...+310).

Input -> Output
    1 -> {}, {1}
    2 -> {1}, {3}
    3 -> {}, {3}
    4 -> {}, {1 ,3}
    5 -> {1, 3}, {9}
    6 -> {3}, {9}
    7 -> {3}, {1, 9}
    8 -> {1}, {9}
    9 -> {}, {9}
   10 -> {}, {1, 9}
   13 -> {}, {1, 3, 9}
   14 -> {1, 3, 9}, {27}
   20 -> {1, 9}, {3, 27}
  100 -> {9}, {1, 27, 81}

Harold Seckington really did have a mobile grocery in the village that I grew up in. However, I made up the bit about him using a ternary system of weights.

\$\endgroup\$

marked as duplicate by Peter Taylor code-golf Feb 26 '17 at 23:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ can we have extra zeros in the middle of the lists? \$\endgroup\$ – Maltysen Feb 26 '17 at 22:39
  • \$\begingroup\$ @Maltysen no, sorry \$\endgroup\$ – Digital Trauma Feb 26 '17 at 22:51
  • \$\begingroup\$ Closely related. \$\endgroup\$ – Greg Martin Feb 26 '17 at 22:59
  • \$\begingroup\$ Can it be a single list with positive and negative values? \$\endgroup\$ – Luis Mendo Feb 26 '17 at 22:59
  • \$\begingroup\$ @LuisMendo no, two separate lists please. \$\endgroup\$ – Digital Trauma Feb 26 '17 at 23:05
3
\$\begingroup\$

MATL, 39 bytes

`x3:H-@Z^3@:q^*!tXsG=~}1MZ)Xzt0>&)_Xh&D

The output lists are in reversed order. Each list is actually a column array of numbers (square brackets, semicolon as separator). In MATL, as in MATLAB and Octave, an array with a single number is the same as a number, so in that case the corresponding list doesn't have enclosing brackets.

Try it online! Or verifiy all test cases.

How it works

This keeps testing sets of weights of increasing size: the set {1}, then {1, 3}, then {1, 3, 9}, ... This is done with a do...while loop.

For any such set, containing k different weights, all possible distributions of those weights are tested.

A distribution of weights is defined by a vector of k numbers, where each number may be -1, 0, 1, meaning that the corresponding weight is on the left side, unused, or on the right side. For each distribution, the sum is compared with the target weight. This is done in a vectorized manner, using 2D arrays.

If for a given set of weights there is a distribution of those weights that matches the target, the solution has been found.

\$\endgroup\$
1
\$\begingroup\$

Python2 - 109 102 bytes

Thought it might be fun to do it without a base conversion builtin.

a=[[],[],[],[]];r=input()+3**12;e=0;i=1
while r:c=r%3+e;a[c]+=[i];e=c>1;r/=3;i*=3
print a[2],a[1][:-1]
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 11376 75 bytes

Returns an array of two arrays [ [left_side], [right_side] ].

f=(n,x=!(r=[[],[]]),i=1)=>n+x?f(n/3|0,(x+=n%3)>1,i*3,x%3&&r[2-x].push(i)):r

Test cases

f=(n,x=!(r=[[],[]]),i=1)=>n+x?f(n/3|0,(x+=n%3)>1,i*3,x%3&&r[2-x].push(i)):r

console.log(JSON.stringify(f(  1))); // -> {}, {1}
console.log(JSON.stringify(f(  2))); // -> {1}, {3}
console.log(JSON.stringify(f(  3))); // -> {}, {3}
console.log(JSON.stringify(f(  4))); // -> {}, {1 ,3}
console.log(JSON.stringify(f(  5))); // -> {1, 3}, {9}
console.log(JSON.stringify(f(  6))); // -> {3}, {9}
console.log(JSON.stringify(f(  7))); // -> {3}, {1, 9}
console.log(JSON.stringify(f(  8))); // -> {1}, {9}
console.log(JSON.stringify(f(  9))); // -> {}, {9}
console.log(JSON.stringify(f( 10))); // -> {}, {1, 9}
console.log(JSON.stringify(f( 13))); // -> {}, {1, 3, 9}
console.log(JSON.stringify(f( 14))); // -> {1, 3, 9}, {27}
console.log(JSON.stringify(f( 20))); // -> {1, 9}, {3, 27}
console.log(JSON.stringify(f(100))); // -> {9}, {1, 27, 81}

\$\endgroup\$
0
\$\begingroup\$

Batch, 178 bytes

@echo off
set l=
set r=
set/aw=%1,p=1,g=w%%3
goto %g%
:2
set l=%l% %p%
goto 0
:1
set r=%r% %p%
:0
set/ap*=3,w+=1,w/=3,g=w%%3
if %w% gtr 0 goto %g%
echo(%l%
echo(%r%
\$\endgroup\$

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