24
\$\begingroup\$

We consider two integers to be similar if, when written in decimal, have the same length, and if we compare characters in any two positions for both decimal strings, the comparison results (less, equal or greater) must be the same in both strings.

Formally, for two number that can be written as decimal strings \$a_1a_2\cdots a_n\$, \$b_1b_2\cdots b_m\$, they're similar if and only if \$n=m\$ and \$a_i<a_j\ \leftrightarrow b_i<b_j\$ (\$\leftrightarrow\$ means if and only if) for all \$ i,j \in [1,n]\$.

For example, 2131 and 8090 are similar. 1234 and 1111, 1234 and 4321 are not similar.

The challenge

For a given positive integer, find a different non-negative integer similar to it. You can assume at least one such integer exists.

  • Your implementation shouldn't be too inefficient. It must be at least able to pass the samples in around one hour on an average computer. (If it doesn't end in a few seconds, consider providing a screenshot running it)

  • Your code can take the input and output as integers, strings or lists of digits. Standard loopholes are forbidden.

Since this is a , the shortest code in bytes wins!

Examples

It's (quite) possible to have different outputs on these inputs as long as inputs and outputs are different and similar.

1 - 0
3 - 9
9 - 1
19 - 23
191 - 121
1111 - 2222 (0 is not considered valid)
2020 - 9393
2842 - 1321
97892 - 31230
113582 - 113452
444615491 - 666807690
87654321000 - 98765432111
98765432111 - 87654321000
526704219279 - 536714329379
99887766553210 - 88776655443210

Sample inputs as a list:

1,3,9,19,191,1111,2020,2842,97892,113582,444615491,87654321000,98765432111,526704219279,99887766553210
\$\endgroup\$
  • 14
    \$\begingroup\$ Looks like you posted the challenge only 4 hours after you posted it to the sandbox. It's way too short to get a meaningful feedback. It is recommended to keep it in the sandbox for at least 3 days. \$\endgroup\$ – Bubbler Apr 8 at 7:25
  • \$\begingroup\$ Sorry, I'll keep that in mind next time. Thanks. @Bubbler \$\endgroup\$ – newbie Apr 8 at 7:27
  • 2
    \$\begingroup\$ Related: Imitate an ordering \$\endgroup\$ – xnor Apr 8 at 8:42
  • \$\begingroup\$ The sample is updated, python tester for sample, check if you're not sure of definition \$\endgroup\$ – newbie Apr 8 at 8:50
  • \$\begingroup\$ I'm a bit confused about the second condition (the comparison results) when at leas one of m or n is 1. \$\endgroup\$ – mappo Apr 8 at 10:54

11 Answers 11

15
\$\begingroup\$

Python 3, 58 52 bytes

lambda n:[9-(9in n)-sum(x>d for x in{*n})for d in n]

Try it online!

Input: The number n, as a list of digits.
Output: A similar number, as a list of digits.

-6 bytes thanks to @xnor!

How:
Reverses the list of unique digits, then maps them to 9,8,7,... or 8,7,6,... depending on whether n contains the digit 9 or not. For example:

               | n = 1827 | n = 7899
Reverse unique |   8721   |   987
Maps to        |   9876   |   876
Results        | m = 6978 | m = 6788

Old solution

Python 3, 80 bytes

f=lambda n,i=9:(i in n)^(i-1in n)and[[d,d^i^~-i][i-2<d<=i]for d in n]or f(n,i-1)

Try it online!

Input: The number n, as a list of digits.
Output: A similar number, as a list of digits.

-1 byte thanks to @KevinCruijssen!

How
The solution tries to find a pair of consecutive digits \$(i-1,i)\$ such that one digit appears in \$n\$, and the other doesn't. It then replaces all occurrences of one digit with the other.
The pair of digits are searched from \$(8,9)\$ downward, in order to discourage replacing 1 with 0.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I like your 50-byter, but I'm afraid it's incorrect for n=9 and n=98765432111. You're supposed to find a different number. \$\endgroup\$ – Kevin Cruijssen Apr 8 at 9:50
  • 2
    \$\begingroup\$ Fixed, but at the cost of 9 bytes. Thanks for pointing this out! \$\endgroup\$ – Surculose Sputum Apr 8 at 10:17
  • 3
    \$\begingroup\$ @SurculoseSputum Glad you managed to fix it. And your approach inspired a -6 golf on my own answer. :) \$\endgroup\$ – Kevin Cruijssen Apr 8 at 10:21
  • 3
    \$\begingroup\$ Shorter sorted indexing: TIO. Also more testing. \$\endgroup\$ – xnor Apr 8 at 10:39
  • 1
    \$\begingroup\$ The 1st and 6th leftmost digits (1-indexed) are 54 vs 44, which doesn't satisfy the requirement (4<5 iff 4<4). \$\endgroup\$ – Surculose Sputum Apr 8 at 21:47
9
\$\begingroup\$

JavaScript (ES6), 55 bytes

I/O format: list of digits.

a=>a.map(d=>d-=-!/9/.test(a)|!a.includes(d-=d>(a<'2')))

Try it online!

Commented

a =>                // a[] = input array of digits
  a.map(d =>        // for each digit d in a[]:
    d -=            //   update d:
      -!/9/.test(a) //     if a[] doesn't include any 9, increment d
      |             //     (this does d = d - (-1 | whatever) = d - (-1) = d + 1)
                    //     otherwise, decrement d if:
      !a.includes(  //     - a[] does not include d - 1
        d -= d >    //     - and d is greater than 0 if the leading digit is not 1,
          (a < '2') //       or greater than 1 otherwise (so that it doesn't result
      )             //       in a leading zero)
  )                 // end of map()
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I guess your code is not working on input 191? \$\endgroup\$ – newbie Apr 8 at 8:34
  • \$\begingroup\$ @newbie Thanks for reporting this. Now fixed. I think 191 should be added to the test cases. \$\endgroup\$ – Arnauld Apr 8 at 8:46
  • \$\begingroup\$ Good idea, added. Updated sample tester too. @Arnauld \$\endgroup\$ – newbie Apr 8 at 8:50
6
\$\begingroup\$

05AB1E, 20 16 10 bytes

êRāTα:DIQ-

-6 bytes after being inspired by @SurculoseSputum partially incorrect approach.

I/O as a list of digits.

Try it online or verify all test cases.

Explanation:

ê          # Sort and uniquify the digits in the (implicit) input-list
           #  i.e. [2,8,4,2] → [2,4,8]
 R         # And reverse it
           #  → [8,4,2]
  ā        # Push a list in the range [1, length] (without popping)
           #  → [1,2,3]
   Tα      # Take the absolute difference with 10
           #  → [9,8,7]
     :     # Replace in the (implicit) input-list the sorted unique digits with [9,8,...]
           #  → [7,9,8,7]
      D    # Duplicate it
       IQ  # Check whether it's equal to the input-list (1 if truthy; 0 if falsey)
           #  → 0 (falsey)
         - # Subtract that from each digit
           #  → [7,9,8,7]
           # (after which the resulting list is output implicitly)

Original 20 16 bytes approach:

∞IK.Δ‚εSæ2ùÆ.±}Ë

-4 bytes thanks to @petStorm.

I/O as regular integers.

Try it online or verify the smaller test cases (larger ones time out).

Explanation:

∞              # Push an infinite list of positive integers: [1,2,3,...]
 IK            # Remove the input-integer itself from the list
.Δ             # Then find the first value in this list which is truthy for:
  ‚            #  Pair the current value with the (implicit) input-integer
               #   i.e. input=2842 and y=1321 → [2842,1321]
   ε           #  Map both to:
    S          #   Convert them to a list of digits
               #    → [[2,8,4,2],[1,3,2,1]]
     æ         #   Take the powerset of this list of digits
      2ù       #   Only leave the pairs
               #    → [[[2,8],[2,4],[2,2],[8,4],[8,2],[4,2]],
               #       [[1,3],[1,2],[1,1],[3,2],[3,1],[2,1]]]
        Æ      #   Reduce each inner pair by subtracting
               #    → [[-6,-2,0,4,6,2],
               #       [-2,-1,0,1,2,1]]
         .±    #   Take the signum of each (-1 if a<0; 0 if a==0; 1 if a>0)
               #    → [[-1,-1,0,1,1,1],
               #       [-1,-1,0,1,1,1]]
           }Ë  #  After the inner map: check if the pair of lists are the same
               #   → 1 (truthy)
               # (after we've found our value, it is output implicitly as result)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I got an incomplete idea over here. If you can complete it it'd be great. \$\endgroup\$ – user92069 Apr 8 at 9:34
  • \$\begingroup\$ @petStorm Ah, nice approach with the powerset. :) Here is a possible way to fix it for 17 bytes: ∞IK.Δ‚εæ2ùε`.S}}Ë (test suite). \$\endgroup\$ – Kevin Cruijssen Apr 8 at 9:39
  • \$\begingroup\$ @petStorm 16 bytes actually: ∞IK.Δ‚εSæ2ùÆ.±}Ë (test suite). \$\endgroup\$ – Kevin Cruijssen Apr 8 at 9:41
  • \$\begingroup\$ To make it clear: I won't accept answers not passing the samples in decent time. But still, well done :) \$\endgroup\$ – newbie Apr 8 at 9:49
  • \$\begingroup\$ @newbie Golfed 6 bytes while making it faster at the same time. ;) Still have to check if it 100% covers all possible test cases though. If you can think of any test case where this might fail for, let me know. \$\endgroup\$ – Kevin Cruijssen Apr 8 at 10:09
4
\$\begingroup\$

K (oK), 27 bytes

{((9-9=|/x)-!#?x)(?x@>x)?x}

Try it online!

Takes the input as a list ot digits.

Inspired by Kevin Cruijssen's 05AB1E and Surculose Sputum's Python solutions - please don't forget to upvote them!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice Galen. What resources have you been using for learning K? \$\endgroup\$ – Jonah Apr 9 at 11:29
  • 2
    \$\begingroup\$ @Jonah Mostly oK. Also you can always chat in th k-tree room \$\endgroup\$ – Galen Ivanov Apr 9 at 11:37
3
\$\begingroup\$

W, 14 bytes

Port of the 10-byte 05AB1E answer.

♥f<~|J▄5sO#o═╥

Uncompressed:

 oFU_:kkT-zrZ:a=-
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 24 19 bytes

⭆θ⁻⁺⁸¬№θ9LΦγ∧›λι№θλ

Try it online! Link is to verbose version of code. Now based on @SurculoseSputum's newer answer. Explanation:

 θ                  Input as a string
⭆                   Map over characters and join
       θ            Input as a string
      № 9           Count `9`s
     ¬              Logical Not (i.e. does not contain `9`)
   ⁺⁸               Add `8`
          Φγ        Filter on printable ASCII
              λ     ASCII character
             ›      Greater than
               ι    Input character
            ∧       Logical And
                  λ ASCII character
                №θ  Occurs in input
         L          Length of matches
  ⁻                 Subtract from the `8` or `9`
                    Implicitly print

Previous 24-byte version based on @SurculoseSputum's older answer:

≔⌈Φχ¬№θIιη⪫⪪θ⎇⁼η⁹⌈θI⊕ηIη

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

≔⌈Φχ¬№θIιη

Find the highest digit not present in the input number.

⎇⁼η⁹⌈θI⊕η

If that digit is less than 9 then increment it (which will give a digit in the input number) otherwise take the highest digit of the input number.

⪫⪪θ...Iη

Replace the digit from the input number with the digit not in the input number.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Erlang (escript), 143 bytes

Port of Surculose Sputum's Python answer.

u([])->[];u([H|T])->[H]++u([A||A<-T,A/=H]).
i(X)->case X of true->1;_->0end.
f(A)->[9-i(lists:member(9,A))-lists:sum([i(X>D)||X<-u(A)])||D<-A].

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 79 bytes

Port of @SurculoseSputum answer

#/.MapThread[Rule,{a=Union@#,Range[0,9][[-Tr[1^a]-(d=Boole[Max@a>8]);;-1-d]]}]&

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

J, 29 24 16 bytes

9-9&e.+\:~@~.i.]

Try it online!

-8 thanks to FrownyFrog!

Thanks to Bubbler for catching some bugs. All are now fixed.

Inspired by Surculose's sweet answer, be sure to upvote him.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice! 0<<./ -> 0&e. for 22 bytes ? \$\endgroup\$ – Galen Ivanov Apr 9 at 7:01
  • 2
    \$\begingroup\$ Sorry for not checking it. I'm glad you fixed it! \$\endgroup\$ – Galen Ivanov Apr 9 at 11:33
  • \$\begingroup\$ 9-9&e.+\:~@~.i.] \$\endgroup\$ – FrownyFrog Apr 11 at 6:11
  • \$\begingroup\$ Impressive! Thanks for finding this. Something about it was bugging me. Now I know why. \$\endgroup\$ – Jonah Apr 11 at 13:01
1
\$\begingroup\$

Bash + Unix utilities, 77 74 bytes

tee t|tr "`rs -T|sort -ur|xargs`" "`grep -q 9 t;seq $[8+$?] -1 0|xargs`"<t

Try the test suite online!

Input is a list of integers on stdin (space-separated digits).

Output is in the same format, on stdout.

This is an implementation of Surculose Sputum's nice method: List the unique digits that appear in the input, sort them in decreasing order, and then replace them in the original input either with \$8, 7, 6, \dots\$ (if \$9\$ appears in the input) or with \$9, 8, 7, \dots\$ (if \$9\$ does not appear in the input).

| improve this answer | |
\$\endgroup\$
-1
\$\begingroup\$

This is a port of @Surculose Sputum's solution in APL2.

U←((A⍳A)=⍳⍴A)/A←,A
((9∊A)⌽⌽⍳10)[U[⍒U]⍳A]

It presupposes that A is a vector of numbers and that ⎕IO=0

| improve this answer | |
\$\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.