2017-07-27

#19/20 Recursion: Davis' Staircase [Cracking the Coding Interview Challenges]

#19 Recursion: Davis' Staircase

www.hackerrank.com

1 o 2 or 3段を一度に登れる人間が、n段の階段を登る際に、何通りの登り方が存在するか計算する問題。

以下のような入力が与えられる。

最初の行が階段の数。2行目以下は、階段のステップ数。それぞれの階段について、何通りの登り方があるかを出力する。

上記入力の場合、出力は以下となる。

1
4
44

solution

再帰関数を使って解く。これもメモ化をすることでテストケースをパスすることができた。以下rubyでの解。

#!/bin/ruby

class Solution
    
    def initialize(n, stepsATime)
        @steps, @stepsATime, @memo = n, stepsATime, []
    end
    
    def climbingWays(current = 0)
        return @memo[current] if @memo[current]
        return 0 if current > @steps
        return 1 if current == @steps
        
        ways = 0
        @stepsATime.each do |v|
            ways += climbingWays(current + v)
        end
        return @memo[current] = ways
    end
end

input = $stdin.read.split("\n").map(&:to_i)
input.shift.times do
    puts Solution.new(input.shift, [1,2,3]).climbingWays
end

github.com

再帰とは

再帰 - Wikipedia

2017-07-26

#18/20 Recursion: Fibonacci Numbers [Cracking the Coding Interview Challenges]

hackerrank code interview

#18 Recursion: Fibonacci Numbers

www.hackerrank.com

入力される数値nに対して、n項のフィボナッチ数を求めて出力する問題。

solution

問題文の通りに実装すると以下のようになる。

def fib(n)
    return n if n <= 1
    return fib(n-1)+fib(n-2)
end
puts fib(gets.to_i)

これは正しいが、計算量が大きくなり、テストケースをパスできない。

今回はメモ化することでフィボナッチ計算を高速化する。以下rubyでの解答。

class Solution
    def initialize
        @memo = [0, 1]
    end
    
    def fib(n)
        return if n < 0
        return @memo[n] if @memo[n]
        return @memo[n] = self.fib(n - 1) + self.fib(n - 2)
    end
end
puts (Solution.new).fib(gets.to_i)

github.com

フィボナッチ数とは

フィボナッチ数 - Wikipedia

2017-07-25

#17/20 Time Complexity: Primalityh [Cracking the Coding Interview Challenges]

hackerrank code interview

#17 Time Complexity: Primality

www.hackerrank.com

素数判定を行う問題。以下のような入力が与えられる。

一行目はデータの数。それ以降の数に対して、素数かどうか判定を行い、素数であれば'Prime'、そうでなければ'Not prime'を出力する。上記の場合の出力は以下となる。

Not prime
Prime
Prime

solution

単純な試し割りではタイムアウトでテストケースをパスできない。

試し割りよりも高速なエラトステネスの篩アルゴリズムで解く。以下はrubyでの解。

def isPrime(num)
    return true if num == 2
    return false if num <= 1 || num % 2 == 0
    ary = (3..Math.sqrt(num).floor).to_a

    while val = ary.shift
        return false if num % val == 0
        ary.delete_if{ |v| v % val == 0 }
    end
    return true
end

input = $stdin.read.split("\n").map(&:to_i)
n = input.shift
n.times { puts isPrime(input.shift) ? 'Prime' : 'Not prime' }

github.com

素数判定について

素数判定 - Wikipedia

エラトステネスの篩とは

エラトステネスの篩 - Wikipedia

計算量(ランダウ記号)について

ランダウの記号 - Wikipedia

計算量算出については、この記事が非常に優しかった。 [初心者向け] プログラムの計算量を求める方法 by @cotrpepe on @Qiita http://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c

2017-07-24

CentOSへKongをインストールする

Kong PostgreSQL

目標

CentOSへKongをインストールする。

マイクロサービスをAPI Gatewayパターンで実装するため、API Gatewayの構築を考えている。 KongがマイクロサービスのAPI Gatewayとして必要な機能を備えているように見えるため、検証のため今回インストールまで行った。

Kongとは

getkong.org

インストール

環境

$ cat /etc/redhat-release
CentOS Linux release 7.3.1611 (Core)

公式のInstallationへ行くと、DockerやVagrantなど色々なインストール方法がでてくる。今回はCentOSの項目に従ってインストールを進めていく。 getkong.org

1. Install the Package

パッケージからインストールを行う。

$ wget https://github.com/Mashape/kong/releases/download/0.10.3/kong-0.10.3.el7.noarch.rpm
$ yum install kong-0.10.3.el7.noarch.rpm

2.Configure your database

DB設定を行う。

Kong supports both PostgreSQL 9.4+ and Cassandra 3.x.x as its datastore.

ということなので、今回はPostgreのv9.6をインストールする。

Postgresql downloadページ PostgreSQL: Linux downloads (Red Hat family)

Postgresqlのインストールから起動

$ yum install https://download.postgresql.org/pub/repos/yum/9.6/redhat/rhel-7-x86_64/pgdg-centos96-9.6-3.noarch.rpm

# Install the client packages
$ yum install postgresql96

# Optionally install the server packages:
$ yum install postgresql96-server

# Optionally initialize the database and enable automatic start:
$ /usr/pgsql-9.6/bin/postgresql96-setup initdb
$ systemctl enable postgresql-9.6
$ systemctl start postgresql-9.6

インストール、起動が完了したら、Kong用のDBとDB Userの設定を行う。

$ su - postgres
bash$ psql
$ CREATE USER kong; CREATE DATABASE kong OWNER kong;
$ \q
bash$ psql -l
                                         データベース一覧
   名前    |  所有者  | エンコーディング |  照合順序   | Ctype(変換演算子) |      アクセス権
-----------+----------+------------------+-------------+-------------------+-----------------------
 kong      | kong     | UTF8             | ja_JP.UTF-8 | ja_JP.UTF-8       |
 postgres  | postgres | UTF8             | ja_JP.UTF-8 | ja_JP.UTF-8       |
 template0 | postgres | UTF8             | ja_JP.UTF-8 | ja_JP.UTF-8       | =c/postgres          +
           |          |                  |             |                   | postgres=CTc/postgres
 template1 | postgres | UTF8             | ja_JP.UTF-8 | ja_JP.UTF-8       | =c/postgres          +
           |          |                  |             |                   | postgres=CTc/postgres
(4 行)

3.Start Kong

$ kong start
Error: /usr/local/share/lua/5.1/kong/cmd/start.lua:21: [postgres error] could not get current migrations: [postgres error] FATAL: ユーザ"kong"のIdent認証に失敗しました

上記のエラーが出たので解決する。

/var/lib/pgsql/9.6/data/pg_hba.conf の 82行目を以下のように書き換えた

$vi /var/lib/pgsql/9.6/data/pg_hba.conf
81 # IPv4 local connections:
82 - host    all             all             127.0.0.1/32            ident
81 # IPv4 local connections:
82 + host    all             all             127.0.0.1/32            trust

Postgreを再起動して再度Kongを起動する

$ systemctl restart postgresql-9.6
$ kong start
2017/07/24 17:14:17 [info] Kong started

Kongが動いたので、確認のためcurlで8001ポートへリクエストを投げる。

# Kong is running
$ curl 127.0.0.1:8001
{"timers":{"running":0,"pending":5},"configuration":{"admin_error_log":"logs\/....

正常に動作していれば、上記のようなjsonレスポンスが返ってくる。

実際にAPIを登録してみる

以下3つのキーを指定する

name
upstream_url
uris

http://httpbin.org/ip を登録してみる。

$ curl -i -X POST \ 
>   --url http://localhost:8001/apis \
>   --data 'name=example-api' \
>   --data 'upstream_url=http://httpbin.org/ip' \
>   --data 'uris=/httpbin/ip' \

HTTP/1.1 201 Created
Date: Mon, 24 Jul 2017 10:25:00 GMT
Content-Type: application/json; charset=utf-8
Transfer-Encoding: chunked
Connection: keep-alive
Access-Control-Allow-Origin: *
Server: kong/0.10.3

{"http_if_terminated":true,"id":"9f15037b-c303-4da6-ae12-465d48998f79","retries":5,"preserve_host":false,"created_at":1500891900000,"upstream_connect_timeout":60000,"upstream_url":"http:\/\/httpbin.org\/ip","upstream_read_timeout":60000,"https_only":false,"upstream_send_timeout":60000,"strip_uri":true,"name":"example-api","uris":["\/httpbin\/ip"]}

以下のリクエストを送信する。

$ curl -i -X GET \
>   --url http://localhost:8000/httpbin/ip \
>
HTTP/1.1 200 OK
Date: Mon, 24 Jul 2017 10:27:25 GMT
Content-Type: application/json
Content-Length: 44
Connection: keep-alive
Server: meinheld/0.6.1
Access-Control-Allow-Origin: *
Access-Control-Allow-Credentials: true
X-Powered-By: Flask
X-Processed-Time: 0.000926971435547
Via: kong/0.10.3
X-Kong-Upstream-Latency: 335
X-Kong-Proxy-Latency: 264

{
  "origin": "127.0.0.1, xxx.xxx.xxx.xxx"
}

すると、localhost:8000へのリクエストがhttpbin.org/ipへ転送され、その結果が返ってくる。

削除する場合はDELETEメソッドを使う

$ curl -i -X DELETE \  --url http://localhost:8001/apis/example-api

まとめ

検証はこれから。

マイクロサービスアーキテクチャ

作者: Sam Newman,佐藤直生,木下哲也
出版社/メーカー: オライリージャパン
発売日: 2016/02/26
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

2017-07-21

#16/20 BFS: Shortest Reach in a Graph [Cracking the Coding Interview Challenges]

hackerrank code interview

16 BFS: Shortest Reach in a Graph

www.hackerrank.com

以下の形式の入力が与えられる。

最初の行には、クエリの数を示す整数が示される。後続の行は、各クエリを次の形式で示す。

最初の行には、グラフ内のノードの数nとエッジの数mのそれぞれの値をスペースで区切りの2つの整数で示す。
後続の各行には、スペースで区切られた2つの整数が含まれており、ノードからノードに接続するエッジが示される。
最後の行には、開始ノードのインデックスを示す1つの整数が示される。

出力は、開始ノードから各ノードへの距離を出力する。1つのエッジの距離は6、エッジで繋がっていないノードへの距離は-1 とする。

上記入力の場合、解答は以下となる。

6 6 -1
-1 6

solution

この問題は、無向グラフの探索問題である。幅優先探索(BFS)アルゴリズムで解いている。以下、rubyでの解。

class Node
    def initialize
        @neighbors = []
    end
    
    def addNeighbor(id)
        @neighbors << id if !@neighbors.index(id)
    end
    
    def getNeighbors
        return @neighbors
    end
end

class Graph
    DIST = 6
    
    def initialize
        @nodes = []
    end
    
    def addNode(node)
        @nodes << node
    end
    
    def shortestReach(startId)
        dist = Array.new(@nodes.size, -1)
        dist[startId] = 0
        queue = []
        queue << startId
   
        while (!queue.empty?)
            nodeId = queue.shift
            @nodes[nodeId].getNeighbors.each do |neighbor|
                if dist[neighbor] == -1
                    queue << neighbor
                    dist[neighbor] = dist[nodeId] + DIST
                end
            end
        end
        return dist
    end
    
end

input = $stdin.read.split("\n")
q = input.shift.to_i

q.times do
    n, edges = input.shift.split(" ").map(&:to_i)
    graph, nodes = Graph.new, []

    n.times { nodes << Node.new }
    
    for i in 0..edges-1
        ary = input.shift.split(" ").map(&:to_i)
        idx1, idx2 = ary[0] - 1, ary[1] - 1
        nodes[idx1].addNeighbor(idx2) if nodes[idx1]
        nodes[idx2].addNeighbor(idx1) if nodes[idx2]
    end
    
    nodes.each { |node| graph.addNode(node) }
    
    startId = input.shift.to_i - 1
    dist = graph.shortestReach(startId)
    dist.delete_at(startId)
    puts dist.join(" ") # output answer here
end

グラフ理論

グラフ理論 - Wikipedia

BFS(breadth first search: 幅優先探索)とは

幅優先探索 - Wikipedia

感想

BFSアルゴリズム自体は難しくないが、有向or無向、深さ優先or幅優先、訪問済みを無視するかどうか、など一歩処理を間違えると期待する答えが得られなくなるので注意する。

2017-07-20

#15/20 DFS: Connected Cell in a Grid [Cracking the Coding Interview Challenges]

hackerrank code interview

#15 DFS: Connected Cell in a Grid

www.hackerrank.com

以下のような入力が与えられる。

1行目にn行、2行目にm列、それ以降はn行m列分のマトリックスがスペース区切りで与えられる。マトリックス内で、1のセルが隣接している(縦横斜め)領域を調べ、マトリックス内での最大領域数を出力する。

上記入力の場合、1が隣接している最大領域は5となるので、5を出力する。

solution

再帰ありDFS(depth first search)で解いた。以下、rubyでの解。

一度訪問した箇所を再度調べる必要はないので、訪問済みの位置には0をセットしている。

#!/bin/ruby

class Solution

    def initialize(matrix)
        @matrix = matrix
    end

    def getBiggestResion
        matrix = @matrix.clone
        maxSize = 0

        for row in 0..(matrix.size - 1)
            for column in 0..(matrix[row].size - 1)
                if matrix[row][column] == 1
                    size = getResionSize(matrix, row, column)
                    maxSize = size if maxSize < size
                end
            end
        end
        return maxSize
    end
    
    private
        def getResionSize(matrix, row, column)
            return 0 if row < 0 || column < 0 || row >= matrix.size || column >= matrix[row].size
            return 0 if matrix[row][column] == 0

            size, matrix[row][column] = 1, 0
            for r in (row - 1)..(row + 1)
                for c in (column - 1)..(column + 1)
                    if r != row || c != column
                        size += getResionSize(matrix, r, c)
                    end
                end
            end
            return size
        end
end

input = $stdin.read.split("\n")
n, m, matrix = input.shift.to_i, input.shift.to_i, []
input.each_with_index { |v, i| matrix[i] = v.split(" ").map(&:to_i) }
puts (Solution.new(matrix)).getBiggestResion