# -*- coding: utf-8 -*-
# q1037_answer.rb
 
# 工夫した点・苦労した点・感想等（ご自由にお書きください）：
# ・infinite_product_process メソッドで得られる Enumerator オブジェクト（イテレータ）をキューに登録して順次実行する仕組みにしました。
# ・infinite_product_process メソッドは、今までに列挙した値と、列挙に使わなかった残りの iters を引数にとって、
# 　そのうちの先頭のイテレータ（Enumerator オブジェクト）で値を列挙してその値と iters の残りを yield に引き渡しています。
 
# 必要に応じてここに require 文を挿入してもOKです（標準添付ライブラリに限る）。
# 例：require set
 
# 無限リスト（ストリーム）に対応した直積（Cartesian product）を生成して列挙するメソッド
def infinite_product *iters
  return to_enum :infinite_product, *iters unless block_given?
  q = [infinite_product_process([], iters)]
  until q.empty?
    it = q.shift
    begin
      vals, next_iters = it.next
      if next_iters.empty?
        yield vals
      else
        q << infinite_product_process(vals, next_iters)
      end
      q << it
    rescue StopIteration
      # pass
    end
  end
end
 
def infinite_product_process vals, iters
  # メソッドの引数は変更しても可↑。ただし「ブロック引数 (&block)」は利用不可。
  # メソッドの引数を変更した場合は、下記の ↓ to_enum の引数も適切に変更すること。
  return to_enum :infinite_product_process, vals, iters unless block_given?
  if iters.empty?
    yield [vals, []]
    return
  end
  xs = iters.dup
  it = xs.shift #.dup.to_enum
  it.each do |e|
    yield [vals + [e], xs]
  end
end
 
# ※これ以降は変更しないこと。
if $0 == __FILE__
  require 'test/unit'
  require 'prime'
 
  # 素数を列挙する Enumerator を返すメソッド
  def primes
    Prime.to_enum
  end
 
  # 整数（>0）を列挙する Enumerable（≠Enumerator） を返すメソッド
  def nats
    (1..1.0/0)
  end
 
  # フィボナッチ数列を列挙するメソッド
  def fib
    return to_enum :fib unless block_given?
    a, b = 0, 1
    loop do
      yield b
      a, b = b, a + b
    end
  end
 
  # infinite_product メソッドのテストクラス
  class AnswerQ3Test < Test::Unit::TestCase
    # fib のみのテスト
    def test_fib_only
      expected = [[1], [1], [2], [3], [5], [8], [13], [21], [34], [55]]
      result = infinite_product(fib).take(10)
      assert_equal(expected, result)
    end 
 
    # nats と fib の infinite_product のテスト
    def test_product_nats_fib
      expected = [
        [1, 1],
        [1, 1], [2, 1],
        [1, 2], [2, 1], [3, 1],
        [1, 3], [2, 2], [3, 1], [4, 1],
        [1, 5], [2, 3], [3, 2], [4, 1], [5, 1],
        [1, 8], [2, 5], [3, 3], [4, 2], [5, 1], [6, 1]
      ]
      result = infinite_product(nats, fib).take(21)
      assert_equal(expected, result)
    end
 
    # primes と nats と fib の infinite_product のテスト
    def test_product_primes_nats_fib
      expected = [
        [2, 1, 1],
        [2, 1, 1], [2, 2, 1],
        [3, 1, 1],
        [2, 1, 2], [2, 2, 1], [2, 3, 1],
        [3, 1, 1], [3, 2, 1],
        [5, 1, 1],
        [2, 1, 3], [2, 2, 2], [2, 3, 1], [2, 4, 1],
        [3, 1, 2], [3, 2, 1], [3, 3, 1],
        [5, 1, 1], [5, 2, 1],
        [7, 1, 1],
        [2, 1, 5], [2, 2, 3], [2, 3, 2], [2, 4, 1], [2, 5, 1],
        [3, 1, 3], [3, 2, 2], [3, 3, 1], [3, 4, 1],
        [5, 1, 2], [5, 2, 1], [5, 3, 1],
        [7, 1, 1], [7, 2, 1],
        [11, 1, 1]
      ]
      result = infinite_product(primes, nats, fib).take(35)
      assert_equal(expected, result)
    end
 
    # nats と [1, 2, 3] の infinite_product のテスト
    def test_product_nats_1_3
      expected = [
        [1, 1],
        [1, 2], [2, 1],
        [1, 3], [2, 2], [3, 1],
                [2, 3], [3, 2], [4, 1],
                        [3, 3], [4, 2], [5, 1],
                                [4, 3], [5, 2], [6, 1]
      ]
      result = infinite_product(nats, 1..3).take(15)
      assert_equal(expected, result)
    end
 
    # [1, 2, 3] と nats の infinite_product のテスト
    def test_product_1_3_nats
      expected = [
        [1, 1],
        [1, 2], [2, 1],
        [1, 3], [2, 2], [3, 1],
        [1, 4], [2, 3], [3, 2],
        [1, 5], [2, 4], [3, 3],
        [1, 6], [2, 5], [3, 4]
      ]
      result = infinite_product(1..3, nats).take(15)
      assert_equal(expected, result)
    end
 
    def test_product_1_2_x3
      expected = [
        [1, 1, 1],
        [1, 1, 2], [1, 2, 1], [2, 1, 1],
        [1, 2, 2], [2, 1, 2], [2, 2, 1],
        [2, 2, 2]
      ]
      # result = infinite_product([1, 2], [1, 2], [1, 2]).take(9)
      result = infinite_product([1, 2], [1, 2], [1, 2]).to_a
      assert_equal(expected, result)
    end
 
    def test_product_1_2_x4
      expected = [
        [1, 1, 1, 1],
        [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [2, 1, 1, 1],
        [1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 2, 1, 1],
        [1, 2, 2, 2], [2, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1],
        [2, 2, 2, 2]
      ]
      # result = infinite_product([1, 2], [1, 2], [1, 2], [1, 2]).take(16)
      result = infinite_product([1, 2], [1, 2], [1, 2], [1, 2]).to_a
      assert_equal(expected, result)
    end
  end
end