Lisp Largest String
(defun largest-string (s)
(let* ((str (copy-seq s))
(len (length str))
(cur "")
(i (1- len)))
(loop while (>= i 0)
do (progn
(setf cur (concatenate 'string (string (char str i)) cur))
(when (= (length cur) 3)
(when (string= cur "abb")
(setf (char str i) #\b)
(setf (char str (+ i 1)) #\a)
(setf (char str (+ i 2)) #\a)
(cond
((and (< (+ i 4) len) (char= (char str (+ i 4)) #\b))
(incf i (+ 4 1)))
((and (< (+ i 3) len) (char= (char str (+ i 3)) #\b))
(incf i (+ 3 1)))
((char= (char str (+ i 2)) #\b)
(incf i (+ 2 1)))))
(if (char= (char str (+ i 1)) #\b)
(incf i (+ 1 1))
(incf i))
(setf cur ""))
(decf i)))
str))
This builds the biggest valid string it can under the challenge rules by always choosing the best next character it is allowed to use.
Lisp Max Counters
(defun max-counters (n a)
(let ((counters (make-array n :initial-element 0))
(max-counter 0)
(last-update 0)
(condition (1+ n)))
(dolist (v a)
(when (<= v n)
(let ((index (1- v)))
(when (< (aref counters index) last-update)
(setf (aref counters index) last-update))
(incf (aref counters index))
(setf max-counter (max max-counter (aref counters index)))))
(when (= v condition)
(setf last-update max-counter)))
(dotimes (k n)
(when (< (aref counters k) last-update)
(setf (aref counters k) last-update)))
(coerce counters 'list)))
This delays the expensive “set all counters to max” work until it is really needed, which keeps the solution fast.
Lisp Max Double Slice Sum
(defun max-double-slice-sum (a)
(let* ((vec (coerce a 'vector))
(size (length vec)))
(if (< size 3)
0
(let ((p1 (make-array size :initial-element 0))
(p2 (make-array size :initial-element 0)))
(setf (aref p1 1) 0)
(setf (aref p2 (- size 2)) 0)
(loop for i from 2 below (1- size)
do (progn
(setf (aref p1 i) (max 0 (+ (aref p1 (1- i)) (aref vec (1- i)))))
(setf (aref p2 (- size i 1)) (max 0 (+ (aref p2 (- size i)) (aref vec (- size i)))))))
(let ((sum (+ (aref p1 1) (aref p2 1))))
(loop for i from 1 below (1- size)
do (setf sum (max sum (+ (aref p1 i) (aref p2 i)))))
sum)))))
This keeps the best sum ending on the left and starting on the right, then combines them around each middle position.
Lisp Max Product Of Three
(defun max-product-of-three (a)
(let* ((sorted (sort (copy-list a) #'<))
(vec (coerce sorted 'vector))
(c (length vec)))
(max (* (aref vec (- c 1)) (aref vec (- c 2)) (aref vec (- c 3)))
(* (aref vec 0) (aref vec 1) (aref vec (- c 1))))))
This checks the useful extremes, because the best product can come from either the three largest numbers or two negatives plus one large positive.
Lisp Max Profit
(defun max-profit (a)
(let ((price (first a))
(profit 0))
(dolist (v a)
(setf price (min price v))
(setf profit (max profit (- v price))))
profit))
This tracks the lowest buy price seen so far and updates the best profit as it scans the prices once.
Lisp Max Slice Sum
(defun max-slice-sum (a)
(let ((tmp most-negative-fixnum)
(max most-negative-fixnum))
(dolist (v a)
(setf tmp (max (+ tmp v) v))
(setf max (max max tmp)))
max))
This is a Kadane-style scan: keep the best running sum and the best overall sum while moving once through the array.
Lisp Min Avg Two Slice
(defun min-avg-two-slice (a)
(let* ((vec (coerce a 'vector))
(count (length vec))
(idx 0)
(min (/ (+ (aref vec 0) (aref vec 1)) 2.0)))
(loop for i from 0 below (1- count)
do (let ((cur (/ (+ (aref vec i) (aref vec (1+ i))) 2.0)))
(when (< (+ i 2) count)
(let ((three (/ (+ (aref vec i) (aref vec (1+ i)) (aref vec (+ i 2))) 3.0)))
(setf cur (min cur three))))
(when (< cur min)
(setf min cur)
(setf idx i))))
idx))
This leans on the key trick for this problem: the minimum average slice is always length 2 or 3.
Lisp Min Perimeter Rectangle
(defun min-perimeter-rectangle (n)
(let ((i 1)
(min most-positive-fixnum))
(loop while (< (* i i) n)
do (progn
(when (zerop (mod n i))
(setf min (min min (* 2 (+ i (/ n i))))))
(incf i)))
min))
This searches factor pairs up to the square root and picks the pair with the smallest perimeter.
Lisp Missing Integer
(defun missing-integer (a)
(let ((sorted (sort (remove-duplicates (copy-list a) :test #'=) #'<))
(min 1))
(loop for v in sorted
do (when (> v 0)
(if (/= min v)
(return)
(incf min))))
min))
This records the positive numbers that exist, then returns the smallest positive value that is still missing.
Lisp Nesting
(defun nesting (s)
(if (zerop (length s))
1
(let ((stack '()))
(loop for v across s
do (if (char= v #\))
(if (or (null stack) (char/= (pop stack) #\())
(return-from nesting 0))
(push v stack)))
(if (null stack) 1 0))))
This treats the string like a balance counter: open parentheses add one, closing ones remove one.