Moeilijkste som naar getal

[Predje]

Dag,

Ik zou graag een stuk code schrijven wat de moeilijkste som naar een getal berekend.

Stel ik heb 1, 4, 6 en 5 en + - x / en wil naar 100.
Dan kan ik doen 5*4*(6-1).

Maar kan ik nu met code bepalen of het nog op andere manieren kan en zoja wat dan de meest complexe variant is? Meeste * of /, meeste stappen, meeste getallen gebruikt.

Meeste getallen kan ik natuurlijk tellen met code, meeste stappen ook.

[Woy]

Je zult ten eerste moeten definieren wat "De meest complexe" betekend.

Verder kun je alle permutaties van mogelijke syntax trees berekenen, en dan daar van kijken wat de hoogste complexiteit heeft.

Wat heb je zelf al geprobeerd?

[Predje]

Zelf heb ik nog geen code geschreven, omdat ik echt niet weet waar te beginnen en of het überhaupt mogelijk is.

[Joolee]

Predje schreef op donderdag 12 juni 2014 @ 13:15:
Zelf heb ik nog geen code geschreven, omdat ik echt niet weet waar te beginnen en of het überhaupt mogelijk is.

Of het mogelijk is is afhankelijk van hoeveel mogelijkheden er zullen zijn. "De moeilijkste" vinden bij ∞ is erg lastig
Zo te zien heb je een beperkte set cijfers in gedachte, als je dat niet doet dan zul je andere beperkingen moeten stellen. Zoals bijvoorbeeld dat cijfers alleen groter mogen worden (dus geen - en /) of dat cijfers nooit dubbel mogen voor komen.

Zoals je het zelf bedacht hebt kom je op een beperkt aantal bewerkingen en combinaties uit. Er zijn ongetwijfeld talloze algoritmes te vinden van mensen die precies doen wat jij wil al is het misschien leuk om het zelf te proberen.

Als je alle mogelijke bewerkingen hebt dan zul je moeten verzinnen welke het meest complex is. Hier zul je toch eerst zelf over de regels moeten nadenken. Waarom vindt je die bepaalde bewerking uit een set nou het meest complex?

[Predje]

Ik wil inderdaad uitgaan van een vaste set getallen en een vast doel.
Daarnaast ook een vast aantal operatoren.
Er is dus sprake van een set invoer en een doel.

Zelf denk ik aan een "punten" systeem om te bepalen hoe "complex" een berekening is.
Elk getal = 1 punt, + - = 2, * / = 3.
Dus bijv doel 25 (input van vijf vijven, ze hoeven niet allemaal gebruikt te worden)
5*5 = 5 punten
5+5+5+5+5 = 9 punten
5*5+5-5 = 9 punten
5*5*5/5 = 13 punten

1)Ik moet dus bepalen of ik met de invoer getallen tot het doelgetal kan komen.
2)Als dat mogelijk is, dan op hoeveel verschillende manieren.
3)En van die manieren adhv een puntensysteem bepalen wat de moeilijkste is.

1 kan met trial en error, maar ik denk dat dat slechte performance geeft.

[Barryvdh]

Hoe belangrijk is performance? Een computer is natuurlijk wel goed in dit soort berekeningen, dus je kan best wel snel veel mogelijkheden proberen.

[Joolee]

Predje schreef op donderdag 12 juni 2014 @ 13:35:
Ik wil inderdaad uitgaan van een vaste set getallen en een vast doel.
Daarnaast ook een vast aantal operatoren.
Er is dus sprake van een set invoer en een doel.

Zelf denk ik aan een "punten" systeem om te bepalen hoe "complex" een berekening is.
Elk getal = 1 punt, + - = 2, * / = 3.
Dus bijv doel 25 (input van vijf vijven, ze hoeven niet allemaal gebruikt te worden)
5*5 = 5 punten
5+5+5+5+5 = 9 punten
5*5+5-5 = 9 punten
5*5*5/5 = 13 punten

1)Ik moet dus bepalen of ik met de invoer getallen tot het doelgetal kan komen.
2)Als dat mogelijk is, dan op hoeveel verschillende manieren.
3)En van die manieren adhv een puntensysteem bepalen wat de moeilijkste is.

1 kan met trial en error, maar ik denk dat dat slechte performance geeft.

1 kun je combineren met 2. Waarschijnlijk zul je inderdaad bruteforce moeten werken maar je kunt hier wel slimme regels aan toevoegen. Je kunt alle sommen welke je hebt uitgeprobeerd natuurlijk al uitsluiten bij de volgende pogingen. Als je 2*3 hebt geprobeerd en nooit uit komt dan hoef je 3*2 ook niet te proberen en (4-1)*2 ook niet.

[ResuCigam]

Predje schreef op donderdag 12 juni 2014 @ 13:35:

5*5*5/5 = 13 punten

Zo kun je nog wel even doorgaan 5*5*5/5*5/5*5/5= 27 punten.

[Predje]

ResuCigam schreef op donderdag 12 juni 2014 @ 13:46:
[...]


Zo kun je nog wel even doorgaan 5*5*5/5*5/5*5/5= 27 punten.

Nee want ik heb maar 5 vijven.

Ik heb vooraf een vast aantal cijfers en operatoren.

Dus doel 100;
set 1: 4, 2, 4, 6, 7, *, -
set 2: 3, 4, 1, *, /, +

Per set: is het mogelijk? Wat is het hoogte aantal punten haalbaar.


Ik denk trouwens dat ik niet bruteforce elke optie hoef te weten.

Ik denk dat een "top-down" manier beter gaat werken.
Eerst proberen om met alle operators tot het doel te komen, cijfers kunnen wel brutoforce geprobeerd worden.
Mocht dat nooit lukken dan eerst de "lagere" operators eruit.
Nog niet gelukt, dan een "hoge" operator ruilen voor een lage.

Ik hoef uiteindelijk slechts het hoogst haalbare puntenaantal te bepalen.

[Woy]

Als je inderdaad alleen het hoogst aantal haalbare punten hoeft te weten, kun je alle verschillende permutaties inderdaad van hoog naar laag genereren en controleren, dan kun je stoppen op het moment dat je een match hebt. Bij het genereren is het ook handig om rekening te houden met de eigenschappen van de operatoren ( Associativiteit, Commutativiteit ), daardoor is het aantal cases dat je moet genereren een stuk kleiner.