Python
Exhaustively tries different combinations of folds for the first few folds, then does the rest of the folds using a greedy approach.
The exhaustive approach is bounded within a reasonable range of folds in the center, such that it won't take forever, while not ignoring too many possible folds to yield a good minimum.
Ran using pypy on my macbook air.
Answers:
20*20D9R15R6D11R10R9D10R11
40*20D6D13D9R19R21R20D11D10
40*40D21R21R11D19R23R20D23D15
20*80D33D47D40R10D39D41R9R11
Outputs:
Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.2
Time taken: 4.016076s
Score: 7.91125
20*20D9R15R6D11R10R9D10R11
Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.2
Time taken: 28.529278s
Score: 16.34375
40*20D6D13D9R19R21R20D11D10
Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.25
Time taken: 98.430465s
Score: 42.13
40*40D21R21R11D19R23R20D23D15
Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.25
Time taken: 234.873787s
Score: 32.30875
20*80D33D47D40R10D39D41R9R11
Total Score: 7.91125 + 16.34375 + 42.13 + 32.30875 = 98.69375
Code:
import time, math
from collections import deque
numberOfFolds = 8 # Total number of folds
startTime = time.clock()
exec "grid = ("+"""
1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1
1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1
0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0
0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1
0 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0
1 0 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 1
0 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0
1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1
1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 0
0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1
0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0
0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1
0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1
1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1
0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0
0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0
0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1 1 1
""".replace(" ",",").replace("\n","],[")[2:-2]+")"
def getAverage(grid):
count = total = 0
for j in grid:
for i in j:
count += 1
total += i
return total/float(count)
def getScore(grid, average):
score = 0
for j in grid:
for i in j:
score += abs(average-i)
return score
def downFoldedGrid(grid, row, width, height, copy=True):
if copy: grid = [r[:] for r in grid]
foldRange = min(row, height-row)
for j in xrange(foldRange):
rowRef1 = grid[row+j]
rowRef2 = grid[row-1-j]
for i in xrange(width):
rowRef1[i] = rowRef2[i] = (rowRef1[i] + rowRef2[i]) * .5
return grid
def downFoldedScore(grid, score, average, row, width, height):
foldRange = min(row, height-row)
average2 = 2*average
for j in xrange(foldRange):
rowRef1 = grid[row+j]
rowRef2 = grid[row-1-j]
a = b = c = 0
for i in xrange(width):
a = rowRef1[i]
b = rowRef2[i]
c = a+b
score += abs(average2-c) - abs(average-a) - abs(average-b)
return score
def rightFoldedGrid(grid, column, width, height, copy=True):
if copy: grid = [r[:] for r in grid]
foldRange = min(column, width-column)
for j in xrange(height):
rowRef = grid[j]
for i in xrange(foldRange):
a = column+i
b = column-1-i
rowRef[a] = rowRef[b] = (rowRef[a] + rowRef[b]) * .5
return grid
def rightFoldedScore(grid, score, average, column, width, height):
foldRange = min(column, width-column)
average2 = 2*average
for j in xrange(height):
rowRef = grid[j]
a = b = c = 0
for i in xrange(foldRange):
a = rowRef[column+i]
b = rowRef[column-1-i]
c = a+b
score += abs(average2-c) - abs(average-a) - abs(average-b)
return score
def bestFoldsGreedy(grid, average, maxFolds, width, height):
score = getScore(grid, average)
folds = []
append = folds.append
for z in xrange(maxFolds):
bestFold = 0
bestFoldScore = score
bestFoldGrid = grid
for i in xrange(1, width): #Try all right folds
foldScore = rightFoldedScore(grid, score, average, i, width, height)
if foldScore < bestFoldScore:
bestFold = i
bestFoldScore = foldScore
for i in xrange(1, height): #Try all down folds
foldScore = downFoldedScore(grid, score, average, i, width, height)
if foldScore < bestFoldScore:
bestFold = -i
bestFoldScore = foldScore
if bestFold:
append(bestFold)
score = bestFoldScore
if bestFold > 0: rightFoldedGrid(grid, bestFold, width, height, False)
else: downFoldedGrid(grid, -bestFold, width, height, False)
return score, folds
# Get the height and width
height = len(grid)
width = len(grid[0])
# Transpose the grid if height > width for better locality of reference
transposed = False
if height > width:
grid = [[grid[i][j] for i in range(height)] for j in range(width)]
transposed = True
height, width = width, height
# The exhaustive grids and folds attempted
exhaustiveGridsAndFolds = deque([(grid,[])])
popleft = exhaustiveGridsAndFolds.popleft
append = exhaustiveGridsAndFolds.append
# Set the bounds to exhaustively test for
exhaustiveLevels = 3
prunePadding = [0.2, 0.25][width*height > 1000]
leftBound = int(max(width*prunePadding, 1))
rightBound = int(width*(1.0-prunePadding))
topBound = int(max(height*prunePadding, 1))
bottomBound = int(height*(1.0-prunePadding))
# Populate the exhaustive grids and folds
while 1:
grid, folds = popleft()
if len(folds) == exhaustiveLevels:
append((grid, folds))
break
for i in xrange(leftBound, rightBound):
if i not in folds:
append((rightFoldedGrid(grid, i, width, height), folds+[i]))
for i in xrange(topBound, bottomBound):
if -i not in folds:
append((downFoldedGrid(grid, i, width, height), folds+[-i]))
# Test all the exhaustive grids and folds greedily
average = getAverage(grid)
bestFinalScore = getScore(grid, average)
bestFinalFolds = []
numberOfGreedyFolds = numberOfFolds-exhaustiveLevels
while exhaustiveGridsAndFolds:
grid, exhaustiveFolds = popleft()
finalScore, greedyFolds = bestFoldsGreedy(grid, average, numberOfGreedyFolds, width, height)
if finalScore <= bestFinalScore:
bestFinalScore = finalScore
bestFinalFolds = exhaustiveFolds + greedyFolds
# Repeat the last fold till the total number of folds if needed
if len(bestFinalFolds) < numberOfFolds:
bestFinalFolds += [bestFinalFolds[-1]]*(numberOfFolds-len(bestFinalFolds))
# Print the best result
foldsString = ""
down = "D"
right = "R"
if transposed:
down, right = right, down
width, height = height, width
for fold in bestFinalFolds:
if fold > 0: foldsString += right+str(fold)
elif fold < 0: foldsString += down+str(-fold)
print "Exhaustive folds levels: " + str(exhaustiveLevels)
print "Percentage pruned from sides from exhaustive folds: " + str(prunePadding)
print "Time taken: " + str(time.clock()-startTime) + "s"
print "Score: " + str(bestFinalScore)
print str(width) + "*" + str(height) + foldsString
1I think it's better if you have some test cases, and that participants are expected to give code that produces the sequence, instead of just giving the sequence. – justhalf – 2014-07-10T11:20:19.363
I know that would be ideal but how could I make sure that people aren't hiding their sequence in a program that looks like a possible algorithm? – Calvin's Hobbies – 2014-07-10T11:39:39.687
You can quote standard loopholes and those entries will be invalidated by the community (or more precisely, by you when community points it out) when they found it. And you'd better give more test cases. EDIT: I think one test case is fine, though, if it's difficult enough, which I think so for your current test case.
– justhalf – 2014-07-10T11:56:00.4631Another option is to ask people to give the sequence that they got with their code, but ask them to provide a hash (say SHA-256) of their code as proof that they actually produce it using their own work. I remember seeing that kind of mechanism some time ago, but I can't remember. Can anybody point to that challenge? – justhalf – 2014-07-10T12:00:24.253
1Another way to prohibit hard-coding is to make the challenge open to other test cases as well. – Howard – 2014-07-10T12:00:28.353
I do want people to include their code so I made that a requirement. Hopefully people will stay honest but if there is contention then the person who posted first will almost certainly win. – Calvin's Hobbies – 2014-07-10T12:19:31.657
@Howard and others, how would making more test cases help? I figured it was easy enough for people to generate their own random grids. Brute force is out as there are (19*39)^8 potential solutions so checking one per nanosecond would still take a couple million years. – Calvin's Hobbies – 2014-07-10T12:30:15.253
@justhalf this was the challenge with the hashes, for different reasons though.
– Martin Ender – 2014-07-10T12:32:51.5471
@Calvin'sHobbies I'd prefer a larger set of test cases, too, to be honest, because some algorithms might fare better on certain grids than others. What you could do is what I did with Vector Racing that each participant may add a test case to the benchmark set. In that case, you'd have to take it on you to test and score all submissions though, because you can't expect early participants to rerun their code with test cases added later.
– Martin Ender – 2014-07-10T12:34:27.213I see, I didn't think of having multiple grids count towards the score but I like it. I think I'll add 3 or 4 more grids to the gamut. – Calvin's Hobbies – 2014-07-10T12:41:37.333
1@Calvin'sHobbies Brute force is (19+39)^8 (minus some symmetries) which is much more feasable. – Howard – 2014-07-10T17:15:23.183