Share
Embed
Come risolvere un puzzle cripto-aritmetico in Scala
Utilizzando Monad Transformer o un semplice algoritmo genetico
Filippo Vitale
April 16, 2019
Transcript
119 slides
-
@filippovitale Aprile 2019 FPinBO Utilizzando Monad Transformer o un semplice
algoritmo genetico Come risolvere un puzzle cripto-aritmetico in Scala -
“Brute force” 10!/(10 – 8)! ≈ 2 Milioni Quanto è
esteso lo Spazio di Ricerca? -
for (int s = 0; s < 10; ++s) for
(int e = 0; e < 10; ++e) for (int n = 0; n < 10; ++n) for (int d = 0; d < 10; ++d) ... s != 0 e != s n != s && n != e d != s && d != e && d != n Approccio Imperativo: 8 loop annidati -
for (int s = 0; s < 10; ++s) for
(int e = 0; e < 10; ++e) for (int n = 0; n < 10; ++n) for (int d = 0; d < 10; ++d) ... s != 0 e != s n != s && n != e d != s && d != e && d != n Ricerca soluzioni teoricamente possibili: ➔ Generazione delle assegnazioni ➔ Verifica dei vincoli -
for { s <- 0 to 9 if s !=
0 e <- 0 to 9 if e != s n <- 0 to 9 if n != s && n != e d <- 0 to 9 if d != s && d != e && d!=n ... for (int s = 0; s < 10; ++s) for (int e = 0; e < 10; ++e) for (int n = 0; n < 10; ++n) for (int d = 0; d < 10; ++d) ... s != 0 e != s n != s && n != e d != s && d != e && d != n Ricerca soluzioni teoricamente possibili: ➔ Generazione delle assegnazioni ➔ Verifica dei vincoli -
val listOfDigits = (0 to 9).toList val solutions = for
{ s <- listOfDigits if s != 0 e <- listOfDigits if s != e n <- listOfDigits if s != n && e != n d <- listOfDigits if s != d && e != d && n != d m <- listOfDigits if m != 0 if s != m && e != m && n != m && d != m o <- listOfDigits if s != o && e != o && n != o && d != o && m != o r <- listOfDigits if s != r && e != r && n != r && d != r && m != r && o != r y <- listOfDigits if s != y && e != y && n != y && d != y && m != y && o != y && r != y } yield ??? Ricerca soluzioni teoricamente possibili Verifica vincoli -
val listOfDigits = (0 to 9).toList val solutions = for
{ s <- listOfDigits if s != 0 e <- listOfDigits if s != e n <- listOfDigits if s != n && e != n d <- listOfDigits if s != d && e != d && n != d m <- listOfDigits if m != 0 if s != m && e != m && n != m && d != m o <- listOfDigits if s != o && e != o && n != o && d != o && m != o r <- listOfDigits if s != r && e != r && n != r && d != r && m != r && o != r y <- listOfDigits if s != y && e != y && n != y && d != y && m != y && o != y && r != y send = List(s, e, n, d).reduce(_ * 10 + _) more = List(m, o, r, e).reduce(_ * 10 + _) money = List(m, o, n, e, y).reduce(_ * 10 + _) if send + more == money } yield (send, more, money) Ricerca soluzioni teoricamente possibili Verifica vincoli -
val listOfDigits = (0 to 9).toList val solutions = for
{ s <- listOfDigits if s != 0 e <- listOfDigits if s != e n <- listOfDigits if s != n && e != n d <- listOfDigits if s != d && e != d && n != d m <- listOfDigits if m != 0 if s != m && e != m && n != m && d != m o <- listOfDigits if s != o && e != o && n != o && d != o && m != o r <- listOfDigits if s != r && e != r && n != r && d != r && m != r && o != r y <- listOfDigits if s != y && e != y && n != y && d != y && m != y && o != y && r != y send = List(s, e, n, d).reduce(_ * 10 + _) more = List(m, o, r, e).reduce(_ * 10 + _) money = List(m, o, n, e, y).reduce(_ * 10 + _) if send + more == money } yield (send, more, money) -
? ? ? ? ? ? ? ? ? ?
S = … -
1 2 3 4 5 6 7 8 9 0
0 S = 0! -
? ? ? ? ? ? ? ? ? ?
S = … -
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 5 1 2 3 4 0 6 7 8 9 0 6 2 3 4 5 1 7 8 9 0 1 7 3 4 5 6 2 8 9 0 1 3 2 4 5 6 7 8 9 0 1 8 3 4 5 6 7 8 9 0 1 4 3 2 5 6 7 8 9 0 1 9 3 4 5 6 7 8 2 -
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 5 1 2 3 4 0 6 7 8 9 0 6 2 3 4 5 1 7 8 9 0 1 7 3 4 5 6 2 8 9 0 1 3 2 4 5 6 7 8 9 0 1 8 3 4 5 6 7 8 9 0 1 4 3 2 5 6 7 8 9 0 1 9 3 4 5 6 7 8 2 S = 1 -
0 1 2 3 4 5 6 7 8 9
S = 1 -
0 1 2 3 4 5 6 7 8 9
S = 1 E = … -
0 1 2 3 4 5 6 7 8 9
S = 1 E = … 0 2 3 4 5 6 7 8 9 -
val l = for { a <- List(1, 2) b
<- List(1, 2) } yield Map('a' -> a, 'b' -> b) val l = ??? -
val l = for { a <- List(1, 2) b
<- List(1, 2) } yield Map('a' -> a, 'b' -> b) val l: List[A] = ??? -
val l = for { a <- List(1, 2) b
<- List(1, 2) } yield Map('a' -> a, 'b' -> b) val l: List[Map[Char, Int]] = ??? -
val l = for { a <- List(1, 2) b
<- List(1, 2) } yield Map('a' -> a, 'b' -> b) List(Map('a' -> 1, 'b' -> 1), Map('a' -> 1, 'b' -> 2), Map('a' -> 2, 'b' -> 1), Map('a' -> 2, 'b' -> 2)) -
val l = for { a <- List(1, 2) b
<- List(1, 2) if a != b } yield Map('a' -> a, 'b' -> b) List(Map('a' -> 1, 'b' -> 2), Map('a' -> 2, 'b' -> 1)) -
“The future is a function of the past.” – A.
P. Robertson https://goo.gl/jt6bvz -
// stateful computation type State[S, +A] = S => (S,
A) https://bartoszmilewski.com/2016/11/30/monads-and-effects/#State -
// stateful computation type State[S, +A] = S => (S,
A) https://stackoverflow.com/a/10231786/81444 -
object State { def apply[S, A](f: S => (S, A)):
State[S, A] } -
// stateful computation f: S => (S, A) def select(xs:
List[Int]): (List[Int], Int) = (xs.tail, xs.head) -
// stateful computation f: S => (S, A) def select(xs:
List[Int]): (List[Int], Int) = (xs.tail, xs.head) 1 2 3 4 5 6 7 8 9 0 -
// stateful computation f: S => (S, A) def select(xs:
List[Int]): (List[Int], Int) = (xs.tail, xs.head) -
// stateful computation f: S => (S, A) def select(xs:
List[Int]): (List[Int], Int) = (xs.tail, xs.head) -
import scalaz.State val s = for { a <- State(select)
b <- State(select) } yield Map('a' -> a, 'b' -> b) val s = ??? -
import scalaz.State val s = for { a <- State(select)
b <- State(select) } yield Map('a' -> a, 'b' -> b) val s: State[ S, A ] = ??? -
import scalaz.State val s = for { a <- State(select)
b <- State(select) } yield Map('a' -> a, 'b' -> b) val s: State[ S, A ] = ??? def select(xs: List[Int]): (List[Int], Int) -
import scalaz.State val s = for { a <- State(select)
b <- State(select) } yield Map('a' -> a, 'b' -> b) val s: State[ List[Int], A ] = ??? -
import scalaz.State val s = for { a <- State(select)
b <- State(select) } yield Map('a' -> a, 'b' -> b) val s: State[ List[Int], Map[Char, Int] ] = ??? -
import scalaz.State val s = for { a <- State(select)
b <- State(select) } yield Map('a' -> a, 'b' -> b) val s: State[ List[Int], Map[Char, Int] ] = ??? -
import scalaz.State val s = for { a <- State(select)
b <- State(select) } yield Map('a' -> a, 'b' -> b) val s: State[ List[Int], Map[Char, Int] ] = ??? -
import scalaz.State val s = for { a <- State(select)
b <- State(select) } yield Map('a' -> a, 'b' -> b) val s: State[ List[Int], Map[Char, Int] ] = ??? s.eval(List(1, 2)) ==== Map('a' -> 1, 'b' -> 2) -
import scalaz.State val s = for { a <- State(select)
b <- State(select) } yield Map('a' -> a, 'b' -> b) val s: State[ List[Int], Map[Char, Int] ] = ??? s.eval(List(8, 3)) ==== Map('a' -> 8, 'b' -> 3) -
val s = for { a <- State(select) b <-
State(select) c <- State(select) } yield Map('a' -> a, 'b' -> b, 'c' -> c) s.eval(1 |-> 3) ==== Map('a' -> 1, 'b' -> 2, 'c' -> 3) -
val s = for { a <- State(select) b <-
State(select) c <- State(select) d <- State(select) } yield Map('a' -> a, 'b' -> b, 'c' -> c, 'd' -> d) s.eval(1 |-> 4) ==== Map('a' -> 1, 'b' -> 2, 'c' -> 3, 'd' -> 4) a b c d -
def select[A](xs: List[A]): (List[A], A) State S => ( S
, A) StateT[F, S, A] S => F[( S , A)] -
def select[A](xs: List[A]): (List[A], A) State S => ( S
, A) def select[A](xs: List[A]): List[(List[A], A)] StateT[F, S, A] S => F[( S , A)] -
def select[A](xs: List[A]): List[(List[A], A)] = xs map { x
=> (xs.filterNot(_ == x), x) } -
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 5 1 2 3 4 0 6 7 8 9 0 6 2 3 4 5 1 7 8 9 0 1 7 3 4 5 6 2 8 9 0 1 3 2 4 5 6 7 8 9 0 1 8 3 4 5 6 7 8 9 0 1 4 3 2 5 6 7 8 9 0 1 9 3 4 5 6 7 8 2 -
sl.eval(1 |-> 2) == ??? import scalaz.StateT import scalaz.std.list._ val
sl = for { a <- StateT(select) b <- StateT(select) } yield Map('a' -> a, 'b' -> b) -
import scalaz.StateT import scalaz.std.list._ val sl = for { a
<- StateT(select) b <- StateT(select) } yield Map('a' -> a, 'b' -> b) sl.eval(1 |-> 2) == List(Map('a' -> 1, 'b' -> 2), Map('a' -> 2, 'b' -> 1)) https://gist.github.com/filippovitale/6cc45396ed917a2a8411 -
val sel = StateT(select[Int]) for { s <- sel e
<- sel n <- sel d <- sel m <- sel o <- sel r <- sel y <- sel … } -
val sel = StateT(select[Int]) for { s <- sel e
<- sel n <- sel d <- sel m <- sel o <- sel r <- sel y <- sel … } Per ogni chiamata `.flatMap`, `sel` restituisce un numero diverso! 0 1 2 3 4 5 6 7 8 9 -
val sel = StateT(select[Int]) for { s <- sel if
s != 0 e <- sel n <- sel d <- sel m <- sel if m != 0 o <- sel r <- sel y <- sel send = List(s, e, n, d).reduce(_ * 10 + _) more = List(m, o, r, e).reduce(_ * 10 + _) money = List(m, o, n, e, y).reduce(_ * 10 + _) if send + more == money } yield (s, e, n, d, m, o, r, y) MonadPlus MonadPlus https://speakerdeck.com/filippovitale/send-plus-more-equals-money-scalasyd-july-2015 -
val listOfDigits = (0 to 9).toList val solutions = for
{ s <- listOfDigits if s != 0 e <- listOfDigits if s != e n <- listOfDigits if s != n && e != n d <- listOfDigits if s != d && e != d && n != d m <- listOfDigits if m != 0 if s != m && e != m && n != m && d != m o <- listOfDigits if s != o && e != o && n != o && d != o && m != o r <- listOfDigits if s != r && e != r && n != r && d != r && m != r && o != r y <- listOfDigits if s != y && e != y && n != y && d != y && m != y && o != y && r != y send = List(s, e, n, d).reduce(_ * 10 + _) more = List(m, o, r, e).reduce(_ * 10 + _) money = List(m, o, n, e, y).reduce(_ * 10 + _) if send + more == money } yield (send, more, money) Ricerca soluzioni teoricamente possibili Verifica vincoli -
"sendmoremoney".distinct.size // 8 distinct `char` val maps = for {
??? } yield ??? Ricerca soluzioni teoricamente possibili Verifica vincoli -
val maps = for { ??? } yield ("sendmoremoney".distinct zip
???).toMap Ricerca soluzioni teoricamente possibili Verifica vincoli -
val maps = for { combination <- (0 to 9).combinations(8)
// 45 combinazioni // Vector(0, 1, 2, 3, 4, 5, 6, 7) // (8, 9) // Vector(0, 1, 2, 3, 4, 5, 6, 8) // (7, 9) // Vector(0, 1, 2, 3, 4, 5, 6, 9) // (7, 8) // Vector(0, 1, 2, 3, 4, 5, 7, 8) // (6, 9) // Vector(0, 1, 2, 3, 4, 5, 7, 9) // (6, 8) // Vector(0, 1, 2, 3, 4, 5, 8, 9) // (6, 7) // Vector(0, 1, 2, 3, 4, 6, 7, 8) // (5, 9) // Vector(0, 1, 2, 3, 4, 6, 7, 9) // (5, 8) // Vector(0, 1, 2, 3, 4, 6, 8, 9) // (5, 7) // ... } yield ("sendmoremoney".distinct zip ???).toMap Ricerca soluzioni teoricamente possibili Verifica vincoli -
val maps = for { combination <- (0 to 9).combinations(8)
// 45 combinazioni permutation <- combination.permutations // 40K permutazioni } yield ("sendmoremoney".distinct zip permutation).toMap Ricerca soluzioni teoricamente possibili Verifica vincoli -
val maps = for { combination <- (0 to 9).combinations(8)
// 45 combinazioni permutation <- combination.permutations // 40K permutazioni } yield ("sendmoremoney".distinct zip permutation).toMap // ~2M Ricerca soluzioni teoricamente possibili Verifica vincoli -
val maps = for { combination <- (0 to 9).combinations(8)
// 45 combinazioni permutation <- combination.permutations // 40K permutazioni } yield ("sendmoremoney".distinct zip permutation).toMap // ~2M val solutions = for { m <- maps if m('s') != 0 && m('m') != 0 send = "send" map m reduce (_ * 10 + _) more = "more" map m reduce (_ * 10 + _) money = "money" map m reduce (_ * 10 + _) if send + more == money } yield (send, more, money) Ricerca soluzioni teoricamente possibili Verifica vincoli -
val maps = for { combination <- (0 to 9).combinations(8)
// 45 combinazioni permutation <- combination.permutations // 40K permutazioni } yield ("sendmoremoney".distinct zip permutation).toMap // ~2M val solutions = for { m <- maps if m('s') != 0 && m('m') != 0 send = "send" map m reduce (_ * 10 + _) more = "more" map m reduce (_ * 10 + _) money = "money" map m reduce (_ * 10 + _) if send + more == money } yield (send, more, money) solutions.next() // (9567,1085,10652) Ricerca soluzioni teoricamente possibili Verifica vincoli -
Risolvere il puzzle a compile-time Peano's arithmetic Shapeless: HList, Sum,
… http://jto.github.io/articles/typelevel_quicksort/ -
Risolvere il puzzle con un Algoritmo Genetico http://dl.acm.org/citation.cfm?id=1725467 Solving cryptarithmetic
problems using a Genetic Algorithm -
Algoritmo genetico type Digit = Int type Individual = Vector[Digit]
// “sendmory” - Individual Vector di lunghezza 8 2 Digit non utilizzate -
Algoritmo genetico type Digit = Int type Individual = Vector[Digit]
// “sendmory” type Population = List[Individual] - Individual - Population -
Algoritmo genetico type Digit = Int type Individual = Vector[Digit]
// “sendmory” type Population = List[Individual] def fitness(individual: Individual): Int // 0 - Individual - Population - Fitness function -
Algoritmo genetico - Individual - Population - Fitness function -
Mutation type Digit = Int type Individual = Vector[Digit] // “sendmory” type Population = List[Individual] def fitness(individual: Individual): Int def mutation(individual: Individual): Individual // asexual genetic algorithm -
/** side-effect */ val r = util.Random val popolationSize =
512 val generationRetainment = 32 // top 6% // 16 of the 28 possible mutations val individualProlificness: Int = generationSize / generationRetainment -
def fitness(individual: Individual): Int = { val cs = "sendmoremoney".distinct
val m = cs.zip(individual).toMap math.abs(send + more - money) } -
def fitness(individual: Individual): Int = { val cs = "sendmoremoney".distinct
val m = cs.zip(individual).toMap val send = "send" map m reduce (_ * 10 + _) val more = "more" map m reduce (_ * 10 + _) val money = "money" map m reduce (_ * 10 + _) math.abs(send + more - money) } -
val mutationIndices = List(0 |-> 7).combinations(2) def everyMutation(individual: Individual): Iterator[Individual]
= r.shuffle(mutationIndices) .map { case Seq(i, j) => individual .updated(i, individual(j)) .updated(j, individual(i)) } // +-+-+-+-+-+-+-+-+ // |S|E|N|D|M|O|R|Y| // +-+-+-+-+-+-+-+-+ // |0|1|2|3|4|5|6|7| // +-+-+-+-+-+-+-+-+ // ^ ^ // | | // +-----+ // [i] [j] -
def createNextGeneration(currentGeneration: Population) : Population = if (fitness(currentGeneration.head) == 0)
{ currentGeneration.take(1) } else { ??? } -
def createNextGeneration(currentGeneration: Population) : Population = if (fitness(currentGeneration.head) == 0)
{ currentGeneration.take(1) } else { currentGeneration.take(generationRetainment) .flatMap(everyMutation(_).take(individualProlificness)) .sortBy(fitness) }