"cell_type": "markdown",
"metadata": {},
"source": [
- "# Project ideas"
+ "# Project ideas\n",
+ "\n",
+ "[Project workspace](https://learn2.open.ac.uk/course/view.php?id=206050)\n"
+ ]
+ },
+ {
+ "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": [
- "## Wordsearch: \n",
+ "## [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": [
- "Travelling salesman: given a network, find the shortest route between them, without visiting the same spot twice.\n",
+ "## 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: run the assembly program, what's the result?\n",
- "Extension: run it again on different input."
+ "# 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: 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",
+ "## 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: words that fit a phone number.\n",
+ "## 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",
+ "## 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. Given a sequence of number of pins knocked down, calculate total score."
+ "## 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."
+ "## Pack and justify text into paragraphs."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
- "Word chain puzzles"
+ "## 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": [
- "Machine code execution: Collatz sequence, count steps."
+ "## 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 pricing, by weight and volumetric weight. Find total postage cost of list of parcels. Each parcel given as w, h, l, mass."
+ "## 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": [
- "Parcel wrapping: first, find area, then find width of 1m strip to wrap. Include extra for wriggle room."
+ "## 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": [
- "Mastermind: how many valid solutions remain after the scores you've seen\n",
- "How many scores are possible for this attempt?~"
+ "## 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"
]
},
{
"metadata": {},
"source": [
"# More problems:\n",
+ "* [Advent of Code 2015](http://adventofcode.com/2015)\n",
+ "* [Advent of Code 2016](http://adventofcode.com/2016)\n",
"* 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/\n",
"* https://www.reddit.com/r/dailyprogrammer/"
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
- "version": "3.5.2"
+ "version": "3.5.2+"
}
},
"nbformat": 4,
projects / ou-summer-of-code-2017.git / blobdiff