Nimでコーディング面接に立ち向かう-第2章-Linked Lists

前置き

この記事について

Nimを理解するために「世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法」のChapter2を解いてみたよ、という記事です。

Nimとは

Nimは、
そもそもNimって何なの？という人は至高の言語、Nimを始めるエンジニアへやNim Tutorial Part Iを日本語訳してみた（前編）を読みましょう。

他のChapter

Chapter1:Arrays and Strings
Chapter2:Linked Lists(これ)
以下は手付かず
Chapter3:Stacks and Queues
Chapter4
Chapter5

Chapter 2

やっていきます。今回もコードはすべてgithubに上げました。記事では割愛しましたがunittestも書きました。
頑張って進めていきます。
ちなみにNimのバージョンは0.18.0で、すべてUbuntu17.10で実行しました。
すべてファイル頭に

import

import system, macros, algorithm, tables, sets, lists, queues, intsets, critbits, sequtils, strutils, math, future, unicode

が必要です。

Chapter 2のテーマ

このチャプターのテーマは「単方向リスト」です。
なのでまず単方向リストを実装します。

myarray.nim

myarray.nim

type
  MyArray* = ref ArrayObj
  ArrayObj* = object
    next*: MyArray
    data*: int

*を付けたものは他のmoduleからアクセスできるようになります。

the * means that name is accessible from other modules

コアになる部分は上の宣言だけですが解答の役に立ちそうなlenや[]、find、appendを用意しました。
他のコードから使うときはimport myarrayを書きます。pythonといっしょですね。わかりやすい

どうしても空の配列[]を表現する方法を思いつかなかったのでCh.2は全体的にみっともない処理が多いです。
他にも循環参照のある単方向リストでコケる、int型しか受け付けないなど実用に足るものではないですが、参考というか、日本語で説明があるNimのコードはたくさんあったほうが自分のような初学者の取っ掛かりにはなると思うので載せておきます。

Problem 1 "Remove Dups"

Remove Dups: Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
「ソートされていない単方向リストから重複を取り除くコードを書きなさい。バッファを使わないで解けますか？」

find()を作ったので普通に解くのは簡単……

Ch2_1.nim

proc Ch2_1(a:MyArray):MyArray=
  result = MyArray(data:a[0].data)
  for i in 1..<len(a):
    if result.find(a[i].data) == -1:
      result.append(a[i].data)

バッファを使わない場合はこれから考えます。

Problem 2

Implement an algorithm to find the kth to last element of a singly linked list.
「k番目から最後までの要素を取り出すアルゴリズムを実装しなさい」

Ch2_2.nim

proc Ch2_2(a:MyArray,k:int):MyArray=
  # k<len(a)とする
  # これは空配列[]が表現できなかった都合上である
  result = MyArray(data:a[k].data)
  for i in (k+1)..<len(a):
      result.append(a[i].data)

本来であればk>=len(a)の場合は空配列[]が返るべきですが、先に述べたとおり空配列が表現できなかったので、k<len(a)の条件を勝手に加えました。
……と書きましたが、後ろ方向へは連結しているのでこれで問題ないですね。

Ch2_2.nim

proc Ch2_2_remake(a:MyArray,k:int):MyArray=
  result = a[k]

Problem 3 "Delete Middle Node"

Delete Middle Node: Implement an algorithm to delete a node in the middle (i.e., any node but the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node.
EXAMPLE
Input: the node c from the linked list a - >b- >c - >d - >e- >f Result: nothing is returned, but the new linked list looks like a - >b- >d - >e- >f
「中間のノードを削除する：中間のノードを削除するアルゴリズムを作りなさい。先頭や終端を削除する必要はなく、厳密に中央のノードでもありません。与えられるのは削除するノードへの参照のみです
例：単方向リストa->b->c->d->e->fにおいて、cを削除する。
結果：何も返しませんが、新しい単方向リストはa->b->d->e->fとなります。」

作ったMyArrayでは.nextに次の要素への参照を格納してるので、例で言えば
b.next=d
とする処理を行うか、

c.data=d.data
c.next=d.next

とするかがあります。
先頭への参照を受け取れないので下の方法を使います。

Ch2_3.nim

proc Ch2_3(c:var MyArray)=
  if c.next != nil:
    c.data = c.next.data
    c = c.next

Problem 4 "Partition"

Partition: Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x . lf x is contained within the list, the values of x only need to be after the elements less than x (see below) . The partition element x can appear anywhere in the "right partition"; it does not need to appear between the left and right partitions.
EXAMPLE
Input: 3 -> 5 -> 8 -> 5 - > 10 -> 2 -> 1 [partition = 5]
Output: 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8
「区分け：単方向リストを与えられる値ｘで仕切るコードを書きなさい。新しい単方向リストでは、すべてのｘより小さな値の要素はｘ以上の値を持つどの要素よりも前にあります。もしｘがリスト内にある場合、ｘはただｘ未満の要素より後にある必要があります（下の例を見てください）。区切りの要素ｘは、”仕切りの右側”のどこかに存在します。仕切りの左右の間にある必要はありません：
例：
Input: 3 -> 5 -> 8 -> 5 - > 10 -> 2 -> 1 [partition = 5]
Output: 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8」

Ch2_4.nim

proc Ch2_4(a:MyArray,p:int):MyArray=
  result = MyArray(data:0)
  var
    l = MyArray(data:0)
    g = MyArray(data:0)
  for i in 0..<len(a):
    if a[i].data < p:
      l.append(a[i].data)
    else:
      g.append(a[i].data)
  echo l
  echo g
  result = l
  result[len(result)-1].next=g[1]
  result[0] = result[1]

最後の行では何をしているのかというと、空のリストが作れなかったため頭に0が入ってしまっているので、先頭を飛ばしています。

Problem 5 "Sum Lists"

Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1 's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2) .That is,617 + 295.
Output: 2 - > 1 - > 9. That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).Thatis,617 + 295.
Output: 9 - > 1 - > 2. That is, 912 .
「単方向リストで表現された二つの数値を与えられます。それぞれのノードにはひと桁の数字が格納されています。数字は逆順で格納されているので、初めの数字が１の位になります。二つの数値を足しあわせ、単方向リストにして返す関数を書きなさい。また、順方向に格納した場合の関数も書きなさい」

Ch2_5.nim

proc Ch2_5(a,b:MyArray):MyArray=
  result = MyArray(data:0)
  var
    anum:int=0
    bnum:int=0
  for i in 0..<len(a):
    anum += a[i].data*10^i
  for i in 0..<len(b):
    bnum += b[i].data*10^i

  for l in (anum+bnum).intToStr.reversed:
    result.append(($l).parseInt())

  # [](空の配列)が用意できなかったので……。
  result[0] = result[1]



proc Ch2_5_F(a,b:MyArray):MyArray=
  result = MyArray(data:0)
  var
    anum:int=0
    bnum:int=0
  for i in 0..<len(a):
    anum += a[i].data*10^(len(a)-i-1)
  for i in 0..<len(b):
    bnum += b[i].data*10^(len(b)-i-1)

  for l in (anum+bnum).intToStr:
    result.append(($l).parseInt())

  # [](空の配列)が用意できなかったので……。
  result[0] = result[1]

本当にpython的に書けるなあと思いました。

Problem 6 "Palindrome"

Palindrome: Implement a function to check if a linked list is a palindrome.
「回文：ある単方向リストが回文になっているか確かめる関数を書きなさい」

Ch2_6.nim

proc Ch2_6(a:MyArray):bool=
  result = true
  var reversed=MyArray(data:0)
  var t:MyArray
  for i in 0..<len(a):
    t=MyArray(data:a[i].data)
    t.next=reversed[0]
    reversed = t
  for i in 0..<len(a):
    if a[i].data != reversed[i].data:
      result = false

他に思いつかなかったので逆順のリストを力技で作って頭から比較する方法を選びました。

Problem 7 "Intersection"

Intersection: Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting node. Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.
「二つの単方向リストが与えられます。二つのリストが途中で合流している場合、それを見つけてください。合流するノードを返してください。なお、合流は参照によって判断し、値によっては判断しないでください。もしも１つ目のリストのk番目の要素と２つ目のリストのｊ番目の要素が参照ベースでまったく同じノードだった場合に、これらが合流しているといいます」

Ch2_7.nim

proc Ch2_7(a,b:MyArray):MyArray=
  result = a
  block doubleloop:
    for ai in 0..<len(a):
      for bi in 0..<len(b):
        if a[ai].next == b[bi].next:
          result = a[ai].next
          break doubleloop

今回はNimでまだ使ってない仕様を使いました。
break文では一番内側のループを抜けますが、上のようにblockを作ってラベルをつけることによって、bleak <ラベル名>でブロックを脱出することができます。

Problem 8

Loop Detection: Given a circular linked list, implement an algorithm that returns the node at the　beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A -> B -> C -> 0 -> E - > C [the same C as earlier]
Output: C
「単方向リストの循環を検知し、循環の始まりのノードを返してください」

フロイドの循環検出法を使います。
一重目で循環していることの検知、二重目で循環節の始まりを探しています。
wikipediaの説明文を読んだ限りだと9行目は要らないような気がするんですが無いと１個ずれてしまう

Ch2_8.nim

proc Ch2_8(a:MyArray):MyArray=
  result = MyArray(data:100)
  var
    turtle=a[0]
    rabbit=turtle.next
  while true:
    if turtle.next == rabbit.next and turtle.data == rabbit.data:
      turtle = a[0]
      rabbit = rabbit.next
      while true:
        if turtle.next == rabbit.next and turtle.data == rabbit.data:
          result = rabbit
          break
        else:
          rabbit = rabbit.next
          turtle = turtle.next
      break
    else:
      turtle = turtle.next
      rabbit = rabbit.next
      if turtle != nil and rabbit != nil:
        rabbit = rabbit.next
      else:
        break

やってみた感想

とにかく不格好なコードが多く悔いが残る結果となりました。