Order a list as per list using scheme

The below program takes in a list of arguments and orders them as per the second list.

(define (nth lst1 lst2 n)
(if (= n (car lst2)) (car lst1) (nth (cdr lst1) (cdr lst2) n)))

(define (order lst1 lst2)
(define (order-help n)
(if (> n (length lst1)) '() (cons (nth lst1 lst2 n) (order-help (+ n 1)))))
(order-help 1))

(order '(a b c d e) '(1 2 3 4 5))
; Value 1: (a b c d e)
(order '(a b c d e) '(4 1 2 3 5))
; Value 2: (b c d a e)
(order '(a b c d e) '(5 4 3 2 1))
; Value 3: (e d c b a)
(order '(a b c d e) '(1 5 2 4 3))
; Value 4: (a c e d b)

My maximum and minimum procedure in scheme

Scheme comes with two built-in procedures to get the maximum and minimum of a given set of numbers. The documentation explains the procedures as below:


(max x ...+) → real?
x : real?
Returns the largest of the xs, or +nan.0 if any x is +nan.0. If any x is inexact, the result is coerced to inexact.

Examples:
> (max 1 3 2)

3
> (max 1 3 2.0)

3.0
(min x ...+) → real?
x : real?
Returns the smallest of the xs, or +nan.0 if any x is +nan.0. If any x is inexact, the result is coerced to inexact.

Examples:
> (min 1 3 2)

1
> (min 1 3 2.0)

1.0

My own implementations of max and min also work in the same way, including that fact that (max 1) will return 1 instead of an error that only one number is given. The code for max and min are the same except for the signs.

(define (mymin x . lst)
(define (myleast lst6 last)
(if (null? (cdr (if (pair? lst6) lst6 (list lst6)))) last
(if (<> last (car(cdr lst6))) (myleast (cdr lst6) last) (myleast (cdr lst6) (car (cdr lst6))))))
(myleast lst x))

(mymax 2 3 4 5 6 1)

These procedure demonstrate the simple concept of sending 1 or more arguments to a scheme procedure. The arguments come into the procedure in the form of a list. The operator "." does the trick.

Scheme program for accumulate - n

The following are two implementations of accumulate - n one that uses map and another that does not. However, both use accumulate procedure.

(define (accumulate op init lst)
(if (null? lst)
init
(op (car lst)
(accumulate op init
(cdr lst)))))

Implementation 1:

(define (accumulate-n op init seqs)
(if (null? (car seqs))
'()
(cons (accumulate op init (car seqs))
(accumulate-n op init (if (pair? (cdr seqs)) (cdr seqs) (list(cdr seqs)))))))

(accumulate-n + 0 (list (list 1) (list 4 5 6)))

Implementation 2:

(define (accumulate-n op init lst)
(define (accumulate-help lst)
(accumulate op init lst))
(map accumulate-help lst))


(accumulate-n + 0 (list (list 1 2 3) (list 4 5 6) (list 7 8 9)))

3 Missionaries and 3 cannibals - crossing the river

3 missionaries (or sheep or carrots) and 3 cannibals (or wolves or rabbits) stand on a riverbank. On
the same riverbank a boat, that can maximally take 2 persons (minimally 1), lies. The 6 people are
facing a problem: how to optimally transport (minimal number of moves) ourselves from
the current riverbank (the left one) to the opposite bank of the river (the right one) in a way
that guarantees that at any time the number of cannibals never outnumber the number of
missionaries (they will then be eaten)?

The missionaries and cannibal problem is a popular problem used in Artificial intelligence to understand and experiment with search methods. Here is a list of the possible optimal solutions for the various cases

1 cannibal and 1 missionary

Step1:(left 1 1 0 0)
Step2:(right 0 0 1 1)

2 cannibals and 2 missionaries

Solution1:
((left 2 2 0 0) (right 2 0 0 2) (left 2 1 0 1) (right 0 1 2 1) (left 1 1 1 1) (right 0 0 2 2))

Solution2:
((left 2 2 0 0) (right 1 1 1 1) (left 2 1 0 1) (right 0 1 2 1) (left 0 2 2 0) (right 0 0 2 2))

3 cannibals and 3 missionaries

Solution1:
((left 3 3 0 0)
(right 3 1 0 2)
(left 3 2 0 1)
(right 3 0 0 3)
(left 3 1 0 2)
(right 1 1 2 2)
(left 2 2 1 1)
(right 0 2 3 1)
(left 0 3 3 0)
(right 0 1 3 2)
(left 1 1 2 2)
(right 0 0 3 3))

Solution2:

((left 3 3 0 0)
(right 2 2 1 1)
(left 3 2 0 1)
(right 3 0 0 3)
(left 3 1 0 2)
(right 1 1 2 2)
(left 2 2 1 1)
(right 0 2 3 1)
(left 0 3 3 0)
(right 0 1 3 2)
(left 0 2 3 1)
(right 0 0 3 3))

2 cannibals and 3 missionaries

Solution1:

((left 3 2 0 0)
(right 2 1 1 1)
(left 2 2 1 0)
(right 1 1 2 1)
(left 2 1 1 1)
(right 1 0 2 2)
(left 1 1 2 1)
(right 0 0 3 2))

Solution2:

((left 3 2 0 0)
(right 3 0 0 2)
(left 3 1 0 1)
(right 1 1 2 1)
(left 2 1 1 1)
(right 0 1 3 1)
(left 1 1 2 1)
(right 0 0 3 2))

1 cannibal and 2 missionaries

Solution1:

((left 2 1 0 0) (right 0 1 2 0) (left 1 1 1 0) (right 0 0 2 1))

Solution2:

((left 2 1 0 0) (right 0 1 2 0) (left 1 1 1 0) (right 1 0 1 1) (left 2 0 0 1) (right 0 0 2 1))

0 cannibal and 1 missionaries

((left 1 0 0 0) (right 0 0 1 0))

Solutions are not possible for numbers greater than 3 or cases in which cannibals outnumber missionaries.

Prime number or not program - scheme

There are many different procedures for testing primality of numbers. One way to

test if a number is a prime is to find the number's divisors. If a number n is prime then

n equals the smallest integral divisor of n.

Below procedure tests if a number is a prime based on the above method.

(define (is-prime-help n count) (if (= count 1) #t (if(= (modulo n count) 0) #f (is-prime-help n (- count 1)))))

(define (is-prime n) (if(<>

Another method is related to Fermat’s little theorem:

If n is a prime number and a is any positive integer less than n, then a raised to the

nth power is congruent to a modulo n.

Two numbers are said to be congruent modulo n if they both have the same remainder

when divided by n. Trying a random number a <>, one can be sure that n is not prime

if the remainder of an modulo n is not equal to a. However, the opposite does not

always hold, i.e. a number n is not always prime if the remainder of an modulo n is

equal to a. By trying more and more random a <>, one can get more confident that n

is prime. This algorithm is known as the Fermat test.

Below implements a Fermat test procedure.

(define a 0)

(define (ftp n k) (cond((= k 0) #t) ((= n 2) #t) ((<>

Fermats test is not always accurate as fermat liers can complicate the situation. Modified versions of Fermats test however provide more accurate results.

How many pins?

In bowling one often uses ten pins positioned on four rows. How many pins are needed for five rows, six rows, or n rows (where n is a positive integer)?

The below procedure calculates the number of pins needed for n rows recurssively.

(define (number-of-pins-rec n)(if(= n 1) n (+ n (number-of-pins-rec(- n 1)))))

> (number-of-pins-rec 2)

3

> (number-of-pins-rec 4)

10

> (number-of-pins-rec 5)

15

> (number-of-pins-rec 6)

21

The procedure in a iterative process.

(define (number-of-pins-it-help n sum count)

(if (> count n)

sum

(number-of-pins-it-help n

(+ sum count)

(+ count 1))))

(define (number-of-pins-it n)

(number-of-pins-it-help n 0 1))

> (number-of-pins-it 3)

6

> (number-of-pins-it 4)

10

> (number-of-pins-it 5)

15

> (number-of-pins-it 6)

21

> (number-of-pins-it 7)

28