Scratchで基本情報技術者試験問8（令和元年秋期：Bitap法による文字列検索)をプログラムしてみました。


最近、Scratchという子ども向けの言語学習環境が凄いと思うようになりました。

本格的なプログラムも書けるのではないかと思い、試してみました。

（普通に解こうとしたのですが、難しく、、解答を見ないと出来ませんでした。大雑把な性格なので、アルゴリズム結構苦手です。。）

IPAの過去問は、こちらです。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2019h31.html#01aki

----------------------------------------------------------------------------
##はじめに用意するブロック定義
###ブロック定義：Index、ブロック定義：論理左シフト演算、ブロック定義：論理和、ブロック定義：論理積を用意する必要があります。

----------------------------------------------------------------------------
###ブロック定義：Index
###（関数Index）
「関数Indexは、引数にアルファベット順でn番目の英大文字を設定して呼び出すと、整数n（1<= n <=26）を返す。」と、問題文に書かれています。関数Indexに該当するブロック定義を用意します。
（「alphabetList」というリストを作成して、線形探索してます。）

引数「n番目の英大文字」、返却値の整数nは、変数「n」に格納します。
![ブロック定義_Index.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/ad824a7a-ff5b-66a9-8639-6249434b2b04.png)

----------------------------------------------------------------------------
###ブロック定義：論理左シフト演算
第一引数「二進数」、第二引数「シフト数」として、
演算結果を変数「左シフト出力」に出力します。
（[SCRATCH Japan wikiの「二進数」](https://ja.scratch-wiki.info/wiki/%E4%BA%8C%E9%80%B2%E6%95%B0)という記事を参考にして、作成しています。）
![ブロック定義_論理左シフト演算.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/38a2542a-6dda-47dd-df09-0dd9b600674d.png)

----------------------------------------------------------------------------
###ブロック定義：論理和
第一引数「二進数-1」、第二引数「二進数-1」として、
演算結果を変数「論理和出力」に出力します。
（[SCRATCH Japan wikiの「二進数」](https://ja.scratch-wiki.info/wiki/%E4%BA%8C%E9%80%B2%E6%95%B0)という記事をもとに作成しています。）
![ブロック定義_論理和.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/56959fa4-43d8-6479-0e86-35e09764b9bd.png)

----------------------------------------------------------------------------
###ブロック定義：論理積
第一引数「二進数-1」、第二引数「二進数-1」として
演算結果を変数「論理積出力」に出力します。
（[SCRATCH Japan wikiの「二進数」](https://ja.scratch-wiki.info/wiki/%E4%BA%8C%E9%80%B2%E6%95%B0)という記事をもとに作成しています。）
![ブロック定義_論理積.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/c1ac2b5c-41ad-c754-8a16-148782106030.png)

----------------------------------------------------------------------------
##TextListの作成
対象文字列を格納するリストを作成します。
![ブロック定義_MakeTextList.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/06c96d27-c443-cd85-bed7-a34da05c5790.png)

----------------------------------------------------------------------------
##PatListの作成
検索文字列を格納するリストを作成します。（下の写真は設問1、設問2）
![ブロック定義_MakePatList.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/a92b83c0-dd30-de99-cb15-bf1d42364c36.png)


----------------------------------------------------------------------------
##MakeMaskListの作成
ビットマスクを格納するリストを作成します。
![ブロック定義_MakeMaskList.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/1dc1dc98-9f83-076a-6798-b3d3b70084b5.png)


----------------------------------------------------------------------------
#ここから、試験問題のプログラムです。
##プログラム1
###ブロック定義：GenerateBitMask
###（整数型関数：GenerateBitMask）
第一引数「PatList」、第二引数「MaskList」

（スクラッチの仕様上、第二引数「MaskList」は使用していませんが、試験の関数に近づけるため置いています。）

返却値の検索文字列の文字数は、変数「PatLen」に格納します。

![プログラム1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/eca2ddc1-3924-21eb-1eab-4d2b6cb8764e.png)


----------------------------------------------------------------------------
##プログラム2
###ブロック定義：BitapMatch
###（整数型関数：BitapMatch）
第一引数「TextList」、第二引数「PatList」

返却値の代わりに、スプライト（ねこ）に、対象文字列中に検索対象文字列が見つかった場合、
一致した文字列の先頭の文字に対応する対象文字列の要素の要素番号を、
検索文字列が見つからなかった場合は、-1を言うようにしています。


![プログラム2.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/28e86f67-715c-8db5-04e1-04dd96f862cc.png)

----------------------------------------------------------------------------
##プログラム3
###ブロック定義：GenerateBitMaskRegex
###（整数型関数：GenerateBitMaskRegex）
第一引数「PatList」、第二引数「MaskList」

（スクラッチの仕様上、第二引数「MaskList」は使用していませんが、試験の関数に近づけるため置いています。）

返却値の検索文字列の文字数は、変数「PatLen」に格納します。

![プログラム3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/b1390e88-0659-1614-62b6-986e7e2bcc09.png)

----------------------------------------------------------------------------
##プログラムの実行
TextListを作成、PatListを作成、MaskListを作成し、関数BitapMatchを実行しています。
![プログラム実行.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/b0a8597f-32f0-cc99-a660-d4c2c3b79557.png)


----------------------------------------------------------------------------
##実行結果
###ちゃんと動いています。
![解答2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606075/119302c2-e3c8-fe3e-801b-6a5ce0262093.png)