Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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).

share|improve this question
    
What about 1213? –  Ypnypn Jul 16 at 16:29
    
@Ypnypn Doesn't exist. –  Sieg Jul 16 at 17:01
    
@TheRare Which means the two sequences (normalizing sequence and A071159) are not equivalent and the task therefore does not match its description. –  Howard Jul 16 at 17:11
    
@tolos Can you please clarify which of the two sequences you want to have? Until then I am voting to close as "unclear what you are asking". –  Howard Jul 16 at 17:20
    
Btw. the variable normalizing sequence seems to be A193023. –  Howard Jul 16 at 17:21

5 Answers 5

up vote 4 down vote accepted

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
share|improve this answer

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
share|improve this answer

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.

share|improve this answer
    
you ca save a char by turning for(int i=2;i<=b;i++)c*=(i+b)/i into for(int i=2;i<=b;)c*=(i+b)/i++ –  Not that Charles Jul 16 at 18:17
    
Oops, just noticed that I'm calculating the Nth catalan number which is not what was asked, I'll be updating this as soon as I have the answer. –  BrunoJ Jul 16 at 20:52

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.

share|improve this answer
    
It's funny how I tend to find Powershell to be the most obfuscated language. –  Sieg Jul 16 at 19:24
    
@TheRare Yeah, when it's done really well (aka not by me) Powershell can be really freaking confusing to look at from the outside. Still got nothin' on Brainfuck or Golfscript or stuff like that... –  fuandon Jul 17 at 20:10
    
Honestly, I find both of those cleaner. –  Sieg Jul 17 at 20:17

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 =<<.

share|improve this answer
1  
save three characters: c=1: instead of c=[1]++ –  MtnViewMark Jul 17 at 6:56
    
Thanks, @MtnViewMark! Don't know what happened there.. –  Matt Noonan Jul 17 at 12:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.