Basado en la pregunta ¿Cuántos enteros positivos <1,000,000 contienen el dígito 2? . Estoy buscando la solución más creativa para contar todos los números enteros desde Xque Ycontienen el número entero Z. Zpuede ser de 0 a Y.

Cada entero encontrado solo cuenta una vez, incluso si el entero Zaparece con más frecuencia. Por ejemplo:

Z = 2
123 counts 1
22222 also counts 1

Comenzaré con un algoritmo realmente simple escrito en Java (porque es amado por todos):

public class Count {
    public static void main(String[] args) {
        int count = 0;
        for (int i = Integer.parseInt(args[0]); i <= Integer.parseInt(args[1]); i++) {
            if (Integer.toString(i).contains(args[2])) {
                count++;
            }
        }
        System.out.println(count);
    }
}

si ejecutas esto con

java -jar Count.jar 0 1000000 2

obtienes esto como resultado:

468559

Debido a que este problema no es difícil de resolver, es solo un concurso de popularidad . ¡La respuesta más votada publicada el 28 de febrero gana!

golpe (20)

seq $1 $2|grep -c $3

Uso

$ bash count.sh 0 1000000 2
468559

Funciton

Como de costumbre, dado que la altura de línea agregada por StackExchange divide las líneas, considere ejecutar $('pre').css('line-height',1)en la consola de su navegador para solucionarlo.

A diferencia de mis otras respuestas de Funciton, esta no usa ninguna declaración de función. Es solo un programa. Sin embargo, utiliza una expresión lambda, una característica que agregué a Funciton en diciembre :)

Espera la entrada como tres enteros decimales (pueden ser negativos) separados por espacios (es decir x y z). De hecho, zpuede ser cualquier cadena; por ejemplo, podría ser solo el signo menos ( −, U + 2212) para contar el número de números negativos en el intervalo :)

           ┌───╖
     ┌───┬─┤ ♯ ╟──────────┐
     │   │ ╘═══╝ ╔════╗ ┌─┴─╖             ┌────╖ ╔═══╗
   ┌─┴─╖ └────┐  ║ 21 ║ │ × ╟─────────────┤ >> ╟─╢   ║
 ┌─┤ ʃ ╟───┐  │  ╚══╤═╝ ╘═╤═╝             ╘═╤══╝ ╚═══╝
 │ ╘═╤═╝   │  └──┐  └─────┘   ┌───────────┐ │
 │ ╔═╧═╗ ┌─┴─╖ ┌─┴─╖ ╔════╗ ┌─┴─╖   ┌───╖ ├─┴────────┐
 │ ║   ╟─┤ · ╟─┤ ʘ ╟─╢ 32 ╟─┤ · ╟───┤ ʘ ╟─┘          │
 │ ╚═══╝ ╘═╤═╝ ╘═══╝ ╚════╝ ╘═╤═╝   ╘═╤═╝ ┌─────┐    │
 │         └───────┐  ╔═══╗ ┌─┴─╖     │ ┌─┴─╖   │    │
 │ ┌───────────┐   └──╢ 0 ╟─┤ ʃ ╟─┐   │ │ ♯ ║   │    │
 │ │   ┌───╖ ┌─┴─╖    ╚═══╝ ╘═╤═╝ │   │ ╘═╤═╝ ┌─┴─╖  │
 │ │ ┌─┤ ♯ ╟─┤   ╟─┬─┐ ╔════╗ │ ┌─┴─╖ │   │ ┌─┤ × ║  │
 │ │ │ ╘═══╝ └─┬─╜ └─┘ ║ −1 ║ └─┤ · ╟─┴───┘ │ ╘═╤═╝  │
 │ │ │    ┌────┴────┐  ╚══╤═╝   ╘═╤═╝       │ ╔═╧══╗ │
 │ │ │    │ ┌───╖ ┌─┴─╖ ┌─┴─╖ ┌───┴─────╖   │ ║ 21 ║ │
 │ │ │    └─┤ ♯ ╟─┤ ? ╟─┤ = ║ │ str→int ║   │ ╚════╝ │
 │ │ │      ╘═══╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═══════╝   │ ┌────╖ │
 │ │ │      ╔═══╗ ┌─┴─╖   └─┐ ┌─┴─╖         └─┤ >> ╟─┘
 │ │ │      ║ 0 ╟─┤ ? ╟─┐   └─┤ · ╟───┐       ╘═╤══╝
 │ │ │      ╚═══╝ ╘═╤═╝ └─┐   ╘═╤═╝   └───┐   ┌─┴─╖
 │ │ │            ┌─┴─╖   └─┐ ┌─┴─╖       └───┤ ʘ ║
 │ │ └────────────┤ · ╟─┐   └─┤ ≤ ║           ╘═╤═╝
 │ │              ╘═╤═╝ │     ╘═╤═╝ ┌─────────╖ │
 │ │        ╔═══╗ ╔═╧═╕ │       └─┬─┤ int→str ╟─┘
 │ │        ║ 0 ╟─╢   ├─┤         │ ╘═════════╝
 │ │        ╚═══╝ ╚═╤═╛ └─────────┘
 │ └────────────────┴─┐              │
 │    ┌─────────╖   ┌─┴─╖ ┌─┐   ┌────┴────╖
 └────┤ str→int ╟───┤   ╟─┴─┘   │ int→str ║
      ╘═════════╝   └─┬─╜       ╘════╤════╝
                      └──────────────┘

C#

public class Program
{
    public static void Main(string[] args)
    {
        Console.WriteLine(Enumerable.Range(Convert.ToInt32(args[0]), (Convert.ToInt32(args[1]) + 1) - Convert.ToInt32(args[0])).Count(x => x.ToString().Contains(args[2])));
    }
}

Ejemplo

count.exe 0 1000000 2
468559

APL (29)

{+/∨/¨(⍕⍺)∘⍷¨⍕¨⊃{⍺+0,⍳⍵-⍺}/⍵}

Esta es una función que toma Zcomo argumento izquierdo y el intervalo [X,Y]como argumento derecho:

      2 {+/∨/¨(⍕⍺)∘⍷¨⍕¨⊃{⍺+0,⍳⍵-⍺}/⍵} 0 1e6
468559
      0 {+/∨/¨(⍕⍺)∘⍷¨⍕¨⊃{⍺+0,⍳⍵-⍺}/⍵} 0 1e6
402131
      42 {+/∨/¨(⍕⍺)∘⍷¨⍕¨⊃{⍺+0,⍳⍵-⍺}/⍵} 0 1e6
49401

Python 2.7

Necesidad de la velocidad

Explicación

Implementación

def Count(lo,hi,key):
    if hi == 0: return 0
    # Count(lo,hi,key) = Count(0,hi,key) - Count(0,lo - 1,key)
    if lo != 0: return Count(0, hi, key) - Count(0, lo - 1, key)
    # Calculate no of digits in the number to search
    # LOG10(hi) may be a descent trick but because of float approximation
    # this would not be reliable
    n = len(str(hi)) - 1
    # find the most significant digit
    a_n = hi/10**n
    if a_n < key:
        count = a_n*(10**n - 9**n)
    elif a_n > key:
        count = (a_n - 1)*(10**n - 9**n) + 10**n
    else:
        count = a_n*(10**n - 9**n) + 1
    if hi % 10**n != 0:
        if a_n != key:
            return count + Count(0, hi%10**n, key)
        else:
            return count + hi%10**n
    else:
        return count

Manifestación

In [2]: %timeit Count(0,123456789987654321,2)
100000 loops, best of 3: 13.2 us per loop

Comparación

@Dennis

$ \time -f%e bash count.sh 0 1234567 2
585029
11.45

@arshajii

In [6]: %timeit count(0,1234567,2)
1 loops, best of 3: 550 ms per loop

Python 2.7

Una solución usando expresiones regulares:

>>> from re import findall as f
>>> count=lambda x,y,z:len(f('\d*%d\d*'%z,str(range(x,y+1))))
>>>
>>> count(0,1000000,2)
468559

bash 32 31 17 14 caracteres + longitud de X, Y y Z

Gracias a devnull por sugerir seq!

seq [X] [Y]|grep -c [Z]

Por ejemplo, X = 100, Y = 200, Z = 20

$ seq 100 200|grep -c 20
2

Por ejemplo, X = 100, Y = 200, Z = 10

$ seq 100 200|grep -c 10
11

Por ejemplo, X = 0, Y = 1000000, Z = 2

$ seq 0 1000000|grep -c 2
468559

PHP

Nada original, solo celebrando mi primer post aquí.

<?php

    $x = $argv[1];
    $y = $argv[2];
    $z = $argv[3];
    $count = 0;

    do
    {
        if (!(strpos($x, $z) === false))
            $count++;
        $x++;
    } while ($x <= $y);

    echo $count;

?>

Entrada

php script.php 0 1000000 2

Salida

468559

Scala:

args(0).toInt to args(1).toInt count (_.toString contains args(2))

Rubí

Este es un gran ejemplo para usar reduce!

puts (ARGV[0]..ARGV[1]).reduce(0) { |c, n| n.to_s.include?(ARGV[2].to_s) ? c + 1 : c }

Entrada:

ruby script.rb 0 1000000 2

Salida:

468559

Python golf - 61

f=lambda x,y,z:len([i for i in range(x,y)if str(z)in str(i)])

Python no golf

def f(x, y, z):
    c = 0
    for i in range(x, y):
        c += str(z) in str(i)
    return c

Java8

Usando el nuevo material IntStream, esto se convierte esencialmente en una línea, si ignora el material obligatorio de Java Framework:

import java.util.stream.IntStream;
public class A{
  public static void main(String[] args){
    System.out.println(IntStream.rangeClosed(Integer.parseInt(args[0], Integer.parseInt(args[1])).filter(x -> ((Integer)x).toString().contains(args[2])).count());
  }
}

Se puede ejecutar aquí , aunque tuve que codificar los valores.

F#

Esta solución utiliza IndexOfpara buscar la cadena, luego un poco de violín numérico para convertir el resultado a 1 si se encuentra, y 0 si no se encuentra, luego suma el resultado:

let count x y (z : string) = 
    [ x .. y ] |> Seq.sumBy(fun n -> min 1 (n.ToString().IndexOf z + 1))

Y se puede llamar así:

count 0 1000000 "2" // 468559

Expresión regular

A continuación se contarán los dígitos de 1 hasta 49.

#!/bin/bash

echo "12313451231241241111111111111111111111111111111111111"  |\  
sed "s/[^1]//g;s/11111/5/g;s/1111/4/g;s/111/3/g;s/11/2/g;s/555555555/45/g;s/55555555/40/g;s/5555555/35/g;s/555555/30/g;s/55555/25/g;s/5555/20/g;s/555/15/g;s/55/10/g;s/54/9/g;s/53/8/g;s/52/7/g;s/51/6/g;s/50/5
/g;s/40/4/g;s/30/3/g;s/20/2/g;s/10/1/g"

R 23 25 27caracteres

Simplemente obtenga la herramienta adecuada para el trabajo. Uso simple de grep en R, nada lujoso.

Esto es lo que hace: greptodas las instancias 2en el vector 0hasta 10e6y cuentan el número de resultados usando length.

length(grep(2,0:100000,value=TRUE))

length(grep(2,0:10e6))

Resultado: [1] 468559

Por supuesto, puede escribir una función que tome los números como entrada, tal como se muestra en el ejemplo.

count = function(x=0, y=1000000, z=2){
  length(grep(z,x:y))
}

Ahora puede llamar countcon x, y y z, si no está configurado (es decir, por defecto), los valores para x, y y z son 0, 1000000 y 2 respectivamente. Algunos ejemplos:

count()
[1] 468559

o

count(20, 222, 2)
[1] 59

o

count(0, 100, 10)
[1] 2

Algunos piensan que el tiempo es importante, usar esta función en R toma alrededor de 1 segundo.

system.time(count())
user  system elapsed 
0.979   0.003   0.981

JavaScript (ES6), 63

f=(i,j,n)=>{for(c=0;i<=j;!~(''+i++).indexOf(n)?0:c++);return c}

Uso:

f(0, 1e6, 2)
> 468559

Sin golf:

f = (i,j,n) => {
  for(
    // Initialize the counter.
    c=0;
    // Iterate through all integers.
    i<=j;
    // Convert current number into string then increment it.
    // Check if the digit appears into the current number.
    !~(''+i++).indexOf(n)
      // Occurence not found.
      ? 0
      // Occurence found.
      // Add 1 to the counter.
      : c++
  );
  return c
}

Rubí

Básicamente, tomé la respuesta de Pablo y la jugué semi-golf (38 caracteres si elimina espacios en blanco innecesarios) en un ejemplo no tan bueno de uso select.

Selecciona cada índice en el rango (x .. y) que contiene z. Lamentablemente, este resultado intermedio se almacena en una matriz, cuyo tamaño se devuelve.

x,y,z = $*
p (x..y).select{ |i| i[z] }.size

Se ve muy bien tanto sintácticamente como semánticamente, aunque la i[z]parte realmente no parece tener sentido.

¡Funciona porque xy en yrealidad son cadenas, no números! Por lo tanto, cada uno itambién es una cadena y, i[z]por supuesto, comprueba si la cadena zestá contenida i.

$ ruby count-digits.rb 100 200 20
2
$ ruby count-digits.rb 0 1000000 2
468559

Python 2.7, 70 signos

f = lambda x,y,z: sum(map(lambda x: str(z) in str(x), range(0, y+1)))

>>> f(0, 1000000, 2)
468559

Más corto, 65 signos

g = lambda x, y, z: sum(str(z) in str(i) for i in range(0, y+1))
>>> g(0, 1000000, 2)
468559

Usando Ruby Enumerable#grep:

start, stop, target = $*
p (start..stop).grep(Regexp.new target).size

T-SQL

Si yo puedo asumir las variables @X, @Yy@Z se encuentran disponibles:

Con una tabla de números existentes (arbitrariamente grande;) - 65

select count(*)from n where n>=@X and n<=@Y and n like '%'+@Z+'%'

Con un CTE recursivo - 127

with n(n)as(select @X union all select n+1 from n where n<@Y)select count(*)from n where n like'%'+@Z+'%'option(MAXRECURSION 0)

Si las variables deben definirse explícitamente:

Agregue 58 a ambas respuestas - Tabla de números: 123, CTE recursivo: 185

declare @X int=0;declare @Y int=100;declare @Z varchar(30)='2';

No tengo idea de cuánta memoria puede usar el CTE recursivo, pero ciertamente no va a ganar ningún concurso de velocidad. El ejemplo de buscar 2 en 0 a 1000000 toma 8 segundos en mi sistema.

Aquí hay un SQL Fiddle si alguien quiere jugar con él. La consulta 1000000 tarda más de 30 segundos en ejecutarse.

Rebol

; version 1 (simple loop counting)

count: func [x [integer!] y [integer!] z [integer!] /local total] [
    total: 0
    for n x y 1 [if found? find to-string n z [++ total]]
    total
]


; version 2 (build series/list and get length)

count: func [x [integer!] y [integer!] z [integer!]] [
    length? collect [for n x y 1 [if find to-string n z [keep true]]]
]

Ejemplo de uso en la consola Rebol (REPL):

>> count 0 1000000 2
== 468559

Potencia Shell

Dos soluciones, ambas 40 37 caracteres.

Para todas las versiones de PowerShell:

$a,$b,$c=$args;($a..$b-match$c).count

PowerShell V3 y superior tienen el slsalias para Select-String. Esto requiere @forzar una matriz si solo un valor pasa a través de la tubería.

$a,$b,$c=$args;@($a..$b|sls $c).count

Lote

@setLocal enableDelayedExpansion&@set a=0&@for /L %%a in (%1,1,%2) do @set b=%%a&@if "!b:%3=!" NEQ "!b!" @set/aa+=1
@echo !a!

H:\uprof>count 0 1000000 2
468559

H:\uprof>count 1 2 3
0

Un poco más legible

@setLocal enableDelayedExpansion
@set a=0
@for /L %%a in (%1,1,%2) do (
    @set b=%%a
    @if "!b:%3=!" NEQ "!b!" @set/aa+=1
)
@echo !a!

Agradable y simple Utiliza la manipulación de cadenas para verificar si la variable !b!es la misma sin la entrada del tercer usuario, %3( !b:%3=!).

Mathematica

Primera forma: cuerdas

x, y, zse convierten en cadenas. Si un entero de cadena no está libre z, se cuenta.

f[{x_,y_},z_] :=Length[Select[ToString/@Range[Max[x, z], y], !StringFreeQ[#, ToString@z] &]]

Ejemplos

f[{22, 1000}, 23]
f[{0, 10^6}, 2]

20
468559

Segunda forma: listas de dígitos

g[{x_,y_},z_]:=(t=Sequence@@ IntegerDigits@z;Length@Cases[IntegerDigits@Range[190], 
{s___,t,e___}])

Ejemplos

g[{22, 1000}, 23]
g[{0, 10^6}, 2]

20
468559

GolfScript

He estado tratando de mejorar mis habilidades de GolfScript, así que pensé en intentarlo con esta pregunta. Esto es lo que se me ocurrió:

`@@0\{.3$>}{.`4$?-1>@+\(}while@;;\;

Esto puede desglosarse así:

0 1000000 2    # parameters

`@@            # convert Z to string and put at bottom of stack
0\             # init counter and swap
{.3$>}         # loop condition: Y > X
{              # loop body
  .`           # convert to string
  4$?          # search for substring
  -1>@+        # if found add to counter
  \(           # decrement Y
}              # end loop body
while          # perform loop
@;;\;          # cleanup

Aunque se trata de GolfScript, el objetivo era más tratar de hacerlo relativamente eficiente en lugar de compacto, por lo que estoy seguro de que alguien puede señalar varias formas en que esto puede mejorarse.

Demostración : tenga en cuenta que he reducido Y en la demostración para que pueda completarse en <5 segundos.

PHP - 112

No hay bucles visibles, pero un poco pesado en la memoria!

<?=count(array_filter(range($argv[1],$argv[2]),function($i)use($argv){return strpos($i,$argv[3].'')!==false;}));

Uso php script.php 0 1000000 2

ECMAScript 3 a 6

usando expresiones regulares:

function f(x,y,z,r){for(r=0,z=RegExp(z);x<y;r+=+z.test(''+x++));return r}

Descompostura:

function f(x,y,z,r){        // note argument `r`, eliminating the need for `var `
  for( r=0, z=RegExp(z)     // omitting `new` since ES will add it if omitted
     ; x<y                  // 
     ; r+=+z.test(''+x++)   // `x++` == post increment
                            // `''+Number` == convert Number to string
                            // `test` gives true | false
                            // `+Boolean` converts boolean to 1 | 0
                            // `r+=Number` incrementing r (were Number is always 1 or 0)
     );                     // no body thus semicolon is mandatory!
  return r;                 // returning r
}

usando indexOf:

function f(x,y,z,r){for(r=0;x<y;r+=+!!~(''+x++).indexOf(z));return r}

Descompostura:

function f(x,y,z,r){                // note argument `r`, eliminating the need for `var `
  for( r=0                          // omitting `new` since ES will add it if omitted
     ; x<y                          // 
     ; r+=+!!~(''+x++).indexOf(z)   // `x++` == post increment
                                    // `''+Number` == convert Number to string
                                    // `indexOf` returns index or `-1` when not found
                                    // `!!~ indexOf` converts sentinel value to boolean
                                    // `+Boolean` converts boolean to 1 | 0
                                    // `r+=Number` incrementing r (were Number is 1 or 0)
     );                             // no body thus semicolon is mandatory!
  return r;                         // returning r
}

^{este cuerpo de función es un char menos que el de florent, por lo que cuando se usa la =>notación de función ES6 el total sería 62 char}

Llamada de ejemplo: f(0,1e6,2)
Ejemplo de uso:alert( f(0,1e6,2) );

JS Violín aquí

PD: ambas funciones anteriores devuelven su variable localr .
Entonces, al filtrar la variable de resultado ren el alcance global, uno puede guardar nuevamente 10 caracteres:

function f(x,y,z){for(r=0;i<=j;r+=+!!~(''+i++).indexOf(z));}

Ejemplo de uso: alert( f(0,1e6,2)||r );

Delphi - 120

Poco para mi gusto, voy a ver si puedo sacar algo.

var x,y,z,i,c:int16;begin readLn(x,y,z);for i:=x to y do if inttostr(i).contains(inttostr(z))then inc(c);writeln(c);end.

Python 2.7 - 50 caracteres

Un poco de ahorro en las respuestas existentes de Python.

lambda x,y,z:sum(1for n in range(y-x)if`z+x`in`n`)

Usando los siguientes trucos:

• La suma se puede aplicar a un generador, a diferencia de len, así que use sum (1 ...) en lugar de len ([n ...])
• Use `` en lugar de str (), que también permite ...
• Mata todos los espacios: mira '1 para' y 'si está z+xen n'
• Elimine el primer rango () arg comenzando en 0 y probando el desplazamiento (en realidad ... no me ahorra nada, pero me gusta su aspecto :))

En acción:

In [694]: (lambda x,y,z:sum(1for n in range(y-x)if`z+x`in`n`))(0,1000000,2)
Out[694]: 468559

k [28 caracteres]

{+/($x+!y)like"*",$:[z],"*"}

Uso

{+/($x+!y)like"*",$:[z],"*"}[0;1000000;2]
468559