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

確か『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 = "ファイルまたはアセンブリ" 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からダ…

Codeforces 110B - B. Lucky String

110B - B. Lucky String calc :: Int -> String calc n = take n $ cycle "abcd" main = do s <- getLine putStrLn $ calc $ read s

Processing, プロジェクト名と同じ名前のクラスは定義できない。

プロジェクト名(.pdeファイル名)と同じ名前のクラスを定義しようとすると、以下のエラーメッセージが表示されました。 The nested type Test cannot hide an enclosing type

Processingで正三角形を描画する

Processingで正三角形を描画しようと思い、コードを書き始めたけど、すぐに手が止まってしまった。triangle()を使って、3点の座標位置を指定すれば三角形を描画できる。だけど、3点の座標位置はどう決めたら良いのだろうか?そもそも正三角形とはどういう形…

primesパッケージをインストール

primesパッケージをインストールします。 cabal install primes http://hackage.haskell.org/package/primes Prelude Data.Numbers.Primes> take 30 primes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113] …

Codeforces 37A - A. Towers

37A - A. Towers import Data.List calc :: [Int] -> (Int, Int) calc xs = (maximum [count x xs | x <- xs], length $ nub xs) where count a xs = sum [1 | x <- xs, x == a] main = do s <- getLine t <- getLine let (x, y) = calc $ map read $ words …

Codeforces 122B - B. Lucky Substring

122B - B. Lucky Substring calc :: String -> Int calc s | n4+n7 == 0 = -1 | otherwise = if n4 >= n7 then 4 else 7 where n4 = sum [1 | c <- s, c == '4'] n7 = sum [1 | c <- s, c == '7'] main = do s <- getLine print $ calc s

Codeforces 122A - A. Lucky Division

122A - A. Lucky Division isLucky :: Int -> Bool isLucky n = show n == filter (\c -> c == '4' || c == '7') (show n) calc :: Int -> String calc n = if null [i | i <- [1..n], isLucky i, n `mod` i == 0] then "NO" else "YES" main = do s <- getL…

第4回 スタートHaskell2に参加してきました

第4回 スタートHaskell2 - [PARTAKE] に参加してきました。 第8章「入出力」@igrep さん IO action putStrLn は文字列を引数にとり、()(空のタプル。unit型ともいう)を結果とする I/O アクションを返す do記法。IO actionをつなぎ合わせる。 >>= 関数の構文…

Codeforces 146B - B. Lucky Mask

146B - B. Lucky Mask整数 a, b が与えられたとき、c のマスクが b と等しく、かつ c > a であるような c を求めよという問題。「c のマスクが b と等しい」とは、整数 c から 4 と 7 以外の数字を取り除いた数が b と等しいという意味。制約: 1 全探索。 ma…

Codeforces 221A - A. Little Elephant and Function

221A - A. Little Elephant and Function calc :: Int -> [Int] calc 1 = [1] calc 2 = [2, 1] calc n = [n, 1] ++ [2..n-1] main = do s <- getLine putStrLn $ unwords $ map show $ calc $ read s

Codeforces 26A - A. Almost Prime

26A - A. Almost Prime素因数分解したときに、素因数の種類が 2 つかどうか求める問題。 import Data.List factorize :: Int -> [Int] factorize 1 = [1] factorize n = fac 2 n where fac p n | n == 1 = [] | n `mod` p == 0 = p : fac p (n `div` p) | ot…

Codeforces 148A - A. Insomnia cure

148A - A. Insomnia cure calc :: Int -> Int -> Int -> Int -> Int -> Int calc k l m n d = d - length [i | i <- [1..d], i `mod` k /= 0, i `mod` l /= 0, i `mod` m /= 0, i `mod` n /= 0] main = do s <- getContents let [k, l, m, n, d] = map read …

Codeforces 3A - A. Shortest path of the king

3A - A. Shortest path of the king import Data.Char parse :: String -> (Int, Int) parse s = (digitToInt (s!!1), ord (s!!0) - ord 'a' + 1) calc :: (Int, Int) -> (Int, Int) -> [String] calc (sr, sc) (dr, dc) | sr == dr && sc == dc = [] | othe…

Codeforces 139A - A. Petr and Book

139A - A. Petr and Book calc :: Int -> [Int] -> Int calc n pages = calc' n (cycle pages) (cycle [1..7]) where calc' n (p:pages) (d:dayWeek) | n <= p = d | otherwise = calc' (n-p) pages dayWeek main = do s <- getLine t <- getLine print $ ca…

Codeforces 146A - A. Lucky Ticket

146A - A. Lucky Ticket import Data.Char isLucky :: String -> Bool isLucky s = all (\c -> c == '4' || c == '7') s calc :: String -> String calc s = if isLucky s && sum hd == sum tl then "YES" else "NO" where xs = map digitToInt s n = length…

Codeforces 219A - A. k-String

219A - A. k-String 文字列をソートする。 同じ文字でグルーピング。 グルーピングした文字列の長さが k の倍数なら、k-string は作れる。そうでなければ k-string は作れない import Data.List calc :: Int -> String -> Maybe String calc k s = if all (\…

Codeforces 50A - A. Domino piling

50A - A. Domino pilingM x N サイズのボードに 2 x 1 サイズのドミノを出来るだけ沢山敷き詰める問題。ボードに配置可能なドミノの個数を出力する。制約: 1 ボードのサイズが偶数であれば、隙間なくドミノを敷き詰められます。なので、まず偶数サイズのボー…

Codeforces 189A - A. Cut Ribbon

189A - A. Cut Ribbon長さ n のリボンある。そのリボンを出来るだけたくさんカットしたい。カットされたリボンの長さは、a, b, cのいずれかでなければならない。最大でいくつのリボンにカットできるか、という問題。制約: 1 DPの問題なのでC++で解きました。…

Codeforces 4A - A. Watermelon

4A - A. Watermelon calc :: Int -> String calc n | n > 2 && even n = "YES" | otherwise = "NO" main = do s <- getLine putStrLn $ calc $ read s

Haskellのdoの中のif式のインデント

Haskellについて調べていたら、do の中の if 式の then と else は if よりもインデントを深くする必要があるという情報があった。手元で試す限り、if, then, elseを揃えても特にエラーにならない。仕様が変わったのだろうか。もしかしたらと思い、-Wall を…

Codeforces 208A - A. Dubstep

208A - A. Dubstep WUBを空白に置き換える 連続する空白をひとつの空白にまとめる 両端の空白を取り除く -- "WUB"を取り除く(代わりに空白をおく) removeWUB :: String -> String removeWUB "" = "" removeWUB ('W':'U':'B':xs) = ' ' : removeWUB xs remove…

Codeforces 1A - A. Theatre Square

1A - A. Theatre Square calc n m a = x * y where x = (n `div` a) + (signum $ n `mod` a) y = (m `div` a) + (signum $ m `mod` a) main = do s <- getLine let [n, m, a] = map read $ words s :: [Integer] print $ calc n m a signumを括弧で囲まない…

Codeforces 216A - A. Tiling with Hexagons

216A - Tiling with Hexagonsb*cを一つの固まりとみなす。aの値が増減するとき、b*cの固まりを取り除いた図形のパターンがどのように変換するかを考えた。b*cの固まりを取り除くと、以下の「へ」の字のラインが見えてくる。 calc a b c = (a-1) * (b + c - 1…

fizzbuzz

http://chaton.practical-scheme.net/gauche/a/2012/08/09#entry-5023d040-7e774 のPythonコードが分かりやすかったので、Haskellで書いてみました。 fizz = cycle ["", "", "fizz"] buzz = cycle ["", "", "", "", "buzz"] fizzbuzz n = [if xy == "" then …

Codeforces 194B - B. Square

194B - B. Square 左下隅からスタートして、はじめて4隅に止まるのは何ステップ目だろうか。 小さいサイズで試してみる。 正方形のサイズを n とすると、 n = 1 のときは、1 ステップ目で四隅にはじめて到達する n = 2 のときは、2 ステップ目 n = 3 のとき…

Codeforces 205A - Little Elephant and Rozdil

205A - Little Elephant and Rozdil以下のように書いたら、calcに渡すリストのサイズが 1 のときにRUNTIME_ERRORとなりました。 import Data.List calc :: [Int] -> String calc xs | length xs > 1 && a == b = "Still Rozdil" | otherwise = case findInde…

Codeforces 214A - A. System of Equations

214A - A. System of Equations全探索。 calc n m = sum [1 | a<-[0..1000], b<-[0..1000], a^2+b==n, a+b^2==m] main = do s <- getLine let xs = map (\x -> read x :: Int) $ words s let (n, m) = (xs!!0, xs!!1) putStrLn $ show $ calc n m

Codeforces 200B - Drinks

200B - Drinks calc xs = (sum xs / fromIntegral (100 * length xs)) * 100 main = do s <- getLine t <- getLine putStrLn $ show $ calc $ map (\x -> read x :: Double) $ words t 型に関する理解があいまいなので、型エラーがなかなか取れませんでした…

Codeforces 199A - A. Hexadecimal's theorem

199A - A. Hexadecimal's theoremフィボナッチ数列を求める関数を作成しましたが、必要ありませんでした。 main = do s <- getLine putStrLn ("0 0 " ++ s)

Codeforcesの問題をHaskellで解いてみる

Haskellで問題を解いてみます。CodeforcesのRatingは1300くらいなので、div2の易しい問題を中心に解いていきたいと思います。

OCamlの練習

4けたの数について、それぞれの位の数字を大きいじゅんにならべた数から小さいじゅんにならべた数をひくという計算を行います。1974 について、この計算を 100 回行った答えを書きなさい。 http://d.hatena.ne.jp/cooldaemon/20120603/1338705617 上の問題…

LuaでPythonのrange関数のようなものを作る

Lua

Pythonのrange関数に似た関数をLuaで作成してみます。 function range(n) local i = 0 return function() if i >= n then return nil end local ret = i i = i + 1 return ret end end function main() for i in range(5) do print(i) end end main() 実行結…

zip関数

Lua

Luaでzip関数を作成してみました。 function zip(xs, ys) local i = 1 return function() x = xs[i] y = ys[i] if x and y then i = i + 1 return x, y else return nil end end end function main() for a, b in zip({1,2}, {3,4,5}) do print(a, b) end en…

Luaのlocal function

Lua

function main() function test() print("test") end test() end main() test() 実行結果です。 test testtestがmainの外側から見えてしまっています。関数内でローカル関数を定義する場合は、local functionを使います。 function main() local function te…

「失敗に学ぶこと」を読んで

Lua

失敗に学ぶことを読んで、Luaだとどうなるか確認してみます。 function main() local t = {} for i = 1, 3 do t[#t + 1] = function() print("call", i) end end for i = 1, #t do t[i]() end end main() 実行結果です。 call 1 call 2 call 3お、ちゃんと値…

テーブルのソート

Lua

function main() t = { "foo", "bar", "baz", "hoge" } print(table.concat(t, " ")) table.sort(t) print(table.concat(t, " ")) table.sort(t, function(a, b) return a > b end) print(table.concat(t, " ")) end main() 実行結果です。 foo bar baz hoge…

Juliaのmap関数

map関数で、文字列を数値のリストに変換しようと思ったのだけどエラー(type error)になる。 型変換が入るとダメなのだろうか。 ~ $ julia _ _ _ _(_)_ | (_) | (_) (_) | _ _ _| |_ __ _ | A fresh approach to technical computing | | | | | | |/ _` | | |…