27
\$\begingroup\$

Title is made up, from 'Sequence Index Digit Not'.

Challenge:

Given an integer n which is >= 0, output the n'th number of the following sequence.
Here are the first 50 items, with it's (0-indexed) index above it:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
1 0 3 2 5 4 7 6 9 8 22 20 30 24 23 26 25 28 27 32 11 33 10 14 13 16 15 18 17 31 12 29 19 21 50 40 41 42 44 45 35 36 37 51 38 39 52 53 55 56 34

How does this sequence work?

The number at index n must be the first in order that does not have any digits in common with n, and hasn't occurred yet for previous indexes. So when we look at normal sequence like this from 0-60:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

We define the n'th values like this:

  • 0: The first number (0) contains the same digit, so we look for the next (1), which does not contain the same digit. So n=0 outputs 1.
  • 1: The first number (0) does not contain the same digit, so n=1 outputs 0.
  • 2: We've already encountered 0 and 1, and the next digit (2) contains the same digit, so we look for the next (3), which does not contain the same digit. So n=2 outputs 3.
  • ...
  • 10: We've already encountered 0-9, so the next in line is 10. 10-19 contain the matching digit 1, 20 contains the matching digit 0, 21 contains the matching digit 1 again, 22 is valid, so n=10 outputs 22.
  • etc.

Challenge rules:

  • If your language is 1-indexed (or you choose to) you are allowed to start the sequence at 3 2 5 4 7 ... (skipping the 1 at n=0 and the 0 at n=1).
  • The minimum largest index you should support is 25,000. NOTE: The sequence stops at index 1,023,456,788, because the next index in line contains all 10 digits.
  • You are also allowed to output / return an array/list of the entire sequence up to and including index n if you want to.

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code.
  • Also, please add an explanation if necessary.

Test cases:

This sequence actually created pairs regarding index and outputs. If index n outputs o, index o outputs n. So you can input either the left or right, and the output will be the other side:

0      <->  1       (this test case is optional)
2      <->  3
10     <->  22
12     <->  30
34     <->  50
89     <->  100
111    <->  200
112    <->  300
199    <->  322
2231   <->  4456
9605   <->  11118
19235  <->  46000
23451  <->  60668
25000  <->  13674

Here is a pastebin of the first 25,001 test cases if you want to try others.

\$\endgroup\$
  • \$\begingroup\$ Related, but not a dupe. \$\endgroup\$ – Kevin Cruijssen Nov 8 '17 at 9:08
  • 3
    \$\begingroup\$ As with the related challenge, the scatterplot is quite fun. :) \$\endgroup\$ – Martin Ender Nov 8 '17 at 9:23
  • \$\begingroup\$ @MartinEnder When I saw the scatterplot of the related challenge, I indeed figured this one would be similar. Turns out it indeed is rather similar, but still different. :) \$\endgroup\$ – Kevin Cruijssen Nov 8 '17 at 9:25
  • \$\begingroup\$ How come such an important sequence is not on OEIS? \$\endgroup\$ – Stewie Griffin Nov 8 '17 at 9:48
  • \$\begingroup\$ @StewieGriffin Good question. Actually, I think all my sequence-challenges so far weren't in OEIS (yet) when I posted them. ;) \$\endgroup\$ – Kevin Cruijssen Nov 8 '17 at 9:57

13 Answers 13

3
\$\begingroup\$

Pyth, 18 bytes

u+Gf!|}TG@`H`T0hQY

Try it here! or Check more test cases!

Note that this returns the entire sequence up to index N, but the link returns the last number only, by prepending an e (end). If you want to see the raw value returned by this program, just remove it.

How it works

u+Gf!|}TG@`H`T0hQY  - Full program.

u     ...      hQY  - Reduce hQ (the input incremented) from left to right, with the
                       function ...(G, H), with starting value Y (the empty list).
                       G is the current value and H is the iteration index.
   f          0     - First integer starting from 0, that satisfies the following:
      }TG             - Appears in G...
     |   @`H`T        - Or its (string) intersection with the current index (H) is
                        non-empty.
    !                 - Logical NOT (boolean negation).
 +G                 - Append the value obtained above to the current value (G).
                      This becomes the given value for the next iteration.
                    - Implicitly print all intermediate results, or add e to print 
                      the last one.
\$\endgroup\$
6
\$\begingroup\$

Python 2, 92 91 89 88 bytes

a=()
i=0
exec"x=0\nwhile set(`x`)&set(`i`)or x in a:x+=1\na+=x,;i+=1;"*-~input()
print a

Try it online!

Prints a list of the first n+1 numbers


Different approach, which is a lot faster:

Python 2, 96 bytes

n=input()
r=range(9*n)
i=0
exec"x=0\nwhile set(`r[x]`)&set(`i`):x+=1\nprint r.pop(x),;i+=1;"*-~n

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Haskell, 80 69 bytes

f n=[x|x<-[0..],all(`notElem`show n)$show x,all(/=x)$f<$>[0..n-1]]!!0

Try it online!

Very slow for large n.

f n=
    [x|x<-[0..]     ] !!0          -- pick the first of all 'x' from [0..]
                                   -- where
      all(`notElem`show n)$show x  -- no digit of 'n' appears in 'x', and
      all(/=x)                     -- 'x' is not seen before, i.e. not in the list
               f<$>[0..n-1]        -- 'f' mapped to [0..n-1]

Edit: @Laikoni saved 10 bytes. Thanks!

\$\endgroup\$
  • \$\begingroup\$ Computing the nth term directly instead of indexing into the sequence is shorter: Try it online! \$\endgroup\$ – Laikoni Nov 8 '17 at 20:39
2
\$\begingroup\$

APL (Dyalog), 39 bytes

0∘{0=⍵:1⋄(~⍺∊0∇¨⍳⍵)∧⊃∧/≠/⍕¨⍺⍵:⍺⋄⍵∇⍨⍺+1}

Uses ⎕IO←0.

Try it online!

How?

Recursion.

0=⍵:1 - take a guess.

~⍺∊0∇¨⍳⍵ - left arg (accumulator) is not already in previous results

∧⊃∧/≠/⍕¨⍺⍵ - and the string representation of the accumulator and n are different

:⍺ - then return the accumulator.

⍵∇⍨⍺+1 - otherwise, increment accumulator and recurse.

\$\endgroup\$
  • \$\begingroup\$ Wow.. I know the default rule is "given any amount of memory and time", but your code already times out for n=10 in TIO.. :S That must be a very performance-heavy operation you're doing there. Is it the recursion that causes this, or is something else the bottleneck? \$\endgroup\$ – Kevin Cruijssen Nov 8 '17 at 13:20
  • 2
    \$\begingroup\$ @KevinCruijssen the second condition basically apply the function on the range of 0..n-1, and considering the same apply for every call, that would come roughly at a huge O(2^n). of course it would be lower with a more reasonable code, but that's where the bottleneck sits \$\endgroup\$ – Uriel Nov 8 '17 at 13:44
2
\$\begingroup\$

Python 3, 92 bytes

o=1,
for i in range(int(input())):
 x=0
 while{*str(x),x}&{*str(~i),*o}:x+=1
 o+=x,
print(o)

Try it online!

This prints all the terms up to the Nth one. Thanks to Dennis for  -4  -5 bytes!

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

Java (OpenJDK 8), 218 217 213 210 202 200 172 171 170 168 167 bytes

I cannot believe that I didn't just return k all this time...

i->{int j=-1,k=0,y=1;for(String r=" ",e=r;j++<i;r+=~-k+e,y=1)for(k=0;y>0;k++)for(int f:(k+(y=0)+"").getBytes())y+=(e+j).indexOf(f)<0&!r.contains(e+k+e)?0:1;return~-k;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Hmm, that's quite a different approach then I was using when I made the pastebin with my Java program. And it seems you can golf for(char f:(""+k).toCharArray()) to for(int f:(""+k).getBytes()), r.substring(-~r.trim().lastIndexOf(32)); and to r.substring(r.lastIndexOf(32)-1). \$\endgroup\$ – Kevin Cruijssen Nov 8 '17 at 10:49
  • \$\begingroup\$ Must be trimmed before lastIndexOf as there's a space on the end \$\endgroup\$ – Roberto Graham Nov 8 '17 at 11:02
  • \$\begingroup\$ Ah, I indeed made a mistake.. I knew the String contained both a leading and trailing space, but my incorrectly suggested change only works for the first 10 single-digit numbers.. My bad \$\endgroup\$ – Kevin Cruijssen Nov 8 '17 at 11:10
2
\$\begingroup\$

Go, 217 205 bytes

package g;import("fmt";"strconv";"strings");var(
d=make(map[int]int)
a=strconv.Itoa)
func G(L int){k,i:=0,0;for;i<=L;i++{s:=a(i);k=0;for d[k]>0||strings.ContainsAny(a(k),s){k++;}
d[k]=1;}
fmt.Print(a(k));}

Alternate version (program instead of a package): Try it online!

Improvements:

  • removed space after outer for by using multiple assignment for i,k
  • importing "fmt"; + fmt.Print is shorter than os.Stdout.WriteString (holdover from package main when os.Args was needed)
\$\endgroup\$
  • \$\begingroup\$ Nice, your answer is the first that doesn't time out after 1 minute when I try the 25000 test case. :) So not only a valid solution, but with relatively good performance as well. +1 from me! (PS: In your TIO-link it's the argument you use, input can be removed / is not used.) \$\endgroup\$ – Kevin Cruijssen Nov 8 '17 at 20:45
2
\$\begingroup\$

JavaScript (ES6), 103 88 81

Edit Revised including many clever ideas by @Neil

n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

Starting point

Basic idea: a loop from 0 to n, and an inner loop checking values still not used

n=>{
  var r=[]
  for(i=0;i<=n;i++)
  {
    s=new Set(i+'')
    for(j=-1;s;)
    {
      if (!r[++j] && ![...j+''].some(d=>s.has(d)))
      {
        r[j]=1
        console.log(i,j)
        s=0
      }
    }
  }
  return j
}

Current version more readable

n=>{
  for(r = [j=i=0]; i <= n; )
    if (r[j] || (i+'').match(`[${j}]`))
      ++j
    else
      r [k=j] = ++i,
      j = 0;
  return k
}

Test

var f=
n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

update=_=>{
  var i=+I.value
  if (i < 1e4 || confirm("Really?")) {
    O.textContent=i + ' -> ...'
    setTimeout(_=>O.textContent=i + ' -> ' + f(i), 100)
  }
}  

update()
<input id=I value=100 type=number max=1023456788>
<button onclick='update()'>Go</button>
(slow when input > 1000)
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ Would replacing ~s.search(d) with s.match(d) work? \$\endgroup\$ – Neil Nov 8 '17 at 16:19
  • \$\begingroup\$ I think you can save another byte by changing 0 to j++, removing the ++ from the j it was on before and then starting j from 0 instead of -1. \$\endgroup\$ – Neil Nov 8 '17 at 16:28
  • \$\begingroup\$ I think I was able to switch to a single loop: n=>eval("for(r=[j=i='0'];i<=n;)r[j]|[...''+j].some(d=>i.match(d))?j++:(i=++i+'',r[k=j]=1,j=0);k") \$\endgroup\$ – Neil Nov 8 '17 at 16:35
  • \$\begingroup\$ @Neil a single loop would be wonderful \$\endgroup\$ – edc65 Nov 8 '17 at 20:06
  • \$\begingroup\$ @Neil the single loop is great, thanks \$\endgroup\$ – edc65 Nov 8 '17 at 20:49
2
\$\begingroup\$

Octave, 114 bytes

N=input("");o=[1];for i=1:N;j=0;while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));j++;end;o=[o,j];end;[0:N;o]

Try it online!

Thanks to Kevin Cruijssen and Dlosc for the character comparison golfing.

Ungolfed

N=input("");o=[1];

for i=1:N;
    j=0;
    while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));
        j++;
    end;
    o=[o,j];
end;
[0:N;o]

Basic explanation:

  • Outer loop and inner loop, one for index i, and another for value to add j
  • For each i, continue to increment j if either of the following are met:

    1. Any j has been used before
    2. This one gets fun. First, split each numeric value into a vector of digits (e.g., 10 becomes [1 0]) using int2str. Then, compare the two numbers using ismember(e.g., [1 0] and [2 1] would return [1 0]) and then nnz to see if any columns matched.
  • If none of the above are met, you have the next number! Append to o, the output matrix

  • Print original indices with output matrix
\$\endgroup\$
  • \$\begingroup\$ Nice answer, +1 from me. And seems @DLosc is right, it works even without both -'0'. But if there is some edge case we both haven't thought of, -48 would be a shorter alternative. Also, both sprintf('%d',...) can be int2str(...). \$\endgroup\$ – Kevin Cruijssen Nov 9 '17 at 8:04
1
\$\begingroup\$

Perl 5, 60 bytes

59 bytes code + 1 for -p.

$_="@{[0..($;=++$_)*9]}";$_=eval's/\b[^ $-]+ //;$-++;$&;'x$

Try it online! (Includes -l for visual purposes and $-=0; to reset each iteration)

\$\endgroup\$
1
\$\begingroup\$

Pip, 30 bytes

29 bytes of code, +1 for -p flag.

Fn,a+1{Y0WyNl|_NyMSn++ylPBy}l

Try it online!

Outputs the whole list. Warning: highly inefficient; the 2231 input case has been running for 35+ minutes on my laptop and still hasn't finished.

Explanation

                               a is cmdline arg, l is [] (implicit)
Fn,a+1{                    }   For each n in range(a+1):
       Y0                       Yank 0 into y
         W                      While...
          yNl|                  y is in l, or...
              _Ny               lambda function: arg is in y
                 MSn            mapped to digits of n and result list summed
                                (i.e., any digit of n is in y):
                    ++y          Increment y
                       lPBy     Once we have a y that meets the criteria, push it to
                                the back of l
                            l  Output l (formatted with -p flag)
\$\endgroup\$
1
\$\begingroup\$

Visual Basic .NET (.NET 4.5), 260 259 bytes

-1 byte thanks to Kevin Cruijssen

Function A(n)
Dim p=New System.Collections.Generic.List(Of Long),j="0",g=0
For i=0To n
j=0
While 1
If Not p.Contains(j)Then
g=1
For Each c In i.ToString
If j.Contains(c)Then g=0
Next
If g Then Exit While
End If
j+=1
End While
p.Add(j)
Next
A=p(n)
End Function

Loops through, generating previous terms in the sequence to then compare later. Then iterates the number as a string looking for matches.

Abuses VB.NET's typing system. For example, j is a string, but adding one converts to an integer for me. Integers are converted to Booleans where 0 is False and the rest are True.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I never programmed in Visual Basic, but it seems you can remove the space at If Not p.Contains(j)Then same like you did at If j.Contains(c)Then g=0 below. Also, If Not p.Contains(j)Then \n g=1 \n For Each c In i.ToString \n If j.Contains(c)Then g=0 \n Next \n If g Then Exit While \n End If can be shortened by removing g and using Exit While directly in the for-loop: If Not p.Contains(j)Then \n For Each c In i.ToString \n If j.Contains(c)Then Exit While \n Next \n End If, which will become 241 bytes by the looks of it. \$\endgroup\$ – Kevin Cruijssen Nov 9 '17 at 18:20
  • \$\begingroup\$ @KevinCruijssen Definitely can remove the space to make it Contains(c)Then, I just missed it. I like what you're thinking, but I'm using g as a sentinel to see if the string contains the number or not. Your link gives the wrong answers, but I'll see if I can rework some of the inner logic along what you're thinking. \$\endgroup\$ – Brian J Nov 9 '17 at 18:26
  • \$\begingroup\$ Ah oops.. It indeed fails.. Now it's only outputting the input. My bad. Shouldn't make these comments when it's evening and I'm tired from work. ;) \$\endgroup\$ – Kevin Cruijssen Nov 9 '17 at 18:41
1
\$\begingroup\$

Jelly, 20 bytes

Pyth beats Jelly. Go Mr. Xcoder!

Df⁹LD¤ȯeṆ
0ç1#ɓ;
1Ç¡

A full program taking input from STDIN and outputting in the list format option using Jelly's list representation*. Uses the standard 0 based indexing.

* single element lists have no surrounding [], so 0 outputs 1, while 1 outputs [1, 0] etc.

Try it online!

How?

Df⁹LD¤ȯeṆ - Link 1, can append n to current? n, number; current, list
D         - convert n to decimal list
     ¤    - nilad followed by link(s) as a nilad:
  ⁹       -   chain's right argument, current
   L      -   length
    D     -   convert to a decimal list
 f        - filter discard from left if not in right
       e  - n exists in current?
      ȯ   - left logical OR right (empty lists are falsey)
        Ṇ - logical NOT

0ç1#ɓ; - Link 2, append next number: current, List
   #   - n find (count up finding first n matches):
  1    - ...finding: 1 match
0      - ...stating at: n=0
 ç     - ...doing: the last link as a dyad (left=n, right=current)
    ɓ  - new swapped-arg-dyadic chain (left = current, right = list of the found n)
     ; - concatenate

1Ç¡ - Main link: no arguments
1   - initialise the return value to 1
  ¡ - repeat input() times:
 Ç  -   last link (2) as a monad
    - implicit print
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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