Long integer to string and vice versa, operation with digits

Question

Solving the Euler project problems I get that I need to make operations with the digits of a long number normally as a string. I work in linux, emacs, slime with sbcl.

For example, to get the sum of the digits of this power 2¹⁰⁰⁰, I work this way,

1) Get the power

CL-USER> (defparameter *answer-as-integer* (expt 2 1000))
*ANSWER-AS-INTEGER*
CL-USER> *ANSWER-AS-INTEGER*
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Thanks to Common Lisp this is very easy. Now I believe that a good way should be to apply reduce to this sequence of digits.

2) Get the string

CL-USER> (defparameter *answer-as-string* (write-to-string *ANSWER-AS-INTEGER*))
*ANSWER-AS-STRING*
CL-USER> *ANSWER-AS-STRING*
"10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376" 

Now I have the sequence, so apply reduce, but I get wrong things: This is a char so I apply a conversion char to integer:

CL-USER> (reduce #'(lambda (x y) (+  (digit-char-p x)  (digit-char-p y))) *ANSWER-AS-string*)

but I get an error:

The value 1 is not of type CHARACTER.
   [Condition of type TYPE-ERROR]

Restarts:
 0: [RETRY] Retry SLIME REPL evaluation request.
 1: [*ABORT] Return to SLIME's top level.
 2: [ABORT] Abort thread (#<THREAD "repl-thread" RUNNING {1005DE80B3}>)

Backtrace:
  0: (DIGIT-CHAR-P 1) [optional]
  1: ((LAMBDA (X Y)) 1 #\7)
  2: (REDUCE #<FUNCTION (LAMBDA (X Y)) {100523C79B}> "1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858127594672917553146825187145285692314043598457757469..
  3: (SB-INT:SIMPLE-EVAL-IN-LEXENV (REDUCE (FUNCTION (LAMBDA # #)) *ANSWER-AS-STRING*) #<NULL-LEXENV>)
  4: (EVAL (REDUCE (FUNCTION (LAMBDA # #)) *ANSWER-AS-STRING*))
  5: (SWANK::EVAL-REGION "(reduce #'(lambda (x y) (+  (digit-char-p x)  (digit-char-p y))) *ANSWER-AS-string*) ..)
      Locals:
        SB-DEBUG::ARG-0 = "(reduce #'(lambda (x y) (+  (digit-char-p x)  (digit-char-p y))) *ANSWER-AS-string*)\n"
  6: ((LAMBDA NIL :IN SWANK-REPL::REPL-EVAL))
  7: (SWANK-REPL::TRACK-PACKAGE #<CLOSURE (LAMBDA NIL :IN SWANK-REPL::REPL-EVAL) {10051F065B}>)
  8: (SWANK::CALL-WITH-RETRY-RESTART "Retry SLIME REPL evaluation request." #<CLOSURE (LAMBDA NIL :IN SWANK-REPL::REPL-EVAL) {10051F059B}>)
  9: (SWANK::CALL-WITH-BUFFER-SYNTAX NIL #<CLOSURE (LAMBDA NIL :IN SWANK-REPL::REPL-EVAL) {10051F057B}>)
 10: (SWANK-REPL::REPL-EVAL "(reduce #'(lambda (x y) (+  (digit-char-p x)  (digit-char-p y))) *ANSWER-AS-string*) ..)
 11: (SB-INT:SIMPLE-EVAL-IN-LEXENV (SWANK-REPL:LISTENER-EVAL "(reduce #'(lambda (x y) (+  (digit-char-p x)  (digit-char-p y))) *ANSWER-AS-string*) ..)
 12: (EVAL (SWANK-REPL:LISTENER-EVAL "(reduce #'(lambda (x y) (+  (digit-char-p x)  (digit-char-p y))) *ANSWER-AS-string*) ..)
 13: (SWANK:EVAL-FOR-EMACS (SWANK-REPL:LISTENER-EVAL "(reduce #'(lambda (x y) (+  (digit-char-p x)  (digit-char-p y))) *ANSWER-AS-string*) ..)
 14: (SWANK::PROCESS-REQUESTS NIL)
 15: ((LAMBDA NIL :IN SWANK::HANDLE-REQUESTS))
 16: ((LAMBDA NIL :IN SWANK::HANDLE-REQUESTS))
 17: (SWANK/SBCL::CALL-WITH-BREAK-HOOK #<FUNCTION SWANK:SWANK-DEBUGGER-HOOK> #<CLOSURE (LAMBDA NIL :IN SWANK::HANDLE-REQUESTS) {1005DF00DB}>)
 18: ((FLET SWANK/BACKEND:CALL-WITH-DEBUGGER-HOOK :IN "/home/anquegi/quicklisp/dists/quicklisp/software/slime-2.13/swank/sbcl.lisp") #<FUNCTION SWANK:SWANK-DEBUGGER-HOOK> #<CLOSURE (LAMBDA NIL :IN SWANK::H..
 19: (SWANK::CALL-WITH-BINDINGS ((*STANDARD-OUTPUT* . #1=#<SWANK/GRAY::SLIME-OUTPUT-STREAM {1005DCF343}>) (*STANDARD-INPUT* . #2=#<SWANK/GRAY::SLIME-INPUT-STREAM {1006160003}>) (*TRACE-OUTPUT* . #1#) (*ERR..
 20: (SWANK::HANDLE-REQUESTS #<SWANK::MULTITHREADED-CONNECTION {1005078BE3}> NIL)
 21: ((FLET #:WITHOUT-INTERRUPTS-BODY-1226 :IN SB-THREAD::INITIAL-THREAD-FUNCTION-TRAMPOLINE))
 22: ((FLET SB-THREAD::WITH-MUTEX-THUNK :IN SB-THREAD::INITIAL-THREAD-FUNCTION-TRAMPOLINE))
 23: ((FLET #:WITHOUT-INTERRUPTS-BODY-647 :IN SB-THREAD::CALL-WITH-MUTEX))
 24: (SB-THREAD::CALL-WITH-MUTEX #<CLOSURE (FLET SB-THREAD::WITH-MUTEX-THUNK :IN SB-THREAD::INITIAL-THREAD-FUNCTION-TRAMPOLINE) {7FFFEA81ED1B}> #<SB-THREAD:MUTEX "thread result lock" owner: #<SB-THREAD:THR..
 25: (SB-THREAD::INITIAL-THREAD-FUNCTION-TRAMPOLINE #<SB-THREAD:THREAD "repl-thread" RUNNING {1005DE80B3}> #S(SB-THREAD:SEMAPHORE :NAME "Thread setup semaphore" :%COUNT 0 :WAITCOUNT 0 :MUTEX #<SB-THREAD:MU..
 26: ("foreign function: call_into_lisp")
 27: ("foreign function: new_thread_trampoline")

and if I try to use this as digits without conversion the inteerpreter says that this is not a integer, so I'm getting crazy, because this is right but the above code not:

(reduce #'+ *ANSWER-AS-string*)

The value #\1 is not of type NUMBER.
   [Condition of type TYPE-ERROR]

Restarts:
 0: [RETRY] Retry SLIME REPL evaluation request.
 1: [*ABORT] Return to SLIME's top level.
 2: [ABORT] Abort thread (#<THREAD "repl-thread" RUNNING {1005DE80B3}>)

Backtrace:
  0: (+ #\1 #\0)
  1: (REDUCE #<FUNCTION +> "107150860718626732094842504906000181056140481170553360744375038837035105112493612249319837881569585812759467291755314682518714528569231404359845775746985748039345677748242309854..
  2: (SB-INT:SIMPLE-EVAL-IN-LEXENV (REDUCE (FUNCTION +) *ANSWER-AS-STRING*) #<NULL-LEXENV>)
  3: (EVAL (REDUCE (FUNCTION +) *ANSWER-AS-STRING*))
  4: (SWANK::EVAL-REGION "(reduce #'+ *ANSWER-AS-string*) ..)
      Locals:
        SB-DEBUG::ARG-0 = "(reduce #'+ *ANSWER-AS-string*)\n"
  5: ((LAMBDA NIL :IN SWANK-REPL::REPL-EVAL))
  6: (SWANK-REPL::TRACK-PACKAGE #<CLOSURE (LAMBDA NIL :IN SWANK-REPL::REPL-EVAL) {100566384B}>)
  7: (SWANK::CALL-WITH-RETRY-RESTART "Retry SLIME REPL evaluation request." #<CLOSURE (LAMBDA NIL :IN SWANK-REPL::REPL-EVAL) {100566378B}>)
  8: (SWANK::CALL-WITH-BUFFER-SYNTAX NIL #<CLOSURE (LAMBDA NIL :IN SWANK-REPL::REPL-EVAL) {100566376B}>)
  9: (SWANK-REPL::REPL-EVAL "(reduce #'+ *ANSWER-AS-string*) ..)
 10: (SB-INT:SIMPLE-EVAL-IN-LEXENV (SWANK-REPL:LISTENER-EVAL "(reduce #'+ *ANSWER-AS-string*) ..)
 11: (EVAL (SWANK-REPL:LISTENER-EVAL "(reduce #'+ *ANSWER-AS-string*) ..)
 12: (SWANK:EVAL-FOR-EMACS (SWANK-REPL:LISTENER-EVAL "(reduce #'+ *ANSWER-AS-string*) ..)
 13: (SWANK::PROCESS-REQUESTS NIL)
 14: ((LAMBDA NIL :IN SWANK::HANDLE-REQUESTS))
 15: ((LAMBDA NIL :IN SWANK::HANDLE-REQUESTS))
 16: (SWANK/SBCL::CALL-WITH-BREAK-HOOK #<FUNCTION SWANK:SWANK-DEBUGGER-HOOK> #<CLOSURE (LAMBDA NIL :IN SWANK::HANDLE-REQUESTS) {1005DF00DB}>)
 17: ((FLET SWANK/BACKEND:CALL-WITH-DEBUGGER-HOOK :IN "/home/anquegi/quicklisp/dists/quicklisp/software/slime-2.13/swank/sbcl.lisp") #<FUNCTION SWANK:SWANK-DEBUGGER-HOOK> #<CLOSURE (LAMBDA NIL :IN SWANK::H..
 18: (SWANK::CALL-WITH-BINDINGS ((*STANDARD-OUTPUT* . #1=#<SWANK/GRAY::SLIME-OUTPUT-STREAM {1005DCF343}>) (*STANDARD-INPUT* . #2=#<SWANK/GRAY::SLIME-INPUT-STREAM {1006160003}>) (*TRACE-OUTPUT* . #1#) (*ERR..
 19: (SWANK::HANDLE-REQUESTS #<SWANK::MULTITHREADED-CONNECTION {1005078BE3}> NIL)
 20: ((FLET #:WITHOUT-INTERRUPTS-BODY-1226 :IN SB-THREAD::INITIAL-THREAD-FUNCTION-TRAMPOLINE))
 21: ((FLET SB-THREAD::WITH-MUTEX-THUNK :IN SB-THREAD::INITIAL-THREAD-FUNCTION-TRAMPOLINE))
 22: ((FLET #:WITHOUT-INTERRUPTS-BODY-647 :IN SB-THREAD::CALL-WITH-MUTEX))
 23: (SB-THREAD::CALL-WITH-MUTEX #<CLOSURE (FLET SB-THREAD::WITH-MUTEX-THUNK :IN SB-THREAD::INITIAL-THREAD-FUNCTION-TRAMPOLINE) {7FFFEA81ED1B}> #<SB-THREAD:MUTEX "thread result lock" owner: #<SB-THREAD:THR..
 24: (SB-THREAD::INITIAL-THREAD-FUNCTION-TRAMPOLINE #<SB-THREAD:THREAD "repl-thread" RUNNING {1005DE80B3}> #S(SB-THREAD:SEMAPHORE :NAME "Thread setup semaphore" :%COUNT 0 :WAITCOUNT 0 :MUTEX #<SB-THREAD:MU..
 25: ("foreign function: call_into_lisp")
 26: ("foreign function: new_thread_trampoline")

I solved this by doing this:

CL-USER> (defun sum-digits-in-a-string (str)
  (reduce #'+ (map 'list #'digit-char-p str)))
SUM-DIGITS-IN-A-STRING
CL-USER> (sum-digits-in-a-string *ANSWER-AS-STRING*)
1366

So my question is to why I get that error first an integer and after a char, and what is the better way of work with the digits of a long integer. If my aproximation is good: long-integer -> string -> list of integers -> apply reduce.

Focus

Answer 1

This isn't Common Lisp specific, but I think it may be a general help if you start by adding some debug output to your functions. E.g., in this case, if you print x and y before adding and calling digit-char-p with them, you can see that after the first two elements are processed, the third gets processed with the result from the previous addition, which is a number, not a character:

CL-USER> (reduce (lambda (x y)
                   (write (list x y))
                   (+ (digit-char-p x)
                      (digit-char-p y)))
                   "1234")
(#\1 #\2)(3 #\3)
; Evaluation aborted on #<TYPE-ERROR expected-type: CHARACTER datum: 3>.

You can think about what a manual unrolling would look like:

(+ (digit-char-p (+ (digit-char-p (+ (digit-char-p #\1) 
                                     (digit-char-p #\2)))
                    (digit-char-p #\3)))
   (digit-char-p #\4))

In those intermediate calls, you call digit-char-p on something that's a number, not a character.

You got to a good point with your final solution:

(defun sum-digits-in-a-string (str)
  (reduce #'+ (map 'list #'digit-char-p str)))

but that has the unfortunate issue that it creates a whole new sequence to contain the digits and then reduces over them. Another common anti-pattern is (apply '+ (map …)). Yours is a bit better, because it uses reduce, but reduce actually takes a key argument that eliminates the need for the map. You can use the key argument to reduce to specify how values should be extracted from the sequence elements, and you can use an initial value (which is important if your sequence is empty, or has just one element):

CL-USER> (reduce '+ "1234" :key 'digit-char-p :initial-value 0)
;=> 10

Kohn

You do not even need extra debug output, you can see it in the backtrace (line 1). – Wongawonga

@Wongawonga Sure, it's there, too, but the practice of debugging output is a useful one. (I don't discount debuggers, etc., but a little bit of log output can do wonders.) Plus, it's not always clear how a debugger will print a value. But you're right, in this case, the output was already visible, but only on that one iteration. By adding some output, we got to see the first one too, where they were both characters. – Kohn

Answer 2

One can avoid to print the number to a string and generate a list of the decimal digits directly.

EXPLODE and IMPLODE

Usually this operation is called explode. Typically the explode operation could deal with symbols, integers and similar. It creates a list of the components. The inverse operating is called implode.

This would be explode for positive integers:

(defun explode-integer (integer)
  "Explode a positve integer."
  (labels ((aux-explode-integer (integer)
             (nreverse
              (loop with i = integer and r = 0
                    while (> i 0)
                    do (multiple-value-setq (i r) (floor i 10))
                    collect r))))
    (cond ((plusp integer)
           (aux-explode-integer integer))
          ((zerop integer) (list 0)))))

Example:

CL-USER 31 > (explode-integer 572304975029345020734)
(5 7 2 3 0 4 9 7 5 0 2 9 3 4 5 0 2 0 7 3 4)

Piccolo

Answer 3

The computation performed by (reduce f "125") is

(f (f #\1 #\2) #\5)

In your case, this means that it is going to compute

(+ (digit-char-p (+ (digit-char-p #\1) (digit-char-p #\2)))
   (digit-char-p #\5))

so it's going to evaluate

(+ (digit-char-p 3) (digit-char-p #\5))

which breaks with a type error.

The simplest solution is to write a variant of digit-char-p that works on integers:

(defun digit-to-int (x)
   (etypecase x
     (integer x)
     (character (digit-char-p x))))

(reduce #'(lambda (x y) (+  (digit-to-int x)  (digit-to-int y))) *ANSWER-AS-string*)

As pointed out by Joshua Taylor, a cleaner solution is to use the :key parameter to reduce, which is roughly equivalent to using map but avoids the need to generate an intermediary sequence:

(reduce #'+ *ANSWER-AS-string* :key #'digit-char-p)

Haven