標準エラーへの出力（Swift）

特にAHCでバグってしまった場合など、競プロに参加していると、標準エラーに文字列を出力したくなる場合があります。 以下のエクステンションを使うことで、print関数のto:パラメータに直接stderrを渡せるようになります。

extension UnsafeMutablePointer: TextOutputStream where Pointee == FILE {
    public mutating func write(_ string: String) {
        guard let data = string.data(using: .utf8) else { return }
        _ = data.withUnsafeBytes { bytes in
#if os(Linux)
            Glibc.write(fileno(self), bytes.baseAddress!, data.count)
#else
            Darwin.write(fileno(self), bytes.baseAddress!, data.count)
#endif
        }
    }
}

使い方は以下のように。

print("Hello, STDERR!", 1, 2, 3, 4, to: &stderr)

既出の内容ですが、print関数の自由度を損ないたくなかったので、stderrに生やしてみました。 どうぞご自由に。

茶色になりました。

AtCoderで茶色になりました。使用言語は主にSwiftです。
ABC324から、ABC332までの、約2ヶ月ほどでの入茶でした。

きっかけは同僚の「すぐ緑になれそう」という一言です。
その後、どちらが少ない出場回数で緑になれるか競争しています。

ここでは、課題に感じたことと、課題への取り組みについて書きたいと思います。

まず、デビュー戦では、暗黙のコピーが発生した際のパフォーマンス低下に苦しみました。特に文字列です。
文字に関してもSwiftがリッチなことで、C++と比べてパフォーマンスが低く、これをどう回避するかに取り組みました。

方針として、文字を触る必要がある場合にはutf8CStringメソッドで変換し、CCharを使うことにしました。

次に作業性の悪さの問題がありました。いろいろ探してみたのですが、自分にはしっくりこなかったので、ojtとSwift Packageを、シェルスクリプトとMakefileを用いて、テストやデバッグや送信ができるように整えました。

その後、upsolveでのライブラリの不足に直面します。ついかっとなって、AcLibraryを勝手に移植しました。以下です。
https://github.com/narumij/swift-ac-library

すでに移植されたものはGithubにみつかったのですが、テストコードがしっかり通っているモノがどうしても欲しかったので、新たに移植する選択をしました。

移植できたライブラリいくつか試したところ、どうしてもTLEしてしまう問題に遭遇しました。

いろいろ試した結果、入力処理だけで制限時間の8割ほどに達していることがわかり、getchar_unlockedを用いた入力ライブラリを作成し、セオリーのreadLineを卒業しました。出力にputchar_unlockedを用いることで、処理時間を稼げる場合もありますが、文字列をutf8CStringにするコストが悪い方に効いて性能悪化する場合もあるので、こちらは採用しませんでした。

他に、平衡二分探索木も勝手に移植していますが、こちらは実験レベルにとどまっています。

関連書籍として、鉄則本を最初の一冊目に選び、今のところこの一冊だけで取り組んでいます。次はけんちょん本を買い足したいです。

1ヶ月半がすぎ、ある程度コンテストに対して慣れたわりにレートが伸び悩んでいて、
問題文を理解したがらない自分の脳みそを課題と感じ、A問題10問を毎日解く取り組みを三日ほどしました。

さらに、レベルアップを望んで、D問題への取り組み始めました。

そんな矢先の、入茶でした。

もともとPaizaでAをとっていたので、茶色になれると踏んではいたのですが、実際に到達できて一安心です。
Swift固有の問題にまだまだ遭遇したり、苦しんだりしそうですが、ゴールは緑、夢は水色で、この先も精進します。

 

SSとかは省略します。あしからずご了承ください。

UnitTestで標準入力の差し替え

過去問やってると、（Command+Uが染みついてて）UnitTestつかいたくなるし、かといって入力をいちいち手作業でリテラルにするのはおっくうで。

そこで！

struct AtCoderRunner {
    typealias Print = (String) -> Void
    typealias Solver = (Print) -> Void
    let solver: Solver
    func run(input: String) -> String {
        var output: [String] = []
        var buffer: [Int8] = input.utf8CString + [0]
        let count = buffer.count
        buffer.withUnsafeMutableBytes {
            let file = fmemopen($0.baseAddress, count, "r")
            assert(file != nil)
            let backup = stdin
            stdin = file!
            solver() { output.append($0) }
            stdin = backup
        }
        return output.joined(separator: "\n")
    }
}

例えばこんな解答関数があったとすると

func TemplateSolver(print: (String) -> Void) {
    let N = Int(Swift.readLine()!)!
    print("\(N)")
}

こんな風にテストできます。

final class AtCoderTemplateTests: XCTestCase {
    var stdinCopy: UnsafeMutablePointer<FILE>?
    override func setUpWithError() throws {
        // 念のため
        stdinCopy = stdin
        // でもテストが並列で動くとおじゃん
    }
    override func tearDownWithError() throws {
        // 念のため
        stdin = stdinCopy!
        // でもテストが並列で動くとおじゃん
    }

    // Greenだよー
    func testTemplate() throws {
        XCTAssertEqual(
            AtCoderRunner(solver: TemplateSolver)
                .run(input:
                     """
                     0
                     """),
                     """
                     0
                     """)
    }
}

提出するときは、雑に説明するとこんな感じです。

TemplateSolver {
    print($0)
}

どうぞご自由におつかいください。

（いまさらですが、過去記事も同様です）

あ、Swiftです。

lowerBound

★3の過去問やった際に書いた、SwiftのlowerBoundを今後も使いそうなのでメモ

extension RandomAccessCollection where Element: Comparable {
    
    func lowerBound(of element: Element) -> Index {
        guard first! < element else { return startIndex }
        var (left, right) = (startIndex, endIndex)
        while left < right {
            let mid = index(left, offsetBy: distance(from: left, to: right) / 2)
            if self[mid] < element {
                left = mid
            } else {
                right = mid
            }
        }
        return left == endIndex ? index(endIndex, offsetBy: -1) : left
    }
}

Implementing Graham Scan in Swift

'ConvexHull' 'Swift'でぐぐってみたら、なんだか物足りなかったので、なんとなく。

import simd

public struct Graham
{
    var target: [SIMD2<Float>] = []
        
    public func scan() -> [SIMD2<Float>] {
        guard let lowestPoint = target.most(in: lower)
            else { return [] }
        return scanLeftTurn(startPoint: lowestPoint,
                            angleOrder: target
                                .filter({ $0 != lowestPoint })
                                .sorted{ lowBiasedAngle(with: lowestPoint)($0,$1) })
    }
    
    func scanLeftTurn(startPoint head: SIMD2<Float>, angleOrder tail: [SIMD2<Float>]) -> [SIMD2<Float>]
    {
        var stack: [SIMD2<Float>] = []
        stack.push(head); stack.push(tail[0])
        for vertex in tail[1..<tail.count] {
            while ( !left( stack.top(1) , stack.top(0), vertex ) ) {
                _ = stack.pop()
            }
            stack.push(vertex)
        }
        return stack
    }

}

func lowBiasedAngle(with h: SIMD2<Float>) -> (_ pi: SIMD2<Float>,_ pj: SIMD2<Float>) -> Bool
{
    { (pi, pj) in areaSign( h, pi, pj ) != .negative }
}

func left(_ a: SIMD2<Float>,_ b: SIMD2<Float>,_ c: SIMD2<Float> ) -> Bool
{
    areaSign( a, b, c ) == .positive
}

func lower<Scalar: Comparable>(_ lhs: SIMD2<Scalar>, _ rhs: SIMD2<Scalar> ) -> Bool {
    lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x > rhs.x)
}

enum Compare {
    case negative
    case even
    case positive
}

func areaSign(_ a: SIMD2<Float>,_ b: SIMD2<Float>,_ c: SIMD2<Float>) -> Compare
{
    let area2 = cross(b - a, c - a).z
    if abs(area2) < .ulpOfOne { return .even }
    else if area2 >  0        { return .positive }
    return .negative
}

extension Array {
    func most(in condition: (Element, Element) -> Bool) -> Element? {
        reduce(nil) { lhs, rhs in
            guard let lhs = lhs
                else { return rhs }
            return condition(lhs, rhs) ? lhs : rhs
        }
    }
}

extension Array {
    mutating func push(_ element: Element) {
        append(element)
    }
    mutating func pop() -> Element {
        removeLast()
    }
    func top(_ i: Int) -> Element {
        self[count - 1 - i]
    }
}


Reference

O'Rourke,J. (1998). Computational Geometry in C, 2nd edn, Cambridge: Cambridge University Press.

Auto-Increment Build Number in Xcode 13

久しぶりにビルドナンバーの自動更新などしようかと思っていたら、Xcode13でInfo.plistがなくなっており、以前から使っていたやり方が使えなくなっていました。ぐぐっても直接的な解答がみつからなかったので、メモ。要点は、agvtoolコマンドを使うということでした。

対処としては、Build PhaseにRun Scriptを追加し、以下のスクリプトを設定しました。

NEW_VERSION=$(git rev-list HEAD | wc -l | tr -d ' ')
agvtool new-version ${NEW_VERSION}

gitのコミット数で更新するようになっています。


16進数が好みなので、実際は以下にしています。

NEW_VERSION=$(git rev-list HEAD | wc -l | tr -d ' ' | xargs -n1 printf '%X')
if [ $(git diff HEAD --stat | wc -l | tr -d ' ') -ne 0 ]; then
NEW_VERSION=$(expr ${NEW_VERSION} + 1)
fi
agvtool new-version ${NEW_VERSION}