[GPC] (got programming contest) Opgave 1

[Dash2in1]

Op zondag 02 december 2001 23:47 schreef Xalista het volgende:
Yeah baby, yeah.

Ik kon even niet accepteren dat _piranha_ mijn snelheidsrecord vermorselde, dus ik heb even een ideetje, wat ik al langer had, uitgeprobeerd.
Dit ideetje houdt in dat ik een paar regels code omwissel, dus het is erg makkelijk uit te voeren. De consequentie hiervan is dat ik de zoekruimte in een andere volgorde doorzoek. Voor deze specifieke puzzel had dat het effect dat de oplossing (het potlood, met het aangevinkte vakje) niet in 50 minuten, maar in.... 60 miliseconden werd gevonden. Ja, dat lees je goed, 60 miliseconden.

Helaas, en dat wist ik ook wel vantevoren, wordt het algoritme hierdoor voor andere puzzels die eerst heel snel werden gevonden, nu een stuk langzamer. Ik moet dus een keuze maken voor welke opgaven ik het algoritme snel maak, want ik geloof niet dat ik vantevoren aan de opgave kan zien welke methode het snelste gaat zijn. Als jouw algoritme wel voor alle opgaven zo snel is ben ik benieuwd naar wat je maandag gaat laten zien. Dat zal trouwens wel dinsdag worden, wegens de nieuwe deadline.

Holy shit! De bom Hmm, toch maar vanavond eens kijken of ik hem 1) sneller krijg 2) ook die moeilijke kan laten oplossen .. zat nu op bijna 85 secondes voor die van twilight burn En 13 secondes over die kraker van xalista, om erachter te komen dat hij hem niet kan oplossen.

[LuCarD]

Hmmm... het is me een bijna gelukt geld dat ook?

* LuCarD had een "smart - bruteforce" methode bedacht, maar helaas na een Memory leak, ben ik nu helaas op een ander probleem gestruikeld.

Mijn programma stopt ALTIJD na 16778 itteraties Geen idee waarom. Krijg dan een vage melding terug van de server "Illegal response from server"

Helaas heb ik vandaag verdomd weinig tijd, anders had ik misschien nog wel kunnen kijken.

* LuCarD is trouwens heel benieuwd naar de diverse algoritmes.
Brute-force snap ik nog wel maar ik heb geen idee hoe je een zo'n puzzel kan berekenen.

[Crysania]

Op maandag 03 december 2001 10:46 schreef LuCarD het volgende:

Brute-force snap ik nog wel maar ik heb geen idee hoe je een zo'n puzzel kan berekenen.

gewoon zelf een paar van die puzzels oplossen en opschrijven wat je nu precies doet, en zul je zien dat je niet zo heel veel verschillende dingen doet (sorry als ik te veel verklap, heb zelf ook nog geen werkende versie)

[LuCarD]

Op maandag 03 december 2001 10:49 schreef THE_CR0SS het volgende:

[..]

gewoon zelf een paar van die puzzels oplossen en opschrijven wat je nu precies doet, en zul je zien dat je niet zo heel veel verschillende dingen doet (sorry als ik te veel verklap, heb zelf ook nog geen werkende versie)

Dat heb ik ook nog wel gedaan....

En op het net kan je diverse tutorials vinden over de beste methode.....

Maar dat maakt nog geen algoritme

HINT voor zoeken:
[wasigh edit: hints geven we nog niet]

[BalusC]

Ik ben ook met een soortgelijk probleem geconfronteerd. Ook ik pas brute force toe en mijn taaltje accepteert niet meer dan 1024 karakters per commandline, wat soms wil voorkomen bij grotere en ingewikkeldere afbeeldingen.

Maar ik vind dat mijn programma theoretiesch in orde is, ook al is ie tering langzaam en pikt ie niet graag grote afbeeldingen ivm de eerdergenoemde beperking..

Hierbij stuur ik hem toch naar jou op, Wasigh, al is het alleen maar om de code te bekijken

[Verwijderd]

/me heeft zojuist een simpele, super-langzame, ranzig gecodeerde maar volgens mij wel werkende oplossing in VBScript gesubmit.

Beter laat dan nooit, toch?

[D2k]

Op maandag 03 december 2001 11:21 schreef MrX het volgende:
/me heeft zojuist een simpele, super-langzame, ranzig gecodeerde maar volgens mij wel werkende oplossing in VBScript gesubmit.

Beter laat dan nooit, toch?

uhm
<n00b mode>
Mr-x hoe run ik dat ding??
</n00b mode>

[raptorix]

Op maandag 03 december 2001 11:30 schreef D2k het volgende:

[..]

uhm
<n00b mode>
Mr-x hoe run ik dat ding??
</n00b mode>

IIS?

[Verwijderd]

Op maandag 03 december 2001 11:30 schreef D2k het volgende:

[..]

uhm
<n00b mode>
Mr-x hoe run ik dat ding??
</n00b mode>

/me grinnikt

Je moet de windows scripting host hebben. Versie 5.6 is ergens op http://msdn.microsoft.com/scripting/ te downloaden, maar met Win2K staat het al op je machine als het goed is.

Je kan het runnen door de .vbs bestandsnaam te associeren met wscript.exe. Of je kunt naar de command line gaan en "wscript opgave1.vbs" intypen.

Enjoy

edit:
Wie weet ga ik iedere opgave wel in een andere taal coden. Java, Perl, JScript, Python, Visual Basic, etc ...

[Nielsz]

Op maandag 03 december 2001 11:30 schreef D2k het volgende:

[..]

uhm
<n00b mode>
Mr-x hoe run ik dat ding??
</n00b mode>

n00b

[D2k]

Op maandag 03 december 2001 11:35 schreef MrX het volgende:

[..]

/me grinnikt

Je moet de windows scripting host hebben. Versie 5.6 is ergens op http://msdn.microsoft.com/scripting/ te downloaden, maar met Win2K staat het al op je machine als het goed is.

Je kan het runnen door de .vbs bestandsnaam te associeren met wscript.exe. Of je kunt naar de command line gaan en "wscript opgave1.vbs" intypen.

Enjoy

hmmzz
dan zal je ff moeten w88 op het antwoord
tenzij jRobert/wasigh het aan de praat krijgen

hier op de zaak lukt het me iig niet

[Verwijderd]

Op maandag 03 december 2001 11:41 schreef D2k het volgende:

[..]

hmmzz
dan zal je ff moeten w88 op het antwoord
tenzij jRobert/wasigh het aan de praat krijgen

hier op de zaak lukt het me iig niet

Hmmmmm .... zie [topic=333063/1/25]

De programma's moeten draaiien op een pentium 3 700, 128 mb, win2000.

en

Alle mogelijke talen mogen gebruikt worden.

[D2k]

Op maandag 03 december 2001 11:57 schreef MrX het volgende:

[..]

Hmmmmm .... zie [topic=333063/1/25]
[..]

en
[..]

jepz
maar aan die specs voldoe ik thuis wel

maar hier niet

[wasigh]

Ik heb geen potientieel virus gevaarlijke software op mijn systeem staan. En heb ook even geen tijd om dat te downloaden. Dat laat dus jRobert over

[roelio]

hoor ik daar wscript.exe?

[Verwijderd]

Op maandag 03 december 2001 12:12 schreef limoentje het volgende:
hoor ik daar wscript.exe?

Hmmmm ....

De Windows Scripting Host is niets mis mee. Het is niet veel anders dan de engines voor shell scripts of voor Perl onder Unix. 't Is zelfs iets krachtiger, omdat je er meerdere scripting engines onder kunt hangen.

Waarom veel mensen een hekel eraan hebben heeft niets te maken met de WSH, maar met de brakke beveiliging van Windows, waarbij beveiligingsnivo's moeilijk zijn te leggen. Met een Perl script op een Unix bak kun je net zo goed een hele schrijf deleten als met een VBScript, alleen belet de betere rechtenstructuur van Unix de meeste schadelijke akties, waar het bij Windows veel moeilijker of soms onmogelijk is om dat te bereiken.

[roelio]

ben ik helemaal met je eens maar ondanks dat die beveiliging niet deugt is het natuurlijk de scripttaal die er op "aangekeken" wordt. Technisch gezien heb je helemaal gelijk maar daarom roept de windows scripting host nog wel doemscenarios bij * roelio op

zo en nu coden!!

[Verwijderd]

ik zie dat ik een opgave mag nakijken
zal ns snel aan de gang dan...

[Verwijderd]

Ik lees nu net pas de rest van de thread en vind de opgave steeds flauwer worden. Ik zal geen spoilers geven, maar dit is kennelijk een zeer bekende puzzel waar all-over het net hinst en tips zijn te vinden die kunnen leiden tot een snel algoritme.

Omdat je geen gecontroleerde omgeving hebt (zoals op het NK proggen, waar je, in mijn tijd in ieder geval, geen toegang tot het internet had) kan iedereen zijn / haar voordeel doen door gewoon eens stevig te gaan zoeken.

Kunnen vervolgopdrachten niet-traditionele puzzels zijn? Anders wordt het meer een 'zoek-maar-raak-voor-een-knaak' wedstrijd.

edit:

Mijn algoritme is dus ranzig langzaam omdat het een eenvoudig back-tracking algoritme is, niet zo op dit probleem toegespitst.

Overigens zou niet pas halverwege een thread van +/- 21 x 25 = 525 posts een cruciale opmerking moeten staan dat de oplossing in 15 min. gevonden moet kunnen worden. Dergelijke info moet dan in de beginpost erbij gezet worden.

[D2k]

Op maandag 03 december 2001 15:03 schreef MrX het volgende:
Ik lees nu net pas de rest van de thread en vind de opgave steeds flauwer worden. Ik zal geen spoilers geven, maar dit is kennelijk een zeer bekende puzzel waar all-over het net hinst en tips zijn te vinden die kunnen leiden tot een snel algoritme.

jepz zou best kunenn
maar dan nog vin ik dat we in 2 thread van bijna 1000posts samen met 6 of 7 oplossingen te maken hebben met mensen die het zelf proberen
anders is nl een wedstrijd niet leuk en moet je gewoon de uitdaging laten schieten

Omdat je geen gecontroleerde omgeving hebt (zoals op het NK proggen, waar je, in mijn tijd in ieder geval, geen toegang tot het internet had) kan iedereen zijn / haar voordeel doen door gewoon eens stevig te gaan zoeken.

Kunnen vervolgopdrachten niet-traditionele puzzels zijn? Anders wordt het meer een 'zoek-maar-raak-voor-een-knaak' wedstrijd.

[Verwijderd]

Ja ach, aan de inzendingen die wij binnen krijgen kunnen we wel zien of mensen copy pasten of niet. Daarbij als mensen verschillende keer inzenden en iedere keer hun algoritme verbeteren, zijn zij ook heus serieus bezig.

Verder is het wedstrijd voor de lol en wordt van iedereen sportiviteit gevraagd (wasigh heeft hierover een oproep gedaan, omdat bleek dat hier idd op het internet een en ander over bekend was).

Als laatste wil ik nog graag kwijt dat voor werkelijk ieder probleem al eens een oplossing is bedacht, en dan wij dat inderdaad niet kunnen controleren, maar iedereen die hier mee doet weet zelf wel dat het veel leuker is zo'n algoritme zelf te bouwen, en daar het dan ook om.

Trouwens: als wij erachter komen dat een oplossing gecopy past is (en wij hebben ook internet + zoekmachine + gezond verstand), dan wordt die deelnemer gewoon gediskwalificeerd voor de rest van de wedstrijd .

Op maandag 03 december 2001 15:03 schreef MrX het volgende:
Ik lees nu net pas de rest van de thread en vind de opgave steeds flauwer worden. Ik zal geen spoilers geven, maar dit is kennelijk een zeer bekende puzzel waar all-over het net hinst en tips zijn te vinden die kunnen leiden tot een snel algoritme.

Omdat je geen gecontroleerde omgeving hebt (zoals op het NK proggen, waar je, in mijn tijd in ieder geval, geen toegang tot het internet had) kan iedereen zijn / haar voordeel doen door gewoon eens stevig te gaan zoeken.

Kunnen vervolgopdrachten niet-traditionele puzzels zijn? Anders wordt het meer een 'zoek-maar-raak-voor-een-knaak' wedstrijd.

edit:

Mijn algoritme is dus ranzig langzaam omdat het een eenvoudig back-tracking algoritme is, niet zo op dit probleem toegespitst.

Overigens zou niet pas halverwege een thread van +/- 21 x 25 = 525 posts een cruciale opmerking moeten staan dat de oplossing in 15 min. gevonden moet kunnen worden. Dergelijke info moet dan in de beginpost erbij gezet worden.

Je algoritme draait nu 48 min en 55 seconden, als de goede uitkomst er nog uit komt is ie gewoon goed. 15 min was gezegd in combinatie met een andere foutmelding op dezelfde inzending. Lees maar eens goed, we hebben geen limiet, maar als een programma op 1 invoer foute uitvoer geeft en op het 2e 15 min doet dan kan het niet goed zijn. Daarentegen als een programma op kleine grids snel en goed is en het op grote grids wat langer doet vinden we dat heus niet erg. Wel de thread goed bijhouden .

[LuCarD]

Op maandag 03 december 2001 15:03 schreef MrX het volgende:
Ik lees nu net pas de rest van de thread en vind de opgave steeds flauwer worden. Ik zal geen spoilers geven, maar dit is kennelijk een zeer bekende puzzel waar all-over het net hinst en tips zijn te vinden die kunnen leiden tot een snel algoritme.

Hoe zo is dat een spoiler, programmeren is meer al alleen code kloppen of algoritme bedenken. Het is ook onderzoek doen lezen, proberen, vallen . En als je goed zoekt vindt je hele leuke dingen.

Omdat je geen gecontroleerde omgeving hebt (zoals op het NK proggen, waar je, in mijn tijd in ieder geval, geen toegang tot het internet had) kan iedereen zijn / haar voordeel doen door gewoon eens stevig te gaan zoeken.

Nooit mogelijk, tenzij je de mogelijkheid hebt om mensen af te sluiten van het internet?

Kunnen vervolgopdrachten niet-traditionele puzzels zijn? Anders wordt het meer een 'zoek-maar-raak-voor-een-knaak' wedstrijd.

Nou ja misschien een aantal voorstellen?

Ik heb er anders wel eentje:

Je kent die kubus'n toch wel, van die "snuzzle puzzle's". Dat zijn van die schuimrubber kubus'n die je uit elkaar kan halen. Dan is bv het idee... Wij krijgen een 6 tal kubus stukjes en ga maar lekker bouwen. En dan een misschien een tweetal bonus punten als je ook nog de grootte kubus kan bouwen?

[wasigh]

Op het NK mag je tegenwoordig ook geen i-net gebruiken. Wel alle boeken etc.

Wat voor eergevoel heb je als je een oplossing copy & paste

verder is het een wedstrijd vooral om van te leren en voor de gezelligheid.

[Crysania]

Op maandag 03 december 2001 15:18 schreef LuCarD het volgende:
........

Ik heb er anders wel eentje:

Je kent die kubus'n toch wel, van die "snuzzle puzzle's". Dat zijn van die schuimrubber kubus'n die je uit elkaar kan halen. Dan is bv het idee... Wij krijgen een 6 tal kubus stukjes en ga maar lekker bouwen. En dan een misschien een tweetal bonus punten als je ook nog de grootte kubus kan bouwen?

NEEE niet die kubusen, daar ben in ZO ontiegelijk slecht in, ik heb een keer een avond lang met die dingen liggen te kloten had ik er nog geen goed pas toen ik op de brute force manier deed kreeg ik een "soort kubusjes"

[LuCarD]

Helemaal mee eens....

Ik heb al heel veel geleerd......

ben er bevoorbeeld al achter gekomen als je een PHP functie 16778 keer recrusief aanroept dat hij dan crasht

Of ik doe het gewoon fout.... (Zou goed kunnen ik had ook al een memory leak van ruim 200 Mb)

[Verwijderd]

/me grijnst

Sorry, misschien kom ik wat te kritisch over. Ik waardeer de wedstrijd en vind het een leuke gelegenheid om eens mijn hersens aan het werk te zetten. Dus neem mijn kritiek met een stevige korrel zout, want ik vind het gewoon leuk.

Als je programmeert in de praktijk moet je natuurlijk gebruik maken van de kennis die al door anderen is opgedaan (denk aan het wiel), maar in een wedstrijd is het leuk om binnen een gecontroleerde omgeving op eigen kracht een prestatie te leveren en die te meten aan die van anderen. Als wedstrijd is het inderdaad gewoon moeilijk te reguleren vanwege eerder genoemde redenen, dus ik zal het vanaf nu ook meer als hobby projecten beschouwen en niet zozeer als wedstrijd.

Ik kan me herinneren dat Wasigh ooit een link naar een PDFje met een aantal opgaven van het NK programmeren heeft gepost, en daar heb ik er een paar van opgelost voor de lol. Zo mag bijvoorbeeld het 'Folding problem' (opgave 8; Wasigh had daarvoor een krat bier als prijs in vooruitzicht gesteld) best een volgende opgave zijn. En nee, ik hed daar nog geen oplossing voor.

Kortom, complimenten aan de organisatoren, zal niet meer zo kritisch zijn en voor de gezelligheid meedoen.

[Verwijderd]

[D2k]

Op maandag 03 december 2001 15:41 schreef MrX het volgende:
/me grijnst

Sorry, misschien kom ik wat te kritisch over. Ik waardeer de wedstrijd en vind het een leuke gelegenheid om eens mijn hersens aan het werk te zetten. Dus neem mijn kritiek met een stevige korrel zout, want ik vind het gewoon leuk.

Als je programmeert in de praktijk moet je natuurlijk gebruik maken van de kennis die al door anderen is opgedaan (denk aan het wiel), maar in een wedstrijd is het leuk om binnen een gecontroleerde omgeving op eigen kracht een prestatie te leveren en die te meten aan die van anderen. Als wedstrijd is het inderdaad gewoon moeilijk te reguleren vanwege eerder genoemde redenen, dus ik zal het vanaf nu ook meer als hobby projecten beschouwen en niet zozeer als wedstrijd.

kritiek is nooit weg
maar op de manier zoals wij het doen is het niet af te dekken dat mensen i-net en collega's enz enz gebruiken
en das niet erg
daar wordt van geleerd

Ik kan me herinneren dat Wasigh ooit een link naar een PDFje met een aantal opgaven van het NK programmeren heeft gepost, en daar heb ik er een paar van opgelost voor de lol. Zo mag bijvoorbeeld het 'Folding problem' (opgave 8; Wasigh had daarvoor een krat bier als prijs in vooruitzicht gesteld) best een volgende opgave zijn. En nee, ik hed daar nog geen oplossing voor.

Kortom, complimenten aan de organisatoren, zal niet meer zo kritisch zijn en voor de gezelligheid meedoen.

hmmz
wasigh: als je er een tray red bull van maak ga ik het ook nog wel eens proberen

tnx voor het compliment iig

[wasigh]

Gelukkig

(krat bier staat nog steeds btw tray red bull vind ik ook goed hoor )

[wasigh]

<center><h2><font color="red">Belangrijk</font></h2></center>
<hr>
Opgave 2 zal vanavond omstreeks 21:00 verschijnen. Opgave 1 loopt tot vanavond 24:00
<hr>
<marquee><center><h2><font color="red">Belangrijk</font></h2></center></marquee>

[drm]

Op maandag 03 december 2001 16:17 schreef wasigh iets belangrijks

aiaiaiai, meine augen!

[D2k]

Op maandag 03 december 2001 16:21 schreef drm het volgende:

[..]

aiaiaiai, meine augen!

lol

hoezo HTML rechten misbruik

[Crysania]

Op maandag 03 december 2001 16:17 schreef wasigh iets walgelijk roods.

dat is echt lelijk

[D2k]

Op maandag 03 december 2001 16:29 schreef THE_CR0SS het volgende:

[..]

dat is echt lelijk

maar je kan niet zeggen dat je het niet gezien hebt

[Verwijderd]

Hmm, ivm die parameter op de commandolijn : nee, ik bedoel niet pipen. Mijn prog is nu gemaakt dat ie zelf een file opent (en de naam van die file is dus de parameter die je op de command line meegeeft) en uit die file de data inleest; dus niet dat ie input van de stdin haalt...
Eigenlijk had ik niet eens gedacht aan pipen

Naja, ik zal nog zien of ik vanavond nog ergens een half uurtje tijd heb om 't aan te passen, anders is 't jammer en blijft het bij wat nuttig tijdverdrijf

En verder : mijn programma (en bijhorend algoritme) is door mezelf ontwikkeld tot de laatste bit, en is een perfecte weerspiegeling van hoe ik het als mens zou oplossen (zo vond ik 't algo dus : gewoon een paar kleine puzzels proberen met de hand, en zien wat ik als mens uitvreet ). Daar leer je 't meeste van, en je kan dan met trots zeggen dat je iets hebt bereikt als 't werkt Mja, zoals iemand al zei : een kwestie van eer he.
I don't care als Xalista z'n prog sneller is of beter of minder geheugen gebruikt of weet ik veel. Ik wou gewoon eens zien wat IK er van bakte. We zullen morgen dan wel van hem (of anderen) leren hoe het echt moet

Btw Xalista : razend snel dingetje heb je daar gemaakt, respect terug...

[Unicron]

Helaas heb ik vanwege mijn tentamenweek geen tijd gehad om een programma te schrijven. Ik heb wel een algoritme bedacht, dus ik ben benieuwd hoe de andere het hebben gedaan.
Maar ik ga zeker meedoen aan de tweede opgave. Kan ik weer eens oefenen met C en C++.;)

En ik vind het niveau van de opdrachten trouwens wel goed. Het is tenminste niet zo makkelijk dat je in een middagje klaar bent. Ook het idee achter de opdracht van het verzinnen van een algoritme vind ik goed. Dus ga zo door

[Twilight Burn]

Op maandag 03 december 2001 17:39 schreef _piranha_ het volgende:
Hmm, ivm die parameter op de commandolijn : nee, ik bedoel niet pipen. Mijn prog is nu gemaakt dat ie zelf een file opent (en de naam van die file is dus de parameter die je op de command line meegeeft) en uit die file de data inleest; dus niet dat ie input van de stdin haalt...
Eigenlijk had ik niet eens gedacht aan pipen

Naja, ik zal nog zien of ik vanavond nog ergens een half uurtje tijd heb om 't aan te passen, anders is 't jammer en blijft het bij wat nuttig tijdverdrijf

En verder : mijn programma (en bijhorend algoritme) is door mezelf ontwikkeld tot de laatste bit, en is een perfecte weerspiegeling van hoe ik het als mens zou oplossen (zo vond ik 't algo dus : gewoon een paar kleine puzzels proberen met de hand, en zien wat ik als mens uitvreet ). Daar leer je 't meeste van, en je kan dan met trots zeggen dat je iets hebt bereikt als 't werkt Mja, zoals iemand al zei : een kwestie van eer he.
I don't care als Xalista z'n prog sneller is of beter of minder geheugen gebruikt of weet ik veel. Ik wou gewoon eens zien wat IK er van bakte. We zullen morgen dan wel van hem (of anderen) leren hoe het echt moet

Btw Xalista : razend snel dingetje heb je daar gemaakt, respect terug...

Dan los jij zo'n puzzel waarschijnlijk anders op dan ik dat zou doen
En idd, het gaat om de lol, ik had eerst nooit gedacht dat ik hiervoor een oplossing zou kunnen bedenken, maar het is me toch gelukt

[Verwijderd]

Op maandag 03 december 2001 17:57 schreef Unicron het volgende:
Het is tenminste niet zo makkelijk dat je in een middagje klaar bent.

Ik was toch echt klaar op een zondagavond hoor (gisteren dus)
Denk dat ik er in totaal een uur of 4 aan gewerkt heb. Maar ik moet toegeven : de code is er ook naar Qua structuur en OO principes moet ze zowat tegen alle regels ingaan denk ik Maar dan moeten ze maar 2 weken per contest geven, ik heb namelijk niet elke week een dag de tijd om te proggen. Och ja, who cares about the beauty prize, zolang we de zooi werkend krijgen en iets bijleren...

Maar je hebt gelijk : het niveau is niet bepaald laag, d'er is tenminste nog een uitdaging met de opgaves. Ik deed ooit mee aan een C programmeerwedstrijd, maar daar waren de opgaves nogal zielig. Stel je voor : als je al 4 opgaves kunt maken in minder dan 2 uur... duh. Naja, dan toch maar deze, no doubt...

[Marcj]

Op maandag 03 december 2001 18:13 schreef _piranha_ het volgende:

[..]

Ik was toch echt klaar op een zondagavond hoor (gisteren dus)
Denk dat ik er in totaal een uur of 4 aan gewerkt heb. Maar ik moet toegeven : de code is er ook naar Qua structuur en OO principes moet ze zowat tegen alle regels ingaan denk ik Maar dan moeten ze maar 2 weken per contest geven, ik heb namelijk niet elke week een dag de tijd om te proggen. Och ja, who cares about the beauty prize, zolang we de zooi werkend krijgen en iets bijleren...

Maar je hebt gelijk : het niveau is niet bepaald laag, d'er is tenminste nog een uitdaging met de opgaves. Ik deed ooit mee aan een C programmeerwedstrijd, maar daar waren de opgaves nogal zielig. Stel je voor : als je al 4 opgaves kunt maken in minder dan 2 uur... duh. Naja, dan toch maar deze, no doubt...

Hier ben ik het mee eens. Eindelijk een moeilijk probleem. Het probleem van mij is eig alleen dat ik wel een algoritme kan bedenken, maar om dat ook nog goed in een programeertaal te schrijven wordt een groter probleem. Daarom ben ik er ook wat langer mee bezig

_{Volgens mij zijn dat geen goede zinnen ofwel}

[Twilight Burn]

Hier ben ik het mee eens. Eindelijk een moeilijk probleem. Het probleem van mij is eig alleen dat ik wel een algoritme kan bedenken, maar om dat ook nog goed in een programeertaal te schrijven wordt een groter probleem. Daarom ben ik er ook wat langer mee bezig

Yup, eindelijk een moeilijker probleem, das een uitdaging, en het leuke ervan Op school (ben nu eerstejaars Informatica student op de TU/e) waren de opdrachten die we kregen allemaal veel te makkelijk

_{Volgens mij zijn dat geen goede zinnen ofwel}

Je zinnen waren trouwens wel goed (of mijn Nederlands is ook erg slecht )

[Verwijderd]

Op maandag 03 december 2001 18:25 schreef Twilight Burn het volgende:

[..]

Yup, eindelijk een moeilijker probleem, das een uitdaging, en het leuke ervan Op school (ben nu eerstejaars Informatica student op de TU/e) waren de opdrachten die we kregen allemaal veel te makkelijk
[..]

[Schoolmeester mode]

Ik ben nu 5de jaars informatica op de TU/e en jij hebt toch een wat verkeerd beeld van die opleiding geloof ik. Het doel daar is niet om jou allerlei moeilijke problemen voor te leggen en je dan uit te leggen hoe je ze et beste kunt oplossen, maar ze leren je daar hoe je zelf kan bedenken hoe je ze et beste oplost. Ze leren je daar ontwerpen, niet programmeren en al helemaal niet coderen. Ze leren je daar abstraheren, zodat je als je zo'n b.v. Japanse Puzzel moet oplossen, je niet meer denkt in termen van puzzels en hoe je dat met de hand zou oplossen, maar in termen van datastructuren en standaard algoritmen.

Ik zie hier geen Japanse Puzzel, ik zie een 2d array dat ik zo moet vullen dat het aan bepaalde eisen voldoet. Dan denk ik dus gelijk aan backtracken, recursie en invarianten. Dan denk ik aan een soort early out mechanisme en dus aan een branch-and-cut strategie. Als je eenmaal zover bent is het scelet van je code al klaar (want dat is dus gewoon een standaard algoritme) je hoeft dan alleen nog wat dingen in te vullen, b.v. een mechanisme dat de invarianten in stand houdt.

IK vond de opleiding informatica aan de TU/e niet zo moeilijk, maar ik kan je wel vertellen dat je dat niet op basis van het eerste trimester van het eerste jaar kunt zeggen. Wacht maar tot je programmeren 2 voor je kiezen krijgt, daar heb ik er veel op zien sneuvelen... Dan wordt er dus geen code meer in elkaar gehackt, maar dan zul je van elke statement in je programma moeten bewijzen dat ie goed is en daar hoort.

O ja, je krijgt daar vast nog wel ooit zo'n gevoel van:
"Ok, ik heb nu dit en dit vak gehad, en ik kan een beetje lambda calculus en ik weet waarom bepaalde problemen inherent moeilijk zijn enzo, maar wat KAN ik nu eigenlijk???" Antwoord: abstraheren. Ben je C-expert? nee. Ben je database-expert? nee. Ben je überhaupt ergens expert in? Nee, maar dat kun je nu wel allemaal makkelijker worden.

[/Schoolmeester mode]

Het is een beetje een zeikerig, betweterig verhaal geworden, nauwelijks waard om gepost te worden, maar het is zonde van de moeite om het niet te doen...

[Unicron]

Ik zit ook op de TU/E
2e jaars elektrotechniek

[Nikel]

Goed ik ga nu ook maar eens beginnen, ik zie dit topic pas net, ik heb nog tot 23:59?

[D2k]

Op maandag 03 december 2001 19:51 schreef Nikel het volgende:
Goed ik ga nu ook maar eens beginnen, ik zie dit topic pas net, ik heb nog tot 23:59?

jepz

[Nikel]

Kan de deadline niet nog wat naar achteren?

[D2k]

Op maandag 03 december 2001 19:58 schreef Nikel het volgende:
Kan de deadline niet nog wat naar achteren?

noopz

[Verwijderd]

Op maandag 03 december 2001 19:51 schreef Nikel het volgende:
Goed ik ga nu ook maar eens beginnen, ik zie dit topic pas net, ik heb nog tot 23:59?

Yep, en als je aan hetzelfde tempo van mij werkt, haal je dat net...of net niet als je ook nog wat wilt testen
Zet 'm op en coden voor dood zou ik zeggen

[Nikel]

M'n visual cafe loopt de hele tijd vast, dus ik kan het in php gaan doen of helemaal niet doen...

Stdin lezen met php heb ik nog nooit gedaan maar het kan vast...

[Dash2in1]

Op maandag 03 december 2001 20:11 schreef Nikel het volgende:
M'n visual cafe loopt de hele tijd vast, dus ik kan het in php gaan doen of helemaal niet doen...

Stdin lezen met php heb ik nog nooit gedaan maar het kan vast...

Gewoon tekstbestandje? Werkt ook wel hoor

[Twilight Burn]

Ik ben nu 5de jaars informatica op de TU/e en jij hebt toch een wat verkeerd beeld van die opleiding geloof ik. Het doel daar is niet om jou allerlei moeilijke problemen voor te leggen en je dan uit te leggen hoe je ze et beste kunt oplossen, maar ze leren je daar hoe je zelf kan bedenken hoe je ze et beste oplost. Ze leren je daar ontwerpen, niet programmeren en al helemaal niet coderen. Ze leren je daar abstraheren, zodat je als je zo'n b.v. Japanse Puzzel moet oplossen, je niet meer denkt in termen van puzzels en hoe je dat met de hand zou oplossen, maar in termen van datastructuren en standaard algoritmen.

Ik wil ook helemaal niet precies uitgelegd krijgen hoe je een bepaalde opdracht op moet lossen, want dan is de lol er snel af, ik heb ook al lang door dat als je eenmaal weet hoe je iets moet doen, dat de implementatie erg makkelijk is. (In het begin wilde men programma niet helemaal werken, maar dat kwam ook dat ik een klein detail dat ik wel in men ontwerp had gezet over het hoofd heb gezien tijdens het programmeren)

Ik zie hier geen Japanse Puzzel, ik zie een 2d array dat ik zo moet vullen dat het aan bepaalde eisen voldoet. Dan denk ik dus gelijk aan backtracken, recursie en invarianten. Dan denk ik aan een soort early out mechanisme en dus aan een branch-and-cut strategie. Als je eenmaal zover bent is het scelet van je code al klaar (want dat is dus gewoon een standaard algoritme) je hoeft dan alleen nog wat dingen in te vullen, b.v. een mechanisme dat de invarianten in stand houdt.

IK vond de opleiding informatica aan de TU/e niet zo moeilijk, maar ik kan je wel vertellen dat je dat niet op basis van het eerste trimester van het eerste jaar kunt zeggen. Wacht maar tot je programmeren 2 voor je kiezen krijgt, daar heb ik er veel op zien sneuvelen... Dan wordt er dus geen code meer in elkaar gehackt, maar dan zul je van elke statement in je programma moeten bewijzen dat ie goed is en daar hoort.

Van een stel van die dingen die je daar noemt weet ik niet/maar half wat ze zijn, maar goed, als je alles al weet dan hoef je de studie ook niet te gaan doen.
Wat ik eigenlijk met makkelijk/niet moeilijk bedoelde is dat dat ik tot nu toe gehad heb niet erg moeilijk was, of een grote uitdaging was. En ik weet van mezelf dat dat niet goed voor me is, omdat als ik niets/weinig hoef te doen daar erg lui van wordt, en daardoor steeds minder ga doen, enzovoorts...

[Verwijderd]

God damnit, om 21 uur begint ook Friends...

Wat nu

[D2k]

Op maandag 03 december 2001 20:37 schreef Xalista het volgende:
God damnit, om 21 uur begint ook Friends...

Wat nu

coden natuurlijk

[Nikel]

Het lukt me al niet eens om de invoer te parsen met java .

[JeroenE]

ben er bevoorbeeld al achter gekomen als je een PHP functie 16778 keer recrusief aanroept dat hij dan crasht

Hm, ik ken geen PHP, maar het is wel een 'bekend' getal. Kijk maar eens naar de eerste 5 cijfers van 16Mb. Is dit niet ergens een limiet van PHP ofzo?

[Unicron]

Dat van bewijzen van je code met invarianten heb ik ook gehad. Dat kan nog best vies tegenvallen kan ik je vertellen. Maar GCL heeft ook zo z'n voordelen. Je kunt programma's bijvoorbeeld zeer efficient maken door het versterken van invarianten, terwijl je nog zeker weet dat de code goed werkt

[Crysania]

nog een paar minuten voor de nieuwe opgave, gelijk beginnen, heb ik een voorsprong op diegene die nog aan opgave 1 bezig zijn

[razor-x]

21.00 uur!!!!! nieuwe opgave!

/edit
21.01 zelfs

[D2k]

*zucht*

Belangrijk


--------------------------------------------------------------------------------

Opgave 2 zal vanavond omstreeks 21:00 verschijnen. Opgave 1 loopt tot vanavond 24:00

--------------------------------------------------------------------------------

Belangrijk

[Crysania]

omstreeks betekend zeker "niet meteen"?

[Verwijderd]

Hmm, we kunnen het toch niet laten
[smal] 'k zal wel een freak zijn zeker [/smal]

Euh Xalista : about your timing info... Van wanneer tot wanneer time je ? Ik bedoel : time je het eigenlijke oplossen NADAT je een en ander 'initialiseerde' (wat dan bvb wel 20 seconden kan duren ) tot de oplossing of time je van zodra alle input er is, tot je iets hebt dat je kan tonen op het scherm ?
In het eerste geval : dan zit ik dus ook in de milliseconden range, anders zogezegd dus iets langer ('k heb je 32x30 uitdaging nu wel op 22 seconden gekregen ipv de 2+ minuten gisteren ).
Is het dat laatste bij jou : want dat haal ik nooit vrees ik... 'k ben benieuwd !!

[edit] Hoe zet je tekst zo klein

[Verwijderd]

Op maandag 03 december 2001 20:57 schreef THE_CR0SS het volgende:
nog een paar minuten voor de nieuwe opgave, gelijk beginnen, heb ik een voorsprong op diegene die nog aan opgave 1 bezig zijn

voorsprong ? ik dacht het niet er zijn al een aantal die 1 af hebben

[Dash2in1]

Op maandag 03 december 2001 20:39 schreef Nikel het volgende:
Het lukt me al niet eens om de invoer te parsen met java .

Al gezocht op GoT? Vast wel wat te vinden .. anders nieuwe topic starten oid (Overigens niet al te moeilijk)

[Nikel]

Nee het is niet al te moeilijk, maar ik ben ook niet al te niet-lui, ik heb het trouwens opgegeven, als ik een week de tijd had gehad had ik er wel wat van gemaakt, maar zo heb ik er geen zin in . Ik ga de tweede opgave wel doen.

[Verwijderd]

Op maandag 03 december 2001 21:03 schreef _piranha_ het volgende:
Hmm, we kunnen het toch niet laten
'k zal wel een freak zijn zeker

Euh Xalista : about your timing info... Van wanneer tot wanneer time je ? Ik bedoel : time je het eigenlijke oplossen NADAT je een en ander 'initialiseerde' (wat dan bvb wel 20 seconden kan duren ) tot de oplossing of time je van zodra alle input er is, tot je iets hebt dat je kan tonen op het scherm ?
In het eerste geval : dan zit ik dus ook in de milliseconden range, anders zogezegd dus iets langer ('k heb je 32x30 uitdaging nu wel op 22 seconden gekregen ipv de 2+ minuten gisteren ).
Is het dat laatste bij jou : [afbeelding] want dat haal ik nooit vrees ik... 'k ben benieuwd !!

Mijn initialisatie is maar 10 miliseconden dus dan kom ik in totaal op 70 miliseconden. Maar nogmaals, als ik m'n code aanpas zodat ie die moeilijke puzzel in 70 miliseconden doet, doet ie andere opgaven weer trager.

[Marcj]

Op maandag 03 december 2001 21:03 schreef _piranha_ het volgende:
[edit] Hoe zet je tekst zo klein

code:

[sub][/sub]

_{1000ste post!!}

Ik heb mijn kreupele oplossing ook maar ingestuurd omdat ik er niet langer aan kan werken. Ik hoop dat ik er nog een puntje voor krijg (voor de poging )

[dusty]

Ik ben pas terug van mijn lange weekend naar Gran Dorado

Dus nee, ik ben geen competitie (niet ingestuurd.. gewoon weg geen tijd gehad..)

Ik zal morgen-avond wel even mijn gedachten optikken over deze opgave hoe ik de oplossing in mijn hoofd heb zitten.

[raptorix]

Ik ook niet, was redelijk op weg maar had gister sinterklaas en vandaag geen zin

[CrazyA]

Ik heb deze thread met veel belangstelling gevolgt. Helaas heb ik zelf niet zo 1 2 3 de kwaliteiten in huis om mee te doen (ook de tijd niet trouwens ). Ik ben toch wel erg nieuwsgierig wat men er van gebakken heeft.

Ik kan haast niet wachten tot de oplossingen te zien/zelf te proberen zijn. En natuurlijk source bekijken en hopen dat ik er zelf wat van kan leren

[Twilight Burn]

De deadline is voorbij:
De source/binaries (VB.Net)
De beschrijving/het ontwerp (Word document)
Het ontwerp is niet echt geweldig geschreven (vinnik) dus als er vragen zijn beantwoord ik die graag

[Verwijderd]

Met veel nieuwsgierigheid jou methode ff gelezen, en in essentie komt die van mij op hetzelfde neer. De beginaanpak (zoeken naar vakjes die zeker aan of uit staan) doe ik ook, als zal het wel iets anders geimplementeerd zijn (want ik heb 't in C++ gedaan). Als ie vastloopt doe ik het iets anders (ik vul een volledige rij in per hint en kijk of daar iets van komt, zoniet probeer ik dan een andere mogelijkheid van die rij etc)...
Ik denk dus dat er nog wel zijn die deze methode gebruiken, omdat je 't als mens ook zo doet in essentie...

Nu Xalista z'n methode ff bekijken als ie ze een dezer dagen openbaar wil maken Ben echt benieuwd !!

[Verwijderd]

Hier is een zipfile met mijn code en exe. Ik heb nog geen tijd gehad om een verhaaltje te schrijven, maar dat komt denk ik nog wel. De code is wel zéér uitgebreid beschreven, daar staat eigenlijk al een soort verhaaltje in.

http://members.chello.nl/~r.nas/JapansePuzzel.rar

[tomato]

The requested URL /~r.nas/JapansePuzzel.zip was not found on this server.

[edit] Hij doet het al

[CrazyA]

Ik ben nu meteen begonnen met download, maar ik heb mscoree.dll niet
Ook een snelle Google-poging leverde niet veel op.
Wie heeft er ff snel een linkje voor mij ?

[tomato]

Crazy A: Ik ben nu meteen begonnen met download, maar ik heb mscoree.dll niet
Ook een snelle Google-poging leverde niet veel op.
Wie heeft er ff snel een linkje voor mij ?

Je zult het .NET Framework moeten installeren.

[Verwijderd]

Ik weet niet of jullie er hier op zitten te wachten, maar misschien hebben jullie P&W-ers hier meer kennis van, of ervaring mee, dan wij nederige W&G-ers

Pelle had naar aanleiding van dit topic een beetje geklust aan een soort van Paint, maar dan online, en puur javascript.

Het onhandige geheugenbeheer, en het omslachtige javascript, zorgen ervoor dat bij grote aantallen recursieve functies stack-overflow's optreden. Is er een manier om dit efficiënter op te lossen?

(Ik bedoel: jullie zijn nu waarschijnlijk toch bezig met recursieve functies...)

[CrazyA]

Op dinsdag 04 december 2001 00:21 schreef tomato het volgende:

[..]

Je zult het .NET Framework moeten installeren.

Dat .NET klinkt heel erg vies

Maar er staat een linkje, een heel stuk terug, maar die werkt dus niet meer
Niemand zo lief om ff die dll ergens te uppen ??

[tomato]

Crazy A: Dat .NET klinkt heel erg vies

.NET is juist heel erg mooi

Maar er staat een linkje, een heel stuk terug, maar die werkt dus niet meer
Niemand zo lief om ff die dll ergens te uppen ??

Zoals ik al zei zul je het .NET Framework moeten installeren, aan die dll heb je dus niets.
Je kunt het .NET Framework vast en zeker vrij gemakkelijk op de Microsoft website vinden.

[Twilight Burn]

Op dinsdag 04 december 2001 00:24 schreef Crazy A het volgende:

[..]

Dat .NET klinkt heel erg vies

Maar er staat een linkje, een heel stuk terug, maar die werkt dus niet meer
Niemand zo lief om ff die dll ergens te uppen ??

Alleen aan die DLL heb je niets, je moet er nog meer hebben... Ik had er een installer van willen maken, maar ik kon die functie niet meer vinden Trouwes, die link ( http://msdn.microsoft.com/downloads/default.asp?url=/downloads/sample.asp?url=/msdn-files/027/000/976/msdncompositedoc.xml ) doet het nog steeds

[CrazyA]

Op dinsdag 04 december 2001 00:32 schreef Twilight Burn
een grote link

Die heb ik al beklikt, maar er stond ook nog ergens een linkje naar alleen het URLetje... maargoed... dan het hele pakket maar...

[Twilight Burn]

Op dinsdag 04 december 2001 00:44 schreef Crazy A het volgende:

[..]

Die heb ik al beklikt, maar er stond ook nog ergens een linkje naar alleen het URLetje... maargoed... dan het hele pakket maar...

dat klopt maar omdat dat bestand alleen niet genoeg was heb ik ut maar weggegooid op de server (zal nu ff de link verwijderen )
[edit - ik mag die link daarboven niet meer weggooien, meer dan 24 uur geleden dat ik die gepost heb, naja]

[CrazyA]

Ik ben 'm nu al aan het downen... het schiet alleen niet op (60KB/s kloteserver dus)

Maar ik moet zeggen dat hier hele mooie dingen gebeurt zijn. Nu alleen nog ff de algoritmes snappen

Ik ben druk bezig met bestuderen

Great work guys !!

[Theswitch]

Hoi.. Ik zie pas net deze programming contest.. Maar zo'n beeldzoeker programma heb ik zelf al eens in februari 1999 gescrheven voor de grap.. in perl, en hij werkt met 3 kleuren, waarbij een negatief getal voor rood staat ipv zwart.

Je kan 'm
http://medz.org/beeldzoeker.tar.gz
daar vinden.

Het is in perl geschreven, en het formaat wijkt een beetje af van deze opgave (met komma's). Maar hij vind ze wel allemaal gegarandeerd.

[Verwijderd]

Op dinsdag 04 december 2001 00:55 schreef Crazy A het volgende:
Maar ik moet zeggen dat hier hele mooie dingen gebeurt zijn. Nu alleen nog ff de algoritmes snappen

Ik ben druk bezig met bestuderen

Hehe, succes ermee

Great work guys !!

Tnx En nu ik weet dat mijn prog is goedgekeurd door de jury (kreeg vanmorgen mailtje van D2k dat ie goed was) zal ik mijn code (C/C++) ook vrijgeven. Ik wil alvast waarschuwen : ze is qua OO principes en structuur een regelrechte ramp, maar je moet ze dan maar es wat herwerken Ander nadeel : ze is hard coded om te werken met een maximaal rooster van 32x32 (wel, niet echt 32, maar eigenlijk het aantal bits in een 'int') wat volstond voor de opgave. Had geen tijd (en eig ook geen zin) om het iets algemener te doen
Ik kan momenteel geen 'verhaaltje' schrijven door gebrek aan tijd, maar ik verwijs graag naar dat van Twilight Burn omdat het idee achter mijn prog ongeveer hetzelfde is. Er staat wel wat commentaar in mijn code; waarschijnlijk genoeg om uit te vissen wat er gebeurt, zeker als je het 't verhaal wat doorhebt.
Ik heb momenteel geen server draaien, dus ik kan 't niet hosten, maar wie 't echt wil moet maar es mailen ( [e-mail] ), dan mail ik 't wel door. (code + exe, in een zip, 98K)

Btw : heb net ff naar Xalista z'n methode gekeken, en die is eigenlijk veel te voor de hand liggend Het verbaasd me eigenlijk dat die zo gruwelijk snel is, omdat die - verbeter me als ik fout zit - in principe uitgaat van alle mogelijkheden van 'X' en '-' in zo'n rooster, ongeacht de gegeven 'patronen' voor een rij en/of kolom (dus voor een 10x10 rooster gaat het ding in principe uit van 2^(10x10) mogelijkheden). Ok, er wordt dan gecontroleerd of die bezetting mogelijk is, zodat je veel subtrees vrij snel 'knipt', maar dan nog. Daar moet ik dus nog eens over nadenken. Ten opzichte van zijn methode verlies ik dus gigantisch veel tijd door de alternatieven voor iedere rij en kolom op te bouwen, welke hij dus niet nodig heeft. Eenmaal ik die alternatieven heb (maar dat vraagt net de tijd), heb ik de oplossing 'voor het grijpen' (lees : in een paar milliseconden). Desondanks toch knap gedaan...

[edit] Laat maar, die opgave 2 is ondertussen geannuleerd merk ik net. Laten we hopen dat de nieuwe ook leuk wordt

[Marcj]

Op dinsdag 04 december 2001 00:03 schreef Twilight Burn het volgende:
De deadline is voorbij:
De source/binaries (VB.Net)
De beschrijving/het ontwerp (Word document)
Het ontwerp is niet echt geweldig geschreven (vinnik) dus als er vragen zijn beantwoord ik die graag

hmm, dat was mijn idee ook, alleen is mijn impementatie een beetje mislukt (zeg maar heel erg )

[Verwijderd]

Op dinsdag 04 december 2001 18:19 schreef _piranha_ het volgende:

[..]

Btw : heb net ff naar Xalista z'n methode gekeken, en die is eigenlijk veel te voor de hand liggend Het verbaasd me eigenlijk dat die zo gruwelijk snel is, omdat die - verbeter me als ik fout zit - in principe uitgaat van alle mogelijkheden van 'X' en '-' in zo'n rooster, ongeacht de gegeven 'patronen' voor een rij en/of kolom (dus voor een 10x10 rooster gaat het ding in principe uit van 2^(10x10) mogelijkheden). Ok, er wordt dan gecontroleerd of die bezetting mogelijk is, zodat je veel subtrees vrij snel 'knipt', maar dan nog. Daar moet ik dus nog eens over nadenken. Ten opzichte van zijn methode verlies ik dus gigantisch veel tijd door de alternatieven voor iedere rij en kolom op te bouwen, welke hij dus niet nodig heeft. Eenmaal ik die alternatieven heb (maar dat vraagt net de tijd), heb ik de oplossing 'voor het grijpen' (lees : in een paar milliseconden). Desondanks toch knap gedaan...

[..]

Jammer dat je niet onder de indruk bent van b.v. de eenvoud (en toch efficientie) van mijn programma. Ik hoop dat je wel inziet dat dat "knippen van een subtree" toch wel erg effient moet gebeuren als je ziet dat er in een binaire boom die in pricipe iets van 2^(35 * 45) ~ 1,3 * 10^474 knopen bevat (de kerstman puzzel) zoveel "geknipt" wordt dat die puzzel in minder dan 1 seconde wordt opgelost. Ik geef toe dat "slimme" oplossingen over het algemeen iets meer creativiteit vergen, maar dat betekent niet dat ze ook beter zijn. Daarnaast kun je ook veel creativiteit kwijt in het bedenken van een goede "knip"-strategie. Zo denk ik met wat meer moeite mijn algoritme nog wel te kunnen uitbreiden met een statische heuristiek om het zoekproces nog beter te sturen. Ik heb hier wel een eerste poging toe gedaan, maar dat gaf toen niet zoveel resultaat.

De indruk die ik van jouw algoritme krijg is de volgende:
Je gaat eerst m.b.v. slimme heuristiek een initiele oplossing bedenken, om vervolgens eventuele gaten in te vullen met een, niet zo erg efficiente, brute force methode. Jouw algoritme staat of valt dus met hoeveel geluk je hebt met die initiele oplossing. Ik denk dat een ideale oplossing jouw start oplossing met mijn bruteforce methode zou combineren.

[Theswitch]

Als je mijn oplossing leest (zie andere draadje over opgave 1), dan kan je lezen dat ik helemaal niks recursief doe, en het probleem gewoon linear aanpak. Daardoor heb ik ook niks te maken met 2^..., dat komt niet voor in mijn programma. Het enige rekenwerk wat er echt inzit is alle permutaties voor een bepaalde rij tegen een bepaalde mask bepalen.

[Dash2in1]

Op dinsdag 04 december 2001 00:03 schreef Twilight Burn het volgende:
De deadline is voorbij:
De source/binaries (VB.Net)
De beschrijving/het ontwerp (Word document)
Het ontwerp is niet echt geweldig geschreven (vinnik) dus als er vragen zijn beantwoord ik die graag

Wat we al dachten, ongeveer het zelfde aangepakt Alleen gebruik geen recursie in me programma.. en de mijne is denk ik stukje trager..

[Verwijderd]

Op dinsdag 04 december 2001 19:25 schreef Theswitch het volgende:
Als je mijn oplossing leest (zie andere draadje over opgave 1), dan kan je lezen dat ik helemaal niks recursief doe, en het probleem gewoon linear aanpak. Daardoor heb ik ook niks te maken met 2^..., dat komt niet voor in mijn programma. Het enige rekenwerk wat er echt inzit is alle permutaties voor een bepaalde rij tegen een bepaalde mask bepalen.

Ik zal idd eens naar je programma kijken, omdat het toch een heeeel andere aanpak is dan wat ik tot nu toe heb gehoord. Het enige is wel dat permutaties zo mogelijk nog erger zijn dan machten van 2....
En het lijkt me ook dat je toch op een of andere manier voor een hoop combinaties van rijen moet testen of ze samen niet met de info over kolommen conflicteren.

edit:

En dat laatste doe je dus door kolommen ook met zo'n mask te matchen. Mooie oplossing. Alleen heb je voor opgaven met meerdere oplossingen nog wel een bruteforce nodig om de gaten in te vullen. Daar zou mijn methode dan weer mooi in passen.

[markvt]

toch leuk om die oplossingen te bekijken, khad er zelf geen tijd voor.

[Theswitch]

Op dinsdag 04 december 2001 19:30 schreef Xalista het volgende:

[..]

edit:

En dat laatste doe je dus door kolommen ook met zo'n mask te matchen. Mooie oplossing. Alleen heb je voor opgaven met meerdere oplossingen nog wel een bruteforce nodig om de gaten in te vullen. Daar zou mijn methode dan weer mooi in passen.

Mijn oplossing ging uit van 1 unieke oplossing, anders blijft ie "rondjes" lopen . Let wel op dat m'n code vrij "onoverzichteljk" is, je moet wel echt iets van perl snappen om 't te kunnen volgen. Maar doe je best zuo ik zeggen

[Verwijderd]

Op dinsdag 04 december 2001 19:23 schreef Xalista het volgende:
Jammer dat je niet onder de indruk bent van b.v. de eenvoud (en toch efficientie) van mijn programma. Ik hoop dat je wel inziet dat dat "knippen van een subtree" toch wel erg effient moet gebeuren als je ziet dat er in een binaire boom die in pricipe iets van 2^(35 * 45) ~ 1,3 * 10^474 knopen bevat (de kerstman puzzel) zoveel "geknipt" wordt dat die puzzel in minder dan 1 seconde wordt opgelost.

Euh, ik ben juist wel onder de indruk! Het verbaast me net dat zo'n eenvoudige aanpak toch zo gruwelijk snel kan zijn, zoals ik hierboven ook al zei. Je moet inderdaad al snel en erg veel gaan snoeien om dat zo snel op te lossen! En daar moest ik dus nog ff over nadenken, omdat ik dat in je code niet meteen doorheb. Je lijkt - once again, correct me if I'm wrong - gewoon rij per rij af te gaan, en per rij die je controleert ga je gewoon de kolommen sequentieel af, en je probeert eens of een 'X' lukt, en zo niet, probeer je eens een ' '. Dat lijkt me niet echt HEEL GERICHT massaal gaan snoeien, en dat is net waarom ik (nog) niet doorheb waarom die zo eenvoudige aanpak zo damn fast is...
Maar laat er geen twijfel over bestaan : respect voor jou oplossing ! Je bewijst dat een eenvoudige maar op het eerste en tweede gezicht bijzonder onefficiente oplossing toch goed kan werken. Ik zal dus in het vervolg 3 keer moeten kijken
Of zoals Enzo Ferrari ooit zei (dacht toch dat hij het was) : geniaal eenvoudig; eenvoudig geniaal

Ik geef toe dat "slimme" oplossingen over het algemeen iets meer creativiteit vergen, maar dat betekent niet dat ze ook beter zijn.

Ben ik met je eens... jij bewijst het trouwens

De indruk die ik van jouw algoritme krijg is de volgende:
Je gaat eerst m.b.v. slimme heuristiek een initiele oplossing bedenken, om vervolgens eventuele gaten in te vullen met een, niet zo erg efficiente, brute force methode. Jouw algoritme staat of valt dus met hoeveel geluk je hebt met die initiele oplossing. Ik denk dat een ideale oplossing jouw start oplossing met mijn bruteforce methode zou combineren.

Euh nee, je hebt een beetje een verkeerde indruk denk ik, maar dat heeft wel te maken met het feit dat ik niet helemaal zoals Twilight Burn werk (zo heb ik het toch voor, en net in dat verschil zit de winst denk ik)...
Net zoals Twilight Burn ga ik idd eerst mbv een slimme heuristiek een initiele oplossing bedenken. Mochten er dan nog gaten zijn (wat niet altijd zo is), dan ga ik een 'smart brute force' aanwenden. Dat is zeker geen brute force, maar een pak efficienter. Het komt er op neer dat ik, zoals jij ook doet, er dan een rij uitpik die nog niet volledig gekend is. Ik probeer dan inderdaad elke mogelijkheid van die rij uit die nog kan voldoen (ik heb alle mogelijke alternatieven hiervoor die aan het patroon van de rij voldoen nl vooraf bepaald). Ik vul dus de rij in kwestie in 1 keer volledig in. En dan probeer ik weer de heuristiek ipv recursief brute force verder te doen. Dat is in feite een speciale 'branch and bound' methode, dus een beetje in de trend van wat jij doet... Alleen is mijn zoekboom dan al heel sterk herleid, nl tot een zoekboom die per definitie voldoet aan de gegeven patronen voor de rijen en kolommen, en snoei ik in die resterende boom dus heel gericht...
Wat dus mijn conclusie is : de volledige zoekboom doorzoeken met een branch and bound zoals jij doet is dus efficienter dan eerst een _veel_ kleinere zoekboom bepalen en dan die doorzoeken (hetzij alleen met een heuristiek om heel snel en heel gericht te snoeien, hetzij met een minder gerichte snoeimethode zoals jij blijkbaar vanin het begin doet). En dat vind ik toch wel een beetje vreemd ja Moet ik dus nog ff over nadenken. Maar ik heb zeker weer wat geleerd van je, no doubt...

[Verwijderd]

Op dinsdag 04 december 2001 20:13 schreef _piranha_ het volgende:

[..]

Euh, ik ben juist wel onder de indruk! Het verbaast me net dat zo'n eenvoudige aanpak toch zo gruwelijk snel kan zijn, zoals ik hierboven ook al zei. Je moet inderdaad al snel en erg veel gaan snoeien om dat zo snel op te lossen! En daar moest ik dus nog ff over nadenken, omdat ik dat in je code niet meteen doorheb. Je lijkt - once again, correct me if I'm wrong - gewoon rij per rij af te gaan, en per rij die je controleert ga je gewoon de kolommen sequentieel af, en je probeert eens of een 'X' lukt, en zo niet, probeer je eens een ' '. Dat lijkt me niet echt HEEL GERICHT massaal gaan snoeien, en dat is net waarom ik (nog) niet doorheb waarom die zo eenvoudige aanpak zo damn fast is...
Maar laat er geen twijfel over bestaan : respect voor jou oplossing ! Je bewijst dat een eenvoudige maar op het eerste en tweede gezicht bijzonder onefficiente oplossing toch goed kan werken. Ik zal dus in het vervolg 3 keer moeten kijken
Of zoals Enzo Ferrari ooit zei (dacht toch dat hij het was) : geniaal eenvoudig; eenvoudig geniaal
[..]

Thanks.

Misschien dat het volgende helpt om dat efficiente knippen wat beter te volgen:

Als ik een locatie (i,j) in het array vul met een # of - heeft dat invloed op zowel rij i als kolom j. Ik ga de subtree alleen doorzoeken als zowel de rij als de kolom nog uitgebreid kunnen worden tot een rij/kolom die aan de eisen voor die rij/kolom voldoen. Ik probeer dus geen rijen die volgens de rij eisen wel goed zijn, maar waarvoor als de hele puzzel gevuld is blijkt dat die rij een bepaalde kolom ongeldig maakt.

Een heel eenvoudig voorbeeld:

3 3
1
1
1 1
2
0
2

oftewel:

code:

--#
#--
#-#

Als ik de eerste rij nu laat beginnen met: -# zou dat volgens de eis van de eerste rij nog best goed kunnen zijn en zou ik dus geneigd kunnen zijn om als eerste rij -#- te proberen. Als ik zo verder ga kom ik er pas helemaal aan het einde achter dat -#- in rij 0 een probleem in kolom 1 geeft.
Wat ik doe is bij het bepalen van een waarde voor locatie (0,1) kijken of dat een probleem geeft in rij 0 (hier niet dus) en ook of het een probleem in kolom 1 geeft (hier wel dus) op basis daarvan zou ik hier beslissen op locatie (0,1) geen # te plaatsen, waardoor ik dus alle mogelijke oplossingen die beginnen met -# niet hoef te controleren.

Kortom, ik heb VEEEEEEL meer kans om te cutten dan ik zou hebben als ik alleen controleerde of een rij aan de eisen van die rij voldoet, want een rij moet nu ook nog voldoen aan de eisen van ALLE kolommen.

[Verwijderd]

D'oh !! Dat had ik dus ff niet door toen ik je code bekeek. Je controleert (uiteraard zou ik nu zeggen) ook of een oplossing voor een rij voldoet aan de specificatie van ALLE kolommen... en daardoor snoei je uiteraard veel efficienter, hetgeen zich vertaalt in snelheid uiteraard

Thanx !
Btw : succes ook met de volgende opgaves. Ik zal ook proberen meedoen, hoop alleen dat ik er de tijd voor vind...

[CrazyA]

Helaas heb ik nou ook niet zo veel tijd om alle code door te zwoegen, maar ik zie al wel dat ik nog veel te leren heb

Ik ben benieuwd hoe opgave 2 er uiteindelijk uit komt te zien, en misschien dat ik daar iets mee kan gaan doen. 't Zou dan wel QuickBasic worden dus veel kan 't niet

Ik moet hoog nodig 's andere talen gaan leren, ik weet 't. En dat ga ik ook zeker doen, als ik ooit nog eens een keertje echt tijd daar voor heb (waarschijnlijk niet de eerst volgende paar jaren, misschien als ik met pensioen ga ofzo )