#lang plai-typed

;; Possible robot steps:
;;  move forward n
;;  turn left
;;  turn right
(define-type Step
  [move-forward (n-steps : number)]
  [turn-left]
  [turn-right]
  [flip-coin (p1 : (listof Step)) (p2 : (listof Step))])

;A program is either empty or it's a cons of a step
;onto a program

;; program-how-far : program -> number
;; reports the maximum distance that a program will move
(define (program-how-far [program : (listof Step)]) : number
  (cond
    [(empty? program) 0]
    [else (+ (how-far(first program))
             (program-how-far(rest program)))]))

;(define (program-how-far [program : (listof Step)]) : number
;  (cond
;    [(empty? program) ...]
;    [else ...(how-far(first program))... ...(program-how-far(rest program))...]))

(module+ test
  (test (program-how-far empty) 0)
  (test (program-how-far (cons (turn-left) empty)) 0))

;; ----------------------------------------

;; reports the maximum distance that a step will move
(define (how-far [step : Step]) : number
  (type-case Step step
    [move-forward (n-steps) n-steps]
    [turn-left () 0]
    [turn-right () 0]
    [flip-coin(p1 p2) (max (program-how-far p1) (program-how-far p2))]))

;(define (how-far [step : Step]) : number
;  (type-case Step step
;    [move-forward (n-steps) n-steps ...]
;    [turn-left ()...]
;    [turn-right ()...]
;    [flip-coin(p1 p2) ...(program-how-far p1)...(program-how-far p2)...]))

(module+ test
  (test (how-far (move-forward 10)) 10)
  (test (how-far (turn-left)) 0)
  (test (how-far (turn-right)) 0)
  (test (how-far (flip-coin empty empty)) 0)
  (test (how-far (flip-coin (cons (move-forward 1) (cons(turn-left) empty)) empty)) 1))

;; ----------------------------------------

;; check whether `step` definitely turns
;; (template is as above)
(define (is-turn [step : Step]) : boolean
  (type-case Step step
    [move-forward (n-steps) false]
    [turn-left () true]
    [turn-right () true]
    [flip-coin (p1 p2) (and (any-turns p1) (any-turns p2))]))

(module+ test
  (test (is-turn (move-forward 1)) #f)
  (test (is-turn (turn-left)) #t)
  (test (is-turn (turn-right)) #t)
  (test (is-turn (flip-coin empty empty)) #f)
  (test (is-turn (flip-coin empty (cons (turn-left) empty))) #f)
  (test (is-turn (flip-coin (cons (turn-right) empty) (cons (turn-left) empty))) #t))

;; check whether a program definitely turns
(define (any-turns [program : (listof Step)]) : boolean
  (cond
    [(empty? program) false]
    [else (or (is-turn (first program))
              (any-turns(rest program)))]))

(module+ test
  (test (any-turns empty) #f)
  (test (any-turns (cons (turn-left) empty)) #t)
  (test (any-turns (cons (move-forward 5) (cons (turn-left) empty))) #t)
  (test (any-turns (cons (move-forward 5) empty)) #f))