 
   # utilities --------------------------------------------------------------------
 
-  cardinality: (password) ->
-    [lower, upper, digits, symbols, latin1_symbols, latin1_letters] = (
-      false for i in [0...6]
-    )
-    unicode_codepoints = []
-    for chr in password.split('')
-      ord = chr.charCodeAt(0)
-      if 0x30 <= ord <= 0x39
-        digits = true
-      else if 0x41 <= ord <= 0x5a
-        upper = true
-      else if 0x61 <= ord <= 0x7a
-        lower = true
-      else if ord <= 0x7f
-        symbols = true
-      else if 0x80 <= ord <= 0xBF
-        latin1_symbols = true
-      else if 0xC0 <= ord <= 0xFF
-        latin1_letters = true
-      else if ord > 0xFF
-        unicode_codepoints.push ord
-    c = 0
-    c += 10 if digits
-    c += 26 if upper
-    c += 26 if lower
-    c += 33 if symbols
-    c += 64 if latin1_symbols
-    c += 64 if latin1_letters
-    if unicode_codepoints.length
-      min_cp = max_cp = unicode_codepoints[0]
-      for cp in unicode_codepoints[1..]
-        min_cp = cp if cp < min_cp
-        max_cp = cp if cp > max_cp
-      # if the range between unicode codepoints is small,
-      # assume one extra alphabet is in use (eg cyrillic, korean) and add a ballpark +40
-      #
-      # if the range is large, be very conservative and add +100 instead of the range.
-      # (codepoint distance between chinese chars can be many thousand, for example,
-      # but that cardinality boost won't be justified if the characters are common.)
-      range = max_cp - min_cp + 1
-      range = 40 if range < 40
-      range = 100 if range > 100
-      c += range
-    c
-
 module.exports = scoring

    average += (n for n in neighbors when n).length
  average /= (k for k,v of graph).length
  average

scoring =
  nCk: (n, k) ->

  # search --- most guessable match sequence -------------------------------------
  # ------------------------------------------------------------------------------
  #
  # takes a sequence of overlapping matches, returns the non-overlapping sequence with
  # minimum guesses. O(nml) dp alg for length-n password with m candidate matches
  # and optimal length-l sequence.
  #
  # the optimal "minimum guesses" sublist is here defined to be the sublist that
  # minimizes:
  #
  #    l! * Product(m.guesses for m in sequence) + D^(l - 1)
  #
  # where l is the length of the sequence.
  #
  # the factorial term is the number of ways to order l patterns.
  #
  # the D^(l-1) term is another length penalty, roughly capturing the idea that an
  # attacker will try lower-length sequences first before trying length-l sequences.
  #
  # for example, consider a sequence that is date-repeat-dictionary.
  #  - an attacker would need to try other date-repeat-dictionary combinations,
  #    hence the product term.
  #  - an attacker would need to try repeat-date-dictionary, dictionary-repeat-date,
  #    ..., hence the factorial term.
  #  - an attacker would also likely try length-1 (dictionary) and length-2 (dictionary-date)
  #    sequences before length-3. assuming at minimum D guesses per pattern type,
  #    D^(l-1) approximates Sum(D^i for i in [1..l-1]
  #
  # ------------------------------------------------------------------------------

  most_guessable_match_sequence: (password, matches) ->

    # at [k][l], the product of guesses of the optimal sequence of length-l
    # covering password[0..k].
    optimal_product = []

    # at [k][l], the final match (match.j == k) in said optimal sequence of length l.
    backpointers = []

    max_l = 0        # max-length sequence ever recorded
    optimal_l = null # length of current optimal sequence

    make_bruteforce_match = (i, j) =>
      match =
        pattern: 'bruteforce'
        token: password[i..j]
        i: i
        j: j
      match

    score = (guess_product, sequence_length) =>
      result = @factorial(sequence_length) * guess_product
      result += Math.pow MIN_GUESSES_BEFORE_GROWING_SEQUENCE, sequence_length - 1
      result

    for k in [0...password.length]
      backpointers[k] = []
      optimal_product[k] = []
      optimal_score = Infinity
      for prev_l in [0..max_l]
        # for each new k, starting scenario to try to beat: bruteforce matches
        # involving the lowest-possible l. three cases:
        #
        # 1. all-bruteforce match (for length-1 sequences.)
        # 2. extending a previous bruteforce match
        #    (possible when optimal[k-1][l] ends in bf.)
        # 3. starting a new single-char bruteforce match
        #    (possible when optimal[k-1][l] exists but does not end in bf.)
        #
        # otherwise: there is no bruteforce starting scenario that might be better
        # than already-discovered lower-l sequences.
        consider_bruteforce = true
        bf_j = k
        if prev_l == 0
          bf_i = 0
          new_l = 1
        else if backpointers[k-1]?[prev_l]?.pattern == 'bruteforce'
          bf_i = backpointers[k-1][prev_l].i
          new_l = prev_l
        else if backpointers[k-1]?[prev_l]?
          bf_i = k
          new_l = prev_l + 1
        else
          consider_bruteforce = false

        if consider_bruteforce
          bf_match = make_bruteforce_match bf_i, bf_j
          prev_j = k - bf_match.token.length # end of preceeding match
          candidate_product = @estimate_guesses bf_match
          candidate_product *= optimal_product[prev_j][new_l - 1] if new_l > 1
          candidate_score = score candidate_product, new_l
          if candidate_score < optimal_score
            optimal_score = candidate_score
            optimal_product[k][new_l] = candidate_product
            optimal_l = new_l
            max_l = Math.max max_l, new_l
            backpointers[k][new_l] = bf_match

        # now try beating those bruteforce starting scenarios.
        # for each match m ending at k, see if forming a (prev_l + 1) sequence
        # ending at m is better than the current optimum.
        for match in matches when match.j == k
          [i, j] = [match.i, match.j]
          if prev_l == 0
            # if forming a len-1 sequence [match], match.i must fully cover [0..k]
            continue unless i == 0
          else
            # it's only possible to form a new potentially-optimal sequence ending at
            # match when there's an optimal length-prev_l sequence ending at match.i-1.
            continue unless optimal_product[i-1]?[prev_l]?
          candidate_product = @estimate_guesses match
          candidate_product *= optimal_product[i-1][prev_l] if prev_l > 0
          candidate_score = score candidate_product, prev_l + 1
          if candidate_score < optimal_score
            optimal_score = candidate_score
            optimal_product[k][prev_l+1] = candidate_product
            optimal_l = prev_l + 1
            max_l = Math.max max_l, prev_l+1
            backpointers[k][prev_l+1] = match

    # walk backwards and decode the optimal sequence
    match_sequence = []
    l = optimal_l
    k = password.length - 1
    while k >= 0
      match = backpointers[k][l]
      match_sequence.push match
      k = match.i - 1
      l -= 1
    match_sequence.reverse()

    # final result object
    password: password
    guesses: optimal_score
    guesses_log10: @log10 optimal_score
    sequence: match_sequence

  # ------------------------------------------------------------------------------
