Porting Peter Norvig’s “Martin Shuffle” algorithm

So I was reading the article written by Dr. Norvig here . It deals with finding a song as efficiently as possible on the displayless iPod shuffles–I think they still don’t have displays–I ain’t an iPod owner 🙂

The code he provides is in Python. I am more familiar with Ruby than Python, so I thought it would be fun to port the code to Ruby. Here it is. You can find the script file(ipod.rb) in the Box widget. The code is licensed under whatever license Dr.Norvig attaches to his code samples. Please pay attention to my disclaimers found after the code listing. By the way, the algorithm is based on Markov Decision Processes–some of you are familiar with Markov Chains. Markov Chains, in a nutshell, are finite state machines whose transitions are probabalistic, and not deterministic–I think that is an accurate description :p Note that this is probably not the most “Ruby-like” way of implementing the algorithm, and there is room for improvement.

#!/usr/bin/env ruby
#Ruby port author: Chinmoy Gavini
#Acknowledgment: Dr.Peter Norvig for his python code and explanation
#Dr.Norvig’s Python code is located at: http://norvig.com/ipod.html

class Array
def sum
total = 0
self.each {|x| total += x}
total
end

def avg
(self.sum.to_f)/(self.length.to_f)
end

end

def valueiteration(_N,_T,epsilon=0.001)
v1 = Array.new
v2 = Array.new
tmp = Array.new
t = _N/2
num_states = Range.new(0,_N-1)
num_states.each do |s|
v1 << (s-t).abs
v2 << 0
end
num_states.each {|s| tmp << ((v2[s] – v1[s]).abs)}

while(tmp.max > epsilon)
shufflecost = _T + v1.avg
num_states.each {|s| v2[s] = [( (s-t).abs),shufflecost].min}
v1,v2 = v2,v1
tmp.length.times {|x| tmp.pop}
num_states.each {|s| tmp << (v2[s] – v1[s]).abs}
end
v2
end

if __FILE__ == $0
_N = 250
_Ts = [1,5,10]
t = _N/2
$V = Array.new
temp = Array.new
_Ts.each do |_T|
$V = valueiteration(_N,_T)
(0.._N-1).each do |s|
temp << s if($V[s] == t-s)
end
num = temp.min
puts “T = #{_T} (N = #{_N}) ==> shuffle when #{(t – num)} or more away
puts “Mean: #{$V.avg}, Median: #{$V.sort[_N/2]}, Max: #{$V.max}”
end

end

Disclaimers:

NO WARRANTY

  11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS
TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE
PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
REPAIR OR CORRECTION.

  12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGES.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s