Weekly Liberty BASIC Challenge #2

[svajoklis]

Hello again.

It was nice to see your solutions. They were no votes, even on own posts, so in the future I will count how many tasks you have completed. Last week's task was on the easier side so this week I tried to find something more interesting. Same as before you have a week to submit your solutions and no peeking before you have made your own! If you want to participate that is 

Small clarification on the level of the problem: the olympiad I am basing this challenge on (and probably some of the future ones) is meant for high-school students, grades 10-12, so it's not something super hardcore 
Edit: small clarification of the challenge details.

---

Weekly Challenge problem #2 [level: olympiad]

You have two whole numbers k and s (1 <= k <= 10, 1 <= s <= 100).

Find the biggest and the smallest numbers so that each one of them:
- is made up out of non-repeating digits
- has k digits
- doesn't start with a 0
- sum of it's digits is s

If there are no numbers that satisfy these conditions then output "none"

Examples:

Input
Output
k = 4, s = 6
max = 3210, min = 1023
k = 2, s = 20
none
k = 2, s = 10
max = 91, min = 19
k = 2, s = 3
max = 30, min = 12
k = 7, s = 38
max = 9876530, min = 1256789
k = 3, s = 11
max = 920, min = 128
k = 6, s = 15
max = 543210, min = 102345
k = 5, s = 36
none
k = 5, s = 9
none

---

Good luck!

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

Hall of Fame (solutions submitted):

	tenochtitlanuk	1
	timur77	1
	Rod	1
	svajoklis	1

[Rod]

dim digit(9)
   for n= 0 to 9
   digit(n)=n
next

k=4
s=6

for o=0 to 9
   for m=0 to 9
       d=m-o+1
       p=0
       for n=o to m
           found(p)=digit(n)
           p=p+1
           'print digit(n);" ";
           t=t+digit(n)
       next
       'print ,d,t
       if d=k and t=s then
           found=1
           print "Found it"
           sort found(,d-1,0
           print "Max ";
           for x=0 to d-1
           print found(x);
           next
           print ,
           Print "Min ";
           sort found(,0,d-1
           if found(0)=0 then found(0)=found(1) : found(1)=0
           for x=0 to d-1
              print found(x);
           next
       end if
       t=0
   next
next
if found=0 then print "Not Found"


[svajoklis]

Had a run of your program, with k = 2 and s = 10 the answer should be 91 and 19, but your program outputs "not found"

I think I will update the rules a bit for the next challenge so that the program has to read data from data statements that are at the top of the program, then have a rem/comment separator, so you could run the program without really looking at the solution to just check it. Before counting the results I will also try to create a test suite that I will run through each submission to check how 'correct' it was. I will of course post the suite and results together with the next challenge and will probably reward points based on how many of the test suite items the program calculated correctly, so 75% would be 0.75 points, 100% is 1 point.

[timur77]

I solved the problem in two ways.
The first way to break, a sequential search with filtering elements, for large values, searches for a long time. But it works.
The second method is combinatorial, it is many times faster.

Tested programs with the following values:
k=7 s=38
maxx=9876530
minn=1256789

k=3 s=11
maxx=920
minn=128

k=6 s=15
maxx=543210
minn=102345

k=5 s=36
none

k=5 s=9
none

№1
k=11
while (k<1 or k>10)
   input "k=";k
wend

s=101
while (s<1 or s>100)
   input "s=";s
wend
'===========
maxxp=9876543210 mod 10^k
smax=0
for e=1 to k
   smax=smax+Val(mid$(str$(maxxp),e,1))
next e
if smax>s then print "none0":end
'===========
maxx=int(9876543210 / 10^(10-k))
'===========
smax=0
for e=1 to k
   smax=smax+Val(mid$(str$(maxx),e,1))
next e
if smax<s then print "none1":end
'- - - - - -
[L1]
'- - - - - -
for i=1 to k
   pp$=mid$(str$(maxx),i,1)
   ppr=0
   for a=1 to k
       if pp$=mid$(str$(maxx),a,1) then ppr=ppr+1
       if ppr>1 then maxx=maxx-maxx mod 10^(k-a):EXIT FOR
   next a
   if ppr>1 then EXIT FOR
next i
if ppr>1 then goto [L2]
'- - - - - -
smax=0
for e=1 to k
   smax=smax+Val(mid$(str$(maxx),e,1))
next e
locate 1,3
print maxx
if smax<>s then goto [L2]
'- - - - - -
print "maxx=";maxx
'===========
'===========
minn=int(1023456789 / 10^(10-k))
'===========
smin=0
for e=1 to k
   smin=smin+Val(mid$(str$(minn),e,1))
next e
if smin>s then print "none2":end
[L3]
'- - - - - -
for i=1 to k
   pp$=mid$(str$(minn),i,1)
   ppr=0
   for a=1 to k
       if pp$=mid$(str$(minn),a,1) then ppr=ppr+1
       if ppr>1 then minn=minn+10^(k-a)-minn mod 10^(k-a)-1:EXIT FOR
   next a
   if ppr>1 then EXIT FOR
next i
if ppr>1 then goto [L4]
'- - - - - -
smin=0
for e=1 to k
   smin=smin+Val(mid$(str$(minn),e,1))
next e
locate 1,5
print minn
if smin<>s then goto [L4]
'- - - - - -
print "minn=";minn
end
'===========
[L2]
if maxx>10^(k-1) then
   maxx=maxx-1
   
   goto [L1]
else
   print "none3"
end if
end
'===========
[L4]
if minn<10^(k+1) then
   minn=minn+1
   goto [L3]
else
   print "none4"
end if
end

№2
k=11
while (k<1 or k>10)
   input "k=";k
wend

s=101
while (s<1 or s>100)
   input "s=";s
wend
'===================================
Dim sv(11)
for i=1 to 10
   sv(i)=1
next i

Dim maxx(11)
data 9,8,7,6,5,4,3,2,1,0
for i=1 to 10
   read buf
   maxx(i)=buf
next i

[L1]
sk=0
for i=1 to 10
   sk=sk+sv(i)
next i
if sk<>k and sk<>0 then
[L2]    
   sv(10)=sv(10)-1
   for i=9 to 1 step (-1)
       if sv(i+1)<0 then sv(i)=sv(i)-1:sv(i+1)=1
   next i
   if sv(1)=(-1) then sv(1)=1
   
   goto [L1]
end if

ss=0
for i=1 to 10
   ss=ss+maxx(i)*sv(i)
next i
if ss<>s and sk<>0 then goto [L2]

if sk=0 then print "none":end

print "maxx=";
for i=1 to 10
   if sv(i)=1 then print maxx(i);
next i
print ""
'=================================
for i=1 to 10
   sv(i)=1
next i

Dim minn(11)
data 1,0,2,3,4,5,6,7,8,9
for i=1 to 10
   read buf
   minn(i)=buf
next i

[L3]
sk=0
for i=1 to 10
   sk=sk+sv(i)
next i
if sk<>k and sk<>0 then
[L4]    
   sv(1)=sv(1)-1
   for i=2 to 10
       if sv(i-1)<0 then sv(i)=sv(i)-1:sv(i-1)=1
   next i
   if sv(10)=(-1) then sv(10)=1
   
   goto [L3]
end if

ss=0
for i=1 to 10
   ss=ss+minn(i)*sv(i)
next i
if ss<>s and sk<>0 then goto [L4]

ei=0
ai=0
for i=1 to 10
   if sv(i)>0 and minn(i)=1 then ei=1
   if sv(i)>0 and minn(i)=0 then ai=1
next i
if ei=0 and ai=1 then goto [L4]

if sk=0 then print "none":end

print "minn=";
for i=1 to 10
   if sv(i)=1 then print minn(i);
next i
end

[tenochtitlanuk]

I thought much the same ways. Especially the need to think and optimise...
Once I knew it worked for the original two examples, I did a kind of Monte Carlo method generating k and s at random but in range. Immediately showed how slow ten digits could get!

It's quite fun to watch for the smaller k values, but for 5 or more digits gets slow.....

EDIT (updated code)

Typical grabbed output..

Testing 4 digit numbers, between 1023 and 9876 whose digits sum to 6
1023 is OK for sum = 6
3210 is OK for sum = 6
Found

Testing 2 digit numbers, between 10 and 98 whose digits sum to 20
None

Testing 2 digit numbers, between 10 and 98 whose digits sum to 10
19 is OK for sum = 10
91 is OK for sum = 10
Found

Testing 2 digit numbers, between 10 and 98 whose digits sum to 3
12 is OK for sum = 3
30 is OK for sum = 3
Found

Testing 7 digit numbers, between 1023456 and 9876543 whose digits sum to 38
1256789 is OK for sum = 38
9876530 is OK for sum = 38
Found

Testing 3 digit numbers, between 102 and 987 whose digits sum to 11
128 is OK for sum = 11
920 is OK for sum = 11
Found

Testing 6 digit numbers, between 102345 and 987654 whose digits sum to 15
102345 is OK for sum = 15
543210 is OK for sum = 15
Found

Testing 5 digit numbers, between 10234 and 98765 whose digits sum to 36
None

Testing 5 digit numbers, between 10234 and 98765 whose digits sum to 9
None



As before I append my code lower on this page!

' Weekly Challenge problem #2

' You have two whole numbers k and s ( 1 <= k <= 10, 1 <= s <= 100).

' Find the biggest and the smallest numbers so that:
' - each one is made up out of non-repeating digits
' - each one has k digits
' - each one doesn't start with a 0
' - the sum of digits is s

' If there are no numbers that satisfy these conditions then output "none"
' k s
data 4, 6 'max = 3210, min = 1023
data 2, 20 'none
data 2, 10 'max = 91, min = 19
data 2, 3 'max = 30, min = 12
data 7, 38 'max = 9876530, min = 1256789
data 3, 11 'max = 920, min = 128
data 6, 15 'max = 543210, min = 102345
data 5, 36 'none
data 5, 9 'none

open "anaysis2.txt" for output as #fOut

global digit$, k, s, finished, result$
digFwd$ ="0123456789"
digRev$ ="9876543210"
order$ ="1023456789" ' smallest number is sum of leftmost k characters of this.

for d =1 to 9
read k, s
result$ ="None"

biggestPoss =val( left$( digRev$, k))
lowestPoss =val( left$( order$, k))
#fOut " Testing "; k; " digit numbers, between ";lowestPoss; " and "; biggestPoss; " whose digits sum to "; s
print " Testing "; k; " digit numbers, between ";lowestPoss; " and "; biggestPoss; " whose digits sum to "; s

for n =lowestPoss to biggestPoss
call test n
if finished =1 then exit for
next n

print result$

next d

wait

sub quit h$
close #fOut
end sub

sub test n ' testNumber
finished =0
n$ =str$( n)
available$ =digit$
for p =1 to len( n$)
sum =sum +val( mid$( n$, p, 1))
next p
if ( sum =s) and digitsDifferent( n$) =1 then #fOut n$; " is OK for sum = "; s: print n$; " is OK for sum = "; s: result$ ="Found"

'if ( sum >10^k) then finished =1': print "None."
scan
end sub

function digitsDifferent( n$)
digitsDifferent =1
for q =1 to len( n$) -1
currentDigit$ =mid$( n$, q, 1)
if instr( mid$( n$, q +1), currentDigit$) then digitsDifferent =0
next q
end function

[svajoklis]

Timur77 goes above and beyond, looks very good! I have taken the liberty (pun intended) of adding your test cases to the main task

Usually there is a time and memory constraints on the solutions, so a brute force solution wouldn't even pass the "checking" stage in the olympiad. There are "hidden" (you don't get to see the input data) test cases are with biggest limits possible, and the time constraints are such, that a brute-force solution would simply take too long. Hell, you could generate Mona Liza if you had enough time to brute force each pixel for a decently sized image I wouldn't say the solution would deserve 0 points, but at the same time I couldn't give it more than 0.1 since it completely bypasses the idea of the task

[svajoklis]

I think the olympiad level tasks are a bit more engaging, loved completing it. Broke out a lot of extra functions to make the code a bit more readable. It's a recursive solution that tries to return back up the stack whenever it sees that it hasn't gone down a good path.

' parameters
' k, s
data 7, 38

' you can either run the solution to data values, or a test suite by uncommenting corresponding sub call
read k, s
call solution k, s
' call doTests

end

sub solution k, s
   empty$ = ""
   for i = 1 to k : empty$ = empty$ + "0" : next i

   max$ = doBiggest$(k, s, empty$, 1, 1)
   if max$ <> "none" then
       min$ = doSmallest$(k, s, empty$, 1, 1)
       print "max = "; max$; ", min = "; min$
   else
       print "none"
   end if
end sub

function doNumber$ (digits$, k, s, number$, processedNumber, nextIndex)
   if processedNumber <= len(number$) and nextIndex <= len(digits$) and sumDigits(number$) <= s then
       for a = nextIndex to len(digits$)
           newNumber$ = setDigit$(number$, processedNumber, getDigit$(digits$, a))
           if getDigit$(newNumber$, 1) <> "0" then
               ret$ = doNumber$(digits$, k, s, newNumber$, processedNumber + 1, a + 1)
               if len(ret$) > 0 then
                   doNumber$ = ret$
                   exit for
               end if
           end if
       next a
   end if

   if sumDigits(number$) = s and processedNumber > len(number$) then
       doNumber$ = number$
   end if

   ' nothing came back, return "none"
   if len(doNumber$) = 0 and processedNumber = 1 then
       doNumber$ = "none"
   end if
end function

function doBiggest$ (k, s, number$, processedNumber, nextIndex)
   digits$ = "9876543210"
   doBiggest$ = doNumber$(digits$, k, s, number$, processedNumber, nextIndex)
end function

function doSmallest$ (k, s, number$, processedNumber, nextIndex)
   digits$ = "1023456789"
   doSmallest$ = doNumber$(digits$, k, s, number$, processedNumber, nextIndex)
end function

sub test k, s, expected$
   empty$ = ""
   for i = 1 to k : empty$ = empty$ + "0" : next i
   out$ = ""
   max$ = doBiggest$ (k, s, empty$, 1, 1)
   if max$ <> "none" then
       min$ = doSmallest$ (k, s, empty$, 1, 0)
       out$ = "max = "; max$; ", min = "; min$
   else
       out$ = "none"
   end if

   print out$
   print expected$
   if out$ = expected$ then
       print "OK!"
   else
       print "fail"
   end if
   print
end sub

sub doTests
   call test 4, 6, "max = 3210, min = 1023"
   call test 2, 20, "none"
   call test 2, 10, "max = 91, min = 19"
   call test 2, 3, "max = 30, min = 12"
   call test 7, 38, "max = 9876530, min = 1256789"
   call test 3, 11, "max = 920, min = 128"
   call test 6, 15, "max = 543210, min = 102345"
   call test 5, 36, "none"
   call test 5, 9, "none"
end sub

' util functions

function sumDigits (string$)
   sumDigits = 0
   for i = 1 to len(string$)
       sumDigits = sumDigits + val(mid$(string$, i, 1))
   next i
end function

function getDigit$ (string$, index)
   getDigit$ = mid$(string$, index, 1)
end function

function setDigit$ (string$, index, character$)
   setDigit$ = mid$(string$, 1, index - 1) + character$ + mid$(string$, index + 1)
end function


Oh wow, it does seem we all went to quite similar solutions It's interesting to see everyone's different coding styles like that