|
(ns rdp.214-intermediate |
|
(:require [clojure.java.io :as io])) |
|
|
|
(def BLOCKS 10) |
|
|
|
(defn- read-line-ints |
|
([] (read-line-ints (read-line))) |
|
([input-line] |
|
(if-let [line input-line] |
|
(->> line |
|
(#(clojure.string/split %1 #" ")) |
|
(map #(Integer/parseInt %1)))))) |
|
|
|
(defrecord Paper [^long color ^long x1 ^long y1 ^long w ^long h ^long x2 ^long y2]) |
|
|
|
(defn- make-paper |
|
([w h] (make-paper 0 0 0 w h)) |
|
([color x y w h] |
|
(->Paper color x y w h (dec (+ x w)) (dec (+ y h))))) |
|
|
|
(defn- parse-inputs |
|
[] |
|
(let [[canvas-width canvas-height] (read-line-ints)] |
|
(loop [papers (list (make-paper canvas-width canvas-height)) |
|
colors #{0}] |
|
(if-let [[color x y w h] (read-line-ints)] |
|
(recur (conj papers (make-paper color x y w h)) |
|
(conj colors color)) |
|
{:papers (into [] papers) |
|
:colors colors |
|
:canvas-width canvas-width |
|
:canvas-height canvas-height})))) |
|
|
|
(defn- read-input-file |
|
[file-name] |
|
(with-open |
|
[rdr (io/reader (io/resource file-name))] |
|
(binding [*in* rdr] |
|
(parse-inputs)))) |
|
|
|
(def ^:private input-files |
|
["100rects100x100.in" |
|
"100rects10Kx10K.in" |
|
"100rects3Kx3K.in"]) |
|
|
|
(defn- covered? |
|
[^long canvas-x ^long canvas-y ^Paper p] |
|
(and (<= (.x1 p) canvas-x) |
|
(<= canvas-x (.x2 p)) |
|
(<= (.y1 p) canvas-y) |
|
(<= canvas-y (.y2 p)))) |
|
|
|
(defn- intersects? |
|
[{left-1 :x1 top-1 :y1 right-1 :x2 bottom-1 :y2 :as rect1} |
|
{left-2 :x1 top-2 :y1 right-2 :x2 bottom-2 :y2 :as rect2}] |
|
(not |
|
(or (> left-1 right-2) ; 1 to right of 2 |
|
(< right-1 left-2) ; 1 to left of 2 |
|
(> top-1 bottom-2) ; 1 below 2 |
|
(< bottom-1 top-2) ; 1 above 2 |
|
))) |
|
|
|
(defn- coarse-index [canvas x y] |
|
(let [x-step (int (Math/ceil (/ (:w canvas) (float BLOCKS)))) |
|
y-step (int (Math/ceil (/ (:h canvas) (float BLOCKS)))) |
|
x-idx (quot x x-step) |
|
y-idx (quot y y-step)] |
|
(+ (* BLOCKS y-idx) x-idx))) |
|
|
|
(defn- subdiv-rect [canvas x-idx y-idx] |
|
(let [x-step (int (Math/ceil (/ (:w canvas) BLOCKS))) |
|
y-step (int (Math/ceil (/ (:h canvas) BLOCKS)))] |
|
(make-paper 0 (* x-idx x-step) (* y-idx y-step) x-step y-step))) |
|
|
|
(defn- make-paper-index [canvas papers] |
|
(reduce |
|
(fn [index [xi yi]] |
|
(let [rect (subdiv-rect canvas xi yi)] |
|
(assoc index |
|
(+ (* BLOCKS yi) xi) |
|
(into-array (filter #(intersects? rect %) papers))))) |
|
{} |
|
(for [xi (range BLOCKS) yi (range BLOCKS)] [xi yi]))) |
|
|
|
#_(defn- old-visible-color |
|
[coord papers] |
|
(some #(when (covered? coord %1) (:color %1)) |
|
papers)) |
|
|
|
(defn- old-visible-color |
|
[^long x ^long y ^"[Lrdp.214_intermediate.Paper;" papers] |
|
(let [len (alength papers)] |
|
(loop [i 0] |
|
(if (< i len) |
|
(let [p ^Paper (aget papers i)] |
|
(if (covered? x y p) |
|
(.color p) |
|
(recur (unchecked-inc i)))) |
|
nil)))) |
|
|
|
(defn- visible-color |
|
[coord canvas paper-index] |
|
(let [i (apply coarse-index canvas coord) |
|
papers (get paper-index i [])] |
|
(some #(when (covered? coord %1) (:color %1)) |
|
papers))) |
|
|
|
(defn- visible-color-frequencies |
|
[xlo xhi ylo yhi papers] |
|
(let [acc (transient {})] |
|
(doseq [y (range ylo yhi) |
|
x (range xlo xhi)] |
|
(when-let [color (old-visible-color x y papers)] |
|
(assoc! acc color (inc (get acc color 0))))) |
|
(persistent! acc))) |
|
|
|
(defn- visible-color-frequencies-arr |
|
[xlo xhi ylo yhi colors papers] |
|
(let [color-counts (long-array (count colors))] |
|
(doseq [y (range ylo yhi) |
|
x (range xlo xhi)] |
|
(when-let [color (old-visible-color x y papers)] |
|
(aset ^longs color-counts color |
|
(inc (aget ^longs color-counts color))))) |
|
(zipmap (range) color-counts))) |
|
|
|
(defn- solve |
|
[input-file] |
|
(let [input (read-input-file input-file) |
|
input (assoc input |
|
:paper-index |
|
(make-paper-index (last (:papers input)) (:papers input))) |
|
w (:canvas-width input) |
|
h (:canvas-height input) |
|
canvas (last (:papers input)) |
|
colors (:colors input) |
|
xstep (int (Math/ceil (/ w (float BLOCKS)))) |
|
ystep (int (Math/ceil (/ h (float BLOCKS)))) |
|
maps (doall |
|
(pmap (fn [[xi yi]] |
|
(let [xlo (* xstep xi) |
|
ylo (* ystep yi) |
|
xhi (min w (+ xstep xlo)) |
|
yhi (min h (+ ystep ylo)) |
|
idx (coarse-index canvas xlo ylo) |
|
papers (get (:paper-index input) idx)] |
|
(visible-color-frequencies-arr xlo xhi ylo yhi colors papers))) |
|
(for [xi (range BLOCKS) yi (range BLOCKS)] [xi yi]))) |
|
color-map (apply merge-with + maps) |
|
sorted (sort-by key color-map)] |
|
(doseq [line sorted] |
|
(println (key line) (val line))))) |
|
|
|
;; (defn -main |
|
;; ([] (-main 0)) |
|
;; ([index] |
|
;; (time (solve (input-files (Integer/parseInt index)))))) |
|
|
|
(defn -main |
|
([] (-main "0")) |
|
([index] |
|
(time |
|
(binding [*unchecked-math* :warn-on-boxed |
|
*warn-on-reflection* true] |
|
(solve (input-files (Integer/parseInt index))))) |
|
(shutdown-agents))) |