Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Introduction

You're playing a matching game, in which coins are inserted at the top and fall to the bottom (onto the top coin) due to gravity.

So this

O <- inserting this coin

OO O
OOOOO

will become this

O
OO O
OOOOO

Now imagine someone rotates the board clockwise. The following will happen:

1. The board is rotated

OOO
OO
O
OO
O

2. Coins fall down due to gravity

O
O
OO
OO
OOO

Your task

Your task is to simulate the rotation of the board by writing a program or a function. For the sake of simplicity we're only dealing with one kind of coin (it's not a too exciting matching game, is it…). You can assume that gravity is applied only after the rotation is complete. The board is rotated clockwise.

Input

The input is going to be a string, which contains 3 types of characters:

  • O (capital o) OR 0 (zero) - a coin (you decide which one your solution supports)
  • (space) - an empty field
  • \n (new line) - end of row

The input represents the state of the board. You can assume, the input is well formed and contains a valid state of the board (no coins are floating). The input can be a function parameter, or can be read from the standard input or from a file.

Output

The output is the new state of the board after rotation. The output contains the same 3 types of characters as the input. The output can be returned from your function or can be written to the standard output or to a file.

Sample

Input1:

O
OO O
OOOOO

Output1:

O
O
OO
OO
OOO

Input2:

O O
O O

Output2:

OO
OO

You can use any language and the standard library of the chosen language. Shortest program in bytes wins.

share|improve this question
    
Are the shorter lines padded with trailing spaces? –  Ventero Jun 26 at 15:05
    
If you need so then yes. –  David Frank Jun 26 at 15:08
    
What are the requirements for the board size? Can I choose a reasonable maximum size, or does the application/function need to work for all possible sizes? –  Fors Jun 26 at 16:16
2  
If gravity is applied after rotation, how does Input2 become Output2? I would have thought it would drop the top coins down but not horizontally? –  Matt Jun 26 at 23:37
2  
@Matt Note, that there are no empty rows in Input2, nor in Output2 (SE displays margin between the rows). –  David Frank Jun 27 at 10:35
show 7 more comments

9 Answers 9

GolfScript, 14 12 characters

' '-n%zip$n*

Input must be given on STDIN, the character for coins can be any non-whitespace characters. Try here. Thanks to Peter for pointing out a two character reduction.

share|improve this answer
    
Oh, what I wouldn't give for a transpose in Ruby that can handle arrays with different lengths ... –  Ventero Jun 26 at 15:07
    
@Ventero Most of the times I use this hacky version: ([nil]*a.map(&:size).max).zip(*a). Not good for golfing though. –  Howard Jun 26 at 15:28
    
You can save 2 chars: since the longest lines always end up at the bottom, you can replace -1% with $. –  Peter Taylor Jun 26 at 15:59
    
@PeterTaylor You're right - we can save to chars. Thank you. –  Howard Jun 26 at 16:12
1  
@PeterTaylor Well, I did include a one-character alias for " ". –  aditsu Jun 26 at 18:01
show 2 more comments

Javascript (E6) 103

First try, just matrix operations. Each row in input string need to be padded.
Quite wordy.

R=t=>(x=t.split('\n').reverse().map(x=>[...x].sort()),x.map((c,i)=>x.map(r=>r[i]).join('')).join('\n'))

Pseudo code

  1. string -> array of rows
  2. up/down reverse array
  3. each row -> char array
  4. sort each row (coins 'fall' to right)
  5. transpose
  6. each char array in a row -> a string
  7. join array -> single string
share|improve this answer
    
Oh wow, sorting is smart (+1)! Mind if I steal it? –  Sieg Jun 26 at 18:46
    
I've never seen the syntax [...x] before. What is it called? –  ComFreek Jun 26 at 21:12
2  
@ComFreak it's called spread [developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… –  edc65 Jun 26 at 21:17
2  
@edc65 You broke your own link with brackets. Here is the correct link –  Chris Cirefice Jun 27 at 17:42
add comment

Ruby 2.0, 59 characters

puts$<.map(&:chars).reverse.transpose.sort[1,50].map &:join

Input via stdin, assumes lines all have the same length. This is probably much longer than necessary. But at least it's readable ...

share|improve this answer
    
I think you can use $<.map instead. –  Howard Jun 26 at 15:08
    
@Howard That's one thing I always forget. Thanks! –  Ventero Jun 26 at 15:09
1  
what is [1,50] doing there? –  Charles Jun 26 at 21:02
1  
@Charles It skips the first row, which contains all the newlines from the input. David mentioned in a comment that 50x50 is the maximum possible size, so instead of selecting all but the first row (1..-1), I just select 50 rows starting with the second one (1,50). –  Ventero Jun 26 at 21:04
    
@Ventero got it. cool. thanks! –  Charles Jun 26 at 21:11
add comment

J - 49 31 24 bytes

I think there might be unnecessary rotations in there, but otherwise it works fine. It's a function that takes the input as specified, coins being O. No trailing whitespace is required in the input.

New version, inspired by edc65's Javascript answer:

f=:[:|."1@|:[:/:~"1,;._2

Explanation:

f=:[:|."1@|:[:/:~"1,;._2
                   ,;._2 Split the string at every fret, which is the last character in the string (newline).
              /:~"1      Sort every row separately.
     |."1@|:             Rotate the array clockwise.

Old version:

f=:[:|:((#~=&' '),=&'O'#])"1@|:@(|."1@|:)@(,;._2)

Explanation:

f=:[:|:((#~=&' '),=&'O'#])"1@|:@(|."1@|:)@(,;._2)
                                          (,;._2) Split the string at every fret, which is the last character in the string (newline).
                                (|."1@|:)@        Rotate the array clockwise.
                             |:@                  Reverse the axes (columns become rows and vice-versa).
       ((#~=&' '),=&'O'#])"1                      Function that applies the "gravity"
                          "1                       Apply to every row separately:
                  =&'O'#]                           Get the O's in the row.
       (#~=&' ')                                    Get the spaces in the row.
                ,                                   Join them, spaces come first.
  [:|:                                            Reverse axes again.

Examples (note that multiline strings start with 0 : 0 and end withh a bracket):

   f 0 : 0
O
OO O
OOOOO
) NB. output starts now
O  
O  
OO 
OO 
OOO
   f 0 : 0
O O
O O
) NB. Output starts now.

OO
OO
share|improve this answer
    
If you can, sort before rotate –  edc65 Jun 26 at 19:07
    
@edc65 You're a smart man. –  Sieg Jun 26 at 19:14
add comment

Haskell — 86

Just learning, so I'm sure this can be improved.

import Data.List
c=putStr.unlines.filter(/="").sort.map(filter(/=' ')).transpose.lines

Sample Input:

let a = "O    \nOO O \nOOOOO"
let b = " O O \n O O "
c a
c b

Sample Output:

O
O
OO
OO
OOO

OO
OO
share|improve this answer
add comment

Python 2 (69) (79)

for c in sorted(zip(*raw_input().split("\\n"))):print''.join(c[::-1])

Takes input padded with spaces so all lines have equal length. The split creates an arrat of each line. The zip effectively transposes the array. Then, the sorted sorts tuples in lexicographic order, causing all coins to fall to the bottom. Finally, we print each line, turning it back into a string, though we must reverse it first. Doing print'O'*c.count('O') is equivalent and uses the same number of characters.

Example run:

>> O    \nOO O \nOOOOO
O
O
OO
OO
OOO
share|improve this answer
add comment

C, 167 119 bytes

This shorter version is (unfortunately?) much clearer than the original too.

m;j;b[99];r;main(){while(j=getchar()+1)j-11?m+=j-33&&++b[r]>m:++r;for(j=r;m+1;putchar(j--?m<b[j]?79:32:(j=r,m--,10)));}
share|improve this answer
add comment

Racket: 130

(let l((a'()))(let((b(sort(string->list(read-line))char<?)))(if
(null? b)(apply map(λ x(map display x)(newline))a)(l(cons b a)))))

It requires you pad with spaces so the lines are equal lemgth.

share|improve this answer
add comment

C# - 209 174 bytes

Right, I have to try this Code golf at some point I reckon. Created a function (r) that rotates the board and prints it. I guess I'm cheating a little when I am printing my char array, but if you cannot figure out why you shouldn't be mad :)

Thanks to ProgramFOX for the tips :)

void r(string s){int x=s.IndexOf('\n'),j,i=-1,k,z=x+1;var y=new char[x*x+x];for(;++i<x;y[z*(i+1)-1]='\n')for(k=j=x;j>0;)if(s[i*z+--j]=='0')y[k--*z-i-2]='0';Console.Write(y);}

Cheat

new char[x*x+x] fills the array with '\0' and not ' '

share|improve this answer
1  
Removing the newlines and removing the space between char[] and y will reduce your character count to 192 characters. Also, it is not really necessary to provide the keyword static when posting an answer here. Removing it will reduce your character count to 185 characters. –  ProgramFOX Jun 27 at 16:20
    
I was also able to remove 'ref ' which was forgotten there since an earlier try. –  WozzeC Jun 27 at 19:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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