(let
[check (fn [& sets]
(first (filter #(not (nil? %))
(map
(fn [ss]
(let [r (first (filter #(or (= % #{:x}) (= % #{:o})) ss))]
(if r (first r) nil)))
sets))))]
(defn ttt [board]
(check
(map set board)
(map set (apply map list board))
(list (set (map #(nth (nth board %) %) (range 3))))
(list (set (map #(nth (nth board %) (- 2 %)) (range 3))))
)))
(assert (= :x (ttt [[:x :o :x] [:x :o :o] [:x :x :o]])))
(assert (= :o (ttt [[:o :x :x] [:x :o :x] [:x :o :o]])))
(assert (nil? (ttt [[:x :o :x] [:x :o :x] [:o :x :o]])))This code is returning the player that won a game of tic-tac-toe from a board input.
This code checks the rows, columns, and both diagonals of the input board to see if any of them have a winning sequence (all the same pieces in a row). To do so, a set is formed for each to see all the unique pieces. If there is only one, that means that the given row is a winning row, and the first encountered will be returned at the end of the function, or if there is no winner, nil will be returned.
One of the most important principles of programming is to write human-readable code. The biggest issue that I see here is a lack of clarity in variable names. From the perspective of this exercise, it is definitely fun to play detective here to see what r and ttt mean, but is hardly maintainable in a larger codebase. Additionally, there is a lot of heavy nesting, and this can become difficult to reason through for the outside observer. I find the use of let, ->, and ->> are very helpful in cleaning up heavy nesting, and they should probably be used as soon as you have more than 2 levels. I would specifically use let for logical breakpoints in an algorithm to help a reader as much as possible, and the threading macros for compressing more granular changes that don't have clear intermediate values. I also like to remove "magic constants" from the code, and place them either in a let, or in the arguments of the function with default values if they are likely to be generalized. The only reason for a let to exist outside of a function definition is for the values to be shared among multiple functions, yet stay lexically scoped to those function definitions, or to provide a mutable variable to a closure, so I would recommend consolidating all of the let expressions into one within the defn, just to clean things up a bit. It is also important to include docstrings in any function that is to be shared or run outside of the namespace itself, and can be nice to do so regardless. Some important things to note as well are that this function doesn't check the validity of the board it is given, and assumes that the first win it runs into is the only player who won (an invalid input could have a row of :x and a row of :o. I have also added assertions that nil isn't recognized as a winner (checked before :x), and that the diagonals are working properly.
Following the principles outlined above, I have rewritten the funciton to use only one internal let to provide most of the clarity, along with reasonable variable names and options with defaults for pieces that may be generalized. This spans many more lines, but is a small price to pay for the increase in legibility.
(defn tic-tac-toe
"Given a tic-tac-toe board, determine the winner, if there is one.
Otherwise, return nil. Can take a map of options including alternate
players and board lengths. Doesn't validate board input, and therefore
assumes all encountered tic-tac-toes belong to one player, so takes only
the first one."
[board & {:keys [players board-length]
:or {players #{:x :o}
board-length 3}}]
(let [rows (map set board)
cols (map set (apply map list board))
diagonal1 (->> (range board-length)
(map #(nth (nth board %) %))
set
list)
diagonal2 (->> (range board-length)
(map #(nth (nth board %) (- (- board-length 1) %)))
set
list)
winning-row? #(->> %
(clojure.set/intersection players)
count
(= 1))
get-winner (fn [sets]
(->> sets
(filter winning-row?)
first
first))]
(->> [rows cols diagonal1 diagonal2]
(map get-winner)
(remove nil?)
first)))
(assert (= :x (tic-tac-toe [[:x :o :x]
[:x :o :o]
[:x :x :o]])))
(assert (= :o (tic-tac-toe [[:o :x :x]
[:x :o :x]
[:x :o :o]])))
(assert (nil? (tic-tac-toe [[:x :o :x]
[:x :o :x]
[:o :x :o]])))
(assert (= :x (tic-tac-toe [[nil nil nil]
[nil nil nil]
[:x :x :x]])))
(assert (= :x (tic-tac-toe [[nil nil :x]
[nil :x nil]
[:x :o :o]])))
(assert (= :x (tic-tac-toe [[:x nil nil]
[nil :x nil]
[:o :o :x]])))I opted to generalize to squares of any width, and I deemed empty codes to be invalid. I like to lean on let to provide local functions/constants that are human readable in the body of the function. When it comes down to it, the high level algorithm is just going through each number and ensuring they are valid, using a set to store the numbers previously seen. A valid number is one that exists in the square, hasn't been seen before, and is next in line on the path of unseen numbers if horizontal, vertical, or 45 degrees away from a the last number. Most of the let functions are just figuring out how to generate the path of numbers moved through with a motion, and what direction the motion is moving.
(defn- abs
"Returns the absolute value of the input"
[n]
(max (- n) n))
(defn valid-path
"Determines if the input path is valid with regards to a square of a given
`square-width`. The standard is 3, representing the standard android lock pad.
A valid combination must only hit each number once,and can only move
horizonally, vertically, or along a 45 degree angle if it hits each member
sequentially in its path, with the exception of those already selected.
Otherwise, a line won't intersect with any other points, and any unselected
number is fine."
[path & {:keys [square-width] :or {square-width 3}}]
(let [max-num (* square-width square-width)
get-row-index (fn [n]
(quot (- n 1) square-width))
get-col-index (fn [n]
(mod (- n 1) square-width))
valid-number? (fn [n]
(and (>= n 1) (<= n max-num)))
horizontal-move? (fn [current-n next-n]
(= (get-row-index current-n)
(get-row-index next-n)))
vertical-move? (fn [current-n next-n]
(= (get-col-index current-n)
(get-col-index next-n)))
diagonal-move? (fn [current-n next-n]
(= (abs (- (get-row-index next-n)
(get-row-index current-n)))
(abs (- (get-col-index next-n)
(get-row-index current-n)))))
rightward-move? (fn [current-n next-n]
(> (- (get-col-index next-n)
(get-col-index current-n))
0))
downward-move? (fn [current-n next-n]
(> (- (get-row-index next-n)
(get-row-index current-n))
0))
get-interval (fn [current-n next-n]
(cond
(horizontal-move? current-n next-n)
(if (rightward-move? current-n next-n)
1
(- 1))
(vertical-move? current-n next-n)
(if (downward-move? current-n next-n)
square-width
(- square-width))
(diagonal-move? current-n next-n)
(+ (if (rightward-move? current-n next-n) 1 (- 1))
(if (downward-move? current-n next-n)
square-width
(- square-width)))
:else (- next-n current-n)))
valid-next? (fn [seen last-seen next-seen]
(cond
(not (valid-number? next-seen)) false
(seen next-seen) false
(->> (get-interval last-seen next-seen)
(range last-seen next-seen)
(drop 1)
(every? seen)) true
:else false))]
(if (and (seq path) (valid-number? (first path)))
(loop [seen #{(first path)} last-seen (first path) path (rest path)]
(let [next-seen (first path)]
(if (valid-next? seen last-seen next-seen)
(recur (conj seen next-seen) next-seen (rest path))
false)))
false)))1. Given a PIN entered with a 9-digit keypad instead, how many digits would be required to have more possible combinations than the pattern lock?
Only two digits are required, since any number can follow the first, but not any number can follow the first on the pattern lock, unless it is the middle number, 5.
I opted to break the problem into producing lists to be checked in all directions, and checking each with a private function. This is similar to how the tic-tac-toe problem is solved. This just checks that the letters are the same for the length of the target word along the list to be checked, starting with each match of the first letter. If they are, 1 is added to the overall count. Pretty simple. Empty words are assumed to be invalid, so there is a count of 0. I decided to break out the private function since it makes good sense on its own, and cleans up the let expression for the matrix version. If diagonals were also capable of being checked, then lists would be formed similar to the tic-tac-toe problem, but including more than just the middle diagonal (can just drop the first column/row and use the same range technique, up until no columns/rows are left).
(defn- count-words-in-list
"Count the occurrences of a given word in a list"
[word letter-list]
(let [target-letters (seq word)
letter-count (count target-letters)
all-exist? (fn [target-letters letter-list]
(and
(>= (count letter-list) letter-count)
(every? (fn [[a b]] (= a b))
(map vector target-letters letter-list))))]
(loop [letter-list letter-list word-count 0]
(cond
(not (seq letter-list)) word-count
(=
(first letter-list)
(first target-letters))
(recur
(rest letter-list)
(+ word-count (if (all-exist? target-letters letter-list) 1 0)))
:else (recur (rest letter-list) word-count)))))
(defn count-words-in-matrix
"Count the occurrences of a given word in a matrix"
[mat word]
(let [left-to-right mat
right-to-left (map reverse mat)
top-down (apply map list mat)
bottom-up (->> mat
(apply map list)
(map reverse))]
(if (seq target-letters)
(->> (concat
left-to-right
right-to-left
top-down
bottom-up)
(map (partial count-words-in-list word))
(reduce +))
0)))