#!/usr/bin/env python3

import random
import sys
from argparse import ArgumentParser
from collections import defaultdict


parser = ArgumentParser(
    "Generate random instance to Bookshelf."""
)
parser.add_argument("-N", type=int, default=100)
parser.add_argument("-W", type=int, default=900)
parser.add_argument("-H", type=int, default=350)
parser.add_argument("--h_lo", type=int, default=76)
parser.add_argument("--h_hi", type=int, default=483)
parser.add_argument("--t_lo", type=int, default=5)
parser.add_argument("--t_hi", type=int, default=60)
parser.add_argument("--fit", choices=['neither', 'stacked', 'upright', 'both'], default='neither', help="stacked means all books fit stacked. upright means all books fit upright.")
parser.add_argument("--solution", choices=['unique', 'impossible', 'many', 'possible'],  default='possible')
parser.add_argument("--tries", type=int, default=900)
parser.add_argument("--seed", type=int, default=0, help="seed")
args = parser.parse_args()

random.seed(args.seed)

# make sure every book fits (on its own) either upright or stacked
h_hi = min(args.h_hi, max(args.W, args.H))
# don't need the same check for thickness, but just to make sure:
assert args.t_hi <= min(args.W, args.H)

# assert obvious lower bounds on H and W
stackable_instance = args.fit in ['stacked', 'both']
upright_instance = args.fit in ['upright', 'both']

if stackable_instance:
    assert args.N * args.t_lo <= args.H
if upright_instance:
    assert args.N * args.t_lo <= args.W

def random_instance(N, W, H):
    # start with all books as thin as possible
    thickness = [args.t_lo] * N
    total_width = sum(thickness)

    # add a millimeter of thickness to random books for 'tries' many times
    tries = 0
    while tries < args.tries and (upright_instance and total_width < W or stackable_instance and total_width < H):
        i = random.randrange(N)
        if thickness[i] < args.t_hi:
            thickness[i] += 1
        tries += 1


    # book heights can be just random in args.h_lo..h_hi,
    # as long as the constraints are satisfied
    height = []
    for _ in range(N):
        h = h_hi
        if args.fit in ['upright', 'both']:
            h = min(h, H)
        if args.fit in ['stacked', 'both']:
            h = min(h, W)
        height.append(random.randint(args.h_lo, h))

    return list(zip(height, thickness))

def solve(W, H, books):
    """ Solve the instance described by books, assuming that the base_id'th book
    forms the base of a base stack.
    """


    # filled[i] = dict mapping (w, h) to the number of ways
    # to fill the bookcase with width w upright
    # books and a stack of height h, using the first i books.
    # Invariantly, we have w <= W - books[0][0], h <= H
    stack_width = books[0][0]

    if stack_width > W:
        return dict()
    choices: list[dict[tuple[int, int]], int] = [
            { (0, books[0][1]) : 1 }
            ]


    ct = 0
    for hi, ti in books[1:]:
        current = defaultdict(int)
        for w, h in choices[-1]:
            ct = choices[-1][w, h]
            # shelve it upright
            if w + ti <= W - stack_width and hi <= H:
                current[w + ti, h] += ct
            # stack it
            if h + ti <= H and hi <= stack_width:
                current[w, h + ti] += ct
        choices.append(current)
        #print(i, current)
    return choices

def count(W, H, books):
    total = 0
    for j in range(len(books)):
        #print('>', j)
        # try with book j at the bottom of the stack
        books[0], books[j] = books[j], books[0]
        choices = solve(W, H, books)
        books[0], books[j] = books[j], books[0]

        for w, h in choices[-1]:
            if w > 0:
                total += choices[-1][w, h]
    return total

for generations in range(1000): # this is the number of tries before hte generator gives up
    random_books = random_instance(args.N, args.W, args.H)
    ct = count(args.W, args.H, random_books)
    if args.solution == "unique" and ct == 1:
        break
    elif args.solution == "impossible" and ct == 0:
        break
    elif args.solution == "many" and ct > 10000:
        break
    elif args.solution == "possible" and ct > 0:
        break
else:
    assert False, "Generator failed, couldn't find good instance"
print(args.N, args.H, args.W)
for book in random_books:
    print(*book)
print(f"{generations + 1} tries", file=sys.stderr)