ErlangとInverse Fizzbuzz - no_orz_no

Inverse FizzbuzzをErlangでやってみることにします。Inverse Fizzbuzzとは、fizz/buzz/fizzbuzz の組み合わせを与えたとき、それを満たすような最短の数列を得るというものです(途中のfizz/buzz/fizzbuzzのいずれでもない項は省く)。たとえば、[fizz] であれば [3] ですし、[fizz,buzz]であれば、[9,10]となります([3,4,5]も[fizz,buzz]ですが、最短ではないため解にはなりません)。

問題だけを見て考えたのは下記のような方針に基づいた解法でした。

とりあえず指定した数値以降で条件を満たす最小の組み合わせを得る関数を作る(inversefizzbuzz_core)
それを1〜100までひととおり評価させて、考えられる回答(ただし最短とは限らない)の組み合わせを得る(inversefizzbuzz_all)
その組み合わせの中で、最短かつ最小のものを求める。(inversefizzbuzz0)

以下、できあがったものを順番に展開してゆきます。まず、補助関数として、以下2つを準備しました。

指定した数値以降で、条件(fizz/buzz/fizzbuzz/any)を満たす最小の値を得る(next)。anyは、fizz/buzz/fizzbuzzいずれでもOKとする。
指定した数値がfizz/buzz/fizzbuzzのいずれの条件を満たすかを調べる(what)

それぞれ下記のようになりました。

-module(inversefizzbuzz).
-compile(export_all).

next(any, N) when N rem 3 =:= 0 orelse N rem 5 =:= 0 -> N;    
next(fizz, N) when N rem 3 =:= 0 andalso N rem 15 =/= 0 -> N;
next(buzz, N) when N rem 5 =:= 0 andalso N rem 15 =/= 0 -> N;
next(fizzbuzz, N) when N rem 15 =:= 0 -> N;
next(FB, N) -> next(FB, N + 1).

what(N) ->
    case N of
	N when N rem 15 =:= 0 -> fizzbuzz;
	N when N rem 5 =:= 0 -> buzz;
	N when N rem 3 =:= 0 -> fizz;
	N -> N
    end.

さて、これを元にして、条件を満たす最小の(最短ではない)値の組を得る関数(inversefizzbuzz_core)を作ります。

inversefizzbuzz_core([H|_] = L) ->
    inversefizzbuzz_core(L, L, next(H, 1), []).

inversefizzbuzz_core(_LL, [], _, Res) -> 
    TL = hd(Res),
    HD = hd(lists:reverse(Res)),
    {HD, TL};
inversefizzbuzz_core(_LL, _, N, _) when N > 100 -> void;
inversefizzbuzz_core(LL, [H|TL], N, Res) ->
    case what(N) of
	H ->
	    case inversefizzbuzz_core(LL, TL, next(any, N + 1), [N|Res]) of
		void ->
		    inversefizzbuzz_core(LL, LL, next(hd(LL), N + 1), []);
		L ->
		    L
	    end;
	_Any ->
	    void
    end.

スタート地点を決定し、その次を探し、それが期待するfizz/buzz/fizzbuzzと一致していれば先に進み、そうでなければふりだしに戻って次を探す、という繰り返しを行います。元のblogの記述にならって、起点と終点の組で結果を表すようにしました。

5> inversefizzbuzz:inversefizzbuzz_core([fizz,buzz]).
{3,5}
6>

よいようですね。{3,5}は問題の回答としては誤りですが、最小の回答であるのでこの関数としては期待通りです。

では、この関数を利用して、考えられるすべての組み合わせを取得する関数(inversefizzbuzz_all)を作ります。

inversefizzbuzz_all(L) ->
    inversefizzbuzz_all(L, next(hd(L), 1), []).
inversefizzbuzz_all(L, N, Res) ->
    case inversefizzbuzz_core(L, L, N, []) of
	void -> % もうない
	    lists:reverse(Res);
	R ->
	    inversefizzbuzz_all(L, next(hd(L), element(1, R)+1), [R|Res])
    end.

実際に試してみると...

6> inversefizzbuzz:inversefizzbuzz_all([fizz,buzz]).
[{3,5},
 {9,10},
 {18,20},
 {24,25},
 {33,35},
 {39,40},
 {48,50},
 {54,55},
 {63,65},
 {69,70},
 {78,80},
 {84,85},
 {93,95},
 {99,100}]
7>

これもよいようですね。あとはこのリストの中から、起点と終点の差が最小のものを選べば、それが求める回答となります。

inversefizzbuzz0(L) ->
    R = inversefizzbuzz_all(L),
    case R of
	[] ->
	    nothing;
	R ->
	    minby(
	      fun({Min0, Max0}, {Min1, Max1}) ->
		      D1 = Max1 - Min1,
		      D0 = Max0 - Min0,
		      if D1 =< D0 -> right;
			 true -> left
		      end
	      end, R)
    end.

minbyは、指定したfunを元に比較を行い、最小の値を得る関数です。

minby([], _F) -> undefined;
minby(F, [H|_TL] = L) ->
    lists:foldl(
      fun(X, Acc) ->
	      case F(X, Acc) of
		  left -> X;
		  right -> Acc
	      end
      end, H, L).

では試してみましょう...

7> inversefizzbuzz:inversefizzbuzz0([fizz,buzz]).
{9,10}
8>

大丈夫そうです。では、いくつか想定される回答を元にテストパターンを作ってみます。

assert(T,T) -> ok.
test() ->
    assert(inversefizzbuzz0([fizz]), {3,3}),
    assert(inversefizzbuzz0([buzz]), {5,5}),
    assert(inversefizzbuzz0([fizz, buzz]), {9, 10}),
    assert(inversefizzbuzz0([buzz, fizz]), {5, 6}),
    assert(inversefizzbuzz0([fizz, buzz, fizz]), {3,6}),
    assert(inversefizzbuzz0([buzz, fizz, buzz]), nothing),
    assert(inversefizzbuzz0([fizz, fizz]), {6,9}),
    assert(inversefizzbuzz0([fizz, fizz, buzz]), {6,10}),
    assert(inversefizzbuzz0([fizzbuzz]), {15,15}),
    assert(inversefizzbuzz0([fizz, fizzbuzz]), {12,15}).

どれどれ...

9> inversefizzbuzz:test().
ok
10>

OKですね(^^) よかったよかった。よかったところで、オリジナルの解法を見てみます。...ふむふむ、考えられるすべての数列に対してfizzbuzzをしてみて、そこから条件を満たす組み合わせを見つけるという感じになっていますね。ではそちらを真似してみましょう。

まず、考えられるすべての範囲の組み合わせを作成します。

10> Max = 100.
100
11> All = lists:flatten([ [{X,Y} || Y <- lists:seq(X, Max)] || X <- lists:seq(1, Max)]).
[{1,1},
 {1,2},
 {1,3},
 {1,4},
 {1,5},
 {1,6},
 {1,7},
 {1,8},
 {1,9},
 {1,10},
 {1,11},
 {1,12},
 {1,13},
 {1,14},
 {1,15},
 {1,16},
 {1,17},
 {1,18},
 {1,19},
 {1,20},
 {1,21},
 {1,22},
 {1,23},
 {1,24},
 {1,25},
 {1,26},
 {1,27},
 {1,...},
 {...}|...]
12> length(All).
5050
13>

次に、その各要素に対してfizzbuzzを適用します。このとき、fizzでもbuzzでもfizzbuzzでもない要素については除去します。以前勉強した lists:zf/2 が使えそうですね。

17> Results = 
	[
	 lists:zf(
	   fun(X) when X rem 15 =:= 0 -> {true, fizzbuzz};
	      (X) when X rem 5 =:= 0 -> {true, buzz};
	      (X) when X rem 3 =:= 0 -> {true, fizz};
	      (_X) -> false
	   end, lists:seq(From, To)) || {From, To} <- All].
[[],[],
 [fizz],
 [fizz],
 [fizz,buzz],
 [fizz,buzz,fizz],
 [fizz,buzz,fizz],
 [fizz,buzz,fizz],
 [fizz,buzz,fizz,fizz],
 [fizz,buzz,fizz,fizz,buzz],
 [fizz,buzz,fizz,fizz,buzz],
 [fizz,buzz,fizz,fizz,buzz,fizz],
 [fizz,buzz,fizz,fizz,buzz,fizz],
 [fizz,buzz,fizz,fizz,buzz,fizz],
 [fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz],
 [fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz],
 [fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz],
 [fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz],
 [fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz],
 [fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz,buzz],
 [fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz|...],
 [fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz|...],
 [fizz,buzz,fizz,fizz,buzz,fizz|...],
 [fizz,buzz,fizz,fizz,buzz|...],
 [fizz,buzz,fizz,fizz|...],
 [fizz,buzz,fizz|...],
 [fizz,buzz|...],
 [fizz|...],
 [...]|...]
18>

元の範囲リスト(All)とzipした後に、同一の組み合わせをまとめます。

18> Io = lists:zip(All, Results).
[{{1,1},[]},
 {{1,2},[]},
 {{1,3},[fizz]},
 {{1,4},[fizz]},
 {{1,5},[fizz,buzz]},
 {{1,6},[fizz,buzz,fizz]},
 {{1,7},[fizz,buzz,fizz]},
 {{1,8},[fizz,buzz,fizz]},
 {{1,9},[fizz,buzz,fizz,fizz]},
 {{1,10},[fizz,buzz,fizz,fizz,buzz]},
 {{1,11},[fizz,buzz,fizz,fizz,buzz]},
 {{1,12},[fizz,buzz,fizz,fizz,buzz,fizz]},
 {{1,13},[fizz,buzz,fizz,fizz,buzz,fizz]},
 {{1,14},[fizz,buzz,fizz,fizz,buzz,fizz]},
 {{1,15},[fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz]},
 {{1,16},[fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz]},
 {{1,17},[fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz]},
 {{1,18},[fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz]},
 {{1,19},[fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz]},
 {{1,20},[fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz|...]},
 {{1,21},[fizz,buzz,fizz,fizz,buzz,fizz|...]},
 {{1,22},[fizz,buzz,fizz,fizz,buzz|...]},
 {{1,23},[fizz,buzz,fizz,fizz|...]},
 {{1,24},[fizz,buzz,fizz|...]},
 {{1,25},[fizz,buzz|...]},
 {{1,26},[fizz|...]},
 {{1,...},[...]},
 {{...},...},
 {...}|...]
19> Inverses = inversefizzbuzz:groupby(Io, fun({A,B}) -> {B, A} end).
{dict,302,61,64,32,305,183,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[[],
          {1,1},
          {1,2},
          {2,2},
          {4,4},
          {7,7},
          {7,8},
          {8,8},
          {11,11},
          {13,13},
          {13,14},
          {14,14},
          {16,16},
          {16,17},
          {17,...},
          {...}|...],
(中略)
        [[[fizz,buzz,fizz,fizz|...],{1,20},{2,20},{3,...},{...}|...],
         [[fizz,buzz,fizz|...],{1,54},{2,...},{...}|...],
         [[fizz,buzz|...],{1,...},{...}|...],
         [[fizz|...],{...}|...],
         [[...]|...],
         [...]|...],
        [],[],[],[],[],[]}}}
20>

groupbyは下記のように実装しました。

groupby(L, F) ->
    R = 
	lists:foldl(
	  fun(X, D) ->
		  {K, V} = F(X),
		  NewValue = 
		      case D:find(K) of
			  {ok, Value} ->
			      [V|Value];
			  error ->
			      [V]
		      end,
		  D:store(K, NewValue)
	  end, dict:new(), L),
    R:fold(
      fun(K, V, D) ->
	      D:store(K, lists:reverse(V))
      end, R).

各要素をFに渡して、{K, V}を返してもらい、それをdictに仕立てあげるという作りになっています。

これで、指定したfizz/buzz/fizzbuzzの組み合わせに対して、考えられるすべての回答を得ることができるようになります(inversefizzbuzz_allに相当)。

20> Inverses:find([fizz,buzz]).
{ok,[{1,5},
     {2,5},
     {3,5},
     {7,10},
     {7,11},
     {8,10},
     {8,11},
     {9,10},
     {9,11},
     {16,20},
     {17,20},
     {18,20},
     {22,25},
     {22,26},
     {23,25},
     {23,26},
     {24,25},
     {24,26},
     {31,35},
     {32,35},
     {33,35},
     {37,40},
     {37,41},
     {38,40},
     {38,41},
     {39,...},
     {...}|...]}
21>

あとは、各リストについて最短かつ最小のものをとるようにしてやればOKですね。

21> Inverses_minby = 
  Inverses:fold(
      fun(K, V, D) ->
	      D:store(K, inversefizzbuzz:minby(
			   fun({A1,B1},{A2,B2}) ->
				   D1 = B1 - A1,
				   D2 = B2 - A2,
				   if
				       D1 < D2 -> left;
				       true -> right
				   end
			   end, V))
      end, Inverses).
{dict,302,61,64,32,305,183,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[[]|{1,1}],
         [[fizz,buzz,fizz]|{3,6}],
         [[fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz,buzz,fizz,
           fizz,buzz,fizz|...]|
          {3,40}],
         [[buzz,fizz,fizz]|{5,9}],
         [[buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz]|{5,18}],
(中略)
        [[[fizz,buzz,fizz,fizz|...]|{3,20}],
         [[fizz,buzz,fizz|...]|{3,54}],
         [[fizz,buzz|...]|{3,...}],
         [[fizz|...]|{...}],
         [[...]|...],
         [...]|...],
        [],[],[],[],[],[]}}}
22>

ではさっそく調べてみましょう...

22> Inverses_minby:find([fizz,buzz]).
{ok,{9,10}}
23> Inverses_minby:find([buzz,fizz,buzz]).
error
24>

いいですね。以上一連の流れを関数に仕立てあげてみます。

get_inverses() ->
    Max = 100,
    All = lists:flatten([ [{X,Y} || Y <- lists:seq(X, Max)] || X <- lists:seq(1, Max)]),
    Results = 
	[
	 lists:zf(
	   fun(X) when X rem 15 =:= 0 -> {true, fizzbuzz};
	      (X) when X rem 5 =:= 0 -> {true, buzz};
	      (X) when X rem 3 =:= 0 -> {true, fizz};
	      (_X) -> false
	   end, lists:seq(From, To)) || {From, To} <- All],
    Io = lists:zip(All, Results),
    groupby(Io, fun({A,B}) -> {B,A} end).

get_inverses_minby() ->
    Inverses = get_inverses(),
    Inverses:fold(
      fun(K, V, D) ->
	      D:store(K, minby(
			   fun({A1,B1},{A2,B2}) ->
				   D1 = B1 - A1,
				   D2 = B2 - A2,
				   if
				       D1 < D2 -> left;
				       true -> right
				   end
			   end, V))
      end, Inverses).

inversefizzbuzz(L) ->
    Inverses = get_inverses_minby(),
    assert(length(Inverses:fetch_keys()), 302),
    case Inverses:find(L) of
	{ok, V} ->
	    V;
	error ->
	    nothing
    end.

inversefizzbuzz0 と同様にテストを仕掛けてもいいのですが、せっかく実装の異なる2つの関数が出来たことですので、考えられるすべての組み合わせについて答えが合っているかどうか調べてみましょう。

test_all() ->
    D = get_inverses_minby(),
    lists:foreach(
      fun(K) ->
	      io:format("~p~n", [K]),
	      case K of 
		  [] ->
		      ok;
		  K ->
		      Exp = D:fetch(K),
		      Exp = inversefizzbuzz0(K)
	      end
      end, D:fetch_keys()).

25> inversefizzbuzz:test_all().
[fizzbuzz,fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz,buzz,fizz,fizz,buzz,
 fizz,fizzbuzz,fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz,buzz,fizz,fizz,
 buzz,fizz,fizzbuzz,fizz,buzz]
(中略)
[fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz,buzz,fizz,fizz,buzz,fizz,
 fizzbuzz,fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz,buzz,fizz,fizz]
[fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz,buzz]
ok
26>

大丈夫なようです。が、遅いです...試験終了までに数分かかります。どうやら私が最初に作ったバージョンは、入力が長くなるとバックトラックにかかる負荷がそうとう大きいようでかなり遅くなります。まさかblute forceより遅いとは情けない限りですね。