Given a string or list, calculate the effects of gravity on that string/list.

The string will be made of 5 characters:

  • N has a weight of 2
  • L has a weight of 1
  • S has a weight of -2
  • D has a weight of -1

(the 5th character is whatever you want, it means empty space. I use (space) in my examples)

Items with negative weight fall upwards (towards the top of the string), and items with positive weight fall downwards (towards the bottom of the string).

When an object collides with something, one of three things happens:

  • If the object collides with the top or bottom "walls" of the input, then it just stops.

  • If the object collides with another object, their weight/velocity is summed (i.e. N and D would give 1). If the result is positive, both objects fall downwards. If it's negative, they fall upwards.

  • If an object (let's call it A) collides with an object B, and B is already pinned against the ceiling/floor, A will just come to rest against B.

All non-occupied spaces of the string/list should be filled with the empty character.

If it wasn't clear already: each character in the string/line is on top of the next one. i.e. NL is the same as:


And SD is:


Test cases: (uses (the space character) to show empty space)

" L D " -> " LD  " or "  LD "

" SDLN " -> "SD  LN"

" NLLSSD " -> "NLLSSD  "
  • 3
    \$\begingroup\$ "Given a delimited string or list." Can also use a string without delimiters? Since all items are just individual characters that shouldn't be a problem, right? And what's the expected outcome for N0S or L0D? \$\endgroup\$ – Martin Ender May 10 '17 at 18:59
  • \$\begingroup\$ @MartinEnder About the delimited string, that was left over form a previous version of the question. It has been edited out. And I added a test case to address the second issue. If it is still unclear, please let me know. \$\endgroup\$ – Comrade SparklePony May 10 '17 at 20:52
  • \$\begingroup\$ Why the NUL character? \$\endgroup\$ – mbomb007 May 10 '17 at 21:21
  • \$\begingroup\$ Should've specified a directional order-of-operations. \$\endgroup\$ – Magic Octopus Urn May 16 '17 at 19:54
  • \$\begingroup\$ Side note: if "physics" is to be accounted for, letters with negative weights should probably fall downwards just like the rest. \$\endgroup\$ – Julian Wolf May 16 '17 at 23:04

Haskell, 169 180 bytes

g s=sum[n|c<-s,(d,n)<-zip"SD LN"[-2..],c==d]
w=elem ' '
h(x:y:r)|(w x&&g y<0)||(w y&&g x>0)=y:h(x:r)|w(x++y)||g x<0=x:h(y:r)|t<-x++y=h$t:r
h r=r

Try it online! Example usage: concat.until((==)=<<h)h.map(:[]) $ " SDLN ".

Edit: +11 bytes, now also works for the " NSDLLD " test case proposed by @zgrep.

(short) Explanation:

h works on a list of tokens where initially each char of the input string is token. Until the token list no longer changes, h bubbles through the list comparing two tokens x and y at a time. Depending on the tokens their order is kept (x:h(y:r)), they are swapped (y:h(x:r)) or combined to a single token (t<-x++y=h$t:r).

g computes the weight of a token and w checks whether a token contains a space.


OCaml, 379 bytes

let rec n f a i=try n f(f a i)(i+1)with _->a
let r s=String.(concat""(let rec w s=if ' '=s.[0]then`E else(function
0->`F|w when w<0->`L|_->`H)(n(fun a i->index"SD LN"s.[i]-2+a)0 0)and l=function
c=a::l(b::t)in if b=List.nth c 1 then c else l c)(w a,w b)|x->x in l(n(fun a
i->a@[sub s i 1])[]0)))

To test:

let () =
    List.iter (fun s -> Printf.printf "`%s`\n" (r s)) [
        "   S S   S S   ";
        "   D D   D D   ";
        "               ";
        "   L L   L L   ";
        "   N N   N N   ";
        " SD";
        " L D ";
        " SDLN ";
        " NLLSSD ";

Python 2, 322 bytes

Try it online

import re
while S!=D:
 for i in[(i.group(),i.span())for i in re.finditer('\w+',S)]:
    if g:S=S[:i[1][0]-1]*l+re.sub('^ '*l+i[0]+' $'*b,''.join([i[0],' '][::c]),[S[i[1][0]-1:],S[:i[1][1]+1]][b])+S[i[1][1]+1:]*b
print S

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.