17
\$\begingroup\$

Given a list of positive integers such as [69, 420], your challenge is to generate the sequence of numbers that can be formed by concatenating numbers from the above set, in ascending numerical order.

For example, with [69, 420] the sequence begins:

69
420
6969
42069
69420
420420

Note that elements of the sequence should be unique.

The list will be nonempty and will not contain duplicates.

Standard rules apply.

Testcases

In list, 0-indexed number format.

[69, 420], 4 -> 69420
[32, 33, 34], 8 -> 3334
[109, 5], 7 -> 10955
[2, 22, 222], 4 -> 22222
\$\endgroup\$
4
  • \$\begingroup\$ I presume we don't have to handle the list being empty? \$\endgroup\$
    – pxeger
    Jun 7 at 15:37
  • \$\begingroup\$ May we assume the list will contain no duplicates? \$\endgroup\$
    – pajonk
    Jun 7 at 18:46
  • \$\begingroup\$ @pajonk Yes. (filler) \$\endgroup\$
    – emanresu A
    Jun 7 at 20:03
  • \$\begingroup\$ @pxeger No, you don't. \$\endgroup\$
    – emanresu A
    Jun 7 at 20:03

15 Answers 15

11
\$\begingroup\$

Python, 71 bytes (-3 thanks to @pxeger)

def f(A):
 o=A
 while o:=o-{x:=min(o,key=int)}|{x+i for i in A}:yield x

Attempt This Online!

This takes a set of strings as its input.

Old Python, 77 bytes

def f(A):
 o=A
 while o:O,*o=sorted({*o},key=int);yield O;o+=map(O.__add__,A)

Attempt This Online!

A generator that walks through the sequence.

How does it work?

It maintains a list/set which always contains (or has yielded) all the concatenations of all numbers output so far with all numbers in the input list. At each iteration it yields the smallest element and adds its concatenations with the input list.

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

JavaScript (V8), 60 bytes

Prints the sequence forever.

a=>{for(k=0;;)(++k+'').match(`^(${a.join`|`})+$`)&&print(k)}

Try it online!

How?

We turn the list of integers into a regular expression:

[69, 420] ~~> /^(69|420)+$/

And we use it to identify the positive integers that belong to the sequence.

\$\endgroup\$
7
\$\begingroup\$

Zsh -F, 30 bytes

seq inf|grep -xP (${(j"|")@})+

Attempt This Online!

Slow.

\$\endgroup\$
6
\$\begingroup\$

05AB1E, 7 bytes

иæJïê¹£

Given \$n\$ and the list, it outputs the first \$n\$ results.

Try it online or verify all test cases.

Explanation:

и        # Repeat the (implicit) second input-list the first (implicit)
         # input-integer amount of times as list
 æ       # Get the powerset of this list
  J      # Join each inner list together
   ï     # Cast each string to an integer
    ê    # Uniquify and sort the list
     ¹£  # Only leave the first first input amount of values
         # (after which this is output implicitly as result)

Too bad sorting builtins don't work on infinite lists, otherwise ÞæJïê would have been enough to output the infinite sequence given just an input-list.

\$\endgroup\$
6
\$\begingroup\$

Brachylog, 13 bytes

tT&j₎⊇ᵘcᵐoh↙T

Try it online!

Extremely inefficient.

This returns the first N elements, 1-indexed.

Explanation

tT               Input = [List, T]
  &j₎            Concatenate List T times to itself
     ⊇ᵘ          Find all unique subsets of this new list
       cᵐ        Map concatenate
         o       Sort
          h↙T    Return the first T elements
\$\endgroup\$
6
\$\begingroup\$

Python 2, 109 108 104 bytes

a=input();i=0
m=lambda n:n*all(n.find(p)or m(n[len(p):])for p in a)
while 1:
 if""==m(`i`):print i
 i+=1

Attempt This Online!

-1 byte thanks to Jonathan Allan


Python, 81 bytes

import re
def f(a,i=0):re.match(f'({"|".join(a)})+$',str(i))and print(i);f(a,i+1)

Attempt This Online!

Dies with the recursion limit, but works theoretically (or if you use a Python interpreter with TCO)

\$\endgroup\$
1
  • \$\begingroup\$ any((p<=n<p+'~')*m(n[len(p):])for p in a) saves a byte. \$\endgroup\$ Jun 7 at 11:55
5
\$\begingroup\$

Jelly, 8 bytes

xŒPḊVQṢḣ

A dyadic Link that accepts the list of positive integers on the left and the number of elements to get, N, on the right and yields a list of the first N concatenated integers.

Try it online! - extremely inefficient!

How?

xŒPḊVQṢḣ - Link: list of positive integers, L; positive integer, N
x        - repeat the elements of L N times each
 ŒP      - powerset
   Ḋ     - dequeue (remove the empty list)
    V    - evaluate as Jelly code (concatenates each and gives back the integer)
     Q   - deduplicate
      Ṣ  - sort
       ḣ - head -> the first N elements
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 26 bytes

≔θζFη«⊞υ⌊⁻ζυ≔⁺ζI⁺I⌈υIθζ»Iυ

Try it online! Link is to verbose version of code. Outputs the first n terms. Explanation: Based on @Albert.Lang's Python answer.

≔θζ

Start with the input list.

Fη«

Repeat n times.

⊞υ⌊⁻ζυ

Save the minimum value not collected so far.

≔⁺ζI⁺I⌈υIθζ

Append all the concatenations of that value with the input list to the current list.

»Iυ

Output the collected terms.

\$\endgroup\$
3
\$\begingroup\$

Retina, 62 bytes

~(T`,`|
(\d+).(.+)
K`0¶$1{`.+¶$$.($*__¶/^($2)+$/^+`.+¶$$.($*__

Try it online! Takes n as the first input in the list and outputs the 1-indexed nth term. Explanation: Similar approach to @Arnauld's JavaScript answer.

T`,`|

Change the commas into |s.

(\d+).(.+)

Match the first number and the remaining numbers separately.

K`0¶$1{`.+¶$$.($*__¶/^($2)+$/^+`.+¶$$.($*__

Create a Retina program with them substituted in.

~(`

Evaluate that program.

For example, with the inputs 5,69,420 the following Retina program is created:

K`0

Set the current value to 0.

5{`

Repeat 5 times.

.+
$.(*__

Increment the current value.

/^(69|420)+$/^+`

Repeat while the current value isn't a concatenation of 69s and 420s...

.+
$.(*__

... increment the current value.

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 9 bytes

ẋfṗvṅ⌊sUi

Try it Online!

Port of the Jelly answer. Yields a list of the first N concatenated integers.

Explained (outdated - will fix soon)

ẋfṗvṅ⌊sUi
ẋf        # Repeat the input list N times
  ṗ       # take the powerset of that list
   vṅ⌊    # Concatenate each sublist into a single integer
      sUi # and get the Nth item in the sorted uniquified list
\$\endgroup\$
2
3
\$\begingroup\$

Pip, 12 bytes

W1Ui~=+Xg&Pi

Try It Online! (link is to a safe version that only runs 1000 times)

-2 thanks to DLosc.

W1           # Forever
     ~=      # Check a regex match of...
        Xg   # Input regex'd
       +     # With a `+`
  Ui         # In (incrementing) i
         &Pi # If so, print i
\$\endgroup\$
1
  • \$\begingroup\$ (The code should be W1Ui~=+Xg&Pi) \$\endgroup\$
    – DLosc
    Jun 10 at 20:57
3
\$\begingroup\$

Factor + lists.lazy, 95 82 bytes

[ 0 lfrom swap "|"join "^(%s)+$"sprintf <regexp> '[ present _ matches? ] lfilter ]

Try it online!

-13 bytes from using @Arnauld's method. Takes input as a sequence of strings representing integers and returns an infinite lazy list of the sequence.

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

R, 82 bytes

function(n)repeat grepl(sprintf("^(%s)+$",paste(n,collapse="|")),F<-F+1)&&print(F)

Try it online!

Port of @Arnauld's answer.

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

BQN, 37 bytes

{𝕨⊑∧⍷•Bqn¨∾¨•Fmt¨¨1↓(⥊(↕2˘)/¨<)∾𝕨/⋈𝕩}

Try it here!

Slow enough that you'll probably need a local interpreter to run most of the cases.

2 bytes saved thanks to @Razetime!

Explanation

w is index, x is list of numbers.

  • ∾𝕨/⋈𝕩 x repeated w times
  • (⥊(↕2˘)/¨<) powerset
  • 1↓ remove empty set
  • •Bqn¨∾¨•Fmt¨¨ for each element in powerset, concatenate numbers
    • Super-slow since we're "eval"ing each string to get the number (BQN doesn't have an easy way to convert strings to numbers)
  • ∧⍷ Deduplicate and sort
  • 𝕨⊑ Get wth number
\$\endgroup\$
2
  • 1
    \$\begingroup\$ looks like this works: {𝕨⊑∧⍷•Bqn¨∾¨•Fmt¨¨1↓(⥊(↕2˘)/¨<)∾𝕨/⋈𝕩} \$\endgroup\$
    – Razetime
    Jun 17 at 16:46
  • \$\begingroup\$ @Razetime thanks! I was stumped on finding a more elegant way to dupe the list, underestimated the power of / \$\endgroup\$ Jun 17 at 18:39
1
\$\begingroup\$

Burlesque, 16 bytes

Jx/jcb)imNB><j!!

Try it online!

Takes block (L) and int (N)

J    # Duplicate N
x/j  # Make stack N,L,N
cb   # Combinations of L of length [1..N]
)im  # Concat each result
NB   # Remove duplicates
><   # Sort
j!!  # Select Nth
\$\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.