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
Improve this question
\$\endgroup\$
10
  • 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\$ Commented Apr 8, 2020 at 7:25
  • \$\begingroup\$ Sorry, I'll keep that in mind next time. Thanks. @Bubbler \$\endgroup\$ Commented Apr 8, 2020 at 7:27
  • 2
    \$\begingroup\$ Related: Imitate an ordering \$\endgroup\$ Commented Apr 8, 2020 at 8:42
  • \$\begingroup\$ The sample is updated, python tester for sample, check if you're not sure of definition \$\endgroup\$ Commented Apr 8, 2020 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\$ Commented Apr 8, 2020 at 10:54

11 Answers 11

Reset to default
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\$
10
  • 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\$ Commented Apr 8, 2020 at 9:50
  • 2
    \$\begingroup\$ Fixed, but at the cost of 9 bytes. Thanks for pointing this out! \$\endgroup\$ Commented Apr 8, 2020 at 10:17
  • 3
    \$\begingroup\$ @SurculoseSputum Glad you managed to fix it. And your approach inspired a -6 golf on my own answer. :) \$\endgroup\$ Commented Apr 8, 2020 at 10:21
  • 3
    \$\begingroup\$ Shorter sorted indexing: TIO. Also more testing. \$\endgroup\$ Commented Apr 8, 2020 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\$ Commented Apr 8, 2020 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\$
3
  • \$\begingroup\$ I guess your code is not working on input 191? \$\endgroup\$ Commented Apr 8, 2020 at 8:34
  • \$\begingroup\$ @newbie Thanks for reporting this. Now fixed. I think 191 should be added to the test cases. \$\endgroup\$ Commented Apr 8, 2020 at 8:46
  • \$\begingroup\$ Good idea, added. Updated sample tester too. @Arnauld \$\endgroup\$ Commented Apr 8, 2020 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\$
7
  • 1
    \$\begingroup\$ I got an incomplete idea over here. If you can complete it it'd be great. \$\endgroup\$ Commented Apr 8, 2020 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\$ Commented Apr 8, 2020 at 9:39
  • \$\begingroup\$ @petStorm 16 bytes actually: ∞IK.Δ‚εSæ2ùÆ.±}Ë (test suite). \$\endgroup\$ Commented Apr 8, 2020 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\$ Commented Apr 8, 2020 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\$ Commented Apr 8, 2020 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\$
2
  • \$\begingroup\$ Nice Galen. What resources have you been using for learning K? \$\endgroup\$ Commented Apr 9, 2020 at 11:29
  • 2
    \$\begingroup\$ @Jonah Mostly oK. Also you can always chat in th k-tree room \$\endgroup\$ Commented Apr 9, 2020 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

⭆θ⁻⁺⁸¬№θ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.

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\$
4
  • 1
    \$\begingroup\$ Nice! 0<<./ -> 0&e. for 22 bytes ? \$\endgroup\$ Commented Apr 9, 2020 at 7:01
  • 2
    \$\begingroup\$ Sorry for not checking it. I'm glad you fixed it! \$\endgroup\$ Commented Apr 9, 2020 at 11:33
  • \$\begingroup\$ 9-9&e.+\:~@~.i.] \$\endgroup\$ Commented Apr 11, 2020 at 6:11
  • \$\begingroup\$ Impressive! Thanks for finding this. Something about it was bugging me. Now I know why. \$\endgroup\$ Commented Apr 11, 2020 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\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.