theuntitledblog

As I read a blogpost written by Gabriel, about solving the 22 of the Ninety-Nine Prolog problems, I thought this would be a good opportunity to improve my functional programming skills in Ruby (I will probably also try to solve some of these problems in either Erlang or Haskell to improve my knowledge of these languages as well). Gabriel also links to the Scala solutions if this is more your cup of tea.

So far I have solved almost all of the Working with Prolog lists problems, with the exception of problem 26 and problem 27. I just can’t wrap my head around how to solve these, not even on paper, and the solution given in Prolog doesn’t exactly help me. Solving these problems in Ruby turned out to be quite simple for most of the problems, close to cheating even for some, as all you need is built into Ruby. I have tried to use a functional style of programming for the solutions, but for some, for example problem 28, I didn’t manage.

For these first problems, I mainly use the Enumarable::inject, which combines the elements of enum by applying the block to an accumulator value (memo) and each element in turn. The hard part is mostly defining the data structure to use, without it, it will be impossible to even solve the problem in a functional fashion.

The following solutions can be downloaded here, with corresponding specs.

# P01 - Find the last element of a list.
# built in
 
# P02 - Find the last but one element of a list.
def second_to_last
  self[-2]
end
 
# P03 - Find the K'th element of a list.
def kth(k)
  self[k - 1]
end
 
# P04 - Find the number of elements of a list.
# built in
 
# P05 - Reverse a list.
# built in
 
# P06 - Find out whether a list is a palindrome.
def palindrome?
  self == self.reverse
end
 
# P07 - Flatten a nested list structure.
# built in
 
# P08 - Eliminate consecutive duplicates of list elements.
def eliminate_consecutive_duplicates
  self.inject([]) do |array, current| 
      array << current unless array[-1] == current
      array
  end
end
 
# P09 - Pack consecutive duplicates of list elements into sublists.
def pack_consecutive_duplicates
  self.inject([[]]) do |array, current|
      if array[-1][-1] == current or array[-1][-1].nil?
          array[-1] << current
      else
          array << [current]
      end
      array
  end
 
end
 
# P10 - Run-length encoding of a list.
def run_length_encode
  self.pack_consecutive_duplicates.inject([]) do |array, current|
      array << [current.size, current[0]]
      array  
  end
end
 
# P11 - Modified run-length encoding.
def modified_run_length_encode
  self.run_length_encode.inject([]) do |array, current|
      array << current if current[0] > 1
      array << current[-1] if current[0] == 1
      array
  end
end
 
# P12 - Decode a run-length encoded list.
def decode_modified_run_length_encoded
  self.inject([]) do |array, current|
      if current.kind_of? Array
        array << [current[-1]] * current[0]
      else
        array << current
      end
      array
  end.flatten
end
 
# P13 - Run-length encoding of a list (direct solution).
def direct_run_length_encode
  self.inject([[0, nil]]) do |array, current|
    if array[-1][-1] == current or array[-1][-1].nil?
        array[-1][-1] = current
        array[-1][0] += 1 
    else
        array[-1] = array[-1][-1] if array[-1][0] == 1
        array << [1, current]
    end
    array
  end
end
 
# P14 & P15 - Duplicate the elements of a list n times, 2 by default.
def duplicate_elements(n = 2)
  self.inject([]) do |array, current|
    array << [current] * n
    array
  end.flatten
end  
 
# P16 (**) Drop every N'th element from a list.
def drop_every_nth(n)
  self.inject([[]]) do |array, current|
    if array[-1].size == n
      array << [current]
    else
      array[-1] << current
    end
    array
  end.inject([]) do |array, list|
    list.pop if list.size == n
    array << list
  end.flatten
end
 
# P17 (*) Split a list into two parts; the length of the first part is given.
def split_in_two(split)
  [self[0...split], self[split..-1]]
end
 
# P18 (**) Extract a slice from a list.
# built in
 
# P19 (**) Rotate a list N places to the left.
def rotate(n)
  self[n..-1].concat(self[0...n])
end
 
# P20 (*) Remove the K'th element from a list.
# built in
 
# P21 (*) Insert an element at a given position into a list.
# built in
 
# P22 (*) Create a list containing all integers within a given range.
# built in
 
# P23 (**) Extract a given number of randomly selected elements from a list.
def randomly_select(n)
  list = []
  n.times do
    list << self[rand * size]
  end
  list
end
 
# P24 (*) Lotto: Draw N different random numbers from the set 1..M.
def randomly_select_different(n)
  old_self = self
  list = []
  n.times do
    list << old_self.delete_at(rand * size)
  end
  list
end
 
# P25 (*) Generate a random permutation of the elements of a list.
def randomize
  randomly_select_different(self.size)
end
 
# P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list
# HELP NEEDED
 
# P27 (**) Group the elements of a set into disjoint subsets.
# HELP NEEDED
 
# P28 (**) Sorting a list of lists according to length of sublists
# a
def sort_sublists_by_length
  sort_by { |array| array.size }
end
 
# b
def sort_sublists_by_length_frequency
  length_frequency = {}
 
  each do |sublist|
    length_frequency[sublist.size] ||= 0
    length_frequency[sublist.size] += 1
  end
 
  sort_by { |array| length_frequency[array.size]}
end

Ruby functional programming

04 May 2009