@bit_otter

Shrike-LiteでAtCoder問題を解く(6)：ABC456A - Dice

Last updated at 2026-07-19Posted at 2026-07-12

はじめに

前回までの準備編では、Shrike-LiteのRP2040とFPGAの間でSPI通信を行うためのテンプレートを作成しました。

今回から、いよいよAtCoder問題の実装に入ります。

最初に取り組む問題は、AtCoder Beginner Contest 456のA問題です。

ABC456A - Dice

この問題では、整数を1個受け取り、条件を満たすかどうかをYesまたはNoで出力します。

入力データは5bit、判定結果は1bitで表現できるため、SPIのMOSI・MISOともに1byteで通信できます。

Shrike-Liteへの実装を進めながら、

何を仕様として決める必要があるのか
AIへ何を伝える必要があるのか
作成された実装のどこを確認すればよいのか

を順番に整理します。

実装編の初回ですので、少し丁寧に進め方を記述するようにします。

この連載での役割分担と縛り

2026/7/19追記： 連載開始時から暗黙的に採用していた、RP2040とFPGAの役割分担および実装上の縛りを明文化するセクションを追加しました。

さて、実装の検討を始める前に、この連載でのRP2040とFPGAの役割分担を明示しておきます。

この連載では、Shrike-LiteをOut-of-box、つまり購入時の構成のまま使用します。

Shrike-Liteへジャンパケーブル、外付け回路、追加のハードウェアを接続しない
RP2040とFPGA間の通信には、Shrike-Lite基板上にあらかじめ用意された接続だけを利用する
開発は、Thonny／MicroPythonとForgeFPGA Workspaceを用いてできる範囲に限定する
テストケースはMicroPythonスクリプトへ埋め込み、外部PCからUSBシリアル通信などで逐次入力しない
RP2040では、入力データの選別、並べ替え、反転など、問題を解くためのデータ変換を行わない
RP2040側でデータを置き換えてよいのは、固有名詞を数値へ置き換える場合と、Yes／Noなどを0／1へ置き換える場合だけとする

RP2040が担当するのは、上記の縛りを破らない範囲での、テストケースの保持、FPGAへのデータ送信、FPGAから返された結果と期待値の比較、標準出力へのテスト結果表示などです。

外部PC上のThonnyはプログラムの実行や結果確認に使用しますが、問題の入力データを逐次送信するためには使用しません。

問題を解くための計算や判定は、FPGA側で行います。

今回の進め方

今回は、次の順番で仕様を決めます。

問題の解法アルゴリズムを検討する
FPGAとRP2040の役割分担を決める
SPI MOSIのフレーム構成を決める
SPI MISOのフレーム構成とSPI通信シーケンスを決める
解法アルゴリズムのVerilog実装方針を決める
RP2040のMicroPython実装方針を決める

解法だけではなく、通信フレーム、処理の分担、通信順序、出力形式などの仕様全体を考えていきます。

1. 問題の解法アルゴリズムを検討する

6面サイコロですから、Xが3以上18以下であれば、3個のサイコロの出目として作ることができます。

したがって、判定条件は次のようになります。

3 ≦ X ≦ 18 なら Yes
それ以外なら No

通常のプログラムであれば、次のような条件式で解けます。

if (X >= 3 and X <= 18) then "Yes" else "No"

今回は、この大小比較をFPGA上の回路として実装します。

2. FPGAとRP2040の役割分担を決める

Shrike-Liteには、MicroPythonを実行するRP2040と、Verilogで作成した回路を動かすForgeFPGAが搭載されています。

今回は、次のように役割を分担します。

処理	担当
MicroPython内に用意したテストケースから`X`を取り出す	RP2040
`X`を5bitデータとしてFPGAに送る	RP2040
`3 ≦ X ≦ 18`を判定する	FPGA
判定結果を1bitで返す	FPGA
1bitの結果を`Yes`または`No`へ変換し、期待値と比較する	RP2040
TX、RX、期待値、判定結果、処理時間をケースごとに表示する	RP2040

処理の流れは、次のようになります。

FPGAから文字列のYesやNoをASCIIバイトとして返すことも可能ですが、FPGA側の回路を小さく保つために、FPGAは判定結果だけを1bitで返します。

文字列への変換、期待値との比較、テスト結果の表示はRP2040に担当してもらうことにします。

3. SPI MOSIのフレーム構成を決める

問題の入力制約は、次のようになっています。

1 ≦ X ≦ 20

20は2進数で10100なので、Xは5bitで表現できます。

SPIでは1回に1byteを送受信するため、MOSIの下位5bitへXを格納します。

残った上位3bitは、SPIコマンドとして使用します。

bit 7                bit 5 bit 4                 bit 0
+-------------------------+----------------------------+
|       COMMAND[2:0]      |          DATA[4:0]         |
+-------------------------+----------------------------+

今回使用するコマンドは、次の4種類です。

コマンド	COMMAND	用途
`NOP`	`000`	FPGAから返信を読み出す or 待機
`SEND_X`	`001`	`X`をFPGAへ送る
`DEBUG`	`110`	デバッグ用
`RESET`	`111`	FPGA側の返信データを初期化する

コマンド値を16進数で表すと、次のようになります。

コマンド	送信byte
`NOP`	`0x00`
`SEND_X`	`0x20 \| X`
`DEBUG`	`0xC0`
`RESET`	`0xE0`

たとえば、X=15の場合、SEND_Xで送信するbyteは次のようになります。

COMMAND = 001
DATA    = 01111

0010_1111 = 0x2F

DEBUGは準備編で作成したテンプレートのデバッグ機能を維持するために残します。

ABC456Aの通常処理では使用しません。

SEND_X以外のコマンドでは、下位5bitを0として送信します。

4. SPI MISOのフレーム構成を決める

FPGAからRP2040へ返す判定結果は1bitです。

今回は、MISOの最上位bitをREPLY、最下位bitをANSWERとして使用します。

bit 7 bit 6                           bit 1 bit 0
+--------+----------------------------------+--------+
| REPLY  |             reserved             | ANSWER |
+--------+----------------------------------+--------+

各bitの意味は次のとおりです。

bit	名前	内容
7	`REPLY`	有効な判定結果が格納されている場合に`1`
6～1	予約	今回は常に`0`
0	`ANSWER`	`1`ならYes、`0`ならNo

MISOの値は、次の3種類になります。

MISO	意味
`0x81`	有効な返信で、答えはYes
`0x80`	有効な返信で、答えはNo
`0x00`	有効な返信なし

ANSWER=0だけでは、答えがNoなのか、まだ回答が準備できていないのかを区別できませんので、REPLYビットを設けて、有効な判定結果の有無をRP2040側で判別できるようにします。

SPIの送受信シーケンス

SPIでは、MOSIによる送信とMISOによる受信が同時に行われます。

FPGAはSEND_Xの1byteを受信した後にXを判定するため、その判定結果は次のSPI通信で読み出します。

また、MISOからREPLYを受け取ったら、その次のMOSI送信ではRESETを送ります。さらにNOPを送り、FPGAを次の入力待ち状態（WAIT）にします。

今回の通信シーケンスは、次のようにします。

処理を文章にすると、次の順番です。

RESETを送り、FPGA側の返信データを初期化する
NOPを送り、FPGAをWAIT状態にする
SEND_XでXを送る
FPGAがXを判定し、返信データを準備する
NOPを送り、REPLYとANSWERを読み出す
REPLYを受け取った直後の次のMOSI送信でRESETを送る
NOPを送り、FPGAを再びWAIT状態にして次の入力を待つ

RESET送信時にMISOから受信する値は使用しません。

ここでいうWAIT状態は、明示的なFSM状態ではなく、返信データが0x00で次のコマンドを待っている状態を指します。

この通信シーケンスも、AIに伝えることを忘れないようにしましょう。

5. 解法アルゴリズムのVerilog実装方針を決める

今回の判定回路は単純です。

受信したXに対して、次の二つを比較します。

X < 3
X > 18

どちらか一方でも成立すれば、答えはNoです。

どちらも成立しなければ、3 ≦ X ≦ 18なので答えはYesです。

回路としては、二つの比較器の出力をNORすれば判定結果を作れます。

ANSWER = NOT（X < 3 OR X > 18）

Verilogでは、たとえば次のように記述できます。

wire x_less_than_3;
wire x_greater_than_18;
wire answer;

assign x_less_than_3     = (rx_data[4:0] < 5'd3);
assign x_greater_than_18 = (rx_data[4:0] > 5'd18);

assign answer = ~(x_less_than_3 | x_greater_than_18);

この記述で作成される回路は次のようなものになります。

SEND_Xコマンドを受信したら、作成したanswerをMISO送信用レジスタへ格納します。

REPLY  = 1
ANSWER = answer

MISO送信用データは、次のようになります。

{1'b1, 6'b000000, answer}

RESETを受信した場合は、MISO送信用データを0x00へ戻します。

回答を読み出した直後にRESETを受信し、その次のNOPで0x00を返してWAIT状態に戻ります。

今回の問題固有回路は、5bit比較器が二つとNORだけです。

この程度であれば自分でVerilogを書いてもよい規模ですが、準備編で作成したSPIテンプレートのどこへ接続するかは確認が必要です。

特に、次の点を区別します。

SPIから受信したデータを保持するレジスタ
MISOで返すデータを保持するレジスタ

判定結果を書き込む先は、次のSPI通信で送信するためのMISO送信用レジスタです。

6. RP2040のMicroPython実装方針を決める

今回は、標準入力から値を1個読み込む版ではなく、MicroPython内に複数のテストケースを用意し、それらを順番にFPGAへ送り込むテスト版を実装します。

MicroPythonファイル名は、テスト用であることが分かるようにabc456a_test.pyとします。

テストケースは、境界値を中心に次の値を使用します。

test_cases = [
    (1, "No"),
    (2, "No"),
    (3, "Yes"),
    (15, "Yes"),
    (18, "Yes"),
    (19, "No"),
    (20, "No"),
]

RP2040側では、次の処理を行います。

FPGAへabc456a.binを書き込む
SPIを初期化する
RESETを送る
NOPを送り、FPGAをWAIT状態にする
テストケースからXと期待値を取り出す
SEND_XでXを送る
NOPを送り、判定結果を受け取る
REPLYとANSWERを取り出す
ANSWERをYesまたはNoへ変換し、期待値と比較する
TX、RX、期待値、結果、PASS／FAIL、処理時間を1行で表示する
RESETを送る
NOPを送り、FPGAをWAIT状態に戻す
すべてのテストケースについて5～12を繰り返す
最後にテスト全体の集計と概算処理時間を表示する

MicroPython側では、受信した1byteから次のようにbitを取り出せます。

reply = (rx >> 7) & 0x01
answer = rx & 0x01

REPLY=1であることを確認した後、ANSWERを文字列へ変換します。

result = "Yes" if answer else "No"

テスト結果は、1ケースにつきおおむね1行で確認できる形にします。

X=3 TX=0x23 RX=0x81 EXPECT=Yes RESULT=Yes PASS TIME_US=...

処理時間を測定する

おおよその処理性能を把握するために、実装の動作時間を測定できるようにします。

MicroPythonのtime.ticks_us()とtime.ticks_diff()を使い、各テストケースについて、SEND_Xを送る直前からREPLYを受信するまでのおおよその処理時間を測定します。

start_us = time.ticks_us()

# SEND_X送信
# NOPでREPLY受信

elapsed_us = time.ticks_diff(time.ticks_us(), start_us)

また、全テストケースを実行するために要した合計時間も最後に表示します。

各ケースの測定値にはMicroPythonとSPI通信の処理時間が含まれます。また、全体時間にはテスト結果の表示時間も含まれるため、厳密なFPGA処理時間ではありませんが、これでヨシとします。

テンプレートをコピーして実装用プロジェクトを作る

仕様が決まったら、準備編で作成したテンプレートをコピーし、ABC456A用の実装プロジェクトを作ります。

作業の流れは次のとおりです。

atcoder_spi_templateフォルダをコピーする
コピーしたフォルダ名をabc456aへ変更する
フォルダ内のatcoder_spi_template.ffpgaをabc456a.ffpgaへ変更する
abc456a.ffpgaをForgeFPGA Workspaceで開く
main.vとspi_target.vがプロジェクトへ登録されていることを確認する
MicroPythonのテストファイル名をabc456a_test.pyとする
ビルド後のbitstream名をabc456a.binとする

.ffpgaファイルはForgeFPGA Workspaceのプロジェクトファイルです。

元のテンプレートを直接変更せず、問題ごとにコピーして使用することで、共通部分をいつでも再利用できます。

Verilogを実装して合成し、bitstreamを作成する

ForgeFPGA Workspace上で、main.vの問題ごとに変更する部分セクションを変更して保存します。

    // ===== 問題ごとに変更する部分 =====
	// 今回はABC456Aの回答回路
	// RP2040から受信したrx_dataから下位5bitを取り出し、3未満 / 18より大きいか
	// どうかを比較し、両者をNORで判定する。
	// 判定結果はtx_dataレジスタにセットし、次のSPI通信で返信する
    
    wire x_less_than_3;
	wire x_greater_than_18;
	wire answer;
	wire [2:0] cmd;
	
	assign cmd = rx_data[7:5];
	
	localparam NOP    = 3'b000;
	localparam SEND_X = 3'b001;
	localparam DEBUG  = 3'b110;
	localparam RESET  = 3'b111;

	assign x_less_than_3     = (rx_data[4:0] < 5'd3);
	assign x_greater_than_18 = (rx_data[4:0] > 5'd18);

	assign answer = ~(x_less_than_3 | x_greater_than_18); 
    
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            tx_data <= 8'h00;
        end else if (rx_data_valid) begin
        	case (cmd)        	
        		NOP:     tx_data <= 8'h00;
        		SEND_X:  tx_data <= {1'b1, 6'b000000, answer};        		
        		DEBUG:   ; // Do nothing
        		RESET:   tx_data <= 8'h00;
        		default: ; // Do nothing
        	endcase
        end
    end

保存が終わったら合成し、bitstreamを作成します。

実機での合成結果は以下のようになりました。まだまだ余裕がありますね。

bitstreamファイルの生成が済んだら FPGA_bitstream_MCU.bin を abc456a.binにリネームして bitstreamフォルダに保存します。

AIへMicroPythonコードの実装を依頼する

次はMicroPythonのテストプログラムをAIへ依頼してみます。

今回は、既存のatcoder_spi_template_test.pyを参考にして、ABC456A用のabc456a_test.pyを作成してもらいます。

依頼文の例は、次のようになります。

Shrike-LiteでABC456A - Diceをテストするための
MicroPythonプログラムを作成してください。

既存の atcoder_spi_template_test.py を参考にして、
abc456a_test.py を新規作成してください。

FPGAのbitstream名は abc456a.bin です。

既存テンプレートの以下の部分は、そのまま使用してください。

- Shrike-Liteへのbitstream書き込み処理
- SPIの初期化処理
- SPIのピン設定
- SPIの周波数
- CPOLおよびCPHAの設定
- FPGAリセット処理
- 1byteのSPI送受信処理

main.v、spi_target.v、abc456a.ffpga、abc456a.binは変更しないでください。

ABC456A固有の仕様は、次のとおりです。

テストケース：
- 標準入力は使用しない
- MicroPython内に、Xと期待結果の組を用意する
- 次のテストケースを順番に実行する

    (1, "No")
    (2, "No")
    (3, "Yes")
    (15, "Yes")
    (18, "Yes")
    (19, "No")
    (20, "No")

MOSIフレーム：
- bit7:5をCOMMANDとする
- bit4:0をDATAとする

コマンド：
- NOP    = 0b000
- SEND_X = 0b001
- DEBUG  = 0b110
- RESET  = 0b111

SEND_Xの送信byteは、次の式で作成すること。

    (SEND_X << 5) | X

RESET、NOP、DEBUGでは、DATAを0とすること。
DEBUGは通常処理では使用しないこと。

MISOフレーム：
- bit7をREPLYとする
- bit0をANSWERとする
- bit6:1は使用しない

MISOの意味：
- 0x81：有効な返信、答えはYes
- 0x80：有効な返信、答えはNo
- 0x00：有効な返信なし

SPI通信は、次の順番で行うこと。

初期化：
1. RESETを送信する
2. NOPを送信し、FPGAをWAIT状態にする

各テストケース：
1. SEND_XでXを送信する
2. NOPを送信し、判定結果を受信する
3. REPLYを受信した直後の次のMOSI送信でRESETを送信する
4. NOPを送信し、FPGAをWAIT状態に戻す

RESET、WAIT用NOP、SEND_Xで受信したMISOデータは使用しないこと。

判定結果を読み出したら、bit7のREPLYを確認すること。
REPLYが0の場合は、RESULTをNO_REPLYとしてFAILにすること。
1件がFAILになっても、残りのテストケースを続けること。

REPLYが1の場合は、bit0のANSWERを確認すること。

- ANSWER=1なら Yes
- ANSWER=0なら No

へ変換し、テストケースの期待結果と比較すること。

各テストケースについて、次の情報をおおむね1行で表示すること。

- X
- SEND_Xで送信したTXデータ
- NOPで受信したRXデータ
- 期待結果
- FPGAから得た結果
- PASSまたはFAIL
- おおよその処理時間（マイクロ秒）

出力例：

    X=3 TX=0x23 RX=0x81 EXPECT=Yes RESULT=Yes PASS TIME_US=...

処理時間の測定には、MicroPythonのtime.ticks_us()と
time.ticks_diff()を使用すること。

各テストケースについて、SEND_Xを送信する直前から、
NOPでREPLYを受信するまでの時間を測定すること。

すべてのテストケースが終了したら、
PASS数、FAIL数、全体の概算処理時間を表示すること。

厳密な時間測定は不要であり、
USB出力やMicroPythonの処理時間が含まれてもよい。

共通処理とABC456A固有処理が分かるように、
ソースコード内へコメントを追加してください。

優秀なコーディングスキルを持ったAIに期待通りの働きをしてもらいましょう。

AIが作成したコード例（全文）

from machine import Pin, SPI
import time
import shrike

# ===== Shrike-Lite共通処理 =====
BITSTREAM = "abc456a.bin"

SCK = 2
CS = 1
MOSI = 3
MISO = 0
FPGA_RESET = 14

shrike.reset()
shrike.flash(BITSTREAM)

reset_pin = Pin(FPGA_RESET, Pin.OUT, value=1)
reset_pin.value(0)
time.sleep_ms(100)
reset_pin.value(1)
time.sleep_ms(100)

cs = Pin(CS, Pin.OUT, value=1)

spi = SPI(
    0,
    baudrate=1_000_000,
    polarity=0,
    phase=0,
    bits=8,
    firstbit=SPI.MSB,
    sck=Pin(SCK),
    mosi=Pin(MOSI),
    miso=Pin(MISO)
)


def spi_exchange(value):
    tx = bytes([value])
    rx = bytearray(1)

    cs.value(0)
    spi.write_readinto(tx, rx)
    cs.value(1)

    return rx[0]


# ===== ABC456A固有処理 =====
NOP = 0b000
SEND_X = 0b001
DEBUG = 0b110
RESET = 0b111

TEST_CASES = [
    (1, "No"),
    (2, "No"),
    (3, "Yes"),
    (15, "Yes"),
    (18, "Yes"),
    (19, "No"),
    (20, "No"),
]


def make_command(command, data=0):
    return (command << 5) | (data & 0x1F)


def decode_reply(rx):
    if (rx & 0x80) == 0:
        return "NO_REPLY"
    if (rx & 0x01) != 0:
        return "Yes"
    return "No"


spi_exchange(make_command(RESET))
spi_exchange(make_command(NOP))

pass_count = 0
fail_count = 0
total_start = time.ticks_us()

for x, expected in TEST_CASES:
    tx = make_command(SEND_X, x)

    start = time.ticks_us()
    spi_exchange(tx)
    rx = spi_exchange(make_command(NOP))
    elapsed = time.ticks_diff(time.ticks_us(), start)

    result = decode_reply(rx)
    ok = result == expected

    if ok:
        pass_count += 1
        status = "PASS"
    else:
        fail_count += 1
        status = "FAIL"

    print(
        "X={} TX=0x{:02X} RX=0x{:02X} EXPECT={} RESULT={} {} TIME_US={}".format(
            x,
            tx,
            rx,
            expected,
            result,
            status,
            elapsed
        )
    )

    spi_exchange(make_command(RESET))
    spi_exchange(make_command(NOP))

total_time = time.ticks_diff(time.ticks_us(), total_start)

print(
    "SUMMARY PASS={} FAIL={} TOTAL_TIME_US={}".format(
        pass_count,
        fail_count,
        total_time
    )
)

AIが作成したコードを確認する

AIがコードを作成したら、実機で動かす前に仕様どおりになっているかを確認します。

今回の主な確認項目は次のとおりです。

確認項目	確認内容
MicroPythonファイル名	`abc456a_test.py`になっているか
bitstream名	`abc456a.bin`になっているか
SPI設定	テンプレートから変更されていないか
テストケース	指定した7ケースが登録されているか
MOSI	上位3bitがコマンド、下位5bitが`X`か
通信順序	`RESET → NOP（WAIT）`の後、各ケースで`SEND_X → NOP（REPLY）→ RESET → NOP（WAIT）`となっているか
MISO	bit7を`REPLY`として確認しているか
判定結果	bit0を`ANSWER`として使用しているか
結果表示	TX、RX、期待値、結果、PASS／FAILがケースごとに表示されるか
時間測定	各ケースと全体の概算時間が測定されるか
エラー処理	`REPLY=0`でも残りのテストを継続するか
変更範囲	指定していないファイルを変更していないか

コードが動くことだけでなく、決めた仕様に従っていることも確認しておくと安心ですね。

コード作成を依頼するAIとは別のAIにコードチェックを依頼するのもいいと思います。

動作確認

作成した abc456a_test.py と abc456a.bin をShrike-LiteのUSBドライブにコピーします。

コピーが済んだらThonnyでabc456a_test.py を開き、実行ボタンで実行します。

Pythonスクリプトに含まれるテストケースは以下の通りです。

X	送信するTX	期待する結果	確認内容
1	`0x21`	`No`	入力制約の最小値
2	`0x22`	`No`	下限の直前
3	`0x23`	`Yes`	Yesとなる最小値
15	`0x2F`	`Yes`	入力例1
18	`0x32`	`Yes`	Yesとなる最大値
19	`0x33`	`No`	上限の直後
20	`0x34`	`No`	入力制約の最大値

以下は手元の実機でテストした結果です。

X=1 TX=0x21 RX=0x80 EXPECT=No RESULT=No PASS TIME_US=392
X=2 TX=0x22 RX=0x80 EXPECT=No RESULT=No PASS TIME_US=394
X=3 TX=0x23 RX=0x81 EXPECT=Yes RESULT=Yes PASS TIME_US=396
X=15 TX=0x2F RX=0x81 EXPECT=Yes RESULT=Yes PASS TIME_US=393
X=18 TX=0x32 RX=0x81 EXPECT=Yes RESULT=Yes PASS TIME_US=401
X=19 TX=0x33 RX=0x80 EXPECT=No RESULT=No PASS TIME_US=395
X=20 TX=0x34 RX=0x80 EXPECT=No RESULT=No PASS TIME_US=406
SUMMARY PASS=7 FAIL=0 TOTAL_TIME_US=14913

1ケース当たりの所要時間は約0.4 msのようですね。ACがとれそうです。

すべてのテストケースで期待結果と一致すれば、ABC456Aの実装は完了です。

今回のまとめ

今回は、ABC456A - Diceの回答回路をShrike-Liteへ実装するための仕様決めと実装をしました。

問題の解法は、次の大小比較だけです。FPGA側の問題固有回路も、二つの5bit比較器とNORだけで作れます。

一方、Shrike-Liteで実際に問題を解くためには、解法以外にも次の仕様検討が必要でした。

RP2040とFPGAの役割分担
MOSIのフレーム構成
MISOのフレーム構成
SPIコマンド
SPIの送受信シーケンス
Verilogの実装方針
MicroPythonの実装方針
AIへ変更を許可する範囲
テストケースと表示形式
処理時間の測定方法
動作確認方法

タイパは最悪ですが、これで実際の問題をShrike-Liteで解いてみることができました。

次回

次回は1バイトに収まりきらない問題をどのようにRP2040からForgeFPGAに受け渡すか、という主題で問題を実装してみます。お楽しみに。

前回: Shrike-LiteでAtCoder問題を解く(5) 準備編⑤：公式サンプルからSPI Slave機能を取り込み、AtCoder実装テンプレートを作る

次回: Shrike-LiteでAtCoder問題を解く(7)：ABC466A - Compromise

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up