Wprowadzenie

Syzyf miał ostatnio kłopoty w pracy. Wygląda na to, że on po prostu nigdy nic nie robi i chciałby znaleźć rozwiązanie tego problemu.

Jego obecne zatrudnienie wymaga stoczenia skały pod górę. Zwykle dobrze wykonuje swoją pracę, ale za każdym razem, gdy jest blisko szczytu wzgórza, znów się stacza.

Staje się naprawdę sfrustrowany swoją pracą i chce rozwiązać problem naukowo poprzez komputerową symulację skały staczającej się ze wzgórza.

Zdarza się, że Syzyf nie jest szczególnie dobry w programowaniu, więc może możesz mu pomóc?

Wyzwanie

Po tym głupim wprowadzeniu przejdźmy do sprawy. Twój program otrzyma ilustrację wzgórza i skały, która wygląda podobnie do tego:

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

Gdzie #reprezentuje część wzgórza i oskałę.

Teraz musisz wdrożyć program, który przesuwa skałę o 1 warstwę w dół. Na przykład wynik powyższego powinien wynosić:

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

Jeśli jest tam równy poziom, wzgórze tylko toczy się poziomo, więc ...

o
######## 

... to spowodowałoby, że kamień przewróciłby się na bok.

 o
######## 

Jeśli jest obszar pionowy, skała spada o jeden stopień, więc ...

#o
#
#
##### 

... dałby ...

#
#o
#
##### 

Otrzymasz również szerokość i wysokość obrazu odpowiednio w jednym wierszu nad obrazem. Podsumowując, nasze przykładowe dane wejściowe wyglądałyby następująco:

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

(Zauważ, że białe znaki tutaj to spacje. Wybierz tekst i zobacz, co mam na myśli).

Trochę szczegółów

• Gdy kamień znajduje się już w ostatnim wierszu podczas uruchamiania programu, możesz albo zakończyć program, albo wyprowadzić niezmienione wejście
• Wzgórze zawsze schodzi tylko w dół

• Twój program powinien sformatować dane wyjściowe dokładnie tak samo jak dane wejściowe (w tym wymiary), więc jeśli potokujesz dane wyjściowe programu do siebie, oblicza następny krok.

• Możesz założyć, że zawsze jest droga na dół, więc dane wejściowe, w których ścieżka jest „blokowana”, mogą powodować niezdefiniowane zachowanie

• Możesz założyć, że w ostatnim wierszu zawsze znajduje się spacja. Skała powinna tam „odpocząć”, więc po kilkukrotnym wywołaniu programu, zawsze przesyłając swoje wyjście do siebie, powinieneś skończyć ze skałą w ostatnim wierszu, leżąc tam, gdzie wcześniej była przestrzeń.

• Możesz zaakceptować dane wejściowe w dowolnej formie (standardowe, plik, ...). Musisz opublikować CAŁY program (więc wszystkie wstępnie zainicjowane zmienne liczą się jako kod).

• Linie są zakończone za pomocą \n.

• Możesz dostać kilka przykładowych wejść tutaj (upewnij się, że kopia spacje prawidłowo!)

• To jest golf golfowy , więc wygrywa działające zgłoszenie z najmniejszą liczbą bajtów .

• Zwycięzca zostanie wybrany 26 lipca 2014 r. Możesz opublikować rozwiązania, ale nie możesz wygrać

Jeśli masz jakieś pytania, daj mi znać w komentarzach.

Miłej gry w golfa!

Regex (.NET, Perl, PCRE, JavaScript, ... smaki), 25 bajtów

Tak, to spowoduje kolejną debatę, czy wyrażenie regularne jest poprawnym programem, ale uprzedzę to i powiem, że to przesłanie jest dla zabawy i nie trzeba brać pod uwagę zwycięzcy. (W przeciwieństwie do 31-bajtowego wariantu Perl na dole;).)

Oto rozwiązanie zastępujące wyrażenia regularne.

Wzór (zwróć uwagę na spację końcową):

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

Zastąpienie (zwróć uwagę na spację wiodącą):

 $1o

Liczba bajtów jest sumą dwóch.

Możesz to przetestować na stronie http://regexhero.net/tester/ . Pamiętaj, aby wybrać zakończenia linii w stylu uniksowym i „zachować wklejone formatowanie” podczas wklejania. Jeśli nadal nie działa, nadal masz wklejone zakończenia linii w stylu Windows. Najprostszym poprawka w tym przypadku jest zastąpienie \nz\r\n we wzorcu, aby zobaczyć, że to działa.

Oto 48-bajtowa funkcja ECMAScript 6 używająca tego

f=(s)=>s.replace(/o(( *)\n#*)(?=\2) |o /,' $1o')

Wreszcie mam też aktualny program. To 31 bajtów Perla (w tym dwa bajty dla pi 0flagi; dzięki Ventero za sugestię!).

s/o(( *)\n#*)(?=\2) |o / $1o/

Jeśli chcesz to przetestować, nawet nie zapisuj go w pliku, po prostu zrób to

perl -p0e 's/o(( *)\n#*)(?=\2) |o / $1o/' < hill.txt

Python - 190

Horror krojenia i konkatenacji, a także zbyt wiele zmiennych. Jestem pewien, że można bardziej grać w golfa, ale nie mogę teraz wymyślić żadnych sprytnych funkcji Pythona. Dane wejściowe są przechowywane w postaci ciągu 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)

Ponieważ ciągi Pythona są niezmienne, zastępuję znak łącząc wszystkie znaki przed, mój nowy znak i wszystkie znaki po. Używam szerokości wzgórza i indeksowania, aby określić, gdzie skała powinna się toczyć.

Ruby, 65/55 znaków

Pomyślałem, że zobaczę, jak długie jest rozwiązanie, które nie tylko rzuci regex na problem.

r=gets p
r[r[(r[k=1+~/o/+x=r.to_i,2]=~/ /||-x)+k]&&=?o]=" "
$><<r

Zgodnie z oczekiwaniami nie jest tak krótki jak rozwiązanie regularne m.buettner - ale też niewiele dłużej.

Podczas korzystania z flag interpretera można to skrócić do 55 znaków (53 dla kodu, 2 dla flag):

sub$_[($_[k=1+~/o/+x=$_.to_i,2]=~/ /||-x)+k]&&=?o," "

Uruchom kod w następujący sposób:

ruby -p0e 'sub$_[($_[k=1+~/o/+x=$_.to_i,2]=~/ /||-x)+k]&&=?o," "' < input

HTML JavaScript - 251 znaków

( 251, jeśli policzymy kod w pojedynczych cudzysłowach, które odczytują dane wejściowe i zwracają dane wyjściowe. 359 jeśli policzymy pole wprowadzania, ciąg wejściowy, przycisk itp. 192, jeśli policzysz tylko to działa.)

Kod golfa:

<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

Kliknij „Idź” w kółko.

metoda

Używam String.match (), aby podzielić wzgórze na 5 części, a następnie zmieniam jedną lub dwie części. Uczę się JavaScript, więc wszelkie sugestie będą mile widziane.

Kod czytelny

<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 bajty

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))))))

Wprowadziłem kilka znaczących ulepszeń, ale wciąż jest to okropne. Jeszcze kilka bajtów można zaoszczędzić, konwertując to na Python 3, ale nie mogę się rozwiać.

Najpierw znajduję kamień. Jeśli znak bezpośrednio pod nim jest '#', wymienić każde wystąpienie 'o 'z ' o'. Ponieważ na końcu jest zapewnione dodatkowe miejsce, zawsze przesunie to kamień w prawo.

Niezależnie od tego, czy właśnie to zrobiłem, czy nie, transponowałem całą siatkę zip(*m). Następnie zrobić kolejną wymianę 'o 'z ' o'. Jeśli po prawej stronie skały znajduje się przestrzeń, oznacza to, że w prawdziwej siatce znajduje się przestrzeń pod nią, więc się porusza. Następnie transponuję z powrotem i drukuję.

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

Bardziej czytelny

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

php 485 484 znaków

Wiem, że jest to ogromne w porównaniu do wejścia autorstwa m.buettner, ale na razie mogę to zrobić najlepiej. Myślę, że musi istnieć szybszy sposób na przekształcenie łańcucha wejściowego w tablicę wielowymiarową, ale jest już bardzo późno.

I chociaż to niekonkurencyjne, podobała mi się ta łamigłówka. Chciałby, aby rozszerzenie pokazywało, gdzie kończy się kula, lub po określonej liczbie kroków, być może dodane po szerokości i wysokości w linii wprowadzania. Można to bardzo łatwo dodać do tej wersji.

Oto mój kod: Dane wejściowe znajdują się w pierwszej zmiennej.

<?
$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";}

Możesz to zobaczyć tutaj w akcji na codepad

Edycja: Zmieniono powyższy kod i kod, ponieważ wyświetlał 0 zamiast o, co powodowało problem, gdy próbowałem przekazać dane wyjściowe z powrotem do programu. Naprawiono teraz i zapisano jeden znak!

Groovy - 263 261 256 znaków

Grał w golfa Wczytaj plik do ciągu i użyj funkcji pdo emulacji funkcji 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

Niegolfowany (nieco):

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

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="")

Manipulacja łańcuchem nie jest najsilniejszym punktem R.

Bardziej czytelnie:

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);}

Lub, jeśli naprawdę chcesz przeczytać kod:

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 znaków

Bez wyrażenia regularnego. Wymagany plik wejściowy o nazwie „d”. Gra w golfa:

(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)))

Nie golfowany:

(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)))

Przykładowy przebieg (tylko jedna sprawa, dla zwięzłości):

bash-3.2$ cat d
6 7
#     
#     
#     
## o  
####  
####  
##### 

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

Jestem nowicjuszem. Sugestie mile widziane.

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);

Bolesną częścią jest wprowadzanie pliku. Rzeczywiste obliczenia miałyby tylko 114 bajtów:

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]);