Instantly share code, notes, and snippets.

# ericnormand/00 Set game.md

Last active September 26, 2020 00:09
Show Gist options
• Save ericnormand/9675d9ebea9f5e3b66474fdef9e3d1b6 to your computer and use it in GitHub Desktop.

Set Game

I used to play a game called Set. In it, you'd place 12 cards down on the table. Then the players would try to find "sets". If you found a set, you'd race to hit the cards with your hand to claim it. It was tons of fun and just mathy enough to appeal to someone like me.

In this task, you are going to take a function that judges whether three cards constitute a valid "set".

Each card has four properties:

1. Color (red, purple, green)
2. Number (1, 2, 3)
4. Shape (squiggle, oval, diamond)

So one card might have 3 purple full diamonds. Search for the game and look at pictures if you want some examples.

We'll represent each card as a map, like this:

```{:color :purple
:number 3
:shape :diamond}```

Three cards form a set if all of the properties are total matches or total mismatches. A property is a total match if all of the values are the same, for instance three red cards. They are a total mismatch if all the values are different, for instance a diamond, an oval, and a squiggle. If any of the properties don't match or mismatch, it's not a set.

Here's an example of a set:

```[{:color :purple :number 3 :shape :diamond :shading :full}
{:color :red    :number 3 :shape :diamond :shading :lines}
{:color :green  :number 3 :shape :diamond :shading :empty}]```

Colors are a total mismatch, numbers are a total match, shape is a total match, shading is a total mismatch.

Here's an example of a non-set:

```[{:color :purple :number 3 :shape :diamond :shading :full}
{:color :red    :number 3 :shape :diamond :shading :lines}
{:color :purple :number 3 :shape :diamond :shading :empty}]```

Above, the colors are two purples and a red. Not a total match and not a total mismatch.

Write a function that takes an array of cards and says whether they are a set.

`(set? [{..} {..} {..}]) ;=> true/false`

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

### rickerbh commented Sep 21, 2020

It's a bit dense, but...

``````(defn set?
[xs]
(let [attribute-set? (map #(-> (map % xs) set count #{1 3}) [:color :number :shape :shading])]
(every? identity attribute-set?)))
``````

### neominik commented Sep 21, 2020

```(def properties [:color :number :shape :shading])

(defn match? [xs]
(not= (count (set xs)) 2))

(defn set? [cards]
(let [prop-sets (map #(map % cards) properties)]
(every? match? prop-sets)))```

### steffan-westcott commented Sep 21, 2020

```(defn set? [cards]
(every? #(-> (map % cards) set count odd?) [:color :number :shading :shape]))```

### jtlocsei commented Sep 21, 2020

Wow, impressed at the brevity of the answers here. My solution is rather longer...

``````(defn all-same?
"True if all items in a list are the same, false otherwise"
[xs]
(= (count (distinct xs)) 1))
(comment
(all-same? [1 2 3]) ; => false
(all-same? [1 1 1]) ; => true
:_)

(defn all-different?
"True if all items in a list are different, false otherwise"
[xs]
(= (count (distinct xs)) (count xs)))
(comment
(all-different? [1 2 3 1]) ; => false
(all-different? [1 2 3 4]) ; => true
:_)

(defn all-same-or-different?
"True if items in a list are all the same or all different, false otherwise"
[xs]
(or (all-same? xs) (all-different? xs)))
(comment
(all-same-or-different? [1 2 3 1]) ; => false
(all-same-or-different? [1 2 3 4]) ; => true
(all-same-or-different? [1 1 1 1]) ; => true
:_)

(defn card-set?
"True if cards are a set, false otherwise.
Each card has properties :color, :number, :shape, :shading
To be a set, for all properties the cards must be a total match (all values the same)
or a total mismatch (all values distinct)"
[cards]
(let [properties [:color :number :shape :shading]
; val-lists is something like
; ((:purple :red :purple) (3 3 3) (:diamond :diamond :diamond) (:full :lines :empty))
val-lists (for [property properties]
(map property cards))]
(every? all-same-or-different? val-lists)))
(comment
(card-set? [{:color :purple :number 3 :shape :diamond :shading :full}
{:color :red :number 3 :shape :diamond :shading :lines}
{:color :green :number 3 :shape :diamond :shading :empty}])
; => true

(card-set? [{:color :purple :number 3 :shape :diamond :shading :full}
{:color :red :number 3 :shape :diamond :shading :lines}
{:color :purple :number 3 :shape :diamond :shading :empty}])
; => false
:_)
``````

### zugnush commented Sep 21, 2020 • edited

using a map vector to "transpose" we don't need to care what the properties are

```(defn property-set?
[xs]
(contains? #{1 (count xs)} (count (set xs))))

(defn set?
[cards]
(every? property-set? (->> cards
(map vals)
(apply map vector))))```

### hustodemon commented Sep 21, 2020

Using `merge-with` seemed to be a natural approach, but it quickly grew into something not-that-nice. Posting here anyway:

```(defn is-set? [s]
(let [init-acc   {:color #{} :shape #{} :shading #{} :number #{}}
merged     (apply (partial merge-with conj) (cons init-acc s))
counts     (map count (vals merged))]
(every?
(fn [cnt] (not= 2 cnt))
counts)))```

Btw, nice one @neominik!

### daveschoutens commented Sep 21, 2020 • edited

I tried to keep it simple and readable, but I know this can be improved!

I also tried to be flexible about the specific rules of the game:

• Arbitrary assortment of properties
• Arbitrary number of cards per set
```(defn is-set-by-property? [cards prop]
(let [cnt (count (set (map prop cards)))]
(or (= cnt 1)
(= cnt (count cards)))))

(defn is-set? [cards]
(let [card-properties (keys (first cards))]
(every? (partial is-set-by-property? cards) card-properties)))```

### mchampine commented Sep 21, 2020 • edited

```(defn set? [ml]
(let [xpi (map #(map % ml) (keys (first ml)))
tm (map #(apply = %) xpi)
tnm (map #(apply distinct? %) xpi)]
(every? true? (map #(or %1 %2) tm tnm))))```

General in map order and property count

### miner commented Sep 21, 2020

Game description has Shading "lined", but examples show :lines (ending in 's' vs. 'd').

### cloojure commented Sep 21, 2020

This code makes extensive use of Plumatic Schema in order to validate the Cards, etc. It was very valuable to me in catching errors, as well as writing the unit tests along the way.

The code:

```(ns demo.core
(:use tupelo.core)
(:require
[schema.core :as s]
[tupelo.schema :as tsk]))

(def Color (s/enum :purple :red :green))
(def CardNumber (s/enum 1 2 3))
(def Shading (s/enum :empty :lines :full))
(def Shape (s/enum :Squiggle :oval :diamond))

(def Card {:color   Color
:number  CardNumber
:shape   Shape})

(def CardProp (apply s/enum (keys Card)))

(def CardAccumulator {:color   #{Color}
:number  #{CardNumber}
:shape   #{Shape}})

(def CardAccumulatorEmpty {:color   #{}
:number  #{}
:shape   #{}})

(s/defn accum-card
[accum :- CardAccumulator
card :- Card]
(reduce
(s/fn [accum :- CardAccumulator
card-mapentry :- tsk/MapEntry]
(let [[cardprop propval] card-mapentry]
(update-in accum [cardprop]
conj propval)))
accum
card))

(s/defn accum->counts :- [s/Num]
[accum :- CardAccumulator]
(mapv count (vals accum)))

(s/defn are-cards-a-set? :- s/Bool
[cards :- [Card]]
(nl)
(let [cum-cards        (reduce accum-card CardAccumulatorEmpty cards)
cum-cards-counts (accum->counts cum-cards)
valid-set-count? (s/fn [n :- Number] (or (= n 1) (= n 3)))
result           (every? valid-set-count? cum-cards-counts)]
result))```

The unit tests:

```(ns tst.demo.core
(:use demo.core tupelo.core tupelo.test)
(:require
[schema.core :as s]
[tupelo.schema :as tsk]))

(dotest
(throws-not? (s/validate Color :purple))
(throws-not? (s/validate Color :red))
(throws-not? (s/validate Color :green))
(throws? (s/validate Color :blue)))

(def card-11
{:color   :purple
:number  3
:shape   :diamond})

(def card-12
{:color   :red
:number  3
:shape   :diamond})

(def card-13
{:color   :green
:number  3
:shape   :diamond})

(def card-21
{:color   :purple
:number  3
:shape   :diamond})

(def card-22
{:color   :red
:number  3
:shape   :diamond})

(def card-23
{:color   :purple
:number  3
:shape   :diamond})

(dotest
(is (s/validate Card card-11))
(is (s/validate Card card-12))
(is (s/validate Card card-13))
(is (s/validate Card card-21))
(is (s/validate Card card-22))
(is (s/validate Card card-23)))

(def cum-11 {:color   #{:purple}
:number  #{3}
:shape   #{:diamond}})
(dotest
(is= cum-11 (accum-card CardAccumulatorEmpty card-11)))

(dotest
(is= [1 1 1 1] (accum->counts cum-11))
(is= [2 3 2 1] (accum->counts {:color   #{:purple :red}
:number  #{3 2 1}
:shape   #{:diamond}})))

(dotest
(let [hand-1 [card-11 card-12 card-13]
hand-2 [card-21 card-22 card-23]]
(is (are-cards-a-set? hand-1))
(isnt (are-cards-a-set? hand-2))))```

### cloojure commented Sep 21, 2020

Game description has Shading "lined", but examples show :lines (ending in 's' vs. 'd').

This caught me out as well.

### mchampine commented Sep 21, 2020 • edited

@steffan-westcott

```(defn set? [cards]
(every? #(-> (map % cards) set count odd?) [:color :number :shading :shape]))```

Nice! Or with a small tweak you get a slightly smaller and more general version:

```(defn set? [cards]
(every? (comp odd? count set) (apply mapv vector (map vals cards))))```

### steffan-westcott commented Sep 21, 2020

@mchampine Thank you! About the suggested 'transpose' tweak (also suggested by @zugnush), I don't think this is strictly correct since equal maps may have differently ordered entries. In my REPL I get:

```   (vals {:a 1 :b 2})
=> (1 2)
(vals {:b 2 :a 1})
=> (2 1)```

I believe you'd need `sorted-map` or similar to make assumptions on entry order.

### mchampine commented Sep 22, 2020

@mchampine Thank you! About the suggested 'transpose' tweak (also suggested by @zugnush), I don't think this is strictly correct
I believe you'd need `sorted-map` or similar to make assumptions on entry order.

Good point! Transposing does not account for that, and a correct solution shouldn't require sorted maps. How about

```(defn aset? [cards]
(every? #(-> (map % cards) set count odd?) (keys (first cards))))```

which is order agnostic but preserves the generality?

### ndonolli commented Sep 22, 2020

```(defn is-set? [cards]
(let [set-count (count cards)]
(->> cards
(map vals)
(apply interleave)
(partition set-count)
(map (comp count set))
(every? (partial #{1 set-count})))))```

### daveschoutens commented Sep 22, 2020 • edited

Inspired by @steffan-westcott, @mchampine, @ndonolli, (EDIT: And @albertzak) and my own prior solution, here is a version that attempts to optimize for readability/understandability, while being general along card properties and set size:

```(defn is-set? [cards]
(let [properties (keys (first cards))
is-valid-set? #(or (apply distinct? %) (apply = %))
is-property-set? #(->> cards (map %) is-valid-set?)]
(every? is-property-set? properties)))```

Test:

```(is-set? [{:color :red :number 1 :shading :full :shape :square :material :paper}
{:color :blue :number 1 :shading :full :shape :triangle :material :metal}
{:color :green :number 1 :shading :full :shape :circle :material :plastic}
{:color :purple :number 1 :shading :full :shape :pentagon :material :wood}]) ;; true```

### sztamas commented Sep 22, 2020 • edited

Could be made shorter, but was trying to make it a bit more readable.

We collect the distinct values for each key, we count the distinct values and then we compare to `1` (total match) or number of cards (total mismatch) at the end.

```(defn set? [cards]
(let [
init-empty-sets        (zipmap (keys (first cards)) (repeatedly hash-set))
distinct-values        (reduce (partial merge-with conj) init-empty-sets cards)
distinct-values-counts (map count (vals distinct-values))]
(every? #(or
(= 1 %)               ; total match
(= (count cards) %))  ; total mismatch
distinct-values-counts)))```

### tugh commented Sep 22, 2020

```(defn- total-match? [xs]
(apply = xs))

(defn- total-mismatch? [xs]
(apply distinct? xs))

(defn- property-set? [xs]
(or (total-match? xs)
(total-mismatch? xs)))

(defn set? [cards]
(letfn [(extract [k] (map k cards))]
(map extract)
(every? property-set?))))```

### ndonolli commented Sep 22, 2020

@daveschoutens very readable, I like this solution.

### proush42 commented Sep 22, 2020

```(defn is-set? [cards]
(let [val-grps (for [p [:color :number :shading :shape]]
(map p cards))
mixed?   (fn [vs]
(< 1 (count (set vs)) (count vs)))]
(not (some mixed? val-grps))))```

### albertzak commented Sep 22, 2020

```(defn all-distinct-or-same? [& xs]
(or (apply distinct? xs)
(apply = xs)))

(defn set? [xs]
(every? true?
(apply mapv all-distinct-or-same?
(map vals xs))))```

### kolstae commented Sep 23, 2020

```(defn set? [cs]
(every? #{1 3}
(for [k [:color :number :shape :shading]]
(count (distinct (map k cs))))))```

### jeroenvanwijgerden commented Sep 23, 2020 • edited

```(defn update-all
"Similar to clojure.core/update but for all values in m."
[m f]
(reduce-kv (fn [acc k v]
(assoc acc k (f v)))
{}
m))

(defn properties
[cards]
;; sometimes let bindings are much more understandable than a threading macro,
;; typically when the intermediate result changes type significantly.
(let [name+value       (apply concat cards)
name->name+value (group-by first name+value)
name->values     (update-all name->name+value
#(map second %))]
name->values))

(defn total-match?
[values]
(apply = values))

(defn total-mismatch?
[values]
(apply distinct? values))

(defn set?
[cards]
(->> (properties cards)
(every? (fn [[_name values]]
(or (total-match?    values)
(total-mismatch? values))))))

(set? [{:color :purple :number 3 :shape :diamond :shading :full}
{:color :red    :number 3 :shape :diamond :shading :lines}
{:color :green  :number 3 :shape :diamond :shading :empty}]) ; => true

(set? [{:color :purple :number 3 :shape :diamond :shading :full}
{:color :red    :number 3 :shape :diamond :shading :lines}
{:color :purple :number 3 :shape :diamond :shading :empty}]) ; => false```

### KingCode commented Sep 23, 2020

``````(defn prop-success? [prop cards]
(let [vs (map prop cards)]
(or (apply = vs)
(= (count vs) (count (set vs))))))

(def props [:color :number :shape :shading])

(defn set? [cards]
(every? #(prop-success? % cards) props))
``````

### JonathanHarford commented Sep 26, 2020

```(defn is-set? [cards]
(->> cards
first
keys
(every? (fn [property]
(let [values (mapv #(get % property) cards)]
(or (apply = values)
(apply distinct? values)))))))```