Forum Mjukvara Programmering och digitalt skapande Tråd Inlägg

Stafettlek för programmerare

1 2
Skriv svar
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av BobbyFromDallas
Ok. Nu får du ursäkta mig om jag är ute och cyklar men jag tror att du har missförstått uppgiften.

Alfapet fungerar så här, man har ett rack med bokstäver som man utifrån försöker bygga ord på ett bräde. För att förenkla skippade jag brädan och fokuserade på huvuduppgiften, matcha olika ord med hjälp av X bokstäver.

Nu inser jag att vilket otroligt dåligt exempel jag valde när jag presenterade uppgiften, men så här var det tänkt i alla fall.

Om man har bokstäverna |s|a|v|e|d| så kan man matcha mot följande "ord" as/vase/save/saved/ etc...

Man behöver alltså inte använda alla bokstäver.

Det här verkar inte alls vara min dag.

(Som tur är så kräver sättet du löst uppgiften bara ett par mindre modikationer för att fungera korrekt.)

Det blev lite svårare då. Trevligt.

Visa signatur

Sverige är ett så litet land att det bara får plats en åsikt i taget där.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Ett program som tar bokstäverna man har som input o svarar vilka ord som kan skapas (skrivet i Haskell):

import List
import System
main = do (letters:[]) <- getArgs
	  file <- readFile "wordlist.txt"
	  let wordList = map (head.words) $ lines file
	      in
	      mapM_ putStrLn $ filter (scrabble letters) $ wordList

scrabble letters word = word \\ letters == []

Lär inte vara den snabbaste, men kort iaf

Senast redigerat
Redigera
Citera flera Citera
Permalänk
Medlem
●

Nu tror jag det funkar i alla fall.
källkod: http://home.student.uu.se/d/daki0267/test/scrabble.bas
program: http://home.student.uu.se/d/daki0267/test/scrabble.rar

tar ungefär 6s i uppstart
och 9s för 7 bokstäver (har inte stöd för fler än 7 då man bara har 7st i scrabble?)
färre bokstäver går betydligt fortare.

Visa signatur

Sverige är ett så litet land att det bara får plats en åsikt i taget där.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Respekt grabbar.

Innan jag går och lägger mig tänkte jag ge ett tips som jag tror kan snabba upp sökningen något ifall man väljer att "sortera" strängen.

I min lösning på förra sidan finner man följande tabell som ordnat bokstäverna i alfabetet efter deras frekvens i vanlig text:

int order[26] = {'e','t','a','h','o','s','n','r','i','l','d','u','w',
		     'm','c','g','y','f','b','p','k','v','j','x','q','z'};

Här ser man tydligt att det kan vara lönt att lägga lite tid på precalculate momentet för att spara tid när man söker. Att sortera strängen efter alfabetets ordning gör t.ex att b/c/g hamnar före o/s/n/i trots att dessa bokstäver fullkomligt dominerar i språket.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Detta blir ju skit intressant. Skit bra Bobby

Visa signatur

Samsung TFT 22" 2233RZ Svart 120HZ - 640GB Western Digital Black 64MB SATA III - Corsair 4GB (2x2048MB) 1333MHz XMS3-10600 - AMD Phenom2 X4 965 3,4GHz Black Edition - Gigabyte GeForce GTX 460 1GB OC - Fractal Design Define R3, Svart - Corsair TX 650W 80+ - Gigabyte GA-870A-UD3 - Cooler Master Hyper 212 Plus

Redigera
Citera flera Citera
Permalänk
Medlem
●

Jag har en lösning som antagligen kommer häpna er alla! Går en kurs i randomiserade algoritmer, och tänkte att "vad är bättre än att använda mina nyförvärvade kunskaper?".

Inom randomiserade algoritmer finns det två sorters algoritmer som jag känner till; Las Vegas och Monte Carlo. Las Vegas-algoritmer ger alltid ett rätt svar, men körningstiden varierar mellan olika gånger man kör algoritmen. Monte Carlo-algoritmer däremot garanterar inte att ge rätt svar (utan kan ge ett approximativt svar), men de går snabbare att köra.

Som kontrast till dessa två har jag hittat på min typ, som jag har döpt till Mölndals-algoritmer (efter min hemstad). Den kan ta hur lång tid på sig som helst, och ändå inte hitta rätt svar!

Jag presenterar koden (skriven i Python) här:

import random
def molndalScrabble(letters):
	f = open("wordlist.txt")
	words = [w[:-1] for w in f.readlines()]
	print words
	while words:
		letterlist = [l for="for" l="l" in="in" letters="letters"]
		random.shuffle(letterlist)
		letters = "".join(letterlist)
		for i in range(1,len(letters)+1):
			if letters[:i] in words:
				print letters[:i]
				words.remove(letters[:i])
				break
Senast redigerat
Visa signatur

Min hemsida: http://www.srekel.net
Pocket Task Force: http://ptf.srekel.net
Kaka e gott! http://kaka.srekel.net

Redigera
Citera flera Citera
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av BobbyFromDallas
Respekt grabbar.

Innan jag går och lägger mig tänkte jag ge ett tips som jag tror kan snabba upp sökningen något ifall man väljer att "sortera" strängen.

I min lösning på förra sidan finner man följande tabell som ordnat bokstäverna i alfabetet efter deras frekvens i vanlig text:

int order[26] = {'e','t','a','h','o','s','n','r','i','l','d','u','w',
		     'm','c','g','y','f','b','p','k','v','j','x','q','z'};

Här ser man tydligt att det kan vara lönt att lägga lite tid på precalculate momentet för att spara tid när man söker. Att sortera strängen efter alfabetets ordning gör t.ex att b/c/g hamnar före o/s/n/i trots att dessa bokstäver fullkomligt dominerar i språket.

Nu har jag provat att implementera nån modifiering av din primtalsverision, så nu är den lite snabbare för mig.

tar ungefär 1s i uppstart första gången, sedan typ ingen tid
och sen typ ingen tid alls för en sökning.
Nackdelen är att ca 1500 ord inte kommer med pga overflow gällande 32bitars. I scrabble får man väl olika poäng för olika bokstäver också och dom orden som försvinner är ju svåra ord på 6 till 7 bokstäver som innehåller ovanliga bokstäver så det är ju inte bra att dom försvinner.
Kanske går att fixa om man väljer tabellen för ordningen av bokstäverna lite annorlunda.

källkod: http://home.student.uu.se/d/daki0267/test/scrabble.bas
program: http://home.student.uu.se/d/daki0267/test/scrabble.rar

Visa signatur

Sverige är ett så litet land att det bara får plats en åsikt i taget där.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Nice.

Angående overflow, jag skrev egentligen min kod i ett helt annat språk (som stödjer s.k bignums) så det var ett hinder jag inte alls tänkte på att förrän jag skrev om koden i C. Å andra sidan är det väldigt lätt att skriva en enkel bignum implementation eller använda 64 bitar tal.

Nu vill jag se lite konstiga lösningar.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av BobbyFromDallas
Nice.

Angående overflow, jag skrev egentligen min kod i ett helt annat språk (som stödjer s.k bignums) så det var ett hinder jag inte alls tänkte på att förrän jag skrev om koden i C. Å andra sidan är det väldigt lätt att skriva en enkel bignum implementation eller använda 64 bitar tal.

Nu vill jag se lite konstiga lösningar.

Hur gör man det i qb?

Visa signatur

Sverige är ett så litet land att det bara får plats en åsikt i taget där.

Redigera
Citera flera Citera
Permalänk
Medlem
●

BobbyFromDallas: Stödjer inte c99 long long som standard. Jag tror det och en long long är 64bitar eller större.

Visa signatur
Redigera
Citera flera Citera
Permalänk
Medlem
●

Daniel:

Det beror på hur utmanade/lätt du vill göra det för dig. Har du tillgång till Knuths böcker så rekomenderar jag att du kollar upp Volym 2 och slår upp "arbitrary precision arithmetic". Annars kan du kan du helt enkelt använda 2 st 32 bit "ints" och simulera en 64 bit "int" själv. Den sista och enklaste metoden är att du helt enkelt representerar talet som en sträng och implementerar skolboksreglerna för mul/div/sub/add. Det kan låta onödigt och inneffektivt men det är bra att han en "enkel" modell som man kan använda som referens. Återkommer med lite kod ifall jag får tid.

Lijat: Jupp

C99 headern <inttypes.h> (u)int8_t (u)int16_t (u)int32_t (u)int64_t

Redigera
Citera flera Citera
1 2
Skriv svar