Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Last active May 29, 2020 12:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ericnormand/c888c22c27e0a6c4edec6e83c5069f1a to your computer and use it in GitHub Desktop.
Save ericnormand/c888c22c27e0a6c4edec6e83c5069f1a to your computer and use it in GitHub Desktop.

Symmetry

We need to classify patterns into four different categories:

  1. horizontally symmetrical
  2. vertically symmetrical
  3. perfect (both vertically and horizontally symmetrical)
  4. imperfect (neither vertically nor horizontally symmetrical)

Patterns are two-dimmensional. We will represent them with vectors of vectors. Each inner vector is a row.

Write a function classify that takes a pattern and returns one of :vertical, :horizontal, :perfect, or :imperfect.

Examples

(classify [["a" "b" "a"]
           ["x" "y" "x"]]) ;=> :horizontal
(classify [["a" "b" "c"]]) ;=> :vertical ;; trivially so
(classify [["a" "b" "a"]
           ["y" "X" "y"]
           ["a" "b" "a"]]) ;=> :perfect

UPDATE: I have horizontal and vertical switched accidentally, but I won't change it since people have already submitted.

Thanks to this site for the challenge idea where it is considered Expert level in JavaScript.

(ns tst.demo.core
(:use tupelo.core tupelo.test)
(:require
[schema.core :as s]
[tupelo.array :as tar]))
(def ArrayClass (s/constrained s/Keyword #{:horizontal :vertical :perfect :imperfect}))
(s/defn classify :- ArrayClass
[edn-data :- [[s/Any]]]
(let [array (tar/rows->array edn-data) ; verifies rectangular (non-ragged)
sym-horiz? (= array (tar/flip-lr array))
sym-vert? (= array (tar/flip-ud array))
result (cond
(and sym-horiz? sym-vert?) :perfect
sym-vert? :vertical
sym-horiz? :horizontal
:else :imperfect)]
result))
(dotest
(is= (classify [["a" "b" "a"]
["x" "y" "x"]]) :horizontal)
(is= (classify [["a" "b" "c"]]) :vertical)
(is= (classify [["a" "b" "a"]
["y" "X" "y"]
["a" "b" "a"]]) :perfect)
(is= (classify [["a" "b" "a"]
["y" "X" "y"]
["666" "b" "a"]]) :imperfect))
(defn sym-h? [xs]
(every? #(= % (reverse %)) xs))
(defn sym-v? [xs]
(if (empty? xs)
true
(-> (apply mapv vector xs)
(sym-h?))))
(defn classify [xs]
(let [sym-h (sym-h? xs)
sym-v (sym-v? xs)]
(cond
(and sym-h sym-v) :perfect
sym-h :horizontal
sym-v :vertical
:else :imperfect)))
(defn symmetrical?
"Checks whether a sequence is equal to its reverse."
[s]
(= s (reverse s)))
(defn classify
[ss]
(let [horizontal? (every? symmetrical? ss)]
(if (symmetrical? ss)
(if horizontal? :perfect :vertical)
(if horizontal? :horizontal :imperfect))))
(ns functional-tv-puzzles.-2020.patterns-378)
;; Solution 1
(defn symmetric? [vovs]
(let [siz (count vovs)
mid (quot siz 2)]
(->> vovs
(split-at mid)
((fn [[front back]]
[(reverse front), (drop (if (odd? siz) 1 0) back)]))
(apply map vector)
(every? #(apply = %)))))
(defn classify [vovs]
(let [rows vovs
horiz? (symmetric? rows)
cols (when (seq vovs) (apply mapv vector vovs))
vert? (symmetric? cols)]
(cond
(not cols) :perfect
(and horiz? vert?) :perfect
horiz? :horizontal
vert? :vertical
:else :imperfect)))
;; Solution 2
(defn ->1d [row col rowsiz]
(-> row (* rowsiz) (+ col)))
(defn mirrors [i rowsiz numrows]
(let [r (quot i rowsiz)
c (rem i rowsiz)
r' (- numrows r 1)
c' (- rowsiz c 1)]
[(->1d r' c rowsiz) (->1d r c' rowsiz)]))
(defn classify-2 [vovs]
(let [ {:keys [horiz? vert?] :as result}
(transduce (comp cat (map-indexed vector))
(completing
(fn [{:keys [horiz? vert? peers rowsiz numrows] :as acc}
[i v :as iv]]
(let [[row-pidx col-pidx] (mirrors i rowsiz numrows)
row-peer (get peers row-pidx)
col-peer (get peers col-pidx)
horiz?' (when horiz? (if row-peer (= v row-peer) true))
vert?' (when vert? (if col-peer (= v col-peer) true))]
(if
(= [false false] [horiz?' vert?']) (reduced :imperfect)
(-> acc
(assoc-in [:peers i] v)
(assoc :horiz? horiz?')
(assoc :vert? vert?'))))))
{:horiz? true :vert? true
:rowsiz (count (first vovs))
:numrows (count vovs)}
vovs)]
(cond
(and horiz? vert?) :perfect
horiz? :horizontal
vert? :vertical
:else :imperfect)))
(defn horizontal-symmetry? [row]
(= row
(reverse row)))
(defn fully-horizontal? [matrix]
(as-> matrix $
(map horizontal-symmetry? $)
(set $)
(contains? $ false)
(not $)))
(defn vertical-symmetry? [matrix]
(= matrix
(reverse matrix)))
(defn classify [matrix]
(let [vertical? (vertical-symmetry? matrix)
horizontal? (fully-horizontal? matrix)]
(cond
(and vertical? horizontal?) :perfect
vertical? :vertical
horizontal? :horizontal
:else :imperfect)))
(defn classify [mat]
(let [symetric-seq? #(= % (reverse %))
transpose #(apply map vector %)
h-symetric? (every? symetric-seq? mat)
v-symetric? (every? symetric-seq? (transpose mat))]
(cond
(and h-symetric? v-symetric?) :perfect
h-symetric? :horizontal
v-symetric? :vertical
:else :imperfect)))
(defn classify [mx]
(let [sym1? #(= (seq %) (reverse %))
allsym? #(every? true? (map sym1? %))
hsym? (allsym? mx)
vsym? (allsym? (apply map vector mx))
perf? (and hsym? vsym?)]
(cond
perf? :perfect
hsym? :horizontal
vsym? :vertical
:else :imperfect)))
(defn classify [rows]
(let [symmetrical? (fn [rows] (every? #(= % (reverse %)) rows))
columns (apply map vector rows)]
(case [(symmetrical? rows) (symmetrical? columns)]
[true true] :perfect
[true false] :horizontal
[false true ] :vertical
:imperfect)))
(defn rows [grid]
grid)
(defn cols [grid]
(loop [res []
rows grid]
(if (empty? (first rows))
res
(recur (conj res (map first rows))
(map rest rows)))))
(defn classify [grid]
(let [symmetric? (fn [vals] (= vals (reverse vals)))
h-sym? (every? symmetric? (rows grid))
v-sym? (every? symmetric? (cols grid))]
(cond
(and h-sym? v-sym?) :perfect
h-sym? :horizontal
v-sym? :vertical
:else :imperfect)))
(defn symmetrical? [xs]
(= xs (reverse xs)))
(defn classify [rows]
(let [vertical? (symmetrical? rows)
horizontal? (every? symmetrical? rows)]
(cond
(and vertical? horizontal?) :perfect
vertical? :vertical
horizontal? :horizontal
:else :imperfect)))
@miner
Copy link

miner commented May 21, 2020

looping like a C programmer

(defn classify [v2]
  (let [sym? (fn [v]
               (loop [eq true  start 0  end (dec (count v))]
                 (if (and (> end start) eq)
                   (recur (= (v start) (v end)) (inc start) (dec end) )
                   eq)))
        horz? (every? sym? v2)
        vert? (sym? v2)]
    (cond (and horz? vert?) :perfect
          horz? :horizontal
          vert? :vertical
          :else :imperfect)))

@KingCode
Copy link

KingCode commented May 24, 2020

Nice job everyone!

It seems almost everyone went with the examples of the problem description in this gist, rather than the site which inspired it - essentially the meanings of :horizontal and :vertical are reversed, (reflecting across a dividing axis orthogonal to the dimension as in the original, vs the dimension of the line linking reflected values as in this gist). I chose the original as it seems more intuitive.

Here are my findings for most solutions against my own tests (see previous post above) - including a few odd errors on empty lists.
If you followed this gist's examples, then it makes sense that they appear reversed. If your name doesn't appear, all my tests passed but would fail against this gist's examples.

|    :coder-name |                         :input |   :expected |                        :actual |    :solution |
|----------------+--------------------------------+-------------+--------------------------------+--------------|
|          miner |                [[:a :b :c :d]] | :horizontal |                      :vertical | Comment area |
|                |                                |             |                                |     (1 of 2) |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
|    ReilySiegel |                [[:a :b :c :d]] | :horizontal |                      :vertical |              |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                     :imperfect |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                     :imperfect |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                             [] |    :perfect | java.lang.UnsupportedOperation |              |
|                |                                |             | Exception: count not supported |              |
|                |                                |             |  on this type: core$map$fn__58 |              |
|                |                                |             |                             62 |              |
|                | [[:a :b :b :a] [:b :b :b :b] [ |    :perfect |                      :vertical |              |
|                |                  :a :b :b :a]] |             |                                |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
|        ninjure |                [[:a :b :c :d]] | :horizontal |                      :vertical | Comment area |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                             [] |    :perfect | java.lang.IllegalArgumentExcep |              |
|                |                                |             | tion: Don't know how to create |              |
|                |                                |             |  ISeq from: clojure.core$map$f |              |
|                |                                |             |                        n__5862 |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
|          miner |                [[:a :b :c :d]] | :horizontal |                      :vertical | Comment area |
|                |                                |             |                                |     (2 of 2) |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
|   AlanThompson |                [[:a :b :c :d]] | :horizontal |                      :vertical |              |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
|   MarkChampine |                [[:a :b :c :d]] | :horizontal |                      :vertical |              |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                             [] |    :perfect | java.lang.IllegalArgumentExcep |              |
|                |                                |             | tion: Don't know how to create |              |
|                |                                |             |  ISeq from: clojure.core$map$f |              |
|                |                                |             |                        n__5862 |              |
|                |                           [[]] |    :perfect |                      :vertical |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
|  DanielGaspani |                [[:a :b :c :d]] | :horizontal |                      :vertical |              |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
|    JuanMonetta |                [[:a :b :c :d]] | :horizontal |                      :vertical |              |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                             [] |    :perfect | java.lang.IllegalArgumentExcep |              |
|                |                                |             | tion: Don't know how to create |              |
|                |                                |             |  ISeq from: clojure.core$map$f |              |
|                |                                |             |                        n__5862 |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
| StefanWestcott |                [[:a :b :c :d]] | :horizontal |                      :vertical |              |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
|   JonathanChen |                [[:a :b :c :d]] | :horizontal |                      :vertical |              |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |
|   JamesElliott |                [[:a :b :c :d]] | :horizontal |                      :vertical |              |
|                |                      [[:a :b]] | :horizontal |                      :vertical |              |
|                |                   [[:a :b :c]] | :horizontal |                      :vertical |              |
|                |              [[:b :a] [:b :a]] | :horizontal |                      :vertical |              |
|                | [[1 2 3 4] [5 6 7 8] [5 6 7 8] | :horizontal |                      :vertical |              |
|                |                     [1 2 3 4]] |             |                                |              |
|                | [[:c :a :a :a] [:b :b :b :b] [ | :horizontal |                      :vertical |              |
|                |                  :c :a :a :a]] |             |                                |              |
|                |                    [[:a] [:b]] |   :vertical |                    :horizontal |              |
|                |               [[:a] [:b] [:c]] |   :vertical |                    :horizontal |              |
|                |  [[:c :a :a :c] [:d :b :b :d]] |   :vertical |                    :horizontal |              |
|                |        [[:a :b :a] [:x :y :x]] |   :vertical |                    :horizontal |              |
|                | [[:a :b :a] [:b :b :b] [:a :b  |   :vertical |                    :horizontal |              |
|                |                :a] [:a :b :a]] |             |                                |              |
|                |                                |             |                                |              |
|                |                                |             |                                |              |

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment