A feladvány

A megoldandó feladat

Fájl beolvasására a File.read!/1, kiírására a File.write!/2 függvény használatát javasoljuk.

to_internal/1

A to_internal függvénynek egyetlen paramétere van: a feladvány szöveges ábrázolását tartalmazó fájl neve, ill. teljes elérési útja (lásd a példákban nhf1_f1.txt-t és nhf1_f2.txt-t).

A fájlban sorok vannak, a sorok szavakból állnak; a sorokat egy vagy több újsor-jel, a szavakat egy vagy több szóköz-jellegű (whitespace) karakter választja el egymástól. A szavak egész számok, fákat jelölő csillagok (*) és üres parcellákat jelölő kötőjelek (-) lehetnek. A fájl első nemüres sora a sátrak oszloponként elvárt számát tartalmazza, és egyúttal meghatározza, hogy a kertben az egyes sorokban hány parcella van. A fájl többi sorának első szava a sátrak soronként elvárt számát adja meg, a többi szó pedig az egyes parcellák tartalmát (fa vagy üres). Ha egy szövegsorból a parcellák számánál kevesebb szó olvasható be, a többi parcellát üresnek kell tekinteni, ha pedig több szó olvasható be, a fölösleges szavakat el kell dobni.

A to_internal függvény visszatérési értéke egy hármas: a sátrak soronkénti számát tartalmazó lista, a sátrak oszloponkénti számát tartalmazó lista, valamint a fákat tartalmazó parcellák koordinátáit tartalmazó lista (a koordináták lexikálisan növekvő sorrendjében).

A mátrix helyességét nem kell ellenőriznie, azaz feltételezheti, hogy a mátrix minden sorában azonos a szavak száma, a sátrak oszloponkénti, ill. soronkénti számát megadó szavak pozitív (esetleg negatív) egész számok, a mátrix többi szava vagy *, vagy -, és a szavakat egy vagy több szóköz-jellegű karakter választja el. Megengedett, hogy a fájlban üres sorok vagy csak szóköz-jellegű karaktereket tartalmazó sorok legyenek, továbbá a sorok elején és végén is lehetnek szóköz-jellegű karakterek.

to_external/3

A to_external függvénynek három paramétere van. Az első a feladványt leíró hármas, ami a to_internal függvény visszatérési értékével azonos felépítésű. A második a sátrak fákhoz viszonyított helyzetét leíró irányok listája. Az irány jelzésére az égtájak angol nevének kezdőbetűit használjuk: N (északra), E (keletre), S (délre), W (nyugatra). A harmadik paraméter a feladvány szöveges ábrázolását tartalmazó fájl neve, ill. teljes elérési útja: ezt kell létrehoznia a függvénynek (lásd a példákban nhf1_r1.txt-t, nhf1_r2.txt-t és nhf1_r3.txt-t).

A fájlban sorok vannak, a sorok szavakból állnak; a sorokat egy-egy újsor-jel, a szavakat egy vagy több szóköz-jellegű karakter választja el egymástól. A szavak egész számok, sátrakat jelölő N, E, S vagy W betűk, fákat jelölő csillagok (*), valamint üres parcellákat jelölő kötőjelek (-) lehetnek. Egy-egy oszlopban minden szó legyen egyforma hosszú és vezető szóközökkel jobbra illesztett. Ennek az a célja, hogy a megjelenített mátrix könnyen olvasható legyen. Az oszlopszélességet célszerű a sátrak oszloponkénti számát megadó listában a legtöbb helyet elfoglaló (esetleg negatív) szám alapján meghatározni.

A fájl első nemüres sora a sátrak oszloponként elvárt számát tartalmazza. A fájl többi sorának első szava a sátrak soronként elvárt számát adja meg, a többi szó pedig az egyes parcellák tartalmát (fa, sátor vagy üres).

A to_external/3 függvény visszatérési értéke a :ok atom.

Feltételezheti, hogy a feladványt leíró hármas hibátlan, azaz a sátrak oszloponkénti, ill. soronkénti számát megadó listában csak pozitív (esetleg negatív) egész számok vannak, és a listák elemszáma azonos az oszlopok, ill. sorok számával. Azt is feltételezheti, hogy a fák pozícióját leíró listában csak koordinátapárok vannak, és ezek mindegyike a mátrixon belüli pozíciót ad meg. Abban is biztos lehet, hogy a sátrak fákhoz viszonyított helyzetét leíró listában csak a megengedett betűk (NEWS) vannak. Az utóbbi lista elemszáma azonban lehet kisebb is, nagyobb is, mint a fák pozícióját megadó lista elemszáma. Azt is garantáljuk, hogy ugyanabba a parcellába nem rakunk egynél több sátrat, továbbá fa helyére sem rakunk sátrat. Ha a sátrak száma nagyobb a fák számánál, a fölösleges sátrakat el kell dobni.

A to_external/3 függvénynek nem feladata, hogy a megoldás helyességét ellenőrizze: a kapott paraméterek szerinti mátrixot meg kell jeleníteni a feljebb leírtak figyelembe vételével.

check_sol/2

A check_sol függvénynek két paramétere van, melyek a feladvány egy megoldását jelentik: az első a feladványt leíró hármas, a második a sátrak fákhoz viszonyított helyzetét leíró irányok listája, mindkettő azonos a to_external/3 függvény első két paraméterével.

A check_sol függvény visszatérési értéke az adott megoldás esetleges hibáit leíró {err_diff, err_rows, err_cols, err_touch} négyes. Elemei olyan kulcs-érték párok, melyekben a kulcs a hibafajtára utal, az érték pedig a hibahelyeket felsoroló lista. A részleteket a formális Elixir-specifikációkban találja.

A to_external/3 függvénynél leírtakat feltételezheti itt is a feladványt leíró hármasról és sátrak irányát leíró listáról.

Az ún. létraversenyben (ld. Egyéb tudnivalók, vö. tantárgyi adatlap, félévi követelmények) az Nhf1.check_sol/2 függvény hatékonyságát fogjuk vizsgálni, azaz a tárigényét és a futási idejét fogjuk mérni, összehasonlítani nagyobb méretű feladványokkal. Ezért ha megajánlott jegyet szeretne kapni, törekedjen hatékony megoldásra.

Elixir-specifikációk

Típusok egy parcella koordinátáinak megadására

  @type row   :: integer    # sor száma (1-től n-ig)
  @type col   :: integer    # oszlop száma (1-től m-ig)
  @type field :: {row, col} # egy parcella koordinátái

Típusok a feladvány leírására

  @type tentsCountRows :: [integer] # a sátrak száma soronként
  @type tentsCountCols :: [integer] # a sátrak száma oszloponként

  @type trees       :: [field]   # a fákat tartalmazó parcellák koordinátái
  @type puzzle_desc :: {tentsCountRows, tentsCountCols, trees} # a feladványleíró hármas

Típusok a sátrak helyzetének leírására

  @type dir       :: :N | :E | :S | :W # a sátorpozícikók iránya: North, East, South, West
  @type tent_dirs :: [dir]         # a sátorpozíciók irányának listája a fákhoz képest

Típusok a lehetséges hibák jelzésére

  @type cnt_tree  :: integer                              # a fák száma a kertben
  @type cnt_tent  :: integer                              # az elemek száma a sátorpozíciók irányának listájában
  @type err_diff  :: %{err_diff:  [{cnt_tree, cnt_tent}]} # a lista nem üres, ha cnt_tent !== cnt_tree
  @type err_rows  :: %{err_rows:  [integer]}              # a sátrak száma rossz a felsorolt sorokban
  @type err_cols  :: %{err_cols:  [integer]}              # a sátrak száma rossz a felsorolt oszlopokban
  @type err_touch :: %{err_touch: [field]}                # a felsorolt koordinátájú sátrak másikat érintenek
  @type errs_desc :: {err_diff, err_rows, err_cols, err_touch} # hibaleíró négyes

A három függvény specifikációja

  @spec to_internal(file::String.t) :: pd::puzzle_desc
  # A file fájlban szövegesen ábrázolt feladvány leírója pd

  @spec to_external(pd::puzzle_desc, ds::tent_dirs, file::String.t) :: :ok
  # Az {rs, cs, ts} = pd feladványleíró és a ds sátorirány-lista alapján
  # a feladvány szöveges ábrázolását írja ki a file fájlba, ahol
  #   rs a sátrak soronként elvárt számának a listája,
  #   cs a sátrak oszloponként elvárt számának a listája,
  #   ts a fákat tartalmazó parcellák koordinátájának listája

  @spec check_sol(pd::puzzle_desc, ds::tent_dirs) :: ed::errs_desc
  # Az {rs, cs, ts} = pd feladványleíró és a ds sátorirány-lista
  # alapján elvégzett ellenőrzés eredménye a ed hibaleíró, ahol
  #   rs a sátrak soronként elvárt számának a listája,
  #   cs a sátrak oszloponként elvárt számának a listája,
  #   ts a fákat tartalmazó parcellák koordinátájának a listája
  # Az {e_diff, e_rows, e_cols, e_touch} = ed négyes elemei olyan
  # kulcs-érték párok, melyekben a kulcs a hiba jellegére utal, az
  # érték pedig a hibahelyeket felsoroló lista (üres, ha nincs hiba)

Példák

Nhf1.to_internal/1

  nhf1_f1.txt == nhf1_r1.txt
      1  0  2  0  2
   1  -  *  -  -  -
   1  -  -  -  -  -
   0  -  -  *  -  *
   3  -  -  -  -  -
   0  *  -  -  -  *

  iex> puzzle1 = Nhf1.to_internal "nhf1_f1.txt"
  {[1, 1, 0, 3, 0], [1, 0, 2, 0, 2], [{1, 2}, {3, 3}, {3, 5}, {5, 1}, {5, 5}]}

  nhf1_f2.txt
      1  0 -2  0  2
   1  -  *  -  -  -
   1  -  -  -  -  -
  -1  -  -  *  -  *
   3  -  -  -  -  -
   0  *  -  -  -  *

  iex> puzzle2 = Nhf1.to_internal "nhf1_f2.txt"
  {[1, 1, -1, 3, 0], [1, 0, -2, 0, 2], [{1, 2}, {3, 3}, {3, 5}, {5, 1}, {5, 5}]}

Nhf1.to_external/3

  nhf1_r2.txt          nhf1_r3.txt
      1  0  2  0  2        1  0 -2  0  2
   1  -  *  E  -  -     1  -  *  E  -  -
   1  -  -  -  -  N     1  -  -  -  -  N
   0  -  -  *  -  *    -1  -  -  *  -  *
   3  N  -  S  -  N     3  N  -  S  -  -
   0  *  -  -  -  *     0  *  -  -  W  *

  iex> Nhf1.to_external puzzle1, [], "nhf1_r1.txt"
  :ok

  iex> Nhf1.to_external puzzle1, [:E,:S,:N,:N,:N], "nhf1_r2.txt"
  :ok

  Nhf1.to_external puzzle2, [:E,:S,:N,:N,:W,:E], "nhf1_r3.txt"
  :ok

Nhf1.check_sol/2

  iex> Nhf1.check_sol puzzle1, [:E,:S,:N,:N,:N]
  {%{err_diff: []}, %{err_rows: []}, %{err_cols: []}, %{err_touch: []}}

  Nhf1.check_sol puzzle1, [:E,:S,:N,:N,:N, :E]
  {%{err_diff: [{5, 6}]}, %{err_rows: []}, %{err_cols: []}, %{err_touch: []}}

  Nhf1.check_sol puzzle2, [:E,:S,:N,:N,:W, :E]
  {%{err_diff: [{5, 6}]}, %{err_rows: [4, 5]}, %{err_cols: [4, 5]}, %{err_touch: [{4, 3}, {5, 4}]}}

Egyéb követelmények

  defmodule Nhf1 do
  @moduledoc """
  Sátrak
  @author "Egyetemi Hallgató <egy.hallg@dp.vik.bme.hu>"
  @date   "2021-10-16"
  ...
  """
  ...
  end

  @doc """
    A check_sol függvény ellenőrzi a sátrak előírásszerű elhelyezését a kertben.
  """

  @spec hany_eves(x:: integer, t::String.t, z::any) :: n::integer 
  # Az árbóc x hosszából, a kikötő t nevéből és a csillagok z állásából
  # a kapitány n életkora úgy számítható ki, hogy vesszük... 
  

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

Segédanyagok

1. Sablon a program megírásához: dp_nhf1_sablon.ex
2. Szkript a tesztesetek futtatásához: dp_nhf1_teszt.exs
3. Fájlok a tesztesetek futtatásához: nhf1_f1.txt, nhf1_f2.txt, nhf1_r1.txt, nhf1_r2.txt, nhf1_r3.txt

Dokumentációs követelmények

Egyéb tudnivalók