#:g1: RubyでL-99 (P9〜P13)

Posted 2009-03-19 17:17:00 GMT

適当につらつらと書いておりますが、折角なのでRSpecでテストも書きたいところ。
次は書いてみよう!

# P09 (**) Pack consecutive duplicates of list elements into sublists.
#     If a list contains repeated elements they should be placed in
#     separate sublists.
#
#     Example:
#     * (pack '(a a a a b c c a a d e e e e))
#     ((A A A A) (B) (C C) (A A) (D) (E E E E))
class Array
  def pack
    self.internal_pack([], [:dummy])
  end

protected def internal_pack(ans, acc) head, *tail = self if self.empty? (ans + [acc])[1..-1] elsif head == acc[0] tail.internal_pack(ans ,acc + [head]) else tail.internal_pack(ans + [acc], [head]) end end end

%w(a a a a b c c a a d e e e e).pack #=> [["a", "a", "a", "a"], ["b"], ["c", "c"], ["a", "a"], ["d"], ["e", "e", "e", "e"]]

# P10 (*) Run-length encoding of a list. # Use the result of problem P09 to implement the so-called # run-length encoding data compression method. Consecutive # duplicates of elements are encoded as lists (N E) where N is the # number of duplicates of the element E. # # Example: # * (encode '(a a a a b c c a a d e e e e)) # ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E)) class Array def encode self.pack.map do |x| [x.size, x.first] end end end

%w(a a a a b c c a a d e e e e).encode #=> [[4, "a"], "b", [2, "c"], [2, "a"], "d", [4, "e"]]

# P11 (*) Modified run-length encoding. # Modify the result of problem P10 in such a way that if an # element has no duplicates it is simply copied into the result # list. Only elements with duplicates are transferred as (N E) # lists. # # Example: # * (encode-modified '(a a a a b c c a a d e e e e)) # ((4 A) B (2 C) (2 A) D (4 E)) class Array def encode_modified self.pack.map do |x| if 1 == x.size x.first else [x.size, x.first] end end end end

%w(a a a a b c c a a d e e e e).encode_modified #=> [[4, "a"], "b", [2, "c"], [2, "a"], "d", [4, "e"]]

# P12 (**) Decode a run-length encoded list. # Given a run-length code list generated as specified in problem # P11. Construct its uncompressed version. class Array def decode self.inject([]) do |ans, x| ans + if x.class == Array Array.new(x[0], x[1]) else Array.new(1, x) end end end end

# 2 class Array def decode t = Array self.inject([]) do |ans, x| ans.+ x.class == Array ? Array.new(x[0], x[1]) : Array.new(1, x) end end end

[[4, "a"], "b", [2, "c"], [2, "a"], "d", [4, "e"]].decode #=> ["a", "a", "a", "a", "b", "c", "c", "a", "a", "d", "e", "e", "e", "e"]

# P13 (**) Run-length encoding of a list (direct solution). # Implement the so-called run-length encoding data compression # method directly. I.e. don't explicitly create the sublists # containing the duplicates, as in problem P09, but only count # them. As in problem P11, simplify the result list by replacing # the singleton lists (1 X) by X. # # Example: # * (encode-direct '(a a a a b c c a a d e e e e)) # ((4 A) B (2 C) (2 A) D (4 E)) class Array def encode_direct (self + [:dummy]).internal_encode_direct([], 1, :dummy)[1..-1] end

protected def internal_encode_direct(ans, cnt, prev) head, *tail = self if self.empty? ans elsif head == prev tail.internal_encode_direct(ans, cnt + 1, head) else tail.internal_encode_direct(ans + [[cnt, prev]], 1, head) end end end

%w(a a a a b c c a a d e e e e).encode_direct #=> [[4, "a"], [1, "b"], [2, "c"], [2, "a"], [1, "d"], [4, "e"]]


comments powered by Disqus