Pagina 4 van 4
Re: Programmeeruitdagingen topic
Geplaatst: vr 18 mar 2011, 17:57
door jhnbk
Wat is traag in deze context?
Ik ga zo meteen eens timen.
Verder zie ik nog een probleem aan mijn probleemomschrijving. Ter verduidelijking: een arithmetic sequence kan uit meer dan 3 elementen bestaan, maar heeft er minstens 3. De arithmetic sequence [1,3,5,7] bevat bijvoorbeeld 4 elementen. De groep [1,3,5,7] levert dus als arithmetic sequences [1,3,5], [3,5,7] en [1,3,5,7].
Bedoel je dat daardoor mijn oplossing niet correct is? M.a.w. ik heb enkel de sequenties met exact 3 termen. Ik ga zo meteen de uitbreiding schrijven.
Re: Programmeeruitdagingen topic
Geplaatst: vr 18 mar 2011, 19:30
door jhnbk
Wat is traag in deze context?
1e code: 8 min
Ik heb ook een implementatie voor sequenties > 3. Deze gaat ellendig traag. Er moet iets beters zijn dan mijn aanpak.
PS: liefst nog even geen oplossing posten. Ik moet en zal het zelf vinden
Re: Programmeeruitdagingen topic
Geplaatst: za 19 mar 2011, 00:03
door EvilBro
Bedoel je dat daardoor mijn oplossing niet correct is?
Als ik enkel de sequenties tel met 3 elementen dan kom ik tot jouw antwoord. Het was echter mijn bedoeling om ook sequenties met meer elementen toe te staan (mits ze aan de voorwaarden voldoen).
1e code: 8 min
Dat is inderdaad wel traag. Mijn oplossing doet het een stuk sneller (~1 s).
Re: Programmeeruitdagingen topic
Geplaatst: zo 03 apr 2011, 09:50
door EvilBro
Ik wilde mijn oplossing posten, maar ik ben de code kwijt...
Ik kon nog wel deze tussenversie vinden:
Verborgen inhoudWat mist aan deze code is het stukje dat uit de groepeerde sequences van lengte 3 sequences maakt van een langere lengte. Misschien heb ik later nog zin om dit toe te voegen...
Wat ik doe:
1. Maak alle priemgetallen aan van de juiste lengte.
2. Groepeer alle anagrammen door ze in een hash table te stoppen (ik doe het met een Map, maar dat is ongeveer hetzelfde).
3. Per groepje genereer je alle sequences van lengte 3.
4. Groepeer de sequences die eventueel aan elkaar te plakken zijn.
5. {ontbrekende stap} genereer alle langere sequences voor die groepen die uit meer dan 1 sequence bestaan.
Code: Selecteer alles
import Primes
import Data.List
import qualified Data.Map as Map
wsf006 = 1 + (sum $ map length $ groupByHash allPossibilities)
allPossibilities = concatMap generateSeqs $
filter ((>2) . length) $
groupAnagrams fiveDigitPrimes
fiveDigitPrimes = takeWhile (<100000) $ dropWhile (<10000) primes
groupAnagrams xs = ga xs Map.empty
where
ga [] m = map (sort . snd) (Map.toList m)
ga (x:xs) m = case Map.lookup hashedX m of
Nothing -> ga xs (Map.insert hashedX [x] m)
Just y -> ga xs (Map.insert hashedX (x:y) m)
where
hashedX = sort $ show x
generateSeqs xs = filter isArithSeq [[a,b,c] | a <- xs, b <- dropWhile (<=a) xs, c <- dropWhile (<=b) xs]
where
isArithSeq [a,b,c] = c-b == b-a
seqHash [a,b,c] = (offset, step)
where
offset = a `mod` step
step = b-a
groupByHash [] = []
groupByHash (x:xs) = (x:a) : groupByHash b
where
(a,b) = partition (\k -> seqHash k == seqHash x) xs
Re: Programmeeruitdagingen topic
Geplaatst: zo 03 apr 2011, 20:21
door jhnbk
Ziet er zeer goed uit! Ik heb intussen ook geen tijd meer gehad. Nieuwe dan maar?
Re: Programmeeruitdagingen topic
Geplaatst: di 05 apr 2011, 00:46
door WG-
2 uitdagingen van een vak dat ik volg. Dit waren 'ster' opdrachten voor de mensen van het honors programma.
1. Suppose you are given an array
\(A[1\ldots n]\)
of
\(n\)
distinct integers which consists of a decreasing sequence followed by an increasing sequence. That is, there is an index
\(k \in \{2, 3, \ldots , n - 1\}\)
such that
\(A[i] > A[i + 1]\)
for all
\(1 \leq i \leq k\)
and
\(A[i] < A[i + 1]\)
for all
\(k \leq i \leq n - 1\)
.
\(A[k]\)
is the minimum element. Give an algorithm to compute
\(A[k]\)
in
\(O(\lg n)\)
time.
2. Suppose your are given a convex polygon
\(P\)
, that is, a simple polygon where all internal angles are less than 180 degrees (see figure). The vertices of
\(P\)
are given in an array
\(V[1\ldots n]\)
in counterclockwise order. Each vertex is described by a pair of coordinates
\((x, y)\)
, you can assume that all
\(x\)
- and all
\(y\)
-coordinates are distinct. The leftmost vertex is stored in
\(V[1]\)
. Describe an algorithm that finds the top-most and the right-most vertex in
\(O(\lg n)\)
time.
Figuur: [attachment=7708:Screenshot_1.png]
ps.
\(\lg(x) = \log_2(x)\)
Re: Programmeeruitdagingen topic
Geplaatst: di 05 apr 2011, 22:53
door EvilBro
Laten we deze dan maar uitdaging 7 noemen:
1. Suppose you are given an array
\(A[1\ldots n]\)
of
\(n\)
distinct integers which consists of a decreasing sequence followed by an increasing sequence. That is, there is an index
\(k \in \{2, 3, \ldots , n - 1\}\)
such that
\(A[i] > A[i + 1]\)
for all
\(1 \leq i \leq k\)
and
\(A[i] < A[i + 1]\)
for all
\(k \leq i \leq n - 1\)
.
\(A[k]\)
is the minimum element. Give an algorithm to compute
\(A[k]\)
in
\(O(\lg n)\)
time.
en deze dan uitdaging 8:
2. Suppose your are given a convex polygon
\(P\)
, that is, a simple polygon where all internal angles are less than 180 degrees (see figure). The vertices of
\(P\)
are given in an array
\(V[1\ldots n]\)
in counterclockwise order. Each vertex is described by a pair of coordinates
\((x, y)\)
, you can assume that all
\(x\)
- and all
\(y\)
-coordinates are distinct. The leftmost vertex is stored in
\(V[1]\)
. Describe an algorithm that finds the top-most and the right-most vertex in
\(O(\lg n)\)
time.
en dan mijn oplossing voor uitdaging 7.
Verborgen inhoudMijn algoritme: ik bekijk telkens een deelrij van l (voor links) tot r (voor rechts). Ik bepaal voor de deelrij het midden en dan bekijk ik het element in het midden en het getal daarop. Als het tweede getal groter is dan het eerste dan is het tweede getal en alle getallen die daarop volgen een deel van het stijgende gedeelte van het array. Het minimum zit dan dus in het eerste gedeelte van de deelrij (inclusief m). Als het tweede getal lager is dan het eerste dan zit het minimum in het tweede gedeelte (m+1 en verder). De volgende deelrij die je gaat bekijken is het eerste of het tweede gedeelte (afhankelijk van waar het minimum inzit). Dit doe je totdat je nog maar 1 getal overhebt.
Je halveert bij elke stap je array. Het algoritme is dus \(O(\lg n)\)
.
Code: Selecteer alles
import Data.Array
findMinFromList xs = findMin (listArray (1,length xs) xs) 1 (length xs)
findMin values l r | l == r
= values ! m
|(values ! m) < (values ! (m+1)) = findMin values l m
| otherwise
= findMin values (m+1) r
where
m = (l+r) `div` 2
Tweede functie is de daadwerkelijke functie. De eerste is er enkel om makkelijk een array te maken in Haskell.
Re: Programmeeruitdagingen topic
Geplaatst: wo 06 apr 2011, 09:12
door EvilBro
Oplossing uitdaging 8:
Verborgen inhoudUitdaging 8 is eigenlijk hetzelfde als uitdaging 7. In plaats van een minimum ben je nu op zoek naar een maximum. Dit doe je eerst op de x-coordinaten. Je vindt dan een punt. Tussen dat punt en het beginpunt (inclusief die twee punten) kun je hetzelfde truukje nog eens doen maar dan met de y-coordinaten.
Code: Selecteer alles
import Data.Array
makeArrayFromList xys = listArray (1,length xys) xys
findExtremes values = (values ! top, values ! right)
where
(a,b) = bounds values
right = findMaxIndexWith fst values b 0 (b-1)
top = findMaxIndexWith snd values b right b
findMaxIndexWith f values n l r
| l == r = i
| f (values ! i) > f (values ! ((i `mod` n) + 1)) = findMaxIndexWith f values n l m
| otherwise = findMaxIndexWith f values n (m+1) r
where
m = (l+r) `div` 2
i = 1 + (m `mod` n)
Re: Programmeeruitdagingen topic
Geplaatst: za 11 jun 2011, 21:46
door Cycloon
EvilBro schreef:Oplossing uitdaging 8:
Verborgen inhoudUitdaging 8 is eigenlijk hetzelfde als uitdaging 7. In plaats van een minimum ben je nu op zoek naar een maximum. Dit doe je eerst op de x-coordinaten. Je vindt dan een punt. Tussen dat punt en het beginpunt (inclusief die twee punten) kun je hetzelfde truukje nog eens doen maar dan met de y-coordinaten.
Code: Selecteer alles
import Data.Array
makeArrayFromList xys = listArray (1,length xys) xys
findExtremes values = (values ! top, values ! right)
where
(a,b) = bounds values
right = findMaxIndexWith fst values b 0 (b-1)
top = findMaxIndexWith snd values b right b
findMaxIndexWith f values n l r
| l == r = i
| f (values ! i) > f (values ! ((i `mod` n) + 1)) = findMaxIndexWith f values n l m
| otherwise = findMaxIndexWith f values n (m+1) r
where
m = (l+r) `div` 2
i = 1 + (m `mod` n)
Ik betwijfel of jouw oplossing uiteindelijk wel klopt. De punten zijn opgeslagen volgens stijgende draaihoek en niet volgens stijgende coördinaten. Dat is wel een verschil.
Re: Programmeeruitdagingen topic
Geplaatst: zo 12 jun 2011, 12:09
door EvilBro
Ik betwijfel of jouw oplossing uiteindelijk wel klopt. De punten zijn opgeslagen volgens stijgende draaihoek en niet volgens stijgende coördinaten. Dat is wel een verschil.
Het klopt dat dat een verschil is, maar dat is niet relevant voor de oplossing. Bekijk het plaatje bij de opgave. Zet nu de x-coordinaat uit tegen het vertex-nummer. Van 1 tot 4 neemt de x-coordinaat toe, van 4 tot 7 neemt ie af. Er is dus een maximum. Dit zal zo zijn voor alle convexe polygonen met unieke x-coordinaten.
Re: Programmeeruitdagingen topic
Geplaatst: zo 12 jun 2011, 15:58
door Cycloon
Het klopt dat dat een verschil is, maar dat is niet relevant voor de oplossing. Bekijk het plaatje bij de opgave. Zet nu de x-coordinaat uit tegen het vertex-nummer. Van 1 tot 4 neemt de x-coordinaat toe, van 4 tot 7 neemt ie af. Er is dus een maximum. Dit zal zo zijn voor alle convexe polygonen met unieke x-coordinaten.
Ja in dit geval klopt dit omdat als je halveert je net op de grens komt van stijgende -> dalende punten. Maar wat als je iets hebt als dit:
3 6 8 7 6 5 4 3 (alle x-coördinaten van de punten volgens stijgende draaihoek).
Als jij de tabel dus opdeelt in 2 ga je volgende delen gaan onderzoeken:
3 6 8 7
6 5 4 3
In het eerste deel heb je dus zowel stijgende als dalende punten.
Ik moet wel toegeven dat ik geen yota van die haskell expressies begrijp, maar afgaande op je uitleg ga je in deze situatie in de fout.
Re: Programmeeruitdagingen topic
Geplaatst: wo 15 jun 2011, 09:41
door EvilBro
Cycloon schreef:Ja in dit geval klopt dit omdat als je halveert je net op de grens komt van stijgende -> dalende punten. Maar wat als je iets hebt als dit:
3 6 8 7 6 5 4 3 (alle x-coördinaten van de punten volgens stijgende draaihoek).
Eerste stap: vergelijk 7 met 6 -> dalend, dus pak je het eerste deel: 3 6 8 7
Tweede stap: vergelijk 6 met 8 -> stijgend, dus pak je tweede deel: 8 7
Derde stap: vergelijk 8 met 7 -> dalend, dus pak eerste deel: 8
Klaar.
Ik zie het probleem niet, maar misschien snap ik je punt niet. De door jou opgegeven rij voldoet trouwens niet aan de voorwaarde dat alle waarden uniek moeten zijn. Dit is niet zo'n probleem zolang de niet-unieke waarden maar niet naast elkaar zitten.
Re: Programmeeruitdagingen topic
Geplaatst: wo 15 jun 2011, 18:26
door Cycloon
Het klopt inderdaad, mijn excuses. Ik had de opdracht verkeerd begrepen. Ik dacht dat men op zoek was naar de vertex die het dichts bij de rechterbovenhoek lag. Maar dat is een ander probleem dan de meeste rechtse vertex (die zo hoog mogelijk ligt, maar dat is een onnodige zaak omdat waarden toch uniek moeten zijn).
Re: Programmeeruitdagingen topic
Geplaatst: ma 14 nov 2016, 10:20
door EvilBro
Even een stapje terug: Per abuis bekeek ik laatst mijn oplossing bij de eerste uitdaging. Ik was niet geheel ontevreden met mijn oplossing van weleer, maar ik zag wel vrij snel in dat het mogelijk was om een oplossing te maken die 'beter' was (de rij rockets hoeft niet meer omgedraaid te worden).
Code: Selecteer alles
solution = foldl insertReplace [] rockets
where
insertReplace ys x = h ++ (x : (drop 1 t))
where
(h, t) = span (> x) ys
rockets = [6684, 8285, 6049, 933, 2383, 6443, 5208, 71, 2884, 3592, 4106, 166, 8214, 758, 5606, 6526, 5171, 1746, 7039, 1179, 7626, 3678, 9212, 8986, 8415, 4193, 5151, 6562, 7724, 1614, 6103, 4462, 8012, 923, 4654, 8494, 8842, 79, 9129, 1740]
Nu begon ik mij dingen af te vragen over de efficientie. Ik denk dat dit programma O(n^2) is, maar ik vermoed dat het O(log(n)) kan. Mijn vraag aan jullie is of jullie dat ook denken.
Even in woorden wat hier gebeurt:
Je hebt een rij van getallen die van hoog naar laag zijn gesorteerd en een nieuw getal. Dit nieuwe getal moet in de rij gezet worden. Als het nieuwe getal kleiner is dan elk getal in de rij dan wordt het nieuwe getal aan het einde van de rij gezet. Anders vervangt het het eerste getal in de rij waar het hoger dan is.
Mijn idee waarom dit O(log(n)) kan: Sla de getallen in de rij op in een of andere boomstructuur zodat je makkelijk dit getal kan vinden (bijvoorbeeld: linker tak altijd hoger dan huidige node, rechter lager, en dan een gebalanceerde boom). De hoogte van zo'n boom zou log(n) zijn, dus verwacht ik dat de efficientie dat ook ongeveer is. Mee eens?
Re: Programmeeruitdagingen topic
Geplaatst: di 15 nov 2016, 09:22
door EvilBro
Waar ik hierboven O(log(n)) zei, had ik waarschijnlijk O(n * log(n)) moeten zeggen (je moet de boom natuurlijk n keer door).