17
\$\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\$
9
  • 1
    \$\begingroup\$ is there a limit to n? \$\endgroup\$
    – FlipTack
    Commented Nov 26, 2016 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
    Commented Nov 26, 2016 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
    Commented Nov 26, 2016 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\$ Commented Nov 26, 2016 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
    Commented Nov 26, 2016 at 15:48

16 Answers 16

11
\$\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\$
2
  • \$\begingroup\$ Wow, a solution that's shorter than the Jelly solution that Dennis made! :'P \$\endgroup\$
    – hyper-neutrino
    Commented Nov 26, 2016 at 16:23
  • 3
    \$\begingroup\$ No one beats Jelly. ¶: \$\endgroup\$ Commented Nov 26, 2016 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\$
0
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\$
4
  • \$\begingroup\$ Fails for 1 (Should output [0], but RangeErrors.) \$\endgroup\$
    – Artyer
    Commented Nov 26, 2016 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\$ Commented Nov 26, 2016 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
    Commented Nov 26, 2016 at 23:50
  • \$\begingroup\$ I like how the solutions start off really short, and then suddenly jump an order of magnitude. \$\endgroup\$
    – Nissa
    Commented Nov 27, 2016 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\$
0
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\$
2
  • 1
    \$\begingroup\$ Fails for 2. The function gives {0, 1}. I believe you need Permutations[Range@#-1, #] instead of Subsets[Range@#-1]. \$\endgroup\$ Commented Nov 27, 2016 at 4:18
  • \$\begingroup\$ Gah, what a boneheaded mistake. Thank you for observing it, and for suggeting the perfect fix! \$\endgroup\$ Commented Nov 27, 2016 at 8:25
2
\$\begingroup\$

Vyxal, 7 bytes

eʁ'?τÞu

Try it Online!

 ʁ      # Range(0, 
e       # n**n
  '     # Filtered by...
   ?τ   # Convert to base n
     Þu # All unique?
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 14 13 bytes

ʁṖƛÞSƛṖ⁰vβ]fU

Try it Online!

ʁṖƛÞSƛṖ⁰vβ]fU
ʁ             # Range [0, n)
 Ṗƛ       ]   # For each permutation:
   ÞSƛ        # For each sublist in the permutation:
      Ṗ         # Generate the permutations of that
        v       # For each permutation:
         β        # Treating it as a list of digits, convert to base 10 from base
       ⁰          # <the input>
           f  # Flatten the resulting list
            U # Remove duplicates
\$\endgroup\$
1
  • \$\begingroup\$ ;; can be ] (I think) \$\endgroup\$
    – emanresu A
    Commented Nov 9, 2022 at 18:56
2
\$\begingroup\$

Haskell, 100 80 bytes

-20 bytes thanks to @Laikoni

f k=[n|n<-[0..k*k^k],let x#0=1>0;x#n|m<-mod n k=notElem m x&&(m:x)#div n k,[]#n]

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ 90 bytes by dropping x from (#) and using a list comprehension for f: Try it online! \$\endgroup\$
    – Laikoni
    Commented Nov 15, 2022 at 15:52
  • \$\begingroup\$ 88 by merging (#) with the test function x: Try it online! \$\endgroup\$
    – Laikoni
    Commented Nov 15, 2022 at 16:20
  • \$\begingroup\$ 80 bytes by putting (#) into the list comprehension where k is given from context: Try it online! \$\endgroup\$
    – Laikoni
    Commented Nov 15, 2022 at 16:24
0
\$\begingroup\$

Ruby, 73 bytes

->n,*a{i=-1
n>1?(0..n**n).filter_map{i+=1
d=i.digits(n)
i if d==d&d}:[0]}

Attempt This Online!

\$\endgroup\$
0
\$\begingroup\$

Japt, 14 bytes

o à cá mìU â ñ

Try it

Explanation:

o à cá mìU â ñ
o              # Get the range [0...input]
  à            # Find all arrays containing unique items from that range
    cá         # Find all orderings for each of those arrays
       m       # For each one:
         U     #  Treat it as an array of base-input digits
        ì      #  Convert it to a base-10 number
           â   # Remove duplicates
             ñ # Sort by ascending value

This alternative and this other alternative are longer, but seems like that strategy could become shorter if someone finds a better way to check for "contains no duplicate elements".

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 8 bytes

mÝʒIвDÙQ

Try it online or verify all test cases.

Explanation:

m         # Push the (implicit) input to the power of the (implicit) input: nⁿ
 Ý        # Pop and push a list in the range [0,nⁿ]
  ʒ       # Filter this list by:
   Iв     #  Convert the integer to base-input as list
     DÙQ  #  Check if all items in this list are unique:
     D    #   Duplicate the list
      Ù   #   Uniquify the items in the copy
       Q  #   Check if the two lists are still the same
          # (after which the result is output implicitly)

† Note: input \$n=1\$ will output as [0,1] instead of [0]. This could be fixed in +1 byte by adding a ¨ after the Ý, to make the range \$[0,n^n)\$ instead. However, I'd argue for \$n=1\$ it should be allowed to output either [0] or [0,1]. If base-1 follows the same rules as the other bases, only 0 can be represented, making it practically useless. Because of that, bijective base-1 (aka unary) is usually used instead when someone talks about base-1, in which case:

  1. \$n=0\$ as bijective base-1 will have an empty result (technically all unique)
  2. \$n=1\$ as bijective base-1 results in a single tally mark (thus all unique)
  3. \$n\geq2\$ as bijective base-1 results in \$n\$ amount of tally mark (thus not all unique)
\$\endgroup\$
0
\$\begingroup\$

Japt, 13 10 bytes

pU ÇìU'âÃâ

Try it

pU ÇìU'âÃâ     :Implicit input of integer U
pU             :Raised to the power of itself
   Ç           :Map the range [0,U**U)
    ìU         :  Convert to base U digit array
      'â       :  Deduplicate and convert back to integer
        Ã      :End map
         â     :Deduplicate
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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