Shape Number 形状的数字问题

Question

Problem Description
In computer vision, a chain code is a sequence of numbers representing directions when following the contour of an object. For example, the following figure shows the contour represented by the chain code 22234446466001207560 (starting at the upper-left corner).

Two chain codes may represent the same shape if the shape has been rotated, or if a different starting point is chosen for the contour. To normalize the code for rotation, we can compute the first difference of the chain code instead. The first difference is obtained by counting the number of direction changes in counterclockwise direction between consecutive elements in the chain code (the last element is consecutive with the first one). In the above code, the first difference is

00110026202011676122
Finally, to normalize for the starting point, we consider all cyclic rotations of the first difference and choose among them the lexicographically smallest such code. The resulting code is called the shape number.
00110026202011676122
01100262020116761220
11002620201167612200
...
20011002620201167612
In this case, 00110026202011676122 is the shape number of the shape above.

Input
The input consists of a number of cases. The input of each case is given in one line, consisting of a chain code of a shape. The length of the chain code is at most 300,000, and all digits in the code are between 0 and 7 inclusive. The contour may intersect itself and needs not trace back to the starting point.

Output
For each case, print the resulting shape number after the normalizations discussed above are performed.

Sample Input
22234446466001207560
12075602223444646600

Sample Output
00110026202011676122
00110026202011676122

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# Import necessary packages
library(readline)

# Define function to convert chain code to shape number
shape_number <- function(chain_code) {
  # Normalize the chain code
  normalized_chain_code <- c(0, -chain_code[1], chain_code[-1] - chain_code[1])
  
  # Calculate the first difference of the normalized chain code
  first_difference <- c(normalized_chain_code[1], 
                       normalized_chain_code[2] - normalized_chain_code[1],
                       normalized_chain_code[3] - normalized_chain_code[2],
                       normalized_chain_code[4] - normalized_chain_code[3],
                       normalized_chain_code[5] - normalized_chain_code[4],
                       normalized_chain_code[6] - normalized_chain_code[5],
                       normalized_chain_code[7] - normalized_chain_code[6],
                       normalized_chain_code[8] - normalized_chain_code[7])
  
  # Find the shape number
  shape_number <- first_difference[c("00", "11", "22", "33", "44", "55", "66", "77")]
  
  return(shape_number)
}

# Read data from user input
input_data <- readline(prompt = "\nEnter chain code: ")

# Convert input data to character vector
input_data <- as.character(input_data)

# Call shape_number function on input data
shape_number_result <- shape_number(input_data)

# Print the result
print(shape_number_result)

This R code defines a function shape_number that takes a chain code as input and returns its corresponding shape number after normalization. It first normalizes the chain code by subtracting the first element and adding it to the second element, then calculates the first difference of the normalized chain code. Finally, it finds the shape number by comparing the first difference against predefined values. The main part of the code reads a chain code from the user, converts it to a character vector, calls the shape_number function on it, and prints the result.