26
\$\begingroup\$

You have a square board with a bunch of items laid out on it in one of a \$3 \times 3\$ grid of cells and you want to lift it up using balloons, but you can only attach balloons to the corners of the board. Your task is to determine the minimum number of balloons in each corner to make sure the board won't tip over in flight, but can still lift all its contents.

"Physics" Model

  • Each balloon can lift 0.25kg (these are very strong balloons)
  • The board itself weighs 1kg, so you would need 1 balloon in each corner to lift an empty board
  • Items in each corner cell only exert force on their respective corners (i.e. 4 balloons are needed in the corresponding corner per kg)
  • Items on each edge cell split their force evenly between their neighboring corners (i.e. 2 balloons on each of the two corresponding corners per kg)
  • Items in the center cell split their force evenly across all corners (i.e. 1 balloon is needed in each corner per kg)

Example Test Cases

1

Input:
0 0 0
0 0 0
0 0 0

Output:
1 1
1 1

2

Input:
1 2 1
2 4 2
1 2 1

Output:
17 17
17 17

3

Input:
5 0 0
0 0 2
0 1 0

Output:
21 5
 3 7

4

Input:
12  9 35
 1 32  2
 4  6 18

Output:
101 195
 63 121

5

Input:
9999 9999 9999
9999 9999 9999
9999 9999 9999

Output:
89992 89992
89992 89992

6

Input:
9999    2 9001
   0 9999 9999
9999  999 9999

Output:
50000 66006
51994 71992

Rules and Assumptions

  • You may assume each cell is filled with a whole number between \$0\$ and \$9999\$ kg weight worth of items
  • Use any convenient format for I/O
  • Shortest code wins!
\$\endgroup\$
5
  • \$\begingroup\$ Can we do the input and output numbers in any order if we use a flat list? \$\endgroup\$
    – xnor
    Mar 12 '20 at 22:02
  • \$\begingroup\$ @xnor yes, as long as it's consistent \$\endgroup\$
    – Beefster
    Mar 12 '20 at 22:05
  • 5
    \$\begingroup\$ Here is a demonstration :-p \$\endgroup\$
    – Arnauld
    Mar 13 '20 at 0:35
  • 3
    \$\begingroup\$ I believe some of your input and output are incorrect. #5 and #6 at least are all of by one. 9999*4,2,2,1 makes 89,991 but you forgot the +1 for the platform it's on. \$\endgroup\$
    – Mathgeek
    Mar 13 '20 at 17:50
  • 1
    \$\begingroup\$ @Arnauld Corrected. \$\endgroup\$
    – Beefster
    Mar 16 '20 at 16:28

20 Answers 20

9
\$\begingroup\$

Jelly, 14 bytes

3Ḷ×þ`ZU$Ƭ×µ§§‘

Try it online!

Takes input as a 3x3 matrix and outputs a list going clockwise starting from the bottom-right.

Explanation

3Ḷ×þ`ZU$Ƭ×µ§§‘     Main Link
3Ḷ                 [0, 1, 2]
  ×þ`              outer product by multiplication with itself ([0, 0, 0], [0, 1, 2], [0, 2, 4])
        Ƭ          (include the original, plus) rotate clockwise until results are no longer unique (4 results total)
     ZU$           zip and upend (clockwise rotation)
         ×         vectorized multiply with original (gets the workload distributions to each balloon)
           §§      sum results for each balloon (vectorized-sum rows in the matrix; sum the results)
              ‘    increment
\$\endgroup\$
8
\$\begingroup\$

Python 2, 58 57 56 bytes

lambda c,*b:[b[~i]*4-~c+b[i]*2+b[i-2]*2for i in 0,2,4,6]

Try it online!

Input: 9 numbers, representing the board in the following orders:

 6 1 8
 3 0 7
 4 5 2

Output: list of length 4, representing the balloons as follow:

1 0
2 3

Explanation

lambda c,*b: separates the 9 numbers into the center c and a list of length 8 representing the corner and edge values:

5 0 7
2 _ 6
3 4 1

The reason for this is because length 8 works nicely with negative index, as shown as follow:

                Indices    |  Indices mod 8
Edge 1 (i)     0  2  4  6  |  0  2  4  6
Edge 2 (i-2)  -2  0  2  4  |  6  0  2  4
Corner (~i)   -1 -3 -5 -7  |  7  5  3  1

-1 byte thanks to @xnor!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ 74 :) Really nice! \$\endgroup\$
    – RGS
    Mar 13 '20 at 0:07
  • \$\begingroup\$ I would upvote again if I could! Good job on finding a nice index distribution that works well for you! I had golfed my Python answer but now you beat me again by 1 byte!!! :) \$\endgroup\$
    – RGS
    Mar 13 '20 at 0:43
  • 1
    \$\begingroup\$ Nice answer, I actually had almost the same. you can cut the parens around (0,2,4,6) in Python 2. \$\endgroup\$
    – xnor
    Mar 13 '20 at 1:26
  • 1
    \$\begingroup\$ A clever idea with the ~i. Might it be possible to go further with i,~i,-i? \$\endgroup\$
    – xnor
    Mar 13 '20 at 1:59
  • 2
    \$\begingroup\$ I'm trying but so far it doesn't seem possible. Let a,b,c,d be the first edges for the balloons, then the second edges must be b, c, d, a or d, a, b, c (aka shift by 1 left or right). Notice that both ~i and -i reverse the ordering of i, so -i and ~i must be the 2 edge sequences. However, the 2 sequences differ by only 1, so they cannot form the same set unless the length of the list is 4. \$\endgroup\$ Mar 13 '20 at 2:06
5
\$\begingroup\$

Python 3, 86 78 77 bytes

Saved 8 bytes thanks to xnor!!!
Saved a byte thanks to S.S. Anne!!!

lambda b:[[4*b[i][j]+2*b[1][j]+2*b[i][1]-~b[1][1]for j in(0,2)]for i in(0,2)]

Try it online!

Uses a list of lists for both input (\$3\times3\$) and output (\$2\times2\$).

\$\endgroup\$
6
  • 1
    \$\begingroup\$ It looks like you can pre-double i and j to 0 and 2. \$\endgroup\$
    – xnor
    Mar 12 '20 at 21:49
  • \$\begingroup\$ @xnor Sweet - thanks! :-) \$\endgroup\$
    – Noodle9
    Mar 12 '20 at 21:52
  • \$\begingroup\$ 77 bytes \$\endgroup\$
    – S.S. Anne
    Mar 12 '20 at 22:07
  • 1
    \$\begingroup\$ @S.S.Anne Tried a smaller refactoring that didn't save any bytes. Very nice - thanks! :-) \$\endgroup\$
    – Noodle9
    Mar 12 '20 at 22:10
  • \$\begingroup\$ You really don't need those parenthesized expressions but it's better than seeing 2* everywhere. The main thing is in -~b[1][1] instead of 1+(...)+b[1][1]. \$\endgroup\$
    – S.S. Anne
    Mar 12 '20 at 22:12
5
\$\begingroup\$

Python 2, 69 63 59 58 57 bytes

lambda l:[2*(2*l[i]+l[i%2]+l[i/2])-~l[8]for i in 4,5,6,7]

Try it online!

The input is in this order:

4 0 6
2 8 3
5 1 7

and output is

0 2
1 3

-1 thanks to @SurculoseSputum

I kept this solution because I started thinking about shuffling indices with it:

Python 3.8 (pre-release), 82 81 80 bytes

def f(l):*l,d=l;return[(l:=l[2:]+l[:2])and-~d+2*(l[1]+l[7]+2*l[0])for _ in'0'*4]

Try it online!

Thanks HyperNeutrino, SSAnne and Surculose Sputum for -1 each!

\$\endgroup\$
7
  • \$\begingroup\$ you have an extra space between in and '0000' \$\endgroup\$
    – hyper-neutrino
    Mar 12 '20 at 21:53
  • \$\begingroup\$ @HyperNeutrino thanks \$\endgroup\$
    – RGS
    Mar 12 '20 at 21:54
  • 1
    \$\begingroup\$ 81 bytes \$\endgroup\$
    – S.S. Anne
    Mar 12 '20 at 22:01
  • 2
    \$\begingroup\$ easy -1 byte by using '0'*4 instead of 0000 \$\endgroup\$ Mar 13 '20 at 0:02
  • \$\begingroup\$ Nevermind! Yours is 58 bytes too! \$\endgroup\$ Mar 13 '20 at 1:04
5
\$\begingroup\$

R, 76 64 50 bytes

-12 bytes thanks to Giuseppe!

-8 bytes with outer product %*%

-6 bytes by changing the order of the output

scan()%*%matrix(c(y<-2:0%o%c(2:0,0:2),rev(y)),9)+1

Try it online!

Takes input as 9 integers, top to bottom and left to right. Output is in order (NW, SW, NE, SE).

Performs the matrix multiplication of the input vector with the matrix

4   0   0   0
2   0   2   0
0   0   4   0
2   2   0   0
1   1   1   1
0   0   2   2
0   4   0   0
0   2   0   2
0   0   0   4

which is constructed by inputting the values of the first two columns, and then combining with those columns in reverse.

\$\endgroup\$
5
  • \$\begingroup\$ 70 bytes \$\endgroup\$
    – Giuseppe
    Mar 12 '20 at 23:33
  • \$\begingroup\$ 64 bytes by building the weights matrix with a couple of shortcuts. Or 64 bytes building the matrix by base conversion and shifting the outputs around a bit. \$\endgroup\$
    – Giuseppe
    Mar 13 '20 at 1:18
  • \$\begingroup\$ @Giuseppe Nice, thanks! \$\endgroup\$ Mar 13 '20 at 10:00
  • 2
    \$\begingroup\$ I'm afraid a much more boring approach is possible here: codegolf.stackexchange.com/a/200971/66252 \$\endgroup\$ Mar 13 '20 at 10:09
  • \$\begingroup\$ @user2390246 Good job! I have managed to reduce substantially the code to represent the matrix in my answer - I'm hopeful I can find a further 3 bytes to equal yours! \$\endgroup\$ Mar 13 '20 at 14:05
5
\$\begingroup\$

05AB1E, 26 25 17 14 bytes

2Ý‚Dδδ*€€*OO>

-8 bytes by porting @HyperNeutrino's Jelly answer, so make sure to upvote him!!
-3 bytes thanks to @Grimmy.

I/O are both integer-matrices. The output-matrix is mirrored diagonally (i.e. if the input-matrix would be [[a,b,c],[d,e,f],[g,h,i]] the output-matrix would result in [[I,G],[C,A]]).

Try it online or verify all test cases.

Explanation:

2Ý       # Push list [0,1,2]
  Â      # Bifurcate it (short for Duplicate & Reverse copy)
   ‚     # Pair those two together: [[0,1,2],[2,1,0]]
    D    # Duplicate it
     δ   # Apply double-vectorized:
      δ  #  Inner apply double-vectorized:
       * #   Multiply:
         #    [[[[0,0,0],[0,1,2],[0,2,4]],
         #      [[0,0,0],[2,1,0],[4,2,0]]],
         #     [[[0,2,4],[0,1,2],[0,0,0]],
         #      [[4,2,0],[2,1,0],[0,0,0]]]]
€        # Map over each inner pair of matrices:
 €       #  Map over each matrix in this pair:
  *      #   Multiply each by the (implicit) input-matrix at the same indices
O        # Sum each row of the inner-most matrices
 O       # Sum those row-sums together as well
  >      # And increase each by 1 for the board itself
         # (after which the result is output implicitly)
\$\endgroup\$
3
  • \$\begingroup\$ Døí => Âø for -1 (rotate ccw instead of cw, but that's just as good) \$\endgroup\$
    – Grimmy
    Mar 13 '20 at 14:19
  • 1
    \$\begingroup\$ 14 with output as a matrix: 2ÝÂ)Dδδ*€€*OO> \$\endgroup\$
    – Grimmy
    Mar 13 '20 at 14:27
  • \$\begingroup\$ @Grimmy Thanks! \$\endgroup\$ Mar 13 '20 at 20:22
3
\$\begingroup\$

R, 47 bytes

x=scan();4*x[1:4]+2*x[5:8]+2*x[c(6:8,5)]+x[9]+1

Try it online!

Input is a vector in the order

1 6 2 
5 9 7 
4 8 3

And output

1 2
4 3
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6),  63  57 bytes

Takes input as a flat array of 9 integers. Outputs a flat array of 4 integers.

a=>[0,2,6,8].map(i=>a[i]*4+2*(a[3+i%6]+a[i>2?7:1])-~a[4])

Try it online!

How?

Below is the matrix of the item indices:

$$\pmatrix{ 0&\color{red}1&2\\ \color{blue}3&4&\color{blue}5\\ 6&\color{red}7&8}$$

We iterate on the indices of the corners \$i\in\{0,2,6,8\}\$.

The index of the left or right edge (\$\color{blue}3\$ or \$\color{blue}5\$) is given by:

$$H_i=3+(i\bmod6)$$

The index of the top or bottom edge (\$\color{red}1\$ or \$\color{red}7\$) is given by:

$$V_i=\cases{ 1&\text{if $i\le2$}\\ 7&\text{if $i>2$} }$$

\$\endgroup\$
3
  • \$\begingroup\$ 62 bytes \$\endgroup\$
    – Shaggy
    Mar 12 '20 at 22:57
  • \$\begingroup\$ @Shaggy Thanks, but I was already editing to something shorter. \$\endgroup\$
    – Arnauld
    Mar 12 '20 at 23:10
  • \$\begingroup\$ 55 by taking input as a "spiral" \$\endgroup\$
    – RGS
    Mar 12 '20 at 23:48
2
\$\begingroup\$

Charcoal, 27 bytes

F⁴«≔E³E⮌θ§μκθ⟦I⊕ΣEθ×λΣEκ×νμ

Try it online! Link is to verbose version of code. Outputs the four corners in order top right, top left, bottom left, bottom right as compared to the test case format. Explanation:

F⁴«

Process each corner in turn.

≔E³E⮌θ§μκθ

Rotate the board.

⟦I⊕ΣEθ×λΣEκ×νμ

Multiply each row and column by its coordinate, then sum the results, and increment the final total.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 90 86 bytes

lambda a,b,c,d,e,f,g,h,i:(4*a+2*b+2*d-~e,2*b+2*f+4*c-~e,2*d+4*g+2*h-~e,2*f+2*h+4*i-~e)

Try it online!

Thanks @xnor for the -4.

\$\endgroup\$
4
  • \$\begingroup\$ Looks like you can save some bytes writing +2*x+1 as +x-~x \$\endgroup\$
    – xnor
    Mar 12 '20 at 21:40
  • \$\begingroup\$ I just noticed there's expressions of +x+1, which could more simply be replaced with -~x \$\endgroup\$
    – xnor
    Mar 12 '20 at 21:46
  • \$\begingroup\$ I think you messed something up there with the edit \$\endgroup\$
    – xnor
    Mar 12 '20 at 22:04
  • \$\begingroup\$ @xnor fixed, sorry for that \$\endgroup\$
    – RGS
    Mar 12 '20 at 22:22
2
\$\begingroup\$

APL (Dyalog Extended), 16 bytes

1+{⍉⊥2↑⍉↑⍵⍮⌽⍵}⍣2

Try it online!

An anonymous function that takes a 3x3 matrix and returns a 2x2 matrix.

How it works

1+{⍉⊥2↑⍉↑⍵⍮⌽⍵}⍣2  ⍝ Input: 3x3 matrix of numbers
  {     ↑⍵⍮⌽⍵}    ⍝ Join the input with its horizontal reverse,
                  ⍝ adding a leading length-2 axis
   ⍉   ⍉          ⍝ For each row (last axis),
     2↑           ⍝ Take the first two numbers x, y and
    ⊥             ⍝ Apply base-2, i.e. evaluate (2×x)+y
                  ⍝ (equivalent to dot product with [2 1 0])
              ⍣2  ⍝ Repeat the above twice
1+                ⍝ Increment element-wise
\$\endgroup\$
2
\$\begingroup\$

Excel (as CSV), 92 bytes

,,,=1+A1*4+(B1+A2)*2+B2,=1+C1*4+(B1+C2)*2+B2
,,,=1+A3*4+(B3+A2)*2+B2,=1+C3*4+(B3+C2)*2+B2
,,

To use: Input between ,'s, save as CSV, open in Excel.

Eg:

12,9,35,=1+A1*4+(B1+A2)*2+B2,=1+C1*4+(B1+C2)*2+B2
1,32,2,=1+A3*4+(B3+A2)*2+B2,=1+C3*4+(B3+C2)*2+B2
4,6,18
\$\endgroup\$
2
\$\begingroup\$

GolfScript, 73 bytes

:a;0{..2/2*:x;2%2*:y;).2%!a...x=y=4*\x=1=2*+\1=y=2*+\1=1=+)`" "+\n*+\}4*;

Just here to submit something. Cool question! stack-based languages are NOT the solution. Fuck this shit, lmfao.

Could probably golf with better modulo shit, but I've stopped caring lol

Try the really "golf-inputted" one, awkward for input

Same program, weird header and footer to format OP's input into the one above, easier to use and test. Plus, look at that identically-formatted output. Gorgeous, ainnit?

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

Perl 5 -MList::Util=sum -MPOSIX -a, 76 bytes

map$_*=++$i==5||$i%2*2+2,@F;map{say ceil.25+sum@F[$_,$_+1,$_+3,$_+4]}0,1,3,4

Try it online!

Input:

If the grid is denoted as:

a b c
d e f
g h i

Then the input is space separated:

a b c d e f g h i

Output:

Output is line separated:

balloons attached at a
balloons attached at c
balloons attached at g
balloons attached at i
\$\endgroup\$
1
\$\begingroup\$

Jelly, 21 19 bytes

3,1p`ạ€3Rp`¤P€€×³§‘

Try it online!

How?

Notice that we can create the weight matrices for each corner by finding the absolute difference to the opposite corners.

For example, for the first balloon, the weight matrix is

4 2 0
2 1 0
0 0 0

This can be found by, for each coordinate, find the absolute difference to the corner (3, 3), and product. For example, (1, 1) has an absolute difference (2, 2) and product 4.

3,1p`ạ€3Rp`¤P€€×³§‘    Main link
3,1                      Get 3,1 pair
   p`                    cartesian product with itself, gives the 3 corner coordinates
       3Rp`¤             Get all the coordinates
     ạ€                  get the absolute differences for each corner coordinate
            P€€          product each subsublist
               ׳        vectorize multiply with the input
                 §‘      sum each sublist and increment
\$\endgroup\$
1
\$\begingroup\$

Jelly, 14 bytes

ŒJḂ§2*ṁ×⁸+Ɲ⁺€‘

A monadic Link accepting a list of lists of integers which yields a list of list of integers:
[[top-left, top-right], [bottom-left, bottom-right]]

Try it online!

How?

ŒJḂ§2*ṁ×⁸+Ɲ⁺€‘ - Link: list of lists of integers, T    e.g. [[ 3, 9, 5],[ 1, 3, 2],[ 4, 6, 1]]
ŒJ             - multidimensional indices (T)               [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
  Ḃ            - least significant bit (vectorises)         [[1,1],[1,0],[1,1],[0,1],[0,0],[0,1],[1,1],[1,0],[1,1]]
   §           - sums                                       [2,1,2,1,0,1,2,1,2]
    2          - literal two                                2
     *         - exponentiate                               [4,2,4,2,1,2,4,2,4]
      ṁ        - mould like (T)                             [[ 4, 2, 4],[ 2, 1, 2],[ 4, 2, 4]]
        ⁸      - chain's left argument, T                   [[ 3, 9, 5],[ 1, 3, 2],[ 4, 6, 1]]
       ×       - multiply (vectorises)                      [[12,18,20],[ 2, 3, 4],[16,12, 4]]
          Ɲ    - for neighbours:
         +     -   add (vectorises)                         [[14,21,24],[18,15, 8]]
            €  - for each:
           ⁺   -   repeat last link                         [[35,45],[33,23]]
               - (...i.e +Ɲ for each)
             ‘ - increment (vectorises)                     [[36,46],[34,24]]
\$\endgroup\$
1
\$\begingroup\$

Haskell, 67 66 bytes

f a b c d e f g h i=[2*v+e+1|v<-[2*a+b+d,b+2*c+f,d+2*g+h,f+h+2*i]]

Try it online!

Inspired by my Python answer.

\$\endgroup\$
3
  • \$\begingroup\$ @BjarturThorlacius thanks for your suggested edit with the improvement. However, in this community it is good practice to leave a comment with the suggestion for the golfing you find or, alternatively, leave a TIO link with the shorter code version! \$\endgroup\$
    – RGS
    Mar 15 '20 at 17:21
  • 1
    \$\begingroup\$ Good to know, I had no idea. Also, I accidentally wiped out the text you had written below your solution on how the solution was inspired by your Python solution. \$\endgroup\$ Mar 15 '20 at 17:35
  • \$\begingroup\$ No problem x2 :) Enjoy this community! Code-golfing can be quite fun! \$\endgroup\$
    – RGS
    Mar 15 '20 at 17:41
0
\$\begingroup\$

brainfuck, 138 bytes

,[->++++<],[->++>++<<],[->>++++<<],[->++>>++<<<],[->+>+>+>+<<<<],[->>++>>++<<<<],[->>>++++<<<],[->>>++>++<<<<],[->>>>++++<<<<]>+.>+.>+.>+.

Try it online!, just for the byte count.

Try it here, by pasting this input: \12\9\35\1\32\2\4\6\18 and hitting the "view memory" button to compare it with the expected output 101 195 063 121.

\$\endgroup\$
1
  • \$\begingroup\$ No comments?... \$\endgroup\$
    – S.S. Anne
    Mar 13 '20 at 0:05
0
\$\begingroup\$

Pyth, 24 bytes

mh+eQ+ys<.<ecPQ4d2yy@Qd4

Try it online!

I/O format: List [0, 1, 2, 3, 4, 5, 6, 7, 8] (input) and [0, 1, 2, 3] (output) with positions

Input: 0 5 1     Output: 0 1
 = Q   4 8 6             3 2
       3 7 2

Explanation

m                      4   # map [0, 1, 2, 3] to (current number = d)
 h                         # 1 +
  +eQ                      # Q[-1] + 1 +
      ys                   #   2 * sum of
           ec  4           #     chop       into pieces of length 4, take last element
             PQ            #          Q[:-1]                 -> [4,5,6,7]
         .<     d          #     rotate left by d
        <        2         #     first two elements -> [4,5], [5,6], [6,7] or [7,4]
     +                     # +
                  yy       #   4 *
                    @Qd    #       Q[d]
\$\endgroup\$
0
\$\begingroup\$

PHP, 101 bytes

A rather inelegant solution. Just multiples corners by 4, sides by 2 and adds 1 to the center than adds up each corner. Some form of matrix multiplication may be possible with array_map().

parse_str($argv[1]);$e++;echo$a*4+$b*2+$d*2+$e,$c*4+$b*2+$f*2+$e,$g*4+$d*2+$h*2+$e,$i*4+$f*2+$h*2+$e;

Try it online!

It takes input as a string in a html query format e.g. a=9999&b=3&c=9001&d=0&e=9998&f=9999&g=9999&h=999&i=9999

+7 bytes if the output can't be an unseparated list, by making it into an array and using print_r()

PHP, 108 bytes

parse_str($argv[1]);$e++;print_r([$a*4+$b*2+$d*2+$e,$c*4+$b*2+$f*2+$e,$g*4+$d*2+$h*2+$e,$i*4+$f*2+$h*2+$e]);

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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