野次馬エンジニア道

野次馬な気持ちでプログラミングをあれこれと綴ります

IKEA TRÅDFRIをZigbeeでGoogle Home から操作

のエントリでIKEA TRÅDFRIをThings Gatewayから操作できるようになった。

せっかくなので

  • OK Google ダイニングのライトをつけて
  • OK Google ダイニングのライトを消して
  • OK Google ダイニングを60%の明るさにして

こんな感じでGoogle Home経由で操作できるようにする。

IKEA TRÅDFRIのファクトリーリセットからメッシュのネットワークの構築まではThings Gatewayに任せて、 Google HomeのIFTTTが設定してある既存Raspberry PiXbeeのドングルを差し替える。

f:id:notta55:20180506080136j:plain:w400

流れとしては、

という感じ。

前準備 : 操作可能な機能の調査

Things Gatewayのログ*1を見ながら、デバイスの情報を調べてみる。

ZDOのSimple Descriptor Resp

ZDOとはネットワークを管理している共通のZigBee Device Profile ( ProfileID:0x0000 ) のエンドポイントのこと。 詳しくはこちら

Rcvd: Explicit Rx 90fdxxxxxxxxxxxxxxxxxx ZDO 8004 Simple Descriptor Resp (0x8004) status: success (0)
Rcvd: { 
    type: 145,
    remote64: '90fdxxxxxxxxxxxxxxxxxx',
    remote16: '2637',
    sourceEndpoint: '00',
    destinationEndpoint: '00',
    clusterId: '8004',
    profileId: '0000',
    receiveOptions: 1,
    data: <Buffer 05 00 37 26 22 01 5e c0 20 02 02 09 00 00 03 00 04 00 05 00 06 00 08 00 00 03 05 0b 00 10 04 05 00 19 00 20 00 00 10>,
    zdoSeq: 5,
    status: 0,
    zdoAddr16: '2637',
    simpleDescriptorLength: 34,
    endpoint: 1,
    appProfileId: 'c05e',
    appDeviceId: '0220',
    appDeviceVersion: 2,
    inputClusterCount: 9,
    inputClusters: [ '0000','0003','0004','0005','0006','0008','0300','0b05', '1000' ],
    outputClusterCount: 4,
    outputClusters: [ '0005', '0019', '0020', '1000' ] }

ここからIKEA TRÅDFRI がどんなデバイスなのかが分かる。

Field ID
profileId c05e ZigBee Light Link Profile
appDeviceId 0220 Lighting devicesのColor temperature light
Input Cluster Basic(0000), Identity(0003), Groups(0004), Scene(0005), On/off(0006), LevelControl(0008), Color control(0300), Diagnostics(0b05), ZLL commissioning(1000)
output Cluster Scene(0005), OTA Upgrade ? (0019), PollControll(0020), ZLL commissioning(1000)

ZCL - ColorCapabilities

続いてZigbee Cluster Libraryの値を見てみる。

Rcvd: Explicit Rx 90fdxxxxxxxxxxxxxxxxxx ZHA 0300 lightingColorCtrl readRsp [ { attrId: 400A, status: 0, dataType: 25, attrData: 16 } ]
Rcvd: { 
    type: 145,
    remote64: '90fdxxxxxxxxxxxxxxxxxx',
    remote16: '2637',
    sourceEndpoint: '01',
    destinationEndpoint: '00',
    clusterId: '0300',
    profileId: '0104',
    receiveOptions: 1,
    data: <Buffer 18 06 01 0a 40 00 19 10 00>,
    zcl: 
    { frameCntl: { frameType: 0, manufSpec: 0, direction: 1, disDefaultRsp: 1 },
      manufCode: 0,
      seqNum: 6,
      cmdId: 'readRsp',
    payload: [ { attrId: 400A, status: 0, dataType: 25, attrData: 16 } ] } }
Field ID
clusterId 0300 Color Control
attrId 400A ColorCapabilities

dataTypeはbitmap(=16)。これはビット番号でサポートしている機能を表すようで、

  • 0: Hue/saturation supported, 1: Enhanced hue supported, 2: Color loop supported, 3: XY attributes supported, 4: Color temperature supported
  • 16=10000なので、Color temperatureのみのサポートとなっている*2

On/Offとレベルコントロールの実装

今回は、On/Off ( 0006 ) とレベルコントロール ( 0008 ) をサクッと実装。ZCLのIDやバイナリ部分の構築は

github.com

github.com

を使う。最低限のコードは下記となる。

const zcl = require('zcl-packet');
const zclId = require('zcl-id');
const xbee_api = require('xbee-api');
const C = xbee_api.constants;
const xbeeAPI = new xbee_api.XBeeAPI({api_mode: 1});

const ZHA_PROFILE_ID = toHex(zclId.profile('HA').value); //0104
const CLUSTER_ID_GENONOFF = toHex(zclId.cluster('genOnOff').value); //0006
const CLUSTER_ID_GENLEVELCTRL = toHex(zclId.cluster('genLevelCtrl').value); //0008
function toHex(v) { return ('0000' + v.toString(16)).substr(-4); }

function buildZclFrame(addr64, addr16, endpoint, profileId, clusterId, zclData) {

    checkAndFillProps(zclData);

    let frame = {
        id: xbee_api._frame_builder.nextFrameId(),
        type: C.FRAME_TYPE.EXPLICIT_ADDRESSING_ZIGBEE_COMMAND_FRAME,
        destination64: addr64,
        destination16: addr16,
        sourceEndpoint: 0,
        destinationEndpoint: endpoint,
        profileId: profileId,
        clusterId: clusterId,
        broadcastRadius: 0,
        options: 0,
        zcl: zclData,
    };
    frame.data = zcl.frame(zclData.frameCntl,
        zclData.manufCode,
        frame.id,
        zclData.cmd,
        zclData.payload,
        clusterId);
    return frame;
}

function checkAndFillProps(zclData){
    if (!zclData.frameCntl) {
        zclData.frameCntl = {frameType: 0};
    }
    if (zclData.frameCntl.manufSpec === undefined) {
        zclData.frameCntl.manufSpec = 0;
    }
    if (zclData.frameCntl.direction === undefined) {
        zclData.frameCntl.direction = 0;
    }
    if (zclData.frameCntl.disDefaultRsp === undefined) {
        zclData.frameCntl.disDefaultRsp = 0;
    }
    if (zclData.manufCode === undefined) {
        zclData.manufCode = 0;
    }
    if (zclData.payload === undefined) {
        zclData.payload = [];
    }
}

function makeOnOffValueProps(propertyValue) {
    let attr = propertyValue ? 'on' : 'off';
    return {
        frameCntl: {frameType: 1},
        cmd: attr,
    };
}

function makeLevelValueProps(propertyValue) {
    let level;
    if (propertyValue < 0.1) {
        propertyValue = 0;
    }
    level = Math.min(Math.round(propertyValue * 254 / 100), 254);
    return {
        frameCntl: {frameType: 1},
        cmd: 'moveToLevel',
        payload: [level]
    };
}

あとはIFFFTの設定(前回の記事と同じ)をすればOK。

動作確認 - Google Home から操作

  • OK Google ダイニングのライトをつけて
  • OK Google ダイニングのライトを消して
  • OK Google ダイニングを60%の明るさにして

上記の発話で下記のようにAPIのフレームを送信するようにサーバ側の実装を追加する。

xbeeAPI.builder.write(buildZclFrame(
    bulb.addr64,
    bulb.addr16,
    bulb.endpoint,
    ZHA_PROFILE_ID,
    CLUSTER_ID_GENONOFF,
    makeOnOffValueProps(true)
));

xbeeAPI.builder.write(buildZclFrame(
    bulb.addr64,
    bulb.addr16,
    bulb.endpoint,
    ZHA_PROFILE_ID,
    CLUSTER_ID_GENONOFF,
    makeOnOffValueProps(false)
));

xbeeAPI.builder.write(buildZclFrame(
    bulb.addr64,
    bulb.addr16,
    bulb.endpoint,
    ZHA_PROFILE_ID,
    CLUSTER_ID_GENLEVELCTRL,
    makeLevelValueProps(60)));
});

一通りZigbeeでの実現方法*3を理解したが、やはり機能を足すのは大変。 www.ikea.com が早く日本でもリリースされますように。。。

*1:https://github.com/mozilla-iot/wiki/wiki/Debugging-Zigbee

*2:IKEA TRÅDFRIのライトでThings Gatewayで色の変更ができないのがこれが原因。Hue/Saturationがいる

*3:正確にはLight LinkではなくHome Automationのプロファイルでですが

IKEA TRÅDFRI を RaspberryPi + Zigbee (Things Gateway) で操作

GWのIKEAのニュースを見て前から気になっていた

www.ikea.com

IKEA TRÅDFRIを購入。帰宅後、早速Google Homeでの接続を調べていると、なんとGateway(日本未発売)が必要なことが判明。。。 色々調べていると、Hueのブリッジとの接続例ばかり。Hueはちょっと高めなのでなんとかIKEAで揃えたい。

公式のページ*1によるとZigbeeLight Linkというプロファイルに準拠しているようなので、自分でZigbeeで操作できるのではと思いまずやってみる*2

Mozilla IoT - Things Gateway

ZigbeeといえばXBeeだが、シリアル経由でXBeeを接続し設定することが必要。最終的にはRaspberryPiに刺したいのでお手軽なUSBドングルタイプのXStick ZB*3にしてみる。

XStick ZB

XStick ZB

すると同じ構成のMozilla IoTというプロジェクトを発見。対応しているRaspberry Pi W Zeroも手元にあったのでそちらを今回は利用。

f:id:notta55:20180505011357j:plain:w400

Zigbee対応はAdd-onという扱いで中身をさらっと見てみるとシンプルなコード。ちょうど使いたかったモジュールでxbee-apiも使っているのでリファレンスとしても良さげ。

github.com

ZHA vs ZLL

Zigbee Light Link (ZLL)は実際には、Mozilla IoTでも非対応*4。実際他の接続例を調べた限りではHome Automation(ZHA)のプロファイルで接続している例が多かった。Coordinatorを使った通常のメッシュのネットワークの接続のフローがそのまま使える。

ZLLのメリットは全てRouterでCoordinater無しでネットワークを構築するためのTouchLinkプロトコルなのだろうが最初のフローでマスターキーが必要だったりして個人で作れるかどうかは不明。

XBeeのセットアップ と Bulbのリセット

早速セットアップ。XBeeの設定は専用のソフトウェア - XCTUで行う。ここを参考にわからない用語だらけだがわかったフリで進める。

  • Zigbee Coordinator firmwareを焼く (Coordinator/Router/End Device用がある)
  • 以下の設定になっていることを確認する。これがZigbee ZDO (ZigBee device objects) /ZCL (ZigBee cluster library) のデバイスに接続するのに必要*5
    • ZS = 2
    • EE = 1
    • EO = 1
    • AO = 1
    • AP = 1

APIモードとは、0x7E+MSB,LSB(データ長)+コマンド、データ+チェックサム(フレーム) で送信する形式。普通のシリアルのような通信は透過モード。

Mozilla IoTの設定画面でZigbeeのAdapterが見えればXBeeの設定は成功。見えない場合は何か設定が間違っている可能性が高い*6

f:id:notta55:20180505013614p:plain

  • デフォルトだとライトが同梱のコントローラーにペアリングされているので主電源を6回トグル *7

実際XSitckをPCに際してX−CTUでScanしてみるとライトがネットワーク上で見える。 f:id:notta55:20180505011409p:plain:w400

バイスの追加と操作

この状態でRaspberryPiの電源を入れて一通り設定。スキャンするとライトが一覧に現れるので追加。

f:id:notta55:20180505084758p:plain:w400

内部的にはメッシュのネットワークが構築されて、うまくいくとモバイルからでもライトが操作可能になる。

f:id:notta55:20180505011425j:plain:w350

輝度調整とオンオフ以外は現在のGatewayでは未対応のようだ。もう一度X-CTUで確認してみるときちんとネットワークが構築されていることがわかる。

f:id:notta55:20180505090117p:plain:w400

次回はHAのプロファイルを使ってGoogleHomeと連携させてみようと思う。XBeeにも慣れたので次は普通のモジュールを買って繋げてみようかな。

XBeeで作るワイヤレスセンサーネットワーク (Make: PROJECTS)

XBeeで作るワイヤレスセンサーネットワーク (Make: PROJECTS)

Android アプリ設計パターン入門 を読む

たまにAndroidを触るぐらいでアプリ開発からは完全に遠ざかってしまって久しい。

Android アプリ設計パターン入門

Android アプリ設計パターン入門

  • 著者:日高 正博,小西裕介,藤原聖,吉岡 毅,今井 智章,
  • 製本版,電子版
  • PEAKSで購入する

AndroidStudioを落としてきて起動したぐらいで「そもそもどうやってアプリを作るのがよいのだろうか」「教えて貰える機会もないしなー」と思っていた矢先にたまたま知った本。 バリバリ書いているエンジニアの人にもそうでない人にもオススメの内容。以下感想。

MVVM (Model-View-Model View)、MVP (Model-View-Presenter)

本書はまず背景となる知識や歴史を振り返った後に、下記のTODOアプリを詳細に見ていくところから始まる(画像は全て下記リポジトリから)。

https://github.com/googlesamples/android-architecture/wiki/images/mvvm-databinding.png

https://github.com/googlesamples/android-architecture/wiki/images/mvp.png

読み進めていく上では、DIの知識が必須。Dependency Injectionと聞いて個人的に思い浮かぶのがこの動画。基本的には大規模なソースコード上でのテストの話なのだが*1その前提としてDIはテスタブルにしておくために必要な書き方となる。

f:id:notta55:20180402233338p:plain

DIをアプリのインフラに導入したことで、単体テストが容易になり品質や開発スピードにも寄与しているということが繰り返し主張されている。

差分開発の問題, Daggar2とRxJavaの導入

メルカリのUSアプリのリニューアル*2を事例にチームが直面した問題を惜しみなく紹介している。

チームの拡大とコードベースの肥大化によるメンテナンスの困難さをアーキテクチャや実装的な問題として捉えて分析。具体的な人員の数も克明に書かれていて相当生々しい。。。が非常に読み応えあり。

その解決方法としてDaggar2とRxJavaを導入して得られた効果は

  • 非同期処理がRxJavaにより統一される、RxJavaはテストを書きやすい
  • Daggar2によりComponentとモジュールから機能全体の依存関係をチームメンバーに分かりやすくシェアできる

Fluxアーキテクチャ、ReactNative

FluxなんかはWebでReactを使って開発している人たちの共通理解のようだが、それをAndroidに当てはめるとどのようになるかを紹介。

そしてReactNativeとNativeのハイブリッドアプリの取り組みについて紹介。「3年間運用されたアプリを3ヶ月で書き直すには?」から着想し、採用の理由はシンプルで、「Web開発者がNative開発に参画できる」「マルチプラットフォーム開発ができる」。

このぐらいまでは想像がつくが「プレイストアを介さずにOn The Air配信が可能」というところまで到達しているのが本当に凄い。また、どんな画面がNative向きでどんな画面が不向きなのか、しっかりとチームのリソースやスキル、中身までを知った上で使いこなしているから素晴らしい。

そして最後の章でAndroid Architecture Componentsのモジュールとここまで紹介してきた内容との対応を紹介。

おしまいに

「新しいから使う」「便利だから使う」ではなくて、レガシーのコードに対峙しながら問題点を意識的に探り、プロダクトとして必要な品質を限られたリソースで作り上げる。そのために最新の設計やライブラリを駆使していかにして具現化していくか、その土台となるようなアーキテクチャを泥臭い実例を交えて紹介している貴重な本だった。

*1:かなり古い動画ですが、Facebookが過去どのようにAndroidをテストしてきたかを紹介していてオススメ。自分の知識も古い。。。

*2:http://tech.mercari.com/entry/2017/07/19/123443

Google Home + Actions SDKでMediaResponseを使ったMP3再生

f:id:notta55:20180325155524j:plain

先日専用のマウントも購入したGoogle Home Mini。開発者向けのサイトを眺めているとMediaResponseを発見。独自に音楽再生ができそうなので早速試してみる。上手くいくとこのような画面になるはず。

f:id:notta55:20180325180714p:plain:w200

これはAssistantの画面だがGoogle Homeでも動作する。

プロジェクトの作成

選択肢が三つあるので、Action SDKを選択。適当に名前をつける。

f:id:notta55:20180325153414p:plain

アクションの作成

gactionのバイナリをとってきて

./gactions init

action.jsonが生成されるので編集。

  • アプリの終了のためにactions.intent.CANCEL *1もいれてしまう。
  • https://your_firebase_domain/fullfilmentのところは次に作成。
{
  "actions": [
    {
      "description": "Media Response Sample",
      "name": "MAIN",
      "fulfillment": {
        "conversationName": "MediaResponseSample"
      },
      "intent": {
        "name": "actions.intent.MAIN"
      }
    }
  ],
  "conversations": {
    "MediaResponseSample": {
      "name": "MediaResponseSample",
      "url": "https://your_firebase_domain/fullfilment",
      "fulfillmentApiVersion": 2,
      "inDialogIntents": [
        {
          "name": "actions.intent.CANCEL"
        }
      ]
    }
  },
  "locale": "ja"
}

Fulfillmentのエンドポイント作成

簡単なのでFirebaseを使う。

npm install -g firebase-tools #CLIをいれる
firebase login #ログイン

functionの雛形を作ってしまう

firebase init functions
cd functions
npm install 

github.comを追加

npm install actions-on-google --save
vi index.js

Actionの中身

さっそく動作を書いてみる

const functions = require('firebase-functions');
const ActionsSdkApp = require('actions-on-google').ActionsSdkApp;

exports.fullfilment = functions.https.onRequest( (req,res) => {

    const app = new ActionsSdkApp({request: req, response: res});

    function responseHandler (app) {
        let intent = app.getIntent();
        switch (intent) {
            case app.StandardIntents.MAIN:
                app.ask('プログラム名を教えてください。');
                break;
            case app.StandardIntents.TEXT: {
                let text = app.getArgument('text');
                const mediaResponse = app.buildMediaResponse()
                mediaResponse.addMediaObjects([
                    app.buildMediaObject("Test MP3", "https://your_test_content/test.mp3")
                        .setDescription("Spoken Word(interviews, reading, etc)")
                        .setImage("https://your_test_content/program.png", app.Media.ImageType.LARGE)
                ]);
                const richResponse =
                    app.buildRichResponse()
                        .addSimpleResponse(text + 'が見つかりました。')
                        .addMediaResponse(mediaResponse)
                        .addSuggestions(["前の回を聞く"]);
                app.ask(richResponse);
                break;
            }
            case app.StandardIntents.CANCEL:
                app.tell('終了します。');
                break;
            case app.StandardIntents.MEDIA_STATUS: {
                app.tell('再生が終わりました。');
                break;
            }
        }
    }
    app.handleRequest(responseHandler);
});

デプロイとアクションの更新

firebase deploy --only functions

実行後に表示されるURLをaction.jsonに入れて

./gactions update --action_package action.json --project PROJECT_ID

後は、Action On GoogleのコンソールからTEST DRAFTをすればOK。App Informationは適当に設定。今回は「マイラジオ」という名前に設定。

動作確認

Action On GoogleのコンソールのSimulatorで動作確認。

f:id:notta55:20180325154021p:plain:w400

Google Home + Raspberry PiでHome Automation入門

昨年の半額セールで購入したGoogle Home Mini。まずは家のリビングのTVとエアコンと照明をオンオフできるような機能を自分で作ってみる*1

準備

赤外線の学習リモコンの類やIoT対応した照明など、機器は色々あるが、レビューを見て評判のよさそうな以下をセレクト。飽きたら別の用途に使ってもよいので汎用性の高そうなRaspberry Pi 3 の Model Bを購入。OSはRaspbianにして付属のマニュアルに沿ってインストール。インストールにはUSBとマウスが必要。

ビット・トレード・ワン USB赤外線リモコンアドバンス ADIR01P

ビット・トレード・ワン USB赤外線リモコンアドバンス ADIR01P

とりあえず全部つなぐ

赤外線モジュールはUSBのmini-USBという一昔前の端子であることに注意。大きい100円ショップで辛うじて売られているものを救出して今回は利用。

f:id:notta55:20180105222934j:plain

コマンドラインツールのビルド

の記事を参考にする。公式にサポートされているのはWindows環境用のC#の実装のようだが、それをlinux上で動作するように ポートしている模様。下記からダウンロードしてセルフビルドしてmake installしておく。

そのままだと実行にはroot権限が必要となるため追加で設定*2。刺した状態でlsusbをしてVendorとidProductをメモして

#sudo vi /etc/udev/rules.d/bittrade.rules
SUBSYSTEM=="usb", ATTRS{idVendor}=="22ea", ATTRS{idProduct}=="003a", MODE="0666"

こんな感じで記述してsudo udevadm control --reload-rulesで設定を読み込み。

IFTTTの設定

ifttt.com

こちらも記事が多く見つかるが、単純なon/offであれば、"Say a phrase with a text ingredient"を選んでWebHookを設定すればOK。 f:id:notta55:20180105231409p:plain

Dynamic DNSの設定

WebHookを設定する際に環境的にグローバルIPとルータのDMZの設定などをする必要がある場合は追加で設定。 Raspberry Pi 3でもDDClientが利用可能*3。 自分の環境ではeth0はローカルのIPになってしまうのでグローバルのIPを設定。

# sudo vi /etc/ddclient.conf
#use=if, if=wlan0
use=web, web=checkip.dyndns.org
ssl=yes

/etc/init.d/ddclient restartで正しく更新されるかテスト。

WebHookの実装

学習したリモコンデータはコマンドラインツールでローカルにファイルで出力されるのでそれをそのまま使ってしまう(手抜き)。 ポイントとしては、IFTTTで設定されたTextの処理。

  • スペースが入っている場合があるのでtrimしてしまう

  • シノニム的な言い換え('電気','ライト','明かり')に備えてマップを持ってしまう

var fs = require('fs');
var express = require("express");
var bodyParser = require("body-parser");
var exec = require('child_process').exec;
var app = express();

app.use(bodyParser.urlencoded({ extended: true }));
app.use(bodyParser.json());

var server = app.listen(3000, function(){
    console.log("Node.js is listening to PORT:" + server.address().port);
});

var targetNameMap = {
    'light' : ['電気','ライト','明かり'],
    'tv' : ['TV','テレビ'],
    'aircon' : ['エアコン','暖房','冷房']
};

function execBTO(path){
    exec('/usr/local/bin/bto_advanced_USBIR_cmd -d `cat '+__dirname+'/'+path+'`',
        function (error, stdout, stderr) {
            if(stdout){
                console.log('stdout: ' + stdout);
            }
            if(stderr){
                console.log('stderr: ' + stderr);
            }
            if (error !== null) {
                console.log('Exec error: ' + error);
            }
    });
}

function processAction(target, cmd){
    Object.keys(targetNameMap).forEach(function(target_){
        if( targetNameMap[target_].indexOf(target) === -1 && target_ !== target){
            return;
        }
        var path = 'data/'+target_+'/'+cmd;
        fs.access(__dirname+'/'+path, (fs.constants || fs).R_OK, function(error){
            if (error) {
                if (error.code === "ENOENT") {
                    console.log('ENOENT error '+__dirname+'/'+path);
                }
            }
            execBTO(path);
        });
    });
}

app.post("/api/action", function(req, res, next){
    if( !req.body.target || !req.body.cmd ) {
        res.json({status:'NG'});
        return;
    }
    processAction(req.body.target.trim(), req.body.cmd);
    res.json({status:'OK'});
});

あとはNodejsの起動スクリプトに入れてforeverを使って常駐化すると良い。

動作確認

  • OK Google リビングのエアコンをつけて
  • OK Google リビングのTVをつけて
  • OK Google リビングの電気をつけて

といった感じで赤外線モジュール経由でコントロールが可能。

所感

一通り動作したので、Raspberry Pi Zero Wへ乗せ変えて暫く運用予定*4。が、やはりインテリア的な見た目やメンテナンスを考えると

Nature Remo

Nature Remo

が欲しい。室内に置くものなので機能観点だけでは割り切れないということなのだろう。

*1:本当はNature Remoが欲しい

*2:c++ - libusb cannot open USB device, permission isse. NetBeans/Ubuntu - Stack Overflow

*3:Dynamic DNSの例 https://support.google.com/domains/answer/6147083?hl=ja

*4:抽選らしいので当たるといいですが

モックインタビューのサービスGainloのブログの問題を1日1問

gainloというサービスを紹介しているブログを発見。

このモックインタビューのサービスは有料らしいが、ブログも中々読み応えがある。毎日一問ずつ解いてみたのでその記録を。

blog.gainlo.co まずは愚直に解く。この"Sub"というのがポイント。つまり複数のウィンドウに切って処理するので 「どこまで切るか」「どこから切るか」で何回もforループを書く必要があるが、そこをウィンドウをスライドするイメージで計算量を減らす工夫をするテクニックを解説している。

vector<vector<int>> getSubArray(vector<int> num, int sum){
    vector<vector<int>> ret;
    int i = 0;
    int j = 0;
    int s = num[0];
    while( i < num.size() && j < num.size()) {
        if( i!=j ){
            s+=num[j];
        }
        if ( s > sum ){
            s -= num[i];
            i++;
        }
        if( s == sum ){
            ret.push_back(getRange(num,i,j));
            s -= num[i];
            i++;
        }
        j++;
    }
    return ret;
}

もしくは動的計画法でメモ化を使ったやり方。

void getSubArrayDP( vector<vector<int>>& result, vector<int> sub, vector<int> num, int sum, int remaining, int i ){

    if( remaining == 0 ) {
        auto it = find(result.begin(),result.end(),sub);
        if(it == result.end())
            result.push_back(sub);
        return;
    }

    if( i == num.size() || remaining < 0 ) return;

    sub.push_back(num[i]);
    getSubArrayDP(result, sub, num, sum, remaining - num[i], i+1);

    getSubArrayDP(result, vector<int>(), num, sum, sum, i+1);

    return;
}

続いてアナグラムWikipediaによると

blog.gainlo.co

なんだ、一旦並べ替えて数えるだけか。

vector<vector<string>>  getAnagramGroup( vector<string> input ){
    vector<vector<string>> ret;
    unordered_map<string,vector<string>> anagramMap;

    for( string s : input ){
        string key = s;
        sort(key.begin(),key.end());
        auto it = anagramMap.find(key);
        if( it != anagramMap.end()){
            it->second.push_back(s);
        } else {
            anagramMap.insert(make_pair(key,vector<string>{s}));
        }
    }

    for( auto it = anagramMap.begin(); it != anagramMap.end(); ++it) {
        if(it->second.size() > 1)
            ret.push_back(it->second);
    }
    return ret;
}

blog.gainlo.co

いわゆる最小の編集距離を求める問題。と聞くと難しそうだが前回紹介した動的計画法がそのまま使える。 積み上げていく感じをイメージするとわかりやすい。

int Solution::minDistance(string word1, string word2) {
    vector<vector<int>> distance(word1.length() + 1, vector<int>(word2.length() + 1, 0));
    for (int i = 0; i < distance.size(); i++) {
        for (int j = 0; j < distance[0].size(); j++) {
            if (i == 0)
                distance[i][j] = j;
            else if (j == 0)
                distance[i][j] = i;
        }
    }

    for (int i = 1; i < distance.size(); i++) {
        for (int j = 1; j < distance[0].size(); j++) {
            if (word1[i - 1] == word2[j - 1])
                distance[i][j] = distance[i - 1][j - 1];
            else
                distance[i][j] = 1 + min(distance[i - 1][j - 1], min(distance[i - 1][j], distance[i][j - 1]));
        }
    }
    return distance[word1.length()][word2.length()];    
}

blog.gainlo.co 続いて木の問題。ブログでも書かれているStackを使ったDFSの走査を試しに書いてみる。

struct TreeNode2 {
    TreeNode2* left;
    TreeNode2* right;
    string value;
    bool visited;
    TreeNode2() : left(NULL),right(NULL),value(""),visited(false){}
};

void printDFS(TreeNode2 *root){
    if(root == NULL) return;

    stack<pair<TreeNode2*,string>> s;
    s.push(make_pair(root,""));

    while(!s.empty()){
        TreeNode2 *n = s.top().first;
        string     p = s.top().second;
        p += n->value;
        s.pop();
        n->visited = true;
        if(n->right && !n->right->visited){

            s.push(make_pair(n->right,p+"->"));
        }
        if(n->left && !n->left->visited){
            s.push(make_pair(n->left,p+"->"));
        }
        if(n->left == NULL && n->right ==NULL ){
            cout << p << endl;
        }
    }
}

blog.gainlo.co 今度はリストの並び替え。

struct LinkedList {
    LinkedList *next;
    LinkedList *down;
    int        value;
    LinkedList(int v) : next(NULL),down(NULL),value(v){}
};

void flattenList(vector<vector<LinkedList*>>& result, LinkedList *root, int level){
    if(root==NULL) return;
    queue<pair<LinkedList*,int>> q;
    q.push(make_pair(root,0));

    while(!q.empty()){
        LinkedList* n = q.front().first;
        int level = q.front().second;
        q.pop();
        result[level].push_back(n);
        if(n->next) q.push(make_pair(n->next,level));
        if(n->down) q.push(make_pair(n->down,level+1));
    }
}

blog.gainlo.co これも最初に紹介したスライドウィンドウに似てる。

string findLongestK2( int K, string input ){
    string maxStr = "";
    int    maxLen = 0;
    int    left   = 0;
    int    right  = 0;
    unordered_set<char> h;
    while(left < input.size() && right < input.size()){
        h.insert(input[right]);
        if( h.size() == K ) {
            int len = right-left+1;
            if(  len > maxLen ){
                maxLen = len;
                maxStr = input.substr(left, len);
            }
        }
        else if( h.size() > K ){
            char c = input[left];
            while(input[left]==c){
                left++;
            }
            h.erase(c);
        }
        right++;
    }
    return maxStr;
}

blog.gainlo.co グラフの二つのノードから共通の親を返すものを見つけるもの。

bool findNode(TreeNode *root, TreeNode *target){
    if( root == NULL) return false;
    if( root->val == target->val) return true;
    return findNode(root->left, target) || findNode(root->right, target);
}

TreeNode* getCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q){
    if( root == NULL || root == p || root == q ){
        return root;
    };
    bool pIsLeft = findNode(root->left, p);
    bool qIsLeft = findNode(root->left, q);
    if(pIsLeft != qIsLeft){
        return root;
    }
    TreeNode *child = pIsLeft ? root->left : root->right;
    return getCommonAncestor(child, p, q);
}


int getLCA(TreeNode *root, TreeNode *p, TreeNode *q){
    if( !findNode(root,p) || !findNode(root,q) ){
        return -1;
    }
    TreeNode* node = getCommonAncestor(root, p, q);
    return  (node) ? node->val : -1;
}

blog.gainlo.co これも有名な問題のようだ。

int countMaximumMeetingRoom(vector<pair<int,int>> interval){
    struct Event{
        int  time;
        bool in;
        Event(): time(-1),in(false){}
        bool operator< ( const Event& right) const {
            return time < right.time;
        }
    };
    vector<Event> ev(interval.size()*2);
    for( int i = 0; i < interval.size(); i++ ){
        ev[2*i].time   = interval[i].first;
        ev[2*i].in     = true;
        ev[2*i+1].time = interval[i].second;
        ev[2*i+1].in = false;

    }
    sort(ev.begin(),ev.end());
    int count = 0;
    int maxCount = 0;
    for( int i = 0; i < ev.size(); i++ ){
        count += ev[i].in ? 1 : -1;
        maxCount = max(count, maxCount);
    }
    return maxCount;
}

blog.gainlo.co

string getLongestSubStr2(string s){
    string maxStr = "";
    unordered_set<char> dup;
    int start = 0;
    int end = 0;
    while(start < s.size() && end < s.size()){
        if(dup.find(s[end])==dup.end()){
            dup.insert(s[end]);
            string sub = s.substr(start,(end-start)+1);
            if(sub.size()>maxStr.size()){
                maxStr = sub;
            }
            end++;
        } else {
            while(start<end){
                dup.erase(dup.find(s[start]));
                if(s[start]==s[end]){
                    start++;
                    break;
                }
                start++;
            }
        }
    }
    return maxStr;
}

動的計画法とトポロジカルソート

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

を本屋で見て買おうか迷っていたところ、アルゴリズムの図解ということでふと思い出したのが、 アルゴリズムイントロダクション15章 動的計画法のスライド。ここで登場する最長共通部分列の図は目から鱗だった。

そういえば電子書籍

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

を持っていたままあまり読んでいなかったので久々にアルゴリズムの勉強でもしてみる。 本を片手に自分で実装してみたものをそのままメモ。

なんとか理解できそうなものをかいつまみ。

DP: Longest Common Subsequence problem: LCS

動的計画法の有名な問題らしい。最長共通部分列とは、X = {a, b, c, b, d, a, b},Y = {b, d, c, a, b, a}があるとすると{b, c, b, a}。

// O(NM)
// dp[i][j] = dp[i-1][j-1]+1 //X[i]==Y[j]
//          = max(dp[i-1][j], dp[i][j-1]) //X[i]!=Y[j]
// getLCSLength("abcbdab","bdcaba") // 4
int 
getLCSLength(string x, string y){
  int M = x.size();
  int N = y.size();
  int maxVal = INT_MIN;
  vector<vector<int>> dp;
  dp.resize(M,vector<int>(N,0));
  if(x[0]==y[0]){ dp[0][0] = 1; } else { dp[0][0] = 0; }
  if(x[0]==y[1]){ dp[0][1] = 1; } else { dp[0][1] = 0; }
  if(x[1]==y[0]){ dp[1][0] = 1; } else { dp[1][0] = 0; }
  for( int i = 1; i < M; i++ ){
    for( int j = 1; j < N; j++ ){
      if(x[i]==y[j]){
        dp[i][j] = dp[i-1][j-1]+1;
      } else {
        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
      }
      maxVal = max(maxVal, dp[i][j]);
    }
  }
  return maxVal;
}

DP: Coin Changing Problem

これも有名。最小のコインの枚数を調べる問題。

// O(NM)
// i is index of coin [0...5]
// j is amount [0...15]
// dp[i][j] = min(dp[i-1][j], dp[i][j-c[i]]+1);
// getMinimumCoinCount(15, 6, vector<int>{1, 2, 7, 8, 12, 50}) // 2
int getMinimumCoinCount(int total, int N, vector<int> c){
    vector<vector<int>> dp;
    int minVal = total;
    dp.resize(N,vector<int>(total+1,INT_MAX));
    for( int i = 0; i < N; i++ ){
        dp[i][0] = 0;
        dp[i][1] = 1;
    }
    for( int j = 2; j <= total; j++ ){
        for( int i = 0 ; i < N; i++ ){
            dp[i][j] = (i > 0) ?  dp[i-1][j] : INT_MAX;

            if( (j - c[i]) >= 0 ) {
                dp[i][j] = min(dp[i][j], dp[i][j - c[i]] + 1);
            }
        }
    }
    for( int i = 0; i < N; i++ ){
        minVal = min(minVal, dp[i][total]);
    }
    return minVal;
}

DP: Knapsack Problem

名前は辛うじて聞いたことがあるナップザック問題。ナップザックに入る重さで価値が最大になるようなものを調べる。

// O(NW)
// i - item index
// v - item value
// w - total weight
// dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
// getMaximumValue(vector<int>{2,2,1,3},vector<int>{4,5,2,8},5)
int getMaximumValue( vector<int> w, vector<int> v, int napSize ){
    vector<vector<int>> dp;
    int N = w.size();
    dp.resize(N,vector<int>(napSize+1,0));

    for( int j = 0; j <= napSize; j++ ){
        dp[0][j]= (w[0] <= j) ? v[0] : 0;
        if(j-w[0]>=0){
            dp[0][j] = max(dp[0][j], dp[0][j-w[0]]+v[0]);
        }
    }
    for( int i = 1; i < N; i++ ){
        for( int j = 1; j <= napSize; j++ ){
            dp[i][j] = dp[i-1][j];
            if( j-w[i] >= 0 ){
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
            }
        }
    }
    return dp[N-1][napSize];
}

DP: Longest Increasing Subsequence

今度は最長増加部分列という問題。最初に自分で考えて書いたときは

// O(N*N)
// getLISLength(vector<int>{5,5,1,3,2,4}) // 3
int getLISLength(vector<int> input){  
  vector<int> dp(input.size(),1);
  for( int i = 1; i < input.size(); i++ ){
    for( int j = i-1; j >= 0; j-- ){
      if( input[j] < input[i] ){
        dp[i]=max(dp[i], dp[j]+1);
      }
    }    
  }
  return *max_element(dp.begin(),dp.end());
}

こんな感じ。これを本に登場するより良い方法で実装すると

// O(N*logN)
// getLISLength(vector<int>{4, 1, 6, 2, 8, 5, 7, 3}) // 4
int getLISLength(vector<int> input){
    vector<int> L(input.size(),0);
    L[0]=input[0];
    int length = 1;

    for( int i = 1; i < input.size(); i++ ){
        if(L[length-1] < input[i]){
            L[length++] = input[i];
        } else {
            *lower_bound( L.begin(), L.begin()+length, input[i] ) = input[i];
        }
    }
    return length;
}

lower_boundは中で二分探索。指定した値以上の最初の要素の位置(つまり値を挿入できる位置)をイテレータで返してくれる。

Graph Topological Sort

ビルド順を考えたりする際によい(そんな仕事はしていないけど)よい方法。 以前に書いた幅優先探索

データ構造 - 計算量・グラフの走査 - 野次馬エンジニア道

がそのまま使われている。

// O(|V |+|E |)
//     vector<pair<int,int>> v{
//        make_pair(0,1),
//        make_pair(1,2),
//        make_pair(3,1),
//        make_pair(3,4),
//        make_pair(4,5),
//        make_pair(5,2)
//    };
//    getSortedNode(v, 6); // {0,3,1,4,5,2}
struct Node {
    int value;
    vector<Node*> next;
    int count;
    bool added;
    Node():value(-1),count(0),added(false){}
};

void traverseBFS( vector<int>& ret, Node* root ){
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
        Node* n = q.front();
        q.pop();
        ret.push_back(n->value);
        n->added = true;
        auto it = n->next.begin();
        while( it != n->next.end()){
            Node *next = *it;
            next->count--;
            if(next->count == 0 && !next->added ){
                q.push(next);
            }
            ++it;
        }
    }
}

vector<int> getSortedNode( vector<pair<int,int>> v, int N){
    vector<Node> node(N);
    vector<int>  ret;
    for( int i = 0; i < N; i++ ){ node[i].value=i; }
    for( pair<int,int> p : v ){
        node[p.first].next.push_back(&node[p.second]);
        node[p.second].count++;
    }
    for( int i = 0; i < N; i++ ){
        if( node[i].count == 0 && !node[i].added ){
            traverseBFS(ret, &node[i]);
        }
    }
    return ret;
}