;;; Scheme Recursive Art Contest Entry
;;;
;;; Please do not include your name or personal info in this file.
;;;
;;; Title: Penrose Stars
;;;
;;; Description:
;;;    If you invert this
;;;    picture, you get a christmas-
;;;    themed wrapping paper.

; NOTES:
; 1. https://en.wikipedia.org/wiki/Penrose_tiling
; 2. It's slow. Really slow. Go to line 130 and change the 7 to something
;    <= 4 if you want to test this yourself.
; 3. I had to cut down the number of tokens, so things aren't as straightforward
;    as they're supposed to be, and a few things that I'd rather not hardcode
;    are hardcoded (such as colors). 
; 4. By changing the subdivide algorithm, specifically lines 100 through 108, 
;    you will end up with a different penrose tilings. Somewhere online there
;    should be algorithms if you need to find them.
; 5. If you change this file the line numbers will also change.

; TODOs:
; X. Reduce tokens to < 256 (done... for now)
; 2. Reduce (if possible) storage to linear space, if possible
;        the only way this is possible is lazy evaluation of functions
;        in particular, subdivide_triangles needs to be lazily evaluated.
;    (right now the program can get unresponsive if subdivide_level > 6)

(define (draw)
  ; a triangle is a list (a b c color), where a -> b -> c is its border
  ; and c is its fill color; a, b, c are coordinates: (x y)
  (define (a triangle)
    (car triangle))
  (define (b triangle)
    (cadr triangle))
  (define (c triangle)
    (cadr (cdr triangle)))
  (define (col triangle)
    (cadr (cdr (cdr triangle))))
  
  ; unpacks a coordinate (x y) and sets turtle position
  (define (setcoordinates c)
    (setposition (car c) (cadr c)))
  
  ; draws a triangle; fill first, border second
  (define (draw_triangle triangle)
    (penup)
    (setcoordinates (a triangle))
    (begin_fill)
    (setcoordinates (b triangle))
    (setcoordinates (c triangle))
    (setcoordinates (a triangle))
    (color (col triangle))
    (end_fill)
    ; for borders. uncomment if you want borders (+10 tokens)
    ;(color "#01bcb3")
    ;(pendown)
    ;(setcoordinates (b triangle))
    ;(setcoordinates (c triangle))
    ;(penup)
    )

  ; draws a list of triangles; tail recursive
  (define (draw_triangles triangles)
    (if (pair? triangles)
        ((draw_triangle (car triangles))
         (draw_triangles (cdr triangles)))))
  
  ; cadr
  (define (cadr li)
    (car (cdr li)))
  
  ; generates a "wheel": 10 triangles of the same color connected together
  ; like a pizza; this wheel is subdivided to create a penrose visual
  (define (generate_wheel scale rem last)
    (if (< rem 0)
        nil
        (let ((key (* rem 0.628318530717958647692528676655900576839433879875021164194)))
          ; that thing is pi/5, by the way; this is the only time we need to use pi
          (let ((current (list (* scale (sin key))
                               (* scale (cos key)))))
            (cons (if (even? rem)
                      (list current '(0 0) last "#21ddd4") 
                      (list last '(0 0) current "#21ddd4"))
                  (generate_wheel scale (- rem 1) current))))))
  
  ; finds the golden ratio split (0.618/0.382 split) given two points
  (define (golden_ratio_split beginning end)
    (let ((phi 1.618033988749894848204586834365638117720309179805762862135))
      (list (+ (car beginning) (/ (- (car end) (car beginning)) phi))
            (+ (cadr beginning) (/ (- (cadr end) (cadr beginning)) phi)))))
    
  ; subdivides a triangle into a list of 2 or 3 new triangles
  (define (subdivide triangle)
    (let ((a (a triangle))
          (b (b triangle))
          (c (c triangle)))
      (let ((p (golden_ratio_split b c))
            (q (golden_ratio_split c b))
            (r (golden_ratio_split c a)))
        (if (equal? (col triangle) "#21ddd4")
            (list (list c a p "#21ddd4")
                  (list b p a "#44fcf3"))
            (list (list b r a "#44fcf3")
                  (list c q r "#44fcf3")
                  (list b r q "#21ddd4"))))))
  
  ; subdivides a list of triangles; tail recursive
  (define (subdivide_triangles triangles result)
    (if (null? triangles)
        result
        (subdivide_triangles (cdr triangles) 
                             (append result (subdivide (car triangles))))))
  
  ; subdivides a wheel many times to obtain a penrose visual; you must pass the 
  ; result of generate_wheel as init; note that different visuals will be 
  ; generated depending on whether level is even or odd
  (define (subdivide_level level init)
    (if (= level 0)
        init
        (subdivide_level (- level 1) (subdivide_triangles init '()))))
  
  ; a scale that will be used as radius of the penrose visual. 
  (define effective_size (* 0.735294 (screen_width)))
  
  ; we finally start drawing
  (speed 0)
  (draw_triangles (subdivide_level 7 (generate_wheel effective_size 9 (list 0 effective_size))))
  (hideturtle))

; Please leave this last line alone.  You may add additional procedures above
; this line.
(draw)