Palindrome Programmering

7. august 2011

Hva i all verden er dette?

Siden vi var så flinke på fibonacci's tallrekke, kan vi like gjerne bry hjernen våres med strenger som er palindrome.

Palindrome, que?

Tekster som er palindrome kan leses fra venstre og fra høyre, men uttales helt likt. Eksempler:

Agnesisenga = agnesisengA
Sas = saS
Radar = radaR

Oppgaven

Lag et program/script som sjekker om strengen brukeren skriver inn er et palindrome!

Mitt forslag

Kode

import java.util.Scanner;


public class palinedrome {

	palinedrome()
	{
		System.out.println("Skriv inn en streng: "); 
		Scanner in = new Scanner(System.in); 
		String tekst = in.next(); 
		
		if(palinedrome(tekst) == true) System.out.println("Strengen du skrev inn er et palinedrome!"); 
		else System.out.println("Strengen du skrev inn er IKKE et palinedrome"); 
	}
	
	public boolean palinedrome(String tekst)
	{
		int v = 0; 
		int h  = tekst.length()-1; 
		
		while(v > h)
		{
			if(tekst.charAt(v) != tekst.charAt(h)) return false;	//er bokstavene like?
			v++;													//bla til høyre
			h--; 													//bla til venstre			
		}
		return true;
	}
	
	
	public static void main(String[] args)
	{
		
		new palinedrome(); 
	}
}

Hva er ditt forslag?

Sist endret av Opous; 7. august 2011 kl. 23:23.

z0p

uʍop ǝpısdn

3.814 906

8. august 2011

python one liner

Kode

s[0:int(round((len(s)/2)-0.1))] == s[::-1][0:int(round((len(s)/2)-0.1))]

Goophy

pls

4.629 1.276

8. august 2011

Perl 4 ever!

perl -nle 'print if $_ eq reverse'

Katt

450 843

8. august 2011

Palindromer kan også være nummeriske

f.eks 10010101001

Kalakov

1.638 355

8. august 2011

Ganske minimalistisk Ruby:

Kode

puts ARGV[0] == ARGV[0].reverse

Restyle

exquisite

4.700 1.391

8. august 2011

Veldig raskt eksempel slengt sammen med rekusjon:

Kode

public class Palindrome {
	
	public static int x, y;
	
	public static void main(String[] args) {
		String input = "anna";
		x = 0;
		y = input.length();
		System.out.println(testPalindrome(input));
	}
	
	public static String testPalindrome(String p) {
		char a = p.charAt(x++);
		char b = p.charAt((y--) - 1);
		
		if(a != b) return "false";
		if(x == y || x > y) return "true";
		else return testPalindrome(p);
	}
}

Nytt eksempel:

Kode

public class Palindrome {
	public static void main(String[] args) {
		String o = "Some string";
		StringBuffer b = new StringBuffer(o);
		b = b.reverse();
		System.out.println(b.toString().equals(o) ? "true" : "false");
	}
}

Provo

5.579 14.200

8. august 2011

C++ har ikke sånne "reverse"-juksefunksjoner, men det kan bli relativt kompakt likevel.

Kode

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

int main(int argc, char* argv[]){
	bool check = true;
	for(int i = 0; i < strlen(argv[1]); ++i)
		check = check && argv[1][i] == argv[1][strlen(argv[1]) - 1 - i];
	std::cout << check << std::endl;
	return 0;
}

snippsat

1.393 716

8. august 2011

@z0p du kunne ha droppet den string slice opplegget og gjort det enklere.

Kode

s == s[::-1]

Denne er kortere og resultatet blir det samme.

Kode

>>> s = '1881'
>>> s == s[::-1]
True
>>> s[0:int(round((len(s)/2)-0.1))] == s[::-1][0:int(round((len(s)/2)-0.1))]
True
>>> s = 'AgnesisengaA'.lower()
>>> s == s[::-1]
True
>>> s[0:int(round((len(s)/2)-0.1))] == s[::-1][0:int(round((len(s)/2)-0.1))]
True
>>> s = 'AgnesisengaA'.lower()
>>> s == s[::-1]
False
>>> s[0:int(round((len(s)/2)-0.1))] == s[::-1][0:int(round((len(s)/2)-0.1))]
False

Kan jo også ta med en med lambda.

Kode

p = lambda s:s == s[::-1]

Kode

>>> p = lambda s:s == s[::-1]
>>> p('racecar')
True
>>> (lambda s:s == s[::-1])('1881')
True
>>>

Sist endret av snippsat; 8. august 2011 kl. 08:01.

z0p

uʍop ǝpısdn

3.814 906

8. august 2011

snippsat: korrekt. men litt av greia er vel å ikke bare bruke de åpenbare løsningene? Nå skal jeg ikke påstå at den er noe mer effektiv

men den sjekker ihvertfall bare halvparten av strengen ot hverandre.

Uansett, kan et palindrom være en karakter?

Jee

52 16

8. august 2011

http://www.fun-with-words.com/palin_panama.html <-- Litt programmeringshistorie

Opous

Trådstarter

185 15

8. august 2011

Sitat av z0p

python one liner

Kode

s[0:int(round((len(s)/2)-0.1))] == s[::-1][0:int(round((len(s)/2)-0.1))]

Vis hele sitatet...

WOW, pent!

snippsat

1.393 716

8. august 2011

snippsat: korrekt. men litt av greia er vel å ikke bare bruke de åpenbare løsningene?

Vis hele sitatet...

Ja enig z0p løsningen din var bra,var nok rimlig sikkert på at du visste om den kortere løsning.
Ja da er hvertfall den koreste løsningen for python vist fram.

Uansett, kan et palindrom være en karakter?

Vis hele sitatet...

Ja,per definisjon er også en string med lengde 0 palindrome og f.eksp a. palindrome når man fjerner punktum.

http://www.fun-with-words.com/palin_panama.html <-- Litt programmeringshistorie

Vis hele sitatet...

En utvidet oppgave kan jo være og sjekke om setninger er palindrome.
A man, a plan, a canal – Panama!
A dog, a pant, a panic in a Patna pagoda!

Nå skal jeg ikke påstå at den er noe mer effektiv men den sjekker ihvertfall bare halvparten av strengen ot hverandre.

Vis hele sitatet...

Ja det har du rett i,men dette overveier på ingen måte at koden kaller len() og round()
Tester litt,kun for gøy

Kode

import timeit

def runMe(s):
    s[0:int(round((len(s)/2)-0.1))] == s[::-1][0:int(round((len(s)/2)-0.1))]
    #Time 25.6080107299

def runMe1(s):
    s == s[::-1]
    #Time 3.10865780157

print timeit.Timer("runMe('saippuakuppinippukauppias')",'from __main__ import runMe').timeit(number=1000000)

Vi ser at på 1000000 loops at det er en forskjell 3sek mot 25sek.
Kjører jeg profile av koden ser vi hvorfor.

Kode

#s == s[::-1]
1000024 function calls in 1.137 CPU seconds

Kode

#s[0:int(round((len(s)/2)-0.1))] == s[::-1][0:int(round((len(s)/2)-0.1))]
5000024 function calls in 6.841 CPU seconds

Vi ser 4mill flere function calls,p.g.a len() og round()

Kode

2000000    0.722    0.000    0.722    0.000 :0(len)
2000000    2.586    0.000    2.586    0.000 :0(round)

Provo

5.579 14.200

8. august 2011

Sitat av snippsat

Vi ser at på 1000000 loops at det er en forskjell 3sek mot 25sek.

Vis hele sitatet...

Til sammenlikning, like mange runder med samme streng i C:

Kode

#include <stdio.h>
#include <string.h>
#include <sys/time.h>

inline int palindrome(const char *str){
	int i, str_half_length = strlen(str)/2;
	for(i = 0; i < str_half_length; ++i){
		if(str[i] != str[str_half_length - 1 - i]){
			return 0;
		}
	}
	return 1;
}

int main(int argc, char* argv[]){
	const char *str = "saippuakuppinippukauppias";
	int i;
	struct timeval start, end;
	gettimeofday(&start, 0);
	for(i = 0; i < 1000000; ++i){
		palindrome(str);
	}
	gettimeofday(&end, 0);
	printf("%.3f ms\n", (end.tv_sec - start.tv_sec) * 1000 + (float)(end.tv_usec - start.tv_usec) / 1000);
	return 0;
}

Kompilert med gcc med optimalisering O3: Tidsforbruk på kjøretid, 0.001 ms.

z0p

uʍop ǝpısdn

3.814 906

8. august 2011

hehe. Jeg tenkte få iterasjoner, og lange strenger, men jeg ser gevinsten ikke eksisterende der også

dog ble jeg vel ikke akkurat overrasket.

men dersom man for morroskyld optimaliserer litt vil man se en liten fordel. Dog ikke nok til å kompansere for iterasjoner

Kode

import timeit
import random
import string

def run1(s):
    m = (len(s)/2))+1
    s = s[0:m]
    s == s[::-1]


def run2(s):
    s == s[::-1]

s = ''.join(random.choice(string.letters) for i in xrange(10000)) * 9000
print timeit.Timer('run("%s")'%s,'from __main__ import run1 as run').timeit(number=100)

men jo da, jeg ville nok gått for "s == s[::-1]" foran min selv

Edit: ble ikke helt bra test scenario der

Sist endret av z0p; 8. august 2011 kl. 19:39.