Project Euler 681

https://projecteuler.net/problem=681

107着。

フォーラムで解けなかった問題、らしい。記憶になかった。
SymPyを使いながら計算をしたら、きれいな形になった。
それを工夫して組んでみたらやけに遅かったので、素直に組んだらPyPyで4分くらいだった。
どうやったら速くなるのだろう。

JuliaでC++のtemplateのようなものを実現する

Julia

Juliaで例えば、グラフのエッジを逆向きにするグラフを作る関数を書くとする。

function main()
    graph = Dict{Int,Vector{Int}}()
    for v in 1:3
        graph[v] = collect(v+1:4)
    end
    println(graph)
    rev_graph = reverse_graph(graph)
    println(rev_graph)
    println(typeof(rev_graph))
end

function reverse_graph(graph)
    rev_graph = Dict()
    for pair in graph
        println(pair)
        v1 = pair.first
        for v2 in pair.second
            if haskey(rev_graph, v2)
                push!(rev_graph[v2], v1)
            else
                rev_graph[v2] = [v1]
            end
        end
    end
    return rev_graph
end

main()

こうすると、このrev_graphの型は、

Dict{Any,Any}

となってしまう。

Dict()

と書いているから当然だ。
しかし、型を書くのは面倒で馬鹿らしい。第一、型を明示的に書いてしまったら、その型でしかこの関数は使えなくなってしまう。C++のtemplateのようなことはできないのだろうか。
それ以前に、型に別名をつけることはできないのか？
調べてみると、型パラメータというもので実現できることが分かった。

const Graph{T} = Dict{T,Vector{T}}

これで、型を短く書くことができる。次のように使える。

graph = Graph{Int}()

これで、

Dict{Int64,Array{Int64,1}}

という型になる。

const Graph{T} = Dict{T,Vector{T}}

function main()
    graph = Graph{Int}()
    for v in 1:3
        graph[v] = collect(v+1:4)
    end
    println(graph)
    rev_graph = reverse_graph(graph)
    println(rev_graph)
    println(typeof(rev_graph))
end

function reverse_graph(graph::Graph{T})::Graph{T} where {T}
    rev_graph = Graph{T}()
    for pair in graph
        println(pair)
        v1 = pair.first
        for v2 in pair.second
            if haskey(rev_graph, v2)
                push!(rev_graph[v2], v1)
            else
                rev_graph[v2] = [v1]
            end
        end
    end
    return rev_graph
end

main()

AtCoder Beginner Contest 138 E

https://atcoder.jp/contests/abc138/tasks/abc138_e

なんということもない問題だ。この位置にいる時に、この文字は次にどこにあるかをテーブルにしておけばよい。
しかし、Pythonでどうしても時間切れになる。PyPyでもなぜか速くならない。
じゃあC++で、とも思ったが、それでは何の勉強にもならない。仕方なく、Juliaを使うことにした。
しかし、そんなに簡単に書けない。配列のインデックスが0から始まるのが最も大きい。気を付けているつもりでも0でアクセスしている。
それから、Juliaのバージョンは0.5.0だという。手元にあるのは、1.2.0。文字列の中に文字列がどこにあるかをネットで検索すると、searchという関数らしい。しかし、動かない。よく見ると、これは0.6.0での話だった。Juliaはバージョンで全然仕様が違うのだ。ネットには0.6.0の情報が多いようだ。最近日本ではJuliaは流行っていないのだろうか。それはともかく、AtCoderのコードテストでは動いた。
しかし、このコードテストが使いづらいのだ。ファイルを開くでファイルを指定して読み込むと、前のコードが残っていて新しいコードがなかなか反映されない。仕方ないので、ブラウザ上で直して、テキストファイルでも同じ修正をする。
結局、Juliaで悠々と通った。