Archive for the ‘explode’ Tag

projecteuler22

projecteuler22

 projecteuler問題22 は、names.txt にある名前をアルファベット順に並べ、全ての名前の順位と名前のアルファベットの値和と積を求め、その総量を求める問題。アルファベットの値は A, B, C,… が 1, 2, 3,… に相当。 
 url にあるデータは get-url で取り出し、sort でソートすれば、後は計算するだけ。繰り返しには dolist でも使いましょうか。文字列の分解には explode が使えます。
 さて、コードは、

(silent)
(setq names (replace "," (parse (get-url "https://projecteuler.net/project/resources/p022_names.txt"))))
(sort names)
(let (res 0)
  (dolist (n names)
    (++ res (* (+ $idx 1) (apply + (map (fn (x) (- x 0x40)) (map char (explode n)))))))
  (println res))

 こんな感じ。これを実行すれば、

871198282

 という答えが得られます。
 silent 文を外せば、names.txt にある名前がすべて表示されます。お好みでどうぞ。
 以上、如何でしょうか?

広告

projecteuler8...または、newLISP の文字列

 今回の projecteuler は、順当に問題 8 だけ。問題で指定された 1000 個の数字から連続する 5 個の数字を取り出し、その積を計算し、最大値を求めるもの。

(let (str (replace {\D} [text]
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
[/text] "" 0))
  (let (n (length str) 
        nums (map int (explode str))
        res 0)
    (for (i 1 (- n 5))
      (let (x (apply * (i 5 nums)))
        (when  (> x res)
          (swap res x) (println (i 5 nums))
        )))
  res)
)

 与えられた 1000 個の数字は 20 桁 20 行の文字列。
 newLISP の文字列には、三種類の形式があります。よく使われるのが、""(ダブル・クォート)で囲むもの。文字列の中に (バックスラッシュ、日本語環境下では ¥ 記号)によるエスケープ・シーケンスが使えます。二つ目は、{}(波括弧)で囲むもの。この中では、エスケープ・シーケンスは使えませんが、そのおかげでエスケープ・シーケンス開始文字のかぶる正規表現の書式指定を書く時に便利です。もう一つが、2048 文字を超える文字列には必須の [text][/text] のタグで囲むもの。
 ということで、今回は三種類とも使ってみました。
 与えられた数値の文字列を [text][/text] のタグで囲み、改行を除いて一連の数列にするために、組込関数 replace を使います。replace の検索文字には正規表現が使えるので、数字以外を表す \D{}(波括弧)で囲んでいます。数字以外を削除するために、置換文字を ""(空文字列)にしています。
 文字列の説明はこれくらいにして、スクリプトの動作を。と言っても、説明するまでもないかもしれません(笑)。
 一連の数列の文字列を組込関数 explode を使って一個ずつの数値文字にばらし、組込関数 mapint で数値リストに変換して、変数 nums に入れておきます。
 後は、数値リストから 五個ずつ取り出し、その積を計算し、最大値を入れてある変数 res と比較して大きければ、組込関数 swap を使って値を交換します。この場合、組込関数 setq でも十分ですが、swap を紹介しておきたかったので(笑)。
 when 内の println 文は答えになる数字の組みを表示するためのもので、問題には必要のないコードです。一行コメントの ;(セミコロン)をつけて、外しておいてもいいでしょう。
 さて、このスクリプト動作は、

(3 1 6 7 1)
(1 6 7 1 7)
(6 7 1 7 6)
(9 6 7 4 4)
(4 9 6 9 8)
(9 4 7 8 8)
(7 6 6 8 9)
(9 9 8 7 9)
40824
> 

 こんな感じ。答えは 9✕9✕8✕7✕940824 となります。

 以上、如何でしょうか?

newLISP で On Lisp する...第4章(その5)

(この blog は、“short short story または 晴耕雨読な日々”からの引越してきたもの。スクリプトは、newLISP V10.2.1 以降で動作するように書き直しています。)
defun 等の newLISP組込関数に無い関数は、特に断らない限り、newlisp-utility.lsp に定義してあります。

 第4章 ユーティリティ関数 も、その5まで来ましたが、今回でこの章は、終了です。
 最初に、入出力入出力関数 を newLISP で書くとこうなります。

(defun readlist ((in 0))
  (read-expr (string "(" (read-line in) ")")))

(defun prompt ()
  (print (apply format (args)))
  (read-expr (read-line)))

(defun break-loop (f quit)
  (print (format "Entering break-loop.\n"))
  (catch 
    (while true
      (let ((in (apply prompt (args))))
        (if (quit in)
            (throw in)
          (print (format "%s\n" (string (f in)))))))))

 まずは、関数readlist から。newLISP には、read-from-string はありませんが、組込関数read-expr がそれに相当します。read-from-stringのような第2値を返すことは無いので、values は使う必要はありません。文字列を生成している concatenate ‘string にとって代わるのは、組込関数string です。そして、組込関数read-line は、Common Listの同関数を同等の機能ですが、引数オプションは、device番号だけです。device番号 0 で、標準入出力になります。
 動作はこうです。

> (readlist)
Call me "Ed"
(Call me "Ed")

 関数prompt は、標準入出力に特化して記述しています。
使われている format は、newLISP にもありますが、出力機能はありません。
それで、組込関数print で出力させます。
そして、read は newLISP にもありますが、Common Lisp の read というよりは、C言語の read に近い関数です。そのため、関数readlist と同様、組込関数read-lineread-expr で代用します。
 動作例です。

> (prompt "Enter a number between %d and %d.\n>> " 1 10)
Enter a number between 1 and 10.
>> 3
3

 format の書式は、これも C言語の printf の書式とほぼ同等です。C言語に慣れている私には、うれしい仕様です。
そして、入出力 の最後は、関数break-loop 。newLISP には、loop がありませんので、組込while + true で無限ループとし、同様に newLISP には無い return は、組込catchthrow で対応しています。
 では、動作を。

> (break-loop eval (fn (x) (= x 'quit)) ">> ")
Entering break-loop.
>> (+ 2 3)
5
>> quit
quit

 終了条件のシンボルに :q を使っていないのは、訳があります。 は、newLISP では、コンテキストとシンボルの区切りに使われる演算子です。つまり、:q というシンボルは、使えないということ。

 次は、シンボルと文字列 です。シンボルと文字列に作用する関数 は、以下のようになります。

(define mkstr string)

(defun symb ()
  (sym (apply mkstr (args))))

(defun reread()
  (read-expr (apply mkstr (args))))

(defun explode-s (s)
  (map sym (explode (string s))))

 まずは、関数mkstr。newLISP には、with-output-to-string がありません。それでも、本文風に書くなら、

(defun mkstr ()
  (let (res "")
    (dolist (a (args))
       (push (string a) res -1))
  res))

 という具合です。もともと、newLISP では、文字列変換関数は、特定の数値文字列変換関数以外には、string しかないのです。そして、組込関数string の機能は、まさに、関数mkstr そのものなのです。動作はというと。

> (define pi (mul 2 (acos 0)))
3.141592654
> (mkstr pi " pieces of " 'pi)
"3.141592654 pieces of pi"

 newLISP には、円周率を返す pi が無いので、組込の逆余弦関数acosを使って定義しています。
次の関数symb で使われている、intern に相当するのが、組込関数sym 。values と #’ はありませんが、本文そのままといったところ。動作はというと、

> (symb 'ar "Madi" "L" "L" 0)
arMadiLL0
> (symbol? (symb 'ar "Madi" "L" "L" 0))
true

 || で囲まれたりしませんけどね。ちなみに、xyzzy でも || は、付きません。clisp は、もちろん付きますよ。
また、newLISP には、データ型に、文字列はありますが、文字はありません。組込関数char で引数に数字を与えて返るのも一文字の文字列です。
 そして、関数reread です。やっていることは、関数prompt で標準入力から取り込んでいたオブジェクトを引数で与えているだけです。 動作的には、これでよいはずですが。

> (reread (+ 2 3))
5
> (reread 'a)
a

 xyzzy でも、Common Lispでも同じ動作でした。もっとも、Common Lispでは、a は A になりますけど。
シンボルと文字列 の最後は、関数explode です。newLISPには、組込explode がありますので、explode-s と名前を変えてあります。組込explode が文字列を一文字ずつに分けたリストを返してくれますので、本文の様に手の込んだことをしなくて済みます(笑)。
 動作も、

> (explode-s 'bomb)
(b o m b)
> (map symbol? (explode-s 'bomb))
(true true true true)

といった具合です。

 この章の最後、密度 に書かれている内容は、別に Lisp に限ったことではありません。“ボトムアップ式のプログラムは概念の密度が高い” というのは、良いユーティリティ(または、ライブラリ)があると、概念の密度が高いプログラムが書けるということでもあります。ニワトリが先か、タマゴが先か。ちにみに、“概念の密度が高いプログラム” は “アルゴリズムが見通せるプログラム” だと思いますが、如何でしょうか?

 さて、第4章 ユーティリティ関数 のまとめです。

  • newLISP の組込関数last は、CommonLispの last とは違い、last1 と同等です。
  • newLISP には nthcdr と subseq はないが、どちらも、インデクシングで実現できます。
  • newLISP では、eq、eql、equal の区別が無く。全て、= で対応します。
  • newLISP の組込関数member は、CommonLisp と違って、判定条件の指定ができません。
  • newLISP 演算子 +、-、*、/、% は、整数専用です。しかし、実数用に、再定義する方法が用意されています。
  • newLISP には、制御文loop はありません。その代わり、while、until、for 等が使えます。
  • newLISP では、apply と map の組合せ使用方法が、Common Lisp と異なります。
  • newLISP の組込関数format には、出力機能はありません。また、その書式は、C言語の printf の書式似です。
  • newLISP のデータ型に、文字(charcter)は、ありません。全て文字列で対応します。

以上、如何でしょうか?