A Sliding Puzzle for the PyBadge and PyBadge LC

15 tile sliding puzzle

A plastic  sliding 15 puzzle using numbers

The sliding puzzle has a long history. The first one, a 4×4, 15 tile puzzle, was made in 1890.  A plastic version is shown to the right. The puzzles may have letters forming words or have pictures instead of, or in addition to, numbers. Basically, the tiles are randomized, and then must be returned, by sliding adjacent tiles into the open space one at a time, until the puzzle is returned to the original arrangement.

Many such puzzles have been made, in various sizes. In addition to physical puzzles, video versions can be found on computers and the web.

This is a sliding puzzle game written in #CircuitPython for the @Adafruit #PyBadge and PyBadge LC. It uses pictures for the puzzle, with numbers superimposed to make the puzzles easier to solve. It is configurable so that different images can be used, and it supports both 3×3 (8 tile) and 4×4 (15 tile) puzzles. The tiled graphics approach used in the Adafruit displayio library is ideally suited for a sliding puzzle game.

How it Works

PyBadge showing Santa image

Complete image for Santa puzzle

PyBadge showing scrambled puzzle

PyBadge showing scrambled puzzle

PyBadge showing puzzle solution

PyBadge showing solved puzzle

After initial setup and bookkeeping, the program has an infinite while loop. It roughly follows a state machine pattern with the the states being “intro”, “setup”, “play”, and “solved”.

“intro” displays the puzzle image and then asks the player to select either a 3×3 or 4×4 puzzle. Once a selection is made, the state transitions to “setup.” In this state, the puzzle is scrambled and the scrambled puzzle is displayed. Then the state transitions to “play.” In “play”, the program monitors the up, down, left, and right buttons and moves the tiles accordingly. After each move, the puzzle is checked to see if it is in the solved position. If so, the state transitions to “solved”. Once in the “solved” state, the program displays a “You Won” message, then the full image. It then waits indefinitely until the player either presses START to go back to the “intro” state and play again or turns the badge off. The software is open source and published on GitHub.

A Note on Solvability

If one scrambles the puzzle by starting with the solution and then making random allowed moves the puzzle can always be solved. However, with this approach, it takes many, many such movements to really randomize the puzzle. If, instead, one simply places each tile at random, it turns out that only half of the possible arrangements can be slid back to the solution. Borrowing from what others have done, my code chooses a totally random arrangement, then checks if it is solvable (see the “solvable” function in the code). If not, it randomizes the puzzle again, and repeats this process until a solvable arrangement is found and used. The rules for solvability are:

  1. If the grid width is odd (e.g., 3×3), then the number of inversions in a solvable situation is even.
  2. If the grid width is even (e.g. 4×4), and the blank is on an even row counting from the bottom (second-last, fourth-last etc), then the number of inversions in a solvable situation is odd.
  3. If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.

The plastic slider puzzle shown at the top of this post is not solvable. The blank is on an odd row from the bottom (the first), and there is just one inversion, an odd number.

How to Play the Game

To play, simply load the software onto the PyBadge and turn it on. The display will first show the complete puzzle image, and then will ask you to press the “A” button for a 3×3 (8 tile) puzzle or the “B” button for a 4×4 (15 tile) puzzle. One slot is always empty so that tiles can be moved. Once you have made your selection, you’ll see the puzzle image with the pieces, in the solved state, and then the puzzle will be scrambled for play. The 4×4 puzzle is significantly harder than the 3×3 puzzle and will take more moves to solve, but both are fairly easy with practice.

Use the 4 directional buttons to slide a tile at a time. The goal is to get the tiles arranged in numerical order, left to right and top to bottom, with the empty spot on the bottom right. Once you have done this, you win! After the complete image is displayed upon winning, you can press the START button to play again. Sometimes you need to press the button a couple of times.

Stuck? There are a number of heuristics for humans to use to solve these puzzles (as well as heuristic algorithms for computers). The approach that works for me is documented here.

Changing the Puzzle Images and Creating Your Own

The parameters.py file stores several parameters, including the name of the folder where the puzzle images are stored. To change, for example, from the Santa to the witch puzzle, simply edit the line: puzzle_graphics_folder = “santa” to puzzle_graphics_folder = “witch”. I have provided three sets of images for the puzzle: Santa, a witch, and a Valentine’s Day floral image:

Flowers and "Happy Valentine's Day" text.

 

Santa, sleigh, and reindeer

 

Flying witch in front of moon, with bat.

To make your own puzzles, you need to create 3 bmp images:

  • The full image, to be saved as “full.bmp” in a new folder
  • A tile image for the 3×3 puzzle, to be saves as “tiles3.bmp” in the same folder
  • A tile image for the 4×4 puzzle, to be saved as “tiles4.bmp” in the same folder. .

These images must be exactly the right size in order for the program to work. The full image and 4×4 tile image must be 160 pixels wide by 128 pixels high. The 3×3 itile image must be 159 pixels wide by 126 pixels high.

Start from the full image. To make the 4×4 tile image, black out the pixels on the lower right of the image (x coordinates 121 – 160, y coordinates 96 – 128). You can also put numbers on what will be each tile to make solving the puzzle easier To do this, I use an image editing program to add a layer with a set of grid lines creating a 4×4 grid. Then I blacken out the lower right tile and put numbers in the upper right of each tile. Then I delete the grid layer and save the image as a bmp file. Follow the same process for the 3×3 tile image, but first re-scale the total image to be 159 x 126 and use a 3×3 rather than 4×4 grid. Once you have saved the three files in a new folder, change the puzzle_graphics_folder line in the parameters.py program to point to the new folder name.

 

Multi-Function PyPortal Information Display

Pyportal front viewAdafruit’s Pyportal is a pretty powerful little device. One of it’s main functions are to grab and display data from internet APIs, but it can also easily log data to the cloud using Adafruit IO, has a couple built in sensors, and can be used to play games and perform other functions. Per Adafruit’s overview page, “the PyPortal uses an ATMEL (Microchip) ATSAMD51J20, and an Espressif ESP32 Wi-Fi coprocessor with TLS/SSL (secure web) support built-in. PyPortal has a 3.2″ 320 x 240 color TFT with resistive touch screen. PyPortal includes: speaker, light sensor, temperature sensor, NeoPixel, microSD card slot, 8MB flash, plug-in ports for I2C, and 2 analog/digital pins.”

It’s called the  Pyportal because it provides a portal (window) to information on the Internet and it’s programmed in CircuitPython, which is Adafruit’s fork of MicroPython and is an implementation of the Python programming language for microcontrollers.

There are a lot of examples of single-function applications available, such as weather, air quality, event count-down clock, and even how many astronauts are currently in space, along with their names. What I wanted to do was to have the device cycle through multiple applications. I ended up coding it to provide

  • The day, date, and time (inspired by how cruise ship’s change out a piece of carpet every day in the elevators to tell you what day of the week it is),
  • The current local weather,
  • The latest “shower thought” post from the shower thoughts subreddit, and
  • The current value and change from the previoius day for the S&P 500.

The project ended up to not be quite as easy as I thought it would be, but still pretty easy. I ended up restructuring a lot of the examples code to work better with scrolling through multiple functions, but the final result still borrows heavily from the examples previously posted online.

In this post, I won’t repeat the basics for getting up and running, which can be found online, but I will do a brief walkthrough of my code, which is posted on gitHub. To use it yourself, you’ll need to edit the “secrets.py” file to provide your WIFI login information as well as sign up with the API providers and put your personal keys or ID in that file. You will also want to provide the location id for your location for the local weather, rather than mine, in the main program.

Overview (code module)

The program consists of a main module that first takes care of initial setup, making the wifi connection, and initializing variables, for example, the location ID for the local weather and the URLs for the various data sources. Then it launches an infinite loop to go through and access and display the various types of data. In each case, there is a timer so that the URLs are not constantly being visited each loop.

For the weather and S&P 500 applications and initial background screen is loaded and briefly displayed. This changes to a different background depending on the current data. For Day / Date/ Time and for Shower Thoughts the appropriate background screen is initially loaded and remains the same while that app’s data is displayed.

For each application, the program checks to see if it’s time to get fresh data from the internet (which occurs the first time the app runs and on a fixed schedule after that. If it does, it updates the old raw data from the internet. If not, the old raw data is kept. Then the program calls an application-specific python module t that extracts the relevant data from the JSON, formats it, and returns a text_group object for display. text_group is part of the displayio library for CircuitPython. I encourage interested readers to read the linked guide to the displayio library, as it took me some time to figure out how all the pieces fit together.

The display is then updated by appending the text group to splash attribute of the previously created Pyportal instance. splash is a displayio Group that is automatically displayed on the screen. After a delay to allow the update to remain on the screen for the specified number of seconds the Pyportal splash.pop() method is called to remove the text_group that had been added. If this were not done, Pyportal.splash would just keep getting bigger and bigger as each app runs over and over through the endless main loop.

I could probably refactor the main loop to make some things more generic and then move them into a common function call, rather than having so much separate for each application.

Day / Date / Time (day_graphics module)

Day, date, and time display on the PyPortal

The PyPortal does not have an RTC, so while it has an internal clock function, it tends

to drift. However Adafruit provides their own time service to call and update the local time. This function is called once per hour to update the local time.

The day_graphics module parses out the date and time information from time.localtime() to extract the day of the week, day of the month, the month, and the year. It puts this in the desired string formatting and specifies the font and location on the screen for each displayed element.

Weather (openweather_graphics module)

Current Weather Displayed on the PyPortal

For the weather, I chose to use openweathermap.org as the source for weather data and base my code on Adafruit’s PyPortal Weather Station example. That site has the local weather for my location and also has nice background icons for each weather type and whether it is daytime or nightime. There are several ways to specify the location you want the weather for, and various types of information available. This is all explained on their website. The example cited above used cityname and country, but that is ambiguous for my location, so I used their ID code for my location, which is unique.

The processing is very similar to the day/date/time app, although there is some additional work to convert temperature, which the API returns in degrees Kelvin, to Fahrenheit.

The icons are not downloaded using the API, but rather are stored on the PyPortal. The API returns the id number of the icon to be displayed. For this application, two items are returned from the function call: the text_group and the file name for the background image.

Shower Thoughts (st_graphics module)

A “shower thought” displayed on the PyPortal

Shower Thoughts is a subreddit for “sharing those miniature epiphanies you have that highlight the oddities within the familiar.” Two recent examples are Taking notes in history class is rewriting history and You’d think the generation that grew up playing Oregon Trail would have more respect for some of these diseases. There is a JSON API to get these posts and I decided that it would be fun to have these cycle through.

The concept for this app is similar to the others, and in fact, only one field (the title) needs to be extracted from the JSON field (one of the rules of that subreddit is that the entire thought must fit in the title). However, the thoughts can still be rather long. If I used the small sized font, they generally appear rather small, but if I use the medium ones I have to truncate the thought n the middle. So the program checks the length, and uses the medium sized font if the message is short enough and otherwise uses the small sized font.

S&P 500 (market_graphics module)

The S&P 500 value displayed on the PyPortal

The final application that this cycles through is getting the current value of the S&P 500 and comparing it to the previous day’s close. The data is obtained using a free API provided by Alpha Vantage.

Again, the processing is very similar. The customized features for this app is that the color of the amount and percent change is set as either green or red, depending on whether or not the index is up or down, and the background image is similarly selected to have either an upwards green arrow or a downwards red arrow.

Other Notes

The Pyportal is designed so that when something is written to it from a PC it does a soft reboot and starts running the main program. This is to make it really easy to do updates. The problem some folks have had, including myself, on a Windows 10 machine, is that it constantly does this soft reboot when plugged into either of my PCs. This doesn’t happen when it’s just plugged into a power source, then it runs fine. Apparently something keeps trying to write to it. As a work around, one can go into the REPL and type:

import supervisor
supervisor.disable_autoreload()

This turns off the auto-reload and soft reboot feature. Once that is done, one needs to stop a running program (type CTRL-C in the serial window) and then reload and restart by typing CTRL-D in the serial window. If anyone has a permanent fix for this problem, I’d love to hear it.

Sometimes the ESP32 board seems to have glitches, and an error condition is created and valid data is not returned. The try / except code in the main program just skips out of the application where that occurs and tries the next one. So far, this has caught and provided a work-around for all but one error, which popped up once after the application had been running for several days.

Summary

The PyPortal is a great little device that is capable of doing a lot (this example didn’t make use of the touchscreen features, built-in sensors, or i/o lines). Hopefully this example will be useful to others, especially if you want to have the PyPortal perform multiple functions, rather than only serving a single purpose at a time. Again, the code is available on gitHub.

Dynamic Toll Data: My First “Real” Alexa Skill

Summary

This project uses a combination of screen-scraping and an API to obtain current travel speeds and the current variable toll costs for Interstate 66 inside the beltway in northern Virginia, and provides the information to users via Amazon’s Alexa voice service. To try it out, first enable it (either just say “Enable sixty six tolls” or visit Sixty Six Tolls in the Amazon skills store). From then on, just say “Open sixty six tolls.”

Resources

The project uses Alexa’s voice service. The code is written in Python 3, using the Alexa Skills Kit SDK for Python. The code runs on AWS’ lambda service. It also makes (minimal) use of DynamoDB to store user-specific information. Travel times are scraped from the Virginia DOT’s (VDOT’s) 511 Virginia Traffic Information website. The real-time toll prices are obtained via an API to VDOT’s SmarterRoads data portal. Web scraping and XML parsing was done using Python’s Beautiful Soup library.

The python code as well as the interaction model (a JSON file) are available at https://github.com/ViennaMike/I-66-Tolls

Background

I was looking for a project that would use one of the data sets on the SmarterRoads portal, and I decided that it would be useful to be able to check the dynamic tolls on Interstate 66 inside the Beltway in Northern Virginia. Inbound traffic is tolled between 5:30 and 9:30 am, while outbound traffic is tolled between 3:00 and 7:00 pm.

The tolls are dynamically adjusted to maintain high speeds. While the toll may change between checking the cost at home and the time a driver reaches their entrance, it’s still useful to have an idea of the highly variable toll, especially since tolls for the entire 10 mile length have sometimes spiked at over $40. 

I had previously written a simple quiz skill using Amazon’s template, but this was my first custom skill.

Description

The overall architecture for the Alexa skill is shown below:

High Level Architecture

When a user interacts with the skill, the input is processed according to the interaction model that the developer defines in the Alexa Skill builder. This is captured in a JSON file. The skill builder is also where you tell the skill where to find the execution code for handling requests and ready a skill for certification and distribution.

In the case of 66 Tolls, there are eight custom intents, along with the Alexa built-in intents such as HelpIntent, FallbackIntent, StopIntent, etc. The custom intents are:

  • get_speeds for getting speeds and travel times for the two roughly parallel travel options (I-66 and US-50)
  • get_toll_hours to get static information on the hours that tolls are in effect
  • get_details to get additional static information about how the dynamic tolling system works
  • list_interchanges to get a list of inbound and outbound entrances and exits
  • get_toll to get the current toll price for a specified direction from a given entrance to exit
  • save_trip to save the user’s most frequent entrance and exit in each direction
  • get_favs to report back to the user what trips he has previously saved.
  • get_specific_help to provide help on particular types of requests (get toll, get speeds, and save trips).

When the skill is opened by a user who has previously saved a trip, the skill immediately returns the appropriate current inbound toll if it’s in the morning, or outbound toll if it’s in the evening or afternoon.

The Alexa Skills Kit SDK contains built-in functions to simplify interacting with Amazon’s DynamoDB NoSQL database. This skill uses a simple DynamoDB table to store the user_id (the key), most frequent inbound entrance and exit, and most frequent outbound entrance and exit.

By far the easiest part of the project was the code to get the travel times and tolls from the two VDOT sources. There is an API for the tolling data, and I had to do some simple web-scraping to get the travel time data. This code can be found in the get_travel_times() and get_tolls() functions in the code.

Developing the voice interaction model took multiple iterations, and I found that as time went on, I was able to improve the dialog model while reducing the number of intents and number of slot types associated with each intent. However, even then, I found that the first released version of my skill didn’t work for users the way I had intended. For the most part is worked well technically (there was one bad bug), but users other than myself said things differently than I had thought they would, and asked for help differently. It definitely pays off to not just spend time thinking of how users will interact with your skill (as I did at first), but in having others test out your skill as well, and getting there feedback.

Because this was new to me, it took considerable time, as well as trial and error, to figure out how to write the handler code, and especially how to handle the session and persistent attributes and the interaction with DynamoDB. I used a large number of resources, with the best being the Skill SDK documentation, the Color Picker sample app, and A Beginner’s Guide to the New AWS Python SDK for Alexa, by Ralu Bolovan. As described in the documentation, the python SDK supports two coding models, one based on functions with decorators, and the other based on classes. I chose to use classes, but the Color Picker example uses decorated functions.

Some of the hassles I had came from two factors: 1) the interface to Alexa skills has changed over time. It’s been improving, but this also meant that some of the samples and tutorials on the web are out of date. 2) While there is thorough documentation, a lot of tutorials and examples focus on simple demonstrations. For this reason, it may have been better for to step back and read more of the SDK rather than always jumping in. For example, I needed to have my code do something every time an intent was called, regardless of what the intent was. It turns out this is handled by Request Interceptors and Response Interceptors, which most of the simple samples leave out. This, along with the thorough walk-through on using DynamoDB, is why I found the Beginner’s Guide to the New AWS Python SDK for Alexa to be so helpful.

I originally wanted the invocation for the skill to be “i sixty six tolls,”, but I found that Alexa had trouble recognizing this as the invocation. For this reason, I had to make the invocation “sixty six tolls” rather than “i. sixty six tolls.”

I also found that if you use Alexa’s built in “confirm” capability, then when your code is called for the first time, the handler_input.request_envelope.session.new is set to False, apparently because the built-in confirmation request kicked off the session. That’s something to be careful of. For this and other reasons, I ended up checking whether or not I had previously initialized the session attributes, rather than whether or not the session was new.

The last technical bug I fixed was that I hadn’t thought about what “local time” was to the server. I have been naively thinking that since I was using AWS’s Northern Virginia server, the local time would be the US eastern time zone, but all Lambda servers use GMT as their local time, which makes a lot more sense. So I used the pytz library to convert to local time.

For the voice interface, I found I had to expand the list of synonyms for slot values (such as the names used for exits), add more specific help queries, besides the comprehensive, and therefore long, “help” intent, and make use of the interface’s built-in capabilities for checking user-provided slot values, which I hadn’t read about in the simple tutorials.

I hope that this example will prove helpful for others who want to write their own custom Alexa skills.