Dat is het hele 'probleem' juist: je loopt bij optimaliseren vaak tegen een lokaal optimum aan waardoor je niet verder komt. Vooral bij random verbeteringen bleef ik soms laag steken en een andere keer kwam ik weer een stuk hoger uit.Marcks schreef op dinsdag 29 mei 2007 @ 21:43:
Vanochtend ben ik eens begonnen mijn gehele progje opnieuw te maken. Te veel aanpassingen hier en daar hebben het geheel nogal kreupel en slordig gemaakt, en mijn scoreberekening, die voorheen telkens werd uitgevoerd wanneer de score werd opgevraagd, wordt nu opgeslagen in een array. Een score van rond de 280 wordt nu gehaald in 12 seconden, maar dan bots ik ook tegen een lokaal optimum. Da's vreemd, want ik heb wel eens boven de 360 gescoord.
:strip_icc():strip_exif()/u/217269/neutral.jpg?f=community)
Verwijderd
Hmm, je hebt gelijk. Na inzenden op de validator van _wm_ sta ik in de lijst met 10 punten, maar zodra ik de pagina refresh is mijn score weg:? Meer mensen hier last van (gehad)? Iemand een idee waar het aan kan liggen?:
[...]
Kan aan mij liggen maar ik zie bij de officiele testset bij de online validator van _wm_ geen eens iemand met 10 punten staan. Ik heb daarna even alles open geklikt, maar zie uberhaupt geen inzending van YeXo ?!
Ik corrigeer mijzelf even, d'r klopt geen donder van mijn scoreberekening. Ik zat er niet minder dan 224 punten naast op een set van 150 deelnemers.
*schaamt zich diep voor zijn geneuzel over efficientie...
edit:
Nog maar even een correctie; zo'n grote fout was het ook weer niet. Alhoewel, probeer voor de gein eens een waarde uit een array te trekken zonder argumenten mee te geven.
[ Voor 12% gewijzigd door Marcks op 29-05-2007 22:57 ]
Ik veronschuldig mij bij voorbaat voor het bovenstaande.
:strip_icc():strip_exif()/u/220462/wm.jpg?f=community)
helaas zit er (volgens mij
) wel een foutje in...Je telt een NRIH nog steeds, ook al is die al een NRK. Maar dat kan ik mis hebben hoor!
Je hebt wel gelijk dat die van mij korter kan... Maar daar heb ik me nu nog even niet op gericht. Eerst alles werkend hebben en een leuk algoritme... Dat verbeteren/comprimeren komt later wel
Kben benieuwd naar jouw uiteindelijk code en plannen
Kzal aan die van mij ook eens wat sleutelen!
dat checken op personen te vaak indelen wordt nu trouwens gedaan... Ik zal de scorelijst even leeggooien!! Dan beginnen we fris opnieuw
[ Voor 10% gewijzigd door _wm_ op 29-05-2007 23:11 ]
Als mijn niet-roomie zich op mijn kamer bevindt, moet ik nog steeds andere niet-roomies tellen die zich níet op mijn kamer, maar wel in mijn huis bevinden. Daarvoor is de voorwaarde AND HuisGenoot <> KamerGenoot (HG<>KG) gesteld.:
[...]
helaas zit er (volgens mij
Je telt een NRIH nog steeds, ook al is die al een NRK. Maar dat kan ik mis hebben hoor!
Er zat overigens nog wel een ander foutje in. Een leeg bed op je kamer en een niet ingevulde niet-roomie kon ervoor zorgen dat er ten onrechte een match gevonden werd (Niet-roomie op kamer). Ach ja, wijsheid komt met de minuten, zeg ik altijd maar.
Mijn scores komen nu exact overeen met die van _wm_'s validator.
[ Voor 7% gewijzigd door Marcks op 29-05-2007 23:15 ]
Ik veronschuldig mij bij voorbaat voor het bovenstaande.
aah, die hele voorwaarde had ik over het hoofd gezien
als de waarden nu kloppen, dan geloof ik dat onze validators nu in ieder geval correct zijn!! hoera
:strip_icc():strip_exif()/u/49820/crop55d1f69498112_cropped.jpeg?f=community)
Ik heb besloten ook maar eens mee te doen .
Ik ga de meuk proggen in cross platform C++. De framework code is inmiddels praktisch klaar, morgen maar eens de score telling fixen en met het algoritme beginnen... mijn huidige pseudo-random indeling geeft de fantastische score van 8 op de test set
.
.Ik ga de meuk proggen in cross platform C++. De framework code is inmiddels praktisch klaar, morgen maar eens de score telling fixen en met het algoritme beginnen... mijn huidige pseudo-random indeling geeft de fantastische score van 8 op de test set
.
kga er nog even proberen een geldige hogere score overheen te gooien en dan ga ik naar bed:
Ik heb besloten ook maar eens mee te doen
Ik ga de meuk proggen in cross platform C++. De framework code is inmiddels praktisch klaar, morgen maar eens de score telling fixen en met het algoritme beginnen... mijn huidige pseudo-random indeling geeft de fantastische score van 8 op de test set
edit: toch maar even eerst naar bed na een mislukt invalidenalgoritme...
prepare
[ Voor 6% gewijzigd door _wm_ op 30-05-2007 00:55 ]
Ik heb de zaak even geanalyseerd: in kamer 5 en kamer 13 zaten de verschillen. Na even de situatie met de hand te hebben uitgewerkt kwam ik erachter dat mijn score inderdaad fout was. Toen even gekeken waar het aan lag: bleek dat niet-roomies op de kamer niet altijd goed geteld werden en er zat nog een foutje in het voorkeur gebeuren. Deze twee zijn eruit en ik kom dus nu op dezelfde score uit als YeXo en dus ook _wm_. Lijkt erop dat er eindelijk een goede scoreberekening is (nog maar niet te hard roepen
).De nieuwe versie staat natuurlijk online: http://paul-dekkers.com/scorevalidator.zip
:strip_icc():strip_exif()/u/182248/its_my_turn.jpg?f=community)
Beste meneer Huge.
het onderstel gedeelte van versie_7 bevat nog een fout.
Ik qoute uit de TS:
-5 Als een niet-roomie in dezelfde kamer wordt ingedeeld.
-2 Per nietroomie als deze in hetzelfde huis wordt ingedeeld, maar niet in de zelfde kamer.
Echter volgens jou schema houdt de negatieve punten telling op als er een niet-roomie op de kamer ligt. Er moet ook nog gechecked worden voor niet roomies in het huis
btw, ik vind je schema geweldig
het onderstel gedeelte van versie_7 bevat nog een fout.
Ik qoute uit de TS:
-5 Als een niet-roomie in dezelfde kamer wordt ingedeeld.
-2 Per nietroomie als deze in hetzelfde huis wordt ingedeeld, maar niet in de zelfde kamer.
Echter volgens jou schema houdt de negatieve punten telling op als er een niet-roomie op de kamer ligt. Er moet ook nog gechecked worden voor niet roomies in het huis
btw, ik vind je schema geweldig
[ Voor 4% gewijzigd door Sibylle op 30-05-2007 00:54 ]
Ctrl+k
Verwijderd
Mijn validator scoort nu ook hetzelfde. De code die in m'n programma de score bepaalt moet ik nog aanpassen, die is incorrect, en levert dus een verkeerd optimum. Ik hoop beter te kunnen scoren als dat is aangepast.
Ook moet mijn validator nog worden bijgeschaafd zodat hij dubbele personen, niet geplaatste personen en verkeerd geplaatste personen fout rekent.
Ik neem aan dat we nu allemaal op dezelfde lijn zitten, nu kan het echte werk dus beginnen
Ook moet mijn validator nog worden bijgeschaafd zodat hij dubbele personen, niet geplaatste personen en verkeerd geplaatste personen fout rekent.
Ik neem aan dat we nu allemaal op dezelfde lijn zitten, nu kan het echte werk dus beginnen
:strip_exif()/u/54199/crop5fac3f2ee1eff.gif?f=community)
Oude post, maar toch nog even hierover... Voor de competitie set mogen we er toch wel van uitgaan dat er geen ongeldige combinaties inzitten, zoals nu nog wel in de officiele testset zitten (roomie/nietroomie tussen organisatie en niet-organisatie)? Om er nu goed mee om te gaan (als in, proberen de boel te repareren ipv gewoon stoppen met een nette melding) geeft nogal wat rommel in de code.:
Als je het 'netjes' afhandelt (dus niet crashen en niet vrolijk met incorrecte data werken) is het al gauw goed
[ Voor 13% gewijzigd door DaCoTa op 30-05-2007 01:17 ]
/u/47683/Asterix%252060x60.png?f=community)
Volgens mij is hij wel goed. Let erop dat de activities Score -= 5 en Score -= 2 in een structured activity Doe Per Niet-Roomie staan. Daarmee wordt bedoeld dat dat blokje in zijn geheel wordt uitgevoerd voor elke niet-roomie van de huidige deelnemer.:
Beste meneer Huge.
het onderstel gedeelte van versie_7 bevat nog een fout.
Ik qoute uit de TS:
-5 Als een niet-roomie in dezelfde kamer wordt ingedeeld.
-2 Per nietroomie als deze in hetzelfde huis wordt ingedeeld, maar niet in de zelfde kamer.
Echter volgens jou schema houdt de negatieve punten telling op als er een niet-roomie op de kamer ligt. Er moet ook nog gechecked worden voor niet roomies in het huis
btw, ik vind je schema geweldig
Stel niet uit tot morgen wat je vandaag nog tot morgen kunt uitstellen...
ah, kijk eens aan, dat had ik over het hoofd gezien. Ik deed t per huidige deelnemers, vandaar.
Ik heb al een mooie manier gevonden om de algemene manier van dit STPP probleem op te lossen. Met deze set moet dat lukken tot minimaal 90% van de maximale score in 30min. Maar als de set ff wat groter wordt......dat schiet niet op zo
Ctrl+k
/u/139331/avatar.png?f=community){kind=avatar}
Ja na debuggen en vergelijken geeft mijn berekening dezelfe score's als Dreamer-1982:
Mijn validator scoort nu ook hetzelfde. De code die in m'n programma de score bepaalt moet ik nog aanpassen, die is incorrect, en levert dus een verkeerd optimum. Ik hoop beter te kunnen scoren als dat is aangepast.
Ook moet mijn validator nog worden bijgeschaafd zodat hij dubbele personen, niet geplaatste personen en verkeerd geplaatste personen fout rekent.
Ik neem aan dat we nu allemaal op dezelfde lijn zitten, nu kan het echte werk dus beginnen
Kunnen we nu weer verder met het echte werk inderdaad.
edit:
Mooi, zie ook dat de score's op de online validator gereset zijn. Even opnieuw een output maken
Mooi, zie ook dat de score's op de online validator gereset zijn. Even opnieuw een output maken
[ Voor 7% gewijzigd door Serpie op 30-05-2007 09:28 ]
:strip_exif()/u/159970/avatar.60x60.gif?f=community){kind=avatar}
:
[...]
Hmm, ach...die naam is eigenlijk puur cosmetisch. Verzin maar een naam, maakt niet uit wat, als het maar een unieke naam is.
Edit:
Hmm dus het gaat fout bij roomies binnen huis ik geef daar nog 1 punt per deelnemer maar dat mag niet (+1 als er roomies in het huis zitten, maakt niet uit hoeveel), sorry voor topic vervuiling maar heeft me wel geholpen de bug te tackelen
Hmm dus het gaat fout bij roomies binnen huis ik geef daar nog 1 punt per deelnemer maar dat mag niet (+1 als er roomies in het huis zitten, maakt niet uit hoeveel), sorry voor topic vervuiling maar heeft me wel geholpen de bug te tackelen
edit:
@Dash2in1 corrected maar nog steeds fout
@Dash2in1 corrected maar nog steeds fout
[ Voor 255% gewijzigd door Serpie op 30-05-2007 11:58 ]
een foutje met een count()-1 ipv een count()
Anyway, nu zou het toch echt goed moeten werken... kan iedereen naar hartelust uploaden en zou het nog correct bewaard moeten blijven ook
eerst werkte het scorebijhouden goed (dacht ik), toen heb ik het toch aangepast na een opmerking van iemand dat er een fout inzat, maar daarmee heb ik een fout gemaakt.
Die fout heb ik nu weer teruggedraaid en nu werkt het wel helemaal als het goed is.
Excuses voor het ongemak...!
(ik wil werken aan mn algoritme en niet aan de validator
)
[ Voor 5% gewijzigd door _wm_ op 30-05-2007 12:20 ]
Verbeteren is ook altijd irritant.:
[...]
eerst werkte het scorebijhouden goed (dacht ik), toen heb ik het toch aangepast na een opmerking van iemand dat er een fout inzat, maar daarmee heb ik een fout gemaakt.
Die fout heb ik nu weer teruggedraaid en nu werkt het wel helemaal als het goed is.
Excuses voor het ongemak...!
(ik wil werken aan mn algoritme en niet aan de validator
Beter is om heel hard na te denken, een mooi schema te maken op de muur voor je (niet met watervaste stift
) en dan in één keer een algorithme goed op te schrijven.Als je dna ook gelijk het beste hebt ben je klaar natuurlijk
Mjah, is best veel werk dat lang nadenken
Ctrl+k
ja klopt:
[...]
Verbeteren is ook altijd irritant.
Beter is om heel hard na te denken, een mooi schema te maken op de muur voor je (niet met watervaste stift
Als je dna ook gelijk het beste hebt ben je klaar natuurlijk
Mjah, is best veel werk dat lang nadenken
Eerst iets supergaafs bedenken en dat dan meteen bouwen... dat is echt top maar nu moet ik wel wat gaan optimaliseren... Ik loop steeds 30 punten achter op Dreamer-1982... Maar dat verschil kan ik zeker weten wegwerken... Dus ik ga vol goede moed aan de slag
En anders moet ik inderdaad maar weer eens wat nieuws uit gaan denken (ik teken het altijd in mn hoofd, niet met breinvaste stift
)...!
Maar ik blijf ook niet stilzitten he!
Maar ik laat jullie eerst wat inlopen, kan ik ondertussen even verder met mijn afstudeeronderzoek, al is dat een stuk saaier dan deze contest
het controleren van de testset op geldigheid is eigenlijk onzin... je moet er wel vanuit kunnen gaan dat de testset in ieder geval correct is!
Dat zelfs de officiële testset fouten bevat is dan ook wel heel erg jammer...
Maar dan nog blijf ik erbij dat je eigen script die fouten zou moeten ondervangen en niet de uiteindelijke puntenvalidator...
zoiets als dubbele (niet)roomies, oke, dat is nog even snel te kijken en valt te repareren.
Maar niet symmetrische partners, of iets tussen wel-organisatie en niet-organisatie kan je niet 'repareren'...
M'n punt is dus dat
1. er een testsetgenerator moet zijn die alleen valide testsets genereert
2. de officiële testset al helemaal correct moet zijn! (en dat er in dit geval dus gewoon een nieuwe officiële testset moet komen!)
3. als een set niet klopt, je script dat op moet vangen, en je je script gewoon op geldige sets moet laten draaien.
dus
Precies, de enige reden waarom een aantal van deze checks bij mijn validator zijn inbegrepen is omdat mijn validator ge-extract is uit mijn oplossing. Daar gebeuren al een aantal checks bij het inlezen van de deelnemers. Ik "repareer" dan ook meteen wat zaken, al blijft het de vraag of dat het juiste is om te doen, maar anders wordt logisch rekenen in ieder geval erg lastig.:
[...]
het controleren van de testset op geldigheid is eigenlijk onzin... je moet er wel vanuit kunnen gaan dat de testset in ieder geval correct is!
Dat zelfs de officiële testset fouten bevat is dan ook wel heel erg jammer...
Maar dan nog blijf ik erbij dat je eigen script die fouten zou moeten ondervangen en niet de uiteindelijke puntenvalidator...
zoiets als dubbele (niet)roomies, oke, dat is nog even snel te kijken en valt te repareren.
Maar niet symmetrische partners, of iets tussen wel-organisatie en niet-organisatie kan je niet 'repareren'...
M'n punt is dus dat
1. er een testsetgenerator moet zijn die alleen valide testsets genereert
2. de officiële testset al helemaal correct moet zijn! (en dat er in dit geval dus gewoon een nieuwe officiële testset moet komen!)
3. als een set niet klopt, je script dat op moet vangen, en je je script gewoon op geldige sets moet laten draaien.
dus
Kan wel, maar het blijft "repareren" met aanhalingstekens dus! In dit geval verwijder ik de partner gewoon.
:strip_icc():strip_exif()/u/51489/heforshe_logo_detail.jpg?f=community){kind=logo}
Ok, duidelijk argument. Dat dubbele deelnemers ongeldige invoer is, lijkt me logisch. De dubbele roomie notatie levert onduidelijke puntentellingen op, dus dat lijkt me ook niet echt handig om op te nemen. Voor de rest is het dan idd een kwestie van 'repareren'
Verwijderd
Aldus geschiede. Het algoritme is nu goed geïmplementeerd, wat dus inderdaad leidt tot hogere scores
Verwijderd
Wat voor scores moeten we dan aan denken? Zit je al over de 400 op de officiele testset?:
[...]
Aldus geschiede. Het algoritme is nu goed geïmplementeerd, wat dus inderdaad leidt tot hogere scores
Verwijderd
Weet je wel zeker dat alle bestanden geldig zijn? Probeer anders de validator van _wm_ eens, dan kunnen anderen je output.ini ook valideren (als je hem tenminste openbaar maakt):
[...]
Ik krijg een error 9, subscript out of range
[ Voor 0% gewijzigd door Verwijderd op 30-05-2007 19:13 . Reden: typo ]
Maakt niets uit, zolang iedereen dezelfde set krijgt voorgeschoteld, natuurlijk.
Ik kan nog veel meer van dat soort situaties verzinnen, tot situaties aan toe waar je meer punten haalt door iemand met lastige voorkeuren niet te plaatsen dan wel. Het lijkt me nou net de uitdaging om een algoritme te verzinnen dat daar ook mee om kan gaan
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:
[...]
Ik krijg een error 9, subscript out of range
Maar als je hem krijgt is de boel iig niet in orde!
:strip_exif()/u/26373/anim4.gif?f=community)
Had hier laatst niet iemand gepost dat het maar max 5 minuten hoefde te duren om een maximale score te halen?Ik kan nog veel meer van dat soort situaties verzinnen, tot situaties aan toe waar je meer punten haalt door iemand met lastige voorkeuren niet te plaatsen dan wel. Het lijkt me nou net de uitdaging om een algoritme te verzinnen dat daar ook mee om kan gaan
"I had a problem, I solved it with regular expressions. Now I have two problems". That's shows a lack of appreciation for regular expressions: "I know have _star_ problems" --Kevlin Henney
Krijg ik straks de schuld dat ik jullie op ideeen breng:
Wellicht, but it wasn't meHad hier laatst niet iemand gepost dat het maar max 5 minuten hoefde te duren om een maximale score te halen?
Then again, als in contest II mensen zulke hoge scores haalden in 1 resp. 1.5 minuut, moet dit in 30 seconden kunnen
dat denk ik niet eerlijk gezegd. Je kunt bij een willekeurige set niet eenduidig zeggen of je kunt ophouden. Dit is een zeer uitgebreid STPP probleem !:
[...]
Krijg ik straks de schuld dat ik jullie op ideeen breng
[...]
Wellicht, but it wasn't me
Then again, als in contest II mensen zulke hoge scores haalden in 1 resp. 1.5 minuut, moet dit in 30 seconden kunnen
De tot nu toe enige toegepaste methode voor dit soort problemen is in het ruw:
Veel mogelijkheen doorrekenen, als duidelijk is dat iets per definitie te weinig punten oplevert de mogelijkheden tak verbieden.
Echter is dit probleem best wel wat ingewikkelder dan zomaar een mogelijkheden tak uit zetten.
Om uit lokale optimums te komen moet de rekenkracht veel verhoogt worden, dat betekend dus dat de uiteindelijke optima bijna allemala gevonden moeten worden.
Oftewel: de precieze samenstelling van het bestand deelnemers.ini is zo belangrijk voor de complexiteit van het probleem dat de rekenkracht nodig pas na analyse hiervan goed bepaald kan worden.
Maar hopelijk gaan jullie niet voor ingewikkelde situaties
edit---
Wat bronnen:
http://www.bjarne.ca/pmflp.pdf
http://www.ai.sri.com/~peintner/papers/AAAI05PeintnerB.pdf !!!!
http://ametist.cs.utwente...cations/ruys-spin2003.pdf
uiteindelijk dus een manier van elegant brute force gebruiken
En de tijd is afhankelijk van de PC en deelnemers.ini.
[ Voor 12% gewijzigd door Sibylle op 30-05-2007 20:25 ]
Ctrl+k
/u/30520/crop63626c261c7cb_cropped.png?f=community)
Gaat de officiele parser dood als er alleen newlines op het einde van lijnen staan?
(
xml output, minder miserie )
(
xml output, minder miserie )
Ik ga echt keihard tijd te kort komen 
Ben nu bijna klaar met 't inlezen van de zooi op 'n redelijk elegante manier vind ik zelf, die ik ook later vrij eenvoudig met extra checks uit kan breiden. Als dat zo ver is de data nog ff checken op dingen die je niet verwacht (partners die niet kloppen enzo). Vervolgens eerst maar eens zorgen voor valide output op 'n psuedo-random manier, en dan kan het echte werk beginnen!
Maar tegen die tijd zijn we wel weer 'n weekje verder ben ik bang
was ik nog maar student
Ben nu bijna klaar met 't inlezen van de zooi op 'n redelijk elegante manier vind ik zelf, die ik ook later vrij eenvoudig met extra checks uit kan breiden. Als dat zo ver is de data nog ff checken op dingen die je niet verwacht (partners die niet kloppen enzo). Vervolgens eerst maar eens zorgen voor valide output op 'n psuedo-random manier, en dan kan het echte werk beginnen!
Maar tegen die tijd zijn we wel weer 'n weekje verder ben ik bang
was ik nog maar student
:strip_exif()/u/17260/icon.gif?f=community){kind=icon}
Je hebt helemaal gelijk! Dat krijg je als er staat: PuntenPerNietIngedeeldeDeelnemer = -1
De nieuwe versie staat weer online: http://paul-dekkers.com/scorevalidator.zip
@_wm_:
Het is al eerder opgemerkt, maar het deelnemersbestand met hash 4b0162771befcf1a19ef396f14f6b27f is corrupt: deelnemer David heeft een dubbele roomie. Jouw validator schijnt dit op te vangen, want de roomie wordt maar één keer geteld. Is het dan niet beter om zo'n validatie niet op te nemen in de lijst, net zoals gebeurt wanneer je bijvoorbeeld het aantal invalidenhuisjes overschrijdt? Sowieso vind ik die hele md5 een beetje overkill. De meeting.ini van de officiële testset zou je bijvoorbeeld net zo goed kunnen wegschrijven als 20,3,8.
Ik ga vannacht overigens eens even twee pc's overuren laten maken, beide gaan acht uur 'stijlvol bruteforcen', en ik zal niet rusten eer ik 500 punten haal! Alhoewel, klokje roept bedtijd. Tot morgen menskes.
Het is al eerder opgemerkt, maar het deelnemersbestand met hash 4b0162771befcf1a19ef396f14f6b27f is corrupt: deelnemer David heeft een dubbele roomie. Jouw validator schijnt dit op te vangen, want de roomie wordt maar één keer geteld. Is het dan niet beter om zo'n validatie niet op te nemen in de lijst, net zoals gebeurt wanneer je bijvoorbeeld het aantal invalidenhuisjes overschrijdt? Sowieso vind ik die hele md5 een beetje overkill. De meeting.ini van de officiële testset zou je bijvoorbeeld net zo goed kunnen wegschrijven als 20,3,8.
Ik ga vannacht overigens eens even twee pc's overuren laten maken, beide gaan acht uur 'stijlvol bruteforcen', en ik zal niet rusten eer ik 500 punten haal! Alhoewel, klokje roept bedtijd. Tot morgen menskes.
Ik veronschuldig mij bij voorbaat voor het bovenstaande.
:strip_exif()/u/60601/Arty.gif?f=community)
Ik vind die hash juist wel elegant. Op die manier weet je zeker dat je met dezelfde files aan de gang bent.
Gezien er nu wat meer tijd is maak ik voor deze contest m'n code maar eens wat meer defensive. Consistentere benamingen voor alles, abstracties, enumeraties, config files, de hele zwik. Hij leest nu alleen nog maar de meeting.ini en de deelnemers.ini in: 1500 regels code al.
Ik zou m'n vrije tijd echt zóveel beter kunnen gebruiken...
Heey iedereen,
Ik ga me ook mengen in deze contest...
Maar zoals ik al zie heb ik een behoorlijke achterstand (en ben druk met afstuderen), dus verwacht maar niet teveel concurentie .
Ik hoop dat ik een werkende output kan leveren voor het eind...
Veel suc6 iedereen.
FF vraagje, klopt het dat ELKE uitvoeg geldig is, mits:
1 - De validator um kan lezen
2 - Er geen organisator mensen bij niet organisator zitten
Ik ga me ook mengen in deze contest...
Maar zoals ik al zie heb ik een behoorlijke achterstand (en ben druk met afstuderen), dus verwacht maar niet teveel concurentie
.Ik hoop dat ik een werkende output kan leveren voor het eind...
Veel suc6 iedereen.
FF vraagje, klopt het dat ELKE uitvoeg geldig is, mits:
1 - De validator um kan lezen
2 - Er geen organisator mensen bij niet organisator zitten
[ Voor 21% gewijzigd door liquid_ice op 30-05-2007 23:36 ]
Klus page: http://klusthuis.blogspot.com
/u/147751/avatar455992_1.gif.png?f=community){kind=avatar}
Het leuke van de opzet van deze contest is dat er werkelijk allerlei verschillende talen langskomen in plaats van de inkoppertjes C, C++, Java en C#.
De testset met hash 23f4627befecbc8339d51b6cf9793fc34b0162771befcf1a19ef396f14f6b27f geeft een validatiefout in mijn inleesroutine. Er wordt namelijk de waarde 'geen' opgegeven in de deelnemers.ini om aan te geven dat er geen partner is. Dit lijkt me niet volgens de specificaties. 'geen' zou namelijk een prima username kunnen zijn.
[ Voor 17% gewijzigd door ArtyShock op 31-05-2007 00:29 ]
:strip_icc():strip_exif()/u/29425/drkatz.jpg?f=community)
Mijn rating is het nog niet eens met _wm_'s validator.
het probleem zit 'm in de roomies, maar ik heb toch echt het idee dat ik de regels opvolg zoals ze er staan, erg frustrerend
overigens doet de validator nogal raar als ik deze ouput.ini gebruik, de extra info in de bestanden werkt niet echt mee
als je checkt voor roomies in andere kamers dan je eigen, sla je de eigen dan wel over?
het probleem zit 'm in de roomies, maar ik heb toch echt het idee dat ik de regels opvolg zoals ze er staan, erg frustrerend
overigens doet de validator nogal raar als ik deze ouput.ini gebruik, de extra info in de bestanden werkt niet echt mee
als je checkt voor roomies in andere kamers dan je eigen, sla je de eigen dan wel over?
[invalidenhuis1] kamer1=Hans,Inge Janse kamer2=.oisyn,Grrrrrene kamer3=Terr,Koffie kamer4=Dido,Turkish points: partner 0 roomie 16 voorkeur 0 vegetarier -2 totale rating huisje: 14 [invalidenhuis2] kamer1=whoami,Aikeleer kamer2=dion_b,Ghost kamer3=Gwenneth,Margje kamer4=Joror,JHS points: partner 0 roomie 21 voorkeur 0 vegetarier 0 totale rating huisje: 21 [invalidenhuis3] kamer1=sanfranjake,naftebakje kamer2=SmartDoDo,Zoefff kamer3=Equator,Cookie kamer4=Creepy,Emmeline points: partner 10 roomie 15 voorkeur 0 vegetarier -2 totale rating huisje: 23 [huisje4] kamer1=HlpDsK,Janoz kamer2=Rataplan,Rosette kamer3=Juultje,McVirusS kamer4=LuNaTiC,BtM909 points: partner 10 roomie 11 voorkeur 1 vegetarier 0 totale rating huisje: 22 [huisje5] kamer1=Xandrios,dusty kamer2=Sophia,Ecteinascidin kamer3=Michel,Robin kamer4=Crash,F_J_K points: partner 0 roomie 11 voorkeur 0 vegetarier 0 totale rating huisje: 11 [huisje6] kamer1=Eggy,P_de_B kamer2=dawuss,Steffie kamer3=YellowCube,TinuX kamer4=Mick,haribold points: partner 0 roomie 10 voorkeur 0 vegetarier 2 totale rating huisje: 12 [huisje7] kamer1=Wouter Tinus,Sprite_tm kamer2=Daedalus,Fuelke kamer3=Longbeard,Stefke kamer4=Abbadon,DeeD2k2 points: partner 0 roomie 14 voorkeur 0 vegetarier 0 totale rating huisje: 14 [huisje8] kamer1=-NMe-,W3ird_N3rd kamer2=DSmarty,RM-rf kamer3=mOrPhie,Confusion kamer4=Jasper,Ralph Smeets points: partner 0 roomie 5 voorkeur 0 vegetarier 0 totale rating huisje: 5 [huisje9] kamer1=zeef,Orion84 kamer2=aperture,Hielko kamer3=Pim.,blaataaps kamer4=Martin Sturm,cybersteef points: partner 0 roomie 18 voorkeur 0 vegetarier 0 totale rating huisje: 18 [huisje10] kamer1=voodooless,Rukapul kamer2=GeniusDex,Wouke kamer3=leon1e,pasta kamer4=XangadiX,Spider.007 points: partner 0 roomie 12 voorkeur 0 vegetarier 0 totale rating huisje: 12 [huisje11] kamer1=Kaj.,elevator kamer2=Fisico,Atlas kamer3=Apen-nootjes,Drobanir kamer4=Jimmy Pop,Superdeboer points: partner 0 roomie 5 voorkeur 0 vegetarier 0 totale rating huisje: 5 [huisje12] kamer1=Floppus,Femme kamer2=Dimitri R,rob_erwt kamer3=IlseIII,RobIII kamer4=Hahn,woltjer points: partner 10 roomie 16 voorkeur 0 vegetarier 0 totale rating huisje: 26 [huisje13] kamer1= kamer2=,Oscar the Grouch kamer3=alt-92 kamer4= points: partner 0 roomie 6 voorkeur 1 vegetarier 0 totale rating huisje: 7 [huisje14] kamer1=Lustucru,JvS kamer2=Opi,bjck kamer3=polaris,moto-moi kamer4= points: partner 0 roomie 2 voorkeur 1 vegetarier 0 totale rating huisje: 3 [huisje15] kamer1=André,Janette kamer2=Kees,xxfile kamer3=KeX,Qwerty-273 kamer4=Wilke,Canaria points: partner 10 roomie 0 voorkeur 0 vegetarier 0 totale rating huisje: 10 [huisje16] kamer1=Pollewob,Pascal Saul kamer2= kamer3= kamer4= points: partner 0 roomie 3 voorkeur 1 vegetarier 0 totale rating huisje: 4 [huisje17] kamer1= kamer2=Harm kamer3= kamer4= points: partner 0 roomie 3 voorkeur 1 vegetarier 0 totale rating huisje: 4 [huisje18] organie kamer1=Kheldar,BalusC kamer2=JAVA-Doctor,Floris kamer3=botoo,T.T. kamer4=Remy,p0m points: partner 0 roomie -2 voorkeur 1 vegetarier 0 totale rating huisje: -1 [huisje19] organie kamer1=ACM,Renegade kamer2=AcouSE,Jan Laros kamer3= kamer4=Twynn,Thandor points: partner 0 roomie -2 voorkeur 1 vegetarier 0 totale rating huisje: -1 [huisje20] kamer1= kamer2= kamer3=dreeke,chem kamer4= points: partner 0 roomie 5 voorkeur 1 vegetarier 0 totale rating huisje: 6 rating: 105
oprecht vertrouwen wordt nooit geschaad
OMG!!!
Ik heb net letterlijk gedaan:
1.code voor de helft bewerkt en geoptimaliseerd voor de helft.
2.gegeten+tv gkeken
3.terug achter me laptop internetten
4.Borland openen, comment van mezelf niet lezen
5.code draaien en tegen allemala fouten oplopen
6. 2uur!!!!!! !!!!! fucking bezig geweest om te kijken hoe dat kon...
7.mezelf voor de kop slaan dat ik pas de helft van me code had veranderd
Ik werkte met random huisjes vuller, en checkte telkens alleen één huisje, dus de fout leek van allerlei verschillende kantn te komen, ik werd para.
Eerst 5 keer een ander fout op ene andere regel, dan opeens gene fout.... en nu snap ik het
bah, volgende keer onthouden wat ik aant doen was
ARJAN:
ik ben het iig met jouwn score eens over huisje met 21roomie punten (invalide 2).
De score validator van Dreamer-1982 echter zegt dat er een deelnemer in ouput zit die niet in deelnemers.ini zit. Welke heb je gebruikt?
kan mn eigen validator niet checken omdat die zit ingebakken.
Ik heb net letterlijk gedaan:
1.code voor de helft bewerkt en geoptimaliseerd voor de helft.
2.gegeten+tv gkeken
3.terug achter me laptop internetten
4.Borland openen, comment van mezelf niet lezen
5.code draaien en tegen allemala fouten oplopen
6. 2uur!!!!!! !!!!! fucking bezig geweest om te kijken hoe dat kon...
7.mezelf voor de kop slaan dat ik pas de helft van me code had veranderd
Ik werkte met random huisjes vuller, en checkte telkens alleen één huisje, dus de fout leek van allerlei verschillende kantn te komen, ik werd para.
Eerst 5 keer een ander fout op ene andere regel, dan opeens gene fout.... en nu snap ik het
bah, volgende keer onthouden wat ik aant doen was
ARJAN:
ik ben het iig met jouwn score eens over huisje met 21roomie punten (invalide 2).
De score validator van Dreamer-1982 echter zegt dat er een deelnemer in ouput zit die niet in deelnemers.ini zit. Welke heb je gebruikt?
kan mn eigen validator niet checken omdat die zit ingebakken.
[ Voor 17% gewijzigd door Sibylle op 31-05-2007 01:57 ]
Ctrl+k
:strip_exif()/u/47168/loop.gif?f=community)
racoontje:
Er past maar 1 roomie bij iemand op de kamer, dus het mag duidelijk zijn dat je per persoon maar op maximaal 1 van deze regels kan scoren.
{signature}
Juist, en voor de laatse geldt het zelfs niet per persoon, maar gewoon +1 ook al deel je 3 roomies in het huis in.:
Er past maar 1 roomie bij iemand op de kamer, dus het mag duidelijk zijn dat je per persoon maar op maximaal 1 van deze regels kan scoren.
Nou, ik wens je veel succes met deze voorwaarden. "Elke uitvoer is geldig mits meer kamers in een huis zijn gebruikt dan gegeven".
Ik veronschuldig mij bij voorbaat voor het bovenstaande.
:strip_icc():strip_exif()/u/30135/images.jpg?f=community)
In principe is deze set natuurlijk op te lossen door aannames te maken. Zo kan ik de maximale score van de Organisatie huisjes benaderen tot 96% over 20 iteraties. Echter, als bij de uiteindelijke delnemers.ini ervoor gekozen wordt om de set ingewikkeld te maken
:Veel afhankelijke punten, zoals roomie op niet roomies list partner bij niet roomies eten bij vega en partner/roomie terwijl een ander weer een niet roomie op vega lijst heeft etc.
Dan krijg je te maken met erg veel lokale optimums. Bij twee huisjes (organisators) is dat nog wel te doen door ipv 20 keer te itereren gewoon 100 keer te doen.
Maar als je echt eenduidig zeker wilt zijn dat de oplossing die je vind minstens 90% van de maximale score betreft moet je dus weten hoe en hoevaak je moet itereren. Dat hangt af van de uiteindelijke deelenmers.ini.
Ik probeer een representatieve score te maken voor de ingewikkeldheid en leidt daaruit af wanneer een oplossing voldoende gewenst is (geen klein lokaal optimum).
Als de deelnemers.ini random wordt gemaakt zal dit verhaal neit zo zeer opgaan. Maar vooral als er vanuit één unieke situatie wordt terugerekend naar de individuele delenemers, dan kan het moeilijk worden.
Stiekem ga ik ervan uit dat de jury dat niet zal doen, want het vergt nogal wat tijd en code om een unieke oplossing te ontbinden in componenten die volden aan deze voorwaardes. (mijn stelling over te ingewikkeld bedoelde ik dus voor het geval de jury dit WEL doet
).
Ctrl+k
STP problemen zijn scheduling problemen: je moet een aantal events in de tijd plaatsen. De beperkingen zijn alleen in de vorm van a_ij <= Xi - Xj <= b_ij. Bij een STPP modellering heb je ook nog een kostenfunctie afhankelijk van Xi - Xj. Het lijkt me heel sterk dat je het hier genoemde probleem zo kan modelleren.:
[...]
Ik heb al een mooie manier gevonden om de algemene manier van dit STPP probleem op te lossen. Met deze set moet dat lukken tot minimaal 90% van de maximale score in 30min. Maar als de set ff wat groter wordt......dat schiet niet op zo
Ergo, volgens mij is het helemaal geen STPP probleem
Verwijderd
Mijn validator is het bijna eens met die van _wm_, alleen kamer 13 hoor je 1 punten ipv 0 te krijgen (ivm dezelfde voorkeuren. Oscar heeft zuiphuis en alt-92 geen). Volgens mij is je set dus 120 punten waard.:
Mijn rating is het nog niet eens met _wm_'s validator.
het probleem zit 'm in de roomies, maar ik heb toch echt het idee dat ik de regels opvolg zoals ze er staan, erg frustrerend
overigens doet de validator nogal raar als ik deze ouput.ini gebruik, de extra info in de bestanden werkt niet echt mee
als je checkt voor roomies in andere kamers dan je eigen, sla je de eigen dan wel over?
Lukt zeker wel, maar je moet enkele aanpassingen maken::
[...]
STP problemen zijn scheduling problemen: je moet een aantal events in de tijd plaatsen. De beperkingen zijn alleen in de vorm van a_ij <= Xi - Xj <= b_ij. Bij een STPP modellering heb je ook nog een kostenfunctie afhankelijk van Xi - Xj. Het lijkt me heel sterk dat je het hier genoemde probleem zo kan modelleren.
Ergo, volgens mij is het helemaal geen STPP probleem
Lineariseren en opdelen in verschillende niveaus die lineair samenhangen.
Dit is te doen maar wel erg moeilijk, en zelfs als heb je een natuurgetrouw model, zit je met een STPP die zo ingewikkeld is dat je nog niet echt opschiet. Voordeel is wel dat als je eenmaal een goede linearisatiemethode hebt gevonden, je die kan toepassen op elke deelnemers.ini.
Het moeilijke is dus de juiste niveau's van linearisatie te vinden, en niet te grof te lineariseren.
Mjah, ik denk toch dat gewoon 30minuten brute forcen beter uitkomt
Ctrl+k
Lekker boeiend allemaal. De meeste van deze termen zijn ook van toepassing op de laatste twee contests. Net alsof je deze termen moet kennen/weten om hoog te kunnen scoren
Laat je niet afschrikken door mensen die met termen smijten. Door gewoon logisch na te denken kan je heel ver komen
[ Voor 10% gewijzigd door Creepy op 31-05-2007 12:08 ]
"I had a problem, I solved it with regular expressions. Now I have two problems". That's shows a lack of appreciation for regular expressions: "I know have _star_ problems" --Kevlin Henney
met logisch nadenken kom je er zeker, maar het is makkelijker om de PC het logische werk te laten doen:
[...]
Lekker boeiend allemaal. De meeste van deze termen zijn ook van toepassing op de laatste twee contests. Net alsof je deze termen moet kennen/weten om hoog te kunnen scoren
[...]
Laat je niet afschrikken door mensen die met termen smijten. Door gewoon logisch na te denken kan je heel ver komen
ik moet zegge dat t mij vies tegenvalt de snelheid te optimaliseren
Zit nu in arrays lijsten en vectors te spelen.
Het is in het ene geval niet te doen een van deze voor een ander in te ruilen (gemak en snelheid) en soms is hij juist weer gewenst om de snelheid te verhogen door deze wel in te ruilen, alleen dna moet hij daarna weer teruggeruild worden.... amagat.
mjah, is mijn eerste projectje in c++, dus ik mag van mezelf ontwerpfouten maken
Ctrl+k
Als STPP NP-compleet is dan gaat het wel lukken ja, maar zo kan ik nog wel wat problemen opnoemen. Het slaat helemaal nergens op om dit probleem als STPP te benoemen, je kan het dan net zo goed afbeelden op een Travelling Salesman Problem. En dat slaat ook nergens op. Het is leuk als je met wat wetenschappelijke termen gooit, maar in dit geval slaat het nergens op:
Lukt zeker wel, maar je moet enkele aanpassingen maken:
Lineariseren en opdelen in verschillende niveaus die lineair samenhangen.
Dit is te doen maar wel erg moeilijk, en zelfs als heb je een natuurgetrouw model, zit je met een STPP die zo ingewikkeld is dat je nog niet echt opschiet. Voordeel is wel dat als je eenmaal een goede linearisatiemethode hebt gevonden, je die kan toepassen op elke deelnemers.ini.
Het moeilijke is dus de juiste niveau's van linearisatie te vinden, en niet te grof te lineariseren.
Mjah, ik denk toch dat gewoon 30minuten brute forcen beter uitkomt
Ik zou het als ILP modelleren en door een solver rammen. Als alternatief kan je ook een local search variant pakken: simulated annealing of een evolutionaire aanpak lijken me het meest geschikt hier.
/u/173935/Avatar3_60x60.png?f=community){kind=avatar}
Volledig eens met joepP.
Gewoon een Lingo-model opstellen met alle beperkingen en het aantal punten maximaliseren. Of zoek(optimalisatie)-methodes (en constraint processing) uit AI toepassen (in Prolog bijvoorbeeld).
Maar idd, als het aantal variabelen groot is, is een Monte Carlo-aanpak de beste manier om een goede (misschien suboptimaal, maar met grote waarschijnlijkheid optimaal) oplossing te krijgen in een eindige tijd. Hier is daar meer informatie over.
Dit zijn dus een 3-tal manieren om het probleem aan te pakken. Misschien inspirerend voor sommigen onder jullie. Jammer genoeg heb ik geen tijd en kan ik niet meedoen, maar ik wens aan alle deelnemers veel succes toe!
Sorry voor eventuele technische termen, maar ik ben er zeker van dat ze u op wikipedia kunnen helpen, of anders google.
Edit: wat links geplaatst
Gewoon een Lingo-model opstellen met alle beperkingen en het aantal punten maximaliseren. Of zoek(optimalisatie)-methodes (en constraint processing) uit AI toepassen (in Prolog bijvoorbeeld).
Maar idd, als het aantal variabelen groot is, is een Monte Carlo-aanpak de beste manier om een goede (misschien suboptimaal, maar met grote waarschijnlijkheid optimaal) oplossing te krijgen in een eindige tijd. Hier is daar meer informatie over.
Dit zijn dus een 3-tal manieren om het probleem aan te pakken. Misschien inspirerend voor sommigen onder jullie. Jammer genoeg heb ik geen tijd en kan ik niet meedoen, maar ik wens aan alle deelnemers veel succes toe!
Sorry voor eventuele technische termen, maar ik ben er zeker van dat ze u op wikipedia kunnen helpen, of anders google.
Edit: wat links geplaatst
[ Voor 23% gewijzigd door just_moving op 31-05-2007 14:32 ]
:strip_icc():strip_exif()/u/11499/morphie.jpg?f=community)
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.
Een experimentele community-site: https://technobabblenerdtalk.nl/. DM voor invite code.
ik ben het er niet mee eens:
[...]
Als STPP NP-compleet is dan gaat het wel lukken ja, maar zo kan ik nog wel wat problemen opnoemen. Het slaat helemaal nergens op om dit probleem als STPP te benoemen, je kan het dan net zo goed afbeelden op een Travelling Salesman Problem. En dat slaat ook nergens op. Het is leuk als je met wat wetenschappelijke termen gooit, maar in dit geval slaat het nergens op
Ik zou het als ILP modelleren en door een solver rammen. Als alternatief kan je ook een local search variant pakken: simulated annealing of een evolutionaire aanpak lijken me het meest geschikt hier.
maar dat wist je natuurlijk al Dit probleem is in mijn ogen juist zeer goed als STPP probleem te modeleren, het kost alleen veel tijd. Traveling salesman is een te simpel geval vergeleken hiermee, dat is correct.
Maar ik bedoelde dat als je dit probleem gaat bekijken vanaf componenten en je deelt dus op in huisjes of voorkeurgroepen of roomiegroepen etc. kun je deze lossen componenten (deelproblemen) benaderen door een lineaire kostenfunctie op te stellen. Het deelprobleem is dan te benaderen als STPP.
De volgende stap is de STPP problemen samenpakken de het volgende level van deelproblemen te gaan benoemen, weer de kostenfunctie lineariseren. Je hebt dan dus een STPP van STPP's etc.
Het uiteindelijke probeelm is een lineair STPP structuur die als zodanig is op te lossen.
Ik geef toe dat het waarschijnlijk niet optimaal is (probee het maar eens te modelleren en te programen, ik werd er niet vorlijk van
). Maar ik denk wel dat als je tijd besteed aan een goede linearisatie van de kostenfuncties, en goede indeling van de deelproblemen, je dit probleem kunt oplossen met beter preciezie dan Sim. Annealing.Maar zoals ik graag zeg tegen de Matlab docenten:
"Als het mij meer tijd kost om te programeren, dan dat het scheelt per 10.000keer draaiien.
Is de methode helemala niet Effectiever"
Helaas is het er maar één met mij eens
Ctrl+k
Verwijderd
Tot je testset ineens 1000 deelnemers bevat, dan ga je veel meer cpu tijd nodig hebben. Evolutie theorien, hebben dan een hoger voorkeur om te gebruiken.:
[...]
ik ben het er niet mee eens
Dit probleem is in mijn ogen juist zeer goed als STPP probleem te modeleren, het kost alleen veel tijd. Traveling salesman is een te simpel geval vergeleken hiermee, dat is correct.
Maar ik bedoelde dat als je dit probleem gaat bekijken vanaf componenten en je deelt dus op in huisjes of voorkeurgroepen of roomiegroepen etc. kun je deze lossen componenten (deelproblemen) benaderen door een lineaire kostenfunctie op te stellen. Het deelprobleem is dan te benaderen als STPP.
De volgende stap is de STPP problemen samenpakken de het volgende level van deelproblemen te gaan benoemen, weer de kostenfunctie lineariseren. Je hebt dan dus een STPP van STPP's etc.
Het uiteindelijke probeelm is een lineair STPP structuur die als zodanig is op te lossen.
Ik geef toe dat het waarschijnlijk niet optimaal is (probee het maar eens te modelleren en te programen, ik werd er niet vorlijk van
Maar zoals ik graag zeg tegen de Matlab docenten:
"Als het mij meer tijd kost om te programeren, dan dat het scheelt per 10.000keer draaiien.
Is de methode helemala niet Effectiever"
Helaas is het er maar één met mij eens
Ikzelf ga het proberen te moddeleren met een genetisch algoritme, want het probleem is wel vergelijkbaar met dat van een Traveling salesman, maar dan met een aantal contraints.
Is enorm veel literatuur over te vinden, dus je kan op een korte tijd de verschillende methodes aanleren.
:strip_icc():strip_exif()/u/2646/shine.jpg?f=community)
Beetje het gras voor m'n voeten wegmaaien
Collega
( * Rukapul vermoedt niet dat z'n eerste C# programmeersel wat wordt
)
[ Voor 26% gewijzigd door Rukapul op 31-05-2007 14:44 . Reden: tussenpostert ]
Verwijderd
Ik heb 5 jaar geleden in school als opdracht voor de programmeerprojecten, een genetisch algortime moeten schrijven om het probleem van de handelsreiziger op te lossen. En dat is zoals dit probleem een permutatieprobleem.
En toen is het mij gelukt om de beste oplossing van de klas te maken en nog redelijk snel ook. Het waren wel maar 20 steden. Ik hoop dat het hiermee ook werkt.
Afwachten dus.
Dit topic is gesloten.