Solution to the fivethirtyeight riddler from Oct 26, 2018

20181026-riddler.py

import numpy as np
from itertools import groupby, product

def model():
    """
    Solves the Riddler Classic from October 26, 2018.
    
    First, generate all valid hands. We only care about suits,  
    so we represent them using numbers 0, 1, 2, 3. There are 
    4096 unique hands we could generate, such as [0,0,0,0,0,0], 
    or [1,2,3,3,2,1], or [3,3,3,3,3,3].
    
    Next, we use a brute force approach to generate all valid
    swaps for a given hand. We are only allowed to move one
    contiguous group of cards one time, so we can enumerate
    these shifts explicitly. For example, there are 30 ways 
    to move one card, 20 ways to move two cards, and 12 ways 
    to move three cards. We don't need to move four, five, or
    six cards because those are repeats of smaller moves.
    
    Now we have an array of 4096 hands with 63 shifts each.
    (30 + 20 + 12 + 1 base case, where we make no moves.)
    
    We test whether any possible shift of each valid hand meets
    our criteria:
        1. All suits in the hand are grouped together
        2. The red suits aren't touching each other, and the black
            suits aren't touching each other either. Meaning the
            numbers 0 and 2 aren't touching, nor 1 and 3.
            
    So we have an array of (4096, 63) boolean values. If any value
    for a row is True, then we return True. The final output is 
    the number of True hands divided by the number of total hands.
    """
    
    def criteria(hand):
        """Returns True if a hand meets our criteria, otherwise False"""
        groups = [i for i, _ in groupby(hand)]
        suits = np.unique(hand)
        
        cond_1 = len(groups) == len(suits)
        cond_2 = (np.abs(np.diff(groups)) != 2).all()
        return cond_1 and cond_2
    
    
    swaps = np.array([
        # base case
        [0, 1, 2, 3, 4, 5],

        # one-card shifts - there are some repeats in here, but that's fine
        [1, 0, 2, 3, 4, 5], [1, 2, 0, 3, 4, 5], [1, 2, 3, 0, 4, 5], [1, 2, 3, 4, 0, 5], [1, 2, 3, 4, 5, 0],
        [1, 0, 2, 3, 4, 5], [0, 2, 1, 3, 4, 5], [0, 2, 3, 1, 4, 5], [0, 2, 3, 4, 1, 5], [0, 2, 3, 4, 5, 1],
        [2, 0, 1, 3, 4, 5], [0, 2, 1, 3, 4, 5], [0, 1, 3, 2, 4, 5], [0, 1, 3, 4, 2, 5], [0, 1, 3, 4, 5, 2],
        [3, 0, 1, 2, 4, 5], [0, 3, 1, 2, 4, 5], [0, 1, 3, 2, 4, 5], [0, 1, 2, 4, 3, 5], [0, 1, 2, 4, 5, 3],
        [4, 0, 1, 2, 3, 5], [0, 4, 1, 2, 3, 5], [0, 1, 4, 2, 3, 5], [0, 1, 2, 4, 3, 5], [0, 1, 2, 3, 5, 4],
        [5, 0, 1, 2, 3, 4], [0, 5, 1, 2, 3, 4], [0, 1, 5, 2, 3, 4], [0, 1, 2, 5, 3, 4], [0, 1, 2, 3, 5, 4],

        # two-card shifts
        [2, 0, 1, 3, 4, 5], [2, 3, 0, 1, 4, 5], [2, 3, 4, 0, 1, 5], [2, 3, 4, 5, 0, 1],
        [1, 2, 0, 3, 4, 5], [0, 3, 1, 2, 4, 5], [0, 3, 4, 1, 2, 5], [0, 3, 4, 5, 1, 2],
        [2, 3, 0, 1, 4, 5], [0, 2, 3, 1, 4, 5], [0, 1, 4, 2, 3, 5], [0, 1, 4, 5, 2, 3],
        [3, 4, 0, 1, 2, 5], [0, 3, 4, 1, 2, 5], [0, 1, 3, 4, 2, 5], [0, 1, 2, 5, 3, 4],
        [4, 5, 0, 1, 2, 3], [0, 4, 5, 1, 2, 3], [0, 1, 4, 5, 2, 3], [0, 1, 2, 4, 5, 3],

        # three-card shifts
        [3, 0, 1, 2, 4, 5], [3, 4, 0, 1, 2, 5], [3, 4, 5, 0, 1, 2],
        [1, 2, 3, 0, 4, 5], [0, 4, 1, 2, 3, 5], [0, 4, 5, 1, 2, 3],
        [2, 3, 4, 0, 1, 5], [0, 2, 3, 4, 1, 5], [0, 1, 5, 2, 3, 4],
        [3, 4, 5, 0, 1, 2], [0, 3, 4, 5, 1, 2], [0, 1, 3, 4, 5, 2]
    ])
    
    hands = np.array(list(product(range(4), repeat=6)))
    all_hands = np.array([x[swaps] for x in hands])
    
    results = np.array([[criteria(y) for y in x] for x in all_hands])
    results = results.any(axis=1)
    
    return hands, results
    
if __name__ == '__main__':
    print(model())