オフラインリアルタイムどう書くE07 の問題の ruby による実装例

問題：http://nabetani.sakura.ne.jp/hena/orde07_7seg/
実装リンク集：http://qiita.com/Nabetani/items/6e7a6fadbfaa4ae20e89

で。

この問題は、

• 情報が不十分な 7seg から、その 7seg で表示可能な数字(あるいは空白)のリストを得る
• 得られた情報から、最大値と最小値を得る

という二段階になっている。

前半はビット演算で簡単に求まる。

集合で書くと、

• ついているとわかっているランプ ⊂ 本当についているランプ
• ついているとわかっているランプ ∩ 本当に消えているランプ = ∅

なので、ビット演算で書くと

• ついているとわかっているランプ & 本当についているランプ == ついているとわかっているランプ
• ついているとわかっているランプ & 本当に消えているランプ == 0

となる。

後半はいろいろな戦略がある。
私が最初に選んだ方法は

• 全部試して合致するものから最大最小を得る

という馬鹿げた実装。こんな感じ。

require "benchmark"

PATS=[
  [0x0, :blank],
  [0x3f, 0],  [0x06, 1],  [0x5b, 2],  [0x4f, 3],  [0x66, 4],
  [0x6d, 5],  [0x7d, 6],  [0x27, 7],  [0x7f, 8],  [0x6f, 9]
]

def okay( x, ketas )
  s=("%*d" % [ketas.size, x ])
  s.size.times.all?{ |ix|
    c=s[ix]
    k=ketas[ix]
    if c==" "
      k.include?(:blank)
    else
      k.include?(c.to_i)
    end
  }
end

def solve(src)
  ons, offs = src.split(",").map{ |x| x.split(":").map{|seg| seg.to_i(16) } }
  ketas=ons.size.times.map do |ix|
    PATS.each.select{ |bits,digit|
      ( ons[ix] & bits ) == ons[ix] && (offs[ix] & bits )==0
    }.map(&:last)
  end

  mm=(10**ketas.size).times.select{ |x|
    okay(x,ketas)
  }.minmax
  mm.compact.empty? ? "-" : mm.join(",")
end

$stdout.sync=true

DATA.map do |line|
  /(?<num>\d+).*"(?<src>.+)".*"(?<expected>.+)"/=~line
  actual = nil
  tick = Benchmark.realtime{ actual = solve( src ) }
  okay = actual==expected
  puts( "%s %s %s->%s ( e:%s ) %f" % [ ( okay ? "ok" : "**NG**" ), num, src, actual, expected, tick ] )
  okay
end.all?.tap{|x| puts( x ? "everything is ok" : "something wrong" ) }

__END__
/*0*/ test( "06:4b:46:64:6d,79:20:10:10:02", "12345,13996" );    
/*1*/ test( "41:00,3e:01", "-" );    
/*2*/ test( "00:00,79:79", "1,11" );    
/*3*/ test( "02:4b:46:64,20:20:10:10", "1234,3399" );    

3桁なら、0から999まで全部試す。
とても遅いけど、正しいと確信が持てるという意味では安心感がある。

とはいえ、これでは全部テストを通すのに数分を要するので困る。困るので、もっと速いのを書いた。

前半は先程のと同じ。
後半は、

• 最初の桁が空白かどうかで分岐して、再帰呼び出しで求める。

というもの。こんな感じ：

PATS=[
  [0, :blank],
  [0x3f, 0],  [0x06, 1],  [0x5b, 2],  [0x4f, 3],  [0x66, 4],
  [0x6d, 5],  [0x7d, 6],  [0x27, 7],  [0x7f, 8],  [0x6f, 9]
]

def find_minmax(ketas, ord, head=true)
  h, *r = ketas
  return ( h - [:blank] ).send(ord) if ketas.size==1
  if head && h.include?( :blank )
    return [
        find_minmax( r, ord, true ),
        find_minmax( [h-[:blank]]+r, ord, true )
      ].compact.send(ord)
  end
  h-=[:blank]
  h-=[0] if head
  return nil if h.size==0
  m=find_minmax( r, ord, false )
  return m ? h.send(ord)*10**(ketas.size-1) + m : nil
end

def solve(src)
  ons, offs = src.split(",").map{ |x| x.split(":").map{|seg| seg.to_i(16) } }
  ketas=ons.zip( offs ).map{ |on,off|
    PATS.select{ |pat|
      (pat[0] & on ) == on && ( pat[0] & off )== 0
    }.map( &:last )
  }
  return "-" if ketas.any?{ |x| x==[] }
  max = find_minmax( ketas, :max )
  return "-" unless max
  [  find_minmax( ketas, :min ), max ].join(",")
end

DATA.map do |line|
  /(?<num>\d+).*"(?<src>.+)".*"(?<expected>.+)"/=~line
  actual = solve( src )
  okay = actual==expected
  puts( "%s %s %s->%s ( e:%s )" % [ ( okay ? "ok" : "**NG**" ), num, src, actual, expected ] )
  okay
end.all?.tap{|x| puts( x ? "everything is ok" : "something wrong" ) }

__END__
/*44*/ test( "18:04:26:20:04:24:1a,02:21:50:48:02:08:00", "6177540,6177678" );    
/*45*/ test( "00:08:34:00:00:64:06,18:24:02:00:61:08:61", "260141,7269141" );    
/*46*/ test( "00:02:0a:04:4a:00:20,18:21:24:02:04:60:19", "125214,7126214" );

最大値を求める計算と最小値を求める計算を同じメソッドにするために、send(:min) のようなことをしている。
head は先頭の桁かどうか。先頭だと 0 が使えないとか、空白が選べるとか、いろいろ違いがあるからね。

問題としては、やや難しかった模様。