#lang racket

(provide (all-defined-out))

(define (all? p? xs)
  (if (null? xs) #t
	(and (p? (car xs)) (all? p? (cdr xs)))))

(define (any? p? xs)
  (if (null? xs) #f
  (or (p? (car xs)) (any? p? (cdr xs)))))

(define (concat xss)
  (apply append xss))

(define (rows xss) xss)

(define (cols xss)
(apply map list xss))

(define (row xss i) (list-ref xss i))
(define (col xss i) (list-ref (cols xss) i))

(define (matrix-ref xss i j)
(list-ref (list-ref xss i) j))

(define (set xs i x [counter 0])
  (cond
  ((= i -1) (cons x xs))
  ((and (= counter i) (null? xs) (list x)))
  ((null? xs) xs)
  ((= counter i) (cons x (cdr xs)))
  (else (cons (car xs) (set (cdr xs) i x (+ 1 counter))))))

(define (place xss i j x)
(set xss i (set (row xss i) j x)))

(define (diag xss)
  (if (null? xss) xss
    (cons (caar xss) (diag (map cdr (cdr xss)))  )))

(define (flip xss)
(map reverse xss))

(define (diags xss)
(list (diag xss) (diag (flip xss))))

(define (apply-matrix op f xss)
(if (null? xss) xss
(cons (op f (car xss)) (apply-matrix op f (cdr xss)) )))

(define (map-matrix f xss)
(apply-matrix map f xss))

(define (filter-matrix p? xss)
(apply-matrix filter p? xss))

(define (zip-with f xs ys)
  (if (or (null? xs) (null? ys))
  '()
  (cons (f (car xs) (car ys)) (zip-with f (cdr xs) (cdr ys)))))


(define (zip-matrix xss yss)
  (if (or (null? xss) (null? yss)) '()
  (cons (zip-with cons (car xss) (car yss))
   (zip-matrix (cdr xss) (cdr yss)))))



(define (liner-set a b)
(if(>= a b) '()
 (cons a (liner-set (+ a 1) b))))

(define (matrix-w xss) (length (car xss)))
(define (matrix-h xss) (length xss))

(define (self-matrix w h)
  (define self-w (liner-set 0 w))
  (define self-h (liner-set 0 h))
  (map
    (lambda (i)
    (map
      (lambda (j)
	    (cons i j)) self-w)) self-h))


 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(define (check w . xss)
(cond
((null? xss) #f)
((all? (lambda (x) (equal? x w)) (car xss)) #t)
(else (apply check w (cdr xss)))
))


(define (winner xss)
  (define dat (append (diags xss) (rows xss) (cols xss)))
	(cond
	((apply check "X" dat) "X")
	((apply check "O" dat) "O")
	((any? (lambda (x) (equal? x #f)) (apply append dat)) #f)
	(else "D")))



(define (plays xss)
 (apply append (map-matrix cdr
 (filter-matrix (lambda (x) (equal? (car x) #f))
  (zip-matrix xss (self-matrix (matrix-w xss)(matrix-h xss) ))))))

(define (inverse x)
	(cond
		((= x 1) -1)
		((= x -1) 1)
		(else 0)
))

(define (cur-winner xss curr)
(define out (winner xss))
	(cond
	((not out) #f)
	((equal? out "D") 0)
	((equal? out curr) 1)
	(else -1)))

(define (not-cur x)
	(if (equal? x "X") "O" "X"))

(define (outcome curr-board curr-sign)
(define state (cur-winner curr-board curr-sign))
(define branches (plays curr-board))

(if state
state
 (inverse (foldr
(lambda (x out)
 (min
 	out
 	 (outcome (place curr-board (car x) (cdr x) curr-sign) (not-cur curr-sign ) ))
 ) 1 branches))))

(define GAME '((#f "O" #f)
               ("O" "X" #f)
               (#f #f #f)))

(define (play curr-board curr-sign)
 (define state (cur-winner curr-board curr-sign))
 (if state
 #f
 (car (foldr (lambda (x a)
  (if (>= (cdr x)(cdr a)) x a))
  (cons (cons 0 0) -2)
  (map (lambda (x)
  (cons x (inverse (outcome (place curr-board (car x) (cdr x) curr-sign) (not-cur curr-sign ) )))) (plays curr-board)))
 ))
)

;;;;;;;;;;;;;;;;;;;;;;;;
(define (play-all begin-board begin-sign)
(define outz (play begin-board  begin-sign))
	(if outz
	(cons (cons begin-sign outz)
 	(play-all (place begin-board (car outz) (cdr outz) begin-sign) (not-cur begin-sign )))
	'()))

(define curr-board GAME)
(define curr-sign "X")
(map (lambda (x)
  (cons x (inverse (outcome (place curr-board (car x) (cdr x) curr-sign) (not-cur curr-sign ) )))) (plays curr-board))