Programming Contest Nieuwe Stijl: Contest 3 *uitslagen!*

[Darkwings]

Ah, ik heb een heel leuk algoritmetje verzonnen wat ik hier nog niet heb langs zien komen

Duidelijk dat ik dat ga proberen dus

[Verwijderd]

Dido schreef op donderdag 31 mei 2007 @ 15:27:
Moet je het eens in het Engels proberen
http://www.google.nl/sear...&btnG=Google+zoeken&meta=

Als je "permutatie probleem" intikt, lukt het ook wel.

[mOrPhie]

Darkwings schreef op donderdag 31 mei 2007 @ 15:33:
Ah, ik heb een heel leuk algoritmetje verzonnen wat ik hier nog niet heb langs zien komen

Duidelijk dat ik dat ga proberen dus

Niet iedereen geeft zijn methodes prijs natuurlijk.

[H!GHGuY]

mijn vorige oplossing was naar een genetisch algo gebouwd (scrabble thing) en heeft qua snelheid niet de hoogste toppen gescheerd...

Het lijkt me idd echter weer een probleem wat je vergelijkbaar kan oplossen.

[Verwijderd]

H!GHGuY schreef op donderdag 31 mei 2007 @ 18:52:
mijn vorige oplossing was naar een genetisch algo gebouwd (scrabble thing) en heeft qua snelheid niet de hoogste toppen gescheerd...

Het lijkt me idd echter weer een probleem wat je vergelijkbaar kan oplossen.

Zo een algoritme staat en valt met de gebruikte methodes. Er zijn tig soorten en variaties, de kunst is de juiste eruit te pikken en indien nodig aan te passen aan je wensen.

[Malthus]

liquid_ice schreef op donderdag 31 mei 2007 @ 14:54:
Hoe zijn jullie er toe gekomen om dit probleem met een genetisch, Sim. Annealing, lineair STPP of nog een ander algoritme aan te vallen?

waar hebben jullie naar gekeken voor deze keus?

Afgelopen dinsdag ben ik ook begonnen aan m'n bijdrage. Het wordt een programma in C#, want ik probeer om nu wat C# te leren. En als oplossingsalgoritme ga ik (ook) een genetisch algoritme gebruiken. De keuze voor een genetisch algoritme is eigenlijk heel simpel: het lijkt me leuk om weer eens een genetisch algoritme te programmeren. Ik zocht dus eigenlijk niet het beste algoritme voor het probleem, maar een probleem bij m'n algoritme.

[Dukdalf]

jaa,

ik heb mijn algorithme klaar, en ook geimplementeerd. Ik weet nog niet zeker of de punten telling 100% accuraat is, maar het zal zeker dichtbij komen.

Mijn score is : 299

Op naar de 300!

[Marcks]

Tjonge, wat komt er weer een theoretisch geneuzel voorbij. 'Kijk mij eens even wikipedia en google te hebben afgestruind naar optimalisatiefeitjes en termen waarvan ik zelf de betekenis niet ken.' No offense jongens, maar ik ben het helemaal met mOrPhie eens. Iedereen kan googlen, dus gezond verstand erbij en bedenk zelf eens een gezellig algoritme.

[Pete]

Zo, na eerst een prototype te hebben gebouwd van mijn inzending eerst maar even een generator in elkaar gebakken. (ik zie trwns nu pas dat ik niet de eerste ben, hij werkt wel echt volgens de specs en je werkt met percentages ipv absolute getallen (itt sommige andere))

Hier te downloaden. Werkt met Java 5.0
Je moet eerst even de namenlijst.txt en properties.xml uit je jar halen en in je directory zetten. Ik kon niet zo snel vinden hoe je naar resources binnen je jar verwees.

Standaard staat ie ingesteld dat organisatie-mensen wel nietorganisatie-(non|)roomies mogen hebben. Ik lees in het document niet dat dit niet mag nl. Wel zijn organisatie partners beide organisatie. Deze instellingen kunnen gewijzigd worden (zie properties.xml).

Mocht je vragen hebben/fouten vinden, vraag het gerust. Mocht de organisatie mijn generator zelf willen gebruiken dan mag dat en mogen ze mij een DM'tje sturen zodat ik aan hun de source kan sturen en ze zelf kunnen of ik geen voordelenvoorphsmit heb ingebouwd.

[ Voor 6% gewijzigd door Pete op 31-05-2007 22:45 ]

[D2k]

Dreamer-1982 schreef op woensdag 30 mei 2007 @ 19:29:
[...]


Die kun je krijgen als bijv. de output niet bij de testset hoort of er erg rare zaken in de input staan. Ik moet die fout nog even netjes afvangen Maar als je hem krijgt is de boel iig niet in orde!

Dreamer: ik weet al wat het is

hij gaat niet goed om met mijn kamer4= bij lege kamers. Die output mag wel volgens de handleiding.
als ik dat weglaat rekent ie de score wel uit

[Verwijderd]

Marcks schreef op donderdag 31 mei 2007 @ 22:05:
Tjonge, wat komt er weer een theoretisch geneuzel voorbij. 'Kijk mij eens even wikipedia en google te hebben afgestruind naar optimalisatiefeitjes en termen waarvan ik zelf de betekenis niet ken.' No offense jongens, maar ik ben het helemaal met mOrPhie eens. Iedereen kan googlen, dus gezond verstand erbij en bedenk zelf eens een gezellig algoritme.

Sommige zaken worden ook in school aangeleerd of moet je het zelf maar studeren voor een bepaalde opdracht. Dan moet je die zaken wel kunnen begrijpen.
In de grote bedrijven worden zulke algoritmen ten volle uitgebuit voor zeer uitlopende problemen.
En google en wikipedia zijn echt niet de enige bron van informatie: boeken en magazines bestaan nog steeds hoor.

[bomberboy]

Marcks schreef op donderdag 31 mei 2007 @ 22:05:
Tjonge, wat komt er weer een theoretisch geneuzel voorbij. 'Kijk mij eens even wikipedia en google te hebben afgestruind naar optimalisatiefeitjes en termen waarvan ik zelf de betekenis niet ken.' No offense jongens, maar ik ben het helemaal met mOrPhie eens. Iedereen kan googlen, dus gezond verstand erbij en bedenk zelf eens een gezellig algoritme.

Het gooien met termen is geen doel op zich uiteraard, maar leerrijk kan het wel zijn.
De opgave is een variant van het inpak probleem (google op bin packing). Dat is een erg bekend en ook al vaak bestudeerd probleem waarvoor reeds heel wat optimalisatietechnieken ontworpen zijn. De ene al meer of minder direct toepasbaar op deze versie van het probleem.

Ik wil niemand voor het hoofd stoten, maar de kans dat iemand een oplossingsalgortime vindt dat (onder één of andere vorm) nog niet bestaat is relatief klein. Indien dit wel zo is, proficiat, en dan mag die persoon waarschijnlijk binnekort wel een aantal wiskunde-prijzen gaan ophalen.
Je kan echter wel erg origineel zijn in de combinatie van verschillende technieken, of varianten implementeren die het specifiek voor dit probleem erg goed zullen doen.

In ieder geval kan het gegooi met termen je naar interessante voorbeeldoplossingen en/of voorbeeldalgoritmen leiden die je kunnen helpen met je eigen oplossing, door inspiratie op te doen of bepaalde implementatietechnieken te gaan gebruiken. Voor zover je dat nog niet (al dan niet bewust) deed natuurlijk. Het kennen van die termen is net daarom belangrijk, opdat je zelf niet alles opnieuw hoeft te doen en/of gericht op zoek kan gaan naar relevante informatie.

[EdwinG]

* EdwinG heeft zijn eigen validator bijna af, en gaat deze vergelijken met andere resultaten.
Inlezen schiet al aardig op, al heb ik bijna het idee dat ik té veel dingen probeer af te vangen. (Staat wel leuk voor 'defensive code')

[Pete]

Trwns nog een fout ontdekt in wm zn validator
kijk maar eens naar output van 1de35d057054699475d69d6bd1c7b7b4c0b4f12bfd05548d20e65a88f5ac765d

Huisje 1 klopt niet helemaal (score van minder dan -1000 op 1 huisje)

[ Voor 10% gewijzigd door Pete op 31-05-2007 22:55 ]

[liquid_ice]

Ben het met bomberboy eens.
Termen gooien is geen doel, maar een goede discussie over verschillende theorieen is voor iedereen (die dat wil) erg leerzaam.

Leren is voor mij ook de reden dat ik mee doe aan deze contest.
Punten halen en hopelijk niet laatste worden is een leuke bij komstigheid, maar niet mijn doel.

[_wm_]

Marcks schreef op donderdag 31 mei 2007 @ 22:05:
Tjonge, wat komt er weer een theoretisch geneuzel voorbij. 'Kijk mij eens even wikipedia en google te hebben afgestruind naar optimalisatiefeitjes en termen waarvan ik zelf de betekenis niet ken.' No offense jongens, maar ik ben het helemaal met mOrPhie eens. Iedereen kan googlen, dus gezond verstand erbij en bedenk zelf eens een gezellig algoritme.

Hier kan ik ja en amen op zeggen
Als al die algoritmes al bestaan en het puur een kwestie zou zijn van eentje eruit pikken en implementeren (of evt die implementatie ook jatten, als je dan toch al met andermans ideeën bezig bent) in jouw favoriete taaltje is deze hele contest niks meer aan...
Gewoon lekker creatief zelf dingen bedenken, dát is gaaf en dat geeft ook als enige (vind ik althans) echt voldoening. Ik doe juist aan deze contest mee omdat er niks te winnen valt en mensen daarom niet de meest gekke dingen gaan doen om te winnen (lees: de meest gekke dingen jatten) maar gewoon heerlijk relaxed in hun kamertje iets tofs verzinnen en dat uitwerken. Dáár gaat het toch om??
Om het plezier? Ik vind het in ieder geval superleuk om zelf iets slims te bedenken om dit probleem op te lossen

Zit nu op 354 punten in minder dan 1 seconden op een niet al te snelle laptop

en daar ben ik stiekem wel een beetje trots op

[Marcks]

liquid_ice schreef op donderdag 31 mei 2007 @ 22:59:
Ben het met bomberboy eens.
Termen gooien is geen doel, maar een goede discussie over verschillende theorieen is voor iedereen (die dat wil) erg leerzaam.

Leren is voor mij ook de reden dat ik mee doe aan deze contest.
Punten halen en hopelijk niet laatste worden is een leuke bij komstigheid, maar niet mijn doel.

Ik heb niks tegen een goede discussie over verschillende theorieen, maar ga er dan ook daadwerkelijk dieper op in. Wat ik hier veelal langs zie komen is een horde losse termen, al dan niet vergezeld door een linkje. Leg dan ook even uit waarom je denkt dat een bepaald algoritme goed zal presteren.

Enfin, ik dwaal nu zelf ook al af. Ik zou me eigenlijk moeten concentreren op boven de 421 scoren op de officiële testset. Door mijn programma enkele uren door te laten ratelen, lukt dat waarschijnlijk wel, maar het is nu een beetje zoeken naar de nodige 'shortcuts'.

[_wm_]

liquid_ice schreef op donderdag 31 mei 2007 @ 22:59:
Ben het met bomberboy eens.
Termen gooien is geen doel, maar een goede discussie over verschillende theorieen is voor iedereen (die dat wil) erg leerzaam.

Leren is voor mij ook de reden dat ik mee doe aan deze contest.
Punten halen en hopelijk niet laatste worden is een leuke bij komstigheid, maar niet mijn doel.

@Liquid: En wat heb je tot nu toe geleerd van die opmerkingen over STPP en shizzle? Niet zo veel waarschijnlijk, helaas... Dan is die 'goeie discussie' waarschijnlijk toch niet zo'n goeie discussie als het lijkt... En dat ligt ergens aan, namelijk:

@STPP experts : Als je voor iedereen die er niks vanaf weet een interessant stukje uitleg kan geven over hoe STPP werkt en waarom dat voor dit probleem een goede methode is, ga je gang, daar leert iedereen van...
Maar als je het alleen maar over STPP enzo hebt óm te laten zien dat je er iets vanaf weet (of pretendeert te weten), daar heeft toch niemand wat aan? Diegenen die er zelf wat van af weten zien niks nieuws en diegenen die er niks van weten snappen van een losse term ook echt nog steeds niks.

Wat ik wil zeggen: voeg wat toe aan de discussie, en laat die grijze cellen ofwel werken om een algoritme in elkaar te schroeven (en nee, dan niet een oplossingsmethode kopiëren van hier of daar) ofwel om wat zinnigs/opbouwends/leerzaams zo neer te zetten dat mensen er wat aan hebben.
Dat geeft: a) voldoening en b) respect
En daar wordt iedereen gelukkig van

Weer genoeg geblaat voor vanavond, lekker naar bedje toe!

[ Voor 5% gewijzigd door _wm_ op 01-06-2007 01:06 ]

[m277755]

Ik heb maar eens besloten om weer code te gaan typen. Ik had ook graag meegedaan aan de eerder programmeercontests, maar ik ben nog niet vaak in de Devschuur geweest en heb ze daarom gemist Mijn programmeerervaring bestaat voornamelijk uit het in java programmeren van een spel (tic-tac-turn). Aan het einde van het project werd een competitie gehouden tussen de deelnemers, waar mijn AI het meest succesvol bleek. Nou waren mijn tegenstanders daar denk ik grotendeels minder ervaren programmeurs dan de mensen in dit subforum

Ik ben in ieder geval gisteravond vol goede moed begonnen en ik heb inmiddels iets in elkaar weten te zetten dan 299 punten haalt op de officiële testset (mijn programma denk dat het 316 is ). Hij heeft daar nog wel maarliefst 10 minuten voor nodig, dus ik heb nog wel wat werk te doen. Zeker gezien dit:

Zit nu op 354 punten in minder dan 1 seconden op een niet al te snelle laptop

Dat is wel iets waar je trots op mag zijn ja

[Dreamer-1982]

D2k schreef op donderdag 31 mei 2007 @ 22:20:
[...]


Dreamer: ik weet al wat het is

hij gaat niet goed om met mijn kamer4= bij lege kamers. Die output mag wel volgens de handleiding.
als ik dat weglaat rekent ie de score wel uit

Ok, heb ik weer wat om te checken, thnx voor de input!

[liquid_ice]

Ik heb gister avond net Visual Studio geinstalleerd, kan komende dagen gaan beginnen met wat te fabriceren.
Eerst ff inlezen en schrijven van de output file bakken.
Daarna een validator en dan de interne werking

Keb er zin in.

PS : Ik heb wel degelijk wat geleerd door de discussie, maar het mag zeker dieper en uitgebreider op de materie in (op een manier die de gemiddelde mens hier kan snappen).

[Creepy]

mOrPhie schreef op donderdag 31 mei 2007 @ 14:15:
Ja, het gooien met die wetenschap is leuk, maar ik zou het interessanter vinden als je het daadwerkelijk implementeert en straks na 16 juli op basis van die wetenschap nog wint ook. Ik vind resultaten veel interessanter dan een theoretische discussie van iets dat volgens zeggen heel lastig te implementeren valt.

* Creepy wacht met spanning op de entries die goed wetenschappelijk zijn onderbouwd en een fatsoenlijke score halen binnen een redelijke tijd

[ Voor 14% gewijzigd door Creepy op 01-06-2007 10:19 ]

[fujiwara]

Ik heb mijn eerste output. Maar met de online validator van_wm_ lukt het niet echt. Hij geeft oa aan dat ik nt. organisatie in mijn organisatie kamers heb. Maar ik vind het ni terug. (aangeven van de validator in welk huis zou al handig zijn )

 
md5 hash van set: f2097397218da09178b24a2c23d03800c4514d97a53c1ee50fa5b99475d37323.

fout: je hebt niet-organisatie geplaatst in een organisatiehuisje!
fout: je hebt niet-organisatie geplaatst in een organisatiehuisje!

Omdat er een foutmelding is geweest, zal de score van je output.ini niet worden opgeslagen!

Huisje_0: -720
Huisje_1: 5
Huisje_2: 0
Huisje_3: -2
Huisje_4: 0
Huisje_5: 0
Huisje_6: 1
Huisje_7: 0
Huisje_8: 0
Huisje_9: 0
Huisje_10: 0
Huisje_11: 0
Huisje_12: 0
Huisje_13: 0
Huisje_14: 0
Huisje_15: 0
Huisje_16: 0
Huisje_17: 0
Huisje_18: 0
------------------------------+
totaal aantal punten voor puur de huisjes: 4

nietgeplaatstpunten: -720
partnerpunten: 0
roomiepunten binnen de kamer: 0
roomiepunten binnen het huis: 4
voorkeurpunten: 0
vegetarischpunten: 0
------------------------------+
totaal aantal punten voor jouw inzending bij deze set: -716
hoogste aantal punten voor deze set tot nu toe: 421

Met als output.ini : (gewone testset)

[Huisje_0]
Huisje_0_room0=Terr, crisp
Huisje_0_room1=Arthur, Microkid
Huisje_0_room2=Roelant, Ropniko
Huisje_0_room3=wilhelmstroker, zomertje
[Huisje_1]
Huisje_1_room0=Daniel, curry684
Huisje_1_room1=Iria, Cookie
Huisje_1_room2=Yoeri, Inge Janse
Huisje_1_room3=Zoefff, dion_b
[Huisje_2]
Huisje_2_room0=Rukapul, Hahn
Huisje_2_room1=Xandrios, Drobanir
Huisje_2_room2=naftebakje, Michel
Huisje_2_room3=Kaj., Harm
[Huisje_3]
Huisje_3_room0=Koffie, Mick
Huisje_3_room1=Joror, Floppus
Huisje_3_room2=Creepy, whoami
Huisje_3_room3=Apen-nootjes, Emmeline
[Huisje_4]
Huisje_4_room0=P_de_B, Fisico
Huisje_4_room1=cybersteef, Wilke
Huisje_4_room2=Atlas, Sprite_tm
Huisje_4_room3=XangadiX, Wouke
[Huisje_5]
Huisje_5_room0=sanfranjake, rob_erwt
Huisje_5_room1=Margje, woltjer
Huisje_5_room2=xxfile, F_J_K
Huisje_5_room3=IlseIII, Longbeard
[Huisje_6]
Huisje_6_room0=Rataplan, Jimmy Pop
Huisje_6_room1=Rosette, Ralph Smeets
Huisje_6_room2=DSmarty, Spider.007
Huisje_6_room3=DeeD2k2, dreeke
[Huisje_7]
Huisje_7_room0=Orion84, Abbadon
Huisje_7_room1=YellowCube, Femme
Huisje_7_room2=blaataaps, haribold
Huisje_7_room3=Dido, zeef
[Huisje_8]
Huisje_8_room0=chem, Hielko
Huisje_8_room1=Dimitri R, Fuelke
Huisje_8_room2=Janette, Jasper
Huisje_8_room3=Andr, leon1e
[Huisje_9]
Huisje_9_room0=Pim., Martin Sturm
Huisje_9_room1=Opi, Crash
Huisje_9_room2=Sophia, Canaria
Huisje_9_room3=Oscar the Grouch, JHS
[Huisje_10]
Huisje_10_room0=RM-rf, aperture
Huisje_10_room1=polaris, Qwerty-273
Huisje_10_room2=KeX, SmartDoDo
Huisje_10_room3=pasta, Eggy
[Huisje_11]
Huisje_11_room0=Equator, alt-92
Huisje_11_room1=Stefke, Janoz
Huisje_11_room2=Confusion, Kees
Huisje_11_room3=Aikeleer, mOrPhie
[Huisje_12]
Huisje_12_room0=-NMe-, Wouter Tinus
Huisje_12_room1=Daedalus, voodooless
Huisje_12_room2=Ecteinascidin, elevator
Huisje_12_room3=Grrrrrene, JvS
[Huisje_13]
Huisje_13_room0=GeniusDex, Ghost
Huisje_13_room1=Superdeboer, Pollewob
Huisje_13_room2=LuNaTiC, W3ird_N3rd
Huisje_13_room3=Lustucru, Pascal Saul
[Huisje_14]
Huisje_14_room0=.oisyn, HlpDsK
Huisje_14_room1=dusty, Gwenneth
Huisje_14_room2=TinuX, BtM909
Huisje_14_room3=RobIII, Robin
[Huisje_15]
Huisje_15_room0=Turkish, moto-moi
Huisje_15_room1=Hans, Juultje
Huisje_15_room2=McVirusS
[Huisje_16]
Huisje_16_room0=dawuss, Steffie
[Huisje_17]
Huisje_17_room0=ACM, T.T.
Huisje_17_room1=JAVA-Doctor, botoo
Huisje_17_room2=Twynn, Jan Laros
Huisje_17_room3=p0m, Thandor
[Huisje_18]
Huisje_18_room0=Remy, BalusC
Huisje_18_room1=AcouSE, Kheldar
Huisje_18_room2=Renegade, Floris

[Marcks]

fujiwara schreef op vrijdag 01 juni 2007 @ 13:21:
Ik heb mijn eerste output. Maar met de online validator van_wm_ lukt het niet echt. Hij geeft oa aan dat ik nt. organisatie in mijn organisatie kamers heb. Maar ik vind het ni terug. (aangeven van de validator in welk huis zou al handig zijn )

Zelfde probleem hier. Hij gaf gisteren aan dat ik niet-organisatie met organisatie gemixt had. Ik heb weliswaar niet mijn hele output.ini gecontroleerd, maar bij elke wissel die ik uit wil voeren, wordt de nieuwe indeling gevalideerd en naar mijn weten is er niets mis met onderstaande code.

code:

Valideer = 1
FOR a = 1 TO Kamers%: FOR b = 1 TO 2
  ID = Bed(Huis, a, b)
  IF ID > 0 THEN
    Totaal = Totaal + 1
    IF Voorkeur$(ID) = "organisatie" THEN Org = Org + 1    
  END IF
NEXT b: NEXT a

IF Org > 0 AND Org < Totaal THEN Valideer = 0: GOTO Break02

_{Edit: probleem gevonden. Per ongeluk ergens deze functie aangeroepen met het argument kamernummer in plaats van huisnummer.}

[ Voor 7% gewijzigd door Marcks op 01-06-2007 13:45 ]

[_wm_]

Marcks schreef op vrijdag 01 juni 2007 @ 13:28:
[...]


Zelfde probleem hier. Hij gaf gisteren aan dat ik niet-organisatie met organisatie gemixt had. Ik heb weliswaar niet mijn hele output.ini gecontroleerd, maar bij elke wissel die ik uit wil voeren, wordt de nieuwe indeling gevalideerd en naar mijn weten is er niets mis met onderstaande code.

code:

Valideer = 1
FOR a = 1 TO Kamers%: FOR b = 1 TO 2
  ID = Bed(Huis, a, b)
  IF ID > 0 THEN
    Totaal = Totaal + 1
    IF Voorkeur$(ID) = "organisatie" THEN Org = Org + 1    
  END IF
NEXT b: NEXT a

IF Org > 0 AND Org < Totaal THEN Valideer = 0: GOTO Break02

Ik voer precies dezelfde check uit... Bij mij ging het alleen even mis met het berekenen van het Totaal, denk ik, omdat ie een lege naam of een spatie ook gewoon als naam telde.
Ik weet het niet precies, maar in ieder geval is het opgelost toen ik daar wat beter op controleerde
De validator geeft nu trouwens ook aan in welk huisje het is misgegaan...
EDIT: het ging niet mis met het totaal berekenen, maar het gaat gewoon fout in de set van fujiwara... Je gebtuikt een spatie na de komma. Een spatie is echter gewoon een geldig karakter, dus wordt bij de gebruikersnaam gerekend. ' Balusc' is geen organisatie, en dan wordt dus de foutmelding gegeven. 'Balusc' (zonder spatie) is wel organisatie, en dan gaat het gewoon goed...!

[ Voor 18% gewijzigd door _wm_ op 01-06-2007 13:53 ]

[fujiwara]

Dat lost het probleem idd op :-). Daar had ik niet snel opgekomen.
mm men score veschilt precies toch serieus met die van de validator een nagaan wat ik mis doe

[EdwinG]

_wm_ schreef op vrijdag 01 juni 2007 @ 13:45:
EDIT: het ging niet mis met het totaal berekenen, maar het gaat gewoon fout in de set van fujiwara... Je gebtuikt een spatie na de komma. Een spatie is echter gewoon een geldig karakter, dus wordt bij de gebruikersnaam gerekend. ' Balusc' is geen organisatie, en dan wordt dus de foutmelding gegeven. 'Balusc' (zonder spatie) is wel organisatie, en dan gaat het gewoon goed...!

In dat geval zou je moeten zeggen dat je een niet bestaand persoon hebt ingedeeld, in plaats van een niet-organisatielid.

Wat ik me alleen nog af vraag, als iemand een roomie dubbel op geeft (bijvoorbeeld op plaats 1, en op plaats 3), en deze wordt in dezelfde kamer ingedeeld, krijg je dan beide punten, of alleen de 5 van 'roomie 1 op zelfde kamer'?

Voor zover ik kan lezen is dat het enige verschil wat ik nog heb met de validator van _WM_

Toch niet dus:
1de35d057054699475d69d6bd1c7b7b4c0b4f12bfd05548d20e65a88f5ac765d
In 1 van de kamers is iemand ingedeeld met de naam 'geen', terwijl die niet bestaat. Mijn validator keurt het af, die van _WM_ geeft 2217 punten.

edit:
2e verschil gevonden

[ Voor 12% gewijzigd door EdwinG op 01-06-2007 15:15 ]

[Verwijderd]

EdwinG schreef op vrijdag 01 juni 2007 @ 14:34:
[...]

In dat geval zou je moeten zeggen dat je een niet bestaand persoon hebt ingedeeld, in plaats van een niet-organisatielid.

Wat ik me alleen nog af vraag, als iemand een roomie dubbel op geeft (bijvoorbeeld op plaats 1, en op plaats 3), en deze wordt in dezelfde kamer ingedeeld, krijg je dan beide punten, of alleen de 5 van 'roomie 1 op zelfde kamer'?

Voor zover ik kan lezen is dat het enige verschil wat ik nog heb met de validator van _WM_

Dat is aan jezelf, omdat het dan om ongeldige invoer gaat. In de officiele testset zou zoiets dus ook niet voor moeten komen.

[Pete]

phsmit schreef op donderdag 31 mei 2007 @ 22:55:
Trwns nog een fout ontdekt in wm zn validator
kijk maar eens naar output van 1de35d057054699475d69d6bd1c7b7b4c0b4f12bfd05548d20e65a88f5ac765d

Huisje 1 klopt niet helemaal (score van minder dan -1000 op 1 huisje)

[EdwinG]

Als we dan toch bezig zijn:
f2097397218da09178b24a2c23d03800905c83529c4e7787a3226e6da6671e52
meeting.ini is meer een output.ini

phsmit schreef op vrijdag 01 juni 2007 @ 15:33:
[...]

Hoe kun je de score per huisje zien? (of is dat alleen bij het uploaden?)

Trouwens, [arthur] komt 2x voor, de invoer is ook ongeldig.

[ Voor 50% gewijzigd door EdwinG op 01-06-2007 15:50 ]

[_wm_]

phsmit schreef op vrijdag 01 juni 2007 @ 15:33:
[...]

opgelost

[_wm_]

EdwinG schreef op vrijdag 01 juni 2007 @ 14:34:
[...]

In dat geval zou je moeten zeggen dat je een niet bestaand persoon hebt ingedeeld, in plaats van een niet-organisatielid.

Wat ik me alleen nog af vraag, als iemand een roomie dubbel op geeft (bijvoorbeeld op plaats 1, en op plaats 3), en deze wordt in dezelfde kamer ingedeeld, krijg je dan beide punten, of alleen de 5 van 'roomie 1 op zelfde kamer'?

Voor zover ik kan lezen is dat het enige verschil wat ik nog heb met de validator van _WM_

Toch niet dus:
1de35d057054699475d69d6bd1c7b7b4c0b4f12bfd05548d20e65a88f5ac765d
In 1 van de kamers is iemand ingedeeld met de naam 'geen', terwijl die niet bestaat. Mijn validator keurt het af, die van _WM_ geeft 2217 punten.

edit:
2e verschil gevonden

1. Hij bekijkt dan alleen de hoogste (niet)roomie, de dubbele wordt weggegooid...
2. als je iemand indeelt die niet bestaat, moet jij weten, je krijgt er alleen geen punten voor en het vult een plek waar je anders iemand anders had neergezet... Bij mij dus inderdaad geen foutmelding... Als je iemand indeelt die niet bestaat, moet je dat haast wel opzettelijk doen, dus daar doe ik maar geen controle op

[_wm_]

EdwinG schreef op vrijdag 01 juni 2007 @ 15:47:
Als we dan toch bezig zijn:
f2097397218da09178b24a2c23d03800905c83529c4e7787a3226e6da6671e52
meeting.ini is meer een output.ini
[...]

Hoe kun je de score per huisje zien? (of is dat alleen bij het uploaden?)

Trouwens, [arthur] komt 2x voor, de invoer is ook ongeldig.

1. meeting.ini is gewoon een meeting.ini ?
2. score per huisje inderdaad alleen als je uploadt...

[EdwinG]

_wm_ schreef op vrijdag 01 juni 2007 @ 16:06:
[...]

1. meeting.ini is gewoon een meeting.ini ?
2. score per huisje inderdaad alleen als je uploadt...

Deelnemers.ini bedoel ik, sorry.

[Verwijderd]

Hoe staat het met de snelheid van jullie programma's? Haal zelf in 5 minuten een score van 1955 op deze testset (90 invaliden, 90 organisatoren, 800 anderen, 100 huizen van 10 personen elk). Mijn score kan zeker hoger worden als ie langer mag stampen. Wat voor scores halen jullie op testsets van deze grote en binnen wat voor tijd?
Edit: na een halfuur rekenen 2081 punten. Slechts een verbetering van 126... daar moet zeker nog wat aan gebeuren.

[ Voor 12% gewijzigd door Verwijderd op 01-06-2007 23:26 ]

[Onbekend]

Ik heb nog 0,0 iets aan het plaatsen van deelnemers gedaan.....

Files inlezen en opslaan gaat perfect, en mijn scoreberekeningen geven eindelijk allemaal de zelfde resultaten als de validator van _WM_.

Nu ben ik er eindelijk klaar voor om personen bij elkaar te zetten.

[Malthus]

Zojuist heb ik m'n eerste output-bestanden door _wm_'s validator gehaald. Het slechte nieuws is dat ik zo rond de -1265 punten haal met de officiële testset (tot nu toe plaats ik alleen de organisatie en dan ook nog in willekeurige volgorde). Het goede nieuws is dat m'n eigen programma tot dezelfde score komt als _wm_'s validator. Het gaat dus langzaam maar zeker de goede kant op.

En natuurlijk wil ik _wm_ bedanken voor het beschikbaar stellen van zijn validator!

[liquid_ice]

De officiele test set, dat is die toch in de openingspost staat?
of is er ergens een geupdate geweest?

[Malthus]

liquid_ice schreef op zaterdag 02 juni 2007 @ 00:11:
De officiele test set, dat is die toch in de openingspost staat?
of is er ergens een geupdate geweest?

Dat is inderdaad de testset die ik bedoel. En ondertussen haal ik 11 punten met deze testset (volgens de validator van _wm_, mijn eigen programma komt helaas nog tot een andere score), dus het gaat de goede kant op.

[NMe]

liquid_ice schreef op zaterdag 02 juni 2007 @ 00:11:
De officiele test set, dat is die toch in de openingspost staat?
of is er ergens een geupdate geweest?

Als er een update is, dan wordt de startpost ook aangepast. De startpost is en blijft dus altijd up to date.

Bedenk overigens wel dat de testset wat anders is dan de uiteindelijke set die we tijdens de evaluatie gebruiken.

[liquid_ice]

waarschijnlijk is dit al gevraagd, maar kon het zo niet vinden.
De key's (dus aantalhuisjes, aantalinvalidenhuisjes, personenperhuis) blijven hetzelfde toch?
ook van de members.ini

Of moet ik er vanuit gaan dat deze ook kunnen veranderen?
behalve voor een robustheidstest (maar dan is een uitkomst niet mogelijk lijkt me), alleen een error, crash of wat dan ook.

[NMe]

Keys blijven zoals gespecificeerd. Dat kan ook niet anders, want als er ineens huizenaantal in plaats van aantalhuisjes staat, hoe wil je programma dan weten wat daarmee bedoeld wordt?

[liquid_ice]

just to be sure

[Apache]

woooha, k'hang ook nog eens in p&w rond en t'is meteen 5:42

K'heb een java implementatie gemaakt, wil makkelijk kunnen spelen met de algo's dus heb een interface gemaakt en dan kan ik gewoon snel switchen of nieuwe ideeën uitproberen.

K'heb nu een werkende, maar zeer onefficiente first come first serve implementatie

Java:

public class FirstComeFirstServe implements IMeetingDistributionAlgorithm {

    @Override
    public HuisManager solve(HuisManager huisManager, List<Member> members) {

        for (Member member : members) {
            
            bleh:
            for (Huis h : huisManager.getHuizen()) {
                if (h.plaatsVrij()){
                    h.inschrijvenInKamer(member, false);
                    break bleh;
                }
            }
            
        }
        
        
        return huisManager;
    }

}

Die lijst van members heeft alle references volledig in orde zodat ik alles kan checken wat nodig is.
Heb meteen al rekening gehouden met performance dus hoop dat dat wel goed zit. De huismanager is zich bewust van alle huizen, de voorkeuren per huis etc ...

Enkel nog proberen een efficient algo te schrijven maar denk dat ik maar eens eerst in m'n bed kruip

[_wm_]

Verwijderd schreef op vrijdag 01 juni 2007 @ 22:33:
Hoe staat het met de snelheid van jullie programma's? Haal zelf in 5 minuten een score van 1955 op deze testset (90 invaliden, 90 organisatoren, 800 anderen, 100 huizen van 10 personen elk). Mijn score kan zeker hoger worden als ie langer mag stampen. Wat voor scores halen jullie op testsets van deze grote en binnen wat voor tijd?
Edit: na een halfuur rekenen 2081 punten. Slechts een verbetering van 126... daar moet zeker nog wat aan gebeuren.

Ik zal zometeen eens even checken met mijn script... Het nadeel is dat ik het met PHP doe en tussendoor niet echt een statusupdate of iets dergelijks kan doen omdat zolang Apache heel hard bezig is, er geen output naar de browser wordt gestuurd. Ik kan dus niet zien hoelang m'n script al bezig is en hoever ie is... dat is wel iets vervelend... Als iemand weet hoe je dat op kan lossen (ob_flush() oid helpt volgens mij niks...) dan zou dat zeer welkom zijn!

heb net wel een efficiëntieverbetering van zo'n 20 keer gerealiseerd, dus dat is wel weer mooi

[Marcks]

Zit nu op 354 punten in minder dan 1 seconden op een niet al te snelle laptop
en daar ben ik stiekem wel een beetje trots op

Ja, jij hebt klagen. Ik moet al 12 seconden draaien voor een score van 300. Bovendien heeft elke programmeertaal of -omgeving zijn beperkingen. Zo moet ik voor de officiële testset een executable maken, omdat ik anders geheugen-issues krijg.

[ Voor 26% gewijzigd door Marcks op 02-06-2007 16:12 ]

[? ?]

Ik denk dat ik ook es ga meedoen
alhoewel ik de vorige opdracht leuker vond op 't eerste gezicht maar toen jammer genoeg geen tijd had
taal wordt VB.NET met VS Express 2005 en dan port ik 't wel naar andere taal als't daar vlugger zou zijn.

[_wm_]

Marcks schreef op zaterdag 02 juni 2007 @ 16:01:
[...]
Ja, jij hebt klagen. Ik moet al 12 seconden draaien voor een score van 300. Bovendien heeft elke programmeertaal of -omgeving zijn beperkingen. Zo moet ik voor de officiële testset een executable maken, omdat ik anders geheugen-issues krijg.

Ik heb ook geheugenproblemen bij wat grotere sets hoor...
met die testset van YeXo gebruikt ie 515Mb aan RAM... En is 5 minuten bezig... Heb dan wel 1986 punten, dus wel iets beter dan YeXo op dezelfde tijd , maar ik vind 515Mb aan ram nog steeds best wel behoorlijk veel eigenlijk... Een set van 1000 personen, dus ongeveer een halve Mb per persoon...! Voor feitelijk alleen maar het tijdelijk opslaan van wat kleine tekst... Moet ik nog maar eens proberen iets aan te doen!

[ Voor 10% gewijzigd door _wm_ op 02-06-2007 17:09 ]

[Marcks]

_wm_ schreef op zaterdag 02 juni 2007 @ 17:07:
[...]


Ik heb ook geheugenproblemen bij wat grotere sets hoor...
met die testset van YeXo gebruikt ie 515Mb aan RAM... En is 5 minuten bezig... Heb dan wel 1986 punten, dus wel iets beter dan YeXo op dezelfde tijd , maar ik vind 515Mb aan ram nog steeds best wel behoorlijk veel eigenlijk... Een set van 1000 personen, dus ongeveer een halve Mb per persoon...! Voor feitelijk alleen maar het tijdelijk opslaan van wat kleine tekst... Moet ik nog maar eens proberen iets aan te doen!

Zo, dat is inderdaad wel behoorlijk veel. Volgens mij gebruik ik slechts 4,9kB per bed.

[_wm_]

nou... 375 punten op de officiële testset na 1,6 seconde... leuk dat het snel is, maar wel 50 punten minder dan Dreamer-1982 nog steeds
Ik snap niet hoe iedereen zulke hoge scores heeft Ik ga het probleem nog maar eens kritisch analyseren denk ik...

Hoe werken die 'evoluerende' methoden eigenlijk? Want ik gebruik nu feitelijk gewoon een rechttoe-rechtaan methode...
Moet je dan gewoon steeds een aantal mensen wisselen, kijken of de nieuwe set hoger ligt, en dan vanuit die set weer een aantal mensen wisselen? Of?

[Marcks]

_wm_ schreef op zaterdag 02 juni 2007 @ 23:16:
Hoe werken die 'evoluerende' methoden eigenlijk? Want ik gebruik nu feitelijk gewoon een rechttoe-rechtaan methode...
Moet je dan gewoon steeds een aantal mensen wisselen, kijken of de nieuwe set hoger ligt, en dan vanuit die set weer een aantal mensen wisselen? Of?

Dat is in ieder geval grofweg de manier waarop ik het aanpak, maar volgens mij kun je dat niet echt 'evoluerend' noemen. De 'goede eigenschappen' worden namelijk niet bij elke set geërfd, want een grote verbetering in de score kan later tegen je gaan werken. Voorbeeldje, je hebt een maximum aan invalidenhuisjes van drie, waarvan twee gebruikt worden. Je plaatst één van de invaliden in een niet-invalidenhuisje, waardoor je score met 15 punten omhoog gaat. Ineens zit je op je maximum, en valt er tussen invaliden nauwelijks meer te schuiven.

[_wm_]

Marcks schreef op zaterdag 02 juni 2007 @ 23:27:
[...]


Dat is in ieder geval grofweg de manier waarop ik het aanpak, maar volgens mij kun je dat niet echt 'evoluerend' noemen. De 'goede eigenschappen' worden namelijk niet bij elke set geërfd, want een grote verbetering in de score kan later tegen je gaan werken. Voorbeeldje, je hebt een maximum aan invalidenhuisjes van drie, waarvan twee gebruikt worden. Je plaatst één van de invaliden in een niet-invalidenhuisje, waardoor je score met 15 punten omhoog gaat. Ineens zit je op je maximum, en valt er tussen invaliden nauwelijks meer te schuiven.

Ja precies, door een lokaal optima kan een nieuwe set goed lijken, maar dat in feite niet zijn omdat dat lokale optimum zo 'nauw' is dat je daarvandaan niet verder meer kan evolueren...
Ik zou het denk ik via een 'boom' doen...

je begint met een willekeurige indeling aan de 'stam' van de boom (níet een set die al hoge punten heeft, want dan begin je in feite al ver op een tak, en dan kan je minder goed uitwaaieren... (lijkt me?)).
Daarna verwissel je vanuit dat punt 5 keer 3 of 4 personen ofzo (misschien afhankelijk van hoe groot deelnemers.ini is) en kijkt wat de nieuwe score wordt. Als de score hoger of gelijk is, komt er een tak bij met de nieuwe indeling. Vanuit deze tak ga je weer hetzelfde doen. Dus 5 keer 3 of 4 personen wisselen. Mochten die allemaal geen hogere indeling opleveren, dan 'loop' je weer terug over de tak en kom je in dit geval bij je beginpunt uit. Daar ga je de andere 4 (de oorspronkelijke 5 min die ene die we al gehad hadden) nieuwe indelingen, waar je nog niet 'gezocht' had, uitproberen. enzovoorts.

Misschien kan je per tak nog kijken hoeveel 'potentie' die tak heeft en aan de hand daarvan bepalen of je nog meer 'uitspruitingen' wilt doen dan die oorspronkelijke 5 uitspruitingen. Bijvoorbeeld voor elke uitspruiting die een hogere score oplevert er 2 uitspruitingen bijmaken... Dus als je vanaf uitspruiting 1 terugkomt naar de stam concluderen dat de tak waar je vandaan kwam een hogere score heeft dan de stam waar je nu op staat en dan dus 2 uitspruitingen erbij maken (waarbij dan de stam dus 7 uitspruitingen heeft...)

zoiets? Of doe je al zoiets?

[liquid_ice]

ff wat linkjes over genetische algoritmes die ik verzameld heb in de afgelope dagen:
http://nl.wikipedia.org/wiki/Genetisch_algoritme
http://alpha.uhasselt.be/...ubs/geneticAlgorithms.pdf
http://home.a-eskwadraat....netische%20Algoritmen.pdf
http://www.liacs.nl/~kosters/AI/genetisch.pdf
http://www.win.ua.ac.be/~verdonk/courses/opt/2005/ga.pdf

ik ben het niet helemaal eens met _WM_, beginnen met een al scorend begin set kan wel voordelen hebben denk ik. Met relatief weinig computer power kan je een redelijke score maken. Als je die neemt en steeds wat aanpast (volgens de GA) kom je sneller hoger. zou ik denken.

maar je moet wel oppassen dat je niet in een lokaal optimum komt.

[ Voor 4% gewijzigd door liquid_ice op 03-06-2007 01:44 ]

[Verwijderd]

_wm_ schreef op zaterdag 02 juni 2007 @ 15:38:
[...]

Ik zal zometeen eens even checken met mijn script... Het nadeel is dat ik het met PHP doe en tussendoor niet echt een statusupdate of iets dergelijks kan doen omdat zolang Apache heel hard bezig is, er geen output naar de browser wordt gestuurd. Ik kan dus niet zien hoelang m'n script al bezig is en hoever ie is... dat is wel iets vervelend... Als iemand weet hoe je dat op kan lossen (ob_flush() oid helpt volgens mij niks...) dan zou dat zeer welkom zijn!

En gewoon flush() helpt ook niet? Dat gebruik ik altijd in zulke gevallen namelijk.

[Dricus]

@ _WM_ en Marcks:

Ik krijg uit jullie posts de indruk dat jullie proberen om één oplossing te laten evolueren tot een hoge score. Bij een evolutionair algoritme moet je volgens mij beginnen met een initiële populatie van allemaal random gegenereerde sets. Vervolgens kun je combineren, muteren en 'survival of the fittest' toepassen. Dit is in ieder geval grofweg mijn aanpak en hij werkt niet onaardig. Het is me zelfs al gelukt om vanuit een beginpopulatie van totaal willekeurig gegenereerde (en dus meestal ongeldige) oplossingen te evolueren tot een score van over de 200 punten in ongeveer 300 a 400 generaties. Er zijn nog genoeg mogelijkheden tot optimalisatie, dus dat gaat nog wel verbeteren .

[liquid_ice]

@MrHuge, hoe groot zijn jou populaties?

[The Flying Dutchman]

MrHuge schreef op zondag 03 juni 2007 @ 08:43:
@ _WM_ en Marcks:

Ik krijg uit jullie posts de indruk dat jullie proberen om één oplossing te laten evolueren tot een hoge score. Bij een evolutionair algoritme moet je volgens mij beginnen met een initiële populatie van allemaal random gegenereerde sets. Vervolgens kun je combineren, muteren en 'survival of the fittest' toepassen. Dit is in ieder geval grofweg mijn aanpak en hij werkt niet onaardig. Het is me zelfs al gelukt om vanuit een beginpopulatie van totaal willekeurig gegenereerde (en dus meestal ongeldige) oplossingen te evolueren tot een score van over de 200 punten in ongeveer 300 a 400 generaties. Er zijn nog genoeg mogelijkheden tot optimalisatie, dus dat gaat nog wel verbeteren .

Dit is ook een beetje wat ik in gedachten heb en waar ik waarschijnlijk naartoe ga werken.
Ik heb echter ook nog wat andere, meer 'experimentele' ideeën, maar die doe ik nog even niet uit de doeken (misschien ga ik ze ook wel nooit implementeren).

[Dricus]

liquid_ice schreef op zondag 03 juni 2007 @ 10:13:
@MrHuge, hoe groot zijn jou populaties?

Met de populatie groottes ben ik nog aan het spelen. De grootte is wel van invloed op de hoogte van de score. Getallen ga ik hier dus ff niet noemen .

[Verwijderd]

Zo, na een week elke dag een uurtje coden, en drie maal de kluts kwijtraken en opnieuw beginnen , ben ik er nu toch in geslaagd om een aardige basisindeling te maken. Ik haal nu rond de 320 punten op de officiële testset in < 100 ms. Deze week ga ik me eerste maar eens richten op het schrijven van een validator.

Ik heb ook geprobeerd om dit topic nog een beetje te volgen. Ik moet zeggen, jullie pakken het wel allemaal aardig 'serieus' aan. Van de wiskundige formules van een paar pagina's terug heb ik bijvoorbeeld geen kaas gegeten. Nee, jullie hoeven van mij geen serieuze competitie te verwachten. Ik doe vooral mee om er wat van te leren, en een hoge score halen is bijzaak.

@_wm_ : Kan het zijn dat je validator offline is gehaald? Firefox meldt mij sinds vijf minuten namelijk het volgende:

Firefox kan de server op www.willem-mulder.nl niet vinden.

edit:
Ow, hij doet het weer!

[EdwinG]

Heel eenvoudig, maar vast handig: Een overzicht van de validators, generators etc
http://got.typefreak.nl/huisjes/overzicht.html

[Verwijderd]

EdwinG schreef op zondag 03 juni 2007 @ 15:42:
Heel eenvoudig, maar vast handig: Een overzicht van de validators, generators etc
http://got.typefreak.nl/huisjes/overzicht.html

Zeker handig. Klopte dat scoreverhaal van Marcks dat er tussen staat nou wel of niet?
En het scoreverloop van MrHuge hoort er zeker tussen.

[EdwinG]

Is nu ook toegevoegd.

[Marcks]

Verwijderd schreef op zondag 03 juni 2007 @ 16:15:
[...]

Zeker handig. Klopte dat scoreverhaal van Marcks dat er tussen staat nou wel of niet?

Er zit een typefout in regel 18, de string Voorkeur$ moet natuurlijk de array Voorkeur$(ID) zijn. Verder werkt deze scoreberekening prima.

Het idee van een boom, zoals voorgesteld door _wm_, lijkt me in theorie heel goed te werken, maar het is lastig te implementeren. Om te beginnen loopt het geheugengebruik natuurlijk volledig uit de hand wanneer honderden indelingen van honderden deelnemers opgeslagen moeten worden. Dan moet je die indelingen noodgedwongen naar de harde schijf wegschrijven, en dat gaat de prestaties niet ten goede komen.

Ook moet je vanuit een bepaald punt gaan optimaliseren op een manier waarbij compleet verschillende indelingen gegenereerd worden; je hebt immers zoveel mogelijk takken nodig. De eenvoudigste manier om dat voor elkaar te krijgen is door willekeur, maar ik besteed de controle over mijn programma liever niet uit aan een willekeurige reeks getallen.

Aan de andere kant moet ik langzamerhand toch naar andere mogelijkheden kijken. Ik kan met het veranderen van enkele parameters een oplossing vinden in 2 seconden of anderhalf uur, maar ook met dat laatste kom ik qua score niet boven de 390 uit.

[Malthus]

_wm_ schreef op zaterdag 02 juni 2007 @ 23:16:
Hoe werken die 'evoluerende' methoden eigenlijk? Want ik gebruik nu feitelijk gewoon een rechttoe-rechtaan methode...
Moet je dan gewoon steeds een aantal mensen wisselen, kijken of de nieuwe set hoger ligt, en dan vanuit die set weer een aantal mensen wisselen? Of?

Mijn programma begint met 1000 mogelijke oplossingen die allemaal valide oplossingen zijn. Vervolgens selecteert het programma steeds drie willekeurige oplossingen. De slechtste van de drie wordt vervangen door een kopie van de beste van de drie (survival of the fittest). Vervolgens wisselt deze kopie nog wat gegevens uit met de derde selecteerde oplossing, en kunnen er nog enkele willekeurige verandering optreden. En als het goed is levert dit uiteindelijk een behoorlijk resultaat op.

De resultaten waren tot nu toe nog niet schokkend, maar ik moest nog wat met de instellingen inregelen. Helaas was m'n programma zo verschrikkelijk traag dat ik vandaag de helft van de code weggegooid heb en heb vervangen. Dus het zal nog even duren voor ik wat goede resultaten kan boeken.

[? ?]

[ok] inlezen
[ok] debug / timing
[ok] output
[ok] solve (first come first serve achtig)

alles wordt mooi met klassen opgelost: Huisje, Kamer, Persoon, Eetvoorkeur, Voorkeur, Huismanager
in VB.NET 2005 Express

code:

        [elapsed] 15ms  meeting.ini

[total] 15ms

        [elapsed] 125ms deelnemers.ini

[total] 140ms

        [elapsed] 0ms   solve

[total] 140ms

        [elapsed] 0ms   output

[total] 140ms

in 140ms heb ik op de eerste testset (100 huizen) -597 ... jihaaa
vind het trouwens niet leuk dat de nummering van de huizen (normaal/gehandicapt) apart is in output

[ Voor 12% gewijzigd door ? ? op 03-06-2007 23:14 ]

[? ?]

vraagje:
gaan er personen als roomies/partners in het ini bestand staan die zelf niet in het ini bestand staan?

[ Voor 4% gewijzigd door ? ? op 03-06-2007 22:23 ]

[SWINX]

in de testset komt iedere deelnemer (roomie/partner) in de deelnemers.ini voor
ik hoop dat we hier dus vanuit mogen gaan, maar als een modje dit nog even kan ophelderen weten we het zeker

[? ?]

was gewoon omdat op de validator pagina er een set stond waar dat het geval is
ik maak tijdens het inlezen van de ini voor elke nog niet bestaande persoon (persoon zelf, roomie, partner) een nieuw persoon object aan; anders moet ik de "lege" eruit gaan halen achteraf.

[SWINX]

De validator van Dreamer-1982 gaat zelfs niet verder als er een persoon in de output.ini voorkomt die niet in de deelnemers.ini zit

Ik zit namelijk even te testen met de online validator van _wm_ en het progje van Dreamer-1982.
Ik krijg bij Dreamer-1982 juist net deze melding dus vandaar (overigens onterecht, want je mag lege kamers gewoon wegschrijven naar je output.ini)

[ Voor 54% gewijzigd door SWINX op 04-06-2007 00:13 ]

[? ?]

argh, ik kreeg altijd maar de melding dat ik mensen dubbel boekte
blijkt nu dat ik geen é en andere speciale tekens inlas,Timo en Timéo waren gelijk

[ Voor 5% gewijzigd door ? ? op 04-06-2007 00:27 ]

[_wm_]

398 punten op de off testset na 1,6 seconde na iets aanpassen van variabelen... Die variabelen zullen echter per set wel weer anders liggen... Dus daar heb ik nog niet zo veel aan
Ga nog 2 verbeteringen in het algoritme doorvoeren, daarna ga ik maar weer eens wat anders proberen denk ik... Of het even een maandje laten liggen ofzo

edit: en 2133 punten op de grote set van YeXo... Is 5 minuten rekenen, maar dan heb je ook wat
grote set:
meeting - http://willem-mulder.nl/g...d9b4e44a744b290bc368c.ini
deelnemers - http://willem-mulder.nl/g...b59f92945053ca071ca2c.ini
ben wel benieuwd wat jullie daar op scoren?

[ Voor 36% gewijzigd door _wm_ op 04-06-2007 10:53 ]

[Dreamer-1982]

SWINX schreef op zondag 03 juni 2007 @ 23:39:
De validator van Dreamer-1982 gaat zelfs niet verder als er een persoon in de output.ini voorkomt die niet in de deelnemers.ini zit

Ik zit namelijk even te testen met de online validator van _wm_ en het progje van Dreamer-1982.
Ik krijg bij Dreamer-1982 juist net deze melding dus vandaar (overigens onterecht, want je mag lege kamers gewoon wegschrijven naar je output.ini)

Mijn validator gaat inderdaad niet door als er een persoon in output.ini voorkomt die niet in deelnemers.ini zit; lijkt me een beetje raar als er deelnemers voorkomen die niet eens gedefinieerd zijn, dit is bijna altijd het resultaat van een programmeerfout, zoals het niet kunnen inlezen van 'speciale' tekens als é. Ook kan het zijn dat de output.ini per ongeluk bij een verkeerde set (meeting.ini + deelnemers.ini) terecht is gekomen.

Lege kamers wilde hij inderdaad niet inlezen (kwam bij mij niet voor omdat ik ze niet wegschrijf). Dat heb ik even aangepast. Nieuwe versie staat online: http://paul-dekkers.com/scorevalidator.zip

[? ?]

Zijn er personen die eventueel willen samenwerken?

Ik ga eerst zelf een applicatie schrijven, maar aangezien er toch zoveel tijd is voor de deadline, zou ik ook graag samenwerken met wat mensen, voor een tweede inzending dan (als dat mag tenminste).
Samen weet je altijd meer! Taal zou .NET (vb/c#) zijn

[EdwinG]

era.zer schreef op maandag 04 juni 2007 @ 13:02:
Zijn er personen die eventueel willen samenwerken?

Ik ga eerst zelf een applicatie schrijven, maar aangezien er toch zoveel tijd is voor de deadline, zou ik ook graag samenwerken met wat mensen, voor een tweede inzending dan (als dat mag tenminste).
Samen weet je altijd meer! Taal zou .NET (vb/c#) zijn

Je eerste inzending is de enige inzending die telt, een tweede inzending zullen we niet in ogenschouw nemen.

[Verwijderd]

Heel simpel gezegd is het het leukst als je op maar één paard wedt.

[? ?]

De tweede inzending zal ook niet "mijn" inzending zijn, maar van de groep, dus zoals de regels geschreven zijn kan dat toch?

Het gaat niet om zoveel mogelijk kans, maar om nieuwe ideeën. Ik denk in een richting en pin me daarop vast terwijl anderen nieuwe frisse ideeën aanbrengen.

[Dreamer-1982]

_wm_ schreef op maandag 04 juni 2007 @ 10:01:
398 punten op de off testset na 1,6 seconde na iets aanpassen van variabelen... Die variabelen zullen echter per set wel weer anders liggen... Dus daar heb ik nog niet zo veel aan
Ga nog 2 verbeteringen in het algoritme doorvoeren, daarna ga ik maar weer eens wat anders proberen denk ik... Of het even een maandje laten liggen ofzo

edit: en 2133 punten op de grote set van YeXo... Is 5 minuten rekenen, maar dan heb je ook wat
grote set:
meeting - http://willem-mulder.nl/g...d9b4e44a744b290bc368c.ini
deelnemers - http://willem-mulder.nl/g...b59f92945053ca071ca2c.ini
ben wel benieuwd wat jullie daar op scoren?

Ik heb deze set ook eens getest, meestal kwam ik op zo'n 2060 tot 2080 punten. In mijn huidige opzet kan alleen erg veel gevarieerd worden met instellingen. Na wat proberen kwam ik uiteindelijk op 2148 punten. Maar dan is er in totaal (met al het proberen) zeker langer dan een half uur gerekend (en dat op een E6600@3,6GHz ) Ik was al bezig met een compleet nieuwe oplossing te maken, een startset creeren en deze d.m.v. een backtrack algoritme optimaliseren. Het backtracken kost alleen ontzettend veel tijd bij een grote set (en dan is het al behoorlijk geoptimaliseerd) en het aantal punten dat hij nu met het backtrack algoritme behaalt valt me ook nog tegen. Ik heb het idee dat hij met de startset eigenlijk al in een lokaal optimum terecht is gekomen wat nog wel iets valt te verbeteren, maar niet genoeg.

Nu nog maar eens een soort van genetisch algortime implementeren en eens kijken wat dat ervan bakt.

[liquid_ice]

ik vind het een leuk idee van era.zer, maar ik ben nog druk bezig met mijn inzending.
(ik heb het inlezen van de files en ben bezig met het controlleren ervan...)

en op 7 -juli ga ik op vakantie, dus ik moet um ook nog eerder inleveren.

[Vaan Banaan]

era.zer schreef op zondag 03 juni 2007 @ 22:23:
vraagje:
gaan er personen als roomies/partners in het ini bestand staan die zelf niet in het ini bestand staan?

Daar ga ik wel van uit.
Een allerdaags voorbeeld in de praktijk:
Henk heeft Klaas als roomie hebt opgegeven, en Klaas wint de lotto en gaat op wereldreis, voor hij zich had opgegeven voor de meeting.
Zomaar een doorsnee voorbeeld

[? ?]

lijkt vrij normaal, maar kan een mod dit bevestigen/ontkennen aub?
al die extra controles vind ik codevervuiling

[Balachmar]

Ja, ook de encoding bijvoorbeeld. Im ga er nu vanuit dat de namen enzo alleen uit normale characters bestaan en niet deze dingen: Timéo.
Ik kan dat wel fixen, maar als het niet nodig is...

[RobIII]

era.zer schreef op maandag 04 juni 2007 @ 14:57:
lijkt vrij normaal, maar kan een mod dit bevestigen/ontkennen aub?
al die extra controles vind ik codevervuiling

Balachmar schreef op maandag 04 juni 2007 @ 15:57:
Ja, ook de encoding bijvoorbeeld. Im ga er nu vanuit dat de namen enzo alleen uit normale characters bestaan en niet deze dingen: Timéo.
Ik kan dat wel fixen, maar als het niet nodig is...

We kunnen het wel blijven herhalen, maar punt is nou eenmaal dat we ook kijken naar hoe stabiel je code is (en of je code dus tegen een stootje kan). Je kunt dat codevervuiling of "teveel werk" vinden om te maken; dat is aan jezelf. En daarbij: zo spannend is een é nou ook weer niet...

Overigens is dat hele encoding verhaal nu wel uitgekauwd

[ Voor 10% gewijzigd door RobIII op 04-06-2007 16:06 ]

[Verwijderd]

Als je de waarden uit het invoerbestand letterlijk kopieert en gebruikt, dan kan het al niet fout gaan. Ik keek met C eerst al niet eens naar de encoding, en het werkte al prima.

[ArtyShock]

Vaan Banaan schreef op maandag 04 juni 2007 @ 14:50:
Daar ga ik wel van uit.
Een allerdaags voorbeeld in de praktijk:
Henk heeft Klaas als roomie hebt opgegeven, en Klaas wint de lotto en gaat op wereldreis, voor hij zich had opgegeven voor de meeting.
Zomaar een doorsnee voorbeeld

Dat lijkt een plausibele praktijksituatie, maar als je de regels er op naslaat is het niet goed mogelijk een juiste beslissing te nemen wat te doen als een roomie wel is opgegeven maar niet voorkomt in de deelnemers.ini.

Stel dat Jan de roomies Leo, Ubbo en Leroy heeft opgegeven en Ubbo komt niet voor in de deelnemers.ini. Aangezien niet gespecificeerd is hoe deze situatie af te handelen en je besluit Ubbo te negeren als roomie, wordt Leroy dan de tweede roomie (voor drie punten samen op een kamer) of blijft hij de derde keuze (voor twee punten samen op een kamer)?

Omdat het enigszins schimmig blijft hoe dit op te lossen heb ik maar besloten deze situatie als fout aan te merken.

[roy-t]

Lijkt me ook compleet onzinnig om mensen als partner op te geven voor vakantie, en die dan niet mee te nemen, dat doe je als je bij OAD boekt toch ook niet

*laat het er dus ook uit* hmm structjes vliegen in het rond de data nu al super-geordend maar moet er werl iets mee doen

[SWINX]

[message=28158341,noline]RobIII schreef op maandag 04 juni 2007 @ 16:01[/message
We kunnen het wel blijven herhalen, maar punt is nou eenmaal dat we ook kijken naar hoe stabiel je code is (en of je code dus tegen een stootje kan). Je kunt dat codevervuiling of "teveel werk" vinden om te maken; dat is aan jezelf. En daarbij: zo spannend is een é nou ook weer niet...

Overigens is dat hele encoding verhaal nu wel uitgekauwd

Misschien ten overvloede, maar wordt voor de "defensive-test" een andere ini gebruikt dan voor een normale test? Of is het gewoon een test, een INI en we zien wel hoever hij komt.

Ik kan me namelijk voorstellen dat je gebruikt maakt van een "normale" INI om het programma gewoon te testen, en een iets wat afwijkende INI ofzo om te kijken wat het allemaal aankan.

Aan de andere kant kan je ook maar 1 INI gebruiken (mogelijk enigzins afwijkend) waardoor de code van iemand totaal anders gaat reageren, terwijl die het met een normale INI wel zou doen zeg maar.

Eigenlijk is dus de vraag, is de defensive-test tegelijkm met de normale test, of wordt deze apart getest (omdat deze ook apart vernoemd wordt in de startpost).

Misschien kan iemand hier wat over vertellen als jullie willen, anders zullen wij helaas moeten gokken ....

(Persoonlijk zou ik het ook maar vreemd vinden als je bij iemand op de kamer kan liggen die niet op de deelnemers lijst staat.)

[ Voor 4% gewijzigd door SWINX op 04-06-2007 17:25 ]

[RobIII]

SWINX schreef op maandag 04 juni 2007 @ 17:13:
Misschien ten overvloede, maar wordt voor de "defensive-test" een andere ini gebruikt dan voor een normale test?

De defensive test is puur voor het beoordelen op 'defensitieviteit' _{* RobIII vandale.nl inlicht} . De contest-set zal geen plaag-dingen bevatten; het gaat immers om de score

SWINX schreef op maandag 04 juni 2007 @ 17:13:
Ik kan me namelijk voorstellen dat je gebruikt maakt van een "normale" INI om het programma gewoon te testen, en een iets wat afwijkende INI ofzo om te kijken wat het allemaal aankan.

Juistem

[EdwinG]

Kijk bijvoorbeeld naar de verschillende tests aan het einde van de vorige contest:
http://crew.tweakers.net/Contests/PRG/002/files/finalset.zip

[Dricus]

_wm_ schreef op maandag 04 juni 2007 @ 10:01:
398 punten op de off testset na 1,6 seconde na iets aanpassen van variabelen... Die variabelen zullen echter per set wel weer anders liggen... Dus daar heb ik nog niet zo veel aan
Ga nog 2 verbeteringen in het algoritme doorvoeren, daarna ga ik maar weer eens wat anders proberen denk ik... Of het even een maandje laten liggen ofzo

edit: en 2133 punten op de grote set van YeXo... Is 5 minuten rekenen, maar dan heb je ook wat
grote set:
meeting - http://willem-mulder.nl/g...d9b4e44a744b290bc368c.ini
deelnemers - http://willem-mulder.nl/g...b59f92945053ca071ca2c.ini
ben wel benieuwd wat jullie daar op scoren?

Grmz, ik moet nodig wat aan m'n performance doen... Die grote set is bij mij niet vooruit te branden, dus die heb je nog tegoed .
Bij de officiële testset zit ik momenteel op 372 punten max.

[Malthus]

RobIII schreef op maandag 04 juni 2007 @ 16:01:
Overigens is dat hele encoding verhaal nu wel uitgekauwd

Toch vind ik het bizar dat het hele encoding verhaal in C# is op te lossen door Encoding.Default als parameter toe te voegen bij het openen van een StreamReader. Hoe standaard is zo'n default nou als je die expliciet moet opgeven?

[Verwijderd]

Malthus schreef op maandag 04 juni 2007 @ 20:27:
[...]


Toch vind ik het bizar dat het hele encoding verhaal in C# is op te lossen door Encoding.Default als parameter toe te voegen bij het openen van een StreamReader. Hoe standaard is zo'n default nou als je die expliciet moet opgeven?

Dat is omdat niet c# zelf, maar het gebruikte NINI-tool om de ini bestanden te parsen, het standaard onder een andere encoding probeert in te lezen. Als je het nini object aanmaakt met gewoon de filename als paramter, dan moet hij zelf nog een stream openen en je weet niet met welke encoding die het dat doet. Dus met een vooraf aangemaakte stream als parameter voor het nini object in te geven, doet hij het wel goed.

[Darkwings]

Yay!

Ik heb valide output gemaakt

Nu nog output die een beetje scoort

[Marcks]

Mijn oude programma gaat helemaal de deur uit. Hij was te langzaam, haalde te lage score's en er kon naar mijn weten niet veel meer aan verbeterd worden. Ondanks mijn eerdere kritiek op het idee van _wm_ om een boom van indelingen te gebruiken, ga ik toch proberen dit te implementeren. Daarvoor eerst eens langs de electronicazaak om nieuwe geheugenkaartjes in te slaan.

Ik begin met een eenvoudige startindeling. Ik weet nog niet hoe lang ik deze door ga optimaliseren (hoge en lage score's hebben beide hun voordelen), maar soit. Daarna ga ik vanuit die indeling zoveel mogelijk nieuwe indelingen (takken) maken, die de 'oude' indeling als parent krijgen. Als er geen nieuwe takken meer bijgemaakt kunnen worden, wordt één van de bestaande takken gevolgd (de hoogst scorende), en begint het verhaaltje overnieuw. Is een tak niet meer te optimaliseren, dan wordt deze gesloten, en ga ik terug naar de parent van de gesloten tak. Heeft ook deze tak geen open optimalisaties meer om te volgen, dan wordt ook deze gesloten, en gaan we terug naar de parent, enzovoorts. Flowchartje.

In theorie kan hiermee waarschijnlijk de perfecte oplossing gevonden worden, maar ik zal een afweging moeten maken tussen snelheid en zoekdiepte. Enfin, het idee is uitgewerkt, en ik kan veel routine's uit mijn oude programma kopiëren, dus deo volente heb ik het morgen werkzaam.

Post scriptum:
I'm gonna kick some ass and chew bubblegum, and guess what...


_{edit: Laat ik het linkje even goed neerzetten voor mijn lieve, geïnteresseerde medeforummers.}

[ Voor 4% gewijzigd door Marcks op 04-06-2007 22:48 ]

[EdwinG]

Marcks schreef op maandag 04 juni 2007 @ 22:45:
Post scriptum:
I'm gonna kick some ass and chew bubblegum, and guess what...

You're all out of gum?

edit:

It's time to kick ass and chew bubblegum, and I'm all out of gum

[ Voor 16% gewijzigd door EdwinG op 04-06-2007 22:55 ]

[Onbekend]

@_WM_:

De resultaten met waarvan de hash begint met d9f1167dce26aa6c...... mogen wat mij betreft verwijderd worden. Deze waren van mij, maar waarschijnlijk had ik het vinkje niet altijd uitgevinkt.

[Malthus]

Verwijderd schreef op maandag 04 juni 2007 @ 20:43:
Dat is omdat niet c# zelf, maar het gebruikte NINI-tool om de ini bestanden te parsen, het standaard onder een andere encoding probeert in te lezen.

Het grappige is dat ik geen NINI-tool gebruik (of dit moet standaard in een StreamReader zitten, maar zoveel weet ik nog niet van C#). Ik heb zelf een functie geschreven voor het inlezen van de ini-file, en ik had hierbij ook de encoding-problemen. Maar zoals ik al zei, ik weet nog niet zoveel van C#, dus het zou ook heel goed aan mij kunnen liggen.

[Malthus]

Marcks schreef op maandag 04 juni 2007 @ 22:45:
Ik begin met een eenvoudige startindeling. Ik weet nog niet hoe lang ik deze door ga optimaliseren (hoge en lage score's hebben beide hun voordelen), maar soit. Daarna ga ik vanuit die indeling zoveel mogelijk nieuwe indelingen (takken) maken, die de 'oude' indeling als parent krijgen. Als er geen nieuwe takken meer bijgemaakt kunnen worden, wordt één van de bestaande takken gevolgd (de hoogst scorende), en begint het verhaaltje overnieuw. Is een tak niet meer te optimaliseren, dan wordt deze gesloten, en ga ik terug naar de parent van de gesloten tak. Heeft ook deze tak geen open optimalisaties meer om te volgen, dan wordt ook deze gesloten, en gaan we terug naar de parent, enzovoorts. Flowchartje.

Leuk zo'n flowchart. En ik ben benieuwd welke resultaten je hiermee gaat bereiken.

Het valt me wel op dat je alleen naar output.ini schrijft als de tijd op is of als je klaar bent. Zelf heb ik ervoor gekozen om geen enkel risico te lopen: zodra er een betere indeling is gevonden, schrijf ik dit weg. Mocht m'n programma de tijd niet goed in de gaten houden of halverwege crashen, dan heb ik tenminste toch een resultaat.

[liquid_ice]

Ik gebruik ook geen nini, maar iets van codeproject.com site.
Ik kon de officiele testset gewoon inlezen en ook speciale tekens voor zover ik weet.

@Malthus: dat is veiliger ja, maar ook een heel stuk langzamer.
Doordat ie langzamer is haal je misschien de eindstreep niet en bereik je geen optimaal resultaat.

mijn progje doet 62,5 ms over het inlezen en het controlloleren van de input bij de officiele test set. Een groot gedeelte van deze tijd gaat op aan het meten, registreren en weergeven van de tijd, zo'n 1/3de oid.

Verder heb ik nog niks, maar ik ga slapen...
Morge om 06:00 weer op.

[ Voor 68% gewijzigd door liquid_ice op 05-06-2007 01:05 ]

[Serpie]

Marcks schreef op maandag 04 juni 2007 @ 22:45:
In theorie kan hiermee waarschijnlijk de perfecte oplossing gevonden worden, maar ik zal een afweging moeten maken tussen snelheid en zoekdiepte. Enfin, het idee is uitgewerkt, en ik kan veel routine's uit mijn oude programma kopiëren, dus deo volente heb ik het morgen werkzaam.

Hmm dit is ook de richting die ik op wilde gaan, alles wat ik had (net zo lang wisselen tot er een lokaal optimum bereikt is) ligt nu op zijn kop en tot ik mijn opdracht voor mijn propedeuse af heb heb ik geen tijd meer voor deze contest. Dus ik hoop dat ik nog tijd heb daarna anders heb ik niets

De deadline voor mijn P is 7 juli, dus dan heb ik nog 10 dagen ofzo, maar goed we zullen zien .

[KoW]

liquid_ice schreef op dinsdag 05 juni 2007 @ 00:13:
mijn progje doet 62,5 ms over het inlezen en het controlloleren van de input bij de officiele test set. Een groot gedeelte van deze tijd gaat op aan het meten, registreren en weergeven van de tijd, zo'n 1/3de oid.

Huh, welk algoritme gebruik jij dan voor "het meten, registreren en weergeven van de tijd" dat je daar 20 ms aan kwijt bent