Grid Search

the_grid_search.clj

(ns the-grid-search)

;; Solves https://www.hackerrank.com/challenges/the-grid-search/problem

;; Checker has aggressive timeout
(set! *warn-on-reflection* true)
(set! *unchecked-math* true)

(defn first-index-of
  "An alias for the boilerplate to avoid reflection"
  [haystack needle start]
  (.indexOf ^String haystack ^String needle ^int start))

(defn matches?
  "Check whether the pattern is a subgrid of this horizontal slice of the main grid.
   Takes an optional starting index to search from."
  ([G P]
   (matches? G P 0))
  ([G P initial]
   (let [firsts (map #(first-index-of %1 %2 initial) G P)]
     (when-not (some #{-1} firsts)
       (let [max-idx (reduce max firsts)]
         (or (every? #{max-idx} firsts)
             (matches? G P max-idx)))))))

(defn find-first-embedding' [G P]
  (->> G
       (partition (count P) 1)
       (map vec)
       (some #(matches? % P))))

(defn grid-search [G P]
  (if (find-first-embedding' G P) "YES" "NO"))

(defn even-smarter-grid-search
  "🧠!💪"
  [G P]
  (let [haystack (apply str (interpose \! G))
        grid-width (count (first G))
        pattern-width (count (first P))
        line-gap (inc (- grid-width pattern-width))
        needle (->> sub
                    ;; skip over the line-break and irrelevant characters 
                    ;; until we are aligned with the next row
                    (interpose (str ".{" line-gap "}"))
                    (apply str)
                    re-pattern)]
    (if (re-find needle haystack)
      "YES"
      "NO")))

;; -------- quick sanity checks

(assert (= "YES"
           (gridSearch
             ["1234567890"
              "0987654321"
              "1111111111"
              "1111111111"
              "2222222222"]
             ["876543"
              "111111"
              "111111"])))

(assert (= "NO"
           (gridSearch
             ["1234567890"
              "0987654321"
              "1111111111"
              "1111111111"
              "2222222222"]
             ["886543"
              "111111"
              "111111"])))

;; optimized their test loader (I think) - don't think this was a bottleneck in the end though.

(defn rows-count
  [input]
  (Integer. ^String (first (clojure.string/split input #"\s"))))

(let [T (Integer. ^String (read-line))]
  (doseq [_ (range T)]
    (let [digits (vec (for [_ (range (rows-count (read-line)))] (read-line)))
          pattern (vec (for [_ (range (rows-count (read-line)))] (read-line)))
          result (grid-search digits pattern)]
      (spit fptr (str result "\n") :append true)))))