X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=problem-ideas.ipynb;h=a4fe4ab601daeaa46ce23d4dc7cc72bf38434e57;hb=130c870164e49bc33d63a887ecbaee95e4fa9997;hp=72ca0213a43ada33a09cc9f6fe5d9abccc2355fc;hpb=6bce78b3e53a6a4399d9108f7fc9c7f2c7b31945;p=ou-summer-of-code-2017.git diff --git a/problem-ideas.ipynb b/problem-ideas.ipynb index 72ca021..a4fe4ab 100644 --- a/problem-ideas.ipynb +++ b/problem-ideas.ipynb @@ -4,7 +4,43 @@ "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": [ + "## 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-08-amidakuji)\n", + "5. [Display board](05-display-board)\n", + "6. [Tour shapes](06-tour-shapes) [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\n", + "7. [Virtual machine](07-interpreter)\n", + "8. [Ghost leg, simplify](04-08-amidakuji)\n", + "9. [Word chains](09-word-chains)\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" + ] + }, + { + "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..." ] }, { @@ -33,7 +69,10 @@ "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?" @@ -63,8 +102,11 @@ "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?" ] }, @@ -72,15 +114,19 @@ "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?" ] }, @@ -88,7 +134,9 @@ "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?" ] }, @@ -96,6 +144,7 @@ "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)" ] }, @@ -103,7 +152,9 @@ "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" ] }, @@ -111,7 +162,7 @@ "cell_type": "markdown", "metadata": {}, "source": [ - "Rainfall problem:\n", + "## Rainfall problem\n", "http://dl.acm.org.libezproxy.open.ac.uk/citation.cfm?doid=6592.6594" ] }, @@ -119,28 +170,36 @@ "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" ] }, @@ -148,29 +207,44 @@ "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" ] }, { @@ -178,6 +252,8 @@ "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/" @@ -195,6 +271,33 @@ "* 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" + ] + }, { "cell_type": "code", "execution_count": null, @@ -221,7 +324,7 @@ "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", - "version": "3.5.2" + "version": "3.5.2+" } }, "nbformat": 4,