# Find a Similar Number

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

• 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. – Bubbler Apr 8 at 7:25
• Sorry, I'll keep that in mind next time. Thanks. @Bubbler – newbie Apr 8 at 7:27
• Related: Imitate an ordering – xnor Apr 8 at 8:42
• The sample is updated, python tester for sample, check if you're not sure of definition – newbie Apr 8 at 8:50
• I'm a bit confused about the second condition (the comparison results) when at leas one of m or n is 1. – mappo Apr 8 at 10:54

# 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


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

• 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. – Kevin Cruijssen Apr 8 at 9:50
• Fixed, but at the cost of 9 bytes. Thanks for pointing this out! – Surculose Sputum Apr 8 at 10:17
• @SurculoseSputum Glad you managed to fix it. And your approach inspired a -6 golf on my own answer. :) – Kevin Cruijssen Apr 8 at 10:21
• Shorter sorted indexing: TIO. Also more testing. – xnor Apr 8 at 10:39
• The 1st and 6th leftmost digits (1-indexed) are 54 vs 44, which doesn't satisfy the requirement (4<5 iff 4<4). – Surculose Sputum Apr 8 at 21:47

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

• I guess your code is not working on input 191? – newbie Apr 8 at 8:34
• @newbie Thanks for reporting this. Now fixed. I think 191 should be added to the test cases. – Arnauld Apr 8 at 8:46
• Good idea, added. Updated sample tester too. @Arnauld – newbie Apr 8 at 8:50

# 05AB1E, 2016 10 bytes

êRāTα:DIQ-


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

I/O as a list of digits.

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)

• I got an incomplete idea over here. If you can complete it it'd be great. – user92069 Apr 8 at 9:34
• @petStorm Ah, nice approach with the powerset. :) Here is a possible way to fix it for 17 bytes: ∞IK.Δ‚εæ2ùε.S}}Ë (test suite). – Kevin Cruijssen Apr 8 at 9:39
• @petStorm 16 bytes actually: ∞IK.Δ‚εSæ2ùÆ.±}Ë (test suite). – Kevin Cruijssen Apr 8 at 9:41
• To make it clear: I won't accept answers not passing the samples in decent time. But still, well done :) – newbie Apr 8 at 9:49
• @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. – Kevin Cruijssen Apr 8 at 10:09

# 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!

• Nice Galen. What resources have you been using for learning K? – Jonah Apr 9 at 11:29
• @Jonah Mostly oK. Also you can always chat in th k-tree room – Galen Ivanov Apr 9 at 11:37

# W, 14 bytes

Port of the 10-byte 05AB1E answer.

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


Uncompressed:

 oFU_:kkT-zrZ:a=-


# 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 9s
¬              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.

# 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!

# Wolfram Language (Mathematica), 79 bytes

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


Try it online!

# J, 2924 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.

• – Galen Ivanov Apr 9 at 7:01
• Sorry for not checking it. I'm glad you fixed it! – Galen Ivanov Apr 9 at 11:33
• 9-9&e.+\:~@~.i.] – FrownyFrog Apr 11 at 6:11
• Impressive! Thanks for finding this. Something about it was bugging me. Now I know why. – Jonah Apr 11 at 13:01

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

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`