Классическая задача на систематический перебор. Дан маленький фиксированный
алфавит charset и короткий максимум длины. Нужно перебрать все строки над
этим алфавитом длиной от 0 до MaxLen и вернуть первую, для которой заданный
предикат-«оракул» (здесь — совпадение MD5 с известным значением) вернёт true.
Это стандартное учебное упражнение на backtracking и аккуратную работу с
аллокациями: кандидатов около миллиона, и наивная сборка каждого через
конкатенацию строк на порядок медленнее генерации в одном буфере.
var charset = []byte{'x', 'y', 'z', 'w', '4', '5', '6'}
const MaxLen = 7
// Recover перебирает строки над charset длиной 0..MaxLen в порядке
// возрастания длины и возвращает первую, для которой match(candidate) == true.
// Если такой нет — "", false.
func Recover(match func([]byte) bool) (string, bool)
Пример применения (восстановление короткого тестового пароля по его хэшу):
want := md5.Sum([]byte("xyz555w"))
got, ok := Recover(func(b []byte) bool { return md5.Sum(b) == want })
// got == "xyz555w", ok == true
Требования
- Перебор в порядке возрастания длины: сначала
"", потом все длины 1, затем 2
и т. д. Среди одной длины порядок — лексикографический по индексам в charset.
match вызывается максимум 7⁰ + 7¹ + … + 7⁷ ≈ 960 тыс. раз и получает срез,
действительный только на время вызова (буфер переиспользуется, нужна копия — делайте её сами).- Весь перебор должен укладываться в доли секунды: генерируй кандидатов в одном
буфере, без
fmt.Sprintf и конкатенаций строк на каждого.
Устно: как распараллелить перебор на все ядра и как корректно остановить
остальные горутины, когда ответ найден?