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.
Medium Question #1 concerns determining the minimum balanced ternary string that can be obtained by replacing the minimum number of digits in a given ternary string. The question reads:
ASU SoDA Coding Challenge VI Medium Question 1: Balanced String Problem
You are given a string s consisting of exactly n characters, and each character is either '0', '1' or '2'. Such strings are called ternary strings.
Your task is to replace minimum number of characters in this string with other characters to obtain a balanced ternary string (balanced ternary string is a ternary string such that the number of characters '0' in this string is equal to the number of characters '1', and the number of characters '1' (and '0' obviously) is equal to the number of characters '2').
Among all possible balanced ternary strings you have to obtain the lexicographically (alphabetically) smallest.
Note that you can neither remove characters from the string nor add characters to the string. Also note that you can replace the given characters only with characters '0', '1' and '2'.
It is guaranteed that the answer exists.
Input
An array of characters consisting of exactly n characters '0', '1' and '2'.
Output
Print one string — the lexicographically (alphabetically) smallest balanced ternary string which can be obtained from the given one with minimum number of replacements.
Because n is divisible by 3 it is obvious that the answer exists. And it is obvious that there is only one possible answer.
Test Cases:
input
121
output
021
input
000000
output
001122
input
211200
output
211200
input
120110
output
120120
My solution for this problem is quite messy, so I apologize if it’s difficult to understand. Here’s my solution:
Solution #1: Casework Approach
First we count the number of 0’s, 1’s, and 2’s in the string. To minimize the number of replacements, any digit with more than the average frequency must be replaced with digits with less than the average frequency. By doing casework on which digits have larger than average frequency and which digits have lower than average frequency, it is possible, to find the corresponding minimal balanced string. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
SoDA Coding Challenge VI Medium Problem #1
https://docs.google.com/document/d/14sk0u9ZVM1rrIsSCSwIWesI1ks8BukFMaT-NlJCr6FQ/edit
'''
import time
import sys
for x in sys.stdin:
myInput = x
def getBalancedString(myString):
l = len(myString)/3
zeros = []
ones = []
twos = []
for i in range(len(myString)):
if myString[i]=="0":
zeros.append(i)
elif myString[i]=="1":
ones.append(i)
else:
twos.append(i)
l1 = len(zeros)
l2 = len(ones)
l3 = len(twos)
if(l1==l2 and l1==l3):
return myString
t = (abs(l1-l)+abs(l2-l)+abs(l3-l))/2
if(l<l1):
if(l<l2):
o = l2-l
for i in ones[l2-o:l2]:
myString = myString[0:i]+"2"+myString[i+1:]
for i in zeros[l1-t+o:l1]:
myString = myString[0:i]+"2"+myString[i+1:]
elif(l<l3):
o = l3-l
for i in twos[0:o]:
myString = myString[0:i] + "1" + myString[i+1:]
for i in zeros[l1-t+o:l1]:
myString = myString[0:i] + "1" + myString[i+1:]
else:
o = l-l3
for i in zeros[l1-o:l1]:
myString = myString[0:i]+"2"+myString[i+1:]
for i in zeros[l1-t:l1-o]:
myString = myString[0:i]+"1"+myString[i+1:]
return myString
elif(l==l1):
if (l2<l3):
for i in twos[0:t]:
myString = myString[0:i]+"1"+myString[i+1:]
else:
for i in ones[l2-t:l2]:
myString = myString[0:i]+"2"+myString[i+1:]
return myString
else:
if(l2<l):
o = l-l2
for i in twos[t-o:t]:
myString = myString[0:i]+"1"+myString[i+1:]
for i in twos[0:t-o]:
myString = myString[0:i]+"0"+myString[i+1:]
elif(l3<l):
o = l-l3
for i in ones[0:t-o]:
myString = myString[0:i]+"0"+myString[i+1:]
for i in ones[l2-o:l2]:
myString = myString[0:i]+"2"+myString[i+1:]
else:
o = l2-l
for i in ones[0:o]:
myString = myString[0:i]+"0"+myString[i+1:]
for i in twos[0:t-o]:
myString = myString[0:i]+"0"+myString[i+1:]
return myString
start = time.time()
print getBalancedString(myInput)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
120120
--- 1.69277191162e-05 seconds ---
for input of myInput = "120110"
'''
And with that, we’re done. I apologize if my solution was a bit messy, but I thought that casework was the simplest method for solving this problem. This is a great example of a problem that is intuitively easy for humans to solve but somewhat difficult for a human to implement a solution.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 