Mainly Tech projects on Python and Electronic Design Automation.

Monday, April 06, 2020

Spin the table: Solution!

An answer to a puzzle set by Matt Parker on his YouTube channel:



The Puzzle:


  1. A Circular table with positions 1..7
  2. Delegates numbered 1..7 arranged arbitrarily around the table.
  3. Delegates start with only one match to a correct seating position.
  4. Is it ALWAYS possible to spin the table and get two or more matches?
Find arrangements where it is not possible to spin the table to get more than one match.

The Model.

Let's number the positions on the table with integers 1 .. 7; and also give the delegates numbers 1 .. 7. If the delegate number equals the table number then that constitutes a seating match.

Storing the table order as a fixed list of [1, 2, ..7], the all the rotations of the table  can be modelled by the additional six rotations of that initial list found by popping the last number from the last rotation and appending to the front of the list, i.e:
[[1, 2, .. 7],
 [7, 1, .. 6],
 [6, 7, 1, .. 5],
 ..
 [2, 3, .. 7, 1]]

This is stored in variable spun.

The permutations of delegate numbers 1 .. 7 are all the possible orderings of delegates.
Every "base" perm will have six other perms which are just other rotations of the "base" ordering . If only the permutations generated with an initial 1 are used, (for example), then we can assume that any of the other six rotations of the permutation will also be an answer.

The Code.



1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# -*- coding: utf-8 -*-
"""
Spin the table.

Created on Wed Mar 25 19:59:49 2020

@author: Paddy3118
"""

from itertools import permutations


table = list(range(1, 8))
spun = []                   # spinning table positions
for i in range(7):
    spun.append(table)
    table = table[-1:] + table[:-1]     # rotate once

def match_count(table, delegates):
    return sum(1 for t, d in zip(table, delegates)
               if t == d)

def max_matches(delegates):
    return max(match_count(table, delegates) for table in spun)

def spin_the_table():
    return [d for d in permutations(table)
            if d[0] == 1 and match_count(table, d) == 1 and max_matches(d) < 2]


if __name__ == '__main__':
    answer = spin_the_table()
    print(f"Found {len(answer)} initial arrangements of the delegates:")
    for a in answer:
        print(' ', str(a)[1:-1])
    print("The 6 rotations of each individual answer above are also solutions")

Answer:



Found 19 initial arrangements of the delegates:
  1, 3, 5, 7, 2, 4, 6
  1, 3, 6, 2, 7, 5, 4
  1, 3, 7, 6, 4, 2, 5
  1, 4, 2, 7, 6, 3, 5
  1, 4, 6, 3, 2, 7, 5
  1, 4, 7, 2, 6, 5, 3
  1, 4, 7, 3, 6, 2, 5
  1, 4, 7, 5, 3, 2, 6
  1, 5, 2, 6, 3, 7, 4
  1, 5, 4, 2, 7, 3, 6
  1, 5, 7, 3, 6, 4, 2
  1, 6, 2, 5, 7, 4, 3
  1, 6, 4, 2, 7, 5, 3
  1, 6, 4, 3, 7, 2, 5
  1, 6, 4, 7, 3, 5, 2
  1, 6, 5, 2, 4, 7, 3
  1, 7, 4, 6, 2, 5, 3
  1, 7, 5, 3, 6, 2, 4
  1, 7, 6, 5, 4, 3, 2
The 6 rotations of each individual answer above are also solutions


Matt Parker's Solution Video: (He mentions my solution at time 05:00).

END.

No comments:

Post a Comment

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive