Sum to 100: Difference between revisions

 

Example:

 

Show all output here.

 

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

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

<br>

 

 

 

<br><br>

=={{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}}

Highest sum: 123456789

Next nine: 23456790 23456788 12345687 12345669 3456801 3456792 3456790 3456788 3456786</pre>

 

=={{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}}==

return

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

1+2+34-5+67-8+9

123+45-67+8-9

123-4-5-6-7+8-9

=={{header|AWK}}==

{{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

 

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

 

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

using System.Collections.Generic;

using System.Linq;

return left;

}

{{out}}

<pre>

</pre>

 

 

 

 

 

 

"Takes a list of digits as argument"

(if (null lst)

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

 

{{out}}

<pre>

 

The other subtasks are not yet implemented.

 

=={{header|D}}==

{{Trans|Java}}

 

void main() {

}

}

 

{{out}}

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

 

 

=={{header|Elixir}}==

def to(val) do

generate

Sum.max_solve

Sum.min_solve

 

{{out}}

</pre>

 

 

=={{header|Forth}}==

{{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.

CHARACTER*1 OPNAME(-1:+1) !Encodement of the operations.

PARAMETER (OPNAME = (/"-"," ","+"/)) !These will look nice.

100 LOOP = LOOP + 1 !Here we go again.

N = 0 !Clear the number.

IF (OP(I).EQ.0) THEN !A no-operation?

END IF !So much for that step.

END DO !On to the next.

VALUE(LOOP) = N !Save the value for later...

IF (N.EQ.TARGET) THEN !Well then?

101 FORMAT (10(A1,I1)) !Single-character operation codes, single-digit number parts.

CALL DEBLANK(TEXT,L) !Squeeze out the no-operations, so numbers are together.

102 FORMAT (I5,": ",A) !This should do.

END IF !So much for that.

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

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

 

Results:

</pre>

 

}

{{out}}

<pre>

</pre>

<pre>

</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...)

function genexpr()::Vector{String}

op = ["+", "-", ""]

end

using DataStructures

function allexpr()::Dict{Int,Int}

rst = DefaultDict{Int,Int}(0)

for e in genexpr()

rst[val] += 1

end

return rst

end

function maxsolve()::Dict{Int,Int}

ae = allexpr()

vmax = maximum(values(ae))

f == vmax

end

return sort!(sums; rev=true)[1:n]

end

println("100 =")

foreach(println, solutions)

 

println("\nMax number of solutions:")

@printf("%3i -> %2i\n", v, f)

end

println("\nHighest sums representable:")

<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}}

</pre>

 

 

 

 

 

{{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

1-2+3456789 3456788

-1-2+3456789 3456786 </pre>

 

=={{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

</pre>

 

 

 

 

 

}

 

 

 

 

 

 

 

 

 

 

 

{{Out}}

<pre>

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}}

Show the ten highest numbers that can be expressed using the rules for this task

'(123456789 23456790 23456788 12345687 12345669 3456801 3456792 3456790 3456788 3456786)</pre>

 

=={{header|REXX}}==

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

@@= 'number of solutions: '; say

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

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

<pre>

 

=={{header|Ruby}}==

 

end

 

 

 

 

 

{{out}}

<pre>

</pre>

 

=={{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:

123456789 23456790 23456788 12345687 12345669

3456801 3456792 3456790 3456788 3456786</pre>

 

=={{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>