Proyecto Euler 17

He estado tratando de resolver Euler 17 y me he encontrado con algunos problemas. La definición de ese problema es:

Si los números del 1 al 5 están escritos en palabras: uno, dos, tres, cuatro, cinco, entonces hay 3 + 3 + 5 + 4 + 4 = 19 letras usadas en total.

Si todos los números del 1 al 1000 (mil) inclusive se escribieran en palabras, ¿cuántas letras se usarían?

NOTA: No cuente espacios o guiones. Por ejemplo, 342 (trescientos cuarenta y dos) contiene 23 letras y 115 (ciento quince) contiene 20 letras. El uso de “y” al escribir números cumple con el uso británico.

Lo escribí en Python, e incluso después de leer el código tres o cuatro veces, todavía no puedo ver cuál es el problema. Es largo (acabo de comenzar a aprender python, y nunca he codificado antes), pero básicamente definí diferentes funciones que toman diferentes números de dígitos y cuentan el número de letras en cada uno. Terminé con 21254 y parece que la respuesta real es 21124, así que me voy exactamente por 130. Cualquier ayuda sería apreciada.

# create dict mapping numbers to their # lengths in English maps = {} maps[0] = 0 maps[1] = 3 maps[2] = 3 maps[3] = 5 maps[4] = 4 maps[5] = 4 maps[6] = 3 maps[7] = 5 maps[8] = 5 maps[9] = 4 maps[10] = 3 maps[11] = 6 maps['and'] = 3 maps['teen'] = 4 maps[20] = 6 maps[30] = 6 maps[40] = 5 maps[50] = 5 maps[60] = 6 maps[70] = 7 maps[80] = 6 maps[90] = 6 maps[100] = 7 maps[1000] = 8 # create a list of numbers 1-1000 def int_to_list(number): s = str(number) c = [] for digit in s: a = int(digit) c.append(a) return c # turn a number into a list of its digits def list_to_int(numList): s = map(str, numList) s = ''.join(s) s = int(s) return s L = [] for i in range(1,1001,1): L.append(i) def one_digit(n): q = maps[n] return q def eleven(n): q = maps[11] return q def teen(n): digits = int_to_list(n) q = maps[digits[1]] + maps['teen'] return q def two_digit(n): digits = int_to_list(n) first = digits[0] first = first*10 second = digits[1] q = maps[first] + one_digit(second) return q def three_digit(n): digits = int_to_list(n) first = digits[0] second = digits[1] third = digits[2] # first digit length f = maps[first]+maps[100] if second == 1 and third == 1: s = maps['and'] + maps[11] elif second == 1 and third != 1: s = digits[1:] s = list_to_int(s) s = maps['and'] + teen(s) elif second == 0 and third == 0: s = maps[0] elif second == 0 and third != 0: s = maps['and'] + maps[third] else: s = digits[1:] s = list_to_int(s) s = maps['and'] + two_digit(s) q = f + s return q def thousand(n): q = maps[1000] return q # generate a list of all the lengths of numbers lengths = [] for i in L: if i  11 and i  20 and i = 100 and i < 1000: n = three_digit(i) lengths.append(n) elif i == 1000: n = thousand(i) lengths.append(n) else: pass # since "eighteen" has eight letters (not 9), subtract 10 sum = sum(lengths) - 10 print "Your number is: ", sum 

Explicando la discrepancia.

Su código está plagado de errores:

  1. Esto está mal:

     maps[60] = 6 

    Contribución al error: +100 (porque afecta de 60 a 69, 160 a 169, …, 960 a 969).

  2. Varios adolescentes se equivocan:

     >>> teen(12) 7 >>> teen(13) 9 >>> teen(15) 8 >>> teen(18) 9 

    Contribución al error: +40 (porque afecta a 12, 13, …, 112, 113, …, 918)

  3. Y cualquier número de la forma x10:

     >>> three_digit(110) 17 

    Contribución al error: 9 (porque 110, 210, … 910)

  4. El número 20 no se cuenta (considera i < 20 y i > 20 pero no i == 20 ).

    Contribución al error: −6

  5. El número 1000 está escrito "mil" en inglés pero:

     >>> thousand(1000) 8 

    Contribución al error: −3

  6. Resta 10 al final en un bash de compensar uno de estos errores.

    Contribución al error: −10

Error total: 100 + 40 + 9 - 6 - 3 - 10 = 130.

Cómo pudiste haber evitado estos errores.

Al tratar de trabajar directamente con los recuentos de letras, le resultó muy difícil verificar su propio trabajo. ¿Cuántas letras hay en "ciento diez" otra vez? ¿Es 17, o es 16? Habría sido mucho más fácil para usted probar su trabajo si hubiera adoptado una estrategia como esta:

 unit_names = """zero one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen""".split() tens_names = """zero ten twenty thirty forty fifty sixty seventy eighty ninety""".split() def english(n): "Return the English name for n, from 0 to 999999." if n >= 1000: thous = english(n // 1000) + " thousand" n = n % 1000 if n == 0: return thous elif n < 100: return thous + " and " + english(n) else: return thous + ", " + english(n) elif n >= 100: huns = unit_names[n // 100] + " hundred" n = n % 100 if n == 0: return huns else: return huns + " and " + english(n) elif n >= 20: tens = tens_names[n // 10] n = n % 10 if n == 0: return tens else: return tens + "-" + english(n) else: return unit_names[n] def letter_count(s): "Return the number of letters in the string s." import re return len(re.findall(r'[a-zA-Z]', s)) def euler17(): return sum(letter_count(english(i)) for i in range(1, 1001)) 

Con este enfoque es más fácil verificar su resultado:

 >>> english(967) 'nine hundred and sixty-seven'