core/
deck.rs

1// Copyright (C) 2017 Steve Sprang
2//
3// This program is free software: you can redistribute it and/or modify
4// it under the terms of the GNU General Public License as published by
5// the Free Software Foundation, either version 3 of the License, or
6// (at your option) any later version.
7//
8// This program is distributed in the hope that it will be useful,
9// but WITHOUT ANY WARRANTY; without even the implied warranty of
10// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11// GNU General Public License for more details.
12//
13// You should have received a copy of the GNU General Public License
14// along with this program.  If not, see <http://www.gnu.org/licenses/>.
15
16use crate::card::*;
17use crate::find::FindSets;
18use crate::pair_iter::PairIter;
19use crate::shuffle::Shuffle;
20use std::cmp;
21
22pub const DECK_SIZE: usize = 81;
23
24/// Returns a vector containing all the cards in a Set deck.
25pub fn cards() -> Vec<Card> {
26    (0..DECK_SIZE).map(Card::new).collect()
27}
28
29#[derive(Default, Clone)]
30pub struct Deck { stock: Vec<Card> }
31
32impl Deck {
33    /// Returns a shuffled `Deck`.
34    pub fn new() -> Deck {
35        let mut cards = cards();
36        cards.shuffle();
37        Deck { stock: cards }
38    }
39
40    /// Removes all cards from the deck that do not have a solid
41    /// shading. This is useful as a deck for beginners.
42    pub fn simplify(&mut self) {
43        self.stock.retain(|card| card.shading() == Shading::Solid);
44    }
45
46    pub fn is_empty(&self) -> bool {
47        self.stock.is_empty()
48    }
49
50    pub fn remainder(&self) -> usize {
51        self.stock.len()
52    }
53
54    pub fn draw(&mut self, n: usize) -> Vec<Card> {
55        let r = self.remainder();
56        let x = cmp::min(n, r);
57        self.stock.split_off(r - x)
58    }
59}
60
61impl Deck {
62    /// The smallest number of cards guaranteed to contain a `Set` is
63    /// 21. However, the odds that there are no sets in 18 cards is so
64    /// low that it almost never happens in practice. As long as there
65    /// are at least 6 cards in the stock, we can doctor the deck to
66    /// guarantee that 18 cards will contain a `Set`:
67    ///
68    /// 15 (table) + 6 (stock) == 21
69    ///
70    /// If there are only 3 more cards to deal, you could still get
71    /// stuck with 18 cards, but at that point the game would be over.
72    ///
73    /// In the worst case scenario, 15 cards are on the table, 6 remain
74    /// in the stock, and there's exactly 1 `Set` amongst those 21
75    /// cards.* There are 3 cases we need to handle:
76    ///
77    /// 1) Two cards from the `Set` are on the table, and one is in the
78    /// stock. We need to make sure that the one card in the stock is in
79    /// the next draw.
80    ///
81    /// 2) One card from the `Set` is on the table, and two are in the
82    /// stock. We need to make sure that both cards in the stock are in
83    /// the next draw.
84    ///
85    /// 3) All three cards in the `Set` are in the stock. We need to put
86    /// those three cards into the next draw.
87    ///
88    /// *NOTE: It's possible that 21 cards always contain 2 or more
89    /// sets. As far as I know, that's an open question.
90    ///
91    pub fn draw_guaranteeing_set(&mut self, hand: &[Card]) -> Option<Vec<Card>> {
92        assert_eq!(hand.len(), 15);
93        assert!(self.stock.len() >= 6);
94
95        // Check to see if simply drawing the next 3 cards is okay.
96        // This will almost always work.
97        let mut draw = self.draw(3);
98        let mut test = hand.to_owned();
99        test.append(&mut draw.clone());
100
101        if test.contains_set() {
102            return Some(draw);
103        } else {
104            // return the draw to the stock so we can doctor the deck
105            self.stock.append(&mut draw);
106        }
107
108        self.fix_one_card(hand)
109            .or_else(|| self.fix_two_cards(hand))
110            .or_else(|| self.fix_three_cards())
111    }
112
113    fn fix_one_card(&mut self, hand: &[Card]) -> Option<Vec<Card>> {
114        // shuffle the cards in the hand so we don't favor cards at
115        // the front of the layout
116        let mut hand = hand.to_owned();
117        hand.shuffle();
118
119        for c in hand.pairs().map(|pair| pair.complete_set()) {
120            if let Some(ix) = self.stock.iter().position(|&obj| obj == c) {
121                // swap the matching card with the top card
122                let last_ix = self.stock.len() - 1;
123                self.stock.swap(ix, last_ix);
124
125                // now just draw normally
126                let mut draw = self.draw(3);
127
128                // shuffle to randomize the position of the found card
129                draw.shuffle();
130                return Some(draw);
131            }
132        }
133
134        None
135    }
136
137    fn fix_two_cards(&mut self, hand: &[Card]) -> Option<Vec<Card>> {
138        if let Some((&a, &b)) = self.stock.pairs()
139            .filter(|&pair| hand.contains(&pair.complete_set()))
140            .nth(0)
141        {
142            let mut result = vec![a, b];
143            // remove the found pair from the stock
144            self.stock.retain(|&n| n != a && n != b);
145
146            // need 1 more card... any will do
147            result.append(&mut self.draw(1));
148
149            // randomize the order
150            result.shuffle();
151            Some(result)
152        } else {
153            None
154        }
155    }
156
157    fn fix_three_cards(&mut self) -> Option<Vec<Card>> {
158        if let Some(set) = self.stock.find_first_set() {
159            let (a,b,c) = set.cards();
160            self.stock.retain(|&n| n != a && n != b && n != c);
161            Some(vec![a, b, c])
162        } else {
163            None
164        }
165    }
166}
167
168////////////////////////////////////////////////////////////////////////////////
169// Tests
170////////////////////////////////////////////////////////////////////////////////
171
172#[cfg(test)]
173mod tests {
174    use super::*;
175    use crate::card::Card;
176    use crate::find::{FindSets, FindSuperSets};
177
178    #[test]
179    fn count_sets() {
180        let sets = cards().find_all_sets();
181        assert_eq!(sets.len(), 1080);
182        assert_eq!(cards().count_sets(), 1080);
183    }
184
185    #[test]
186    fn count_supersets() {
187        let supersets = cards().find_all_supersets();
188        assert_eq!(supersets.len(), 63180);
189        assert_eq!(cards().count_supersets(), 63180);
190    }
191
192    #[test]
193    fn check_draw_cards() {
194        let mut deck = Deck::new();
195        let mut r = deck.remainder();
196
197        let mut deal = deck.draw(12);
198        assert_eq!(deal.len(), 12);
199        assert_eq!(deck.remainder(), r - 12);
200
201        r = deck.remainder();
202        deal = deck.draw(r + 10);
203        assert_eq!(deal.len(), r);
204        assert!(deck.is_empty());
205
206        deal = deck.draw(3);
207        assert!(deal.is_empty());
208    }
209
210    trait AsCards {
211        fn as_cards(&self) -> Vec<Card>;
212    }
213
214    impl AsCards for [usize] {
215        fn as_cards(&self) -> Vec<Card> {
216            self.iter()
217                .map(|&ix| Card::new(ix))
218                .collect()
219        }
220    }
221
222    #[test]
223    fn check_fixers() {
224        // these cards are a set
225        const A: usize = 21;
226        const B: usize = 41;
227        const C: usize = 58;
228        let set = [A, B, C].as_cards();
229        assert!(set.contains_set());
230
231        // 9 cards that contain exactly one set: (A, B, C)
232        let indices = vec![11, 19, 31, 34, 64, 72, A, B, C];
233        let cards = indices.as_cards();
234        assert_eq!(cards.count_sets(), 1);
235
236        ////////////////////////////////////////////////////////////////////////////////
237        // TEST fix_one_card
238        ////////////////////////////////////////////////////////////////////////////////
239
240        let hand = [11, A, B].as_cards(); // two cards from the set in the hand
241        let stock = [C, 19, 31, 34, 64, 72].as_cards(); // one in the stock
242
243        assert!(!hand.contains_set());
244        assert!(!stock.contains_set());
245
246        let mut deck = Deck { stock };
247        match deck.fix_one_card(&hand) {
248            None => panic!("Could not guarantee set!"),
249            Some(mut draw) => {
250                let mut test = hand.clone();
251                test.append(&mut draw);
252                assert!(test.contains_set());
253                test.sort_by_key(|c| c.index());
254                assert_eq!(test, [11, A, 34, B, C, 64].as_cards());
255                assert_eq!(deck.stock, [72, 19, 31].as_cards());
256            }
257        }
258
259        ////////////////////////////////////////////////////////////////////////////////
260        // TEST fix_two_cards
261        ////////////////////////////////////////////////////////////////////////////////
262
263        let hand = [11, 19, A].as_cards(); // one card from the set in the hand
264        let stock = [B, 31, 34, C, 64, 72].as_cards(); // two in the stock
265
266        assert!(!hand.contains_set());
267        assert!(!stock.contains_set());
268
269        let mut deck = Deck { stock };
270        match deck.fix_two_cards(&hand) {
271            None => panic!("Could not guarantee set!"),
272            Some(mut draw) => {
273                let mut test = hand.clone();
274                test.append(&mut draw);
275                assert!(test.contains_set());
276                test.sort_by_key(|c| c.index());
277                assert_eq!(test, [11, 19, A, B, C, 72].as_cards());
278                assert_eq!(deck.stock, [31, 34, 64].as_cards());
279            }
280        }
281
282        ////////////////////////////////////////////////////////////////////////////////
283        // TEST fix_three_cards
284        ////////////////////////////////////////////////////////////////////////////////
285
286        let stock = [34, A, B, C, 64, 72].as_cards(); // three cards from the set in the stock
287
288        let mut deck = Deck { stock };
289        match deck.fix_three_cards() {
290            None => panic!("Could not guarantee set!"),
291            Some(mut draw) => {
292                assert!(draw.contains_set());
293                draw.sort_by_key(|c| c.index());
294                assert_eq!(draw, set);
295                assert_eq!(deck.stock, [34, 64, 72].as_cards());
296            }
297        }
298    }
299
300    #[test]
301    fn check_guarantee() {
302        // 20 cards that contain no sets
303        let indices = vec![0,1,3,4,9,13,14,15,19,34,38,39,40,44,49,50,52,53,60,74];
304
305        // find the remaining cards in the deck
306        let mut complement: Vec<usize> = (0..81).collect();
307        for &ix in indices.iter().rev() {
308            complement.remove(ix);
309        }
310
311        // convert indices to Cards
312        let mut hand = indices.as_cards();
313        let rest = complement.as_cards();
314
315        assert_eq!(hand.len(), 20);
316        assert!(!hand.contains_set());
317
318        let mut stock = hand.split_off(15);
319        assert_eq!(stock.len(), 5);
320
321        // shift the stock to the right, so we can put our test cards at the bottom
322        stock.insert(0, rest[0]);
323
324        // add each of the remaining cards to the stock one by one,
325        // making sure that we can find sets
326        for &x in &rest {
327            stock[0] = x;
328            let mut deck = Deck { stock: stock.clone() };
329
330            match deck.draw_guaranteeing_set(&hand) {
331                None => panic!("Could not guarantee set!"),
332                Some(mut draw) => {
333                    let mut test = hand.clone();
334                    test.append(&mut draw);
335                    assert_eq!(test.len(), 18);
336                    assert!(test.contains_set());
337                }
338            }
339        }
340    }
341}
core/deck.rs

core/
deck.rs
