2015-04-02

原本以为自己会利用晚上的时间好好看看书，最终还是想找到一个其他的解决方案来消磨时间。突然发现原来自己并没有什么特殊的兴趣爱好，这点着实让我头疼。对电影电视不感兴趣，音乐也仅仅是喜欢，没事就开着网易云音乐随便挑一个歌单就开始听着，当做所有事情的背景音乐。 今天在做饭的时候想着温习一下法语，便打开FranceInfo Direct，没想到这段时间他们那里又在闹罢工，所以节目不能正常播出。只有在整点和半点的时候才播放新闻，其余时间播放音乐。想要看看书，却不知道从何处下手。挑了本网上推荐的关于self-improvement的书，英文版，想着学习学习英语也不错。不知是因为这本书本身写的很无聊还是我英语太差，自己不能完全明白这本书究竟在讲些什么。坚持了一会儿，实在是觉得枯燥。当然我应该还是会把它读完，否则又是半途而废相当的不好。之后挑了本关于谈判的书，这回找的是中文版。阅读英文书籍的速度与阅读中文书籍的速度还是相差了一大截。

两本书都是畅销书。我发现很多畅销书都喜欢例举大量的实例来表达自己的观点，然后在每个章节的末尾有个像模像样的总结。所以，我觉得第一本书很无聊可能真的不是因为我的英语太差。虽然书本身写得很无趣，但是书中的观点倒是挺有意思。尤其是介绍谈判技巧的《优势谈判》，里面列举的一些要点和注意事项让我觉得很是熟悉。我不禁回想起自己和别人的谈判经历，真的是太过天真太过稚嫩，把书中提到的错误一个不剩的都实践了一遍。其实关于compensation就是一场谈判，只是我之前没有意识到这一点，再加上自己并没有太多的选择而且还有一些别的顾虑，所以压根就没有把和HR的对话当做谈判交易来对待。以至于当挂掉HR电话的时候就开始后悔。也是在那个时候我发现最让人难过的事实往往是自己可以做得更好。

还是应了那句老话，书到用时方恨少。自己读书量之少以至于都没有意识到有些知识可以从书本中获取。习惯了在网上搜索，但是相对于网上零散的知识以及网友们的经验，书本更能提供一套相对完整的体系。并不是说一切只是都能从书本里获得，但是至少书本可以给我们带来一些启发。遗憾的是一流的书太多，二流的书更多。往往找到一本好书需要花费一段时间，如果运气不好遇到一本二流的书，很有可能看完全本书只能获得一点点愉悦。所以说，读书是一件奢侈的事情。

如果真的可以完全放松下来，无所事事也未尝不是件好事。有时候也十分享受一个人的独处，感受着时间缓慢的从身边流淌。什么也不做，什么也不想，就这样吧，我们总会去到一个地方。

《从前慢》——木心

记得早先少年时

大家诚诚恳恳

说一句 是一句

　　

清早上火车站

长街黑暗无行人

卖豆浆的小店冒着热气

　　

从前的日色变得慢

车，马，邮件都慢

一生只够爱一个人

　　

从前的锁也好看

钥匙精美有样子

你锁了 人家就懂了

Hackerrank: Xoring Ninja Solution in Ocaml

Problem Statement
https://www.hackerrank.com/challenges/xoring-ninja

Given a list containing N integers, calculate the XOR_SUM of all the non-empty subsets of the list and print the value of sum % (109 + 7).

XOR operation on a list (or a subset of the list) is defined as the XOR of all the elements present in it.
E.g. XOR of list containing elements {A,B,C} = ((A^B)^C), where ^ represents XOR.

E.g. XOR_SUM of list A having three elements {X1, X2, X3} can be given as follows.
All non-empty subsets will be {X1, X2, X3, (X1,X2), (X2,X3), (X1,X3), (X1,X2,X3)}

XOR_SUM(A) = X1 + X2 + X3 + X1^X2 + X2^X3 + X1^X3 + ((X1^X2)^X3)

Input Format

An integer T, denoting the number of testcases. 2T lines follow.
Each testcase contains two lines, first line will contains an integer N followed by second line containing N integers separated by a single space.

Output Format

T lines, ith line containing the output of the ith testcase.

Constraints

1 <= T <= 5
1 <= N <= 105
0 <= A[i] <= 109

let large_number = 1000000007 ;;

let compute n k =
  if k = 0 then
    0
  else
    let result = ref 1 in
    for i = 1 to (n - 1) do
      result := (!result lsl 1) mod large_number
    done;
    !result
;;

let process arr length =
  let max_elem = ref (-1) in
  for i = 0 to (length - 1 ) do
    if (arr.(i) > !max_elem) then
      max_elem := arr.(i)
  done;
  let level = ref 0
  and result = ref 0 in
  while !max_elem > 0 do

    let count = ref 0 in
    for i = 0 to (length - 1) do
      count := !count + (1 land arr.(i));
      arr.(i) <- (arr.(i) lsr 1)
    done;
    (* Printf.printf "max_elem: %d, level: %d, result: %d, count: %d\n" !max_elem !level !result !count; *)
    let res = compute length !count in
    result := (!result + (res lsl !level) ) mod large_number;
    level := !level + 1 ;
    max_elem := !max_elem lsr 1 ;
  done;
  !result
;;


(* main *)

let num_case = read_int () ;;

for i = 1 to num_case do
  let n = read_int () in
  let line = read_line () in
  let lst_string = Str.split (Str.regexp " ") line in
  let lst_int = List.map int_of_string lst_string in
  let arr = Array.of_list lst_int in
  let result = process arr n in
  Printf.printf "%d\n" result
done ;;

Hackerrank: AND Product Solution in Ocaml

AND product

Problem Statement

You will be given two intergers A and B. You are required to compute the bitwise AND amongst all natural numbers lying between A and B, both inclusive.

Input Format

First line of the input contains T, the number of testcases to follow.
Each testcase in a newline contains A and B separated by a single space.

Constraints

1 <= T <= 200
0 <= A <= B <= 2^32

Output Format

Output one line per test case with the required bitwise AND

let read_line_int () =
  let line = read_line () in
  let lst = Str.split (Str.regexp " ") line in
  let lst_int = List.map int_of_string lst in
  let arr = Array.of_list lst_int in
  arr
;;


let number_of_bits n =
  let rec num_of_bits count n =
    match n with
    | 0 -> count
    | n -> num_of_bits (count + 1) (n lsr 1)
  in
    num_of_bits 0 n ;;


let rec process result a b =
  let n_bits_a = number_of_bits a
  and n_bits_b = number_of_bits b in
  match n_bits_a = n_bits_b with
  | false -> result
  | true ->
    let m = 1 lsl (n_bits_a - 1) in
    process (result + m) (a - m) (b - m)
;;

let process_main a b =
  process 0 a b ;;



(* main part *)

let num_case = read_int () ;;

for i = 1 to num_case do
  let arr = read_line_int () in
  let result = process_main arr.(0) arr.(1) in
  Printf.printf "%d\n" result
done;;

Generate Partitions

let rec generate start n =
  if start = 0 then
    match n with
    | 0 -> raise (Invalid_argument "n")
    | 1 -> [[1]]
    | k -> let result = generate 1 k in [k]::result
  else if start < n then
        (let result = ref [] in
          for i = start to n - start do
            let tmp_result = generate i (n - i) in
            let tmp_result_i = List.map (fun lst -> i :: lst) tmp_result in
            let tmp_result2 = tmp_result_i @ !result in
            result := tmp_result2
          done;
          !result ;)
  else
    [[n]];;


let generate_partitions n =
  generate 0 n ;;


generate_partitions 1 ;;
generate_partitions 2 ;;
generate_partitions 3 ;;

Generate All Subsets of N

(* In this scripte, we will write a function to generate all the subset of {1,2,...,n} 
 * The basic idea is to use the bit array of 1, 2, ..., n to represent the subset.
 *)

let rec int_power x n =
  let xf = float_of_int x
  and nf = float_of_int n in
  int_of_float (xf ** nf) ;;


let generate_subset n =
  let arr = Array.init n (fun x -> x + 1)in
  let rec generate_set result index k =
    match k with
    | 0 -> result
    | k ->
      if k land 1 = 1 then
        let elem = arr.(index) in
        generate_set (elem::result) (index + 1) (k lsr 1)
      else
        generate_set result (index + 1) (k lsr 1)
  in
    let rec generate_allset result k limit =
      match k < limit with
      | false -> result
      | true ->
        let res = generate_set [] 0 k in
        generate_allset (res::result) (k + 1) limit
    in
    let num_iter = int_power 2 n in
    let final_result = generate_allset [] 0 num_iter in
    final_result ;;


generate_subset 1 ;;
generate_subset 2 ;;
generate_subset 3 ;;
generate_subset 4 ;;

Implement max heap in Ocaml

(* In this script, we will implement the max heap.
 * In this implementation, we use the first element in
 * the array to store the number of elements in the heap.
 * This number has type of int, it follows that the heap
 * is of type int array.
 *)


let parent i = i / 2 ;;
let left i = 2 * i ;;
let right i = 2 * i + 1 ;;


(* the function heapify maintains the heap property of the sub-heap
 * rooted at k
 *)

let rec heapify heap k = 
  let count = heap.(0) in 
  if k < 1 then
    raise (Invalid_argument "heap")
  else if k < count then
    match left k <= count, right k <= count with
    |(true, true) ->
        let elem = heap.(k) 
        and elem_left = heap.(left k) 
        and elem_right = heap.(right k) in
        (match elem < elem_left, elem < elem_right with
        | (false, false ) -> ()
        | (_,_) ->
            if elem_left < elem_right then
                (heap.(k) <- elem_right; heap.(right k) <- elem; heapify heap (right k))
            else
                (heap.(k) <- elem_left; heap.(left k) <- elem; heapify heap (left k)))
    |(true, false) -> 
        let elem_left = heap.(left k) and elem = heap.(k) in
        if elem <elem_left then
          (heap.(left k) <- elem ; heap.(k) <- elem_left)
    |(false, _)  -> () ;;



(* the function heapify_all will call function heapify on every node in the heap *)

let heapify_all  heap = 
  let count = heap.(0) in
  for i = count downto 1 do
    heapify heap i
  done;;

(* add function will add a new element to the heap *)
let add heap elem = 
  let count = heap.(0) in
  if count = Array.length heap then
    raise (Failure "The heap is full. Cannot add new element.")
  else
    (heap.(0) <- count + 1;
     let p = ref heap.(0) in
     while !p / 2  > 0 && heap.(!p) > heap.(!p / 2)  do
       p := !p / 2;
       heapify heap !p
     done);;


(* max_heap return the maximum value of the heap but not remove it from the heap
 * *)
let max_heap heap =
  if heap.(0) = 0 then
    raise (Failure "The heap is empty.")
  else
    heap.(1) ;;

(* pop function returns the maximum value of the heap and remove it from the
 * heap *)

let pop heap = 
  let count = heap.(0) in
  if count  = 0 then
    raise (Failure "The heap is empty.")
  else
    let elem = heap.(1) in    
    heap.(1) <- heap.(count);
    heap.(0) <- count - 1;
    heapify heap 1;
    elem;;
   

Simple Implementation of Double Linked List in Ocaml

In this script, we will give a simple implementation of double linked list in OCaml. We can find more details in the book Introduction to Objective Caml, page 65.

type 'a elem =
  | Nil
  | Elem of 'a * 'a elem ref * 'a elem ref
;;

let nil_elem = Nil ;;   (* create a Nil element *)

let create_element x = Elem (x, ref Nil, ref Nil) ;;

let get = function
  | Elem (x, _, _) -> x
  | Nil -> raise (Invalid_argument "get") ;;

let prev_elem = function
  | Elem (_, prev, _) -> !prev
  | Nil -> raise (Invalid_argument "prev_elem") ;;



(* implement the doubly-linked list, the list itself can be just
 * a reference ot the first element. 
 *)

type 'a dlist = 'a elem ref ;;

let create () = ref Nil ;;

let insert list elem =
  match elem, !list with
  | Elem (_, prev, next), Nil ->
      prev := Nil;
      next := Nil;
      list := elem
  | Elem (_, prev1, next1) , (Elem (_, prev2, _) as head) ->
      prev1 := Nil;
      next1 := head;
      prev2 := elem;
      list  := elem
  | Nil, _ ->
      raise (Invalid_argument "insert")
;;

let remove list elem =
  match elem with
  | Elem (_, prev, next) ->
      (match !prev with
       | Elem (_, _, prev_next) -> prev_next := !next
       | Nil -> list := !next) ;
      (match !next with
       | Elem (_,next_prev, _) -> next_prev := !prev
       | Nil -> ())
  | Nil ->
      raise (Invalid_argument "remove")
;;

Rotate a one-dimensional array of N elements left by k positions

We can find the discussion of this problem in Bentley's book Programming Pears, Column 2.

First Solution

First observation is that we can decompose a rotation into several swap. This idea will lead us to find the recursive structure of the problem. Here is the implementation

let rec rotate arr is ie k i0 j0 =
  let kk = k mod (ie-is+1) in
  if is < ie && kk <> 0 then
    let condition_i0 = i0 < kk
    and condition_j0 = (is+j0) < ie in
    if condition_i0 then
      let tmp = arr.(is+i0) in
      arr.(is+i0) <- arr.(is+j0);
      arr.(is+j0) <- tmp;
      match condition_j0 with
      | true -> rotate arr is ie kk (i0+1) (j0+1)
      | false ->  let kk2 = kk - i0 - 1 in rotate arr (is+i0+1) ie kk2 0 kk2
    else
      rotate arr (is+kk) ie kk 0 kk
;;

Second Solution

We can also look at this problem from another point of view. We can decompose the rotation into several sub-rotation.

0  <- k <- 2k <- 3k ...
1 <- k+1 < 2k+1 <- 3k+1 <- ...

This idea leas to another solution.

let rec gcd a b =
  let x = min a b and y = max a b in
  if x = 0 then y
  else
    gcd x (y mod x ) ;;

let rotate2 arr k =
  let length = Array.length arr in
  let kk = k mod length in
  let n_loop = gcd kk length in
  let n_loop_j = length / n_loop in
  for i = 0 to n_loop - 1 do
    let tmp = arr.(i) in
    for j = 0 to n_loop_j - 2 do
      arr.((i+ j * kk) mod length) <- arr.((i + (j+1) * kk) mod length )
    done ;
    arr.((i + (n_loop_j-1) * kk) mod length) <- tmp
  done ;;

Third Solution

In the book we can find a third solution and it is very elegant.

rotate(n,k) = {reverse(n,0,k-1);
                       reverse(n,k,n-1);
                       reverse(n,0,n-1);}

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 ;;