Números en una cadena

15

Se puede mostrar que algunos enteros positivos tienen una propiedad llamada divisibilidad en cadena. Para que un número sea divisible en cadena por  n , debe cumplir tres requisitos:

  1. Cada dígito divide el número formado por los n  dígitos que le siguen.

    Por ejemplo, el número 7143 es la cadena-divisible por 2 porque 7 divisiones 14 y 1 divide 43. Es no cadena-divisible por 3 porque 7 no divide 143.

  2. Cada subsecuencia tomada en cuenta para la divisibilidad no debe tener ceros a la izquierda.

    Por ejemplo, el número 14208 no es divisible en cadena por 2 porque 08 tiene un cero a la izquierda. Sin embargo, es divisible en cadena por 3, porque 208 no tiene un cero a la izquierda.

  3. Todos los dígitos en el número deben ser únicos.

Por ejemplo, el número 14280 es divisible en cadena por 2, 3 y 4. Si mi explicación de la divisibilidad de la cadena no está clara, haga preguntas en los comentarios.

Entrada

La entrada al programa consiste en un solo entero n, seguido de un espacio, luego un número que ha tenido ciertos dígitos reemplazados por guiones bajos. Por ejemplo, lo siguiente es una entrada posible:

3 6__2__4508

n será mayor que 1. El número nunca será completamente subrayado. No se garantiza que el primer dígito no sea un guión bajo. El primer dígito nunca será 0. n nunca será mayor o igual al número de dígitos en el número.

Salida

Genere el número, con los dígitos reemplazados por enteros de modo que el número resultante sea divisible en cadena por n . Si existe más de una forma de completar el número divisible en cadena, cualquiera puede usarse como salida. Si no hay números que puedan completarlo, salida no answer. Por ejemplo, la salida de la entrada de ejemplo podría ser:

6132794508

Este es el código de golf, por lo que gana el código más corto.

Ajenjo
fuente
Supongo que si nes mayor o igual que el número de dígitos en ese número, ¿el número es divisible en cadena?
John Dvorak
@ Jan Dvorak n nunca será igual o mayor que el número de dígitos en la entrada. Siempre será más pequeño. Lo editaré para reflejar eso.
ajenjo
¿Estamos obligados a escribir un programa completo o una función es suficiente?
John Dvorak
@ Martin Sí. Relleno de límite de caracteres.
ajenjo
@ Jan Dvorak Un programa completo.
ajenjo

Respuestas:

5

Bash + coreutils, 197 bytes

for i in $(eval printf '%s\\n' ${2//_/{0..9\}}|grep -vP '(\d).*\1');{
for((f=d=0;d<${#i}-$1;d++));{
((${i:d+1:1}==0||10#${i:d+1:$1}%${i:d:1}))&&f=
}
[ $f ]&&echo $i&&((c++))
}
((c))||echo no answer

Salida:

$ ./chain.sh 3 714_
7140
$ ./chain.sh 2 7141
no answer
$ ./chain.sh 2 14208
no answer
$ ./chain.sh 3 14208
14208
$ ./chain.sh 2 1_208
no answer
$ ./chain.sh 3 1_208
14208
$ ./chain.sh 2 6__2__4508
no answer
$ ./chain.sh 3 6__2__4508
6132794508
$

Explicación

  • La expansión del parámetro ${2//_/{0..9\}}reemplaza todos los guiones bajos con {0..9}.
  • La cadena resultante se evaledita para expandir todas estas expresiones de llaves.
  • El grepelimina a todas las posibilidades en las que hay los dígitos repetidos.
  • Luego, se verifica cada número restante, dígito por dígito para las condiciones 1 y 2.
Trauma digital
fuente
2

Python - 239 267

from itertools import*
T=raw_input()
n=int(T[0])
N=len(T)-2
J=''.join
for i in permutations('0123456789',N):
 if all([S in[I,'_']for S,I in zip(T[2:],i)])*all([i[j]>'0'<i[j+1]and int(J(i[j+1:j+n+1]))%int(i[j])<1for j in range(N-n)]):print J(i);exit()
print'no answer'

Lento pero corto. Simplemente compare cada posible permutación de N dígitos con el patrón dado y verifique todos los requisitos. Lo probé solo con 7 u 8 dígitos. Debería funcionar también para 9 o 10, pero llevará bastante tiempo.

Editar: agregué el resultado predeterminado que falta "sin respuesta".

Falko
fuente
2

Mathematica Ruby, 349 224 229 bytes

n=$*[0].to_i
r='no answer'
(?0..?9).to_a.permutation($*[1].count'_'){|q|s=$*[1]
q.map{|d|s=s.sub'_',d}
c=s.chars
(t=1
c.each_cons(n+1){|c|e=c.shift.to_i
(t=!t
break)if e<1||c[0]==?0||c.join.to_i%e>0}
(r=s)if t)if c==c.uniq}
$><<r

Esta es una implementación muy ingenua. Cuento la cantidad de guiones bajos, y luego simplemente creo una lista de todas las permutaciones de dígitos de esa longitud, para forzar la fuerza bruta en cada combinación posible. Esto funcionará horriblemente para un mayor número de guiones bajos, pero este es el código de golf y no el código más rápido. :)

Editar: Portado esto desde Mathematica. Vea el historial de edición para la versión original.

Editar: Se corrigieron los principales casos de subrayado.

Martin Ender
fuente
¿No deberían usarse las permutaciones en lugar de las tuplas (con vistas al recuento de caracteres)?
DavidC
@DavidCarraher ¿Por qué? Me faltarían muchas combinaciones allí, ¿no?
Martin Ender
Cada dígito en el número debe ser único. Tuplesno impone esa restricción. Permutationswill, siempre que no haya dígitos repetidos en el conjunto de entrada. Y puede permutar solo los dígitos que aún no se han utilizado. (Aunque, de nuevo, esto puede alargar su código.)
DavidC
@DavidCarraher Ohhh, pasé por alto el requisito de singularidad. Necesito agregar eso al bucle interno, en cuyo caso también podría seguir Tuplesporque es más corto.
Martin Ender
@DavidCarraher corregido.
Martin Ender
1

Java, 421

class C{static int n;public static void main(String[]a){n=new Short(a[0]);f(a[1]);System.out.print("no answer");}static void f(String s){if(s.contains("_"))for(int i=0;i<=9;i++)f(s.replaceFirst("_",i+""));else{for(int i=1;i<s.length()-n+1;){String t=s.substring(i,i+n);if(t.charAt(0)<49||new Long(t)%new Long(s.substring(i-1,i++))>0||s.chars().distinct().count()<s.length())return;}System.out.print(s);System.exit(0);}}}

Menos golf, con explicación:

class C {

    static int n;

    public static void main(String[] a) {
        n = new Short(a[0]);
        f(a[1]);
        System.out.print("no answer");
    }

    /**
     * This method is called recursively, each time with
     * another underscore replaced by a digit, for all possible digits.
     * If there is a solution, the method prints it and exits the program.
     * Otherwise, it returns.
     */
    static void f(String s) {
        if (s.contains("_")) {
            for (int i = 0; i <= 9; i++) {
                f(s.replaceFirst("_", i + ""));
            }
        } else {
            for (int i = 1; i < s.length() - n + 1;) {
                String t = s.substring(i, i + n);       // on each substring...
                if (                                    // test for the three rules
                    t.charAt(0) < 49 ||
                    new Long(t) % new Long(s.substring(i - 1, i++)) > 0 ||
                    s.chars().distinct().count() < s.length()
                ) {
                    return;            // a rule was broken
                }
            }
            System.out.print(s);       // if we made it this far, it's a success!
            System.exit(0);
        }
    }
}
Ypnypn
fuente