### 15.awk -- Play to the sum 15 using the numbers 1 through 9, once.

## Copyright (C) 2007  Aaron S. Hawley <aaronh@localhost>

## Keywords: games

## This program is free software: you can redistribute it and/or
## modify it under the terms of the GNU General Public License as
## published by the Free Software Foundation, either version 3 of
## the License, or (at your option) any later version.

## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
## GNU General Public License for more details.

## You should have received a copy of the GNU General Public License
## along with this program.  If not, see <http://www.gnu.org/licenses/>.

## $Id: 15.awk,v 2.1 2007/07/31 01:27:09 aaronh Exp $

### Commentary:

## Provide numbers on standard input or play interactively.

## To let the computer play first, run:

## $ awk -f 15.awk -v start=1

## To play first, run:

## $ awk -f 15.awk -v start=2

### Code:

BEGIN {
    winning_sum = 15;
    max_play = 9;
    used[0] = 1;
    my_sum = your_sum = 0;
    if (start == 1) {
        answer = ftw(used, my_sum);
	used[answer] = 1;
	my_sum += answer;
	print answer;
    }
    halted=0;
}

! /^[1-9]$/ {
    print "Illegal play: " $0;
}

{
    if ($0 in used) {
        print "Illegal play: " $0;
    } else {
        used[$0] = 1;
        your_sum += $0;
        if (your_sum == winning_sum) {
            print "You win!";
	    halted=1
	    exit 0
        } else if (your_sum > winning_sum && my_sum > winning_sum) {
            print "Draw";
	    halted=1;
	    exit 2;
        } else {
	    answer = block = winning_sum - your_sum;
	    winning_move = ftw(used, my_sum);
            if (block > max_play \
		|| block <= 0 \
		|| block in used) {
                answer = winning_move;
	    }
	    while (answer <= 0 || answer > max_play || answer in used) {
		answer++;
	    }
            my_sum += answer;
            used[answer] = 1;
            print answer;
            if (my_sum == winning_sum) {
                print "I win!";
		halted=1;
		exit 1;
            }
        }
    }
}

END {
    if (halted == 1) {
	exit;
    }
    if (your_sum != winning_sum && my_sum != winning_sum) {
	print "I win by forfeit";
	exit 1;
    }
}

function ftw(used, sum) {
    strlst = "";
    for (v in used) {
        strlst = strlst "" v;
    }
    to_win = try(strlst, max_play "", sum);
    if (to_win == "") {
        return -1;
    }
    return substr(to_win, 1, 1);
}

function try(used, hunches, sum) {
    curr_sum = strsum(hunches) + sum;
    curr_hunch = substr(hunches, 1, 1);
    next_hunch = curr_hunch - 1;
    if (hunches == "") {
        return "";
    } else if (curr_hunch < 1) {
        return substr(hunches, 2);
    } else if (index(used, curr_hunch) || curr_sum > winning_sum) {
        return try(used, next_hunch "" substr(hunches, 2), sum);
    } else if (curr_sum == winning_sum) {
        return hunches;
    }
    return try(curr_hunch "" used, next_hunch "" hunches, sum);
}

function strsum(str) {
    s = 0;
    str_length = length(str);
    for (i = 1; i <= str_length; i++) {
        s += substr(str, i, 1);
    }
    return s;
}

## Test suite:

# for i in $(seq 1 9521); do echo $i; done | grep -ve 0 | grep -Eve '(.)\1' \
# | awk '{ s = 0; for (i = 1; i <= length($0); i++) { s += substr($0, i, 1); } if (s > 2 && s < 18) {print;} }' \
# | awk '{gsub(//, "\\n"); gsub(/^\\n/, ""); gsub(/\\n$/, ""); print "echo game" NR "a"; print "echo -e \"" $0 "\" | awk -f ./15.awk -v start=1"; print "echo game" NR "b"; print "echo -e \"" $0 "\" | awk -f ./15.awk -v start=2";}' | /bin/sh \
# | grep -ve ^[0-9]$ -ve ^game | sort | uniq -c \
# | awk '{sum+=$1;print;}END{print "  " ,sum, "Total";}'
#      38 Draw
#     156 Illegal play: 1
#     105 Illegal play: 2
#     102 Illegal play: 3
#      67 Illegal play: 4
#      62 Illegal play: 5
#     443 Illegal play: 6
#      39 Illegal play: 7
#      33 Illegal play: 8
#       6 Illegal play: 9
#    2966 I win!
#     776 I win by forfeit
#    4793 Total