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

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

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回答で一応予選通ったんで（多分、一番簡単な通り方でしょう）次も一応参加はしてみます。