Construct a graph

Question

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 by m. Note that 0 is divisible by all m, 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.

Answer 1

Pyth, 37 31

lu?+GH<H2m@Gdf%+*@GTtTs>GTHUGQY

This solution uses a reduce function (u) to build up a list, where each entry corresponds to a node remaining in the list, and the value of the entry corresponding to whether the node was originally added under directive 0 or 1.

G is the accumulator variable in the reduce function, and holds the aforementioned list. It is initialized to the empty list, Y.

H takes the value of each member of Q, the input, one by one. The result of the expression is assigned to G each time, and the next entry of Q is assigned to H, and the expression is rerun.

To update G properly, there are two possibilities, one for directive 0 or 1, and one for the other directives. These case are distinguished with the ternary ? ... <H2 ...

If H is 0 or 1, then all we need to do is append H to G. +GH accomplishes this.

Otherwise, the first thing that is need is to determine, for every node in the graph, how many neighbors it has. This is accomplished in two steps:

First, s>GT counts the number of nodes at or after the input node which are 1s. These are all connected to the input node, except that we will over count by 1 if the input node is a 1.

Second, we need the number of nodes earlier than the input node which are connected to it. This is 0 if the input node is a 0, and the index of the input node, T, if the input node is a 1. This value would be given by *@GTT. However, there is still the over count from the first section which needs to be corrected. Thus, we calculate *@GTtT instead, which is 1 less if the input node is a 1. These values are summed, to give the number of nodes connected to the input node.

% ... H will give 0 is that number is divisible by H, and thus should be removed, and will not give 0 otherwise.

f ... UG will thus give the indices of the input which should not be removed, since f is a filter, and 0 is falsy.

m@Gd converts these indices to the 0s and 1s of the corresponding nodes.

Finally, once the resultant list of nodes labeled 0 and 1 is found, its length is computed (l) and printed (implicit).

Broad idea thanks to @PeterTaylor.

Answer 2

GolfScript (53 bytes)

])~{:^1>{.-1:H)-,:T;{..H):H*T@-:T+^%!{;}*}%}{^+}if}/,

Online demo

I haven't actually golfed this yet, but I have discovered that it's not very easy to eliminate the H and T variables so this might be a local minimum.

Takes input on stdin in the format [0 1 2 3]. Leaves output on stdout.

Ungolfed:

])~{
  :^1>{
    # array of 0s and 1s
    # Each 0 has degree equal to the number of 1s after it
    # Each 1 has degree equal to the number of values before it plus the number of 1s after it
    .-1:H)-,:T;
    {
      # Stack: x
      # T' = T - x is the number of 1s after it
      # H' = H + 1 is the number of values before it
      # Degree is therefore H' * x + T' = H * x + T - x = (H-1)*x + T
      # Keep x unless degree % ^ == 0
      ..H):H*T@-:T+^%!{;}*
    }%
  }{^+}if
}/,

Answer 3

CJam, 129 75 73 68 61 46 42 bytes

Solution based on Peter's algorithm:

Lq~{I+I1>{0:U(<:L{LU<,*LU):U>1b+I%},}*}fI,

Code expansion to follow.

---

Previous solution (61 bytes):

Lq~{:N2<{U):UaN{f+U1$0f=+}*a+}{{:X,(N%_!{X0=L+:L;}*},Lf-}?}/,

Takes input from STDIN like:

[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]

Output is the number on STDOUT:

8

Algorithm:

• Maintain an incrementing variable U which stores id of the node to be added.
• Maintain a list of list in which , each list is a node with a unique id made up by the first element of the list and the remaining elements being the ids of connected nodes.
• In each iteration (while reading the input directives),
  • If the directive is 0, add [U] to a list of list
  • If the directive is 1, add U to each list in the list of list and add another list comprised of first element of each of the list of list and U
  • For directive to remove, I filter out all lists of length - 1 divisible by m and keep noting the first element of those lists. After filtering, I remove all the removed id from remaining list of ids.

Code expansion:

Lq~{:N2<{U):UaN{f+U1$0f=+}*a+}{{:X,(N%_!{X0=L+:L;}*},Lf-}?}/,
L                                            "Put an empty array on stack";
 q~                                          "Evaluate the input";
   {                                }/       "For each directive";
    :N                                       "Store the directive in N";
      2<{     ...    }{    ...    }?         "If directive is 0 or 1, run the first";
                                             "block, else second";
{U):UaN{f+U1$0f=+}*a+}
 U):U                                        "Increment and update U (initially 0)";
     a                                       "Wrap it in an array";
      N{         }*                          "Run this block if directive is 1";
        f+                                   "Add U to each list in list of list";
          U1$                                "Put U and list of lists on stack";
             0f=                             "Get first element of each list";
                +                            "Prepend U to the above array";
                   a+                        "Wrap in array and append to list of list";
{{:X,(N%_!{X0=L+:L;}*},Lf-}
 {                   },                      "Filter the list of list on this block";
  :X,(                                       "Get number of connections of this node";
      N%_                                    "mod with directive and copy the result";
         !{        }*                        "If the mod is 0, run this block";
           X0=                               "Get the id of this node";
              L+:L;                          "Add to variable L and update L";
                       Lf-                   "Remove all the filtered out ids from the";
                                             "remaining nodes";
,                                            "After the whole process is completed for"
                                             "all directives, take length of remaining ";
                                             "nodes in the list of list";

Try it here

Answer 4

APL, 71 65 55 characters

{⍬≡⍺:≢⍵⋄r←1↓⍺⋄1<c←⊃⍺:r∇i⌿⍵/⍨i←0≠c|+/⍵⋄c:r∇∨⌿↑a(⍉a←⍵,1)⋄r∇0,0⍪⍵}∘(0 0⍴0)

{⍺←0 0⍴0⋄⍬≡⍵:≢⍺⋄(⍺{1<⍵:i⌿⍺/⍨i←×⍵|+/⍺⋄⍵:-⌿↑(1,1⍪⍺)1⋄0,0⍪⍺}⊃⍵)∇1↓⍵}

{g←0 0⍴0⋄(≢g)⊣{1<⍵:g⌿⍨←g/⍨←×⍵|+/g⋄(⊃g)-←g⍪⍨←g,⍨←⍵}¨2,⍵}

The graph is represented as a boolean adjacency matrix. Rows/columns are added and removed as necessary.

Answer 5

Pyth, 88 80 75 characters

JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J

I'm done. Maybe someone else has some golfing tips.

Y is the adjacency list of the graph. For golfing reasons, I also keep a node in this list, even after the node got deleted (Otherwise I would have to update all indices). Each node has itself as neighbor. The list J keeps track of the deleted nodes.

I show the changes of the adjacency list on the example input [0,1,0,1,0,1,3]:

input 0: Y=[[0]]                                                         J=[]
input 1: Y=[[0,1],[0,1]] 0                                               J=[]
input 0: Y=[[0,1],[0,1],[2]]                                             J=[]
input 1: Y=[[0,1,3],[0,1,3],[2,3],[0,1,2,3]]                             J=[]
input 0: Y=[[0,1,3],[0,1,3],[2,3],[0,1,2,3],[4]]                         J=[]
input 1: Y=[[0,1,3,5],[0,1,3,5],[2,3,5],[0,1,2,3,5],[4,5],[0,1,2,3,4,5]] J=[]
input 3: Y=[[3,5],[3,5],[2,3,5],[2,3,5],[4,5],[2,3,4,5]]                 J=[0,1]

The algorithm then is pretty simple: Iterate over all inputs, if input==0: add a new node with itself as neighbour, if input==1: add a new node with all nodes as neighbors (also the deleted ones) and add this node to the adjacency list of all nodes, if input>1: determine the nodes with #neighbor-1%input==0 and add them to J, in each case, update the neighbors of each node using J. At the end print the length of Y minus the length of (the set of) J.

JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J
JY                      set J=[]
  FHQ                   for H in: input()
I!H      )                if H==0:
   ~Y]]lY                   Y.append([len(Y)])
IqH1              )       if H==1:
    =Y+                     Y=                 +
       m+dlYY                 old nodes updated
             ]UhlY                              new node with all neighbors
VY                )       for N in range(len(Q)):
  I&Hq%l@YNH1    )          if H>0 and len(Y[N])%H==1:
             ~J]N             J.append(N) //this node gets deleted
=Ym           Y           Y=[           for k in Y]
   f!}TJ@YkUlY               k-filtered  //all items of J are removed
;                       end input for loop
-lYl{J                  print len(Y) - len(set(J))

Usage

Just call the script and give as input [0,1,0,1,0,1,3] or some other test-case.

Answer 6

Python 2, 296

s=input();e=[];n=[];c=0
for t in s:
    if t<2:e=e+[[]]if t==0 else [x+[c]for x in e]+[n[:]];n+=[c];c+=1
    else:
        M=zip(*[(i,n[i])for i,x in enumerate(e)if not len(x)%t])
        if M:e=[list(set(z)-set(M[1]))for j,z in enumerate(e)if j not in M[0]];n=list(set(n)-set(M[1]))
print len(n)

Each node is given a unique id and the neighbor ids of each node are recorded. When the directive is 0, an empty neighbor list is added for the new node. When the directive is 1, the ids of all existing nodes become the neighbor list for the new node, and all other neighbor lists are updated to include the new node id. For m>1, nodes with neighbor lists that are a multiple of m are removed from the node list and all neighbor lists. Thanks to @Optimizer for catching a bug in an earlier version.

Answer 7

NetLogo, 160

to f[t]foreach t[if ? = 0[crt 1]if ? = 1[crt 1[create-links-with other turtles]]if ? > 1[ask turtles with[count my-links mod ? = 0][die]]]show count turtles
end

The implementation is straightforward, reading each symbol and doing the appropriate action.

to f[t]
  foreach t [
    if ? = 0 [
      crt 1
    ]
    if ? = 1 [
      crt 1 [create-links-with other turtles]
    ]
    if ? > 1 [
      ask turtles with [count my-links mod ? = 0] [die]
    ]
  ]
  show count turtles
end

You can run from the command line as f[0 0 1 1 0 0 1 1 2 5 7 0 1].

Answer 8

Ruby 159 157 (demo)

N=Struct.new:l
G=->c{n=[]
c.map{|m|m<1?n<<N.new([]):m<2?(w=N.new([])
n.map{|x|x.l<<w;w.l<<x}
n<<w):(n-=r=n.select{|x|x.l.size%m<1}
n.map{|x|x.l-=r})}
n.size}

This defines a function called G using stabby-lambda syntax. Use G[[0, 1]] to call it with commands 0 and 1.

The implementation is pretty straightforward: there is a Node structure (called N above) which holds references to all linked nodes via the l property. G creates nodes as needed and manipulates their links. A readable version is available here.

Answer 9

CJam, 99 97 bytes

Lal~{I2<{_0={{If+z}2*));0+a+}{;Iaa}?}{_0=!!{{{_:+I%+}%z}2*));1+a+{{W=},z}2*);z_{);}{a}?}*}?}fI0=,

There is still a lot to be golfed in this. The algorithm is based on keeping track of the adjacency matrix, but representing the empty matrix without having to treat it specially is giving me headaches.

Test it here.

Input is a CJam-style array:

[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]

You can use this test harness to run all tests:

"[]
[5]
[0,0,0,11]
[0,1,0,1,0,1,3]
[0,0,0,1,1,1]
[0,0,1,1,0,0,1,1,2,5,7,0,1]
[0,0,1,1,1,1,5,1,4,3,1,0,0,0,1,2]
[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]
[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]"

","SerN/{
La\~{I2<{_0={{If+z}2*));0+a+}{;Iaa}?}{_0=!!{{{_:+I%+}%z}2*));1+a+{{W=},z}2*);z_{);}{a}?}*}?}fI0=,
N}/

Answer 10

Python 2, 174

l=input()
g={}
n=0
for x in l:
 n+=1;g[n]=set()
 if x>1:h={i for i in g if len(g[i])%x};g={i:g[i]&h for i in set(g)&h}
 if x==1:
  for i in g:g[i]^={n};g[n]^={i}
print len(g)

This can probably still be golfed a lot.

I used a dictionary g to represent the graph. The nodes are labelled by numbers, and they map to the set of adjacent nodes. This means that each update of an edge needs to be executed at both of its endpoints.

Fresh node indices are created by counting up n. Each time, I create a new empty node n. For command 0, it just remains. For command 1, it's connected to each other node via g[i]^={n};g[n]^={i}; using xor make its so that the node isn't connected to itself. For commands >1, it's immediately deleted.

The filtering of nodes whose degree is a multiple is done by first finding nodes that the remain (h), then anding it with the list of nodes and the neighbors of each node.

Finally, the number of entries in the graph dictionary is the answer.

Answer 11

Mathematica, 223 bytes

Wow, this turned out longer than I expected.

f=(g={};t=Append;l=Length;m=ListQ;h=Flatten;k=Position;o=If;(d=#;o[d==0,g=g~t~{},o[d==1,g=o[m@#,t[#,l@g+1],#]&/@g;g=t[g,h@k[g,_?m,1]],g=o[l@#~Mod~d==0,0,#]&/@g;p=h@k[g,0];(c=#;g=#~DeleteCases~c&/@g)&/@p]])&/@#;g~Count~_?m)&

Usage:

f@{0, 1, 0, 1, 0, 1, 3}

Here are the results from the test cases:

f /@ {
  {},
  {5},
  {0, 0, 0, 11},
  {0, 1, 0, 1, 0, 1, 3},
  {0, 0, 0, 1, 1, 1},
  {0, 0, 1, 1, 0, 0, 1, 1, 2, 5, 7, 0, 1},
  {0, 0, 1, 1, 1, 1, 5, 1, 4, 3, 1, 0, 0, 0, 1, 2},
  {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},
  {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}
}

Out: {0, 0, 0, 4, 6, 6, 6, 8, 14}

Less golfed:

f = (
   a = #;
   g = {};
   Table[
    If[a[[n]] == 0,
     AppendTo[g, {}],
     If[a[[n]] == 1,
      g = If[ListQ@#, Append[#, Length@g + 1], #] & /@ g; 
      g = Append[g, Flatten@Position[g, _?ListQ, 1]],
      If[a[[n]] > 1,
       g = If[Mod[Length@#, a[[n]]] == 0, 0, #] & /@ g;
       p = Flatten@Position[g, 0];
       (c = #; g = DeleteCases[#, c] & /@ g) & /@ p
       ]
      ]
     ],
    {n, Length@a}];
   Count[g, _?ListQ]
   ) &

The way this works is by representing the graph as list of "lists of neighbors".
For the 0 directive, I just append an empty list.
For the 1 directive, I append a list of all the previous nodes, and add the new node to all the previous nodes.
For a directive >1, I removed the specified nodes and update the rest.