problem-ideas.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Project ideas"
   8    ]
   9   },
  10   {
  11    "cell_type": "markdown",
  12    "metadata": {},
  13    "source": [
  14     "## Monotone substrings\n",
  15     "Find the Longest monotonic substring in a list of numbers (words?)\n",
  16     "\n",
  17     "Extension: longest non-decreasing (or non-increasing) substring.\n",
  18     "\n",
  19     "Extension: longest monotonic subsequence"
  20    ]
  21   },
  22   {
  23    "cell_type": "markdown",
  24    "metadata": {},
  25    "source": [
  26     "## Product in grid\n",
  27     "Given a grid of numbers, find the largest product of five numbers in a row (totally Project Euler no. 11: https://projecteuler.net/problem=11 ).\n",
  28     "\n",
  29     "Extension: largest product of five adjacent numbers, no necessarily colinear, but can't loop back to same number twice."
  30    ]
  31   },
  32   {
  33    "cell_type": "markdown",
  34    "metadata": {},
  35    "source": [
  36     "## Wordsearch: \n",
  37     "Given a grid of letters and a list of words, how many words are in the grid?\n",
  38     "\n",
  39     "Extension: what's the longest word you can make from the leftover letters?"
  40    ]
  41   },
  42   {
  43    "cell_type": "markdown",
  44    "metadata": {},
  45    "source": [
  46     "## Countdown\n",
  47     "Given some letters and a list of words, what's the longest word you can make from the letters.\n",
  48     "\n",
  49     "Extension: you're actually playing scrabble. What's the highest-scoring word you can make?"
  50    ]
  51   },
  52   {
  53    "cell_type": "markdown",
  54    "metadata": {},
  55    "source": [
  56     "## Connect 4\n",
  57     "Given a grid size and a list of moves, who won? Input is a list of games, result is number of games that went to completion\n",
  58     "\n",
  59     "Extension: how many games would be won by on the next go? (At least one of the puzzles has to have a game that would be \"won\" by placing a piece above an already-full column."
  60    ]
  61   },
  62   {
  63    "cell_type": "markdown",
  64    "metadata": {},
  65    "source": [
  66     "Travelling salesman: given a network, find the shortest route between them, without visiting the same spot twice.\n",
  67     "Extension: find the longest travelling salesman route.\n",
  68     "Extension: relax the constraint, and allow repeated visits to the same place. What's the shortest route now?"
  69    ]
  70   },
  71   {
  72    "cell_type": "markdown",
  73    "metadata": {},
  74    "source": [
  75     "Virtual machine: run the assembly program, what's the result?\n",
  76     "Extension: run it again on different input."
  77    ]
  78   },
  79   {
  80    "cell_type": "markdown",
  81    "metadata": {},
  82    "source": [
  83     "Given a boolean expression, how many variables are in it?\n",
  84     "Extension: is it satisfiable?"
  85    ]
  86   },
  87   {
  88    "cell_type": "markdown",
  89    "metadata": {},
  90    "source": [
  91     "Battleships: given a grid of hits and misses, where could be battleship be? (count how many positions it could be in) Assume the battleship is unhit.\n",
  92     "Extension: the battleship might have been hit, but not sunk. Now how many places could it be?"
  93    ]
  94   },
  95   {
  96    "cell_type": "markdown",
  97    "metadata": {},
  98    "source": [
  99     "How many ways can you fill a bunch of knapsacks (e.g. Advent 2015 days 17, 24)"
 100    ]
 101   },
 102   {
 103    "cell_type": "markdown",
 104    "metadata": {},
 105    "source": [
 106     "Phone number puzzle: words that fit a phone number.\n",
 107     "Extension: non-ascii unicode in input"
 108    ]
 109   },
 110   {
 111    "cell_type": "markdown",
 112    "metadata": {},
 113    "source": [
 114     "Rainfall problem:\n",
 115     "http://dl.acm.org.libezproxy.open.ac.uk/citation.cfm?doid=6592.6594"
 116    ]
 117   },
 118   {
 119    "cell_type": "markdown",
 120    "metadata": {},
 121    "source": [
 122     "Ten-pin bowling scores. Given a sequence of number of pins knocked down, calculate total score."
 123    ]
 124   },
 125   {
 126    "cell_type": "markdown",
 127    "metadata": {},
 128    "source": [
 129     "Pack and justify text into paragraphs."
 130    ]
 131   },
 132   {
 133    "cell_type": "markdown",
 134    "metadata": {},
 135    "source": [
 136     "Word chain puzzles"
 137    ]
 138   },
 139   {
 140    "cell_type": "markdown",
 141    "metadata": {},
 142    "source": [
 143     "Derangement network simulation.\n",
 144     "Extension: sum several networks"
 145    ]
 146   },
 147   {
 148    "cell_type": "markdown",
 149    "metadata": {},
 150    "source": [
 151     "Machine code execution: Collatz sequence, count steps."
 152    ]
 153   },
 154   {
 155    "cell_type": "markdown",
 156    "metadata": {},
 157    "source": [
 158     "Parcel pricing, by weight and volumetric weight. Find total postage cost of list of parcels. Each parcel given as w, h, l, mass."
 159    ]
 160   },
 161   {
 162    "cell_type": "markdown",
 163    "metadata": {},
 164    "source": [
 165     "Parcel wrapping: first, find area, then find width of 1m strip to wrap. Include extra for wriggle room."
 166    ]
 167   },
 168   {
 169    "cell_type": "markdown",
 170    "metadata": {},
 171    "source": [
 172     "Mastermind: how many valid solutions remain after the scores you've seen\n",
 173     "How many scores are possible for this attempt?~"
 174    ]
 175   },
 176   {
 177    "cell_type": "markdown",
 178    "metadata": {},
 179    "source": [
 180     "# More problems:\n",
 181     "* https://books.google.co.uk/books?id=85NsAHJjTJ0C&pg=PA390&lpg=PA390&dq=phone+number+problem+programming+names&source=bl&ots=c7oC9JvpZz&sig=aNnW6t_nmGK7SyAKchK0MaxqbkA&hl=en&sa=X&ved=0ahUKEwjnzcbbgs7RAhWKKcAKHQiFCDAQ6AEIJDAC#v=onepage&q=phone%20number%20problem%20programming%20names&f=false\n",
 182     "* https://www.cs.uoregon.edu/Activities/Luks_Programming_Contest/\n",
 183     "* https://www.reddit.com/r/dailyprogrammer/"
 184    ]
 185   },
 186   {
 187    "cell_type": "markdown",
 188    "metadata": {},
 189    "source": [
 190     "# Related research\n",
 191     "* https://computinged.wordpress.com/2016/12/16/graduating-dr-briana-morrison-posing-new-puzzles-for-computing-education-research/\n",
 192     "* https://computinged.wordpress.com/2010/08/16/a-challenge-to-computing-education-research-make-measurable-progress/\n",
 193     "* http://dl.acm.org.libezproxy.open.ac.uk/citation.cfm?doid=6592.6594\n",
 194     "* https://computinged.wordpress.com/2017/01/18/power-law-of-practice-in-software-implementation-does-this-explain-the-w-going-away/\n",
 195     "* https://www.cs.utexas.edu/users/mckinley/305j/pair-hcs-2006.pdf"
 196    ]
 197   },
 198   {
 199    "cell_type": "code",
 200    "execution_count": null,
 201    "metadata": {
 202     "collapsed": true
 203    },
 204    "outputs": [],
 205    "source": []
 206   }
 207  ],
 208  "metadata": {
 209   "kernelspec": {
 210    "display_name": "Python 3",
 211    "language": "python",
 212    "name": "python3"
 213   },
 214   "language_info": {
 215    "codemirror_mode": {
 216     "name": "ipython",
 217     "version": 3
 218    },
 219    "file_extension": ".py",
 220    "mimetype": "text/x-python",
 221    "name": "python",
 222    "nbconvert_exporter": "python",
 223    "pygments_lexer": "ipython3",
 224    "version": "3.5.2"
 225   }
 226  },
 227  "nbformat": 4,
 228  "nbformat_minor": 1
 229 }