Вы катаетесь на каноэ по довольно быстрой реке Уайтуотер. Внезапно ваши весла взрываются, и вы попадаете в опасную ситуацию, быстро несущуюся по реке без каких-либо весел. К счастью, у вас все еще есть свои навыки программирования, поэтому вы решили вырезать программу на байдарке, чтобы помочь вам пережить пороги. Однако на стороне каноэ недостаточно места для написания вашей программы, поэтому вы должны сделать программу максимально короткой.

Река может быть представлена ​​в виде сетки 8 на 16. Мы будем маркировать столбцы с номерами 0до 7и строк с номерами 0к 15.

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

Вверху: совершенно спокойная, обычная река без препятствий. Естественно, это не та река, на которой вы находитесь.

Вы начинаете с координаты (4, 0) и оттуда неконтролируемо двигаетесь вверх по реке (т.е. к вектору (0,1)), пока не натолкнетесь на скалу (обозначенную oв этих примерах как). Когда вы попадаете в камень, у вас будет 55% шанс пройти мимо камня влево (т.е. вектор (-1,1)) и 45% шанс пройти мимо камня вправо (то есть вектор (1,1)). Если каноэ находится в крайнем левом или правом столбцах, оно всегда будет двигаться к центру. Если нет камней, он будет двигаться прямо вверх.

        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

Вверху: возможный маршрут, по которому может идти каноэ, представленный персонажем x

Учитывая карту реки, напишите программу, которая выведет вероятность окончания каноэ в данном столбце.

Принимайте ввод любым удобным для вашей программы способом (например, STDIN, аргумент командной строки raw_input(), чтение из файла и т. Д.). Первая часть ввода представляет собой одно целое число от 0 до 7, представляющее столбец, для которого программа найдет вероятность. После этого приведен список кортежей в форме, x,yпредставляющей положение камней.

Пример:

Входные данные:

4 4,1 5,5 3,5

Это указало бы на реку с камнями в позициях (4,1), (5,5) и (3,5), и спрашивает о вероятности окончания каноэ в 4-м столбце.

Выход:

0.495

Обратите внимание, что в этом примере положение пород было симметричным, что позволило решить проблему с биномиальным распределением. Это не всегда так!

Также река всегда будет проходимой. То есть никогда не будет двух камней, которые расположены рядом друг с другом по горизонтали. См . Комментарий Гленна для примера невозможного случая.

Это код гольф, поэтому выигрывает меньшее количество персонажей. Не стесняйтесь задавать вопросы в комментариях, если спецификация не ясна.

GolfScript, 105 символов

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

Версия GolfScript, которая стала намного длиннее, чем предполагалось, но каждая попытка с другим подходом была еще длиннее. Ввод должен быть дан на STDIN.

Пример:

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

Аннотированный код:

# 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?*

Рубин, 204 191 172 персонажа

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]

Он рекурсивно моделирует все возможные результаты, отслеживая вероятность каждого отдельного результата, а затем добавляет эту вероятность к совокупному счетчику, когда y == 15.

Необычные трюки:

• c,*r=gets.split- оператор «splat» ( *) берет все оставшиеся элементы gets.splitи помещает их в rмассив

• next {something} if {condition}: по существу эквивалентно

  if {condition}
      {something}
      return
  end
  

  «Обнаружен» путем эволюции от if condition; something; return; endк return something if conditionк break something if condition, и тогда я решил, что попробую более короткий «оператор цикла», чтобы посмотреть, сработает ли он (что, конечно, и так).

• Спасибо @ MartinBüttner за предложение использовать цепные троичные операторы (которые в итоге превратились в огромную третью строку в приведенном выше коде игры в гольф) и исключить вышеуказанный пункт (который сохранил 19 (!) Символов).

  Я использовал несколько причудливый трюк с этим: я понял, что s[foo],s[bar]в Ruby это не работает для двух вызовов метода в одном выражении. Так что сначала я изменил его (_=s[foo],s[bar])(переменный фиктивный), но потом я понял , что я мог бы просто добавить и выбросить возвращаемые значения: s[foo]+s[bar]. Это работает только потому, что вызовы sбудут только «возвращать» другие вызовы sили номер ( o[x]+=p), поэтому мне не нужно беспокоиться о проверке nil.

• Другие различные оптимизации: pвместо того, putsчтобы печатать числа, <1вместо ==0(поскольку каноэ никогда не покидает реку) и аналогичных сравнений где-либо еще, [0]*8для начальных вероятностей, поскольку числа Руби всегда «передаются по значению»

Ungolfed:

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 байта

Завершите программу на C #, ожидая ввода от STDIN. Работает, считывая камни в массив всех мест в реке, эффективно создавая карту, а затем выполняет 16 итераций перемещения вероятностей вокруг десятичного массива шириной 8, прежде чем выводить результат.

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

Форматированный код:

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 байт

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

Вот очень неряшливая версия вместе с некоторыми уловками, которые были использованы:

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)

Последним трюком, который я использовал, было отметить, что вы можете действовать так, как будто камни в одном ряду на самом деле разделены каким-то бесконечно малым количеством. Другими словами, вы можете применять преобразователь распределения вероятностей для каждой породы в одной и той же строке последовательно и в любом порядке, а не применять их все одновременно. Это работает только потому, что проблема не позволяет двум горизонтально смежным камням.

Таким образом, программа превращает местоположение каждого камня в трансформатор распределения вероятности, упорядоченный по координате y камня. Затем трансформаторы просто упорядочиваются и применяются к начальному распределению вероятностей. И это все!

Perl 169 байт

Читает из 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{$&}

Довольно прямолинейно, неявно использует столбцы -1 и 8 для сглаживания границ. Вероятности можно безопасно распространять на каждый следующий уровень, потому что нет соседних камней, поэтому достаточно одного прогона.

PHP, 358

Использовать интеллектуальные возможности для определения возможных путей и их вероятностей сложно, и, вероятно, потребуется больше кода, чем просто симуляция 1 000 000 аварий на каноэ. О, человечество!

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

Пример:

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

Golfed:

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

Эта версия не выполняет красивую печать и выводит вероятность плавания на каноэ в указанной позиции.

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

PHP, 274

Я не могу читать / писать GolfScript, чтобы спасти мою жизнь, но, глядя на представление @ Говарда, он направил меня в лучшем направлении, чем простая имитация 1 миллиона каноэ.

Начиная с массива вероятностей для стартовых позиций, мы можем просто разделить эти числа каждый раз, когда встречается камень.

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

Пример вывода:

# 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

Golfed:

<? $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];

Пример выполнения:

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

Хаскелл, 237

Я просто надеюсь, что каноэ идет с установленным GHC ...

Уловка с бесконечным списком украдена у Мэтта Нунана, слава ему!

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

Я надеюсь, что я понял правильную логику, но пример Мэтта "5 4,4 1,5 5,3 3,6 2,9 4,12 3,13"уступает, 0.5613750000000001а пример OP "4 4,1 5,5 3,5"дает0.49500000000000005 , что представляется правильным за исключением некоторых ошибок с плавающей точкой.

Вот оно в действии:

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