エンジニアリングにはほど遠い

iPhoneアプリとかサイトとかをつくっていくブログです。

Google Code Jam 2017 予選参加してみました

この記事は攻略記事ではなくただの思い出メモです。

せっかくなので去年同様Clojureでやってみました。

Clojureでの処理

Clojureをコマンドライン実行するためには

lein exec hoge.clj

標準入力読み込みは

(read-line)

問題を解くときは以下な感じ

実行

lein exec hoge.clj < q.txt > a.txt

読み込み部

(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

A問題

問題の理解

  • 上下の概念があるパンケーキが並んでいて、一操作は与えられた数(K)を一度にひっくり返す行為。全部表にするための操作数
  • 全部表にできない場合はIMPOSSIBLE

方針

  • 左から見ていって裏があった場合はひっくり返す操作をする
  • 操作をしていって、残り枚数がKの時に全部+ならそれまでの操作数、全部-なら操作数+1、それ以外は全部表にするのは不可能
  • 力技だけど解けた

ソース

(defn- inverse [s]
  (-> s
      (clojure.string/replace #"-" "_")
      (clojure.string/replace #"\+" "-")
      (clojure.string/replace #"_" "+")))

(defn- iter [s k ans]
  (if (= (count s) k)
    (cond
      (= (count (re-seq #"-" s)) 0) ans
      (= (count (re-seq #"\+" s)) 0) (inc ans)
      :else       nil)
    (if (= (first s) \+)
      (recur (subs s 1) k ans)
      (recur (str (inverse (subs s 0 k)) (subs s k)) k (inc ans)))))

(defn- work [s k]
  (if (= (count (re-seq #"-" s)) 0)
   0
   (iter s (read-string k) 0)))

(defn- solve [line]
  (or (apply work (clojure.string/split line #" ")) "IMPOSSIBLE"))

(read-line)

(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

B問題

問題の理解

  • 与えられた数値までの数で数字が昇順になるような数の最大を求める

方針

  • 与えられた数に関して、グループ分けをする。(1113325なら111,33,2,5)グループを2個ずつ見ていって、左のグループの数が大きい場合はそのグループの左端の桁の数を1減らし、残りの右全部の各桁を9にする。
  • partition-byが使えそう
  • 左端が0になった場合は取り除く

ソース

(defn- ninize [list-]
  (take (count list-) (repeat 9)))

(defn- numberize [list-]
  (map #(read-string (str %)) list-))

(defn- asc-list [num-str]
  (defn- iter [[f s & r] result]
    (cond (nil? f) (flatten result)
          (nil? s) (flatten (conj result f))
          :else
          (if (< (first f) (first s))
            (recur (conj r s) (conj result f))
            (flatten (conj result
                           (dec (first f))
                           (ninize (drop 1 f))
                           (map ninize (conj r s)))))))
  (iter (->> num-str
             seq
             (partition-by identity)
             (map numberize)) []))

(defn remove-head-zero [list-]
  (if (= (first list-) 0)
    (drop 1 list-)
    list-))

(defn- solve [line]
  (->> line
       asc-list
       remove-head-zero
       (apply str)))

(read-line)

(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

C問題

問題の理解

  • N個並んでいるシャワー部屋があり、来た人は必ず隣との距離が最大になるように入る
  • N個に対してk番目の人が入る場合の部屋の隣との距離の最大と最小を求める

方針

  • k>1の場合、一人目に半分に分けられた部屋に対してkを半分にして考えることができる(NをA,B(B>=A)に分けたとして、k2はB,k3はA,k4はBに絶対入る)
  • これを整理すると、
    • Nが偶数かつkが奇数： N.k = (N/2 - 1).(k/2)
    • それ以外： N.k = (N/2).(k/2)

ソース

(defn- max-min [n k]
  (if (= k 1)
    (list (long (/ n 2)) (- (long (/ n 2)) (if (even? n) 1 0)))
    (recur (- (long (/ n 2)) (if (and (even? n) (odd? k)) 1 0)) (long (/ k 2)))))

(defn- solve [line]
  (clojure.string/join
    " "
    (apply max-min (map read-string (clojure.string/split line #" ")))))

(read-line)

(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

D問題

リタイア。

まとめ

Cは去年より優しかったようで、今年は解けました。 一応予選通ったんで１回戦突破目標でがんばります。

ActiveRecordで複数カラムに対し複数キーワードで探す

Rails Ruby

割と汎用的かと思ったので載せてみようかと。
orの引数にnilがきたらそのままなのがミソ。

class ActiveRecord::Base         
  def self.search_with_multi(columns:, keywords:)
    where(columns_keywords_cond(columns, keywords))
  end
            
  def self.columns_keywords_cond(columns, keywords)
    columns
    .product(keywords)  
    .reduce(nil) do |cond, (column, keyword)|
      arel_table[column].matches("%#{keyword}%").or cond
    end
  end
end


Book.search_with_multi(columns: [:title, :description], keywords: ["夏", "休み"])

追記

これだと%と_の文字が埋もれてしまうのと、nilが条件を汚染していたので、以下に修正。 sanitize_sql_likeはRails4.2からは標準で入ってるメソッドとのこと。

class ActiveRecord::Base         
  def self.search_with_multi(columns:, keywords:)
    where(columns_keywords_cond(columns, keywords))
  end

  def self.columns_keywords_cond(columns, keywords)
    columns
    .product(keywords)
    .map { |column, keyword| arel_table[column].matches("%#{sanitize_sql_like(keyword)}%") }
    .reduce(&:or)
  end

  def self.sanitize_sql_like(string, escape_character = "\\")
    pattern = Regexp.union(escape_character, "%", "_")
    string.gsub(pattern) { |x| [escape_character, x].join }
  end
end

Google Code Jam 2016 予選参加してみました

この記事は攻略記事ではなくただの思い出メモです。

せっかくなのでClojureでやってみました。

Clojureでの処理

Clojureをコマンドライン実行するためには

lein exec hoge.clj

標準入力読み込みは

(read-line)

問題を解くときは以下な感じ

実行

lein exec hoge.clj < q.txt > a.txt

読み込み部

(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

A問題

問題の理解

  • とある数値NをN x 2, N x 3, N x 4, ... としていって、0~9までの数字がすべて登場したときの最後の結果の数
  • 何倍しても数字がすべて登場できない場合はINSOMNIA

方針

  • setに入れていけばいいんじゃないかということでやったら普通に解けました。

ソース

(defn- iter
  [n digits idx]
  (let [n-i (str (* (read-string n) idx))
        result-digits (set (concat digits (set n-i)))]
    (if (= (count result-digits) 10)
      n-i
      (recur n result-digits (inc idx)))))

(defn- solve [n]
  (if (= n "0")
    "INSOMNIA"
    (iter n #{} 1)))

(read-line) ; 最初の１行捨てている
(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

B問題

問題の理解

  • 上下の概念があるパンケーキが積み上がっていて、それを全部表にするための操作数
  • パンケーキの操作は天辺からどこかの地点までを決めて、全部をひっくり返す

方針

  • 天辺からしかひっくり返せないので、結局表と裏が切り替わっている部分の数だけ操作をしなければいけない
  • 最後の一枚が裏だった場合、最終的に全部を表にしなきゃいけないのでもう一回操作が増える

ソース

(defn- gap-count [n]
  (+ (count (re-seq #"\+-" n))
     (count (re-seq #"-\+" n))))

(defn- last-step-count [n]
  (if (= (last n) \+) 0 1))

(defn- solve [n]
  (+ (gap-count n) (last-step-count n)))

(read-line)
(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

C問題

問題の理解

  • 1....1 の01で構成された数において、基数を2~10にしたときに計算されるそれぞれの数が全部素数でないもの
  • その時の各基数の数の割れた数（？）も出す必要がある（？）

方針

  • 素数の計算がキツそうなんでエラトステネスの篩というものを使ってみる

結果

  • 全然計算が終わらなくて無理。
  • 解法として、1...1の偶数番目と奇数番目の1の数が同じものは(基数+1)で割り切れるというのがあるらしい

ソース

解けなかったけど一応単純にやるやつのソースを

(require '[clojure.string :as string])

(def finish-count
  (atom nil))

(def got-count
  (atom 0))

(defn- era [limit primes idx]
  (if (or (> idx limit) (= (count primes) 0))
    (first primes)
    (recur limit (remove #(= (rem % idx) 0) primes) (inc idx))))

(defn- divided-num [target]
  (if (< target 2)
    nil
    (era (Math/sqrt target) (range 3 target) 2)))

(defn- bit-sum [base string]
  (reduce +
          (map-indexed (fn [idx value] (Math/pow (if (= value \1) base 0) idx))
                       (reverse (seq string)))))

(defn- bit-string [strings j]
  (if (>= (->> strings first count) j)
    strings
    (recur (mapcat #(list (str % "0") (str % "1")) strings) j)))

(defn- trimmed-str [string]
  (subs string 1 (dec (count string))))

(defn- iter [string]
  (when-not (= @finish-count @got-count)
    (loop [bases (range 2 11) divided-nums []]
      (if (empty? bases)
        (do
          (swap! got-count inc)
          (println string (trimmed-str (str (vec divided-nums)))))
        (let [divided-num_ (divided-num (bit-sum (first bases) string))]
          (if-not (nil? divided-num_)
            (recur (rest bases) (conj divided-nums divided-num_))))))))

(defn- solve [goal-count]
  (loop [bit-strs (map #(str "1" % "1") (bit-string ["0" "1"] (- goal-count 2)))]
    (when-not (= @finish-count @got-count)
      (when-not (empty? bit-strs)
        (iter (first bit-strs))
        (recur (rest bit-strs))))))

(read-line)
(println "Case #1:")
(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (let [args (string/split input #" ")]
      (reset! finish-count (read-string (last args)))
      (solve (read-string (first args)))
      (recur (read-line) (inc idx)))))

追記：解き直したので追加

  • 100ほど試し割りをしてみてダメならその数は諦める
  • 32桁は16桁の物をくっつけた物の倍数 -> 数を抑えて計算可能

ソース

(require '[clojure.string :as string])

(def finish-count
  (atom nil))

(def got-count
  (atom 0))

(defn- divisor [target]
  (defn- iter [target divisor]
    (cond
      (rem target divisor) divisor
      (< divisor 100)      (recur target (inc divisor))
      :else                nil))
  (if (< target 2)
    nil
    (iter target 2)))

(defn- digits [limit]
  (defn- iter-digits [strings limit]
    (if (>= (->> strings first count) limit)
      strings
      (recur (mapcat #(list (str % "0") (str % "1")) strings) limit)))
  (iter-digits [""] limit))

(defn- arranged [digits] (map #(str "1" % "1") digits))

(defn- trimmed-str [string]
  (subs string 1 (dec (count string))))

(defn- solve-digit [digit]
  (loop [bases (range 2 11) divided-nums []]
    (if (empty? bases)
      (do
        (swap! got-count inc)
        (println (str digit digit) (trimmed-str (str (vec divided-nums)))))
      (let [divisor (divisor (Long/parseLong digit (first bases)))]
        (if-not (nil? divisor)
          (recur (rest bases) (conj divided-nums divisor)))))))

(defn- solve [goal-count]
  (loop [digits (->> (- (/ goal-count 2) 2) digits arranged)]
    (when-not (= @finish-count @got-count)
      (solve-digit (first digits))
      (recur (rest digits)))))

(println "Case #1:")
(read-line)
(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (let [args (string/split input #" ")]
      (reset! finish-count (read-string (last args)))
      (solve (read-string (first args)))
      (recur (read-line) (inc idx)))))

Rubyでも書いてみた

class String
  def nexts
    [self + "0", self + "1"]
  end

  def digits limit
    length < limit ? nexts.flat_map { |next_| next_.digits limit } : self
  end
end

def divisor num
  (2..100).find { |divisor| num % divisor == 0 }
end

def solve digit
  divisors = (2..10).reduce([]) do |this, base|
    this << divisor(digit.to_i(base)).tap { |divisor| return unless divisor }
  end

  puts digit + digit + " " + divisors.to_s.gsub(/,|\[|\]/, "")
  @got += 1
end

puts 'Case #1:'
gets
N, J = gets.split(' ').map(&:to_i)
@got = 0

"".digits((N / 2) - 2)
.map { |digit| "1#{digit}1" }
.each do |digit|
  solve digit
  break if @got == J
end

Rubyの方が簡潔にみえる。Clojure力のある方突っ込んでいただけるとうれしいです。

追記

遅延評価してるので途中で止めなくてもいいじゃん、と思い直して書き直した。

(require '[clojure.string :as string])

(defn- divisor [target]
  (->>
    (range 2 100)
    (filter #(= 0 (rem target %)))
    first))

(defn- divisors [digit]
  (->>
    (range 2 11)
    (map #(Long/parseLong digit %))
    (map divisor)))

(defn- digits [limit]
  (loop [strings [""] limit limit]
    (if (->> strings first count (<= limit))
      strings
      (recur (mapcat #(list (str % "0") (str % "1")) strings) limit))))

(defn- result-lines [n]
  (->>
    (digits (- (/ n 2) 2))
    (map #(str "1" % "1"))
    (map #(if (not-any? nil? (divisors %)) (str % % " " (-> (divisors %) vec str (string/replace #"[\[\]]" ""))) nil))
    (remove nil?)))

(defn- solve [n j]
  (doseq [result-line (take j (result-lines n))]
    (println result-line)))

(println "Case #1:")
(read-line)
(loop [input (read-line) idx 1]
  (when-not (nil? input)
      (apply solve (map read-string (string/split input #" ")))
      (recur (read-line) (inc idx))))

前のよりは大分いい感じ。

D問題

よく分からず終了。

まとめ

問題文がよく分からない。 AB回答で一応予選通ったんで（多分、一番簡単な通り方でしょう）次も一応参加はしてみます。

Swift2の正規表現マッチの簡易メソッド

Swiftの正規表現処理はObjective-C同様にとても面倒なので、色々な方が使いやすいように改良していますが、 自分もやってみました。（正規表現のパターンが不正な時はクラッシュします）

extension String {
    private func checkingResults(pattern:String) -> [NSTextCheckingResult] {
        return try! NSRegularExpression(pattern:pattern,options:NSRegularExpressionOptions())
        .matchesInString(self,
            options: NSMatchingOptions(),
            range: NSMakeRange(0, self.characters.count))
    }

    private func convertToStrings(result: NSTextCheckingResult) -> [String] {
        return Array(0..<result.numberOfRanges).map { index in
            (self as NSString).substringWithRange(result.rangeAtIndex(index))
        }
    }

    func match(pattern: String) -> [String]? {
        if let result = checkingResults(pattern).first {
            return convertToStrings(result)
        } else {
            return nil
        }
    }

    func matches(pattern: String) -> [[String]] {
        return checkingResults(pattern).map { result in convertToStrings(result) }
    }
}

matchのところとか、ぱっと見冗長に見えますね〜。こういうもんなんでしょうか。

結果

print("http://example.com".match("https?://(.*)"))
// Optional(["http://example.com", "example.com"]) 最初は全体、それ以降は各グループ
    
print("https://example.com".match("https?://(.*)"))
// Optional(["https://example.com", "example.com"])
    
print("a ab abc abcd".match("(.*?)\\s"))
// Optional(["a ", "a"]) 
    
print("a ab abc abcd".matches("(.*?)\\s"))
// [["a ", "a"], ["ab ", "ab"], ["abc ", "abc"]]

なんでこれが欲しかったのかというと、前回作った辞書機能の結果から品詞部分を抜き出したかったため。 definitionから以下の文字列が得られるので正規表現で抜き出す方針。
English |ˈɪŋglɪʃ| ▶adjective relating to England or its people or language. ▶noun 1 [ mass noun ] the language of England, now widely used in many varieties throughout the world. 2 (as plural noun the English) the people of England. 3 ...

func definition(word: String) -> String? {
    if let definition = DCSCopyTextDefinition(nil, word, CFRangeMake(0, word.characters.count))?
    .takeUnretainedValue() {
        return String(definition)
    } else {
        return nil
    }
}

if let definition = definition("English") {
    print(definition.matches("▶(.*?)\\s").map{ $0.last! })
    // ["adjective", "noun"]
}

これで、単語の品詞を得ることができました。

Swiftのスクリプトで辞書

Swift Mac

最近英語を勉強していて、せっかくなので英語勉強ツールを作ろうと思った。 まずそのパーツとして手始めに辞書機能をつくることに。

Macの標準の辞書アプリの機能を使ってみるのが良いかなと思いやってみました。

dict.swift

import Foundation
import CoreServices

func definition(word: String) -> CFString? {
    return DCSCopyTextDefinition(nil, word, CFRangeMake(0, word.characters.count))?
    .takeUnretainedValue()
}

func trimmed(str: String) -> String {
    return str.stringByTrimmingCharactersInSet(NSCharacterSet.whitespaceCharacterSet())
}

func main() {
    if let word = Process.arguments.dropFirst().first as String? {
        if let definition = definition(trimmed(word)) {
            print(definition)
        }
    }
}

main()

実行（Englishは検索したい文字）

swift dict.swift English

または以下でコンパイルしてファイル生成し実行

swiftc dict.swift
./dict English

または１行目に#!/usr/bin/env swiftシバンを書いておけば以下でいきなり実行できる

chmod +x dict.swift
./dict.swift English

Process.argumentsで引数一覧が取れる。とても楽。
DCSCopyTextDefinitionが辞書を使うCoreServicesのメソッド。第一引数に辞書をいれられるみたい。今回はデフォルトの辞書を使うのでnil。

次は文章を記憶していく機能を作りたい。