On Sunday, November 24, 2019, I participated in the ASU SoDA Coding Challenge VI. The ASU Software Developer’s Association (SoDA) is a club that is dedicated to teaching aspiring programmers how to solve complex problems that will prepare them for industry. The club runs recruiting events, Hackathons, Interview Prep sessions, and other activities that I have personally found invaluable during my first semester at ASU. I would strongly recommend anyone with a remote interest in computer science to join the club.
The SoDA Coding Challenge had 15 questions which were divided into three categories of three questions based on their respective difficulty levels. The Easy Questions, the Medium Questions, and the Hard Questions were made available to the contestants through Google Forms, and participants would have proctors manually check their code to make sure their programs worked.
Easy Question #2 concerns determining whether a given outcome of a repeated game is possible. The question reads:
ASU SoDA Coding Challenge VI Easy Question 2: 3 Person Chess
Alex, Bob and Carl will soon participate in a team chess tournament. Since they are all in the same team, they have decided to practise really hard before the tournament. But it's a bit difficult for them because chess is a game for two players, not three.
So they play with each other according to following rules:
Alex and Bob play the first game, and Carl is spectating;
When the game ends, the one who lost the game becomes the spectator in the next game, and the one who was spectating plays against the winner.
Alex, Bob and Carl play in such a way that there are no draws.
Today they have played n games, and for each of these games they remember who was the winner. They decided to make up a log of games describing who won each game. But now they doubt if the information in the log is correct, and they want to know if the situation described in the log they made up was possible (that is, no game is won by someone who is spectating if Alex, Bob and Carl play according to the rules). Help them to check it!
Input:
The first parameter contains one integer n (1 ≤ n ≤ 100) — the number of games Alex, Bob and Carl played.
The second parameter entered as an array, describing the game log. i-th line contains one integer ai (1 ≤ ai ≤ 3) which is equal to 1 if Alex won i-th game, to 2 if Bob won i-th game and 3 if Carl won i-th game.
Output:
Print YES if the situation described in the log was possible. Otherwise print NO.
Test Cases:
input
3
1
1
2
output
YES
input
2
1
2
output
NO
This problem was also a good warm up for the complex questions in the competition. Here’s my solution:
Solution #1: O(n) Approach
We simply keep track of the spectator after each game, and if the winner is ever equal to the spectator, we know the outcome is impossible. After a little thought, you can convince yourself that this is the only condition for determining whether an outcome is possible. Here’s an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
SoDA Coding Challenge VI Easy Problem #2
https://docs.google.com/document/d/1E_8BtPkGH5iQSBVOxr_lZpjrS5pToaWtDBS1WEZTxWw/edit
'''
import time
import sys
myInput = []
i = 0
for x in sys.stdin:
if(i>0):
myInput.append(int(x))
else:
n = int(x)
i+=1
def isPossible(myList):
spectator = 3
for x in myList:
if x==spectator:
return "NO"
temp = spectator
if(temp==3):
if(x==1):
spectator=2
else:
spectator=1
elif(temp==2):
if(x==1):
spectator=3
else:
spectator=1
else:
if(x==2):
spectator=3
else:
spectator=2
return "YES"
start = time.time()
print isPossible(myInput)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
NO
--- 9.05990600586e-06 seconds ---
for input of n = 12, myInput = [1,1,2,1,2,1,3,1,2,3,1,1]
'''
And with that, we’re done. Once again, I thought this was a good problem. It is not completely trivial, but it can be understood by people without USACO experience. During the competition, I heard more people discuss this question than nearly any other question.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 