Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Input

A integer n ( ≥ 1) and a digit d (an integer such that 0 ≤ d ≤ 9).

In either order; from stdin or parameters or whatever; to a program or function; etc.

Output

The integers from 1 to n inclusive (in order) whose decimal representations contain an even number of ds. (That is, the integers in the list are the integers that have, respectively, an even number of ds.)

In any standard format, etc. In particular, the output need not be represented in decimal.

If output as a single string, the integers must be separated somehow (spaces, commas, newlines, null bytes, whatever).

Examples

in(d,n) ↦ out
1,12    ↦ 2 3 4 5 6 7 8 9 11
0,111   ↦ 1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,21,22,23,24,25,26,27,28,29,31,32,33,34,35,36,37,38,39,41,42,43,44,45,46,47,48,49,51,52,53,54,55,56,57,58,59,61,62,63,64,65,66,67,68,69,71,72,73,74,75,76,77,78,79,81,82,83,84,85,86,87,88,89,91,92,93,94,95,96,97,98,99,100,111

Thanks

To quintopia for the title.

share|improve this question

32 Answers 32

up vote 3 down vote accepted

Jelly, 7 bytes

RDċ€Ḃ¬T

Try it online!

How it works

RDċ€Ḃ¬T  Main link. Arguments: n, d

R        Range; yield [1, ..., n].
 D       Convert each integer in the range to base 10.
  ċ€     Count the occurrences of d in each array of decimal digits.
    Ḃ    Compute the parities.
     ¬   Negate, so even amounts evaluate to 1, odds to 0.
      T  Find all indices of truthy elements.
share|improve this answer

05AB1E, 11 10 bytes

Code:

\>GN¹¢ÈiN,

Explanation:

\           # Pop input, which saves the first input into ¹
 >          # Increment on second input
  G         # For N in range(1, input + 1)
   N        # Push N
    ¹       # Push the first input from the input register
     ¢      # Count the number of occurences of the digit in N
      È     # Is even?
       iN,  # If true, print N with a newline

Try it online

Uses CP-1252 encoding.

share|improve this answer
    
¢ interprets both arguments as strings? – Sparr Mar 9 at 17:19
    
@Sparr That depends, it can also be done on lists containing strings. But here, it interprets both arguments as strings. – Adnan Mar 9 at 20:56

Haskell, 69 63 52 50 bytes

d#n=[i|i<-[1..n],even$sum[1|x<-show i,read[x]==d]]

Straightforwared solution for my first ever post here. It uses show to count the number of d's. I explicitly did not use Char as input for d, which would have saved 12 6 (after Damien's edit) bytes.

EDIT: 11 bytes less thanks to Damien! EDIT 2: another 2 bytes less thanks to nimi!

share|improve this answer
2  
you could replace filter by a comprehension list: f d n=[i|i<-[1..n],even$sum[1|x<-show i,read[x]==d]] – Damien Mar 8 at 13:41

Befunge, 1080 945 bytes

vd>"000">" "v
&0      ^              p21-1+*68<
62            >        v
8           >-|        >12g68*-:|
*             >11g1+11p^        $
+                      v  <
5                         |%2g11<
5                      v.:<          
+         v            <        
0         >268*+12p68*11p"000"40p50p60pv
p
           v                             -1<
             v-g01p06+1g06<
>&         >:>:10g1-`     |            >:0`|
             v            <                @
             v-+55p05+1g05<      
             >:54+`       |
   v               p04+g04<
  ^          <                <      <
   >60g68*-0`|      >50g68*-0`|
             >" "60p^         >" "50p^

The score is given that we count the entire square, including newlines, which makes sense. You can copy paste the code into the interpeter. Provide two inputs, first d and then n. This solution does not work for values larger than n > 999.

This will obviously not be a contender for the grand prize, but I've been wanting to implement a codegolf in Befunge for a while now, so I decided to just do it. I figure this will not be even close to an optimal Befunge solution, as it is the first actual thing I've done in Befunge. So, hints are welcome, if you need clarification or more information, please let me know in the comments.

Attempt at explanation:

In the first column downward we read an integer from the input, add 48 (6*8, you'll see this more often) to it to convert it to the corresponding ASCII value and puts it to (10, 0).

& - read input

68*+ - add 48

55+0p - put the value at (10, 0)

Note that the d at (1, 0) is just an easy way to get the number 100 on the stack.

After that, we go east and read another integer and head in to what I call the ASCIIfier. This turns the current number into a series of ASCII characters. The ASCIIfier is the rectangular piece from (13, 12) to (26, 17). It consists of two loops, first counting the hunderds and than the tens and putting them into the three digits at (6, 0) and (5, 0). After that the last digit is put into (4, 0). So the numbers is actually in reverse.

v-g01p06+1g06< - increment the "hunderds counter" located at (0, 6) and decrease current value by 100
>:10g1-`     | - ASCIIfier entry; check if the current value is > 99, if so, go up, else go down
v            < - go to start of "tens counter"
v-+55p05+1g05< - increment the "tens counter" located at (0, 5) and decrease current value by 10
>:54+`       | - check if current value is > 9, if so, go up, else go down
      p04+g04< - put the final value into the "singles counter" located at (0, 4)

After putting the current integer into a series of ASCII characters, we go a bit more south to remove prepended zeroes. Thus, afterwards, what are initially the three zeroes at the top, will be the current number, without prepended zeroes.

Then we go back up, all the way to the North, where we put the three digits on the stack. We iterate over the three digits in the top loop, each time incrementing the counter located at (1, 1) if the current digit corresponds with the input d

When that is done we go and check to see if the counter that located at (1, 1) is odd or even. If it is even, we output the current number and move on to the big outer loop to decrement the current value and start over again.

share|improve this answer
    
Please do post an explanation if you have time! – A Simmons Mar 8 at 14:15
    
I've added an attempt at a description.. Found out it wasn't so easy to clarify... Don't hesitate to ask further... – Lex Mar 8 at 15:03
    
By the way, I just found out I have to output the result in ascending order, which makes this even more unfitting to the requirements.... – Lex Mar 8 at 15:10
    
Always +1 for a working Befunge answer! BTW, is this really 945 bytes? This says 679 – Luis Mendo Mar 9 at 17:12
    
Hehe, thanks. I counted 945 because I took the entire square of 21 lines x 45 columns (including newlines) – Lex Mar 10 at 8:06

Python 2, 50 bytes

f=lambda d,n:n*[0]and f(d,n-1)+~`n`.count(d)%2*[n]

A recursive function that takes the digit d as a string and the upper bound n as a number.

The count of digits d's in n is tested to be even by taking it's bit complement modulo 2, which gives 1 for even and 0 for odd. This many n's are appending to the list, and the function recurse down to n-1, stopping via logical short-circuit on the empty list when n==0.

If the output may be given in decreasing order, one byte can be saved, for 49 bytes:

f=lambda d,n:n*[0]and~`n`.count(d)%2*[n]+f(d,n-1)

Old 51-byte solution:

lambda d,n:[x+1for x in range(n)if~`~x`.count(d)&1]

An anonymous function that takes the digit d as a string and the upper bound n as a number.

Two tricks are used:

  • Python's range is zero-indexed 0...n-1, so we add one to each potential value x. Then, to count d's in x+1, it saves a character to use its negation ~x instead.
  • To filter for even values, we do ~_%2, which first bit-flips to switch parity, then takes the last bit with &1 (same as %2 here), producing a truthy value only if the original was even.
share|improve this answer

Pyth, 10 bytes

f!%/`Tz2SE

Try it online. Test suite.

share|improve this answer

Lua, 86 Bytes

If using inconsistent separator is allowed, I could replace io.write by print, meaning numbers would be separated by one or multiple newlines.

This is a full program, which have to be called like this: lua file.lua d n.

It removes all non-d character from the current number and uses the size of the resulting string to decide weither or not it should be outputed.

for i=1,0+arg[2]do io.write(#(i..''):gsub("[^"..arg[1].."]","")%2<1 and i.." "or"")end
share|improve this answer

JavaScript (ES6) 64

An anonymous function with output to console. Straightforward implementation using split to count the digits.

(d,n)=>{for(i=0;i++<n;)(i+'').split(d).length&1&&console.log(i)}

Output using alert would be 6 byte less, but I really don't like it (and I'm not going to beat the toy languages anyway)

share|improve this answer

MATL, 12 10 bytes

:!V!=s2\~f

First input is n, second is d as a string. For example:

12
'1'

Try it online!

:       % implicitly take input n (number). Generate row vector [1,2,...,n]
!       % transpose into column vector
V       % convert each number to string. Gives 2D char array padded with spaces
!       % transpose
=       % implicitly take input d (string). Compare with each element of the array
s       % sum of each column: number of coincidences with d
2\~     % true for even values
f       % find indices of true values. Implicitly display
share|improve this answer

Ruby, 47 42 bytes

?1.upto $*[1]{|s|s.count($*[0])%2<1&&p(s)}

Run with d and n as command-line parameters, e.g.

ruby golf.rb 1 12
share|improve this answer
2  
Great first answer! Welcome to PPCG! :D – mbomb007 Mar 8 at 19:46
    
Well done! In Ruby 1.9+, you can use ?1 for "1". And it's less pretty, but a byte shorter, to do %2>0 instead of .odd? – histocrat Mar 9 at 17:05
    
Thanks! That saves a few bytes :) – mrhmouse Mar 9 at 23:05

PowerShell, 62 55

param($1,$2);1..$2|?{!(([char[]]"$_"-match$1).Count%2)}

edit: using a param block in this case is shorter. removed some redundant space


Not a golfing language but its the only one I really know. This would work saved as a script and called like this M:\Scripts\cgNeverTellMeTheOdds.ps1 1 12. First argument is the digit d and the second is integer n.

Create an array of number 1 to n. For each of those convert that into a character array. 10 would be 1,0. Using -match as an array operator return all the elements that match the digit d. Count the amount of elements returned and mod 2 the result. Result will be 0 for even and 1 for odd. 0 as a boolean is false so we use ! for the loop to evaluate the odd results to false and even results to true.

Output is a newline delimited on console.

share|improve this answer
    
Welcome to PPCG, nice first answer! :) – FryAmTheEggman Mar 10 at 15:55
    
@FryAmTheEggman Sweet. Thanks for the nod. I though this would be buried under all the other answers. – Matt Mar 10 at 16:05

Retina, 99 105 bytes

Note the trailing spaces. <empty> represents an empty line.

\d+$
$*
+`^(. )(1*)1\b
$1$2 1$2
1+
$.0
+`^(.)(.*) ((?!\1)\d)*\1((?!\1)\d|(\1)((?!\1)\d)*\1)*\b
$1$2
^.  
<empty>

Takes input like 1 12. Output is space separated in decreasing order.

I modified 0*1(0|10*1)* to match an odd number of \1 in a number. I changed 0 to (?!\1)\d, and 1 to \1 to create the long regex line you see above. Understanding how the linked regex works is crucial.

Try it online

Commented explanation of old version

If descending order were okay

\d+$            Convert last number N to unary
$*
+`1(1*)$        Create list N N-1 ... 1 in unary
$0 $1
 (1)+           Convert back to decimal
 $#1
+`^(.)(.*) ((?!\1)\d)*\1((?!\1)\d|(\1)((?!\1)\d)*\1)*   Remove numbers w/ odd num of D's
$1$2 
^.              Remove first parameter
<empty>
share|improve this answer
1  
You can use 1+ and $.0 to do the conversion from unary back to decimal. – FryAmTheEggman Mar 8 at 18:13

Bash + GNU utilities, 37

  • 1 byte saved thanks to @Ruud.
seq $1|egrep "^[^$2]*($2[^$2]*){2}*$"
share|improve this answer
    
The * following the opening parenthesis appears to be redundant. Removing it saves you 1 byte. – Ruud Mar 9 at 20:56
    
@Ruud yes - thanks - fixed now. – Digital Trauma Mar 9 at 21:05

Python 3.4, 92 85 79 85 bytes

Saved 7 bytes thanks to Mego
Saved another 6 bytes thanks to mbomb007
Regained those 6 bytes because Python 3.x

This is my first shot at code golf, so here goes nothing!

lambda n,d:[i for i in range(n+1)if len([j for j in list(str(i))if j==str(d)])%2is 0]
share|improve this answer
1  
There are a few spaces you can remove in this. Also, if you make it an unnamed lambda, it will be considerably shorter. – Mego Mar 8 at 18:56
    
You can use `d` instead of str(d), and if you assume n is an integer (< 2**32), you can use `i` instead of str(i). – mbomb007 Mar 16 at 16:38
    
Are the backticks shorthand for str()? – Nakaan Mar 16 at 16:41
1  
The backticks were a shorthand for__repr__ in python 2, they were removed in python 3. You should probably change your header to reflect that restriction. – FryAmTheEggman Mar 17 at 17:07
    
Yeah, I just found that while digging around and throwing a test case in the interpreter. Sadface. – Nakaan Mar 17 at 17:09

Perl 6, 38 bytes

{(1..$^n).grep(*.comb.Bag{~$^d} %% 2)}
share|improve this answer

Brachylog, 32 bytes

:1reIlL,"":Ic:.xl-L=%2=0,Iw,@Sw\

Expects N as input and the digit as output, e.g. brachylog_main(12,1).

Explanation

:1reI                            § I is a number between 1 and Input
     lL,                         § L is the length of I
        "":Ic                    § Convert I to a string
             :.x                 § Remove all occurences of Output in that string
                l-L=%2=0,        § Check that the length of that new string - L mod 2 is 0
                         Iw,@Sw  § Write I, then write a space
                               \ § Backtrack (i.e. try a new value of I)
share|improve this answer

Mathematica, 54 bytes

Position[Count[#2]/@IntegerDigits/@Range@#,x_/;2∣x]&
share|improve this answer

Perl, 28 29 31 bytes

Includes +2 for -an

Run with the specification digit and count on consecutive lines on STDIN:

echo -e "0\n111" | perl -anE'map s/@F/$&/g%2||say,1..<>'
share|improve this answer

Oracle SQL 11.2, 111 82 bytes

SELECT LEVEL FROM DUAL WHERE MOD(REGEXP_COUNT(LEVEL,:d),2)=0 CONNECT BY LEVEL<=:n;
share|improve this answer

Kotlin, 136 bytes

fun main(a:Array<String>)=print({n:String,d:String->IntRange(1,n.toInt()).filter{"$it".count{"$it"==d}%2==0}.joinToString()}(a[0],a[1]))

Fully functional program, takes arguments as: n d

Try it online!

share|improve this answer

Java 8, 84 bytes

This is a lambda expression for a BiConsumer< Integer, Integer>:

(d,n)->for(int x=0;x++<n;)if((""+x).split(""+d,-1).length%2>0)System.out.println(x);

Explanation:

for each number between 1 and n, convert the number to a string and split it using d as the delimiter. If it was split into an odd number of sections, then print out the number followed by a new line.

share|improve this answer

Retina, 72 71 55

\d+$
$*
\B
¶$`
1+
$.0
G`(.),((?>.*?\1){2})*(?!.*\1)
.,
<empty>

Great thanks to Martin, who totally by accident reminded me of atomic matching groups!

Try it online!

Explanation:

\d+$
$*

Replace the number, but not the digit, with its unary equivalent.

\B
¶$`

\B matches each position (zero-width) that is not a word boundary. Note that this will not match any of the following: the beginning of the string, the end of the string, or any position around the comma character. Each of these non-boundaries is then replaced with a newline and then the string that comes before the match ($`). This gives a list like:

d,1
d,11
d,111

Where d is any single decimal digit.

1+
$.0

This converts all lists of 1s into the decimal representation of their lengths. This conveniently won't affect the 1 that could be before the comma, as it's length it always 1 as well.

G`(.),((?>.*?\1){2})*(?!.*\1)

Here, the G turns on grep mode, which means that lines that match the regex are kept, and other lines are discarded. This regex is complicated, but it essentially matches groups of 2 of the leading digit (stored in capture group 1, so we can reference it with \1).

The key here, is that if it failed when using the non-greedy match up to the two earliest appearances of the digits, it would then just roll back and try again, with . matching over the digit. This would make numbers like 111 match when our digit is 1. Therefore, we use ?> to make the match atomic, essentially preventing the regex from backtracking to before it matched this value. An atomic match works kind of like possesive matching would in certain flavours. Since the * meta-character is followed by a ? the . will match characters up until it is able to match what we stored in \1. Then once we do this twice, the regular expression's "memory" is destroyed, preventing the behaviour that would normally occur, where it goes back and has the . match an additional character, our \1 digit, which would created invalid matches.

Then, we check that from the final position, after matching repeated groups of two of the input digit, that we cannot match another input digit.

.,
<empty>

Here we are just removing the digit and comma from each of the strings, so we just get our nice answer.

share|improve this answer
    
Please add an explanation. – mbomb007 Mar 8 at 19:45
    
@mbomb007 Ok, added :) – FryAmTheEggman Mar 8 at 22:11
    
Atomic matching is something I don't yet understand. – mbomb007 Mar 8 at 22:42
    
@mbomb007 I've attempted to clarify what is going on, let me know if something stands out as being unclear. – FryAmTheEggman Mar 8 at 23:16

Python 2, 57 54 bytes

lambda d,n:[i for i in range(1,n+1)if`i`.count(d)%2<1]

Usage

>>> (lambda d,n:[i for i in range(1,n+1)if`i`.count(d)%2<1])('1', 12)
[2, 3, 4, 5, 6, 7, 8, 9, 11]
share|improve this answer

Julia, 44 bytes

f(n,d)=filter(i->sum(d.==digits(i))%2<1,1:n)

This is a function that accepts two integers and returns an array.

We start with the set of integers from 1 to n, inclusive. For each integer i, we determine which of its decimal digits are equal to d, which yields a Boolean array. We sum this to get the number of occurrences of d as a digit in i, and filter the original range based on the parity of the sum.

Try it here

share|improve this answer

Seriously, 17 bytes

╩╜R;`$╛@c2@%Y`M@░

Takes inputs as n\n'd' (integer, newline, string).

Try it online!

Explanation:

╩╜R;`$╛@c2@%Y`M@░
╩                  push all inputs to registers
 ╜R;               push two copies of range(1, n+1)
    `        `M    map:
     $╛@c            count the number of d's
         2@%Y        modulo 2, logical not (1 if even, 0 if odd)
               @░  filter: take only the values of range(1, n+1) where the count is even
share|improve this answer

Mathematica, 45 bytes

Select[a=#2;Range@#,2∣DigitCount[#,10,a]&]&

Uses the built-in DigitCount.

share|improve this answer

Japt, 13 12 bytes

Uò1 f_s èV v

Input is n, then d wrapped in quotes. Test it online!

How it works

       // Implicit: U = input integer, V = input string
Uò1    // Create the inclusive range [1..U].
f_     // Filter to only the items Z that return truthily to this function:
s èV   //  Take Z.toString(), then count the number of matches of V.
v      //  Return 1 (truthy) if even, 0 (falsy) otherwise.
       // Implicit output, array separated by commas
share|improve this answer

CJam, 38 bytes

r:P;r~1+,0-_{s{s}%Pe=2%!}%]z{~{}{;}?}%

Explanation

r:P;                                    e# set input d to variable P
    r~1+,0-                             e# create a range(1, n+1)
           _{s{s}%Pe=2%!}%              e# determine which numbers are needed
                          ]z{~{}{;}?}%  e# remove extra numbers
share|improve this answer

Scala, 66 bytes

(d:Int,n:Int)=>(1 to n).map(""+).filter(_.count((""+d)(0)==)%2==0)
share|improve this answer

R, 145 bytes (I am sure there are ways to shorten this further) :)

g<-sapply(sprintf("%s",seq(1:111)),function(z){if(sapply(regmatches(z,gregexpr("0",z)),length)%%2==0){z}else{NULL}})
names(g[!sapply(g,is.null)])
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.