Simple Implementation of Hash Table in OCaml

(* In this script, we will implement a simple hash table.                       
 * In our implementation, the keys are strings and the table has                
 * polymorphic values.                                                          
 *                                                                              
 * Part of the implementation can be found in the book Introduction to Objective Caml by Jason Hickey. P92      
 *)                                                                             
                                                                                
                                                                                
(* create an array of random numbers *)                                       
                                                                                
let random_numbers = Array.init 37 (fun x -> Random.int 100 + 1) ;;                                                                                       
let random_length = Array.length random_numbers ;;                              
          
type hash_info =                                                                
  { mutable hash_index : int;                                                   
    mutable hash_value : int;                                                   
  };;                                                                           
                                                                                
let hash_char info c =                                                          
  let i = Char.code c in                                                      
  let index = (info.hash_index + i + 1) mod random_length in                    
  info.hash_value <- (info.hash_value * 3 ) lxor random_numbers.(index);        
  info.hash_index <- index                                                      
;;                                                                              
                                                                                
                                                                                
let hash s =  (* compute the hash of a string *)                                
  let info = { hash_index = 0; hash_value = 0 } in                              
  for i = 0 to String.length s - 1 do                                           
    hash_char info s.[i]                                                        
  done;                                                                         
  info.hash_value                                                               
;;                       


type 'a hash_entry = { key : string; value : 'a };;                             
type 'a hash_table = 'a hash_entry list array ;;                                
                                                                                
let create () =                                                                 
  Array.make 101 [] ;;                                                        
                                                     
(* add functino adds {key ;value} to the hash table. however
 * it does not check if the key has already existed. One of the
 * consequences is we may have multiple values corresponding to
 * the same key 
 *)

             
let add table key value =                                                       
  let index = (hash key) mod (Array.length table) in                            
  table.(index) <- {key = key; value = value} :: table.(index) ;;   


(* find function will find the corresponding value of the given key.
 * In case of multiple values, it returns the first one when it 
 * walks through the chain. If the key does not exist, it raises
 * Not_found
 *)


let find table key =                                                            
  let index = (hash key) mod (Array.length table) in                            
  find_entry key table.(index) ;; 
                                              
let rec find_entry (key :string) = function                                     
    {key = key' ; value = value } ::_ when key' = key -> value                  
  | _ :: entries -> find_entry key entries                                      
  | [] -> raise Not_found 
;;

   

(* delete function will remove the key from the hash table. In the case that
 * there are multiple values corresponding to the same key, the function removes
 * the first value when it walks through the chain. 
 *)

let delete table key  =                                                    
  let index = (hash key) mod (Array.length table) in                            
  let entries = table.(index) in                                                
  let rec del part = function                                                   
    | [] -> ([], false)                                                         
    | ({key = key'; value = value} as hd) :: tl ->                                
        if key = key' then                                                      
          (List.rev part @ tl, true)                                         
        else                                                                    
          del (hd::part) tl                                                     
  in                                                                            
    let (res_lst, flag) = del [] entries in                                     
    match flag with                                                             
    | false -> print_string "key does not exist. No change occurs"                                
    | true -> table.(index) <- res_lst                                     
;;        

(* replace function will update the value of a given key. In the case that
 * there are multiple values corresponding to the same key, the function updates
 * the first value when it walks through the chain. If the key does not exist
 * the function will raise Not_found.
 *)

let replace table key value = 
 let index = (hash key) mod (Array.length table) in
 let entries = table.(index) in
 let rec rep part = function 
  | [] -> ([], false)
  | {key = key'} as hd :: tl ->
    if key = key' then
      let new_entry = {key;value} in
        (List.rev (new_entry::part) @ tl, true)
    else
      rep (hd::part) tl
 in
  let (res_lst, flag) = rep [] entries in
  match flag with 
  | false -> raise Not_found
  | true -> table.(index) <- res_lst
;;




                            

List directories in Bash

Here we present tree methods to list directories in Bash

List sub-directories in the current directory

ls -d */

List all the sub-directories in the current directory

ls -Rl | grep "^d"

List all the sub-directories including hidden directories in the current directory

find ./ -type d 

Generate Permutation in Ocaml

let insert_all n lst =
 let rec insert_all_rec result part = function 
  | []  -> (List.rev (n::part))::result 
  | (h::t) as lst -> 
     let new_lst =  (List.rev (n::part)) @ lst in
     insert_all_rec (new_lst :: result) (h::part) t 
 in 
   insert_all_rec [] [] lst ;;

val insert_all : 'a -> 'a list -> 'a list list = <fun>

let rec generate_permutation n =
 match n with
 | 0 -> []
 | 1 -> [[1]]
 | n -> let list_perm = generate_permutation (n-1) in
      let list_list_perm = List.map (insert_all n) list_perm in
       List.flatten list_list_perm ;;

val generate_permutation : int -> int list list = <fun>


generate_permutation 1 ;;
generate_permutation 2 ;;
generate_permutation 3 ;;
generate_permutation 4 ;;

Simple Implementation of Binary Search Tree in Ocaml

type 'a tree = 
 | Node of 'a * 'a tree * 'a tree
 | Leaf;;

let empty = Leaf ;;

let rec mem x = function
 | Leaf -> false
 | Node (key, left, right) ->
  key = x || (x < key && mem x left) || (x > key && mem x right) ;;


(* insert function will ignore the key which has already existed *)
let rec insert x = function
 | Leaf -> Node (x, Leaf, Leaf)
 | Node (k, left, right) as node-> 
    if x < k then
    Node (k, insert x left, right)
   else if x > k then
    Node (k, left, insert x right)
   else
    node ;;


let rec tree_of_list = function
 | [] -> empty
 | h::t -> insert h (tree_of_list t) ;;


let rec insert x = function
 | Leaf -> Node (x, Leaf, Leaf)
 | Node (k, left, right) as node-> 
    if x < k then
    Node (k, insert x left, right)
   else if x > k then
    Node (k, left, insert x right)
   else
    node ;;


let my_tree = tree_of_list [2;3;4;1;7;6;4;8] ;;

let rec in_order_walk = function
 | Leaf -> ()
 | Node (k,left,right) ->
  in_order_walk left;
  let () = print_int k in
    print_newline ();
  in_order_walk right;;

let rec pre_order_walk = function
 | Leaf -> ()
 | Node (k, left, right) ->
  let () = print_int k in
   print_newline ();
  pre_order_walk left;
  pre_order_walk right ;;

let rec post_order_walk = function
 | Leaf -> ()
 | Node (k, left, right) ->
  post_order_walk left;
  post_order_walk right;
  let () = print_int k in
   print_newline () ;;
  
let rec height = function
 | Leaf -> 0
 | Node (k, left, right) ->
   1 + max (height left) (height right) ;;





  

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~%")))))

          
          

          
         
             

Hackerrank: Stone Piles

Problem Statement

Stone Piles

 https://www.hackerrank.com/challenges/stone-piles
 
There are N piles of stones where the ith pile has xi stones in it. Alice and Bob play the following game:

1. Alice starts, and they alternate turns.
2. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the newly created piles have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5). 
3. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Given the starting set of piles, who wins the game assuming both players play optimally?

Input:
The first line contains the number of test cases T. T test cases follow. The first line for each test case contains N, the number of piles initially. The next line contains N space delimited numbers, the number of stones in each of the piles.

Output:
Output T lines, one corresponding to each test case containing "ALICE" if Alice wins the game and "BOB" otherwise.

Constraints:
1 ≤ T ≤ 50
1 ≤ N ≤ 50
1 ≤ x_i ≤ 50
Sample Input

4  
1  
4  
2  
1 2  
3  
1 3 4  
1  
8

Sample Output

BOB  
BOB  
ALICE  
BOB

Explanation
For the first case, the only possible move for Alice is (4) -> (1,3). Now Bob breaks up the pile with 3 stones into (1,2). At this point Alice cannot make any move and has lost.

Solution:
To solve this problem we need some basic knowledge in game theory. There is a well-written tutorial about impartial games online. (http://web.mit.edu/sp.268/www/nim.pdf)

Now back to our problem. The basic idea is to compute the Sprague-Grundy function. We can apply the same argument about the Nim game mentioned in the tutorial, meaning if we have SG function eaqual to zero in the current step, we will get a non-zero value in the next step and if we have a non-zero value at current step, we can always construct a strategy  that brings the value to zero again.

Given the initial array, we can compute the SG value, if it is zero then print "BOB", otherwise print "ALICE".

Code:

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <vector>
#include <climits>
#include <list>
#include <unordered_map>
#include <algorithm>

using namespace std;


typedef vector< vector<bool> > myVector;


void compute_sg_fun(int prev, int start, int rest, int key, vector<int>& sg_fun, myVector& record) {

 for (int i = start; i <= rest / 2; i++) {
  if (rest-i > i) {
   int res = prev ^ sg_fun[i] ^ sg_fun[rest-i];
   record[key][res] = true;
   compute_sg_fun(prev ^ sg_fun[i], i+1, rest - i,key, sg_fun, record);
  }
 }

 int k = 0;

 while (record[key][k]) ++k;

 sg_fun[key] = k;
}






int main(void)


{

 myVector record(51, vector<bool>(51,false));
 vector<int> sg_fun(51,-1);
 sg_fun[0] = 0;
 sg_fun[1] = 0;
 sg_fun[2] = 0;
 sg_fun[3] = 1;


 for (int i = 4; i <= 50; i++) compute_sg_fun(0,1,i,i,sg_fun,record);
 
 int t; cin >> t;

 for (int i = 0; i < t; i++) {
  int n;
  cin >> n;

  int res = 0;

  for (int j = 0; j < n; j++) {
   int c; cin >> c;
   res = res ^ sg_fun[c];
  }

  printf("%s\n", res == 0 ? "BOB" : "ALICE");

 }

 return 0;

}

Common Lisp Books

Common Lisp Books

It is really fun to learn Common Lisp. Though it may take time to learn the nuance of different concepts in Common Lisp, it is actually not that hard to learn. Once we become familiar with the basic concepts of the language, we can start to write our own program very quickly.

It turns out that we can really get satisfaction when we write Common Lisp program. Part of the reason is the name of functions in Common Lisp. For instance, there is a really useful function called “describe”, when I enter the word describe I have the feeling that I am talking with the machine.

There are some well-written books, I would recommend the following three books. They are not hard to read and I think they cover most of the aspects in the language.



Practical Common Lisp, by Peter Seibel
http://www.gigamonkeys.com/book/


Common Lisp: A gentle introduction to Symbolic Computation, by David S. Touretzky
https://www.cs.cmu.edu/~dst/LispBook/book.pdf

Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, by Peter Norvig

http://www.amazon.com/Paradigms-Artificial-Intelligence-Programming-Studies-ebook/dp/B003VWBY1I

Hey, Jack

"Hey, Jack, HUNGRYP?"
"T, I'm startved!"

good one:)

Lisp的括号

之前一直觉得lisp的括号确实多的有点让人难以置信。想到以前看到的一个笑话，说是有人去偷别人写的代码但是只拿到了最后几页，回去一看只有括号。 原先觉得这个笑话不是那么的好笑，现在想想觉得还有有点意思。


写for loop 的时候心里也有些微词，觉得格式有些复杂，不够简洁。但是今天开始写C++的时候发现虽然C++的 for loop 看上去简洁，但是真正打起来还是有点费时间，主要是因为手要来回移动，消耗不少时间。虽然不知道为什么，但是现在隐约觉得似乎lisp的程序写起来要稍稍快一些。 不知道是不是一种错觉。

我觉得应该设计一种键盘，专门为编程优化才对。