Teaching Kids Programming – Algorithms to Count Houses in a Circular Street

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an object street of class Street that represents a circular street and a positive integer k which represents a maximum bound for the number of houses in that street (in other words, the number of houses is less than or equal to k). Houses’ doors could be open or closed initially.

Initially, you are standing in front of a door to a house on this street. Your task is to count the number of houses in the street.

The class Street contains the following functions which may help you:

• void openDoor(): Open the door of the house you are in front of.
• void closeDoor(): Close the door of the house you are in front of.
• boolean isDoorOpen(): Returns true if the door of the current house is open and false otherwise.
• void moveRight(): Move to the right house.
• void moveLeft(): Move to the left house.

Return ans which represents the number of houses on this street.

Example 1:
Input: street = [0,0,0,0], k = 10
Output: 4
Explanation: There are 4 houses, and all their doors are closed.
The number of houses is less than k, which is 10.

Example 2:
Input: street = [1,0,1,1,0], k = 5
Output: 5
Explanation: There are 5 houses, and the doors of the 1st, 3rd, and 4th house (moving in the right direction) are open, and the rest are closed.
The number of houses is equal to k, which is 5.

Constraints:
n == number of houses
1 <= n <= k <= 103

Algorithms to Count Houses in a Circular Street

The number of the houses has a upper bound k so we can close all the doors by closing one door and move left/right k times. Then we can use the status of the doors as the markers (boolean). As long as the current door is closed, we can count the door by increment the counter and then open it, and then move left or right.

# Definition for a street.
# class Street:
#     def openDoor(self):
#         pass
#     def closeDoor(self):
#         pass
#     def isDoorOpen(self):
#         pass
#     def moveRight(self):
#         pass
#     def moveLeft(self):
#         pass
class Solution:
    def houseCount(self, street: Optional['Street'], k: int) -> int:
        for i in range(0, k):
            street.closeDoor()
            street.moveRight() # either left or right
        r = 0
        while not street.isDoorOpen():
            r += 1
            street.openDoor()
            street.moveRight() # either left or right
        return r

Another slightly different solution is to intentionally having one door open, then count the closed doors and plus one. Here, we don’t bother opening the remaining doors when we walk.

class Solution:
    def houseCount(self, street: Optional['Street'], k: int) -> int:
        for i in range(0, k):
            street.closeDoor()
            street.moveLeft() # either left or right
        ans = 1
        street.openDoor()
        street.moveLeft()
        while not street.isDoorOpen():
            ans += 1
            street.moveLeft()
        return ans

The time complexity is O(K). If you can’t use openDoor, moveLeft and isDoorClose, how can we solve this? Teaching Kids Programming – Algorithms to Count Houses in a Circular Street (with Restrictions – at least one door open)

–EOF (The Ultimate Computing & Technology Blog) —