Exercise 5.7. Who needs friends to play Set? The card game Set has 81 different cards varying in four features across three possibilities for each kind of feature. The four features are: 12 or paragraphs, or more... sigh... 95 5. Sequential optimization and caching Kent Quanrud 5.6. Exercises Spring 2023 1. The shape, which is either a diamond, a squiggle, or an oval. 2. The number of shapes, which is either 1,2 , or 3 . 3. The color of the shape, which is either red, green, purple. 4. The shading of the shape, which is either solid, striped, or open. There are multiple variations of Set but they all are based on trying to form particular "sets" of three cards. A set consists of three cards satisfying all of these conditions: 1. They all have the same number or have three different numbers. 2. They all have the same shape or have three different shapes. 3. They all have the same shading or have three different shadings. 4. They all have the same color or have three different colors. Loosely speaking, the rules of Set are summarized by: If you can sort a group of three cards into "two of and one of ", then it is not a set. For example, the three cards on the right form a set. We have one card of each color, one of each shape, one of each shading, and one of each number. (In case this is printed in black and white, we mention that the first card is green, the second is purple, and the third is red.) We will study a solitaire version of Set. Solitaire Set starts with 3 decks of cards. Each round you choose one of the following options. 1. If the three cards on top of the deck form a set, you may remove all three from the top of their decks, and set them aside. 2. You may discard one card from the top of one of the decks, revealing a new card underneath (unless that deck is empty). (Even if the top three cards form a set, you can choose to discard one of them instead.) The goal is to form as many sets as possible by the time you empty all the decks. We will consider the game as an optimization problem where we also know the full sequence of cards in the deck. The three decks are represented by three arrays A[1..m],B[1..n], and C[1p]13 The cards are listed from top to bottom in each deck. For simplicity, we assume access to a constant-time subroutine IsItASet (i,j,k) that takes as input three indices i,j,k and outputs True if the cards (A[i],B[j],C[k]) form a set, and False if they do not. The problem is to compute the maximum number of sets that can be obtained in a game of Solitaire Set over the decks A[1..m],B[1..n], and C[1..p]. Design and analyze an algorithm for this
