はじめに

ABC332Dは、順列を全部ためして最小値を求める問題です。

Pythonで復習してみました。

itertoolsを使って書いてみたら、とてもシンプルに記述できました。

Pythonの場合

Pythonで書いたコードはこんな感じです。

inf = 1<<60

H,W = TII()
A = [LII() for _ in range(H)]
B = [LII() for _ in range(H)]

def count_swap(p):
    L = len(p)
    ret = 0
    for i in range(L-1):
        for j in range(i+1,L):
            if p[i]>p[j]:
                ret += 1
    return ret

ans = inf
for ph, pw in product(
    permutations(range(H),H),
    permutations(range(W),W)
):
    for i,j in product(range(H),range(W)):
        if A[ph[i]][pw[j]] != B[i][j]:
            break
    else:
        # print(ph,pw)
        ans = min(ans, count_swap(ph)+count_swap(pw))

if ans == inf:
    ans = -1
print(ans)

H,Wで二重のループになるんですが、productを使うと二重ループを一度に書けるので、気に入っています。
二重のループで書くのと本質的には同じです。

permutations()これが便利なんです。

>>> list(permutations(range(3),3))
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

range(3)を並べ替えたものを返してくれます。

abc332Dでやってほしいことは、この関数がやってくれます。

for文のelseについて、Pythonを使っててもあまり見かけないので補足しておきます。
elseの中は、forのループ中がbreakされずに終了した時だけ実行されます。
今回のような処理にはピッタリです。
332DのPythonの回答としては、整理されたものになってると思います。

Elixirの場合

Pythonのfor文はElixirのfor文と同じでイテレータなので、同じ構造で書けそうです。
permutations自分で実装しようかと思ったんですが、検索してみたら、

素晴らし！
今回は、この関数を使用してみる事にします。

方針

構造はPythonのコードと同じ
A,Bの二次元配列は、Tupleでもつ（時間が厳しいのでMapでは間に合わないだろう）
count_swapの繰り返し部分は再帰で実現する

defmodule Main do
  import Bitwise
  def next_token(acc \\ "") do
      case IO.getn(:stdio, "", 1) do
        " " -> acc
        "\n" -> acc
        x -> next_token(acc <> x)
      end
  end
  def input(), do: IO.read(:line) |> String.trim()
  def ii(), do: next_token() |> String.to_integer()
  def li(), do: input() |> String.split(" ") |> Enum.map(&String.to_integer/1)

  @inf 100100100

  def count_less_than_head([h|t]) do
      Enum.count(t, fn e -> e < h end)
  end

  def count_swap(p, h \\ 0)
  def count_swap(p, h) when h == tuple_size(p), do: 0
  def count_swap(p, h), do: count_less_than_val(p, h, h+1) + count_swap(p, h+1)

  def count_less_than_val(p, _h,i) when i == tuple_size(p) do
    0
  end

  def count_less_than_val(p, h, i) do
    (if elem(p,h) > elem(p,i), do: 1, else: 0) + count_less_than_val(p, h, i+1)
  end

  def is_matched(h,w,a,b,ph, pw) do
    for i<- 0..h-1, j <-0..w-1, reduce: :true do
      acc ->
        i1 = elem(ph,i)
        j1 = elem(pw,j)
        if a|> elem(i1)|> elem(j1) != b|> elem(i)|> elem(j), do: :false, else: acc
    end
  end

  def to_tuple_2d(list) do
    Enum.map(list, fn x -> List.to_tuple(x) end)
    |> List.to_tuple()
  end

  def solve(h, w, a, b) do

    for ph <- Combinatorics.permutations(0..h-1),
        pw <- Combinatorics.permutations(0..w-1),
        reduce: @inf
    do
      acc ->
        if is_matched(h, w, a, b, ph, pw) do
          min(acc, count_swap(ph) + count_swap(pw))
        else
          acc
        end
    end
    |> then(fn x -> if x == @inf, do: -1, else: x end)
    |> IO.puts()
  end

  def main() do
      h = ii()
      w = ii()
      a = for _ <- 1..h, do: li()
      b = for _ <- 1..h, do: li()

      tuple_a = to_tuple_2d(a)
      tuple_b = to_tuple_2d(b)

      solve(h, w, tuple_a, tuple_b)
  end

end

defmodule Combinatorics do
#～～省略～～  
#https://github.com/antimon2/combinatorics.ex/blob/master/lib/combinatorics.ex
#このコードを使いました
end

1754 msでACできました。

まとめ

Pythonのfor文をitertoolsを使うことでシンプルに記述できた
この記述がElixirのプログラムでもそのまま表現できる構造だった
関数型プログラミング言語の良いところを感じられる問題だった

参考
https://qiita.com/antimon2/items/bd4c3c2f6bd02654fe10

ABC332DをPythonとElixirで復習してみる

はじめに

Pythonの場合

Elixirの場合

まとめ