プログラミング例題（ハミルトン閉路問題）：Android版+RNN学習

   【what is this】小規模（５ノード）の有向ハミルトン閉路問題を、前回はマイクロビット（micro:bit）単体で解きました。今回は、それをAndroidスマホで実現しました。MIT App Inventorを用いて、チェックボックスによる接続指定や矢印付きグラフの描画も含めて見やくしました。さらに、Deep Learning（RNN(LSTM)）を用いて、グラフとそのハミルトン閉路の個数の対を、多数学習させる実験も行いました。

■MIT App Inventorを用いたハミルトン閉路解法アプリ
　micro:bit単体では、出力表示が5x5のLEDに限られますが、Androidスマホを使えば、入出力とも、大幅に改善できます。また、この解法は全パス検索となるのですが、具体的なその方法は（順列生成を含めて）、それほど自明ではありません。ですから、スマホでこの解法アプリを設計製作することは、高校〜大学初級におけるプログラミング題材の候補になるはずです。小生のアイディアを以下にご紹介します。
　例えば、以下のような４ノードの有向ハミルトン経路を調べるとします。（目視ですぐに分かるのですが）

　図１(a)のようにして、このアプリで解くことができます。4x4のチェックボックスにチェックを入れることで、ノード間の有向接続を指定します。ボタン"genGraph"によって、それを矢印付きのグラフで表示します。そして、ボタン"solve"を押すと、解が得られます。この例では、解は存在しませんでしたが。

　では次に、ノード数を６に設定して、別のグラフでやってみます。図１(b)の通りです。この例では解は２つ見つかりました。そのうちの一つについては、グラフ上に赤い矢印を付してその経路を明示しています。

■ディープラーニングでハミルトン閉路の個数を学習させる
　次にやってみたのは、「ディープラーニングでハミルトン閉路の個数を発見させる」試みです。５ノードの場合でも、それから作られる有向グラフは、約100万個になります。そのうちの、20万個をランダムに選択します。その各グラフ（接続情報）に対して、上記のような方法で求めたハミルトン閉路の個数をラベルとして付与し、学習させました。図２がその場合の学習データです。

　この学習データをある構造のRNN(LSTM)で学習させた結果を図３に示します。20万件のうち、18万件を学習（訓練）データに、2万件をテストデータとした場合の、テストデータの正解率は、50エポックで99.75%に達しました！
　すなわち、「５ノードのどんな有向グラフを与えても99.7％程度の確率でハミルトン閉路の個数を正答する」ように学習できた、と言えるでしょう。

（注）この学習は、スマホではなく、PCで行いました。

Using MIT App Inventor AWS AI Services Extension

Modern AI image recognition allows us to recognize not only objects, but also the accompanying text (strings). Here we will try it using Amazon AWS Rekognition. Using the APIs provided there, we can create a variety of applications on our PC, but for more convenient use, the applications on our smartphone will be preferable.

Recently, I focused on the AWS AI Services Extension developed by Ceyhun Özgün. This is an Extension that allows MIT App Inventor applications to easily take advantage of such recognition features. References [1] and [2] provide descriptions and demo programs. I've created a simple smartphone application like Fig.1 below, using this useful information as a reference.

(Please click to enlarge)

Let me illustrate the recognition results in this diagram. Fig.1 (a) is an image of the US $2 bill. Immediately, “Money, Person, Dollar” was recognized. In addition, the text in the image was also recognized. In particular, the number “J045... 5A”, which is the id of the banknote, is also recognized precisely. Fig.1 (b), on the other hand, is an image of a notebook and books. It is recognized as “Book”, and the text of the titles of the books (although handwriting is also included) is almost accurate. I think it's great. These smartphone apps are fun to use wherever you take them!

The design part of this app is shown in Fig.2. Here, I used AppyBuilder. You can choose to take a picture now or use an image that you already have in your library. After that, recognition is performed automatically and the results of recognition of objects and text are displayed.

Next Fig.3 is the complete blocks of this app. Thanks to the Extension mentioned above, you will find that it has become a very concise program. In order to use this Extension, you need to set up an AWS account. In particular, be aware that you will give your AWS Services credentials on the first run. Details of this are also described in the literature [1]. Thanks to Ceyhun Özgün!

References
[1] https://hackernoon.com/your-kid-can-code-a-fruit-detector-with-this-mit-app-inventor-aws-ai-services-extension-231665c8bcdc
[2] https://github.com/ceyhunozgun/awsAIServicesAppInventorExtension/wiki

A JSON Decoding Extension for App Inventor (2)

[Dec.6, 2019] For your convenience, another example is shown below:
https://sparse-dense.blogspot.com/2019/12/another-example-using-json-decoding.html

In the previous article, I introduced a JSON Decode Extension to easily extract the necessary information from the JSON file received from a Web service. This time, in order to test this Extension, I created a simple book search application. There are many applications of this type, but the concern here is how easy it is to decode JSON files.

Results from the book search app

The created application is as shown above. It shows the search results of one English book and two Japanese books. Giving a few keywords, Google Book Search searches for books and returns the results in JSON text as shown below. In this example, I set to receive only one book out of hit books.

JSON text sent back from the web service　(a part)

For example, in the first search, "Galois" and "Groups" were given as keywords. The resulting Json text is shown above. "title", "authors", "publishedDate", "thumbnail" and "description" are extracted and displayed from this data. The program is shown in the figure below. This is all of the source program. Therefore, it can be said that this is made quite compact.

Complete App Inventor source program of the book search

However, there is still room for improvement. For example, the current Extension receives the following list individually as a search instruction string.

query for title -> "items,volumeInfo,title"
query for authors -> "items,volumeInfo,authors"
query for publishedDate -> "items,volumeInfo,publishedDate"
query for thumbnail -> "items,volumeInfo,imageLinks,thumbnail"
query for description -> "items,volumeInfo,description"

This is a little inefficient. The values ​​of tags at the same hierarchical level should be collectively received as follows. In the near future, we plan to revise the extension so that we can respond to this. That way, you can make this application even easier.

query for several items -> "items,volumeInfo,[title,authors,publishedDate,description]"
query for thumbnail -> "items,volumeInfo,imageLinks,thumbnail"

A JSON Decoding Extension for App Inventor (1)

[Dec.6, 2019] For your convenience, another example is shown below:
https://sparse-dense.blogspot.com/2019/12/another-example-using-json-decoding.html

[This Extension and  its doc are available. Please see the bottom of this article.]

JSON format is commonly used when receiving data from Web services, etc. With App Inventor, JsonTextDecode in the web block can convert JSON to list structures. Then, the conversion result can be manipulated by the selectItem and lookUpInPairs of the list block. However, as Evan W Patton (MIT) pointed out in the paper [1], these list processes are generally very complicated. And he also suggested a more readable and compact Extension block to alleviate this. 

I independently developed an Extension for JSON decode based on his new block idea. This Extension might be intuitive and easy to understand because it can hierarchically acquire necessary information with the tag names (properties) without using complicated operations on nested lists. The outline is shown in the figure below. (please enlarge and see the figure.)

This Extension takes two arguments. One is JSON data that was converted into list structure. The other is a search instruction list for hierarchically specifying the value of a specific tag (property). In this example, JSON text holds the values ​​of four kinds of sensors as "healthData". In the above figure, the name of the third sensor is specified. Note that in the query list, a number such as "3" indicates the element index of the JSON array structure.

Query List : John, healthData, 3, sensor
Result : Systolic pressure

JSON data used here is a modified version of the health data published in the following document [2]. The following figure shows the part of listing up all four sensors and their values ​​using this Extension. I think that it is written concisely. Operations for complicated list processing are not appeared here.

Collecting values of the four sensors

An example of running this application is shown below. For details, please see the files shown below.

Result of the test program on Android

Within this Extension, the list structure is iteratively processed using the function of YailList [3]. I think that YailList makes somewhat relaxation of complicated data type conversion (casting)  in JAVA. This Extension is still in beta. Although some of the JSON structures have been tested, all the structures are not covered, so bugs may be included. However, it is shown below for your reference. It was tested with Nexus 6 (Android 7.1.1). This extension was created using AppyBuilder Code Editor [4].

･JSON Decoding Extension (beta version, FoYoJSON.aix）revised Jan. 19, 2019

･JSON Decoding Extension Document (pdf file) created on Jan.21, 2019

References

[1] JSON Interoperability in MIT App Inventor
https://2018.splashcon.org/event/blocks-2018-papers-json-interoperability-in-mit-app-inventor
[2] http://georgepavlides.info/ehealth-made-simple/
[3] http://3nportal.com/AIBridge/API/com/google/appinventor/components/runtime/util/YailList.html
[4] AppyBuilder Code Editor
http://Editor.AppyBuilder.com

Make a mini calendar app for Android, celebrating the New Year

Celebrate the New Year and make a small app! As you can see from the calendar, there are several months with the same day of the week. So, let's make an application that groups months by the day of the week on the 1st day as a key.

[ For Japanese version, please click here.]

grouping months by the day of the week on the 1st day

Although this mini app is not so practical, I will make it with the following five goals:

[1] Make the application logic in Java for Android.
[2] Use lambda expressions, streams, and the new date classes provided by Java 8.
[3] Create a GUI with App Inventor and call Java from there.
[4] Create as a general-purpose framework applicable to other applications.
[5] Customize the ActivityStarter to create a new block.

First, I will talk about [1] and [2]. With the recent Android, we can use Java 8 features. So, I'm going to write this app as concisely as possible using lambda expressions and streams. The logic part is as follows. The essential part is only one assignment statement to a Map object named "mp". The element of this object is a pair of "day of the week" and "a list of months whose first day matches that day of the week".

Next is [3] and [4]. Java programs like the above can be called using App Inventor 's Activity Starter function (block). I will use it, but in order to make it a general-purpose framework, I prepared a template for both the App Inventor side and the Java side. On the Java side, I prepared an input processing part and an output processing part beforehand so that users can complete it by rewriting only the application logic. Also, the App Inventor side has been designed to be applicable to many other applications as shown below.　

A generic App Inventor application that calls Java programs

With regard to the last item [5], I wanted to slightly change the input data and parameters passing to Activity Starter, as a result of considering the versatility as described above. So, I customized ActivityStarter and created new blocks shown below, using AppyBuilder Code Editor. I / O with the Java side was designed to do via a text file. Regarding the input, I provide two ways, passing the path of the input file and passing the text data directly. The boolean parameter "isFile" in the Setup block blow makes this selection possible.

Newly created App Inventor block (customized version of Activity Starter)

The entire App Inventor program created using this new block is as follows.

App Inventor program with newly created block

[Note] About Android and Java 8
Under Android 5.0 (API level 22), it is Java 7 compliant and Java 8 cannot be used. Android 6.0 (API level 23) can use part of lambda expressions etc., but seems to require Android 8.0 (API level 26) or higher in order to use full functions including streams.

A good example of Extension for App Inventor

If you want to create your own blocks (Extensions blocks) with App Inventor, how about referring to the example below. It is an ImageProcessor Extension published on the MIT App Inventor site. This makes two images to be combined into one.
http://appinventor.mit.edu/extensions/

It is said to be "Unsupported" materials, but intelligible Java source code has been released. The main functions of this extension are as follows:

• Fetch two images into the application, then creates an image combining the two.
• Give a weight to decide which image to adopt strongly.
• For all the pixels, for each of the elements of R, G, B, A, both images are combined according to the weight. It is as follows: (pixel in image C) = weight * (pixcel in image A) + (1 - weight) * (pixcel in image B)
• Writes the image of the join result to external storage. In doing so, give write permission with annotation @UsesPermissions.

From the Java source code of this Extension, you can learn the following basic items:

• Basic operation of pixels of an image
• How to make a function block with and without return value
• Generation of user event and its processing
• How to set properties (image size, weight,  etc.)

After understanding this Java source program, I made a very simple application using this extension. The following figure shows the entire source program of this application. Of course, thanks to this Exrensions block, this is extremely consice. Furthermore, after preparing the Java source list, you do not need to set up the build environment yourself. The following cloud builder will take care of everything.

http://editor.appybuilder.com/

Complete source program using Extensions blocks

Two examples of execution result of this application are shown below. The images as expected were obtained. How fun this is!

Original images(above) and the combined image(blow)

I would like to introduce my second version Extension which is a little advanced now.

With this experience as a clue, you want to develop yet another unique Extensions. The following reference sites would help you.

# How to make Extension concretely
http://ai2.appinventor.mit.edu/reference/other/extensions.html
# Java source code for existing blocks in App Inventor
https://github.com/mit-cml/appinventor-sources/tree/master/appinventor/components/src/com/google/appinventor/components/runtime

Creating my own extension blocks for App Inventor

MIT App Inventor for efficiently developing mobile applications has functions named Extensions that users can develop their own blocks. If you know Java, in principle you can do that, but in fact it's not so easy. Development methods for Extensions are presented in several sites, among which the AppyBuilder Code Editor shown in the following is extremely easy to use and useful:
https://amerkashi.wordpress.com/2018/11/26/appybuilder-code-editor/
http://Editor.AppyBuilder.com

Anyway, here we will create a simple and unique block with Extensions. The figure below is a hearing training application using English news. There is a counter to record how many times you have heard a particular news. Of course, even when resuming after turning off the power of smartphone, that counter must be continued. In other words, it must be created as a persistent counter.

Persistent counter in a real app

We will proceed with a simple application that extracts only this persistent counter portion as follows.

Persistent counter for an examination

If you use TinyDB, you can easily create such a counter as shown below. However, to do that, first you need to read the value of the counter (tag) from TinyDB, add 1 to it, and store the result in TinyDB again. This is very troublesome, because this counter is supposed to be used in many situations.

Persistent counter made with normal TinyDB (built-in)

To alleviate this complexity, we have created a new block to "count up one tag value" that is not found in the conventional Tiny DB. Including the original TinyDB functions, I made this name FoYoDB. As you can see, count-up part became very neat!

Persistent counter made with new FoYoDB (Extension)

In order to have versatility in this FoYoDB, we also made a block that allows you to arbitrarily specify "step value for counting up" as follows. This time, we created Extensions to extend original TinyDB, but from now on we would like to tackle the development of Extensions with higher originality.

All blocks created as an extension FoYoDB

Google Fusion Tables Turndown

One of the easy-to-use web databases on various smartphone applications is Google Fusion Tables. This has been effectively used especially in MIT App Inventor, Thunkable, AppyBuilder and others. So I was surprised at the email from Google that I received recently. In the mail, it was written as follows:

"we will be retiring Fusion Tables. We plan to turn down Fusion Tables and the Fusion Tables API on December 3, 2019. .... Maps using the Fusion Tables Layer in the Maps JavaScript API v3.37 will start to see errors in August 2019."

please see also MIT App Inventor Forum:
https://groups.google.com/forum/#!topic/mitappinventortest/Z5ft8KY93O4

Famous Pizza Party app based on Fusion Tables

In other words, the day we have to say good-by to FusionTables is coming! Besides this, there is also a key-value type Tiny WebDB as a web database that can be used from a smartphone. However, this Fusion Tables is a highly versatile SQL type, and furthermore it was superior in visualization and cooperation with maps. Retiring this valuable database makes us sad.

Let's write some memories of Fusion Tables. As an example of App Inventor app, Pizza Party using this was famous. Below are excellent commentaries, which many enthusiasts were able to create their own applications based on.

http://appinventor.mit.edu/explore/ai2/pizzaparty.html

In addition, the following Pura Vida Apps (by Taifun) has responded to various troubles in using Fusiontables. Many users will also appreciate it.

"Frequently Made Errors with Fusion Tables and how to fix them"
"How to use the Service account option to connect to a Fusion Tables"
https://puravidaapps.com/fusionservice.php

Currently, with smartphone applications, more advanced Firebase DB and CloudDB can be used. Actually in App Inventor, those functions are either built in as standard or provided as one of Extensions. In the future, these will gradually be used. 

Thank you Google Fusion Tables!

WebDB expected as a successor to Fusion Tables

共通のソースプログラムでiOS用とAndroid用のアプリを作れるThunkableX（その１）

*最後にある【ご参考事項】を補強しました。2018-6-28

これまでずっと利用してきたMIT App Inventor for AndroidとThunkableですが、限時点でThunkableの方に、大きな進展がありますので、それを試行してみます。注目点はいくつかあるのですが、共通のひとつのソースプログラム（デザインとブロック）を用いて、iOS上でもAndroid上でも実行できる！これが最大のポイントです。

さっそく、画像認識アプリを作ってみます。３つのパートの構成にしました。初級向けには、最初のPart A (または、Part A + Part B）だけでもよいかと思います。

• Part A：スマホで認識させたいものを撮影する。それをMicrosoft Recognizerに送って、何が写っているかの認識結果（英文）を表示させる。
• Part B：これと同じですが、撮影済みのPhoto Libraryにある画像も認識させる。
• Part C：認識結果に、評点と感想（コメント）を付ける。それを後で仲間とシェアするために、Media DBとRealTime DB（Firebase）に格納する。

以下に、そのソースプログラム（デザイン部とブロック部）を示します。以下がその全てです。

画像認識アプリのデザイン部

画像認識アプリのブロック部

このソースプログラム全体は、以下に公開していますので、詳細はそちらをご覧ください。ご自分のgmailアカウントに入っている状態で、下記リンクをクリックすると、自動的に、ThunkableXのプロジェクトとして、上記のソースプログラムが設定されます。

https://x.thunkable.com/copy/3a30e4c6b8b976811b85aef29bfac2e8

このソースプログラムを、iPhone用とAndroid用にビルドして、それぞれ実行させた例を以下に示します。

共通ソースプログラムからビルドして実行した例

Part Cでは、各人が色々なものを撮影して、仲間同士でその結果を検討するために、認識結果とその人の評点、コメント（意見）を保存します。撮影画像の保存は、Media DBというものに格納します。その格納場所を示すURLとその他の情報を、RealTime DB（Firebase）に格納します。

撮影画像のMedia DBへの格納例

認識結果やユーザ評点などのRealTime DBへの格納例

【ご参考事項】

今回の試行で気がついたことなどを、ご参考までに記します。

1. 上記に公開しているソースでは、Media DBとRealTIme DBを利用するためのAPIキー情報などは削除してあります。生徒らに、Part Cを使わせる場合には、管理者がこれらのAPIキーなどを取得して各人に設定させる必要があります。
2. これら２つのDBの設定については、 下記をご覧ください。Thunkable Docs→「Thunkable Cross Platform X」→「Create」→「Components」→「Data」→RealTimeDB, Media DB
3. 従来のAndroid用のThunkable(Thunkable Classic)と比べて、今回のThunkableXは、使えるセンサー類の少なさが目立ちます。またExtensions機能もありません。しかし、そうだとしても、iOSにも共通に使えるようになったメリットは非常に大きいです。不足の機能も順次追加されていくはずです。
4. iOS用のビルドには、現時点では、10分〜15分程度かかります。したがって、一定の完成度になるまでは、Live Testを使う方がよいです。WiFi環境下で、PCとiOSを接続して、リアルタイムにプログラム修正、実行ができます。Live Testには、Apple Storeにある「Thunkable Live」が必要です（→下図参照）。
5. iOSのビルド結果は、メールで通知されます。それをiOSで（PCではなく）受信して、示されたリンクをクリックするだけでインストールされます。しかしながら、現時点では、iOS側にダウンロードできるのは、１アプリに限定されています。別のアプリをダウンロードすると置き換わってしまいます。
6. iOSにビルドしたファイルをインストールする際に「信頼されていないソフト...」が表示される場合があります。「設定」→「一般」→「プロファイルとデバイス管理」ヘ進み、「Rappidly Inc」を「信頼する」にして下さい。
7. Android用にも、Live Testは使えますので重宝します。そのためには、Google Playストアにある「Thunkable Live」が必要です（→下図参照）。ビルドを行う場合、通常ほぼ直ちに結果が返ってきますが、PC側にダウンロードされるので、それをメールか、Dropboxなどを経由してAndroidにインストールする必要があるようです。
8. 今回のThunkableXと、従来のThunkableおよびMIT App Inventorとのソースレベルの互換性はほぼ全面的に失われています。iOSとの共通化のためには、全面的に設計を見直す必要があったとのことです。その意気込みは高く評価したいと思います。

Live Testに必要なアプリ

Cooperation between micro:bit and MIT App Inventor (No.3)

In the last article (No.2), communication between micro:bit and Android smartphone was done with Bluetooth UART service (serial over Bluetooth). I will also use this UART this time, but I would like to consider a simple example including NFC which is a short range wireless communication other than Bluetooth.

The figure below shows the contents. Prepared here a big toy dice. We prepared six NFC tags on which the number of eyes on each side are written, and incorporated them on each surface of the dice. Flip over the Android terminal and touch the dice on the back of it. Then the number of eyes on the opposite side of the touched surface is read. The number of eyes read is sent to micro:bit by UART communication. Pressing the micro:bit buttonA will make it receive that information and display the number of eyes on the micro:bit LED.

please see also the following youtube:
https://youtu.be/aOb69nweq3c

Using NFC in addition to BLE UART

The Android program was created using MIT App Inventor. After reading NFC tag information (number of eyes of dice), it will send the number of eyes on the opposite side of that face to micro:bit using UART. At the same time, an image corresponding to the number of eyes should be displayed on Android's screen.

Android program (reading NFC tags and sending with UART)

On the micro:bit side, pressing buttonA gets the number of eyes sent from Android, so we just display it on the LED. The function "show_spots_on_dice" is defined with JavaSript as a custom block. In this example, since we received 4 as the number of eyes, the four outer corners of the LED are lit.

micro:bit program to receive the pips of a dice and to display it on the LED board

Cooperation between micro:bit and MIT App Inventor with Eddystone signals (No.1)

Let's try to collaborate between micro:bit which is currently drawing attention and MIT App Inventor for Android. As one of them, we exchange Eddystone signals. There are several signal configurations of Eddystone, but here we deal with Eddystone-UID and Eddystone-URL among them.

Micro:bit (advertiser) and Android (receiver)

Let's perform the demonstration and watch it.
As a Microbit program, we made it possible to advertise these two types of Eddystone signals.  First, when you press micro: bit button A, it advertises the current pitch (inclination to the horizontal plane) and temperature. In the figure below, you can see that they are being received on the Android screen. That is, at the present time, the pitch of micro: bit is 30 degrees, and the temperature is found to be 26 degrees Celsius.

Pressing buttonA on the Micro:bit makes it advertise two kinds of data

Next, when pressing the micro:bit button B, a certain URL is advertised. On the screen of Android, the received contents are displayed.

Pressing buttonB on the Micro:bit makes it advertise an url of a web page

And soon, the web page for that URL was automatically displayed. In this case, it is a web page about the Akita dogs which became more famous for being given to famous Russian ice figure skater Miss Zagitova (Алина Ильназовна Загитова).

In this case, cheerful “Japanese Akita Dogs” web page is illustrated

Let's see these source programs. The following figure is a micro:bit advertising program. By pressing button A or button B you can issue either Eddysotne-UID or Eddystone-URL.

Eddystone advertising program (micro:bit)

Next is the Android program that receives Eddystone. This is made with MIT App Inventor only. It uses the extensions function for BLE (Bluetooth Low Energy), so it's very easy to write. However, the figure below shows only the essential part. By this alone, it is possible to directly acquire the content of the received data advertised. Thereafter, for example, it is necessary to decode the received URL data and convert it into a character string. It is also necessary to pass it to the Web viewer. All of them can also be written with MIT App Inventor.

Main part of Eddystone receiving program (MIT App Inventor)

please read this related article

Thanks

FoYo