Pushing boxes away

Question

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

Answer 1

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.

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

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

Answer 2

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.

Answer 3

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

Answer 4

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)

Answer 5

Charcoal, 31 bytes

Ｆθ«✳ι#≔ＫＤＬθ✳ιθ§≔θ⌕θ#ψ»ψ≔ＬＫＡθ⎚Ｉθ

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

Ｆθ«

Loop over the input string.

✳ι#

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

≔ＫＤＬθ✳ιθ

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

≔ＬＫＡθ⎚Ｉθ

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