Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2009-03-20

RubyでL-99 (P9〜P13)

| 02:17 | RubyでL-99 (P9〜P13) - わだばLisperになる を含むブックマーク はてなブックマーク - RubyでL-99 (P9〜P13) - わだばLisperになる

適当につらつらと書いておりますが、折角なので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"]]

2009-03-16

RubyでL-99 (P1〜P8)

| 23:59 | RubyでL-99 (P1〜P8) - わだばLisperになる を含むブックマーク はてなブックマーク - RubyでL-99 (P1〜P8) - わだばLisperになる

Rubyを勉強しております。

Rubyにリストが無いのとブロックの引数がローカルのスコープをつくらないところ(1.8では)にびっくりしました。

びっくりというより若干ショックでしたが、別にLispじゃないので当然のことでした。

ちょっとMatz Lispという言葉を真に受け過ぎていたようです(笑)

無駄に再帰していますが、L-99はそういう問題なのでRubyでも再帰。

色々分からないことが多く、まったくRubyっぽく書けてないですが、10年後位にはRubyっぽく書けるようになるのかもしれません。

# P01 (*) Find the last box of a list.
#     Example:
#     * (my-last '(a b c d))
#     (D)
class Array
  def my_last 
    head, *tail = self
    if tail.empty?
      self
    else
      tail.my_last
    end
  end
end

%w(1 2 3).my_last
#=> ["3"]

# P02 (*) Find the last but one box of a list.
#     Example:
#     * (my-but-last '(a b c d))
#     (C D)
class Array
  def last2
    _, *tail = self
    if tail[1..-1].empty?
      self
    else
      tail.last2
    end
  end
end

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

#P03 (*) Find the K'th element of a list.
#    The first element in the list is number 1.
#    Example:
#    * (element-at '(a b c d e) 3)
#    C
class Array
  def element_at (pos)
    head, *tail = self
    if 0 > pos
      nil
    elsif self.empty? || 1 >= pos 
      head
    else
      tail.element_at(pos - 1)
    end
  end 
end

%w(1 2 3 4).element_at(2)
#=> "2"

# P04 (*) Find the number of elements of a list.
class Array
  def my_size
    _, *tail = self
    if self.empty?
      0
    else
      1 + tail.my_size
    end
  end
end

%w(1 2 3 4).my_size
#=> 4

# P05 (*) Reverse a list.
class Array
  def my_reverse
    head, *tail = self    
    if self.empty?
      []
    else
      tail.my_reverse + [head]
    end
  end
end

%w(1 2 3 4).my_reverse
#=> ["4", "3", "2", "1"]


#P06 (*) Find out whether a list is a palindrome.
#    A palindrome can be read forward or backward; e.g. (x a m a x).
class Array 
  def palindrome?
    self.my_reverse == self
  end
end

%w(x a m a x).palindrome?
#=> true

%w(x m a x).palindrome?
#=> false

# P07 (**) Flatten a nested list structure.
#     Transform a list, possibly holding lists as elements into a
#     `flat' list by replacing each list with its elements
#     (recursively).
#     Example:
#     * (my-flatten '(a (b (c d) e)))
#     (A B C D E)
#     Hint: Use the predefined functions list and append.
class Array
  def my_flatten
    head, *tail = self
    if self.empty?
      []
    elsif head.class == Array
      head.my_flatten + tail.my_flatten
    else
      [head] + tail.my_flatten
    end
  end
end

[1, [2, [3, 4], 5]].my_flatten
#=> [1, 2, 3, 4, 5]

# P08 (**) Eliminate consecutive duplicates of list elements.
#     If a list contains repeated elements they should be replaced
#     with a single copy of the element. The order of the elements
#     should not be changed.
#     Example:
#     * (compress '(a a a a b c c a a d e e e e))
#     (A B C A D E)
class Array 
  def _compress(prev, acc)
    head, *tail = self
    if self.empty?
      acc
    elsif head == prev
      tail._compress(head, acc)
    else
      tail._compress(head, acc + [head])
    end
  end

  def compress
    self._compress(:dummy, [])
  end
end

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