Removing files from data analysis directory

[ou-summer-of-code-2017.git] / problem-ideas.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Project ideas\n",
    "\n",
    "[Project workspace](https://learn2.open.ac.uk/course/view.php?id=206050)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems by day\n",
    "\n",
    "1. [Ticket prices](01-ticket-prices)\n",
    "2. [Lift instructions](02-lifts)\n",
    "3. [Door codes](03-door-codes)\n",
    "4. [Ghost leg, follow and pack](04-amidakuji)\n",
    "5. [Display board](05-display-board)\n",
    "6. [Tour shapes](06-tour-shapes)\n",
    "7. [Virtual machine](07-interpreter)\n",
    "8. [Word chains](08-word-chains)\n",
    "9. [Resolving the bill](09-resolving-the-bill)\n",
    "10. [Word search](10-word-search)\n",
    "\n",
    "### Extras\n",
    "* [Suitcase packing](10-suitacase-packing)\n",
    "9. [Filling the days](08-filling-days) [Problem C](https://www.cs.uoregon.edu/Activities/Luks_Programming_Contest/problems/Problems2017.pdf): A per the problem, B when there are multiple rooms available\n",
    "\n",
    "\n",
    "Problem 6 taken from [Problem B](https://www.cs.uoregon.edu/Activities/Luks_Programming_Contest/problems/Problems2017.pdf): A is check if string is a closed loop, B is finding if two partial loops make a whole one"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Longest substring of _k_ distinct characters\n",
    "Given a string of letters, what is the longest (contiguous) substring with no more than _k_ distinct characters?\n",
    "\n",
    "Could also do it with words instead of letters. \n",
    "\n",
    "Not sure how to find the extension..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Monotone substrings\n",
    "Find the Longest monotonic substring in a list of numbers (words?)\n",
    "\n",
    "Extension: longest non-decreasing (or non-increasing) substring.\n",
    "\n",
    "Extension: longest monotonic subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Product in grid\n",
    "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",
    "\n",
    "Extension: largest product of five adjacent numbers, no necessarily colinear, but can't loop back to same number twice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Wordsearch](wordsearch/): \n",
    "\n",
    "Wordsearch [creation](wordsearch/wordsearch-creation.ipynb) and [solving](wordsearch/wordsearch-solving.ipynb).\n",
    "\n",
    "Given a grid of letters and a list of words, how many words are in the grid?\n",
    "\n",
    "Extension: what's the longest word you can make from the leftover letters?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Countdown\n",
    "Given some letters and a list of words, what's the longest word you can make from the letters.\n",
    "\n",
    "Extension: you're actually playing scrabble. What's the highest-scoring word you can make?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Connect 4\n",
    "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",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Travelling salesman\n",
    "Given a network, find the shortest route between them, without visiting the same spot twice.\n",
    "\n",
    "Extension: find the longest travelling salesman route.\n",
    "\n",
    "Extension: relax the constraint, and allow repeated visits to the same place. What's the shortest route now?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Virtual machine\n",
    "Run the assembly program, what's the result? Count the steps in a collatz sequence?\n",
    "\n",
    "Extension: run it again on different input. This takes longer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Satisfiability\n",
    "Given a boolean expression, how many variables are in it?\n",
    "\n",
    "Extension: is it satisfiable?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Battleships\n",
    "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",
    "\n",
    "Extension: the battleship might have been hit, but not sunk. Now how many places could it be?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Multi-knapsack\n",
    "How many ways can you fill a bunch of knapsacks (e.g. Advent 2015 days 17, 24)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Phone number puzzle\n",
    "Words that fit a phone number.\n",
    "\n",
    "Extension: non-ascii unicode in input"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rainfall problem\n",
    "http://dl.acm.org.libezproxy.open.ac.uk/citation.cfm?doid=6592.6594"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ten-pin bowling scores. \n",
    "Given a sequence of number of pins knocked down, calculate total score.\n",
    "\n",
    "Extension: the sequence of scores is for several players, doing round after round. Who wins?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pack and justify text into paragraphs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Word chain puzzles\n",
    "Given a start and end word and a dictionary, find a chain of valid words transforming one to the other.\n",
    "\n",
    "Extension: what is the shortest chain? What is the longest chain without repeated words?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Amidakuji / Ghost leg](https://en.wikipedia.org/wiki/Ghost_Leg)\n",
    "Derangement network simulation.\n",
    "\n",
    "Extension: sum several networks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parcel pricing\n",
    "By weight and volumetric weight. \n",
    "\n",
    "Find total postage cost of list of parcels. Each parcel given as w, h, l, mass.\n",
    "\n",
    "Extension: find the volumetric weight of the packages. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parcel wrapping: \n",
    "First, find area, \n",
    "\n",
    "Extension: find width of 1m strip to wrap. Include extra for wriggle room."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mastermind\n",
    "How many valid solutions remain after the scores you've seen\n",
    "\n",
    "Extension: How many scores are possible for this attempt?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lift simulator\n",
    "Given a sequence of lift calls (time of call, floor of call, destination of passenger), what is the best solution to move all the passengers? Cost sum of passenger waits, where a passenger wait is the time between calling a lift and arriving at destination.\n",
    "\n",
    "Extension: multiple lifts?\n",
    "\n",
    "Extension: limited capacity in lift"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# More problems:\n",
    "* [Advent of Code 2015](http://adventofcode.com/2015)\n",
    "* [Advent of Code 2016](http://adventofcode.com/2016)\n",
    "* [Programming and Problem Solving with C++: Brief Edition](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",
    "* https://www.cs.uoregon.edu/Activities/Luks_Programming_Contest/ , specifically the overlapping presentaitons problem from [2017 problems](https://www.cs.uoregon.edu/Activities/Luks_Programming_Contest/problems/Problems2017.pdf)\n",
    "* https://www.reddit.com/r/dailyprogrammer/\n",
    "\n",
    "* N-rooks problem from http://www.olympiad.org.uk/images/bio2012-poster-v.jpg\n",
    "\n",
    "* \"How tweet it is\" from [2014 APL programming language competition](http://www.dyalog.com/uploads/files/student_competition/2014_problems_phase1.pdf) (remove interior vowels from words)\n",
    "\n",
    "* More ghost leg: simplify a network by finding whole permuation, then splitting it down into transpositions. Look at theory of permutations for details.\n",
    "\n",
    "* [Strata](https://en.wikipedia.org/wiki/Strata_(video_game)) game: how many puzzles have a valid solution? How many valid solutions are there to a puzzle?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Related research\n",
    "* https://computinged.wordpress.com/2016/12/16/graduating-dr-briana-morrison-posing-new-puzzles-for-computing-education-research/\n",
    "* https://computinged.wordpress.com/2010/08/16/a-challenge-to-computing-education-research-make-measurable-progress/\n",
    "* http://dl.acm.org.libezproxy.open.ac.uk/citation.cfm?doid=6592.6594\n",
    "* https://computinged.wordpress.com/2017/01/18/power-law-of-practice-in-software-implementation-does-this-explain-the-w-going-away/\n",
    "* https://www.cs.utexas.edu/users/mckinley/305j/pair-hcs-2006.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Polyglot challenge languages\n",
    "\n",
    "- Python\n",
    "- Ruby\n",
    "- Haskell\n",
    "- Lisp\n",
    "- Prolog\n",
    "- Ada\n",
    "- C\n",
    "- Brainfuck\n",
    "- Whitespace\n",
    "- x64 assembler\n",
    "- Smalltalk\n",
    "- Scala\n",
    "- Clojure\n",
    "- Lua\n",
    "- JavaScript\n",
    "- Java\n",
    "- Dart\n",
    "- Kotlin\n",
    "- Elixir / Erlang\n",
    "- Oz / Mozart\n",
    "- APL / J\n",
    "- Rust\n",
    "- Go"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Polyglot challenge: languages by day\n",
    "\n",
    "1. [Ticket prices](01-ticket-prices): Ruby x\n",
    "2. [Lift instructions](02-lifts): Brainfuck x\n",
    "3. [Door codes](03-door-codes): Dart x\n",
    "4. [Ghost leg, follow and pack](04-amidakuji): Clojure\n",
    "5. [Display board](05-display-board): JavaScript/Node.js\n",
    "6. [Tour shapes](06-tour-shapes): Lua\n",
    "7. [Virtual machine](07-interpreter): Haskell (Advent 16 day 23)\n",
    "8. [Word chains](08-word-chains): Prolog\n",
    "9. [Resolving the bill](09-resolving-the-bill): Sense\n",
    "10. [Word search](10-word-search): Python x\n",
    "\n",
    "Scala, Clojure?\n",
    "Sense? Day 9?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.5.2+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}