Programmeer wedstrijd(je)

[PiepPiep]

Tijdens het zoeken op GoT kwam ik laatst een programmeer wedstrijd tegen, deze was alleen van een tijdje terug.
Daarom probeer ik er zelf maar een te organiseren.
Nu leek mij het leuk om het travalers salesman problem te gaan doen.
Probleem is als volgt heel simpel uitgelegt :

Zakenman moet langs een x aantal klanten.
Wat is de snelste weg.

Stel hij heeft 10 klanten, kan die kiezen uit 10, daarna 9, daarna 8 enz...
Dus mogelijkheden is 10! = 3628800
Nu heb ik 1000 coordinaten gemaakt, mogelijkheden
4,02387260077093773543702433923e+2567
Niet te doen om alles na te rekenen dus slimheid algoritme best wel belangrijk.

Kijk dus snel op http://home.planet.nl/~burg0484 voor de got.zip met 2 programma's.
genrnd.exe genereert de reeks met coordinaten.
checktry.exe check de reeks die je hebt berekent op de lengte.
verder nog de source van deze 2 en een file met de coordinaten in ascii text voor als je niet mijn generatie code kan/wil gebruiken.
Die checktry.exe staat er bij omdat er zeker weten met verschillende talen/os'en/weetikhet gaat worden gewerkt.
En aangezien niet elke taal precies hetzelfde afrond gebruiken we gewoon dit proggie.
genrnd.exe en checktry.exe zijn gecompiled met djgpp maar met borland C 4.5 geven ze dezelfde resultaten dus als het goed is zijn ze makkelijk te porten naar een andere taal, mits deze ook 16 bits en 32 bits integers ondersteund.

Snelste oplossingen wil ik gaan bijhouden op mijn site dus heb je er een die sneller is dan wat er staat kan je de getallen.uit file naar mij mailen.

Verdere vragen kan je mailen of in dit forum zetten.

Succes!

[ACM]

Het probleem is simpel... Er is alleen geen 'perfecte', simpele oplossing, omdat het probleem NPComplete is.
Het is niet zomaar een probleem, het is zo'n beetje _het_ probleem van de wetenschappelijke/wiskundige ICT. Dit lijkt me absoluut geen geschikt "programmeer wedstrijdje" probleem
Als dit probleem lineair (in minder dan exponentiele tijd iig) opgelost kan worden, kunnen _alle_ NPC-problemen zo opgelost worden...

De gene die hier een goede oplossing voor kan maken, zal zich niet bij jou, maar een organisatie als ACM.org moeten melden
Verder is het dus meer een wiskundig dan een programmeertechnisch probleem (wat ik sowieso het nadeel van al die programmeerwedstrijden vindt).

[ Voor 11% gewijzigd door ACM op 12-03-2003 21:24 ]

[Verwijderd]

En deze hebben we toch al es gedaan!?

[Glimi]

PiepPiep Je bent niet echt duidelijk in je start post imho, ik waar je over praat met je c programma met coordinaten, maar het lijkt me dat die voor elke deelnemer gelijk moeten zijn anders is de eerlijkheid ver te zoeken dus wat we aan genrnd hebben vraag ik me af . Verder zoek jij niet de snelste weg, maar de kortste

Ik zit hier dan ook met die zipfile, maar iets ermee te doen durf ik eig niet Kun je eerst even een MD5 hash hier posten voor controle ( beetje para )

Verder zie ik het nut niet zo van de 'wedstrijd'. Hoe lang het programma draait, hoe beter de banadering. Als ik sneller klaar ben dan X en langer laat draaien zijn mijn kansen veel hoger.
Het lijkt me een beter plan dat mensen eerst wat maken, voor een bep. periode insturen, en dat jij het dan op je pc gaat draaien voor een bepaalde tijd een aantal keer.

Als programmeur zou ik bij de afweging snelle generatie/ goede oplossing een overhand gaan krijgen voor evolutionaire algoritmes. Ik denk hierbij voornamelijk aan Extreme Optimalisation. Zie oa http://www.cs.uu.nl/docs/vakken/ici/NatureWay.pdf. Probleem is dat met het onderwerp van dit probleem er al 100, dan niet 100den 'oplossingen' bestaan die 1, 2 ,3 in te leveren zijn.
Misschien met iets meer orginaliteit een anders soortig probleem bedenken?

Als mod zijnde:
- Ik wil geen HK reply's in dit topic. Als je reageert, doe dit met technische inslag
- Volgende keer ff overlegen met de moderators voor zo'n contest, dan had ik m'n bovenstaande kritiek al kunnen uiten

[PiepPiep]

De punten zijn niet random, maar pseudo random, dus altijd dezelfde 'random' reeks dus iedereen heeft dezelfde punten.
De perfecte oplossing is denk ik ook niet te vinden, maar wel een kortere dan die van iemand anders.
Een ander soort probleem bedenken vind ik ook goed, ik heb alleen geen idee wat
Hoe ik een MD5 moet berekenen weet ik niet eens eerlijk gezecht
Mgoe.. anders deze niet doen en andere zoeken?
Ik ben wel in voor een leuke contest.

[Tomatoman]

PiepPiep schreef op 12 maart 2003 @ 22:01:
De perfecte oplossing is denk ik ook niet te vinden, maar wel een kortere dan die van iemand anders.

Dat geeft wel aan dat je niet precies weet wat de consequenties zijn van het probleem dat je hebt gekozen. Voor de efficiëntie waarmee je programma op zoek gaat naar de kortste weg is niet het programmeren de kunst, maar hoe goed je een beroemd wetenschappelijk optimalisatievraagstuk weet te vertalen naar wiskundige theorie.

Om de moeilijkheid van het handelsreizigersprobleem aan te geven: degene die de optimale oplossing van dit probleem weet te vinden, zal daar zeker de Nobelprijs voor ontvangen. En dit is geen grapje!

Mijn suggestie: zoek een andere programmeeruitdaging.

[SWfreak]

Het kan op zich wel hoor. Lees in een oud dictaat van mij dat het huidige record is 15.112 steden. Je kunt best een nieuw distributed project opstarten om dat record te breken (of waar het inmiddels maar op staat). Dat geeft echter meer een wiskundige challenge dan een programmeer challenge, omdat je hele slimme dingen moet bedenken om snel te rekenen.

Als dit niet de bedoeling is, zijn er best wel wat problemen te verzinnen die beter geschikt zijn voor een onderling wedstrijdje. Denk bijvoorbeeld aan een scheduling probleem (kan er misschien wel eentje verzinnen if needed).

[Eskimootje]

SWfreak schreef op 12 maart 2003 @ 22:29:

Kun je ff een spatie in je ondertitel zetten ? Je vernaggeld de lay-out

[Rukapul]

tomatoman schreef op 12 maart 2003 @ 22:23:
Om de moeilijkheid van het handelsreizigersprobleem aan te geven: degene die de optimale oplossing van dit probleem weet te vinden, zal daar zeker de Nobelprijs voor ontvangen. En dit is geen grapje!

Hoewel offtopic wil ik de mensen er hier op wijzen dat het je waarschijnlijk geen Nobelprijs oplevert: er is namelijk geen Nobelprijs voor de wiskunde. (De reden hiervoor zou zijn dat de vrouw van Nobel vreemd ging met een wiskundige!)

Maargoed, als je onder de 40 bent dan is een Fields Medal ook wel leuk (Aldus Ueli Maurer.)

On topic: moet een programmeerwedstrijd niet altijd een wiskundige insteek hebben? De rest rondom programmeren: beheersing syntax en programmeerconcepten, architecturele schoonheid etc. zijn of geen bruikbare metrieken of niet objectief/automatisch meetbaar. Je zult dus altijd de wedstrijd moeten houden om gegeven een bepaalde input een bepaalde output te generen en dat is meestal toch wiskundig/algoritmisch.

[ Voor 27% gewijzigd door Rukapul op 12-03-2003 22:40 ]

[Dash2in1]

Nee snelheid is wel objectief? In 999/1000 gevallen zal goeie c code sneller zijn dan bv. java.

[Tomatoman]

Dergelijke optimalisatievraagstukken hebben meestal een bedrijfseconomische achtergrond. Ik ben ervan overtuigd dat vervoersorganisaties zoals UPS miljoenen hebben uitgegeven aan onderzoek naar dit probleem. Een Nobelprijs voor de economie daarom zou best op zijn plaats zijn .

[SWfreak]

Wat er ook gebeurd, je krijgt iig een miljoen dollar als je het oplost. Zie http://www.claymath.org/Millennium_Prize_Problems/ en http://www.claymath.org/Millennium_Prize_Problems/P_vs_NP/

[Verwijderd]

Als ik zo zit te denken kom ik voor een programmeercontest ook op vooral wiskundige vraagstukken uit. De grootste contests zijn volgens mij vaak van wiskundige aard. Neem bijvoorbeeld het grootste priemgetal en ik meen mij ook iets te herinneren over het drie-deeltjes probleem. Hangen programmeren en wiskunde niet te sterk samen om zo'n strikt onderscheid tussen de twee te maken? Wat zou een betere uitdaging voor een contest zijn?

/misschien het interface component laten meetellen en jureren? Usability? Of denk ik helemaal verkeerd?

[ Voor 14% gewijzigd door Verwijderd op 12-03-2003 23:07 ]

[ACM]

Een programmingcontest zal best vaak een wiskundige insteek hebben. Maar om nou een probleem te nemen dat in principe uitsluitend in de wiskunde op te lossen valt, (muv brute-force) en wat daarna een vertaling van je algortime naar programma-code nodig heeft, is weer wat jammer imho.
Zeker dit probleem is wat onhandig in die zin, aangezien er nog geen enkele "snelle" oplossing voor is (wel redelijk snelle oplossingen die niet altijd geldig zijn of een semi-optimaal resultaat hebben).

[Verwijderd]

[rml][ All Languages]Alternatieve Programmeer Webstrijd[/rml]
dejavu

[YaPP]

Ik heb laatst op school een memory-allocator moeten schrijven in C++, en de resultaten moeten vergelijken met de rest..

Daarin zijn verschillende dingen te meten:
- malloc() / free() tijd..
- fragmentatie (versnipperde vrije blokken)
- overhead van de administratie-data.
- interne fragmentatie (verspilde ruime, omdat de allocator bijvoorbeeld blokken in 2-machten teruggeeft, dus meestal groter dan het aangevraagde gedeelte)
- verschillen van algoritmen en implementaties daarvan..

Is zoiets niet meer een idee voor een contest? :-/

Dit is dus gewoon een suggestie, misschien kunnen jullie er wat mee

[Tomatoman]

Kritiek spuien is veel gemakkelijker dan een aardig idee bedenken, dus laat ik ook maar eens een suggestie doen. Misschien ken je dit raadseltje wel.

Stel, je hebt een tabel van vier rijen bij vier kolommen. In iedere cel staat een geheel getal: minimaal 0 en maximaal 9. Een bepaald getal kan in meerdere cellen voorkomen. Nu zet je achter alle rijen de som van de vier getallen in die rij. Onder alle kolommen doe je hetzelfde: daar schrijf je het totaal van die kolom op. Tenslotte schrijf je bij beide diagonalen de som van de vier getallen in die diagonaal. Nu wis je alle getallen in de tabel, maar laat je de totalen staan.

De opgave: bereken zo snel mogelijk alle mogelijke oplossingen van welke getallen er in de tabel hadden kunnen staan.

Dit probleem heeft precies 10¹⁶ mogelijke oplossingen. Door wat slimme optimalisaties kun je het probleem echter terugbrengen tot een paar miljard mogelijke oplossingen. En die kun je vervolgens stuk voor stuk doorrekenen om ze te controleren. Niet al te moeilijk, maar ook niet heel eenvoudig. Je hoeft er niet voor zijn te afgestudeerd in de wiskunde. En het doorrekenen kost je (gelukkig) geen dagen.

Randvoorwaarden:

• Het gaat natuurlijk niet om de snelheid van je , maar om hoe snel je programma rekent.
• Mooie code is ook wat waard. Enne, over schoonheid valt best te twisten

OK allemaal, kom maar op met die kritiek!

[aatos]

tomatoman schreef op 13 maart 2003 @ 01:44:
Kritiek spuien is veel gemakkelijker dan een aardig idee bedenken, dus laat ik ook maar eens een suggestie doen. Misschien ken je dit raadseltje wel.

Stel, je hebt een tabel van vier rijen bij vier kolommen. In iedere cel staat een geheel getal: minimaal 0 en maximaal 9. Een bepaald getal kan in meerdere cellen voorkomen. Nu zet je achter alle rijen de som van de vier getallen in die rij. Onder alle kolommen doe je hetzelfde: daar schrijf je het totaal van die kolom op. Tenslotte schrijf je bij beide diagonalen de som van de vier getallen in die diagonaal. Nu wis je alle getallen in de tabel, maar laat je de totalen staan.

De opgave: bereken zo snel mogelijk alle mogelijke oplossingen van welke getallen er in de tabel hadden kunnen staan.

Dit probleem heeft precies 10¹⁶ mogelijke oplossingen. Door wat slimme optimalisaties kun je het probleem echter terugbrengen tot een paar miljard mogelijke oplossingen. En die kun je vervolgens stuk voor stuk doorrekenen om ze te controleren. Niet al te moeilijk, maar ook niet heel eenvoudig. Je hoeft er niet voor zijn te afgestudeerd in de wiskunde. En het doorrekenen kost je (gelukkig) geen dagen.

Randvoorwaarden:

• Het gaat natuurlijk niet om de snelheid van je , maar om hoe snel je programma rekent.
• Mooie code is ook wat waard. Enne, over schoonheid valt best te twisten

OK allemaal, kom maar op met die kritiek!

Volgens mij kan je het aantal door te rekenen oplossingen zo terugbrengen tot 10^8:

We nemen de velden als volgt:

code:

               X

A1 B1 C1 D1   R1
A2 B2 C2 D2   R2
A3 B3 C3 D3   R3
A4 B4 C4 D4   R4

A  B  C  D    Y

A, B, C, D, R1, R2, R3, R4, X en Y zijn gegeven.

Je zou voor A1..D4 nu alle combinaties van getallen tussen 0 en 9 kunnen invullen en dan de boel doorrekenen. Dat zijn echter 10^16 mogelijkheden.

Nu de truc: We rekenen alleen alle combinaties door van A1, A2, A3, B1, B2, C1, C2, en C3. Dat zijn 10^8 mogelijkheden.

Wat moet er per keer doorgerekend worden?

allereerst gaan we de ontbrekende getallen berekenen. Dat gaat als volgt (de waarden die berekend worden aan de hand van andere waarden zijn aangeduid met ' :

'D1=R1-A1-B1-C1
'D1=R2-A2-B2-C2
'A4=A-A1-A2-A3
'C4=C-C1-C2-C3
'B3=X-'A4-C2-'D1
'B4=B-B1-B2-'B3
'D3=R3-A3-'B3-C3
'D4=R4-'A4-'B4-'C4

mocht het programma ergens een getal berekenen dat niet tussen 0 en 9 is kan hij kappen en verder met de volgende combinatie.

Alle getallen zijn nu ingevuld. Nog slechts twee controlestappen zijn nu nodig:

'D='D1+'D2+'D3+'D4
'Y=A1+B2+C3+D4

nu wordt gekeken of 'D=D en 'Y=Y. is dat beide het geval, dan worden de getallen als oplossing weggeschreven.

Daarna verder met de volgende combinatie!


slechts 100 miljoen oplossingen doorrekenen! dat is net weer iets minder dan een paar miljard


oh ja, ik ga dit niet coden, zelfs met mijn beperkte progammeerervaring is dit natuurlijk vrij makkelijk te maken, maar ik heb er nu geen tijd voor.

edit: er is nog wel wat optimalisatie mogelijk. Zo zou je eerst A1..A3 kunnen bepalen, dan R1-A1-A2-A3='A4 laten berekenen, en dan al kijken of het getal tussen 0 en 9 is. Is dat niet het geval, dan hoeven alle andere combinaties met die waarden voor A1..A3 niet meer doorgerekend te worden. Als het wel tussen 0 en 9 is, ga je B1..B3 op dezelfde manier invullen en berekenen, etc etc

Dit bespaart een boel tijd, maar je krijgt er wel wat minder overzichtelijke code door.

[ Voor 24% gewijzigd door aatos op 13-03-2003 03:46 ]

[crisp]

Ik ben momenteel bezig met deze programmeer wedstrijd. Ook een behoorlijke opgave; het heeft me in eerste instantie al een paar dagen gekost om een algorithme te ontwikkelen dat op een vrij simpele manier een 50x50x8 grid oplost binnen de gestelde tijd.