[alg] Cijfercombinaties maken naar gewenste uitkomst *

[GeeBee]

Er is een leuk wiskundig spel waarin je met 6 getallen (uit bv 1...50) een ander getal moet maken (uit vb 100...999).
Hierbij moet en mag je alle 6 slechts 1x getallen gebruiken, en mag je x, :, + en - gebruiken.
Nu zijn er natuurlijk oneindig veel manieren te bedenken om 6 getallen te bewerken met x, :, + en -, zeker omdat je ook kleine sommen kunt maken van 2 getallen en met het antwoord daarvan weer verder kunt rekenen.

Nu vraag ik mij af of er een programma is wat doorrekent wat het beste resultaat is, exacte uitkomst dan wel een zo dicht mogelijke benadering.

Voorbeeld
Maak met 23, 46, 22, 74 en 65 het getal 829.
Kun je met deze 6 getallen 829 maken en zo nee, wat is dan de manier om zo dicht mogelijk in de buurt te komen?

Kun je een programma schrijven dat dit probleem aankan, of is het te open en kom je dan niet verder dan alle mogelijkheden van bewerkingen met alle getallen doorrekenen?

[RobIII]

GeeBee schreef op vrijdag 25 november 2011 @ 00:02:
Voorbeeld
Maak met 23, 46, 22, 74 en 65 het getal 829.
Kun je met deze 6 getallen 829 maken en zo nee, wat is dan de manier om zo dicht mogelijk in de buurt te komen?

Met 6 getallen en vier operands is het nogal makkelijk te bruteforcen; helemaal als haakjes niet zijn toegestaan. (er zijn 11 factoren => 11! => 39.916.800 permutaties _{als ik me niet vergis} max waarbij er nog een shitload afvallen omdat 2 operators naast elkaar of twee getallen zonder operator ertussen bijvoorbeeld natuurlijk niet zinnig is)

edit:
Pedorus' benadering lijkt me nauwkeuriger, maar 't is laat en ik ben wel eens helderder geweest

Maar dit is gewoon een variant op de bekende 24 game

[ Voor 28% gewijzigd door RobIII op 25-11-2011 00:41 ]

[pedorus]

Lijkt me http://www.chifr.com/nl
Ik heb het zeer sterke vermoeden dat ze daar ook gewoon bruteforcen, dat is minder dan (6!*4^5 <=) 1.000.000 doorrekeningen. Overigens voldoet je voorbeeld niet aan 1..50

[Rone]

GeeBee schreef op vrijdag 25 november 2011 @ 00:02:

Voorbeeld
Maak met 23, 46, 22, 74 en 65 het getal 829.
Kun je met deze 6 getallen 829 maken?

Nee, want dat zijn vijf getallen. Verder is zoiets inderdaad te realiseren door een programma alle mogelijke combinaties uit te laten voeren en vervolgens te controleren op de juiste uitkomst. Daarnaast bestaat er niet zoiets als het 'beste' resultaat; de uitkomst is simpelweg wel of geen 829, en aangezien je verplicht bent om alle zes getallen te gebruiken (met daartussen dus vijf operands met keuze uit vier) zijn alle juiste oplossingen in principe gelijkwaardig.

En waarom heet dit topic 'Cijfers en letters' als het alleen over getallen gaat?

[ Voor 6% gewijzigd door Rone op 25-11-2011 01:18 ]

[RobIII]

Rone schreef op vrijdag 25 november 2011 @ 00:28:
Daarnaast bestaat er niet zoiets als het 'beste' resultaat

Nou ja, tenzij je 829 niet zou kunnen vormen en je wel 828 en 831 zou kunnen vormen. 828 is dan "het beste" resultaat (want, 1 van 829 vandaan)

Rone schreef op vrijdag 25 november 2011 @ 00:28:
En waarom heet dit topic 'Cijfers en letters' als het alleen over getallen gaat?

Omdat "Cijfers" zo kort is? Zal 't even fixen...

[ Voor 28% gewijzigd door RobIII op 25-11-2011 01:21 ]

[Rone]

RobIII schreef op vrijdag 25 november 2011 @ 00:31:

Nou ja, tenzij je 829 niet zou kunnen vormen en je wel 828 en 830 zou kunnen vormen. 828 is dan "het beste" resultaat (want, 1 van 829 vandaan)

Dat is waar, ik had kennelijk te veel een 'je doet het goed of je doet het niet'-mentaliteit.

[pedorus]

Kon het trouwens toch niet laten om het even uit te proggen. Ik kom op 4 mogelijkheden voor het voorbeeld:

46-74=-28
-28+65=37
37*23=851
851-22=829

46+65=111
111-74=37
37*23=851
851-22=829

65+46=111
111-74=37
37*23=851
851-22=829

65-74=-9
-9+46=37
37*23=851
851-22=829

[Bee.nl]

pedorus schreef op vrijdag 25 november 2011 @ 00:57:
Kon het trouwens toch niet laten om het even uit te proggen. Ik kom op 4 mogelijkheden voor het voorbeeld:

[..]

Eigenlijk zijn al jouw varianten gelijk aan mekaar, dus je hebt hier maar 1 unieke oplossing. Even helemaal uitschrijven geeft: (46 - 74 - 28 + 64) * 23 - 22= 829. In jouw voorbeeld verander je alleen de volgorde van de getallen (met hun operands) binnen de haakjes, maar dat levert geen andere berekening op.
Dus er is nog ruimte voor optimalisatie

[Aloys]

RobIII schreef op vrijdag 25 november 2011 @ 00:31:
[...]

Nou ja, tenzij je 829 niet zou kunnen vormen en je wel 828 en 830 zou kunnen vormen. 828 is dan "het beste" resultaat (want, 1 van 829 vandaan)

Whahah, doe je dat nou expres ? | 829-830 | = | 829-828 | , volgens mij is het bedtijd .

[RobIII]

Aloys schreef op vrijdag 25 november 2011 @ 01:19:
[...]

Whahah, doe je dat nou expres ? | 829-830 | = | 829-828 | , volgens mij is het bedtijd .

Bedtijd Fixed...

[Soultaker]

pedorus schreef op vrijdag 25 november 2011 @ 00:57:
Kon het trouwens toch niet laten om het even uit te proggen.

Ik ook niet, maar ik heb wel de moeite genomen om niet-canonieke expressies uit te filteren (dat levert bovendien wat snelheidswinst op) en dan is er, zoals Bee.nl al zei, maar één oplossing.

Prolog:

pickone([This|Tail], This, Tail).
pickone([Head|Tail], That, [Head|Rest]) :- pickone(Tail, That, Rest).

solve([Expr], Goal, [], Expr) :- Goal is Expr.

solve(Stack, Goal, Numbers, Answer) :-
    pickone(Numbers, N, OtherNumbers),
    solve([N|Stack], Goal, OtherNumbers, Answer).

solve([A,B|Stack], Goal, Numbers, Answer) :-
    binop(A,B,C), \+forbidden(C), solve([C|Stack], Goal, Numbers, Answer).

binop(A, B, A + B).
binop(A, B, A - B).
binop(A, B, A * B).
binop(A, B, rdiv(A, B)) :- Y is B, Y \= 0.  % can't divide by zero!

% These are forbidden not because they are wrong, but because we want to
% generate canonical expressions only:

forbidden((_ + (_ + _))).       % write ((A + B) + C) instead of (A + (B + C))
forbidden((_ * (_ * _))).       % write ((A * B) * C) instead of (A * (B * C))
forbidden(((_ - _) + _)).       % write ((A + B) - C) instead of ((A - C) + B)
forbidden((_ - (_ - _))).       % write ((A + B) - C) instead of (A - (C - B))
forbidden(A + B) :- X is A, Y is B, X > Y.  % write (B + A) instead of (A + B)
forbidden(A * B) :- X is A, Y is B, X > Y.  % write (B * A) instead of (A * B)

:- forall(solve([], 829, [23, 46, 22, 74, 65], Answer), writeln(Answer)).

Uitvoer:

23* (46+65-74)-22

Zonder forbidden/1 worden álle oplossingen geprint (en dan kom ik in totaal op 16) maar het is wel fijn om alleen canonieke oplossingen te hebben (al kun je discussiëren over wat canoniek precies is). (Prolog is een fijne taal voor dit soort combinatorische problemen, trouwens!)

[pedorus]

Ik heb het spel daadwerkelijk eens gespeeld, en zou nu een oplossing definiëren aan de hand van de uitkomsten van de tussenstappen. Als deze uitkomsten anders zijn (of een brongetal/operatie anders is), ze positief zijn, en ze gehele getallen zijn, dan zou ik zeggen dat er een andere oplossing is.
Van de 16 mogelijkheden blijven er zo 3 over in het voorbeeld:

46 + 65 = 111
111 - 74 = 37
23 * 37 = 851
851 - 22 = 829

74 - 46 = 28
65 - 28 = 37
23 * 37 = 851
851 - 22 = 829

74 - 65 = 9
46 - 9 = 37
23 * 37 = 851
851 - 22 = 829

Mijn definitie is niet exact hetzelfde als die van het spel zelf, aangezien ik toch wel sterk vind dat http://www.chifr.com/nl/2011/11/19 maar 2 oplossing kent in plaats van 4. De volgende oplossingen ziet het origineel als verschillend, maar ik zie niet in wat er echt verschillend aan is:

    1 + 8 = 9
    9 × 4 = 36
    100 × 50 = 5000
    5000 / 8 = 625
    625 - 36 = 589

    100 × 50 = 5000
    5000 / 8 = 625
    1 + 8 = 9
    9 × 4 = 36
    625 - 36 = 589

Prolog is trouwens een stuk handiger voor dit soort zaken inderdaad, hoewel ik niet heb getest of dat ook maar een paar seconden kost voor de oplossing bij 6 getallen (of misschien juist sneller is). Mijn code is met c#/IEnumerable<string>, en niet erg geoptimaliseerd.

[GeeBee]

Nou iedereen bedankt voor de reacties tot nu toe.
Het was idd 00:02, dus de getallen waren er geen 6 maar 5 en inderdaad ook niet allemaal uit de range 1..50
Met 'het beste' resultaat bedoelde ik een berekening die het doelgetal niet exact als resultaat heeft, maar van alle mogelijkheden wel het dichtste in de buurt zit.
Qua programmeren ben ik een noob (beetje Pascal en houdt het wel mee op), maar ik zal dit blijven volgen.

De site Chifr kende ik nog niet, maar heeft niet de eis om verplicht alle 6 getallen te gebruiken. De vraag is ook hoe die aan het doelgetal komt.
Worden er 6 getallen gegenereerd waarmee vervolgens een antwoord wordt gemaakt dat daarna als doelgetal wordt gepresenteerd?

[ Voor 26% gewijzigd door GeeBee op 25-11-2011 19:34 ]

[Soultaker]

pedorus schreef op vrijdag 25 november 2011 @ 10:51:
Ik heb het spel daadwerkelijk eens gespeeld, en zou nu een oplossing definiëren aan de hand van de uitkomsten van de tussenstappen.

Hmm, dat vind ik raar. Dan zou je 2+3+4=9 ook kunnen schrijven als 2+4+3=9 of 3+4+2=9, maar feitelijk is dat natuurlijk hetzelfde omdat + gewoon commutatief is. Vandaar dat ik 23*(46+65-74)-22 de enige echte oplossing vind voor 829 (of één van de varianten, natuurlijk).

Overigens klopt mijn normalisatie-code ook niet helemaal. Ik zal er nog eens dieper over nadenken.

Prolog is trouwens een stuk handiger voor dit soort zaken inderdaad, hoewel ik niet heb getest of dat ook maar een paar seconden kost voor de oplossing bij 6 getallen (of misschien juist sneller is).
Mijn code is met c#/IEnumerable<string>, en niet erg geoptimaliseerd.

Prolog duurt in dit geval ook maar een paar seconden, maar uiteindelijk zal C# wel sneller zijn. Het ging vooral om het gemak om het programma te schrijven.

[pedorus]

Soultaker schreef op vrijdag 25 november 2011 @ 20:32:
Hmm, dat vind ik raar. Dan zou je 2+3+4=9 ook kunnen schrijven als 2+4+3=9 of 3+4+2=9, maar feitelijk is dat natuurlijk hetzelfde omdat + gewoon commutatief is.

Het was ingegeven door hoe die site het doet. Na iedere tussenstap van 2 getallen en operatie ontstaat er een nieuw getal aan de linkerkant dat je kan gebruiken. Zodoende is het logisch om naar die getallen te kijken. Als je geen tussenstappen geeft, dan is het niet al te logisch inderdaad.

GeeBee schreef op vrijdag 25 november 2011 @ 19:31:
De site Chifr kende ik nog niet, maar heeft niet de eis om verplicht alle 6 getallen te gebruiken. De vraag is ook hoe die aan het doelgetal komt.
Worden er 6 getallen gegenereerd waarmee vervolgens een antwoord wordt gemaakt dat daarna als doelgetal wordt gepresenteerd?

Ik kende de website chifr ook nog niet, maar aangezien je dit draadje "Cijfers en letters" had genoemd kwam het als eerste uit google.. Ik neem aan dat ze voor iedere dag wat getallen genereren, en dit herhalen totdat ze een combinatie vinden die oplosbaar is. Vervolgens geven ze nog een moeilijkheidslabel naar aanleiding van het aantal oplossingen dat ze vinden (met geheeltallige, positieve deelstappen).

GeeBee schreef op vrijdag 25 november 2011 @ 19:31:
Qua programmeren ben ik een noob (beetje Pascal en houdt het wel mee op), maar ik zal dit blijven volgen.

Als je in plaats van een kloppend resultaat op zoek wil naar de "beste match" dan is dat met mijn code niet heel veel aanpaswerk (logica en test vooraan toevoegen, check op geheel wegcommenten). Maar ik zou eigenlijk denken dat wel/geen resultaat genoeg is om te weten of een spelletje klopt. En dan kun je het er nog over hebben of iets als 2,5,5,10 een correct raadsel is bij het spelletje 24.

Evengoed kan iets als 1,5,7,7 voor 24 een interessante zijn om de 'beste match' te vinden.

spoiler:

Is het antwoord met 23 of dat met 24.5 als uitkomt nu het beste?

Overigens, 24 met negatieve getallen kan ook best lastig zijn, zie hier bijvoorbeeld mensen falen om de oplossingen die er wel zijn te vinden..

[ Voor 0% gewijzigd door pedorus op 25-11-2011 21:48 . Reden: stomme tikfout (1,2 ipv 5,7,7), bedankt :) ]

[arnold_m]

spoiler:

De beste match is ((7*7)-1)/2.

[Tharulerz]

arnold_m schreef op vrijdag 25 november 2011 @ 21:37:

spoiler:

De beste match is ((7*7)-1)/2.

Als je de 5 vervangt door een 2 krijg je natuurlijk gewoon een andere opgave

[pedorus]

Er stond ook een 2