104 lines
4.6 KiB
VB.net
104 lines
4.6 KiB
VB.net
' Recursively iterates (increments) iteration array, returns -1 when out of "digits".
|
|
Function plusOne(iAry() As Integer, spot As Integer) As Integer
|
|
Dim spotLim As Integer = If(spot = 0, 1, 2) ' The first "digit" has a lower limit.
|
|
If iAry(spot) = spotLim Then ' Check if spot has reached limit
|
|
If spot = 0 Then Return -1 ' No previous spot to increment, so indicate completed.
|
|
iAry(spot) = 0 ' Reset current spot, and
|
|
Return plusOne(iAry, spot - 1) ' Increment previous spot.
|
|
Else
|
|
iAry(spot) += 1 ' Increment current spot.
|
|
End If
|
|
Return spot
|
|
End Function
|
|
|
|
' Returns string sequence of operations from iAry and terms string
|
|
Function generate(iAry() As Integer, terms As String) As String
|
|
Dim operations As String() = {"", "-", "+"} ' Possible operations.
|
|
generate = ""
|
|
For i As Integer = 0 To iAry.Count - 1
|
|
generate &= operations(iAry(i)) & Mid(terms, i + 1, 1).ToString()
|
|
Next
|
|
End Function
|
|
|
|
' Returns evaluation of string sequence
|
|
Function eval(sequence As String) As Integer
|
|
eval = 0
|
|
Dim term As Integer = 0, operation As Integer = 1
|
|
For Each ch As Char In sequence
|
|
Select Case ch
|
|
Case "-", "+" ' New operation detected, apply previous operation to term,
|
|
eval += If(operation = 0, -term, term) : term = 0 ' and reset term.
|
|
operation = If(ch = "-", 0, 1) ' Note next operation.
|
|
Case Else ' Digit detected, increase term.
|
|
term = term * 10 + Val(ch)
|
|
End Select
|
|
Next
|
|
eval += If(operation = 0, -term, term) ' Apply final term.
|
|
End Function
|
|
|
|
' Sorts a pair of List(Of Integer) by the first
|
|
Sub reSort(ByRef first As List(Of Integer), ByRef second As List(Of Integer))
|
|
Dim lou As New List(Of ULong) ' Temporary list of ULong for sorting.
|
|
For i As Integer = 0 To first.Count - 1
|
|
lou.Add((CULng(first(i)) << 32) + second(i)) ' "Pack" list items.
|
|
Next
|
|
lou.Sort()
|
|
For k As Integer = 0 To first.Count - 1
|
|
first(k) = lou(k) >> 32 ' "Unpack" first list item.
|
|
second(k) = lou(k) And &H7FFFFFFF ' "Unpack" second list item.
|
|
Next
|
|
End Sub
|
|
|
|
' Returns first result not in sequence, assumes passed list is sorted before call,
|
|
' uses binary search algo.
|
|
Function firstMiss(loi As List(Of Integer))
|
|
Dim low As Integer = 0, high As Integer = loi.Count - 1, middle = (low + high) \ 2
|
|
Do
|
|
If loi(middle) = middle Then low = middle + 1 Else high = middle - 1
|
|
middle = (low + high) \ 2
|
|
Loop Until high <= low
|
|
Return middle + If(loi(middle) = middle, 1, 0)
|
|
End Function
|
|
|
|
' Iterates through all possible operations,
|
|
' uses a pair of List (of Integer) to tabulate solutions.
|
|
Sub Solve100(Optional terms As String = "123456789",
|
|
Optional targSum As Integer = 100,
|
|
Optional highNums As Integer = 10)
|
|
Dim lastDig As Integer = Len(terms) - 1 ' The final "digit".
|
|
Dim iAry() As Integer = New Integer(lastDig) {} ' Iterations array.
|
|
Dim seq As String ' Sequence of numbers and operations.
|
|
Dim sVal As Integer ' Sequence value.
|
|
Dim sCnt As Integer = 1 ' Solution count (targSum).
|
|
Dim res As New List(Of Integer) ' List of results.
|
|
Dim tally As New List(Of Integer) ' Tally of results.
|
|
Console.WriteLine("List of solutions that evaluate to 100:")
|
|
Do ' Tabulate results until digits are exhausted.
|
|
seq = generate(iAry, terms) ' Obtain next expression.
|
|
sVal = eval(seq) ' Obtain next evaluation.
|
|
If sVal >= 0 Then ' Don't bother saving the negative results.
|
|
If res.Contains(sVal) Then tally(res.IndexOf(sVal)) += 1 _
|
|
Else res.Add(sVal) : tally.Add(1)
|
|
If sVal = targSum Then _
|
|
Console.WriteLine(" {0,2} {1}", sCnt, seq) : sCnt += 1
|
|
End If
|
|
Loop Until plusOne(iAry, lastDig) < 0
|
|
reSort(tally, res) ' Sort by tally to find result with the most solutions.
|
|
Console.WriteLine("The sum that has the the most solutions is {0}, (at {1}).",
|
|
res.Last, tally.Last)
|
|
reSort(res, tally) ' Sort by result to find first missing result and top results.
|
|
Console.WriteLine("The lowest positive sum that can't be expressed is {0}.",
|
|
firstMiss(res))
|
|
Console.WriteLine("The ten highest numbers that can be expressed are:")
|
|
res.Reverse() ' To let us take the last items for output.
|
|
sCnt = 0 ' Keep track of items displayed (for formatting).
|
|
For Each item As Integer In res.Take(highNums)
|
|
Console.Write("{0, -11}", item)
|
|
sCnt = (sCnt + 1) Mod 5 : If sCnt = 0 Then Console.WriteLine()
|
|
Next
|
|
End Sub
|
|
|
|
Sub Main()
|
|
Solve100() ' if interested, try this: Solve100("987654321")
|
|
End Sub
|