Cover alphabets by five-letter words

coverage.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"abcdefghijklmnopqrstuvwxyz\""
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using JuMP, GLPK\n",
    "const optimizer = GLPK.Optimizer\n",
    "\n",
    "# https://github.com/charlesreid1/five-letter-words/blob/master/sgb-words.txt minus \"bronx\"\n",
    "f = open(\"sgb-words.txt\") \n",
    "\n",
    "const words = readlines(f)\n",
    "const characters = \"abcdefghijklmnopqrstuvwxyz\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "set_covering (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function set_covering()\n",
    "    m = Model(optimizer)\n",
    "    @variable(m, x[words], Bin)\n",
    "    @objective(m, Min, sum(x[w] for w in words))\n",
    "    @constraint(\n",
    "        m, \n",
    "        covered[c in characters], \n",
    "        sum(contains(w, c) * x[w] for w in words) >= 1\n",
    "    )\n",
    "    optimize!(m)\n",
    "\n",
    "    solution = String[]\n",
    "    for w in words \n",
    "        if value(x[w]) == 1.0\n",
    "            push!(solution, w)\n",
    "        end\n",
    "    end\n",
    "    return solution\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "weighted_maximum_coverage (generic function with 1 method)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function weighted_maximum_coverage(;n_words=3)\n",
    "    frequency = Dict( [c => 0 for c in characters] )\n",
    "    for w in words \n",
    "        for c in w \n",
    "            frequency[c] += 1\n",
    "        end\n",
    "    end\n",
    "\n",
    "    m = Model(optimizer)\n",
    "    @variable(m, x[words], Bin)\n",
    "    @variable(m, 0 <= y[c in characters] <= 1)\n",
    "    @objective(m, Max, sum(frequency[c] * y[c] for c in characters))\n",
    "    @constraint(\n",
    "        m, \n",
    "        covered[c in characters], \n",
    "        sum(contains(w, c) * x[w] for w in words) >= y[c]\n",
    "    )\n",
    "    @constraint(\n",
    "        m, \n",
    "        n_words_limit,\n",
    "        sum(x[w] for w in words) <= n_words\n",
    "    )\n",
    "    optimize!(m)\n",
    "\n",
    "    solution = String[]\n",
    "    for w in words \n",
    "        if value(x[w]) == 1.0\n",
    "            push!(solution, w)\n",
    "        end\n",
    "    end\n",
    "    return solution \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set_covering() = [\"fixed\", \"blimp\", \"jowls\", \"vetch\", \"zingy\", \"quark\"]\n",
      "weighted_maximum_coverage(n_words = 1) = [\"arose\"]\n",
      "weighted_maximum_coverage(n_words = 2) = [\"enrol\", \"staid\"]\n",
      "weighted_maximum_coverage(n_words = 3) = [\"tonal\", \"syrup\", \"medic\"]\n",
      "weighted_maximum_coverage(n_words = 4) = [\"flags\", \"mound\", \"berth\", \"picky\"]\n",
      "weighted_maximum_coverage(n_words = 5) = [\"racks\", \"vixen\", \"blitz\", \"whomp\", \"fudgy\"]\n"
     ]
    }
   ],
   "source": [
    "@show set_covering()\n",
    "@show weighted_maximum_coverage(n_words=1)\n",
    "@show weighted_maximum_coverage(n_words=2)\n",
    "@show weighted_maximum_coverage(n_words=3)\n",
    "@show weighted_maximum_coverage(n_words=4)\n",
    "@show weighted_maximum_coverage(n_words=5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.7.2",
   "language": "julia",
   "name": "julia-1.7"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}