Skip to main content
added 118 characters in body
Source Link
Jonathan Allan
  • 115.5k
  • 8
  • 68
  • 293

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL 

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online! Or see the test-suite.

How?

Repeatedly add edges that do not yet exist for all traversable pairs of edges, then count the number of new edges.

;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A ÐL - start with X=A and loop until a fixed point applying: € - for each {node in X}: ʋ - last four links as a dyad - F(node, X) ị - {node} index into {X} (vectorises) ; - {node} concatenate {that} F - flatten Q - deduplicate -> updated node ⁸ - chain's left argument -> A " - zip with: ḟ - {final node} filter discard {original node from A} F - flatten L - length 

The end, ḟ"⁸FL, seems long, is there something better than this or ;ịFQʋ€ÐLn>0SS etc.?

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL 

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online! Or see the test-suite.

How?

;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A ÐL - start with X=A and loop until a fixed point applying: € - for each {node in X}: ʋ - last four links as a dyad - F(node, X) ị - {node} index into {X} (vectorises) ; - {node} concatenate {that} F - flatten Q - deduplicate -> updated node ⁸ - chain's left argument -> A " - zip with: ḟ - {final node} filter discard {original node from A} F - flatten L - length 

The end, ḟ"⁸FL, seems long, is there something better than this or ;ịFQʋ€ÐLn>0SS etc.?

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL 

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online! Or see the test-suite.

How?

Repeatedly add edges that do not yet exist for all traversable pairs of edges, then count the number of new edges.

;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A ÐL - start with X=A and loop until a fixed point applying: € - for each {node in X}: ʋ - last four links as a dyad - F(node, X) ị - {node} index into {X} (vectorises) ; - {node} concatenate {that} F - flatten Q - deduplicate -> updated node ⁸ - chain's left argument -> A " - zip with: ḟ - {final node} filter discard {original node from A} F - flatten L - length 

The end, ḟ"⁸FL, seems long, is there something better than this or ;ịFQʋ€ÐLn>0SS etc.?

added 243 characters in body
Source Link
Jonathan Allan
  • 115.5k
  • 8
  • 68
  • 293

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL 

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online! Or see the test-suite.

How?

;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A ÐL - start with X=A and loop until a fixed point applying: € - for each {node in X}: ʋ - last four links as a dyad - F(node, X) ị - {node} index into {X} (vectorises) ; - {node} concatenate {that} F - flatten Q - deduplicate -> updated node ⁸ - chain's left argument -> A " - zip with: ḟ - {final node} filter discard {original node from A} F - flatten L - length 

The end, ḟ"⁸FL, seems long, is there something better than this or ;ịFQʋ€ÐLn>0SS etc.?

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL 

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online!

How?

;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A ÐL - start with X=A and loop until a fixed point applying: € - for each {node in X}: ʋ - last four links as a dyad - F(node, X) ị - {node} index into {X} (vectorises) ; - {node} concatenate {that} F - flatten Q - deduplicate -> updated node ⁸ - chain's left argument -> A " - zip with: ḟ - {final node} filter discard {original node from A} F - flatten L - length 

The end, ḟ"⁸FL, seems long, is there something better than this or ;ịFQʋ€ÐLn>0SS etc.?

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL 

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online! Or see the test-suite.

How?

;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A ÐL - start with X=A and loop until a fixed point applying: € - for each {node in X}: ʋ - last four links as a dyad - F(node, X) ị - {node} index into {X} (vectorises) ; - {node} concatenate {that} F - flatten Q - deduplicate -> updated node ⁸ - chain's left argument -> A " - zip with: ḟ - {final node} filter discard {original node from A} F - flatten L - length 

The end, ḟ"⁸FL, seems long, is there something better than this or ;ịFQʋ€ÐLn>0SS etc.?

added 660 characters in body
Source Link
Jonathan Allan
  • 115.5k
  • 8
  • 68
  • 293

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL 

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online!

How?

;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A ÐL - start with X=A and loop until a fixed point applying: € - for each {node in X}: ʋ - last four links as a dyad - F(node, X) ị - {node} index into {X} (vectorises) ; - {node} concatenate {that} F - flatten Q - deduplicate -> updated node ⁸ - chain's left argument -> A " - zip with: ḟ - {final node} filter discard {original node from A} F - flatten L - length 

The end, ḟ"⁸FL, seems long, is there something better than this or ;ịFQʋ€ÐLn>0SS etc.?

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL 

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online!

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL 

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online!

How?

;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A ÐL - start with X=A and loop until a fixed point applying: € - for each {node in X}: ʋ - last four links as a dyad - F(node, X) ị - {node} index into {X} (vectorises) ; - {node} concatenate {that} F - flatten Q - deduplicate -> updated node ⁸ - chain's left argument -> A " - zip with: ḟ - {final node} filter discard {original node from A} F - flatten L - length 

The end, ḟ"⁸FL, seems long, is there something better than this or ;ịFQʋ€ÐLn>0SS etc.?

Source Link
Jonathan Allan
  • 115.5k
  • 8
  • 68
  • 293
Loading