Vous pagayez en canoë sur une rivière d'eau vive assez rapide. Soudain, vos pagaies explosent et vous vous retrouvez dans une situation dangereuse dévalant une rivière rapide sans pagaies. Heureusement, vous avez toujours vos compétences en programmation, vous décidez donc de vous tailler un programme sur le côté de votre canoë pour vous aider à survivre aux rapides. Cependant, il n'y a pas beaucoup de surface sur le côté du canoë pour écrire votre programme, vous devez donc le rendre aussi court que possible.

La rivière peut être représentée par une grille de 8 sur 16. Nous allons étiqueter les colonnes avec les nombres 0à 7et les lignes avec les nombres 0à 15.

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

Ci-dessus: une rivière ordinaire, complètement calme et sans obstruction. Naturellement, ce n'est pas la rivière sur laquelle vous vous trouvez.

Vous commencez aux coordonnées (4, 0) et à partir de là, vous remontez de façon incontrôlable la rivière (c'est-à-dire le vecteur (0,1)) jusqu'à ce que vous heurtiez un rocher (représenté par un odans ces exemples). Lorsque vous frappez un rocher, vous aurez 55% de chances de passer devant le rocher vers la gauche (ie le vecteur (-1,1)) et 45% de chances de passer devant le rocher vers la droite (ie le vecteur (1,1)). Si le canoë est sur les colonnes à l'extrême gauche ou à droite, il se déplacera toujours vers le centre. S'il n'y a pas de roches, il se déplacera tout droit vers le haut.

        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

Ci-dessus: un itinéraire possible que le canoë pourrait emprunter, représenté à l'aide du caractère x

Étant donné la carte de la rivière, écrivez un programme qui affichera la probabilité que le canoë se termine à une colonne donnée.

Acceptez la saisie selon la méthode qui convient à votre programme (par exemple, STDIN, argument de ligne de commande raw_input(), lecture à partir d'un fichier, etc.). La première partie de l'entrée est un entier unique de 0 à 7, représentant la colonne pour laquelle le programme trouvera la probabilité. Ensuite, une liste de tuples sous la forme x,yreprésentant la position des pierres.

Un exemple:

Contribution:

4 4,1 5,5 3,5

Cela indiquerait une rivière avec des rochers aux positions (4,1), (5,5) et (3,5), et demande la probabilité que le canoë se termine à la 4e colonne.

Sortie:

0.495

Notez que dans cet exemple, les positions des roches étaient symétriques, permettant de résoudre le problème avec une distribution binomiale. Ce ne sera pas toujours le cas!

De plus, la rivière sera toujours traversable. Autrement dit, il n'y aura jamais deux roches placées côte à côte horizontalement. Voir le commentaire de Glenn pour un exemple d'un cas impossible.

C'est le golf de code, donc le plus petit nombre de personnages gagne. N'hésitez pas à poser des questions dans les commentaires si la spécification n'est pas claire.

GolfScript, 105 caractères

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

Une version GolfScript qui est devenue beaucoup plus longue que prévu - mais chaque tentative avec une approche différente était encore plus longue. L'entrée doit être donnée sur STDIN.

Exemple:

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

Code annoté:

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

Rubis, 204 191 172 caractères

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]

Il simule récursivement tous les résultats possibles tout en gardant une trace de la probabilité de chaque résultat individuel, puis il ajoute cette probabilité à un compteur cumulatif quand y == 15.

Astuces de fantaisie:

• c,*r=gets.split- l'opérateur "splat" ( *) prend tous les éléments restants de gets.splitet les colle dans le rtableau

• next {something} if {condition}: essentiellement équivalent à

  if {condition}
      {something}
      return
  end
  

  « Découvert » en évoluant if condition; something; return; endvers return something if conditionà break something if condition, puis je me suis dit que je voudrais essayer un « opérateur de boucle » plus courte pour voir si elle fonctionnerait (ce qu'elle a fait, bien sûr).

• Merci à @ MartinBüttner d'avoir suggéré d'utiliser des opérateurs ternaires chaînés (qui ont fini par devenir l'énorme troisième ligne du code golfé ci-dessus) et d'éliminer le point ci-dessus (qui a sauvé 19 (!) Caractères).

  J'ai cependant utilisé une astuce quelque peu sophistiquée: j'ai réalisé que s[foo],s[bar]cela ne fonctionne pas dans Ruby pour deux appels de méthode dans une seule instruction. Donc au début je l' ai changé (_=s[foo],s[bar])(une variable factice), mais je me suis aperçu que je pouvais ajouter et jeter les valeurs de retour: s[foo]+s[bar]. Cela ne fonctionne que parce que les appels à sne "renverront" jamais d'autres appels à sou un numéro ( o[x]+=p), donc je n'ai pas à me soucier de vérifier nil.

• Autres optimisations diverses: pau lieu de putspour imprimer les nombres, <1au lieu de ==0(puisque le canoë ne quitte jamais la rivière) et des comparaisons similaires ailleurs, [0]*8pour les probabilités initiales car les nombres de Ruby sont toujours "pass by value"

Non golfé:

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 octets

Programme C # complet attendant l'entrée de STDIN. Fonctionne en lisant les roches dans un tableau de tous les emplacements de la rivière, créant efficacement une carte, puis il effectue simplement 16 itérations de probabilités de déplacement autour d'un tableau décimal de 8 largeurs avant de produire le résultat.

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

Code formaté:

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 octets

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

Voici une version très non golfée avec quelques astuces qui ont été utilisées:

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)

La dernière astuce que j'ai utilisée était de noter que vous pouvez agir comme si les roches d'une même rangée étaient réellement séparées par une quantité infinitésimale. En d'autres termes, vous pouvez appliquer le transformateur de distribution de probabilité pour chaque roche de la même ligne de manière séquentielle et dans l'ordre que vous souhaitez, plutôt que de les appliquer tous simultanément. Cela ne fonctionne que parce que le problème interdit deux roches adjacentes horizontalement.

Ainsi, le programme transforme l'emplacement de chaque roche en un transformateur de distribution de probabilité, ordonné par la coordonnée y de la roche. Les transformateurs sont ensuite simplement enchaînés dans l'ordre et appliqués à la distribution de probabilité initiale. Et c'est ça!

Perl 169 octets

Lit à partir de 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{$&}

Assez simple, utilise implicitement les colonnes -1 et 8 pour lisser les cas de bordure. Les probabilités peuvent être propagées en toute sécurité à chaque niveau suivant car il n'y a pas de pierres adjacentes, donc une seule passe suffit.

PHP, 358

Utiliser le cerveau pour déterminer les chemins possibles et leurs probabilités est difficile et nécessiterait probablement plus de code que de simuler simplement 1 000 000 d'accidents de canoë. Oh l'humanité!

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

Exemple:

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

Golfé:

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

Cette version ne fait pas de jolie impression et affiche la probabilité de flottement de l'atterrissage du canoë à la position spécifiée.

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

PHP, 274

Je ne peux pas lire / écrire GolfScript pour me sauver la vie, mais en jetant un œil à la soumission de @ Howard, je me suis dirigé dans une meilleure direction que de simuler simplement 1 million d'accidents de canoë.

En commençant par un tableau de probabilités pour les positions de départ, nous pouvons simplement diviser ces nombres chaque fois qu'une pierre est rencontrée.

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

Exemple de sortie:

# 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

Golfé:

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

Exemple d'exécution:

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

Haskell, 237

J'espère juste que le canoë est livré avec ghc installé ...

L'astuce avec la liste infinie est volée à Matt Noonan, bravo à lui!

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

J'espère avoir bien compris la logique, mais l'exemple de Matt "5 4,4 1,5 5,3 3,6 2,9 4,12 3,13"donne 0.5613750000000001et l'exemple de OP "4 4,1 5,5 3,5"donne 0.49500000000000005, ce qui semble être correct à part quelques erreurs en virgule flottante.

Le voici en action:

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