Lisp newbie: deck of cards in Lisp

Hi everyone, I'm learning Lisp this year. I'm trying to learn it by writing a simple card game ( with the possibility of writing some AI to help me prepare for an AI course next semester.)

So, I'm very new to lisp and really don't have much idea what to do! I come from a java background so think in "things" but I don't want to write java in Lisp.

How do I go about making a deck of cards in lisp?

Thanks!

That is a very general question. Anyway, in case you had any misconceptions, Common Lisp is a multi-paradigm language, which include object oriented programming. It is just perhaps more "verb" centered, but there are classes and objects and things. You should probably read most, if you haven't already, of Practical Common Lisp before worrying about the particulars of your problem.

That said, the question should be not "how do I make a deck of cards", but what do you want to do with it? Representation of data should be chosen only after the protocol of using that data is chosen, and should be optimized for that use case. Not that there are that many possible representations of a deck of cards... a vector of symbols is the most likely simplest case.

titanium_geek wrote:How do I go about making a deck of cards in lisp?

In a room of N CL programmers, I would expect to get O(N*(N+1)/2) approaches.

Here's one.

(defun make-deck ()
  (let ((deck (make-array '(52)))
        (index 0))
    (dolist (suite '(:spades :hearts :diamonds :clubs))
      (loop for number from 2 upto 10
            do (setf (aref deck index) (cons number suite)
                     index (1+ index)))
      (dolist (face '(:jack :queen :king :ace))
        (setf (aref deck index) (cons face suite)
              index (1+ index))))
    deck))

titanium_geek wrote:I don't want to write java in Lisp.

Excellent!
Prepare to have your head turned around a bit when you get into CLOS (the Common Lisp Object System), because it's a total inversion from the Java approach.

titanium_geek wrote:How do I go about making a deck of cards in lisp?

Ramarren's question is probably the most apt: what do you want to do with the deck? This isn't a facetious question; it's useful for guiding you to the right implementation. At least, it'll guide you to a good starting implementation; one of the nice things about CL is how easy it is to re-prototype things.

Y'see, you could start by describing the cards as a bunch of lists contained within a list, define a few functions to operate on them, move them to a vector, turn them into objects, turn some of the functions into methods that are specialised on those objects, then move them back to a list because it's easier to shuffle them that way, then...

Personally, I'd probably start by defining them as classes with suit and rank slots, then think about what kind of operations I want to perform on them. Or maybe create a 4x13 array, and store state information in the resulting cells.

It's, um, an almost embarrassingly versatile little language you've started playing with, here

I guess I'm thinking too real world (like java).

I'm really hesitant about posting the whole problem because I have had a bad experience before where someone wrote the whole code for me, said "here" and killed all the joy in solving the problem. (I haven't learnt to learn well from code.)

So, no one write this for me!

I want to have a deck of cards, then deal out 5 cards to 4 players. You can't see your cards but you can see the other player's cards (the game is called reverse go fish) any pairs in your hand are taken out automatically as they appear. You take turns in asking: "do I have any x card" (you must ask something that you can see, obviously,) and if you do have that card, you get that added to your pairs pile. As you go you make sure you maintain 5 cards in your hands- this would be easy to automate.

The winner is the one with the most pairs at the end of the game. (a scoring system could also be used- correct guess/total guess, or something)

In the future I'd like to mess around with simple computer AI for this game as it's fairly simple, on the most basic level just guess something you can see.

Thanks!

nuntius wrote:

(defun make-deck ()
  (let ((deck (make-array '(52)))
        (index 0))
    (dolist (suite '(:spades :hearts :diamonds :clubs))
      (loop for number from 2 upto 10
            do (setf (aref deck index) (cons number suite)
                     index (1+ index)))
      (dolist (face '(:jack :queen :king :ace))
        (setf (aref deck index) (cons face suite)
              index (1+ index))))
    deck))

Fast hacking? Sounds fun

(defun shuffle (deck)
  (sort (copy-sequence 'vector deck)
        #'(lambda (x y)
            (declare (ignore x y))
            (zerop (random 2)))))

cl-user> (make-deck)
#((2 . :spades) (3 . :spades) (4 . :spades) (5 . :spades) (6 . :spades)
  (7 . :spades) (8 . :spades) (9 . :spades) (10 . :spades)
  (:jack . :spades) (:queen . :spades) (:king . :spades) (:ace . :spades)
  (2 . :hearts) (3 . :hearts) (4 . :hearts) (5 . :hearts) (6 . :hearts)
  (7 . :hearts) (8 . :hearts) (9 . :hearts) (10 . :hearts)
  (:jack . :hearts) (:queen . :hearts) (:king . :hearts) (:ace . :hearts)
  (2 . :diamonds) (3 . :diamonds) (4 . :diamonds) (5 . :diamonds)
  (6 . :diamonds) (7 . :diamonds) (8 . :diamonds) (9 . :diamonds)
  (10 . :diamonds) (:jack . :diamonds) (:queen . :diamonds)
  (:king . :diamonds) (:ace . :diamonds) (2 . :clubs) (3 . :clubs)
  (4 . :clubs) (5 . :clubs) (6 . :clubs) (7 . :clubs) (8 . :clubs)
  (9 . :clubs) (10 . :clubs) (:jack . :clubs) (:queen . :clubs)
  (:king . :clubs) (:ace . :clubs))
cl-user> (shuffle *)
#((7 . :hearts) (6 . :spades) (8 . :diamonds) (5 . :clubs) (9 . :diamonds)
  (10 . :spades) (10 . :diamonds) (4 . :diamonds) (9 . :spades)
  (8 . :hearts) (:king . :clubs) (:ace . :diamonds) (5 . :diamonds)
  (9 . :hearts) (2 . :clubs) (4 . :clubs) (6 . :hearts) (2 . :hearts)
  (10 . :hearts) (:king . :hearts) (5 . :hearts) (10 . :clubs)
  (:queen . :hearts) (7 . :diamonds) (:ace . :clubs) (8 . :clubs)
  (3 . :diamonds) (3 . :clubs) (:king . :diamonds) (4 . :hearts)
  (:queen . :diamonds) (4 . :spades) (3 . :hearts) (:queen . :clubs)
  (:jack . :diamonds) (3 . :spades) (6 . :diamonds) (2 . :spades)
  (:queen . :spades) (7 . :spades) (:ace . :spades) (:jack . :spades)
  (6 . :clubs) (7 . :clubs) (:jack . :hearts) (5 . :spades) (8 . :spades)
  (:jack . :clubs) (9 . :clubs) (:king . :spades) (:ace . :hearts)
  (2 . :diamonds))
cl-user> 

titanium_geek wrote:I guess I'm thinking too real world (like java).

Probably a mistake in Java too.

I don't think it much matters what representation you choose for this, although you'll probably be happier if you store the rank in a form that can be compared without a lot of fuss. The cons cell representation that Nuntius chose would be simple to work with, although for Go Fish it's not even necessary to store the suit unless you think they add flavor. A game this simple, I would just make the list: '(1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 'jack 'jack 'jack 'jack 'queen 'queen 'queen 'queen 'king 'king 'king 'king 'ace 'ace 'ace 'ace). I would make a function to generate it, although I can't justify that having just typed it here. Then I could just run through the game, writing a function to perform each needed step (shuffle, deal cards, move cards from hand to hand, and so on.

Good point about just number comparing being necessary, but I guess I'd like to write a proper gui for this eventually, so starting with a proper deck would be handy.

Thanks everyone, I can now see the next steps!

TG

Here is a basic framework (/ snippet of code):

http://rosettacode.org/wiki/Playing_cards#Common_Lisp

What I find a neat trick for shuffling is using a sort applicative operator with
a random function as key.

Destruct1 wrote:Here is a basic framework (/ snippet of code):

http://rosettacode.org/wiki/Playing_cards#Common_Lisp

What I find a neat trick for shuffling is using a sort applicative operator with
a random function as key.

That is what I did above

gugamilare wrote:

Destruct1 wrote:Here is a basic framework (/ snippet of code):

http://rosettacode.org/wiki/Playing_cards#Common_Lisp

What I find a neat trick for shuffling is using a sort applicative operator with
a random function as key.

That is what I did above

Good job

I am not sure if I remember correctly but I think there is another way which makes the sorting more comfortable.
Instead of passing a comparison lambda (lambda (x y) (which-is-greater-x-or-y)) there is a sorting algorythm that takes a "fitness
function" which maps any object/string to a numerical value and then sorts the list by their fitness integer.

Like this:
fitness function: (lambda (d) (return-a-numerical-value))
shuffle with fitness function: (mysterious-sort #'(lambda (d) (random)) cardlist)

Destruct1 wrote:Good job

Thanks!

Destruct1 wrote:I am not sure if I remember correctly but I think there is another way which makes the sorting more comfortable.
Instead of passing a comparison lambda (lambda (x y) (which-is-greater-x-or-y)) there is a sorting algorythm that takes a "fitness
function" which maps any object/string to a numerical value and then sorts the list by their fitness integer.

Like this:
fitness function: (lambda (d) (return-a-numerical-value))
shuffle with fitness function: (mysterious-sort #'(lambda (d) (random)) cardlist)

The problem would be sorting the same number twice. For instance, the position sorted for the 2 of spades would be the same that the position for the ace of clubs, then the algorithm would replace the 2 of spades by the ace of clubs, leaving the deck with no 2 of spades.

You could maintain a list with all possible position and remove the random elements from it:

(defun misterious-sort (pos-function vector)
  (let ((new-vector (copy-sequence 'vector vector))
        (size (length vector)))
    (dotimes (i size)
      (let ((elt (aref vector i)))
        (setf (aref new-vector (funcall pos-function i elt))
              elt)))
    new-vector))

(defun shuffle (deck)
  (let* ((size (length deck))
         (list-of-positions (loop for i from 0 below size
                               collect i)))
    (misterious-sort
     #'(lambda (old-pos elt)
         (declare (ignore old-pos elt))
         (let* ((aux (random (length list-of-positions)))
                (new-pos (elt list-of-positions aux)))
           (setf list-of-positions
                 (delete new-pos list-of-positions))
           new-pos))
     deck)))

It is more complicated and slower, it is O(n^2). A way to leave this faster would be to substitute the list with a binary tree, leaving the algorithm O(n logn). But the algorithm that uses sort is already O(n logn), so nothing faster will be obtained.

Can you think of an algorithm O(n)? I know can't.

gugamilare wrote:Can you think of an algorithm O(n)? I know can't.

To sort or to shuffle? Durstenfeld's variation of Fisher-Yates is O(n).
http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

nuntius wrote:

gugamilare wrote:Can you think of an algorithm O(n)? I know can't.

To sort or to shuffle? Durstenfeld's variation of Fisher-Yates is O(n).
http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Shame on me, it is just to maintain an array (instead of a list) and exchange the the sorted number with the last number of the array.

I meant something else:

;; first I take a list and a function and create a returnlist of the kind lst = ((x1 f(x1)) (x2 f(x2)) (x3 f(x3)) etc... )
(defun mapcarzip (func lst)
  (mapcar #'(lambda (d) (list d (funcall func d))) lst)

;; then I sort the list by the second number in each sublist (so by f(xi))
(defun sortsecondnum (tuplelist)
  (sort tuplelist #'(lambda (x y) (> (second x) (second y)))))

;; now I splice the first element of the list
(defun splicefirst (tuplelist)
  (mapcar #'(lambda (d) (first d)) tuplelist))

and here is mysterious sort:
(defun mysterious-sort (fitnessfunc lst)
  (splicefirst (sortsecondnum (mapcarzip fitnessfunc lst))))

I think this sort function is way more convinient than the compare x with y approach.

Some examples:

(mysterious-sort #'(lambda (d) (+ (first d) (second d))) '(examplelist))
sort the list ((x1 y1) (x2 y2) ...) by the sum of x and y

(mysterious-sort #'(lambda (d) (random 1000)) examplelist)
shuffles the list

(mysterious-sort #'(lambda (d) (slot-value 'priority)) classlist)
sort a list of classinstaces and put the one with the highest priority to the front of the list.

Destruct1 wrote:I think this sort function is way more convinient than the compare x with y approach.

Well, I get it, but, to be honest, I don't find it very convenient. You need to form the tuples, sort them and undo the tuples. The other version is faster and more intuitive. Not to mention that this one has a problem with collisions. Well, it is intuitive in my mind at least

Anyway, each person has its own way of thinking, so it may be different with you.

BTW, you can use :key to simplify the call to sort:

(defun sortsecondnum (tuplelist)
  (sort tuplelist #'> :key #'second))

gugamilare wrote:

Destruct1 wrote:I think this sort function is way more convinient than the compare x with y approach.

Well, I get it, but, to be honest, I don't find it very convenient. You need to form the tuples, sort them and undo the tuples. The other version is faster and more intuitive. Not to mention that this one has a problem with collisions. Well, it is intuitive in my mind at least

Anyway, each person has its own way of thinking, so it may be different with you.

I think it is at least a good alternative to the default. In Python the "sort with the compare method" has been removed after nobody could show a decent example why it needs to stay. Fitness functions are now the only way to sort.

The compare strtegy has several disadvantages:
a) You might get not transitive comparisions, like a>b and b>c and c>a. These are difficult to solve and I hate thinking about crap like that.
b) When two elements have the same function result the order is not easy to determine.But it doesnt matter. Simply say that the order of the original list will be preserved or that it is implementation specific (like in the Lisp Set functions). If you care enough as a programmer make sure your fitness function is unambigious.
c) I think it is slower. The computer is very efficient in comparing numerical values but a complex comparision function kills the sort algorythm. Even if you have a matrix which caches the compare (a,b) result, a NxN matrix is needed. With bubble sort you need the whole matrix filled and with merge sort a good part of it must be computed. The fitness function needs a O(n) mapcar and thats it.

Destruct1 wrote:I think it is at least a good alternative to the default. In Python the "sort with the compare method" has been removed after nobody could show a decent example why it needs to stay. Fitness functions are now the only way to sort.

The compare strtegy has several disadvantages:
a) You might get not transitive comparisions, like a>b and b>c and c>a. These are difficult to solve and I hate thinking about crap like that.
b) When two elements have the same function result the order is not easy to determine.But it doesnt matter. Simply say that the order of the original list will be preserved or that it is implementation specific (like in the Lisp Set functions). If you care enough as a programmer make sure your fitness function is unambigious.
c) I think it is slower. The computer is very efficient in comparing numerical values but a complex comparision function kills the sort algorythm. Even if you have a matrix which caches the compare (a,b) result, a NxN matrix is needed. With bubble sort you need the whole matrix filled and with merge sort a good part of it must be computed. The fitness function needs a O(n) mapcar and thats it.

a) In the case presented, that is not a problem. In other cases, the transitivity would be your concern as much as creating a good fitness function that preserves your ordering.
b) Note that in Common Lisp you need to use stable-sort to preserve the order of the original list. And, in the case presented, collisions are a problem because they make the shuffling less effective. They will be less of a problem if you use a big number in your random function, though.
c) Again, in the example given, this method will actually be slower, since it also needs a function to make the comparison, even if it is the function #'<. In Common Lisp's implementation, the only case where sorting with numbers is faster is to inline the sort function, maybe not even in that case. If you need a comparison function, you will probably need to create a good correspondence between you values and numbers, which would be tiresome, and its computation could consume more time than the sorting itself. Your method would also need to cons a list of tuples and restore the original list, which creates a lot of garbage.

In any case, I understand you point, you could gain little to lots of time of your sorting with a fitness function, but I still believe that in many cases it won't be faster. I'll make some tests here and see if I am right or not.