save point

1 files changed, 75 insertions, 0 deletions

diff --git a/coding-exercises/3/12.rkt b/coding-exercises/3/12.rkt
new file mode 100644
index 0000000..902cc12
--- /dev/null
+++ b/coding-exercises/3/12.rkt
@@ -0,0 +1,75 @@
+#lang racket
+;; 12
+(require compatibility/mlist)
+(define (last-pair x)
+  (if (null? (mcdr x))
+    x
+    (last-pair (mcdr x))))
+(define x (mlist 'a 'b))
+(define y (mlist 'c 'd))
+(define z (mappend x y))
+x
+(define w (mappend! x y))
+x
+
+;; 13
+(define (make-cycle x)
+  (set-mcdr! (last-pair x) x)
+  x)
+(define zp (make-cycle (mlist 'a 'b 'c)))
+zp
+;; last-pair would make an infinite loop
+
+;; 14
+;; The procedure reverses the list. And messes up the list that is bound in the global env
+(define v (mlist 'a 'b 'c 'd))
+(define (mystery x)
+  (define (loop x y)
+    (if (null? x)
+      y
+      (let ((temp (mcdr x)))
+        (set-mcdr! x y)
+        (loop temp x))))
+  (loop x '()))
+(define wp (mystery v))
+v
+wp
+
+;; 15
+;; 16
+;; 17
+(define (make-pair-counter)
+  (define counted (list))
+  (define (count-pairs x)
+    (display counted)
+    (if (or (not (pair? x))
+            (memq x counted))
+      0
+      (begin
+        (set! counted (cons x counted))
+        (+ 1
+           (count-pairs (car x))
+           (count-pairs (cdr x))))))
+  count-pairs)
+((make-pair-counter) (list 'a 'b 'c))
+(define bc (list 'b 'c))
+((make-pair-counter) (cons bc bc))
+((make-pair-counter) (cons bc (cdr bc)))
+(define c (list 'c))
+(define b (cons c c))
+((make-pair-counter) (cons b b))
+
+;; 18/19
+;; This is actually only a valid way to check for cycles if the first pair in the list is also the state of the cycle.
+;; A better way would be to check against all memory addresses in the list by hashing or counting.
+(define (cycle? x)
+  (define (iter v items)
+    (cond ((null? items) false)
+          ((eq? v items) true)
+          (else (iter v (mcdr items)))))
+  (iter x (mcdr x)))
+(cycle? (mlist 'a 'b 'c))
+(cycle? (make-cycle (mlist 'a 'b 'c)))
+;; For 19 you need a famous trick with two pointers
+
+;; 20