Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

share|improve this question
24  
The first rule seems unnecessary. Any number that consists of digits 1-9 once each will always be divisible by 9. –  Geobits Jun 24 at 19:31
6  
What's the code-aspect here? This sounds like it could be posted on Puzzling –  Simon André Forsberg Jun 24 at 19:32
10  
Even if we’re going to call it a “standard loophole”, code golf challenges that produce a fixed output generally shorter than any code that could build it are usually not particularly interesting. –  minitech Jun 24 at 21:23
8  
The problem I have with challenges like this is that the border between hardcoding and applying mathematical properties is vague. For example, the divisibility rule for 5 is that the number has to end in 0 or 5. Is restricting the choices for that digit to 0 and 5 hardcoding part of the output? It'd get even worse if we were dealing with 10-digit numbers. –  user2357112 Jun 24 at 22:07
3  
@Sylwester What you've done is assume there's only 1 way to solve the problem, because you're afraid of breaking the loophole. "Loop through numbers checking requirements". This completely excludes any interesting examples. And the question is: "Which language can check these things and loop in the fewest characters". –  Cruncher Jun 26 at 14:19

19 Answers 19

up vote 8 down vote accepted

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

share|improve this answer
    
Nice! You can save one more byte by using a dummy value: 0{;9,:)_mrsT@{_3$<i\%+}/}g –  Dennis Jun 24 at 22:09

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'])
share|improve this answer
    
+1 for using E6. –  Awal Garg Jun 25 at 5:24
1  
105 Characters: (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') –  MT0 Jun 25 at 19:38
    
101 Characters: (Q=(n,d,b)=>Math.max(...[(m=n+(s=[...b]).splice(i,1))%d||Q(m,d+1,s)for(i in b)],n))('',1,'123456789') –  MT0 Jun 25 at 19:50
    
@MT0 wow! Array comprehension strikes back. I'll take the 1st one, becouse the other one can find a wrong number if there is not one correct (IE counting up to 7 instead of 9). –  edc65 Jun 25 at 20:37

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.

share|improve this answer

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 :)

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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*
share|improve this answer

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
share|improve this answer
    
Welcome to PPCG.SE! Try adding <!-- language: lang-haskell --> two lines before your code for syntax highlighting! –  Flonk Jun 25 at 6:57
    
And I did indeed find a way to save 8 more characters! Instead of checking if each remainder==0, you could sum over all of them and check if that==0, which is just as long. By seperating out the foldl1 into a function however, you can use that instead of sum or any. 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 –  Flonk Jun 25 at 7:19
    
It seems that you counted your characters including the trailing newline: there are only 128 characters in your code. –  Peter Taylor Jun 25 at 8:41
    
@Flonk I absolutely love the use of the f function on the mod predicate to avoid writing foldl1, although the extra cycles do hamper performance severely. –  DrJPepper Jun 25 at 14:33
    
@DrJPepper 0.65 seconds? Meh. Lets make that worse! You can also replace !!0 with a call to f, which works out since there's only one item in the list. The list [9,8..1] can also be replaced by x, because the order doesn't matter. Talk about code reuse! –  Flonk Jun 26 at 9:26

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)
share|improve this answer

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]
share|improve this answer
    
You should be able to replace r(9,1,-1) with r(9), as the order of iteration doesn't really matter. –  Ventero Jun 24 at 20:39
    
You'd have to use r(1,9) because %0 is an error. –  Greg Hewgill Jun 24 at 20:40
    
@GregHewgill Ah, of course you're right, didn't realize it starts with 0. Guess it's obvious I'm not a Python expert. :) –  Ventero Jun 24 at 20:41
    
@Ventero Thanks for the tip, Greg is right I'll have to use r(1, 9) in Python. –  undefined is not a function Jun 24 at 20:44
1  
Using permutations("123456789") and ''.join(s[:i]) is probably shorter than what you have (and then you can eliminate r=range) –  Greg Hewgill Jun 24 at 20:46

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
share|improve this answer
    
You can save a character by removing the space between (2 to 8) and forall. –  ProgramFOX Jun 25 at 15:41
    
@ProgramFOX I had no idea. I've always thought a dot or a space was required there. Thanks, I've edited down to 128 chars. –  Keith Pinson Jun 25 at 17:34

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.

share|improve this answer
    
Nice hand-rolled shuffle –  Miller Jun 25 at 9:08

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.                                       ";
share|improve this answer
    
Impressive size, but it seems even slower than mine, and I suspect it's not correct –  aditsu Jun 24 at 20:44
    
I don't fully understand it, but it seems to accept 0 as a digit? Also, when does it stop? –  aditsu Jun 24 at 20:48

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.

share|improve this answer

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.
share|improve this answer

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)
share|improve this answer

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)
share|improve this answer

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;
    }
}
share|improve this answer

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.

share|improve this answer
    
You can save 5 bytes and allow it to run on all kinds of databases by replacing the first row with: with A as(select 1n union all select n+1 from A where n<9), –  comfortablydrei Jun 27 at 8:07
    
Good point. In real code, I would never use a rCTE to count so it didn't even dawn on me to try it! –  Michael B Jun 27 at 12:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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