Considérons cette version ASCII d’un mécanisme similaire à une machine à haricots ou à un jeu plinko / pachinko :

    O

    ^
   \ ^
  ^ ^ \
 \ ^ / ^
U U U U U
1 2 3 4 5

Le Oest une balle qui tombe.

• Quand il frappe un ^, il y a 50% de chance qu'il aille à gauche ou à droite.
• Quand il frappe un /, il va toujours à gauche.
• Quand ça frappe un \, ça va toujours bien.

La balle finit par tomber dans l'un des Ucreux numérotés en bas. La question est de savoir quelle est la probabilité qu'il finisse dans chaque creux.

Pour ce cas particulier, les probabilités sont 0.0, 0.1875, 0.5625, 0.125, et 0.125, pour des creux de 1 à 5 respectivement.

Voici un autre exemple avec 3 creux au lieu de 5. Les probabilités sont 0.5, 0.5, et 0.0:

  O

  /
 ^ ^
U U U
1 2 3

Dans ce défi, nous allons généraliser ce problème à un mécanisme avec n'importe quel nombre de couches configurées de n'importe quelle manière.

Défi

Ecrivez un programme ou une fonction prenant en compte la représentation ASCII de la structure pyramidale du mécanisme. (Entrée via stdin / ligne de commande / argument de fonction.)

Vous pouvez soit supposer qu'il entre avec des espaces qui le mettent dans la forme appropriée, par exemple

   ^
  \ ^
 ^ ^ \
\ ^ / ^

Ou vous pouvez supposer qu'il entre sans espaces du tout, par exemple

^
\^
^^\
\^/^

(Si vous le souhaitez, vous pouvez supposer qu'il existe une nouvelle ligne de fuite et / ou un motif cohérent d'espaces de fin.)

La structure pyramidale en entrée peut avoir un nombre quelconque de niveaux (également appelés lignes), y compris zéro. Chaque niveau a une plus ^, /ou \que le dernier, et il y a des levels + 1creux sur le fond (qui ne font pas partie de l'entrée).

Votre programme / fonction doit imprimer / renvoyer la liste des probabilités que la balle atterrisse dans chacun des creux (dans l'ordre le plus à gauche). Celles-ci doivent être des valeurs à virgule flottante qui, une fois imprimées, comportent au moins 3 décimales (des zéros ou des points décimaux superflus ne sont pas obligatoires; 1convient très bien 1.000, .5convient parfaitement 0.500, etc.). Si vous avez écrit une fonction, vous pouvez imprimer les valeurs ou renvoyer une liste / tableau des flottants.

Tout format de liste imprimée raisonnable convient. par exemple 0.5 0.5 0.0, [0.5 0.5 0.0], [0.5, 0.5, 0.0], {0.5, 0.5, 0.0}ou 0.5\n0.5\n0.0tout serait bien.

Exemples

0 niveaux: (se résume à un trivial U)

Entrée: [no input/empty string given]
sortie:1.0

1 niveau:

Entrée: ^
sortie:0.5 0.5

Entrée: /
sortie:1.0 0.0

Entrée: \
sortie:0.0 1.0

2 niveaux: (deuxième exemple ci-dessus)

Contribution:

 /
^ ^

Sortie: 0.5 0.5 0.0

3 niveaux:

Contribution:

  ^
 ^ ^
^ ^ ^

Sortie: 0.125 0.375 0.375 0.125

Contribution:

  \
 / \
/ / \

Sortie: 0.0 0.0 0.0 1.0

4 niveaux: (premier exemple ci-dessus)

Contribution:

   ^
  \ ^
 ^ ^ \
\ ^ / ^

Sortie: 0.0 0.1875 0.5625 0.125 0.125

7 niveaux:

Contribution:

      ^
     / ^
    ^ ^ /
   / \ / \
  ^ ^ / ^ \
 ^ \ ^ \ / ^
\ ^ ^ ^ \ ^ /

Sortie: 0.0 0.09375 0.28125 0.4375 0.1875 0.0 0.0 0.0

Notation

La réponse la plus courte en octets l'emporte. Tiebreaker est post plus tôt.

CJam, 50 48 45 44 42 40 octets

1]q{iD%"(+0 0+( (\Y/::+ (d2/_a+"S/=~+}/p

Ceci s'attend à ce que l'entrée soit sans espace et ait un retour à la ligne final. Par exemple:

^
\^
^^\
\^/^

[0 0.1875 0.5625 0.125 0.125]

Algorithme

L'idée de base est que vous continuez à analyser chaque caractère (il n'y a que 4 caractères différents) et à effectuer différentes opérations sur la distribution de probabilité (initialement un tableau contenant 1 élément de valeur 1). Pour chaque ligne de caractères d'entrée (en commençant par le premier caractère de la première ligne), nous maintenons un tableau de probabilité de la même taille. Chaque caractère agit sur la première probabilité de la liste et pousse la paire résultante à la fin de la liste. Après chaque ligne, nous résumons les paires de la liste pour obtenir le nombre exact d'éléments comme les éléments de la ligne suivante.

Voici les quatre personnages et les actions requises correspondant à chacun:

• ^: Lorsque ce caractère apparaît, vous divisez la probabilité actuelle en deux parties. Par exemple, si nous avons ceci sur la première ligne, nous devons convertir le [1]en[0.5 0.5]
• /: Lorsque ces caractères apparaissent, nous devons mettre <current probability> 0en place la probabilité actuelle dans le tableau.
• \: Lorsque ces caractères apparaissent, nous devons mettre 0 <current probability>en place la probabilité actuelle dans le tableau.
• \n: Lorsque ce personnage apparaît, nous avons une nouvelle ligne. Nous regroupons ainsi toutes les paires de plus de 3 caractères et les additionnons pour obtenir la probabilité de chaque élément pour la ligne suivante. Par ex. [0 0.5 0.25 0.25]se convertit en [0 0.75 0.25]. Notez que les premier et dernier éléments ont une paire implicite (valeur 0) avant et après eux.

Il ne reste plus qu’à identifier le bon personnage et à effectuer la bonne action. Utilisons les calculs habituels pour le faire. Les codes ASCII pour ^, \, /et \nsont 94, 92, 47et 10. Après quelques essais, nous obtenons cette équation simple pour convertir ces nombres en 0, 1, 2 et 3:

"^\/
":ied13f%ed4f%ed

donne:

Stack: [[94 92 47 10]]
Stack: [[3 1 8 10]]
Stack: [[3 1 0 2]]
3102

Dans un tableau de longueur 4, le dernier 4f%serait implicite. Nous faisons donc simplement %13avec le code ASCII du personnage et choisissons la bonne action parmi un tableau d’actions.

Explication du code :

1]                                 e# Initial probability array with 1 probability
  q{                          }/   e# Read the whole input and iterate char by char
    iD%                            e# mod the ASCII code of the character with 13
"(+0 0+( (\Y/::+ (d2/_a+"S/        e# This is our actions array in order of [\ / \n ^]
                           =~      e# We pick the correct action and eval it
                             +     e# Evaling each action will leave one number out of the
                                   e# pairs out of the array. So we put it back in
                                p  e# Print the final probability array

Essayez-le en ligne ici

Ruby 140

->s{r=[1.0]
s.lines.map{|l|n=[i=0.0]*(r.size+1)
l.scan(/\S/).map{|e|a,b=e>?/?e>?]?[0.5]*2:[0,1]:[1,0]
z=r[i]
n[i]+=z*a
n[i+=1]+=z*b}
r=n}
r}

Fonction qui prend en entrée la chaîne (peut être joliment formatée en pyramide) et renvoie un tableau de flottants.

Testez-le en ligne: http://ideone.com/kmsZMe

Mise en œuvre assez simple. Ici c'est non-golfé:

F = -> input {
  probabilities = [1.0]

  input.lines.each { |line|

    new_probabilities = [0.0] * (probabilities.size+1)
    elements = line.scan /\S/
    elements.map.with_index{|el, i|
      deltas = el > '/' ? (el > ']' ? [0.5,0.5] : [0,1]) : [1,0]

      d1, d2 = deltas

      new_probabilities[i] += probabilities[i] * d1
      new_probabilities[i + 1] += probabilities[i] * d2
    }
    probabilities = new_probabilities
  }
  return probabilities
}

Ruby, 140 158 octets

Ne continuez pas à voter pour cela quand il y a une meilleure version ruby . Voici d'autres astuces pour vous.

Fonction sans nom avec un argument. Ne doit contenir aucun espace. Peut contenir ou non un saut de ligne.

->s{Z=(s.split'
')<<[]
K=[]
F=->i,j,f{k=Z[i][j]
K[i]||=0
k==?^?2.times{|m|F[i+1,j+m,f/2]}:!k ?K[j]+=f :F[i+1,j+(k==?/?0:1),f]}
F[0,0,1.0]
K}

Détruit 9 octets s'il doit être manipulé 0 levels(chaîne vide). Tous les cas de test fonctionnent correctement, voir ici chez ideone .

Pyth, 43 42 41 octets

umsdc+0sm@c[ZJhkJZKcJ2K)2x"\/"ekC,GH2.z]1

Ceci s'attend à ce que l'entrée soit sans espaces. Essayez-le en ligne: Compilateur / Exécuteur Pyth

Pyth, 40 octets (discutable)

umsdc+0sm,K@[ZJhkcJ2)x"\/"ek-JKC,GH2.z]1

Merci à @isaacg pour avoir sauvegardé un octet. Notez que cette version ne fonctionnait pas réellement dans la version de Pyth, lorsque la question a été posée. Il y avait un petit bug dans le compilateur. Malgré le fait que ce code n'utilise pas de nouvelles fonctionnalités de Pyth (uniquement des éléments conservés dans la documentation Pyth pendant longtemps et qui auraient dû fonctionner), il se peut que cette réponse ne soit pas valide. Décider vous-même.

Essayez-le en ligne: Compilateur / Exécuteur Pyth

Explication:

umsdc+0sm,K@[ZJhkcJ2)x"\/"ek-JKC,GH2.z]1   
u                                   .z]1  reduce G, starting with G = [1], for H in all_input():
                               C,GH         zip(G,H)
        m                                   map each pair k to:
            [ZJhkcJ2)                         create a list [0, k[0], k[0]/2]
                     x"\/"ek                  index of k[1] in "\/" (-1 for "^")
          K@                                  take the correspondent element of the list and store in K
         ,                  -JK               create a pair (K, k[0]-K)                                                      
     +0s                                    sum and insert 0 at the begin
    c                              2        chop into pairs
 msd                                        sum up each pair
                                            G gets updated with this new list

Par exemple, si j'ai actuellement les probabilités d'entrée G = [0.5, 0.5, 0.0]et la ligne, H = "^/^"voici ce qui se passe:

• Zip *: français ... [(0.5,"^"), (0.5,"/"), (0.0,"^")]
• créer des probabilités de sortie ... [[0.25,0.25], [0.5,0.0], [0.0, 0.0]]
• 0 + somme ... [0, 0.25, 0.25, 0.5, 0.0, 0.0, 0.0]
• hacher ... [0,0.25], [0.25,0.5], [0.0,0.0], [0.0]]
• somme ... [0.25, 0.75, 0.0, 0.0]

C #, 274 247 octets

Rien de spécial, programme complet qui lit les lignes (avec ou sans espaces, il les supprime) de STDIN, et imprime les résultats séparés par des espaces dans STDOUT.

using Q=System.Console;class P{static void Main(){decimal[]k={1},t;string L;for(int l=0,i;(L=Q.ReadLine())!=null;k=t)for(L=L.Replace(" ",""),t=new decimal[++l+1],i=0;i<l;)t[i]+=k[i]-(t[i+1]=(8-L[i]%8)/2*k[i++]/2);Q.WriteLine(string.Join(" ",k));}}

Code plus propre avec des commentaires:

using Q=System.Console;

class P
{
    // / 47
    // \ 92
    // ^ 94

    static void Main()
    {
        decimal[]k={1},t; // k is old array, t is new array

        string L; // L is the current line, R is the current result (1 if no rows)
        for(int l=0,i; // l is length of old array, i is index in old array
            (L=Q.ReadLine())!=null; // for each line of input
            k=t) // swap array over
            for(L=L.Replace(" ",""), // remove spaces
                t=new decimal[++l+1], // create a new array
                i=0;

                i<l;) // for each position

                t[i]+=k[i]-( // add to left position (for last time)
                        t[i+1]=(8-L[i]%8)/2*k[i++]/2 // assign right position (k is decimal)
                    );

        Q.WriteLine(string.Join(" ",k)); // print result
    }
}

Python 3, 113

P=[1]
for C in input().split():
 l,*Q=0,
 for p,c in zip(P,C):r=p*"\^/".find(c)/2;Q+=l+r,;l=p-r
 P=Q+[l]
print(P)

Met régulièrement à jour le vecteur de probabilité Pen réponse à chaque ligne. Ce nouveau vecteur de probabilité Qest créé une entrée à la fois. Parcourt les nouveaux créneaux horaires et calcule la contribution de l’ancrage à sa droite r, tout en calculant la contribution restante au créneau suivant p-r.

Attend que chaque ligne se termine par au moins un espace pour éviter un problème où les lignes se terminent par une barre oblique inverse.

Python 3, 138 octets

def f(s):
 r=[1];p=t=0
 for e in s:
  if'!'<e:b=p==t*-~t/2;r+=[0]*b;t+=b;v=ord(e)%7+1;a=r[p]/2;r[-1]+=v//3*a;r+=v%3*a,;p+=1
 return r[~t:]

Fonctionne avec tous les espaces blancs car ils sont tous filtrés (par if'!'<e).

Méthode:

• Nous gardons une liste rde plus en plus longue des probabilités d'atteindre tous les obstacles et des creux implicites en dessous d'eux. Nous partons de la liste [1].
• Si nous sommes au premier obstacle d'affilée, nous devons ajouter un supplément 0à la liste pour le creux du leader. Nous décidons s'il s'agit du premier obstacle en comparant son index pau prochain nombre triangulaire t*-~t/2.
• Pour chaque obstacle, nous ajoutons sa valeur de liste partiellement au dernier élément et partiellement à un nouvel élément de fin. Nous divisons la valeur de liste en fonction du caractère d'obstacle ( ^:0.5 0.5; /:1 0; \:0 1). Nous utilisons la méthode suivante:
  • Prendre v = ord(char) mod 7 + 1céder^:4 /:6 \:2
  • v div 3 / 2donne la première fraction ( ^:0.5 /:1 \:0)
  • v mod 3 / 2donne la seconde fraction ( ^:0.5 /:0 \:1)
• Le résultat est le dernier t + 1élément de la liste finale r.

2 octets grâce au conseil de chat de @ Sp3000.

Perl, 78

#!perl -p0a
@r=($/=1);$^=.5;@r=map$r-$l+($l=$$_*($r=shift@r)),/./g,$r=$l=0for@F;$_="@r"

Prend des entrées sans espaces.

Essayez - moi .

TI-BASIC, 73 76

Prend une ligne à la fois et se termine lorsqu'un espace est entré seul, car ni les sauts de ligne dans les chaînes ni les chaînes vides ne sont légaux dans TI-BASIC.

{1→X
Input Str1
While Str1≠"  //one space
.5seq(inString("^/",sub(Str1,I,1)),I,1,dim(Ans
augment(Ans∟X,{0})+augment({0},∟X-∟XAns→X
Input Str1
End
∟X

Je suis presque sûr d'avoir la bonne taille (TI-BASIC est segmenté, chaque commande prend donc un ou deux octets: seq () en prend un, inString () en prend deux, dim () en prend un, etc.). compté la taille manuellement.)

Bien que la barre oblique inverse soit valide dans une chaîne, notez qu’il n’ya aucun moyen de la saisir depuis l’intérieur du programme si vous n’avez pas modifié votre calculatrice.

Javascript - 117

J'ai essayé d'utiliser la récursivité, mais c'était trop long ...

Pointe du chapeau à xnor pour l'idée de soustraction, qui a rasé une douzaine de personnages ou plus.

w=s=>{a=[1];s.split('\n').map(m=>{for(b=[i=0];z=a[i],f=m[i];b[i++]+=z-b[i])b[i+1]=f>']'?z/2:f<':'?0:z;a=b})
return a}

Ungolfed:

// s must not have spaces
w=s=>{
  // a is the current probability array
  a=[1];
  s.split('\n').map(
    // for each row of input...
    m=>{
      b=[0];  // b is the next row's probability array
      for(i=0; i<m.length;){
        z=a[i]; // z = probability
        f=m[i]; // f = letter
                                  // let's assume i == 0
        b[i+1] = (f>']') ? z/2 :  // if f == '^', b[1] = z/2
          (f<':' ? 0 :            // else if f == '/', b[1] = 0 
            z);                   // else b[1] = z
        b[i++]+=z-b[i];           // then add (z-b[1]) to b[0]
      }
      a=z-b    // increment current probability array
    }
  )
  return a;
}