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.
