------=_Part_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 = 0
   high = File.size(Filename)
   fp = File.open(Filename)

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

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

       line = fp.gets # read once to find the next line
       line = fp.gets # read again to get the next full line
       from, to, country_code = parse_line(line)

       if (from == nil or from > ip_addr_num) # Safety check
           high = mid - 1
       elsif (to < ip_addr_num)
           low = mid + 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 = 4 + (3 * 256) + (2 * 256 * 256) + (1 * 256 * 256 * 256)
# is 4 + 768 + 13,1072 + 16,777,216 = 16,909,060
def convert_ip_str_to_num(ip_addr_str)
  ip_addr = ip_addr_str.split(".")
  ip_addr_num = ip_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 = line.split(',')

  # Validate to handle comments and unexpected data
  if line_parsed != nil and line_parsed.size >= 5
    from = line_parsed[0].tr('"', '').to_i
    to = line_parsed[1].tr('"', '').to_i
    country_code = line_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
>
>

------=_Part_3878_16493755.1189948769539--