pacman

Pacman

Contest: Cloudflight Coding Contest - November 2022 (36th CCC) Language: C++17

Problem

Simulate a Pacman game on an N x N grid. Cell types:

Char	Meaning
W	Wall - impassable for Pacman
C	Coin - collected when Pacman enters the cell
P	Pacman's starting cell
G	Ghost starting cell (static in level 4)

Ghosts follow a pre-defined movement sequence that bounces (reverses at the ends): the ghost walks through its sequence forward, then backward, then forward again - ping-pong forever.

If Pacman occupies the same cell as a ghost at any point, he dies. The goal is to collect as many coins as possible before dying (or before running out of allowed steps).

Level progression

Level	What changes
1	No ghosts; count coins on a given Pacman path
2	One moving ghost; simulate and count coins
3	Multiple moving ghosts
4	Multiple static ghosts (G on the grid, no movement sequence)
5	Multiple moving ghosts + find optimal Pacman path

Input Format

N
<N rows of the grid>
pacman_row pacman_col       (1-based)
num_ghosts
  ghost_row ghost_col       (1-based, repeated per ghost)
  sequence_length
  movement_sequence
max_movement_length

Output Format

<number of coins collected>

Algorithm - Tick-based simulation

Each simulation tick:

1. Advance ghosts: each ghost takes one step in its bounce sequence.
2. Collision check: if any ghost shares Pacman's cell -> Pacman dies, stop.
3. Collect coin: if the current cell has an uncollected coin, collect it.

Ghost bounce sequence

idx: 0 1 2 3 4 ... L-1 L-2 ... 1 0 1 2 ...
dir: forward ----------> <----- backward --->

The ghost always applies the direction at seq[idx], but if traversing backward it inverts the direction character (U<->D, L<->R). After each step the index increments or decrements depending on current traversal direction, and flips when it reaches the end.

Why this works

The bounce model guarantees ghosts stay on their corridor indefinitely. The simulation is deterministic, so we just run it step by step until Pacman dies, collects everything, or exhausts max_steps.

Complexity

• O(max_steps x G) where G = number of ghosts
• Coin collection uses a set<pair<int,int>> -> O(C log C) insertions

Compile & Run

g++ -std=c++17 -O2 -o solution solution.cpp
./solution < input.in