ABC001からABC007までやってみた思い出

AtCoder Biginner Contestの001から007までやってみて学んだことを覚えている限り

ABC001-D 感雨時刻の整理

いもす法というシンプルですごいアルゴリズムを知った。

いもす法 - いもす研 (imos laboratory)

蟻本を買った当時はまだ生まれていなかったアルゴリズムというのもエモい。

ABC003-D AtCoder社の冬

  1. パスカルの三角形を使うと、足し算のみで二項係数を求められることを知った
  2. 剰余演算の分配則

(a+b) \bmod n = ( (a \bmod n) + (b \bmod n)) \bmod n

ABC006-D トランプ挿入ソート

最長増加部分列( Longest Increasing Subsequence)というアルゴリズムを知った。

最長増加部分列(LIS)の長さを求める - Qiita

ABC007-D 禁止された数字

桁DPというアルゴリズムを知った。

桁DP入門 - ペケンペイのブログ

ここまでJavaScriptで解答してきたが、JavaScriptで表現できる整数が53bitまでという問題があり、Kotlinに切り替えた(AtCoderのNodeのバージョンではBigIntegerは使用できない)。

AtCoder Beginners Selectionの問題でつまづいたところ

積本の中に蟻本があるのを見つけたところ、急に競技プログラミングをやってみたくなった。 日本にはAtCoderというプログラミングコンテストサイトがあり、競技プログラミングの練習ができるという。 (蟻本を買ったのは2010年頃だったが当時はなかったかと思う)

親切なことに「AtCoderに登録したけど何をしていいか分からない・・・!」という人に向けて作られた、初心者向け問題集の AtCoder Beginners Selection が用意されている。 さっそく解いてみたところつまづいた。

行末改行問題

ABC049C - 白昼夢 / Daydream で解法はあっているはずと思っていても、一部のテストケースがさっぱり通らない。 諦めて他の人の解法を見ても、やはり間違っていない。

最終的には入力値をtrimすることですべてのテストケースが通るようになった。 行末が改行で終わっているテストケースとそうでないテストケースがあるのだろうか。

問題文をよく読め問題

ABC086C - Traveling も解法については問題ないはずだが、まったくテストケースが通らない。 公開されているサンプルのテストケースすら通らない。

1日経って気がついた。

求められている出力値は Yes あるいは No だが、 YES NO で出力しているのが問題だった。

言い訳させていただくと、一つ前の問題で求められている出力値が YES NO だったから……。

'Deploy to Heroku' Buttonで、Dockerイメージを利用してDeploy

'Deploy to Heroku' Buttonを使った際に、Dockerイメージを利用してDeployする方法がわかりづらかったのでメモ。

‘Deploy to Heroku’ Button

対象のリポジトリに用意するものは次の3つ。

  • heroku.yml
  • app.json
  • Dockerfile

heroku.yml

最低限の記述は次のような感じ。 ※Node.jsアプリの例

build:
  docker:
    web: Dockerfile
run:
  web: node dist/index.js

app.json

いつものように書けばいいが、stack にはcontainer を指定する。

{
  "name": "kakuyomu feed API",
  "description": "Providing kakuyomu feed API",
  "repository": "https://github.com/bagpack/kakuyomu-feed",
  "keywords": ["node", "kakuyomu", "feed"],
  "stack": "container"
}

このcontainerオプションはドキュメントになぜか書いていない。

Dockerfile

いつものように書く。

リポジトリ

以上を実装したリポジトリがこちらになります。

参考

Docker Builds with heroku.yml (beta) | Heroku Dev Center

Container Registry & Runtime (Docker Deploys) | Heroku Dev Center

暗黙的インテントを使用したときに選択されたアプリを知る

暗黙的インテントを使用したときにユーザがどのアプリを選択するか知るにはどうすればいいのか調査しました。 結論からいうと、Android 5.1以上から追加された次のAPIを利用することで、どのアプリを選択したかBroadcastReceiverで受け取ることができます。

public static Intent createChooser (Intent target, 
                CharSequence title, 
                IntentSender sender)

第三引数のIntentSenderはどうやって作るのかですが、PendingIntentgetIntentSender()というメソッドが用意されており、PendingIntentから取得するようです。

全体の流れは次になります。

  1. 選択された結果を受け取るためのBroadcastReceiverを用意する
  2. 受信先に1を指定したPendingIntentを用意する
  3. 発行したい暗黙的Intentを用意する
  4. 3のcreateChooserから取得したIntentをstartActivityに渡す

選択された結果を受け取るためのBroadcastReceiverを用意する

選択された結果を受け取るためのBroadcastReceiverを用意します。

class ChooseReceiver : BroadcastReceiver() {

  override fun onReceive(
    context: Context,
    intent: Intent
  ) {
    val componentName = intent.extras.get(EXTRA_CHOSEN_COMPONENT) as ComponentName
  }
}

manifestに追加することを忘れないようにします。

<receiver android:name="ChooseReceiver" android:exported="false"/>

受信先にさきほど作成したReceiverを指定したPendingIntentを用意する

val receiver = Intent(context, ChooseReceiver::class.java)
val pendingIntent = PendingIntent.getBroadcast(context, 0, receiver, PendingIntent.FLAG_UPDATE_CURRENT)

発行したい暗黙的Intentを用意する

お好きな暗黙的Intentをご用意ください。

val share = Intent()
share.action = Intent.ACTION_SEND
share.type = "text/plain"
share.putExtra(
    Intent.EXTRA_TEXT,
    "テキスト"
)

createChooserから取得したIntentをstartActivityに渡す

    startActivity(Intent.createChooser(share
        , "タイトル"
        , pendingIntent.intentSender
    ))

以上です。

参考

Get results from Android Chooser – Code With Lisa – Medium

WISPrのSmart Clientを実装する

WISPrとは?

Wi-Fi based Wireless Internet Service Provider(WISP)のローミングについてのベストプラクティスです。 あくまでも、RFCのような標準ではなくベストプラクティスだそうです。

具体的には?

次のようなケースで使われています。

  1. 公衆無線LANに接続する
  2. 任意のURLにアクセスする
  3. ログインページ(Captive Portal)が表示される

このとき、Captive PortalのHTMLには次のようなXMLが埋め込まれています。

<?xml version="1.0" encoding="UTF-8"?>
<WISPAccessGatewayParam
xmlns:xsi=http://www.w3.org/2001/XMLSchema-instance
xsi:noNamespaceSchemaLocation="http://www.acmewisp.com/WISPAccessGatewa
yParam.xsd">
Alliance Wireless ISP Roaming

<Redirect>
<AccessProcedure>1.0</AccessProcedure>
<AccessLocation>12</AccessLocation>
<LocationName>
ACMEWISP,Gate_14_Terminal_C_of_Newark_Airport
</LocationName>
<LoginURL>http://www.acmewisp.com/login/</LoginURL>
<AbortLoginURL>
http://www.acmewisp.com/abortlogin/
</AbortLoginURL>
<MessageType>100</MessageType>
<ResponseCode>0</ResponseCode>
</Redirect>
</WISPAccessGatewayParam>

このXMLWISPrの仕様の一部です。

Smart Clientとは?

上記XMLを使ったやりとりを利用して、自動ログインの方法を提供することで、ユーザーの利便性を向上しようというのがSmart Clientになります。

WIPr 1.0の仕様書はなかなか読みづらいですが、Smart Clientを実装するだけであれば、Appendix D以降を読むだけで大丈夫です。 次にSmart Clientを実装するのに必要な情報をまとめました。

Smart Clientの実装

基本的な流れは次のとおりです。

  1. 任意のURLにGETリクエストを投げる
  2. (ログイン済みでなければ)ログインURLにリダイレクトされる
  3. ログインURLが返すHTML内にXMLが埋め込まれているので、XMLの内容にしたがって認証情報のリクエストを行う

フルスペックで実装するには次の1〜5の手続きを実装すればよさそうです。

  1. Login Request: Successful Case
  2. Login Request: Successful Case With プロキシ Reply
  3. Login Request: Successful Case With Polling
  4. Login Request: Reject
  5. Login Request: Reject With Polling

Login Request: Successful Case

ログイン正常系。 おそらく、日本の公衆無線LANの場合はこれを実装しておけばほとんどこと足りそう。

XMLのサンプル

 <?xml version="1.0" encoding="UTF-8"?>
 <WISPAccessGatewayParam
 xmlns:xsi=”http://www.w3.org/2001/XMLSchema-instance”
 xsi:noNamespaceSchemaLocation="http://www.acmewisp.com/WISPAccessGatewa
 yParam.xsd">
 <Redirect>
 <AccessProcedure>1.0</AccessProcedure>
 <AccessLocation>12</AccessLocation>
 <LocationName>
 ACMEWISP,Gate_14_Terminal_C_of_Newark_Airport
 </LocationName>
 <LoginURL>http://www.acmewisp.com/login/</LoginURL>
 <AbortLoginURL>
 http://www.acmewisp.com/abortlogin/
 </AbortLoginURL>
 <MessageType>100</MessageType>
 <ResponseCode>0</ResponseCode>
 </Redirect>
 </WISPAccessGatewayParam>

資格情報

次のパラメータをapplication/x-www-form-urulencoded形式で送信する。

パラメータ名 説明
UserName ユーザー名 example@domain
Pasword パスワード abcdefgh-123456
button ボタン(固定値) Login
FNAME フォーム名(固定値) 0
OriginatingServer もともとアクセスしようとしていた先のURL https://www.google.co.jp

Login Request: Successful Case With プロキシ Reply

Proxy Reply が返ってくるケース。 NextURLを挟んではいるが基本はLogin Request: Successful Caseと一緒。

XMLのサンプル

<?xml version="1.0" encoding="UTF-8"?>
<WISPAccessGatewayParam
xmlns:xsi=”http://www.w3.org/2001/XMLSchema-instance”
xsi:noNamespaceSchemaLocation=
"http://www.acmewisp.com/WISPAccessGatewayParam.xsd">
<Proxy>
<MessageType>110</MessageType>
<NextURL>http://www.acmewisp.com/proxypoll</NextURL>
<ResponseCode>200</ResponseCode>
<Delay>5</Delay>
</Proxy>
</WISPAccessGatewayParam>

Login Request: Successful Case With Polling

即座に認証結果が返されずポーリングすることを要求されるケース。 Polling URLはレスポンスにLoginResultsURL が含まれていればLoginResultsURLを使用する。 含まれていなければLoginURLを使用する。

XMLのサンプル

<?xml version="1.0" encoding="UTF-8"?>
<WISPAccessGatewayParam
xmlns:xsi=http://www.w3.org/2001/XMLSchema-instance
xsi:noNamespaceSchemaLocation="http://www.acmewisp.com/WISPAccessGate
wayParam.xsd">
<AuthenticationPollReply>
<MessageType>140</MessageType>
<ResponseCode>201</ResponseCode>
<ReplyMessage>Authentication Pending</ReplyMessage>
<Delay>5</Delay>
<LoginResultsURL>http://wi2net/RLogin/1/</LoginResultsURL>
<LogoffURL>http://www.acmewisp.com/logoff/</LogoffURL>
</AuthenticationPollReply>
</WISPAccessGatewayParam>

Login Request: Reject

資格情報を送ったがログイン失敗するケース。

XMLのサンプル

<?xml version="1.0" encoding="UTF-8"?>
<WISPAccessGatewayParam
xmlns:xsi=http://www.w3.org/2001/XMLSchema-instance
xsi:noNamespaceSchemaLocation="http://www.acmewisp.com/WISPAccessGate
wayParam.xsd">
<AuthenticationReply>
<MessageType>120</MessageType>
<ResponseCode>100</ResponseCode>
<ReplyMessage>Invalid Password</ReplyMessage>
<LoginResultsURL>
http://www.acmewisp.com/loginresults/
</LoginResultsURL>
<LogoffURL>http://www.acmewisp.com/logoff/</LogoffURL>
</AuthenticationReply>
</WISPAccessGatewayParam>

Login Request: Reject With Polling

即座に認証結果が返されずポーリングすることを要求されて、ポーリングを繰り返すが、最終的にログイン失敗するケース。

リポジトリ

以上をSwiftで実装したのが次のリポジトリです。

Q&A

  • WISPrで使うユーザー名とパスワードはどうやって入手するの?

存じ上げません。

参考資料

Microsoft Word - WISPr-2003Jan.doc

wichert/wispr: Commandline WISPr client

iOS 9.0でSVGにtext-shadowのカンマ区切り記法を適用すると描画がおかしい問題

2018年にもなってiOS 9.0の記事を書くのはどうかしている感がありますね。

概要

iOS 9.0でSVGのTEXTタグにCSSでtext-shadowをカンマ区切りで複数適用すると、本来描画される文字列の下の方にもうひとつ文字列が描画されてしまうwebkitの不具合があります。

text-shadowをカンマ区切りで指定。

    .text-shadow {
      text-shadow: -2px -2px 0 #F00, 2px 2px 0 #F00;
    }

文字列が二重に表示される。

対策

下記のいずれかの対策がおすすめです。

  1. iOS 9を対象外にする
  2. SVGを使わない選択肢を考える
  3. text-shadowのカンマ区切りを使ったスタイルを諦める

しかし、何らかのしがらみでどうしても上記の対策を取れない場合は次のような対策方法があります。

  • 文字列を重ねて表示して、それぞれに別のtext-shadowを適用する
    <svg xmlns="http://www.w3.org/2000/svg"
         width="500" height="200" viewBox="0 0 500 40">
      <text x="0" y="35" font-size="35" class="text-shadow-1">
        Lower
      </text>
      <text x="0" y="35" font-size="35" class="text-shadow-2">
        Lower
      </text>
    </svg>

この方法には、セマンティックが壊れるという欠点があるので注意して使用する必要があります。

再現コード

下記は再現コードです。

JS Bin on jsbin.com

参考

webkitの類似バグ

https://bugs.webkit.org/show_bug.cgi?id=111216 https://bugs.webkit.org/show_bug.cgi?id=139810

NEHotspotHelperでAuthenticatingにフックする

NEHotspotHelperの情報は、開発に使用するのにも申請が必須というハードルの高さからか情報が少ない。 そんな中で貴重な情報源の次のページを参考にNEHotspotHelperを使ってみるとはまるケースがある。

[iOS] Wi-Fi一覧でアピール表示し、パスワードを自動入力して接続させる方法(とまとレストランの販売促進アプリ) | Developers.IO

はまったケース

f:id:bagpack:20170707104434p:plainApple Inc. online: Authentication State Machine

上図のAuthenticatingMaintainingの処理にフックしたい場合に、参考コードに処理を付け加える形で書くと、kNEHotspotHelperCommandTypeAuthenticateがいつまでも呼ばれない。 というのは、下記のコードをよくよく読んでみると、

    NSDictionary *options = [NSDictionary dictionaryWithObjectsAndKeys:@"🍅🍅🍅とまとレストラン🍅🍅🍅", kNEHotspotHelperOptionDisplayName, nil];
    dispatch_queue_t queue = dispatch_get_main_queue();
    BOOL isAvailable = [NEHotspotHelper registerWithOptions:options queue:queue handler: ^(NEHotspotHelperCommand * cmd) {
        NSMutableArray *hotspotList = [NSMutableArray new];
 
        if(cmd.commandType == kNEHotspotHelperCommandTypeEvaluate || cmd.commandType == kNEHotspotHelperCommandTypeFilterScanList) {
            for (NEHotspotNetwork* network  in cmd.networkList) {
                NSLog(@">%@", network.SSID);
                if ([network.SSID isEqualToString:@"spw05"]) {
                    [network setConfidence:kNEHotspotHelperConfidenceHigh];
                    [network setPassword:@"password"];
                    [hotspotList addObject:network];
                }
            }
            NEHotspotHelperResponse *response = [cmd createResponse:kNEHotspotHelperResultSuccess];
            [response setNetworkList:hotspotList];
            [response deliver];
        }
    }];

[Developers.IO online: [iOS] Wi-Fi一覧でアピール表示し、パスワードを自動入力して接続させる方法(とまとレストランの販売促進アプリ) | Developers.IO]

kNEHotspotHelperCommandTypeEvaluateのときはcmd.networkListにはnilが入ってくるので、setNetworkListで空リストがセットされている。 そのため、対象のNetworkがNEHotspotHelperの管理対象から外れて、kNEHotspotHelperCommandTypeEvaluate以降のkNEHotspotHelperCommandTypeAuthenticateなどのコマンドが送られない状態となっている。

kNEHotspotHelperCommandTypeAuthenticateが呼ばれるために必要なこと

フォーラムの次の回答によると、

NEHotspotHelper (NetworkExtension iOS9.0) Sampl... | Apple Developer Forums

kNEHotspotHelperCommandTypeEvaluateのときに下記の処理をすればAuthenticatingステートが呼ばれるらしい。

  • コマンドからレスポンスを作製する(NEHotspotHelperResponse *response = [cmd createResponse:kNEHotspotHelperResultSuccess])
  • コマンドからnetworkを取得する(NENetwork *network = cmd.network)
  • networkにconfidenceを設定する(setConfidence)
  • レスポンスにnetworkを追加する(setNetwork)
  • レスポンスを配達する( [response deliver])

サンプルコード

以上を踏まえて、次のようなコードを書いてみると(ついでにSwift3に書き換え)、確かにauthenticateが呼ばれるようになった。 よかったです。

        let options : [String: NSString] = [
            kNEHotspotHelperOptionDisplayName: "🍅🍅🍅とまとレストラン🍅🍅🍅"
        ]
        
        let isAvailable = NEHotspotHelper.register(options: options, queue: DispatchQueue.main) { (cmd) in
            
            print(cmd)
            
            switch cmd.commandType {
            case .filterScanList:
                let list = cmd.networkList
                var networks = [NEHotspotNetwork]()
                for network in list! {
                    if network.ssid == "spw05" {
                        network.setPassword("password")
                        network.setConfidence(.high)
                        networks.append(network)
                    }
                }
                let response = cmd.createResponse(.success)
                response.setNetworkList(networks)
                response.deliver()
            case .evaluate:
                let network = cmd.network!
                let response = cmd.createResponse(.success)
                network.setConfidence(.high)
                response.setNetwork(network)
                response.deliver()
            case .authenticate:
                let network = cmd.network!
                let response = cmd.createResponse(.success)
                response.setNetwork(network)
                response.deliver()
            case .maintain:
                let network = cmd.network!
                let response = cmd.createResponse(.success)
                response.setNetwork(network)
                response.deliver()
            case .none:
                // anycode
                break
            case .presentUI:
                // anycode
                break
            case .logoff:
                // anycode
                break
            }
            
        }