13
\$\begingroup\$

Your program must take an input (n for the purpose of description) and output all permutations of a number that is n digits long with no repeating digits, where each of the digits preceding and including its index are divisible by the place in the number that it falls.

You can read about magic numbers here.

Rules:

  • 1 <= n <= 10
  • No digits may be repeated
  • The leading 0 must be present (if applicable)
  • The 1st through xth digit of the number (starting with the first character as 1) must be divisible by x, i.e. in 30685, 3 is divisible by 1, 30 is divisible by 2, 306 is divisible by 3, 3068 is divisible by 4, and 30685 is divislbe by 5.
  • The program must take an integer as input (through the command line, as a function argument, etc.) and print all permutations that satisfy the rules.
  • Output must be separated by 1 or more white space character
  • Permutations may start and with zero (so they're not technically magic numbers).
  • The order of output does not matter
  • You do not need to handle unexpected input
  • Least characters in bytes wins

Examples

Given 1:

0
1
2
3
4
5
6
7
8
9

Given 2:

02
04
06
08
10
12
14
16
18
20
24
26
28
30
32
34
36
38
40
42
46
48
50
52
54
56
58
60
62
64
68
70
72
74
76
78
80
82
84
86
90
92
94
96
98

Given 10:

3816547290

Credit to Pizza Hut & John H. Conway for the original puzzle (Option A). Thanks to @Mego and @sp3000 for their links.

\$\endgroup\$
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/63183/42854 \$\endgroup\$ – Daniel Apr 5 '16 at 16:46
  • 6
    \$\begingroup\$ @DavisDude "Related" doesn't mean "duplicate". The purpose of posting a related link is for that challenge to show up as "Linked" in the sidebar. \$\endgroup\$ – Martin Ender Apr 5 '16 at 16:59
  • 1
    \$\begingroup\$ Related reading: polydivisible numbers \$\endgroup\$ – Sp3000 Apr 5 '16 at 17:38
  • 3
    \$\begingroup\$ Do leading 0's need to be included output numbers that have them? \$\endgroup\$ – xnor Apr 6 '16 at 4:19
  • 4
    \$\begingroup\$ You mention printing and whitespace when it comes to output, but for a function, the most natural form of output would probably be returning a list. Is that allowed? \$\endgroup\$ – Dennis Apr 6 '16 at 4:44
4
\$\begingroup\$

Jelly, 20 17 16 bytes

QḣQV%S
ØDṗçÐḟRj⁷

This is very slow and memory intensive... Try it online!

How it works

ØDṗçÐḟRj⁷  Main link. Input: n (integer)

ØD         Yield d := '0123456789'.
  ṗ        Compute the nth Cartesian power of d.
      R    Range; yield [1, ..., n].
    Ðḟ     Filter false; keep strings of digits for which the following yields 0.
   ç         Apply the helper link to each digit string and the range to the right.
       j⁷  Join the kept strings, separating by linefeeds.


QḣQḌ%S     Helper link. Arguments: s (digit string), r (range from 1 to n)

Q          Unique; deduplicate s.
 ḣ         Head; get the prefixes of length 1, ..., n or less.
           If s had duplicates, the final prefixes fill be equal to each other.
  Q        Unique; deduplicate the array of prefixes.
   V       Eval all prefixes.
    %      Compute the residues of the kth prefixes modulo k.
           If s and the array of prefixes have different lengths (i.e., if the
           digits are not unique), some right arguments of % won't have corr. left
           arguments. In this case, % is not applied, and the unaltered right
           argument is the (positive) result.
     S     Add all residues/indices. This sum is zero iff all digits are unique
           and the kth prefixes are divisible by k.
\$\endgroup\$
  • 3
    \$\begingroup\$ If this is slow... my answer is a sleepy slug \$\endgroup\$ – Luis Mendo Apr 5 '16 at 21:31
6
\$\begingroup\$

JavaScript (Firefox 30-57), 77 bytes

f=n=>n?[for(s of f(n-1))for(c of"0123456789")if(s.search(c)+(s+c)%n<0)s+c]:[""]

Edit: Saved 1 byte thanks to @edc65.

\$\endgroup\$
  • \$\begingroup\$ A gem! just save 1 byte with ...of"012... \$\endgroup\$ – edc65 Apr 5 '16 at 19:55
  • \$\begingroup\$ @edc65 Ugh, I can't believe I overlooked that. \$\endgroup\$ – Neil Apr 5 '16 at 20:21
3
\$\begingroup\$

Pyth, 19 bytes

jf!s%VsM._TS;.PjkUT

Demonstration

A brute force solution. Explanation to follow. Inspiration thanks to FryAmTheEggman


22 bytes

juf!%sThH{I#sm+LdTGQ]k

Demonstration

Numbers are built and stored as strings, and only converted to ints to check divisibility.

Explanation:

juf!%sThH{I#sm+LdTGQ]k
 u                 Q]k    Apply the following input many times, starting with ['']
             m    G       For each string at the previous step,
              +LdT        Append each digit to it
            s             Concatenate
         {I#              Filter out strings with repeats
  f                       Filter on
     sT                   The integer
    %  hH                 Mod the 1 indexed iteration number
   !                      Is zero.
j                         Join on newlines.
\$\endgroup\$
  • \$\begingroup\$ I'm curious: just how masochistic do you have to be to learn Pyth? /s \$\endgroup\$ – DavisDude Apr 5 '16 at 20:06
  • 2
    \$\begingroup\$ @DavisDude I think it is easier than what people think when they see it. The scariest part is beginning. Once you're in, you're in. \$\endgroup\$ – FliiFe Apr 5 '16 at 20:16
  • 1
    \$\begingroup\$ It's fairly easy, imho, because of how much the debug mode helps you. The docs are also pretty good, and explain what you need to know. \$\endgroup\$ – Ven Apr 5 '16 at 20:17
  • \$\begingroup\$ Just for reference, I wound up with one more using ._ and some other stuff, but it's waaay slower for big inputs: jjLkf!s.e%ib10hk._T.PUT \$\endgroup\$ – FryAmTheEggman Apr 5 '16 at 21:11
3
\$\begingroup\$

MATL, 30 bytes

4Y2Z^!"@Sd@!U10G:q^/kPG:\~h?@!

Try it online!

It's very slow. For input 3 it takes a few seconds in the online compiler. To see the numbers appearing one by one, include a D at the end of the code.

Explanation

4Y2       % predefined literal: string '0123456789'
Z^        % implicit input. Cartesian power: 2D char array. Each number is a row
!         % transpose
"         % for each column
  @       %   push current column
  Sd      %   sort and compute consecutive differences (*)
  @!U     %   push current column. Convert to number
  10G:q^  %   array [1 10 100 ... 10^(n-1)], where n is the input
  /k      %   divide element-wise. Round down
  P       %   reverse array
  G:      %   array [1 2 ... n]
  \~      %   modulo operation, element-wise. Negate: gives 1 if divisible (**)
  h       %   concatenate (*) and (**). Truthy if all elements are nonzero
  ?       %   if so
    @!    %     current number as a row array of char (string)
          %   implicitly end if
          % implicitly end if
          % implicitly display stack contents
\$\endgroup\$
  • \$\begingroup\$ Something is wrong with your code; It stops producing output for me after 5, and with 5 the last number (the only one I've bothered to check) is incorrect. 986 is not divisible by 3 \$\endgroup\$ – DavisDude Apr 5 '16 at 20:04
  • \$\begingroup\$ Update: for 2 it skips 10, 12, 32, 34, 54, 56, 76, 78 \$\endgroup\$ – DavisDude Apr 5 '16 at 20:09
  • \$\begingroup\$ I think you misunderstood the prompt. Looking at 3 I can see you have a couple indications (e.g. 026). Also an explanation would be appreciated \$\endgroup\$ – DavisDude Apr 5 '16 at 20:20
  • \$\begingroup\$ This still doesn't work- 3 skips 021, 024, etc. The first correct number is 063. \$\endgroup\$ – DavisDude Apr 5 '16 at 20:25
  • \$\begingroup\$ @DavisDude Edited, now that I read the challenge more carefully \$\endgroup\$ – Luis Mendo Apr 5 '16 at 21:29
1
\$\begingroup\$

Ruby, 87 bytes

Basic recursive solution.

f=->n,x="",j=1{j>n ?puts(x):([*?0..?9]-x.chars).map{|i|f[n,x+i,j+1]if((x+i).to_i)%j<1}}

If you're allowed to return a list of the permutations instead of printing, 85 bytes:

f=->n,x="",j=1{j>n ?x:([*?0..?9]-x.chars).map{|i|f[n,x+i,j+1]if((x+i).to_i)%j<1}-[p]}
\$\endgroup\$
1
\$\begingroup\$

Python, 132 bytes

lambda n:[x for x in map(("{:0%s}"%n).format,(range(10**n)))if all(int(x[:i])%i<1and len(set(x))==len(x)for i in range(1,len(x)+1))]

Dropped 26 bytes by getting rid of itertools, thanks to Sp3000 for making me realize I shouldn't be using it.

Dropped 2 bytes by using a list comprehension rather than filter, thanks again to Sp3000 for the tip.

Try it online: Python 2, Python 3

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