9 Digit Problem

Question

Write a program to find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

1. The number should be divisible by 9.
2. If the rightmost digit is removed, the remaining number should be divisible by 8.
3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
4. And so on, until there’s only one digit (which will necessarily be divisible by 1).

Credit Dávid Németh

Answer 1

CJam - 26

1{;9,:)_mrs0@{_3$<i\%+}/}g

It's randomized but works pretty fast with the java interpreter. It can take a couple of minutes with the online interpreter.

Explanation:

1 pushes 1 (to be explained later)
{…}g is a do-while loop
; removes a value from the stack (initially the 1 we started with)
9, makes the array [0 ... 8]
:) increments the array elements, resulting in [1 ... 9]
_ duplicates the array
mr shuffles the array
s converts to string
0@ pushes 0 then brings the other copy of the array on top
{…}/ is a for-each loop (over the numbers 1 ... 9)
_ duplicates the current number (let's call it "k")
3$ copies the numeric string from the stack
<i gets the substring with the first k characters then converts to integer
\% swaps with the other copy of k then gets the remainder (%k)
+ adds the remainder to the previous value on the stack (initially 0 from above)
At this point, we have the numeric string on the stack, followed by a 0 if the number matches all the requirements (i.e. all the remainders were 0) or a non-0 value otherwise.
The top of the stack becomes the do-while loop condition. It is popped and the loop continues if the condition was true.
If we found the solution, the condition is 0 (false), the loop ends and the rest of the stack (the numeric string) is printed.
If it's not the solution, the condition is the non-0 value (true) and the loop continues with the string on the stack. The string gets popped at the start of the next iteration (so the loop expects a value on the stack, and that's the reason for the initial 1).

Thanks Dennis for making the code shorter and more convoluted :p

Answer 2

Javascript (E6) 105 125 134

Recursive building of the number, each step check the divisibility.
Runtime near 0 sec
No I/O this time, as the OP asked for a program to find the number, and the number is found and automatically logged to console

Golfed more Courtesy of MT0

(Q=(n,d,b)=>([(m=n+(s=[...b]).splice(i,1))%d||Q(m,d+1,s)for(i in b)],d>9&&(Q.z=n),Q.z))('',1,'123456789')

Golfed

(Q=(n='',d=1,b=[...'123456789'],i)=>{
for(i=0;s=[...b],m=n+s.splice(i,1),b[i];i++)m%d||Q(m,d+1,s);d>9&&(Q.z=n);return Q.z;
})()

Ugly

(Q=(n='', d=1, b=[...'123456789'], i) => {
   for(i=0; s=[...b], m=n+s.splice(i,1), b[i]; i++)
     m % d || Q(m,d+1,s);
   d > 9 && (Q.z=n);
   return Q.z;
})()

Bonus

With 3 little changes, you can use the same function to find longer numbers using base > 10. For instance in base 14 ...

(Q=(n='',d=1,b=[...'123456789ABCD'],i)=>{
  for(i=0; s=[...b], m = n+s.splice(i,1), b[i]; i++)
    parseInt(m,14)%d || Q(m,d+1,s);
  d>13 && (Q.z=n);
  return Q.z;
})()

9C3A5476B812D

Ungolfed

Q=(n,d,b,i,c,z)=>{ // i,c,z fake parameters instead of vars.
  for (i=0; b[i]; i++)
  {
    s=[...b];
    m = n + s.splice(i,1);
    if (m % d == 0)
      if (z = d<9 ? Q(m, d+1, s) : m) return z;
  }
}
Q('',1,[...'123456789'])

Answer 3

Python3, 214, 199, 184, 176, 174, 171, 165, 150, 146

from itertools import*
g=lambda i,d:d==1!=print(i)or int(i[9:])%d==0!=g(i[:-1],d-1)
for x in permutations("123456789"):g("".join(map(str,x))*2,9)

output:

381654729

This is my first golf script. Hope you like it :)

Answer 4

Perl, 56

Usage: perl -E '...'

{$s++;redo if grep{$s!~$_||substr($s,0,$_)%$_}1..9}say$s

Output: 381654729

This program is really slow. As in more than 3.5 hours.

As a more fun exercise, I decided to develop an extremely fast algorithm:

my $set = [1..9];
for my $divisor (2..9) {
    my $newset = [];
    for my $element (@$set) {
        my $num = $element * 10;
        for (my $digit = $divisor - ($num % $divisor); $digit < 10; $digit += $divisor) {
            if (index($element, $digit) == -1) {
                push @$newset, $num + $digit;
            }
        }
    }
    $set = $newset;
}

print "@$set\n";

The above runs in .00095 seconds, and confirms that there is only one solution to this problem.

Answer 5

Ruby, 66 78 chars

[*r=1..9].permutation{|i|r.all?{|x|eval(i[0,x]*"")%x<1}&&$><<i*""}

Runtime is ~8 seconds (output printed after 3 s).

This doesn't stop after finding the first number, so technically it prints all numbers that fulfill the criteria - but since there's only one such number, it doesn't make a difference.

Ruby 1.8, 63

[*r=1..9].permutation{|i|r.all?{|x|eval(i[0,x]*"")%x<1}&&$><<i}

Essentially the same solution as above. In Ruby 1.8, arrays are converted to strings by implicitly calling Array#join on them, so we can save the call to that. Interestingly, the code also runs much faster in Ruby 1.8 than 2.0 (4.5 seconds total runtime, output printed after 1.6 s).

Answer 6

Pyth, 33 characters

=Y]kFkY~Yf>ql{TlT%vTlTm+k`dr1T)pk

To test it, put the above code as standard input in the link in the title.

After compiling into Python 3.4:

k=''
T=10
Y=[k]
for k in Y:
 Y+=list(filter(lambda T:(len(set(T))==len(T))>(eval(T)%len(T)),
                map(lambda d:k+repr(d),range(1,T))))
print(k)

Explanation:

=Y]k:Y=['']

FkY: for k in F:

~Y: Add to Y

f: Filter by

>ql{TlT: All unique elements and

%vTlT: eval(element)%len(element)=0

m+k` d On the list of k + repr(d)

r1T: for d from 1 to 9.

): End for loop

pk: print k

Answer 7

Haskell 129 121

Here is my amateurish Haskell attempt (suggestions/improvements would be greatly appreciated). It might not be the shortest, but it does execute in only .19 .65 seconds after Flonk's changes on my system.

import Data.List;f=foldl1$(+).(*10);main=print$[f x|x<-permutations[1..9],f[mod(read.take y.show$f x)y|y<-[9,8..1]]<1]!!0

Answer 8

GolfScript (35 chars)

1,{{10*){.)}8*}%{`..&=},{.`,%!},}9*

Online demo

This builds prefixes which satisfy the condition.

# Initial prefixes: [0]
1,
# Loop 9 times
{
    # Extend each prefix by digits 1 to 9
    {10*){.)}8*}%
    # Filter out ones which repeat a digit
    {`..&=},
    # Filter down to ones which are divisible by their length
    {.`,%!},
}9*

Answer 9

Python, 142, 139, 125, 124

Essentially same as @Ventero's solution if I understood his code correctly, but in Python.(Much of the credit goes to @Greg Hewgill.)

from itertools import*;print[s for s in map(''.join,permutations('123456789'))if all(t(s[:i])%i==0 for i in range(1,9))][0]

Answer 10

Javascript 75 (terminating)

Bruteforce solution (super slow)

for(a=c=1;b=c&&++a;)for(c=9;~(a+'').search(c)&&b%c<1;)--c?b=b/10|0:alert(a)

If you want to see the result in this lifetime, update the initial value to something like a=c=38e7

Javascript 70 (non-terminating)

for(a=1;b=++a;)for(c=9;~(a+'').search(c)&&b%c<1;)--c?b=b/10|0:alert(a)

And just for fun, a random bruteforce that runs much faster: (ES6 only)

for(a=i=[..."123456789"];b=c=i&&a.sort(x=>Math.random()*9-5|0).join('');)for(i=9;c%i<1;)--i?c=c/10|0:alert(b)

Answer 11

Perl, 72

Usage: perl -M5.010 find-9-digits.pl

{$s=join'',sort{4-rand 8}1..9;redo if grep{substr($s,0,$_)%$_}2..9}say$s

Output: 381654729

This program is slow. It might take more than 10 seconds, because it shuffles the digits "123456789", but the shuffle has a flaw.

Ungolfed:

# Enter a block.
{
     # Shuffle the characters "123456789".
     $s = join('', sort({2 - rand(4)} 1..9));

     # Redo block if any divisiblity test fails; grep returns the
     # number of failing tests.
     redo if grep({
        # For each divisor $_ in 2..9, test if the first $_ digits of
        # of $s are divisible by $_.  The test fails if the remainder
        # is a true value (not zero).
        substr($s, 0, $_) % $_
     } 2..9);
}
say $s;

I golfed the code that shuffles the array of digits 1..9:

• use List'Util shuffle;shuffle 1..9 (34 characters)
• sort{(-1,1)[rand 2]}1..9 (24 characters)
• sort{.5<=>rand}1..9 (19 characters)
• sort(2-rand 4}1..9 (18 characters)
• sort{4-rand 8}1..9 (18 characters)

Perl expects the sort block to compare $a and $b in a consistent way. My sort blocks never look at $a and $b. They return a random ordering so the sort becomes a shuffle.

If I would use sort{.5<=>rand}1..9, my program would run faster. That one compares 0.5 with a random float from 0.0 to 1.0, excluding 1.0, for a 1/2 chance that $a < $b, and an almost 1/2 chance that $a > $b. (Beware: This is a "Microsoft shuffle", which is not a fair shuffle. This has bias because .5<=>rand does not provide a consistent ordering.)

Suppose that I golf away one character and use the much worse sort(2-rand 4}1..9. Perl expects the sort block to return an integer, but 2-rand 4 is a float. It is a random float from -2.0 to 2.0, excluding -2.0. Perl truncates this float toward zero, with these results:

• 1/4 chance that $a < $b, integer -1 from -2.0 < float <= -1.0
• near 1/2 chance that $a == $b, integer 0 from -1.0 < float < 1.0
• near 1/4 chance that $a > $b, integer 1 or 2 from 1.0 <= float <= 2.0

When $a == $b, Perl does not shuffle well. So, my program would do more shuffles, until it gets enough shuffles where 2-rand 4 did not return 0 too often. My program would run so slow, it might take more than one minute.

I use sort{4-rand 8}1..9, so there is only a 1/4 chance that $a == $b, and my program uses fewer shuffles.

Answer 12

Scala (128 chars)

My stab at this...

Seq(1,2,3,4,5,6,7,8,9).permutations.filter(p=>(2 to 8)forall{n=>(p.take(n).mkString.toLong%n==0)}).map(_.mkString.toLong).toList

Answer 13

CJam, 35 bytes

0{)_`$A,1>s=!1$9,{9\m1$\%@+\A/}/;}g

After roughly 27 minutes, this produces the following output:

381654729

How it works

0         " Push 0 (“n”).                                                      ";
{         "                                                                    ";
  )_`$    " Increment “N”, duplicate, stringify and sort the resulting string. ";
  A,1>s   " Push '123456789'.                                                  ";
  =!      " Push 0 if the strings are equal and 1 otherwise (“a”).             ";
  1$      " Copy “n”.                                                          ";
  9,{     " For each i in [ 0 1 2 3 4 5 6 7 8 ].                               ";
    9\m   " Calculate “9 - i”.                                                 ";
    1$\%  " Calculate “n % (9 - i)”.                                           ";
    @+    " Add the result to “a”.                                             ";
    \A/   " Swap “a” with “n” and calculate “n / 10”.                          ";
  }/      "                                                                    ";
  ;       " Discard “n”.                                                       ";
}g        " If “a > 0”, repeat the loop.                                       ";

Answer 14

Python 2 (78)

x=1
while len(set(`10*x`))<=9+sum(x/10**i%(9-i)for i in range(9)):x+=1
print x

No need to generate permutations, just try each number and check if its digits plus 0 are distinct. Takes a while to run.

Answer 15

SWI-Prolog 84

g([],O,_,O).
g(L,N,I,O):-nth1(_,L,D,R),M is N*10+D,J is I+1,0 is M mod J,g(R,M,J,O).

It is a bit cheating, because the list of digits needs to be supplied in the query:

?- g([1,2,3,4,5,6,7,8,9],0,0,O).
O = 381654729 ;
false.

However, it is what makes this code interesting: you can solve the problem for any list of digits. For example:

?- g([1,2,3,4,5,6,7,8,9,0],0,0,O).
O = 3816547290 ;
false.

?- g([1,2,3,4,5,6,7,8],0,0,O).
O = 38165472 ;
false.

?- g([1,2,3,4,5,6,7],0,0,O).
false.

?- g([1,2,3,4,5,6],0,0,O).
O = 123654 ;
O = 321654 ;
false.

?- g([2,2,3,3,5,6,7,8,9],0,0,O).
O = 363258729 ;
O = 363258729 ;
O = 363258729 ;
O = 363258729 ;
O = 723258963 ;
O = 723258963 ;
O = 723258963 ;
O = 723258963 ;
false.

Answer 16

Python 2 – 114

Not even the shortest Python solution, but I am sharing it anyway:

e=""
f=lambda s,n:[[n,e.join(f(s.replace(j,e),n+j)for j in s)][s>e],e][n>e>0<int(n)%len(n)]
print f("123456789",e)

Answer 17

Bash+coreutils, 159 bytes

l=`echo {1..8}`
for d in {2..8};{
l=$(printf "a=%s;if(!a%%$d)a\n" $(eval echo {${l// /,}}{1..8}|tr \  '
'|grep -Pv '(\d).*\1')|bc|paste -d\  -s -)
}
echo ${l}9

This is kind of long, but I think the algorithm is perhaps one of the fastest, considering this is a (usually slow) shell script that runs in less than 0.1 second.

The algorithm goes something like this:

• Start with the leftmost digit (1-8)
• append the next digit to the right (1-8)
• remove any numbers with repeated digits (grep)
• check for divisibility by $d (the digit number) using bc, with an expression generated by printf
• Repeat the above until an 8 digit number is obtained

Note we take a couple of shortcuts, but I think these are mathematically sound:

• The leftmost digit must be divisible by 1, which is all digits, so we don't explicitly check for the first set of leftmost digits
• The rightmost digit must be 9 (actually I'm not sure if this is a valid assumption - I'll have to think about it a bit)

Answer 18

C++, 187

I just had to try this in C++. Obviously, it's not going to be the shortest solution but here it is:

#include <algorithm>
using namespace std;bool c(int n,int d=9){return d<2||n%d==0&c(n/10,d-1);}int main(){for(char n[]="123456789";next_permutation(n,n+9);)if(c(atoi(n)))return atoi(n);}

returns the number instead of printing it to save some characters (damn include). Under POSIX-systems this will of course be converted to an 8-bit unsigned and thus not correct - but the program will calculate a correct number.

Ungolfed (requires C++11):

#include <iostream>
#include <algorithm>
using namespace std;

bool check(int n, int digit = 9)
{
  return (n % digit==0) && (digit == 1 || check(n/10,digit-1));
}

int main()
{
  string num {"123456789"};
  while (next_permutation(begin(num), end(num)))
    if (check(stoi(num))){
      cout << num << endl;
      break;
    }
}

Answer 19

T-SQL 2005+ - 203

T-sql is not a very competitive golf language...

with A(n)as(select top 10 number from spt_values where'p'=type),R as(select \r,1l union all select r*10+n,l+1from R,A where n not in(select substring(str(r),n,1)from A)and(r*10+n)%l=0)select max(r)FROM R

Must be run on the master database. You can replace the first CTE with this to make it database agnostic but then it uses a few more characters (and requires 2008)

with A as(select*from(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9))f(n))

Readable formation:

 with A(n)as(select top 10 number from spt_values where'p'=type),
    R as(select \ r,1 l 
        union all 
        select r*10+n,l+1
        from R,A
        where n not in (
            select substring(str(r),n,1)
            from A
        )
        and(r*10+n)%l=0)
select max(r) FROM R

Basically we keep adding digits to the back of the r number that we haven't seen in the string yet, and making sure that the new string is still modulo 0 of the current level. We initialize R to \, This is really the only trick in this code. Which is a crazy way to set it to 0 in money datatype. It's I'm guessing a way to let you type \ instead of currency. $ also does the same thing in T-SQL, but $l would try to interpret a pseudo column that doesn't exist and throw an error. This lets us avoid the worry about using int which would cause an overflow normally at the 10th concatenation, forcing us to actually check the level. Edit: Fun fact T-sql even in 2014 doesn't have a built in way to turn a string into a table of values (e.g. no split func), so we actually also get to reuse our A table twice to iterate the characters in the stringified R.

T-Sql precedence rules are annoying so we have to use numeric concatenation (*10+n), rather than string concat.

Answer 20

PHP, 89 bytes

random version, 89 bytes:

for($n=123456789;$n=str_shuffle($n);$d||die("$n"))for($d=10;--$d&&substr($n,0,$d)%$d<1;);

shuffles a string containing the digits, then tests divisibility in a loop.

Run with -nr.

---

brute force loop, 90 bytes, very slow:

for(;++$i<1e9;$d||die("$i"))for($d=10;--$d&&max(count_chars($i))<2&substr($i,0,$d)%$d<1;);

loops from 100000001, tests divisibility in inner loop, and exits when it finds a solution.

---

recursive function, 94 bytes, very fast:

function f($n="",$e=1){while($d++<9)strpos(_.$n,"$d")|($x=$n.$d)%$e||print$e>8?$x:f($x,$e+1);}

appends one digit that´s not yet in the number, if divisibility by length is given, recurse (or print).

This exploits that there is only one solution. without that, print$e>8?$x:f($x,$e+1) had to be print$e>8?"$x\n":f($x,$e+1) (+3 bytes, print all solutions) or ($e>8?die("$x"):f($x,$e+1)) (+4 bytes, exit at first solution) or the solutions would be printed without a delimiter.

Call with f();

--

TiO

The brute force version has no TiO for obvious reasons, but you can try the other two.

The function call´s runtime is measured inline (somewhere between 2 and 4 milliseconds);
total runtime is measured by the website (usually between 50 and 500 ms).