なんとな~くしあわせ?の日記

JavaとかAWSの設定とかをメモする技術ブログ

AOJ - ALDS1_11_A,B,C (グラフアルゴリズム) を解いてみた

AOJ - ALDS1_11は、グラフアルゴリズムです。

グラフの表現 | アルゴリズムとデータ構造 | Aizu Online Judge
深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge
幅優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge

解くと以下の3つを覚えられるのでとても有用です。

どれももっと早く覚えておけばよかったと悔やまれる非常に使いでのあるアルゴリズムです。これらが解けると、以下のAtCoderの問題も解けます(そのままなので…)

abc007.contest.atcoder.jp

アルゴリズム自体の解説はWikipediaとかヨークカレッジペンシルバニア校の授業用の教科書が良かったです。

あと、最初にコレを見たほうが理解が早そう

ottati.hatenablog.com

ALDS1_11_A (隣接行列)

自分の解答

以下メモ

  • N個の頂点があるグラフをN * Nの行列で表すことを隣接行列と言うようだ(頭いい考えだな〜)
  • N個の頂点があった場合、そのうち1つのある頂点Aから他の頂点へつながる数はN-1…
  • 頂点AからAに対する数も含むような行列になってしまうがそれは気にしない

ALDS1_11_B (深さ優先探索)

アルゴリズム

Wikipediaに疑似コードがあるので、それをそのまま実装すれば良い

function 深さ優先探索(v)
    v に訪問済みの印を付ける
    v を処理する
    for each v に接続している頂点 i do
        if i が未訪問 then
            深さ優先探索(i)

自分の解答

ここでもRubyのStructが活躍しており、

  • :u → ノードの番号(1〜)
  • :k → ノードから出る辺の本数
  • :v → 対向ノードの番号(1〜)
  • :visited → 訪問したか否か

ぐらいの意味で使っている

Node = Struct.new(:u, :k, :v, :visited)
lines = $stdin.read
array = lines.split("\n")
 
Node = Struct.new(:u, :k, :v, :visited)
 
class Graph
 
  attr :nodes, :d, :f
 
  def initialize(n)
    @nodes = Array.new(n){ Node.new }
    @d = Array.new(n)
    @f = Array.new(n)
  end
 
  def set_graph_node(u, k, v)
    @nodes[u-1].u = u
    @nodes[u-1].k = k
    @nodes[u-1].v = v
    @nodes[u-1].visited = false
  end
 
  def dfs(start = 0, count = 1)
 
    # puts "visit = #{@nodes[start].to_s}, count = #{count}"
    @nodes[start].visited = true
    @d[start] = count
    count = count + 1
 
    for i in @nodes[start].v
      count = dfs(i-1, count) unless @nodes[i-1].visited
    end
    # puts "visited = #{@nodes[start].to_s}, count = #{count}"
 
    @f[start] = count
    count = count + 1
    count
  end
end
 
N     = array[0].to_i
graph = Graph.new(N)
 
for i in 1...array.length
  seps = array[i].split(" ")
  u = seps.drop(0).first.to_i
  k = seps.drop(1).first.to_i
  v = seps.drop(2).map(&:to_i)
  graph.set_graph_node(u, k, v)
end
 
start, count = 0, 1
 
while graph.nodes.any?{|n| n.visited == false}
  start = graph.nodes.find_index{|n| n.visited == false }
  count = graph.dfs(start, count)
end
 
# puts "d #{graph.d.to_s}"
# puts "f #{graph.f.to_s}"
 
1.upto(N).each do |n|
  puts "#{n} #{graph.d[n-1]} #{graph.f[n-1]}"
end

これはそんなに詰まらなかった。

ALDS1_11_C (幅優先探索)

アルゴリズム

Wikipediaに疑似コードがあるが、これだと問題がある。あるノードからあるノードへの最短距離がわからない。。。すごく悩んだ

function 幅優先探索(v)
    v に訪問済みの印を付ける
    v をキューに追加
    while キューに要素を含む do
        v ← キューから取り出す
        v を処理
        for each v に接続している頂点 i do
            if i が未訪問 then
                i に訪問済みの印を付ける
                i をキューに追加

最終的に、アメリカの大学*1が公開していたアルゴリズムの手順をそのまま実装した。

ポイントはノードに到達したかどうか、探索済みかどうかを3色で表すことだ。また、各ノードへの距離はノード自体のクラスに設定する。

BFS(G,s)
for each vertex u ∈ G.V - {s}
   u.color == WHITE
   u.d = INF
   u.pi = NIL
s.color = GRAY
s.d = 0
s.pi = NIL
Q = ∅
ENQUEUE(Q,s)
while Q ≠ ∅
   u = DEQUEUE(Q)
   for each v ∈ G.Adj[u]
      if v.color == WHITE
         v.color = GRAY
         v.d = u.d + 1
         v.pi = u
         ENQUEUE(Q,v)
   u.color = BLACK

自分の解答

いろいろ試してノードのクラスはこんな感じになった。

Node = Struct.new(:u, :k, :v, :c, :d, :pi)
  • :u → ノードの番号(1〜)
  • :k → ノードから出る辺の本数
  • :v → 対向ノードの番号(1〜)
  • :c → 訪問状況を3値(=3色)で
  • :d → ノード間の距離の記録
  • :pi → 一つ前に探索したノードの記録
# Queue
class Array
  alias_method :enqueue, :push
  alias_method :dequeue, :shift
end
 
# u : Index of nodes starting from 1...N
# k : degree of this node
# v : array of vertices connected with this node
# c : :white(=undiscovered), :gray(=frontier), :black(finished searching)
# d : distance when the vertex is first discovered
# pi: predecessor vertex
Node = Struct.new(:u, :k, :v, :c, :d, :pi)
 
class Graph
 
  attr :nodes, true
 
  def initialize(n)
    @nodes = Array.new(n){ Node.new }
  end
 
  def add_graph_node(u, v)
    @nodes[u-1].u = u
    if not v.nil?
      (@nodes[u-1].v ||= []).push(v)
      @nodes[u-1].k = @nodes[u-1].v.length ||= 0
    else
      @nodes[u-1].v = [] if @nodes[u-1].v.nil?
      @nodes[u-1].k = 0
    end
    @nodes[u-1].c = :white
    @nodes[u-1].d = -1
    @nodes[u-1].pi = nil
  end
 
  def reset()
    @nodes.each do |node|
      node.c  = :white
      node.d  = -1
      node.pi = nil
    end
  end
 
  def dist()
    puts "d : #{@nodes.map{|node| node.d}.to_a.to_s}"
    puts "pi: #{@nodes.map{|node| node.pi}.to_a.to_s}"
  end
 
  def bfs(start, queue)
 
    start_idx = (start - 1).to_i
    @nodes[start_idx].c  = :gray
    @nodes[start_idx].d  = 0
    @nodes[start_idx].pi = nil
    queue.enqueue(@nodes[start_idx])
 
    while not queue.empty?
 
      u = queue.dequeue
      break if u.v.nil?
 
      u.v.each do |label|
        v = @nodes[label-1]
        if v.c == :white
          v.c  = :gray
          v.d  = u.d.to_i + 1
          v.pi = u
          queue.enqueue(v)
        end
      end
      u.c = :black
    end
  end
end
 
# start
lines = $stdin.read
array = lines.split("\n")
 
N     = array[0].to_i
graph = Graph.new(N)
 
for i in 1...N+1
  seps = array[i].split(" ")
  u    = seps.drop(0)[0].to_i
  k    = seps.drop(1)[0].to_i
  vs   = seps.drop(2).map(&:to_i)
  #puts "add_graph_node(#{u} <--> #{v})"
  for v in vs
    graph.add_graph_node(u, v)
  end
  graph.add_graph_node(u, nil) if vs.length == 0
end
 
graph.bfs(1, [])
 
graph.nodes.each_with_index do |elem, idx|
    puts "#{idx+1} #{graph.nodes[idx].d.to_i}"
end

アルゴリズムをどう使うかなども書きたいのだが、それは後日

*1:ヨークカレッジ ペンシルバニア校/York College of Pennsylvania というところらしい

mavenで本番用/開発用のwarファイル切り替え

f:id:panzer-jagdironscrap1:20171018130045p:plain

成果物の設定情報切り替え

ユースケース

システム開発を行う際、DBやサーバを本番環境、開発環境(あるいは+ステージング環境)に用意することは当たり前のことだろう。

上記のようにすることで

  • 開発環境で事前にテストすることでバグが発見しやすくなる
  • 本番環境のデプロイのノウハウがたまってミスりにくくなる

ここからさらに進めて自動デプロイ環境、いわゆるCIを用意していくのが最近の潮流です。というかそうしないで人の手でやるのは時間がかかるしミスが多い。

実際に使われる環境変数

接続先データベースのURLや秘密のトークン文字列などを環境ごとに分けます。これにより、同じアプリケーションを起動するときに、環境変数を切り替えれば本番用/開発用の環境が切り替えられます。

他のフレームワークでの方法

Rubyには dotenv というフレームワークがあり、最初から環境は3種類用意することが前提になっています。development, staging, productionそしてtest。ごめんなさい4種類でした。

testに関してはユニットテストで実行される際の環境変数を提供するという認識です。

GitHub - bkeepers/dotenv: A Ruby gem to load environment variables from `.env`.

mavenで本番用/開発用のwarファイル切り替え

profile

mavenにはビルドの際にオプションとして「-P env」という形式で切り替え用の環境を与えられます。

maven resources plugin

profileごとに使用するプロパティファイルを切り替えるとき Maven Resources Plugin が使えます。

環境ごとの切り替えの実装

プロパティファイルの値の置き換え

  • resource タグで指定された場所にあるファイルが、変数の置き換え対象になります
<project>
  ...
  <name>jdbc:postgresql://localhost/test</name>
  ...
  <build>
    ...
    <resources>
      <resource>
        <directory>src/main/resources</directory>
        <filtering>true</filtering>
      </resource>
      ...
    </resources>
    ...
  </build>
  ...
</project>
  • src/main/resources/config.properties
jdbc.url=${name}

こういう風に設定しておくと、mavenでのビルド後にプロパティファイルの中身が書き換わります。

jdbc.url=jdbc:postgresql://localhost/test

書き換わったファイルが入るのは、ビルド後にクラスファイルが入る target/classes 以下になります。

プロパティの置き換えを「-P env」オプションで行う

以下のサイトの内容の受け売りになりますが

pom.xmlの中身を以下のように設定すると

  • 「mvn -P dev compile」
  • 「mvn -P prod compile」
  • 「mvn -P test compile」

で切り替えられるようになります。

<!-- プロファイル設定 -->
<profiles>
    <profile>
        <id>dev</id>
        <activation>
            <activeByDefault>true</activeByDefault>
        </activation>
        <properties>
            <build.profile.id>dev</build.profile.id>
        </properties>
    </profile>
    <profile>
        <id>prod</id>
        <properties>
            <build.profile.id>prod</build.profile.id>
        </properties>
    </profile>
    <profile>
        <id>test</id>
        <properties>
            <build.profile.id>test</build.profile.id>
        </properties>
    </profile>
</profiles>

<!-- プロパティ値の取得元(dev/prod/testというディレクトリ)を用意しておく -->
<filters>
    <filter>profiles/${build.profile.id}/config.properties</filter>
</filters>

<!-- プロパティ値の適用先ファイル -->
<resources>
    <resource>
        <directory>src/main/resources</directory>
        <filtering>true</filtering>
    </resource>
</resources>

Bitnami版Jenkinsとコンソール出力の自動更新

f:id:panzer-jagdironscrap1:20171010134552p:plain
Bitnami Jenkins

AWS上で使用するJenkinsにBitnamiが提供しているUbuntuのイメージを使っているのですが

bitnami.com

どうもこれが原因でビルド結果の自動更新がうまく動いてなかったらしい。

対象チケット

[JENKINS-25026] Console output stops populating after several seconds - Jenkins JIRA

参考になったコメント

Daniel Beck added a comment - 2015-01-08 23:33
And that's why you don't use some random vendor's preconfigured shit. It's broken.Disable mod_pagespeed (whatever the hell that is) in Apache and things start working.What a waste of time.

あんたらがITベンダーによって設定済みのクソを使わないのはこういうわけだな、こいつは壊れてる。Apacheの中のmod_pagespeed(ちくしょう!)を無効化したらうまく動き出した。なんて時間の無駄だ…

実際の変更手順

$ cd /opt/bitnami

$ sudo ./ctlscript.sh stop

$ sudo vim /opt/bitnami/apache2/conf/pagespeed.conf

# Turn on mod_pagespeed. To completely disable mod_pagespeed, you
# can set this to "off".

- ModPagespeed on
+ ModPagespeed off

$ sudo ./ctlscript.sh start

これでちゃんとコンソール出力が自動更新されるようになった。