Veckans problem nr2 - 1bit bitmap to vector

Bara för att man har snabbast kod i en optimeringstävling betyder ju det tex inte att man har snyggast ide osv... Tycker vi kan ha förutom den som har snabbast/minst vad man nu än tävlar i även kan ha lite hedersomnämningar, typ bäst försök, smartast ide osv...
eller som pelle76 sa en klass för varje språk.

Ett slags förslag. (Som kanske påminner för mycket om den gamla...)

Du presenterar olika svartvita kartor. Med en startpunkt och en målpunkt. (Röd resp. blå i mitt exempel). Sedan ska man ta sig från röd till blå under följande regler:

* Man får inte röra de svarta.
* Man får bara gå "rakt".

Sedan ser vi vem som skriver bästa algoritmen som hittar en lösning med minst antal "vändpunkter". Alltså sådana punkter där man stannar upp och väljer att gå åt ett annat håll. Om två personer kommer på en lösning med minst antal vändpunkter så går man efter kortast sammanlagda längd av linjerna.

Eller... Kanske inte. Det var bara ett förslag.

Tanken med programmet är alltså att det är nog jäkligt lätt att skriva en lösning där man hittar till mål. Men att göra det med minst antal vändpunkter gör det hela mycket klurigare. Kanske?

Fast jag har inte en jäkla aning om hur man ens börjar på en algoritm som hittar i mål.

Bra ide... Men man borde få gå rakt fram om kartan tillåter det.

Gillar Sims idé!

Edit: Psionicists också.

Man kan göra ett program som löser en labyrint.

det problemet låter helgrymt, detta är ju ett idealiskt problem för mig att lösa. synd att jag bara kan teorin och inte kan programmera så bra i nått språk...

(om nån vill veta vad jag menar inför en eventuell sådan tävling som Sim föreslår så kan ni höra av er)

förresten vad är "rakt fram" för en massa små raka streck blir ju en "böj". iofs man kan begränsa antalet "vändpunkter" mellan "A" och "B"...

Sims idé var bra. Går kanske att göra med PHP och GD också, då kanske jag kan vara med.

EDIT: Psionicists problem var också bra.
EDIT2: Men då är frågan vad man skulle tävla om? En laborint går bara att lösa på ett sätt. Hastighet i koden vinner C/C++ och Assembler lätt och rader kod är bara att skriva allt på en rad.

Jo. Jag var inne på det också först. Men gamla hederliga labyrintlösningar går vi till och med igenom på högskolan, så det känns som att utmaningen blir mindre. De flesta kommer nog på den optimala lösningen till labyrinten och då blir det väldigt många "oavgjort".

Missade jag något? Går inte linjen upp på "Bästa lösning"?

Annars kan vi ju hämta inspiration från denna veckas tävling och skriva ut kordinaterna för vändpunkterna, då kollar man bara att y-kordinat för punkt n >(=) n+1

Jo. Varför skulle den inte få det?

Sim:
Din "Bästa lösning" var väl ändå inte så bäst?

Två som är bättre:
http://www.home.no/zevon/swec/map.PNG

EDIT:
typiskt att home.no går ner just då man lagt upp bilden.. Aja..
Här då:
http://upl.silentwhisper.net/uplfolders/upload5/map2.PNG

Oj, läste "rakt ner"

Sims röstar jag på. Går nog att lösa på en helvetes massa roliga sätt.

Labyrint blir lite för lätt känns det som.. Men mest för att man har redan pluggat liknande i "Aloritmer och datastruktur" på lth

jag röstar för sims förslag
samma bildformat som förra gången eller?

Sims röstar jag också på. Verkar vara ett lika roligt problem som förra.
(tror dessutom att jag redan har kommit på en lösning )

Yeah.. Och samma format på lösningarna.

Sen om matricks hade bara kunnat modifiera den gamla viewern att läsa in och se att strecken inte går över några 'blobbar' så hade det bara varit att köra igång

Hehe. Jag slog dig

http://upl.silentwhisper.net/uplfolders/upload4/map3.PNG

Samma antal punkter, men kortare väg

Haha, nytt nätverksspel på gång kanske?
"Hitta snabbaste vägen, ett roligt spel för 2-4 personer!"

haha

Sims... Kanske du skulle ta och komma på lita brar regler och förutsättningar så kan du ju presentera dom på fredag 18:00 i en ny tråd eller? Så kör vi till nästa söndag (9 dagar).

Nenene. Jag har tentavecka. Sedan gjorde Matricks ett så jäkla bra jobb sist så jag överlåter det åt honom.

Kör gärna Sims nästa vecka... ni kan väl ha någon tråkig tävling denna vecka, så man inte missar något.

aye

edit: damn.. då har jag ju tenta.. aja bra förslag iallafall

Ja för fan!

ja

Ja ja ja