#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

まとめ

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

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

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

#7/20 Trees: Is This a Binary Search Tree? [Cracking the Coding Interview Challenges]

#7 Trees: Is This a Binary Search Tree?

www.hackerrank.com

データ構造が二分探索木になっているかどうかをチェックする問題。

• The value of every node in a node’s left subtree is less than the data value of that node.
• The value of every node in a node’s right subtree is greater than the data value of that node.

つまり、与えられたデータ構造が二分木探索木(左の子の値 < 親の値 < 右の子の値)となっているかどうかをチェックする。 チェックして、データ構造が二分探索木になっていれば、trueを、それ以外はfalseを返せばよい。

solution

python3での解

def check(root, min, max):
    if root == None:
        return True
    if root.data <= min or max <= root.data:
        return False
    return check(root.left, min, root.data) and check(root.right, root.data, max)
    
def checkBST(root):
    return check(root, float('-inf'), float('inf'))

github.com

Binary Tree とは

二分木（binary tree; 二進木、バイナリツリー）は、データ構造の1つである。根付き木構造の中で、あるノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 たとえば、二分探索や二分ヒープを実装するために使われる。

二分木 - Wikipedia

Binary Search Tree とは

二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。

二分探索木 - Wikipedia

メアリと魔女の花を観た

*以下の内容はネタバレを含みます。

「メアリと魔女の花」を観てきた。

www.maryflower.jp

以前映画館で予告を観た時、とても面白そうだと思った。

予告を見る限り、どう観てもジブリ作品にしか見えないが、スタジオポノックというアニメ制作会社の作品らしい。

www.ponoc.jp

この制作会社はジブリの意思を受け継いだ人たちによって立ち上げられた会社のようだ。 まあそれはどうでもよくて、とにかく興味が湧いたので見ることにした。

イントロの赤毛の魔女

いきなり謎の赤毛の魔女が追手に追われるところから始まる。 この時点では何もわからないので、この赤毛の魔女が主人公なのかな？と思った。

花を奪って地上に墜落するまで、疾走感があって惹きつけられた。 思い返すとこのイントロが一番テンションが上った場面だった。

メアリは赤毛の魔女ではなかった。

赤毛の魔女のイントロが終わるとメアリが登場。あれ、同じ赤毛だけどさっきの魔女より幼いし顔も違う。 さっきの魔女が主人公の話ではないのか。

しばらくはメアリの日常パートが続く。良くも悪くも、使い古されたジブリっぽさのあるキャラクターアニメーション。

メアリのおっちょこちょい表現が割りと度を越していて、注意欠陥ではないかと疑うレベルに酷いのが気になった。

赤毛を気にしているところから、「赤毛」というのがキーワードでこの世界では特別だということが理解できる。

なぜギブ(黒猫)はメアリを夜間飛行へ案内した？

西洋の御伽話や寓話には、黒猫がしばしば魔女の使い魔として登場する。この映画も例外ではなく、黒猫が登場する。

ギブはメアリを夜間飛行まで案内するが、どうもここが腑に落ちない。 ギブにはティムを助けるという動機があることが後にわかるが、初回の案内時にはまだティムは攫われていなかったはずだ。

なぜギブはメアリを夜間飛行へ連れて行った？

ティムはなぜ変身実験台として攫われた？

これが一番の謎。 変身実験台に地上の動物が使われていたので、ティムも変身実験台の対象となることはわかるが、なぜティムが選ばれた？

箒に掘られていた文字は何？

なんだったんだろう？持ち主の名前でなければ、あれは魔法陣のようなものか？

夜間飛行によって烙印された手の紋章は何？

あの紋章は何だったのか？

エンドワ大学

実質、あの学校に存在しているのは、マダムとドクター、佐藤二朗(箒管理者)の3人だけしかない。

学校がこの物語に本当に必要だったのか疑問だ。

魔女という神秘的なワード使っておきながら、規格化された明るい大学で勉強するというあまりにも平凡なバックグラウンドが明らかになり一気に醒めてしまった。 魔女というのは、魔女狩りの文脈の魔女ではなく、ハリポタ文脈の魔法使い少女だったか。

ピーターとの関係

ピーターは恋人でもなんでもないし、そういうストーリーもない。 助けに行く動機として考えられるのは、完全に自分の失敗の尻拭いである。

再会後の恋心を頂いていると勘違いさせるような描写は本当に余計だったと思うし、中途半端だった。

シャーロットおばあちゃん

シャーロットおばあちゃんが実は謎の赤毛の魔女だったことが明かされる。

シャーロットおばあちゃんが、メアリに夜間飛行を取り返してくるようお願いするが、 おばあちゃん何も手助けができずにメアリに全てを託すことになる。

もう魔法を使えないと言っていたのは、歳を取ったから？それとも墜落するときに、髪が黒髪に戻っていたのでそのときに魔法の力を失った？

力が使えないにせよ、優しいおばあちゃんが、メアリに死ぬかもしれないような危険なことを丸投げするのはちょっと信じられなかった。 夜間飛行の力を使って1日だけまた魔法使いに(若返って)戻って、メアリと一緒にピーターを助けに行くぐらいの展開があってもよかったんじゃないかな。

メアリはただの赤毛少女だった

メアリは赤毛であり何かしら、シャーロットから魔女の血を受け継いでいると容易に予想できるが、魔女の力に目覚める、なんてことはなく、一度もその設定は生かされなかった。 そのため、メアリはただの平凡な赤毛少女、で終わってしまった。

これはメアリの成長物語ではない

魔女の力も、箒の修理も、呪文の解除も、全て他力で、メアリ自身の成長によって解決されたものではない。

結局このストーリーが何を伝えたかったのか、エンドロール中に色々思い返してみたが、何もわからなかった。

まとめ

魔女の宅急便、という映画はとても優れた作品であるということを再認識した。

#8/20 Heaps: Find the Running Median [Cracking the Coding Interview Challenges]

#8 Heaps: Find the Running Median

www.hackerrank.com

以下のような入力が与えられる。 1行目は、データの数、2行目以下はデータリストに追加する数となっている。

6
12
4
5
3
8
7

上記の入力が与えられた場合、1行毎にデータリストへ値を追加し、その時点でのデータリストの中央値を計算し以下のフォーマットで出力する。

12.0
8.0
5.0
4.5
5.0
6.0

solution

rubyで解いた。 rubyのsortメソッドを使えばarrayのソートについては何も考える必要はないが、本問題はそれではパスできないテストケースが用意されている(timeoutを起こす)。そのため、処理速度を考慮したコードを書く必要がある。 この問題では、1行毎にデータがリストへ追加されるため、ソートアルゴリズムとして挿入ソートを採用した。

def insertSort(ary, num)
    if ary.empty?
        ary << num
    else
        left, right, mid = 0, ary.length - 1, 0
        while left < right do
            mid = right <= 0 ? 0 : (left + right) / 2
            if num < ary[mid]
                right = mid - 1
            else
                left = mid + 1
            end
        end
        if num < ary[left]
            ary.insert(left, num)
        else
            ary.insert(left + 1, num)
        end
    end
    return ary
end

input = $stdin.read.split("\n").map(&:to_i)
n, nums, ary = input.shift, input, []
nums.each do |num|
    ary = insertSort(ary, num)
    len = ary.length
    puts (ary[(len - 1) / 2] + ary[len / 2]) / 2.0
end

github.com

中央値とは

中央値（ちゅうおうち、英: median）とは、代表値の一つで、有限個のデータを小さい順に並べたとき中央に位置する値。たとえば5人の人がいるとき、その5人の年齢の中央値は3番目に年寄りな人の年齢である。ただし、データが偶数個の場合は、中央に近い2つの値の算術平均をとる。中央値の事を、メディアン、メジアン、中間値とも呼ぶ。ただし、「中間値の定理」の中間値はこの意味ではない。

中央値 - Wikipedia

挿入ソートとは

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。

挿入ソート - Wikipedia

感想

中央値算出は単純に見えて、案外嵌りやすい気がする。良問。

#6/20 Queues: A Tale of Two Stacks [Cracking the Coding Interview Challenges]

#6 Queues: A Tale of Two Stacks

www.hackerrank.com

キュー操作を行う問題。以下のような入力を受け取る。

6
1 42
2
1 14
3
1 28

1行目はデータの数。2行目以下は、1つもしくはスペース区切りで2つの数値が入力される。

最初の数値をtype、2つめの数値をx と呼ぶ。以下のような3タイプの操作を行う。

• type 1: x をキュー(enqueue)に追加する
• type 2: キュー値を１つ取り出す(dequeue)
• type 3: キューの先頭の値を表示する

solution

input = $stdin.read.split("\n")
n, lines, queue = input.shift.to_i, input, []

lines.each do |l|
    t, x = l.split(" ")
    case t
    when "1" then
        queue.push(x)
    when "2" then
        queue.shift
    when "3" then
        puts queue.first
    end
end

github.com

キューとは

キュー（英: queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー、取り出すことをデキューという。

キュー (コンピュータ) - Wikipedia

#5/20 Stacks: Balanced Brackets [Cracking the Coding Interview Challenges]

#5 Stacks: Balanced Brackets

www.hackerrank.com

括弧記号のみで構成される文字列が入力として渡される。 {, }, (, ), [, ] 文字列の括弧が均衡していれば、YES、それ以外は NO を出力する。

例えば{[(])}は均衡していない。なぜなら閉じていない([) 部分の(が閉じられていないから。

{[(])} # NO
{[()]} # YES

solution

table = {"[" => "]", "(" => ")", "{" => "}"}
input = $stdin.read.split("\n")
n, l = input.shift.to_i, input

l.each do |str|
    stack = []
    str.split("").each do |c|
        if !stack.empty? && "])}".include?(c)
            break if table[stack.last] != c
            stack.pop
        else
            stack.push(c)
        end
    end
    puts stack.empty? ? "YES" : "NO"
end

github.com

スタックとは

この類いの問題は上記のように配列でスタックを実現することによって簡単に解くことができる。

スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。

スタック - Wikipedia