[vari] Contest 10: Numeri palindormi (Semplice)

[gugoXX]

Poiche' mi e' stato chiesto di provare a mettere in gioco anche i non esperti, propongo questo contest per i piu' JUNIOR

Sta al singolo decidere se si sente parte degli Junior oppure no (Junior in senso di skill. Potrebbe anche essere 90anni...)

Problema:
Sia dato un elenco di numeri.
Per ciascuno dei numeri letti, stampare il numero palindromo piu' piccolo che sia pero' maggiore del numero dato.
Palindromo significa che, date le cifre in base decimale, il numero si puo' leggere allo stesso modo sia leggendolo da sinistra a destra, sia leggendolo da destra a sinistra

Es:
Se si avesse come input i numeri

119
115434
576
1024


Si dovrebbe restituire come risultato

121
115511
585
1111


2 File per l'esercizio, il primo semplice, il secondo piu' difficile
http://www.usaupload.net/d/mnp0jyk2kt8

Posto qui di seguito anche il Codice C# per generare i file di prova, per eventuali futuri utilizzi

class Program
{
static void Main(string[] args)
{
Generator.Generate(@"C:\temp\File1.dat", 1000, 7);
Generator.Generate(@"C:\temp\File2.dat", 100, 30);
}
}

public static class Generator
{
static Random rnd = new Random(155452);

public static void Generate(string FileName,int nValori,int nCifre)
{
nCifre -= 3;
StreamWriter sw = new StreamWriter(FileName);
for (int t = 0; t < nValori; t++)
{
int rndcif = 3+rnd.Next(nCifre);
bool first = true;
for (int u = 0; u < rndcif; u++)
{
int cifra;
if (first) cifra = rnd.Next(9) + 1;
else cifra = rnd.Next(10);
first = false;
sw.Write(cifra);
}
sw.WriteLine();
}
sw.Close();
}
}

[^TiGeRShArK^]

palindormi? :asd:
mi sa che è ora che tu vada a letto in effetti :asd:

P.S. comunque il contest potrebbe anche essere carino per i senior, anche se mi sa che ad occhio la soluzione + efficiente non è poi così difficile da trovare :p

[fero86]

ma il palindromo immediatamente successivo a 115434 non dovrebbe essere 115511? nel primo post c'é scritto 116611

[G30]

ma il palindromo immediatamente successivo a 115434 non dovrebbe essere 115511? nel primo post c'é scritto 116611

Esatto :read:

[gugoXX]

ma il palindromo immediatamente successivo a 115434 non dovrebbe essere 115511? nel primo post c'é scritto 116611

Sisi',errore mio. Correggo.

[gugoXX]

palindormi? :asd:
mi sa che è ora che tu vada a letto in effetti :asd:


Si, meglio che vada va... :ronf:

[bio82]

Si, meglio che vada va... :ronf:

primo:D

ho trovato il metodo, ma sbaglia quando iniziano ad esserci numeri uguali fra la parte destra e sinistra del numero...

quindi mancano alcune righe che completo stasera quando torno...per ora sto a

http://bio.gbservicesnc.it/public/images/contest10ver1.JPG (http://bio.gbservicesnc.it/?filename=contest10ver1.JPG)

(millesimi) con il file + grande...

bio

[ndakota]

ma li trattereste come interi o come stringhe?? nel secondo caso sarebbe molto più semplice ma non so se più veloce..

[MasterDany]

edit

[cionci]

ma li trattereste come interi o come stringhe?? nel secondo caso sarebbe molto più semplice ma non so se più veloce..
Come stringa direi.

[MasterDany]

Qualche consiglio??

[VICIUS]

Se il numero da cercare è già palindromo come ci si deve comportare? Possiamo ritornare direttamente il numero oppure dobbiamo cercare il palindromo successivo?

Implementazione banale:
def search_nearest_palindrome(n)
n+=1 until n.to_s == n.to_s.reverse
n
end

File.open('File1.txt', 'r') do |file|
while line = file.gets
puts line.chop + " -> " + search_nearest_palindrome(line.to_i).to_s
end
end
200 millisecondi per il primo file mentre con il secondo è ovviamente impraticabile a causa di quei numeri a molte cifre.

Sempre per il primo file mi stavo chiedo se mettendo tutti i palindromi formati da 1 fino a 7 cifre e poi usando una ricerca di qualche tipo in quella lista si potrebbero velocizzare di molto le ricerche. Anche se probabilmente alla fine la generazione dell'array a runtime renderebbe lo sforzo inutile.

Peccato che il trucchetto di capovolgi e somma non funzioni in questo caso :D

[MasterDany]

edit.

[..::DAVE::..]

ho un problemuccio... ho finito... ma non riesco a calcolare il tempo... cioè con start=clock() all'inizio ed end=clock() alla fine mi da lo stesso numero... strano...
nel frattempo posto il codice?

[cionci]

Ve gusta ?

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

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

while(i < j)
{
s[j--] = s[i++];
}
return atoi(s);
}

int findNextPalindrom(int n)
{
if(n < 10)
{
return n;
}

char s[11];
sprintf(s, "%d", n);

int mirrored = mirrorInt(s);
if(mirrored > n)
{
return mirrored;
}

int length = strlen(s);
int middle = lenght / 2;
if(length % 2 == 0)
{
middle--;
}

sprintf(s, "%d", n + (int)pow(10, length - middle - 1));

return mirrorInt(s);
}

[cionci]

ho un problemuccio... ho finito... ma non riesco a calcolare il tempo... cioè con start=clock() all'inizio ed end=clock() alla fine mi da lo stesso numero... strano...
nel frattempo posto il codice?
Non è strano se ci mette meno di un secondo ;)

[..::DAVE::..]

Non è strano se ci mette meno di un secondo ;)

e come faccio a calcolarlo se ci impiega meno di un secondo :D ?

un po' lungo...


#include <time.h>
#include <fstream>
#include <iostream>
#include <string>

using namespace std;

string strOut(string stringa);

int main()
{
time_t start,end;
ifstream fin("File2.dat");
ofstream fout("Output.txt");
double tempo;
start=clock();

string numero;
char temp[100];

while(!fin.eof())
{
fin.getline(temp,99);
numero=temp;
fout<<strOut(numero)<<endl;
}

end=clock();
tempo=((double)(end-start))/CLOCKS_PER_SEC;
fin.close();
fout.close();
cout<<tempo<<" "<<start<<" "<<end<<" "<<CLOCKS_PER_SEC<<endl;
cin.get();
}

string strOut(string stringa)
{
int lung=stringa.length();
bool maggiore=false;

for(int i=0; i<=(lung/2); i++)
{
if(i==(lung-i-2))
{
if(stringa[i]>stringa[lung-1-i])
stringa[lung-1-i]=stringa[i];
else
{
if(stringa[i]<stringa[lung-1-i])
stringa[i]=stringa[lung-1-i];
else
if(maggiore)
{
int j=i;

while(stringa[j]=='9')
j++;

stringa[j]+=1;
stringa[lung-1-j]+=1;
}
}
}
else
{
if(i==(lung-i-1))
{
if(maggiore)
if(stringa[i]<'9')
stringa[i]+=1;
else
{
int j=i;
while(stringa[j]=='9')
j++;

stringa[j]+=1;
stringa[2*i-j]+=1;
}

}
else
{
if(stringa[lung-1-i]>=stringa[i])
maggiore=true;
else
maggiore=false;

stringa[lung-1-i]=stringa[i];
}
}
}

return stringa;
}

[cionci]

Aspe...usi già clock, avevo confuso con time, allora dovrebbe andare, strano. Visivamente quanto ci mette ?

[DanieleC88]

Ve gusta ?

[...]
Forte! :D

Io avevo pensato ad un calcolo puramente matematico, ma è troppo "umano" (via codice dovrei estrarre le varie cifre ogni volta).

[..::DAVE::..]

Aspe...usi già clock, avevo confuso con time, allora dovrebbe andare, strano. Visivamente quanto ci mette ?

appena si apre la console mi appare il risultato... moolto meno di un secondo
in compenso copiando 50 volte i numeri del file 2 (quello da 100) come tempo mi da 0.078 che diviso 50 da 0,00156

[MasterDany]

Allora volevo partire dalla creazione del palindromo ragiono cosi:


Prendi un numero, inverti le sue cifre e somma il numero che ottieni a quello iniziale. Se il risultato non è un numero palindromo, ripeti il procedimento.



87 + 78 = 165 165 + 561 = 726 726 + 627 = 1353 1353 + 3531 = 4884


Ora vorrei implementare.Conoscete qualche funzione che inverte i numeri?

[..::DAVE::..]

Allora volevo partire dalla creazione del palindromo ragiono cosi:




87 + 78 = 165 165 + 561 = 726 726 + 627 = 1353 1353 + 3531 = 4884


Ora vorrei implementare.Conoscete qualche funzione che inverte i numeri?

il numero che dovresti trovare da 87 è 88... non 4884

[MasterDany]

il numero che dovresti trovare da 87 è 88... non 4884

Sono un principiante quindi prima volevo provare a cercare un semplice polindromo ;)

Però devo trovare qualcosa in python che converta 87 in 78 ;)

[cionci]

Chiedi nella discussione relativa a Python ;)

[cionci]

Versione senza l'uso di stringhe:
int getLength(int n)
{
int divisor = 10;
int length = 1;
while(divisor < n)
{
length++;
divisor *= 10;
}

return length;
}

int mirrorInt(int n, int length)
{
int divisor, multiplier;
divisor = multiplier = (int)pow(10, length / 2);

n = (n / divisor) * divisor;

if(length % 2 == 0)
{
divisor /= 10;
}

do
{
divisor *= 10;
multiplier /= 10;
n += ((n / divisor) % 10) * multiplier;
}
while(multiplier > 1);

return n;
}


int findNextPalindrome2(int n)
{
if(n < 10)
{
return n;
}

int length = getLength(n);

int mirrored = mirrorInt(n, length);
if(mirrored > n)
{
return mirrored;
}

int middle = length / 2;
if(length % 2 == 0)
{
middle--;
}

n += (int)pow(10, length - middle - 1);

return mirrorInt(n, getLength(n));
}

Ora la ottimizzo ;)

[DanieleC88]

Versione senza l'uso di stringhe:

[...]
Oddio, hai fatto qualcosa di molto simile a ciò che sto facendo io! :D

L'algoritmo sembra (incredibilmente) funzionare, il tempo di implementare la lettura del file e poi posto il codice.

[DanieleC88]

Pare funzionare bene ed anche velocemente:
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(name)
for line in f:
n = int(line)
print n, "->", nextPalindrome(n)

if __name__ == "__main__":
main()


L'algoritmo sembra essere molto molto simile a quest'ultimo di cionci in effetti, l'abbiamo fatto in contemporanea. :p

[cionci]

Versione ottimizzata, da notare come alla fine va a ricalcare la prima versione con le stringhe :D
#define POWER_VECTOR_SIZE 10

int getLength(int n, int powerVector[])
{
int length = 1;
while(++length <= POWER_VECTOR_SIZE)
{
if(powerVector[length] > n)
return length;
}

return POWER_VECTOR_SIZE;
}

int mirrorInt(int n, int length, int powerVector[])
{
n = (n / powerVector[length / 2]) * powerVector[length / 2];

int i = 0;
int j = length - 1;

while(i < j)
{
n += ((n / powerVector[j--]) % 10) * powerVector[i++];
}
return n;
}


int findNextPalindrome(int n)
{
static int powerVector[] = {1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000 };

if(n < 10)
{
return n;
}

int length = getLength(n, powerVector);

int mirrored = mirrorInt(n, length, powerVector);
if(mirrored > n)
{
return mirrored;
}

int middle = length / 2;
if(length % 2 == 0)
{
middle--;
}

n += (int)pow(10, length - middle - 1);

return mirrorInt(n, getLength(n, powerVector), powerVector);
}
E' circa il doppio più veloce di quella con le stringhe e più veloce della precedente del 70% circa.
Edit: aggiunto lo static al vettore ed il rapporto è salito rispettivamente a 6 e 5 volte più veloce ;)

[DanieleC88]

int middle = length / 2;
if(length % 2 == 0)
{
middle--;
}

n += (int)pow(10, length - middle - 1);

return mirrorInt(n, getLength(n, powerVector), powerVector);
}
Questa parte la puoi ottimizzare ancora, in particolare ti puoi evitare una seconda chiamata a mirrorInt(). :)

[cionci]

Questa parte la puoi ottimizzare ancora, in particolare ti puoi evitare una seconda chiamata a mirrorInt(). :)
Non mi sembra che si possa, come fai a farlo ?
Se il numero è 1999999 o anche 999999 è impossibile evitare di fare nuovamente la copia.

[cionci]

C'era rimasta una piccola incoerenza dovuta al copia ed incolla:
#define POWER_VECTOR_SIZE 10

int getLength(int n, int powerVector[])
{
int length = 1;
while(++length <= POWER_VECTOR_SIZE)
{
if(powerVector[length] > n)
return length;
}

return POWER_VECTOR_SIZE;
}

int mirrorInt(int n, int length, int powerVector[])
{
n = (n / powerVector[length / 2]) * powerVector[length / 2];

int i = 0;
int j = length - 1;

while(i < j)
{
n += ((n / powerVector[j--]) % 10) * powerVector[i++];
}
return n;
}


int findNextPalindrome3(int n)
{
static int powerVector[] = {1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000 };

if(n < 10)
{
return n;
}

int length = getLength(n, powerVector);

int mirrored = mirrorInt(n, length, powerVector);
if(mirrored > n)
{
return mirrored;
}

n += powerVector[length / 2];

return mirrorInt(n, getLength(n, powerVector), powerVector);
}

[DanieleC88]

Non mi sembra che si possa, come fai a farlo ?
Se il numero è 1999999 o anche 999999 è impossibile evitare di fare nuovamente la copia.
Cavoli, hai ragione, con i numeri "agli estremi" il mio metodo non funziona correttamente. Peccato! :D

[bio82]

E' circa il doppio più veloce di quella con le stringhe e più veloce della precedente del 70% circa.
Edit: aggiunto lo static al vettore ed il rapporto è salito rispettivamente a 6 e 5 volte più veloce ;)

quanto + veloce? per la versione da 1k numeri...

intanto posto la mia soluzione..manca ancora 1 punto che ho scopiazzato dal web, ma lo metterò apposto....

http://bio.gbservicesnc.it/public/images/contest10v2.JPG (http://bio.gbservicesnc.it/?filename=contest10v2.JPG)


Public Class Form1

Public Function ReverseString(ByVal stringToReverse As String) As String
If stringToReverse.Length > 0 Then
Dim arr As Byte() = System.Text.UTF8Encoding.UTF8.GetBytes(stringToReverse)
Array.Reverse(arr)
Return System.Text.UTF8Encoding.UTF8.GetString(arr)
Else
Return ""
End If
End Function

Function palindromo(ByVal numero As String)
Dim risultato As String
Dim dimensione As Integer = numero.Length
If dimensione Mod 2 = 0 Then
'se lunghezza diviso 2 = 0
Dim dimensionea = dimensione / 2
Dim parte1 As String = numero.Substring(0, dimensionea)

If numero.Substring(dimensionea - 1, 1) < numero.Substring(dimensionea, 1) Then
parte1 = (Int(parte1) + 1).ToString
Else
Dim conta = 1
Do
If numero.Substring(dimensionea - conta, 1) < numero.Substring(dimensionea + conta - 1, 1) Then
parte1 = (Int(parte1) + 1).ToString
Exit Do
ElseIf numero.Substring(dimensionea - conta, 1) > numero.Substring(dimensionea + conta - 1, 1) Then
Exit Do
ElseIf dimensionea - conta = 0 Then
parte1 = (Int(parte1) + 1).ToString
Exit Do
End If
conta = conta + 1
Loop
End If

Dim parte2 As String = ReverseString(parte1)
risultato = parte1 & parte2
Else
'se lunghezza diviso 2 != 0
Dim dimensionea = Int(dimensione / 2)

Dim parte1 As String = numero.Substring(0, dimensionea)
Dim partecentrale As String = numero.Substring(dimensionea, 1)

If partecentrale < numero.Substring(dimensionea + 1, 1) Then
partecentrale = (Int(partecentrale) + 1).ToString
Else
Dim conta = 1
Do
If numero.Substring(dimensionea - conta, 1) < numero.Substring(dimensionea + conta, 1) Then
partecentrale = (Int(partecentrale) + 1).ToString
Exit Do
ElseIf numero.Substring(dimensionea - conta, 1) > numero.Substring(dimensionea + conta, 1) Then
Exit Do
ElseIf dimensionea - conta = 0 Then
partecentrale = (Int(partecentrale) + 1).ToString
Exit Do
End If

conta = conta + 1
Loop
End If
Dim parte2 As String = ReverseString(parte1)
risultato = parte1 & partecentrale & parte2
End If
Return risultato
End Function

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim watch As New System.Diagnostics.Stopwatch()
Dim risultato As String = ""
Dim numero As String
watch.Start()
Using sr As New System.IO.StreamReader("E:\scambio\progetti_vb\contest10\file1.dat")
Do
numero = sr.ReadLine()
If (numero) = "" Then Exit Do

risultato = risultato & palindromo(numero) & vbCrLf
Loop
sr.Close()
End Using
watch.Stop()
text_tempo.Text = watch.ElapsedMilliseconds & " ms"
text_risultati.Text = risultato
End Sub
End Class


16 ms per la versione da 1k numeri, mi pare 7 per la versione breve..

unico appunto, tratta i numeri già palindromi (come 808 nel file1.dat) andando al successivo (risultato 818, come richiesto implicitamente :P )...

ultima nota, c'è anche il tempo di lettura del file nel timer...

bio

[cionci]

quanto + veloce? per la versione da 1k numeri...

Non ho provato con i dati perché ci mettevo troppo poco.
Con 1 milione di numeri con la massima lunghezza (10 cifre) ci mette circa 98 ms.

Ora provo con il file dei dati, ma dipende troppo dall'hardware e dal compilatore ;)

[bio82]

Non ho provato con i dati perché ci mettevo troppo poco.
Con 1 milione di numeri con la massima lunghezza (10 cifre) ci mette circa 98 ms.

Ora provo con il file dei dati, ma dipende troppo dall'hardware e dal compilatore ;)

fa niente... era per chiedere...umiliare del mio codicillo non serve :D

(1 milione : 98ms = 1 k : X)

ho paura :D

bio

[cionci]

Aspe, ho visto ora che Gugo ha utilizzato numeri interi più grandi di maxint nel secondo file dei dati, non ci avevo fatto caso, credevo che si operasse esclusivamente sul limite massim degli interi. A questo punto bisogna operare necessariamente sulle stringhe.

Gugo: magari la prossima volta dillo nel testo :stordita:

[sottovento]

0.6 millisecondi per numeri da un milione di cifre (ovviamente se non ho calcolato male e se non ho fatto ERORI):

Dimenticavo: Buona Santa Lucia ai bimbi buoni! (vabbe', e' arrivata anche ai miei bimbi, che e' tutto dire...)


#include <stdio.h>
#include <time.h>

bool palindromiseString(char *strNumber, bool performCheck);
void increaseMiddle(char *strNumber);


void palindromise (char *strNumber)
{
if (!palindromiseString(strNumber, true))
{
increaseMiddle(strNumber);
palindromiseString(strNumber, false);
}
}

bool palindromiseString(char *strNumber, bool performCheck)
{
int i = 0;
int j = (int)strlen(strNumber) - 1;
if (performCheck)
{
while(i < j)
{
if (strNumber[j] > strNumber[i])
return false;
strNumber[j--] = strNumber[i++];
}
return true;
}
else
{
while(i < j)
strNumber[j--] = strNumber[i++];
return true;
}
}

void increaseMiddle(char *strNumber)
{
int length = (int)strlen(strNumber);
bool isEven = ((length % 2) == 0);
int index;
if (isEven)
index = (length / 2) - 1;
else
index = (length / 2);

while (index >= 0)
{
int val = strNumber[index] - '0';
val++;
if (val <= 9)
{
strNumber[index]++;
return;
}
strNumber[index] = '0' + index - 10;
index--;
}
}

[cionci]

Questo lavora sulle stringhe e quindi può superare i limiti degli interi.
Tempo sul file con 1000 numeri: 4 ms.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>


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

while(i < j)
{
s[j--] = s[i++];
}
}

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

while(j >= 0)
{
if(s[i++] > s[j--])
{
return 0;
}
}

return 1;
}

void addOneToMiddle(char *s)
{
unsigned int i = strlen(s) / 2 + strlen(s) % 2 - 1;
if(s[i] != '9')
{
s[i]++;
return;
}

while(s[i]++ == '9')
{
s[i] = '0';
if(i-- == 0)
return;
}
}


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

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

addOneToMiddle(s);

mirrorString(s);
}

int main(int argc, char** argv)
{
FILE * f = fopen(argv[1], "rt");

if(!f)
return -1;

char number[300];

while(1)
{
fscanf(f, "%s", number);

if(feof(f))
break;

findNextPalindrome(number);
printf("%s\n", number);
}

return 0;
}

[^TiGeRShArK^]

ecco il mio in python:

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:
halfIndex = len(number) / 2
if len(number) % 2 == 0:
halfIndex = len(number) / 2 - 1
palyndrome = list(number)
length = len(palyndrome)
i = halfIndex
needUpdate = False
while i >= 0 and palyndrome[length -i -1] == palyndrome[i]:
needUpdate = True
i = i -1
if needUpdate:
palyndrome[halfIndex] = str(int(number[halfIndex]) + 1)
if palyndrome[halfIndex + 1] > palyndrome[halfIndex]:
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

tempo impiegato sul file grande:
Elapsed time: 0.00887298583984

non male tenendo conto della lentezza di python :D

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

[cionci]

for(int i = 0; i < 1000000; i++)
{
char s[300];
sprintf(s, "%d", rand());
findNextPalindrome(s);
printf("%s\n", s);
}
Chiamando la ricerca in questo modo e redirigendo l'output su null o su file: 337 ms

[cionci]

P.S. cionci il file da 1 milione di numeri che hai usato si può avere così lo provo anch'io? :stordita:
Ho semplicemente usato un ciclo chiamando rand ;)

[bio82]

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]

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]

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 :D

il mio funziona (per una volta :P )

bio

[cionci]

il risultato di un numero come 226611 lo risolvi a 226622? e 226622?
Aspetta, mi hai fatto riflettere ed ho trovato un errore :D

[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]

Aspetta, mi hai fatto riflettere ed ho trovato un errore :D

questo errore l'ho visto facendo il file piccolo :D 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^]

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 :fagiano:

[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ò.. :stordita:

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]

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

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 :D

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

bio

[MasterDany]

edit...

[cdimauro]

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

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:

http://www.guidealgoritmi.it/images/ImgForums/Contest10CionciTiger.jpg

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 :confused:

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);
}


:bimbo:

[Vincenzo1968]

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

http://www.guidealgoritmi.it/images/ImgForums/Contest10Daniele.jpg

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()


:bimbo:

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

[^TiGeRShArK^]

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

http://www.guidealgoritmi.it/images/ImgForums/Contest10Daniele.jpg

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()


:bimbo:

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 :p
aggiungi una print e redireziona su file e vedi se cambia qualcosa :p

[Vincenzo1968]

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 :p
aggiungi una print e redireziona su file e vedi se cambia qualcosa :p

Ehm, Tiger,

aggiungo una print dove e come? Non ne capisco un tubo di python :D
Puoi gentilmente postarmi le modifiche? Grazie ;)

P.S. I tempi sono già presi con redirezione dell'output su file ;)

[^TiGeRShArK^]

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 palyndrome

print 'Elapsed time:', time.time() - t0

:fagiano:

[Vincenzo1968]

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 palyndrome

print 'Elapsed time:', time.time() - t0

:fagiano:

Grazie mille ;)

http://www.guidealgoritmi.it/images/ImgForums/Contest10Tiger.jpg

:bimbo:

[Vincenzo1968]

Questa è la classifica:

http://www.guidealgoritmi.it/images/ImgForums/Contest10Classifica.jpg

I tempi(in millisecondi) sono presi su un file da un milione di numeri con redirezione dell'output su file.

Manca il codice di Sottovento perchè non è completo(manca il main); il codice di Dave mi va in crash sul file grosso; il codice di Bio, invece, non c'è perché non so usare Visual Basic.

[..::DAVE::..]

Questa è la classifica:

http://www.guidealgoritmi.it/images/ImgForums/Contest10Classifica.jpg

I tempi(in millisecondi) sono presi su un file da un milione di numeri con redirezione dell'output su file.

Manca il codice di Sottovento perchè non è completo(manca il main); il codice di Dave mi va in crash sul file grosso; il codice di Bio, invece, non c'è perché non so usare Visual Basic.

il mio problema è nell'ultima riga... togli l'ultimo a capo e va :D dovrei correggerlo... ma per adesso tieni quello

[Vincenzo1968]

il mio problema è nell'ultima riga... togli l'ultimo a capo e va :D dovrei correggerlo... ma per adesso tieni quello

Classifica aggiornata:

http://www.guidealgoritmi.it/images/ImgForums/Contest10Dave.jpg

http://www.guidealgoritmi.it/images/ImgForums/Contest10Classifica.jpg

;)

[bio82]

il codice di Bio, invece, non c'è perché non so usare Visual Basic.


boooo brutto e cattivo... :oink:


Module Module1

Private Function ReverseString(ByVal stringa As String)

Return Strings.StrReverse(stringa)

End Function

Function palindromo(ByVal numero As String)
Dim risultato As String
Dim dimensione As Integer = numero.Length
If dimensione Mod 2 = 0 Then
'se lunghezza diviso 2 = 0
Dim dimensionea = dimensione / 2
Dim parte1 As String = numero.Substring(0, dimensionea)

If numero.Substring(dimensionea - 1, 1) < numero.Substring(dimensionea, 1) Then
parte1 = (Int(parte1) + 1).ToString
Else
Dim conta = 1
Do
If numero.Substring(dimensionea - conta, 1) < numero.Substring(dimensionea + conta - 1, 1) Then
parte1 = (Int(parte1) + 1).ToString
Exit Do
ElseIf numero.Substring(dimensionea - conta, 1) > numero.Substring(dimensionea + conta - 1, 1) Then
Exit Do
ElseIf dimensionea - conta = 0 Then
parte1 = (Int(parte1) + 1).ToString
Exit Do
End If
conta = conta + 1
Loop
End If

Dim parte2 As String = ReverseString(parte1)
risultato = parte1 & parte2
Else
'se lunghezza diviso 2 != 0
Dim dimensionea = Int(dimensione / 2)

Dim parte1 As String = numero.Substring(0, dimensionea)
Dim partecentrale As String = numero.Substring(dimensionea, 1)

If partecentrale < numero.Substring(dimensionea + 1, 1) Then
partecentrale = (Int(partecentrale) + 1).ToString
Else
Dim conta = 1
Do
If numero.Substring(dimensionea - conta, 1) < numero.Substring(dimensionea + conta, 1) Then
partecentrale = (Int(partecentrale) + 1).ToString
Exit Do
ElseIf numero.Substring(dimensionea - conta, 1) > numero.Substring(dimensionea + conta, 1) Then
Exit Do
ElseIf dimensionea - conta = 0 Then
partecentrale = (Int(partecentrale) + 1).ToString
Exit Do
End If

conta = conta + 1
Loop
End If
Dim parte2 As String = ReverseString(parte1)
risultato = parte1 & partecentrale & parte2
End If
Return risultato
End Function
Sub Main()
Dim watch As New System.Diagnostics.Stopwatch()
Dim risultato As String = ""
Dim numero As String
Dim leggifile As New System.IO.StreamReader("c:\temp\input.txt", False)
Dim scrivifile As New System.IO.StreamWriter("c:\temp\output.txt", False)
watch.Start()

Do
numero = leggifile.ReadLine
If (numero) = "" Then Exit Do
scrivifile.WriteLine(palindromo(numero))
Loop

watch.Stop()
scrivifile.Close()
leggifile.Close()
Console.Write(watch.ElapsedMilliseconds)
Console.ReadLine()
End Sub

End Module


http://rapidshare.de/files/41186156/ConsoleApplication1.zip.html

qui trovi il programma compilato, penso non ti serva null'altro che il .net framework installato (niubbo inside), prende come input il file c:\temp\input.txt e da come output c:\temp\output.txt...

essendo molto niubbo, non so come tenere aperta la console alla fine, quindi ho aggiunto un console.readline() che aspetta un input :D ... il numero che compare in console è il tempo impiegato in ms..

spero di aver rispettato tutte le regole :P

bio

ps: 1 milione di righe da 10 cifre sul mio pc la fa in 2200 ms
pps: fa sempre append al file, quindi se fai un paio di prove, cancellalo :D

[shinya]

Classifica aggiornata:
http://www.guidealgoritmi.it/images/ImgForums/Contest10Classifica.jpg

La tabella non è normalizzata.







Ok, ok...la smetto... :fagiano:

[cionci]

C'era un errore macroscopico nella mia versione :muro:
Ecco qua la versione riveduta e corretta:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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 = s[j--] - s[i++]));

return diff > 0;
}

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);
}

int main()
{
FILE * f = fopen("Dati3.dat", "r");
char buffer[300];
while(1)
{
fgets(buffer, 299, f);
findNextPalindrome(buffer);
puts(buffer);
if(feof(f))
break;
}

return 0;
}

Con un milione di numeri (utilizzando il generatore di Vincenzo):
time ./Contest10 > file

real 0m0.496s
user 0m0.340s
sys 0m0.148s

Provo a vedere se ottengo miglioramenti con l'aritmetica dei puntatori ;)

[Vincenzo1968]

boooo brutto e cattivo... :oink:
...


:D

Cattivo, forse. Brutto no. Questa è la mia foto:

http://www.guidealgoritmi.it/images/ImgForums/scimmia.jpg

Alla fine ho risolto creando un nuovo progetto VB e copincollando il tuo codice. È stato facile ;)

Ecco i tempi tuoi(e quelli della nuova versione di Cionci) sulla mia macchina:
http://www.guidealgoritmi.it/images/ImgForums/Contest10BioCionci.jpg

Tra un po' aggiorno la classifica.

[Vincenzo1968]

Eqque qua:

http://www.guidealgoritmi.it/images/ImgForums/Contest10Classifica2.jpg

:bimbo:

[bio82]

Eqque qua:
:bimbo:

il mio E8200 è il 30% + veloce del tuo 4800+ :D

domanda fuori concorso, dato che quando metto in pausa il debug (su visualstudio) mi esce l'avviso che non posso modificare applicazioni a 64 bit, non è che compilo a 64 bit (non volendo)?

cambierebbe qualcosa in un'applicazione come questa dove si maneggiano stringhe (e non interi a 64 per esempio)?

o sto dicendo solo stronzate :D ?

bio

[Vincenzo1968]

il mio E8200 è il 30% + veloce del tuo 4800+ :D

domanda fuori concorso, dato che quando metto in pausa il debug (su visualstudio) mi esce l'avviso che non posso modificare applicazioni a 64 bit, non è che compilo a 64 bit (non volendo)?

cambierebbe qualcosa in un'applicazione come questa dove si maneggiano stringhe (e non interi a 64 per esempio)?

o sto dicendo solo stronzate :D ?

bio

Boh! :confused:

Ricordo che i tempi li prendo con questa applicazione C++ che Cionci aveva proposto in un altro contest:


#include <iostream>
#include <process.h>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
if(argc == 1)
return 1;

clock_t start = clock();
char **argv2 = &argv[1];
spawnvp(_P_WAIT, argv2[0], argv2);
cerr << endl << "User time: " << ((double)(clock() - start)*1000)/CLOCKS_PER_SEC << "ms" << endl;
return 0;
}

[bio82]

Ricordo che i tempi li prendo con questa applicazione C++ che Cionci aveva proposto in un altro contest:



adesso ho capito perchè quando metti l'immaginetta c'è scritto "tempi progetto >output"...

:Prrr:


bio

[Vincenzo1968]

Ho recuperato Sottovento aggiungendo la funzione main:

http://www.guidealgoritmi.it/images/ImgForums/Contest10Sottovento.jpg

http://www.guidealgoritmi.it/images/ImgForums/Contest10Classifica3.jpg

El còdigo fuente:

#include <stdio.h>

int palindromiseString(char *strNumber, int performCheck);
void increaseMiddle(char *strNumber);

void palindromise (char *strNumber)
{
if (!palindromiseString(strNumber, 1))
{
increaseMiddle(strNumber);
palindromiseString(strNumber, 0);
}
}

int palindromiseString(char *strNumber, int performCheck)
{
int i = 0;
int j = (int)strlen(strNumber) - 1;
if (performCheck)
{
while(i < j)
{
if (strNumber[j] > strNumber[i])
return 0;
strNumber[j--] = strNumber[i++];
}
return 1;
}
else
{
while(i < j)
strNumber[j--] = strNumber[i++];
return 1;
}
}

void increaseMiddle(char *strNumber)
{
int length = (int)strlen(strNumber);
int isEven = ((length % 2) == 0);
int index;
if (isEven)
index = (length / 2) - 1;
else
index = (length / 2);

while (index >= 0)
{
int val = strNumber[index] - '0';
val++;
if (val <= 9)
{
strNumber[index]++;
return;
}
strNumber[index] = '0' + index - 10;
index--;
}
}

int main()
{
FILE * f = fopen("File3.dat", "r");
char buffer[300];
while(1)
{
fgets(buffer, 299, f);
palindromise(buffer);
puts(buffer);
if(feof(f))
break;
}

return 0;
}


:bimbo:

[cionci]

Ho recuperato Sottovento aggiungendo la funzione main:
E' praticamente identico al mio. Però prova immettere 999 come numero. Non si ottiene 1001 come dovrebbe fare ;)

[Vincenzo1968]

E' praticamente identico al mio. Però prova immettere 999 come numero. Non si ottiene 1001 come dovrebbe fare ;)

Ahò, li mortan guerieri, è vero.

http://www.guidealgoritmi.it/images/ImgForums/scimmia.jpg

Aspettiamo che Sottovento risolva il problema. Per il momento, dunque, la classifica è questa:

http://www.guidealgoritmi.it/images/ImgForums/Contest10Classifica2.jpg

:bimbo:

[cdimauro]

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:

La versione psyco di Tiger è questa:
[...]
e impiega più tempo rispetto alla versione normale :confused:
La versione di Daniele sembra, invece, beneficiare dell'uso di psyco:
E' normale. Psyco agisce compilando tutte le funzioni che vengono mano a mano definite.

Il codice di "Tiger" non ha funzioni, mentre quello di Daniele sì, per cui nel primo caso il codice va anche più lento (perché alla normale esecuzione si aggiunge l'overhead di psyco), mentre nel secondo caso riesce a beneficiarne.

Inoltre ci sono 3 cose da considerare.

Con Python è sempre meglio utilizzare le variabili locali (quelle definite all'interno delle funzioni) anziché globali, perché il codice risultante è molto più veloce (nel primo caso NON viene effettuato NESSUN look-up nello scope per accedere alla variabile; nel secondo caso si deve necessariamente analizzare il global scope del modulo corrente, e in caso di fallimento anche lo scope degli identificatori built-in).

Inoltre avendo a che fare con una quantità non piccola di dati da generare, è sempre meglio usare la funzion built-in xrange anziché range, perché nel primo caso i numeri vengono generati man mano che servono, mentre nel secondo caso viene PRIMA generata l'intera lista di numeri, e successivamente "consumata" (scorrendo gli elementi uno alla volta; inoltre alla fine, quando la lista non viene più utilizzata, si attiva il garbage collector per finalizzare gli elementi della lista e infine la lista stessa).

In sezioni computazionalmente intensive è preferibile disattivare il garbage collector, e abilitarlo alla fine, in questo modo:
import gc

gc.disable()
....
Codice da eseguire
...
gc.enable()
Le prestazioni possono beneficiarne anche di molto.

[Vincenzo1968]

Disattivando il garbage collector ottengo i seguenti risultati:

http://www.guidealgoritmi.it/images/ImgForums/Contest10DanieleTiger.jpg

Il tempo di Tiger migliora leggermente; quello di Daniele peggiora. :confused:

Questo è il codice:

Daniele:

import psyco
import gc

gc.disable()

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()


Tiger:

from __future__ import with_statement
import time
import gc

gc.disable()

numbers = []
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 xrange(halfIndex, -1, -1):
palyndrome[length -i -1] = palyndrome[i]
print palyndrome

print 'Elapsed time:', time.time() - t0

#gc.enable()

[cdimauro]

Non mi spiego perché il codice di Daniele peggiori, anche se di poco.