Introduction to the problem

The full description can be found in https://adventofcode.com/2025/day/4. Let me summarize the main points of the problem:

You are given a grid of rolls (‘@’). A roll is called accessible if there are fewer than four rolls in the eight adjacent positions. In part 1, we need to count how many accessible rolls. Part 2 is more interesting: we remove all accessible rolls from initial grid to get a new grid. Then we remove all accessible rolls from the new grid. We repeat the process until there are no accessible rolls. Count how many rolls were removed in total.

Part 1 is easily done by scanning all positions and count how many neighbor rolls each roll @ has. I will mainly discuss part 2.

Relation to \(k\)-core decomposition

The problem can be translated into the language of Graph Theory: each position \((i,j)\) where ‘@’ is located is a vertex (or node). Two vertices \((i_1,j_1)\) and \((i_2,j_2)\) are adjacent (i.e. there is an edge connecting them) if \(\max(|i_1-i_2|, |j_1-j_2|)=1\). The degree of each vertex is at most \(8\). This is an example of King’s graph.

A vertex \(v\) is accessible if \(\deg(v)<4\). We repeatedly remove vertices of degree \(<4\), the final resulting graph is called a \(4\)-core whose all vertices have degree \(\geq 4\).

Through the process, we have removed \(71-28=43\) vertices to obtain the \(4\)-core graph. The part 2 problem is related to the construction of the \(4\)-core graph. In 2003, Batagelj & Zaversnik introduced a \(k\)-core decomposition algorithm which has efficiency \(O(m)\), where \(m=|E|=\) number of edges in \(G\). In order to discuss the algorithm and how it is adapted to our problem, let me introduce some notions.

Some definitions

Let \(G=(V, E)\) be an undirected graph, with \(V\) is the set of vertices and \(E\) is the set of edges. The (maximal) subgraph \(H_k\) of \(G\) is called a \(k\)-core or core of order \(k\) if every vertex of \(H_k\) has degree \(\geq k\). The following result shows an equivalent definition of \(k\)-core.

BATAGELJ & MRVAR (1998)
If from a given graph \(G=(V, E)\) we recursively delete all vertices, and edges incident with them, of degree less than \(k\), the remaining graph is the \(k\)-core.

The core number (or coreness) of vertex \(v\) is the highest order of a core that contains this vertex. In other words, a vertex \(v\) has coreness \(c\) if it belongs to the \(c\)-core but not to \((c+1)\)-core.

By the definition, \(k\)-cores are nested:

\[ H_0 \supseteq H_1 \supseteq H_2 \supseteq H_3 \supseteq \dots\]

• the graph itself is the \(1\)-core since all vertices have degree at least \(1\).
• subgraph formed by red and green vertices is the \(2\)-core.
• subgraph formed by red vertices is the \(3\)-core.

\(k\)-core theory has vast applications in social networks, biology, ecology, … (see [2]) If we know the coreness all of vertices of \(G\), we can construct the core of any order \(k\). Batagelj-Zaversnik algorithm provides us an efficient way to compute the coreness numbers.

Batagelj-Zaversnik algorithm

The general outline of the algorithm is as follows:

INPUT: graph \(G=(V, E)\) represented by lists of neighbors

OUTPUT: table core with core number for each vertex

The idea is simple: The degree of a vertex at the moment it is processed is its core number. We iteratively peeling smallest current degree vertices. When a vertex is removed, it reduces the degree of its neighbors by \(1\). But if a neighbor’s degree drops, it may move earlier in the order (correspond to the step “reorder \(V\) accordingly”). We need an efficient method to keep track the order of \(V\) and also to implement step 2. To this end, the algorithm uses 4 arrays

• \(deg[v]\): current degree of vertex \(v\)
• \(vert[i]\): vertex at position \(i\) in sorted order
• \(pos[v]\): current position of vertex \(v\) in \(vert\)
• \(bin[d]\): starting index of vertices with degree \(d\)

These arrays allow constant-time swaps and constant-time updates when degrees decrease. In [1], the authors described the algorithm in Pascal-like language. Let me rewrite the algorithm in Python-like pseudocode.

# Python-like pseudocode of Batagelj-Zaversnik k-core algorithm
def core_number(G):
    n = len(G)  # n=number of vertices
    # Step 1: compute degrees
    deg = [0] * n
    for v in range(n):
        deg[v] = len(G[v]) # G[v]=list of vertices incident to v
    #record the maximum degree
    md = max(deg)
    # Step 2: count degrees
    bin = [0] * (md + 1)
    for v in range(n):
        bin[deg[v]] += 1
    # Step 3: transform bin so that 
    # bin[d]=starting index of vertices with degree d
    start = 0
    for d in range(md + 1):
        num = bin[d]
        bin[d] = start
        start += num
    # Step 4: initialize vert and pos
    vert = [0] * n 
    pos = [0] * n
    for v in range(n):
        pos[v] = bin[deg[v]]
        vert[pos[v]] = v
        bin[deg[v]] += 1
    # vert[]=vertices in increasing order
    # pos[v]=position of v in vert[]
  
    # restore bin[] to the bin[] in step 2
    for d in range(md, 0, -1):
        bin[d] = bin[d - 1]
    bin[0] = 0
    # Step 5: peel vertices (main step)
    for i in range(n):
        # process vertices with smallest degree first
        v = vert[i]
        for u in G[v]: # for each vertex u adjacent to v
            # if deg[u]> deg[v], remove vertex v
            if deg[u] > deg[v]:
            # remove vertex v
                du = deg[u]
                pu = pos[u]
                pw = bin[du]
                w = vert[pw]
                # w is the first vertex in vert[] whose degree
                # equals to deg[u]
                if u != w:
                    # swap u and w in vert[] and pos[]
                    vert[pu], vert[pw] = vert[pw], vert[pu]
                    pos[u], pos[w] = pos[w], pos[u]
                # update bin[du] and deg[u]
                bin[du] += 1
                deg[u] -= 1 # since v is removed
    return deg  # deg[v] is the core number

Look at an example of a small graph with \(n=5\) vertices.

The graph \(G\) is represented is adjacency dictionary:

\(G= \{0: [1,3,4], 1: [0,2,3], 2: [1], 3:[0,1,4], 4: [0,3] \} \)

Vertices \(V= \{0, 1, 2, 3, 4\}\)

After step 1: \( deg= [3, 3, 1, 3, 2] \), maximum degree \(md=3\).

After step 2: \( bin= [0, 1, 1, 3] \) (degree counts)

After step 3: \( bin= [0, 0, 1, 2] \). This means when sorting vertices in increasing degree order in step 4, vertices of degree \(0\) start at index \(0\) , vertices of degree \(1\) start at index \(0\) , vertices of degree \(2\) start at index \(1\) , vertices of degree \(3\) start at index \(2\) .

After step 4:

• \( vert= [2, 4, 0, 1, 3] \), vertices in increasing degree order ( [ C | E | A, B, D] )
• \( pos= [2, 3, 0, 4, 1] \) (vertex \(0\), i.e. A, has position \(2\) in \(vert\); vertex \(1\) , i.e. B, has position \(4\) and so on)

In step 5, we process vertex with smaller degree first. For example, consider the vertex with smallest degree, that is, \(v=vert[0]=2\) (i.e. C). The only neighbor of \(v\) is \(u=1\) (or B). Since \(deg[u]=3 > deg[v]=1\), we will remove \(v\), which makes \(deg[u]\) decrease by \(1\). To update this accordingly, we swap \(u\) and \(w\), where \(w=0\) (or A) is the first vertex in \(vert\) whose degree is \(3\) . The array \(vert\) now becomes [ C | E, B | A, D], where vertex B now joined the group of \(2\) -degree vertices.

After processing all vertices, the final result is \( deg= [2, 2, 1, 2, 2] \), which gives the core numbers of A, B, C, D, E respectively. To construct the \(k\)-core, we just collect vertices of coreness \(\geq k\). In particular, the subgraph formed by A, B, D, E is the \(2\)-core and there is no \(3\)-core.

Observe that for all steps, every vertex is visited once with \(O(1)\) operations, therefore the total complexity is \(O(|V|+|E|)\). Also note that we don’t actually remove the vertex: we technically remove it by decreasing degrees of its neighbor’s vertex and record the state by 4 arrays. This avoids rebuilding the graph.

\(k\)-core in NetworkX:

NetworkX is a nice Python library for studying graphs and networks. The function k_core(G, k) in NetworkX allows you quickly get the \(k\)-core of a graph. It uses exactly the same logic of Batagelj-Zaversnik algorithm with some minor changes (for example, uses dictionary for \(deg\) and \(pos\) instead of arrays). For the AoC problem part 2, we simply need to create the graph \(G\), pass it into (k\)_core function with \(k=4\). The final result is number of nodes of \(G -\) number of nodes of the \(4\)-core.

An adaptation for the part 2 problem

In this problem we need to count how many vertices (rolls) are removed rather than compute all core numbers. We can track the number of removed vertices in step 5 and stop when all vertices have coreness \(\geq 4\). In a similar way, we can use a deque to store all vertices with degree \(< 4\), which are vertices to be removed. If the degree of the neighbor vertices decrease to \(3\), add them to the deque to wait for being removed. When the deque is empty, we are done.

References

1. Batagelj, V., & Zaversnik, M. (2003). An O(m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049.

2. Kong, Y. X., Shi, G. Y., Wu, R. J., & Zhang, Y. C. (2019). k-core: Theories and applications. Physics Reports, 832, 1-32. (link)

3. Batagelj, V., & Mrvar, A. (1998). Pajek-program for large network analysis. Connections, 21(2), 47-57.