Boter, kaas en eieren

• Er is (nog) geen in de browser speelbare code:
  Scalafiddle was geen optie: dat geeft een resultaat terug, maar heeft geen REPL.
  
• TODO Spelen zou in de browser alleen met Scala.js kunnen.
  Een Scala-swing GUI heb ik al. Die zou er als service bij geleverd kunnen worden.
• TODO Naast Java-swing kun je in Scala dus ook gebruik maken van Scala-swing, een wrapper-library om de eerste. Ik vind Scala-swing een heel elegante library, in mijn ogen ten onrechte in discrediet geraakt ten gunste van o.a. ScalaFX dat ik verder niet ken.
• De hier getoonde code heeft gedraaid in ghci (Haskell) en Ammonite (Scala)

• Het idee is de Haskell-code letterlijk te vertalen naar Scala, met gebruik van value-functies (nieuw voor mij) zodat compositie mogelijk wordt.
• In de Scala-versie moest soms de volgorde worden aangepast. Je kunt daar bijvoorbeeld geen Grid definiëren als List van List van Player, als de Player nog niet is gedefinieerd.
• De tabelrijen komen zoveel mogelijk overeen met de paragrafen uit het boek. Afwijkingen staan in verband met het hiervoor genoemde volgordeprobleem.
• De hier gebruikte Scala-syntax, met veel value-functies, wijkt af van de syntax die je meestal zult zien, met veel def-methods. Value-functie syntax lijkt op die van functie-literals, de scala versie van anonieme λ-functies, maar dan toegekend aan een variabele. Deze syntax komt veel meer overeen met die van Haskell, terwijl def-methods meer lijken op Java.
  (Ook def-methods kunnen via zgn. eta-expansion automatisch worden omgezet in functies en dan worden gebruikt als argument).

-- 11.2 Basic declarations 
import Data.Char
import Data.List
import System.IO

size :: Int
size = 3 -- In deze versie aanpasbaar

type Grid = [[Player]]
data Player = O | B | X
    deriving (Eq, Ord, Show)

next :: Player -> Player
next O = X
next B = B
next X = O

// 11.2
import scala.util.{Random => Rnd } //In deze versie nog niet nodig

sealed abstract class Player 
case object O extends Player
case object B extends Player
case object X extends Player

//Opstartcommando voor Ammonite-scriptfile. Uitcommentariëren bij gebruik van Swing-Gui
TicTacToe.main(Array()) 
object TicTacToe{
  def main(args: Array[String]): Unit = {
      tictactoe()
  }

  val size: Int = 3

  type Grid = List[List[Player]]

  val next: Player => Player = {
    case O => X
    case B => B
    case X => O
  }

-- 11.3
empty :: Grid
empty = replicate size (replicate size B)

full :: Grid -> Bool
full = all (/= B) . concat

turn :: Grid -> Player
turn g = if os <= xs then O else X
         where 
             os = length (filter (==O) ps)
             xs = length (filter (==X) ps)
             ps = concat g

wins :: Player -> Grid -> Bool
wins p g = any line (rows ++ cols ++ dias)
           where
               line = all (== p)
               rows = g
               cols = transpose g
               dias = [diag g, diag (map reverse g)]

diag :: Grid -> [Player]
diag g = [ g !! n !! n | n <- [0 .. size-1]]

won :: Grid -> Bool
won g = wins O g || wins X g

//-- 11.3
val empty: Grid = List.fill(size,size)(B)

val full: Grid => Boolean = gr => gr.flatten.forall(_!=B)

val turn: Grid => Player = gr => {
    val ps = gr.flatten
    val os = ps.filter(_==O).length
    val xs = ps.filter(_==X).length
    if (os<=xs) O else X
}

@annotation.tailrec //TODO: proberen dit met een val-functie te doen.
def diag(arr: Grid, result: List[Player] = Nil): List[Player] = {
    if (arr.isEmpty) result
    else 
      diag(arr.tail.map(_.tail), result :+ arr.head.head)
}

val wins: (Player, Grid) => Boolean = (p, g) => {
    val rows = g
    val cols = g.transpose
    val dias = List(diag(g), diag(g.map(_.reverse))) 
    val line: List[Player] => Boolean = _.forall(_==p)
    (rows ++ cols ++ dias).exists(line)
}

val won: Grid => Boolean = g => if (wins(O, g) || wins(X, g)) true else false

-- 11.4
putGrid:: Grid -> IO ()
putGrid = putStrLn . unlines . concat . interleave bar . map showRow
          where bar = [replicate ((size*4)-1) '-']

showRow :: [Player] -> [String]
showRow = beside . interleave bar . map showPlayer
          where
              beside = foldr1 (zipWith (++))
              bar    = replicate 3 "|"

showPlayer :: Player -> [String]
showPlayer O = ["   ", " O ", "   "]
showPlayer B = ["   ", "   ", "   "]
showPlayer X = ["   ", " X ", "   "]

interleave :: a -> [a] -> [a]
interleave x []     = []
interleave x [y]    = [y]
interleave x (y:ys) = y : x : interleave x ys

// 11.4
// Libraryfunctie van Haskell:
val unlines: List[String] => String = strs => strs.mkString("\n")
// Libraryfunctie van Haskell:
val concat: List[List[String]] => List[String] = _.flatten

val showPlayer: Player => List[String] = {
    case O => List(" O ")
    case B => List("   ")
    case X => List(" X ")
}

val interleave:  (String ,  List[String]) => List[String] =  {//goed, maar niet generic
    case (x,  Nil)     => Nil /*List()*/
    case (x, y::Nil)   => y::Nil /*List(y)*/
    case (x, y::ys)    =>  y :: x :: interleave(x, ys) 
}

val showRow: List[Player] => String = plrs => {//Signature aangepast
    val beside =  plrs.foldRight( "")(_+_)
    val st0: String = interleave("|",List.fill(3)("   ")).mkString
    val st1: String = interleave("|",plrs.map(showPlayer(_).mkString(""))).mkString
    List(st0,st1,st0).mkString("\n") 
}

val putGrid: Grid => Unit = g => {
    val v1 = g.map(showRow)
    val bar = "-" * (size*4-1)
    val v2 = v1.mkString("\n"+bar+"\n")
    println(v2+"\n")
}

-- 11.5 
valid :: Grid -> Int -> Bool
valid g i = 0 <= i && i < size^2 && concat g !! i == B

move  :: Grid -> Int -> Player -> [Grid]
move g i p =
    if valid g i then [chop size (xs ++ [p] ++ ys)] else []
    where (xs, B:ys) = splitAt i (concat g)

chop :: Int -> [a] -> [[a]] 
chop n [] = []
chop n xs = take n xs : chop n (drop n xs)

// 11.5
val valid: (Grid, Int) => Boolean = (g, i) => {
    val cellen = g.flatten //Vreemd, lukt alleen met tussenstap
    0 <= i && i <= size*size && cellen(i) == B
}

val chop/*[A]*/: (Int, List[Player]) => List[List[Player]] = {
    case (n, Nil) => Nil
    case (n, xs ) => xs.take(n) :: chop (n, (xs.drop(n)))
}

val move: (Grid, Int, Player) => List[Grid] = (g,i,p) => {
    if (valid(g, i)) {
        val gridParts: (List[Player],List[Player]) =  (g.flatten).splitAt(i)
        val (xs, B::ys) = gridParts
        val hersteldGrid: List[Player] = xs ::: List(p) ::: ys
        val listGrid: List[List[Player]] = chop(size, hersteldGrid)
        List(listGrid) //Verwarrend: lijst van 1 Grid, Nil is failure
    }
    else
        Nil
}

--11.6 
getNat :: String -> IO Int
getNat prompt = do putStr prompt
                   xs <- getLine
                   if xs /= [] && all isDigit xs then
                       return (read xs)
                   else
                       do putStrLn "ERROR: Ongeldig nummer"
                          getNat prompt

//--11.6
val prompt: Player => String = p => "Speler " + show(p) + ", doe een zet: (1..9)"

val getNat: (String) => Int = str => { 
    println(str)
    val ch: Int = scala.io.StdIn.readChar.toInt - 48
    if(ch >= 1 && ch <= 9)
        ch-1
    else {
        println("ERROR: Ongeldig nummer")
        getNat(str)
    }
}

//-- Van pagina 134
type Pos = (Int,Int)

val cls: () => Unit = () => print ("\u001b[2J")

val show: Any => String = _.toString

val goto: Pos => Unit = pos => {
    val (x,y) = (pos._1, pos._2)
    print ("\u001b[" + y + ";" + x + "H")
}

-- 11.7
tictactoe :: IO ()
tictactoe = run empty O

run :: Grid -> Player -> IO ()
run g p = do cls
             goto (1,1)
             putGrid g
             run' g p

run' :: Grid -> Player -> IO ()
run' g p | wins O g = putStrLn "Speler O wint!\n"
         | wins X g = putStrLn "Speler X wint!\n"
         | full g   = putStrLn "Gelijk spel!\n"
         | otherwise =
             do i <- getNat (prompt p)
                case move g i p  of
                    [] -> do putStrLn "ERROR: Ongeldige zet"
                             run' g p
                    [g'] -> run g' (next p)

prompt :: Player -> String
prompt p = "Speler " ++ show p ++ ", doe een zet: "

-- Van pagina 134
type Pos = (Int,Int)

cls :: IO ()
cls = putStr "\ESC[2J"

goto :: Pos -> IO ()
goto (x,y) = putStr ("\ESC[" ++ show y ++ ";" ++ show x ++ "H")

// 11.7

val run: (Grid, Player) => Unit = (g, p) => {
    cls ()
    goto(1,1)
    putGrid(g)
    run1(g,p) 
}

val tictactoe: () => Unit = () => run(empty, O) //mens <==> mens
//val tictactoe: () => Unit = () => play(empty, O) //mens <==> computer
                                  
val run1: (Grid, Player) => Unit = (g,p) => {
        if (wins(O,g))  println ("Speler O heeft gewonnen!\n")
        else if (wins(X,g))  println ("Speler X heeft gewonnen!\n")
        else if (full(g))   println ("Gelijk spel!\n")
        else {
		    val i = getNat(prompt(p))
		    move(g,i,p) match {
			case Nil            => println ("ERROR: Ongeldige zet")
					       run1(g,p)                                        
			case List(g1: Grid) => run(g1, next(p)) 
		    }
              }
}

-- 11.8 
data Tree a = Node a [Tree a] 
              deriving Show

gameTree :: Grid -> Player -> Tree Grid
gameTree g p = Node g [gameTree g' (next p) | g' <- moves g p]

moves :: Grid -> Player -> [Grid]
moves g p
    | won g     = []
    | full g    = []
    | otherwise = concat [move g i p | i <- [0..((size^2)-1)]]

// 11.8
sealed trait Tree[+A]
case class Node[A](value: A, subTrees: List[Tree[A]]) extends Tree[A]

val moves: (Grid, Player) => List[Grid] = (g,p) => {
  if (won(g) || full(g)) Nil
  else (for(i <- 0 to size*size-1) yield move(g,i,p)).toList.flatten
}

val gameTree: (Grid, Player) => Tree[Grid] = (g,p) => {
  val choices = for(g1 <- moves(g,p)) yield gameTree(g1,next(p))
  Node(g, choices)
}

-- 11.9
prune :: Int -> Tree a -> Tree a
prune 0 (Node x _ ) = Node x []
prune n (Node x ts) = Node x [prune (n-1) t | t <- ts]

depth :: Int
depth = 9

/* Nu mens tegen computer*/
// 11.9
val prune: (Int, Tree[Grid]) => Tree[Grid] = {
  case (0, Node(x,_ )) => Node(x,Nil)
  case (n, Node(x,ts)) => Node(x, for (t<-ts) yield prune(n-1, t))
}

val depth: Int = 9

-- 11.10 
minimax :: Tree Grid -> Tree (Grid, Player)
minimax (Node g [])
    | wins O g  = Node (g,O) []
    | wins X g  = Node (g,X) []
    | otherwise = Node (g,B) []
minimax (Node g ts)
    | turn g == O = Node (g, minimum ps) ts'
    | turn g == X = Node (g, maximum ps) ts'
                    where
                        ts' = map minimax ts
                        ps = [p | Node (_,p) _ <- ts']

bestmove ::Grid -> Player -> Grid
bestmove g p = head [g' | Node(g',p') _ <- ts, p' == best]
               where 
                   tree = prune depth (gameTree g p )
                   Node (_,best) ts = minimax tree

// 11.10
val minimax: (Tree[Grid]) => Tree[(Grid, Player)] = {
  case (Node(g,Nil))=> if      (wins(O,g)) Node((g,O),Nil)
                       else if (wins(X,g)) Node((g,X),Nil)
                       else                Node((g,B),Nil)

  case (Node(g,ts )) => val ts1: List[Tree[(Grid,Player)]]=ts.map(minimax)
                        val ps:  List[Player]             = for (Node((_,p),_) <- ts1) yield p
                          if(turn(g)==O) Node((g,minimum(ps)),ts1)
                          else  Node((g,maximum(ps)),ts1) 
                          
}
val playerRank: Player => Int = {
  case O =>1
  case B =>2
  case X =>3
}
val playerName: Player => String = {
  case O => "O"
  case B => " "
  case X => "X"
}
val minimum: List[Player] => Player = _.sortBy(playerRank).head

val maximum: List[Player] => Player = _.sortBy(playerRank).reverse.head

val bestMove: (Grid, Player) => Grid = (g,p) => {
  val tree: Tree[Grid]  = prune(depth, gameTree(g,p))
  val Node((_,best),ts) = minimax(tree)
  //(for(Node((g1,p1),_)<-ts; if p1==best)yield g1).head //Original
  val result = for(Node((g1,p1),_)<-ts; if p1==best)yield g1
  if (result != Nil) result.head else empty
}

-- 11.11 
main :: IO ()
main = do hSetBuffering stdout NoBuffering
          play empty O

play :: Grid -> Player -> IO ()
play g p = do cls
              goto (1,1)
              putGrid g
              play' g p

play' :: Grid -> Player -> IO ()
play' g p 
    | wins O g = putStrLn "Speler O heeft gewonnen!\n"
    | wins X g = putStrLn "Speler X heeft gewonnen!\n"
    | full g   = putStrLn "Het is een gelijk spel!\n"
    | p == O   = do i <- getNat (prompt p)
                    case move g i p of
                        []   -> do putStrLn "ERROR: Ongeldige zet"
                                   play' g p
                        [g'] -> play g' (next p)
    | p ==X   = do putStr "Speler X denkt ..."
                   (play $! (bestmove g p)) (next p)

// 11.11
val play:  (Grid, Player) => Unit = (g, p) => {
    cls ()
    goto(1,1)
    putGrid(g)
    play1(g,p) 
}

val play1: (Grid, Player) => Unit = (g,p) => {
       if (wins(O,g))  println ("Speler O heeft gewonnen!\n")
       else if (wins(X,g))  println ("Speler X heeft gewonnen!\n")
       else if (full(g))   println ("Gelijk spel!\n")
       else if(p==O){
                        val i = getNat(prompt(p))
                        move(g,i,p) match {
                            case Nil            => println ("ERROR: Ongeldige zet")
                                                   play1(g,p)                                        
                            case List(g1: Grid) => play(g1, next(p)) 
                        }
                     }
       else if(p==X){
                      println("X denkt even na ...")
                      play(bestMove(g,p),next(p))
                    }
       else println("Oeps")
  }

}