User:Tom McGuire/TeachingJvsJava
Teaching J/Computer Science: AP Computer Science
Slashdot reported on the AP Computer Science 2024 free response question 4:
High School AP CS A Exam Takers Struggled Again With Java Array Question
The problem stem has been posted by the College Board here:
https://apcentral.collegeboard.org/media/pdf/ap24-frq-comp-sci-a.pdf
The following was posted as a proposed solution done by an AP Computer Science Tutoring service, the link was provided in the Slashdot article:
apcomputersciencetutoring.com gridpath soulution
The author is Brandon Horn from the appearance of the website one of the instructors at apcomputersciencetutoring.com. He has a Bio at the page. The code from that site is reproduced here for educational purposes.
Mr. Horn's solution
To handle grid position, a class given in the set up of the question for which you had to write getNextLoc function
public Location getNextLoc(int row, int col)
{
Location belowLoc = new Location(row + 1, col);
Location rightLoc = new Location(row, col + 1);
if(row == grid.length - 1)
return rightLoc;
if(col == grid[0].length - 1)
return belowLoc;
if(grid[row + 1][col] < grid[row][col + 1])
return belowLoc;
else
return rightLoc;
}
The sumPath routine
public int sumPath(int row, int col)
{
int sum = grid[row][col];
Location loc = getNextLoc(row, col);
while(loc != null)
{
sum += grid[loc.getRow()][loc.getCol()];
if(loc.getRow() < grid.length - 1 ||
loc.getCol() < grid[0].length - 1)
loc = getNextLoc(loc.getRow(), loc.getCol());
else
loc = null;
}
return sum;
}
Now 2 replies to this solution posited recursive solutions to this problem. This is the first thing I thought of when I reviewed the problem before seeing any other solutions. One solution was succinct by using object oriented dereferencing in place and not using temporary variables. The one chosen here is used because it's wrong just like the other solution, but it's easier to fix. They're wrong because they fail to meet the preconditions of the problem (I admit on my attempt I too fell prey to the preconditions):
* Preconditions: row is a valid row index and col is a valid column index in grid. * row and col do not specify the element in the last row and last column of grid."
public int sumPathRec(int row, int col) {
if (row == grid.length-1 && col == grid[0].length-1) {
return grid[row][col];
}
else {
Location loc = getNextLoc(row, col);
int nextRow = loc.getRow();
int nextCol = loc.getCol();
return grid[row][col] + sumPath(nextRow, nextCol);
}
}
You should be able to see that this relies on providing the last cell coordinates as the base case. The college board seems to be forcing you away from this fairly elegant solution. I believe the correct recursive solution would be:
public int sumPathRec(int row, int col)
Location loc = getNextLoc(row, col);
int nextRow = loc.getRow();
int nextCol = loc.getCol();
if (nextRow == grid.length-1 && nextCol == grid[0].length-1) {
return grid[row][col] + grid[nextRow][nextCol];
}
else {
return grid[row][col] + sumPath(nextRow, nextCol);
}
}
I thought this would be a good example to implement in J as a way of teaching J and to further a more general discussion of teaching computer science.
NB. AP CS 2024 free response question 4
NB. redone in J without object oriented programming
NB. in the AP problem the grid is presumed to be given to you with parameters for size initialized in the object that defines it.
NB. in J it's a nice way to show how to use shuffle (dyadic ?) and shape ($) it into the grid we will need
makegrid =: 3 : 0
'm n'=. y
(m,n) $ (m*n) ? m*n
)
NB. so things won't run until I want them to I have an init routine
NB. it takes the grid row and column maximums you want and initializes grid, M = max rows, N = max columns
initproblem =: 3 : 0
'M N' =: y
grid =: makegrid M,N
)
NB. create a possible set of next locations
NB. in the case of this problem it will be the cell underneath
NB. and the cell to the right.
nxtlocs =: 1 0&+ ; 0 1&+
NB. must be a valid index and not go off the grid
NB. I assume there will be no negative numbers
NB. just make sure rows and columns are less than M,N
NB. constrain =: 3 : 'N&>@>./ y'
NB. my first cut at constrain I just used square grids
constrain =: 3 : '(M,N)&> each y'
NB. nxtloc - will return the location of the either the bottom or right neihbor
NB. depending on which location contains the smallest number
nxtloc =: 3 : 0
NB. get proposed set of possible grid locations
locs =. nxtlocs y
NB. keep only those locations that meet the constraints (ie. don't run off grid
locs =. (; *./each constrain locs) # locs
NB. for the grid locations that are left find the one with the smallest
NB. value in grid
((<./ locs { grid) = locs { grid)#locs
)
NB. return the full path through the grid
NB. precondition: y has valid row and column values. y can not be the coordinates of the last cell
path =: 3 : 0
NB. base case the next location coordinates are for the highest row and highest col
loc =. ;nxtloc y. NB. I return boxed coordinates when I didn't need to
if. *./ ((M-1),N-1) = loc do.
y;loc
return.
end.
(<y),path loc
)
sumPath =: {{ +/ x {~ path y }}
NB. sumPath =: {{ +/ (path y){grid }}
NB. run initproblem 12 9 for example to set up grid
NB. then the sum of the path is now easily obtained:
NB. +/ (path 3 4){grid
NB. will return the sum of the path starting at location 3 4
Here's the above code sans comments:
NB. AP CS 2024 free response question 4
NB. redone in J without object oriented programming
NB. no comment version except for this
makegrid =: 3 : 0
'm n'=. y
(m,n) $ (m*n) ? m*n
)
initproblem =: 3 : 0
'M N' =: y
grid =: makegrid M,N
)
nxtlocs =: 1 0&+ ; 0 1&+
constrain =: 3 : '(M,N)&> each y'
nxtloc =: 3 : 0
locs =. nxtlocs y
locs =. (; *./each constrain locs) # locs
((<./ locs { grid) = locs { grid)#locs
)
path =: 3 : 0
loc =. ;nxtloc y
if. *./ ((M-1),N-1) = loc do.
y;loc
return.
end.
(<y),path loc
)
sumPath =: {{ +/ x {~ path y }}
Handwriting a lost art
I hate to show my age but my Freshman year at college was the last year we had to use punch cards to write program. Sophomore year there were enough 3270 terminals to retire those monstrous dinosaurs. Getting on a punch card machine was tough. So when you finally got one you had to make sure the lion's share of your work was done. To do that you had to write your program out on paper by hand. You proofread the code a couple of times to make sure syntax was good and that the program seemed like it would do what it was supposed to. Then you sat at the machine typing in a line of code per card. Heaven help you if you ever dropped the cards on the ground on your way to the card reader.
Fast forward to the 21st century and my kids just jam in code to the IDE and run it. Then yell for me when it doesn't work.
When I ask, "what it is supposed to do?"
They pull up a PDF and say "this".
I ask if they printed the PDF out?
They give me a horrified look like no one prints stuff out. They get another horrified look because they know Dad's going to go into teaching mode.
They get up from the table just as I sit down and I ask "Where are they going?"
"I'm going to get a drink this seems like you are going to take a while"
When we finally get settled in for me to give them some help I find they have no hand written notes. There isn't single diagram they have put together. So I kind of have to start from scratch to show them how to design by hand so to speak. I have had 2 kids at 2 different schools and neither seem to require any handwritten documentation ever be done.
Even the teachers use slideware to teach the course so students don't even get to see someone else design on paper or a white board.
I have to wonder if this neglected form of designing software is partly why some students have trouble with programming. They aren't internalizing what the computer does, so every program is a mystery as to why it works.
This is also a place that J excels I can jot down a few lines of J and use it for a specification in any language I may be programming in. Its terseness takes away much of the drudgery of hand writing out code.
Recursion
Maybe it's me but I believe this is one of the single most important concepts you can teach to a new programmer. It not only exposes them to a powerful technique in programming it exposes them to the process of mathematical induction. Inductive reasoning is a useful tool for any student to have. AP CS Free Response Question 4 represents the antithesis of that process by seeming to deliberately steer students away from an elegant recursive solution, in favor of a brute force looping solution. The precondition for getNextLoc in the problem makes sense as there are no elements beyond the last cell and therefore no way to complete the logic needed without producing a memory leak. In the case of sumPath the precondition is arbitrary. Why can't I call sumPath with M-1,N-1 as the location. It should just return the value of the last cell. It also provides a more elegant solution in Java and a simpler recursive routine in J.
path =: 3 : 0 if. *./ ((M-1),N-1) = y do. <y return. end. (<y),path ;nxtlcoc y )
While this solution doesn't meet the preconditions. I believe it's a better solution. It has a cleaner look to it. There are no temporary variables used. Array languages have always had recursion and the language encourages recursive thinking. J even provides a self-reference operator ($:) so you can place recursion into your tacit programming. Here is the late Roger Hui's tacit quicksort definition as an example:
quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ ?@#)) ^: (1<#)
For those who might say recursion is inefficient and teaching looping code is more performance oriented. I would say that outside of teaching that recursive forms have a looping equivalent. The recursive form is a great specification for a generative AI program. I won't share the Java translation but perplexity.ai did a fine job of turning the Java based recursive program into a while loop. You can cut and paste the Java recursive definition into your favorite chatbot and see. What I will share is the stems for the Java translation and the stem and translation of the J recursive code into looping code. This was done at the perplexity.ai site.
Java code translation request stem:
can you translate the Java code delimited by '===' from its recursive form to loop form: === <paste java code here> ===
Now for the J code translation request:
Here is a similar recursive function written in the J programming language by jsoftware. It is a language in the category of array programming. Can you translate the recursive function (called a verb in J) into its loop based form. The verb (ie. function) is delimited by '==='. === path =: 3 : 0 if. *./ ((M-1),N-1) = y do. <y return. end. (<y),path ;nxtloc y )===
The results are pretty good (see below). The comments were added by perplexity.ai. You can see above I gave it uncommented code. The Java code I gave was for a combined sumPath routine. I only said similar I could have given a more detailed stem telling it I was saving all the coordinates of the path in J boxes. But it seems to have figured it out for itself.
path =: 3 : 0
result =. 0$0 NB. Initialize an empty list to store the path
current =. y NB. Start with the initial position
while. 1 do.
result =. result, <current NB. Append current position to result
if. *./ ((M-1),N-1) = current do.
break. NB. If we've reached the bottom-right corner, exit the loop
end.
current =. nxtloc current NB. Move to the next position
end.
result NB. Return the complete path
)
The Ah Ha! moment
Seeing the recursion in the solution to this problem is an Ah Ha! moment. Your brain sees it and there is intense satisfaction with it. Ruining that moment with arbitrary preconditions is taking the fun out of programming and probably losing a few students forever. The computer as a device is nit-picking enough on its own. Many new students find that alone annoying. If teachers and test creators add their own level of nit-picking how many more students are we chasing away. J takes the complete opposite approach. Most verbs return something. If you are trying to find the index of a particular integer in an array and it's not there J returns the size of the array as a signal it's not there. It doesn't immediately stop you most of the time. It returns some sort of an answer. The answer is usually useful in some way. In the indexing example it is returning the index of the number should you choose concatenate it to the end of the list.