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.