CSES Code Golf

cses.fi is a competitive programming website. One helpful resource on the website is their problem set, which has a bunch of standard competitive programming exercises (this may also be helpful preparing for CS interviews). CSES has an online judge, so users can submit their programs and have them be evaluated, and there are also leaderboards. The “shortest code” leaderboard is interesting for a few reasons:

  1. Competitive programming is about programmer speed, program correctness, and program speed, not code length.
  2. All programming languages compete on the same leaderboard.
  3. Whitespace is not counted towards code length.

I am going to demonstrate why 2. and 3. are not only weird, but also terrible ideas for any code golf competition. In Ruby, any program can be rewritten using only 17 nonwhitespace characters. The following Ruby program will convert any Ruby program into one with only 17 nonwhitespace characters:

$><<"eval ['#{gets(p).unpack1('b*').tr('01'," \t")}'].pack'b*'"

Usage:

ruby golf.rb < prog.rb > golfed-prog.rb

The result will look something like this:

eval [' 			 		      	  	 				       	  			  		 	 	  		   	 			 		  			  			 	    	 			 				 		 					 	 	  	 		  	 	        			      	   			 		  	 	    			 			    	 		 	  	 		   		 		 	 	  		      	   			 		      	   					       	  	   		   	 	         	       	       	       	   			 		      	  	 				       	   			 		      	  	 	  	       	   	  		       	  	 				  	 				       	      		       	  						       	   			 		 				 	   	  		       	   	 			       	  		  		   	 	 	   			 		      	  		 	 	       	  	   		   	 	         	       	       	       	      			      	   			 		  	 	    	 	  		  			 		   	  		  	 	    '].pack'b*'

This program prints the $3n+1$ sequence starting from the integer given as input, solving the “Weird Algorithm” problem on CSES. Here is the program again, but with most of the whitespace erased:

eval ['                     '].pack'b*'

The whitespace is a combinations of spaces and tabs, representing the original Ruby program in binary. pack will convert it back to text (for some reason pack 'b*' interprets spaces as zeroes and tabs as ones). Then, eval runs the program.

I’m not sure if 17 characters is the limit. At one point, I tried to see if the 'b*' could be replaced with a ?m or a ?u. These replacements would represent base64 and uuencoding, respectively, but as far as I’m aware, neither can be used to produce general Ruby programs using only tabs and spaces.