Programming Contest

What does the following batch program do? Try to take a guess before running it yourself:

@echo off
setlocal enabledelayedexpansion

set NUMROWS=10
set NUMCOLS=10

REM // These start at 10 so they're always 2 digits
set nFirstRow=10
set /a nLastRow=nFirstRow+NUMROWS-1
set nFirstCol=10
set /a nLastCol=nFirstCol+NUMCOLS-1

REM // This is a capital oh, not zero
set ON=O
set OFF=.
set Var1=0
set Var3=1

:Initialize
REM // CELLrrcc
for /L %%I in (%nFirstRow%,1,%nLastRow%) do (
 for /L %%J in (%nFirstCol%,1,%nLastCol%) do (
   set CELL%%I%%J=%OFF%
 )
)

if %1[==[ goto :Pattern5
goto :Pattern%1
:Pattern1
REM // What is it?
set CELL1110=%ON%
set CELL1111=%ON%
set CELL1112=%ON%
goto :Render
:Pattern2
REM // What is it?
set CELL1011=%ON%
set CELL1112=%ON%
set CELL1210=%ON%
set CELL1211=%ON%
set CELL1212=%ON%
goto :Render
:Pattern3
REM // What is it?
set CELL1314=%ON%
set CELL1315=%ON%
set CELL1413=%ON%
set CELL1414=%ON%
set CELL1514=%ON%
goto :Render
:Pattern4
REM // What is it?
set CELL1314=%ON%
set CELL1413=%ON%
set CELL1414=%ON%
set CELL1415=%ON%
set CELL1514=%ON%
goto :Render
:Pattern5
for /L %%I in (%nFirstRow%,1,%nLastRow%) do (
 for /L %%J in (%nFirstCol%,1,%nLastCol%) do (
   if !RANDOM! GTR 16383 set CELL%%I%%J=%ON%
 )
)

:Render
cls
set Var2=0
for /L %%I in (%nFirstRow%,1,%nLastRow%) do (
 set ROW=
 for /L %%J in (%nFirstCol%,1,%nLastCol%) do (
   set ROW=!ROW!!CELL%%I%%J!
   if !CELL%%I%%J!==%ON% set /a Var2=Var2+1
 )
 echo !ROW!
)
echo P:%Var2% / G:%Var1%
if %Var2%==0 goto :EOF
if %Var3%==0 goto :EOF

:Advance
set Var2=0
set nRow=%nFirstRow%
set Var3=0
:AdvanceRow
set nCol=%nFirstCol%
if %nRow%==%nFirstRow% (
 set nPrevRow=%nLastRow%
 set /a nNextRow=%nRow% + 1
) else if %nRow%==%nLastRow% (
 set /a nPrevRow=%nRow% - 1
 set nNextRow=%nFirstRow%
) else (
 set /a nPrevRow=%nRow% - 1
 set /a nNextRow=%nRow% + 1
)
:AdvanceCol
if %nCol%==%nFirstCol% (
 set nPrevCol=%nLastCol%
 set /a nNextCol=%nCol% + 1
) else if %nCol%==%nLastCol% (
 set /a nPrevCol=%nCol% - 1
 set nNextCol=%nFirstCol%
) else (
 set /a nPrevCol=%nCol% - 1
 set /a nNextCol=%nCol% + 1
)
set nSum=0
if !CELL%nPrevRow%%nPrevCol%!==%ON% set /a nSum=nSum+1
if !CELL%nPrevRow%%nCol%!==%ON% set /a nSum=nSum+1
if !CELL%nPrevRow%%nNextCol%!==%ON% set /a nSum=nSum+1
if !CELL%nRow%%nPrevCol%!==%ON% set /a nSum=nSum+1
if !CELL%nRow%%nNextCol%!==%ON% set /a nSum=nSum+1
if !CELL%nNextRow%%nPrevCol%!==%ON% set /a nSum=nSum+1
if !CELL%nNextRow%%nCol%!==%ON% set /a nSum=nSum+1
if !CELL%nNextRow%%nNextCol%!==%ON% set /a nSum=nSum+1
set NEWCELL%nRow%%nCol%=!CELL%nRow%%nCol%!
if %nSum% GTR 3 (
 set NEWCELL%nRow%%nCol%=%OFF%
) else if %nSum%==3 (
 set NEWCELL%nRow%%nCol%=%ON%
) else if %nSum% LSS 2 (
 set NEWCELL%nRow%%nCol%=%OFF%
)
if not !NEWCELL%nRow%%nCol%!==!CELL%nRow%%nCol%! set /a Var3=Var3+1

set /a nCol=%nCol% + 1
if not %nCol% GTR %nLastCol% goto :AdvanceCol
set /a nRow=%nRow% + 1
if not %nRow% GTR %nLastRow% goto :AdvanceRow

for /L %%I in (%nFirstRow%,1,%nlastRow%) do (
 for /L %%J in (%nFirstCol%,1,%nLastCol%) do (
   set CELL%%I%%J=!NEWCELL%%I%%J!
 )
)
set /a Var1=Var1 + 1
goto :Render

Twenty imaginary gold doubloons to the pirate that first guesses correctly. I think I might have created the worst-performing implementation of this particular algorithm.

Programming contest!

The prize is a bag-o-marshmallows to whomever can come up with the most efficient way to solve the "Write, efficient code for extracting unique elements from a sorted list" problem.

Apparently everyone else on the web is content to post the question as a possible interview question. Well, I'm not interviewing for anything. I actually need better way to do this. Sure, I have some ideas, but I can't help thinking there is an optimal way to do this (my head keeps going back to the 2 bowling balls being dropped from the building... I can't help thinking there is a logical connection...).

Some quick background so you understand that the half-arsed check-every-item-in-the-array solution is not what I'm looking for. I'm looking for something that minimizes the number of reads I have to do since this algorithm will actually be applied to reading off a file, not an in memory array. I can guarantee you that the list is in order and that I can traverse the list like an array. So we can treat this particular problem like searching an array.

Consider also that I have to read 339,712 records. So think of an array that long with at least 100 duplicates per unique value. The actual number of duplicates per value is of course unknown. I want to avoid reading as many of those duplicates as I can. The one thing in my favor is that I know that they are all in order. Another thing that is clear to me is that I know the high and low values, so I should be able to deduce the maximum number of unique values. Of course you yourself probably saw that too.

Treat this contest like a C++ or VB contest of course. Answers like “SELECT DISTINCT column_name FROM table_name” will be laughed at and will owe me a bag of marshmallows.

Just to give you a head start (since I actually want the darned answer ASAP), I think that since I know the maximum number of unique elements, there must be an optimal number of jumps I can make through the array. I should compare at those jump points and decide whether or not to investigate the areas in-between my jumps based on the comparison result. Just the same as there was an optimal number of floors to skip in the bowling ball problem, I think there is an optimal number of records to skip here. How do I get that value? Following that, what is the most efficient way to search in-between my jumps? Or am I way off?

Please enlighten me and receive a bag of marshmallows in exchange.