Showing posts with label 24 game. Show all posts
Showing posts with label 24 game. Show all posts

Thursday, November 21, 2013

How Does Twentyfour Challenge Work?

Download Twentyfour Challenge (it's free) for Android and iOS from these locations:
Google Play
iTunes Store






The Phonegap Diaries describe how the Twentyfour Challenge app was built, but they don't really describe how it works. That's what I'm going to do here.

You probably guessed that the app has a built-in (recursive descent) parser that processes what is in the expression text box on the solver screen.
Within the app the text box does not permit data entry. If it did the user could just type in the goal number (say 24) and would immediately be rewarded with solving the problem. While parsing the code, it also builds an expression tree reflecting operator precedence for this ANTLR grammar (ANTLR is not used within the app):

grammar twentyfour;
solution:	expr ;
expr	:	multExpr ('+' multExpr | '-' multExpr)*
	;
multExpr:	atom ('*' atom | '/' atom)*
	;
atom	:	RATIONAL
	|	'(' expr ')'
	;
RATIONAL:	'0'..'9'+ ('/' '0'..'9')+;

The parser and rational expression evaluator are at the heart of the application, but where do the problems come from? The problems (and there are hundreds of them) are pre-programmed within the application. Each has this form:

// lvl :goal:   tuple1   :   tuple2   :     solution
    "4 : 24 : 6,10,15,6  : 2,10,15,10 : ((15-10)*6)-6"

A valid problem must have these properties:
  1. One of the tuples must yield a solution whereas the other must not
  2. The correct tuple values must appear in the solution expression.
  3. The solution expression must evaluate to the goal
Note that there may be more than one valid solution expression using the correct tuple. This just reflects the fact that 4 = 2+2 and 4 = 2*2. Only one of these valid solutions is pre-programmed, but the user can enter either solution to get the correct answer.

This brings up the subject of hints. I tried lots of alternative versions of the 24 game from the iTunes store. Most use four operands and some of the problems would stump me for minutes on end. All of the programs have a timer which makes you nervous as the seconds keep ticking away. If only the app would give me a hint!

That's it! in the next version of Twentyfour Challenge I will make the app both harder and easier. I will implement a level 4 of difficulty (that is, four operands) and I will implement a hint function at all levels of difficulty.

So how do hints work? There are two contexts -- the problem screen (below) and the solver screen.


Here the hint has been given as the incorrect tuple is disabled. The user should click the active tuple and move to the solver screen.

On the solver screen the hint button progressively shows the solution to the problem in the hint area (below).

Is this the best design for hints? Maybe not, but it certainly was easy to implement using regular expressions. The program examines the canned solution and extracts the operands from it. Here's the regular expression used to extract integer operands:

game.hintNumbers = game.problemSolution.match(/(\d+)/g);
game.hintSolution = game.problemSolution.replace(operand, "?");

When hints are given it just substitutes these numbers back one by one.

At first I though the hints should build on the progress the user has made on her own. It would suggest the next operator or operand (or clear a bad operator/operand). This was very hard to implement. Keep it simple, Sam!

Finally I should mention a back office application I wrote (thankfully) in Java that generated level 3 (three operands) and level 4 (four operands) problems. I had to write this program to guarantee that the pair of tuples for level 4 problems had the desired property of one correct and one incorrect tuple (the incorrectness had to be guaranteed).

This was done by brute force computation. The program generates four random integers and then all possible expressions using them as operands. It then evaluates each expression tree and records the results. Here's some output from the program:

	"4 : 24 : 8,11,15,9 : 6,9,18,8 : ((9-8)*18)+6",
//                                6-((8-9)*18)
//                                ((9/18)*8)*6
//                                6/((18/9)/8)
//                                ((6/18)*8)*9
//                                9/((18/6)/8)
//                                ((9-8)*6)+18
//                                18-((8-9)*6)
//                                ((6*9)*8)/18
//                                ((6*9)/18)*8
//                                8/((18/6)/9)
//                                (6*9)*(8/18)
//                                (6*9)/(18/8)
//                                (6/18)*(9*8)
//                                (9*8)/(18/6)
//                                (6+18)*(9-8)
//                                (6+18)/(9-8)
//                                (6*8)*(9/18)
//                                (6*8)/(18/9)
//                                (9/18)*(6*8)
//                                (6*8)/(18/9)
//                                (9-8)*(6+18)
//                                (6+18)/(9-8)
//                                (9*8)*(6/18)
//                                (9*8)/(18/6)
//                                (8/18)*(6*9)
//                                (6*9)/(18/8)

Obviously this problem has tons of solutions, but there is no solution involving [8,11,15,9].

Friday, October 11, 2013

Phonegap Diaries: Summary

Here's a bullet point summary of my lessons learned.

Bright Spots

  • Phonegap lives up to its promise
  • JQuery Mobile also lives up to its promise.  It game me a better UI and excellent portability
  • Translation from Java to Javascript is not too difficult.
  • There exist real unit testing tools for Javascript

Disappointments

  • <audio> tag and its API had spotty implementation (not working on iPad2 and Galaxy devices).  Why it works on some devices (iPhone4 w. iOS6) is beyond me.
  • JQM documentation needs significant improvement
  • Apple process for releasing to iTunes store is both lengthy and bizarre
  • Lost all i18n capabilities using HTML5 / javascript

Gotchas

  • iOS upgrade on a device is irreversible
  • stackoverflow.com is good source of info but can mess you up:
    •             right answer to a different problem
    •             right answer for a specific version of JQM (or phonegap, or css, ...)
  • javascript type system is tricky.  
    • For example $mobile.changePage("problem_screen?newProblem=false") cases a transition to the problem screen.  The parameter passed is 'false'.  But 'false' evaluates to true.  Huh? 'false' is a string that needs to be converted to Boolean false.

Unsolved problems

  • Can all information for platform generation emanate from "config.xml?"
  • What is the best way to detect and report javascript errors?
  • What can be done to speed up application load time (5-8 seconds)?

Plans for the Future

I plan future versions of Twentyfour Challenge that include these features:
  • a new level using four numbers
  • a "give me a hint" function during game play
And I'm waiting for feedback from a couple of middle school math teachers whom I know.

Phonegap Diaries: Process

Introduction

This article discusses the process used to develop Twentyfour Challenge.  First you have to understand the project structure.

Project Structure

Below is the file structure for Twentyfour Challenge as a PhoneGap project:

phonegap-projects
|____.DS_Store
|____Twentyfour                 <= PhoneGap project root
| |____.cordova
| |____.svn
| |____merges
| |____platforms
| | |____android                <= imported into Eclipse/Android
| | | |____AndroidManifest.xml
| | | |____ant.properties
| | | |____assets
| | | | |____www
| | |____ios
| | | |____build
| | | | |____Twentyfour.app
| | | | | |____www
| | | |____ Twentyfour.xcodeproj    <= imported into XCode
| |____plugins
| |____www              <= source code here! Dreamweaver site root
| | |____config.xml
| | |____css
| | | |____index.css
| | |____img
| | | |____logo.png
| | |____index.html                 <= main page
| | |____js
| | | |____index.js    
| | |____res
| | |____spec
| | |____spec.html

Most of my work is under that www folder and this is what really needs to be under source control.  There are platform specific changes that need to be made under android and ios folders also.

Development Process

After some fits and starts I got into this basic cycle:
  1. Write new html and/or javascript within DW
  2. From DW launch Chrome on index.html page
  3. Set breakpoints on pageinit events within application
  4. Execute application looking for errors/exceptions/bugs
  5. Fix errors/exceptions/bugs in DW
  6. Repeat

Simulator Testing

Periodically I would test the application in either an AVD (Android Virtual Device) or the iOS simulator.  Cordova CLI made this incredibly easy to do:

cordova build ios
cordova emulate ios

The last command will launch the ios simulator and give you a feedback on the look and feel and basic functionality.  But it gives you no information about what's going on within the application.  So you must use XCODE (Eclipse for Android) and launch the simulator (AVD for Android) from there.  This will show any errors that ios detects so you can correct them.

Device Testing

At some stage you have to start testing on a physical device.  You will need to use Eclipse with the ADT to run your app on an Android device, or XCODE to run it on an ios device.

On Android I only tested on my current smartphone – a Samsung Galaxy Stellar model.  On ios I tested on an iPad2 and several iPhone4s.

Icons

Don’t forget those icons!  Whereas there are a reasonably small number of icons to develop for Android there are an unreasonably large number of icons to develop for ios.

Don’t forget the all of those screenshots and splash screens that you have to provide.

Summary

The process I describe should include all of the rabbit holes that I went down trying to find solutions to my problems; however, I choose not to mention them.  Google (and stackoverflow) should be mentioned as primary development tools as these were the only means for getting unstuck when I was stuck.

Other postings:




Phonegap Diaries: Technologies

Introduction

Here I’m going to review the programming technologies used in the Twentyfour Challenge.  These include:
  •         Html5
  •          CSS3
  •          Javascript
  •          JQuery Mobile
  •          PhoneGap

Html5

There’s not too much to say about Html5 as I only used a couple of features that are specific to it:  local storage and the <audio> tag.  I also used a specific tag that is crucial to all PhoneGap projects.
Local storage is incredibly easy to use.  I use it to store the game options for Twentyfour and to keep track of the high scores.  The code below saves the game options:

function storeOptions () {
 // must use JSON stringify here!
 localStorage["tfc.options"] = JSON.stringify(options);
}

Here’s the code that reads the stored options:

function loadOptions () {     
 // are options in localStorage?
 if (localStorage["tfc.options"]) {
  options = JSON.parse(localStorage["tfc.options"]);
  // Options that are not strings need to be converted
  options.difficulty = Number(options.difficulty);
  options.count      = Number(options.count);      
  options.soundEnabled = Number(options.soundEnabled);
 }
 game.numSystem = options.numSystem;
 game.difficultyLevel = options.difficulty;
 game.countProblems = options.count;
 game.soundEnabled = options.soundEnabled;
};

The tag is complemented by a simple DOM-oriented API to play the sound file that is referenced.  It is also very easy to use.  The sound file (applause) worked in the Chrome browser, the iOS simulator, and an iPhone 4 device running iOS6.  It did not work in my own Android device (Samsung Galaxy Stellar I200), my iPad2, and another iPhone4 running iOS7.  I know I did everything right so I decided not to advertise the applause function.

A crucial <meta> tag needed by PhoneGap (really just the html5 compliant browser) is:
<meta name="viewport" content="width=device-width, height=device-height, initial-scale=1, minimum-scale=1, maximum-scale=1" >

There are many stackoverflow questions regarding the application’s web page being shown in a teensy-weensy font.  The solution is to add the above meta tag.

There’s one more thing that almost drove me crazy regarding a brower-based application – the back button.  The application runs as a “WebView” (Android terminology) where the browser does not display any “chrome”  (not Google Chrome, this is chrome like the back button, forward button, refresh, etc.).  This works fine on iOS but on Android there is a hardware back button.

I found that while playing a game of Twentyfour you must not use the back button at all as it destroys the state tracking that the app must perform.  I will discuss the solution later in this article.

CSS3

Most of the styling for Twentyfour comes from JQuery Mobile.  My hat is off to the professionals that developed CSS/html code that is portable across Safari, Chrome, and Internet Explorer, especially since the vendors of these browsers compete against one another.

I did, however, have to define a few styles for specific situations.  Here’s the problem “goal” which is really a button with some style changes.


The style changes are:

.goal-style   {
  text-align: center;
  background: chartreuse;
  ui-disabled: true;
}

 The trick to achieving this style is to add it dynamically when the page is rendered.  

            $('#problem-goal').addClass('goal-style');

The most important reason for learning CSS is due to the fact that JQuery uses its notion of a selector extensively.

Javascript

Ah, Javascript, how do I hate thee?  I speak these words as a Java programmer who trusts the statically typed language completely.  Remember that Twentyfour started as a native Android application that at its heart contained six classes with 775 lines of code (carriage returns counted here).  This includes a simple algebraic expression parser and evaluator.

Since I was skeptical of translating my Java code to Javascript by hand, I first sought an automated solution in the Google Web Toolkit (GWT).  Google created the GWT so they could create sophisticated browser-based applications (think Google Maps) in Java and then convert the client part to html/javascript.  I did get my 775 lines of java code translated by GWT, but then realized that there was no way to incorporate the generated javascript into a PhoneGap application.

So I hand translated to Javascript using techniques documented by David Flanagan in “Javascript: The Definitive Guide.”  It resulted in six classes and 588 lines of code.

Yes, there were type conversion surprises during development, but thorough testing flushed them out.  I developed unit test cases for the important code and gained the desired degree of confidence in the reincarnated algebraic expression parser and evaluator.

On every page of the application I included all of the Javascript files of the application (including JQuery Mobile files).  This was recommended in various books and Internet articles that I read.  It also benefits the use of a Javascript debugger.  Chrome, for example, will not allow you to set breakpoints on a page if it doesn’t see Javascript included on the page.

There are a couple of takeaways from this:
  1.        You must order your Javascript includes avoiding forward references.
  2.        You have to live with an enormous number of global variables.

JQuery Mobile

The technology I had the most difficulty with was JQuery Mobile (JQM).  The technology (including JQuery itself) has been going through many rapid revisions.  And there is the fundamental fact that JQM loads a document into the browser’s DOM and manipulates that one DOM thereafter.  This means that you get one chance to set up your event handlers.

Let me backtrack and try to re-express myself.  For the longest time I could not get my JQM page events to fire properly.  My stackoverflow searches resulted in conflicting information:  “use ‘bind’ on the pageinit event.”  “No use ‘on’ event.”  “Sorry you’re both wrong use ‘delegate’.”  No matter what I tried the JQM event never fired off my handler code.

Then I realized that the DOM is created exactly once by JQM and just updated when new pages are loaded via AJAX (really HJAX here).  The “binding” code that worked for me is shown below.

$(document).delegate('#index', 'pageinit', function() {
  console.log('#index: pageinit');
  // local event handlers
  $('#play').on('click', function() {
    console.log('play clicked');
    startGame();
  });
});

This breakthrough got me off the dime so I could learn the JQM widgets and events.  The most confusing event is one of the most important – the ‘click’ event.  Due to the nature of clicking using a mouse versus tapping on a touch sensitive screen, JQM differentiates separate events: ‘tap,’ ‘click,’ and ‘vclick.’  I started with ‘click’ but found it introduces an annoying 300 ms delay which isn’t good for rapid play.  So I switched to ‘tap’ which has no delay by occasionally has its own unwanted side-effects (ghost clicks).  ‘vclick’ wasn’t any improvement so I left the implementation with ‘tap.’  I finally learned that 'tap' works fine as long as you immediately stopped event propagation.

// event handlers
  
$("#score-ok-btn").tap (function(e) {
  e.preventDefault();
  gamePauseAudio();
  $.mobile.changePage('index.html');
});

Another surprise from JQM is that when you manipulate one of its widgets you must explicitly tell JQM to refresh its display of the widget.

$('#num-probs').val(game.countProblems).slider('refresh');

There were tons of stackoverflow questions asking, “Why doesn’t my updated widget show the update?”  Answer: “you didn’t refresh it.”

PhoneGap

As I mentioned in a previous blog PhoneGap gives you free packaging of your browser application and some level of Javascript access to native device APIs.

I thought I could live without any need for device-specific API but that Android hardware “back” button was a source of much aggravation.  If the user clicked in the middle of a game the entire game state would be invalid and many Javascript errors would occur.

So the back button became my nemesis as it has been forever for web developers.  I thought of several approaches:
  1. Disable the back button
  2. Manipulate the browser’s stack of “back” pages
  3. Catch every page transition and only allow the transitions for a “normal” game
  4. Detect when the hardware back button was pressed
Well #1 is prohibited.  #2 is difficult given the DOM APIs available.  #3 requires a lot of careful programming and is very brittle.  #4 is supported by PhoneGap.  After exploring #1 through #3, I found A PhoneGap API (see the Events API)  that solved the problem completely.  When the hardware back button is pressed on Android (iOS doesn’t have this) then just jump to the application homepage.  Thank you, PhoneGap!

PhoneGap also does the packaging and in this area it encourages you to use Adobe’s PhoneGap build service.  I did not use this approach for a couple of reasons:
  1. It costs money (there is a limited free plan)
  2. You need to package, deploy, and test your app on real devices before a release build.
The build service drives off the application’s config.xml file.  I discovered more documentation on config.xml at Adobe’s build site than I did at W3 Consortium (there’s a minor standard for widget packaging) and at the PhoneGap site.

It is not clear to me if the PhoneGap CLI tools process config.xml the same as the PhoneGap build service.

Summary

There’s a lot of technologies involve here.  JQuery Mobile keeps its promise for great looking portable UIs across mobile clients (Javascript too).  And PhoneGap delivers in its packaging for specific platforms.

Other postings: