#14/20 Binary Search: Ice Cream Parlor [Cracking the Coding Interview Challenges]

#14 Binary Search: Ice Cream Parlor

www.hackerrank.com

アイスクリーム屋で、持っているお金を全てを使い切って2個のアイスクリームを購入したい。 その組み合わせを見つける、という問題。

アイスクリーム屋には、様々なフレーバーのアイスがあり、それぞれ値段とユニークなIDが定められている(IDは与えられる入力順に1から始まる)。

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

2
4
5
1 4 5 3 2
4
4
2 2 4 3

1. 1行目はアイスクリーム屋に行く回数
2. 2行目以降は3行単位で、1.所持金、2.フレーバーの総数、3.フレーバーのコストが繰り返される。

解答は2個のアイスクリームのIDをスペース区切りで、ID昇順で出力する。上記入力場合、解答は以下となる。

1 4
1 2

solution

問題タイトルどおり、バイナリーサーチを使って解いた。

#!/bin/ruby

def binarySearch(ary, key, min, max)
    return -1 if max < min
    
    mid = min + (max - min) / 2
    if key < ary[mid]
        return binarySearch(ary, key, min, mid -1)
    elsif key > ary[mid]
        return binarySearch(ary, key, mid + 1, max)
    else
        return mid
    end
end

def getFlavorId(menu, value, excludeIdx = nil)
    menu.each_with_index do |v, i|
        if v == value
            if excludeIdx && excludeIdx == i
                next
            else
                return i + 1
            end
        end
    end
    return -1
end

def find(menu, money)
    sorted = menu.sort
    len = menu.size
    sorted.each_with_index do |v, i|
        complement = money - v
        result = binarySearch(sorted, complement, i + 1, len - 1)
        if result != -1
            flavor1 = getFlavorId(menu, v)
            flavor2 = getFlavorId(menu, sorted[result], flavor1 - 1)
            return [flavor1, flavor2].sort if flavor2 != -1
        end
    end
    return []
end


input = $stdin.read.split("\n")
trips = input.shift.to_i
trips.times do
    money, n, menu = input.shift.to_i, input.shift.to_i, input.shift.split(" ").map(&:to_i)
    puts find(menu, money).join(" ")
end

github.com

Binary Search(2分探索)とは

二分探索 - Wikipedia

#13/20 DP: Coin Change [Cracking the Coding Interview Challenges]

#13 DP: Coin Change

www.hackerrank.com

タイトルどおり、Dynamic Programming で解く問題。

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

4 3
1 2 3

4 3 # {コインの組み合わせで達成したい値} {コインの種類数}
1 2 3 # コインの種類。この場合、価値が1, 2, 3の3種類のコインが存在するということになる

各コインが無限に利用可能である場合、達成したい値(上記の場合4)を達成する組み合わせが何通り存在するかを計算する。

上記の入力の場合

• 1,1,1,1
• 1,1,2
• 2,2
• 1,3

の4種類の組み合わせがあるため、4を出力すれば良い。

solution

以下 ruby での解。

#!/bin/ruby

def solution(coins, target)
    lenCoins = coins.size
    table = Array.new(lenCoins + 1).map{Array.new(target + 1,0)}
    for i in 0..lenCoins
        table[i][0] = 1
    end

    for i in 1..lenCoins
        for j in 1..target
            table[i][j] = coins[i - 1] <= j ?
                table[i - 1][j] + table[i][j - coins[i -1]]
                : table[i - 1][j]
        end
    end
    return table[lenCoins][target];
end

input = $stdin.read.split("\n")
n, m = input[0].split(" ").map(&:to_i)
coins = input[1].split(" ").map(&:to_i)
puts solution(coins, n)

動的計画法に倣って、まず小さい問題に分割、ボトムアップで順次に解を得ていくというアプローチで解いた。 ソースコード内table配列が全ての部分結果を保持する。

追加するコインの値がtarget値より大きい場合

table[i - 1][j] を参照する 。合計値をオーバーするためこの場合、既に算出している自身より1ワイズ小さいコインの結果を参照する。

追加するコインの値がtarget値以下の場合

table[i - 1][j] + table[i][j - coins[i -1]] を参照する。 自身のコインを追加できる場合、目標値は(target - コインの値)と考えることができるので既に算出済みの table[追加するコインindex][(target - 追加するコインの値)] を加算している。

github.com

Dynamic Programming(動的計画法)とは

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

動的計画法 - Wikipedia

感想

動的計画法、すらすらと書けないなあ。解いてみるとすごくシンプルなんだけど。

#12/20 Merge Sort: Counting Inversions [Cracking the Coding Interview Challenges]

#12 Merge Sort: Counting Inversions

www.hackerrank.com

以下のようなインプットが与えられる。

2  
5  
1 1 1 2 2  
5  
2 1 3 1 2

• 1行目はデータセットの総数
• 2行目以降はデータセットの総数分だけ以下の入力の繰り返し
  • データの要素の数が整数で与えられる
  • スペース区切りで上記要素の数だけ整数が与えられる

与えられたデータをマージソートし、swapした回数を出力する。 上記のインプットの場合、2個のデータセットが与えられるので、それぞれに対して マージソートを行いswap数を出力する。

0  
4   

solution

以下、rubyでの解。

class Solution

    def initialize(ary)
        @ary = ary
        @swaps = 0
    end

    def mergeSort(ary = @ary)
        return ary if (len = ary.size) <= 1
        ary = ary.clone
        mid = len == 2 ? 1 : len / 2
        list1 = ary.slice(0, mid)
        list2 = ary.slice(mid, len - mid)

        return merge(self.mergeSort(list1), self.mergeSort(list2))
    end

    def getSwaps
        return @swaps
    end

    private
        def merge(list1, list2)
            len1, len2 = list1.size, list2.size
            result = Array.new(len1 + len2)
            a, b, i, j, k = list1[0], list2[0], 0, 0, 0
            loop {
                if a <= b then
                    result[i] = a
                    i += 1
                    j += 1
                    break unless j < len1
                    a = list1[j]
                else
                    # count number of swaps here
                    @swaps += len1 - j
                    result[i] = b
                    i += 1
                    k += 1
                    break unless k < len2
                    b = list2[k]
                end
            }
            while j < len1 do
                result[i] = list1[j]
                i += 1
                j += 1
            end
            while k < len2 do
                result[i] = list2[k]
                i += 1
                k += 1
            end
            return result
        end
end

input = $stdin.read.split("\n")
d = input.shift.to_i
d.times do |v|
    n, ary = input.shift.to_i, input.shift.split(" ").map(&:to_i)
    s = Solution.new(ary)
    s.mergeSort
    puts s.getSwaps
end

github.com

マージソートとは

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする。 （ナイーブな）クイックソートと比べると、最悪計算量は少ない。ランダムなデータでは通常、クイックソートのほうが速い。

マージソート - Wikipedia

pipでWebスクレイピングライブラリScrapyのインストール(Python3)

環境

$ python -V 
Python 3.6.1

$ pip -V
pip 9.0.1

Scrapyとは？

これ

Scrapy | A Fast and Powerful Scraping and Web Crawling Framework

pipでScrapyをインストールする

$ pip install Scrapy 
Collecting scrapy
  Using cached Scrapy-1.4.0-py2.py3-none-any.whl
Collecting PyDispatcher>=2.0.5 (from scrapy)
  Using cached PyDispatcher-2.0.5.tar.gz
Collecting queuelib (from scrapy)
  Using cached queuelib-1.4.2-py2.py3-none-any.whl
Collecting w3lib>=1.17.0 (from scrapy)
  Downloading w3lib-1.17.0-py2.py3-none-any.whl
Collecting parsel>=1.1 (from scrapy)
  Using cached parsel-1.2.0-py2.py3-none-any.whl
Collecting service-identity (from scrapy)
  Using cached service_identity-17.0.0-py2.py3-none-any.whl
Collecting pyOpenSSL (from scrapy)
  Using cached pyOpenSSL-17.1.0-py2.py3-none-any.whl
Collecting lxml (from scrapy)
  Downloading lxml-3.8.0-cp36-cp36m-manylinux1_x86_64.whl (7.3MB)
    100% |████████████████████████████████| 7.3MB 79kB/s
Collecting Twisted>=13.1.0 (from scrapy)
  Could not find a version that satisfies the requirement Twisted>=13.1.0 (from scrapy) (from versions: )
No matching distribution found for Twisted>=13.1.0 (from scrapy)

インストールに失敗した。どうやらTwisted >=13.1.0 が必要とのことなのでTwistedをインストールする。

$ pip install Twisted
Collecting Twisted
  Could not find a version that satisfies the requirement Twisted (from versions: )
No matching distribution found for Twisted

が、Twistedのインストールもダメ。仕方がないので、公式のソースからインストールする。

Downloads – Twisted

Twisted 17.5.0 をダウンロードしてインストール。

$ wget https://twistedmatrix.com/Releases/Twisted/17.5/Twisted-17.5.0.tar.bz2
$ tar -jxvf Twisted-17.5.0.tar.bz2
$ cd Twisted-17.5.0.tar.bz2
$ python setup.py install
...
Finished processing dependencies for Twisted==17.5.0

Twistedのインストール完了。再度pipでScrapyのインストールにトライする。

$ pip install Scrapy
...
Successfully installed PyDispatcher-2.0.5 Scrapy-1.4.0 pyasn1-0.2.3 pyasn1-modules-0.0.9 queuelib-1.4.2 service-identity-17.0.0

無事にインストールできた。

$ scrapy
Scrapy 1.4.0 - no active project

Usage:
  scrapy <command> [options] [args]

Available commands:
  bench         Run quick benchmark test
  fetch         Fetch a URL using the Scrapy downloader
  genspider     Generate new spider using pre-defined templates
  runspider     Run a self-contained spider (without creating a project)
  settings      Get settings values
  shell         Interactive scraping console
  startproject  Create new project
  version       Print Scrapy version
  view          Open URL in browser, as seen by Scrapy

  [ more ]      More commands available when run from project directory

Use "scrapy <command> -h" to see more info about a command

PythonによるWebスクレイピング

#11/20 Sorting: Comparator [Cracking the Coding Interview Challenges]

#11 Sorting: Comparator

www.hackerrank.com

solution

python3 での解答。

from functools import cmp_to_key

class Player:
    def __init__(self, name, score):
        self.name = name
        self.score = score

    def comparator(a, b):
        if a.score > b.score:
            return -1
        elif a.score < b.score:
            return 1
        elif a.score == b.score and a.name > b.name:
            return 1
        else:
            return -1

n = int(input())
data = []
for i in range(n):
    name, score = input().split()
    score = int(score)
    player = Player(name, score)
    data.append(player)

data = sorted(data, key=cmp_to_key(Player.comparator))
for i in data:
    print(i.name, i.score)

github.com

#10/20 Sorting: Bubble Sort [Cracking the Coding Interview Challenges]

#10 Sorting: Bubble Sort

www.hackerrank.com

solution

与えられた数値をバブルソートアルゴリズムを使って昇順にソートし、スワップ回数、ソートの最初と最後を指定のフォーマットで出力する問題。

以下、rubyでの解答。

def bubbleSort(n, elements)
    total = 0
    for i in 0..n-1 do
        swaps = 0
        for j in 0..n-2 do
            if elements[j] > elements[j + 1]
                elements[j], elements[j + 1] = elements[j + 1], elements[j]
                swaps += 1
            end
        end
        break if swaps == 0
        total += swaps
    end
    return total
end

input = $stdin.read.split("\n")
n, ary = input[0].to_i, input[1].split(" ").map(&:to_i)
total = bubbleSort(n, ary)

puts "Array is sorted in #{total} swaps."
puts "First Element: #{ary.first}"
puts "Last Element: #{ary.last}"

github.com

バブルソートとは

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）

バブルソート - Wikipedia

まとめ

特に特筆すべき点なし

#9/20 Tries: Contacts [Cracking the Coding Interview Challenges]

#9 Tries: Contacts

www.hackerrank.com

シンプルなコンタクトリスト管理アプリケーションを作成する問題。

以下のフォーマットの入力が与えられる。

4
add hack
add hackerrank
find hac
find hak

1行目はオペレーション数、2行目以下は、スペース区切りでオペレーション(add or find)、オペレーションのパラメータ(文字列)となっている。 add の場合は、コンタクトリストへパラメータ(名前)を追加、findの場合はコンタクトリストからパラメータの文字列で始まるコンタクトの総数を表示する。

上記の入力の場合、実行結果は以下となる。

2
0

solution

以下はrubyでの解。 問題タイトルにあるように、トライ木のアルゴリズムを使って解いている。

#!/bin/ruby

class Node
    CHARACTER_OF_NODE = 26
    
    def initialize()
        @children = Array.new(CHARACTER_OF_NODE)
        @size = 0
    end

    def add(str, index = 0)
        @size += 1
        return if str.size == index
        
        current = str[index]
        child = getNode(current)
        if child == nil
            child = Node.new
            setNode(current, child)
        end
        child.add(str, index + 1)
    end
    
    def findContact(str, index = 0)
        return @size if str.size == index
        child = getNode(str[index])
        return 0 if child == nil
        return child.findContact(str, index + 1)
    end
    
    private 
        def getCharIndex(c)
            return c.ord - 'a'.ord
        end

        def getNode(c)
            return @children[getCharIndex(c)]
        end

        def setNode(c, node)
            @children[getCharIndex(c)] = node
        end
end

input = $stdin.read.split("\n")
n, contacts, list, node = input.shift, input, [], Node.new
contacts.each do |v|
    operation, name = v.split(" ")
    
    case operation
        when "add" then node.add(name)
        when "find" then puts node.findContact(name)
    end
end

github.com

トライ木とは

トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。

トライ木 - Wikipedia

まとめ

ゴリ推しで解こうとしても、大抵の場合はテストケースがタイムアウトし、パスできないようになっている。

トライ木を使えば高速にキー検索を行えるため、全てのテストケースをパスできた。

実際にトライ木アルゴリズムを書いたのは初めてかもしれない。とても美しい。