Я считаю, что нашел достойный алгоритм, который должен справиться с этим для вас. Я заранее прошу прощения, если какое-либо объяснение недостаточно подробное, но многое из этого пришло к интуиции, которую трудно объяснить.
Я начал с более упрощенных случаев, выяснив способ получения наименьшего числа образцов из сравнения. Для моих примеров я буду сравнивать 211234 с 245245.
Подумав немного, я решил, что вам нужно взять диапазон чисел от меньшего числа до 9 и обработать специальный случай для младшей цифры в меньшем числе. Чтобы объяснить более подробно, в числе 211234 идеальным является представление последней цифры в виде X, но мы можем сделать это только для случаев, когда цифра может быть [0-9] единственным случаем в этом примере, где мы не можем использовать [0-9], когда наша десятка равна 3, потому что у нас есть нижний предел 4. Затем эта логика распространяется вверх по остальной части числа, когда мы направляемся к самой значимой цифре. Таким образом, для цифры десятков в следующем случае у нас есть нижняя граница, основанная на предыдущем примере 4, потому что мы обрабатываем случай, когда мы специально разрешаем 3. Таким образом, для нашего диапазона десятков мы получаем 4-9, потому что следующая цифра не ограничивает наш диапазон.
На самом деле мы не будем ограничены до самой значимой цифры, которая ограничена числами в диапазоне между числами, которые мы сравниваем. Поработав вручную над несколькими проблемами, я заметил некоторую структуру пирамиды X в тех случаях, когда цифры значительно различались:
compare: 211234
to: 245245
21123[4-9]
2112[4-9]X
211[3-9]XX
21[2-9]XXX
2[2-3]XXXX
24[0-4]XXX
245[0-1]XX
2452[0-3]X
24514[0-5]
Это был мой первый намек на то, как с этим справиться. Начиная с наименее значимого движения вверх, используя симметрию, но обращаясь к случаю, когда мы достигаем «вершины пирамиды». Этот пример прост, хотя есть много угловых случаев, которые могут вызвать проблемы. Для краткости я не буду вдаваться в подробности для каждого, но я дам краткое объяснение для каждого:
Что вы делаете, когда две сравниваемые цифры имеют между собой одно число, например, между 4 и 6?
В этом случае просто используйте одну цифру вместо диапазона.
Что вы делаете, когда между двумя сравниваемыми цифрами нет числа между ними, например, между 4 и 5?
В этом случае отбросьте строку, в которой вы будете обрабатывать числа между цифрами, поскольку все случаи будут обрабатываться явно.
Что вы делаете, когда минимальное число в диапазоне составляет 8?
В этом случае, когда мы добавляем 1 к числу, чтобы получить нижнюю границу для диапазона, мы получаем 9, что означает, что мы можем просто заменить на 9 вместо диапазона [9-9]
Что вы делаете, когда минимальное число в диапазоне составляет 9?
В этом случае мы просто не заботимся о том, чтобы обрабатывать это число, так как при обработке следующей цифры вверх оно должно охватываться использованием X
Я уверен, что мне не хватает некоторых угловых случаев, которые я обрабатываю в коде, который я просто не думал включать в этот список. Я хочу уточнить любую часть кода, если вы просто оставите комментарий с вопросом.
Ниже мой удар по Го. Возможно, это может быть немного более СУХОЙ, но это то, что я придумал, немного поигравшись. Я также довольно новичок в Go, поэтому, пожалуйста, сообщите мне о любых нарушениях духа в комментариях, и я исправлю их.
Я не гарантирую, что это будет обрабатывать каждый случай, но он обрабатывал каждый случай, который я бросил в него. Вам решать превратить его в скрипт, который содержит 2 строки;)
Редактировать: Я только что понял из примера в вопросе (который по какой-то причине я никогда не запускал), что это не всегда сводит предоставленный диапазон к наименьшему количеству выходов, но это должно всегда дайте образцы, которые покрывают каждый случай. Несмотря на этот недостаток, я считаю, что для вас это хороший шаг в правильном направлении. Я обновлю ответ, если найду время, чтобы привести его к сжатию, когда предыдущий диапазон равен 1-9, а особый случай - 0. Наилучшее средство, которое может оказаться после первоначального поколения, сжимая эти случаи «вручную».
package main
import (
"strconv"
"fmt"
)
func getStringFromMinAndMax(min int, max int) (string, bool){
minstr := strconv.Itoa(min)
maxstr := strconv.Itoa(max)
if max == min {
return minstr, false
}
if max < min{
return minstr, false
}
return "["+minstr+"-"+maxstr+"]", true
}
func main(){
str1 := "211234"
str2 := "245245"
diffLength := 0
for i := 0; i < len(str1); i++{
diffLength = i+1
number1, _ := strconv.Atoi(str1[:len(str1)-i-1])
number2, _ := strconv.Atoi(str2[:len(str2)-i-1])
if number1 == number2 {
break
}
}
elems := (diffLength * 2)-1
output := make([]*[]string, elems+1)
for i := 0; i < elems; i++ {
newSlice := make([]string, diffLength)
output[i] = &newSlice
}
for digit := 0; digit < diffLength; digit++ {
for j := 0; j < diffLength; j++ {
if j == digit {
if output[j] != nil {
min, _ := strconv.Atoi(string(str1[len(str1)-(digit+1)]))
max := 9
if digit == diffLength-1 {
max, _ = strconv.Atoi(string(str2[len(str1)-(digit+1)]))
max = max - 1
}
if digit != 0{
min = min+1
}
if min < 10 {
maxchar := strconv.Itoa(max)[0]
minchar := strconv.Itoa(min)[0]
newVal, safe := getStringFromMinAndMax(min, max)
if digit == diffLength-1 && !safe && (str1[len(str1)-(digit+1)] == maxchar || str2[len(str2)-(digit+1)] == minchar) {
output[j] = nil
} else {
(*output[j])[diffLength-digit-1] = newVal
}
} else {
output[j] = nil
}
}
if j != diffLength-1 && output[elems-1-j] != nil {
min := 0
max, _ := strconv.Atoi(string(str2[len(str1)-(digit+1)]))
if digit != 0{
max = max-1
}
if max >= 0{
newVal, _ := getStringFromMinAndMax(min, max)
(*output[elems-1-j])[diffLength-digit-1] = newVal
} else {
output[elems-1-j] = nil
}
}
} else {
if j > digit {
if output[j] != nil {
(*output[j])[diffLength-digit-1] = "X"
}
if j != diffLength-1 && output[elems-1-j] != nil {
(*output[elems-1-j])[diffLength-digit-1] = "X"
}
} else {
if output[j] != nil {
(*output[j])[diffLength-digit-1] = string(str1[len(str1)-digit-1])
}
if j != diffLength-1 && output[elems-1-j] != nil {
(*output[elems-1-j])[diffLength-digit-1] = string(str2[len(str2)-digit-1])
}
}
}
}
}
for _, list := range output {
if list != nil{
if len(str1) != diffLength{
fmt.Printf(str1[:len(str1)-diffLength])
}
for _, element := range *list {
fmt.Printf(element)
}
fmt.Printf("\n")
}
}
}
Сноска:
diffLength - это количество символов в конце строк, которые отличаются, я не мог придумать лучшего способа получить это число, чем в сценарии ... - Я устанавливаю вывод на
nil, я говорю: «Этот будет обработан явно, поэтому выбросьте его» * 1066 *
j - это переменная, для которой я устанавливаю вывод ... Но это также отражается в нижней части, поэтому я не мог придумать краткое имя, чтобы дать его, поэтому я оставил его j. digit отслеживает, какую цифру справа мы модифицируем