Problem Statement
Minesweeper strings are strings of length N with the following properties:
- Each character is either a '*' (representing a mine) or a digit: '0', '1', or '2'.
- The value of each digit must be equal to the number of mines adjacent to it.
For example, for N = 7:
- "0000000" is a valid minesweeper string with no mines.
- "*******" is a valid minesweeper string with seven mines.
- "0001*2*" is a valid minesweeper string with two mines.
- "0001000" is not a valid minesweeper string because the number of mines adjacent to the '1' in the middle is not 1.
- "**0001*" is not a valid minesweeper string because the number of mines adjacent to the leftmost '0' is not 0.
- "2*1*02*" is not a valid minesweeper string: all digits are wrong.
Suppose we order all valid minesweeper strings lexicographically (i.e., using the ASCII values of the characters that form them) and then number the sorted order starting from 0.
Given the string length N and the non-negative integer X, find the minesweeper string number X in the order described in the previous paragraph. Return that string, or an empty string if no string has the number X.
Definition
- Class:
- MinesweeperStrings
- Method:
- generate
- Parameters:
- int, long
- Returns:
- String
- Method signature:
- String generate(int N, long X)
- (be sure your method is public)
Notes
- The ASCII values of characters '*', '0', '1', and '2' are 42, 48, 49, and 50, respectively.
- In all common programming languages, the built-in string comparison operator produces the desired lexicographic order.
Constraints
- N will be between 1 and 60, inclusive.
- X will be between 0 and 10^18, inclusive.
Examples
1
0
Returns: "*"
There are only two valid minesweeper strings for N=1. The lexicographically smaller one (i.e., string number 0) is "*".
1
1
Returns: "0"
There are only two valid minesweeper strings for N=1. The lexicographically bigger one (i.e., string number 1) is "0".
1
47
Returns: ""
There are only two valid minesweeper strings for N=1. There is no string number 47, so the correct return value is an empty string.
7
71
Returns: "0001*2*"
Our old friend, the valid minesweeper string "0001*2*", has number 71 among all strings of length 7.
14
9876543210987654
Returns: ""
47
47
Returns: "*****************************************11*2*1"
3
0
Returns: "***"
3
1
Returns: "**1"
3
2
Returns: "*10"
3
3
Returns: "*2*"
3
4
Returns: "000"
3
5
Returns: "01*"
3
6
Returns: "1**"
3
7
Returns: "1*1"
3
8
Returns: ""
3
124125
Returns: ""
3
1000000000000000000
Returns: ""
60
1000000000000000000
Returns: "1**2*2******11*11*11**2***2*11***2*11*101*******************"
60
100000000000000000
Returns: "***11*1001*11****11**2*2*****11*2**2****11******************"
60
10000000000000000
Returns: "******1001*2*****2**2*2***101*11*2*2*100001*****************"
60
100000000000000
Returns: "*************11*11**2*2***2****100001*2*11***100000000000000"
60
100000000000
Returns: "***********************11*2**101*****2*11*11*2**100000000000"
60
100000000
Returns: "*********************************11*2*2**11*2*10001*********"
60
100000
Returns: "*******************************************2*****2**11******"
60
100
Returns: "*****************************************************2***100"
60
0
Returns: "************************************************************"
47
3295230580238502
Returns: ""
47
3205230582085855
Returns: ""
47
2345
Returns: "***********************************101***11***1"
47
240359305305380658
Returns: ""
1
3
Returns: ""
59
1000000000
Returns: "*****************************2*11*2***2**11*101**1000000000"