ループ変数をクロージャで包む

Common Lisp や ISLISP の do がループ変数を破壊的変更するのに対して Scheme では新しく環境を生成するのを知った時には「似て非なるものだ……」と思いました。 https://t.co/xKLGTMEzuA— 齊藤敦志 (@SaitoAtsushi) 2020年10月30日 Gauche で確認コードを書…

ハミング数

Gauche の data.heap モジュール を使ってハミング数を求めてみます。(効率は悪いです) (use data.heap) (use gauche.generator) (define (hamming n) (define (gen) (generate (^[yield] (let1 heap (make-binary-heap) (binary-heap-push! heap 1) (let lo…

ソート後の移動先インデックスを求める

配列をソートしたときの移動先インデックスを知りたい場合があります。 D 言語だと topNIndex 関数で知ることが出来ます。 import std; void main() { auto a = [99, 1, 100, 2, 150]; auto id = new int[a.length]; a.topNIndex(id, Yes.sortOutput); forea…

競プロ(AtCoder)の問題を D 言語で解くための Tips

これは Competitive Programming (2) Advent Calendar 2018 の 12 日目の記事です。 競プロの問題を D 言語で解くための Tips を集めました。 オンラインジャッジサイトによって、D 言語のコンパイラのバージョンは異なりますので、この記事では、 AtCoder …

べき乗演算子

べき乗演算子が定義されている言語について調べてみました。 D int x = 2 ^^ 10; //=> 1024 Haskell Prelude> 2 ^ 10 1024 JavaScript > 2 ** 10 1024 Julia julia> 2 ^ 10 1024 Mathematica In[1]:= 2 ^ 10 Out[1]= 1024 Python >>> 2 ** 10 1024 Ruby [1] …

オイラーのトーシェント関数

オイラーのトーシェント関数は、以下の形で表すことができます(正確な定義は オイラーのφ関数 - Wikipedia にあります)。 この式の括弧内の分母を揃えます。 プログラムで値を得るときは、この式を元に以下のように計算していました。 import std.experiment…

D言語: recurrence の練習

import std.experimental.all; void main() { // 初項 1, 公差 2 auto a = recurrence!((a, n) => a[n-1] + 2)(1); writeln(a.take(10)); //=> [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] // 初項 3, 公比 2 auto b = recurrence!((a, n) => a[n-1] * 2)(3); writ…

D言語: foreach の変数展開の仕組みが分からない

import std.experimental.all; void main() { foreach (a; [10, 20, 30]) writeln(a); } と書くと、配列の中身が foreach の変数 a に代入されて以下のように出力されます。 10 20 30 次に foreach の変数をひとつ追加します。 すると、その追加した変数には…

D言語: 2, 3, 5, 7... のシーケンスを作る

D 言語で、2, 3, 5, 7... のシーケンスを作る方法です。 素数をふるいにかけるとき 2 で割り切れるか 3, 5, 7... で割り切れるか を試しますが、これらを分離せずにひとつのシーケンスとして扱えると便利ですね。 import std.experimental.all; void main() …

隣り合う要素でグループ分け

0 と 1 からなる配列があります。 たとえば [0, 1, 1, 0, 0, 1, 0, 0] の配列を [[0], [1, 1], [0, 0], [1], [0, 0]] のように 0 と 1 とでグループ分けする関数が必要になったので作ってみました。 def group(xs) return [] if xs.empty? g = [] buf = [xs[…

Ruby で三角数の無限シーケンスを作る

まずは Enumerator で三角数を具体的に生成してみよう。 def triangles Enumerator.new do |y| sum = 0 1.step {|i| sum += i y << sum } end end p triangles.take(10) #=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55] 三角数を生成するところをもっと抽象化し…

SageMath でフィボナッチ数の練習

sage: def fib(n): ....: if n == 0: return 0 ....: m = matrix([[1, 1], [1, 0]]) ** n ....: return m[0, 1] ....: sage: [fib(i) for i in range(20)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] 参考 行列…

Python で多次元リストを作る

Python で 2 次元リストを作るには、リスト内包表記を使って以下のように書くことが出来ます。 >>> rows, cols = 2, 3 >>> [[0] * cols for _ in range(rows)] [[0, 0, 0], [0, 0, 0]] 2 次元まではいいのですが、3 次元以上になるとリスト内包表記で書くの…

curry, uncurry

Prelude> :t curry curry :: ((a, b) -> c) -> a -> b -> c Prelude> :t uncurry uncurry :: (a -> b -> c) -> (a, b) -> c Prelude> add (a, b) = a + b Prelude> curry add 2 3 5 Prelude> mul a b = a * b Prelude> uncurry mul (2, 3) 6 curry はタプル…

AtCoder など競プロで学んだこと

これはCompetitive Programming Advent Calendar 2017の 17 日目の記事です。 AtCoder のレートは緑です。最近ようやく水色に届きました。そんな筆者ですが、AtCoder など競プロで学んだ内容をいくつか紹介したいと思います。 long に収まらない整数の余りを…

「カウント・スリー」問題を解いてみました

桁 DP + 二分探索で解きました。 リンク togetter.com

VSCode で Markdown のみ行末の空白を削除しない

settings.json で以下のように設定します。 すると、Markdown のみ行末の空白が削除されなくなります。 "files.trimTrailingWhitespace": true, "[markdown]": { "files.trimTrailingWhitespace": false } 参考 https://github.com/editorconfig/editorconfi…

再帰に対する考え方を教えてくれた練習問題

確か『LISP I』だったと思うけど、次のような練習問題があった。 2 つの引数をとり、その 2 つの値の合計を返す関数を書け。ただし + は使わずに 1+ と 1- を使って。 なお、2 つの引数は正の整数と仮定してよい。 答えをみたら「なあんだ」と思えるが、その…

数値文字参照を文字に変換する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 = "&#x30D5;&#x30A1;&#x30A4;&#x30EB;&#x307E;&#x305F;&#x306F;&#x30A2;&#x30BB;&#x30F3;&#x30D6;&#x30EA;" p…

自然数から平方数を取り除いた数列の 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 1…

バットとボールの問題を SageMath で解く

問題:バットとボールはセットで1ドル10セントします。バットはボールより1ドル高いです。ボールはいくらですか? http://karapaia.com/archives/52047106.html $ sage ┌────────────────────────────────────────────────────────────────────┐ │ SageMath …

1158と四則演算で10を作る問題

1, 1, 5, 8 と四則演算で10を作る問題をやってみました。

Gaucheで小町算にチャレンジ

Makoto HiroiさんのMemorandum(2013年1月5日)で小町算の問題が紹介されていました。 M.Hiroi's Home Page / Memorandum ●パズルでプログラミング パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。 たとえば、1234…

RubyのBinDataが便利!

RubyのBinDataが便利!バイナリ構造が宣言的に書ける。Javaクラスファイルのconstant_poolを解析してppしただけのプログラムだが2-30分でできてしまった。これにはほとんど感動してしまった。gist.github.com/3408774#binsummer— Shiina san!さん (@shinaisa…

深さ優先探索によるトポロジカルソート

Lua

トポロジカルソートのアルゴリズムは、『プログラマのうちあけ話―続・プログラム設計の着想』を読んで学びました。この本では次の方法により、トポロジカルソートします。 入力辺がないノードをキュー q に入れる while (q に要素が含まれる): node = q.pop(…

池袋バイナリ勉強会(9)に参加しました

12月2日(日)に開催された池袋バイナリ勉強会(9)に参加しました。PDP-11のバイナリ解析に取り組んでいます。a.outの逆アセンブル、およびインタプリタの作成に取り組んでいます。 目標: hello.c を実行するインタプリタの作成 % cat hello.c main() { write(1…

SRM563 div2 easy FoxAndHandleEasy

SRM

文字列Sがあり、その文字列Sの任意の位置に同じ文字列Sを挿入する。そうして作られる文字列をSのexpansionと呼ぶとする。文字列S, Tが与えられたとき、TがSのexpansionかどうかを求める問題。 コンテスト中に書いたコードは以下。std::stringの文字列の削除…

池袋バイナリ勉強会(8)に参加しました

11月25日(日)に開催された池袋バイナリ勉強会(8)に参加しました。PDP-11のバイナリ解析に取り組んでいます。a.outを逆アセンブルする自作スクリプトを作成しながら、平行してそれを実行するインタプリタを作ろうとしている段階です。 逆アセンブラの作成 以…

池袋バイナリ勉強会(5)に参加しました

10月21日(日)に開催された池袋バイナリ勉強会(5)に参加しました。PDP-11の実行ファイル(a.out形式)の解析に取り組んでいます。 以下、取り組んだ内容のメモです(書かれている内容には間違いがあるかも知れません)。 前回までの復習 前回までの勉強会で学んだ…

池袋バイナリ勉強会(2)に参加してきました

9月23日(日)に池袋バイナリ勉強会(2)に参加してきました。 MonoDevelopでHello world! MonoDevelopとGTK#を用いて、ボタンをクリックしたらメッセージダイアログを表示するGUIプログラムを書きました。 MonoDevelopをインストールします。MonoDevelopからダ…