' version 11-10-2016
' compile with: fbc -s console

' Brute force

' adopted from "Sorting algorithms/Shell" sort Task
Sub shellsort(s() As String)
  ' sort from lower bound to the highter bound
  Dim As UInteger lb = LBound(s)
  Dim As UInteger ub = UBound(s)
  Dim As Integer done, i, inc = ub - lb

  Do
    inc = inc / 2.2
    If inc < 1 Then inc = 1

    Do
      done = 0
      For i = lb To ub - inc
        If s(i) > s(i + inc) Then
          Swap s(i), s(i + inc)
          done = 1
        End If
      Next
    Loop Until done = 0

  Loop Until inc = 1

End Sub

' ------=< MAIN >=------

Dim As UInteger x, y, count, c, sum
Dim As UInteger cube(1290)
Dim As String result(), str1, str2, str3
Dim As String buf11 = Space(11), buf5 = Space(5)
ReDim result(900000)    ' ~1291*1291\2

' set up the cubes
Print : Print " Calculate cubes"
For x = 1 To 1290
  cube(x) = x*x*x
Next

' combine and store
Print : Print " Combine cubes"
For x = 1 To 1290
  For y = x To 1290
    sum = cube(x)+cube(y)
    RSet buf11, Str(sum) : str1 = buf11
    RSet buf5, Str(x) : str2 = buf5
    RSet buf5, Str(y) : Str3 = buf5
    result(count)=buf11 + " = " + str2 + " ^ 3 + " + str3 + " ^ 3"
    count = count +1
  Next
Next

count= count -1
ReDim Preserve result(count) ' trim the array

Print : Print " Sort (takes some time)"
shellsort(result())   ' sort

Print : Print " Find the Taxicab numbers"
c = 1 ' start at index 1
For x = 0 To count -1
  ' find sums that match
  If Left(result(x), 11) = Left(result(x + 1), 11) Then
    result(c) = result(x)
    y = x +1
    Do    ' merge the other solution(s)
      result(c) = result(c) + Mid(result(y), 12)
      y = y +1
    Loop Until Left(result(x), 11) <> Left(result(y), 11)
    x = y -1 ' let x point to last match result
    c = c +1
  End If
Next

c = c -1
Print : Print " "; c; " Taxicab numbers found"
ReDim Preserve result(c) ' trim the array again

cls
Print : Print " Print first 25 numbers" : Print
For x = 1 To 25
  Print result(x)
Next

Print : Print " The 2000th to the 2006th" : Print
For x = 2000 To 2006
  Print result(x)
Next


' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End