Korrutise.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWX'\n",
    "\n",
    "def empty_state():\n",
    "    return { letter: set(range(10)) for letter in ALPHABET }\n",
    "\n",
    "class Constraint:\n",
    "    def __init__(self, letters, predicate):\n",
    "        self.letters = letters\n",
    "        self.predicate = predicate\n",
    "        \n",
    "class State:\n",
    "    def __init__(self, state = empty_state()):\n",
    "        self.state = state\n",
    "        \n",
    "    def updated(self, constraint):\n",
    "        return self.update_with(count_combinations(self, constraint))\n",
    "    \n",
    "    def update_with(self, update):\n",
    "        new_state = self.state.copy()\n",
    "        new_state.update(update)\n",
    "        return State(new_state)\n",
    "    \n",
    "    # Helpers\n",
    "    def unsolved(self):\n",
    "        return sum(1 for x in self.state.values() if len(x) != 1)\n",
    "    \n",
    "    def combinations(self, letters):\n",
    "        result = 1\n",
    "        for a in letters: result *= len(self.state[a])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "def generate_combinations(state, constraint):\n",
    "    possible_values = [state[letter] for letter in constraint.letters]\n",
    "    for combination in product(*possible_values):\n",
    "        values = dict(zip(constraint.letters, combination))\n",
    "        if constraint.predicate(values):\n",
    "            yield values\n",
    "            \n",
    "def count_combinations(state, constraint):\n",
    "    if state.combinations(constraint.letters) > 1000000: \n",
    "        #print('Skipping', constraint.letters)\n",
    "        return state.state\n",
    "    values = { letter: set() for letter in constraint.letters }\n",
    "    for combo in generate_combinations(state.state, constraint):\n",
    "        for k, v in combo.items(): \n",
    "            values[k].add(v)\n",
    "    return values\n",
    "\n",
    "        \n",
    "start_state = State()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'A': 0, 'B': 0},\n",
       " {'A': 2, 'B': 1},\n",
       " {'A': 4, 'B': 2},\n",
       " {'A': 6, 'B': 3},\n",
       " {'A': 8, 'B': 4}]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(generate_combinations(start_state.state, Constraint('AB', lambda x: x['A'] == x['B'] * 2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': {0, 2, 4, 6, 8}, 'B': {0, 1, 2, 3, 4}}"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_combinations(start_state, Constraint('AB', lambda x: x['A'] == x['B'] * 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "def num(abc, state):\n",
    "    result = 0\n",
    "    for a in abc:\n",
    "        result = (result * 10) + state[a]\n",
    "    return result\n",
    "\n",
    "def eql(abc, value):\n",
    "    return Constraint(abc, lambda s: num(abc, s) == value)\n",
    "\n",
    "def eql_value(a, b):\n",
    "    return Constraint(a + b, lambda s: num(a, s) == num(b, s))\n",
    "\n",
    "def mul(a, b, c):\n",
    "    return Constraint(a + b + c, lambda s: num(a, s) * num(b, s) == num(c, s))\n",
    "\n",
    "def not_equal(abc, value):\n",
    "    return Constraint(abc, lambda s: num(abc, s) != value)   \n",
    "    \n",
    "def sub(a, b, c):\n",
    "    return Constraint(''.join(set(a + b + c)), lambda s: num(a, s) - num(b, s) == num(c, s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "constraints = [\n",
    "    eql('TR', 58),\n",
    "    eql('WI', 26),\n",
    "    eql('V', 2),\n",
    "    eql('M', 4),\n",
    "    not_equal('A', 0),\n",
    "    not_equal('C', 0),\n",
    "    not_equal('P', 0),\n",
    "    mul('AB', 'F', 'GHI'),\n",
    "    mul('AB', 'E', 'JKL'),\n",
    "    mul('AB', 'D', 'MNO'),\n",
    "    mul('AB', 'C', 'PQR'),\n",
    "    eql_value('I', 'X'),\n",
    "#     more_than_equal('S', 'P'),\n",
    "#     more_than_equal('ST', 'M', 'PQ'),\n",
    "#     more_than_equal('STU', 'MN', 'PQR', 'J'),\n",
    "#     Constraint('HILWX', lambda s: (num('HI', s) + num('L', s) * 10) % 100 == num('WX', s)),\n",
    "#     Constraint('GHIKLOVWX', lambda s: (num('GHI', s) + num('KL', s) * 10 + num('O', s) * 100) % 1000 == num('VWX', s)),\n",
    "#     Constraint('GHIJKLNORUVWX', lambda s: (num('GHI', s) + num('JKL', s) * 10 + num('NO', s) * 100 + num('R', s) * 1000) % 10000 == num('UVWX', s)),\n",
    "    mul('AB', 'CDEF', 'STUVWX'),\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "state = State()\n",
    "\n",
    "def iterate(state):\n",
    "    for constraint in constraints: \n",
    "        state = state.updated(constraint)\n",
    "    return state\n",
    "\n",
    "def iterate_until_break(state):\n",
    "    prev_unsolved = -1\n",
    "    while state.unsolved() != prev_unsolved:\n",
    "        prev_unsolved = state.unsolved()\n",
    "        state = iterate(state)\n",
    "    return state\n",
    "\n",
    "def recurse(state, depth = 0):\n",
    "    state = iterate_until_break(state)\n",
    "    if state.unsolved() == 0:\n",
    "        print(state.state)\n",
    "        return\n",
    "    \n",
    "    if depth > 2: \n",
    "        return\n",
    "    \n",
    "    try:\n",
    "        count, smallest_letter = min((len(s), letter) for letter, s in state.state.items() if len(s) > 1)\n",
    "        #print(depth, 'Smallest/count', smallest_letter, count, state.state[smallest_letter], state.state)\n",
    "        for attempted_value in state.state[smallest_letter]:\n",
    "            #print(depth, 'Setting value to', smallest_letter, attempted_value)\n",
    "            new_state = state.update_with({ smallest_letter: set([attempted_value]) })\n",
    "            recurse(new_state, depth + 1)\n",
    "    except: pass\n",
    "    \n",
    "#recurse(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = {'A': {5}, 'B': {4}, 'C': {2}, 'D': {8}, 'E': {1}, 'F': {9}, 'G': {4}, 'H': {8}, 'I': {6}, 'J': {0}, 'K': {5}, 'L': {4}, 'M': {4}, 'N': {3}, 'O': {2}, 'P': {1}, 'Q': {0}, 'R': {8}, 'S': {1}, 'T': {5}, 'U': {2}, 'V': {2}, 'W': {2}, 'X': {6}}\n",
    "s2 = {'A': {5}, 'B': {1}, 'C': {8}, 'D': {9}, 'E': {2}, 'F': {6}, 'G': {3}, 'H': {0}, 'I': {6}, 'J': {1}, 'K': {0}, 'L': {2}, 'M': {4}, 'N': {5}, 'O': {9}, 'P': {4}, 'Q': {0}, 'R': {8}, 'S': {4}, 'T': {5}, 'U': {5}, 'V': {2}, 'W': {2}, 'X': {6}}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "V = lambda s: { k: list(v)[0] for k, v in s.items() }\n",
    "def fformat(string, s):\n",
    "    return ''.join(str(s[l]) if l in s else l for l in string)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(\"58° 20.542'\", \"26° 44.839'\")"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fformat(\"TR° VJ.ABC'\", V(s1)), fformat(\"WI° MG.DNF'\", V(s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(\"58° 21.518'\", \"26° 43.956'\")"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fformat(\"TR° VJ.ABC'\", V(s2)), fformat(\"WI° MG.DNF'\", V(s2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'A': {4}, 'B': {5}, 'C': {5}, 'D': {2}, 'E': {2}, 'F': {6}, 'G': {5}, 'H': {1}, 'I': {8}, 'J': {9}, 'K': {2}, 'L': {6}, 'M': {0}, 'N': {8}, 'O': {4}, 'P': {7}, 'Q': {4}, 'R': {5}, 'S': {9}, 'T': {1}, 'U': {3}, 'V': {0}, 'W': {2}, 'X': {3}, 'Y': {0}, 'Z': {6}}\n"
     ]
    }
   ],
   "source": [
    "ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "\n",
    "constraints= [\n",
    "    eql('RN', 58),\n",
    "    eql('DZ', 26),\n",
    "    eql('E', 2),\n",
    "    eql('O', 4),\n",
    "    not_equal('A', 0),\n",
    "    not_equal('G', 0),\n",
    "    not_equal('O', 0),\n",
    "    not_equal('Q', 0),\n",
    "    not_equal('T', 0),\n",
    "    not_equal('X', 0),\n",
    "    mul('GH', 'I', 'AMN'),\n",
    "    mul('GH', 'J', 'QRS'),\n",
    "    mul('GH', 'K', 'TVW'),\n",
    "    mul('GH', 'L', 'XYZ'),\n",
    "    sub('ABC', 'AMN', 'OP'),\n",
    "    sub('OPD', 'QRS', 'TU'),\n",
    "    sub('TUE', 'TVW', 'XY'),\n",
    "    mul('IJKL', 'GH', 'ABCDEF')\n",
    "]\n",
    "state = State(empty_state())\n",
    "\n",
    "recurse(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(\"58° 22.692'\", \"26° 43.326'\")"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lah = {'A': {4}, 'B': {5}, 'C': {5}, 'D': {2}, 'E': {2}, 'F': {6}, 'G': {5}, 'H': {1}, 'I': {8}, 'J': {9}, 'K': {2}, 'L': {6}, 'M': {0}, 'N': {8}, 'O': {4}, 'P': {7}, 'Q': {4}, 'R': {5}, 'S': {9}, 'T': {1}, 'U': {3}, 'V': {0}, 'W': {2}, 'X': {3}, 'Y': {0}, 'Z': {6}}\n",
    "fformat(\"RN° EW.FSE'\", V(lah)), fformat(\"DZ° OU.XKL'\", V(lah))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}