Anyway, I have to stop encouraging my client, he specifies requirements
like a woman ordering in a restaurant. Here goes:
Given:
(defparameter *pets*
'((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
(cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
(snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
(cow ((jersey 200)(heiffer 300)(moo 400)))))
Write:
(defun digest-tag-population (tag-population pick-tags count)...)
Such that:
(digest-tag-population *pets* '(dog cat snake) 5)
=> ((DOG CBRET 82) (DOG DOBER 42) (CAT RUSS 92) (CAT TIBET 52) (SNAKE
PYTHON 77))
...the rules being:
- consider only the populations of tags (the first symbol in each
sublist) found in the parameter pick-tags, a list
- take only the <count> most populous of the union of the populations
- return (tag name population) of the most populous in this order:
firstly, by position of the tag in pick-tags
second, ie within a tag, in descending order of population
Scroll waaaaaaaaay down for my code.
Remember, you have to code this in one go.
kt
(defun subseq-ex (st e s)
(subseq s st (min e (length s))))
(defun digest-tag-population (tag-population pick-tags count)
(flet ((tagpos (tag) (position tag pick-tags)))
(stable-sort (subseq-ex 0 count
(sort (loop for (tag population) in tag-population
when (tagpos tag)
append (loop for pop in population
collecting (list* tag pop)))
'> :key (lambda (x)
(caddr x))))
'< :key (lambda (x) (tagpos (car x))))))
(defparameter *pets*
'((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
(cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
(snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
(cow ((jersey 200)(heiffer 300)(moo 400)))))
#+test
(digest-tag-population *pets* '(dog cat snake) 5)
In Ruby:
1 PETS = [
2 [:dog, [[:blab, 12], [:glab, 17], [:cbret, 82], [:dober, 42], [:gshep, 25]]],
3 [:cat, [[:pers, 22], [:siam, 7], [:tibet, 52], [:russ, 92], [:meow, 35]]],
4 [:snake, [[:garter, 10], [:cobra, 37], [:python, 77], [:adder, 24], [:rattle, 40]]],
5 [:cow, [[:jersey, 200], [:heiffer, 300], [:moo, 400]]]
6 ]
7
8 def digest_tag_population tag_population, pick_tags, count
9 tag_population.select {|e| pick_tags.include?(e[0]) }.
10 inject([]) {|memo,obj| obj[1].each {|e| memo << [obj[0], e[0], e[1]] }; memo }.
11 sort {|a,b| b[2] <=> a[2] }[0,count].
12 sort_by {|e| [ tag_population.map{|p| p[0]}.rindex(e[0]), e[2] * -1] }
13 end
14
15 digest_tag_population(PETS, [:dog, :cat, :snake], 5)
Line 9: select elements that match the pick tags
Line 10: map to a list of tuples of the form [:dog, :blab, 12]
Line 11: sort the list of tuples by population and select the first count of them
Line 12: sort by tag position, population
Someone please do a Haskell version.
--
Brian Adkins
http://lojic.com/
Holy Craps! That is so cool. Been programming longer than anyone has
been alive and I don't unnerstand a word. Oh, I should read the doc you
so helpfully provided. Duh. Hope my new god WJ likes that cute "unnerstand".
Python:
pets = {'dog' : 'blab 12, glab 17, cbret 82, dober 42, gshep 25',
'cat' : 'pers 22, siam 7, tibet 52, russ 92, meow 35',
'snake' : 'garter 10, cobra 37, python 77, adder 24, rattle 40',
'cow' : 'jersey 200, heiffer 300, moo 400'}
for k in pets: pets[k] = [(k,tag,int(n)) for (tag,n) in
[s.split() for s in pets[k].split(',')]]
def keycmp(f): return lambda x,y: cmp(f(x), f(y))
def dtp(tags, types, cnt):
l = []
for t in types: l.extend(pets[t])
l.sort(keycmp(lambda x:-x[2]))
l=l[:cnt]
l.sort(keycmp(lambda x: types.index(x[0]))
return l
>>> dtp(pets, ['dog','cat','snake'], 5)
[('dog', 'cbret', 82), ('dog', 'dober', 42), ('cat', 'russ', 92),
('cat', 'tibet', 52), ('snake', 'python', 77)]
Scheme:
(define (digest-tag-population population tags count)
(define (tag-position tag) (length (memq tag tags)))
(define (population>? a b) (> (caddr a) (caddr b)))
(define (tag-position<? a b)
(> (tag-position (car a)) (tag-position (car b))))
(define (tagged-list->tuples tagged-list)
(map (lambda (pair) (cons (car tagged-list) pair)) (cadr tagged-
list)))
(let* ((lists (filter (lambda (list) (memq (car list) tags))
population))
(tuples (apply append (map tagged-list->tuples lists))))
(list-sort tag-position<?
(take (list-sort population>? tuples) count))))
(define pets
'((dog ((blab 12) (glab 17) (cbret 82) (dober 42) (gshep 25)))
(cat ((pers 22) (siam 7) (tibet 52) (russ 92) (meow 35)))
(snake ((garter 10) (cobra 37) (python 77) (adder 24) (rattle
40)))
(cow ((jersey 200) (heiffer 300) (moo 400)))))
(digest-tag-population pets '(dog cat snake) 5)
=> ((dog cbret 82) (dog dober 42) (cat russ 92) (cat tibet 52) (snake
python 77))
Someone got a jump on St. Patrick's Day...
>
> pets = {'dog' : 'blab 12, glab 17, cbret 82, dober 42, gshep 25',
> 'cat' : 'pers 22, siam 7, tibet 52, russ 92, meow 35',
> 'snake' : 'garter 10, cobra 37, python 77, adder 24, rattle 40',
> 'cow' : 'jersey 200, heiffer 300, moo 400'}
>
> for k in pets: pets[k] = [(k,tag,int(n)) for (tag,n) in
> [s.split() for s in pets[k].split(',')]]
Damn, I forgot to add K to my wishlist.
kt
clojure short, like line noise (watch out for google groups' line
breaks):
(defn digest-tag-population [tag-population pick-tags count]
(sort-by #(first (for [[idx elt]
(map vector (iterate inc 0) pick-tags)
:when (= elt (first%))] idx))
< (take count (sort-by #(nth % 2) >
(mapcat (fn [a-lst] (map #(cons (first a-lst) %)
(first (rest a-lst))))
(filter #(contains? (set pick-tags) (first %)) tag-
population))))))
clojure, somewhat longer, but actually intelligible:
(defn digest-tag-population [tag-population pick-tags count]
(let [selected (filter #(contains? (set pick-tags) (first %)) tag-
population)
union (mapcat (fn [a-lst]
(map (fn [lst]
(cons (first a-lst) lst))
(first (rest a-lst))))
selected)
pet-position (fn [petsym]
(first (for [[idx elt] (map vector (iterate inc 0) pick-
tags) :when (= elt petsym)] idx)))
pop-sorted (sort-by #(nth % 2) > union)
top-n (take count pop-sorted)
pet-sorted (sort-by #(pet-position (first %)) < top-n)]
pet-sorted))
(defn digest-tag-population [tag-population pick-tags count]
(sort-by #(first (for [[idx elt] (map vector (iterate inc 0) pick-
tags) :when (= elt (first%))] idx))
Ah. now which of these were you able to bang in as is... well, clojure
is new so no fair testing fluency.
meanwhile, I also forgot to ask for a Java version. Mr Bradshaw?
kt
> Ah. now which of these were you able to bang in as is... well, clojure
> is new so no fair testing fluency.
The more readable one. Clojure's let is like lisp's let* so it's easy
to think in progressive chunks, each using the previous binding.
Just for completeness, here's a condensed loopy version in 5 lines of
common lisp with no helper funcs:
(defun digest-tag-population (tag-population pick-tags count)
(stable-sort (subseq (sort (loop for elt in tag-population when
(member (car elt) pick-tags)
append (loop for petexp in (cadr elt)
collect (cons (car elt) petexp)))
#'> :key #'caddr) 0 count)
#'< :key (lambda (x) (position (car x) pick-tags))))
btw, If I were writing this in common lisp and wanted to understand
what I wrote 6 months from now, I'd use the same style as the readable
clojure version, i.e., using let* and perspicuously named intermediate
results:
(defun digest-tag-pop (tag-population pick-tags count)
(let* ((selected (loop for elt in tag-population
when (member (car elt) pick-tags)
collect elt))
(labeled-union (loop for pet-list in selected append
(loop for unlabeld-petexp in (cadr pet-list)
collect (cons (car pet-list) unlabeld-
petexp))))
(pop-sorted (sort labeled-union #'> :key #'caddr))
(top-n (subseq pop-sorted 0 count))
(pet-sorted
(flet ((pet-position (labeled-petexp) (position (car labeled-
petexp) pick-tags)))
(stable-sort top-n #'< :key #'pet-position))))
pet-sorted))
From Paul Rubin on comp.lang.haskell:
import Data.List
import Data.Ord
import Control.Monad
pets =
[("dog", [("blab", 12),("glab", 17),("cbret", 82),
("dober", 42),("gshep", 25)]),
("cat", [("pers", 22),("siam", 7),("tibet", 52),
("russ", 92),("meow", 35)]),
("snake", [("garter", 10),("cobra", 37),("python", 77),
("adder", 24),("rattle", 40)]),
("cow", [("jersey", 200),("heiffer", 300),("moo", 400)])]
digest_tag tag_pop pick_tags count =
let selected_pops =
[(i,(-c,b)) | (i,(a,bs)) <- zip [0..] tag_pop, a `elem` pick_tags,
(b,c) <- bs]
top_pops = sort $ take count (sortBy (comparing snd) selected_pops)
in [(fst (tag_pop !! i), b, -c) | (i, (c,b)) <- top_pops]
main = print $ digest_tag pets ["dog","cat","snake"] 5
> This one was too much fun for words in re how cool it is programming with
> Lisp. I would like to see this in Ruby, Clojure, Qi, and Scheme. The
> precise fun part tho is typing it all in in the final form versus dividing
> the thing up into steps to get intermediate results, ie, a test of one's
> mastery of one's language. Non-functional languages I guess have no choice
> but to stop and assign temporaries.
>
> Anyway, I have to stop encouraging my client, he specifies requirements
> like a woman ordering in a restaurant. Here goes:
>
> Given:
>
> (defparameter pets
> '((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
> (cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
> (snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
> (cow ((jersey 200)(heiffer 300)(moo 400)))))
>
> Write:
>
> (defun digest-tag-population (tag-population pick-tags count)...)
>
> Such that:
>
> (digest-tag-population pets '(dog cat snake) 5)
>
> => ((DOG CBRET 82) (DOG DOBER 42) (CAT RUSS 92) (CAT TIBET 52) (SNAKE
> PYTHON 77))
>
> ...the rules being:
>
> - consider only the populations of tags (the first symbol in each sublist)
> found in the parameter pick-tags, a list
>
> - take only the <count> most populous of the union of the populations
>
> - return (tag name population) of the most populous in this order:
>
> firstly, by position of the tag in pick-tags
> second, ie within a tag, in descending order of population
>
> Scroll waaaaaaaaay down for my code.
>
> Remember, you have to code this in one go.
>
> kt
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> (defun subseq-ex (st e s)
> (subseq s st (min e (length s))))
>
> (defun digest-tag-population (tag-population pick-tags count)
> (flet ((tagpos (tag) (position tag pick-tags)))
> (stable-sort (subseq-ex 0 count
> (sort (loop for (tag population) in tag-population
> when (tagpos tag)
> append (loop for pop in population
> collecting (list* tag pop)))
> '> :key (lambda (x)
> (caddr x))))
> '< :key (lambda (x) (tagpos (car x))))))
>
> (defparameter pets
> '((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
> (cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
> (snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
> (cow ((jersey 200)(heiffer 300)(moo 400)))))
>
> #+test
> (digest-tag-population pets '(dog cat snake) 5)
Arc:
(= pets
'((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
(cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
(snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
(cow ((jersey 200)(heiffer 300)(moo 400)))))
(def flatten-animals (animals)
(accum save
(each xs animals
(each name-pop (cadr xs)
(save (cons (car xs) name-pop))))))
(def digest-tag-population (animals tags count)
(withs (pets-selected (keep [mem (car _) tags] animals)
pets-flat (flatten-animals pets-selected)
chosen (bestn count (compare > last) pets-flat))
(sort
(fn two (apply < (map [pos (car _) tags] two)))
chosen)))
Jarc> (digest-tag-population pets '(dog cat snake) 5)
> This one was too much fun for words in re how cool it is programming with
> Lisp. I would like to see this in Ruby, Clojure, Qi, and Scheme. The
> precise fun part tho is typing it all in in the final form versus dividing
> the thing up into steps to get intermediate results, ie, a test of one's
> mastery of one's language. Non-functional languages I guess have no choice
> but to stop and assign temporaries.
>
> Anyway, I have to stop encouraging my client, he specifies requirements
> like a woman ordering in a restaurant. Here goes:
>
> Given:
>
> (defparameter pets
> '((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
> (cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
> (snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
> (cow ((jersey 200)(heiffer 300)(moo 400)))))
>
> Write:
>
> (defun digest-tag-population (tag-population pick-tags count)...)
>
> Such that:
>
> (digest-tag-population pets '(dog cat snake) 5)
>
> => ((DOG CBRET 82) (DOG DOBER 42) (CAT RUSS 92) (CAT TIBET 52) (SNAKE
> PYTHON 77))
>
> ...the rules being:
>
> - consider only the populations of tags (the first symbol in each sublist)
> found in the parameter pick-tags, a list
>
> - take only the <count> most populous of the union of the populations
>
> - return (tag name population) of the most populous in this order:
>
> firstly, by position of the tag in pick-tags
> second, ie within a tag, in descending order of population
>
> Scroll waaaaaaaaay down for my code.
>
> Remember, you have to code this in one go.
>
> kt
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> (defun subseq-ex (st e s)
> (subseq s st (min e (length s))))
>
> (defun digest-tag-population (tag-population pick-tags count)
> (flet ((tagpos (tag) (position tag pick-tags)))
> (stable-sort (subseq-ex 0 count
> (sort (loop for (tag population) in tag-population
> when (tagpos tag)
> append (loop for pop in population
> collecting (list* tag pop)))
> '> :key (lambda (x)
> (caddr x))))
> '< :key (lambda (x) (tagpos (car x))))))
>
> (defparameter pets
> '((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
> (cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
> (snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
> (cow ((jersey 200)(heiffer 300)(moo 400)))))
>
> #+test
> (digest-tag-population pets '(dog cat snake) 5)
Ruby:
pets =
[[:dog, [[:blab, 12], [:glab, 17], [:cbret, 82], [:dober, 42],
[:gshep, 25]]],
[:cat, [[:pers, 22], [:siam, 7], [:tibet, 52], [:russ, 92],
[:meow, 35]]],
[:snake, [[:garter, 10], [:cobra, 37], [:python, 77],
[:adder, 24], [:rattle, 40]]],
[:cow, [[:jersey, 200], [:heiffer, 300], [:moo, 400]]]]
def flatten_pets pets
pets.map{|tag, list| list.map{|xs| [tag, xs].flatten}}.flatten(1)
end
def digest_tag_population animals, tags, count
pool = flatten_pets(
animals.select{|tag,list| tags.include?(tag)} )
chosen = pool.sort_by{|x| -x.last }.take( count )
chosen.sort_by{|tag,_,pop| [ tags.index(tag), -pop ]}
end
p digest_tag_population( pets, [:dog, :cat, :snake], 5)
==>
[[:dog, :cbret, 82], [:dog, :dober, 42], [:cat, :russ, 92],
[:cat, :tibet, 52], [:snake, :python, 77]]