5
\$\begingroup\$

In prepping to teach a workshop on recursion I wrote this code that uses a maze-building algorithm. In doing so I found it really natural to use generators a lot. I feel pretty happy with how the code turned out but its also pretty unusual and I wonder what yall think of it.

This is meant to run on latest chrome (partial es2015 support, no destructing assignment, no modules yet)

<style>
* {
	box-sizing: border-box;
}
body { 
	background-color: red;
	min-height: 100vh;
	padding: 0;
	margin: 0;
	display: flex;
}
main {
	flex: 1;
	display: flex;
	flex-direction: column;
}
.row {
	display: flex;
	flex: 1;
}
.row:first-child .cell {
	border-top: 2px solid red;
}
.row .cell:first-child {
	border-left: 2px solid red;
}

.cell {
	display: flex;
	background-color: yellow;
	width: 2%;
	border-bottom: 2px solid red;
	border-right: 2px solid red;
	transition: background-color 1.5s;
}
.cell.clear-right {
	border-right: 0;
}
.cell.clear-down {
	border-bottom: 0;
}
.cell.visited {
	background-color: grey;
}
fieldset {
	position: fixed;
	bottom: 0;
	right: 0;
	background-color: beige;
	max-height: 5px;
	transition: max-height .25s;
	overflow: hidden;
}
fieldset:hover {
	max-height: 3em;
}
</style>
<main></main>
<fieldset>
	<label>Speed:
		<input type="range" name="speed" min=1 max=500 value=10 >
	</label>
	<button name="finish" title="Might take a few seconds">Finish</button>
</fieldset>

<script>
(function(){
'use strict'
var speed = document.querySelector('[name=speed]')
var runLater = fn => setTimeout(fn, speed.value)
document.querySelector('[name=finish]').addEventListener('click', () => runLater = fn => fn())

const board = createBoard(50, 50)
const cell = pos(randomInteger(board.width), randomInteger(board.height))
run(createMaze(board, null, cell))

function run(iterator, prev) {
	if( (prev||{}).done ) return
	runLater( () => run(iterator, iterator.next()))
}

function* createMaze(board, fromCell, toCell) {
	// console.log(`moving from ${fromCell} -> ${toCell}`)
	board.move(fromCell, toCell)
	yield
	yield* createMazeOnUnvisitedNeighbors(board, toCell)
}

function* createMazeOnUnvisitedNeighbors(board, cell) {
	const surroundingCells = board.surroundingCells(cell)
	const surroundingUnvisited = surroundingCells.filter(c => !board.isVisited(c) )
	const nextToVisit = selectRandom(surroundingUnvisited)
	if(!nextToVisit)
		return
	yield* createMaze(board, cell, nextToVisit)
	yield* createMazeOnUnvisitedNeighbors(board, cell)
}

function createBoard(width, height) {
	document.querySelector('main').innerHTML = Array.from(getTableHtml(width, height)).join('');
	const cells = Array.from(cells2D( Array.from(document.querySelectorAll('main .row')) ))
	const visited = new Map()
	const cellAt = (pos) => cells[pos.y][pos.x]

	const move = (from, to) => {
		visited.set(JSON.stringify(to), true)
		cellAt(to).classList.add('visited')
		if(!from)
			return
		if(from.x < to.x)		//→
			cellAt(from).classList.add('clear-right')
		else if(from.x > to.x)	//←
			cellAt(to).classList.add('clear-right')
		else if(from.y < to.y)	//↓
			cellAt(from).classList.add('clear-down')
		else if(from.y > to.y)	//↑
			cellAt(to).classList.add('clear-down')
	}
	return {
		surroundingCells: (position) => [...getSurroundingCells({width, height}, position)],
		isVisited: (position) => !!visited.get(JSON.stringify(position)),
		move,
		height, width,
	}
}

function pos(x, y) { return {x,y, toString: () => `[${x}, ${y}]`} }
function* getSurroundingCells(dimensions, position) {
	const x = position.x
	const y = position.y
	if(x > 0)                   yield pos(x-1, y)
	if(x < dimensions.width-1)  yield pos(x+1, y)
	if(y > 0)                   yield pos(x, y-1)
	if(y < dimensions.height-1) yield pos(x, y+1)
}

function selectRandom(items) {
	return !items.length ? null : items[randomInteger(items.length)]
}

function* cells2D(rows) {
	if(rows.length <= 0) 
		return
	yield Array.from( rows[0].querySelectorAll('.cell') )
	yield* cells2D( rows.slice(1) )
}

function* getCellsHtml(width) {
	if(width <= 0)
		return
	yield '<div class="cell">'
	yield '</div>'
	yield* getCellsHtml(width-1)
}
function* getRowsHtml(height, width) {
	if(height <= 0)
		return
	yield '<div class="row">'
	yield* getCellsHtml(width)
	yield '</div>'
	yield* getRowsHtml(height-1, width)
}
function* getTableHtml(height, width) {
	yield* getRowsHtml(height, width)
}
function randomInteger(maxExclusive) {
	return Math.floor(Math.random() * maxExclusive)
}
})()
</script>

I'm curious especially about the following

  • I wanted to demonstrate that loops are just specialized recursion so I wrote this on purpose with no loops whatsoever. Would loops in places here be clearer (assuming the reader is equally versed in either)?
  • Generators seem to be is a really neat way of generating a state machine where the invoker can control when the next step is invoked, but not the order or implementation of either. This is super cool, but also seems like not as flexible as it can be. Is this just always going to be better with some sort of library?
  • A css one! I don't like that I have to set width: 2%. where width should be a calculated value 100% / widthOfGrid. I would rather do flex: 1 but when I do, often lines don't line up. I can't quite figure out why.
  • I don't like having to json-ize the keys into my Map as it defeats a lot of the point, but I see no good way around that since {x:1,y:2} !== {x:1,y:2}. Could I do something else?
  • This seems to be preforming quite well but I'm pretty bad at interpreting profiler tooling
  • ...except for where it says that yield is not optimized. Is this a temporary bug or a limitation of yield?
  • Are we all agreed that function-declaration hoisting in javascript is a good thing?
  • Assuming I abstract away the generators stuff, how good is the maze-building concept for teaching (intermediate-advanced) recursion?
  • How good is this for teaching (advanced) generators?
  • Other thoughts?
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Indentation

You're missing a level of indentation in your IIFE - it should be:

(function() {
    'use strict'

I've used spaces rather than a tab as I prefer that. I'm not going to recommend one over the other as I don't want to start a holy war.

Spacing

You're inconsistent with spacing around your brackets, sometimes they get a space and sometimes they don't:

board.surroundingCells(cell)

vs

surroundingCells.filter(c => !board.isVisited(c) )

I'd generally never put a space after an opening bracket or before a closing one.

That's the stylistic stuff out the way, I haven't mentioned semicolons because I don't want to start the other JavaScript holy war.

Hoisting

No, hoisting isn't good. It confuses beginners and I don't like having to scroll below the line I'm reading to find the function. Declare your functions first.

var a = true;
function a() {
   return "hello";   
}
console.log(typeof a);

Ask some beginners what the code above logs. I bet at least some of them will get it wrong. Obviously naming a variable the same as a function in the same scope is a pretty big mistake but I have seen it happen.

Confusing code

Look at this bit of code:

var speed = document.querySelector('[name=speed]')
var runLater = fn => setTimeout(fn, speed.value)
document.querySelector('[name=finish]').addEventListener('click', () => runLater = fn => fn())

function run(iterator, prev) {
    if( (prev||{}).done ) return
    runLater( () => run(iterator, iterator.next()))
}

First, speed is a poor name as it is actually a delay in milliseconds. prev is also a poor name, I assume you meant previous but even then, I think current is a better name. It's certainly not the previous step.

I'd move all of the run stuff into a separate object with functions like start, changeDelay and finish.

Recursion

Tail recursion is a special case that is optimised in many languages/compilers to a loop. A loop is far simpler as you don't need to save a new frame on the stack.

function* getRowsHtml(height, width) {
    if(height <= 0)
        return
    yield '<div class="row">'
    yield* getCellsHtml(width)
    yield '</div>'
    yield* getRowsHtml(height-1, width)
}

If you refactor that to use a loop you can also only compute the cells' html once instead of having to recompute it for each row (width doesn't change between rows).

I also think all the generator/iterator stuff is pointless for the html as it is all called from getTableHtml which is only called by Array.from.

File outline

I see what you're saying about being able to read the file as an outline, I generally do this sort of thing:

(function (w, $) {
    'use strict';

    var field1,
        field2,
        function1,
        main;

     function1 = function(arg) {
         // Do something important.
     };

     main = function() {
        // entry point.
     };


     main();
}(window, jQuery));
\$\endgroup\$
5
  • \$\begingroup\$ "I'm not going to recommend one over the other as I don't want to start a holy war." Heresy! But also a good answer, which could be improved by mentioning that semicolons can prevent unexpected errors, so it's worth keeping them in mind at the very least. \$\endgroup\$
    – anon
    Nov 17, 2015 at 12:05
  • \$\begingroup\$ Thanks for the code review. Good stuff, I want to make the counter-point for hoisting as I feel like the reasons for it are rarely expressed. The idea is that you want your code file to read like an outline with broad strokes as to what this code does up top and details available for drilling into below. Short of classes (which are a nightmare for other reasons) there isn't any other way to do this in js. Notice that this is specifically about function declaration hoisting where the function is never re-assigned. There is far fewer proper uses cases for variable hoisting. \$\endgroup\$ Nov 17, 2015 at 15:04
  • \$\begingroup\$ I'll also say that the statement about beginners being confused by function declaration hoisting is anecdotal. I teach many beginning and intermediate javascript developers and my experience is the opposite, any confusion is cleared up in 30 seconds, and it barely registers on the things-they-have-issues-with scale. I've had several students who really embrace the view-it-as-an-outline approach, although admittedly, most do not and just nod and move on with their day. \$\endgroup\$ Nov 17, 2015 at 15:09
  • \$\begingroup\$ @GeorgeMauer - yes definitely anecdotal - if your experience is different then no problem at all. I almost never use function declarations in my own code - I always use function expressions so hoisting declarations is rarely something that I worry about in my own code. \$\endgroup\$
    – RobH
    Nov 17, 2015 at 16:15
  • 1
    \$\begingroup\$ @GeorgeMauer - I added an update to show you how I achieve the easy to skim outline of a file... The main difference is that the entry point is usually right at the bottom of the file. \$\endgroup\$
    – RobH
    Nov 17, 2015 at 16:26

Your Answer

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

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