Długa liczba całkowita na ciąg i na odwrót, operacja za pomocą cyfr

Rozwiązywanie problemów z projektem Eulera Dostaję, że muszę wykonywać operacje z cyframi długiej liczby zwykle w postaci ciągu. Pracuję w Linuksie, emacs, slime z sbcl.Długa liczba całkowita na ciąg i na odwrót, operacja za pomocą cyfr

Na przykład, aby uzyskać sumę cyfr tej mocy 2¹⁰⁰⁰, pracuję w ten sposób,

1) Get moc

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

Dzięki Common Lisp jest to bardzo łatwe. Teraz uważam, że dobrym sposobem powinno być zastosowanie zmniejszenia do tej sekwencji cyfr.

2) Pobiera ciąg

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

Teraz mam sekwencję, więc stosuje się zmniejszyć, ale mam złe rzeczy: jest to char więc zastosować CHAr do liczby całkowitej:

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

ale pojawia się błąd:

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

i jeśli próbuję użyć tego jako cyfr bez konwersji inteerpreter mówi, że ten nie jest liczbą całkowitą, więc ja dostaję szału, bo to jest w porządku, ale powyższy kod nie:

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

Rozwiązałem to w ten sposób:

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

Więc moje pytanie jest dlaczego otrzymasz ten błąd najpierw jako liczbę całkowitą i po znaku, i jaki jest lepszy sposób pracy z cyframi długiej liczby całkowitej. Jeśli moja aproksymacja jest dobra: long-integer -> string -> lista liczb całkowitych -> zastosuj zmniejsz.

Źródło

2015-05-19 anquegi

To nie jest typowy Lisp, ale myślę, że może to być pomoc ogólna, jeśli zaczniesz od dodania do funkcji niektórych danych debugowania. Np. W tym przypadku, jeśli wydrukujesz xiy przed dodaniem i wywołaniem cyfr-char-p, zobaczysz, że po przetworzeniu pierwszych dwóch elementów trzecia zostanie przetworzona z wynikiem z poprzedniego dodania, czyli numer, a nie znak:

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

można myśleć o tym, co instrukcja rozwijanie wyglądałby następująco:

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

W tych połączeń pośrednich, zadzwonić cyfrowy-char-p na coś, co jest liczbą , a nie postać.

Musisz dobry punkt z ostatecznego rozwiązania:

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

ale ma niestety problem, że tworzy zupełnie nową sekwencję, aby zawierał cyfry, a następnie zmniejsza się nad nimi. Innym powszechnym anty-wzorem jest (zastosuj "+ (map & hellip;)). Twój jest nieco lepszy, ponieważ używa redukcji, ale zmniejszenie rzeczywiście bierze kluczowy argument, który eliminuje potrzebę mapy.Można użyć klucza argumentu, aby ograniczyć do określenia sposobu wartości powinny być wyodrębnione z elementów sekwencji, można użyć wartości początkowej (co jest ważne, jeśli sekwencja jest pusta, albo ma tylko jeden element):

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

Źródło

2015-05-19 12:13:16

Nawet nie potrzebują dodatkowego wyjścia debugowania, można zobaczyć go w backtrace (linia 1). – Svante

@Svante Oczywiście, jest tam również, ale * praktyka * debugowania danych wyjściowych jest przydatna. (Nie dyskontuję debuggerów itp., Ale trochę logu może zdziałać cuda.) Dodatkowo, nie zawsze jest jasne, w jaki sposób debugger wydrukuje wartość. Ale masz rację, w tym przypadku wynik był już widoczny, ale tylko w tej jednej iteracji. Dodając trochę danych wyjściowych, zobaczyliśmy także pierwszy, gdzie obie były postaciami. –

obliczenia wykonywane przez (reduce f "125") jest

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

W twoim przypadku, to znaczy, że to będzie obliczyć

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

tak to się dzieje, aby ocenić

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

zrywa z błędem typu.

Najprostszym rozwiązaniem jest napisanie wariant digit-char-p który działa na całkowite:

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

Jak zauważył Joshua Taylor, czystsze rozwiązaniem jest użycie parametru do reduce:key, która jest w przybliżeniu równa stosując map ale unika się konieczności wygenerować sekwencję pośrednika:

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

Źródło

2015-05-19 12:23:11 jch

można uniknąć drukowania liczbę na łańcuch i wygenerować listę cyfr po przecinku bezpośrednio.

wybuchnąć i implozji

Zazwyczaj ta operacja jest nazywana eksplodować. Zwykle operacja ta może zajmować się symbolami, liczbami całkowitymi i podobnymi. Tworzy listę składników. Operacja odwrotna nazywa się implode.

Byłoby eksplodować dla dodatnich liczb całkowitych:

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

Przykład:

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)

Źródło

2015-05-19 14:59:42

Długa liczba całkowita na ciąg i na odwrót, operacja za pomocą cyfr

Odpowiedz

Powiązane problemy