hello! i'm doing a module in programming and I've encountered some problems with an assignment! ):
the input is a single integer M, that has digits 1 through 9, wihout repeats and can have any number of digits. and I'm suppose to output the next cyclerun number higher than the input.
cyclerun number is an integer with unique digits, none of it can be zero. for example, 81362. then you start with the leftmost digit, and count that number of times to the right, wrapping to the first when the end of the integer is reached. repeat with the digit that you stopped on and till you end up with the first digit again. and you only can touch each digit once.
the following is my code. it can be compiled and run. but it'll just give me an output that is input + 1.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <sstream>
usingnamespace std;
bool isCycleRunNumbers(int input) {
int len;
int input_1[len];
int n;
int i = 0;
while (input_1[i] != 0) {
n = input_1[i];
input_1[i] = 0;
i = i + n - len;
}
i = 1;
while (input_1[i] == 0) {
i++;
returntrue;
}
returnfalse;
}
int solve(int input) {
while (!isCycleRunNumbers(input)) {
input++;
}
return 0;
}
int noOfDigits(int input) { // To get the number of digits in the integer entered
ostringstream o;
o << input;
int len = o.str().size();
return len;
}
int main() {
int input;
cin >> input;
input++;
noOfDigits(input);
isCycleRunNumbers(input);
if (isCycleRunNumbers(input)) {
cout << input << endl;
}
else {
solve(input);
}
return 0;
}
bool isCycleRunNumbers(int input) {
int len;
int input_1[len];
int n;
int i = 0;
input_1[len] = input; // added in this
while (input_1[i] != 0) {
n = input_1[i];
input_1[i] = 0;
i = i + n - len;
}
for (i = 1; i < len; i++) { // and changed this
if (input_1[i] == 0) {
returntrue;
}
else {
break;
}
}
returnfalse;
}
Firstly you are using variables without initializing them.
n = input_1[i]; // input_1[i] does not have any value.
Secondly, int input_1[len]; is incorrect. len should be a compile time constant.
Thirdly if you want input_1 array to be a copy of the input array, then you will have to copy it element by element. At present, input is just an integer whereas input_1[] is an array.
I suggest you go through the tutorial on this website to brush up on how arrays and function parameters work in C++.
oh, ok, no wonder there was an error at those parts.
anyway, i tried to do it in a different way. but ended with an endless loop. and i cant figure out where went wrong, though i think there's a lot of errors somewhere..
I'd like to help, but your description of the requirements is a little vague.
From what I gathered, there are two integers involved : M and cyclerun.
Please correct me if I'm wrong with any of this.
Both of these integers can have any number of digits, and each digit is a number between 1-9 inclusive (no zeros). Also, each digit can only appear once, which means the longest either integer could ever be is nine digits.
By that logic, any of the following values would be valid for M and cyclerun:
4
139
64537 (assuming unsigned int)
then you start with the leftmost digit, and count that number of times to the right
That's where you lost me. If cyclerun is 81362, does that mean you would start by cycling through through each digit 8 times? If you wrap, you'd end up on 6. Also, where does the value of cyclerun come from?
Please clarify.
if i start with the leftmost digit, (which in this case will be 8), then i'll count that number of times(i.e. count 8 times) to the right, wrapping back, and yes, i'll end up on 6.
then i'll repeat the cycle, which in this case, i'll count 6 times, and will end up on a new digit: 2 8 1 3 6 2 (i'll end up on 2).
repeat again, in this case, count 2 times: 8 1
continue again: 3
the count 3 steps: 6 2 8 and i'll end back on the first digit that i started out with.
at the end of each cycle, i'm supposed to reach a new digit, one that hasnt been landed on before. and at the end, have to end where i started (in this case, the digit 8)
so 81362 is a cyclerun number.
if an integer can't fulfill all these, then it is not a cyclerun number.
for example, 139 is not a cyclerun number. neither is 64537.
and so for the program, the user is to enter a integer M. then the program will have to find a cyclerun number that is larger than M.
Here is the solution I came up with. This was really fun to figure out actually.
This is, however, a pretty terrible solution in my opinion. It uses string streams and it's not necessarily portable. It's pretty hacky, but it works:
@xismn
+1 for your code. However, why do you say it's not portable? Apart from a few system commands (that can be avoided) I can't see anything non-portable in your code.
Though it maybe made slightly more efficient by changing the following:
1 2 3 4
index += digits[index];
while(index>=size) {
index-=size;
}
to
1 2 3 4
index+=digits[index] % size;
if ( index >= size ) {
index -= size;
}
However, since the maximum number of digits is only 9, the above change won't make much of difference.
Yeah, it was pretty late. There certainly are ways of making it prettier. I was tired and I just wanted to post it and go to bed, haha. I don't know what made me think it wouldn't have the capacity to be portable, I think what I meant to say was that it's sloppy and that there isn't any real error checking/handling.
Nice work with the use of modulo. Modulo was my first instinct, but I just couldn't get it to work for some reason.
EDIT* it was because I had
Here you go. I've made some slight modifications to the original.
I thought it might be better for me to paste the code again, instead of editing my original post, because I always think it's confusing when someone modifies their original code.
#include <windows.h>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#define WIN32_LEAN_AND_MEAN //Strip windows.h of excessive headers.
#define _SECURE_SCL 0 //Totally not safe. Prevents iterators from being checked as well as some other things. Can speed things up.
typedefunsignedlong ulong;
bool isValid(const std::string& number) {
/*
This function takes a const string reference parameter, to see if the number contained within is a valid one.
A number is considered to be valid when all of its digits are unique and don't occur more than once.
Additionally, a valid number cannot contain a zero in any of its digits.
Because of these restrictions, it is safe to assume that a number will never have more than 9 digits.
A 4-byte integer cannot hold a number of that size, which is why I've made the 'ulong' typedef on line 10. I've decided to
keep things unsigned because of complications of negative numbers being read by the stringstream.
*/
std::string temp = ""; //temp will act as a lookup/dictionary.
//we will push unique digits from the number string to temp, to keep track of which digits are present in the number string.
unsignedshort size = number.size();
if(size==0) {returnfalse;} //this should never be the case, but whatever.
for(unsignedshort digit=0; digit<size; ++digit) { //for each digit in the string
if(number[digit]=='0') {returnfalse;} //if the digit is a zero return false
if(temp.size()==0) { //this will only happen once. temp is empty, which means there are no previous digit definitions.
temp.push_back(number[digit]); //we can safely push the first digit on to temp without conflicts.
}else {
for(unsignedshort i=0; i<temp.size(); ++i) { //if there are digit definitions present in temp, iterate through them.
if(number[digit]==temp[i] && digit!=i) { //if there is another instance of the same digit in the numberstring
returnfalse; //then our number is invalid, as there are multiple instances of the same digit.
}
}
temp.push_back(number[digit]); //if the current digit didn't conflict with previous definitions in temp, we can push it to temp.
}
}
returntrue; //if our number string survived all that, it's valid.
}
bool isCRN(const std::string& number) {
/*
This function also takes a const string reference parameter.
You should only pass valid number strings to this function.
This function confirms whether or not a valid candidate number string is a cyclerun number.
*/
std::vector<ulong> digits;
std::vector<bool> taken; //You could use some kind of bitfield here instead, but whatever.
unsignedshort size = number.size();
for(unsignedshort i=0; i<size; ++i) { //we iterate through the digits of the number string.
digits.push_back((ulong)(number[i]-48)); //and push each digit (cast as ulong) to the digit vector.
taken.push_back(false); //and fill the taken vector with 'false'.
}
size = digits.size(); //this is me being paranoid. There's no reason for number.size() and digit.size() to be different.
short index=0;
for(unsignedshort i=0; i<size; ++i) { //iterate through each digit. A true cyclerun number will have completed its full cycle in the same number of digits in the number.
index+=digits[index]%size; //This just works. I could write a whole lot here, but I think it makes more sense to just work it out on paper.
if(index>=size) { //Wrap
index-=size;
}
if(taken[index]==false) { //if the digit at location 'index' has not already been landed on
taken[index]=true; //then mark it as taken
}else { //otherwise, if it already has been taken
returnfalse; //it's not a CRN.
}
} //digit for loop is now over.
for(unsignedshort i=0; i<taken.size(); ++i) { //iterate through the taken vector.
if(taken[i]==false) { //If one of the digits has not been taken
returnfalse; //it's not a CRN
}
}
returntrue; //Yay.
}
ulong findCRN(ulong x) {
std::stringstream stream;
while(1) {
x++;
stream.str("");
stream << x;
if(isValid(stream.str())) {
if(isCRN(stream.str())) {
return x;
}
}
}
}
int main(int argc, char* argv[]) {
SetConsoleTitleA("Cyclerun");
ulong x=0;
std::cout << "Enter a value: ";
std::cin >> x;
while(1) {
x = findCRN(x);
std::cout << x << std::endl;
std::cin.sync();
std::cin.get();
}
return 0;
}
Let me know if there's anything else I should document, or if I was too vague.