[vari] Contest 10: Numeri palindormi (Semplice)

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

Originariamente inviato da MasterDany

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]

Originariamente inviato da ..::DAVE::..

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]

Originariamente inviato da cionci

Versione senza l'uso di stringhe:

[...]

Oddio, hai fatto qualcosa di molto simile a ciò che sto facendo io!

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.

[cionci]

Versione ottimizzata, da notare come alla fine va a ricalcare la prima versione con le stringhe

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

Originariamente inviato da cionci

    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]

Originariamente inviato da DanieleC88

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]

Originariamente inviato da cionci

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!

[bio82]

Originariamente inviato da cionci

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....

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]

Originariamente inviato da bio82

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]

Originariamente inviato da cionci

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

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

ho paura

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

[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

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

[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