Problem: programming_paths_part_1 (2023 finals)

_The only difference between chapters 1 and 2 is the maximum allowed grid size, given in bold below._

A *Drizzle* program is a 2D grid of the following four types of cells:
 - '`@`' (start) \(-\) there is exactly one start cell in the entire grid
 - '`#`' (wall)
 - '`.`' (space)
 - '`*`' (instruction)

The program uses two registers \(A\) and \(B\) (both initially \(0\)), and executes as follows:

1. Compute the minimum distance from the start to each instruction cell using orthogonal movements, without going outside of the grid or passing through any wall cells. Instruction cells that cannot be reached are ignored. 
2. In increasing order, for each unique distance \(D\) such that there’s at least one instruction cell that’s at distance \(D\) from the start cell:
   2a. Count the number of shortest paths, \(P\), to all instruction cells of distance \(D\).
   2b. Look up the instruction corresponding to \((P \text{ mod } 2, D \text{ mod } 2)\) in the table below and modify one of the registers accordingly.
3. At the end, the value in register \(A\) is outputted.

```
┌─────────────┬─────────────┬─────────────┐
│             │ D mod 2 = 0 │ D mod 2 = 1 │
├─────────────┼─────────────┼─────────────┤
│ P mod 2 = 0 │ A := A + 1  │ A := A - 1  │
│ P mod 2 = 1 │ B := B + A  │ A := B      │
└─────────────┴─────────────┴─────────────┘
```

For a given value \(K\), output any Drizzle program that outputs \(K\) when executed, with the restriction that **the program must fit on a \(\mathbf{13}\) × \(\mathbf{13}\) grid**.


# Constraints

\(1 \le T \le 2{,}000\)
\(0 \le K \le 10{,}000\)


# Input Format

Input begins with an integer \(T\), the number of test cases. For each case, there is a line containing the single integer \(K\).


# Output Format

For the \(i\)th case, output "`Case #i: `" followed by two integers \(R\) and \(C\), the number of rows and columns in your program, respectively. Then output your program. It must be exactly \(R\) lines long, with each line containing exactly \(C\) characters.


# Sample Explanation

Here are the instructions executed for each of the sample programs. Note that many other programs would be accepted for any for these cases.

In the first case, there is a single instruction. There are \(2\) shortest paths of length \(2\) to that instruction, so \(P = 2\) and \(D = 2\). That means we perform \(A := A + 1\). There are no more instructions, so the program ends and outputs \(1\).

In the second case, there are three instruction cells. Each of them are an even distance from the start, and each have an even number of shortest paths leading to them, so each represents \(A := A + 1\):

1) \(2\) paths of length \(2\) \(\;(A := A + 1 = 1)\)
2) \(4\) paths of length \(6\) \(\;(A := A + 1 = 2)\)
3) \(4\) paths of length \(12\) \(\;(A := A + 1 = 3)\)

In the third case, there are eight instruction cells, but some of them are at the same distance as each other. In particular, there are two instruction cells at distance \(2\), and three instruction cells at distance \(10\). There's a single shortest path to each of the cells at distance \(2\), so in total there are \(2\) shortest paths to instructions at distance \(2\). One of the cells at distance \(10\) has a unique shortest path, and the other has two shortest paths, so in total there are \(3\) shortest paths to instructions at distance \(10\).

1) \(2\) paths of length \(2\) \(\;(A := A + 1 = 1)\)
2) \(6\) paths of length \(4\) \(\;(A := A + 1 = 2)\)
3) \(1\) path of length \(6\) \(\;(B := B + A = 2)\)
4) \(1\) path of length \(8\) \(\;(B := B + A = 4)\)
5) \(3\) paths of length \(10\) \(\;(B := B + A = 6)\)
6) \(3\) paths of length \(11\) \(\;(A := B = 6)\)


Sample input:
3
1
3
6


Sample output:
Case #1: 2 2
@.
.*
Case #2: 5 6
@.#.*.
.*#...
#.#...
...#.#
..*...
Case #3: 4 10
...#*.*.**
.*.*##..#.
.....#*#..
.@.*.....#


Solution: It's clear that larger numbers will tend to require larger programs. By repeating \(B := B + A\) and \(A := B\) we can exponentiate to get to a large number quickly. We'll also need \(A := A + 1\) to get started, and to make smaller adjustments. However, \(A := A - 1\) is not nearly as useful (technically it has some utility when trying to strictly minimize the number of instructions it takes to generate a certain value, but that isn't the goal in this problem).

Since \(A := A - 1\) is not very useful, we don't need many, if any, ways to have an even number of paths at an odd distance from the start. We do, however, need to have an even number of paths at *even* distances from the start.

So our two goals when constructing a grid are to make a long enough path to fit all the instructions we need, and also maximize the number of cells at even distances from the start. For example, a grid like this:

```
@##....##....
..#.##..#.##.
.#..##.#..##.
..#.#..##.#..
.#..##.#..##.
..#.#..##.#..
.#..##.#..##.
..#.#..##.#..
.#..##.#..##.
..#.#..##.#..
.#..##.#..##.
.##.#..##.#..
....##....##.
```

This grid gives us one long path, and then many "alcoves" that are all at even distances from the start. Instruction cells along the main path will represent \(B := B + A\) and \(A := B\), and whenever we need to use \(A := A + 1\) we can add another instruction cell in one next alcove.

Given such a grid, there are multiple ways to then determine a program that fits on the grid, such as using dynamic programming where the state is the value of the two registers, or manually constructing a set of instructions where we repeatedly multiply \(A\) by 2 and optionally add \(1\) to \(A\) as needed (essentially constructing the bitstring representation of the goal value).


Code: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int N = 13;

vector<string> G;
vector<int> b;
vector<vector<int>> len;
vector<vector<pair<int, int>>> cells;

inline bool check(int r, int c) {
  return r >= 0 && c >= 0 && r < N && c < N;
}

void dfs(int r, int c, int l) {
  len[r][c] = l;
  if (static_cast<int>(cells.size()) <= l) {
    cells.resize(l + 1);
  }
  cells[l].emplace_back(r, c);
  for (auto [r2, c2] : {pair{r - 1, c}, {r + 1, c}, {r, c - 1}, {r, c + 1}}) {
    if (!check(r2, c2) || G[r2][c2] == '#' || len[r2][c2] != -1) {
      continue;
    }
    dfs(r2, c2, l + 1);
  }
}

int count_adj(int r, int c) {
  int res = 0;
  for (auto [r2, c2] : {pair{r - 1, c}, {r + 1, c}, {r, c - 1}, {r, c + 1}}) {
    if (!check(r2, c2)) {
      continue;
    }
    res += G[r2][c2] == '#';
  }
  return res;
}

void run(int r, int c, int l) {
  len[r][c] = l;
  if (l & 1) {
    for (auto [r2, c2] : {pair{r - 1, c}, {r + 1, c}, {r, c - 1}, {r, c + 1}}) {
      if (!check(r2, c2) || G[r2][c2] != '#') {
        continue;
      }
      if (count_adj(r2, c2) == 3) {
        G[r2][c2] = '.';
        break;
      }
    }
  }
  for (auto [r2, c2] : {pair{r - 1, c}, {r + 1, c}, {r, c - 1}, {r, c + 1}}) {
    if (!check(r2, c2) || G[r2][c2] == '#' || len[r2][c2] != -1) {
      continue;
    }
    run(r2, c2, l + 1);
  }
}

void solve() {
  int K;
  cin >> K;
  b.clear();
  for (int x = K; x; x >>= 1) {
    b.push_back(x & 1);
  }
  reverse(b.begin(), b.end());
  G.assign(N, string(N, '.'));
  G[0][0] = '@';
  for (int j = 1, par = 0; j < N; j += 3, par ^= 1) {
    int st = 0, fn = N;
    if (par) {
      st += 1;
    } else {
      fn -= 1;
    }
    for (int i = st; i < fn; i++) {
      G[i][j] = '#';
      G[i][j + 1] = '#';
    }
  }
  len.assign(N, vector<int>(N, -1));
  run(0, 0, 0);
  len.assign(N, vector<int>(N, -1));
  cells.clear();
  dfs(0, 0, 0);
  vector<int> d0;
  for (int i = 2; i < (int)cells.size(); i += 2) {
    if (d0.size() & 1) {
      d0.push_back(i);
      continue;
    }
    if (cells[i].size() > 1) {
      d0.push_back(i);
    }
  }
  for (int i = 0, ind = 0; i < (int)b.size(); i++, ind += 2) {
    if (b[i]) {
      int d = d0[ind];
      for (int j = 0; j <= 1; j++) {
        auto [r, c] = cells[d][j];
        G[r][c] = '*';
      }
    }
    for (int j = 0; j <= 1; j++) {
      int d = d0[ind + 1] + j;
      auto [r, c] = cells[d][0];
      G[r][c] = '*';
    }
  }
  cout << N << " " << N << endl;
  for (int i = 0; i < N; i++) {
    cout << G[i] << endl;
  }
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": ";
    solve();
  }
  return 0;
}