Q solution to LeetCode #649

leetcode649.q

// Generate Test Senate
PARTIES:"DR";
partyDict:"DR"!("Dire";"Radiant");
genSenate:{[x] x?PARTIES};

// Utility functions

// If one party controls 2/3 (2:1 ratio) or more of the senate, they will win
// This function will compare the party counts 
//     if one has super majority, it will return the party name
//     if no party has super majority, it will return null
superMajority:{[x] first where 2<=3*(count each group x)%count x}

// If there is no super majority, parties will take turns banning each other
// It is assumed that the most advantageous move is to ban the next opposing party member in line
// After one senator votes, they will move to the end of the voting line and wait for their turn again
ban1:{[x] cp:first where x<>x 0; 1 rotate raze (cp#;_[cp+1])@\:x}

// Method 1 - Recursion 
func:{[senate] $[null winner:superMajority senate; .z.s ban1 senate; :partyDict winner] }

// Method 2 - While loops
// Recursive method is subject to 'stack error at larger senate sizes
func2:{[senate] while[null winner:superMajority senate; senate:ban1 senate]; :partyDict winner}


// Optimizations

// Multi-member ban
// Multiple senate members of the same party in a row present a huge advantage
// They can act as a "block" voting at the same time to eliminate the next 'n' members of the opposing party
// This will reduce the number of iterations we will need to acheive a super majority
// This function determines how many members of the same party are located in a row (as 'n')
//     then it will delete the next 'n' members of the opposing party
//     finally it will rotate the voting list by 'n'
banMulti:{[x] n rotate x where @[count[x]#1b;(n:first o) sublist o:where x<>x 0;not]}