[ASSIGNMENT] Question marks ! (coderbyte problem)

Question

Code QuestionsMarks(str) take the str string parameter, which will contain single digit numbers, letters, and question marks, and check if there are exactly 3 consecutive question marks between every pair of two numbers that add up to 10. If so, then your program should return the string true, otherwise it should return the string false. If there aren't any two numbers that add up to 10 in the string, then your program should return false as well.

For example: if str is "arrb6???4xxbl5???eee5" -> true

Answer 1

https://code.sololearn.com/c0Q9dOnshEc9/?ref=app

Updated (2.may 2018) :
https://code.sololearn.com/czkSKLloN3fa/?ref=app

Answer 2

~ swim ~
I assumed that every pair must meet the conditions. But if I read the task again, it says "If there are not any two numbers that add up to 10 in the string, then your program should return false as well" you might be right when you say that it's enough that at least one pair meets the conditions.

Answer 3

Nevfy
Yes, I saw that this case is false to you though I do not know why because :
5 + 5 = 10 and 5 + 5 = 10.

If I understand well, if we have 3 marks '?' between 2 digits whose sum is 10 then result is true.
I checked the VcC solution, it seems to me that he think like me.
I hope that VcC will clarify this case 😉

Answer 4

~ swim ~
It should not be consecutive, but exactly 3 marks '?' between two digits (surrounded with digits)

Answer 5

Wow wow wow - lets stay calm my friends. And feel free to solve whatever problem you want - this is a training and discussion forum, not a customer tender ;-)

Answer 6

This is a realization of naive algorithm proposed by @Ali Zhussupov with some improvements, because in a way he presented it above it is wrong for the case when there is no numbers with sum equals to 10:

https://code.sololearn.com/ctwPjewAU9iH/?ref=app

However, it has a huge complexity of O(L^3) where L is a length of the string.

Here is mine realization with complexity of O(N^3+L) where N is a number of digits in a string and L is a length of the string:

https://code.sololearn.com/cqe6kTHuJ6hE/?ref=app

Thanks to @VcC for the interesting assignment and looking forward for his and others solutions implementing any other interesting optimizations!

Answer 7

@VcC You really need to clarify the definition of the challenge, because at my point of view string "2q?q2???8" is False, because there are 4 '?' between first 2 and 8. However, your solution returns True.

Answer 8

First of all, I agree with @VcC: take it easy. These challenges are mostly invented to practice your skills in programming. You code your own approach and then compare productivity of your code with others and learn something new from them. However, it is obviously better for everyone if the definition is clear and has enough of examples to confirm the correctness of understanding before you start to make your code. Nevertheless, this time we had a problem of task's understanding, so everyone produced a bit different code solving a bit different task. What I propose in such cases is to write explicitly your understanding of the task in the comment with your code. Like that it will be much easier to check: does your code successfully work or it requires some corrections.

@JPM7 I have the same understanding as you that from the definition of the challenge explicitly follows that EVERY pair those sum is equal to 10 should be taken into account. However, @VcC have already answered that he meant only consecutive pairs (as well as '?' marks).
Nevertheless, I will be happy to see your solution in your initial understanding as well (you can find mine above). Let's introduce some notation to estimate the performance:
- N is a number of digits in a string;
- L is a length of the string.
Mine realization works with time complexity of O(N^3+L) and memory complexity of O(L).
The code you presented above (if I have understood it correctly) works with time complexity of O(L^3) and memory complexity of O(L^2) and you also have some improvements in mind. So, as I have already said, I would be happy to see your ideas (but preferably not in a text form but in a form of code) to investigate them and maybe to learn something new.

Answer 9

My version using an automaton. Complexity is O(N+dxM) where N is the size of the string & d the number of digits and M the number of question marks in it.

This version will tell you precisely why your string does match or does not match

https://code.sololearn.com/cCIGfN16MZYb

Answer 10

@VcC That's very smart to use regular expressions for that task! I'm not very strong in this topic, but I guess I should master it. It seems to be very powerful approach. And thanks for the article to read, I hope I'll find some time to do it...

However, you need to correct your code. For a moment it returns True for input "8?2".

Answer 11

@LukArToDo and @~ swim ~
At my understanding it should be exactly 3 marks '?' (not necessary consecutive) between EACH pair, those sum is equal to 10.
Thus, answering on the question, why at my point of view "5???5qqq5???5" is a False string. There is no 3 '?' between two middle 5 (there are just 3 'q').
And "46???5???5" is also False string, because there are no '?' between 4 and 6.

Answer 12

https://code.sololearn.com/cTlkhJomDYq0/?ref=app

Answer 13

How about mine🤔. It meets the requirements shown in the VcC and LukArToDo codes.☺️👇

https://code.sololearn.com/ctqioZDTmSnQ/?ref=app

Answer 14

@JPM7 In fact "on the fly" realization is also possible. It means we obtain a string by one symbol and after each new symbol we can decide if string is still valid or not. You just need to store all numbers that you have already met in this string and amount of question mark after them. For each new number you check if its compliment is already in a storage and if so you check amount of question mark in between. You also need to check if new number itself is already in a list and if so check if there were any question mark in between. If so there is no need to calculate amount of Q-marks for that number anymore. As soon as its compliment appears in a string it becomes False. For example, string like "2?2..." will be False as soon as 8 appears on any position later. I assume that this algorithm can be also the quickest one...

Answer 15

The straightforward solution comes to mind immediately(pseudo code):
n = length of str
loop i in 0 ..< n
loop j in i+1 ..< n
{
if (str[i] and str[j] are digits) and str[i]+str[j] == 10 then
{
x = count ‘?’s in range from i to j
if x != 3
return “false”
}
}
return “true”

Complexity of this solution is O(n^3). Is it OK for your input constraints and time limit?

Answer 16

Bravo Nevfy. For this one i dont know about the complexity but the onelinecity is low.

https://code.sololearn.com/cg5yai7SLrPR/?ref=app

Bonus: https://swtch.com/~rsc/regexp/regexp1.html

Answer 17

@LukArToDo It returns True for "5???5qqq5???5", however it shows be False.

Answer 18

6???5 6+5=11

Answer 19

New version

https://code.sololearn.com/cg5yai7SLrPR/?ref=app

Answer 20

Question marks were meant to be consecutive but agree it was not clearly mentionned