Reverse and Add: găsește un palindrom (Revizuirea codului, Python, Provocare De Programare, Palindrom)

Nikolay Derkach a intrebat.

Aceasta este una dintre provocările codeeval

Descrierea provocării:

Credite: Provocări de programare de Steven S. Skiena și Miguel A. Revilla

Problema este următoarea: alegeți un număr, inversați-i cifrele și adăugați-l la cel original. Dacă suma nu este un palindrom (ceea ce înseamnă că nu este același număr de la stânga la dreapta și de la dreapta la stânga), repetați această procedură. De ex.

195 (numărul inițial) + 591 (inversarea numărului inițial) = 786

786 + 687 = 1473

1473 + 3741 = 5214

5214 + 4125 = 9339 (palindrom) În acest caz particular, palindromul 9339 a apărut după a patra adunare. Această metodă conduce la palindromuri în câțiva pași pentru aproape toate numerele întregi. Există însă și excepții interesante. 196 este primul număr pentru care nu a fost găsit niciun palindrom. Totuși, nu este dovedit că nu există un astfel de palindrom.

Iată soluția mea pentru el:

#!/usr/bin/env python
import sys

"""
I've done some tests with timeit and it seems that both numeric and string version
have the same performance (at least for numbers < 10000)

# def reverse_num(num):
#   rev = 0
#   while(num > 0):
#     rev = (10*rev)+num%10
#     num //= 10
#   return rev
"""

def reverse(num):
    """Reverses the number

       >>> reverse(1456)
       6541
       >>> reverse(111)
       111
    """
    return int(str(num)[::-1])

def palindrome(num):
    """Return the number of iterations required to compute a palindrome

       >>> palindrome(195)
       (4, 9339)
    """
    # compute in 100 iterations or less
    for i in range(100):
        rnum = reverse(num)
        if rnum == num:
            break
        num = num + rnum
    return (i, num)

if __name__ == "__main__":
    with open(sys.argv[1]) as f:
        for line in f:
            print "%s %s" % palindrome(int(line))

Aveți vreo observație asupra stilului de cod, asupra algoritmului în sine?

Comentarii

  • Două comentarii: Probabil că ar fi bine să se gestioneze erorile în cazurile în care a trecut de 100 de iterații (față de a termina exact la iterația 100! :)) De asemenea, de dragul curiozității, ați rescris palindromul(num) folosind recursivitatea pentru a vedea dacă ar exista o scădere de performanță și cu cât de mult?  > Por shivsky.
2 răspunsuri
fscore

Doar 2 lucruri:

  1. De ce aveți acest lucru? Acest lucru face ca codul dvs. să fie puțin neclar și confuz. Îndepărtați acest lucru dacă nu doriți să îl utilizați, deoarece ar putea face codul dvs. real să arate dezordonat.

    # def reverse_num(num):
    #   rev = 0
    #   while(num > 0):
    #     rev = (10*rev)+num%10
    #     num //= 10
    #   return rev
    
  2. Este descurajată utilizarea for i in range(100): în Python.

Comentarii

  • Presupun că comentariul dvs. de la punctul 2 indică faptul că utilizarea enumerării era mai idiomatic?-  > Por shivsky.
  • for i in range(100) este folosit în mod corespunzător aici. Ar putea fi xrange în schimb în Python 2, totuși.-  > Por Janne Karila.
SylvainD

Comentariile de la un răspuns la o altă întrebare se aplică aici la funcția comentată reverse_num:

divmod

În Python, atunci când efectuați aritmetică și vă interesează atât cutientul, cât și restul unei împărțiri, puteți folosi divmod.

Numerele magice

Aveți 10 codificate în mai multe locuri. Preferința mea este să folosesc un argument implicit care să dea baza de utilizat.

def reverse(integer, base=10):
    result = 0
    while integer:
        integer, r = divmod(integer, base)
        result = base * result + r
    return result

Comentarii mai specifice

  • Documentația pentru palindrome este oarecum imprecisă. Aceasta implică faptul că returnează un număr, dar de fapt returnează un tupluplu.

  • num = num + rnum poate fi rescrisă num += rnum

  • ar putea fi interesant să memorați orice rezultat pe care îl calculați, astfel încât să nu mai fie nevoie să pierdeți timp pentru a-l calcula ulterior. Acest lucru necesită o analiză comparativă pentru a fi siguri că este relevant.