第3回 どう書く

esm_doukaku_3rd.md

カルキュラマシーン 〜 第3回 ESM どう書く (2017/05/18)

符号化された入力を受け取り、復号し、計算し、解を符号化して出力する計算機を作成してください。

問題

下記のようなルールで計算式をエンコードした文字列があります。

これを次の手順に従って処理を行い結果を取得してください。

1. まず、これをデコードして計算式を取得します
2. 次に、計算式を評価して解を求めます
3. 最後に、エンコードのルールで解をエンコードします

文字	符号
0	00
1	01
2	100
3	1010
4	1011
5	1100
6	11010
7	11011
8	111000
9	111001
+	1110100
-	1110101
*	1110110
/	1110111

ルール

入力は、有効ビット数を10進数で表現した文字列と、エンコードされたビット列を16進数で表現した文字列を : で連結した文字列です。

例：

入力	計算式をエンコードした値（16進数表現）	有効ビット数
27:675AED8	675AED8	27

計算式は次の要素で構成されます。

• オペランドは正の整数のみ
• 演算は 6 種類で、すべて整数演算（除算は小数部を切り捨て）

括弧や空白は含みません。

オペランドは正の整数のみですが、解は負の整数になる場合があります。

演算の種類と演算子：

演算	演算子
加	+
減	-
乗	*
除	/
冪	**
剰余	//

演算子の優先順位：

演算子	優先順位
**	高
*, /, //	中
+, -	低

演算子の結合性：

演算子	結合性
**	右結合
*, /, //, +, -	左結合

例

入力

27:675AED8

指定された数のビットを先頭から取り出す

6	7	5	A	E	D	8
0110	0111	0101	1010	1110	1101	1000

27 ビット	パディング（使用しない）
011001110101101011101101100	0

デコードする

01	100	1110101	1010	1110110	1100
1	2	-	3	*	5

12-3*5

演算する

12-3*5 => -3

エンコードする

-3

-	3
1110101	1010

16 進数で表現する

ビット数が 4 の倍数になるようにする（16 進数として表現できるようにする）ために 0 でパディングする

11 ビット	パディング
11101011010	0

1110	1011	0100
E	B	4

有効ビット数を先頭に追加する

10 進数で先頭に追加する

出力

11:EB4

補足

• 不正な入力に対応する必要はありません  - 復号できない入力や、演算できない式を考慮する必要はありません
• 書いたコードは社内から参照できる場所にアップしていただき、リンクを連絡していただけると助かります。 アップ先は GitHub, Qiita, esa.io などの公のサービスでも構いません。

Elixir/Erlang のためのヒント

除

Elixir の除算には / と div があります。/ は浮動小数点演算、div は整数演算です。

• //2
• div/2

冪

冪演算には Erlang の math モジュールの pow を利用できます。ただし値が浮動小数点数なので round で整数にする必要があります。

今回のケースでは利用できませんでした！　ごめんなさい！

:math.pow では有効桁数が足りないため、正しく計算できないテストケースがあります。

• 例： round(:math.pow(2, 10)) # => 1024
• pow/2
• round/1

主なモジュール

主なモジュールのドキュメントです。

• Enum
• Integer
• List
• String
• Regex
• binary （Erlang のモジュール）

バイナリ操作

バイナリ操作に関するドキュメントです。

• Elixir
  • Binaries, strings, and char lists
  • Bitstring generators - Comprehensions
• Erlang
  • Bit Syntax
  • Constructing and Matching Binaries
  • binary module

Erlang と Elixir のバイナリの表現の違い

Erlang	Elixir
<<123:10>>	<<123::size(10)>> または <<123::10>>
<<A/bitstring>>	<<a::bitstring>>

テストデータ

入力	出力
27:675AED8	11:EB4
21:BCE8E0	7:D0
21:D1D760	11:EA8
22:E676A0	15:9BD0
22:E4EFB0	2:4
29:AE3B76D8	44:5BB733899CC
26:B7BF76C	6:68
34:D3D2E7490	9:660
41:E4EAF1D79D0	14:EB2C
45:BAED9AEDC720	20:8DD30
52:C33B769DFBEF9	6:68
54:64EDC671DFBAEC	11:DF0
49:D35D752FA66E0	11:CD2
51:ACD76A39EF354	12:B78
58:E2F3BDE73DB5BE4	16:D6F9
66:68EDC39D666BBBC6C	24:4CE6F9
63:ACB3AF172BBCE2B6	18:ACAE0
50:E6FB71C77DE84	2:4
94:A26BAEB9E6FAEB8D4EBC1BE0	29:EAF1C9C0
63:B9DBB5D77EF57CF0	12:9A4
49:6BB47AF13BE50	11:9B8
58:E5E9C6BB66FAF30	14:BE44
41:E3B76CEDDA0	103:ADEF7C734F1A9CE6DD3B39CD70
53:95ACEFDD3BF780	4:C
23:9DBB20	116:66B7AC341271273637CEB65432B7A

コード形式

test("27:675AED8", "11:EB4")
test("21:BCE8E0", "7:D0")
test("21:D1D760", "11:EA8")
test("22:E676A0", "15:9BD0")
test("22:E4EFB0", "2:4")
test("29:AE3B76D8", "44:5BB733899CC")
test("26:B7BF76C", "6:68")
test("34:D3D2E7490", "9:660")
test("41:E4EAF1D79D0", "14:EB2C")
test("45:BAED9AEDC720", "20:8DD30")
test("52:C33B769DFBEF9", "6:68")
test("54:64EDC671DFBAEC", "11:DF0")
test("49:D35D752FA66E0", "11:CD2")
test("51:ACD76A39EF354", "12:B78")
test("58:E2F3BDE73DB5BE4", "16:D6F9")
test("66:68EDC39D666BBBC6C", "24:4CE6F9")
test("63:ACB3AF172BBCE2B6", "18:ACAE0")
test("50:E6FB71C77DE84", "2:4")
test("94:A26BAEB9E6FAEB8D4EBC1BE0", "29:EAF1C9C0")
test("63:B9DBB5D77EF57CF0", "12:9A4")
test("49:6BB47AF13BE50", "11:9B8")
test("58:E5E9C6BB66FAF30", "14:BE44")
test("41:E3B76CEDDA0", "103:ADEF7C734F1A9CE6DD3B39CD70")
test("53:95ACEFDD3BF780", "4:C")
test("23:9DBB20", "116:66B7AC341271273637CEB65432B7A")