Last active
March 1, 2018 22:23
-
-
Save silvia-odwyer/5a52ef573efb3922df821372f5518596 to your computer and use it in GitHub Desktop.
HashCode 2018 Solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| Our solution for the HashCode 2018 Online Qualification Round | |
| Team: PyCharmers | |
| Hub: University College Cork, Ireland | |
| ''' | |
| class Ride: | |
| pickedUp = False | |
| ride_id = 0 | |
| completed = False | |
| taken = False | |
| def __init__(self, ride_id, startInt, endInt, earliest, latest): | |
| self.ride_id = ride_id | |
| self.startInt = startInt | |
| self.endInt = endInt | |
| self.earliest = earliest | |
| self.latest = latest | |
| class Vehicle: | |
| ride = None | |
| vehicle_id = 0 | |
| x = 0 | |
| y = 0 | |
| def __init__(self, vehicle_id, x, y): | |
| self.vehicle_id = vehicle_id | |
| self.x = x | |
| self.y = y | |
| def setRide(self, ride): | |
| self.ride = ride | |
| vehicles = [] | |
| rides = {} | |
| rides_taken = {} | |
| filename = "e_high_bonus.in" | |
| R = 0 | |
| C = 0 | |
| F = 0 | |
| N = 0 | |
| B = 0 | |
| T = 0 | |
| with open(filename,"r") as fileIn: | |
| inputs = fileIn.read().split("\n") | |
| consts = inputs[0].split(" ") | |
| R = int(consts[0]) | |
| C = int(consts[1]) | |
| F = int(consts[2]) | |
| N = int(consts[3]) | |
| B = int(consts[4]) | |
| T = int(consts[5]) | |
| for index in range(1,N+1): | |
| inp = inputs[index].split(" ") | |
| print(inp) | |
| ride = Ride(index - 1, (int(inp[0]),int(inp[1])),(int(inp[2]),int(inp[3])),int(inp[4]),int(inp[5])) | |
| rides[ride.ride_id] = ride | |
| for i in range(F): | |
| vehicle = Vehicle(i + 1, 0, 0) | |
| vehicles.append(vehicle) | |
| rides_taken[vehicle.vehicle_id] = [] | |
| def simulationLoop(): | |
| step = 0 | |
| while not step == T: | |
| runStep(step) | |
| step += 1 | |
| #print(step) | |
| #print("Step %s" % (step)) | |
| for vehicle in vehicles: | |
| if not vehicle.ride == None: | |
| #print("Vehicle %s coordinates (ride %i), %i %i" % (vehicle.vehicle_id, vehicle.ride.ride_id, vehicle.x, vehicle.y)) | |
| pass | |
| continue | |
| #print output | |
| #print("done") | |
| def decideRide(vehicle): | |
| leastRide = 0 | |
| leastDistance = 0 | |
| for ride in rides.values(): | |
| if ride.completed or ride.taken: | |
| continue | |
| if leastRide == 0: | |
| leastRide = ride | |
| leastDistance = abs(leastRide.startInt[0] - vehicle.x) + abs(leastRide.startInt[1] - vehicle.y) | |
| continue | |
| distance = abs(ride.startInt[0] - vehicle.x) + abs(ride.startInt[1] - vehicle.y) | |
| if distance < leastDistance: | |
| leastRide = ride | |
| leastDistance = distance | |
| if not leastRide == 0: | |
| vehicle.ride = leastRide | |
| vehicle.ride.taken = True | |
| rides_taken[vehicle.vehicle_id].append(vehicle.ride.ride_id) | |
| else: | |
| vehicle.ride = None | |
| def moveVehicle(vehicle): | |
| moveTo = (0, 0) | |
| if vehicle.ride.pickedUp: | |
| moveTo = (vehicle.ride.endInt[0], vehicle.ride.endInt[1]) | |
| else: | |
| moveTo = (vehicle.ride.startInt[0], vehicle.ride.startInt[1]) | |
| if moveTo[0] < vehicle.x: | |
| vehicle.x -= 1 | |
| return | |
| elif moveTo[0] > vehicle.x: | |
| vehicle.x += 1 | |
| return | |
| if moveTo[1] < vehicle.y: | |
| vehicle.y -= 1 | |
| return | |
| elif moveTo[1] > vehicle.y: | |
| vehicle.y += 1 | |
| return | |
| def runStep(step): | |
| for vehicle in vehicles: | |
| if vehicle.ride == None: | |
| decideRide(vehicle) | |
| if not vehicle.ride == None: | |
| ride = vehicle.ride | |
| if ride.latest < step: | |
| #we failed | |
| if vehicle.ride.ride_id in rides_taken[vehicle.vehicle_id]: | |
| rides_taken[vehicle.vehicle_id].remove(vehicle.ride.ride_id) | |
| decideRide(vehicle) | |
| if not vehicle.ride == None: | |
| moveVehicle(vehicle) | |
| continue | |
| pass | |
| if vehicle.x == ride.startInt[0] and vehicle.y == ride.startInt[1] and not vehicle.ride.pickedUp: | |
| # the vehicle is at the start location | |
| if step >= ride.earliest: | |
| #go, need to move | |
| vehicle.ride.pickedUp = True | |
| moveVehicle(vehicle) | |
| continue | |
| else: | |
| #wait | |
| continue | |
| elif vehicle.ride.pickedUp and vehicle.x == ride.endInt[0] and vehicle.y == ride.endInt[1]: | |
| # the vehicle is at the end location | |
| pass | |
| # vehicle is in transit, move accordingly | |
| else: | |
| moveVehicle(vehicle) | |
| continue | |
| #vehicle is where its meant to go | |
| if not vehicle.ride == None: | |
| vehicle.ride.completed = True | |
| rides.pop(vehicle.ride.ride_id, None) | |
| decideRide(vehicle) | |
| simulationLoop() | |
| for vehicle in vehicles: | |
| if not vehicle.ride == None: | |
| if not vehicle.ride.completed: | |
| if vehicle.ride.ride_id in rides_taken[vehicle.vehicle_id]: | |
| rides_taken[vehicle.vehicle_id].remove(vehicle.ride.ride_id) | |
| print("Vehicle ID: %s" % vehicle.vehicle_id) | |
| output_filename = "output.txt" | |
| output = open("output.txt", "w") | |
| for vehicle in vehicles: | |
| rides = "" | |
| for ride in rides_taken[vehicle.vehicle_id]: | |
| rides = rides + " %s" % (ride) | |
| line = "%i%s" % (len(rides_taken[vehicle.vehicle_id]), rides) | |
| print(line) | |
| output.write(line + "\n") | |
| output.close() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment