Lisp Dominator
(defun dominator (a)
(let ((vec (coerce a 'vector))
(size 0) (value 0) (index 0))
(loop for k from 0 below (length vec)
for v = (aref vec k)
do (cond
((zerop size) (incf size) (setf value v) (setf index k))
((/= value v) (decf size))
(t (incf size))))
(let ((candidate (if (> size 0) value -1))
(count 0))
(loop for v across vec do (when (= v candidate) (incf count)))
(when (<= count (/ (length vec) 2))
(setf index -1))
index)))
This finds a value that appears in more than half of the array, then returns one valid index for it.
Lisp Equi Leader
(defun equi-leader (a)
(let ((vec (coerce a 'vector))
(leader-size 0) (value 0))
(loop for v across vec
do (cond
((zerop leader-size) (incf leader-size) (setf value v))
((/= value v) (decf leader-size))
(t (incf leader-size))))
(let* ((candidate (if (> leader-size 0) value -1))
(leader-count 0))
(loop for v across vec do (when (= v candidate) (incf leader-count)))
(let ((leader (if (> leader-count (/ (length vec) 2)) candidate -1))
(count (length vec))
(l-leader-count 0)
(equi-leaders 0))
(loop for k from 0 below count
for v = (aref vec k)
do (let ((left-half (floor (1+ k) 2))
(right-half (floor (- count k 1) 2)))
(when (= v leader) (incf l-leader-count))
(let ((r-leader-count (- leader-count l-leader-count)))
(when (and (> l-leader-count left-half)
(> r-leader-count right-half))
(incf equi-leaders)))))
equi-leaders))))
This keeps leader counts on both sides of the split and counts positions where the same leader survives in each half.
Lisp Fib Frog
(defun fib-frog (a)
(let* ((vec (coerce a 'vector))
(size (length vec))
(fib (make-array 2 :initial-contents '(0 1) :adjustable t :fill-pointer 2)))
(let ((i 1))
(loop while (<= (aref fib i) size)
do (progn
(incf i)
(vector-push-extend (+ (aref fib (1- i)) (aref fib (- i 2))) fib))))
(let ((paths (list (list :idx -1 :jmp 0)))
(steps (make-array size :initial-element nil)))
(loop while paths
do (let ((path (pop paths)))
(loop for i from (1- (length fib)) downto 2
do (let ((idx (+ (getf path :idx) (aref fib i))))
(cond
((= idx size) (return-from fib-frog (1+ (getf path :jmp))))
((or (> idx size)
(aref steps idx)
(zerop (aref vec idx)))
nil)
((= (aref vec idx) 1)
(setf (aref steps idx) t)
(setf paths (append paths (list (list :idx idx :jmp (1+ (getf path :jmp))))))))))))
-1)))
This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.
Lisp Fish
(defun fish (a b)
(let* ((veca (coerce a 'vector))
(vecb (coerce b 'vector))
(size (length veca))
(dead 0)
(stack '()))
(dotimes (i size)
(if (= (aref vecb i) 1)
(push (aref veca i) stack)
(when stack
(loop while stack
do (progn
(incf dead)
(if (> (aref veca i) (first stack))
(pop stack)
(return)))))))
(- size dead)))
This uses a stack for downstream fish and resolves fights only when opposite directions meet.
Lisp Flags
(defun flags (a)
(let* ((vec (coerce a 'vector))
(size (length vec))
(peaks (make-array size :initial-element nil))
(next (make-array size :initial-element -1)))
(loop for i from 1 below size
do (setf (aref peaks i)
(and (< (aref vec (1- i)) (aref vec i))
(> (aref vec i) (if (< (1+ i) size) (aref vec (1+ i)) 0)))))
(setf (aref next (1- size)) -1)
(loop for i from (- size 2) downto 0
do (setf (aref next i) (if (aref peaks i) i (aref next (1+ i)))))
(let ((i 1) (result 0))
(loop while (<= (* i (1- i)) size)
do (let ((pos 0) (num 0))
(loop while (and (< pos size) (< num i))
do (progn
(setf pos (aref next pos))
(when (= pos -1) (return))
(incf num)
(incf pos i)))
(incf i)
(setf result (max result num))))
result)))
This finds all peaks first, then checks how many flags can be placed while keeping the required distance.
Lisp Frog Jmp
(defun frog-jmp (x y d)
(ceiling (- y x) d))
This computes the jump count with math instead of simulation, which is the cleanest way to solve it.
Lisp Frog River One
(defun frog-river-one (x a)
(let ((existing (make-hash-table)))
(loop for k from 0
for i in a
do (when (and (not (gethash i existing)) (<= i x))
(setf (gethash i existing) i)
(when (= (hash-table-count existing) x)
(return-from frog-river-one k))))
-1))
This tracks the earliest time each needed position appears and stops as soon as the frog can cross.
Lisp Genomic Range Query
(defun genomic-range-query (s p q)
(loop for pi in p
for qi in q
collect (let ((sub (subseq s pi (1+ qi))))
(cond
((find #\A sub) 1)
((find #\C sub) 2)
((find #\G sub) 3)
(t 4)))))
This builds prefix counts for each DNA letter so every query can return the minimum impact factor quickly.
Lisp Is Ipv 4 Adress
(defun split-on-char (s ch)
(loop with start = 0
for pos = (position ch s :start start)
collect (subseq s start pos)
while pos
do (setf start (1+ pos))))
(defun is-ipv4-address (input-string)
(let ((parts (split-on-char input-string #\.)))
(and (= (length parts) 4)
(every (lambda (v)
(and (> (length v) 0)
(every #'digit-char-p v)
(<= (parse-integer v) 255)
(string= v (write-to-string (parse-integer v)))))
parts))))
This splits the string by dots and validates each part as a normal IPv4 octet.
Lisp Ladder
(defun ladder (a b)
(let* ((veca (coerce a 'vector))
(vecb (coerce b 'vector))
(size (length veca))
(modulus (1- (ash 1 (reduce #'max vecb))))
(limit (reduce #'max veca))
(fib (make-array (+ limit 2) :initial-element 0)))
(setf (aref fib 1) 1)
(loop for i from 2 below (+ limit 2)
do (setf (aref fib i) (logand (+ (aref fib (1- i)) (aref fib (- i 2))) modulus)))
(loop for i from 0 below size
collect (logand (aref fib (1+ (aref veca i))) (1- (ash 1 (aref vecb i)))))))
This precomputes climb counts once and applies the modulo per query, which avoids recalculating the same paths over and over.