import random class ListNode: def __init__(self, data, link = None): self.data = data self.link = link class LinkedList: def __init__(self): self._head = None self._tail = None self._length = 0

def addfirst(self, item): self._head = ListNode(item, self._head) if self._tail is None: self._tail = self._head self._length += 1

def addlast(self, item): if self._head is None: self.addfirst(item) else: self._tail.link = ListNode(item) self._tail = self._tail.link self._length += 1

def removefirst(self): item = self._head.data self._head = self._head.link if self._head is None: self._tail = None self._length -= 1 return item

def removelast(self): if self._head is self._tail: return self.removefirst() else: currentnode = self._head while currentnode.link is not self._tail: currentnode = currentnode.link

item = self._tail.data self._tail = currentnode self._tail.link = None self._length -= 1 return item

def __len__(self): return self._length

# To-do: complete display function # the function should loop through all elements # and print each one # function ends with a print() for new line def display(self): # Your code here print() # new line

def alldata(self): L = [] cur = self._head while cur is not None: L.append(cur.data) cur = cur.link return L

class LinkedDeque: def __init__(self): self._L = LinkedList()

def addfirst(self, item): self._L.addfirst(item)

def removefirst(self): return self._L.removefirst()

def addlast(self, item): self._L.addlast(item)

def removelast(self): return self._L.removelast()

def __len__(self): return len(self._L)

def display(self): self._L.display()

def alldata(self): return self._L.alldata()

def displaydeck(deck): for card in deck: print(card, end = ' ') print()

def playgame(seed): # Shuffles deck and sets random seed. # Do not delete or alter deck = ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']*4 random.seed(seed) random.shuffle(deck)

# To-do: split the deck in half using a list # assign 1 half to each player

# To-do: after splitting the deck into 2 lists, # create a LinkedDeque instance for each player # in each LinkedDeque add that player's cards.

# This is the public deck deckP = []

# To-do: Simulate the cycles of 1 game. See PDF for explanation.

# To-do: Once a game has finished, return a tuple # which has either "A wins" or "B wins" as its first element # and the winning player's deck as a list as the second element

1. Introduction In this exercise, we will use a data structure known as a LinkedDeque (deque implemented using linked list) to implement the card game Snap! 2. Objectives The purpose of this assignment is to help you: Sharpen your knowledge on basic data structures through an application *Refine your ability to translate real-world scenarios into code Note: Before you start, if you are not familiar with LinkedLists or Deques you are recommended to review the sample codes we covered in lecture first. 3. Background 3.1. Snap Card Game Snap is an easy-to-learn card game. Our version of Snap makes the game even more straight forward. The basic flow of our version of Snap is as follows: Step 1: Divide the deck into 2 halves (1 half per player; deck does not include Jokers) Step 2: While neither player has an empty deck, the two players take turns throwing a card into a public deck (which starts off as an empty deck). If a card is thrown that has the same rank as a previous card in the public deck, the player who threw that card takes the cards in the public deck up until (and including) the card of the same rank. Note: the cards thrown by each player can be from either the top or the bottom of their deck. We will determine whether the top or bottom card is thrown using randomness. Consider this example: suppose player A has the cards A, 2, Q, J, K, 5, Q, player B has the cards 3,2, Q, 7, 4, and the public deck has the card 7, 5, 4, 1, 8 (this example is not with 52 cards, it is simplified for the sake of explanation). Player A randomly decides to throw the card that's on the bottom of his/her deck, a Queen, which has not appeared thus far in the public deck (so the new public deck is 7, 5, 4, 1, 8, Q). Then player B throws a 4 which has appeared in the public deck (now the public deck is 7, 5, 4, 1, 8,Q, 4), thus player B takes the public deck up until and including the 4 and adds it to the bottom of his/her deck (4, 1, 8, Q,4-in exactly that order). After this one cycle of turns, player A has the cards A, 2, Q, J, K, 5, player B has the cards 3, 2, Q,7, 4, 1, 8, Q, 4, and the public deck has 7, 5. 1. Introduction In this exercise, we will use a data structure known as a LinkedDeque (deque implemented using linked list) to implement the card game Snap! 2. Objectives The purpose of this assignment is to help you: Sharpen your knowledge on basic data structures through an application *Refine your ability to translate real-world scenarios into code Note: Before you start, if you are not familiar with LinkedLists or Deques you are recommended to review the sample codes we covered in lecture first. 3. Background 3.1. Snap Card Game Snap is an easy-to-learn card game. Our version of Snap makes the game even more straight forward. The basic flow of our version of Snap is as follows: Step 1: Divide the deck into 2 halves (1 half per player; deck does not include Jokers) Step 2: While neither player has an empty deck, the two players take turns throwing a card into a public deck (which starts off as an empty deck). If a card is thrown that has the same rank as a previous card in the public deck, the player who threw that card takes the cards in the public deck up until (and including) the card of the same rank. Note: the cards thrown by each player can be from either the top or the bottom of their deck. We will determine whether the top or bottom card is thrown using randomness. Consider this example: suppose player A has the cards A, 2, Q, J, K, 5, Q, player B has the cards 3,2, Q, 7, 4, and the public deck has the card 7, 5, 4, 1, 8 (this example is not with 52 cards, it is simplified for the sake of explanation). Player A randomly decides to throw the card that's on the bottom of his/her deck, a Queen, which has not appeared thus far in the public deck (so the new public deck is 7, 5, 4, 1, 8, Q). Then player B throws a 4 which has appeared in the public deck (now the public deck is 7, 5, 4, 1, 8,Q, 4), thus player B takes the public deck up until and including the 4 and adds it to the bottom of his/her deck (4, 1, 8, Q,4-in exactly that order). After this one cycle of turns, player A has the cards A, 2, Q, J, K, 5, player B has the cards 3, 2, Q,7, 4, 1, 8, Q, 4, and the public deck has 7, 5