Min-swap palindrome

README.md

To run application

./app.py

To make request to it

curl -H 'Content-Type: application/json' -d '{"word":"aabb"}' localhost:8000

To run tests

pytest

app.py

#!/usr/bin/env python3
"""
$ curl -H 'Content-type: application/json' -d '{"word":"aabb"}' localhost:8000
{"palindrome": "abba"}
"""
import json

from palindrome import min_palindrome


def app(environ, start_response):
    # get word from the request
    try:
        request_body_size = int(environ.get("CONTENT_LENGTH", 0))
    except ValueError:
        request_body_size = 0

    request_body = environ["wsgi.input"].read(request_body_size)
    word = json.loads(request_body)["word"]

    # find palindrome
    palindrome = min_palindrome(word)

    # return response
    status = "200 OK"
    headers = [("Content-type", "application/json")]
    start_response(status, headers)
    return [json.dumps(dict(palindrome=palindrome)).encode()]


if __name__ == "__main__":
    from wsgiref.simple_server import make_server

    with make_server("localhost", 8000, app) as httpd:
        print("Serving on localhost:8000...")
        httpd.serve_forever()

palindrome.py

from collections import Counter, defaultdict
from collections.abc import Sequence

__all__ = ["min_palindrome"]


def odd(n: int) -> bool:
    return bool(n % 2)


def is_palindrome(chars: Sequence) -> bool:
    return chars == chars[::-1]


def min_palindrome(s: str) -> str:
    """Make min-swap palindrome from *s* or return empty string if can't.

    If multiple such palindromes exists, prefer lexicographical order.
    """
    # https://stackoverflow.com/questions/51796237/minimum-number-of-swaps-to-convert-a-string-to-palindrome
    chars = list(s)

    # determine whether we can make a palindrome from chars at all
    freq = Counter(s)
    if sum(map(odd, freq.values())) > 1:  # more than one odd frequency
        return ""  # can't make palindrome

    # move char with odd count into the middle
    n = len(chars)
    middle = n // 2
    if odd(n):
        ch = next(ch for ch, count in freq.items() if odd(count))
        for i, c in enumerate(chars):
            if c == ch and ch != chars[n - i - 1]:
                # move asymmetric char into the middle
                # baa(b)b -> babab
                #     ^i=n-2 != chars[1]
                chars[middle], chars[i] = chars[i], chars[middle]  # swap
                break
        else:  # already in the middle
            assert ch == chars[middle]

    misplaced = defaultdict(list)  # misplaced positions
    while True:
        # invariant: at least one letter finds its position
        for ai, (a, b) in enumerate(zip(chars[:middle], chars[::-1][:middle])):
            if a != b:
                # a, b are misplaced
                bi = n - ai - 1
                if b < a:
                    a, b = b, a  # arrange lexicographically
                    ai, bi = bi, ai
                assert a < b
                if misplaced[a, b]:
                    # found 2nd misplaced position for the same a,b pair
                    # put pair into the same place with one swap
                    aj, bj = misplaced[a, b].pop()
                    del misplaced[a, b]
                    # a(a)b(b) -> abba
                    # ab(a)(b) -> abba
                    # -abba- -baab-
                    # (b)(a)ba -> abba
                    # (b)b(a)a -> abba
                    assert chars[aj] == a
                    assert chars[ai] == a
                    assert chars[bj] == b
                    assert chars[bi] == b
                    # earlier position gets smaller letter (alphabetical order)
                    chars[min(aj, bj)] = chars[max(aj, bj)] = a
                    chars[min(ai, bi)] = chars[max(ai, bi)] = b
                else:
                    misplaced[a, b].append((ai, bi))
        if not any(misplaced.values()):
            # no misplaced positions
            assert is_palindrome(chars)
            return "".join(chars)

        # expect cycle e.g.:  a -> c -> b -> a
        # abcbac -> abcb(c)(a) -> abc(c)(b)a

        # collect misplaced positions
        positions = defaultdict(list)
        for (a, b), [(ai, bi)] in misplaced.items():
            assert a < b
            assert chars[ai] == a
            assert chars[bi] == b
            positions[a].append(ai)
            positions[b].append(bi)

        # put one letter into right place with one swap and repeat the loop
        (a, b), [_] = misplaced.popitem()

        def find_positions_to_swap():
            assert a < b
            for ai in sorted(positions[a]):
                for bi in sorted(positions[b]):
                    # prefer lexicographical order
                    if (ai < middle and bi < ai) or (ai >= middle and bi > ai):
                        return (ai, bi)
            assert 0, "failed to find wrong order"

        ai, bi = find_positions_to_swap()
        # initially both letters are missplaced
        assert (
            chars[ai] != chars[n - ai - 1] and chars[bi] != chars[n - bi - 1]
        )
        chars[ai], chars[bi] = chars[bi], chars[ai]  # swap
        # found correct position after the swap
        assert chars[ai] == chars[n - ai - 1] or chars[bi] == chars[n - bi - 1]
        misplaced.clear()

pyproject.toml

[tool.black]
line-length = 79
# Split long strings & merge short ones;
#   future default: https://github.com/psf/black/issues/2188
experimental-string-processing = true
exclude = '''

(
  /(
      \.eggs         # exclude a few common directories in the
    | \.git          # root of the project
    | \.hg
    | \.mypy_cache
    | \.tox
    | \.venv
    | _build
    | build
    | dist
  )/
)
'''

test_palindrome.py

"""Unit tests for palindrome."""
import pytest

from palindrome import is_palindrome, min_palindrome


@pytest.mark.parametrize(
    "word, expected",
    [
        ("ab", ""),  # can't make
        ("", ""),
        ("a", "a"),
        ("abc", ""),
        ("abba", "abba"),
        ("aabb", "abba"),
        ("baab", "baab"),
        ("abab", "abba"),
        ("baba", "abba"),
        ("bbaa", "abba"),
        ("babac", "bacab"),
        ("aabbc", "abcba"),
        ("baabb", "babab"),
        ("bbaab", "babab"),
        ("abbaa", "ababa"),
        ("aabba", "ababa"),
        ("babaaab", "baabaab"),
        ("abacb", "abcba"),
        ("baacb", "bacab"),
        ("cabcba", "abccba"),
        ("abcbac", "abccba"),
        ("cabbacabcbac", "cababccbabac"),
        ("baaaccb", "bacacab"),
        pytest.param("baaabcc", "bacacab", marks=pytest.mark.xfail),
        pytest.param("aaabbcc", "abcacba", marks=pytest.mark.xfail),
    ],
)
def test_min_palindrome(word, expected):
    assert is_palindrome(expected)
    assert min_palindrome(word) == expected


@pytest.mark.parametrize(
    "word, expected",
    [
        ("ab", False),
        ("", True),
        ([], True),
        ("a", True),
        (["a"], True),
        ("ababa", True),
        ("abc", False),
        ("baab", True),
        ("abba", True),
        ("abcba", True),
        ("ababa", True),
        ([*"ababa"], True),
        ("aabba", False),
        ([*"aabba"], False),
        ("abbba", True),
        ("aabb", False),
        ("babac", False),
        ("aabbc", False),
    ],
)
def test_is_palindrome(word, expected):
    assert is_palindrome(word) == expected