19
\$\begingroup\$

Sometimes when I get the urge to post a new challenge, I have trouble finding a notable* problem that has not yet been solved upon which to base my challenge (I'm not very creative). I thought it might be cool if we could generate a list of such problems here.

Here are some examples that I tried to find using the search box on Code Golf.

Here is one example of a problem that has been used before (many times).

Please post notable* problems that have not yet been touched. Post as many as you can think of. Correct other answers (and this question) if you see one that has been used before, but make sure that you provide a link.

If you decide to use one of the problems, leave a comment saying that you took it and link to the challenge.

*A notable problem is one that has been discussed in Academia as opposed to one you just thought of.

\$\endgroup\$
3
  • \$\begingroup\$ I would be surprised if max flow isn't covered by one of the various calculate-the-resistance questions. \$\endgroup\$
    – Peter Taylor
    Apr 23, 2014 at 10:40
  • \$\begingroup\$ Am I right that we have hardly covered any data structures on PPCG? \$\endgroup\$
    – user9206
    Apr 28, 2015 at 18:32
  • 1
    \$\begingroup\$ I find it amusing that Peter is the only answerer yet. \$\endgroup\$
    – Riker
    Jan 5, 2016 at 20:10

4 Answers 4

Reset to default
11
\$\begingroup\$

Graph theory

The basics have been done (sometimes more than once), but some advanced stuff is still up for grabs:

  • Fractional graph-theoretic properties (e.g. fractional chromatic number)
  • vertex-connectivity.
  • ...

Ones which have been done already:

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Edge colouring? Finding the dual graph? To avoid duplicates and suggestions that have been done, it might be useful to include some of said basics with strike-through markup and a link to the question. \$\endgroup\$
    – Martin Ender
    Oct 7, 2014 at 22:17
9
\$\begingroup\$

Combinatorics

The number of ways to quarter a chessboard: http://oeis.org/A003213 . Requires some work to explain what exactly it means to quarter a chessboard.

There's one question about knot theory, but it's about testing whether a given knot is the unknot. How many prime alternating tangle types of knot are there with n crossings? http://oeis.org/A047051 . An alternative approach to this one would be to generalise it: A047051 has an ordinary generating function A(z) which satisfies a quintic equation p_5(z) A(z)^5 + ... + p_1(z) A(z) + p_0(z) = 0 where each of the p_i is a polynomial in z with integer coefficients. How about a question to evaluate ogfs defined by similar polynomial relationships and a suitable number of initial terms?

For further combinatoric ideas, watch the OEIS webcam until you spot something interesting.

\$\endgroup\$
1
  • \$\begingroup\$ Perfect! We need more like this one. It's so easy to post them, and someone else can turn it into a nice pretty challenge with well-defined inputs and outputs and such. \$\endgroup\$
    – Rainbolt
    Jul 10, 2014 at 14:50
3
\$\begingroup\$

I stumbled upon some course notes for a course on multi-agent modelling which has a list of ideas for things to model. Not all of them would be suitable, and I think one or two have been done, but it can serve as a source of ideas.

I actually found it while doing a bit of background reading on Paterson's worms, because this question on math.SE seemed like a promising idea for a challenge. (My suggestion would be a which takes worm definition and number of steps and outputs an svg).

\$\endgroup\$
2
\$\begingroup\$

Puzzles and Games

Single-player puzzles/games can easily be formulated as either (solve it) or (try to optimize the score). Two-player games can be formulated as . Indeed there are many more puzzles than you think.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .