Project Euler 117

https://odz.sakura.ne.jp/projecteuler/index.php?Problem+117

考え方は116と大体同じ。

多分動的計画法だかメモ化？だかを実装しているような気がする…（使用しているアルゴリズムの名前をわかってない）

116、117あたりはChatGPTでもするっと解けそう

回答は省略

%problem117
:- dynamic combination_count_assert/3.

%combination_count_assert(tile_rest, most_left_block_size, combination_count).

solve:-
	retractall(combination_count_assert(_,_,_)),
	combination_count(50, 1, CombinationCount1),
	combination_count(50, 2, CombinationCount2),
	combination_count(50, 3, CombinationCount3),
	combination_count(50, 4, CombinationCount4),
	Answer is CombinationCount1 + CombinationCount2 + CombinationCount3 + CombinationCount4, 
	printf(output,"answer = %d = %d + %d + %d + %d\n",[Answer,CombinationCount1,CombinationCount2,CombinationCount3,CombinationCount4]).

combination_count(RestTiles, BlockSize, CombinationCount):-
	combination_count_assert(RestTiles,BlockSize,CombinationCount),!.	% メモしたケースにヒット
combination_count(RestTiles, BlockSize, CombinationCount):-
	RestTiles - BlockSize =:= 0,
	CombinationCount = 1,
	!.
combination_count(RestTiles, BlockSize, CombinationCount):-
	RestTiles - BlockSize < 0,
	CombinationCount = 0,
	!.
combination_count(RestTiles, BlockSize, CombinationCount):-
	RestTiles1 is RestTiles - BlockSize,
	combination_count(RestTiles1, 1, CombinationCount1),	% 一番左が空のケース
	combination_count(RestTiles1, 2, CombinationCount2),	% 一番左がBlock(size:2)を配置したケース
	combination_count(RestTiles1, 3, CombinationCount3),	% 一番左がBlock(size:3)を配置したケース
	combination_count(RestTiles1, 4, CombinationCount4),	% 一番左がBlock(size:4)を配置したケース
	
	CombinationCount is CombinationCount1 + CombinationCount2 + CombinationCount3 + CombinationCount4,
	assert(combination_count_assert(RestTiles, BlockSize, CombinationCount)).