20
\$\begingroup\$

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 code-golf, 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!

Improve this question
\$\endgroup\$
16
  • \$\begingroup\$ Will there be a trailing column of whitespace as in your last example? (because the others don't have it) \$\endgroup\$
    – Martin Ender
    Commented Jul 18, 2014 at 23:14
  • \$\begingroup\$ @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). \$\endgroup\$
    – Christoph Böhmwalder
    Commented Jul 18, 2014 at 23:16
  • \$\begingroup\$ 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.) \$\endgroup\$
    – Martin Ender
    Commented Jul 18, 2014 at 23:22
  • 8
    \$\begingroup\$ Missed a great chance to call it "Rock and Roll" \$\endgroup\$
    – qwr
    Commented Jul 19, 2014 at 0:19
  • 1
    \$\begingroup\$ @HackerCow you're right. Fixed by removing a character :D \$\endgroup\$
    – Martin Ender
    Commented Jul 19, 2014 at 0:30

13 Answers 13

Reset to default
38
\$\begingroup\$

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

Replacement (note the leading space):

 $1o

The byte count is for the sum of the two.

You can test it at https://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
Improve this answer
\$\endgroup\$
10
  • \$\begingroup\$ 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! \$\endgroup\$
    – Christoph Böhmwalder
    Commented Jul 18, 2014 at 23:34
  • \$\begingroup\$ @HackerCow You're right, I just noticed there's a problem. Fixing... \$\endgroup\$
    – Martin Ender
    Commented Jul 18, 2014 at 23:36
  • \$\begingroup\$ @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) \$\endgroup\$
    – Martin Ender
    Commented Jul 18, 2014 at 23:37
  • \$\begingroup\$ For me the rock don't fall when is against the right wall, ie. it only matches it when it has a trailing space. \$\endgroup\$
    – BrunoJ
    Commented Jul 18, 2014 at 23:39
  • 4
    \$\begingroup\$ How am I supposed to beat this? Great solution \$\endgroup\$
    – qwr
    Commented Jul 18, 2014 at 23:40
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ My eyes hurt. +1 \$\endgroup\$
    – Christoph Böhmwalder
    Commented Jul 19, 2014 at 10:00
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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>

https://goo.gl/R8nOIK
click "Go" over and over
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>
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$
    – Doorknob
    Commented Jul 19, 2014 at 10:30
  • \$\begingroup\$ @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. \$\endgroup\$
    – undergroundmonorail
    Commented Jul 19, 2014 at 10:45
2
\$\begingroup\$

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='')
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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}'

More Readable

    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.
      if(index($0,"# ")<= rockIndex){  //Move down: if the rock is on a cliff or on a slope,
        sub("o"," ",orig);             //update the orig so that the rock is removed
        sub(" ", "o")                  //and update the current (first available position).
      }                                         
      else {                           //Move right: if the rock is on flat ground,
        sub("o "," o", orig)           //update the orig so the the rock is advanced.
      }
      print orig                       //Print the line we skipped (but stored      
    }                                  //and updated based on the line we're now on).
    print                              //Print the line we're now on.
  }
'
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

php 485 484 chars

I know this is massive compared to entry by m.buettner but is best I can do for now. I think there must be a quicker way to turn the input string into a multi dimensional array but it is very late now.

And although it it uncompetitive I liked this puzzle. Would like the extension to show where the ball ends up, or after a set number of steps, perhaps added after the width and height on the input line. Could add that very easily to this version.

Here is my code: Input is in the first variable.

<?
$a.='10 5
#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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Groovy - 263 261 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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Christoph Böhmwalder
    Commented Jul 19, 2014 at 13:13
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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);
}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

MATLAB, 160

function r(f)
F=cell2mat(table2array(readtable(f)));
m=@(d)mod(d-1,size(F,1));C=find(F=='o');P=find(F==' ');N=min(P(P>C&m(P)>=m(C)));F([C,N])=F([N,C]);
disp(F);

The painful part is the file-input. The actual computation would be only 114 bytes:

function F=r(F)
m=@(d)mod(d-1,size(F,1));C=find(F=='o');P=find(F==' ');N=min(P(P>C&m(P)>=m(C)));F([C,N])=F([N,C]);
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.