C: A gentle introduction... find-if task(chapter 7) - find highest card in a hand

[Malice]

Hello,
I'm learning from book called "Common Lisp: A gentle introduction to symbolic computation".

It looks nice enough to me, however, there are exercises that don't have suggested answers, so I got to do them by myself. Most of the time, I'm doing fine, but this one is tough for me.

The chapter introduced a programming style called "applicative programming". Basically, I'm using mapcar, remove-if, remove-if-not, lambda, and seldom find-if and funcall(well, these were rather introduced then used). At the end of sub-chapter, there's an exercise with cards.

Each card is represented as 2-element list:
(rank suit), e.g. (2 hearts) or (ace spades)

There's an alist called *my-hand*:
((3 hearts)
(5 clubs)
(2 diamonds)
(4 diamonds)
(ace spades))
And there's a list called *all-ranks*
(2 3 4 5 6 7 8 9 10 jack queen king ace)

My task is to write a function HIGH-CARD, that will return the highest ranked card in a hand. Author included hint, which says: "One way to solve this is to use find-if to search a list of ranks(ordered from high to low) to find the highest rank that appears in the hand. Then use ASSOC on the hand to pick the card with that rank."
It also tells me about possibility of using REDUCE function, but it hasn't been introduced yet, so I'm not using it.

And my question is: how may I solve it with find-if and assoc? I can't find a way to do it with these functions. I'm asking, because I would like to know how to solve it using these applicative functions. I've found solution, but used sort and mapcard instead, but it looks... dirty to me:

(defun high-card (hand)
"Returns highest ranked card in a hand"
(nth
(-
(length *all-ranks*)
(first
(sort
(mapcar #'(lambda (e) (length (member (rank e) *all-ranks))) hand)
#'<)))
*all-ranks*))

Sorry if indentation is making it hard to read, I tried to make it as readable as possible.
Thought behind my function is that minding return value of member, I know that the lower length - the latter value. So I make list of lengths of each ranks(which turns out to be their place in list, when counting from back), and then sort them from lowest to highest. Then I pick lowest number, and look up corresponding value from *all-ranks* list(of course, going from back).

However, as I said, it looks a bit dirty to me, and I don't learn the functions described in chapter better. Could you please help me?

Useful functions that are available to use are:
(rank card) - return rank of card
(suit card) - return suit of card
(higher-rank-p card1 card2) - return T if first card has higher rank then the second(and NIL otherwise).

I hope I'm not expecting too much. It's not something that I won't live without, but I'd be glad to know how to solve it.
Sorry for the long post!

[Pascal J. Bourguignon]

Malice <gwma...@gmail.com> writes:

> Hello,

> I'm learning from book called "Common Lisp: A gentle introduction to
> symbolic computation".
>
> It looks nice enough to me, however, there are exercises that don't
> have suggested answers, so I got to do them by myself. Most of the
> time, I'm doing fine, but this one is tough for me.
>
> The chapter introduced a programming style called "applicative
> programming". Basically, I'm using mapcar, remove-if, remove-if-not,
> lambda, and seldom find-if and funcall(well, these were rather
> introduced then used). At the end of sub-chapter, there's an exercise
> with cards.
>
> Each card is represented as 2-element list:
> (rank suit), e.g. (2 hearts) or (ace spades)
>
> There's an alist called *my-hand*:

No, it's not a a-list. It's a list of lists of two elements.

> ((3 hearts)
> (5 clubs)
> (2 diamonds)
> (4 diamonds)
> (ace spades))

It's not an a-list because it's not a map and there's no key, and the
numbers can't be used as a key, since they're not unique:

((3 hearts) (3 clubs) (3 diamonds) (3 diamonds) (2 diamonds))

If it was an a-list, then this example would be equivalent to

((3 hearts) (2 diamonds))

A-list may contain several occurences of the same key, but the earliest
ones shadow the following ones.


Also, it's not a a-list, because it's a list of cards! The proof:

(defun cardp (object)
(and (consp object)
(consp (cdr object))
(null (cddr object))
(typep (car object) '(or (integer 2 10)
(member jack queen king ace)))
(member (cadr object) '(hearts clubs diamonds spades))
t))

(every 'cardp '((3 hearts)

(5 clubs)
(2 diamonds)
(4 diamonds)

(ace spades)))
--> t

> And there's a list called *all-ranks*
> (2 3 4 5 6 7 8 9 10 jack queen king ace)
>
> My task is to write a function HIGH-CARD, that will return the highest
> ranked card in a hand. Author included hint, which says: "One way to
> solve this is to use find-if to search a list of ranks(ordered from
> high to low) to find the highest rank that appears in the hand. Then
> use ASSOC on the hand to pick the card with that rank."
>
> It also tells me about possibility of using REDUCE function, but it
> hasn't been introduced yet, so I'm not using it.
>
> And my question is: how may I solve it with find-if and assoc? I can't
> find a way to do it with these functions. I'm asking, because I would
> like to know how to solve it using these applicative functions. I've
> found solution, but used sort and mapcard instead, but it
> looks... dirty to me:
>
> (defun high-card (hand)
> "Returns highest ranked card in a hand"
> (nth
> (-
> (length *all-ranks*)
> (first
> (sort
> (mapcar #'(lambda (e) (length (member (rank e) *all-ranks))) hand)
> #'<)))
> *all-ranks*))

Since there's a small fixed number of ranks and of cards in a hand, the
time complexity of this function is bounded: it's O(1).

However, if the number of ranks or cards could grow, it would display
very bad time complexity, with a lot of redundant work.

> Sorry if indentation is making it hard to read, I tried to make it as
> readable as possible.

Let emacs do that!

> Thought behind my function is that minding return value of member, I
> know that the lower length - the latter value. So I make list of
> lengths of each ranks(which turns out to be their place in list, when
> counting from back), and then sort them from lowest to highest. Then I
> pick lowest number, and look up corresponding value from *all-ranks*
> list(of course, going from back).

When you work with lists, do not try to compute indices and index into
list with them! Instead, see the double MEMBER call below.

> However, as I said, it looks a bit dirty to me, and I don't learn the
> functions described in chapter better. Could you please help me?
>
> Useful functions that are available to use are:
> (rank card) - return rank of card
> (suit card) - return suit of card
> (higher-rank-p card1 card2) - return T if first card has higher rank
> then the second(and NIL otherwise).
>
> I hope I'm not expecting too much. It's not something that I won't
> live without, but I'd be glad to know how to solve it.

(defun rank (card) (first card))
(defun suit (card) (second card))

(defun higher-rank-p (card1 card2)
(if (numberp (rank card1))
(if (numberp (rank card2))
(> (rank card1) (rank card2))
nil)
(if (numberp (rank card2))
t
(member (rank card1)
(rest (member (rank card2) '(jack queen king ace)))))))

(defun max-rank (card1 card2)
(if (higher-rank-p card1 card2)
card1
card2))

(defun high-card (hand)
(reduce (function max-rank) hand))


(high-card '((3 hearts)
(2 diamonds)
(2 clubs)
(5 diamonds)
(4 diamonds)))
--> (5 diamonds)

(high-card '((3 hearts)
(2 diamonds)
(queen clubs)
(5 diamonds)
(4 diamonds)))
--> (queen clubs)

(high-card '((queen hearts)
(jack diamonds)
(king clubs)
(5 diamonds)
(4 diamonds)))
--> (king clubs)



--
__Pascal Bourguignon__
http://www.informatimago.com/
"Le mercure monte ? C'est le moment d'acheter !"

[Malice]

Thanks for reply, which is insightful, but at the same time you came up with excellent answer, to all questions that I didn't ask - and no answer to question that I asked! That's something unusual :)

You're right about alist thing. I mapped alist in my memory to a picture of list of lists - but it isn't equal, as you showed.

Also, I'm really not concerning performance yet, because, following Knuth -
"Premature optimization is the root of all evil"; I shouldn't really optimize my programs(apart from making obviously bad bad functions), if I don't know the language itself.

This said, your function would be valid if I asked for it later. You can see that I said:

> It also tells me about possibility of using REDUCE function, but it
> hasn't been introduced yet, so I'm not using it.

It may be unclear, but what I meant was that I *don't want* to use it - because right now, I want to focus on learning how to do it with remove-if and assoc.

And I asked the same question on #lisp @ freenode. User jasom(if you're reading this - thanks again!) guided me to the proper answer. This is what I came up with:

(defun high-card (hand)
(assoc
(find-if #'(lambda (e) (assoc e hand)) (reverse *all-ranks*))
hand))

If anyone will face the same problem, I hope this answer will help him.

And thanks again, Pascal - while your post didn't answer my question, it provided useful insight on problem.

[Pascal J. Bourguignon]

Malice <gwma...@gmail.com> writes:

> Thanks for reply, which is insightful, but at the same time you came
> up with excellent answer, to all questions that I didn't ask - and no
> answer to question that I asked! That's something unusual :)
>
> You're right about alist thing. I mapped alist in my memory to a
> picture of list of lists - but it isn't equal, as you showed.
>
> Also, I'm really not concerning performance yet, because, following
> Knuth - "Premature optimization is the root of all evil"; I shouldn't
> really optimize my programs(apart from making obviously bad bad
> functions), if I don't know the language itself.
>
> This said, your function would be valid if I asked for it later. You
> can see that I said:
>
>> It also tells me about possibility of using REDUCE function, but it
>> hasn't been introduced yet, so I'm not using it.
>
> It may be unclear, but what I meant was that I *don't want* to use it
> - because right now, I want to focus on learning how to do it with
> remove-if and assoc.

I understand, but remove-if and assoc are NOT the functions to use to
implement this function.


Oh, right you can use them because as soon as you have one conditional
loop, you have turing equivalence. But that doesn't mean they're the
right tool to use.




For example, once upon a time, I had a system programming teacher who
bet with us we couldn't write a program in less of 30 lines to sum an
array of 1000 elements after having introduced us a few ASM-360
instructions, but not indexed addressing. We obviously found a
solution, by using the vector as a circular buffer, and summing the
first element.

--------------------------------------------------------------------------------
;; PROGRAMME : ADDITION DE MILLE NOMBRES
;; PROGRAMMEUR : BOURGUIGNON
;; DATE: 28 MARS 1983
;; D'APRES L'IDEE DE DELANNOY

NBR DS 1000PL2
TEMP DS PL2 TEMP EST PLACE OBLIGATOIREMENT JUSTE DERRIERE NBR.
SOM DC PL5'0' ON FAIT APPEL A UNE FILE FIFO DONT
TOT DC PL3'0' LES ELEMENTS SE DEPLACERONT.
APACHE AP SOM,NBR ON ADDITIONNE LE 1ER NOMBRE DE LA FILE
MVC TEMP,NBR ET ON LE PLACE A L'ENTREE DE LA FILE.
MVC NBR(256),NBR+L'NBR ON DECALE TOUS LES ELEMENTS
MVC NBR+256(256),NBR+256+L'NBR DE LA FILE PAR BLOCS DE 256 OCTETS,
MVC NBR+512(256),NBR+512+L'NBR SOIT 128 ELEMENTS VERS LA SORTIE.
MVC NBR+768(256),NBR+768+L'NBR
MVC NBR+1024(256),NBR+1024+L'NBR L'EX-PREMIER ELEMENT ETANT A
MVC NBR+1280(256),NBR+1280+L'NBR L'ENTREE, IL EST REINTEGRE A
MVC NBR+1536(256),NBR+1536+L'NBR LA FILE ET REPRENDRA SA PLACE
MVC NBR+1792(208),NBR+1792+L'NBR INITIALE AU BOUT DE 1000 ITERATIONS.
AP TOT,=P'1'
CLC TOT,=P'1000'
BC 7,APACHE
LA SORTIE DE LA FILE EST LA ZONE ADRESSEE
PAR NBR, L'ENTREE CELLE ADRESSEE PAR TEMP.
--------------------------------------------------------------------------------
(this earned us a bottle of Champagne).


In lisp that would be:

(defun sum-thousand (v)
(check-type v (vector * 1000))
(let ((temp)
(sum 0))
(loop repeat 1000
do (setf temp (aref v 0))
(incf sum temp)
(replace v v :start1 0 :start2 1)
(setf (aref v 999) temp))
sum))

(sum-thousand (coerce (iota 1000) 'vector))
--> 499500
(* 500 999)
--> 499500


But of course, it's not because it's possible to write it like that (and
you can also prove that it's correct, happy Pr. Knuth), that you should
write it like that. You can do it for the intellectual gymanistic, the
puzzle solving, but you should at the same time also go beyond the
exercise, and go find the right tool for the job, and implement it
correctly.


Which in lisp would be something like:
(defun sum-thousand (v) (reduce (function +) v))

and in assembler would involve indexed addressing.

> And I asked the same question on #lisp @ freenode. User jasom(if
> you're reading this - thanks again!) guided me to the proper
> answer. This is what I came up with:
>
> (defun high-card (hand)
> (assoc
> (find-if #'(lambda (e) (assoc e hand)) (reverse *all-ranks*))
> hand))


> If anyone will face the same problem, I hope this answer will help
> him.
>
> And thanks again, Pascal - while your post didn't answer my question,
> it provided useful insight on problem.

[tar...@google.com]

On Monday, April 14, 2014 1:47:55 PM UTC-7, Malice wrote:
| (defun high-card (hand)
| (assoc
| (find-if #'(lambda (e) (assoc e hand)) (reverse *all-ranks*))
| hand))

I you wanted to get fancy, you could replace

(find-if #'(lambda (e) (assoc e hand)) (reverse *all-ranks*))

with
(find-if #'(lambda (e) (assoc e hand)) *all-ranks* :from-end t)
to make it search the list backwards.

Also, you might find that (position rank *all-ranks*) could be useful...

If you want another solution using your given data structures, consider:

(defun rank (card) (first card))
(defun suit (card) (second card))

(defun numeric-rank (card) (position (rank card) *all-ranks*))

(defun high-card (hand)
(assoc (nth (apply #'max (mapcar #'numeric-rank hand))
*all-ranks*)
hand))

OK, the use of NTH is a bit distasteful, but I'll go with it for this.
You could also substitute (reduce #'max ...) for (apply #'max ...)

This also will fail if HAND is empty, but it would be easy to add a check for that and return nil.

[Malice]

On Monday, 14 April 2014 23:59:15 UTC+2, informatimago wrote:


> Oh, right you can use them because as soon as you have one conditional
>
> loop, you have turing equivalence. But that doesn't mean they're the
>
> right tool to use.

> You can do it for the intellectual gymanistic, the
>
> puzzle solving, but you should at the same time also go beyond the
>
> exercise, and go find the right tool for the job, and implement it
>
> correctly.

I didn't ask because I wanted to get the best algorithm for finding highest card in hand. It was an exercise that I couldn't do - which made me feel bad, and I wanted to know how I can do it. I do realize, that it may be not the best way to make this function, but I wanted to know *how* make this function using these tools, rather then how to make this function at all - because, as I explained in OP, I already made other version of this function that works fine.

And I disagree with "finding right tool for the job" when learning - I'm not aware of many things in CL yet - it would be pointless to roam from one thing to another, just to implement some algorithms efficiently. The book is written so that it creates one closed logical composition, and while I can learn from more than one book at the same time, I'd like to follow book's flow instead of searching through all functions, because I think something isn't done in the way it should be. I haven't worked with CL, so instead of wasting time to find some functions - part of which I will likely forget, I follow the book. I will find time to re implement these badly designed functions later.

[Aditya Raj Bhatt]

Well said! I have faced this problem myself too, many times. But I choose to blinker myself temporarily and just _follow the book_, since the author must have had a certain progression in which he wants us to learn the content.

[Nicolas Neuss]

Malice <gwma...@gmail.com> writes:

> [...]

> And I disagree with "finding right tool for the job" when learning -
> I'm not aware of many things in CL yet - it would be pointless to roam
> from one thing to another, just to implement some algorithms
> efficiently. The book is written so that it creates one closed logical
> composition, and while I can learn from more than one book at the same
> time, I'd like to follow book's flow instead of searching through all
> functions, because I think something isn't done in the way it should
> be. I haven't worked with CL, so instead of wasting time to find some
> functions - part of which I will likely forget, I follow the book. I
> will find time to re implement these badly designed functions later.

IMO, it highly depends on the quality of the book, if your approach is a
good one.

A good book will pose questions/exercises so that they can be solved in
an appropriate way with the tools already presented. And if this is so,
your approach usually will not be too far away from Pascal's answers.

A bad book, on the other hand, could ask the solution of exercises with
inappropriate means at hand. For some students, this may lead to
distaste of the language which is taught, for others it may lead to a
bad programming style in the future. [OK, there might also be some
students for which this approach might lead to good results, but I would
not bet on that.]

Nicolas

[Curt]

On 2014-04-16, Nicolas Neuss <last...@scipolis.de> wrote:
>
> IMO, it highly depends on the quality of the book, if your approach is a
> good one.

We know which book he's reading.

> A good book will pose questions/exercises so that they can be solved in
> an appropriate way with the tools already presented. And if this is so,
> your approach usually will not be too far away from Pascal's answers.
>
> A bad book, on the other hand, could ask the solution of exercises with
> inappropriate means at hand. For some students, this may lead to
> distaste of the language which is taught, for others it may lead to a
> bad programming style in the future. [OK, there might also be some
> students for which this approach might lead to good results, but I would
> not bet on that.]

So is "Common Lisp: A Gentle Introduction to Symbolic Programming"
a good or a bad book according to your criteria?

[Barry Margolin]

In article <slrnll074p...@einstein.electron.org>,

Curt <cu...@free.fr> wrote:

> On 2014-04-16, Nicolas Neuss <last...@scipolis.de> wrote:
> >
> > IMO, it highly depends on the quality of the book, if your approach is a
> > good one.
>
> We know which book he's reading.

Based on the subject line, it's a book about C.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[Nicolas Neuss]

I don't know it sufficiently well, but my first impression was that it
is much too verbose/gentle. YMMV.

Nicolas

[WJ]

Malice wrote:

> There's an alist called *my-hand*:
> ((3 hearts)
> (5 clubs)
> (2 diamonds)
> (4 diamonds)
> (ace spades))
> And there's a list called *all-ranks*
> (2 3 4 5 6 7 8 9 10 jack queen king ace)
>
> My task is to write a function HIGH-CARD, that will return
> the highest ranked card in a hand.

MatzLisp (Ruby):

ranking = (2..10).to_a + [:jack, :queen, :king, :ace]

hand = [[3, :hearts],
[5, :clubs],
[2, :diamonds],
[4, :diamonds],
[:ace, :spades]]

hand.max_by{|rank,suit| ranking.index( rank )}
==>[:ace, :spades]

[Alexander Skobelev]

Well, I'm not sure about find-if, but you can use MAPC:

(defparameter *hand* '((3 hearts)

(5 clubs)
(2 diamonds)
(4 diamonds)

(ace spades)))

(defparameter *ranks* '(2 3 4 5 6 7 8 9 10 jack queen king ace))

(let (max-card max-card-pos)

(mapc #'(lambda (x)
(let ((x-pos (position (car x) *ranking*)))
(if (or (not max-card)
(>= x-pos max-card-pos))
(setf max-card x
max-card-pos x-pos))))
*hand*)
max-card)

or REDUCE:

(reduce #'(lambda (x y)
(if (>= (position (car x) *ranks*)
(position (car y) *ranks*))
x y))
(cdr *hand*) :initial-value (car *hand*))

[WJ]

Gauche Scheme:

(use gauche.collection)

(define *all-ranks* (reverse '(2 3 4 5 6 7 8 9 10 jack queen king ace)))

(define (less . cards)
(apply < (map (^c (length (member (car c) *all-ranks*))) cards)))

(define (high-card cards)
(find-max cards :compare less))