不運なチケットについての投稿を通過できませんでした。 これは私のお気に入りのタスクの1つです。 さらに、ソリューション内の組み合わせは手動でプログラムされたため、 すべてのオプションをアルゴリズム的にソートすることは興味深いでしょう 。 私はElixirを使用してこの問題を解決したかったのです。
これに由来するものに興味がある場合、またはインストールして繰り返してください。
Elixirをインストールした後、ランタイム環境に入ります。
user@host:~/$ iex Erlang/OTP 19 [erts-8.0.2] [source-753b9b9] [64-bit] [smp:2:2] [async-threads:10] [hipe] [kernel-poll:false] Interactive Elixir (1.3.2) - press Ctrl+C to exit (type h() ENTER for help) iex(1)>
ソースデータを変数などに文字列として設定します
iex(1)> data_in = "123456" "123456"
次に、この文字列を何らかの方法で断片に解析する必要があります。 最初に、文字列
"123456"
を文字列の配列に変換しますが、一度に1文字-
["1", "2", "3", "4", "5", "6"]
、その後、すべての要素配列は整数に変換されます：
[1, 2, 3, 4, 5, 6]
1、2、3、4、5、6
[1, 2, 3, 4, 5, 6]
。 パイプを使用してこれを行います（ パイプ演算子 ）：
iex(2)> [a,b,c,d,e,f] = data_in \ ...(2)> |> String.split("", trim: true) \ ...(2)> |> Enum.map(fn(x)-> String.to_integer(x) end) [1, 2, 3, 4, 5, 6]
チャンネルは簡単に理解できます。 処理の各段階で関数が配置されますが、入力データは関数の最初のパラメーターに提供されます。 そのため、該当する場合、呼び出された
String.split
関数には3つのパラメーターがありますが、
data_in
は置き換えられます。 この変換の結果は、次の
Enum.map
関数に渡されます。 最初のパラメーターは再び表示されず、自動的に置き換えられます。 2番目のパラメーターは心配する必要はありません。 配列の各要素を変換するために呼び出される関数を示します。 関数のみで、すぐにパラメーターとして識別して渡しました。 これは高階関数と呼ばれます 。 変数
a, b, c, d, e, d
は数字
a, b, c, d, e, d
あります。
iex(4)> a 1 iex(5)> b 2
ためらうことなく、記号と括弧のすべてのオプションを完全に列挙するには、 ポーランド表記を使用する必要があるという結論に達します。 このことから、ソリューションでは3つの数字のうち3つの数字のすべての順列を整理する必要があります。 そして、今使用することに決めた4つの演算子のうちの2つ（
"+", "-", "*", "/"
）のすべてのバリアントを繰り返します。
次に、すべての順列を提供する関数を見つける必要があります。 短い検索では、rosettacodeの結果が返されます。 （touch perm.ex）ファイルを作成し、モジュールテキストを入力します。
defmodule RC do def permute([]), do: [[]] def permute(list) do for x <- list, y <- permute(list -- [x]), do: [x|y] end end
コンパイルします：
iex(7)> c("perm.ex") warning: redefining module RC (current version loaded from Elixir.RC.beam) perm.ex:1 [RC]
私達は試みます：
iex(9)> RC.permute([1, 2, 3]) [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
これがまさに必要なものです。 現在、組み合わせを計算するためのアルゴリズムを探しています。 オープンスペーススタックオーバーフローのどこかで、このような解決策が見つかります。 また、perm.exに追加します。
def comb(0,_), do: [[]] def comb(_,[]), do: [] def comb(n, [x|xs]) do (for y <- comb(n - 1, xs), do: [x|y]) ++ comb(n, xs) end
同じperm.exファイルに追加して、コンパイルします。 私たちはチェックします：
iex(12)> RC.comb(2, [1,2,3,4]) [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
さあ、先に進みましょう。 次に、これら2つの配列を乗算する必要があります。 したがって、最初の要素の各要素には、2番目の要素が割り当てられます。 判明したように、これは集合のデカルト積と呼ばれます 。 Elixirでは、このような操作は理解を通じて行われます：
iex> for i <- [:a, :b, :c], j <- [1, 2], do: {i, j} [a: 1, a: 2, b: 1, b: 2, c: 1, c: 2]
これで、すべての組み合わせを並べ替える準備ができたので、次に...それらの組み合わせを並べ替えます！ 数字の左3桁とその組み合わせ：
iex(14)> digs1 = RC.permute([a,b,c]) [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
数字の右3桁とその組み合わせ：
iex(14)>digs2 = RC.permute([d,e,f]) [[4, 5, 6], [4, 6, 5], [5, 4, 6], [5, 6, 4], [6, 4, 5], [6, 5, 4]]
次に、それぞれに操作シーケンスのすべてのバリアントを乗算し、次の3つの数値（左3）で実行できるすべてを取得します。
iex(19)> vari1 = for i <- ops, j <- digs1, do: {i, j} [{["+", "-"], [1, 2, 3]}, {["+", "-"], [1, 3, 2]}, {["+", "-"], [2, 1, 3]}, {["+", "-"], [2, 3, 1]}, {["+", "-"], [3, 1, 2]}, {["+", "-"], [3, 2, 1]}, {["+", "*"], [1, 2, 3]}, {["+", "*"], [1, 3, 2]}, {["+", "*"], [2, 1, 3]}, {["+", "*"], [2, 3, 1]}, {["+", "*"], [3, 1, 2]}, {["+", "*"], [3, 2, 1]}, {["+", "/"], [1, 2, 3]}, {["+", "/"], [1, 3, 2]}, {["+", "/"], [2, 1, 3]}, {["+", "/"], [2, 3, 1]}, {["+", "/"], [3, 1, 2]}, {["+", "/"], [3, 2, 1]}, {["-", "*"], [1, 2, 3]}, {["-", "*"], [1, 3, 2]}, {["-", "*"], [2, 1, 3]}, {["-", "*"], [2, 3, 1]}, {["-", "*"], [3, 1, 2]}, {["-", "*"], [3, 2, 1]}, {["-", "/"], [1, 2, 3]}, {["-", "/"], [1, 3, 2]}, {["-", "/"], [2, 1, 3]}, {["-", "/"], [2, 3, 1]}, {["-", "/"], [3, 1, 2]}, {["-", "/"], [3, 2, 1]}, {["*", "/"], [1, 2, 3]}, {["*", "/"], [1, 3, 2]}, {["*", "/"], [2, 1, 3]}, {["*", "/"], [2, 3, 1]}, {["*", "/"], [3, 1, 2]}, {["*", "/"], [3, 2, 1]}]
そして、右の3つ：
iex(22)> vari2 = for k <- ops, l <- digs2, do: {k, l} [{["+", "-"], [4, 5, 6]}, {["+", "-"], [4, 6, 5]}, {["+", "-"], [5, 4, 6]}, {["+", "-"], [5, 6, 4]}, {["+", "-"], [6, 4, 5]}, {["+", "-"], [6, 5, 4]}, {["+", "*"], [4, 5, 6]}, {["+", "*"], [4, 6, 5]}, {["+", "*"], [5, 4, 6]}, {["+", "*"], [5, 6, 4]}, {["+", "*"], [6, 4, 5]}, {["+", "*"], [6, 5, 4]}, {["+", "/"], [4, 5, 6]}, {["+", "/"], [4, 6, 5]}, {["+", "/"], [5, 4, 6]}, {["+", "/"], [5, 6, 4]}, {["+", "/"], [6, 4, 5]}, {["+", "/"], [6, 5, 4]}, {["-", "*"], [4, 5, 6]}, {["-", "*"], [4, 6, 5]}, {["-", "*"], [5, 4, 6]}, {["-", "*"], [5, 6, 4]}, {["-", "*"], [6, 4, 5]}, {["-", "*"], [6, 5, 4]}, {["-", "/"], [4, 5, 6]}, {["-", "/"], [4, 6, 5]}, {["-", "/"], [5, 4, 6]}, {["-", "/"], [5, 6, 4]}, {["-", "/"], [6, 4, 5]}, {["-", "/"], [6, 5, 4]}, {["*", "/"], [4, 5, 6]}, {["*", "/"], [4, 6, 5]}, {["*", "/"], [5, 4, 6]}, {["*", "/"], [5, 6, 4]}, {["*", "/"], [6, 4, 5]}, {["*", "/"], [6, 5, 4]}]
興味深いことに、オプションの数は次のとおりです。
iex(24)> length(vari1) 36
次に、ポーランド表記で表現を数える方法を学びたいと思います。 これを行うには、同じperm.exファイルにもう少しコードを追加します。 最初に、2つの数値で演算を実行する方法を学びます
最初に、1つのパラメーターで関数を呼び出します。このパラメーターとして、2つの要素のタプルがあります：
{, }
。 関数の一致メカニズムを使用して、パラメーターの数によって、単一の関数が選択されます。 その中で、タプルからの値は2つの変数
ops
と
stack
「ロールアップ」され、2つのパラメーターを持つ関数が既に呼び出されます。 Elixirでは、Erlangのように、
if
および
else if
代わりに、着信パラメーターの値に応じて、関数でマッチングが使用されます。 さらに、前述の機能が動作します。 私たちの場合、最初のパラメーターが空の配列（[]）になるまで、3番目の関数が実行されます。 しかし、配列が空になるとすぐに、2番目の関数が機能し、結果が得られます。 この例は、末尾再帰の実装の典型的な例です。 すべての計算は3番目の関数で行われ、最初の操作とテールは操作の配列から取得されます。 スタックの役割を果たす数字付きの配列から、2つの数字とテールが選択されます。 次に、データがなくなるまで関数が再帰的に呼び出されます。 再帰によるサイクルの実装も一般的なアプローチです。 また、計算のために、calは3つのパラメーター（関数と2つの数値）で呼び出されます。 ゼロによる除算を行うと、エラーが発生します。 したがって、条件の代わりに除算を実行する関数の前に、マッチングによって除算器の入力でゼロを「キャッチ」し、結果としてatom：errを与える関数を追加します。 したがって、すべての操作の前に、最初または2番目のオプションがerrであるという事実に一致するものを追加します。この場合、結果は同じになります。
def calc({ops,stack}), do: calc(ops,stack) def calc([], stack), do: hd(stack) def calc(ops, stack) do [op|ops_tail] = ops [a,b|stack_tail] = stack calc(ops_tail, [calc(op, a, b)|stack_tail]) end def calc(_, :err,_), do: :err def calc(_, _,:err), do: :err def calc("*", a, b), do: a * b def calc("/", _, 0), do: :err def calc("/", a, b), do: a / b def calc("+", a, b), do: a + b def calc("-", a, b), do: a - b
したがって、すでにおなじみの構造を使用して、数値の左側と右側の組み合わせを乗算します。
iex(27)> vari_all = for m <- vari1, n <- vari2, do: {m, n}
仮想マシンによって短縮された非常に長い出力が得られます。 左側と右側の平等のみが推定されるようにフィルタリングします
iex(30)> vari_all \ ...(30)> |> Enum.filter(fn({left, right})-> RC.calc(left) == RC.calc(right) end) [{{["+", "-"], [1, 3, 2]}, {["+", "/"], [4, 6, 5]}}, {{["+", "-"], [1, 3, 2]}, {["+", "/"], [6, 4, 5]}}, {{["+", "-"], [2, 3, 1]}, {["-", "*"], [6, 5, 4]}}, {{["+", "-"], [3, 1, 2]}, {["+", "/"], [4, 6, 5]}}, {{["+", "-"], [3, 1, 2]}, {["+", "/"], [6, 4, 5]}}, {{["+", "-"], [3, 2, 1]}, {["-", "*"], [6, 5, 4]}}, {{["+", "*"], [2, 3, 1]}, {["+", "-"], [4, 6, 5]}}, {{["+", "*"], [2, 3, 1]}, {["+", "-"], [6, 4, 5]}}, {{["+", "*"], [3, 2, 1]}, {["+", "-"], [4, 6, 5]}}, {{["+", "*"], [3, 2, 1]}, {["+", "-"], [6, 4, 5]}}, ...
最初の行から、（1 + 3）-2 = 2であり、右側（4 + 6）/ 5 = 2であることがわかります。そう、ポーランド表記だけが人間にとって便利ではありません。 perm.exにもう少し追加して変換します。
def expr_to_str({ops, stack}), do: expr_to_str(ops, stack) def expr_to_str(ops, stack) do [d1, d2, d3] = Enum.map(stack, fn(x)-> Integer.to_string(x) end) [op1, op2] = ops to_string(["(", d1, op1, d2, ")", op2, d3]) end
パイプに変換を追加します。
iex(37)> vari_all \ ...(37)> |> Enum.filter(fn({left, right})-> RC.calc(left) == RC.calc(right) end) \ ...(37)> |> Enum.map(fn({left, right})-> \ ...(37)> RC.expr_to_str(left) <> " = " <> \ ...(37)> RC.expr_to_str(right) \ ...(37)> end) ["(1+3)-2 = (4+6)/5", "(1+3)-2 = (6+4)/5", "(2+3)-1 = (6-5)*4", "(3+1)-2 = (4+6)/5", "(3+1)-2 = (6+4)/5", "(3+2)-1 = (6-5)*4", "(2+3)*1 = (4+6)-5", "(2+3)*1 = (6+4)-5", "(3+2)*1 = (4+6)-5", "(3+2)*1 = (6+4)-5", "(1+3)/2 = (4+6)/5", "(1+3)/2 = (6+4)/5", "(2+3)/1 = (4+6)-5", "(2+3)/1 = (6+4)-5", "(3+1)/2 = (4+6)/5", "(3+1)/2 = (6+4)/5", "(3+2)/1 = (4+6)-5", "(3+2)/1 = (6+4)-5", "(1-3)*2 = (5-6)*4", "(2-1)*3 = (4+5)-6", "(2-1)*3 = (5+4)-6", "(3-1)*2 = (6-5)*4", "(1*3)/2 = (4+5)/6", "(1*3)/2 = (5+4)/6", "(2*3)/1 = (5-4)*6", "(3*1)/2 = (4+5)/6", "(3*1)/2 = (5+4)/6", "(3*2)/1 = (5-4)*6"]
写真のチケットについても同じことを繰り返しましょう。
iex(39)> data_in = "666013" "666013" iex(40)> [a,b,c,d,e,f] = data_in \ ...(40)> |> String.split("", trim: true) \ ...(40)> |> Enum.map(fn(x)-> String.to_integer(x) end) [6, 6, 6, 0, 1, 3] iex(41)> ops = RC.comb(2, ["+","-","*","/"]) [["+", "-"], ["+", "*"], ["+", "/"], ["-", "*"], ["-", "/"], ["*", "/"]] iex(42)> digs1 = RC.permute([a,b,c]) [[6, 6, 6], [6, 6, 6], [6, 6, 6], [6, 6, 6], [6, 6, 6], [6, 6, 6]] iex(43)> digs2 = RC.permute([d,e,f]) [[0, 1, 3], [0, 3, 1], [1, 0, 3], [1, 3, 0], [3, 0, 1], [3, 1, 0]] iex(44)> vari1 = for i <- ops, j <- digs1, do: {i, j} ... iex(45)> vari2 = for k <- ops, l <- digs2, do: {k, l} iex(46)> vari_all = for m <- vari1, n <- vari2, do: {m, n} iex(47)> vari_all \ ...(47)> |> Enum.filter(fn({left, right})-> RC.calc(left) == RC.calc(right) end) \ ...(47)> |> Enum.map(fn({left, right})-> \ ...(47)> RC.expr_to_str(left) <> " = " <> \ ...(47)> RC.expr_to_str(right) \ ...(47)> end) ["(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", "(6-6)*6 = (1*0)/3", "(6-6)*6 = (3*0)/1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", "(6-6)*6 = (1*0)/3", "(6-6)*6 = (3*0)/1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", "(6-6)*6 = (1*0)/3", "(6-6)*6 = (3*0)/1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", "(6-6)*6 = (1*0)/3", "(6-6)*6 = (3*0)/1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", ...]
ご覧のとおり、チケットは非常に幸せです！ ）
もちろん、ここで何かを改善することができます（重複する666を削除します）。結果を次のように比較することはできません：err、そして実際、著者が最初に提起した問題を解決しませんでした。最初の3桁のうち、最後の3桁のセットの値と一致しません 。 」 しかし、私はそのような目標を設定しませんでした。 Elixirを適用するときに問題を解決するアプローチの違いを示すことは、より興味深いものでした。 タスクの完全なソリューションには、チケット番号の全範囲の計算が必要になります。ここでは、Erlang \ Elixir並列コンピューティングの全能力を示すことができますが、これはおそらく別の記事のトピックであり、時計はすでに02:53です。