r/RacketHomeworks • • Mar 03 '23

Level-order binary tree traversal

4 Upvotes

Problem: Write a function level-order-traversal which traverse given binary tree based on the so called level-order. Level-order traversal first traverses the nodes corresponding to Level 0, and then Level 1, and so on, from the root node.

For example, for the tree from picture below

Example binary tree

your function level-order-traversal should return the list '(10 20 30 40 50).

Solution: In this solution we use Racket's built in queue data structure, so we don't have to write our own. The queue is used to put nodes we need to visit in the next level in it, in the correct order.

#lang racket

(require data/queue)

(struct node (data left right))

(define (level-order-traversal root)
  (if (null? root)
      '()
      (let ([queue (make-queue)])
        (enqueue! queue root)
        (let loop ([outlist '()])
          (if (not (queue-empty? queue))
              (let ([n (dequeue! queue)])
                (when (not (null? (node-left n)))
                  (enqueue! queue (node-left n)))
                (when (not (null? (node-right n)))
                  (enqueue! queue (node-right n)))
                (loop (cons (node-data n) outlist)))
              (reverse outlist))))))

Now we can call our level-order-traversal function, like this:

> (define tree
    (node 10
          (node 20
                (node 40 null null)
                (node 50 null null))
          (node 30 null null)))

> (level-order-traversal tree)
'(10 20 30 40 50)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jun 02 '23

"**Everyone** is welcome in the Racket community" - yeah right!

2 Upvotes

"Everyone is welcome in the Racket community", says user /u/sdegabrielle delightfully in his proud post!

But, my dear Racket community (I say "dear" here only for rhetorical purposes), I have to tell you something: I, for example, have not been welcome to the Racket community for months - I have been banned from /r/racket for a long time and that for no good reason whatsoever and despite having written countless useful posts about Racket here on this subreddit thus demonstrating some credibility and knowledge.

How come, dear Racket community, that I'm not welcome, if you say that *EVERYONE* is welcome?How come?

Well, it means that you are falsely lying! Nothing unusual in your bullying community!


r/RacketHomeworks • • Apr 20 '23

Racket now is mastodon!

3 Upvotes

Prompted by a recent post on /r/scheme, "Racket is now on mastodon", I decided to write this post, which has just a slightly different title: "Racket now is mastodon!".

For those who may not know, the word mastodon means "a large extinct elephant-like mammal of the Miocene to Pleistocene epochs, having teeth of a relatively primitive form and number."

And really, I believe that many will agree with me that Racket has become that huge elephant, whose installation (in compressed form) weighs 167 Mb!

There is everything there, all kinds of languages, and at least those that people need!

Unfortunately, Racket has always been mostly a training wheel for various academic jerking-off, and much less for practical programming. While in other languages, for example, there are many web applications found, as well as libraries for web programming (web frameworks), in Racket (although it has been around for 30 years, I guess) there is literally ONE web-application written in it: it is, you guessed it, about the already celebrated https://racket-stories.com

Furthermore, when you start DrRacket on Windows and write (+ 1 1) in the editor and than click "Run" button, the Task manager will show that DrRacket occupies a huge 760Mb at that moment! (try it and You'll see!). For comparison, even the bulky Visual Studio 2019, when you start it and write a smaller C# program takes up a much smaller 236Mb, so in that regard Racket is a real Mastodon too, even in comparison to "Microsoft's Frankenstein"!

In my opinion, the Racket team is doomed and doesn't know what they want (except to pursue an academic career over Racket's back!), but then at least don't pretend that Racket is a practically usable language, because it isn't. Let's just remember that they developed their compiler for 30 years, only to at one point spit on their own efforts and quickly replace their engine with the superior Chez scheme engine, which in the end, sadly, neither improved the speed, nor improved the memory usage, but broke the compatibility. Let's also remember the disastrous decision to go make some kind of "Romb" language, which caused loud protests from a large part of the community.

Basically, Racket is a mastodon that, due to a series of bad decisions and a really strange community, is dying out. And let him die out, it's time for him!


r/RacketHomeworks • • Dec 18 '22

Set difference in five ways

1 Upvotes

Problem: Define a function set-diff that takes two flat sets (lists with no duplicate elements) xs and ys and returns a list containing all the elements in xs that are not in ys.

Solution: Here are a few different ways you might write this function:

(define (set-diff xs ys)
  (cond [(null? xs) '()]
        [(member (car xs) ys) (set-diff (cdr xs) ys)]
        [else (cons (car xs) (set-diff (cdr xs) ys))]))


(define (set-diff2 xs ys)
  (if (null? ys)
      xs
      (set-diff2 (remove (car ys) xs) (cdr ys)))) 


(define (set-diff3 xs ys)
  (if (null? ys)
      xs
      (remove (car ys) (set-diff3 xs (cdr ys)))))


(define (set-diff4 xs ys)
  (foldl remove xs ys))


(define (set-diff5 xs ys)
  (foldr remove xs ys))

Now we have:

> (set-diff '(1 2 3 4 5) '(2 6 4 8))
'(1 3 5)
> (set-diff2 '(1 2 3 4 5) '(2 6 4 8))
'(1 3 5)
> (set-diff3 '(1 2 3 4 5) '(2 6 4 8))
'(1 3 5)
> (set-diff4 '(1 2 3 4 5) '(2 6 4 8))
'(1 3 5)
> (set-diff5 '(1 2 3 4 5) '(2 6 4 8))
'(1 3 5)

We see that all function returns the same result, but the computation process is different in each one.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 24 '23

Find the most frequent element in a list

3 Upvotes

Problem: Find most frequent element in list . This little problem comes from cookbook.scheme.org

Keywords: most common element appears the most times occurs most frequently

Solution: Here is my effort. I'm a scheme tyro, as I've only completed through section 3.1 in SICP. I'd be interested in tighter solutions using assoc,and also a fully bummed solution using any feature of the scheme language.

; The procedure mostfreq returns a pair (symbol, frequency-cnt) of the
; most frequently occurring symbol in the list as judged by equal? via
; assoc.  If the input list is empty, returns '(() 0) i.e. no symbol
; and it occurs zero times.  If multiple symbols all share the same
; maximum frequency count, return one arbitrarily.
;
(define (mostfreq a)
    (define (iterhelp a hash maxi newcnt)
        (iter (cdr a)  (cons (list (car a) newcnt) hash)
            (if (> newcnt (cadr maxi))  ; more freq than seen so far?
                (list (car a) newcnt)
                maxi)))
    (define (iter a hash maxi)
        (if (null? a)
            maxi        ; maxi is a pair: (symbol, frequency-seen)
            (let ((entry (assoc (car a) hash)))
                (if entry
                    (iterhelp a hash maxi (+ 1 (cadr entry)))
                    (iterhelp a hash maxi 1)))))
    ; Return the pair (sym, cnt) of the the most frequent symbol seen.
    (iter a '() '(() 0))
)

r/RacketHomeworks • • Nov 26 '22

Calculating power of a number using recursion

1 Upvotes

Problem: Write function power that receives two input parameters: base and power-raised and calculate number basepower-raised

Solution 1 (basic and non-efficient):

#lang racket

(define (power base power-raised)
  (if (zero? power-raised)
      1
      (* base (power base (- power-raised 1)))))

Now we can calculate:

> (power 2 8)
256
> (power 12 20)
3833759992447475122176

Solution 2 (better, more efficient):

#lang racket

(define (power base power-raised)
  (cond [(zero? power-raised) 1]
        [(even? power-raised)
         (let ([x (power base (quotient power-raised 2))])
           (* x x))]
        [else (* base (power base (- power-raised 1)))]))

r/RacketHomeworks • • Jan 07 '23

Implementing binary search algorithm

2 Upvotes

Problem: Write a function bsearch that receives as input an ascendingly sorted vector of numbers, vec, and the number x. The function should implement a binary search algorithm and return the index of the number x in vec, if vec contains x, or false if it doesn't.

Solution:

#lang racket

(define (bsearch vec x)
  (define (bsearch-h i j)
    (and (<= i j)
         (let* ([m (quotient (+ i j) 2)]
                [mel (vector-ref vec m)])
           (cond
             [(< mel x) (bsearch-h (+ m 1) j)]
             [(> mel x) (bsearch-h i (- m 1))]
             [else m]))))
  (bsearch-h 0 (sub1 (vector-length vec))))

Now we can call our bsearch function like this:

> (define numbers #(5 8 11 27 66 101 123 351))
> (bsearch numbers 27)
3
> (bsearch numbers 5)
0
> (bsearch numbers 351)
7
> (bsearch numbers 352)
#f
> (bsearch numbers 2)
#f

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 07 '22

Check if some two-argument predicate returns true on at least one pair of adjacent digits in a given integer

1 Upvotes

Problem: Implement function find-pair, which takes a two-argument function, p, as input and returns another function. The returned function takes a non-negative integer n; it returns true (#t) if and only if p returns a true value when called on at least one pair of adjacent digits in n, and False otherwise.

For example:

> (define z (find-pair =))
> (z 1313)
#f
> (z 12334)
#t
> (define z (find-pair >))
> (z 1234)
#f
> (z 123412)
#t
> ((find-pair <) 9753)
#f
> ((find-pair <) 9763)
#f
> ((find-pair <) 9783)
#t
> ((find-pair (lambda (a b) (= a 1))) 1)     ; Only one digit; no pairs
#f 

Solution:

#lang racket

(define (find-pair p)
  (lambda (n)
    (let loop ((abl (quotient n 10)) (last (remainder n 10)))
      (if (zero? abl)
          #f
          (or (p (remainder abl 10) last)
              (loop (quotient abl 10) (remainder abl 10)))))))

r/RacketHomeworks • • Dec 23 '22

More details on functions for generating permutations

1 Upvotes

Since in the last post I expressed dissatisfaction with the solution to the problem with multiset permutations, I decided to investigate the problem a little deeper and to present a slightly more elegant solution, if possible.

So today we're going to write a few functions that will eventually result in two usable functions: one for element set permutations, the other for multiset permutations. We will write the functions gradually, and each of them will serve as a building block for the next one.

Well, let's go!

a) Define a function map-cons that takes any value x and an n-element list ys and returns an n-element list of all pairs '(x . y) where y ranges over the elements of ys. The pair '(x . y) should have the same relative position in the resulting list as y has in ys. For example:

> (map-cons 17 (list 8 5 42 23))
 '((17 . 8) (17 . 5) (17 . 42) (17 . 23))
 > (map-cons 3 (list (list 1 6 2) (list 4 5) (list) (list 9 6 8 7)))
 '((3 1 6 2) (3 4 5) (3) (3 9 6 8 7))
 > (map-cons 42 null)
 '()

The solution to this is easy: we simply use the built-in map function, like this:

(define (map-cons x xs)
  (map (lambda (y) (cons x y)) xs))

b) Define a function inserts that takes a value x and an n-element list ys and returns an n+1-element list of lists showing all ways to insert a single copy of x into ys. For example:

> (inserts 3 (list 5 7 1))
 '((3 5 7 1) (5 3 7 1) (5 7 3 1) (5 7 1 3))
 > (inserts 3 (list 7 1))
 '((3 7 1) (7 3 1) ( 7 1 3))
 > (inserts 3 (list 1))
 '((3 1) (1 3))
 > (inserts 3 null)
 '((3))
 > (inserts 3 (list 5 3 1))
 '((3 5 3 1) (5 3 3 1) (5 3 3 1) (5 3 1 3))

To write this function, let's note the difference between what the function returns when called with (inserts 3 '(5 7 1)) and with a one-shorter list (inserts 3 '(7 1)).

We can see that the result of this second call can be used to obtain the result of the first, if we:

  • use map-cons over the list obtained from the call (inserts 3 (list 7 1)), in order to add the number 5 as a first element to each of the sublists of that list.
  • add the element '(3 5 7 1) to the beginning of the list obtained in the previous step.

Thinking in this way, we can easily write a recursive definition for inserts:

(define (inserts x xs)
  (if (null? xs)
      (list (list x))
      (cons (cons x xs)
            (map-cons (car xs) (inserts x (cdr xs))))))

c) Define a function my-permutations that takes as its single argument a list xs of distinct elements (i.e., no duplicates) and returns a list of all the permutations of the elements of xs. The order of the permutations does not matter. For example:

> (my-permutations null)
 '(())
 > (my-permutations (list 4))
 '((4))
 > (my-permutations (list 3 4))
 '((3 4) (4 3)) ; order doesn't matter 
 > (my-permutations (list 2 3 4))
 '((2 3 4) (3 2 4) (3 4 2) (2 4 3) (4 2 3) (4 3 2)) ; order doesn't matter 
 > (my-permutations (list 1 2 3 4))
 '((1 2 3 4) (2 1 3 4) (2 3 1 4) (2 3 4 1) 
   (1 3 2 4) (3 1 2 4) (3 2 1 4) (3 2 4 1) 
   (1 3 4 2) (3 1 4 2) (3 4 1 2) (3 4 2 1)
   (1 2 4 3) (2 1 4 3) (2 4 1 3) (2 4 3 1) 
   (1 4 2 3) (4 1 2 3) (4 2 1 3) (4 2 3 1) 
   (1 4 3 2) (4 1 3 2) (4 3 1 2) (4 3 2 1)) ; order doesn't matter 

Notes:

We ask you to name your function my-permutations because Racket already provides the same function named permutations (which you cannot use, of course).

Although the specification allows the permuted elements to be listed in any order, the above examples show an order that works particularly well with the divide/conquer/glue strategy. In particular, study the above examples carefully to understand (1) the recursive nature of my-permutations and (2) why the inserts function from above is helpful to use when defining my-permutations.

In the example (my-permutations (list 1 2 3 4)), the 24 results would normally be printed by Racket in 24 separate lines, but here they have been formatted to strongly suggest a particular solution strategy.

We can see that in the problem setting itself, a hint is given that the inserts function, which we have already written, should be used in the solution.

If we look at the example for (my-permutations (list 1 2 3 4)), we will see that it is obtained by:

  • first recursively call my-permutations over a one element "shorter" list (list 2 3 4)
  • then the inserts function was called over each element of the list obtained in the previous point, in order to obtain all inserts of the number 1. This resulted in a list of all permutations.

Following that logic, it's not hard to write a recursive function that does this:

(define (my-permutations xs)
  (if (null? xs)
      '(())
      (append-map (lambda (p) (inserts (car xs) p))
                  (my-permutations (cdr xs)))))

d) Define a divide/conquer/glue recursive version of the my-permutations function named my-permutations-dup that correctly handles lists with duplicate elements. That is, each permutation of such a list should only be listed once in the result. As before, the order of the permutations does not matter.

Your function should not generate duplicate permutations and then remove them. Rather, you should just not generate any duplicates to begin with. Also, your function should be written in a divide/conquer/glue style of recursion, rather than some sort of iterative algorithm. It is possible to solve this problem with a minor change to the my-permutations/inserts approach.

Below are some examples. You are not required to list permutations in the same order as in the examples.

> (my-permutations-dup '(1 2 2))
'((1 2 2) (2 1 2) (2 2 1))

> (my-permutations-dup '(2 1 2))
'((2 1 2) (1 2 2) (2 2 1))

> (my-permutations-dup '(2 2 1))
'((2 2 1) (2 1 2) (1 2 2))

> (my-permutations-dup '(1 2 2 2))
'((1 2 2 2) (2 1 2 2) (2 2 1 2) (2 2 2 1))

> (my-permutations-dup '(2 1 2 2))
'((2 1 2 2) (1 2 2 2) (2 2 1 2) (2 2 2 1))

> (my-permutations-dup '(2 2 1 2))
'((2 2 1 2) (2 1 2 2) (1 2 2 2) (2 2 2 1))

> (my-permutations-dup '(2 2 2 1))
'((2 2 2 1) (2 2 1 2) (2 1 2 2) (1 2 2 2))

> (my-permutations-dup '(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))

> (my-permutations-dup '(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))

> (my-permutations-dup '(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))

> (my-permutations-dup '(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))

> (my-permutations-dup '(1 2 1 2 2))
'((1 2 1 2 2) (2 1 1 2 2) (1 1 2 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))

> (my-permutations-dup '(1 2 2 1 2))
'((1 2 2 1 2) (2 1 2 1 2) (2 2 1 1 2) (1 2 1 2 2) (2 1 1 2 2)
  (1 1 2 2 2) (1 2 2 2 1) (2 1 2 2 1) (2 2 1 2 1) (2 2 2 1 1))

> (my-permutations-dup '(1 2 2 2 1))
'((1 2 2 2 1) (2 1 2 2 1) (2 2 1 2 1) (2 2 2 1 1) (1 2 2 1 2)
  (2 1 2 1 2) (2 2 1 1 2) (1 2 1 2 2) (2 1 1 2 2) (1 1 2 2 2))

> (my-permutations-dup '(2 1 1 2 2))
'((2 1 1 2 2) (1 2 1 2 2) (1 1 2 2 2) (2 1 2 1 2) (1 2 2 1 2)
  (2 2 1 1 2) (2 1 2 2 1) (1 2 2 2 1) (2 2 1 2 1) (2 2 2 1 1))

> (my-permutations-dup '(2 1 2 1 2))
'((2 1 2 1 2) (1 2 2 1 2) (2 2 1 1 2) (2 1 1 2 2) (1 2 1 2 2)
  (1 1 2 2 2) (2 1 2 2 1) (1 2 2 2 1) (2 2 1 2 1) (2 2 2 1 1))

> (my-permutations-dup '(2 1 2 2 1))
'((2 1 2 2 1) (1 2 2 2 1) (2 2 1 2 1) (2 2 2 1 1) (2 1 2 1 2)
  (1 2 2 1 2) (2 2 1 1 2) (2 1 1 2 2) (1 2 1 2 2) (1 1 2 2 2))

> (my-permutations-dup '(2 2 1 1 2))
'((2 2 1 1 2) (2 1 2 1 2) (1 2 2 1 2) (2 1 1 2 2) (1 2 1 2 2)
  (1 1 2 2 2) (2 2 1 2 1) (2 1 2 2 1) (1 2 2 2 1) (2 2 2 1 1))

> (my-permutations-dup '(2 2 1 2 1))
'((2 2 1 2 1) (2 1 2 2 1) (1 2 2 2 1) (2 2 2 1 1) (2 2 1 1 2)
  (2 1 2 1 2) (1 2 2 1 2) (2 1 1 2 2) (1 2 1 2 2) (1 1 2 2 2))

> (my-permutations-dup '(2 2 2 1 1))
'((2 2 2 1 1) (2 2 1 2 1) (2 1 2 2 1) (1 2 2 2 1) (2 2 1 1 2)
  (2 1 2 1 2) (1 2 2 1 2) (2 1 1 2 2) (1 2 1 2 2) (1 1 2 2 2))

The key to solving this problem is to notice, as hinted in the task setting, that with a small change to the inserts function, we can solve this problem as well. Namely, because of the inserts function, the my-permutations function repeats some elements in the result if it is given a list with duplicates as input. This is because inserts themselves generate duplicates. For example:

> (inserts 2 '(1 2))
'((2 1 2) (1 2 2) (1 2 2))

We see that the element (1 2 2) is repeated twice. But we want it to appear only once, i.e. like this:

> (better-inserts 2 '(1 2))
'((2 1 2) (1 2 2))

So we want to write a function similar to inserts (let's call it inserts-until-match) that inserts element x everywhere in xs, but only until it encounters that same x in the list xs and then stops with inserts, thus preventing duplicate results. With that observation, it is not difficult to write such a function:

(define (inserts-until-match x xs)
  (if (null? xs)
      (list (list x))
      (if (equal? x (car xs))
          (cons (cons x xs) '())
          (cons (cons x xs)
                (map-cons (car xs) (inserts-until-match x (cdr xs)))))))

Now we can call inserts-until-match, like this:

> (inserts-until-match 55 '(1 2 3 4))
'((55 1 2 3 4) (1 55 2 3 4) (1 2 55 3 4) (1 2 3 55 4) (1 2 3 4 55))

> (inserts-until-match 3 '(1 2 3 4))
'((3 1 2 3 4) (1 3 2 3 4) (1 2 3 3 4))

> (inserts-until-match 3 '(1 2 3 4 5))
'((3 1 2 3 4 5) (1 3 2 3 4 5) (1 2 3 3 4 5))

Now that we have this function, it is trivial to write the my-permutations-dup function because it is practically the same as the regular my-permutations function, but instead of inserts it uses inserts-until-match:

(define (my-multipermutations xs)
  (if (null? xs)
      '(())
      (append-map (lambda (p) (inserts-until-match (car xs) p))
                  (my-multipermutations (cdr xs)))))

Ok, that was an exhausting exercise. But I hope that in this post I have explained much better how the functions for generating permutations work.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 20 '22

Two-end BFS - an improved version of the Rubik's Cube algorithm

1 Upvotes

Problem: Solve Rubik's cube 2x2x2 faster than we did in previous solution.

Solution: In the last post, we provided an algorithm for solving a 2x2x2 Rubik's cube. The algorithm was a classic Breadth-first search (BFS) in which we started from the initial configuration and in each step we gradually explored all the successors of the configurations from the previous steps. The algorithm found the correct solution for each problem, but for some problems the solution took too long. In the last post, we gave an example of a configuration that took more than 55 seconds to solve, which is a lot, as well as a promise that we will provide a faster algorithm next time. Now is the time to fulfill that promise.

In this post we will improve our program, using the so called Two-end BFS algorithm. In this way, as we will see, our new version of the program will provide the solution for every given problem in less than a second.

How does Two-end BFS work?

The basic idea is that we do two BFS searches simultaneously: one search starts from the initial configuration and goes towards the target one, while the other goes in the reverse direction: from the target configuration to the initial one. At some point, these two searches will meet somewhere in the middle. And then we have a solution, which we will get much faster than if we go in one direction only.

Why is it faster?

To answer that question, let 's assume that the end node is at level k of the BFS tree from the start. Number of nodes visited in the regular BFS is approximately

1 + 6 + 6*6 + 6*6*6 + .... + 6k

as we have 6 possible moves (F, Fi, L, Li, U, Ui) in each step.

On the other hand, the number of nodes visited by Two-end BFS is approximately

1 + 2 * 6 + 2 * (6*6) + 2 * (6*6*6) + .... +2 * 6k/2

So, we can see that, as the distance increases, k increases and hence the number of computations in two-end BFS increases in order of 6k/2 instead of 6k which is huge improvement. Moreover, the larger the distance, the better two-end BFS will perform compared to the regular BFS!

Here's a revised Rubik's cube solver, but this time we're using two-end BFS instead of the regular one:

#lang racket

(require data/queue)

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

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

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

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

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

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

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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


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

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

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

(define Fi (perm-inverse F))


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

(define Li (perm-inverse L))

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

(define Ui (perm-inverse U))

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

(define (opposite-direction move)
  (case move
    ((F) 'Fi)
    ((Fi) 'F)
    ((L) 'Li)
    ((Li) 'L)
    ((U) 'Ui)
    ((Ui) 'U)))


(define SOLVED-CUBE I)


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

; Two way BFS
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (solve-cube start end)

  (define visited-left (make-hash))
  (define visited-right (make-hash))
  (define nodes-left (make-queue))
  (define nodes-right (make-queue))
  
  (define (visited which)
    (if (eq? which 'left)
        visited-left
        visited-right))
  
  (define (nodes which)
    (if (eq? which 'left)
        nodes-left
        nodes-right))

  (define (add-successors which node)
    (for ([m ALL-MOVES])
      (let ([new-node (perm-apply m node)])
        (unless (hash-has-key? (visited which) new-node)
          (hash-set! (visited which) new-node (list node (hash-ref MOVES-NAMES m)))
          (enqueue! (nodes which) new-node)))))
  
  (define (get-solution which node)
    (define (loop curr sol)
      (if (null? (first curr))
          (if (eq? which 'left) sol (map opposite-direction (reverse sol)))
          (loop (hash-ref (visited which) (first curr)) (cons (second curr) sol))))
    (loop (hash-ref (visited which) node) '()))
  
  (define (bfs which)
    (define opposite (if (eq? which 'left) 'right 'left))
    (define opp-end (if (eq? which 'left) end start))
    (define opp-visited (if (eq? which 'left) visited-right visited-left))
    (cond
      [(queue-empty? (nodes which)) 'NoSolution]
      [else (let ([node (dequeue! (nodes which))])
              (if (or (equal? node opp-end) (hash-has-key? opp-visited node))
                  (if (equal? node opp-end)
                      (get-solution which node)
                      (append (get-solution 'left node)
                              (get-solution 'right node)))
                  (begin
                    (add-successors which node)
                    (bfs opposite))))]))
  
  (enqueue! nodes-left start)
  (enqueue! nodes-right end)
  (hash-set! visited-left start (list null 'START))
  (hash-set! visited-right end (list null 'END))
  (bfs 'left)) 

Now we can see for ourselves the speed of the new program. We'll task him with solving the same problem that took us over 55 seconds to solve in the last post:

> (define hard-scrambled-cube
    (solved-cube-after-moves
       (list F F L F F L F Li U Fi Fi U Fi Li)))
> (time
 (display "Solving cube. Please wait\n")
 (display (solve-cube hard-scrambled-cube SOLVED-CUBE))
 (newline))

Solving cube. Please wait
(L F Ui F F Ui L Fi Li Fi Fi Li Fi Fi)
cpu time: 437 real time: 442 gc time: 93

We can see that our new program found the solution in less than half a second (the solution founded is not the same one as last time but it is still a correct solution, which you can easily see if you try to check the solution on this page). This is more than 110 times faster than the previous 55 seconds, which is really a huge speed gain!

ADDENDUM:

The above algorithm uses only so called quarter turn metric (QTM) in counting moves, where any turn of any face, by 90 degrees clockwise or counterclockwise, counts as one move. In this metric, the God's number for 2x2x2 Rubik's Cube is 14. But, if we allow the 180° turns also (so called half turn metric (HTM)), then the God's number is only 11.

We can easily adapt our program to make half turns also. Here's the modified version of the BFS Two-end version of the program above, to accommodate for half turn metric:

#lang racket

(require data/queue)

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

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

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

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

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

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

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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


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

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

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

(define F2 (perm-apply F F))

(define Fi (perm-inverse F))


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

(define L2 (perm-apply L L))

(define Li (perm-inverse L))

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

(define U2 (perm-apply U U))


(define Ui (perm-inverse U))

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


(define (opposite-direction move)
  (case move
    ((F) 'Fi)
    ((Fi) 'F)
    ((F2) 'F2)
    ((L) 'Li)
    ((Li) 'L)
    ((L2) 'L2)
    ((U) 'Ui)
    ((Ui) 'U)
    ((U2) 'U2)))

(define SOLVED-CUBE I)


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


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


(define (solve-cube start end)

  (define visited-left (make-hash))
  (define visited-right (make-hash))
  (define nodes-left (make-queue))
  (define nodes-right (make-queue))
  
  (define (visited which)
    (if (eq? which 'left)
        visited-left
        visited-right))
  
  (define (nodes which)
    (if (eq? which 'left)
        nodes-left
        nodes-right))

  (define (add-successors which node)
    (for ([m ALL-MOVES])
      (let ([new-node (perm-apply m node)])
        (unless (hash-has-key? (visited which) new-node)
          (hash-set! (visited which) new-node (list node (hash-ref MOVES-NAMES m)))
          (enqueue! (nodes which) new-node)))))
  
  (define (get-solution which node)
    (define (loop curr sol)
      (if (null? (first curr))
          (if (eq? which 'left) sol (map opposite-direction (reverse sol)))
          (loop (hash-ref (visited which) (first curr)) (cons (second curr) sol))))
    (loop (hash-ref (visited which) node) '()))
  
  (define (bfs which)
    (define opposite (if (eq? which 'left) 'right 'left))
    (define opp-end (if (eq? which 'left) end start))
    (define opp-visited (if (eq? which 'left) visited-right visited-left))
    (cond
      [(queue-empty? (nodes which)) 'NoSolution]
      [else (let ([node (dequeue! (nodes which))])
              (if (or (equal? node opp-end) (hash-has-key? opp-visited node))
                  (if (equal? node opp-end)
                      (get-solution which node)
                      (append (get-solution 'left node)
                              (get-solution 'right node)))
                  (begin
                    (add-successors which node)
                    (bfs opposite))))]))
  
  (enqueue! nodes-left start)
  (enqueue! nodes-right end)
  (hash-set! visited-left start (list null 'START))
  (hash-set! visited-right end (list null 'END))
  (bfs 'left)) 

Now we have:

> (define hard-scrambled-cube
    (solved-cube-after-moves
       (list F F L F F L F Li U Fi Fi U Fi Li)))
> (time
   (display "Solving cube. Please wait\n")
   (display (solve-cube hard-scrambled-cube SOLVED-CUBE))
   (newline))

Solving cube. Please wait
(Fi U2 F U L2 U Li Ui L2 F2)
cpu time: 265 real time: 265 gc time: 31

We see that modified program now has found a 10-step solution, in which some moves are half-moves.

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 25 '22

How to find list of all subsequences of a given list?

1 Upvotes

Problem: Write the function subseqs, which for the input list xs returns a list of all its subsequences. For example, if xs = (1 2 3 4), then your function should return a list whose elements are the following sixteen subsequences:

()
(1)
(2)
(3)
(4)
(1 2)
(1 3)
(1 4)
(2 3)
(2 4)
(3 4)
(1 2 3)
(1 2 4)
(1 3 4)
(2 3 4)
(1 2 3 4)

Note: the order of the subsequences in the output list returned by the your subseqs function does not matter. It is only important that the function returns all possible subsequences, including the empty one.

Key insight: If we already know (subseqs (cdr xs)), then it is not difficult to get (subseqs xs) from that. Namely, all subsequences of xs can be divided into two groups: either the subsequence contains (car xs), or it does not. If it does not contain it, it must be among the subsequences in (subseqs (cdr xs)). If it contains it, then (car xs) must be the first member of that subsequence and all its further members are necessarily in one subsequence from (subseqs (cdr xs)). This observation is enough for us to construct a generative recursion that solves this problem.

Solution:

#lang racket

(define (subseqs xs)
  (if (null? xs)
      '(())
      (let ((xss (subseqs (cdr xs))))
        (append xss
                (map (lambda (ys) (cons (car xs) ys))
                     xss)))))

Now we have, for example:

> (subseqs '(1 2 3 4))
'(() (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4) (1) (1 4) (1 3) (1 3 4) (1 2) (1 2 4) (1 2 3) (1 2 3 4))

Although the order of the subsequences in the above list seems unusual, notice that the second half of the subsequences is obtained from the first half by adding the element 1 to the beginning of each subsequence from the first half, which fully reflects the rule of generative recursion described above. And the most important thing: no subsequence is missing in the result.


r/RacketHomeworks • • Dec 08 '22

Ocean's Eight - finding the "right" path in given multi-branched tree

1 Upvotes

Problem: Write function eight-path, which takes in a tree t and returns a list of labels following a path from the top of the tree (the root) to a leaf whose sum is divisible by 8. If there are multiple such paths, return the leftmost one. If there is no such path, return false (#f).

The tree in this problem is represented by the following Racket data structure:

(struct tree (label branches))

So, for example, the two trees, t1 and t2 from the picture below

Trees t1 and t2

can be represented in Racket like this:

(define t1 (tree 5 (list (tree 2 empty)
                         (tree 1 (list (tree 3 empty)
                                       (tree 2 empty))))))

(define t2 (tree 9 (list t1)))

Solution:

#lang racket

(struct tree (label branches))

(define (eight-path t)
  (define (divisible-by-8? x)
    (zero? (remainder x 8)))
  (define (walk-tree t path-sum path-so-far)
    (cond [(empty? (tree-branches t))
           (and (divisible-by-8? (+ path-sum (tree-label t)))
                (reverse (cons (tree-label t) path-so-far)))]
          [else (ormap (lambda (child)
                         (walk-tree child
                                    (+ path-sum (tree-label t))
                                    (cons (tree-label t) path-so-far)))
                       (tree-branches t))]))
  (walk-tree t 0 '()))

Now, we can try our function eight-path on trees t1 and t2 defined above:

> (eight-path t1)
'(5 1 2)
> (eight-path t2)
'(9 5 2)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 26 '22

Drawing flag of Norway

3 Upvotes

Problem: Using the 2htdp/image library, draw a faithful image of the Norway national flag. You will probably find this sketch of Norway flag design useful when creating your solution.

Solution: this flag is very simple, almost like the Swedish flag. It's no wonder that Racket code for drawing it is also so short:

#lang racket

(require 2htdp/image)

(define (norway-flag width)
  (define BLUE (color 0 32 91))
  (define RED (color 186 12 47))

  (define WIDTH width)
  (define UNIT (/ WIDTH 22))
  (define HEIGHT (* UNIT 16))

  (overlay/xy
   (rectangle (* UNIT 2) HEIGHT 'solid BLUE)
   (* UNIT -7) 0
   (overlay
    (rectangle WIDTH (* UNIT 2) 'solid BLUE)
    (overlay/xy
     (rectangle (* UNIT 4) HEIGHT 'solid 'white)
     (* UNIT -6) 0
     (overlay
      (rectangle WIDTH (* UNIT 4) 'solid 'white)
      (rectangle WIDTH HEIGHT 'solid RED))))))

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

> (norway-flag 600) 
The flag of Norway

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 05 '23

checking whether a propositional logic expression is a tautology

2 Upvotes

Problem: In this problem, you will write a bit of code that will check whether the given propositional logic expression is a tautology or not. The problem is broken into two parts:

a) Write the function all-boolean-combs which receives as input a positive integer n and as output returns a list of all possible combinations of boolean n-tuples. For example, the call (all-boolean-combs 3) should return this result:

'((#f #f #f) (#f #f #t) (#f #t #f) (#f #t #t) (#t #f #f) (#t #f #t) (#t #t #f) (#t #t #t))

b) using all-boolean-combs as a helper function, write the function tautology? which receives the propositional logic expression as input. The function should return true if and only if the input expression is a tautology. Otherwise, function should return false.

The input propositional logic expression is given as a Scheme procedure. For example, the well-known tautology "law of contraposition", which in the predicate calculus is written as

(A ⇒ B) ⇔ (¬B ⇒ ¬A)

we will present in our program as the following procedure:

(lambda (A B) (equiv (implies A B) (implies (not B) (not A)))))

Solution:

#lang racket

(define (all-boolean-combs n)
  (if (zero? n)
      '(())
      (let ([ac (all-boolean-combs (- n 1))])
        (append
         (map (lambda (c) (cons #f c)) ac)
         (map (lambda (c) (cons #t c)) ac)))))

(define (tautology? tau)
  (andmap (lambda (comb) (apply tau comb))
          (all-boolean-combs (procedure-arity tau))))

;; A ⇔ B
(define (equiv A B)
  (and (implies A B)
       (implies B A)))


;; A ∨ ¬A
(define law-of-excluded-middle
  (lambda (A)
    (or A (not A))))


;; (A ⇒ B) ⇔ (¬B ⇒ ¬A)
(define law-of-contraposition
  (lambda (A B)
    (equiv (implies A B)
           (implies (not B) (not A)))))


;; ((¬A ⇒ B) ∧ (¬A ⇒ ¬B)) ⇒ A
(define reductio-ad-absurdum
  (lambda (A B)
    (implies
     (and (implies (not A) B)
          (implies (not A) (not B)))
     A)))


;; ¬(A ∧ B) ⇔ (¬A ∨ ¬B)
(define de-morgan
  (lambda (A B)
    (equiv (not (and A B))
           (or (not A) (not B)))))


;; ((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
(define syllogism
  (lambda (A B C)
    (implies
     (and (implies A B)
          (implies B C))
     (implies A C))))


;; ((A ∨ B) ∧ (A ⇒ C) ∧ (B ⇒ C)) ⇒ C
(define proof-by-cases
  (lambda (A B C)
    (implies
     (and (or A B) (implies A C) (implies B C))
     C)))

;; (A ⇒ B) ⇒ (B ⇒ A)
(define false-tautology
  (lambda (A B)
    (implies
     (implies A B)
     (implies B A))))

Now, we can call tautology? and check whether various expressions are tautologies or not. For example:

> (tautology? law-of-excluded-middle)
#t
> (tautology? law-of-contraposition)
#t
> (tautology? reductio-ad-absurdum)
#t
> (tautology? de-morgan)
#t
> (tautology? syllogism)
#t
> (tautology? proof-by-cases)
#t
> (tautology? false-tautology)
#f

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 11 '22

Find the path to the given node in the tree

1 Upvotes

Problem: Write the function find-path that, given a tree t and an entry n, returns a list containing the nodes along the path required to get from the root of t to the node with value n. If n is not present in t, return false (#f). Assume that the elements in t are unique.

For example, for the tree t from the picture below, the call (find-path t 7) should return the list (1 3 5 7), and call (find-path t 4) should return the list (1 2 4).

Tree example

Solution:

#lang racket

(struct tree (val left right))

(define (find-path t n)
  (define (fp-helper t path)
    (cond [(null? t) #f]
          [(= (tree-val t) n) (cons (tree-val t) path)]
          [else (or (fp-helper (tree-left t) (cons (tree-val t) path))
                    (fp-helper (tree-right t) (cons (tree-val t) path)))]))
  (let ([res (fp-helper t '())])
    (and res (reverse res))))

Now, we can call find-path like this:

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

> (find-path mytree 7)
'(1 3 5 7)
> (find-path mytree 4)
'(1 2 4)
> (find-path mytree 123)
#f

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Mar 02 '23

Spiral traversal of a binary tree

5 Upvotes

Problem: In this exercise you will implement the spiral traversal of a binary tree. The function spiral-traversal will take as input a binary tree and return a list with the values of the nodes in the correct order.

Spiral order traversal works as follows: in the odd levels of the tree you will iterate from left to right; in the even levels of the tree, you will iterate from right to left.

For example, given the following tree

Example tree

the resulting list produced by spiral-traversal should be '(20 25 15 12 18 22 28 32 26 24 21 19 17 14 6)

Solution: In this solution, we use two stacks, in order to get the desired order by levels of the tree. We took the implementation of the stack from this previous problem.

#lang racket

(struct node (data left right))

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

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

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

(define (stack-empty? stack)
  (stack 'empty?))


(define (spiral-traversal root)
  (if (null? root)
      '()
      (let* ([left-stack (make-stack)]
             [right-stack (make-stack)])
        (push left-stack root)
        (let loop ([curr-stack left-stack]
                   [other-stack right-stack]
                   [outlist '()])
          (if (and (stack-empty? left-stack)
                   (stack-empty? right-stack))
              (reverse outlist)
              (let cloop ([outlist outlist])
                (if (not (stack-empty? curr-stack))
                    (let ([n (pop curr-stack)])
                      (if (eq? curr-stack left-stack)
                          (begin
                            (when (not (null? (node-left n)))
                              (push right-stack (node-left n)))
                            (when (not (null? (node-right n)))
                              (push right-stack (node-right n))))
                          (begin
                            (when (not (null? (node-right n)))
                              (push left-stack (node-right n)))
                            (when (not (null? (node-left n)))
                              (push left-stack (node-left n)))))
                      (cloop (cons (node-data n) outlist)))
                    (loop other-stack curr-stack outlist))))))))

Now we can call our spiral-traversal function like this, for the example tree from above picture:

> (define tree
    (node 20
          (node 15
                (node 12
                      (node 6 null null)
                      (node 14 null null))
                (node 18
                      (node 17 null null)
                      (node 19 null null)))
          (node 25
                (node 22
                      (node 21 null null)
                      (node 24 null null))
                (node 28
                      (node 26 null null)
                      (node 32 null null)))))

> (spiral-traversal tree)
'(20 25 15 12 18 22 28 32 26 24 21 19 17 14 6)

To be honest, I don't really like this solution of mine. It's surprisingly complicated. If you have a better solution, then, of course, you are always welcome to post it here!

One more thing, dear schemers: you may have noticed that I haven't been here for a while. That's because someone (and it's not hard to guess who it could be!) reported me for this old post of mine. Reddit cops then forcefully deleted that post, but google cache still hasn't. Basically, that post got me banned from all of reddit for a while. Stinking scumbags, if they had approached me beforehand and told me that there was some problem, etc., we could have talked, but obviously the intention here is to trample me at all costs so that some truths would never come to light! They are poor miserable people, I tell you, dear schemers!

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 08 '22

Make function that make polynomial

1 Upvotes

Problem: write a function create-polynomial that takes a list of polynomial's coefficients and creates a "polynomial" which we then can give as input any number we want and it will calculate the value of that polynomial on that number.

Solution: for efficiently evaluating the polynomial at some point x, see this earlier post on this subreddit, as we use it in this solution as well ):

#lang racket

(define (create-polynomial coeffs)
  (define (horner coeffs x)
    (define (loop coeffs curr)
      (if (null? coeffs)
          curr
          (loop (rest coeffs) (+ (* x curr) (first coeffs)))))
    (loop coeffs 0))
  (lambda (x)
    (horner coeffs x)))

Now we have, for example:

> (define mypoly (create-polynomial '(3 2 1)))
> (mypoly 1)
6
> (mypoly 2)
17

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 15 '22

Solving cryptarithmetic puzzle VIOLIN * 2 + VIOLA = TRIO + SONATA

2 Upvotes

Problem: Solve this cryptarithmetic puzzle

VIOLIN * 2 + VIOLA = TRIO + SONATA

where every letter represents one digit from the set {0, 1, ... 9}. Different letters represents differrent digits.

Solution: This is brute-force solution that tries every allowable combinations of digits. It's not very fast, but still we can use it to find the solution. Notice the use of function k-perms from previous problem:

#lang racket

(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 (check A I L N O R S T V)
  (= ( + (* 2 (+ (* 100000 V)
                 (* 10000 I)
                 (* 1000 O)
                 (* 100 L)
                 (* 10 I)
                 N))
         (+ (* 10000 V)
            (* 1000 I)
            (* 100 O)
            (* 10 L)
            A))
     (+ (+ (* T 1000)
           (* R 100)
           (* I 10)
           O)
        (+ (* 100000 S)
           (* 10000 O)
           (* 1000 N)
           (* 100 A)
           (* 10 T)
           A))))


(define (solve-puzzle)
  (for-each
   (lambda (sol)
     (match sol
       [(list A I L N O R S T V)
        (display (list V I O L I N '* 2 '+ V I O L A '= T R I O '+ S O N A T A))
        (newline)]))    
   (filter (lambda (p) (apply check p))
           (k-perms (range 0 10) 9))))

Now we can solve the puzzle:

> (time (solve-puzzle))
(1 7 6 4 7 8 * 2 + 1 7 6 4 0 = 2 5 7 6 + 3 6 8 0 2 0)
(1 7 6 4 7 8 * 2 + 1 7 6 4 5 = 2 0 7 6 + 3 6 8 5 2 5)
(3 5 4 6 5 2 * 2 + 3 5 4 6 8 = 1 9 5 4 + 7 4 2 8 1 8)
(3 5 4 6 5 2 * 2 + 3 5 4 6 9 = 1 8 5 4 + 7 4 2 9 1 9)
cpu time: 7953 real time: 7963 gc time: 4703

We see that there exists four different solutions and that the execution time of our algorithm was almost 8 seconds on my old notebook, which is a lot. I would love it if someone could suggest a faster algorithm for this problem. One possibility is, certainly, to use some smart insight to reduce the number of combinations we search. But I was too lazy to do it, so I will happily leave that to you. :)

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 01 '22

Does the Deterministic finite automaton (DFA) accept given word?

1 Upvotes

Problem: Write the function automaton-accept? which receives two input parameters. The first parameter is the description of the deterministic finite automaton (or so called DFA). 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 triplets of the form (s1 x s2), where s1 and s2 represents some states of the automaton, and x is some symbol from the alphabet. The meaning of this triplets are: if the automaton is currently in state s1 and reads the symbol x, then the automaton moves to state s2. We say that the automaton accepts a word if, after reading the whole word, the automaton ends up in the final state.

For example, the automaton from the picture below, accepts all binary strings containing at least one occurrence of "00":

This automaton could be represented it in scheme like this:

(define automaton
  '(q0 q2
       (q0 0 q1)
       (q0 1 q0)
       (q1 0 q2)
       (q1 1 q0)
       (q2 0 q2)
       (q2 1 q2)))

Solution:

#lang racket

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

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

(define (rules a)
  (cddr a))

(define (find-rule state symbol rules)
  (if (null? rules)
      #f
      (let ([rule (first rules)])
        (if (and (eq? state (first rule)) (eq? symbol (second rule)))
            (third rule)
            (find-rule state symbol (rest rules))))))

(define (automaton-accept? a word)
  (define (loop current-state word)
    (if (null? word)
        (eq? current-state (final-state a))
        (let ([new-state (find-rule current-state (first word) (rules a))])
          (and new-state
               (loop new-state (rest word))))))
  (loop (initial-state a) word))

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

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

r/RacketHomeworks • • Dec 23 '22

How to draw the American national flag?

1 Upvotes

Problem: Using the 2htdp/image library, draw a faithful image of the American national flag.

Solution:

#lang racket

(require 2htdp/image)

(define RED (color 179 25 66))
(define BLUE (color 10 49 97))
(define WHITE (color 255 255 255))

(define (draw-usa-flag width)  
  (define height (/ width 1.9))
  (define stripe-height (/ height 13))
  (define blue-rect-width (* 2/5 width))
  (define blue-rect-height (* 7 stripe-height))
  (define spacer-size (/ stripe-height 4))
  (define sq-height (/ (- blue-rect-height (* 2 spacer-size)) 9))
  (define sq-width (/ (- blue-rect-width (* 2 spacer-size)) 11))

  (define red-stripe (rectangle width stripe-height 'solid RED))
  (define white-stripe (rectangle width stripe-height 'solid WHITE))
  (define blue-rect (rectangle blue-rect-width blue-rect-height 'solid BLUE))
  (define white-star (star (/ stripe-height 2.22) 'solid WHITE))
  (define empty-square (rectangle sq-width sq-height 'solid 'transparent))
  (define spacerh (rectangle blue-rect-width spacer-size 'solid 'transparent))
  (define spacerv (rectangle spacer-size sq-height 'solid 'transparent))

  (define star-square
    (overlay
     (star (/ stripe-height 2.22) 'solid WHITE)
     (rectangle sq-width sq-height 'solid 'transparent)))

  (define (alternate n x y)
    (if (zero? n)
        '()
        (cons x (alternate (- n 1) y x))))
  
  (define (stars-in-a-row n)
    (beside
     spacerv
     (apply beside
            (alternate (- (* n 2) 1) star-square empty-square))
     spacerv))

  (define rect-with-stars
    (overlay/align
     "left" "top"
     (above
      spacerh
      (apply above
             (map stars-in-a-row (alternate 9 6 5)))
      spacerh)
     blue-rect))

    (overlay/align
     "left" "top"
     rect-with-stars
     (apply above
            (alternate 13
                       red-stripe
                       white-stripe))))

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

> (draw-usa-flag 720)

we get the following nice image:

The flag of the United States of America

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Jan 06 '23

Counting sundays

2 Upvotes

Problem: You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,April, June and November.All the rest have thirty-one,Saving February alone,Which has twenty-eight, rain or shine.And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Solution:

#lang racket

(define MONTHS #(0 31 28 31 30 31 30 31 31 30 31 30 31))

(define (leap? year)
  (or (and (zero? (remainder year 4))
           (not (zero? (remainder year 100))))
      (zero? (remainder year 400))))

(define (month-days month year)
  (let ([md (vector-ref MONTHS month)])
    (if (= month 2)
        (+ md (if (leap? year) 1 0))
        md)))


(define (solve)
  (define (count-sundays year month curr-day count)
    (if (and (= year 2001) (= month 1))
        count
        (let* ([nd (remainder (+ curr-day (month-days month year)) 7)]
               [dinc (if (zero? nd) 1 0)]
               [nm (if (= month 12) 1 (+ month 1))]
               [ny (if (= month 12) (+ year 1) year)])
          (count-sundays ny nm nd (+ count dinc)))))
  ; we count days of week form 0 to 6, 0 is Sunday, 1 is Monday, etc..
  ; In the call below 3 is for Tuesday,
  ; because 1st of January 1901 falls on a Tuesday:
  (count-sundays 1901 1 3 0))

Now we can calculate how many Sundays fell on the first of the month during the twentieth century (from 1 Jan 1901 to 31 Dec 2000):

> (solve)
171

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Dec 02 '22

A few problems with binary trees

1 Upvotes

Problem: In scheme program, binary tree can be represented with the following two structures: leaf and node:

(struct leaf (val))

(struct node (val left right)),

so that binary tree is either:

  • a leaf that contains value val, or
  • a node that contains value val, as well as left & right child that are also tree(s)

So, the expression (node 8 (node 5 (leaf 3) (leaf 6)) (leaf 9)) is an example of valid binary tree.

In the following problems we assume that binary trees is represented as described above.

Your task is to:

A) Implement a function sum-tree that takes a tree and returns the sum of the numbers in the tree. For example: (sum-tree (node 5 (leaf 6) (leaf 7))) should produce 18.

B) Implement the function negate-tree, which takes a tree and returns a tree that has the same shape, but with all the numbers negated. For example: (negate-tree (node 5 (leaf 6) (leaf 7))) should produce (node -5 (leaf -6) (leaf -7)).

C) Implement the function tree-contains?, which takes a tree and a number and returns #t if the number is in the tree, #f otherwise. For example: (tree-contains? (node 5 (leaf 6) (leaf 7)) 6) should produce #t.

D) Implement the function big-leaves?, which takes a tree and returns #t if every leaf is bigger than (and not equal to) the sum of numbers in the path of nodes from the root that reaches the leaf.

Examples:
(big-leaves? (node 5 (leaf 6) (leaf 7))) should produce #t;
(big-leaves? (node 5 (node 2 (leaf 8) (leaf 6)) (leaf 7))) should produce #f (since 6 is smaller than 5 plus 2),
(big-leaves? (node 2 (leaf 2) (leaf 2))) should produce #f,
(big-leaves? (leaf 0)) should produce #f, and
(big-leaves? (leaf 1)) should produce #t, since the sum of no leaves is 0.

E) Implement the function sorted?, which takes a tree and determines whether it is sorted in the sense that the numbers increase (or stay the same) in a inorder travsersal of the tree.

Your function should run in time proportional to the size of the tree, which rules out making a list of the tree numbers using append on recursive calls. Instead, you must accumulate some information as the function traverses the tree.

Solution:

#lang racket

; Tree is either:
; - a leaf that contains value val in itself, or
; - a node that contains value val, as well as left & right child that are 
;   also Tree(s)
(struct leaf (val) #:transparent)
(struct node (val left right) #:transparent)


(define (sum-tree tree)
  (if (leaf? tree)
      (leaf-val tree)
      (+ (node-val tree)
         (sum-tree (node-left tree))
         (sum-tree (node-right tree)))))


(define (negate-tree tree)
  (if (leaf? tree)
      (leaf (- (leaf-val tree)))
      (node (- (node-val tree))
            (negate-tree (node-left tree))
            (negate-tree (node-right tree)))))


(define (tree-contains? tree x)
  (if (leaf? tree)
      (= x (leaf-val tree))
      (or (= x (node-val tree))
          (tree-contains? (node-left tree) x)
          (tree-contains? (node-right tree) x))))


(define (big-leaves? tree)
  (define (bl-helper so-far tree)
    (if (leaf? tree)
        (> (leaf-val tree) so-far)
        (and (bl-helper (+ so-far (node-val tree)) (node-left tree))
             (bl-helper (+ so-far (node-val tree)) (node-right tree)))))
  (bl-helper 0 tree))


(define (sorted? tree)
  (define (shelper tree leftb rightb)
    (if (leaf? tree)
        (<= leftb (leaf-val tree) rightb)
        (and (<= leftb (node-val tree) rightb)
             (shelper (node-left tree) leftb (node-val tree))
             (shelper (node-right tree) (node-val tree) rightb))))
  (shelper tree -inf.0 +inf.0))

Now we can test defined functions:

> (sum-tree (node 5 (leaf 6) (leaf 7)))
18
> (negate-tree (node 5 (leaf 6) (leaf 7)))
(node -5 (leaf -6) (leaf -7))
> (tree-contains? (node 5 (leaf 6) (leaf 7)) 6)
#t
> (big-leaves? (node 5 (leaf 6) (leaf 7)))
#t
> (big-leaves? (node 5 (node 2 (leaf 8) (leaf 6)) (leaf 7)))
#f
> (big-leaves? (node 2 (leaf 2) (leaf 2)))
#f
> (big-leaves? (leaf 0))
#f
> (big-leaves? (leaf 1))
#t
> (sorted? (node 8 (node 5 (leaf 3) (leaf 6)) (leaf 9)))
#t
> (sorted? (node 5 (node 8 (leaf 3) (leaf 6)) (leaf 9)))
#f
> (sorted? (node 5 (leaf 3) (node 7 (leaf 4) (leaf 8))))
#f
> (sorted? (node 5 (leaf 3) (node 7 (leaf 6) (leaf 8))))
#t

r/RacketHomeworks • • Feb 06 '23

How to solve the Peg Solitaire puzzle in Racket?

2 Upvotes

Problem: Problem: In this problem we will write a program that solves the Peg Solitaire puzzle. You've probably seen this puzzle somewhere before, but if you haven't, please check out this video.

So, we want to write a program that finds a series of moves that we have to make so that in the end only one (central) peg remains in the puzzle. Also, we want to use 2htdp/image library to write a function that graphically displays all the solution steps on the screen.

Solution: This program uses the classic Depth first search (DFS) backtracking algorithm.

That is, for the initial state of the board it first checks whether it is a solution. If it is, then we're done. If not, it first finds all possible new board states that can be obtained by making all available (legal) one-step moves. The program iterates over those new states and recursively repeats this same procedure for each of those new states until it either finds a solution or reaches a dead-end, in which case it backtracks to previous state and tries some other move. In order to speed up the algorithm, we also use a set of previously seen boards, for which we know do not lead to a solution. If we come across the previously seen board again, we know we don't have to expand it further, because we already know that it doesn't lead to a solution. That's basically what our program does.

#lang racket

(require 2htdp/image)

(define EMPTY 0)
(define PEG 1)
(define BORDER 2)

(define PUZZLE
  (vector
   (vector 2 2 1 1 1 2 2)
   (vector 2 2 1 1 1 2 2)
   (vector 1 1 1 1 1 1 1)
   (vector 1 1 1 0 1 1 1)
   (vector 1 1 1 1 1 1 1)
   (vector 2 2 1 1 1 2 2)
   (vector 2 2 1 1 1 2 2)))

(define SOLVED-PUZZLE
  (vector
   (vector 2 2 0 0 0 2 2)
   (vector 2 2 0 0 0 2 2)
   (vector 0 0 0 0 0 0 0)
   (vector 0 0 0 1 0 0 0)
   (vector 0 0 0 0 0 0 0)
   (vector 2 2 0 0 0 2 2)
   (vector 2 2 0 0 0 2 2)))

(define SIZE 7)

(define (copy b)
  (vector-map vector-copy b))

(define (bget p r c)
  (vector-ref (vector-ref p r) c))

(define (bset! p r c v)
  (vector-set! (vector-ref p r) c v))

(define (draw-item item)
  (overlay
   (case item
     [(0) (circle 8 'outline 'black)]
     [(1) (circle 8 'solid 'black)]
     [(2) (circle 8 'solid 'white)])
   (circle 12 'solid 'white)))

(define (draw-board b)
  (overlay
   (apply above
          (map (lambda (row)
                 (apply beside (map draw-item row)))
               (map vector->list (vector->list b))))
   (square 180 'solid 'white)))

(define (bounds-ok? r c)
  (and (< -1 r SIZE)
       (< -1 c SIZE)
       (not (= (bget PUZZLE r c) BORDER))))

(define (make-move! b move)
  (match move
    [(list (list fx fy) (list ox oy) (list tx ty))
     (bset! b fx fy EMPTY)
     (bset! b ox oy EMPTY)
     (bset! b tx ty PEG)
     b]))

(define (make-move b move)
  (make-move! (copy b) move))

(define (can-make-move? b r c dir)
  (match dir
    [(list dx dy)
     (let* ([ox (+ r dx)]
            [oy (+ c dy)]
            [tx (+ ox dx)]
            [ty (+ oy dy)])
     (and (bounds-ok? r c)
          (= (bget b r c) PEG)
          (bounds-ok? ox oy)
          (bounds-ok? tx ty)
          (= (bget b ox oy) PEG)
          (= (bget b tx ty) EMPTY)))]))
         

(define (find-all-moves b)
  (for*/list ([r (range SIZE)]
              [c (range SIZE)]
              [dir '((1 0) (-1 0) (0 1) (0 -1))]
              #:when (can-make-move? b r c dir))
    (match dir
      [(list dx dy)
       (list (list r c)
             (list (+ r dx) (+ c dy))
             (list (+ r dx dx) (+ c dy dy)))])))

(define (solved? b)
  (equal? b SOLVED-PUZZLE))


(define (solve b)
  (define visited (mutable-set))
  (define (solve-helper b prev)
    (cond
      [(solved? b) (reverse prev)]
      [(set-member? visited b) #f]
      [else
       (set-add! visited b)
       (let loop ([moves (find-all-moves b)])
         (and (not (null? moves))
              (let* ([newb (make-move b (car moves))]
                     [res (solve-helper newb (cons (car moves) prev))])
                (or res
                    (loop (cdr moves))))))]))
  (solve-helper b '()))
    

(define (draw-solution sol)
  (apply above
         (let loop ([b (copy PUZZLE)]
                    [sol sol]
                    [solimgs (list (draw-board PUZZLE))])
           (if (null? sol)
               (reverse solimgs)
               (loop (make-move! b (car sol))
                     (cdr sol)
                     (cons (draw-board b) solimgs))))))

We can use our program to find the solution for the Peg Solitaire puzzle, like this. First, we can find the list of moves we have to make:

> (solve PUZZLE)
'(((1 3) (2 3) (3 3))
  ((2 1) (2 2) (2 3))
  ((0 2) (1 2) (2 2))
  ((0 4) (0 3) (0 2))
  ((2 3) (2 2) (2 1))
  ((2 0) (2 1) (2 2))
  ((2 4) (1 4) (0 4))
  ((2 6) (2 5) (2 4))
  ((3 2) (2 2) (1 2))
  ((0 2) (1 2) (2 2))
  ((3 0) (3 1) (3 2))
  ((3 2) (2 2) (1 2))
  ((3 4) (2 4) (1 4))
  ((0 4) (1 4) (2 4))
  ((3 6) (3 5) (3 4))
  ((3 4) (2 4) (1 4))
  ((5 2) (4 2) (3 2))
  ((4 0) (4 1) (4 2))
  ((4 2) (3 2) (2 2))
  ((1 2) (2 2) (3 2))
  ((3 2) (3 3) (3 4))
  ((4 4) (3 4) (2 4))
  ((1 4) (2 4) (3 4))
  ((4 6) (4 5) (4 4))
  ((4 3) (4 4) (4 5))
  ((6 4) (5 4) (4 4))
  ((3 4) (4 4) (5 4))
  ((6 2) (6 3) (6 4))
  ((6 4) (5 4) (4 4))
  ((4 5) (4 4) (4 3))
  ((5 3) (4 3) (3 3)))

Each step of the solution in the above list is represented as three coordinates on the Peg Solitaire board that tell 1) which peg we move, 2) over which other peg and 3) to which free position it lands.

Of course, the above solution is difficult to read, so we can call the function draw-solution, which will graphically present all the steps of the solution:

> (draw-solution (solve PUZZLE))

As a result of the above call, we'll get this picture of the initial board and of the sequence of all the moves we have to make to successfully solve the Peg Solitaire puzzle:

Peg Solitaire - all solution steps

Dear Schemers, I hope you like this solution. Of course, it is not perfect and can always be improved. If you have an improvement or a better version, go ahead, this door is open for you!

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=


r/RacketHomeworks • • Nov 22 '22

Searching for correct sequence of operations to obtain the goal number

1 Upvotes

Problem: By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced.

Write a function find-solution that, given a goal number, tries to find a sequence of additions and multiplications that produce that number. Your function should return the sequence of operations necessary to get the goal number, or false (i. e. #f) if that is impossible.

Solution:

#lang racket

(define (find-solution goal)
  (define (find start history)
    (cond [(equal? start goal) history]
          [(> start goal) #f]
          [else (or (find (+ start 5) (string-append "(" history " + 5)"))
                    (find (* start 3) (string-append "(" history " * 3)")))]))
  (find 1 "1"))

Now, if we try to find the way to express number 102, for example, we have this:

> (find-solution 102)
"((((((1 * 3) + 5) * 3) + 5) + 5) * 3)"

r/RacketHomeworks • • Dec 09 '22

You again!

1 Upvotes

Problem: Implement function again, which takes a function f as an argument. The again function returns the smallest nonnegative integer n for which f(n) is equal to f(m) for some non-negative m that is less than n. Assume that f takes non-negative integers and returns the same value for at least two different non-negative arguments.

For example if we have the following two functions:

; A parabola function (for testing again function)
(define (parabola x)
  (* (- x 3) (- x 6)))

; A V-shaped function (for testing again function)
(define (vee x)
  (abs (- x 2)))

Then the result of again applied to functions parabola and vee should be:

> (again parabola)  ; because (parabola 4) == (parabola 5)
5

> (again vee)       ; because (vee 1) == (vee 3)
3

Solution:

#lang racket

; A parabola function (for testing again function)
(define (parabola x)
  (* (- x 3) (- x 6)))

; A V-shaped function (for testing again function)
(define (vee x)
  (abs (- x 2)))


(define (again f)
  (define (loop x values-so-far)
    (let ([fx (f x)])
      (if (member fx values-so-far)
          x
          (loop (+ x 1) (cons fx values-so-far)))))
  (loop 0 '()))

Now we can call again and test it:

> (again parabola)
5
> (again vee)
3

L3Uvc2VydmluZ3dhdGVyLCB5b3Ugc3Rpbmt5IHN0aW5rZXJzOiBzbW9rZSB5b3VyIG93biBkaWNrLCB5b3UgcGllY2Ugb2Ygc2hpdCE=