14
\$\begingroup\$

Challenge

You are given an ASCII-art representation of characters on a plane as input by any reasonable method. This will only contain:

  • [a-z] representing moveable characters. Every letter will appear on the board at most once.
  • # representing immovable walls
  • . representing empty space

For example:

abcdef.gh#..
.......ij.#.
#..#.......#
...#.#...###
.#.......#q#
.........###

You are also given a string representing the changes in gravity. This will only contain:

  • > representing a change to rightward gravity
  • < representing a change to leftward gravity
  • ^ representing a change to upward gravity
  • v representing a change to downward gravity

For example:

v>^

Your program must simulate the each change in gravity sequentially until all characters stop moving (they hit a wall, or another character). Characters that "fall off the edge of the map" are permanently removed, and characters can "stack" on top of each other.

In this example, at the start there is downward gravity (v), so c, e, g, h, i, and j fall off the bottom of the map. All other characters slide downwards until hitting a wall, leaving the map like this:

.........#..
a..d......#.
#..#.f.....#
.b.#.#...###
.#.......#q#
.........###

Then, we move on to rightward gravity (>), which leaves us with this: Note how the a stacks next to the d.

.........#..
........ad#.
#..#......f#
..b#.#...###
.#.......#q#
.........###

Finally, we simulate upward gravity (^), during which the a and the b fall off the map.

.........#..
.........d#.
#..#......f#
...#.#...###
.#.......#q#
.........###

Your task is to output the remaining characters after the gravitational shifts. They can be given in any order. For this example, you could output any permutation of dfq.

Testcases

For the following map:

abcde
.....
##.##
v   =  abde
v>  =  <nothing>

For the following map:

######
#....#
abcdef
#.gh..
######
>   = <nothing>
<   = gh
^>  = bcde
v<  = bghef
\$\endgroup\$
  • \$\begingroup\$ How is the input given? List of strings? Function argument? STDIN? \$\endgroup\$ – Leaky Nun Apr 9 '16 at 3:56
  • \$\begingroup\$ @KennyLau All of those options are fine. Input and output can be anything reasonable for your language. \$\endgroup\$ – jrich Apr 9 '16 at 3:58
  • \$\begingroup\$ Somewhat related. \$\endgroup\$ – Martin Ender Apr 9 '16 at 6:50
4
\$\begingroup\$

JavaScript (ES6), 251 233 bytes

(m,d,r=`replace`)=>[...d].map(c=>[...`<^>v`].map(d=>m=[...(m=(c==d?m[r](/[.\w]+/g,s=>s[r](/\./g,``)+s[r](/\w/g,``))[r](/^\w+/gm,s=>s[r](/./g,`.`)):m).split`
`)[0]].map((_,i)=>m.map(s=>s[i]).join``).reverse().join`
`))&&m[r](/\W/g,``)

Edit: Saved 18 bytes thanks to @WashingtonGuedes.

Works by rotating the input grid four times for each directional character, but on the direction where the directional character matches the loop character we do the left gravity thing. Pseudocode:

function slideleft(map) {
    map = map.replace(/[.\w+]/g, match=>movedotstoend(match));
    map = map.replace(/^\w+/gm, match=>changetodots(match));
}
function rotate(map) {
    return joinrows(reverse([for each (column of rows(map)[0])
            joinrow([for each (row of rows(map)) row[column]])
           ]));
}
function gravity(map, directions) {
    for each (direction of directions) {
        for each (angle of '<^>v') {
            if (direction == angle) map = slideleft(map);
            map = rotate(map);
        }
    }
    return letters(map);
}
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 199

Same algortihm of @Neil's answer. The grid is rotated four times for each directional character, when in the right position the gravity shift to left is applied to each row.

x=>y=>(x=>{for(d of y){R='';for(e of'^>v<')x=[...x[0]].map((c,i)=>e!=d?x.map(r=>r[i]).join``:x.map(r=>(c=r[i])<'.'?(q+=p+c,p=''):c>'.'&&q?(q+=c,R+=c):p+='.',q=p='')&&q+p).reverse();}})(x.split`
`)||R

F=x=>y=>(x=>{for(d of y){R='';for(e of'^>v<')x=[...x[0]].map((c,i)=>e!=d?x.map(r=>r[i]).join``:x.map(r=>(c=r[i])<'.'?(q+=p+c,p=''):c>'.'&&q?(q+=c,R+=c):p+='.',q=p='')&&q+p).reverse();}})(x.split`
`)||R

// Less golfed

U=(x,y)=>
{
  x = x.split`\n`;
  for(d of y)
  {
    R = '';
    for(e of '^>v<')
      x = [...x[0]].map( 
        (c,i) => e != d
        ? x.map( r => r[i] ).join`` // basic rotation
        : x.map( // rotation with gravity shift
          r=> (c=r[i])<'.' ? (q+=p+c,p='') : c>'.'&&q?(q+=c,R+=c) : p+='.', q=p=''
        ) && q+p
      ).reverse();
  }
  return R
}

console.log=x=>O.textContent+=x+'\n'

;[
  ['abcdef.gh#..\n.......ij.#.\n#..#.......#\n...#.#...###\n.#.......#q#\n.........###',
   [['v>^','dfq']]
  ],
  ['abcde\n.....\n##.##',[['v','abde'],['v>','']]],
  ['######\n#....#\nabcdef\n#.gh..\n######',[['>',''],['<','gh'],['^>','bcde'],['v<','befgh']]]
].forEach(t => {
  var i=t[0]
  console.log(i)
  t[1].forEach(([d,k])=>{
    var r=F(i)(d),ok=[...r].sort().join``==k
    console.log((ok?'OK ':'KO ')+d+' : '+r+(ok?'':' (expected '+k+')'))
  })
  console.log('')
})
<pre id=O></pre>

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

Pyth, 143 bytes

(Do we really need that much bytes?)

JhQKeQMe.u:N+"\."H+H"."G;DybVkI}NG=gkN;D'bVlJ=k@JNykVkI}HG=:kH\.).?B)=XJNk;VKIqN\<'J)IqN\v=C_J'J=_CJ)IqN\>=C_CJ'J=C_CJ)IqN\^=CJ'J=CJ;VJVNI}HGpH

Try it online!

How it works

We define a function left which does the leftward gravity thing.

Then, the other directions are implemented by messing with the array so that the desired direction is leftwards, then do left.

The algorithm of left is here:

  • Do the following until idempotent:
  • Replace ".X" with "X.", where X represents a letter.

The whole program is divided into the following 6 sections:

JhQKeQ
Me.u:N+"\."H+H"."G;
DybVkI}NG=gkN;
D'bVlJ=k@JNykVkI}HG=:kH\.).?B)=XJNk;
VKIqN\<'J)IqN\v=C_J'J=_CJ)IqN\>=C_CJ'J=C_CJ)IqN\^=CJ'J=CJ;
VJVNI}HGpH

First section

JhQKeQ     Q auto-initialized to evaluate(input())
JhQ        J = Q[0]
   KeQ     K = Q[len(Q)-1]

Second section

Me.u:N+"\."H+H"."G;   @memoized
M                 ;   def g(G,H):
  .u             G      repeat_until_idempotent(start:G, as N):
    :Nxxxxxxyyyyy         return N.replace(xxxxxx,yyyyy)
      +"\."H                               "\."+H
            +H"."                                 H+"."

Third section

DybVkI}NG=gkN;    @memoized
Dyb          ;    def y(b):
   Vk               for N in k:     --TAKES GLOBAL VARIABLE k
     I}NG             if N in G:    --G pre-initialized to "abcde...z"
         =gkN           k = g(k,N)

Fourth section

D'bVlJ=k@JNykVkI}HG=:kH\.).?B)=XJNk;  @memoized
D'b                                ;  def single_quote(b):
   VlJ                       )          for N in range(len(J)): --TAKES GLOBAL VARIABLE J
      =k@JN                               k = J[N] --SETS GLOBAL VARIABLE k
           yk                             y(k) --returns nothing, but MODIFIES GLOBAL VARIABLE k
             Vk                           for H in k:
               I}HG      )                  if H in G:
                   =:kH\.                     k = k.replace(H,".")
                          .?                else:
                            B                 break
                              =XJNk     J[N] = k --MODIFIES GLOBAL VARIABLE J

Fifth section

VKIqN\<'J)IqN\v=C_J'J=_CJ)IqN\>=C_CJ'J=C_CJ)IqN\^=CJ'J=CJ;
VK                                                       ; for N in K:
  IqN\<  )                                                   if N == '<':
       'J                                                      single-quote(J)
          IqN\v          )                                   if N == 'v':
               =C_J                                            J = transpose(reverse(J))
                   'J                                          single-quote(J)
                     =_CJ                                      J = reverse(transpose(J))
                          IqN\>            )                 if N == '>':
                               =C_CJ                           J = transpose(reverse(transpose(J)))
                                    'J                         single-quote(J)
                                      =C_CJ                    J = transpose(reverse(transpose(J)))
                                            IqN\^            if N == '^':
                                                 =CJ           J = transpose(J)
                                                    'J         single-quote(J)
                                                      =CJ      J = transpose(J)

Sixth section

VJVNI}HGpH
VJ           for N in J:
  VN           for H in N:
    I}HG         if H in G: --G = "abc...z"
        pH         print(H)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 306 bytes

Anonymous function. Pretty circuitous technique that could probably be optimized.

->s,d{w=[];x=y=0;m={}
s.chars.map{|c|c>?!?(c<?A?c<?.?w<<[x,y]:0:m[c]=[x,y]
x+=1):(x=0;y+=1)}
d.chars.map{|c|q=[c<?=?-1:c<?A?1:0,c>?a?1:c>?A?-1:0];e=1
(n=m.clone.each{|k,v|z=[v[0]+q[0],v[1]+q[1]]
w.index(z)||m.value?(z)?0:m[k]=z}
m.reject!{|k,v|i,j=v;i<0||i>=x||j<0||j>y}
e=(m!=n ?1:p))while e}
m.keys.join}
\$\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.