Marathon puzzles in C ++

Greetings to all!

In this post we will discuss the solution of several puzzles that I spied from the “Marathon of C ++ tasks” (I think the links can easily be found by a search engine). No, I have absolutely no relation to the site, but I learned about it from Habr: either I had someone in my profile, or there was a link in the comments, though I doubt that this would prevent the followers of the local conspiracy theory from easily minus the topic. He exhaled ... So, we will define the tasks, the solutions of which will be considered (only 9 problems, but these seemed interesting to me):

Forgot how to multiply. Help!
Multiply the number by 7 without using the multiplication operation.
Two in one.
Some clever swap buttons in the elevator. I put the second floor instead of the first floor, and the first one instead of the second floor. Honestly, I'm too lazy to pick buttons. I'd rather reprogram the elevator. But I'm too lazy to program. You have all the hope. Write, please, a switch function that returns 1 if input 2 and 2, if input 1.

Training

Usually, I am not at all pulling (not pulling) to solve problems of such an “entertaining” (and, possibly, informative) kind, but this time, then the beautiful weather outside the window, or the working-smoothly flowing-in-non-working day did their job and I decided. As I have already described, I came across an article (it would be better to write a cycle of 3 articles) about a certain marathon of tasks in C ++. Curiosity took over and decided to sketch solutions: but not in the head, as usual, but on paper. And, as you might guess, after the first line crossed out, I finished this crazy work (writing on paper) and decided this: I use only a simple text editor (gedit) and, in extreme cases, google.
')

Go

Task number one:

Forgot how to multiply. Help! Multiply the number by 7 without using the multiplication operation.

The solution for a single-flow execution model suggests itself:

the function, which takes as an argument a number to multiply by 7, performs 7 consecutive additions, and then returns the result (runtime) :

//      typedef unsigned long long TCurrentCalculateType; inline TCurrentCalculateType mulby7(TCurrentCalculateType value) { return value + value + value + value + value + value + value; } //  ,  assert()   // #include <assert.h> #ifdef DEGUB assert(mulby7(1) == 7); assert(mulby7(7) == 49); #endif //DEBUG

An article on this can not be pulled out. Let's take a broader look: in general, what a limitation is this - to multiply an arbitrary number by exactly 7? Disorder: give the multiplication of an arbitrary number by an arbitrary number without using multiplication:

An iteration function that takes as an argument a number to multiply by N, performs N consecutive additions in a loop, and then returns the result (runtime):

 //    // typedef unsigned long long TCurrentCalculateType; inline TCurrentCalculateType mulbyN(unsigned long long times, TCurrentCalculateType value) { TCurrentCalculateType result = 0; for(unsigned long long i = 0; i < times; ++i) result += value; return result; } //  ,  assert()   // #include <assert.h> #ifdef DEGUB assert(mulbyN(7, 1) == mulbyN(1, 7)); assert(mulbyN(7, 7) == 49); #endif //DEBUG

the parameterized class, which receives as an argument a number to multiply by N, performs N consecutive additions, recursively instantiating templates, and then the result is available in the static const class member (compiletime):

 //    // typedef unsigned long long TCurrentCalculateType; // : , , : , ... //  N + 1   ( ) template <typename T, T value, int step> struct mulStep { static const T partSumm = value + mulStep<T, value, step - 1>::partSumm; }; //  ,   template <typename T, T value> struct mulStep<T, value, 0> { static const T partSumm = 0; }; template <unsigned long long times, TCurrentCalculateType value> struct mulbyNct { static const TCurrentCalculateType result = mulStep<TCurrentCalculateType, value, times>::partSumm; }; static_assert(mulbyNct<7, 7>::result == 49, "Imposible!"); static_assert(mulbyNct<10, 10>::result == 100, "Imposible!");

Yes, the third option was not written “from the fly”: we had to refresh in memory a very similar to our problem example of calculating factorial . Sighted what to do. But, in fact, I originally wrote the following code, which, although it looks more organic in use than the one proposed above, is not going to, due to some (logical) restrictions:

 template <int times, typename T> inline T mulbyNct(T value) { return mulStep<T, value, times>::partSumm; } //  ... // std::cout << mulbyNct<7>(calcMeDigit) << std::endl; //  .   :(

“Freak, kid,” the attentive reader will notice. I agree that you can optimize bread crumbs: if you initialize result initial value equal to value , you will be able to save at one step of the cycle. We get:

 //    // typedef unsigned long long TCurrentCalculateType; inline TCurrentCalculateType mulbyNlittleFast(unsigned long long times, TCurrentCalculateType value) { TCurrentCalculateType result = value; //   for(unsigned long long i = 1; i < times; ++i) //   result += value; return result; } //     //     ,   #undef mulbyN #define mulbyN mulbyNlittleFast //  ,  assert()   // #include <assert.h> #ifdef DEGUB assert(mulbyN(7, 1) == mulbyN(1, 7)); assert(mulbyN(7, 7) == 49); #endif //DEBUG

“All the same, there are few options,” I thought, and, opening this saytik , looking at the functors, I realized the fourth option:

Oh, this fourth option:

 //    // typedef unsigned long long TCurrentCalculateType; inline TCurrentCalculateType mulbyNSTL(unsigned long long times, TCurrentCalculateType value) { TCurrentCalculateType result = value; std::binder1st<std::plus<TCurrentCalculateType> > plus1st(std::plus<TCurrentCalculateType>(), value); for(unsigned long long i = 1; i < times; ++i) result = plus1st(result); return result; } //  ,  assert()   // #include <assert.h> #ifdef DEGUB assert(mulbyNSTL(7, 1) == mulbyNSTL(1, 7)); assert(mulbyNSTL(7, 7) == 49); #endif //DEBUG

I know, I need to marry, and not to invent such monsters ... but not about that now. In order to talk about which solution is “better,” you first need to decide on the comparison metric. On good - the metric of the minimum product of the used memory and runtime:

algo_diff = used_mem * calc_time;
algo_winner = min(algo_diff(1, 2, 3, ..., N))

And the weather is excellent, so I decided to stop only at minimizing the execution time: faster - better.

Prepare to fight

Let's start with the things that I didn't want to write myself - the “timer” of the runtime. For the measurement we will use the class found once on the Internet. This class is small and simple, but even it uses the semblance of the RAII principle (yes, google help again). Place it on the stack and voila:

 #include <stdio.h> #include <string> #include <sys/time.h> #include <sys/timeb.h> class StackPrinter { public: explicit StackPrinter(const char* msg) : msMsg(msg) { fprintf(stdout, "%s: --begin\n", msMsg.c_str()); mfStartTime = getTime(); } ~StackPrinter() { double fEndTime = getTime(); fprintf(stdout, "%s: --end (duration: %.10f sec)\n", msMsg.c_str(), (fEndTime-mfStartTime)); } void printTime(int line) const { double fEndTime = getTime(); fprintf(stdout, "%s: --(%d) (duration: %.10f sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime)); } private: double getTime() const { timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec + tv.tv_usec / 1000000.0; } ::std::string msMsg; double mfStartTime; }; // Use case // //{ // StackPrinter("Time to sleep") sp; // sleep(5000); //}

But, this "printer" is suitable for output to the console, but I want a more convenient output for later analysis using LabPlot ( LabPlot sourceforge ). Here you can cry in bloody tears, for I maliciously violate DRY (let the bloody tears flow from the one who saw this. And in general, make allowances for warm weather and cold head):

StackPrinterTiny

 class StackPrinterTiny { public: explicit StackPrinterTiny(const char* msg) { mfStartTime = getTime(); } ~StackPrinterTiny() { double fEndTime = getTime(); fprintf(stdout, "%g\n", (fEndTime-mfStartTime)); } void printTime(int line) const { double fEndTime = getTime(); fprintf(stdout, "(%d) %g\n", line, (fEndTime-mfStartTime)); } private: double getTime() const { timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec + tv.tv_usec / 1000000.0; } double mfStartTime; }; #ifdef OutToAnalyze typedef StackPrinterTiny usedStackPrinter; #else typedef StackPrinter usedStackPrinter; #endif // Use case // //{ // usedStackPrinter("Time to sleep") sp; // sleep(5000); //}

At the finish line

Now, to get the craft together, we need a little “binding” code - let's respect the compiler:

 #include <iostream> #include <functional> #include <stdio.h> #include <string> #include <sys/time.h> #include <sys/timeb.h> #include <climits> typedef unsigned long long TCurrentCalculateType; // Closured: result, fiMax // loop, loooop, loooooooop #define LOOP_LOOP(what) \ for(unsigned long long fi = 0; fi < fiMax; ++fi) \ for(unsigned long long fi2 = 0; fi2 < fiMax; ++fi2) \ for(unsigned long long fi3 = 0; fi3 < fiMax; ++fi3) \ result = what int main() { //     mulbyNct<> const TCurrentCalculateType calcMeDigit = 9000000; const unsigned long long fiMax = ULLONG_MAX; #ifndef OutToAnalyze std::cout << "Calculate: " << calcMeDigit << " with fiMax = " << fiMax << std::endl; #endif currentCalculateType result = 0; #ifdef CALCULATE_IN_COMPILE_TIME std::cout << "compile time " << calcMeDigit << " * " << calcMeDigit << " = " << mulbyNct<calcMeDigit, calcMeDigit>::result << std::endl; #endif { usedStackPrinter sp("1"); // on image - mulby7 LOOP_LOOP(mulby7(calcMeDigit)); #ifndef OutToAnalyze std::cout << "by x7 = " << result << std::endl; #else std::cout << "=" << result << std::endl; #endif } { usedStackPrinter sp("2"); // on image - mulbyN LOOP_LOOP(mulbyN(calcMeDigit, calcMeDigit)); #ifndef OutToAnalyze std::cout << "x*x where x is " << calcMeDigit << " = " << result << std::endl; #else std::cout << "=" << result << std::endl; #endif } { usedStackPrinter sp("3"); // on image - mulbyNSTL LOOP_LOOP(mulbyNSTL(calcMeDigit, calcMeDigit)); #ifndef OutToAnalyze std::cout << "STL x*x where x is " << calcMeDigit << " = " << result << std::endl; #else std::cout << "=" << result << std::endl; #endif } return 0; } // Compile with // // clear && g++ main.1.cpp -O3 -std=c++0x -o main.1 // PS      -Ofast.    -  .

We have everything you need to successfully build and get results. If gathered (and it should) - we continue.

We thought, we thought - our nuclei are tired

By the way, I haven’t forgotten yet: I couldn’t calculate more than 498 * 498 in compile time. In other words, if I set calcMeDigit = 499 (and more) for ifif #if defined(CALCULATE_IN_COMPILE_TIME) , I received a compilation error: I’m not stack overflow when deploying templates? I repent, did not understand. So, we return to the tests at run time : the figures are, in my opinion, meaningless, because on your machine, they will be different: but to visualize in a picture - it will go. Hmm, I see you began to forget how to cry with bloody tears - I’m happy to remind you. The following is a script that helped collect the numbers into a file for later analysis and building pictures in LabPlot (I warned you):

main.1.to.out.sh

# / bin / sh
./main.1> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
./main.1 >> out.txt
# And what did you expect? }: ->

Results on my machine (Intel® Core (TM) i5 CPU @ 2.8 GHz CPU, 8 GiB Memory):

Scott Meyers tip 43 says "Use algorithms instead of cycles." In a broader sense, advice can be understood as using standard algorithms, collections, and objects to get more readable, supported and secure, and, sometimes, more efficient code. What the fuck ... dozhnik, you ask (I have already stopped asking this question), the average time of the mulbyNSTL variant is less than that of its parent mulbyN . I sin on my not completely straight arms ... but that is, that is.

The first one, I'm the second.

Problem number two:

Two in one. Some clever swap buttons in the elevator. I put the second floor instead of the first floor, and the first one instead of the second floor. Honestly, I'm too lazy to pick buttons. I'd rather reprogram the elevator. But I'm too lazy to program. You have all the hope. Write, please, a switch function that returns 1 if input 2 and 2, if input 1.

Pokumekav, I came up with only 1 solution:

the function that takes the floor number as an argument produces a bitwise modulo-two addition and returns the result:

 int worker1(unsigned int n) { return (n xor 3); } //  ,  assert()   // #include <assert.h> #ifdef DEGUB assert(worker1(2) == 1); assert(worker1(1) == 2); #endif //DEBUG

One option is not enough. One option is not to compare, so I decided to come up with a second idiotic option: it makes a bitwise “AND”, increments the result and returns the resulting value:

 int worker2(unsigned int n) { return (n & 1) + 1; } //  ,  assert()   // #include <assert.h> #ifdef DEGUB assert(worker2(2) == 1); assert(worker2(1) == 2); #endif //DEBUG

And, to my misfortune, I had a peek at the elegant answer of this problem (according to the version of the one who produced it): we return the result of subtracting the number of the floor from 3:

 int worker3(unsigned int n) { return 3 - n; } //  ,  assert()   // #include <assert.h> #ifdef DEGUB assert(worker3(2) == 1); assert(worker3(1) == 2); #endif //DEBUG

Teperich, using the already known script for data collection (you could not forget the bloody tears), we will write a program to test the speed of execution of these tiny functions (worker1, worker2, worker3). It seems that you have already suspected my unhealthy craving for patterns - I hurry to upset you, this is not true. And what about us? This is a helper class for using generators in the std::generate algorithm:

 // Like binder1st // require #include <numeric>, #include <random> template <class Operation, class TRandomEngine> class binderRandom: public std::unary_function <void, typename Operation::result_type> { protected: Operation op; TRandomEngine& y; public: binderRandom ( const Operation& x, TRandomEngine& y) : op (x), y (y) {} typename Operation::result_type operator()() { return op(y); } };

The idea is as old as C ++ world: we construct a vector of random numbers (floor numbers, i.e. [1, 2]) and perform the proposed functions for each element of the sequence ... Total:

 #include <iostream> #include <functional> #include <stdio.h> #include <string> #include <sys/time.h> #include <sys/timeb.h> #include <climits> #include <vector> #include <algorithm> #include <numeric> #include <random> #include <iterator> int main() { static std::mt19937 _randomNumbersEngine; std::vector<unsigned int> _vectorNumbers(50000000); //    ? std::uniform_int<unsigned int> uiRandomNumber(1, 2); std::generate(_vectorNumbers.begin(), _vectorNumbers.end(), binderRandom<std::uniform_int<unsigned int>, std::mt19937>(uiRandomNumber, _randomNumbersEngine)); //    - //    // { usedStackPrinter sp("1"); std::transform(_vectorNumbers.begin(), _vectorNumbers.end(), _vectorNumbers.begin(), worker1); } { usedStackPrinter sp("2"); std::transform(_vectorNumbers.begin(), _vectorNumbers.end(), _vectorNumbers.begin(), worker2); } { usedStackPrinter sp("3"); std::transform(_vectorNumbers.begin(), _vectorNumbers.end(), _vectorNumbers.begin(), worker3); } return 0; }

Results on my machine (Intel® Core (TM) i5 CPU @ 2.8 GHz CPU, 8 GiB Memory):

Here the result is adequate: both (normal) variants are performed in the same time (we will throw off the difference as the measurement error). Interestingly, and if you look at the generated code, it will be similar or even the same? This is a topic for another conversation, so it remains for the reader to do the homework.
In any case - I liked to do this garbage, which means that time was not wasted (personal value judgment).

Update:
Added by:

 inline TCurrentCalculateType mulby7fast(TCurrentCalculateType value) { return (value << 3) - value; }

Updated results on my machine (Intel® Core (TM) i5 CPU @ 2.8 GHz CPU, 8 GiB Memory):

Update # 2
Awesome distribution of cons and pros:

If someone knows in which compiler it will meet:

 inline float mulby7fast(float value) { return (value << 3) - value; }

please do not hesitate to write.

Yes, I did not know (and I can’t think of such a thing) that:
Multiplication by an arbitrary number is done as the sum of the shifts at the position where in the multiplier there is one
Learn with the help of Google - not to learn, but to spy.
Quiet downsides - very inspiring

Conclusion

It turns out that writing without IDE with all kinds of auto complete (such as Visual Assist X from Whole Tomato) is not so deadly difficult (apparently no more than 200+ lines and simple logic). Yes, there are a lot of things missing: clever alignment, paired brackets and quotation marks, but there is something in it ... something that tells me: correct and convenient IDE is cool!

Version gcc 4.4.5 and therefore I did not use lambda - and in fact in cases with “workerN” it would have looked great

 std::transform(_vectorNumbers.begin(), _vectorNumbers.end(), _vectorNumbers.begin(), [](int n) { return n xor 3; } );

So it goes. Thank you for your attention and good luck!

^{PS Errors or typographical errors, please write to the PM.}

Source: https://habr.com/ru/post/177111/

All Articles