Animal Crossing New Horizons happy villagers

animal_crossing_village.py

"""
Use the formula found on https://nookipedia.com/wiki/Compatibility (slightly modified) to compute Animal Crossing New Horizons village compositions optimizing villagers happiness.

Compatibility score between 2 villagers is a grade from 0 (worst) to 4 (best) and village score is the sum of every combinations of 2 villagers score in the village.

You can pass a required list of villagers (using their english ids or french names) to find the ideal villagers to recrute next.

See --help for options. -m3 -r2 are usualy good parameters.

Note that the program never stops so you will have to hit CTRL-C when you're done!

If you pass 10 or more required villager, the program will output the best possible village(s) with these villagers.
"""

__author__ = 'fbparis@gmail'
__license__ = 'iv'

import argparse
import pickle
from collections import namedtuple, defaultdict
from itertools import combinations
from random import sample, choice, choices

fieldnames = 'id name french_name birthday species gender personality zodiac_sign zodiac_element'.split()
Villager = namedtuple('Villager', fieldnames)

def get_personality_score(personality_1, personality_2):
	if set([personality_1, personality_2]) in (set(['lazy']), set(['peppy']), set(['jock']), set(['cranky']), set(['smug']), set(['uchi']), set(['normal', 'snooty']), set(['normal', 'smug']), set(['lazy', 'uchi']), set(['peppy', 'jock']), set(['snooty', 'cranky'])): return 'A'
	if set([personality_1, personality_2]) in (set(['normal', 'jock']), set(['normal', 'uchi']), set(['lazy', 'peppy']), set(['lazy', 'cranky']), set(['peppy', 'snooty']), set(['jock', 'smug']), set(['snooty', 'smug']), set(['cranky', 'uchi'])): return 'B'
	if set([personality_1, personality_2]) in (set(['normal']), set(['snooty']), set(['normal', 'cranky']), set(['lazy', 'snooty']), set(['lazy', 'smug']), set(['peppy', 'smug']), set(['peppy', 'uchi']), set(['jock', 'cranky']), set(['jock', 'uchi'])): return 'C'
	return 'D'

def get_zodiac_score(zodiac_element_1, zodiac_element_2):
	if zodiac_element_1 == zodiac_element_2: return 'A'
	if set([zodiac_element_1, zodiac_element_2]) in (set(['fire', 'water']), set(['earth', 'air'])): return 'D'
	return 'B'


def get_species_score(species_1, species_2):
	if species_1 == species_2: return 'B'
	if set([species_1, species_2]) in (set(['bear', 'cub']), set(['bull', 'cow']), set(['cat', 'tiger']), set(['dog', 'wolf']), set(['goat', 'sheep']), set(['kangaroo', 'koala'])): return 'A'
	if set([species_1, species_2]) in (set(['deer', 'horse']), set(['hamster', 'squirrel']), set(['hamster', 'mouse']), set(['mouse', 'squirrel'])): return 'B'
	if set([species_1, species_2]) in (set(['cat', 'mouse']), set(['cat', 'hamster']), set(['dog', 'gorilla']), set(['dog', 'monkey']), set(['sheep', 'wolf'])): return 'D'
	return 'C'

def get_compatibility_score(villager_1, villager_2, alt=False):
	score = get_classic_compatibility_score(villager_1, villager_2)
	if alt:
		score /= 2
		# if villager_1.personality != villager_2.personality: score += 2	
		if villager_1.gender != villager_2.gender: score += 2/3
		if villager_1.species != villager_2.species: score += 2/3
		if villager_1.personality != villager_2.personality: score += 2/3	
	return score

def get_classic_compatibility_score(villager_1, villager_2):
	results = sorted([get_personality_score(villager_1.personality, villager_2.personality), get_species_score(villager_1.species, villager_2.species), get_zodiac_score(villager_1.zodiac_element, villager_2.zodiac_element)])
	if results.count('A') == 3: return 4
	if results.count('A') == 2 or results in (['A', 'B', 'C'], ['A', 'B', 'B']): return 3
	if results.count('D') == 3: return 0
	if results.count('D') == 2: return 1
	return 2 

def load_villagers():
	with open('villagers.pickle', 'rb') as f:
		villagers = pickle.load(f)
	return villagers

def get_village_score(village, balanced=False, alt=False):
	score = 0
	for (villager_1, villager_2) in combinations(village, 2):
		score += get_compatibility_score(villager_1, villager_2, alt=alt)
	if balanced:
		score += get_balance_score(village)
	return score

def get_balance_score(village):
	"""
	"""
	gender_count = 1
	species_count = 9
	personality_count = 7
	village_gender = defaultdict(int)
	village_species = defaultdict(int)
	village_personality = defaultdict(int)
	for villager in village:
		village_gender[villager.gender] += 1
		village_species[villager.species] += 1
		village_personality[villager.personality] += 1
	village_gender = [x for x in village_gender.values()]
	village_species = [x for x in village_species.values()]
	village_personality = [x for x in village_personality.values()]
	gender_score = 9 - ((len(village_gender) - 1) / gender_count) * (9 - max(village_gender) + min(village_gender))
	species_score = 9 - ((len(village_species) - 1) / species_count) * (9 - max(village_species) + min(village_species))
	personality_score = 9 - ((len(village_personality) - 1) / personality_count) * (10 - max(village_personality) + min(village_personality))
	village_norm = sum([x**2 for x in (gender_score, species_score, personality_score)])**0.5
	return .999 * (1 - village_norm / 243**.5)

def best_villages_with(villagers, balanced=False, alt=False, french=False):
	"""
	"""
	best = []
	best_score = 0
	for village in combinations(villagers, 10):
		score = get_village_score(village, balanced=balanced, alt=alt)
		if score >= best_score:
			if score > best_score:
				best_score = score
				best = []
			best.append(village)
	print('\nBEST SCORE FOUND: %.2f' % best_score)
	for village in best:
		if french:
			print('\n  %s' % ', '.join(sorted([v.french_name for v in village])))
		else:
			print('\n  %s' % ', '.join(sorted([v.name for v in village])))
		props = zip(*[(v.gender, v.species, v.personality) for v in village])
		props = zip(['genders', 'species', 'personalities'],[[(x, prop.count(x)) for x in set(prop)] for prop in props])
		for prop, values in props:
			print('    %s: %s' % (prop, ', '.join(['%d %s' % (c, v) for v, c in values])))
		if alt:
			other_score = 'classic score: %d' % get_village_score(village, alt=False)
		else:
			other_score = 'alternative score: %.2f' % get_village_score(village, alt=True)
		print('    balance score: %.3f; %s' % (get_balance_score(village), other_score))

def random_walk(village, villagers, required, scores, steps, alt=False):
	"""
	we use weighted random, less popular villager most likely chosen for replacement, then most popular substitute most likely chosen
	"""
	for step in range(steps):
		best_move = []
		# first select a villager to replace
		weights = []
		for villager in village:
			weights.append(sum([v for k, v in scores.items() if villager.id not in k]))
		score_without_villager, villager = choices([(weights[i], villager) for i, villager in enumerate(village)], weights=[weight**2 for weight in weights], k=1)[0]
		# now select a subsitute
		weights = []
		for subsitute in villagers:
			if subsitute in village:
				continue
			score = score_without_villager
			_scores = {}
			for other in village + required:
				if other == villager:
					continue
				_score = get_compatibility_score(subsitute, other, alt=alt)
				_scores[(subsitute.id, other.id)] = _score
				score += _score
			best_move.append((subsitute, _scores))
			weights.append(score**2)
		# make the replacement
		(subsitute, _scores) = choices(best_move, weights=weights, k=1)[0]
		village = [v for v in village if v != villager] + [subsitute]
		scores = dict([(k, v) for k, v in scores.items() if villager.id not in k] + [(k, v) for k, v in _scores.items()])
	return sum([score for score in scores.values()]), village, scores

def improve_village(village, villagers, required, random_steps=None, alt=False):
	"""
	Replace a villager with another to maximize village score at each step
	When no more replacement can be done, return the new village
	As fast as we can, never compute the same thing twice (but still slow)
	"""
	scores = {}
	best_score = 0
	for villager_1, villager_2 in combinations(village + required, 2):
		score = get_compatibility_score(villager_1, villager_2, alt=alt)
		scores[(villager_1.id, villager_2.id)] = score
		best_score += score
	if random_steps is None:
		steps = max(0, 9 - len(required))
	else:
		steps = random_steps
	if steps > 0:
		# randomly switch some villagers then try to improve the resulting village
		best_score, village, scores = random_walk(village, villagers, required, scores, steps, alt)
	while 1:
		best_move = []
		best_score += 1 # new solution must be better to avoid infinite loops
		for villager in village:
			score_without_villager = sum([v for k, v in scores.items() if villager.id not in k])
			for substitute in villagers:
				if substitute in village:
					continue
				score = score_without_villager
				_scores = {}
				for other in village + required:
					if other == villager:
						continue
					_score = get_compatibility_score(substitute, other, alt=alt)
					_scores[(substitute.id, other.id)] = _score
					score += _score
				if score >= best_score:
					if score > best_score:
						best_score = score
						best_move = []
					best_move.append((villager, substitute, _scores))
		if not best_move:
			break
		# If several replacements have the same score, randomly choose one
		(villager, substitute, _scores) = choice(best_move)
		village = [v for v in village if v != villager] + [substitute]
		scores = dict([(k, v) for k, v in scores.items() if villager.id not in k] + [(k, v) for k, v in _scores.items()])
	return best_score - 1, village

def generate_villages(villagers, base=None, random_steps=None, keep_best=False, max_repetitions=None, balanced=False, alt=False, french=False):
	"""
	find villages that maximize the compatibility between its villagers
	can be seeded with a list of required villagers
	"""
	required = set()
	if base is not None:
		base = set([x.lower() for x in base])
		for villager in villagers.values():
			found = False
			for name in base:
				if (french == True and name == villager.french_name.lower()) or (french == False and name == villager.id.lower()):
					found = True
					required.add(villager)
					break
			if found:
				base.remove(name)
				if not base:
					break
	if len(required) >= 10:
		best_villages_with(required, balanced, alt, french)
	else:
		villagers = [villager for villager in villagers.values() if villager not in required]
		required = list(required)
		best_score = -1000
		n = 10 - len(required)
		results = set()
		best_village = sample(villagers, n)
		repeat = 0
		history = set()
		if required:
			if french:
				required_output = ', '.join(['%s' % v.french_name for v in required])
			else:
				required_output = ', '.join(['%s' % v.name for v in required])
			if len(required) < 10:
				required_output += ' + '
		else:
			required_output = ''
		while 1:
			score, village = improve_village(best_village, villagers, required, random_steps, alt=alt)
			balance_score = get_balance_score(village + required)
			if alt:
				other_score = 'classic score: %d' % get_village_score(village + required)
			else:
				other_score = 'alternative score: %.2f' % get_village_score(village + required, balanced=balanced, alt=True)
			if balanced:
				score += balance_score
			if french:
				last = tuple(sorted(['%s' % v.french_name for v in village]))
			else:
				last = tuple(sorted(['%s' % v.name for v in village]))
			if last in history:
				repeat += 1
			else:
				if max_repetitions is not None:
					history.add(last)
				if score >= best_score:
					best_village = village
					if last not in results:
						print()
						if score > best_score:
							best_score = score
							results = set()
							repeat = 0
							print('NEW BEST SCORE WITH %.2f POINTS\n' % score)
						results.add(last)
						props = zip(*[(v.gender, v.species, v.personality) for v in village + required])
						props = zip(['genders', 'species', 'personalities'],[[(x, prop.count(x)) for x in set(prop)] for prop in props])
						print('  %s%s' % (required_output, ', '.join(last)))
						for prop, values in props:
							print('    %s: %s' % (prop, ', '.join(['%d %s' % (c, v) for v, c in values])))
						print('    balance score: %.3f; %s' % (balance_score, other_score))
			if (max_repetitions is not None and repeat > max_repetitions) or (random_steps is not None and random_steps <= 0):
				# if too much repetitions of the same position, or if random walk not used then regenerate a fresh new random village
				best_village = sample(villagers, n)
				repeat = 0
			elif not keep_best:
				# restart from the last generated village
				best_village = village

if __name__ == '__main__':
	best_village_found = "BEST FOUND SO FAR WITH 147 POINTS: Bianca, Felicity, Kid Cat, Pinky, Poncho, Rudy, Stinky, Tabby, Tutu, Tybalt (genders: 5 female, 5 male; species: 2 bear, 5 cat, 1 cub, 2 tiger; personalities: 5 jock, 5 peppy)"
	parser = argparse.ArgumentParser(description=__doc__, epilog=best_village_found)
	parser.add_argument('--villagers', '-v', nargs='*', help='list of space sperated names for required villagers')
	parser.add_argument('--random-steps', '-r', type=int, default=None, help='number of random walk steps to escape local maxima ; automatic by default, 0 to skip random walk and try improving a random village at each step')
	parser.add_argument('--max-repetitions', '-m', type=int, default=None, help='regenerate a random village to improve when getting too much known results ; not used by default')
	parser.add_argument('--keep-best', '-k', action='store_true', help='only try to improve the best solution found')
	parser.add_argument('--balanced', '-b', action='store_true', help='extend scoring to boost well balanced villages (gender, species and personality)')
	parser.add_argument('--alt', '-a', action='store_true', help='alternative ranking mixing villagers compatibility and village balance')
	parser.add_argument('--french', '-f', action='store_true', help='use villagers french name')
	args = parser.parse_args()
	try:
		generate_villages(load_villagers(), base=args.villagers, random_steps=args.random_steps, keep_best=args.keep_best, max_repetitions=args.max_repetitions, balanced=args.balanced, alt=args.alt, french=args.french)
	except KeyboardInterrupt:
		pass

build-animal-crossing-villagers-db.py

"""
Create a CSV of Animal Crossing New Horizons from:
	- https://github.com/jefflomacy/villagerdb/tree/master/data/villagers for name, id, birthday, species, gender, personality
	- https://nookipedia.com/wiki/List_of_villager_names_in_other_languages for french name
	- utility functions to convert birthday to zodiac sign and element

1) check and/or update VILLAGERS_PATH_MASK
2) save source html of https://nookipedia.com/wiki/List_of_villager_names_in_other_languages in List_of_villager_names_in_other_languages.html
3) call create_csv()
4) Manualy check/fix villagers.csv (name and french_name can be wrong)
5) call create_pickle() when done
6) you can now use animal-crossing-village.py

"""

__author__ = 'fbparis.com'
__license__ = 'iv'

import csv
import json
import pickle
from bs4 import BeautifulSoup
from collections import namedtuple
from glob import glob

VILLAGERS_PATH_MASK = 'villagerdb-master/data/villagers/*.json'

fieldnames = 'id name french_name birthday species gender personality zodiac_sign zodiac_element'.split()
Villager = namedtuple('Villager', fieldnames)

def get_zodiac_sign_from_birthday(birthday):
	month, day = birthday.split('-')
	md = (int(month), int(day))
	if md >= (1, 20) and md <= (2, 18): return 'aquarius'
	if md >= (2, 19) and md <= (3, 20): return 'pisces'
	if md >= (3, 21) and md <= (4, 19): return 'aries'
	if md >= (4, 20) and md <= (5, 20): return 'taurus'
	if md >= (5, 21) and md <= (6, 20): return 'gemini'
	if md >= (6, 21) and md <= (7, 22): return 'cancer'
	if md >= (7, 23) and md <= (8, 22): return 'leo'
	if md >= (8, 23) and md <= (9, 22): return 'virgo'
	if md >= (9, 23) and md <= (10, 22): return 'libra'
	if md >= (10, 23) and md <= (11, 21): return 'scorpio'
	if md >= (11, 22) and md <= (12, 21): return 'sagittarius'
	return 'capricorn'

def get_zodiac_element_from_zodiac_sign(zodiac_sign):
	if zodiac_sign in ('aquarius', 'gemini', 'libra'): return 'air'
	if zodiac_sign in ('pisces', 'cancer', 'scorpio'): return 'water'
	if zodiac_sign in ('aries', 'leo', 'sagittarius'): return 'fire'
	return 'earth'

def create_csv():
	to_french = dict()
	with open('List_of_villager_names_in_other_languages.html') as f:
		html = f.read()
	soup = BeautifulSoup(html)
	for tr in soup.select('tbody tr'):
		td = tr.find_all('td')
		if not td:
			continue
		name = td[0].a.text
		if name in to_french:
			print('problem with %s' % name)
		to_french[name] = td[3].text
	with open('villagers.csv', 'w', newline='') as csvfile:
		writer = csv.DictWriter(csvfile, fieldnames=fieldnames)
		for json_file in glob(VILLAGERS_PATH_MASK):
			with open(json_file) as f:
				data = json.load(f)
			if 'nh' not in data['games']:
				continue
			french_name = to_french[data['name']]
			zodiac_sign = get_zodiac_sign_from_birthday(data['birthday'])
			zodiac_element = get_zodiac_element_from_zodiac_sign(zodiac_sign)
			villager = Villager(data['id'], data['name'], french_name, data['birthday'], data['species'], data['gender'], data['games']['nh']['personality'], zodiac_sign, zodiac_element)
			writer.writerow(villager._asdict())

def create_pickle():
	villagers = {}
	with open('villagers.csv', newline='') as csvfile:
		reader = csv.DictReader(csvfile, fieldnames=fieldnames)
		for row in reader:
			villager = Villager(**row)
			villagers[villager.id] = villager
	check_villagers(villagers)
	with open('villagers.pickle', 'wb') as f:
		pickle.dump(villagers, f)

def check_villagers(villagers):
	names = set()
	french_names = set()
	for villager in villagers.values():
		names.add(villager.name)
		french_names.add(villager.french_name)
	print('%d villagers / %d names / %d french names' % (len(villagers), len(names), len(french_names)))

if __name__ == '__main__':
	#create_csv()
	create_pickle()

villagers.csv