17
$\begingroup$

Puzzling Stack Exchange:

Don’t even ask where I found the old printout, below, of an uncommented computer program. As I am a leading-edge software solutionaut hone-tuned for elegantly annotated exoticode, reconnoitering this printout is beneath my paygrade. All I’ve bothered to notice is that some drone meant this program to spin out something called "puzzle.txt". I need for you to spec the deets for me.

  Assuming that puzzle.txt is a puzzle, what kind? How is this program supposed to produce it?

  Know that I am particularly impatient to be debriefed on the identities of the 7 characters besmirched on line 200.
200 w$(1,0) = ??????? [7 smudged characters]

  It would be really great if you could also dummy up a possible printout of puzzle.txt by noon, okay?.


 10  rows = 8 : columns = 8
 20  dim n(rows,columns), f$(rows,columns), w$(rows,columns)
 30  for r = 0 to rows : for c = 0 to columns
 40      n(r,c) = 0
 50      f$(r,c) = "_"
 60      if r=0 then w$(r,c) = "_" else w$(r,c) = "|"
 70  next c : next r
 80  w$(0,columns) = " " : w$(rows,columns) = "_"
 90  d = INT(4*RND) : r = 1+INT(rows*RND) : c = 1+INT(columns*RND)
100  n(r,c) = 1
110  unvisited = rows*columns - 1
120  while unvisited > 0
130      d = INT( d + 3.6 + 2.4*RND ) mod 4
140      if d=3 and c < columns then:  c = c+1 : if n(r,c)=0 then w$(r,c-1) = "_"
150      if d=1 and c > 1       then:  c = c-1 : if n(r,c)=0 then w$(r,c)   = "_"
160      if d=0 and r > 1       then:  r = r-1 : if n(r,c)=0 then f$(r,c)   = " "
170      if d=2 and r < rows    then:  r = r+1 : if n(r,c)=0 then f$(r-1,c) = " "
180      if n(r,c)=0 then:  n(r,c) = 1 : unvisited = unvisited-1
190  wend
200  w$(1,0) = ???????  [7 smudged characters]
210  for r = 1 to rows-1 : for c = 1 to columns-1
220      if f$(r,c)=" " or f$(r,c+1)=" " then:  if w$(r,c)="_" then w$(r,c) = " "
230  next c : next r
240  open "o", #1, "puzzle.txt"
250  for r = 0 to rows : for c = 0 to columns
260          if c > 0 then print #1, f$(r,c);
270          print #1, w$(r,c);
280      next c : print #1,""
290  next r : close #1 : end

(Yeah yeah, no this is not an actual corporate-speak demand for information, but the challenge is to answer as if it were. The tag means that the old program should not be run in order to figure it out or to make the sample puzzle.txt.)

$\endgroup$
3
  • 4
    $\begingroup$ This is a neat puzzle! I've figured out what the code overall is doing - now trying to figure out what those characters are... $\endgroup$
    – Deusovi
    Jul 17, 2020 at 20:00
  • 1
    $\begingroup$ To find a computer that still can run this code would be a challenge in itself. $\endgroup$
    – Florian F
    Jul 18, 2020 at 10:20
  • 1
    $\begingroup$ So true, @Florian F, the pre-puzzle was to figure out a way to run this. Enter qb64.org, whose QuickBASIC works with minimal modification to the code originally written for GW-BASIC. $\endgroup$
    – humn
    Jul 18, 2020 at 19:43

2 Answers 2

12
$\begingroup$

Let's trace through the code!

Lines 10-70 seem to just be setting up variables. It looks like three 2D arrays are being created: n, f$, and w$. From the next few lines, n appears to be an integer array, and the other two seem to be arrays of strings.

The arrays are either 8×8 or 9×9 (depending on whether the language uses half-open or closed intervals). Line 80 appears to index into the array at (0,8), so we'll need to use 9×9 grids.

So, after setup, we're here:

Lines 10-80 have defined three arrays and initialized them:

enter image description here
Now we get into the less certain part of the code - the part that uses random numbers. Random numbers are often floating-point numbers from 0 to 1 by default: to generate a number from 4 possible options, you simply multiply your result by 4 and round down. This appears to be roughly what's happening here.

Line 90 generates 3 new numbers: d, r, and c. d is a number from 0 to 3, and r and c are both from 1 to 8.

So, what does this loop do? It has a count called "unvisited" - that's a helpful name. That count starts at the total size of the array -1, and then decreases in the loop. It only decreases whenever you find a place where n(r,c)=0; when you do this, n(r,c) is set to 1, and then unvisited is decremented.

So it looks like it's searching all the cells of the board. (Well, not quite - we're ignoring row and column 0 here. The conditions in lines 140 to 170 seem to explicitly avoid those.)

Speaking of 140-170, what's going on with d there? Depending on d, either r or c is increased or decreased by 1... so d must be a direction! The coordinates (r,c) are going to wander around the grid, guided by d. Each time they visit a cell they haven't seen before, they will mark it with a 1 in n, do something with w$ and f$, and then decrease the number of unvisited cells. Once the whole grid is explored, the program leaves the loop.

And this also explains the weird update for d: it is specifically set up so that you can get any value for d except the opposite direction. There's a 0.4/2.4 chance that you turn left, a 1/2.4 chance that you go straight, and a 1/2.4 chance that you go right.

So, what is that "something"?

By now it's getting clearer what the point of this program is. Each time it finds a new cell, it changes either f$ or w$, by either replacing the cell in w$ with a _, or replacing the cell in f$ with a space.

Then something happens with w$(1,0). We're not sure what that is yet. But let's look ahead to the end. It appears that in each row, f$ and w$ are being printed alternately. So, if we skip the loop, let's look at the output:

enter image description here
And now it's clear what the program does! It wanders through all of these cells, deleting some of the characters in this final output -- this is a maze generator. f$ and w$ are the arrays of floor and wall tiles. Row and column 0 are mostly ignored because they represent the top and left boundaries of the maze, so they shouldn't change.

Armed with this knowledge, we can finally check out lines 200-230:

It appears that lines 210-230 are going through the grid and fixing some of the ASCII art: if either floor adjacent to a _ is missing, then we don't need to use the _.

And this will finally give us the missing line! Note that we still need an entrance to the maze. That's what w$(0,1) will be. But the question is: do we use _ or as our character there? It depends on the floors nearby: just like the rest of the maze, if there is floor on all sides, the "unused wall" character is _; if there is not, then the "unused wall" character is . Here, there is only one side, so it turns into:
"If f$(1,1) is _, then use _. If f$(1,1) is , then use ."

In other words, the missing line is:
200 w$(1,0) =f$(1,1).

A sample output:

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Thank you for another complete and fun to follow solution, Deusovi! Along the way you answered every candidate question that i had considered asking before realizing how they might be compelled by line 200 (which had been casually under-implemented as a plain " " space for decades). $\endgroup$
    – humn
    Jul 18, 2020 at 8:02
  • $\begingroup$ (cont'd) Did you deliberately include some handmade improvements in your sample puzzle.txt where ___ underlines happen to form loose ends? Perhaps the gappy font insisted on touch-ups, spreadsheet maestro. Those improvements really got me going so i implemented them in the home version of line 220 as ` 220 if ( f(r,c)=" " or f(r,c+1)=" " ) and w(r,c)="_" and w(r+1,c)="|" then w(r,c) = " " ` and am downright thrilled with the result (different font). $\endgroup$
    – humn
    Jul 18, 2020 at 8:05
  • 1
    $\begingroup$ You could try ... then w$(r,c) = "." $\endgroup$
    – Florian F
    Jul 18, 2020 at 10:38
  • 1
    $\begingroup$ @humn Unfortunately, that was an accident -- the spreadsheet formula I used must have been not quite right. But it looks like it led to some interesting aesthetic improvements regardless! $\endgroup$
    – Deusovi
    Jul 18, 2020 at 13:58
  • $\begingroup$ There it is Deusovi and @Florian F, a Community Wiki gallery with your improvements. Please feel free to revise it in any way. $\endgroup$
    – humn
    Jul 20, 2020 at 3:00
3
$\begingroup$

From the QA Department (solver-led improvements) – Community Wiki, feel free to edit


Test Ø.   A puzzle.txt that could be produced by the posted program were it set to use more rows and columns. It’s ASCII,,, but is it art? Good enough, at least, to solve by hand and test its simplistic puzzle-producing algorithm.



Test D.   puzzle.txt after a revision motivated by Deusovi’s solution. Poof – gone are the excessive horizontal gaps of Test Ø.



Test DF.   puzzle.txt after also following Florian F’s suggestion in a comment. No more rounded corners or excessive vertical gaps. Is it ASCII puzzle art yet?



Appendix DFc.   Code that produced Test DF with its combined improvements while running in QB64 v1.4, a handy version of QuickBASIC made by QB64.org.

  10  rows = 19 : columns = 35
  20  dim n(rows,columns), f$(rows,columns), w$(rows,columns)
  30  for r = 0 to rows : for c = 0 to columns
  40      n(r,c) = 0
  50      f$(r,c) = "_"
  60      if r=0 then w$(r,c) = "_" else w$(r,c) = "|"
  70  next c : next r
  80  w$(0,columns) = "," : w$(rows,columns) = "_"
  90  d = INT(4*RND) : r = 1+INT(rows*RND) : c = 1+INT(columns*RND)
 100  n(r,c) = 1
 110  unvisited = rows*columns - 1
 120  while unvisited > 0
 130      d = INT( d + 3.6 + 2.4*RND ) mod 4
 140      if d=3 and c < columns then:  c = c+1 : if n(r,c)=0 then w$(r,c-1) = "_"
 150      if d=1 and c > 1       then:  c = c-1 : if n(r,c)=0 then w$(r,c)   = "_"
 160      if d=0 and r > 1       then:  r = r-1 : if n(r,c)=0 then f$(r,c)   = " "
 170      if d=2 and r < rows    then:  r = r+1 : if n(r,c)=0 then f$(r-1,c) = " "
 180      if n(r,c)=0 then:  n(r,c) = 1 : unvisited = unvisited-1
 190  wend
 200  w$(1,0) = f$(1,1)
 210  for r = 1 to rows-1 : for c = 1 to columns-1
 220      if ( f$(r,c)=" " or f$(r,c+1)=" " ) and w$(r,c)="_" and w$(r+1,c)="|" then w$(r,c) = ","
 230  next c : next r
 240  open "o", #1, "puzzle.txt" : print #1,""
 250  for r = 0 to rows : for c = 0 to columns
 260          if c > 0 then print #1, f$(r,c);
 270          print #1, w$(r,c);
 280      next c : print #1,""
 290  next r : close #1 : end  

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.