StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>One way to reduce the search space is to consider this: A string of length <code>n</code> can be colorful only if the substring given by its first <code>n-1</code> characters is also colorful. That this assertion is true should be fairly obvious.</p> <p>Suppose you have a function <code>colorful(n)</code> which returns the set of all colorful strings of length <code>n</code>. You could implement it recursively, like this:</p> <pre><code>colorful(n): if n = 1: return { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" } def colorful_subs = colorful(n-1) def colorfuls for each sub in colorful_subs: remaining_digits = { 2, 3, 4, 5, 6, 7, 8, 9 } - digits_in(sub) for each digit in remaining_digits: if is_colorful(sub, digit): colorfuls += (sub + digit) return colorfuls </code></pre> <p>And the supporting function <code>is_colorful</code> can take advantage of the fact that the substring given as the first argument is <em>already known to be colorful and to not contain the appended digit</em>.</p> <p>Then call <code>colorful(n)</code> and select the <code>k</code>th element of the returned set. (note that we <em>do</em> have to include "0" and "1" in the base case, otherwise it would give the wrong answer for <code>n</code>=1)</p> <p>This is basically a <a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow noreferrer">dynamic programming</a> approach. I'm sure this could be improved -- there might be a clever way to figure out if appending a certain digit to a colorful number would make the number no longer colorful without actually doing it and checking. But this certainly does check considerably fewer numbers than all of the possible permutations of 2-9.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload