Płyniesz kajakiem po dość szybkiej rzece o białych wodach. Nagle wiosła eksplodują i znajdujesz się w niebezpiecznej sytuacji, pędzącej szybko rzeką bez żadnych wioseł. Na szczęście nadal masz umiejętności programistyczne, więc postanawiasz wykuć program na boku kajaka, aby pomóc ci przetrwać bystrza. Jednak z boku czółna nie ma zbyt dużej powierzchni do pisania programu, więc program musi być jak najkrótszy.

Rzekę można przedstawić jako siatkę 8 na 16. Oznaczymy kolumny liczbami 0do 7i wierszy liczbami 0do 15.

        y
--------15
--------14
--------13
--------12
--------11
--------10
--------9
--------8
--------7
--------6
--------5
--------4
--------3
--------2
--------1
--------0
01234567
x

Powyżej: całkowicie spokojna, zwykła rzeka bez przeszkód. Oczywiście nie jest to rzeka, na której płyniesz.

Zaczynasz od współrzędnej (4, 0), a stamtąd poruszasz się w sposób niekontrolowany w górę rzeki (tj. Wektora (0,1)), aż uderzysz w skałę (reprezentowaną przez ow tych przykładach jako). Kiedy uderzysz w skałę, będziesz miał 55% szansy na przejście obok skały w lewo (tj. Wektor (-1,1)) i 45% szansy na przejście obok skały w prawo (tj. Wektor (1,1)). Jeśli czółno znajduje się na skrajnych lewych lub prawych kolumnach, zawsze przesunie się w kierunku środka. Jeśli nie ma skał, przesunie się prosto w górę.

        y
----x---15
----xo--14
-o--x---13
----x---12
---ox---11
---x----10
---xo---9
---ox---8
----xo--7
-----x--6
----ox--5
-o--x---4
----x---3
----xo--2
----x---1
----x---0
01234567

Powyżej: możliwa trasa, którą może płynąć kajak, przedstawiony za pomocą postaci x

Biorąc pod uwagę mapę rzeki, napisz program, który wyświetli prawdopodobieństwo zakończenia czółna w danej kolumnie.

Zaakceptuj dane wejściowe dowolną metodą dogodną dla Twojego programu (np. STDIN, argument wiersza poleceń raw_input(), odczyt z pliku itp.). Pierwsza część danych wejściowych to pojedyncza liczba całkowita od 0 do 7, reprezentująca kolumnę, dla której program znajdzie prawdopodobieństwo. Poniżej znajduje się lista krotek w formie x,yreprezentującej pozycję kamieni.

Przykład:

Wkład:

4 4,1 5,5 3,5

Oznaczałoby to rzekę ze skałami w pozycjach (4,1), (5,5) i (3,5) i prosi o prawdopodobieństwo, że kajak zakończy się w czwartej kolumnie.

Wydajność:

0.495

Należy zauważyć, że w tym przykładzie położenia skał były symetryczne, co pozwoliło rozwiązać problem z rozkładem dwumianowym. Nie zawsze tak będzie!

Ponadto rzekę zawsze można pokonywać. Oznacza to, że nigdy nie będzie dwóch skał, które byłyby ustawione poziomo obok siebie. Zobacz komentarz Glenna, aby zobaczyć przykład niemożliwego przypadku.

To jest kod golfowy, więc wygrywa najmniejsza liczba znaków. Jeśli specyfikacja nie jest jasna, możesz zadawać pytania w komentarzach.

GolfScript, 105 znaków

~](\2/:A;8,{4=}%15,{:B;{20*}%A{~B={[\\,.1,*\[2$=..20/9*:C-\~)C]+(1,\+1,6*2$8>+]zip{{+}*}%.}*;}/}/=20-15?*

Wersja GolfScript, która stała się znacznie dłuższa niż zamierzona - ale każda próba z innym podejściem była jeszcze dłuższa. Dane wejściowe należy podać na STDIN.

Przykład:

> 4 4,1 5,5 3,5
99/200

Kod z adnotacjami:

# Evaluate the input
#  - stack contains the first number (i.e. column)
#  - variable A contains the rock coordinates (pairs of X y)
#    where X is an array of length x (the coordinate itself)
~](\2/:A;

# Initial probabilities
#  - create array [0 0 0 0 1 0 0 0] of initial probabilities
8,{4=}%

# Loop over rows 
15,{:B;           # for B = 0..14
  {20*}%          #   multiply each probability by 20
  A{              #   for each rock 
    ~B={          #     if rock is in current row then
                  #       (prepare an array of vectors [v0 vD vL vR] 
                  #       where v0 is the current prob. before rocks,
                  #       vD is the change due to rocks,
                  #       vL is a correction term for shifting out to the left
                  #       and vR the same for the right side)
      [\\         #       move v0 inside the array
      ,           #       get x coordinate of the rock
      .1,*        #       get [0 0 ... 0] with x terms
      \[2$=       #       get x-th item of v0
      ..20/9*:C-  #       build array [0.55P -P 0.45P]
      \~)C]+      #       and append to [0 0 ... 0]
      (1,\+       #       drop the leftmost item of vD and prepend [0] again
                  #       which gives vL
      1,6*2$8>+   #       calculate vR using the 8th item of vD
      ]           #       
      zip{{+}*}%  #       sum the columns of this list of vectors
      .           #       dummy dup for end-if ;
    }*;           #     end if
  }/              #   end for
}/                # end for

# take the n-th column and scale with 20^-15
=
20-15?*

Ruby, 204 191 172 znaków

c,*r=gets.split
o=[0]*8
s=->x,y,p{y>14?o[x]+=p :(r.index("#{x},#{y+=1}")?(x<1?s[x+1,y,p]:(x>6?s[x-1,y,p]:(s[x-1,y,p*0.55]+s[x+1,y,p*0.45]))):s[x,y,p])}
s[4,0,1]
p o[c.to_i]

Rekurencyjnie symuluje wszystkie możliwe wyniki, jednocześnie śledząc prawdopodobieństwo każdego wyniku, a następnie dodaje to prawdopodobieństwo do licznika skumulowanego, kiedy y == 15.

Fantazyjne sztuczki:

• c,*r=gets.split- operator „splat” ( *) pobiera wszystkie pozostałe elementy gets.spliti umieszcza je w rtablicy

• next {something} if {condition}: zasadniczo równoważne z

  if {condition}
      {something}
      return
  end
  

  „Odkryte” poprzez ewolucję od if condition; something; return; enddo return something if conditiondo break something if condition, a potem pomyślałem, że spróbuję krótszego „operatora pętli”, aby zobaczyć, czy zadziała (co oczywiście zrobiło).

• Dzięki @ MartinBüttner za sugestię użycia przyklejonych operatorów trójskładnikowych (co ostatecznie stało się ogromną trzecią linią w powyższym kodzie golfowym) i wyeliminowanie powyższego punktu (co uratowało 19 (!) Znaków).

  Użyłem jednak nieco fantazyjnej sztuczki: zdałem sobie sprawę, że s[foo],s[bar]nie działa w Ruby dla dwóch wywołań metod w jednej instrukcji. Więc w pierwszej chwili zmienił go do (_=s[foo],s[bar])(zmiennej obojętne), ale potem zdałem sobie sprawę, mogę tylko dodać i wyrzucić wartości zwracanych: s[foo]+s[bar]. Działa to tylko dlatego, że wywołania do zawsze sbędą „zwracać” inne połączenia slub numer ( o[x]+=p), więc nie muszę się martwić o sprawdzenie nil.

• Inne różne optymalizacje: pzamiast putsdo drukowania liczb, <1zamiast ==0(ponieważ kajak nigdy nie opuszcza rzeki) i podobnych porównań gdzie indziej, [0]*8dla początkowych prawdopodobieństw, ponieważ liczby Ruby są zawsze „przekazywane przez wartość”

Nie golfowany:

column, *rocks = gets.chomp.split
outcomes = Array.new(8, 0)
simulate = -> x, y, probability {
    if y == 15
        outcomes[x] += probability
    elsif rocks.index("#{x},#{y + 1}")
        case x
        when 0 then simulate[x + 1, y + 1, probability]
        when 7 then simulate[x - 1, y + 1, probability]
        else
            simulate[x - 1, y + 1, probability * 0.55]
            simulate[x + 1, y + 1, probability * 0.45]
        end
    else
        simulate[x, y + 1, probability]
    end
}
simulate[4, 0, 1.0]
p outcomes
puts outcomes[column.to_i]

C # 418 364 bajtów

Kompletny program C # oczekuje danych wejściowych od STDIN. Działa poprzez wczytywanie skał do tablicy wszystkich miejsc w rzece, skutecznie tworząc mapę, a następnie wykonuje 16 iteracji prawdopodobieństw przesunięcia wokół tablicy dziesiętnej o szerokości 8 przed wygenerowaniem wyniku.

using C=System.Console;class P{static void Main(){var D=C.ReadLine().Split();int i=0,j=D.Length;var R=new int[8,16];var p=new decimal[8];for(p[4]=1;--j>0;)R[D[j][0]-48,int.Parse(D[j].Substring(2))]=1;for(;i<16;i++){var n=new decimal[j=8];for(;j-->0;)if(R[j,i]>0){n[j<1?1:j-1]+=p[j]*0.55M;n[j>6?6:j+1]+=p[j]*0.45M;}else n[j]+=p[j];p=n;}C.WriteLine(p[D[0][0]-48]);}}

Sformatowany kod:

using C=System.Console;

class P
{
    static void Main()
    {
        var D=C.ReadLine().Split();
        int i=0,j=D.Length;
        var R=new int[8,16];
        var p=new decimal[8];

        for(p[4]=1;--j>0;) // read rocks into map (R)
            R[D[j][0]-48,int.Parse(D[j].Substring(2))]=1;

        for(;i<16;i++) // move up the river
        {
            var n=new decimal[j=8];
            for(;j-->0;)
                if(R[j,i]>0)
                { // we hit a rock!
                    n[j<1?1:j-1]+=p[j]*0.55M;
                    n[j>6?6:j+1]+=p[j]*0.45M;
                }
                else
                    n[j]+=p[j];
            p=n; // replace probability array
        }

        C.WriteLine(p[D[0][0]-48]); // output result
    }
}

Haskell, 256 bajtów

import Data.List
m=map;v=reverse
a p n x=take n x++(x!!n+p:drop(n+1)x)
l=abs.pred
o[_,n]s=n#(s!!n)$s
n#p=a(11*p/20)(l n).a(9*p/20)(7-(l$7-n)).a(-p)n
b=0:0:0:0:1:b
k(c:w)=(foldl1(.)$m o$v$sort$m(v.read.('[':).(++"]"))w)b!!read c
main=getLine>>=print.k.words

Oto bardzo nie golfowa wersja wraz z kilkoma zastosowanymi sztuczkami:

import Data.List

-- Types to represent the distribution for the canoe's location
type Prob = Double
type Distribution = [Prob]

-- Just for clarity..
type Index = Int

-- An Action describes some change to the probability distribution
-- which represents the canoe's location.
type Action = Distribution -> Distribution

-- Helper to add k to the nth element of x, since we don't have mutable lists.
add :: Index -> Prob -> Action
add n k x = take n x ++ [p] ++ drop (n + 1) x
    where p = k + x!!n  

-- A trick for going finding the index to the left of n,
-- taking the boundary condition into account.
leftFrom n = abs (n - 1)

-- A trick for getting the other boundary condition cheaply.
rightFrom = mirror . leftFrom . mirror
    where mirror = (7 -)

-- Make the action corresponding to a rock at index n.
doRock :: Index -> Action
doRock n p = (goLeft . goRight . dontGoForward) p
    where goLeft  =  (leftFrom n) `add` (p_n * 11/20)
          goRight = (rightFrom n) `add` (p_n * 9/20)
          dontGoForward =  (at n) `add` (-p_n)
          p_n = p!!n
          at = id

initialProb = [0,0,0,0,1,0,0,0]

-- Parse a pair "3,2" ==> (3,2)
readPair :: String -> (Index,Index)
readPair xy = read $ "(" ++ xy ++ ")"

-- Coordinate swap for the sorting trick described below.
swap (x,y) = (y,x)

-- Put it all together and let it rip!
main = do
    input <- getLine
    let (idx : pairs) = words input
    let coords = reverse . sort $ map (swap . readPair) pairs
    let rockActions = map (doRock . snd) coords
    let finalProb = (foldl1 (.) rockActions) initialProb
    print $ (finalProb !! read idx)

Ostatnią sztuczką, jaką zastosowałem, było zwrócenie uwagi na to, że skały w jednym rzędzie są rzeczywiście oddzielone przez nieskończenie małą ilość. Innymi słowy, można zastosować transformator rozkładu prawdopodobieństwa dla każdej skały w tym samym rzędzie sekwencyjnie i w dowolnej kolejności, zamiast stosować je wszystkie jednocześnie. Działa to tylko dlatego, że problem uniemożliwia dwie poziomo sąsiadujące skały.

Tak więc program zamienia położenie każdej skały w transformator rozkładu prawdopodobieństwa, uporządkowany według współrzędnej y skały. Transformatory są następnie łączone w łańcuchy i stosowane do początkowego rozkładu prawdopodobieństwa. I to jest to!

Perl 169 bajtów

Czyta ze STDIN.

$_=<>;s/ (.),(\d+)/$s{$1,$2}=1/eg;/./;$x{4}=1.0;for$y(1..15){for$x(0..7){if($s{$x,$y}){$x{$x-1}+=$x{$x}*($x%7?.55:1);$x{$x+1}+=$x{$x}*($x%7?.45:1);$x{$x}=0}}}print$x{$&}

Całkiem prosto, domyślnie wykorzystuje kolumny -1 i 8, aby wygładzić przypadki graniczne. Prawdopodobieństwa można bezpiecznie przenosić na każdy następny poziom, ponieważ nie ma żadnych sąsiadujących kamieni, dlatego wystarczy jeden przebieg.

PHP, 358

Użycie siły mózgowej do ustalenia możliwych ścieżek i ich prawdopodobieństwa jest trudne i prawdopodobnie wymagałoby więcej kodu niż zwykła symulacja 1 000 000 wypadków na kajakach. Oh ludzkość!

define('MX',7);
define('MY',16);
define('IT',1000000);
error_reporting(0);

function roll(){return rand()%100 > 44;}

function drift($rocks,$print=false) {
    for($px=4,$py=0;$py<MY;$py++) {
        if(isset($rocks[$px][$py])){
            if(roll()) $px--;
            else $px++;
        }
        else if($px==0) $px++;
        else if($px==MX) $px--;
        if($print) {
            for($i=0;$i<MX;$i++){
                if($i==$px) echo 'x';
                else if(isset($rocks[$i][$py])) echo 'o';
                else echo '-';
            }
            echo " $py\n";
        }
    }
    return $px;
}

$input = $argv[1];
$tmp = explode(' ',$input);
$end_target = array_shift($tmp);
$rocks = array();
array_map(function($a) use(&$rocks) {
    list($x,$y) = explode(',',$a);
    $rocks[$x][$y]=1;
}, $tmp);

$results=array();
for($i=0;$i<IT;$i++) {
    $results[drift($rocks)]++;
}

drift($rocks, true); // print an example run

foreach($results as $id=>$result) {
    printf("%d %0.2f\n", $id, $result/IT*100);
}

Przykład:

php river.php "4 4,1 5,5 3,3 6,2 9,4 12,3 13,5"
----x-- 0
---xo-- 1
---x--o 2
--xo--- 3
--x---- 4
--x--o- 5
--x---- 6
--x---- 7
--x---- 8
--x---- 9
--x---- 10
--x---- 11
--x---- 12
--x---- 13
--x---- 14
--x---- 15
4 49.53
2 30.18
6 20.29

Gra w golfa:

<? function d($r){for($x=4,$y=0;$y<16;$y++){if(isset($r[$x][$y])){if(rand()%100>44)$x--;else $x++;}elseif($x==0)$x++;elseif($x==7)$x--;}return $x;}$t=explode(' ',$argv[1]);$e=array_shift($t);$r=array();array_map(function($a)use(&$r){list($x,$y)=explode(',',$a);$r[$x][$y]=1;},$t);$c=0;for($i=0;$i<1000000;$i++){if(d($r)==$e)$c++;}printf("%.4f", $c/1000000);

Ta wersja nie wykonuje żadnego ładnego wydruku i wyświetla prawdopodobieństwo pływakowego lądowania czółna w określonej pozycji.

# php river_golf.php "4 4,1 5,5 3,3 6,2 9,4 12,3 13,5"
0.4952

PHP, 274

Nie umiem czytać / pisać GolfScript, aby uratować mi życie, ale zerknięcie na poddanie @ Howarda wskazało mi lepszy kierunek niż po prostu symulacja 1 miliona wypadków na kajakach.

Zaczynając od szeregu prawdopodobieństw dla pozycji początkowych, możemy po prostu podzielić te liczby za każdym razem, gdy napotkasz kamień.

function psplit($i){ return array(.55*$i,.45*$i); }
function pt($a) {
    foreach($a as $p) {
        printf("%1.4f ", $p);
    }
    echo "\n";
}

$input = $argv[1];
$tmp = explode(' ',$input);
$end_target = array_shift($tmp);
$rocks = array();
array_map(function($a) use(&$rocks) {
    list($x,$y) = explode(',',$a);
    $rocks[$x][$y]=1;
}, $tmp);

$state = array(0,0,0,0,1,0,0,0);
pt($state);
for($y=1;$y<16;$y++){
    for($x=0;$x<8;$x++){
        if(isset($rocks[$x][$y])){
            echo('   o   ');
            list($l,$r)=psplit($state[$x]);
            $state[$x]=0;
            $state[$x-1]+=$l;
            $state[$x+1]+=$r;
        } else { echo '   -   '; }
    }
    echo "\n";
    pt($state);
}

Przykładowe dane wyjściowe:

# php river2.php "4 4,1 5,5 3,3 6,2 9,4 12,3 13,5"
0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000
   -      -      -      -      o      -      -      -
0.0000 0.0000 0.0000 0.5500 0.0000 0.4500 0.0000 0.0000
   -      -      -      -      -      -      o      -
0.0000 0.0000 0.0000 0.5500 0.0000 0.4500 0.0000 0.0000
   -      -      -      o      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.2475 0.4500 0.0000 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.2475 0.4500 0.0000 0.0000
   -      -      -      -      -      o      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
   -      -      -      -      -      -      -      -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000

Gra w golfa:

<? $t=explode(' ',$argv[1]);$e=array_shift($t);$r=array();foreach($t as $n){list($j,$k)=explode(',',$n);$r[$j][$k]=1;}$s=array(0,0,0,0,1,0,0,0);for($y=1;$y<16;$y++){for($x=0;$x<8;$x++){if(isset($r[$x][$y])){$s[$x-1]+=$s[$x]*.55;$s[$x+1]+=$s[$x]*.45;$s[$x]=0;}}}echo $s[$e];

Przykładowy przebieg:

# php river2_golf.php "4 4,1 5,5 3,3 6,2 9,4 12,3 13,5"
0.495

Haskell, 237

Mam tylko nadzieję, że kajak ma zainstalowany ghc ...

Sztuczka z nieskończoną listą została skradziona Mattowi Noonanowi, ku czci dla niego!

import Data.List
r=reverse
(a:b:x)%0=0:a+b:x
x%7=r(r x%0)
x%n=take(n-1)x++(x!!(n-1)+x!!n*0.55:0:x!!(n+1)+x!!n*0.45:drop(n+2)x)
q=0:0:0:0:1:q
u(w:x)=(foldl(%)q.map last.sort.map(r.read.('[':).(++"]"))$x)!!read w
main=interact$show.u.words

Mam nadzieję, że dobrze zrozumiałem logikę, ale przykład Matta "5 4,4 1,5 5,3 3,6 2,9 4,12 3,13"daje 0.5613750000000001i przykład OP "4 4,1 5,5 3,5"daje 0.49500000000000005, co wydaje się poprawne, pomijając pewne błędy zmiennoprzecinkowe.

Oto jest w akcji:

>>> echo 5 4,4 1,5 5,3 3,6 2,9 4,12 3,13 | codegolf
0.5613750000000001