Pagina 1 van 4
Programmeeruitdagingen topic
Geplaatst: vr 25 feb 2011, 09:02
door jhnbk
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.
Re: Programmeeruitdagingen topic
Geplaatst: vr 25 feb 2011, 15:53
door Kravitz
Oké, ik waag mijn kans.
Oplossing uitdaging 1:
Verborgen inhoudProgrammeertaal: 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.
Re: Programmeeruitdagingen topic
Geplaatst: vr 25 feb 2011, 18:58
door jhnbk
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
Re: Programmeeruitdagingen topic
Geplaatst: vr 25 feb 2011, 19:08
door jhnbk
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!
Re: Programmeeruitdagingen topic
Geplaatst: vr 25 feb 2011, 19:18
door Kravitz
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...
Re: Programmeeruitdagingen topic
Geplaatst: vr 25 feb 2011, 20:00
door jhnbk
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.
Re: Programmeeruitdagingen topic
Geplaatst: vr 25 feb 2011, 22:57
door Kravitz
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.
Re: Programmeeruitdagingen topic
Geplaatst: za 26 feb 2011, 00:30
door EvilBro
Oplossing voor uitdaging 1:
Verborgen inhoudHaskell:
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).
Re: Programmeeruitdagingen topic
Geplaatst: za 26 feb 2011, 09:56
door EvilBro
Andere oplossing voor uitdaging 1:
Verborgen inhoudHaskell, 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.
Re: Programmeeruitdagingen topic
Geplaatst: za 26 feb 2011, 11:52
door Kravitz
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!
Re: Programmeeruitdagingen topic
Geplaatst: zo 27 feb 2011, 09:21
door jhnbk
Ter volledigheid nog een oplossing in python:
Verborgen inhoudAls 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 !
Re: Programmeeruitdagingen topic
Geplaatst: zo 27 feb 2011, 10:56
door jhnbk
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?
Re: Programmeeruitdagingen topic
Geplaatst: zo 27 feb 2011, 19:06
door Rogier
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(2
n) dus qua efficiency is deze niet optimaal (al is hij met bovengenoemde test van 40 stuks in een fractie van een seconde klaar).
Re: Programmeeruitdagingen topic
Geplaatst: zo 27 feb 2011, 21:12
door jhnbk
Leuk, een recursieve oplossing!
Mooi zo en blijkbaar ook redelijk efficiënt.
Ik ga morgen eens kijken naar uitdaging 2.
Re: Programmeeruitdagingen topic
Geplaatst: zo 27 feb 2011, 21:29
door Rogier
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).