In this challenge, your task is to construct an undirected graph from a sequence of directives. There is one directive for each nonnegative integer, and each transforms a given graph into a new one.
- Directive
0
: Add a new disconnected node. - Directive
1
: Add a new node, and connect it to every existing node. - Directive
m > 1
: Remove all nodes whose degree (number of neighbors) is divisible bym
. Note that0
is divisible by allm
, so disconnected nodes are always removed.
The directives are applied one by one, from left to right, starting with the empty graph. For example, the sequence [0,1,0,1,0,1,3]
is processed as follows, explained using awesome ASCII art. We start with the empty graph, and add a single vertex as directed by 0
:
a
Then, add another vertex and connect it to the first, as directed by 1
:
a--b
We add another disconnected vertex and then a connected one, as directed by 0
and 1
:
a--b c
\ \ /
`--d
We repeat this one more time, as directed by 0
and 1
:
,--f--e
/ /|\
a--b | c
\ \|/
`--d
Finally, we remove the degree-3 vertices a
and b
, as directed by 3
:
f--e
|\
| c
|/
d
This is the graph defined by the sequence [0,1,0,1,0,1,3]
.
Input
A list of nonnegative integers, representing a sequence of directives.
Output
The number of nodes in the graph defined by the sequence.
Test cases
[] -> 0
[5] -> 0
[0,0,0,11] -> 0
[0,1,0,1,0,1,3] -> 4
[0,0,0,1,1,1] -> 6
[0,0,1,1,0,0,1,1,2,5,7,0,1] -> 6
[0,0,1,1,1,1,5,1,4,3,1,0,0,0,1,2] -> 6
[0,0,1,1,0,0,1,1,5,2,3,0,0,1,1,0,0,1,1,3,4,0,0,1,1,2,1,1] -> 8
[0,0,1,1,0,0,1,1,2,5,7,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,8] -> 14
Detailed rules
You can write a function or a full program. The shortest byte count wins. Standard loopholes are disallowed. Please explain your algorithm in your answer.
It's been a week, so I have accepted the shortest answer. If an even shorter one comes along later, I'll update my choice. An honorable mention goes to Peter Taylor's answer, on which several others were based on, including the winner.