elixirでhackerrankのString-o-Permuteを解いて気づいたこと

string-o-Permuteという問題を説いた際にまた気がついたことがあったのでまとめていきます

問題内容

T行のL文字の偶数文字列が与えられるので各行毎に奇数文字と偶数文字を入れ替えて出力する

input

T
String1
String2
..
StringT

但し T <= 10, L <= 10^5, Lは偶数

output

（String1の奇数文字と偶数文字を入れ替えたもの）
..
（StringTの奇数文字と偶数文字を入れ替えたもの）

sample

# input
2
abcdef
12345678

# output
badcfe
21436587

解1(失敗)

方針

• 前回のやつを元に各文字列をリストにして先頭2文字をマッチングして残りの文字列を再起呼び出しすればいけるやんけ！

コード

defmodule StringOPermute do
  def permute([]), do: ""
  # ↓これ書けたときの全能感はすごかった
  def permute([str_hd | [new_str_hd | str_tl]]), do: new_str_hd <> str_hd <> permute(str_tl)
  def main(l), do: l |> Enum.each(&(permute(&1) |> IO.puts))
end

_ = IO.gets("") # Tは特に使わない
str_list = IO.read(:stdio, :all)
    |> String.split("\n")
    |> Enum.map(&String.trim(&1) |> String.codepoints)
# [["a", "b", "c", "d"], ["1", "2", "3", "4"]]

StringOPermute.main(str_list)

結果

Terminated due to timeout
(時間切れ)（死亡）
😇😇😇😇😇😇😇😇😇😇😇😇

原因

最大で10^5の文字列が10個もあるので再起呼び出しで1つずつ入れ替えてたら間に合わなかったぽい😇

解2（成功）

方針

• Enum.chunk_every/2 を用いてリストを分割してEnum.map/2で処理すれば勝手に並列にやってくれないかな？（実は適当にやったらできた）

コード

defmodule StringOPermute do
  # 変数名strだけど実際はリストなのでよろしくない
  def permute(str) do
    str
    |> Enum.chunk_every(2) # [["a", "b"], ["c", "d"]]
    |> Enum.map(fn([first, last]) -> [last, first] end) # [["b", "a"], ["d", "c"]]
    |> List.flatten # ["b", "a", "d", "c"]
  end

  # 一行で書きたい病気
  def main(str_list), do: str_list |> Enum.each(&(permute(&1) |> IO.puts))
end

_ = IO.gets("")
str_list = IO.read(:stdio, :all) # ここも変数名str_listsとかの方がよかった気がする
     |> String.split("\n")
     |> Enum.map(&String.trim(&1) |> String.codepoints)
# [["a", "b", "c", "d"], ["1", "2", "3", "4"]]
StringOPermute.main(str_list)

結果

†Accepted†

所感

• 再起呼び出しだけに頼るのはやめよう
• Enumがいい感じにやってくれるっぽいしStreamやFlowでメモリやCPUを効率的に使えることからEnumのメソッドで済むものはそれで済ませよう
• パターンマッチングが最高に気持ちよくなってきた