Scratch for Arduino tutorials

Some more Arduino tutorials, these use the excellent Scratch for Arduino (http://s4a.cat/). The following links are to PDFs:

First off we get a single LED to flash on / off:

https://drive.google.com/open?id=0B_YZvz83_le0Uk93Qm51MC11Tlk

A simple reaction test game:

https://drive.google.com/open?id=0B_YZvz83_le0VlV3NFBGZVR4ckE

A temperature sensor:

https://drive.google.com/open?id=0B_YZvz83_le0bjhmdTcxR3Z6aFU

How to wire up buttons part 1:

https://drive.google.com/open?id=0B_YZvz83_le0ZGpzNEs5b2FOZVk

Following on from the above this tutorial uses the buttons to move a sprite:

https://drive.google.com/open?id=0B_YZvz83_le0Y2dkcFZzdGp2Q2c

Using a joystick:

https://drive.google.com/open?id=0B_YZvz83_le0Y2dkcFZzdGp2Q2c

Simple Arduino memory game

Here is a tutorial for a very simple memory game that flashes a sequence of LEDs. You respond via the serial console with a list of  'r' or 'g' characters to indicate the sequence. The tutorial also shows you how to respond via a console application. There are more sophisticated arduino memory games on the web but I tried to keep this one as easy as possible as it was used in our coder dojo session.

PDF:
https://drive.google.com/file/d/0B_YZvz83_le0Vy16WUg1eVNyVjQ/view?usp=sharing

Code:
https://drive.google.com/open?id=0B_YZvz83_le0a0g0bWxPSV9xeTA

Arduino - Sending key presses from attached PC

I wanted to be able to send real time key presses to the Arduino from the PC so could not use the Arduino application as it requires the return key after every send. I initially tried a simple bat file with echos to the COM ports but could not get it to work. In the end I wrote a powershell script:

$port = new-Object System.IO.Ports.SerialPort COM9,9600,None,8,one
$port.open()
do
{
  $key = $Host.UI.RawUI.ReadKey("NoEcho,IncludeKeyDown")
  Write-Host $key.Character
  $port.WriteLine($key.Character) 
}
while(($key.Character -ne 'q'))
$port.Close()

Put the above into a script (scr.ps1) and invoke it as follows:

c:\> powershell -ExecutionPolicy ByPass -File scr.ps1

Ensure you have closed the Arduino app or you will get a permission error talking to the COM port. Also ensure you amend the COM9 (first line of script) to be the appropriate COM port. The script will run until the q key is pressed. I have only tested it on Windows 7 so I don't know whether it will work with powershell 1 (XP / Vista version). The corresponding Arduino code is simply:

void setup() { serial.begin(9600); }

void loop() {
  char inChar = serial.read();
  if (inChar == 'a') {
    // 'a' key was pressed
  }
}

Java Trie - Ascii only

Just uploading an Ascii only version, uses a byte instead of a char. Also uses the top bit as an end of word flag so you can not populate it with Ansi (ie 8 bit characters).

https://drive.google.com/file/d/0B_YZvz83_le0alZ1OFNMVW56cWs/edit?usp=sharing

Also probably worth mentioning that this implementation (and the other full 'char' version) will only return the longest match when there are multiple overlapping terms within the Trie. For example a Trie containing "cap", "capitulate", "capitulated" and a search string of "capitulated" would only return the longest, "capitulated".

I haven't implemented the compressed version as it turns out the above version doesn't use that much memory.

Trie - Java implementation

I have ported the C++ code over to Java so I can use it on an android application I am developing. I need to try and reduce the memory footprint and my requirement is only for lower case ASCII so whilst this version uses a Java 'char' I am re-factoring to use a byte (plus re-use some of the top bits). I was also going to try and convert it to a compressed trie. There are a few Java implementations out there and to be honest the only difference with this one is I have used a sorted ArrayList rather than a map within the nodes. I then do a binary search of the list. This probably reduces performance but it should use less memory.

https://drive.google.com/folderview?id=0B_YZvz83_le0VTdDSjF2OU9CTW8&usp=sharing

C++ implementation of a Trie / Prefix Tree

A Trie (http://en.wikipedia.org/wiki/Trie) is a great way to search a stream of text for multiple keywords. It's extremely fast and is a very simple structure to understand. Here is my initial attempt in C++. It is a first cut, not yet fully tested but seems to work. It is case sensitive and will match partial words. The main disadvantage of a Trie is the memory consumption. Each letter requires a node that contains a character / bool and vector so adding words quickly chews up memory.

Here is a link to the source on github:

https://github.com/eskeels/trie

There is just the header file and a main.cpp with some tests. I have also added 2 additional methods, Compress() and ValidateState(). Compress() will recurse through the Trie calling shrink_to_fit() on each of the vectors that are used to store child nodes. ValidateState() performs validation of the nodes. It is only required for testing purposes.

Generating C++ code from a Trie

If you need to search for a small amount of hard coded strings then this might be a good solution. Whilst the Trie is fast you have to contend with the overhead of initialising the Trie data structure and the memory usage. This version of the Trie has a dump() method that will generate a search() function capable of performing a parallel search of all the words in the Trie. Some simple tests have shown this to be considerably faster than using the Trie directly. The generated search() function is pretty ugly and unwieldy but so long as you don't have too many terms it could prove useful.

The prototype of the search method generated is below:

const char * search(const char * pStart,  const char * pbuff, CallbackFunction cf )

pStart is a pointer to the very start of the buff you are search. pbuff is a pointer to the position where you want to search from. Finally cf is a callback function that is invoked whenever a search term is found. A sample showing use of the search function is below:

while( p && (*p != '\0') )
{
p = search(&peterpan[0], p, &myCallback );
count++;
}

The callback is of the form:

int myCallback(const char * pStart, const char * pbuff, const char * resultString, const char * position)

pStart / pbuff are as per the search() method. resultString is a NULL terminated string containing the search term that has been found. position is a pointer to the last character of where it was found. The return type is currently ignored.

The code is below. It is the same as the other Trie code example however it has the dump() methods added and a tweak to track the size of the largest term in the Trie.

https://github.com/eskeels/trie_code_generator

Sample code

An example callback function. It uses std::distance() to work out the offset.

int myCallback(const char * pStart, const char * pbuff, const char * resultString, const char * position)

{

std::cout << "Found word :" << resultString << std::endl;

if (pStart && position)

std::cout << "At position :" << std::distance(pStart, position) << std::endl;

return 0;

}

// This is the search() function output from the call to dump().
typedef int (CallbackFunction)(const char * pStart, const char * pbuff, const char * resultString, const char * position);

const char * search(const char * pStart,  const char * pbuff, CallbackFunction cf )
{
  const char * p = pbuff;
  const char * pRet = NULL;
  const size_t maxWordLen = 7;
  while(*p)
  {
  switch(*p){
  case 'c':
    switch(*(++p)){
    case 'a':
      switch(*(++p)){
      case 't':
      // found a word:cat Store pointer to last character of where it was found.
      pRet=p;
      cf(pStart, pbuff, "cat", p);
        switch(*(++p)){
        case 's':...

...

...

   int main(int argc, char* argv[])
  {
      Trie<char> t;
      std::map<const void *,std::string> dictionary;
      std::vector<SearchResult<char> > searchResults;

      AddWord<char>("cat", t, dictionary);
      AddWord<char>("cats", t, dictionary);
      AddWord<char>("peter", t, dictionary);
      AddWord<char>("wendy", t, dictionary);
      AddWord<char>("hook", t, dictionary);
      AddWord<char>("hooks", t, dictionary);
      AddWord<char>("party", t, dictionary);
      AddWord<char>("pillows", t, dictionary);
      t.dump();
      return 0;

}

// Run once calling the dump() function and then capture the output.

std::ifstream myfile ("c:\\Users\\soswin\\peterpan.txt");

std::string peterpan;

std::string line;

if (myfile.is_open())

{

while ( getline (myfile,line) )

{

peterpan.append(line);

}

myfile.close();

}

while( p && (*p != '\0') )

{

p = search(&peterpan[0], p, &myCallback );

}

}