読者です 読者をやめる 読者になる 読者になる

euphonictechnologies’s diary

Haskell超初心者の日記です。OCamlが好きです。

follow us in feedly

TopCoder SRM 694 Div2 Hard : UpDownNess

プログラミングコンテスト

全然解けなかった。頑張って一週間かけて解いてみた。

問題

TopCoder Statistics - Problem Statement

1からNまで数字を並べるとき、並べ終わった列の中のlo-hi-loの出現数を考えます。lo-hi-loとは0<=i<j<kのときに並べ終わった列x中でx[i]<x[j]かつx[j]>x[k]となるような(要は真ん中がこんもりしてる)3つの数字の組です。例えば[ 1, 3, 4, 2 ] には(1, 3, 2), (1, 4, 2), (3, 4, 2)の3つのlo-hi-loがあります。

問題はNとKが与えられます。1からNまでを含む全ての列の中でlo-hi-loの数がK個になる列の数をカウントします。

方針

出題者のスライドがあるのでそちらを参照。DPで解く。

www.slideshare.net DPの配列は

dp[i][j] = 数列のパターン数

where

  • i = 1からiまでの数字を並べ終えたとき
  • j = j個のlo-hi-loを含む

当然答えはd[N][K]となります。なので、3重ループで

  1. iについて1からNまでループ、
  2. jについて0からKまでループ、
  3. i+1をiまでの数字の列に入れる時にどこの隙間に入れるか、例えば0なら先頭、3なら数列の3番めの要素の前、iなら一番最後です(ここ自分の少し失敗したところで、1からNまで並べるので、iが3の時、要素は3つで0オリジンの配列のインデックスと1オリジンの並べてる数字の最大数がずれます。なのでiの時一番最後となります)。

Code

3種類書いてみました。 まずは普通のforまわすDP。 lとrはそれぞれ挿入箇所の左にある要素の数、右にある要素の数です。

public class UpDownNess {
    public static final int DIVISOR = 1000000007;

    public int count(int N, int K) {
        int[][] dp = new int[5005][5005];
        dp[0][0] = 1;

        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < K + 1; j++) {
                for (int l = 0; l <= i; l++) {
                    int r = i - l;
                    if (j >= l * r) {
                        dp[i + 1][j] += dp[i][j - l * r];
                        dp[i + 1][j] %= DIVISOR;
                    }
                }
            }
        }

        return dp[N][K] % DIVISOR;
    }
}

次はメモ化再帰。countInnerは右と左にある要素の数がわかるとき分割統治法的に求められる、という考えが強調されていて私としては理解しやすいです。4つめを入れる時には3つ目までの時のパターンがわかっていると良くて、それは左に何もないとき、左が1つ、右2つの時、左が2つ、右1つの時、右に何もない時の4パターンで、それぞれのパターン内で再帰的にこの考え方を適用します。

public class UpDownNess {
    private static final int DIVISOR = 1000000007;
    private static int[][] dp = new int[5005][5005];

    int countInner(int n, int k) {
        if (n == 1 && k == 0) return 1;
        if (dp[n][k] >= 0) return dp[n][k];

        int ret = 0;
        for (int l = 0; l < n; ++l) {
            int r = n - 1 - l;
            if (k >= l * r)
                ret += countInner(n - 1, k - l * r);
            ret %= DIVISOR;
        }
        System.out.printf("%d %d called\n", n, k);
        dp[n][k] = ret % DIVISOR;
        return dp[n][k];
    }

    public int count(int N, int K) {
        for (int i = 0; i < 5005; i++) {
            for (int j = 0; j < 5005; j++) {
                dp[i][j] = -1;
            }
        }
        return countInner(N, K) % DIVISOR;
    }
}

最後にJava8特有のFunctionを使った汎用memoizeでのメモ化再帰。メモ化する関数はInt -> Int -> Intなのでmemoizeを二回使ってcurryingみたいなことをしています。何も考えずHashMapを使いました。つまり配列です。TreeMapとか使うよりは早いかと。

import java.util.HashMap;
import java.util.Map;
import java.util.function.Function;

public class UpDownNess {
    public static final int DIVISOR = 1000000007;

    public static <I, O> Function<I, O> memoize(Function<I, O> f) {
        Map<I, O> lookup = new HashMap<>();
        return input -> lookup.computeIfAbsent(input, f);
    }

    static int countInner(int n, int k) {
        if (n == 1 && k == 0) return 1;

        int ret = 0;
        for (int l = 0; l < n; ++l) {
            int r = n - 1 - l;
            if (k >= l * r)
                ret += cached.apply(n - 1).apply(k - l * r);
            ret %= DIVISOR;
        }
        return ret % DIVISOR;
    }

    private static final Function<Integer, Function<Integer, Integer>> cached =
            memoize(x -> memoize(y -> countInner(x, y)));

    public int count(int N, int K) {
        return cached.apply(N).apply(K) % DIVISOR;
    }
}

countInner内でもcachedを呼び出さないと全然メモ化されなくて意味ないのでそこに気をつける(私は15分ほど無駄にしました)。

ちなみにmemoize関数を使った実装でもシステムテスト通ります。時間的にも問題なしなのでさくっとメモ化再帰したい時にはいいかも。memoize関数をコピって貼っつけるだけで使えるしいい感じです。感覚的には普通のdp配列を使ったものに対するオーバーヘッドは+10~20%ぐらい。

反省

なぜか完全な全列挙をやろうとしていてperm関数を実装したりcomb関数を実装したりしていた。流石に全列挙してフィルタしてカウントしていたら太陽が何度爆発してお姉さんが何人爆死しても足りないことぐらいは気づくべき。

あとperm関数がStreamの形でしかかけなくてほんとダメな方の関数脳だなって思った。気をつけたい(でも再帰とパターンマッチで2秒でかけるものをwhile使って書くとかどうかしムニョムニョ...)。

[追記: 20160717 01:44] 加筆しました。

Swift 1.2から2.2でウラシマ状態 - ワーニングを撲滅する

iPhone Swift

ワーニングはエラーだ

今更かも知れませんがワーニングはエラーです。ワーニングはエラーです。ワーニングはエラーなんです。ワーニングを放置してコミットする意味がわかりません。なのでワーニングを修正していきます。

f:id:euphonictechnologies:20160605145205p:plain

このエントリは前回のエントリの続きです。

blog.euphonictech.com

ワーニングたち

Variable 'nantoka' was never mutated; consider changing to 'let' constant

これは非常にいいワーニングですね。varだけど一度しか代入されていないものはletじゃねえの?っていういいおせっかいです。Fix-itがあるのでクリックしちゃいましょう。たぶん賢いSwiftコンパイラのことなのでletだろうがvarだろうが変化するかしないかをきちんと解析して最適化をかけてくれると思うので、仕上がりのバイナリにそれほど違いは出ないと思うのですが、letにしておけばSwiftコンパイラは安心して定数としての最適化をかけることができます。

それにもましてconstを増やせば増やすほどコードは頑丈になります。letしましょう。

Forced cast of '[UIWindow]' to same type has no effect

let windows = UIApplication.sharedApplication().windows as! [UIWindow]

こういうの、返り値の方がちゃんと直っているみたいです。昔はNSなんとかが返っていたんでしょう。素直にFix-itで消しちゃいましょう。

今気づいたんですが、左っ側のワーニングとエラーの一覧のペインのエントリをクリックするとその場所にジャンプするだけじゃなくてFix-itが使えるときはFix-itの内容を表示してエンターするだけで治るようになってますね。たくさん修正するときにクリックエンターの繰り返しで簡単にできるようになっていてとてもよいです。一気に直すみたいなのもあるといいなと思いましたが、一個一個一応見ようぜというAppleの心遣いなんでしょうか。

f:id:euphonictechnologies:20160605143418p:plain

Treating a forced downcast to '[String: AnyObject]' as optional will never produce 'nil'

let titleDict: NSDictionary = [NSForegroundColorAttributeName: colorPalette.uiColorText]
UINavigationBar.appearance().titleTextAttributes = titleDict as! [String : AnyObject]

これ実は前回のエントリでas!に直したものだと思います。これ、NSDictionaryを普通の辞書に直しているからおかしなことになっているので、NSDictionaryを普通の辞書に直します。

let titleDict: [String : AnyObject] = [NSForegroundColorAttributeName: colorPalette.uiColorText]
UINavigationBar.appearance().titleTextAttributes = titleDict

こうですね。変なボクシングとアンボクシングが必要になりました。Swit2.2たしかに前よりいいね。

Use of string literal for Objective-C selector is deprecated; use '#selector' instead

SegmentTableCell(tableView: self.tableView, id: "blackPlayerSegment", labelText: "Black player", segmentItems: ["Human", "Computer"], selectedSegmentIndex: blackSSI, targetObject: self, targetSelector: "changeSegmentBlackPlayer:"),

こういうやつです。ここでtargetSelector: "changeSegmentBlackPlayer:"がだめらしい。この"changeSegmentBlackPlayer:"Objective-Cのメッセージパッシング原理主義的オブジェクト指向では許されていたやつですね。当然コンパイル時に全くチェックができないのでここをコンパイラがチェックできる形式にする…ということかな? ここで不正なセレクタを指定すると

f:id:euphonictechnologies:20160605144302p:plain

となります。だめみたいですね。

'++' is deprecated; it will be removed in Swift 3

インクリメント演算子はなくなると。残念です。a += 1みたいに書けということらしいです。なんの利点があるんでしょうか。とはいえ私はインクリメント演算子はあんまり好きじゃないです。というのもa += 1と書いたほうが代入文だということがわかりやすいからです。そりゃそうだろ、と言われるかもしれませんが、そりゃそうです。「インクリメント演算子の便利さはfor文とか関数の引数としてとかあんだろ」と言われるかもしれません。例えばCで例を出すと

/* C */
q = f(i++);

みたいな感じで一行にまとめられます。便利ですね。でも

/* C */
q = f(i++) + g(++i);

ってどうなんでしょう。これはおんなじSequence point内でiに対する変更と読み取りが両方発生するのでコンパイラワーニングになります。でもってその結果はコンパイラの作者次第です。てことはおんなじ行内でこういうことできないんだから明示的にした方がいいよねってなるとa += 1として独立した行に書くのがいいのかもしれません。当然(a+=1)として置き換えてその場でインクリメントしてそのまま使うこともできますが、流石にそんな気持ち悪いのは書かねえだろってこと・・・でしょうか。

/* C */
q = f(i) + g(i+=1);
i+=1;

やっぱちょっときもいですもんね。

さらに、Swiftは演算子オーバーロードがあるので

var q = f(i++) + g(++j)

これは大丈夫でしょうか。このコードだけではわかりません。やっぱりSequence pointを大事にする姿勢からするとインクリメント演算子はとりあえずなくしてきれいに書く癖を強制させる方向性なのかな、ということをインクリメント演算子の将来的な削除から考えました。結論:どっちでもいい!

メイヤー先生はいらないと考えているみたいですね。

オブジェクト指向入門 第2版 原則・コンセプト (IT Architect’Archive クラシックモダン・コンピューティング)

オブジェクト指向入門 第2版 原則・コンセプト (IT Architect’Archive クラシックモダン・コンピューティング)

C style for statement is deprecated and will be removed in a future version of Swift

for var by : CGFloat = 0; by <= width; by += piece_width {
...

って感じのやつです。Pythonみたいに書くのがいいというわけですね。つまり

for i in 0..<5 {
}

みたいな書き方ですね。ただこれ、増分1固定なので僕のオリジナルの文は書き直せません。ここでstrideを使います。

for i in stride(from: 0, through: width: by: piece_width) {
}

とすると上と同じになります。

stride(from: 0, to: 1, by: 0.2)            // 0.0, 0.2, 0.4, 0.6, 0.8
stride(from: 0, through: 1, by: 0.2)  // 0.0, 0.2, 0.4, 0.6, 0.8, 1.0

という違いがあります。ここにはStrideableなる新しい型の作用があるみたいですね。参考:

Swift: Six Killer Features — Erica Sadun

Strideable Protocol Reference

swift-evolution/0007-remove-c-style-for-loops.md at master · apple/swift-evolution · GitHub

Immutable value 'nantoka' was never used; consider replacing with '_' or removing it

これは使われてない変数の取り扱いに関する警告ですね。消せるところは消しちゃいましょう。forの条件に使われていたりする場合は_に置き換えちゃいましょう。

        for _ in 0..<height {
            var row: [Double] = []
            for _ in 0..<width {
                row += [initVal]
            }
            self.zones += [row]
        }

ちなみにこうやっても上と下の_は混じりませんよ。安心してください。

'var' parameters are deprecated and will be removed in Swift 3

func sum (var array : [Int]) {

これ、変数は基本constで、変更する場合はvarをつけなければいけませんでした。これはそのうちinoutに置き換わる予定です。こうやってimmutablityを重視するのって本当にいいですね。

Result of call to non-mutating function 'sort' is unused; use 'sortInPlace' to mutate in-place

これはワーニングの中でも特に重要に思います。以前はsort関数はsequenceの中身を直接変更するものでしたが、これからはそのsortしたものを返す関数になっているようです。

        arr.sort({
            $0.0 > $1.0
        })

とかやると何にもしない文になります。sortInPlaceしましょう、というよりarr = art.sort~と書き直したほうが良いように思います。RValue optimizationがかかる…のかな?そうだといいな。

プロジェクトの設定のワーニング

こんな感じのものが出ました。

f:id:euphonictechnologies:20160605153758p:plain

面倒なんでPerform Changesしちゃいましょう。

一応調べてみると

  • Turn on "Enable Testability" When Debugging

この"Enable Testability"はテストクラスの冒頭で

@testable import ClassToBeTested

するだけで大丈夫になるみたいです。便利ですね。

  • Disable Safety

これは-Ouncheckedフラグの代わりみたいです。私のような完璧無敵超人に配列の境界チェックは必要ないのでuncheckedにしているのですが、Disable Safetyで置き換えみたいです。

綺麗になりました

ワーニングは全部修正できたみたいです。というわけで、次はSwift1.2と2.2で私の書いたオセロのプログラムを使ってスピードの比較でも暇な時にやってみたいと思います。

参考文献

Open Source Swift Under the Hood

Swift 1.2から2.2でウラシマ状態 - ビルドできるように修正する

iPhone Swift

久しぶりにXCodeを起動しました。

昔のプロジェクトをインポートしたところ"最新のswiftに自動で変換しますか?"と余計なお世話をぶちかましてきたのでスルーしてビルドしたところビルドエラーの嵐。後方互換性とか関係ねえからっていうAppleの教えが心に響きます。新しい機能は拡張で導入するHaskellが懐かしいです。

というわけで自分のために直した箇所をメモしていこうと思います。確か前回のブログを読むと使っていたコンパイラは1.2なので1.2->2.2です。

$ swift --version
Apple Swift version 2.2 (swiftlang-703.0.18.8 clang-703.0.31)

一応確認してみました。

違いたち

  • touchesBegan

修正前

override func touchesBegan(touches: Set<NSObject>, withEvent event: UIEvent)

修正後

override func touchesBegan(touches: Set<UITouch>, withEvent event: UIEvent?)

お前overrideつってるけどoverrideしてねえぜと言われて調べてみたらこの有様です。

  • 関数宣言だけかなんかしんねーけどすべての変数に名前をつけろよこのデコスケ野郎

Unnamed parameters must be written with the empty name '_'

馬鹿じゃねーのか。明らかにredundantなんですけど、大丈夫なんですかね。とりあえず言われたとおり_:をつけて名前の無い変数ですという宣言をします。他言語ブリッジに対する嫌がらせですかね。

  • Unknown attribute 'asmname'

名前が変わって@_silgen_nameになったようです。xcode - How to use @asmname() in Swift 3.0 - Stack Overflowの回答者の人がその変更が行われたコミットとチェンジログにもリンクを貼ってくれています。とても偉い。

  • 'reduce' is unavailable: call the 'reduce()' method on the sequence

普通の人間であれば畳み込みは

reduce [1, 2, 3, 4, 5] 0 add

と書くところですが、この頭の狂った言語では

[1, 2, 3, 4, 5].reduce(0, add)

と書くらしい。頭大丈夫?関数がファーストクラスオブジェクトって言いたいだけなのはわかった。2016年になっても関数型言語の普及ははるか遠い。部分適用するときに

[1, 2, 3, 4, 5].reduce()

って書くのかな?と思ったのですが、Swiftには部分適用はクロージャ作って自分でカリー化しないかぎりなさそうなので別にどうでも良さそうでした。頭に血が上ってすみません。Swiftは手続き型言語なのを忘れていたのです。この書き方だとメソッド呼び出しをチェーンするときに便利ですね。

  • Missing argument label 'combine' in call

さて、上の例はまだ不完全です。なぜならば

[1, 2, 3, 4, 5].reduce(0,combine: add)

ふたつ目の引数には必ずラベルを付けて呼ぶ決まりです。これは特に文句をつけることもないかな、と思います。OCamlとかでもJane Street Coreとか使っていてラベル付き引数関数を多用していると手が自然につけていたりします。多分CとかJavaから来た人はびっくりするんじゃないでしょうか。ただラベルつけるかつけないか選べないのは鬱陶しくて

some2dMatrix.getElement(x, y: y)

と変なy:がつきます。これは少し鬱陶しい。タプルでやれってことだと思います。 とまれ、結局Objective-C臭さを消せなかったSwiftです。OCamlなんとかっていうのは

String.sub "Hello" ~pos:0 ~len:4

こういうのですね。にょろかわいい。

  • supportedInterfaceOrientations() -> Intはもうないよ

ガイシュツだと思いますが

supportedInterfaceOrientations() -> UIInterfaceOrientationMask

になりました。なので昔無理やり

Int(UIInterfaceOrientationMask.AllButUpsideDown.rawValue)

してたキャストは外して.rawValueのプロパティで返さなくても大丈夫です。オブジェクトの返し方の最適化でも入ったんでしょうか。

  • NSData(contentsOfFile: path, options: .DataReadingMappedIfSafe, error: nil)

これは

Argument labels '(contentsOfFile:, options:, error:)' do not match any available overrides

というエラーになります。簡単に言うとerror:がなくなったのでこれを外せばよいのですが、これはSwift1->2でエラーハンドリングが充実したことによって変わった模様です。

www.hackingwithswift.com

というわけで、きちんとハンドルするようにしてみます。しかし足りない頭で私見を言えばこの場合nilを返せばいいわけで、なんでtry-catchが必要なんでしょうか。それがOptionalのいいところだったはずなのですが。多分エラーの種類によって処理を変えたいということなんだと思いますが型による解決を図るならばEither型とかある…といっても多分Swiftプログラマ混乱しちゃうだろうし無理だろうな。Optionalが特別な型なおかげでこういう自由な拡張ができなくなってしまったのは少し残念です。普通にtryキャッチしましょう。まずerror:を外します。

var sceneData = NSData(contentsOfFile: path, options: .DataReadingMappedIfSafe)

とすると

Call can throw, but it is not marked with 'try' and the error is not handled

と出ます。すぐにエラー処理をせよと。遅延させるなと。

guard let sceneData = try? NSData(contentsOfFile: path, options: .DataReadingMappedIfSafe) else {
    return nil
}

こういう書き方でいいんでしょうか。これは新しいguard句です。メイヤー先生もニッコリですね。もちろん私もこういう表明的プログラミングは好きです。ここでguard ~ elseと出てきています。これはassertです。elseでassert失敗した時の処理を書きます。ifで等価なステートメントがかけますね。つまり

if let sceneData = try? ~ {
    // do nothing
} else {
    return nil
}

ってことですね。参考:swift - try, try! & try? what’s the difference, and when to use each? - Stack Overflow

marked with 'try'

と言うのは参考リンクにあるtry!try?の表明をせよということです。try!は「ダメだったら死んじゃお!」でtry?「ダメだったら見なかったことにしちゃお!」ってことです。try?の場合nilが帰るのでOptionalの話に戻れます。そこをguardとかif letとかで処理を分けるわけです。ちう事で、try?は上で文句言った「Optional型もっと使えよ!」に対する答えになっています。文句言ってすみません。死にたくもシカトも嫌な場合は

do {
    // codes can throw
} catch {
    // error handling
}

と普通にtry-catchもできます。

  • StringはSequenceじゃないよ

Type String does not conform to protocol 'SequenceType'

となりましたので、

for c in fromText.characters {
...

としましょう。The Swift Programming Language (Swift 2.2): Strings and Characters のWorking with charactersにも書かれています。

  • 'NSDictionary' is not implicitly convertible to '[NSObject : AnyObject]'; did you mean to use 'as' to explicitly convert?
UINavigationBar.appearance().titleTextAttributes = titleDict as [NSObject : AnyObject]

というステートメントにエラーが出ました。この場合素直にas [NSObject : AnyObject]を消して自動で教えてくれる修正をしましょう。この場合

UINavigationBar.appearance().titleTextAttributes = titleDict as! [String : AnyObject]

という修正になりました。型推論便利ですね。確かに1.2の頃よりも型推論機が強力になっているような気がしています。

  • Downcast from 'UITableViewCell?' to 'UITableViewCell' only unwraps optionals; did you mean to use '!'?

まず混乱したのはビックリマークなのかハテナなのか解んなくなっちゃうところです、末尾が。

なんか

return tableView.dequeueReusableCellWithIdentifier(reusableCellId) as! UITableViewCell

としていたところが変なダウンキャストなしでも大丈夫になったみたいです。素直にunwrapだけに変えましょう。

return tableView.dequeueReusableCellWithIdentifier(reusableCellId)!

これも指摘されている部分を素直に削除すると修正方法を教えてくれます。素直に従っちゃいましょう。もしくは先に上げたナイスなエラーハンドリングを書きましょう。

全部赤いやつ修正できた!

これらが私のコードにあったエラーでした。すべて修正してビルド完成です。つぎは黄色いワーニングを修正していきます。

github.com

Swift Pocket Reference: Programming for Ios and OS X: Covers Swift 2.1

Swift Pocket Reference: Programming for Ios and OS X: Covers Swift 2.1