Inverse (Udacity)
二文探索の応用で所定のf(x) < y条件下での、xの最大値をとるコード
二文探索で解けるとは思っていたが、yの外に枠を設ける発想ができていなかった。勉強不足か。
def inverse(f, delta=1/1024):
def f_1(y):
lo, hi = find_bounds(f, y)
return binary_search(f, y, lo, hi, delta)
return f_1
def find_bounds(f, y):
x = 1
while f(x) < y:
x = x * 2
lo = 0 if (x == 1) else x/2
return lo, x
def binary_search(f, y, lo, hi, delta):
while lo <= hi:
x = (lo + hi) / 2
if f(x) < y:
lo = x + delta
elif f(x) > y:
hi = x - delta
else:
return x
return hi if (f(hi)-y < y-f(lo)) else lo
def square(x): return x*x
def power10(x): return 10**x
log10 = inverse(power10)
sqrt = inverse(square)
cuberoot = inverse(lambda x: x*x*x)
def test():
import math
nums = [2,4,6,8,10,99,100,101,1000,10000,20000,40000,100000000]
for n in nums:
test1(n, 'sqrt', sqrt(n),math.sqrt(n))
test1(n, 'log', log10(n), math.log10(n))
test1(n, '3-rt', cuberoot(n), n**(1./3.))
def test1(n, name, value, expected):
diff = abs(value-expected)
print('%6g: %s = %13.7f (%13.7f actual); %.4f diff; %s' % (
n, name, value, expected, diff,
('ok' if diff < .002 else '****BAD****')))
pyhtonの正規表現チェッカー+コード
意外と便利だったので。
import re
def findtags1(text):
params = '(\w+\s*=\s*"[^"]*"\s*)*'
tags = '(<\s*\w+\s*' + params + '\s*/?>)'
return re.findall(tags, text)
def findtags2(text):
m = re.findall(r'<[^\/<>]*[ab].*?>', text)
return m
testtext1 = """
My favorite website in the world is probably
<a href="www.udacity.com">Udacity</a>. If you want
that link to open in a <b>new tab</b> by default, you should
write <a href="www.udacity.com"target="_blank">Udacity</a>
instead!
"""
testtext2 = """
Okay, so you passed the first test case. <let's see> how you
handle this one. Did you know that 2 < 3 should return True?
So should 3 > 2. But 2 > 3 is always False.
"""
testtext3 = """
It's not common, but we can put a LOT of whitespace into
our HTML tags. For example, we can make something bold by
doing < b > this < /b >, Though I
don't know why you would ever want to.
"""
def test1():
assert findtags1(testtext1) == ['<a href="www.udacity.com">',
'<b>',
'<a href="www.udacity.com"target="_blank">']
assert findtags1(testtext2) == []
assert findtags1(testtext3) == ['< b >']
return 'tests pass'
def test2():
assert findtags2(testtext1) == ['<a href="www.udacity.com">',
'<b>',
'<a href="www.udacity.com"target="_blank">']
assert findtags2(testtext2) == []
assert findtags2(testtext3) == ['< b >']
return 'tests pass'
print(test1())
print(test2())
Udacity Design of Computer Programsのメモその2
左右対称の文字列を含む文字列を与えると、左右対称の開始位置から終了位置までを切り取ってくれる。
grow関数・・・ある特定の文字を中心に左右対称性があれば、2文字ずつ左右に伸ばして最長の左右対称文字列を取得する関数
def longest_subpalindrome_slice(text):
"Return (i,j) such that text[i:j] is the longest palindrome in text."
if text == '': return (0,0)
def length(slice): a,b = slice; return b-a
candidates = [grow(text, start, end)
for start in range(len(text))
for end in (start, start+1)]
return max(candidates, key=length)
def grow(text, start, end):
"Start with a 0- or 1- length palindrome; try to grow a bigger one."
while(start > 0 and end < len(text)
and text[start-1].upper() == text[end].upper()):
start -= 1; end += 1
return (start, end)
def test():
L = longest_subpalindrome_slice
assert L('racecar') == L('Racecar') == L('RacecarX') == (0, 7)
Udacity Design of Computer Programsのメモ
Lesson2で出たコードを模写。
fill_in2に'ODD +ODD = EVEN'のような引数を渡して実行すると、適当に数字を埋めて'3+3 = 6'のような文字列を返してくれる。
permutationで組み合わせの数を出せるのは、かなり便利だなと思った。
import re
import itertools
import string
def compile_formula(formula, verbose=False):
"""Compile formula into a function. Also return letters found, as a str,
in same order as parms of function. The first digit of a multi-digit
number can't be 0. So if YOU is a word in the formula, and the function
is called with Y eqal to 0, the function should return False."""
# modify the code in this function.
letters = ''.join(set(re.findall('[A-Z]', formula)))
firstletters = set(re.findall(r'\b([A-Z])[A-Z]',formula))
parms = ', '.join(letters)
tokens = map(compile_word, re.split('([A-Z]+)', formula))
body = ''.join(tokens)
if firstletters:
tests = ' and '.join(L+'!=0' for L in firstletters)
body = '%s and (%s)' % (tests, body)
f = 'lambda %s: %s' % (parms, body)
if verbose: print(f)
return eval(f), letters
def compile_word(word):
"""Compile a word of uppercase letters as numeric digits.
E.g., compile_word('YOU') => '(1*U+10*O+100*Y)'
Non-uppercase words uncahanged: compile_word('+') => '+'"""
if word.isupper():
terms = [('%s*%s' % (10 ** i, d))
for (i, d) in enumerate(word[::-1])]
return '(' + '+'.join(terms) + ')'
else:
return word
def faster_solve(formula):
"""Given a formula like 'ODD + ODD == EVEN', fill in digits to solve it.
Input formula is a string; output is a digit-filled-in string or None.
This version precompiles the formula; only one eval per formula."""
f, letters = compile_formula(formula)
for digits in itertools.permutations((1, 2, 3, 4, 5, 6, 7, 8, 9, 0), len(letters)):
try:
if f(*digits) is True:
table = str.maketrans(letters, ''.join(map(str, digits)))
return formula.translate(table)
except ArithmeticError:
pass
def test():
assert faster_solve('A + B == BA') == None # should NOT return '1 + 0 == 01'
assert faster_solve('YOU == ME**2') == ('289 == 17**2' or '576 == 24**2' or '841 == 29**2')
assert faster_solve('X / X == X') == '1 / 1 == 1'
return 'tests pass'
test()
Gitのお勉強 1日目
Udemyで以下のコースを受けてみた。
もう怖くないGit!チーム開発で必要なGitを完全マスター
自分の場合、ネットで調べると情報の整理がうまくできないことが多いので、こういう風に体系的に教えてもらった方がありがたい。
ローカルリポジトリでのCommitまでの基本コマンドをメモ書きがてら書いておく。
ワークツリーでのファイル作成
# 初期化 # .gitディレクトリが作成される # ファイル一覧:圧縮(コード等)、ツリー、コミット、インデックス、設定 $ git init Initialized empty Git repository in C:/Users/rai-j/python_bin/atcoder_trials/.git/ # .git内はこんな感じ $ ls .git/ COMMIT_EDITMSG description hooks/ info/ objects/ config HEAD index logs/ refs/ # ハッシュ化 $ git hash-object R081C_make_a_retangle.py ad6c5ab1513c2f4b58f05b956adea87392cbe88f # addコマンドでステージに圧縮済みファイルを追加 $ git add R081C_make_a_retangle.py warning: CRLF will be replaced by LF in R081C_make_a_retangle.py. The file will have its original line endings in your working directory.
ローカルリポジトリへコミット
# -mはメッセージのオプション # # メッセージの書き方 # 1行目:変更内容の要約 # 2行目:空行 # 3行目:変更した理由 # ステージからリポジトリへコミット $ git commit -m 'add answer R081C' [master (root-commit) 305cb88] add answer R081C 1 file changed, 27 insertions(+) create mode 100644 R081C_make_a_retangle.py
コミット状況の確認
$ git status On branch master Untracked files: (use "git add <file>..." to include in what will be committed) C++/ R080C_adjacent.py R081D_coloring_dominoes.py R081E_dont_be_a_subsequence.py R082C_together.py nothing added to commit but untracked files present (use "git add" to track)
コミット後のデータ確認方法
$ git cat-file -p master^{tree} 100644 blob ad6c5ab1513c2f4b58f05b956adea87392cbe88f R081C_make_a_retangle.py 040000 tree fea172f4f6ef0a096ae5766b02d54459a72d82a6 subdir # コミットをたどるには、parent(以下だと、305cb88...)を追っていけばよい $ git cat-file -p HEAD tree 1a7da0f8af907e650847b7fecc312105113c4118 parent 305cb88f2cd7184e21b2c6eacf189099fdaa8b56 author yasuhitotanaka <sitofourth02@gmail.com> 1506399493 +0900 committer yasuhitotanaka <sitofourth02@gmail.com> 1506399493 +0900 # Treeオブジェクトの先頭の文字列(1a7da)で検索した中身を表示 $ git cat-file -p 1a7da 100644 blob ad6c5ab1513c2f4b58f05b956adea87392cbe88f R081C_make_a_retangle.py 040000 tree fea172f4f6ef0a096ae5766b02d54459a72d82a6 subdir
Atomに入れたパッケージ一覧
2年ぶりに家のソファーを掃除した
今の家に引っ越してから、2年くらい経ったけど、あまりまともにソファー掃除していなかった。汚れたときちょっと拭いたり、ファブリーズしたりするくらい。
で、ふとソファーの掃除ってどうやるんだっけ?って感じで検索したら、よさげな記事が何個かでてきたので試してみたら、以外にかんたんで手軽に掃除できた。
布製ソファーを徹底的に掃除してみた!毎日のお手入れからシミ抜き方法まで紹介|ウーマンエキサイト
もう困らない! ソファ汚れがあっという間に取れる方法 | プロが教える!すぐに実践できる掃除術
気分もすっきり。
重曹は水回りの掃除や床掃除に使えるのは、知ってたし、活用してたけど、ソファーにも応用できるとは知らなかった。