Wednesday, September 26, 2007

A Chinese Fortune Teller

I happened to see this Chinese fortune teller in the shopping mall claiming that he can tell your Chinese surname without you telling him what your surname is. He claimed he has this "special power" or "six sense" in him.

All you have to do is to pick up one of the cards (16 of them) that has your surname. Put that card (face down) on the card board grid that has the same surname. Before he tells you the surname, you will ensure you are indeed picking up your own surname (i suppose this is to cover his backside in case you do not choose your own surname). Once the 'victim' convinced that the fortune teller has that 'special power', he will invite the 'victim' to sit down so that he can tell you a bit of your future. That's where the money will come when you tip him towards the end. Most of the stuff he talked about are pretty general.

I was surprised that he was able to do that correctly every time. At the back of my mind, I was thinking if he was so damn good, he wouldn't have to be here, right! So the question is how can he accomplish this, does he really have that special power ? Below images show you the HOW TO.

Lots of Chinese surnames written on the card board:

Find your surname in one of these 16 cards (You can shuffle the surname in each card to prevent your victim from finding out the pattern)

Below shows how these cards are prepared to ensure that you can correctly tell your "victim" surname. In this special case, no matter where you are going to place on the card board grid, you can be for sure that the first surname in the grid is the correct one. Now all you have to do is to find a way to tell the card #.

Open Office Calc == MS Excel ?

I was helping a colleague to analyse and present the Cisco firewall rules using a Apache, CGI and shell script. Another colleague was telling me that I can use MS Excel to do similar things and he showed me a few tricks which are damn useful. He also highlighted to me that MS Excel has a limitation of max of 65536 rows. During our discussion, we are wondering whether Open Office Calc is better than Excel in this aspect. Now, I am going to undercover the truth ...

I generated 70,000 CSV records with 3 fields in each record using awk. This CSV file will be imported into MS Excel and Open Office.

awk '
  for(i=1;i<=70000;++i) {
    print i,i+1,i+2
}' /dev/null > 70k.csv

Below are the screen dumps for both applications in importing the 70k.csv file. To my disappointment, OO Calc (my version is 2.0.2) has the same limitation as MS Excel.

MS Excel error in loading 70,000 records

MS Excel can only load 65536 records

OO error in loading 70,000 records

OO can only load 65536 records

Labels: , ,

Wednesday, September 19, 2007

Endianness, beautifully done

My performance enthusiastic friend wrote an excellent article (with working code) in how to determine the system's endianness and how to do swap bytes.

Out of curiosity, I browsed the Tcl source code to see how Tcl work out the global variable tcl_platform(byteOrder). Below code is extracted from tclBasic.c under the Tcl8.4.x source base. It is done beautifully and it really showed what Beautiful Code is all about.


     union {
         char c[sizeof(short)];
         short s;
     } order;


      * Compute the byte order of this machine.

     order.s = 1;
     Tcl_SetVar2(interp, "tcl_platform", "byteOrder",
             ((order.c[0] == 1) ? "littleEndian" : "bigEndian"),

I extracted part of the code for verification.

union {
         char c[sizeof(short)];
         short s;
} order;

int main(void)
         printf("%s\n",order.c[0]==1 ? "littleEndian" : "bigEndian");

On my Intel notebook, it is littleEndian and on the SPARC it is bigEndian. Of course it tallies with the Tcl global variable tcl_platform(byteOrder). In case you a Perl guy, this is how you can do it:

$is_big = unpack("h*", pack("s", 1)) =~ /01/;
$is_little = unpack("h*", pack("s", 1)) =~ /^1/;

Labels: ,

Monday, September 17, 2007

Primary 5 Maths Question

During 1 week September school holiday, my son (Primary 5) was given a set of maths questions (50 of them) to solve. One of them seems almost clueless but later found out that there is a better way to solve it than a brute force approach.

I am not sure how many of our 11-year old kids can solve this type of question? Or, how many of the teachers can solve this question and manage to explain to the kid until they understand ? Anyway, the question is:

[Q] John bought 3 of the 6 items and Peter bought 2 of the remaining items. John spent twice as much as Peter. Which items did each of them buy ?

Item 1Ping-pong bat$4.70
Item 2Ping-pong ball$2.70
Item 3Shuttlecock$1.40
Item 4T-shirt$3.10
Item 5Shoes$7.20
Item 6Racket$6.10

Let me take you through my thinking process.

  • My first impression is that how on earth can I find a solution using the "model approach" (method to solve a problem without using algebra, it is taught in primary school). I did not spend much time in thinking of the problem because there are 60 combinations to try ( 6C3 * 3C2 ) and it would be too tough to do it manually. Instead, I tapped onto my programming skill to do a "brute force attack" approach to verify an answer(s) exist. This is the Tcl script I wrote:
    package require struct
    array set price { 1 4.70 2 2.70 3 1.40 4 3.10 5 7.20 6 6.10 }
    proc PriceSum { items } {
     global price
     set peterSum 0
     foreach i $items {
      set peterSum [expr {$peterSum+$price($i)}]
     return $peterSum
    set all [array names price]
    set allN [array size price]
    for { set i 1 } { $i<=$allN } { incr i } {
     for { set j $i } { $j<=$allN } { incr j } {
      for { set k $j } { $k<=$allN } { incr k } {
       if { $i == $j || $j == $k || $i == $k } { continue }
       set john     [list $i $j $k]
       set peter012 [struct::set difference $all $john]
       set peter01  [list [lindex $peter012 0] [lindex $peter012 1]]
       set peter12  [list [lindex $peter012 1] [lindex $peter012 2]]
       set peter02  [list [lindex $peter012 0] [lindex $peter012 2]]
       set peterSum01  [PriceSum $peter01]
       set peterSum12  [PriceSum $peter12]
       set peterSum02  [PriceSum $peter02]
       set johnSumHalf [expr [PriceSum $john]/2]
       if { $johnSumHalf == $peterSum01 } {
        puts "John: $john, Peter: $peter01"
       } elseif { $johnSumHalf == $peterSum12 } {
        puts "John: $john, Peter: $peter12"
       } elseif { $johnSumHalf == $peterSum02 } {
        puts "John: $john, Peter: $peter02"
    The answer is:
    John: 1 4 5, Peter: 6 3

    OK, a unique solution does exist. If it is a Primary 5 question, I am sure there is a simplier way to solve it.

  • If John bought 3 items and Peter bought 2 items, there will be 1 item left. Ok, may be we can work out the total amount spent by John and Peter and see whether the amount can be divisble by 3, since John spent twice than Peter. Hey, that's the model approach (see model below), isn't it. Great, let's tabulate the result


    John spent
    Peter spent

    Item NTotal w/o Item NDivisble by 3?

    Now we narrowed down to two possible routes, either item 2 or item 5 is not being bought by John and Peter.

    • Case 1: Item 2 not being bought
      If John spent twice the amount as Peter, the 10¢ digit of the sum of 3 items has to be an even number (we do not have to work out the exact total). We can ignore it if it is odd.
      John's Items10¢ digit
      (sum of John's items)
      Peter's Items10¢ digit
      (sum of Peter's items)
      Twice ?
      Bingo! John bought Items 1,4,5 and Peter bought items 3 and 6. This tally with my "brute force attack" approach.
    • Case 2: Item 5 not being bought
      You can repeat the same tabulation but I can tell you that there is no solution.

  • Another approach that I can think of. If you look at the cost of the items, the 10¢ digits are basically just 1, 2, 4 and 7. There are only 4 numbers and there won't be a lot of combination to try. If John spent twice as much as Peter, the 10¢ digit sum has to be even, let's tabulate so that we can narrow down our search
    John's items
    (10¢ digit)
    Cost of 3 items
    (10¢ digit)
    Possible Answer?
    1,2,70Yes (ie, items 5,[12],[4,6])
    1,4,72Yes (ie, items 3,[12],[4,6])
    Note: [12] means either 1 or 2, in regular expression notation

    Another tablulation for John's items

    John's itemsSum of 2 items = half of John's (10¢ digit)John=2xPeter?
    5,1,4 ($15.0)$7.50 = items 3,6Yes
    5,1,6 ($18.0)$9.00 = xx
    5,2,4 ($12.0)$6.00 = xx
    5,2,6 ($16.0)$8.00 = xx
    3,1,4 ($9.20)$4.60 = xx
    3,1,6 ($12.2)$6.10 = xx
    3,2,4 ($7.20)$3.60 = xx
    3,2,6 ($10.2)$5.10 = xx

Hope that the teacher and the students read my blog:-)

Labels: ,

Wednesday, September 12, 2007

Code to HTML

To display software code in a browser as what it is supposed to be, you need to do encoding according to the HTML standard. Example, to display a "<" (less than sign), it has to be written as "&lt;".

A CGI program is written to help my friend to put his code in the blog. BTW, I used to script this interactively in a Tcl shell and now I don't have to do that anymore :-)

The following tools and environment are used:

The bulk of the work is done by this Tcl procedure '::html::html_entities' which it does a 'string map' dictionary mapping from special characters to their entities

    variable entities {
        \xa0 &nbsp; \xa1 &iexcl; \xa2 &cent; \xa3 &pound; \xa4 &curren;
        \xa5 &yen; \xa6 &brvbar; \xa7 &sect; \xa8 &uml; \xa9 &copy;
        \xaa &ordf; \xab &laquo; \xac &not; \xad &shy; \xae &reg;
        \xaf &macr; \xb0 &deg; \xb1 &plusmn; \xb2 &sup2; \xb3 &sup3;
        \xb4 &acute; \xb5 &micro; \xb6 &para; \xb7 &middot; \xb8 &cedil;
        \xb9 &sup1; \xba &ordm; \xbb &raquo; \xbc &frac14; \xbd &frac12;
        \xbe &frac34; \xbf &iquest; \xc0 &Agrave; \xc1 &Aacute; \xc2 &Acirc;
        \xc3 &Atilde; \xc4 &Auml; \xc5 &Aring; \xc6 &AElig; \xc7 &Ccedil;
        \xc8 &Egrave; \xc9 &Eacute; \xca &Ecirc; \xcb &Euml; \xcc &Igrave;
        \xcd &Iacute; \xce &Icirc; \xcf &Iuml; \xd0 &ETH; \xd1 &Ntilde;
        \xd2 &Ograve; \xd3 &Oacute; \xd4 &Ocirc; \xd5 &Otilde; \xd6 &Ouml;
        \xd7 &times; \xd8 &Oslash; \xd9 &Ugrave; \xda &Uacute; \xdb &Ucirc;
        \xdc &Uuml; \xdd &Yacute; \xde &THORN; \xdf &szlig; \xe0 &agrave;
        \xe1 &aacute; \xe2 &acirc; \xe3 &atilde; \xe4 &auml; \xe5 &aring;
        \xe6 &aelig; \xe7 &ccedil; \xe8 &egrave; \xe9 &eacute; \xea &ecirc;
        \xeb &euml; \xec &igrave; \xed &iacute; \xee &icirc; \xef &iuml;
        \xf0 &eth; \xf1 &ntilde; \xf2 &ograve; \xf3 &oacute; \xf4 &ocirc;
        \xf5 &otilde; \xf6 &ouml; \xf7 &divide; \xf8 &oslash; \xf9 &ugrave;
        \xfa &uacute; \xfb &ucirc; \xfc &uuml; \xfd &yacute; \xfe &thorn;
        \xff &yuml; \u192 &fnof; \u391 &Alpha; \u392 &Beta; \u393 &Gamma;
        \u394 &Delta; \u395 &Epsilon; \u396 &Zeta; \u397 &Eta; \u398 &Theta;
        \u399 &Iota; \u39A &Kappa; \u39B &Lambda; \u39C &Mu; \u39D &Nu;
        \u39E &Xi; \u39F &Omicron; \u3A0 &Pi; \u3A1 &Rho; \u3A3 &Sigma;
        \u3A4 &Tau; \u3A5 &Upsilon; \u3A6 &Phi; \u3A7 &Chi; \u3A8 &Psi;
        \u3A9 &Omega; \u3B1 &alpha; \u3B2 &beta; \u3B3 &gamma; \u3B4 &delta;
        \u3B5 &epsilon; \u3B6 &zeta; \u3B7 &eta; \u3B8 &theta; \u3B9 &iota;
        \u3BA &kappa; \u3BB &lambda; \u3BC &mu; \u3BD &nu; \u3BE &xi;
        \u3BF &omicron; \u3C0 &pi; \u3C1 &rho; \u3C2 &sigmaf; \u3C3 &sigma;
        \u3C4 &tau; \u3C5 &upsilon; \u3C6 &phi; \u3C7 &chi; \u3C8 &psi;
        \u3C9 &omega; \u3D1 &thetasym; \u3D2 &upsih; \u3D6 &piv;
        \u2022 &bull; \u2026 &hellip; \u2032 &prime; \u2033 &Prime;
        \u203E &oline; \u2044 &frasl; \u2118 &weierp; \u2111 &image;
        \u211C &real; \u2122 &trade; \u2135 &alefsym; \u2190 &larr;
        \u2191 &uarr; \u2192 &rarr; \u2193 &darr; \u2194 &harr; \u21B5 &crarr;
        \u21D0 &lArr; \u21D1 &uArr; \u21D2 &rArr; \u21D3 &dArr; \u21D4 &hArr;
        \u2200 &forall; \u2202 &part; \u2203 &exist; \u2205 &empty;
        \u2207 &nabla; \u2208 &isin; \u2209 &notin; \u220B &ni; \u220F &prod;
        \u2211 &sum; \u2212 &minus; \u2217 &lowast; \u221A &radic;
        \u221D &prop; \u221E &infin; \u2220 &ang; \u2227 &and; \u2228 &or;
        \u2229 &cap; \u222A &cup; \u222B &int; \u2234 &there4; \u223C &sim;
        \u2245 &cong; \u2248 &asymp; \u2260 &ne; \u2261 &equiv; \u2264 &le;
        \u2265 &ge; \u2282 &sub; \u2283 &sup; \u2284 &nsub; \u2286 &sube;
        \u2287 &supe; \u2295 &oplus; \u2297 &otimes; \u22A5 &perp;
        \u22C5 &sdot; \u2308 &lceil; \u2309 &rceil; \u230A &lfloor;
        \u230B &rfloor; \u2329 &lang; \u232A &rang; \u25CA &loz;
        \u2660 &spades; \u2663 &clubs; \u2665 &hearts; \u2666 &diams;
        \x22 &quot; \x26 &amp; \x3C &lt; \x3E &gt; \u152 &OElig;
        \u153 &oelig; \u160 &Scaron; \u161 &scaron; \u178 &Yuml;
        \u2C6 &circ; \u2DC &tilde; \u2002 &ensp; \u2003 &emsp; \u2009 &thinsp;
        \u200C &zwnj; \u200D &zwj; \u200E &lrm; \u200F &rlm; \u2013 &ndash;
        \u2014 &mdash; \u2018 &lsquo; \u2019 &rsquo; \u201A &sbquo;
        \u201C &ldquo; \u201D &rdquo; \u201E &bdquo; \u2020 &dagger;
        \u2021 &Dagger; \u2030 &permil; \u2039 &lsaquo; \u203A &rsaquo;
        \u20AC &euro;

# ::html::html_entities --
#       Replaces all special characters in the text with their
#       entities.
# Arguments:
#       s       The near-HTML text
# Results:
#       The text with entities in place of specials characters.

proc ::html::html_entities {s} {
    variable entities
    return [string map $entities $s]

Here is the CGI program:

#! /usr/sfw/bin/tclsh

package require cgi
package require http
package require html

set title {Converting Code to HTML}

set htmlHeader "

set htmlForm "
<form method=post action=$env(REQUEST_URI)>
<input type=submit name=submit value=\"Convert to Raw HTML\"><br>
<textarea name=code cols=80 rows=10>

set htmlFooter {

puts "Content-type: text/html\n"
puts $htmlHeader
puts $htmlForm
if { $env(REQUEST_METHOD) == "POST" } {
        set code {}
        if { [catch {cgi_import code} code] } {
                puts "Error in $code"
                puts $htmlFooter
        puts "<hr>"
        puts "<h1>Raw HTML</h1>"
        puts "<pre>[string map {& &amp;} [::html::html_entities $code]</pre>]"
        puts "<hr>"
        puts "<h1>Rendered HTML</h1>"
        puts "<pre>"
        puts [::html::html_entities $code]
        puts "<pre>"
puts $htmlFooter

Screen dumps of the CGI program in action

Labels: , ,

Tuesday, September 11, 2007

How to Delete "Dot Dot Backslash" Files

How to remove files like this '..\logs\access-2007-09-01' in a UNIX environment. They looked like files residing inside a directory if you are living in Windows environment. In UNIX, any files that starts with a dot (.) is considered a hidden file. You need to 'ls -a' to list them out 'cos they won't show up in 'ls'. It is definitely a challenge to get rid of them.

Let's create some of these files to try things out.

$ for i in 01 02 03 04 05 06 07 08 09 10 11 12
  touch '..\logs\access-2007-09-'$i

$ ls

$ ls -a
.                          ..\logs\access-2007-09-06
..                         ..\logs\access-2007-09-07
..\logs\access-2007-09-01  ..\logs\access-2007-09-08
..\logs\access-2007-09-02  ..\logs\access-2007-09-09
..\logs\access-2007-09-03  ..\logs\access-2007-09-10
..\logs\access-2007-09-04  ..\logs\access-2007-09-11
..\logs\access-2007-09-05  ..\logs\access-2007-09-12

$ rm ..\logs*
..logs*: No such file or directory

You will realise that you are not able to remove them using 'rm' command. However, you can remove them based on their corresponding i-node number. In 'find', you can specify the i-node number with '-inum'. To remove it, simply include '-exec rm' in 'find'. The down side is you need to do it one at a time, or feed the i-node in a loop.

$ ls -ai1
     41286 .
        25 ..
     41287 ..\logs\access-2007-09-01
     41288 ..\logs\access-2007-09-02
     41289 ..\logs\access-2007-09-03
     41290 ..\logs\access-2007-09-04
     41291 ..\logs\access-2007-09-05
     41292 ..\logs\access-2007-09-06
     41293 ..\logs\access-2007-09-07
     41294 ..\logs\access-2007-09-08
     41295 ..\logs\access-2007-09-09
     41296 ..\logs\access-2007-09-10
     41297 ..\logs\access-2007-09-11
     41298 ..\logs\access-2007-09-12

$ find . -inum 41287 -exec /bin/rm -i {} \;
rm: remove ./..\logs\access-2007-09-01 (yes/no)?

$ for i in `ls -ai1 | awk '/logs/ {print $1}'`
  find . -inum $i -exec rm -i {} \;

So, can we use 'find' to locate these files and have them removed in a one-liner? The trick is to be able to pass the pattern (\\, two backslashes) to 'find' so that the escape meaning of a '\\' will be interpreted as '\'. If you use doube quote (") syntax in 'find', you will have to have four backslashes to represent a backslash inside. If you are using single quote syntax, you will need two backslashes. Make sure you include '-i' in 'rm' to prompt you before removal, unless you are sure what are doing.

$ find . -name "..\logs\*"

$ find . -name "..\\logs\\*"

$ find . -name "..\\\\logs\\\\*"

$ find . -name '..\\logs\\*'

$ find . -name '..\\logs\\*' -exec /bin/rm -i {} \;
rm: remove ./..\logs\access-2007-09-01 (yes/no)?
rm: remove ./..\logs\access-2007-09-02 (yes/no)?
rm: remove ./..\logs\access-2007-09-03 (yes/no)?
rm: remove ./..\logs\access-2007-09-04 (yes/no)?
rm: remove ./..\logs\access-2007-09-05 (yes/no)?
rm: remove ./..\logs\access-2007-09-06 (yes/no)?
rm: remove ./..\logs\access-2007-09-07 (yes/no)?
rm: remove ./..\logs\access-2007-09-08 (yes/no)?
rm: remove ./..\logs\access-2007-09-09 (yes/no)?
rm: remove ./..\logs\access-2007-09-10 (yes/no)?
rm: remove ./..\logs\access-2007-09-11 (yes/no)?
rm: remove ./..\logs\access-2007-09-12 (yes/no)?