トモロログ

仕事や趣味でのメモや記録など

ABC169 問題D [asarenメモ] #幅優先(BFS)基本

Atcoder Begginer Contest 169 でのキューを使った幅優先探索のメモ

atcoder.jp

import os, sys, re, math
from collections import deque

N,M = map(int, input().split(' '))

tag = [-1] * N
path_r = {}

for _ in range(M):
    A,B = map(lambda x: int(x) - 1, input().split(' '))
    if A in path_r:
        path_r[A].append(B)
    else:
        path_r[A] = [B]
    if B in path_r:
        path_r[B].append(A)
    else:
        path_r[B] = [A]

tag[0] = 0
queue = deque()
queue.append(0)

while queue:
    next_r = queue.popleft()
    for t in path_r[next_r]:
        if tag[t] < 0:
            tag[t] = next_r
            queue.append(t)

if -1 in tag:
    print('No')
else:
    print('Yes')
    for t in tag[1:]:
        print(t+1)

※asarenとは自主的な競技プログラミング練習会のことです

ABC165 問題C [asarenメモ] #深さ優先

atcoder.jp

問題文にある階段状に増加する数列の全パターンの生成数は

N+M-1 Combination N 通り で最大見積もりは 19 C 10 = 92738 通り

なので全生成してからスコア計算で対応可能。

全生成の方法は深さ優先探索(DFS)で生成可能。以下pythonでの回答例。

N,M,Q = map(int,input().split(' '))

ret = 0
question = []

for _ in range(Q):
    t = list(map(int,input().split(' ')))
    question.append(t)

def score(A):
    ans = 0
    for q in question:
        if (A[q[1]] - A[q[0]] == q[2]):
            ans += q[3]
    return ans

def dfs(A):
    tail = A[-1]
    if len(A) > N:
        global ret
        cur = score(A)
        ret = max(ret, cur)
        return
    for i in range(M-tail+1):
        dfs(A+[tail+i])

dfs([1])
print(ret)

意外にはまったのが ret変数を関数内でglobal宣言するところ。。まだ甘い。。 しかしこの回のCは難しかった。。

※asarenとは自主的な競技プログラミング練習会 atcoder上の組織でも見れますよ

Selenium + python で xpathで要素を見つけるときの存在チェック

Selenium + pythonについての話題。

xpathを用いて要素を見つけるときに find_element_by_xpath をやった場合、その対象の要素がないとき にexceptionが発生してしまう。

driver.find_element_by_xpath('hogehoge')

事前に存在チェックがないので以下のようにtry & except で行うのもよいけど、

try:
  driver.find_element_by_xpath('hogehoge')
except:
  #エラー処理

find_elements_by_xpath (複数形!)を使うとエラーにならず空の配列を返すのでそれを利用すると簡単に処理できる。

hoge = driver.find_elements_by_xpath('hogehoge')
if hoge:
  print(hoge[0]) // 要素が1つの時は0番目

xpathだけでなくほかのメソッドでも同様。

Laravel の twitter Oauthの設定

現在G's Academy というプログラミング学校に週末通っており、そこでPHPフレームワークLaravelを利用しています。

Laravelは認証系の仕組みがコマンド打つだけであっという間にできてしまい楽勝だったので、色気を出してtwitterOauth認証に手を出してハマってしまいました。 その時のメモです。

twitter API

まずはTwitterAPIキーを取得するために公式サイトでの設定が必要です。

https://apps.twitter.com/

Laravel Socialiteを使っています。

公式URL Laravel Socialite - Laravel - The PHP Framework For Web Artisans

参考URL

https://php-junkie.net/framework/laravel/socialite/ https://qiita.com/KeisukeKudo/items/18dd8a342a4bdd43913c

他にも ' laravel socialite twitter 認証' などでググると結構情報は出てきます。

インストールと初期設定

まずはsocialiteをインストールします。コンソールにて

>composer require laravel/socialite

twitter developersにて取得したAPIキー等は.envに記載

TWITTER_API_KEY = ''; //Consumer Key (API Key)
TWITTER_API_SECRET = ''; //Consumer Secret (API Secret)
TWITTER_CALLBACK_URL= 'http://xxxxxx' 
TWITTER_ACCESS_TOKEN = "";
TWITTER_ACCESS_TOKEN_SECRET = "";

上記は全てtwitter developersで取得した値と一致する必要があります。callback_urlは自身でせってしなければなりませんが、とりあえずは localhost 指定でも大丈夫なのでログイン後に遷移する先のルーティングを指定してください。

続いてconfig/services.phptwitter APIのキー設定を追記。これでモジュール内で.env内から具体的な値にアクセスすることができるようになります。

'twitter' => [
        'client_id'     => env('TWITTER_API_KEY'),
        'client_secret' => env('TWITTER_API_SECRET'),
        'redirect'      => env('TWITTER_CALLBACKURL'),
    ],

 モジュールの設定

twitterのログイン認証を行う実行先のルーティングを指定します。
web.phpにルート情報を追加します。下記は私の例ですので任意のルーティングで大丈夫です。以下自身の設定に合わせて読んでください。

Route::get('login/twitter', 'Auth\LoginController@redirectToTwitterProvider');
Route::get('login/twitter/callback', 'Auth\LoginController@handleTwitterCallback');

app/http/Controllers/Auth/LoginController.php にメソッド追加

use Laravel\Socialite\Facades\Socialite;

// 途中略

public function redirectToTwitterProvider() {
       return Socialite::driver('twitter')->redirect();
}

config/app.php の該当箇所に以下を追加

'providers' => [
    // これを追加
    Laravel\Socialite\SocialiteServiceProvider::class,


'aliases' => [
  // これを追加
  'Socialite' => Laravel\Socialite\Facades\Socialite::class,

以上の設定で /login/twitter のルートにアクセスすると自動的にtwitterの認証画面に遷移します。
そしてそこでログイン処理をすると上記で設定したcallback先に自動的に遷移します。素晴らしい。

 ユーザ情報の取得&ハマりポイント

ログイン処理後twitterからユーザ情報を取得します。一応公式や参考URLには

$user = Socialite::driver("twitter")->user(); 

で取得できるとありますが、何度やってもエラーになります。ここで結構ハマってしまいました。

※補足:その後サーバにデプロイしたケースでは上記の取り方でうまく行きました。エラーはローカル環境の時だけ起こることがわかりました。

他のSNSgoogle経由では大丈夫みたいですが、twitterはうまく行きませんでした。
そこでエラーの発生場所のソースコードを見てみると原因は SocialiteのAbstractProvider.php 内にありました。

protected function hasNecessaryVerifier()
    {
        return $this->request->has('oauth_token') && $this->request->has('oauth_verifier');
    }

原因はrequest に auth_token, oauth_verifier が設定されていないからのようです。
本来ならcallbackしてきたあとで自動で設定されるはずのようなのですがうまくいかずのようです。しかしこちらではすでに上記の情報は既知であるので、 直接代入して設定することにしました。

$token = env('TWITTER_ACCESS_TOKEN');
$secret = env('TWITTER_ACCESS_TOKEN_SECRET');

$user = Socialite::driver('twitter')->userFromTokenAndSecret($token, $secret);

Laravel Socialite公式にトークン等の設定する値が分かっている場合は上記のように設定しましょうとの説明がありました。

Laravel Socialite - Laravel - The PHP Framework For Web Artisans
Socialiteを使ってLaravelでTwitterログイン機能を実装 - Qiita

これでユーザ情報を取得できるはずです。しかし!
このようにしてtwitterからユーザ情報を取得した際に、emailが取れていないかもしれません。それはtwitter api の設定時にprivacy policy とterms_of_service のURLを設定していないからです。
それらを設定すればemail取得の許可の設定チェックボックスが表示され、それをオンに設定すればメール情報を取得することができます。以下参考。

omniauth-twitterでemail情報を取得する - Qiita

ユーザ情報の登録

twitterからログインしてきたユーザが新規であった場合は取得したユーザ情報をデータベースに登録します。 基本ユーザはemailでユニークにしたい。そしてtwitter経由登録の場合はパスワード無しになるのでusersテーブルのpasswordはnullableに変更する必要があります。

そこでUsersテーブルのpasswordをnullableに変更するためmigration

> php artisan make:migration change_password_users_table

migrationファイルの中

public function up()
    {
        Schema::table('users', function (Blueprint $table) {
            //passwordカラムにnullを許可
            $table->string('password')->nullable()->change();
        });
    }

    /**
     * Reverse the migrations.
     *
     * @return void
     */
    public function down()
    {
        Schema::table('users', function (Blueprint $table) {
            $table->string('password')->nullable(false)->change();
        });
    }

migrationの実行

>php artisan migrate

migrationでテーブルのカラム変更が初めての場合はエラーになるので、以下をインストールしてからmigrateを再実行しましょう。

> composer require doctrine/dbal

基本的にはメールアドレスでユーザの判断をしますが、twitter id も併用するように私はしました。
理由はtwitterに紐づいたemailが変更された時を考えてのことです。(あらゆるケースを想定しだすと何がベストか迷いますが、ひとまずそのように判断)。

その為にUserテーブルにtwitter_id に対応したカラムを追加しました。これは通常のmigrationで対応可能。

そして実際にデータベースの更新をしますが、Userのデータベース更新メソッドは特殊なようです。
単純に User::find や User::where で取得したオブジェクトに対してsaveメソッドを実行してもエラーになります(メソッドがないと怒られます)。
一旦ログイン操作をしてからfindやwhereするとうまくいきます。

$user = User::where('twitter_id', twitter_idの何か)->get();
$user->email = xxx@yyy.com; // 取得したemailの設定

 // ダメなパターン
$user->save(); // このままではエラーになる 

// good!
Auth::login($user); // これをやってから
$user->save();  // saveがうまくいった

ちなみに上記処理をLoginControllerでやっている場合はAuthを呼び出しているか注意(下記)。

use Illuminate\Support\Facades\Auth;
use App\User;

上記のsave方法以外にUserには、firstOrCreate メソッドがあり、これは上記のlogin操作なしでも使えます。
このメソッドでは、第一引数で検索して見つかればselect 、なければ第二引数と合わせてcreateし、Userのオブジェクトを返します。

$user = User::firstOrCreate(
 ['email'=> $user_info->email], // これで検索 第一引数 あれば$userに検索結果を返す
 ['name' => $user_info->name, 'twitter_id'=>$user_info->id,
                'img_url'=>$user_info->avatar]); // 第一引数で存在しなければこれも合わせてcreateし、新たなユーザを$userに返す

Auth::login($user); // その後の操作用にログイン

以上で一通り完了。あとは通常ログインユーザと同様に動くはずです。お疲れ様でした。

python入門第1回終了

知財の人のためのpython入門の第1回を開催しました。

7名の方に参加いただき盛況でした。

写真載せたかったですがその後の飲み会のものしかなかったので次回取ってアップロードしたいと思います。

 

 内容はデータ型、for, if, whle などの制御文が中心で基本的な内容でしたが、説明するといろいろ項目が多く、2時間を予定していましたが少しオーバーして終わりました。参加者のプログラミング経験にばらつきがありましたが演習問題を多めにかつ難易度も易からやや難までそろえていたのでそれぞれが楽しめたようです。

 参加者の方からは今日やった内容で特許の実務に役立つイメージがわかないという話がありましたが、現状では文字列処理、ファイル操作もまだなので仕方ないのかなとは思います。その段階になればサンプルとしてこのサイトかpython用のサイト(こちら)

にアップしたいと思います。

 次回は12/17を予定しています。引き続き続けていきたいと思います。

知財の人のためのPython サイト

先日募集していた「知財の人のためのPython入門」にあわせてサイトを立ち上げました。

講座の内容やそれに関する情報を残していこうと思います。

 

知財の人のためのPythonサイト

f:id:tomoro_azu:20181118210542p:plain

「一発リンクトモロヲ君」の思い出

「退屈なことはpythonにやらせよう」のまえがきに筆者の友人の経験談についての話があった。

 その友人は大学時代、家電量販店で他店と自店舗の価格比較を紙ベースで突き合わせて比較し、競合店の方が安い商品をピックアップするという作業をしていた。そしてその作業に丸2日かかっていた。そして別の友人からの助言でデータを処理するプログラムを数時間で作成し、作業は数秒になった。とのこと。

 

 これを読んで自分が特許業界に入ったすぐの時のことを思い出した。まだ何も業界のこともわからず右往左往しながらときに手を持て余すこともあった。そんな時アルバイトの人がエクセルで何か一生懸命作業しているので聞いてみると、公報のPDFにハイパーリンクを張っているとのこと。その件数3000件。その2か月前までプログラマだった私は衝撃を受け「なにをしとるんじゃ~」と思い、そして自分でもこれなら役に立てると思い、上司にその仕事を引き受けさせてほしいと願い出た。そしてまったくエクセルのVBAを触ったことはなかったが、ネットで調べながら自動的にリンクを作成するマクロを作成した。作業は数秒になった。

 意外に他の同僚にも好評で配布することになり、ファイル名を「一発リンクトモロヲ君」と名付けて配布し、自身が退職するときにもファイルは配布していたのでそのまま残った。

 

 それから十数年後のつい先週(上記の書籍を買う数日前)に特許情報フェアで当時の同僚(今もその会社にいる人)に偶然会った。久しぶりなのでちょっとお茶でもと誘って話していると他の同僚だけど私が退職後に入社した、会ったことのない方が合流した。するとその方が「あのトモロヲ君の作者ですか~、お世話になってます!」というではないか。なんとまだ現役で使われているらしい。なんか恥ずかしいやらおかしいやらいろんなことを思ったが話は盛り上がった。一番おかしかったのが「名前にインパクトがあって忘れない」ということだった(ファイル名変えてないんかい!とは思った)。

 どうやら私が手を持て余して作ったトモロヲ君は私のいないところで多くの「退屈なこと」をやったらしい。

 

 で、そのインパクトのある名前も当時は「またまたふざけて~」「サムい」などいろいろ言われたのだけど結構思い入れがありまして。

 その昔プログラマ時代にとっても火を噴いているプロジェクトがあって、時間的にも肉体的にも限界に近い状況。あるときデータベースの処理に皆困っていて、プロジェクト側の身内で使うツールが必要となったものの、だれも手を出せない状況。そんな中、一番忙しいはずのリーダーから「たまにはプログラムしたくてね~、こんなんつくちゃったよ」とエクセルVBAで作ったファイルが配布された。その出来は素晴らしく、そしてどこにそんな時間が?わずかしかない自分の時間を皆のために使ったのではと驚いた。そしてそのファイル名は皆に気を使わせないようにしたのか真意は定かではないが「一発タナカ君」。

 その精神を少しでも受け継げたらと思って特許業界新人のときに思って付けた(パクった)ファイル名なのだった。

 

 あれから十数年。自分で使うことはないがその気持ちを忘れないようにと「一発リンクトモロヲ君」はPCを買い替えても中に置くことにしている。そして一人会社となった今、手助けする同僚はいない。

 

トモロヲ君の画面紹介

 デザインはいまいち。。ほしい人がいたら許可もらって配布しようかな。

f:id:tomoro_azu:20181116101408j:plain

 正規表現を使ってファイル名のパターンを自由に定義できるように対応

 どのデータベースのファイルでも外国の公報でも対応できる。

f:id:tomoro_azu:20181116101503j:plain