Skip to content

Commit 805bed0

Browse files
lowelowe
committed
cleaner sequence_match impl + unit tests
1 parent 2a3d018 commit 805bed0

2 files changed

Lines changed: 126 additions & 33 deletions

File tree

‎src/matching.coffee‎

Lines changed: 29 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -25,12 +25,13 @@ GRAPHS =
2525
SEQUENCES =
2626
lower: 'abcdefghijklmnopqrstuvwxyz'
2727
upper: 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
28-
digits: '01234567890'
28+
digits: '0123456789'
2929

3030
matching =
3131
empty: (obj) -> (k for k of obj).length == 0
3232
extend: (lst, lst2) -> lst.push.apply lst, lst2
3333
translate: (string, chr_map) -> (chr_map[chr] or chr for chr in string.split('')).join('')
34+
mod: (n, m) -> ((n % m) + m) % m # mod impl that works for negative numbers
3435

3536
# ------------------------------------------------------------------------------
3637
# omnimatch -- combine everything ----------------------------------------------
@@ -268,40 +269,35 @@ matching =
268269
result
269270

270271
sequence_match: (password) ->
272+
min_sequence_length = 3 # TODO allow 2-char sequences?
271273
result = []
272-
i = 0
273-
while i < password.length
274-
j = i + 1
275-
seq = null # either lower, upper, or digits
276-
seq_name = null
277-
seq_direction = null # 1 for ascending seq abcd, -1 for dcba
278-
for seq_candidate_name, seq_candidate of SEQUENCES
279-
[i_n, j_n] = (seq_candidate.indexOf(chr) for chr in [password.charAt(i),password.charAt(j)])
280-
if i_n > -1 and j_n > -1
281-
direction = j_n - i_n
282-
if direction in [1, -1]
283-
seq = seq_candidate
284-
seq_name = seq_candidate_name
285-
seq_direction = direction
286-
break
287-
if seq
288-
loop
289-
[prev_char, cur_char] = password[j-1..j]
290-
[prev_n, cur_n] = (seq_candidate.indexOf(chr) for chr in [prev_char, cur_char])
291-
if cur_n - prev_n == seq_direction
274+
for sequence_name, sequence of SEQUENCES
275+
for direction in [1, -1]
276+
i = 0
277+
while i < password.length
278+
unless password[i] in sequence
279+
i += 1
280+
continue
281+
j = i + 1
282+
sequence_position = sequence.indexOf password[i]
283+
while j < password.length
284+
# mod by sequence length to allow sequences to wrap around: xyzabc
285+
next_sequence_position = @mod sequence_position + direction, sequence.length
286+
unless sequence.indexOf(password[j]) == next_sequence_position
287+
break
292288
j += 1
293-
else
294-
if j - i > 2 # don't consider length 1 or 2 chains. TODO revisit.
295-
result.push
296-
pattern: 'sequence'
297-
i: i
298-
j: j-1
299-
token: password[i...j]
300-
sequence_name: seq_name
301-
sequence_space: seq.length
302-
ascending: seq_direction == 1
303-
break
304-
i = j
289+
sequence_position = next_sequence_position
290+
j -= 1
291+
if j - i + 1 >= min_sequence_length
292+
result.push
293+
pattern: 'sequence'
294+
i: i
295+
j: j
296+
token: password[i..j]
297+
sequence_name: sequence_name
298+
sequence_space: sequence.length
299+
ascending: direction == 1
300+
i = j + 1
305301
result
306302

307303
#-------------------------------------------------------------------------------

‎test/test-matching.coffee‎

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
test = require 'tape'
2+
matching = require '../src/matching'
3+
4+
# takes a pattern and list of prefixes/suffixes
5+
# returns a bunch of variants of that pattern embedded
6+
# with each possible prefix/suffix combination, including no prefix/suffix
7+
# returns a list of triplets [variant, i, j] where [i,j] is the start/end of the pattern, inclusive
8+
genpws = (pattern, prefixes, suffixes) ->
9+
prefixes = prefixes.slice()
10+
suffixes = suffixes.slice()
11+
for lst in [prefixes, suffixes]
12+
lst.unshift '' if '' not in lst
13+
result = []
14+
for prefix in prefixes
15+
for suffix in suffixes
16+
[i, j] = [prefix.length, prefix.length + pattern.length - 1]
17+
result.push [prefix + pattern + suffix, i, j]
18+
result
19+
20+
test 'matching utils', (t) ->
21+
t.ok matching.empty []
22+
t.notOk matching.empty [1]
23+
t.notOk matching.empty [1, 2]
24+
t.notOk matching.empty [[]]
25+
t.ok matching.empty {}
26+
t.notOk matching.empty {a: 1}
27+
t.notOk matching.empty {0: {}}
28+
29+
lst = []
30+
matching.extend lst, []
31+
t.deepEqual lst, []
32+
matching.extend lst, [1]
33+
t.deepEqual lst, [1]
34+
matching.extend lst, [2, 3]
35+
t.deepEqual lst, [1, 2, 3]
36+
[lst1, lst2] = [[1], [2]]
37+
matching.extend lst1, lst2
38+
t.deepEqual lst1, [1, 2]
39+
t.deepEqual lst2, [2]
40+
41+
chr_map = {a: 'A', b: 'B'}
42+
t.equal matching.translate('a', chr_map), 'A'
43+
t.equal matching.translate('c', chr_map), 'c'
44+
t.equal matching.translate('ab', chr_map), 'AB'
45+
t.equal matching.translate('abc', chr_map), 'ABc'
46+
t.equal matching.translate('aa', chr_map), 'AA'
47+
t.equal matching.translate('abab', chr_map), 'ABAB'
48+
t.equal matching.translate('', chr_map), ''
49+
t.equal matching.translate('', {}), ''
50+
t.equal matching.translate('abc', {}), 'abc'
51+
t.end()
52+
53+
t.equal matching.mod(0, 1), 0
54+
t.equal matching.mod(5, 5), 0
55+
t.equal matching.mod(-1, 5), 4
56+
t.equal matching.mod(-5, 5), 0
57+
t.equal matching.mod(6, 5), 1
58+
59+
test 'sequence matching', (t) ->
60+
t.deepEqual matching.sequence_match(''), []
61+
t.deepEqual matching.sequence_match('a'), []
62+
t.deepEqual matching.sequence_match('1'), []
63+
prefixes = ['!', '22', 'ttt']
64+
suffixes = ['!', '22', 'ttt']
65+
for [pattern, name, is_ascending] in [
66+
['ABC', 'upper', true]
67+
['CBA', 'upper', false]
68+
['PQR', 'upper', true]
69+
['RQP', 'upper', false]
70+
['XYZ', 'upper', true]
71+
['ZYX', 'upper', false]
72+
['abcd', 'lower', true]
73+
['dcba', 'lower', false]
74+
['ghij', 'lower', true]
75+
['jihg', 'lower', false]
76+
['wxyz', 'lower', true]
77+
['zyxw', 'lower', false]
78+
['01234', 'digits', true]
79+
['43210', 'digits', false]
80+
['67890', 'digits', true]
81+
['09876', 'digits', false]
82+
]
83+
for [password, i, j] in genpws pattern, prefixes, suffixes
84+
matches = matching.sequence_match password
85+
t.equal matches.length, 1
86+
match = matches[0]
87+
t.equal match.pattern, 'sequence'
88+
t.equal match.i, i
89+
t.equal match.j, j
90+
t.equal match.token, pattern
91+
t.equal match.sequence_name, name
92+
t.equal match.ascending, is_ascending
93+
t.equal matching.sequence_match('abcba').length, 2
94+
t.equal matching.sequence_match('xyzabc').length, 1
95+
t.equal matching.sequence_match('ab').length, 0
96+
t.end()
97+

0 commit comments

Comments
 (0)