Never tell me the odds

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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!

Answer 4

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.

Answer 5

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.

Answer 6

Pyth, 10 bytes

f!%/`Tz2SE

Try it online. Test suite.

Answer 7

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

Answer 8

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)

Answer 9

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

Answer 10

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

Answer 11

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.

Answer 12

Bash + GNU utilities, 37

• 1 byte saved thanks to @Ruud.

seq $1|egrep "^[^$2]*($2[^$2]*){2}*$"

Answer 13

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>

Answer 14

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]

Answer 15

Perl 6, 38 bytes

{(1..$^n).grep(*.comb.Bag{~$^d} %% 2)}

Answer 16

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)

Answer 17

Mathematica, 54 bytes

Position[Count[#2]/@IntegerDigits/@Range@#,x_/;2∣x]&

Answer 18

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

Answer 19

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.

Answer 20

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.

Answer 21

Oracle SQL 11.2, 111 82 bytes

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

Answer 22

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!

Answer 23

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]

Answer 24

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

Answer 25

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

Answer 26

Mathematica, 45 bytes

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

Uses the built-in DigitCount.

Answer 27

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

Answer 28

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

Answer 29

Scala, 66 bytes

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

Answer 30

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

Answer 31

C, 175 Bytes

_;main(f,n,d){f?f-1?main(0,n,d),printf(_?"%d ":"",n),(n-1?main(2,n-1,d):0):(scanf("%d %d",&n,&d),main(2,n,d)):(n>9?n%10==d?(main(0,n/10,d),_=!_):main(0,n/10,d):(_=!(n==d)));}

Takes n, then d, from standard input. Prints the correct numbers in reverse order.

Expansion

_; // declare return variable
main(f,n,d) //entry point (function selection [1==real main],n,d)
{
    f?
        f-1?
            //recursive loop from 'n' to 1
            main(0,n,d), //call even_digits?
            printf(_?"%d ":"",n),
            (n-1?main(2,n-1,d):0)
        :
            //actual main, just scan and run the loop
            (scanf("%d %d",&n,&d),main(2,n,d))
    :
        //even_digits? (stores result in _)
        (n>9? // recursive case, many digits
            n%10==d?
                (main(0,n/10,d),_=!_)
            :
                main(0,n/10,d)
         :
            (_=!(n==d)) //base case: 1 digit, return !(n==d)
        );
}

I feel like it might be possible to remove the duplicated main(0,n/10,d) near the end.

Answer 32

Python 2, 68 chars

f=lambda d,n:filter(lambda x:x.count(`d`)%2^1,map(str,range(1,n+1)))

This function takes two ints and returns a list of the numbers with an even number of ds.