Canoë en eau vive extrême

28

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.

Absinthe
la source
8
L'ironie est que le programme n'aide vraiment personne à survivre aux rapides. Il ne leur dire à quel point il est probable qu'ils survivront bien.
absinthe
1
Que se passe-t-il lorsque deux roches ou plus sont côte à côte d'affilée? Par exemple, si la carte est "0 1,0 1,1", le canot s'écraserait dans le rocher à 1,1. (a) la condition n'est pas autorisée, ou (b) la probabilité de terminer le cours est de 0.
Glenn Randers-Pehrson
1
Ah ok. Désolé, j'ai raté cette partie.
Poignée de porte
3
Réflexions finales: "Peut-être que la construction d'un canot programmable n'était pas la meilleure solution au problème de l'utilisation de pagaies explosives."
Kai
2
Je veux voir à quoi ça ressemble quand une pagaie explose.
Robbie Wxyz

Réponses:

4

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?*
Howard
la source
11

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]
Poignée de porte
la source
Ne serait-il pas encore plus court de rassembler tous ces éléments next X if Ydans des opérateurs ternaires imbriqués? Belle trouvaille cependant, vous voudrez peut-être l'ajouter aux conseils Ruby!
Martin Ender
@ MartinBüttner Oui, c'est en fait un énorme 19 caractères plus court! Merci, même si cela a l'effet secondaire malheureux d'une ligne ridiculement longue: P
Poignée de porte
5

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
    }
}
VisualMelon
la source
+1 pour utiliser l'opérateur "va à" ( for(;j-->0;)). Vous pouvez vous débarrasser de quelques caractères en remplaçant le dernier C.WriteLinepar C.Write. De plus, si vous utilisez floatau lieu de, decimalvous pouvez enregistrer quelques octets supplémentaires.
Christoph Böhmwalder
@HackerCow pratique standard;) a obtenu de tirer le meilleur parti de vos boucles for! J'utilise decimalparce que floatce ne sera pas précis, mais la décimale devrait suffire pour ces problèmes, mais pourrait probablement s'en tirer comme vous le dites. Je mettrai C.Writesi je parviens à jouer au golf plus loin car il est probablement plus proche de la spécification que C.WriteLineje ne pense pas que 4 octets justifient une modification pour ce programme de taille;)
VisualMelon
2

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!

Matt Noonan
la source
2

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.

Thaylon
la source
2

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
Sammitch
la source
Je pense que le format d'entrée ici est légèrement désactivé, par exemple river.php devrait donner 0,561375 sur "5 4,4 1,5 5,3 3,6 2,9 4,12 3,13"
Matt Noonan
@MattNoonan ce fut une journée difficile hier. Je devrais être en mesure de résoudre ce problème ...
Sammitch
2

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
Sammitch
la source
1

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
Flonk
la source