AtCoder Beginner Contest 125

AtCoder Python

A - Biscuit Generator

a, b, t = [int(a) for a in input().split()]

result = ((t + 0.5) // a) * b
print(int(result))

B - Resale

n = int(input())
V = [int(a) for a in input().split()]
C = [int(a) for a in input().split()]

diff = [v - c for v,c in zip(V, C) if v - c > 0]
result = int(sum(diff))
print(result)

C - GCD on Blackboard

n = int(input())
A = [int(a) for a in input().split()]
A.sort()

def func():
    for i in range(A[1], 0, -1):
        yellow_card = 0
        for a in A:
            if a % i > 0:
                yellow_card += 1
            if yellow_card >= 2:
                break
        if yellow_card < 2:
            return i

result = func()
print(result)

D - Flipping Signs

j, k - 1 の間の全ての整数 i に対して「 A_i と A_{i+1} に -1 を乗算する」操作を繰り返すと、 最終的には、両端の A_j と A_k だけが符号を反転され、他の値は変化しません。

従って、問題文の操作を次のように置き換えても等価な問題になります。

操作: 1 \leq j, k \leq N - 1 を満たす整数 j, k を選ぶ。 A_j と A_k に -1 を乗算する。

A_i の中に負数が偶数個あれば、操作を繰り返して全てを正数に変えることができます。
A_i の中に負数が奇数個あれば、操作を繰り返して任意の1つ以外全てを正数に変えることができます。

n = int(input())
A = [int(a) for a in input().split()]

num_negative = sum(a < 0 for a in A)
A_abs = [abs(a) for a in A]

if num_negative % 2 == 0:
    result = sum(A_abs)
else:
    result = sum(A_abs) - 2 * min(A_abs)

print(result)

つくってまなぼう 自動微分 (Automatic Differentiation)

機械学習 Python Automatic Differentiation

導入

機械学習で予測問題（Regression や Classification）を解くステップは、大きく以下のように分解することができます：

  1. 予測器となる関数をモデル化（CNN、RNNなど）
  2. 予測結果を評価するための損失関数を定義（自乗誤差、Cross Entropyなど）
  3. 勾配法によって損失を最小化
    1. 勾配を計算（backpropagation）
    2. パラメータを更新（SGD、Adamなど）

Neural Network などの機械学習でよく用いられるモデルは、シンプルな関数を合成や四則演算などで組み合わせた巨大な計算グラフの形をしています。そんな関数の勾配を効率的に計算するためには工夫が必要で、標準的な方法として知られているのが backpropagation です。

実は、この backpropagation は Automatic Differentiation (AD) と呼ばれるアルゴリズムの特殊ケースに当たり、機械学習が脚光を浴びるより前から提案されていました。

ADの中心的なアイデア

微分の連鎖律

Neural Network は全体として見ると非常に複雑な関数ですが、パーツ単位で見れば線形関数やsigmoid関数など導関数が既知のシンプルな関数で構成されています。

f:id:P_N_D:20190421191021p:plain

そこで役に立つのが、合成関数に対する微分の連鎖律です。例えば、上図のように変数 y が変数 u_1, u_2, \cdots, u_n だけに依存し、更に u_1, u_2, \cdots, u_n が x に依存している場合、連鎖律は次式のように表されます：

$$ \dfrac{\partial y}{\partial x} = \dfrac{\partial y}{\partial u_1}\dfrac{\partial u_1}{\partial x} + \dfrac{\partial y}{\partial u_2}\dfrac{\partial u_2}{\partial x} + \cdots + \dfrac{\partial y}{\partial u_n}\dfrac{\partial u_n}{\partial x} $$

この関係を利用すると、式 x \mapsto y の微分という問題を、より細かな部分式 x \mapsto u_i および u_i \mapsto y の微分という問題に分解することができます。更に、各部分式について再帰的に連鎖律を適用することで、最終的には導関数が既知の関数まで到達します。

この素朴なアイデアに基づいて、機械的に微分を計算する Python スクリプトを実装します。大まかな仕様は：

  • 計算式を表現するためのデータ型として Expr クラスを定義
  • args プロパティで、引数の計算式を表す Expr オブジェクトを参照
  • Expr オブジェクト y と Symbol オブジェクト x に対して、 y.diff(x) は関数 x \mapsto y の導関数を表す Expr オブジェクトを返す
    def dot(xs, ys):
        return Plus(*[Product(x, y) for x, y in zip(xs, ys)])
    
    class Expr:
        def diff(self, symbol):
            diffs = [arg.diff(symbol) for arg in self.args]
            grad = self.grad()
            return dot(diffs, grad)
    
    class Symbol(Expr):
        def __init__(self, symbol):
            self.symbol = symbol
        
        def diff(self, symbol):
            if self == symbol:
                return Constant(1)
            else:
                return Constant(0)
    
    class Constant(Expr):
        def __init__(self, value):
            self.value = value
    
        def diff(self, symbol):
            return Constant(0)
    
    class Plus(Expr):
        def __init__(self, *args):
            self.args = args
    
        def grad(self):
            return [Constant(1)] * len(self.args)
    
    class Product(Expr):
        def __init__(self, arg0, arg1):
            self.args = [arg0, arg1]
    
        def grad(self):
            arg0, arg1 = self.args
            return [arg1, arg0]

特に5～8行目の関数 diff が、前述の連鎖律を用いて再帰的に定義されている部分です。コード中の変数名と式中の記号に対応を付けると：

  • Expr オブジェクト ↔ y
  • symbol ↔ x
  • args ↔ u_1, u_2, \cdots, u_n
  • diffs ↔ \dfrac{\partial u_1}{\partial x}, \dfrac{\partial u_2}{\partial x}, \cdots, \dfrac{\partial u_n}{\partial x}
  • grad ↔ \dfrac{\partial y}{\partial u_1}, \dfrac{\partial y}{\partial u_2}, \cdots, \dfrac{\partial y}{\partial u_n}

上記のコードが正しく動くことを確認するために、 Expr オブジェクトを文字列に変換する方法を定義します。

    Symbol.__str__   = lambda self: str(self.symbol)
    Constant.__str__ = lambda self: str(self.value)
    Plus.__str__     = lambda self: ' + '.join(['(' + str(arg) + ')' for arg in self.args])
    Product.__str__  = lambda self: ' * '.join([str(arg) for arg in self.args])

例として y = x + x^ 2 を微分してみると以下のような結果になります。冗長な見た目ではありますが、 \dfrac{\partial y}{\partial x} = 1 + 2x と等価な式になっていることがわかります。

    x = Symbol('x')
    y = Plus(x, Product(x, x))
    dy = y.diff(x)
    str(dy)
    
    # '(1 * 1) + ((1 * x) + (1 * x) * 1)'

動的計画法

前述の素朴な実装はADと呼べる代物ではなく、分割統治法に共通して存在する欠陥を抱えています。その欠陥とはつまり、同一の部分式に対する微分計算を無駄に多数回繰り返してしまうことです。

f:id:P_N_D:20190421191019p:plain

上図のような計算式 y を変数 x について微分する場合を考えましょう。前述の diff メソッドは、式 y を始点として引数を再帰的に（矢印を逆方向に）辿っていきます。このとき、 上図のグラフはツリーではなく Directed Acyclic Graph (DAG) になっているので、 y から v に至る経路が複数（ n 個）存在します。従って、関数 f \colon x \mapsto v の微分を計 n 回計算することになりますが、何度計算しても同じ結果が返されるだけなので非常に効率が悪いです。

そこで、次のようにメモ化を用いて実装することで冗長な計算を省くことができます。

  • ある部分式について初めて diff が呼び出されたら普通に微分を計算
  • 計算結果をメモリに保存
  • 再び同じ部分式について diff が呼び出されたら保存された結果を再利用
    def memoize(f):
        memo = {}
        def memoized(*args):
            if args not in memo:
                memo[args] = f(*args)
            return memo[args]
        return memoized
    
    class Expr:
            @memoize # デコレーターを追加
        def diff(self, symbol):
                    # 前述の実装と同じ

評価順序

Forward-mode (bottom-up) AD

前述の実装では、 \dfrac{\partial x}{\partial x} = 1 からスタートして、中間変数 u_i を入力 x で微分した値 \dfrac{\partial u_i}{\partial x} を徐々に求めていきます。この方法は、元の計算グラフで中間変数の値を計算していくのと同じ順序で微分を計算していくため、 forward-mode AD と呼ばれています。

f:id:P_N_D:20190421191033p:plain

forward-mode AD を使うと、「各出力 y_i をある1つの入力 x で微分した値 \dfrac{\partial y_i}{\partial x}」を1度の走査で求めることができます。従って、関数の入力より出力の方が個数が多い場合には、 forward-mode AD が計算量的に有利です。

Reverse-mode (top-down) AD

一方 reverse-mode AD では、 \dfrac{\partial y}{\partial y} = 1 からスタートして、出力 y を中間変数 u_i で微分した値 \dfrac{\partial y}{\partial u_i} を徐々に求めていきます。

f:id:P_N_D:20190421191036p:plain

reverse-mode AD を使うと、「ある1つの出力 y を各入力 x_i で微分した値 \dfrac{\partial y}{\partial x_i}」を1度の走査で求めることができます。従って、関数の出力より入力の方が個数が多い場合には、 reverse-mode AD が計算量的に有利です。特に機械学習の問題では、出力が1つだけの関数の勾配を計算することが多いため reverse-mode AD (backpropagation) が重宝されます。

つづく

次の記事で書く予定の内容：

  • reverse-mode AD のPython実装
  • ADでよく使われる中間表現（ Wengert list など）
  • operator overloading

参考文献

  • Automatic differentiation in machine learning: a survey
    • 初めてADを学ぶのに適した survey 論文
    • 記号微分や有限差分近似とADの違いを最初に明確にしている。
    • forward-mode, reverse-mode の仕組みとメリットについて説明している。
    • Wengert list の例を示している。
    • dual number を使った forward-mode AD の実装を説明している。
    • ADの歴史や応用例を紹介している。
    • 5節で実装の詳細を説明しているが、式や図が無いため初学者には読みづらい。
  • Automatic differentiation in ML: Where we are and where we should be going
    • Python の AD パッケージ Myia を提案する論文
    • TensorFlow など既存の AD 実装の特徴を簡単に述べている。
    • Myiaの特徴を述べている。
      • 中間表現として計算グラフを使う。
      • 高階関数や再帰関数も微分できる。
      • 純粋な関数型。
    • Myiaの実装に関する説明はほぼ無い。
    • 図1中の "After macro expansion" から "After optimization" が飛躍しすぎていて、変換過程をイメージできない。
  • Don't Unroll Adjoint: Differentiating SSA-Form Programs
  • MikeInnes/diff-zoo: Differentiation for Hackers
    • Zygote.jl の開発者による、 AD の基礎的な説明
    • Jupyter notebook + Julia を使って、徐々に実装を進めながら解説している。
    • Julia の metaprogramming 機能を使って計算式をパースし、 Wengert list に変換している。
    • 「記号微分は ”expression swell" を引き起こす」というよくある言説を否定している。

AtCoder Tenka1 Programmer Beginner Contest 2019

AtCoder Python

A - On the Way

a, b, c = [int(n) for n in input().split()]

x = min([a,b])
y = max([a,b])

if x <= c and c <= y:
    print('Yes')
else:
    print('No')

B - *e**** ********e* *e****e* ****e**

n = int(input())
s = input()
k = int(input())

a = s[k - 1]

result = [a if s[i] == a else '*' for i in range(n)]
print(''.join(result))

C - Stones

「黒い石のすぐ右に白い石があるような箇所がない」ならば、有り得るのは「左側は全て白、右側は全て黒」という状態だけです。この状態は更に「左から n 番目まで白」の場合に分けることができます。よって：

  1. 左から n 番目までに存在する黒石の数 b[n] をカウント
  2. n 番目より右に存在する白石の数 w[n] をカウント
  3. b[n] + w[n] の n についての最小値が答え
n = int(input())
s = input()

def black():
    result = [0] * n
    count = 0
    for i in range(n):
        if s[-i-1] == '.':
            count += 1
        result[-i-1] = count
    return result + [0]

def white():
    result = [0] * n
    count = 0
    for i in range(n):
        if s[i] == '#':
            count += 1
        result[i] = count
    return [0] + result

num = [x + y for x,y in zip(black(), white())]
result = min(num)

print(result)

D - Three Colors

解けず

AtCoder Beginner Contest 124

AtCoder Python

A - Buttons

a, b = [int(x) for x in input().split()]

c = max([a, b])

if c == a:
    d = max([a - 1, b])
else:
    d = max([a, b - 1])

result = c + d
print(result)

B - Great Ocean View

スケールがしょぼいので超素朴に解く。

計算量 O(N^ 2)

n = int(input())
h = [int(a) for a in input().split()]

result = 0
for i in range(n):
    if all([h[j] <= h[i] for j in range(i)]):
        result += 1

print(result)

C - Coloring Colorfully

  • タイルは左右一列に並ぶ
  • タイルは N 枚
  • タイルの色は2種類
  • どの隣り合う2枚のタイルも異なる色

という条件を満たすのは、黒と白が交互に並ぶ次の2パターンだけ。

  • 0101010...
  • 1010101...

したがって解法は

  1. 与えられたタイルの並び S と上記2パターンを比較し、色が異なるタイルの枚数 p, q をそれぞれ求める。
  2. p と q の最小値を取る。

計算量 O(N)

s = [int(x) for x in list(input())]

n = len(s)

p = [s[i] == i % 2 for i in range(n)]
q = [s[i] == (i - 1) % 2 for i in range(n)]

result = min([sum(p), sum(q)])
print(result)

D - Handstand

最善手では、常に 0 が連続している部分だけを反転させる。

  1. 111 00 11 0 1111 000 のように、文字が連続している部分に分割する。
  2. 「 1 の間にある 0 を反転させて繋ぐ」ことで、 1 を繋げられる最大の長さを計算。
    1. 文字が連続している各部分の長さを計算。
    2. 移動平均を取る。
    3. 最大値を取る。
import numpy as np

n, k = [int(a) for a in input().split()]
s = input()

def main():
    consecutive_ones = [len(x) for x in s.split("0") if x != '']
    consecutive_zeros = [len(x) for x in s.split("1") if x != '']

    if s[0] == "0":
        consecutive_ones.insert(0, 0)
    if s[-1] == "0":
        consecutive_ones.append(0)
    
    if len(consecutive_zeros) == 0:
        return n
    else:
        cumsum_ones = np.convolve(consecutive_ones, np.ones(k+1), mode='valid')
        cumsum_zeros = np.convolve(consecutive_zeros, np.ones(k), mode='valid')

        z = [x + y for x,y in zip(cumsum_ones, cumsum_zeros)]
        return int(max(z))

print(main())

LAPRAS株式会社でインターンを始めました

インターン 機械学習

概要

2019年3月25日から、LAPRAS株式会社（旧scouty）でアルゴリズムエンジニアとしてインターンを始めました。

LAPRASについて簡単に説明すると、GitHubやSNSなどをクロールして構築したDBと機械学習技術を用いて、エンジニアと企業をマッチングさせるサービスです。4月10日からto Cのサービスが開始し、今まで採用担当者だけが閲覧可能だったプロフィール画面がエンジニア本人にも公開されました。

f:id:P_N_D:20190610133809p:plain
LAPRASプロフィール

LAPRASを選んだ理由

私は大学で機械学習の研究をしており、また趣味やアルバイトでWeb開発の経験があります。就職/インターン先を選ぶにあたっては、これらのスキルセットのどちらか或いは両方を活かせることを第一条件にしています。

とは言え、人工知能の活用を謳う企業は掃いて捨てるほどあります。その中で特にLAPRASが良いと思った理由を以下で述べていきます。

広報記事の内容に説得力が有る

LAPRASでは、自社ブログのHR TECH LABとAI LAB、加えてWantedly feedで主に情報を発信しています。そこには、LAPRASが組織として持っている考え方と、なぜそのように考えるのかという根拠がはっきりと書かれています。

特に印象に残ったものを1つ挙げましょう。LAPRASから送られるスカウトメールは全て人が手動で書かかれていますが、その理由に繋がるのが以下の記事です。

どんなに候補者に強い関心を持っていても、それが文面から伝わらないのでは意味がありません。また、文面から関心の強さが伝わっても、仕事内容にも、環境にも、待遇にも、候補者にとってメリットがないというのでは、その会社に興味を持ちません。 これらを候補者に伝えるために、重要となってくるのがスカウトメールのパーソナライズです。多数の人に対して送られるテンプレートのような内容では、特に関心の強さが伝わりません。また、メリットの説得力も弱くなります。

スカウトメールを実際に受け取る側として、この記述が正しいことを私はよく知っています。「特別オファー」と称して不特定多数を相手にスパムメールをばらまく就活サービスもあれば、プロフィールのどこに興味を持ったか一言添えてスカウトを送るサービスもありました。好感を抱いたのは当然後者の方です。

更に、この記事には非常に高度にパーソナライズされたスカウトメールの文例が多数提示されています。広報のために脚色した話ではなく、普段からこの考えが実践されていることが明白に見て取れました。

組織体制がおもしろい

LAPRASはホラクラシー組織という形態を取っています。

私もまだ詳しく理解できているわけではないですが、大雑把に説明するならば：

  • 従来 : 人を階層状に組織
  • ホラクラシー : 役割を階層状に組織

軍隊にとっては従来の組織が自然ですが、現代の企業にとってはホラクラシーの方が自然な形のように感じます。

何か大きな仕事を達成する為に別の副次的な仕事が複数発生することはよくあります。そうして次々と仕事が増殖していく中で秩序を保つためには：

  • 今どんな役割があるのか
  • その役割はそもそも何の目的で存在しているのか
  • その役割には誰が割り当てられているのか

を常に明らかにしておかなければなりませんが、これを最も自然に整理できるのがホラクラシー組織だと認識しています。

インターン選考

私がアルゴリズムエンジニアのインターンとして選考を受けた際には、スキルチェック課題として以下の3つが出題されました：

  1. 自身の研究のプレゼン（学会で発表したスライドを流用）
  2. Web API実装（課題が事前に与えられ、面接当日までにソースコードを提出）
  3. ホワイトボードコーディング（面接当日にコーディング）

各課題について質疑応答やディスカッションがあり、研究や実装の能力に加えて思考過程と論理性も判断されるような選考でした。

個人的におもしろかったのは、学会で研究者向けに発表するためのスライドをそのまま使ってプレゼンできた点です。普通の企業の面接でそんなことをしたらまず理解されないのですが、LAPRASの選考では、たった15分ほど話をしただけで私の指導教員より的確な質問が飛んできました。それだけ優秀な社員がいて、なおかつ採用に本気で取り組んでいることを示す証拠です。

現在までにやった仕事

取り組んだ課題

LAPRAS SCOUTには検索条件を基に適切なエンジニアを採用担当者にレコメンドする機能があり、その関連の課題に現在取り組んでいます。この記事を書いている時点で累計9日出社しましたが、その間にした仕事は：

  • 候補者の技術力スコアと採用担当者のフィードバックの相関を分析
  • レコメンドの新しいアルゴリズムとして使えそうな先行研究の調査
  • LAPRAS SCOUTを使って候補者を選び、スカウトメールを書く研修

LAPRAS SCOUTを実際に使う中で、検索条件と合致しない地域に住んでいる候補者がレコメンドされることがありました。その解決に向けて私は今、候補者の居住地データの構造化をしているところです。

仕事の方法論

私のワークフローを振り返ると、おおよそ以下のようなパターン（順不同）を繰り返しています：

  • 課題を明確にしてGitHub issueを作る
  • Redashでデータを閲覧
  • Python + Jupyter Notebookでもう少し詳しい分析、プロトタイピング
  • 業務の過程で考えたこと、詰まった所、細かいタスクなどをSlackに書く
  • ノートアプリ（Notion）で自分のタスクや分析結果などを整理
  • 分析結果がまとまったら社内wiki（esa.io）にページを作成して報告

まだ洗練されているとは言い難く、特に情報やタスクの管理に関してツールをどう使い分けるかが悩ましいところです。現状では、自分が今何をしているかを他のメンバーからわかるようにする目的でSlackに雑に情報を投げ、ローカルで整理し、最終的にまとまったものをチームに共有するようにしています。

LAPRASにインターンとして入った後の印象

LAPRASの企業情報ページには5つのAction Agendaが掲げられており、実際に仕事をする中でこれらのAgendaが非常によく遵守されている印象を受けました。以下では特に、 オープンであれと エンドユーザーファースト について述べます。

オープンであれ

社内外に向けて、本当に恐ろしいほど情報がオープンにされています：

  • 社外に向けてオープン
    • エンジニアに対して、LAPRASのプロフィールページを公開
    • AI LABで技術を発信
    • 各種イベントでの発表
    • GlassFrogでホラクラシーの組織図を見ることができる
  • 社内に向けてオープン
    • Slackのチャンネルが全てpublic
    • 社内wikiで全ての情報が公開されている

特に社内wikiは、正社員/インターンや部署に関係なく（ホラクラシー組織なので部署という用語は適切ではないと思いますが）全てのページを閲覧することができます。公開されている情報の例を挙げると：

  • 技術情報
  • 各月の売上、売上原価、販管費、損益
  • 各月の契約企業数、スカウト返信率などのKPI
  • 給与のスタンス
  • ミーティングの議事録

エンドユーザーファースト

LAPRASにとってのエンドユーザーとはつまり、採用候補者となるエンジニアのことです。エンドユーザーの利益向上のためにLAPRASが今取り組んでいることとして、上でも述べた2つの点が挙げられます：

  • 候補者一人ひとりに向き合ったスカウトメールを書く
  • 収集した候補者プロフィールの情報を、企業だけでなく本人にも開示する

「スカウトメールをパーソナライズする」と言葉にするのは簡単ですが、実行するには多大な労力が必要です。実際に、私が研修で初めてスカウトメールを書いたときは、1通あたり1時間程度かかっていたと思います。

そこまでしてエンドユーザーを大事にしている理由について、私なりの推測があります。LAPRASの社員は、自社サービスの開発者であり顧客であると同時に、エンドユーザーの立場でもあることです。LAPRAS SCOUTからメールを受け取ってLAPRASに転職した方もいれば、他社サービスからスカウトメールを受け取った経験のある方もいます。そうした自身の体験に基づいてエンドユーザーファーストを志向しているのだと私は考えています。

最後に

LAPRASに登録すると、エンジニアとしての技術力が客観的に数値で評価されておもしろいので、ぜひ試してみてください。（ポジショントーク）

Google Place APIで住所や地名のデータを構造化する

機械学習 Google Cloud Platform Python

概要

Google Mapの検索機能は、人がある程度大雑把に地名を入力しても正確な住所を返してくれます。これを利用すれば、人が生成した住所や地名の膨大なデータを、プログラムや機械学習で扱いやすいように構造化することができます。この記事では特に、 Tokyo, Japan や 東京都渋谷区 などの文字列をGoogle Place APIに投げて、対応する都道府県の情報を得ることを目的とします。

Google Place APIについて

今回の目的に関係があるAPIは、下記のような階層で整理されています。

特に今回必要とする情報は、Find Place requests と Places Details requests だけを使えば得ることができます。 Text Search requests は無用に詳細な情報を取得して料金が高くなるため、今回は使用すべきではありません。

  • Find Place requests : 地名や住所の文字列を入力として、対応する場所の情報を返す。
  • Text Search requests : 地名や住所の文字列を入力として、対応する場所の完全な情報を返す。要求する情報の種類を指定することができず、常に追加課金が発生する。
  • Places Details requests : place_id を入力として、対応する場所の情報を返す。

APIの料金

Google Maps Platformの料金表を見るとわかるように、 Find Place と Places Details にはどちらも同じ料金体系が設定されています。

  • 毎月$200のフリークレジットが与えられる
  • 月間100,000リクエスト以内で、必要最小限の情報だけを要求する場合：
    • $17 / 1,000リクエスト
    • 月間11000リクエストまでは無料

都道府県を取得する手順

Find Place requests で取得できる値の一つに、 formatted_address があります。実際にいくつかの地名や住所で検索した結果得られた formatted_address は下表の通りです。

検索クエリ formatted_address
ディズニーランド 1-1 Maihama, Urayasu, Chiba 279-0031, Japan
千葉県浦安市 Urayasu, Chiba, Japan
ユニバーサル・スタジオ・ジャパン 2 Chome-1-33 Sakurajima, Konohana Ward, Osaka, 554-0031, Japan
大阪府大阪市此花区桜島２丁目１−３３ 2-chōme-1-33 Sakurajima, Konohana-ku, Osaka, 554-0031, Japan

これを見ると、 formatted_address も表記揺れを含んでおり、正確な文法を特定するのが困難です。

  • 都道府県と郵便番号の間にカンマが入る場合と入らない場合がある。
  • 伸ばす音を示すオーバーラインが有る場合と無い場合がある。
  • 同一の場所に対して、複数の僅かに異なる formatted_address が対応する場合がある。

何らかの方法で formatted_address から無理やり都道府県を取得することも考えられますが、より簡単で確実なのは Place Details requests を併用する方法です。すなわち

  1. Find Place requests で place_id を取得
  2. Place Details requests で place_id を検索し、 address_component を取得

ただし、この方法は1つの地名を検索するために2回のAPIコールを用いるため、課金額に特に注意を払う必要があります。

例えば「千葉県」を検索すると以下のような address_component が得られます。 types に administrative_area_level_1 を含む部分が都道府県に関する情報です。

[
    {
        "long_name": "Chiba",
        "short_name": "Chiba",
        "types": [
            "administrative_area_level_1",
            "political"
        ]
    },
    {
        "long_name": "Japan",
        "short_name": "JP",
        "types": [
            "country",
            "political"
        ]
    },
    {
        "long_name": "279-0031",
        "short_name": "279-0031",
        "types": [
            "postal_code"
        ]
    }
]

Python Client for Google Maps Services

Google Maps APIを簡単に叩けるPythonライブラリが公式に提供されています。各エンドポイントとライブラリのメソッドの対応関係は下表の通りです。

エンドポイント Python Clientのメソッド
Find Place requests googleMaps.Client.find_place
Text Search requests googleMaps.Client.places
Places Details requests googleMaps.Client.place

メソッド名が非常に紛らわしいので、誤って Text Search requests (googleMaps.Client.places) を使わないように注意してください（自戒）。

古いSteamアカウントを乗っ取られかけた話

セキュリティ

経緯

一昨年のある日、Steamから以下のようなメールが届きました。

Dear {ユーザー名},

Here is the Steam Guard code you need to login to account {ユーザー名}: {Steam Guard コード}

This email was generated because of a login attempt from a web or mobile device located at 60.179.231.135 (CN). The login attempt included your correct account name and password.

The Steam Guard code is required to complete the login. No one can access your account without also accessing this email.

If you are not attempting to login then please change your Steam password, and consider changing your email password as well to ensure your account security.

新しい端末からSteamにログインしようとすると送られてくる恒例のメールです。ただし上記のメールで通常と明らかに違うのは、ログイン元として中国のIPアドレスが記載されていることです。当時中国に渡航した経験は無く、このログインは明らかに身に覚えのないものでした。そのため、攻撃者が私のSteamのユーザー名とパスワードを何らかの手段で入手しログインを試みた、としか考えられません。

その後すぐに、パスワード管理ソフトを使って100文字のランダム文字列を生成し、Steamのパスワードを変更しました。これで安心と思っていたのですが、2ヶ月ほど後にまたSteam Guardのメールが届いたので驚きです。しかも今度は中国、ブラジル、ベネズエラから複数のログイン試行を受けています。

ここで流石におかしいと思い気が付きました。攻撃者がログインを試みていたのは、私が現在使っているSteamアカウントではなく、10年程前に作成して完全に忘れ去っていた別のアカウントだということに。私がパスワードを変更したのは新アカウントの方だったので、旧アカウントへの攻撃が止まらないのは当然です。新旧どちらのアカウントも同じメールアドレスで登録していたことが混乱の原因でした。

パスワードが漏れた原因

過去に起きた情報流出事件のデータを蓄積している、Have I Been Pwnedというサイトがあります。これで調べた結果、あるサイトから私のメールアドレスとパスワード（のSHA1ハッシュ値）が流出していたことがわかりました。

CDProjektRedのアカウントやSteamの旧アカウントを作成したのは私が小学生か中学生くらいの頃です。当時のセキリュティ知識は皆無に等しく、5文字のパスワードを色々なサイトで使い回していました。攻撃者は、流出した私のメールアドレスとパスワードを利用してSteamでもログインを試みたと考えられます。

ネット上を探すと、MD5やSHA1などのハッシュを総当たりでクラックしてルックアップテーブルを公開しているサイトがすぐに見つかります。

パスワードの文字数が短ければ、これらのサイトを使って、ハッシュからパスワードを容易に割り出すことができます。実際に私が使っていた5文字のパスワードもクラック可能でした。

教訓

アカウントハックは他人事ではありません。どんな人でも被害を受ける可能性があります。最低限の対策として、パスワード管理ソフト*1を導入し、各サイトで個別の強力なパスワードを設定するようにしましょう。

*1:Bitwarden、KeePass、LastPass、1Passwordなど