Programmeeruitdagingen topic

[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.

[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

[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).

[EvilBro]

Ik wilde mijn oplossing posten, maar ik ben de code kwijt... Ik kon nog wel deze tussenversie vinden:

Verborgen inhoud

Wat 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

[jhnbk]

Ziet er zeer goed uit! Ik heb intussen ook geen tijd meer gehad. Nieuwe dan maar?

[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)\)

[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 inhoud

Mijn 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.

[EvilBro]

Oplossing uitdaging 8:

Verborgen inhoud

Uitdaging 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)

[Cycloon]

Oplossing uitdaging 8:

Verborgen inhoud

Uitdaging 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.

[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.

[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.

[EvilBro]

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.

[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).

[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?

[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).