Maximizing by swapping

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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