# Numbers on a Chain

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.

• I assume that if n is greater than or equal to the number of digits in that number, the number is chain divisible? Sep 4, 2014 at 10:18
• @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. Sep 4, 2014 at 10:20
• Are we required to write a full program, or does a function suffice? Sep 4, 2014 at 10:21
• @Martin Yes. Character limit padding. Sep 4, 2014 at 10:22
• @Jan Dvorak A full program. Sep 4, 2014 at 10:22

# 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++))
}


### Output:

$./chain.sh 3 714_ 7140$ ./chain.sh 2 7141
$./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.

# 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()


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

## Mathematica Ruby, 349224 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.

• Shouldn't Permutations be used instead of Tuples (overlooking the character count)? Sep 4, 2014 at 14:52
• @DavidCarraher Why? I'd be missing a lot of combinations there, wouldn't I? Sep 4, 2014 at 14:57
• 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.) Sep 4, 2014 at 15:09
• @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. Sep 4, 2014 at 15:16
• @DavidCarraher fixed. Sep 4, 2014 at 15:21

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

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


# APL (Dyalog Unicode), 179 bytes

d←≠⊆⊢
p←≢¨'|'d'\d'⎕R'|'⊢n←2⊃a←' 'd⍞


Try it online!

-4 bytes from dzaima.

-9 bytes from ngn.

-4 bytes from Adam.

Golfed by a lot at The APL Orchard.

## Explanation

d←≠⊆⊢ splitting function: takes character on left, string on right.

p←≢¨'|'d'\d'⎕R'|'⊢n←2⊃a←' 'd⍞ a multiple assignment:

a←' 'd⍞ a - holds input split on spaces.

n←2⊃ n - holds the number string.

p←≢¨'|'d'\d'⎕R'|'⊢ p - holds the length of each blank space.

### Part 1: generating the required number partitions

r←{×≢p:{⍕⍎∊⍉↑('_'d n)(⍵⊆⍨p/⍳≢p)}¨(⊂p/⍕0),⍕¨{⍵~⍳⌊⊃⌽⍵÷10}⍳1-⍨10*+/p⋄⊂n}0

×≢p: ... ⋄⊂n If there are no underscores, return the number, wrapped.

Otherwise:

⍳1-⍨10*+/p generate range 1..(9 repeated sum(p) times)

{⍵~⍳⌊⊃⌽⍵÷10} remove 1..10^(sum(p)-1), getting all sum(p) digit numbers.

⍕¨ convert each to string

(⊂p/⍕0), prepend 0 repeated sum(p) times to it

{⍕⍎∊⍉↑('_'d n)(⍵⊆⍨p/⍳≢p)}¨ execute the following for each no. string:

(⍵⊆⍨p/⍳≢p) split into pieces of sizes in p

↑('_'d n) add the input to it and make a 2xn matrix

⍕⍎∊⍉ transpose the fillers and enlist them, then remove all spaces using ⍕⍎

r/⍨ filter this list by:

### Part 2: checking chain divisibility

(⍎⊃a)∘{(∧/'0'≠⊃¨x)>1∊×(⊖⍺↓⊖⍎¨⍵)|⍎¨x←1↓⍺,/⍵}¨

(⍎⊃a)∘{...} execute the following, using the first number as constant left argument:

⍎¨x←1↓⍺,/⍵ store overlapping groups of 3 in x, convert to int

| modulo:

(⊖⍺↓⊖⍎¨⍵) list of numbers they should be divisible by

1∊× are any of them truthy?

> check if the result is lesser than:

(∧/'0'≠⊃¨x) whether any of the groups have a leading zero

filter complete!

### Part 3: checking uniqueness

t≡¨∪¨t← boolean mask for whether each number matches itself uniquified.

t/⍨ filter to get the final array

⊃(...),⊂'no answer' pick the first item of the result with 'no answer' appended.

if there are no results, it will default to that.