はじめに
言語処理100本ノック言語処理100本ノックという面白いサイトを見つけました。
言語処理アルゴリズムの解決を求める課題ですが、普通にLipsまたはLisp学習者にとっても良問です。
第1章: 準備運動の中から00～04の設問にチャレンジしましたので投稿します。
課題の自力解決は難しかったので解答サイトをカンニングしました。(ヽ(ﾟдﾟ)ノ ええじゃないか)
解答サイトはpythonを使っているのですが、私はpythonの知見がないので次の手順で取り組みました。
- 解答サイトのPythonコードをAIでJS変換する
- JSでPythonコードの内容を理解する
- AIでJSをLipsに書き換える
- AIが提案したコードの手直し(Lipsでサポートしていない関数の修正、制御フローの見直し等)
環境
OS:
windows11 - wsl(ubuntu 20.04.6 LTS)
node.js: v24.11.1
インストール手順は適当な紹介サイトをご参照してください。
Lips:
手順はNode.jsをインストールした後、下記のコマンドを実行することでインストールできました。
npm install -g lips@beta
手順サイト : https://lips.js.org/docs/intro#nodejs
私はVSCodeを使っていますが、ターミナルで"lips -quiet"または"lips xxxx.scm"のようにコマンドをたたけば
お手軽に動作確認できます。
[!NOTE]
OSはWindowsを使っています。Windowsのcmdおよびpowrshellでは問題ありませんが
WSL(Ubuntu)でREPLを起動したとき入力プロンプトが出てきませんでした。
スクリプトの実行は問題ありません。
Windowsのcmdまたはpowershellであれば問題ないです。
00. 文字列の逆順
文字列"stressed"の文字を逆に（末尾から先頭に向かって）並べた文字列を得よ．
JavaScript
//1 文字列を配列に展開 [ 's', 't', 'r', 'e', 's', 's', 'e', 'd' ]
//2 配列に転換した文字配列を反転する
//3 文字を連結して文字列を作る
console.log([..."stressed"] .reverse().join(''))
//実行 : node chlg1_00.js -> desserts
Lips
(console.log
;;1 文字列を配列に展開 [ 's', 't', 'r', 'e', 's', 's', 'e', 'd' ]
;;2 配列に転換した文字配列を反転する
;;3 文字を連結して文字列を作る
(list->string (reverse (string->list "stressed")))
)
;;実行 : lips chlg1_00.scm -> desserts
01. 「パタトクカシーー」
「パタトクカシーー」という文字列の1,3,5,7文字目を取り出して連結した文字列を得よ．
奇数列の文字を取り出して文字列化するということですね。
| 0 | ① | 2 | ③ | 4 | ⑤ | 6 | ⑦ |
|---|---|---|---|---|---|---|---|
| パ | タ | ト | ク | カ | シ | ー | ー |
JavaScript
//1 文字列を配列に展開 ["パ","タ","ト","ク","カ","シ","ー","ー"]
//2 奇数インデックスだけ残す
//3 文字を連結して文字列を作る
console.log([..."パタトクカシーー"].filter((_, i) => i % 2 !== 0).join(""));
//実行 : node chlg1_01.js -> タクシー
Lips
LipsはJSのようにインデックス付きの文字列を扱いができないのでインデックス値のリストが別に必要です。
インデックス値の条件をチェック箇所をfilterで行う方法と単純にforループ内のチェックする例を示します。
;;1 文字列を配列(リスト)に展開する(chars) ("パ","タ","ト","ク","カ","シ","ー","ー")
;;2 1のリスト長分の数値リスト(0..7)を作成する(range)
;;3 2の数値リストから奇数の数値リストを作成する(filter)
;;4 3の数値リストをmapに食べさせてmap中の処理で文字リスト(chars)から奇数位置にある文字を取り出す
;;5 4の結果を文字列化する(list->string)
(let ((chars (string->list "パタトクカシーー")))
(console.log (list->string
(map (lambda (i) (list-ref chars i))
(filter odd? (range (length chars)))))
)
)
;;;実行 : lips chlg1_01.scm -> タクシー
私のように関数指向に不慣れな場合はforループ内を使う方法が分かり易いと思います。
(let ((text "パタトクカシーー") (rslt ""))
(let loop ((i 0) (len (length text)) )
;; インデックス値が奇数であれば文字列から文字を抽出して出力バッファに結合(string-append)する
;; string-refで取り出した値は文字型(例 #\a)になるのでstring関数で文字列変換する
(if (odd? i) (set! rslt (string-append rslt (string (string-ref text i)))))
(if (< i len) (loop (+ i 1) len))
)
(console.log rslt)
)
;;;実行 : lips chlg1_01.scm -> タクシー
02. 「パトカー」＋「タクシー」＝「パタトクカシーー」
「パトカー」＋「タクシー」の文字を先頭から交互に連結して文字列「パタトクカシーー」を得よ．
| 0 | 1 | 2 | 3 |
|---|---|---|---|
| パ | ト | カ | ー |
| タ | ク | シ | ー |
JavaScript
console.log([..."パトカー"].map((char, i) => char + "タクシー"[i]).join(""));
//実行例 : node chlg1_03.js -> パタトクカシーー
Lips
(let ((str-list (map (
lambda (c1 c2) (string c1 c2)
) (string->list "パトカー") (string->list "タクシー"))
))
;;applyを使う理由:mapの戻り値はリストになっているため。'("パタ" "トク" "カシ" "ーー")
;;appendするために個別の文字列にする必要がある。(string-append "パタ" "トク" "カシ" "ーー")
(console.log (apply string-append str-list))
)
;;;実行例 : lips chlg1_02.scm -> パタトクカシーー
03. 円周率
"Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."という文を
単語に分解し，各単語の（アルファベットの）文字数を先頭から出現順に並べたリストを作成せよ．
JavaScript
const text1_3 = "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics.";
const text1_cleaned = text1_3.replace(/,/g, ""); // カンマを削除
const words = []; //スペースで分割して配列に入れなおす
for (const x of text1_cleaned.split(" ")) {
lis.push(x);
}
//各語の文字列サイズを取得する
const len_words = words.map(y => y.length);
console.log(len_words);
//実行例 : node chlg1_03.js ->
// [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 10]
Lips
(let* ((text1_3 "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics.")
;; 1. 正規表現でカンマを空文字に置換(JSのString.replaceと同じ)
(text1_cleaned (replace #/,/g "" text1_3 ))
;; 2. スペースで分割してリスト化
(words (string-split " " text1_cleaned))
;; 3. 各単語の長さを取得 (map)
(len_words (map string-length words))
)
(for-each (lambda (i)
(display i) (display ","))
len_words)
(newline)
)
;;;実行例 : lips chlg1_03.scm -> 3,1,4,1,5,9,2,6,5,3,5,8,9,7,10,
数学弱者の私はこのお題にひるみそうになりました。言語処理における円周率とは何かをgeminiに問い合わせました。
geminiによると数学的な意味ではなく簡単に言うと多角的に文字列処理を見るという比喩的な意味合いのようです。
04. 元素記号
"Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause.
Arthur King Can."という文を単語に分解し，1, 5, 6, 7, 8, 9, 15, 16, 19番目の単語は先頭の1文字，
それ以外の単語は先頭に2文字を取り出し，取り出した文字列から単語の位置（先頭から何番目の単語か）への
連想配列（辞書型もしくはマップ型）を作成せよ．
ほしい結果 :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| H | He | Li | Be | B | C | N | O | F | Ne | Na | Mi | Al | Si | P | S | Cl | Ar | K | Ca |
英語speakersが20元素を暗記するためのフレーズなのですね。知りませんでした。
JavaScript
const text = "Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can.";
const num = [1, 5, 6, 7, 8, 9, 15, 16, 19];
const dict = {}; //結果保存用の連想配列
// ピリオドを除去してスペースで分割して配列にする
const text_no_dot = text.replace(/\./g, "");
const arr_text = text_no_dot.split(" ");
arr_text.forEach((v, i) => {
const index = i + 1;
if (num.includes(index)) {
// 指定されたi+1番目(arr_text[i+1])の単語は先頭1文字をキー名にする
dict[v.slice(0, 1)] = index;
} else {
// それ以外(arr_text[i])は先頭2文字をキー名にする
dict[v.slice(0, 2)] = index;
}
});
console.log(JSON.stringify(dict));
//実行例 : node chlg1_04.js
Lips
(let* (
(text "Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can.")
;; ピリオドを取り除き、スペースで分割して配列にする
(arr-text (string-split " " (replace #/\./g "" text)))
(num '(1 5 6 7 8 9 15 16 19))
)
;; 語毎にループで処理する。結果(dict)は連想リスト(Alist)に保管する
(let loop ((words arr-text) (i 0) (dict '()))
(if (null? words)
(display (reverse dict))
(let* ( ; else
(word (car words))
;; 文字列リストのインデックスをチェックして抽出する文字列サイズ(1 or 2)を決める
(key (substring word 0 (if (member i num) 1 2)))
)
(loop ; 次のループに進む
(cdr words) ; 次の検索リスト
(+ i 1) ; 次のインデックス(+1)
(cons (cons key i) dict) ; key-valueのリストを積み上げる
)
)
)
)
)
;;; 実行例 : node chlg1_04.scm ->
;;; ((H . 1) (He . 2) (Li . 3) (Be . 4) (B . 5) (C . 6) (N . 7) (O . 8) (F . 9) (Ne . 10) (Na . 11) (Mi . 12) (Al . 13) (Si . 14) (P . 15) (S . 16) (Cl . 17) (Ar . 18) (K . 19) (Ca . 20))
処理が小さい内はloopでもよいですが、処理内容が複雑になると見通しが悪くなりますよね。再帰関数のパターンも考えました。
(define (extract-elements words i num-list)
(if (null? words)
'() ;; 空リストを返して終了
(let* (
(word (car words))
(key-len (if (member (+ i 1) num-list) 1 2)) ; インデックスの調整
(key (substring word 0 key-len))
)
(cons (cons key (+ i 1))
(extract-elements (cdr words) (+ i 1) num-list)))
)
)
;;; 実行部分
(let* (
(text "Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can.")
(text-wo-dot (replace #/\./g "" text))
(arr-text (string-split " " text-wo-dot))
(num '(1 5 6 7 8 9 15 16 19))
)
(display (extract-elements arr-text 0 num))
)
修正 -- 「04. 元素記号」のパフォーマンス改善
上で示したコードはパフォーマンスの問題がありました。
12月27日の投稿時には、お題の解答できればよいという気持ちでしたが気になったので調べました。
member関数が足を引っ張っていました。
memberをJSのArray.includesに変更することで簡単に改善できます。
下はmemberとArray.includesを比較するテストコードです。実行すると感覚的に認識できます。
(print "member関数版 -----")
(let ((num '(1 5 6 7 8 9 15 16 19)))
(let ((i 0))
(while (< i 20)
(if (member i num )
(begin (display i) (display " はtなので1, "))
(begin (display i) (display " はfなので2, ")))
(set! i (+ i 1)))
(newline)
)
)
(print "JS Arraya.includes版 -------")
(let ((num (new Array 1 5 6 7 8 9 15 16 19)))
(let ((i 0))
(while (< i 20)
(if (num.includes i)
(begin (display i) (display " はtなので1, "))
(begin (display i) (display " はfなので2, ")))
(set! i (+ i 1)))
(newline)
)
)
参考
おわりに
ここまで見ていただき「ありがたやま」でございました。
2025年日曜の楽しみ「べらぼう」が終わってしました。朝ドラのマッサンの再放送がはじまりましたね。「ウイスキーがお好きでしょ」という石川さゆりさんの声が頭の中でリフレインしています。
100本ノックは楽しめる問題なので時間を見つけて残りも続けようと思います。
検索してみると、参考リストに挙げるときりがないほどたくさんの人たちがチャレンジしていることにびっくり・納得です。
おわりに2
パフォーマンス改善にはいろいろな手が考えられますが、安直ですがJSコードで対応しました。
LipsはJSがネイティブコードになっているためパフォーマンス性能が懸念されるところですが
そのような場合はJSコードの利用が手っ取り早い対応になります。
LipsはJSコードがシームレスに使えるということがLipsの大きなアドバンテージです。
そういう意味ではLipsはSchemeの一派というよりJSとのハイブリッドLISPと呼んでも良いのではないのでしょうか。JS市場にあるたくさんの拡張ライブラリが使えることでLISPを楽しめる分野が広がると思います。
あと1日で2025年が終わろうとしています。世界が平和でありますように。