「L被覆」をErlangでやってみました。他の実装は 第16回オフラインリアルタイムどう書くの参考問題 から辿れます。
lcove.erl
-module(lcove).
-compile(export_all).
%% 解く
solve(Data) ->
% 1の位と10の位に分ける関数
F = fun(SX) -> X = list_to_integer(SX), {X div 10, X rem 10} end,
area([F(SX) || SX <- string:tokens(Data, ",")]).
%% L字型の面積を求める
area(L) ->
% 四隅から削れる最大面積を求める
{_, C} = lists:foldl(fun(_, {La, Max}) ->
case cornerarea(La) of
A when A > Max -> {turnr(La), A};
_ -> {turnr(La), Max}
end
end, {L, 0}, [1, 2, 3, 4]),
% 文字列に変換する
case C of
0 -> % 四隅が削れずエリアが四角の時
case {rangex(L), rangey(L)} of
{{0, 9}, {0, 9}} -> "-"; % 目一杯なら"-"
_ -> integer_to_list(squarearea(L) + 1) % それ以外なら1マス飛び出させる
end;
X -> integer_to_list(squarearea(L) - X) % 削れる時は角を削った分を引く
end.
%% 左上から四角く削れる最大面積を求める
cornerarea(L) ->
{X1, X2} = rangex(L),
{Y1, Y2} = rangey(L),
F = fun(X) -> lists:foldl(fun
({Xa, Ya}, Hi) when Xa =:= X -> lists:min([Ya, Hi]);
(_, Hi) -> Hi
end, Y2, L) end,
H2 = [F(X) - Y1 || X <- lists:seq(X1, X2 - 1)],
H3 = lists:zip(lists:seq(1, X2 - X1), H2),
{_, H4} = lists:foldl(fun({W, H}, {Hacc, Ret}) ->
M = lists:min([H, Hacc]),
{M, [{W, M} | Ret]}
end, {Y2 - Y1, []}, H3),
lists:max([W * H || {W, H} <- H4]).
%% データーを右へ90度回転させる
turnr(L) -> [{Y, 9 - X} || {X, Y} <- L].
%% すべての塗られたマス目を含む四角形の面積を返す
squarearea(L) ->
{X1, X2} = rangex(L),
{Y1, Y2} = rangey(L),
(X2 - X1 + 1) * (Y2 - Y1 + 1).
%% 指定された座標の範囲を返す
range(F, L) ->
Rs = [F(R) || R <- L],
R2 = lists:max(Rs),
case lists:min(Rs) of
R2 -> {R2 - 1, R2}; % 1マスの時は2マスに拡張する
R1 -> {R1, R2}
end.
%% X座標の範囲を返す
rangex(L) -> range(fun({X, _}) -> X end, L).
%% Y座標の範囲を返す
rangey(L) -> range(fun({_, Y}) -> Y end, L).
%% テスト
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("41,33,26,55,74,58,68", "39"), %0
test("00,99,09,90", "-"), %1
test("09", "3"), %2
test("05,05,05", "3"), %3
test("45", "3"), %4
test("38,39", "3"), %5
test("38,47", "3"), %6
test("45,66", "4"), %7
test("12,34,56,78", "33"), %8
test("12,34,56,78,45", "37"), %9
test("00,09,00", "11"), %10
test("00,90", "11"), %11
test("99,09", "11"), %12
test("99,90", "11"), %13
test("11,12,21,22", "5"), %14
test("42,45,92,95,83,62", "25"), %15
test("42,45,92,83,62", "14"), %16
test("34,38,78,74,56,35,77,48,54", "26"), %17
test("38,78,74,56,35,77,48,54", "23"), %18
test("31,41,21,71,21", "7"), %19
test("46,45,42,44,45", "6"), %20
test("00,99,09", "19"), %21
test("99,09,90,24", "64"), %22
test("99,16,61,34,17,24,42,26,18,71,19,91,81,43,33,62,52,25", "75"), %23
test("55,43,16,91,61,19,24,18,33,34,71,81,42,62,52,26,17,25", "53"), %24
test("71,26,81,62,17,16,25,42,33,52,19,18,91,24,61,34,43", "45"), %25
test("39,49,19,93,78,58,48,91,95,29,68,92,86,87,94,77", "39"), %26
test("69,89,25,26,58,12,37,36,68,24,11,13,48,14,79", "37"), %27
test("58,67,92,38,83,29,91,76,84,57,75,48,85,19,66", "51"), %28
test("00,83,76,85,48,19,75,29,92,57,66,67,91,58,38,84", "91"), %29
test("11,92,57,38,58,66,91,67,84,48,83,19,75,85,76,29", "72"), %30
test("36,07,45", "9"), %31
test("57,23,24,74", "21"), %32
test("92,20,32,12,65", "39"), %33
test("24,54,66,48,54,15", "21"), %34
test("05,17,42,20,48,22,13", "39"), %35
test("53,84,55,56,25,14,84,43", "26"), %36
test("06,77,56,59,15,24,09,66,71", "51"), %37
test("53,36,47,45,45,67,66,46,63,75", "21"), %38
test("35,53,93,33,02,84,83,48,54,32,28", "50"), %39
test("55,74,32,84,41,64,24,44,15,14,26,53", "39"), %40
test("47,60,34,32,19,67,24,83,94,38,47,05,79", "88"), %41
test("63,32,42,74,66,64,35,41,74,25,48,62,44,54", "42"), %42
test("00,86,16,19,09,92,51,10,68,23,14,63,21,46,03", "91"), %43
test("56,46,54,14,15,25,53,84,58,85,44,37,54,76,26,76", "42"), %44
test("71,87,39,43,76,38,91,69,98,33,43,26,56,69,73,52,89", "66"), %45
test("43,26,84,64,52,48,36,23,66,53,41,57,76,36,84,57,35,41", "47"), %46
test("81,02,85,93,36,46,80,27,72,28,02,99,13,41,36,40,18,97,38", "91"), %47
test("63,46,75,58,42,26,58,37,14,75,35,63,32,36,52,46,85,14,48,23", "47"), %48
test("66,92,64,12,17,33,10,28,75,05,81,05,42,86,52,57,56,78,87,81,10", "82"), %49
test("48,25,58,76,15,74,43,44,24,62,33,67,34,34,42,48,37,33,51,43,46,67", "50"). %50