[GPC opgave 2] Oplossingen

[D2k]

In het kader van beter laat dan nooit (sorry druk druk druk)

De jury testset

code:

5
hell 5
hello 4
idea 8
next 8
super 3
3
324450
32210
380

en de uitvoer

code:

h
he
hel
hell
hello

h
he
ide
idea

h
onmogelijk

Hier gingen er aardig wat de mist op in

[Verwijderd]

misschien handig als je er even een link naar de vraag bij zet?

[RickN]

Geintje zeker....
Was DIT de testset, heb ik daarvoor een boom datastructuur gemaakt waarmee ik in O(n) een codewoord kon opzoeken???

DAMN!

[Orphix]

dus als het voorbeeld het deed, dan was het goed??
hmm maar goed dat ik niet al te intensief heb getest

[D2k]

Op maandag 17 december 2001 13:47 schreef hezik het volgende:
misschien handig als je er even een link naar de vraag bij zet?

jij doet niet mee zeker??
[topic=340659/1/25]

[D2k]

Op maandag 17 december 2001 13:48 schreef RickN het volgende:
Geintje zeker....
Was DIT de testset, heb ik daarvoor een boom datastructuur gemaakt waarmee ik in O(n) een codewoord kon opzoeken???

DAMN!

het ging om de truc

[wasigh]

Op maandag 17 december 2001 13:48 schreef Orphix het volgende:
dus als het voorbeeld het deed, dan was het goed??
hmm maar goed dat ik niet al te intensief heb getest

Dit is net iets anders als de voorbeeld testset

[Orphix]

ik vond het al zo raar dat die goed was met dit progje

code:

int main(int argc, char* argv[])
{
cout << "h
he
hel
hell
hello
h
he
ide
idea

h
onmogelijk" << endl;
return 0;
}

(pff ja niet gaan zeuren over de newlines he)

[D2k]

Op maandag 17 december 2001 13:52 schreef wasigh het volgende:

[..]

Dit is net iets anders als de voorbeeld testset

code:

5
hell 3
hello 4
idea 8
next 8
super 3
3
324450
32210
380

zoek de verschillen

code:

i
id
hel
hell
hello
i
id
ide
idea
i
onmogelijk

[Orphix]

ooooh

[Twilight Burn]

En wij moesten dat programma bouwen voor 1000 woorden van 50 tekens....

[wasigh]

Op maandag 17 december 2001 14:16 schreef Twilight Burn het volgende:
En wij moesten dat programma bouwen voor 1000 woorden van 50 tekens....

that's life

(waar moeten in een halve dag zo'n testset vandaan halen met goede uitkomst?)

[D2k]

Op maandag 17 december 2001 14:16 schreef Twilight Burn het volgende:
En wij moesten dat programma bouwen voor 1000 woorden van 50 tekens....

ja
daar moeten de mods uit de opgave natuurlijk wel mee kunnen werken

<edit>
damn wasigh
das ook voor het eerst dat je sneller bent

[Wokker]

Kan niemand hier een werkende versie plus source code kunnen posten ??
Kan ik er mischien nog wat van leren
Alvast bedankt !!

[Orphix]

Ik vraag me af hoeveel mensen hier hun opdrachten goed met commentaar voorzien
Ik denk dat je aan mijn code weinig zult hebben iig (C++), ik zit on-the-fly wat te programmeren bij dit soort dingen eigenlijk

[Wokker]

Op maandag 17 december 2001 16:10 schreef Orphix het volgende:
Ik vraag me af hoeveel mensen hier hun opdrachten goed met commentaar voorzien
Ik denk dat je aan mijn code weinig zult hebben iig (C++), ik zit on-the-fly wat te programmeren bij dit soort dingen eigenlijk

oHh maakt niet zo uit
ik wil gewoon ff kijken
of mag dat niet ??

[Munters]

Op maandag 17 december 2001 16:17 schreef Wokker het volgende:

[..]

oHh maakt niet zo uit
ik wil gewoon ff kijken
of mag dat niet ??

Je mag mijn oplossing best hebben / inzien hoor.
Maar het bestaat uit 161 regels, dus minder geschikt om hier neer te zetten denk ik.

Hier volgt alvast een voorproefje, de main routine:

int main(int argc, char *argv[])
{
Init();
DictRead();
HandleInput();
}

Kan niet fout zijn toch? Als je de rest ook wilt, geef maar je mailadres. (Ik geef er overigens geen uitleg bij).

[RickN]

Op maandag 17 december 2001 16:32 schreef Munters het volgende:

[..]

Hier volgt alvast een voorproefje, de main routine:

code:

int main(int argc, char *argv[])
{
  Init();
  DictRead();
  HandleInput();
}

Mooie "seperation of concerns"

[Orphix]

Ik heb het even online gezet. hier kan je het vinden. Als je weet hoe iets beter moet, zeg het me dan!

[Verwijderd]

Lol, leuke testset.
Het verbaast me dat er hier veel de mist in gingen.
Ik denk dat met deze set er nog veel meer de mist in zouden gaan :

code:

4
got 10
hebben 20
houden 2
geheel 2
1
3570

Waar zit de moeilijkheid ? Wel, in het feit dat iedereen vertrekt met een h (20+2 > 10+2), en daarna in die richting verder gaat. En dus met 'ho' voor de dag komt na de 5, om dus te eindigen met 'hou'. Helaas, want 'go' heeft hogere prioriteit dan 'ho'...en dus met het 'go' en dan 'got' zijn. Als de jury ff wil hertesten met deze

[Orphix]

code:

h
go
got

die van mij struikelt er niet over

[RickN]

mijne ook niet hoor...

[Dash2in1]

mijne ook niet ..

[Verwijderd]

Hmm, ik zei ook niet dat iedereen z'n prog er over zou vallen... De betere doen 't toch wel hoor, daar twijfel ik niet aan...

Maar ik kan me inbeelden dat als je de 'jury-val' niet overleefd, dat je die van mij ook niet overleefd. En dat er dan nog zijn die die van de jury overleven, maar de mijne niet. Snappie ? Ik wou ff de behoorlijke oplossingen van de uitstekende scheiden zie je

[Verwijderd]

Mijn oplossing Web-pagina en javascript console-app.

Algoritme:
Laad de library per woord. Ik houd per (deel)woord een lijst bij wat de prioriteit is :

woord-lengte:[deel-woord:prio,...]
1:[h:7,i:8,n:8,s:3]
2:[he:7,id:8,ne:8,su:3]
3:[hel:7,ide:8,nex:8,sup:3]
4:[hell:7,idea:8,next:8,supe:3]
5:[hello:4,super:3]

en per positie houd ik bij welke letters mogelijk zijn:

string-positie:[lijst-mogelijke-letters]
0:[h,i,n,s]
1:[e,d,u]
2:[l,e,x,p]
3:[l,a,t,e]
4:[o,r]

Dit alles per relatief snelle objecten (associatieve array) in een array.

Daarna ga ik recursief de woorden proberen. Onmogelijke letters probeer ik niet (op positie 1 het cijfer 1 kan bijv. niet). Structuur:

<invoer:=mogelijke-letters,...>
<324450:=hi,de,l,l,o>
<32210:=hi,de,e,a>
<380:=hi,>
<8173330:=,,,,,>

Het enige jammerre is: ik stop de te proberen string steeds weer op de stack, omdat je in javascript niet het laatste teken van de string af kunt kappen. Dingen als str.length-- werkt niet
Heeft iemand nog een idee om dat recursieve gedoe wat efficienter te doen?

Btw: dit is m'n eerste zelfbedachte recursie-algoritme (op school heb ik natuurlijk fibonacci, faculteit, doolhofoplossen gemaakt, maar dit is toch anders). Maare, het wordt niet m'n hobby.

edit:
Zo'n lang verhaal schrijf je nooit in 1 keer goed

[Munters]

Op maandag 17 december 2001 16:36 schreef RickN het volgende:

[..]

Mooie "seperation of concerns"

Ja, voor de rest is het een takkenzooi.
(Een weight-balanced 26-voudige boomstructuur dus).

[Verwijderd]

Op maandag 17 december 2001 16:32 schreef Munters het volgende:
Kan niet fout zijn toch? Als je de rest ook wilt, geef maar je mailadres. (Ik geef er overigens geen uitleg bij).

Ik zou wel eens willen zien wat er in je Init() staat ;): [e-mail]

[Orphix]

Toch leuk om andere oplossingen te lezen, zoals Doekman. Niet elke keer zoeken, maar gewoon een data-structuur ontwerpen voor elke mogelijke zoek-actie

(gelukkig voor jou dat de test set niet zo groot was )

[RickN]

Op maandag 17 december 2001 23:45 schreef Munters het volgende:

[..]

Ja, voor de rest is het een takkenzooi.
(Een weight-balanced 26-voudige boomstructuur dus).

Ik heb ook een boomstructuur. De mijne is tienvoudig en elk pad geeft de codering van een woord uit de library aan. Deel paden bevatten dus de codering deelwoorden. Een (deel)pad bevat alleen het (deel)woord met de hoogste prioriteit. Een (deel)woord dat dus nooit opgevraagd kan worden (omdat het een te lage prioriteit heeft) wordt dus uiteindelijk niet in mijn boom opgeslagen. Het opzoeken van een code woord bestaat nu nog uit het het volgen van het bijbehorende pad door de boom (dat dus helemaal bepaald wordt door de cijferreeks van het gecodeerde woord) en onderweg alle (deel)woorden die je tegenkomt af te drukken. Da's mooi O(n) dus, met voor n de lengte van het codewoord. Sneller opzoeken kan niet .

[wasigh]

nice