A kukorica feladvány

A kukorica kirakós egy térbeli kirakós játék. 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 kirakós elemei és az összerakott játék. Képek forrása: thill.me.

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).

elem = [
  "X ",
  "O ",
  "OO"
]

Az 1. nagy házi feladat

Az első nagy házi feladat a megold/1 függvény megírása. A függvény paraméterei a következők:

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.

Megoldható feladvány esetén a függvény visszatérési értéke a feladvány egy lehetséges megoldása, azaz az elemek olyan lehelyezése, amelyben a keszlet-ben szereplő minden elemet ütközés- és lelógásmentesen elhelyeztünk a csutkán, úgy, hogy a csutka minden mezőjét pontosan egy elem fedje le.

Az elemek lehelyezéseit {i, j, f} hármasokkal írjuk le (0 ≤ i < n, 0 ≤ j < m), ahol i és j rendre a lehelyezett elem referencia-kukoricaszemének sor- és oszlopindexe, f pedig true, ha az elemet 180 fokkal elforgattuk (középpontosan tükröztük), egyébként false.

A visszaadott megoldás egy olyan Elixir map, ahol a kulcsok az elemek alakjai, a hozzájuk tartozó értékek pedig a lehelyezéseket tartalmazó listák. A listákon belül a lehelyezések sorrendje tetszőleges.

A keszlet minden kulcsához tartozó összes példányt le kell helyezni, azaz length(megoldas[elem]) === keszlet[elem] a keszlet minden elem kulcsára. A megoldas más kulcsokat nem tartalmazhat.

Ha a keszlet által megadott készlettel a kirakós nem oldható meg, a függvény visszatérési értéke nil legyen. Feltételezheti azonban, hogy a rendelkezésre álló elemek összesen pontosan n×m kukoricaszemet tartalmaznak.

Feltételezheti még azt is, hogy a bemenet jól formált, azaz helyes méreteket, elem-leírásokat és darabszámokat tartalmaz.

Bár érdemes törekedni a minél hatékonyabb algoritmus írására, programját csak nem túl nagy méretű feladványokkal fogjuk tesztelni. De ha jó vagy jeles megajánlott jegyet szeretne kapni a létraversenybe való bejutással, és jó helyezést elérni a létraversenyen (lásd: Egyéb tudnivalók), akkor ügyeljen a hatékonyságra. Teljesítménymérésre használhatja a Benchee modult.

Elixir-specifikációk

  @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 megold(n :: meret(), m :: meret(), keszlet :: %{ elem() => db() }) :: megoldas :: %{ elem() => [lehelyezes()] } | nil
  # A n sorból és m oszlopból álló üres csutkán a keszlet elemek
  # egy lehetséges helyes elhelyezése megoldas, vagy nil, ha nincs ilyen.
  

Példa

Az alábbi példa két különböző alakú elemmel tölti ki a 3×4 méretű csutkát: két L alakú és egy téglalap alakú elemmel. Az egyik L alakú elem 180 fokkal el van forgatva, a téglalap alakú elem pedig a 3. oszlopból a 0. oszlopba ér körbe. Az ábrán a mezőkben az őket lefedő elem indexe látható, a félkövér index pedig a referencia-kukoricaszemet jelöli.

iex> piece_a = ["XO", "O "]
["XO", "O "]
iex> piece_b = ["XO", "OO", "OO"]
["XO", "OO", "OO"]
iex> keszlet = %{piece_a => 2, piece_b => 1}
%{["XO", "O "] => 2, ["XO", "OO", "OO"] => 1}
iex> Nhf1.megold(3, 4, keszlet)
%{["XO", "O "] => [{0, 1, false}, {2, 2, true}],
 ["XO", "OO", "OO"] => [{0, 3, false}]}

Egyéb követelmények

      defmodule Nhf1 do
      @moduledoc """
      Kukorica-kirakós
      @author "Egyetemi Hallgató <egy.hallg@edu.bme.hu>"
      @date   "2026-11-xx"
      ...
      """
      ...
      end

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

Segédanyagok

1. Sablon a program megírásához: nhf1_sablon.exs

Dokumentációs követelmények

Egyéb tudnivalók