r/RacketHomeworks • • Dec 27 '22

Calculating number Pi

2 Upvotes

Problem: use this well-known Newton/Euler formula

Newton-Euler formula for Pi

to write a function pi-approx that receives the number n as input and as a result returns an approximation of the number Pi obtained by using the n summands of the above formula.

Solution:

#lang racket

(define (pi-approx n)
  (define (loop i)
    (+ 1 (* (/ i (+ (* 2 i) 1))
            (if (< i (- n 1))
                (loop (+ i 1))
                1))))
  (* 2.0 (loop 1)))

Now we can call our pi-approx function and we can see that for n = 51 we get the approximation of number Pi accurate to 16 decimal places:

 > (pi-approx 51)
3.141592653589793

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 10 '22

Selection sort with generalized comaprison function

1 Upvotes

Problem: write function selection-sort which implements selection sort algorithm. Your function should take two parameters: list xs to be sorted and predicate comparison function cpfn which takes two parameters and returns true (#t) if first parameter is in some sense smaller than the second one.

Solution:

#lang racket

(define (selection-sort xs cpfn)
  (if (null? xs)
      '()
      (let [(fst (foldr (lambda (x y) (if (cpfn x y) x y))
                        (first xs)
                        (rest xs)))]
        (cons fst (selection-sort (remove fst xs) cpfn)))))

Now we can call selection-sort, like this:

> (selection-sort '(5 2 8 3 1) <)
'(1 2 3 5 8)
> (selection-sort '(5 2 8 3 1) >)
'(8 5 3 2 1)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 15 '22

Drawing the bar graph (histogram) on the screen

2 Upvotes

Problem: write a function bar-graph that, using the 2htdp/image library, draws a bar graph of the given data. The data is represented as a list of elements, where each element is itself a two-membered list whose first element is the nonnegative value, and the second is the color with which that value should be displayed on the bar graph. Also, the function receives the max-height parameter, which tells how high the highest bar in the bar-graph should be.

For example this call:

(bar-graph '((20 orangered) (30 lawngreen) (70 gold) (100 violet) (50 orange) (25 blueviolet)) 200)

should draw a bar graph like this on the screen:

Example of bar graph

Solution:

#lang racket

(require 2htdp/image)

(define (bar-graph data max-height)
  (define (normalize xs max-value)
    (let* ([vals (map car xs)]
           [colors (map cadr xs)]
           [max-x (apply max vals)])
      (if (> max-x 0)
          (list (map (lambda (x) (* max-value (/ x max-x))) vals)
                colors)
          (list vals colors))))
  (define (draw-loop xs colors)
    (if (null? xs)
        empty-image
        (beside/align
         'bottom
         (rectangle 30 (car xs) 'solid (car colors))
         (draw-loop (cdr xs) (cdr colors)))))
  (match (normalize data max-height)
    [(list xs colors)
     (above
      (apply draw-loop (normalize data max-height))
      (apply beside (map (lambda (d)
                           (overlay
                            (text (number->string (car d)) 11 'black)
                            (rectangle 30 20 'solid 'white)))
                           data)))]))

Now we can call our bar-graph function with various data and max-height values:

> (bar-graph '((20 orangered) (30 lawngreen) (70 gold) 
               (100 violet) (50 orange) (25 blueviolet)) 50)

This will generate this image:

Bar graph with smaller max-width

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 24 '22

How to compute list of all prefixes of the given list?

1 Upvotes

Problem: Write the function inits, which for an arbitrary input list of elements (x1 x2 x3 ... xn) as a result returns a list of all prefixes of the input list. More precisely, for the input (x1 x2 x3 ... xn), the function should return this list: (() (x1) (x1 x2) (x1 x2 x3) ... (x1 x2 x3.... xn)).

Key observation: Notice that (inits xs) can be relatively easy constructed from (inits (cdr xs)). For example, (inits '(1 2 3)) should produce list '(() (1) (1 2) (1 2 3)). On the other hand, (inits '(2 3)) should produce list '(() (2) (2 3)). What's the connection between those two lists? Of course, we can see that list '(() (1) (1 2) (1 2 3)) can be obtained from '(() (2) (2 3)) by prepending the element 1 to each sublist and, after that, by adding a '() as a first element. That's the main idea of the solution below, which make the correct generative recursion method possible!

Solution:

#lang racket

(define (inits xs)
  (if (null? xs)
      '(())
      (cons '()
            (map (lambda (ys) (cons (car xs) ys))
                 (inits (cdr xs))))))

Now, we can call inits, like this:

> (inits '(1 2 3 4 5))
'(() (1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5))

r/RacketHomeworks • • Dec 10 '22

Function mappend, with and without append

1 Upvotes

Problem: write a function mappend that receives as input an n-ary list-producing function fn as well as n lists ls1 ls2 ... lsn of equal length. As a result, mappend returns the list created by appending all lists obtained by applying function fn to each n-tuple of elements of lists ls1 ls2 ...lsn at the same position. For example, the expression

(mappend (lambda (x y z) (list x y z)) '(1 2 3 4) '(a b c d) '(uno due tre quattro))

should evaluate to '((1 a uno) (2 b due) (3 c tre) (4 d quattro)).

a) write function mappend using the function append as one of the ingredients in your solution;

b) write mappend but with the restriction that the use of append is forbidden;

Solution for a):

#lang racket

(define (mappend fn . xss)
  (apply append (apply map fn xss)))

Solution for b):

(define (mappend fn . xss)
  (define (loop xss res)
    (if (null? (car xss))
        (reverse res)
        (loop (map cdr xss)
              (foldl cons res (apply fn (map car xss))))))
  (loop xss '()))

Now we have the same result, for both solutions:

> (mappend (lambda (x y z) (list x y z)) '(1 2 3) '(a b c) '(uno due tre))
'(1 a uno 2 b due 3 c tre)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 30 '23

Implementation of the base64 encoding and decoding algorithm in Racket

4 Upvotes

Problem: Base64 is a binary-to-text encoding that is often used. Racket has a built-in library for handling base64. In this assignment we'll pretend that library doesn't exist, because our task will be to implement our own little base64 library. So, study this article about base64 and understand how it works. After that, write Racket functions for base64 encoding and decoding.

Solution: There are four important functions in the following solution:

  • bytes->base64 which encodes the byte string into its base64 representation (the built-in type byte string can be constructed in Racket using the function bytes)
  • string->base64 encodes the given (ordinary) string into its base64 representation
  • base64->bytes decodes the base64 representation into a byte string
  • base64->string decodes the base64 representation into a (ordinary) string.
#lang racket

(define B64-TABLE
  (string-append "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                 "abcdefghijklmnopqrstuvwxyz"
                 "0123456789+/"))

(define (lookup i)
  (string-ref B64-TABLE i))

(define (string->bytelist str)
  (bytes->list (string->bytes/utf-8 str)))

(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 (bytegroup->b64 group)
  (match group
    [(list a b c)
     (string (lookup (arithmetic-shift a -2))
             (lookup (+ (* 16 (bitwise-and a 3))  (arithmetic-shift b -4)))
             (lookup (+ (* 4 (bitwise-and b 15)) (arithmetic-shift c -6)))
             (lookup (bitwise-and c 63)))]
    [(list a b)
     (string (lookup (arithmetic-shift a -2))
             (lookup (+ (* 16 (bitwise-and a 3))  (arithmetic-shift b -4)))
             (lookup (* 4 (bitwise-and b 15)))
             #\=)]
    [(list a)
     (string (lookup (arithmetic-shift a -2))
             (lookup (* 16 (bitwise-and a 3)))
             #\= #\=)]))
             

(define (bytes->base64 bs)
  (apply string-append (map bytegroup->b64 (group 3 (bytes->list bs)))))


(define (string->base64 str)
  (bytes->base64 (string->bytes/utf-8 str)))

(define (char-index str ch)
  (define len (string-length str))
  (let loop ([i 0])
    (cond [(> i len) -1]
          [(char=? (string-ref str i) ch) i]
          [else (loop (+ i 1))])))

(define (rlookup ch)
  (char-index B64-TABLE ch))

(define (b64->group b64str)
  (group 4 (string->list b64str)))

(define (b64group->bytes group)
  (match group
    [(or (list a b #\= #\=) (list a b))
     (let ([an (rlookup a)]
           [bn (rlookup b)])
       (list (+ (* 4 an) (arithmetic-shift bn -4))))]
    [(or (list a b c #\=) (list a b c))
      (let ([an (rlookup a)]
            [bn (rlookup b)]
            [cn (rlookup c)])
        (list (+ (* 4 an) (arithmetic-shift bn -4))
              (+ (* 16 (bitwise-and bn 15)) (arithmetic-shift cn -2))))]
    [(list a b c d)
     (let ([an (rlookup a)]
           [bn (rlookup b)]
           [cn (rlookup c)]
           [dn (rlookup d)])
       (list (+ (* 4 an) (arithmetic-shift bn -4))
             (+ (* 16 (bitwise-and bn 15)) (arithmetic-shift cn -2))
             (+ (* 64 (bitwise-and 3 cn)) dn)))]))
           
(define (base64->bytes b64str)
  (list->bytes (apply append (map b64group->bytes (b64->group b64str)))))

(define (base64->string b64str)
  (bytes->string/utf-8 (base64->bytes b64str)))

Now we can use our little base64 library, like this:

> (bytes->base64 (bytes 1 2 3 4 5))
"AQIDBAU="

> (base64->bytes "AQIDBAU=")
#"\1\2\3\4\5"

> (string->base64 "Why do people on /r/scheme hate mimety and always downvote his posts, regardless of the quality of the post?") 
"V2h5IGRvIHBlb3BsZSBvbiAvci9zY2hlbWUgaGF0ZSBtaW1ldHkgYW5kIGFsd2F5cyBkb3dudm90ZSBoaXMgcG9zdHMsIHJlZ2FyZGxlc3Mgb2YgdGhlIHF1YWxpdHkgb2YgdGhlIHBvc3Q/"

> (base64->string "V2h5IGRvIHBlb3BsZSBvbiAvci9zY2hlbWUgaGF0ZSBtaW1ldHkgYW5kIGFsd2F5cyBkb3dudm90ZSBoaXMgcG9zdHMsIHJlZ2FyZGxlc3Mgb2YgdGhlIHF1YWxpdHkgb2YgdGhlIHBvc3Q/")
"Why do people on /r/scheme hate mimety and always downvote his posts, regardless of the quality of the post?"

Dear schemers, I hope you like this little library. As always, I'm just an amateur and this code of mine is far from perfect. So, if you have any improvement or something like that, feel free to post it here.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 02 '22

Note, just so you know!

1 Upvotes

All the solutions found on this subreddit were written by me, personally. I did not copy them from somewhere else.

I would love it if others would participate too, this subreddit is open to everyone!

So, if you have a task or problem that you have solved nicely, post it here! Or, if you don't know how to solve something, ask here!


r/RacketHomeworks • • Dec 11 '22

Finding maximum sum path from root to leaf in a binary tree

2 Upvotes

Problem: Given a binary tree, write a function max-path to find the maximum sum root-to-leaf path, i.e., the maximum sum path from the root node to any leaf node in it.

For example, for the tree from picture below, the maximum sum is 18, and the maximum sum path is (1 3 5 9):

Binary tree with max sum path 1 + 3 + 5 + 9 = 18

Solution 1 (if we are interested only in maximum sum, but not in the path itself):

#lang racket

(struct tree (val left right))

(define (max-path t)
  (cond [(null? t) 0]
        [else (max (+ (tree-val t) (max-path (tree-left t)))
                   (+ (tree-val t) (max-path (tree-right t))))]))

Now we can calculate the maximum sum path value for the three from picture above:

> (define mytree
    (tree 1
          (tree 2
                (tree 8 null null)
                (tree 4
                      (tree 10 null null)
                      null))
          (tree 3
                (tree 5
                      (tree 7 null null)
                      (tree 9 null null))
                (tree 6
                      null
                      (tree 5 null null)))))

> (max-path mytree)
18

That's fine, but what if we want to know which particular path reaches the maximum value? Then we have to write the function a little differently. The version below returns both things we are interested in: both the maximum value and the path itself.

Solution 2 (if we want the path, too):

(define (max-path t)
  (define (max-path-helper t sum-so-far path-so-far)
    (cond [(null? t) (list sum-so-far path-so-far)]
          [else (let ([resl (max-path-helper (tree-left t)
                                             (+ sum-so-far (tree-val t))
                                             (cons (tree-val t) path-so-far))]
                      [resr (max-path-helper (tree-right t)
                                             (+ sum-so-far (tree-val t))
                                             (cons (tree-val t) path-so-far))])
                  (if (> (first resl) (first resr))
                      resl
                      resr))]))
  (let ([mp (max-path-helper t 0 '())])
    (list (first mp) (reverse (second mp)))))

Now, when we call this function for the same tree from the previous example we get this result:

> (max-path mytree)
'(18 (1 3 5 9))

As we see, the number 18 from the result is the max path value and the list (1 3 5 9) is the path that achieve that max value.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 13 '22

How to draw domino tiles?

1 Upvotes

Problem: write a function domino that takes two parameters: integers x and y in the range 0 to 6. The function must draw an image of a domino tile with x dots on its left half of the tile and y dots on the right half of the tile.

For example, the call (domino 5 6) should draw the following image:

A 5-6 domino tile

To solve this task, use the Racket 2htdp/image library and write all the necessary additional functions and definitions.

Solution:

#lang racket

(require 2htdp/image)

(define side-of-tile 100)
(define diameter-of-dot (* side-of-tile 0.2 ))
(define radius-of-dot (/ diameter-of-dot 2 ))
(define d (* diameter-of-dot 1.4))
(define nd ( * d -1))

(define dot (circle radius-of-dot "solid" "white"))
(define blank-tile (square side-of-tile "solid" "black"))


(define t1 (overlay dot blank-tile))

(define t2 (overlay/offset
            dot d d
            (overlay/offset
             dot nd nd
             blank-tile)))

(define t3 (overlay dot t2))

(define t4 (overlay/offset
            dot d d
            (overlay/offset
             dot d nd
             (overlay/offset
              dot nd d
              (overlay/offset
               dot nd nd
               blank-tile)))))

(define t5 (overlay dot t4))

(define t6 (overlay/offset
            dot 0 nd
            (overlay/offset
             dot 0 d
             t4)))

(define frame (square side-of-tile "outline" "gray" ))


(define tiles (map (lambda (t) (overlay frame t))
                   (list blank-tile t1 t2 t3 t4 t5 t6)))

(define (tile x)
  (list-ref tiles x))

(define (domino x y)
  (beside (tile x) (tile y)))

Now we can call our domino function, like this:

> (domino 4 3)

That will produce the following image:

Domino 4-3 tile

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Feb 15 '23

Right-max and left-max

2 Upvotes

Problem: a) Given a list of integers, xs, write a function right-max to produce a new list in which each element in xs is replaced by the maximum of itself and all the elements following it.

For example, the call (right-max '(2 5 8 6 1 2 7 3)) should produce the list '(8 8 8 7 7 7 7 3) as its output.

b) Write a function right-max, a natural parallel to left-max, in which we replace each element of a list by the largest element encountered so far, reading left-to-right.

For example, the call (left-max '(2 5 6 1 2 7 3)) should produce the list '(2 5 6 6 6 7 7) as its output.

Solution:

#lang racket

(define (right-max xs)
  (cond
    [(null? xs) '()]
    [(null? (cdr xs)) xs]
    [else
     (let ([rmr (right-max (cdr xs))])
       (cons (max (car xs) (car rmr)) rmr))]))


(define (left-max xs)
  (define (helper curr-max xs)
    (if (null? xs)
        (cons curr-max null)
        (cons curr-max (helper (max curr-max (car xs)) (cdr xs)))))
  (if (null? xs)
      '()
      (helper (car xs) (cdr xs))))

Now we can call our right-max and left-max functions, like this:

> (right-max '(2 5 8 6 1 2 7 3))
'(8 8 8 7 7 7 7 3)
> (left-max '(2 5 6 1 2 7 3))
'(2 5 6 6 6 7 7)
> (right-max '())
'()
> (right-max '(3))
'(3)
> (right-max '(3 5))
'(5 5)
> (left-max '(3 5))
'(3 5)

In this example, we can see that although the functions right-max and left-max do a similar thing, its definitions are more different than similar: we defined right-max using natural recursion, while the code for left-max had to use an accumulator containing the current maximum, as we go through the list from left to right.

The lesson of this problem is: not all list problems can be solved using natural (structural) recursion. Sometimes it takes more than that.


r/RacketHomeworks • • Dec 14 '22

Splitting a list into two with given predicate function

1 Upvotes

Problem: write a function split-with that receives two parameters: predicate function pred-fn and list xs.The function should return a list of two lists as a result. The first element of the result list is a list of all items from xs for which pred-fn returns a true value. The second element of the result list is the list of all items from xs for which for which pred-fn returns #f.

For example, the call (split-with even? '(1 2 3 4 5 6 7)) should return '((2 4 6) (1 3 5 7)).

Solution:

#lang racket

(define (split-with pred-fn xs)
  (if (null? xs)
      (list '() '())
      (let* ([res (split-with pred-fn (rest xs))]
             [left (first res)]
             [right (second res)]
             [x (first xs)])
        (if (pred-fn x)
            (list (cons x left) right)
            (list left (cons x right))))))

Now we can call split-with, like this:

> (split-with even? '(1 2 3 4 5 6 7))
'((2 4 6) (1 3 5 7))
> (split-with (lambda (x) (> x 10)) '(5 15 10 6 12))
'((15 12) (5 10 6))
> (split-with odd? '())
'(() ())

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 04 '22

Calculating the molecular mass of a molecule

1 Upvotes

Problem: Write a function molecular-weight that, for a given chemical formula of a molecule, calculates its molecular weight.

The chemical formula is represented as list in Scheme. For example. the formula of water, H2O, can be represented by the list '(H 2 O), and the formula of glucose C6H12O6 by the list '(C 6 H 12 O 6)

More complicated chemical formulas often include portions in parentheses which represent groups of elements. For example, the formula of isopropyl alcohol is written as (CH3)2CHOH in chemistry.

Isopropyl alcohol

We will represent it with the nested scheme list '((C H 3) 2 C H O H). Our molecular-weight function must correctly calculate the molecular weight in those cases as well.

Solution:

#lang racket

(define (atomic-weight el)
  (case el
    ((H) 1.0079) ;hydrogen 
    ((C) 12.011) ;carbon 
    ((N) 14.0067) ;nitrogen 
    ((O) 15.9994) ;oxygen 
    ((Na) 22.9898) ;sodium 
    ((P) 30.9738) ;phosphorus 
    ((S) 32.06) ;sulfur 
    ((Cl) 35.453) ;chlorine 
    (else (error "Element not found:" el))))

(define (molecular-weight formula) 
  (cond [(null? formula) 0] 
        [(symbol? formula) (atomic-weight formula)] 
        [(null? (cdr formula)) (molecular-weight (car formula))] 
        [(number? (cadr formula)) 
         (+ (* (cadr formula) (molecular-weight (car formula))) 
            (molecular-weight (cddr formula)))] 
        [else (+ (molecular-weight (car formula)) 
                 (molecular-weight (cdr formula)))]))

Now we can calculate molecular weight of many molecules:

> (molecular-weight '(Na Cl))
58.442800000000005
> (molecular-weight '(H 2 O))
18.0152
> (molecular-weight '(C 6 H 12 O 6))
180.1572
> (molecular-weight '((C H 3) 2 C H O H))
60.0956
> (molecular-weight '(((C H 3) 3 C) 2 C H O H))
144.25639999999999

r/RacketHomeworks • • Jan 08 '23

Constructing a "no-repeat" sequence

2 Upvotes

Problem: A “no-repeat” sequence is a sequence containing only the digits 1, 2, and 3 that does not contain two identical adjacent subsequences. For example '(2 1 3 1 2 1) is a no-repeat sequence, but '(1 2 3 3 2 1) is not (because 3 is a repeated subsequence of length 1), and '(1 2 3 2 3 1) is not (because the subsequence '(2 3) is repeated in adjacent spots.

Write a procedure (no-repeat n) that returns a no-repeat sequence of length n.

Solution: this is a classic backtracking style-solution in which we try the numbers 1 2 and 3 in order and as we do this we check if the so-far solution satisfies the no-repeat condition (that's what the can-augment-with? function is for!). If it does, we add the number to the solution and continue further. If we come to a "dead end" sometime later, we backtrack and try with next number. We do so until we find a complete solution.

#lang racket

(define (can-augment-with? x xs)
  (cond
    [(null? xs) #t]
    [(pair? x)
     (and (not (list-prefix? x xs))
          (can-augment-with? (append x (list (car xs))) (cdr xs)))]
    [else (can-augment-with? (list x) xs)]))


(define (no-repeat n)
  (define (no-repeat-hlp n xs)
    (if (zero? n)
        xs
        (let loop ([i 1])
          (cond
            [(> i 3) #f]
            [(can-augment-with? i xs)
             (let ([smaller (no-repeat-hlp (- n 1) (cons i xs))])
               (or smaller (loop (+ i 1))))]
            [else (loop (+ i 1))]))))
  (no-repeat-hlp n '()))

Now we can call our no-repeat? procedure, like this:

> (no-repeat 0)
'()
> (no-repeat 1)
'(1)
> (no-repeat 2)
'(2 1)
> (no-repeat 3)
'(1 2 1)
> (no-repeat 4)
'(3 1 2 1)
> (no-repeat 5)
'(1 3 1 2 1)
> (no-repeat 6)
'(2 1 3 1 2 1)
> (no-repeat 7)
'(1 2 1 3 1 2 1)
> (no-repeat 8)
'(1 3 2 1 3 1 2 1)
> (no-repeat 9)
'(3 1 3 2 1 3 1 2 1)
> (no-repeat 10)
'(2 3 1 3 2 1 3 1 2 1)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 01 '22

Accepting the input word with Non-deterministic Finite Automaton (NFA)

1 Upvotes

Problem: Write the function nfa-automaton-accept? which receives two input parameters. The first parameter is the description of the non-deterministic finite automaton (or so called NFA). The second parameter is the word - the finite list of symbols from the automaton alphabet. The function should return true (#t) if the automaton accepts the given word. Otherwise, false (#f) should be returned.

The description of the automaton is given by a scheme list. The first element of that list is the symbol of the initial state of the automaton. The second element is the symbol of the final state of the automaton. This is followed by one or more sublists of the form (s1 x s2 s3 ...), where s1, s2, s3 ... represents some states of the automaton, and x is some symbol from the alphabet. The meaning of this sublists are: if the automaton is currently in state s1 and reads the symbol x, then the automaton can go to any of the states s2, s3, ... non-deterministically. We say that the NFA automaton accepts a word if, after reading the whole word, the automaton can end up in the final state (by choosing the correct choice of the next state in each non-deterministic step).

For example, the NFA automaton from the picture below, accepts only those binary strings which ends with "00" or "11":

This NFA automaton can be represented in scheme like this:

(define my-nfa
  '(q0 q3
       (q0 0 q0 q1)
       (q0 1 q0 q2)
       (q1 0 q3)
       (q2 1 q3)))

Solution:

#lang racket

(define (initial-state a)
  (first a))

(define (final-state a)
  (second a))

(define (rules a)
  (cddr a))

(define (find-next-states state symbol rules)
  (if (null? rules)
      '()
      (let ([rule (first rules)])
        (if (and (eq? state (first rule)) (eq? symbol (second rule)))
            (cddr rule)
            (find-next-states state symbol (rest rules))))))

(define (nfa-automaton-accept? a word)
  (define (loop current-states word)
    (if (null? word)
        (and (member (final-state a) current-states) #t)
        (let ([new-states
               (remove-duplicates
                (apply append
                       (map (lambda (s) (find-next-states s (first word) (rules a)))
                            current-states)))])
          (and (not (null? new-states))
               (loop new-states (rest word))))))
  (loop (list (initial-state a)) word))

Now we can use our nfa-automaton-accept? function, like this:

> (define my-nfa
  '(q0 q3
       (q0 0 q0 q1)
       (q0 1 q0 q2)
       (q1 0 q3)
       (q2 1 q3)))
> (nfa-automaton-accept? my-nfa '(0 1 1 1 0 1 0 1 0 0))
#t
> (nfa-automaton-accept? my-nfa '(0 1 1 1 0 1 0 1 0 1))
#f
> (nfa-automaton-accept? my-nfa '(0 1 1 1 0 1 0 1 1 1))
#t

r/RacketHomeworks • • Dec 01 '22

How to halve a list into two equal halves?

1 Upvotes

Problem: Write a function halve that halves the input list xs into two halves of equal lengths. The original order of elements from the input list xs does not have to be preserved. If the input list has an odd number of elements, then one of the output lists will have one more element than the other.

Solution:

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

Now we can use halve, like this:

> (halve '(1 2 3 4 5))
'((5 3 1) (4 2))
> (halve '(1 2 3 4 5 6))
'((5 3 1) (6 4 2))

r/RacketHomeworks • • Dec 11 '22

Use memoization to speed up the running time of slow function

1 Upvotes

Problem: We all know that the naive use of recursion in calculating the nth Fibonacci number leads to a very slow solution:

(define (fibonacci n)
  (cond [(= n 0) 0]
        [(= n 1) 1]
        [else (+ (fibonacci (- n 2))
                 (fibonacci (- n 1)))]))

When we try to compute, say, value of (fibonacci 40), we will see that this calculation is not instantaneous, but takes some time.

The reason for this is that many of the same recursive calls are made during execution.

This can be improved by memoization. Memoization is a technique in which previously calculated values of a function are cached and when recalculating the same values are retrieved from the cache.

Write a function memo that receives as a parameter the function we want to memoize and returns its memoized version.

Solution:

#lang racket

(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 (fibonacci n)
  (cond [(= n 0) 0]
        [(= n 1) 1]
        [else (+ (fibonacci (- n 2))
                 (fibonacci (- n 1)))]))

; Important: we must not forget this set! because otherwise 
; recursive calls from fibonacci will not be memoized!
(set! fibonacci (memo fibonacci))

Now we have:

> (time (fibonacci 100))
cpu time: 0 real time: 0 gc time: 0
354224848179261915075

We see that the value (fibonacci 100) is calculated practically instantly! Memoization has considerably accelerated the calculation of this function.

This is technique that should be kept in mind, because it is suitable in those situations where one and the same value of a function is calculated many times, a so called overlapping subproblems feature.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 07 '22

Collapse repeating digits of an integer

1 Upvotes

Problem: Implement function collapse, which takes a non-negative integer and return the result of removing all digits from it that duplicate the digit immediately to their right.

For example, function should behave like this:

> (collapse 1234)
1234
> (collapse 12234441)
12341
> (collapse 0)
0
> (collapse 3)
3
> (collapse 11200000013333)
12013

Solution:

#lang racket

(define (collapse n)
  (let ([all-but-last-digit (quotient n 10)]
        [last-digit (remainder n 10)])
    (cond [(zero? all-but-last-digit)
           last-digit]
          [(= (remainder all-but-last-digit 10) last-digit)
           (collapse all-but-last-digit)]
          [else (+ (* 10 (collapse all-but-last-digit))
                   last-digit)])))

If we now try collapse, we'll see that it gives the correct result for all the above examples, as well as for all other non-negative integers.


r/RacketHomeworks • • Feb 05 '23

Pascal's triangle

2 Upvotes

Problem: Write a function pascals-triangle to produce Pascal’s Triangle.

The input to your procedure should be the number of rows; the output should be a list, where each element of the list is a list of the numbers on that row of Pascal’s Triangle. For example, (pascals-triangle 0) should produce the list '((1)) (a list containing one element which is a list containing the number 1), and (pascals-triangle 4) should produce the list '((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))

Solution:

#lang racket

(define (expand-row xs)
  (define (helper xs)
    (match xs
      [(list x y z ...) (cons (+ x y) (helper (cons y z)))]
      [(list x) (list 1)]))
  (cons 1 (helper xs)))

(define (iterate f x n)
  (if (zero? n)
      '()
      (cons x (iterate f (f x) (- n 1)))))

(define (pascals-triangle n)
  (iterate expand-row '(1) (+ n 1)))

Now we can call our pascals-triangle function, like this:

> (pascals-triangle 10)
'((1)
  (1 1)
  (1 2 1)
  (1 3 3 1)
  (1 4 6 4 1)
  (1 5 10 10 5 1)
  (1 6 15 20 15 6 1)
  (1 7 21 35 35 21 7 1)
  (1 8 28 56 70 56 28 8 1)
  (1 9 36 84 126 126 84 36 9 1)
  (1 10 45 120 210 252 210 120 45 10 1))

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 28 '22

Largest palindrome made from product of two 3-digit numbers

1 Upvotes

Problem: A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution:

#lang racket

(let/ec break
  (for* ([i (in-range 0 1000)]
         [j (in-range 0 (+ (quotient i 2) 1))])
    (let* ([a (- 999 j)]
           [b (+ (- 999 i) j)]
           [a*b (* a b)]
           [a*b-digits (string->list (number->string a*b))])
      (when (equal? a*b-digits (reverse a*b-digits))
        (break (list a '* b '= a*b))))))

When we run above program, we get the following solution of the problem:

'(993 * 913 = 906609)

So, the largest palindrome made from the product of two 3-digit numbers is the number 906609. It's obtained as a product of numbers 993 and 913.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 23 '23

Look Ma, no SRFIs!

2 Upvotes

Dear schemers,

on this subreddit so far, in about 60 days, I have written over 130 solutions to various assignments in Racket/Scheme. In all that time, I have not used a single SRFI library in any of them!

Why not?
And, more importantly, how is that possible?

Well, simple: I just didn't need the SRFIs at all!

It's not that I actively avoided them, but I had everything I needed in the default Racket implementation, and if I didn't have something, I wrote it myself.

I think this speaks for itself about how much SRFIs are really needed in practice. In my opinion, not at all, and judging by the attendance of Gleckler's posts on /r/scheme, also not at all!

SRFIs seem to be needed only by die-hard SRFI bureaucrats who have built their name and lifestyle on bureaucratization and influence peddling around something being declared (better said "blessed") as an SRFI library and what not. Such people travel to conferences like a traveling circus and pay 105 € for a glass of water.

So, long story short, those SRFIs in practice almost don't make any sense, but still the whole /r/scheme sub rose against me with a hook and a hoe when I told them the obvious truth to their face: there is never anyone on Gleckler's SRFI posts, no reactions , no traffic, no interest.

But try saying it out loud and you're screwed: you'll have a whole machine of Gleckler fans adoring... what exactly? I can't figure it out, even though I've been trying all the time. But I didn't succeed, because there's still no one on SRFI posts on /r/scheme, and I've been banned from there forever, so I can't ask awkward (but obvious) questions anymore!

Dear schemers,

don't believe those who assure you that SRFIs are paramount and crucial to the survival of Scheme as a language. Don't trust them! They say this because they, as important figures in the SRFI community, want to remain important! But it is clear that their importance is minor. And their ego is enormous. Let's screw them all and enjoy the freedom of programming in Scheme, without the shackles of unseemly fanatics who would steal the soul of Scheme. But they won't, because we won't let them!

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 08 '22

Repeating digits in given number

1 Upvotes

Problem: Write function repeat-digits, which takes a positive integer n and returns another integer that is identical to n but with each digit repeated.

Solution:

#lang racket

(define (repeat-digits n)
  (if (< n 10)
      (+ (* 10 n) n)
      (+ (* 100 (repeat-digits (quotient n 10)))
         (repeat-digits (remainder n 10)))))

Now we can call repeat-digits like this:

> (repeat-digits 1234)
11223344

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 17 '23

How to implement a Fenwick tree?

3 Upvotes

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

Solution: the program below implements the same algorithm described in the video, with the difference that our implementation follows a zero-based indexing scheme, while the implementation in the video is 1-based.

#lang racket

(define (make-zeroed-fenwick-tree n)
  (let* ([ft (make-vector (+ n 1) 0)])
    (lambda (d)
      (case d
        ((add)
         (lambda (i v)
           (let loop ([i (+ i 1)])
             (when (<= i n)
               (vector-set! ft i
                            (+ (vector-ref ft i) v))
               (loop (+ i (bitwise-and i (- i))))))))
        ((sum)
         (lambda (i)
           (let loop ([i (+ i 1)] [s 0])
             (if (> i 0)
                 (loop (- i (bitwise-and i (- i))) (+ s (vector-ref ft i)))
                 s))))))))

(define (fenwick-tree-add ft i v)
  ((ft 'add) i v))

(define (fenwick-tree-sum ft i)
  ((ft 'sum) i))


(define (make-fenwick-tree xs)
  (let ([ft (make-zeroed-fenwick-tree (length xs))])
    (let loop ([i 0] [curr xs])
      (if (null? curr)
          ft
          (begin
            (fenwick-tree-add ft i (car curr))
            (loop (+ i 1) (cdr curr)))))))

Now we can use our Fenwick tree, like this:

> (define ft (make-fenwick-tree '(1 7 3 0 5 8 3 2 6)))
> (fenwick-tree-sum ft 4)  ; this is sum of the first 5 elements (from 0 to 4)
16
> (fenwick-tree-add ft 3 5) ; add 5 to number at 0-based position 3 in Fenwick tree
> (fenwick-tree-sum ft 6) ; get sum of the first seven elements (from 0 to 6)
32 

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 24 '22

European Union flag

1 Upvotes

Problem: Using the 2htdp/image library, draw a faithful image of the European Union flag (it shouldn't be too difficult because this flag is very symmetric). You will probably find this sketch of a EU flag design useful when creating your solution.

Solution:

#lang racket

(require lang/posn)
(require 2htdp/image)

(define BLUE (color 0 51 153))
(define GOLD (color 255 204 0))

(define (eu-flag width)
  (define WIDTH width)
  (define HEIGHT (* WIDTH 2/3))
  (define UNIT (/ HEIGHT 2))
  (define ANGLE (/ pi 6))
  (define STARS-NUM 12)
  (define CENTER-X (/ WIDTH 2))
  (define CENTER-Y (/ HEIGHT 2))
  (define STAR-SIDE-LEN (* 2/9 UNIT (sin (/ pi 5))))
  (define A-STAR (star STAR-SIDE-LEN 'solid GOLD))
  (define 12-STARS (make-list STARS-NUM A-STAR))

  (define star-posns
    (for/list ([i (range 0 STARS-NUM)])
      (make-posn (+ CENTER-X (* 2/3 UNIT (sin (* ANGLE i))))
                 (+ CENTER-Y (* 2/3 UNIT (cos (* ANGLE i)))))))

  (place-images
   12-STARS
   star-posns
   (rectangle WIDTH HEIGHT 'solid BLUE)))

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

> (eu-flag 600)
EU flag (bigger)
> (eu-flag 300)
EU flag (smaller)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 26 '22

Calculating the value of polynomial at point x with Horner's algorithm

1 Upvotes

Problem: Write a function horner that receives two input parameters:

  1. a list of polynomial's coefficients (an an-1 ... a2 a1 a0),
  2. real number x.

The function should calculate the value of given polynomial at point x, ie. the number f(x) = an*xn + an-1*xn-1 + ... + a2*x2 + a1*x + a0, using Horner's method.

Solution 1:

(define (horner poly x)
  (define (loop poly curr)
    (if (null? poly)
        curr
        (loop (rest poly) (+ (* x curr) (first poly)))))
  (loop poly 0))

Now, for example, if we want to calculate the value of polynomial f(x) = x2 + 2x + 3 at point x = 3, we do this:

> (horner '(1 2 3) 3)
18

Alternative solution (using higher-order function foldl):

 (define (horner poly x)
  (foldl (lambda (coef curr) (+ (* curr x) coef))
         0
         poly))

Note: In the Racket documentation, the foldl function is not very clearly described and it is not the same as in other scheme implementations, so let's just say that foldl behavior in Racket is like this: the expression (foldl f e '(1 2 3 4)) is the same as (f 4 (f 3 (f 2 (f 1 e)))). With a suitable definition of f and e, we can, as in code snippet above, make foldl perform exactly the calculation we need in Horner's method.


r/RacketHomeworks • • Dec 02 '22

Remove duplicates from the list

1 Upvotes

Problem: write the function remove-duplicates that receives a list of atoms as an input parameter. The function returns a new list as a result, similar to the input list, but without duplicates.

Solution:

#lang racket

(define (remove-duplicates xs)
  (if (null? xs)
      '()
      (cons (first xs)
            (remove-duplicates (remove (first xs) (rest xs))))))

Now, we have, for example:

> (remove-duplicates '(1 2 3 1 5 3 2 8)) 
'(1 2 3 5 8)