Create a gist now

Instantly share code, notes, and snippets.

@mattsan /ramen-2.cpp Secret
Created Oct 25, 2015

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
static std::string to_hex(unsigned long int n, int digits)
{
std::ostringstream oss;
oss.fill('0');
oss << std::hex << std::setw(digits) << n;
return oss.str();
}
static std::string solve(const std::string& input)
{
unsigned long int seats = 0;
for(std::string::const_iterator i = input.begin(); i != input.end(); ++i)
{
const int visitors = *i - '0';
const std::string visitors_s = std::string(visitors, '0');
std::string::size_type index = std::string::npos;
do
{
seats = (seats >> 1) & 0x77777777lu;
} while((index = to_hex(seats * 0x100000001lu, 16).find(visitors_s)) == std::string::npos);
seats |= (((((1lu << (visitors * 4)) - 1) * 0x100000001lu) << ((8 - visitors) * 4) >> (index * 4)) & 0x44444444lu);
}
return to_hex((seats | (seats >> 1) | (seats >> 2)) & 0x11111111u, 8);
}
static void test(const std::string& input, const std::string& expected)
{
const std::string actual = solve(input);
if(expected == actual)
{
std::cout << "PASSED" << std::endl;
}
else
{
std::cout << "FAILED input " << input << ", expected " << expected << ", actual " << actual << std::endl;
}
}
int main(int, char* [])
{
test("3316", "11111110");
return 0;
}
def solve(input)
seats = 0
input.split('').map(&:to_i).each do |visitors|
begin
seats = (seats >> 1) & 0x77777777
end until (index = ('%016x' % (seats * 0x100000001)).index('0' * visitors))
seats |= (((((1 << (visitors * 4)) - 1) * 0x100000001) << ((8 - visitors) * 4) >> (index * 4)) & 0x44444444)
end
'%08x' % ((seats | (seats >> 1) | (seats >> 2)) & 0x11111111)
end
def test(input, expected)
actual = solve(input)
if expected == actual
puts "PASSED"
else
puts "FAILED input #{input}, expected #{expected}, actual #{actual}"
end
end
test("3316", "11111110")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment