8
\$\begingroup\$

Input

An integer n in the range 100 to 10^18 and an integer k in the range 1 to 18, inclusive.

The swap operation

A swap chooses two digits at different positions and exchanges their positions, as long as the swap does not result in a leading zero. For example if we start with the integer 12345 we can perform one swap to make it 12543.

Task

Output the largest number you can get after exactly k swaps.

Examples

n = 1283, k = 2. Output: 8312 n = 510, k = 1. Output: 501 n = 501, k = 2. Output: 501 n = 999, k = 3. Output: 999 n = 12345678987654321, k = 1. Output: 92345678187654321
Improve this question
\$\endgroup\$
18
  • 9
    \$\begingroup\$ What is it with these [code-golf] + [restricted-time] challenges lately.. They are complete opposites imho. Anyway, as for the actual challenge, if we are to output huge test cases with k=18 and n between \$10^{17}\$ and \$10^{18}\$ within 10 seconds, you may want to add some test cases for those. \$\endgroup\$ Commented May 1, 2019 at 8:16
  • 2
    \$\begingroup\$ @KevinCruijssen It's a combination I really like :) Basically the challenge is to write compact code that is not too naive/brute force. I will try to add some more test cases.If anyone comes up with any first, please post them in the comments and I will add them to the question. \$\endgroup\$ Commented May 1, 2019 at 8:19
  • 3
    \$\begingroup\$ Also, a test case where k is larger than the length of n would be good as well, since we have to do exactly k swaps instead of up to k swaps. Can't really think of a good test case for this, but I think we might need to do an inefficient swap first sometimes in order to get to the maximum in exactly k swaps. \$\endgroup\$ Commented May 1, 2019 at 8:19
  • 1
    \$\begingroup\$ Can we take input n as a list of digits? \$\endgroup\$ Commented May 1, 2019 at 12:45
  • 3
    \$\begingroup\$ @MagicOctopusUrn Not necessary, since n=501, k=2 would become 510 in the first iteration, but then should be swapped back to 501 as our result. \$\endgroup\$ Commented May 1, 2019 at 20:08

5 Answers 5

Reset to default
5
\$\begingroup\$

Python 3, 194 190 196 193 175 164 162 bytes

def f(n,k): for i in range(len(n)-1): y=max(n[i:]);j=n[::-1].index(y) if(y>n[i])*k:n[i],n[~j]=y,n[i];k-=1 if len(n)-len({*n})<k%2:n[-2:]=n[:-3:-1] return n

Try it online!

Pretty tough to golf this challenge in a real world language - I like it :)

After golfing down to 190 bytes (and below..), I found some cases where the algorithm would not find the maximum possible value. Bugfixing forced me back up to 196 193 bytes :/

... then I found some ways to better handle branching on k and went down below 180 :)

After the comment from Chas Brown, switching from integer to list I/O saved 28 bytes! (And more golfing another 2..)

Then, another bug: the algorithm incorrectly handles remaining swaps, if there are equal digits present. The fix cost 19 bytes.

Algorithm:

  1. For each digit, starting from the leftmost one, swap it with the rightmost maximum digit, if that one is bigger. First line of the for-loop finds the maximum and its index. Second line does the swap.
  2. If there are k' swaps left, swap two equal digits, or the two rightmost k' times. I.e. if there are two equal digits present, or if k' is even, no more swaps have to be done. Else, just swap the last two digits once.
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ The bug I needed to fix: f(899,1)=989, but should be 998. If there are multiple candidates to swap, use the rightmost one for the biggest effect. This is now taken care of by looking for the index in reverse. Takes up a lot of bytes for index calculation though :/ \$\endgroup\$ Commented May 1, 2019 at 20:44
  • 1
    \$\begingroup\$ Hi and welcome, movatica! For the input 9881,1 you return 9818; but you should return 9881. (Also, you can take n as a string of digits already, and return a list of digits as well; as noted in the comments; so that should give you some breathing space! :)). \$\endgroup\$ Commented May 1, 2019 at 21:18
  • \$\begingroup\$ Hi @ChasBrown and thanx for the warm welcome :) You're right about the bug, this is because of how i handle possible swaps... I'm thinking of a way around. The removal of string/list handling will indeed save a lot of bytes. \$\endgroup\$ Commented May 1, 2019 at 21:43
  • 1
    \$\begingroup\$ 162 bytes by tweaking that last if clause a bit: len(n)-len({*n}) must be 0 and k%2 must be 1, which is the condition len(n)-len({*n})<k%2. \$\endgroup\$ Commented May 1, 2019 at 22:53
3
\$\begingroup\$

Jelly, 16 bytes

JŒ!nJ$S⁼ɗƇ2ị⁸Ṁµ¡

Try it online!

A dyadic Link accepting a list of digits (as non-negative integers) on the left and a non-negative integer on the right which yields a list of digits.

How?

JŒ!nJ$S⁼ɗƇ2ị⁸Ṁµ¡ - Link: L, n µ¡ - repeat the monad to the left n times -- i.e. f(f(f(...(L)...))): J - range of length Œ! - all permutations Ƈ - filter keep if: ɗ 2 - last three links as a dyad with right argument 2 $ - last two links as a monad: J - range of length n - not equal? (vectorises) S - sum ⁼ - equal? ị - index into (vectorises): ⁸ - chain's left argument, L Ṁ - maximum

20 byte version which is fine within the previous time-constraint since \$\binom{18}2=\frac{18\times 17}2=153\$

JŒcœṖḢ;Ḣ€ṚżƊƊFɗ€⁸Ṁµ¡

Try it online!

How?

JŒcœṖḢ;Ḣ€ṚżƊƊFɗ€⁸Ṁµ¡ - Link: L, n µ¡ - repeat the monad to the left n times -- i.e. f(f(f(...(L)...))): J - range of length Œc - all (length(L)-choose-2) pairs: [[1,2],[1,3],[1,4],...,[2,3],[2,4],...] € - for each (such pair, P): ɗ ⁸ - last three links as a dyad, with right argument L: œṖ - partition (L) at indexes (P) - call this X Ɗ - last three links as a monad - i.e. f(X): Ḣ - head (of X) (the items up to but not including the first to swap) Ɗ - last three links as a monad - i.e. f(X): Ḣ€ - head each (actually removes them too) (the items to swap) Ṛ - reverse ż - zip with (the altered X) ; - concatenate F - flatten Ṁ - maximum
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python 2, 185 177 173 166 164 161 152 bytes

def f(a,k):exec"i=0;j=L=len(a)-1\nwhile i<L>0<a[i]==max(a[i:]):i+=1\nwhile a[j]<max(a[i:]):j-=1\nj-=i==j<=L<len(set(a));a[i],a[j]=a[j],a[i];"*k;return a

Try it online!

Takes a list of digits and an integer k; returns a list of digits.

j-=i==j<=L<len(set(a))

uses a bunch of shortcuts, and is the same as:

if i==j: # if i==j, then the list is already sorted if len(a)-1<len(set(a)): # since len(a)>=len(set(a)) is *always* True, # this means len(a)==len(set(a), i.e, # a has no duplicated digits, j = i-1 # so do a swap with the rightmost digits
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 2, 113 bytes

f=lambda l,k,E=enumerate:l*0**k or f(max(l[:i]+[y]+l[i+1:j]+[x]+l[j+1:]for(i,x)in E(l)for j,y in E(l)if i<j),k-1)

Try it online!

Greedily does the best swap at each step, found by testing all possible swaps and taking the maximum.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 162 bytes

$f={param($s,$k)if($k--){$s=if($s.length-le2){&$f($s[1]+$s[0])$k}else{($m=($s|% t*y|sort)[-1])+(&$f(($s-replace"(?<!$m.*)$m",$s[0])|% s*g 1)($k+=$s[0]-eq$m))}}$s}

Try it online!

The Recursive Function. Less golfed:

$f={ param($s,$k) if($k--){ $s=if($s.length-le2){ &$f ($s[1]+$s[0]) $k } else{ $max=($s|% t*y|sort)[-1] $k+=$s[0]-eq$max $s=$s-replace"(?<!$max.*)$max",$s[0] $s=$s|% subString 1 $max+(&$f $s $k) } } $s }

Alternative, 169 bytes

param($s,$k)1..$k|%{do{if($s.length-le2){$s=-join$s[1,0] $r=0}else{$m+=($c=($s|% t*y|sort)[-1]) $r=$s[0]-eq$c $s=($s-replace"(?<!$c.*)$c",$s[0])|% s*g 1}}while($r)}$m+$s
Improve this answer
\$\endgroup\$