Last active
August 29, 2015 14:20
-
-
Save mattsta/b6749e566f5cfd75762a to your computer and use it in GitHub Desktop.
This is an erlang version of https://gist.github.com/gigamonkey/6249d85021bc8bf54eb4 (with a minor change to 'combos'/'combineAdjacent' for easier reading)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env escript | |
% Problem statement: | |
% Write a program that outputs all possibilities to put + or - or nothing between the | |
% numbers 1, 2, ..., 9 (in this order) such that the result is always 100. | |
% For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100. | |
% Generate all combos of digits 1-9 with +, -, or nothing in between. | |
combos([N]) -> [[N]]; | |
combos([N|Ns]) -> [[N, X] ++ Rest || X <- [plus, minus, empty], Rest <- combos(Ns)]. | |
% Combine adjacent digits into a single number. | |
combineAdjacent([N, empty, M | Rest]) -> combineAdjacent([N * 10 + M | Rest]); | |
combineAdjacent([N, Op | Rest]) -> [N, Op | combineAdjacent(Rest)]; | |
combineAdjacent(X) -> X. | |
% Now eval the resulting thing as a left-associative expression. | |
eval([N, plus, M | Rest]) -> eval([N + M | Rest]); | |
eval([N, minus, M | Rest]) -> eval([N - M | Rest]); | |
eval([N]) -> N. | |
results(Matches) -> | |
lists:foldl(fun(X, Result) -> | |
Result ++ [lists:map(fun(plus) -> " + "; | |
(minus) -> " - "; | |
(N) -> integer_to_list(N) | |
end, X)] | |
end, [], Matches). | |
main([]) -> | |
Matches100 = lists:filter(fun(Combined) -> eval(Combined) == 100 end, [combineAdjacent(X) || X <- combos(lists:seq(1, 9))]), | |
io:format("~s~n", [string:join(results(Matches100), "\n")]). |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment