15
\$\begingroup\$

Some positive integers can be shown to have a property called Chain divisibility. For a number to be chain-divisible by n, it must fulfil three requirements:

  1. Each digit divides the number formed by the n  digits that follow it.

    For example, the number 7143 is chain-divisible by 2 because 7 divides 14 and 1 divides 43. It is not chain-divisible by 3 because 7 does not divide 143.

  2. Each subsequence taken into account for divisibility must not have leading zeros.

    For instance, the number 14208 is not chain-divisible by 2 because 08 has a leading zero. It is, however, chain-divisible by 3, because 208 does not have a leading zero.

  3. All digits in the number must be unique.

For instance, the number 14280 is chain-divisible by 2, 3 and 4. If my explanation of chain divisibility is unclear please ask questions in the comments.

Input

The input to the program consists of a single integer n, followed by a space, then a number that has had certain digits replaced by underscores. For example, the following is a possible input:

3 6__2__4508

n will be greater than 1. The number will never be entirely underscores. You are not guaranteed that the first digit is not an underscore. The first digit will never be 0. n will never be greater or equal to the number of digits in the number.

Output

Output the number, with the digits replaced by integers such that the resulting number is chain-divisible by n. If more than one way of completing the chain-divisible number exists, any may be used as output. If there is no numbers that can complete it, output no answer. For instance, the output of the example input could be:

6132794508

This is code golf, so the shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ I assume that if n is greater than or equal to the number of digits in that number, the number is chain divisible? \$\endgroup\$ – John Dvorak Sep 4 '14 at 10:18
  • \$\begingroup\$ @Jan Dvorak n will never be equal to or greater than the number of digits in the input. It will always be smaller. I'll edit to reflect that. \$\endgroup\$ – absinthe Sep 4 '14 at 10:20
  • \$\begingroup\$ Are we required to write a full program, or does a function suffice? \$\endgroup\$ – John Dvorak Sep 4 '14 at 10:21
  • \$\begingroup\$ @Martin Yes. Character limit padding. \$\endgroup\$ – absinthe Sep 4 '14 at 10:22
  • \$\begingroup\$ @Jan Dvorak A full program. \$\endgroup\$ – absinthe Sep 4 '14 at 10:22
5
\$\begingroup\$

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

Output:

$ ./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
$

Explanation

  • The parameter expansion ${2//_/{0..9\}} replaces all underscores with {0..9}.
  • The resulting string is evaled to expand all these brace expressions.
  • The grep weeds out all possibilities where there are any repeated digits.
  • Then each remaining number is checked, digit-by-digit for conditions 1 and 2.
\$\endgroup\$
2
\$\begingroup\$

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'

Slow, but short. Simply compare every possible N-digit permutation with the given pattern and check all requirements. I've tested it only with 7 or 8 digits. Should work for 9 or 10 as well, but will take quite a while.

Edit: I added the missing default output "no answer".

\$\endgroup\$
2
\$\begingroup\$

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

This is a very naive implementation. I count the number of underscores, and then simply create a list of all digit-permutations of that length, to brute force every possible combination. This will perform horribly for larger numbers of underscores, but this is code golf and not fastest-code. :)

Edit: Ported this from Mathematica. See the edit history for the original version.

Edit: Fixed leading underscore cases.

\$\endgroup\$
  • \$\begingroup\$ Shouldn't Permutations be used instead of Tuples (overlooking the character count)? \$\endgroup\$ – DavidC Sep 4 '14 at 14:52
  • \$\begingroup\$ @DavidCarraher Why? I'd be missing a lot of combinations there, wouldn't I? \$\endgroup\$ – Martin Ender Sep 4 '14 at 14:57
  • \$\begingroup\$ Each digit in the number must be unique. Tuples does not impose that constraint. Permutations will, provided there are no repeated digits in the input set. And you can permute only the digits that have not yet been used. (Although, again, this may lengthen your code.) \$\endgroup\$ – DavidC Sep 4 '14 at 15:09
  • \$\begingroup\$ @DavidCarraher Ohhh, I overlooked the uniqueness requirement. I need to add that to the inner loop then, in which case I might as well stick with Tuples because it's shorter. \$\endgroup\$ – Martin Ender Sep 4 '14 at 15:16
  • \$\begingroup\$ @DavidCarraher fixed. \$\endgroup\$ – Martin Ender Sep 4 '14 at 15:21
1
\$\begingroup\$

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);}}}

Less golfed, with explanation:

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);
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.