Filip Wieland FLamparski

This is an extension of the previous gist - while that gist explored a particular question, this one tries to compare some algorithms which have very similar implementations, but different requirements and performance characteristics. It generates a random but somewhat believable geography on a plane and then tries to get from Q to W (noting that there may be more than one connection between two cities, with different costs). Each run is different.

An example result:

====================================================================================
Algorithm A*:
Expanded Q; Agenda = [(E, 308), (P, 190), (D, 289), (A, 497)]
Expanded E; Agenda = [(P, 190), (W, 412), (D, 289), (I, 512), (A, 497)]
Expanded P; Agenda = [(W, 412), (D, 289), (L, 338), (M, 385), (I, 512), (G, 420), (A, 497), (V, 528)]

If you run agendaSearch.js you should get the same output as output.txt

I reverse-engineered the optimisations made in the mark scheme solution. They were:

If a cheaper path exists to a node in the agenda already, don't add the more expensive path to the agenda. If you find a cheaper path to a node than you already have in the agenda, remove the more expensive path.
Don't expand nodes which were already expanded, even if you reach them through a different path. In UCS, the path to every node expanded so far should already be optimal.

The algorithm works even without those two optimisations, but the agenda size gets quite big - not an issue for a computer on such a small problem, possibly a problem for a computer on a much larger problem, definitely a problem for someone doing this in an exam.

To turn off the simplifying assumptions:

	#include <ArduinoJson.h>
	#include <WiFi.h>
	#include <SdsDustSensor.h>
	#include <PubSubClient.h>

	// v1.0 - 2019-06-16 - Initial public release of script
	// v1.1 - 2019-06-17 - Turn off sensor if resetting due to lack of connectivity
	// v1.2 - 2019-06-22 - Increase WiFi connection timeout

	// XXX Change these to your WiFi details

	/**
	* Computes the checksum of a SDS011 message.
	*
	* This checksum is the low 8 bits of the sum of the data bytes.
	* The sensor will not react to commands with invalid checksum.
	*/
	byte sds011_checksum(byte* msg, size_t msg_size) {
	int sum = 0;
	for (int i = 2; i < msg_size - 2; i++) {
	sum += msg[i];

	void setup() {
	Serial.begin(115200);

	Serial2.begin(9600, SERIAL_8N1, -1, -1, false);
	}

	void loop() {
	if (Serial2.available()) {
	byte pm_buf[10];
	Serial2.readBytes(pm_buf, 10);

	import serial
	import struct
	from datetime import datetime

	# Change this to the right port - /dev/tty* on Linux and Mac and COM* on Windows
	PORT = 'COM5'

	UNPACK_PAT = '<ccHHHcc'

	with serial.Serial(PORT, 9600, bytesize=8, parity='N', stopbits=1) as ser:

	import serial
	import struct
	from collections import deque
	import numpy as np
	import matplotlib.pyplot as plt
	import matplotlib.animation as anim
	from matplotlib.ticker import FuncFormatter

	# Change this to the right port - /dev/tty* on Linux and Mac and COM* on Windows
	PORT = 'COM5'

	<!DOCTYPE html>
	<html>
	<head>
	<meta charset="utf-8"/>
	<title>foreach or for(i)</title>
	<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/1.0.0/benchmark.min.js"></script>
	<script src="./suite.js"></script>
	</head>
	<body>
	<h1>Open the console to view the results</h1>