Mercurial > public > m209

changeset 34:502b6bbcfefb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Can now generate key list for first time. The algorithm fails on certain selections from group B (the unit test catches this). I'm committing this anyway and will address this later.
author Brian Neal <bgneal@gmail.com>
date Sat, 22 Jun 2013 15:32:13 -0500
parents c9cc6f9f3bad
children b32ded2f157f
files m209/keylist/data.py m209/keylist/generate.py m209/keylist/tests/test_generate.py
diffstat 3 files changed, 172 insertions(+), 11 deletions(-) [+]
line wrap: on
line diff
--- a/m209/keylist/data.py	Fri Jun 21 20:20:43 2013 -0500
+++ b/m209/keylist/data.py	Sat Jun 22 15:32:13 2013 -0500
@@ -374,3 +374,92 @@
     [1, 2, 4, 7, 12, 12],
     [1, 2, 3, 7, 13, 13],
 ]
+
+
+# All possible inputs to the Drum.rotate() function. This is used to ensure lug
+# settings can create all values between 1 - 27, inclusive.
+#
+# This list was generated as follows:
+# >>> from itertools import permutations
+# >>> cases = [
+# ...     [True, True, True, True, True, True],
+# ...     [True, True, True, True, True, False],
+# ...     [True, True, True, True, False, False],
+# ...     [True, True, True, False, False, False],
+# ...     [True, True, False, False, False, False],
+# ...     [True, False, False, False, False, False],
+# ... ]
+# >>>
+# >>> result = []
+# >>> for case in cases:
+# ...     result.extend(sorted(list(set(permutations(case)))))
+#
+# The code above could have been included directly but it seems wasteful to
+# compute it every time the program is run. We'll trade some memory for CPU
+# here.
+
+ALL_DRUM_ROTATE_INPUTS = [
+    (True, True, True, True, True, True),
+    (False, True, True, True, True, True),
+    (True, False, True, True, True, True),
+    (True, True, False, True, True, True),
+    (True, True, True, False, True, True),
+    (True, True, True, True, False, True),
+    (True, True, True, True, True, False),
+    (False, False, True, True, True, True),
+    (False, True, False, True, True, True),
+    (False, True, True, False, True, True),
+    (False, True, True, True, False, True),
+    (False, True, True, True, True, False),
+    (True, False, False, True, True, True),
+    (True, False, True, False, True, True),
+    (True, False, True, True, False, True),
+    (True, False, True, True, True, False),
+    (True, True, False, False, True, True),
+    (True, True, False, True, False, True),
+    (True, True, False, True, True, False),
+    (True, True, True, False, False, True),
+    (True, True, True, False, True, False),
+    (True, True, True, True, False, False),
+    (False, False, False, True, True, True),
+    (False, False, True, False, True, True),
+    (False, False, True, True, False, True),
+    (False, False, True, True, True, False),
+    (False, True, False, False, True, True),
+    (False, True, False, True, False, True),
+    (False, True, False, True, True, False),
+    (False, True, True, False, False, True),
+    (False, True, True, False, True, False),
+    (False, True, True, True, False, False),
+    (True, False, False, False, True, True),
+    (True, False, False, True, False, True),
+    (True, False, False, True, True, False),
+    (True, False, True, False, False, True),
+    (True, False, True, False, True, False),
+    (True, False, True, True, False, False),
+    (True, True, False, False, False, True),
+    (True, True, False, False, True, False),
+    (True, True, False, True, False, False),
+    (True, True, True, False, False, False),
+    (False, False, False, False, True, True),
+    (False, False, False, True, False, True),
+    (False, False, False, True, True, False),
+    (False, False, True, False, False, True),
+    (False, False, True, False, True, False),
+    (False, False, True, True, False, False),
+    (False, True, False, False, False, True),
+    (False, True, False, False, True, False),
+    (False, True, False, True, False, False),
+    (False, True, True, False, False, False),
+    (True, False, False, False, False, True),
+    (True, False, False, False, True, False),
+    (True, False, False, True, False, False),
+    (True, False, True, False, False, False),
+    (True, True, False, False, False, False),
+    (False, False, False, False, False, True),
+    (False, False, False, False, True, False),
+    (False, False, False, True, False, False),
+    (False, False, True, False, False, False),
+    (False, True, False, False, False, False),
+    (True, False, False, False, False, False),
+]
--- a/m209/keylist/generate.py	Fri Jun 21 20:20:43 2013 -0500
+++ b/m209/keylist/generate.py	Sat Jun 22 15:32:13 2013 -0500
@@ -13,14 +13,15 @@
 from ..converter import M209
 from .. import M209Error
 from ..data import KEY_WHEEL_DATA
-from .data import GROUP_A, GROUP_B
+from .data import GROUP_A, GROUP_B, ALL_DRUM_ROTATE_INPUTS
+from ..drum import Drum
 
 
 logger = logging.getLogger(__name__)
 
 # Maximum number of attempts to generate valid settings before giving up and
 # raising a M209Error:
-MAX_ATTEMPTS = 128
+MAX_ATTEMPTS = 1024
 
 # Total number of pins on all 6 wheels:
 TOTAL_PINS = sum(len(letters) for letters, _ in KEY_WHEEL_DATA)
@@ -101,15 +102,20 @@
     for n in range(MAX_ATTEMPTS):
         overlaps = distribute_overlaps(selection, overlap)
         if overlaps and check_overlaps(overlaps):
-            break
+            # So far this looks good. But now we need to determine if the drum
+            # can generate all numbers in the range 1-27.
+            # Build a drum from our setup:
+            drum = Drum(build_lug_list(selection, overlaps))
+            logger.debug('Drum: %s', drum)
+            if check_lug_placement(drum):
+                break
+            else:
+                logger.debug("Failed lug placement check")
     else:
-        raise M209Error("generate_lugs: too many attempts")
+        raise M209Error("generate_lugs: too many attempts: %s" % sorted(selection))
     logger.info("Lugs generated in %s iteration(s)", n + 1)
 
-    # Build lug string
-    # TODO
-
-    return ''
+    return drum.to_key_list()
 
 
 def distribute_overlaps(selection, overlap):
@@ -211,6 +217,47 @@
     return True
 
 
+def build_lug_list(selection, overlaps):
+    """Build a lug list given the current selection and overlaps list."""
+
+    remaining = list(selection)
+
+    lug_list = []
+    for x, y, n in overlaps:
+        lug_list.extend([(x, y)] * n)
+        remaining[x] -= n
+        remaining[y] -= n
+
+    for n in range(6):
+        lug_list.extend([(n, )] * remaining[n])
+
+    return lug_list
+
+
+def check_lug_placement(drum):
+    """Returns True if this drum is capable of generating all values in the
+    range 1-27, inclusive, and False otherwise.
+
+    """
+    values = set()
+
+    # Loop over all possible inputs to Drum.rotate(), noting the answer each
+    # time by storing it in our values set. When the size of our set reaches 27
+    # we know we have good settings.
+
+    for pins in ALL_DRUM_ROTATE_INPUTS:
+        val = drum.rotate(pins)
+        assert(1 <= val <= 27)
+        values.add(val)
+
+        if len(values) == 27:
+            break
+    else:
+        return False
+
+    return True
+
+
 def generate_pin_list():
     """Return a random pin list based on Army procedure."""
 
--- a/m209/keylist/tests/test_generate.py	Fri Jun 21 20:20:43 2013 -0500
+++ b/m209/keylist/tests/test_generate.py	Sat Jun 22 15:32:13 2013 -0500
@@ -11,6 +11,8 @@
 from ..generate import generate_key_list, pin_list_check, check_overlaps
 from m209.converter import M209
 from m209.data import KEY_WHEEL_DATA
+from m209.drum import Drum
+from m209.keylist.data import ALL_DRUM_ROTATE_INPUTS
 
 
 def make_pin_list(eff_cnt):
@@ -40,7 +42,7 @@
             'EFGHIJLMNP'
         ]
 
-    def test_generate_key_list(self):
+    def do_test_generate_key_list(self):
 
         key_list = generate_key_list('BN')
         self.assertEqual(key_list.indicator, 'BN')
@@ -50,13 +52,36 @@
         for i, pins in enumerate(key_list.pin_list):
             self.assertTrue(all(c in KEY_WHEEL_DATA[i][0] for c in pins))
 
-        # TODO: add some lug asserts
-
         m_209 = M209(lugs=key_list.lugs, pin_list=key_list.pin_list)
         m_209.set_key_wheels('AAAAAA')
         s = m_209.encrypt('A' * 26)
         self.assertEqual(s, key_list.letter_check)
 
+    def test_generate_key_list(self):
+
+        for n in range(32):
+            self.do_test_generate_key_list()
+
+    def do_test_lug_settings(self):
+
+        key_list = generate_key_list('BN')
+        drum = Drum.from_key_list(key_list.lugs)
+
+        vals = set()
+        for pins in ALL_DRUM_ROTATE_INPUTS:
+            val = drum.rotate(pins)
+            self.assertTrue(1 <= val <= 27)
+            vals.add(val)
+            if len(vals) == 27:
+                break
+        else:
+            self.fail('Invalid drum settings (1-27 check)')
+
+    def test_lug_settings(self):
+
+        for n in range(1024):
+            self.do_test_lug_settings()
+
     def test_pin_list_check(self):
 
         # Effective pin ratio too high (100%)