Asp Forum - Re: [QUIZ] Preferable Pairs (#165

Steven Hahn

6/9/2008 10:05:00 PM

I made a couple of minor optimizations to my solution. It still will not h=
andle large inputs, but it is a little better. Thanks to Eric Ivancich, I =
removed some of the duplicate checks of potential solutions. I hope I got =
them all. Also, I added some memoization for values of solution sets, whic=
h has the downside of requiring more memory but seems to improve overall pe=
rformance.

-------------------------------------------------
require 'yaml'

#execute program by providing a file name with the data in YAML format
#Example YAML file contents:
#David: Helen Vicki Joseph
#Helen: David Vicki Joseph
#Joseph: Vicki Helen David
#Vicki: David Helen Joseph

class PairCalculator
def initialize(filename)
#read data into hash from YAML file
@pairs_hash =3D YAML::load_file(filename)
@num_people =3D @pairs_hash.length
@num_choices =3D @num_people - 1
@pair_set_value_hash =3D Hash.new
@pair_value_hash =3D Hash.new
=20
#build array of all possible pairs
@all_pairs =3D get_all_pairs
end
=20
#finds the nth choice of a person for some value n, 0 would be
#the first choice, 1 second, etc.
def get_nth_choice(person, n)
@pairs_hash[person].scan(/\w+/)[n]
end
=20
#this method returns 0 if the pair is only one name
#otherwise it looks up the pair value in a hash
#preference indexes, 0=3Dbest, 1=3Dnext best, etc.
def get_pair_value(pair)
pair_array =3D pair.split(" ")
return 0 if(pair_array.length=3D=3D1)
=20
#get the value from the pair value hash
return @pair_value_hash[pair] + @pair_value_hash[pair_array[1] + " " + =
pair_array[0]]
end

#this method calculates the value of a possible solution of pairs
def get_pair_set_val(pair_set)
#check the hash first
return @pair_set_value_hash[pair_set] if(@pair_set_value_hash.include?(=
pair_set))
=20
#not in the hash calculate it
val =3D 0
pair_set.each {|next_pair| val +=3D get_pair_value(next_pair)}
@pair_set_value_hash[pair_set] =3D val
return val
end
=20
#this method calculates a list of pairs from the pair array minus the
#head_pair and any similar pairs (see similar? method for more details).
def get_tail(pair_array, head_pair)
tail_array =3D []
pair_array.each do |next_pair|
#remove all pairs with common partners
tail_array +=3D [next_pair] unless(similar?(head_pair, next_pair))
end
return tail_array
end
=20
#pairs are considered similar if they share a common name or they
#are both a single name (this case makes sure that only one single
#name can be selected in any given solution
def similar?(pair1, pair2)
#returns true if they are both length of 1
return true if(pair1.split(" ").length=3D=3D1 and
pair2.split(" ").length=3D=3D1)

#returns true if the pairs have common partners
pair1.split(" ").each do |next_name|
if(pair2.include?(next_name))
return true
end
end
return false
end

#this method generates a list of all possible pairs
def get_all_pairs
all_pairs =3D []
@pairs_hash.each_key do |p1|
1.upto(@num_choices) do |cnt|
#select the next person in the list
p2 =3D get_nth_choice(p1, cnt-1)
=20
#add to all pairs list
all_pairs +=3D [p1 + " " + p2] unless(all_pairs.include?(p2 + " " +=
p1))
=20
#add to pair_value_hash for later lookup
@pair_value_hash[p1 + " " + p2] =3D (cnt-1)**2
end
#add individual names if there are an odd number of people
all_pairs +=3D [p1] if (@num_people & 1 =3D=3D 1)
end
return all_pairs
end
=20
#this method executes an exhaustive search of all pair sets for
#each set it calculates the value with the best found up to that
#point. if the value is lower then it saves the new solution.
def get_preferred_pairs(pair_array=3D@all_pairs)
solution =3D []
solution_value =3D 1.0/0.0
#base case: pair_array is empty
if(pair_array.length=3D=3D0)
return solution
end
=20
#iterate over all pairs in the array use each one as the head
#in a potential solution
pair_array.each do |pair|
#get the next potential solution
pair_set =3D [pair] +
get_preferred_pairs(get_tail(pair_array, pair)) #recursive call
#calculate the value of the next potential solution
pair_set_val =3D get_pair_set_val(pair_set)
if(solution_value>pair_set_val)
#better solution has been found... save it!
solution =3D pair_set
solution_value =3D pair_set_val
end
end
return solution
end
end

if(ARGV.length =3D=3D 0)
puts "Usage: provide YAML file name as the argument."
exit 0
end

t1 =3D Time.now
pc =3D PairCalculator.new("list.yaml")
pair_set =3D pc.get_preferred_pairs
pair_set.each {|pair| puts pair}
t2 =3D Time.now
puts "Pair set value: #{pc.get_pair_set_val(pair_set)} \nTime: #{t2 - t1}"

_________________________________________________________________
Instantly invite friends from Facebook and other social networks to join yo=
u on Windows Live=99 Messenger.
https://www.invite2messenger.net/im/?source=3DTXT_EML_WLH_Invi...

comp.lang.ruby

Re: [QUIZ] Preferable Pairs (#165

Steven Hahn

x Login to ForumsZone