[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?
mi sa che è ora che tu vada a letto in effetti

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

[fero86]

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

[G30]

Originariamente inviato da fero86

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

Esatto

[gugoXX]

Originariamente inviato da fero86

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

Sisi',errore mio. Correggo.

[gugoXX]

Originariamente inviato da ^TiGeRShArK^

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

Si, meglio che vada va...

[bio82]

Originariamente inviato da gugoXX

Si, meglio che vada va...

primo

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



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

Originariamente inviato da ndakota

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

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

Originariamente inviato da ..::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?

Non è strano se ci mette meno di un secondo

[..::DAVE::..]

Originariamente inviato da cionci

Non è strano se ci mette meno di un secondo

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

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]

Originariamente inviato da cionci

Ve gusta ?

[...]

Forte!

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

[..::DAVE::..]

Originariamente inviato da cionci

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