长整数到字符串,反之亦然,用数字操作

Question

解决Euler项目问题​​我得到的是我需要使用长数字的数字作为字符串进行操作.我使用sbcl在linux,emacs,slime中工作.

例如,为了得到这个数字2的数字之和,我这样工作,

1)获得力量

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

感谢Common Lisp,这非常简单.现在我相信一个好方法应该是将reduce应用于这个数字序列.

2)获取字符串

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

现在我有了序列,所以应用reduce,但是我得到错误的东西:这是一个char所以我将转换字符应用于整数:

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

但是我收到一个错误:

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

如果我尝试将其用作没有转换的数字,则inteerpreter会说这不是整数,所以我变得疯狂,因为这是正确的,但上面的代码不是:

(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")

我通过这样做解决了这个问题:

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

所以我的问题是为什么我首先得到一个整数和一个字符后的错误,以及使用长整数的数字的更好的方法是什么.如果我的aproximation是好的:long-integer - > string - >整数列表 - > apply reduce.

Answer 1

这不是Common Lisp特有的,但我认为如果你开始为你的函数添加一些调试输出,它可能是一般帮助.例如,在这种情况下,如果在添加并使用它们调用digit-char-p之前打印x和y,则可以看到在处理前两个元素之后,第三个元素将使用前一个添加的结果进行处理,即一个数字,而不是一个字符:

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

您可以考虑手动展开的外观:

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

在那些中间调用中,你在数字上调用digit-char-p,而不是字符.

你最终的解决方案得到了一个好处:

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

但这有一个不幸的问题,它创建了一个全新的序列来包含数字,然后减少它们.另一种常见的反模式是(应用'+(map ...)).你的更好一点,因为它使用reduce,但reduce实际上采用了一个关键参数,消除了对map的需求.您可以使用reduce参数reduce来指定如何从序列元素中提取值,并且您可以使用初始值(如果序列为空,或者只有一个元素,这很重要):

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

Answer 2

可以避免将数字打印到字符串并直接生成小数位数列表.

爆炸与实现

通常这个操作称为爆炸.通常,爆炸操作可以处理符号,整数和类似操作.它创建了一个组件列表.反向操作称为内爆.

这将对正整数爆炸:

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

例:

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)