プログラミング言語

Codewars（python）練習ノート23：Brainfuck Translator（Brainfuck翻訳）



Codewars Practice Notes Twenty Three



トピック

前書き

Brainfuckは、最もよく知られている難解プログラミング言語の1つです。ただし、5文字を超えるコードを理解するのは難しい場合があります。このカタでは、その問題を解決する必要があります。

説明

このカタでは、3つのタスクを実行する関数を作成する必要があります。



  1. Optimize the given Brainfuck code.
  2. Check it for mistakes.
  3. Translate the given Brainfuck programming code into C programming code.

各タスクについてより正式に：

  1. 関数は、 '+-'、 ''、 '[]'などのすべての役に立たないコマンドシーケンスをソースコードから削除する必要があります。また、+-,. []を除くすべての文字を消去する必要があります。
    例：
'++--+.' -> '+.' '[][+++]' -> '[+++]' '> ''

  1. ソースコードにペアになっていない中括弧が含まれている場合、関数は「エラー！」を返す必要があります。ストリング。



  2. 関数は、次のようにCプログラミングコードの文字列を生成する必要があります。

  • Xコマンド+または-のシーケンスは、* p + = X nまたは* p- = X nに置き換える必要があります。

例：

'++++++++++' -> '*p += 10 ' '------' -> '*p -= 6 '
  • Yコマンドのシーケンス>または例：
'>>>>>>>>>>' -> 'p += 10 ' '<<<<< 'p -= 6 '
  • 。コマンドはputchar（* p） nに置き換える必要があります。
    例：
'..' -> 'putchar(*p) putchar(*p) '
  • 、コマンドは* p = getchar（） nに置き換える必要があります。
    例：
',' -> '*p = getchar() '
  • [コマンドはif（ p）{ nを実行します。 ]コマンドは} while（ p） n。
    例：
'[>>]' -> if (*p) do { p += 2 } while (*p)
  • コードブロック内の各コマンドは、前のコードブロックに応じて右に2スペースシフトする必要があります。
    例：
'[>>[

例

Input: +++++[>++++.<-] Output: *p += 5 if (*p) do { p += 1 *p += 4 putchar(*p) p -= 1 *p -= 1 } while (*p)

サンプルテスト

def testing(code, expected): result = brainfuck_to_c(code) test.assert_equals(result, expected) test.describe('general tests') test.it('basic') testing('++++', '*p += 4 ') testing('----', '*p -= 4 ') testing('>>>>', 'p += 4 ') testing('<<< <<', 'p -= 1 ') testing('[[.]]', 'if (*p) do { if (*p) do { putchar(*p) } while (*p) } while (*p) ')

私の解決策

元のバージョン：

#!/usr/bin/python def brainfuck_sum(l): r = '' if l['key'] == '+': r = '*p += ' + str(l['value']) + ' ' if l['key'] == '-': r = '*p -= ' + str(l['value']) + ' ' if l['key'] == '': r = 'p += ' + str(l['value']) + ' ' return r def brainfuck_add(i): r = '' if i == ',': r = '*p = getchar() ' if i == '.': r = 'putchar(*p) ' if i == '[': r = 'if (*p) do { ' if i == ']': r = '} while (*p) ' return r def brainfuck_retract(i, p): r = '' p_count_l = p[0:i].count('[') p_count_r = p[0:i+1].count(']') p_count = p_count_l - p_count_r for t in range(p_count): r += ' ' return r def brainfuck_to_c(source_code): p = source_code for i in p: if i not in ['+', '-', '', '.', ',', '[', ']']: p = p.replace(i, '') while '+-' in p or '-+' in p or '' in p or '><' in p or '[]' in p: p = p.replace('+-', '').replace('-+', '').replace('', '').replace('><', '').replace('[]', '') if '[' in p or ']' in p: if p.count('[') != p.count(']') or p.index('[')> p.index(']'): return 'Error!' r = '' l = {'key': 'p', 'value': 0} for i in range(len(p)): r += brainfuck_retract(i, p) r += brainfuck_add(p[i]) if p[i] == '' or '+' or '-': if p[i] == l['key']: l['value'] += 1 else: r += brainfuck_sum(l) l['key'] = p[i] l['value'] = 1 else: r += brainfuck_sum(l) l['key'] = '' l['value'] = 0 if l['value'] != 0: r += brainfuck_sum(l) return r

部分的に最適化されたバージョン：

ソリューションコードが冗長すぎて、境界テストを実行するとメモリが過負荷になるため、コードを最適化します。
それを簡単に見て、whileループの一部を削除し、アイデアを最適化して、コードの実行を確認することにしました。



#!/usr/bin/python def brainfuck_sum(l): r = '' if l['key'] == '+-': if l['value'] > 0: r = '*p += ' + str(l['value']) + ' ' elif l['value'] <0: r = '*p -= ' + str(-l['value']) + ' ' if l['key'] == '': if l['value'] 0: r = 'p += ' + str(l['value']) + ' ' return r def brainfuck_add(i): r = '' if i == ',': r = '*p = getchar() ' if i == '.': r = 'putchar(*p) ' if i == '[': r = 'if (*p) do { ' if i == ']': r = '} while (*p) ' return r def brainfuck_retract(i, p): r = '' p_count_l = p[0:i].count('[') p_count_r = p[0:i+1].count(']') p_count = p_count_l - p_count_r for t in range(p_count): r += ' ' return r def brainfuck_to_c(source_code): p = source_code print(p) for i in p: if i not in ['+', '-', '', '.', ',', '[', ']']: p = p.replace(i, '') if '[]' in p: p = p.replace('[]', '') if '[' in p or ']' in p: if p.count('[') != p.count(']') or p.index('[')> p.index(']'): return 'Error!' r = '' l = {'key': '', 'value': 0} for i in range(len(p)): if p[i] in '+-': if l['key'] != '+-': r += brainfuck_sum(l) l['key'] = '+-' l['value'] = 0 l['value'] += (1 if (p[i] == '+') else -1) elif p[i] in '': if l['key'] != '': r += brainfuck_sum(l) l['key'] = '' l['value'] = 0 l['value'] += (-1 if (p[i] == '<') else 1) elif p[i] in ['.', ',', '[', ']']: r += brainfuck_retract(i, p) r += brainfuck_add(p[i]) if l['value'] != 0: r += brainfuck_sum(l) print(r) return r

現在の最終バージョン：

解決策2はメモリの過負荷の問題を解決しますが、境界テストでは、到達した最大バッファサイズ（1.5 MiB）が引き続き発生します。これは、コードは最適化されていますが、引き続き最適化する必要があることを示しています。しかし、それについて少し考えてみるか、whileループの一部を1列のコードと同じように追加してください（この部分は、トピックが物議を醸していると思うので、はっきりとは考えていませんでした。思考の部分は最後です）。結果は次の解決策です。

#!/usr/bin/python def brainfuck_sum(l): res = '' if l['key'] == '+-': if l['value'] > 0: res = '*p += ' + str(l['value']) + ' ' elif l['value'] <0: res = '*p -= ' + str(-l['value']) + ' ' elif l['key'] == '': if l['value'] 0: res = 'p += ' + str(l['value']) + ' ' else: pass return res def brainfuck_add(i): r = '' if i == ',': r = '*p = getchar() ' elif i == '.': r = 'putchar(*p) ' elif i == '[': r = 'if (*p) do { ' elif i == ']': r = '} while (*p) ' else: pass return r def brainfuck_retract(i, p): r = '' p_count_l = p[0:i].count('[') p_count_r = p[0:i+1].count(']') p_count = p_count_l - p_count_r for t in range(p_count): r += ' ' return r def brainfuck_replace(p): while '+-' in p or '-+' in p or '' in p or '><' in p or '[]' in p: p = p.replace('+-', '').replace('-+', '').replace('', '').replace('><', '').replace('[]', '') return p def brainfuck_to_c(source_code): p = source_code print(p) for i in p: if i not in ['+', '-', '', '.', ',', '[', ']']: p = p.replace(i, '') p = brainfuck_replace(p) if '[' in p or ']' in p: if p.count('[') != p.count(']') or p.index('[')> p.index(']'): return 'Error!' if p == '': return '' r = '' l = {'key': '', 'value': 0} for i in range(len(p)): if p[i] in '+-': if l['key'] != '+-': r += brainfuck_sum(l) l['key'] = '+-' l['value'] = 0 l['value'] += (1 if (p[i] == '+') else -1) elif p[i] in '': if l['key'] != '': r += brainfuck_sum(l) l['key'] = '' l['value'] = 0 l['value'] += (-1 if (p[i] == '<') else 1) elif p[i] in ['.', ',', '[', ']']: r += brainfuck_retract(i, p) r += brainfuck_add(p[i]) if l['value'] != 0: r += brainfuck_sum(l) return r

考え：

主にトピックが物議を醸していると思うので、私はついにwhileループ部分を追加しました。
たとえば、トピックには次のものが必要です。 '関数は、' +-'、' '、' [] 'などのすべての役に立たないコマンドシーケンスをソースコードから削除する必要があります。また、+-,. []を除くすべての文字を消去する必要があります。
このルールは再帰的ですか？
例えば：

'' -> '' '' -> '' Which one is right? (I guess the second is right, just want to be sure.)