Output nth term in Catalan type sequence

Question

Given a number, starting with 1, create new numbers (children) by taking the last digit, n, and concatenating 1 through n+1.

This seems to be a much better explanation of the sequence A071159.

Integers whose decimal expansion start with 1, do not contain zeros and each successive digit to the right is at most one greater than the previous.

1, 11, 12, 111, 112, 121, 122, 123, 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1221, 1222, 1223, 1231, 1232, 1233, 1234, 11111, 11112, ...

Personally I find the description for the sequence rather unhelpful, and find it is easier to understand with a graph.

                              1
          11-------------------------------------12
      111----112                     121---------122----------123
1111-1112    1121-1122-1123    1211-1212    1221-1222-1223    1231-1232-1233-1234

I find the graph rather interesting as it is very self-repeating. For instance, the left-most node on a branch is always identical to the root node. Might be easier to see on this graph.

Challenge

Submit a solution that can output the nth item of sequence A071159.

Rules

Your submission should be able to calculate any item before number 23713. A071159(23713) is the first time a 10 would appear as a single digit (12345678910; comma-separated 1,2,3,4,5,6,7,8,9,10).

Answer 1

GolfScript (29 chars)

~([1]{.{.10*)\10%{.)}*}%|}9*=

This is a pretty naïve implementation, although reasonably fast.

~(         # Evaluate input, decrement to get a 0-based index
[1]        # Initial row of tree
{          # Loop: stack is the first n rows of the tree as an array
  .        # Duplicate the array
  {        # Map: extend each element of the array into its children
    .10*)  # Get the first child; stack is   rows x 10x+1
    \10%   # How many more children does x have?
    {.)}*  # Those children are found by successive incrementation
  }%       # End map
  |        # Add the new unique elements (i.e. the new bottom row) to the rows
}9*        # Repeat 9 times, so that the array has 23713 correct values and one incorrect
=          # Array lookup

Answer 2

Python 2 (83) (86)

r=[1]
exec"r=[1]+[i+w*10for w in r for i in range(1,w%10+2)];"*9
print r[input()-1]

Explanation to come.

A completely different approach of counting up an testing for membership in the sequence (87 chars). Take ridiculously long for larger numbers,

n=0
k=input()
while k:n+=1;k-=all(0<int(b)<2+int(a)for a,b in zip('0'+`n`,`n`))
print n

Answer 3

JAVA (146)

I know I'm not winning this, but oh well:

public class a{public static void main(String[]a){float b=Float.parseFloat(a[0]);float c=1;for(int i=2;i<=b;i++)c*=(i+b)/i;System.out.print(c);}}

Just straightforward from Wikipedia, any tips for further golfing this will be appreciated.

Answer 4

Powershell (136)

$n=Read-Host;$x=,'1';$a=1;While($x.length-lt$n){$b=[int]$x[$a-1].Substring($x[$a-1].length-1);1..($b+1)|%{$x+=$x[$a-1]+$_};$a++}$x[$n-1]

Probably some wasted characters here, but I'm still learning. $a traverses the list as it's being built (each level of the tree). $b takes the last digit of the current item, then the loop after that adds on 1 to $b+1 to the end of the current item and adds it to the array $x.

Loop is a bit inefficient, as the $n-1 index is necessary because it doesn't always stop on the nth number of the sequence that you want.

But hey, it's my first draft. And it replicated the correct sequence output based on the input here.

Also an input of 23713 produces an output of 12345678910.

Answer 5

Haskell (73)

c=1:((\n->[10*n+d|d<-[1..n`mod`10+1]])=<<)c;main=readLn>>=print.((0:c)!!)

And ungolfed:

step n = [ 10*n + d | d <- [1 .. lastDigit+1] ]
    where lastDigit = n `mod` 10

soln = 1 : concatMap step soln

main = do
    n <- readLn
    let nthTerm = soln !! (n - 1)
    print nthTerm

soln is a list containing the entire A071159 sequence.

The step function is not very interesting, just a straightforward list comprehension that takes a number to the list of its children in the OP's tree.

The main function's only trick is to do 1-based indexing of [1,11,12,...] by using 0-based indexing on [0,1,11,12,...], saving a character.

The real fun is in the recursive definition of soln, which does the breadth-first traversal of the OP's tree. A couple characters are saved by replacing concatMap with its generalization =<<.