Coding Challenge 5 - Meme Graveyard Keeper

[chili]

　　　　　　　　　　　　　　　Meme Graveyard Keeper

Challenge Page: https://patdash.planetchili.net/challenges/2
Announcement Video: https://youtu.be/JAA19vXSRto
Guide Video: https://youtu.be/63uc34wNSdk
Results/Solution: https://youtu.be/h2D-2L0lbzQ
Ultimate Solution: https://patdash.planetchili.net/series/4 (*see notes below)

Problem Statement
You are given a struct that contains A) a field size and B) a std::vector of commands. Each command has 3 parameters: i) quantity, ii) offset, and iii) count. Each command encodes an operation on an array of ints g[fieldsize] (field of meme graves) in which you add the value quantity to a contiguous range of elements in the array g (bury memes in the graves). Quantity indicates amount to add to each element. Offset indicates start element. Count indicates the number of elements to act on. Return the maximum value in g after all commands have been executed. Each element of g starts with a value of 0.

Start Code
Available on the challenge page (see link above). Also see the guide video (link above).

Problem Conditions
1 <= fieldsize <= max unsigned int
0 <= quantity <= max int
0 <= offset <= fieldsize - 1
1 <= count <= fieldsize - offset
1 <= commands.size() <= 8000000

Code Conditions
Write your solution in Solution.cpp (follow the directions in that file). Code will be compiled/evaluated using VS2017 C++ compiler in x64 configuration. You may use the stdlib + visual studio compiler intrinsics, but no other libraries. If code is suspected of potentially trying to subvert the test or the test system, it will be rejected (so do not obfuscate).

Test Conditions
Test will run on Intel i7 4770k (Haswell) CPU. You may not consume more than 1 GB ram in total. Algorithm must complete within 3000ms.

Submission
Submit on the challenge page (link above). See challenge page for submission deadline. Submit only your Solution.cpp file as a zip archive. The name of the zip archive itself does not matter, but must have the .zip extension. Zipped solution must be less than 20kb in size. See the guide video (link above) for a walk-through on submission.

Scoring
Full points given for passing all tests. Part points given for passing all low-n tests but timing out on high-n. Mono bounties for top 3 fastest algorithms and the earliest submission that passes all tests. Poly bounty for beating Chili in speed performance. Poly bounty also available for supplying test data that breaks Chili solution. See challenge page for details on the number of algos awarded.

Notes

• See announcement video for additional explanation. Discussion / questions should happen here rather than in the comments on the announcement video (I will not answer clarification questions in the comments).
• Bounty for "Break Chili" will be awarded by providing a valid dataset that breaks Chili's published solution code. Provide data on forum or Discord.
• As the second run with the new system, this is still somewhat of a beta test. Expect that there might be some bumps in the road.
• Ultimate Solution will be unlockable on the patron-exclusive challenge playlist soon after the basic solution video is released.
• Max runtime updated 11.5
• Some challenges will not have an Ultimate Solution.

[Slidy]

Here's a python script to generate test files, it doesn't generate the answer for you so you'll have to fill that in manually.

Code: Select all

import random

MAX_UINT = 4294967296

fieldsize = random.randint(1, MAX_UINT)
num_commands = random.randint(1, 8000000)

with open('Test.txt', 'w') as file:
    file.write("Slidy's Test (" + format(num_commands, ',') + " Commands, " + format(fieldsize, ',') + " Field Size)\n")
    file.write("0\n")
    file.write(str(fieldsize) + '\n')
    for i in range(num_commands):
        quantity = random.randint(0, MAX_UINT)
        offset = random.randint(0, fieldsize - 1)
        count = random.randint(1, fieldsize - offset)
        file.write(str(quantity) + ' ' + str(offset) + ' ' + str(count) + '\n')

It generates up to several hundred MB worth of data, so I decided not to use it (or rather my computer decided not to "IOError: [Errno 28] No space left on device"). I'll probably go with generating the data dynamically to save on both disk space and run-time.

[Slidy]

Here's a test we can all use as a baseline generated using my python script: https://mega.nz/#!k4lViIrT!wijBZsLVJARL ... hgBT4YJKaQ

Using a naive solution I get the following results:

Code: Select all

PASS (0.00ms) File Test: Buck Futter's Sexy Test 1
PASS (0.00ms) File Test: Buck Futter's Sexy Test 2
PASS (0.00ms) File Test: Buck Futter's Sexy Test 3
PASS (0.00ms) File Test: Buck Futter's Sexy Test 4
PASS (840.73ms) File Test: Slidy's Test (1,798,592 Commands, 2,645 Field Size)

[Slidy]

Optimized algorithm results:

Code: Select all

PASS (0.01ms) File Test: Buck Futter's Sexy Test 1
PASS (0.00ms) File Test: Buck Futter's Sexy Test 2
PASS (0.00ms) File Test: Buck Futter's Sexy Test 3
PASS (0.00ms) File Test: Buck Futter's Sexy Test 4
PASS (153.04ms) File Test: Slidy's Baseline Test (1,798,592 Commands, 2,645 Field Size)
PASS (52.10ms) Slidy's Test (659,562 Commands, 1,610,754,479 Field Size)
PASS (466.84ms) Slidy's Test (4,711,410 Commands, 2,621,936,526 Field Size)
PASS (60.65ms) Slidy's Test (730,112 Commands, 3,780,355,003 Field Size)
PASS (377.97ms) Slidy's Test (4,023,170 Commands, 382,510,701 Field Size)
PASS (490.96ms) Slidy's Test (5,687,800 Commands, 4,276,620,824 Field Size)
PASS (459.11ms) Slidy's Test (5,513,761 Commands, 1,090,378 Field Size)
PASS (418.93ms) Slidy's Test (4,695,739 Commands, 3,473,657,922 Field Size)
PASS (132.15ms) Slidy's Test (1,694,388 Commands, 2,694,292,550 Field Size)
PASS (208.49ms) Slidy's Test (2,596,053 Commands, 4,252,267,227 Field Size)
PASS (16.06ms) Slidy's Test (228,432 Commands, 1,648,507,950 Field Size)

[colencon]

My result, with async 4 thread

Code: Select all

PASS (0.02ms) File Test: Buck Futter's Sexy Test 1
PASS (0.00ms) File Test: Buck Futter's Sexy Test 2
PASS (0.00ms) File Test: Buck Futter's Sexy Test 3
PASS (0.00ms) File Test: Buck Futter's Sexy Test 4
PASS (272.60ms) File Test: Slidy's Test (1,798,592 Commands, 2,645 Field Size)

[thesmallcreeper]

> 1 <= fieldsize <= max unsigned int (aka fieldsize <= 2^32)
> Each command encodes an operation on an array of ints g[fieldsize]

> You may not consume more than 1 GB ram in total.

Looks like some of the rules may have contradiction between them...

P.S: Havent any idea how such program should behave but Slidy are you sure that your program stress all of your array?

[NightFighter]

yeah, I'm having the same problem as thesmallcreeper. I tried to create a file with max field size and commands and when initialising a vector with size as fieldsize(uint 32 max) it failed as it tried to allocate 31 gigs of data (the vector is <unsigned long long> btw)

[albinopapa]

There's nothing stopping chili from creating a vector that takes up 4GB of memory, since he's using his machine for the test. I would persoanlly cap your field size to 1024 * 1024 * 1024 if that's really what you want, surely you can verify any and all results with a field size of 1 GB.

The commands vector will be 12 bytes to 96,000,000 bytes alone, so keep that in mind if you are limited on RAM.

[thesmallcreeper]

Hey! I created a random test generator that you can download over here:

https://www.dropbox.com/s/bscy2t75pnklh ... r.zip?dl=0

How-to use it:

1. Unzip all the files
2. Take one of your Solution.cpp that you are 100% that create correct results and paste it at the same folder overwriting the default Solution.cpp (if you like number 69 as much as chili you can skip this step )
3. Compile using "Release" and "x64" because default option is "Debug" and iirc debug sucks when it comes to I/O
4. Open cmd with working folder the folder that contains the TestGenerator.exe you just created
5. Type what you want like this:

Code: Select all

testgenerator <desired commands count> <desired field size> <average count> <count +- range>

Use M for x2^20 , K for x2^10 and U for x1 (aka 2^0 and sorry you have to :/)

Examples:

Code: Select all

testgenerator 1 M 4 K 2 K 512 U

Will generate a test file with 1048576 commands, 4096 field size, 2048 average count and count range from 1536 up to 2560.

Code: Select all

testgenerator 1 M 3 K 2 K 0 U

testgenerator 1 M 3 K 2 K 0 U

Will generate a test file with 1048576 commands, 3072 field size, 2048 average count, count range from 2048 up to 2048

Code: Select all

testgenerator 1 M 4 K 2 K 2 K

Will generate a test file with 1048576 commands, 4096 field size, 2048 average count, count range from 1 up to 4095


Notes:
1. Haven't test is too much. You might find a bug :/
2. It isnt user friendly or "safe".
3. yeah, yeah. My code brings some cancer to the chili planet. Long live C's C++ style.
4. Average count is not accurate especially if you count range is relative big.
5. gl hf <3

[Slidy]

Here's another method of creating tests:

Spoiler:

Code: Select all

#pragma once
#include "TestCase.h"
#include <random>
#include <iomanip>
#include <sstream>
#include <string>

using namespace std::chrono_literals;

class TestCaseEmbeds : public TestCase
{
public:
	TestCaseEmbeds( std::chrono::duration<int,std::milli> timeoutMilli,std::string casename,bool advanced )
		:
		TestCase( timeoutMilli,std::move( casename ),advanced )
	{}
protected:
	Output& GetExpected_() override
	{
		return expected;
	}
	Input& GetInput_() override
	{
		return input;
	}
protected:
	Input input;
	Output expected;
};

class RandomTestCase : public TestCaseEmbeds
{
public:
	RandomTestCase( bool advanced = false, std::chrono::duration<int, std::milli> timeoutMilli = 1ms )
		:
		TestCaseEmbeds( timeoutMilli, GenerateInput(), advanced )
	{}
	void SpinUp_() override
	{
		input.fieldSize = rand_fieldsize;
		input.commands.reserve( rand_numcommands );

		for( unsigned int i = 0; i < rand_numcommands; i++ )
		{
			InputCommand cmd;
			cmd.quantity = GetRandUInt( 0, UINT_MAX );
			cmd.offset = GetRandUInt( 0, rand_fieldsize - 1 );
			cmd.count = GetRandUInt( 1, rand_fieldsize - cmd.offset );
			input.commands.push_back( cmd );
		}
	}
private:
	std::string GenerateInput()
	{
		rand_fieldsize = GetRandUInt( 1, UINT_MAX );
		rand_numcommands = GetRandUInt( 1, 8000000 );

		return "Random Test (" + FormatWithCommas( rand_numcommands ) + " Commands, " + FormatWithCommas( rand_fieldsize ) + " Field Size)";
	}

	static unsigned int GetRandUInt( unsigned int min, unsigned int max )
	{
		static std::mt19937 engine( std::random_device{}() );

		using dist = std::uniform_int_distribution<unsigned int>;
		return dist{ min, max }(engine);
	}
	template<class T>
	static std::string FormatWithCommas( T value )
	{
		std::stringstream ss;
		ss.imbue( std::locale( "" ) );
		ss << std::fixed << value;
		return ss.str();
	}
private:
	std::mt19937 engine;

	unsigned int rand_fieldsize;
	unsigned int rand_numcommands;
};

class StaticTestCase : public TestCaseEmbeds
{
public:
	StaticTestCase( int numcommands, int fieldsize, bool advanced = false, std::chrono::duration<int, std::milli> timeoutMilli = 1ms )
		:
		TestCaseEmbeds( timeoutMilli, GenerateInput( numcommands, fieldsize ), advanced )
	{}
	void SpinUp_() override
	{
		input.fieldSize = fieldsize;
		input.commands.reserve( numcommands );

		for( unsigned int i = 0; i < numcommands; i++ )
		{
			InputCommand cmd;
			cmd.quantity = GetRandUInt( 0, UINT_MAX );
			cmd.offset = GetRandUInt( 0, fieldsize - 1 );
			cmd.count = GetRandUInt( 1, fieldsize - cmd.offset );
			input.commands.push_back( cmd );
		}
	}
private:
	std::string GenerateInput( unsigned int in_numcommands, unsigned int in_fieldsize )
	{
		numcommands = in_numcommands;
		fieldsize = in_fieldsize;

		return "Static Test (" + FormatWithCommas( numcommands ) + " Commands, " + FormatWithCommas( fieldsize ) + " Field Size)";
	}

	static unsigned int GetRandUInt( unsigned int min, unsigned int max )
	{
		static std::mt19937 engine( std::random_device{}() );

		using dist = std::uniform_int_distribution<unsigned int>;
		return dist{ min, max }(engine);
	}
	template<class T>
	static std::string FormatWithCommas( T value )
	{
		std::stringstream ss;
		ss.imbue( std::locale( "" ) );
		ss << std::fixed << value;
		return ss.str();
	}
private:
	std::mt19937 engine;
	unsigned int numcommands;
	unsigned int fieldsize;
};

Replace the TestCaseEmbeds.h file with the code above and add something like the following to Main.cpp:

Code: Select all

for( int i = 0; i < 10; i++ )
{
	testCases.push_back( std::make_unique<RandomTestCase>() );
}
testCases.push_back( std::make_unique <StaticTestCase>( 8000000, UINT_MAX ) );

I've found doing it this way rather than through files results in less loading time and gives you more freedom. Obviously this doesn't create a solution because then I'd have to give you solution code, but feel free to extend it to make it generate the solution as well.

On an unrelated note, after another optimization I've cut down the baseline test to about 100ms

Code: Select all

PASS (95.20ms) File Test: Slidy's Test (1,798,592 Commands, 2,645 Field Size)