#+title: beginner j : dealing cards

* init
: @cls

@hide("jp-editor")

@show("jp-editor")

@move("jp-editor", 38, 570, 400)

@move("jp-editor", 38, 1080, 400)

: NB. kludge to move the cursor to the bottom of the repl.

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

: 

@pause(5000)


* the deck
: @cls

@title("the deck")

Let's say you want to deal some cards.

A standard deck has four suits: clubs, diamonds, hearts, and spades.

: . ?suits =: 'cdhs'?

: suits =: 'cdhs'

Then there are thirteen ranks: deuce through ten, jack, queen, king, and Ace.

: . ?ranks =: '1?X?23456789T?_?JQKA'?

: ranks =: '23456789TJQKA'

We can use the catalog operator (that's the left curly brace here) to see every combination:

: . ?|: ?_?{?_? ranks;?_? suits?

: |: { ranks; suits

The semicolon there puts the two strings into boxes,

: . ^bbbbXXXXX$

: ranks; suits

Then catalog takes every combination of the boxed values.

: . ^bb?{ ?

: { ranks; suits

Then transpose turns that on it side just to make it look nicer.

: . ^ bbb?|: ?

: |: { ranks; suits

Okay, so let's convert those boxed strings to symbols...

: . ^0?s: ?

: s: |: { ranks; suits

... flatten it with ravel ...

: . ^0?, ?$

: , s: |: { ranks; suits

and then give it a name:

: . ^0?by_suit =: ?$

: by_suit =: , s: |: { ranks; suits

: . ?by_suit?

: by_suit

If you'd prefer to have it sorted by rank instead of by suit, just remove the transpose:

: . ^^bb0>>>xxxx?rank?www>xxx$

: by_rank =: , s: { ranks ; suits

: . ?by_rank?

: by_rank

Anyway, let's call that our deck.

: . ^0?deck =: ?

: deck =: by_rank

@sync

* enumeration
: @cls

@title("enumeration")

If we did that right, we'd expect to have 52 cards:

The hash operator gives us the length of an array.

: . ?# deck?

: # deck

So that looks good.

We can grab the first four cards with "take" or left-curly dot.

: . ^0x?4 {.?$

: 4 {. deck

Since the deck is sorted by rank, that gives us the twos, or "deuces".

If we want the aces, we can deal from the bottom of the deck.

: . ^0?_?

: _4 {. deck     NB. _4 is negative four

If we want to know what card is card number 23 is, we can just extract it.

: . ?23 { deck?

: 23 { deck

Array indices start at zero, so that deuce of clubs up there is card zero, and the ace of spades is 51.

: . ^0xx?0 51?

: 0 51 { deck

J complains if you ask for an entry that's out of range.

: . ^0xx>x?2?

: 52 { deck

You can ask for negative one through negative 52 though.

: . ^0?_1 _?w

: _1 _52 { deck

@pause(750)

@sync

* card lookup
: @cls

@title("card lookup")

So now we can map numbers to cards. But what if we want to go the other way?

Let's say we want to find the queen of hearts:

: . ?'Qh'?

: 'Qh'

This here is a string, but our deck is actually an array of symbols.

We can't match strings and symbols directly, so we need a symbol.

Unfortunately, J doesn't have a syntax for writing symbols.

But they're still pretty easy to construct.

We can either use less than to box the string,

: . ^0?<?

: <'Qh'

and then pass that to s-colon...

: . ^0?s:?

: s:<'Qh'

Or we can put an extra character at the start of the string and forget the boxing:

: . ^0>>x>? ?

: s:' Qh'

That extra space is called a fret character, and it acts like a delimiter for defining multiple symbols at once.

: . ^$<? As 3d?

: s:' Qh As 3d'    NB. ' ' as fret

... And it doesn't have to be a space. You can use anything.

: . ^0wx?.?wx?.?wx?.?wwwwwwx?.?

: s:'.Qh.As.3d'    NB. '.' as fret

Anyway, now we have the symbols, so we can use i-dot to find them in the deck:

: . ^^bbbbbbbbK0?deck i. ?

: deck i. s:' Qh As 3d'

So it found all three cards, and if we extract those indices, those are the cards we should get.

: . ?42 51 5 { deck?

: 42 51 5 { deck

You might ask why bother with symbols instead of sticking with strings, or boxed strings.

Boxed strings and symbols are about the same:

: . ?(,{ranks;suits)i.<'Qh'?

: (,{ranks;suits)i.<'Qh'

Although you might wind up doing a little more typing with boxes.

: . ^<<<<X? ?$?;'As';'3d'?

: (,{ranks;suits)i. 'Qh';'As';'3d'

You don't normally have an array of unboxed strings in J, because the arrays have to rectangular.

which means your strings would all have to be the same length.

In this particular case, our strings are all two characters long,

: . ^b<<K0$X0x

: ,{ranks;suits

so we could have modeled the deck as a fifty-two-by-two character array:

: . ^0?>?

: >,{ranks;suits

: . ^0?(?$?) i. ?__?>'Qh';"?X?'?As';'?

: (>,{ranks;suits) i. >'Qh';'As';'3d'

I guess really I just kinda prefer symbols, so that's what I went with.

@sync

* shuffling
: @cls

@title("shuffling")

Okay, so if you want to pick a random number in J, use the question mark.

: . ??? 52?

: ? 52

Of course, you'll get a different number each time:

: . ^

: ? 52

: . ^

: ? 52

There is also question mark dot that uses a fixed seed for the random number generator,
 but I'm not going to mess with that here.

: . ^b?.?

: ?. 52   NB. ?. uses a fixed seed

: . ^b?.?

: ?. 52

: . ^

: ?. 52

Okay, so given a random card number we can extract the card with from.

: . ^0>x<?(?$?) { deck?

: (? 52) { deck

We need parentheses here because J executes right to left.

It's actually a bit shorter to use tilde on the from operator, and swap the arguments:

: . ^^0?deck {~ ?

: deck {~ ? 52

So that's dealing one random card.

If we add a number to the left of the question mark, we can deal as many cards as we like:

: . ^^^0?5 ?

: 5 ? 52

This dyadic form of the question mark is called "deal", and it guarantees we won't get any duplicates.

So if we say 5 deal 5, you can see that all of the values are unique.

: . ^$X

: 5 ? 5

If you wanted to allow duplicates, you could use the monadic form, and pass the more than one number in on the right.

So for example, 5 copy 5 gives us five fives.

: . ?5 # 5?

: 5 # 5

The monadic form of the question mark is called "roll", and in this case it would be like rolling five five sided dice.

: . ^0??? ?

: ? 5 # 5

But for cards, we pretty much always want "deal" instead of "roll" and so we will use the dyadic form.

So here are five random card numbers.

: . ?5 ?? 52?

: 5 ? 52

And here are five random cards.

: . ^0?deck {~ ?

: deck {~ 5 ? 52

(Remember they're random every time so the numbers and the cards don't match.)

: . ^

: deck {~ 5 ? 52

Finally if we want to shuffle the whole deck, we can just deal all 52 cards.

: . ^$2

: deck {~ 52 ? 52

Notice that we're passing in 52 on both sides of the question mark.

We can simplify that a bit.

: . ^bbXXx>?~?

: deck {~ ?~ 52

Whenever you want to pass the same argument to both sides of a verb, you can use a tilde:

So that means the same thing.

To recap, the tilde on the question mark makes it reflexive, so we're still passing in 52 on both sides.

The tilde on the curly brace is swapping the arguments,

so that we don't have to put parentheses around everything.

The difference is that the question mark only has an argument on the right hand side,

whereas the curly brace has an argument on both sides.

The deck is on the left and the shuffled indices are on the right.

So reading right to left, it says

deal 52 numbers from a set of 52 numbers

then extract the cards in those positions from the deck.

Anyway, if I were going to write a function to deal cards,

it would probably look something like this.

: . ^0?deal =: {{ ?$? }}?bb<x<?y ?

: deal =: {{ deck {~ y ? 52 }}

: . ?deal 5 ?

: deal 5 NB. a random poker hand

And again to shuffle the whole deck, just deal 52 cards.

: . ?shuffle =: deal @ 52?

: shuffle =: deal @ 52

: . ?shuffle''?

: shuffle''

@pause(1500)

@sync

* permutations
: @cls

@title("permutations")

There /is/ at least one other way to think about shuffling in J.

If you're going to arrange a deck of cards in some order...

Well, you have 52 possible choices for the first card, 51 for the second, and so on.

: . ?1+i.52?0?|.?

: |.1+i.52

And then when you get to the last card, you have one possibility left.

So if you multiply all those numbers together:

: . ^0?*/?

: */|.1+i.52

... then that's how many different possible ways there are to arrange the cards.

You may recall learning at some point that this is called the factorial function.

In math notation you'd write that as 52 exclamation point,
 and in J, you write exclamation point 52:

: . ?52!?_____________________________X<<?!?

: !52

That's about eight times ten to the 67th power.

If you wrote it out longhand, it would look like this:

: . ^?x?

: !52x

The x at the end makes J use extendend precision integers so you get the exact value.

And then it just happens to format those without scientific notation by default.

Anyway this is how many permutations there are for a deck of cards.

And the idea is that instead of making a sequence of 52 random choices to shuffle the deck...

We could just say that there are 52 factorial "shufflings" out there in the universe,

and we're going to pick /one of them/ at random.

: . ^0??

: ?!52x

: . ^

: ?!52x

: . ^

: ?!52x

Of course, /now/ we need some way to take one of these numbers

and map it to an actual arrangement.

It turns out that J has a primitive that does exactly that.

@sync

* permutation table
: @cls

@title("permutation table")

Imagine we had a table of all the permutations.

: . ?t =. (A.~i.@!@#) 'ABCD'?

: t =. (A.~i.@!@#) 'ABCD'

Don't worry about what this means yet.

We're just defining a table called 't'

: . ?t?

: t

where each row is a permutation of the string 'ABCD'.

That's four letters, so there should be four factorial permutations:

Four factorial is 24, and there are 24 rows in the table.

: . ?!4?

: !4

: . ?#t?

: #t

It's a little hard to read so let's format it a bit:

: . ?<@,."1 t?

: <@,."1 t

So that's itemizing and then boxing each row to make it vertical.

So each column in this picture corresponds to a row in t.

You can kind of see there's a pattern there.

Row 0 is the original string.

: . ?t{~0?

: t{~0

And then it swaps the last two characters.

: . ^X?1?

: t{~1

And then it moves the C towards the front.

: . ^X?2?

: t{~2

And then swaps the last two characters again.

: . ^X?3?

: t{~3

When it gets to the very last permutation, it's the reverse of the original string.

: . ^X?_1?

: t{~_1

And the one before that is reversed except for the last two letters.

: . ^X?2?

: t{~_2

So there's a definite pattern here.

It's not actually that hard to generate all the permutations of a list this way.

I've been known to give this as an interview question.

I like it because it seems a little daunting at first,

but once I get the person talking about how they would do this by hand,

they can usually put a recursive solution into words within a few minutes.

Then it's just a matter of whether they can express the idea in code.

So, I won't spoil the algorithm here. I'll leave it as a challenge for you.

: . ?t {~ 0 _1?

: t {~ 0 _1

Meanwhile, if we want a particular permutation in J...

: . ^0x?'ABCD'?>x?A.?

: 'ABCD' A.~ 0 _1

... we can use capital A-dot to generate that permutation on demand.

The "A" is for anagram.

@sync

* anagrams
: @cls

@title("anagrams")

Let's take another look at how we defined t:

: . ^^^^^^^^^^^^^^

: t =. (A.~i.@!@#) 'ABCD'

This part in parentheses is a hook made of two verbs.

: . ^0ww>>>>>? ?

: t =. (A.~ i.@!@#) 'ABCD'

A monadic hook is just another way to copy the right argument over to the left,

so if we expand the hook it looks like this.

: . ^0ww? 'ABCD'?>xwwX$

: t =. 'ABCD' A.~ i.@!@# 'ABCD'

@pause(1000)

And the tilde is swapping the arguments, so we can expand that:

: . ^0ww? (i.@!@#?w?)?wX>xxxxxxx$

: t =. (i.@!@# 'ABCD') A. 'ABCD'

@pause(1000)

And now on the left we have the at signs composing three verbs together into a pipeline.

But 'ABCD' is a noun and when you have a sequence of verbs applied directly to a noun,
they form a pipeline anyway, so we can get rid of the at signs.

: . ^0www<<x<<x

: t =. (i.!# 'ABCD') A. 'ABCD'

So let's ignore the call to A-dot and just look at the part on the left.

: . ^bb<K0xxxxxx

: i.!# 'ABCD'

It says count to the factorial of the length of this string.

: . ^^0xxxxx>xxxxxxxxxxx?0 1 2 . . . ?XXXXXX?22 23

: (0 1 2 22 23) A. 'ABCD'

So anagram takes some numbers on the left and a sequence on the right, and returns the permutation corresponding to that number.

: . ^0xwwwxxxxxxx

: 0 1 2 A. 'ABCD'

It also takes the length of the sequence into account:

: . ^<?E?

: 0 1 2 A. 'ABCDE'

So we can pass it a sequence of any length.

: . ^<?FGH?

: 0 1 2 A. 'ABCDEFGH'

Anagram acts like it's pullling rows out of the table of permutations,

but it doesn't have to actually construct the table.

That's important, because generating the permutation table for a deck of cards
 would pretty much take forever.

: . ^bK? deck?

: 0 1 2 A. deck

: . ?!52x?

: !52x

And yet, with the anagram primitive, we can just pretend that we have that
 table, and ask J for any row we want.

So, we should expect that anagram 0 gives us the original deck:

: . ?deck -: deck A.~ 0?

: deck -: deck A.~ 0   NB. -: tests for match

and this giant number ...

: . ^^

: !52x

... minus one ...

: . ^0?<:?

: <:!52x   NB. <:n is n-1

... should give us the deck in reverse.

: . ?(|.deck) -: deck A.~ ?

: (|.deck) -: deck A.~ <:!52x

If we wanted the cards sorted by suit, there's a number for that.

It's not at all obvious to me how to /derive/ that number,

but if we can show J what we're looking for,

: . ?deck i. by_suit?

: deck i. by_suit

Then the monadic form of A-dot
(called anagram index)

: . ^0?A. ?

: A. deck i. by_suit   NB. A. y is 'anagram index'

can tell us where it is in the table.

: . ^0?p =. ?

: p =. A. deck i. by_suit

: . ?by_suit -: deck A.~ p?

: by_suit -: deck A.~ p

And of course to bring this back where we started,
 if we want to shuffle the deck, we 
can just extract a permutation from the table at random.

: . ?deck A.~ ?? ?!52x?

: deck A.~ ? !52x   NB. random permutation

: . ^bbbbbK

: deck A.~ ? !52x

: . ^

: deck A.~ ? !52x

@pause(500)

: . ^0?shuffle2 =: {{ ?$?}}?

: shuffle2 =: {{ deck A.~ ? !52x }}

@pause(2000)

* the end
#+begin_src j
suits =: 'cdhs'
ranks =: '23456789TJQKA'
by_suit =: , s: |: { ranks ; suits
by_rank =: , s: { ranks ; suits
deck =: by_rank
deal =: {{ deck {~ y ? 52 }}
shuffle =: deal @ 52
shuffle2 =: {{ deck A.~ ? !52x }}

#+end_src

: @cls

@editor_goxy(0, 8)

@move("jp-editor", 38, 570, 400)

@editor_goxy(0, 8)

So that's dealing cards in J!

If you enjoyed this, please do hit the like button and let youtube know.

Either way, thank you for watching, and I hope to see you again soon.

@title("thanks for watching!")