CODEWITHSUNDEEP
pythonnested-lists
Yassin Bahri
Yassin Bahri

Reputation: 11

lockboxes problem: list inside a list and each list contains keys to unlock the other boxes

Here is the problem: You have n number of locked boxes in front of you. Each box is numbered sequentially from 0 to n - 1 and each box may contain keys to the other boxes.

boxes is a list of lists

A key with the same number as a box opens that box

You can assume all keys will be positive integers

The first box boxes[0] is unlocked

Return True if all boxes can be opened, else return False

This is my code but I have found in some cases that it takes all the values of the lists and stores them even the ones that can't be unlocked:

def canUnlockAll(boxes):
    newlist = []
    k = len(boxes)
    for i in boxes:
        if len(i) == 0 and i is not boxes[k-1]:
            return False
        for j in i:
            newlist.append(j)
    print(newlist)
    for index, keys in enumerate(boxes):
        if index in newlist or index < k-1:
            return True
        else:
            return False

And this is the test case I used:

#!/usr/bin/python3

canUnlockAll = __import__('0-lockboxes').canUnlockAll

boxes = [[1, 4, 6], [2], [0, 4, 1], [5, 6, 2], [3], [4, 1], [6], [7]]
print(canUnlockAll(boxes), "\t: False")
print('-----------------------------')

My issue is how to fix the issue where the box in index 7 is unlocked while it shouldn't be unlocked!

Upvotes: 0

Views: 1738

Answers (4)

MAA
MAA

Reputation: 1

This is the Fastest|Simplest way I could find:

def canUnlockAll(boxes):
    """ Method that determines if all boxes can be opened """

    for key in range(1, len(boxes)):
        flag = False
        for box in range(len(boxes)):
            if key in boxes[box] and box != key:
                flag = True
                break
        if not flag:
            return False

    return True

Passed all Test cases with success

boxes = [[]]
print(canUnlockAll(boxes))

boxes = [[1], [2], [3], [4], []]
print(canUnlockAll(boxes))

boxes = [[1, 4, 6], [2], [0, 4, 1], [5, 6, 2], [3], [4, 1], [6]]
print(canUnlockAll(boxes))

boxes = [[1, 4], [2], [0, 4, 1], [3], [], [4, 1], [5, 6]]
print(canUnlockAll(boxes))

boxes = [[], [2], [1], [4], []]
print(canUnlockAll(boxes))

Upvotes: 0

Abubeker Abdullahi
Abubeker Abdullahi

Reputation: 1

How about this

def canUnlockAll(boxes):
    """method that determines if all the boxes can be opened.

    Args:
        boxes (a list of lists): contain keys to the other boxes

    Returns:
        boolean: True if all boxes can be opened, else return False
    """
    availableKeys = set(boxes[0])
    openedBoxes = set([0])

    while availableKeys:
        newKeys = set()
        for key in availableKeys:
            if key not in openedBoxes and key < len(boxes):
                openedBoxes.add(key)
                newKeys.update(boxes[key])

        availableKeys = newKeys - openedBoxes

    return len(openedBoxes) == len(boxes)

Upvotes: 0

Jane Ng&#39;ethe
Jane Ng&#39;ethe

Reputation: 9

I faced a similar task and this is the code I used. I've tested it with your test case and it worked. Maybe you can try it.

def canUnlockAll(boxes):
    unlocked = [0]
    for box_id, box in enumerate(boxes):
        if not box:
            continue
        for key in box:
            if key < len(boxes) and key not in unlocked and key != box_id:
                unlocked.append(key)
    if len(unlocked) == len(boxes):
        return True
    return False

Upvotes: 0

Anass ABEA
Anass ABEA

Reputation: 479

try this code :

def join(T,R):
  res =[]
  for e in R:
    res += T[e]
  return res

def canUnlockAll(boxes):
  index = 0
  total = list(set(boxes[0])| {0})
  added = True
  while added:
    added = False
    for j in join(boxes,total[index:]):
      if j not in total:
        total.append(j)
        index +=1
        added= True
  print(total)
  
  return len(total)==len(boxes)

Tests :

boxes = [[1], [2], [3], [4], [5], [6], [7], [0]]
print(canUnlockAll(boxes), "\t: True\n")

boxes = [[1, 4, 6], [2], [0, 4, 1], [5, 6, 2], [3], [4, 1], [6], [7]]
print(canUnlockAll(boxes), "\t: False")

Results:

[0, 1, 2, 3, 4, 5, 6, 7]
True    : True

[0, 1, 4, 6, 2, 3, 5]
False   : False

Upvotes: 0

Related Questions