Pas votre routine Bean Machine

42

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.

Les passe-temps de Calvin
la source
16
Quinconces avait mieux répondre.
Hobbies de Calvin
"un certain motif cohérent d'espaces de fuite" - puis-je supposer que les espaces de fuite sur la ligne Nth codent la probabilité pour que la balle atterrisse dans le seau Nth?
Random832
4
@ Random832 Non. (Pensez-vous vraiment que ça volerait?)
Calvin's Hobbies
Il y a une raison pour laquelle je l'ai posté comme un commentaire plutôt que comme une réponse. Je pensais simplement que le casse-tête de cette énigme était intéressant: la plupart de celles que j'ai vues dictent de manière plus stricte le format de l'entrée et / ou de la sortie.
Random832
@ Random832: L'entrée et la sortie sont très claires. Les failles standard (telles que l'encodage de la réponse dans l'entrée) n'ont pas besoin d'être traitées à chaque défi.
Alex A.

Réponses:

10

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

Optimiseur
la source
1
Comment testez-vous avec 0 lignes?
Trichoplax
1
@trichoplax devrait fonctionner maintenant.
Optimiseur
Cela fonctionne maintenant avec une entrée vide :)
trichoplax
15

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
}
Cristian Lupascu
la source
13

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 .

blutorange
la source
4
Ce n’est pas parce qu’il ya une "meilleure" réponse Ruby que la vôtre (ou toute autre réponse Ruby) ne vaut pas la peine de voter. :)
Alex A.
J'ai moi-même voté cela parce qu'il contient quelques astuces intéressantes. J'aime votre multiligne split, par exemple.
Cristian Lupascu
12

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]
Jakube
la source
3
J'essayais de jouer au golf, et cela m'a amené à un bug dans le compilateur. Le golf fonctionne, maintenant que j'ai corrigé le bogue. La solution consiste à remplacer la liste des listes à 2 valeurs par une liste, puis à générer l'autre valeur en soustrayant la première valeur hk. ,K@[ZJhkcJ2)x"\/"ek-JK
Isaac
1
Ceci est vraiment une ligne fine quand vous corrigez un bogue n'est pas compté comme une version plus récente du langage (et est donc toujours valable pour les questions posées avant le correctif)
Optimiseur
1
@ Optimiseur Votre droit. Ajout de quelques notes à la réponse, qui explique les circonstances.
Jakube
2
@Optimizer Dans ce cas, il semble judicieux de déterminer s'il s'agit vraiment d'une version plus récente du langage ou d'une version plus récente de l' implémentation du langage qui corrige un bogue, rapprochant ainsi l'implémentation de la spécification.
Desty
@Desty C'est pourquoi j'ai mentionné que c'est une ligne fine;)
Optimizer
8

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
    }
}
VisualMelon
la source
7

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.

Xnor
la source
L'entrée aura plusieurs lignes, donc je ne pense pas qu'un seul input()puisse gérer cela.
randomra
un retour à la ligne n'est pas nécessaire pour chaque ligne de l'entrée.
Brian Minton
@randomra J'ai écrit ceci en mode veille et cela a bien fonctionné en insérant des entrées multilignes à l'invite du shell.
xnor
6

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.

randomra
la source
4

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 .

nutki
la source
1

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.

lirtosiast
la source
0

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;
}
Pas que Charles
la source