Skip to content

Instantly share code, notes, and snippets.

@thattommyhall
Last active December 12, 2015 03:28
Show Gist options
  • Save thattommyhall/4706850 to your computer and use it in GitHub Desktop.
Save thattommyhall/4706850 to your computer and use it in GitHub Desktop.
Hacker cup qualifier
(def letters
(set "abcdefghijklmnopqrstuvwxyz"))
;; If you don't know clojure it might be interesting that sets are functions of their elements
;; and return either nil or the element, so can be used as predicates
(defn counts [s]
(frequencies (filter letters (str/lower-case s))))
;; Here we filter the string for letters we care about (after lowercasing it)
;; and create a map of the characters to there count in the string
;; eg (counts "Good luck in the Facebook Hacker Cup this year!")
;; {\a 3, \b 1, \c 4, \d 1, \e 4, \f 1, \g 1, \h 3, \i 2, \k 3, \l 1, \n 1, \o 4, \p 1, \r 2, \s 1, \t 2, \u 2, \y 1}
(defn beauty [s]
(reduce + (map *
(reverse (sort (vals (counts s))))
(iterate dec 26))))
;; To make the score as big as possible you want the most frequent letter to be worth 26
;; then each one descending by frequency is work 25, 24 etc
;; (reverse (sort (vals (counts s)))) it the frequencies in descending order
;; (iterate dec 26) is 26, 25, 24 etc
;; we multiply each and then add them
(def factorial
(memoize (fn [n]
(reduce *' (range 1 (inc n))))))
(defn nCks [k]
(let [fac (factorial k)]
(map #(/ % fac)
(reductions (fn [acc n]
(* acc (/ n (- n k))))
fac
(iterate inc (inc k))))))
(defn sum-max-of-subsets [cards k]
(let [sorted (drop (dec k) (sort cards))
nck (nCks (dec k))]
(mod (reduce +'
(map * sorted nck))
1000000007)))
(defn bigparse [s]
(bigint (Integer. s)))
(defn parse-input [line1 line2]
(let [k (bigparse (second (str/split line1 #"\s+")))
cards (map bigparse (str/split line2 #"\s+"))
]
(sum-max-of-subsets cards k)))
(defn sum-max-of-subsets [cards k]
(reduce + (map #(apply max %) (comb/combinations cards k))))
@darraghjones
Copy link

f= File.readlines("beautiful_stringstxt.txt")
f[1..-1].each_with_index do |s, i|  
    chars = s.downcase.chars.to_a.find_all {|c| c >= 'a' && c <= 'z' }  
    groups = chars.uniq.map {|c| chars.count(c)}.sort.reverse   
    beauty = groups.each_with_index.reduce(0) {|b, x| b += (26-x[1]) * x[0] }
    puts "Case ##{i+1}: #{beauty}"
end

@thattommyhall
Copy link
Author

Only just saw this after updating my blog, are you suggesting the ruby is clearer?
(I added ``` so it was highlighted properly)

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