sparse crossword layout

gistfile1.coffee

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
    else
      @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)
    true

  # 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)
    true

  # 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 + ' '
      else
        line += '   '
    console.log(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())
  print(best.table)
  process.exit()

console.log('could not build a crossboard')
process.exit(1)