# 4clojure答案（二）

4clojure答案（一）：

###### #62

(= (take 5 (__ #(* 2 %) 1)) [1 2 4 8 16])
(= (take 100 (__ inc 0)) (take 100 (range)))
(= (take 9 (__ #(inc (mod % 3)) 1)) (take 9 (cycle [1 2 3])))

(fn r [f %]
(cons % (lazy-seq (r f (f %)))))

###### #63

(= (__ #(> % 5) [1 3 6 8]) {false [1 3], true [6 8]})
(= (__ #(apply / %) [[1 2] [2 4] [4 6] [3 6]])
{1/2 [[1 2] [2 4] [3 6]], 2/3 [[4 6]]})
(= (__ count [ [1 2]  [1 2 3] [2 3]])
{1 [ ], 2 [[1 2] [2 3]], 3 [[1 2 3]]})

#(apply merge-with concat (map (fn [x] {(%1 x) [x]}) %2))

```(merge-with concat
{"Lisp" ["Common Lisp" "Clojure"]
"ML" ["Caml" "Objective Caml"]}
{"Lisp" ["Scheme"]
"ML" ["Standard ML"]})
;;=> {"Lisp" ("Common Lisp" "Clojure" "Scheme"), "ML" ("Caml" "Objective Caml" "Standard ML")}```
###### #64

(= 15 (reduce __ [1 2 3 4 5]))
(= 0 (reduce __ []))
(= 6 (reduce __ 1 [2 3]))

+

###### #65

(= :map (__ {:a 1, :b 2}))
(= :list (__ (range (rand-int 20))))
(= :vector (__ [1 2 3 4 5 6]))
(= :set (__ #{10 (rand-int 5)}))
(= [:map :set :vector :list] (map __ [{} #{} [] ()]))

(comp {\# :set \{ :map \[ :vector \c :list} first str)

#({\# :set \{ :map \[ :vector \c :list} (nth (str %) 0))

###### #66

(= (__ 2 4) 2)
(= (__ 10 5) 5)
(= (__ 5 7) 1)
(= (__ 1023 858) 33)

(fn [x y] (if (zero? y) x (recur y (rem x y))))

###### #67

(= (__ 2) [2 3])
(= (__ 5) [2 3 5 7 11])
(= (last (__ 100)) 541)

(fn [n]
(take n
(filter
(fn [x]
(not-any? #(= 0 (mod x %)) (range 2 x))) (iterate inc 2))))

(fn [r c]
(take c
(remove #(some (fn [i] (= (mod % i) 0)) (r 2 %))
(r 2 1e3))))
range

###### #68

(= __
(loop [x 5
result []]
(if (> x 0)
(recur (dec x) (conj result (+ 2 x)))
result)))

[7 6 5 4 3]

###### #69

(fn [f & m]
(reduce
(fn [m [k v]] (conj m [k (if (m k) (f (m k) v) v)]))
{}
(apply concat (map seq m))))

#70

```(fn [s]
(sort-by clojure.string/lower-case
(re-seq #"[A-Za-z]+" s)))```

#71

last

reduce +

###### #84

Write a function which generates the transitive closure of a binary relation. The relation will be represented as a set of 2 item vectors.

(let [divides #{[8 4] [9 3] [4 2] [27 9]}]
(= (__ divides) #{[4 2] [8 4] [8 2] [9 3] [27 9] [27 3]}))

(let [more-legs
#{[“cat” “man”] [“man” “snake”] [“spider” “cat”]}]
(= (__ more-legs)
#{[“cat” “man”] [“cat” “snake”] [“man” “snake”]
[“spider” “cat”] [“spider” “man”] [“spider” “snake”]}))

(let [progeny
#{[“father” “son”] [“uncle” “cousin”] [“son” “grandson”]}]
(= (__ progeny)
#{[“father” “son”] [“father” “grandson”]
[“uncle” “cousin”] [“son” “grandson”]}))
(let [progeny
#{[“father” “son”] [“uncle” “cousin”] [“son” “grandson”]}]
(= (__ progeny)
#{[“father” “son”] [“father” “grandson”]
[“uncle” “cousin”] [“son” “grandson”]}))

(fn f [s]
(#(if (= % s) s (f %))
(set (for [[a b] s [c d] s]
[a (if (= b c) d b)]))))

###### #85

Write a function which generates the power set of a given set. The power set of a set x is the set of all subsets of x, including the empty set and x itself.

#{} #{1}})
(= (__ #{1 :a}) #{#{1 :a} #{:a} #{} #{1}})

(= (__ #{}) #{#{}})

(= (__ #{1 2 3})
#{#{} #{1} #{2} #{3} #{1 2} #{1 3} #{2 3} #{1 2 3}})

(= (count (__ (into #{} (range 10)))) 1024)
(= (count (__ (into #{} (range 10)))) 1024)
(fn [r u]
(r (fn [a e]
(r #(conj % (conj %2 e)) a a))
#{#{}} u))
reduce

###### #86

Happy numbers are positive integers that follow a particular formula: take each individual digit, square it, and then sum the squares to get a new number. Repeat with the new number and eventually, you might get to a number whose squared sum is 1. This is a happy number. An unhappy number (or sad number) is one that loops endlessly. Write a function that determines if a number is happy or not.

(= (__ 7) true)

(= (__ 986543210) true)

(= (__ 2) false)

(= (__ 3) false)
(= (__ 3) false)

#(or (= % 1)
(if (= % 4) false
(recur
(reduce (fn [a c] (+ a (* (- (int c) 48) (- (int c) 48))))
0 (str %)))))

###### #88

Write a function which returns the symmetric difference of two sets. The symmetric difference is the set of items belonging to one but not both of the two sets.

(= (__ #{1 2 3 4 5 6} #{1 3 5 7}) #{2 4 6 7})

(= (__ #{:a :b :c} #{}) #{:a :b :c})

(= (__ #{} #{4 5 6}) #{4 5 6})

(= (__ #{[1 2] [2 3]} #{[2 3] [3 4]}) #{[1 2] [3 4]})

reduce #((if (% %2) disj conj) % %2)

###### #89

Graph Tour

Difficulty: Hard
Topics: graph-theory
Starting with a graph you must write a function that returns true if it is possible to make a tour of the graph in which every edge is visited exactly once.

The graph is represented by a vector of tuples, where each tuple represents a single edge.

The rules are:

– You can start at any node.
– You must visit each edge exactly once.
– All edges are undirected.

(= true (__ [[:a :b]]))

(= false (__ [[:a :a] [:b :b]]))

(= false (__ [[:a :b] [:a :b] [:a :c] [:c :a]
[:a :d] [:b :d] [:c :d]]))

(= true (__ [[1 2] [2 3] [3 4] [4 1]]))

(= true (__ [[:a :b] [:a :c] [:c :b] [:a :e]
[:b :e] [:a :d] [:b :d] [:c :e]
[:d :e] [:c :f] [:d :f]]))

(= false (__ [[1 2] [2 3] [2 4] [2 5]]))

(fn [d [h & r]]
((fn f [a r]
(or (empty? r)
(boolean
(some #(f (nth (d #{a} %) 0) (d #{%} r))
(filter #(some #{a} %) r)))))
(h 1) r))
remove

###### #90

Cartesian Product

Difficulty: Easy
Topics: set-theory
Write a function which calculates the Cartesian product of two sets.

“♥”] [“queen” “♦”] [“queen
(= (__ #{“ace” “king” “queen”} #{“♠” “♥” “♦” “♣”})
#{[“ace” “♠”] [“ace” “♥”] [“ace” “♦”] [“ace” “♣”]
[“king” “♠”] [“king” “♥”] [“king” “♦”] [“king” “♣”]
[“queen” “♠”] [“queen” “♥”] [“queen” “♦”] [“queen” “♣”]})

(= (__ #{1 2 3} #{4 5})
#{[1 4] [2 4] [3 4] [1 5] [2 5] [3 5]})

(= 300 (count (__ (into #{} (range 10))
(into #{} (range 30)))))

#(set (for [x % y %2] [x y]))

###### #91

Graph Connectivity

Difficulty: Hard
Topics: graph-theory
Given a graph, determine whether the graph is connected. A connected graph is such that a path exists between any two given nodes.

-Your function must return true if the graph is connected and false otherwise.

-You will be given a set of tuples representing the edges of a graph. Each member of a tuple being a vertex/node in the graph.

-Each edge is undirected (can be traversed either direction).

(= true (__ #{[:a :a]}))

(= true (__ #{[:a :b]}))

(= false (__ #{[1 2] [2 3] [3 1]
[4 5] [5 6] [6 4]}))

(= true (__ #{[1 2] [2 3] [3 1]
[4 5] [5 6] [6 4] [3 4]}))

(= false (__ #{[:a :b] [:b :c] [:c :d]
[:x :y] [:d :a] [:b :e]}))

(= true (__ #{[:a :b] [:b :c] [:c :d]
[:x :y] [:d :a] [:b :e] [:x :a]}))

(fn [e o]
(let [[h & r] (seq o)]
((fn f [c r]
(or (e r)
(let [n (mapcat #(filter (fn [p] (some (set %) p)) r) c)]
(if (e n) false
(f (reduce conj c n)
(remove (set n) r))))))
#{h} r)))
empty?

(fn [edgeSet]
(let [nodeSet (set (flatten (seq edgeSet)))];get the node set
(loop[connectivity (for [[n1 n2] edgeSet] [#{n1}, n2])];inital connectivity where the first element is the visited nodes
(let[extendedConnectivity (for [[linked node] connectivity, [n1 n2] edgeSet :when (and (or (= n1 node) (= n2 node)) (or (nil? (linked n1)) (nil? (linked n2))))]
[(conj linked n1 n2) (if (= node n1) n2 n1)])];extend the connectivity when a newly linked node is found
(if (not-any? #(= nodeSet %) (map first connectivity));if not a fully connected graph is found
(if (empty? extendedConnectivity) false;and no extended connectivity can be found either
(recur extendedConnectivity));extend the connectivity
true)))));a fully connected graph is found

###### #92

Roman numerals are easy to recognize, but not everyone knows all the rules necessary to work with them. Write a function to parse a Roman-numeral string and return the number it represents.

You can assume that the input will be well-formed, in upper-case, and follow the subtractive principle. You don’t need to handle any numbers greater than MMMCMXCIX (3999), the largest number representable with ordinary letters.

(= 14 (__ “XIV”))

(= 827 (__ “DCCCXXVII”))

(= 3999 (__ “MMMCMXCIX”))

(= 48 (__ “XLVIII”))
(= 48 (__ “XLVIII”))

(fn [roman-numeral]
(let [value-map {\I 1 \V 5 \X 10 \L 50 \C 100 \D 500 \M 1000}]
(reduce + (map
(fn
[str]
(if (and (> (count str) 1) (< (value-map (first str)) (value-map (second str))))
(- (value-map (second str)) (value-map (first str)))
(reduce + (map #(value-map %) str))))
[(first (re-seq #”M*” roman-numeral))
(first (re-seq #”[CD][CDM]*” roman-numeral))
(first (re-seq #”[XL][XLC]*” roman-numeral))
(first (re-seq #”[IV][IVX]*” roman-numeral))]))))

###### #93

Write a function which flattens any nested combination of sequential things (lists, vectors, etc.), but maintains the lowest level sequential items. The result should be a sequence of sequences with only one level of nesting.

(= (__ [[“Do”] [“Nothing”]])
[[“Do”] [“Nothing”]])

(= (__ [[[[:a :b]]] [[:c :d]] [:e :f]])
[[:a :b] [:c :d] [:e :f]])

(= (__ ‘((1 2)((3 4)((((5 6)))))))
‘((1 2)(3 4)(5 6)))
(= (__ ‘((1 2)((3 4)((((5 6)))))))
‘((1 2)(3 4)(5 6)))

#(remove % (tree-seq % seq %2))
#(sequential? (nth % 0))

###### #94

The game of life is a cellular automaton devised by mathematician John Conway.

The ‘board’ consists of both live (#) and dead ( ) cells. Each cell interacts with its eight neighbours (horizontal, vertical, diagonal), and its next state is dependent on the following rules:

1) Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2) Any live cell with two or three live neighbours lives on to the next generation.
3) Any live cell with more than three live neighbours dies, as if by overcrowding.
4) Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Write a function that accepts a board, and returns a board representing the next generation of cells.
(= (__ [” ”
” ## ”
” ## ”
” ## ”
” ## ”
” “])
[” ”
” ## ”
” # ”
” # ”
” ## ”
” “])
(= (__ [” ”
” ”
” ### ”
” ”
” “])
[” ”
” # ”
” # ”
” # ”
” “])
(= (__ [” ”
” ”
” ### ”
” ### ”
” ”
” “])
[” ”
” # ”
” # # ”
” # # ”
” # ”
” “])

(fn [board]
(map #(apply str %) (map
(fn [sub-board]
(apply
(partial
map
(fn [first-row second-row last-row]
(case (count (filter #{\#} (concat first-row last-row [(first second-row) (last second-row)])))
3 \#
2 (second second-row)
\space)))
(map #(partition 3 1 (concat [\space] % [\space])) sub-board)))
(partition 3 1 (concat [” “] board [” “])))))

###### #95

Write a predicate which checks whether or not a given sequence represents a binary tree. Each node in the tree must have a value, a left child, and a right child.

(= (__ ‘(:a (:b nil nil) nil))
true)

(= (__ ‘(:a (:b nil nil)))
false)

(= (__ [1 nil [2 [3 nil nil] [4 nil nil]]])
true)

(= (__ [1 [2 nil nil] [3 nil nil] [4 nil nil]])
false)

(= (__ [1 [2 [3 [4 nil nil] nil] nil] nil])
true)

(= (__ [1 [2 [3 [4 false nil] nil] nil] nil])
false)

(= (__ ‘(:a nil ()))
false)

(fn r [x]
(or (= x nil)
(and (coll? x)
(= (count x) 3)
(every? r (rest x)))))

###### #96

Let us define a binary tree as “symmetric” if the left half of the tree is the mirror image of the right half of the tree. Write a predicate to determine whether or not a given binary tree is symmetric. (see To Tree, or not to Tree for a reminder on the tree representation we’re using).

(= (__ ‘(:a (:b nil nil) (:b nil nil))) true)

(= (__ ‘(:a (:b nil nil) nil)) false)

(= (__ ‘(:a (:b nil nil) (:c nil nil))) false)

(= (__ [1 [2 nil [3 [4 [5 nil nil] [6 nil nil]] nil]]
[2 [3 nil [4 [6 nil nil] [5 nil nil]]] nil]])
true)

(= (__ [1 [2 nil [3 [4 [5 nil nil] [6 nil nil]] nil]]
[2 [3 nil [4 [5 nil nil] [6 nil nil]]] nil]])
false)

(= (__ [1 [2 nil [3 [4 [5 nil nil] [6 nil nil]] nil]]
[2 [3 nil [4 [6 nil nil] nil]] nil]])
false)

(fn [[n l r]]
(= l ((fn f [[n l r]]
(if n [n (f r) (f l)]))
r)))

###### #97

(fn [c]
(nth
(iterate
#(map + `[0 ~@%] `[~@% 0]) )
(- c 1)))

###### #98

(fn [f s]
(set (map #(set (val %)) (group-by f s))))

###### #99

(fn [a b]
(letfn [(step [i]
(if (pos? i)
(cons (rem i 10) (step (quot i 10)))))]
(reverse (step (* a b)))))

###### #100

(fn [e & r]
((fn f [p]
(if (every? #(= (mod p %) 0) r)
p
(f (+ p e))))
e))

###### #101

(fn [n f r c x y]
(last
(f #(f (fn [c i]
(conj c (+ 1 (min (n % (+ i 1)) (n c i)
(- (n % i) ({(n x i) 1} (n y %2) 0))))))
[(+ %2 1)] (r (c x)))
(r (+ 1 (c x)))
(r (c y)))))
nth reduce range count

###### #102

(fn [s]
(let [r (re-seq #”[^-]+” s)]
(apply str (cons
(first r)
(map
#(apply str (concat [(.toUpperCase (str (first %)))] (rest %)))
(rest r))))))

###### #103

Given a sequence S consisting of n elements generate all k-combinations of S, i. e. generate all possible sets consisting of k distinct elements taken from S. The number of k-combinations for a sequence is equal to the binomial coefficient.

(= (__ 1 #{4 5 6}) #{#{4} #{5} #{6}})

(= (__ 10 #{4 5 6}) #{})

(= (__ 2 #{0 1 2}) #{#{0 1} #{0 2} #{1 2}})

(= (__ 3 #{0 1 2 3 4}) #{#{0 1 2} #{0 1 3} #{0 1 4} #{0 2 3} #{0 2 4}
#{0 3 4} #{1 2 3} #{1 2 4} #{1 3 4} #{2 3 4}})

(= (__ 4 #{[1 2 3] :a “abc” “efg”}) #{#{[1 2 3] :a “abc” “efg”}})

(= (__ 2 #{[1 2 3] :a “abc” “efg”}) #{#{[1 2 3] :a} #{[1 2 3] “abc”} #{[1 2 3] “efg”}
#{:a “abc”} #{:a “efg”} #{“abc” “efg”}})
(= (__ 2 #{[1 2 3] :a “abc” “efg”}) #{#{[1 2 3] :a} #{[1 2 3] “abc”} #{[1 2 3] “efg”}
#{:a “abc”} #{:a “efg”} #{“abc” “efg”}})

(fn [c u]
(set (filter
#(= (count %) c)
(reduce (fn [a e]
(reduce #(conj % (conj %2 e)) a a))
#{#{}} u))))

###### #114

For Science!

Difficulty: Hard
Topics: game
A mad scientist with tenure has created an experiment tracking mice in a maze. Several mazes have been randomly generated, and you’ve been tasked with writing a program to determine the mazes in which it’s possible for the mouse to reach the cheesy endpoint. Write a function which accepts a maze in the form of a collection of rows, each row is a string where:
spaces represent areas where the mouse can walk freely
hashes (#) represent walls where the mouse can not walk
M represents the mouse’s starting point
C represents the cheese which the mouse must reach
The mouse is not allowed to travel diagonally in the maze (only up/down/left/right), nor can he escape the edge of the maze. Your function must return true iff the maze is solvable by the mouse.

(= true (__ [“M C”]))
(= true (__ [“M C”]))

(= false (__ [“M # C”]))

(= true (__ [“#######”
“# #”
“# # #”
“#M # C#”
“#######”]))

(= false (__ [“########”
“#M # #”
“# # #”
“# # # #”
“# # #”
“# # #”
“# # # #”
“# # #”
“# # C#”
“########”]))

(= false (__ [“M ”
” ”
” ”
” ”
” ##”
” #C”]))

(= true (__ [“C######”
” # ”
” # # ”
” # #M”
” # “]))

(= true (__ [“C# # # #”
” ”
“# # # # ”
” ”
” # # # #”
” ”
“# # # #M”]))
(= true (__ [“C# # # #”
” ”
“# # # # ”
” ”
” # # # #”
” ”
“# # # #M”]))

(fn [r m]
(not= nil (some #(re-seq #”C@” %)
(flatten (take 50 (iterate r m))))))
#(map (fn [s] (.replaceAll s “(M|@) ” “\$1@”))
(reverse (apply map str %)))

###### #134

(fn
[a b]
(let [ret (find b a)]
(and (not (= ret nil)) (= (get b a) nil)))) 