ナベアツ問題これは難しい・・・

ナベアツ問題なるものが、紹介されていました。

http://q.hatena.ne.jp/1207585413

これを文字列化もせず、桁に分割したりせず、第3の方法がないかなと思って試しています。
BCD(http://ja.wikipedia.org/wiki/%E4%BA%8C%E9%80%B2%E5%8C%96%E5%8D%81%E9%80%B2%E8%A1%A8%E7%8F%BE)の考え方を利用する方向性で考えています。まだ、うまく行っていませんが、こんな感じです。

#!/bin/env ruby

j = 0
(0..100).each do |i|
  j += 1
  if j & 0xf > 9 then
    j += 0x10
    j -= 10
  end

  if j & 0xff > 0x9f then
    j += 0x100
    j -= 0xa0
  end

  k = j
  k ^= 0x33333333
  k = (k * (k >> 16)) & 0xffff
  k = (k * (k >> 8)) & 0xff
  k = (k * (k >> 4)) & 0xf

  printf "%x %x\n", j, k
end

この中で次の部分がBCDのカウンタを実現する部分です。

  j += 1
  if j & 0xf > 9 then
    j += 0x10
    j -= 10
  end

  if j & 0xff > 0x9f then
    j += 0x100
    j -= 0xa0
  end

0x9の次は0x10になり、0x99の次は0x100になるように補正します。BCD表現を利用することによって、ビット演算のみで各桁の切り出しができるようになります。

後は、3を含む桁を見つけ出す処理ですが、これがうまく行っていません。もちろん、ナイーブに各桁を切り出していくといいのですが・・・。

追記 2008/4/12 その１

とりあえずナイーブな方法で完成。これだと結局桁ごとに切り出しているのでもうちょっと検討します。

#!/bin/env ruby

j = 0
(1..1000).each do |i|
  j += 1
  if j & 0xf > 9 then
    j += 0x10
    j -= 10
  end

  if j & 0xff > 0x9f then
    j += 0x100
    j -= 0xa0
  end

  if j & 0xfff > 0x9ff then
    j += 0x1000
    j -= 0xa00
  end

  if j & 0xffff > 0x9fff then
    j += 0x10000
    j -= 0xa000
  end

  k = j
  k ^= 0x33333333
  l = (k >> 24) & 0xf
  l *= (k >> 20) & 0xf
  l *= (k >> 16) & 0xf
  l *= (k >> 12) & 0xf
  l *= (k >> 8) & 0xf
  l *= (k >> 4) & 0xf
  l *= k & 0xf
  
  print i
  if l == 0 or i % 3 == 0 then
    print " aho"
  end
  if i % 5 == 0 then
    print " wan"
  end
  print "\n"
end

追記 2008/4/12 その2

完成しました。

#!/bin/env ruby

j = 0
(1..1000).each do |i|
  j += 1
  if j & 0xf > 9 then
    j += 0x10
    j -= 10
  end

  if j & 0xff > 0x9f then
    j += 0x100
    j -= 0xa0
  end

  if j & 0xfff > 0x9ff then
    j += 0x1000
    j -= 0xa00
  end

  if j & 0xffff > 0x9fff then
    j += 0x10000
    j -= 0xa000
  end

  k = j
  k ^= 0xcccccccc
  k &= (k >> 1)
  k &= (k >> 2)
  k |= (k >> 16)
  k |= (k >> 8)
  k |= (k >> 4)
  k &= 1
  
  print i
  if k == 1 or i % 3 == 0 then
    print " aho"
  end
  if i % 5 == 0 then
    print " wan"
  end
  print "\n"
end