Embed URL


SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

sparse crossword layout

View gist:2004692
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 146 147 148 149
words = [ 'able', 'about', 'above', 'across', 'act', 'action', 'actually', 'add', 'addition', 'adjective', 'afraid', 'Africa', 'after', 'again', 'against', 'age', 'ago', 'agreed', 'ahead', 'air', 'all', 'allow', 'almost', 'alone', 'along', 'already', 'also', 'although', 'always', 'America', 'among', 'amount', 'and', 'angle', 'animal', 'another', 'answer', 'any', 'anything', 'appear', 'apple', 'are', 'area', 'arms', 'army', 'around', 'arrived', 'art', 'ask', 'away', 'baby', 'back', 'bad', 'ball', 'bank', 'base', 'bear', 'beat', 'beautiful', 'became', 'because', 'become', 'bed', 'been', 'before', 'began', 'begin', 'behind', 'being', 'believe', 'bell', 'belong', 'below', 'beside', 'best', 'better', 'between', 'big', 'bill', 'birds', 'bit', 'black', 'block', 'blood', 'blow', 'blue', 'board', 'boat', 'body', 'bones', 'book', 'born', 'both', 'bottom', 'box', 'boy', 'branches', 'break', 'bright', 'bring', 'British', 'broken', 'brother', 'brought', 'brought', 'brown', 'build', 'building', 'built', 'burning', 'business', 'but', 'buy', 'call', 'came', 'can', 'cannot', 'capital', 'captain', 'car', 'care', 'carefully', 'carry', 'case', 'cat', 'catch', 'cattle', 'caught', 'cause', 'cells', 'center', 'cents', 'century', 'certain', 'chance', 'change', 'chart', 'check', 'chief', 'child', 'children', 'choose', 'church', 'circle', 'city', 'class', 'clean', 'clear', 'climbed', 'close', 'clothes', 'cloud', 'coast', 'cold', 'color', 'column', 'come', 'common', 'company', 'compare', 'complete', 'compound', 'conditions', 'consider', 'consonant', 'contain', 'continued', 'control', 'cook', 'cool', 'copy', 'corn', 'corner', 'correct', 'cost', 'cotton', 'could', 'count', 'country', 'course', 'covered', 'cows', 'create', 'cried', 'crops', 'cross', 'crowd', 'current', 'cut', 'dance', 'dark', 'day', 'dead', 'deal', 'death', 'decided', 'decimal', 'deep', 'describe', 'desert', 'design', 'details', 'determine', 'developed', 'dictionary', 'did', 'died', 'difference', 'different', 'difficult', 'direct', 'direction', 'discovered', 'distance', 'divided', 'division', 'doctor', 'does', 'dog', 'dollars', 'done', 'door', 'down', 'draw', 'drawing', 'dress', 'drive', 'drop', 'dry', 'during', 'each', 'early', 'ears', 'earth', 'east', 'easy', 'eat', 'edge', 'effect', 'eggs', 'eight', 'either', 'electric', 'elements', 'else', 'end', 'energy', 'engine', 'England', 'English', 'enjoy', 'enough', 'entered', 'entire', 'equal', 'equation', 'especially', 'Europe', 'even', 'evening', 'ever', 'every', 'everyone', 'everything', 'exactly', 'example', 'except', 'exciting', 'exercise', 'expect', 'experience', 'experiment', 'explain', 'express', 'eye', 'face', 'fact', 'factories', 'factors', 'fall', 'family', 'famous', 'far', 'farm', 'farmers', 'fast', 'father', 'fear', 'feel', 'feeling', 'feet', 'fell', 'felt', 'few', 'field', 'fig', 'fight', 'figure', 'filled', 'finally', 'find', 'fine', 'fingers', 'finished', 'fire', 'first', 'fish', 'fit', 'five', 'flat', 'floor', 'flow', 'flowers', 'fly', 'follow', 'food', 'foot', 'for', 'force', 'forest', 'form', 'forward', 'found', 'four', 'fraction', 'France', 'free', 'French', 'fresh', 'friends', 'from', 'front', 'fruit', 'full', 'fun', 'game', 'garden', 'gas', 'gave', 'general', 'get', 'girl', 'give', 'glass', 'God', 'gold', 'gone', 'good', 'got', 'government', 'grass', 'great', 'Greek', 'green', 'grew', 'ground', 'group', 'grow', 'guess', 'gun', 'had', 'hair', 'halt', 'hand', 'happened', 'happy', 'hard', 'has', 'hat', 'have', 'head', 'hear', 'heard', 'heart', 'heat', 'heavy', 'held', 'help', 'her', 'here', 'high', 'hill', 'him', 'himself', 'his', 'history', 'hit', 'hold', 'hole', 'home', 'hope', 'horse', 'hot', 'hours', 'house', 'how', 'however', 'huge', 'human', 'hundred', 'hunting', 'ice', 'idea', 'important', 'inches', 'include', 'increase', 'Indian', 'indicate', 'industry', 'information', 'insects', 'inside', 'instead', 'instruments', 'interest', 'interest', 'into', 'iron', 'island', 'its', 'itself', 'Japanese', 'job', 'joined', 'jumped', 'just', 'keep', 'kept', 'key', 'killed', 'kind', 'king', 'knew', 'know', 'known', 'lady', 'lake', 'land', 'language', 'large', 'last', 'later', 'laughed', 'law', 'lay', 'lead', 'learn', 'least', 'leave', 'led', 'left', 'legs', 'length', 'less', 'let', 'letter', 'level', 'lie', 'life', 'lifted', 'light', 'like', 'line', 'list', 'listen', 'little', 'live', 'located', 'long', 'look', 'lost', 'lot', 'loud', 'love', 'low', 'machine', 'made', 'main', 'major', 'make', 'man', 'many', 'map', 'march', 'mark', 'match', 'material', 'matter', 'may', 'maybe', 'mean', 'measure', 'meat', 'meet', 'melody', 'members', 'men', 'metal', 'method', 'middle', 'might', 'mile', 'milk', 'million', 'mind', 'mine', 'minutes', 'miss', 'modern', 'molecules', 'moment', 'money', 'months', 'moon', 'more', 'morning', 'most', 'mother', 'mountain', 'mouth', 'move', 'movement', 'much', 'music', 'must', 'name', 'nation', 'natural', 'near', 'necessary', 'need', 'never', 'new', 'next', 'night', 'nor', 'north', 'northern', 'nose', 'not', 'note', 'nothing', 'notice', 'noun', 'now', 'number', 'numeral', 'object', 'observe', 'ocean', 'off', 'office', 'often', 'oil', 'old', 'once', 'one', 'only', 'open', 'opposite', 'order', 'other', 'our', 'out', 'outside', 'over', 'own', 'oxygen', 'page', 'paint', 'pair', 'paper', 'paragraph', 'park', 'part', 'particular', 'party', 'passed', 'past', 'pattern', 'pay', 'people', 'per', 'perhaps', 'period', 'person', 'phrase', 'picked', 'picture', 'piece', 'place', 'plains', 'plan', 'plane', 'plant', 'plants', 'play', 'please', 'plural', 'poem', 'point', 'pole', 'poor', 'position', 'possible', 'pounds', 'power', 'practice', 'prepared', 'presidents', 'pretty', 'printed', 'probably', 'problem', 'process', 'produce', 'products', 'property', 'provide', 'pulled', 'pushed', 'put', 'questions', 'quickly', 'quiet', 'quite', 'race', 'radio', 'rain', 'raised', 'ran', 'rather', 'reached', 'read', 'ready', 'really', 'reason', 'received', 'record', 'red', 'region', 'remain', 'remember', 'repeated', 'report', 'represent', 'resent', 'rest', 'result', 'return', 'rhythm', 'rich', 'ride', 'right', 'ring', 'rise', 'river', 'road', 'rock', 'rolled', 'room', 'root', 'rope', 'rose', 'round', 'row', 'rule', 'run', 'safe', 'said', 'sail', 'same', 'sand', 'sat', 'save', 'saw', 'say', 'scale', 'school', 'science', 'scientists', 'score', 'sea', 'seat', 'second', 'section', 'see', 'seeds', 'seem', 'seen', 'sell', 'send', 'sense', 'sent', 'sentence', 'separate', 'serve', 'set', 'settled', 'seven', 'several', 'shall', 'shape', 'sharp', 'she', 'ship', 'shoes', 'shop', 'short', 'should', 'shoulder', 'shouted', 'show', 'shown', 'side', 'sight', 'sign', 'signal', 'silent', 'similar', 'simple', 'since', 'sing', 'sir', 'sister', 'sit', 'six', 'size', 'skin', 'sky', 'sleep', 'sleep', 'slowly', 'small', 'smell', 'smiled', 'snow', 'soft', 'soil', 'soldiers', 'solution', 'some', 'someone', 'something', 'sometimes', 'son', 'song', 'soon', 'sound', 'south', 'southern', 'space', 'speak', 'special', 'speed', 'spell', 'spot', 'spread', 'spring', 'square', 'stand', 'stars', 'start', 'state', 'statement', 'stay', 'steel', 'step', 'stick', 'still', 'stone', 'stood', 'stop', 'store', 'story', 'straight', 'strange', 'stream', 'street', 'stretched', 'string', 'strong', 'students', 'study', 'subject', 'substances', 'such', 'suddenly', 'suffix', 'sugar', 'suggested', 'sum', 'summer', 'sun', 'supply', 'suppose', 'sure', 'surface', 'surprise', 'swim', 'syllables', 'symbols', 'system', 'table', 'tail', 'take', 'talk', 'tall', 'teacher', 'team', 'tell', 'temperature', 'ten', 'terms', 'test', 'than', 'that', 'the', 'their', 'them', 'themselves', 'then', 'there', 'these', 'they', 'thick', 'thin', 'thing', 'think', 'third', 'this', 'those', 'though', 'thought', 'thousands', 'three', 'through', 'thus', 'tied', 'time', 'tiny', 'today', 'together', 'told', 'tone', 'too', 'took', 'tools', 'top', 'total', 'touch', 'toward', 'town', 'track', 'trade', 'train', 'train', 'travel', 'tree', 'triangle', 'trip', 'trouble', 'truck', 'true', 'try', 'tube', 'turn', 'two', 'type', 'uncle', 'under', 'underline', 'understand', 'unit', 'until', 'upon', 'use', 'usually', 'valley', 'value', 'various', 'verb', 'very', 'view', 'village', 'visit', 'voice', 'vowel', 'wait', 'walk', 'wall', 'want', 'war', 'warm', 'was', 'wash', 'Washington', 'watch', 'water', 'waves', 'way', 'wear', 'weather', 'week', 'weight', 'well', 'went', 'were', 'west', 'western', 'what', 'wheels', 'when', 'where', 'whether', 'which', 'while', 'white', 'who', 'whole', 'whose', 'why', 'wide', 'wife', 'wild', 'will', 'win', 'wind', 'window', 'wings', 'winter', 'wire', 'wish', 'with', 'within', 'without', 'woman', 'women', 'wonder', 'wood', 'word', 'work', 'workers', 'world', 'would', 'write', 'written', 'wrong', 'wrote', 'yard', 'year', 'yellow', 'yes', 'yet', 'you', 'young', 'your', 'yourself' ]
class Point
constructor: (@row, @col, @horizontal) ->
if @horizontal
@colinc = 1
@rowinc = 0
@colinc = 0
@rowinc = 1
class Board
constructor: ->
@intersections = 0
@last = {row: 0, col: 0}
@table = []
# The more square it is, and the more dense it is, the more we like it (and the worse the rank is)
# but they might need to be weighed...dunno, not sure about this ranking at all
rank: ->
return @_rank if @_rank?
x = @last.col
y = @last.row
for row in [0..@last.row]
for col in [0..@last.col]
if @table[row]?[col]?
x = col if col < x
y = row if row < y
@_rank = Math.abs(@last.col - x - @last.row - y) + @last.row + @last.col
return @_rank
add: (word) ->
return @addFirst(word) if @last.col == 0 && @last.row == 0
point = @findPoint(word)
return false unless point?
@insert(word, point)
# first word can go anywhere, so let's just pick a random spot
addFirst: (word) ->
point = new Point(Math.floor(Math.random() * 15), Math.floor(Math.random() * 15), Math.floor(Math.random() * 2) == 0)
@insert(word, point)
# Finds the best place to put a word
# Since we scan the entire table from top-left to button-right, we only need to try to position the word
# in two directions (left-to-right and up-to-down)
findPoint: (word) ->
topScore = 0
topPoint = null
for row in [0..@last.row]
for col in [0..@last.col]
point = new Point(row, col, true)
score = @score(word, point)
if score > topScore
topPoint = point
topScore = score
point = new Point(row, col, false)
score = @score(word, point)
if score > topScore
topPoint = point
topScore = score
@intersections += topScore
return topPoint
# scores the position of a word from a given point based on how many other words it intersects
# the more words interesected, the higher the score
# scores 0 if the word doesn't go anywhere, or if it collides with another word
score: (word, point) ->
[row, col] = [point.row, point.col]
l = word.length
return 0 if @table[row-point.rowinc]?[col-point.colinc]? || @table[row + (l * point.rowinc)]?[col + (l * point.colinc)]?
intersections = 0
for c in word
intersection = false
theRow = @table[row]
if theRow? && theRow[col]?
return 0 if theRow[col] != c
intersections += 1
intersection = true
unless intersection
return 0 if point.horizontal && (@table[row+1]?[col]? || (row > 0 && @table[row-1]?[col]?))
return 0 if !point.horizontal && (theRow?[col+1]? || (col > 0 && theRow?[col-1]?))
col += point.colinc
row += point.rowinc
return intersections
insert: (word, point) ->
[col, row] = [point.col, point.row]
for c in word
@table[row] = [] unless @table[row]?
@table[row][col] = c
col += point.colinc
row += point.rowinc
@last.col = col if col > @last.col
@last.row = row if row > @last.row
print = (table) ->
for row in table
line = ''
continue unless row?
for col in row
if col?
line += ' ' + col + ' '
line += ' '
buildBoard = (words) ->
clone = words.slice(0)
clone.sort -> 0.5 - Math.random()
board = new Board()
for i in [1..500]
word = clone.shift()
clone.push(word) unless board.add(word)
return board if clone.length == 0
return null
words.sort -> 0.5 - Math.random()
words = words.slice(0, 25)
best = null
for i in [1..10]
board = buildBoard(words)
continue unless board?
best = board if best == null || board.rank() < best.rank()
if best?
console.log(best.intersections, best.rank())
console.log('could not build a crossboard')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.