I am trying to solve the following code challenge:
There are a given number of pioneers who can build villages. These villages are built on a straight line, and will have a certain order, from left to right. At the very start there are no villages. Once a pioneer has built a village, that village is forever their property, and the pioneer will reside at that village until they move to another one.
The input defines a series of operations, which each specify a pioneer (identified by their 0-based index) and an action for that pioneer:
Action "build": the given pioneer builds a new village at the immediate right of where they currently reside, or if the pioneer has no residence yet, it will become the leftmost village. If there is already a village at the immediate right of the pioneer's residence, then the new village will be inserted between the pioneer's current residence and that next village.
After this operation, the new village becomes the residence of the building pioneer.
Action "move": the given pioneer simply moves their residence to the next village. If there's no next village, the pioneer remains where they are now.
The program must output the owners of the built villages in their order from left to right, taking into account all the actions specified in the input.
First line has two numbers separate by a space: the number of pioneers and the number of actions
Per action the input has a line with two parts separated by space: a pioneer number and the type of action ("build" or "move")
The first line in the output must give the number of villages
For each village (in their proper order), the output should have a separate line with the index of the pioneer that owns the corresponding village.
Input:
2 4
0 build
1 build
1 move
1 build
Expected output:
3
1
0
1
The example has two pioneers (0 and 1). Pioneer 0 creates the first village. Pioneer 1 creates a village that is inserted to the left of that village and then moves to the other village. Finally pioneer 1 creates a village to the right of that village.
I used a linked list data structure for the villages.
Here is my code:
class Village:
def __init__(self, owner=None):
self.owner = owner
self.next = None
class Pioneer:
def __init__(self, position):
self.position = None
def main():
k, n = map(int, input().split())
pioneers = [Pioneer(i) for i in range(k)]
starting_village = Village()
current_village = starting_village
villages = [starting_village]
for i in range(n):
pioneer, action = map(str, input().split())
if action == "move":
if current_village.next is not None:
current_village = current_village.next
pioneers[int(pioneer)].position = current_village
elif action == "build":
new_village = Village(owner=pioneer)
if current_village.next is not None:
new_village.next = current_village.next
current_village.next = new_village
pioneers[int(pioneer)].position = new_village
villages.append(new_village)
m = len(villages) - 1
print(m)
current_village = starting_village.next
while current_village is not None:
print(current_village.owner)
current_village = current_village.next
if __name__ == "__main__":
main()
For the example input my code outputs:
3 1 1 0
...which is evidently not the expected output. I don't understand where it goes wrong. What is my mistake?
The problem is that you use current_village to determine what will be the position and insertion point for the action, no matter what the position is of the involved pioneer. Instead, you need to work with the village where the current pioneer is at. This is not necessarily the same village for each of the pioneers, so working with one current_village is not going to work correctly.
Another issue in your code is that the position attribute is not initialised to the dummy village that you create at the start.
Here is how I would correct your code:
class Village:
def __init__(self, owner=None):
self.owner = owner
self.next = None
class Pioneer:
def __init__(self, id, position):
self.id = id # distinquish id and position
self.position = position # initialise with argument
def main():
k, n = map(int, input().split())
starting_village = Village()
num_villages = 0 # Instead of a list of villages, just track a count of them
# Initialise the pioneers to be at the starting village
pioneers = [Pioneer(i, starting_village) for i in range(k)]
for i in range(n):
pioneerstr, action = input().split()
pioneer = pioneers[int(pioneerstr)] # Get the pioneer instance
# Use the village where the selected pioneer is at
if action == "move":
if pioneer.position.next is not None:
pioneer.position = pioneer.position.next
elif action == "build":
new_village = Village(owner=pioneer)
new_village.next = pioneer.position.next
pioneer.position.next = new_village
pioneer.position = new_village
num_villages += 1
print(num_villages)
current_village = starting_village.next
while current_village is not None:
print(current_village.owner.id)
current_village = current_village.next
if __name__ == "__main__":
main()