[/14] Programmeer wedstrijd

[kvdveer]

$.2

Volgens mij moet een wedstrijd voldoen aan een aantal punten:

Meetbaarheid
Het reultaat moet goed meetbaar zijn. Een juri is ook een optie.

Eerlijkheid
Een goede wedstrijd is eerlijk. Dat houdt in dat alleen datgene meetelt waar de westrijd om draait. Andere dingen, die niet onderdeel zijn van de wedstrijd mogen niet (of nauwelijks) meetellen. Hiermee vallen 'Bouw een snel Brute-force algoritme' vragen af, tenzijn de wedstrijd draait om de snelheid van de afzonderlijke talen.

Diversiteit
De resultaten moeten uiteenlopen. Het is gewoon niet zinnig om iedereen eerste te laten worden. Er moeten slechte en goede resultaten zijn. Hiermee valt (weer) een 'Bouw een snel Brute-force algoritme' af', omdat vrijwel alle serieuze deelnemers het in dezelfde tijd voor elkaar kunnen krijgen.


Zo, weer het een en ander afgekraakt, nu wat iedeen.
Bouw een algoritme dat een (zelfbedacht?) spelletje kan winnen van een ander algoritme.
Bouw een programma dat op efficiente wijze een rooster maakt.

[Verwijderd]

Op dinsdag 09 oktober 2001 14:40 schreef kvdveer het volgende:
Bouw een algoritme dat een (zelfbedacht?) spelletje kan winnen van een ander algoritme.

Dit stelde ik dus al eerder voor, overigens heeft het natuurlijk geen zin als iedereen zn eigen spelletje bedenkt..

Bouw een programma dat op efficiente wijze een rooster maakt.

Efficiency in de zin van snelheid ? Of geheugengebruik ? Of tijd benodigd om het proggy te maken ? Alle drie lijken me oneerlijk aangezien dit natuurlijk weer heel erg per taal verschilt..

[im_ik]

Op dinsdag 09 oktober 2001 15:00 schreef Sneech het volgende:

Efficiency in de zin van snelheid ? Of geheugengebruik ? Of tijd benodigd om het proggy te maken ? Alle drie lijken me oneerlijk aangezien dit natuurlijk weer heel erg per taal verschilt..

ehh ik denk dat ie een les rooster of werk rooster bedoelde ..

[Verwijderd]

Op dinsdag 09 oktober 2001 15:09 schreef im_ik het volgende:
ehh ik denk dat ie een les rooster of werk rooster bedoelde ..

Ooooohhh !!

Naja, dat soort roosters zijn meestal wel gewoon te bruteforcen..

[im_ik]

Maar als je ook rekening moet houden met voorkeuren,etc,etc
Dan moet je toch echt beter naar een wiskundige oplossing gaan kijken..
Eve kijken daar was pas een mooi topic over....hiero

[Verwijderd]

Op dinsdag 09 oktober 2001 15:30 schreef im_ik het volgende:
Dan moet je toch echt beter naar een wiskundige oplossing gaan kijken..

Brute force is natuurlijk ook wiskundig: nadat je een hele zooi combinaties hebt gegenereerd, moet je ze gaan beoordelen op hoeveel iedereen aan zn trekken komt etc, om vervolgens de combinatie met de hoogste score te kiezen.
Bij dat beoordelen moet je dus ff wat formuletjes gebruiken.

[tomato]

* tomato zou het maken van een simpele NFA regex engine wel leuk vinden


Over wiskundige oplossingen:In haast iedere 'programmeerwedstrijd' gaat het om 'wiskundige problemen'. Een groot deel van de opdrachten bestaat meestal uit iets met grafen, priemgetallen, verdelingen, en dat soort wiskundige speeltjes
Niet iedereen is hier altijd blij mee en er is over te discussieren of dat nou echte 'programmeer'-opgaven zijn. Ik vind van wel, maar programmeren kan ook op heel andere dingen neerkomen.

[marcusk]

een regex parser lijkt mij ook wel interessant om te maken, maar NFA, wasda? alleen is er niet echt een competitie-element geloof ik (alleen snelheid kan ik bedenken)

[elnino]

Op dinsdag 09 oktober 2001 15:00 schreef Sneech het volgende:
Efficiency in de zin van snelheid ? Of geheugengebruik ? Of tijd benodigd om het proggy te maken ? Alle drie lijken me oneerlijk aangezien dit natuurlijk weer heel erg per taal verschilt..

Daarom lijkt de opdracht van 'Bouw je eigen scriptingtaal' wel leuk, omdat:

• Het in meerdere talen kan.
• Het niet een gebruikelijke opdracht is, dus een uitdaging.
• Veel creativiteit kun je erin stoppen.

Er zou dan een soort van jury ofzo kunnen komen die dan beoordeeld op:

• werking
• syntax
• efficiëntie

etc.

[im_ik]

Brute force is natuurlijk ook wiskundig: nadat je een hele zooi combinaties hebt gegenereerd, moet je ze gaan beoordelen op hoeveel iedereen aan zn trekken komt etc, om vervolgens de combinatie met de hoogste score te kiezen.
Bij dat beoordelen moet je dus ff wat formuletjes gebruiken.

Mmm zit wat in....
Ik denk bij nader inzien dat ie dan toch afvalt.
Of je moet hem gaan reguleren...
maar das ni leuk..
Ik denk dat we dan weer terug komen op "vechtende algoritems"
We hebben alleen eerst een "base" nodig van hoe en wat.
bijvoorbeeld: hoe communiceren ze ?
is het realtime of turn-based, etc

offtopic:
coole .sig

edit: mot sneller type

[marcusk]

Bouw een algoritme dat een (zelfbedacht?) spelletje kan winnen van een ander algoritme.

RoboCode?

[tomato]

Op dinsdag 09 oktober 2001 15:39 schreef marcusk het volgende:
een regex parser lijkt mij ook wel interessant om te maken, maar NFA, wasda? alleen is er niet echt een competitie-element geloof ik (alleen snelheid kan ik bedenken)

NFA = Nondeterministic Finite Automata if I remember correctly

Dure woorden, maar het komt er op neer dat de engine de opdracht verwerkt aan de hand van de reguliere expressie. Daar tegenover staan DFA engines (rara waar staat het voor ), die werken via de tekst (je begrijpt wellicht dat deze veel minder interessant zijn qua techniek).

[/off-topic]

Je zou in ieder geval bepaalde eisen moeten stellen wat de engine moet kunnen. Het zal al lastig genoeg zijn om daar altijd aan te voldoen, dus veel eisen moeten er denk ik niet gesteld worden. Verder inderdaad misschien snelheid, of aantal regels code ofzo

[Mister_X]

ik bouw een ASP login script, met cookie support!!!

[Nielsz]

Op dinsdag 09 oktober 2001 15:41 schreef im_ik het volgende:

[..]

Mmm zit wat in....
Ik denk bij nader inzien dat ie dan toch afvalt.
Of je moet hem gaan reguleren...
maar das ni leuk..
Ik denk dat we dan weer terug komen op "vechtende algoritems"
We hebben alleen eerst een "base" nodig van hoe en wat.
bijvoorbeeld: hoe communiceren ze ?
is het realtime of turn-based, etc

En dan komt het gewoon neer op RoboCode.

[Mister_X]

nee, geintje, hoewel ik wel een goeie hebt, maareh,

ik doe mee met de wedstrijd ik heb mijn opdracht wel al af... www.microsft.com voor de nieuwschierige ,

nee maar eh, ik had wel toendertijd wat gelezen over deze match, nooit wat geworden?> ik keek toen regelmatig op die site, het enige wat er op stond was dat de site nog niet af was, is ie dat ooit al geweest?

[Korben]

Op dinsdag 09 oktober 2001 15:41 schreef elnino het volgende:

[..]

Daarom lijkt de opdracht van 'Bouw je eigen scriptingtaal' wel leuk, omdat:

• Het in meerdere talen kan.
• Het niet een gebruikelijke opdracht is, dus een uitdaging.
• Veel creativiteit kun je erin stoppen.

Er zou dan een soort van jury ofzo kunnen komen die dan beoordeeld op:

• werking
• syntax
• efficiëntie

etc.

Hehe... nieuwe opdracht... bouw een 4GL-achtige scriptingtaal

Maar het lijkt mij idd wel tof om een scriptingtaal te schrijven. Heh dat wordt leuk... scripting for PHP

[im_ik]

Op dinsdag 09 oktober 2001 15:49 schreef Nielsz het volgende:
[..]
En dan komt het gewoon neer op RoboCode.

oftewijl wij kunnen hier me zijn allen geen eerlijk en orginele wedstijdt houden..
Ik heb namalijk met veel plezier met het lezen van dat draadje over "abc" -> "abd" ofzo..in C en asm

[.oisyn]

Op dinsdag 09 oktober 2001 16:12 schreef im_ik het volgende:

[..]

oftewijl wij kunnen hier me zijn allen geen eerlijk en orginele wedstijdt houden..
Ik heb namalijk met veel plezier met het lezen van dat draadje over "abc" -> "abd" ofzo..in C en asm

ja, en ik heb eigenlijk nooit plezier omdat er nooit eens een ingewikkeld computer graphics/game programming topic voorbij komt, dus moet ik me maar redden met draadjes als "abc" -> "abd" ofzo..in C en asm

[marcusk]

Op dinsdag 09 oktober 2001 15:46 schreef tomato het volgende:
NFA = Nondeterministic Finite Automata if I remember correctly

Dure woorden, maar het komt er op neer dat de engine de opdracht verwerkt aan de hand van de reguliere expressie. Daar tegenover staan DFA engines (rara waar staat het voor ), die werken via de tekst (je begrijpt wellicht dat deze veel minder interessant zijn qua techniek).

Dus de regexp-parsers in PHP bv. zijn NFA als ik het goed begrijp? Hoe werkt het via DFA dan?

Je zou in ieder geval bepaalde eisen moeten stellen wat de engine moet kunnen. Het zal al lastig genoeg zijn om daar altijd aan te voldoen, dus veel eisen moeten er denk ik niet gesteld worden. Verder inderdaad misschien snelheid, of aantal regels code ofzo

Je zou een lijstje met mogelijke features kunnen maken, en dan punten kunnen geven per geimplementeerde feature. En natuurlijk snelheid ja. Aantal regels code lijkt me niet echt een goed plan

Zijn er nog meer mensen die dit interessant zouden vinden?

[kvdveer]

RoboCode is inderdaad een leuke optie, maar is niet taal onafhankelijk, en test dus niet je programmeer vaardigheid, maar de kennis van die taal. Alhoewel iedereen met wat programmeer ervaring java moet kunnen leren, het is zeer eenvoudig qua syntax. Bovendien zijn er VEEL tutorials.

Wat dacht je bijvoorbeeld aan een klaverjas engine? Is mooi complex, en taal onafhankelijk, omdat de verschillende engines met elkaar communiceren middels een persoon.
Andere optie: schaken/dammen, Colonisten, Gargason, Monopoly, etc...

Je test je algoritme door je computer het spelletje te laten spelen, en zelf je stukken / kaarten te verplaatsen. (of even te zeggen via IRC). De ander voert dit in in zijn computer en Voila! je hebt een eerlijke, taalonafhankelijke engine, die heel eenvoudig uitgevoerd kan worden, maar ook heel complex.

edit:
oeps...

[tomato]

Op dinsdag 09 oktober 2001 16:55 schreef marcusk het volgende:
Dus de regexp-parsers in PHP bv. zijn NFA als ik het goed begrijp?

De standaard regular expressions in PHP zijn volgens mij POSIX NFA, maar niet helemaal (extended noemen ze het geloof ik).
DFA's vind je ook wel terug in aardig wat tools, maar met een echte DFA kun je eigenlijk alleen zien of een pattern matched, niet waar, of wat. Backreferences (capturing dus) zijn met een echte DFA ook onmogelijk.
Er zijn ook tools die beiden combineren. Omdat een DFA erg snel kan zien of iets matched wordt die eerst uitgevoerd en als dat zo is wordt een NFA ingezet om meer informatie over de match te krijgen. Er zijn ook geavanceerdere vormen van combinaties van beiden.

Hoe werkt het via DFA dan?

Een DFA compileert eerst de regex in een soort boomstructuur (alle mogelijke paden). Dan wordt de tekst geanaliseerd om te kijken of deze in een van deze paden past. Het compileren duurt even (een NFA 'compileert' ook het pattern, maar lang niet zo uitgebreid en niet te vergelijken), maar dan maakt het verder niet uit hoe je de regex gebouwd hebt. Bijvoorbeeld /(hooooo|hooo|hoo|ho)/ of /hoo?o?(oo)?/ maakt voor een DFA qua efficientie absoluut niets uit, heel anders dan bij een NFA (belangrijk is bijvoorbeeld dat een DFA geen backtracking hoeft toe te passen om tot een match te komen, hij houdt gewoon bij welke 'paden' nog 'kunnen').

Maar dit is best wel off-topic
Als je geinteresseerd bent in de theorie is er eigenlijk maar 1 echte aanrader: Mastering Regular Expresssions van Jeffrey Friedl (O'Reilly).
Ik denk dat het vast ergens op het web te vinden is. Ik heb het boek hier liggen, dus met een simpele search op een stukje tekst eruit moet wel een HTML versie te vinden zijn, alleen mag ik hier waarschijnlijk geen link plaatsen (hint)

Aantal regels code lijkt me niet echt een goed plan

Was ook een mopje

Zijn er nog meer mensen die dit interessant zouden vinden?

Niet zo veel denk ik
Het is misschien ook wel erg complex (maar dat heb je met de opdracht natuurlijk zelf in de hand...)

[edit]
/hooo.../ voorbeeld was niet zo fijn gekozen, omdat de twee natuurlijk niet aan elkaar gelijk zijn
Beter voorbeeld:

/(0|1|2|3|4|10|11|12|13|14)/ en /1?[0-4]/ maken voor een DFA absoluut geen verschil.

[wasigh]

Schoonheid van een algoritme is niet meetbaar daarom kun je daar geen westrijd over houden:

hier een opgave: laat ff weten of ie te makkelijk of te moeilijk is:

Beschrijving
Gegeven is een land in de vorm van een rechthoekige matrix van velden waarvan sommige wel en andere niet begaanbaar zijn. Gevraagd wordt het aantal verschillende routes waarlangs het land doorkruist kan worden. Voor zon route gelden de volgende regels:
Je moet linksboven beginnen en rechtsonder eindigen.
Je mag alleen naar rechts of naar onderen.
Je mag niet op een onbegaanbaar veld komen.
Je mag aannemen dat het aantal routes in een long (64 bits) past.
Invoer
De invoer bestaat uit:
een regel met het aantal runs r (1 ≤ r ≤ 100);
per run:
een regel met daarop de breedte b en de hoogte h van het land (2 ≤ b, h ≤ 100);
h regels met b karakters, waarbij het karakter een punt kan zijn (begaanbaar) of een x (onbegaanbaar).
Uitvoer
De uitvoer moet bestaan uit r regels met op elke regel het aantal routes waarlangs je het desbetreffende land kunt doorkruisen.

VoorbeeldinvoerUitvoer voor de voorbeeldinvoer

5
2 2
..
..
2 2
.x
x.
3 3
.x.
x.x
.x.
5 5
..x..
x..x.
.x..x
..x..
...x.
6 4
......
......
......
......


uitvoer:


2
0
0
1
56

[marcusk]

Op dinsdag 09 oktober 2001 17:22 schreef wasigh het volgende:
Schoonheid van een algoritme is niet meetbaar daarom kun je daar geen westrijd over houden:

hier een opgave: laat ff weten of ie te makkelijk of te moeilijk is:

Lijkt me wel te doen (ook voor meer mensen dan de regexp opgave denk ik)

[im_ik]

hee niet et simpel maken...he
nu hoeven we allen een parser voor de inpute en ouput te maken..
en de rest lost je op met A* (zie hier voor de Delphi/Visual C++/JAVA en plain-C code )

[marcusk]

hehe ik heb em al

edit:
bijna

af (nee, niet met A*, dat is een beetje overdreven)

edit:
alleen nog ff het invoer-gedeelte maken

[marcusk]

code:

Opgave Wasigh
=============
aantal runs: 5

breedte: 2
hoogte: 2
..
..
aantal routes: 2

breedte: 2
hoogte: 2
.x
x.
aantal routes: 0

breedte: 3
hoogte: 3
.x.
x.x
.x.
aantal routes: 0

breedte: 5
hoogte: 5
..x..
x..x.
.x..x
..x..
...x.
aantal routes: 1

breedte: 6
hoogte: 4
......
......
......
......
aantal routes: 56

[Verwijderd]

Kijk eens op crackmes.cjb.net, hier kun je crackme posten (een proggie met serienummer invoer of dergelijke dingen met een zo moeilijk mogelijk algoritme wat dan door anderen "gecrackt" moet worden. Voor diegene wat niet weten wat een crackme is.) je kunt je helemaal uitleven en kijken hoe lang het duurt voordat ze hem gecrackt hebben. Mijn eerste proggie was binnen 2 uurtjes gecrackt mijn 2e hadden ze ong. 1 dag nodig en mijn 3e ongeveer 2 maanden dus die was al wat beter. Het is eigenlijk de bedoeling dat diegene die jouw proggie "cracken" een keygen maken die met hun eigen naam een goed serienummer maakt

[D2k]

Op dinsdag 09 oktober 2001 18:26 schreef marcusk het volgende:

code:

Opgave Wasigh
=============
antwoord

welke taal?

[marcusk]

C (eigenlijk C++ omdat ik cin, cout en new gebruik )
slechts 66 regels

[D2k]

Op dinsdag 09 oktober 2001 18:34 schreef marcusk het volgende:
C (eigenlijk C++ omdat ik cin, cout en new gebruik )
slechts 66 regels

* D2k is ook bezig
zeg niet dat het lukt
maar vin het wel ff leuk om te tryen

[im_ik]

mmm kon hem hier niet vinden..
Hij moet ergens staan ik weet zeker dat ik dit al een keer voorbij heb zien komen..

[tomato]

Op dinsdag 09 oktober 2001 19:15 schreef im_ik het volgende:
mmm kon hem hier niet vinden..
Hij moet ergens staan ik weet zeker dat ik dit al een keer voorbij heb zien komen..

Klopt, ik kende hem volgens mij ook al...
Maar dat geeft verder niet

[Gerco]

Wij hebben zo'n opdracht gehad in het 1e jaar van Technische Info voor het vak Proggen in Java deel 2.

Was wel leuk. Moesten we op een "schaakbord" het aantal mogelijke routes van een willekeurig punt tot een willekeurig punt uitrekenen. Een andere opdracht was om een algo te maken die uit een doolhofje de uitgang moest vinden.

edit:

Ik had de opgaven niet helemaal correct, maar hier staan ze:
Dobbelschaak
Doolhof

Wel beiden op een 8x8 veld, maar da's natuurlijk kinderlijk eeivoudig uit te breiden.

[RvdH]

Doe es ff een andere

[Demo]

Uuh, Nielsz, leuk dat iedereen de kleur van je icon kan verbouwen, maar de waarden voor Groen en Blauw moet je toch echt ff omwisselen...

[wasigh]

Op dinsdag 09 oktober 2001 17:46 schreef im_ik het volgende:
hee niet et simpel maken...he
nu hoeven we allen een parser voor de inpute en ouput te maken..
en de rest lost je op met A* (zie hier voor de Delphi/Visual C++/JAVA en plain-C code )

A* heb je hier niet eens voor nodig, het kan op een veel snellere manier.