snichols@therealm.io
BAN USERC++ solution. Tricky but fun problem!
#include <array>
#include <limits>
#include <iostream>
int main(void)
{
std::array<int, 10> values {0, 1, 5, 3, 2, 8, 9, 9, 0, 11};
int maxLeft = std::numeric_limits<int>::min();
int maxIndex = 0;
int minRight = std::numeric_limits<int>::max();
int minIndex = 0;
int leftIndex = 0;
int rightIndex = values.size()-1;
for(;;)
{
auto leftValue = values[leftIndex];
auto rightValue = values[rightIndex];
if(leftValue > maxLeft)
{
maxLeft = leftValue;
maxIndex = leftIndex;
}
if(rightValue < minRight)
{
minRight = rightValue;
minIndex = rightIndex;
}
leftIndex++;
rightIndex--;
if(leftIndex >= rightIndex)
break;
}
if(maxLeft < minRight)
{
std::cout << "#" << minRight << " at index " << minIndex << " is a match!" << std::endl;
}
else
{
std::cout << "no match!" << std::endl;
}
return 0;
}
C++ solution. Pretty simple.
#include <vector>
#include <type_traits>
#include <iostream>
template<typename IteratorType, typename ResultType>
void pushRest(IteratorType && it, IteratorType && end, ResultType && result)
{
while(it != end)
result.push_back(*it++);
}
template<typename IteratorType, typename ValueType, typename ResultType>
IteratorType pushUntilGreaterEqual(IteratorType && it, IteratorType && end, ValueType && comparand, ResultType && result)
{
while(it != end)
{
auto value = *it;
if(value >= comparand)
break;
result.push_back(value);
it++;
}
return it;
}
template<typename IteratorType, typename ValueType>
IteratorType skipDuplicates(IteratorType && it, IteratorType && end, ValueType && value)
{
while(it != end && value == *it)
it++;
return it;
}
template<typename T>
typename std::remove_reference<T>::type merge(T &&left, T &&right)
{
typename std::remove_reference<T>::type result;
auto lit = left.cbegin();
auto rit = right.cbegin();
auto lend = left.cend();
auto rend = right.cend();
for(;;)
{
if(lit == lend)
{
// done with left, push rest of right
pushRest(rit, rend, result);
break;
}
else if(rit == rend)
{
// done with right, push rest of left
pushRest(lit, lend, result);
break;
}
else
{
auto leftValue = *lit;
auto rightValue = *rit;
if(leftValue == rightValue)
{
// equal values, push one and advance until not equal
result.push_back(leftValue);
lit = skipDuplicates(lit, lend, leftValue);
rit = skipDuplicates(rit, rend, rightValue);
}
else if(leftValue < rightValue)
{
// left is lower, push values from left until this isn't so
lit = pushUntilGreaterEqual(lit, lend, rightValue, result);
}
else if(rightValue < leftValue)
{
// right is lower, push values from right until this isn't so
rit = pushUntilGreaterEqual(rit, rend, leftValue, result);
}
}
}
return result;
}
int main(void)
{
std::vector<int> a {0, 0, 1, 5, 7, 19, 19, 19, 19, 21};
std::vector<int> b {-50, -45, -12, 19, 19, 19, 19, 19, 19, 19, 20, 22, 5000};
auto result = merge(a, b);
for(auto value : result)
std::cout << value << " ";
std::cout << std::endl;
return 0;
}
#include <string>
#include <iostream>
enum class CharacterType
{
Digit,
OpenBracket,
CloseBracket,
Text,
Terminate
};
static CharacterType characterType(const char ch)
{
switch(ch)
{
case 0:
return CharacterType::Terminate;
case '[':
return CharacterType::OpenBracket;
case ']':
return CharacterType::CloseBracket;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
return CharacterType::Digit;
default:
return CharacterType::Text;
}
}
static uint32_t parseNumber(const char *start, const char *end)
{
const char *digitPointer = end-1;
uint32_t result = 0;
uint32_t multiplier = 1;
while(digitPointer >= start)
{
char digit = *digitPointer--;
result += (digit - '0') * multiplier;
multiplier *= 10;
}
return result;
}
static const char *expand(uint32_t repeatCount, const char * const input, std::string &result)
{
char ch;
CharacterType type;
const char *pointer;
while(repeatCount > 0)
{
repeatCount--;
pointer = input;
for(;;)
{
ch = *pointer;
type = characterType(ch);
if(type == CharacterType::Terminate)
break;
if(type == CharacterType::Digit)
{
const char *lastDigitPointer = pointer+1;
while(characterType(*lastDigitPointer) == CharacterType::Digit)
lastDigitPointer++;
uint32_t childRepeatCount = parseNumber(pointer, lastDigitPointer);
pointer = lastDigitPointer;
ch = *pointer;
type = characterType(ch);
if(type == CharacterType::OpenBracket)
{
pointer = expand(childRepeatCount, pointer+1, result);
}
else if(type == CharacterType::Text)
{
while(childRepeatCount>0)
{
result.push_back(ch);
childRepeatCount--;
}
++pointer;
type = characterType(ch);
}
}
else if(type == CharacterType::Text)
{
result.push_back(ch);
++pointer;
}
else if(type == CharacterType::OpenBracket)
{
pointer = expand(1, pointer+1, result);
}
else if(type == CharacterType::CloseBracket)
{
++pointer;
break;
}
}
}
return pointer;
}
std::string decode(const std::string &input)
{
std::string result;
expand(1, input.c_str(), result);
return result;
}
int main(void)
{
auto result = decode("3[a2[bd]g4[ef]h]");
std::cout << result << std::endl;
return 0;
}
C++ solution. Very fast. Early out when run length exceeds remaining search space.
- snichols@therealm.io January 26, 2017