[python] project euler problem

Začel sem z project euler ampak pri 4 problemu ne vem zakaj mi vrne preveliko stevilo. mnozim 2 3 mestni številki torej bi moral dobiti kvečjemu 6 mestno številko vrne pa veliko večjo. bi mi lahko kdo prosim našel napako v kodi? Naloga pa je Find the largest palindrome made from the product of two 3-digit numbers.

def prezrcali(s):
    niz = ""
    dolzina = len(s)
    for i in range (0, dolzina):
        niz = niz + s[dolzina -1-i]
    return niz


a = 100
b = 100
niz = []
for i in range (0,899):
    a = a + i
    for k in range (0,899):
        b = b + k
        c = a * b

        if str(c) == prezrcali(str(c)):
            niz = niz +[c]
print(niz)
print (max(niz))
input()

for (i = 0; i< 899; i++)
a++;
for (k = 0; k < 899; k ++)
b++;
c = a * b;


Uporabil sem "Javo" za primer. Mislim da bi tako moralo delovati. Če nočeš da začne a z 101, ampak s 100 in enako za b..potem nastavi a in b pred loopom na 99. Ali pa čekiraj znotraj for-a, če je i=0, če je, potem ne incrementaj vrednosti.

Napako imaš v vrstici 13 in 15.

import time;

def prezrcali(s):
    niz = ""
    dolzina = len(s);
    for i in range(0, dolzina):
        niz = niz + s[dolzina - 1 - i];
    return niz;

a = 100;
b = 100;
niz = [];
for i in range(0, 899):
    _a = a + i;
    for k in range(0, 899):
        _b = b + k;
        c = _a * _b;
        if str(c) == prezrcali(str(c)):
            niz.extend([c]);
        print ("a=" + str(_a) + " | b=" + str(_b) + " | c=" + str(c) + " | nc=" + str(len(niz)));

print("Sleeping 5 seconds...");
time.sleep(5);

niz.sort();

count = 1;

for n in niz:
    print(str(count) + "/" + str(len(niz)) + " | " + str(n));
    count = int(count) + 1;
    time.sleep(0.1);

Še rezultat na koncu (998*998):

2466/2470 | 886688
2467/2470 | 888888
2468/2470 | 888888
2469/2470 | 906609
2470/2470 | 906609

to da preveč povečujem sem će popravil da povečujem samo za 1 zdaj imam:

def prezrcali(s):
    niz = ""
    dolzina = len(s)
    for i in range (0, dolzina):
        niz = niz + s[dolzina -1-i]
    return niz


a = 100
b = 100
niz = []
for i in range (0,900):
    a = a + 1
    for k in range (0,900):
        b = b + 1
        c = a * b

        if str(c) == prezrcali(str(c)):
            niz = niz +[c]
print(niz)
print (max(niz))
input()

ampak se vedno vrača veliko prevelika stevila. glede duplikatov pa vem da so, ampak mislim da vseeno nebi smelo vplivati na resitev pritem primeru

Tukaj ne uporabljaš prav števcev printaj si ven B dobiš dosti več kot 1000 :) pomisli zakaj je tako


EDIT: HotBurek ti je prigranil mindstormanje

Še ena varianta, z izpisom in barvami. :)

import time;

def prezrcali(s):
    niz = ""
    dolzina = len(s)
    for i in range(0, dolzina):
        niz = niz + s[dolzina - 1 - i]
    return niz


niz = [];
max = 0;
count = 0;
countmax = 900*900;
for i in range(100, 1000):
    for k in range(100, 1000):
        c = i * k;
        count = int(count) + 1;
        percent = str(int((count/countmax)*100));
        if str(c) == prezrcali(str(c)):
            niz = niz + [c]
            if c > int(max):
                max = c;
                print(str(i) + "*" + str(i) + "= " + "\033[92m" + str(c) + " | " + str(prezrcali(str(c))) + "\033[0m" + "\033[95m" + " | " + str(max) + "\033[0m" + " | " + "\033[94m" + str(count) + "/" + str(countmax) + " " + percent + "%" + "\033[0m");
                time.sleep(0.4);
            else:
                print(str(i) + "*" + str(i) + "= " + "\033[92m" + str(c) + " | " + str(prezrcali(str(c))) + " | " + "\033[0m" + " | " + str(max) + " | " + "\033[94m" + str(count) + "/" + str(countmax) + " " + percent + "%" + "\033[0m");
        else:
            print(str(i) + "*" + str(k) + "= " + "\033[91m" + str(c) + " | " + str(prezrcali(str(c))) + "\033[0m" + " | " + str(max) + " | " + "\033[94m" + str(count) + "/" + str(countmax) + " " + percent + "%" + "\033[0m");
time.sleep(1);

Zdaj so tudi rezultati do 20:
12252240 | 1-17 | time taken= 0:00:27
12252240 | 1-18 | time taken= 0:00:28
232792560 | 1-19 | time taken= 0:08:43
232792560 | 1-20 | time taken= 0:08:43

Možno, da so pravi :) Rabi pa 8-9 minut.


htop pokaže, da vse skupaj teče samo na enem jedru:



Za pohitritev mogoče 8 skript (oz. kolikor je jeder) vzporedno, vsaka pa preveri 1/8 od vseh števil.
skripta1=[1,9,17,25,...]
skripta2=[2,10,18,26,...]
skripta3=[3,11,19,27,...]
skripta4=[4,12,20,28,...]
skripta5=[5,13,21,29,...]
skripta6=[6,14,22,30,...]
skripta7=[7,15,23,31,...]
skripta8=[8,16,24,32,...]

Zrcaljenje vzame največ časa, ker za vsako novo števko se sproži postopek iteracije posameznih števk, da se obrne vrstni red.

Možne optimizacije:
- Preden začneš algoritem zrcaljenja lahko narediš check če se prva števka ujema z zadnjo (če se ne, sploh ne rabiš nič zrcalit, samo skipp
- Algoritem zrcaljenja: Palindrom pomeni, da če obrneš vrstni red števk, je številka še vedno ista (1221).
--> 3 števke v številu: preveri samo ali je prva števka enaka zadnji števki, le takrat je palindrom (222, 121, 909 .. in NE 122, 331,..)
--> 4 števke v številu: razdeliš celotno 4-mestno števko na polovico in sešteješ dve števki (tj prvi dve števki in zadnji dve števki). Če je vsota teh dveh seštevanj enaka, je palindrom.
--> 5 števk v številu: isto kot za 4 števke v številu..saj sredinsko število ni važno da palindrom velja (12321)

Upam, da nisem preveč zasral, ker iz glave pišem in se nisem poglabljal kaj dlje v palindrome (možno da obstajajo že kakšni optimizacijski algoritmi). Zgoraj izhajam iz predpostavke, da je časovno manj zapravno, če ne preverjaš celotnega niza zmeraj, ampak to poskusiš razčlenit na čim manj operacij (pri tvoji funkciji za zrcaljenje pa npr greš skozi vsak člen array-a in ga celo vpisuješ v nov array, zelo časovno potratno).

Se opravičujem za morebitne napake oz. če sem kje kaj spregledal kakšno pravilo palindroma ali pa spregledal kak primer, ki izključuje moje zgornje predpostavke.