Unofficial Ruby Quiz -- Ranking Choices

[Ken Bloom]

Apparently some people around here can't stand Ruby Quiz withdrawal. For
those people, here's a quiz question I just came up with.

I have a list of some items, and I would like to manually rank which ones
are most important to me. But it's not easy to rank them when I'm looking
at them all at once, so I'd like to consider them in pairs and choose
from each pair which one is most important to me. Then I'd like to use my
answers to those questions to create a ranked list. Anyone think they can
come up with a good program to quiz me about these items pairwise, and
output a ranking?

Extra credit: come up with a solution that lets me take the quiz multiple
times, and outputs a single ranked list reflecting all of my sessions
taking the quiz.

I have my solution to the basic question, but I want to see what other
people come up with.

--Ken

 

[Bill Guindon]

Apparently some people around here can't stand Ruby Quiz withdrawal. For
those people, here's a quiz question I just came up with.

I have a list of some items, and I would like to manually rank which ones
are most important to me. But it's not easy to rank them when I'm looking
at them all at once, so I'd like to consider them in pairs and choose
from each pair which one is most important to me. Then I'd like to use my
answers to those questions to create a ranked list. Anyone think they can
come up with a good program to quiz me about these items pairwise, and
output a ranking?

Thanks much for filling in. I'm very interested, and I hope I have
the time to take a shot at this one.

Could you elaborate on the rules a bit? Do all possible pairs have to
be evaluated, or should it deduce values based on previous answers?

banana is more important than apple
orange is more important than banana
no need to compare apples to oranges (pardon the pun).

Extra credit: come up with a solution that lets me take the quiz multiple
times, and outputs a single ranked list reflecting all of my sessions
taking the quiz.

I have my solution to the basic question, but I want to see what other
people come up with.

--Ken

PS: typo on your home page: 'contected', looks bad for a linguistics major

 

[Chris Carter]

Apparently some people around here can't stand Ruby Quiz withdrawal. For
those people, here's a quiz question I just came up with.

I have a list of some items, and I would like to manually rank which ones
are most important to me. But it's not easy to rank them when I'm looking
at them all at once, so I'd like to consider them in pairs and choose
from each pair which one is most important to me. Then I'd like to use my
answers to those questions to create a ranked list. Anyone think they can
come up with a good program to quiz me about these items pairwise, and
output a ranking?

Extra credit: come up with a solution that lets me take the quiz multiple
times, and outputs a single ranked list reflecting all of my sessions
taking the quiz.

I have my solution to the basic question, but I want to see what other
people come up with.

--Ken

I wrote a webapp that did something like that using a perverted
Condorcet method described here: http://xkcd.com/date/algorithms.html.
I don't have the code anymore, but that's a concise way fo doing it.

 

[Ken Bloom]

Thanks much for filling in. I'm very interested, and I hope I have the
time to take a shot at this one.

Could you elaborate on the rules a bit? Do all possible pairs have to
be evaluated, or should it deduce values based on previous answers?

banana is more important than apple
orange is more important than banana
no need to compare apples to oranges (pardon the pun).

I guess I'd want to know if I ran into a cycle, but I know that's a lot
more questions. Something else that I would find interesting is having a
way to determine the top 10 asking the minimum number of questions. So
implement whatever answer you prefer.

--Ken

P.S. I think the Ruby Quiz needs a fourth rule: don't ask too many
questions about what the rules of a particular quiz are. Your variation
on the problem may have interesting techniques that nobody else's has.

 

[Clifford Heath]

I have a list of some items, and I would like to manually rank which ones
are most important to me. But it's not easy to rank them when I'm looking
at them all at once, so I'd like to consider them in pairs and choose
from each pair which one is most important to me.

Topological sort. "man tsort" on most *nix systems, or
<http://en.wikipedia.org/wiki/Topological_sorting#Algorithms>.
The rest is just I/O.

 

[Eric Mahurin]

I have a list of some items, and I would like to manually rank which ones
are most important to me. But it's not easy to rank them when I'm looking
at them all at once, so I'd like to consider them in pairs and choose
from each pair which one is most important to me. Then I'd like to use my
answers to those questions to create a ranked list. Anyone think they can
come up with a good program to quiz me about these items pairwise, and
output a ranking?

The way I see it, ranking is nothing more than sorting and choosing
between pairs is just the comparison of the sort. So, here is a
one-liner given the item list in a file and the questions on stdin:

ruby -e 'puts(ARGF.read.split.sort { |a,b| print "1: #{a}\n2: #{b}\n";
STDIN.gets.to_i*2-3}.inspect)' <item-file>

Eric

 

[Ken Bloom]

Apparently some people around here can't stand Ruby Quiz withdrawal. For
those people, here's a quiz question I just came up with.

I have a list of some items, and I would like to manually rank which
ones are most important to me. But it's not easy to rank them when I'm
looking at them all at once, so I'd like to consider them in pairs and
choose from each pair which one is most important to me. Then I'd like
to use my answers to those questions to create a ranked list. Anyone
think they can come up with a good program to quiz me about these items
pairwise, and output a ranking?

Extra credit: come up with a solution that lets me take the quiz
multiple times, and outputs a single ranked list reflecting all of my
sessions taking the quiz.

I have my solution to the basic question, but I want to see what other
people come up with.

Here's a solution that uses tsort, the topological sort module from
Ruby's standard library. It asks Theta(n^2) questions, but allows me to
specify that two items on the list are really redundant (and have that
reflected in the output), and to detect cycles in my preferences that I
may need to break somehow.

#!/usr/bin/env ruby
require 'rubygems'
require 'enumerator'
require 'facets/core/enumerable/each_unique_pair'
require 'tsort'

class Hash
include TSort
alias tsort_each_node each_key
def tsort_each_child(node, &block)
fetch(node).each(&block)
end
end

LIST=["Option 1","Option 2","Option 3","Option 4"]
RESULTS=Hash.new{|h,k| h[k]=[]}
LIST.each{|x| RESULTS[x]}


LIST.enum_foreach_unique_pair).
map{|x| x.sort_by{rand}}.
sort_by{rand}.each do |opt1,opt2|
printf "1:%s 2:%s ",opt1,opt2
case readline.chomp
when "1":
RESULTS[opt2] << opt1
when "2":
RESULTS[opt1] << opt2
when "=":
RESULTS[opt1] << opt2
RESULTS[opt2] << opt1
else
puts "No preference"
end
end


puts

#ORDERED LIST
RESULTS.strongly_connected_components.
each{|list| p list}