Sum Embedded Numbers

May 15, 2018

It’s mid-May, so at most universities the semester has ended and it is safe for me to solve some of the exercises that students sent to me over the last few months. Here’s a fun little one:

Given a string containing embedded numbers, find the sum of the embedded numbers. For instance, given the string “11aa22bb33cc44”, the desired sum is 11 + 22 + 33 + 44 = 110. You may not use regular expressions.

Although the problem statement doesn’t say so, you may assume that the numbers of interest are non-negative integers. Thus, the purpose of the exercise is for students to iterate through a string, identify the digits in the string, and manipulate them numerically.

Your task is to write a program that sums the numbers embedded in a string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

35 Responses to “Sum Embedded Numbers”

  1. Milbrae said

    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)

  2. (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
    
  3. Milbrae said

    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

  4. Phil Runninger said

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

  5. Steve said

    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”

  6. sbocq said

    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
    
  7. sbocq said

    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
    
  8. Milbrae said

    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;
        }
    }
    
  9. Globules said
    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
    
  10. Daniel said

    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
    
  11. sbocq said

    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

  12. Daniel said

    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:

    110
    
  13. Daniel said

    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()))
    
  14. Daniel said

    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
    
  15. programmingpraxis said

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

  16. sbocq said

    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.

  17. V said

    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
    
  18. sbocq said

    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
    
  19. Mike said

    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!

  20. WWW.ХХХ.ХQТSРN.ХУZ said

    What ?

  21. WWW.ХХХ.SРNСР.ХУZ said

    What ?

  22. WWW.ХХХ.GЕРBJZ.ХУZ said

    What ?

  23. WWW.ХХХ.SРNСР.ХУZ said

    What ?

  24. WWW.ХХХ.ТАJКХР.ХУZ said

    What ?

  25. WWW.ХХХ.UЕLЕЕS.ХУZ said

    What ?

  26. WWW.ХХХ.ЕWZJJ.ХУZ said

    What ?

  27. WWW.ХХХ.LЕАХ.ХУZ said

    What ?

  28. WWW.ХХХ.VIDIОХХХ.ХУZ said

    What ?

  29. sealfin said

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

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: