Round 1C (Google Code Jam 2009)

日記 Haskell

ヘボヘボだった，1Bだが，なんとか通過していた．練習のために，1Cもやってみた．時間制限とかプレッシャーがないぶん，気楽で，まぁまぁ良い感じだった（たぶん，問題も簡単になっている）．（前回と同じテンプレートを使用しています．） A そのまま．た…

2009-09-13

Round 1B (Google Code Jam 2009)

日記 Haskell

まぁ，前回同様，予想通り，ダメダメだったわけだが．共通のテンプレート（下）を使用した． import Data.List import Data.Maybe import Data.Ord import Data.Char import Data.Function import Data.Map (Map) import qualified Data.Map as M import Dat…

2009-09-12

Problem 255 めも

日記 Memo Haskell C++ Project Euler

Problem 255 - Project Euler解いた．前2問に比べると簡単だと思う（もう内容忘れかけているが）．はじめにHaskellで解いたら，実行時間は3分ぐらいだった．再帰を使おうとしたら，stack space overflow． seq入れてみたり，!入れてみたりして，stack space…

2009-09-08

速いnubが欲しい．（Haskell)

Haskell 日記

The Haskell 98 Library Report: List Utilities によると， nub :: (Eq a) => [a] -> [a] nub [] = [] nub (x:xs) = x : nub (filter (\y -> not (x == y)) xs) なので，実はnubはO(n^2). Eq だけ，だから仕方ないのかもしれないが．しかし， nub :: (Ord …

2009-09-05

Problem 254 めも

Haskell Project Euler

取り敢えず，解いた．しかし，少し遅い．約20秒 (Core 2 Duo E8500).もうすこし工夫して下限を求めるか，探索方法を工夫するか，の二択なのか？追記 #1 ad hoc な工夫をして，約3秒になった．しかし，もう少し綺麗な改良の方法はないのか？追記 #2 C++…

2009-09-04

Qualification Round 感想

Haskell 日記

総じて，ダメダメな出来だったが，反省会の意味も込め感想を書いておく． Qualification なだけあって，どの問題も簡単だったが，アルゴリズムをコードにするのに時間がかかった．あと入出力もメンドウ． A - Alien Language すべての問題についてあてはま…

2009-08-29

Problem 253 めも

Haskell Project Euler Memo

Problem 253 - Project Euler 取り敢えず，解いたが，フォーラムのシンプルかつ高速な解法が理解できない… それにしてもMemoTrieは強力だ．お手軽，メモ化．ほとんどコードを変えることなくメモ化できる．やはり，高階関数は便利． # import MemoTrie とし…

2009-08-24

Practice

Haskell Memo

去年のやつ． Dashboard - Qualification Round 2008 - Google Code JamBの問題簡単な問題だと思う．Qualificationなんちゃらだし．各駅での列車の出発，到着（正確には再び出発可能な状態になる）をイベントと思い，その時系列順のリストをつくる．本質的…

2009-08-02

メモ化 @ Haskell

日記 Haskell

MemoTrieのソースを読んで，だいたい理解した．どうやら，内部では Tree を作って，その中に関数の評価値を保持するみたい．まず，全ての入力に対応する出力を Tree の中に保存する．しかし，実際に計算はしない．遅延評価を利用して，必要になったときだ…

2009-07-31

Haskellの簡約の実装とMemoTrieの秘密？

日記 Haskell

関数型言語では，グラフ簡約と最外簡約を行うと効率が良くなるらしい．っていうのを http://www.amazon.co.jp/%E9%96%A2%E6%95%B0%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0-R-%E3%83%90%E3%83%BC%E3%83%89/dp/4764901811 で読んだ…

2009-07-29

MemoTrie? (関数の自動メモ化@Haskell)

日記 Haskell

HaskellにはMemoTireというパッケージがあります．どうやら，関数のメモ化を自動でやってくれるみたい． http://hackage.haskell.org/cgi-bin/hackage-scripts/package/MemoTrie http://hackage.haskell.org/packages/archive/MemoTrie/0.4.5/doc/html/Data…

2009-07-27

LU分解

日記 Haskell

LU分解@Haskell 遅延評価って便利．自分で評価の順番を明示的に与えなくても，よきにはからってくれる． import Data.Array type Matrix = Array (Int, Int) Double -- assumption: u!(i,i) /= 0 lu :: Matrix -> (Matrix, Matrix) lu a = (l, u) where b =…

2009-07-24

ラングトンのアリ

日記 Haskell

平面が格子状に構成され、各マスが白または黒で塗られる。ここで、1つのマスを「アリ」とする。アリは各ステップで上下左右のいずれかのマスに移動することができる。アリは以下の規則に従って移動する。 * 黒いマスにアリがいた場合、90°右に方向転換し、そ…

2009-07-22

GMAP

Memo Haskell

import Data.List -- greedy algorithm next :: Integral a => a ->[a] -> [a] next c ms = bs ++ 1: genericReplicate n 0 where (as, bs) = genericSplitAt c ms n = c - sum as sequences :: Integral a => a -> a -> [[a]] sequences c n | c > n = [] |…

2009-07-19

cabal-install をインストール

Memo Haskell 日記

何度もcabal-installをインストールしている気がするのでメモ．追記 id:nobsunさんのコメントから； cabal-installを展開した中に bootstrap があります．これを実行すれば必要なパッケージをインストールしてくれるようです．（試していませんが）以下 R…

2009-07-17

APR素数判定

日記 Haskell

多分当っている．コード長いです． Miller Rabin はやはり非常にシンプル．それに比べ，APRは… まぁ，実装がヘタなんだよと，言われればそれまでだが．しかし，綺麗なコードがあれば見てみたいが，すくなくとも簡単にはwebでは見つからなかった． 100桁と…

2009-07-16

連立合同方程式

日記 Haskell

ちょっと，連立合同方程式を解く必要がでてきたので，実装してみた．ここで，invMod n p = n^(-1) (mod p)． -- Input: 互いに素な整数 m1,m2,...,mn, 整数 a1,a2,...,an -- Output: 連立合同方程式の解 x in Zm s.t. x = ai (mod mi) congruence :: (Integ…

2009-07-13

いまさらながら，素数判定 @ Haskell

日記 Haskell

とりあえず，試し割りとMiller-Rabin． Miller-Rabinはアルゴリズム自体は簡単．なんで，こんなコードがほぼ正しい答えを返すか若干不思議である（乱択アルゴリズムは，相当単純なのに，まぁまぁなものが多い）．決定性アルゴリズムも実装したいが… modul…

2009-07-07

Problem 252

Haskell Project Euler

252 Convex Holes Problem 252 - Project Euler 計算幾何の問題．二次元平面上に点集合が与えられる．最大空凸包とでもいうのでしょうか？凸包であって，内部に他の点を含まないもののうちの最大面積を求める問題．さて，どこから手を付ければ良いのや…

2009-07-03

Problem 250

Project Euler Haskell C++

250 250250 Problem 250 - Project Euler 前の問題（249）と似ているが…

2009-07-03

Problem 249

Project Euler Haskell C++

249 Prime Subset Sums Problem 249 - Project Euler 部分和問題はNP困難で，難しそうですが…

2009-07-03

Problem 248

Project Euler Haskell

248 Numbers for which Euler’s totient function equals 13!Problem 248 - Project Eulerphi(n) = 13 ! となる n を探す問題．一見，探索範囲が広そうに見えるが…

2009-06-30

Problem 247

Project Euler Haskell

247 Squares under a hyperbola Problem 247 - Project Euler x=1, y=0, y=1/x の中に次々と最大の正方形を詰めていく問題．一見，複雑だが…一つ，正方形を詰めると，残りの領域の分割数が丁度一つ増えることに着目．再帰関数を構成した． haskellのコード…

2009-06-30

Flymake-mode for Haskell (Emacs) without perl script

Haskell Memo

前の Flymake-mode for Haskell (Emacs) - 落書き、時々落学ではperlスクリプトが必要だった．しかし，それがなくても，大丈夫であることが分かった．参考 EmacsWiki: Flymake Haskell 環境 Ubuntu 9.04 emacs 23.0.91.1 flymake 0.3 ghc 6.8.2 .emacsの…