From: James Gray <james@...>
Date: 2008-01-23T01:16:02+09:00
Subject: Fwd: Please Forward: Ruby Quiz Submission

--Apple-Mail-1--626932263
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed
Content-Transfer-Encoding: 7bit

Begin forwarded message:

> From: Douglas Meyer <douglas.meyer@centro.net>
> Date: January 22, 2008 10:11:57 AM CST
> To: submission@rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
>
> Hello, could you please forward my submission, thanks!
>
> LongestFirst is my first attempt, and fastest solution.
> I'm not sure on the whole O=n and O=n^2 thing, but this solution will
> repeat, at most, N(x) = x/2 + N(x-1) times (less if a match is found).
>
> I tried to optimize it with ShortestFirst, but it turned out to run
> about 10 times slower.
>
> Also attached is Bench. If you set the GLOBALS properly, it will do a
> benchmark on all the solutions.
>
> Thanks again,
> -Doug Meyer

--Apple-Mail-1--626932263
Content-Disposition: attachment;
	filename=longest_first.rb
Content-Type: application/x-ruby;
	x-unix-mode=0666;
	name="longest_first.rb"
Content-Transfer-Encoding: 7bit

#!/usr/bin/env ruby

VERBOSE = ENV['VERBOSE'] || false

=begin
01234567890123 = 14
somelongstring
|  7  |*  7  *
| 6  |*  8   *
1|  6 |* 7   *
2 | 6  |* 6  *
| 5 |*   9   *
1| 5 |*  8   *
2 | 5 |*  7  *
 3 | 5 |* 6  *
 4  | 5 |* 5 *
|4 |*   10   *
1|4 |*   9   *
2 |4 |*   8  *
 3 |4 |*  9  *
 4  |4 |*  6 *
  5  |4 |* 5 *
  6   |4 |* 4*

 shift |looking_for|*looking_in*

20 -> 100
19 -> 90
18 -> 81
17 -> 72
16 -> 64
15 -> 56
14 -> 49
13 -> 42
12 -> 36
11 -> 30
10 -> 25
9 -> 20
8 -> 16
7 -> 12
6 -> 9
5 -> 6
4 -> 4
3 -> 2
2 -> 1
1 -> 0

N(x) = x/2 + N(x-1)
O= n   -> 0,1,2,3, 4, 5, 6, 7, 8, 9, 10
O= ??? -> 0,1,2,4, 6, 9,12,16,20,23, 30
O= n^2 -> 0,1,4,9,16,25,36,49,64,81,100
=end

def find_longest_substring(string)
  matches = []
  (string.length/2).downto(0) do |length|
    max_shift = (string.length - length*2)
    matches = (0..max_shift).map do |shift|
      looking_for = string[(shift)..(shift+length-1)]
      looking_in = string[(shift+length)..-1]
  
      puts "looking for:#{looking_for} in:#{looking_in}" if VERBOSE
      (looking_in.include?(looking_for) || nil) && looking_for
    end
    return matches.compact.uniq.join(', ') if matches.compact.any?
  end
  return nil
end

if __FILE__ == $0
  string = ARGV[0] || STDIN.gets
  string = string.match(/\s*([^\s]*)\s*/)[1]
  if string.nil? || string.empty?
    STDOUT << "Useage: #{__FILE__} some_string\n"
    STDOUT << "    or: echo some_string | #{__FILE__}\n"
  else
    STDOUT << find_longest_substring(string) << "\n"
  end
end

--Apple-Mail-1--626932263
Content-Disposition: attachment;
	filename=shortest_first.rb
Content-Type: application/x-ruby;
	x-unix-mode=0666;
	name="shortest_first.rb"
Content-Transfer-Encoding: 7bit

#!/usr/bin/env ruby

require 'rubygems'
require 'ruby-debug'

VERBOSE = ENV['VERBOSE'] || false

=begin
somelongstring
**---****---** max = 2
||   ****   **
     ||**   **
      ||    ** MATCH & done

banana
-***** max = 2
 ||*** MATCH
  ||** MATCH & done

|looking_for|*looking_in*

N(x) = x/2 + N(x-1)
O= n   -> 0,1,2,3, 4, 5, 6, 7, 8, 9, 10
O= ??? -> 0,1,2,4, 6, 9,12,16,20,23, 30
O= n^2 -> 0,1,4,9,16,25,36,49,64,81,100
=end

def find_duplicates(string)
  indexes = Array.new(string.length){|i|i}
  dups = indexes.map do |index|
    looking_in = string[(index+1)..-1]
    looking_in << string[0..(index-1)] unless index == 0
    looking_in.include?(string[index]) && string[index]
  end
  dups = dups.inject(['']) do |acc, char|
    if char
      acc.last << char
    else
      acc.push('')
    end
    acc
  end
  dups.select{|s| !s.empty?}
end
def find_longest_substring(strings)
  matches = []
  lengths = strings.map{|s|s.length}
  length = (lengths << lengths.max/2).sort.last
  while matches.empty? && length > 1

    strings.each_with_index do |string, index|
      0.upto(string.length-length) do |shift|
        looking_ins = strings.dup
        looking_for = looking_ins.delete_at(index)
        looking_ins.insert index, looking_for[shift+length..-1]
        looking_ins = looking_ins.select{|s| s.length >= length}
        looking_for = looking_for[(shift)..(shift+length-1)]
  
        looking_ins.map { |looking_in|
          puts "looking for:#{looking_for} in:#{looking_in}" if VERBOSE
          matches << ((looking_in.include?(looking_for) || nil) && looking_for)
        }
      end
    end
    matches = matches.compact.uniq
  
    return matches.join(', ') if matches.any?
    length -= 1
  end
  return nil
end

if __FILE__ == $0
  string = ARGV[0] || STDIN.gets
  string = string.match(/\s*([^\s]*)\s*/)[1]
  if string.nil? || string.empty?
    STDOUT << "Useage: #{__FILE__} some_string\n"
    STDOUT << "    or: echo some_string | #{__FILE__}\n"
  else
    duplicates = find_duplicates string
    puts duplicates.join(',') if VERBOSE
    STDOUT << find_longest_substring(duplicates) << "\n"
  end
end

--Apple-Mail-1--626932263
Content-Disposition: attachment;
	filename=bench.rb
Content-Type: application/x-ruby;
	x-unix-mode=0666;
	name="bench.rb"
Content-Transfer-Encoding: 7bit

#!/usr/bin/env ruby

require 'benchmark'

#VERBOSE = ENV['VERBOSE'] || false
FILES = [ 'longest_first.rb', 'shortest_first.rb' ]
COLLECTION = %w(0 1 2 3 4 5 6 7 8 9
  a b c d e f g h i j k l m n o p q r s t u v w x y z)[0..-1]

if __FILE__ == $0
  count = ARGV[0]
  if count.nil?
    STDOUT << "Useage: #{__FILE__} count\n"
  else

    tests = []
    count.to_i.times do
      string = ''
      60.times { string << COLLECTION.sort_by{rand}.first }
      tests << string
    end

    FILES.each do |file|
      puts file
      time = Benchmark.measure do
        tests.each do |test|

          result = %x(./#{file} #{test})
          puts "#{test} -> #{result}"

        end
      end
      puts "#{file}: #{time.real}"
    end

  end
end

--Apple-Mail-1--626932263
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed
Content-Transfer-Encoding: 7bit



--Apple-Mail-1--626932263--