[vari] Contest 10: Numeri palindormi (Semplice)

[cionci]

Originariamente inviato da ^TiGeRShArK^

P.S. cionci il file da 1 milione di numeri che hai usato si può avere così lo provo anch'io?

Ho semplicemente usato un ciclo chiamando rand

[bio82]

Originariamente inviato da cionci

Questo lavora sulle stringhe e quindi può superare i limiti degli interi.
Tempo sul file con 1000 numeri: 4 ms.

dato che non riesco a interpretare proprio facilmente il tuo codice, mi illumini come ragione?

il risultato di un numero come 226611 lo risolvi a 226622? e 226622?

@ tiger shark

se metti t0 prima di quando richiami il file i tempi cambiano di molto?

bio

[gugoXX]

Originariamente inviato da bio82

dato che non riesco a interpretare proprio facilmente il tuo codice, mi illumini come ragione?

il risultato di un numero come 226611 lo risolvi a 226622? e 226622?

@ tiger shark

se metti t0 prima di quando richiami il file i tempi cambiano di molto?

bio

226622 devi trovare il palindromo successivo al numero (non importa che sia palindromo esso stesso, come da specifiche)
quindi diventa
227722

[bio82]

Originariamente inviato da gugoXX

226622 devi trovare il palindromo successivo al numero (non importa che sia palindromo esso stesso, come da specifiche)
quindi diventa
227722

dato che non riesco a seguire il codice postato da lui lo chiedevo

il mio funziona (per una volta :P )

bio

[cionci]

Originariamente inviato da bio82

il risultato di un numero come 226611 lo risolvi a 226622? e 226622?

Aspetta, mi hai fatto riflettere ed ho trovato un errore

[MasterDany]

Ora provo a ragionare ditemi se è giusto cosi proverò a stilare il mio python(Considerate che ancora non so prendere file in input ma solo numeri in stringhe):

-Prendo un numero in input

-
Per calcolare il palindromo uso questo:

78+87=etc...

L'unica insicurezza ce l'ho qui...quando si tratta di numeri ad es. 440044 per verificare se è giusto posso farte anche qui l'inverso che mi pare nel caso dei numeri sia uguali ad esempio:

Numero                Inverso
440044   -------->440044
121       --------->121

Qundi posso risolvere con un semplice == ??

Questa è solo un parte dell'esercizio dell'altra non nè ho proprio la minima idea..uffi..

[bio82]

Originariamente inviato da cionci

Aspetta, mi hai fatto riflettere ed ho trovato un errore

questo errore l'ho visto facendo il file piccolo uno dei primi numeri mi dava questo errore al controllo umano (!!!!)

per questo controllo se il centrale è maggiore o minore del centrale +1 e se sono uguali leggo tutto il numero per capire se la parte + a destra di quella pari è maggiore (quindi numero a metà +1) o minore uguale (quindi il palindromo giusto è semplicemente l'inverso della prima parte)..

bio

[^TiGeRShArK^]

Originariamente inviato da bio82

dato che non riesco a interpretare proprio facilmente il tuo codice, mi illumini come ragione?

il risultato di un numero come 226611 lo risolvi a 226622? e 226622?

@ tiger shark

se metti t0 prima di quando richiami il file i tempi cambiano di molto?

bio

non cambia praticamente niente....
ora ho sistemato un pò il codice e corretto un buggettino con dei numeri dispari:

from __future__ import with_statement
import time

numbers = []
with open('../Downloads/Contest10/File2.dat') as f:
    for number in f:
        number = number.rstrip()
        numbers.append(number)
t0 = time.time()

for number in numbers:        
    palyndrome = list(number)
    length = len(palyndrome)
    halfIndex = length / 2
    if length % 2 == 0:
        halfIndex = halfIndex - 1
    i = halfIndex
    needUpdate = False
    while i >= 0 and palyndrome[length -i -1] >= palyndrome[i]:
        if length -i -1 != i:
            needUpdate = True
        i = i -1
    if needUpdate:
        palyndrome[halfIndex] = str(int(number[halfIndex]) + 1)
    for i in range(halfIndex, -1, -1):
        palyndrome[length -i -1] = palyndrome[i]
    
print 'Elapsed time:', time.time() - t0

il risultato calcolando il tempo di caricamento è:
Elapsed time: 0.00817394256592
senza calcolarlo è:
Elapsed time: 0.00750613212585

ah.. e sono col portatile a batteria per ora, quindi non so se infuisce sulle prestazioni

[cionci]

Avevo un paio di bug, uno nel controllo se potevo o meno rendere direttamente palindroma la stringa.
E l'altro si presentava con i numeri che contengono tutti 9, come 9999. Devo allungare la stringa, aggiungere uno 0 in mezzo e un 1 in testa.

Ho messo qualche commento

void mirrorString(char *s)
{
    int i = 0;
    int j = strlen(s) - 1;

    //copio la parte sinistra in quella destra invertendo gli indici
    while(i < j)
    {
        s[j--] = s[i++];
    }
}

int canMirror(char *s)
{
    int i = strlen(s) / 2;
    int j = strlen(s) - i - 1;

   //confronto fra loro le rispettive posizioni:
   //se la parte sinistra è maggiore di quella allora posso invertire direttamente
   //se la parte sinistra è minore di quella destra allora non posso invertire
    int diff = 0;
    while(j >= 0 && diff == 0)
    {
        diff = s[i++] - s[j--];
    }

    return diff;
}

void addOneToMiddleNumber(char *s)
{
    //aggiungo 1 all'elemento centrale, 
    unsigned int i = strlen(s) / 2 + strlen(s) % 2 - 1;
    if(s[i] != '9')
    {
        s[i]++;
        return;
    }
    
    //se l'elemento ha valore '9', inserisco '0' e continuo così fino a quando trovo '9' andando a sinistra (faccio il riporto)
    while(s[i]++ == '9')
    {
        s[i] = '0';
        if(i-- == 0)
            break;
    }

    //gestisco il caso particolare con la stringa composta da tutti 9
    if(s[0] == '0')
    {
        s[0] = '1';
        s[strlen(s) / 2 + strlen(s) % 2] = '0';
        s[strlen(s) + 1] = '\0';
        s[strlen(s)] = '0';
    }
}


void findNextPalindrome(char *s)
{
    if(strlen(s) < 2)
    {
        return;
    }

    if(canMirror(s))
    {
        mirrorString(s);
        return;
    }

    addOneToMiddleNumber(s);

    mirrorString(s);
}

Ottengo 317 ms con un milione di numeri.

[^TiGeRShArK^]

con un milione di stringhe fino a 4miliardi ci impiega circa 8 secondi però..

numbers = []
for i in range(0, 1000000):
    numbers.append(str(random.randint(0,4000000000)))
t0 = time.time()umbers = []
for i in range(0, 1000000):
    numbers.append(str(random.randint(0,4000000000)))
t0 = time.time()

Elapsed time: 7.9970331192

[MasterDany]

però ora non ce la faccio nemmeno a creare un palindromo.

[MasterDany]

Chi è che mi aiuto allora procedo cosi io:

a="142"

def inverso(x):
   n = len(x)
   inv = ""
   while(n > 0):
	   inv = inv + x[n - 1]
	   n = n - 1
   return inv

chiamando inverso con a viene stampato 241!
Ora devo verificare se questo valore più l'altro dà un unmero polidromo:

def verifica():
   return inverso(a)+a==inverso(a+inverso(a))

Con quest'ultima riga vedo se la somma di a + l'inverso è uguale all'inverso della somma dell'inverso di a+a.

lo chiamo cosi:

if verifica():
        print   ...
else:

Il punto è sull'else vorrei aumentare il valore di a di 1.Devo convertirlo in int eppoi in stringa...Provo cosi:

c=int(a)+1
a=str(c)

eppoi:

inverso(c)

Il punto è che quale funzione devo chiamare per far ripartire l'applicazione?

devo gestire con un while?..

while verifica()!=True:
  ...

Sto molto lontato da tutto considerate che ho iniziato a programmare 3 settimane fa precise..

Critiche sono ben gradie

[MasterDany]

forse dico un baggianate:

while verifica() !=True:

Qui posso chiamare un metodo che calcola lo stesso di prima.Però quei velori devono essere salvati in delle variabili.

Però io non posso sapere qunte varibiali occorrono creare il palindromo..Qundi potrei salvarli in una lista o tuple..

Che confusione! aiuto!

[bio82]

Originariamente inviato da ^TiGeRShArK^

con un milione di stringhe fino a 4miliardi ci impiega circa 8 secondi però..

numbers = []
for i in range(0, 1000000):
    numbers.append(str(random.randint(0,4000000000)))
t0 = time.time()umbers = []
for i in range(0, 1000000):
    numbers.append(str(random.randint(0,4000000000)))
t0 = time.time()

Elapsed time: 7.9970331192

con un numero da 1 milione di cifre impiego 12ms...ma impiega 6/7 minuti a caricarmelo a video (pazzo io:P)

        Dim watch As New System.Diagnostics.Stopwatch()
        Dim risultato As String = ""
        Dim numero As String = ""
        Dim casuale = New Random


        Do
            numero = numero & casuale.Next(1000000)
        Loop Until numero.Length > 1000000

        watch.Start()
        risultato = palindromo(numero)
        watch.Stop()

        text_tempo.Text = watch.ElapsedMilliseconds & " ms - lunghezza stringa = " & numero.Length & " cifre"
        text_risultati.Text = risultato

con 1 milione di elementi fino a 2 miliardi impiego 1969 ms.... ovviamente numeri casuali...dopo provo con uint (4miliardi)..

edit: sono un cretino

se non salvo i palindromi nella stringa "risultati" scendo a 8 ms...

bio

[MasterDany]

edit...

[cdimauro]

Originariamente inviato da ^TiGeRShArK^

con un milione di stringhe fino a 4miliardi ci impiega circa 8 secondi però..

numbers = []
for i in range(0, 1000000):
    numbers.append(str(random.randint(0,4000000000)))
t0 = time.time()umbers = []
for i in range(0, 1000000):
    numbers.append(str(random.randint(0,4000000000)))
t0 = time.time()

Elapsed time: 7.9970331192

Prova con http://psyco.sourceforge.net/

Basta mettere questo:

import psyco
psyco.full()

all'inizio del codice.

Inoltre al posto di range prova a usare xrange.

[MasterDany]

Da solo ci sono riuscito solo a fare il poliandromo a caricare i file devo imparare ancora:

def reverse(x):
    i=-1
    lunghezza=len(x)
    rit=""
    while i>= -lunghezza:
        rit=rit+x[i]
        i=i-1
    return rit



def palindromo(x):
    return x==reverse(x)

def programma(x):
   if palindromo(x):
     print x,"e' polindromo"
     return
   else:
     programma(str(int(x)+1))

programma("119")

[Vincenzo1968]

Ho preso i tempi, su un file da un milione di numeri, della versione di Tiger(con e senza psyco) e di quella di Cionci:



Questa è la mia macchina:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3

La versione psyco di Tiger è questa:

from __future__ import with_statement
import time
import psyco
psyco.full()


numbers = []
#with open('../Downloads/Contest10/File2.dat') as f:
with open('File3.dat') as f:
    for number in f:
        number = number.rstrip()
        numbers.append(number)
t0 = time.time()

for number in numbers:        
    palyndrome = list(number)
    length = len(palyndrome)
    halfIndex = length / 2
    if length % 2 == 0:
        halfIndex = halfIndex - 1
    i = halfIndex
    needUpdate = False
    while i >= 0 and palyndrome[length -i -1] >= palyndrome[i]:
        if length -i -1 != i:
            needUpdate = True
        i = i -1
    if needUpdate:
        palyndrome[halfIndex] = str(int(number[halfIndex]) + 1)
    for i in range(halfIndex, -1, -1):
        palyndrome[length -i -1] = palyndrome[i]
    
print 'Elapsed time:', time.time() - t0

e impiega più tempo rispetto alla versione normale

Per creare il file da un milione di punti ho utilizzato la seguente funzione C:

void CreaFile()
{
	FILE *fp;
	int i;
	int n1, n2, n3, n4, n5;
	char szNum1[256];
	char szNum2[256];
	char szNum3[256];
	char szNum4[256];
	char szNum5[256];

	int range_min = 1;
	int range_max = 32767;

	fp = fopen("Dati3.dat", "w+");

	srand((unsigned)time(NULL));

	for ( i = 0; i < 1000000; i++ )
	{
		//n1 = rand();
		//n2 = rand();

		n1 = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min;
		n2 = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min;
		n3 = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min;
		n4 = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min;
		n5 = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min;

		itoa(n1, szNum1, 10);
		itoa(n2, szNum2, 10);
		itoa(n3, szNum3, 10);
		itoa(n4, szNum4, 10);
		itoa(n5, szNum5, 10);

		fwrite(szNum1, strlen(szNum1), 1, fp);
		fwrite(szNum2, strlen(szNum2), 1, fp);	
		fwrite(szNum3, strlen(szNum3), 1, fp);	
		fwrite(szNum4, strlen(szNum4), 1, fp);	
		fwrite(szNum5, strlen(szNum5), 1, fp);	

		fwrite("\n", 1, 1, fp);
		//printf("record n. %d\n", i);
	}

	fclose(fp);
}

[Vincenzo1968]

La versione di Daniele sembra, invece, beneficiare dell'uso di psyco:



Questo è il codice di Daniele con psyco:

import psyco
psyco.full()

def numLength(n):
	length = 0
	while (n != 0):
		n /= 10
		length += 1
	return length

def odd(n):
	return (n & 1) != 0

def palindromize(n):
	l = numLength(n)
	n /= 10**(l/2)

	tmp = n
	if odd(l):
		tmp /= 10

	while (tmp != 0):
		c = tmp % 10
		tmp /= 10

		n *= 10
		n += c
	return n

def nextPalindrome(n):
	p = palindromize(n)
	if (p >= n):
		return p

	l = numLength(n)

	distance = 0
	if (l != 1): distance += 10
	if (l != 3): distance += 10**(l-2)

	return (p + distance)

def main():
	#name = raw_input("Inserisci il nome del file: ")

	f = open('File3.dat')
	for line in f:
		n = int(line)
		print n, "->", nextPalindrome(n)

if __name__ == "__main__":
	main()

P.S. Ohé Tiger, la tua applicazione non produce output(a parte la stampa dei tempi).

[^TiGeRShArK^]

Originariamente inviato da Vincenzo1968

La versione di Daniele sembra, invece, beneficiare dell'uso di psyco:



Questo è il codice di Daniele con psyco:

import psyco
psyco.full()

def numLength(n):
	length = 0
	while (n != 0):
		n /= 10
		length += 1
	return length

def odd(n):
	return (n & 1) != 0

def palindromize(n):
	l = numLength(n)
	n /= 10**(l/2)

	tmp = n
	if odd(l):
		tmp /= 10

	while (tmp != 0):
		c = tmp % 10
		tmp /= 10

		n *= 10
		n += c
	return n

def nextPalindrome(n):
	p = palindromize(n)
	if (p >= n):
		return p

	l = numLength(n)

	distance = 0
	if (l != 1): distance += 10
	if (l != 3): distance += 10**(l-2)

	return (p + distance)

def main():
	#name = raw_input("Inserisci il nome del file: ")

	f = open('File3.dat')
	for line in f:
		n = int(line)
		print n, "->", nextPalindrome(n)

if __name__ == "__main__":
	main()

P.S. Ohé Tiger, la tua applicazione non produce output(a parte la stampa dei tempi).

no, l'avevo tolto perchè la console su MAC rallentava i tempi di un fattore 10000 circa e mi rompevo le balle farlo partire da riga di comando per redirezionare l'output su file
aggiungi una print e redireziona su file e vedi se cambia qualcosa