Sum to 100: Difference between revisions

 

:* &nbsp; Show all solutions that sum to &nbsp; <big> '''100''' </big>

:* &nbsp; Show the lowest positive sum that &nbsp; ''can't'' &nbsp; be expressed &nbsp; (has no solutions), &nbsp; using the rules for this task

:* &nbsp; Show the ten highest numbers that can be expressed using the rules for this task &nbsp; (extra credit)

<br>

 

An example of a sum that can't be expressed &nbsp; (within the rules of this task) &nbsp; is: &nbsp; '''5074'''

<br>(which, &nbsp; of course, &nbsp; isn't the lowest positive sum that can't be expressed).

 

 

 

=={{header|Ada}}==

Between any two consecutive digits, there can be a "+", a "-", or no operator. E.g., the digits "4" and "5" occur in the string as either of the following three substrings: "4+5", "4-5", or "45". For the first digit, we only have two choices: "+1" (written as "1"), and "-1". This makes 2*3^8 (two times (three to the power of eight)) different strings. Essential is the generic function Eval in the package Sum_To calls the procedure Callback for each such string Str, with the number Int holding the sum corresponding to the evaluation of Str. The second generic procedure Print is for convenience. If the Sum fits the condition, i.e., if Print_If(Sum, Number), then Print writes Sum = Str to the output.

 

generic

procedure Print(S: String; Sum: Integer);

 

 

The implementation of Eval follows the observation above: Eval calls Rec_Eval with the initial string "1" and "-1". For each call, Rec_Eval recursively evaluates a ternary tree with 3^8 leafs. At each leaf, Rec_Eval calls Callback. The implementation of Print is straightforward.

 

 

package body Sum_To is

end Print;

 

===The First Subtask===

Given the package Sum_To, the solution to the first subtask (print all solution for the sum 100) is trivial: Eval_100 calls Print_100 for all 2*3^8 strings, and Print_100 writes the output if the sum is equal to 100.

 

 

procedure Sum_To_100 is

begin

Eval_100;

 

{{out}}

For the three other subtasks, we maintain an ordered map of sums (as the keys) and counters for the number of solutions (as the elements). The procedure Generate_Map generates the Map by calling the procedure Insert_Solution for all 2*3^8 solutions. Finding (1) the sum with the maximal number of solutions, (2) the first sum>=0 without a solution and (3) the ten largest sums with a solution (extra credit) are done by iterating this map.

 

use Ada.Text_IO;

 

end loop;

New_Line;

 

{{out}}

 

=={{header|Aime}}==

index r, w;

 

break;

}

{{Out}}

<pre>123-45-67+89

 

=={{header|ALGOL 68}}==

# find the numbers the string 123456789 ( with "+/-" optionally inserted #

# before each digit ) can generate #

# we don't distinguish between strings starting "+1" and starting " 1" #

FOR s1 FROM -1 TO 0 DO

OD

OD

OD;

 

FI

OD;

# find the smallest positive number that has no solutions #

BOOL have solutions := TRUE;

print( ( newline ) )

 

{{out}}

<pre>

{{Trans|JavaScript}}

AppleScript is essentially out of its depth at this scale. The first task (number of distinct paths to 100) is accessible within a few seconds. Subsequent tasks, however, terminate only (if at all) after impractical amounts of time. Note the contrast with the lighter and more optimised JavaScript interpreter, which takes less than half a second to return full results for all the listed tasks.

 

property pSigns : {1, 0, -1} --> ( + | unsigned | - )

end script

end if

{{Out}}

<pre>Sums to 100:

 

=={{header|AutoHotkey}}==

for k, v in (sum2num(100))

output .= k "`n"

DllCall("msvcrt.dll\" v, "Int64", value, "Str", s, "UInt", OutputBase, "CDECL")

return s

{{out}}

<pre>

{{trans|Fortran IV}}

Awk is a weird language: there are no integers, no switch-case (in the standard language version), programs are controlled by data flow, the interpreter speed is moderate. The advantage of Awk are associative arrays, used here for counting how many times we get the same sum as the result of calculations.

# RossetaCode: Sum to 100, AWK.

#

limit = best

}

{{Out}}

<pre>Show all solutions that sum to 100

{{Works with|Microsoft Visual Studio|2015}}

Warning: '''this version requires at least four byte integers.'''

* RossetaCode: Sum to 100, C99, an algorithm using ternary numbers.

*

return 0;

{{Out}}

<pre>

{{Works with|GCC|5.1}}

Warning: '''this program needs at least four byte integers'''.

* RossetaCode: Sum to 100, C11, MCU friendly.

*

return 0;

{{Out}}

<pre>Show all solutions that sum to 100

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

using System.Linq;

return left;

}

{{out}}

<pre>

{{Works with|Microsoft Visual Studio|2010}}

For each expression of sum s, there is at least one expression whose sum is -s. If the sum s can be represented by n expressions, the sum -s can also be represented by n expressions. The change of all signs in an expression change the sign of the sum of this expression. For example, -1+23-456+789 has the opposite sign than +1-23+456-789. Therefore only the positive sum with the maximum number of solutions is shown. The program does not check uniqueness of this sum. We can easily check (modifying the program) that: sum 9 has 46 solutions; sum -9 has 46 solutions; any other sum has less than 46 solutions.

* RossetaCode: Sum to 100, C++, STL, OOP.

* Works with: MSC 16.0 (MSVS2010); GCC 5.1 (use -std=c++11 or -std=c++14 etc.).

 

return 0;

{{Out}}

<pre>

 

=={{header|Common Lisp}}==

"Takes a list of digits as argument"

(if (null lst)

(parse-integer (format nil "~{~d~}" lst)) ))

 

{{out}}

<pre>

=={{header|D}}==

{{Trans|Java}}

 

void main() {

}

}

 

{{out}}

=={{header|Delphi}}==

See [https://rosettacode.org/wiki/Sum_to_100#Pascal Pascal].

 

=={{header|Elixir}}==

def to(val) do

generate

Sum.max_solve

Sum.min_solve

 

{{out}}

3456788, 3456786]

</pre>

 

=={{header|F_Sharp|F#}}==

(*

Generate the data set

yield! fn -1 2 0 -1 "-1"

}

{{out}}

N |> Seq.filter(fun n->n.g=100) |> Seq.iter(fun n->printfn "%s" n.n)

<pre>

1+2+3-4+5+6+78+9

-1+2-3+4+5+6+78+9

</pre>

let n,g = N |> Seq.filter(fun n->n.g>=0) |> Seq.countBy(fun n->n.g) |> Seq.maxBy(snd)

printfn "%d has %d solutions" n g

<pre>

9 has 46 solutions

</pre>

match N |> Seq.filter(fun n->n.g>=0) |> Seq.distinctBy(fun n->n.g) |> Seq.sortBy(fun n->n.g) |> Seq.pairwise |> Seq.tryFind(fun n->(snd n).g-(fst n).g > 1) with

|Some(n) -> printfn "least non-value is %d" ((fst n).g+1)

|None -> printfn "No non-values found"

<pre>

least non-value is 211

</pre>

N |> Seq.filter(fun n->n.g>=0) |> Seq.distinctBy(fun n->n.g) |> Seq.sortBy(fun n->(-n.g)) |> Seq.take 10 |> Seq.iter(fun n->printfn "%d" n.g )

<pre>

123456789

{{works with|Gforth|0.7.3}}

This solution uses <code>EVALUATE</code> on a string buffer to compute the sum. Given the copious string manipulations, <code>EVALUATE</code>, and the large byte-array used to keep sum counts, this implementation is optimized neither for speed nor for memory. On my machine it runs in about 3.8 seconds, compared to the speed-optimized C solution which runs in about 0.005 seconds.

CREATE 0OPS CHAR - C, CHAR # C,

CREATE BUFF 43 C, 43 CHARS ALLOT

: .SOLUTIONS cr ." Solutions that sum to 100:"

BEGIN SYNTH EVALUATE REPORT INDX+ UNTIL ;

{{Out}}

Note: must start Gforth with a larger-than-default dictionary size:

=== Fortran 95 ===

{{works with|gfortran|5.1}}

!

! Find solutions to the 'sum to one hundred' puzzle.

ivalue = ievaluate(icode)

print *, ivalue, ' = ', s

{{Out}}

<pre>

 

===Batch processing===

PARAMETER (NDIGITS = 9, TARGET = 100)

INTEGER*1 OP(NDIGITS) !A set of operation codes, associated with each digit.

WRITE (MSG,322) VALUE(LOOP - 9:LOOP) !Surely LOOP > 9.

322 FORMAT ("The ten highest sums: ",10(I0:","))

 

Results:

The lowest positive sum that can't be expressed is 211

The ten highest sums: 3456786,3456788,3456790,3456792,3456801,12345669,12345687,23456788,23456790,123456789

</pre>

 

=={{header|Frink}}==

digits = array[1 to 9]

opList = makeArray[[8], ["", " + ", " - "]]

for i = size-10 to size-1

println[freq@i@0]

{{out}}

<pre>

=={{header|Go}}==

{{trans|C}}

 

import (

fmt.Println(e)

}

{{out}}

<pre>

 

=={{header|Haskell}}==

import Data.Char (intToDigit)

 

data Sign

| Minus

deriving (Eq, Show)

 

universe :: [[(Int, Sign)]]

universe =

 

allNonNegativeSums :: [Int]

 

uniqueNonNegativeSums :: [Int]

asSum :: [(Int, Sign)] -> Int

asSum xs =

where

(n, s) = foldr readSign (0, []) xs

readSign (i, x) (n, s)

| x == Unsigned = (n, intToDigit i : s)

| otherwise =

n

 

asString :: [(Int, Sign)] -> String

| x == Unsigned = intToDigit i : s

| otherwise =

 

main :: IO ()

main =

putStrLn $

where

maybeReport (Just (x, _)) = show x

{{Out}}

(Run in Atom editor, through Script package)

Since J has no verb precedence, -1-2 would evaluate to 1 and not to -3. That's why I decided to multiply each of the partitions of '123456789' (like '123','45', '6', '78', '9') with each possible +1/-1 vectors of length 9 (like 1 1 -1 1 -1 -1 1 1 -1) and to add up the results. This leads to 512*256 results, that of course include a lot of duplicates. To use directly ~. (nub) on the 512x256x9 vector is very slow and that's why I computed a sort of a hash to use it to get only the unique expressions. The rest is trivial - I check which expressions add up to 100; sort the sum vector and find the longest sequence ot repeating sums; get the 10 largest sums and finnaly check which sum differs with more then 1 from the previous one.

 

p =: ,"2".>(#: (+ i.)2^8) <;.1 '123456789'

m =. (9$_1x)^"1#:i.2^9

'Ten largest:';,.(->:i.10){ss

'First not expressible:';>:pos{~ 1 i.~ 1<|2-/\pos

{{out}}

<pre>

{{trans|C++}}

For each expression of sum s, there is at least one expression whose sum is -s. If the sum s can be represented by n expressions, the sum -s can also be represented by n expressions. The change of all signs in an expression change the sign of the sum of this expression. For example, -1+23-456+789 has the opposite sign than +1-23+456-789. Therefore only the positive sum with the maximum number of solutions is shown. The program does not check uniqueness of this sum. We can easily check (modifying the program) that: sum 9 has 46 solutions; sum -9 has 46 solutions; any other sum has less than 46 solutions.

* RossetaCode: Sum to 100, Java 8.

*

}

}

{{Out}}

<pre>Show all solutions that sum to 100

===ES5===

{{Trans|Haskell}}

'use strict';

 

show(take(10, uniqueNonNegativeSums.sort(flip(compare))))

].join('\n') + '\n';

 

{{Out}}

===ES6===

{{Trans|Haskell}}

'use strict';

 

show(take(10, uniqueNonNegativeSums.sort(flip(compare))))

].join('\n') + '\n';

 

{{Out}}

{{Works with|Microsoft Windows Script Host}}

{{Trans|AWK}}

 

function SumTo100()

}

{{Out}}

<pre>Show all solutions that sum to 100

 

'''All possible sums'''

def generate(n):

def pm: ["+"], ["-"], [""];

# Pretty-print a "sum", e.g. ["",1,"+", 2] => 1 + 2

def pp: map(if . == "+" or . == "-" then " " + . else tostring end) | join("");

'''Solutions to "Sum to 100" problem'''

{{out}}

<pre>

For brevity, we define an efficient function for computing a histogram in the form of a JSON object, and

a helper function for identifying the values with the n highest frequencies.

 

# Emit an array of [ value, frequency ] pairs

| sort_by(.[1])

| .[(length-n):]

 

'''Maximum number of solutions'''

{{out}}

<pre>[["9",46]]</pre>

 

'''Ten most frequent sums'''

{{out}}

<pre>[["9",46],["27",44],["1",43],["21",43],["15",43],["45",42],["3",41],["5",40],["7",39],["17",39]]</pre>

 

'''First unsolvable'''

first( foreach s as $i (null;

if . == null or $i == . or $i == .+1 then $i else [.+1] end;

select(type == "array") | .[0]));

 

{{out}}

211

 

'''Ten largest sums'''

{{out}}

[3456786,3456788,3456790,3456792,3456801,12345669,12345687,23456788,23456790,123456789]

 

=={{header|Julia}}==

expr(p::String...)::String = @sprintf("%s1%s2%s3%s4%s5%s6%s7%s8%s9", p...)

println("\nHighest sums representable:")

foreach(println, hsums)

<pre>100 =

1+23-4+56+7+8+9

=={{header|Kotlin}}==

{{trans|C++}}

 

class Expression {

println("\nThe ten highest numbers that do have solutions are:\n")

stat.countSum.keys.toIntArray().sorted().reversed().take(10).forEach { Expression.print(it) }

 

{{out}}

=={{header|Lua}}==

{{trans|C}}

function compareExpressionBySum(a, b)

return a.sum - b.sum

end

limit = best

{{out}}

<pre>Show all solutions that sum to 100

3456786 = -1-2+3456789</pre>

 

Defining all possible sums:

Sums to 100:

{{out}}

<pre>-1+2-3+4+5+6+78+9

 

Maximum number of solutions:

{{out}}

<pre> <|9 -> 46, -9 -> 46|> </pre>

 

First unsolvable:

{{out}}

<pre>211</pre>

 

Ten largest sums:

{{out}}

<pre> 123456789 123456789

=={{header|Modula-2}}==

{{trans|C}}

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

 

ReadChar

{{out}}

<pre>Show all solutions that sum to 100

 

=={{header|Nim}}==

 

var

liS = split(li," ")

for i in liS:

echo "Valeur à atteindre : ",aAtteindre

echo "Plus grandes valeurs pouvant être atteintes :"

for i in 1..10:

{{out}}

<pre>Valeur à atteindre : 100

{{works with|Lazarus}}

{{trans|C}}

 

Find solutions to the "sum to one hundred" puzzle.

limit := best;

end

{{Out}}

<pre>Show all solutions that sum to 100

=={{header|Perl}}==

{{works with|Perl|5.10}}

use warnings;

use strict;

 

say 'Show the ten highest numbers that can be expressed';

{{Out}}

<pre>Show all solutions that sum to 100

===oneliner version===

The first task posed can be solved simply with (pay attention to doublequotes around the program: adjust for you OS):

perl -E "say for grep{eval $_ == 100} glob '{-,}'.join '{+,-,}',1..9"

 

While the whole task can be solved by:

perl -MList::Util="first" -E "@c[0..10**6]=(0..10**6);say for grep{$e=eval;$c[$e]=undef if $e>=0;$h{$e}++;eval $_==100}glob'{-,}'.join'{+,-,}',1..9;END{say for(sort{$h{$b}<=>$h{$a}}grep{$_>=0}keys %h)[0],first{defined $_}@c;say for(sort{$b<=>$a}grep{$_>0}keys %h)[0..9]}"

which outputs

<pre>

Admittedly, categorising them into 3429 bins is slightly more effort, but otherwise I am somewhat bemused by all the applescript/javascript/Haskell shenanegins.<br>

 

<span style="color: #008080;">enum</span> <span style="color: #000000;">SUB</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">NOP</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ADD</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span>

<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ADD</span>

<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>

<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">i</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>

<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">done</span> <span style="color: #008080;">do</span>

<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>

<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">solns</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">maxl</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solns</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>

<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">highest</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">10</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The 10 highest sums: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">highest</span><span style="color: #0000FF;">})</span>

 

{{Out}}

The lowest positive sum that cannot be expressed: 211

The 10 highest sums: {123456789,23456790,23456788,12345687,12345669,3456801,3456792,3456790,3456788,3456786}

</pre>

 

=={{header|Python}}==

 

 

 

max_solve()

min_solve()

 

{{out}}

Mostly the same algorithm, but both shorter and faster.

 

from collections import defaultdict, Counter

 

print("Ten highest sums")

for k in reversed(v[-10:]):

 

{{out}}

=={{header|Racket}}==

 

 

(define list-partitions

(check-equal? (partition-digits-to-numbers '()) '(()))

(check-equal? (partition-digits-to-numbers '(1)) '((1)))

 

{{out}}

{{works with|Rakudo|2017.03}}

 

my $N = 10;

my @ops = ['-', ''], |( [' + ', ' - ', ''] xx 8 );

}

 

{{out}}

<pre>12 solutions for sum 100:

 

=={{header|REXX}}==

parse arg LO HI . /*obtain optional arguments from the CL*/

if LO=='' | LO=="," then LO= 100 /*Not specified? Then use the default.*/

if LO\==00 then say right(y, 9) 'solution's(#, , " ") 'found for' ,

right(j, length(HI) ) left('', #, "─")

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ruby}}==

 

end

 

 

 

 

 

{{out}}

<pre>

</pre>

 

=={{header|Scala}}==

def main(args: Array[String]): Unit = {

val exps = expressions(9).map(str => (str, eval(str)))

case _ => ""

}

{{out}}

<pre>All 12 solutions that sum to 100:

=={{header|Sidef}}==

{{trans|Ruby}}

var x = ['-', '']

var y = ['+', '-', '']

say "Sum of #{n} has the maximum number of solutions: #{solutions.len}"

say "Lowest positive sum that can't be expressed : #{min_solve()}"

{{out}}

<pre>

 

=={{header|Tcl}}==

for {set i 0} {$i <= 13121} {incr i} {

set i3 [format %09d [dec2base 3 $i]]

return $res

}

<pre>

~ $ ./sum_to_100.tcl

highest 10:

123456789 23456790 23456788 12345687 12345669 3456801 3456792 3456790 3456788 3456786

</pre>

 

 

Another interesting thing this program can do is solve for other sets of numbers easily, as neither the number of digits, nor the digit sequence itself, is hard-coded. You could solve for the digits 1 through 8, for example, or the digits starting at 9 and going down to 1. One can even override the target sum (of 100) parameter, if you happen to be interested in another number.

Function plusOne(iAry() As Integer, spot As Integer) As Integer

Dim spotLim As Integer = If(spot = 0, 1, 2) ' The first "digit" has a lower limit.

Sub Main()

Solve100() ' if interested, try this: Solve100("987654321")

{{out}}

<pre>List of solutions that evaluate to 100:

{{libheader|Wren-math}}

{{libheader|Wren-sort}}

 

var Op = Enum.create("Op", ["ADD", "SUB", "JOIN"])

var res = stat.countSum.keys.toList

Sort.quick(res)

 

{{out}}

=={{header|zkl}}==

Taking a big clue from Haskell and just calculate the world.

(9).pump(List,fcn(n){ split("123456789"[n,*]) }) // 45

.apply(fcn(ns){ ns.extend(ns.copy().apply('*(-1))) }); // 90

}

// "123" --> (1,12,123)

slns:=allSums.find(N,T);

if(printSolutions) println("%d solutions for N=%d".fmt(slns.len(),N));

'wrap([(k,v)]){ v=v.len(); ms.holds(v) and T(k.toInt(),v) or Void.Skip })

.sort(fcn(kv1,kv2){ kv1[1]>kv2[1] }) // and sort

{{out}}

<pre>