# tags: wordsearch, words, puzzle, awk, code
#
# awk script that generates a random wordsearch puzzle
# Michael Sanders 2023
# https://busybox.neocities.org/notes/wordsearch.txt
#
# usage: awk -f wordsearch.txt
#
# each puzzle contains 12 words grouped by category,
# randomly dispersed throughout the grid in any position
# of horizontally, vertically, or diagonally, shown below
# is output from the 1st puzzle...
#
# ANIMALS
#
# V Q T A M E R K Y K I C Q M R  TURTLE
# Y G O R I L L A X S L F X U E  WALRUS
# T U R T L E G S U Q E Y W S E  ZEBRA
# W Y O Q G M W C L U O P W S P  AARDVARK
# Z E B R A S Q Y O I P X T O O  ANTELOPE
# G A A R D V A R K R A W A P L  BUFFALO
# H R J T I B B A R R R A W O E  GORILLA
# R P F L I C D B I E D L T H T  LEOPARD
# A E J C L T R V V L K R C N N  OPOSSUM
# N Q G D B U F F A L O U A V A  RABBIT
# Z Y B I Q Y U Y E M D S K O N  SQUIRREL
# G P M Q T Z Q U M N M B B R Y  TIGER
#
# 50 categories that include...
#
# animals, sitcoms, zodiac, indian tribes, fastfood
# ships, trees, rock and roll, months, rulers, shapes
# directions, colors, canines, snacks, natural disasters
# furnishings, opposites, countries, paper products
# landscaping, units, dance crazes, tyrants, astronomy
# breakfast, gemstones, apparel, bugs, office supplies
# cardgames, minerals, franchise, paranormal, veggies
# tools, authors, thanksgiving, metals, games, spirits
# condiments, flowers, spices, kitchenware, cities
# nuts, moutain ranges, christmas, fruit

BEGIN {
  srand()
  ROWS=12; COLS=15 # grid dimensions
  create_puzzle()
}

function create_puzzle() {
  # get a category & split its words
  split(getcat(), tmp, ",")

  printf "%s\n\n", tmp[1]

  # initialize list of words to place in grid
  for (i = 2; i <= length(tmp); i++) toPlace[i-1] = tmp[i]

  attempts = 0; max_attempts = 1000

  while (attempts < max_attempts) {
    empty_grid()
    all_words_placed = 1
    for (word in toPlace) {
      wordToPlace = remove_spaces(toPlace[word])

      # sneaky: 30% probability of a reversed word
      if (rand() < 0.3) wordToPlace = reverse_word(wordToPlace)

      placed = 0
      for (try = 1; try <= 100 && !placed; try++) {
        x = int(1 + rand() * ROWS)
        y = int(1 + rand() * COLS)
        direction = int(rand() * 3)
        dx = (direction == 0 ? 1 : (direction == 1 ? 0 : 1))
        dy = (direction == 0 ? 0 : (direction == 1 ? 1 : 1))
        if (can_place_word(wordToPlace, x, y, dx, dy)) {
          place_word(wordToPlace, x, y, dx, dy)
          placed = 1
        }
      }
      if (!placed) {
        all_words_placed = 0
        break
      }
    }
    if (all_words_placed) break
    attempts++
  }

  if (attempts == max_attempts) {
    print "Failed to place all words for category", tmp[1], "after", max_attempts, "attempts."
    exit 1
  }

  # fill grid with random letters
  for (i = 1; i <= ROWS; i++) {
    for (j = 1; j <= COLS; j++) {
      if (grid[i,j] == "-") {
        grid[i,j] = sprintf("%c", 65 + int(rand() * 26)) # ASCII values A-Z
      }
    }
  }

  # print grid with original words to the right
  idx = 1
  for (i in toPlace) {
    for (j = 1; j <= COLS; j++) {
      printf("%s ", grid[idx,j])
    }
    printf(" %s\n", toPlace[i])
    idx++
  }
}

function empty_grid(    i, j) {
  for (i = 1; i <= ROWS; i++)
    for (j = 1; j <= COLS; j++)
      grid[i,j] = "-"
}

function is_valid(x, y) { return x >= 1 && x <= ROWS && y >= 1 && y <= COLS }

function can_place_word(word, x, y, dx, dy, i) {
  for (i = 1; i <= length(word); i++) {
    if (!is_valid(x, y) ||
      (grid[x,y] != "-" && grid[x,y] != substr(word, i, 1))) {
    return 0
    }
    x += dx
    y += dy
  }
  return 1
}

function place_word(word, x, y, dx, dy, i) {
  for (i = 1; i <= length(word); i++) {
    grid[x,y] = substr(word, i, 1)
    x += dx
    y += dy
  }
}

function remove_spaces(word,    i, c, result) {
  result = ""
  for (i = 1; i <= length(word); i++) {
    c = substr(word, i, 1)
    if (c != " ") result = result c
  }
  return result
}

function reverse_word(word,    i, r) {
  for (i = length(word); i > 0; i--) {
    r = r substr(word, i, 1)
  }
  return r
}

function getcat(    c) {
  c[ 1] = "ANIMALS,AARDVARK,ANTELOPE,BUFFALO,GORILLA,LEOPARD,OPOSSUM,RABBIT,SQUIRREL,TIGER,TURTLE,WALRUS,ZEBRA"
  c[ 2] = "SITCOMS,BEWITCHED,BOSOM BUDDIES,CHEERS,FATHER KNOWS BEST,HAPPY DAYS,I DREAM OF JEANNIE,I LOVE LUCY,MASH,SANFORD AND SON,THE BRADY BUNCH,THE JEFFERSONS,THREES COMPANY"
  c[ 3] = "ZODIAC,ARIES,TAURUS,GEMINI,CANCER,LEO,VIRGO,LIBRA,SCORPIO,SAGITTARIUS,CAPRICORN,AQUARIUS,PISCES"
  c[ 4] = "INDIAN TRIBES,APACHE,BLACKFOOT,CHEROKEE,COMANCHE,CROW,HOPI,MOHICAN,NAVAJO,PAWNEE,SEMINOLE,SHAWNEE,SIOUX"
  c[ 5] = "FASTFOOD,BURITTO,CHEESEBURGER,DONUTS,FRIES,HOTDOG,ICECREAM,NUGGETS,ONIONRINGS,PIZZA,SHAKE,SOFTDRINK,TACO"
  c[ 6] = "SHIPS,BOAT,CANOE,CLIPPER,CRUISER,DESTROYER,DINGHY,PONTOON,RAFT,SCHOONER,TANKER,TRAWLER,YACHT"
  c[ 7] = "TREES,ASH,BEECH,BIRCH,ELM,EVERGREEN,MAPLE,OAK,PINE,SEQUOIA,SPRUCE,SYCAMORE,WILLOW"
  c[ 8] = "ROCK AND ROLL,BUDDY HOLLY,CARL PERKINS,CHUCK BERRY,THE COASTERS,EDDIE COCHRAN,ELVIS PRESLEY,FATS DOMINO,JERRY LEE LEWIS,LITTLE RICHARD,THE BIGBOPPER,EVERLY BROTHERS,THE PLATTERS"
  c[ 9] = "MONTHS,JANUARY,FEBRUARY,MARCH,APRIL,MAY,JUNE,JULY,AUGUST,SEPTEMBER,OCTOBER,NOVEMBER,DECEMBER"
  c[10] = "RULERS,CHANCELLOR,CHIEF,CZAR,EMPEROR,KING,LORD,MONARCH,PHARAOH,PRESIDENT,PRIME MINISTER,SULTAN,TETRARCH"
  c[11] = "SHAPES,CIRCLE,CUBE,ELLIPTICAL,HEXAGON,OCTAGON,OVAL,PARALLELOGRAM,RECTANGLE,RHOMBUS,SQUARE,TRAPEZOID,TRIANGLE"
  c[12] = "DIRECTIONS,BACKWARD,DOWN,EAST,FOREWARD,HORIZONTAL,LEFT,NORTH,RIGHT,SOUTH,UP,VERTICAL,WEST"
  c[13] = "COLORS,AZURE,BLACK,BLUE,CYAN,GREEN,INDIGO,MAGENTA,ORANGE,RED,VIOLET,WHITE,YELLOW"
  c[14] = "CANINES,BEAGLE,BULLDOG,CHIHUAHUA,COCKER SPANIEL,COLLIE,DACHSHUND,DOBERMAN,GERMAN SHEPHERD,GOLDEN RETRIEVER,POODLE,ROTTWEILER,SIBERIAN HUSKY"
  c[15] = "SNACKS,CANDYBAR,CHIPS,COOKIES,CRACKERS,GRANOLA,JERKY,MIXEDNUTS,POPCORN,PORKSKINS,PRETZELS,RAISINS,TRAILMIX"
  c[16] = "NATURAL DISASTERS,AVALANCHE,BLIZZARD,CYCLONE,DROUGHT,EARTHQUAKE,ERUPTION,FLOOD,HAILSTORM,HURRICANE,TORNADO,TSUNAMI,WILDFIRE"
  c[17] = "FURNISHINGS,BEANBAG,BOOKCASE,CUSHIONS,DESK,DIVAN,DRAPERY,ENDTABLE,LAMPSTAND,OTTOMAN,RECLINER,RUG,TAPESTRY"
  c[18] = "OPPOSITES,BIG,LITTLE,THICK,THIN,PLUMP,PETITE,TALL,SHORT,LITHE,AWKWARD,ASTUTE,NAIVE"
  c[19] = "COUNTRIES,AMERICA,AUSTRALIA,CANADA,CHINA,EGYPT,ENGLAND,FRANCE,GERMANY,GREECE,ITALY,JAPAN,RUSSIA"
  c[20] = "PAPER PRODUCTS,BAG,BOOK,CARDBOARD,CUPS,ENVELOPES,LAMPSHADES,LETTER,NAPKINS,NEWSPAPER,PLATES,POSTCARD,TISSUE"
  c[21] = "LANDSCAPING,BLOWER,CHAINSAW,CLIPPERS,HATCHET,HOE,MOWER,RAKE,SHOVEL,SPRAYER,SPRINKLER,TRIMMER,WATERHOSE"
  c[22] = "UNITS,CUBITS,FEET,FURLONGS,GALLONS,INCHES,MILES,OUNCES,PINTS,POUNDS,QUARTS,TONS,YARDS"
  c[23] = "DANCE CRAZES,CHARLESTON,FOXTROT,JITTERBUG,LOCOMOTION,MAMBO,POLKA,RUMBA,TANGO,THE BUMP,THE HUSTLE,THE TWIST,WALTZ"
  c[24] = "TYRANTS,ALEXANDER,ATILLA,CAESAR,CHARLEMAGNE,CORTES,CYRUS,GENGHIS KHAN,HANNIBAL,HITLER,NAPOLEON,NERO,TAMERLANE"
  c[25] = "ASTRONOMY,ASTEROID,BLACK HOLE,CELESTIAL,COMET,CONSTELLATION,GALAXY,MILKYWAY,NEBULA,QUASAR,SOLAR,SUPERNOVA,WHITE DWARF"
  c[26] = "BREAKFAST,BACON,BISCUIT,CEREAL,COFFEE,DONUTS,EGGS,MILK,OATMEAL,PANCAKES,SAUSAGE,TOAST,WAFFLES"
  c[27] = "GEMSTONES,DIAMOND,EMERALD,GARNET,JADE,ONYX,OPAL,QUARTZ,RUBY,SAPPHIRE,TOPAZ,TURQUOISE,ZIRCON"
  c[28] = "APPAREL,BANDANNA,BIKINI,BOOTS,CORSET,GLOVES,GOWN,HOODIE,JACKET,SHAWL,SOCKS,TROUSERS,UNDERWEAR"
  c[29] = "BUGS,ANT,BEETLE,CATERPILLAR,CICADA,CRICKET,FIREFLY,GRASSHOPPER,LADYBUG,MANTIS,MOSQUITO,SPIDER,TERMITE"
  c[30] = "OFFICE SUPPLIES,CALCULATOR,ENVELOPES,FOLDERS,GLUE,PAPER,PAPERCLIPS,PEN,PENCIL,RULER,SCISSORS,STAPLER,TAPE"
  c[31] = "CARDGAMES,BLACKJACK,CRAZYEIGHTS,CANASTA,CRIBBAGE,GOFISH,HEARTS,MEMORY,PINOCHLE,POKER,RUMMY,SOLITAIRE,SPADES"
  c[32] = "MINERALS,BAUXITE,BERYLLIUM,COAL,COPPER,GOLD,GYPSUM,IRON,LEAD,LITHIUM,MOLYBDENUM,NICKEL,SILVER"
  c[33] = "FRANCHISE,DAIRYQUEEN,DOMINOS,KFC,MCDONALDS,POPEYES,SONIC,STARBUCKS,SUBWAY,TACOBELL,WENDYS,WHATABURGER,WHITECASTLE"
  c[34] = "PARANORMAL,ALIEN,BANSHEE,CHUPACABRA,CTHULHU,NOSTRADAMUS,POLTERGEIST,SATSQUATCH,SEANCE,SNALLYGASTER,STIGMATA,TELEKINESIS,UFO"
  c[35] = "VEGGIES,ASPARAGUS,BEANS,BROCCOLI,CABBAGE,CARROT,PEAS,RADISH,SPINACH,SQUASH,TURNIP,YAM,ZUCCHINI"
  c[36] = "TOOLS,CHISEL,CLAMP,CROWBAR,DRILLBIT,HAMMER,JIGSAW,LEVEL,PLIERS,RULER,SCREWDRIVER,SQUARE,WRENCH"
  c[37] = "AUTHORS,ASIMOV,DICKENS,DOSTOEVSKY,HEMINGWAY,KAFKA,ORWELL,POE,SHAKESPEARE,STEINBECK,TOLKIEN,TOLSTOY,TWAIN"
  c[38] = "THANKSGIVING,CORN,CRANBERRY SAUCE,GREENBEANS,MAC AND CHEESE,MASHED POTATOES,PECAN PIE,PUMKIN PIE,ROLLS,SQUASH,STUFFING,TURKEY,YAMS"
  c[39] = "METALS,ALUMINUM,BRASS,BRONZE,CHROME,COPPER,IRON,MERCURY,PLATINUM,TIN,TITANIUM,TUNGSTEN,ZINC"
  c[40] = "GAMES,BACKGAMMON,CHARADES,CHECKERS,CHESS,DOMINOES,GO,HANGMAN,JACKS,MAHJONG,MANCALA,MARBLES,TICTACTOE"
  c[41] = "SPIRITS,ALE,BOURBON,BRANDY,CIDER,GIN,MASH,RUM,SAKE,TEQUILA,VODKA,WHISKEY,WINE"
  c[42] = "CONDIMENTS,KETCHUP,MAYONNAISE,MUSTARD,PEPPER,PESTO,RELISH,SALSA,SALT,SOYSAUCE,TABASCO,TARTAR,TERIYAKI"
  c[43] = "FLOWERS,BUTTERCUP,CARNATION,CHRYSANTHEMUM,DAFFODIL,DAISY,GERANIUM,LILY,MARIGOLD,ORCHID,ROSE,TULIP,VIOLET"
  c[44] = "SPICES,BASIL,CINNAMON,CLOVE,CUMIN,GINGER,MUSTARD,NUTMEG,OREGANO,PAPRIKA,PEPPER,ROSEMARY,THYME"
  c[45] = "KITCHENWARE,BOWL,CARAFE,DISH,FORK,KETTLE,KNIFE,LADLE,MUG,SKILLET,SPATULA,SPOON,WHISK"
  c[46] = "CITIES,BEIJING,BERLIN,CAIRO,LONDON,MEXICO,MOSCOW,NEWYORK,PARIS,ROME,SYDNEY,TOKYO,VANCOUVER"
  c[47] = "NUTS,ALMOND,BRAZILNUT,CASHEW,CHESTNUT,COCONUT,HAZELNUT,MACADAMIA,PEANUT,PECAN,PINENUT,PISTACHIO,WALNUT"
  c[48] = "MOUTAIN RANGES,ADIRONDACKS,APPALACHIANS,BIGHORN,BLACK HILLS,BLUE RIDGE,CASCADES,CATSKILLS,CHISOS,OUACHITAS,ROCKIES,SIERRAS,SMOKIES"
  c[49] = "CHRISTMAS,CANDY CANE,ELVES,GIFTS,JINGLE BELLS,MISTLETOE,NATIVITY,NORTHPOLE,ORNAMENTS,REINDEER,SANTACLAUS,SLEIGH,STOCKINGS"
  c[50] = "FRUIT,APPLE,APRICOT,AVOCADO,BANANA,CANTALOUPE,CHERRY,GRAPE,LEMON,MELON,ORANGE,PEACH,POMEGRANATE"
  return c[int(1 + rand() * 50)]
}

# eof