------art_3878_16493755.1189948769539
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Hello,

Had some fun with this one :). Basically, my approach was to download the
.csv database file and use that file to convert from IP Country code. The
program reads this file each time it processes an individual lookup, with no
precomputations required.

Initially I coded up a linear search (SLOW!) and a binary search that read
the entire file into an array (somewhat faster). But the final "binary seek"
approach is more efficient - it uses IO.seek to only read the specific lines
that it needs, thus providing a good balance of CPU/Memory/IO. Binary seek
does this by taking advantage of the fact that IP ranges in the file are in
numerical order. I was planning to also code up a file that uses a web
service to do the conversion, but I doubt that would win any speed contests
:).

Anyway, the algorithm is a simple modification of a standard binary search:

def binary_seek(ip_addr_num)
   low  
   high  ile.size(Filename)
   fp  ile.open(Filename)

   # Find first line of real data and set "low" placeholder accordingly
   line  p.gets
   while line.strip.size 0 or line[0].chr "#"
    line  p.gets
    low  ow + line.size
   end

   # Then find the corresponding the IP Range, if any
   while (low < igh)
       mid  low + high) / 2
       fp.seek(mid, IO::SEEK_SET)

       line  p.gets # read once to find the next line
       line  p.gets # read again to get the next full line
       from, to, country_code  arse_line(line)

       if (from nil or from > ip_addr_num) # Safety check
           high  id - 1
       elsif (to < ip_addr_num)
           low  id + 1
       else
           fp.close
           return "Binary Seek Search: #{country_code}"
       end
   end

   fp.close
   return "No Country Found"
end

A hard-coded constant points to the look up file:

Filename  IpToCountry.csv" # IP to Country Code database file


And utility methods are provided to make the core algorithm easier to
follow:

# Convert an IP (V4) address (as string) to a decimal number
# Example from file:
# 1.2.3.4   + (3 * 256) + (2 * 256 * 256) + (1 * 256 * 256 * 256)
# is 4 + 768 + 13,1072 + 16,777,216  6,909,060
def convert_ip_str_to_num(ip_addr_str)
  ip_addr  p_addr_str.split(".")
  ip_addr_num  p_addr[0].to_i * 256 ** 3 +
                ip_addr[1].to_i * 256 ** 2 +
                ip_addr[2].to_i * 256 ** 1 +
                ip_addr[3].to_i
  return ip_addr_num
end

# Parse an IP range field of the IP/Country DB file
def parse_line(line)
  line_parsed  ine.split(',')

  # Validate to handle comments and unexpected data
  if line_parsed ! il and line_parsed.size > 
    from  ine_parsed[0].tr('"', '').to_i
    to  ine_parsed[1].tr('"', '').to_i
    country_code  ine_parsed[4]
  end

  return from, to, country_code
end

Finally, the program simply iterates over a list of input IP addresses:

for ip in ARGV
  puts binary_seek(convert_ip_str_to_num(ip))
end

Here is a test run on a Pentium 4 2.4 Ghz Desktop with 512 MB RAM, using one
of the test cases from the initial email chain:

justin@marketgarden:~/Desktop/139_IP_to_Country$ time ruby IP_to_Country.rb
68.97.89.187 84.191.4.10 80.79.64.128 210.185.128.123 202.10.4.222
192.189.119.1
Binary Seek Search: "US"
Binary Seek Search: "DE"
Binary Seek Search: "RU"
Binary Seek Search: "JP"
Binary Seek Search: "AU"
Binary Seek Search: "EU"

real    0m0.020s
user    0m0.016s
sys     0m0.004s

A pastie is available here: http://pastie.caboo.se/97562
This file contains Binary Seek as well as linear and binary search
implementations.
Thanks,

Justin


On 9/14/07, Ruby Quiz <james / grayproductions.net > wrote:
>
> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this quiz
> until
> 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps
> everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz
> message,
> if you can.
>
>
> --------------------
>
> This week's Ruby Quiz is to write a simple utility.  Your program should
> accept
> an IP address as a command-line argument and print out the two letter code
> for
> the country that IP is assigned in.  You can find a database for the
> matching
> at:
>
>          http://software77.net/cgi-bin/ip-country/geo-ip.pl
>
> To keep the problem interesting though, let's write our programs with a
> focus on
> speed and memory efficiency.
>
>         $ time ruby ip_to_country.rb 68.97.89.187
>         US
>
>         real    0m0.314s
>         user    0m0.259s
>         sys     0m0.053s
>
>

------art_3878_16493755.1189948769539--