Why not working recrusively ?

Question

The task is to print all numbers with n digits which difference of all consecutive digits is k . I expect the Generate function works recrusively as I call the Generate function , but it only outputs one number ... although I guess it is because of returning a value , which probably terminates the program .. now how can I fix it ?
https://code.sololearn.com/c0a0A13A4A16/?ref=app

Answer 1

Ali_combination Either the problem is horribly written or you're still excluding critical details.

The information provided as:

"the main task is to output all n-digit number which difference of every consecutive digit is exactly k . Formally , for i , 0<=i<n , abs(string[i] - string[i+1]) = k , and the string variable is the number"

... still begs the following clarifications:

What's the function signature?
- return type, function name, and order and types of all input parameters.

Were there any sample inputs with expected output provided?

Does the function print the output or return the output?

Are there any specified constraints on the inputs?

Such as, but not limited to:
- Any min/max ranges for either n or k?

- Can these be negative and/or zero and/or positive?

Are these the only inputs?

Does the output expect all possible n-digit variants or a specific single value?

Ambiguity in current wording could imply all digits for "a single number" or for "all possible variants".

Answer 2

Ali_combination It seems the specific requirements of the original problem aren't clear and therefore is a moving target.

The original code uses a function containing 3 arguments and returns the value to be printed.

However, the posted Python solution uses 5 arguments and prints the output within the recursive function rather than return the value.

If the interface is this flexible, I'm curious how important it really is for this to be done recursively.

Ultimately, the solution doesn't require recursion and attempting to use it is a bit forced.

Can you provide specific text from the source? It's possible you're over looking subtle wording you may not have realized was significant for the expected solution. Paraphrasing these problems almost always leaves out critical points.

Answer 3

from where do you got this assignement?

there's a shorter and simpler implementation than the one you try to implement here ^^

you should iterate over each number of k digits and test if fulfill the requirement...

so you need only one function to check a number and return True or False...

then, you only need to iterate from 10^(n-1) to 10^n (former included, later not included), and output/append numbers wich return True when passed to your check function ;)

try to implement that, rather than trying to correct your actual code wich attempt to generate all valid numbers (and may have more mistakes than exiting after the first valid generated number) ;P

Answer 4

visph LOL... Indeed... that may very well be the case. 😉 However, you assume I have any clue of what the actual requirements are. 🤣

The assertions in my pervious posts are that the details are ambiguous at best and left to interpretation with various possible assumptions. That's a strong indication of a poorly constructed problem or crucial details were excluded because the OP either thought they weren't significant or should be understood by all.

Rather than try to guess, I used the output from your Python code as a basis for my version to cover a few test cases. It really wasn't worth my time to get more comprehensive without further clarifications.

I only wanted to point out that recursion wasn't necessarily the best choice.

All said, which inputs should I test. I'll try to look at them when I get a few minutes.

Answer 5

Ali_combination
Hmm... I'll try to clarify further:

1. The use of return values or otherwise can be different from one contest to another. They don't exclusively use standard output comparisons.

2. The ambiguity from the phrase "ALL N-DIGIT NUMBER" may be caused by a translation issue.

Possible meanings as phrased are:

a) "all possible N-digit number(s)"

or

b) "include all N-digit(s) in the number"

The lack of plurality and additional words make both (a) and (b) possible interpretations without further context.

However, the rest of the sentence using this phrase is focused only on the "digits", thereby establishing a context that aligns better with the second meaning - (b).

3. This is further supported by the formal statement that follows, which, again, refers only to details about the digits.

4. This is the first mention of all natural numbers, which is a perfect example of "deats" that are missing.

I just now saw you mentioned earlier that the max for n is 50. Again...

Answer 6

... this is another "deat" missing from your earlier clarification to me.

5. I'm still waiting to see the complete list of constraints and the sample inputs and outputs. This would clarify so much more for everyone.

6. If this was referring to all possible values of N-digit number(s), then details like the following are missing as well:

a) each value should be on a separate line

b) each value should be listed in ascending order (or whatever it should be)

One would expect these to be specified in a well constructed coding problem.

7. I can't say whether or not anything was clearly understood by the others or if they were simply filling in the blanks based on assumptions about what they believed to be obvious.

However...I can say that seasoned developers tend to scrutinize such details as they've had much experience navigating past challenges with general assumptions and biased expectations.

It's a common thing we look for with certain types of questions during technical interviews. 😉

Answer 7

Ali_combination Awesome! I'm really glad the feedback in my last response made sense and was helpful.

Your response and the details you provided were brilliant and cleared up everything.

The things that are now clear to me are:

There are 2 inputs:
- N: where N > 1 and N < 51
- K: where K > 0 and K < 10

Output is comma delimited set of all possible values with N-digits. Also, my original solution was too limited as mentioned by visph.

I'm sure you now see how useful the full set of details make it much clearer. 😉

I may or may not have time to attempt this. My schedule is slammed this week. I'm sure you and the others have it handled though.

If I do get a moment, I'll share my own versions, perhaps in other languages.

Answer 8

the C++ recursive implementation:

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

quite more efficient, but less concise ^^

timeout also in sololearn for not as big number of digits ;P

however; I'm very few experiemented at C/C++, so it may probably be improved (even if probably not enough to reach 5000 digits numbers without timing out: that would certainly require algorithm improvment and maybe non-recursive solution: I guess there is a way by computing base pattern and concatenate substring rather than adding char one by one ;P)

Answer 9

visph sorry but i think you are mistaken

for both i and i+1 to be valid indices, i has to be less than N-1

Answer 10

ok, for 5000 digits numbers you should handle the problem by using strings and generate all valid combinations ^^

however, I'm not sure that recursion is required to solve it ;)

Answer 11

P.M. well done for improving efficiency... however, output is not exactly what's expected (if I correctly understand the task): shouldn't your for loop in main function be:

for (int i = 1; i < 10; i++) {

to print all possibilities?
your own loop for k (included) to 10-k (not included) ^^

Answer 12

Ali_combination When not restricted to arbitrary requirements like, "make it work with recursion," it's pretty straight forward to implement.

Here's a code I threw together to demonstrate it with less complexity.

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

NOTE: My general approach was taken after reviewing the Python version from visph.

But... you'll see here how recursion is completely unnecessary.

Also... your rational for using recursion could be applied to any imperative or functional looping construct as well.

Recursion is a strong candidate for me when I see a pattern of repeatable logic where the context of nested scopes via new call stacks can improve the flow over using alternative looping constructs.

That benefit, for this problem, just isn't something that's jumping out at me upon initial glance.

However... technically... maybe... the list comprehensions are a form of recursion behind the scenes. But that's a stretch.

Answer 13

David Carroll I'm afraid that your code doesn't fulfill requirements: it doesn't return all possible n digits numbers with digit step of k, but only a subset... ;P

Answer 14

Ali_combination i think you meant

for each i, 0<= i < N - 1

not

for each i, 0<= i <= N

Answer 15

Bot yes you're right: I was taken account only of i, forgotten i+1 ^^

Answer 16

is the last python code supposed be the implementation I suggested in my first post???

you may have not understand what I was meaning: my code is very much more simple ;P

you have only to define a check function and do one iteration wich call it (could be a list comprehension to filter the valid values, or a simple loop to print every valid numbers)... no more.

Answer 17

I do not have the time now to implement my idea in C++, but I'm quite sure I could do shorter than your, and potentially more efficient ^^

anyway, if I enter 5 3 as input your C++ code only output five 0... it seems to not work ;P

I don't know what you are trying to achieve with the last python code: it even don't ask for input!

Answer 18

yes, for k >= 5 it should do no loops at all (as k >= 10 - k)...

Answer 19

P.M. I don't think so: a number cannot start with a 0 digit ;P

Answer 20

David Carroll You are completely right . Most people do not make me aware of these precious points you mentioned , so I used to think that the way I was explaining was proper.I also shouldn't have used short form of words like deat( = deet).I should pay especial attention to the correct way of illustrating points .
I totally admit that it was a struggle to understand.So I want to clear all points up and keep it as similar as legal way of writing, please let me know if I made it or not...

You are given two integers N and K in a single line . The task is to print all possible positive N-digit numbers which absolute value of difference between any two consecutive digits is strictly K . Formally ,for each i, 0<= i <= N-2 value of | number[i] - number[i+1] | is exactly K .

input 1 : 3 8
output 1 : 191 , 808 , 919

Explanation : The number 191 is a valid output . Because abs(1-9) = abs(9-1) = 8 . The number 808 is a valid number number .abs(8-0) = abs(0-8) = 8 . The last number is valid too .abs(1-9)=abs(9-1)=8