Saturday, November 17, 2012

[funpost] Powershell : Wallpaper Grabber

I recently discovered that I have a hobby compulsion for downloading wallpapers. I have a pretty decent collection of wallpapers, and I like browsing through them every once in a while.

The way I mainly collect wallpapers is by torrents. If all options fail, then go to any website that hosts the wallpapers and download them one at a time. I have a personal record of downloading almost 700 wallpapers at stretch. It is a tedious boring job stuck in a "right click-open in new tab - right click - save picture as".

Recently I had to download wallpaper of a particular artist, and I looked around for a torrent only to find stale links. So I was finally left with the option of downloading the papers manually.

Now people who know me, know that I'm one lazy ass. So entering the loop again was something I didn't want to do.

Recently I've been having an "affair" with Powershell, and it seemed like an opportunity to .. well further.. you know..

Disclaimer :
    This is a written by a lazy ass, to download wall papers from a website and not to saving the world. So the script is dirty and fragile. It targets a particular scenario. For me that is how it is suppose to be. The spirit of scripting for me is the quickest way of getting things done. So the script doesn't have any error checking and even if something is slightly different it'll fail.

Running A Powershell Script :
     If you have Windows 7 or Windows 8, Powershell is installed by default. For earlier versions of Windows, you need to download and install Powershell.

    To run Powershell, start a command prompt, and execute command "powershell" (without quotes).

    Copy the script to a file and save the script with a .ps1 extension.

    In Powershell prompt, execute "Set-ExecutionPolicy -ExecutionPolicy unrestricted". This is to allow us to execute scripts.

    The code downloads the wallpaper from the site xtremewalls.com, and places it in a folder created with the name of the artist in the same folder. I would search for the artist in the site, and grab the url and provide as input. This will retrieve images in the current page only. we have to rerun the script for page2. (as I said, dirty way of doing it but hey it works.. most of the times..)

 <# download wall paper from : http://xtremewalls.com/  
   They have a good collection of paper, good organization  
   http://xtremewalls.com/category/hollywoodf/<nameOfArtist>/<pageNumber>  
   http://xtremewalls.com/category/hollywoodf/ashleesimpson/1  
   Each page contains a number of links, with varying resolution. we need to   
   parse the links for highest resolution, then turn over to next page.  
   cumbersome, but hey, gatta do what ya gat ta doo  
 #>  
 # get link to fisrt page  
 if($args.Count -lt 1)  
 {  
   Write-Host -ForegroundColor Red "Invalid syntax"  
   Write-Host -ForegroundColor Red "<scriptname> <urlToFirstPage>"  
   Write-Host -ForegroundColor Red "eg: <scriptname> http://xtremewalls.com/category/hollywoodf/ashleesimpson/1"  
   return 1  
 }  
 $url = $args[0]  
 # now extract artist name and category  
 $tind = $url.LastIndexOf("/")  
 $url.Substring(0,$tind)  
 $tstr = $url.Substring(0,$tind) # -1 to remove /  
 $tind = $tstr.LastIndexOf("/")  
 $artist=$tstr.Substring($tind+1,$tstr.length-1-$tind)  
 $tstr = $tstr.Substring(0,$tind)  
 $tind = $tstr.LastIndexOf("/")  
 $category=$tstr.Substring($tind+1,$tstr.length-1-$tind)  
 # save path  
 $saveloc=Get-Location  
 $saveloc = Join-Path $saveloc -ChildPath $artist  
 if(Test-Path $saveloc)  
 {  
   "save Loc exists"  
 }  
 else  
 {  
   mkdir $saveloc  
 }  
 # get webpage  
 $wc = New-Object net.webclient  
 $webpage=$wc.DownloadString($url)  
 # split the page into lines  
 $lineArray = $webpage.Split("`r`t")  
 $lineArray = $lineArray | Sort-Object -Unique  
 # prepare linkstring used for matching  
 $matchLink = "http://xtremewalls.com/wallpaper/"  
 $matchLink = [string]::concat($matchLink, $category);  
 $matchLink = [string]::Concat($matchLink, "/");  
 $matchLink = [string]::Concat($matchLink, $artist);  
 $matchGroupLink = $matchLink;  
 $matchLink = [string]::Concat($matchLink, "/\d*/\d*x\d*");  
 $matchGroupLink = [string]::Concat($matchGroupLink, "/\d*");  
 # extract links  
 $linkArray = [regex]::Matches($lineArray, $matchLink)  
 # we have links. Now group links by number  
 $linkgroupArray = [regex]::Matches($lineArray, $matchGroupLink)  
 $linkgroupArray = $linkgroupArray | Select-Object -Unique  
 # Now for each group link, get the link with highest resolution  
 for($i=0; $i -lt $linkgroupArray.Length; $i++)  
 {  
   $grouplink = $linkgroupArray[$i];  
   $allResolutionLinks = $linkArray -match $grouplink  
   $allResolutionLinks = $allResolutionLinks | Sort-Object -Unique  
   # get the link to highest resolution  
   $hires=0  
   $link  
   for($j=0; $j -lt $allresolutionLinks.Length; $j++)  
   {  
     $res = [regex]::Matches($allResolutionLinks[$j], "\d+$");  
     $res = $res[0].Value  
     if([int]$hires -le [int]$res)  
     {  
       $hires=$res  
       $link = $allResolutionLinks[$j].Value  
     }  
   }  
   # Now that we have the link, lets download  
   $jpgPageString = $wc.DownloadString($link.ToString())  
   $jpgPageLines = $jpgPageString.Split("`r`n")  
   $jpgLines = $jpgPageLines -match ".jpg"  
   $jpgLinks = [regex]::matches( $jpglines, "img src=(?!.*img.*).*$category/$artist.*jpg")  
   # blindly take the first guy  
   $jpgstr = $jpgLinks[0].ToString()  
   $linkext = $jpgstr.Substring(9, $jpgstr.Length-9)  
   # download string  
   $dstr = [string]::Concat($link, "/")  
   $dstr = [string]::Concat($dstr, $linkext)  
   $dstr  
   #extract filename  
   $dind = $dstr.LastIndexOf("/")  
   $filename = $dstr.substring($dind+1,$dstr.Length-$dind-1)  
   $savepath = Join-Path $saveloc -ChildPath $filename  
   $savepath  
   # FINALLY DOWNLOAD THE DAMN PIC #  
   $wc.DownloadFile($dstr, $savepath.ToString())  
 }  

Thursday, April 26, 2012

Fibonacci Numbers - Golden Ratio (float)

In the previous post we discovered the relation between fibonacci numbers and golden ratio. This time, we attempt to calculate nth fibonacci number using the golden ratio.


/****************************************************************
 Program to generate nth Fibonacci number using Golden Ratio
 
 Theory: From Cormen
  fibonacci numbers are related to the golden ratio and 
  to its conjugate, which are the two roots of the
  equation
   x^2 = x + 1
  The roots are 
   r1=(1+sqrt(5))/2 = 1.61803... and
   r2=(1-sqrt(5))/2 = 0.61803...
   
  For nth Fibonacci number, we have
  F(n) = ((r1)^n - (r2)^n)/sqrt(5)
  
  Since r2<1, the value of r2 diminishes as the power
  applied on r2 increases. By induction, we can prove
  r2/sqrt(5) < 1/sqrt(5) < 1/2
  
  So finally we have 
   F(n) = floor(((r1)^n)/sqrt(5) + 0.5)
   
  Our approximation
   F(n) = floor((r1)^n)/sqrt(5)  
  works well in practice
   
 In our program we will use the same golden ratio to produce
 nth fibonacci number. 
 
 The limit when using the long data type for holding the 
 fibonacci result is 46th term.

 With float this becomes more interesting. 
 
***************************************************************/

#include <stdio.h>
#include <math.h>

const double sqrtOf5 = 2.2360679774997896964091736687313; //sqrt(5)
const double phi = 1.6180339887498948482045868343656; //(double)(sqrtOf5+1)/2; // we precalculate the root

int main(int argc, char* argv[])
{
 int n;      // out input value
 int i;
 
 double fibnum, fibfloor;
 double fibres;
 
 // get input from user
 printf("Program to print nth number of Fibonacci Series\n");
 printf("Enter n:");
 scanf("%d", &n);
 
 if (n <= 0)
 {
  printf("Invalid value of n. Please enter value > 0\n");
  goto exit;
 }

 printf("The nth Fibonacci Number is : ");
 
 fibnum = (pow(phi, n))/sqrtOf5;
 fibfloor = floor(fibnum);
 fibres = (fibnum - fibfloor)>0.5? ceil(fibnum):fibfloor; // approximate to nearest num
  
 printf("%.0f \n", fibres);
 
exit:
 printf("Exit from Program\n");
 
 return 0;
}

/***************************************************************
output:
E:\VSProjs\blog>2c_Fibonacci_nth_float.exe
Program to print nth number of Fibonacci Series
Enter n:76
The nth Fibonacci Number is : 3416454622906715
Exit from Program

E:\VSProjs\blog>2c_Fibonacci_nth_float.exe
Program to print nth number of Fibonacci Series
Enter n:77
The nth Fibonacci Number is : 5527939700884771
Exit from Program

E:\VSProjs\blog>2c_Fibonacci_nth_float.exe
Program to print nth number of Fibonacci Series
Enter n:78
The nth Fibonacci Number is : 8944394323791488
Exit from Program

E:\VSProjs\blog>2c_Fibonacci_nth_float.exe
Program to print nth number of Fibonacci Series
Enter n:79
The nth Fibonacci Number is : 14472334024676260
Exit from Program

PS E:\VSProjs\blog> .\2c_Fibonacci_nth_float.exe
Program to print nth number of Fibonacci Series
Enter n:82
The nth Fibonacci Number is : 61305790721611752
Exit from Program

PS E:\VSProjs\blog> .\2c_Fibonacci_nth_float.exe
Program to print nth number of Fibonacci Series
Enter n:83
The nth Fibonacci Number is : 99194853094755776
Exit from Program

PS E:\VSProjs\blog> .\2c_Fibonacci_nth_float.exe
Program to print nth number of Fibonacci Series
Enter n:84
The nth Fibonacci Number is : 160500643816367550
Exit from Program
***************************************************************/

Notes :
 We see that the fib(79) != fib(78) + fib (77). The expected
answer is : 14472334024676259. If we observe closely, the value
has been approximated (i.e the last two digits 59 is approxmiated
to 60. 

    But if we continue further, we get the right answer for 82
and 83, and again it flips at 84. 

 This is interesting. Everybody must already be aware that the 
way floating points are represented in computers are not the same as 
an integer. 
 
 So we have hit the limit for float. After this we lose precision
and zeros are attached. 

Representation of floating number
        The way floating numbers are represented in computers are by 
splitting the number into three parts. 
     - precision
     - exponent
     - sign
 (essentially as (sign)*(Mantissa or precision)*base^exponent
 eg. 13456*10^-2 represents 134.56)
 
 The IEEE 754 standard specifies a binary32(there is also a 
decimal32 format) as having:
  Sign bit: 1 bit
  Exponent width: 8 bits
  Significand precision: 24 (23 explicitly stored)
  
 s eeeeeeee fffffffffffffffffffffff
 
 With this format, we use 23 bits to store the number in binary
format. What we need to take a moment to realize is that the 
number is stored in binary format. That means the number of digits
of precision (when converted to decimal) vary. 
 
 eg. consider we have 4 bits to represent precision. we can 
represent numbers 0000 to 1111 in binary. Translated to decimal its
0 to 16. So the precision supported is 1 to 2. 
 
 Single precision number gives from 6 to 9 significant 
decimal digits precision. For double precision numbers it is
from 15 - 17 significant decimal digits. 
 
 The wikipedia article dedicated to this concept gives better
 insight into the format along with representing NaN, 
 Normalization, decimal32, binary32 etc.
 
Bottom Line is when using float or double, its all about precision 
and not the range of numbers you can represent. We can try and 
calculate fib(100). The value will not overflow like integer types, 
but we will not get the correct answer. 

For a problem where the outcome is dependent on the precision, we
need to be careful when choosing the floating number datatype. 

Fibonacci Numbers

A program to generate Fibonacci numbers. This again is an elementary level program.

 

 
/***************************************************************
 Program to print the first n fibonacci series
 n is taken as input
 0 1 1 2 3 5 8 ...
***************************************************************/

#include <stdio.h>

int main(int argc, char* argv[])
{
 int n; // input
 int fib1, fib2, fib3;  
 int i;
 
 // get input from user
 printf("Program to print first n Fibonacci Series\n");
 printf("Enter n:");
 scanf("%d", &n);
 
 if (n <= 0)
 {
  printf("Invalid value of n. Please enter value > 0\n");
  goto exit;
 }
 
 // print fibo series
 fib1=0; fib2=0; fib3=1;
 
 printf("The %d fibonacci numbers are \n", n);
 for (i=0; i<n; i++)
 {
  printf("%d ", fib1);
  fib2=fib3; fib3=fib1;
  fib1 = fib2 + fib3;
 }
 printf("\n");
 
exit:
 printf("Exit from Program\n");
 
 return 0;
}

/***************************************************************
Output:

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:-1
Invalid value of n. Please enter value > 0
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:0
Invalid value of n. Please enter value > 0
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:1
The 1 fibonacci numbers are
0
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:2
The 2 fibonacci numbers are
0 1
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:3
The 3 fibonacci numbers are
0 1 1
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:5
The 5 fibonacci numbers are
0 1 1 2 3
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:10
The 10 fibonacci numbers are
0 1 1 2 3 5 8 13 21 34
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:20
The 20 fibonacci numbers are
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Exit from Program

E:\VSProjs\blog>

***************************************************************/

 
Notes : <source http://en.wikipedia.org/wiki/Fibonacci_number - its a complete copy paste job>
 
 
         In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence : 0 1 1 2 3 5 8 13 … Obtained by the relation F(n) = F(n-1) + F(n-2), the seed values used are F(0)=0, F(1)=1
 
                Fibonacci considers the growth of an idealized (biologically unrealistic) rabbit population, assuming that: a newly born pair of rabbits, one male, one female, are put in a field; rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits; rabbits never die and a mating pair always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was: how many pairs will there be in one year?
  • At the end of the first month, they mate, but there is still only 1 pair.
  • At the end of the second month the female produces a new pair, so now there are 2 pairs of rabbits in the field.
  • At the end of the third month, the original female produces a second pair, making 3 pairs in all in the field.
  • At the end of the fourth month, the original female has produced yet another new pair, the female born two months ago produces her first pair also, making 5 pairs.
         At the end of the nth month, the number of pairs of rabbits is equal to the number of new pairs (which is the number of pairs in month n − 2) plus the number of pairs alive last month (n − 1). This is the nth Fibonacci number.

 
        On similar lines we have "negafibonacci" numbers, satisfying the relation
F_{-n} = (-1)^{n+1} F_n. \,

 
Thus the fibonacci series :
F−8F−7F−6F−5F−4F−3F−2F−1F0F1F2F3F4F5F6F7F8
−2113−85−32−1101123581321


Relation with Golden Ratio

The Fibonacci numbers have a closed-form solution. It has become known as Binet's formula.


F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}
where
\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\cdots\,
is the golden ratio and
\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\cdots
for the purpose of computation we use the following form :
F_n=\bigg\lfloor\frac{\varphi^n}{\sqrt 5} + \frac{1}{2}\bigg\rfloor,\ n \geq 0.

  
  

Recognizing Fibonacci Numbers

      On similar lines we can use the following formula to check if a given number is a fibonacci number :
F\bigg(\bigg\lfloor\log_\varphi\bigg(z\cdot\sqrt{5}+\frac{1}{2}\bigg)\bigg\rfloor\bigg)=z,

 
or alternatively
         a positive integer z is a Fibonacci number if and only if one of 5z^2+4 or 5z^2-4 is a perfect square.

  
  

Applications

  1. The Fibonacci numbers are important in the computational run-time analysis of Euclid's algorithm to determine the greatest common divisor of two integers: the worst case input for this algorithm is a pair of consecutive Fibonacci numbers.
     
     
  2. The Fibonacci numbers are also an example of a complete sequence. This means that every positive integer can be written as a sum of Fibonacci numbers, where any one number is used once at most. Specifically, every positive integer can be written in a unique way as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. This is known as Zeckendorf's theorem, and a sum of Fibonacci numbers that satisfies these conditions is called a Zeckendorf representation. The Zeckendorf representation of a number can be used to derive its Fibonacci coding.
     
     
  3. Fibonacci numbers are used by some pseudorandom number generators.
  4. Fibonacci numbers are used in a polyphase version of the merge sort algorithm in which an unsorted list is divided into two lists whose lengths correspond to sequential Fibonacci numbers
     
     
  5. The Fibonacci cube is an undirected graph with a Fibonacci number of nodes that has been proposed as a network topology for parallel computing.
     
     
  6. Fibonacci numbers arise in the analysis of the Fibonacci heap data structure.
     
     
  7. The Fibonacci number series is used for optional lossy compression in the IFF 8SVX audio file format used on Amiga computers. The number series compands the original audio wave similar to logarithmic methods such as ยต-law
Apart from this there are a bunch of properties about fibonacci numbers. I found This to be the most interesting one:

 
The Fibonacci numbers can be found in different ways in the sequence of binary strings.
 
  • The number of binary strings of length n without consecutive 1s is the Fibonacci number Fn+2. For example, out of the 16 binary strings of length 4, there are F6 = 8 without consecutive 1s – they are 0000, 0100, 0010, 0001, 0101, 1000, 1010 and 1001. By symmetry, the number of strings of length n without consecutive 0s is also Fn+2.
  • The number of binary strings of length n without an odd number of consecutive 1s is the Fibonacci number Fn+1. For example, out of the 16 binary strings of length 4, there are F5 = 5 without an odd number of consecutive 1s – they are 0000, 0011, 0110, 1100, 1111.
  • The number of binary strings of length n without an even number of consecutive 0s or 1s is 2Fn. For example, out of the 16 binary strings of length 4, there are 2F4 = 6 without an even number of consecutive 0s or 1s – they are 0001, 1000, 1110, 0111, 0101, 1010.
There are more topics on observing fibonacci patterns in Nature, combinatorial identities etc. The brave can march ahead to explore.

Saturday, April 21, 2012

yatb!! (yet another technical blog)

I am an Engineer. And like all engineers I believe engineering is a craft. The only way to become good at it is to subject yourself to an endless cycle building and rebuilding things. So after months of procrastination I finally decided to dedicate a part of my time to coding and learning. As I started, I realized the amount of effort it takes. So I decided to share it out to the world, in case somebody finds it useful.

There was another thing that got me off my butt to start working. A few months ago I saw this ted talk :
We are makers, by Dale Dougherty. (http://www.ted.com/talks/dale_dougherty_we_are_makers.html).
It was a fascinating talk, and I agree with him. If we look at history, some of the most coolest stuff are built not in a high tech lab, but in the garage of ordinary people. You don't need to be a certified genius to build cool things. 

What I mean to say is we love to build things, make things. And there is a maker in all of us. All we have to do is give it a chance. Just lock away all our inhibitions and doubts for a while and let our imagination go wild. We might come up with something something interesting or something that is completely stupid and utterly useless. But that is fine. We do it because we are passionate towards our craft and we love doing it.

It was time to honor curiosity, to make an effort and go beyond the safe boundaries, to explore, discover and learn. Many times we have thought "Hey, I wonder what would happen if..." or "I wonder how this works". Well its time to work on those ideas and see how far it goes.

This will be my technical journal, to record and share what I've learnt in my journey. I'm not an expert at anything, I'm just a guy who's curious about things around him. And fiddle with things to understand it better. I might be wrong some or most times. In such cases I'd be more than happy to be corrected.

As we start on our new journey of exploration and discovery, lets us draw some inspiration from greats who have walked the path before us.

Our deepest fear is not that we are inadequate.
Our deepest fear is that we are powerful beyond measure.

It is our light, not our darkness, that most frightens us.
We ask ourselves, Who am I to be brilliant,
gorgeous, handsome, talented and fabulous?

Actually, who are you not to be?
You are a child of God.

Your playing small does not serve the world.
There is nothing enlightened about shrinking
so that other people won't feel insecure around you.
We are all meant to shine, as children do.

We were born to make manifest the glory of God within us.
It is not just in some; it is in everyone.

And, as we let our own light shine, we consciously give
other people permission to do the same.
As we are liberated from our fear,
our presence automatically liberates others.
                                             - Marianne Williamson

Twenty years from now you will be more disappointed by the things that you didn’t do than by the ones you did do. So throw off the bowlines. Sail away from the safe harbor. Catch the trade winds in your sails.
Explore. Dream. Discover.

                                              - Mark Twain

Here I go...

Saturday, April 14, 2012

Hello World

I will start off by writing the most important piece of code that I write whenever I get introduced to a new language. The "Hello World!!!" program. It is a program written by most of the programmers in the world. So yes, it is one of the simplest programs that you can write as well.

I will be using the visual studio compiler for compiling and running this program.


/***************************************************************
    Program to print Hello World to screen
***************************************************************/

#include <stdio.h>

int main(int argc, char* argv[])
{
    printf("Hello World\n");
    
    return 0;
}

/**************************************************************
Output:
E:\VSProjs\blog>1_HelloWorld.exe
Hello World
**************************************************************/