Asha loves mathematics a lot. She always spends her time by playing with digits. Suddenly, she is stuck with a hard problem, listed below. Help Asha to solve this magical problem of mathematics.

Given a number N (using any standard input method), compute how many integers between 1 and N, inclusive, do not contain two consecutive identical digits. For example 1223 should not be counted, but 121 should be counted.

Test Cases

7 => 7
1000 => 819
3456 => 2562
10000 => 7380

Scoring

This is , so the shortest answer in bytes wins.

share|improve this question
2  

24 Answers 24

Perl 5, 22 bytes

21 bytes of code + -p flag.

$_=grep!/(.)\1/,1..$_

Try it online!

grep returns a list of all elements from 1 to $_ (the input) that satisfy the condition !/(.)\1/ (ie. all the elements that don't have consecutive digits). Then $_= assigns the size of that list to $_, which is implicitly printed at the end thanks to -p flag.

share|improve this answer

Python 2, 72 bytes

lambda n:sum(all(a!=b for a,b in zip(`i`,`i`[1:]))for i in range(1,n+1))

Try it online!


shorter recursive solution at 61 bytes, will overflow for f(1000):

f=lambda i:i and all(a!=b for a,b in zip(`i`,`i`[1:]))+f(i-1)

Try it online!

share|improve this answer
    
+1, I've just wrote the same thing, but wasn't fast enough to post :D – Dead Possum 14 hours ago
    
You can save 2 bytes by removing 1 inside the range. You can just write for i in range(n+1) – Mr. Xcoder 12 hours ago
    
@Mr.Xcoder This would include 0 and yield an result 1 too high – ovs 12 hours ago

Jelly, 6 bytes

DIẠµ€S

Try it online!

Well, this was a) easier than I expected before I started writing it, but b) longer than I expected it to be once I started writing it (several Jelly commands have an implicit D when run on an integer, and I expected I to be one of them, but it isn't).

Explanation

DIẠµ€S
   µ€    Run the following on each value from 1 to the input:
D          Convert it to decimal;
 I         Take deltas between consecutive elements;
  Ạ        then output 1 if all the deltas are nonzero, 0 if any are zero.
     S   Then add all the resulting values together.

Clearly, two consecutive equal digits give us a delta of 0, two consecutive nonequal digits give us a nonzero delta.

share|improve this answer
    
Wow, I had no idea this ...µ€ construction would create a range implicitly. – steenbergh 10 hours ago
    
@steenbergh It's actually which implicitly creates the range. – Erik the Outgolfer 10 hours ago

Brachylog, 13 bytes

⟦₁{ẹḅ{l1}ᵐ}ˢl

Try it online!

Assuming I understood the challenge correctly…

Explanation

⟦₁                 Range: [1, …, Input]
  {       }ˢ       Select the integers of the range which verify:
   ẹḅ                Take the list of lists of consecutive equal digits
     {l1}ᵐ           All of those sublists must have one element
            l      Output = number of selected integers
share|improve this answer

JavaScript (ES6), 31 bytes

f=n=>n&&f(n-1)+!/(.)\1/.test(n)

Will stack overflow on large enough inputs.

share|improve this answer

Jelly, 10 9 bytes

DIP
çÐf$L

Try it online!

Thank you, @JonathanAllen, for saving one byte!

Explanation:

çÐf$L     Main link
          Using Ðf creates a range from 1 - N implicitly.
 Ðf       Filter out all falses from te implicit range where
ç         The helper link returns a 0
   $L     Then output the length of the remaining list.

DIP        Helper link
D          Break number into a list of digits
 I         Get a list of consecutive increments
  P        And take the product. This is 0 for repeating digits.
share|improve this answer
1  
I think you can use the fact that Jelly will form a range implicitly and hence remove R. – Jonathan Allan 8 hours ago

05AB1E, 7 bytes

>GNDÔQO

Try it online!

Explanation

>G        # for N in range[1 ... input] do
  N       # push N
   DÔ     # duplicate and remove consecutive equal elements
     Q    # push is equal
      O   # sum
share|improve this answer

Retina, 23 19 15 bytes

Thanks to Martin Ender and Neil for all the help!


$.'¶
A`(.)\1
¶

Takes input in unary, using 0 as unary digit, outputs in decimal.

Try it online! (Has an added header to convert from decimal)

Explanation


$.'¶

Build the descending range [n,0] by inserting in every position the number of characters coming after it, plus a newline. There will be a leading 0 in every number of the range but the first. For example, this stage would turn the string 000 into 3\n02\n01\n00\n.

A`(.)\1

Drop all lines that contain a character repeated two times. This will also get rid of the final 0 of the range, since another 0 has been prepended to it.

Count the number of remaining newlines

share|improve this answer
1  
Save 1 byte: Try it online! – Neil 12 hours ago
    
@Neil that's really neat. :) This saves another: tio.run/nexus/retina#09PmUtH6z6VjoKKXcGgbl2OChp5mjCHXoW3//… – Martin Ender 12 hours ago
    
@MartinEnder Whoa, I was struggling to work out what to do with all of those left-over 1s... do you really need the comma though, 10 doesn't duplicate a digit. – Neil 12 hours ago
    
@Neil Yeah, I just realised that. I first had the , to deal with the 1s but then had trouble to get rid of the line with the 0. I didn't consider that just adding a zero suffices, but that saves another byte then. – Martin Ender 12 hours ago
    
@MartinEnder Thank you again, I've golfed that solution a bit more requiring 0 to be used as unary digit... Do you think that's a fair input requirement? – Leo 10 hours ago

Röda, 46 35 bytes

{[_-#[seq(1,_1)|grep`.*(.)\1+.*`]]}

Try it online!

Explanation:

{[_-#[seq(1,_1)|grep`.*(.)\1+.*`]]}
{                                 } /* Anonymous function */
      seq(1,_1)                     /* Creates a sequence from 1 to _1 */
               |grep`.*(.)\1+.*`    /* Filter numbers having consecutive digits */
    #[                          ]   /* Length of stream */
  _-                                /* Subtract from _1 */
 [                               ]  /* Return the result */

_ and _1 represent a number in the input stream (ie. N). There can be many numbers in the input stream, in which case the function calculates the result for all of them.

Old solution

{[#[seq(1,_)|replace`(.)\1+`,"$1"|sort|uniq]]}

Try it online!

share|improve this answer

MATL, 8 bytes

:"@VdAvs

Try it online!

:       % Implicitly input N. Push row vector [1 2 ... N]
"       % For each k in that array
  @     %   Push k
  V     %   String representation
  d     %   Consecutive differences
  A     %   True if they are all nonzero
  v     %   Concatenate all stack contents into a column vector
  s     %   Sum
        % Implicitly end loop and display stack
share|improve this answer

Japt, 21 bytes

ò è@!Xs f"(.)%1+"} -1

Try it online!

share|improve this answer
    
You can save... um... 4 bytes, I think, by doing ò1 è@!Xs f"(.)%1+. I should add a builtin for creating the range [1...N]... – ETHproductions 5 hours ago
    
Also, I don't think you need the + in the regex, saving another byte. – ETHproductions 5 hours ago

JavaScript (ES6), 71 70 63 bytes

a=>[...Array(a+1).keys()].filter(b=>!/(.)\1+/.test(b)).length-1

Saved 1 byte thanks to Dada. Saved 7 bytes thanks to Neil.

f=a=>[...Array(a+1).keys()].filter(b=>!/(.)\1+/.test(b)).length-1

console.log(f(7))
console.log(f(1000))
console.log(f(3456))
console.log(f(10000))

share|improve this answer
1  
I'm not familiar with JS, but maybe /(.)\1/ would be enough for your regex. – Dada 14 hours ago
    
Use [...array] instead of Array.from(array). – Neil 13 hours ago
    
@Neil Keep forgetting about that one, thanks! – Tom 12 hours ago

Brachylog, 13 bytes

{≥ℕ₁ṡ¬{s₂=}}ᶜ

Try it online!

Here's a completely different solution from @Fatalize's, in the same number of bytes, and more of a direct translation of the question. In general, Brachylog is really good at expressing this sort of question, but held back by a syntax that's fairly verbose for a golfing language.

Explanation

{≥ℕ₁ṡ¬{s₂=}}ᶜ
{          }ᶜ   Count the number of ways to
 ≥              find a number less than or equal to the input
  ℕ₁            that's a positive integer
    ṡ           that when converted to a string
     ¬{   }     does not fulfil the following condition:
       s₂         some 2-element substring
         =        has all its elements equal to each other

If only {} weren't two bytes, this could be fairly competitive with some of the other golfing languages. Perhaps a useful innovation would be for various metapredicates like and ~ to apply to the whole program if they're moved to the "wrong" end of the program (which would at present be a syntax error). Sequences like ≥ℕ₁ are also common enough to arguably deserve their own bulitin. Still, I don't think this could reasonably be reduced below 8 bytes even with a Jelly-like constructor for short predicates, a condensed representation of ≥ℕ₁ or ≥ℕ₁≜, and a cheap-in-bytes way to metapredicate the program as a whole. (It's unsurprising that 05AB1E is winning, really; this is the type of problem it specialises in.)

For people who are aware of the fairly crazy way "not" works in Prolog, note that my use of implicitly labelizes the number, thus forcing the "not" to act on each individual number rather than on the concept of all numbers as a group.

share|improve this answer

C, 114 bytes

f(int n){int i=1;int c=n;for(;i<=n;i++){int m=-1;int x=i;while(x){if(x%10==m){c--;break;}m=x%10;x/=10;}}return c;}
share|improve this answer
1  
You can golf this down to about 101 bytes by using the fact that you don't need the keyword int to declare variables global and taking advantage of the ; in the for(...) loop i,c,m,x;f(n){i=1;for(c=n;i<=n;i++){m=-1;x=i;while(x){if(x%10‌​==m){c--;break;}m=x%‌​10;x/=10;}}return c;} – cleblanc 9 hours ago
    
I was able to golf it down to 99 this way i,c,m,x;f(n){i=1;for(c=n;i<=n;i++){for(m=-1,x=i;x;x/=10){if(‌​x%10==m){c--;break;}‌​m=x%10;}}return c;} – cleblanc 5 hours ago

Bash + GNU utilities, 24

  • 1 byte saved thanks to @MitchellSpector
seq $1|egrep -cv '(.)\1'

Try it online.

share|improve this answer
1  
I think you can take out the + and save a byte. – Mitchell Spector 7 hours ago

Mathematica, 61 53 bytes

Count[x_/;Differences@IntegerDigits@x~FreeQ~0]@*Range

This function first calls Range on the input (giving a list from 1 to the input) and then calls another function on it which counts the number of values which satisfy:

Differences@IntegerDigits@x~FreeQ~0

I.e. it checks that there are no zeros in the consecutive differences of the digits of the value.

share|improve this answer

Python 2, 83 bytes

lambda n:len(filter(lambda n:not __import__("re").search("(.)\\1",`n+1`),range(n)))

Try it online!

share|improve this answer
    
This returns 6 for 7 as input. – Dead Possum 14 hours ago

AHK 54 bytes

Loop,%1%
If RegExMatch(A_Index,"(.)\1")=0
i++
Send %i%

Nothing special here. %1% is the first passed parameter for AHK. It saves a few bytes because AHK assume that anything that would normally have brackets - like Loop or If - but doesn't have brackets this time only includes the next line.

share|improve this answer

Stacked, 28 bytes

~>[tostr'(.)\1+'match#']NO#'

Try it online!

I wonder if rle worked correctly I could save bytes...

Explanation

~>[tostr'(.)\1+'match#']NO#'  input: n
~>                            range: range from 1 to n
  [                    ]NO    reject values that satisfy the inner condition
   tostr                      cast to string
        '(.)\1+'match         extract the parts that match the regex
                     #'       get the length of the matches
                          #'  get the length of the numbers that match
share|improve this answer

Haskell, 50 bytes

f n=sum[1|x<-[1..n],and$zipWith(/=)=<<tail$show x]

Usage example: f 10000 -> 7380. Try it online!

Take a 1 for every number x between 1 and n where the string representation of x only has unequal neighbor elements. Sum the 1s.

share|improve this answer

C (gcc), 151 138 129 100 97 92 bytes

Time to golf this way down...

i[9];k;f(j){char*n=i;for(sprintf(i,"%d",j--);*n&&*n!=*++n;);k+=!*n;return!j?n=k,k=0,n:f(j);}

Try it online!

share|improve this answer

Swift 3, 131 bytes

func c(n:Int)->Int{return(1...n).filter({j->Bool in((0...9).reduce(1){$0*(("\(j)".range(of:"\($1)\($1)")==nil) ?1:0)})==1}).count}
share|improve this answer

PHP, 50 Bytes

echo count(preg_grep('#(.)\1#',range(1,$argn),1));

PHP, 54 Bytes

for(;$i++<$argn;)$s+=!preg_match('#(.)\1#',$i);echo$s;
share|improve this answer

CJam, 17 bytes

ri{)se`0f=:*1=},,

Try it online!

Explanation

ri                 e# Read an integer from input
  {                e# Filter on the range from 0 to n-1, keeping only numbers that give a 
                   e#   truthy result in this block:
   )               e#  Increment the number
    se`            e#  Take the run-length encoding of its digits
       0f=         e#  Take the first element of each encoding pair (the run length)
          :*       e#  Take the product of all run lengths
            1=     e#  Check if it's equal to 1 (i.e. all run lengths were 1)
              },   e# (end of filter block)
                ,  e# Take the length of the resulting array
share|improve this answer

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.