is_steal_sort.sh - return true for GrabScrab steal (via letter sorting)

is_steal_sort.sh

#!/bin/sh
# is_steal_sort.sh - return true for GrabScrab steal (via letter sorting)
# Andrew Ho (andrew@zeuscat.com)
#
# Given two words, exits with zero return status if the second word is a
# GrabScrab steal for the first (see <http://grabscrab.com>).
#
# This solution counts letters and compares the letter counts, with best
# case O(n*log(n)) performance, where n is total letter count.

ME=`basename "$0"`
USAGE="usage: $ME base steal"

# Main loop, run at end
main() {
    # Check for valid inputs
    [ $# -ge 2 ] || usage 'both base and steal word inputs are required'
    base=`normalize "$1"`
    [ -n "$base" ] || die 'base word must have at least one English letter'
    steal=`normalize "$2"`
    [ -n "$steal" ] || die 'steal word must have at least one English letter'

    # Turn words into lists of sorted letters
    base=`sortletters "$base"`
    steal=`sortletters "$steal"`

    # Iterate through base, search for each letter from front of steal
    extra=false
    while [ -n "$base" ]; do
        b=`first $base`
        s=`first $steal`
        # If letter in steal is not in base, keep shifting letters off steal
        while [ "$b" '!=' "$s" ] && [ -n "$steal" ]; do
            extra=true
            steal=`rest $steal`
            s=`first $steal`
        done
        base=`rest $base`
        steal=`rest $steal`
        [ "$b" '!=' "$s" ] && break
    done
    [ -n "$steal" ] && extra=true
    [ -z "$base" ] && [ "$extra" = true ]
}

# Print error message and usage to stderr, exit with non-zero return status
usage() { echo "$ME: $@" 1>&2; echo "$USAGE" 1>&2; exit 1; }

# Print error message to stderr, exit with non-zero return status
die() { echo "$ME: $@" 1>&2; exit 1; }

# Given a string, output it with only uppercase English letters
normalize() { echo "$1" | tr a-z A-Z | sed 's/[^A-Z]//g'; }

# Given a string, output sorted letters in it
sortletters() { echo "$1" | fold -w1 | sort; }

# Return first whitespace separated token in string
first() { echo "$1"; }

# Return string other than the first whitespace separated token
rest() { [ $# -gt 0 ] && shift; echo "$@"; }

# Run main loop
main $@