Last active
August 29, 2015 13:57
-
-
Save drewhutchison/9747015 to your computer and use it in GitHub Desktop.
Quick script to brute-force http://ask.metafilter.com/259160/How-many-different-colors-does-this-quilt-need
This file contains hidden or 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
| #!/usr/bin/env python | |
| from copy import deepcopy | |
| X = 10 | |
| Y = 12 | |
| grid = [[None for i in range(X)] for j in range(Y)] | |
| # patterns will be a dict of dict of lists, such that: | |
| # patterns[c1][c2] = [(dx, dy), ...] where (dx, dy) are the offsets | |
| # from a tile of color c2 to a tile of color c1 | |
| patterns = {} | |
| for j in range(Y): | |
| for i in range(X): | |
| c = 0 | |
| while True: | |
| c += 1 | |
| # check if we're the same color of adjacent tiles | |
| print 'on tile ', i, j, ' trying ', c | |
| if j>0: | |
| if i>0: | |
| if grid[j-1][i-1] == c: | |
| print 'matches above left' | |
| continue | |
| if i+1<X: | |
| if grid[j-1][i+1] == c: | |
| print 'matches above right' | |
| continue | |
| if grid[j-1][i] == c: | |
| print 'matches above' | |
| continue | |
| if i>0: | |
| if grid[j][i-1] == c: | |
| print 'matches left' | |
| continue | |
| # now check the offsets. the test algorithm is destructive, so | |
| # copy the dict | |
| if not c in patterns: patterns[c] = {} | |
| newpatterns = deepcopy(patterns) | |
| flag = False | |
| # check all tiles in above rows and to the left of us in present row | |
| for ii,jj in [(ii,jj) | |
| for jj in range(j) | |
| for ii in range(X)] + [(ii, j) | |
| for ii in range(i)]: | |
| dx = ii-i | |
| dy = jj-j | |
| testcolor = grid[jj][ii] | |
| matches = newpatterns[c].setdefault(testcolor, []) | |
| if (dx, dy) in matches: | |
| print 'matches %d at (%d, %d)' % (testcolor, dx, dy) | |
| flag = True | |
| break | |
| newpatterns[c][testcolor].append((dx,dy)) | |
| # can't tell if we broke the loop or fell off the end. | |
| # flags are unpythonic but this was a quick hack. if the flag was | |
| # never set, we didn't conflict with any existing patterns, so | |
| # overwrite the old dict with the ones we've testing by the append | |
| # statement above | |
| if not flag: | |
| patterns = newpatterns | |
| break | |
| print 'setting (%d, %d) to %d' % (i, j, c) | |
| grid[j][i] = c | |
| for line in grid: | |
| print ' '.join(['%02d' % tile for tile in line]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment