There is no Spoon - Episode 1 – CodinGame solution in C
Store the grid as rows of characters, then for every cell containing '0' scan to the right along its row and downward along its column until you hit the next '0'. Print the node's coordinates, the first node found on the right and the first node found below, using -1 -1 when a scan reaches the edge. With at most 30x30 cells this direct scan is far fast enough.
The problem
You receive a small grid (width and height up to 30) in which '0' marks a power node and '.' marks an empty cell. For every node you must report which node it would connect to horizontally and vertically: the closest node to its right on the same row, and the closest node below it in the same column.
Each output line has six integers: x y of the node, then x y of its right neighbour, then x y of its bottom neighbour, with -1 -1 standing in for a missing neighbour. Coordinates are column first, row second. The puzzle used to be called APU: Init Phase and is the warm-up for the much harder There is no Spoon - Episode 2.
Approach, step by step
- Read the grid row by rowKeep each row as a string or char array and index it as grid[y][x]. Writing it down in that order from the start avoids the most common bug in this puzzle: swapping x and y somewhere between reading and printing.
- Visit nodes in reading orderLoop over y, then x, and only act on cells equal to '0'. Reading order (top to bottom, left to right) is the order used in the examples, so stick to it rather than collecting nodes in a set or dictionary with no defined order.
- Scan right for the next nodeFrom x+1 to width-1 on the same row, stop at the first '0'. Empty cells are skipped, so the neighbour can be several columns away; it is not simply the adjacent cell.
- Scan down for the next nodeDo the same from y+1 to height-1 in the same column. If either scan reaches the border without finding a node, output -1 -1 for that neighbour.
- Print one line per nodeConcatenate the three coordinate pairs into a single line. Build the line in one print call so you do not leave stray spaces or a missing newline at the end.
Complexity
O(W·H·(W+H))O(W·H)Each node may scan a full row and a full column, which is at most 900 × 60 character checks. A backwards pass that remembers the last node seen per row and column would make it O(W·H), but it is not needed at this size.
Solution code
Bug fixed in this version: C: rows are read with fgets(line, 31, stdin). When the grid is 30 cells wide, fgets stops after 30 characters and leaves the newline in the buffer, so the next fgets returns an empty line and every following row is shifted or filled with stale data (tested: a 30-wide grid produces wrong bottom neighbours). Python: logic is correct but every line ends with a trailing space ('... x y '), which some strict comparisons reject. Clean replacements for both are provided.
There is no Spoon - Episode 1 – C
#include <stdio.h>
int main()
{
int width, height;
scanf("%d %d", &width, &height);
char grid[30][32];
for (int y = 0; y < height; y++)
scanf("%31s", grid[y]);
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (grid[y][x] != '0')
continue;
// closest node to the right on the same row
int rx = -1, ry = -1;
for (int k = x + 1; k < width; k++)
if (grid[y][k] == '0') { rx = k; ry = y; break; }
// closest node below in the same column
int bx = -1, by = -1;
for (int k = y + 1; k < height; k++)
if (grid[k][x] == '0') { bx = x; by = k; break; }
printf("%d %d %d %d %d %d\n", x, y, rx, ry, bx, by);
}
}
return 0;
}
There is no Spoon - Episode 1 – Python
width = int(input())
height = int(input())
grid = [input() for _ in range(height)]
for y in range(height):
for x in range(width):
if grid[y][x] != '0':
continue
# closest node to the right on the same row
right = next((f"{k} {y}" for k in range(x + 1, width) if grid[y][k] == '0'), "-1 -1")
# closest node below in the same column
below = next((f"{x} {k}" for k in range(y + 1, height) if grid[k][x] == '0'), "-1 -1")
print(f"{x} {y} {right} {below}")
Common mistakes
- Only checking the adjacent cellThe neighbour is the next node on the row or column, not the cell at x+1. A grid like '0.0' must give 2 0 as the right neighbour of 0 0, not -1 -1.
- Swapping x and yInput is read row by row, so the natural index is grid[y][x], but the output wants x first. Mixing the two works on square symmetric examples and fails on the first rectangular test.
- Fixed-size line buffers that are one byte shortA 30-character row needs room for the newline and the terminating zero. With fgets you need at least 32 bytes, otherwise the newline spills into the next read and the grid becomes garbage.
- Formatting the -1 -1 case differentlyWhen a neighbour is missing you still print two numbers. Printing a single -1, or nothing, makes the line length inconsistent and the validator rejects it.
Going further
If you later tackle There is no Spoon - Episode 2, it pays to compute these neighbours in a single backwards pass: iterate rows from bottom to top and columns from right to left while keeping, for each row, the last node seen and, for each column, the last node seen. When you meet a node, those two remembered values are exactly its right and bottom neighbours, and you then overwrite them with the current node. That turns the work into O(W·H) and gives you the adjacency list that Episode 2's backtracking search needs, without any rescanning.
FAQ
Is APU: Init Phase the same puzzle as There is no Spoon - Episode 1?
Yes. CodinGame renamed it; the rules, input and output are unchanged, so any solution for one passes the other.
Do I need a graph structure or BFS here?
No. The grid itself is the graph and each node has at most one right and one bottom neighbour, so two linear scans per node are enough.
What does a node with no neighbour print?
Its own coordinates followed by -1 -1 for the missing right neighbour and/or -1 -1 for the missing bottom neighbour, always six numbers per line.