15
\$\begingroup\$

Introduction

A xenodrome in base n is an integer where all of its digits in base n are different. Here are some OEIS sequences of xenodromes.

For example, in base 16, FACE, 42 and FEDCBA9876543210 are some xenodromes (Which are 64206, 66 and 18364758544493064720 in base 10), but 11 and DEFACED are not.

Challenge

Given an input base, n, output out all xenodromes for that base in base 10.

The output should be in order of least to greatest. It should be clear where a term in the sequence ends and a new one begins (e.g. [0, 1, 2] is clear where 012 is not.)

n will be an integer greater than 0.

Clarifications

This challenge does IO specifically in base 10 to avoid handling integers and their base as strings. The challenge is in abstractly handling any base. As such, I am adding this additional rule:

Integers cannot be stored as strings in a base other than base 10.

Your program should be able to theoretically handle reasonably high n if there were no time, memory, precision or other technical restrictions in the implementation of a language.

This is , so the shortest program, in bytes, wins.

Example Input and Output

1  # Input
0  # Output
2
0, 1, 2
3
0, 1, 2, 3, 5, 6, 7, 11, 15, 19, 21
4
0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 18, 19, 24, 27, 28, 30, 33, 35, 36, 39, 44, 45, 49, 50, 52, 54, 56, 57, 75, 78, 99, 108, 114, 120, 135, 141, 147, 156, 177, 180, 198, 201, 210, 216, 225, 228
\$\endgroup\$
  • 1
    \$\begingroup\$ is there a limit to n? \$\endgroup\$ – FlipTack Nov 26 '16 at 14:02
  • \$\begingroup\$ @Flp.Tkc No. It should be able to handle reasonably high n. I don't want the challenge to be limited by how high a base the builtin base conversion of a language can handle. \$\endgroup\$ – Artyer Nov 26 '16 at 14:26
  • \$\begingroup\$ @Artyer That should have been part of the challenge text, then. It seems some answers are already doing that \$\endgroup\$ – Luis Mendo Nov 26 '16 at 14:38
  • \$\begingroup\$ I know the base conversion in Pyth can handle values larger that 36, but since this wants all of the xenodromes, the underlying python breaks when the list gets too large, saying it can't fit a value in a ssize_t. Is it breaking in this way acceptable? \$\endgroup\$ – FryAmTheEggman Nov 26 '16 at 14:43
  • 2
    \$\begingroup\$ Somebody seems to have downvoted all answers that cannot handle larger bases because of a built-in precision limit, which also seems like an implementation rather than an algorithm problem. Could you clarify? \$\endgroup\$ – Dennis Nov 26 '16 at 15:48
10
\$\begingroup\$

Pyth, 8 bytes

f{IjTQU^

Filters the numbers in [0, n^n - 1] on having no duplicate elements in base n. The base conversion in Pyth will work with any base, but since this looks at a very quickly increasing list of numbers, it will eventually be unable to store the values in memory.

Try it online!

Explanation:

f{IjTQU^QQ    - Auto-fill variables
      U^QQ    - [0, n^n-1]
f             - keep only those that ...
 {I           - do not change when deduplicated
   jTQ        - are converted into base n
\$\endgroup\$
  • \$\begingroup\$ Wow, a solution that's shorter than the Jelly solution that Dennis made! :'P \$\endgroup\$ – HyperNeutrino Nov 26 '16 at 16:23
  • 3
    \$\begingroup\$ No one beats Jelly. ¶: \$\endgroup\$ – Roman Gräf Nov 26 '16 at 17:40
5
\$\begingroup\$

Python 2, 87 bytes

n=input()
for x in range(n**n):
 s={n};a=x
 while{a%n}|s>s:s|={a%n};a/=n
 print-~-a*`x`

Prints extra blank lines for non-xenodromes:

golf % python2.7 xenodromes.py <<<3
0
1
2
3

5
6
7



11



15



19

21
\$\endgroup\$
5
\$\begingroup\$

Jelly, 9 8 bytes

ð*ḶbQ€Qḅ

Thanks to @JonathanAllan for golfing off 1 byte!

Try it online! or verify all test cases.

How it works

ð*ḶbQ€Qḅ  Main link. Argument: n

ð         Make the chain dyadic, setting both left and right argument to n.
          This prevents us from having to reference n explicitly in the chain.
 *        Compute nⁿ.
  Ḷ       Unlength; yield A := [0, ..., nⁿ - 1].
   b      Convert each k in A to base n.
    Q€    Unique each; remove duplicate digits.
      Q   Unique; remove duplicate digit lists.
       ḅ  Convert each digit list from base n to integer.
\$\endgroup\$
4
\$\begingroup\$

Jelly, 12 bytes

*`ḶbµQ⁼$Ðfḅ³

TryItOnline!

Will work for any n, given enough memory, Jelly's base conversion is not restrictive.

How?

*`ḶbµQ⁼$Ðfḅ³ - Main link: n
    µ        - monadic chain separation
*            - exponentiation with
 `           - repeated argument, i.e. n^n
  Ḷ          - lowered range, i.e. [0,1,2,...,n^n-1]
   b         - covert to base n (vectorises)
        Ðf   - filter keep:
       $     -     last two links as a monad
     Q       -         unique elements
      ⁼      -         equals input (no vectorisation)
           ³ - first program argument (n)
          ḅ  - convert from base (vectorises)
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES7), 86 bytes

n=>{a=[];for(i=n**n;i--;j||a.unshift(i))for(j=i,b=0;(b^=f=1<<j%n)&f;j=j/n|0);return a}
\$\endgroup\$
  • \$\begingroup\$ Fails for 1 (Should output [0], but RangeErrors.) \$\endgroup\$ – Artyer Nov 26 '16 at 14:49
  • \$\begingroup\$ Exactly what I had, but this would theoretically fail for 37 if precision weren't an issue, which I think makes it invalid... \$\endgroup\$ – ETHproductions Nov 26 '16 at 14:59
  • \$\begingroup\$ @Artyer I've ported my Batch version, so now this will work for n from 1 to 13 before floating-point precision kills it. \$\endgroup\$ – Neil Nov 26 '16 at 23:50
  • \$\begingroup\$ I like how the solutions start off really short, and then suddenly jump an order of magnitude. \$\endgroup\$ – Nissa Nov 27 '16 at 0:24
2
\$\begingroup\$

Perl 6, 47 bytes

{(0..$_**$_).grep: !*.polymod($_ xx*).repeated}

Returns a Seq. ( Seq is a basic Iterable wrapper for Iterators )

With an input of 16 it takes 20 seconds to calculate the 53905th element of the Seq (87887).

Expanded:

{       # bare block lambda with implicit parameter 「$_」

  ( 0 .. ($_ ** $_) )    # Range of values to be tested

  .grep:                 # return only those values

    !\                   # Where the following isn't true
    *\                   # the value
    .polymod( $_ xx * )  # when put into the base being tested
    .repeated            # has repeated values
  }
}
\$\endgroup\$
2
\$\begingroup\$

Batch, 204 200 bytes

@set/an=%1,m=1
@for /l %%i in (1,1,%1)do @set/am*=n
@for /l %%i in (0,1,%m%)do @set/ab=0,j=i=%%i&call:l
@exit/b
:l
@set/a"f&=b^=f=1<<j%%n,j/=n"
@if %f%==0 exit/b
@if %j% gtr 0 goto l
@echo %i%

Won't work for n > 9 because Batch only has 32-bit arithmetic. Conveniently, Batch evaluates f &= b ^= f = 1 << j % n as f = 1 << j % n, b = b ^ f, f = f & b rather than f = f & (b = b ^ (f = 1 << j % n)).

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

Mathematica, 59 48 bytes

Select[Range[#^#]-1,xMax[x~DigitCount~#]==1]&

Contains U+F4A1 "Private Use" character

Explanation

Range[#^#]-1

Generate {1, 2, ..., n^n}. Subtract 1. (yields {0, 1, ..., n^n - 1})

xMax[x~DigitCount~#]==1

A Boolean function: True if each digit occurs at most once in base n.

Select[ ... ]

From the list {0, 1, ..., n^n - 1}, select ones that give True when the above Boolean function is applied.

59 byte version

Select[Range[#^#]-1,xDuplicateFreeQ[x~IntegerDigits~#]]&
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 48 55 bytes

Union[(x   x~FromDigits~#)/@Permutations[Range@#-1,#]]&

(The triple space between the xs needs to be replaced by the 3-byte character \uF4A1 to make the code work.)

Unnamed function of a single argument. Rather than testing integers for xenodromicity, it simply generates all possible permutations of subsets of the allowed digits (which automatically avoids repetition) and converts the corresponding integers to base 10. Each xenodrome is generated twice, both with and without a leading 0; Union removes the duplicates and sorts the list to boot.

\$\endgroup\$
  • 1
    \$\begingroup\$ Fails for 2. The function gives {0, 1}. I believe you need Permutations[Range@#-1, #] instead of Subsets[Range@#-1]. \$\endgroup\$ – JungHwan Min Nov 27 '16 at 4:18
  • \$\begingroup\$ Gah, what a boneheaded mistake. Thank you for observing it, and for suggeting the perfect fix! \$\endgroup\$ – Greg Martin Nov 27 '16 at 8:25

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.