Problem 1019: Dodecahedron Skeleton

View on Project Euler

Project Euler Problem 1019 Solution

A skeleton is a connected, non-empty set of edges, and skeletons that differ only by a rotation count once. Burnside's lemma turns the count into an average over the 60 rotations of the dodecahedron: a rotation keeps exactly the connected unions of its cycles of edges, and the half-turns, the rotations of order 3 and those of order 5 have only 16, 10 and 6 cycles, so their skeletons are listed directly (the 23 kept by a rotation of order 5 can be counted by hand). The identity needs the number of all connected non-empty sets among the 2^30 sets of edges, which a sweep over the edges finds with tables of at most 731 states. Implementations are available in C++, Python and Java.

Detailed mathematical approach

Problem Summary

A skeleton of a polyhedron is a non-empty set of its edges that is connected: any two edges of the set can be reached from each other along a path of edges of the set. Two skeletons are considered the same if they differ only by a rotation in space. The regular tetrahedron has \(10\) different skeletons, and we must find the number of different skeletons of the regular dodecahedron. [1] The regular dodecahedron has \(12\) pentagonal faces, \(30\) edges and \(20\) vertices; three faces, and hence three edges, meet at each vertex. [2]

The dodecahedron has \(2^{30}-1=1\,073\,741\,823\) non-empty sets of edges, and \(60\) rotations map it onto itself. A computer can list all these sets and compare each of them with its rotated copies, and one of our checks does exactly that, but there is a much shorter way, which rests on two ideas. The first is Burnside's lemma, which replaces the number of different skeletons by an average: for each of the \(60\) rotations, count the skeletons that the rotation maps onto themselves (we say that the rotation keeps them), add these numbers and divide by \(60\). A rotation moves the edges around in cycles, and it maps a set of edges onto itself exactly when the set is a union of such cycles. A rotation other than the identity has at most \(16\) cycles, so the skeletons that it keeps are found by testing fewer than \(2^{16}\) sets; a rotation by a fifth of a turn has only six cycles, and the \(23\) skeletons that it keeps can be counted by hand. The identity keeps every skeleton, so what remains to be found is the number of all connected non-empty sets of edges. The second idea is a sweep, which finds this number by deciding for one edge after another whether it belongs to the set. Of the decisions already made it remembers only this: for each vertex that has both decided and undecided edges, whether a chosen edge ends there, and which of these vertices the chosen edges join to one another; or else only that a connected set has already been completed. Its table of states never has more than \(731\) entries.

Mathematical Approach

We begin with the tetrahedron, where everything can be checked by hand, prove Burnside's lemma, describe the sixty rotations of the dodecahedron and what they do to its edges, and count the skeletons that a rotation keeps. The last two sections count all connected non-empty sets of edges.

1. Skeletons of the tetrahedron

Call two edges adjacent when they have a common endpoint. A set \(S\) of edges is connected when any two of its edges are the first and the last of a sequence of edges of \(S\) in which consecutive edges are adjacent; in other words, the edges of \(S\) and their endpoints form a connected graph. A skeleton is a connected set with at least one edge.

The tetrahedron has four vertices and six edges, one for each pair of vertices. Two edges of the tetrahedron without a common vertex are called opposite; the six edges form three opposite pairs, and all other pairs of edges are adjacent. If a set of edges is not connected, it splits into two parts without a common vertex, and each part uses at least two vertices; with only four vertices, each part is a single edge. So the only sets that are not connected are the three pairs of opposite edges, and of the \(2^6-1=63\) non-empty sets of edges \(60\) are connected. This is the term for \(n=4\) of the sequence A287689 of the OEIS, which counts the non-empty connected sets of edges of the complete graph on \(n\) vertices, the graph in which every two vertices are joined by an edge; for \(n=4\) it is the graph of the tetrahedron. [3]

Sorted by their number of edges, the ten different skeletons are: a single edge; two edges with a common vertex; with three edges, the edges of a face, the three edges at a vertex, and a path through all four vertices, which occurs in two forms; with four edges, a closed path through all four vertices and a face with one more edge attached; five of the six edges; and all six edges. That is \(1+1+4+2+1+1=10\). The two paths of three edges are mirror images of each other, like a left-handed and a right-handed screw, and no rotation turns one into the other; Section 2 shows why. If reflections were allowed as well, only \(9\) different skeletons would remain. The reflection in the plane through an edge and the midpoint of the opposite edge exchanges two vertices and leaves the other two in place, and such exchanges produce all \(24\) permutations of the four vertices. Two skeletons would then be the same exactly when they have the same shape as graphs, and there are \(1+2+6=9\) connected graphs with two, three or four vertices. [4]

Each of the ten different skeletons can be placed on the tetrahedron in one or more positions, that is, it stands for one or more of the \(60\) connected sets: for \(6,12,4,4,6,6,3,12,6\) and \(1\) of them, in the order of the list above, with the two forms of the path counted separately, \(60\) in all. A different skeleton without any symmetry of its own has as many positions as there are rotations, \(12\) for the tetrahedron, but most of the ten are mapped onto themselves by some rotation other than the identity and have fewer. This is why the number of different skeletons is not simply \(60/12\), and it is exactly what Burnside's lemma corrects.

2. Burnside's lemma

Let \(X\) be a finite set and \(G\) a finite group acting on it. For our purposes this means that \(G\) is a finite collection of one-to-one maps of \(X\) onto itself with three properties: it contains the identity; whenever it contains a map \(g\), it contains the inverse \(g^{-1}\); and whenever it contains two maps \(g\) and \(h\), it contains their product \(hg\), the map that applies first \(g\) and then \(h\). The orbit of an element \(x\) consists of all \(g(x)\) with \(g\) in \(G\). Write \(|A|\) for the number of elements of a finite set \(A\), \(X/G\) for the set of orbits and \(F(g)\) for the number of elements \(x\) of \(X\) with \(g(x)=x\). Burnside's lemma states that the number of orbits is the average of the numbers \(F(g)\). [5] In a formula,

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}F(g).$$

To prove it, count the pairs \((g,x)\) with \(g(x)=x\) in two ways. Counted by \(g\), there are \(\sum_{g}F(g)\) of them. Now fix \(x\), and let \(G_x\) be the set of all \(g\) with \(g(x)=x\). If \(y=h(x)\) is an element of the orbit of \(x\), the elements of \(G\) that carry \(x\) to \(y\) are exactly the products \(hg\) with \(g\) in \(G_x\): such a product carries \(x\) to \(y\), and if \(f\) carries \(x\) to \(y\), then \(g=h^{-1}f\) leaves \(x\) in place and \(f=hg\). Different \(g\) give different products, so there are \(|G_x|\) of them, the same number for every \(y\). Every element of \(G\) carries \(x\) to exactly one element of its orbit, so \(|G|=|G_x|\cdot r\) when the orbit of \(x\) has \(r\) elements, and \(x\) belongs to \(|G_x|=|G|/r\) pairs. Because \(G\) contains the inverses and the products of its maps, two orbits are either equal or have no common element. So each of the \(r\) elements of an orbit belongs to \(|G|/r\) pairs, the whole orbit to \(|G|\) pairs, and the number of pairs is \(|G|\) times the number of orbits.

Here \(X\) will be the set of the skeletons of the polyhedron, in all their positions, and \(G\) will consist of the rotations of the polyhedron, that is, of the rotations of space that map the polyhedron onto itself, the identity included; such a rotation leaves the centre of the polyhedron in place, so its axis passes through the centre. A rotation \(g\) carries a skeleton \(S\) to the skeleton \(g(S)\). This fits the definition: a rotation of the polyhedron carries edges to edges and adjacent edges to adjacent edges, hence skeletons to skeletons; the inverse of such a rotation and the product of two of them are again rotations of the polyhedron, because two rotations about axes through the centre combine to a rotation about an axis through the centre, by Euler's rotation theorem; [6] and different rotations act differently on \(X\), because a rotation other than the identity moves at least one edge, and every single edge is a skeleton. We read the problem statement as follows: two skeletons are the same when some rotation of the polyhedron carries one to the other, that is, when they lie in the same orbit. Each orbit is thus one of the different skeletons, and its elements are the positions of that skeleton, as in Section 1. The value \(10\) for the tetrahedron fits this reading, since with reflections there would be only \(9\), and the answer is the number of orbits.

The lemma needs one more observation. A rotation \(g\) permutes the edges, and repeating it moves each edge \(e\) through a cycle \(e,\ g(e),\ g(g(e)),\dots\) that returns to \(e\). A set \(S\) of edges satisfies \(g(S)=S\) exactly when, with each of its edges, it contains the whole cycle of that edge, that is, when \(S\) is a union of cycles of \(g\). A rotation with \(q\) cycles therefore maps \(2^q-1\) non-empty sets of edges onto themselves, and \(F(g)\), the number of skeletons that \(g\) keeps, is the number of connected sets among them.

For the tetrahedron, \(G\) has \(12\) elements, which are described next; there are no others, by the argument that Section 3 gives for the dodecahedron, applied to the \(12\) directed edges of the tetrahedron. The identity has six cycles of one edge and keeps all \(60\) skeletons. Eight rotations turn by one third or two thirds of a full turn about one of the four axes through a vertex and the centre of the face that does not contain it; such a rotation has two cycles, the three edges at the vertex and the three edges of the face, and all three non-empty unions of these cycles are connected. Three rotations are half-turns, one about each of the three axes through the midpoints of two opposite edges; a half-turn maps each of these two edges onto itself, exchanging its endpoints, and exchanges the other four edges in two pairs of opposite edges. Its four cycles have \(15\) non-empty unions, and by Section 1 exactly three of them, the three pairs of opposite edges, are not connected. The lemma gives

$$\frac{60+8\cdot3+3\cdot12}{12}=\frac{120}{12}=10,$$

the number given in the problem statement. The relation \(|G|=|G_x|\cdot r\) from the proof also explains the two paths of Section 1. A rotation that maps the path through the vertices \(a,b,c,d\), in this order, onto itself either leaves all four vertices in place, and is the identity, or reverses the path, and is the half-turn that exchanges \(a\) with \(d\) and \(b\) with \(c\). So the path has \(12/2=6\) positions. But the tetrahedron has \(4!/2=12\) such paths, so they fall into two orbits of six. With reflections allowed, the tetrahedron has \(24\) symmetries, one for each permutation of its vertices (Section 1), and they carry any of these paths to any other; by the same relation only \(24/12=2\) of them map a given path onto itself, and these are the two rotations just found. So a symmetry \(t\) that is not a rotation cannot carry a path \(P\) to a path \(g(P)\) of the same orbit, where \(g\) is a rotation: \(g^{-1}t\) would map \(P\) onto itself without being a rotation. Every symmetry that is not a rotation, and in particular every reflection, therefore carries each of the two orbits into the other.

3. The sixty rotations

Put the centre of the dodecahedron at the origin, and let \(\varphi=(1+\sqrt5)/2\). The twenty vertices of the dodecahedron can be taken to be the following points. [2] Eight of them are the points \((\pm1,\pm1,\pm1)\), and the other twelve are

$$\begin{aligned}&(0,\pm\tfrac1\varphi,\pm\varphi),\quad(\pm\tfrac1\varphi,\pm\varphi,0),\\&(\pm\varphi,0,\pm\tfrac1\varphi).\end{aligned}$$

Every vertex has exactly three nearest vertices, at distance \(2/\varphi\), and the \(30\) pairs of nearest vertices are the edges. For example, the coordinates of \((1,1,1)\) and \((0,\tfrac1\varphi,\varphi)\) differ by \(1\), \(1-\tfrac1\varphi=\varphi^{-2}\) and \(\varphi-1=\varphi^{-1}\), so the squared distance between these two points is \(1+\varphi^{-4}+\varphi^{-2}\). This equals \(4\varphi^{-2}\): multiplied by \(\varphi^4=3\varphi+2\), both numbers become \(4\varphi+4\), because \(\varphi^2=\varphi+1\).

As in Section 2, a rotation of the dodecahedron is a rotation of space that maps the solid onto itself; its axis passes through the centre, and it maps vertices onto vertices and edges onto edges. The order of a rotation is the number of times it must be applied until every point is back in its place. Two faces, two vertices or two edges of the dodecahedron are called opposite when the reflection in the centre, which carries every point to the point at the same distance on the other side of the centre, exchanges them. The dodecahedron has the following rotations:

  • the identity, of order \(1\);
  • \(24\) rotations of order \(5\), by \(72^\circ\), \(144^\circ\), \(216^\circ\) or \(288^\circ\) about one of the \(6\) axes through the centres of two opposite faces;
  • \(20\) rotations of order \(3\), by \(120^\circ\) or \(240^\circ\) about one of the \(10\) axes through two opposite vertices;
  • \(15\) rotations of order \(2\), the half-turns about the \(15\) axes through the midpoints of two opposite edges.

These are \(1+24+20+15=60\) rotations. [7] There are no others. To see this, call an edge together with one of its two directions a directed edge; there are \(60\) of them. A rotation other than the identity leaves in place only the points of its axis, and two neighbouring vertices \(a\) and \(b\) do not lie on a common line through the centre. Now suppose that two rotations of the dodecahedron carry the directed edge from \(a\) to \(b\) to the same directed edge. The first followed by the inverse of the second is again a rotation of the dodecahedron (Section 2), and it leaves \(a\) and \(b\) in place; so it is the identity, and the two rotations are equal. Hence different rotations carry a fixed directed edge to different directed edges, there are at most \(60\) rotations, and since there are \(60\), for any two directed edges exactly one rotation carries the first to the second.

4. Cycles of edges

Which rotations map an edge onto itself? If a rotation other than the identity maps the edge \(ab\) onto itself, it cannot leave \(a\) and \(b\) in place, so it exchanges them, and by Section 3 only one rotation does that. The half-turn about the axis through the midpoint of \(ab\) does that, so the rotation is this half-turn. Its axis meets exactly two edges, \(ab\) and the opposite edge. Therefore:

  • a half-turn maps each of the two edges that its axis meets onto itself, exchanging its endpoints, and exchanges the other \(28\) edges in pairs, which gives \(2+14=16\) cycles;
  • a rotation \(g\) of order \(3\) maps no edge onto itself, and neither does \(g^2\), which also has order \(3\); so no edge returns before the third step, and \(g\) has \(10\) cycles of three edges;
  • a rotation \(g\) of order \(5\) and its powers \(g^2,g^3,g^4\), which also have order \(5\), map no edge onto itself, so \(g\) has \(6\) cycles of five edges.

The number \(F(g)\) depends only on the order of \(g\), for three reasons. First, two rotations of the same order about the same axis have the same cycles, as sets of edges: each of them is a power of the other, for instance \(g=(g^2)^3\) when \(g\) has order \(5\), and the cycles of a power of \(g\) lie inside the cycles of \(g\). Second, let \(h\) be any rotation of the dodecahedron. Then \(hgh^{-1}\) is a rotation of the same order as \(g\) about the axis into which \(h\) carries the axis of \(g\), and \(g\) maps \(S\) onto itself exactly when \(hgh^{-1}\) maps \(h(S)\) onto itself; since \(h\) carries skeletons to skeletons, \(F(hgh^{-1})=F(g)\). Third, any two axes of the same kind are carried into each other by a rotation of the dodecahedron: by Section 3 a rotation can carry any directed edge to any other, and with the edge it carries along the midpoint of the edge, its starting point and, seen from outside the solid, the face on its left. So if \(g\) and \(g'\) have the same order, their axes are of the same kind by the list of Section 3, and some rotation \(h\) carries the axis of \(g\) to the axis of \(g'\); then \(hgh^{-1}\) and \(g'\) have the same cycles, and \(F(g')=F(hgh^{-1})=F(g)\).

So there are four numbers \(F_1,F_2,F_3,F_5\) such that every rotation of order \(k\) keeps exactly \(F_k\) skeletons, and the number \(K\) of different skeletons of the dodecahedron is

$$K=\frac{F_1+15F_2+20F_3+24F_5}{60}.$$

Without the word connected the problem would end here. A rotation with \(q\) cycles maps \(2^q\) sets of edges onto themselves, the empty set included, so the number of different sets of edges, where two sets are the same if a rotation carries one to the other, is

$$\begin{aligned}&\frac{2^{30}+15\cdot2^{16}+20\cdot2^{10}+24\cdot2^{6}}{60}\\&\qquad=17\,912\,448.\end{aligned}$$

One of them is the empty set, so \(17\,912\,447\) of them are non-empty. Connectedness cannot be read off from the number of cycles: the numbers \(F_k\) have to be found by looking at the sets themselves.

5. Skeletons kept by a rotation

First take a rotation of order \(5\), and hold the dodecahedron so that the axis of the rotation is vertical, with one face on top and the opposite face at the bottom. The six cycles are then easy to name: the five edges of the top face, \(T\); the five edges that lead downwards from its vertices, the upper spokes \(U\); the five edges of the bottom face, \(B\); the five lower spokes \(L\), which lead upwards from its vertices; and the remaining ten edges, which form a closed zigzag path around the middle, the belt, and make up the last two cycles. The vertices of the belt are alternately lower ends of upper spokes and upper ends of lower spokes, and its edges belong alternately to the two cycles \(Z_1\) and \(Z_2\), because the rotation carries lower ends of upper spokes to lower ends of upper spokes and so moves the belt by an even number of steps. The edges of \(T\) form a closed path, and so do those of \(B\); each of the cycles \(U\), \(L\), \(Z_1\) and \(Z_2\) consists of five edges without common vertices. Which unions of these six cycles are connected?

  • If the union contains \(Z_1\) and \(Z_2\), the belt holds it together. Above the belt there may be nothing, \(U\), or \(U\) and \(T\); the face \(T\) without \(U\) is not possible, because it touches the rest only through the upper spokes. The same three possibilities exist below the belt, which gives \(3\cdot3=9\) skeletons.
  • If it contains exactly one of \(Z_1\) and \(Z_2\), these five edges are separate, and something must tie them together: \(U\) and \(T\) from above, or \(L\) and \(B\) from below. With \(U\) and \(T\) present there are three possibilities below; otherwise \(L\) and \(B\) must be present, and above there is nothing or \(U\) alone. That gives \(2\cdot(3+2)=10\) skeletons.
  • If it contains neither, the upper and the lower edges cannot meet, so the union lies entirely above or entirely below the belt: \(T\), or \(T\) and \(U\), or \(B\), or \(B\) and \(L\). That gives \(4\) skeletons.

Hence \(F_5=9+10+4=23\): of the \(63\) non-empty unions, \(23\) are connected.

A rotation of order \(3\) has ten cycles of three edges, among them the three edges at each of the two vertices on its axis. A half-turn has the two edges that its axis meets, each a cycle of its own, and \(14\) cycles of two edges. For these rotations the program lists the non-empty unions, \(2^{10}-1=1023\) and \(2^{16}-1=65\,535\) of them, tests each for connectedness, and finds \(F_3=373\) and \(F_2=14\,432\). The table shows, for each order \(k\), the number \(m_k\) of rotations, the number \(q\) of cycles of each of them, the number \(2^q-1\) of non-empty unions and the number \(F_k\) of skeletons among them.

\(k\)\(m_k\)\(q\)\(2^q-1\)\(F_k\)
\(1\)\(1\)\(30\)\(2^{30}-1\)\(F_1\)
\(2\)\(15\)\(16\)\(65\,535\)\(14\,432\)
\(3\)\(20\)\(10\)\(1023\)\(373\)
\(5\)\(24\)\(6\)\(63\)\(23\)

The last three rows contribute

$$\begin{aligned}&15\cdot14\,432+20\cdot373+24\cdot23\\&\qquad=224\,492\end{aligned}$$

to the sum in Burnside's lemma. The first row is the hard one: \(F_1\) is the number of all connected non-empty sets of edges, and it turns out to be more than a hundred million.

6. Sweeping the edges

It remains to count the connected sets among the \(2^{30}-1\) non-empty sets of edges. Testing all of them one by one is possible but slow. The sweep reaches the same number much faster, because it treats sets that behave alike together. It works for any graph.

Fix an ordering of the edges. The sweep goes through the edges in this ordering and decides each of them: the edge is either chosen or not. Every set of edges corresponds to exactly one sequence of decisions, and the edges chosen so far form a partial set. At any moment the chosen edges form pieces, the connected parts into which they fall, and a vertex is on the frontier if at least one of its edges has been decided and at least one has not. A piece that has a vertex on the frontier is open: an undecided edge at that vertex can still enlarge it or join it to another piece. A piece without a vertex on the frontier is closed: every edge at each of its vertices has been decided, so no later edge can touch it, and it will be one of the pieces of the final set.

The final set is a skeleton exactly when it consists of a single piece. So a partial set can be dropped as soon as a piece closes while another piece is still open, or two pieces close at the same time, or an edge is chosen after a piece has closed: in each case the final set would have at least two pieces. If, on the other hand, a piece closes and there is no other piece, the edges chosen so far form a skeleton, and the final set is a skeleton exactly when no further edge is chosen. We then call the partial set finished.

As long as a partial set is neither dropped nor finished, all its pieces are open, and what can still happen to it depends only on two things: which frontier vertices are endpoints of chosen edges, and which of these vertices belong to the same piece. The sweep therefore records a state, one label for each frontier vertex: \(0\) if no chosen edge ends at the vertex, and otherwise the number of its piece, where the pieces are numbered \(1,2,\dots\) in the order in which they first occur in the list of frontier vertices, so that equal patterns get equal names. One further state stands for the finished sets. For every state the sweep stores its count, the number of partial sets that have led to it; at a given step, partial sets in the same state have the same possible futures, so they need not be told apart. The states that occur after a step, each with its count, form the table of that step. This is the idea of frontier-based search, in which the decided part of a graph is summarised by the connections among the frontier vertices. [8]

Deciding an edge \(uv\) changes a state as follows. An endpoint that is not yet on the frontier enters it with the label \(0\). If the edge is not chosen, no label changes. If it is chosen and both labels are \(0\), the edge starts a new piece with a new number; if one label is \(0\), that vertex receives the label of the other; if the labels are different numbers, two pieces merge, and every vertex with one of the two labels receives the other; if they are the same number, the edge joins two vertices of the same piece and no label changes. Then every vertex whose last edge has just been decided leaves the frontier. A piece whose label no longer occurs on the frontier has closed, and the rule above is applied: the state is dropped if another piece remains on the frontier or if two pieces close at once, and otherwise it becomes the finished state, in which every later edge must be left unchosen. If no piece has closed, the pieces that remain are numbered anew.

At the start the frontier is empty and there is one partial set, the empty one. At the end the frontier is empty again, and the only states that can remain are the state without pieces, reached only by the empty set, and the finished state, whose count is the number of connected non-empty sets of edges. Take, for example, the tetrahedron with the vertices \(a,b,c,d\) and the edges in the ordering \(ab,ac,ad,bc,bd,cd\). Choose \(ab\) and do not choose \(ac\) and \(ad\); then \(a\) has left the frontier, but the piece \(ab\) is still open at \(b\). If \(bc\) and \(bd\) are not chosen either, \(b\) leaves the frontier and the piece closes: the set is finished, and \(cd\) can no longer be chosen. Indeed \(ab\) and \(cd\) together are a pair of opposite edges. The sweep of the tetrahedron ends with the count \(60\) in the finished state, as in Section 1.

7. A short frontier

The number of states depends on the ordering of the edges; a good ordering makes the frontier short. The program numbers the vertices in the order of a breadth-first search, which starts at the first vertex of the program's list of vertices, continues with the neighbours of that vertex, then with their unvisited neighbours, and so on, always in the order in which the list of edges yields them; it then sorts the edges by the smaller of the two numbers of their endpoints and, among edges with the same smaller number, by the larger one. The decided region grows from the first vertex across the dodecahedron towards the opposite vertex, and the frontier has at most seven vertices while an edge is being decided and at most six between two steps.

Six frontier vertices allow at most \(877\) states besides the finished one. To see this, add an imaginary seventh element to the six vertices. Put it in one block with the vertices of label \(0\), and let the vertices of each piece form a block of their own. Every state thus divides the seven elements into blocks, and different states give different divisions. A set of seven elements can be divided into blocks in \(877\) ways, the Bell number \(B_7\). [9] With the ordering of the program, no table of the sweep of the dodecahedron contains more than \(731\) states, the finished state included, and the \(30\) tables, one after each step, contain \(9378\) states altogether, instead of \(2^{30}\) sets.

How the Code Works

The C++ program [10] works with sets of edges as bit masks: the edges are numbered from \(0\) to \(29\), and a set of edges is a \(32\)-bit integer. dodecahedron() returns the coordinates of Section 3, and make_graph(points) finds the smallest distance between two points and takes all pairs at that distance as edges. The structure Graph stores for every edge the mask adjacent of the edges that share an endpoint with it, the edge itself included, and connected(selected) tests a set by flooding: starting from the edge of the set with the smallest number, it repeatedly adds the edges of the set that are adjacent to an edge already reached, and the set is connected when every edge has been reached.

rotations(points, graph) builds the rotations as in Section 3. frame(a, b) turns two vertices into three mutually perpendicular unit vectors: the first points towards \(a\), the second lies in the plane through the centre, \(a\) and \(b\), on the side of \(b\), and the third is their cross product. For each of the \(60\) directed edges the function takes the linear map that carries the frame of the first directed edge to the frame of that one; this map is a rotation about the centre, and no other rotation about the centre carries the first directed edge there. The function requires that the map sends every vertex to a vertex, within a tolerance of \(10^{-8}\), and every edge to an edge, stores it as a permutation of the \(30\) edges, and requires the \(60\) permutations to be different.

cycles(permutation) returns the cycles of a rotation as a sorted list of masks, and transform(mask, permutation) applies a rotation to a set of edges. canonical_partition(partition, group) applies every rotation \(h\) to the cycles of a rotation \(g\), which gives the cycles of \(hgh^{-1}\), and takes the smallest of the resulting lists; by Section 4, rotations with the same list keep equally many skeletons. skeletons(graph, group) sorts the rotations into classes by this list, for the dodecahedron four classes of \(1,15,20\) and \(24\) rotations, one for each order, calls fixed_subsets once for each class, multiplies the result by the size of the class, adds everything up, requires the sum to be divisible by the number of rotations and returns the quotient.

fixed_subsets(graph, partition) counts the connected unions of the given cycles. If there are as many cycles as edges, the rotation is the identity, and the function returns connected_subsets(graph). Otherwise it requires at most \(20\) cycles and runs through all non-empty selections of cycles; subsets[mask], the union of the selected cycles, is obtained from the union for the selection without its first cycle by adding that cycle, and each union is tested with connected.

connected_subsets(graph) is the sweep of Sections 6 and 7. sweep_edges produces the ordering of the edges; when the graph is not connected, as many of the small test graphs are, the breadth-first search starts again at the first vertex of the list that has no number yet. last holds for every vertex the step of its last edge. A state is a \(64\)-bit integer with four bits for the label of each frontier vertex, in the order of the list frontier, and the top bit FINISHED; the program requires that the frontier never has more than \(15\) vertices, so that a label never exceeds \(15\). The table current maps states to counts. For each edge, the function determines the indices u and v of its endpoints in the list frontier, appending new vertices to it, and the list keep of the indices that stay. For every state and both decisions it unpacks the labels, applies the edge if it is chosen, and forms two sets of labels: used, the labels present before vertices leave, and retained, those that remain. A label in used but not in retained is a piece that closes; the state is dropped if retained is not empty or more than one piece closes, and becomes FINISHED otherwise. A state that is already FINISHED skips the decision to choose the edge. The remaining labels are renumbered in the order of their first occurrence and packed again, and the count is added to the new state in the table next. The count stored under FINISHED after the last edge is the result.

run_tests, started with --self-test, combines exhaustive comparisons on small graphs and small polyhedra with consistency checks on the dodecahedron. For each of the \(1024\) graphs on five labelled vertices it compares the sweep with brute_connected, which tests every set of edges. For the tetrahedron, the cube and the octahedron it requires \(12\), \(24\) and \(24\) rotations respectively, verifies with check_group that the product of any two rotations is again one of them, compares the sweep with brute_connected and the result of skeletons with brute_skeletons, which replaces every connected set by the smallest of its images under all rotations and counts the different results, and it requires the value \(10\) for the tetrahedron. For the dodecahedron it requires \(20\) vertices, \(30\) edges and \(60\) rotations, the product of any two of which is again one of them, checks that \(1,15,20\) and \(24\) rotations have \(30,16,10\) and \(6\) cycles respectively, compares the result of skeletons, multiplied by \(60\), with the sum of fixed_subsets over all \(60\) rotations taken one by one, and repeats the sweep with the vertices numbered backwards and the list of edges reversed, which leads to another ordering of the edges and must give the same result. Without arguments the program prints the number of different skeletons of the dodecahedron.

The Python and Java versions follow the C++ program function by function, with the same command line and the same self-test. Python represents sets of edges and states by its unbounded integers and permutations by tuples. Java stores sets of edges in int and states in long, where FINISHED is the sign bit, and uses TreeSet and TreeMap with Arrays.compare where the C++ program uses ordered sets and maps of vectors.

Complexity and Verification

For a rotation other than the identity, with \(q\) cycles, fixed_subsets makes \(2^q-1\) tests of connectedness, and each test visits every edge of the set at most once. For the dodecahedron, with one call for each of the three classes, these are \(65\,535+1023+63=66\,621\) tests. The identity is handled by the sweep instead. The sweep processes \(9377\) states, each with at most two decisions: the single state at the start and the states of the \(29\) tables after the steps \(1\) to \(29\). The table after the last step holds only the two states named in Section 6 and is not processed. Yet the identity has more than \(10^9\) sets to consider, far more than all the other rotations together. In general a frontier of \(w\) vertices allows up to \(B_{w+1}+1\) states, the finished one included, and a rotation with \(q\) cycles has \(2^q-1\) non-empty unions, so the method depends on a short frontier and on few cycles; the dodecahedron has both. Measured as the median wall-clock time of five runs of the whole program on an Apple M4 Max, the C++ program built with clang++ -std=c++20 -O3 prints the answer in about \(0.005\) seconds, the Java version, compiled beforehand and run on OpenJDK 17, in about \(0.06\) seconds, and the Python version on CPython 3.11 in about \(0.13\) seconds; their self-tests take about \(0.03\), \(0.12\) and \(1.5\) seconds.

All three programs print the same value and pass their self-tests. Their functions give \(127\) different skeletons for the cube and \(192\) for the octahedron, by Burnside's lemma and by direct listing alike, and the numbers counted by hand in this article agree with them: \(60\) connected sets and \(10\) different skeletons for the tetrahedron, and \(F_5=23\).

A further check, which is not part of the published solutions, uses neither Burnside's lemma nor the sweep. A second program builds the graph of the dodecahedron without coordinates, as the generalised Petersen graph \(G(10,2)\): a closed path through ten vertices, a spoke at each of them, and the ten inner ends of the spokes joined in steps of two. [2] It finds the \(120\) symmetries of this graph by backtracking, and exactly \(60\) of them move the edges in an even number of cycles. By Section 4 every rotation does so, in \(30\), \(16\), \(10\) or \(6\) cycles, and the \(60\) rotations are among the symmetries of the graph; so these \(60\) symmetries are the rotations. The program then goes through all \(2^{30}-1\) non-empty sets of edges, tests each for connectedness by a flood over vertices instead of edges, and counts a connected set if none of its \(60\) images is smaller as a \(30\)-bit number, so that every orbit is counted once, at its smallest element. This direct enumeration agrees with the published programs in the number \(F_1\) of connected non-empty sets, in the number \(K\) of different skeletons, and in the numbers \(F_2\), \(F_3\) and \(F_5\). For the last three it uses that an orbit whose smallest element is kept by \(s\) rotations has \(60/s\) elements, by the relation \(|G|=|G_x|\cdot r\) of Section 2, and that each of them is kept by as many rotations of each order as the smallest one, by the second reason of Section 4. So the orbit contributes \(60/s\) times the number of rotations of order \(k\) that keep its smallest element, and the sum of these contributions over all orbits is \(15F_2\), \(20F_3\) and \(24F_5\) for \(k=2,3,5\). The enumeration also shows how rare symmetry is: only \(7380\) of the \(K\) different skeletons have a symmetry of their own, that is, are kept in each of their positions by some rotation other than the identity, and only one of them, the set of all \(30\) edges, is kept by all sixty. Every different skeleton outside these \(7380\) has \(60\) positions, so \(K\) is only slightly larger than \(F_1/60\).

Two further checks concern the reading of the problem statement and a related polyhedron. Section 2 reads the statement as speaking of rotations of the polyhedron, but a rotation of space can carry a skeleton onto a skeleton without mapping the dodecahedron onto itself; the half-turn about the bisector of the angle between two edges at a vertex, for example, exchanges these two edges. This does not change the number of different skeletons. If a skeleton contains the three edges at some vertex, a rotation of space that carries it onto another skeleton moves this vertex and its three neighbours in the same way as one of the rotations of the dodecahedron, and therefore is that rotation. The other skeletons are the \(125\,370\) paths and the \(1168\) closed paths, and a comparison of all of them shows that whenever a rotation of space carries one of them onto another, a rotation of the dodecahedron does so too. The second check is a test case of the same size for readers who write their own solution: with the twelve vertices of a regular icosahedron, which also has \(30\) edges and \(60\) rotations, the functions of the published program and the direct enumeration both give \(16\,096\,174\) different skeletons.

Footnotes and References

The references below supply background facts. The cycles of the rotations, the numbers counted by hand and the sweep are derived explicitly in this article.

  1. Project Euler 1019 — Dodecahedron Skeleton. The official statement: a skeleton of a polyhedron is a connected, non-empty subset of its edges, two skeletons are the same if they differ only by a rotation in space, the regular tetrahedron has \(10\) different skeletons, and the task is to find the number of different skeletons of the regular dodecahedron.
  2. Wikipedia — Regular dodecahedron. The regular dodecahedron has twelve pentagonal faces, three of which meet at each vertex, thirty edges and twenty vertices. The article gives the vertex coordinates \((\pm1,\pm1,\pm1)\), \((0,\pm\varphi,\pm\tfrac1\varphi)\), \((\pm\tfrac1\varphi,0,\pm\varphi)\) and \((\pm\varphi,\pm\tfrac1\varphi,0)\); the coordinates of Section 3 are these after a quarter turn about the first coordinate axis, \((x,y,z)\mapsto(x,-z,y)\). The article also states that the graph of the dodecahedron can be constructed as the generalised Petersen graph \(G(10,2)\) and that this graph has \(120\) automorphisms, that is, symmetries.
  3. OEIS A287689. The number of non-null connected induced subgraphs of the \(n\)-triangular graph, which by a comment in the entry is also the number of labelled simple graphs with \(n\) vertices whose edge set is connected. The terms for \(n=2,3,4,5\) are \(1,7,60,968\).
  4. OEIS A001349. The number of simple connected graphs on \(n\) unlabelled nodes, \(1,1,1,2,6,21,\dots\) for \(n=0,1,2,\dots\); there are \(1\), \(2\) and \(6\) of them with two, three and four nodes.
  5. Wikipedia — Burnside's lemma. The number of orbits of a finite group acting on a set is the average number of points fixed by an element of the group. The article notes that the result is also called the Cauchy–Frobenius lemma or the orbit-counting theorem, that it was known to Cauchy in 1845 and that Burnside attributed it to Frobenius, and it works out the colourings of the faces of a cube under its \(24\) rotations as an example.
  6. Wikipedia — Euler's rotation theorem. In three-dimensional space, every displacement of a rigid body that leaves one of its points fixed is a single rotation about an axis through that point. The article concludes that the composition of two rotations is again a rotation and that the rotations form a group; here this conclusion is used for rotations about axes through one common point, the centre of the polyhedron.
  7. Wikipedia — Icosahedral symmetry. The rotation group of the regular dodecahedron and of the regular icosahedron has \(60\) elements and is isomorphic to the alternating group \(A_5\); the full symmetry group, which also contains the reflection in the centre, has \(120\) elements. Besides the identity, the article lists \(12\) rotations by \(\pm72^\circ\) and \(12\) by \(\pm144^\circ\), all of order \(5\), about the \(6\) axes through the face centres of the dodecahedron, \(20\) rotations of order \(3\) about the \(10\) axes through its vertices and \(15\) half-turns about the \(15\) axes through the midpoints of its edges.
  8. Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato — Frontier-based Search for Enumerating All Constrained Subgraphs with Compressed Representation, TCS Technical Report TCS-TR-A-14-76, Hokkaido University, 2014; the journal version appeared in IEICE Transactions on Fundamentals E100-A (2017), 1773–1784. The report processes the edges of a graph in a fixed ordering, calls the vertices that are incident to both a processed and an unprocessed edge the frontier, stores for every frontier vertex the identifier of its connected component, treats partial subgraphs with equal values on the frontier as identical, and observes that a component with no vertex remaining on the frontier can no longer be connected to the others.
  9. OEIS A000110. The Bell numbers, the numbers of ways to partition a set of \(n\) labelled elements: \(1,1,2,5,15,52,203,877,\dots\) for \(n=0,1,2,\dots\), so that \(B_7=877\).
  10. C++ — Euler1019.cpp. The linked immutable C++ revision contains make_graph, rotations, cycles, canonical_partition, fixed_subsets, connected_subsets, skeletons and the checks run by --self-test. It is the implementation record for this article.

Problem 1019 source code

C++

#include <algorithm>
#include <array>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <set>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

namespace {

using u32 = std::uint32_t;
using u64 = std::uint64_t;
using Edge = std::pair<unsigned, unsigned>;
using Permutation = std::vector<unsigned>;
using Partition = std::vector<u32>;
constexpr u64 FINISHED = u64{1} << 63;
constexpr double EPSILON = 1e-8;

void require(const bool condition, const char* description) {
    if (!condition) throw std::runtime_error(std::string("Check failed: ") + description);
}

unsigned first_bit(const u32 mask) {
    return static_cast<unsigned>(__builtin_ctz(mask));
}

struct Point {
    double x, y, z;

    Point operator+(const Point& other) const { return {x + other.x, y + other.y, z + other.z}; }
    Point operator-(const Point& other) const { return {x - other.x, y - other.y, z - other.z}; }
    Point operator*(const double scale) const { return {x * scale, y * scale, z * scale}; }
};

double dot(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

Point cross(const Point& a, const Point& b) {
    return {a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x};
}

Point unit(const Point& point) {
    return point * (1 / std::sqrt(dot(point, point)));
}

std::array<Point, 3> frame(const Point& a, const Point& b) {
    const Point x = unit(a);
    const Point y = unit(b - x * dot(x, b));
    return {x, y, cross(x, y)};
}

std::vector<Point> cube() {
    std::vector<Point> result;
    for (const double x : {-1.0, 1.0}) {
        for (const double y : {-1.0, 1.0}) {
            for (const double z : {-1.0, 1.0}) result.push_back({x, y, z});
        }
    }
    return result;
}

std::vector<Point> dodecahedron() {
    auto result = cube();
    const double phi = (1 + std::sqrt(5.0)) / 2;
    for (const double a : {-1.0, 1.0}) {
        for (const double b : {-1.0, 1.0}) {
            result.push_back({0, a / phi, b * phi});
            result.push_back({a / phi, b * phi, 0});
            result.push_back({b * phi, 0, a / phi});
        }
    }
    return result;
}

struct Graph {
    unsigned vertices;
    std::vector<Edge> edges;
    std::vector<u32> adjacent;

    Graph(const unsigned size, std::vector<Edge> pairs) : vertices(size), edges(std::move(pairs)) {
        require(vertices <= 20 && edges.size() <= 30, "graph fits the masks");
        adjacent.resize(edges.size());
        for (unsigned i = 0; i < edges.size(); ++i) {
            const auto [a, b] = edges[i];
            require(a < vertices && b < vertices && a != b, "valid edge endpoints");
            for (unsigned j = 0; j < edges.size(); ++j) {
                const auto [c, d] = edges[j];
                if (a == c || a == d || b == c || b == d) adjacent[i] |= u32{1} << j;
            }
        }
    }

    bool connected(const u32 selected) const {
        if (selected == 0) return false;
        u32 reached = u32{1} << first_bit(selected);
        u32 pending = reached;
        while (pending != 0) {
            const unsigned edge = first_bit(pending);
            pending &= pending - 1;
            const u32 next = adjacent[edge] & selected & ~reached;
            reached |= next;
            pending |= next;
        }
        return reached == selected;
    }
};

Graph make_graph(const std::vector<Point>& points) {
    double distance = std::numeric_limits<double>::max();
    for (unsigned i = 0; i < points.size(); ++i) {
        for (unsigned j = i + 1; j < points.size(); ++j) {
            const Point delta = points[i] - points[j];
            distance = std::min(distance, dot(delta, delta));
        }
    }
    std::vector<Edge> edges;
    for (unsigned i = 0; i < points.size(); ++i) {
        for (unsigned j = i + 1; j < points.size(); ++j) {
            const Point delta = points[i] - points[j];
            if (std::abs(dot(delta, delta) - distance) < EPSILON) edges.emplace_back(i, j);
        }
    }
    return Graph(static_cast<unsigned>(points.size()), std::move(edges));
}

std::vector<Permutation> rotations(const std::vector<Point>& points, const Graph& graph) {
    const auto [a, b] = graph.edges.front();
    const auto source = frame(points[a], points[b]);
    std::set<Permutation> unique;
    for (const auto& edge : graph.edges) {
        for (unsigned reverse = 0; reverse < 2; ++reverse) {
            const auto target = reverse == 0 ? frame(points[edge.first], points[edge.second])
                                             : frame(points[edge.second], points[edge.first]);
            Permutation vertices;
            for (const Point& point : points) {
                const Point mapped = target[0] * dot(source[0], point)
                                   + target[1] * dot(source[1], point)
                                   + target[2] * dot(source[2], point);
                unsigned match = graph.vertices;
                for (unsigned i = 0; i < points.size(); ++i) {
                    const Point delta = mapped - points[i];
                    if (dot(delta, delta) < EPSILON * EPSILON) {
                        require(match == graph.vertices, "unique rotated vertex");
                        match = i;
                    }
                }
                require(match < graph.vertices, "rotation preserves the vertex set");
                vertices.push_back(match);
            }
            auto sorted = vertices;
            std::sort(sorted.begin(), sorted.end());
            for (unsigned i = 0; i < sorted.size(); ++i) require(sorted[i] == i, "vertex permutation");
            Permutation permutation;
            for (const auto& [u, v] : graph.edges) {
                const Edge mapped = std::minmax(vertices[u], vertices[v]);
                const auto found = std::find(graph.edges.begin(), graph.edges.end(), mapped);
                require(found != graph.edges.end(), "rotation preserves edges");
                permutation.push_back(static_cast<unsigned>(found - graph.edges.begin()));
            }
            require(unique.insert(permutation).second, "distinct directed edges give distinct rotations");
        }
    }
    return {unique.begin(), unique.end()};
}

std::vector<Edge> sweep_edges(const Graph& graph) {
    std::vector<unsigned> order, rank(graph.vertices, graph.vertices);
    for (unsigned start = 0; start < graph.vertices; ++start) {
        if (rank[start] != graph.vertices) continue;
        rank[start] = static_cast<unsigned>(order.size());
        order.push_back(start);
        for (std::size_t i = rank[start]; i < order.size(); ++i) {
            for (const auto& [u, v] : graph.edges) {
                if (u != order[i] && v != order[i]) continue;
                const unsigned next = u == order[i] ? v : u;
                if (rank[next] == graph.vertices) {
                    rank[next] = static_cast<unsigned>(order.size());
                    order.push_back(next);
                }
            }
        }
    }
    auto result = graph.edges;
    const auto key = [&](const Edge& edge) -> Edge { return std::minmax(rank[edge.first], rank[edge.second]); };
    std::sort(result.begin(), result.end(), [&](const Edge& a, const Edge& b) { return key(a) < key(b); });
    return result;
}

u64 connected_subsets(const Graph& graph) {
    const auto edges = sweep_edges(graph);
    std::vector<unsigned> last(graph.vertices), frontier;
    for (unsigned i = 0; i < edges.size(); ++i) {
        last[edges[i].first] = last[edges[i].second] = i;
    }
    std::unordered_map<u64, u64> current{{0, 1}}, next;
    for (unsigned step = 0; step < edges.size(); ++step) {
        const unsigned previous_size = static_cast<unsigned>(frontier.size());
        const auto position = [&](const unsigned vertex) {
            const auto found = std::find(frontier.begin(), frontier.end(), vertex);
            if (found != frontier.end()) return static_cast<unsigned>(found - frontier.begin());
            frontier.push_back(vertex);
            return static_cast<unsigned>(frontier.size() - 1);
        };
        const unsigned u = position(edges[step].first), v = position(edges[step].second);
        require(frontier.size() <= 15, "frontier fits four-bit component labels");
        std::vector<unsigned> keep;
        for (unsigned i = 0; i < frontier.size(); ++i) {
            if (last[frontier[i]] > step) keep.push_back(i);
        }
        next.clear();
        next.reserve(current.size() * 2);
        for (const auto& [state, count] : current) {
            for (unsigned selected = 0; selected < 2; ++selected) {
                if (selected != 0 && (state & FINISHED) != 0) continue;
                std::array<unsigned, 15> labels{};
                unsigned maximum = 0;
                for (unsigned i = 0; i < previous_size; ++i) {
                    labels[i] = static_cast<unsigned>((state >> (4 * i)) & 15);
                    maximum = std::max(maximum, labels[i]);
                }
                if (selected != 0) {
                    if (labels[u] == 0 && labels[v] == 0) {
                        labels[u] = labels[v] = maximum + 1;
                    } else if (labels[u] == 0) {
                        labels[u] = labels[v];
                    } else if (labels[v] == 0) {
                        labels[v] = labels[u];
                    } else {
                        const unsigned from = labels[v], to = labels[u];
                        for (unsigned& label : labels) {
                            if (label == from) label = to;
                        }
                    }
                }
                u32 used = 0, retained = 0;
                for (const unsigned label : labels) used |= u32{1} << label;
                for (const unsigned i : keep) retained |= u32{1} << labels[i];
                used &= ~u32{1};
                retained &= ~u32{1};
                const u32 closed = used & ~retained;
                u64 encoded = state & FINISHED;
                if (closed != 0) {
                    // A component leaving the frontier can never connect to a later edge.
                    if (retained != 0 || (closed & (closed - 1)) != 0) continue;
                    encoded = FINISHED;
                }
                std::array<unsigned, 16> canonical{};
                unsigned next_label = 1;
                for (unsigned i = 0; i < keep.size(); ++i) {
                    const unsigned label = labels[keep[i]];
                    if (label != 0 && canonical[label] == 0) canonical[label] = next_label++;
                    encoded |= u64{canonical[label]} << (4 * i);
                }
                next[encoded] += count;
            }
        }
        std::vector<unsigned> remaining;
        for (const unsigned i : keep) remaining.push_back(frontier[i]);
        frontier.swap(remaining);
        current.swap(next);
    }
    const auto found = current.find(FINISHED);
    return found == current.end() ? 0 : found->second;
}

u32 transform(u32 mask, const Permutation& permutation) {
    u32 result = 0;
    while (mask != 0) {
        result |= u32{1} << permutation[first_bit(mask)];
        mask &= mask - 1;
    }
    return result;
}

Partition cycles(const Permutation& permutation) {
    Partition result;
    u32 visited = 0;
    for (unsigned i = 0; i < permutation.size(); ++i) {
        if ((visited & (u32{1} << i)) != 0) continue;
        u32 cycle = 0;
        unsigned j = i;
        do {
            cycle |= u32{1} << j;
            j = permutation[j];
        } while (j != i);
        visited |= cycle;
        result.push_back(cycle);
    }
    std::sort(result.begin(), result.end());
    return result;
}

Partition canonical_partition(const Partition& partition, const std::vector<Permutation>& group) {
    Partition result = partition;
    for (const auto& permutation : group) {
        Partition candidate;
        for (const u32 cycle : partition) candidate.push_back(transform(cycle, permutation));
        std::sort(candidate.begin(), candidate.end());
        result = std::min(result, candidate);
    }
    return result;
}

u64 fixed_subsets(const Graph& graph, const Partition& partition) {
    if (partition.size() == graph.edges.size()) return connected_subsets(graph);
    require(partition.size() <= 20, "small nonidentity cycle enumeration");
    std::vector<u32> subsets(std::size_t{1} << partition.size());
    u64 result = 0;
    for (u32 mask = 1; mask < subsets.size(); ++mask) {
        subsets[mask] = subsets[mask & (mask - 1)] | partition[first_bit(mask)];
        result += graph.connected(subsets[mask]);
    }
    return result;
}

u64 skeletons(const Graph& graph, const std::vector<Permutation>& group) {
    std::map<Partition, unsigned> classes;
    for (const auto& permutation : group) ++classes[canonical_partition(cycles(permutation), group)];
    u64 total = 0;
    for (const auto& [partition, multiplicity] : classes) total += multiplicity * fixed_subsets(graph, partition);
    require(total % group.size() == 0, "integral Burnside average");
    return total / group.size();
}

u64 brute_connected(const Graph& graph) {
    u64 result = 0;
    for (u32 mask = 1; mask < (u32{1} << graph.edges.size()); ++mask) result += graph.connected(mask);
    return result;
}

u64 brute_skeletons(const Graph& graph, const std::vector<Permutation>& group) {
    std::set<u32> representatives;
    for (u32 mask = 1; mask < (u32{1} << graph.edges.size()); ++mask) {
        if (!graph.connected(mask)) continue;
        u32 representative = mask;
        for (const auto& permutation : group) representative = std::min(representative, transform(mask, permutation));
        representatives.insert(representative);
    }
    return representatives.size();
}

void check_group(const std::vector<Permutation>& group) {
    const std::set<Permutation> elements(group.begin(), group.end());
    for (const auto& a : group) {
        for (const auto& b : group) {
            Permutation product(a.size());
            for (unsigned i = 0; i < a.size(); ++i) product[i] = a[b[i]];
            require(elements.count(product) == 1, "rotation group closure");
        }
    }
}

void run_tests() {
    std::vector<Edge> complete;
    for (unsigned u = 0; u < 5; ++u) {
        for (unsigned v = u + 1; v < 5; ++v) complete.emplace_back(u, v);
    }
    for (u32 mask = 0; mask < (u32{1} << complete.size()); ++mask) {
        std::vector<Edge> edges;
        for (unsigned i = 0; i < complete.size(); ++i) {
            if ((mask & (u32{1} << i)) != 0) edges.push_back(complete[i]);
        }
        const Graph graph(5, std::move(edges));
        require(connected_subsets(graph) == brute_connected(graph), "all 1024 labelled graphs on five vertices");
    }
    const std::vector<Point> tetrahedron{{1, 1, 1}, {1, -1, -1}, {-1, 1, -1}, {-1, -1, 1}};
    const std::vector<Point> octahedron{{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};
    for (const auto& points : {tetrahedron, cube(), octahedron}) {
        const Graph graph = make_graph(points);
        const auto group = rotations(points, graph);
        require(group.size() == (points.size() == 4 ? 12 : 24), "small rotation group size");
        check_group(group);
        require(connected_subsets(graph) == brute_connected(graph), "small polyhedron connected subsets");
        const u64 answer = skeletons(graph, group);
        require(answer == brute_skeletons(graph, group), "direct small polyhedron orbit enumeration");
        if (points.size() == 4) require(answer == 10, "given tetrahedron example");
    }
    const auto points = dodecahedron();
    const Graph graph = make_graph(points);
    const auto group = rotations(points, graph);
    require(graph.vertices == 20 && graph.edges.size() == 30 && group.size() == 60, "dodecahedron dimensions");
    check_group(group);
    std::map<unsigned, unsigned> cycle_counts;
    u64 total = 0;
    for (const auto& permutation : group) {
        const auto partition = cycles(permutation);
        ++cycle_counts[static_cast<unsigned>(partition.size())];
        total += fixed_subsets(graph, partition);
    }
    require(cycle_counts == std::map<unsigned, unsigned>{{6, 24}, {10, 20}, {16, 15}, {30, 1}}, "rotation cycle types");
    require(total == group.size() * skeletons(graph, group), "all 60 rotations versus grouped enumeration");
    auto relabelled = graph.edges;
    for (auto& [u, v] : relabelled) {
        u = graph.vertices - 1 - u;
        v = graph.vertices - 1 - v;
    }
    std::reverse(relabelled.begin(), relabelled.end());
    require(connected_subsets(Graph(graph.vertices, std::move(relabelled))) == connected_subsets(graph),
            "independent frontier order");
    std::cout << "All checks passed: 1024 small graphs, tetrahedron example, direct tetrahedron/cube/octahedron "
                 "orbits, rotation groups, all 60 dodecahedron rotations, and frontier reordering.\n";
}

}

int main(int argc, char* argv[]) {
    try {
        if (argc == 2 && std::string(argv[1]) == "--self-test") {
            run_tests();
        } else {
            if (argc != 1) throw std::invalid_argument("Usage: Euler1019 [--self-test]");
            const auto points = dodecahedron();
            const Graph graph = make_graph(points);
            const auto group = rotations(points, graph);
            require(graph.vertices == 20 && graph.edges.size() == 30 && group.size() == 60, "dodecahedron dimensions");
            std::cout << skeletons(graph, group) << '\n';
        }
    } catch (const std::exception& error) {
        std::cerr << error.what() << '\n';
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

Python

#!/usr/bin/env python3
"""Project Euler Problem 1019 - Dodecahedron Skeleton."""

import math
import sys

FINISHED = 1 << 63
EPSILON = 1e-8


def require(condition, description):
    if not condition:
        raise RuntimeError("Check failed: " + description)


def first_bit(mask):
    return (mask & -mask).bit_length() - 1


# Points are (x, y, z) tuples.
def plus(a, b):
    return (a[0] + b[0], a[1] + b[1], a[2] + b[2])


def minus(a, b):
    return (a[0] - b[0], a[1] - b[1], a[2] - b[2])


def times(a, scale):
    return (a[0] * scale, a[1] * scale, a[2] * scale)


def dot(a, b):
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


def cross(a, b):
    return (a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0])


def unit(point):
    # A zero vector yields infinite or undefined coordinates, as in the C++ arithmetic, not an exception.
    length = math.sqrt(dot(point, point))
    return times(point, 1 / length if length != 0 else math.inf)


def frame(a, b):
    x = unit(a)
    y = unit(minus(b, times(x, dot(x, b))))
    return (x, y, cross(x, y))


def cube():
    return [(x, y, z) for x in (-1.0, 1.0) for y in (-1.0, 1.0) for z in (-1.0, 1.0)]


def dodecahedron():
    result = cube()
    phi = (1 + math.sqrt(5.0)) / 2
    for a in (-1.0, 1.0):
        for b in (-1.0, 1.0):
            result.append((0.0, a / phi, b * phi))
            result.append((a / phi, b * phi, 0.0))
            result.append((b * phi, 0.0, a / phi))
    return result


class Graph:
    def __init__(self, size, pairs):
        self.vertices = size
        self.edges = list(pairs)
        require(self.vertices <= 20 and len(self.edges) <= 30, "graph fits the masks")
        self.adjacent = [0] * len(self.edges)
        for i, (a, b) in enumerate(self.edges):
            require(0 <= a < self.vertices and 0 <= b < self.vertices and a != b, "valid edge endpoints")
            for j, (c, d) in enumerate(self.edges):
                if a == c or a == d or b == c or b == d:
                    self.adjacent[i] |= 1 << j

    def connected(self, selected):
        if selected == 0:
            return False
        adjacent = self.adjacent
        reached = selected & -selected
        pending = reached
        while pending != 0:
            edge = (pending & -pending).bit_length() - 1
            pending &= pending - 1
            following = adjacent[edge] & selected & ~reached
            reached |= following
            pending |= following
        return reached == selected


def make_graph(points):
    distance = sys.float_info.max
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            delta = minus(points[i], points[j])
            distance = min(distance, dot(delta, delta))
    edges = []
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            delta = minus(points[i], points[j])
            if abs(dot(delta, delta) - distance) < EPSILON:
                edges.append((i, j))
    return Graph(len(points), edges)


def rotations(points, graph):
    a, b = graph.edges[0]
    source = frame(points[a], points[b])
    unique = set()
    for edge in graph.edges:
        for reverse in range(2):
            target = (frame(points[edge[0]], points[edge[1]]) if reverse == 0
                      else frame(points[edge[1]], points[edge[0]]))
            vertices = []
            for point in points:
                mapped = plus(plus(times(target[0], dot(source[0], point)),
                                   times(target[1], dot(source[1], point))),
                              times(target[2], dot(source[2], point)))
                match = graph.vertices
                for i in range(len(points)):
                    delta = minus(mapped, points[i])
                    if dot(delta, delta) < EPSILON * EPSILON:
                        require(match == graph.vertices, "unique rotated vertex")
                        match = i
                require(match < graph.vertices, "rotation preserves the vertex set")
                vertices.append(match)
            require(sorted(vertices) == list(range(len(vertices))), "vertex permutation")
            permutation = []
            for u, v in graph.edges:
                image = (min(vertices[u], vertices[v]), max(vertices[u], vertices[v]))
                require(image in graph.edges, "rotation preserves edges")
                permutation.append(graph.edges.index(image))
            permutation = tuple(permutation)
            require(permutation not in unique, "distinct directed edges give distinct rotations")
            unique.add(permutation)
    return sorted(unique)


def sweep_edges(graph):
    order = []
    rank = [graph.vertices] * graph.vertices
    for start in range(graph.vertices):
        if rank[start] != graph.vertices:
            continue
        rank[start] = len(order)
        order.append(start)
        i = rank[start]
        while i < len(order):
            for u, v in graph.edges:
                if u != order[i] and v != order[i]:
                    continue
                following = v if u == order[i] else u
                if rank[following] == graph.vertices:
                    rank[following] = len(order)
                    order.append(following)
            i += 1

    def key(edge):
        first, second = rank[edge[0]], rank[edge[1]]
        return (min(first, second), max(first, second))

    return sorted(graph.edges, key=key)


def connected_subsets(graph):
    edges = sweep_edges(graph)
    last = [0] * graph.vertices
    for i, (a, b) in enumerate(edges):
        last[a] = last[b] = i
    frontier = []
    current = {0: 1}
    for step, (a, b) in enumerate(edges):
        previous_size = len(frontier)

        def position(vertex):
            if vertex in frontier:
                return frontier.index(vertex)
            frontier.append(vertex)
            return len(frontier) - 1

        u = position(a)
        v = position(b)
        require(len(frontier) <= 15, "frontier fits four-bit component labels")
        keep = [i for i in range(len(frontier)) if last[frontier[i]] > step]
        following = {}
        for state, count in current.items():
            for selected in range(2):
                if selected != 0 and (state & FINISHED) != 0:
                    continue
                labels = [(state >> (4 * i)) & 15 for i in range(previous_size)]
                maximum = max(labels, default=0)
                labels += [0] * (len(frontier) - previous_size)
                if selected != 0:
                    if labels[u] == 0 and labels[v] == 0:
                        labels[u] = labels[v] = maximum + 1
                    elif labels[u] == 0:
                        labels[u] = labels[v]
                    elif labels[v] == 0:
                        labels[v] = labels[u]
                    else:
                        origin, target = labels[v], labels[u]
                        labels = [target if label == origin else label for label in labels]
                used = 0
                for label in labels:
                    used |= 1 << label
                retained = 0
                for i in keep:
                    retained |= 1 << labels[i]
                used &= ~1
                retained &= ~1
                closed = used & ~retained
                encoded = state & FINISHED
                if closed != 0:
                    # A component leaving the frontier can never connect to a later edge.
                    if retained != 0 or (closed & (closed - 1)) != 0:
                        continue
                    encoded = FINISHED
                canonical = [0] * 16
                next_label = 1
                for i, kept in enumerate(keep):
                    label = labels[kept]
                    if label != 0 and canonical[label] == 0:
                        canonical[label] = next_label
                        next_label += 1
                    encoded |= canonical[label] << (4 * i)
                following[encoded] = following.get(encoded, 0) + count
        frontier = [frontier[i] for i in keep]
        current = following
    return current.get(FINISHED, 0)


def transform(mask, permutation):
    result = 0
    while mask != 0:
        result |= 1 << permutation[(mask & -mask).bit_length() - 1]
        mask &= mask - 1
    return result


def cycles(permutation):
    result = []
    visited = 0
    for i in range(len(permutation)):
        if (visited & (1 << i)) != 0:
            continue
        cycle = 0
        j = i
        while True:
            cycle |= 1 << j
            j = permutation[j]
            if j == i:
                break
        visited |= cycle
        result.append(cycle)
    result.sort()
    return result


def canonical_partition(partition, group):
    result = partition
    for permutation in group:
        candidate = sorted(transform(cycle, permutation) for cycle in partition)
        result = min(result, candidate)
    return result


def fixed_subsets(graph, partition):
    if len(partition) == len(graph.edges):
        return connected_subsets(graph)
    require(len(partition) <= 20, "small nonidentity cycle enumeration")
    subsets = [0] * (1 << len(partition))
    result = 0
    for mask in range(1, len(subsets)):
        subsets[mask] = subsets[mask & (mask - 1)] | partition[first_bit(mask)]
        result += graph.connected(subsets[mask])
    return result


def skeletons(graph, group):
    classes = {}
    for permutation in group:
        partition = tuple(canonical_partition(cycles(permutation), group))
        classes[partition] = classes.get(partition, 0) + 1
    total = 0
    for partition in sorted(classes):
        total += classes[partition] * fixed_subsets(graph, list(partition))
    require(total % len(group) == 0, "integral Burnside average")
    return total // len(group)


def brute_connected(graph):
    result = 0
    for mask in range(1, 1 << len(graph.edges)):
        result += graph.connected(mask)
    return result


def brute_skeletons(graph, group):
    representatives = set()
    for mask in range(1, 1 << len(graph.edges)):
        if not graph.connected(mask):
            continue
        representative = mask
        for permutation in group:
            representative = min(representative, transform(mask, permutation))
        representatives.add(representative)
    return len(representatives)


def check_group(group):
    elements = set(group)
    for a in group:
        for b in group:
            product = tuple(a[b[i]] for i in range(len(a)))
            require(product in elements, "rotation group closure")


def run_tests():
    complete = [(u, v) for u in range(5) for v in range(u + 1, 5)]
    for mask in range(1 << len(complete)):
        edges = [complete[i] for i in range(len(complete)) if (mask & (1 << i)) != 0]
        graph = Graph(5, edges)
        require(connected_subsets(graph) == brute_connected(graph), "all 1024 labelled graphs on five vertices")
    tetrahedron = [(1.0, 1.0, 1.0), (1.0, -1.0, -1.0), (-1.0, 1.0, -1.0), (-1.0, -1.0, 1.0)]
    octahedron = [(1.0, 0.0, 0.0), (-1.0, 0.0, 0.0), (0.0, 1.0, 0.0),
                  (0.0, -1.0, 0.0), (0.0, 0.0, 1.0), (0.0, 0.0, -1.0)]
    for points in (tetrahedron, cube(), octahedron):
        graph = make_graph(points)
        group = rotations(points, graph)
        require(len(group) == (12 if len(points) == 4 else 24), "small rotation group size")
        check_group(group)
        require(connected_subsets(graph) == brute_connected(graph), "small polyhedron connected subsets")
        answer = skeletons(graph, group)
        require(answer == brute_skeletons(graph, group), "direct small polyhedron orbit enumeration")
        if len(points) == 4:
            require(answer == 10, "given tetrahedron example")
    points = dodecahedron()
    graph = make_graph(points)
    group = rotations(points, graph)
    require(graph.vertices == 20 and len(graph.edges) == 30 and len(group) == 60, "dodecahedron dimensions")
    check_group(group)
    cycle_counts = {}
    total = 0
    for permutation in group:
        partition = cycles(permutation)
        cycle_counts[len(partition)] = cycle_counts.get(len(partition), 0) + 1
        total += fixed_subsets(graph, partition)
    require(cycle_counts == {6: 24, 10: 20, 16: 15, 30: 1}, "rotation cycle types")
    require(total == len(group) * skeletons(graph, group), "all 60 rotations versus grouped enumeration")
    relabelled = [(graph.vertices - 1 - u, graph.vertices - 1 - v) for u, v in graph.edges]
    relabelled.reverse()
    require(connected_subsets(Graph(graph.vertices, relabelled)) == connected_subsets(graph),
            "independent frontier order")
    print("All checks passed: 1024 small graphs, tetrahedron example, direct tetrahedron/cube/octahedron "
          "orbits, rotation groups, all 60 dodecahedron rotations, and frontier reordering.")


def main(argv):
    try:
        if len(argv) == 2 and argv[1] == "--self-test":
            run_tests()
        else:
            if len(argv) != 1:
                raise ValueError("Usage: Euler1019.py [--self-test]")
            points = dodecahedron()
            graph = make_graph(points)
            group = rotations(points, graph)
            require(graph.vertices == 20 and len(graph.edges) == 30 and len(group) == 60, "dodecahedron dimensions")
            print(skeletons(graph, group))
    except (ValueError, RuntimeError) as error:
        print(error, file=sys.stderr)
        return 1
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv))

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;

public class Euler1019 {
    // Edge sets are bit masks in an int (at most 30 edges), frontier states are packed into a long
    // exactly as in the C++ program: four bits per frontier position and the top bit for FINISHED.
    private static final long FINISHED = 1L << 63;
    private static final double EPSILON = 1e-8;

    private static void require(boolean condition, String description) {
        if (!condition) throw new IllegalStateException("Check failed: " + description);
    }

    static int firstBit(int mask) {
        return Integer.numberOfTrailingZeros(mask);
    }

    static final class Point {
        final double x, y, z;

        Point(double x, double y, double z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        Point plus(Point other) { return new Point(x + other.x, y + other.y, z + other.z); }
        Point minus(Point other) { return new Point(x - other.x, y - other.y, z - other.z); }
        Point times(double scale) { return new Point(x * scale, y * scale, z * scale); }
    }

    static double dot(Point a, Point b) {
        return a.x * b.x + a.y * b.y + a.z * b.z;
    }

    static Point cross(Point a, Point b) {
        return new Point(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
    }

    static Point unit(Point point) {
        return point.times(1 / Math.sqrt(dot(point, point)));
    }

    static Point[] frame(Point a, Point b) {
        Point x = unit(a);
        Point y = unit(b.minus(x.times(dot(x, b))));
        return new Point[] {x, y, cross(x, y)};
    }

    static List<Point> cube() {
        List<Point> result = new ArrayList<>();
        for (double x : new double[] {-1.0, 1.0}) {
            for (double y : new double[] {-1.0, 1.0}) {
                for (double z : new double[] {-1.0, 1.0}) result.add(new Point(x, y, z));
            }
        }
        return result;
    }

    static List<Point> dodecahedron() {
        List<Point> result = cube();
        double phi = (1 + Math.sqrt(5.0)) / 2;
        for (double a : new double[] {-1.0, 1.0}) {
            for (double b : new double[] {-1.0, 1.0}) {
                result.add(new Point(0, a / phi, b * phi));
                result.add(new Point(a / phi, b * phi, 0));
                result.add(new Point(b * phi, 0, a / phi));
            }
        }
        return result;
    }

    static final class Graph {
        final int vertices;
        final int[][] edges;
        final int[] adjacent;

        Graph(int size, List<int[]> pairs) {
            vertices = size;
            edges = pairs.toArray(new int[0][]);
            require(vertices <= 20 && edges.length <= 30, "graph fits the masks");
            adjacent = new int[edges.length];
            for (int i = 0; i < edges.length; ++i) {
                int a = edges[i][0], b = edges[i][1];
                require(a >= 0 && a < vertices && b >= 0 && b < vertices && a != b, "valid edge endpoints");
                for (int j = 0; j < edges.length; ++j) {
                    int c = edges[j][0], d = edges[j][1];
                    if (a == c || a == d || b == c || b == d) adjacent[i] |= 1 << j;
                }
            }
        }

        boolean connected(int selected) {
            if (selected == 0) return false;
            int reached = 1 << firstBit(selected);
            int pending = reached;
            while (pending != 0) {
                int edge = firstBit(pending);
                pending &= pending - 1;
                int next = adjacent[edge] & selected & ~reached;
                reached |= next;
                pending |= next;
            }
            return reached == selected;
        }
    }

    static Graph makeGraph(List<Point> points) {
        double distance = Double.MAX_VALUE;
        for (int i = 0; i < points.size(); ++i) {
            for (int j = i + 1; j < points.size(); ++j) {
                Point delta = points.get(i).minus(points.get(j));
                distance = Math.min(distance, dot(delta, delta));
            }
        }
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < points.size(); ++i) {
            for (int j = i + 1; j < points.size(); ++j) {
                Point delta = points.get(i).minus(points.get(j));
                if (Math.abs(dot(delta, delta) - distance) < EPSILON) edges.add(new int[] {i, j});
            }
        }
        return new Graph(points.size(), edges);
    }

    // Permutations and partitions are int arrays; Arrays.compare orders them as std::vector does.
    static List<int[]> rotations(List<Point> points, Graph graph) {
        Point[] source = frame(points.get(graph.edges[0][0]), points.get(graph.edges[0][1]));
        TreeSet<int[]> unique = new TreeSet<>(Arrays::compare);
        for (int[] edge : graph.edges) {
            for (int reverse = 0; reverse < 2; ++reverse) {
                Point[] target = reverse == 0 ? frame(points.get(edge[0]), points.get(edge[1]))
                                              : frame(points.get(edge[1]), points.get(edge[0]));
                int[] vertices = new int[points.size()];
                for (int index = 0; index < points.size(); ++index) {
                    Point point = points.get(index);
                    Point mapped = target[0].times(dot(source[0], point))
                            .plus(target[1].times(dot(source[1], point)))
                            .plus(target[2].times(dot(source[2], point)));
                    int match = graph.vertices;
                    for (int i = 0; i < points.size(); ++i) {
                        Point delta = mapped.minus(points.get(i));
                        if (dot(delta, delta) < EPSILON * EPSILON) {
                            require(match == graph.vertices, "unique rotated vertex");
                            match = i;
                        }
                    }
                    require(match < graph.vertices, "rotation preserves the vertex set");
                    vertices[index] = match;
                }
                int[] sorted = vertices.clone();
                Arrays.sort(sorted);
                for (int i = 0; i < sorted.length; ++i) require(sorted[i] == i, "vertex permutation");
                int[] permutation = new int[graph.edges.length];
                for (int i = 0; i < graph.edges.length; ++i) {
                    int u = vertices[graph.edges[i][0]], v = vertices[graph.edges[i][1]];
                    int first = Math.min(u, v), second = Math.max(u, v);
                    int found = 0;
                    while (found < graph.edges.length
                            && (graph.edges[found][0] != first || graph.edges[found][1] != second)) {
                        ++found;
                    }
                    require(found < graph.edges.length, "rotation preserves edges");
                    permutation[i] = found;
                }
                require(unique.add(permutation), "distinct directed edges give distinct rotations");
            }
        }
        return new ArrayList<>(unique);
    }

    static int[][] sweepEdges(Graph graph) {
        int[] order = new int[graph.vertices];
        int[] rank = new int[graph.vertices];
        Arrays.fill(rank, graph.vertices);
        int size = 0;
        for (int start = 0; start < graph.vertices; ++start) {
            if (rank[start] != graph.vertices) continue;
            rank[start] = size;
            order[size++] = start;
            for (int i = rank[start]; i < size; ++i) {
                for (int[] edge : graph.edges) {
                    if (edge[0] != order[i] && edge[1] != order[i]) continue;
                    int next = edge[0] == order[i] ? edge[1] : edge[0];
                    if (rank[next] == graph.vertices) {
                        rank[next] = size;
                        order[size++] = next;
                    }
                }
            }
        }
        int[][] result = graph.edges.clone();
        Arrays.sort(result, (a, b) -> {
            int lowA = Math.min(rank[a[0]], rank[a[1]]), lowB = Math.min(rank[b[0]], rank[b[1]]);
            if (lowA != lowB) return Integer.compare(lowA, lowB);
            return Integer.compare(Math.max(rank[a[0]], rank[a[1]]), Math.max(rank[b[0]], rank[b[1]]));
        });
        return result;
    }

    private static int position(List<Integer> frontier, int vertex) {
        int found = frontier.indexOf(vertex);
        if (found >= 0) return found;
        frontier.add(vertex);
        return frontier.size() - 1;
    }

    static long connectedSubsets(Graph graph) {
        int[][] edges = sweepEdges(graph);
        int[] last = new int[graph.vertices];
        for (int i = 0; i < edges.length; ++i) {
            last[edges[i][0]] = last[edges[i][1]] = i;
        }
        List<Integer> frontier = new ArrayList<>();
        Map<Long, Long> current = new HashMap<>();
        current.put(0L, 1L);
        for (int step = 0; step < edges.length; ++step) {
            int previousSize = frontier.size();
            int u = position(frontier, edges[step][0]), v = position(frontier, edges[step][1]);
            require(frontier.size() <= 15, "frontier fits four-bit component labels");
            int[] keep = new int[frontier.size()];
            int kept = 0;
            for (int i = 0; i < frontier.size(); ++i) {
                if (last[frontier.get(i)] > step) keep[kept++] = i;
            }
            keep = Arrays.copyOf(keep, kept);
            Map<Long, Long> next = new HashMap<>(4 * current.size());
            for (Map.Entry<Long, Long> entry : current.entrySet()) {
                long state = entry.getKey(), count = entry.getValue();
                for (int selected = 0; selected < 2; ++selected) {
                    if (selected != 0 && (state & FINISHED) != 0) continue;
                    int[] labels = new int[15];
                    int maximum = 0;
                    for (int i = 0; i < previousSize; ++i) {
                        labels[i] = (int) ((state >>> (4 * i)) & 15);
                        maximum = Math.max(maximum, labels[i]);
                    }
                    if (selected != 0) {
                        if (labels[u] == 0 && labels[v] == 0) {
                            labels[u] = labels[v] = maximum + 1;
                        } else if (labels[u] == 0) {
                            labels[u] = labels[v];
                        } else if (labels[v] == 0) {
                            labels[v] = labels[u];
                        } else {
                            int from = labels[v], to = labels[u];
                            for (int i = 0; i < labels.length; ++i) {
                                if (labels[i] == from) labels[i] = to;
                            }
                        }
                    }
                    int used = 0, retained = 0;
                    for (int label : labels) used |= 1 << label;
                    for (int i : keep) retained |= 1 << labels[i];
                    used &= ~1;
                    retained &= ~1;
                    int closed = used & ~retained;
                    long encoded = state & FINISHED;
                    if (closed != 0) {
                        // A component leaving the frontier can never connect to a later edge.
                        if (retained != 0 || (closed & (closed - 1)) != 0) continue;
                        encoded = FINISHED;
                    }
                    int[] canonical = new int[16];
                    int nextLabel = 1;
                    for (int i = 0; i < keep.length; ++i) {
                        int label = labels[keep[i]];
                        if (label != 0 && canonical[label] == 0) canonical[label] = nextLabel++;
                        encoded |= (long) canonical[label] << (4 * i);
                    }
                    next.merge(encoded, count, Long::sum);
                }
            }
            List<Integer> remaining = new ArrayList<>();
            for (int i : keep) remaining.add(frontier.get(i));
            frontier = remaining;
            current = next;
        }
        return current.getOrDefault(FINISHED, 0L);
    }

    static int transform(int mask, int[] permutation) {
        int result = 0;
        while (mask != 0) {
            result |= 1 << permutation[firstBit(mask)];
            mask &= mask - 1;
        }
        return result;
    }

    static int[] cycles(int[] permutation) {
        int[] result = new int[permutation.length];
        int size = 0, visited = 0;
        for (int i = 0; i < permutation.length; ++i) {
            if ((visited & (1 << i)) != 0) continue;
            int cycle = 0;
            int j = i;
            do {
                cycle |= 1 << j;
                j = permutation[j];
            } while (j != i);
            visited |= cycle;
            result[size++] = cycle;
        }
        result = Arrays.copyOf(result, size);
        Arrays.sort(result);
        return result;
    }

    static int[] canonicalPartition(int[] partition, List<int[]> group) {
        int[] result = partition;
        for (int[] permutation : group) {
            int[] candidate = new int[partition.length];
            for (int i = 0; i < partition.length; ++i) candidate[i] = transform(partition[i], permutation);
            Arrays.sort(candidate);
            if (Arrays.compare(candidate, result) < 0) result = candidate;
        }
        return result;
    }

    static long fixedSubsets(Graph graph, int[] partition) {
        if (partition.length == graph.edges.length) return connectedSubsets(graph);
        require(partition.length <= 20, "small nonidentity cycle enumeration");
        int[] subsets = new int[1 << partition.length];
        long result = 0;
        for (int mask = 1; mask < subsets.length; ++mask) {
            subsets[mask] = subsets[mask & (mask - 1)] | partition[firstBit(mask)];
            if (graph.connected(subsets[mask])) ++result;
        }
        return result;
    }

    static long skeletons(Graph graph, List<int[]> group) {
        TreeMap<int[], Integer> classes = new TreeMap<>(Arrays::compare);
        for (int[] permutation : group) {
            classes.merge(canonicalPartition(cycles(permutation), group), 1, Integer::sum);
        }
        long total = 0;
        for (Map.Entry<int[], Integer> entry : classes.entrySet()) {
            total += entry.getValue() * fixedSubsets(graph, entry.getKey());
        }
        require(total % group.size() == 0, "integral Burnside average");
        return total / group.size();
    }

    static long bruteConnected(Graph graph) {
        long result = 0;
        for (int mask = 1; mask < (1 << graph.edges.length); ++mask) {
            if (graph.connected(mask)) ++result;
        }
        return result;
    }

    static long bruteSkeletons(Graph graph, List<int[]> group) {
        TreeSet<Integer> representatives = new TreeSet<>();
        for (int mask = 1; mask < (1 << graph.edges.length); ++mask) {
            if (!graph.connected(mask)) continue;
            int representative = mask;
            for (int[] permutation : group) {
                representative = Math.min(representative, transform(mask, permutation));
            }
            representatives.add(representative);
        }
        return representatives.size();
    }

    static void checkGroup(List<int[]> group) {
        TreeSet<int[]> elements = new TreeSet<>(Arrays::compare);
        elements.addAll(group);
        for (int[] a : group) {
            for (int[] b : group) {
                int[] product = new int[a.length];
                for (int i = 0; i < a.length; ++i) product[i] = a[b[i]];
                require(elements.contains(product), "rotation group closure");
            }
        }
    }

    static void runTests() {
        List<int[]> complete = new ArrayList<>();
        for (int u = 0; u < 5; ++u) {
            for (int v = u + 1; v < 5; ++v) complete.add(new int[] {u, v});
        }
        for (int mask = 0; mask < (1 << complete.size()); ++mask) {
            List<int[]> edges = new ArrayList<>();
            for (int i = 0; i < complete.size(); ++i) {
                if ((mask & (1 << i)) != 0) edges.add(complete.get(i));
            }
            Graph graph = new Graph(5, edges);
            require(connectedSubsets(graph) == bruteConnected(graph), "all 1024 labelled graphs on five vertices");
        }
        List<Point> tetrahedron = List.of(new Point(1, 1, 1), new Point(1, -1, -1),
                new Point(-1, 1, -1), new Point(-1, -1, 1));
        List<Point> octahedron = List.of(new Point(1, 0, 0), new Point(-1, 0, 0), new Point(0, 1, 0),
                new Point(0, -1, 0), new Point(0, 0, 1), new Point(0, 0, -1));
        for (List<Point> points : List.of(tetrahedron, cube(), octahedron)) {
            Graph graph = makeGraph(points);
            List<int[]> group = rotations(points, graph);
            require(group.size() == (points.size() == 4 ? 12 : 24), "small rotation group size");
            checkGroup(group);
            require(connectedSubsets(graph) == bruteConnected(graph), "small polyhedron connected subsets");
            long answer = skeletons(graph, group);
            require(answer == bruteSkeletons(graph, group), "direct small polyhedron orbit enumeration");
            if (points.size() == 4) require(answer == 10, "given tetrahedron example");
        }
        List<Point> points = dodecahedron();
        Graph graph = makeGraph(points);
        List<int[]> group = rotations(points, graph);
        require(graph.vertices == 20 && graph.edges.length == 30 && group.size() == 60, "dodecahedron dimensions");
        checkGroup(group);
        Map<Integer, Integer> cycleCounts = new TreeMap<>();
        long total = 0;
        for (int[] permutation : group) {
            int[] partition = cycles(permutation);
            cycleCounts.merge(partition.length, 1, Integer::sum);
            total += fixedSubsets(graph, partition);
        }
        require(cycleCounts.equals(Map.of(6, 24, 10, 20, 16, 15, 30, 1)), "rotation cycle types");
        require(total == group.size() * skeletons(graph, group), "all 60 rotations versus grouped enumeration");
        List<int[]> relabelled = new ArrayList<>();
        for (int i = graph.edges.length - 1; i >= 0; --i) {
            relabelled.add(new int[] {graph.vertices - 1 - graph.edges[i][0], graph.vertices - 1 - graph.edges[i][1]});
        }
        require(connectedSubsets(new Graph(graph.vertices, relabelled)) == connectedSubsets(graph),
                "independent frontier order");
        System.out.println("All checks passed: 1024 small graphs, tetrahedron example, direct "
                + "tetrahedron/cube/octahedron orbits, rotation groups, all 60 dodecahedron rotations, "
                + "and frontier reordering.");
    }

    public static void main(String[] args) {
        try {
            if (args.length == 1 && args[0].equals("--self-test")) {
                runTests();
            } else {
                if (args.length != 0) throw new IllegalArgumentException("Usage: java Euler1019 [--self-test]");
                List<Point> points = dodecahedron();
                Graph graph = makeGraph(points);
                List<int[]> group = rotations(points, graph);
                require(graph.vertices == 20 && graph.edges.length == 30 && group.size() == 60,
                        "dodecahedron dimensions");
                System.out.println(skeletons(graph, group));
            }
        } catch (RuntimeException error) {
            System.err.println(error.getMessage());
            System.exit(1);
        }
    }
}