Rozważ tę wersję ASCII mechanizmu podobnego do maszyny do fasoli lub gry Plinko / Pachinko :

    O

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

OJest piłka, która spada w dół.

• Kiedy trafi w ^, istnieje 50-50 szans, że pójdzie w lewo lub w prawo.
• Kiedy uderza w /, zawsze idzie w lewo.
• Kiedy uderza w \, zawsze idzie dobrze.

Piłka ostatecznie wpada do jednej z ponumerowanych Ukorytek na dole. Pytanie brzmi: jakie jest prawdopodobieństwo, że skończy w każdej niecce?

W tym konkretnym przypadku, to prawdopodobieństwo 0.0, 0.1875, 0.5625, 0.125i 0.125, dla korytek 1 do 5 odpowiednio.

Oto kolejny przykład z 3 niecek zamiast 5. są szanse 0.5, 0.5oraz 0.0:

  O

  /
 ^ ^
U U U
1 2 3

W tym wyzwaniu uogólnimy ten problem na mechanizm z dowolną liczbą warstw skonfigurowanych w dowolny sposób.

Wyzwanie

Napisz program lub funkcję, która przyjmuje reprezentację ASCII struktury piramidy mechanizmu. (Wprowadzane przez stdin / wiersz poleceń / funkcję arg.)

Możesz albo założyć, że wchodzi ze spacjami, które nadają mu odpowiedni kształt, np

   ^
  \ ^
 ^ ^ \
\ ^ / ^

Możesz też założyć, że wchodzi bez spacji, np

^
\^
^^\
\^/^

(W razie potrzeby możesz założyć, że istnieje nowa linia i / lub jakiś spójny wzór spacji końcowych).

Struktura piramidy wejściowej może mieć dowolną liczbę poziomów (czyli linii), w tym zero. Każdy poziom zawiera jeden ^, /lub \od poprzedniego, a są levels + 1niecki na dnie (nie będące częścią wejściu).

Twój program / funkcja musi wydrukować / zwrócić listę prawdopodobieństw, że kula wyląduje w każdej z koryt (w kolejności od lewej do lewej do lewej). Powinny to być wartości zmiennoprzecinkowe, które po wydrukowaniu mają co najmniej 3 miejsca po przecinku (zbędne zera lub kropki po przecinku nie są wymagane; 1jest w porządku dla 1.000, .5jest w porządku 0.500itp.). Jeśli napisałeś funkcję, możesz wydrukować wartości lub zwrócić listę / tablicę liczb zmiennoprzecinkowych.

Każdy rozsądny format listy drukowanej jest w porządku. np 0.5 0.5 0.0, [0.5 0.5 0.0], [0.5, 0.5, 0.0], {0.5, 0.5, 0.0}, lub 0.5\n0.5\n0.0będzie wszystko w porządku.

Przykłady

0 poziomów: (sprowadza się do jednego trywialnego U)

Wejście: [no input/empty string given]
Wyjście:1.0

1 poziom:

Wejście: ^
Wyjście:0.5 0.5

Wejście: /
Wyjście:1.0 0.0

Wejście: \
Wyjście:0.0 1.0

2 poziomy: (drugi przykład powyżej)

Wejście:

 /
^ ^

Wynik: 0.5 0.5 0.0

3 poziomy:

Wejście:

  ^
 ^ ^
^ ^ ^

Wynik: 0.125 0.375 0.375 0.125

Wejście:

  \
 / \
/ / \

Wynik: 0.0 0.0 0.0 1.0

4 poziomy: (pierwszy przykład powyżej)

Wejście:

   ^
  \ ^
 ^ ^ \
\ ^ / ^

Wynik: 0.0 0.1875 0.5625 0.125 0.125

7 poziomów:

Wejście:

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

Wynik: 0.0 0.09375 0.28125 0.4375 0.1875 0.0 0.0 0.0

Punktacja

Najkrótsza odpowiedź w bajtach wygrywa. Tiebreaker jest wcześniejszym postem.

CJam, 50 48 45 44 42 40 bajtów

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

Oczekuje to, że dane wejściowe będą pozbawione spacji i będą miały końcowy znak nowej linii. Na przykład:

^
\^
^^\
\^/^

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

Algorytm

Podstawową ideą jest to, że nadal analizujesz każdy znak (są tylko 4 różne znaki) i wykonujesz różne operacje na rozkładzie prawdopodobieństwa (początkowo tablica zawierająca 1 element o wartości 1). Dla każdego wiersza znaków wejściowych (zaczynając od pierwszego znaku w pierwszym rzędzie) utrzymujemy tablicę prawdopodobieństwa o tym samym rozmiarze. Każda postać działa na podstawie pierwszego prawdopodobieństwa z listy i przesuwa wynikową parę na koniec listy. Po każdej linii sumujemy pary z listy, aby uzyskać dokładną liczbę pozycji jako pozycji w następnym wierszu.

Oto cztery znaki i wymagane czynności odpowiadające każdej z nich:

• ^: Kiedy ta postać występuje, dzielisz obecne prawdopodobieństwo na dwie części. Na przykład, jeśli mamy to w pierwszym wierszu, musimy przekonwertować [1]na[0.5 0.5]
• /: Kiedy wystąpią te znaki, musimy umieścić <current probability> 0w tablicy aktualne prawdopodobieństwo.
• \: Kiedy wystąpią te znaki, musimy umieścić 0 <current probability>w tablicy aktualne prawdopodobieństwo.
• \n: Kiedy pojawia się ten znak, mamy nową linię. W ten sposób grupujemy wszystkie pary powyżej 3 znaków i sumujemy je, aby uzyskać prawdopodobieństwo każdego elementu w następnym wierszu. Np. [0 0.5 0.25 0.25]zostaje przekonwertowany na [0 0.75 0.25]. Zauważ, że pierwszy i ostatni element mają ukrytą parę (o wartości 0) przed nimi i po nich.

Teraz musimy tylko zidentyfikować odpowiednią postać i wykonać właściwą akcję. Wykorzystajmy tutaj zwykłe matematyki. Kody ASCII ^, \, /i \nsą 94, 92, 47, i 10. Po kilku próbach otrzymujemy to proste równanie, aby przekonwertować te liczby na 0, 1, 2 i 3:

"^\/
":ied13f%ed4f%ed

daje:

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

W tablicy o długości 4 ostatnia 4f%byłaby domyślna. Więc po prostu wykonujemy %13kod ASCII znaku i wybieramy odpowiednią akcję z szeregu akcji.

Objaśnienie kodu :

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

Wypróbuj online tutaj

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}

Funkcja, która przyjmuje jako dane wejściowe ciąg znaków (może być ładnie sformatowany jako piramida) i zwraca tablicę liczb zmiennoprzecinkowych.

Przetestuj online: http://ideone.com/kmsZMe

Dość prosta implementacja. Tutaj nie jest golfem:

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
}

Rubinowy, 140 158 bajtów

Nie kontynuuj głosowania, gdy jest lepsza wersja ruby . Oto więcej sztuczek dla Ciebie.

Funkcja bez nazwy z jednym argumentem. Nie może zawierać spacji. Może lub nie może zawierać końcowy znak nowej linii.

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

Marnuje 9 bajtów na konieczność obsługi 0 levels(pusty ciąg). Wszystkie przypadki testowe działają poprawnie, patrz tutaj w ideone .

Pyth, 43 42 41 bajtów

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

Oczekuje się, że wejście będzie bez spacji. Wypróbuj online: Pyth Compiler / Executor

Pyth, 40 bajtów (wątpliwy)

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

Dzięki @isaacg za zaoszczędzenie jednego bajtu. Zauważ, że ta wersja tak naprawdę nie działała w wersji Pyth, kiedy zadano pytanie. W kompilatorze był mały błąd. Pomimo tego, że ten kod nie używa żadnych nowych funkcji Pyth (tylko rzeczy, które były w dokumentach Pyth przez długi czas i powinny powinny działać), może to nie być poprawna odpowiedź. Zdecyduj sam.

Wypróbuj online: Pyth Compiler / Executor

Wyjaśnienie:

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

Na przykład, jeśli obecnie mam prawdopodobieństwa wejściowe G = [0.5, 0.5, 0.0]i wiersz H = "^/^"dzieje się tak:

• zamek błyskawiczny ... [(0.5,"^"), (0.5,"/"), (0.0,"^")]
• tworzyć prawdopodobieństwa wyjściowe ... [[0.25,0.25], [0.5,0.0], [0.0, 0.0]]
• 0 + suma ... [0, 0.25, 0.25, 0.5, 0.0, 0.0, 0.0]
• siekać ... [0,0.25], [0.25,0.5], [0.0,0.0], [0.0]]
• suma ... [0.25, 0.75, 0.0, 0.0]

C #, 274 247 bajtów

Nic szczególnego, kompletny program, który odczytuje wiersze (ze spacjami lub bez, po prostu je rozdziela) ze STDIN i drukuje wyniki rozdzielone spacjami do 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));}}

Kod Tidier z komentarzami:

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)

Wielokrotnie aktualizuje wektor prawdopodobieństwa Pw odpowiedzi na każdą linię. Ten nowy wektor prawdopodobieństwa Qjest tworzony pojedynczo. Iteruje przez nowe gniazda i oblicza wkładkę z kołka po prawej stronie as r, a także oblicza pozostałą część do nadchodzącego gniazda jako p-r.

Oczekuje, że każda linia zakończy się co najmniej jedną spacją, aby uniknąć problemu, w którym linie kończą się odwrotnym ukośnikiem.

Python 3, 138 bajtów

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

Działa z dowolnymi białymi spacjami, ponieważ wszystkie są odfiltrowywane (według if'!'<e).

Metoda:

• Prowadzimy stale rosnącą listę rprawdopodobieństw dotarcia do przeszkód i ukrytych dolin poniżej nich. Zaczynamy od listy [1].
• Jeśli znajdujemy się na pierwszej przeszkodzie z rzędu, musimy dodać dodatkowy 0do listy dla wiodącej rynny. Decydujemy, czy jest to pierwsza przeszkoda, porównując jej indeks pz kolejną liczbą trójkątną t*-~t/2.
• Dla każdej przeszkody dodajemy jej wartość listy częściowo do ostatniego elementu, a częściowo do nowego elementu końcowego. Dzielimy wartość listy na podstawie znaku przeszkody ( ^:0.5 0.5; /:1 0; \:0 1). Używamy następującej metody:
  • Weź v = ord(char) mod 7 + 1plonowanie^:4 /:6 \:2
  • v div 3 / 2daje pierwszą frakcję ( ^:0.5 /:1 \:0)
  • v mod 3 / 2daje drugą frakcję ( ^:0.5 /:0 \:1)
• Wynik jest ostatnim t + 1elementem końcowej listy r.

2 bajty dzięki poradom na czacie @ Sp3000.

Perl, 78

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

Pobiera dane wejściowe bez spacji.

Spróbuj mnie .

TI-BASIC, 73 76

Pobiera dane wejściowe po jednym wierszu i kończy się, gdy spacja jest wprowadzana samodzielnie, ponieważ ani łamanie wierszy w łańcuchach, ani puste ciągi znaków nie są dozwolone w 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

Jestem prawie pewien, że mam odpowiedni rozmiar (TI-BASIC jest tokenizowany, więc każde polecenie zajmuje jeden lub dwa bajty - seq () zajmuje jeden, inString () zajmuje dwa, dim () bierze jeden itd. I ręcznie policzyłem rozmiar.)

Chociaż znak odwrotnego ukośnika jest prawidłowy w ciągu, pamiętaj, że nie można wprowadzić go z poziomu programu, chyba że zmodyfikowałeś kalkulator.

JavaScript - 117

Próbowałem użyć rekurencji, ale to było za długo ...

Czapka dla Xnora za pomysł odejmowania, który ogolił kilkanaście lub więcej postaci.

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}

Nie golfowany:

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