Matrix Chain Optimal

  1. #include <iostream>
  2. #include <cstdlib>
  3. using namespace std;
  4.  
  5. #define MAX 32767
  6.  
  7. void MatrixChainOrder(int *p)
  8. {
  9.   int n = 6; int q;
  10.   int m[6][6];
  11.   for (int i = 0; i < n; i++)
  12.     m[i][i] = 0;                // lowest layer's value is 0
  13.   for (int l = 2; l <= n; l++)  // l is the chain length.
  14.     for (int i = 0; i < n - l + 1; i++) {
  15.       int j = i + l - 1;
  16.       m[i][j] = MAX;
  17.       for (int k = i; k <= j - 1; k++) {
  18.           q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
  19.         if (q < m[i][j])
  20.           m[i][j] = q;
  21.       }
  22.     }
  23.   cout << m[1][4] << endl;
  24. }
  25.  
  26. int main()
  27. {
  28.   int p[7] = {30, 35, 15, 5, 10, 20, 25};
  29.   MatrixChainOrder(p);
  30.   return 0;
  31. }

Binary Search Tree

 

  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. template <class Type>
  5. struct bNode {
  6.     Type key;
  7.     bNode *link[2];
  8.     bNode(){
  9.         link[0] = NULL;
  10.         link[1] = NULL;
  11.     }
  12. };
  13.  
  14. template <class Type>
  15. class BinarySearchTree {
  16. private:
  17.     int count;
  18.     bNode<Type> *root;
  19.     void clear(bNode<Type> *&ptr);
  20.     bool search(const Type &item, bNode<Type> *&curr, bNode<Type> *&prev, bool
  21.                 &lr) const;
  22.     inline Type inOrder(bNode<Type> *ptr) const;
  23.     inline int subNodes(bNode<Type> * const &ptr) const;
  24.     int height(bNode<Type>* const &ptr) const;
  25.     bNode<Type>* minmax(bNode<Type> *ptr, const bool &lr) const;
  26. public:
  27.     BinarySearchTree();
  28.     ~BinarySearchTree();
  29.     void clear();
  30.     bool isEmpty() const;
  31.     bool insert(const Type &item);
  32.     bool remove(const Type &item);
  33.     bool search(const Type &item, Type *&ptr) const;
  34.     Type min() const;
  35.     Type max() const;
  36.     int size() const;
  37.     int height() const;
  38. };
  39.  
  40. template <class Type>
  41. void BinarySearchTree<Type>::clear(bNode<Type> *&ptr)
  42. {
  43.     if (ptr != NULL) {
  44.         clear(ptr->link[0]);    // clear left
  45.         clear(ptr->link[1]);    // clear right;
  46.         delete ptr;             // delete recursively
  47.     }
  48. }
  49.  
  50. template <class Type>
  51. bool BinarySearchTree<Type>::search(const Type &item, bNode<Type> *&curr,
  52.                                     bNode<Type> *&prev, bool &lr) const
  53. {
  54.     while(curr != NULL) {
  55.         if (curr->key == item)
  56.             return true;
  57.         lr = (item > curr->key); // check bigger? go left : go right.
  58.         prev = curr;             
  59.         curr = curr->link[lr];
  60.     }
  61.     return false;
  62. }
  63.  
  64. template <class Type>
  65. inline Type BinarySearchTree<Type>::inOrder(bNode<Type> *ptr) const
  66. {
  67.     bool lr = 1;
  68.         Type temp;
  69.         bNode<Type> *prev = ptr;
  70.        
  71.         ptr = ptr->link[1]; // right child.
  72.         // find a node which have no left child in the right subTree.
  73.         // find (neighbor) next item. which of course, have no left child.
  74.         while (ptr->link[0] != NULL) {
  75.                 prev = ptr;
  76.                 ptr = ptr->link[lr = 0];
  77.         }
  78.         prev->link[lr] = ptr->link[1]; // remove the item.
  79.         temp = ptr->key; // save the value of the just removed item.
  80.         delete ptr;
  81.         return temp; // return the value.
  82. }
  83.  
  84. template <class Type>
  85. int BinarySearchTree<Type>::height(bNode<Type>* const &ptr) const
  86. {
  87.         if (ptr == NULL)
  88.                 return 0;
  89.         int lt = height(ptr->link[0]), rt = height(ptr->link[1]);
  90.         if (lt < rt)
  91.                 return 1 + rt;
  92.         return 1 + lt;
  93. }
  94.  
  95. template <class Type>
  96. bNode<Type>* BinarySearchTree<Type>::minmax(bNode<Type> *ptr, const bool &lr) const
  97. {
  98.         // lr = zero min: lr = NOZero, max;
  99.         while (ptr->link[lr] != NULL)
  100.                 ptr = ptr->link[lr];
  101.         return ptr;
  102. }
  103.  
  104. template <class Type>
  105. BinarySearchTree<Type>::BinarySearchTree()
  106. {
  107.         // constructor
  108.         root = NULL;
  109.         count = 0;
  110. }
  111.  
  112. template <class Type>
  113. BinarySearchTree<Type>::~BinarySearchTree()
  114. {
  115.         clear(root);
  116. }
  117.  
  118. template <class Type>
  119. void BinarySearchTree<Type>::clear()
  120. {
  121.         clear(root);
  122.         root = NULL;
  123.         count = 0;
  124. }
  125.  
  126. template <class Type>
  127. bool BinarySearchTree<Type>::isEmpty() const
  128. {
  129.         return (root == NULL);
  130. }
  131.  
  132. template <class Type>
  133. bool BinarySearchTree<Type>::insert(const Type &item)
  134. {
  135.         if (root == NULL) {
  136.                 root = new bNode<Type>;
  137.                 root->key = item;
  138.                 count++;
  139.                 return true;
  140.         }
  141.         bool lr;
  142.         bNode<Type> *curr = root, *prev;
  143.         if (search(item, curr, prev, lr)) // overlap item is not allowed.
  144.                 return false;
  145.         prev->link[lr] = new bNode<Type>;
  146.         prev->link[lr]->key = item;
  147.         count++;
  148.         return true;
  149. }
  150.  
  151. template <class Type>
  152. inline int BinarySearchTree<Type>::subNodes(bNode<Type>* const &ptr) const
  153. {
  154.         if (ptr->link[1] != NULL) {
  155.                 if (ptr->link[0] != NULL) // have two childs
  156.                         return 2;
  157.                 else
  158.                         return 1// have only one child
  159.         } else if (ptr->link[0] != NULL)
  160.                 return 1; // have only one child.
  161.         else
  162.                 return 0; // have no child
  163. }
  164.  
  165. template <class Type>
  166. bool BinarySearchTree<Type>::remove(const Type &item)
  167. {
  168.         bool lr = 1;
  169.         bNode<Type> *curr = root, *prev;
  170.         if (!search(item, curr, prev, lr))
  171.                 return false;
  172.         switch (int s = subNodes(curr)) {
  173.         // get the number of childs.
  174.         case 0:
  175.         case 1:
  176.                 if (curr == root)
  177.                         root = curr->link[(s > 0)];
  178.                 else
  179.                         prev->link[lr] = curr->link[(s > 0)];
  180.                 delete curr;
  181.                 break;
  182.         case 2:
  183.                 curr->key = inOrder(curr); // replace the value with the next(neighbour) item's
  184.         }
  185.         count--;
  186.         return true;
  187. }
  188.  
  189. template <class Type>
  190. bool BinarySearchTree<Type>::search(const Type &item, Type *&ptr) const
  191. {
  192.         bool found;
  193.         bNode<Type> *curr = root, *prev;
  194.         found = search(item, curr, prev, found);
  195.         ptr = &curr->key;
  196.         return found;
  197. }
  198.  
  199. template <class Type>
  200. Type BinarySearchTree<Type>::min() const
  201. {
  202.     return minmax(root, 0)->key;
  203. }
  204.  
  205. template <class Type>
  206. Type BinarySearchTree<Type>::max() const
  207. {
  208.     return minmax(root, 1)->key;
  209. }
  210.  
  211. template <class Type>
  212. int BinarySearchTree<Type>::size() const
  213. {
  214.     return count;
  215. }
  216.  
  217. template <class Type>
  218. int BinarySearchTree<Type>::height() const
  219. {
  220.     return height(root);
  221. }
  222.  
  223. int main(int argc, char **argv)
  224. {
  225.         BinarySearchTree<int> *bst = new BinarySearchTree<int>();
  226.         //               8
  227.         //             /   \
  228.         //            7     9
  229.         //           / \   /  \
  230.         //          5   4 10  11
  231.         bst->insert(8);
  232.         bst->insert(7);
  233.         bst->insert(9);
  234.         bst->insert(5);
  235.         bst->insert(4);
  236.         bst->insert(10);
  237.         bst->insert(11);
  238.         std::cout << bst->height()  << std::endl;
  239.         std::cout << bst->min() << std::endl;
  240.         std::cout << bst->max() << std::endl;
  241.         std::cout << bst->size() << std::endl;
  242.         std::cout << bst->remove(8) << std::endl;
  243.         std::cout << bst->size() << std::endl;
  244.         std::cout << bst->height()  << std::endl;
  245.         delete bst;
  246.         return 0;
  247. }

Reverse a string

Evil C:

#include <stdio.h>

void strrev(char *p)
{
 
char *q = p;
 
while(q && *q) ++q;
 
for(--q; p < q; ++p, --q)
   
*p = *p ^ *q,
   
*q = *p ^ *q,
   
*p = *p ^ *q;
}

int main(int argc, char **argv)
{
 
do {
    printf
("%s ",  argv[argc-1]); strrev(argv[argc-1]);
    printf
("%s\n", argv[argc-1]);
 
} while(--argc);

 
return 0;
}

(This is XOR-swap thing. Take care to note that you must avoid swapping with self, because a^a==0.)


Ok, fine, let's fix the UTF-8 chars...

#include <bits/types.h>
#include <stdio.h>

#define SWP(x,y) (x^=y, y^=x, x^=y)

void strrev(char *p)
{
 
char *q = p;
 
while(q && *q) ++q; /* find eos */
 
for(--q; p < q; ++p, --q) SWP(*p, *q);
}

void strrev_utf8(char *p)
{
 
char *q = p;
  strrev
(p); /* call base case */

 
/* Ok, now fix bass-ackwards UTF chars. */
 
while(q && *q) ++q; /* find eos */
 
while(p < --q)
   
switch( (*q & 0xF0) >> 4 ) {
   
case 0xF: /* U+010000-U+10FFFF: four bytes. */
      SWP
(*(q-0), *(q-3));
      SWP
(*(q-1), *(q-2));
      q
-= 3;
     
break;
   
case 0xE: /* U+000800-U+00FFFF: three bytes. */
      SWP
(*(q-0), *(q-2));
      q
-= 2;
     
break;
   
case 0xC: /* fall-through */
   
case 0xD: /* U+000080-U+0007FF: two bytes. */
      SWP
(*(q-0), *(q-1));
      q
--;
     
break;
   
}
}

int main(int argc, char **argv)
{
 
do {
    printf
("%s ",  argv[argc-1]); strrev_utf8(argv[argc-1]);
    printf
("%s\n", argv[argc-1]);
 
} while(--argc);

 
return 0;
}
  • Why, yes, if the input is borked, this will cheerfully swap outside the place.
  • Useful link when vandalising in the UNICODE: http://www.macchiato.com/unicode/chart/
  • Also, UTF-8 over 0x10000 is untested (as I don't seem to have any font for it, nor the patience to use a hexeditor)

    $ ./strrev Räksmörgås ░▒▓○◔◑◕●

    ░▒▓○◔◑◕● ●◕◑◔○▓▒░

    Räksmörgås sågrömskäR

    ./strrev verrts/.

拍个QuickSort

  1. void Swap(int *a, int *b)
  2. {
  3.     int tmp = *a;
  4.     *a = *b;   
  5.     *b = tmp;   
  6. }
  7.  
  8. int partition(int *a, int p, int r)
  9. {
  10.     int x = a[r];
  11.     int i = p - 1;
  12.     int j = p;
  13.    
  14.     for (; j <= (r - 1); j++)
  15.         if (a[j] < x)
  16.         {
  17.             i++;
  18.             Swap(&a[i], &a[j]);
  19.         }
  20.     Swap(&a[i+1], &a[r]);
  21.     return i+1;
  22. }
  23.    
  24.        
  25. void quickSort(int *a, int p, int r)
  26. {
  27.     if (p < r) {
  28.         int q = partition(a, p, r);
  29.         quickSort(a, p, q - 1);
  30.         quickSort(a, q + 1, r);
  31.     }
  32. }
  33. int main(int argc, char *argv[])
  34. {
  35.     int a[] = {0, 8, 7, 1, 3, 5, 6, 4};
  36.     int sorted[8] = {0,1,3,4,5,6,7,8};
  37.     int ii = 0;
  38.    
  39.     quickSort(a, 2, 7);
  40.     for(; ii < 8; ii++)
  41.         //if(sorted[ii] != a[ii])
  42.             printf("failed in %d\n", a[ii]);
  43.  
  44.     // printf("Success\n");
  45.    
  46. //    int k1 = 3, k2 = 4;
  47. //    int a[2] ={0,1};
  48.    
  49.    
  50.     /* Swap(&a[0], &a[1]);   */
  51.     /* printf("k1=%d, k2=%d", a[0], a[1]); */
  52.    
  53.     return 0;
  54. }
  55.  
  56.  

 

在阿里巴巴吃到的蜇

 #include <stdio.h>

int printer(int x)
{
    int counter = 0;
    while(x) {
        counter++;
        x = x & (x-1);//算一的个数
    }
    return counter;
}

int main()
{
    printf("%d\n", printer(9999));
    return 0;
}

Puzzle: Fast Bit Counting

 Explaination and Analysis

  1.  
  2. /*
  3.    Bit Counting routines
  4.  
  5.    Author: Gurmeet Singh Manku    (manku@cs.stanford.edu)
  6.    Date:   27 Aug 2002
  7.   */
  8.  
  9.  
  10. #include <stdlib.h>
  11. #include <stdio.h>
  12. #include <limits.h>
  13.  
  14. /* Iterated bitcount iterates over each bit. The while condition sometimes helps
  15.    terminates the loop earlier */
  16. int iterated_bitcount (unsigned int n)
  17. {
  18.     int count=0;   
  19.     while (n)
  20.     {
  21.         count += n & 0x1u ;   
  22.         n >>= 1 ;
  23.     }
  24.     return count ;
  25. }
  26.  
  27.  
  28. /* Sparse Ones runs proportional to the number of ones in n.
  29.    The line   n &= (n-1)   simply sets the last 1 bit in n to zero. */
  30. int sparse_ones_bitcount (unsigned int n)
  31. {
  32.     int count=0 ;
  33.     while (n)
  34.     {
  35.         count++ ;
  36.         n &= (n - 1) ;     
  37.     }
  38.     return count ;
  39. }
  40.  
  41.  
  42. /* Dense Ones runs proportional to the number of zeros in n.
  43.    It first toggles all bits in n, then diminishes count repeatedly */
  44. int dense_ones_bitcount (unsigned int n)
  45. {
  46.     int count = 8 * sizeof(int) ;   
  47.     n ^= (unsigned int) -1 ;
  48.     while (n)
  49.     {
  50.         count-- ;
  51.         n &= (n - 1) ;   
  52.     }
  53.     return count ;
  54. }
  55.  
  56.  
  57. /* Precomputed bitcount uses a precomputed array that stores the number of ones
  58.    in each char. */
  59. static int bits_in_char [256] ;
  60.  
  61. void compute_bits_in_char (void)
  62. {
  63.     unsigned int i ;   
  64.     for (i = 0; i < 256; i++)
  65.         bits_in_char [i] = iterated_bitcount (i) ;
  66.     return ;
  67. }
  68.  
  69. int precomputed_bitcount (unsigned int n)
  70. {
  71.     // works only for 32-bit ints
  72.    
  73.     return bits_in_char [n         & 0xffu]
  74.         +  bits_in_char [(n >>  8) & 0xffu]
  75.         +  bits_in_char [(n >> 16) & 0xffu]
  76.         +  bits_in_char [(n >> 24) & 0xffu] ;
  77. }
  78.  
  79.  
  80. /* Here is another version of precomputed bitcount that uses a precomputed array
  81.    that stores the number of ones in each short. */
  82.  
  83. static char bits_in_16bits [0x1u << 16] ;
  84.  
  85. void compute_bits_in_16bits (void)
  86. {
  87.     unsigned int i ;   
  88.     for (i = 0; i < (0x1u<<16); i++)
  89.         bits_in_16bits [i] = iterated_bitcount (i) ;
  90.     return ;
  91. }
  92.  
  93. int precomputed16_bitcount (unsigned int n)
  94. {
  95.     // works only for 32-bit int
  96.    
  97.     return bits_in_16bits [n         & 0xffffu]
  98.         +  bits_in_16bits [(n >> 16) & 0xffffu] ;
  99. }
  100.  
  101.  
  102. /* Parallel   Count   carries   out    bit   counting   in   a   parallel
  103.    fashion.   Consider   n   after    the   first   line   has   finished
  104.    executing. Imagine splitting n into  pairs of bits. Each pair contains
  105.    the <em>number of ones</em> in those two bit positions in the original
  106.    n.  After the second line has finished executing, each nibble contains
  107.    the  <em>number of  ones</em>  in  those four  bits  positions in  the
  108.    original n. Continuing  this for five iterations, the  64 bits contain
  109.    the  number  of ones  among  these  sixty-four  bit positions  in  the
  110.    original n. That is what we wanted to compute. */
  111.  
  112. #define TWO(c) (0x1u << (c))
  113. #define MASK(c) (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
  114. #define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
  115.  
  116. int parallel_bitcount (unsigned int n)
  117. {
  118.     n = COUNT(n, 0) ;
  119.     n = COUNT(n, 1) ;
  120.     n = COUNT(n, 2) ;
  121.     n = COUNT(n, 3) ;
  122.     n = COUNT(n, 4) ;
  123.     /* n = COUNT(n, 5) ;    for 64-bit integers */
  124.     return n ;
  125. }
  126.  
  127.  
  128. /* Nifty  Parallel Count works  the same  way as  Parallel Count  for the
  129.    first three iterations. At the end  of the third line (just before the
  130.    return), each byte of n contains the number of ones in those eight bit
  131.    positions in  the original n. A  little thought then  explains why the
  132.    remainder modulo 255 works. */
  133.  
  134. #define MASK_01010101 (((unsigned int)(-1))/3)
  135. #define MASK_00110011 (((unsigned int)(-1))/5)
  136. #define MASK_00001111 (((unsigned int)(-1))/17)
  137.  
  138. int nifty_bitcount (unsigned int n)
  139. {
  140.     n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
  141.     n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
  142.     n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;       
  143.     return n % 255 ;
  144. }
  145.  
  146. /* MIT Bitcount
  147.  
  148.    Consider a 3 bit number as being
  149.         4a+2b+c
  150.    if we shift it right 1 bit, we have
  151.         2a+b
  152.   subtracting this from the original gives
  153.         2a+b+c
  154.   if we shift the original 2 bits right we get
  155.         a
  156.   and so with another subtraction we have
  157.         a+b+c
  158.   which is the number of bits in the original number.
  159.  
  160.   Suitable masking  allows the sums of  the octal digits  in a 32 bit  number to
  161.   appear in  each octal digit.  This  isn't much help  unless we can get  all of
  162.   them summed together.   This can be done by modulo  arithmetic (sum the digits
  163.   in a number by  molulo the base of the number minus  one) the old "casting out
  164.   nines" trick  they taught  in school before  calculators were  invented.  Now,
  165.   using mod 7 wont help us, because our number will very likely have more than 7
  166.   bits set.   So add  the octal digits  together to  get base64 digits,  and use
  167.   modulo 63.   (Those of you  with 64  bit machines need  to add 3  octal digits
  168.   together to get base512 digits, and use mod 511.)
  169.  
  170.   This is HACKMEM 169, as used in X11 sources.
  171.   Source: MIT AI Lab memo, late 1970's.
  172. */
  173.  
  174. int mit_bitcount(unsigned int n)
  175. {
  176.     /* works for 32-bit numbers only */
  177.     register unsigned int tmp;
  178.    
  179.     tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
  180.     return ((tmp + (tmp >> 3)) & 030707070707) % 63;
  181. }
  182.  
  183. void verify_bitcounts (unsigned int x)
  184. {
  185.     int iterated_ones, sparse_ones, dense_ones ;
  186.     int precomputed_ones, precomputed16_ones ;
  187.     int parallel_ones, nifty_ones ;
  188.     int mit_ones ;
  189.    
  190.     iterated_ones      = iterated_bitcount      (x) ;
  191.     sparse_ones        = sparse_ones_bitcount   (x) ;
  192.     dense_ones         = dense_ones_bitcount    (x) ;
  193.     precomputed_ones   = precomputed_bitcount   (x) ;
  194.     precomputed16_ones = precomputed16_bitcount (x) ;
  195.     parallel_ones      = parallel_bitcount      (x) ;
  196.     nifty_ones         = nifty_bitcount         (x) ;
  197.     mit_ones           = mit_bitcount           (x) ;
  198.  
  199.     if (iterated_ones != sparse_ones)
  200.     {
  201.         printf ("ERROR: sparse_bitcount (0x%x) not okay!\n", x) ;
  202.         exit (0) ;
  203.     }
  204.    
  205.     if (iterated_ones != dense_ones)
  206.     {
  207.         printf ("ERROR: dense_bitcount (0x%x) not okay!\n", x) ;
  208.         exit (0) ;
  209.     }
  210.  
  211.     if (iterated_ones != precomputed_ones)
  212.     {
  213.         printf ("ERROR: precomputed_bitcount (0x%x) not okay!\n", x) ;
  214.         exit (0) ;
  215.     }
  216.        
  217.     if (iterated_ones != precomputed16_ones)
  218.     {
  219.         printf ("ERROR: precomputed16_bitcount (0x%x) not okay!\n", x) ;
  220.         exit (0) ;
  221.     }
  222.    
  223.     if (iterated_ones != parallel_ones)
  224.     {
  225.         printf ("ERROR: parallel_bitcount (0x%x) not okay!\n", x) ;
  226.         exit (0) ;
  227.     }
  228.  
  229.     if (iterated_ones != nifty_ones)
  230.     {
  231.         printf ("ERROR: nifty_bitcount (0x%x) not okay!\n", x) ;
  232.         exit (0) ;
  233.     }
  234.  
  235.     if (mit_ones != nifty_ones)
  236.     {
  237.         printf ("ERROR: mit_bitcount (0x%x) not okay!\n", x) ;
  238.         exit (0) ;
  239.     }
  240.    
  241.     return ;
  242. }
  243.  
  244.  
  245. int main (void)
  246. {
  247.     int i ;
  248.    
  249.     compute_bits_in_char () ;
  250.     compute_bits_in_16bits () ;
  251.  
  252.     verify_bitcounts (UINT_MAX) ;
  253.     verify_bitcounts (0) ;
  254.    
  255.     for (i = 0 ; i < 100000 ; i++)
  256.         verify_bitcounts (lrand48 ()) ;
  257.    
  258.     printf ("All bitcounts seem okay!\n") ;
  259.    
  260.     return 0 ;
  261. }

Tic Tac Toe

 

  1. # Tic Tac Toe
  2. import random
  3.  
  4. def drawBoard(board):
  5.     # This function prints out the board that is was passed.
  6.     # "board" is a list of 10 strings representing the board
  7.     print '   |    |'
  8.     print ' ' + board[7] + ' | ' + board[8] + '  | ' + board[9]
  9.     print '   |    |'
  10.     print '------------'
  11.     print '   |    |'
  12.     print ' ' + board[4] + ' | ' + board[5] + '  | ' + board[6]
  13.     print '   |    |'
  14.     print '------------'
  15.     print '   |    |'
  16.     print ' ' + board[1] + ' | ' + board[2] + '  | ' + board[3]
  17.     print '   |    |'
  18.  
  19. def inputPlayerLetter():
  20.     # Let's the player type which letter they want to be.
  21.     # Returns a list with the player's letter as the first
  22.     # item, and the computer's letter as the second.
  23.     letter = ''
  24.     while not (letter == 'X' or letter == 'O'):
  25.         print 'Do you want to be X or O?'
  26.         letter = raw_input().upper()
  27.  
  28.     if letter == 'X':
  29.         return ['X', 'O']
  30.     else:
  31.         return ['O', 'X']
  32.  
  33. def whoGoesFirst():
  34.     # Randomly choose the player who goes first.
  35.     if random.randint(0, 1) == 0:
  36.         return 'computer'
  37.     else:
  38.         return 'player'
  39.  
  40. def playAgain():
  41.     print 'Do you want to play again?'
  42.     return raw_input().lower().startswith('y')
  43.  
  44. def makeMove(board, letter, move):
  45.     board[move] = letter
  46.  
  47. def isWinner(bo, le):
  48.     # Given a board and a player's letter, this function returns
  49.     # True if that player has won.
  50.     return ((bo[7] == le and bo[8] == le and bo[9] == le) or
  51.             (bo[4] == le and bo[5] == le and bo[6] == le) or
  52.             (bo[1] == le and bo[2] == le and bo[3] == le) or
  53.             (bo[7] == le and bo[5] == le and bo[3] == le) or
  54.             (bo[9] == le and bo[5] == le and bo[1] == le) or
  55.             (bo[7] == le and bo[4] == le and bo[1] == le) or
  56.             (bo[8] == le and bo[5] == le and bo[2] == le) or
  57.             (bo[9] == le and bo[6] == le and bo[3] == le))
  58.  
  59. def getBoardCopy(board):
  60.     # Make a duplicate of the board
  61.     dupBoard = []
  62.  
  63.     for i in board:
  64.         dupBoard.append(i)
  65.     return dupBoard
  66.  
  67. def isSpaceFree(board, move):
  68.     return board[move] == ' '
  69.  
  70. def getPlayerMove(board):
  71.     move = ' '
  72.     while move not in '1 2 3 4 5 6 7 8 9'.split() or not isSpaceFree(board,
  73.                                                                  int(move)):
  74.         print 'What is your next move?(1-9)'
  75.         move = raw_input()
  76.     return int(move)
  77.  
  78. def chooseRandomMoveFromList(board, moveList):
  79.     # Returns a valid move from the passed list on the passed board
  80.     # return None if there is no valid move
  81.     possibleMoves = []
  82.     for i in moveList:
  83.         if isSpaceFree(board, i):
  84.             possibleMoves.append(i)
  85.  
  86.     if len(possibleMoves) != 0:
  87.         return random.choice(possibleMoves)
  88.     else:
  89.         return None
  90.  
  91. def getComputerMove(board, computerLetter):
  92.     # Given a board and the computer's letter, determine
  93.     # where to move and return  that move.
  94.     if computerLetter == 'X':
  95.         playerLetter = 'O'
  96.     else:
  97.         playerLetter = 'X'
  98.  
  99.  
  100.         # Here is our algorithm for our Tic Tac Toe AI:
  101.         # First, check if we can win in the next move.
  102.     for i in range(1, 9):
  103.         copy = getBoardCopy(board)
  104.         if isSpaceFree(copy, i):
  105.             makeMove(copy, computerLetter, i)
  106.             if isWinner(copy, computerLetter):
  107.                 return i
  108.         # Check if the player could win on their next move, and block them.
  109.     for i in range(1, 9):
  110.         copy = getBoardCopy(board)
  111.         if isSpaceFree(copy, i):
  112.             makeMove(copy, playerLetter, i)
  113.             if isWinner(copy, playerLetter):
  114.                 return i
  115.  
  116.         # Try to take one of the corners, if they are free.
  117.     move = chooseRandomMoveFromList(board, [1, 3, 7, 9])
  118.     if move != None:
  119.         return move
  120.  
  121.     # Try to take the center, if it is free.
  122.     if isSpaceFree(board, 5):
  123.         return 5
  124.         # Move on one of the sides.
  125.     return chooseRandomMoveFromList(board, [2, 4, 6, 8])
  126.        
  127. def isBoardFull(board):
  128.     # Return True if every space on the board has been
  129.     # taken.Otherwise return False.
  130.     for i in range(1, 10):
  131.         if isSpaceFree(board, i):
  132.             return False
  133.     return True
  134.  
  135. print 'Welcome to the Hell of Tic Tac Toe!'
  136.  
  137. while True:
  138.     # Reset the board
  139.     theBoard = [' '] * 10
  140.     playerLetter, computerLetter = inputPlayerLetter()
  141.     turn = whoGoesFirst()
  142.     print 'The ' + turn + ' will go first.'
  143.     gameIsPlaying = True
  144.  
  145.     while gameIsPlaying:
  146.         if turn == 'player':
  147.             # Player's turn.
  148.             drawBoard(theBoard)
  149.             move = getPlayerMove(theBoard)
  150.             makeMove(theBoard, playerLetter, move)
  151.             #drawBoard(theBoard)
  152.            
  153.             if isWinner(theBoard, playerLetter):
  154.                 drawBoard(theBoard)
  155.                 print 'Hooray! you have won the game!'
  156.                 gameIsPlaying = False
  157.             else:
  158.                 if isBoardFull(theBoard):
  159.                     drawBoard(theBoard)
  160.                     print 'The game is a tie!'
  161.                     break
  162.                 else:
  163.                     turn = 'computer'
  164.                     #drawBoard(theBoard)
  165.  
  166.         else:
  167.             # Computer's turn.
  168.             #drawBoard(theBoard)
  169.             move = getComputerMove(theBoard, computerLetter)           
  170.             makeMove(theBoard, computerLetter, move)
  171.             print 'Computer is moving'
  172.             if isWinner(theBoard, computerLetter):
  173.                 drawBoard(theBoard)
  174.                 print 'The computer has beaten you!You lose.'
  175.                 gameIsPlaying = False
  176.             else:
  177.                 if isBoardFull(theBoard):
  178.                     drawBoard(theBoard)
  179.                     print 'The game is a tie!'
  180.                     break
  181.                 else:
  182.                     turn = 'player'
  183.                     #drawBoard(theBoard)
  184.     if not playAgain():
  185.         break
  186.  

Fast median search

 a asic implementationn

  1. #define ELEM_SWAP(a, b) {
  2.     register elem_type t = (a); (a) = (b); (b) = (t);
  3. }
  4.  
  5. elem_type quickSelect(elem_type arr[], int n)
  6. {
  7.     int low, high;
  8.     int median;
  9.     int middle, ll, hh;
  10.  
  11.     low = 0;
  12.     high = n - 1;
  13.     median = (low + high) / 2;
  14.     for (; ;)
  15.     {
  16.         if (high < low)         /* one element only */
  17.             return arr[median];
  18.         if (high == low + 1) {
  19.             /* Two elements only */
  20.             if (arr[low] > arr[high])
  21.                 ELEM_SWAP(arr[low], arr[high]);
  22.             return arr[median];
  23.         }
  24.  
  25.         /* Find median of low, median and high items; Swap into positin low */
  26.         middle = (low + high) / 2;
  27.         if (arr[middle] > arr[high]) ELEM_SWAP(arr[middle], arr[high]);
  28.         if (arr[low] > arr[high]) ELEM_SWAP(arr[low], arr[high]);
  29.         if (arr[middle] > arr[low]) ELEM_SWAP(arr[middle], arr[low]);
  30.  
  31.         /* Swap low item (now in position middle) into low + 1 */
  32.         ELEM_SWAP(arr[middle], arr[low+1]);
  33.  
  34.         /* Nibble from each end towards middle, swapping items was stuck */
  35.         ll = low + 1;
  36.         hh = high;
  37.         for (;;)
  38.         {
  39.             do ll++; while (arr[low] > arr[ll]);
  40.             do hh--; while (arr[hh] > arr[low]);
  41.  
  42.             if (hh < ll) break;
  43.             ELEM_SWAP(arr[ll], arr[hh]);
  44.            
  45.         }
  46.         /* Swap middle item (in position low) back into position */
  47.         ELEM_SWAP(arr[low], arr[hh]);
  48.         /* Re-set actieve partition */
  49.         if (hh <= median)
  50.             low = ll;
  51.         if (hh >= median)
  52.             high = hh - 1;
  53.     }
  54. }
  55.  
  56.  

Algo -> Python so convenient !


Multiplication a la Francais.

         

Python implementation

function multiply(x; y)
Input: Two n-bit integers x and y, where y >= 0
Output: Their product
if y = 0: return 0
z = multiply(x; by=2c)
if y is even:
   return 2z
else:
   return x + 2z
 
  1. def mul(x, y):
  2.         if y == 0:
  3.                 return 0
  4.         z = mul(x, y/2)
  5.         if y % 2 == 0:
  6.                 return 2*z
  7.         else:
  8.                 return x + 2*z

Source: P24, Algorithms, Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, 2006

Recursion Explaination

 A CS professor once explained recursion as follows

child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
        ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

This is real cool!