Calculate gravity on a 1D field
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
concat.until((==)=<<h)h.map(:[])
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
a::b::t->(function`E,`L|`H,`E->l(b::a::t)|_,`L|`H,_|`F,`F|`E,`E->l((a^b)::t)|_->let
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 ";
"NL";
" SD";
" L D ";
" SDLN ";
" NLLSSD ";
]