feat: implement cpp local test #90

w43322 · 2023-02-02T09:29:06Z

Info

This pull request adds preliminary cpp local test support. #11

Tested on linux / gcc 12.2.1

How it works

After `pick` command

It creates new folders for each new question. The code that you write is in an automatically created file solution.h.

It automatically generates a file solution.cpp, which contains the testing code, and includes solution.h.

After `test` command with `-L` parameter

It executes command g++ -O2 -std=c++17 solution.cpp -o solution.exec

Then it writes the test case into input.txt, and executes command solution.exec input.txt output.txt

After the testing program finishes, it checks the content of output.txt against expected output, and shows the result.

If multiple test cases exist, the previously mentioned process is repeated.

Note:

No special judge implemented at this point, the judging function is a simple raw string comparison.
If you'd like to run custom tests, make sure to follow leetcode input format.
solution.exec takes exactly two arguments, which are paths for input and output files. It will exit prematurely if an incorrect number of arguments are provided, or if one of the file fails to open.

Prerequisites

Recent version of gcc / clang (that supports c++17 compilation)
If you use clang, make sure to create an alias (macOS does this automatically)
If you're on Windows, make sure to install tools like MinGW and add it to PATH

Completion Status

Implement I/O for basic data types
Implement I/O for LC DS (Linked List, Binary Tree)
Implement Local Testing
Implement Support for System Design Problems
Execution time output
Check for CE, RE, TLE, ~~MLE~~ and automatically stop the program if Time ~~/ Memory~~ exceeds a certain value

Example of a generated testing code

Click to Expand

// Code generated by https://github.com/j178/leetgo
#include <bits/stdc++.h>
using namespace std;

// definitions
struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};



#include "solution.h"

// helper funcs
auto &operator>>(istream &is, ListNode *&node) {
	node = nullptr;
	ListNode *now = nullptr;
L0: is.ignore();
L1: switch (is.peek()) {
	case ' ':
	case ',': is.ignore(); goto L1;
	case ']': is.ignore(); goto L2;
	default : int x; is >> x;
	          now = (now ? now->next : node) = new ListNode(x);
	          goto L1;
	}
L2: switch (is.peek()) {
	case '\r': is.ignore(); goto L2;
	case '\n': is.ignore(); goto L3;
	case EOF : goto L3;
	}
L3: return is;
}

auto &operator<<(ostream &os, ListNode *node) {
	os << '[';
	while (node != nullptr) {
		os << node->val << ',';
		node = node->next;
	}
	os.seekp(-1, ios_base::end);
	os << ']';
	return os;
}

auto &operator>>(istream &is, TreeNode *&node) {
	deque<TreeNode *> dq;
L0: is.ignore();
L1: switch (is.peek()) {
	case ' ':
	case ',': is.ignore(); goto L1;
	case 'n': is.ignore(5); dq.emplace_back(nullptr);
	          goto L1;
	case ']': is.ignore(); goto L2;
	default : int x; is >> x;
	          dq.emplace_back(new TreeNode(x));
	          goto L1;
	}
L2: switch (is.peek()) {
	case '\r': is.ignore(); goto L2;
	case '\n': is.ignore(); goto L3;
	case EOF : goto L3;
	}
L3: int n = dq.size();
	for (int i = 0, j = 1; i < n; ++i) {
		auto root = dq[i];
		if (root == nullptr) { continue; }
		root->left = j < n ? dq[j] : nullptr;
		root->right = j + 1 < n ? dq[j + 1] : nullptr;
		j += 2;
	}
	node = n ? dq[0] : nullptr;
	return is;
}

auto &operator<<(ostream &os, TreeNode *node) {
	queue<TreeNode *> q;
	int cnt_not_null_nodes = 0;
	auto push = [&](TreeNode *node) {
		q.emplace(node);
		if (node != nullptr) { ++cnt_not_null_nodes; }
	};
	auto pop = [&]() {
		auto front = q.front(); q.pop();
		if (front != nullptr) {
			--cnt_not_null_nodes;
			push(front->left);
			push(front->right);
			os << front->val << ',';
		} else {
			os << "null,";
		}
	};
	os << '[';
	if (node != nullptr) {
		push(node);
		while (cnt_not_null_nodes > 0) { pop();	}
		os.seekp(-1, ios_base::end);
	}
	os << ']';
	return os;
}

template <typename T>
auto &operator>>(istream &is, vector<T> &v) {
L0: is.ignore();
L1: switch (is.peek()) {
	case ' ':
	case ',': is.ignore(); goto L1;
	case ']': is.ignore(); goto L2;
	default : v.emplace_back();
	          if constexpr (is_same_v<T, string>) {
	              is >> quoted(v.back());
	          } else {
	              is >> v.back();
	          }
	          goto L1;
	}
L2: switch (is.peek()) {
	case '\r': is.ignore(); goto L2;
	case '\n': is.ignore(); goto L3;
	case EOF : goto L3;
}
L3: return is;
}

template <typename T>
auto &operator<<(ostream &os, const vector<T> &v) {
	os << '[';
	if constexpr (is_same_v<T, string>) {
		for (auto &&x : v) { os << quoted(x); os << ','; }
	} else if constexpr (is_same_v<T, double>) {
		for (auto &&x : v) { { char buf[32]; sprintf(buf, "%.5f", x); os << string(buf); } os << ','; }
	} else {
		for (auto &&x : v) { os << x << ','; }
	}
	os.seekp(-1, ios_base::end);
	os << ']';
	return os;
}



// main func
int main(int argc, char **argv) {
	if (argc != 3) {
		return 1;
	}

	ifstream ifs(argv[1]);
	if (!ifs.is_open()) {
		return 1;
	}

	ofstream ofs(argv[2]);
	if (!ofs.is_open()) {
		return 1;
	}

	// scan input args
	vector<int> weights; ifs >> weights;
	int k; ifs >> k;


	// initialize object
	Solution *obj = new Solution();


	// call methods
	auto &&res = obj->putMarbles(weights, k);


	// print result
	ofs << res;


	// delete object
	delete obj;

	ifs.close();
	ofs.close();
	return 0;
}

Future plans for improvement

make I/O more robust, for potential custom input (accept a variety of white spaces)
optimize the output function for binary trees (memory usage could potentially be cut in half)
more accurate time measurement, omitting time consumed by I/O operations

Tested problems

Click to Expand

suppoted	reason	qid	name	return type	arg1 type	arg2 type
no	unsorted return	0001	two-sum	vector	vector	int
yes	n/a	0002	add-two-numbers	ListNode*	ListNode*	ListNode*
yes	n/a	0003	longest-substring-without-repeating-characters	int	string	n/a
yes	n/a	0004	median-of-two-sorted-arrays	double	vector	vector
yes	n/a	0005	longest-palindromi-substring	string	string	n/a
yes	n/a	0006	zigzag-conversion	string	string	int
yes	n/a	0460	lfu-cache	SystemDesign	SystemDesign	SystemDesign
yes	n/a	0542	01-matrix	vector<vector>	vector<vector>	n/a
yes	n/a	0814	binary-tree-pruning	TreeNode*	TreeNode*	n/a
yes	n/a	0981	time-based-key-value-store	SystemDesign	SystemDesign	SystemDesign
yes	n/a	2551	put-marbles-in-bags	iint64_t	vector	int

j178 · 2023-02-02T09:59:41Z

@w43322 Hi, thank you for your hard work and contributions!

Your work is truly impressive and I'm looking forward to reviewing it in detail over the weekend.
I was also wondering if you would be okay with me making modifications to your code for further development?

w43322 · 2023-02-02T12:30:15Z

@w43322 Hi, thank you for your hard work and contributions!

Your work is truly impressive and I'm looking forward to reviewing it in detail over the weekend.

Thank you for your kind words! I really enjoyed working on this project. I'm fairly new to golang, so there might be some imperfections in the code, and many things may be simplified, or could be done in a better way. I'm going to write some comments and documents so other developers can add support for more languages in a similar manner.

I was also wondering if you would be okay with me making modifications to your code for further development?

Of course it's okay, that's what open source is all about. :-)

Still have some work left to do, but everything should be ready by Sunday.

.gitignore

lang/cpp.go

see j178#90 for more information

lang/cpp.go

lang/cpp/LC_DS.h

see j178#90 for more information

lang/cpp.go

lang/cpp/LC_DS.h

j178 · 2023-02-04T08:07:34Z

Regarding the generated input.txt, solution.exec, and output.txt, can we incorporate testcases into the source code directly, the program does not need to read from stdin and write to stdout. We get the return value from function and serialize it to string, compare it with the expected string directly, avoid generating an additional output.txt.

I also want to place the compiled binary in a temporary directory similar to what go run does, so that it does not generate additional files in the current directory. What do you think of this approach?

w43322 · 2023-02-04T11:27:34Z

Regarding the generated input.txt, solution.exec, and output.txt, can we incorporate testcases into the source code directly, the program does not need to read from stdin and write to stdout. We get the return value from function and serialize it to string, compare it with the expected string directly, avoid generating an additional output.txt.

I actually thought about this before implementing everything, but decided on the I/O approach because this approach has some serious drawbacks.

It needs to recompile the binary for every new test case, and that alone can take quite some time with -O2, and if your program is complicated, it'll be even worse. (Although we can incorporate all test-cases into the program and just do a one-pass, the following reasons still stand.)
This can complicate things when the user wants to provide custom input for testing. Although one can argue that, how do you get the expected output for the custom input? There's only one way - from LC online testing. But if we come to this, then people might say, why bother with local testing when we can do everything through LC API? IMO the main benefit of local testing is to reduce waiting time, both the latency that comes from the Internet and LC's restrictions (for non-premium users, if you submit code too frequently it will often refuse that).
Constructing pre-defined vectors in C++ is rather inefficient, especially when it's a vector of strings, or a vector of vectors. The resulted binary will initialize the vector objects by appending elements one by one, which is not much better than using I/O to initialize it.
The I/O approach is how most OJ systems do it, and I think LC's too. And the current implementation does not interfere with stdin/stdout, because it does the I/O on files. So users can output stuff onto stdout and it'll work as intended.
This can help make a more streamlined process when adding local test support for more languages in the future, as the maintainer will only need to implement the I/O interface. If we do it by comparing results inside the generated executable, then there would be a lot more work involved with each new language.

I also want to place the compiled binary in a temporary directory similar to what go run does, so that it does not generate additional files in the current directory. What do you think of this approach?

I think this is okay. Or we can delete the files after testing, which more or less yields the same result. It might become a problem if the user wants to use solution.exec independently, though.

j178 · 2023-02-04T12:08:25Z

5. This can help make a more streamlined process when adding local test support for more languages in the future, as the maintainer will only need to implement the I/O interface. If we do it by comparing results inside the generated executable, then there would be a lot more work involved with each new language.

Good point, then I suggest we clarify things a bit:

Similar to most OJs, the generated binary reads input from stdin and serializes the result to stdout.
The file input.txt contains test cases, each case is composed of input parameters and expected output. leetgo test retrieves the input parameters from input.txt as stdin and calls the binary to obtain the binary stdout output, which is then compared to the expected output. This part of logic can be reused by every language.
Users can add their own cases to input.txt, where the expected output can be left blank. In this case, the case can be submitted to LC to obtain the expected output.

w43322 · 2023-02-04T12:50:11Z

I agree with this approach. There is one issue though: I think we still need a temporary file to store the serialized output, instead of using stdout directly. Because on LeetCode the stdout is independent from the judging process, and many users use stdout for debugging. So I think we should to respect this behavior and leave stdout to the user.

j178 · 2023-03-08T11:00:26Z

I made some code movements and minor adjustments, hoping they won't conflict with your code :)

I tested the newly generated code with some abnormal code, here are two strage cases I don't know why:

Case 1: no return statement, it will hang forever

click to expand

#include <bits/stdc++.h>
#include "LC_IO.h"
using namespace std;

// @lc code=begin

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    }
};

// @lc code=end

int main() {
	ios_base::sync_with_stdio(false);
	stringstream out_stream;
	vector<int> nums; cin >> nums;
	int target; cin >> target;

	Solution *obj = new Solution();

	auto &&res = obj->twoSum(nums, target);

	out_stream << res;
	cout << "output: " << out_stream.rdbuf();

	delete obj;
	return 0;
}

Case 2: return an empty list, output contains a single ]

click to expand

#include <bits/stdc++.h>
#include "LC_IO.h"
using namespace std;

// @lc code=begin

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        return {};
    }
};

// @lc code=end

int main() {
	ios_base::sync_with_stdio(false);
	stringstream out_stream;
	vector<int> nums; cin >> nums;
	int target; cin >> target;

	Solution *obj = new Solution();

	auto &&res = obj->twoSum(nums, target);

	out_stream << res;
	cout << "output: " << out_stream.rdbuf();

	delete obj;
	return 0;
}

the output:

w43322 · 2023-03-08T11:25:10Z

Case 1: no return statement, it will hang forever

This is to be expected since it's undefined behavior. The compiler should issue a warning. However on my machine it compiles and says runtime error instead of hanging. (x86-64, linux, gcc12)

Case 2: return an empty list, output contains a single ]

This is due to a bug in my I/O library implementation, which I will fix just in a minute. Basically I output a list and overwrite the last character (expected to be ',') with ']'. When the list is empty, it just overwrites the starting bracket.

w43322 · 2023-03-08T11:29:45Z

If it hangs during the compilation phase we probably should add a timer to the compilation process.

j178 · 2023-03-08T11:36:41Z

Interesting, for case 1, It compiles with a warning on my machine (x86-64, Windows 11, gcc 11.2.0):

D:\projects\goland\leetgo\out\cpp\0001.two-sum\solution.cpp: In member function 'std::vector<int> Solution::twoSum(std::vector<int>&, int)':
D:\projects\goland\leetgo\out\cpp\0001.two-sum\solution.cpp:13:5: warning: no return statement in function returning non-void [-Wreturn-type]
   13 |     }
      |     ^

but when it runs, it will hang.

Adding some printf reveals that it hangs on this line:

auto &&res = obj->twoSum(nums, target);

whatever, since it's an UB, I thinks it's ok to ignore it.

add serialization of boolean value TODO: add serialization of char value add scan / print code for boolean / char value in cpp.go

w43322 · 2023-03-08T13:09:05Z

Everything should be functional now. :)

j178 · 2023-03-08T13:23:43Z

Thank you very much. I will play with it for some time before merging it. However, since I have absolutely no knowledge of C++, I may need another C++ pro to review it. I will give you feedback as soon as possible.

w43322 · 2023-03-08T13:29:45Z

Thanks, I might start working on C when I have more free time. It's going to be a lot harder due to the lack of templates and dynamically allocated containers though.

j178 · 2023-03-08T13:39:04Z

Wouldn't it be a bit difficult to use C to solve algorithmic problems? I'm not sure how many people have this need, and I don't know if it's worth the effort to support C. But it's okay, if you want to do it, just do it. I will try my best to provide help.

w43322 · 2023-03-08T13:47:37Z

Yes, I doubt that many people will benefit from this. I used to use C on leetcode when I don't need STL or strings, but later switched to all C++ because it's too much hassle with C as soon as you step into nd arrays or strings. Everything needs to be manually allocated. 🤣

j178 · 2023-03-08T13:58:47Z

haha, I know that pain.

j178 · 2023-03-11T09:03:06Z

merged, thanks @w43322 ! 🎉

j178 marked this pull request as ready for review February 2, 2023 11:05

j178 marked this pull request as draft February 2, 2023 11:09

w43322 force-pushed the cpp_local_test branch from eb63e3b to f8ea073 Compare February 2, 2023 12:48

j178 reviewed Feb 2, 2023

View reviewed changes

.gitignore Outdated Show resolved Hide resolved

j178 reviewed Feb 2, 2023

View reviewed changes

lang/cpp.go Outdated Show resolved Hide resolved

w43322 added a commit to w43322/leetgo that referenced this pull request Feb 3, 2023

feat: implement cpp local test

9b982ea

see j178#90 for more information

w43322 force-pushed the cpp_local_test branch from f8ea073 to 9b982ea Compare February 3, 2023 07:34

w43322 added a commit to w43322/leetgo that referenced this pull request Feb 3, 2023

feat: implement cpp local test

cde2d5c

see j178#90 for more information

w43322 force-pushed the cpp_local_test branch from 9b982ea to cde2d5c Compare February 3, 2023 07:36

w43322 added a commit to w43322/leetgo that referenced this pull request Feb 3, 2023

feat: implement cpp local test

9d39558

see j178#90 for more information

w43322 force-pushed the cpp_local_test branch from cde2d5c to 9d39558 Compare February 3, 2023 08:23

w43322 added a commit to w43322/leetgo that referenced this pull request Feb 3, 2023

feat: implement cpp local test

6a8253a

see j178#90 for more information

w43322 force-pushed the cpp_local_test branch from 9d39558 to 6a8253a Compare February 3, 2023 08:26

w43322 added a commit to w43322/leetgo that referenced this pull request Feb 3, 2023

feat: implement cpp local test

77a108c

see j178#90 for more information

w43322 force-pushed the cpp_local_test branch from 6a8253a to 77a108c Compare February 3, 2023 09:26

w43322 marked this pull request as ready for review February 3, 2023 09:36

w43322 commented Feb 3, 2023

View reviewed changes

lang/cpp.go Outdated Show resolved Hide resolved

w43322 commented Feb 3, 2023

View reviewed changes

lang/cpp/LC_DS.h Outdated Show resolved Hide resolved

w43322 and others added 2 commits February 4, 2023 13:36

feat: implement cpp local test

6d5785c

see j178#90 for more information

rename some variables

cb262a2

j178 force-pushed the cpp_local_test branch from 77a108c to cb262a2 Compare February 4, 2023 05:43

fix lint

92728ef

j178 reviewed Feb 4, 2023

View reviewed changes

lang/cpp.go Outdated Show resolved Hide resolved

j178 reviewed Feb 4, 2023

View reviewed changes

lang/cpp.go Outdated Show resolved Hide resolved

lang/cpp/LC_DS.h Outdated Show resolved Hide resolved

w43322 and others added 6 commits March 8, 2023 14:48

update readme

37b478c

merge CodeFile and TestFile into a single .cpp file

7aa8ef9

place compiled binary under tmp folder

6fc3330

fix readme

d7a9b6d

Merge branch 'master' into cpp_local_test

b0be544

refactor a bit

0a71855

j178 added 2 commits March 8, 2023 19:01

Merge branch 'master' into cpp_local_test

2f7d15d

copy flags

e69a67a

w43322 added 5 commits March 8, 2023 19:54

minor changes

960d679

fix serialization on empty list

0a2afde

add serialization of boolean value TODO: add serialization of char value add scan / print code for boolean / char value in cpp.go

add ser and deser for char

08d9a2b

add scan and print code for bool and char types

c8d8bbd

fix typo

04fcd9e

w43322 force-pushed the cpp_local_test branch from c1c85c2 to 04fcd9e Compare March 8, 2023 12:55

change this value to comply with the behavior of all other I/O functions

eef1c23

w43322 requested a review from j178 March 8, 2023 13:08

Merge branch 'master' into cpp_local_test

d87c836

j178 merged commit 67c90b9 into j178:master Mar 11, 2023

w43322 deleted the cpp_local_test branch March 16, 2023 12:56

Uh oh!

feat: implement cpp local test #90

feat: implement cpp local test #90

Conversation

w43322 commented Feb 2, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Info

How it works

After pick command

After test command with -L parameter

Prerequisites

Completion Status

Example of a generated testing code

Future plans for improvement

Tested problems

Uh oh!

j178 commented Feb 2, 2023

Uh oh!

w43322 commented Feb 2, 2023

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

j178 commented Feb 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

w43322 commented Feb 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

j178 commented Feb 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

w43322 commented Feb 4, 2023

Uh oh!

j178 commented Mar 8, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

w43322 commented Mar 8, 2023

Uh oh!

w43322 commented Mar 8, 2023

Uh oh!

j178 commented Mar 8, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

w43322 commented Mar 8, 2023

Uh oh!

j178 commented Mar 8, 2023

Uh oh!

w43322 commented Mar 8, 2023

Uh oh!

j178 commented Mar 8, 2023

Uh oh!

w43322 commented Mar 8, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

j178 commented Mar 8, 2023

Uh oh!

j178 commented Mar 11, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

w43322 commented Feb 2, 2023 •

edited

Loading

After `pick` command

After `test` command with `-L` parameter

j178 commented Feb 4, 2023 •

edited

Loading

w43322 commented Feb 4, 2023 •

edited

Loading

j178 commented Feb 4, 2023 •

edited

Loading

j178 commented Mar 8, 2023 •

edited

Loading

j178 commented Mar 8, 2023 •

edited

Loading

w43322 commented Mar 8, 2023 •

edited

Loading