Pair programming job

Team mate blog address: https://www.cnblogs.com/minskiter/p/13816780.html
Your blog address: https://www.cnblogs.com/ElizzF/p/13780877.html
Wechat applet + prototype html + game video demonstration Github project address: https://github.com/ElizzF/Picture-Klotski
Backend Github project address: https://github.com/minskiter/klotski.git
Specific division of labor:

full name work
Zhang Zhengfeng Wechat applet development, interaction with the back-end and prototyping
Ye Feiyang Back end micro service development, AI competition and docking, front and back end docking of wechat applet

1. Prototype design

1.1 design description

=
The overall page structure is as follows:
Because it is a game, the structure is not too complex. There is a start interface, a preparation interface (used to preview the target image to be achieved), and a game interface. There are pop-up events in the start interface and the game interface.

First, start the interface, click start game to enter the preparation interface, but log in and authorize before entering, otherwise the user will be refused to start the game.
The purpose of login authorization is to save the history of each player (the shortest steps in history / the fastest time in History). After clicking, a window will pop up to prompt you to start the game.
Exit the game as the name suggests.

Then the preparation interface
The game rules and the target pattern of the game to be spliced are displayed here. Players need to remember this pattern, because in the formal game interface, we will no longer give players the opportunity to watch (test players' memory).

Game interface
It has the following functions:
1) Games. Players click the picture grid near the blank grid, and the picture grid will be exchanged with the blank grid. The number of steps is + 1, and there is timing. The goal is to finally transform the disordered picture lattice into the case that the target pattern in the preparation interface is missing one lattice.
2) Start over. After clicking, the player will return to the start interface. At this time, click again to start the game and will be randomly replaced with other patterns.
3) Reset. After the player clicks, the pattern will return to the way it was at the beginning of the game. The step count is 0, but the timing continues.
4) Automatic. After the player clicks, the pattern will be automatically restored step by step according to the embedded AI, but at the end of the game, the number of steps and time will not be recorded in the history record (because it is not manual)
5) Next step. After clicking, the player will be prompted where to go next (the path is automatically consistent with AI).
6) History. After the player successfully restores the pattern each time, the steps and time consumed will be recorded, and the shortest steps and the fastest time will be displayed to the player to let the player break through himself gif.


1.2 prototype tool used: ink knife

1.3 pairing process

Discuss prototype design pictures

1.4 difficulties encountered and solutions:

Difficulty description
At first, I didn't know how to play Huarong Road.
The prototype tool has just started to use many functions and doesn't know how to use it.
Solution attempt
Find the digital Huarong Road to play as described in the homework, and you will understand how to play.
In terms of prototype tools, I wanted to explore slowly, but in the end, it was oriented to Baidu.
Is it solved
All the above difficulties have been solved.
What did you get
I played a game I hadn't played before
I've seen the prototype of the product before, but I haven't tried it. I've experienced it this time and understand how to make the prototype.

1.5 prototype design and Implementation

Moving algorithm: no = 9 in the code is a blank block.

let index = e.currentTarget.dataset.index;
let numData = this.data.pictureData;
let step = this.data.step;
for (let i in numData) {
    if (index == i && numData[index].no != 9) {
    let x = '';
    // If there is space in the up, down, left and right directions of the current click, the positions will be exchanged
    if (numData[index - 3] && numData[index - 3].no == 9) {  // lower
        x = index - 3;
    } else if (numData[index + 3] && numData[index + 3].no == 9) {  // upper
        x = index + 3;
    } else if (numData[index - 1] && numData[index - 1].no == 9) {  // Left
        // If it is on the far left, it is forbidden to move to the left
        for (let h = 1; h < 3; h++) {
        if (index == 3 * h) return;
        }
        x = index - 1;
    } else if (numData[index + 1] && numData[index + 1].no == 9) {  // right
        // If it is on the far right, it is forbidden to move to the right
        for (let h = 1; h < 3; h++) {
        if (index == 3 * h - 1) return;
        }
        x = index + 1;
    } else {
        return; // No space, no operation
    }

    [numData[i], numData[x]] = [numData[x], numData[i]];
    step++;
    break;
    }
}

2. AI and prototype design and Implementation

2.1 code implementation ideas

Use of network interface

Http1. Provide external services 1 restful web API to support end-to-end calling of applet. Grpc http2 is used internally 0 remote call implementation dotnet core calls python function.

Code organization and internal implementation design (class diagram)

The following is the class diagram of the control layer, service layer and some help API s, which hides the data classes of the Model layer (that is, they are not in the diagram)

The code is based on MVC layered design idea. Since there is no View layer, the layers are mainly Controller layer, Service layer (directly including CRUD operation) and Model

python end

Testapi is responsible for the basic test in the early stage
CharGraph is responsible for image matching and processing. By preloading all images into memory and calculating their eigenvalues, it can achieve fast matching by using eigenvalues

Explain the key of the algorithm and the flow chart of the key implementation part

AI first thinks of search. There are two kinds of search, depth first search and breadth first search, and two heuristic searches that combine evaluation function to predict. Considering the optimal time and number of steps, breadth first search is adopted (the generation of the following steps will not affect the previous state. It is feasible to simply deduce dynamic programming, which is also the worst A * algorithm, so the lowest solution can be obtained). Therefore, breadth first search + recording the state of the minimum number of steps is adopted. The path is to trace back to find the parent node. At the same time, in terms of time, all States are only 9/ About 2 * 9 (about 1.62 million solutions) can be directly cached in memory to speed up the search speed. At the same time, judging whether there is A solution can also get the result in o(1) time.
The picture determines whether python is used to support cross platform deployment.
The approximate flow chart of the algorithm is as follows:

Post code snippets that you think are important / valuable and explain them

Image matching adopts simple scaling and hard matching. Of course, there is still a lot of optimization space for this matching. For example, there is no need to match after matching twice, and fine matching is carried out after hash global coarse screening

def find_image(self,image):
        ''' 
            Match picture

            Attributes:
                image: numpy, numpy Image array

            Returns:
                ans: [{'dest':0,'origin':2},...]  Target location
        '''
        spilt_images = []
        rows = np.split(image,3,axis=0)
        for row in rows:
            cols = np.split(row,3,axis=1)
            for col in cols:
                spilt_images.append({
                    'image':col,
                    'hash':Image.fromarray(col).resize((8,8)).tobytes()
                })
        ans=None
        for originImage in self.origin_images:
            matches = 0
            matches_array = []
            for origin_index,origin_split in enumerate(originImage['images']):
                exists = {} # duplicate removal
                for split_index,split_image in enumerate(spilt_images):
                    if origin_split['hash']==split_image['hash'] and split_index not in exists:
                        matches_array.append({
                            'dest':origin_index,
                            'origin':split_index
                        })
                        exists[split_index]=True
                        matches+=1
                        break
            if matches>=8:
                ans=matches_array
                return ans
        return ans

The algorithm part adopts two-way wide search. See the algorithm flow chart above for details

        /// <summary>
        ///Initialize all possible scenarios
        /// </summary>
        /// <returns></returns>
        public async Task<Dictionary<long, KlotStep>> SearchAllStepAsync()
        {
            return await Task.Run(() =>
            {
                // Initialize initial node state
                // 9 represents space, 0, 1, 2, 3, 4, 5, 6, 7 and 8 represent the original position of the grid
                // There are a total of 9 initial states, and the shortest path of all States is obtained from 9 wide searches
                var initState = new long[]{
                976543210,
                896543210,
                879543210,
                876943210,
                876593210,
                876549210,
                876543910,
                876543290,
                876543219,
            };
                var visited = new Dictionary<long, KlotStep>();
                var searchQuery = new Queue<long>();
                var index = 0;
                foreach (var state in initState)
                {
                    searchQuery.Enqueue(state);
                    visited.Add(state, new KlotStep
                    {
                        step = 0,
                        father = -1,
                        blankPos = 8 - index
                    });
                    ++index;
                };
                while (searchQuery.Count > 0)
                {
                    var state = searchQuery.Dequeue(); // Out of line, get status
                    var lastStep = visited[state];
                    foreach (var dir in direction)
                    {
                        int nextPos = lastStep.blankPos + dir;
                        if (nextPos % 3 == 0 && dir == 1) continue;
                        if (nextPos % 3 == 2 && dir == -1) continue;
                        if (nextPos < 0 || nextPos > 8) continue;
                        var nextState = SwapState(lastStep.blankPos, nextPos, state);
                        if (visited.ContainsKey(nextState)) continue;
                        var currentStep = new KlotStep
                        {
                            father = state,
                            blankPos = nextPos,
                            step = lastStep.step + 1
                        };
                        visited.Add(nextState, currentStep);
                        searchQuery.Enqueue(nextState);
                    }
                }
                return visited;
            });
        }

        /// <summary>
        ///Shortest path solution
        /// </summary>
        ///< param name = "state" > status of Huarong Road < / param >
        ///< param name = "step" > steps < / param >
        ///< param name = "swap" > exchange location < / param >
        /// <returns></returns>
        public async Task<KlotOperations> ShortDistanceAsync(long state, int step, List<int> swap)
        {
            return await Task.Run(() =>
            {
                step = step + 1;
                // Check whether the current status can display the results before the exchange
                var launchStep = _allSolution;
                var operations = new KlotOperations();
                if (launchStep.TryGetValue(state, out var path))
                {
                    if (path.step < step)
                    { // The reference setting is that step is calculated from 1. 1 is the first step. Here, the step of path is calculated from 1
                        while (path.father != -1)
                        {
                            char forw = forward(path.blankPos, state, path.father);
                            operations.operations += forw;
                            state = path.father;
                            path = launchStep[path.father];
                        }
                        return operations;
                    }
                }
                var swapBeforeList = new List<long>(); // Last state before exchange
                var visited = new Dictionary<long, KlotStep>();
                // The visited here also contains the information of recording steps
                var searchQuery = new Queue<long>();
                // The end of the state represents odd and even times, 1 represents odd times, and 0 represents even times
                searchQuery.Enqueue(state * 10);
                visited.Add(state * 10, new KlotStep
                {
                    step = 0,
                    father = -1,
                    blankPos = getPos(state)
                });
                while (searchQuery.Count > 0)
                {
                    // The state here contains parity information
                    state = searchQuery.Dequeue();
                    var lastStep = visited[state];
                    if ((step - 1 - lastStep.step) % 2 == 0)
                    { // If the difference is an even number of times before the forced exchange, you can reach the destination qwq by repeatedly jumping
                        swapBeforeList.Add(state); 
                    }
                    if (lastStep.step == step - 1)
                    {
                        // swapBeforeList.Add(state);
                        continue;
                    } // The limit cannot exceed the number of forced exchange steps
                    foreach (var dir in direction)
                    {
                        var nextPos = lastStep.blankPos + dir;
                        if (nextPos % 3 == 0 && dir == 1) continue;
                        if (nextPos % 3 == 2 && dir == -1) continue;
                        if (nextPos < 0 || nextPos > 8) continue;
                        var nextState = SwapState(lastStep.blankPos, nextPos, state / 10) * 10 + (lastStep.step + 1) % 2;
                        if (visited.ContainsKey(nextState)) continue;
                        var currentStep = new KlotStep
                        {
                            father = state,
                            blankPos = nextPos,
                            step = lastStep.step + 1
                        };
                        visited.Add(nextState, currentStep);
                        searchQuery.Enqueue(nextState);
                    }
                }
                // After all searches are completed, judge whether there is a solution after forced exchange
                int minStep = -1;
                long solutionState = -1;
                var freeSwap = new List<int>();

                foreach (var beforeState in swapBeforeList)
                {
                    var nextState = SwapState(swap[0], swap[1], beforeState / 10);
                    if (launchStep.TryGetValue(nextState, out path))
                    {
                        if (minStep == -1 || path.step < minStep)
                        {
                            minStep = path.step;
                            solutionState = beforeState;
                            freeSwap.Clear();
                        }
                    }
                    else // Judge free exchange
                    {
                        var temp = nextState;
                        for (var i = 0; i < 9; ++i)
                        {
                            for (var j = 0; j < 9; ++j)
                            {
                                if (i != j)
                                {
                                    nextState = SwapState(i, j, temp);
                                    if (launchStep.TryGetValue(nextState, out path))
                                    {
                                        if (minStep == -1 || path.step < minStep)
                                        {
                                            minStep = path.step;
                                            solutionState = beforeState;
                                            freeSwap.Clear();
                                            freeSwap.AddRange(new int[] { i, j });
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
                // if (minStep == -1)
                // {/ / if there is no solution, any lattice can be transformed freely, and there must be at least one solution after exchange
                //     foreach (var beforeState in swapBeforeList)
                //     {
                //         var nextState = SwapState(swap[0], swap[1], beforeState/1000);
                //         var temp = nextState;
                //         for (var i = 0; i < 9; ++i)
                //         {
                //             for (var j = 0; j < 9; ++j)
                //             {
                //                 if (i != j)
                //                 {
                //                     nextState = SwapState(i, j, temp);
                //                     if (launchStep.TryGetValue(nextState, out path))
                //                     {
                //                         if (minStep == -1 || path.step < minStep)
                //                         {
                //                             minStep = path.step;
                //                             solutionState = beforeState;
                //                             freeSwap.Clear();
                //                             freeSwap.AddRange(new int[] { i, j });
                //                         }
                //                     }
                //                 }
                //             }
                //         }
                //     }
                // }
                long swapAfterState = SwapState(swap[0], swap[1], solutionState / 10);
                // The swapAfterState here does not include parity information
                if (freeSwap.Count > 0)
                {
                    swapAfterState = SwapState(freeSwap[0], freeSwap[1], swapAfterState);
                    operations.swap = freeSwap;
                }
                // Generate path solution
                path = visited[solutionState];
                if (path.step != step - 1)
                {
                    // Calculate the number of repeated jumps qwq
                    for (var i = 0; i < step - 1 - path.step; ++i)
                    {
                        if (i % 2 == 0)
                        {
                            // operations.operations = forward(fatherPos, path.father, swapBeforeState) + operations.operations;
                            if (path.blankPos % 3 == 0) operations.operations = 'a' + operations.operations;
                            else operations.operations = 'd' + operations.operations;
                        }
                        else
                        {
                            // operations.operations = forward(path.blankPos, swapBeforeState, path.father) + operations.operations;
                            if (path.blankPos % 3 == 0) operations.operations = 'd' + operations.operations;
                            else operations.operations = 'a' + operations.operations;
                        }
                    }

                }
                // Calculate the number of steps before the jump
                while (path.father != -1)
                {
                    var fatherPos = getPos(path.father / 10);
                    operations.operations = forward(fatherPos, path.father / 10, solutionState / 10) + operations.operations;
                    solutionState = path.father;
                    path = visited[path.father];
                }

                // Calculate the number of steps after exchange
                path = launchStep[swapAfterState];
                // Here is a small bug in the test judgment. An additional step needs to be added to trigger forced exchange
                // if (path.father == -1)
                // {
                //     if (path.blankPos % 3 == 0)
                //     {
                //         operations.operations += 'd';
                //     }
                //     else
                //     {
                //         operations.operations += 'a';
                //     }
                // }
                while (path.father != -1)
                {
                    operations.operations += forward(path.blankPos, swapAfterState, path.father);
                    swapAfterState = path.father;
                    path = launchStep[path.father];
                }
                if (operations.swap.Count > 0)
                {
                    for (var index = 0; index < operations.swap.Count; ++index)
                    {
                        operations.swap[index]++;
                    }
                }
                return operations;
            });

Originally, there was no odd number, but it was found that there were fewer steps in the AI competition test (later, it was speculated that it might be an evaluation error? Now the measured steps have not decreased)

Performance analysis and improvement

In terms of optimization, the first is cache optimization. For two-way wide search, the target 9 nodes are known, and the 162w situation generated by the reverse search from the 9 nodes can be directly buffered into memory for quick call by the program; (when there is no buffer, the average test time is about 1.4s. When the buffer is added, the time can be further reduced to about 0.25s. Of course, 100MB more space is used, which is equivalent to space for time.)
For the API competition, the answer cache is specially optimized to directly and effectively reduce the time after the second brush (due to too much cache in the later stage, the efficiency of using string hash is low, so the second brush at the end does not reduce the time)

Describe your ideas for improvement

python's processing cycle efficiency is relatively poor. Compared with C, c#, java and other similar functions, it may take a constant time. Therefore, C language can be used for translation to speed up the speed;
Image matching uses violence loop, which can be combined with hash global positioning and partial matching pruning optimization.

Show the performance analysis chart and the functions that consume the most in the program


It can be seen from the figure that the most consumed preprocessing search is 1.4s, but the modified part is obtained from the cache after the first loading, which is reduced to 1.54ms


The main consumption of python is to start the service and load the image, but these are preprocessors, which do not affect the subsequent fast matching

Show some unit test codes of the project, explain the test functions and the idea of constructing test data

At present, the test is at the interface level. Because the source code uses dependency injection, the unit test needs to use mock simulation class to realize the unit test. Therefore, this test is only at the API level based on the network.

import requests
import json
import time
import math

success_count = 0
calc_time = 0
max_time = 0

for i in range(1,200):
    res = json.loads(requests.get("http://localhost:5000/api/klotski/solvetest").text)
    if not res['score']['score']:
        print(res)
    else:
        calc_time += res['score']['time']
        max_time = max(res['score']['time'],max_time)
        success_count+=1
    if success_count>0:
        print("\r Current success times:{0} Average time{1}s Maximum time:{2}s".format(success_count,calc_time/success_count,max_time),end='')
    time.sleep(1)

2.2. Post Github's code check-in record and reasonably record the commit information


2.3 code module exceptions or pairing difficulties encountered and Solutions

Difficulty description
1. During debugging, due to the problem of picture sequence, the solution given is in the state of no solution when submitted to the test server, but the error cannot be solved after several manual simulations;
2. During forced exchange, the final status is directly obtained through free exchange. It is False after submission
3. The understanding is not optimal in the competition

Solution attempt
The artificial simulation solution and the help of the test team leader were solved with the help of the leader. The last point is that the wrong understanding of the problem leads to the judgment that there is no solution to all the states that can be reached in the initial state.
Is it solved
yes
What did you get
Only patience + care can modify bug s

2.4. Evaluate your teammates

Ye Feiyang:

  • Places worth learning:
    The boss is very efficient. He completed the prototype design and part of the front-end code in the first week and basically completed the front-end code in the second week. At the same time, I often take the initiative to communicate. I should learn from him and feel that my efficiency has been greatly improved.
  • Areas for improvement:
    Every aspect of the boss is very good, very good qwq.

Zhang Zhengfeng:

  • Places worth learning:
    The boss club has a lot of technologies and develops in all aspects. We should learn from him. In addition, it is very efficient to do things. The interface is realized soon after the request is made.
  • Areas for improvement:
    I think it's already very good. There's nothing to improve.

2.5 PSP and learning progress bar

PSP table

  • Zhang Zhengfeng:
PSP2.1 Personal Software Process Stages Estimated time (minutes) Actual time (minutes)
Planning plan 60 60
· Estimate ·Estimate how long this task will take 60 60
Development development 700 650
· Analysis ·Demand analysis (including learning new technologies) 150 160
· Design Spec ·Generate design documents 60 60
· Design Review ·Design review 20 30
· Coding Standard ·Code specifications (develop appropriate specifications for current development) 20 20
· Design ·Specific design 60 50
· Coding ·Specific coding 360 300
· Code Review ·Code review 10 10
· Test ·Test (self test, modify code, submit modification) 20 20
Reporting report 60 60
· Test Report ·Test report 30 30
· Size Measurement ·Calculation workload 10 10
· Postmortem & Process Improvement Plan ·Summarize afterwards and put forward the process improvement plan 20 20
·Total 820 770
  • Ye Feiyang:
PSP2.1 Personal Software Process Stages Estimated time (minutes) Actual time (minutes)
Planning plan 60 60
· Estimate ·Estimate how long this task will take 60 60
Development development 1500 1455
· Analysis ·Demand analysis (including learning new technologies) 60 360
· Design Spec ·Generate design documents 60 60
· Design Review ·Design review 20 20
· Coding Standard ·Code specifications (develop appropriate specifications for current development) 30 10
· Design ·Specific design 45 45
· Coding ·Specific coding 300 800
· Code Review ·Code review 15 60
· Test ·Test (self test, modify code, submit modification) 30 100
Reporting report 80 70
· Test Report ·Test report 40 30
· Size Measurement ·Calculation workload 10 10
· Postmortem & Process Improvement Plan ·Summarize afterwards and put forward the process improvement plan 30 30
·Total 1640 1585

Learning progress bar

  • Zhang Zhengfeng:
Week N New code (line) Cumulative code (line) Learning time this week (hours) Cumulative learning time (hours) Important growth
1 100 100 8 8 Started the prototype tool ink knife to understand how to carry out prototype design and realize a small number of pages
2 200 300 20 20 Read the wechat applet document and implement the rest of the prototype pages on the wechat applet
3 600 900 45 65 Carry out front-end and back-end interaction on wechat applet, and preliminarily realize playing Huarong Road on wechat applet
4 200 1100 12 77 Add several small functions to the original basis, and make some improvements to the previous code
  • Ye Feiyang:
Week N New code (line) Cumulative code (line) Learning time this week (hours) Cumulative learning time (hours) Important growth
1 0 0 10 10 Learned some characteristics of Huarong Road and understood heuristic search at the same time
2 650 650 12 22 The docking between python and dotnet is realized, and docker deployment integration is carried out at the same time
3 560 1210 10 32 It is preliminarily preset to realize API competition and docking, and continuously optimize the code to improve the automatic construction script
4 200 1410 8 40 Learn other existing algorithms and improve and optimize the previous code

2.6 prototype design and implementation demonstration:

Because the demo video on github runs on wechat developer tools, the "automatic" function will be stuck until the end of an instant, while the demo video below will be directly demonstrated on wechat applet, which will not happen.
Video demonstration of wechat applet designed through prototype

Tags: Software Engineering

Posted by daniellynn2000 on Tue, 10 May 2022 21:43:38 +0300