Tirare i dadi

Qualche giorno fa su un (poco) noto social, il buon Zar poneva una questione apparentemente semplice.

“Ci sono cinque dadi a sei facce recanti (le facce) i seguenti numeri: 0, 0, 1, 2, 3, 4. Si lanciano tutti insieme e si fa la somma dei valori ottenuti. Problema: calcolare le probabilità di uscita dei numeri da 0 a 20.”

Nel post linkato Zar fa la trattazione matematica, e vi consiglio di leggerlo tutto perché merita. Nel “socialino dell’ammmore” abbiamo anche discusso alcune soluzioni al problema tramite programmini in vari linguaggi di programmazione. Io, che nel frattempo mi sono parecchio arrugginito con Haskell, ne ho approfittato per proporre 2 soluzioni con questo elegante linguaggio di programmazione: la prima semplice semplice, la seconda una generalizzazione della prima. Dato che le soluzioni le avevo messe su pastebin e chissà che fine faranno, adesso le riposto qui, così magari viene voglia anche a voi di provare nel vostro linguaggio di programmazione preferito.

Cominciamo con la prima:

module Main where
import System.Environment

main :: IO ()
main = do args <- getArgs          
          putStrLn("Probabilità di " ++
                   (args !! 0) ++ " con 5 dadi : " ++ " = " ++ 
                   show( prob_dadi (read (args!!0)::Integer) 5 ))
          -- putStrLn("Test : " ++ show(test))


prob_faccia :: Integer -> Rational               
prob_faccia 0 = 2/6
prob_faccia 1 = 1/6
prob_faccia 2 = 1/6
prob_faccia 3 = 1/6
prob_faccia 4 = 1/6
prob_faccia n = 0
                
prob_dadi :: Integer -> Integer -> Rational
             
prob_dadi n 0 | n == 0   = 1
              | n > 0    = 0
              | n < 0    = 0
                           
prob_dadi n nd  =  (prob_faccia 0)  *  (prob_dadi n (nd-1)) + 
                   (prob_faccia 1)  *  (prob_dadi (n-1) (nd-1)) +
                   (prob_faccia 2)  *  (prob_dadi (n-2) (nd-1)) +  
                   (prob_faccia 3)  *  (prob_dadi (n-3) (nd-1)) +
                   (prob_faccia 4)  *  (prob_dadi (n-4) (nd-1))


test = (test_loop 20)

test_loop (-1) = 0
test_loop n = (prob_dadi n 5) + test_loop (n-1)

Il programmino prende sulla linea di comando il numero di cui si vuole calcolare la probabilità (tra 5 e 20 ovviamente) e restituisce la probabilità in forma di frazione. La funzione principale è prob_dadi che naturalmente è ricorsiva. Il primo parametro n è il numero di cui si vuole calcolare la probabilità, il secondo è il numero di dadi da lanciare.

Per ottenere n, si lancia un dado e:
– si calcola la probabilità che venga 1, e si moltiplica per la probabilità che i restanti nd-1 dadi ottengano n-1;
– si calcola la probabilità che venga 2, e si moltiplica per la probabilità che i restanti nd-1 dadi ottengano il numero n-2
– ecc.
Tutte queste probabilità si sommano per ottenere la probabilità finale.
Resta da stabilire la fine della ricorsione: la probabilità di ottenere n > 0 con 0 dadi, è sempre 0; la probabilità di ottenere n == 0 con 0 dadi è pari a 1.

E’ chiaro? Spero di si. Se avete capito questo programmino, potrete agevolmente capire il secondo programmino che generalizza il contenuto delle facce mettendolo in una lista.
Ecco il codice (ATTENZIONE: per mia praticità, e per confondervi un po’ le idee, qui ho scambiato l’ordine dei parametri della prob_dadi! adesso prende prima il numero dei dadi e poi il numero da ottenere):

module Main where
import System.Environment

main :: IO ()
main = do args <- getArgs          
          putStrLn("Probabilità di " ++
                   (args !! 0) ++ " con 5 dadi : " ++ " = " ++ 
                   show( prob_dadi 5 (read (args!!0)::Integer)))
          -- putStrLn("Test : " ++ show(test))

facce :: [Integer]
facce = [0, 0, 1, 2, 3, 4]

prob_faccia :: Rational
prob_faccia = 1/6

prob_partial:: Integer -> Integer -> Integer -> Rational
prob_partial nd n faccia =  
  prob_faccia * (prob_dadi (nd-1) (n-faccia))


prob_dadi :: Integer -> Integer -> Rational             
prob_dadi 0 n | n == 0   = 1
              | n > 0    = 0
              | n < 0    = 0

prob_dadi nd n =
  sum (map (prob_partial nd n) facce)  

test = (test_loop 20)

test_loop (-1) = 0
test_loop n = (prob_dadi 5 n) + test_loop (n-1)

Qui prob_dadi fa una sommatoria (che nel programma precedente era svolta a mano, elemento per elemento) di una lista che risulta dall’applicazione (tramite map) della funzione prob_partial agli elementi della lista facce.

La funzione prob_partial fa la moltiplicazione di prima:
– calcola la probabilità di ottenere una certa faccia, e la moltiplica per la probabilità di ottenere il numero n-faccia con nd-1 dadi.

E adesso a voi! (Voglio la stessa cosa in Lisp, mi raccomando!)