Create a gist now

Instantly share code, notes, and snippets.

@mattsan /esm_doukaku_3rd.md Secret
Last active May 22, 2017

What would you like to do?
第3回 どう書く

カルキュラマシーン 〜 第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 は整数演算です。

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

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

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

主なモジュール

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

バイナリ操作

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

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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment