LISPで配列(APG4b EX18)
呼び水的初心者アウトプット風LISP記事第三弾.第二弾にて,コンスセルやリスト構造について扱ったので,今回は配列にしました.記述例は引き続きCommon Lisp(SBCL)です.
配列を扱う関数・構文
配列表記およびmake-array
1次元配列(ベクタ)は,S式によるリスト表現の頭に('
ではなく)#
を付けます.n次元(n≧2)の場合は#nA
とします.
* #(A B)
#(A B)
* #2A((A B) (C D))
#2A((A B) (C D))
* #3A(((A B) (C D)) ((E F) (G H)))
#3A(((A B) (C D)) ((E F) (G H)))
S式表記ではなく関数で配列を生成する場合は,make-array
を用います.要素数を指定する必要があり,2次元以上はリストで示します.初期値は:initial-element
で指定します(デフォルト値は0).
* (make-array 2)
#(0 0)
* (make-array '(2 2))
#2A((0 0) (0 0))
* (make-array '(2 2 2))
#3A(((0 0) (0 0)) ((0 0) (0 0)))
* (make-array '(2 2 2) :initial-element 'A)
#3A(((A A) (A A)) ((A A) (A A)))
aref
および値の変更
aref
は,添字で配列の値を参照する関数です.
* (aref #(A B) 0)
A
* (aref #(A B) 1)
B
* (aref #2A((A B) (C D)) 0 0)
A
* (aref #2A((A B) (C D)) 1 1)
D
* (aref #3A(((A B) (C D)) ((E F) (G H))) 1 1 1)
H
配列の値を変更する場合は,属性リストの値変更と同じくsetf
構文を用います.Common Lispでは,配列に限らず,参照する関数と組み合わせて値を変更するためにsetf
を用います.
* (defparameter DIM #2A((A B) (C D)))
DIM
* (aref DIM 1 0)
C
* (setf (aref DIM 1 0) 'Z)
Z
* DIM
#2A((A B) (Z D))
なお,上記実行例のdefparameter
は,値に新しく記号を対応付けるための構文です.
利用例:APG4b EX18
配列の利用例として,AtCoderのAtCoder Programming Guide for beginners (APG4b)の多次元配列問題『EX18 - ゲーム大会』の解答例をCommon Lispで書き直してみました.本来はC++学習用ですが,AtCoderではC++以外の多くのプログラミング言語でも解答を提出することができ,結果を得ることができます.下記コードは次のスコアで正解(AC)しています.
【実行時間】23 ms
【メモリ】26264 KB
【コード長】523 Byte
(let* ((N (read))
(M (read))
(A (make-array M))
(B (make-array M))
(L (make-array (list N N) :initial-element "-")))
(dotimes (i M)
(setf (aref A i) (read))
(setf (aref B i) (read)))
(dotimes (i M)
(decf (aref A i))
(decf (aref B i))
(setf (aref L (aref A i) (aref B i)) "o")
(setf (aref L (aref B i) (aref A i)) "x"))
(dotimes (i N)
(dotimes (j N)
(princ (aref L i j))
(if (eq j (- N 1))
(terpri)
(princ " ")))))
上記プログラムのうち,let*
は値に記号を一時的に対応付ける構文,dotimes
は繰り返しの構文,decf
はデクリメントを行う構文,read
は入力関数,princ
は出力関数,terpri
は改行を出力する関数です.
(おまけ)リスト処理の場合
参考までに,同じ問題をリスト処理および再帰関数処理のみで記述したのが次のコードです.こちらも正解していますが,実行時間,使用メモリ,コード長共に,配列を用いた記述と比べて数倍となっています.これは,配列を用いた場合は値の書き換えおよび単純な繰り返しで処理を行っているのに対し,こちらは,値を変更するたびにリスト構造をコピーしていることに加え,最適化が行われない非末尾再帰型の関数処理を繰り返しているためです.
【実行時間】423 ms
【メモリ】85992 KB
【コード長】1030 Byte
(labels ((readmatch (m)
(if (= m 0) nil
(cons (cons (read) (read))
(readmatch (- m 1)))))
(makecheck (AB n c)
(if (null AB) "-"
(let ((r (car AB)))
(cond ((equal r (cons n c)) "x")
((equal r (cons c n)) "o")
(t (makecheck (cdr AB) n c))))))
(makematchn (AB n c)
(if (= n 0) nil
(cons (makecheck AB n c)
(makematchn AB (- n 1) c))))
(makematch (AB c n)
(if (= c 0) nil
(cons (makematchn AB n c)
(makematch AB (- c 1) n)))))
(let ((NM (cons (read) (read))))
(let ((r (makematch (readmatch (cdr NM))
(car NM) (car NM))))
(mapc (lambda (x)
(mapc (lambda (c) (princ c) (princ " "))
(reverse (cdr x)))
(princ (car x))
(terpri))
(reverse r)))))
備考
更新履歴
- 2020-11-13:初版公開
Author And Source
この問題について(LISPで配列(APG4b EX18)), 我々は、より多くの情報をここで見つけました https://zenn.dev/ytaki0801/articles/4e8e91641e691020dc3f著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol