CodeIQ に出した「1の並びで小さい方から」の解説解題

CodeIQ に「1の並びで小さい方から」( https://codeiq.jp/q/2706 )という問題を出した。

問題の概要はこんな感じ：

数を2進数で表します。このとき、1 の連なりの最大の長さを
F(n)
と書きます。
X と Y という2つの数を与えます。
1以上の整数 n について、F(n)=X である n のうち、小さい方から Y 番目の数を求めてください。

入力は、XとY をコンマ区切りで繋いだ文字列です。
ただし：

• X は、1以上32以下の整数です。
• Y は、1以上1000以下の整数です。

数学的背景とかアルゴリズム的背景はいつもどおり特になくて、ふと思いついたから出したという感じ。
「32,10000」とか「1,1000」で計算時間が多くなりすぎて敗北しがちなのがこの問題の面白みだと思う。

で。どうするか。

比較的読みやすいけど実行時間はギリギリになりやすい実装から。

字句解析を省略するけど、こんな感じ：

def f(n)
  len=maxlen=0
  m=1
  loop do
    if 0 != (m & n )
      len+=1
      maxlen = len if maxlen<len
    else
      len=0
    end
    return maxlen if n<m
    m<<=1
  end
end

def solve( keta, ord )
  cands = {(1<<keta)-1=>true}
  memo={}
  keta.upto(Float::INFINITY) do |k|
    cands.keys.each{ |x|
        [x*2, x*2+1, x+(1<<k)].each do |y|
          cands[y]=true if (memo[y]||=f(y))==keta
        end
    }
    return cands.keys.sort[ord-1] if ord<cands.size
  end
end

たとえば X が 3 の場合。
まず、0b111 だけがある集合（実装の都合で Hash だけど）を用意する。
桁数を X から順に増やしていって、集合に含まれている要素について

• 右にゼロをつける( x*2 )
• 右に 1 をつける( x*2+1 )
• k 桁目に 1 をつける( x+(1<<k) )

の3つの数について調査して、F(n) が X であれば集合に追加する。
集合のサイズが Y を超えたところで小さい方から Y 番目を返せば終了。

でも、この実装だとちょっとギリギリ。

f は to_s(2) を使えばもっと短く書けるんだけど、実行速度を優先して整数演算のみにした。

もうちょっと速い実装はだいぶ長いんだけどこんな感じ：

# 1の連なりが len 個で、桁数 keta 桁以下の数のリスト
def just_lte(len,keta)
  (len..keta).flat_map{ |k|
    just_just(len,k)
  }
end

# 1の連なりが len 個で、桁数 keta 桁の数のリスト
def just_just(len,keta)
  return [] if keta<len
  return [2**len-1] if keta==len
  #len より少ない 1の連なり + ちょうど len 個を含むパターン
  lt_just=(1...len).flat_map{ |x|
    lows=just_lte(len, keta-x-1)
    head = (2**x-1)<<(keta-x)
    lows.flat_map{ |o|
      o+head
    }
  }
  #ちょうど len個の 1の連なり + len 以下のパターン
  lt_just+lte_lte(len, keta-len-1).flat_map{ |o|
    ((2**len-1)<<(keta-len))+o
  }
end

$memo={}
# 1の連なりが len 個以下で、桁数が keta 桁以下の数のリスト（メモ化）
def lte_lte(len,keta)
  $memo[[len,keta]]||=lte_lte_impl(len,keta)
end

# 1の連なりが len 個以下で、桁数が keta 桁以下の数のリスト（実装）
def lte_lte_impl(len,keta)
  len = [len, keta].min
  (len+1).times.flat_map{ |x|
    head = (2**x-1)<<(keta-x)
    lows=lte_lte(len, keta-x-1)
    lows=[0] if lows.empty?
    lows.flat_map{ |o|
      o+head
    }
  }
end

def solve( len, ord )
  r=[]
  (len..Float::INFINITY).each do |k|
    r+=just_just(len, k)
    if ord<r.size
      return r.sort[ord-1]
    end
  end
end

行ったり来たりの再帰呼び出しになっていて追いにくい。すいません。
1の連なりが len 個以下で、桁数が keta 桁以下の数のリスト をメモ化付き再帰呼び出しで創りだして、そこからちょうどのものを構成するという流れ。
自分でもわかりにくいと思う。