前置き
この記事について
Nimを理解するために「世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法」のChapter1を解いてみたよ、という記事です。
Nimとは
Nimは、
そもそもNimって何なの？という人は至高の言語、Nimを始めるエンジニアへやNim Tutorial Part Iを日本語訳してみた（前編）を読みましょう。
他のChapter
Chapter1:Arrays and Strings(これ)
Chapter2:Linked Lists
以下は手付かず
Chapter3:Stacks and Queues
Chapter4
Chapter5
Chapter 1
やっていきます。退路を断つためにも今回使用したコードはすべてgithubに上げました。記事では割愛しましたがunittestも書きました。
頑張って進めていきます。
ちなみにNimのバージョンは0.18.0で、すべてUbuntu17.10で実行しました。
すべてファイル頭に
import system, macros, algorithm, tables, sets, lists, queues, intsets, critbits, sequtils, strutils, math, future, unicode
が必要です
Problem 1
Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
「ある文字列に含まれる文字がすべて一度しか登場しないか判定するアルゴリズムを書きなさい。もしもデータ構造を新たに使うことができないとしたらどうしますか？」
Nimでは関数の宣言はproc <関数名>(<引数>:<型名>):<戻り値の型>=なんですね。
変数の宣言には三通りあり、
const(コンパイル時に値が決定できる定数)
var(値が変更できる定数)
let(値を変更できない定数)
です。
もとの文字列の文字数と、使われている文字の集合のサイズが等しいか確認すればいいです。
proc Ch1_1(s:string):bool= # コメントは文頭にシャープ
let test:seq[Rune] = s.replace(" ","").toRunes() # 変数の型を記述するならこう
let sSet = toSet(test) # ただし無くてもコンパイラが推定してくれる
len(sSet) == len(test)
データ構造を使わない場合は、今回のNimを勉強するという目的から逸れるので飛ばしました。
Problem 2
Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.
「与えられた二つの文字列が、アナグラムになっているか調べる関数を書きなさい」
cmpは同じ型の変数を受け取って大小を判定するプロシージャです。
sortedによればそのようなプロシージャであればなんでも渡して良いようです。
これは言うことないですね。
ソートして同じ文字列になれば並べ替え可能です。
proc Ch1_2(a,b:string):bool=
sorted(a,cmp) == sorted(b,cmp)
Problem 3
URLify: Write a method to replace all spaces in a string with '%20: You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the "true" length of the string. (Note: If implementing in Java, please use a character array so that you can perform this operation in place.)
「渡される文字列のすべてのスペースを%20で置き換える関数を作りなさい。渡される文字列は新たな文字を追加するのに十分なスペースを持っていると仮定して良い。また、文字列の真の長さを与えられるものとします。（注意：もしJavaで書く場合、この操作を実行できるように文字配列を利用してください。）」
このプロシージャにはreturn句がありませんが、それはNimには暗黙の変数resultがあるからです。
プロシージャは返り値の型（この場合はstring）の変数resultを持ち、下のreplace()のようにstringを返す文の返り値がresultに代入され、return句がない場合勝手にreturnされます。
proc Ch1_3(s:string):string=
replace(s," ", by="%20")
Problem 4
Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.
「文字列が与えられます。その文字列が回文のアナグラムであるか判定する関数を書きなさい。アナグラムとは文字を並べ替えたものです。回文は辞書に載っているような単語に限定されません。」
EXAMPLESではスペースを無視していたのでそのように。
toRunes()はunicode文字列を取り扱うための関数で、テストケースに日本語の回文を追加したかったので挿入しました。
最後のreturn句が実は不要なのはProblem 3で書いたとおりです。でもあったほうがわかりやすそう
proc Ch1_4(s:string):bool=
var odd = 0
for l in s.replace(" ","").toRunes().toSet():
if s.toRunes().count(l) mod 2 == 1:
odd = odd + 1
# 並びかえて回文（Permutation）になるような文字列は、各文字が偶数回出現するか、１種類を覗いて偶数回出現する
return odd<=1
Problem 5
One Away: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.
「文字列に対する三つの操作：文字の挿入、文字の除去、文字の置換のどれかを一度使って（または一度も使わずに）、二つの文字列を一致させることができるか判定する関数を書きなさい」
動的計画法のやつですね。
一応バックトラックも用意しようかと思ったのですが面倒でやめました。名残がありますが
high(int)でint型が表現できる最大値を得ています。
seqが多分いわゆる動的配列だと思います。静的型付けの言語に触るのが本当に久々なのでこの辺りはあやふやです。
多次元配列を宣言と同時に初期化する方法も自分なりに調べたんですが見つかりませんでした。おかげで不格好になりました。
for文では0..Nというふうに範囲を指定することができます。イテレータcountup(0,N)へのエイリアスです。
Nを含むのがPythonと違うところです。
4/4追記
..<で終点を含まないようになるそうです。
proc Ch1_5(a,b:string):bool=
var table:seq[seq[int]]=newSeq[seq[int]](len(a))
var table_back: seq[seq[int]]=newSeq[seq[int]](len(a))
let cost_mismatch = 1
let cost_slice = 1
table.fill(newSeq[int](len(b)))
for i in 0..len(table)-1:
table[i].fill(high(int))
for ai in 0..<len(table):
table[ai][0] = cost_slice * abs(ai-0)
for bi in 0..<len(table[0]):
table[0][bi] = cost_slice * abs(0-bi)
for ai in 1..<len(table):
for bi in 1..<len(table[0]):
table[ai][bi] = min(
[table[ai-1][bi-1]+int(a[ai]!=b[bi])*cost_mismatch,
table[ai][bi-1]+cost_slice,
table[ai-1][bi]+cost_slice]
)
# ちなみにそのものの関数がある
# echo a.editDistance(b)
table[len(table)-1][len(table[0])-1]<=1
終わる頃に知りましたがレーベンシュタイン距離をまさに返す関数がありました。悲しい
Problem 6
String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).
「文字の繰り返し回数を利用する基礎的な文字列圧縮の関数を書きなさい。例えば、"aabcccccaaa"は"a2b1c5a3"と圧縮されます。もしも"圧縮後"の文字列が圧縮前のものよりも小さくならない場合はもとの文字列を返すようにしなさい。登場する文字は大文字か小文字のアルファベットだけだと仮定して良い」
str[i+1]がコケないのはNimのstringの仕様によるもののようです。
頭でresultに空の文字列を代入しています。
プロシージャが宣言されたときのresultの値は返り値の型に依存し、string型の場合のデフォルト値はnilです。
nilにaddするとコケるので空の文字列を事前に代入しています。
proc Ch1_6(str:string):string=
result = ""
var l:char
var c=1
for i in 0..len(str)-1:
l = str[i]
if str[i] == str[i+1]:
c+=1
else:
result.add(l&intToStr(c))
c=1
if len(result) < len(str):
return result
else:
return str
Problem 7
Rotate Matrix: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
「それぞれのピクセルが４バイトの、N*N行列で与えられる画像を９０度回転させなさい。これをその場でやることができますか？」
in placeはプログラム用語で"追加の記憶領域をほとんど使わずに行うアルゴリズムを意味する。"そうです。
直しました（４/４）
Nim by Examplesをガッツリ参考にしました。
arrayは固定長配列です。
array[1..N,int]の書き方が若干面白く、配列への添字は1~Nでアクセスするようになります。
type
Image[N:static[int]] = array[1..N,array[1..N,int]]
var image:Image[3] = [[1,2,3],[0,0,0],[0,0,0]]
proc Ch1_7(i:var Image)=
for x in 1..len(i):
for y in 1..<x:
swap(i[x][y],i[y][x])
Problem 8
Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
「ある要素が０のとき、それを含む行と列をすべて０にするアルゴリズムを書きなさい」
書いてあるとおりに書いただけで、もしかしたらfilterやmapを使ってもっとスマートに書けるんじゃないかと疑ってます。
章を進めるうちにひらめいたら修正します。
proc Ch1_8(m:Matrix):Matrix=
var m_row:array[1..len(m),int]
var m_col:array[1..len(m[1]),int]
var am = m
for l in 1..len(m):
for e in 1..len(m[l]):
if m[l][e] == 0:
m_row[l] = 1
m_col[e] = 1
for l in 1..len(am):
for e in 1..len(am[l]):
if m_row[l] == 1 or m_col[e] == 1:
am[l][e]=0
return am
Problem 9
Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).
「関数isSubstringは、文字列を二つ与えると片方がもう一方の部分文字列であるか判定します。この関数isSubstringを一度だけ呼び、ある文字列s1が文字列s2を巡回させたものか判定するコードを書きなさい。（例えば、"waterbottle"は"erbottlewat"を巡回させたものです）」
isSubstringにあたる関数はcontainsです。
s1とs2の長さが等しく、s1を二度繰り返したものがs2を含む場合、二つの文字列は巡回関係にあるので
proc Ch1_9(s1,s2:string):bool=
len(s1)==len(s2) and repeat(s1,2).contains(s2)
やってみた感想
配列やとくに多次元配列の取扱はあまり得意じゃないのでやっていてもっとスムーズな（Nimらしい）答えがあるんじゃないかとやきもきしました。
今後二章三章とやっていってこなれてきたらもう一度挑戦したいです。