HarvsG/mpmp3.py

## mpmp3.py
import sys

if sys.version_info[0] < 3:
    raise Exception("Python 3 or a more recent version is required.")

# this will serve as a dictionary of what each tile face is worth
scores = {"A": 1 , "B": 3 , "C": 3 , "D": 2 ,
         "E": 1 , "F": 4 , "G": 2 , "H": 4 ,
         "I": 1 , "J": 8 , "K": 5 , "L": 1 ,
         "M": 3 , "N": 1 , "O": 1 , "P": 3 ,
         "Q": 10, "R": 1 , "S": 1 , "T": 1 ,
         "U": 1 , "V": 4 , "W": 4 , "X": 8 ,
         "Y": 4 , "Z": 10, " ":0}

# this is the amount of each tile that is in the game, there are 100 tiles totoal
pieces = {"A":9, "B":2, "C":2, "D":4, "E":12,
         "F":2, "G":3, "H":2, "I":9, "J":1,
         "K":1, "L":4, "M":2, "N":6, "O":8,
         "P":2, "Q":1, "R":6, "S":4, "T":6,
         "U":4, "V":2, "W":2, "X":1, "Y":2,
         "Z":1, " ":2}

def make_uniques(dic):
    unique_scores = set(dic.values())
    score_tiles = {}

    for key, val in dic.items():
        if val not in score_tiles:
            score_tiles[val] = pieces[key]
        else:
            score_tiles[val] += pieces[key]

    sorted_tiles = {}
    for key in reversed(sorted(score_tiles.keys())):
        sorted_tiles[key] = score_tiles[key]
    return sorted_tiles

def max_from_uniques(uniques, rem_choices):
    max = 0
    i = 0

    for key, value in uniques.items():
        if i < rem_choices:
            p = min(value,rem_choices-i)
            max = max + (key*p)
            i += p
        else:
            break
    return max


def calc(lim, pieces, uniques, remainder, choices=[], solutions=set()):
    '''A recursive function to find ways of making 46 from lim tiles
    lim = the number of tiles we are choosing
    pieces = dictionary of the {tile_string:number_of_tiles}
    unqiues = dictionary of {tile_score:number_of_tiles_with_that_score} aka make_uniques(pieces)
    remainder = the target number
    choices = list the current choices made so far
    solutions = the current set of discovered solutions'''

    if len(choices) == lim:
        # we have made all our n==lim choices so we either have a solution or we dont

        if  remainder is 0:
            # in this case we have found a solution so return it

            # sort to prevent duplicates
            choices.sort()

            # ------optional code to print new solutions-------
            if tuple(choices) not in solutions:
                print('New soultion found: ' + str(tuple(choices)))
            # ---end optional code to print new solutions-------

            # add the solutions to the set of solutions, duplicates will be ignored
            solutions.add(tuple(choices))

            return solutions

        else:
            # in this case we have used all tiles and not found a solution so return False

            return False

    elif len(choices) < lim:
        # we still have remaining choices to make
        rem_choices = lim - len(choices)

        # this if statement checks if it is even possible to make the remainder with the remaining tiles, massively more efficient
        if max_from_uniques(uniques, rem_choices) < remainder:
            return False

        for piece, num in pieces.items():

            # only try if any tiles of that name remain
            if num > 0:

                # as each recurrsion may generate > 1 aditional recursion, a branching version must be made, so we make copies
                d_choices = choices.copy()
                d_lim = lim
                d_pieces = pieces.copy()
                d_uniques = uniques.copy()
                d_remainder = remainder
                d_solutions = solutions.copy()

                # alter the copies to make the choice
                d_pieces[piece] -= 1
                d_uniques[scores[piece]] -= 1
                d_remainder -= scores[piece]
                d_choices.append(piece)

                # recurr
                res = calc(d_lim, d_pieces, d_uniques, d_remainder, choices=d_choices, solutions=d_solutions)

                # if the solution is valid, add it to the solutions. As we are using sets it doesn't matter if there are duplicates
                if res is not False:
                    solutions = solutions | res
                else:
                    continue
            else:
                continue

        return solutions

    else:
        print('here be dragons')

solutions = calc(7,pieces,make_uniques(scores), 46)
print(sorted(solutions))
print(len(solutions))
	import sys

	if sys.version_info[0] < 3:
	raise Exception("Python 3 or a more recent version is required.")

	# this will serve as a dictionary of what each tile face is worth
	scores = {"A": 1 , "B": 3 , "C": 3 , "D": 2 ,
	"E": 1 , "F": 4 , "G": 2 , "H": 4 ,
	"I": 1 , "J": 8 , "K": 5 , "L": 1 ,
	"M": 3 , "N": 1 , "O": 1 , "P": 3 ,
	"Q": 10, "R": 1 , "S": 1 , "T": 1 ,
	"U": 1 , "V": 4 , "W": 4 , "X": 8 ,
	"Y": 4 , "Z": 10, " ":0}

	# this is the amount of each tile that is in the game, there are 100 tiles totoal
	pieces = {"A":9, "B":2, "C":2, "D":4, "E":12,
	"F":2, "G":3, "H":2, "I":9, "J":1,
	"K":1, "L":4, "M":2, "N":6, "O":8,
	"P":2, "Q":1, "R":6, "S":4, "T":6,
	"U":4, "V":2, "W":2, "X":1, "Y":2,
	"Z":1, " ":2}

	def make_uniques(dic):
	unique_scores = set(dic.values())
	score_tiles = {}

	for key, val in dic.items():
	if val not in score_tiles:
	score_tiles[val] = pieces[key]
	else:
	score_tiles[val] += pieces[key]

	sorted_tiles = {}
	for key in reversed(sorted(score_tiles.keys())):
	sorted_tiles[key] = score_tiles[key]
	return sorted_tiles

	def max_from_uniques(uniques, rem_choices):
	max = 0
	i = 0

	for key, value in uniques.items():
	if i < rem_choices:
	p = min(value,rem_choices-i)
	max = max + (key*p)
	i += p
	else:
	break
	return max



	def calc(lim, pieces, uniques, remainder, choices=[], solutions=set()):
	'''A recursive function to find ways of making 46 from lim tiles
	lim = the number of tiles we are choosing
	pieces = dictionary of the {tile_string:number_of_tiles}
	unqiues = dictionary of {tile_score:number_of_tiles_with_that_score} aka make_uniques(pieces)
	remainder = the target number
	choices = list the current choices made so far
	solutions = the current set of discovered solutions'''

	if len(choices) == lim:
	# we have made all our n==lim choices so we either have a solution or we dont

	if remainder is 0:
	# in this case we have found a solution so return it

	# sort to prevent duplicates
	choices.sort()

	# ------optional code to print new solutions-------
	if tuple(choices) not in solutions:
	print('New soultion found: ' + str(tuple(choices)))
	# ---end optional code to print new solutions-------

	# add the solutions to the set of solutions, duplicates will be ignored
	solutions.add(tuple(choices))

	return solutions

	else:
	# in this case we have used all tiles and not found a solution so return False

	return False

	elif len(choices) < lim:
	# we still have remaining choices to make
	rem_choices = lim - len(choices)

	# this if statement checks if it is even possible to make the remainder with the remaining tiles, massively more efficient
	if max_from_uniques(uniques, rem_choices) < remainder:
	return False

	for piece, num in pieces.items():

	# only try if any tiles of that name remain
	if num > 0:

	# as each recurrsion may generate > 1 aditional recursion, a branching version must be made, so we make copies
	d_choices = choices.copy()
	d_lim = lim
	d_pieces = pieces.copy()
	d_uniques = uniques.copy()
	d_remainder = remainder
	d_solutions = solutions.copy()

	# alter the copies to make the choice
	d_pieces[piece] -= 1
	d_uniques[scores[piece]] -= 1
	d_remainder -= scores[piece]
	d_choices.append(piece)

	# recurr
	res = calc(d_lim, d_pieces, d_uniques, d_remainder, choices=d_choices, solutions=d_solutions)

	# if the solution is valid, add it to the solutions. As we are using sets it doesn't matter if there are duplicates
	if res is not False:
	solutions = solutions \| res
	else:
	continue
	else:
	continue

	return solutions

	else:
	print('here be dragons')

	solutions = calc(7,pieces,make_uniques(scores), 46)
	print(sorted(solutions))
	print(len(solutions))