-
Notifications
You must be signed in to change notification settings - Fork 3
/
pro14.lisp
45 lines (41 loc) · 992 Bytes
/
pro14.lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
(defun collatz-length (n)
(labels ((rec (m times)
(if (= 1 m)
times
(if (evenp m)
(rec (/ m 2) (1+ times))
(rec (1+ (* 3 m)) (1+ times))))))
(rec n 1)))
(defun pro14 (n)
(let ((max nil)
(win 0))
(loop
:for i from 2 upto n
:do (let ((len (collatz-length i)))
(if (> len win)
(setf max i
win len))))
(values max win)))
;;; The version used the hash table
(defparameter *collatz*
(make-hash-table :test #'eql))
(setf (gethash 1 *collatz*) 1)
(defun collatz-length/hash (n)
(multiple-value-bind (value found)
(gethash n *collatz*)
(if found
value
(let ((m (if (evenp n) (/ n 2) (1+ (* 3 n)))))
(let ((v (collatz-length/hash m)))
(setf (gethash m *collatz*) v)
(1+ v))))))
(defun pro14/hash (n)
(let ((max nil)
(win 0))
(loop
:for i from 2 upto n
:do (let ((len (collatz-length/hash i)))
(if (> len win)
(setf max i
win len))))
(values max win)))