Als startpunt voor een getallenpuzzel krijg je een tabel met gehele getallen. De tabel telt $$M$$ rijen en $$N$$ kolommen. De puzzel wordt als "opgelost" beschouwd, als elke kolom dezelfde somwaarde heeft. Om dit te realiseren, mag je enkel binnen een rij van de tabel, elementen cylisch permuteren.

Klasse SomPuzzel

Schrijf een klasse SomPuzzel, met volgende methoden:

• een constructor met 1 argument, namelijk een lijst van lijsten. Deze lijst van lijsten stelt de originele puzzel voor, en bestaat uit $$M$$ lijsten van elk $$N$$ elementen.
• een methode __str__() die de puzzel als lijst van lijsten afdrukt
• de operator << met bijhorende magic function __lshift__(self, other). De operator verwacht als tweede argument een tuple, bestaande uit twee gehele getallen $$(a, b)$$. Het effect van de operator is dat op de rij met rangnummer $$a$$ van de puzzel, een cyclische permutatie uitgevoerd wordt. Deze permutatie bestaat erin dat de rij $$b$$ keer naar links geschoven wordt. In elke schuifoperatie worden de elementen van de rij 1 positie naar voor geschoven, en het eerste element komt op het eind te staan. Je mag aannemen dat $$0 \le a \lt M$$. Let op : het effect van de operator is een wijziging van de waarde van het linkeroperand van de operator. De operator levert voor de rest GEEN resultaat (dus eigenlijk resultaat None).
• de methode fout() (zonder argumenten). Deze methode berekent een foutmaat die aangeeft in hoeverre de puzzel opgelost is. Dit resultaat komt als volgt tot stand:
  • bereken elke kolomsom $$S_i$$ (er zijn dus $$N$$ dergelijke kolomsommen)
  • bereken het gemiddelde van deze $$N$$ kolomsommen $$G$$
  • de fout is dan gegeven door:
    $$ fout = \sqrt{\sum_{i=0}^{N-1} (S_i - G)^2} $$

Voorbeeld

p = SomPuzzel([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
str(p)				# '[[1, 2, 3], [4, 5, 6], [7, 8, 9]]'
p.fout()			# 4.242640687119285
p << (1, 2)
str(p)				# '[[1, 2, 3], [6, 4, 5], [7, 8, 9]]'
p.fout()			# 2.449489742783178
p << (2, 1)
str(p)				# '[[1, 2, 3], [6, 4, 5], [8, 9, 7]]'
p.fout()			# 0.0

Klasse SomPuzzelRandom

Deze klasse erft over van de klasse SomPuzzel, en beschikt bijkomend over:

• een constructor met 2 argumenten, namelijk de tabel die de puzzel voorstelt (zie klasse SomPuzzel) en een geheel getal, dat het maximaal toegelaten aantal zetpogingen $$Z$$ om de puzzel op te lossen aangeeft
• een methode solve() zonder argumenten. Deze methode poogt de puzzel op te lossen, in hoogstens $$Z$$ zetten. Een zet waarvan het effect nagegaan werd, maar die niet effectief doorgevoerd werd, telt hierbij mee (en wordt dus geteld bij de zetpogingen, waarvan het maximum dus $$Z$$ bedraagt). Hierbij ga je als volgt tewerk:
  • indien de fout kleiner dan of gelijk is aan 0.1 of het maximaal aantal pogingen tot zetten bereikt is, worden geen verdere zetten ondernomen
  • in het andere geval, wordt een willekeurige te proberen zet bepaald, via

    a = random.randint(0, aantal_rijen - 1)
    b = random.randint(1, aantal_kolommen -1)
    

    Indien de zet gunstig is, m.a.w. de fout strikt kleiner wordt door de zet door te voeren, wordt ze ook effectief doorgevoerd. In het andere geval wordt ze niet doorgevoerd.
  • het resultaat van de methode is een lijst van de effectief doorgevoerde zetten, waarbij elke zet voorgesteld wordt door het tuple (a, b).

Let erop dan je de generatie van randomgetallen precies uitvoert zoals aangegeven (en ook geen extra randomgetallen genereert), anders is controle via Dodona van dit onderdeel niet mogelijk. Voor de eerste 2 testcases op Dodona is de random seed gelijk aan 200.

Voorbeeld

p = SomPuzzelRandom([[4, 9], [3, 6], [8, 2], [2, 3], [1, 8], [8, 10], [6, 4], [3, 9], [6, 2]], 100)
str(p)		# '[[4, 9], [3, 6], [8, 2], [2, 3], [1, 8], [8, 10], [6, 4], [3, 9], [6, 2]]'
p.solve()	# [(0, 1), (3, 1)]
str(p)		# '[[9, 4], [3, 6], [8, 2], [3, 2], [1, 8], [8, 10], [6, 4], [3, 9], [6, 2]]'

Klasse SomPuzzelGulzig

Ook deze klasse erft over van de klasse SomPuzzel. Ze definieert bijkomend:

• een methode beste_zet() (zonder argumenten). Deze methode zoekt tussen alle mogelijke schuifoperaties (je overloopt dus alle rijen, en past alle mogelijke schuifoperaties "naar links" toe), de best mogelijke zet. Deze is gedefinieerd als de zet die de fout het kleinst maakt. Zijn er meerder zetten mogelijk, dan kies je de zet met kleinste rij-nummer. Zijn nog altijd meerdere zetten mogelijk, dan kies je voor het kleinst aantal verschuivingen. Het resultaat van de methode is een tuple $$(a, b)$$ ($$a$$ geeft het rijnummer aan, $$b$$ het aantal posities waarover cyclisch naar links geschoven wordt). De puzzel zelf wordt NIET aangepast ! Indien geen enkele zet de fout laat dalen, dan is het resultaat van de methode $$(0, 0)$$.
• de methode solve() : deze methode past de beste zetten toe, zolang die via de hierboven beschreven methode kunnen gevonden worden. Wanneer geen zetten meer mogelijk zijn die de fout laten dalen, stopt de methode. Het resultaat van de methode is een lijst van de toegepaste zetten. Deze lijst wordt afgesloten met de zet $$(0, 0)$$.

Voorbeeld

p = SomPuzzelGulzig([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
str(p)			# '[[1, 2, 3], [4, 5, 6], [7, 8, 9]]'
p.beste_zet()	# (0, 1)
str(p)			# '[[1, 2, 3], [4, 5, 6], [7, 8, 9]]'
p.solve()		# [(0, 1), (1, 2), (0, 0)]
str(p)			# '[[2, 3, 1], [6, 4, 5], [7, 8, 9]]'