Sum Embedded Numbers

May 15, 2018

We break the problem into two parts: function next-number gets the next number from the input string while resetting the string for the next call, and function sum-embedded-numbers iterates through the numbers returned by next-number, returning the sum when the input string is exhausted:

(define (next-number xs)
  (let loop ((xs xs))
    (if (null? xs) (values #f #f)
      (if (not (char-numeric? (car xs)))
          (loop (cdr xs))
          (let loop ((xs xs) (n 0))
            (if (null? xs) (values n xs)
              (if (char-numeric? (car xs))
                  (loop (cdr xs)
                        (+ (* n 10)
                           (- (char->integer (car xs))
                              (char->integer #\0))))
                  (values n xs))))))))

(define (sum-embedded-numbers str)
  (let loop ((xs (string->list str)) (sum 0))
    (call-with-values
      (lambda () (next-number xs))
      (lambda (n xs)
        (if n (loop xs (+ sum n)) sum)))))

The outer loop in next-number advances past any initial non-digits, and the inner loop collects the values of the number n. Here’s the example:

> (sum-embedded-numbers "11aa22bb33cc44")
110

You can run the program at https://ideone.com/GZ5Ltn.

Posted by programmingpraxis

Filed in Exercises

35 Comments »

35 Responses to “Sum Embedded Numbers”

Milbrae said

May 15, 2018 at 2:26 PM

Python

def embeddednumbers(s):
    sd, cd = 0, 0

    # single digit numbers
    for d in s:
        v = ord(d)
        if v >= 0x30 and v <= 0x39:
            sd += v - 0x30

    # consecutive numbers
    l = len(s)
    i = 0
    while i < l:
        v = ord(s[i])
        if v >= 0x30 and v <= 0x39:
            j = 1
            while i + j < l:
                v = ord(s[i+j])
                if v >= 0x30 and v <= 0x39:
                    j += 1
                else:
                    break
            cd += int(s[i:i+j])
        i += j

    return sd, cd

if __name__ == "__main__":
    ''
    text = "11aa22bb33cc44"
    print (text + " = " + str(embeddednumbers(text)))

    text = "1k23jk34jk56jk3454"
    print (text + " = " + str(embeddednumbers(text)))

Sample output:
11aa22bb33cc44 = (20, 110)
1k23jk34jk56jk3454 = (40, 3568)

Pascal Bourguignon said

May 15, 2018 at 3:24 PM

(defun sum-embedded-cardinals (string)
  (loop
    :for start := (position-if (function digit-char-p) string)
      :then (position-if (function digit-char-p) string :start end)
    :for (cardinal end) := (when start
                             (multiple-value-list
                              (parse-integer string :start start :junk-allowed t)))
    :while cardinal
    :sum cardinal))

(defun test/sum-embedded-cardinals ()
  (assert (= 0   (sum-embedded-cardinals "")))
  (assert (= 0   (sum-embedded-cardinals "foo")))
  (assert (= 42  (sum-embedded-cardinals "42")))
  (assert (= 42  (sum-embedded-cardinals "-42")))
  (assert (= 42  (sum-embedded-cardinals "-42-")))
  (assert (= 10  (sum-embedded-cardinals "1-2-3-4")))
  (assert (= 10  (sum-embedded-cardinals "    1     2,    3;    4.  ")))
  (assert (= 110 (sum-embedded-cardinals "11aa22bb33cc44")))
  :success)


(test/sum-embedded-cardinals)
;; --> :success

Milbrae said

May 15, 2018 at 3:41 PM

Tested the samples of Pascal and found a misplacement of a variable. Should be fixed now.

def embeddednumbers(s):
    sd, cd = 0, 0

    # single digit numbers
    for d in s:
        v = ord(d)
        if v >= 0x30 and v <= 0x39:
            sd += v - 0x30

    # consecutive numbers
    l = len(s)
    if l == 0: return sd, 0

    i = 0
    while i < l:
        v = ord(s[i])
        j = 1
        if v >= 0x30 and v <= 0x39:
            while i + j < l:
                v = ord(s[i+j])
                if v >= 0x30 and v <= 0x39:
                    j += 1
                else:
                    break
            cd += int(s[i:i+j])
        i += j

    return sd, cd

if __name__ == "__main__":
    ''
    data = ["", "42", "-42", "-42-", "1-2-3-4", "    1     2,    3;    4.  ", "11aa22bb33cc44"]
    for text in data:
        print (str(embeddednumbers(text)) + " = " + text)

Output is:
(0, 0) =
(6, 42) = 42
(6, 42) = -42
(6, 42) = -42-
(10, 10) = 1-2-3-4
(10, 10) = 1 2, 3; 4.
(20, 110) = 11aa22bb33cc44

Phil Runninger said
May 15, 2018 at 6:02 PM
Here’s a one-line Erlang solution
```
lists:sum(lists:foldl(fun(X,[H|T]) when X >= $0 andalso X =< $9 -> [H*10+X-$0 | T]; (X,L) -> [0|L] end, [0], "11aa22bb33cc44")).
```
and an attempt to explain it:
```
lists:sum(
    lists:foldl(
        fun(X,[H|T]) when X >= $0 andalso X =< $9 -> [H*10+X-$0 | T];
           (X,L) -> [0|L]
        end, 
        [0], 
        "11aa22bb33cc44")
    ).
```
Start with a list containing the value 0 (line 6). For each character X (lines 3,4) in the string (line 7), if it’s between “0” and “9”, multiply the head of the list by 10, add X to it, and put that back at the head of the list (line 3); and if X is not numeric, tack on another 0 to the list (line 4). When lists:foldl is done, you have the list of numbers [44,0,33,0,22,0,11], which lists:sums to 110 (line 1).
Steve said
May 15, 2018 at 6:53 PM
Cache/Mumps version
```
SUMEMBNUM(STR) ;
         N SUBTOTAL,TOTAL
         S TOTAL=0
         F  S SUBTOTAL="" D GETNUMS(.STR) S TOTAL=TOTAL+SUBTOTAL D FINDNEXTNUMS(.STR) Q:STR=""
         Q TOTAL
         ;
GETNUMS(STR)  ;
         N CHAR
         F  Q:STR=""  S CHAR=$A(STR) Q:CHAR<48!(CHAR>57)  S SUBTOTAL=SUBTOTAL_$C(CHAR),STR=$E(STR,2,$L(STR))
         Q
         ;
FINDNEXTNUMS(STR)  ;
         N CHAR
         F  Q:STR=""  S CHAR=$A(STR) Q:CHAR'<48&(CHAR'>57)  S STR=$E(STR,2,$L(STR))
         Q
```
f i=””,”foo”,”42″,”-42″,”-42-“,”1-2-3-4″,” 1 2, 3; 4. “,”11aa22bb33cc44″ w !,””””,i,””” –>”,?40,””””,$$SUMEMBNUM(i),””””

“” –> “0”
“foo” –> “0”
“42” –> “42”
“-42” –> “42”
“-42-” –> “42”
“1-2-3-4” –> “10”
” 1 2, 3; 4. ” –> “10”
“11aa22bb33cc44” –> “110”

sbocq said

May 15, 2018 at 8:34 PM

Bash.

function sum_embedded {
  local tot=0 acc="" c i

  while read -r -n1 c; do
    i=$(printf "%d\n" "'$c");
    if (( i >= 0x30 && i <= 0x39 )); then
      acc+=$c;
    elif [[ -n ${acc} ]]; then
      (( tot+=acc ))
      acc=""
    fi
  done <<< "$1"

  echo $tot
}

Test:

$ for assert in "foo=0" \
                "42=42" \
                "-42=42" \
                "-42-=42" \
                "1-2-3-4=10" \
                "    1     2,    3;    4.  =10" \
                "11aa22bb33cc44=110"; do
    echo -en "${assert}="
    IFS='=' read s expect <<< "${assert}"
    (( $(sum_embedded "$s") == expect )) && echo -e "OK" || echo -e "FAIL!"
  done|column -s$'=' -t

foo=0                          OK
42=42                          OK
-42=42                         OK
-42-=42                        OK
1-2-3-4=10                     OK
    1     2,    3;    4.  =10  OK
11aa22bb33cc44=110             OK

sbocq said

May 15, 2018 at 9:32 PM

ClojureScript.

(defn sum-embedded [s]
  (first (reduce (fn [[tot acc] c] (cond (<= 0x30 (.charCodeAt c 0) 0x39) [tot (str acc c)]
                                         (not (= acc "")) [(+ tot (js/parseInt acc)) ""]
                                         :else [tot acc]))
                 [0 ""]
                 (str s "_"))))

Test:

(doseq ([s expect] [["foo" 0]
                    ["42" 42]
                    ["-42" 42]
                    ["-42-" 42]
                    ["1-2-3-4" 10]
                    ["1     2,    3;    4.  " 10]
                    ["11aa22bb33cc44" 110]])
  (print s "=" expect " " (if (= (sum-embedded s) expect) "OK" "FAIL")))

foo = 0   OK
42 = 42   OK
-42 = 42   OK
-42- = 42   OK
1-2-3-4 = 10   OK
1     2,    3;    4.   = 10   OK
11aa22bb33cc44 = 110   OK
nil

Milbrae said

May 15, 2018 at 9:46 PM

Re-implementation of my Python solution in D

import std.stdio;
import std.range;
import std.string;
import std.conv;

ulong embedded(string s)
{
    ulong l = s.length;
    ulong sum = 0;

    if (l > 0) {
        ulong i = 0;
        while (i < l) {
            byte v = cast(byte)s[i];
            ulong j = 1;
            if (v >= 0x30 && v <= 0x39) {
                while (i + j < l) {
                    v = cast(byte)s[i+j];
                    if (v >= 0x30 && v <= 0x39) {
                        j++;
                    }
                    else {
                        break;
                    }
                }
                ulong t = to!ulong(s[i..(i+j)]);
                sum += t;
            }
            i += j;
        }
    }

    return sum;
}

void main()
{
    string[] data = ["", "42", "-42", "-42-", "1-2-3-4", "    1     2,    3;    4.  ", "11aa22bb33cc44"];

    foreach (text; data) {
        text.embedded.writeln;
    }
}

Globules said

May 16, 2018 at 1:36 AM

import Data.Char (isDigit)
import Data.List.Split (wordsBy)

embeddedSum :: (Read a, Integral a) => String -> a
embeddedSum = sum . map read . wordsBy (not . isDigit)

main :: IO ()
main = do
  let strs = ["", "foo", "42", "-42", "-42-", "1-2-3-4",
              "1     2,    3;    4.  ", "11aa22bb33cc44"]
  mapM_ (print . embeddedSum) strs

$ ./embedsum
0
0
42
42
42
10
10
110

Daniel said

May 16, 2018 at 4:58 AM

Here’s a solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int sum_embedded(char* str) {
  size_t i = strlen(str);
  int sum = 0;
  int place = 1;
  while (1) {
    if (i == 0) break;
    --i;
    char c = str[i];
    if (c < '0' || c > '9') {
      place = 1;
      continue;
    }
    sum += place * (c - '0');
    place *= 10;
  }
  return sum;
}

int main(int argc, char* argv[]) {
  if (argc != 2) {
    fprintf(stderr, "Usage: %s <STRING>\n", argv[0]);
    return EXIT_FAILURE;
  }
  int sum = sum_embedded(argv[1]);
  printf("%d\n", sum);
  return EXIT_SUCCESS;
}

Example:

$ ./sum_embedded "11aa22bb33cc44"
110

sbocq said

May 16, 2018 at 8:52 PM

I really like the Haskell solution of Globules. The closest I could come with in ClojureScript, without using regex, is with partition-by:

(defn sum-embedded [s]
  (->> (partition-by #(<= 0x30 (.charCodeAt % 0) 0x39) s)
       (map (comp cljs.reader/read-string (partial apply str)))
       (filter integer?)
       (reduce +)))

Test:

(doseq ([s expect] [["" 0] ["foo" 0] ["42" 42] ["-42" 42] ["-42-" 42] ["1-2-3-4" 10]
                    ["1     2,    3;    4.  " 10] ["11aa22bb33cc44" 110]])
  (print s "=" expect " " (if (= (sum-embedded s) expect) "OK" "FAIL")))

= 0 OK
foo = 0 OK
42 = 42 OK
-42 = 42 OK
-42- = 42 OK
1-2-3-4 = 10 OK
1 2, 3; 4. = 10 OK
11aa22bb33cc44 = 110 OK

Daniel said

May 16, 2018 at 11:22 PM

Here’s a solution in Python.

def sum_embedded(s):
  s = ''.join(c if c.isdigit() else ' ' for c in s)
  return sum(map(int, s.split()))

s = "11aa22bb33cc44"
print sum_embedded(s)

Output:

Daniel said
May 16, 2018 at 11:24 PM
Here’s the same solution using double quotes, to attempt to improve the formatting.
```
def sum_embedded(s):
  s = "".join(c if c.isdigit() else " " for c in s)
  return sum(map(int, s.split()))
```

Daniel said

May 17, 2018 at 2:20 AM

Here’s another solution in C.

#include <stdio.h>
#include <stdlib.h>

int sum_embedded(char* str) {
  int sum = 0;
  char* endptr;
  while (1) {
    sum += strtol(str, &endptr, 10);
    if (*endptr == '\0') break;
    str = endptr + 1;
  }
  return sum;
}

int main(int argc, char* argv[]) {
  if (argc != 2) {
    fprintf(stderr, "Usage: %s <STRING>\n", argv[0]);
    return EXIT_FAILURE;
  }
  int sum = sum_embedded(argv[1]);
  printf("%d\n", sum);
  return EXIT_SUCCESS;
}

Example:

$ ./sum_embedded "11aa22bb33cc44"
110

programmingpraxis said

May 17, 2018 at 3:15 AM

@sbocq: It’s not hard to adapt Globules’ Haskell solution to Scheme. Start with a variant of the Standard Prelude’s string-split function that takes a predicate instead of just comparing to a character:

(define (string-split-by pred? str)
  (define (f cs xs) (cons (list->string (reverse cs)) xs))
  (let loop ((ss (string->list str)) (cs (list)) (xs (list)))
    (cond ((null? ss) (reverse (if (null? cs) xs (f cs xs))))
          ((pred? (car ss)) (loop (cdr ss) '() (f cs xs)))
          (else (loop (cdr ss) (cons (car ss) cs) xs)))))

Then just build a pipeline of Scheme functions:

(define (sum-embedded-numbers str)
  (sum
    (filter integer?
      (map string->number
        (string-split-by (complement char-numeric?)
          str)))))

And here’s the result:

> (sum-embedded-numbers "11aa22bb33cc44")
110

Be sure you understand the output of string-split-by, which is slightly different than the Haskell wordsBy function.

sbocq said
May 17, 2018 at 6:39 AM
Oh sure, I could have reimplemented split-by myself. But for these exercises, I’m interested in how much bang you get for the bucks sticking to the language and its standard library. In my eyes, you give up a bit of that if you have to resort to custom loops or recursion to implement split-by. This is why I like the Haskell solution.

V said

May 17, 2018 at 7:01 AM

In Ruby. An imperative and a functional version.

def sum_embedded_numbers_imperatibely(str)
  sum = 0
  current_val = nil

  str.chars do |c|
    if (Integer(c) rescue false)
      current_val = current_val ? current_val << c : c
    elsif current_val
      sum += current_val.to_i
      current_val = nil
    end
  end
  sum += current_val.to_i
  sum
end

def sum_embedded_numbers_functionaly(str)
  str
    .chars
    .chunk  { |char| (Integer(char) rescue false) }
    .select { |is_match, _| is_match }
    .sum    { |_,v| v.join.to_i }
end

# Test

def test(output, target)
  puts "target: #{target}"
  puts "output: #{output}"
  puts "pass: #{output == target}"
  puts
end

test sum_embedded_numbers_imperatibely("11aa22bb33cc44"), 110
test sum_embedded_numbers_functionaly("11aa22bb33cc44"),  110

Output:

target: 110
output: 110
pass: true

target: 110
output: 110
pass: true

sbocq said

May 17, 2018 at 8:51 PM

Another Bash solution inspired from Daniel’s nice use of strtol in his C version:

function sum_embedded {
  local tot=0 n
  while read -d' ' n; do
    (( tot+=n ))
  done < <(tr -c '[:digit:]' $' ' <<< "$1")
  echo ${tot}
}

Example:

$ sum_embedded 11aa22bb33cc44
110

Mike said
May 17, 2018 at 9:46 PM
Python
```
import operator as op
import itertools as it

isdigit = op.methodcaller('isdigit')

def sum_embedded_numbers(s):
    return sum(int(''.join(vs)) for k,vs in it.groupby(s, key=isdigit) if k)
```
Uses ‘groupby’ to break the input string into groups of characters according to the function provided as the ‘key’ parameter, e.g., ‘isdigit’. If the key, k, is True, the characters in the group are concatenated and converted to an integer. The sum of the integers is returned.

Here is a link to a pastebin that lets you execute the code.
Try it online!
WWW.ХХХ.FJУWV.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.SGDLСQ.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.ХQТSРN.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.SРNСР.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.GЕРBJZ.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.JIIZIР.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.FUIОB.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.SРNСР.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.ТАJКХР.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.FJУWV.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.UЕLЕЕS.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.GGZNЕ.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.ЕWZJJ.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.LЕАХ.ХУZ said
May 18, 2018 at 2:58 PM
What ?
WWW.ХХХ.VIDIОХХХ.ХУZ said
May 18, 2018 at 2:58 PM
What ?

sealfin said

July 2, 2018 at 8:34 AM

May 15th, 2018.c:

#include "seal_bool.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_bool.h> */
#include <string.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

int main( const int argc, const char * const argv[] )
{
  #ifdef LEONARDO
  const size_t length = 1;
  #else
  const size_t length = 2;
  #endif

  if( argc == length )
  {
    size_t i = 0;
    #ifdef LEONARDO
    const size_t index = 0;
    #else
    const size_t index = 1;
    #endif
    bool any_digits_encountered = false, number_begun = false;
    unsigned long
    #ifndef LEONARDO
    long
    #endif
    number = 0;
    size_t number_of_numbers_encountered = 0;
    unsigned long
    #ifndef LEONARDO
    long
    #endif
    sum = 0;

    for( ; i < strlen( argv[ index ] ); i ++ )
    {
      const char c = argv[ index ][ i ];

      if(( c >= '0' ) && ( c <= '9' ))
      {
        any_digits_encountered = true;
        number_begun = true;
        number *= 10;
        number += ( c - '0' );
        if( number > UINT_MAX )
          goto l_Error;
      }
      else
        if( number_begun )
        {
          number_begun = false;
          number_of_numbers_encountered ++;
          sum += number;
          if( sum > UINT_MAX )
            goto l_Error;
          number = 0;
        }
    }
    if( !any_digits_encountered )
      goto l_Error;
    if( number_begun )
    {
      number_of_numbers_encountered ++;
      sum += number;
      if( sum > UINT_MAX )
        goto l_Error;
    }
    printf( "\nThe %snumber%s embedded in the string \"%s\" is "
    #ifdef LEONARDO
    "%lu"
    #else
    "%llu"
    #endif
    ".\n", ( number_of_numbers_encountered == 1 )?"":"sum of the ", ( number_of_numbers_encountered == 1 )?"":"s", argv[ index ], sum );
    #ifndef LEONARDO
    printf( "\n" );
    #endif
    exit( EXIT_SUCCESS );
  }
  l_Error:;
  printf( "\nThis program must be passed, via the command line, a string containing at least one digit and – optionally – one or more letters; this program will then sum the number(s) embedded in that string.\n" );
  printf( "\n(Furthermore, the number(s) embedded in that string – and the sum of those number(s) – must be in the range [ 0, %lu ].)\n", UINT_MAX );
  #ifndef LEONARDO
  printf( "\n" );
  #endif
  exit( EXIT_FAILURE );
}

The solution is known to run on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) on both Mac OS 9.2.2 (International English) (the solution interpreted using Leonardo IDE 3.4.1) and Mac OS X 10.4.11 (the solution compiled using Xcode 2.2.1).

(I’m just trying to solve the problems posed by this ‘site whilst I try to get a job; I’m well-aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

Programming Praxis