Springen naar inhoud

Programmeeruitdagingen topic


  • Log in om te kunnen reageren

#1

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 25 februari 2011 - 09:02

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.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Kravitz

    Kravitz


  • >1k berichten
  • 4042 berichten
  • Moderator

Geplaatst op 25 februari 2011 - 15:53

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.

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

#3

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 25 februari 2011 - 18:58

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.

#4

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 25 februari 2011 - 19:08

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.

#5

Kravitz

    Kravitz


  • >1k berichten
  • 4042 berichten
  • Moderator

Geplaatst op 25 februari 2011 - 19:18

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

#6

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 25 februari 2011 - 20:00

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.

#7

Kravitz

    Kravitz


  • >1k berichten
  • 4042 berichten
  • Moderator

Geplaatst op 25 februari 2011 - 22:57

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

#8

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 26 februari 2011 - 00:30

Oplossing voor uitdaging 1:
Verborgen inhoud
Haskell:
-- 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).

#9

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 26 februari 2011 - 09:56

Andere oplossing voor uitdaging 1:
Verborgen inhoud
Haskell, twee implementaties van hetzelfde algoritme:
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.

Veranderd door EvilBro, 26 februari 2011 - 09:57


#10

Kravitz

    Kravitz


  • >1k berichten
  • 4042 berichten
  • Moderator

Geplaatst op 26 februari 2011 - 11:52

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

#11

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 27 februari 2011 - 09:21

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)

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.

#12

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 27 februari 2011 - 10:56

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.

#13

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 27 februari 2011 - 19:06

Mijn poging in php:
Verborgen inhoud
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]) );
}


Test:
Verborgen inhoud
$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


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.

#14

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 27 februari 2011 - 21:12

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.

#15

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 27 februari 2011 - 21:29

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures