; ★ CSC 104 Fall 2018 Project 1 ★
; ================================

; ★★★ READ EVERYTHING CAREFULLY, IN ORDER ★★★

; This program will animate the creation of a maze, visualized as cutting a path through
;  a grid of trees.

; The program has five sections:
;   Drawing the Maze (40% of mark)
;   Maze Generation Algorithm (40% of mark)
;   Moving Kat (10% of mark)
;   Path Finding (10% of mark)
;   Launch the Animation

; The first four sections contain places where you need to write or fix a check-expect,
;  or fix a function. Those places are marked with a ‘★’.

; When you start working on a function (or a check-expect for it), uncomment any check-expects
;  for that function that we have already provided.

; Each function that you need to fix has an incorrect implementation. Sometimes the incorrect
;  implementation is a hint, but most of the time it is there just so that the program is likely
;  to run without crashing: run this program now, and a window should appear with a purple
;  background and a small cat girl figure. When you complete a section, some new meaningful
;  behaviour will be noticeable.

; The Grid
; --------
; The grid of trees has dimensions size × size, where the size is set by the following variable:
(define size 10)

; For example, if the size were 3, the initial grid would be 3 × 3, and be drawn as:
#;.

; We'll refer to a position in the grid as a “point” in the grid.
; There are nine points in that example grid.

; We'll assume the size has been set to a number that's at least three, since some of the
;  check-expects below rely on that.

; Representation
; --------------
; A point in the grid has an X co-ordinate and a Y co-ordinate.
; The top-left point in the grid is at X = 0, Y = 0.
; The bottom-right point in the grid is at X = size - 1, Y = size - 1
;  (computer graphics usually treats downward as the positive y direction).

; We'll represent a point as a list of two integers.

; When making a list representing a point, use the following alias to make the intent clear:
(define point list)

; When extracting the first and second element of a point, use the following aliases:
(define X first)
(define Y second)

; A cleared part of the grid will be represented as a list of points.

; For example, the following represents a small “L” shaped path in the grid:
#;(list (point 0 1)
        (point 0 0)
        (point 1 2)
        (point 0 2))
; If the size of the grid were 3, that would be drawn as:
#;.


; Drawing The Maze
; ================
(define barrier (render (scale  . 1/4)))

; floor-piece : function color → image
; ------------------------------------
; This function produces a shape of a particular color, with the same dimensions as ‘barrier’.

#;(check-expect (floor-piece rectangle "brown") .)
#;(check-expect (floor-piece ellipse "orange") .)

; ★ Write a Partial (or Full) Design check-expect for floor-piece:
(check-expect (floor-piece rectangle "brown") .)
(check-expect (floor-piece ellipse "orange") .)

; ★ Fix floor-piece:
(define
  (floor-piece shape color)
  (shape 25 28 "solid" color))
(define ground (floor-piece rectangle "brown"))
(define invisible (floor-piece rectangle "transparent"))
(define highlight (overlay (shrink (floor-piece ellipse (list 100 100 0 25)))
                           invisible))


; xs : list-of-points → list-of-numbers
; -------------------------------------
; This function extracts the X co-ordinates of a list of points.

#;(check-expect (xs (list (point 1 2) (point 3 4) (point 1 5)))
                (list 1 3 1))

; ★ Write a Partial (or Full) Design check-expect for xs:
(check-expect (xs (list (point 1 2) (point 3 4) (point 1 5)))
                (list 1 3 1))

; ★ Fix xs:
(define (xs points)
  (map X points))

; row : number list-of-points → list-of-points
; --------------------------------------------
; This function extracts the points that have a particular Y co-ordinate, from a list of points.

#;(check-expect (row (list (point 1 2) (point 3 4) (point 2 2)) 2)
                (list (point 1 2) #;(point 3 4) (point 2 2)))

#;(check-expect (row (list (point 1 2) (point 3 4) (point 2 2)) 2)
                (local [(define (y? a-point)
                          (= (Y a-point) 2))]
                  (list (point 1 2) #;(point 3 4) (point 2 2))))

; ★ Write a Full Design check-expect for row:
(check-expect (row (list (point 1 2) (point 3 4) (point 2 2)) 2)
                (list (point 1 2) #;(point 3 4) (point 2 2)))
(check-expect (row (list (point 1 2) (point 3 4) (point 2 2)) 2)
                (local [(define (y? a-point)
                          (= (Y a-point) 2))]
                  (list (point 1 2) #;(point 3 4) (point 2 2))))

; ★ Fix row:
(define (row points y)
    (local [(define (y? a-point)
                  (= (Y a-point) y))]
      (sift y? points)))

; xs->image : number list-of-numbers image image → image
; -----------------------------------------------------
; This function draws a row of foreground and background images, with a given total number of images,
;  and a list of which images (numbered left to right as 0, 1, 2, ...) are the foreground ones.

#;(check-expect (xs->image 4 (list 2 0) ground barrier) .)
#;(check-expect (xs->image 4 (list 2 0) ground barrier) (beside ground barrier ground barrier))
#;(check-expect (xs->image 4 (list 2 0) ground barrier)
                (local [(define (represent x)
                          (if [(element? x (list 2 0)) ground]
                              [else barrier]))]
                  (beside (represent 0) (represent 1) (represent 2) (represent 3))))

; ★ Write a Fuller (or Full) Design check-expect for xs->image:
(check-expect (xs->image 4 (list 2 0) ground barrier) .)
(check-expect (xs->image 4 (list 2 0) ground barrier) (beside ground barrier ground barrier))
(check-expect (xs->image 4 (list 2 0) ground barrier)
                (local [(define (represent x)
                          (if [(element? x (list 2 0)) ground]
                              [else barrier]))]
                  (beside (represent 0) (represent 1) (represent 2) (represent 3))))

; ★ Fix xs->image:
(define (xs->image total some-xs foreground background)
                (local [(define (represent x)
                          (if [(element? x some-xs) foreground]
                              [else background]))](apply beside(map represent(range 0 total 1)))))

; points->image : number list-of-points image image → image
; ---------------------------------------------------------
; This function takes a list of points and draws them using a foreground image, filling in
;  the rest of the grid with a background image.

(define (points->image a-size points foreground background)
  (local [(define (row->image y)
            (xs->image a-size (xs (row points y)) foreground background))]
    (apply above (map row->image (range 0 size 1)))))

; draw-all : list-of-points point point → image
; ---------------------------------------------
; This function draws:
;   • the maze
;   • kat at a particular point
;   • the path from kat to a particular point
(define kat (render (scale . 1/4)))

(define (draw-all a-maze kat-point click-point)
  (align-overlay "left" "top"
                 (above (rectangle 0 (* (height barrier) (Y kat-point)) "solid" "transparent")
                        (beside (rectangle (* (width barrier) (X kat-point)) 0 "solid" "transparent")
                                kat))
                 (overlay (points->image size (path a-maze kat-point click-point) highlight invisible)
                          (points->image size a-maze invisible barrier)
                          (scale ground size))))

; Test The Functionality
; ----------------------
; Run the program now, and you should see a forest of trees, with a small L-shaped path.
; Pressing keys should move kat to the right.
; Clicking in the L-shaped path should highlight the point you clicked with an ellipse.

; Maze Generation Algorithm
; =========================

; The maze (cleared path) will start off containing a single point, for example:

#;(list (point 0 0))
 
; Then we'll repeat the following process to grow the maze, adding points to that list:
;
;   #1. Randomly pick a point that is already in the maze.
;   #2. Randomly pick a point from the four points above, below, left, and right
;        of the point from #1.
;   #3. If that point is:
;         • not already in the maze, and
;         • within the bounds of the grid, and
;         • doesn't connect two points already in the maze
;       then add that point to the maze.

; The functions below implement that algorithm.

; in-grid? : point → boolean
; --------------------------
; This function determines whether a point (a list containing two integers) is actually
;  within the grid: are the co-ordinates of the point non-negative and at most size - 1 ?

#;(check-expect (in-grid? (point -1 0)) #false)
#;(check-expect (in-grid? (point 3 size)) #false)
#;(check-expect (in-grid? (point 1 2)) #true)
#;(check-expect (in-grid? (point (- size 1) 0)) #true)

; ★ Turn the following check-expects into Partial (or Full) Designs, by making explicit
;     (at least) the main reason the function produces #false in each case:
#;(check-expect (in-grid? (point -1 0)) #false)
#;(check-expect (in-grid? (point 3 size)) #false)

; ★ Write a Full Design check-expect for in-grid? (if your previous ones weren't Full Designs):
(check-expect (in-grid? (point -1 0))
                (if [(< -1 0) #false]
        [(< 0 0) #false]
        [(> (- size -1)0) #true]
        [(> (- size 0)0) #true]
        [(< -1 size) #true]
        [(< 0 size) #true]
        [(< -1 0) #false]
        [(< 0 0) #false]
        [else #false]))

; ★ Fix in-grid?:
(define (in-grid? a-point)
    (if [(< (X a-point) 0) #false]
        [(< (Y a-point) 0) #false]
        [(> (- size (X a-point))0) #true]
        [(> (- size (Y a-point))0) #true]
        [(< (X a-point) size) #true]
        [(< (Y a-point) size) #true]
        [else #false]))

; neighbours : point → list-of-points
; -----------------------------------
; This function produces a list of the four points above, below, left, and right of a point.

#;(check-expect (neighbours (point 3 7))
                (local [(define x 3)
                        (define y 7)]
                  (list (point x 6)
                        (point x 8)
                        (point 2 y)
                        (point 4 y))))

; ★ Turn the following check-expect into a Fuller (or Full) Design:
#;(check-expect (neighbours (point 3 7))
                (local [(define x 3)
                        (define y 7)]
                  (list (point x 6)
                        (point x 8)
                        (point 2 y)
                        (point 4 y))))

; ★ Write a Full Design check-expect for neighbours (if your previous one wasn't a Full Design):


; ★ Fix ‘neighbours’:
(define (neighbours a-point)
    (local [(define x (X a-point))
            (define y (Y a-point))]
      (list (point x (- y 1 ))
             (point x (+ y 1))
             (point (- x 1) y)
             (point (+ x 1)y))))

; intersection : list list → list
; -------------------------------
; This function takes two lists and produces the list of elements from the first list
;  that are also in the second list.

#;(check-expect (intersection (list "ant" "bee" "cat" "bee" "dog") (list "dog" "eel" "bee"))
                (list "bee" "bee" "dog"))

; ★ Fix the following check-expect, and make it a Full Design (hint: see the function ‘row’):
#;(check-expect (intersection (list "ant" "bee" "cat" "bee" "dog") (list "dog" "eel" "bee"))
                (local [(define (in-list-2? e) #true)]
                  (list #;"ant" "bee" #;"cat" "bee" "dog")))

; ★ Fix intersection:
(define (intersection list-1 list-2)
  (local [(define e list-1)
          (define (in-list-2? e)
            (element? e list-2))]
    (sift in-list-2? list-1)))

; random-element : list → any
; ---------------------------
; This function produces an element randomly chosen from a non-empty list.

#;(check-expect (<= 0 (random-element (range 0 1000 1)) 999)
                #true)
#;(check-expect (= (random-element (range 0 1000 1))
                   (random-element (range 0 1000 1)))
                ; Probably:
                #false)
#;(check-expect (element? (random-element (list "programming" "is" "fun"))
                          (list "programming" "is" "fun"))
                #true)

; ★ Fix random-element:
(define (random-element list1)
    (element list1 (random (length list1))))

; random-neighbour : point → point
; --------------------------------
; This function produces a random neighbour of a point.

#;(check-expect (element? (random-neighbour (point 123 104)) (list (point 123 103)
                                                                   (point 123 105)
                                                                   (point 122 104)
                                                                   (point 124 104)))
                #true)

; ★ Fix random-neighbour:
(define (random-neighbour a-point)
    (random-element (neighbours a-point)))

; bridge? : point list-of-points → boolean
; ----------------------------------------
; This function determines whether adding a point to a list-of-points creates a “bridge”:
;  does it connect two or more points in the list-of-points?

#;(check-expect (bridge? (point 3 4)
                         (list (point 1 2)
                               (point 3 3)   ; one of the neighbours of (point 3 4)
                               (point 4 5)
                               (point 2 4))) ; one of the neighbours of (point 3 4))
                ; (point 3 4) touches, so connects, (point 3 3) and (point 2 4)
                #true)

#;(check-expect (bridge? (point 3 4)
                         (list (point 1 2)
                               (point 3 3)
                               (point 4 5)
                               (point 3 2)))
                #false)

#;(check-expect (bridge? (point 3 4)
                         (list (point 1 2)
                               (point 3 3)
                               (point 4 5)
                               (point 2 4)))
                (>= (length (list (list 3 3) #;(list 3 5) (list 2 4) #;(list 4 4)))
                    2))

; ★ Write a Fuller (or Full) Design check-expect:


; ★ Write a Full Design check-expect (if your previous one wasn't a Full Design):


; ★ Fix bridge?:
(define (bridge? a-point points)
    (element? a-point (apply join (map neighbours (join points)))))

; maybe-attach : point list-of-points → list-of-points
; ----------------------------------------------------
; This function checks the three conditions mentioned in #3 of the maze generation algorithm,
;  and adds the point to the maze if the three conditions are satisfied, otherwise it just
;  produces the maze unchanged.

#;(check-expect (maybe-attach (point 1 2)
                              (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
                (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))

#;(check-expect (maybe-attach (point -1 2)
                              (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
                (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))

#;(check-expect (maybe-attach (point 1 1)
                              (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
                (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))


#;(check-expect (maybe-attach (point 2 2)
                              (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
                (list (point 2 2) (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
; ★ Write a Partial (or Full) Design check-expect for the case covered by the previous check-expect:


; ★ Fix maybe-attach:
(define (maybe-attach a-point a-maze)
  (if [(same? (and (bridge? a-point a-maze)
              (not(element? a-point a-maze)))
              #true)
       (adjoin a-point a-maze)]
      [else a-maze]))

; try-grow : list-of-points → list-of-points
; ------------------------------------------
; This function tries to grow the maze by maybe attaching a random neighbour of a random point
;  in the maze, trying again if that point doesn't attach, with a small probability of giving up.

(define (try-grow a-maze)
  (local [(define new-maze (maybe-attach (random-neighbour (random-element a-maze)) a-maze))]
    (if [(and (same? a-maze new-maze)
              (positive? (random (squared size))))
         (try-grow a-maze)]
        [else new-maze])))

; The following has a large probability of being correct:
#;(check-expect (local [(define small-maze (try-grow (list (point 0 0))))]
                  (and (= (length small-maze) 2)
                       (element? (point 0 0) small-maze)
                       (or (element? (point 0 1) small-maze)
                           (element? (point 1 0) small-maze))))
                #true)

; Unless size is small, the following produces a list of ten mazes, growing by one point each time:
#;(repeats try-grow (list (point 0 0)) 10)


; Moving Kat Around
; =================
; This part lets you move kat around the maze, by pressing the arrow keys on your keyboard.
; The big-bang expression at the end of the program is set up to use the function move.

; move : point text list-of-points → point
; ----------------------------------------
; This function helps react to pressing a key on the keyboard.
; It takes a point, a text representing a key, and a maze.
; If the text represents one of the arrow keys, and the point in that direction is in the maze,
;  then produce that point, otherwise produce the original point.

#;(check-expect (move (point 0 2) "up"
                      (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
                (point 0 1))

#;(check-expect (move (point 0 2) "down"
                      (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
                (point 0 2))

#;(check-expect (move (point 0 2) "left"
                      (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
                (point 0 2))

#;(check-expect (move (point 0 2) "right"
                      (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
                (point 1 2))

#;(check-expect (move (point 0 2) "cat"
                      (list (point 0 1) (point 0 0) (point 1 2) (point 0 2)))
                (point 0 2))

; ★ Write Partial Design check-expects for the two check-expect examples above
;    with "up" and "right":


; ★ Fix move:
(define (move a-point key maze)
  (local[(define(maze? a-point maze)(element? a-point maze))]
  (if[(and(same? key "right")(maze?(point(+(X a-point) 1)(Y a-point))maze))(point (+ (X a-point) 1)(Y a-point))]
     [(and(same? key "left")(maze?(point(-(X a-point) 1)(Y a-point))maze))(point (- (X a-point) 1)(Y a-point))]
     [(and(same? key "up")(maze?(point (X a-point) (- (Y a-point)1))maze))(point (+ (X a-point) 1)(Y a-point))]
     [(and(same? key "down")(maze?(point(X a-point) (+ (Y a-point)1))maze))(point (+ (X a-point) 1)(Y a-point))]
     [else (point (X a-point)(Y a-point))])))

; Path Finding
; ============
; This part requires is considerably more difficult than the rest of the project.

; The big-bang expression is set up to keep track of the last point in the grid that was clicked
;  with the mouse, via the function click-point. And draw-all draws the path from that point to
;  kat, via the function path.

; click-point: point number number text → point
; ---------------------------------------------
; This function helps react to clicking on the grid.
; It takes a point representing the last place the mouse was clicked, the new click's co-ordinates,
;  and a text describing whether it's in fact a mouse click (versus, for example, a drag action).
; If it's the right type of action, the point in the grid representing the mouse location is produced,
;  otherwise the previous point is produced.
(define (click-point previous-point x y type)
  (if [(same? type "button-down") (point (quotient x (width barrier))
                                         (quotient y (height barrier)))]
      [else previous-point]))

; path : list-of-points point point
; ---------------------------------
; For any two points in the generated maze, there is exactly one non-backtracking path connecting
;  the two points. The following describes a function to find such a connecting path. It works more
;  generally on parts of mazes, since that turns out to allow a simpler recursive implementation.

#;(path sub-maze from to)
; For part of a maze sub-maze, and a point end-point within it, with at most one path from
;  start-point to end-point within sub-maze, produce the list of points connecting start-point
;  to end-point. If there is no such path, produce the empty list.

; The approach:
;   If start-point and end-point are the same point, the path contains exactly that point.
;   Otherwise, if start-point is in the sub-maze, then the path, if there is one, continues from
;    one of the neighbours and is within the partial maze with start-point removed. If one of
;    those four neighbours produces a (non-empty) path then adding start-point to that path
;    produces the whole path.
;   Otherwise, we know already that there is no path.

; One of the simple cases:
#;(check-expect (path (list (point 0 0) (point 0 1) (point 1 1) (point 1 2))
                      (point 0 1)
                      (point 0 1))
                (list (point 0 1)))

; Another kind of simple case:
#;(check-expect (path (list (point 0 0) (point 0 1) (point 1 1) (point 1 2))
                      (point 1 0)
                      (point 0 1))
                (list))

; When there's a path from one of the neighbours:
#;(check-expect (path (list (point 0 0) (point 0 1) (point 1 1) (point 1 2))
                      (point 0 1)
                      (point 1 2))
                (local [(define (rest-of-path a-neighbour)
                          (path (list (point 0 0) (point 1 1) (point 1 2))
                                a-neighbour
                                (point 1 2)))
                        (define maybe-rest-of-path
                          (join (rest-of-path (point  0 0))
                                (rest-of-path (point  0 2))
                                (rest-of-path (point -1 1))
                                (rest-of-path (point  1 1))))]
                  (adjoin (point 0 1) maybe-rest-of-path)))

; When there's no path from one of the neighbours:
#;(check-expect (path (list (point 0 0) (point 0 1) #;(point 1 1) (point 1 2))
                      (point 0 1)
                      (point 1 2))
                (local [(define (rest-of-path a-neighbour)
                          (path (list (point 0 0) (point 1 2))
                                a-neighbour
                                (point 1 2)))
                        (define maybe-rest-of-path
                          (join (rest-of-path (point  0 0))
                                (rest-of-path (point  0 2))
                                (rest-of-path (point -1 1))
                                (rest-of-path (point  1 1))))]
                  (list)))

; ★ Write Full Design check-expects for the two previous non-simple cases:


; ★ Fix path:
(define (path sub-maze start-point end-point)
  (local[(define(rest-of-path a-neighbour)(path (remove start-point sub-maze)a-neighbour end-point))
         (define (maybe-rest-of-path x-point)
           (apply join (map rest-of-path (neighbours x-point))))]
    (if[(not (and (element? start-point sub-maze) (element? end-point sub-maze))) (list)]
       [(same? start-point end-point) (list start-point)]
       [(>(length (maybe-rest-of-path start-point)) 0) (adjoin start-point (maybe-rest-of-path start-point))]
       [else (list)])))

; Launch the Animation
; ====================

(define make-state list)
(define maze first)
(define kat-point second)
(define path-point third)

(define (key state a-key)
  (make-state (maze state) (move (kat-point state) a-key (maze state)) (path-point state)))

(define (draw state)
  (apply draw-all state))

(define (tick state)
  (make-state (try-grow (maze state)) (kat-point state) (path-point state)))

(define (click state x y type)
  (make-state (maze state) (kat-point state) (click-point (path-point state) x y type)))

(big-bang (make-state (list (point 0 0))
                      (point 0 0)
                      (point 0 0))
  [to-draw draw]
  [on-tick tick]
  [on-mouse click]
  [on-key key])