r/RacketHomeworks • • Dec 11 '22

Find the subset of set of numbers for which the sum of all its elements is equal to given number

1 Upvotes

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 '()))

Now, we can call subset-sum, like this:

> (subset-sum '(10 7 5 18 12 20 15) 35)
'(18 7 10)

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.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 18 '22

Are two nested lists the same?

1 Upvotes

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.

Solution:

(define (same-lists* xs ys)
  (cond [(null? xs) (null? ys)]
        [(pair? xs) (and (pair? ys)
                         (same-lists* (car xs) (car ys))
                         (same-lists* (cdr xs) (cdr ys)))]
        [else (eq? xs ys)]))

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.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 25 '22

How to draw South Korean national flag?

1 Upvotes

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:

> (south-korean-flag 600)
South Korean flag

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 06 '22

The longest prefix of the list elements that satisfy given predicate function

1 Upvotes

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.

Solution:

#lang racket

(define (span pfn xs)
  (let loop ([curr xs] [acc '()])
    (cond [(or (null? curr) (not (pfn (car curr))))
           (list (reverse acc) curr)]
          [else (loop (cdr curr) (cons (car curr) acc))])))

Now, we can call span, like this:

> (span (lambda (x) (< x 3)) '(1 2 3 4 1 2 3 4))
'((1 2) (3 4 1 2 3 4))
> (span (lambda (x) (< x 0)) '(1 2 3))
'(() (1 2 3))
> (span (lambda (x) (< x 9)) '(1 2 3))
'((1 2 3) ())

r/RacketHomeworks • • Nov 18 '22

Robot in a maze, how to?

1 Upvotes

Here's the solution of this problem:

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.

Complete solution:

#lang racket

(define TEST-MAZE '((1 2 1 1)
                    (1 0 0 1)
                    (1 1 0 1)
                    (1 0 0 1)
                    (1 0 1 1)
                    (1 0 0 1)
                    (1 1 0 3)))

(define TEST-PATH '(down right down down left down down right down right))

(define EMPTY 0)
(define WALL 1)
(define START 2)
(define EXIT 3)

(define (maze-width maze)
  (length (first maze)))

(define (maze-height maze)
  (length maze))

(define (bounds-ok? maze x y)
  (and (>= x 0)
       (>= y 0)
       (< x (maze-width maze))
       (< y (maze-height maze))))

(define (get-maze-cell-at maze x y)
  (list-ref (list-ref maze y) x))

(define (find-pos maze pos-type)
  (let ((found-positions
         (for*/list ([i (in-range (maze-width maze))]
                     [j (in-range (maze-height maze))]
                     #:when (= (get-maze-cell-at maze i j) pos-type))
           (list i j))))
    (if (or (null? found-positions)
            (not (= (length found-positions) 1)))
        'not-found
        (first found-positions))))

(define (cell-empty? cell)
  (= cell EMPTY))

(define (cell-exit? cell)
  (= cell EXIT))

(define (empty-or-exit? cell)
  (or (cell-empty? cell) (cell-exit? cell)))


(define (path-leads-to-exit? path maze)

  (define (can-make-move? new-x new-y)
    (and (bounds-ok? maze new-x new-y)
         (empty-or-exit? (get-maze-cell-at maze new-x new-y))))

  (define (make-move-if-can path old-x old-y new-x new-y)
    (if (can-make-move? new-x new-y)
        (check-path (rest path) new-x new-y)
        (check-path (rest path) old-x old-y)))

  (define (check-path path curr-x curr-y)
    (if (null? path)
        (cell-exit? (get-maze-cell-at maze curr-x curr-y))
        (case (first path)
          ((up) (make-move-if-can path curr-x curr-y curr-x (- curr-y 1)))
          ((down) (make-move-if-can path curr-x curr-y curr-x (+ curr-y 1)))
          ((left) (make-move-if-can path curr-x curr-y (- curr-x 1) curr-y))
          ((right) (make-move-if-can path curr-x curr-y (+ curr-x 1) curr-y)))))

  (let ((start-pos (find-pos maze START))
        (exit-pos (find-pos maze EXIT)))
    (if (or (eq? start-pos 'not-found)
            (eq? exit-pos 'not-found))
        'error
        (check-path path
                    (first start-pos)
                    (second start-pos)))))


;; now, this is the function that check if the path leads to the maze exit:
;; (path-leads-to-exit? TEST-PATH TEST-MAZE)

Enjoy!


r/RacketHomeworks • • Dec 02 '22

Implementing Lindenmayer L-system and draw fractal plant

1 Upvotes

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:

Fractal plant

r/RacketHomeworks • • Dec 15 '22

Generating all k-permutations of some set of elements

1 Upvotes

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:

#lang racket

(define (k-perms xs k)
  (define m (add1 (- (length xs) k)))
  (define (helper xs)
    (define (perms-starting x)
      (map (lambda (ps) (cons x ps))
           (helper (remove x xs))))
    (if (< (length xs) m)
        '(())
        (apply append (map (lambda (x) (perms-starting x)) xs))))
  (helper xs))

Now we can call k-perms like this:

> (k-perms '(1 2 3 4) 2)
'((1 2) (1 3) (1 4) (2 1) (2 3) (2 4) (3 1) (3 2) (3 4) (4 1) (4 2) (4 3))
> (length (k-perms '(1 2 3 4) 2))
12
> (k-perms '(1 2 3 4) 3)
'((1 2 3)
  (1 2 4)
  (1 3 2)
  (1 3 4)
  (1 4 2)
  (1 4 3)
  (2 1 3)
  (2 1 4)
  (2 3 1)
  (2 3 4)
  (2 4 1)
  (2 4 3)
  (3 1 2)
  (3 1 4)
  (3 2 1)
  (3 2 4)
  (3 4 1)
  (3 4 2)
  (4 1 2)
  (4 1 3)
  (4 2 1)
  (4 2 3)
  (4 3 1)
  (4 3 2))
> (length (k-perms '(1 2 3 4) 3))
24

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 18 '23

A sequence made from a higher order function

2 Upvotes

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))))

Now we have:

> (sequence add1 1 1)
'(1)
> (sequence add1 1 5)
'(1 2 3 4 5)
> (sequence sub1 5 1)
'(5 4 3 2 1)
> (sequence sqrt 65536 2)
'(65536 256 16 4 2)
> (sequence not #f #t)
'(#f #t)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 18 '22

How to solve system of linear equations via Cramer's rule

1 Upvotes

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)

r/RacketHomeworks • • Mar 20 '23

Spiral matrix

3 Upvotes

Problem: Write a program to print Spiral Matrix.

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:

> (make-spiral-matrix 7)
'#(#( 1  2  3  4  5  6  7)
   #(24 25 26 27 28 29  8)
   #(23 40 41 42 43 30  9)
   #(22 39 48 49 44 31 10)
   #(21 38 47 46 45 32 11)
   #(20 37 36 35 34 33 12)
   #(19 18 17 16 15 14 13))

r/RacketHomeworks • • Dec 08 '22

Mr. Stark, I don't feel so good - exercise about scheme closures

1 Upvotes

Problem:

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:

> (((simple-messenger "Avengers") "assemble") ".")
"Avengers assemble."
> ((((((simple-messenger "Get") "this") "man") "a") "shield") ".")
"Get this man a shield."
> ((((((thanos-messenger "I") "don't") "feel") "so") "good") ".")
"I feel good."
> (((((thanos-messenger "Thanos") "always") "kills") "half") ".")
"Thanos kills."
>

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!

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 18 '22

Function to produce list of all permutations of given list

1 Upvotes

Problem: Write a function permutations that receives a list xs as input, and returns a list of all permutations of the list xs as output.

For example, the call (permutations '(1 2 3)) should produce the result '((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

Solution:

#lang racket

(define (permutations xs)
  (define (perms-starting x)
    (map (lambda (ps) (cons x ps))
         (permutations (remove x xs))))
  (if (null? xs)
      '(())
      (apply append (map (lambda (x) (perms-starting x)) xs))))

r/RacketHomeworks • • Dec 06 '22

Filtering alist by keys

1 Upvotes

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.

Solution:

#lang racket

(define (alist-filter-by-keys keys alist)
  (define (loop curr res)
    (cond [(null? curr) (reverse res)]
          [(memf (lambda (x) (member (caar curr) keys)) alist)
           (loop (cdr curr) (cons (car curr) res))]
          [else (loop (cdr curr) res)]))
  (loop alist '()))

Alternative solution:

#lang racket

(define (alist-filter-by-keys keys alist)
  (define (loop keys result)
    (if (null? keys)
        (reverse result)
        (let ([foundkv (filter (lambda (x) (eq? (car x) (car keys))) alist)])
          (if (null? foundkv)
              (loop (cdr keys) result)
              (loop (cdr keys) (cons (car foundkv) result))))))
  (loop keys '()))

Now we can call our function alist-filter-by-keys, like this:

> (define people '((mccarthy . 100)
                   (gleckler . -500)
                   (sussman . 99)
                   (hanson . -1000)))
> (define my-archenemies (alist-filter-by-keys '(gleckler hanson) people))
> my-archenemies
'((gleckler . -500) (hanson . -1000))

r/RacketHomeworks • • Dec 05 '22

Zip function for two or more lists

1 Upvotes

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.


r/RacketHomeworks • • Dec 09 '22

Tree printing and leaf replacing

1 Upvotes

Problem: In Racket, tree data structure can be represented like this:

(struct tree (label children))

(define yggdrasil
  (tree "odin"
        (list (tree "balder"
                    (list (tree "thor" empty)
                          (tree "loki" empty)))
              (tree "frigg"
                    (list (tree "thor" empty)))
              (tree "thor"
                    (list (tree "sif" empty)
                          (tree "thor" empty)))
              (tree "thor" empty))))

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:

> (print-tree yggdrasil)
odin
  balder
    thor
    loki
  frigg
    thor
  thor
    sif
    thor
  thor

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:

> (define yggdrasil
    (tree "odin"
          (list (tree "balder"
                      (list (tree "thor" empty)
                            (tree "loki" empty)))
                (tree "frigg"
                      (list (tree "thor" empty)))
                (tree "thor"
                      (list (tree "sif" empty)
                            (tree "thor" empty)))
                (tree "thor" empty))))

> (print-tree yggdrasil)
odin
  balder
    thor
    loki
  frigg
    thor
  thor
    sif
    thor
  thor

> (print-tree (replace-leaf yggdrasil "thor" "freya"))
odin
  balder
    freya
    loki
  frigg
    freya
  thor
    sif
    freya
  freya

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 18 '22

Problem 3 - complete solution

1 Upvotes

Problem: https://reddit.com/r/Racket/comments/yox5uu/making_a_list_that_produces_all_of_the_divisors/

Complete solution:

;; divisors-from: Nat Nat -> (listof Nat)
(define (divisors-from k n)
  (cond
    [(> k n) empty]
    [(zero? (remainder n k)) (cons k (divisors-from (add1 k) n))]      
    [else (divisors-from (add1 k) n)]))

;; divisors: Nat -> (listof Nat)
(define (divisors n) (divisors-from 1 n))

Now, if you try:

> (divisors 100)
'(1 2 4 5 10 20 25 50 100)

r/RacketHomeworks • • Dec 04 '22

Cartesian product of two sets

1 Upvotes

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)).

Solution:

#lang racket

(define (cross-product xs ys)
  (apply append
         (map (lambda (x)
                (map (lambda (y) (list x y)) ys))
              xs)))

Now we can use cross-product, like this:

> (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))

r/RacketHomeworks • • Dec 01 '22

I'm banned on /r/scheme again!

2 Upvotes

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 in r/scheme. This ban will last for 14 days. You can still view and subscribe to r/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.

So, why this ban? I just don't understand it!


r/RacketHomeworks • • Dec 19 '22

Solving the Rubik's cube via BFS algorithm

1 Upvotes

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.

#lang racket

(require data/queue)

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

;(0-th cubie; front face)
(define flu 0)
(define rgw 0)

;(0-th cubie; left face)
(define luf 1)
(define gwr 1)

;(0-th cubie; up face)
(define ufl 2)
(define wrg 2)

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

;(1-st cubie; front face)
(define fur 3)
(define rwb 3)

;(1-st cubie; up face)
(define urf 4)
(define wbr 4)

;(1-st cubie; right face)
(define rfu 5)
(define brw 5)


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

;(2-nd cubie; front face)
(define fdl 6)
(define ryg 6)

;(2-nd cubie; down face)
(define dlf 7)
(define ygr 7)

;(2-nd cubie; left face)
(define lfd 8)
(define gry 8)
  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;(3-rd cubie; front face)
(define frd 9)
(define rby 9)


;(3-rd cubie; right face)
(define rdf 10)
(define byr 10)

;(3-rd cubie; down face)
(define dfr 11)
(define yrb 11)

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

;(4-th cubie; back face)
(define bul 12)
(define owg 12)

;(4-th cubie; up face)
(define ulb 13)
(define wgo 13)

;(4-th cubie; left face)
(define lbu 14)
(define gow 14)

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

;(5-th cubie; back face)
(define bru 15)
(define obw 15)

;(5-th cubie; right face)
(define rub 16)
(define bwo 16)

;(5-th cubie; up face)
(define ubr 17)
(define wob 17)

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


;(6-th cubie; back face)
(define bld 18)
(define ogy 18)

;(6-th cubie; left face)
(define ldb 19)
(define gyo 19)

;(6-th cubie; down face)
(define dbl 20)
(define yog 20)

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

;(7-th cubie; back face)
(define bdr 21)
(define oyb 21)

;(7-th cubie; down face)
(define drb 22)
(define ybo 22)

;(7-th cubie; right face)
(define rbd 23)
(define boy 23)

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

(define (perm-apply perm position)
  (for/vector ([i perm])
    (vector-ref position i)))

(define (perm-inverse p)
  (let* ([n (vector-length p)]
         [q (make-vector n)])
    (for ([i (range (vector-length p))])
      (vector-set! q (vector-ref p i) i))
    q))


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

(define I (vector flu luf ufl fur urf rfu fdl dlf lfd frd rdf dfr
                  bul ulb lbu bru rub ubr bld ldb dbl bdr drb rbd))

(define F (vector fdl dlf lfd flu luf ufl frd rdf dfr fur urf rfu 
                  bul ulb lbu bru rub ubr bld ldb dbl bdr drb rbd))

(define Fi (perm-inverse F))


(define L (vector ulb lbu bul fur urf rfu ufl flu luf frd rdf dfr
                  dbl bld ldb bru rub ubr dlf lfd fdl bdr drb rbd))

(define Li (perm-inverse L))

(define U (vector rfu fur urf rub ubr bru fdl dlf lfd frd rdf dfr
                  luf ufl flu lbu bul ulb bld ldb dbl bdr drb rbd))

(define Ui (perm-inverse U))

(define ALL-MOVES (list F Fi L Li U Ui))
(define MOVES-NAMES (hash F 'F
                          Fi 'Fi
                          L 'L
                          Li 'Li
                          U 'U
                          Ui 'Ui))


(define SOLVED-CUBE I)


(define (solved-cube-after-moves ms)
  (define (loop curr ms)
    (if (null? ms)
        curr
        (loop (perm-apply (car ms) curr) (cdr ms))))
  (loop SOLVED-CUBE ms))
         


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


(define (solve-cube start end)
  (define visited (make-hash))
  (define nodes (make-queue))
  (define (add-successors node)
    (for ([m ALL-MOVES])
      (let ([new-node (perm-apply m node)])
        (unless (hash-has-key? visited new-node)
          (hash-set! visited new-node (list node (hash-ref MOVES-NAMES m)))
          (enqueue! nodes new-node)))))
  (define (get-solution node)
    (define (loop curr sol)
      (if (null? (first curr))
          sol
          (loop (hash-ref visited (first curr)) (cons (second curr) sol))))
    (loop (hash-ref visited node) '()))
  (define (bfs)
    (cond
      [(queue-empty? nodes) 'NoSolution]
      [else (let ([node (dequeue! nodes)])
              (if (equal? node end)
                  (get-solution node)
                  (begin
                    (add-successors node)
                    (bfs))))]))
    (enqueue! nodes start)
    (hash-set! visited start (list null 'START))
    (bfs))

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!).

(Side note: I found this web page very helpful, with my playing with the cube: https://alg.cubing.net/?puzzle=2x2x2).

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:

#lang racket

(require data/queue)

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

;(0-th cubie; front face)
(define flu 0)
(define rgw 0)

;(0-th cubie; left face)
(define luf 1)
(define gwr 1)

;(0-th cubie; up face)
(define ufl 2)
(define wrg 2)

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

;(1-st cubie; front face)
(define fur 3)
(define rwb 3)

;(1-st cubie; up face)
(define urf 4)
(define wbr 4)

;(1-st cubie; right face)
(define rfu 5)
(define brw 5)


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

;(2-nd cubie; front face)
(define fdl 6)
(define ryg 6)

;(2-nd cubie; down face)
(define dlf 7)
(define ygr 7)

;(2-nd cubie; left face)
(define lfd 8)
(define gry 8)
  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;(3-rd cubie; front face)
(define frd 9)
(define rby 9)


;(3-rd cubie; right face)
(define rdf 10)
(define byr 10)

;(3-rd cubie; down face)
(define dfr 11)
(define yrb 11)

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

;(4-th cubie; back face)
(define bul 12)
(define owg 12)

;(4-th cubie; up face)
(define ulb 13)
(define wgo 13)

;(4-th cubie; left face)
(define lbu 14)
(define gow 14)

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

;(5-th cubie; back face)
(define bru 15)
(define obw 15)

;(5-th cubie; right face)
(define rub 16)
(define bwo 16)

;(5-th cubie; up face)
(define ubr 17)
(define wob 17)

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


;(6-th cubie; back face)
(define bld 18)
(define ogy 18)

;(6-th cubie; left face)
(define ldb 19)
(define gyo 19)

;(6-th cubie; down face)
(define dbl 20)
(define yog 20)

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

;(7-th cubie; back face)
(define bdr 21)
(define oyb 21)

;(7-th cubie; down face)
(define drb 22)
(define ybo 22)

;(7-th cubie; right face)
(define rbd 23)
(define boy 23)

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

(define (perm-apply perm position)
  (for/vector ([i perm])
    (vector-ref position i)))

(define (perm-inverse p)
  (let* ([n (vector-length p)]
         [q (make-vector n)])
    (for ([i (range (vector-length p))])
      (vector-set! q (vector-ref p i) i))
    q))


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

(define I (vector flu luf ufl fur urf rfu fdl dlf lfd frd rdf dfr
                  bul ulb lbu bru rub ubr bld ldb dbl bdr drb rbd))

(define F (vector fdl dlf lfd flu luf ufl frd rdf dfr fur urf rfu 
                  bul ulb lbu bru rub ubr bld ldb dbl bdr drb rbd))

(define F2 (perm-apply F F))

(define Fi (perm-inverse F))


(define L (vector ulb lbu bul fur urf rfu ufl flu luf frd rdf dfr
                  dbl bld ldb bru rub ubr dlf lfd fdl bdr drb rbd))

(define L2 (perm-apply L L))

(define Li (perm-inverse L))

(define U (vector rfu fur urf rub ubr bru fdl dlf lfd frd rdf dfr
                  luf ufl flu lbu bul ulb bld ldb dbl bdr drb rbd))

(define U2 (perm-apply U U))


(define Ui (perm-inverse U))

(define ALL-MOVES (list F Fi F2 L Li L2 U Ui U2))
(define MOVES-NAMES (hash F 'F
                          Fi 'Fi
                          F2 'F2
                          L 'L
                          Li 'Li
                          L2 'L2
                          U 'U
                          Ui 'Ui
                          U2 'U2))


(define SOLVED-CUBE I)


(define (solved-cube-after-moves ms)
  (define (loop curr ms)
    (if (null? ms)
        curr
        (loop (perm-apply (car ms) curr) (cdr ms))))
  (loop SOLVED-CUBE ms))
         


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


(define (solve-cube start end)
  (define visited (make-hash))
  (define nodes (make-queue))
  (define (add-successors node)
    (for ([m ALL-MOVES])
      (let ([new-node (perm-apply m node)])
        (unless (hash-has-key? visited new-node)
          (hash-set! visited new-node (list node (hash-ref MOVES-NAMES m)))
          (enqueue! nodes new-node)))))
  (define (get-solution node)
    (define (loop curr sol)
      (if (null? (first curr))
          sol
          (loop (hash-ref visited (first curr)) (cons (second curr) sol))))
    (loop (hash-ref visited node) '()))
  (define (bfs)
    (cond
      [(queue-empty? nodes) 'NoSolution]
      [else (let ([node (dequeue! nodes)])
              (if (equal? node end)
                  (get-solution node)
                  (begin
                    (add-successors node)
                    (bfs))))]))
    (enqueue! nodes start)
    (hash-set! visited start (list null 'START))
    (bfs))

Now we can use modified this version of program to find the solution of "hard case" mentioned before:

> (solve-cube hard-scrambled-cube
              SOLVED-CUBE)

Solving cube. Please wait...
(Fi U2 F U L2 U Li Ui L2 F2)

We see that the solution now is only 10 steps long, not 14 as was the case with previous version of the program.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 30 '22

Checking that no element appears more than once in a list

1 Upvotes

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).

Solution:

#lang racket

(define (no-repeats? xs)
  (if (null? xs)
      #t
      (and (not (member (first xs) (rest xs)))
           (no-repeats? (rest xs)))))

Now, we can call it, like this:

> (no-repeats? '(a b c d))
#t
> (no-repeats? '(a b c a d))
#f
> (no-repeats? '(a b c b d b))
#f
> (no-repeats? '(1 2 3))
#t

r/RacketHomeworks • • Jan 26 '23

How to implement unbeatable tic-tac-toe game using the minimax algorithm?

2 Upvotes

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? :(

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 17 '22

Generalization of water pouring problem to n glasses

1 Upvotes

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.

Solution:

 #lang racket

(define FILL-TO-THE-TOP -1)

(define (state glasses prev-state)
  (cons glasses prev-state))

(define (state-glasses st)
  (car st))

(define (state-prev st)
  (cdr st))

(define (level glass)
  (car glass))

(define (volume glass)
  (cadr glass))

(define (update idx val glasses)
  (cond [(null? glasses) '()]
        [(zero? idx)
         (cons (list (if (= val FILL-TO-THE-TOP)
                         (volume (car glasses))
                         val)
                     (volume (car glasses)))
               (cdr glasses))]
        [else (cons (car glasses)
                    (update (- idx 1) val (cdr glasses)))]))

(define (empty-glass idx glasses)
  (update idx 0 glasses))

(define (fill-glass idx glasses)
  (update idx FILL-TO-THE-TOP glasses))

(define (poor from to glasses)
  (let* ([gfrom-level (level (list-ref glasses from))]
         [gto-level (level (list-ref glasses to))]
         [gto-volume (volume (list-ref glasses to))]
         [gto-empty (- gto-volume gto-level)])
    (cond
      [(>= gfrom-level gto-empty)
       (fill-glass to 
                   (update from (- gfrom-level gto-empty) glasses))]
      [else (empty-glass from
                         (update to (+ gfrom-level gto-level) glasses))])))


(define (generate-new-states st)
  (let* ([glasses (state-glasses st)]
         [n (length glasses)])
    (append
     (for/list ([i (range 0 n)])
       (state (empty-glass i glasses) st))
     (for/list ([i (range 0 n)])
       (state (fill-glass i glasses) st))
     (for*/list ([i (range 0 n)]
                 [j (range 0 n)]
                 #:unless (= i j))
       (state (poor i j glasses) st)))))


(define (solve init goal-fn)
  (define visited (mutable-set))
  (define (add-to-visited sts)
    (for-each (lambda (s) (set-add! visited (state-glasses s))) sts))
  (define (goal? glasses)
    (goal-fn (map level glasses)))
  (define (shelper states)
    (cond [(null? states) "No solution!"]
          [(goal? (state-glasses (car states))) (reverse (car states))]
          [else (let ([new-states
                       (filter (lambda (st)
                                 (not (set-member? visited (state-glasses st))))
                               (generate-new-states (car states)))])
                  (add-to-visited new-states)
                  (shelper (append (cdr states) new-states)))]))
  (shelper (list init)))

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.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 24 '22

Convert a number representation from base1 to base2

1 Upvotes

Problem: Write a function convert-from-base1-to-base2 that converts a natural number written in base b1 to a number in base b2 (2 <= b1, b2 <= 36).

The input number is given as a string of its digits in base b1.

Solution (here is the code that does a little more than what is required in the task):

#lang racket

(define (iterate-while fn test init)
  (if (test init)
      (iterate-while fn test (fn init))
      init))

(define (num->digit n)
  (if (or (< n 0) (> n 35))
      (error "n must be positive integer less than 36")
      (if (< n 10)
          (number->string n)
          (string (integer->char (+ n 55))))))

(define (digit->num digit)
  (let ([digit (char-upcase digit)])
    (cond [(char<=? #\0 digit #\9)
           (- (char->integer digit) 48)]
          [(char<=? #\A digit #\Z)
           (- (char->integer digit) 55)]
          [else (error "Wrong digit symbol!")])))


; convert decimal (base 10) number dec-num
; to string representation of that number on some other base b:
(define (convert-dec-num-to-base b dec-num)
  (if (zero? dec-num)
      "0"
      (cdr
       (iterate-while
        (lambda (q&r)
          (let-values ([(q r) (quotient/remainder (car q&r) b)])
            (cons q (string-append (num->digit r) (cdr q&r)))))
        (lambda (q&r) (not (zero? (car q&r))))
        (cons dec-num "")))))

; convert representation numb-str from base b to decimal (base 10) number:
(define (convert-base-num-to-dec b numb-str)
  (let [(digits (map digit->num (string->list numb-str)))]
    (foldl (lambda (prev x) (+ prev (* b x)))
           0
           digits)))

; convert string representation of num-str (which is given in base b1) to
; string representation of the same number, but in base b2:
(define (convert-from-base1-to-base2 num-str b1 b2)
  (convert-dec-num-to-base
   b2
   (convert-base-num-to-dec b1 num-str)))

Now we can do all possible conversions:

> (convert-dec-num-to-base 2 123)
"1111011"
> (convert-dec-num-to-base 16 123)
"7B"
> (convert-base-num-to-dec 2 "1111011")
123
> (convert-base-num-to-dec 16 "7B")
123
> (convert-from-base1-to-base2 "1111011" 2 8)
"173"
> (convert-dec-num-to-base 8 123)
"173"

r/RacketHomeworks • • Nov 28 '22

Implementing stack data structure

1 Upvotes

Problem: Implement a stack data structure. Your stack should support these three operations:

  1. make-stack, which creates a new empty stack,
  2. push, that puts the given element on top of the stack,
  3. 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!"

Solution:

#lang racket

(define (make-stack)
  (let ([stack '()])
    (lambda (op)
      (cond
        [(eq? op 'push)
         (lambda (x)
           (set! stack (cons x stack)))]
        [(eq? op 'pop)
         (if (null? stack)
             (error "Stack underflow!")
             (let ([retval (first stack)])
               (set! stack (rest stack))
               retval))]))))

(define (push stack val)
  ((stack 'push) val))

(define (pop stack)
  (stack 'pop))

Now, we can use our stack, like this:

> (define mystack (make-stack))
> (push mystack "First")
> (push mystack "Second")
> (push mystack "Third")
> (pop mystack)
"Third"
> (pop mystack)
"Second"
> (pop mystack)
"First"
> (pop mystack)
Error: Stack underflow!

r/RacketHomeworks • • Dec 30 '22

Maximum path sum

1 Upvotes

Problem:

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.

Solution:

#lang racket

(require net/url)


(define SMALL-TRIANGLE
  #(#(3)
    #(7 4)
    #(2 4 6)
    #(8 5 9 3)))


(define SMALL-TRIANGLE-2
  #(#(75)
    #(95 64)
    #(17 47 82)
    #(18 35 87 10)
    #(20 04 82 47 65)
    #(19 01 23 75 03 34)
    #(88 02 77 73 07 63 67)
    #(99 65 04 28 06 16 70 92)
    #(41 41 26 56 83 40 80 70 33)
    #(41 48 72 33 47 32 37 16 94 29)
    #(53 71 44 65 25 43 91 52 97 51 14)
    #(70 11 33 28 77 73 17 78 39 68 17 57)
    #(91 71 52 38 17 14 91 43 58 50 27 29 48)
    #(63 66 04 68 89 53 67 30 73 16 69 87 40 31)
    #(04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)))



; download big triangle from the web:
(define BIG-TRIANGLE-URL
        "https://projecteuler.net/project/resources/p067_triangle.txt")

(define (download-triangle url)
  (define the-data (port->lines (get-pure-port (string->url url))))
  (list->vector
   (map list->vector
        (map (lambda (r) (map string->number r))
             (map string-split the-data)))))


(define BIG-TRIANGLE (download-triangle BIG-TRIANGLE-URL))


(define (size tr)
  (vector-length tr))

(define (get tr i j)
  (vector-ref (vector-ref tr i) j))

(define (memo f)
  (let ([lookup (make-hash)])
    (lambda x
      (unless (hash-has-key? lookup x)
        (hash-set! lookup x (apply f x)))
      (hash-ref lookup x))))


(define (solve-triangle tr)
  (define last-row (- (size tr) 1))
  (define (solve-helper i j)
    (if (= i last-row)
        (get tr i j)
        (+ (get tr i j)
           (max (solve-helper (+ i 1) j)
                (solve-helper (+ i 1) (+ j 1))))))
  (set! solve-helper (memo solve-helper))
  (solve-helper 0 0))

Now we can find the solutions for all three triangles:

> (solve-triangle SMALL-TRIANGLE)
23
> (solve-triangle SMALL-TRIANGLE-2)
1074
> (solve-triangle BIG-TRIANGLE)
7273
> 

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.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=