[Løst] Lage ord av tilfeldige bokstaver

[v3g4rd]

Hei alle sammen!

 

Tidligere i dag fikk jeg for meg at det hadde vært morsomt å lage et program som kan lage ord utifra en tilfeldig gitt kombinasjon av bokstaver - slik at hvis strengen "gtars" blir gitt, vil ord som "art,rat,star,rats" osv. dukke opp.

 

Jeg har allerede laget en liten ordliste over ord, så det eneste som gjenstår er selve algoritmen - og det er her jeg sliter litt.

 

Jeg tenkte jeg skulle lage algoritmen på samme måte som jeg "bruteforcer" kodelåser, altså ved at du starter på 0000, og tester deg fremover.

 

Eksempel:

0000

0001

0002

0003

0004

0010

0011

[...]

Dere skjønner nok tegninga.

 

Ordene skal som sagt kunne lages utifra en tilfeldig gitt bokstavkombinasjon som ikke skal ha noen fast størrelse. Det er her hjernen min sier stopp, for jeg trenger vel et ukjent antall løkker for å få dette til - alt avhengig av hvor lang denne tekststrengen er?

 

Dere må gjerne korrigere meg hvis jeg er helt på bærtur.. Har ikke våknet ordentlig enda:)

 

Og forresten, det er ikke noen skoleoppgave - men et forsøk på hacke et spill som går ut på å lage ord utifra en tilfeldig gitt strengkombinasjon

Endret 11. januar 2008 av v3g4rd

[Gjest Slettet+1374861]

Ett par ting slår meg vertfall når jeg leser dette. Det første som falt meg inn var å finne anagram. Anagram er da ord som inneholder samme bokstaver men i annen rekkefølge (kan også ha mellomrom).

Eksempel: "Britney Spears" og "Presbyterians"

 

Typisk i java vil da være noe ala dette:

	public static boolean erAnagram(String ord1, String ord2)
{
	ord1 = ord1.toLowerCase();
	ord1 = ord1.replaceAll(" ", "");

	ord2 = ord2.toLowerCase();
	ord2 = ord2.replaceAll(" ", "");

	char[] ord1rekke = ord1.toCharArray();
	char[] ord2rekke = ord2.toCharArray();

	Arrays.sort(ord1rekke);
	Arrays.sort(ord2rekke);

	if(new String(ord1rekke).equals(new String(ord2rekke)))
		return true;
	else
		return false;
}

 

Sånn i utgangspunktet muligens litt rart fordi poenget ditt var vel å finne det uavhengig av lengde iforhold til utgangs-strengen. Men det faller meg inn at via anagrammer kan du gå vekk fra å sjekke alle permutasjoner, og heller benytte kombinasjoner, som bør minke antall søk, men spørsmålet er vel om metoden som må kjøres for å avgjøre om de er anagram da også må effektiviseres.

 

Generellt her vil jeg vel slå fast at ettersom ordbokstørrelsen øker vil du stadig få problem med at det nok må gjennomføres aaaalt for mange tester for å få dette til å gå kjapt nok. Nå vet jeg riktignok ikke om du har noen tidsbegrensning på dette spillet, men hvis mengdene her blir store vil søketiden bli dramatisk høy. både antall permutasjoner og kombinasjoner vokser kjapt med mengden.

 

Tar forbehold om dårlig tenking og lite effektiv kode i dette innlegget

[Mr.Garibaldi]

Ser ett par forskjellige måter du kan gjøre dette på..

Enkleste blir vel noe som dette:

Hvis du ikke kan bruke samme bokstav flere ganger bruker du en lenket liste, kan de repeteres bruker du en array.

int ordLengde = tilfeldig tall < streng lengde (< streng lengde bare nødvendig hvis du fjerner tegn)
for i < ordLengde {
int bokstav = tilfeldig tall
for j < bokstav {
	 løp gjennom liste/array til du finner den (hvis bokstav > liste/array, fortsett fra starten
	 legg bokstav til det nye ordet, evt. slett det fra listen
}
sjekk om ordet foreløpig er gyldig (finnes ett annet i ordlisten som innehar samme tegn)
	 hvis nei, avbryt og start på nytt
	 hvis ja, fortsett
}

[v3g4rd]

Da har jeg implementert sjekking av anagrammer, og kommet et lite steg videre

 

Jeg trenger nok litt mer tid på å finne ut hvordan resten av algoritmen blir.. Skulle noen være interessert - har jeg lagt ved kildekoden til programmet.

WordSpeller.zip

[LostOblivion]

Jeg gidder ikke sette meg inn i hvordan koden skal se ut, men her har du hvertfall en ordbok! (UTF-8)

ordbok.txt

Endret 31. desember 2007 av LostOblivion

[v3g4rd]

Da har jeg gjort en liten innsats, og fått programmet ferdig! Dere som er interessert kan laste ned programmet og kildekoden her.

Endret 11. januar 2008 av v3g4rd

[Gjest Slettet+1374861]

Da har jeg gjort en liten innsats, og fått programmet ferdig! Dere som er interessert kan laste ned programmet og kildekoden her.

 

sweet

ser pent ut det der. savner setCaretPosition(..) til bunnen av "console"-en da

[v3g4rd]

Jeg har utelatt den der med vilje fordi jeg trengte den ferdige ordlisten i alfabetisk rekkefølge kjappest mulig - og hvis den da autoscroller ned til bunnen, må jeg bla opp til start igjen selv

[Gjest Slettet+1374861]

hva mener du? ordene du får ut når du kjører en "check ..."?

funker forsåvidt greit hvis du kjører en "clear" før du gjør ting, men da forsvinner jo riktignok tidligere ting.

ble problematisk hvis du lot være å "clear"e.

[v3g4rd]

Okei, tror jeg misforstod hva setCaretPosition dreide seg om, men nå vet jeg det

Det hadde kanskje vært greit om jeg bygget inn en slik funksjon, men det får bli i en fremtidig versjon.