[java] palindroom probleem

[Verwijderd]

Hoi allemaal,

Ik las vanavond het volgende probleem bij een coder wedstrijd van Oracle:

Sample Problem Statement #2:
A palindrome is a number that is the same whether it is read from left-to-right or right-to-left. For example, 121 and 34543 are both palindromes. It turns out that nearly every integer can be transformed into a palindrome by reversing its digits and adding it to the original number. If that does not create a palindrome, add the reverse of the new number to itself. A palindrome is created by repeating the process of reversing the number and adding it to itself until the number is a palindrome.

Create a class Transform that contains the method palindrome, which takes a number N that is to be transformed and returns a number that is the resultant palindrome from this process. Of course if N is already a palindrome, return it without changing it. Though it is theorized that all numbers can be transformed to palindromes in this way, some numbers do not converge in a reasonable amount of time. For instance, 196 has been carried out to 26,000 digits without finding a palindrome. So if the method finds that the resultant palindrome must be greater than 1,000,000,000, return the special value -1 instead.

DEFINITION
Class: Transform
Method: palindrome
Parameters: int
Returns: int
Method signature (be sure your method is public): int palindrome(int N);

NOTES
Leading zeroes are never considered part of a number when it is reversed. For instance, 12's reverse will always be 21 regardless of whether it is represented as 12, 012, or 0012. Examples with leading zeroes use the leading zeroes for clarity only.

TopCoder will ensure the validity of the inputs. Inputs are valid if all of the following criteria are met:
- N will be between 1 and 10000 inclusive.

EXAMPLES
Worked examples:
Example 1: N = 28
28 + 82 = 110
110 + 011 = 121, a palindrome. Return 121

Example 2: N = 51
51 + 15 = 66, a palindrome. Return 66

Example 3: N = 11, return 11
Example 4: N = 607, return 4444
Example 5: N = 196, return -1

Ik had even niks te doen, dus ik dacht laat ik het eens proberen. Dit is de code waar ik op ben gekomen:

code:

public class Test {
    private int count = 0;
    public Test () {
        for (long i = 0; i < 1000; i++) {
            System.out.println("" + i + ": "  + palindrome(i));
        }
        System.out.println("I found: " + count + " palindromes.");
    }

    public long palindrome(long find) {
        if (find > 100000000) {
            return -1;
        }

        if (isPalindrome(find)) {
            count++;
            return find;
        } else {
            find = find + reverse(find);
            return palindrome(find);
        }
    }

    public boolean isPalindrome(long find) {
        String s = "" + find;
        if (find == reverse(find)) {
            return true;
        }
        return false;
    }

    public long reverse (long find) {
        String s_value = "" + find;
        s_value = reverse(s_value);
        long return_val = -1;
        try {
            return_val = Long.parseLong(s_value);
        } catch (NumberFormatException e) {
            e.printStackTrace();
        }
        return Long.parseLong(s_value);
    }

    public String reverse(String find) {
        char reversed[] = new char[find.length()];
        for (int i = 0; i < find.length(); i++)
            reversed[i] = find.charAt(find.length() - i - 1);
        return new String(reversed);
    }

    public static void main(String args[]) {
        new Test();
    }
}

De klasse namen e.d. kloppen niet helemaal volgens de specs. Maar het ging me alleen maar om het idee...
Wat vinden jullie van de code? En hoe zou die verder verbeterd kunnen worden?

[.oisyn]

Waarvoor is die String s in isPalindrome () ?

[ReLight]

volgens mij kan dit in php veel sneller.


in theorie zoiets uitwerken ?:
TEST:
input>100000 TEST(TRUE) break.
count=digitcount(input)
count=oneven ->read 0->1/2(count-1) = reverse(read (1/2(count+1))->end) True->palindrome FALSE->Convert
count=even ->read 0->1/2(count) = reverse(read (1/2count)->end) True-> palindrome FALSE->Convert


TEST(TRUE)->return(input)
TEST(False)->CONVERT

CONVERT:
input=input+reverse(input)
TEST(input)

[mbravenboer]

Ik krijg altijd koppijn van zulke algoritmes, dus heb geen zin om daar op in te gaan , maar kan wel wat kleine dingen zeggen over de performance en stijl van je code.

code:

    public boolean isPalindrome(long find) {
        String s = "" + find;
        if (find == reverse(find)) {
            return true;
        }
        return false;
    }

Je hoort vaak mensen opmerken dat het een goede stijl is om dit gewoon zo te schrijven:

code:

    public boolean isPalindrome(long find) {
        return find == reverse(find));
    }

code:

    public String reverse(String find) {
        char reversed[] = new char[find.length()];
        for (int i = 0; i < find.length(); i++)
            reversed[i] = find.charAt(find.length() - i - 1);
        return new String(reversed);
    }

Hum... Ik wilde gaan zeuren waarom je hier niet gewoon String.reverse() gebruikt, maar die is er dus inderdaad niet .

code:

    public long reverse (long find) {
        String s_value = "" + find;
        s_value = reverse(s_value);
        long return_val = -1;
        try {
            return_val = Long.parseLong(s_value);
        } catch (NumberFormatException e) {
            e.printStackTrace();
        }
        return Long.parseLong(s_value);
    }

Dit is een beetje vreemde code: eerst try je de zaak te parsen en daarna doe je het gewoon alsnog zonder dit in een try te doen . Je 'eet' hier in feite ook je Exception op, wat niet zo netjes in.

code:

    public long reverse (long find) throws NumberFormatException {
        return reverse(String.valueOf(find));
    }

Je gooit de exception dan gewoon door. Je kan hem dan later elders opvangen.

code:

    public static void main(String args[]) {
        new Test();
    }
}

Ik houd er zelf niet zo van om een klasse aan het werk te zetten in de constructor, waardoor je alleen maar een instantie aanmaakt. Wellicht kan je een methode 'run' maken die de test draait en dan new Test().run() doen.

Sorry dat het geen algoritmisch commentaar is . Sowieso is het belangrijk om bij dit soort intensieve zaken zeer goed op te laten hoe efficient je operaties implementeert. De reverse van een long zou bijvoorbeeld ook prima zonder een tussenstap naar een String kunnen, waardoor je veel object create (en dus garbage) voorkomt.

[mbravenboer]

ReLight: volgens mij kan dit in php veel sneller.

Met sneller bedoel je hier sowieso hopelijk compacter. Wat dat betreft: dat heeft nogal weinig met de taal te maken, maar vooral met de manier van noteren en de hoeveelheid foutopvang die je daarin opneemt. Je kan ook zo je vraagtekens zetten bij de duidelijkheid van zo compact mogelijk gemaakt code (Ik ga geen concrete taal of sport noemen ).

[.oisyn]

mbravenboer: De reverse van een long zou bijvoorbeeld ook prima zonder een tussenstap naar een String kunnen, waardoor je veel object create (en dus garbage) voorkomt.

PHP:

public long reverse (long l)
{
    if (l < 10)
        return l;

    long r = 0;
    while (l > 0)
    {
        r = r * 10 + l % 10;
        l /= 10;
    }

    return r;
}

[ReLight]

Geef ik je 100% gelijk in Fout opsporing/opvank is wel belangrijk, maar ondergeschikt in dit soort theoretische vraagstukjes, er wordt immers een INT aangeboden en niet een string per ongeluk.Ik bedoelde inderdaad compacter qua notatie, maar ook in mogelijke kortheid aan code.

Het zou leuker zijn een wedstrijd te doen met een char count voor de functie. Maar dan zal C wel winnen

Toch complimentje aan de topcstarter, je moet er maar zin in hebben op dinsdag avond.

[Verwijderd]

Een leuke gelegenheid om m'n oude MSX weer van zolder te halen en eens lekker in MSX basic te gaan klooien. Je mist na verloop van jaren gewoon het gezellige gepiep van een data-recorder.

Lekker scheel worden achter m'n 22" TV

(en ja, ik weet het, regelnummers zuigen )

[ACM]

.oisyn schreef op 28 augustus 2002 @ 00:08:

Wat doet die met een getal als 100000
Want string-reverse technisch moet dat 000001 worden toch?

[.oisyn]

ACM schreef op 28 augustus 2002 @ 00:18:
[nohtml]
[...]
[/nohtml]
Wat doet die met een getal als 100000
Want string-reverse technisch moet dat 000001 worden toch?

je moet het getal gewoon omdraaien, de string representatie doet er niet zo toe
000001 is gewoon 1 (zoals ook in het artikel staat):

NOTES
Leading zeroes are never considered part of a number when it is reversed. For instance, 12's reverse will always be 21 regardless of whether it is represented as 12, 012, or 0012. Examples with leading zeroes use the leading zeroes for clarity only

dus om van 100000 een palindroom te maken doe je 1000000 + reverse (100000) = 100000 + 1 = 100001 = een palindroom

[ReLight]

<wiseass> dromen van paling->palindrome </wiseass>

edit: okey is flauw, excuus, het is laat. en hier krijg je koppijn van /edit

[Verwijderd]

ReLight schreef op 28 augustus 2002 @ 00:31:
<wiseass> dromen van paling->palindrome </wiseass>

Uhm ja?

[.oisyn]

ReLight schreef op 28 augustus 2002 @ 00:31:
<wiseass> dromen van paling->palindrome </wiseass>

okee...

[Soultaker]

Mooie programmeeropgave is dit. Ze geven je de oplossing eigenlijk al kado in de vraagstelling en er is nauwelijks ruimte (of noodzaak) voor eigen inbreng. Palindroomopgaven zijn sowieso wel heel erg veelvoorkomend; je hoort er eigenlijk niet meer bij als je nog nooit een palindroomopgave verzonnen dan wel opgelost hebt.

Een heel wat leukere opgave over palindromen is te vinden in de set opgaven van het Nederlands Kampioenschap Programmeren 2001:
http://ch.its.tudelft.nl/...chief/2001/nkp/html/#opgb
Er staan trouwens ook uitwerkingen op de website, voor wie er niet uitkomt.

Ook zitten er palindroomopgaven tussen de opgaven van de USACO training gateway:

PALINDROMIC SQUARES

Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome.

Given a number base B (2 <= B <= 20 base 10), print all the integers N (1 <= N <= 300 base 10) such that the square of N is palindromic when expressed in base B; also print the value of that palindromic square. Use the letters 'A', 'B', and so on to represent the digits 10, 11, and so on.

Print both the number and its square in base B.

PROGRAM NAME: palsquare

INPUT FORMAT
A single line with B, the base (specified in base 10).

SAMPLE INPUT (file palsquare.in)
10

OUTPUT FORMAT
Lines with two integers represented in base B. The first integer is the number whose square is palindromic; the second integer is the square itself.

SAMPLE OUTPUT (file palsquare.out)
1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696

DUAL PALINDROMES

A number that reads the same from right to left as when read from left to right is called a palindrome. The number 12321 is a palindrome; the number 77778 is not. Of course, palindromes have neither leading nor trailing zeroes, so 0220 is not a palindrome.

The number 21 (base 10) is not palindrome in base 10, but the number 21 (base 10) is, in fact, a palindrome in base 2 (10101).

Write a program that reads two numbers (expressed in base 10):
- N (1 <= N <= 15)
- S (0 < S < 10000)

and then finds and prints (in base 10) the first N numbers strictly greater than S that are palindromic when written in two or more number bases (2 <= base <= 10).

Solutions to this problem do not require manipulating integers larger than the standard 32 bits.

PROGRAM NAME: dualpal

INPUT FORMAT
A single line with space separated integers N and S.

SAMPLE INPUT (file dualpal.in)
3 25

OUTPUT FORMAT
N lines, each with a base 10 number that is palindromic when expressed in at least two of the bases 2..10. The numbers should be listed in order from smallest to largest.

SAMPLE OUTPUT (file dualpal.out)
26
27
28

Voor (intelligente) vragen en opmerkingen over dit soort programmeeropgaven is wat mij betreft altijd plaats op GoT. Ik vind deze USACO opgaven overigens wat flauw; als je een leuk probleem zoekt kun je beter die van 't NKP proberen (al is die misschien wat moeilijker).

[Dash2in1]

Uit die programmeerwedstrijd:

Voor elk geval geef je 1 regel uitvoer met daarop het kleinste aantal letters dat moet worden weggelaten om een palindroom te vormen

Maar dan geven ze als voorbeeld:

code:

invoer     uitvoer
---------------------
   3           0
anna           3

Moet dat niet ook 0 zijn bij die anna? Er staat nl nergens beschreven dat er minimaal 1 weg moet (anders zou de bovenste ook niet kloppen natuurlijk).

[Dido]

Dash2in1 schreef op 28 augustus 2002 @ 12:46:
Uit die programmeerwedstrijd:

[...]


Maar dan geven ze als voorbeeld:

code:

invoer     uitvoer
---------------------
   3           0
anna           3

Moet dat niet ook 0 zijn bij die anna? Er staat nl nergens beschreven dat er minimaal 1 weg moet (anders zou de bovenste ook niet kloppen natuurlijk).

Dat staat er niet, er staat:
INVOER:
3, anna, hallo, programmeerwedstrijd
UITVOER:
0, 3, 14

Die eerste 3 van de invoer is het aantal woorden dat volgt. Specs lezen voordat je begint, he

[Verwijderd]

Leuke site, die van het NKP. Helaas is het niveau van de vragen toch wat te hoog voor mij. Ik heb zelf informatica gestudeerd op de HTS. Ik hou me ook niet dagelijks bezig met dit soort problemen. (Gelukkig maar). Ik denk dat ik voor een opgave als dit minimaal een week bezig ben . Wel leuk... Bedankt voor de link....

[Sjaaky]

Ik heb met mijn team toendertijd die palindroom opgave op het NKP2001 gemaakt. Gewoon lekker naief recursief, maar dat werd al heel snel heel langzaam (zeg maar ongeveer het idee dat je fibonacci volledig recursief implementeert).
Na een aantal optimalisaties kregen we nog steeds een 'runtime exceeded', wat dus betekent dat het te langzaam was.
Helaas pas na de wedstrijd bedacht dat je de invoer van een recursieve functie kan coderen als string en dan met de uitvoer in een hashtable zetten.
Je kan dan heel snel bepalen of de functie met bepaalde parameters al voorbij is gekomen en dan kan je dus ook heel snel het antwoord geven.

[Dash2in1]

Dido schreef op 28 augustus 2002 @ 12:52:
[...]

Dat staat er niet, er staat:
INVOER:
3, anna, hallo, programmeerwedstrijd
UITVOER:
0, 3, 14

Die eerste 3 van de invoer is het aantal woorden dat volgt. Specs lezen voordat je begint, he

Hmm ik kom echt uit een ei zo te zien

[Dido]

Dash2in1 schreef op 28 augustus 2002 @ 14:45:
Hmm ik kom echt uit een ei zo te zien

Geeft niet, sommigen die ik ken zitten er nog in

Waarom zit ik nou al een hele middag in ASM te k*tten om getalletje LIFO op een stack te zetten?

[Soultaker]

Off-topic:

Dido schreef op 28 augustus 2002 @ 15:11:
Waarom zit ik nou al een hele middag in ASM te k*tten om getalletje LIFO op een stack te zetten?

Je weet dat je hiervoor de push/pop instructies kan misbruiken, mits je je stack pointer bewaart? Boundary checking zelf toevoegen natuurlijk.

[Dido]

Ja natuurlijk... maar ik bedoelde dus, om een inverse functie te schrijven
Volgens mij moet dat in ASM heel snel kunnen, de vcijfertjes je stack op pushen, ze dan weer poppen, dan staan ze anders om. Maar als je niet slim omspringt met het opslitsen en weer samenstellen van je getal schiet je er nog weinig mee op...

[ Voor 0% gewijzigd door Dido op 28-08-2002 15:21 . Reden: vijvertjes op je stack = lekke koeling :) ]

[.oisyn]

Soultaker schreef op 28 augustus 2002 @ 15:16:
Off-topic:


[...]


Je weet dat je hiervoor de push/pop instructies kan misbruiken, mits je je stack pointer bewaart? Boundary checking zelf toevoegen natuurlijk.

en met stos*/lods* kan het ook, dan kun je ook je richting kiezen

[Sjaaky]

Je hoeft geen inverse functie te schrijven om te zien of iets een palindroom is.
Gewoon in een loopje van i = 0 tot lengte/2 (naar beneden afgerond) charAt(i) met charAt(lengte-i-1) vergelijken. .
In asm kan je jammer genoeg geen 'repe cmpsb' doen, zodanig dat si automatisch ophoogt en di automatisch verlaagt. Maar om dit in asm te programmeren vind ik eigenlijk wel een beetje ver gaan. Eigenlijk ook heel erg , maar na een aantal jaar geprogd te hebben in asm, ben ik toch maar hogere programmeertalen gaan gebruiken. :-)