changeset 27:941590d946c0

Reworked the consecutive pin checks. Added tests.
author Brian Neal <bgneal@gmail.com>
date Sat, 15 Jun 2013 15:21:30 -0500 (2013-06-15)
parents 425981f27876
children 4db95b820ae2
files m209/keylist/generate.py m209/keylist/tests/test_generate.py
diffstat 2 files changed, 134 insertions(+), 20 deletions(-) [+]
line wrap: on
line diff
--- a/m209/keylist/generate.py	Fri Jun 14 21:46:42 2013 -0500
+++ b/m209/keylist/generate.py	Sat Jun 15 15:21:30 2013 -0500
@@ -5,6 +5,7 @@
 """This module contains routines to generate key lists."""
 
 import collections
+import itertools
 import random
 
 from .key_list import KeyList
@@ -20,6 +21,26 @@
 # Total number of pins on all 6 wheels:
 TOTAL_PINS = sum(len(letters) for letters, _ in KEY_WHEEL_DATA)
 
+# CONSEC_MAPS is a list of dicts, one for each key wheel. Each dict key is
+# a letter. The value is the string of 7 consecutive letters that would make the
+# key setting invalid according to Army procedure. The consecutive string
+# accounts for the letters on the key wheel and wrap-around.
+
+def build_consec_map(letters):
+    """Builds a "consecutive map" for the list of letters on a key wheel. This
+    is used to validate a pin list to make sure there are not too many effective
+    or ineffective pins in a consecutive sequence.
+
+    """
+    deque = collections.deque(letters)
+    consec = {}
+    for c in letters:
+        consec[c] = ''.join(itertools.islice(deque, 0, 7))
+        deque.rotate(-1)
+    return consec
+
+CONSEC_MAPS = [build_consec_map(letters) for letters, _ in KEY_WHEEL_DATA]
+
 
 def generate_key_list(indicator):
     """Create a key list at random with the given indicator.
@@ -96,26 +117,43 @@
         return False
 
     # Check for more than 6 consecutive effective pins on a wheel
-    # TODO: not all letters are on every wheel
 
-    for pins in pin_list:
-        run = 0
-        for i in range(len(pins) - 1):
-            if ord(pins[i]) + 1 == ord(pins[i + 1]):
-                run = 2 if run == 0 else run + 1
-            else:
-                run = 0
-            if run >= 7:
-                return False
+    for n, pins in enumerate(pin_list):
+        if check_consecutive(n, pins):
+            return False
 
     # Check for more than 6 consecutive ineffective pins on a wheel
-    # TODO: not all letters are on every wheel
 
-    for pins in pin_list:
-        x = 'A'
-        for y in pins:
-            if ord(y) - ord(x) >= 8:
-                return False
-            x = y
+    for n, pins in enumerate(pin_list):
+        if check_consecutive(n, invert_pins(n, pins)):
+            return False
 
     return True
+
+
+def check_consecutive(n, pins):
+    """Check for consecutive pins on key wheel n. The pins parameter must be
+    a string of the pins that are effective. Returns True if there are more than
+    6 consecutive effective pins and False otherwise.
+
+    """
+    consec = CONSEC_MAPS[n]
+    deque = collections.deque(pins)
+    for c in pins:
+        if consec[c] == ''.join(itertools.islice(deque, 0, 7)):
+            return True
+        deque.rotate(-1)
+    return False
+
+
+def invert_pins(n, pins):
+    """Given a string of effective pins on key wheel n, return a string where
+    all the effective pins are pushed to the left and all the ineffective pins
+    are pushed to the right, thus flipping which pins are effective
+    / ineffective.
+
+    """
+    all_letters = set(KEY_WHEEL_DATA[n][0])
+    effective = set(pins)
+    inverse = sorted(all_letters - effective)
+    return ''.join(inverse)
--- a/m209/keylist/tests/test_generate.py	Fri Jun 14 21:46:42 2013 -0500
+++ b/m209/keylist/tests/test_generate.py	Sat Jun 15 15:21:30 2013 -0500
@@ -81,7 +81,7 @@
         self.assertFalse(pin_list_check(make_pin_list(100)))
         self.assertFalse(pin_list_check(make_pin_list(125)))
 
-    def test_consecutive_effective_pins(self):
+    def test_consecutive_effective_pins_0(self):
 
         pin_list = self.valid_pin_list
         pin_list[0] = 'ABEGHIJKLNOSUZ'
@@ -96,8 +96,84 @@
         self.assertFalse(pin_list_check(pin_list))
         pin_list[0] = 'BEFGHIJKSUX'
         self.assertFalse(pin_list_check(pin_list))
+        pin_list[0] = 'ABCDGKOTXYZ'
+        self.assertFalse(pin_list_check(pin_list))
 
-    def test_consecutive_noneffective_pins(self):
-        pass
+    def test_consecutive_effective_pins_1(self):
 
+        pin_list = self.valid_pin_list
+        pin_list[1] = 'BCEGIKMOTUVXYZ'
+        self.assertTrue(pin_list_check(pin_list))
+        pin_list[1] = 'ABCEGIKMOTUVXYZ'
+        self.assertFalse(pin_list_check(pin_list))
 
+    def test_consecutive_effective_pins_2(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[2] = 'ACEGIKMOSTUVX'
+        self.assertTrue(pin_list_check(pin_list))
+        pin_list[2] = 'ABEGIKMOSTUVX'
+        self.assertFalse(pin_list_check(pin_list))
+
+    def test_consecutive_effective_pins_3(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[3] = 'ACEGIKMOSTU'
+        self.assertTrue(pin_list_check(pin_list))
+        pin_list[3] = 'ABCDGIKMOSTU'
+        self.assertFalse(pin_list_check(pin_list))
+
+    def test_consecutive_effective_pins_4(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[4] = 'ABCEGIKMOQRS'
+        self.assertTrue(pin_list_check(pin_list))
+        pin_list[4] = 'ABGIKMOPQRS'
+        self.assertFalse(pin_list_check(pin_list))
+
+    def test_consecutive_effective_pins_5(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[5] = 'ABCEGIKMOQ'
+        self.assertTrue(pin_list_check(pin_list))
+        pin_list[5] = 'ABGIKMNOPQ'
+        self.assertFalse(pin_list_check(pin_list))
+
+    def test_consecutive_noneffective_pins_0(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[0] = 'ABCDENOPQSUWYZ'
+        self.assertFalse(pin_list_check(pin_list))
+        pin_list[0] = 'BCDFGHJKLMOPRST'
+        self.assertFalse(pin_list_check(pin_list))
+
+    def test_consecutive_noneffective_pins_1(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[1] = 'CDEGHJKLNOPQRST'
+        self.assertFalse(pin_list_check(pin_list))
+
+    def test_consecutive_noneffective_pins_2(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[2] = 'CDEFHIJKMNOPQRS'
+        self.assertFalse(pin_list_check(pin_list))
+
+    def test_consecutive_noneffective_pins_3(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[3] = 'CDEGHIKLNOP'
+        self.assertFalse(pin_list_check(pin_list))
+
+    def test_consecutive_noneffective_pins_4(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[4] = 'EFGIJKMOP'
+        self.assertFalse(pin_list_check(pin_list))
+
+    def test_consecutive_noneffective_pins_5(self):
+
+        pin_list = self.valid_pin_list
+        pin_list[5] = 'DEFHIKLM'
+        self.assertFalse(pin_list_check(pin_list))
+