[GPC] opgave 3

[RickN]

Op vrijdag 14 december 2001 23:22 schreef wasigh het volgende:

[..]

jawel
(((((((((((((((1+2))))))))))))))) *3 mag niet

MMM, ik heb deze vraag al vrij snel nadat de opgave was gepost gestelt en ik heb daar toen nooit een antwoord op gekregen. Ik ben er toen vanuit gegaan dat haakjes gebruikt mogen worden waar ze de zaak verduidelijken (dus niet alleen waar ze absoluut noodzakelijk zijn.

D.w.z. 1*2+3*4=14 heeft in principe geen haakjes nodig, maar ik ben ervan uit gegaan dat (1*2)+(3*4)=14 ook goed wordt gerekend.....

[Dash2in1]

Op vrijdag 14 december 2001 23:28 schreef Theswitch het volgende:

[..]

Ik heb bij cijfers en letters nog nooit negative getallen gezien, dus hier ook niks negatief. De invoer klopt dus niet

Ok, helder. Vraag me dan echter af waarom er staat dat alleen de eerste niet negatief mag zijn ?!

[kvdveer]

De opdracht is zeer duidelijk (complimenten) maar ik heb toch nog een vraagje:
is / een integer division of een gewone deling?

oftewel:
(1/2)*2 = 0 ?
(1/2)*2 = 1 ?

[Orphix]

Alleen gehele getallen worden gebruikt bij de invoer en antwoord. Echter tussendoor zijn wel niet-gehele getallen toegestaan. Bijvoorbeeld (3/4)*4 = 3.

dus (1/2)*2 = 1.

[kvdveer]

oeps... beter lezen...

Nu ik toch aan het zeiken ben... er staan geen bereiken voor de invoerwaarden. Mogen we 32-bits integers aannemen?

[Verwijderd]

Vraag: geldt de limiet van 10/20 minuten voor elke mogelijke invoer? [Zo staat het in de opgave, maar weten jullie dat zeker :)]

[kvdveer]

Op zaterdag 15 december 2001 03:02 schreef DiFool het volgende:
Vraag: geldt de limiet van 10/20 minuten voor elke mogelijke invoer? [Zo staat het in de opgave, maar weten jullie dat zeker :)]

Zo staat het in de opgave, en zo is het dus.
Dat is trouwens wel een poosje wachten voor de juri .

BTW... volgens mij haalt mijn algo de meeste combinaties van 7 in binnen 100 ms. Het is dus mogelijk.

[kvdveer]

code:

   39 ms 1 + 7 + 173 + 406 + 55 + 135 + 8 + 9 + 10 x (2 - 64) - 33 = 141
  220 ms 169 + 12 + 59 + 1.835 + 74 + 15 + 4 + 17 - 4 - 140 - 66 - 155 = 658
   30 ms 94 + 50 + 166 + 559 + 97 + 30 + 58 + 20 + 18 + (175 + 20) / 10 = 1.654
    0 ms 5 + 29 + 29 + 1.002 + 5 + 119 + 14 + 14 + 12 - 15 - 16 - 2 = 412
  149 ms 137 + 119 + 192 + 1.289 + 200 + 136 + 2 + 2 * 10 / 16 - 18 - 49 = 1.019
   10 ms 115 + 191 + 137 + 678 + 2 + 142 + 198 + 15 + 4 * 3 / 15 - 19 = 1.568
   81 ms 118 + 173 + 138 + 576 + 19 + 126 + 6 + 11 + 11 + 20 - 176 - 57 = 348
 6109 ms 32 + 54 + 36 + 1.154 + 15 + 2 + 2 x (122 + 15 x (32 - 58)) - 100 = 119
  160 ms 22 + 160 + 162 + 764 + 123 + 17 + 3 - 17 - 99 - 17 - 149 - 88 = 186
   10 ms 14 + 13 + 39 + 1.346 + 46 + 115 + (7 + 7 + 7 - 14 - 74) / 51 = 1.384
   10 ms 181 + 64 + 96 + 593 + 154 + 149 + 111 + (12 * 18 / 9 - 145) / 11 = 1.337
   20 ms 23 + 95 + 81 + 230 + 11 + 110 + (17 + 19 + 14 x (17 + 19)) / 135 = 554
  139 ms 141 + 147 + 100 + 1.328 + 32 + 47 + 2 x (3 + 20 + 7 x (73 - 190)) = 203
   10 ms 174 + 111 + 140 + 202 + 134 + 4 + (19 + 7 * 9 - 181) / 11 - 62 = 694
   30 ms 71 + 98 + 15 + 1.702 + 153 + 37 + 99 + 9 + 9 - 5 - 185 - 18 = 1.614
   29 ms 118 + 22 + 125 + 1.856 + 109 + 66 + 20 + 13 + 90 x (4 - 14) - 46 = 1.383
   40 ms 109 + 20 + 150 + 298 + 47 + 177 + 1 + 4 + (4 - 143) / 4 - 88 = 19
    0 ms 76 + 79 + 73 + 165 + 91 + 101 + 93 + 17 + (17 + 12) / 8 - 6 = 1.165
   10 ms 175 + 122 + 52 + 1.394 + 112 + 176 + 13 + 10 x (16 - 73) - 5 - 73 = 1.396
  130 ms 168 + 151 + 181 + 373 + 156 + 54 + 141 + (10 - 141) / 20 - 4 - 1 = 449
    0 ms 180 + 65 + 173 + 1.527 + 194 + 55 + 80 + 5 + 5 / 2 - 11 - 1 = 845
   10 ms 1 + 31 + 142 + 625 + 80 + 110 + 31 x (6 + 15) - 7 - 2 - 53 = 1.578
   80 ms 132 + 114 + 180 + 44 + 52 + 177 + 4 + 7 + 4 * 9 - 9 - 137 = 287
   10 ms 1 + 106 + 153 + 1.141 + 47 + 173 + (98 / 2 - 14) / 5 - 8 - 13 = 1.607
   40 ms 105 + 84 + 8 + 1.985 + 33 + 10 + 3 + 20 + 5 x (12 - 20) - 21 = 1.527
   79 ms 197 + 100 + 7 + 1.188 + 161 + 185 + (103 + 18 + 15 x (133 + 20)) / 16 = 1.989
  351 ms 147 + 157 + 4 + 733 + 64 + (18 + 157 x (53 + 18) - 1 - 19) / 15 = 1.848
 1832 ms 98 + 138 + 76 + 845 + 150 + 11 + 69 + (69 * 20 - 3) / 126 - 20 = 48
  289 ms 124 + 72 + 103 + 1.293 + 163 + 4 x (20 x (10 + 5) / 100 - 191) - 128 = 875
  831 ms 138 + 152 + 7 + 1.226 + 161 + 16 + (127 + 16) / 2 - 18 - 93 - 34 = 860
35310 ms 110 + 104 + 147 + 1.790 + 170 + (19 + 1 + 110 - 15 - 1 - 121) / 1 = 18

even opscheppen...

[edit] even een mooie piek van 35 seconden toegevoegd.

[Dash2in1]

Hey,

Doet hij het bij jullie ook met
9 9 9 9
324
?

Kwam er net achter dat me programma daarop dus niet werkt

[Twilight Burn]

Op zaterdag 15 december 2001 11:30 schreef Dash2in1 het volgende:
Hey,

Doet hij het bij jullie ook met
9 9 9 9
324
?

Kwam er net achter dat me programma daarop dus niet werkt

(9+9)*(9+9)
00:00:00.0800808

[Munters]

Op zaterdag 15 december 2001 03:24 schreef kvdveer het volgende:

[..]
10 ms 115 + 191 + 137 + 678 + 2 + 142 + 198 + 15 + 4 * 3 / 15 - 19 = 1.568
10 ms 14 + 13 + 39 + 1.346 + 46 + 115 + (7 + 7 + 7 - 14 - 74) / 51 = 1.384
[..]
even opscheppen...

1.568? 1.346? 1.384?
Het is extreem snel imo.
Maaruh... snap je de opgave eigenlijk wel?

[RickN]

Op zaterdag 15 december 2001 12:37 schreef Munters het volgende:

[..]

1.568? 1.346? 1.384?
Het is extreem snel imo.
Maaruh... snap je de opgave eigenlijk wel?

Ja, ik moest hier ook even 10 keer naar kijken, maar 1.568 is gewoon 1568

Maar verder, die metingen zeggen idd niet zoveel als je er niet bij zegt wat je hebt gemeten. Daarnaast zijn het natuurlijk wel extreem eenvoudige expressies die je daar berekent (bijna alleen plusjes)

En het is wel een beetje erg snel. Lijkt "to good to be true" en dat is het dan meestal ook. Garandeerd jouw algoritme dat er een uitkomst wordt gevonden als er een is (ook als er b.v. maar 1 goede oplossing is?)

[Verwijderd]

Op zaterdag 15 december 2001 03:24 schreef kvdveer het volgende:
Cijfers

Oke, maar probeer eens 7 cijfers, allemaal heel groot [dus geen 100 of zo], en niet mooi [geen 1000000], waar geen oplossing voor is, hoe snel is die dan?

[Dash2in1]

Op zaterdag 15 december 2001 12:49 schreef DiFool het volgende:

[..]

Oke, maar probeer eens 7 cijfers, allemaal heel groot [dus geen 100 of zo], en niet mooi [geen 1000000], waar geen oplossing voor is, hoe snel is die dan?

1234124 1234897 12351 9871235 8723451 12340975 1295871
0
41229 ms

Is dat snel? Enn, ach, maakt toch niet heel veel uit als het snel is, want zoals eerder gezegd 9 9 9 9 = 324 vindt ie (nog) niet.

[D2k]

Op zaterdag 15 december 2001 03:10 schreef kvdveer het volgende:

[..]

Zo staat het in de opgave, en zo is het dus.
Dat is trouwens wel een poosje wachten voor de juri .

* D2k gaat ff een tukkie doen tijdens het controleren

ff wat duurt dat soms lang zeg
of onze testset is te moeilijk voor de bruteforce

[Theswitch]

Op zaterdag 15 december 2001 02:41 schreef kvdveer het volgende:
oeps... beter lezen...

Nu ik toch aan het zeiken ben... er staan geen bereiken voor de invoerwaarden. Mogen we 32-bits integers aannemen?

Ja hoor, da's meer als genoeg lijkt me zo

[Theswitch]

Op zaterdag 15 december 2001 13:25 schreef D2k het volgende:

[..]

* D2k gaat ff een tukkie doen tijdens het controleren

ff wat duurt dat soms lang zeg
of onze testset is te moeilijk voor de bruteforce

Als je er iets in perl hebt of in windows/exe kan je ook wat naar mij sturen hooor.

[D2k]

Op zaterdag 15 december 2001 14:36 schreef Theswitch het volgende:

[..]

Als je er iets in perl hebt of in windows/exe kan je ook wat naar mij sturen hooor.

k
tnx
ik ga je er nu eens sturen

[D2k]

Op zaterdag 15 december 2001 03:02 schreef DiFool het volgende:
Vraag: geldt de limiet van 10/20 minuten voor elke mogelijke invoer? [Zo staat het in de opgave, maar weten jullie dat zeker :)]

ja

[Theswitch]

Volgens mij is deze opgave niet zo populair aan het aantal reacties te zien.

Verder, hoe zit 't met de uitslag van opgave 2 jury?

[Verwijderd]

Ik heb echt geen idee hoe ik 't moet aanpakken (nouja brute force snap ik wel maar dan krijg je meer dan een miljard iteraties dus dat haal je niet qua tijd) dus dan is de opgave vrij snel niet meer interessant. Als iemand nu een tipje van de sluier zou kunnen oplichten in goed overleg met de jury dan zou de opgave wel weer interessant worden want dan kan je iig aan de slag ..

[wasigh]

Op zondag 16 december 2001 14:01 schreef eXoR het volgende:
Ik heb echt geen idee hoe ik 't moet aanpakken (nouja brute force snap ik wel maar dan krijg je meer dan een miljard iteraties dus dat haal je niet qua tijd) dus dan is de opgave vrij snel niet meer interessant. Als iemand nu een tipje van de sluier zou kunnen oplichten in goed overleg met de jury dan zou de opgave wel weer interessant worden want dan kan je iig aan de slag ..

de 1e goede oplossing die we binnen hadden was een bruteforce oplossing dus het is zeker mogelijk!

[Verwijderd]

Op zondag 16 december 2001 14:29 schreef wasigh het volgende:

[..]

de 1e goede oplossing die we binnen hadden was een bruteforce oplossing dus het is zeker mogelijk!

was dat mijn inzending? en zo nee, is die van mij al getest?

[D2k]

Op zondag 16 december 2001 14:43 schreef crashburn het volgende:

[..]

was dat mijn inzending? en zo nee, is die van mij al getest?

nee en nee
hij ligt bij een java man te w88 op controle

[Verwijderd]

Op zondag 16 december 2001 14:44 schreef D2k het volgende:

[..]

nee en nee
hij ligt bij een java man te w88 op controle

Is de testset die gebruikt word om de inzendingen te testen eigenlijk ergens vandaan te halen?

[D2k]

Op zondag 16 december 2001 14:55 schreef crashburn het volgende:

[..]

Is de testset die gebruikt word om de inzendingen te testen eigenlijk ergens vandaan te halen?

noopz
die wordt achteraf pas bekend gemaakt

[kvdveer]

Op zaterdag 15 december 2001 12:42 schreef RickN het volgende:

[..]

Ja, ik moest hier ook even 10 keer naar kijken, maar 1.568 is gewoon 1568

Maar verder, die metingen zeggen idd niet zoveel als je er niet bij zegt wat je hebt gemeten. Daarnaast zijn het natuurlijk wel extreem eenvoudige expressies die je daar berekent (bijna alleen plusjes)

En het is wel een beetje erg snel. Lijkt "to good to be true" en dat is het dan meestal ook. Garandeerd jouw algoritme dat er een uitkomst wordt gevonden als er een is (ook als er b.v. maar 1 goede oplossing is?)

het zijn willekeurig gegenereerde variabelen. (ik geloof dat het vierkeer random(2000) was, 3xrandom(500) en twee keer random(20). Dat er plusjes en minnetjes uit komen is verklaarbaar: mijn algo geeft die grotere voorkeur, en als er meerdere oplossingen zijn, dan komen er dus antwoorden met plusjes en minnetjes uit.

Het algo is niet volledig. Het vindt ongeveer 90% van de antwoorden. als het antwoord niet gevonden wordt, dan probeer ik met een veel intensievere algo alsnog de oplossing te vinden.

[Verwijderd]

Op zondag 16 december 2001 14:29 schreef wasigh het volgende:

de 1e goede oplossing die we binnen hadden was een bruteforce oplossing dus het is zeker mogelijk!

Mja, tuurlijk is dat mogelijk. Omdat het zelden gebeurt dat je via brute force echt tot de laatste mogelijkheid moet zoeken. Als dat toch 't geval is, tja, dan ben je de klos...
Want ff rap gerekend moet de brute force die ik zo snel bedenk niet minder dan 10.899.947.520 mogelijkheden testen (bij 7 getallen als input dus). Als dat binnen de 20 minuten moet, dan moet ie er dus meer dan 9 miljoen testen per seconde in het allerslechtste geval. Vergeet dat dus maar Want op de testmachine (dacht PIII 700) komt dat heel grofweg overeen met een 70tal machine-instructies per test. Juist ja... Of zouden we 't toch maar in asm gaan doen ?

[Theswitch]

Ik denk niet dat dit een spoiler is, maar gewoon een ideetje

code:

(1*2) + (3*4) 
(3*4) + (1*2)
(2*1) + (3*4)
etc

zijn allemaal dezelfde berekeningen he

[Verwijderd]

Op zondag 16 december 2001 16:17 schreef Theswitch het volgende:
Ik denk niet dat dit een spoiler is, maar gewoon een ideetje

code:

(1*2) + (3*4) 
(3*4) + (1*2)
(2*1) + (3*4)
etc

zijn allemaal dezelfde berekeningen he

Jaja, I know...
Maar checken of je niet 't zelfde uitrekent kost meer tijd dan 't nog eens uitrekenen
En bovendien : juist daarom zal een brute force nooit (of toch met probabiliteit 0) alles moeten nagaan, en kan 't dus werken

[kvdveer]

Op zondag 16 december 2001 16:17 schreef Theswitch het volgende:
Ik denk niet dat dit een spoiler is, maar gewoon een ideetje

code:

(1*2) + (3*4) 
(3*4) + (1*2)
(2*1) + (3*4)
etc

zijn allemaal dezelfde berekeningen he

Ik denk wel dat het een spoiler is... op dit concept kan een bruteforce mechanisme behoorlijk strepen in het aantal mogelijkheden...
(hierop is mijn brute force backup-mechanisme gebaseerd)

[Theswitch]

Op zondag 16 december 2001 17:06 schreef kvdveer het volgende:

[..]

Ik denk wel dat het een spoiler is... op dit concept kan een bruteforce mechanisme behoorlijk strepen in het aantal mogelijkheden...
(hierop is mijn brute force backup-mechanisme gebaseerd)

Nah, laat wazigh de boel maar doorstrepen, ik denk dat iedereen dit zelf wel kan bedenken. En zoals boven gezegd: uitrekenen gaat misschien net zo snel.

Verder weet ik wel een andere manier om sneller tot een antwoord te komen, maar die hou ik nog maar ff voor mezelf,.

[Munters]

ok probeer dees dan maar eens op te lossen met jullie tooltjes
1 8 9 9
1

Even geprobeerd, en het progje komt met een aanzienlijker simpeler antwoord als waar ik aan gedacht had....

Probeer eens voor hetzelfde principe (I guess):
2 7 10 14
1

Ook iedereen aan:
0
0

gedacht?

Dus nu heb ik wel iets dat alles vind, maar met maximaal 14 * 10^9 iteraties
Geldt ook als randvoorwaarde dat het maximaal 20 minuten op een Cray mag draaien?


Komt er trouwens nog een uitslag van opgave 2? Ik begrijp dat jullie het druk hebben, maar de animo neemt danig af. Mijn interesse op dat algoritme nog eens met anderen te analyseren is inmiddels tot het nulpunt afgenomen.

[D2k]

Op maandag 17 december 2001 13:29 schreef Munters het volgende:
Komt er trouwens nog een uitslag van opgave 2? Ik begrijp dat jullie het druk hebben, maar de animo neemt danig af. Mijn interesse op dat algoritme nog eens met anderen te analyseren is inmiddels tot het nulpunt afgenomen.

psssst ff beter kijken (klassement is al omhoog getrapt)
de test set komt er ook aan

[kvdveer]

code:

2 7 10 14
1
10 - 2 - 7 - 14 = 1
result in < 10ms

1 8 9 9
1
8 / 9 + 1 / 9 = 1
result in < 20ms

[Verwijderd]

Op maandag 17 december 2001 18:38 schreef kvdveer het volgende:
10 - 2 - 7 - 14 = 1

I doubt that...

Typo denk ik, want het kan wel op jouw manier hoor : 10 - 2 + 7 - 14 = 1

[RickN]

Op maandag 17 december 2001 19:39 schreef _piranha_ het volgende:

[..]

I doubt that...

Typo denk ik, want het kan wel op jouw manier hoor : 10 - 2 + 7 - 14 = 1

Ja, maar ik denk dat hij 10-(2-7)-14 bedoelt.

[kvdveer]

Op maandag 17 december 2001 20:17 schreef RickN het volgende:

[..]

Ja, maar ik denk dat hij 10-(2-7)-14 bedoelt.

you are right... Mijn redundant haakjes remover is nog wat hyperactief...

[Dash2in1]

Hmm, irritant, programma vindt een juiste combinatie (eindelijk), maar lukt me niet om een of andere gedachtenstap te maken om het goed weer te geven

[kvdveer]

Hiervoor geld Vermenigvuldigen/delen gaat voor optellen/aftrekken. Verder
zijn haakjes toegestaan. Alle getallen moeten gebruikt worden.

Begrijp ik het goed dat dit NIET 'meneer van dalen wacht op antwoord' is?

Bij MVDWOA: 1 - 2 + 5 = -6
Bij links voor rechts: 1 - 2 + 5 = 4

Ik neem aan dat de laatste bedoeld wordt?

[Theswitch]

Op maandag 17 december 2001 22:42 schreef kvdveer het volgende:

[..]

Begrijp ik het goed dat dit NIET 'meneer van dalen wacht op antwoord' is?

Bij MVDWOA: 1 - 2 + 5 = -6
Bij links voor rechts: 1 - 2 + 5 = 4

Ik neem aan dat de laatste bedoeld wordt?

Ja mijn rekenmachine zegt het laatste inderdaad.
Je bent de eerste die hier over valt volgens mij
Verder moet je MVDWOA niet letterlijk lezen, maar als
M VD W OA

Dus eerst alle M, dan alle VD , danalle W en dan alle OAs van links naar rechts uitrekenen.

[Dash2in1]

Op maandag 17 december 2001 22:42 schreef kvdveer het volgende:

[..]

Begrijp ik het goed dat dit NIET 'meneer van dalen wacht op antwoord' is?

Bij MVDWOA: 1 - 2 + 5 = -6
Bij links voor rechts: 1 - 2 + 5 = 4

Ik neem aan dat de laatste bedoeld wordt?

Hmm, dat ezelsbruggetje wordt wel vaker verkeerd uitgelegd imho. Het is altijd zo dat optellen en aftrekken gelijkwaardig aan elkaar zijn, net zoals delen en vermenigvuldigen...

[kvdveer]

Dat verklaart mijn onvoldoendes!!!

[Verwijderd]

Op maandag 17 december 2001 18:38 schreef kvdveer het volgende:

code:

2 7 10 14
1
10 - 2 - 7 - 14 = 1
result in < 10ms

1 8 9 9
1
8 / 9 + 1 / 9 = 1
result in < 20ms

Okey, dat kan ik ook:

code:

1 8 9 9
1
Antwoord: (1 / 9 + 8 / 9) = 1 (0.2885 ms)

2 7 10 14
1
Antwoord: (2 / 7 + 10 / 14) = 1 (0.4697 ms)

2 2 2 2 2
2
Antwoord: (2 + 2 / 2 * (2 - 2)) = 2 (12.61 ms)

1 2 3 4 5 6
4
Antwoord: (1 + 6) / (5 / 2 - 3 / 4) = 4 (606.97 ms)

1 2 3 4 5 6 7
11
Antwoord: ((1 + 7 / 2) - (6 / 4 - (3 + 5))) = 11 (62079 ms)

De looptijden voor weinig getallen zijn wel rap dus, maar bij 5 or meer gaat het helemaal fout.

En er staan wat haakjes teveel. Zorgen voor later.

[Verwijderd]

Je ziet : je bent nooit te oud om bij te leren he

edit:
is reactie op kvdeveer z'n post

Heb net ook een uurtje aan die van mij gewerkt, en hij doet het wel mooi... Tot en met 6 getallen is geen probleem. 7 doet ie ook wel, maar ik heb berekend dat een wel bijzonder slecht gekozen input van de jury (en zo slecht zijn ze wel ) mijn progje bijna 2 uur aan de praat kan houden. Ikzelf vond nog geen inputs waar ie langer dan 3 minuten op rekent, maar je zal nooit anders zien natuurlijk... Worst case design moet onder de 20 min weet je wel, en dus moet ik 'm nog ff aanpassen morgen of woensdag
Ik weet wel hoe ik 'm een pak sneller krijg, alleen vergt dat wat werk, en dus tijd, en da's nu net 't probleem...

[kvdveer]

Op maandag 17 december 2001 23:10 schreef _piranha_ het volgende:
Ik weet wel hoe ik 'm een pak sneller krijg, alleen vergt dat wat werk, en dus tijd, en da's nu net 't probleem...

Geen tijd? je hebt toch twintig minuten

[Munters]

Op maandag 17 december 2001 23:10 schreef _piranha_ het volgende:
Ikzelf vond nog geen inputs waar ie langer dan 3 minuten op rekent, maar je zal nooit anders zien natuurlijk... Worst case design moet onder de 20 min weet je wel, en dus moet ik 'm nog ff aanpassen morgen of woensdag
Ik weet wel hoe ik 'm een pak sneller krijg, alleen vergt dat wat werk, en dus tijd, en da's nu net 't probleem...

Heb je behoefte aan een niet oplosbaar 7 input variant?
Hoor ik dat goed?
Ok.

1 2 3 4 5 6 7
9999

Mijn oplossing doet hier ook "iets" te lang over.
Tijd voor wat turbo axioma's en een hyper-common-tail-remover.

[Munters]

Op maandag 17 december 2001 23:04 schreef HH het volgende:
[..]2 2 2 2 2
2
Antwoord: (2 + 2 / 2 * (2 - 2)) = 2 (12.61 ms)

Wat een vreemd algoritme dat ie deze vindt boven de simpele
2 + 2 + 2 - 2 - 2

En er staan wat haakjes teveel. Zorgen voor later.

Blij dat ik dat helemaal onder de knie heb.

[Verwijderd]

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

Antwoord: (2 + 2 / 2 * (2 - 2)) = 2 (12.61 ms)

Wat een vreemd algoritme dat ie deze vindt boven de simpele
2 + 2 + 2 - 2 - 2

Simpel? Ligt eraan hoe je het opschrijft he?

Over far fetched gesproken:

code:

1 2 3 4 5 6
6
Antwoord: (1 + 6) / (5 / 2 - 4 / 3) = 6

Uitleggen hoe dit komt mag helaas pas na de deadline.

[Verwijderd]

Kan iemand van de jury de mailbox van gotcoders leeghalen, die is nl vol; krijg mijn oplossing steeds terug

[kvdveer]

Op maandag 17 december 2001 23:04 schreef HH het volgende:

code:

1 8 9 9
1
Antwoord: (1 / 9 + 8 / 9) = 1 (0.2885 ms)

2 7 10 14
1
Antwoord: (2 / 7 + 10 / 14) = 1 (0.4697 ms)

2 2 2 2 2
2
Antwoord: (2 + 2 / 2 * (2 - 2)) = 2 (12.61 ms)

1 2 3 4 5 6
4
Antwoord: (1 + 6) / (5 / 2 - 3 / 4) = 4 (606.97 ms)

1 2 3 4 5 6 7
11
Antwoord: ((1 + 7 / 2) - (6 / 4 - (3 + 5))) = 11 (62079 ms)

De looptijden voor weinig getallen zijn wel rap dus, maar bij 5 or meer gaat het helemaal fout.

En er staan wat haakjes teveel. Zorgen voor later.

1 8 9 9
1
8 / 9 + 1 / 9 = 1
[in 33,5000ms measured over 6 runs]

2 7 10 14
1
10 - (2 - 7) - 14 = 1
[in 1,7857ms measured over 112 runs]

2 2 2 2 2
2
2 + 2 + 2 - 2 - 2 = 2
[in 0,6361ms measured over 316 runs]

1 2 3 4 5 6
4
6 - (1 + 2 + 3 + 4) / 5 = 4
[in 0,8000ms measured over 250 runs]

1 2 3 4 5 6 7
11
7 - ((1 + 2 + 3 + 4) / 5 - 6) = 11
[in 6,2813ms measured over 32 runs]

het lijkt er op dat mijn algo effecienter is, maar minder goed geimplementeerd... Ik gebruik delphi op een PII 350@400. Dat zal ook vast wel uitmaken

[Orphix]

Die van mij geeft bij de laatste test:
5 + 6 - 7 * ((1 - 2) - (3 - 4))

Binnen een seconde (meet het niet echt)
Je mag toch wel een * 0 in je antwoord hebben?

[Verwijderd]

Ik gebruik java op een P3 700, dus dat is wel vergelijkbaar.

Maar goed, mijn tijd is op en mijn algorithme te traag, dus ik ga slapen en ik zie wel wat jullie er van bakken. Succes!

[kvdveer]

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

Heb je behoefte aan een niet oplosbaar 7 input variant?
Hoor ik dat goed?
Ok.

1 2 3 4 5 6 7
9999

Mijn oplossing doet hier ook "iets" te lang over.
Tijd voor wat turbo axioma's en een hyper-common-tail-remover.

1 2 3 4 5 6 7
9999
[geen oplossingen in 0,1031ms measured over 1939 runs]




Ik heb er een 'belachelijke-vraag-kickout-systeempje' ingebouwd

[D2k]

Op dinsdag 18 december 2001 00:03 schreef DiFool het volgende:
Kan iemand van de jury de mailbox van gotcoders leeghalen, die is nl vol; krijg mijn oplossing steeds terug

welke

[e-mail] ????

<edit>
stop maar met sturen
ik heb um nu 5 keer!!!!!!!!!!!!!!!

[D2k]

Op maandag 17 december 2001 23:10 schreef _piranha_ het volgende:
Tot en met 6 getallen is geen probleem. 7 doet ie ook wel, maar ik heb berekend dat een wel bijzonder slecht gekozen input van de jury (en zo slecht zijn ze wel ) mijn progje bijna 2 uur aan de praat kan houden.

[Munters]

Op dinsdag 18 december 2001 01:04 schreef kvdveer het volgende:

[..]

1 2 3 4 5 6 7
9999
[geen oplossingen in 0,1031ms measured over 1939 runs]

Ik heb er een 'belachelijke-vraag-kickout-systeempje' ingebouwd

Uiteraard mogelijk.

Maar de vraag was een onmogelijke 7 invoer, opdat de maximale looptijd van het algoritme bepaald kon worden.

En er zijn verrassend veel mogelijkheden.
Bij in invoer "1 2 3 4" is pas uitkomst 29 niet te maken.
En bij "1 2 3 4 5" kan 76 pas niet.

[kvdveer]

Wat zijn jullie fail tijden eigenlijk?
mij mij:
3 vars: 2,7 ms
4 vars: 910ms
5 vars: > 5 minuten

edit:
hij draait nog steeds

[edit2] ... ik heb hem net gestopt...[/edit2]
6 vars: eeuwig (I guess)
7 vars: nog langer (I guess)


Ik moet dus nog wat intelligentie toevoegen... ;-)

[Munters]

Op dinsdag 18 december 2001 12:27 schreef kvdveer het volgende:
Wat zijn jullie fail tijden eigenlijk?
mij mij:
3 vars: 2,7 ms
4 vars: 910ms
5 vars: > 5 minuten

edit:
hij draait nog steeds

[edit2] ... ik heb hem net gestopt...[/edit2]
6 vars: eeuwig (I guess)
7 vars: nog langer (I guess)


Ik moet dus nog wat intelligentie toevoegen... ;-)

5 vars: ca 1 sec.
6 vars, ca 65 sec.
Ik schat 7 vars op ca 4 uur.

Dit alles op een PII/350.

[D2k]

Op dinsdag 18 december 2001 14:49 schreef Munters het volgende:
Ik schat 7 vars op ca 4 uur.

goh

ik denk dat het nog wel ff duurt voor ik die van jou af heb getest

[kvdveer]

nou ik heb wat getweakt...
Single precicion en double precicion maakt zeker 10% uit in rekentijd... (daarmee is de worstcase onder de 10 minuten gekomen)

[edit]
even evidence:
single:
1 5 19 42 2
16
[in 11,51ms measured over 87 runs] 42 - (1 x 5 + 2 + 19) = 16

double
1 5 19 42 2
16
[in 13,30ms measured over 76 runs] 42 - (1 x 5 + 2 + 19) = 16

extended
1 5 19 42 2
16
[in 13,71ms measured over 73 runs] 42 - (1 x 5 + 2 + 19) = 16

real48
1 5 19 42 2
16
[in 40,48ms measured over 25 runs] 42 - (1 x 5 + 2 + 19) = 16

comp <-- kan niet omgaan met breuken en is dus onbruikbaar.
1 5 19 42 2
16
[in 9,44ms measured over 106 runs] 42 - (1 x 5 + 2 + 19) = 16

[Munters]

Op woensdag 19 december 2001 00:39 schreef kvdveer het volgende:
nou ik heb wat getweakt...
Single precicion en double precicion maakt zeker 10% uit in rekentijd... (daarmee is de worstcase onder de 10 minuten gekomen)

[edit]
single:
[..]
double
[..]
extended
[..]
real48

Wat zijn dit voor datatypes?
Ik heb float gebruikt (in C). Omschakelen naar double leverde niet veel op.

Ik had een variant waarbij de berekeningen zonder deling naar een integer boom afgetakt werden.
Dit leverde hoegenaamd geen verbetering op!
Een snelle test bevestigde dat: een globale substitute van data type "double" naar "int", en testen leverde ongeveer gelijke tijden op (maar foutieve antwoorden natuurlijk).

Common-tail-removal leverde trouwens wel flink wat op:
Invalid5 gaat nu in 0,11 s.
Invalid6 in 13 sec.
Invalid7 in 37 min 53 sec.

(PII/550 Linux/gcc -O)

Jouw worst-case binnen de 10 minuten is wel erg snel trouwens. Wat voor machine / compiler gebruik je?

[Verwijderd]

Worst case met 7 getallen doet 'ie hier in iets meer dan 2 minuten .. maar ik ben bang dat m'n algoritme niet alles berekend
Heb 'm "op hoop van zegen" net toch maar opgestuurd.

/me duimt

[D2k]

Op woensdag 19 december 2001 19:47 schreef eXoR het volgende:
Worst case met 7 getallen doet 'ie hier in iets meer dan 2 minuten .. maar ik ben bang dat m'n algoritme niet alles berekend
Heb 'm "op hoop van zegen" net toch maar opgestuurd.

* D2k duimt

<Edit>
zo alles is weer nagekeken

[Dash2in1]

Mocht het programma geen antwoord vinden dan komt de uitvoer "Geen antwoord".
De maximale runtime is 10 minuten tot 6 getallen en 20 minuten voor 7 getallen.

Betekent dit dat er ook met invoeren wordt gewerkt die geen oplossing hebben? (Als het kan svp snel antwoorden, heb nog een uur )
Want bij een invoer waar een oplossing voor is lukt dit zeker te weten wel.

[Verwijderd]

iedereen is nog duchtig aant verbeteren

[Dash2in1]

Op woensdag 19 december 2001 23:11 schreef Zoepnek het volgende:
iedereen is nog duchtig aant verbeteren

mjah 3 secondes af voor onmogelijke 6 (23 secondes nu)
maar voor 7 is 'ie nog bezig

[Verwijderd]

Gvd dat was close
Ik vond net nog een uurtje tijd om 'm sneller te maken (werken deed ie al) en heb 'm net verstuurd. Amper 9 minuten voor 'affluiten dus', en dat terwijl ik er alles samen niet eens 3 uur aan spendeerde
Maar het worst case gedrag voor 7 inputs is nu wel van een goede 2 uur naar max 4,5 minuten gebracht (op mijn Athlon 750, Win2K). Aangezien een PIII 700 geen factor 4 trager is, is dat ruim onder de specs
Bij 6 inputs blijft ie altijd onder de 1,5 seconde (terug op mijn bak dus)

Wie de C/C++ code wil - maar ik moet toegeven dat ik door tijdgebrek amper commentaar heb geschreven en dus ziet ze er deze keer echt niet uit - moet maar es mailen... als je er niet uitkomt kun je achteraf ook steeds je vragen mailen.
Till next time guys !

[Munters]

Op woensdag 19 december 2001 23:52 schreef _piranha_ het volgende:
Gvd dat was close
Ik vond net nog een uurtje tijd om 'm sneller te maken (werken deed ie al) en heb 'm net verstuurd. Amper 9 minuten voor 'affluiten dus', en dat terwijl ik er alles samen niet eens 3 uur aan spendeerde
Maar het worst case gedrag voor 7 inputs is nu wel van een goede 2 uur naar max 4,5 minuten gebracht (op mijn Athlon 750, Win2K). Aangezien een PIII 700 geen factor 4 trager is, is dat ruim onder de specs
Bij 6 inputs blijft ie altijd onder de 1,5 seconde (terug op mijn bak dus)

Wie de C/C++ code wil - maar ik moet toegeven dat ik door tijdgebrek amper commentaar heb geschreven en dus ziet ze er deze keer echt niet uit - moet maar es mailen... als je er niet uitkomt kun je achteraf ook steeds je vragen mailen.
Till next time guys !

Ik wil het wel eens zien, maar je e-mail adres is niet bekend.
Wil je anders je source mailen naar [e-mail]?
(als anderen ook hun source sturen, zal ik een vergelijk op dezelfde machine maken, maar het zal wel na nieuwjaar worden).

[D2k]

Op donderdag 20 december 2001 09:59 schreef Munters het volgende:

[..]

Ik wil het wel eens zien, maar je e-mail adres is niet bekend.
Wil je anders je source mailen naar [e-mail]?
(als anderen ook hun source sturen, zal ik een vergelijk op dezelfde machine maken, maar het zal wel na nieuwjaar worden).

er komt als we klaar zijn met controleren ook weer een thread met de testset enzo
ook handig om die ff in de smiezen te houden en dan evt nog wat antwoorden te bespreken.

Ik zag iig net 5 inzendingen in mijn mail dus daar kan ik nog wel ff mee bezig zijn vanavond.
Dus houdt hoop gij allen
de jury werkt door

[Theswitch]

Op donderdag 20 december 2001 10:02 schreef D2k het volgende:

[..]

Ik zag iig net 5 inzendingen in mijn mail dus daar kan ik nog wel ff mee bezig zijn vanavond.
Dus houdt hoop gij allen
de jury werkt door

Was ff weg tijdje hiero. MAar ik ben benieuwd wat mensen van m'n opgave gemaakt hebben. Leuk dat de tijdslimieten dit keer wel een opstakel vormen

[Soultaker]

He, jammer dat ik deze thread nu pas zie! Ik zou wel graag meegedaan hebben namelijk.

Ik begrijp trouwens niet waarom deze opgave moeilijker zou zijn dan op het eerste gezicht lijkt - hij is toch simpelweg te bruteforcen?

Het aantal gelabelde bomen op 7 punten is gelijk aan 7^5, oftewel 16807. Elk punt splitst zich echter in precies twee andere takken, dus het feitelijke aantal mogelijke plaatsingen van de haakjes is nog veel lager. Tussen elk paar getallen komt één van de vier operatoren, dus er zijn in totaal 4^6 (4096) mogelijke formules nodig bij een gegeven boom.

Alle mogelijke oplossingen zijn dus in maximaal 7^5 * 4^6 vrij eenvoudige iteraties te vinden. Dit zijn er zo'n 68 miljoen, wat wel binnen een minuut te doen moet zijn. In de praktijk zal het hooguit om een paar seconden gaan, schat ik zo.

Zie ik hier iets over het hoofd? Het diverse commentaar doet vermoeden van wel, maar ik zou niet weten wat.

MVG,
Maks Verver.

PS. Ik neem aan dat ik nu wel spoilers mag geven aangezien de instuurtermijn verstreken is - zoniet, gooi dit bericht er dan maar uit.

[MisterData]

De instuurtermijn verstrijkt toch pas vanavond 24:00

[Verwijderd]

Soultaker Je vergeet er een paar bv. a\b is wat anders dan b\a

MisterData Termijn verstreek op woensdag

[kvdveer]

berekening:

code:

7!  = 5040 -> het aantal mogelijke volgorden voor de getallen
 *     *
6^6 = 46656 -> de mogelijke operatoren er tussen.
     =
    235.146.240 -> het aantal mogelijk antwoorden

De gebruikte operatoren zijn:
- vermenigvuldigen
- delen
- optellen zonder haakje
- optellen met haakje
- aftrekken zonder haakje
- aftrekken met haakje

weer even doorrekenen: 20 min -> 20*60 sec = 1200 sec
195.955,2 combinaties per seconde genereren en controleren.
Op 1 ghz komt dat neer op 5103 cycli per berekening. dat is niet haalbaar.

maw, een dom brute force algo is niet bruikbaar.

edit:

D2K, is mijn inzending al nagekeken?
Kan ik evt een gerecompileerde versie versturen? (Ik zal alleen het datatype veranderen)

[D2k]

kvdveer : vooruit dan maar

de rest is allemaal (op Dash2in1 na das java en dat doe ik nie ) nagekeken

[Verwijderd]

Ok, Munters heeft m'n source gekregen als alles goed gaat

Ik ga toch ff tijd maken om mijn methode uit te leggen, of althans een poging te doen

Om te beginnen : de triviale gevallen. Namelijk 0 en 1 getallen zijn opgegeven. Als je geen getallen hebt kun je geen ander getal 'maken', dus geen oplossing. Met 1 getal is 't simpel : gewoon dat getal pakken Dus als het gegeven getal datgene is dat je wil, dan heb je de oplossing door dat getal te nemen, anders is er geen oplossing.

Dan de kleintjes : 2 getallen gegeven. Dat doe ik uiteraard brute force, lettende op de commutativiteit van de optelling en de vermenigvuldiging, en dus heb ik 6 mogelijkheden :

code:

getal1 + getal2
getal1 * getal2
getal1 / getal2
getal1 - getal2
getal2 / getal1
getal2 - getal1

Meer kan niet.

Ok, alle andere doe ik recursief. Jawel
Neem ff aan dat ik n waarden binnen krijg (bvb n=6 of n=7 voor de contest). Ik kies dan willekeurig 2 waarden uit deze verzameling. Op dit paar getallen kan ik, net als hierboven, 6 mogelijkheden uitproberen. Uit de set van n getallen schrap ik dan de 2 die ik koos, en ik plaats het resultaat van 1 van de 6 mogelijkheden terug. Ik hou dan een set van n-1 getallen over, die ik recursief behandel. Iedere oproep doet m'n set met 1 waarde afnemen, en dus kom ik snel genoeg bij 2, en die doe ik dus brute force (zie hoger). Voor ieder paar probeer ik de 6 mogelijkheden. En dat doe ik voor ieder paar dat mogelijk is. Let op : volgorde maakt niet uit, dus eigenlijk moet ik zeggen : voor iedere deelverzameling van 2 elementen. Als n=7 dan zijn er dat 7! / (5!2!) = 21. En voor iedere deelverzameling dus 6 mogelijkheden, zodat ik dus 21*6 recursieve oproepen moet doen in 't slechtste geval. Dus een 7-waarden probleem oplossen is in 't slechtste geval 126 6-waarden problemen oplossen. Analoog : een 6-waarden probleem oplossen is worst case 6*(6!/(4!2!)) = 6*15 = 90 5-waarden problemen, etc.
Waarom die deelverzameling van 2 elementen ? Wel, het idee kreeg ik omdat een oplossing, als deze bestaat, altijd zonder haakjes kan geschreven worden als een postfixuitdrukking. Wat de vorm ook is van die uitdrukking, je moet altijd op een zeker moment beginnen door 2 elementen te nemen (welke weet je dus niet) en daarop een binaire operatie toe te passen. Dan heb je een postfixuitdrukking met 1 waarde minder, en daarop kan je dezelfde redenering toepassen. Ik kan bewijzen dat je op die manier _alle_ mogelijke schikkingen van de n getallen tegenkomt, ongeacht de bewerkingen in de uitdrukking en ongeacht of er in de uitdrukking nu haakjes staan, teveel of niet, etc.
Dat is een eerste deel. Als bij een bepaalde mogelijkheid de recursieve oproepen een 2-waardenprobleem bekomen, en deze blijkt een oplossing te hebben, dan wordt een postfixuitdrukking opgebouwd, van achter naar voor dus.
De functie die de oplossing vind, weet dat de oplossing gegeven wordt door - ik zeg maar wat - getal1 * getal2, en genereert daarbij de postfixuitdrukking '%1%2*' (%x wil zeggen : het zoveelste getal dat de functie binnen kreeg) en geeft die terug aan de oproeper. Die kreeg 3 waarden binnen, maar weet wat hij doorgaf aan de functieoproep die het 2-waardenprobleem afhandelde. Stel dat - terug als voorbeeld - deze als deelverzameling van 2 elementen uit de 3 de eerste en de derde waarde koos, en de som maakte. Hij weet dus dat het eerste getal wat de opgeroepen functie zag voor hem het tweede getal is, en het tweede getal wat de opgeroepen functie zag voor hem de som is van 't eerste en 't derde getal. Hij zal de postfixuitdrukking dus vertalen naar : '%2%1%3+*' (in de originele dus %1->%2 en %2->%1%3+, wel _tegelijkertijd_ aanpassen om neveneffecten te vermijden). Zo gaat het door tot de eerste oproep, dus die van de main. Deze heeft dan de postfixuitdrukking die het resultaat oplevert. Maar de waarden staan niet noodzakelijk in volgorde, 'k kan ook een permutatie zijn, bvb (3-waardenprobleem) '%2%1+%3*'. Daarom worden de waarden gepermuteerd, zodat ze in volgorde van de postfixuitdrukking staan. Het is dan een koud kunstje om de postfixuitdrukking te vertalen naar een infixuitdrukking. Dat doe ik door een boom op te bouwen die de postfixuitdrukking weergeeft (is heel eenvoudig). Bewerkingen krijgen een prioriteit mee in de boom. Dan 'traverse' ik de boom infix, dus ik bepaal (recursief) de infixuitdrukking voor de linker subboom, dan voor de rechter subboom, en ik plak er de bewerking tussen. Rekening houdend met de prioriteiten van de bewerkingen zie ik meteen ook of rond de infixuitdrukking van de linker en/of rechter subboom haakjes moeten, zodat ik alleen haakjes zet als ze absoluut noodzakelijk zijn...

Oh, het bepalen van de postfix uitdrukking kan eigenlijk makkelijker als je ze 'on the fly' maakt en steeds meegeeft bij een volgende recursieve oproep. Mijn methode vraagt veel meer tijd door de 'vertalingen' van de %x tussen de oproepen door. Maar er is een groot voordeel : je hebt maar 1 oplossing van doen, dus 't gebeurt maar 1 keer, terwijl je 't anders ook constant doet voor pogingen die niet tot een oplossing leiden. Dat alleen al maakte m'n code een factor 6 (jawel !) sneller...

Hopelijk verduidelijkt dit een en ander...
Wie nog vragen/opmerkingen heeft of wie de C/C++ code zelf eens wil napluizen, mag uiteraard altijd mailen ([e-mail] dus ) of 't hier posten...

[Verwijderd]

Hmm, ik krijg net mail dat m'n prog bljkbaar niet goed is ("foutieve uitvoer") ?

Zou ik dan ff mogen weten wat er niet goed gaat aub ?
Het verbaasd me erg dat ie 't niet doet, dus ik wil ff zien wat er mis gaat, zodat ik wat kan bijleren...

Tnx...

[Orphix]

Op donderdag 20 december 2001 21:17 schreef _piranha_ een uitgebreid stuk

Ik gebruik eigenlijk hetzelfde principe (alleen was ik zo lui om uit te gaan van >1 getallen)
Alleen de manier waarop je 'terugrekent' vanaf het moment dat je weet dat de uitkomst goed is heb ik anders opgelost (voor zover ik jouw verhaal heb begrepen

Ik sla elke bewerking in een object op die zichzelf weer kan geven (via ostream), dit object bevat weer 2 pointers naar andere objecten (van beide operanden) en de 'begin' objecten bevatten alleen een getal. Die objecten maak ik dus aan en de pointers daarvan sla ik in de lijst op die via hetzelfde principe als jou aldoor 1 minder groot naarmate je verder in de 'boom' komt.
Beetje vaag, maar het is ook best wel moeilijk uit te leggen

Ik heb eigenlijk niet zo nagerekend over de performance e.d. maar de meeste oplossingen konden zeer snel worden gevonden, dus ik heb het er op gegokt, en het was goed.

[D2k]

Op donderdag 20 december 2001 21:21 schreef _piranha_ het volgende:
Hmm, ik krijg net mail dat m'n prog bljkbaar niet goed is ("foutieve uitvoer") ?

Zou ik dan ff mogen weten wat er niet goed gaat aub ?
Het verbaasd me erg dat ie 't niet doet, dus ik wil ff zien wat er mis gaat, zodat ik wat kan bijleren...

Tnx...

je zal ff moeten wachten op de testset
maar ik kreeg vaak te zien dat ik CPU time voor nix had verziekt
en das nie goe

[Verwijderd]

Op donderdag 20 december 2001 21:27 schreef D2k het volgende:

je zal ff moeten wachten op de testset
maar ik kreeg vaak te zien dat ik CPU time voor nix had verziekt
en das nie goe

Hangt van je probleem af

Niet dat het niet kan hoor, want eigenlijk heb ik maar een 3tal sets getest, 'k had nl geen tijd. Maar ik vraag me wel af wat ik dan over 't hoofd zag. Ik dacht zelfs aan 0 of 1 waarden, dat je niet mag delen door 0, etc etc. Ik ben wel benieuwd welke kameel ik heb geschoten Het enige dat ik nl kan bedenken is dat rekenen met floats ipv ints voor wat afrondingen zorgt en dat 't daardoor de mist ingaat, maar dat kan ik me nauwelijks voorstellen...

Als 't zo blijft dat ie verkeerd is - en dat zal wel zeker - dan was dit dus het sein dat ik maar beter geen code schrijf als ik eigenlijk geen tijd heb, want dat dat niet goed gaat. Ofte : dit was m'n onfortuinlijke exit
Xalista/DiFool : the crown is yours (als ie dat al nog niet was dus).

Btw : heeft Xalista/RickN een oplossing ingestuurd ? Want ik hoorde 'm precies nog niet, en anders komt ie altijd mooi melden dat ie sneller is dan mij...

[D2k]

Op donderdag 20 december 2001 21:39 schreef _piranha_ het volgende:
Hangt van je probleem af

Niet dat het niet kan hoor, want eigenlijk heb ik maar een 3tal sets getest, 'k had nl geen tijd. Maar ik vraag me wel af wat ik dan over 't hoofd zag. Ik dacht zelfs aan 0 of 1 waarden, dat je niet mag delen door 0, etc etc. Ik ben wel benieuwd welke kameel ik heb geschoten Het enige dat ik nl kan bedenken is dat rekenen met floats ipv ints voor wat afrondingen zorgt en dat 't daardoor de mist ingaat, maar dat kan ik me nauwelijks voorstellen...

Als 't zo blijft dat ie verkeerd is - en dat zal wel zeker - dan was dit dus het sein dat ik maar beter geen code schrijf als ik eigenlijk geen tijd heb, want dat dat niet goed gaat. Ofte : dit was m'n onfortuinlijke exit
Xalista/DiFool : the crown is yours (als ie dat al nog niet was dus).

Btw : heeft Xalista/RickN een oplossing ingestuurd ? Want ik hoorde 'm precies nog niet, en anders komt ie altijd mooi melden dat ie sneller is dan mij...

die van jou is iig fout
en blijft fout
over de rest zeg ik nog nix
deze ronde is nog niet helemaal nagekeken nl

[Verwijderd]

Op donderdag 20 december 2001 21:17 schreef _piranha_ een lang verhaal:

Dat post-fix had ik ook bedacht. Dat is nl. de manier hoe computers het best rekenen met formules.

Alleen snap dat vertaal gebeuren niet echt. Je neemt toch gewoon een stack, waar je getallen en operators op kan pushen? En voor het vertalen naar in-fix neem je er toch een stack bij (rangeer- of wissel-algoritme, bekend van de trein)

En verder: je daadwerkelijke algoritme is slim. Ik had zelf alleen een recursieve super-loop bedacht, en dat vond ik niet de moeite waard om te coden. Jammer dat je code niet werkt.

[Theswitch]

d2K: was m'n testset te moeilijk dat je zoveel hebt zitten wachten?

[Verwijderd]

Op donderdag 20 december 2001 22:25 schreef Doekman het volgende:
Alleen snap dat vertaal gebeuren niet echt. Je neemt toch gewoon een stack, waar je getallen en operators op kan pushen? En voor het vertalen naar in-fix neem je er toch een stack bij (rangeer- of wissel-algoritme, bekend van de trein)

Jaja, maar dat vertalen gebeurt _voor_ het omzetten van postfix naar infix. Ik zal ff een klein voorbeeld geven :

Je hebt de waarde 1 2 5 en wil 11 maken.
Ik doe een oproep vanuit de main, en geeft alle waardes en het resultaat dat ik wil bereiken mee. Als waardes geef ik dus - let dus op de volgorde - 1 2 5 mee. Neem aan dat ik als deelverzameling van 2 de laatste 2 neem, dus de 2de en 3de waarde, en als operatie probeer ik de * uit. De recursieve oproep wordt dan : 1 10 (1 2*5) met als te bereiken waarde 11. Aangezien we hier al een 2-waardenprobleem hebben, doen we 't brute force, en merken dat een optelling een oplossing is. Dus geven we aan de oproeper (de functie die de 3 waarden binnenkreeg) de postfixuitdrukking %1%2+ terug. Merk op dat voor de oproeper dit _niet_ waar is he ! De som van de eerste waarde en de tweede waarde voor hem (dus 1 + 2) is geen oplossing! Uiteraard omdat waarden niet in dezelfde volgorde worden doorgegeven aan de recursieve oproep ! Want de %1 slaat op de 1e waarde in de recursieve oproep, dus op de 2, die voor de oproeper _toevallig_ ook de 1e waarde was !! Die %1 moet dus %1 worden (blijven) als ie een niveau hoger gaat. Analoog : die %2 (2de waarde voor de recursieve oproep) was _niet_ de tweede waarde voor de oproeper maar eigenlijk het product van de 2e en de 3e waarde. Die %2 is voor de oproeper dus eigenlijk %2%3* ... Snap je ? De vertaling is dan %1%2%3*+ en dit is hier ook 't eindresultaat, maar normaal propageert dat dus naar 'boven' toe... Dat klopt dus : 1 + 2*5
Hier is 't toevallig wel zo dat de cijfers in de juiste
volgorde staan, maar dat hoeft niet zo te zijn. Als ik 12 wou, zou 't resultaat %1%3+%2* kunnen zijn, dus waarde 1, dan naar 3 springen, en dan waarde 2... vandaar dat ik m'n waarden nog ff permuteer vooraleer ik van postfix naar infix ga. Die boom is idd een letterlijke vertaling van jou stack-gedoe, gewoon omdat dat beter is om er een infix van te maken die meteen geen overbodige haakjes meer heeft
Hope this helps...

Jammer dat je code niet werkt.

Tegen wie zeg je 't...
Naja, volgend jaar beter ofzo
Ik zal wel weer een stom detail vergeten zijn

[kvdveer]

Ik geloof dat mijn algo helemaal afwijkt van wat jullie allemaal doen.

ik ga uit van de testset
8 9 9 1
1
1 / 8 + 8 / 9

Ik bouw een bibliotheek van sub-sommen.
de eerste ronde zijn dat alleen de varuabelen:
# 1. (gebruikt: 1, over: 8 8 9, waarde 1)
# 8. (gebruikt: 8, over: 1 8 9, waarde
# 8. (gebruikt: 8, over: 1 8 9, waarde
# 9. (gebruikt: 9, over: 1 8 8, waarde 9)

De derde optie komt niet eens in mijn bibliotheek, 'ie de zelfde getallen heeft, en dezelfde waarde heeft. Ik kijk hierbij niet naar de som zelf.

Vervolgens ga ik per som kijken welke waarden nog 'passen' in de overgebleven getallen.
voor # 1. (gebruikt: 1, over: 8 8 9, waarde 1) passen:
# 8. (gebruikt: 8, over: 1 8 9, waarde
# 9. (gebruikt: 9, over: 1 8 8, waarde 9)

daar maak ik alle zes de sommen mee. Een aantal voorbeelden van toevoegingen aan mijn bibliotheek:
# (1 * (gebruikt: 1 8, over: 8 9, waarde
# (1 - (gebruikt: 1 8, over: 8 9, waarde -7)
# (9 / 1) (gebruikt: 1 9, over: 1 8, waarde 9)


als alle waarden zijn gebruikt, vergelijk ik met de doelwaarde, en als 'ie gelijk is spring't 'ie uit de loop.
ALs 'ie ongelijk is, vergeet 'ie de som en gaat 'ie door.

Hierbij noem ik nog even niet de (intelligente) manier waarop ik een overschot aan haakjes voorkom.

Is er ook maar iemand die dit kan volgen?

[RickN]

Op donderdag 20 december 2001 21:39 schreef _piranha_ het volgende:

[..]

Btw : heeft Xalista/RickN een oplossing ingestuurd ? Want ik hoorde 'm precies nog niet, en anders komt ie altijd mooi melden dat ie sneller is dan mij...

Ja, ik heb een oplossing ingestuurd (wacht maar op de officiële uitslag ), maar ik heb me deze ronde erg rustig gehouden, omdat ik me erg schaam over m'n oplossing... Hij is namelijk nog al langzaam zie je. Ik zeg dit met pijn in m'n hart, maar ik denk dat ik geluk heb gehad met de testinvoer van de jury, want ik betwijfel of m'n progje snel genoeg was bij elke mogelijke invoer...(heel eerlijk gezegd WEET ik dat het niet zo is). Nadat ik mijn versie had ingestuurd heb ik nog een paar keer de tijd en de zin gezocht om een echt goede oplossing te implementeren (want daar heb ik wel wat ideetjes voor), maar dat is er niet van gekomen. Ik vond het wel goed van mezelf dat ik aan de Reversed Polish Notation (a.k.a. postfix notatie) had gedacht (is nl. al 5 jaar geleden dat ik er over hoorde) omdat ik daardoor niet met echt bomen en objecten aan de gang hoefde zoals Orphix, maar ik zie dat ik ook daarmee niks bijzonders heb gedaan. Al met al ben ik deze ronde mijn punten eigenlijk onwaardig en dit gevoel zal alleen maar sterker worden als straks de uitslag bekend wordt...

[Verwijderd]

Ik zal mijn oplossing ook ff posten, die was ook goed maar wel na 4 pogingen

Mijn opl is eigenlijk een veredelde brute force, ik heb een component waar ik getallen in kan stoppen, en met een method Solve.

In deze method heb ik 3 mogelijkheden:

Zeg benodigde totaal = t, aantal getallen = n en de getallen zijn a_0...a_n-1

• n = 1, dan kijk if of a_0 = t.
• n = 2, dan kijk ik of a_0 + a_1, a_0 * a_1, a_0 - a_1, a_1 - a_0, a_1 / a_0 of a_0 / a_1 gelijk aan t is.
• n > 2, dan roep ik voor i = 1..div(n) de method Split(i) aan.

Split(i) kijkt of er een oplossing is voor (a_0 .. a_i-1) ? (a_i .. a_n-1) = t
met ? = +, *, -, - omgedraaid, /, / omgedraaid.

Voor i = 1 maak ik een nieuw component met de getallen a_1 .. a_n-1 en een nieuw totaal. Bv voor ? = + wordt het nieuwe totaal t-a_0. Van dit nieuwe component roep ik dan weer Solve aan.

Voor i > 1 construeer ik steeds een nieuwe combinatie voor de getallen voor de ?; van deze combinatie maak ik een lijst met elke mogelijke waarde, dan maak ik een nieuw component met de getallen a_i+1 .. a_n-1 met totaal = t ! [waarde]; Met ! is de inverse van ?.

De truc is nu dat ik alle mogelijke waarden voor een combinatie van 3 getallen opsla. Dus bij n=3 kijkt method Solve eerst of t in deze lijst voorkomt. En de method Split gebruikt deze lijst om alle mogelijke waarde van een bepaalde combinatie van 3 getallen te krijgen.

Na nog wat geoptimaliseer [ik onthou ook alle mogelijke waarde voor (a?b)?(c?d) en nog wat dingen] wordt de maximale duur voor 7 cijfers ongeveer 15 sec.

De fouten die ik gemaakt had, ter lering en vermaak:

• Ik had een functie in Solve gezet die keek wat het maximale getal was wat met de getallen te maken was.
  Dat deed ik door alle getallen behalve de 1'en en het maximum met elkaar te vermenigvuldigen, dit vermenigvulde ik dan nog met het maximum + aantal 1'en.
  
  Dat gaat echter fout bij bv 1, 50, 1, 50; maximum is hier (1+50)*(1+50) en ik dacht (50+2)*50 [Met negatieve getallen had ik wel rekening gehouden]
• Bij het maken van alle mogelijk combinaties in Split, hield ik a_0 vast dus als n = 4 en i = 2 heb je de combinaties
  
  code:
  

  (1 2)(3 4)
  (1 3)(2 4)
  (1 4)(2 3)

  
  Dit gaat echter fout als i*2 <> n, bv als i=2 en n=5, heb je de combinaties
  
  code:
  

  (1 2)(3 4 5)
  (1 3)(2 4 5)
  (1 4)(2 3 5)

  
  maar ook
  
  code:
  

  (2 3)(1 4 5)
  (2 4)(1 3 5)
  (2 5)(1 4 5)
  (3 4)(1 2 5)
  (3 5)(1 2 4)
  (4 5)(1 2 3)

• En tussendoor had ik nog een oplossing opgestuurd die geen overbodige haakjes aanmaakte, omdat ik fout 2 echt niet kon vinden

[D2k]

Op donderdag 20 december 2001 22:27 schreef Theswitch het volgende:
d2K: was m'n testset te moeilijk dat je zoveel hebt zitten wachten?

neu maar in het begin waren er vooral brute force pogingen
dat is volgens mij wel iets verbeterd naderhand

[D2k]

Op donderdag 20 december 2001 23:50 schreef kvdveer het volgende:
[hele boel]

ik heb je mail gezien
ik zal kijken of ik vandaag overdag tijd vind
anders duurt het tot vanavond.

ER MOETEN NOG 2 OPGAVEN NAGEKEKEN WORDEN.
TOT DIE TIJD NOG GEEN TESTSET VAN DE JURY EN DE UITSLAG LAAT OOK NOG EVEN OP ZICH WACHTEN!


zo heb ik weer genoeg geschreeuwd voor vandaag

[eXistenz]

al bekend wanneer opgave 4 ?

[D2k]

Op vrijdag 21 december 2001 19:44 schreef eXistenz het volgende:
al bekend wanneer opgave 4 ?

noopz
als het goed is krijg ik vanavond opgave 4 gemaild van ons aller dusty
en dan moet ie beoordeeld worden
ik doe nog geen uitspraken over de datum van verschijning iig

[Verwijderd]

Op donderdag 20 december 2001 21:50 schreef D2k het volgende:

die van jou is iig fout
en blijft fout
over de rest zeg ik nog nix
deze ronde is nog niet helemaal nagekeken nl

Je hebt volkomen gelijk.

Zonet viel m'n frank, dus die testset hoeft al niet meer, want er zijn er wel heel veel die m'n prog niet vind. Mijn idee en m'n code werken perfect, op 1 klein ding na.

Wat is er mis met m'n code ? Heel eenvoudig : op een bepaald moment wil ik 't voorlaatste element van een array een waarde geven, dus doe ik :
ArrayVariabele[theArraySize-1] = ... ;
Uiteraard begint C/C++ z'n array-elementen te tellen vanaf 0, dus 't voorlaatste moet natuurlijk -2 zijn ipv -1. Pas dat aan en ie werkt perfect.

Gvd, had ik 'm een dag eerder kunnen insturen dan had ik geweten dat ie verkeerd was en had ik 't nog kunnen aanpassen, zodat ie goed was geweest in 2 pogingen

Ok, hint aan iedereen : probeer niet te proggen als je geen tijd hebt, want dan schiet je van die kemels zoals mij

En ik neem aan dat ze mijn progje met minimale wijziging niet meer zullen aanvaarden voor een retest (ook al vond ik de fout dus alsnog zelf), zodat ie alsnog dienst kan doen als goede inzending (maar met halve aantal punten bvb)...
[eig wil ik dit gewoon omdat ik zin heb in die opgave 4, maar als ik nu een -1 heb dan heeft die 4de al geen zin meer voor me omdat m'n achterstand toch te groot is voor een top 5 positie]
Nochtans was er toch iemand die nog ff z'n 'types' mocht aanpassen en 't toch doorsturen. Your call jury, ik leg me neer bij jullie beslissing.

RickN : toppie dat je gewoon eerlijk toegeeft dat ie niet goed is wegens te traag. Voor je eerlijkheid alleen al verdien je je punten wel...

/me is wel blij dat ie toch eens sneller is dan 'Xalista'

[D2k]

Op zaterdag 22 december 2001 18:19 schreef _piranha_ het volgende:

[..]
En ik neem aan dat ze mijn progje met minimale wijziging niet meer zullen aanvaarden voor een retest (ook al vond ik de fout dus alsnog zelf), zodat ie alsnog dienst kan doen als goede inzending (maar met halve aantal punten bvb)...
[eig wil ik dit gewoon omdat ik zin heb in die opgave 4, maar als ik nu een -1 heb dan heeft die 4de al geen zin meer voor me omdat m'n achterstand toch te groot is voor een top 5 positie]
Nochtans was er toch iemand die nog ff z'n 'types' mocht aanpassen en 't toch doorsturen. Your call jury, ik leg me neer bij jullie beslissing.

nee dat gaat dus niet mogen
die van kvdveer kwam door een klein verschil van inzicht over de opgave, en heeft uiteindelijk nix veranderd voor um

[Verwijderd]

Ik merk net dat ze de testset ook hebben gepost...

[EDIT]

nee dat gaat dus niet mogen
die van kvdveer kwam door een klein verschil van inzicht over de opgave, en heeft uiteindelijk nix veranderd voor um

Dat dacht ik al. Ik kan je 't ook moeilijk kwalijk nemen natuurlijk.

Nou ja, dit was het dan wat mij betreft. Allemaal heel veel succes met de laatste opgave, en dat de beste uiteindelijk moge winnen !!

Het was heel leuk om hieraan deel te nemen. Hopelijk doen jullie volgend jaar iets gelijkaardigs !
Hpelijk ga ik dan wel geen kamelen schieten, zodat ik voor wat meer weerwerk kan zorgen in de eindstrijd

[D2k]

Op zaterdag 22 december 2001 18:23 schreef _piranha_ het volgende:
Ik merk net dat ze de testset ook hebben gepost...

klopt

[wasigh]

wanneer de nieuwe opgave online komt is nog niet bekend
(hij is wel erg lastig dat weten we al wel )

[D2k]

Op zondag 23 december 2001 02:11 schreef wasigh het volgende:
wanneer de nieuwe opgave online komt is nog niet bekend
(hij is wel erg lastig dat weten we al wel )

mwoah valt wel mee toch ??

"be affraid, be very affraid"

[Dash2in1]

Toch maar eens polsen op deze tweede kerstmiddag: al iets bekend over wanneer deel 4 van start gaat?

[D2k]

Op woensdag 26 december 2001 14:30 schreef Dash2in1 het volgende:
Toch maar eens polsen op deze tweede kerstmiddag: al iets bekend over wanneer deel 4 van start gaat?

ik heb nog geen id
ben net thuis maar de rest van de jury is gewoon nog bezig met familie verplichtingen.
Maar ook dit keer geld gewoon dat je het minstens 6 uur van te voren te horen krijgt volgens mij