25
\$\begingroup\$

You are on a plane filled with boxes, and you get a sequence of movements, say "up right right down left":

You move up, pushing all boxes in front of you away:

You move right, right and down, getting

and finally left. This time you only push one box rather than infinite boxes:

At the end, there are 4 spaces.

Given a sequence of moves, decide how many spaces are there after these moves. You can take 4 distinct inputs to mean 4 directions. You can also count yourself as space(result +1). Shortest code in each language wins.

Test data:

R => 1
RD => 2
RL => 1
RDRU => 4
URRDL => 4
UURDLL => 5
DRDDDLUUU => 7
\$\endgroup\$
4
  • \$\begingroup\$ Can you take input as coordinates, like (1,0) for right? \$\endgroup\$
    – mousetail
    Jan 25 at 6:37
  • 1
    \$\begingroup\$ @mousetail You take 4 distant inputs to mean LRUD \$\endgroup\$
    – l4m2
    Jan 25 at 9:02
  • 1
    \$\begingroup\$ Not relevant to the question at all, but I like the illustrations :) \$\endgroup\$ Jan 25 at 16:38
  • 6
    \$\begingroup\$ @97.100.97.109 They are from the game "Baba is you" \$\endgroup\$
    – mousetail
    Jan 25 at 16:43

5 Answers 5

15
\$\begingroup\$

JavaScript (ES6), 94 bytes

-3 bytes thanks to @l4m2

Expects an array of [dx,dy] pairs, e.g. [[-1,0],[1,0]] for LR.

a=>a.map(([h,v],i)=>a[[X=x,Y=y]]=!(g=_=>~--a[[X+=h,Y+=v]]?i--?g():++n:1)(x+=h,y+=v),n=x=y=0)|n

Try it online!

How?

The algorithm used here is pretty straightforward.

Whenever we move in a direction \$(dx,dy)\$, we look for the first empty cell along this ray.

Figure A

If we find one, we mark it as non-empty anymore.

Figure B

Otherwise, we increment the total number of empty cells. In both cases, we mark the cell at our new position as empty.

Note that if we move to an empty cell, it will briefly be marked as non-empty and then marked as empty again, which is conceptually silly but functionally correct.

In order to make sure that we look far enough, the length of the test ray is simply the number of moves performed so far (including the current one).

Commented

a =>            // a[] = input array, re-used to store visited cells
a.map(          // for each ...
([h, v], i) =>  // ... direction [h, v] at index i in a[]:
  a[[           //
    X = x,      //   initialize (X, Y) to (x, y)
    Y = y       //
  ]] =          //   mark this cell as visited (i.e. empty)
  !(            //   by setting it to false
    g = _ =>    //   g is a recursive function ignoring its argument
    ~--a[       //
      [         //     lookup key of the new position
        X += h, //     defined as (X + h, Y + v)
        Y += v  //
      ]         //     we force the state of this cell to non-empty
    ] ?         //     if it already was non-empty:
      i-- ?     //       if i is not equal to 0 (decrement i afterwards):
        g()     //         keep moving along this ray
      :         //       else:
        ++n     //         increment the number n of empty cells and stop
    :           //     else:
      1         //       stop
  )(            //   initial call to g ...
    x += h,     //     ... with (x, y) updated to (x + h, y + v)
    y += v      //
  ),            //
  n = x = y = 0 //   start with n = 0 and (x, y) = (0, 0) 
) | n           // end of map(); return n
\$\endgroup\$
2
  • \$\begingroup\$ Alternative 97 \$\endgroup\$
    – l4m2
    Jan 25 at 15:48
  • \$\begingroup\$ 96 \$\endgroup\$
    – l4m2
    Jan 25 at 17:18
4
\$\begingroup\$

Python 3.8 (pre-release), 130 123 bytes

-7 bytes thanks to @l4m2

def f(l):
 E=set();p=0
 for m in l:E^={p,p+min([q for y in E if(x:=(y-p)/m)==int(q:=x.real)>0]or[0])*m};p+=m
 return len(E)

Try it online!

Takes input as a list of complex numbers.

\$\endgroup\$
1
  • \$\begingroup\$ 123 \$\endgroup\$
    – l4m2
    Jan 25 at 10:38
3
\$\begingroup\$

Vyxal, 20 bytes

Ė¾$(n*:~¨=ȧgF0J‹n/)L

Try it Online! or verify all test cases

A full program accepting a list of strings "1°0", "0°1N", "1°0N", "0°1" for right, down, up, left respectively. Works by keeping a list of empty positions and removing the first one in the direction of travel each time.

Ė              # evaluate (convert each to a complex number)
 ¾             # push empty list
  $            # swap
   (           # for n in directions:
    n*         #   multiply by n
      :        #   duplicate
       ~¨=ȧ    #   keep only real non-negative numbers by checking if they are invariant under abs(x)
           g   #   minimum
            F  #   remove from the original list

0J             #   append 0
  ‹            #   decrement
   n/          #   divide by n
     )         # end for
      L        # length
\$\endgroup\$
3
  • \$\begingroup\$ Please can you explain a little more what Ė exactly does? Thanks! \$\endgroup\$
    – lesobrod
    Feb 5 at 14:19
  • \$\begingroup\$ @lesobrod It just executes a string as vyxal code. Afaik Vyxal can't parse complex number input so I used this to substitute for it. \$\endgroup\$
    – AndrovT
    Feb 5 at 14:43
  • \$\begingroup\$ Aha, now i see! \$\endgroup\$
    – lesobrod
    Feb 5 at 15:30
2
\$\begingroup\$

Pyth, 34 bytes

K,ZZVQ=-aYK<@Ym+VK*LhdNUY1=+VKN;lY

Try it online!

Same basic method as @Arnauld. Takes input as four distinct direction vectors (1,0), (-1,0), (0,1), (0,-1).

Explantion

K is the current position and Y is a list of empty positions.

                                      # implicitly assiqn Q = eval(input())
K,ZZ                                  # K = (0,0)
    VQ                                # for N in Q:
        aYK                           #   append K to Y
              m        UY             #   map range(len(Y)) over lambda d
               +VK*LhdN               #     K + ((d + 1) * N)  (vectorized)
            @Y                        #   intersection of that with Y
           <             1            #   take the first element (or empty list if none)
      =-                              #   remove that element from Y
                          =+VKN       #   K = K + N  (vectorized)
                               ;lY    # after all iterations, output length(Y)
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 31 bytes

Fθ«✳ι#≔KDLθ✳ιθ§≔θ⌕θ#ψ»ψ≔LKAθ⎚Iθ

Try it online! Link is to verbose version of code. Explanation:

Fθ«

Loop over the input string.

✳ι#

Mark the current square as "empty" and move in the given direction.

≔KDLθ✳ιθ

Peek ahead the number of characters in the input string in the direction given by the current character.

§≔θ⌕θ#ψ

Try to erase the first # found (this corresponds to pushing a box there).

»ψ

Erase the finishing square. (This could be »# to count yourself as an empty square.)

≔LKAθ⎚Iθ

Get the number of empty squares, clear the canvas, and output the count.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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