In the book From Bacteria to Bach and Back by Daniel Dennet there is this note:

Four people come to a river in the night. There is a narrow bridge, and it can only hold two people at a time. They have one torch and, because it’s night, the torch has to be used when crossing the bridge. Person A can cross the bridge in one minute, B in two minutes, C in five minutes, and D in eight minutes. When two people cross the bridge together, they must move at the slower person’s pace. The question is, can they all get across the bridge in fifteen minutes or less?

This is a well know crossing problem like wolf cabbage and goat problem. Many of this problem are solved by simple Prolog program. But now i want solve this problem with a functional language: F#. A simple solution is (based on this):

open System

//cambia per trovare soluzioni in tempi diversi
let MAX_TIME = 15

type Person = 
  | Person of string * int

type Direction =
  | L
  | R

type Move =
  | Move of Direction * Person list

//estende il modulo List
module List =
  let rec combinations items =
    [
      match items with
      | [] -> ()
      | x::xs ->
        for y in xs do yield x, y
        yield! combinations xs
    ]

let rec Solve cost moves atStart atEnd dir =
  seq {
    if cost > MAX_TIME then ()
    elif Set.isEmpty atStart then yield cost, List.rev moves
    else
      match dir with
      | L ->
        for Person(_, time) as person in atEnd do
          let move = Move(dir, [person])
          yield! Solve (cost + time) (move :: moves) (Set.add person atStart) (Set.remove person atEnd) R
      | R ->
        let combinations = List.combinations (Set.toList atStart)
        for (Person(_, time1) as person1), (Person(_, time2) as person2) in combinations do  
          let move = Move(dir, [person1; person2])
          let persons = set [person1; person2]
          yield! Solve (cost + (max time1 time2)) (move :: moves) (atStart - persons) (atEnd + persons) L
  }      

let Persons =
  set [
    Person("A", 1)
    Person("B", 2)
    Person("C", 5)
    Person("D", 8)
    //Person("E", 1)
  ]

Solve 0 [] Persons Set.empty R
|> Seq.iter (printfn "%A")

 

Executing the program yield the following output (can be executed as is in LINQPad):

(15,
 [Move (R,[Person (“A”,1); Person (“B”,2)]); Move (L,[Person (“A”,1)]);
  Move (R,[Person (“C”,5); Person (“D”,8)]); Move (L,[Person (“B”,2)]);
  Move (R,[Person (“A”,1); Person (“B”,2)])])
(15,
 [Move (R,[Person (“A”,1); Person (“B”,2)]); Move (L,[Person (“B”,2)]);
  Move (R,[Person (“C”,5); Person (“D”,8)]); Move (L,[Person (“A”,1)]);
  Move (R,[Person (“A”,1); Person (“B”,2)])])

So the puzzle have two equivalent solution.

Playing with set of Persons and MAX_TIME constant, is possible to explore solution for different problem.

In un articolo su Il Post si discuteva di un indovinello. Nei commenti all’articolo si faceva cenno ad un’altro indovinello della stessa categoria. Facendo una breve ricerca in rete ho trovato una trattazione del problema nientedimeno che da parte di E.W.Dijkstra. La soluzione è sicuramente la più elegante e rigorosa tra quelle che si possono trovare in rete, che spesso non si capisce bene il passo da un passaggio e l’altro. Mi è quindi sembrato un buon esercizio per rinfrescare le mie conoscenze di F# tentare di svolgere i passaggi matematici della soluzione in F# appunto. Ma prima riassumiamo il problema come descritto nella soluzione di Dijkstra.

Ci  sono tre persone, Cheryl sceglie due numeri nell’intervallo [2..99], poi comunica a Paul il prodotto di questi numeri, mentre a Sam viene comunicata la somma dei due numeri. A questo punto si svolge il seguente dialogo:

Paul: non conosco i due numeri;

Sam: lo sapevo già;

Paul: allora adesso so quali sono i due numeri;

Sam: allora anch’io adesso so quali sono;

A questo punto ci viene chiesto di determinare i due numeri, è stabilire che la soluzione sia unica.

Dalla prima affermazione di Paul possiamo deudurre che:

  1. il prodotto non è il prodotto di due numeri primi;

e dal fatto che, inoltre, i fattori devono essere minori di 99, segue che il prodotto non può contenere fattori primi>= 50, o poiché 53 è il più piccolo numero primo >=50 ( questo perché banalmente 50*2=100>99)

2. il prodotto non contiene fattori >=53

Poiché Sam sa anche lui prima di qualsiasi informazione da parte di Paul che Paul non può determinare i due fattori, la somma dei due numeri deve essere tale che le proprietà 1 e 2 possono essere dedotte dalla loro somma. La proprietà 1 esclude tutte le somme che possono essere scritte come la somma di due numeri primi. La congettura di Goldbach (grandioso! ndt) dice che tutti i numeri pari >=4 possono essere scritti come somma di due numeri primi, esclude tutti i numeri pari per la somma (se non è dato nessun limite superiore per i numeri). Se un numero dispari può essere scritto come somma di due numeri primi, uno di essi deve essere pari, ossia 2, e quindi sapere che la somma è un numero non primo +2 è sufficiente per garantire la proprietà 1. Per garantire la proprietà 2 la somma deve essere <=54.

Ora dalla prima risposta di Sam deriva che la somma è un numero non primo + 2 e <=54. Chiamiamo questo insieme S0.

Dijkstra determina l’insieme a mano, io ho cercato di determinarlo con F#. Per eseguire il programma ho utilizzato l’ottimo LINQPad, che a dispetto del nome serve ad eseguire in maniera immediata pezzi di codice scritti non solo in LINQ ma in uno dei vari linguaggi disponibili per .NET, anche F#. Quindi installatelo immediatamente, può tornare sempre utile.  Quindi apriamo un nuovo documento in LINQPad e impostiamo il linguaggio a F# program. Poi scriviamo il seguente codice:

// crivello di Eratostene per i numeri primi da [a..b]
let rec sieve = function
    | (p::xs) -> p :: sieve [ for x in xs do if x % p > 0 then yield x ]
    | [] -> [] 

//controlla se il numero e nella lista
let containsNumber number list = List.exists (fun elem -> elem = number) list

//lista dei numeri primi da 2 a 53
let primes = sieve [2..53] 

//test se pari o dispari
let rec even n = n = 0 || odd (abs n - 1)
        and odd n = n <> 0 &&  even (abs n - 1) 

//finalmente il nostro insieme
let S0= [ for a in 2 .. 53 do
    if odd a && a+2<54 && not (containsNumber a primes) then yield ( a+2 ) ]

S0.Dump("Insieme di test")

Eseguendo questo pezzo di codice viene stampato l’insieme S0 = {11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53}, esattamente lo stesso presente nell’articolo di Dijkstra, quindi fino a qui ci siamo.

Torniamo al ragionamento di Dijkstra:

Dopo la prima risposta di Sam, Paul sa che la somma dei due fattori deve appartenere all’insieme S0. Se Paul è più intelligente di quello che siamo stati, lui forse potrebbe concludere che la soma appartiene ad un insieme più piccolo, ma non può essere più intelligente di quello che sono stato, io non ho altra scelta che assumere che Paul potrebbe determinare i fattori del prodotto attraverso conoscenze aggiuntive che la loro somma appartiene a S0.

Paul non può determinare i fattori se il loro prodotto può essere scritto in più di un modo come  x*y, in modo tale che x+y appartiene a S0. Potrebbe, per esempio, essere disorientato dal prodotto = 30, perché 6+5=11 e 2+15=17. Paul, tuttavia, ha un compito particolarmente facile se il prodotto è (numero primo * potenza di 2): poiche tutti gli elementi di S0 sono dispari, uno dei fattori deve essere dispari ( ad esempio un numero primo), l’altro deve essere pari ( cioè una potenza di 2).

Quindi se il prodotto era 24, Paul concluderebbe immediatamente 3*8, se fosse  28, Paul concluderebbe immediatamente 7*4. Poiché 3+8=7+4=11 nel caso della somma = 11, Sam non potrebbe mai fare l’affermazione finale che anche lui conosce i due numeri! Quindi, in considerazione della seconda risposta data da Sam, noi (ma non Paul quando da la seconda risposta) possiamo cancellare da S0 tutti i valori come 11 che possono essere scritti come un numero primo+ una potenza di 2.

Quindi torniamo al nostro programma F# e sfoltiamo l’insieme S0.

(*
determiniamo S1 eliminiamo da S0 tutti valori che possono essere scritti
come una potenza di 2^x + numero primo
x>1

la funzione dato un itero y determina per quante x y= 2^x+numero primo per x>1
è facile filtrare la lista S0 per ottenere S1
*)
let s2p2 n =
 let rec loop c p =
 if c>p then 0
 elif (containsNumber (p-c) primes) then 1 + loop (c*2) p
 else 0 + loop (c*2) (p-c)

 loop 4 n

let S1=S0
 |> List.filter ( fun x -> (s2p2 x)=1)

S1.Dump("somme che possono essere scritti come 2^x+numero primo e x>")

Questo programma ci da l’insieme S1={17,29,41,53}.

Esaminando le 4 possibilità a turno:

somma = 17

2 * 15 = 6 * 5         rigettato perché 6 + 5 = 11  è in S0

3 * 14 = 2 * 21       rigettato perché 2 + 21=23 è in S0

4 * 13                      decidibile per Paul

5 * 12 = 3 * 20       rigettato perché 2 + 35 = 37 è in S0

6 * 11 = 2 * 33       rigettato perché 3  + 24 = 27 è in S0

7 * 10 = 2 * 35      rigettato perché 2 + 35 = 37 è in S0

8 * 9 = 3 * 24       rigettato perché 3 +24 = 27 è in S0

Poiché il caso della somma 17 fornisce solo un caso che è decidibile per Paul su quali siano i fattori, la coppia (4, 13) è una soluzione. Per mostrare che questa soluzione è unica, è sufficiente mostrare che per ogni caso, dei tre rimanenti, in S1 almeno uno degli altri casi decidibili esistono affiancati  a 16 * 13, 4 * 37m e 16 * 37 rispettivamente.

somma = 29

4 * 25 = 20 * 5      decidibile per Paul (come 4 * 25) perché 20+5=25 che non è in S0

 

somma = 41

3 * 38 = 2* 57 = 6 * 19    decidibile per Paul (come 3 *38) perch* ne 2 +57=59 ne 6+19=25 sono in S0

 

somma = 53

6*47=2*141=3*94         decidibile per Paul (come 6 * 47) perché ne 2+141=143 ne 3+94=97 sono in S0

Quindi Sam non può giustificare la sua seconda risposta per 29, 41, o 53, per cui è dimostrata l’unicità della soluzione.

I giochi di auto per consolle o pc non mi sono mai piaciuti molto. Forse sopratutto perché sembravo sembre un imbranato, facendo andare la macchina a zig-zag senza mai trovare la giusta angolazione dei comandi della consolle. Così è stato ieri mentre provavo un gioco di corse sulla PS3, ad uno dei Mediaworld di Roma. Poi passando vicino al banco dei giochi per la WII ho trovato Need for speed in offerta a soli 19 euro, così ho deciso di prenderlo, così a scatola chiusa. Dopo averlo provato, posso dire che per me controllare l’auto dovendo inclinare il controller della WII, risulta molto intuitivo. Infatti riesco addirittura ad andare in linea retta. Certo la grafica della WII non può rivaleggiare con quella della PS3, ma il coinvolgimento è sicuramente uguale o superiore. Penso che per risultare uguale sulle altre consolle bisogna necessariamente comprare uno di quei volanti opzionali.

Need for Speed in vendita su eBay.