Week 10 - Workshop.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Worksheet 9\n",
    "## Overview\n",
    "The workshop for week 10 will start with a short tutorial on Dijkstra's Algorithm and will involve writing a simple priority queue.\n",
    "## Tutorial Questions\n",
    "For a directed graph with the following edges (from - to - weight):\n",
    "\n",
    "a b 3\n",
    "\n",
    "a d 7\n",
    "\n",
    "b d 2\n",
    "\n",
    "c e 6\n",
    "\n",
    "d b 2\n",
    "\n",
    "d c 5\n",
    "\n",
    "d e 4\n",
    "\n",
    "e d 2\n",
    "\n",
    "Draw the graph and then run through Dijkstra's Algorithm starting from the vertex a.\n",
    "## Programming Exercises\n",
    "**Programming 9.1** Given a set of data and key pairs, write a priority queue, this will be directly useful for next week's workshop. It should have a *makeQueue* function, which creates an empty priority queue, an *enqueue* function, which adds a data, key pair in the correct place in the queue, a *dequeue* function, which takes the highest priority item from the queue (for usefulness next week, you can make the highest priority the item with the *lowest* key), an *update* function, which moves an item with a certain index up in the queue to where it belongs (this function can assume the rest of the keys remain unchanged) and an *empty* function, which checks whether the queue is empty.\n",
    "\n",
    "NOTE: You don't need to make this task harder than it needs to be, you can implement this as an unsorted array. When a dequeue is called, you can search through all the items to find the cheapest item to dequeue and then remove it when a dequeue happens, replacing it with the last item in the array (so the items don't need to be shuffled). Likewise, in this case, the update function needn't do anything either. If you like, you can switch the underlying structure to a heap later and implement a lot of that more efficiently, but the input will be sufficiently small that this isn't much of a problem for the moment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/* pqueue.h */\n",
    "struct pqueue;\n",
    "\n",
    "/* Creates an empty priority queue. */\n",
    "struct pqueue *makeQueue();\n",
    "\n",
    "/* Adds an item to a priority queue. */\n",
    "void enqueue(struct pqueue *queue, int priority, void *data);\n",
    "\n",
    "/* Takes the highest priority item from the queue. */\n",
    "void *dequeue(struct pqueue *queue);\n",
    "\n",
    "/* Updates the position of the given data item. \n",
    "    Note: if you were writing this generally, you\n",
    "    might like to include a priority data update \n",
    "    function in your pqueue creation (like the\n",
    "    hash table exercise) that allows you to read\n",
    "    and update priority information and set and\n",
    "    retrieve heap position information from\n",
    "    an auxillary data structure (there's a lot\n",
    "    of options here which are all fairly reasonable\n",
    "    choices).\n",
    "    For now, presume this does nothing (or make it \n",
    "    read through the array and update priorities,\n",
    "    it depends on your dequeue implementation). */\n",
    "void update(struct pqueue *queue, int index);\n",
    "\n",
    "/* Returns 1 if the queue is empty, 0 otherwise. */\n",
    "int empty(struct pqueue *queue);\n",
    "\n",
    "/* Frees all memory allocated by the queue given. */\n",
    "void freeQueue(struct pqueue *queue);\n",
    "    \n",
    "/* pqueue.c */\n",
    "#include <stdlib.h>\n",
    "#include <assert.h>\n",
    "/* #include \"pqueue.h\" */\n",
    "struct pqueue {\n",
    "    /* FILL IN THIS PART */\n",
    "\n",
    "};\n",
    "\n",
    "struct pqueue *makeQueue(){\n",
    "    /* Write this */\n",
    "    \n",
    "    \n",
    "    return NULL;\n",
    "}\n",
    "\n",
    "void enqueue(struct pqueue *queue, int priority, void *data){\n",
    "    /* Write this */\n",
    "    \n",
    "    \n",
    "    \n",
    "}\n",
    "\n",
    "void *dequeue(struct pqueue *queue){\n",
    "    /* Write this */\n",
    "    \n",
    "    return NULL;\n",
    "}\n",
    "\n",
    "void update(struct pqueue *queue, int index){\n",
    "    /* Do whatever is appropriate. */\n",
    "    return;\n",
    "}\n",
    "\n",
    "int empty(struct pqueue *queue){\n",
    "    /* Write this. */\n",
    "    return 0;\n",
    "}\n",
    "\n",
    "void freeQueue(struct pqueue *queue){\n",
    "    \n",
    "}\n",
    "\n",
    "/* main.c */\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "/* #include \"pqueue.h\" */\n",
    "#define SIZE 10\n",
    "#define ARBITRARYTAKE 3\n",
    "\n",
    "int main(int argc, char **argv){\n",
    "    int inputs[SIZE] = {7, 1, 3, 5, 6, 8, 4, 2, 9, 11};\n",
    "    int i;\n",
    "    \n",
    "    struct pqueue *queue = makeQueue();\n",
    "    \n",
    "    printf(\"Adding all items to priority queue\\n\");\n",
    "    for(i = 0; i < SIZE; i++){\n",
    "        printf(\"%d \",inputs[i]);\n",
    "        enqueue(queue, inputs[i], &(inputs[i]));\n",
    "    }\n",
    "    printf(\"\\n\");\n",
    "    if(empty(queue)){\n",
    "        printf(\"ERROR: Queue empty after all items added\\n\");\n",
    "    }\n",
    "    \n",
    "    printf(\"Removing first three items from priority queue\\n\");\n",
    "    for(i = 0; i < ARBITRARYTAKE; i++){\n",
    "        printf(\"%d \",*(int *) (dequeue(queue)));\n",
    "    }\n",
    "    printf(\"\\n\");\n",
    "    \n",
    "    printf(\"Updating priority 11 item to 1\\n\");\n",
    "    inputs[SIZE - 1] = 1;\n",
    "    /* Normally you'd find this information from somewhere that\n",
    "        the priority queue will update, but as the update function\n",
    "        doesn't do anything anything with this information, that\n",
    "        doesn't really matter. */\n",
    "    update(queue, SIZE - ARBITRARYTAKE - 1);\n",
    "    printf(\"Taking rest of items from priority queue.\\n\");\n",
    "    for(i = 0; i < SIZE - ARBITRARYTAKE; i++){\n",
    "        if(!empty(queue)){\n",
    "            printf(\"%d \",*(int *) (dequeue(queue)));\n",
    "        }\n",
    "    }\n",
    "    printf(\"\\n\");\n",
    "    \n",
    "    if(! empty(queue)){\n",
    "        printf(\"ERROR: Queue not empty after all items dequeued\\n\");\n",
    "    }\n",
    "    \n",
    "    freeQueue(queue);\n",
    "    \n",
    "    return 0;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Programming Challenge 9.1** For this problem, you're the companion (voiced by Eddy Murphy) to a big brown bugbear who has been tasked by King Git to rescue a supposedly helpless princess from her castle in exchange for the rights to your marshland. [1]\n",
    "\n",
    "The problem to solve is that you will need to find a path to the castle, but, due to a bad habit of getting distracted while talking, you can only move in an L shape (two spaces forward in up, down, left or right directions, followed by a single space in a direction perpendicular, or one space forward followed by two spaces perpendicular). The map is given as a 2D array, where empty spaces are marked with ' &nbsp; ' and spaces you can't traverse are marked with '#', your starting location is marked with 'S' and the castle is marked with 'C'. Print out a path to the castle. This needn't be the shortest path, but you should ensure that the path doesn't return to the same location at any point (no moves are redundant). [2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "#define UNTRAVERSABLE '#'\n",
    "#define START 'S'\n",
    "#define CASTLE 'C'\n",
    "#define XSIZE 6\n",
    "#define YSIZE 6\n",
    "\n",
    "/* Prints the path from the S symbol in the map\n",
    "    to the C symbol which doesn't ever stop on\n",
    "    any # symbols. The map given, of size xSize by\n",
    "    ySize can be modified freely and needn't be\n",
    "    kept in any way consistent with the original\n",
    "    map. */\n",
    "void printPath(char map[XSIZE][YSIZE + 1], int xSize, int ySize);\n",
    "\n",
    "void printPath(char map[XSIZE][YSIZE + 1], int xSize, int ySize){\n",
    "    int i, j;\n",
    "    struct coordinatePair {\n",
    "        int x;\n",
    "        int y;\n",
    "    };\n",
    "    struct coordinatePair startPair = { .x = -1, .y = -1 };\n",
    "    \n",
    "    for(i = 0; i < XSIZE; i++){\n",
    "        for(j = 0; j < YSIZE; j++){\n",
    "            if(map[i][j] == START){\n",
    "                startPair.x = i;\n",
    "                startPair.y = j;\n",
    "                /* Could also just let the loops\n",
    "                    run, but may as well break\n",
    "                    out of both. */\n",
    "                break;\n",
    "            }\n",
    "        }\n",
    "        if(startPair.x != -1){\n",
    "            break;\n",
    "        }\n",
    "    }\n",
    "    /* FILL IN */\n",
    "\n",
    "}\n",
    "\n",
    "int main(int argc, char **argv){\n",
    "    char map[XSIZE][YSIZE + 1] = {\n",
    "        \"     C\",\n",
    "        \"  #  #\",\n",
    "        \"# # ##\",\n",
    "        \"#  # #\",\n",
    "        \"# #   \",\n",
    "        \" S    \"\n",
    "    };\n",
    "    \n",
    "    printPath(map, XSIZE, YSIZE);\n",
    "    \n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[1]: The story, all names, characters, and incidents portrayed in this question are fictitious. No identification with actual persons (living or deceased), places, buildings, and products is intended or should be inferred.\n",
    "\n",
    "[2]: This problem was inspired by Tuenti Challenge 8's Challenge 4 ([https://contest.tuenti.net/Challenges?id=4])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C",
   "language": "c",
   "name": "jupyter_c_kernel"
  },
  "language_info": {
   "file_extension": ".c",
   "mimetype": "text/plain",
   "name": "c"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}