swiftでアナグラム
swift playgrouds での6番目のプログラミング。今回はアナグラムの生成。
アナグラムとは、単語の文字をいくつか入れ替えることで、別の単語を作り上げて、別の意味を持たせる遊びです。
ノストラダムスがナンダッテー ΩΩΩ に出てくる文字を入れ替えて別の単語にするアレです。
“/usr/share/dict/words” に英単語集があります。この単語集とコレクションクラスの各種メソッドを使って、与えられた英単語からアナグラムになる英単語を出力します。
入力例
let theAnagram = MTFAnagrams()
print(theAnagram.anagrams("thinker")) // thinker(思想家) -> rethink(再考)
print(theAnagram.anagrams("canoe")) // canoe(カヌー) -> ocean(海)
print(theAnagram.anagrams("orange")) // orange(オレンジ) -> onager(投石機)
print(theAnagram.anagrams("valencia")) // valencia(スペインの地名？) -> valiance(たれ布?カーテン?)
出力例
["rethink"]
["acone", "ocean"]
["onager"]
["valiance"]
ソースコードを分けた
ソースコードを分けて、別ファイルに入れると実行スピードが上がる。 おそらく、別ファイルにすることでトレース機能が及ばなくなるのだと思われる。
アナグラムを探し出すクラスは以下のようになってます。ファイルanagrams.swiftに書いている。
import Foundation
public struct MTFAnagrams
{
let wordSet: Set<String>
public init()
{
// - テキストファイルから読み込み、単語の集合を作る
let wordArray:[String] =
try! String.init(contentsOfFile:"/usr/share/dict/words") // ファイルから読み込み
.components(separatedBy:"\n") // 改行で分割し
self.wordSet = Set<String>(wordArray) // 単語の存在確認のために、集合にしておく。
}
public func anagrams(_ word:String) -> Set<String>
{
// 1単語毎に単語を入れ替えた仮のアナグラムを生成。
let anagrams = Set(
word.characters // 文字毎に分解
.flatMap{ String($0) } // 型を文字列に変換
.permutations() // 文字順を入れ替えた仮のアナグラムの配列を生成
.map{ $0.joined() } // 1文字毎だったものを連結
.flatMap // 仮のアナグラムが単語集wordSetにある場合は、アナグラムである。元の文字列と同じものは除く
{
(anagram:String) -> String? in
word != anagram && self.wordSet.contains(anagram) ? anagram : nil
}
)
return anagrams
}
}
swiftで特徴的なのは、クラスやメソッドの可視スコープです。 今まで、プレイグラウンドで1つのファイルでやっていたので気がつかなかったが、ファイルや、フレームワークがスコープの範囲になっています。
ファイルを分けたことで、別ファイルから利用するには、 “public” キーワードを付けました。
アルゴリズムに関してはコメントを参考にしてください。
また、アナグラムを作るのに、arrayにメソッド “permutations” を追加しました。ファイル “ArrayExtension.swift” にエクステンションを書いています。
import Foundation
extension Array
{
// 各要素の順列違いを全て生成する。n!個のパターンを作る。nが8を越えると猛烈に遅くなる。
// 注意：nが大きくなると爆発的に巨大な数になるのでカードゲームのシャッフルなどには使わないこと
// https://stackoverflow.com/questions/34968470/calculate-all-permutations-of-a-string-in-swift
public func permutations() -> [[Element]]
{
var scratch = Array(self) // This is a scratch space for Heap's algorithm
var result: [[Element]] = [] // This will accumulate our result
// Heap's algorithm
func heap(_ n: Int)
{
if n <= 1
{
result.append(scratch)
return
}
for i in 0..<n-1
{
heap(n-1)
let j = (n%2 == 1) ? 0 : i
swap(&scratch[j], &scratch[n-1])
}
heap(n-1)
}
// Let's get started
heap(scratch.count)
// And return the result we built up
return result
}
}
これは、可能な組合せの配列を返すメソッドです。コードは stackOverFlow から引用したものをコンパイルが通るように修正を加えただけ。
参考文献のサンプルコードからの移植の感想
元のコードはC++のSTLを使ったサンプルコードです。以下C++やObjective-Cとの違いの感想です。
- C++よりもエラーメッセージがわかりやすい
- クロージャーのおかげで、関数オブジェクトの事を考えなくて良く楽
- unixのフィルターを使った1行プログラミングに近い感じがする
- forよりもmapを使うと見た目がスッキリする事が多い
- 今回は使用しなかったが、forとカウンタ変数を使うよりも数列 ( 1…5 ) の表記とmapを組み合わせた方がキレイ。
- reduceよりも使えるならばjoinedを使うと見た目がキレイ。
後の課題は、オプショナルとアンラップがまだよくわかっていない。
参考文献とソースコード
- STL標準テンプレートライブラリによるC++プログラミング
- https://www.amazon.co.jp/STL―標準テンプレートライブラリによるC-プログラミング-Higher-education-computer/dp/4795296987
Swiftで8人の女王その2
reduceの代わりにjoinを使うとメソッドdebugPrintが簡潔にかけるようになった。 文字列の結合や配列の結合くらいでは、joinの方が見た目が綺麗。
// debug用出力
func debugPrint()
{
// 数列に対するmap&joinedを行い、デバッグ文字列を作成する
print(
( 0..<queens.count ).map
{
i -> String in // ここで引数に名前をつけないと内側のmapのクロージャでアクセスできない。
(0..<sizeN).map{ $0 == queens[i] ? " q" : " ." }.joined() + "\n"
}.joined()
)
}
メソッドresolveの方はreduceの代わりにflatMapを二重にかけた方が簡潔に見える。
func resolve() -> [EQBoard]
{
precondition(queens.count <= self.sizeN)
func resolve_intarnal( _ count:Int, _ boards:[EQBoard]) -> [EQBoard]
{
return count == 0 ? boards :
resolve_intarnal(
count - 1,
boards.flatMap
{
i -> [EQBoard] in // この記述がないと曖昧(ambiguous)でわからぬとエラーが出る
(0..<i.sizeN).flatMap
{
i.tryAddAQueen($0) ? i.boardAddAQueen($0) : nil
}
})
}
return resolve_intarnal(self.sizeN, [self])
}
参考文献とソースコード
- Logo 人工知能へのアプローチ
- https://www.amazon.co.jp/Logo-人工知能へのアプローチ-ラジオ技術選書-150-祐安-重夫/dp/4844301500
Swiftで8人の女王
swift playgrouds での5番目のプログラミング。今回は8Queenパズル。
チェスのクイーンは、チェス盤上で最も自由に動けまわれるコマです。 縦横斜めの8方向に、任意の数だけ駒を進めることが出来ます。将棋でいう飛車と角を合わせた動きです。
このクイーンを8x8のチェス盤上に8個、お互いに取られないように配置するのが8Queenパズルです。
解法は 8Queen から見てゆくとわかりやすいです。
参考文献ではバックトラッキングの例題として書かれて素直に移植したつもりだった。 しかし書いているうちに、深さ優先の検索でなく広さ優先検索になっていた。
作ったクラスの動き
以下のようにチェス版の大きさを指定して、結果を出力させます。sizeは板の大きさです。8Queenなので8の大きさにしてます。
let queen = EQBoard(size:8)
let QueenAnser = queen.resolve()
QueenAnser.map{ $0.debugPrint() }
print("---\(QueenAnser.count)")
出力結果は以下のようになります。
q . . . . . . .
. . . . q . . .
. . . . . . . q
. . . . . q . .
. . q . . . . .
. . . . . . q .
. q . . . . . .
. . . q . . . .
q . . . . . . .
. . . . . q . .
. . . . . . . q
. . q . . . . .
. . . . . . q .
. . . q . . . .
. q . . . . . .
. . . . q . . .
q . . . . . . .
. . . . . . q .
. . . q . . . .
. . . . . q . .
. . . . . . . q
. q . . . . . .
. . . . q . . .
. . q . . . . .
.
.
.
. . . . . . . q
. . . q . . . .
q . . . . . . .
. . q . . . . .
. . . . . q . .
. q . . . . . .
. . . . . . q .
. . . . q . . .
---92
qの文字はQueenの位置を示しています。最後の–92は、結果が92パターンの配置があるとの結果です。
作ったクラスの中み
構造体の名前は “EQBoard” 、プロパティは2つ、メソッド数は 6つ。
初期化メソッドが2つ、デバッグメソッドが1つなので、計算をする部分は事実上3つのメソッドで行なっています。
で、メインの3つのメソッドは以下の通り。
- resolve
- ここで、解を求める
- boardAddAQueen
- 今の盤にqueenを1個追加した盤を返す。resolveの補助。
- tryAddAQueen
- 今の盤に配置可能かのチェックを行う。resolveの補助。
ソースはこんな感じ。
func resolve() -> [EQBoard]
{
precondition(queens.count <= self.sizeN)
func resolve_intarnal( _ count:Int, _ boards:[EQBoard]) -> [EQBoard]
{
if count == 0
{
return boards;
}
// 与えられた板の次のrawの配置の配列を計算する
return resolve_intarnal( count - 1,
boards.reduce([])// 計算結果を配列にひとまとめにする
{
let i = $1
return $0 + ( 0..<i.sizeN ) // 横のマスの数だけ、置いて試す
.flatMap
{
i.tryAddAQueen($0) ? i.boardAddAQueen($0) : nil
}
})
}
return resolve_intarnal(self.sizeN, [self])
}
// queenを1個追加した盤を返す
func boardAddAQueen(_ newQueen: Int) -> EQBoard
{
precondition(newQueen >= 0)
precondition(newQueen < self.sizeN)
precondition(queens.count < self.sizeN)
return EQBoard(size:self.sizeN, queens: self.queens + [newQueen])
}
// 配置可能かのチェックを行う
func tryAddAQueen(_ newQueen: Int) -> Bool
{
precondition(newQueen >= 0)
precondition(newQueen < self.sizeN)
// 縦方向と左右の斜めにQueenがないかチェックする
return ( self.queens.enumerated().map
{
( $0.element == newQueen) || /* 縦が一致 */
( $0.element == newQueen - self.queens.count + $0.offset ) || /* 斜め左方向が一致 */
( $0.element == newQueen + self.queens.count - $0.offset ) ? /* 斜め右方向が一致 */
false : true
}.filter{ $0==false }.count ) == 0
}
解説は、次回のCocoa勉強会で行います。じゃあね。
参考文献とソースコード
- Logo 人工知能へのアプローチ
- https://www.amazon.co.jp/Logo-人工知能へのアプローチ-ラジオ技術選書-150-祐安-重夫/dp/4844301500