imHo RSSフィード

2007-06-15

素因数分解を求める golf

haskellのプログラムの Exercise として、素因数分解はどうだろうと思って作ってみた。分かりにくいエラーメッセージと格闘して、ようやく書けた。

-- 素因数分解

import System
import List

-- 約数
factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

-- 素因数分解
factorization :: Int -> [Int]
factorization 1 = []
factorization x = v : factorization (x `div` v)
	where
		v = (factors x) !! 1

-- 文字列の連結 間に与えられたセパレータで結合
join :: [a] -> [[a]] -> [a]
join sep (x:[]) = x
join sep (x:xs) = x ++ sep ++ join sep xs

-- エントリ
main = do cs <- getContents
          putStrLn $ unlines $ map (\str -> makeFactorization $ read str) $ lines cs
	where
		makeFactorization x = (\xs -> show x ++ " = " ++ xs) $ join " * " $ map (\xs -> dispFormat (head xs) (length xs)) $ group $ factorization x

		-- 表示用に "x^n" もしくは "x" という文字列に変換
		dispFormat x 1 = show x
		dispFormat x n = show x ++ "^" ++ show n

せっかくだから、anarchy golfに、適当な説明文を書いて出してみた。それが昨日の深夜 25:42。「もう夜も遅いし」と寝て、起きて見てみるとすでに登録されてる!

Rubyで77バイト、さらにUnlambdaとかいう難読言語で、ってこいつら人間じゃないだろ…。

皆さんチャレンジお願いします。

b2oxb2ox 2007/06/15 22:29 mokeheheさんのをベースに短縮してみました。

import List
f 1=[]
f n=let(v:_)=[x|x<-[2..n],n`mod`x<1]in v:f(n`div`v)
s=show
q[i]=s i
q x=s(head x)++’^’:s(length x)
m@main=do x<-getLine;putStrLn$x++” = ”++(concat.intersperse” * ”.map q.group.f.read)x;m

mokehehemokehehe 2007/06/16 10:10 m@という書き方ははじめて知りました。getLineでこうやって処理するのかぁ。
intersperseという関数を知らなくて自作してしまったのですが、「入門Haskell」にも載ってるんですね。
あと、リストの要素がひとつの時のマッチングとか、非常に参考になりました!

mokehehemokehehe 2007/06/16 10:10 コメント欄での半角のクォーテーションのテスト:
’シングルクォート’
”ダブルクォート”
<>&?=

mokehehemokehehe 2007/06/16 10:12 コメント欄に入力した半角クォートは勝手に全角に変換されてしまうようです。
はてなめ、なんのために…?

tattyutattyu 2007/06/16 10:19 これ真面目にやって77バイトはありえないですねw
luaでズルしてゴメンナサイorz

b2oxb2ox 2007/06/16 12:14 m@main=do 〜; m はmainの無限ループを作るためのもので、anarchy golfで他の人が使ってるのを見て覚えました。anarchy golfでしか使いませんが(笑

> コメント欄に入力した半角〜
たしか¥も全角になったはず。

mokehehemokehehe 2007/06/16 16:17 >tattyu
もっとしっかり Sample input と Sample output を作らないとダメですね。

はてなユーザーのみコメントできます。はてなへログインもしくは新規登録をおこなってください。