Posts tagged as “simulation”

花花酱 LeetCode 2069. Walking Robot Simulation II

By zxi on November 13, 2021

A width x height grid is on an XY-plane with the bottom-left cell at (0, 0) and the top-right cell at (width - 1, height - 1). The grid is aligned with the four cardinal directions ("North", "East", "South", and "West"). A robot is initially at cell (0, 0) facing direction "East".

The robot can be instructed to move for a specific number of steps. For each step, it does the following.

Attempts to move forward one cell in the direction it is facing.
If the cell the robot is moving to is out of bounds, the robot instead turns 90 degrees counterclockwise and retries the step.

After the robot finishes moving the number of steps required, it stops and awaits the next instruction.

Implement the Robot class:

Robot(int width, int height) Initializes the width x height grid with the robot at (0, 0) facing "East".
void move(int num) Instructs the robot to move forward num steps.
int[] getPos() Returns the current cell the robot is at, as an array of length 2, [x, y].
String getDir() Returns the current direction of the robot, "North", "East", "South", or "West".

Example 1:

Input
["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
Output
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

Explanation
Robot robot = new Robot(6, 3); // Initialize the grid and the robot at (0, 0) facing East.
robot.move(2);  // It moves two steps East to (2, 0), and faces East.
robot.move(2);  // It moves two steps East to (4, 0), and faces East.
robot.getPos(); // return [4, 0]
robot.getDir(); // return "East"
robot.move(2);  // It moves one step East to (5, 0), and faces East.
                // Moving the next step East would be out of bounds, so it turns and faces North.
                // Then, it moves one step North to (5, 1), and faces North.
robot.move(1);  // It moves one step North to (5, 2), and faces North (not West).
robot.move(4);  // Moving the next step North would be out of bounds, so it turns and faces West.
                // Then, it moves four steps West to (1, 2), and faces West.
robot.getPos(); // return [1, 2]
robot.getDir(); // return "West"

Constraints:

2 <= width, height <= 100
1 <= num <= 10⁵
At most 10⁴ calls in total will be made to move, getPos, and getDir.

Solution: Simulation

Note num >> w + h, when we hit a wall, we will always follow the boundary afterwards. We can do num %= p to reduce steps, where p = ((w – 1) + (h – 1)) * 2

Time complexity: move: O(min(num, w+h))
Space complexity: O(1)

C++

// Author: Huahua

constexpr static int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

const static vector<string> kNames{"East", "North", "West", "South"};

class Robot {

public:

Robot(int width, int height): w_(width), h_(height) {

p_ = ((w_ - 1) + (h_ - 1)) * 2;

}

void move(int num) {

while (num) {

int tx = x_ + dirs[d_][0];

int ty = y_ + dirs[d_][1];

if (tx < 0 || tx >= w_ || ty < 0 || ty >= h_) {

if (num > p_) num %= p_;

if (num) d_ = (d_ + 1) % 4;

continue;

}

x_ = tx;

y_ = ty;

--num;

}

vector<int> getPos() { return {x_, y_}; }

string getDir() { return kNames[d_]; }

private:

int w_;

int h_;

int d_{0}; // 0: E, 1: N, 2: W, 3: S

int x_{0};

int y_{0};

int p_{0};

};

花花酱 LeetCode 2043. Simple Bank System

By zxi on October 17, 2021

You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has n accounts numbered from 1 to n. The initial balance of each account is stored in a 0-indexed integer array balance, with the (i + 1)^th account having an initial balance of balance[i].

Execute all the valid transactions. A transaction is valid if:

The given account number(s) are between 1 and n, and
The amount of money withdrawn or transferred from is less than or equal to the balance of the account.

Implement the Bank class:

Bank(long[] balance) Initializes the object with the 0-indexed integer array balance.
boolean transfer(int account1, int account2, long money) Transfers money dollars from the account numbered account1 to the account numbered account2. Return true if the transaction was successful, false otherwise.
boolean deposit(int account, long money) Deposit money dollars into the account numbered account. Return true if the transaction was successful, false otherwise.
boolean withdraw(int account, long money) Withdraw money dollars from the account numbered account. Return true if the transaction was successful, false otherwise.

Example 1:

Input
["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"]
[[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
Output

[null, true, true, true, false, false]

Explanation Bank bank = new Bank([10, 100, 20, 50, 30]); bank.withdraw(3, 10); // return true, account 3 has a balance of $20, so it is valid to withdraw $10. // Account 3 has $20 – $10 = $10. bank.transfer(5, 1, 20); // return true, account 5 has a balance of $30, so it is valid to transfer $20. // Account 5 has $30 – $20 = $10, and account 1 has $10 + $20 = $30. bank.deposit(5, 20); // return true, it is valid to deposit $20 to account 5. // Account 5 has $10 + $20 = $30. bank.transfer(3, 4, 15); // return false, the current balance of account 3 is $10, // so it is invalid to transfer $15 from it. bank.withdraw(10, 50); // return false, it is invalid because account 10 does not exist.

Constraints:

n == balance.length
1 <= n, account, account1, account2 <= 10⁵
0 <= balance[i], money <= 10¹²
At most 10⁴ calls will be made to each function transfer, deposit, withdraw.

Solution: Simulation

Time complexity: O(1) per operation
Space complexity: O(n) for n accounts

C++

class Bank {

public:

Bank(vector<long long>& balance)

: n_(balance.size()), balance_(balance) {}

bool transfer(int account1, int account2, long long money) {

if (account1 <= 0 || account1 > n_) return false;

if (account2 <= 0 || account2 > n_) return false;

if (balance_[account1 - 1] < money) return false;

balance_[account1 - 1] -= money;

balance_[account2 - 1] += money;

return true;

}

bool deposit(int account, long long money) {

if (account <= 0 || account > n_) return false;

balance_[account - 1] += money;

return true;

}

bool withdraw(int account, long long money) {

if (account <= 0 || account > n_ || balance_[account - 1] < money)

return false;

balance_[account - 1] -= money;

return true;

}

private:

const int n_;

vector<long long> balance_;

};

/**

* Your Bank object will be instantiated and called as such:

* Bank* obj = new Bank(balance);

* bool param_1 = obj->transfer(account1,account2,money);

* bool param_2 = obj->deposit(account,money);

* bool param_3 = obj->withdraw(account,money);

花花酱 LeetCode 1900. The Earliest and Latest Rounds Where Players Compete

By zxi on August 11, 2021

There is a tournament where n players are participating. The players are standing in a single row and are numbered from 1 to n based on their initial standing position (player 1 is the first player in the row, player 2 is the second player in the row, etc.).

The tournament consists of multiple rounds (starting from round number 1). In each round, the i^th player from the front of the row competes against the i^th player from the end of the row, and the winner advances to the next round. When the number of players is odd for the current round, the player in the middle automatically advances to the next round.

For example, if the row consists of players 1, 2, 4, 6, 7
- Player 1 competes against player 7.
- Player 2 competes against player 6.
- Player 4 automatically advances to the next round.

After each round is over, the winners are lined back up in the row based on the original ordering assigned to them initially (ascending order).

The players numbered firstPlayer and secondPlayer are the best in the tournament. They can win against any other player before they compete against each other. If any two other players compete against each other, either of them might win, and thus you may choose the outcome of this round.

Given the integers n, firstPlayer, and secondPlayer, return an integer array containing two values, the earliest possible round number and the latest possible round number in which these two players will compete against each other, respectively.

Example 1:

Input: n = 11, firstPlayer = 2, secondPlayer = 4
Output: [3,4]
Explanation:
One possible scenario which leads to the earliest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 2, 3, 4, 5, 6, 11
Third round: 2, 3, 4
One possible scenario which leads to the latest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 1, 2, 3, 4, 5, 6
Third round: 1, 2, 4
Fourth round: 2, 4

Example 2:

Input: n = 5, firstPlayer = 1, secondPlayer = 5
Output: [1,1]
Explanation: The players numbered 1 and 5 compete in the first round.
There is no way to make them compete in any other round.

Constraints:

2 <= n <= 28
1 <= firstPlayer < secondPlayer <= n

Solution 1: Simulation using recursion

All possible paths,
Time complexity: O(n²*2ⁿ)
Space complexity: O(logn)

dfs(s, i, j, d) := let i battle with j at round d, given s (binary mask of dead players).

C++

// Author: Huahua

class Solution {

public:

vector<int> earliestAndLatest(int n, int a, int b) {

vector<int> ans{INT_MAX, INT_MIN};

function<void(int, int, int, int)> dfs = [&](int s, int i, int j, int d) {

while (i < j && s >> i & 1) ++i;

while (i < j && s >> j & 1) --j;

if (i >= j) {

return dfs(s, 1, n, d + 1);

} else if (i == a && j == b) {

ans[0] = min(ans[0], d);

ans[1] = max(ans[1], d);

} else {

if (i != a && i != b)

dfs(s | (1 << i), i + 1, j - 1, d);

if (j != a && j != b)

dfs(s | (1 << j), i + 1, j - 1, d);

}

};

dfs(0, 1, n, 1);

return ans;

}

};

花花酱 LeetCode 1886. Determine Whether Matrix Can Be Obtained By Rotation

By zxi on August 8, 2021

Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.

Example 1:

Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise to make mat equal target.

Example 2:

Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
Output: false
Explanation: It is impossible to make mat equal to target by rotating mat.

Example 3:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise two times to make mat equal target.

Constraints:

n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] and target[i][j] are either 0 or 1.

Solution: Simulation

Time complexity: O(n²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {

const int n = mat.size();

auto rot = [n](vector<vector<int>>& mat) {

for (int i = 0; i < n; ++i)

for (int j = i; j < n; ++j)

swap(mat[i][j], mat[j][i]);

for (int j = 0; j < n; j++)

for (int i = 0; i < n / 2; ++i)

swap(mat[i][j], mat[n - i - 1][j]);

return mat;

};

for (int i = 0; i < 4; ++i)

if (rot(mat) == target) return true;

return false;

}

};

花花酱 LeetCode 1882. Process Tasks Using Servers

By zxi on August 8, 2021

You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the i^th server, and tasks[j] is the time needed to process the j^th task in seconds.

Tasks are assigned to the servers using a task queue. Initially, all servers are free, and the queue is empty.

At second j, the j^th task is inserted into the queue (starting with the 0^th task being inserted at second 0). As long as there are free servers and the queue is not empty, the task in the front of the queue will be assigned to a free server with the smallest weight, and in case of a tie, it is assigned to a free server with the smallest index.

If there are no free servers and the queue is not empty, we wait until a server becomes free and immediately assign the next task. If multiple servers become free at the same time, then multiple tasks from the queue will be assigned in order of insertion following the weight and index priorities above.

A server that is assigned task j at second t will be free again at second t + tasks[j].

Build an array ans of length m, where ans[j] is the index of the server the j^th task will be assigned to.

Return the array ans.

Example 1:

Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
Output: [2,2,0,2,1,2]
Explanation: Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 2 until second 1.
- At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
- At second 2, task 2 is added and processed using server 0 until second 5.
- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
- At second 4, task 4 is added and processed using server 1 until second 5.
- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.

Example 2:

Input: servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
Output: [1,4,1,4,1,3,2]
Explanation: Events in chronological order go as follows: 
- At second 0, task 0 is added and processed using server 1 until second 2.
- At second 1, task 1 is added and processed using server 4 until second 2.
- At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4. 
- At second 3, task 3 is added and processed using server 4 until second 7.
- At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9. 
- At second 5, task 5 is added and processed using server 3 until second 7.
- At second 6, task 6 is added and processed using server 2 until second 7.

Constraints:

servers.length == n
tasks.length == m
1 <= n, m <= 2 * 10⁵
1 <= servers[i], tasks[j] <= 2 * 10⁵

Solution: Simulation / Priority Queue

Two priority queues, one for free servers, another for releasing events.
One FIFO queue for tasks to schedule.

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {

const int n = servers.size();

const int m = tasks.size();

using P = pair<long, int>;

priority_queue<P, vector<P>, greater<P>> frees, release;

for (int i = 0; i < n; ++i)

frees.emplace(servers[i], i);

vector<int> ans(m);

queue<int> q;

int l = 0;

long t = 0;

int count = 0;

while (count != m) {

// Release servers.

while (!release.empty() && release.top().first <= t) {

auto [rt, i] = release.top(); release.pop();

frees.emplace(servers[i], i);

}

// Enqueue tasks.

while (l < m && l <= t) q.push(l++);

// Schedule tasks.

while (q.size() && frees.size()) {

const int j = q.front(); q.pop();

auto [w, i] = frees.top(); frees.pop();

release.emplace(t + tasks[j], i);

ans[j] = i;

++count;

}

// Advance time.

if (frees.empty() && !release.empty()) {

t = release.top().first;

} else {

++t;

}

return ans;

}

};