I have a variable called valorInicial with values from 0 to 9. This variable can have a variable length, ranging from 9 to 60 characters.
To this variable valorInicial, I select 3 values and subtract -1, -2, and -3 from them, considering that if it goes below zero, it continues at 9, for example, 1-3=8 or 0-1=9. These are circular subtractions.
Then, we create the variable valorRestado with valorInicial variable subtracted by the selected values.
Then, we shuffle valorInicial. Therefore, valorInicial is disordered with respect to valorRestado.
I would need invaluable help to create a function that detects which values of valorInicial have been subtracted and how much has been subtracted from each value, considering that the subtraction is done with the characteristic that if it goes below 0, it continues at 9, and also that valorInicial is disordered with respect to valorRestado, and that the only possible subtractions are -1, -2, and -3.
We can take this example:
valorInicial: 988735928
9 is subtracted by 1 and becomes 8
2 is subtracted by 2 and becomes 0
8 is subtracted by 3 and becomes 5
valorRestado: 858735908
9: Two in valorInicial, ONE in valorRestado
8: Three in valorInicial, three in valorRestado
7: One in valorInicial, one in valorRestado
6: Zero in valorInicial, zero in valorRestado
5: One in valorInicial, TWO in valorRestado
4: Zero in valorInicial, zero in valorRestado
3: One in valorInicial, one in valorRestado
2: One in valorInicial, ZERO in valorRestado
1: Zero in valorInicial, zero in valorRestado
0: Zero in valorInicial, ONE in valorRestado
Then valorInicial is shuffled - valorInicial: 753982898
A logic that I have thought is as follows:
First, we have to check the frequency of each value in each variable, both in valorInicial and valorRestado.
If the frequency of the value in valorRestado is less than the frequency of the value in valorInicial, we know that that value of valorInicial has been subtracted, and as many times as the difference is. If there are 3 ones in valorInicial and 1 one in valorRestado, we know that two ones have been subtracted from valorInicial, and we know then that there must be two ones with two different subtractions, for example, one 1 has been subtracted by -1 and another 1 has been subtracted by -3.
If the frequency of the value in valorRestado is greater than the frequency of the value in valorInicial, we know that the result of the subtractions from valorInicial has resulted in that value, as many times as the difference is. If in valorInicial there are 2 fives and in valorRestado there are 4 fives, we know that the result of the subtraction of two values of valorInicial has resulted in 5, for example, there could be a value 6 that has been subtracted by -1 and a value 8 that has been subtracted by -3.
With this, the code has to be capable of controlling the decreases and the increases, and with that data, and knowing that only the possibility of subtracting -1, -2, and -3 exists, it has to find the values of valorInicial that have been subtracted and how much has been subtracted from each one.
We have to take into account, and here is the key to complexity, that we have to evaluate the set, because, for example, there may be two values whose frequency has decreased and two values whose frequency has increased. And with that data, we have to be able to find the 3 values that have been subtracted, and find out how much has been subtracted from each value, whether -1, -2, or -3.
First, we have to find the values that have decreased to establish the easy-to-observe values, and then we have to observe the values that have increased so that, knowing those that have decreased and are already established, and the values that have increased, which are the result of the subtraction, find the remaining values.
There may be particularities where the values are not directly taken out, since when subtracting, they become other values present in valorInicial, which in turn have been subtracted. There may be substitutions. In the example given, that happens. We have to use a complex comparison logic to correctly find the values and their subtractions. It's not just seeing which value has decreased its frequency and that's it. We have to do a deeper and more exhaustive analysis, and the answer can only be given when it is complete. That is, it has to find the 3 values and their subtractions, and the subtractions can only be -1, -2, and -3.
Always remembering that the subtraction when it is below zero continues at 9, for example, 1-3=8, 2-5=7
In the given example, the result of the MsgBox should say something like this:
9 is subtracted by 1
2 is subtracted by 2
8 is subtracted by 3
And to find this result, it has to do a thorough and deep analysis, not just compare the frequencies and that's it. As we have discussed, it has to compare frequencies of valorInicial that have decreased with respect to valorRestado, frequencies of restado that have increased with respect to valorInicial, and then analyze the data obtained and find the 3 values and their corresponding subtractions.
The code that I have tried is the following:
Private Sub Button3_Click(sender As Object, e As EventArgs) Handles Button3.Click
Dim valorInicial As String = "982079171"
Dim restado As String = "982979978"
Dim resultadoFuncion As New List(Of String)
resultadoFuncion = ReconstruirValorInicial(valorInicial, restado)
' Concatenar todos los elementos de la lista en una cadena
Dim mensaje As String = String.Join(vbCrLf, resultadoFuncion)
' Mostrar la cadena en un MsgBox
MsgBox(mensaje, MsgBoxStyle.OkOnly, "Valores de la lista")
End Sub
Function ReconstruirValorInicial(valorInicial As String, restado As String) As List(Of String)
Dim frecuenciaInicial As New Dictionary(Of Char, Integer)
Dim frecuenciaRestado As New Dictionary(Of Char, Integer)
Dim resultados As New List(Of String)
' Contar frecuencia de cada dígito
For i As Integer = 0 To valorInicial.Length - 1
Dim c As Char = valorInicial.Substring(i, 1)
If frecuenciaInicial.ContainsKey(c) Then
frecuenciaInicial(c) += 1
Else
frecuenciaInicial(c) = 1
End If
Next
For i As Integer = 0 To restado.Length - 1
Dim c As Char = restado.Substring(i, 1)
If frecuenciaRestado.ContainsKey(c) Then
frecuenciaRestado(c) += 1
Else
frecuenciaRestado(c) = 1
End If
Next
' Identificar dígitos restados y determinar la cantidad a restar
For i As Integer = 0 To valorInicial.Length - 1
Dim c As Char = valorInicial.Substring(i, 1)
Dim frecuenciaInicialDigito As Integer = frecuenciaInicial(c)
Dim frecuenciaRestadoDigito As Integer = 0
If frecuenciaRestado.ContainsKey(c) Then
frecuenciaRestadoDigito = frecuenciaRestado(c)
End If
Dim cantidadARestar As Integer
If frecuenciaRestadoDigito <= frecuenciaInicialDigito Then
' Se ha restado
cantidadARestar = frecuenciaInicialDigito - frecuenciaRestadoDigito
End If
' Almacenar resultados
If cantidadARestar > 0 Then
resultados.Add(c & " : " & cantidadARestar.ToString & " (Posición: " & (i + 1).ToString & ")")
End If
Next
Return resultados
End Function
But it doesn't work correctly, as it doesn't have the deep and exhaustive comparison logic, nor does it control what has been subtracted from each value.
But it doesn't work correctly, as it doesn't have the deep and exhaustive comparison logic, nor does it control what has been subtracted from each value.
The logic must be looking at the frequencies that decrease and increase
InitialValue: 988735928 From 9 you subtract 1 it becomes 8 2 is subtracted from 2, it becomes 0 3 is subtracted from 8 and it becomes 5 subtracted: 858735908 9: two in initial value, ONE in subtraction 8: three in initial value, three in subtraction 7: one in initialvalue, one in subtraction 6: zero in initialvalue, zero in subtraction 5: one in initialvalue, TWO in subtraction 4: zero in initialvalue, zero in subtraction 3: one in initialvalue, one in subtracted 2: one in initialvalue, ZERO in subtraction 1: zero in initialvalue, zero in subtraction 0: zero in initialvalue, ONE in subtraction
First we see that 9 has reduced, and 2 has reduced. with which we know directly that the 9 has been subtracted and the 2 has been subtracted.
then we see that the 5 and the 0 have increased, it means that when performing the subtractions, one of them has become 5 and another has become 0, then we have to control that the possible subtractions are one -1 another -2 and another -3. so we have to look at the options available.
If -1 is subtracted from 2, it becomes a 1 -> does not fit, discarded
If -3 is subtracted from 2, it becomes a 9 -> does not fit, discarded
If -2 is subtracted from 2 it becomes a 0 -> it fits
If -3 is subtracted from 9 it becomes a 5 -> it fits, but...
there would be a number left to subtract -1 -> there is NO combination that fits, discarded
If -2 is subtracted from 2 it becomes a 0 -> it fits
If -1 is subtracted from 9 it becomes an 8-> it could fit if...
If -3 is subtracted from 8, it becomes a 5 -> it fits! found the combination!
My solution converts the digits from the String Chars to Integers. I also use an array with the index range 0 .. 9 to store the frequency of each digit. This is very handy as the digit is given by the array index.
Asc(c) - Asc("0"c) gets the digit value as integer from a character.
Dim initialFrequency = New Integer(9) {}
Dim resultingFrequency = New Integer(9) {}
' Count frequency of each digit
For Each c In initialValue
initialFrequency(Asc(c) - Asc("0"c)) += 1
Next
For Each c In reducedValue
resultingFrequency(Asc(c) - Asc("0"c)) += 1
Next
Then we create lists of changed initial digits and resulting digits. If the frequency is decreasing, we have an initial digit, if the frequency is increasing, we have a resulting digit.
We also create a list of unchanged digits. Those are used later to complement sets of changed digits smaller than 3 because sometimes more subtractions than apparently changed digits might yield results.
' Get lists of changed and unchanged digits
Dim initialDigits = New List(Of Integer)()
Dim resultingDigits = New List(Of Integer)()
Dim unchangedDigits = New List(Of Integer)()
For i = 0 To 9
Dim changes = resultingFrequency(i) - initialFrequency(i)
If changes < 0 Then 'initial > resulting
For j = 0 To -changes - 1
initialDigits.Add(i)
Next
For j = 0 To initialFrequency(i) + changes - 1
unchangedDigits.Add(i)
Next
ElseIf changes > 0 Then 'resulting > initial
For j = 0 To changes - 1
resultingDigits.Add(i)
Next
For j = 0 To resultingFrequency(i) - changes - 1
unchangedDigits.Add(i)
Next
Else
For j = 0 To initialFrequency(i) - 1
unchangedDigits.Add(i)
Next
End If
Next
Then comes the core of the algorithm. The idea is to get all permutations of possible subtractions and to apply them to the initial changed digits and to compare the result with the list of the resulting digits. If the sequences are equivalent, we have a hit.
The permutations depend on the number of changed digits. This helper function returns these permutations:
' First index is the permutation, second index is the digit affected
Private Function GetSubtractionPermutations(count As Integer) As Integer(,)
Select Case count
Case 1
Return New Integer(2, 0) { ' One digit changed
{-1},
{-2},
{-3}}
Case 2
Return New Integer(5, 1) { ' Two digits changed
{-1, -2},
{-1, -3},
{-2, -1},
{-2, -3},
{-3, -1},
{-3, -2}}
Case 3
Return New Integer(5, 2) { ' Three digits changed
{-1, -2, -3},
{-1, -3, -2},
{-2, -1, -3},
{-2, -3, -1},
{-3, -1, -2},
{-3, -2, -1}}
Case Else
Return New Integer(-1, -1) {}
End Select
End Function
I also mentioned complementing sets smaller than 3. This is another helper method doing it. It returns a list of tuples of lists of initial and resulting digits:
' If the count of changing digits is less than 3, we create synthetic sets with more digits
' to find more intricate solutions.
Private Function ComplementSets(ByVal initialDigits As List(Of Integer),
ByVal resultingDigits As List(Of Integer),
ByVal unchangedDigits As List(Of Integer)
) As List(Of (intial As List(Of Integer), resulting As List(Of Integer)))
Dim sets = New List(Of (List(Of Integer), List(Of Integer))) From {
(initialDigits, resultingDigits)
}
Select Case initialDigits.Count
Case 1 ' Create 2-sets and from those also 3-sets (recursively)
For Each d In unchangedDigits.Distinct()
' Create 2-set
Dim i2 = New List(Of Integer)(initialDigits)
Dim r2 = New List(Of Integer)(resultingDigits)
i2.Add(d)
r2.Add(d)
sets.Add((i2, r2))
'Create 3-sets recursively
Dim u = New List(Of Integer)(unchangedDigits)
u.Remove(d)
Dim sets3 = ComplementSets(i2, r2, u)
sets.AddRange(sets3)
Next
Case 2 ' Create 3-sets
For Each d In unchangedDigits.Distinct()
Dim i3 = New List(Of Integer)(initialDigits)
Dim r3 = New List(Of Integer)(resultingDigits)
i3.Add(d)
r3.Add(d)
sets.Add((i3, r3))
Next
End Select
Return sets
End Function
Now, we can write the algorithm:
Dim complementedDigitSets =
ComplementSets(initialDigits, resultingDigits, unchangedDigits)
Dim results = New HashSet(Of String)()
Dim testResult = New List(Of Integer)()
For Each complementedSet In complementedDigitSets
Dim initial = complementedSet.intial
Dim resulting = complementedSet.resulting
Dim permutations = GetSubtractionPermutations(initial.Count)
resulting.Sort()
For p = 0 To permutations.GetLength(0) - 1
testResult.Clear()
For i = 0 To initial.Count - 1
testResult.Add((initial(i) + permutations(p, i) + 10) Mod 10)
Next
testResult.Sort()
If testResult.SequenceEqual(resulting) Then
results.Add(String.Join(", ", initial.[Select](Function(d, i) $"{d}{permutations(p, i)}={(d + permutations(p, i) + 10) Mod 10}").Order()))
End If
Next
Next
Note that a HashSet eliminates duplicates. Since I order the strings representing the resulting subtractions, this will eliminate equivalent results appearing in a different order. (If you want to see what I mean, simply remove the .Order() part.)
We can get the "circular subtraction" with the modulo operator: (d - x + 10) Mod 10. I am actually doing the addition of a negative number instead of a subtraction.
Putting this together we get this function:
Private Function FindSubtractions(initialValue As String, reducedValue As String) As List(Of String)
Dim initialFrequency = New Integer(9) {}
Dim resultingFrequency = New Integer(9) {}
If initialValue.Length <> reducedValue.Length Then
Throw New ArgumentException("initialValue and reducedValue must have the same length")
End If
' Count frequency of each digit
For Each c In initialValue
initialFrequency(Asc(c) - Asc("0"c)) += 1
Next
For Each c In reducedValue
resultingFrequency(Asc(c) - Asc("0"c)) += 1
Next
' Get lists of changed and unchanged digits
Dim initialDigits = New List(Of Integer)()
Dim resultingDigits = New List(Of Integer)()
Dim unchangedDigits = New List(Of Integer)()
For i = 0 To 9
Dim changes = resultingFrequency(i) - initialFrequency(i)
If changes < 0 Then 'initial > resulting
For j = 0 To -changes - 1
initialDigits.Add(i)
Next
For j = 0 To initialFrequency(i) + changes - 1
unchangedDigits.Add(i)
Next
ElseIf changes > 0 Then 'resulting > initial
For j = 0 To changes - 1
resultingDigits.Add(i)
Next
For j = 0 To resultingFrequency(i) - changes - 1
unchangedDigits.Add(i)
Next
Else
For j = 0 To initialFrequency(i) - 1
unchangedDigits.Add(i)
Next
End If
Next
If initialDigits.Count > 3 Then
Console.WriteLine("Every subtraction -1, -2 and -3 can occur only once")
ElseIf initialDigits.Count <> resultingDigits.Count Then
Console.WriteLine("The size of the set of initial and resulting changed digits must be equal")
ElseIf initialDigits.Count = 0 Then
Return New List(Of String)
End If
If initialDigits.Count + unchangedDigits.Count <> initialValue.Length Then
Console.WriteLine("There's somthing wrong with counting the digits")
End If
Dim complementedDigitSets =
ComplementSets(initialDigits, resultingDigits, unchangedDigits)
Dim results = New HashSet(Of String)()
Dim testResult = New List(Of Integer)()
For Each complementedSet In complementedDigitSets
Dim initial = complementedSet.intial
Dim resulting = complementedSet.resulting
Dim permutations = GetSubtractionPermutations(initial.Count)
resulting.Sort()
For p = 0 To permutations.GetLength(0) - 1
testResult.Clear()
For i = 0 To initial.Count - 1
testResult.Add((initial(i) + permutations(p, i) + 10) Mod 10)
Next
testResult.Sort()
If testResult.SequenceEqual(resulting) Then
results.Add(String.Join(", ", initial.[Select](Function(d, i) $"{d}{permutations(p, i)}={(d + permutations(p, i) + 10) Mod 10}").Order()))
End If
Next
Next
Return results.Order().ToList()
End Function
You will note that I also added a test, checking whether the number of changed digits is plausible.
We can test it with this console application:
Dim examples = {
(initial:="982079171", resulting:="982979978"),
(initial:="978465321", resulting:="978465118"),
(initial:="987301037", resulting:="957191037"),
(initial:="123456789", resulting:="123456759"),
(initial:="123479", resulting:="123467")}
For Each example In examples
Console.WriteLine($"{example.initial} --> {example.resulting}")
Dim results = FindSubtractions(example.initial, example.resulting)
For Each result In results
Console.WriteLine(result)
Next
Console.WriteLine()
Next
It prints:
982079171 --> 982979978
0-1=9, 1-2=9, 1-3=8
978465321 --> 978465118
1-3=8, 2-1=1, 3-2=1
2-3=9, 3-2=1, 9-1=8
987301037 --> 957191037
0-1=9, 3-2=1, 8-3=5
123456789 --> 123456759
6-1=5, 8-2=6
7-2=5, 8-1=7
8-3=5
123479 --> 123467
7-1=6, 9-2=7
9-3=6