Introduction to the

I often use Meituan app to buy movie tickets, so I was curious about its seat recommendation function, so I decided to implement a similar algorithm by myself. The recommended seat selection interface of Meituan App is as follows

5 seats are recommended

This demo is built by vue-CLI. Click the Github address here. After clone, direct NPM start to perform specific operations

Algorithmic thinking process

For this seat recommendation algorithm, I tried to recommend seats for movies of different times, and summarized the following points: (1) The recommendation algorithm starts to search from the middle of the last row of the middle row of the theater as shown in the figure below

(2) Search to the back row first, and then search to the front row from the middle starting position after the search is completed. This is correct in most cases, as shown in the figure below, but occasionally there are differences

(3) After the back-row search is completed, each row will have a result (the result of each row is the group of seats closest to the central axis), and the result with the smallest distance from the central axis of these results will be taken as the final result, rather than the result closer to the screen

This is also true most of the time, some of the time, strangely enough

(4) If only side by side and consecutive seats are considered, there must be a division in a row or in the middle of a row, such as the aisle, which is understandable. After all, sitting in a row will definitely make the movie viewing experience much better

Theater seat data structure

To be sure, a two-dimensional array seatArray is used to represent the seats in the cinema. It is noted that the distribution of seats in the cinema is irregular. Therefore, a seatRow and seatCol should be determined to determine the array size of the seats in the cinema, respectively representing the number of rows and columns. Here are the specific values and what they stand for

-1 Non-seat 0 Optional seat (white) 1 Selected seat (green) 2 Purchased seat (red)Copy the code

In Mounted, initialize all seats to 0(optional seat)

// initSeatArray:function() {letseatArray = Array(this.seatRow).fill(0).map(()=>Array(this.seatCol).fill(0)); this.seatArray = seatArray; SeatSize = this. SeatSize = this.$refs.innerSeatWrapper
                        ? parseInt(parseInt(window.getComputedStyle(this.$refs.innerSeatWrapper).width,10) / this.seatCol,10) :0; This.initnonseatplace (); }, // initialize initNonSeatPlace where it is not a seat:function() {for(leti=0; i<9; i++){ this.seatArray[i][0]=-1; }for(leti=0; i<8; i++){ this.seatArray[i][this.seatArray[0].length-1]=-1; this.seatArray[i][this.seatArray[0].length-2]=-1; }for(leti=0; i<9; i++){ this.seatArray[i][this.seatArray[0].length-3]=-1; }for(leti=0; i<this.seatArray[0].length; i++){ this.seatArray[2][i]=-1; }}Copy the code

After initialization, a double loop is used to build the HTML structure, and 2 V-for nested loops to the entire structure, as shown in the following code

 <div class="inner-seat-wrapper" ref="innerSeatWrapper" >
      <div v-for="row in seatRow">
        <! -- seatArray is empty -- seatArray is empty -->
        <div v-for="col in seatCol"
             v-if="seatArray.length>0"
             class="seat"
             :style="{width:seatSize+'px',height:seatSize+'px'}">
          <div class="inner-seat"
               @click="handleChooseSeat(row-1,col-1)"
               v-if="seatArray[row-1][col-1]! = = 1"
               :class="seatArray[row-1][col-1]===2? 'bought-seat':(seatArray[row-1][col-1]===1? 'selected-seat':'unselected-seat')">
          </div>
        </div>
      </div>
</div>
Copy the code

The inner seat div above is the specific seat div. V-if indicates that it will not be rendered if it is -1, i.e. aisle, etc. Then :class statement controls the value of the class corresponding to the seat state, a nested trisomate operator controls, HandleChooseSeat (ROW-1,col-1) switches state for each seat binding click event

// Handle seat selection logic handleChooseSeat:function(row,col){
  	let seatValue = this.seatArray[row][col];
  	letnewArray = this.seatArray; // If you have purchased a seat, return directlyif(seatValue===2) return// If the seat is selected, click to change it to unselectedif(seatValue === 1){
          newArray[row][col]=0
        }else if(seatValue === 0){newArray[row][col]=1} SeatArray = newarray.slice (); this.seatArray = newarray.slice (); },Copy the code

Note here that vUE must first cache the two-dimensional array in data. After modification, the two-dimensional array will be reassigned. Otherwise, the modification will not take effect, because VUE cannot detect the changes in the array.

The specific code of the recommended seat

First bind the event smartChoose to the button for each recommended seat

SmartChoose: smartChoose: smartChoose: smartChoose:function(num){// Find the row behind the center of the theater seatletRowStart = parseInt ((enclosing seatRow - 1) / 2, 10) + 1; // Search from the middle to the backlet backResult = this.searchSeatByDirection(rowStart,this.seatRow-1,num);
      	if(backResult.length>0){
      	    this.chooseSeat(backResult);
            return} // Search from the middle row forwardletForwardResult = this. SearchSeatByDirection (rowStart - 1, 0, num);if(forwardResult.length>0) {
            this.chooseSeat(forwardResult);
            return} // Alert (no valid location optional)'No legal location to choose from! ')},Copy the code

The first step is finding level vertical after the middle of a row of the cinema, then calls the enclosing searchSeatByDirection in the direction of the search, the back row to search in the middle, and the first row on row from the center search again. ChooseSeat is used to change the state of the seat if the search results are found in either direction, return directly, otherwise the user is informed that there is no valid location

The key is the searchSeatByDirection implementation, the code is as follows

// A function that searches in a certain direction, taking the start row, the end row, and the recommended number of seats
  searchSeatByDirection: function(fromRow,toRow,num){
    / * * * recommended seat rules (1) the initial state from the seat after half of the number of rows in a row around the middle of the began to search, respectively take intermediate nearest, if meet the conditions, * to record the results from the seat of the central axis distance, search after the completion of the back to take the smallest distance that the results as the final result, give the back to search, * * * * * * * * * * * * * * * * * * * * * *

    * {* result:Array([x,y]) * offset:Number *} */
    let currentDirectionSearchResult = [];
    // Determine the size of the row relationship, from small to large traversal
    letlargeRow = fromRow>toRow? fromRow:toRow, smallRow = fromRow>toRow? toRow:fromRow;// Search line by line
    for(leti=smallRow; i<=largeRow; i++){// Search each row to find the group of seats closest to the axis of the row
      let tempRowResult = [],
          minDistanceToMidLine=Infinity;
      for(let j=0; j<=this.seatCol - num; j++){// If there is a valid location
        if(this.checkRowSeatContinusAndEmpty(i,j,j+num- 1)) {// Calculate the distance between the group position and the central axis: the distance between the middle position of the group position and the central axis
          let resultMidPos = parseInt((j+num/2),10);
          let distance = Math.abs(parseInt(this.seatCol/2) - resultMidPos);
          // Update if the distance is short
          if(distance<minDistanceToMidLine){
            minDistanceToMidLine = distance;
            // The final result of the row
            tempRowResult = this.generateRowResult(i,j,j+num- 1)}}}// Save the final result of the row
      currentDirectionSearchResult.push({
        result:tempRowResult,
        offset:minDistanceToMidLine
      })
    }

    // Find the shortest distance from the central axis
    // Note that the logic needs to distinguish between front and back rows. For back rows, it is front and back. For front rows, it is back and front
    let isBackDir = fromRow < toRow;
    let finalReuslt = [],minDistanceToMid = Infinity;
    if(isBackDir){
    	// Back row, front to back
      currentDirectionSearchResult.forEach((item) = >{
        if(item.offset < minDistanceToMid){ finalReuslt = item.result; minDistanceToMid = item.offset; }}); }else{
    	// Look from back to front
      currentDirectionSearchResult.reverse().forEach((item) = >{
        if(item.offset < minDistanceToMid){ finalReuslt = item.result; minDistanceToMid = item.offset; }})}// Return the result directly
    return finalReuslt
  },
Copy the code

The code is a bit long, but the logic is not difficult, is that the implementation of the previous rules, for each row of search, there may be more than one reasonable seat results

Each line of the best results will be stored in currentDirectionSearchResult array

Then the back direction of all the row after the traversal, get the best results by each line array currentDirectionSearchResult, central axis to traverse the array according to the rules to take distance recently one as the final return results

This algorithm can be optimized to go straight from the middle to the two sides, and return if you find it, but it’s a little tricky to write, but it’s definitely efficient. It is important to note the front case to currentDirectionSearchResult. Reverse reverse array (), because for the front part is give preference to the latter part of the front of the (who doesn’t want to sit in the first row!) The opposite of the back row

The last

This algorithm has a few problems, as shown below