test/int/each_subset_test.cr

• View this file on GitHub
• Last update: 2021-10-17 21:54:05+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_11_C

Depends on

• src/int/each_subset.cr

Code

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_11_C
require "../../src/int/each_subset"
n = read_line.to_i
a = read_line.split.map(&.to_i).skip(1).reduce(0) { |acc, x| acc | (1 << x) }
puts a.each_subset.map { |x|
  "#{x}:" + (0...n).select { |i| x.bit(i) == 1 }.join { |x| " #{x}" }
}.to_a.reverse.join('\n')

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_11_C
# require "../../src/int/each_subset"
struct Int
  private class SubsetIterator(T)
    include Iterator(T)

    def initialize(@set : T)
      @subset = T.zero.as(T)
      @first = true
    end

    def next
      if @subset == 0 && !@first
        stop
      else
        @first = false
        @subset = ~-@subset & @set
      end
    end
  end

  # Returns an iterator that returns all subsets of `self`.
  #
  # ```
  # 0b101.each_subset.to_a # => [0b101, 0b100, 0b001, 0b000]
  # ```
  def each_subset
    SubsetIterator.new(self)
  end

  # Calls the given block for each subset of `self`.
  #
  # ```
  # # x = 0b101, 0b100, 0b001, 0b000
  # 0b101.each_subset { |x| }
  # ```
  def each_subset(&)
    yield self
    sub = ~-self & self
    loop do
      yield sub
      break if sub == 0
      sub = ~-sub & self
    end
  end
end

n = read_line.to_i
a = read_line.split.map(&.to_i).skip(1).reduce(0) { |acc, x| acc | (1 << x) }
puts a.each_subset.map { |x|
  "#{x}:" + (0...n).select { |i| x.bit(i) == 1 }.join { |x| " #{x}" }
}.to_a.reverse.join('\n')

Back to top page