はじめに

この記事はAndroid Advent Calendar 2019の18日目の記事です。

Android Advent Calendarということで、今回はAndroid 10のイースターエッグを自動で解くアプリを作成してみました。この記事ではその方法について解説してみたいと思います。

Android 10のイースターエッグとは

イースターエッグとは、昔からAndroidに備わっているおまけ機能で、OSバージョンごとに異なるものが実装されています。昔はただ絵が表示されるだけだったりシンプルなものが多かったですが、最近は年々凝ったものになってきており、Android 6ではFlappy Bird風のゲーム、Android 7ではねこあつめを遊ぶことができました。

イースターエッグの出し方はどのバージョンでもほぼ変わらず、Androidのバージョン番号を連打するというものです。Android 10でもこれは変わりません。
まず、設定 → デバイス情報 → Android バージョンでバージョン番号を開きます。

バージョン番号を連打すると、Android 10と表示されます。

ここで表示されている「android」「1」「0」はスワイプすることにより動かすことができます。さらに、ダブルタップしたまま押し続けると、押し続けている間回転させることができます。これらの操作で「1」と「0」を動かすことにより、以下のような「Q」の文字を作ることができます。

そうすると、背景が動き出します。これで終わりかと思いきや、この状態でさらに何度かタップすると、以下のような画面が開きます。

これは「お絵かきロジック」や「ピクロス」、英語ではNonogramなどと呼ばれるゲームです。
数字はその列に入る黒マスの数を表していて、マス目をタップすることでそのマスを黒く塗りつぶすことができます。条件を満たしている行・列は濃い緑色になります。
通常のお絵かきロジックとは違いこのイースターエッグでは、行と列のうち片方しか数字を見ることができず、もう片方は条件を満たしているかどうかしか知ることができません。
（実は画面回転するともう片方も知ることができますが、今回の記事では特に使いません）

今回はこのゲームを自動で解くアプリを作ることができないかと考え、いくつかの手法を試しました。以下では、

盤面情報の取得
パズルの解探索
盤面の操作

という3つのフェーズに分けて、説明していきたいと思います。

盤面情報の取得

盤面情報を取得するために、まずはAccessibility Serviceを用いることを検討しました。

Accessibility Service

Accessibility Serviceとは、ハンディキャップのあるユーザーの端末操作を補助する機能です。
ユーザーに代わって操作を行うため、比較的強い権限が与えられています。

Accessibility Serviceは、AccessibilityServiceというクラスを継承して作ります。onAccessibilityEventにeventに応じた処理を実装します。

MainAccessibilityService.kt

class MainAccessibilityService : AccessibilityService() {
    override fun onInterrupt() = Unit

    override fun onAccessibilityEvent(event: AccessibilityEvent) {
        // ...
    }
}

次に、作成したServiceをAndroidManifestに宣言します。
この時、 BIND_ACCESSIBILITY_SERVICE というパーミッションが必要になります。また、 AccessibilityService をintent-filterに追加します。さらに、どのようなイベントを受け取るかなどについてxmlファイルで記述したものを、meta-dataとして宣言します。

AndroidManifest.xml

<manifest>
    <application>
        <service
            android:name=".MainAccessibilityService"
            android:permission="android.permission.BIND_ACCESSIBILITY_SERVICE">
            <intent-filter>
                <action android:name="android.accessibilityservice.AccessibilityService" />
            </intent-filter>
            <meta-data
                android:name="android.accessibilityservice"
                android:resource="@xml/accessibilityservice" />
        </service>
    </application>
</manifest>

accessibilityservice.xml は以下のように宣言します。

accessibilityservice.xml

<?xml version="1.0" encoding="utf-8"?>
<accessibility-service xmlns:android="http://schemas.android.com/apk/res/android"
    android:accessibilityEventTypes="typeAllMask"
    android:accessibilityFeedbackType="feedbackAllMask"
    android:accessibilityFlags="flagDefault"
    android:canRetrieveWindowContent="true"
    android:description="@string/description" />

このアプリをインストールすると、設定 → ユーザー補助に、アプリが出てきます。

これを有効にするとサービスが起動し、 onAccessibilityEvent に記述した処理を実行することができます。

次にこれをイースターエッグに適用するために、まずはイースターエッグの実装を見ていきます。
https://android.googlesource.com/platform/frameworks/base/+/master/packages/EasterEgg

対象となるActivityはQuaresActivityという名前で、パッケージ名は com.android.egg であることが分かります。そのためまずは、先ほどのxmlファイルにパッケージ名のフィルタを追加します。

accessibilityservice.xml

android:packageNames="com.android.egg"

次に、 onAccessibilityEvent でイベントを受け取った際、ルートとなるViewを取得するために、 getRootInActiveWindow() を呼び出します。 getRootInActiveWindow() は AccessibilityNodeInfo を返します。 AccessibilityNodeInfo は実際の View 構造とは異なり、Accessibility Service用に限定された入出力関数を提供します。

QuaresActivity に対して getRootInActiveWindow() を実行すると、以下のような構造が返ってきます。

FrameLayout
└ CompoundButton
└ CompoundButton
└ CompoundButton
└ ……
└ CompoundButton

FrameLayout はルートのViewであり、 CompoundButton は各マスのViewで256(16×16)個あります。実際のView Hierarchyにはこれ以外のViewも存在していますが、ここでは見えていません。

すなわち、黒く塗りつぶすマスは取得できましたが、ヒントとなる数字の部分については取得する事ができませんでした。理由は、ここで使われているClueViewが TextView ではなく単なる View を継承しており、 onDraw で直接文字を描画しているからだと思います。

そのため、盤面情報の取得には別の方法を検討する必要があります。かなり力技ですが、画面を文字認識できれば、ヒントとなる数字を取得することができるのではないかと考えました。幸いにも、 AccessibilityService で以下のメソッドを実行すると、スクリーンショットを撮影することができます。

performGlobalAction(GLOBAL_ACTION_TAKE_SCREENSHOT)

撮影したスクリーンショットは、通常Screenshotsディレクトリに格納されます。撮影時刻がファイル名になっているため、ファイルリストの最後を取得すれば最新のスクリーンショットを手に入れることができます。

val pictures = Environment.getExternalStoragePublicDirectory(Environment.DIRECTORY_PICTURES)
val screenshots = File(pictures, "Screenshots")
val file = screenshots.listFiles()?.lastOrNull()

スクリーンショット撮影直後には画像を取得できないので、少し待ってから取得するか、 FileObserver で監視して CLOSE_WRITE イベントが来てから取得する必要があります。

Firebase ML Kit

撮影したスクリーンショットからヒントの数字を抽出するために、Firebase ML KitのText Recognizerを使いました。

基本的には公式のドキュメント通りにセットアップすれば使うことができます。
https://firebase.google.com/docs/ml-kit/android/recognize-text

まずFirebaseのプロジェクトを作成し、 google-services.json を配置します。

次に依存関係に追加します。

app/build.gradle

dependencies {
    implementation 'com.google.firebase:firebase-ml-vision:24.0.1'
}
apply plugin: 'com.google.gms.google-services'

最後に、AndroidManifestに使うモデルを宣言すればOKです。

AndroidManifest.xml

<manifest>
    <application>
        <meta-data
            android:name="com.google.firebase.ml.vision.DEPENDENCIES"
            android:value="ocr" />
    </application>
</manifest>

今回解析したい文字は数字だけなので、無料＆オンデバイスで動作します。

スクリーンショットで撮影した文字は横向きになっているので、回転してから解析します。

// スクリーンショットの読み込み
val options = BitmapFactory.Options()
options.inPreferredConfig = Bitmap.Config.ARGB_8888
val bitmap = BitmapFactory.decodeFile(file.absolutePath, options)

// スクリーンショットの回転
val matrix = Matrix()
matrix.postRotate(270f)
val rotatedBitmap = Bitmap.createBitmap(bitmap, 0, 0, bitmap.width, bitmap.height, matrix, true)

// スクリーンショットの解析
val image = FirebaseVisionImage.fromBitmap(rotatedBitmap)
val detector = FirebaseVision.getInstance().onDeviceTextRecognizer
detector.processImage(image).addOnSuccessListener { result ->
    // result.textには「0\n1-2\n3-4-5\n...」といった文字が入っている
    val clue = result.text.split("\n").map {
        it.split("-").map { it.toInt() }
    }
    // 解析したヒントを元に、パズルの解探索へ
}

実際に使ってみると高い精度で数字を取得することができました。しかし時々誤認識することがあるので、「A」を「4」にreplaceするなど泥臭いチューニングをしましたが、本題から逸れるので詳細は割愛します
（同じ数字が連続すると1つにまとまってしまうことがあったりします）

あとは数字以外にも、その列（行）が条件を満たしているかどうかを色で判定します。

この判定はライブラリなどを使う必要はなく、特定の座標の色を取得して愚直に判定しました。

bitmap[x, y] == Color.parseColor("#3ddc84")

パズルの解探索

今回解こうとしているパズルは、最初に見えている情報だけでは答えを1つに絞ることができないので、総当たりで解く必要があります。すなわち、以下のステップに分けることができます。

ヒントの数字を元に、各列に対してそれぞれ解答候補リストを作成する
条件を満たしている行・列を元に、解答候補リストからあり得ない解答を除外する
各列に対して解答候補リストの1番目を試してみる
問題が解けていない場合、2に戻る

2, 3, 4については、書いてある通りのことをそのまま実装すれば良いので、この章では1の解答候補リスト作成について簡単に解説します。

例えば、16マスに対して「3-4-5」というヒントが与えられた場合、どのような解答候補があるでしょうか？一見難しそうな問題ですが、「余分な白マスの分配」と考えると分かりやすいと思います。例えば、「3-4-5」を左端から敷き詰めていくと、以下のようになると思います。

■ ■ ■ □ ■ ■ ■ ■ □ ■ ■ ■ ■ ■ □ □

右端の余った2マスを、以下の①〜④に分配する、という風に考えます。

① ■ ■ ■ ② □ ■ ■ ■ ■ ③ □ ■ ■ ■ ■ ■ ④

この分配は、「①〜④から重複を許して2つ選ぶ」という重複組合せの問題に帰着できるので、パターン数は以下のように求められます。

{}_4 \mathrm{H} _2 = {}_5 \mathrm{C} _2 = 10

具体的には、以下の10通りです。

(2, 0, 0, 0)
(0, 2, 0, 0)
(0, 0, 2, 0)
(0, 0, 0, 2)
(1, 1, 0, 0)
(1, 0, 1, 0)
(1, 0, 0, 1)
(0, 1, 1, 0)
(0, 1, 0, 1)
(0, 0, 1, 1)

元の問題に戻すと、以下のような解答候補があるということになります。

□□■■■□■■■■□■■■■■
■■■□□□■■■■□■■■■■
■■■□■■■■□□□■■■■■
■■■□■■■■□■■■■■□□
□■■■□□■■■■□■■■■■
□■■■□■■■■□□■■■■■
□■■■□■■■■□■■■■■□
■■■□□■■■■□□■■■■■
■■■□□■■■■□■■■■■□
■■■□■■■■□□■■■■■□

これを一般化すると、ヒントの数列

a_1, a_2, ..., a_n

が与えられた時に、黒マスの個数は

\sum_{k=1}^n a_k

であり、各黒マスの間に最低限置かなければならない白マスが n-1 個なので、16マスの列に対して余分な白マスの個数は

16 - \sum_{k=1}^n a_k - (n-1)

となります。これを n+1 箇所に分配すれば良いことになります。

重複組合せ

{}_n \mathrm{H} _k

の全パターンを出力する関数は、以下のように再帰で書くことができます。

fun combinationWithRepetition(n: Int, k: Int, current: List<Int> = emptyList()): List<List<Int>> {
    if (current.size == k) return listOf(current)
    val last = current.lastOrNull() ?: 0
    return last.until(n).flatMap {
        combinationWithRepetition(n, k, current + listOf(it))
    }
}

以上の関数から得られた数列を、盤面の解答候補リストとして使えば良いということになります。

盤面の操作

ここまでできれば、後はAccessibility Serviceで取得した CompoundButton に対して、クリックアクションを送信するだけで、クリックすることができます。

button.performAction(AccessibilityNodeInfo.ACTION_CLICK)

クリックするかどうかは、現在のチェック状態と操作後に期待するチェック状態でxorを取って決めます。adb経由でクリックするよりも素早く実行することができます。

まとめ

というわけで完成したものがコチラ！

わりといい感じに動かすことができました

……そして後から気づいたのですが、実はQuaresActivityが問題作成時に、デバッグログに答えを出力していました。これを見ながらやれば、誰でも解けちゃいますね

V/Quares: icon: 
                    
          XXXX      
         XX  XX     
         X    X     
         X    X     
       XXXXXXXXXX   
       XXXXXXXXXX   
       X        X   
       X        X   
       X   XX   X   
       X   XX   X   
       X        X   
       X        X   
       XXXXXXXXXX   
       XXXXXXXXXX

この記事は以上となります、何か間違いや感想等あれば気軽にコメントもらえればと思います。

次のイースターエッグも楽しみですね！それではよいお年を