# Simulate walking with collisions

In this challenge, the task is to write a program or function which simulates a number of people walking. Input will be some representation of the people's positions on a 2d grid, and one of four directions (or none) for each.

The movement follows a few rules:

• No person can walk into a space occupied by a person who is not moving
• No two or more people can walk into the same space (none of them move)
• No two adjacent people can swap positions

If a person would not collide with another, they will move one space in the specified direction. You can choose how directions are represented. All coordinates are pairs of integers. No two people will start in the same position.

### Test cases:

Inputs are represented as pairs of coordinates ([x, y]), followed by a direction. Outputs are only the resulting coordinates. All of these have four people for simplicity, but inputs can consist of any (non-zero) number of people.

Input 1:

[[[0, 0], +y], [[-1, 0], +x], [[-2, 0], +x], [[1, 0], -x]]


Output 1:

[[0, 1], [-1, 0], [-2, 0], [1, 0]]


Input 2:

[[[0, 0], none], [[0, 1], +y], [[0, 2], +y], [[0, 3], +x]]


Output 2:

[[0, 0], [0, 2], [0, 3], [1, 3]]


Input 3:

[[[0, -1], +y], [[0, -2], +y], [[0, -3], +y], [[1, -2], -x]]


Output 3:

[[0, 0], [0, -1], [0, -3], [1, -2]]


Input 4:

[[[0, 0] +x], [[1, 0], +y], [[1, 1], -x], [[0, 1], -y], [[2, 0], +x]]


Output 4:

[[1, 0], [1, 1], [0, 1], [0, 0], [3, 0]]


Input 5:

[[[0, 0] +x], [[1, 0], +y], [[1, 1], -x], [[0, 1], -y], [[2, 0], -x]]


Output 5:

[[0, 0], [1, 0], [1, 1], [0, 1], [2, 0]]


Input 6:

[[[0, 1], -y], [[1, 1], -x], [[1, 0], +y], [[0, 0] +x], [[2, 0], +x]]


Output 6:

[[0, 0], [0, 1], [1, 1], [1, 0], [3, 0]]


This is , shortest answer in bytes per language wins!

• May we take a direction as a vector [dx, dy]? Mar 17, 2021 at 23:10
• @Arnauld Sure, go ahead Mar 17, 2021 at 23:15
• I'm not totally clear on the movement rules. Will a cycle of 4 or more people all wanting to go into the next person's space all move at the same time?
– xnor
Mar 17, 2021 at 23:33
• @xnor Yes (filler) Mar 17, 2021 at 23:36
• Suggest testcases: [[[0, 0] +x], [[1, 0], +y], [[1, 1], -x], [[0, 1], -y], [[2, 0], +x]] -> [[1, 0], [1, 1], [0, 1], [0, 0], [3, 0]]; [[[0, 0] +x], [[1, 0], +y], [[1, 1], -x], [[0, 1], -y], [[2, 0], -x]] -> [[0, 0], [1, 0], [1, 1], [0, 1], [2, 0]]; [[[0, 1], -y], [[1, 1], -x], [[1, 0], +y], [[0, 0] +x], [[2, 0], +x]] -> [[0, 0], [0, 1], [1, 1], [1, 0], [3, 0]]
– tsh
Mar 18, 2021 at 2:20

# J, 60 58 50 47 bytes

[:+/(*1,:1-(1<1#.+/=/+/)+{.(~:*[=i.{_,~])+/)^:_


Try it online!

Takes input as a matrix of complex numbers -- starting positions in the 1st row, steps to walk in the 2nd row.

Passes all test cases including those suggested by tsh and the cycle of 4 suggested by xnor.

## tldr how

We iteratively adjust the steps to be 0 for impossible moves (same destination (1<1#.+/=/+/) or + swaps {.(~:*[=i.{_,~])+/) until they reach a fixed point ^:_. Iteration is needed because some steps only become illegal after a walker changes from someone who will move to someone standing still. There's a chain reaction.

After that iteration, impossible steps will have been converted to 0, and legal steps will remain what they were.

Once that's done, we just add those steps to the starting positions [:+/.

# Python 2, 127112 104 bytes

def f(l):r=map(sum,l);exec"r=[[p,x][r.count(p)>1or[x+d,-d]in l]for p,[x,d]in zip(r,l)];"*len(l);return r


Try it online!

Takes input as a list of pairs of complex numbers, outputs a list of complex numbers. Initially has everyone walk unless they would swap and then repeatedly sends back anyone who collided until there are no collisions left.

-8 bytes thanks to xnor!

• if/else is overkill here: 104
– xnor
Mar 20, 2021 at 10:45

# Charcoal, 48 bytes

Ｗφ«≔⁰φＦθ¿∧§κ¹∨№θ⟦Σκ±§κ¹⟧⊖№ＥθΣλΣκ«≔⊟κφ⊞κ⁰»»Ｅθ⭆¹Σι


Try it online! Link is to verbose version of code. Takes input as an array of pairs of complex numbers and outputs a list of complex numbers. Explanation:

Ｗφ«


Repeat while a flag value is non-zero.

≔⁰φ


Zero out the flag value.

Ｆθ


Loop over the people.

¿∧§κ¹


If they want to move, and...

∨№θ⟦Σκ±§κ¹⟧


... they would be swapping with the person at their destination, or...

⊖№ＥθΣλΣκ«


... another person would end up at the same destination, then:

≔⊟κφ


Set the flag value by removing that person's desired movement, and...

⊞κ⁰


Replace their movement with standing still.

»»Ｅθ⭆¹Σι


Print the final positions. (I've printed them on separate lines as that's what Charcoal's default output should be, although Charcoal doesn't know how to output complex numbers, so I've had to cheat slightly. I could extend that cheat and simply output the whole list as a Python array which would save two bytes.)