The 17th offline real-time how to write reference problem implemented in Python

Click here for details of the problem. http://nabetani.sakura.ne.jp/hena/ord17scheherazade/ http://qiita.com/Nabetani/items/dabe8ec57e0313229552

#!/usr/bin/env python
# -*- coding:utf8 -*-

def is_palindrome(data, base):
    digits = []
    while data > 0:
        digits.append(data % base)
        data /= base
    return digits == digits[::-1]

def solve(data):
    bases = [base for base in xrange(2, data) if is_palindrome(data, base)]
    return ','.join(map(str, bases)) if bases else '-'

def test(data, correct):
    answer = solve(int(data))
    print 'xo'[answer == correct], data, correct, answer

0, test( "17301", "5,38,100,218,236,5766,17300" );
1, test( "2", "-" );
2, test( "1", "-" );
3, test( "3", "2" );
4, test( "4", "3" );
5, test( "5", "2,4" );
6, test( "6", "5" );
7, test( "10", "3,4,9" );
8, test( "101", "10,100" );
9, test( "1001", "10,25,76,90,142,1000" );
10, test( "10001", "10,24,30,42,80,100,136,10000" );
11, test( "1212", "22,100,201,302,403,605,1211" );
12, test( "123412", "62,100,205,215,30852,61705,123411" );
13, test( "5179", "5178" );
14, test( "4919", "4918" );
15, test( "5791", "5790" );
16, test( "5498", "2748,5497" );
17, test( "453", "150,452" );
18, test( "134", "66,133" );
19, test( "8489", "27,652,8488" );
20, test( "1234", "22,616,1233" );
21, test( "5497", "41,238,5496" );
22, test( "4763", "19,35,432,4762" );
23, test( "3974", "17,27,1986,3973" );
24, test( "3521", "44,55,502,3520" );
25, test( "5513", "20,38,53,148,5512" );
26, test( "8042", "23,29,60,4020,8041" );
27, test( "7442", "37,60,121,3720,7441" );
28, test( "4857", "25,1618,4856" );
29, test( "22843", "49,69,91,141,430,22842" );
30, test( "194823", "84,121,21646,64940,194822" );
31, test( "435697", "160,169,235,626,1822,435696" );
32, test( "142", "3,7,70,141" );
33, test( "886", "5,14,442,885" );
34, test( "3102", "7,65,93,140,281,516,1033,1550,3101" );
35, test( "17326", "11,28,99,105,8662,17325" );
36, test( "32982", "13,72,238,477,716,1433,5496,10993,16490,32981" );
37, test( "36", "5,8,11,17,35" );
38, test( "37", "6,36" );
39, test( "251", "8,250" );
40, test( "252", "5,10,17,20,27,35,41,62,83,125,251" );
41, test( "253", "12,14,22,252" );
42, test( "6643", "2,3,9,81,90,510,948,6642" );
43, test( "5040", "71,79,83,89,104,111,119,125,139,143,167,179,209,239,251,279,314,335,359,419,503,559,629,719,839,1007,1259,1679,2519,5039" );

I somehow found a rule from the output result and tried to speed up the processing.

def reverse(number, base):
    r = 0
    while number > 0:
        r = r * base + (number % base)
        number /= base
    return r

def solve(number):
    if number < 3: return '-'
    bases = []
    prev = 0
    for div in xrange(1, number):
        base = (number - 1) / div
        if base == 1 or base == prev: break
        if number == reverse(number, base): bases.append(base)
        prev = base
    for base in xrange(base - 1, 1, -1):
        if number == reverse(number, base): bases.append(base)
    return ','.join(map(str, bases[::-1]))
Execution time
Before speeding up 2.122s
After speeding up 0.255s

Thanks to cielavenir, the boundary was found to be √ (number -1), so I tried to organize the speed-up process. http://qiita.com/cielavenir/items/3d2bea62d301a2309884

def palindrome(number, base):
    forward, reverse = number, 0
    while number > 0:
        reverse = (reverse * base) + (number % base)
        number /= base
    return forward == reverse

def solve(number):
    if number < 3: return '-'
    pre = number - 1
    root = int(pre ** 0.5)
    bases = [base for base in xrange(2, pre / root) if palindrome(number, base)]
    bases += [pre / div for div in xrange(root, 0, -1) if palindrome(number, pre / div)]
    return ','.join(map(str, bases))

Recommended Posts

The 17th offline real-time how to write reference problem implemented in Python
The 15th offline real-time how to write reference problem in Python
The 14th offline real-time how to write reference problem in python
The 18th offline real-time how to write reference problem in Python
The 16th offline real-time how to write reference problem to solve with Python
The 19th offline real-time how to write reference problem to solve with Python
20th Offline Real-time How to Write Problems in Python
The 16th offline real-time how to write problem was solved with Python
The 15th offline real-time how to write problem was solved with python
The 18th offline real-time writing problem in Python
The 19th offline real-time writing problem in Python
The 17th Offline Real-time How to Solve Writing Problems in Python
The 15th offline real-time I tried to solve the problem of how to write with python
The 14th offline real-time writing reference problem with Python
Part 1 I wrote the answer to the reference problem of how to write offline in real time in Python
13th Offline Real-time How to Solve Writing Problems in Python
The 10th offline real-time writing reference problem. Implementation example by Python.
Offline real-time how to write Python implementation example of E15 problem
The 11th offline real-time writing reference problem. Implementation example by python.
Answer to "Offline real-time how to write F02 problem"
Part 1 I wrote an example of the answer to the reference problem of how to write offline in real time in Python
Answer to "Offline Real-time How to Write F01 Problem"
Answer to "Offline Real-time How to Write E13 Problem"
Offline real-time how to write Python implementation example of E14
How to write offline real-time Solving E05 problems with Python
The twelfth offline real-time writing reference problem. Implementation by python
How to write Ruby to_s in Python
Offline real-time how to write E11 ruby and python implementation example
How to write offline real time Solve E04 problems in Python
How to write offline real time I tried to solve the problem of F02 with Python
How to use the C library in Python
How to write the correct shebang in Perl, Python and Ruby scripts
The trick to write flatten concisely in python
How to get the files in the [Python] folder
How to retrieve the nth largest value in Python
How to get the variable name itself in python
Basic information Write the 2018 fall algorithm problem in Python
How to get the number of digits in Python
How to write string concatenation in multiple lines in Python
How to know the current directory in Python in Blender
I want to write in Python! (3) Utilize the mock
How to use the model learned in Lobe in Python
[Python] How to output the list values in order
How to develop in Python
[Note] How to write QR code and description in the same image with python
How to write custom validations in the Django REST Framework
[python] How to check if the Key exists in the dictionary
How to debug the Python standard library in Visual Studio
How to use the __call__ method in a Python class
[Python] How to write an if statement in one sentence.
How to get the last (last) value in a list in Python
How to write a Python class
[Python] How to do PCA in Python
How to write soberly in pandas
How to collect images in Python
How to use SQLite in Python
In the python command python points to python3.8
How to get the Python version
[Python] How to import the library
How to use Mysql in python
How to wrap C in Python