salvageon.erl

-module(salvageon).
-export([main/0]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CodeIQ / サルベジオン問題 を解きました。
% (https://codeiq.jp/ace/yuki_hiroshi/q1215)
% 
% ・db1 はキーが昇順にソートされているので二分探索で探せば見つかります。
%   大きな整数を扱える、Erlang でプログラムを書きました。
% 
% ・db2 は factor コマンドを主に使いました。キーの一般項が
% 
%    2^(100 - n) (2k + 1), 1 <= n <= 100, 0 <= k <= 2^n
%
% のような形をしていることに気が付きました。
% 探しているキー K2023636070998557444542586045 を factor コマンドで素因数分解してみると
% 
% 3 5 59 2286594430506844570104617
%
% となり、因数 2 を持たないことが分かります。
% したがって、n = 100 のブロックを調べればよいです。
% それは index = 2^99 から始まります。
%
% 2k + 1 = 2023636070998557444542586045
%
% を解いて k を決め、index = 2^99 + k の値を調べたところ、探していたキーを発見できました。
%
% 以下は二分探索のプログラムです。
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% エントリーポイント
main() ->
    Min = 0,
    Max = 19781945725870318832662826826,
    % 下限が Min, 上限が Max で二分探索を開始する
    main_loop(1, (Min + Max) div 2, Min, Max).

%% 二分探索を実行する
main_loop(Db_, Index, Min, Max) ->
    TARGET = 208050656559285601386927895421059705239114932023754,
    LIMIT = 19781945725870318832662826826,

    {Id, Key, Val} = key(Db_, Index),
    if
	Key =:= TARGET ->
	    % 見つけた
	    Key;
	Key  <  TARGET ->
	    main_loop(Db_, (Id + Max) div 2, Id, Max);

	Key  >  TARGET ->
	    main_loop(Db_, (Min + Id) div 2, Min, Id)

    end.

%% 指定された DB の指定された Index を持つデータを API から取得するし、
%% {Index, Key, Value} のタプルで返す
key(Db_, Index) ->
    inets:start(),
    URL_FORMAT = "http://salvageon.textfile.org/?db=~p&index=~p",

    Url = io_lib:format(URL_FORMAT, [Db_, Index]),

    {ok, { {_, 200,_}, Headers, Body}} = httpc:request(Url),

    io:format("~s~n", [Body]),

    [Db, Id, Key, Val, Limit] = string:tokens(Body, " "),
    {
      list_to_integer(Id),
      list_to_integer(re:replace(Key, "K", "", [{return, list}])),
      list_to_integer(re:replace(Val, "V", "", [{return, list}]))
    }.