Find a Similar Number

Question

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 code-golf, 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

Answer 1

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.

Answer 2

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()

Answer 3

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)

Answer 4

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!

Answer 5

W, 14 bytes

Port of the 10-byte 05AB1E answer.

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

Uncompressed:

 oFU_:kkT-zrZ:a=-

Answer 6

Charcoal, 24 19 bytes

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

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
         Ｌ          Length of matches
  ⁻                 Subtract from the `8` or `9`
                    Implicitly print

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

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

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

≔⌈Φχ¬№θＩιη

Find the highest digit not present in the input number.

⎇⁼η⁹⌈θＩ⊕η

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.

⪫⪪θ...Ｉη

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

Answer 7

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!

Answer 8

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!

Answer 9

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.

Answer 10

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).

Answer 11

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