Archive for April, 2010

28
Apr
10

Tic-Tac-Toe: Scala

If Clojure is a way to have your LISP and eat your JVM too, Scala seems more like a subversive attempt to introduce the Java world to dynamic and functional programming in friendly clothing.  The whole approach is very Java: syntactically baroque and wordy, but admirably complete and well-documented.  The java integration is more seamless than it is in Clojure.  I was struggling to figure out how to read a line of input the Scala way, and finally gave up and did it like Java.  It worked, it was easy, and most importantly (ha) it didn’t look out of place.

The downside of syntactical harmony with Java is that it’s a bit ugly.  For example, if you define a method that returns Unit (void), you can stick the curl brace right next to the method name.  If you give it a return type, you have to stick an equals sign in there.  Not a big deal.  But ugly.

That said, it’s still way better than bog-standard Java, as a a language.  Type inference, pattern matching, lazy evaluation, optional duck(ish) typing.  Almost everything I like about Ruby structurally, but with relatively unobtrusive type safety.  I’d miss method_missing under some circumstances, but maybe not enough to matter.  I could definitely see myself doing my next project in Scala + JRuby.

This compiles in Scala 2.7.7.


import java.io.{BufferedReader, InputStreamReader}

object TicTacToe {
    
  private val input = new BufferedReader(new InputStreamReader(System.in))

  def main(args: Array[String]) {
  
    var result: Result = Continue(X)

    while (true) {

      println
      println(board)
      println
      print(result)

      result match {
        case Continue(player) => {
            val space = readAnswer
            if (board.spaceAvailable(space)) {
              board.place(space, player)
              result = board.checkResult(player)
            }
        }
        case _ => return
      }

    }
  }

  def readAnswer: Int = {
    try {
      input.readLine().toInt
    } catch {
      case nfe: NumberFormatException => 0
    }
  }
}

abstract class Player {
  def next: Player
}
case object X extends Player {
  override def toString() = "X"
  def next = O
}
case object O extends Player {
  override def toString() = "O"
  def next = X
}

abstract class Space
case class Empty(n: Int) extends Space { 
  override def toString() = "(" + n + ")"
}
case class Filled(player: Player) extends Space {
  override def toString() = " " + player + " "
}

abstract class Result
case class Win(player: Player) extends Result {
  override def toString() = "" + player + " Wins!\n"
}
case object Draw extends Result {
  override def toString() = "It's a Draw!\n"
}
case class Continue(player: Player) extends Result {
  override def toString() = "Select a square, " + player + ": "
}

object board {
  private val spaces = Array[Space](
    Empty(1),Empty(2),Empty(3),
    Empty(4),Empty(5),Empty(6),
    Empty(7),Empty(8),Empty(9)
  )

  def spaceAvailable(n: Int): Boolean = {
    for (space  return true
        case _ => ()
      }
    }
    return false
  }

  def full: Boolean = {
    for (space  return false
        case _ => ()
      }
    }
    return true;
  }

  def checkResult(player: Player): Result = {
    for (row  {
          return Win(p)
        }
        case _ => ()
      }
    }
    if (full) return Draw
    return Continue(player.next)
  }

  def place(n: Int, player: Player) {
    spaces(n-1) = Filled(player)
  }

  private def get(n: Int): Space = spaces(n-1)

  private def rows: Array[Array[Space]] = {
    Array[Array[Space]](
      spaces.slice(0,3),
      spaces.slice(3,6),
      spaces.slice(6,9),

      Array(get(1),get(4),get(7)),
      Array(get(2),get(5),get(8)),
      Array(get(3),get(6),get(9)),

      Array(get(1),get(5),get(9)),
      Array(get(3),get(5),get(7)))
  }

  override def toString() = {
    spaces(0) + "|" + spaces(1) + "|" + spaces(2) +
    "\n---+---+---\n" +
    spaces(3) + "|" + spaces(4) + "|" + spaces(5) +
    "\n---+---+---\n" +
    spaces(6) + "|" + spaces(7) + "|" + spaces(8)
  }
}

21
Apr
10

Tic-Tac-Toe: Clojure

Clojure, for those who don’t know, is a newish LISP implemented on top of the JVM. It’s designed to play nicely with Java libraries, which I didn’t end up exercising, and is largely lazy and functional, which I did.

If you’ve been following along, you might notice that this implementation is very similar to the one for Scheme. That’s because I cheated and just ported it over. There are some pointed differences in its API, but it was actually pretty easy to translate. No major changes in the basic logic, with the exception of one function which I had to rewrite to get around a JVM-imposed restriction on how recursive you can get inside a let.

I like scheme better on purely aesthetic grounds, but Clojure seems more useful, and is certainly more relevant lately. A few notable innovations:

  • Shortcut lambdas: #(+ %1 10) => (fn [x] (+ x 10))
  • Extensive use of vectors as syntactic distinguishers, e.g. denoting function parameters
  • Java Method calls: (.toString x)
  • Lots more that I didn’t end up using

Here’s the code:

; Defining the players -- Infinite Lazy Sequence
(def players (cycle ["X" "O"]))

; Setting up the board
(def *starting-board*
	 [[1 2 3]
	  [4 5 6]
	  [7 8 9]])

(defn space-available? [space board]
	  (some (fn [row] (some #(= %1 space) row)) board))

; Moving -- returns a transformed board
(defn move [player space board]
	  (letfn [(move-in-row
			   ([accum row]
				 (cond
				   ; if we reach the end, that's it
				   (empty? row) accum
				   ; if we have found the space, take it
				   (= space (first row)) (concat accum (cons player (rest row)))
				   ; if not, keep going
				   true (recur (concat accum (list (first row))) (rest row))))
				 ([row] (move-in-row '() row)))]
		(map move-in-row board)))

(defn space->string [space]
	  (if (number? space)
		(str "(" space ")")
		(str " " space " ")))

(defn row->string [row] (apply str (interpose "|" (map space->string row) )))

(defn board->string [board]
	  (apply str (interpose "\n---+---+---\n" (map row->string board))))

(defn third [seq] (nth seq 2))

(defn winner? [board]
	  (or
		; rows
		(apply = (first board))
		(apply = (second board))
		(apply = (third board))
		; columns
		(apply = (map first board))
		(apply = (map second board))
		(apply = (map third board))
		; diagonals
		(= (first (first board))
		   (second (second board))
		   (third (third board)))
		(= (third (first board))
		   (second (second board))
		   (first (third board)))))

(defn full? [board]
	  (not (some number? (mapcat identity board))))

(defn print-board [board]
	  (do
		(newline)
		(print (board->string board))
		(newline)
		(newline)))

(defn play [board players]
	  (do
		(print-board board)
		(let [ player (first players) ]
		  (cond
			(winner? board) (print (str (first (next players))  " Wins!\n"))
			(full? board) (print "It's a Draw!\n")
			true (do
				   (print (str "Select a square, " player ": "))
				   (flush)
				   (let [answer (read)]
					 (if (and answer (space-available? answer board))
					   (recur (move player answer board) (next players))
					   (recur board players))))))))

(play *starting-board* players)
14
Apr
10

Tic-Tac-Toe: Awk

Awk’s original intended use is as a stream processor, and in fact in its most basic form you can’t even do explicit input. My first version of this used gawk/nawk extensions for that purpose, but I figured it would be a bit more fun to use input patterns, so that’s what you see here.

Perl fans (and thus, Ruby and Python fans) might recognize an ancestor here.

#!/usr/bin/env awk -f

BEGIN {
	split("1 2 3 4 5 6 7 8 9", spaces)
	player = "X"

	print_board()
	print_prompt()
}

/[0-9]/ { place_move($1) }
/./ { print_board(); print_prompt() }

function print_board () {
	print ""
	for (i = 1; i <= 9; i++) {
		space = spaces[i]
		if (space ~ /[0-9]/)
			printf("(%d)", space);
		else
			printf(" %s ", space);

		if (i % 3 == 0) {
			if (i / 3 < 3) {
				printf "\n---+---+---\n";
			}
		} else {
			printf "|";
		}
	}

	print "\n"
}

function print_prompt () {
	printf "Select a square, %s: ", player
}

function read_move () {
	getline move
}

function place_move (move) {
	if (move && spaces[move] == move) {
		spaces[move] = player
		good_move = 0

		if (keep_playing()) {
			swap_player()
		} else {
			exit 0
		}
	}
}

function swap_player () {
	if (player == "X")
		player = "O"
	else
		player = "X"
}

function m3(i, j, k) {
	return spaces[i] == spaces[j] && spaces[j] == spaces[k]
}

function has_winner () {
	return m3(1,2,3) || 
		   m3(4,5,6) ||
		   m3(7,8,9) ||
		   m3(1,4,7) ||
		   m3(2,5,8) ||
		   m3(3,6,9) ||
		   m3(1,5,9) ||
		   m3(3,5,7);
}

function is_draw () {
	for (i = 1; i <= 9; i++) {
		space = spaces[i]
		if (space ~ /[0-9]/) 
			return 0;
	}
	return 1
}

function keep_playing() {
	if (has_winner()) {
		print_board()
		printf("%s Wins!\n", player)
		return 0;
	} else if (is_draw()) {
		print_board()
		print("It's a Draw!")
		return 0;
	} else
		return 1;
}

07
Apr
10

Tic-Tac-Toe: Haskell

Haskell is seriously packed with modern, interesting, expressive goodies.

But I have a message for the Haskell community: stop trying to “simplify” monads.  Really, just stop.  I have yet to see an “explanation” of monads that does not add to the confusion and fear a novice might feel at approaching the language.  You don’t need to know what a monad is in order to use the language effectively.  Talking about them to a beginner is about as useful as explaining loop unrolling and keyhole optimization to a beginning C programmer.  Later, yes, it’s helpful.  But it’s too much information at the start.  A beginner just needs to know that if you want to use code that does IO, it has to go inside a do, and if you want to pull out values and use them elsewhere, you need the <- operator.  It took me three nights of working on this one to learn that one, because the Gentle Introduction relegated I/O to chapter 7.

On that note, you’ve got to stop treating I/O in general as a red-headed stepchild.  I realize that isolating side effects is one of the raisons d’être for Haskell in the first place, but if you hope to win converts from the programming world at large (and I really hope you do) then you’ve got to understand that most of us mere mortals want our programs to do something, and that means input/output.  I understand, or at least I think I do, that you want to instill good habits from the start and minimize time spend in the IO monad, but honestly, the language is pretty good at doing that already.  You’ve got to go and talk to people where they already are before you can lead them somewhere else.

Once peple get used to IO and Maybe and whatever other monads are out there, then you can introduce the concept because there’s somewhere for it to land.  I remember taking CS theory in college, and talking with one of the TFs who I happened to know socially.  He is an extremely bright guy, and as is sometimes common with bright guys, can have trouble explaining a concept to someone who doesn’t get it themselves right away.  I made plea for more concrete examples to go with the theoretical explanations in the class, and his response was, “Well, we assume that you, the smart [name of school] students, can come up with the examples yourselves.”  This is exactly wrong for many many people out there, including a lot of the folks who are attracted to coding in the first place.  Some folks work well top-down — get the overarching concepts and then fill in the details themselves.  But some people learn the other way around — experience the details, and then build up the framework from there.  My impression is that the Haskell community is filled with the former type of learner.  But it’s a great language, even for the more experiential/practical and less theoretical, and I hate to see it shunned as too scary.

Ranting aside, I really enjoyed writing this.  For those of you who haven’t tried it yet, I highly recommend it.  It will make you smarter.  I stumbled on places where it differs from OCaml, and I got stuck on IO for a while, but I’m glad I persevered.

This was written against GHC 6.10.4.


import Data.List (intersperse)
import System.IO (stdout, hFlush)
import System.Exit (exitSuccess)

-- 
-- Users
--
data User = X | O
    deriving(Show, Eq)

otherUser X = O
otherUser O = X

-- 
-- Squares
--
data Square = Move User | Empty Int
    deriving(Eq)

instance Show Square where
    show (Move x)   = " " ++ show x ++ " "
    show (Empty x)  = "(" ++ show x ++ ")"

filled (Move _) = True
filled _        = False

-- 
-- Boards
--
data Board = Board [[Square]]
    deriving(Eq)

instance Show Board where
    show (Board ls) = "\n" ++ concat (intersperse "---+---+---\n" $ map showLine ls) ++ "\n"
        where
            showLine xs = concat (intersperse "|" $ map show xs) ++ "\n"

full (Board squares) = all filled (concat squares)

-- 
-- Results
--
data Result = Continue User Board | Win User Board | Draw Board

instance Show Result where
    show (Continue user board) = show board ++ "Select a square, " ++ show user ++ ": "
    show (Win user board)      = show board ++ show user ++ " Wins!\n"
    show (Draw board)          = show board ++ "It's a Draw!\n"

-- 
-- Initial Board
--
startingBoard :: Board
startingBoard = Board [[Empty 1,Empty 2,Empty 3],
                       [Empty 4,Empty 5,Empty 6],
                       [Empty 7,Empty 8,Empty 9]]

matchSquare :: User -> Int -> Square -> Square
matchSquare user position (Empty x) | x == position = Move user
matchSquare _ _ square                              = square

-- This evaluates the board and determines the result of the current user's action
outcome :: User -> Board -> Result
outcome user board =
      case board of
           (Board [[a, _, _],
                   [_, b, _],
                   [_, _, c]]) | eq a b c -> Win user board

           (Board [[_, _, a],
                   [_, b, _],
                   [c, _, _]]) | eq a b c -> Win user board

           (Board [[a, b, c],
                   [_, _, _],
                   [_, _, _]]) | eq a b c -> Win user board

           (Board [[_, _, _],
                   [a, b, c],
                   [_, _, _]]) | eq a b c -> Win user board

           (Board [[_, _, _],
                   [_, _, _],
                   [a, b, c]]) | eq a b c -> Win user board

           (Board [[a, _, _],
                   [b, _, _],
                   [c, _, _]]) | eq a b c -> Win user board

           (Board [[_, a, _],
                   [_, b, _],
                   [_, c, _]]) | eq a b c -> Win user board

           (Board [[_, _, a],
                   [_, _, b],
                   [_, _, c]]) | eq a b c -> Win user board

           _ | full board -> Draw board
             | otherwise  -> Continue (otherUser user) board
    where
        eq a b c = a == b && b == c
             

move :: User -> Int -> Board -> Result
move user pos board = result user pos board (place user pos board)
    where
        place user pos (Board lines) = Board $ map (placeInLine user pos) lines

        placeInLine user pos         = map $ matchSquare user pos

        result user pos orig board 
            | orig == board          = Continue user orig
            | otherwise              = outcome user board

main :: IO ()
main = loop (Continue X startingBoard)
    where 
        loop result = do 
            putStr $ show result
            hFlush stdout
            case result of
                 Win user board      -> exitSuccess
                 Draw board          -> exitSuccess
                 Continue user board -> getInput user board
        getInput user board = do
             pos <- readLn::IO Int 
             loop (move user pos board)



Follow

Get every new post delivered to your Inbox.