;;William Martin Homework submission. (Tic-Tac-Toe)
;;FULL\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'full?' takes a game board and returns #t
;; if the board is full and #f if the board is not full yet.
;;
;; INPUT: A list.
;;
;; OUTPUT: Boolean.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define full?
(lambda (ls)
(if (member?* 0 ls)
#f
#t)))
;;ALL SAME\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'all-same?' checks a list to see if all
;; elements are all the same.
;;
;; INPUT: A list.
;;
;; OUTPUT: Boolean.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define all-same?
(lambda (ls)
(cond ((null? ls) #t) ;list empty.
((null? (cdr ls)) #t) ;contain only 1.
((equal? (car ls) (cadr ls)) ;1st = 2nd,
(all-same? (cdr ls))) ;recurse w/ tail.
(else #f)))) ;none above, false.
;;ZERO IN\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'zero-in?' tests a list to see if there
;; exists a zero.
;;
;; INPUT: A list.
;;
;; OUTPUT: Boolean.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define zero-in?
(lambda (ls)
(if (member?* 0 ls)
#t
#f)))
;;LIST INDEX\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'list-index' takes a list with a index and
;; uses that index to return the sublist of that position.
;;
;; INPUT: A list and a integer index.
;;
;; OUTPUT: A sub-list.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define list-index
(lambda (index ls)
(cond
((= index 1) (car ls))
((= index 2) (cadr ls))
(else (caddr ls)))))
;;DIAG VERT WIN\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'diag-vert-win?' takes a list and tests
;; that list for a possible diagnol win. Wins are:
;; ((X--)(-X-)(--X)) or ((--X)(-X-)(X--))
;;
;; INPUT: A lis.
;;
;; OUTPUT: Boolean.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define diag-vert-win?
(lambda (ls)
(and
(or (= (caddr (list-index 1 ls))
(caddr (list-index 2 ls))
(caddr (list-index 3 ls)))
(= (cadr (list-index 1 ls))
(cadr (list-index 2 ls))
(cadr (list-index 3 ls)))
(= (car (list-index 1 ls))
(car (list-index 2 ls))
(car (list-index 3 ls)))
(= (car (list-index 1 ls))
(cadr (list-index 2 ls))
(caddr (list-index 3 ls)))
(= (car (list-index 3 ls))
(cadr (list-index 2 ls))
(caddr (list-index 1 ls))))
(> (cadr (list-index 2 ls)) 0))))
;;WINNER\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'winner?' takes a list and checks for a
;; winner.
;;
;; DEPENDENCIES: diag-vert-win?, zero-in?, all-same?.
;;
;; INPUT: A list.
;;
;; OUTPUT: Boolean.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define winner?
(lambda (x)
(cond
((diag-vert-win? x) #t)
((zero-in? x) #f)
((all-same? x) #t)
(else (or winner? (car x)
winner? (cdr x))))))
;;ASK ME\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'ask-me' takes a game board, and the
;; player's number then asks the user to type the new game
;; board (in proper list format); then returns that game
;; board as it's value.
;;
;; INPUT: A list and a integer representing the player.
;;
;; OUTPUT: A list (game board).
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define ask-me
(lambda (ls i-am)
(display "Player ")
(display i-am)
(display ": Type new game board.")
(read)))
;;bill-m\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'bill-m' takes a game board, and the
;; player's number then inserts the player number into the
;; slot of the second zero from either the begining of each
;; sublist or from the other players number. If this is not
;; possible then the procedure reverts to the dumb-stratagy
;; in which just replaces the next zero.
;;
;; INPUT: A list and a integer representing the player.
;;
;; OUTPUT: A list (game board).
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define bill-m
(lambda (ls i-am)
;; this procedure replaces the second zero from the end
;; or from the other player
(define replace-2nd-zero
(lambda (x new)
(cond
((and (= (car x) 0)
(= (cadr x) 0)) (cons (car x) (cons new (cddr x))))
((and (= (cadr x) 0)
(= (caddr x) 0)) (cons (car x) (cons (cadr x) (cons new '())))))))
;; this procedure looks to see if there exists a zero
(define zero-in?
(lambda (x)
(member?* 0 x)))
(define replace-1st-zero
(lambda (x new)
(if (= (car x) 0)
(cons new (cdr x))
(cons (car x) (replace-1st-zero (cdr x) new)))))
;;MAIN PROGRAM
(cond
;; is it possible to insert a 0 in first list?
((or (and (= (car (car ls)) 0)
(= (cadr (car ls)) 0))
(and (= (cadr (car ls)) 0)
(= (caddr (car ls)) 0)))
(cons (replace-2nd-zero (car ls) i-am) (cdr ls)))
;; is it possible to insert a 0 in second list?
((or (and (= (car (cadr ls)) 0)
(= (cadr (cadr ls)) 0))
(and (= (cadr (cadr ls)) 0)
(= (caddr (cadr ls)) 0)))
(cons (car ls)
(cons (replace-2nd-zero (cadr ls) i-am) (cddr ls))))
;; is it possible to insert a 0 in third list?
((or (and (= (car (caddr ls)) 0)
(= (cadr (caddr ls)) 0))
(and (= (cadr (caddr ls)) 0)
(= (caddr (caddr ls)) 0)))
(cons (car ls)
(cons (cadr ls)
(cons (replace-2nd-zero (caddr ls) i-am) '()))))
;; is there just a zero to replace in the first list?
((zero-in? (car ls))
(cons (replace-1st-zero (car ls) i-am)
(cdr ls)))
;; is there just a zero to replace in the second list?
((zero-in? (cadr ls))
(cons (car ls)
(cons (replace-1st-zero (cadr ls) i-am)
(cddr ls))))
;; find the last 0's in the last list and replace.
(else (cons (car ls)
(cons (cadr ls)
(cons (replace-1st-zero (caddr ls) i-am)
'())))))))
;;START\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'start' initializes the game with an empty
;; game board, who goes first, and the two players
;; strategies.
;;
;; INPUT: Two stratagies that take a list and depending
;; on where there is an empty slot on the game
;; board (0's), will mark that spot with it's mark
;; (iAm).
;;
;; OUTPUT: Output will be the action of the call to 'play',
;; which will return a print to the screen of the
;; gameboard as the procedure play recurses
;; through the game. Finally the procedure 'play'
;; will print the reasults of the game.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define start
(lambda (strategy-1 strategy-2)
(play '((0 0 0) (0 0 0) (0 0 0))
1
strategy-1
strategy-2)))
;;PLAY\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'play' takes two stratagies for a
;; tic-tac-toe game and plays them against each other on a
;; game-board comprised of three nested lists (2-d array).
;;
;; INPUT: game-board (2-d array [3x3]),
;; whose-turn which will be a integer 1 or 2,
;; stratagy-1 and stratagy-2 which will be the
;; stratagies that will be played against each
;; other. The stratagies consists of procedures
;; that replace one of the zero's on the game
;; board with it's own mark.
;;
;; OUTPUT: Returns a print to the screen of the
;; gameboard as the procedure play recurses
;; through the game. Finally a print out of the
;; results of game.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define play
(lambda (game-board whose-turn strategy-1 strategy-2)
(cond
((full? game-board)
(print-board game-board)
(display "The board is full. Draw."))
((winner? game-board)
(print-board game-board)
(display "player ")
(display whose-turn)
(display " lost."))
((= whose-turn 1)
(print-board game-board)
(play (strategy-1 game-board 1)
2
strategy-1
strategy-2))
(else
(print-board game-board)
(play (strategy-2 game-board 2)
1
strategy-1
strategy-2)))))
;;PRINT-BOARD\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'print-board' takes a deep list [3x3]
;; and prints it to the screen.
;;
;; INPUT: 'x' or game-board (2-d array [3x3]).
;;
;; OUTPUT: Returns a print to the screen of the
;; gameboard.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define print-board
(lambda (x)
(display (car x))
(newline)
(display (cadr x))
(newline)
(display (caddr x))
(newline)
(newline)))
;;DUMB-STRATEGY\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'dumb-strategy' searches out a game board
;; ([3x3]table) and replaces it with its own number or id.
;;
;; INPUT: A list(gameboard) and an item (integer id
;; (1 or 2)).
;;
;; OUTPUT: The input list is treturned with one of its
;; 0's replaced with the id of this player.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define dumb-strategy
(lambda (x iam)
(define zero-in?
(lambda (x)
(member?* 0 x)))
(define replace-1st-zero
(lambda (x new)
(if (= (car x) 0)
(cons new (cdr x))
(cons (car x) (replace-1st-zero (cdr x) new)))))
(cond
((zero-in? (car x))
(cons (replace-1st-zero (car x) iam)
(cdr x)))
((zero-in? (cadr x))
(cons (car x)
(cons (replace-1st-zero (cadr x) iam)
(cddr x))))
(else (cons (car x)
(cons (cadr x)
(cons (replace-1st-zero (caddr x) iam)
'())))))))
;;ATOM\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'atom?' checks the type of an item.
;;
;; INPUT: An item.
;;
;; OUTPUT: Boolean on whether or not this item is a atom
;; (single item and not a list).
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define atom?
(lambda (x)
(and (not (null? x))
(not (pair? x)))))
;;MEMBER\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
;; This procedure 'member?*' checks a list (deeply) for an
;; item.
;;
;; INPUT: The item to be searched for and a list to
; search in.
;;
;; OUTPUT: Boolean on whether or not this item was found
;; in the list provided.
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
(define member?*
(lambda (item ls)
(cond
((null? ls) #f)
((atom? (car ls))
(or (eq? (car ls) item)
(member?* item (cdr ls))))
(else (or (member?* item (car ls))
(member?* item (cdr ls)))))))
[ t o p ]
© Copyright 2001 William L. Martin All rights reserved.