当前位置:网站首页>Programming art of programmer chapter 38: evolution and optimization of hero's online programming problem judging and testing system

Programming art of programmer chapter 38: evolution and optimization of hero's online programming problem judging and testing system

2020-12-07 13:01:34 osc_ 5h77wdgp

  Chapter 38 :Hero Online programming judgment questions 、 The evolution and optimization of the question system

Programming art githubhttps://github.com/julycoding/The-Art-Of-Programming-By-July, I invite you to create !


Preface

    I used to go out and play , I often go to the Internet bar , Go to the Internet bar and do nothing , Take a look at the blog , Change your blog , But if you want to change a piece of code on your blog , But I found that there is no compiler in the Internet bar , But it takes a lot of time to install it , So every time I want to write code in the Internet bar, I will stop .

    at that time , I thought , If you open your browser one day , You can type code directly on the web page , That would be great , Whenever and wherever possible , No compiler restrictions . ' , This year, 3 At the end of the month CSDN To do such an online programming website Hero 了 :http://hero.csdn.net/, Overall responsibility for its products and operations as project leader 、 Including questions .

    Why write this article ? This article does not talk about Hero How to achieve , Not this year 3 Month so far , its PV How many times has it gone up , Don't talk about the specific solution of each problem 、 Ideas 、 What's the code like ( You may write in the future ), Let alone how its interface is optimized step by step , Just talk about its decision system 、 How does the problem solving system evolve and optimize step by step , That is, what kind of mechanism is behind it ( It is used to judge whether the program submitted by thousands of users every day is correct or not ), And how to make every user can come Hero The one who came up with the question .

    By the way, ask a lot of friends “Hero How does the backstage judge the question , Why is my program submitted in error ?” A concentrated answer to , Open up the mechanism of judging questions , For each Hero Our customers are fair and just . The end of the year is coming , It is also part of the review and summary of my work in the past year .

    OK, What's the problem with this article , You are welcome to correct at any time , Yes Hero Any improvement or suggestion , Feel free to give me feedback ,thanks.


Chapter 38 、Hero Online programming judgment questions 、 The evolution and optimization of the question system

One 、 The first artificial eye test

    Hero The implementation from the beginning to the end has not borrowed any open source tools , So every step of its exploration seems to progress slowly 、 Push hard . In this year 3 Before month , stay Hero There are not many people playing , So when I first came to the company , It is completely artificial to see whether the program idea of each user is correct , I have to copy the user's code and paste it into the compiler for compilation , See if the result is normal . That is to say, if I work out a question : seek N A full arrangement of characters . There's only one thing the system does backstage , Just save the user's code .

    But after opening many users' answers , Only then discovered that he did not realize the entire arrangement , He just wrote a “hello world”:

public class HelloWorld 
{ 
	public static void main(String args[]) 
	{
		System.out.println("Hello World");
	} 
} 

    That is, whether the user's program is correct , I have to judge by hand . This kind of artificial judgment lasted for a whole month , Later I found out Hero More and more people are playing , Every day from just a few copies of code to hundreds of copies of code , I immediately thought it was wrong .

    Yes , We have to let the machine automatically judge questions .


Two 、 Write test code to let the machine automatically judge the problem

2.1、 A series of simple rudeness if else Judge

    How to make the machine realize automatic problem determination ? In fact, the principle is quite simple , You can write a test code when you write the question , Then use this test code which contains a lot of test data to verify whether the user's program is correct .

    For example, there is a question like this :

  The length of the longest valid bracket : Given contains only parenthesis characters '(' and ')'' String , Please find the length of the longest valid parenthesis .

Here are a few examples :

  1. For example, for "( ()", The longest valid substring in parentheses is "()" , Valid number of double brackets 1 individual , So its length is 2. 
  2. Another example is string ") () () )", The longest valid substring in parentheses is "() ()", Valid number of double brackets 2 individual , So its length is 4. 
  3. Another example is for "( () () )", Its length is 6.     

    In other words , It's a valid double bracket "()" Double the number .

Given the function prototype int longestValidParentheses(string s),

#include <string>
#include <iostream>
using namespace std;

class Solution
{
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       //....
        return length;
    }
};













//start Tips : Automatic marking start unique identification , Do not delete or add .
int main()
{    
    //write your code


    return 0;
}
//end // Tips : The unique mark of the end of automatic marking , Do not delete or add .        


Please complete this function , Realize the function required by the title .”

    such , I may write such a test code to verify whether each user's program is correct , as follows :

//start  Tips : Automatic marking start unique identification , Do not delete or add .
int main()
{    
    char* la ="";
    char* b =    "(";    
    char* c =    ")"    ;
    char* d =    ")(";    

    char* e =    "()";    
    char* f =     "(()";    
    char* g =    "())";    

    char* h    = "()()";    
    char* i    = "()(())";    
    char* j =    "(()()";    
    char* k =    "()(()";    
    char* l =    "(()()";    
    char* m =    "(()())";    
    char* n =    "((()))())";    
    char* o =    ")()())()()(";    
    char* p =    ")(((((()())()()))()(()))(";

    Solution a;
    if (a.longestValidParentheses(la) == 0 && a.longestValidParentheses(b) == 0 && a.longestValidParentheses(c) == 0
        && a.longestValidParentheses(d) == 0 && a.longestValidParentheses(e) == 2 && a.longestValidParentheses(f) == 2
        && a.longestValidParentheses(g) == 2 && a.longestValidParentheses(h) == 4 && a.longestValidParentheses(i) == 6
        && a.longestValidParentheses(j) == 4 && a.longestValidParentheses(k) == 2 && a.longestValidParentheses(l) == 4
        && a.longestValidParentheses(m) == 6 && a.longestValidParentheses(n) == 8 && a.longestValidParentheses(o) == 4
        && a.longestValidParentheses(p) == 22
        )
    {
        cout<<"Y!"<<endl;
    }
    else
    {
        cout<<"N!"<<endl;
    }

    return 0;
}
//end // Tips : The unique mark of the end of automatic marking , Do not delete or add .    
    Then use the above test code that contains the test data , In place of the user main Function to judge :
//start  Tips : Automatic marking start unique identification , Do not delete or add .
int main()
{    
    //write your code
    return 0;
}
//end // Tips : The unique mark of the end of automatic marking , Do not delete or add .  

    such , Just write the test code when you come out , The machine will be able to automatically judge questions . But soon , We found that the above test code can be optimized in two ways :

  1. One for Cycle instead of a series of if else;
  2. Don't let the machine run through all the test data , But as long as a set of test data fails , The program exits immediately , That is, as long as the machine finds the test data that the first group of users fails .

2.2、for Loop instead of if else
    As mentioned in the previous section , If the test data is small , It's good to say , But there's a lot of data , Then you have to write a long, long if else, For the coding People seem to be very amateur . therefore , Let's look at the following question :

  Legal string use n Different characters ( Number 1 - n), Make a string , There are the following 2 Point requirements :
    1、 For No i The characters of , If 2 * i > n, Then the character can be used as the last character , But if it's not the last character , Then the character can be followed by any character ;
    2、 For No i The characters of , If 2 * i <= n, Then the character cannot be the last character , And the number of the next character following the character must be >= 2 * i.


How long is it M And strings that match the criteria .

for example :N = 2,M = 3. be abb, bab, bbb Is a string that meets the criteria , The rest are strings that don't match the criteria .

Input :n,m  (2<=n,m<=1000000000);

Output : The number of strings satisfying the condition , Because of the big data , Output the number Mod 10^9 + 7 Result .

Function header

int validstring(int n,int m) {}

    We can write the following test code :

//start  Tips : Automatic marking start unique identification , Do not delete or add .
int main() {
	const int n[] = {2,2,66,123,31542/* Because the subject is still there Hero on-line , So only a part of the test data */};
	const int m[] = {2,1000000000,634,10000,55555535 /* Only a part of the test data is disclosed */};
	const int answer[] = {2,999999994,171104439,8789556,605498333 /* Only a part of the test data is disclosed */};
	int i;
	for (i = 0; i < 4/* actually i More than 4 Group */; ++i) {
		if (validstring(n[i],m[i]) != answer[i]) {
			break;
		}
	}
	if (i >= 4) {
		puts("Y!");
	}
	else {
		printf("N!");
	}
	return 0;
}
//end // Tips : The unique mark of the end of automatic marking , Do not delete or add .    
    such , The above test code will allow the machine to automatically determine whether each program submitted by the user is correct . But as you do now, you will also realize , The system light tells me whether the program is right or wrong , I don't think it's enough , That is, if the user's program is wrong , The system has to tell him what's wrong ? It's because of overtime , Or the logic of the program itself is wrong .

    therefore , The system quickly fed back the first set of data that the user had made a mistake , How to achieve it ? It's simple , Just add the wrong part of the program to the wrong data :

//start  Tips : Automatic marking start unique identification , Do not delete or add .
int main() {
	const int n[] = {2,2,66,123,31542/* Because the subject is still there Hero on-line , So only a part of the test data */};
	const int m[] = {2,1000000000,634,10000,55555535 /* Only a part of the test data is disclosed */};
	const int answer[] = {2,999999994,171104439,8789556,605498333 /* Only a part of the test data is disclosed */};
	int i;
	for (i = 0; i < 4/* actually i More than 4 Group */; ++i) {
		if (validstring(n[i],m[i]) != answer[i]) {
			break;
		}
	}
	if (i >= 4) {
		puts("Y!");
	}
	else {
		printf("N!\n%d %d\n",n[i],m[i]);
	}
	return 0;
}
//end // Tips : The unique mark of the end of automatic marking , Do not delete or add .

    Soon , I found out again , For the question itself , It is not easy to construct its complete and comprehensive test data , Now I have to write a test code for each topic , And every language C、C++、Java、C# Write it all down , Do it once and realize it's not right . But such a process of writing painful test code for each problem and each programming language lasted for half a year , Until this year 10 month .

    Can that simplify the work of writing this test code , Make the system itself more intelligent ? Because since the key is the construction of test data , So with the test data , Whether to just fill in the test data , Instead of writing test code ? Please see No 3 Section .


3、 ... and 、 Continuous improvement and optimization of the problem solving system itself

3.1、 The long process of writing test code

    As mentioned above , Until this year 10 month ,hero The back-end question determination mechanism has always been , Write a tape for each question in each language main Function test code , Use this test code to replace the main function . As shown in the figure below : Dexter start end Code Replace the start end Code :


    Of course , In the process of writing test code , With the help of his friend Cao Peng , If it wasn't for his support , I can't hold on either 6 Months ,thanks. But even with his help , The long process of writing test code is still very painful .

    Besides , Push yourself to simplify the problem-solving process , There's another important reason why you don't want to write test code : That is because I have to write a test code for every programming language of every problem , This leads to the abnormal efficiency of the problem , This is for the whole Hero The system is very disadvantageous .

    therefore , Team decision , Open the interface of the question , So that everyone can come Hero Write a question , This function is : Social problem solving . stay Hero The right sidebar of the home page , as follows :

    This is the time , Here's the problem , Let yourself write the test code , It's not easy , But at least with Cao Peng's help, we can deal with , But how can we let users write test code for every language of every problem ? But all of this is just my own subjective judgment , There is not much practical evidence to support my judgment , So the team decided , For the time being, let's talk about socialization first .

3.2、 Just fill in the test data , Don't write test code

3.2.1、 Fill in the test data one by one

    The worst result I'm most worried about is that .10 Socialized online at the beginning of the month , until 10 End of month , Although there are some enthusiastic friends without any reward Hero There's a problem , But almost no one wants to write test code .

    Although we have taken many detours , The whole process of progress is very slow , But at least it's moving on .

    Thanks to the whole team , stay 11 Month of the month , Finally, there is no need to write test code again , You just need to fill in the test data one by one .


3.2.2、 Fill in the test data in batches when writing questions

    If there is less than one subject 10 Group test data , So it's no problem to fill in the test data one by one when the questions are asked . But the problem is , There is no test data less than 10 Group situation , More words, hundreds of groups , Even thousands of groups , therefore , We soon found that it was necessary to support batch filling of test data , So this year 12 End of month , The question system has been transformed as shown in the figure below :


3.3.3、 Subsequent improvements 、 Optimize

    Of course , Until now, , There is still a lot to be improved in the question system 、 Where to optimize , If you need to support arrays , Multi line input corresponding to multi line output is supported , Until the end is complete OJ Pattern , Please update these later in this article . The team has a lot to do , But we've been trying to , Driven by the whole team ,Hero And I've been moving on , Never back down .

    

Related links

  1. Hero Online programming website :http://hero.csdn.net/;
  2. this paper 2.1 Section question online challenge address :http://hero.csdn.net/Question/Details?ID=54&ExamID=52;
  3. this paper 2.2 Section problem online programming address :http://hero.csdn.net/Question/Details?ID=74&ExamID=72;


Postscript

    Thank you for your attention to this programming art series , Welcome to continue to pay attention to or contribute to the art of programming githubhttps://github.com/julycoding/The-Art-Of-Programming-by-July, I also hope that you will continue to support Hero. What's the problem , Feel free to give me feedback , The end of this paper .

    July、 December 28, 2013 .



版权声明
本文为[osc_ 5h77wdgp]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/202012071250031092.html