Opgelost Programmeeropgave

Hierbij twee oplossingen (C++ en Python 3), die beide werken.

Hierbij een oplossing in Java.

De programmeeropgave staat live op https://programmeren.hcc.nl/programmeeropgave.html

Bij de presentatie afgelopen zaterdag vroeg ik me af waarom de iteratieve versie 8679 combinaties moest testen tegenover 1210 in de recursieve versie. Naar mijn gevoel zou je iteratief ook aan zo'n 1200 pogingen genoeg moeten hebben. Ik kon het niet van me afzetten en heb zonder naar de gisteren geplaatste oplossingen te kijken toch ook maar iets in elkaar gezet. In Lua, lekker primitief, maar net iets minder primitief dan C.

In eerste instantie heeft mijn uitwerking veel weg van de gegeven iteratieve C-oplossing. Van groot naar klein werken en vooruitblikken of er verder nog wat te halen valt. Onderweg de deelnemercombinatie bijhouden in een of andere vorm van array. Het grote verschil is dat mijn versie een rollback-mechanisme bevat dat heel wat iteraties voorkomt. Ik sluit niet uit dat dit mechanisme nòg intelligenter kan, maar een paar betrekkelijk simpele regels maken het al behoorlijk effectief. Verdere optimalisaties, als die al mogelijk zijn, zouden het programma onbegrijpelijk maken, vrees ik. Het is nu al twee keer zo groot als de C-versie. Voor wie het bijgesloten script niet zelf wil draaien, kan ik op de volgende bijeenkomst wel een korte demonstratie geven.

Hier alvast de cijfers: 380 coalities na 756 pogingen. Als ik de maximumeis van hooguit 6 partijen laat vallen, worden er 2430 coalities gevonden na 5303 pogingen. Niet slecht toch.

Mijn excuses. In de oorspronkelijke code staan een paar regels die ik heb geschrapt uit het artikel en die het aantal geteste combinaties voorstellen (terwijl dat aantal in de tekst wel genoemd wordt). Ik ken geen Lua, wat het lezen moeilijk maakt.

De code van msmsa lijkt correct te werken en de indruk is dat ze ook goed gebruikt maakt van de mogelijkheden om zoektijd te besparen. 2 * 380 = 760, dus dan is 756 pogingen uitstekend. Hij heeft een stuk meer regels code nodig dan ik en binnen de grote loop staan nog een paar for-loops, zodat ik moet concluderen dat voor het testen van 1 combinatie meer dan 1 stap gebruikt wordt, dus dat mijn versies per combinatie minder werk verrichten.

Mijn recursieve algoritme stelt de geteste coalitie voor door middel van een array waarvan maximaal 6 elementen gebruikt worden, terwijl mijn iteratieve versie een array maakt van de 17 partijen waarvan de elementen 0 of 1 zijn (wel of niet lid van coalitie), terwijl msmsa daar een tussenvorm voor gebruikt met een vector die dynamisch groeit of krimpt met 0/1. (dat soort dynamische arrays kennen de meeste programmeertalen niet).

Conclusie: niet zeker of dit beter is dan mijn oplossing.

Of mijn oplossing qua aantal machine-instructies beter is, valt inderdaad te betwijfelen. Ik heb niet geprobeerd dat na te trekken. Wel had ik aanvankelijk gepoogd tussenstanden (zeteltotaal en lijst van partijen) in een stack op te slaan, zodat de zetels en partijnamen niet steeds opnieuw vanuit niets hoefden worden gecumuleerd. Dat werd me echter te ingewikkeld, en ook hier kun je weer de vraag bij stellen of de winst niet geheel teniet zou worden gedaan door gecompliceerde algoritmen voor de bepaling van het aantal pop-operaties (het bleek al doende in elk geval lastiger goed te krijgen dan ik had verwacht). Bovendien, zou ik er op die manier niet stiekem toch een recursieve oplossing van maken?

Ik heb vanochtend nog wel een kleine verbetering aangebracht. De controle op nDeelnemers > maxCoalitie aan het begin van de iteratie heb ik vervangen door nDeelnemers >= maxCoalitie aan het eind van de iteratie. Dat reduceert het aantal iteraties voor maxima t/m 7 coalitiepartijen met 10 à 11% -- bij hogere maxima neemt de besparing geleidelijk af tot 0%. Het maximum van 6 partijen kost nu nog maar 672 pogingen. Dit is echte reductie, niet alleen maar administratieve.

Als je het Lua-script en het C-programma van alle franje ontdoet, ontlopen ze elkaar qua omvang niet veel meer. Lua: 88 regels; C: 74 regels. Mijn dynamische array is in C ook eenvoudig te realiseren: een array met een vaste grootte van 17 bytes plus een variabele die de daadwerkelijk gebruikte lengte aangeeft. Dat laatste lijkt op meer overhead in C, maar die overhead vindt in Lua onder water natuurlijk evengoed plaats en heeft dus ook daar zijn prijs (zij het niet ten koste van de programmeur)!

Mocht er een groot publiek geïnteresseerd zijn in een wedstrijd op performance, dan valt zoiets wel te organiseren. Voor nu laat ik het bij de lichtelijk verbeterde versie van het Lua-script, waarin ook de extra rapportage nog een pietsje grondiger is opgepoetst.

Ik ga morgen nog eens naar uw laatste versie kijken.

Mijn programma's tellen 'stappen' op zo'n manier dat er zes stappen nodig zijn voor een coalitie van 6 partijen.

Voor vandaag heb ik eens de grootte van de output geteld in dergelijke stappen, dus telkens geteld hoeveel partijen er veranderen tussen twee opeenvolgende resultaten: dat geeft 492 stappen als minimale looptijd als elke stap 1 partij verandert.

Dingen in een stack opslaan? Dat is het voordeel van recursief programmeren dat je de stack er gratis bij krijgt.

Vanochtend heb ik nog wat extra tellers ingebouwd voor de geneste iteraties. Dit zijn de uitkomsten:

Aantal pogingen  = 672

Aantal coalities = 380



Aantal inventarisaties          = 1344

Aantal inventarisatie-iteraties = 15202

Aantal rollbacks                = 126

Aantal rollbackiteraties        = 797

Je ziet wel hoeveel werk het cumuleren van de partijgegevens is. Maar zoals je zegt, du moment je aan zelfbeheerde stacks gaat denken, kun je het maar beter meteen recursief aanpakken. Wel kan ik nog proberen het aantal inventarisaties in de buurt van 672 te krijgen door informatie aan de volgende poging door te geven.

Omdat jouw programma ook geneste loops bevat, wilde ik daar eveneens zulke extra tellers voor inbouwen. Ik kreeg echter geen executable die uitvoer produceert. Handicap is, dat de mintekens bij het kopiëren vanuit de PDF bij mij verloren gaan. Ik heb geprobeerd dat op het oog te herstellen, maar kennelijk toch iets niet goed gedaan.

Update 16:00 -- Er zijn maar 203 iteraties waarin het verder opbouwen van een coalitie daarna kan worden voortgezet (in andere gevallen moeten er eerst een of meer partijen uit de aangelegde groep worden verwijderd). Meer dan 203 inventarisaties vallen er dus met doorgifte van informatie niet uit te sparen. Een betere manier is het geheel overbodig maken van het inventariseren van de beginsituatie vlak vóór het toevoegen van een volgende partij. Daarmee wordt het aantal inventarisaties zonder meer gehalveerd:

Aantal pogingen  = 672

Aantal coalities = 380



Aantal inventarisaties          = 672

Aantal inventarisatie-iteraties = 7937

Aantal rollbacks                = 126

Aantal rollbackiteraties        = 797

Zie bijgesloten nieuwe scriptversie.

Hierbij dan mijn broncode in C zodat u die niet uit de PDF hoeft te kopieren.

Het is op zich goed, maar de functie inventariseer() zou ik weglaten omdat ze telkens een loop doorloopt; door die gegevens niet telkens opnieuw uit te rekenen is er tijd te winnen.

Dank je. Ik heb gezien dat het niet uitmaakt vanaf welke kant je itereert:

  for( i = PARTIES - 1; i >= 0; i--) 

//  for( i = 0; i < PARTIES; i++)

In beide gevallen krijg je uiteindelijk dezelfde uitkomsten:

Checked 8679 combinations

# coalitions       = 380

# print calls      = 380

# print iterations = 6460

Ook wordt in beide gevallen de eerste coalitie (D66, PVV, CDA, FvD, GL, CU) pas bij de 2.626-ste poging gevonden. De print-functie verzamelt alleen maar de namen van de deelnemende partijen. Het zeteltotaal en aantal deelnemers wordt op een slimmere manier bijgehouden.

De stand is nu 15.139 iteraties in C tegenover 9.406 in Lua. Daarmee is nog steeds niet bewezen dat mijn script beter is, want er zijn nu weliswaar iteraties geteld, maar geen machine-instructies.

Update 14:10 -- Wanneer ik de facultatieve rapportage over de mislukte pogingen opgeef, hoef ik de inventariseer-functie slechts 380 keer aan te spreken. Zetel- en deelnemergroei kan ik tijdens de hoofditeratie bijhouden, en beider afname in de rol_terug-functie. Dan loopt het script aanmerkelijk zuiniger:

Aantal pogingen  = 672

Aantal coalities = 380



Aantal inventarisaties          = 380

Aantal inventarisatie-iteraties = 4838

Aantal rollbacks                = 126

Aantal rollbackiteraties        = 797

Het totale aantal iteraties komt daarmee op 6.307. Het zuinige script is hier bijgesloten.