12
\$\begingroup\$

Challenge

Given a list of bases for positional numeral systems as input, output the lowest positive integer that when represented in those bases they have no common digits. The input list can be assumed to have two or more unique positive integers >= 2.

Example

For the input list of bases 2, 8, 10, 16 (binary, octal, decimal and hexadecimal) the lowest number is 58 (a printed result should be in decimal) since 58 is 111010, 72, 58 and 3A which, as you can see, have no common digits between them. And no positive integer less than 58 have that property. Whereas 57 is 111001, 71, 57 and 39 for the same bases and here the digit 1 appears in more than one base, in base 2 and base 8, so 57 cannot be the result for 2,8,10,16. (Also digit 7 appears in two of them).

Tests

2 8 10 16          → 58
2 8 10             → 27
2 8 16             → 43
16 17 18           → 160
16 17 18 19        → 224
16 17 18 19 21     → 225
34 35 36           → 646
4 44 444 4444      → 512
3 33 333 3333 4444 → 16702
555 777 999        → 1665
111 222 333        → 555

Some valid inputs have no solution, as pointed out by @Nitrodon, or none that can be found within reasonable time (one minute at TIO/Try It Online). I'll leave it up to each contributor to chose if or how they want to handle such inputs.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'd suggest making it explicit that the input will always be positive integers greater than or equal to 2, and that there will be no duplicates \$\endgroup\$ Commented Jan 12, 2022 at 16:36
  • \$\begingroup\$ @cairdcoinheringaahing - Edited that now. \$\endgroup\$
    – Kjetil S
    Commented Jan 12, 2022 at 20:08
  • 6
    \$\begingroup\$ Some sets of bases have no solution (such as 2 3 4 5). What should happen in those cases? \$\endgroup\$
    – Nitrodon
    Commented Jan 12, 2022 at 21:41
  • \$\begingroup\$ @Nitrodon – I'll leave it up to each contributor to chose if or how they want to handle such inputs of which no solution can be found within reasonable time or at all. \$\endgroup\$
    – Kjetil S
    Commented Jan 13, 2022 at 13:03

14 Answers 14

6
\$\begingroup\$

R, 96 bytes

Or R>=4.1, 82 bytes by replacing two function occurrences with \s.

function(b){while(any(table(unlist(Map(function(y)unique(T%/%y^(0:log(T,y))%%y),b)))>1))T=T+1
T}

Try it online!

Similar approach to @Giuseppe's, but independently developed (and shorter).

\$\endgroup\$
4
\$\begingroup\$

Pyth, 10 bytes

f{Is{MjLTQ

Test suite

Explanation:
f{Is{MjLTQ | Full code
-----------+-----------------------------------------------------------------------
f          | Find the first integer T (starting with 1) such that
      jLTQ |  the list of T converted to each base in the input as a list of digits
    {M     |  with each sublist deduplicated
   s       |  flattened
 {I        |  is invariant over deduplication
\$\endgroup\$
4
\$\begingroup\$

Husk, 12 11 bytes

ḟȯS=uṁuMB⁰N

Try it online!

ḟ         N  # get ḟirst Natural number that satisfies:
       M ⁰   #  Map over the input:
        B    #   get lists of digits in these Bases;
     ṁ       #  now ṁap over each list & flatten result:
      u      #   get unique digits;
  S=         #  is this list equal to 
    u        #   the unique elements of itSelf?  

(Or alternative 11 byte program: VS=umṁuṪ`BN:)

       Ṫ`    # make a Ṫable of:
         B   #  the digits in the bases of the input
          N  #  for each of the infinite list of Natural numbers;
   m         # now map over each list of lists of digits
    ṁ        #  and ṁap over each list of digits, flattening the result,
     u       #   getting just the unique digits;
V            # finally, return the index of the first list that satisfies:
 S=          #  it's equal to 
   u         #   the unique elements of itself?  
\$\endgroup\$
2
  • \$\begingroup\$ ṁu can be Σ \$\endgroup\$
    – Razetime
    Commented Jan 13, 2022 at 4:04
  • \$\begingroup\$ @Razetime - Unfortunately Σ does not remove the duplicates from each list before concatenating (it's ṁI), so I don't think it'll work here... \$\endgroup\$ Commented Jan 13, 2022 at 11:01
3
\$\begingroup\$

Jelly, 10 bytes

1bQ€FQƑʋ1#

Try it online!

How it works

1bQ€FQƑʋ1# - Main link. Takes a list of integers L on the left
       ʋ   - Group the previous 4 links into a dyad f(k, L):
 b         -   Convert k into each base in L
  Q€       -   For each list of digits, remove duplicates
    F      -   Flatten
     QƑ    -   Are all elements in this list unique?
1       1# - Count up from n = 1, 2, ... until the first n is found such that f(n, L) is truthy
\$\endgroup\$
5
  • \$\begingroup\$ Can you use œ&/? \$\endgroup\$
    – pxeger
    Commented Jan 12, 2022 at 17:23
  • \$\begingroup\$ @pxeger No, because the intersection doesn't reduce like that. If you have [[1,0], [2, 0], [5]], œ&/ will give [] (as the [0] œ& [5], the last reduction, is []) \$\endgroup\$ Commented Jan 12, 2022 at 17:25
  • \$\begingroup\$ Ah. How about œ&Ɲ? \$\endgroup\$
    – pxeger
    Commented Jan 12, 2022 at 17:28
  • \$\begingroup\$ @pxeger That would fail if the base lists had something like [[1,0], [2,3], [4,1]] as [1,0] œ& [4,1] would never be run \$\endgroup\$ Commented Jan 12, 2022 at 17:29
  • \$\begingroup\$ Damn, this is trickier than I thought! \$\endgroup\$
    – pxeger
    Commented Jan 12, 2022 at 17:30
3
\$\begingroup\$

Ruby, 54 bytes

->a{(1..).find{|i|!a.flat_map{i.digits(_1)|[]}.uniq!}}

Try it online! (with modifications to work on older versions)

\$\endgroup\$
2
  • \$\begingroup\$ @Natte and AZTECCO – Replace 9999 with for example 2e4 for the 16702 result test to work. And also save a byte. \$\endgroup\$
    – Kjetil S
    Commented Jan 13, 2022 at 13:11
  • 1
    \$\begingroup\$ the code on tio is not meant to be the solution, only a representation of my solution that works on tio's outdated ruby version \$\endgroup\$
    – Natte
    Commented Jan 13, 2022 at 13:18
3
\$\begingroup\$

R, 105 bytes

function(b){while(anyDuplicated(unlist(lapply(b,function(B,x)unique(x%/%B^(0:log(x,B))%%B),F<-F+1))))0
F}

Try it online!

Ugly and appears altogether too long. Outgolfed by pajonk.

\$\endgroup\$
3
  • \$\begingroup\$ Too long indeed ;-) Independently developed, but similar in nature: 96 bytes. \$\endgroup\$
    – pajonk
    Commented Jan 12, 2022 at 20:03
  • 1
    \$\begingroup\$ @pajonk I think you should post that yourself. I need to start remembering to use Map every time I start thinking about lapply... \$\endgroup\$
    – Giuseppe
    Commented Jan 12, 2022 at 20:24
  • \$\begingroup\$ Thanks, posted. Yes, Map is something I learned by being consistently reminded of its existence by @Dominic. \$\endgroup\$
    – pajonk
    Commented Jan 12, 2022 at 20:30
2
\$\begingroup\$

Charcoal, 28 bytes

≔²ηW⊙Eθ↨ηκ⊙θ∧⁻λν⁻κ⁻κ↨ημ≦⊕ηIη

Try it online! Link is to verbose version of code. Explanation:

≔²η

Start searching at 2 since 1 will have the same digit in all bases.

W⊙Eθ↨ηκ⊙θ∧⁻λν⁻κ⁻κ↨ημ

Convert the search value to all bases, then perform set intersection between all of the sets, and repeat until they are all empty (except for self-intersection of course). (Strictly speaking each set intersection repeats one of the base conversions but that's code golf for you.)

≦⊕η

Increment the search value.

Iη

Output the final search value.

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

JavaScript (Node.js), 86 bytes

Expects a list of BigInts.

f=(a,n=2n)=>a.some(c=>a.some(b=>c-b&&(g=k=>k&&1n<<k%b|g(k/b))(n)&g(n,b=c)))?f(a,-~n):n

Try it online!

How?

The helper function \$g\$ is used to build a bitmask of all digits appearing in the representation of \$k\$ in base \$b\$ :

g = k => k && 1n << k % b | g(k / b)

The main function \$f\$ recursively looks for the smallest \$n\ge2\$ for which there's no pair \$(b,c)\$ from the input array such that \$b\neq c\$ and the bitmaks generated by \$g(n)\$ in base \$b\$ and \$c\$ have at least one bit in common.

f = (a, n = 2n) =>
a.some(c =>
  a.some(b =>
    c - b &&
    g(n) & g(n, b = c)
  )
) ?
  f(a, -~n)
:
  n
\$\endgroup\$
2
\$\begingroup\$

Burlesque, 25 bytes

{bcqdgZ])NB\[U_}j1iar1jfe

Try it online!

{
 bc  # Box and cycle infinitely
 qdg # boxed Digits
 Z]  # Zip and evaluate (get list of digits of N in bases Input) 
 )NB # Map Nub (remove duplicates within each set of digits)
 \[  # Concatenate all digits
 U_  # Digits are unique
}
j    # Reorder stack
1ia  # Insert bases at position 1 (as the second argument of zip)
r1   # Range [1..inf)
j    # Reorder stack
fe   # Find the first element (in infinite range) which fulfils requirements

A shorter variant would be where bcqdgZ] is simply replaced with the convert base function B!

Burlesque, 19 bytes

{B!)NB\[U_}j+]r1jfe

Try it online!

Unfortunately, this fails for larger bases due to limitations on rendering the digits as strings

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

Julia 1.0, 67 bytes

x\b=digits(x;base=b)
<(l,x=1)=((a=x.\l).∩a'.>[[]])l>l ? l<x+1 : x

Try it online!

Explanation:

  • digits gives the digits of a number in a certain base, eg digits(9,base=8) == [1,1]
  • we rename digits to \ to allow broadcasting over the base: 10 .\ [3,4] == [[1,0,1], [2,2]]
  • a .∩ a' is the intersect function: every list of digits is compared to all the others, the output is a matrix of lists
  • (...) .> [[]] checks which elements of the matrix are empty, the output is a bitmatrix, where 0 means the list is empty (no common digits). The diagonal will always have 1s
  • (...)*l > l will be true is there is any 1 outside of the diagonal
  • l<x+1 iterates recursively to the next number
\$\endgroup\$
1
\$\begingroup\$

Apl 37 bytes

a←⎕
1∘+⍣{{⍬≡∊⍵/⍨⍤1≠/¨⍳⍴⍵}∘.∩⍨⍺⊥⍣¯1⍨¨a}0

1∘+⍣{...}0 adds 1 until the function returns true

⍺⊥⍣¯1⍨¨a converts ⍺ to bases of a(input array)

∘.∩⍨ returns a matrix checking if numbers present in one base are present in another base

⍵/⍨⍤1≠/¨⍳⍴⍵ removes the diagonal (as it is compared to itself)

⍬≡∊ checks if every argument is empty

\$\endgroup\$
1
\$\begingroup\$

Ruby, 80 bytes

f=->l,n=1{a=l.map(&g=->b,x=n{x<1?[]:[x%b]|g[b,x/b]}).flatten
a|a==a ?n:f[l,n+1]}

Try it online!

f=->l,n=1{..}    recursive lambda taking a list and trying next number until a solution is found
a=l.map          map bases to:
&g=->b,x=n{        recursive base digits(as array of integer numbers)
..%b]|g[b..        we use | to add only new digits 
.flatten         finally we flatten to get all digits found
a|a==a           if by removing duplicates the array doesn't change we return the number
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 11 bytes

∞.Δsв€Ù˜DÙQ

Try it online or verify all test cases.

Explanation:

∞.Δ          # Find the first positive integer which is truthy for:
   Iв        #  Convert it to each of the input-bases as list of lists
     €Ù      #  Uniquify each inner list
       ˜     #  Flatten it
        DÙQ  #  Check if all values are unique:
        D    #   Duplicate the list
         Ù   #   Uniquify the copy
          Q  #   Check if the two lists are still the same
             # (after which the result is output implicitly)
\$\endgroup\$
1
\$\begingroup\$

Python 3, 139 bytes

def e(n,b):
 while n:
  yield n%b;n//=b
def f(a):
 n=1
 while 1:
  if all(sum(q in e(n,b)for b in a)<2 for q in range(n+1)):return n
  n+=1

Try it online!

It's annoying for it not to be a single expression, but those seemed to end up longer.

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