Considere esta versão ASCII de um mecanismo semelhante a uma máquina de feijão ou a um jogo plinko / pachinko :

    O

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

A Oé uma bola que cai.

• Quando atinge um ^, há uma chance de 50 a 50 de ir para a esquerda ou direita.
• Quando atinge a /, sempre sai para a esquerda.
• Quando atinge a \, sempre dá certo.

A bola eventualmente cai em uma das Uvalas numeradas na parte inferior. A questão é: qual é a probabilidade de acabar em cada vale?

Para este caso particular, as probabilidades são 0.0, 0.1875, 0.5625, 0.125, e 0.125, por calhas de 1 até 5 respectivamente.

Aqui está outro exemplo com 3 calhas em vez de 5. As probabilidades são 0.5, 0.5, e 0.0:

  O

  /
 ^ ^
U U U
1 2 3

Neste desafio, generalizaremos esse problema para um mecanismo com qualquer número de camadas configuradas de qualquer maneira.

Desafio

Escreva um programa ou função que absorva a representação ASCII da estrutura em pirâmide do mecanismo. (Entrada via stdin / linha de comando / função arg.)

Você pode assumir que ele vem com espaços que o colocam na forma correta, por exemplo,

   ^
  \ ^
 ^ ^ \
\ ^ / ^

Ou você pode assumir que ele não possui espaços, por exemplo,

^
\^
^^\
\^/^

(Se desejar, você pode assumir que há uma nova linha à direita e / ou algum padrão consistente de espaços à direita).

A estrutura da pirâmide de entrada pode ter qualquer número de níveis (também conhecido como linhas), incluindo zero. Cada nível tem mais um ^, /ou \que a última, e há levels + 1depressões na parte inferior (que não são parte da entrada).

Você programa / função deve imprimir / retornar a lista de probabilidades de que a bola caia em cada uma das valas (na ordem da esquerda para a direita). Devem ser valores de ponto flutuante que, quando impressos, têm pelo menos três casas decimais (zeros supérfluos ou pontos decimais não são necessários; 1é bom para 1.000, .5é bom para 0.500etc.). Se você escreveu uma função, pode imprimir os valores ou retornar uma lista / matriz dos carros alegóricos.

Qualquer formato razoável de lista impressa é bom. por exemplo 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.0tudo seria bem.

Exemplos

0 Níveis: (resume-se a um trivial U)

Entrada: [no input/empty string given]
Saída:1.0

1 Nível:

Entrada: ^
Saída:0.5 0.5

Entrada: /
Saída:1.0 0.0

Entrada: \
Saída:0.0 1.0

2 níveis: (segundo exemplo acima)

Entrada:

 /
^ ^

Saída: 0.5 0.5 0.0

3 Níveis:

Entrada:

  ^
 ^ ^
^ ^ ^

Saída: 0.125 0.375 0.375 0.125

Entrada:

  \
 / \
/ / \

Saída: 0.0 0.0 0.0 1.0

4 níveis: (primeiro exemplo acima)

Entrada:

   ^
  \ ^
 ^ ^ \
\ ^ / ^

Saída: 0.0 0.1875 0.5625 0.125 0.125

7 níveis:

Entrada:

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

Saída: 0.0 0.09375 0.28125 0.4375 0.1875 0.0 0.0 0.0

Pontuação

A resposta mais curta em bytes vence. O desempatador é uma publicação anterior.

CJam, 50 48 45 44 42 40 bytes

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

Isso espera que a entrada fique sem espaço e tenha uma nova linha à direita. Por exemplo:

^
\^
^^\
\^/^

[0 0,1875 0,5625 0,125 0,125]

Algoritmo

A idéia básica é que você continue analisando cada caractere (existem apenas 4 caracteres diferentes) e execute operações diferentes na distribuição de probabilidade (inicialmente uma matriz contendo 1 elemento do valor 1). Para cada linha de caracteres de entrada (começando com o primeiro caractere na primeira linha), mantemos uma matriz de probabilidade do mesmo tamanho. Cada caractere age com a primeira probabilidade da lista e empurra o par resultante para o final da lista. Após cada linha, somamos pares da lista para obter o número exato de itens como os itens da próxima linha.

Aqui estão os quatro caracteres e as ações necessárias correspondentes a cada um:

• ^: Quando esse caractere ocorre, você divide a probabilidade atual em duas partes. Por exemplo, se temos isso na primeira linha, temos que converter o [1]para[0.5 0.5]
• /: Quando esses caracteres ocorrem, precisamos colocar <current probability> 0a probabilidade atual no array.
• \: Quando esses caracteres ocorrem, precisamos colocar 0 <current probability>a probabilidade atual no array.
• \n: Quando esse personagem ocorre, temos uma nova linha. Assim, agrupamos todos os pares acima de 3 caracteres e os somamos para obter a probabilidade de cada item para a próxima linha. Por ex. [0 0.5 0.25 0.25]é convertido em [0 0.75 0.25]. Observe que o primeiro e o último item têm um par implícito (com valor 0) antes e depois deles.

Agora só precisamos identificar o personagem certo e executar a ação correta. Vamos usar a matemática usual aqui para fazer isso. Os códigos ASCII para ^, \, /e \nsão 94, 92, 47, e 10. Após algumas tentativas, obtemos esta equação simples para converter esses números em 0, 1, 2 e 3:

"^\/
":ied13f%ed4f%ed

dá:

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

Em uma matriz de comprimento 4, o último 4f%seria implícito. Então, simplesmente fazemos %13o código ASCII do personagem e escolhemos a ação correta em uma matriz de ações.

Explicação do código :

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

Experimente online aqui

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}

Função que recebe como entrada a string (pode ser bem formatada como uma pirâmide) e retorna uma matriz de flutuadores.

Teste on-line: http://ideone.com/kmsZMe

Implementação bastante direta. Aqui está não destruído:

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 bytes

Não continue votando isso quando houver uma versão ruby ​​melhor . Aqui estão mais truques para você.

Função sem nome com um argumento. Não deve conter espaços. Pode ou não conter uma nova linha à direita.

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

Desperdiça 9 bytes por ter que lidar 0 levels(string vazia). Todos os casos de teste funcionam corretamente, veja aqui em ideone .

Pitão, 43 42 41 bytes

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

Isso espera que a entrada fique sem espaços. Experimente on-line: Compilador / Executor Pyth

Pitão, 40 bytes (questionável)

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

Obrigado a @isaacg, por salvar um byte. Observe que essa versão não funcionou na versão do Pyth, quando a pergunta foi feita. Houve um pequeno erro no compilador. Apesar desse código não usar novos recursos do Pyth (apenas coisas que estavam nos documentos do Pyth por um longo tempo e deveriam ter funcionado), isso pode não ser uma resposta válida. Decida por si mesmo.

Experimente on-line: Compilador / Executor Pyth

Explicação:

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

Por exemplo, se atualmente tenho as probabilidades de entrada G = [0.5, 0.5, 0.0]e a linha H = "^/^"acontece o seguinte:

• fecho eclair ... [(0.5,"^"), (0.5,"/"), (0.0,"^")]
• criar probabilidades de saída ... [[0.25,0.25], [0.5,0.0], [0.0, 0.0]]
• 0 + soma ... [0, 0.25, 0.25, 0.5, 0.0, 0.0, 0.0]
• pique ... [0,0.25], [0.25,0.5], [0.0,0.0], [0.0]]
• soma ... [0.25, 0.75, 0.0, 0.0]

C #, 274 247 bytes

Nada sofisticado, programa completo que lê linhas (com ou sem espaços, apenas as retira) do STDIN e imprime resultados separados por espaço no 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));}}

Código mais ordenado com comentários:

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)

Atualiza repetidamente o vetor de probabilidade Pem resposta a cada linha. Esse novo vetor de probabilidade Qé criado uma entrada por vez. Percorre os novos slots, e calcula a contribuição do peg para o seu direito como r, ao mesmo tempo, o cálculo da contribuição restante para o próximo slot, como p-r.

Espera que cada linha termine em pelo menos um espaço para evitar um problema em que as linhas terminam em uma barra invertida.

Python 3, 138 bytes

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:]

Funciona com todos os espaços em branco, pois todos são filtrados (por if'!'<e).

Método:

• Mantemos uma lista cada vez maior rdas probabilidades de alcançar qualquer obstáculo e as valas implícitas abaixo deles. Começamos a partir da lista [1].
• Se estivermos no primeiro obstáculo consecutivo, precisamos adicionar um extra 0à lista da calha principal. Decidimos se é o primeiro obstáculo comparando seu índice pcom o próximo número triangular t*-~t/2.
• Para cada obstáculo, adicionamos seu valor de lista parcialmente ao último elemento e parcialmente a um novo elemento final. Dividimos o valor da lista com base no caractere do obstáculo ( ^:0.5 0.5; /:1 0; \:0 1). Usamos o seguinte método:
  • Tome v = ord(char) mod 7 + 1rendimento^:4 /:6 \:2
  • v div 3 / 2produz a primeira fração ( ^:0.5 /:1 \:0)
  • v mod 3 / 2produz a segunda fração ( ^:0.5 /:0 \:1)
• O resultado são os últimos t + 1elementos da lista final r.

2 bytes graças ao conselho do @ Sp3000.

Perl, 78

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

Recebe entrada sem espaços.

Experimente- me .

TI-BASIC, 73 76

Recebe uma linha de cada vez e termina quando um espaço é inserido por conta própria, porque nem quebras de linha nem vazias são válidas no 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

Tenho certeza de que consegui o tamanho certo (TI-BASIC é tokenizado, portanto, cada comando leva um ou dois bytes - seq () leva um, inString () leva dois, dim () leva um e assim por diante. contado o tamanho manualmente.)

Embora o caractere de barra invertida seja válido em uma string, observe que não há como inserir um de dentro do programa, a menos que você tenha modificado sua calculadora.

Javascript - 117

Tentei usar recursão, mas isso foi muito longo ...

Dica para xnor para a idéia de subtração, que raspou uma dúzia ou mais de caracteres.

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