<commit_before>#!/usr/bin/env gprolog --consult-file

make_change(0, _, []).

% Note it finds one solution; it may not be the best one (= with the fewer
% coins).
%
% E.g.: make_change(8, [5, 4, 1], C).
%       C = [5, 1, 1, 1] ?
%
% The best solution would be [4, 4].
%
make_change(Sum, Coins, [N|Change]) :-
  Sum > 0,
  member(N, Coins),
  Sum2 is Sum-N,
  make_change(Sum2, Coins, Change).

% convenient alias
make_usa_change(Sum, Change) :-
  make_change(Sum, [25, 10, 5, 1], Change).<commit_msg>KataChange: find the best solution<commit_after>#!/usr/bin/env gprolog --consult-file

make_some_change(0, _, []).

make_some_change(Sum, Coins, [N|Change]) :-
  Sum > 0,
  member(N, Coins),
  Sum2 is Sum-N,
  make_change(Sum2, Coins, Change).

longer_or_equal(List, Length) :-
  length(List, L),
  L >= Length.

make_change(Sum, Coins, C1) :-
  make_some_change(Sum, Coins, C1),
  length(C1, L1),
  % note this takes too much time even on simple cases
  forall(make_some_change(Sum, Coins, C2), longer_or_equal(C2, L1)).

% convenient alias
make_usa_change(Sum, Change) :-
  make_change(Sum, [25, 10, 5, 1], Change).
{'fraction_non_alphanumeric': 0.16815742397137745, 'fraction_numerical': 0.03309481216457961, 'mean_word_length': 3.9513274336283186, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '86471', 'n_tokens_mistral': 479, 'n_tokens_neox': 450, 'n_words': 120}