[/14] Programmeer wedstrijd

[ACM]

Op woensdag 03 oktober 2001 13:15 schreef wasigh het volgende:
zaterdag nkp
* wasigh is present

Mja, denk dat ik daar ook wel effe ga kijken, is tenslotte 'mijn' faculteit
(Gerco: ga je mee? )


Maar dat betekend natuurlijk wel dat wasigh automatisch van deelname uitgesloten moet worden, aangezien hij 'meer ervaring' heeft dan veel anderen met prog-wedstrijden

[ACM]

Op donderdag 04 oktober 2001 00:37 schreef VisionMaster het volgende:
Ik vind dat de wedstryd niet taal-gebonden moet worden. Er zijn altijd goeie programmeurs die totaal niet bekent zijn met een bepaalde taal, maar die alles kunnen betekennen op hun vlak.

Er zal een zekere beperking moeten gelden.

Want er zijn dingen die in prolog ofzo in 1 regel code kunnen, waar je met c/java vele regels aan kwijt bent

Maar daarna maakt het nauwelijks uit, of er nou javascript, java, c, c++, php, vbscript, vb, perl, python wordt gebruikt. Zolang er maar geen gebruik wordt gemaakt van 'flauwe includes' (import BigInteger in java, als de opdracht het implementeren van een big integer is en dat soort dingen)

[razor-x]

Net of je al niet genoeg te doen hebt nielsz

[Nielsz]

Whehehe, idd
Voor sommige dingen moet je tijd maken, en andere dingen naar achteren schuiven

[Verwijderd]

Op woensdag 03 oktober 2001 23:24 schreef Nielsz het volgende:
Jawel, maar ik wil wel altijd weten of iets wat ik zou brouwen sneller is als dan die van de buurman
(btw, ik heb nu een forum geschreven, is echt bloedje snel, dat geeft wel een kick )

Voor jou is het dus eigenlijk een partijtje ego krikken dus

[Nielsz]

Nah, ik weet zelf ook wel dat ik het tegen de meeste afleg, maar het is toch lachen. En als razor-x meedoet wordt ik tenminste niet laatste

En over dat mijn bak al draait, dat was een grapje!

[wasigh]

Op donderdag 04 oktober 2001 02:29 schreef ACM het volgende:

[..]

Er zal een zekere beperking moeten gelden.

Want er zijn dingen die in prolog ofzo in 1 regel code kunnen, waar je met c/java vele regels aan kwijt bent

Maar daarna maakt het nauwelijks uit, of er nou javascript, java, c, c++, php, vbscript, vb, perl, python wordt gebruikt. Zolang er maar geen gebruik wordt gemaakt van 'flauwe includes' (import BigInteger in java, als de opdracht het implementeren van een big integer is en dat soort dingen)

waarom mag je geen gebruik maken van de mogelijkheden van de taal
dan moeten de opdrachten maar variabel genoeg zijn!

[Nielsz]

Bij mijn opdracht vallen er wel een aantal talen af, ik denk aan ASM, maybe zelfs C (C++ wel uiteraard )

[Korben]

Als het bij deze wedstrijd gaat om snelheid, zullen scripttalen altijd verliezen. Nou ja, als we er ff vanuit gaan dat de echte programmeurs ook goed om kunnen gaan met hun taal. Laten we niet vergeten dat scripttalen in principe interpretertalen zijn, zoals QBASIC. En het maakt niet uit hoe flitsend snelle algoritmes je bouwt in PHP of JSP, hetzelfde algoritme in C++ zal altijd een factor 2 sneller zijn.

[Verwijderd]

Op donderdag 04 oktober 2001 09:20 schreef Xenophage het volgende:
Nou ja, als we er ff vanuit gaan dat de echte programmeurs ook goed om kunnen gaan met hun taal.

De echte programmeurs hebben niet "hun" taal, die kunnen zonder enige moeite zo een andere taal leren en er in programmeren alsof ze het al jaren doen

[Korben]

Op donderdag 04 oktober 2001 09:28 schreef Zef het volgende:

[..]

De echte programmeurs hebben niet "hun" taal, die kunnen zonder enige moeite zo een andere taal leren en er in programmeren alsof ze het al jaren doen

Dat is waar. Daarom vind ik mezelf ook een echte programmeur. Maar toch hebben programmeurs meestal een favoriete taal. De mijne is C++. Maar ik zeg niet dat dat niet kan veranderen. Het kan (als ik een keer de kans krijg om erin te coden) best C# worden.

[Verwijderd]

Persoonlijk lijkt me een wedstrijd waarbij het alleen gaat om de snelheid van je algoritme nogal saai.

wat ik veel interessanter zou vinden is om meerdere agents (geschreven door kandidaten) direct tegen elkaar te laten 'strijden' , dus mbv. een beetje AI. En dan bedoel ik niet meteen het aloude arena+bots concept, het kan van alles zijn; real time/turn based, simulatie-achtig/abstracter, etc.

Er moet dan wel een soort protocol komen waarmee de agents met het 'platform' communiceren, zodat iedereen fijn z'n agent in z'n eigen taaltje kan proggen.

Suggesties ?

[Korben]

Global Thermonuclear Warfare?

[Verwijderd]

Xenophage: Het maakt niet uit hoe flitsend snelle algoritmes je bouwt in PHP of JSP, hetzelfde algoritme in C++ zal altijd een factor 2 sneller zijn.

Ik heb wel een C interpreter (wel leuk om te schrijven trouwens), maar het lijkt erop dat ik voor jouw programma een C++ interpreter moet gaan schrijven. Hmm... ... zoeken dan maar ...

(Je ziet het probleem met je bewering? Dit werkt twee kanten op.)

[Nielsz]

Whehehe
Zijn er nog andere mensen die leuke opgaven hebben?

[Korben]

Jah zeker... Schrijf je eigen scripttaal!

Zow en kom nou maar op met je PHP...

[Nielsz]

Zijn jullie er klaar voor?

[D2k]

Op donderdag 04 oktober 2001 19:42 schreef Nielsz het volgende:
Zijn jullie er klaar voor?

nee

[wasigh]

try me...

[Nielsz]

Nou jongens de opdracht is:

Zoek twee strings op die dezelfde md5 hash hebben.
En niet op internet, een geen tijgerstrings!

Get, set, go!

[Verwijderd]

Boooooriiiiing.....

[HappyFun]

Op donderdag 04 oktober 2001 19:42 schreef Nielsz het volgende:
Zijn jullie er klaar voor?

Maak die PlugIn voor Pim

[Nielsz]

Zijn er al mensen bezig, of ben ik de enige die zijn database aan het volgooien is?

[HappyFun]

Op donderdag 04 oktober 2001 20:03 schreef Nielsz het volgende:
Zijn er al mensen bezig, of ben ik de enige die zijn database aan het volgooien is?

Met je pron zeker prongrot

[Nielsz]

Zeg, het is hier geen happyforum, ga es ff ontopic lullen man!

[HappyFun]

Op donderdag 04 oktober 2001 20:05 schreef Nielsz het volgende:
Zeg, het is hier geen happyforum, ga es ff ontopic lullen man!

Sorry

[RvdH]

Oke, nu heb ik dat gemaakt. Moet ik het nu ergens posten ofzo?

[razor-x]

Op donderdag 04 oktober 2001 09:16 schreef Nielsz het volgende:
Nah, ik weet zelf ook wel dat ik het tegen de meeste afleg, maar het is toch lachen. En als razor-x meedoet wordt ik tenminste niet laatste

En over dat mijn bak al draait, dat was een grapje!

Damn dit bericht negeer ik dus echt ff

[Nielsz]

Op donderdag 04 oktober 2001 23:32 schreef RickJansen het volgende:
Oke, nu heb ik dat gemaakt. Moet ik het nu ergens posten ofzo?

Shit was je sneller als ik
Ik had een brak systeempje gebouwd wat via de browser
md5.php?string=
binnenkreeg, en daarvan de hash berekende, opsloeg in de db,
en daarna een headers sturen met location: md5.php$string=string++

Helaas vondt mijn browser het niet tof en knalde er telkens uit na een halve minuut. Toch wel zo'n 500 records toegevoegd, maar geen goede....
Maar wat is de oplossing, uitkomst, algoritme en snelheid?

[RvdH]

Op donderdag 04 oktober 2001 23:39 schreef Nielsz het volgende:

[..]

Shit was je sneller als ik
Ik had een brak systeempje gebouwd wat via de browser
md5.php?string=
binnenkreeg, en daarvan de hash berekende, opsloeg in de db,
en daarna een headers sturen met location: md5.php$string=string++

Helaas vondt mijn browser het niet tof en knalde er telkens uit na een halve minuut. Toch wel zo'n 500 records toegevoegd, maar geen goede....
Maar wat is de oplossing, uitkomst, algoritme en snelheid?

Eh, ik denk dat er meerdere oplossingen zijn he.

Wat ik in ieder geval gedaan heb:
Elke ASCII file openen in je homedirectory, regel splitsen op woorden, md5 hash maken van de woorden, woorden en hash in MySQL database opslaan, en dan kijken of een hash meer dan 1 keer voorkomt met verschillende woorden, zoja, woorden uitpoepen.

Uitkomst? Eh.. hij's nog aan het checken
Algoritme? Wa?
Snelheid? Afhankelijk van je systeem

[Nielsz]

Ah, dus toch met mysql. Ik was ff bang dat er mensen bezig waren met hele grote arrays te maken haha

[RvdH]

En perl
En dat ie nog bezig is, is in mijn signature te zien

[.oisyn]

Op donderdag 04 oktober 2001 09:20 schreef Xenophage het volgende:
Als het bij deze wedstrijd gaat om snelheid, zullen scripttalen altijd verliezen. Nou ja, als we er ff vanuit gaan dat de echte programmeurs ook goed om kunnen gaan met hun taal. Laten we niet vergeten dat scripttalen in principe interpretertalen zijn, zoals QBASIC. En het maakt niet uit hoe flitsend snelle algoritmes je bouwt in PHP of JSP, hetzelfde algoritme in C++ zal altijd een factor 2 sneller zijn.

wat heb jij tegen qbasic? huh? huh? SPREEK OP! ketter!

anyway, wat is de opdracht nou? "het vinden van 2 waardes" vind ik een beetje een vage omschrijving

code:

int main ()
{
    printf ("waarde1 : %d\n", 0xdeadbeef);
    printf ("waarde2 : %d\n", 0xdeadbeef ^ 0x2a2a2a2a);
    return 0;
}

niet goed?
Misschien is het al gezegd, maar dan moeten ze maar een onzinfilter maken voor GoT zodat ik alleen de nuttige posts effe op mijn gemakkie door kan lezen
(IDEE: opdracht: maak een onzinfilter voor GoT )

.edit: oh nee dan zit je met een leeg forum

[Explore]

Tsjonge, wat een gedoe zeg... Op zich leek me het wel een leuk idee (voor mensen die er tijd voor hebben). Aan leuke suggesties ontbreekt het echter, afgezien van die van Sneech:

Op donderdag 04 oktober 2001 09:43 schreef Sneech het volgende:
Persoonlijk lijkt me een wedstrijd waarbij het alleen gaat om de snelheid van je algoritme nogal saai.

wat ik veel interessanter zou vinden is om meerdere agents (geschreven door kandidaten) direct tegen elkaar te laten 'strijden' , dus mbv. een beetje AI. En dan bedoel ik niet meteen het aloude arena+bots concept, het kan van alles zijn; real time/turn based, simulatie-achtig/abstracter, etc.

Er moet dan wel een soort protocol komen waarmee de agents met het 'platform' communiceren, zodat iedereen fijn z'n agent in z'n eigen taaltje kan proggen.

Suggesties ?

Snelheid lijkt me er niet toe doen - dat hangt van veel te veel dingen af (afgezien van bv. het verschil tussen bubble sort en quick sort, waarbij de laatste natuurlijk een veel mooiere oplossing is als het gaat om grote hoeveelheden data). Meest elegante oplossing, best werkend ofzo is dus veel interessanter.

Helaas is zo'n 'thermonuclear warfare' idee nogal omslachtig. Aan een programmeer wedstrijd moet vanzelfsprekend een tijdslimiet zitten. Bovendien moet het te beoordelen zijn. Als het bv. gaat om iets grafisch dan kan iemand iets met c++ en opengl iets moois maken, maar met html/javascript/php enzo kan je 't dan compleet schudden. Het lijkt mij dus dat bv. de ene keer iets 'web-achtigs' wordt gedaan en de andere keer iets met standalone dingen in een niet-web-taal, om het zo maar effe te noemen

Wie komt er met een goede suggestie en wat (van die saaie ) regeltjes?

[Explore]

Op vrijdag 05 oktober 2001 00:19 schreef OiSyN het volgende:
(IDEE: opdracht: maak een onzinfilter voor GoT )

.edit: oh nee dan zit je met een leeg forum

precies: definieer 'onzin'...

[wasigh]

ik heb reeds(vroeger) een database gevuld met alle md5 hashes tot 3 karakters (60.000 hashes) kopen ?

(java-progje en mysql database, ging redelijk snel )

[Nielsz]

OiSyN >> Niet goed nee, ik kan nergens uit opmaken dat ze ook maar uit de verte door md5 zijn gebakken

[.oisyn]

Op vrijdag 05 oktober 2001 00:22 schreef Explore het volgende:

[..]

precies: definieer 'onzin'...

1 woord: GoT

[.oisyn]

Op vrijdag 05 oktober 2001 00:23 schreef Nielsz het volgende:
OiSyN >> Niet goed nee, ik kan nergens uit opmaken dat ze ook maar uit de verte door md5 zijn gebakken

oh was het de bedoeling dat je 2 strings met dezelfde md5 hasj (ken ik niet, waar wordt dat verbouwd? ) moest vinden... zeg dat dan gewoon

[VisionMaster]

Ik vind het niet echt een geweldige opdracht.

Of je zit lang te piekeren hoe je dit in godesnaam moet doen of je heb dit af in een X aantal minuten .

De opdracht is ook een beetje vaag en nutteloos.

[Grum]

Op donderdag 04 oktober 2001 19:52 schreef Nielsz het volgende:
Nou jongens de opdracht is:

Zoek twee strings op die dezelfde md5 hash hebben.
En niet op internet, een geen tijgerstrings!

Get, set, go!

dit is alleen te bruut forcen of je moet heel slim gaan doen (en flauw)

[Gerco]

Op donderdag 04 oktober 2001 19:52 schreef Nielsz het volgende:
Nou jongens de opdracht is:

Zoek twee strings op die dezelfde md5 hash hebben.
En niet op internet, een geen tijgerstrings!

Get, set, go!

Dat is te doen in 2^64 operaties geloof ik, is nou niet echt een handige opdracht. Tenzij je pas over een paar jaar antwoorden wil zien. Meer dan het triviale antwoord kan ik hier niet op geven:

String 1: a
String 2: a

_{(Er stond niet bij dat het verschillende strings moesten zijn!)}

[.oisyn]

hmmm okee subopdracht: hack in op de distributed.net keyserver en webserver, en zorg dat de distributed.net deelnemers een client gaan draaien die deze MD5 strings bij elkaar gaan zoeken

.edit: trouwens wel een leuk idee, laten we met z'n allen een mini-distributed.net projectje opzetten

[Nielsz]

Op vrijdag 05 oktober 2001 00:59 schreef Grum_ het volgende:

[..]

dit is alleen te bruut forcen of je moet heel slim gaan doen (en flauw)

Ja, und?

rename opdracht de_snelste_brute_force_methode

Het gaat er om dat je een manier verzint die snel en goed werkt. Dat het dan onder het kopje bf valt is weer iets anderes.
En zoals verwacht pakte RickJansen het heel anders aan dan ik, zijn manier vind ik ook wel leuk. En daar gaat het om.

[Korben]

Op vrijdag 05 oktober 2001 00:19 schreef OiSyN het volgende:

[..]

wat heb jij tegen qbasic? huh? huh? SPREEK OP! ketter!

Te moeilijk

code:

sub MAIN()
{
  int I;

  for (I = 1 TO 200)
  {
    PRINT("Bert");
  }
  NEXT I;

  PRINT("En nog een bert");
}

Wat is MD5?

[curry684]

Op vrijdag 05 oktober 2001 00:59 schreef Grum_ het volgende:
dit is alleen te bruut forcen of je moet heel slim gaan doen (en flauw)

M'n vinger jeuken bijna om m'n MD5 class te reversen zodat ie bij een hash alle mogelijke inputs gaat uitpoepen.

Bijna.

Ik heb bovendien maar 40Gb HD-space...

[.oisyn]

Op vrijdag 05 oktober 2001 09:52 schreef curry684 het volgende:

[..]

M'n vinger jeuken bijna om m'n MD5 class te reversen zodat ie bij een hash alle mogelijke inputs gaat uitpoepen.

Bijna.

Ik heb bovendien maar 40Gb HD-space...

ik ook... samenwerken?
(Bestaat er ook zoiets als RAID-over-internet? )

[elnino]

Lees dit hieronder eens... Succes!

php.net comment on md5:
I just wanted to comment on the person above who claimed that MD5 (which generates 128-bit keys) is likely to produce repeats. There are 340282366920938463463374607431768211456 distinct 128-bit integers. Running MD5 on a million random inputs will produce duplicates much less than .000000000001 % of the time.

340282366920938463463374607431768211456 mogelijkheden dus. Succes nogmaals

[elnino]

Misschien is het zinvoller om een programma te maken dat berekend hoe lang je hiermee bezig bent om dit te bereken en hoeveel schijfruimte je nodig hebt om een dubbele MD5-string te krijgen.

En hoe bepalen jullie de winnaar? Door de source-code te bekijken, of hoe snel het antwoord berekend werd door het programma, of door de code te benchmarken?

[ Voor 24% gewijzigd door elnino op 03-05-2004 10:32 . Reden: quote weggehaald, was totaal irrelevant :) ]

[marcusk]

Op zaterdag 06 oktober 2001 12:09 schreef elnino het volgende:
Misschien is het zinvoller om een programma te maken dat berekend hoe lang je hiermee bezig bent om dit te bereken en hoeveel schijfruimte je nodig hebt om een dubbele MD5-string te krijgen.

Bijna 1500 TB succes nielsz

(100 / .000000000001) * (128 / = 160000000000 bytes = 1445 TB

[Nielsz]

Whow, is dat md5 toch veiliger als ik dacht
Nog andere idee'n voor wedstrijden?

[.oisyn]

maar die 1500 TB en zoveel mogelijkheden zijn natuurlijk wel worst-case he

[Nielsz]

Ja, als je geluk hebt, zit je pas op de helft als je er eentje vindt

[Verwijderd]

Gisteren zijn net de nederlands kampioenschappen programmeren geweest.

Daar zaten best leuke opgaven tussen.
Ik zou zeggen kijk maar eens op :
http://www.nkp2001.nl

[Gerco]

Op zondag 07 oktober 2001 12:26 schreef FesterBergeend het volgende:
Gisteren zijn net de nederlands kampioenschappen programmeren geweest.

Waren best leuk idd. De opgaven van de voorrondes ook. Maar die van de wedstrijd zelf staan nog niet online geloof ik. Dan moet Wasish ze even inscannen

edit:
De opgaven staan er nu wel

[CyberSnooP]

Op zondag 07 oktober 2001 12:26 schreef FesterBergeend het volgende:
Gisteren zijn net de nederlands kampioenschappen programmeren geweest. http://www.nkp2001.nl

[off-topic]
Die geldbedragen die je kunt winnen zijn wel grappig:
1e plaats: EUR 512
2e plaats: EUR 256
3e plaats: EUR 128
[/off-topic]

edit:
Waarom doet mijn Euro teken () het niet?

[Verwijderd]

Wasigh hogeschool ??

Hmm, je ziet bij de uitslag nu wel een echt verschil tussen uni. en hogeschool..

[mbravenboer]

Tizzwat: Hmm, je ziet bij de uitslag nu wel een echt verschil tussen uni. en hogeschool..

En tussen de UU en de andere universiteiten

[D2k]

Op zondag 07 oktober 2001 16:15 schreef mbravenboer het volgende:

[..]

En tussen de UU en de andere universiteiten

gokje : mbravenboer zit op de UU

waar zat wasigh ook alweer op?

code:

Ranking Name Organization Solved Time A B C D E F G H 
29 Wasigh Hogeschool 's-Hertogenbosch 0 0   2 1 5

29e op de 32 deelnemers

[SWINX]

Op zondag 07 oktober 2001 12:36 schreef CyberSnooP het volgende:

edit:
Waarom doet mijn Euro teken () het niet?

Staat al een bericht over op www.topix.nl

[wasigh]

Op zondag 07 oktober 2001 16:20 schreef D2k het volgende:

[..]

gokje : mbravenboer zit op de UU

waar zat wasigh ook alweer op?

code:

Ranking Name Organization Solved Time A B C D E F G H 
29 Wasigh Hogeschool 's-Hertogenbosch 0 0   2 1 5

29e op de 32 deelnemers

Bekijk eerst ff de opgaven
(verder is het niet makkelijk om misselijk en met koppijn te programmeren (ACM en gerco kunnen dit bevestigen )
Er waren ook nogal wat universiteiten teams die niets goed hadden..
binnenkort EK

[wasigh]

Op zondag 07 oktober 2001 13:47 schreef Tizzwat het volgende:
Wasigh hogeschool ??

Yep, (surprised )

Hmm, je ziet bij de uitslag nu wel een echt verschil tussen uni. en hogeschool..

onze docent (java) had ook geen enkele opgave goed. Verder is de wedstrijd meer een wiskunde wedstrijd dan een programmeerwedstrijd..
Er zit denk ik nog een groot verschil tussen hogeschool en universiteit. namelijk dat wij vrijwel geen onderwijs krijgen algoritmiek e.d. maar vooral programmeren..

[mbravenboer]

wasigh: Verder is de wedstrijd meer een wiskunde wedstrijd dan een programmeerwedstrijd..

Goed punt (en reden waarom ik die wedstrijd (en wedstrijden hier) niet interessant vind).

Jammer dat het niet zo lekker ging, maar goed, zoals je zelf al zei is het niet echt een indicatie van iemands programmeer capaciteiten en zeker niet op het gebied van OO-design.

[elnino]

Op maandag 08 oktober 2001 10:53 schreef mbravenboer het volgende:

[..]

Goed punt (en reden waarom ik die wedstrijd (en wedstrijden hier) niet interessant vind).

Jammer dat het niet zo lekker ging, maar goed, zoals je zelf al zei is het niet echt een indicatie van iemands programmeer capaciteiten en zeker niet op het gebied van OO-design.

Misschien nog een leuke opdracht, dat ook al eerder in deze thread genoemd werd, namelijk:

ontwerp je eigen scripttaal (zoals php of VB-script). Niet speciaal iets voor het internet ofzo, maar meer iets als een macro (bijv. VBscript en JAVAscript).

[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.