;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; matrix-lib
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; fori=: num, num, num, (num-->(void)) --> (void)
;; Calls the function given from the beginning value to the end value
;; SIDE EFFECTS: Any side effect caused by the body! function

(define (fori= start-val stop-val step body!)
  (if (>= start-val stop-val)
      (void)
      (begin (body! start-val)
             (fori= (+ step start-val) stop-val step body!))))

;; An accumulator-version of "fori="
;;
;; Call body on each intgeter in [strt,stop)
;; also passing in the result so-far.
;;
(define (fori=-a strt stop body so-far)
  (cond [(>= strt stop) so-far]
        [else (fori=-a (add1 strt) stop body (body strt so-far))]))

;; A matrix is a vector-of-vectors-of-alphas

;; make-matrix: num num alpha -> matrix
;; Purpose: To create a matrix of cols x rows with the initial value of init

(define (make-matrix cols rows init)
  (build-vector cols (lambda (c) (make-vector rows init))))

(define matrix3x3 (make-matrix 3 3 0))
;(define matrix5x5 (make-matrix 5 5 0))
;(define matrix4x8 (make-matrix 4 8 0))
(define matrix5x0 (make-matrix 5 0 0))
(define matrix0x5 (make-matrix 0 5 0))

;; matrix-cols: matrix -> num
;; Purpose: To find the number of columns in a matrix

(define (matrix-cols m)
  (vector-length m))

;; Tests
;(matrix-cols matrix3x3) = 3
;(matrix-cols matrix5x5) = 5
;(matrix-cols matrix4x8) = 8
;(matrix-cols matrix5x0) = 5
;(matrix-cols matrix0x5) = 0


;; matrix-rows: matrix -> num
;; Purpose: To find the number of rows in a matrix

(define (matrix-rows m)
  (if (> (matrix-cols m) 0)
      (vector-length (vector-ref m 0))
      -inf.0))

;; Tests
;(matrix-rows matrix3x3) = 3
;(matrix-rows matrix5x5) = 5
;(matrix-rows matrix4x8) = 8
;(matrix-rows matrix5x0) = 0
;(matrix-rows matrix0x5) = 5

;; matrix-set!: matrix-of-alpha num num alpha -> (void)
;; Purpose: To set matrix[x][y] to val

(define (matrix-set! m x y val)
  (if (and (> (matrix-rows m) 0) (> (matrix-cols m) 0))
      (vector-set! (vector-ref m x) y val)
      (void)))


;; Tests
;matrix3x3
;(matrix-set! matrix3x3 1 1 10)
;matrix3x3
;matrix5x5
;(matrix-set! matrix5x5 3 4 12)
;matrix5x5
;matrix4x8
;(matrix-set! matrix4x8 0 7 2)
;matrix4x8
;matrix0x5
;(matrix-set! matrix0x5 0 2 5)
;matrix0x5
;matrix3x3
;(matrix-set! matrix3x3 4 4 2)
;matrix3x3

;; matrix-ref: matrix-of-alpha num num -> alpha
;; Purpose: To retrieve the value at the given x y coordinates

(define (matrix-ref m x y)
  (vector-ref (vector-ref m x) y))

;; Tests
;(matrix-ref matrix3x3 1 1) = 10
;(matrix-ref matrix5x5 3 4) = 12
;(matrix-ref matrix4x8 0 7) = 2

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

;; a player is 
(define BLACK 'X)
(define WHITE 'O)

;a board position is
(define EMPTY '-)
(define UNSET 'unset)
;-player

;a matrix element is
;(list c r)
;where c is a num and r is a num

(define CONNECT 5)

;(define SAMPLE
;  '((- - - - -)
;    (X X X X -)
;    (- O O O O)
;    (- - - - -)
;    (- - - - -)))


(define SAMPLE
  '((- - - - - - -)
    (X X X X - - -)
    (- O O O O - -)
    (- - O - - - -)
    (- - - O - - -)
    (X O - X - - -)
    (O O X O O - X)))

;; convert: list-of-list-of-alphas -> matrix-of-alphas
;; Converts a list-of-list-of-alpha to a matrix-of-alphas

(define (convert l)
  (local [(define rows (length l))
          (define cols (length (first l)))
          (define m (make-matrix cols rows UNSET))]
    (begin
      (fori= 0 cols 1
             (lambda (i)
               (fori= 0 rows 1
                      (lambda (j)
                        (matrix-set! m i j (list-ref (list-ref l j) i))))))
      m)))

;; Tests
(define SAMPLE-m (convert SAMPLE))


;valid?: m c r -> boolean
;checks if we're in a valid spot in the matrix
(define (valid? m c r)
  (and (< c (matrix-cols m))
       (< r (matrix-rows m))
       (>= c 0)
       (>= r 0)))

;tests
;(valid? SAMPLE-m 1 1) = true
;(valid? SAMPLE-m -1 3) = false
;(valid? SAMPLE-m 3 -1) = false
;(valid? SAMPLE-m 5 3) = false
;(valid? SAMPLE-m 3 5) = false  



;check: matrix num num player num num num-> matrix element or empty
;m c r p dc dr so-far
(define (check m c r p dc dr so-far)
  (if (valid? m c r)
      (cond [(and (< so-far (sub1 CONNECT))
                  (symbol=? (matrix-ref m c r) p))
             (check m (+ dc c) (+ dr r) p dc dr (add1 so-far))]
            [(and (= so-far (sub1 CONNECT))
                  (symbol=? (matrix-ref m c r) EMPTY))
             (list c r)]
            [else empty])
      empty))

;tests
;(check SAMPLE-m 0 1 BLACK 1 0 0) = (list 4 1)
;(check SAMPLE-m 4 2 WHITE -1 0 0) = (list 0 2)
;(check SAMPLE-m 0 1 BLACK 0 1 0) = empty
;(check SAMPLE-m 0 1 BLACK 0 -1 0) = empty
;(check SAMPLE-m 0 1 BLACK 1 1 0) = empty
;(check SAMPLE-m 0 1 BLACK -1 0 0) = empty


;directions: m c r p -> matrix element or empty
;calls check for each direction on a given element
(define (directions m c r p)
  (filter cons? (list (check m c r p 1 0 0)  ;right
                      (check m c r p -1 0 0) ;left
                      (check m c r p 0 1 0)  ;down
                      (check m c r p 0 -1 0) ;up 
                      (check m c r p 1 1 0)  ;down right
                      (check m c r p 1 -1 0) ;up right
                      (check m c r p -1 1 0) ;down left
                      (check m c r p -1 -1 0);up left
                      )))

;test
;(directions SAMPLE-m 0 1 BLACK) = (list (list 4 1))
;(directions SAMPLE-m 2 2 WHITE) = empty
;(directions SAMPLE-m 0 0 WHITE) = empty


;iterate: matrix player -> matrix element or empty
;calls on each element of matrix
(define (iterate m p)
  (fori=-a 0 (matrix-cols m)
         (lambda (i so-far)
           (append (fori=-a 0 (matrix-rows m)
                  (lambda (j so-far)
                    (append (directions m i j p) so-far)) empty) so-far)) empty))
       
;(iterate SAMPLE-m BLACK) = (list (list 4 1))
;(iterate SAMPLE-m WHITE) = (list (list 0 2))

;notme: player -> player
;finds the opposing player

(define (notme p)
  (cond [(symbol=? p WHITE) BLACK]
        [(symbol=? p BLACK) WHITE]))

; tests 
;(notme BLACK) = WHITE
;(notme WHITE) = BLACK


;dumb: matrix player -> matrix element
;return a winning move or block a winning move of the opponent

(define (dumb m p)
  (local [(define moves (iterate m p))]
    (cond [(cons? (first moves)) (first moves)]
          [else (local [(define moves (iterate m (notme p)))]
                  (cond [(cons? (first moves)) (first moves)]
                        [else 'who-the-hell-knows]))])))

;tests
;(dumb SAMPLE-m BLACK) = (list 4 1)
;(dumb SAMPLE-m WHITE) = (list 0 2)


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

(define B 'X)
(define W 'O)
(define E '-)

(define-struct pattern (black white))

(define P1 (make-pattern (list B B B B B) (list W W W W W)))
(define P2 (make-pattern (list E B B B B E) (list E W W W W E)))
(define P3 (make-pattern (list E E B B B E) (list E E W W W E)))
(define P3b (make-pattern (list E B B B E E) (list E W W W E E)))
(define P4 (make-pattern (list E B B E B E) (list E W W E W E)))
(define P4b (make-pattern (list E B E B B E) (list E W E W W E)))
(define P5 (make-pattern (list B B B B E) (list W W W W E)))
(define P5b (make-pattern (list E B B B B) (list E W W W W)))
(define P6 (make-pattern (list E B B B E) (list E W W W E)))
(define P7 (make-pattern (list E B E B E) (list E W E W E)))
(define P8 (make-pattern (list E E B E E) (list E E W E E)))
(define P9 (make-pattern (list B B E B B) (list W W E W W)))
(define P10 (make-pattern (list B E B B B) (list W E W W W)))
(define P10b (make-pattern (list B B B E B) (list W W W E W)))
(define P11 (make-pattern (list E E B B B E E) (list E E W W W E E)))
(define P12 (make-pattern (list E B B E E) (list E W W E E)))
(define P12b (make-pattern (list E E B B E) (list E E W W E)))
(define P13 (make-pattern (list B B B E E) (list W W W E E)))
(define P13b (make-pattern (list E E B B B) (list E E W W W)))
(define P14 (make-pattern (list B B E B E) (list W W E W E)))
(define P14b (make-pattern (list E B E B B) (list E W E W W)))
(define P15 (make-pattern (list B E B B E) (list W E W W E)))
(define P15b (make-pattern (list E B B E B) (list E W W E W)))
(define P16 (make-pattern (list B E B) (list W E W)))
(define P17 (make-pattern (list E B B E) (list E W W E)))



                         


;pattern-check: matrix num num player list-of-alpha num num -> boolean
;see if the pattern matches at the current position

(define (pattern-check m col row pattern dc dr)
  (cond [(empty? pattern) 1]
        [(cons? pattern) 
         (if (symbol=? (matrix-ref m col row) (first pattern))
             (pattern-check m (+ col dc) (+ row dr) (rest pattern) dc dr)
             0)
         ]))


; tests
;(pattern-check SAMPLE-m 1 1 '(X X X -) 1 0) = true
;(pattern-check SAMPLE-m 1 2 '(X X X -) 1 0) = false
;(pattern-check SAMPLE-m 1 1 '(X - X -) 1 0) = false


;directions: matrix num num pattern -> matrix element or empty
;calls check for each direction on a given element

(define (directions m c r p pl)
  (local [(define enough-cols-left? (<= pl (add1 c)))
          (define enough-cols-right? (<= pl (- (matrix-cols m) c)))
          (define enough-rows? (<= pl (- (matrix-rows m) r)))]
    (+ (if enough-cols-right?
           (pattern-check m c r p 1 0)  ;right
           0)
       (if enough-rows?
           (pattern-check m c r p 0 1)  ;down
           0)
       (if (and enough-cols-right? enough-rows?)
           (pattern-check m c r p 1 1)  ;down right
           0)
       (if (and enough-cols-left? enough-rows?)
           (pattern-check m c r p -1 1) ;down left
           0))))


;tests
;(directions SAMPLE-m 0 1 (pattern-black PATTERN8))


;iterate: matrix pattern -> matrix element or empty
;calls on each element of matrix
(define (iterate m p pl)
  (fori=-a 0 (matrix-cols m)
         (lambda (i so-far)
           (+ (fori=-a 0 (matrix-rows m)
                  (lambda (j so-far)
                    (+ (if (symbol=? (matrix-ref m i j) (first p))
                           (directions m i j p pl)
                           0) so-far)) 0) so-far)) 0))

(define (pattern-length p)
  (length (pattern-black p)))

;pick-pattern

(define (pick-pattern pttrn plyr)
  (cond [(symbol=? plyr BLACK) (pattern-black pttrn)]
        [(symbol=? plyr WHITE) (pattern-white pttrn)]))

;(iterate SAMPLE-m (pattern-black PATTERN8))


(define (valuation n factor floor ceiling)
  (min ceiling (+ (* (sub1 n) factor) floor)))



(define (win-this-move? m p)
  (positive? (iterate m (pick-pattern P1 p) (pattern-length P1))))

(define (count-losses-next-move m p)
  (+ (iterate m (pick-pattern P5 (notme p)) (pattern-length P5))
     (iterate m (pick-pattern P5b (notme p)) (pattern-length P5b))
     (iterate m (pick-pattern P9 (notme p)) (pattern-length P9))
     (iterate m (pick-pattern P10 (notme p)) (pattern-length P10))
     (iterate m (pick-pattern P10b (notme p)) (pattern-length P10b))))

(define (assured-win? m p)
  (or
   (positive? (iterate m (pick-pattern P2 p) (pattern-length P2)))
   (< 1 (+ (iterate m (pick-pattern P5 p) (pattern-length P5))
           (iterate m (pick-pattern P5b p) (pattern-length P5b))))))
  
;   (< 1 (+ (iterate m (pick-pattern P11 p) (pattern-length P11))
;           (iterate m (pick-pattern P4 p) (pattern-length P4))
;           (iterate m (pick-pattern P4b p) (pattern-length P4b))))


(define (assured-loss? m p)
  (positive? (+ (iterate m (pick-pattern P3 (notme p)) (pattern-length P3))
                (iterate m (pick-pattern P3b (notme p)) (pattern-length P3b))
                (iterate m (pick-pattern P4 (notme p)) (pattern-length P4))
                (iterate m (pick-pattern P4b (notme p)) (pattern-length P4b)))))

(define (chances-to-force m p)
  (+ (iterate m (pick-pattern P11 p) (pattern-length P11))
     (iterate m (pick-pattern P4 p) (pattern-length P4))
     (iterate m (pick-pattern P4b p) (pattern-length P4b))))

(define (count-threes m p)
  (+ (iterate m (pick-pattern P13 p) (pattern-length P13))
     (iterate m (pick-pattern P13b p) (pattern-length P13b))))
;     (iterate m (pick-pattern P14 p) (pattern-length P14))
;     (iterate m (pick-pattern P14b p) (pattern-length P14b))
;     (iterate m (pick-pattern P15 p) (pattern-length P15))
;     (iterate m (pick-pattern P15b p) (pattern-length P15b))))



(define (count-twos m p)
  (+ (iterate m (pick-pattern P16 p) (pattern-length P16))
     (iterate m (pick-pattern P12 p) (pattern-length P12))
     (iterate m (pick-pattern P12b p) (pattern-length P12b))))


(define (count-ones m p)
  (iterate m (pick-pattern P8 p) (pattern-length P8)))

(define (negative n)
  (* -1 n))


(define (static-board-evaluation m p)
    (cond [(win-this-move? m p) +1.0]
          [else (local [(define lsnm (count-losses-next-move m p))]
                  (cond [(positive? lsnm) (negative (valuation lsnm 0.002 0.95 1.0))]
                        [(assured-win? m p) +0.9]
                        [(assured-loss? m p) -0.9]
                        [else 
                         (local [(define ctf (chances-to-force m p))]
                           (cond 
                             [(> ctf 1) +0.8]
                   
                             [else (local [(define your-twos (count-twos m (notme p)))
                                           (define your-threes (count-threes m (notme p)))
                                           (define your-twos-and-threes (+ your-twos your-threes))]
                                     (cond [(positive? your-twos-and-threes) (negative (valuation your-twos-and-threes 0.002 0.6 0.7))]
                                           [(= ctf 1) +0.55] ; be slightly risky (0.7 would make it really risky)
                                           [else (local [(define my-twos (count-twos m p))]
                                                   (cond [(positive? my-twos) (valuation my-twos 0.002 0.4 0.5)]
                                                         [else (local [(define my-ones (count-ones m p))
                                                                       (define your-ones (count-ones m (notme p)))]
                                                                 (cond [(> my-ones your-ones) (valuation my-ones 0.002 0.2 0.3)]
                                                                       [(< my-ones your-ones) (negative (valuation your-ones 0.002 0.2 0.3))]
                                                                       [else 0]))]))]))]))]))]))
 
;Tests
;(static-board-evaluation SAMPLE-m BLACK)
;(static-board-evaluation SAMPLE-m WHITE)

(define (occupied? s)
  (or (symbol=? s BLACK) (symbol=? s WHITE)))

(define (matrix-set-if-valid! m c r val)
  (if (valid? m c r)
      (matrix-set! m c r val)
      (void)))

(define (moves m)
  (local [(define move-matrix (make-matrix (matrix-cols m) (matrix-rows m) false))]
    (begin
      (fori= 0 (matrix-cols m) 1
             (lambda (c)
               (fori= 0 (matrix-rows m) 1
                      (lambda (r)
                        (if (occupied? (matrix-ref m c r))
                            (begin (matrix-set! move-matrix c r true)
                                   (matrix-set-if-valid! move-matrix (add1 c) (sub1 r) true)
                                   (matrix-set-if-valid! move-matrix (add1 c) r true)
                                   (matrix-set-if-valid! move-matrix (add1 c) (add1 r) true)
                                   (matrix-set-if-valid! move-matrix c (sub1 r) true)
                                   (matrix-set-if-valid! move-matrix c (add1 r) true)
                                   (matrix-set-if-valid! move-matrix (sub1 c) (sub1 r) true)
                                   (matrix-set-if-valid! move-matrix (sub1 c) r true)
                                   (matrix-set-if-valid! move-matrix (sub1 c) (add1 r) true))
                            (void))))))
      move-matrix)))

; enough-time? number -> boolean
; Purpose: To determine whether there is a enough time left

(define (enough-time? timestamp)
  (local [(define TIME_ALLOWED 20000)
          (define TIME_ERROR 1000)]
    (< (abs (- timestamp (current-milliseconds))) (- TIME_ALLOWED TIME_ERROR))))


;Tests
(enough-time? (current-milliseconds)) = false
(enough-time? 0) = true

; find-move: 

(define (find-move board plyr timestamp)
  (local [(define move-matrix (moves board))
          (define maximum -inf.0)
          (define move (list (floor (/ (matrix-cols board) 2))
                             (floor (/ (matrix-rows board) 2))))] ; default move
    (begin
      (fori= 0 (matrix-cols board) 1
             (lambda (i)
               (fori= 0 (matrix-rows board) 1
                      (lambda (j)
                        (if (enough-time? timestamp)
                            (if (and (symbol=? (matrix-ref board i j) EMPTY)
                                     (matrix-ref move-matrix i j))
                                (local [(define save (matrix-ref board i j))]
                                  (begin
                                    (matrix-set! board i j plyr)
                                    (local [(define value (static-board-evaluation board plyr))]
                                      (if (> value maximum)
                                          (begin
                                            (set! maximum value)
                                            (set! move (list i j)))
                                          (void)))
                                    (matrix-set! board i j save)))
                                (void))
                            (void))))))
      (list maximum move))))

           
;(define BOARD20x20 '((- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)
;                     (- - - - - - - - - - - - - - - - - - - -)))

;(define BOARD10x10 '((- - - - - - - - - -)
;                     (- - - - - - - - - -)
;                     (- - - - - - - - - -)
;                     (- - - - - - - - - -)
;                     (- - - - - - - - - -)
;                     (- - - - - - - - - -)
;                     (- - - - - - - - - -)
;                     (- - - - - - - - - -)
;                     (- - - - - - - - - -)
;                     (- - - - - - - - - -)))

;(define BOARD '((- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - X X X X - - - - - - - - - -)
;                (- - - - - - - O X O - - - - - - - - - -)
;                (- - - - - O - X O - - - - - - - - - - -)
;                (- - - - - - O O - O - - - - - - - - - -)
;                (- - - - - - X - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)
;                (- - - - - - - - - - - - - - - - - - - -)))

;(define BOARD7x7 '((- - - - - - -)
;                   (- - - - - - -)
;                   (- - O - O - -)
;                   (- - - O - - -)
;                   (- - O - O - -)
;                   (- O - - - O -)
;                   (- - - - - - -)))


; Let's play baby!

;(define BOARD-m (convert BOARD))
(define BOARD-m (convert (read)))

;(time (find-move BOARD-m BLACK (current-milliseconds)))
(printf "~s~n" (second (find-move BOARD-m BLACK (current-milliseconds))))