改行のある文字列ファイルをリストに変換する方法
rosalindに解答する際に以下のような文字列ファイルをリストに変換する必要があり、手こずったので記事にしておこうと思います。
test_rosa.txt
>Rosalind_6404
CCTGCGGAAGATCGGCACTAGAATAGCCAGAACCGTTTCTCTGAGGCTTCCGGCCTTCCC
TCCCACTAATAATTCTGAGG
>Rosalind_5959
CCATCGGTAGCGCATCCTTAGTCCAATTAAGTCCCTATCCAGGCGCTCCGCCGAAGGTCT
ATATCCATTTGTCAGCAGACACGC
>Rosalind_0808
CCACCCTCGTGGTATGGCTAGGCATTCAGGAACCGGAGAACGCTTCAGACCAGCCCGGAC
TGGGAACCTGCGGGCAGTAGGTGGAAT
項目名とDNA配列が交互にくり返されているファイルで すね。しかも配列は途中で改行が入っています。これを[[項目名,配列], [項目名,配列]・・・ ]という形に変換することを目指します。
方針
①一行ずつ読み込んでエスケープシーケンス（＝"\n")を取り除く。
②項目名とDNAを区別する。
③改行で分断されたDNAをつないで、一列の文字列にする。
④リストに[項目名,DNA]を追加する。
完成
file =open("C:/python33/test_rosa.txt").readlines() #テキストファイルを行ごとのリストに変換
List=[]
counter=-1
for line in file:
line=line.strip("\n") #各行のエスケープシーケンスを取り除く
if line.startswith(">"):
List.append([line,""]) # ">"を含む行が現れるごとにリストに項目を追加
counter +=1
else:
List[counter][1] +=line # ">"を含まない行を結合して一つの文字列を生成
先ほどのテキストを上記コードに入れて実行すると、
[['>Rosalind_6404', 'CCTGCGGAAGATCGGCACTAGAATAGCCAGAACCGTTTCTCTGAGGCTTCCGGCCTTCCCTCCCACTAATAATTCTGAGG'], ['>Rosalind_5959', 'CCATCGGTAGCGCATCCTTAGTCCAATTAAGTCCCTATCCAGGCGCTCCGCCGAAGGTCTATATCCATTTGTCAGCAGACACGC'], ['>Rosalind_0808', 'CCACCCTCGTGGTATGGCTAGGCATTCAGGAACCGGAGAACGCTTCAGACCAGCCCGGACTGGGAACCTGCGGGCAGTAGGTGGAAT']]
と出力されます（実際は改行なし）。
プロセッサ処理時間を測定するtime.clock()
プログラムのコストについて勉強するに当たり避けては通れない、プロセッサ処理時間の測定の話です。
処理時間の測り方
import time
start_time=time.clock()
-----------------------------------
測りたいコード
-----------------------------------
end_time=time.clock()
result=end_time - start_time
time.clock()を最初に呼び出した時点から計測が始まり、途中のコードをすべて走らせた後に再びtime.clock()を呼び出した時点で計測が終わります。
例
import time
start=time.clock()
for i in range(10):
print( i , end=" ")
end=time.clock()
print("It took",end-start)
これを実行すると
0123456789 It took 0.00010454482278234294 という結果が得られます。
ただしこの0.0001045～という数字はいつでも同じというわけではなく、コンピューターが他に処理していた事柄の多少に左右されます。あくまで「今回」、或いは「現環境」でのプロセッサ処理時間ということです。
例えば今回の場合、
一回目 0123456789 It took 0.00010454482278234294
二回目 0123456789 It took 7.212782346998855e-05(=0.000072127)
三回目 0123456789 It took 0.00013655660960329292
となりました。
ProjectEulerを始めた時点で学んでおくべきテクニックだったのですが、後回しにしていて今まで学んでこなかったtime.clock()。こんなに簡単なことならもっと早く学べばよかったなぁ。
Project Euler56 をpythonで解く
問題
A googol (10^100) is a massive number: one followed by one-hundred zeros; 100^100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, ab, where a, b 100, what is the maximum digital sum?
10の10乗や100の100乗はその値自体は巨大であるが、各桁の数字の合計は1である。
a^b（1<a,b<100）の各桁の数字の合計の最大値を求めよ。
特に言うことがないので解答です。
解答
max_sum=(0)
for a in range(1,100):
for b in range(1,100):
sum=0
for i in str(a**b):
sum +=int(i)
if sum>max_sum:
max_sum=(sum)
print(max_sum)
グローバル変数とローカル変数の違いにさえ気をつければなんということはないです。
答えは972（a=99,b=95）でした。
Project Euler 55をpythonで解く
問題
If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,
349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?
NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.
ある数にそれを逆さまに並べた数を足すという試行を繰り返すと、いずれ12321や4884のように数字の並びが左右どちらから読んでも同じ回文数が得られる場合がある。例えば349は
349+943＝1292、1292+2921＝4213、4213+3124＝7337となり、3回目の試行で回文数が得られる。一方で、196のように何度試行を繰り返しても回文数にならない数も存在する。こうした数はLychrel numberと呼ばれる。
10000以下の数字の内、50回の試行で回文数が得られない数字の個数を求めよ
一般に196問題と呼ばれる問題です。Lychrel numberの最小値が196であることからこう呼ばれています。詳しくはこちら
1桁と2桁の数にLychrel numberが存在しないことは証明済みのようなので、調べる範囲は196～10000でいいようです。
解答
List=[]
for i in range(196,10001):
counter=0
num=i
while counter<50:
num +=int(str(num)[::-1])
if str(num)==str(num)[::-1]:
List.append(i)
break
else:
counter +=1
print(9805-len(List))
forループで調べる数字をwhileループで試行を表現しました。whileループ2行目で試行を行い、ifステートメントで回文数か否かを調べます。あとは10000-196+1＝9805から非Lycheral数の個数を引けば答え249が得られます。
ProjectEuler42 をpythonで解く
最近ご無沙汰だったProjectEuler。なんとなく解けそうだったので挑戦してみました。
Problem42
The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.
Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?
（適当な）訳
１からnまでの自然数の和を三角数といい、tn=n(n+1)/2で表す。今、ある英単語に含まれる各文字のアルファベット順での位置を数値とし、その和を単語の数値と呼ぶことにする。例えばSKYという単語はS=19、K=11、Y＝25となるから単語の数値は55となる。
word.txtに含まれる単語のうち単語の数値が三角数であるもの（三角単語）の個数を求めよ。
解答
alphabet=[chr(i) for i in range(65,65+26)]
input=open("C:/python/words.txt")
read=str(input.read())
word=read.split('","')
def word_to_sum(word):
sum=0
for i in word:
for j in range(26):
if i ==alphabet[j]:
sum += j+1
return sum
def find_tri_num(num):
boolean=False
for i in range(1,100):
if i*(i+1)/2==num:
boolean=True
return boolean
List=
for i in word:
List.append(word_to_sum(i))
tri_num=
for i in List:
if find_tri_num(i):
tri_num.append(i)
print(len(tri_num))
本当はreadline()で一気にリストが作れたらよかったんですが、words.txtが一行のテキストオブジェクトであるために上手くいかず断念。結局、一度文字列に変換してからsplit()を用いてリストに再変換することにしました。
word_to_num()では代入された文字列の各文字をアルファベットリスト内で探し、そのインデックス値を基に単語の数値を作成します。
find_tri_num()では代入された数値が三角数か否かを判定します。今回は1≦n≦100で判定しました。
len()でリストの長さを得れば完成で、答え162を得られます。
アルファベットのリストを作る in python
アルファベットのリストを手打ちするのが面倒だったので、瞬時にリストを作成する方法を探してみました。
Pythonでシンプルにアルファベットのリストを作るを参考にしました。というかこのコードをpython3系用にいじっただけです。
コード
# upper-case A-Z
[chr(i) for i in range(65,65+26)]
# lower-case a-z
[chr(i) for i in range(97,97+26)]
chr()は整数値を文字に変換する関数。それをrange()を用いて65～90まで適用すれば大文字、97～122まで適用すれば小文字のリストが得られます。
因みに文字からそれに対応する整数値を得るにはord()を使います。
例：ord('A') =65 ,chr(65) ='A'
処理の順番の重要性を考える。
コードを書く時、僕は思いついた順にコードを書き連ねていきます。大抵はそれで上手くいっていたんですが、今日とあるコードを書いていた際、分岐の順番の違いからくるエラーに直面したので、記録に残しておこうと思います。
例えば
def func(List):
if List[0]=='a':
print('python')
elif List==:
print('it's empty!!')
という関数を作ったとします。一見Listの先頭が'a'だった場合にはpython、Listが空っぽだった場合にはit's empty!!を値として返すというだけの関数に見えますが、ここに重大な欠点があります。
この関数に「」を代入してみると、
func()
Traceback (most recent call last):
File "<pyshell#20>", line 1, in <module>
func()
File "<pyshell#19>", line 2, in func
if List[0]=='a':
IndexError: list index out of range
となり、エラーが返ってきます。このときエラーが2行目で起きていることが問題なのです。
この関数では空のリストに対応する処理が設定されていたはずなのに、その処理より以前に別の処理が存在するためにそちらが優先されてしまいます。その結果、せっかく設定した処理が活かされなくなってしまうのです。
上の例では以下のように分岐の順番を入れ替えることでこの間違いを回避することができます。
def func(List):
if List==[]:
print('it's empty!!')
elif List[0]=='a':
print('python')
こうすればリストが空か否かをまず分岐として設定することができ、仮に空でなかった場合のみ4行目の分岐に進むようにできます。
どうやら分岐は、多くの場合が対象となるものは後に、ごく少数の場合が対象となるものは先に書くのがいいようです。言い換えれば分岐は条件がキツい順に書くべきということです。（例えば「空のリストに対する分岐」は「リスト全般に対する分岐」より先に書く、「自然数に対する分岐」は「整数に対する分岐」より先に書く等）
実は自分で書いたコードの中にも無意識のうちにこの法則を実践してるものがちらほらあったのに後で気が付きました(笑） 間違えてみるまで気づかないものですねぇ・・・。これからもガンガン間違えていきたいと思います（爆）
