21
\$\begingroup\$

Inspired by the problem with the same name on Puzzling SE by our very own Dmitry Kamenetsky.

You are to find the largest number that only uses every digit pair once, in a given base. For example, in ternary we have 2212011002.

Challenge: Given a base from 2-10, output the largest number in that base with no repeating digit pairs.

As long as the digits make the number, you may output with anything, or nothing, in between. Whether regularly delimited, or irregularly gibberished.

You may also take input in any reasonable way. For example, you might take the base, the max digit, or an ordered list representing the digits available. For octal, this would mean 8, 7 or 76543210. If you feel like a challenge, you can take octal as input. I won't complain!

Note that it need only work for bases from 2-10. Invisible points for doing alphanumeric bases like hex, but not at all required.

This is , so least bytes per language wins.

Test Cases

Decimal: 10
99897969594939291908878685848382818077675747372717066564636261605545352515044342414033231302212011009


Octal: 8
77675747372717066564636261605545352515044342414033231302212011007


Quaternary: 4
33231302212011003


Ternary: 3
2212011002


Binary: 2
11001

Edit: It used to be required for bases 1-10, with the desired output for unary being 00. However, that was just an obfuscating edge case in some cases when people wanted to manipulate natural numbers. So unary has been dropped; only bases 2-10 required.

\$\endgroup\$
9
  • 4
    \$\begingroup\$ Thanks for using the sandbox, but you definitely need to leave your posts there for a lot longer than 36 minutes. 3-5 days is about right. \$\endgroup\$ – pxeger Jun 16 at 19:53
  • \$\begingroup\$ @pxeger I know, haha. The intention wasn't to sandbox it. I'm confident with this one. I just wanted to post it publicly so I could ask a question about it in TNB. \$\endgroup\$ – AviFS Jun 16 at 19:58
  • 1
    \$\begingroup\$ Just as a friendly reminder, there's no obligation to write a comment on each and every answer to your challenge. :-) This is actually discouraged. (Unless of course there's a good reason to.) \$\endgroup\$ – Arnauld Jun 16 at 21:02
  • \$\begingroup\$ @Arnauld I was meaning to ask about that in meta. It feels like a nice thing to do, so long as it’s only one person doing it (the question poster). But then again, I know that’s not the purpose of comments. And I know chattiness is discouraged there. \$\endgroup\$ – AviFS Jun 16 at 21:09
  • 1
    \$\begingroup\$ @DmitryKamenetsky Oh, no way! Thank you. I meant to comment on your puzzling post to let you know, but I forget. And I didn't think you had an account here, or I'd have mentioned you. I'll credit you rn! As for hexadecimal, it's a shame to miss it, but I decided that worrying about alphanumeric bases would complicate it needlessly. I wasn't totally sure, but we discussed it in TNB here. \$\endgroup\$ – AviFS Jun 17 at 3:48

16 Answers 16

7
\$\begingroup\$

Jelly,  8  7 bytes

-1 thanks to Neil (avoid a reverse by reordering to flatten first.)

Żj)ŻFṚ;

A monadic Link accepting the maximal digit (e.g. 7 for octal) that yields the digits as a list of integers.

Try it online!

How?

Note that if x is the base then the least significant (rightmost) digit of f(x) is x-1, the previous digits are the same as all but the last digit of f(x-1) and the digits before that are:
[x-1, x-1, x-2, x-1, x-3, x-1, x-4, x-1, ..., 0], so...

Żj)ŻFṚ; - Link: non-negative integer, M (max digit = base - 1)
  )     - for each (x in [1..M]):
Ż       -   zero-range    -> [0,1,2,3,...,x]
 j      -   join (x)      -> [0,x,1,x,2,x,3,x,...,x]
   Ż    - prepend a zero  -> [0,[0,1,1],[0,2,1,2,2],[0,3,1,3,2,3,3],...]
    F   - flatten         -> [0,0,1,1,0,2,1,2,2,0,3,1,3,2,3,3,...]
     Ṛ  - reverse         -> [...,3,3,2,3,1,3,0,2,2,1,2,0,1,1,0,0]
      ; - concatenate (M) -> [...,3,3,2,3,1,3,0,2,2,1,2,0,1,1,0,0,M]
\$\endgroup\$
3
  • \$\begingroup\$ Why not Żj)ŻFṚ;? \$\endgroup\$ – Neil Jun 16 at 23:47
  • \$\begingroup\$ Didn't think of that golf, thanks! \$\endgroup\$ – Jonathan Allan Jun 16 at 23:52
  • 2
    \$\begingroup\$ No, thank you for explaining it so well that I could understand it well enough to golf it! \$\endgroup\$ – Neil Jun 16 at 23:54
6
\$\begingroup\$

R, 61 52 51 bytes

Edit: -9 bytes, and then -1 more byte, thanks to Robin Ryder

for(i in 1:scan())F=c(i,rbind(i,i:1-1),F);c(F,F[1])

Try it online!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Nice use of rbind. Surely n=scan();for(i in 1:n)F=c(i,rbind(i,i:1-1),F);c(F,n) would be equivalent and shorter? \$\endgroup\$ – Robin Ryder Jun 16 at 21:50
  • \$\begingroup\$ @RobinRyder - You're right, of course. My code was embarassingly wasteful. Do you want to post that? \$\endgroup\$ – Dominic van Essen Jun 16 at 21:53
  • \$\begingroup\$ No, go ahead, thanks! I was working on a solution with paste, but your strategy is better. \$\endgroup\$ – Robin Ryder Jun 16 at 21:54
  • \$\begingroup\$ 51 bytes \$\endgroup\$ – Robin Ryder Jun 17 at 7:27
  • \$\begingroup\$ @RobinRyder - Very nice: thanks again! \$\endgroup\$ – Dominic van Essen Jun 17 at 9:21
5
\$\begingroup\$

JavaScript (ES6), 55 bytes

n=>(g=p=>p--?p+(h=q=>q--?[p]+q+h(q):'')(p)+g(p):~-n)(n)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Nice, the third person to post and the first worst language! \$\endgroup\$ – AviFS Jun 16 at 20:37
  • 6
    \$\begingroup\$ the [p]+q+... trick is really nice, instead of ''+p+q+.... \$\endgroup\$ – EliteDaMyth Jun 16 at 20:39
5
\$\begingroup\$

Japt, 14 11 bytes

Çò qZìÔ+´U
Ç           // Exclusive range [0..U) where U is the input, mapped to
 ò          // inclusive range [0..Z] of each item Z
   qZ       // joined together by Z.
     Ã¬Ô    // Join and reverse the result, then
        +´U // append input minus one.

Try it here.

\$\endgroup\$
3
  • \$\begingroup\$ Nice. The first rarer-ish language! \$\endgroup\$ – AviFS Jun 16 at 20:38
  • \$\begingroup\$ @AviFS Japt is fun, but tends to be a bit verbose. I think these days it's mostly just me and Shaggy who regularly use it. \$\endgroup\$ – Etheryte Jun 16 at 20:58
  • 1
    \$\begingroup\$ @AviFS, Japt is one of the most used golfing languages on the site. Admittedly, the majority of that is me, though! \$\endgroup\$ – Shaggy Jun 17 at 16:49
3
\$\begingroup\$

Jelly, 12 bytes

,€`€j0ṚF;Ø0;

Try it online!

Takes base - 1 for input, so 7 for octal. Does not work for unary, as permitted.

,€`€j0ṚF;Ø0;  Main Link
   €          For each x from 1 to N
  `           Apply the following to (x, x) rather than (x, N):
 €            - For each y from 1 to x
,             - (y, x)
    j0        Join the list of sublists of pairs on 0
      Ṛ       Reverse the whole thing
       F      Flatten
        ;Ø0   Append 2 zeroes
           ;  Append the input
\$\endgroup\$
3
\$\begingroup\$

Jelly, 11 bytes

;€`Ṛ)ŻṚj0F;

Try it online!

A monadic link taking the max digit and returning a list of digits. Works for unary as well.

Explanation

    )       | For each digit from 1 up to the argument:
;€`         | - Concatenate each digit from 1 to that digit together
   Ṛ        | - Reverse
     Ż      | Prepend zero
      Ṛ     | Reverse
       j0   | Join with zeros
         F  | Flatten
          ; | Concatenate to original argument
\$\endgroup\$
3
\$\begingroup\$

Ruby, 56 53 bytes

->n{(?0..n="#{n}").map{|m|[*?0..m]*m}.join.reverse+n}

Try it online!

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

Vyxal, 16 bytes

ʁ?²›↔'₌ḢṪZ:U⁼;tṅ

Try it Online!

Sorry about that. I wayyyy misinterpreted the question.

Explanation:
ʁ?²›↔'₌ḢṪZ:U⁼;tṅ    # main program

ʁ                   # range 0 to n-1
 ?²›                # base^2 + 1
    ↔               # combination w/ replacement
     '₌ḢṪZ:U⁼;      # filter lambda
      ₌ḢṪ           # a[1:], a[:-1]
         Z          # zip
          :U⁼       # check if the zip is unique
              tṅ    # tail joined by ""          

This is really slow, so it will only finish for n <= 3 probably, but it works in theory.

\$\endgroup\$
3
  • \$\begingroup\$ Second answer, shortest answer, and first answer in a weird lang. No offense Lyxal :p \$\endgroup\$ – AviFS Jun 16 at 20:14
  • \$\begingroup\$ This doesn't work - 3 should output 2212011002 \$\endgroup\$ – caird coinheringaahing Jun 16 at 20:16
  • \$\begingroup\$ @cairdcoinheringaahing oops, I misinterpreted the question. Give me a sec to fix \$\endgroup\$ – Underslash Jun 16 at 20:20
2
\$\begingroup\$

Charcoal, 13 bytes

⮌⁺⊖θ⭆N⪫…·⁰ιIι

Try it online! Link is to verbose version of code. Takes b as input. Works for b=1. Explanation:

     N          Input `b`
    ⭆           Map over implicit range and join
       …·⁰ι     Inclusive range from 0 to current index
      ⪫         Joined with
            ι   Current index
           I    Cast to string
 ⁺              Prefixed with
   θ            Input `b`
  ⊖             Decremented
⮌               Reverse
                Implicitly print
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 51 bytes

.+
$*
1
$`¶
¶$

1
$.%_

$.%`
^(.*¶)*
$#1$&
¶

O$^`.

Try it online! Link includes test suite that generates results for b=1..10. Explanation:

.+
$*

Convert to unary.

1
$`¶

List the values from 0 to b-1 (in unary).

¶$

Delete the trailing newline that the previous stage generates.

1
$.%_

Replace each 1 with its line number, so now we have a triangle of digits where there are n digits n on each line.


$.%`

Intersperse the digits from 0 to n around the existing digits n.

^(.*¶)*
$#1$&

Insert an extra digit b-1 at the beginning.

Join everything together.

O$^`.

Reverse the string.

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

Husk, 15 13 11 bytes

Edit: -2 bytes thanks to Razetime

↔:¹ṁSoJ←ŀḣ→

Try it online!

↔:¹ṁSoJ←ŀḣ→ # Full program:
   ṁS       # map across
         ḣ→ # each integer n from 1 to input plus 1:
        ŀ   # integers from zero to n,
     oJ←    # joined-together using n plus 1;
 :¹         # then, prefix this with the input,
↔           # and reverse it all.
\$\endgroup\$
2
  • \$\begingroup\$ 11 bytes \$\endgroup\$ – Razetime Jun 17 at 7:13
  • \$\begingroup\$ @Razetime - Thanks! I kind-of knew that there must be a nicer solution using S out there, but just couldn't find it. Very slick. \$\endgroup\$ – Dominic van Essen Jun 17 at 9:06
2
\$\begingroup\$

Python 3, 52 bytes

f=lambda a,*b:(b and a+a+a.join(b)+f(*b)[:-1]or a)+a

Try it online!

  • Take as inputs each individual available digits in descending order.

  • Bonus: Base 0 works perfectly fine, so does other bases like Hexadecimal (as long you provide the digits available)

How it works:

Let say your digits are "43210", the expcted result should be 4(4)3(4)2(4)1(4)0__3(3)2(3)1(3)0__2(2)1(2)0__1(1)0__0__[4]

  • We can see that each segent contains the numbers up to a certain point separated by the leading number.
  • These segments repeat in decending order
  • The first number is added at the end

From that I construct the recursive program :

  • f=lambda a,*b:: definition of the function, each individual digit in descending order. Store the first in a and the other in b
  • b and ... or a if the digits is just "0", b is empty and the expression will be equal to "0", else it will be equal to ...
  • a+a+a.join(x)+f(b)[:-1], return the string of the available digits separated by the first element (a), then recurse over the available digits the first element. Then remove the last digit of it.
  • return(...)+a add the first element of x to the result. The previous [::-1] is to remove this char from the recursive call but not from the main call.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thanks for the explanation under How It Works, that's a great visual! I now finally understand how half of the programs work. And congrats on the invisible points!! \$\endgroup\$ – AviFS Jun 18 at 11:02
2
\$\begingroup\$

Python 3, 97 bytes

def f(x):
	k=[]
	for i in range(x,0,-1):k+=sum([[i-j,i]for j in range(i)],[])+[0]
	return k+[0,x]

Try it online!

fixed thanks to Jakque

Takes base - 1 for input, so 7 for octal. Does not work for unary, as permitted.

\$\endgroup\$
3
  • \$\begingroup\$ First (and longest) answer goes to hyper. Congrats! \$\endgroup\$ – AviFS Jun 16 at 20:10
  • \$\begingroup\$ It doesn't seems the code returns the largest number. Shouldn't the 3rd line of code be for i in range(x,0,-1):k+=sum([[i-j,i]for j in range(i)],[])+[0] instead? \$\endgroup\$ – Jakque Jun 18 at 11:20
  • \$\begingroup\$ @Jakque yeah, not sure how I missed that... \$\endgroup\$ – hyper-neutrino Jun 18 at 19:11
1
\$\begingroup\$

05AB1E, 13 10 bytes

-10 thanks to ovs.

ÝεÝy.ý}˜Rš

Try it online! Takes input as the maximum digit in the base, and outputs as a strangely arranged list of numbers - this is allowed, since

As long as the digits make the number

it is valid.

ÝεÝy.ý}˜Rš  # full program
         š  # prepend...
        R   # reversed...
       ˜    # flattened...
Ý           # [0, 1, 2, ...,
            # ..., implicit input...
Ý           # ]...
 ε          # with each element replaced by...
  Ý         # [0, 1, 2, ...,
            # (implicit) ..., current element in map...
  Ý         # ]...
    .ý      # joined by...
   y        # current element in map...
         š  # to...
            # implicit input
      }     # exit map
            # implicit output
\$\endgroup\$
4
  • \$\begingroup\$ DÝRs -> ÝRy for -1. \$\endgroup\$ – ovs Jun 17 at 5:59
  • \$\begingroup\$ 10 bytes \$\endgroup\$ – ovs Jun 17 at 6:03
  • 1
    \$\begingroup\$ I'm so glad you abused "as long as the digits make the number." I was hoping someone would and was looking forward to seeing what people would come up with. The nested lists & strings at the end don't disappoint! \$\endgroup\$ – AviFS Jun 17 at 7:31
  • \$\begingroup\$ @ovs Thank you! \$\endgroup\$ – Makonede Jun 17 at 20:57
1
\$\begingroup\$

Pip, 15 bytes

@ORV:0\,_J_MJ,a

Try it online!

Explanation

We construct (most of) the number backwards and then reverse it:

                                                      Current value         Output
              a  The base, given via command-line     3
             ,   Range(^)                             [0 1 2]
           MJ    Map this function...
     0\,_          Inclusive-range(0, arg)            [[0] [0 1] [0 1 2]]
         J_        joined on arg                      [0 011 02122]
                 ... and join the results as string   001102122
  RV:            Reverse                              221201100
 O               Output without a newline             221201100             221201100
@                Get the first character              2                     221201100
                 (Autoprint)                                                2212011002
\$\endgroup\$
1
\$\begingroup\$

Acc!!, 100 bytes

N-48
Count i while _+1-i {
Count j while _-i-j {
Write _-i-j+48
Write _-i+48
}
Write 48
}
Write _+48

Takes input as (base - 1). Try it online!

Explanation

N-48                     # Input a digit and store its value in the accumulator
Count i while (_+1)-i {  # Loop i from 0 through (acc + 1) - 1
                         #   acc - i is the recurring digit in this block
Count j while (_-i)-j {  # Loop j from 0 through (acc - i) - 1
                         #   acc - i - j is the changing digit in this block
Write (_-i-j)+48         # Write the changing digit
Write (_-i)+48           # Write the recurring digit
}
Write 48                 # End the block with a 0
}
Write _+48               # End the number with a final digit of (base - 1)
\$\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.