scoring/scoring.go
func MinimumEntropyMatchSequence(password string, matches []match.Match) MinEntropyMatch {
	bruteforceCardinality := float64(entropy.CalcBruteForceCardinality(password))
	upToK := make([]float64, len(password))
	backPointers := make([]match.Match, len(password))

	for k := 0; k < len(password); k++ {
		upToK[k] = get(upToK, k-1) + math.Log2(bruteforceCardinality)

		for _, match := range matches {
			if match.J != k {
				continue
			}

			i, j := match.I, match.J
			//see if best entropy up to i-1 + entropy of match is less that current min at j
			upTo := get(upToK, i-1)
			candidateEntropy := upTo + match.Entropy

			if candidateEntropy < upToK[j] {
				upToK[j] = candidateEntropy
				match.Entropy = candidateEntropy
				backPointers[j] = match
			}
		}
	}

	//walk backwards and decode the best sequence
	var matchSequence []match.Match
	passwordLen := len(password)
	passwordLen--
	for k := passwordLen; k >= 0; {
		match := backPointers[k]
		if match.Pattern != "" {
			matchSequence = append(matchSequence, match)
			k = match.I - 1

		} else {
			k--
		}

	}
	sort.Sort(match.Matches(matchSequence))

	makeBruteForceMatch := func(i, j int) match.Match {
		return match.Match{Pattern: "bruteforce",
			I:       i,
			J:       j,
			Token:   password[i : j+1],
			Entropy: math.Log2(math.Pow(bruteforceCardinality, float64(j-i)))}

	}

	k := 0
	var matchSequenceCopy []match.Match
	for _, match := range matchSequence {
		i, j := match.I, match.J
		if i-k > 0 {
			matchSequenceCopy = append(matchSequenceCopy, makeBruteForceMatch(k, i-1))
		}
		k = j + 1
		matchSequenceCopy = append(matchSequenceCopy, match)
	}

	if k < len(password) {
		matchSequenceCopy = append(matchSequenceCopy, makeBruteForceMatch(k, len(password)-1))
	}
	var minEntropy float64
	if len(password) == 0 {
		minEntropy = float64(0)
	} else {
		minEntropy = upToK[len(password)-1]
	}

	crackTime := roundToXDigits(entropyToCrackTime(minEntropy), 3)
	return MinEntropyMatch{Password: password,
		Entropy:          roundToXDigits(minEntropy, 3),
		MatchSequence:    matchSequenceCopy,
		CrackTime:        crackTime,
		CrackTimeDisplay: displayTime(crackTime),
		Score:            crackTimeToScore(crackTime)}

}
func MinimumEntropyMatchSequence(password string, matches []match.Match) MinEntropyMatch {
	bruteforceCardinality := float64(entropy.CalcBruteForceCardinality(password))
	upToK := make([]float64, len(password))
	backPointers := make([]match.Match, len(password))

	for k := 0; k < len(password); k++ {
		upToK[k] = get(upToK, k-1) + math.Log2(bruteforceCardinality)

		for _, match := range matches {
			if match.J != k {
				continue
			}

			i, j := match.I, match.J
			//see if best entropy up to i-1 + entropy of match is less that current min at j
			upTo := get(upToK, i-1)
			candidateEntropy := upTo + match.Entropy

			if candidateEntropy < upToK[j] {
				upToK[j] = candidateEntropy
				match.Entropy = candidateEntropy
				backPointers[j] = match
			}
		}
	}

	//walk backwards and decode the best sequence
	var matchSequence []match.Match
	passwordLen := len(password)
	passwordLen--
	for k := passwordLen; k >= 0; {
		match := backPointers[k]
		if match.Pattern != "" {
			matchSequence = append(matchSequence, match)
			k = match.I - 1

		} else {
			k--
		}

	}
	sort.Sort(match.Matches(matchSequence))

	makeBruteForceMatch := func(i, j int) match.Match {
		return match.Match{Pattern: "bruteforce",
			I:       i,
			J:       j,
			Token:   password[i : j+1],
			Entropy: math.Log2(math.Pow(bruteforceCardinality, float64(j-i)))}

	}

	k := 0
	var matchSequenceCopy []match.Match
	for _, match := range matchSequence {
		i, j := match.I, match.J
		if i-k > 0 {
			matchSequenceCopy = append(matchSequenceCopy, makeBruteForceMatch(k, i-1))
		}
		k = j + 1
		matchSequenceCopy = append(matchSequenceCopy, match)
	}

	if k < len(password) {
		matchSequenceCopy = append(matchSequenceCopy, makeBruteForceMatch(k, len(password)-1))
	}
	var minEntropy float64
	if len(password) == 0 {
		minEntropy = float64(0)
	} else {
		minEntropy = upToK[len(password)-1]
	}

	crackTime := roundToXDigits(entropyToCrackTime(minEntropy), 3)
	return MinEntropyMatch{Password: password,
		Entropy:          roundToXDigits(minEntropy, 3),
		MatchSequence:    matchSequenceCopy,
		CrackTime:        crackTime,
		CrackTimeDisplay: displayTime(crackTime),
		Score:            crackTimeToScore(crackTime)}

}
func MinimumEntropyMatchSequence ( password string , matches [ ] match . Match ) MinEntropyMatch { bruteforceCardinality := float64 ( entropy . CalcBruteForceCardinality ( password ) ) upToK := make ( [ ] float64 , len ( password ) ) backPointers := make ( [ ] match . Match , len ( password ) ) for k := 0 ; k < len ( password ) ; k ++ { upToK [ k ] = get ( upToK , k - 1 ) + math . Log2 ( bruteforceCardinality ) for _ , match := range matches { if match . J != k { continue } i , j := match . I , match . J //see if best entropy up to i-1 + entropy of match is less that current min at j upTo := get ( upToK , i - 1 ) candidateEntropy := upTo + match . Entropy if candidateEntropy < upToK [ j ] { upToK [ j ] = candidateEntropy match . Entropy = candidateEntropy backPointers [ j ] = match } } } //walk backwards and decode the best sequence var matchSequence [ ] match . Match passwordLen := len ( password ) passwordLen -- for k := passwordLen ; k >= 0 ; { match := backPointers [ k ] if match . Pattern != " " { matchSequence = append ( matchSequence , match ) k = match . I - 1 } else { k -- } } sort . Sort ( match . Matches ( matchSequence ) ) makeBruteForceMatch := func ( i , j int ) match . Match { return match . Match { Pattern : " " , I : i , J : j , Token : password [ i : j + 1 ] , Entropy : math . Log2 ( math . Pow ( bruteforceCardinality , float64 ( j - i ) ) ) } } k := 0 var matchSequenceCopy [ ] match . Match for _ , match := range matchSequence { i , j := match . I , match . J if i - k > 0 { matchSequenceCopy = append ( matchSequenceCopy , makeBruteForceMatch ( k , i - 1 ) ) } k = j + 1 matchSequenceCopy = append ( matchSequenceCopy , match ) } if k < len ( password ) { matchSequenceCopy = append ( matchSequenceCopy , makeBruteForceMatch ( k , len ( password ) - 1 ) ) } var minEntropy float64 if len ( password ) == 0 { minEntropy = float64 ( 0 ) } else { minEntropy = upToK [ len ( password ) - 1 ] } crackTime := roundToXDigits ( entropyToCrackTime ( minEntropy ) , 3 ) return MinEntropyMatch { Password : password , Entropy : roundToXDigits ( minEntropy , 3 ) , MatchSequence : matchSequenceCopy , CrackTime : crackTime , CrackTimeDisplay : displayTime ( crackTime ) , Score : crackTimeToScore ( crackTime ) } }
/*
MinimumEntropyMatchSequence returns the minimum entropy

    Takes a list of overlapping matches, returns the non-overlapping sublist with
    minimum entropy. O(nm) dp alg for length-n password with m candidate matches.
*/
/ * MinimumEntropyMatchSequence returns the minimum entropy