Form minimum number from the given sequence of I's and D's

Question

Given a sequence consisting of 'I' and 'D' where 'I' denotes increasing sequence and 'D' denotes the descreasing sequence. Write a program that decodes the given sequence to construct minimum number without repeated digits. The digits should start from 1 i.e. there should be no zeroes.

   Input: D        Output: 21
   Input: I        Output: 12
   Input: DD       Output: 321
   Input: II       Output: 123
   Input: DIDI     Output: 21435
   Input: IIDDD    Output: 126543
   Input: DDIDDIID Output: 321654798

My python code works. I translated it into C++ but the C++ version doesn't work. I don't understand why.

Python code (Works):

s = input()
ans = [1]
count = 0
for i in s:
    if i == 'I':
        count = 0
        k = len(ans)
        ans.append(k + 1)
    else:
        count += 1
        tmp = ans[-1]
        for i in range(-1, -1 - count, -1):
            ans[i] += 1
        ans.append(tmp)
for i in ans:
    print(i, end = "")

C++ code (Doesn't work i.e. doesn't give the correct output)

#include <bits/stdc++.h>

using namespace std;

vector<int> digits(string s){
    vector<int> ans = {1};
    int count = 0;
    for (char const &c : s){
        if (c == 'I'){
            count = 0;
            int k = ans.size();
            ans.push_back(k + 1);
        }
        else{
            count ++;
            int tmp = ans.back();
            for (int i = ans.size() - 1; i > ans.size() - 1 - count; i--){
                ans[i] += 1;
            }
            ans.push_back(tmp);
        }
    }
   return ans; 
}

int main(){
    string s;
    cin >> s;
    vector<int> ans = digits(s);
    for (int i = 0; i < ans.size(); i++){
        cout << ans[i];
    }
    return 0;
}

Eg - When I input DD in the C++ code, it gives 111, but it should output 321.

Don't add "edit" or "update" to your question. Just make the question complete. We can see the edit history if we need to know how it changed. — Mad Physicist, Jul 14 '20 at 16:30
@MadPhysicist D, we start from 1. We don't use zero. That's a constraint. — Just another person, Jul 14 '20 at 16:33
Makes sense. So you are guaranteed a sequence of no more than 8 letters? — Mad Physicist, Jul 14 '20 at 16:34
Have you tried debugging the C++, using a debugger or print statements? — Mad Physicist, Jul 14 '20 at 16:35
You should add some print statements to your code to monitor the values of your variables, or use a debugger! Your for loop is never entered because `ans.size() - 1 - count` leads to an integer underflow as `ans.size()` returns an `std::size_t` which is an unsigned integer. — NotAProgrammer, Jul 14 '20 at 16:36
@MadPhysicist I'd tried printing. I didn't yet use a debugger though (I'm just a beginner, so I'm learning, my bad). — Just another person, Jul 14 '20 at 16:39
@Justanotherperson On an unrelated note, [don't use `#include `](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) — NotAProgrammer, Jul 14 '20 at 18:43

score 4 · Accepted Answer · edited Jul 14 '20 at 18:14

4

ans.size() in C++ returns a size_t, which is unsigned (either 32-bit or 64-bit depending on your configuration). You can simply cast ans.size() to an int to fix your issue, like so:

for ( int i = static_cast<int>(ans.size()) - 1; i > static_cast<int>(ans.size()) - 1 - count; i-- )

Using a debugger, you could check that you never actually got into the for-loop's body, for your input.

As NotAProgrammer notes, unsigned-to-signed conversion may be implementation defined, but this should work in most (all?) cases for your examples. From [conv.integral]/3:

If the destination type is signed, the value is unchanged if it can be represented in the destination type; otherwise, the value is implementation-defined.

edited Jul 14 '20 at 18:14

NotAProgrammer

552
1
5
15

answered Jul 14 '20 at 16:36

ChrisMM

8,448
13
29
48

2

Just a note that casting unsigned to signed is implementation-defined. – NotAProgrammer Jul 14 '20 at 16:38
@NotAProgrammer can you elaborate that a bit with an example? I didn't understand. – Just another person Jul 14 '20 at 16:40
@Justanotherperson, see my edit with the quote from the C++ standard. – ChrisMM Jul 14 '20 at 16:42
@NotAProgrammer Only for values outside the range of the unsigned type. It seems unlikely `ans.size()` will be larger than the maximum value of `int`, especially assuming that `int` is at least 32-bit (as it probably is). – Arthur Tacca Jul 14 '20 at 16:42
@ArthurTacca It's true that it is unlikely to lead to a problem in this case, but you know what they about "assume". Edit: Isn't it true for values outside the range of the signed type, rather than the unsigned type? – NotAProgrammer Jul 14 '20 at 16:43
@NotAProgrammer. I assume that they say it's a good idea :) – Mad Physicist Jul 14 '20 at 16:45
@NotAProgrammer are there specific cases where we need to convert 'unsigned int' into 'int' even if the value is very low ? – Just another person Jul 14 '20 at 16:49
@NotAProgrammer Oops, you're right about that edit. But I am prepared to risk the consequences of my assumption when violating it would require the user to manually enter a string more than 2 billion characters long, and the code appears to assume the string is less than 10 characters! – Arthur Tacca Jul 14 '20 at 16:52
1

@Justanotherperson [This answer](https://stackoverflow.com/a/56528886/3672674) may shed some more light on this (and the thread as well). But no, I can't think of a time when using small numbers non-negative numbers will lead to a problem. Of course in your case you tried to assign -1 to an unsigned int which lead to a problem. – NotAProgrammer Jul 14 '20 at 16:54
@NotAProgrammer where is -1 assigned to an unsigned int? – Just another person Jul 14 '20 at 16:57
@Justanotherperson What is the result of `ans.size() - 1 - count` on the first time the condition is checked? – NotAProgrammer Jul 14 '20 at 17:05
@NotAProgrammer oops, my bad. – Just another person Jul 14 '20 at 17:06

Form minimum number from the given sequence of I's and D's

1 Answers1