# Introduction

Sisyphus was having some troubles at work lately. It seems he just never gets anything done, and he would love to find a solution to this problem.

His current employment requires rolling a rock up a hill. He usually does his job well, but every time he is near the top of the hill it rolls down again.

He is getting really frustrated with his job and wants to solve the problem scientifically by having a computer simulate the rock rolling down the hill.

It so happens that Sisyphus isn't particularly good at programming, so maybe you can help him out?

# The Challenge

After this silly introduction, let's come to business. Your program will receive an illustration of the hill and the rock which looks similar to this:

#o
##
###
######
########


Where # represents a part of the hill and o represents the rock.

You now have to implement a program which moves the rock 1 layer down. For example, the output of the above should be:

#
##o
###
######
########


If there is a horizontally even area, the hill just rolls horizontally, so...

o
########


...this would just make the stone roll sideways.

 o
########


If there is a vertical area, the rock falls down one step, so...

#o
#
#
#####


...would yield...

#
#o
#
#####


You will also receive the width and height of the image respectively in one line above the image. So, in complete, our sample input would look like this:

10 5
#o
##
###
######
#########


(Note that the whitespace here are spaces. Select the text and see what I mean.)

## Some details

• When the rock is already in the last line when running the program, you can choose to either terminate the program or output the unchanged input
• The hill only ever goes downwards
• Your program should format the output exactly the same as the input (including the dimensions), so if you pipe the output of the program to itself, it calculates the next step.

• You can assume there is always a way to the bottom, so input where the path is "blocked" may cause undefined behaviour

• You can assume there is always a space in the last line. The rock should "rest" there, so after calling the program a few times, always piping it's output into itself, you should end up with the rock in the last line, laying where the space previously was.

• You may accept input in any form you like (stdin, file,...). You have to post the WHOLE program (so all pre-initialized variables count as code).

• The lines are terminated with \n.

• You can get some example inputs here (make sure you copy the spaces correctly!)

• This is , so the working submission with the least bytes wins.

• The winner will be chosen on July 26th, 2014. You can post solutions after that, but you can't win

If you have any questions, let me know in the comments.

Happy golfing!

• Will there be a trailing column of whitespace as in your last example? (because the others don't have it) – Martin Ender Jul 18 '14 at 23:14
• @m.buettner In the last example there are only 9 #s, so there is one space at the end because the width is 10. In this case (after a few iterations) the rock would lay where the whitespace is (so at the bottom-right corner). – Christoph Böhmwalder Jul 18 '14 at 23:16
• Yes, I realise that, I was just wondering whether we can assume that's always the case, because it's not for your other examples. (That being said, your other examples don't have any trailing whitespace at all.) – Martin Ender Jul 18 '14 at 23:22
• Missed a great chance to call it "Rock and Roll" – qwr Jul 19 '14 at 0:19
• @HackerCow you're right. Fixed by removing a character :D – Martin Ender Jul 19 '14 at 0:30

## Regex (.NET, Perl, PCRE, JavaScript, ... flavours), 25 bytes

Yes, this will create some debate again, whether a regular expression is a valid program, but I'll pre-empt that and say that this submission is just for fun and doesn't need to be considered for the winner. (As opposed to the 31 byte Perl variant at the bottom ;).)

So here is a pure regex replacement solution.

Pattern (note the trailing space):

o(( *)\n#*)(?=\2) |o


 $1o  The byte count is for the sum of the two. You can test it at http://regexhero.net/tester/. Make sure to choose Unix-style line endings and "preserve pasted formatting" when pasting. If it still doesn't work, you still have pasted Windows-style line endings. The easiest fix in that case is to replace \n with \r\n in the pattern to see that it works. Here is a 48 byte ECMAScript 6 function using this f=(s)=>s.replace(/o(( *)\n#*)(?=\2) |o /,'$1o')


Finally, I've also got an actual program. It's 31 bytes of Perl (including two bytes for p and 0 flags; thanks to Ventero for the suggestion!).

s/o(( *)\n#*)(?=\2) |o / $1o/  If you want to test it, don't even save it in a file, just do perl -p0e 's/o(( *)\n#*)(?=\2) |o /$1o/' < hill.txt

• Doesn't work for me unfortunately (in the online tester). It just always moves the rock to the right. 40 bytes is a great start though, that will be hard to beat! – Christoph Böhmwalder Jul 18 '14 at 23:34
• @HackerCow You're right, I just noticed there's a problem. Fixing... – Martin Ender Jul 18 '14 at 23:36
• @HackerCow No I think it actually works, but "preserve formatting" overwrites the line ending, so if you paste Windows-style line endings it doesn't work (try replacing \n with \r\n) – Martin Ender Jul 18 '14 at 23:37
• For me the rock don't fall when is against the right wall, ie. it only matches it when it has a trailing space. – BrunoJ Jul 18 '14 at 23:39
• How am I supposed to beat this? Great solution – qwr Jul 18 '14 at 23:40

# Python - 190

Slicing and concatenation horror, along with way too many variables. I'm certain this can be golfed more, but I can't think of any clever python functions right now. Input is stored in string s.

r=" "
o="o"
i=s.index(o)
b=i+int(s.split(r)[1])
q=s[:i]+r
x=s[b+3:]
try:
a=s[b+1:b+3]
if a[0]==r:s=q+s[i+1:b+1]+o+r+x
elif a[1]==r:s=q+s[i+1:b+2]+o+x
else:s=q+o+s[i+2:]
except:1
print(s)


Since python strings are immutable, I replace a character by concatenating all the characters before, my new character, and all the characters after. I use the hill width and indexing to determine where the rock should roll to.

## Ruby, 65/55 characters

Figured I'd see how long a solution is that doesn't just throw a regex on the problem.

r=gets p
r[r[(r[k=1+~/o/+x=r.to_i,2]=~/ /||-x)+k]&&=?o]=" "
$><<r  As expected, it's not as short as m.buettner's regex solution - but not much longer either. When using interpreter flags, this can be shortened to 55 characters (53 for the code, 2 for the flags): sub$_[($_[k=1+~/o/+x=$_.to_i,2]=~/ /||-x)+k]&&=?o," "


Run the code like this:

ruby -p0e 'sub$_[($_[k=1+~/o/+x=$_.to_i,2]=~/ /||-x)+k]&&=?o," "' < input  ## HTML JavaScript - 251 chars (251 if you count the code inside the single quotes that reads the input and returns the output. 359 if you count the input box, input string, button, etc. 192 if you count just that does the work.) Golf code: <pre id="i">10 5 #o ## ## ###### ######### </pre><button onclick='i=document.getElementById("i");h=i.innerHTML;if(p=h. match(/([\s\S]*?)([# ]+)(o *\n)(#+)([\s\S]*)/)){if(p[4].length>p[2].length+1)p[3]=p[3]. replace("o "," o");else{p[3]=p[3].replace("o"," ");p[5]="o"+p[5].substr(1);}p[0]=""; h=p.join("");}i.innerHTML=h;'>Go</button>  http://goo.gl/R8nOIK Click "Go" over and over. Method I uses String.match() to break hill into 5 parts, then I change one or two parts. I'm learning JavaScript, so any suggestions would be appreciated. Readable Code <pre id="io">10 5 #o ## ## ###### ######### </pre> <button onclick=' // get image io = document.getElementById("io"); image = io.innerHTML; // break image into five parts // 1(10 5\n# \n## \n) 2(### ) 3(o \n) 4(######) 5( \n######### ) if (parts = image.match(/([\s\S]*?)([# ]+)(o *\n)(#+)([\s\S]*)/)) { // move rock to the right if (parts[4].length > parts[2].length + 1) parts[3] = parts[3].replace("o ", " o"); // or move rock down else { parts[3] = parts[3].replace("o", " "); parts[5] = "o" + parts[5].substr(1); } // return new image parts[0] = ""; image = parts.join(""); // MAP io:i image:h parts:p } io.innerHTML = image; '>Go</button>  # Python 2 - 289 252 bytes p=raw_input w,h=map(int,p().split()) m=[p()for a in[0]*h] j=''.join f=lambda s:s.replace('o ',' o') for i,r in enumerate(m): x=r.find('o') if x+1:y=i;break if m[y+1][x]=='#':m=map(f,m);x+=1 print w,h print'\n'.join(map(j,zip(*map(f,map(j,zip(*m))))))  I made some significant improvements but this is still terrible. A couple more bytes can be saved by converting this to Python 3 but I can't be arsed. First, I find the rock. If the character immediately below it is '#', replace every instance of 'o ' with ' o'. Since there's guaranteed to be an extra space at the end, this will always move the rock to the right. Regardless of if I just did that or not, I transpose the whole grid with zip(*m). Then, I do another replacement of 'o ' with ' o'. If there's a space to the right of the rock, that means that in the real grid there's a space below it, so it gets moved. Then I transpose back and print. • Wouldn't this mess up the OP's 3rd example, where there's empty space to the right of and below the rock, and move it diagonally? – Doorknob Jul 19 '14 at 10:30 • @dor It shouldn't. I only move to the right if the space below is #, and I do that check before I do the check to move vertically. – undergroundmonorail Jul 19 '14 at 10:45 # Python (201) import sys print(input()) g=list(sys.stdin.read()) o='o' x=g.index(o) n=x+g.index('\n')+1 try: if g[n]==' ':g[n]=o elif g[n+1]==' ':g[n+1]=o else:g[x+1]=o g[x]=' ' except:1 print(*g,sep='',end='')  # awk, 152 awk 'NR==1{w=$2}{if(NR<=w&&$0~/o/){r=index($0,"o");g=$0;getline;if(index($0,"# ")<=r){sub("o"," ",g);sub(" ","o")}else{sub("o "," o",g)}print g}print}'


    awk '
NR==1{  //If we're at the first line, set the width from the second column in the header.
width=$2 } { if(NR<=width &&$0~/o/){   //If not at the bottom, look for the line with the rock.
rockIndex=index($0,"o"); //Set the position of the rock. orig=$0;                 //Remember the current line so we can compare it to the next.
getline;                 //Get the next line.

#o
##
###
######
#########';$b=array();$c=explode("\n",$a);$d=explode(" ",$c[0]);$e=$d[0];$f=$d[1];unset($c[0]);$g=0;foreach($c as $h){$b[$g]=str_split($h);++$g;}for($i=0;$i<$f;++$i){for($j=0;$j<$e;++$j){if($b[$i][$j]=='o'){$k=$j;$l=$i;$b[$i][$j]=' ';}}}if($b[$l+1][$k]!='#'){$b[$l+1][$k]='o';}else if($b[$l+1][$k+1]!='#'){$b[$l+1][$k+1]='o';}else{$b[$l][$k+1]='o';}echo"$e$f\n";for($i=0;$i<$f;++$i){for($j=0;$j<$e;++$j){echo $b[$i][$j];}echo "\n";}  You can see it here in action on codepad Edit: Changed codepad and code above as was outputting 0 instead of o, which caused problem when I tried to feed the output back into the program. Fixed now and saved one char! ## Groovy - 263261 256 chars Golfed. Read the file into a String, and use a function p to emulate a function String.putAtIndex(index,value): o="o" b=" " s=new File(args[0]).text z={s.size()-it} s=s[0..z(2)] w=s.find(/\n.*?\n/).size()-1 p={i,v->s=s[0..i-1]+v+((i<z(0)-2)?s[i+1..z(1)]:"")} try{ t=s.indexOf o i=w+t j=i+1 x=t+1 (s[i]==b)?x=i:(s[j]==b)?x=j:0 p x,o p t,b }catch(Exception e){} print s  Ungolfed (somewhat): o = "o" b = " " s = new File(args[0]).text z = {s.size()-it} s = s[0..z(2)] w = s.find(/\n.*?\n/).size()-1 putAtIndex = { i,val -> s = s[0..i-1] + val + ((i<z(0)-2)?s[i+1..z(1)]:"") } try { t=s.indexOf o i=w+t j=i+1 x=t+1 // default x as horizontal move // check for (a) directly below (b) below and over one (s[i]==b) ? x=i : ( (s[j]==b) ? x=j : 0) putAtIndex x,o putAtIndex t,b } catch (Exception e) {} print s  • Nice. I don't know the language, but I'm almost sure you can get rid of (at least) two bytes if you write try{ instead of try { and catch(Exception instead of catch (Exception. – Christoph Böhmwalder Jul 19 '14 at 13:13 • Indeed! Thanks for the note.... – Michael Easter Jul 19 '14 at 13:44 ## R, 234 require(stringr) g=scan(,"") g=do.call(rbind,strsplit(str_pad(g,m<-max(nchar(g)),"r"),"")) if(g[(x<-which(g=="o"))+1]==" "){g[x+1]="o";g[x]=""}else{if(!is.na(g[x+1])){g[x+(n<-nrow(g))]="o";g[x]=""}} for(i in 1:n) cat(g[i,],"\n",sep="")  String manipulation is not R's strongest point. More readably: require(stringr) # load package stringr, available from CRAN. required for str_pad g=scan("") # read input from console g=do.call( # applies the first argument (a function) to the second argument (a list of args to be passed) rbind, # "bind" arguments so that each one becomes the row of a matrix strsplit( # split the first argument by the second str_pad(g,max(nchar(g)),"r"," "), # fill each row with whitespace "") ) if(g[(x<-which(g=="o"))+1]==" ") { # if the next element down from the "o" is " "... g[x+1]="o";g[x]="" # make it an "o" and replace the current element with "" } else { if(!is.na(g[x+1])) { # if the next element down is not empty (i.e. out of range) g[x+nrow(g)]="o"; g[x]="" # move "o" right } } for(i in 1:n) cat(g[i,],"\n",sep="") # print to console  # C (182) char b[1024],*x,*n;main(z){read(0,b,1024);n=index(b,10)+1;x=index(n,'o');z=index(n,10)-n;n=x+z+1;if(n[1]){if(*n==32)*n='o';else if(n[1]==32)n[1]='o';else x[1]='o';*x=32;}printf(b);}  Or, if you actually want to read the code: char b[1024],*x,*n; //1024 byte buffer hard coded main(z){ read(0,b,1024); n=index(b,10)+1; //start of line 2 x=index(n,'o'); z=index(n,10)-n; //10='\n' n=x+z+1; //reusing n if(n[1]){ //if not 0 if(*n==32) //32=' ' *n='o'; else if(n[1]==32) n[1]='o'; else x[1]='o'; *x=32; } printf(b); }  ## Clojure - 366 chars Without regex. Required input file named "d". Golfed: (def s(slurp "d"))(def w(-(.length(re-find #"\n.*?\n" s))2))(def t(.indexOf s "o"))(def i(+ t w 1))(defn g[i,j,x,c](cond (= x i) \ (= x j) \o :else c))(defn j[i,j] (loop[x 0](when(< x (.length s))(print(g i j x (.charAt s x)))(recur(inc x)))))(try(cond(= \ (.charAt s i))(j t i)(= \ (.charAt s (inc i)))(j t (inc i)):else (j t (inc t)))(catch Exception e (print s)))  Ungolfed: (def s (slurp "d")) (def w (- (.length (re-find #"\n.*?\n" s)) 2)) (def t (.indexOf s "o")) (def i (+ t w 1)) (defn g [i,j,x,c] (cond (= x i) \ (= x j) \o :else c)) (defn j [i,j] (loop [x 0] (when (< x (.length s)) (print (g i j x (.charAt s x))) (recur (inc x))))) (try (cond (= \ (.charAt s i)) (j t i) (= \ (.charAt s (inc i))) (j t (inc i)) :else (j t (inc t)))(catch Exception e (print s)))  Sample run (just one case, for brevity): bash-3.2$ cat d
6 7
#
#
#
## o
####
####
#####

bash-3.2\$ java -jar clojure-1.6.0.jar hill.clj
6 7
#
#
#
##
####o
####
#####


I'm a newbie. Suggestions welcome.

# MATLAB, 160

function r(f)

function F=r(F)