Home/

...

/

Problem Challenge 1

Problem Challenge 1

Problem statement

Given a sequence originalSeq and an array of sequences, write a method to find if originalSeq can be uniquely reconstructed from the array of sequences.

Unique reconstruction means that we need to find if originalSeq is the only sequence such that all sequences in the array are subsequences of it.

Dry-run tables

The following is the implementation of the solution provided for the problem posed in the Problem Challenge 1 lesson:

Press + to interact
Python 3.8
from collections import deque
def can_construct(originalSeq, sequences):
  sortedOrder = []
  if len(originalSeq) <= 0:
    return False
  # a. Initialize the graph
  inDegree = {}  # count of incoming edges
  graph = {}  # adjacency list graph
  for sequence in sequences:
    for num in sequence:
      inDegree[num] = 0
      graph[num] = []
  # b. Build the graph
  for sequence in sequences:
    for i in range(1, len(sequence)):
      parent, child = sequence[i - 1], sequence[i]
      graph[parent].append(child)
      inDegree[child] += 1
  # if we don't have ordering rules for all the numbers we'll not able to uniquely construct the sequence
  if len(inDegree) != len(originalSeq):
    return False
  # c. Find all sources i.e., all vertices with 0 in-degrees
  sources = deque()
  for key in inDegree:
    if inDegree[key] == 0:
      sources.append(key)
  # d. For each source, add it to the sortedOrder and subtract one from all of its children's in-degrees
  # if a child's in-degree becomes zero, add it to the sources queue
  while sources:
    if len(sources) > 1:
      return False  # more than one sources mean, there is more than one way to reconstruct the sequence
    if originalSeq[len(sortedOrder)] != sources[0]:
      # the next source(or number) is different from the original sequence
      return False
    vertex = sources.popleft()
    sortedOrder.append(vertex)
    for child in graph[vertex]:  # get the node's children to decrement their in-degrees
      inDegree[child] -= 1
      if inDegree[child] == 0:
        sources.append(child)
  # if sortedOrder's size is not equal to original sequence's size, there is no unique way to construct
  return len(sortedOrder) == len(originalSeq)
def main():
  print("Can construct: " +
        str(can_construct([1, 2, 3, 4], [[1, 2], [2, 3], [3, 4]])))
  print("Can construct: " +
        str(can_construct([1, 2, 3, 4], [[1, 2], [2, 3], [2, 4]])))
  print("Can construct: " +
        str(can_construct([3, 1, 4, 2, 5], [[3, 1, 5], [1, 4, 2, 5]])))
main()

Sample input #1

Input: originalSeq: [1, 2, 3, 4], seqs: [[1, 2], [2, 3], [3, 4]]

Note: The column Outer loops represents the loops in our algorithm and their iteration number. For example, column entry while: 2 represents the second iteration of the while loop.

Since, there are 3 loops, the column Line number specifies the loop we’re considering. The column Inner loop iteration represents the nested for loops (line 19 - line 22 and line 45 - line 48).

Line number

Outer loops

Inner loop iteration

graph

sequence

parent

child

inDegree[child]

inDegree

sources

vertex

sortedOrder

5-15



{1: [], 2: [], 3: [], 4: []}





{1: 0, 2: 0, 3: 0, 4: 0}



[ ]

18-22

for: 1

1

{1: [2], 2: [], 3: [], 4: []}

[1, 2]

1

2


{1: 0, 2: 1, 3: 0, 4: 0}



[ ]

18-22

for: 2

1

{1: [2], 2: [3], 3: [], 4: []}

[2, 3]

2

3


{1: 0, 2: 1, 3: 1, 4: 0}



[ ]

18-22

for: 3

1

{1: [2], 2: [3], 3: [4], 4: []}

[3, 4]

3

4


{1: 0, 2: 1, 3: 1, 4: 1}



[ ]

29-32

for: 1


{1: [2], 2: [3], 3: [4], 4: []}





{1: 0, 2: 1, 3: 1, 4: 1}

[1]


[ ]

29-32

for: 2


{1: [2], 2: [3], 3: [4], 4: []}





{1: 0, 2: 1, 3: 1, 4: 1}

[1]


[ ]

29-32

for: 3


{1: [2], 2: [3], 3: [4], 4: []}



c


{1: 0, 2: 1, 3: 1, 4: 1}

[1]


[ ]

36-48

while: 1

1

{1: [2], 2: [3], 3: [4], 4: []}



2

0

{1: 0, 2: 0, 3: 1, 4: 1}

[2]

1

[1]

36-48

while: 2

1

{1: [2], 2: [3], 3: [4], 4: []}



3

0

{1: 0, 2: 0, 3: 0, 4: 1}

[3]

2

[1, 2]

36-48

while: 3

1

{1: [2], 2: [3], 3: [4], 4: []}



4

0

{1: 0, 2: 0, 3: 0, 4: 0}

[4]

3

[1, 2, 3]

36-48

while: 4

1

{1: [2], 2: [3], 3: [4], 4: []}





{'b': 0, 'c': 0, 'a': 0}

[ ]

4

[1, 2, 3, 4]

Sample input #2

Students may be encouraged to complete the dry-run table with the following input:

Input: originalSeq: [1, 2, 3, 4], seqs: [[1, 2], [2, 3], [2, 4]]

Line number

Outer loops

Inner loop iteration

graph

sequence

parent

child

inDegree[child]

inDegree

sources

vertex

sortedOrder

5-15



{1: [], 2: [], 3: [], 4: []}





{1: 0, 2: 0, 3: 0, 4: 0}



[ ]

18-22

for: 1

1

{1: [2], 2: [], 3: [], 4: []}

[1, 2]

1

2


{1: 0, 2: 1, 3: 0, 4: 0}



[ ]

18-22

for: 2

1

{1: [2], 2: [3], 3: [], 4: []}

[2, 3]

2

3


{1: 0, 2: 1, 3: 1, 4: 0}



[ ]

...

...

...

...

...

...

...

...

...

...

...

...

Step-by-step solution construction

In the above problem, the given sequences can be considered as edges. For example, for the sequence [1, 2], we can assume there is an edge from 1 to 2, and hence, 1 comes before 2.

The first step is to initialize the graph with vertices and empty adjacency lists. We also maintain a dictionary inDegree that will store the number of incoming edges for each vertex. However, in this step, we’ll initialize it to 0.

Press + to interact
Python 3.8
from collections import deque
def can_construct(originalSeq, sequences):
  sortedOrder = []
  if len(originalSeq) <= 0:
    return False
  print("originalSeq: ", originalSeq)
  print("sequences: ", sequences)
  print("")
  # a. Initialize the graph
  inDegree = {}  # count of incoming edges
  graph = {}  # adjacency list graph
  k = 1
  print("Initialising the graph and inDegree")
  for sequence in sequences:
    print("\tLoop iteration: ", k, sep ="")
    k+=1
    print("\t\tsequence: ", sequence, sep ="")
    n = 1
    for num in sequence:
      print("\t\tLoop iteration: ", n, sep = "")
      n+=1
      print("\t\t\tnum: ", num, sep = "")
      print("\t\t\tAdding vertex '", num, "' to inDegree and graph", sep = "")
      inDegree[num] = 0
      graph[num] = []
      print("\t\t\tinDegree: ", inDegree, sep = "")
      print("\t\t\tgraph: ", graph, sep = "")
      print("")
  # if sortedOrder's size is not equal to original sequence's size, there is no unique way to construct
  return len(sortedOrder) == len(originalSeq)
def main():
  inputsequences = [([1, 2, 3, 4], [[1, 2], [2, 3], [3, 4]]), ([1, 2, 3, 4], [[1, 2], [2, 3], [2, 4]]), ([3, 1, 4, 2, 5], [[3, 1, 5], [1, 4, 2, 5]])]
  for i in inputsequences:
    print("Can construct: ", str(can_construct(i[0], i[1])), sep = "")
    print("-"*100+"\n")
main()

The next step is building the graph. For a given sequence, every element can be considered a parent of the succeeding element. For example, in sequence [1, 2, 3], 1 is the parent of 2 and 2 is the parent of 3.
We’ll append the parent to the graph and add the child to its adjacency list. We’ll also increment the inDegree of the child by 1.

Press + to interact
Python 3.8
from collections import deque
def can_construct(originalSeq, sequences):
  sortedOrder = []
  if len(originalSeq) <= 0:
    return False
  print("originalSeq: ", originalSeq)
  print("sequences: ", sequences)
  print("")
  # a. Initialize the graph
  inDegree = {}  # count of incoming edges
  graph = {}  # adjacency list graph
  k = 1
  print("Initialising the graph and inDegree")
  for sequence in sequences:
    for num in sequence:
      inDegree[num] = 0
      graph[num] = []
  print("\tgraph: ", graph, sep = "")
  print("\tinDegree: ", inDegree, sep = "")
  print("")
  # b. Build the graph
  print("Building the graph")
  k = 1
  for sequence in sequences:
    print("\tLoop iteration: ", k, sep = "")
    k+=1
    print("\tsequence: ", sequence, sep = "")
    m = 1
    for i in range(1, len(sequence)):
      print("\tInner loop iteration: ", m, sep = "")
      m+=1
      parent, child = sequence[i - 1], sequence[i]
      print("\t\tparent: ", parent, sep = "")
      print("\t\tchild: ", child, sep = "")
      graph[parent].append(child)
      print("\t\tAdding ", child, " to the adjacency list of ", parent, " --> ", graph, sep = "")
      inDegree[child] += 1
      print("\t\tIncrementing inDegree of ", child, ": ", inDegree[child]-1, " + 1 = ", inDegree[child], sep = "")
      print("\t\tinDegree: ", inDegree, sep = "")
      print("")
  if len(inDegree) != len(originalSeq):
    return False
  # if sortedOrder's size is not equal to original sequence's size, there is no unique way to construct
  return len(sortedOrder) == len(originalSeq)
def main():
  inputsequences = [([1, 2, 3, 4], [[1, 2], [2, 3], [3, 4]]), ([1, 2, 3, 4], [[1, 2], [2, 3], [2, 4]]), ([3, 1, 4, 2, 5], [[3, 1, 5], [1, 4, 2, 5]])]
  for i in inputsequences:
    print("Can construct: ", str(can_construct(i[0], i[1])), sep = "")
    print("-"*100+"\n")
main()

The if condition in lines 46 and 47 checks if we have ordering rules for all the numbers, hence, ensuring that we get a uniquely reconstructed sequence.

Next, we’ll find the sources, that is, vertices with inDegree = 0.

Press + to interact
Python 3.8
from collections import deque
def can_construct(originalSeq, sequences):
  sortedOrder = []
  if len(originalSeq) <= 0:
    return False
  print("originalSeq: ", originalSeq)
  print("sequences: ", sequences)
  print("")
  # a. Initialize the graph
  inDegree = {}  # count of incoming edges
  graph = {}  # adjacency list graph
  k = 1
  print("Initialising the graph and inDegree")
  for sequence in sequences:
    for num in sequence:
      inDegree[num] = 0
      graph[num] = []
  print("\tgraph: ", graph, sep = "")
  print("\tinDegree: ", inDegree, sep = "")
  print("")
  # b. Build the graph
  print("Building the graph")
  k = 1
  for sequence in sequences:
    for i in range(1, len(sequence)):
      parent, child = sequence[i - 1], sequence[i]
      graph[parent].append(child)
      inDegree[child] += 1
  print("\tgraph: ", graph, sep = "")
  print("\tinDegree: ", inDegree, sep = "")
  print("")
  if len(inDegree) != len(originalSeq):
    return False
  print("Finding the sources")
  sources = deque()
  l = 1
  for key in inDegree:
    print("\tLoop iteration: ", l, sep = "")
    l+=1
    if inDegree[key] == 0:
      print("\t\tinDegree of vertex ", key, " = ", inDegree[key], " --> vertex is a source", sep = "")
      sources.append(key)
      print("\t\tsources: ", sources, sep = "")
    else:
      print("\t\tinDegree of vertex ", key, " = ", inDegree[key], " --> not 0, hence, not a source", sep = "")
    print("")
  print("")
  # if sortedOrder's size is not equal to original sequence's size, there is no unique way to construct
  return len(sortedOrder) == len(originalSeq)
def main():
  inputsequences = [([1, 2, 3, 4], [[1, 2], [2, 3], [3, 4]]), ([1, 2, 3, 4], [[1, 2], [2, 3], [2, 4]]), ([3, 1, 4, 2, 5], [[3, 1, 5], [1, 4, 2, 5]])]
  for i in inputsequences:
    print("Can construct: ", str(can_construct(i[0], i[1])), sep = "")
    print("-"*100+"\n")
main()

Now, we’ll try to topologically sort the sequence elements. We’ll use the same layer-by-layer approach explained in the Introduction guide: adding the sources into an array, sortedOrder, and decrementing their children’s in-degrees. If a child’s in-degree becomes zero, this signifies that it belongs to the next layer and we add it to the sources queue.

Since we want unique sequence reconstructions, we’ll add two if conditions:

  • If the length of sources is ever greater than 1, that means that there is more than 1 source in that layer, leading to the possibility of multiple orderings of the subsequences. As this violates our requirement, we return False.
  • If the next source is different from the number in the original sequence predicted by the sortOrder computed so far, we return False.

Lastly, we’ll check if the length of sortedOrder is equal to the length of the original sequence. If yes, originalSeq can be uniquely reconstructed from the given sequences. This step is shown in lines 89 and 91.

Press + to interact
Python 3.8
from collections import deque
import copy
def can_construct(originalSeq, sequences):
  sortedOrder = []
  if len(originalSeq) <= 0:
    return False
  print("originalSeq: ", originalSeq)
  print("sequences: ", sequences)
  print("")
  # a. Initialize the graph
  inDegree = {}  # count of incoming edges
  graph = {}  # adjacency list graph
  k = 1
  print("Initialising the graph and inDegree")
  for sequence in sequences:
    for num in sequence:
      inDegree[num] = 0
      graph[num] = []
  print("\tgraph: ", graph, sep = "")
  print("\tinDegree: ", inDegree, sep = "")
  print("")
  # b. Build the graph
  print("Building the graph")
  k = 1
  for sequence in sequences:
    for i in range(1, len(sequence)):
      parent, child = sequence[i - 1], sequence[i]
      graph[parent].append(child)
      inDegree[child] += 1
  print("\tgraph: ", graph, sep = "")
  print("\tinDegree: ", inDegree, sep = "")
  print("")
  if len(inDegree) != len(originalSeq):
    return False
  print("Finding the sources")
  sources = deque()
  for key in inDegree:
    if inDegree[key] == 0:
      sources.append(key)
  print("\tsources: ", sources, sep = "")
  print("")
  print("Getting the tolopogical ordering")
  n = 1
  while sources:
    print("\tLoop iteration: ", n)
    n+=1
    if len(sources) > 1:
      print("\t\tThere are more than 1 source, hence, there is more than once way to reconstruct a sequence --> returning False", sep = "")
      return False  # more than one sources mean, there is more than one way to reconstruct the sequence
    if originalSeq[len(sortedOrder)] != sources[0]:
      print("\t\tThe source is different from the original sequence --> returning False", sep = "")
      # the next source(or number) is different from the original sequence
      return False
    tempsource = deque()
    tempsource = copy.copy(sources)
    vertex = sources.popleft()
    print("\t\tPopping from sources: ", tempsource, " --> ", sources, sep = "")
    print("\t\tvertex: ", vertex, sep = "")
    temporder = []
    temporder = copy.copy(sortedOrder)
    sortedOrder.append(vertex)
    print("\t\tAppending to sortedOrder: ", temporder, " --> ", sortedOrder, sep = "")
    n = 1
    for child in graph[vertex]:  # get the node's children to decrement their in-degrees
      print("\t\tInner loop iteration: ", n)
      n+=1
      print("\t\t\tchild: ", child, sep="")
      print("\t\t\tDecrementing the indegree of vertex ", child, ": ", inDegree[child], " --> ", inDegree[child] - 1, sep = "")
      inDegree[child] -= 1
      if inDegree[child] == 0:
        print("\t\t\tindegree of ", child, " = 0", sep = "")
        temps = []
        temps = copy.copy(sources)
        sources.append(child)
        print("\t\t\tAppending to sources: ", temps, " --> ", sources, sep = "")
      print("")
  # if sortedOrder's size is not equal to original sequence's size, there is no unique way to construct
  
  print("")
  print("Length of sortedOrder: ", len(sortedOrder))
  print("Length of originalSeq: ", len(originalSeq))
  if len(sortedOrder) == len(originalSeq):
    print("Since length of the original sequence is equal to the length of our topological order, a unique sequence exists --> returning True")
    return True
  else:
    print("The length of original sequence is not equal to the length of our topological order, a unique sequence exists doesn't exist --> returning False")
    return False
def main():
  inputsequences = [([1, 2, 3, 4], [[1, 2], [2, 3], [3, 4]]), ([1, 2, 3, 4], [[1, 2], [2, 3], [2, 4]]), ([3, 1, 4, 2, 5], [[3, 1, 5], [1, 4, 2, 5]])]
  for i in inputsequences:
    print("Can construct: ", str(can_construct(i[0], i[1])), sep = "")
    print("-"*100+"\n")
main()