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.
Programming Praxis 
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)
(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) ;; --> :successTested 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
Here’s a one-line Erlang solution
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).
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)) Qf 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”
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 OKClojureScript.
(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 nilRe-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; } }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) strsHere’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:
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
Here’s a solution in Python.
Output:
Here’s the same solution using double quotes, to attempt to improve the formatting.
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:
@sbocq: It’s not hard to adapt Globules’ Haskell solution to Scheme. Start with a variant of the Standard Prelude’s
string-splitfunction 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:
Be sure you understand the output of
string-split-by, which is slightly different than the HaskellwordsByfunction.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.
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"), 110Output:
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:
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!
What ?
What ?
What ?
What ?
What ?
What ?
What ?
What ?
What ?
What ?
What ?
What ?
What ?
What ?
What ?
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 :/ )