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.