Weekly Liberty BASIC Challenge #3: Geometric progression

[svajoklis]

Welcome to week 3!

First - quick note about the score. The way I try to tally it up is that I add your new score to your old score and then put you at the end of the list of people with same score. That way people who scored more earlier are prioritized.

Now for your submissions:

Rod's solution got 5/9 test cases provided right, so it results in a score of 0.55. Tenochtitlanuk added a brute force-like solution, so as I previously mentioned it would get a 0.1. Since it does a bit of heuristics to determine at least the range of numbers to check, so I bumped it up to 0.2. (Let me know if you think the score should be adjusted, I don't want to be the sole judge here!) Timur77 submitted two solutions that both worked well. Sorry, but I only have a single point to give out! I checked the last one and it passed all the tests. Thanks again for the extra test cases. I think I will do the same thing this week where I post only a few test cases initially and as the week goes along I'll try to post more just to keep you on the edge to find possible bugs you might have missed.

I'll go ahead with an another olympiad level task this week. Let me know if they are maybe too hard and you want something easier like the week #1 task. I think olympiad tasks are more interesting, since with tasks like the #1 task it's more about finding the "trick" behind it and exploiting it, where here it's more of a creative task.

---

Weekly Challenge problem #3: Geometric progression [level: olympiad]

You are given a list of natural numbers that are known to belong to a geometric progression. Natural numbers are numbers that are whole and larger than 0. Geometric progression is a sequence of numbers, where each next element after the first is the product of previous element and the common ratio. Find a geometric progression, that has all the numbers in a given set, if the common ratio can only be a whole number. Print out the common ratio of the sequence. If there can be more than one possible common ratio, print the highest one. Also print all found geometric progression members starting with the lowest given and ending with the highest given.

Note: follow the task input and output formats exactly with no extraneous characters. Your program should be able to handle multiple sets as displayed below. This lets you immediately test multiple cases with a single run of the program.

Data format: File "challenge3_data.txt". First line specifies how many sets of numbers there will be (1 <= n <= 10). Subsequent lines consist of the size of the single number set you are given (2 <= m <= 10), rest of the numbers on the line are numbers of the set.

Output: Print your results on the screen.

Example:

Input (challenge3_data.txt)
Output (screen)
2
3 128 8 512
4 1500 300 37500 12
ratio = 4
8 32 128 512
ratio = 5
12 60 300 1500 7500 37500
4
3 1 4 32
3 7 28 224
3 7 112 7168
3 1 6 216
ratio = 2
1 2 4 8 16 32
ratio = 2
7 14 28 56 112 224
ratio = 4
7 28 112 448 1792 7168
ratio = 6
1 6 36 216
2
4 82055753 37349 17 485537
3 7 45927 413343
ratio = 13
17 221 2873 37349 485537 6311981 82055753
ratio = 9
7 63 567 5103 45927 413343

---

Good luck!

Previous week's challenge:
libertybasiccom.proboards.com/thread/1068/weekly-liberty-basic-challenge-2

Hall of Fame:

		Total score	Score in last task
	timur77	2	1
	svajoklis	2	1
	Rod	1.55	0.55
	tenochtitlanuk	1.2	0.2

[Rod]

open "n.txt" for output as #1
#1, "2"
#1, "3 128 8 512"
#1, "4 1500 300 37500 12"
close #1

open "n.txt" for input as #1
line input #1,nc$
for n=1 to val(nc$)
   line input #1, c$
   num=val(word$(c$,1," "))
   dim num(num)
   for m=1 to num
       num(m)=val(word$(c$,m+1," "))
   next
   sort num(,0,num
   for m=num to 2 step -1
       x=num(m)/num(m-1)
       if z=0 then z=x
       if x<z then z=x
   next
   print "Ratio = ";z
   m=1
   a=num(m)
   print a;" ";
   while a<num(num)
       a=a*z
       print a;" ";
   wend
   print
   z=0
next
close #1
end


[svajoklis]

The second set trips up your solution, since the ratio is good, but the output sequence looks nothing like the one in the solution. The initial number in that sequence is 12 and others should be 12 multiplied by 5 over and over again ending with 37500 I get '1 5 25 125 625 3125 15625 78125'

[tsh73]

I took file code form Rod
But I added another test which Rod's program fails.
("3 1 4 32")
Then I started to think and found where my program fails again
("3 1 6 216")

Now my program big and fat and ugly but it solves all my tests.
ratio = 4
8 32 128 512
ratio = 5
12 60 300 1500 7500 37500
ratio = 2
1 2 4 8 16 32
ratio = 2
7 14 28 56 112 224
ratio = 4
7 28 112 448 1792 7168
ratio = 6
1 6 36 216


'geometric progression task

'a$= "4 1500 300 37500 12"
'a$= "3 128 8 512"
'a$= "3 1 4 32"  '2^2 and 2^3. Right ratio is 2^1 - how to check?

open "n.txt" for output as #1
#1, "6"
'#1, "1"
#1, "3 128 8 512"
#1, "4 1500 300 37500 12"
#1, "3 1 4 32"
#1, "3 7 28 224"    'just multiplied by 7
#1, "3 7 112 7168"    'with 2^2 ratio
#1, "3 1 6 216"    'with 2*3 ratio
close #1

open "n.txt" for input as #1
line input #1,nc$
for nn=1 to val(nc$)
   line input #1, a$

   n = val(word$(a$,1))
   dim a(n)
   for i = 1 to n
       a(i) = val(word$(a$,i+1))
   next

   'gosub [printArr]

   sort a(),1,n

   'gosub [printArr]

   'print "min ";a(1)
   'print "max ";a(n)


   'geometric progression:
   'ai = a0*p^i
   'so aj/ai ought to be p^k

   min = 1e10
   for i = 1 to n-1
       pk =a(i+1)/a(i)
       if pk <min then min = pk
       'print pk; " ";
   next
   'print

   ratio = min

   'print "min p^k is: ";min
   'print "first ratio is: ";ratio

   'decompose ratio into primes, take each prime once
   r = ratio
   p = 1
   for i = 2 to r/2
       if r mod i = 0 then
           p = p*i
           while r mod i = 0 : r = r /i: wend
           'exit for
       end if
   next
   'print "p=";p
   if p = 1 then ' ratio is prime
       p = ratio: kk = 1
   else    'ratio is p^kk
       kk = int(log(ratio)/log(p)+0.001)    '+0.001 just for a case
   end if
   'print "k =";kk
   'print "first ratio is: ";p;"^";kk

   'now check from p^kk to p^1
   for k = kk to 1 step -1
       ratio = p^k
       'check
       covered = 1
       a = a(1)
       j = 2
       'print a;" ";
       while a <a(n)
           a=a*ratio
           if a(j) = a then covered = covered+1: j=j+1
           'print a;" ";
       wend
       'print
       'print " covered: "; covered
       if covered <n then
           'print "No good. have to decrease ratio by ";p
       else
           'print "all done"
           'print all stuff here
           print "ratio = "; ratio
           a = a(1)
           j = 2
           print a;" ";
           while a <a(n)
               a=a*ratio
               print a;" ";
           wend
           print
           exit for
       end if
   next k
next nn
close #1
end

[printArr]
   for i = 1 to n
       print a(i); " ";
   next
   print
return


[tsh73]

May 19, 2020 15:54:42 GMT -5 svajoklis said:

The second set trips up your solution, since the ratio is good, but the output sequence looks nothing like the one in the solution. The initial number in that sequence is 12 and others should be 12 multiplied by 5 over and over again ending with 37500 I get '1 5 25 125 625 3125 15625 78125'

Rod's program works for me as posted - on initial two sets of data.

[svajoklis]

I seem to have miscopied the initial test data and didn't quite select the last digit 1, my bad I rechecked Rod's solution and it now completes 3/6 total sets. I added tsh73 sets to the test data in the task, thanks!

Good job, tsh73, your program does seem to work with all the data sets we currently have. We'll see if it holds up when we think up new ones

[tenochtitlanuk]

EDIT Sorry-posted wrong version..

And just realised 'If there can be more than one possible common ratio, print the highest one.'. I'd assumed the smallest was appropriate.

My current version. Test results..


3 data items, being 128 8 512
 Ratio = 2
         8         16         32         64        128        256        512       1024       2048

4 data items, being 1500 300 37500 12
 Ratio = 5
        12         60        300       1500       7500      37500     187500     937500    4687500

3 data items, being 1 32 4
 Ratio = 2
         1          2          4          8         16         32         64        128        256

3 data items, being 1 216 6
 Ratio = 6
         1          6         36        216       1296       7776      46656     279936    1679616

3 data items, being 28 7 224
 Ratio = 2
         7         14         28         56        112        224        448        896       1792

3 data items, being 7168 112 7
 Ratio = 2
         7         14         28         56        112        224        448        896       1792

4 data items, being 1500 300 37500 12
 Ratio = 5
        12         60        300       1500       7500      37500     187500     937500    4687500






   open "challenge3_data.txt" for output as #fOut
       #fOut "7"                    '   ie seven sets follow with number of terms specified by first number in data line.

       #fOut "3 128 8 512"          '   these example numbers are in the desired set but in no particular order
       #fOut "4 1500 300 37500 12"  '      this second set with 4 example numbers is a set with a different ratio.
       #fOut "3 1 32 4"
       #fOut "3 1 216 6"
       #fOut "3 28 7 224"
       #fOut "3 7168 112 7"
       #fOut "4 1500 300 37500 12"
   close #fOut

   open "challenge3_data.txt" for input as #fIn
       line input #fIn, c$

       for j =0 to val( c$) -1         '   each new test case
           line input #fIn, d$         '   data for this case
           N           =val( word$( d$, 1, " "))
           sample$     =mid$( d$, 1 +instr( d$, " "))
           print N; " data items, being "; sample$

           R           =val( word$( HCF$( sample$, N), 2, " "))
           start       =val( word$( HCF$( sample$, N), 1, " "))
           print "  Ratio = "; R

           for q =0 to 8
               term = start *R^q
               print using( "###########", term);
           next q

           print "": print ""

       next j

   close #fIn

   end

   function HCF$( i$, nTerms)   '   given eg "128 8 512" and 3 returns HCF$ ie 6 ( start) and ratio ( 4) .. or 2 if preferred Occam solution)
       HCF         =1E20
       smallest    =1E20

       for m =1 to nTerms -1           '   eg if three terms, m runs from 1 to 2
           for n =m +1 to nTerms       '       and n from m +1 to 3
               a       =val( word$( i$, m, " "))
               if smallest >a then smallest =a
               b       =val( word$( i$, n, " "))
               HCF     =min( HCF, max( b, a) /min( b, a))
           next n
       next m

       a       =val( word$( i$, nTerms, " "))
       if smallest >a then smallest =a

       [o]
       if HCF^0.5 =int( HCF^0.5) then HCF =HCF^0.5: goto [o]

       HCF$        =str$( smallest) +" " +str$( HCF)
   end function


   


[timur77]

On a business trip on Saturday, I’ll decide if I have time.

[svajoklis]

timur77, I really hope you can find the time, I enjoy seeing your solutions!

tenochtitlanuk, that's some nice progress, can't wait to see your final solution!

[timur77]

All decided. And I added two tests when large numbers and when ratio> the first number of the progression.

challenge3_data.txt

8
3 128 8 512
4 1500 300 37500 12
3 1 4 32
3 7 28 224
3 7 112 7168
3 1 6 216
4 82055753 37349 17 485537
3 7 45927 413343
=========================================
ratio=4
8 32 128 512
ratio=5
12 60 300 1500 7500 37500
ratio=2
1 2 4 8 16 32
ratio=2
7 14 28 56 112 224
ratio=4
7 28 112 448 1792 7168
ratio=6
1 6 36 216
ratio=13
17 221 2873 37349 485537 6311981 82055753
ratio=9
7 63 567 5103 45927 413343

The program does not have protection against incorrect data (in the condition there were no such requirements)

Dim nab(100,100),kelem(100)
Dim nabmin(101)
Dim ratio(100)

open "challenge3_data.txt" for input as #text
item$=inputto$(#text, " ")
Knab=Val(item$)
print Knab
For i=1 to Knab
   item$=inputto$(#text, " ")
   kelem(i)=Val(item$)
   print kelem(i);" ";
   For a=1 to kelem(i)
       item$=inputto$(#text, " ")
       nab(i,a)=Val(item$)
       print nab(i,a);" ";
   Next a
   print
Next i
close #text
print "========================================="
For Kn=1 to Knab
   For i=1 to kelem(Kn)-1
       For a=i+1 to kelem(Kn)
           if nab(Kn,i)>nab(Kn,a) then
               buf=nab(Kn,i)
               nab(Kn,i)=nab(Kn,a)
               nab(Kn,a)=buf
           end if
       Next a
   Next i
Next Kn
'-----------------------------------------------
For i=1 to Knab
   For aa=nab(i,2) to 2 step (-1)
       if (nab(i,2) mod aa)=0 then
       For ee=nab(i,1) to 1 step (-1)
           x=0
           ind=1
[L1]
           scan
           if ee*aa^x=nab(i,ind) then
               if nab(i,ind)=nab(i,kelem(i)) and kelem(i)=ind then exit for
               ind=ind+1
               x=x+1
               goto [L1]
           end if
           if ee*aa^x<nab(i,ind) then
               x=x+1
               goto [L1]
           end if
           if ee*aa^x>nab(i,ind) then ind=0
       next ee
       if nab(i,ind)=nab(i,kelem(i)) and kelem(i)=ind then exit for
       end if
   next aa
   ratio(i)=aa
   nabmin(i)=ee
Next i
'-----------------------------------------------
For i=1 to Knab
   print "ratio=";ratio(i)
   print nabmin(i);" ";
   a=nabmin(i)
   while a<nab(i,kelem(i))
       a=a*ratio(i)
       print a;" ";
   wend
   print
Next i
end


[tenochtitlanuk]

I'm still unhappy that if numbers for a test are random samples, Occam's Razor implies that the smaller ratio that works would be chosen. ??
So my version gives 2 as the ratio for data set '2 8 128 512' rather than 4. Hey ho!!

Otherwise happy on all tests so far..

[svajoklis]

Timur77, nice to see your solution! I added your test cases to the main post, thanks  And yes, you are right, only valid partial progressions are submitted to the program.

tenochtitlanuk, the point of only outputting the largest possible ratio, is that for example the progression "1 4 16 64" could either be partial with the ratio 2 (1 2 4 8 16 32 64), or a full one with ratio 4 (1 4 16 64), both of which are possibilities. Thus, the task is to extract the largest possible one.