A feladat a 2. kis házi feladathoz hasonlóan egy térbeli kirakós játékot vizsgál. A játék célja, hogy egy henger alakú kukoricacsutkára összetapadt kukoricaszemekből álló elemeket helyezzük el úgy, hogy a csutka minden részét pontosan egyszer fedjük be.

A játékot egy olyan n×m méretű, azaz n sorból és m oszlopból álló négyzetráccsal modellezhetjük, ahol az oszlopindexet modulo m szerint értelmezzük. Így például egy 4×5 méretű csutkán a {2, 0} és {2, 5} párok ugyanazt a mezőt jelölik.

Az összetapadt kukoricaszemekből álló elemekre a következő jelölést vezetjük be: ha az elem belefér egy k×l méretű négyzetrácsba, akkor egy k elemű, egyenként l karakteres sztringből álló listával ábrázoljuk. A sztringek kizárólag a ?\s (szóköz), ?O, ?X karakterekből állnak. Ezeknek a jelentése az alábbi:

• A ?\s karakterek az üres helyeket jelölik, ahol nincs kukoricaszem.
• A ?O karakterek a kukoricaszemeket jelölik. Feltételezheti, hogy a kukoricaszemek összefüggő elemet alkotnak.
• Az elemben egyetlen kukoricaszem ?O karakter helyett ?X karakterrel van megjelölve. Ez a referencia-kukoricaszem. Amikor azt mondjuk, hogy az elemet a csutkán a {i, j} mezőre helyeztük, akkor a referencia-kukoricaszem a csutka i. sorában és j. oszlopában foglal helyet.

Mivel a csutka hengeres, az elemek is egy hengerpalástra illeszkednek. Ezért az elemeket csak 0 vagy 180 fokkal forgathatjuk el. Ha az elem a csutkán a sztringek listájával leírt elrendezésben található meg, azt mondjuk, hogy 0 fokkal van elforgatva. A másik lehetséges elforgatás a referencia-kukoricaszem körül történő 180 fokos elforgatás (azaz középpontos tükrözés).

A feladat célja a Khf3 modul elkészítése, melynek függvényei a kirakós megoldását segítik.

kezdet

A modul kezdet függvénye létrehoz egy új megoldó-állapotot. A feladatban ennek a szerkezetét nem specifikáljuk, any() típusú. A függvény argumentumai az alábbiak:

1. A csutka sorainak n száma, ahol 0 < n.
2. A csutka oszlopainak m száma, ahol 0 < m.
3. A csutkára helyezendő elemek keszlet készlete. Ez egy olyan Elixir map, ahol a kulcsok az elemek alakjai, az értékek pedig pozitív egész számok, melyek azt adják meg, hogy az adott elemből hány darab áll rendelkezésre.

lerak

A modul lerak függvénye egy elemet helyez el a csutkára. A függvény argumentumai az alábbiak:

1. Az előző megoldó-állapot, azaz az allapot.
2. A lerakandó elem elem alakja.
3. A lerakandó elem referencia-kukoricaszemének i sorindexe, ahol 0 ≤ i < n.
4. A lerakandó elem referencia-kukoricaszemének j oszlopindexe, ahol 0 ≤ j < m.
5. Az f paraméter true, ha az elemet 180 fokos forgatás (középpontos tükrözés) után helyezzük el a csutkán, false, ha nem.

A lerak függvény visszatérési értéke a lerakás utáni új megoldó-állapot.

Feltételezheti, hogy a lerakandó elem alakja a kezdet függvénynek átadott elemkészletben szerepel, abból még legalább egy példány rendelkezésre áll, és az elemet a csutkán ütközés és lelógás nélkül lehet elhelyezni.

hova

A modul hova függvénye meghatározza, hogy egy adott alakú elem hová helyezhető el a csutkára. A függvény argumentumai az alábbiak:

1. Az aktuális megoldó-állapot, azaz az allapot.
2. A lerakandó elem elem alakja.

A hova függvény visszatérési értéke az összes olyan {i, j, f} hármasból álló lista, ahol a lerak függvény által meghatározott módon (azaz ütközés és lelógás nélkül) az elem alakú elem lerakható a csutkára az i, j, f pozícióra az allapot megoldó-állapotban. A lista elemeinek sorrendje tetszőleges.

Feltételezheti, hogy a lerakandó elem a kezdet függvénynek átadott elemkészletben szerepel. Ha az elemet nem lehet szabályos módon elhelyezni a csutkán, vagy már minden példányát elhelyeztük a csutkán, a visszaadott lista legyen üres.

felvesz

A modul felvesz függvénye felveszi az utoljára lerakott elemet a csutkáról. Egyetlen argumentuma az aktuális allapot megoldó-állapot, és visszatérési értéke a felvétel után kapott új megoldó-állapot.

Feltételezheti, hogy a csutkán legalább egy lerakott elem van már.

Elixir-specifikációk

  @type allapot() :: any() # a megoldó-állapot
  @type meret() :: pos_integer() # a csutka sorainak vagy oszlopainak száma
  @type elem() :: [String.t()] # egy elem szöveges leírása
  @type db() :: pos_integer() # elemek darabszáma

  @type sorindex() :: non_neg_integer() # a csutka egy sorának indexe
  @type oszlopindex() :: non_neg_integer() # a csutka egy oszlopának indexe
  @type forgatas() :: boolean() # false: nincs forgatás; true: 180 fokos forgatás
  @type lehelyezes() :: { i :: sorindex(), j :: oszlopindex(), f :: forgatas() } # egy elem lehelyezése
  
  @spec kezdet(n :: meret(), m :: meret(), keszlet :: %{ elem() => db() }) :: kezdo_allapot :: allapot()
  # Létrehozza az n sorból és m oszlopból álló üres csutkához
  # és a teljes keszlet-hez tartozó kezdeti megoldó-állapotot.

  @spec lerak(allapot :: allapot(), elem :: elem(), i :: sorindex(), j :: oszlopindex(), f :: forgatas()) :: uj_allapot :: allapot()
  # Az uj_allapot az allapot megoldó-állapotból az elem i, j, f
  # paraméterek szerinti elhelyezésével kapott új megoldó-állapot.

  @spec hova(allapot :: allapot(), elem :: elem()) :: l :: [lehelyezes()]
  # l az allapot megoldó-állapotban az elem összes szabályos
  # elhelyezését felsoroló lista; a lista sorrendje tetszőleges.

  @spec felvesz(allapot :: allapot()) :: uj_allapot :: allapot()
  # Az uj_allapot az allapot megoldó-állapotból az utoljára lerakott elem
  # felvételével kapott új megoldó-állapot.
  

Egyéb követelmények

  defmodule Khf3 do
  @moduledoc """
  Kukorica kirakási lépések kiértékelése
  @author "Egyetemi Hallgató <egy.hallg@edu.bme.hu>"
  @date   "2026-10-xx"
  """
  ...
  end

A beadott programokat Linux környezetben Elixir 1.20 (Erlang/OTP 29) rendszerrel teszteljük.

Példák

Az alábbi példák egyetlen IEx-munkamenet egymás után végrehajtandó lépéseit mutatják. A piece_a alakú elem egyszer, a piece_b alakú elem kétszer áll rendelkezésre. Az ábrák mindig az ugyanabban a sorban következő hova/2 hívás előtti kirakós-elrendezést mutatják.

Az ábrák mezőiben az őket lefedő elemek indexe látható. Ha egy mezőn több elem is található, az összes indexet feltüntetjük. A félkövér index azt jelzi, hogy az adott elemnek ezen a mezőn van a referencia-kukoricaszeme. Az elemeket a 0., 1. és 2. indexhez rendre sárga, kék és zöld háttér jelöli.

iex> piece_a = ["XO", " O"]
["XO", " O"]
iex> piece_b = ["X", "O"]
["X", "O"]
iex> s0 = Khf3.kezdet(3, 4, %{piece_a => 1, piece_b => 2}); :ok
:ok
iex> Khf3.hova(s0, piece_b) |> length()
16

iex> s1 = Khf3.lerak(s0, piece_a, 1, 0, true); :ok
:ok
iex> Khf3.hova(s1, piece_b)
[{0, 1, false}, {0, 2, false}, {1, 1, false},
 {1, 1, true}, {1, 2, false}, {1, 2, true},
 {2, 1, true}, {2, 2, true}]

iex> s2 = Khf3.felvesz(s1); :ok
:ok
iex> Khf3.hova(s2, piece_b) |> length()
16

iex> s3 = Khf3.lerak(s2, piece_b, 0, 0, false); :ok
:ok
iex> Khf3.hova(s3, piece_b)
[{0, 1, false}, {0, 2, false}, {0, 3, false},
 {1, 1, false}, {1, 2, false}, {1, 3, false},
 {1, 1, true}, {1, 2, true}, {1, 3, true},
 {2, 1, true}, {2, 2, true}, {2, 3, true}]

iex> s4 = Khf3.lerak(s3, piece_b, 0, 1, false); :ok
:ok
iex> Khf3.hova(s4, piece_b)
[]

Az s4 kirakós-elrendezésben a piece_b alakú elem már nem helyezhető le, mert a készletben egyetlen példány sem maradt. Ez akkor is így van, ha például az {0, 2, false} elhelyezés geometriailag szabályos lenne. A piece_a alakú elemet az s1 kirakós-elrendezésben leraktuk, majd az s2 kirakós-elrendezésben felvettük, ezért abból ekkor ismét egy példány áll rendelkezésre; az állapotváltozást a felvesz/1 hívás mutatja.

Segédanyagok

• Sablon a program megírásához: khf3_sablon.exs

Tudnivalók a beadásról