A feladat 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 é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"
]

A feladat célja egy olyan utkozesek függvény elkészítése, amely egy csutka adott mezőire, adott elforgatással elhelyezendő elemekről megállapítja, hogy mely elemek ütköznek egymással. 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 lehelyez listája. Minden elhelyezést egy {sorok, i, j, f} négyes ír le, amelynek jelentése a következő:
   • A sorok lista egyforma hosszú sztringekből áll, és az elem elforgatás nélküli (0 fokos) alakját írja le.
   • Az i az elem referencia-kukoricaszemének sorindexe a csutkán (0 ≤ i < n).
   • A j az elem referencia-kukoricaszemének oszlopindexe a csutkán (0 ≤ j < m).
   • Az f logikai érték az elem elforgatását jelzi: false esetén az elemet nem forgatjuk el (0 fok), true esetén pedig 180 fokkal forgatjuk el.
   Feltételezheti, hogy mindegyik elem úgy van elhelyezve, hogy minden kukoricaszeme a csutkán helyezkedik el, azaz nem lóg le róla.

A függvény visszatérési értéke egy {a, b} párokból álló lista, amelynek minden párjára 0 ≤ a < b < length(lehelyez) teljesül. A lista pontosan azokat az a. és b. (nullától kezdődő) indexű elemek párjait tartalmazza, amelyek a csutkára helyezve ütköznének egymással, azaz a csutka valamelyik mezőjét mindkét elem lefedné kukoricaszemmel. A lista elemeit növekvő lexikografikus sorrendben adja meg.

Elixir-specifikációk

  @type meret() :: pos_integer() # a csutka sorainak vagy oszlopainak szá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 elem() :: [String.t()] # egy elem szöveges leírása
  @type lehelyezes() :: { elem :: elem(), i :: sorindex(), j :: oszlopindex(), f :: forgatas() } # egy elem lehelyezése
  @type elemindex() :: non_neg_integer() # hivatkozás egy lehelyezett elemre
  @type utkozes() :: { a :: elemindex(), b :: elemindex() } # lehelyezett elemek ütközése, a < b
  @spec utkozesek(n :: meret(), m :: meret(), lehelyez :: [lehelyezes()]) :: ut :: [utkozes()]
  # Az n sorból és m oszlopból álló csutkára az elemeket a lehelyez lista szerint helyezve pontosan
  # az ut elempárok ütköznek egymással, lexikografikusan növekvő sorrendben felsorolva.
  

Egyéb követelmények

  defmodule Khf2 do
  @moduledoc """
  Ütköző kukoricaelemek megkeresé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 á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> Khf2.utkozesek(3, 5, [
...>   {["OXO"], 0, 1, false},
...>   {["XO", "O "], 1, 3, false}
...> ])
[]

iex> Khf2.utkozesek(3, 5, [
...>   {["OXO"], 1, 4, false},
...>   {["XO", "O "], 2, 4, true}
...> ])
[{0, 1}]

iex> Khf2.utkozesek(4, 5, [
...>   {["OXO"], 1, 1, false},
...>   {["XOO", "  O"], 1, 1, false},
...>   {["X", "O"], 2, 3, false}
...> ])
[{0, 1}, {1, 2}]

iex> Khf2.utkozesek(3, 4, [
...>   {["XO"], 1, 1, false},
...>   {["X", "O"], 1, 1, false},
...>   {["OOO", " X "], 1, 1, false}
...> ])
[{0, 1}, {0, 2}, {1, 2}]

Segédanyagok

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

Tudnivalók a beadásról