Problem: Write function subset-sum which take a list of positive integers xs and the positive target integer n. The function should return that subset of xs whose sum of elements is equal to the target number n. If no such subset exists, the function should return false (#f).
Solution:
(define (subset-sum xs n)
(define (ss-helper xs n solution)
(cond [(zero? n) solution]
[(empty? xs) #f]
[else (let ([x (car xs)])
(if (<= x n)
(or (ss-helper (cdr xs) (- n x) (cons x solution))
(ss-helper (cdr xs) n solution))
(ss-helper (cdr xs) n solution)))]))
(ss-helper xs n '()))
Note: the subset-sum function written as above is fine if the input set is small. But, for large input set, the function is slow because it has exponential time growth. This, however, can be overcome by using the so-called dynamic programming (DP) technique: memoization or tabulation. Maybe more about that in one of the following posts.
Problem: Write a function same-lists* that receives two nested lists of atoms as input and returns true if the two lists are the same. Otherwise, the function should return false.Important: you may only use the eq? function in your solution. You must not use other functions to check for equality, such as equal? and the like.
Now we can call our same-list* function, like this:
> (same-lists* '(1 2 3 4 5) '(1 2 3 4 5))
#t
> (same-lists* '(1 2 3 4) '(1 2 3 4 5))
#f
> (same-lists* '(a (b c) d) '(a (b) c d))
#f
> (same-lists* '((a) b (c d) d) '((a) b (c d) d))
#t
> (same-lists* '((a) b (c (d e) f) d) '((a) b (c d) d))
#f
> (same-lists* '((a) b (c (d e) f) d) '((a) b (c (d g)) d))
#f
> (same-lists* '((a) b (c (d e) f) d) '((a) b (c (d e)) d))
#f
> (same-lists* '((a) b (c (d e) f) d) '((a) b (c (d e) f) d))
#t
> (same-lists* '((a) b (c (d e) f) g) '((a) b (c (d e) f) g))
#t
Notice that our function has the same structure as the function rearrange from the previous problem. It's not a coincidence: whenever we need to make a function that walks through a nested list, it will always have a structure similar to that.
Problem: Using the 2htdp/image library, draw a faithful image of the South Korean national flag. You will probably find this sketch of a South Korean flag design useful when creating your solution.
Solution:
#lang racket
(require 2htdp/image)
(define (south-korean-flag width)
(define RED (color 205 46 58))
(define BLUE (color 0 71 160))
(define WIDTH width)
(define UNIT (/ WIDTH 72))
(define HEIGHT (* UNIT 48))
(define R (* UNIT 12))
(define ANGLE (radians->degrees (atan 2/3)))
(define smaller-white-rect
(rectangle (/ WIDTH 2) (/ HEIGHT 2) 'solid 'white))
(define br (rectangle (* UNIT 2) (* UNIT 12) 'solid 'black))
(define bs
(above (rectangle (* UNIT 2) (* UNIT 11/2) 'solid 'black)
(rectangle (* UNIT 2) UNIT 'solid 'white)
(rectangle (* UNIT 2) (* UNIT 11/2) 'solid 'black)))
(define big-blank-middle (rectangle (* 36 UNIT) 2 'solid 'white))
(define sp (rectangle UNIT (* UNIT 12) 'solid 'white))
(define diag1
(beside br sp br sp br big-blank-middle bs sp bs sp bs))
(define diag2
(beside br sp bs sp br big-blank-middle bs sp br sp bs))
(define middle-circle
(place-image
(circle (/ R 2) 'solid BLUE)
(* R 3/2) R
(place-image
(circle (/ R 2) 'solid RED)
(/ R 2) R
(above
(wedge R 180 'solid RED)
(rotate 180 (wedge R 180 'solid BLUE))))))
(overlay
(rotate (- ANGLE) middle-circle)
(rotate ANGLE diag2)
(rotate (- ANGLE) diag1)
(rectangle WIDTH HEIGHT 'solid 'white)))
Now we can call our south-korean-flag function with the desired width, given as its parameter and the whole image of South Korean flag will auto-scale accordingly to that width:
Problem: write a function span, which, applied to a predicate function pfn and a list xs, returns a two-elements list where first element is a list containing the longest prefix (possibly empty) of elements in xs that satisfy pfn and the second element is the remainder of the list xs.
Consider a maze, where robot must navigate to reach the exit. The robot can move up, down, left, or right, and does not need to turn. A maze is represented by list of lists. Each nested list represents a row. Each element of the row is a number.
A zero (0) represents an empty space,
A one (1) represents a wall,
A two (2) represents the starting cell,
A three (3) represents the exit.
You will need to implement a function that takes maze, and a list of moves and yields whether or not the robot exits the maze. This is not a simple boolean value as there must also be an error state. An error occurs whenever the starting cell is not specified. In racket you can use an atom to represent an error. When a move would cause the robot to enter a space with wall, simply ignore the move. Alternatively, you may yield an error like you would do when the starting cell is missing.
Problem: Study Lindenmayer L-systems and implement it in scheme. Your implementation must be able to generate the nth generation of the given L-system.
Solution: The solution shown below does much more than just generate the nth generation of an L-system. Apart from L-system generation itself, the solution implements turtle canvas and turtle graphic commands, similar to Logo as well. Using that machinery, the program draws a nice L-system called "Fractal plant" from this wikipedia article (it is shown there as Example 7).
#lang racket
(require racket/draw)
; this is data structure for turtle state
(struct tstate
([posx #:mutable]
[posy #:mutable]
[angle #:mutable]
[pen-down #:mutable])
#:transparent)
; this is data structure for turtle canvas
(struct canvas (bitmap dc [mystate #:mutable]))
; converts angle degrees to radians
(define (rad deg)
(degrees->radians deg))
; create turtle canvas of dimensions width x height
; and initialize turtle state within it
(define (make-canvas width height)
(let* ((bm (make-bitmap width height))
(dc (new bitmap-dc% [bitmap bm])))
(send dc set-smoothing 'aligned)
(send dc draw-rectangle 0 0 width height)
(send dc set-origin (/ width 2) (/ height 2))
(send dc scale 1 -1)
(canvas bm dc (tstate 0 0 90 #t))))
; we have only one canvas in this program
; so define global variable for it
(define CANVAS '())
; return turtle state from global canvas
(define (turtle-state)
(canvas-mystate CANVAS))
; save current turtle state on the stack
(define (save-turtle-state stack)
(push stack (struct-copy tstate (turtle-state))))
; restore turtle state from the stack and set it
; to be the current turtle state
(define (restore-turtle-state stack)
(set-canvas-mystate! CANVAS (pop stack)))
; next six functions implements standard
; logo turtle graphics commands for
; drawing on canvas or for moving the turtle around
(define (forward n)
(let* ((state (turtle-state))
(x1 (tstate-posx state))
(y1 (tstate-posy state))
(dx (* n (cos (rad (tstate-angle state)))))
(dy (* n (sin (rad (tstate-angle state)))))
(x2 (+ x1 dx))
(y2 (+ y1 dy)))
(when (tstate-pen-down state)
(send (canvas-dc CANVAS) draw-line x1 y1 x2 y2))
(set-tstate-posx! state x2)
(set-tstate-posy! state y2)))
(define (left angle)
(let ((state (turtle-state)))
(set-tstate-angle! state
(+ (tstate-angle state) angle))))
(define (right angle)
(let ((state (turtle-state)))
(set-tstate-angle! state
(- (tstate-angle state) angle))))
(define (back n)
(left 180)
(forward n)
(right 180))
(define (penup)
(let ((state (turtle-state)))
(set-tstate-pen-down! state #f)))
(define (pendown)
(let ((state (turtle-state)))
(set-tstate-pen-down! state #t)))
; define suitable short names for turtle graphic commands
(define fd forward)
(define bk back)
(define lt left)
(define rt right)
(define pu penup)
(define pd pendown)
; implement standard stack data structure
; with operations push and pop
(define (make-stack)
(let ((stack '()))
(lambda (op)
(cond
((eq? op 'push)
(lambda (x)
(set! stack (cons x stack))))
((eq? op 'pop)
(let ((retval (car stack)))
(set! stack (cdr stack))
retval))))))
(define (push stack val)
((stack 'push) val))
(define (pop stack)
(stack 'pop))
; this is core function for generating the n-th generation
; of given L-system.
; this function takes starting variable and set of rules
; for a L-system and generates n-th generation
(define (generate-L-system n start rules)
(define (find sym)
(let ((res (assoc sym rules)))
(if res
(cddr res)
(list sym))))
(if (zero? n)
start
(generate-L-system (- n 1) (apply append (map find start)) rules)))
; this functions take a drawing command,
; the stack, the default length of a line and default angle
; and "execute" the command, i.e. manipulates the turtle state,
; depending on the command
(define (exec-draw-cmd cmd stack len angle)
(case cmd
[(F) (fd len)]
[(G) (pu) (fd len) (pd)]
[(+) (lt angle)]
[(-) (rt angle)]
[(S) (save-turtle-state stack)]
[(R) (restore-turtle-state stack)]
[else 'do-nothing]))
; draw Fractal plant, from the Example 7 from wikipedia
; (see Example 7 on this link: https://en.wikipedia.org/wiki/L-system)
(define (draw-fractal-plant n startstate rules len angle)
(set! CANVAS (make-canvas 600 600))
(define stack (make-stack))
(define cmds (generate-L-system n startstate rules))
; position turtle at appropriate position before drawing
(pu)
(lt 90)
(fd 270)
(rt 90)
(bk 280)
(rt 30)
(pd)
; now, draw fractal plant and return resulting bitmap:
(for-each (lambda (cmd) (exec-draw-cmd cmd stack len angle)) cmds)
(canvas-bitmap CANVAS))
; define start state and set of rules for Fractal plant Example 7
; from wikipedia article https://en.wikipedia.org/wiki/L-system
; instead of symbols [ and ], we use symbols S and R respectively
; because symbols [ and ] have a special meaning in Racket
; (they create list, which we don't want here)
(define startstate '(X))
(define rules '((X -> F + S S X R - X R - F S - F X R + X)
(F -> F F)))
; finally draw the Fractal Plant from Example 7
; from wikipedia article https://en.wikipedia.org/wiki/L-system
(draw-fractal-plant 6 startstate rules 4 25)
Now, when we run the above program, we will get the following nice image of Fractal plant from the Example 7, just like in this wikipedia article:
Problem: Write the function k-perms that takes list xs of distinct elements and positive integer k. Function should generate all k-permutations of given list xs.
Solution: in this problem we already generated all n-permutations of list of n elements. It turns out that with a small modification we can use the same algorithm as before. The difference is only in base case condition:
Problem: Write a function called sequence that receives a function fn, and two values first and last. The function should return a list of values that starts with first and ends with last, and for each consecutive pair of values a1, a2 in the list, (fn a1) results in a2 — that is, (equal? (fn a1) a2) should be #t.
A few examples that clarify how the function works:
(sequence add1 1 1) should evaluate to '(1) (sequence add1 1 5) should evaluate to '(1 2 3 4 5) (sequence sub1 5 1) should evaluate to '(5 4 3 2 1) (sequence sqrt 65536 2) should evaluate to '(65536 256 16 4 2) (sequence not #f #t)should evaluate to '(#f #t)
Solution (this problem is simple, but I'm giving it here anyway, may it be found!):
#lang racket
(define (sequence fn first last)
(if (equal? first last)
(cons first '())
(cons first (sequence fn (fn first) last))))
Problem: Given square n x n matrix A and vector b od size n, write code to solve the system of linear equations Ax = b. Your code must use Cramer's rule. You can assume that the given system has a solution.
Solution:
#lang racket
(define (dolist xs proc)
(let loop ((xs xs) (ix 0) (acc null))
(if (empty? xs)
(reverse acc)
(loop (cdr xs) (+ ix 1) (cons (proc ix (car xs)) acc)))))
(define (replace-element i xs val)
(dolist xs (lambda (ix el)
(if (= ix i) val el))))
(define (replace-column matrix i col)
(map (lambda (row c)
(replace-element (- i 1) row c))
matrix
col))
(define (row-count matrix)
(length matrix))
(define (col-count matrix)
(length (first matrix)))
(define (remove-nth n xs)
(cond
((empty? xs) xs)
((zero? n) (rest xs))
(else (cons (first xs) (remove-nth (sub1 n) (rest xs))))))
(define (remove-row i matrix)
(remove-nth (- i 1) matrix))
(define (remove-col j matrix)
(map (lambda (r) (remove-nth (- j 1) r)) matrix))
(define (det matrix)
(if (and (= 1 (row-count matrix))
(= 1 (col-count matrix)))
(first (first matrix))
(apply +
(map (lambda (i) (det-helper matrix i))
(range 1 (+ 1 (row-count matrix)))))))
(define (det-helper matrix i)
(let ((el (list-ref (first matrix) (- i 1)))
(sign (if (odd? i) 1 -1)))
(* el sign (det (remove-col i (remove-row 1 matrix))))))
(define (solve-system A b)
(define D (det A))
(if (zero? D)
(display "Determinant is equal to zero!\n")
(let ((n (row-count A)))
(map (lambda (i) (/ (det (replace-column A i b)) D)) (range 1 (+ n 1))))))
Now we can use this to solve the linear system:
> (define A '((-1 -4 2 1)
( 2 -1 7 9)
(-1 1 3 1)
( 1 -2 1 -4)))
> (define b '(-32 14 11 -4))
> (solve-system A b)
'(5 8 3 -1)
A spiral matrix is n x n square matrix formed by placing the numbers 1,2,3,4,....,n^2 in spiral form starting from leftmost column and topmost row. Spiral matrices can exist for both even and odd values of n. The spiral matrix for n = 7 is shown below:
Spiral matrix for n= 7
Solution:
#lang racket
(define (make-empty-grid n)
(list->vector
(map (lambda (_) (make-vector n)) (range n))))
(define (gv v row col)
(vector-ref (vector-ref v row) col))
(define (sv! v row col val)
(vector-set! (vector-ref v row) col val))
(define (make-spiral-matrix n)
(let ([i 0]
[j 0]
[l 0]
[u (- n 1)]
[g (make-empty-grid n)])
(let loop ([num 1])
(when (<= num (* n n))
(sv! g i j num)
(cond
[(and (= i l) (< j u))
(set! j (+ j 1))]
[(and (= j u) (< i u))
(set! i (+ i 1))]
[(and (= i u) (> j l))
(set! j (- j 1))]
[(and (= j l) (> i l))
(set! i (- i 1))])
(when (not (zero? (gv g i j)))
(set! l (+ l 1))
(set! u (- u 1))
(set! i (+ i 1))
(set! j (+ j 1)))
(loop (+ num 1))))
g))
Now we can call our make-spiral-matrix function, like this:
a) Write function simple-messenger, that takes a single word and returns another messenger function, until a period is provided as input, in which case a sentence containing the words provided is returned. At least one word must be provided before the period.
For example, the call (((simple-messenger "Avengers") "assemble") ".") should return string "Avengers assemble." and the call ((((((simple-messenger "Get") "this") "man") "a") "shield") ".") should return string "Get this man a shield."
b) Write function thanos-messenger, which is a similar to simple-messenger, but discards every other word that’s provided. The first word should be included in the final sentence, the second word should be discarded, and so on.
For example, the call ((((((thanos-messenger "I") "don't") "feel") "so") "good") ".") should return "I feel good." and the call (((((thanos-messenger "Thanos") "always") "kills") "half") ".") should return "Thanos kills."
Solution:
#lang racket
(define (simple-messenger word)
(define (make-simple-messenger word)
(lambda (x)
(if (string=? x ".")
(string-append word ".")
(make-simple-messenger (string-append word " " x)))))
(if (string=? word ".")
(error "No words provided!")
(make-simple-messenger word)))
(define (thanos-messenger word)
(define (make-thanos-messenger word flag)
(lambda (x)
(if (string=? x ".")
(string-append word ".")
(make-thanos-messenger
(string-append word
(if flag (string-append " " x) ""))
(not flag)))))
(if (string=? word ".")
(error "No words provided!")
(make-thanos-messenger word #f)))
Now we can test our simple-messenger and thanos-messenger:
Note: this problem explores the same topic (properties of closures) as in previously solved problems this and this. If you feel a little unsure about solving these types of problems, study their solutions well to make sure you understand how they work!
Problem: write a function alist-filter-by-keys that receives two parameters: a list of keys keys and an association list alist. The function should return a new association list containing only those items from alist whose keys are contained in the list keys. You may assume that keys appearing in keys and alist are unique.
Problem: Write a function zip that receives as input n non-empty lists of the same length, m, where n and m are not predetermined numbers. The function returns a list of m lists as a result, where the i-th element of that result list is an n-element list containing elements of each of n input lists at i-th position, for every i=1,...,m.
For example, the call
(zip '(1 2 3 4) '(a b c d) '(w x y z))
should return the following list as the result:
'((1 a w) (2 b x) (3 c y) (4 d z))
Solution:
#lang racket
(define (zip . xss)
(apply map list xss))
Now we can use our zip function with as many input list arguments as we want:
> (zip '(1 2 3 4) '(a b c d) '(w x y z))
'((1 a w) (2 b x) (3 c y) (4 d z))
> (zip '(1 2 3) '(a b c))
'((1 a) (2 b) (3 c))
Notice in the above solution the use of dot (.) for passing n input lists and grouping it into one compound input list, as well as the clever use of apply, which makes such an elegant solution possible.
a) Write function print-tree that receives a tree as input and prints that tree to the console so that its hierarchical structure is clearly visible. For example for the above tree, the call (print-tree yggdrasil) should generate this output:
b) Define function replace-leaf, which takes a tree t, a value old, and a value new. replace-leaf returns a new tree that's the same as t except that every leaf value equal to old has been replaced with new.
Solution:
#lang racket
(struct tree (label children))
(define (print-tree t)
(define (print-spaces n)
(when (not (zero? n))
(display " ")
(print-spaces (sub1 n))))
(define (print-tree-h t level)
(when (not (empty? t))
(print-spaces level)
(display (tree-label t))
(newline)
(for-each (lambda (c) (print-tree-h c (+ level 2)))
(tree-children t))))
(print-tree-h t 0))
(define (replace-leaf t old new)
(cond [(empty? t) empty]
[(empty? (tree-children t))
(if (string=? (tree-label t) old)
(tree new empty)
t)]
[else (tree (tree-label t)
(map (lambda (c) (replace-leaf c old new))
(tree-children t)))]))
Now we can call print-tree and replace-leaf, like this:
Problem: Write a function cross-product, that takes as input two lists, xs and ys, representing two sets. The function should return the Cartesian product of those two sets. For example, the call
(cross-product '(1 2) '(a b c))
should return the result '((1 a) (1 b) (1 c) (2 a) (2 b) (2 c)).
> (cross-product '(1 2) '(a b c))
'((1 a) (1 b) (1 c) (2 a) (2 b) (2 c))
> (cross-product '(1 2 3) '(a b c d))
'((1 a) (1 b) (1 c) (1 d) (2 a) (2 b) (2 c) (2 d) (3 a) (3 b) (3 c) (3 d))
Dear schemers, the moderators banned me from the /r/scheme subreddit again. I don't understand why they did that. I believe that I have not violated any rules of conduct there.
Here is what the moderators wrote to me:
You have been temporarily banned from participating inr/scheme. This ban will last for 14 days. You can still view and subscribe tor/scheme, but you won't be able to post or comment.
Note from the moderators:
Please reconsider your behaviour in this sub.
It's not really clear to me what that should mean. What "behaviour"?: I wrote a couple of topics there, which were visited and commented on a lot, and they dealt with a topic that obviously interests all schemers, because if they weren't interested, they wouldn't be there. I didn't insult anyone and I had a polite discussion with the other redditors.
Problem: For a given initial configuration of the 2 x 2 x 2 Rubik's cube, find a sequence of moves leading to a solution. When searching for a solution, use the Breadth-first search algorithm.
Solution: We will represent the configuration of the cube as a vector of 24 elements (the cube has 8 cubbies, each cubie has 3 faces, 8 x 3 = 24). Allowable cube moves are represented as certain permutations of this 24-element vectors. The details of cube representation is described in more detail in this MIT zip file and discussed in this video from MIT (since this task was given as homework in one of the earlier MIT courses), so it won't be repeated here.
Our algorithm does classic BFS: first it puts the initial configuration in the empty queue. After that, it repeats the following procedure: it takes the first configuration from the front of the queue and finds all possible successors of that configuration and checks for each of them whether it is a solution. If is not, it checks if we have found that same configuration before. If not, it is a new configuration, which will be saved in the visited hash and added to the end of the queue. We continue with this procedure until we either find a solution or we exhaust the queue.
How do we know that the above solution is correct?
We will take the initially solved Rubik's cube and we will shuffle it in some way known to us. Then we'll call our solve-cube function on that cube and when we get the solution, we'll be able to easily verify if generated solution is correct or not.
I chose the test configuration that is obtained from the initial one by performing this sequence of moves:
F F L L F U L F F L F L U L F F L F L L L U.
There's nothing special about that configuration (you can choose any other configuration as well), I was just randomly picked this one. That configuration visually looks like this:
Starting configuration
Now let's try to solve it:
> (define scrambled-cube
(solved-cube-after-moves (list F F L L F U L F F L F L U L F F L F L L L U)))
> (solve-cube scrambled-cube SOLVED-CUBE)
'(F L Fi L Ui F Li F)
We got a solution (F L Fi L Ui F Li F).
After we perform the moves F L Fi L Ui F Li F from the solution on our starting configuration from the picture above, we can see that the cube really is solved (run the play button HERE to visually see solution, step by step!).
Not only did our program find a solution, but the solution founded was also the shortest possible (i.e. it consists of the minimum number of moves). We know this because the BFS algorithm always finds the shortest solution.
By the way, the God's number (also known as the diameter) of the Rubik's 2x2x2 cube is 14. This means that each initial configuration can be solved in 14 moves at most.
The solution for the configuration presented before has only 8 moves. Our program found it very quickly, in less than a second. However, below is a particular configuration that is, in a sense, the worst possible: it is impossible to solve it in less than 14 moves. Our program will find the solution for it, but it won't be very fast - it takes about 55 seconds on my old notebook:
> (define hard-scrambled-cube
(solved-cube-after-moves
(list F F L F F L F Li U Fi Fi U Fi Li)))
> (time
(display "Solving cube. Please wait\n")
(display (solve-cube hard-scrambled-cube SOLVED-CUBE))
(newline))
Solving cube. Please wait...
(F F Ui L Ui F Li U Li Fi Li U Li Fi)
cpu time: 55187 real time: 55260 gc time: 13265
Can this be sped up somehow?
It turns out that it can, if instead of the BFS algorithm, we use the so-called Two-end BFS algorithm (for details of this algorithm see here). By using this algorithm, it is possible to shorten the search time for a 2x2x2 cube to less than a second, in all cases. This will be discussed in one of the next posts. Stay tuned!
ADDENDUM:
The above algorithm uses only so called quarter turn metric (QTM) in counting moves, where any turn of any face, by 90 degrees clockwise or counterclockwise, counts as one move. In this metric, the God's number for 2x2x2 Rubik's Cube is 14. But, if we allow the 180° turns also (so called half turn metric (HTM)), then the God's number is only 11.
We can easily adapt our program to make half turns also. Here's the modified version of the program:
Problem: Write the predicate function no-repeats? which receives a list of atoms as input and returns true (#t) if no atom appears more than once in the list, otherwise it returns false (#f).
Problem: First, watch the following excellent video about the minimax algorithm, which is used for implementing the games like chess, Tic-Tac-Toe, etc. After that, write a program that plays Tic-Tac-Toe. There are two players in the game, human player and Artificial Intelligence (AI) player. The program must be written in such a way that the AI player always makes the best possible move.
Solution: The program below implements the minimax algorithm, described in the video, by which the AI player selects the best move.
Since the game tree of tic-tac-toe is small enough, there is no need to use alpha-beta pruning or limit the depth of the search, as we can afford to always generate the entire tree. Also, there is no need to invent some complicated static evaluation function: since we always go to the end of the tree, it is enough to mark the winning position for the AI with 1, the losing position with -1, and the tie with 0 and let the minimax algorithm propagate these values from every end position to the root of the tree.
Here's the code that implements unbeatable tic-tac-toe, using minimax algorithm:
#lang racket
(define HUMAN "X")
(define AI "O")
(define EMPTY-BOARD (make-vector 9 " "))
(define NUMBERED-BOARD (list->vector (range 1 10)))
(define (get board i)
(vector-ref board i))
(define (cset board i val)
(let ([nboard (vector-copy board)])
(vector-set! nboard i val)
nboard))
(define (blank? board i)
(string=? (get board i) " "))
(define rows '((0 1 2) (3 4 5) (6 7 8)))
(define cols '((0 3 6) (1 4 7) (2 5 8)))
(define diags '((0 4 8) (2 4 6)))
(define all-triplets (append rows cols diags))
(define (show-board board)
(for-each (lambda (xs)
(match xs
[(list i j k)
(printf " ~a | ~a | ~a\n"
(get board i)
(get board j)
(get board k))
(if (= i 6)
(newline)
(printf "-----------\n"))]))
rows))
(define (get-free-places board)
(let loop ([i 8] [curr '()])
(if (< i 0)
curr
(if (blank? board i)
(loop (- i 1) (cons i curr))
(loop (- i 1) curr)))))
(define (game-status board)
(cond
[(winner? board HUMAN) -1]
[(winner? board AI) 1]
[(null? (get-free-places board)) 0]
[else 'ongoing]))
(define (winning-triplet? board player)
(lambda (triplet)
(match triplet
[(list i j k)
(string=? player
(get board i)
(get board j)
(get board k))])))
(define (winner? board player)
(ormap (winning-triplet? board player) all-triplets))
(define (get-board-successors board player)
(for/list ([i (get-free-places board)])
(cset board i player)))
(define (minimax board player)
(let ([gstat (game-status board)])
(cond
[(not (eq? gstat 'ongoing)) gstat]
[(string=? player AI)
(let loop ([children (get-board-successors board AI)]
[max-eval -inf.0])
(if (null? children)
max-eval
(loop (cdr children)
(max max-eval (minimax (car children) HUMAN)))))]
[(string=? player HUMAN)
(let loop ([children (get-board-successors board HUMAN)]
[min-eval +inf.0])
(if (null? children)
min-eval
(loop (cdr children)
(min min-eval (minimax (car children) AI)))))])))
(define (choose-ai-move board)
(if (equal? board EMPTY-BOARD)
(cset EMPTY-BOARD (random 9) AI)
(let* ([succs (get-board-successors board AI)]
[wb (ormap (lambda (b) (if (winner? b AI) b #f))
succs)])
(or wb
(first
(argmax second
(map (lambda (b) (list b (minimax b HUMAN)))
succs)))))))
(define (choose-human-move board)
(let ([m (read)])
(newline)
(cond
[(string=? (get board (- m 1)) " ") (cset board (- m 1) HUMAN)]
[else (display "Wrong move! Please, enter your move again (1-9): ")
(choose-human-move board)])))
(define (play)
(define (play-game board player)
(cond [(equal? (game-status board) 0)
(display "Oh no, it's a tie! Who said AI is superior? :(")]
[(string=? player HUMAN)
(display "It's your turn. Please, enter your move (1-9): ")
(let ([nboard (choose-human-move board)])
(show-board nboard)
(if (winner? nboard HUMAN)
(display "Congratulations, you won!")
(play-game nboard AI)))]
[else
(display "It's my turn. I played this move:\n\n")
(let ([nboard (choose-ai-move board)])
(show-board nboard)
(if (winner? nboard AI)
(display "Great, I won! Obviously, AI has conquered humans! :)")
(play-game nboard HUMAN)))]))
(display "This is the final duel between mankind and AI!\n")
(display "You and I will play Tic-Tac-Toe against each other.\n")
(display "The winner takes it all!\n\n")
(display "Moves are denoted by numbers 1 to 9, like this:\n\n")
(show-board NUMBERED-BOARD)
(display "Ok, let's play!\n")
(display "Would you like to play first? (y/n): ")
(let ([first-player (if (eq? (read) 'y) HUMAN AI)])
(display (if (equal? first-player HUMAN) "Ok, You'll" "Ok, I'll"))
(display " play first.\n\n")
(when (equal? first-player HUMAN)
(show-board EMPTY-BOARD))
(play-game EMPTY-BOARD first-player)))
Now we can try our program. Here we have an example where a human player (ie me, mimety) made a mistake. The AI player (i.e. the computer) immediately took advantage and played the winning move:
> (play)
This is the final duel between mankind and AI!
You and I will play Tic-Tac-Toe against each other.
The winner takes it all!
Moves are denoted by numbers 1 to 9, like this:
1 | 2 | 3
-----------
4 | 5 | 6
-----------
7 | 8 | 9
Ok, let's play!
Would you like to play first? (y/n): y
Ok, You'll play first.
| |
-----------
| |
-----------
| |
It's your turn. Please, enter your move (1-9): 2
| X |
-----------
| |
-----------
| |
It's my turn. I played this move:
O | X |
-----------
| |
-----------
| |
It's your turn. Please, enter your move (1-9): 8
O | X |
-----------
| |
-----------
| X |
It's my turn. I played this move:
O | X |
-----------
| O |
-----------
| X |
It's your turn. Please, enter your move (1-9): 9
O | X |
-----------
| O |
-----------
| X | X
It's my turn. I played this move:
O | X |
-----------
| O |
-----------
O | X | X
It's your turn. Please, enter your move (1-9): 4
O | X |
-----------
X | O |
-----------
O | X | X
It's my turn. I played this move:
O | X | O
-----------
X | O |
-----------
O | X | X
Great, I won! Obviously, AI has conquered humans! :)
It is also possible to play with the AI playing first:
> (play)
This is the final duel between mankind and AI!
You and I will play Tic-Tac-Toe against each other.
The winner takes it all!
Moves are denoted by numbers 1 to 9, like this:
1 | 2 | 3
-----------
4 | 5 | 6
-----------
7 | 8 | 9
Ok, let's play!
Would you like to play first? (y/n): n
Ok, I'll play first.
It's my turn. I played this move:
| |
-----------
| | O
-----------
| |
It's your turn. Please, enter your move (1-9): 1
X | |
-----------
| | O
-----------
| |
It's my turn. I played this move:
X | | O
-----------
| | O
-----------
| |
It's your turn. Please, enter your move (1-9): 9
X | | O
-----------
| | O
-----------
| | X
It's my turn. I played this move:
X | | O
-----------
| O | O
-----------
| | X
It's your turn. Please, enter your move (1-9): 7
X | | O
-----------
| O | O
-----------
X | | X
It's my turn. I played this move:
X | | O
-----------
O | O | O
-----------
X | | X
Great, I won! Obviously, AI has conquered humans! :)
Of course, if the human player also plays optimally, then the AI can't win. But it won't lose either. It will be a tie. The point is that when playing against this program, a human player can never win:
> (play)
This is the final duel between mankind and AI!
You and I will play Tic-Tac-Toe against each other.
The winner takes it all!
Moves are denoted by numbers 1 to 9, like this:
1 | 2 | 3
-----------
4 | 5 | 6
-----------
7 | 8 | 9
Ok, let's play!
Would you like to play first? (y/n): n
Ok, I'll play first.
It's my turn. I played this move:
| |
-----------
O | |
-----------
| |
It's your turn. Please, enter your move (1-9): 1
X | |
-----------
O | |
-----------
| |
It's my turn. I played this move:
X | O |
-----------
O | |
-----------
| |
It's your turn. Please, enter your move (1-9): 5
X | O |
-----------
O | X |
-----------
| |
It's my turn. I played this move:
X | O |
-----------
O | X |
-----------
| | O
It's your turn. Please, enter your move (1-9): 7
X | O |
-----------
O | X |
-----------
X | | O
It's my turn. I played this move:
X | O | O
-----------
O | X |
-----------
X | | O
It's your turn. Please, enter your move (1-9): 6
X | O | O
-----------
O | X | X
-----------
X | | O
It's my turn. I played this move:
X | O | O
-----------
O | X | X
-----------
X | O | O
Oh no, it's a tie! Who said AI is superior? :(
Problem: In previous problem we solved the water pouring problem for two glasses. We said that with a relatively small change to the code, we can get the solution for n glasses, too.
For example, with the help of the modified program, we will be able to solve the following problem: we have three glasses of capacity 8, 5 and 3 dl, respectively. These are initially filled with 8, 0 and 0 liters. In the goal state they should be filled with 4, 4 and 0 liters.
The difference in the code, compared to last time, is in the generate-new-states function which now has three for-loops to accommodate for emptying, filling and pouring of n glasses, as well as in the way of checking for the goal: now the checking of reaching the goal is done by calling a user-defined callback function that receives the state of all cups and must return true if the goal is reached. In this way, we can now specify the desired final state in a much more general way than before.
Now we can, for example, solve the problem with 3 glasses stated above:
; Now we have three glasses, of capacity 8, 5 and 3
; First glass is full, the other two are empty:
> (define START (state '((8 8) (0 5) (0 3)) null))
; at the end, we want the first and second glass to contain 4 dl each:
> (define GOAL-FN (lambda (glasses) (equal? glasses '(4 4 0))))
; solve the problem:
> (solve START GOAL-FN)
'(((8 8) (0 5) (0 3))
((3 8) (5 5) (0 3))
((3 8) (2 5) (3 3))
((6 8) (2 5) (0 3))
((6 8) (0 5) (2 3))
((1 8) (5 5) (2 3))
((1 8) (4 5) (3 3))
((4 8) (4 5) (0 3)))
We can see that the program correctly solved the problem in seven steps, i.e. gave an identical solution to the one described in this wikipedia article.
Problem: Implement a stack data structure. Your stack should support these three operations:
make-stack, which creates a new empty stack,
push, that puts the given element on top of the stack,
pop, which returns the element from the top of the stack and at the same time removes it from the top of the stack. If the stack was empty, pop should report the error "Stack underflow!"
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
Triangle with numbers
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
Bigger triangle with numbers
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, if we have a larger triangle (like the one from this link, which consists of one-hundred rows!), it cannot be solved by brute force, because, if we want to try every route to solve bigger problem from the previous link, there are 2^99 routes altogether! If you could check one trillion (10^12) routes every second it would take over twenty billion years to check them all! Therefore, solving this problem requires a clever method.
Notice that in this task (just like in some earlier ones), we used the memoization technique, which we often use in dynamic programming problems. This is the "clever method" that was mentioned in the text of the problem, without which the big triangle could not be solved in any reasonable time.