Challenge 205.1 in Racket

1 files changed, 46 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))