Hackerrank: Permutation game

Permutation game
https://www.hackerrank.com/challenges/permutation-game

Problem Statement
Alice and Bob play the following game:

1. They choose a permutation of the first N numbers to begin with.
2. They play alternately and Alice plays first.
3. In a turn, they can remove any one remaining number from the permutation.
4. The game ends when the remaining numbers form an increasing sequence. The person who played the last turn (after which the sequence becomes increasing) wins the game.

Assuming both play optimally, who wins the game? 

Input: 
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by a permutation of the integers 1..N on the second line.

Output: 
Output T lines, one for each test case, containing "Alice" if Alice wins the game and "Bob" otherwise.

Constraints: 
1 <= T <= 100 
2 <= N <= 15 
The permutation will not be an increasing sequence initially.

Sample Input:

2
3
1 3 2
5
5 3 2 1 4

Sample Output:

Alice
Bob

Explanation: 
For the first example, Alice can remove the 3 or the 2 to make the sequence increasing and wins the game. 

For the second example, if 4 is removed then the only way to have an increasing sequence is to only have 1 number left, which would take a total of 4 moves, thus allowing Bob to win. On the first move if Alice removes the 4, it will take 3 more moves to create an increasing sequence thus Bob wins. If Alice does not remove the 4, then Bob can remove it on his next turn since Alice can not win in one move.

Solution: To solve this problem, we will use recursion and memorization. Given a list we will determine if the player starts from that position can win the game. In my algorithm, I tested all the possibilities. For example, let say Alice starts from (5 3 2 1 4), the algorithm will test all available choices, therefore we will test if (3 2 1 4) (5 2 1 4) (5 3 2 4) (5 3 2 1) are winnable positions.

Notice that (5 2 1 4) is equivalent to (4 2 1 3) = (5-1 2 1 4-1) and it is here that the recursion comes in.

Code:

(defvar num-case)       ;; denotes the number of test case in the online judgement

(defvar tab)            ;; we will use a hash table to store all the results that have been calculated
                        ;; we expect that during the recursion we will meet the same configuration many times
                        ;; hence, use a hash table to memorize results can accelerate the algorithm


(setq tab (make-hash-table :test 'equal)) ;; we use 'equal test, because we want to compare the contents of two list



(defun test-lst (lst)
  "this function test if the lst reaches a terminal condition"
  (if (= 1 (length lst))      
    t                             ;; if the list has only one element, then this is a terminal condition 
    (let ((ref (first lst))       ;; otherwier, we will check if the list is in a increasing order
          (terminated t))
      (dolist (it (rest lst))
        (if (< it ref)
          (setq terminated nil))
        (setq ref it))
      terminated)))
        

 (defun is-win-position(lst) 
   (if (gethash lst tab)          
     (gethash lst tab)                       ;;; if we have already calculated the result
     (let ((test-res (test-lst lst)))        ;;; otherwise, test every possibility
       (if test-res
         (setf (gethash lst tab) nil)
      (let ((this-is-a-win-position nil))
       (dolist (element lst)
         (let ((new-lst ()))
           (dolist (x lst)                   ;;; here we will create a new list and it is here that 
             (cond                           ;;; the recursion involves
               ((< x element) (push x new-lst))
               ((> x element) (push (1- x) new-lst))
               (t ())))
                  (setf new-lst (reverse new-lst))
               (let ((tmp-result (is-win-position new-lst)))
                 (if (null tmp-result)
                   (progn
                     (setf this-is-a-win-position t)
                     (return))))))
        (setf (gethash lst tab) this-is-a-win-position))))))


 (setq tab (make-hash-table :test 'equal))         
          


;;; main part

(setq num-case (read))

(dotimes (i num-case)
  (let ((n (read))
        (my-lst ()))
    (dotimes (j n)
      (push (read) my-lst))
    (setq my-lst (reverse my-lst))
    (let ((res (is-win-position my-lst)))
      (if res
        (format t "Alice~%")
        (format t "Bob~%")))))