Patrick (patrickwonders) wrote,
Patrick
patrickwonders

  • Mood:

More Card Dealing Loops

This is a follow-on to a previous post.

Alice and Bob are playing a game described in The Math Factor podcast. Alice starts with some number of cards. She deals them out to Bob and herself one at a time until she is out of cards. If she got the last card, she is the next dealer. If Bob got the last card, Bob is the next dealer. The next dealer picks up the cards she or he has and deals them in the same manner. Play continues until one person has all of the cards.

In my previous post, I showed a diagram for all of the loops possible with 52 cards. This post shows all of the loops for anywhere from 2 to 100 cards. In my previous post, I showed rows that were basically mirrors of each other (swap Bob and Alice). In these pictures, I have eliminated this redundancy and the degenerate case where the dealer starts with no cards.

As a refresher, each row represents one loop. For nn cards the image is (nn + 1) squares wide. A blue square in column kk (counting columns starting at zero) means that at some point in that loop, Alice had kk cards and the deal. A red square in column kk means that at some point in that loop, Alice had kk cards but Bob had the deal. A yellow square in column kk means that twice during the loop, Alice had kk cards: once when she had the deal and once when Bob had the deal.

Two players with 2 cards loop image (Two players with 2 cards)
Two players with 3 cards loop image (Two players with 3 cards)
Two players with 4 cards loop image (Two players with 4 cards)
Two players with 5 cards loop image (Two players with 5 cards)
Two players with 6 cards loop image (Two players with 6 cards)
Two players with 7 cards loop image (Two players with 7 cards)
Two players with 8 cards loop image (Two players with 8 cards)
Two players with 9 cards loop image (Two players with 9 cards)
Two players with 10 cards loop image (Two players with 10 cards)
Two players with 11 cards loop image (Two players with 11 cards)
Two players with 12 cards loop image (Two players with 12 cards)
Two players with 13 cards loop image (Two players with 13 cards)
Two players with 14 cards loop image (Two players with 14 cards)
Two players with 15 cards loop image (Two players with 15 cards)
Two players with 16 cards loop image (Two players with 16 cards)
Two players with 17 cards loop image (Two players with 17 cards)
Two players with 18 cards loop image (Two players with 18 cards)
Two players with 19 cards loop image (Two players with 19 cards)
Two players with 20 cards loop image (Two players with 20 cards)
Two players with 21 cards loop image (Two players with 21 cards)
Two players with 22 cards loop image (Two players with 22 cards)
Two players with 23 cards loop image (Two players with 23 cards)
Two players with 24 cards loop image (Two players with 24 cards)
Two players with 25 cards loop image (Two players with 25 cards)
Two players with 26 cards loop image (Two players with 26 cards)
Two players with 27 cards loop image (Two players with 27 cards)
Two players with 28 cards loop image (Two players with 28 cards)
Two players with 29 cards loop image (Two players with 29 cards)
Two players with 30 cards loop image (Two players with 30 cards)
Two players with 31 cards loop image (Two players with 31 cards)
Two players with 32 cards loop image (Two players with 32 cards)
Two players with 33 cards loop image (Two players with 33 cards)
Two players with 34 cards loop image (Two players with 34 cards)
Two players with 35 cards loop image (Two players with 35 cards)
Two players with 36 cards loop image (Two players with 36 cards)
Two players with 37 cards loop image (Two players with 37 cards)
Two players with 38 cards loop image (Two players with 38 cards)
Two players with 39 cards loop image (Two players with 39 cards)
Two players with 40 cards loop image (Two players with 40 cards)
Two players with 41 cards loop image (Two players with 41 cards)
Two players with 42 cards loop image (Two players with 42 cards)
Two players with 43 cards loop image (Two players with 43 cards)
Two players with 44 cards loop image (Two players with 44 cards)
Two players with 45 cards loop image (Two players with 45 cards)
Two players with 46 cards loop image (Two players with 46 cards)
Two players with 47 cards loop image (Two players with 47 cards)
Two players with 48 cards loop image (Two players with 48 cards)
Two players with 49 cards loop image (Two players with 49 cards)
Two players with 50 cards loop image (Two players with 50 cards)
Two players with 51 cards loop image (Two players with 51 cards)
Two players with 52 cards loop image (Two players with 52 cards)
Two players with 53 cards loop image (Two players with 53 cards)
Two players with 54 cards loop image (Two players with 54 cards)
Two players with 55 cards loop image (Two players with 55 cards)
Two players with 56 cards loop image (Two players with 56 cards)
Two players with 57 cards loop image (Two players with 57 cards)
Two players with 58 cards loop image (Two players with 58 cards)
Two players with 59 cards loop image (Two players with 59 cards)
Two players with 60 cards loop image (Two players with 60 cards)
Two players with 61 cards loop image (Two players with 61 cards)
Two players with 62 cards loop image (Two players with 62 cards)
Two players with 63 cards loop image (Two players with 63 cards)
Two players with 64 cards loop image (Two players with 64 cards)
Two players with 65 cards loop image (Two players with 65 cards)
Two players with 66 cards loop image (Two players with 66 cards)
Two players with 67 cards loop image (Two players with 67 cards)
Two players with 68 cards loop image (Two players with 68 cards)
Two players with 69 cards loop image (Two players with 69 cards)
Two players with 70 cards loop image (Two players with 70 cards)
Two players with 71 cards loop image (Two players with 71 cards)
Two players with 72 cards loop image (Two players with 72 cards)
Two players with 73 cards loop image (Two players with 73 cards)
Two players with 74 cards loop image (Two players with 74 cards)
Two players with 75 cards loop image (Two players with 75 cards)
Two players with 76 cards loop image (Two players with 76 cards)
Two players with 77 cards loop image (Two players with 77 cards)
Two players with 78 cards loop image (Two players with 78 cards)
Two players with 79 cards loop image (Two players with 79 cards)
Two players with 80 cards loop image (Two players with 80 cards)
Two players with 81 cards loop image (Two players with 81 cards)
Two players with 82 cards loop image (Two players with 82 cards)
Two players with 83 cards loop image (Two players with 83 cards)
Two players with 84 cards loop image (Two players with 84 cards)
Two players with 85 cards loop image (Two players with 85 cards)
Two players with 86 cards loop image (Two players with 86 cards)
Two players with 87 cards loop image (Two players with 87 cards)
Two players with 88 cards loop image (Two players with 88 cards)
Two players with 89 cards loop image (Two players with 89 cards)
Two players with 90 cards loop image (Two players with 90 cards)
Two players with 91 cards loop image (Two players with 91 cards)
Two players with 92 cards loop image (Two players with 92 cards)
Two players with 93 cards loop image (Two players with 93 cards)
Two players with 94 cards loop image (Two players with 94 cards)
Two players with 95 cards loop image (Two players with 95 cards)
Two players with 96 cards loop image (Two players with 96 cards)
Two players with 97 cards loop image (Two players with 97 cards)
Two players with 98 cards loop image (Two players with 98 cards)
Two players with 99 cards loop image (Two players with 99 cards)
Two players with 100 cards loop image (Two players with 100 cards)

A state is totally defined by the number of cards Alice has along with who has the deal. With nn cards, there are 2 * nn possible states (not counting the two degenerate cases where the dealer has no cards). Some lines start with a red dot then have all yellow up to a final blue dot. Those lines hit every one of the 2 * nn states. I expected such cases to be isolated, but they occur at 5 & 6 cards 29 & 30 cards and at 89 & 90 cards.

I have much improved my code, and placed it on github. Most of the improvement comes from uniqing and sorting the lines and using xach's handy Vecto library to draw the images full-size directly to png with the grid lines and everything. I have a feeling Vecto will figure big in many future visualization tasks.

Any of you Lisp-ers out there, I felt like there must already be some way to lexicographically sort a sequence of sequences given a LESS-THAN function that compares elements of the sequences, but I couldn't find one. I ended up with this but would be pleased to hear other ideas on the matter:

(sort sequence-of-sequences-of-numbers
      (sequence-comparator #'< #'=))
(sort sequence-of-sequences-of-strings
      (sequence-comparator #'string-lessp #'string-equal))

(defun sequence-comparator (elt-less-than &optional elt-equal)
    "Given a ELT-LESS-THAN that compares elements of a sequence, compare the sequences lexicographically.  You can give an optional ELT-EQUAL or this function can forge one from the ELT-LESS-THAN."
    (let ((elt-equal (or elt-equal (equals-from-less-than elt-less-than))))
        #'(lambda (list1 list2)
            (let ((idx (mismatch list1 list2 :test elt-equal)))
                (cond
                    ((or (not idx) (>= idx (length list2))) nil)
                    ((>= idx (length list1)) t)
                    (t (funcall elt-less-than
                                (elt list1 idx)
                                (elt list2 idx))))))))

(defun equals-from-less-than (less-than)
    "Given a LESS-THAN comparison that totally orders some elements, make an equality operator that assumes two items are equal if neither is less than the other"
    #'(lambda (elt1 elt2)
            (not (or (funcall less-than elt1 elt2)
                     (funcall less-than elt2 elt1)))))
Tags: lisp, math
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments