|
Post by svajoklis on May 5, 2020 8:44:07 GMT -5
I have some problems laying around that I think would be interesting to solve in different ways as a community. The rules are simple: - Each week I will post a problem and your task is to solve it!
- No peeking at other's solutions and try not to Google solutions, since they are probably out there.
- The week after I will be back with a new problem and we will pick the best solution from the previous week as the winner.
- You can vote for a solution by liking the post with the solution. You can remove your vote by unliking the post.
- If you want to update your solution - do so by editing the same post you submitted previously to keep all the likes.
- Some tasks will contain bonus objectives. Completing bonus objectives should be taking into consideration when judging submissions
- Solution with most likes - wins!
Of course I will be submitting my own solution, though it will live in it's own little post a bit further down below, same as yours Without further ado, here's the first problem: Weekly Challenge problem #1 [level: easy]You are given a list of numbers and a number k. You should print out whether any two numbers from the list add up to k. Example: given [10, 15, 3, 7] and k of 17, print "yes" since 10 + 7 is 17. Bonus points: can you do this in one pass? --- Best of luck, can't wait to see what you come up with (after doing my own solution of course!)
|
|
|
Post by tenochtitlanuk on May 5, 2020 9:41:43 GMT -5
Do you only allow each number to appear once? And must they be less than the sum required? I generated 50 random integers including ones which were too high, and got results..
13,26,16,8,5,26,21,10,16,22,4,7,3,21,22,16,15,11,13,28,14,14,7,5,25,8,24,25,24,14,23,29,21,5,26,27,23,2,26,29,24,9,7,17,11,18,6,6,12,1
13 + 4= 17 16 + 1= 17 8 + 9= 17 5 + 12= 17 10 + 7= 17 10 + 7= 17 10 + 7= 17 16 + 1= 17 4 + 13= 17 3 + 14= 17 3 + 14= 17 3 + 14= 17 16 + 1= 17 15 + 2= 17 11 + 6= 17 11 + 6= 17 5 + 12= 17 8 + 9= 17 5 + 12= 17 11 + 6= 17 11 + 6= 17
'Weekly Challenge problem #1 [level: easy]
'You are given a list of numbers and a number k. 'You should print out whether any two numbers from the list add up to k. 'Example: given [10, 15, 3, 7] and k of 17, print "yes" since 10 + 7 is 17. 'Bonus points: can you do this in one pass?
dim num( 100)
'n$ ="10,15,3,7,32,1,243,2,6"
for check =1 to 50 n$ =n$ +str$( int( 30 *rnd( 1))) if check <>50 then n$ =n$ +"," next check
print n$
sum =17
cnt =1
do e$ =word$( n$, cnt, ",") a =val( e$) num( cnt) =a cnt =cnt +1 loop until e$ =""
cnt =cnt -1
for first =1 to cnt -1 if num( first) <sum then for second =first +1 to cnt if num( first) +num( second) =sum then print num( first); " + "; num( second); "= "; sum next second end if next first
|
|
|
Post by Brandon Parker on May 5, 2020 10:52:13 GMT -5
When does the "first pass" start? Are we allowed to get the data into one or more arrays first? This is how I have seen this done before that way only the algorithm for checking is considered for efficiency purposes.
{:0)
Brandon Parker
|
|
|
Post by Carl Gundel on May 5, 2020 10:55:30 GMT -5
Bonus points: can you do this in one pass? One pass means no nested loops?
|
|
|
Post by Brandon Parker on May 5, 2020 11:01:20 GMT -5
Bonus points: can you do this in one pass? One pass means no nested loops? I would assume "one pass" is for testing the data that way the code is O(n) with respect to efficiency. Having a single nested loop makes the efficiency O(n^2). This can definitely be done in a single pass and is a common interview question. The problem requires a little more refinement for when the efficiency analysis will start. For instance, should we assume the data is already in an array or can we place it there without penalty? Can we sort that array without penalty? {:0) Brandon Parker
|
|
|
Post by svajoklis on May 5, 2020 12:19:49 GMT -5
tenochtitlanuk, they may be more, they may be more, they may repeat. The only task is to find whether any two of them sum up to k.
Brandon Parker, I am not the creator of the task, but when I first read this I assumed, that by "one pass" it means iterating through the array and reading it once, so pretty much going "for i = 1 to len(arr)". If you iterated again through all the elements in the array in a nested loop that would put it into O(n^2) territory.
|
|
|
Post by Carl Gundel on May 5, 2020 12:36:49 GMT -5
One pass means no nested loops? I would assume "one pass" is for testing the data that way the code is O(n) with respect to efficiency. Having a single nested loop makes the efficiency O(n^2). This can definitely be done in a single pass and is a common interview question. The problem requires a little more refinement for when the efficiency analysis will start. For instance, should we assume the data is already in an array or can we place it there without penalty? Can we sort that array without penalty? {:0) Brandon Parker Thinking about it I guess one pass means that you don't transform the information into a different form, and then iterate on that form afterwards to produce results.
|
|
|
Post by Rod on May 5, 2020 12:39:56 GMT -5
😀 I had forgotten why we stopped setting challenges. Good luck choosing a winner. And we have weeks more of this entertainment!
Well done for setting the challenge, stick with it for as long as you can.
We need stuff like this.
|
|
|
Post by svajoklis on May 5, 2020 12:57:04 GMT -5
Rod, thanks!
Carl Gundel, well yeah, if you went through the array once to do something with it and then went over it again it would mean two passes.
Edit: I'd think of it as a stream that you can read one number by another, but you can't go and access a specific index later if I was going for the optional objective.
|
|
timur77
Junior Member
Someday I will tell my grandsons that I am older than the Internet. And it will blow their brain.
Posts: 79
|
Post by timur77 on May 6, 2020 0:34:58 GMT -5
Dim a(101) for i=1 to 100 a(i)=int(rnd(1)*100) print a(i);" "; if (i mod 20)=0 then print next i k=int(rnd(1)*100) print print "k=";k
b1=a(1) b2=a(2) for i=3 to 100 if a(i)<b1 then b2=b1 b1=a(i) else if a(i)<b2 then b2=a(i) end if next i if b1+b2<=k then print "yes ";b1;" ";b2 else print "no"
something like this, everything seems to work
|
|
|
Post by Rod on May 6, 2020 2:45:15 GMT -5
n$="10, 15, 3, 7" pos=1 n=val(word$(n$,pos)) while n>0 if instr(n$,str$(17-n),1)>0 then print n,"yes" pos=pos+1 n=val(word$(n$,pos)) wend
|
|
|
Post by svajoklis on May 9, 2020 16:03:50 GMT -5
I am still missing solutions from some of our hard-hitters. There is still time until tuesday to submit your solutions! I'll probably "close" this thread and start a new one at ~12:00 EEST, Or 09:00 GMT.
|
|
|
Post by svajoklis on May 9, 2020 17:11:16 GMT -5
My humble solution, only reads data one time, doesn't iterate through either data or some intermediate form, only does array access.
' basic idea: ' check index (num) for each number, if set - then it's the other part of sum, so sum found, end search ' else subtract num from k and set 1 at calculated index
' read data, where ' first item is k ' second item is count of numbers to check followed by said numbers
' known issues: only tracks differences up to 1000 as set by maxDifference, requires more memory for bigger numbers
maxDifference = 1000 dim remainders(maxDifference)
read k read numOfNums
sumFound = 0 for i = 1 to numOfNums read num if remainders(num) = 1 then sumFound = 1 exit for end if differenceIndex = k - num if differenceIndex >= 0 and differenceIndex <= maxDifference then remainders(differenceIndex) = 1 end if if differenceIndex > maxDifference then print "Found difference bigger than supported, increase maxDifference" end end if next i
if sumFound then print "yes" end if
end
' task data
data 20 data 4, 1, 3, 7, 19
|
|
ombre
New Member
Posts: 12
|
Post by ombre on May 13, 2020 8:55:21 GMT -5
To Ron,
I like your solution to challenge #1 because it follows the KISS solution. But, If you change «17» to «15» it doesn't seem to work anymore !
Sorry if I misunderstood the problem.
|
|
|
Post by Rod on May 13, 2020 9:41:40 GMT -5
Well none of the number pairs add up to 15, try changing 17 to 13 then you should get a match.
|
|