Sum to 100
- Task
Find solutions to the sum to one hundred puzzle.
Add (insert) the mathematical
operators + or ─ (plus
or minus) before any of the digits in the
decimal numeric string 123456789 such that the
resulting mathematical expression adds up to a
particular sum (in this iconic case, 100).
Example:
123 + 4 - 5 + 67 - 89 = 100
Show all output here.
- Show all solutions that sum to 100
- Show the sum that has the maximum number of solutions (from zero to infinity*)
- Show the lowest positive sum that can't be expressed (has no solutions), using the rules for this task
An example of a sum that can't be expressed (within the rules of this task) is: 5074
which, of course, is not the lowest positive sum that can't be expressed.
* (where infinity would be a relatively small 123,456,789)
Haskell
<lang Haskell>import Control.Monad (replicateM) import Data.Char (intToDigit) import Data.List (nub, group, sort, sortBy, find, intercalate) import Data.Function (on)
data Sign
= Unsigned | Plus | Minus deriving (Eq, Show)
universe :: (Int, Sign) universe =
zip [1 .. 9] <$> filter ((/= Plus) . head) (replicateM 9 [Unsigned, Plus, Minus])
allNonNegativeSums :: [Int] allNonNegativeSums = sort $ filter (>= 0) (asSum <$> universe)
asSum :: [(Int, Sign)] -> Int asSum xs =
n + (if null s then 0 else read s :: Int) where (n, s) = foldr readSign (0, []) xs readSign :: (Int, Sign) -> (Int, String) -> (Int, String) readSign (i, x) (n, s) | x == Unsigned = (n, intToDigit i : s) | otherwise = ( (if x == Plus then (+) else (-)) n (read (show i ++ s) :: Int) , [])
asString :: [(Int, Sign)] -> String asString = foldr signedDigit []
where signedDigit (i, x) s | x == Unsigned = intToDigit i : s | otherwise = (if x == Plus then " +" else " -") ++ [intToDigit i] ++ s
main :: IO () main =
mapM_ putStrLn [ "Sums to 100:\n" , unlines $ asString <$> filter ((== 100) . asSum) universe , "\n10 commonest sums (sum, followed by number of routes to it):\n" , show (let sumAndSolutions xs@(x:_) = (x, length xs) in take 10 $ sortBy (flip compare `on` snd) (sumAndSolutions <$> group allNonNegativeSums)) , "\n\nFirst positive integer not expressible as a sum of this kind:\n" , maybeReport (find (uncurry (/=)) (zip [0 ..] (nub allNonNegativeSums))) ] where maybeReport :: Show a => Maybe (a, b) -> String maybeReport (Just (x, _)) = show x maybeReport _ = "No gaps found"</lang>
- Output:
Sums to 100: 123 +45 -67 +8 -9 123 +4 -5 +67 -89 123 -45 -67 +89 123 -4 -5 -6 -7 +8 -9 12 +3 +4 +5 -6 -7 +89 12 +3 -4 +5 +67 +8 +9 12 -3 -4 +5 -6 +7 +89 1 +23 -4 +56 +7 +8 +9 1 +23 -4 +5 +6 +78 -9 1 +2 +34 -5 +67 -8 +9 1 +2 +3 -4 +5 +6 +78 +9 -1 +2 -3 +4 +5 +6 +78 +9 10 commonest sums (sum, followed by number of routes to it): [(9,46),(27,44),(1,43),(15,43),(21,43),(45,42),(3,41),(5,40),(7,39),(17,39)] First positive integer not expressible as a sum of this kind: 211
Perl 6
<lang perl6>my @ops = ['-', ], |( [' + ', ' - ', ] xx 8 ); my @str = [X~] map { .Slip }, ( @ops Z 1..9 ); my %sol = @str.classify: *.subst( ' - ', ' -', :g )\
.subst( ' + ', ' ', :g ).words.sum;
my %count.push: %sol.map({ .value.elems => .key });
my $max_solutions = %count.max( + *.key ); my $first_unsolvable = first { %sol{$_} :!exists }, 1..*; my @two_largest_sums = %sol.keys.sort(-*)[^2];
given %sol{100}:p {
say "{.value.elems} solutions for sum {.key}:"; say " $_" for .value.list;
}
say .perl for :$max_solutions, :$first_unsolvable, :@two_largest_sums;</lang>
- Output:
12 solutions for sum 100: -1 + 2 - 3 + 4 + 5 + 6 + 78 + 9 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 1 + 2 + 34 - 5 + 67 - 8 + 9 1 + 23 - 4 + 5 + 6 + 78 - 9 1 + 23 - 4 + 56 + 7 + 8 + 9 12 + 3 + 4 + 5 - 6 - 7 + 89 12 + 3 - 4 + 5 + 67 + 8 + 9 12 - 3 - 4 + 5 - 6 + 7 + 89 123 + 4 - 5 + 67 - 89 123 + 45 - 67 + 8 - 9 123 - 4 - 5 - 6 - 7 + 8 - 9 123 - 45 - 67 + 89 :max_solutions("46" => $["9", "-9"]) :first_unsolvable(211) :two_largest_sums(["123456789", "23456790"])
REXX
<lang rexx>/*REXX pgm solves a puzzle: using the string 123456789, insert - or + to sum to 100*/ parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO=100 /*Not specified? Then use the default.*/ if HI== | HI=="," then HI=LO /* " " " " " " */ if LO=00 then HI=123456789 /*LOW specified as zero with leading 0s*/ ops= '+-'; sol="solution"; L=length(ops) + 1 /*define operators (and their length). */ @.=; do i=1 to L-1; @.i=substr(ops,i,1) /* " some handy-dandy REXX literals*/
end /*i*/ /* " individual operators for speed*/
mx=0; mn=999999; mxL=; mnL= /*initialize some minimums and maximums*/ tell= (LO==HI); do j=LO to HI until LO==00 & mn==0 /*solve with a range of sums*/
z=solve(j); y=z; if y==0 then y='no' /*find # solutionson for J.*/ if tell then say y sol ||s(y) 'found.' /*Not a range? Show number.*/ if z> mx then mxL= /*see if this is a new max. */ if z>=mx then do; mxL=mxL j; mx=z; end /*remember this new maximum.*/ if z< mn then mnL= /*see if this is a new min. */ if z<=mn then do; mnL=mnL j; mn=z; end /*remember this new minimum.*/ end /*j*/
if tell then exit /*should we show max and min*/ @@= 'number of solutions: ' _=words(mxL); say 'sum's(_) "of" mxL ' 's(_,"have",'has') 'the maximum' @@ mx _=words(mnL); say 'sum's(_) "of" mnL ' 's(_,"have",'has') 'the minimum' @@ mn exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ s: if arg(1)==1 then return arg(3); return word(arg(2) "s",1) /*simple pluralizer*/ /*──────────────────────────────────────────────────────────────────────────────────────*/ solve: parse arg answer; #=0 /*obtain the answer (sum) to the puzzle*/
do a=L-1 to L; aa= @.a'1' /*choose one of ─ or nothing. */ do b=1 for L; bb=aa || @.b'2' /* " " " ─ +, or abutment.*/ do c=1 for L; cc=bb || @.c'3' /* " " " " " " " */ do d=1 for L; dd=cc || @.d'4' /* " " " " " " " */ do e=1 for L; ee=dd || @.e'5' /* " " " " " " " */ do f=1 for L; ff=ee || @.f'6' /* " " " " " " " */ do g=1 for L; gg=ff || @.g'7' /* " " " " " " " */ do h=1 for L; hh=gg || @.h'8' /* " " " " " " " */ do i=1 for L; ii=hh || @.i'9' /* " " " " " " " */ interpret '$=' ii /*calculate the sum of modified string.*/ if $\==answer then iterate /*Is sum not equal to answer? Then skip*/ #=#+1; if tell then say 'solution: ' $ " ◄───► " ii end /*i*/ end /*h*/ end /*g*/ end /*f*/ end /*e*/ end /*d*/ end /*c*/ end /*b*/ end /*a*/ ; return # /*return the number of solutions found.*/</lang>
output when the default input is used:
solution: 100 ◄───► -1+2-3+4+5+6+78+9 solution: 100 ◄───► 1+2+3-4+5+6+78+9 solution: 100 ◄───► 1+2+34-5+67-8+9 solution: 100 ◄───► 1+23-4+5+6+78-9 solution: 100 ◄───► 1+23-4+56+7+8+9 solution: 100 ◄───► 12+3+4+5-6-7+89 solution: 100 ◄───► 12+3-4+5+67+8+9 solution: 100 ◄───► 12-3-4+5-6+7+89 solution: 100 ◄───► 123+4-5+67-89 solution: 100 ◄───► 123+45-67+8-9 solution: 100 ◄───► 123-4-5-6-7+8-9 solution: 100 ◄───► 123-45-67+89 12 solutions found.
output when the following input is used: 00
sum of 9 has the maximum number of solutions: 46 sum of 211 has the minimum number of solutions: 0
For those that are interested, the 46 solutions (for the sum of 9) are:
solution: 9 ◄───► -1+2+3+4+5+6+7-8-9 solution: 9 ◄───► -1+2+3-4+5-6-7+8+9 solution: 9 ◄───► -1+2+3-4-5+6+7-8+9 solution: 9 ◄───► -1+2+3-45+67-8-9 solution: 9 ◄───► -1+2+34+56+7-89 solution: 9 ◄───► -1+2-3+4+5-6+7-8+9 solution: 9 ◄───► -1+2-3+4-5+6+7+8-9 solution: 9 ◄───► -1+23+4+5+67-89 solution: 9 ◄───► -1+23+4-5-6-7-8+9 solution: 9 ◄───► -1+23-4+5-6-7+8-9 solution: 9 ◄───► -1+23-4-5+6+7-8-9 solution: 9 ◄───► -1-2+3+4+5+6-7-8+9 solution: 9 ◄───► -1-2+3+4+5-6+7+8-9 solution: 9 ◄───► -1-2+3-4-5-6+7+8+9 solution: 9 ◄───► -1-2+3-4-56+78-9 solution: 9 ◄───► -1-2-3+4-5+6-7+8+9 solution: 9 ◄───► -1-2-3+45-6-7-8-9 solution: 9 ◄───► -1-2-3-4+5+6+7-8+9 solution: 9 ◄───► -1-2-34+56+7-8-9 solution: 9 ◄───► -1-23+45-6-7-8+9 solution: 9 ◄───► -12+3-45-6+78-9 solution: 9 ◄───► -12+34+5+6-7-8-9 solution: 9 ◄───► -12+34+56-78+9 solution: 9 ◄───► -12-34+5+67-8-9 solution: 9 ◄───► 1+2+3+4-5-6-7+8+9 solution: 9 ◄───► 1+2+3-4+5-6+7-8+9 solution: 9 ◄───► 1+2+3-4-5+6+7+8-9 solution: 9 ◄───► 1+2-3+4+5+6-7-8+9 solution: 9 ◄───► 1+2-3+4+5-6+7+8-9 solution: 9 ◄───► 1+2-3-4-5-6+7+8+9 solution: 9 ◄───► 1+2-3-4-56+78-9 solution: 9 ◄───► 1+2-34-56+7+89 solution: 9 ◄───► 1+23+4-5-6-7+8-9 solution: 9 ◄───► 1+23-4+5-6+7-8-9 solution: 9 ◄───► 1+23-45+6+7+8+9 solution: 9 ◄───► 1-2+3+4+5+6-7+8-9 solution: 9 ◄───► 1-2+3-4-5+6-7+8+9 solution: 9 ◄───► 1-2-3+4+5-6-7+8+9 solution: 9 ◄───► 1-2-3+4-5+6+7-8+9 solution: 9 ◄───► 1-2-3-4+5+6+7+8-9 solution: 9 ◄───► 1-2-3-4-5-67+89 solution: 9 ◄───► 1-23+4+5-67+89 solution: 9 ◄───► 1-23+45-6-7+8-9 solution: 9 ◄───► 1-23-4+5+6+7+8+9 solution: 9 ◄───► 1-23-45-6-7+89 solution: 9 ◄───► 12-34-56+78+9 46 solutions found.
zkl
Taking a big clue from Haskell and just calculate the world. <lang zkl>var all = // ( (1,12,123...-1,-12,...), (2,23,...) ...)
(9).pump(List,fcn(n){ split("123456789"[n,*]) }) // 45 .apply(fcn(ns){ ns.extend(ns.copy().apply('*(-1))) }); // 90
fcn calcAllSums{ // calculate all 6572 sums (1715 unique)
fcn(n,sum,soFar,r){ if(n==9) return(); foreach b in (all[n]){
if(sum+b>=0 and b.abs()%10==9) r.appendV(sum+b,"%s%+d".fmt(soFar,b)); self.fcn(b.abs()%10,sum + b,"%s%+d".fmt(soFar,b),r);
} }(0,0,"",r:=Dictionary()); r
}
// "123" --> (1,12,123)
fcn split(nstr){ (1).pump(nstr.len(),List,nstr.get.fp(0),"toInt") }</lang> <lang zkl>fcn showSums(allSums,N=100,printSolutions=2){
slns:=allSums.find(N,T); if(printSolutions) println("%d solutions for N=%d".fmt(slns.len(),N)); if(printSolutions==2) println(slns.concat("\n")); println();
}
allSums:=calcAllSums(); showSums(allSums); showSums(allSums,0,1);
println("Smallest postive integer with no solution: ",
[1..].filter1('wrap(n){ Void==allSums.find(n) }));
eqns:=allSums.values; // all equations eqns=eqns[(0).minMaxNs(eqns.apply("len"))[1]]; // largest collection of solutions print("Most common sum is ");
Compiler.Compiler.compileText("print(0%s)".fmt(eqns[0]))(); // eval the hard way println(" with %d ways to calculate it.".fmt(eqns.len()));</lang>
- Output:
12 solutions for N=100 +1+2+3-4+5+6+78+9 +1+2+34-5+67-8+9 +1+23-4+5+6+78-9 +1+23-4+56+7+8+9 +12+3+4+5-6-7+89 +12+3-4+5+67+8+9 +12-3-4+5-6+7+89 +123+4-5+67-89 +123+45-67+8-9 +123-4-5-6-7+8-9 +123-45-67+89 -1+2-3+4+5+6+78+9 22 solutions for N=0 Smallest postive integer with no solution: 211 Most common sum is 9 with 46 ways to calculate it.