Stafettlek för programmerare

Det blev lite svårare då. Trevligt.

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

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.

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

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'};

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

Hur gör man det i qb?

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