lvl 4.2 running-with-the-bunnies .ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "from itertools import permutations\n",
    "\n",
    "def pow_set(list):\n",
    "    x = len(list)\n",
    "    masks = [1 << i for i in range(x)]\n",
    "    for i in range(1 << x):\n",
    "        yield [s_set for mask, s_set in zip(masks, list) if i & mask]\n",
    "\n",
    "def mat_to_graph(mat):\n",
    "    keys = [\"Start\"]\n",
    "    for num in range(1, len(mat)-1):\n",
    "        keys.append(num-1)\n",
    "    keys.append(\"Bulkhead\")\n",
    "    graph = dict(zip(keys, mat))\n",
    "    return graph\n",
    "\n",
    "\n",
    "def make(graph, source):\n",
    "    dist = {}\n",
    "    pre = {}\n",
    "    for node in graph:\n",
    "        dist[node] = 1000\n",
    "        pre[node] = None\n",
    "    dist[source] = 0 \n",
    "    return dist, pre\n",
    "\n",
    "\n",
    "def wait(node, neighbour, graph, dist, pre):\n",
    "    id = get_neighbour(neighbour, len(graph))\n",
    "    if dist[node] + graph[node][id] < dist[neighbour]:\n",
    "        dist[neighbour] = dist[node] + graph[node][id]\n",
    "        pre[neighbour] = node\n",
    "\n",
    "\n",
    "def get_neighbour(neighbour, g_size):\n",
    "    if neighbour == \"Bulkhead\":\n",
    "        return g_size - 1\n",
    "    elif neighbour == \"Start\":\n",
    "        return 0\n",
    "    else:\n",
    "        return int(neighbour)+1\n",
    "        \n",
    "def bell_ford_alg(mat, graph, time_limit, source):\n",
    "    dist, pred = make(graph, source)\n",
    "    for num in range(len(graph)-1):\n",
    "        for node in graph:\n",
    "            temp = dict(graph)\n",
    "            del temp[node]\n",
    "            for neighbour in temp:\n",
    "                wait(node, neighbour, graph, dist, pred)\n",
    "\n",
    "    for node in graph:\n",
    "        for neighbour in graph:\n",
    "            id = get_neighbour(neighbour, len(graph))\n",
    "            if dist[node] + graph[node][id] < dist[neighbour]:\n",
    "                return [num for num in range(0, len(graph)-2)]\n",
    "\n",
    "    paths = floyd_alg(mat)\n",
    "    return save_max_bunnies(mat, paths, time_limit)\n",
    "\n",
    "\n",
    "def floyd_alg(mat):\n",
    "    n = len(mat)\n",
    "    paths = deepcopy(mat) \n",
    "    for k in range(n):\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if paths[i][k] + paths[k][j] < paths[i][j]:\n",
    "                    paths[i][j] = paths[i][k] + paths[k][j]\n",
    "    return paths\n",
    "\n",
    "\n",
    "def save_max_bunnies(mat, paths, time_limit):\n",
    "    n = len(mat)-2\n",
    "    bunnies = []\n",
    "    for num in range(n):\n",
    "        bunnies.append(num)\n",
    "    p_set = pow_set(bunnies)\n",
    "    p_set = sorted(p_set)\n",
    "\n",
    "    \n",
    "    saved_bunnies = []\n",
    "    for s_set in p_set:\n",
    "        for permutation in permutations(s_set):\n",
    "            sub_sum = 0\n",
    "            prev = 0\n",
    "            next = len(mat)-1\n",
    "            \n",
    "            for bunnyid in permutation:\n",
    "                next = bunnyid+1\n",
    "                sub_sum += paths[prev][next]\n",
    "                prev = next\n",
    "            sub_sum += paths[prev][len(mat)-1]\n",
    "            if sub_sum <= time_limit and len(s_set) > len(saved_bunnies):\n",
    "                saved_bunnies = s_set\n",
    "                if len(saved_bunnies) == n:\n",
    "                    break\n",
    "            else:\n",
    "                continue\n",
    "    return saved_bunnies\n",
    "\n",
    "\n",
    "def solution(times, time_limit):\n",
    "    if len(times) <= 2:\n",
    "        return []\n",
    "    \n",
    "    graph = mat_to_graph(times)\n",
    "    return bell_ford_alg(times, graph, time_limit, \"Start\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer([[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0, 1], [1, 1, 1, 1, 0]], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "wait"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}