Programmeeruitdagingen topic

Moderators: jkien, Xilvo

Gebruikersavatar
Berichten: 6.905

Programmeeruitdagingen topic

Naar analogie met Het grote raadsel topic eenzelfde topic voor algoritmen gerelateerde raadsels.

Opmerkingen:
  • Het staat iedereen vrij een uitdaging te plaatsen op voorwaarde dat: de vorige uitdaging duidelijk opgelost is en de plaatser van de uitdaging zelf een oplossing heeft.
  • De uitdagingen nummeren maakt het overzichtelijker
  • De uitdaging moet onafhankelijk van de gebruikte programmeertaal opgelost kunnen worden in een haalbare tijd.
  • Oplossingen worden geplaatst tussen hide tags en eventueel waar nodig de broncode in code tags.
  • Indien jouw uitdaging gebaseerd is op een andere uitdaging is een bronvermelding verplicht.
Uitdaging 1: Star Wars

Volgende uitdaging is overgenomen van probleem B uit ACM-ICPC '94

Gegeven:

Door een fout in de code van een anti-raketten schild kan dit schild enkel raketten uitschakelen waarvoor geldt:

- de raket in kwestie is de eerste raket

of

- de inkomende raket vliegt op een lagere hoogte en is later gelanceerd dan de laatste uitgeschakelde raket.

Gevraagd: een efficiënt algoritme om op basis van een lijst van inkomende raketten (in volgorde van lanceren) met gegeven hoogte het maximaal aantal raketten te bepalen die uitgeschakeld kunnen worden.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Gebruikersavatar
Berichten: 3.963

Re: Programmeeruitdagingen topic

Oké, ik waag mijn kans.

Oplossing uitdaging 1:

Verborgen inhoud
Programmeertaal: VBA

Ik ga ervan uit dat de gegeven hoogten worden weergegeven op de eerste kolom van een Excel bestand.

Code: Selecteer alles

Option Explicit

Sub CATCHER()

Dim i As Integer, teller As Integer, laatst_uitgeschakelde As Integer

laatst_uitgeschakelde = Cells(1, 1)

teller = 1

 'eerste raket wordt onderschept

i = 1

Do While Cells(i, 1) <> ""

  'doorlopen van de lijst

If Cells(i, 1) < laatst_uitgeschakelde Then

teller = teller + 1

  'uitschakelen van de overige raketten

laatst_uitgeschakelde = Cells(i, 1)

End If

i = i + 1

Loop

Debug.Print teller

End Sub




Uitdaging 2: Levenswijzer


Volgende uitdaging is overgenomen uit een cursus informatica aan de UGent.

Gegeven:

Veronderstel dat de levensverwachting van een doorsnee persoon 70 jaar is, en dat die levensverwachting kan worden aangepast op basis van de volgende criteria:
  • Wat is je geslacht (M/V)? Bij vrouwen wordt vier jaar bijgeteld.
  • Ben je een roker (J/N)? Bij rokers wordt vijf jaar afgetrokken, en bij niet-rokers wordt vijfjaar bijgeteld.
  • Hoeveel uren per week doe je aan sport? Trek drie jaar af voor personen die nooit sporten en tel één jaar bij voor elk uur dat iemand wekelijks aan sport doet.
  • Hoeveel glazen alcohol drink je per week? Trek een half jaar af voor elk geconsumeerd glas alcohol boven de zeven (bij iemand die elf glazen alcohol per week drinkt worden dus twee jaren afgetrokken). Bij geheelonthouders wordt er twee jaar bijgeteld.
  • Eet je vaak fast-food (J/N)? Voor personen die niet vaak fast-food eten wordt er drie jaar bijgeteld.
Gevraagd: bepaal de levensverwachting van een mannelijke roker die slechts twee uur per week aan sport doet, tien glazen alcohol per week drinkt en vaak fast food eet.

Noot: bovenstaande levenswijzer is niet wetenschappelijk bewezen.
"Success is the ability to go from one failure to another with no loss of enthusiasm" - Winston Churchill

Gebruikersavatar
Berichten: 6.905

Re: Programmeeruitdagingen topic

Ik ben er niet 100% zeker van dat jouw oplossing een correcte is. Werkt deze voor de voorbeelden?

Indien Ja, wat krijg je voor de volgende lijst:

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

Mijn algoritme lost dit op in een fractie van een seconde en vindt een maximum van 8 raketten die onder de gestelde voorwaarde kunnen worden onderschept.

Ik stel voor dat we nog even door gaan op probleem 1.

Ik bedenk mij net: het hoeft toch niet de eerste raket te zijn die wordt onderschept? Ik denk dat ik de formulering in het Nederlands niet waterdicht heb gemaakt ;)
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Gebruikersavatar
Berichten: 6.905

Re: Programmeeruitdagingen topic

Gevoelsmatig kan de opgave vertaald worden als volgt:

Gegeven een rij A. Zoek een deelverzameling C van A zodat C0 > C1 > ...> Cn. C wordt geordend zodat de elementen die in A voor elkaar komen dit ook in C doen.

Alle deelverzamelingen genereren zou een complexiteit O(2m) geven met m het aantal elementen in A. Er is dus een elegantere aanpak!
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Gebruikersavatar
Berichten: 3.963

Re: Programmeeruitdagingen topic

Hmm... via jouw voorbeeld en mijn algoritme kom ik op 4 uit.

Even voor de duidelijkheid: en raket kan toch enkel onderschept worden als ze lager vliegt dan de vorige onderschepte raket. Terwijl de eerste raket altijd onderschept wordt. Of gaat het hier al de mist in?

Dan zou je toch krijgen 6684, 6049, 933 en 71

(De voorbeelden in de pdf had ik nog niet gezien, ik ga er eens naar kijken.)

EDIT:
Ik bedenk mij net: het hoeft toch niet de eerste raket te zijn die wordt onderschept? Ik denk dat ik de formulering in het Nederlands niet waterdicht heb gemaakt ;)
Waarom zou de eerste niet onderschept worden? Het is immers de eerste in de test...
"Success is the ability to go from one failure to another with no loss of enthusiasm" - Winston Churchill

Gebruikersavatar
Berichten: 6.905

Re: Programmeeruitdagingen topic

Je moet een maximaal aantal raketten onderscheppen

Stel: 10 15 14 9 3

Als je hier de eerst onderschept kom je op 3 maximum: 10, 9, 3.

Onderschep eerst de tweede en je hebt: 15, 14, 9 & 3.

Ik geef toe; op dat gebied kon de vraag beter gesteld worden.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Gebruikersavatar
Berichten: 3.963

Re: Programmeeruitdagingen topic

Ah zo, ik snap het!

Ik heb een paar wijziging aangebracht en kom nu aan 7 ;) , telt de jouwe toevallig niet 1'tje teveel?

Morgen misschien meer.
"Success is the ability to go from one failure to another with no loss of enthusiasm" - Winston Churchill

Berichten: 7.068

Re: Programmeeruitdagingen topic

Oplossing voor uitdaging 1:

Verborgen inhoud
Haskell:

Code: Selecteer alles

-- simple solution

solution1 = maximum $ map length (intercept rockets)

	where

		intercept [] = [[]]

		intercept (x:xs) = (map (x:) (intercept (filter (<x) xs))) ++ (intercept xs)



-- slightly more complex, but more efficient

solution2 = catch [] (reverse rockets)



catch ys [] = maximum $ map (snd) ys

catch ys (x:xs) | t == [] = catch ((x, 1):ys) xs   -- this height is lower than any behind it.

					   | otherwise = catch ((x, 1 + maximum t):ys) xs

	where

		t = map (snd) $ filter ((<x) . fst) 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]
tweede oplossing kan nog efficienter door waarden uit ys te gooien die niet zinnig zijn (misschien heb ik daar morgen nog zin in).

Berichten: 7.068

Re: Programmeeruitdagingen topic

Andere oplossing voor uitdaging 1:

Verborgen inhoud
Haskell, twee implementaties van hetzelfde algoritme:

Code: Selecteer alles

solution3 = length $ foldl insertReplace [] (reverse rockets)

where

insertReplace [] x = [x]	-- new height x is higher than everything behind it

insertReplace (y:ys) x | x <= y	= x : ys	 -- replace y with x

   | otherwise = y : insertReplace ys x

solution4 = length $ foldl insertReplace [] (reverse rockets)

where

insertReplace ys x = h ++ (x:(drop 1 t))

where

(h,t) = span (<x) ys
Misschien is het een idee om ook nog een extra grote lijst hoogtes te genereren. De huidige lijst is namelijk zo kort dat al mijn oplossingen (zelfs solution1 die geheel niet efficient is) meteen een antwoord geven.

P.S. en het antwoord is wel degelijk 8.

Gebruikersavatar
Berichten: 3.963

Re: Programmeeruitdagingen topic

Ondertussen heb ik de fout in mijn redenering gevonden.

Als je bijv. 10, 15, 1, 14, 9 & 3 hebt wordt het maximum 15, 14, 9 & 3. Je ben dus niet verplicht om na de eerste onderschepte raket ook de volgende lager vliegende raket te onderscheppen. Dit was nog niet helemaal tot me doorgedrongen.

Op die manier sluit ik me aan bij de antwoorden van EvilBro en krijg je inderdaad 8!
"Success is the ability to go from one failure to another with no loss of enthusiasm" - Winston Churchill

Gebruikersavatar
Berichten: 6.905

Re: Programmeeruitdagingen topic

Ter volledigheid nog een oplossing in python:

Verborgen inhoud
Als startwaarde voor elke oplossing wordt genomen dat elke raket de eerste kan zijn. Voor elke oplossing worden dan de volgende mogelijke oplossingen toegevoegd. Deze stap wordt herhaald tot er geen extra meer gevonden zijn. Om dit proces sneller te doen lopen worden op het einde van elke iteratie de oplossingen verwijderd die nooit nog maximaal gaan kunnen zijn. (vb. zelfde eind positie maar minder raketten)

Code: Selecteer alles

seq=[389,207,155,300,299,170,158,65]

seq=[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]

solutions=[[i] for i in range(len(seq))]

next=True

while next:

next=False

newsolutions=[]

for solution in solutions:

foundnext=False

for j in range(solution[-1],len(seq)):

if seq[j]<seq[solution[-1]]:

newsolution=solution[:]

newsolution.append(j)

newsolutions.append(newsolution)

foundnext=True

next=True

if not foundnext:

newsolutions.append(solution)

solutions=newsolutions[:]

#te korte oplossingen deleten:

# bv. als [1,3,4] en [1,4] mogelijk zijn dan enkel de eerste behouden

i=0

while i<len(solutions):

j=i+1

while j<len(solutions):

#noot: indien len(solutions[i])>=len(solutions[j]) is het algoritme veel trager

#oplossing: per positie de beste mogelijkheden bijhouden en achteraf terug samenstellen!

if solutions[i][-1]==solutions[j][-1] and len(solutions[i])>=len(solutions[j]):

del solutions[j]

else:

j+=1

i+=1

#bepalen maximum

m=max([len(i) for i in solutions])

for i in solutions:

if len(i)==m:

print i, "Aantal: ", m

break


@Evilbro: leuke oplossingen in Haskell !
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Gebruikersavatar
Berichten: 6.905

Re: Programmeeruitdagingen topic

Ik denk dat mijn algoritme een complexiteit O(n³) (met n het aantal raketten). Dat is dus uiteraard stukken beter dan O(2n) bij het domweg nagaan van alle mogelijkheden.

PS: wie verzint een oplossing met backtracking voor de eerste uitdaging?
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Gebruikersavatar
Berichten: 5.679

Re: Programmeeruitdagingen topic

Mijn poging in php:
Verborgen inhoud
[pre]function MaxRockets( $rockets, $index=0, $lastHeight=-1 )

{

for ($n=count($rockets);;$index++)

{

if ($index>=$n) return 0;

if ($lastHeight<0 || $rockets[$index]<$lastHeight) break;

}

return max( MaxRockets($rockets,$index+1,$lastHeight), 1+MaxRockets($rockets,$index+1,$rockets[$index]) );

}[/pre]


Test:
Verborgen inhoud
[pre]$r = array( 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);

print( MaxRockets($r) ); // resultaat: 8[/pre]


Maar in het worst case scenario is dit O(2n) dus qua efficiency is deze niet optimaal (al is hij met bovengenoemde test van 40 stuks in een fractie van een seconde klaar).
In theory, there's no difference between theory and practice. In practice, there is.

Gebruikersavatar
Berichten: 6.905

Re: Programmeeruitdagingen topic

Leuk, een recursieve oplossing!

Mooi zo en blijkbaar ook redelijk efficiënt.

Ik ga morgen eens kijken naar uitdaging 2.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Gebruikersavatar
Berichten: 5.679

Re: Programmeeruitdagingen topic

De Haskell oplossingen van EvilBro (ik moet ook eens leren functioneel programmeren...) zijn uiteraard ook recursief.

Uitdaging 2 heeft overigens weinig met programmeren te maken, het is meer een invuloefening (iets interessanter zou een vraag zijn geweest als "hoeveel verschillende soorten personen hebben een levensverwachting van 79 jaar", maar dan nog is het meer een diophantische vergelijking dan echt een programmeerprobleem).
In theory, there's no difference between theory and practice. In practice, there is.

Reageer