A számtekercs feladvány

Az 1. nagy házi feladat

A függvény egyetlen paramétere a feladványt írja le, visszatérési értéke pedig a feladvány összes megoldásának a listája, tetszőleges sorrendben. Ha egy feladványnak nincs megoldása, a visszatérési érték az üres lista. Egy-egy megoldás a kitöltött táblát írja egész számokból álló listák listájaként. Minden szám a tábla egy mezőjének értéket adja meg: ha 0, a mező üres, egyébként pedig az i értek, ahol 1<=i<=m.

Megoldásának nem kell nagyon hatékonynak lennie, azaz alkalmazhatja a generate-and-test módszert: állítsa elő az összes lehetséges elrendezést, és gyűjtse össze közülük azokat, amelyeket egy ugyancsak megírandó ellenőrző segédfüggvény helyesnek talál. 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.

Az 1. ábrán bemutatott feladvány esetén például a helix/1 függvény paramétere:

{6, 3, [{{1,5},2},{{2,2},1},{{4,6},1}]}

A 2. ábrán látható megoldást írja le például az alábbi (egyelemű) megoldás-lista:

     [[[1,0,0,0,2,3],
       [0,1,2,3,0,0],
       [0,3,1,2,0,0],
       [0,2,3,0,0,1],
       [3,0,0,0,1,2],
       [2,0,0,1,3,0]]
     ]

Elixir-specifikációk

Típusok a feladvány alapadatainak megadására

      @type size()  :: integer() # tábla mérete (0 < n)
      @type cycle() :: integer() # ciklus hossza (0 < m <= n)
      @type value() :: integer() # mező értéke (0 < v <= m)

Típusok egy mező 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 n-ig)
      @type field() :: {row(), col()}  # mező koordinátái

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

      @type field_value() :: {field(), value()}                 # mező és értéke
      @type puzzle_desc() :: {size(), cycle(), [field_value()]} # feladvány

Típusok az eredmény leírására

      @type retval()    :: integer()    # eredménymező értéke (0 <= rv <= m)
      @type solution()  :: [[retval()]] # egy megoldás
      @type solutions() :: [solution()] # összes megoldás

A helix/1 függvény specifikációja

      @spec helix(sd::puzzle_desc()) :: ss::solutions()
      # ss az sd feladványleíróval megadott feladvány összes megoldásának listája

Példa

Az 1. ábrán látható feladvány a 2. ábrán látható megoldással:

  iex> Nhf1.helix({6, 3, [{{1,5},2},{{2,2},1},{{4,6},1}]})
  [[[1,0,0,0,2,3],[0,1,2,3,0,0],[0,3,1,2,0,0],[0,2,3,0,0,1],[3,0,0,0,1,2],[2,0,0,1,3,0]]
    

Egyéb követelmények

      defmodule Nhf1 do
      @moduledoc """
      Számtekercs
      @author "Egyetemi Hallgató <egy.hallg@dp.vik.bme.hu>"
      @date   "2024-10-14"
      ...
      """
      ...
      end

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

Segédanyagok

1. Sablon a program megírásához: nhf1_sablon.ex
2. Szkript a tesztesetek futtatásához: nhf1_teszt.exs

Dokumentációs követelmények

Egyéb tudnivalók