Polyglot Maxxie and Minnie

In Dyalog APL it’s easier to define a swap function; the @ operator takes a function (reverse) so s here performs a swap. The outer product is super handy for finding all the combinations of x and y: x ∘., y.

maxmin←{
  ⎕IO←1  ⍝ so that x[1] is subset not x[0]
  n←⍎¨⍕⍵  ⍝ convert int to vec 
  s←{⌽@⍵⊢⍺}  ⍝ swap two elements
  swaps←{n s ⍵}  ⍝ apply swaps to a vec n
  opts←,(⍳≢n)∘.,⍳≢n ⍝ combinations of 1..n
  new←swaps¨opts  ⍝ perform the swaps
  keep←(~0=⊃¨new)/new  ⍝ filter out values starting with 0
  (⌈/,⌊/)10⊥¨keep  ⍝ max and min of ints
}

     maxmin 213 

312 123

     maxmin 12345 

52341 12345

     maxmin 100 

100 100

     maxmin 11321

31121 11123

I’m quite pleased with this solution; performing a map is as simple as using each (¨) and performing both max and min concatenated together with a fork ((⌈/,⌊/)) is just so aesthetic. Conversion from a vector of numbers to a single number uses a base-10 decode (10⊥) which is how one might need to do that in other languages, but with a loop.

If I was to take some liberties with what one calls a ‘line’, I could say that this is a 1-line solution

maxmin←{⎕IO←1 ⋄ n←⍎¨⍕⍵ ⋄ s←{⌽@⍵⊢⍺} ⋄ swaps←{n s ⍵} ⋄ opts←,(⍳≢n)∘.,⍳≢n ⋄ new←swaps¨opts ⋄ keep←(~0=⊃¨new)/new ⋄ (⌈/,⌊/)10⊥¨keep }

You can try this out yourself at tryapl.org (tryapl.org)

In Julia the swap function can use destructuring which is nice, but since the language uses pass-by-reference semantics, I need to make a copy of the vector being swapped, otherwise I’ll just keep swapping it over and over. Note: this recent post of mine.

using Combinatorics

function swap(x, i, j)
  y = copy(x)
  y[i], y[j] = y[j], y[i]
  y
end

function maxmin(x)
    nvec = parse.(Int64, split(string(x), ""))
    opts = collect(combinations(1:length(nvec), 2))
    new = [[nvec]; map(x -> swap(nvec, x...), opts)]
    keep = filter(x -> x[1] != 0, new)
    vals = parse.(Int64, join.(keep))
    (maximum(vals), minimum(vals))
end

maxmin(213)

(312, 123)

maxmin(12345)

(52341, 12345)  

maxmin(100)

(100, 100)  

maxmin(11321)

(31121, 11123)    

The part I probably had the most trouble with here was concatenating together the original vector with its swapped versions; it looks clean now, but figuring out how to get those all into the same vector-of-vectors took me a while.

The splatting of opts variants in the map was nice; no need to define the swap in terms of a tuple. Overall, this is a very clean solution, in my opinion - Julia really does make for a lovely language.

Continuing my Haskell-learning journey, I figured it would be best to have a go at this. As a heavily functional language, one doesn’t do a lot of defining of variables, instead one writes a lot of functions which will pass data around. This makes it a bit tricky for testing, but I got there eventually. I did have to borrow the swapElts function, and nub was a new one for me (essentially unique()).

import Data.List
import Data.Digits

uniq_pairs l = nub [(x,y) | x <- l, y <- l, x < y]
opts n = uniq_pairs [0..n-1]
-- https://gist.github.com/ijt/2010183
swapElts i j ls = [get k x | (k, x) <- zip [0..length ls - 1] ls]
    where get k x | k == i = ls !! j
                  | k == j = ls !! i
                  | otherwise = x
doswap t v = swapElts (fst t) (snd t) v
newlist v = v : map (\x ->  doswap x v) (opts (length v))
keep v = filter (\x -> (head x /= 0)) (newlist v)
maxmin n = (maximum(x), minimum(x)) where 
  x = map (unDigits 10) (keep (digits 10 n))

maxmin 213

(312,123)

maxmin 12345

(52341,12345)

maxmin 100

(100,100)

maxmin 11321

(31121,11123)

The Data.Digits package was very helpful here - having digits and unDigits, though if I was going to use these more I would have curried the required base 10 into something like digits10 and unDigits10.

There are likely improvements to be made here, and I’m interested in any you can spot!

“Everyone” uses it, so I gotta learn it… is what I keep telling myself. I’m no stranger to the quirks of different languages, but every time I try to do something functional in python I end up angry that the print method for generators shows the memory address instead of, say, the first few elements. Printing a value and seeing <map at 0x7fb928d4a2c0> gets me every. single. time. Yes, yes, list(value) “collects” it, but grrr…

Python has the destructuring syntax which is nice in the swap function, but again it’s pass-by-reference so I need to make a copy first.

import itertools

def swap(x, t):
    y = x.copy()
    i, j = t
    y[i], y[j] = y[j], y[i]
    return y

def minmax(num): 
    nums = [int(i) for i in str(num)]
    opts = itertools.combinations(range(len(nums)), 2)
    new = map(lambda x: swap(nums, x), list(opts))
    keeps = list(filter(lambda x: x[0] != 0, new))
    keeps.append(nums)
    vals = list(map(lambda x: int(''.join(map(str, x))), keeps))
    return (max(vals), min(vals))

minmax(213)

(312, 123)

minmax(12345)

(52341, 12345)

minmax(100)

(100, 100)

minmax(11321)

(31121, 11123)

Aside from my grumbles while writing it, the solution is still pretty clean. The calls to list() interspersed throughout might be avoidable, but the need to do that while developing at least slowed me down.

I almost didn’t do a Rust solution because I thought I’d done enough. It ended up being the most complicated, though - I’m not sure if that’s because of me, or Rust.

use itertools::Itertools;

fn swap(v: Vec<u32>, t1: usize, t2: usize) -> Vec<u32> {
    let mut vv = v;
    let tmp1 = vv[t1];
    let tmp2 = vv[t2];
    vv[t1] = tmp2;
    vv[t2] = tmp1;
    return vv;
}

fn maxmin(num: u32) -> (u32, u32) {
    let numc = num.to_string();
    let n = numc.len();
    let numv: Vec<u32> = numc
        .to_string()
        .chars()
        .map(|c| c.to_digit(10).unwrap())
        .collect();
    let mut opts = Vec::new();
    for (a, b) in (0..n).tuple_combinations() {
        opts.push((a, b));
    }
    let mut new: Vec<Vec<u32>> = Vec::new();
    new.push(numv.clone());
    for o in opts {
        new.push(swap(numv.clone(), o.0, o.1));
    }
    let keeps: Vec<Vec<u32>> = new.into_iter().filter(|x| x[0] != 0).collect();
    let mut vals = Vec::new();
    for v in keeps {
        let tmp: u32 = v
            .clone()
            .into_iter()
            .map(|x| x.to_string())
            .collect::<String>()
            .parse()
            .unwrap();
        vals.push(tmp);
    }
    let min = *vals.iter().min().unwrap();
    let max = *vals.iter().max().unwrap();
    (max, min)
}

fn main() {
    println!("{:?}", maxmin(213));
    println!("{:?}", maxmin(12345));
    println!("{:?}", maxmin(100));
    println!("{:?}", maxmin(11321))
}

(312, 123)
(52341, 12345)
(100, 100)
(31121, 11123)

This solution reminded me why I like working with array (or at least vector-supporting) languages; not needing to explicitly loop over every element of a vector to do something. I had to write a lot of push() loops to move data around. max() doesn’t work on a vector (in the sense of finding the maximum of n elements); it works that way on an iterator, and may fail, hence the longer min and max lines.

Having to clone() various values explicitly because they can’t be re-used was a bit annoying, but I understand why it complains about those.

This took longer than I would have liked, but of course I learned more by doing it.

At the APL meetup we discussed one partial J solution which used a slightly different approach to the ‘swap’ algorithm. I’m not sure that there is a way in J that’s as elegant as the APL solution, but I’d be interested if there is.

Justus Perlwitz (www.justusperlwitz.com) offered this (gist.github.com) solution, the essence of which is

digits =: 10&#.^:_1

sd =: {{
  amend =. (|.y)}
  swap =. (y { ]) amend ]
  swap &.: digits x
}}

cart =: {{
  all =. ,/ (,"0)/~ y
  uniq =. ~. /:~"1 all
  l =. 0{"1 uniq
  r =. 1{"1 uniq
  (l ~: r) # uniq
}}

swapmaxmin =: {{
  ndigits =. [: # digits
  combs =. cart i. ndigits y
  constr =. ((ndigits y) <: [: ndigits"0 ]) # ]
  swaps =. constr y, y sd"1 combs
  (>./ , <./) swaps
}}

swapmaxmin 213

312 123

swapmaxmin 12345

52341 12345

swapmaxmin 100

100 100

swapmaxmin 11321

31121 11123

and which you can run in the J playground (jsoftware.github.io)

There’s a lot I want to learn about J, so I’ll be digging through this solution myself.

Andrew Gray in my local Functional Programming meetup offered a Go solution (github.com) which I pared down to the following

package main

import (
	"fmt"
	"slices"
	"strconv"
)

func MaxMin(n int) (max, min int) {
	s := strconv.Itoa(n)
	digits := []rune(s)
	max, min = n, n
	for i := range digits {
		for j := i + 1; j < len(digits); j++ {
			if i == 0 && digits[j] == '0' {
				continue
			}
			swapped := slices.Clone(digits)
			swapped[i], swapped[j] = swapped[j], swapped[i]
			curr, _ := strconv.Atoi(string(swapped))
			if curr > max {
				max = curr
			}
			if curr < min {
				min = curr
			}
		}
	}
	return max, min
}

func main() {
	fmt.Println(MaxMin(213))
	fmt.Println(MaxMin(12345))
	fmt.Println(MaxMin(100))
	fmt.Println(MaxMin(11321))
}

312 123
52341 12345
100 100
31121 11123

Go also has the handy destructuring syntax, but has a slightly different way to convert between digits and strings. Go also offers a playground in which you can run this code (go.dev).