Yokohama.rb #103 の実装例

問題の名前 : マスクしても同じ数
問題 : http://nabetani.sakura.ne.jp/yokohamarb/103mask/
実装リンク集 : https://qiita.com/Nabetani/items/35e83eb39fed3c75d586

で。

地味な問題。

Yokohama.rb なので、ruby による実装例：

# frozen_string_literal: true

require "minitest/autorun"
require "json"

class MaskedNumbers
  def initialize(mask)
    @mask = mask
    @digits = @mask.digits(2)
    @count = @mask.to_s(2).gsub("0", "" ).to_i(2)
  end

  private 
  def expand(i)
    d0 = i.digits(2)
    d = @digits.map{ |e| e==1 ? (d0.shift||0) : 0 }
    d.reverse.join.to_i(2)
  end

  public
  def first(n)
    (1..@count).take(n).map{ |i| expand(i) }
  end

  def last(n)
    @count.downto(1).take(n).map{ |i| expand(i) }.reverse
  end
end

def solve( src )
  m = MaskedNumbers.new(src.to_i(16))
  nums = m.first(15+1)
  if 15<nums.size
    [nums.take(13).join(","), m.last(2).join(",")].join(",...,")
  else
    nums.join(",")
  end
end

if ! ARGV[0] || ! File.exist?( ARGV[0] )
  raise "you should specify json file as ARGV[0]"
end

class TestYokohamaRb103 < Minitest::Test
  json_string = File.open( ARGV[0], &:read )
  data = JSON.parse( json_string, symbolize_names:true )
  data[:test_data].each do | number:, src:, expected: |
    define_method( :"test_#{number}" ) do
      actual = solve(src)
      assert_equal( expected, actual )
    end
  end
end

Minitest の経験がないので、Minitest としてこれが正解なのかどうかよくわからない。

それはさておき。

例えば mask が2進数で 10001001 なら、mask 適合な数は、mask の1 がある場所にしか1がない数。つまり、2×2×2=8 通り...かと思いきや、0 を含めないので 7通りしかない。
パターンとしては、2進数の 001 〜 111 に対応する。
であれば、001〜111 を数え上げ、
2進数の xyz を 2進数の x000y00z に変換する関数があれば、それでよい。それが MaskedNumbers#expand 。

expand さえできれば、あとは 1〜16 を expand して、15個までしか作れなかったらそれを join して終了。

16個以上ある場合。
マスク適合な数は ( 2**(2進数表示の1の数) -1 ) 個だとわかるので、末尾をとることもできる。
あとは join(",") したものを join(",...,") すればよい。

というもの。