数値文字参照を文字に変換するPythonスクリプト
import re def conv(s): cs = [] for e in re.findall("&#x([0-9a-fA-F]+);", s): cs.append(chr(int(e, 16))) return "".join(cs) def main(): s = "ファイルまたはアセンブリ" print(conv(s)) # ファイルまたはアセンブリ if __name__ == "__main__": main()
リンク
自然数から平方数を取り除いた数列の N 番目を求める
A000037 - OEIS の式を使って求めます。
; https://oeis.org/A000037 (define (f n) (+ n (exact-integer-sqrt (+ n (exact-integer-sqrt n)))))
実行結果です。
% gosh -l ./not-square-numbers.scm gosh> (map f (iota 100 1)) (2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27 28 29 30 31 32 33 34 35 37 38 39 40 41 42 43 44 45 46 47 48 50 51 52 53 54 55 56 57 58 59 60 61 62 63 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 101 102 103 104 105 106 107 108 109 110)
バットとボールの問題を SageMath で解く
問題:バットとボールはセットで1ドル10セントします。バットはボールより1ドル高いです。ボールはいくらですか?
$ sage ┌────────────────────────────────────────────────────────────────────┐ │ SageMath version 7.2, Release Date: 2016-05-15 │ │ Type "notebook()" for the browser-based notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ sage: var('bat ball') (bat, ball) sage: f = [bat + ball == 110, bat == ball + 100] sage: solve(f, bat, ball) [[bat == 105, ball == 5]]
1158と四則演算で10を作る問題
1, 1, 5, 8 と四則演算で10を作る問題をやってみました。
Gaucheで小町算にチャレンジ
Makoto HiroiさんのMemorandum(2013年1月5日)で小町算の問題が紹介されていました。
●パズルでプログラミング パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。 たとえば、123456789 とか 321654987 のような数字です。「小町算」というものもあり、 たとえば 123 + 456 + 789 とか 321 * 654 + 987 のようなものです。 [問題] 小町算 1 から 9 までの数字を順番に並べ、間に + と - を補って三桁の値 (100 - 999) になる式を作ることにします。 100 になる式の一例を示します。 例:1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100 100 になる式は全部で 11 通りあります。それでは問題です。 1. 式の総数が最大になる値をすべて求めてください。 2. 解のない値で最小のものを求めてください。 3. 解のある値で最大のものを求めてください。
Gauche(Scheme)でチャレンジしてみたいと思います。
はじめに、100になる式は全部で11通りあるとのことですので、それを確かめるプログラムを作成します。
(use util.match) (define (komachi) (let loop ((expr '(1)) ; 計算式 (rest '(2 3 4 5 6 7 8 9))) ; 残りの数字 (cond ((null? rest) (when (and (integer? (car expr)) (= 100 (eval (reverse expr)))) (print (reverse expr)))) ((integer? (car expr)) (loop (cons (+ (* 10 (car expr)) (car rest)) (cdr expr)) (cdr rest)) (loop (cons '+ expr) rest) (loop (cons '- expr) rest)) (else (loop (cons (car rest) expr) (cdr rest)))))) ;;; 式を評価 (define (eval expr) (let loop ((expr (cdr expr)) (acc (car expr))) (match expr (() acc) (('+ x . z) (loop z (+ acc x))) (('- x . z) (loop z (- acc x))))))
実行結果です。
gosh> (komachi) (123 + 45 - 67 + 8 - 9) (123 + 4 - 5 + 67 - 89) (123 - 45 - 67 + 89) (123 - 4 - 5 - 6 - 7 + 8 - 9) (12 + 3 + 4 + 5 - 6 - 7 + 89) (12 + 3 - 4 + 5 + 67 + 8 + 9) (12 - 3 - 4 + 5 - 6 + 7 + 89) (1 + 23 - 4 + 56 + 7 + 8 + 9) (1 + 23 - 4 + 5 + 6 + 78 - 9) (1 + 2 + 34 - 5 + 67 - 8 + 9) (1 + 2 + 3 - 4 + 5 + 6 + 78 + 9) #<undef>
100になる式は全部で11通りありました。上のプログラムを元に以下の3つの問題を解いていきます。
- 式の総数が最大になる値をすべて求めてください。
- 解のない値で最小のものを求めてください。
- 解のある値で最大のものを求めてください。
(use util.match) (use gauche.collection) (use srfi-1) ; lset-difference (define (komachi) (let ((ht (make-hash-table))) (let loop ((expr '(1)) ; 計算式 (rest '(2 3 4 5 6 7 8 9))) ; 残りの数字 (cond ((null? rest) (when (integer? (car expr)) (let ((x (eval (reverse expr)))) (when (<= 100 x 999) (hash-table-put! ht x (+ 1 (hash-table-get ht x 0))))))) ((integer? (car expr)) (loop (cons (+ (* 10 (car expr)) (car rest)) (cdr expr)) (cdr rest)) (loop (cons '+ expr) rest) (loop (cons '- expr) rest)) (else (loop (cons (car rest) expr) (cdr rest))))) ht)) ;;; 式を評価 (define (eval expr) (let loop ((expr (cdr expr)) (acc (car expr))) (match expr (() acc) (('+ x . z) (loop z (+ acc x))) (('- x . z) (loop z (- acc x)))))) (define (solve1) ; 問題1 (let* ((alist (hash-table->alist (komachi))) (nmax (cdr (find-max alist :key cdr)))) (map car (filter (^x (= nmax (cdr x))) alist)))) (define (solve2) ; 問題2 (let ((alist (hash-table->alist (komachi)))) (find-min (lset-difference = (iota 900 100) (map car alist))))) (define (solve3) ; 問題3 (let ((alist (hash-table->alist (komachi)))) (car (find-max alist :key car))))
問題 1 の「全て求める」というのが結構くせ者ですね……。上のプログラムでは、まず最大値を見つけてから、再度その値を持つ要素を検索しています。1度きりの探索で答えを出せたら良いのですがうまく書けませんでした。
問題 2 は、存在しない値を求めるのにlset-difference
を使っています。最小値だけでなく、存在しない値を全て求めてしまっているのはあまり良くないかも知れません。
問題 3 は、単純にfind-max
で最も大きい値を求めています。
実行結果です。
gosh> (solve1) (117 108 126) gosh> (solve2) 160 gosh> (solve3) 972
参考
- 作者: Kahuaプロジェクト,川合史朗
- 出版社/メーカー: オライリージャパン
- 発売日: 2008/03/14
- メディア: 大型本
- 購入: 20人 クリック: 707回
- この商品を含むブログ (273件) を見る
追記
- 2013年1月12日のMemorandumに解答編が掲載されていました(2013-01-14)。
RubyのBinDataが便利!
RubyのBinDataが便利!バイナリ構造が宣言的に書ける。Javaクラスファイルのconstant_poolを解析してppしただけのプログラムだが2-30分でできてしまった。これにはほとんど感動してしまった。gist.github.com/3408774#binsummer
— Shiina san!さん (@shinaisan) 8月 20, 2012
これはすごい。。忘れないようにメモ。Rubyだとこんな書き方が出来るんですね。
深さ優先探索によるトポロジカルソート
トポロジカルソートのアルゴリズムは、『プログラマのうちあけ話―続・プログラム設計の着想』を読んで学びました。この本では次の方法により、トポロジカルソートします。
入力辺がないノードをキュー q に入れる while (q に要素が含まれる): node = q.pop() print(node) nodeの出力辺を全て削除する 入力辺がないノードをキュー q に入れる(ただし、printしたnodeは除く)
トポロジカルソート - Wikipedia をみますと、上記アルゴリズムの他に、深さ優先探索による方法でトポロジカルソートを行うアルゴリズムが書かれてあります。
深さ優先探索によるトポロジカルソートのプログラムを Lua で書いてみました。
入力ファイルとして、Problem 79 - Project Eulerのkeylog.txtを使います。
tsort コマンド
tsort (Unix) - Wikipedia, the free encyclopedia というトポロジカルソートを行うコマンドがあるようです。この tsort コマンドをつかって、トポロジカルソートしてみました。
% awk '{ split($1, a, ""); print a[1], a[2], a[2], a[3] }' < keylog.txt | tsort 7 3 1 6 2 8 9 0