将Clojure引入Euler 19项目

Question

我最近为了好玩而开始学习Clojure，在完成考恩之后，我决定Euler项目将提供我的下一个挑战。以下是问题陈述：

(如果有人知道如何在不破坏格式的情况下将其放入spolier标记中，请随时编辑或评论，并让我知道如何修复它。)

算上星期日Problem 19，您会得到以下信息，但您可能更愿意为自己做一些研究。

• 1900年1月1日是星期一。
• 三十天有九月，
• 四月，六月和十一月。
• 其余的都有三十一,
• 光是拯救二月，
• 那里有二十八个，不管下雨还是晴天。
• 在闰年，29年。
• 闰年发生在任何可以被4整除的年份，但除非它可以被400整除，否则不能发生在一个世纪。

在二十世纪的第一个星期日(1901年1月1日至2000年12月31日)有多少个星期日？

这是我用来找到解决方案的代码。注意，我故意避免使用日期/时间API，这样我就可以尝试更多的语言特性了。

(ns euler.n19)


(def week-days (cycle [:mon :tue :wed :thr :fri :sat :sun]))

(defn leap-year?
  ([year] (if (= 0 (mod year 100))
            (= 0 (mod year 400))
            (= 0 (mod year 4)))))

(def months [:jan :feb :mar :apr :may :jun :jul :agu :sep :oct :nov :dec])
(def month-length {:jan 31 :feb 28 :mar 31 :apr 30 
                   :may 31 :jun 30 :jul 31 :agu 31
                   :sep 30 :oct 31 :nov 30 :dec 31})
(def leap-year-month-length (assoc month-length :feb 29))

(def years (->> (range 1901 2001)
               (map (fn [yr] (if (leap-year? yr) 
                               leap-year-month-length 
                               month-length)))))

(defn zip
  ([coll-1 coll-2] map list coll-1 coll-2))

(defn count-number-of-times-day-on-nth-of-month
  ([day date]
   (->> years
        (map (fn [month-len] (map #(% month-len) months)))
        (flatten)
        (reduce (fn [[week-days num-occurrences] curr-month-len]
                  [(drop curr-month-len week-days)
                   (if (= day (nth week-days date))
                     (inc num-occurrences)
                     num-occurrences)])
                [(drop 1 week-days) 0])
        (second))))

(defn main ([]  println (count-number-of-times-day-on-nth-of-month :sun 0)))

特别是，我想知道如何澄清reduce In count-number-of-times-day-on-nth-of-month，因为在我看来它非常混乱。

(顺便说一句，经过几个小时的讨论，我注意到现在很难正确地键入我的其他代码:)

Answer 1

在给定的year中给出月长序列的函数：

(defn month-seq [year]
  (map
    (if (leap-year? year) leap-year-month-length month-length)
    months))

..。是您的count-number-of-times-day-on-nth-of-month函数所需要的全部。

• 我将其扩展为接受year-range以及day和date。
• 我已经取代了
  • flatten与简单的mapcat和
  • reduce与reductions，简化了算法。

结果是..。

(defn count-number-of-times-day-on-nth-of-month
  [year-range day date]
  {:pre [(>= (first year-range) 1900)]}
  (let [month-lengths (mapcat month-seq (range 1900 (inc (last year-range))))
        day-seqs (reductions
                   (fn [s n] (drop n s))
                   week-days
                   month-lengths)
        first-days (map first day-seqs)]
    (->> first-days
         (drop (+ (* 12 (- (first year-range) 1900)) date))
         butlast
         frequencies
         day)))

例如,

(count-number-of-times-day-on-nth-of-month (range 1901 2001) :sun 0)

杂乱无章

• 您的zip函数(未使用)和main函数都缺少一对括号。
• 如果只有一种情况，则不需要在参数列表和正文周围加上括号。

例如,

(defn zip
  [coll-1 coll-2] (map list coll-1 coll-2))

编辑以更正在处理date参数到count-number-of-times-day-on-nth-of-month时出现的符号错误。

Answer 2

我先前的回答

• 无谓地离开了原著，
• 没能暴露出它的问题。

我们再来一次。

函数count-number-of-times-day-on-nth-of-month有一两个问题：

• 2001年1月1日是星期二。这个从天上掉下来。这并不是从2000年1月1日是星期一这一既定事实出发的。
• 在reduce 中
  • 最初的一周没有经过测试。应该是这样的。
  • 最后一周进行测试。不应该是这样。

一次性错误不会影响问题的情况，因为初始值和最终值都不会落在周日。

让我们把这个函数做得更好。

• 用简单的flatten代替危险的concat。
• 将其合并到前面的map中，以生成mapcat。
• 关键词是函数。因此，我们可以在month-len函数中这样使用mapcat。
• 将nth从循环中移出初始drop。

这给了我们

(defn count-number-of-times-day-on-nth-of-month
  [day date]
  (->> years
       (mapcat (fn [month-len] (map month-len months)))
       (reduce (fn [[week-days num-occurrences] curr-month-len]
                 [(drop curr-month-len week-days)
                  (if (= day (first week-days))
                    (inc num-occurrences)
                    num-occurrences)])
               [(drop (inc date) week-day-cycle) 0])
       (second)))

现在，我们将复杂的reduce分解为一个reduction，然后是一系列简单的序列函数。

(defn count-number-of-times-day-on-nth-of-month
  [day date]
  (->> years
       (mapcat (fn [month-len] (map month-len months)))
       (reductions
         (fn [week-days curr-month-len] (drop curr-month-len week-days))
         (drop (inc date) week-day-cycle))
       butlast
       (map first)
       (filter #(= day %))
       count))

这是较慢，但更清楚。它并不完全相同，因为它正确地考虑了初始值。然而，我们还是要砍掉最后一个。必需的butlast必须介于mapcat和filter之间。

我说过密码有缺陷。这很难证明。然而，我找到了一种方法来对算法进行框架化，从而使测试变得更容易。

其思想是将日历信息作为配置对象传递到函数中。我们建立的标准日历如下：

(def standard-months [:jan :feb :mar :apr :may :jun :jul :agu :sep :oct :nov :dec])

(def non-leap-month-lengths
  (into {}
    (map
      (juxt identity #(case %, (:sep :apr :jun :nov) 30, :feb 28, 31))
      standard-months)))
(def leap-month-lengths (assoc non-leap-month-lengths :feb 29))

(defn standard-month-lengths [year]
  (if (leap-year? year) leap-month-lengths non-leap-month-lengths))

(def standard-calendar
  {:year-zero 1900
   :week-days [:mon :tue :wed :thr :fri :sat :sun]
   :months standard-months
   :month-lengths standard-month-lengths})

然后，一般的函数变成

(defn count-week-days-on-month-day
  [calendar [from-year up-to-year] month-day]
  (let [{:keys [year-zero week-days months month-lengths]} calendar]
    (->> (range year-zero up-to-year)
         (mapcat (comp #(map % months) month-lengths))
         (drop (+ (* (count months) (- from-year year-zero))))
         butlast
         (reductions
           (fn [wds cml] (drop cml wds))
           (drop (dec month-day) (cycle week-days)))
         (map first)
         frequencies)))

这

• 显式下降from-year前几个月；
• 传递所有week-days的频率图；
• 从这个月的第一个月开始，编号为1。

问题的解决变成

(defn count-number-of-times-day-on-nth-of-month [week-day month-day]
  (week-day (count-week-days-on-month-day
              standard-calendar [1901 2001]
              month-day)))

(count-number-of-times-day-on-nth-of-month :sun 1)

这会产生与以前相同的答案，但一般功能更容易测试。例如..。

(def test-calendar
  {:year-zero 100
   :week-days [:doh :rae :me]
   :months [:yip]
   :month-lengths (constantly (constantly 1))})

(count-week-days-on-month-day test-calendar [100 110] :rae 1)
;{:doh 4, :rae 3, :me 3}

请注意

• 频率加起来为10 -正确；
• :doh的频率更高，这是应该的。

这表明该代码是正确的，并且原始代码存在缺陷。

备注

• 1900年不是闰年。
• 因此，2001年1月1日是1900年1月1日之后的365天。
• (mod 365 7)是1。
• 所以2001年1月1日比1900年1月1日(星期二)晚一周.