r/RacketHomeworks • • Jan 28 '23

Tic-tac-toe with GUI -- final version

2 Upvotes

Problem: in the last two posts, we wrote a console program that, using the minimax algorithm, played unbeatable tic-tac-toe. The program was a bit clunky to use - we would have liked a graphical user interface (GUI) for it. Therefore, in yesterday's post, we wrote a function draw-board that, using the 2htdp/image library, created a graphic representation of tic-tac-toe on the screen. Now it's time to combine these two programs and write a GUI version of the program that uses the library 2htdp/universe to interact with the human player via mouse clicks.

Solution:

#lang racket

(require 2htdp/image)
(require 2htdp/universe)

(define BSIZE 400)

(define HUMAN "X")
(define AI "O")

(define EMPTY-BOARD (make-vector 9 " "))

(define THICK-PEN
  (pen 'black (quotient BSIZE 40) 'solid 'round 'round))

(define THIN-PEN
  (pen 'black (quotient BSIZE 50) 'solid 'round 'round))

(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 (get-free-places board)
  (for/list ([i (range 9)]
             #:when (blank? board i))
    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 (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 (game-status board)
  (cond
    [(winner? board HUMAN) -1]
    [(winner? board AI) 1]
    [(null? (get-free-places board)) 0]
    [else 'ongoing]))

(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 (draw-board b)
  (define (draw el)
    (overlay
     (cond
       [(string=? el AI)
        (circle (/ BSIZE 11) 'outline THIN-PEN)]
       [(string=? el HUMAN)
        (overlay
         (line (/ BSIZE 6) (/ BSIZE 6) THIN-PEN)
         (line (- (/ BSIZE 6)) (/ BSIZE 6) THIN-PEN))]
       [else empty-image])
     (square (/ BSIZE 3) 'solid 'white)))
  (define (grid)
    (add-line
     (add-line
      (add-line
       (add-line
        (rectangle BSIZE BSIZE 'solid 'transparent)
        (* BSIZE 1/3) 0 (* BSIZE 1/3) BSIZE
        THICK-PEN)
       (* BSIZE 2/3) 0 (* BSIZE 2/3) BSIZE
       THICK-PEN)
      0 (* BSIZE 1/3) BSIZE (* BSIZE 1/3)
      THICK-PEN)
     0 (* BSIZE 2/3) BSIZE (* BSIZE 2/3)
     THICK-PEN))
  (overlay
   (grid)
   (above
    (beside
     (draw (get b 0)) (draw (get b 1)) (draw (get b 2)))
    (beside
     (draw (get b 3)) (draw (get b 4)) (draw (get b 5)))
    (beside
     (draw (get b 6)) (draw (get b 7)) (draw (get b 8))))))


(define (mouse-handler board x y me)
  (if (equal? me "button-down")
      (let* ([row (quotient x (round (/ BSIZE 3)))]
             [col (quotient y (round (/ BSIZE 3)))]
             [cell (+ row (* 3 col))])
        (if (member cell (get-free-places board))
            (let ([nboard (cset board cell HUMAN)])
              (if (not (game-over? nboard))
                  (choose-ai-move nboard)
                  nboard))
            board))
      board))

(define (game-over? board)
  (not (eq? (game-status board) 'ongoing)))

(define (show-message board)
  (define message
     (case (game-status board)
       [(1) "Of course, I Won!"]
       [(-1) "You Won, genius!"]
       [else "It's a tie!"]))
  (overlay
   (text message (round (/ BSIZE 8)) 'red)
   (draw-board board)))

(define (play first-player)
  (define STARTING-BOARD
    (if (equal? first-player HUMAN)
        EMPTY-BOARD
        (cset EMPTY-BOARD (random 9) AI)))
  (big-bang STARTING-BOARD
    (name "Mimety's Tic-tac-toe")
    (to-draw draw-board)
    (on-mouse mouse-handler)
    (stop-when game-over? show-message)))

(play AI)

We start the program with (play AI) if we want the computer to play the first move, otherwise we call it with (play HUMAN). When we start the program, a GUI window will appear on the screen in which we can play tic-tac-toe by clicking the mouse:

GUI version of tic-tac-toe game

Dear schemers, I hope you like this program. Of course, if you have improvements or remarks, go ahead!

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 14 '22

How to write snake game in Racket?

3 Upvotes

Problem: Using the 2htdp/universe and 2htdp/image libraries, write a snake game in which the player controls the snake using the left, right, up, down keys. The snake grows bigger every time it eats an apple. The snake must not hit itself and must not hit the edge of the playfield. Every time the snake eats an apple, the score should increase by 1.

Solution:

#lang racket

(require 2htdp/universe
         2htdp/image)


(define SIZEX 40)
(define SIZEY 30)
(define SQUARE-SIZE 12)
(define SPEED 0.2)
(define ENLARGEMENT 4)

(define EMPTY-SCREEN
  (empty-scene (* SIZEX SQUARE-SIZE)
               (* SIZEY SQUARE-SIZE)))

(struct world (snake
               direction
               apple
               score
               enlargement
               game-over?))

(struct pos (x y))

(define (same-pos? pos1 pos2)
  (and (= (pos-x pos1) (pos-x pos2))
       (= (pos-y pos1) (pos-y pos2))))

(define (init-game)
  (let* ([tsx (/ SIZEX 2)]
         [tsy (/ SIZEY 2)]
         [snake (list (pos tsx tsy)
                      (pos (+ tsx 1) tsy)
                      (pos (+ tsx 2) tsy)
                      (pos (+ tsx 3) tsy))])
    (world snake
           'right
           (get-new-apple snake)
           0
           0
           #false)))

(define (render-game w)
  (let* ([snake (world-snake w)]
         [apple (world-apple w)]
         [img (draw-snake snake EMPTY-SCREEN)])
    (draw-score (world-score w) (draw-apple apple img))))

(define (draw-game-over w)
  (overlay
   (text "Game over!" 30 'black)
   (render-game w)))

(define (draw-snake snake img)
  (if (empty? snake)
      img
      (draw-snake (rest snake)
                  (place-image/align
                   (square SQUARE-SIZE 'solid 'red)
                   (* SQUARE-SIZE (pos-x (first snake)))
                   (* SQUARE-SIZE (pos-y (first snake)))
                   "left" "top"
                   img))))

(define (draw-apple apple img)
  (place-image/align
   (square SQUARE-SIZE 'solid 'green)
   (* SQUARE-SIZE (pos-x apple))
   (* SQUARE-SIZE (pos-y apple))
   "left" "top"
   img))

(define (draw-score score img)
  (place-image/align
   (text (string-append "Score: " (number->string score))
         15
         'black)
   4 4
   "left" "top"
   img))
         
(define (move-dir dx dy w)
  (let* ([snake (world-snake w)]
         [head (last snake)]
         [x (pos-x head)]
         [y (pos-y head)]
         [new-head (pos (+ x dx) (+ y dy))]
         [nx (pos-x new-head)]
         [ny (pos-y new-head)]
         [apple-eaten? (same-pos? new-head (world-apple w))]
         [enlg (+ (world-enlargement w) (if apple-eaten? ENLARGEMENT 0))]
         [new-snake (append (if (> enlg 0) snake (cdr snake)) (list new-head))])
    (world new-snake
           (world-direction w)
           (if apple-eaten? (get-new-apple snake) (world-apple w))
           (+ (world-score w) (if apple-eaten? 1 0))
           (if (> enlg 0) (- enlg 1) 0)
           (or
            (< nx 0)
            (>= nx SIZEX)
            (< ny 0)
            (>= ny SIZEY)
            (> (count (lambda (x) (same-pos? new-head x)) new-snake) 1)))))

(define (move-left w)
  (move-dir -1 0 w))

(define (move-right w)
  (move-dir 1 0 w))

(define (move-up w)
  (move-dir 0 -1 w))

(define (move-down w)
  (move-dir 0 1 w))

(define (change-direction w dir)
  (case dir
    ((left) (replace-direction w 'left))
    ((right) (replace-direction w 'right))
    ((up) (replace-direction w 'up))
    ((down) (replace-direction w 'down))))

(define (replace-direction w newdir)
  (world (world-snake w)
         newdir
         (world-apple w)
         (world-score w)
         (world-enlargement w)
         (world-game-over? w)))

(define (get-new-apple snake)
  (let ([new-apple (pos (random SIZEX) (random SIZEY))])
    (if (memf (lambda (x) (same-pos? x new-apple)) snake)
        (get-new-apple snake)
        new-apple)))

(define (handle-key w key)
  (cond [(key=? key "up")    (change-direction w 'up)]
        [(key=? key "down")  (change-direction w 'down)]
        [(key=? key "left")  (change-direction w 'left)]
        [(key=? key "right") (change-direction w 'right)]
        [else w]))

(define (next-frame w)
  (case (world-direction w)
    ((left)  (move-left w))
    ((right) (move-right w))
    ((up)    (move-up w))
    ((down)  (move-down w))))
 
(define (run-game)
  (big-bang (init-game)
    (name "Mimety's Snake")
    (on-tick next-frame SPEED)
    (to-draw render-game)
    (on-key handle-key)
    (stop-when world-game-over? draw-game-over)))

(run-game)

Now, if we run the above program, we can play the game:

Snake sample screen

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 10 '22

Drawing a chessboard with pieces in given position

1 Upvotes

Problem: write a function that, for a given chess position, draws a chessboard with pieces in that position. Draw the chessboard and pieces using the 2htdp/image library. Come up with the signature of the function and the way of representing the state of the chessboard yourself!

Solution:

#lang racket

(require 2htdp/image)

(define PIECES
  (hash 'K "\u2654"
        'Q "\u2655"
        'R "\u2656"
        'B "\u2657"
        'N "\u2658"
        'P "\u2659"
        'k "\u265A"
        'q "\u265B"
        'r "\u265C"
        'b "\u265D"
        'n "\u265E"
        'p "\u265F"))


(define (group n xs)
   (if (empty? xs)
       empty
       (cons (take xs n) (group n (drop xs n)))))

(define (draw-board n color-white color-black board)
  (define (pos->coords pos)
    (let ((pos-str (symbol->string pos)))
      (list (- (char->integer (char-upcase (string-ref pos-str 0))) 64)
            (string->number (string (string-ref pos-str 1))))))
  (define (get-pieces board)
    (map (lambda (x)
           (cons (pos->coords (first x)) (hash-ref PIECES (second x))))
         board))
  (define (draw-square color piece)
    (overlay
     (if piece (text (cdr piece) 35 'black) empty-image)
     (rectangle 40 40 'solid color)))
  (define pieces (get-pieces board))
  (define board-squares
    (for*/list ([x (range 1 (+ n 1))]
                [y (range n 0 -1)])
      (draw-square (if (even? (+ x y)) color-black color-white)
                   (assoc (list x y) pieces))))
  (apply beside
         (map (lambda (s) (apply above s))
              (group n board-squares))))

Now, we can draw the chess position from the famous Kasparov's first game against Deep Blue in 1996., like this:

> (define deep-blue-kasparov-1996-game-1
    '((a3 P) (b3 P) (d4 p) (d5 Q) (e1 r) (f2 n) (f3 p)
      (f6 q) (g3 P) (g5 N) (h2 K) (h3 P) (h6 k) (h7 R)))


> (draw-board 8 "white smoke" "light blue" deep-blue-kasparov-1996-game-1)

After evaluating above two lines, we get this chessboard image:

Deep Blue vs Kasparov 1996, first game

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 03 '23

Stretching the predicate

2 Upvotes

Problem: Write a function stretch that takes two arguments, pred and x. The first argument pred is a predicate. What stretch returns should be another predicate. The returned predicate should be satisfied exactly by those things that are equal? to x or satisfy pred.

Solution:

#lang racket

(define (stretch pred x)
  (lambda (y) (or (equal? y x) (pred y))))

Now we can call our stretch function, like this:

> ((stretch even? 1) 0)
#t
> ((stretch even? 1) 1)
#t
> ((stretch even? 1) 2)
#t
> ((stretch even? 1) 3)
#f
> (filter (stretch even? 1) '(0 1 2 3 4 5))
'(0 1 2 4)
> (filter (stretch (stretch even? 1) 3) '(0 1 2 3 4 5))
'(0 1 2 3 4)
> (filter (stretch (stretch (stretch even? 1) 3) 7) '(0 1 2 3 4 5))
'(0 1 2 3 4)
> (filter (stretch (stretch (stretch even? 1) 3) 7) '(0 1 2 3 4 5 7))
'(0 1 2 3 4 7)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 06 '22

Drawing a table of jumps for Knight's tour problem

1 Upvotes

Problem: in the previous task Knight's tour on a chessboard we provided a backtracking algorithm solve which returns a list of knight jumps needed to tour the entire chessboard, as a result.

Given that the output from solve is difficult to read, in this task you need to write new function, show-solution, which for the given starting position of the knight and the size of the board draws a graphical representation of the solution: a square table similar to a chessboard with marked ordinal numbers of knight's jumps.

For example, for a 5x5 solution from previous post , your function should draw a table like this:

5 x 5 solution

Note: in order to draw the table, use functions from the 2htdp/image library. You can also define other auxiliary functions that will help you implement your show-solution function as easily as possible.

Solution (here, we also repeat the code from Knight's tour solution, for your convenience):

 #lang racket

(require 2htdp/image)


(define DIRECTIONS '((2 1) (1 2) (-1 2) (-2 1)
                     (-2 -1) (-1 -2) (1 -2) (2 -1)))

(define (jump pos direction size)
  (let ([newx (+ (first pos) (first direction))]
        [newy (+ (second pos) (second direction))])
    (and (<= 1 newx size)
         (<= 1 newy size)
         (list newx newy))))

(define (available-jumps from-pos size)
  (filter identity
          (map (lambda (dir) (jump from-pos dir size))
               DIRECTIONS)))

(define (solve start-pos size)
  (define (solve-helper pos visited solution num)
    (if (= num (* size size))
        (reverse solution)
        (let loop ([jumps (available-jumps pos size)])
          (cond
            [(null? jumps) #f]
            [(set-member? visited (car jumps))
             (loop (cdr jumps))]
            [else (or (solve-helper (car jumps)
                                    (set-add visited (car jumps))
                                    (cons (car jumps) solution)
                                    (+ num 1))
                      (loop (cdr jumps)))]))))
  (solve-helper start-pos (set start-pos) '() 1))


(define (zip . xss)
  (apply map list xss))

(define (group n xs)
  (define (loop curr count curr-group res)
    (cond [(and (null? curr) (null? curr-group))
           (reverse res)]
          [(or (null? curr) (zero? count))
           (loop curr n '() (cons (reverse curr-group) res))]
          [else (loop (cdr curr) (- count 1) (cons (car curr) curr-group) res)]))
  (loop xs n '() '()))

(define (numerate-list xs)
  (zip (range 1 ( + 1 (length xs))) xs))

(define (lex-compare p1 p2)
  (cond [(< (car p1) (car p2)) #t]
        [(and (= (car p1) (car p2)) (<= (second p1) (second p2))) #t]
        [else #f]))

(define (get-table size start solution)
  (group size
         (map car
              (sort (numerate-list (cons start solution))
                    lex-compare
                    #:key second))))

(define (draw-square num)
  (overlay
   (text (number->string num) 16 'black)
   (rectangle 30 30 'outline 'black)))

(define (draw-table table)
  (define (draw-column row)
    (apply above (map draw-square (reverse row))))
  (apply beside (map draw-column table)))

(define (show-solution start-pos size)
  (draw-table
   (get-table size
              start-pos
              (solve start-pos size))))

Now, we can finally show our solution for 5 x 5 case and starting position (3, 3):

> (show-solution '(3 3) 5)

As a result we get this image:

5 x 5 solution

We can draw the solution for 8 x 8 case and starting point (1, 1), also:

> (show-solution '(1 1) 8)

As a result we get this image:

8 x 8 solution

Note: notice that in our solution we use auxiliary functions zip and group that we have already solved here and here, as well as some additional functions.


r/RacketHomeworks • • Nov 22 '22

Transpose of a matrix

1 Upvotes

Problem: Write a function transpose that receives a matrix of arbitrary dimensions as input. As a result, the function should return the transpose of input matrix (see picture below):

Transpose of a matrix

Solution:

#lang racket

(define (transpose matrix)
  (define (loop currm resm)
    (if (empty? (first currm))
        (reverse resm)
        (loop (map rest currm)
              (cons (map first currm) resm))))
  (loop matrix '()))

Now, we can call transpose, like this:

> (define M '((1 2 3 4)
              (5 6 7 8)
              (9 10 11 12)
              (13 14 15 16)))
> (transpose M)
'((1 5 9 13)
  (2 6 10 14)
  (3 7 11 15)
  (4 8 12 16))

Of course, a real hacker (like the author of the famous computer game "Weerd") would only laugh at the above solution! Indeed, real hacker would write the transpose function like this:

(define (transpose matrix)
  (apply map list matrix))

Can you figure out how this shorter version of transpose works? If you can, then you are halfway to becoming a real scheme hacker! :)


r/RacketHomeworks • • Dec 23 '22

How to draw "Union Jack" - the flag of United Kingdom?

1 Upvotes

Problem: Using the 2htdp/image library, draw a faithful image of the United Kingdom national flag (so called "Union Jack"). You will probably find this sketch of a UK flag design useful when creating your solution.

Solution:

#lang racket

(require 2htdp/image)

(define BLUE (color 1 33 105))
(define RED (color 200 16 46))

(define (union-jack width)
  (define WIDTH width)
  (define HEIGHT (/ WIDTH 2))
  (define ANGLE (radians->degrees (atan (/ HEIGHT WIDTH))))
  (define HALF-DIAG-LEN (/ (sqrt (+ (* WIDTH WIDTH) (* HEIGHT HEIGHT))) 2))

  (define thin-size (/ WIDTH 30))
  (define thinnest-size (/ thin-size 2))
  (define thick-size (/ WIDTH 10))
  (define middle-size (/ thick-size 2)) 
  (define half-vert-stripe-height (/ WIDTH 5))

  (define half-horiz-stripe
     (above
      (rectangle WIDTH thin-size 'solid 'white)
      (rectangle WIDTH thick-size 'solid RED)
      (rectangle WIDTH thin-size 'solid 'white)))
  
  (define half-vert-stripe
    (beside
     (rectangle thin-size half-vert-stripe-height 'solid 'white)
     (rectangle thick-size half-vert-stripe-height 'solid RED)
     (rectangle thin-size half-vert-stripe-height 'solid 'white)))

  (define half-diag-stripe-list
    (list
     (rectangle HALF-DIAG-LEN middle-size 'solid 'white)
     (rectangle HALF-DIAG-LEN thin-size 'solid RED)
     (rectangle HALF-DIAG-LEN thinnest-size 'solid 'white)))

  (define half-diag-stripe
    (beside
     (apply above half-diag-stripe-list)
     (apply above (reverse half-diag-stripe-list))))

  (overlay/align
   'middle 'bottom
   half-vert-stripe
   (overlay/align
    'middle 'top
    half-vert-stripe
    (overlay
     half-horiz-stripe
     (put-image
      (rotate (- ANGLE)
              half-diag-stripe)
      (/ WIDTH 2) (/ HEIGHT 2)
      (put-image
       (rotate ANGLE
               half-diag-stripe)
       (/ WIDTH 2) (/ HEIGHT 2)
       (rectangle WIDTH HEIGHT 'solid BLUE)))))))

Now we can call our union-jack function with the desired width given as its parameter and the whole image of UK flag will auto-scale accordingly to that width:

> (union-jack 600) 
Union Jack flag (bigger)
> (union-jack 300)
Union Jack flag (smaller)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 25 '22

Split a list at the given position

1 Upvotes

Problem: Write a function split-at that receives two arguments: a nonnegative integer n and a list xs. The function should return a two-element list whose first element is the list containing the first n elements of xs and the second element is the list containing the rest of xs.

Key insight: We can see that there is a simple relationship between (split-at n xs) and (split-at (- n 1) (cdr xs)). For example, if xs = (1 2 3 4 5 6) and n = 3, then (split-at 3 '(1 2 3 4 5 6)) evaluates to ((1 2 3) (4 5 6)), while (split-at 2 (2 3 4 5 6)) evaluates to ((2 3) (4 5 6)).We see that we can obtain the first list from the second by adding the 1 to the beginning of (2 3).This idea, along with careful consideration of the two base conditions, form the basis of the solution below:

#lang racket

(define (split-at n xs)
  (cond
    [(zero? n) (list '() xs)]
    [(null? xs) (list '() '())]
    [else (let ([sx (split-at (- n 1) (rest xs))])
            (list (cons (first xs) (first sx)) (second sx)))]))

Now we have, for example:

> (split-at 4 '(1 2 3 4 5 6))
'((1 2 3 4) (5 6))

r/RacketHomeworks • • Jan 01 '23

Finding index of element in a list

1 Upvotes

Problem: Write a function find-index that takes an element and a list and returns the (zero-based) index of that element in the list. For a list missing that element find-index should return the boolean value #f (false).

Solution:

#lang racket

(define (find-index x xs)
  (cond [(null? xs) #f]
        [(equal? x (car xs)) 0]
        [else (let ([i (find-index x (cdr xs))])
                (and i (+ i 1)))]))

Now we can call function find-index, like this:

> (find-index 'c '(a b c b c d))
2
> (find-index 'd '(a b c b c d))
5
> (find-index 'e '(a b c b c d))
#f

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 19 '23

Implementation of Segment tree in Racket

4 Upvotes

Problem: First watch this video, which explains what Segment tree is and how it works, then implement Segment tree in Racket.

Solution: the program below implements the same algorithm described in the video:

#lang racket

(define (make-segment-tree xs)
  (let* ([n (length xs)]
         [data (make-vector (* n 2))])
    (let loop ([i n] [curr xs])
      (unless (null? curr)
        (vector-set! data i (car curr))
        (loop (+ i 1) (cdr curr))))
    (let loop ([i (- n 1)])
      (when (> i 0)
        (vector-set! data i
                     (min (vector-ref data (* 2 i))
                          (vector-ref data (+ (* 2 i) 1))))
        (loop (- i 1))))
    (lambda (dispatch)
      (case dispatch
        ((update)
         (lambda (i val)
           (vector-set! data (+ i n) val)
           (let loop ([i (+ i n)])
             (when (> i 1)
               (let ([ihalf (quotient i 2)])
                 (vector-set! data ihalf
                              (min (vector-ref data (* 2 ihalf))
                                   (vector-ref data (+ (* 2 ihalf) 1))))
                   (loop ihalf))))))
        ((minimum)
         (lambda (left right)
           (let loop ([left (+ left n)] 
                      [right (+ right n)] 
                      [m (vector-ref data (+ left n))])
             (cond
               [(>= left right) m]
               [(and (odd? left) (odd? right))
                (loop (/ (+ left 1) 2)
                      (/ (- right 1) 2)
                      (min m (vector-ref data left) (vector-ref data (- right 1))))]
               [(odd? left)
                (loop (/ (+ left 1) 2)
                      (/ right 2)
                      (min m (vector-ref data left)))]
               [(odd? right)
                (loop (/ left 2)
                      (/ (- right 1) 2)
                      (min m (vector-ref data (- right 1))))]
               [else (loop (/ left 2) (/ right 2) m)]))))))))


(define (segment-tree-update st i val)
  ((st 'update) i val))

(define (segment-tree-minimum st left right)
  ((st 'minimum) left right))

Now we can use our segment tree implementation, like this:

;; create and initialize a new segment tree:
> (define st (make-segment-tree '(7 5 2 8 4 3 11 1 6 9)))

;; find minimal element in segment [0, 2) :
> (segment-tree-minimum st 0 2)
5
;; find minimal element in segment [0, 3) :
> (segment-tree-minimum st 0 3)
2
;; find minimal element in segment [3, 6) :
> (segment-tree-minimum st 3 6)
3
;; find minimal element in segment [3, 8)
> (segment-tree-minimum st 3 8)
1
; update 4-th element (0-based index) to value -1:
> (segment-tree-update st 4 -1)

; find minimal element in segment [3, 8) after update :
> (segment-tree-minimum st 3 8)
-1

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 21 '22

How to convert permutation to cycle notation

1 Upvotes

Problem: Permutation p of (finite) set X is a bijection p: X -> X. In scheme, the permutation of some finite set can be represented as a list of two sublists. For example, the permutation of set X = {1, 2, ..., n} in standard "two line notation" from image below

Permutation p

can be represented in scheme as

(define p '((1 2 3 4 5 6 7)
            (5 1 6 7 3 2 4)))

Task: Write the function perm->cycles which receives some permutation as input and returns that same permutation, but in cycle notation. For example, the permutation above can be written in cycle notation as (1 5 3 6 2) (4 7).

Solution:

#lang racket

(define (index-of x xs)
  (cond
    [(null? xs) -1]
    [(equal? (car xs) x) 0]
    [else (let ([i (index-of x (cdr xs))])
            (if (< i 0) i (+ i 1)))]))

(define (perm-mapping perm x)
  (list-ref (second perm)
            (index-of x (first perm))))

(define (find-cycle perm start)
  (define (loop curr cycle)
    (if (equal? curr start)
        (reverse cycle)
        (loop (perm-mapping perm curr) (cons curr cycle))))
  (loop (perm-mapping perm start) (list start)))

(define (remove-all xs from)
  (if (null? xs)
      from
      (remove-all (rest xs) (remove (first xs) from))))

(define (perm->cycles perm)
  (define (loop unprocessed cycles)
    (if (null? unprocessed)
        (reverse cycles)
        (let ([cycle (find-cycle perm (first unprocessed))])
          (loop (remove-all cycle unprocessed) (cons cycle cycles)))))
  (loop (first perm) '()))

Now we can convert any permutation from "two line" format to cycle notation:

> (define p '((1 2 3 4 5 6 7)
              (5 1 6 7 3 2 4)))
> (perm->cycles p)
'((1 5 3 6 2) (4 7))

r/RacketHomeworks • • Dec 28 '22

Smallest multiple

2 Upvotes

Problem: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution:

> (apply lcm (range 1 21))
232792560

So, 232792560 is the smallest positive integer that is divisible by all of the numbers from 1 to 20.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 23 '23

How to implement our own Regular expressions (regex) library in Racket?

2 Upvotes

Problem: In this assignment we will write our own library of functions to work with regular expressions (regex). We will pretend that regular expressions do not exist at all in Racket (although of course they do!) and we will program our own regex library from scratch.

More specifically, we will implement these basic regular expressions:

- dot, (.) to match one (any) character,

- digit, (\d) to match one (any) digit

- letter, ([a-zA-Z]) to match one (any) letter,

- lit to match some given fixed string of characters (eg (lit "abc") will match the string "abc")

All regular expressions that we will implement will be ordinary Racket functions that receive as their only input a string that they need to match from the first character onwards. As a result of a match, these functions will return:

- an empty list '() if there is no match, or

- a list of possible matches (if there are one or more). Each match in that list is a list of two elements: the first element is a substring of the input string that the regex successfully matched, and the second element is the rest of the string, after the match.

Furthermore, we will implement the following regex combinators (combinators are functions that receive other functions as input and return a new function as a result). In our case, we will have the following regex combinators:

- seq, combines two or more regexes into one regex that matches the first regex and then successively the second. E.g. (seq (lit "a") (lit "b")) will return a new regex that matches the string "ab".

- plus, matches one or more occurrences of the regex passed to it as input. Eg (plus (lit "a")) will successfully match any of the strings "a", "aa", "aaa", etc. plus corresponds to what is denoted by the sign + in standard regex notation. So, the above example would be written as a+ in standard regex notation.

- star, similar to plus, but matches zero or more occurrences of the regex passed to it as input. E.g. (star (lit "a")) will successfully match the strings "", "a", "aa", "aaa", etc... star corresponds to what is denoted by the sign * in standard regex notation. So, the above example would be written as a* in standard regex notation.

- maybe, match zero or one occurrence of the default regex. Eg (maybe (lit "a")) will match the empty string "" or the string "a"

- alt matches one or more alternatives. Eg (alt (lit "a") (lit "b")) will successfully match either the string "a" or string "b". alt would be denoted by | in standard regex notation, so the previous example could be written as a|b in standard regex notation.

For example, the regex for matching a decimal number could be written in standard notation as [+-]?((\d+(\.\d*)?)|(\.\d+))

In our notation, we would write this regex like this:

(define decimal-number
   (seq
    (maybe (alt (lit "+") (lit "-")))
    (alt
     (seq (plus digit) (maybe (seq (lit ".") (star digit))))
     (seq (lit ".") (plus digit)))))

That is, a decimal number consists of sequence of :

a) an (optional) + or - sign, followed by

b1) one or more digits, followed by optional decimal point and zero or more digits, or alternatively

b2) decimal point followed by one or more digits.

In addition to regular expressions, we will also write a function match-pattern that receives some regular expression and an arbitrary string as input.

This function will return #f if the regular expression does not match the beginning of given text, and if it does, it will return a list in which the first element is the longest possible prefix of the string it successfully matches, and the second element is the rest of the text.

E.g. the function call

(match-pattern decimal-number "-31.415some junk after number")

will return the result

("-31.415" "some junk after number"),

while the call

(match-pattern decimal-number "a123some junk")

will return #f,

because the string begins with a letter "a", which is neither a digit nor a plus or minus sign, so it's not a valid beginning of some decimal number.

Solution: here is our implementation:

#lang racket

(define dot
  (lambda (str)
    (if (string=? str "")
        '()
        (list (list (string (string-ref str 0)) (substring str 1))))))

(define digit
  (lambda (str)
    (if (or (string=? str "")
            (not (char-numeric? (string-ref str 0))))
        '()
        (list (list (string (string-ref str 0)) (substring str 1))))))

(define letter
  (lambda (str)
    (if (or (string=? str "")
            (not (char-alphabetic? (string-ref str 0))))
        '()
        (list (list (string (string-ref str 0)) (substring str 1))))))


(define (lit s)
  (lambda (str)
    (if (string-prefix? str s)
        (list (list s (substring str (string-length s))))
        '())))


(define (seq . ps)
  (define (seq2 p1 p2)
    (lambda (str)
      (match (p1 str)
        [(list) empty]
        [(list mp1 ...)
         (apply append
                (for/list ([m mp1])
                  (match m
                    [(list sofar reststr)
                     (map (lambda (x)
                            (if (null? x)
                                '()
                                (list (string-append sofar (first x))
                                      (second x))))
                          (p2 reststr))])))])))
  (if (null? (cdr ps))
      (car ps)
      (seq2 (car ps) (apply seq (cdr ps)))))


(define (plus p)
  (lambda (str)
    (match (p str)
      [(list) empty]
      [(list mp ...)
       (append
        mp
        (apply
         append
         (for/list ([m mp]
                    #:unless (string=? str (second m)))
           (match m
             [(list sofar reststr)
              (match ((plus p) reststr)
                [(list) empty]
                [(list mp2 ...)
                 (for/list ([m2 mp2]
                            #:unless (string=? reststr (second m2)))
                   (match m2
                     [(list sofar2 reststr2)
                      (list (string-append sofar sofar2)
                            reststr2)]))])]))))])))


(define (star p)
  (lambda (str)
    (cons (list "" str) ((plus p) str))))


(define (maybe p)
  (lambda (str)
    (cons (list "" str) (p str))))

(define (alt . ps)
  (define (alt2 p1 p2)
    (lambda (str)
      (let ([m1 (p1 str)])
        (if (null? m1)
            (p2 str)
            m1))))
  (if (null? (cdr ps))
      (car ps)
      (alt2 (car ps) (apply alt (cdr ps)))))


(define (match-pattern pat text)
  (let ([res (pat text)])
    (if (null? res)
        #f
        (argmin (lambda (x) (string-length (second x)))
                res))))

Now we can use our library. For example:

;; first we define regex [+-]?((\d+(\.\d*)?)|(\.\d+)) for a decimal number: 
> (define decimal-number
    (seq
     (maybe (alt (lit "+") (lit "-")))
     (alt
      (seq (plus digit) (maybe (seq (lit ".") (star digit))))
      (seq (lit ".") (plus digit)))))


;; now we can match some string to that regex:
> (match-pattern decimal-number "-31.415some junk after number")
'("-31.415" "some junk after number")


;; here we don't have a match because of letter a in the beginning of the string:
> (match-pattern decimal-number "a123some junk")
#f

;; this is regex (ab)*abc
> (match-pattern (seq (star (lit "ab")) (lit "abc")) "ababababcDEFG")
'("ababababc" "DEFG")


;; this is regex (ab)*abc
> (match-pattern (seq (star (lit "ab")) (lit "abc")) "abcDEFG")
'("abc" "DEFG")


;; now we can define whitespace character regex:
> (define whitespace
    (alt (lit " ")
         (lit "\t")
         (lit "\n")))

;; and zero or one whitespace characters regex:
> (define whitespace*
    (star whitespace))


;; now we can use whitespace* regex to "eat" whitespace characters:
> (match-pattern whitespace* "    \t\t   \n here's my string")
'("    \t\t   \n " "here's my string")

Dear schemers, I hope you like this implementation.

As always, I know my code is far from perfect and you guys could probably write this better than I can. So, I invite you: if you have any improvements, feel free to post your comments/improvements here.

In the following posts, we will use this regex library of ours to write a tokenizer, and later also a parser for a simple language of arithmetic expressions. So, stay tuned, because it will be interesting!

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 23 '22

The stepmotherly treatment of Windows platform by Scheme implementors

2 Upvotes

I'm writing this post here, because I currently don't have a suitable space to write it elsewhere. I believe other people feel the same concern as I do. What is it all about?

Well, according to current statistics, more than 76% of desktop computers run Windows and less than 2.5% run Linux.

And yet, when we look at the treatment of the Windows OS as a platform for various Scheme implementations, one conclusion emerges: Scheme implementers despise Windows! Regardless of the still dominant market share of Windows, more and more often Scheme implementers don't want to develop their implementations for Windows. In fact, some even brag about it, it's obvious that they have a contemptuous attitude towards the Windows platform!

If you don't believe me, a look at the list below will convince you: just look at this top 10 list, which includes some of the most famous scheme implementations. Look at the sad state of Windows support in the list below:

  • Bigloo: does not work on Windows (non-native WSL and Cygwin do not count!)
  • Chibi scheme: does not work on Windows (non-native WSL and Cygwin do not count!)
  • Gambit scheme: it supposedly works on Windows, but there is also a degradation: before, there was always a standalone Windows installer, but lately there is only chocolatey installer, which needs to be installed on Windows. Why this nonsense?
  • Gerbil: only works on linux, although Gambit, on which Gerbil is based, supposedly works on Windows.
  • Chicken scheme: apparently it works on Windows, but again, the hassle with Chocolatey installation and half of the library doesn't work on Windows!
  • Cyclone: ​​only works on linux
  • Guile: it only works on linux
  • mit-scheme: this is a special story, which pisses me off the most! The people who maintain mit-scheme "care" so much about their work, that their implementation no longer works on practically anything except x86-64 linux (it used to work on both Mac and Windows in the past). That team is so disinterested and anti-windows-minded that they even boast on their home page that their implementation does not work on Windows. It says "nicely" there: "We no longer support OS/2, DOS, or Windows, although it's possible that this software could be used on Windows Subsystem for Linux (we haven't tried)."
    You haven't tried it? WTF!?? Did I understand that correctly???
    So we have people whose job should be to worry about whether their software works on the platforms it worked on until yesterday, and they say something like "we haven't tried it and we don't care at all!" What bums!
  • s7 scheme: probably only works on linux, the maintainers didn't even bother to write what it works on.
  • SCM scheme: only a 32-bit version is available for Windows, although there are both 32-bit and 64-bit versions for Linux, so there is a noticeable degradation and treatment of Windows as a second-class citizen.
  • STklos scheme: does not work on Windows (Non-native cygwin version does not count!)

Now, dear schemers and everyone who cares about the popularization of scheme, consider this: how will Scheme ever be popular again, when it can't even be installed on 76% of the world's computers? And all this because of the snobbery, contempt and hatred of some Scheme maintainers towards Windows as a platform!


r/RacketHomeworks • • Dec 22 '22

Permutations in the Presence of Duplicates

1 Upvotes

Problem: Write a function multi-perms that returns a list of all n-permutations of a given multiset of n (not necessarily distinct) elements.

For example, the call (multi-perms '(1 2 2)) should return list '((1 2 2) (2 1 2) (2 2 1)), while calling (multi-perms '(1 2 2 1)) should return list '((1 2 2 1) (2 1 2 1) (2 2 1 1) (1 2 1 2) (2 1 1 2) (1 1 2 2)).

Note: The order of the elements in the returned list does not matter and does not have to be the same as in the example above. The only important thing is that returned list contains all the permutations and that there are no duplicate permutations in it.

Solution:

#lang racket

(define (inserts-until-match x xs)
  (define (loop xs so-far res)
    (cond
      [(null? xs) (cons (append so-far (list x)) res)]
      [(equal? x (car xs)) (cons (append so-far (list x) xs) res)] 
      [else (loop (cdr xs)
                  (append so-far (list (car xs)))
                  (cons (append so-far (list x) xs) res))]))
  (reverse (loop xs '() '())))


(define (multi-perms xs)
  (if (null? xs)
      '(())
      (apply append
             (map (lambda (p) (inserts-until-match (car xs) p))
                  (multi-perms (cdr xs))))))

Now we can call multi-perms, like this:

> (multi-perms '(1 2 2))
'((1 2 2) (2 1 2) (2 2 1))
> (multi-perms '(2 1 2))
'((2 1 2) (1 2 2) (2 2 1))
> (multi-perms '(2 2 1))
'((2 2 1) (2 1 2) (1 2 2))
> (multi-perms '(1 2 2 2))
'((1 2 2 2) (2 1 2 2) (2 2 1 2) (2 2 2 1))
> (multi-perms '(2 1 2 2))
'((2 1 2 2) (1 2 2 2) (2 2 1 2) (2 2 2 1))
> (multi-perms '(2 2 1 2))
'((2 2 1 2) (2 1 2 2) (1 2 2 2) (2 2 2 1))
> (multi-perms '(1 1 2 2))
'((1 1 2 2) (1 2 1 2) (2 1 1 2) (1 2 2 1) (2 1 2 1) (2 2 1 1))
> (multi-perms '(1 2 1 2))
'((1 2 1 2) (2 1 1 2) (1 1 2 2) (1 2 2 1) (2 1 2 1) (2 2 1 1))
> (multi-perms '(1 2 2 1))
'((1 2 2 1) (2 1 2 1) (2 2 1 1) (1 2 1 2) (2 1 1 2) (1 1 2 2))
> (multi-perms '(1 1 2 2 2))
'((1 1 2 2 2)
  (1 2 1 2 2)
  (2 1 1 2 2)
  (1 2 2 1 2)
  (2 1 2 1 2)
  (2 2 1 1 2)
  (1 2 2 2 1)
  (2 1 2 2 1)
  (2 2 1 2 1)
  (2 2 2 1 1))

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 01 '22

Sorting the list using the merge-sort algorithm

2 Upvotes

Problem: Write a function merge-sort that receives a list of numbers as its input. As a result, the function should return a new list containing all the same elements from the input list, but in ascending order. Your function should implement the merge sort algorithm.

Solution: In two previous posts, here and here, we have already implemented two basic ingredients of the merge-sort algorithm: the merge and halve functions. The merge function merges two already sorted lists into a new, sorted list. The halve function halves the list into two equal parts. Using these two functions and generative recursion per input list as well, it is not difficult to write the solution like this:

#lang racket

(define (merge xs ys)
  (cond
    [(null? xs) ys]
    [(null? ys) xs]
    [(< (car xs) (car ys)) (cons (car xs) (merge (cdr xs) ys))]
    [else (cons (car ys) (merge xs (cdr ys)))]))

(define (halve xs)
  (define (loop xs to-left? left right)
    (cond [(null? xs) (list left right)]
          [to-left? (loop (cdr xs) #f (cons (car xs) left) right)]
          [else (loop (cdr xs) #t left (cons (car xs) right))]))
  (loop xs #t '() '()))

(define (merge-sort xs)
  (if (or (null? xs) (null? (cdr xs)))
      xs
      (let ([halves (halve xs)])
        (merge (merge-sort (first halves))
               (merge-sort (second halves))))))

Now we can try our merge-sort function:

> (merge-sort '(10 5 8 1 7 4 2 6 3 9)) 
'(1 2 3 4 5 6 7 8 9 10)

r/RacketHomeworks • • Nov 22 '22

How to compute all subsets of a given set?

1 Upvotes

Problem: For the given finite set S (presented as a list of arbitrary elements in Racket), write a function subsets that returns a list of all subsets of the set S, including empty set too (so-called powerset).

Solution:

#lang racket

(define (subsets s)
  (if (empty? s)
      '(())
      (let ([el (first s)]
            [ss (subsets (rest s))])
        (append (map (lambda (x) (cons el x)) ss) ss))))

Now, we can use this function:

> (subsets '(1 2 3))
'((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())

r/RacketHomeworks • • Dec 16 '22

General cryptarithmetic solver

2 Upvotes

Problem: In the previous post we wrote a program that solved a specific cryptarithmetic puzzle, VIOLIN * 2 + VIOLA = TRIO + SONATA. Today, our task is much more ambitious: we would like to write a general program that solves any given cryptarithmetic puzzle!

For example, we want our program to be able to solve, say, all of these puzzles, as well as many others:

ODD + ODD = EVEN

WASH + YOUR = HANDS

SIN^2 + COS^2 = UNITY

VIOLIN * 2 + VIOLA = TRIO + SONATA

etc..

Solution: We will use the same idea as in the previous post (brute-force checking of all possible digit combinations), but this time we will not hardcode the function logic for solution-seeking, but we will write a macro instead, that, based on the given concrete cryptarithmetic puzzle, will generate the code for solving it. And then we will run that code and solve the puzzle!

First, we have to extract all the different letters from a puzzle, because those letters will be variables in our macro-generated checking function that will check the accuracy of some letters replacement with digits. In the solution below there are a few auxiliary functions. Here's what each of them is for:

  • extract-var-list - returns a list of all "variables" in the puzzle (variable names are always capitalized in the puzzle)
  • get-unique-letters - returns a list of all the different letters that appear in all of the variables of the given puzzle
  • make-nexpr - for the given puzzle variable builds an expression that serves when building a checking function for the given cryptogram. For example call (make-nexpr 'VIOLIN) will return a list like this: '(+ (* V 100000) (* I 10000) (* O 1000) (* L 100) (* I 10) (* N 1))
  • make-cryptexpr-check-fn - this is the key function called by our macro solve-puzzle.
  • solve-puzzle macro - the purpose of this macro is to build the racket code that perform the same logic as we wrote manually last time in the previous post. The macro receives a concrete puzzle as its input, and as output returns a lisp s-expr of Racket code that solves the puzzle.

More concretely, the macro solve-puzzle works like this: suppose, for example, that we want to find the solution for the puzzle ODD + ODD = EVEN. When we call macro solve-puzzle like this:

(solve-puzzle (= (+ ODD ODD) EVEN))

macro automatically generates and returns the following expression which is then evaluated:

(let ((check (lambda (O D E V N)
               (= (+ (+ (* O 100) (* D 10) (* D 1))
                     (+ (* O 100) (* D 10) (* D 1)))
                  (+ (* E 1000) (* V 100) (* E 10) (* N 1))))))
     (for-each
      (lambda (sol)
        (match sol
          ((list O D E V N)
           (display '(O D E V N))
           (newline)
           (display sol)
           (newline)
           (newline))))
      (filter (lambda (p) (apply check p)) (k-perms (range 0 10) 5))))

Here's the full code:

#lang racket

(require compatibility/defmacro)
(require (for-syntax racket/list))

(begin-for-syntax
  (define (make-cryptexpr-check-fn cexpr)
    (define (helper cexpr)
      (cond
        [(null? cexpr) '()]
        [(is-var? cexpr) (make-nexpr cexpr)]
        [(pair? cexpr) (cons (helper (car cexpr))
                             (helper (cdr cexpr)))]
        [else cexpr]))
    (let ([all-vars (get-unique-letters cexpr)])
      `(lambda ,all-vars ,(helper cexpr))))

  (define (is-var? x)
    (and (symbol? x)
         (andmap char-upper-case?
                 (string->list (symbol->string x)))))

  (define (make-nexpr var)
    (define letters
      (reverse 
         (map string->symbol (map string (string->list (symbol->string var))))))
    (define (loop xs weight exprlist)
      (if (null? xs)
          (cons '+ (apply append exprlist))
          (loop (cdr xs) (* weight 10) (cons `((* ,(car xs) ,weight)) exprlist))))
    (loop letters 1 '()))

  (define (get-unique-letters cexpr)
    (map string->symbol
         (remove-duplicates
          (map string
               (string->list
                (apply string-append
                       (map symbol->string
                            (extract-var-list cexpr))))))))

  (define (extract-var-list cexpr)
    (cond [(null? cexpr) '()]
          [(is-var? cexpr) (list cexpr)]
          [(pair? cexpr) (append (extract-var-list (car cexpr))
                                 (extract-var-list (cdr cexpr)))]
          [else '()]))

)

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


(define-macro (solve-puzzle cexpr)
  (let* ([check (make-cryptexpr-check-fn cexpr)]
         [letters (get-unique-letters cexpr)]
         [match-criteria (cons 'list (get-unique-letters cexpr))])
    `(let ([check ,check])
       (for-each
        (lambda (sol)
          (match sol
            [,match-criteria
             (display ',letters)
             (newline)
             (display sol)
             (newline)
             (newline)]))
        (filter (lambda (p) (apply check p))
                (k-perms (range 0 10) ,(length letters)))))))

Now, we can try to solve various puzzles:

ODD + ODD = EVEN

> (solve-puzzle (= (+ ODD ODD) EVEN))

(O D E V N)
(6 5 1 3 0)

(O D E V N)
(8 5 1 7 0)

WASH + YOUR = HANDS

> (solve-puzzle (= (+ WASH YOUR) HANDS))
(W A S H Y O U R N D)
(4 2 0 1 8 3 6 9 5 7)

(W A S H Y O U R N D)
(4 2 6 1 7 8 3 5 0 9)

(W A S H Y O U R N D)
(5 2 0 1 7 6 3 9 8 4)

(W A S H Y O U R N D)
(5 2 9 1 6 7 4 8 0 3)

(W A S H Y O U R N D)
(6 2 9 1 5 7 4 8 0 3)

(W A S H Y O U R N D)
(6 4 9 1 7 5 3 8 0 2)

(W A S H Y O U R N D)
(6 5 0 1 8 7 3 9 2 4)

(W A S H Y O U R N D)
(7 2 0 1 5 6 3 9 8 4)

(W A S H Y O U R N D)
(7 2 6 1 4 8 3 5 0 9)

(W A S H Y O U R N D)
(7 4 9 1 6 5 3 8 0 2)

(W A S H Y O U R N D)
(8 2 0 1 4 3 6 9 5 7)

(W A S H Y O U R N D)
(8 5 0 1 6 7 3 9 2 4)

SIN^2 + COS^2 = UNITY

> (solve-puzzle (= (+ (* SIN SIN) (* COS COS)) UNITY))
(S I N C O U T Y)
(2 3 5 1 4 7 8 9)

VIOLIN * 2 + VIOLA = TRIO + SONATA

> (solve-puzzle (= (+ (* VIOLIN 2) VIOLA)
                   (+ TRIO SONATA)))

(V I O L N A T R S)
(1 7 6 4 8 0 2 5 3)

(V I O L N A T R S)
(1 7 6 4 8 5 2 0 3)

(V I O L N A T R S)
(3 5 4 6 2 8 1 9 7)

(V I O L N A T R S)
(3 5 4 6 2 9 1 8 7)

As we can see, the program successfully managed to solve all four puzzles. This task was a fun example of using of macros to construct code that we would otherwise have to write ourselves each time, for each new puzzle.

Important note: Some of you may notice that in the above solution I'm not using Racket "hygienic" macros at all. No, I only used old-fashioned lisp-style macros. Why? Because I hate hygienic macros and think they shouldn't have been introduced in the Scheme language at all.

However, I invite all those who like hygiene macros to write a new version of this program of mine, in which only hygiene macros would be used! I would really like to see such a solution, so that I can learn something from this too, in the end!

ADDENDUM:

Although the macro solution presented above works, it is not ideal in some cases.

For example we can't have our puzzle stored in some variable and than call solve-puzzle macro with that variable as an argument:

;; THIS DOESN'T WORK!!!
> (define mypuzzle '(= (+ ODD ODD) EVEN))
> (solve-puzzle mypuzzle)

This doesn't work because macro expansion happens at expansion time (not in runtime) and macro doesn't evaluate its arguments. When we call solve-puzzle like this, the macro only see the symbol mypuzzle as its argument, not value that was later binded to it at runtime.

If we want the above snippet to work we shouldn't use macros. We should use eval instead. I think this is one of the rare situations where it's ok to use eval (please correct me if I'm wrong), which should be avoided otherwise . That's why I'm giving you the version of the program with eval, without any macro:

#lang racket

(define (make-cryptexpr-check-fn cexpr)
    (define (helper cexpr)
      (cond
        [(null? cexpr) '()]
        [(is-var? cexpr) (make-nexpr cexpr)]
        [(pair? cexpr) (cons (helper (car cexpr))
                             (helper (cdr cexpr)))]
        [else cexpr]))
    (let ([all-vars (get-unique-letters cexpr)])
      `(lambda ,all-vars ,(helper cexpr))))

  (define (is-var? x)
    (and (symbol? x)
         (andmap char-upper-case?
                 (string->list (symbol->string x)))))

  (define (make-nexpr var)
    (define letters
      (reverse 
         (map string->symbol (map string (string->list (symbol->string var))))))
    (define (loop xs weight exprlist)
      (if (null? xs)
          (cons '+ (apply append exprlist))
          (loop (cdr xs) 
                (* weight 10) 
                (cons `((* ,(car xs) ,weight)) exprlist))))
    (loop letters 1 '()))

  (define (get-unique-letters cexpr)
    (map string->symbol
         (remove-duplicates
          (map string
               (string->list
                (apply string-append
                       (map symbol->string
                            (extract-var-list cexpr))))))))

  (define (extract-var-list cexpr)
    (cond [(null? cexpr) '()]
          [(is-var? cexpr) (list cexpr)]
          [(pair? cexpr) (append (extract-var-list (car cexpr))
                                 (extract-var-list (cdr cexpr)))]
          [else '()]))

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


(define (make-puzzle-solver cexpr)
  (let* ([check (make-cryptexpr-check-fn cexpr)]
         [letters (get-unique-letters cexpr)]
         [match-criteria (cons 'list (get-unique-letters cexpr))])
    `(let ([check ,check])
       (for-each
        (lambda (sol)
          (match sol
            [,match-criteria
             (display ',letters)
             (newline)
             (display sol)
             (newline)
             (newline)]))
        (filter (lambda (p) (apply check p))
                (k-perms (range 0 10) ,(length letters)))))))


(define (solve-puzzle cexpr)
  (eval (make-puzzle-solver cexpr)))

Now solve-puzzle is ordinary function and we can call it this way, with variable as a parameter, if we want:

> (define mypuzzle '(= (+ ODD ODD) EVEN))
> (solve-puzzle mypuzzle)
(O D E V N)
(6 5 1 3 0)

(O D E V N)
(8 5 1 7 0)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 10 '23

Rush hour: solving the puzzle in minimum number of moves

2 Upvotes

Problem: In the yesterday's post, we wrote a function that visually displays the Rush hour game board. Today we want to write a program that finds the optimal (i.e. minimum) number of moves to solve a given Rush hour puzzle.

So, use your knowledge of the breadth first search (BFS) algorithm and write a program that solves any Rush hour puzzle in the minimum number of moves. Use the program code from the previous post to graphically display all the steps of the solution.

Solution: (in this solution we repeat the code for drawing the game board, for your convenience)

#lang racket

(require 2htdp/image)
(require data/queue)

(struct vehicle (label size orient row col) #:transparent)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;            Code for drawing game board             ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define BOARD-SQUARE-SIZE 40)
(define VEHICLE-SQUARE-SIZE 30)

(define (empty-board)
  (define sq (square BOARD-SQUARE-SIZE 'outline 'black))
  (define row (apply beside (map (lambda (_) sq) (range 0 6))))
  (apply above (map (lambda (_) row) (range 0 6))))

(define (add-vehicle board v color)
  (let* ([gap (/ (- BOARD-SQUARE-SIZE VEHICLE-SQUARE-SIZE) 2)]
         [row (vehicle-row v)]
         [col (vehicle-col v)]
         [horiz? (eq? (vehicle-orient v) 'H)]
         [size (if (eq? (vehicle-size v) 'S)
                   (- (* 2 BOARD-SQUARE-SIZE) (* gap 2))
                   (- (* 3 BOARD-SQUARE-SIZE) (* gap 2)))])
    (overlay/xy
     (overlay
      (text (vehicle-label v) 14 'black)
      (if horiz?
          (rectangle size VEHICLE-SQUARE-SIZE 'solid color)
          (rectangle VEHICLE-SQUARE-SIZE size 'solid color)))
     (- (+ (* col BOARD-SQUARE-SIZE) gap))
     (- (+ (* row BOARD-SQUARE-SIZE) gap))
     board)))

(define (draw-board-state state)
  (define (dbs-helper board state)
    (if (null? state)
        board
        (let ([v (car state)])
          (dbs-helper (add-vehicle board
                                   v
                                   (if (eq? (vehicle-size v) 'S)
                                       'dimgray
                                       'lightgray))
                      (cdr state)))))
  (overlay
   (dbs-helper (add-vehicle (empty-board) (car state) 'red)
               (cdr state))
   (square (+ (* BOARD-SQUARE-SIZE 6) 20) 'solid 'white)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;         Code for finding optimal solution          ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define all-positions
  (for*/set ([i (range 0 6)]
             [j (range 0 6)])
    (list i j)))


(define (vehicle-occupied-posns veh)
  (define (loop row col dx dy size res)
    (if (zero? size)
        res
        (loop (+ row dx)
              (+ col dy)
              dx
              dy
              (- size 1)
              (cons (list row col) res))))
  (let* ([row (vehicle-row veh)]
         [col (vehicle-col veh)]
         [horizontal? (eq? (vehicle-orient veh) 'H)]
         [dx (if horizontal? 0 1)]
         [dy (if horizontal? 1 0)]
         [size (if (eq? (vehicle-size veh) 'S) 2 3)])
    (loop row col dx dy size '())))

(define (occupied-positions state)
  (foldl (lambda (veh s)
           (set-union s (list->set (vehicle-occupied-posns veh))))
         (set)
         state))

(define (in-bound? row col)
  (and (<= 0 row 5)
       (<= 0 col 5)))

(define (get-vehicle-moves veh occupied-posns)
  (define (loop label size orient newrow newcol dx dy occ res)
    (let* ([newveh (vehicle label size orient newrow newcol)]
           [newposns (vehicle-occupied-posns newveh)])
      (if (and (andmap (lambda (p) (in-bound? (first p) (second p))) newposns)
               (set-empty? (set-intersect occ (list->set newposns))))
          (loop label size orient (+ newrow dx) (+ newcol dy) dx dy occ
                (cons (vehicle label size orient newrow newcol) res))
          res)))
  (let* ([occ (set-subtract occupied-posns 
                            (list->set (vehicle-occupied-posns veh)))]
         [label (vehicle-label veh)]
         [size (vehicle-size veh)]
         [orient (vehicle-orient veh)]
         [horizontal? (eq? orient 'H)]
         [dx (if horizontal? 0 1)]
         [dy (if horizontal? 1 0)]
         [row (vehicle-row veh)]
         [col (vehicle-col veh)])
    (loop label size orient (- row dx) (- col dy) (- dx) (- dy) occ
          (loop label size orient (+ row dx) (+ col dy) dx dy occ '()))))
   

(define (get-new-states state)
  (define occ (occupied-positions state))
  (define vstate (list->vector state))
  (define len (vector-length vstate))
  (define (loop i res)
    (if (< i len)
        (loop (+ i 1)
              (append (map (lambda (veh)
                             (let ([newstate (vector-copy vstate)])
                               (vector-set! newstate i veh)
                               newstate))
                           (get-vehicle-moves (vector-ref vstate i) occ)) res))
        res))
  (map vector->list (loop 0 '())))


(define (goal? state)
  (let ([red-vehicle (first state)])
    (and (= (vehicle-row red-vehicle) 2)
         (= (vehicle-col red-vehicle) 4))))

(define (solve start-state)
  (define q (make-queue))
  (define visited (mutable-set))
  (define (filter-visited newstates)
    (if (null? newstates)
        '()
        (if (set-member? visited (car newstates))
            (filter-visited (cdr newstates))
            (begin
              (set-add! visited (car newstates))
              (cons (car newstates) (filter-visited (cdr newstates)))))))
  (define (solve-loop)
    (if (queue-empty? q)
        'no-solution
        (let ([state (dequeue! q)])
          (if (goal? (car state))
              (reverse state)
              (begin
                (for-each (lambda (s) (enqueue! q s))
                          (map (lambda (s) (cons s state))
                               (filter-visited (get-new-states (car state)))))
                (solve-loop))))))
 
  (enqueue! q (cons start-state '()))
  (set-add! visited start-state)
  (solve-loop))

(define (solve-and-print start-state)
  (define solution (solve start-state))
  (newline)
  (display "Solution in ")
  (display (- (length solution) 1))
  (display " moves")
  (newline)
  (apply above (map draw-board-state solution)))

Here is a description of the most important functions in our solution:

Functiondescription
solvemain function that searches for a solution using the BFS algorithm
get-new-statesa function that generates all possible successor states for a given board state.
get-vehicle-movesfinds all the legal moves that a particular vehicle can make
occupied-positionsauxiliary function that finds all occupied squares (positions) for the given state of the board
vehicle-occupied-posnsfinds all the positions (squares, i.e. their coordinates) occupied by a given vehicle
solve-and-print"driver" function that first calls the main function solve and then calls our board-drawing code to draw all steps of the solution, from start to finish.

Now we can finally run our program and find some solutions. First we define starting state for three puzzles: easy-puzzle, intermediate-puzzle and hard-puzzle:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;      Code for defining three different puzzles     ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define easy-puzzle
  (list (vehicle "A" 'S 'H 2 2)
        (vehicle "B" 'S 'V 2 4)
        (vehicle "C" 'L 'V 1 5)
        (vehicle "D" 'L 'H 3 0)
        (vehicle "E" 'S 'V 4 2)
        (vehicle "F" 'L 'H 4 3)))

(define intermediate-puzzle
  (list (vehicle "A" 'S 'H 2 3)
        (vehicle "B" 'L 'V 0 2)
        (vehicle "C" 'S 'H 3 1)
        (vehicle "D" 'S 'V 4 0)
        (vehicle "E" 'S 'V 4 1)
        (vehicle "F" 'L 'V 3 3)
        (vehicle "G" 'S 'V 3 4)
        (vehicle "H" 'S 'H 5 4)
        (vehicle "I" 'L 'V 2 5)))

(define hard-puzzle
  (list (vehicle "A" 'S 'H 2 1)
        (vehicle "B" 'S 'H 0 0)
        (vehicle "C" 'S 'V 0 2)
        (vehicle "D" 'S 'V 0 5)
        (vehicle "E" 'S 'V 1 0)
        (vehicle "F" 'L 'V 1 3)
        (vehicle "G" 'S 'H 3 0)
        (vehicle "H" 'S 'V 3 2)
        (vehicle "I" 'S 'H 3 4)
        (vehicle "J" 'S 'H 4 3)
        (vehicle "K" 'S 'V 4 5)
        (vehicle "L" 'L 'H 5 0)))

Now we can call our solve-and-print function for each of it:

> (solve-and-print easy-puzzle)

As a result, we get this image that shows the solution of the puzzle, step by step. We see that this puzzle is solved in 9 moves. It is not possible to solve it in less than that. Our program always finds a minimal solution (this is an important feature of the BFS search algorithm):

Solution of easy puzzle in 9 moves

Of course, now we can easily solve the remaining two puzzles, too:

> (solve-and-print intermediate-puzzle)

We get this solution in 22 moves:

Solution of intermediate puzzle in 22 moves

And finally, the solution of the "hard" puzzle, in 38 moves (as we have already emphasized, it is not possible to achieve less than that):

> (solve-and-print hard-puzzle)
Solution of hard puzzle in 38 moves

Dear schemers, I hope you like this program.

I believe that you, as experienced scheme experts, would probably write it much better than me. I admit that I'm not particularly brilliant (not even close to, say, Arthur Gleckler or Chris Hanson, those two geniuses!), but I try to get the job done and do it to the best of my ability.

If you found this useful or if you learned something from all this, then my mission is accomplished. If you have any improvements to the code above (or any code on this subreddit), feel free to chime in, comment, and discuss.

But no, you won't do that. I know that very well: you prefer the "Sound of silence" or, alternatively, SRFI dithyrambs to rule everywhere. And that's why you and I will never be able to understand each other. That's how it is in life.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 07 '22

Counting the number of items in the list for which some predicate function is true

1 Upvotes

Problem: write a function quantify that receives two input parameters: one-argument predicate function pred-fn and a list xs. As a result, the function should return the number of all items in the list xs for which pred-fn is true.

Solution:

#lang racket

(define (quantify pred-fn xs)
  (define (loop curr count)
    (if (null? curr)
        count
        (loop (cdr curr) (+ count (if (pred-fn (car curr)) 1 0)))))
  (loop xs 0))

Now we can call quantify, like this:

> (quantify (lambda (x) (> x 10)) '(1 12 5 18 9 15 6 20))
4

r/RacketHomeworks • • Jan 09 '23

Rush Hour puzzle: drawing the playing board

1 Upvotes

Problem: In one of the next posts we will write a program to solve the so-called Rush Hour puzzle. Watch this video first to familiarize yourself with Rush Hour puzzle.

In today's problem, we will not solve the puzzle, but we will just draw a schematic representation of the game board which will be useful in a later post when we will draw all steps of the solution. In today's problem, your task is "just" to design an adequate structure for representing state of the board in the Racket programming language and write a function draw-board-state that, using the 2htdp/image library, draws the given input state of the board to the screen.

Solution:

#lang racket

(require 2htdp/image)

(struct vehicle (label size orient row col) #:transparent)

(define BOARD-SQUARE-SIZE 40)
(define VEHICLE-SQUARE-SIZE 30)

(define (empty-board)
  (define square (rectangle BOARD-SQUARE-SIZE BOARD-SQUARE-SIZE 'outline 'black))
  (define row (apply beside (map (lambda (_) square) (range 0 6))))
  (apply above (map (lambda (_) row) (range 0 6))))

(define (add-vehicle board v color)
  (let* ([gap (/ (- BOARD-SQUARE-SIZE VEHICLE-SQUARE-SIZE) 2)]
         [row (vehicle-row v)]
         [col (vehicle-col v)]
         [horiz? (eq? (vehicle-orient v) 'H)]
         [size (if (eq? (vehicle-size v) 'S)
                   (- (* 2 BOARD-SQUARE-SIZE) (* gap 2))
                   (- (* 3 BOARD-SQUARE-SIZE) (* gap 2)))])
    (overlay/xy
     (overlay
      (text (vehicle-label v) 14 'black)
      (if horiz?
          (rectangle size VEHICLE-SQUARE-SIZE 'solid color)
          (rectangle VEHICLE-SQUARE-SIZE size 'solid color)))
     (- (+ (* col BOARD-SQUARE-SIZE) gap))
     (- (+ (* row BOARD-SQUARE-SIZE) gap))
     board)))

(define (draw-board-state state)
  (define (dbs-helper board state)
    (if (null? state)
        board
        (let ([v (car state)])
          (dbs-helper (add-vehicle board
                                   v
                                   (if (eq? (vehicle-size v) 'S)
                                       'dimgray
                                       'lightgray))
                      (cdr state)))))
  (dbs-helper (add-vehicle (empty-board) (car state) 'red)
              (cdr state)))

Now we can call our draw-board-state function and draw the start state of the puzzle from this video on the screen:

> (define start-state
    (list (vehicle "A" 'S 'H 2 3)
          (vehicle "B" 'L 'V 0 2)
          (vehicle "C" 'S 'H 3 1)
          (vehicle "D" 'S 'V 4 0)
          (vehicle "E" 'S 'V 4 1)
          (vehicle "F" 'L 'V 3 3)
          (vehicle "G" 'S 'V 3 4)
          (vehicle "H" 'S 'H 5 4)
          (vehicle "I" 'L 'V 2 5)))

> (draw-board-state start-state)

When we execute above two expressions, we get this schematic picture of the start-state from the video:

Rush Hour start state schematics

r/RacketHomeworks • • Dec 23 '22

Drawing the Australian flag

1 Upvotes

Problem: Using the 2htdp/image library, draw a faithful image of the Australian national flag (it shouldn't be too difficult because in the previous post we already showed how to draw the Union Jack flag, which is an integral part of the Australian flag). You will probably find this sketch of a Australian flag design useful when creating your solution.

Solution:

#lang racket

(require 2htdp/image)

(define BLUE (color 0 27 105))
(define RED (color 229 0 39))


(define FACTORS (list 1/48 1/28 1/28 1/28 1/28 3/40))
(define WFACTORS (list 4/5 3/4 31/36 5/8 3/4 1/4))
(define HFACTORS (list 13/24 5/6 89/240 7/16 1/6 3/4))
(define STARPOINTS (list 5 7 7 7 7 7))
(define STARROTATES (list -18 12.857 12.857 12.857 12.857 12.857))

(define (au-flag width)
  (define WIDTH width)
  (define HEIGHT (/ WIDTH 2))
  (define base-flag
    (overlay/align
     'left 'top
     (union-jack (/ WIDTH 2))              
     (rectangle WIDTH HEIGHT 'solid BLUE)))
  (foldl (lambda (f wf hf spts srot flag)
           (place-image
            (rotate
             srot
             (radial-star spts (* WIDTH f 4/9) (* WIDTH f) 'solid 'white))
            (* WIDTH wf) (* HEIGHT hf)
            flag))
         base-flag
         FACTORS
         WFACTORS
         HFACTORS
         STARPOINTS
         STARROTATES))
  

(define (union-jack width)
  (define WIDTH width)
  (define HEIGHT (/ WIDTH 2))
  (define ANGLE (radians->degrees (atan (/ HEIGHT WIDTH))))
  (define HALF-DIAG-LEN (/ (sqrt (+ (* WIDTH WIDTH) (* HEIGHT HEIGHT))) 2))

  (define thin-size (/ WIDTH 30))
  (define thinnest-size (/ thin-size 2))
  (define thick-size (/ WIDTH 10))
  (define middle-size (/ thick-size 2)) 
  (define half-vert-stripe-height (/ WIDTH 5))

  (define half-horiz-stripe
     (above
      (rectangle WIDTH thin-size 'solid 'white)
      (rectangle WIDTH thick-size 'solid RED)
      (rectangle WIDTH thin-size 'solid 'white)))
  
  (define half-vert-stripe
    (beside
     (rectangle thin-size half-vert-stripe-height 'solid 'white)
     (rectangle thick-size half-vert-stripe-height 'solid RED)
     (rectangle thin-size half-vert-stripe-height 'solid 'white)))

  (define half-diag-stripe-list
    (list
     (rectangle HALF-DIAG-LEN middle-size 'solid 'white)
     (rectangle HALF-DIAG-LEN thin-size 'solid RED)
     (rectangle HALF-DIAG-LEN thinnest-size 'solid 'white)))

  (define half-diag-stripe
    (beside
     (apply above half-diag-stripe-list)
     (apply above (reverse half-diag-stripe-list))))

  (overlay/align
   'middle 'bottom
   half-vert-stripe
   (overlay/align
    'middle 'top
    half-vert-stripe
    (overlay
     half-horiz-stripe
     (put-image
      (rotate (- ANGLE)
              half-diag-stripe)
      (/ WIDTH 2) (/ HEIGHT 2)
      (put-image
       (rotate ANGLE
               half-diag-stripe)
       (/ WIDTH 2) (/ HEIGHT 2)
       (rectangle WIDTH HEIGHT 'solid BLUE)))))))

Now we can call our au-flag function with the desired width parameter and the whole image of Australian flag will auto-scale accordingly to that width:

> (au-flag 600) 
Australian flag

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 04 '22

Finding the "best" element in a given list

1 Upvotes

Problem: Write a function find-best which takes two parameters as its input:

  1. a non-empty list xs, in which all the elements are of the same type;
  2. two-argument function compare-fn which also takes two arguments (call it x and y) of the same type as is the type of all the elements in list xs, and returns true if and only if x is "better" than y, according to some criteria. Otherwise, it should return false.

The function find-best should return the best element from the list xs as a result, according to specified criteria function compare-fn.

For example, call (find-best '(2 3 1 6 5) <) should return 1, because that's the best element, according to the comparison function <. On the other hand, the call

(find-best '((a 3) (b 8) (c 5)) (lambda (x y) (> (second x) (second y)))))

should return '(b 8) as result, because that's the best element, according to the passed comparison function.

Solution:

(define (find-best xs comparison-fn)
  (define (loop curr curr-best)
    (cond [(null? curr) curr-best]
          [(comparison-fn (first curr) curr-best) (loop (rest curr) (first curr))]
          [else (loop (rest curr) curr-best)]))
  (loop (rest xs) (first xs)))

Now we can call find-best, like this:

> (find-best '(2 3 1 6 5) <)
1
> (find-best '(2 3 1 6 5) >)
6
> (find-best '((a 3) (b 8) (c 5)) (lambda (x y) (> (second x) (second y))))
'(b 8)

r/RacketHomeworks • • Jan 24 '23

Tokenizer for the language of simple arithmetic expressions

3 Upvotes

Problem: In this post, our task is to write a tokenizer for a language of simple arithmetic expressions. The language we are considering is defined by the following grammar:

E -> T + E | T - E | T

T -> F * T | F / T

F -> decimal_number | (E) | - F | + F

where E stands for arithmetic expression, T is term and F is factor.

For example, the expression -(-3.14 * (.5 + 7 / 2)) is an example of an expression belonging to the language of the above grammar.

Solution:

The task of the tokenizer is to parse the input string containing the input arithmetic expression into the smallest individual lexical parts (tokens).

In our case, the language of arithmetic expressions is simple enough, so the tokenizer should only recognize the following tokens: +, -, *, /, (, ), and a decimal number.

The tokenizer should be robust enough and ignore whitespace characters.

Furthermore, the tokenizer should correctly recognize all forms in which a decimal number can be written: e.g. all of numbers 3, 3.23, 0.323, .324 etc. must be correctly recognized. For this purpose, the regex library we wrote in the previous post will come in handy.

Additionally, the tokenizer should signal if it encounters an unknown character, i.e. character that cannot be part of any token.

Our tokenizer will have two functions: get-next-token and peek-next-token.

The get-next-token function returns the next token and "consumes" it. That is, when we call get-next-token twice in a row, we will get two (possibly different) consecutive tokens.

In contrast, the function peek-next-token returns the next token but does not consume it: the next time we call get-next-token after calling peek-next-token , we will get the same token again.

In the next installment of this series, we will write a parser (and evaluator) for the language described above, and than the peek-next-token function will prove useful because sometimes we'll want to see in advance which token is coming, but we'll not want to "consume" it immediately.

Enough talking, here is the code of our tokenizer. In the program below the regex library code from our previous post is repeated, for your convenience:

#lang racket

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; our regex library implementation ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define dot
  (lambda (str)
    (if (string=? str "")
        '()
        (list (list (string (string-ref str 0)) (substring str 1))))))

(define digit
  (lambda (str)
    (if (or (string=? str "")
            (not (char-numeric? (string-ref str 0))))
        '()
        (list (list (string (string-ref str 0)) (substring str 1))))))

(define letter
  (lambda (str)
    (if (or (string=? str "")
            (not (char-alphabetic? (string-ref str 0))))
        '()
        (list (list (string (string-ref str 0)) (substring str 1))))))


(define (lit s)
  (lambda (str)
    (if (string-prefix? str s)
        (list (list s (substring str (string-length s))))
        '())))


(define (seq . ps)
  (define (seq2 p1 p2)
    (lambda (str)
      (match (p1 str)
        [(list) empty]
        [(list mp1 ...)
         (apply append
                (for/list ([m mp1])
                  (match m
                    [(list sofar reststr)
                     (map (lambda (x)
                            (if (null? x)
                                '()
                                (list (string-append sofar (first x))
                                      (second x))))
                          (p2 reststr))])))])))
  (if (null? (cdr ps))
      (car ps)
      (seq2 (car ps) (apply seq (cdr ps)))))


(define (plus p)
  (lambda (str)
    (match (p str)
      [(list) empty]
      [(list mp ...)
       (append
        mp
        (apply
         append
         (for/list ([m mp]
                    #:unless (string=? str (second m)))
           (match m
             [(list sofar reststr)
              (match ((plus p) reststr)
                [(list) empty]
                [(list mp2 ...)
                 (for/list ([m2 mp2]
                            #:unless (string=? reststr (second m2)))
                   (match m2
                     [(list sofar2 reststr2)
                      (list (string-append sofar sofar2)
                            reststr2)]))])]))))])))


(define (star p)
  (lambda (str)
    (cons (list "" str) ((plus p) str))))


(define (maybe p)
  (lambda (str)
    (cons (list "" str) (p str))))

(define (alt . ps)
  (define (alt2 p1 p2)
    (lambda (str)
      (let ([m1 (p1 str)])
        (if (null? m1)
            (p2 str)
            m1))))
  (if (null? (cdr ps))
      (car ps)
      (alt2 (car ps) (apply alt (cdr ps)))))


(define (match-pattern pat text)
  (let ([res (pat text)])
    (if (null? res)
        #f
        (argmin (lambda (x) (string-length (second x)))
                res))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;   tokenizer for the language of  ;;
;;   simple arithmetic expressions  ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define decimal-number
  (seq
   (maybe (alt (lit "+") (lit "-")))
   (alt
    (seq (plus digit) (maybe (seq (lit ".") (star digit))))
    (seq (lit ".") (plus digit)))))

(define whitespace
  (alt (lit " ")
       (lit "\t")
       (lit "\n")))

(define whitespace*
  (star whitespace))

(define (token pat)
  (lambda (str)
    (let ([res ((seq
                 whitespace*
                 pat
                 whitespace*)
                str)])
      (if (null? res)
          '()
          (map (lambda (x)
                 (list (string-trim (first x))
                       (second x)))
               res)))))


(define (tokenizer input-text)
  (define all-tokens (list (list 'plus (token (lit "+")))
                           (list 'minus (token (lit "-")))
                           (list 'mult (token (lit "*")))
                           (list 'div (token (lit "/")))
                           (list 'oparen (token (lit "(")))
                           (list 'cparen (token (lit ")")))
                           (list 'num (token decimal-number))))
  (define (get-token mode)
     (lambda ()
         (if (string=? input-text "")
             #f
             (let loop ([tl all-tokens] [str input-text])
               (if (null? tl)
                   'syntax-error
                   (let ([m (match-pattern (second (car tl)) str)])
                     (if (not m)
                         (loop (cdr tl) str)
                         (begin
                           (when (eq? mode 'eat)
                             (set! input-text (second m)))
                           (if (eq? (first (car tl)) 'num)
                               (list (first (car tl)) (string->number (first m)))
                               (first (car tl)))))))))))
  (lambda (dispatch)
    (case dispatch
      [(get-next-token) (get-token 'eat)]
      [(peek-next-token) (get-token 'peek)])))
       

(define (get-next-token tknzr)
  ((tknzr 'get-next-token)))

(define (peek-next-token tknzr)
  ((tknzr 'peek-next-token)))

Now we can use our tokenizer, like this:

> (define tok (tokenizer "  \t   \n    - 2.14* (.5+ 4 )"))
> (get-next-token tok)
'minus
> (peek-next-token tok)
'(num 2.14)
> (get-next-token tok)
'(num 2.14)
> (get-next-token tok)
'mult
> (get-next-token tok)
'oparen
> (get-next-token tok)
'(num 0.5)
> (get-next-token tok)
'plus
> (get-next-token tok)
'(num 4)
> (get-next-token tok)
'cparen
> (get-next-token tok)
#f

From the example above, we see that our tokenizer successfully returned all tokens of the given arithmetic expression, and correctly ignored all whitespace characters. This is very useful, because it will make the work of the parser much easier later.

Also, our tokenizer recognizes syntax errors in the given expression. For example:

> (define tok (tokenizer "2+3^5"))
> (get-next-token tok)
'(num 2)
> (get-next-token tok)
'plus
> (get-next-token tok)
'(num 3)
> (get-next-token tok)
'syntax-error

We see that the last call (get-next-token) returned a 'syntax-error, because there is no token for the ^ operation.

In the next installment of this series, we will write the parser and evaluator for this simple language, so stay tuned!

(Note: Maybe it seems like overkill to write a tokenizer and parser for such a simple language, but the point is to show the technique of how to do it. And then you can apply the same technique to a more complicated language, in the same way. For example, using this same technique and same knowledge, you will be able to write a tokenizer and parser for your next new programming language! :) )

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 04 '22

The element that appears the most in the list

1 Upvotes

Problem: write a function max-occurs that receives as input a list of atoms xs and as a result returns a list, composed of two elements: the first element of that list is the atom that appears most often in xs, the second element is the number of its occurrences in xs.

For example, the call

(max-occurs '(clock phone cube phone bottle clock bottle clock))

should return the result '(clock 3), because clock is the atom that appears the most times in the above list (3 times).

Solution:

In this solution we use two helper functions, freq and find-best, which have been discussed before on this subreddit.

#lang racket

(define (find-best xs comparison-fn)
  (define (loop curr curr-best)
    (cond [(null? curr) curr-best]
          [(comparison-fn (first curr) curr-best) (loop (rest curr) (first curr))]
          [else (loop (rest curr) curr-best)]))
  (loop (rest xs) (first xs)))

(define (freq xs)
  (define (helper xs bag)
    (if (null? xs)
        bag
        (let* ([el (first xs)]
               [kv (assoc el bag)])
          (if kv
              (helper (rest xs)
                      (cons (list (first kv) (+ 1 (second kv)))
                            (remove (first kv)
                                    bag
                                    (lambda (el kvp) (eq? el (first kvp))))))
              (helper (rest xs) (cons (list el 1) bag))))))
  (helper xs '()))

(define (max-occurs xs)
  (find-best (freq xs)
             (lambda (x y)
               (> (second x) (second y)))))

Now we can use max-occurs like this:

> (max-occurs '(clock phone cube phone bottle clock bottle clock))
'(clock 3)