[python] Vergelijking met 88 variabelen oplossen

[Boudewijn]

hoihoi

Ik ben zoals elk jaar weer bezig met de NBV-puzzel en daar zit wel een geinige opgave in die ik wilde programmeren:




Nu kun je hier natuurlijk een vergelijking schrijven in de vorm van:

37 = w1 + w2 + w7
43 = w1 + w7 + 12

et cetera et cetera. Dan is het handig om rechts in het midden van de puzzle te beginnen (daar vind je 4x 1). Hierbij is wN de waarde van veld N. Ik verwacht dat dit initieel best wel veel opties oplevert , maar gezien er 88 velden zijn dit aantal fors inkakt.

Dit uitwerken vind ik een leuke oefening voor mezelf; ik heb in het verleden dingen met allerlei gare SAT-solvers gedaan (Alloy ed) maar eigenlijk nooit met Python. Ik ben me er ook terdege van bewust dat dit soort middelen niet noodzakelijk is voor het oplossen van de puzzle.

Enige waar ik me zorgen om maak is dat het aantal opties uit de hand loopt. Als je gewoon wat arrays aanmaakt en slim gaat reduceren houdt het vrij snel op. Dus wellicht is er een library die dit goed aan kan pakken. Iemand tips?

Nu wilde ik eens naar numpy voor de vergelijkingen kijken, maar ook naar sympy. Heeft iemand nog wat libs of algemene trucs hiervoor?

[ Voor 6% gewijzigd door Boudewijn op 21-12-2017 22:44 ]

[Vaan Banaan]

Mijn gevoel zegt, dat het niet zo gruwelijk uitgebreid hoeft te worden.
Die 4 x 1 lijkt me wel het sleutelvak.
Daarna zou je de vakjes daarboven en rechtsboven (via blauwe 23 en 30) moeten kunnen oplossen.
Dat zijn maar 2 vergelijkingen met 2 onbekenden.
En dan zo steeds verder uitbreiden
-edit-
Nee, dan houd je nog steeds hetzelfde probleem, het zijn 2 vergelijkingen met 3 onbekenden (de 17 is ook een onkende)
Hmm, van het weekend eens verder bekjken....

[ Voor 22% gewijzigd door Vaan Banaan op 22-12-2017 13:31 ]

[Bennnie]

Zoals de opgave er nu uitzien kun je niet gemakkelijk zien welke blauwe cel bij welke witte cel hoort, programmeer technisch word het nog veel lastiger om alles uit elkaar te houden. Ik heb deze vraag opgelost door de structuur aan te passen. Door de grote witte vlakken 3 breed te maken ten opzichte van de kleine witte vlakken en blauwe vlakken, kon ik gemakkelijk waardes controleren door te zeggen "blauw vlak = cel boven + cel rechts + cel onder + cel links". Misschien kun je, als je het in die structuur zet, een methode bedenken waarmee je het probleem kunt oplossen. Ik heb het niet in python of een andere programmeertaal opgelost.

[marc1990]

Wat je wilt doen is de volgende vergelijk oplossen:
Ax=b
Waar A is je input (sparse) matrix(vergelijken), b is vector antwoord (blauw) en x is onbekende vector (wit).
zie Wikipedia: Linear equation en hier Wikipedia: Matrix (mathematics)

Dit kan je dan oplossen met sympy.

[ Voor 16% gewijzigd door marc1990 op 22-12-2017 13:35 ]

[Knutselsmurf]

marc1990 schreef op vrijdag 22 december 2017 @ 13:29:
Wat je wilt doen is de volgende vergelijk oplossen:
Ax=b
Waar A is je input (sparse) matrix(vergelijken), b is vector antwoord (blauw) en x is onbekende vector (wit).
zie Wikipedia: Linear equation en hier Wikipedia: Matrix (mathematics)

Dit kan je dan oplossen met sympy.

Dat is niet helemaal correct. In de puzzel zal de oplossing een set natuurlijke getallen zijn, terwijl zo'n solver op zoek gaat naar een oplossing met Reële getallen.

Juist het feit dat de oplossing moet bestaan uit natuurlijke getallen is de extra voorwaarde die er voor zorgt dat er een oplossing is.

Ook lijkt het mij een goede veronderstelling dat de waarde in ieder veld niet groter is dan 26 en niet kleiner dan 1. Ook dat zal niet meegenomen worden in een solver.

[ Voor 9% gewijzigd door Knutselsmurf op 22-12-2017 13:54 ]

[MaartenBW]

Dit lijkt mij inderdaad een job voor lineare algebra.

Maar daarvoor kan je beter numpy gebruiken. Dit is prima voor matrix operaties.

Dan wil je dus x bepalen door A te inverteren en met b te vermenigvuldigen.

x = INV(A)*b


Waar bij A je matrix is met een 1 op de lokatie welke variabelen meedoen in die vergelijking.
Dus voor de eerste equtaion heb je op de eerste, tweede en 7de plek een 1, rest 0. b is op de eerste plek 37.

A wordt een matrix van 81*88
b is een vector van 83 lang
x een vector van 88

EDIT:

Voor bovenstaande moet A square zijn, dit is niet het geval aangezien je 83 equations hebt en 88 variabelen. Er is dus geen unique solution.

Je moet dus ergens nog 5 constraints vandaan halen.

[ Voor 19% gewijzigd door MaartenBW op 22-12-2017 14:28 ]

[Lrrr]

Zoals @Knutselsmurf zegt is het aannemelijk dat alle getallen natuurlijke getallen zijn, dat is dus ook een constraint. Als er maar één oplossing is die daaraan voldoet is dat natuurlijk de oplossing.

[TweakPino]

Constraint programming is een andere optie om dit op te lossen. Hierbij kun je ook aangeven dat de oplossing uit natuurlijke getallen bestaat tussen 1 en 26. In Python: https://pypi.python.org/pypi/python-constraint

[Boudewijn]

Heren,

Dank voor de tips, ik ga hier vanavond eens mee spelen. Mijn eigen oplossing die tot nu toe redelijk (!) werkt is dat ik 4 witte vierkanten neem (ik begin bij het stukje met de blauwe 4 en 8 op rechts) en alle opties bereken in een cartesiaans product. De witte velden noem ik velden, de blauwe velden noem ik constraints.
Hierna ga ik alle relevante constraints toepassen op de velden, met dien verstande dat ik over het algemeen 3 (of 2, aan de rand) van de 4 velden om een constraint wil hebben ingevuld. Op dat punt gooi ik alle permutaties die niet aan de constraints voldoen weg.

Daarna kies ik met de hand een nieuw veld, waarbij ik al zoveel mogelijk andere velden rond die constraint ken/kan raden. Daar maak ik een nieuw product van, en daarna gooi ik meteen weer alle permutaties die niet aan die constraint voldoen weg. Tactiek is dus om zodra je oplossingsspace groter wordt, deze zo snel mogelijk weer zoveel mogelijk te verkleinen.
Op deze manier krijg ik het voor elkaar om met 16gb mem en een core i5 alsnog alle opties te berekenen voor deze puzzle in Python. Niet heel mooi, maar het werkt wel (veeeeel boilerplate code ) .
Ik heb hem nu uitgeschreven tot en met veld 77 van de 88 en op een paar trage punten na ga dit wonderwel.


Blijft natuurlijk wel het punt sta dat ik het netjes met een algebra lib wil doen ipv een matrix en een berg filters .

[ Voor 4% gewijzigd door Boudewijn op 23-12-2017 14:46 ]

[TomsDiner]

Leuk probleem!

Ik denk dat het grapje is dat je een "voorselectie moet maken". Als ik alleen al naar de allerbovenste rij kijk, dan geven 6 getallen tussen de 1 en 26 maar liefst 308 miljoen mogelijke combinaties.

Als ik onderstaand programma draai in PHP, kan ik zien dat er -als ik sec naar getal 1-4 kijk, maar 16 mogelijkheden zijn:

code:

<?php
$aantal = 0;
for ($i1 = 1; $i1 < 27; $i1++){
    for ($i2 = 1; $i2 < 27; $i2++){
        for ($i3 = 1; $i3 < 27; $i3++){
            for ($i4 = 1; $i4 < 27; $i4++){
                $correct = 0;
                if ($i1+$i2 == 37) { $correct++;}
                if ($i2+$i3 == 34) { $correct++;}
                if ($i3+$i4 == 18) { $correct++;}
                if ($correct == 3){
                    $aantal++;  
                    echo "mogelijke getallen: ". $i1, " ". $i2 . " " . $i3 . " " .$i4 .  "Dit is mogelijkheid nummer:" . $aantal . "</br>";
                }
            }
        }
    }
}
echo "end of test";
?>

Dan komt door de onderlinge afhankelijkheid: als getal 1 omhoog gaat met 1, moet getal 2 omlaag met dezelfde hoeveelheid. Dat betekent dat ik getal 5 en 6 toe kan voegen aan de berekening -wat waarschijnlijk erg lang duurt- zonder dat op die rij het aantal mogelijkheden groter kan worden. Als er voor getal 4 maximaal 16 waardes kunnen, dan kan met 5 en 6 erbij hooguit het aantal mogelijkheden dalen, niet stijgen.

Ik denk dus dat je van buiten naar binnen moet werken. Ik kan het niet beredeneren, maar ik gok dat voor de hele buitenrand <16 mogelijkheden zullen zijn.

Met de tweede ring erbij, zal dit aantal misschien drastisch stijgen. Als voor de meeste potentiele waardes van de buitenring ook iets van 16 mogelijkheden zijn, heb je al 256 mogelijkheden.

Zou je dit niet net zo als een sudoku kunnen oplossen? Met wegstrepen? Alle 88 velden hebben in eerste instantie 26 mogelijke waardes. Laat het programma steeds twee witte velden vergelijken, en kijk welke combinaties niet mogelijk zijn, en streep deze waardes weg. Bijvoorbeeld veld 1 en 2 linksboven moeten samen 37 zijn. Dan kunnen beide al niet de waardes 1-10 bevatten: wegstrepen als mogelijkheid bij allebei. Zo laat je het programma alle "witte buren" vergelijken. Dat moet meerdere keren opnieuw gebeuren, omdat het aantal mogelijke getallen per veld steeds verder terugloopt. En dus ook van zijn buurmannen.

Edit: slecht gelezen. Dit moet dus minimaal met trio's. Maar het idee blijft hetzelfde

[Boudewijn]

Nou de lol is dat ik dus geen voorselectie maak. Ik voeg een veld toe, en draai vervolgens alle constraints over het model. Gooi daarna alle oplossingsversies weg die niet aan de constraints voldoen. Daarna voeg ik weer een oplossing toe. Wat ik wel doe is dat ik de keuze maak om telkens een wit veld toe te voegen, waarna ik alle zijden van een blauw veld heb ingevuld zodat ik weer heel snel mijn oplossingsspade kan verkleinen. Dit lukt best vaak, er zijn een paar uitzonderingen waarbij ik 2 witte velden in moet vullen voor dit kan.

Als je hier stukje output van mijn code pakt:

code:

218010      Step: 50 v31 
5140     Step: 51 R23 
133640      Step: 52 v32 
1690     Step: 53 R24 
43940       Step: 54 v33 
1690     Step: 55 R25 
43940       Step: 56 v34 
1035     Step: 57 R26 
26910       Step: 58 v35 
1035     Step: 59 R27 
26910       Step: 60 v36 
1035     Step: 61 R28 
26910       Step: 62 v37 
1035     Step: 63 R29 
26910       Step: 64 v38 
1035     Step: 65 R30 
26910       Step: 66 v39 
1035     Step: 67 R31 
26910       Step: 68 v40 
1035     Step: 69 R32 
26910       Step: 70 v41 
957  Step: 71 R33 
24882       Step: 72 v42 
957  Step: 73 R34

Elke keer dat ik of een veld toevoeg, of een constraint toevoeg, dan is dat een stap. Aan het begin van de regel staat het aantal valide oplossingen in het model.

Een R<x> regel is het toevoegen van een blauw veld, een v<x> regel is het toevoegen van een wit veld (en dus in potentie een 26-voudidiging van de oplossingen). Zoals je ziet kan ik het aantal opties relatief beschaafd houden .

Dit heb ik alleen zelf gebouwd, ik wil het eigenlijk van de week eens met een echte algebralib doen.

[ Voor 15% gewijzigd door Boudewijn op 24-12-2017 01:53 ]