CodeEval C++/Python Challenges

Solutions to the CodeEval challenges in C++/Python (2.7/3.x)

The aim is producing effective code (quick and low memory usage) and at the same time crafting it to be elegant and reusable.

• Profile
• Solutions

Languages/Compilers

The languages/compiler versions in use at CodeEval:

• C++: gcc 4.8.4 (from 2016-01-11) / gcc 4.8.1 (until 2016-01-10)
• Python 2: 2.7.6 (from 2016-01-11) / 2.7.3 (until 2016-01-10)
• Python 3: 3.4.3 (from 2016-01-11) / 3.2.3 (until 2016-01-10)

CodeEval issued a sandbox update on 2016-01-11, including updating some of the above versions. Following issues have been (are still being) observed over 2 weeks later:

• C++ Apparently random execution times / memory consumption

  Nothing below 46 ms with memory consumption around 512 bytes !!!

  New submissions on 2016-01-29 show:

  • Execution times ok (even down to 1ms from previous 2ms)
  • Memory consumption ok

• Python 2.7

  Execution times around 14ms and memory consumption 256 BYTES

  Why program in C++ anymore?

• Python 3.4

  Even if memory consumption seems a bit too high, the numbers are by no means orders of magnitude away from expected results

Notes

• C++: Some C++11 features are not fully supported in gcc 4.8.1 and have required some workarounds. It is quite often that the 10 second compilation time barrier is met if a couple of templates are thrown in (this seems to be a regular case with maps) and some things like forward_list and containers adaptors consume memory orders of magnitude above vector and hence are not used even if they would fit (conceptually) the purpose much better
• Python 3.2.3: It is curious to see that in most of the challenges the time can be up to 10x that of Python 2.7.3, whilst memory consumption is roughly a 1/2. This compensates in the points calculation but it seems rather strange. A bit more modern version of Python 3 would probably deliver different results

Challenges

The challenges below have been 100% solved. The scoring is:

• Hard: 0-100
• Medium: 0-65
• Easy: 0-35

Achieving the perfect maximum score is impossible because that would imply no time usage and no memory comsumption. Faster and leaner programs approach the perfect score for each category asymptotically. See: https://www.codeeval.com/ranking.

Code	Category	Name	Language	Score	(ms)	(bytes)
					Time	Memory
0006	Hard	Longest Common Subsequence Date: 2016-01-09	C++	99.910	4	29173
			Python 2	92.918	570	1773568
			Python 3	86.478	282	5078695
0007	Hard	Prefix Expressions Date: 2015-12-30	C++	99.791	6	74572
			Python 2	89.686	122	4068604
			Python 3	89.814	1121	1921024
0014	Hard	String Permutations Date: 2015-12-29	C++	99.952	3	11961
			Python 2	89.984	111	3967770
			Python 3	89.177	1129	2170880
0028	Hard	String Searching Date: 2016-01-06	C++	99.961	3	8924
			Python 2	89.314	112	4245328
			Python 3	89.177	270	4522754
0044	Hard	Following Integer Date: 2016-01-09	C++	99.961	3	8784
			Python 2	89.191	113	4294933
			Python 3	87.839	270	4532517
0047	Hard	Palindromic Ranges Date: 2016-01-02	C++	99.959	3	9688
			Python 2	89.509	132	4122958
			Python 3	87.507	292	4627414
0048	Hard	Discount Offers Date: 2016-01-08	C++	99.839	3	61063
			Python 2	96.580	47	1336012
			Python 3	76.620	305	9166848
0053	Hard	Repeated Substring Date: 2016-02-09	C++	99.965	2	10538
			Python 2	99.844	31	256
			Python 3	84.509	103	6281430
0069	Hard	Distinct Subsequences Date: 2016-01-01	C++	99.959	3	9772
			Python 2	89.910	120	3979474
			Python 3	88.936	1179	2166784
0072	Hard	Minimum Path Sum Date: 2015-12-02	C++	99.939	5	13241
			Python 2	93.491	136	3996781
			Python 3	87.646	298	4555150
0085	Hard	Find Min Date: 2016-01-04	C++	99.950	4	11761
			Python 2	88.967	141	4330783
			Python 3	87.566	303	4578550
0086	Hard	Poker Hands Date: 2016-01-03	C++	99.929	5	18961
			Python 2	89.018	131	4330960
			Python 3	89.170	1132	2166784
0171	Hard	DNA Alignment Date: 2016-01-31	C++	99.950	2	16978
			Python 2	81.440	1627	4371450
			Python 3	78.598	2077	4619414
0185	Hard	Glue Shredded Pieces Date: 2016-01-31	C++	98.850	19	442593
			Python 2	77.583	304	8764384
			Python 3	72.351	1744	7938048
0210	Hard	Brainf*ck Date: 2015-12-06	C++	99.897	11	19243
			Python 2	85.319	869	4334554
			Python 3	83.599	1045	4686966
0213	Hard	Lakes Not Cakes Date: 2016-02-16	C++	99.827	2	68314
			Python 2	85.319	45	256
			Python 3	83.599	138	6922478
0224	Hard	Prisoner Or Citizen Date: 2015-12-15	C++	99.942	3	16034
			Python 2	88.605	121	4523975
			Python 3	87.713	275	4576480
0234	Hard	Code Like Huffman Date: 2016-02-08	C++	99.963	2	11250
			Python 2	99.799	40	256
			Python 3	73.089	127	11020975
0002	Medium	Longest Lines Date: 2015-12-29	C++	64.965	3	14809
			Python 2	58.547	108	3935245
			Python 3	58.625	1133	1736704
0009	Medium	Stack Implementation Date: 2016-01-10	C++	64.927	7	11105
			Python 2	58.306	113	4082534
			Python 3	56.908	269	4656369
0010	Medium	Mth Element Date: 2016-01-10	C++	64.980	1	11065
			Python 2	64.918	25	256
			Python 3	54.947	113	6250161
0013	Medium	Remove Characters Date: 2015-12-15	C++	64.970	3	11866
			Python 2	58.528	109	3946200
			Python 3	57.173	268	4487021
0015	Medium	Endianness Date: 2016-02-15	C++	64.996	1	256
			Python 2	64.938	19	256
			Python 3	54.941	97	6287561
0032	Medium	Trailing String Date: 2015-12-15	C++	64.969	3	12671
			Python 2	58.552	109	3931824
			Python 3	57.187	267	4481560
0043	Medium	Jolly Jumpers Date: 2015-11-27	C++	64.969	5	8760
			Python 2	58.399	945	2277376
			Python 3	52.279	1771	4493312
0045	Medium	Reverse and Add Date: 2015-11-27	C++	64.975	3	8789
			Python 2	58.496	111	3962802
			Python 3	58.525	1051	2166784
0046	Medium	Prime Numbers Date: 2016-01-10	C++	64.919	20	8760
			Python 2	55.918	287	5258477
			Python 3	54.503	487	5750411
0071	Medium	Reverse Groups Date: 2016-01-08	C++	64.980	1	11105
			Python 2	64.954	14	256
			Python 3	54.965	101	6263671
0073	Medium	Decode Numbers Date: 2016-01-05	C++	64.975	3	8789
			Python 2	58.487	111	3968903
			Python 3	57.180	268	3968903
0084	Medium	Balanced Smileys Date: 2016-01-30	C++	64.983	1	9071
			Python 2	64.961	12	256
			Python 3	54.904	103	6298562
0089	Medium	Pass Triangle Date: 2015-12-18	C++	64.944	11	12305
			Python 2	57.495	173	4479031
			Python 3	56.150	346	4983777
0158	Medium	Interrupted Bubble Sort Date: 2016-12-18	C++	64.969	4	11209
			Python 2	58.426	115	3999382
			Python 3	57.064	275	4543691
0197	Medium	Column Names Date: 2015-12-30	C++	64.974	3	9026
			Python 2	58.512	111	3953645
			Python 3	58.437	1107	1912832
0200	Medium	Sort Matrix Columns Date: 2016-01-01	C++	64.937	13	12025
			Python 2	58.060	148	4166702
			Python 3	57.546	1262	2162688
0223	Medium	Alternative Reality Date: 2015-12-16	C++	64.974	3	8848
			Python 2	58.479	121	3952758
			Python 3	57.140	280	4483777
0228	Medium	To PI or not to PI Date: 2015-12-26	C++	64.887	32	4096
			Python 2	59.388	275	3043328
			Python 3	58.041	1108	2166784
0232	Medium	Meet Comb Sort Date: 2016-01-29	C++	64.980	1	11105
			Python 2	64.957	13	256
			Python 3	54.886	96	6324724
0001	Easy	Fizz Buzz Date: 2016-01-09	C++	34.985	4	8760
			Python 2	31.453	119	3999837
			Python 3	30.740	277	4522640
0003	Easy	Prime Palindrome Date: 2016-01-10	C++	34.991	3	4096
			Python 2	31.217	114	4293794
			Python 3	30.729	271	4550026
0004	Easy	Sum of Primes Date: 2016-01-04	C++	34.988	4	4096
			Python 2	31.134	328	3944489
			Python 3	30.335	535	4467173
0008	Easy	Reverse Words Date: 2016-02-09	C++	34.989	1	10534
			Python 2	34.937	36	256
			Python 3	29.594	89	6291892
0018	Easy	Multiples of a Number Date: 2016-02-09	C++	34.989	1	10705
			Python 2	34.937	19	256
			Python 3	29.594	97	6257528
0019	Easy	Bit Positions Date: 2016-02-09	C++	34.989	1	10705
			Python 2	34.965	20	256
			Python 3	29.584	100	6280519
0020	Easy	Lowercase Date: 2016-02-09	C++	34.990	1	10434
			Python 2	34.949	29	256
			Python 3	29.616	97	6248251
0021	Easy	Sum of Digits Date: 2016-02-09	C++	34.990	1	10434
			Python 2	34.984	9	256
			Python 3	29.622	94	6247394
0024	Easy	Sum of Integers from File Date: 2016-01-10	C++	34.991	1	8760
			Python 2	31.510	109	3952575
			Python 3	30.805	266	4468506
0087	Easy	Query Board Date: 2016-02-08	C++	34.991	1	8760
			Python 2	34.932	39	256
			Python 3	29.086	122	6830885
0156	Easy	Roller Coaster Date: 2016-01-31	C++	34.990	1	10434
			Python 2	34.967	19	256
			Python 3	29.567	99	6303641
0199	Easy	String Mask Date: 2015-12-22	C++	34.982	3	13846
			Python 2	31.485	111	3978136
			Python 3	31.469	1105	1912832
0208	Easy	Find the Highest Score Date: 2016-01-04	C++	34.977	7	12025
			Python 2	31.365	131	4080577
			Python 3	30.568	294	4694034
0220	Easy	Trick or Treat Date: 2016-01-10	C++	34.986	3	8760
			Python 2	31.486	111	3976367
			Python 3	30.781	269	4490559
0222	Easy	Black Card Date: 2016-02-05	C++	34.970	1	33786
			Python 2	34.949	29	256
			Python 3	29.601	91	6278964
0227	Easy	`Real Fake`_ Date: 2016-02-05	C++	34.990	1	10434
			Python 2	34.933	38	256
			Python 3	29.601	86	6286332
0230	Easy	Football Date: 2016-02-09	C++	34.987	2	11505
			Python 2	34.947	30	256
			Python 3	29.131	98	6827755
0232	Easy	Not So Clever Date: 2016-01-29	C++	34.991	1	8960
			Python 2	34.958	24	256
			Python 3	29.524	95	6363653
0235	Easy	Simple or Trump Date: 2016-02-15	C++	34.990	1	9392
			Python 2	34.958	31	256
			Python 3	29.524	95	6295079