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の正規表現チェッカー+コード

www.pyregex.com

 

意外と便利だったので。

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に入れたパッケージ一覧

atomに入れたパッケージ一覧

Anacondaやpythonのmatplotlibを使う際、Windows10開発機能の1つであるBashだといろいろ不都合が多かったので、思い切ってWindows環境に変更た。

その際に、emacsからatomに切り替えたので、パッケージ探しで以下のリンク先を参照。
職業別!ATOMエディタの作業が超捗る便利パッケージ24選

とありえずは、こんな感じで入れてみた。 何か必要と思う場合は、そのたびに更新していけばいいかな。

2年ぶりに家のソファーを掃除した

今の家に引っ越してから、2年くらい経ったけど、あまりまともにソファー掃除していなかった。汚れたときちょっと拭いたり、ファブリーズしたりするくらい。

 

で、ふとソファーの掃除ってどうやるんだっけ?って感じで検索したら、よさげな記事が何個かでてきたので試してみたら、以外にかんたんで手軽に掃除できた。

 

布製ソファーを徹底的に掃除してみた!毎日のお手入れからシミ抜き方法まで紹介|ウーマンエキサイト

 

もう困らない! ソファ汚れがあっという間に取れる方法 | プロが教える!すぐに実践できる掃除術

 

布製ソファーの日々の掃除方法&臭いや汚れの落とし方まとめ!

 

気分もすっきり。

重曹は水回りの掃除や床掃除に使えるのは、知ってたし、活用してたけど、ソファーにも応用できるとは知らなかった。