-
Notifications
You must be signed in to change notification settings - Fork 42
/
Solution.py
145 lines (100 loc) · 5.96 KB
/
Solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# $$$$$$ $$$$$$$$ $$ $$ $$$$$$$$ $$$$$$ $$ $$ $$$$$$$$ $$$$$$$$ $$$$$$ $$ $$ $$$ $$ $$ #
# $$ $$ $$ $$$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$$ $$ #
# $$ $$ $$$$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$$$ $$ #
# $$$$$$ $$$$$$ $$ $$ $$ $$$$$$ $$$$$$ $$$$$$$$$ $$ $$ $$$$$$ $$$$$$ $$$$$$$$$ $$ $$ $$ $$ $$ #
# $$ $$ $$ $$$$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$$$$$$$$ $$ $$$$ #
# $$ $$ $$ $$ $$$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$$ #
# $$$$$$ $$$$$$$$ $$ $$ $$$$$$$$ $$$$$$ $$ $$ $$$$$$$$ $$$$$$$$ $$$$$$ $$ $$ $$ $$ $$ $$ #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# More Pizza
# Solution for the Practice Round of Google Hash Code 2020
# 27-JAN-2020
# https:#github.com/senesh-deshan/Google-Hash-Code-2020
def solve(MAX, inputList):
solutionIndexList = [] # To store the best solution indexes through out the solution generating
solutionValueList = [] # To store the best solution values through out the solution generating
currentIndexList = [] # To store the current solution indexes through out the solution generating
currentValueList = [] # To store the current solution values through out the solution generating
fullSize = len(inputList)
maxScore = 0 # Stores the maximum score achieved through out the solution generating
startIndex = fullSize # Stores index which the solution generating should start from
sum = 0
# Solution generating starts from the last element of the inputList
# If first element of currentIndexList becomes 0 that means solution generating is finished
while((len(currentIndexList) > 0 and currentIndexList[0] != 0) or len(currentIndexList) == 0):
startIndex = startIndex - 1
for i in range(startIndex, -1, -1): # Used to traverse from end to start of the inputList
currentValue = inputList[i]
tempSum = sum + currentValue
if (tempSum == MAX): # If the temporary sum is equal to target that means the perfect solution is found
sum = tempSum
currentIndexList.append(i) # Add current Pizza index to the solution
currentValueList.append(currentValue) # Add current Pizza value to the solution
break # Go to return solution
elif (tempSum > MAX): # If the temporary sum is greter than target
continue # Try next value
elif (tempSum < MAX): # If the temporary sum is lesser than target
sum = tempSum
currentIndexList.append(i) # Add current Pizza index to the solution
currentValueList.append(currentValue) # Add current Pizza value to the solution
continue # Try next value
if (maxScore < sum): # If currently generated solution has the best score
maxScore = sum # Save its value
solutionIndexList = []
solutionValueList = []
for y in currentIndexList:
solutionIndexList.append(y) # Save the currently best solution indexes
for y in currentValueList:
solutionValueList.append(y) # Save the currently best solution values
if (maxScore == MAX): # If current solution is the perfect solution
break # Stop solution generating
if(len(currentValueList) != 0):
lastVal = currentValueList.pop() # Remove the last element from current values
sum = sum - lastVal # Subtract it from sum
if(len(currentIndexList) != 0):
lastIndex = currentIndexList.pop() # Remove the last element from current indexes
startIndex = lastIndex # Make it as the starting index for the next iteration
if(len(currentIndexList) == 0 and (startIndex == 0)): # If solution generating is almost finished
break # Stop solution generating
print("SCORE = " + str(maxScore)) # Print the score of the best solution
return solutionIndexList # Return indexes list of the best solution
def process(fileName):
# Print data to console
print("")
print("-----------------------")
print(fileName)
print("-----------------------")
# Read the open file by name
inputFile = open(inputFilesDirectory + fileName + ".in", "rt")
# Read file
firstLine = inputFile.readline()
secondLine = inputFile.readline()
inputFile.close()
# Print input data
print("INPUT")
print(firstLine)
print(secondLine)
# Assign parameters
MAX, NUM = list(map(int, firstLine.split()))
# Create the pizza list by reading the file
inputList = list(map(int, secondLine.split()))
outputList = solve(MAX, inputList) # Solve the problem and get output
# Print output data and create output file
print("")
print("OUTPUT")
print(len(outputList))
outputString = ""
for l in outputList:
outputString = outputString + str(l) + " "
print(outputString)
outputFile = open(outputFilesDirectory + fileName + ".out", "w")
outputFile.write(str(len(outputList)) + "\n")
outputFile.write(outputString)
outputFile.close()
inputFilesDirectory = "Input/" # Location of input files
outputFilesDirectory = "Output/" # Location of output files
fileNames = ["a_example", "b_small", "c_medium",
"d_quite_big", "e_also_big"] # File names
for fileName in fileNames: # Take each and every file and solve
process(fileName)