Merge pull request #7626 from shawnw/challenge-205-solutions

Challenge 205 solutions

2 files changed, 67 insertions, 0 deletions

diff --git a/challenge-205/shawn-wagner/racket/ch-1.rkt b/challenge-205/shawn-wagner/racket/ch-1.rkt
new file mode 100644
index 0000000000..8cd2fcba41
--- /dev/null
+++ b/challenge-205/shawn-wagner/racket/ch-1.rkt
@@ -0,0 +1,46 @@
+#lang racket/base
+
+(require srfi/43) ; For vector-swap!
+
+(define (vector-partition! vec left right pivot-index <?)
+  (define pivot (vector-ref vec pivot-index))
+  (vector-swap! vec pivot-index right)
+  (let loop ([i left]
+             [store-index left])
+    (cond
+      ((< i right)
+       (cond
+         ((<? (vector-ref vec i) pivot)
+          (vector-swap! vec store-index i)
+          (loop (+ i 1) (+ store-index 1)))
+         (else
+          (loop (+ i 1) store-index))))
+      (else
+       (vector-swap! vec right store-index)
+       store-index))))
+
+;;; Basic quickselect
+(define (kth-element! vec k <? [left 0] [right (- (vector-length vec) 1)])
+  (if (= left right)
+      (vector-ref vec left)
+      (let* ([pivot-index (random left (+ right 1))]
+             [pivot-index (vector-partition! vec left right pivot-index <?)])
+        (cond
+          ((= k pivot-index)
+           (vector-ref vec k))
+          ((< k pivot-index)
+           (kth-element! vec k <? left (- pivot-index 1)))
+          (else
+           (kth-element! vec k <? (+ pivot-index 1) right))))))
+
+(define (solution vec)
+  (if (< (vector-length vec) 3)
+      (apply max (vector->list vec))
+      (kth-element! (vector-copy vec) 2 >)))
+
+(define (demo num vec)
+  (printf "Example ~A: Third highest element of ~S -> ~A~%" num vec (solution vec)))
+
+(demo 1 #(5 3 4))
+(demo 2 #(5 6))
+(demo 3 #(5 4 4 3))
diff --git a/challenge-205/shawn-wagner/racket/ch-2.rkt b/challenge-205/shawn-wagner/racket/ch-2.rkt
new file mode 100644
index 0000000000..2d8d88e5b8
--- /dev/null
+++ b/challenge-205/shawn-wagner/racket/ch-2.rkt
@@ -0,0 +1,21 @@
+#lang racket/base
+
+(require racket/list racket/match)
+(define (solution nums)
+  (for/fold ([num1 -1]
+             [num2 -1]
+             [max-xor 0])
+            ([pair (in-combinations nums 2)])
+    (match-let ([(list p1 p2) pair])
+      (let ([xor (bitwise-xor p1 p2)])
+        (if (> xor max-xor)
+            (values p1 p2 xor)
+            (values num1 num2 max-xor))))))
+
+(define (demo n nums)
+  (let-values ([(n1 n2 xor) (solution nums)])
+    (printf "Example ~A: The maximum result of ~A xor ~A = ~A~%" n n1 n2 xor)))
+
+(demo 1 '(1 2 3 4 5 6 7))
+(demo 2 '(2 4 1 3))
+(demo 3 '(10 5 7 12 8))