{"id":2537,"date":"2017-06-08T00:01:31","date_gmt":"2017-06-08T07:01:31","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=2537"},"modified":"2017-06-10T07:39:05","modified_gmt":"2017-06-10T14:39:05","slug":"the-perfect-shuffle-solution","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=2537","title":{"rendered":"The Perfect Shuffle – Solution"},"content":{"rendered":"

A perfect shuffle splits a deck of cards in two. The second half is folded evenly into the first half, so that every other card comes from the first and last half of the deck, respectively. This type of shuffle is practically impossible in real life, but for a computer simulation it’s not that difficult.
\n
\nProgrammers use an array to simulate a deck of cards. You could craft a multidimensional array to represent the 13 cards of the 4 suits, though most game programmers use a 52-element int<\/em> array for the deck. They simulate the cards and suits when the array is output.<\/p>\n

Rather than go through a 52-card simulation for this month’s Exercise<\/a>, I tasked you to perfectly shuffle the letters in the alphabet, A to Z, which is a 26-element char<\/em> array. A single shuffle()<\/em> function can do the job, but you must also count how many shuffles are required to restore the array to its original order. Therefore, two tasks are in order.<\/p>\n

For my solution, I wrote the shuffle()<\/em> function first. Its job is to split the deck in two, then rebuild the deck by alternating cards from the first half and second half. Here is my solution, which — warning — uses both array and pointer notation.<\/p>\n

\r\nvoid shuffle(char *deck)\r\n{\r\n    char left[HALFDECK];\r\n    char right[HALFDECK];\r\n    int x;\r\n\r\n    \/* split the deck *\/<\/span>\r\n    for(x=0;x<HALFDECK;x++)\r\n    {\r\n        left[x] = *(deck+x);\r\n        right[x] = *(deck+HALFDECK+x);\r\n    }\r\n\r\n    \/* shuffle *\/<\/span>\r\n    for(x=0;x<HALFDECK;x++)\r\n    {\r\n        *(deck+(x*2)) = left[x];\r\n        *(deck+(x*2)+1) = right[x];\r\n    }\r\n}<\/pre>\n
The char<\/em> pointer variable deck<\/code> is the alphabet or deck of cards. Arrays left[]<\/code> and right[]<\/code> are the two halves that must be shuffled together.<\/p>\n
The first step is to copy the upper and lower parts of the deck to the two arrays. The initial for<\/em> loop does that, using the constant HALFDECK<\/code> to set the offset for the upper half of the deck\/array.<\/p>\n
After the left[]<\/code> and right[]<\/code> arrays are filled, the second step is to rebuild the deck<\/code> array by alternating characters from left[]<\/code> and right[]<\/code>. The second for<\/em> loop accomplishes this task by using its looping variable x<\/code> as an offset. Variable x<\/code> needs to increment only to the HALFDECK<\/code> size because it fetches two cards at once:<\/p>\n
(x*2)<\/code> inserts cards from the left[]<\/code> half of the deck into even positions.<\/p>\n
(x*2)+1<\/code> inserts cards from the right[]<\/code> half of the deck into odd positions.<\/p>\n
The end result is that the alphabet goes from this:<\/p>\n
ABCDEFGHIJKLMNOPQRSTUVWXYZ<\/code><\/p>\n
To this:<\/p>\n
ANBOCPDQERFSGTHUIVJWKXLYMZ<\/code><\/p>\n
The Exercise’s solution also involves counting shuffles until the string returns to its original state. To do that, in the main()<\/em> function, I duplicate the string. That way the original is intact, and only the copy is shuffled. A strcmp()<\/em> function is used in a do-while<\/em> loop to determine when the shuffles need to stop. Then the number of shuffle count is displayed.<\/p>\n
Click here<\/a> to view my full solution. Here is sample output:<\/p>\n
Original deck: ABCDEFGHIJKLMNOPQRSTUVWXYZ\r\nShuffle  1: ANBOCPDQERFSGTHUIVJWKXLYMZ\r\nShuffle  2: ATNHBUOICVPJDWQKEXRLFYSMGZ\r\nShuffle  3: AWTQNKHEBXUROLIFCYVSPMJGDZ\r\nShuffle  4: ALWITFQCNYKVHSEPBMXJUGRDOZ\r\nShuffle  5: ASLEWPIBTMFXQJCUNGYRKDVOHZ\r\nShuffle  6: AJSCLUENWGPYIRBKTDMVFOXHQZ\r\nShuffle  7: ARJBSKCTLDUMEVNFWOGXPHYQIZ\r\nShuffle  8: AVRNJFBWSOKGCXTPLHDYUQMIEZ\r\nShuffle  9: AXVTRPNLJHFDBYWUSQOMKIGECZ\r\nShuffle 10: AYXWVUTSRQPONMLKJIHGFEDCBZ\r\nShuffle 11: AMYLXKWJVIUHTGSFREQDPCOBNZ\r\nShuffle 12: AGMSYFLRXEKQWDJPVCIOUBHNTZ\r\nShuffle 13: ADGJMPSVYCFILORUXBEHKNQTWZ\r\nShuffle 14: AODRGUJXMBPESHVKYNCQFTIWLZ\r\nShuffle 15: AHOVDKRYGNUCJQXFMTBIPWELSZ\r\nShuffle 16: AQHXOFVMDTKBRIYPGWNEULCSJZ\r\nShuffle 17: AIQYHPXGOWFNVEMUDLTCKSBJRZ\r\nShuffle 18: AEIMQUYDHLPTXCGKOSWBFJNRVZ\r\nShuffle 19: ACEGIKMOQSUWYBDFHJLNPRTVXZ\r\nShuffle 20: ABCDEFGHIJKLMNOPQRSTUVWXYZ\r\nIt took a total of 20 shuffles to restore the deck.<\/code><\/pre>\n
Your solution can be different, but the number of shuffles required to restore a 26-card deck is constant at 20.<\/p>\n","protected":false},"excerpt":{"rendered":"
A perfect shuffle splits a deck of cards in two. The second half is folded evenly into the first half, so that every other card comes from the first and last half of the deck, respectively. This type of shuffle … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-2537","post","type-post","status-publish","format-standard","hentry","category-solution"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2537","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2537"}],"version-history":[{"count":5,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2537\/revisions"}],"predecessor-version":[{"id":2566,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2537\/revisions\/2566"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2537"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2537"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}