Heuristics Problem Solving

This repository contains our solutions to problems provided by Dr Dennis Shasha during Heuristics Problem Solving class at NYU Fall 2016.

More details are listed inside each folder's readme (problem description and solution approach). Most of the problems are NP-Complete in nature and we have to apply suitable heuristics to solve these under the time limit of 2 minutes and provide an efficient solution. Solutions of teams (12 in our case) compete with each other in a tournament, where one team is architect of tournament (tournament host). Winner is the last team standing.

Contents

• Expanding Nim - Week 1

Version of nim games where one can pick up 1 more stone than last maximum picked stones number. The one to pick last stone is winner.

• Optimal Touring - Week 2

Visit n places in a city with each having a particular benefit value to tourist and fixed closing and opening times. The team which generates max score wins.

• No Tipping - Week 3

A board of titanium, 15 blocks. Teams place them and one to tip the board loses.

• Shortest Adversarial Path - Week 4

We were the architects for this game. We also made this game as our final project playable here. In this game, player wants to reach a particular position and advesary increases edge costs. The min cost path one is winner.

• Gravitational Voronoi - Week 5

A board where both teams have colors and they can place stones on board. Board color changes according to gravitational pull at particular position. The most covered area team wins.

• Evasion Game - Week 6

Prey and Hunter, hunter can place walls and prey wants to escape. The min time to capture prey wins.

• Dancing without Stars - Week 7

Choreographer and Spoiler. There are n blue dancers and red dancers which need to adjacent as pairs, min step to do that with stars placed on board.

• Dating Game - Week 9

Preferences by date, we generate candidates, we don't know the preferences and one to generate best candidate wins.