The Movie Seating Problem

A-social Networking Question

Jamie Ding

Torrey Pines High School
San Diego, California

What is the Movie Seating Problem?

Thanks to Randall Munroe
www.xkcd.com

The MSP and Graph Theory

The MSP as the Weighted Hamiltonian Path Problem

Given a weighted graph, find the Hamiltonian Path with the highest total weight.

Assumptions

Single Row Seating

Complete Graph

Approach?

Permutations

Dynamic Front End

TheMovieSeatingProblem5

Thanks to...

Randall Munroe

Harry Calkins

t0rajir0u

Art of Problem Solving Messageboard

S.O.S. Mathematics CyberBoard

And, of course, Ms. Abby Brown

Mathematica Projects by High School Students

Jamie Ding, Vivian Feig, Alan Joyce, Victoria Le, and Ernest Lee

Torrey Pines High School

www.MathematiClub.com

Initialization

TheMovieSeatingProblem5=DynamicModule[
{FirstFriend=Harry,SecondFriend=Ron,ThirdFriend=Hermione,FourthFriend=Malfoy,FifthFriend=Ginny,
Rule1=1,Rule2=1,Rule3=-2,Rule4=2,Rule5=1,Rule6=2,Rule7=-2,Rule8=1,Rule9=1,Rule10=2,Rule11=-2,Rule12=1,Rule13=-2,Rule14=-2,Rule15=-2,Rule16=-2,Rule17=2,Rule18=1,Rule19=1,Rule20=-2},

Grid[{
{"Here is an optimized seating chart:","The Coefficient of Pleasure (CoP) is: "},
{Dynamic[Row[{TheChosenPath[[1]]," ",TheChosenPath[[2]]," ",TheChosenPath[[3]]," ",TheChosenPath[[4]]," ",TheChosenPath[[5]]}]/.{Vicky->,Vivian->,Alan->,Ernest->,Jamie->}]},
{ExtractionFunction[x_,y_]:=y[[x]][[1]];
Dynamic[TheChosenPath=RandomChoice[Table[ExtractionFunction[x,Delete[Select[AllPathsAndWeights,#[[2]]==Max[AllPathsAndWeights[[All,2]]]&],Position[Select[AllPathsAndWeights,#[[2]]==Max[AllPathsAndWeights[[All,2]]]&],Max[AllPathsAndWeights[[All,2]]]]]],{x,Length[Delete[Select[AllPathsAndWeights,#[[2]]==Max[AllPathsAndWeights[[All,2]]]&],Position[Select[AllPathsAndWeights,#[[2]]==Max[AllPathsAndWeights[[All,2]]]&],Max[AllPathsAndWeights[[All,2]]]]]]}]]],
Dynamic[N[Max[AllPathsAndWeights[[All,2]]]/16,3]]},

{"Input Names Here:"},
{InputField[Dynamic[FirstFriend]],
InputField[Dynamic[SecondFriend]]},
{InputField[Dynamic[ThirdFriend]],
InputField[Dynamic[FourthFriend]]},
{InputField[Dynamic[FifthFriend]]},

{},
{"Input Relationship Data Here:"},
{Row[{Dynamic[FirstFriend]," ",PopupMenu[Dynamic[Rule1],{0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[SecondFriend]}],
Row[{Dynamic[FirstFriend]," ",PopupMenu[Dynamic[Rule2], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[ThirdFriend]}]},
{Row[{Dynamic[FirstFriend]," ",PopupMenu[Dynamic[Rule3], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FourthFriend]}],
Row[{Dynamic[FirstFriend]," ",PopupMenu[Dynamic[Rule4], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FifthFriend]}]},
{},
{Row[{Dynamic[SecondFriend]," ",PopupMenu[Dynamic[Rule5], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FirstFriend]}],
Row[{Dynamic[SecondFriend]," ",PopupMenu[Dynamic[Rule6], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[ThirdFriend]}]},
{Row[{Dynamic[SecondFriend]," ",PopupMenu[Dynamic[Rule7], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FourthFriend]}],
Row[{Dynamic[SecondFriend]," ",PopupMenu[Dynamic[Rule8], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FifthFriend]}]},
{},
{Row[{Dynamic[ThirdFriend]," ",PopupMenu[Dynamic[Rule9], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FirstFriend]}],
Row[{Dynamic[ThirdFriend]," ",PopupMenu[Dynamic[Rule10], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[SecondFriend]}]},
{Row[{Dynamic[ThirdFriend]," ",PopupMenu[Dynamic[Rule11], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FourthFriend]}],
Row[{Dynamic[ThirdFriend]," ",PopupMenu[Dynamic[Rule12], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FifthFriend]}]},
{},
{Row[{Dynamic[FourthFriend]," ",PopupMenu[Dynamic[Rule13],{0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FirstFriend]}],
Row[{Dynamic[FourthFriend]," ",PopupMenu[Dynamic[Rule14], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[SecondFriend]}]},
{Row[{Dynamic[FourthFriend]," ",PopupMenu[Dynamic[Rule15], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[ThirdFriend]}],
Row[{Dynamic[FourthFriend]," ",PopupMenu[Dynamic[Rule16], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FifthFriend]}]},
{},
{Row[{Dynamic[FifthFriend]," ",PopupMenu[Dynamic[Rule17], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FirstFriend]}],
Row[{Dynamic[FifthFriend]," ",PopupMenu[Dynamic[Rule18], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[SecondFriend]}]},
{Row[{Dynamic[FifthFriend]," ",PopupMenu[Dynamic[Rule19], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[ThirdFriend]}],
Row[{Dynamic[FifthFriend]," ",PopupMenu[Dynamic[Rule20], {0->"is Neutral Towards",1->"is a Friend of",2->"Loves",-2->"Despises"}]," ", Dynamic[FourthFriend]}]},

{},
{},
{"Path Weight Rules:","All Paths and Weights:"},
{Dynamic[PathWeightRules={{FirstFriend,SecondFriend}->Rule1+Rule5,
{FirstFriend,ThirdFriend}->Rule2+Rule9,
{FirstFriend,FourthFriend}->Rule3+Rule13,
{FirstFriend,FifthFriend}->Rule4+Rule17,
{SecondFriend,FirstFriend}->Rule5+Rule1,
{SecondFriend,ThirdFriend}->Rule6+Rule10,
{SecondFriend,FourthFriend}->Rule7+Rule14,
{SecondFriend,FifthFriend}->Rule8+Rule18,
{ThirdFriend,FirstFriend}->Rule9+Rule2,
{ThirdFriend,SecondFriend}->Rule10+Rule6,
{ThirdFriend,FourthFriend}->Rule11+Rule15,
{ThirdFriend,FifthFriend}->Rule12+Rule19,
{FourthFriend,FirstFriend}->Rule13+Rule3,
{FourthFriend,SecondFriend}->Rule14+Rule7,
{FourthFriend,ThirdFriend}->Rule15+Rule11,
{FourthFriend,FifthFriend}->Rule16+Rule20,
{FifthFriend,FirstFriend}->Rule17+Rule4,
{FifthFriend,SecondFriend}->Rule18+Rule8,
{FifthFriend,ThirdFriend}->Rule19+Rule12,
{FifthFriend,FourthFriend}->Rule20+Rule16}],

Dynamic[AllPathsAndWeights=Map[PathWeightFunction,Permutations[{FirstFriend,SecondFriend,ThirdFriend,FourthFriend,FifthFriend}]]],

PathWeightFunction[PossibleSeatingChart_]:={PossibleSeatingChart,Total[Partition[PossibleSeatingChart,2,1]/.PathWeightRules]};}

},

Alignment->Left,ItemStyle->{Automatic,Automatic,{{1,1}->Directive[FontSize->17,Bold],{1,2}->Directive[FontSize->17,Bold],{3,1}->Directive[White],{4,1}->Directive[FontSize->17,Bold],{9,1}->Directive[FontSize->17,Bold],{26,1}->Directive[FontSize->17,Bold],{26,2}->Directive[FontSize->17,Bold],{27,1}->Directive[FontSize->4],{27,2}->Directive[FontSize->4]}}]
]