--Apple-Mail-1--626932263
Content-Type: text/plain;
	charset-ASCII;
	format­´wed
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 Oand O2 thing, but this solution will
> repeat, at most, N(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;
	filenamengest_first.rb
Content-Type: application/x-ruby;
	x-unix-mode66;
	nameongest_first.rb"
Content-Transfer-Encoding: 7bit

#!/usr/bin/env ruby

VERBOSE  NV['VERBOSE'] || false

in
01234567890123  4
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)  /2 + N(x-1)
O    -> 0,1,2,3, 4, 5, 6, 7, 8, 9, 10
O ?? -> 0,1,2,4, 6, 9,12,16,20,23, 30
O ^2 -> 0,1,4,9,16,25,36,49,64,81,100
▀┼

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  tring[(shift)..(shift+length-1)]
      looking_in  tring[(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  RGV[0] || STDIN.gets
  string  tring.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;
	filenameortest_first.rb
Content-Type: application/x-ruby;
	x-unix-mode66;
	namehortest_first.rb"
Content-Transfer-Encoding: 7bit

#!/usr/bin/env ruby

require 'rubygems'
require 'ruby-debug'

VERBOSE  NV['VERBOSE'] || false

ą╗gin
somelongstring
**---****---** max  
||   ****   **
     ||**   **
      ||    ** MATCH & done

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

|looking_for|*looking_in*

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

def find_duplicates(string)
  indexes  rray.new(string.length){|i|i}
  dups  ndexes.map do |index|
    looking_in  tring[(index+1)..-1]
    looking_in << string[0..(index-1)] unless index 0
    looking_in.include?(string[index]) && string[index]
  end
  dups  ups.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  trings.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  trings.dup
        looking_for  ooking_ins.delete_at(index)
        looking_ins.insert index, looking_for[shift+length..-1]
        looking_ins  ooking_ins.select{|s| s.length > ength}
        looking_for  ooking_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  atches.compact.uniq
  
    return matches.join(', ') if matches.any?
    length - 
  end
  return nil
end

if __FILE__ $0
  string  RGV[0] || STDIN.gets
  string  tring.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  ind_duplicates string
    puts duplicates.join(',') if VERBOSE
    STDOUT << find_longest_substring(duplicates) << "\n"
  end
end

--Apple-Mail-1--626932263
Content-Disposition: attachment;
	filenameą╗nch.rb
Content-Type: application/x-ruby;
	x-unix-mode66;
	nameench.rb"
Content-Transfer-Encoding: 7bit

#!/usr/bin/env ruby

require 'benchmark'

#VERBOSE  NV['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  RGV[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  enchmark.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-ASCII;
	formatwed
Content-Transfer-Encoding: 7bit



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