「増やす減らす二倍する」をErlangで(横へな13参考)

http://qiita.com/Nabetani/items/89fb0e2e712d4b396535
http://nabetani.sakura.ne.jp/hena/ord13updowndouble/
「増やす減らす二倍する」をErlangでやってみました。

0からスタートするのではなく、逆に目的の値からスタートし、1増やす、1減らす、2で割るを繰り返して0に到達するまでに要した回数を調べています。どの演算をするかは値の下位2ビットで判定します。

下位2ビットが:

• ?0 → 2で割る
• 01 → 1減らす
• 11 → 1増やす

01のとき1減らし、11のとき1増やすことで下位2ビットを00にすることができます。これは4の倍数であり、2で2回割れるため、より少ない回数で1に収束させることができます。

ただし下位2ビットが11になる数のうち3の時だけは、4にするより2にする方が収束が早いため、特例として1減らすことにします。実際には2→1→0にする処理を省略し「回数を3回増やしてその場で終了」しています。

updown.erl

-module(updown).
-compile(export_all).

solve(Data) ->
  integer_to_list(op_count(list_to_integer(Data), 0)).

%% 結果が1か3になるまで2で割るか1を増減し、その回数を返す
op_count(1, Count) -> Count + 1;
op_count(3, Count) -> Count + 3;
op_count(Num, Count) ->
  Bit0 = Num band 1,         % 最下位ビット
  Bit1 = (Num bsr 1) band 1, % 最下位ビットの1つ上のビット
  case {Bit1, Bit0} of                        % 下2ビットが
    {_, 0} -> op_count(Num bsr 1, Count + 1); % ?0なら2で割る
    {0, 1} -> op_count(Num - 1, Count + 1);   % 01なら1減らす
    {1, 1} -> op_count(Num + 1, Count + 1)    % 11なら1増やす
  end.

test(Data, Expected) ->
  Result = solve(Data),
  OkNg = case Result =:= Expected of true -> ok; false -> ng end,
  io:fwrite("~s: ~s -> ~s~n", [OkNg, Data, Result]).

tests() ->
  test("59", "9"), %0
  test("10", "5"), %1
  test("11", "6"), %2
  test("12", "5"), %3
  test("13", "6"), %4
  test("14", "6"), %5
  test("15", "6"), %6
  test("16", "5"), %7
  test("17", "6"), %8
  test("18", "6"), %9
  test("27", "8"), %10
  test("28", "7"), %11
  test("29", "8"), %12
  test("30", "7"), %13
  test("31", "7"), %14
  test("32", "6"), %15
  test("33", "7"), %16
  test("34", "7"), %17
  test("35", "8"), %18
  test("41", "8"), %19
  test("71", "9"), %20
  test("1023", "12"), %21
  test("1024", "11"), %22
  test("1025", "12"), %23
  test("1707", "17"), %24
  test("683", "15"), %25
  test("123", "10"), %26
  test("187", "11"), %27
  test("237", "12"), %28
  test("5267", "18"), %29
  test("6737", "18"), %30
  test("14796", "20"), %31
  test("18998", "20"), %32
  test("23820", "20"), %33
  test("30380", "21"), %34
  test("31119", "21"), %35
  test("33301", "20"), %36
  test("33967", "21"), %37
  test("35443", "22"), %38
  test("35641", "22"), %39
  test("43695", "23"), %40
  test("44395", "23"), %41
  test("44666", "22"), %42
  test("987", "14"), %43
  test("1021", "13"), %44
  test("1019", "13"), %45
  test("1015", "13"), %46
  test("1007", "13"), %47
  test("1011", "14"), %48
  test("1003", "14"), %49
  test("983", "14"), %50
  test("999", "14"), %51
  test("2731", "18"), %52
  test("6827", "20"), %53
  test("10923", "21"), %54
  test("27307", "23"), %55
  test("43691", "24"), %56
  test("109227", "26"), %57
  test("174763", "27"). %58

結果の一部:

ok: 59 -> 9
ok: 10 -> 5
ok: 11 -> 6
ok: 12 -> 5
...