Website:
Paste Title:
Colors
Sizes
1
2
3
4
5
6
7
(defun shiritori (num-words) (loop with ht = (make-hash-table :size num-words :test 'equal) repeat (1- num-words) for player = 1 then (- 1 player) for prev-word = (read-line) then curr-word for curr-word = (read-line) then (read-line) do (setf (gethash prev-word ht) t) (when (or (char/= (char curr-word 0) (char prev-word (1- (length prev-word)))) (gethash curr-word ht)) (return player)))) (defun main () (case (shiritori (read)) (0 (format t "Player 1 lost")) (1 (format t "Player 2 lost")) (otherwise (format t "Fair Game")))) (main) #| UPDATE: I generated a torture test data-set to profile the code. Just 100,000 random "words" of length 120 (the problem's declared input constraints)such that the first letter of i-th word equals the last letter of the (i-1)-th word (i.e. a "Fair Game"). The culprit is READ-LINE. GET-HASH and PUT-HASH just wrap (GETHASH CURR-WORD HT) and (SETF (GETHASH PREV-WORD HT) T), respectively. seconds | gc | consed | calls | sec/call | name ; ----------------------------------------------------------- ; 1.421 | 0.034 | 102,398,912 | 100,000 | 0.000014 | READ-LINE ; 0.076 | 0.000 | 0 | 99,999 | 0.000001 | PUT-HASH ; 0.071 | 0.000 | 0 | 99,999 | 0.000001 | GET-HASH ; ----------------------------------------------------------- ; 1.567 | 0.034 | 102,398,912 | 299,998 | | Total ; BACKGROUND ========== See: <https://open.kattis.com/problems/shiritori>, click on statistics. Common Lisp (SBCL) has the slowest solution (namely, mine, the one shown above.) The equivalent C++ sol'n, for example, literally translated from Lisp to C++ using unordered_map instead of make-hash-table, takes 0.06s. |#
Password to view?
Enable code highlighting?
No
Yes
