Created
January 16, 2017 23:53
-
-
Save jianminchen/d3134517ab63c09c47c711832c1b7427 to your computer and use it in GitHub Desktop.
HackerRank week code 28 - suffix rotation - continue to look into issues and do code review, prepare to submit a code review on stackexchange.com
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
using System.IO; | |
using System.Linq; | |
class Solution | |
{ | |
internal class Rotations | |
{ | |
/* | |
* Put a test case here. | |
* cababc | |
* C# String.Join(string separator, string[] value, int startIndex, int count) | |
* | |
* Review rotation definition | |
*/ | |
public static string RotateClockwise(string[] input, int start) | |
{ | |
int length = input.Length; | |
string afterRotation = string.Join("", input, start, length - start); | |
afterRotation += string.Join("", input, 0, start); | |
return afterRotation; | |
} | |
} | |
internal class StringHelper | |
{ | |
/* | |
* "aabbcc" | |
* result is "abc" | |
* remove duplicate chars if they are in the sequence, just keep distinct chars | |
* For example, "aaab" will be compressed to "ab" | |
*/ | |
public static void RunFunctionTest_CompressChars() | |
{ | |
Debug.Assert(StringHelper.CompressChars("aabbcc").CompareTo("abc") == 0); | |
Debug.Assert(StringHelper.CompressChars("ccbbaa").CompareTo("cba") == 0); | |
Debug.Assert(StringHelper.CompressChars("cababc").CompareTo("cababc") == 0); | |
Debug.Assert(StringHelper.CompressChars("caababc").CompareTo("cababc") == 0); | |
} | |
/* | |
* understand the design here... | |
* write a test case for the function. | |
* https://msdn.microsoft.com/en-us/library/system.linq.enumerable.range(v=vs.110).aspx | |
*/ | |
public static string CompressChars(string input) | |
{ | |
var inputc = Enumerable.Range(0, input.Length).Where(i => i == 0 || input[i] != input[i - 1]).Select(i => input[i]).ToArray(); | |
return new string(inputc); | |
} | |
} | |
internal class ArrayHelper | |
{ | |
/* merge last and first two string, and then resize the array to the size - reduce size by minusing one | |
* test case: "cababc", {"c","b","bc"}, merge first one and last one. | |
* Since rotation can go to two directions | |
* Array {"c","b","bc"} -> resize to {"bcc","b"} | |
*/ | |
public static void MergeFirstAndLastNode(ref string[] strings) | |
{ | |
int length = strings.Length; | |
strings[0] = strings[length - 1] + strings[0]; | |
Array.Resize(ref strings, length - 1); | |
} | |
} | |
/* | |
* source code study: | |
* https://www.hackerrank.com/rest/contests/w28/challenges/suffix-rotation/hackers/feliandrade/download_solution | |
* | |
* work on sample test case: | |
* "cababc" | |
*/ | |
static void Main(String[] args) | |
{ | |
//ProcessInput(); | |
RunTestcase_cababc(); | |
//StringHelper.RunFunctionTest_CompressChars(); | |
} | |
public static void RunTestcase_cababc() | |
{ | |
int result = GetMinimumMoves("cababc"); | |
} | |
public static void ProcessInput() | |
{ | |
int queries = Convert.ToInt32(Console.ReadLine()); | |
for (int i = 0; i < queries; i++) | |
{ | |
string s = Console.ReadLine(); | |
Console.WriteLine(GetMinimumMoves(s)); | |
} | |
} | |
/* | |
* Find minimum moves to get lexicographic minimum string | |
* "cababc", minChars will be "abc" | |
*/ | |
private static int GetMinimumMoves(string input) | |
{ | |
var minChars = input.Distinct().OrderBy(c => c).ToArray(); | |
return CalculateMinimumMoves(input, minChars, 0); | |
} | |
static Dictionary<string, int> memo = new Dictionary<string, int>(); | |
/* | |
* "cababc" | |
* To get the lexicographic smallest string | |
* | |
* Rotation definition: | |
* either clockwise or anticlockwise | |
* | |
* @input | |
* @pointerPosition - start from 0 to last char in the string @input | |
* | |
* Use dynamic programming | |
* recursive function - | |
* | |
* Most important, need to do time analysis: | |
* Avoid timeout issue | |
*/ | |
private static int CalculateMinimumMoves(string input, char[] minChars, int pointerPosition) | |
{ | |
if (input.Length == 1) | |
{ | |
return 0; | |
} | |
input = StringHelper.CompressChars(input); | |
var currentChar = minChars[pointerPosition]; | |
if (input.Length == 1) | |
{ | |
return 0; | |
} | |
if (input[0] == currentChar) | |
{ | |
input = input.Substring(1); | |
} | |
if (input.Length == 1) | |
{ | |
return 0; | |
} | |
if (memo.ContainsKey(input)) | |
{ | |
return memo[input]; | |
} | |
var multipleChoices = input.Split(currentChar); // work on cababc, Split('a')->{"c","b","bc"} | |
int minimumMoves = int.MaxValue; | |
if (multipleChoices.Length == 1) | |
{ | |
minimumMoves = CalculateMinimumMoves(input, minChars, pointerPosition + 1); | |
} | |
else | |
{ | |
ArrayHelper.MergeFirstAndLastNode(ref multipleChoices); | |
var optimalExists = false; | |
for (int start = 0; start < multipleChoices.Length; start++) | |
{ | |
int length = multipleChoices.Length; | |
var currentOne = multipleChoices[start]; | |
var toCompare = multipleChoices[(start + length - 1) % length]; | |
// try to figure out what two chars are compared, | |
// go over the example and figure out what is doing here, the checking ... | |
// cababc -> {"b","bcc"} | |
// First iteration: | |
// bcc b | |
// ^ ^ | |
// | | | |
// optimalExists if checking fails, do nothing. | |
// Second iteration: | |
// b bcc | |
// ^ ^ | |
// | | | |
// 'b' != 'c' | |
// need to do optimal selection here ... | |
// those two chars can be next to each other when to rotate | |
char[] optimalExistsChecking = { | |
currentOne[0], | |
minChars[pointerPosition + 1], | |
toCompare[toCompare.Length - 1] | |
}; | |
if (optimalExistsChecking[0] == optimalExistsChecking[1] && | |
optimalExistsChecking[0] != optimalExistsChecking[2]) | |
{ | |
optimalExists = true; | |
string afterRotation = Rotations.RotateClockwise(multipleChoices, start); | |
var movesNeeded = CalculateMinimumMoves(afterRotation, minChars, pointerPosition + 1); | |
if (movesNeeded < minimumMoves) | |
{ | |
minimumMoves = movesNeeded; | |
} | |
} | |
} | |
if (!optimalExists) | |
{ | |
string nextInput = string.Join("", multipleChoices, 0, multipleChoices.Length); | |
minimumMoves = CalculateMinimumMoves(nextInput, minChars, pointerPosition + 1); | |
} | |
minimumMoves += multipleChoices.Length; | |
} | |
if (pointerPosition > 0) | |
{ | |
memo[input] = minimumMoves; | |
} | |
return minimumMoves; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment