From def033119a52ddd4a71bdc31fc2baa7adb0a7c44 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 19:33:55 -0400 Subject: c++ solution for challenge 74 task 2 --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 39 +++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 challenge-074/walt-mankowski/cpp/ch-2.cpp (limited to 'challenge-074/walt-mankowski/cpp/ch-2.cpp') diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp new file mode 100644 index 0000000000..dc94578e19 --- /dev/null +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -0,0 +1,39 @@ +#include +#include +#include +#include + +using namespace std; + +int main(int argc, char *argv[]) { + const char *s = argv[1]; + set seen; + list nr; + char *out = new char[strlen(s)+1]; + out[strlen(s)] = '\0'; + + for (size_t i = 0; i < strlen(s); i++) { + const char c = s[i]; + + // have we seen c before? + if (seen.find(c) == seen.end()) { + seen.insert(c); + nr.push_back(c); + } else { + // remove c from nr + for (auto x = nr.begin(); x != nr.end(); x++) + if (*x == c) { + nr.erase(x); + break; + } + } + + if (nr.empty()) + out[i] = '#'; + else { + auto p = *(nr.crbegin()); + out[i] = p; + } + } + cout << out << endl; +} -- cgit From 2939a88fedf20679bde35a93e9b6c74c79d33d1d Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 19:47:01 -0400 Subject: use std::find() to find c in nr Nicer than doing it by hand! --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'challenge-074/walt-mankowski/cpp/ch-2.cpp') diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index dc94578e19..c25f4cbe62 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -2,6 +2,7 @@ #include #include #include +#include using namespace std; @@ -21,13 +22,10 @@ int main(int argc, char *argv[]) { nr.push_back(c); } else { // remove c from nr - for (auto x = nr.begin(); x != nr.end(); x++) - if (*x == c) { - nr.erase(x); - break; - } + nr.erase(find(nr.cbegin(), nr.cend(), c)); } + // now the FNR is either the last element of nr, or # if (nr.empty()) out[i] = '#'; else { -- cgit From 8f23cc2dd5289e0a191417a13c94dbf552be0b8c Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 19:50:54 -0400 Subject: removed unneeded braces --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'challenge-074/walt-mankowski/cpp/ch-2.cpp') diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index c25f4cbe62..9e9822fc95 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -20,10 +20,9 @@ int main(int argc, char *argv[]) { if (seen.find(c) == seen.end()) { seen.insert(c); nr.push_back(c); - } else { + } else // remove c from nr nr.erase(find(nr.cbegin(), nr.cend(), c)); - } // now the FNR is either the last element of nr, or # if (nr.empty()) -- cgit From 0ca8c6f59ae500add88481add595ab8889b99f9d Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 19:52:44 -0400 Subject: removed unneeded temp variable --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'challenge-074/walt-mankowski/cpp/ch-2.cpp') diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index 9e9822fc95..efb1aa1225 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -27,10 +27,8 @@ int main(int argc, char *argv[]) { // now the FNR is either the last element of nr, or # if (nr.empty()) out[i] = '#'; - else { - auto p = *(nr.crbegin()); - out[i] = p; - } + else + out[i] = *(nr.crbegin()); } cout << out << endl; } -- cgit From 58a0d9119903d53470dce47142017d76aedb5e5e Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Wed, 19 Aug 2020 22:05:54 -0400 Subject: Store iterators to the positions in the list in a map This saves me having to find() each element -- now I can jump right to them. But I had to store the list in the opposite order since erase() doesn't like reverse iterators. --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'challenge-074/walt-mankowski/cpp/ch-2.cpp') diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index efb1aa1225..01fb9a916b 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -1,6 +1,6 @@ #include #include -#include +#include #include #include @@ -8,7 +8,7 @@ using namespace std; int main(int argc, char *argv[]) { const char *s = argv[1]; - set seen; + map::const_iterator> seen; list nr; char *out = new char[strlen(s)+1]; out[strlen(s)] = '\0'; @@ -18,17 +18,17 @@ int main(int argc, char *argv[]) { // have we seen c before? if (seen.find(c) == seen.end()) { - seen.insert(c); - nr.push_back(c); + nr.push_front(c); + seen[c] = nr.cbegin(); } else // remove c from nr - nr.erase(find(nr.cbegin(), nr.cend(), c)); + nr.erase(seen[c]); // now the FNR is either the last element of nr, or # if (nr.empty()) out[i] = '#'; else - out[i] = *(nr.crbegin()); + out[i] = *(nr.cbegin()); } cout << out << endl; } -- cgit From 13cdfa88e53569f70d9094b2d858490224a6cb25 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Thu, 20 Aug 2020 20:53:47 -0400 Subject: check for double-delete when removing c from nr After it's been removed, set the value in seen to end() so we know not to erase it again. --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'challenge-074/walt-mankowski/cpp/ch-2.cpp') diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index 01fb9a916b..b5f32cc7a4 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -20,9 +20,13 @@ int main(int argc, char *argv[]) { if (seen.find(c) == seen.end()) { nr.push_front(c); seen[c] = nr.cbegin(); - } else + } else { // remove c from nr - nr.erase(seen[c]); + if (seen[c] != nr.end()) { + nr.erase(seen[c]); + seen[c] = nr.end(); + } + } // now the FNR is either the last element of nr, or # if (nr.empty()) -- cgit From e519ffe2910e017d481548eec99c0590d748f82b Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Thu, 20 Aug 2020 21:26:15 -0400 Subject: use strings instead of char *'s --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'challenge-074/walt-mankowski/cpp/ch-2.cpp') diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index b5f32cc7a4..df7aec5325 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -1,4 +1,4 @@ -#include +#include #include #include #include @@ -7,13 +7,12 @@ using namespace std; int main(int argc, char *argv[]) { - const char *s = argv[1]; + const string s(argv[1]); + string out = string(s.length(), ' '); map::const_iterator> seen; list nr; - char *out = new char[strlen(s)+1]; - out[strlen(s)] = '\0'; - for (size_t i = 0; i < strlen(s); i++) { + for (size_t i = 0; i < s.length(); i++) { const char c = s[i]; // have we seen c before? -- cgit From 7b6d29c26480a31630c65e2e62dde7e960fa41e2 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Sun, 23 Aug 2020 09:17:27 -0400 Subject: no longer need to include algorithm --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 1 - 1 file changed, 1 deletion(-) (limited to 'challenge-074/walt-mankowski/cpp/ch-2.cpp') diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index df7aec5325..ab8b330e19 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -2,7 +2,6 @@ #include #include #include -#include using namespace std; -- cgit