tag:blogger.com,1999:blog-41607314626680277112024-03-13T23:34:06.187-07:00Unexpected Result'Unexpected Result' is a tech blog by a self-taught developer whose passions for continuous growth and to stay busy led to an accidental Master's in Computer Science and a fortuitous position with a fantastic software consultancy firm. Each post or series highlights a point of interest to software developers and users, and features tangents that follow the author's stream of consciousness.Steven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-4160731462668027711.post-5547488661824407692020-03-17T09:00:00.001-07:002020-10-06T01:27:49.722-07:00The March of Progress<p>In ancient times, I was assigned to a legacy project that was nearly 30 years old. Much of the team on that project had been on it for just as long. These are <i>not</i> inherently bad things. There is great value to a team with rich experience and intimate project and domain knowledge. Risk can arise, though, from technology, tooling, and processes that are allowed to stagnate unnecessarily, despite easy access to free education and resources. If you are reading this, chances are that you know what it's like to be in tech; the world is constantly moving, and if the momentum leaves your project behind, it only gets harder to catch back up, no matter how important catching up might be.</p>
<p>When I joined the aforementioned project, the team had not yet (in their <i>twenty-some-odd years</i>) implemented any kind of source control. Keeping a project alive without source control for that long without catastrophe struck me as miraculous, and dangerous. A degree of waste was also in play, considering the process overhead in manually managing a large code base among a growing team of developers. The merge process for the flagship product at the time I left the company was still (I wish I were kidding) to copy the entire code base onto a network drive with my changes in it; the team lead would then pick that up and copy my changes among his own for each release, by hand.</p>
<p>Despite being low on the totem pole at the time, I voiced my concerns early, and gently. Management responded with confidence (and I hazard to say, defensiveness) that their project was not suited to source control. Besides, they said, the transition to any source control system would be too risky, and cost too much time. Determined to demonstrate otherwise, on my own time I carried out a proof of concept to show both that the project <i>was</i> suited, and that the transition itself was feasible. Leadership was not impressed, and declined to move on source control.</p>
<p>Management's hand was finally forced, though, by the continued growth of the project's complexity and team size. With myself added to the team, it had nearly doubled in size, in just half a year. The existing process of copying <i>gigabytes</i> of monolithic project code and assets back and forth for every significant change (let alone the manual process of merging that code) was no longer sustainable. The project lead, however, continued to resist the transition to source control. He raised concerns over poor reliability, and worried that source control would be too slow and restrictive in its capabilities. When pressed, he admitted not researched the topic, including not having read my emails to him on the topic or looking at my proof of concept even in passing. Incidentally, though it is not the topic of this essay, that was the moment I decided I was going to start looking for a new job.</p>
<p>By way of disclaimer, I am not myself a team lead (though I aspire to become one some day). However, having worked under several, I have observed and learned from some of the habits of leaders who I, personally, believe to be successful. Now, it's good to have an understanding of what I mean here by "success." The management team described above <i>considers themselves</i> to be successful, because their company has not failed and there have been no catastrophic failures of the software in the wild - yet. From my perspective, though, I see a great deal of churn on inefficient processes, which wastes time and energy that could be spent on new features or products; I see tremendous risk involved in the event major defects are discovered, rollbacks need to be made, etc; and I see stressful pain points for the developers and even the team lead himself in working within the confines of the existing system.</p>
<p>I would like to give this team the benefit of the doubt and say that it is fear that held them back, rather than laziness (and I do believe this to be the case). They did not understand what source control was, and so they were scared of it. The way they saw it, things just worked, and worked just fine. However, a small amount of research, an openness to change, and a relatively small amount of effort would have made their lives far and away better than under the existing system. I suppose the moral of the story, if there can be said to be one, is that some comfort with learning about the unknown can allow you to convert unknowns into knowns. And when you do that, you broaden your horizons, strengthen your skills as a team and an organization, and give yourself more tools with which to be successful. I, myself, have a natural tendency to hesitate and shy away from the discomfort of the unknown; but only by pressing on into the unknown can I uncover what is there, and build myself up for the next task ahead.</p>Steven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-67520976839126798092020-03-10T15:52:00.000-07:002020-03-10T16:22:08.987-07:00Inverted Mouse Scrolling in Windows w/o RegEdit<p>I love inverted mouse scrolling. Meaning, when I spin my scroll wheel <i>away from</i> myself (up), I want the UI to scroll down. When I spin the wheel <i>toward</i> myself (down), I want the UI to scroll up. This feels intuitive to me because it's how touch screens (phones, tablets, etc), and touch pads (Mac and PC laptops, notebooks, etc) all work. When you slide your finger upward along the screen or touch pad, the thing you're touching follows your finger upward. I never understood why scroll wheels behaved in reverse. To me, the default Windows scroll wheel behavior <i>is</i> the "inverted" one.</p>
<p>Unfortunately, Windows provides no native method of flipping this simple input. If you know what you're doing, and you have enough system access, you can modify the Windows system registry using <span class="code">regedit.exe</span>. This strikes me as a pretty invasive way to go about flipping something as simple as mouse wheel scrolling. But for some reason, this is the primary method I keep finding in searches. It turns out <b>there is an easier way</b> that doesn't require the same level of administrator privileges (though it does come with a potential downside).</p>
<div class="cmd-line">PS C:\> <span style="color:#EEE8AA">Get-ItemProperty HKLM:\SYSTEM\CurrentControlSet\Enum\HID\*\*\Device` Parameters <b>FlipFlopWheel</b> -EA 0 | <b>ForEach-Object</b> { Set-ItemProperty $_.PSPath FlipFlopWheel 1 }</span></div><br>
<div class="note" style="margin:0 4em">Shamelessly but usefully ripped from <a href="https://superuser.com/questions/310681/inverting-direction-of-mouse-scroll-wheel">this post</a> on StackOverflow.</div>
<p>The downside to this method, as you can see, is that the <span class="code">FlipFlopWheel</span> property is being set to 1 for every single object in our query. This may not be ideal for your situation. For me, I just needed a way to get my mouse wheel flipped, and to have it persist, without needing to go into the registry. I'm surprised that this issue has persisted so long, over so many iterations of Windows itself, that this StackOverflow question from over <i>8 years ago</i> is still relevant, but here's the solution!</p>Steven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com1tag:blogger.com,1999:blog-4160731462668027711.post-15637738041406765072020-03-10T04:49:00.001-07:002020-03-10T04:49:29.690-07:00Separation of Concerns<p>Rules are handed down from authority figures. <i>Best practices</i>, though, are born of community consensus on good ways to get things done. There are usually good reasons for certain practices to surface out of our collective consciousness. One simple, sometimes painful example is white space in code. The example is painful because there are so many ways white space can be used (or <i>ab</i>used). The broader community prefers a handful of styles; these make code easier to read and digest for other developers (and even our future selves). Proper use of white space, thus, has become a best practice. Tools now exist to enforce proper spacing; languages like Python even go so far as to <i>define scope</i> using white space.</p>
<p>Okay, let's get into it. I have a piece of gold-stamped parchment declaring me "Master" of computer science. I'm not so sure about that. In any case, there are certain best practices that <i>even I</i> can recognize as sensible, useful, and even <i>important</i>. When these practices are ignored (or willfully disregarded) it gives me the fingernails-on-a-blackboard shivers.</p>
<p>One such best practice is known as <i>separation of concerns</i>. There are many levels, high and low, at which it can (and should) be observed. The basic idea, however, is that you want a given piece of code or architecture to:</p>
<ul><li>do its job</li>
<li>do its <i>entire</i> job</li>
<li>do <i>no one else's</i> job</li></ul>
<p>Once you've called a function, you <i>should</i> be able to expect its job to be completed. Sure, the function might delegate responsibility to smaller helper functions, breaking the task into workable chunks; but when that function eventually returns, <i>the job should be done</i>. Importantly, <i>nothing else should have been done along the way</i>. When extra stuff gets done along the way - either intentionally or by accident - we call that a <i>side effect</i>. According to the tenets of <a href="https://medium.com/javascript-scene/master-the-javascript-interview-what-is-functional-programming-7f218c68b3a0">functional programming</a> and general coding best practices, <b>side effects are bad</b>.</p>
<p>My mission today is to use a frustrating, real-life example to illustrate the importance of this concept, leaving as much of my emotional baggage at the door as possible.</p>
<img style="height:15em" src="https://i.kym-cdn.com/photos/images/original/000/827/085/dbe.jpg">
<p>A company I used to work for had a design review process in place. All tasks required project lead approval before development could begin on a task. It meant some extra overhead, but I liked the sentiment. I think it's a fine idea to have strategies vetted by leadership and scoured for weaknesses <i>before</i> mistakes are made. Cool.</p>
<p>So my task was to add a reporting feature to our existing product. The existing feature retrieved documents from the back end, looping over them and calling a helper function to print each individual one. <span style="font-size: 0.8em">There were weaknesses in this design to begin with - you may wonder, as I did, why each individual document had to be retrieved with a separate query - but it wasn't my design and I just had to work with it.</span></p>
<p>Let's pause in brief review. Someone wants to print a batch of reports. They call the batch printing function, whose one job is to print a batch of things. We expect our function to:</p>
<ul><li>do its job (print the batch)</li>
<li>do its <i>entire</i> job (read each document file and print it correctly, i.e. perform sub-tasks that the main task depends on)</li>
<li>do <i>no one else's</i> job (don't randomly delete user accounts, etc)</li></ul>
<p>Still with me? Okay. Now we get to my task and the problem I encountered.</p>
<p>At the batch printing level, I was to gather data on each individual report in the batch. This was to be aggregated and added to the final batch report. I came up with a few angles of attack. With separation of concerns and best practices in mind, I avoided solutions that leaned on side effects. What do I mean, here? I mean that I wanted to be clear with what each part of the code was doing; and I wanted the code to do nothing more than it was asked.</p>
<p>For example, my new function would <i>return data to be aggregated</i>, rather than <i>modifying aggregation data by reference</i>. This meant I had to add another function to manage the aggregation itself. A little extra work? Maybe. But the result was crystal clear code, functions with crystal clear purpose and methodology:</p>
<h4>Function A, aggregator</h4>
<ul><li>do its job (aggregate data from multiple calls of getter)</li>
<li>do its <i>entire</i> job (return aggregated data)</li>
<li>do <i>no one else's</i> job (don't email users' credit card numbers to other users)</li></ul>
<h4>Function B, getter</h4>
<ul><li>do its job (gather data about a document)</li>
<li>do its <i>entire</i> job (query back end and return the result)</li>
<li>do <i>no one else's</i> job (don't drunk dial Function X)</li></ul>
<p>Without getting into details, I can tell you that even this solution felt a little messy to me. Within the project and resource constraints, however, and in light of what followed next, this was a positively glowing example of separation of concerns.</p>
<p>The project lead rejected my design proposal wholesale. I was instructed to write a system of helper functions <i>into the ORM class for the documents</i>.</p>
<p>Confused?</p>
<p><i>me too</i></p>
<p>He specified hard-coded mock-ups of data from unrelated classes to be written into the ORM. This would, he argued, allow us to perform testing and comparisons of data and models from <i>within the ORM class</i>. In other words, outside code that called the ORM class constructor would have no idea that a partial testing framework and a whole suite of hard-coded data was being instantiated, parsed, judged, and passed around, complete with database interactions, that had <i>nothing to do</i> with the the ORM itself.</p>
<p>Imagine troubleshooting the reason for data coming in from the wrong table. Imagine database calls being made when you aren't making them. Imagine your report's performance profile degrading, only to find out that someone had hard-coded your document's ORM class with sample data and testing infrastructure ... for some random batch document report printing functionality. Can you imagine that?</p>
<p>I can; I lived it. This was an extreme example, but let the allegory of the hard-coded ORM stand as your reminder to keep best practices and separation of concerns close to your heart.</p>Steven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-46877823984084950142016-10-11T10:58:00.001-07:002016-10-11T10:59:37.528-07:00Switching to React - First Impressions<p>In earlier posts I wrote that I planned to use <a href="http://handlebarsjs.com/">Handlebars</a> as my templating engine for the <a href="https://github.com/stevenkitzes/cyoag">CYOAG project</a>. Things happened since then that caused me to change directions towards <a href="https://facebook.github.io/react/">ReactJS</a>. I'll take a moment here to say that I've had no contact with or sponsorship from the Handlebars or React teams. This is all just my opinion, formulated based on personal experience working with these technologies on the side-project level. Incidentally, though I'm enjoying working with React, this is notwithstanding my opinion of Facebook, who we have to thank for React. So there's some food for thought.</p>
<p>So why did I make the switch?</p>
<p>I realized Handlebars was more challenging to learn than a templating system needs to be. I didn't find community support to be as extensive or helpful as I'd like. Handlebars also hasn't enjoyed industry adoption as extensively as React, so from a career growth aspect React seemed a better choice. Ironically, the reason I chose Handlebars originally was because we used it on a project at work. But after talking to the lead dev on that project, I learned it wasn't selected for its quality or utility, but due to circumstance. Finally, having built my first working Handlebars prototype, it just didn't <em>feel right</em>. There's no remedy for that.</p>
<p>So, React. It's already big in the web dev scene, has been for some time, and continues to grow. Whether it'll become a longstanding mainstay in industry remains to be seen, but <a href="http://www.blindfiveyearold.com/wp-content/uploads/2015/06/signs-point-to-yes-300x189.jpg">signs point to yes</a>.</p>
<p>I'm surprised to say it, but React was easier to pick up than Handlebars. It surprises me because React has lots of new ideas and syntax you have to learn, while Handlebars has relatively few and advertises itself as a "no frustration" templating system; which, I can attest, is patently false. React, likewise, advertises itself as "painless," also a lie. I'm being a little harsh here, but point being that I find React <em>less</em> painful than Handlebars, despite the fact that neither is a walk in the park.</p>
<p>To be fair, Handlebars lends itself better to smaller projects. The infrastructure and planning required to use it <em>is</em> lighter. To get Hello World up in React, you have to do more work, download more libraries, and learn more technology: JSX, props, state, rendering, components and their lifecycles, etc. In Handlebars, you slap up a template and you're off to the races (relatively-ish). <span class='note'>Build processes are another story. I found precompilation to be roughly equivalent in difficulty from Handlebars to React. The documentation is better for React, though, due to superior community support. More community support means more flavors of help, and a greater likelihood one of them will match your style of learning.</span></p>
<p>The appeal of React is reusability, structure, and organization. From a mile-high perspective, let's say you're the app lead for Facebook, and you want a UI component to let people "Like" things. All kinds of things; wall posts, images, events, shared links, comments, everything. With React and some proper planning, you can make a single component displaying a "Like" link, that dynamically hooks up to whatever needs to be "Like"d. The component itself doesn't care what it belongs to. You can plug-and-play it wherever. One downside to this, as mentioned above, is that the initial development of this component is relatively heavy. Once you have it built, though, you can reuse it dozens, hundreds, millions of times, at very little dev cost.</p>
<p>Another downside is that you have to be conscious of your component structure when building larger applications. CYOAG is not a large application, but if I didn't think about component structure in advance - and thus plan out how state was to managed and communicated among components - I'd find myself having a <a href="https://openclipart.org/image/2400px/svg_to_png/222252/feels.png">real bad time</a>. The complexity of component interactions isn't hard to wrap your head around, but once you've built them, that complexity makes maintenance and modification a chore, and a considerable risk.</p>
<p>Part of this is because state and props "cascade" (my term) from parent components to child components when you build an application The React Way. So if anything changes along the cascade path, you have to make sure you account for it at every step and in every handler. Of course, things change as we go, this is life; but I think we can all agree it's to our advantage to minimize this, and with React, best practices in design amplify this risk/advantage relationship.</p>
<p>In short, React encourages better software engineering principles. Other technologies allow you to start hacking out a solution before thinking it through, which can lead to other kinds of headaches down the road.</p>
<h3>Non-technical Example</h3>
<p>We can use my (thus far incomplete) <a href="https://stevenkitzes.github.io/cyoag/docs/react-design.html">React component design doc for CYOAG</a> as an example for this. I won't bother quoting the doc here, you can read it if you like. In short, the application state is best managed at the top level. One easy reason to explain for this is that if you allow children to manage state, you'll quickly find yourself making more calls in integration, and having a hard time communicating among components. So we manage the state at the top level, and (in short) provide getters and setters for particular parts of the state to children through props.</p>
<p>When building your components, it's helpful to know what state you'll need to be passing down to children from the ancestral point of view; and what props to expect to receive from the descendent's point of view; and what functions will be needed in order to manage and pass these around. And later, if changes need to be made, you need to keep this "flow" of state in mind to preserve it.</p>
<p>These are my early days with React and my opinions and understanding will undoubtedly develop as I develop applications using React. Once I start using this code "in production" on CYOAG, I'll have plenty more to say, I'm sure.</p>
<p>Thanks for reading!<br />
- Steven Kitzes</p>Steven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-18176241272236552772016-10-03T01:41:00.003-07:002016-10-03T13:01:52.916-07:00Circular Dependency in Relational Databases<p>This post is going to have an element of storytelling to it, because while some elementary understanding of SQL will be required, the Cliff's Notes seem to tell it all:</p>
<blockquote>You probably want to avoid circular dependencies in relational databases.</blockquote>
<p>These Cliff's Notes are incomplete, a little vague, a bit of an oversimplification, and up for debate besides. Some RDBMs (relational database managers) handle circular dependency better than others, and some problem domains necessitate circular dependency. Take, for example, table representations of nodes in a graph that allows cyclical paths.</p>
<p>However, not all problems necessitate circular dependency, and some RDBMs prohibit, or aren't capable of handling, circular dependencies. In these cases, we need to design around the limitations of our RDBM, and in any case, it's good to be aware of circular dependencies, just on principle. The purpose of this post is thus to share my own early explorations of database design, and to describe how I broke out of the circular dependency trap on a small side project.</p>
<p>Some project context will help here. I've been working on a <a href="http://www.stevenkitzes.com/2016/08/precompiled-handlebars-ridiculously.html#cyoag">passion project</a> for a little while now. The high level idea is to build a "Create Your Own Adventure" game, where all content is user-generated, and the best story line branches rise to the top through a voting system like that used by <a href="http://www.reddit.com">Reddit</a> and <a href="http://www.stackoverflow.com">StackOverflow</a>. An important early part of this project involved designing a decent database schema to build the rest of the project on top of.</p>
<p class='note'>You may wonder why I chose an RDB (relational database) for this in the first place, rather than an alternative such as some flavor of NoSQL. I plan to host this on the AWS (Amazon Web Services) free tier, so I can learn more about AWS. Unfortunately, at the time I started this project, the AWS free tier didn't offer any option other than RBDs. Incidentally, an RDB is almost certainly best for this type of application due to the interrelationships of different types of data, but that's a topic for another time.</p>
<p>So, how did a circular dependency surface in my design?</p>
<p>One feature I want this app to have is position persistence. When a visitor is reading the story, I want to remember where they left off, so they can conveniently come back and resume reading the story at a later date. My plan was to give the Users table a column called Current, to track a given user's position in the story. In other words, a story node would appear as a foreign key in the Users table.</p>
<p>The Nodes table was designed with an Author column to record who had authored a given story node. This was to support a variety of features, such as prohibiting authors from voting on their own posts, and allowing an author to edit their contributions, while protecting those posts from being edited by others. Unfortunately, you'll notice this means a user (author) is now a foreign key in the Nodes table.</p>
<p>Uh oh.</p>
<p>Now I have a node ID as a foreign key in the Users table, and a user ID as a foreign key in the Nodes table. This is a circular dependency of sorts, and is a block in SQL. You'll find <a href="http://stackoverflow.com/questions/3891535/circular-dependencies-in-foreign-keys-use-it-or-avoid-it">some argument</a> as to whether circular dependencies are fundamentally bad practice, or whether SQL just suffers some unhappy limitations. After all, what's conceptually wrong with tracking current node in the Users table, and author in the Nodes table? There's no conflict in authority over the data, since a user doesn't own its current node in this read-only context, it's just a position marker. To be fair, SQL doesn't understand our motivations, and to argue that an RDBM's designers could have done more toward enabling us to convey these human intuitions to the machine is too philosophical for this post.</p>
<p>Whatever the reason and our opinion of it, MySQL forbids this kind of interdependency. The solution I came to was to create a simple table called Positions, with a compound primary key consisting of two foreign keys, one being a user ID from the Users table, the other being a node ID from the Nodes table. Despite some apparent duplication of information, this works for the simple reason that the Positions table relies on Users and Nodes, but neither Users nor Nodes relies on Positions. I'll try to illustrate the improvement in design without opening Visio:</p>
<blockquote style='font-family:monospace'>
<p class='note'>An arrow (->) implies dependency</p>
<p><strong>Before:</strong></p>
<p>Users -> Nodes<br>
Nodes -> Users</p>
<p>As you can see, this yields Users -> Nodes -> Users, and so on, ad infinitum. This is bad.</p>
<p><strong>After:</strong></p>
<p>Nodes -> Users<br>
Positions -> Users<br>
Positions -> Nodes</p>
<p>We can combine two of these lines together to yield:</p>
<p>Positions -> Nodes -> Users<br>
Positions -> Users</p>
<p>but you can see that this doesn't introduce any loops, or circular dependencies, as my first design did.</p>
</blockquote>
<p>Thanks for reading!<br>
- Steven Kitzes</p>Steven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-69678746713032967742016-08-29T10:26:00.000-07:002016-08-29T11:19:08.305-07:00Alexa Skill Hackathon Takeaways<p>This past weekend we had a hackathon at work, focused on developing Skills for the (relatively) new <a href="https://www.amazon.com/Amazon-Echo-Bluetooth-Speaker-with-WiFi-Alexa/dp/B00X4WHP5E">Amazon Echo</a>. The purpose of the hackathon was to expose us to a technology we hadn't used before and explore what use cases might exist that we could leverage either internally, or for customers. We had a great time and built some really fun Skills along the way to learning the Alexa Skill development tools. We found there were pros and cons, as with anything, and I personally took away a few key lessons from my short time working with the Echo.</p>
<p>I want to take a moment here to point out that I wasn't paid or encouraged by anyone, anyone at all, to share my experience on this blog. Amazon, to my knowledge, had no part in this hackathon; it was an internal event we did just for fun and exploration. I just want to solidify what I learned by revisiting it in a writeup. So let's talk about the Echo!</p>
<p>When you buy the Amazon Echo, you are buying a very nice piece of hardware that connects you to a service named Alexa, which is where the magic happens. You make your voice request, and then Alexa uses <em>Skills</em> (voice applications) to do something useful or fun in response to your request. First of all, I want to say that Alexa is a lot of fun to work with from a creative product standpoint. Working with Alexa's voice API provides a vast landscape of opportunities to be creative in ways that feel fresh and new. Alexa is also a lot of fun to use from the consumer standpoint, for me at least. I've heard many people say they don't know what they would do with an Echo if they had one, but to someone with that complaint, I'd say the cliche that <em>there's an app for that</em> holds true here.</p>
<p>Alexa has tons of capabilities out of the box, covering everything from checking the weather, to listening to podcasts, news, and music, to telling jokes, to making purchases on Amazon through your account. The system can integrate with home automation tools, and work in concert with apps on your phone to manage shopping lists, to-do lists, and other handy utility features. Additional Skills can be obtained from the community through the Skill Store to cover all kinds of additional fun and useful scenarios. Alexa has lots to offer.</p>
<p>In case this is reading too much like an advertisement, don't worry. There's plenty for Amazon to work out with the Echo before I would ever buy one at full price. That being the first of my concerns: I find it to be unjustifiably expensive. You're buying a speaker, with a hardcore microphone array, connected to the web via wi-fi; that's really all the hardware you get, and it comes in just shy of $200. It <em>is</em> a very nice enclosure, and the speaker itself is exemplary; but without internet, this thing is a brick. The Echo does no work of its own locally. All services are performed by Alexa on Amazon's side, and piped back to you over the web. I can go to OK Google, or Siri, or even Cortana for a lot of what Alexa can provide; so $180 feels brutal for the sole perk of having your voice assistant always-on. A big downside of the Echo, compared with voice services provided by Google, Apple, and even Microsoft, is that the Echo is immobile, whereas your phone is always with you. Adding to the cost, some of the handy features (music providers being a prominent one) require subscription fees; and the buy-by-voice feature, while convenient, can feel a little dangerous since Alexa doesn't recognize which voice is yours. (Buying each other socks without permission became a running gag throughout the hackathon.)</p>
<p>Along those lines, Alexa doesn't always understand voice input clearly, so you sometimes find yourself repeating commands to get her to hear you right. I find Google's voice recognition to be a tad more reliable. Alexa also does poorly if you try to give her a command in a room with other people speaking. She can't differentiate among voices, and this is very frustrating at times. Granted, this is an emerging technology, and natural language and voice recognition are very challenging problems for computers to handle, but from a practical, daily usage standpoint, this is often a frustrating shortcoming.</p>
<p>By far, though, my biggest gripe about working with Alexa is as a developer. Every technology has its idiosyncrasies, but I found learning the Alexa Skill developer tools to be a particularly harrowing experience. First of all, you need to use Amazon Lambda to host your Skills. Amazon Lambda is a cool idea, but developing Alexa Skills thereon is a new kind of challenge, and not in any particularly fulfilling kind of way. The tools for building Skills are a little clunky and the documentation is practically non-existent. They have some nice features, like the ability to test your Skills without needing to go through the time-consuming process of conversing with Alexa repeatedly. However, in order to deploy Alexa skills, you need to access two separate dashboards; the Skill itself, the Lambda logic, is deployed on AWS Lambda through the AWS console, but you have to separately log into the Amazon Developer Console to access Alexa configurations and tools to define things like user interactions, and recognized user phrases. Where is this documented? <em>Great question.</em></p>
<p>The feedback from the system when something goes wrong is minimal. You'll get messages like "Syntax error." That's it. What kind of syntax error? Where? Your only option is to lint the code yourself and hope that any of your mistakes can be found that way, or be so good at programming that you never make typos or logic errors. There's not much available in terms of debugging help. By its nature, Amazon Lambda also faces the limitation of weak session and state management. This is one reason why some of us at the hackathon resorted to using Alexa as a forwarding service, simply to translate voice into API calls to a remote server (EC2 in this case) that hosted more complex service implementations outside of Amazon Lambda.</p>
<p>As mentioned earlier, the documentation for this set of developer tools is sorely lacking. The official Amazon guide points to a blog post from 4 months ago that is not only incomplete, but also already out of date, with screenshots and instructions that are both flat-out incorrect. It was a headache trial-and-erroring our way through the process of developing our first Alexa Skill and finding third-party tutorials for Skill development. We <em>were</em> able to pull it off, but it was a lot harder than it needed to be. It could have been an hour long process if the documentation had been half-way complete or at least up-to-date. I would expect sketchy documentation from open source projects made by volunteers; not from a top tech company, on a service they profit from, that other developers are meant to use as part of a business model. Maybe I expect too much, but fair or not, that is my expectation of a for-profit system provided by a sixty-five billion dollar tech company.</p>
<p>It really doesn't feel like Amazon is bringing their A-game to the Alexa developer community. If these issues cropped up during an open beta or in a staging environment, that would be one thing, but this is a public-facing, monetized platform. One or two of the features <em>are</em> sub-labeled as beta as of this writing, but the features work fine; the process and interface design are just abysmal, and the documentation is being provided by home-use amateurs because Amazon isn't providing it. I personally find that to be a weak effort on Amazon's part.</p>
<p>Overall, I do like the Echo and Alexa, and I would like to have one if the price were more reasonable. I find it fun and useful. I would also be excited at the opportunity to do more development on Alexa Skills now that I know the process, but it was needlessly painful to learn the ropes compared with other platforms.</p>
<p>Thanks for reading!<br>
- Steven Kitzes</p>Steven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-42170790069787028552016-08-07T11:15:00.003-07:002016-10-03T00:14:35.609-07:00Precompiled Handlebars - A Ridiculously Clear Tutorial<h3>This is a step-by-step tutorial on getting introductory, hello-world level, precompiled Handlebars up and running.</h3>
<blockquote><strong>Just so you know</strong>, if you're already fluent in NPM or otherwise want to skip ahead, you can <a href='#good-stuff'>jump to the good stuff</a></blockquote>
<p>It's my first time writing a tutorial like this. I plan to take you through it <em><strong>very slowly, but very clearly</strong></em>, so that even beginners can understand if they have some programming experience, but little to no web or templating experience. If this style of tutorial proves helpful to people, I'll follow up with a second tutorial on more in-depth Handlebars features. I encourage you to send any feedback that will improve this tutorial. Now let's dive in!</p>
<p class='note'>For those who read my recent post about a "real" side project, I know I promised a more detailed explanation so I'll tack it on at the end here. ;)</p>
<p>First, some context. What you're reading was born partly of frustration. I had a needlessly difficult time figuring this out for myself, and I want it to be easier for others in the future. Therefore, today's post has become three things: a precompiled Handlebars primer, a learning experience post-mortem, and an experiment in writing effective tutorials <em>for</em> beginners, <em>by</em> recent beginners. Handlebars isn't hard to learn, the concepts are approachable; but existing tutorials, StackOverflow Q&As, even the Handlebars team's own documentation assume you already know web dev and templating, so their tutorials give condensed steps for experts to hit the ground running.<p>
<p>Not much help for a beginner like myself. Therefore...</p>
<h2>Handlebars for Beginners, by a Beginner</h2>
<p>I'm going to take you through the steps I had to take to get this project moving, from the perspective of someone with beginner-level knowledge of web development, and zero knowledge of templating. I won't leave any of the steps out or assume you know any of them, and I'll try to cover the minutiae and details that many tutorials gloss over, either because they figure you already know them, or because it doesn't even occur to them that you might not know them. I also don't like tutorials that speak only to Windows users when I'm stuck on Unix for work, or vice versa, so I'll try to cover these cross-pollinations as well.</p>
<p>The only thing I won't explain in detail is installing NPM, the Node Package Manager. You'll need to have that running in order to precompile. It is relatively easy to get NPM going, <a href='https://nodejs.org/en/download/'><strong>here</strong></a> are installers/binaries for Windows, Mac, and even Linux.</p>
<blockquote><strong>Just so you know</strong>, the installer is intended to automatically add NPM to your PATH variable, but in some cases an error may prevent that. I'm tempted to describe the fix for this, but due to the number of operating systems out there, it's beyond the scope of this tutorial. Just be aware of this if you install NPM and it doesn't work, and it's not immediately obvious why.</blockquote>
<a name='good-stuff'></a>
<h2>Brass Tacks</h2>
<p>First, you must install Handlebars for Node.js via NPM. From the command line (any directory is fine), issue the following command. <span class='note'><strong>Note for Windows users:</strong> think of the '$' symbol as your 'C:\>' or other command line prompt.</span></p>
<div class='cmd-line'>
<p>$ npm install -g handlebars</p>
</div>
<p>Now you should be able to run Handlebars on the command line from any directory. To test, try typing the following, and you should be rewarded with your installed Handlebars version, in my case, 4.0.5:</p>
<div class='cmd-line'>
<p>$ handlebars -v</p>
<p>4.0.5</p>
</div>
<p>That is all the infrastructure you need. Now I'll take you through the process of building a few files that you'll need. This is one place in particular I find that other tutorials fail to be clear, so I will do my best. First of all, I'll assume for clarity everything is taking place in the same directory, so make yourself a directory and keep all files there. I encourage you to improve your infrastructure and employ best practices, but later. First let's make sure we understand this technology.</p>
<h2>We will end up with a total of 4 files:</h2>
<ol>
<li><em>We will make</em> a Handlebars temmplate file, with the .handlebars file extension (not strictly required, but consider it so for the purposes of this tutorial)</li>
<li><em>We will make</em> an HTML file to inject our template into</li>
<li><em>We will download or link to</em> the Handlebars library provided by the Handlebars team</li>
<li><em>The Handlebars precompiler will output</em> a JavaScript file which performs our template injection (details to follow, don't get intimidated yet if this sounds foreign or complex)</li>
</ol>
<p>Some folks will likely argue the best practice is to link in your code to an outside source for your Handlebars library (file 3). That may be so, but to make your life easier, I recommend downloading it and keeping a copy locally for the purposes of this tutorial. You can get it <a href='http://handlebarsjs.com/installation.html'>here</a>. The version I got is called <em>handlebars-v4.0.5.js</em>.</p>
<p>File 4 is output by the precompiler, so we won't worry about that yet. Let's start by making a very, very simple template (file 1), to inject into our HTML file (file 2). What you need to know for now, is that a Handlebars template is basically made up of a mixture of raw HTML, and special Handlebars tags (discussed later). What that means, is that we can get started with an extremely simple example template containing <strong>just HTML</strong>, to make sure we have a grasp on the concepts, and that we're doing it right. So here's file 1, in all its young glory:</p>
<strong>hello.handlebars</strong> <span class='note'>File 1</span>
<ol class='code'>
<li><p>Hello, world!<p></li>
</ol>
<p>Yup, that's it for file 1. Precompiling is very simple and straightforward, assuming Handlebars is installed properly. What you need to know for now, is that Handlebars takes .handlebars files and turns them into .js files. So let's use Handlebars to turn <em>hello.handlebars</em> <span class='note'>(file 1)</span> into <em>hello.js</em> <span class='note'>(file 4)</span>:</p>
<div class='cmd-line'>
<p>$ handlebars hello.handlebars -f hello.js</p>
</div>
<p><span class='note'>... or more generically ...</span></p>
<div class='cmd-line'>
<p>$ handlebars <input-file>.handlebars -f <output-file>.js</p>
</div>
<p>Note that the Handlebars precompiler doesn't give you any real feedback on the command line. Just check that you got a .js file out of the deal, and that it contains some JavaScript in there, including your HTML. At this point, if all has gone well, we should have the following files, all in the same directory:</p>
<ul>
<li>File 1: hello.handlebars <span class='note'>Handlebars template file</span></li>
<li>File 2: <span class='note'>not done yet</span></li>
<li>File 3: handlebars-v4.0.5.js <span class='note'>or version of your choice</span></li>
<li>File 4: hello.js <span class='note'>output from file 1</span></li>
</ul>
<p>So all we need to do now is put together a very simple HTML file into which our template will be injected. <strong>Note</strong> that in this case, I'll be including some JavaScript in my HTML file. Normally, it may be wise to separate your JS from your HTML files, but for simplicity I'll keep it all together for this tutorial. Let's start with a very basic HTML file and build our way up from there. I'll highlight changes at each following step in green, and describe the changes.</p>
<strong>hello.html</strong> <span class='note'>File 2</span>
<ol class='code'>
<li><html></li>
<li> <head></li>
<li> <meta charset='UTF-8'></li>
<li> <title>Handlebars Tutorial</title></li>
<li> </head></li>
<li> <body></li>
<li> <div id='content'></div></li>
<li> </body></li>
<li></html></li>
</ol>
<p>If you're new to HTML, most of this should still be approachable. Just note the <span style='font-family:monospace;'><meta></span> tag, which tells the browser what character encoding the HTML file uses; and the initially empty <span style='font-family:monospace;'><div></span> tag, which warrants <a href='http://www.w3schools.com/tags/tag_div.asp'>more explanation</a> (but for now, don't overthink it; it's a generic container for part of a page's content).</p>
<p>Nothing really special going on here, if you load this in a browser now, it'll just be a blank page. Just take note that <span style='font-family:monospace;'><div id='content'><></span> is the place in this HTML that I have chosen to inject my Handlebars template, which is why I gave it an ID.</p>
<p>Now I'm going to add in some vanilla JavaScript, whose job is singular: tell the browser not to try doing anything with any scripts, until all of them are loaded. <span class='note'>(If you want to do this using jQuery or other more advanced methods, I encourage it, but the point of this exercise is to be simple and to-the-point, so for now, we'll stay vanilla.)</span></p>
<strong>hello.html</strong> <span class='note'>File 2</span>
<ol class='code'>
<li><html></li>
<li> <head></li>
<li> <meta charset='UTF-8'></li>
<li> <title>Handlebars Tutorial</title></li>
<li> </head></li>
<li> <body></li>
<li> <div id='content'></div></li>
<li></li>
<li class='addition'> <script type='text/javascript'></li>
<li class='addition'> function init() {</li>
<li class='addition'> // This only runs after the whole page is loaded</li>
<li class='addition'> }</li>
<li class='addition'></li>
<li class='addition'> window.addEventListener('load', init, false);</li>
<li class='addition'> </script></li>
<li> </body></li>
<li></html></li>
</ol>
<p>Simple enough to follow, I think. Now, let's add in the scripts themselves, that the browser will load before running our <span style='font-family:monospace;'>init()</span> function.</p>
<strong>hello.html</strong> <span class='note'>File 2</span>
<ol class='code'>
<li><html></li>
<li> <head></li>
<li> <meta charset='UTF-8'></li>
<li> <title>Handlebars Tutorial</title></li>
<li> </head></li>
<li> <body></li>
<li> <div id='content'></div></li>
<li></li>
<li class='addition'> <script type='text/javascript' src='handlebars-v4.0.5.js'></li>
<li class='addition'> </script></li>
<li class='addition'> <script type='text/javascript' src='hello.js'></li>
<li class='addition'> </script></li>
<li> <script type='text/javascript'></li>
<li> function init() {</li>
<li> }</li>
<li></li>
<li> window.addEventListener('load', init, false);</li>
<li> </script></li>
<li> </body></li>
<li></html></li>
</ol>
<h2>Magic Happens</h2>
<p>We're going to inject our template with just 3 lines of code. You can do it in fewer, but for clarity I'm spreading this over more lines. I'll explain this process line by line following the new code below:</p>
<strong>hello.html</strong> <span class='note'>File 2</span>
<ol class='code'>
<li><html></li>
<li> <head></li>
<li> <meta charset='UTF-8'></li>
<li> <title>Handlebars Tutorial</title></li>
<li> </head></li>
<li> <body></li>
<li> <div id='content'></div></li>
<li></li>
<li> <script type='text/javascript' src='handlebars-v4.0.5.js'></li>
<li> </script></li>
<li> <script type='text/javascript' src='hello.js'></li>
<li> </script></li>
<li> <script type='text/javascript'></li>
<li> function init() {</li>
<li class='addition'> var target = document.getElementById('content');</li>
<li class='addition'> var inject = Handlebars.templates['hello'];</li>
<li class='addition'> target.innerHTML = inject();</li>
<li> }</li>
<li></li>
<li> window.addEventListener('load', init, false);</li>
<li> </script></li>
<li> </body></li>
<li></html></li>
</ol>
<p><span class='addition'>Line 15:</span> This is the easy part. We are just creating a JS variable to represent the <span style='font-family:monospace;'>$lt;div></span> we're going to inject our template into.</p>
<p><span class='addition'>Line 16</span> Here we are grabbing our template, and putting it in a variable called <span style='font-family:monospace;'>inject</span>. There are a few things here worth knowing. First of all, the reason we have access to the template at all, is because we included the <span style='font-family:monospace;'>hello.js</span> file we precompiled with Handlebars on the command line (file 4). We have access to the <span style='font-family:monospace;'>Handlebars</span> variable because it is provided by <span style='font-family:monospace;'>handlebars-v4.0.5.js</span>, file 3, which we also included. As a convenience, Handlebars allows us to refer to our precompiled script by file name, without needing the extension (e.g. <span style='font-family:monospace;'>'hello'</span> instead of <span style='font-family:monospace;'>'hello.js'</span>). The last thing that is <strong>critical</strong> to understand, is that <span style='font-family:monospace;'>inject</span> is now a function, not a string or other variable type. You must therefore use it as a function, and that function <em>returns</em> the precompiled template as a string.</p>
<p><span class='addition'>Line 17:</span> Now that we have our target, and our injection function, we can inject our template into the target. We call our template function, and assign it to the <span style='font-family:monospace;'>innerHTML</span> property of the target. Done! If all has gone well, you should be able to load your HTML and see your simple HTML template loaded into an otherwise blank page: "Hello, world!"</p>
<h2>Celebrate</h2>
<p>This write-up has given me a great opportunity to review what I learned in teaching myself Handlebars, and I hope this tutorial, written from the perspective of a web templating beginner, for other beginners, was helpful.</p>
<p>Thanks for reading!<br>- Steven Kitzes</p>
<hr>
<h2><a name="cyoag">CYOAG</a></h2>
<p>I promised to describe my side project, so I'll take just a moment to do that. (It'll be a quick moment, because that's all I have to spare at this particular moment, but I want to fulfill my promise of sharing my idea.)</p>
<p>In short, it's a user-generated Choose Your Own Adventure game. Many of us enjoyed these books as kids. The basic idea for those of you who are unfamiliar, is that you read a chapter, the book lets you make a decision for what the characters in the story should do, and you flip to different pages based on your choice and get to see different outcomes. I basically want to create a web-based version of this, where users not only get to see different outcomes based on their choices, but also get to contribute their own branches and paths to the story.</p>
<p>Of course, with users able to generate content, you could potentially have dozens of possible paths out from any given chapter (or 'node' or 'snippet', as I call them). In order to combat the potentially overwhelming number of options available, I plan to implement a voting system, similar to the ones used by Reddit or StackOverflow (but without the complexity of decay, though I may add that in later if needed... not likely). Basically, all paths will be available to any user by request, if they want to read and vote on them; but by default, the user will only be shown the top four most popular paths.</p>
<p>That's all I can give you for now, not because I don't want to share more, but due to time restraints... gotta jet! I've cobbled together a first-pass functional requirements doc for this project, so if you want to learn more, it's public on my project's GitHub page. You can check out all the gory details <a href='http://stevenkitzes.github.io/cyoag/docs/functional-requirements.html'>here</a>!</p>Steven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-74805417519136320202016-07-31T00:31:00.000-07:002016-07-31T00:31:52.664-07:00My First "Real" Side Project<p>Greetings, old friend, and well met, new acquaintance! You have stumbled across my dev blog at a fortuitous moment in my career. You can think of this as a reboot in many ways.</p>
<p class='note'>And I promise, if you read (or <a href='#firstRealSide'>skip to the bottom</a> of) this characteristically long-winded post, you'll find that it does, matter of fact, have a purpose.</p>
<p>At the most shallow level, I'm rebooting my blog. The old posts, I'm leaving them up for posterity. Some seem to have helped people, and I'm glad for that, despite a level of quality I'm not, in retrospect, happy with. <i>Oh, well</i>, as they say; <i>oh, well</i>.</p>
<p>At a deeper dive, I'm finding that I have rebooted myself. What manner of melodrama is this? Part of my self-improvement effort being a closer attention to a need for conciseness, I'll describe it thusly: I recently finished my Master's in Comp Sci. I'm psyched about it, in spite of myself, it's been a very trying road. I also recently landed my first <i>real</i> full time job as a software developer, with a fantastic company that I plan to talk about later, pending a discussion with leadership on the propriety of divulging various levels of trade secrets. In short, during the respite I gave myself between graduation and the first day of work, I realized that a day without career development, in <i>some</i> form or another, be it software development, reading, practicing, ideating, etc, was a day that felt in some sense hollow.</p>
<p class='note'>Note to self: 'in short'? Who am I kidding? Concision will never feature in this blog. I'm just going to accept that that is 'okay,' and that this is a place not only for sharing knowledge, but also for free expression. So I'll try and just enjoy myself a little writing these up, and hopefully the flavor of my style will stick on the back of your throat in a not wholly unpleasant way.</p>
<p>I digress. Point is, in my spare time, I've come to feel some kind of learning toward a better career as a software developer is not only fulfilling and rewarding professionally (and hopefully financially), but also personally. I find that I <i>enjoy</i> writing software. I prefer fun software, such as a near-complete, but technically in-progress web tool that I started on, and which I shall shamelessly plug posthaste: <a href="http://stevenkitzes.github.io/howmany">How Many Drinks In That Drink?</a> I put this little static web app together to help beer snobs track how much alcohol they're really drinking.</p>
<p>This was an incredibly rewarding project for me. Not only because the end result was useful to me personally as a craft beer fan. Not only because others will hopefully find it helpful, possibly in deeply meaningful ways. Not only because it is taking shape better than expected. But also more importantly because I learned a ton about a new software domain and new technologies in building it. This last point was, I have found in-spite-of-myself, probably the most rewarding part of building the tool and the part that has stuck with me the most.</p>
<p>To place this narrative in temporal context, How Many Drinks was made over winter break, basically January of 2016, so yeah, fair to say it's been a while since I worked on a side project; but the experience and the feeling it gave me stuck, and it's been gnawing at me ever since, however gently. Grad school resumed that spring term, delaying my ability to spend time on personal projects, then my month off between school and work was packed, I say <i>packed</i> with travel, and then I fell into this new job, and I fell <i>hard</i>.</p>
<p>Alright, now what manner of melodrama is <i>this</i>? Well, I won't name names because I haven't run the idea of connecting my employer to myself in this blog past my boss just yet; but I will say it's a software consultancy firm with a highly unusual, enthusiastic, and very genuine focus on growing talent internally, rather than burning it out and tossing it on the midden to make space for the next unfortunate soul. I won't get into too many details, but the basic idea is that they <i>take care o' ya</i> in a big way, protecting you from overwork, and making opportunities for you to grow both personally and professionally without taking your life away. Sounds too good to be true, right? Well, I'm not exaggerating in the least when I tell you with honest, genuinely unsarcastic, dead-straight, and seriously intense eye contact that I made it to the final level of on-site interviews at Google, and the interview at my current employer was equally challenging, yet <i>more</i> grueling. Rewards are earned, sometimes, I guess.</p>
<p>That felt a little tangential, but it has a point to it in the emphasis on career development without employee burnout. The basic policy is to keep client work to a sensible level, close to or even occasionally <i>below</i> 40 hours a week, to make space over the span of a reasonable work week schedule to spend on career development. Meaning, you get to work on building technical, business, networking, and other skills on the clock; and it's not only allowed, it's <i>encouraged</i>. I'm trying to think of a more melodramatically eloquent way to put this last, most salient point, but what it basically comes down to is that I'm absolutely psyched to fall into such an opportunity just at the same time I'm learning to really, truly love learning and career development in what I unfortunately have to refer to as a synergistic way. (I know, we all hate the word <i>synergy</i> because it has been so badly misused by middle management for so many years, but this particular synergy is both real, and startlingly pleasant.)</p>
<p><a name='firstRealSide'></a>You will soon realize that all of the above has been an elaborate way of leading you to an announcement that I am starting a new project; not only a side project, but a project of passion. I will be blogging about it regularly, discussing what I've learned, what I've achieved, and any pitfalls I've encountered; I set this explicitly for myself as a task. I'll be posting weekly, as the plan has it, both to motivate myself to get work done on it more quickly and also to practice blogging more quickly, frequently, and effectively (and yes, even concisely ... starting next post, as always).</p>
<p>The project itself, which I'll describe in next week's post, is already under way, and it's quite exciting and fun to be making progress on it already (in a sense you may not agree with calling 'progress,' but we'll get to that). In any case, hope to have you along for the ride, and even if you don't care to read up on my trials and tribulations, I hope you'll enjoy the result when it's done!</p>
<p>Thanks for reading!<br>
- Steven Kitzes</p>Steven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-65403679457089194902015-03-26T17:38:00.000-07:002015-03-26T17:39:11.359-07:00Troubleshooting Serial CommunicationsAfter two months of troubleshooting, countless gallons of coffee, endless hours of stress, several years off my life, and many square inches of cranial real estate lost to newfound baldness, I finally solved a longstanding, serious blocking bug with a single line of code. I don't know how useful the particulars might be to anyone who stumbles across this posting, but the thought process and methods used to narrow in on a solution might help other fledgling developers by giving them new angles from which to view problems. In any case, I want to document the process for myself, because it has been a very painful ride, and one I'd very much like to think I've learned from.<br /><br />
By way of context, I'm working on enabling two-way communication over serial COM ports using the Windows API. One application, written in C++, needs to communicate with another, written in C#. Both applications existed before this new use case was devised, and both applications were previously proven to successfully communicate over COM ports. However, when the two applications were set up to communicate with <em>each other</em>, the communications failed 100% of the time. I had to figure out why.<br /><br />
It's worth mentioning here that prior to finding myself attached to this project, I'd never been exposed to many of the concepts and technologies involved. I have some limited experience with C++, for instance, but not in a large-scale production environment. I've never worked with serial communications before, and never used the Windows API for C++, which is not as friendly to newcomers as other libraries can sometimes be. Some complexities were also encountered in the realm of threading, which I have some experience with, but not in the Windows environment. A big part of the reason this solution took two months is that I had to learn all of these concepts in parallel in order to start focusing in on the location and nature of the problem.<br /><br />
The first thing I did was to have someone walk me through the existing functionality and where the breakdown was occurring. It was explained and demonstrated to me that the client application, written in C++, was able to send a message to the server application, written in C#. The server reported successful receipt and parsing of the message, and reported a consistent attempt to respond. After that, there would be silence from both applications. The client reported that it was listening for a response from the server, but no response would arrive - or at least, the client did not report receiving it.<br /><br />
So began my adventure. The first thing I did was to look at the client side application and implement some kind of logging functionality. The existing code, having been whipped up in an apparent panic on a tight deadline, provided no logging - in fact, no output of any kind was visible to the user, and no comments or documentation were given in the code to help those who would later have to maintain or extend the application.<br /><br />
It took me several days just to implement logging, and there are a couple of reasons for this. First, as mentioned above I had never worked with C++ before, and learning the ropes on that front is not trivial, especially where file access and streams are concerned. But the bigger stumbling block in this particular case was the unorthodox use of the standard output buffer.<br /><br />
The original author of the client side software had been intercepting all standard output and copying it to a secondary buffer, where it was stored and later passed over a named pipe for use as input to an integrated service. Since there was no documentation of this method of message passing, it took many long, confusing hours and lots of help from more experienced developers for me to come to the understanding that every time I tried to use console output for debugging purposes, it was breaking integrated services because they were not expecting my debug messages to come in over the pipe! So console logging was out, and I had to do any and all logging strictly to disk (or to debug output in Visual Studio, where execution in debug mode was permissible), where the log file could later be read and investigated. Whew...<br /><br />
In any case, I did manage to get a logging feature set up and then it was off to the debugging phase. I set up logging output to report on program status throughout the execution of the client side code, as well as setting breakpoints to investigate the state of suspicious variables. This yielded some curious information.<br /><br />
The first thing I tried was to check the <span class='code'>ReadFile(...)</span> command on the client for errors. It turned out that the call to <span class='code'>ReadFile(...)</span> was returning error code 0, with a timeout. In other words, no errors were being thrown. The <span class='code'>ReadFile(...)</span> call was successful, and all arguments passed to it were valid, but nothing was being received before the given timeout parameter was met. I tried setting the timeout to infinite, and this resulted in the <span class='code'>ReadFile(...)</span> command looping, as you might expect, infinitely.<br /><br />
Since no error was being thrown, I assumed that the port was open, and that the client had successfully connected to it. This suspicion was reinforced by the fact that expected data had been verified arriving at the server, as explained above. However, just as a sanity check, I set breakpoints to observe the definition and state of the file handle used by the Windows API to represent and access the COM port itself. I verified, in this way, that the serial port handle carried the same definition and state when <em>listening</em> for a server response, as it did when it was sending a message <em>to</em> the server. As far as the client application was concerned, it was a simple matter of no data coming in over the seemingly valid port.<br /><br />
More sanity checks came over the following weeks. I started building simplified sandbox applications with the dual-purpose of learning, so I would feel more comfortable with the Windows API and COM port communications in general, and also to verify that the code worked as expected, both on the C++ and the C# sides. I built a simple C++ program whose only mission in life was to contact the server with a hardcoded, known-good message, and listen for a (and report the receipt of) a known-good response. It worked! This was my first sigh of relief, but didn't yield any immediate solution.<br /><br />
Keeping my momentum up, I built a simulated server with the same strategy in mind, just to ensure that there wasn't some idiosyncrasy in the existing server code that made it behave oddly. As expected, the simplified, standalone sandbox server I whipped up worked. My sandbox C++ client was able to contact my sandbox C# server over the expected COM port; the C# server responded over the same port; and the C++ client received and reported the server's response. Everything worked! Unfortunately, also as expected, the simple sandbox server also behaved exactly the same as the <em>real</em> server when used in conjunction with the real C++ client.<br /><br />
I felt I was back at square one. I had tried lots of things, and verified little more than the simple fact that everything <em>should</em> have been working! All the C++ code I wrote worked, and all the C# code worked. The <span class='code'>ReadFile(...)</span> and <span class='code'>WriteFile(...)</span> calls and even the <span class='code'>CreateFile(...)</span> calls, and all parameters passed to these functions, were identical - as far as I could tell. I even went so far as to duplicate the code I was using in the sandbox to build the COM port in the production application. This still did not avail.<br /><br />
Then (this morning) something interesting happened. I had been going back and forth between testing my sandbox apps and their production counterparts, and I realized that after running my sandbox app successfully any number of times, any failed execution of the production client permanently broke the COM port, even for future attempts at running the supposedly known-good sandbox app! This didn't make much sense to me, but I also stumbled across the fact that running a C# version of the sandbox client seemed to repair the COM port. Something was so dramatically different between the COM port setup in the C++ and C# applications that not only did the C# application run more reliably, it actually repaired the damage done by the production client, that the sandbox C++ client wasn't able to address on its own.<br /><br />
I did a side-by-side comparison of the code in the C++ and C# applications to see how they set up the COM port (yes, even though I had written both). I saw that the examples I had followed in building the C++ application had only set a few of the <span class='code'><a href="https://msdn.microsoft.com/en-us/library/windows/desktop/aa363214%28v=vs.85%29.aspx">DCB</a></span> parameters during initialization of the COM port. (<span class='code'><a href="https://msdn.microsoft.com/en-us/library/windows/desktop/aa363214%28v=vs.85%29.aspx">DCB</a></span> is a <span class="code">struct</span> in the Windows API that contains all the data needed to manage a COM port.) It only set up the parameters needed to establish a COM port connection under known good conditions. Since this had been working for me under most test conditions, and it hadn't even occurred to me that there were parameters that weren't being set one way or another, I didn't think to look there. And it turned out that yes, there were <span class="code">DCB</span> parameters that I hadn't even known were going uninitialized, because most of the time I didn't need them.<br /><br />
The C# application, on the other hand, had been developed based on a more thorough set of tutorials and examples, and included full initialization of all <span class="code">DCB</span> parameters; most importantly, the <span class="code">DTR</span> (Data Terminal Ready) and the <span class="code">RTS</span> (Request to Send) flags. Setting both of these explicitly to enabled or handshake mode, rather than the default disabled mode, suddenly fixed everything.<br /><br />
Now I felt a broad spectrum of mixed emotions. On the one hand, I was elated that a two-month troubleshooting session had finally, finally, finally come to an end. The problem was solved, and all would rejoice. On the other hand, it took me two months to solve the problem, and there was no rejoicing in that, especially given the simplicity of the fix, which was <em>not even</em> a one-liner. I only had to add a couple of arguments to an existing function call, it was that simple.<br /><br />
No one else on the project seems terribly upset with me, though. After all, each time I asked for help, more experienced developers did not see the solution either, or have a particular idea of where to focus the search. All of us went on many wild goose chases trying to pin this problem down, and it's a relief to have it behind us. Also on the bright side, though the wild goose chases did not, for the most part, yield anything beyond validation of pre-existing suppositions, they did teach me a lot about new ways to troubleshoot, debug, and test assumptions to ensure that you <em>do know</em> what you <em>think</em> you know.<br /><br />
Thanks for reading!<br />
- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-7778600773326852742015-02-22T04:13:00.000-08:002015-03-26T17:36:38.097-07:00Virtualizing Ubuntu with VirtualBox in Windows 8.1After my homework was done tonight, I decided to have a little fun and experiment with virtual machines and their relationships with their hosts. More on my ultimate goal with this experiment later, but it may suffice to say that the necessary means to the end included running a virtual machine with some kind of visual GUI interface with remote desktop access. I chose Ubuntu for this task because it's a free Linux based OS that includes a simple GUI that I'm familiar with.<br /><br />
I had a harder time than expected getting this all set up, for a few reasons. For one, it wasn't easy finding a comprehensive guide on how to do much of this. I did eventually find a very handy guide to setting up the basic Ubuntu VM in Oracle's VirtualBox <a href="http://navet.ics.hawaii.edu/~casanova/VirtualBoxUbuntuHowTo.html">here</a>. The guide is straightforward for beginners, but there were still sticking points for me that I want to go over.<br /><br />
The first few basic steps to pulling this off (as listed in the guide linked above) are to <a href="https://www.virtualbox.org/">get VirtualBox</a>, <a href="http://www.ubuntu.com/download">get a copy of Ubuntu</a> in <span class="code">.iso</span> format (32 bit versions are more reliable and easy to work with for this), and install Ubuntu into a new VM in VirtualBox using the <span class="code">.iso</span>. This is, however, already a departure from my initial expectation.<br /><br />
In the past, I've been running VMs from <a href="http://www.turnkeylinux.org/">TurnKeyLinux</a>. The fully provisioned TKL system images I've been using came in the form of <em>appliances</em>, which are extremely handy. VirtualBox allows you to import an appliance in a single operation; you don't even really need to configure anything. It will just run the VM with all the software you wanted provisioned. I most recently downloaded a LAMP stack running on a Debian distro that comes out of the box so conveniently pre-configured that you can access <a href="http://www.phpmyadmin.net/home_page/index.php">phpMyAdmin</a> on the VM from your host in about five minutes from the time you initiate the appliance download. It's really that easy. But I digress.<br /><br />
In my folly, I assumed an appliance would exist for a simple, clean installation of Ubuntu. What I found instead were dead links, shady sources that I didn't fully trust, and an appliance I tried to install that did run, but would hang on any login attempted. It took me a while before I realized, thanks to the tutorial linked above, that there was another way; that being the <span class="code">.iso</span> installation.<br /><br />
So I did that. Lo and behold, using the handy dandy tutorial, I had Linux running in a VM inside ten minutes. But it looked horrible. Absolutely horrible. The resolution was capped at 640x480, and all the window contents were so badly cut off that the GUI was literally unusable.<br /><br />
<blockquote style="text-align: center;">
This was the best I could get after my initial installation.<br /><br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYegPEjN0LqMNx00v-JyuW5zZmQ0KHteLqjLb9Hl1RYJanj9Dubb6hBZpu4kNZ98odOoW9b1VfwycBBXyssD6_J9EbRFdMZgdiwlBgZs_p00hdOC93_8dp3LskXn4xXIF_D7XrbWQF7tFm/s1600/ubuntu-vm-lowres.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" width="80%" caption="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYegPEjN0LqMNx00v-JyuW5zZmQ0KHteLqjLb9Hl1RYJanj9Dubb6hBZpu4kNZ98odOoW9b1VfwycBBXyssD6_J9EbRFdMZgdiwlBgZs_p00hdOC93_8dp3LskXn4xXIF_D7XrbWQF7tFm/s1600/ubuntu-vm-lowres.jpg" /></a>
</blockquote><br />
To make a long story just-a-little-less-long, an Ubuntu VM needs to have its device drivers and system applications installed <em>after the OS is installed into the VM</em>. This is done via the installation, in the case of VirtualBox, of the <a href="https://www.virtualbox.org/manual/ch04.html">VirtualBox Guest Additions</a>. But even armed with this knowledge, it's not easy figuring out how to get the blasted things into your VM.<br /><br />
I found some threads suggesting all kinds of terminal commands, <span class="code">sudo apt-get install blah-de-blah-de-blah</span>. It might be due to my version of Ubuntu or for other reasons (I never really figured it out), but none this of this worked for me. I got errors about missing dependencies; I tried to manually install these, only to find absent dependencies chaining together; several steps along that chain I came to a place where a vague message about <em>existing</em> packages preventing dependency installation prompted me to flip tables and head in search of another solution.<br /><br />
Turns out that the Guest Additions themselves are contained on yet another <span class="code">.iso</span>. I went through another minor crisis trying to source and install the appropriate <span class="code">.iso</span> file <em>all from within the still-ailing VM itself</em>, because that's where it needs to be installed. To my chagrin, it turns out the Guest Additions <span class="code">.iso</span> is already there once you get Ubuntu running in a VirtualBox VM. You just spool up your Ubuntu VM, then in the VM view window you visit the <em>Devices</em> menu and select <em>Insert Guest Additions CD image...</em>. Wow. Well. That was easy, eh?<br /><br />
Now, for the long-ago promised revelation of my ultimate goal in all of this. Earlier tonight I dropped a line on Facebook about how I could see it being easy to get lost when you have multiple VM and remote desktop views open on the same machine. A friend and I went back and forth about it until I joked about remoting into the host machine from its own guest VM. The glorious result took a couple of hours to achieve, but the laughs and learning were worth it.<br /><br />
<blockquote style="text-align: center;">
Ridiculous.<br /><br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9WIaN64Nt-uR8T1a54vRhvRS_tnptaZvV_I-X0hJzjneoBxmG-KUflngfRX6Cw3r1dVNEc7trSuM5IMaN8jiAVdryZ17gCscHfDI-2lfaKrg9sB9M2V4XZ9sSjUKhc1zTTLtyCbCwR7sD/s1600/remote-lulz.jpg" imageanchor="1" ><img border="0" width="80%" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9WIaN64Nt-uR8T1a54vRhvRS_tnptaZvV_I-X0hJzjneoBxmG-KUflngfRX6Cw3r1dVNEc7trSuM5IMaN8jiAVdryZ17gCscHfDI-2lfaKrg9sB9M2V4XZ9sSjUKhc1zTTLtyCbCwR7sD/s1600/remote-lulz.jpg" /></a>
</blockquote><br />
A night well spent.<br /><br />
Thanks for reading!!<br />
- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/14376004231145398163noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-75132661748033157082015-02-13T06:00:00.000-08:002015-03-26T15:24:52.601-07:00A Brief Study of the Independent Set Problem<h3>Prologue</h3>
<p>I normally prefer to share posts of a more practical nature, but in celebration of a hard-fought semester fraught with theory, research, and not a whole lot of actual development in the curriculum, I've decided to share some of what I learned even if it isn't directly applicable to the kind of day-to-day development most of us face on the job.</p>
<p>One of my most vicious classes last semester was combinatorial algorithms, a course focusing on algorithm design and analysis with particular attention to time complexity. Needless to say, computers and programming didn't factor into the curriculum at all. This was strictly a math class. Our big assignment for the semester was to pick an existing problem in the math domain, describe it in detail, and analyze a variety of the known approaches to solving it.</p>
<p>I chose the independent set family of problems, and the professor - considered one of the most brutal on campus - wrote me to congratulate me on a flawless paper. So I figured it must not have been too shabby, and I'll pass it on to the masses! Now, let's talk about independent sets!</p>
<h3>Introduction: What is an Independent Set?</h3>
<p>If you already know about graphs, and what an independent set is, you can skip ahead, but a little bit of background knowledge is needed to understand what an independent set is. Fair warning, it would be quite helpful to know a little bit about graphs, time complexity, and dynamic programming (or at least recursion). But I'll do my best to make this digestible with a minimum of prerequisite knowledge.</p>
<p>The very least you need to know is that a <em>graph</em> is made of <em>vertices</em> and <em>edges</em>, so that the edges connect the vertices together, like connect-the-dots. You can have a graph with any number of vertices, connected to each other in any number of ways by any number of edges. We call the group of vertices together a <em>set</em> of vertices, and the group of edges is also a set. Any group of items that belongs to a set (but might not include all of the items in that set) is called a <em>subset</em>.</p>
<p>So, if we have a graph, let's call it <em>G</em>, composed of vertex set <em>V</em> and edge set <em>E</em>, an independent set within that graph is a <em>subset</em> of the vertices in <em>G</em> where none of the vertices in the subset are connected by any edge. In other words, an independent set of vertices in a graph is a subset of the graph's vertices with no two vertices adjacent.</p>
<p>Two important types of independent set we will talk about below include the <a href="http://en.wikipedia.org/wiki/Independent_set_(graph_theory)"><em>maximal independent set</em> and the <em>maximum independent set</em></a> (they are sometimes, but not always, different from each other). We will also discuss what a graph’s <em>independence number</em> is. For the most part, we're only concerned with <em>maximum independent sets</em> and <em>independence numbers</em>, but I want to talk about maximal independent sets because that will help us to understand just what a <em>maximum</em> independent set is.</p>
<p>A <em>maximal independent set</em> in <em>G</em> is a type of independent set. In a maximal independent set, if you add <em>any</em> vertex from the total vertex set <em>V</em>, that wasn't already in the subset, that would force an adjacency into the subset. Remember, if we have two adjacent nodes in our graph, it's not independent. So a maximal independent set is a subset of the vertices in <em>G</em> that can't have any more of <em>G</em>'s vertices added without stopping the subset from being independent.</p>
<p>There are two things I find worth noting about maximal independent sets. First, a given graph might have any number of maximal independent sets. Second, each maximal independent set might have a different total cardinality (number of vertices in the subset). In other words, a single graph might contain multiple maximal independent sets, each of varying size. The largest possible one of these is called the <em>maximum independent set</em>. This is the largest independent set found in a given <em>G</em>.</p>
<p>Note also that a graph can have multiple maximum independent sets, but in this case, all of the maximum independent sets will have the same cardinality.</p>
<p>Finally, whether there is only one maximum independent set, or there are many, we refer to the cardinality of maximum independent sets as the <a href="http://en.wikipedia.org/wiki/Independent_set_(graph_theory)"><em>independence number</em></a> of the graph to which they belong.</p>
<p>We'll use these terms and concepts more below to discuss a variety of problems relating to independent sets, most importantly to my research, the <em>maximum independent set problem</em> and the <em>independent set decision problem</em></p>
<h3>Details: Problem Formulation and Motivation</h3>
<p>As we noted above, the maximum independent set problem takes a graph as input, <em>G</em> = (<em>V</em>, <em>E</em>). The goal is to find a subset of <em>V</em> comprising one maximum independent set on <em>G</em>, which might just be one of several maximum independent sets in <em>G</em>. The solution can then be used to obtain the answer to the independence number problem, which takes the same input (a graph) but seeks, instead of a maximum independent set, the <em>independence number</em> of the graph (the <em>number of vertices</em> in the maximum independent set). All we have to do to get the independence number once we have the maximum independent set is return the cardinality of the maximum independent set, and we're done. Along the same lines, the solution to the maximum independent set problem also comes packaged with the solution to the independent set decision problem, which is looking for a simple Boolean value: <em>true</em> if the graph’s independence number is greater than or equal to some given number, <em>k</em>, and <em>false</em> otherwise.</p>
<p>In other words, we can formally define the <em>independent set decision problem</em> as taking a graph, <em>G</em> = (<em>V</em>, <em>E</em>) and an integer <em>k</em>, and returning a Boolean value, <em>true</em> if <em>k</em> is less than or equal to <em>G</em>’s independence number, or <em>false</em> if <em>k</em> is greater than that independence number. In the simplest terms, we have a number, and we want to know if there is an independent set in some graph that is as big as our number.</p>
<table>
<tr>
<td class="theme"><strong>Input:</strong> a graph <em>G</em> = (<em>V</em>, <em>E</em>), and an integer <em>k</em></td>
<td class="spacer" />
<td class="theme"><strong>Output:</strong> a Boolean <em>true</em> or <em>false</em> value</td>
</tr>
</table>
<p>Believe it or not, these versions of the same problem – maximum independent set, independence number problem, and independent set decision – each has a specific real world application. The maximum independent set and independence number problems in particular have a wide variety of practical uses. The maximum independent set, for instance, is a problem that materializes in visual pattern recognition, molecular biology, and certain scheduling applications; and the independence number problem has applications in molecular stability prediction and network configuration optimization.</p>
<p>Astute readers will notice that I've omitted the very specific subject of the <em>independent set decision problem</em>, which (to refresh our memories) seeks only a Boolean value and no other data. This member of the independent set family of problems is not considered to have any practical "real world" application. That said, it plays a crucial role in the realm of theoretical research. It is considered <a href="http://en.wikipedia.org/wiki/Independent_set_(graph_theory)">necessary in order to apply the theory of NP-completeness to problems related to independent sets.</a> That's a topic for a whole other kind of blog post.</p>
<p>Though the topic of NP-Completeness can get pretty hairy, the dominating factor of the time complexity of solving the <em>decision</em> version of this problem is the same as for the independence number problem or the maximum independent set problem. As mentioned above, the decision version of the problem uses the same underlying algorithm as the independence number problem, and simply examines the resulting data to a different end. In short, to get the solution to the decision problem, we reduce the independence number solution to a Boolean value. The independence number problem itself is the same as the maximum independent set problem, with the output reduced to a single value representing the cardinality of a maximum independent set in <em>G</em>. But we're getting a bit beside the point here.</p>
<p>Since the domains of practical applications defer in large part to the maximum independent set and independence number versions of this problem, this is where the vast majority of interesting research on the topic of independent sets has been done. The complexity of the algorithms to solve <em>all three</em> problems is dominated <em>overwhelmingly</em> by the operations performed in the original maximum independent set problem. The transformations we have to make to produce solutions to the other versions of the problem are pretty trivial (counting cardinality, or comparing a given <em>k</em> value to the independence number to determine a Boolean value). For that reason, we'll focus on the research surrounding the maximum independent set problem.</p>
<h3>The Brute Force Approach – Slow but Simple</h3>
<p>Now let's talk about how we actually solve this problem. The brute force approach to the maximum independent set problem is very simple in principle. In short, <a href="http://stackoverflow.com/a/12452086/983173">all we need to do is iterate over all possible subsets in <em>G</em>, and then for each subset, check all vertices <em>v</em> in <em>V</em> for pair-wise adjacency</a>. The time complexity of checking each possible subset is O(2<sup><em>n</em></sup>), yielding an exponential time complexity, and the checking of all vertices yields an additional (relatively insignificant) polynomial factor to the complexity, <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">referred to in this case as poly(<em>n</em>), where <em>n</em> is, of course, the number of vertices in <em>G</em></a>. We consider the polynomial factor insignificant because the complexity of any polynomial factor will never dominate the exponential factor of O(2<sup><em>n</em></sup>), <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">and so becomes irrelevant for large graphs</a>.</p>
<p>In summary, for each vertex subset <em>S</em> in <em>V</em>, we check all vertices in <em>S</em> for adjacencies. If an adjacency exists, this subset can be thrown out because the adjacency violates the defintion of an independent set. As we iterate over subsets, we simply measure each and track which is the largest. For maximum independent set, we return the independent set that ends up providing the largest number of vertices over all iterations (this being the largest, read <em>maximum</em> independent set). This ends up taking a total of O(2<sup><em>n</em></sup>poly(<em>n</em>)) time. For the <em>independence number</em> problem, instead of returning the <em>largest independent set</em>, we return only the <em>cardinality</em> of the largest independent set, which we can trivially store while iterating over subsets. Finally, in the case of the <em>independent set decision problem</em>, we simply compare the independence number gained via the above brute force algorithm, trivially compare it against our given <em>k</em>, and return the appropriate Boolean value, <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">yielding a worst case that is still O(2<sup><em>n</em></sup>poly(<em>n</em>)) time</a>.</p>
<h3>Serious Business: Strategy and Analysis of an Improved Algorithm</h3>
<p>Before we get too excited, it's only fair to say right up front that we are not going to beat exponential time complexity with any known algorithm for solving this problem. That said, a fair amount of research has been done on it, yielding impressive improvements to the base of exponentiation. This, in turn has led to vastly improved run times in real world applications that rely on solutions to the independent set family of problems. (We're going to start getting very technical here.)</p>
<p>Following <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">Jeff Erickson’s guide to the optimization of the independence number algorithm</a>, we see that there are a series of steps that can be taken in turn to improve the performance of our algorithm. As a first step toward understanding the complicated means of optimization, Erickson provides a recursive formulation of an algorithm for obtaining the independence number on a graph, <em>G</em> (shown below). Next, he shows that the worst case scenario for that recursive algorithm can be split into subcases, some of which are redundant recursive calls that do not need to be performed in duplicity. Eliminating these duplicate cases, obviously, improves run time complexity. Finally, he shows that this improvement can be repeated on the resultant worst case, splitting that into further subcases, some of which are also redundant; and so on and so forth, continually improving the run time complexity in seemingly small, but ultimately meaningful, increments. To begin, observe Erickson’s most elementary version of the algorithm in its recursive form:</p>
<blockquote class="code">
MaximumIndSetSize(<em>G</em>):<br>
if <em>G</em> = { empty set }<br>
<span class="indent">return 0</span><br>
else<br>
<span class="indent"><em>v</em> = any node in <em>G</em></span><br>
<span class="indent"><em>withv</em> = 1 + MaximumIndSetSize( <em>G</em> \ <em>N</em>(<em>v</em>) )</span><br>
<span class="indent"><em>withoutv</em> = MaximumIndSetSize( <em>G</em> \ {<em>v</em>} )</span><br>
<span class="indent">return max { <em>withv</em>, <em>withoutv</em> }</span>
</blockquote>
<p>To clarify the notation here, <em>N</em>(<em>v</em>) refers to the <em>neighborhood</em> of <em>v</em>, meaning the set that includes <em>v</em> and all of its adjacent neighbors, but no other vertices. The backslash symbol refers to set-wise exclusion or "subtraction." For example:<br>
{ a, b, c } \ { b } yields { a, c }.</p>
<p>As you can see at a glance, the number of recursive calls at each iteration is doubled! This yields the same exponential growth of time complexity we saw in the brute force approach. What’s worse, we see that in the worst case, <em>G</em> \ <em>N</em>(<em>v</em>) = <em>G</em> \ {<em>v</em>}, meaning that <em>v</em> has no neighbors! This means that in both recursive calls at each iteration, our vertex subset is only being reduced by size 1. The result is the recurrence equation <em>T</em>(<em>n</em>) = 2<em>T</em>(<em>n</em> – 1) + poly(<em>n</em>), <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">yielding a time complexity of O(2<sup><em>n</em></sup>poly(<em>n</em>))</a>. <em>T</em>(<em>x</em>) here represents the time required to solve a problem of size <em>x</em>.</p>
<p>At this stage, though no clear improvement has yet been made, we already have the information we need to make our first improvement to the algorithm. As noted above, in the worst case, <em>G</em> \ <em>N</em>(<em>v</em>) = <em>G</em> \ {<em>v</em>}, meaning that <em>v</em> has no neighbors. However, if <em>v</em> has no neighbors, then it is <em>guaranteed</em> to be included in every maximal independent set, including maximum independent sets, because a node that never has neighbors is always independent! As a result, one of the recursive calls, the one assigning the value <em>withoutv</em>, becomes superfluous, because no maximum independent set can exclude <em>v</em> if it never has neighbors in any subset. At the same time (but on the other hand), if <em>v</em> does have at least one neighbor, then <em>G</em> \ <em>N</em>(<em>v</em>) will have <em>at most</em> (<em>n</em> – 2) vertices. That's quite a brain-full, so let me explain it another way, with concrete examples.</p>
<p>Let's say <em>G</em> has 10 nodes total. So <em>n</em> is 10. Then, if our random node <em>v</em> has at least 1 neighbor, then the <em>neighborhood</em> of <em>v</em> is size 2 or greater. Since <em>N</em>(<em>v</em>) is 2 or greater, then <em>G</em> \ <em>N</em>(<em>v</em>) is 10, minus some number 2 or greater. <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">This line of reasoning yields a new recursive formula with a dramatically improved run time complexity</a>:</p>
<blockquote class="code">
<em>T</em>(<em>n</em>) ≤ O(poly(<em>n</em>)) + max{<em>T</em>(<em>n</em> - 1), [<em>T</em>(<em>n</em> - 1) + <em>T</em>(<em>n</em> - 2)]}
</blockquote>
<p><a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">The run time complexity on this improved version of the recursive algorithm is reduced to <em>T</em>(<em>n</em>) ≤ O(1.61803398875<sup><em>n</em></sup>)</a> after just one subcase division! That might not seem like much of an improvement, but in a little bit we're going to see some concrete examples of just how big an improvement this can make at execution time. In the meantime, following this line of logic and making further observations, we can immediately improve on our new worst case by splitting that into subcases – some of which are, again, redundant and superfluous.</p>
<p>Note that our new worst case is the case in which both <span class="code"><em>T</em>(<em>n</em> – 1)</span> and <span class="code"><em>T</em>(<em>n</em> – 2)</span> must be calculated. In other words, this is the case in which our recursive calls are doubled, <em>and</em> in which the graphs we pass along are of relatively large size (only 1 or 2 vertices smaller than the graph from which they were derived). In this specific case, <em>v</em> has exactly 1 neighbor; let's call this neighbor <em>w</em>. Specifically because <em>v</em> has exactly 1 neighbor, we will find that either <em>v</em> or <em>w</em> will appear in every maximal independent subset of our original <em>G</em>. Think about it: if <em>w</em> is in a maximal independent set, <em>v</em> simply can't be, because they're neighbors, and two neighbors can't both be in the same independent set. Conversely, if <em>w</em> is <em>not</em> in a maximal independent set, <em>v</em> will be, because its only neighbor is not in the set, which frees <em>v</em> up to join without fear of standing by an adjacent neighbor. Taking this line of reasoning yet another step further, we see that given a maximal independent set containing <em>w</em>, we can remove <em>w</em> and instead include <em>v</em>. Therefore, we can conclude that <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">some maximal independent set will include vertex <em>v</em></a> (whether this <em>maximal</em> independent set ends up being <em>maximum</em> or not).</p>
<p>Note also that if we <em>know</em> there is a strict pair-wise relationship between <em>v</em> and <em>w</em> (due to the given fact that <em>v</em> has 1 adjacent neighbor), we <em>never have to evaluate</em> the recursive case in which the call MaximumIndSetSize(<em>G</em> \ {<em>v</em>}) needs to be made. Our case evaluating <em>T</em>(<em>n</em> – 1) + <em>T</em>(<em>n</em> – 2) becomes only <em>T</em>(<em>n</em> – 2). Furthermore, expanding on our idea from the last worst-case scenario subcase split, we will see that if the degree of <em>v</em> is 2 or more, then <em>N</em>(<em>v</em>) will contain at least 3 vertices, and therefore <em>G</em> \ <em>N</em>(<em>v</em>) will have at most (<em>n</em> – 3) vertices. In such a case, <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">the max{...} function of our recursive algorithm is expanded</a>:</p>
<blockquote class="code">
<em>T</em>(<em>n</em>) ≤ O(poly(<em>n</em>)) + max{<br>
<span class="indent"><em>T</em>(<em>n</em> - 1),</span><br>
<span class="indent"><em>T</em>(<em>n</em> - 2),</span><br>
<span class="indent"><em>T</em>(<em>n</em> - 1) + <em>T</em>(<em>n</em> - 3)</span><br>
}
</blockquote>
<p>This second improvement yields a time complexity of <em>T</em>(<em>n</em>) ≤ O(1.46557123188<sup><em>n</em></sup>), a smaller but still valuable improvement. On the other hand, note that the complexity of the algorithm is growing rapidly here. Not the time complexity, but the algorithmic complexity, as well as the difficulty we find in determining where to make future optimizations. At each step we take toward a faster algorithm, things are getting much more complicated. At this point, the complexity of the algorithm and the steps required to make further improvements go beyond the scope of what I can talk about in a blog post (even one as ridiculously long and complicated as this). However, <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">Erickson does go on to show that further clever observations can be made continuously, yielding even better time complexities</a>. Two further observations of worst-case splitting and problem structure yield time complexities <em>T</em>(<em>n</em>) ≤ O(1.44224957031<sup><em>n</em></sup>) and <em>T</em>(<em>n</em>) ≤ O(1.3802775691<sup><em>n</em></sup>), respectively. <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">According to Erickson</a>, the best published time complexities for this problem are solutions quoted by Fomin, who achieved <em>T</em>(<em>n</em>) ≤ O(1.2210<sup><em>n</em></sup>, and Bourgeois, who managed to achieve an impressive <em>T</em>(<em>n</em>) ≤ O(1.2125<sup><em>n</em></sup>).</p>
<p>Considering we're still ultimately stuck with exponential time, it may seem like a lot of work needs to be done for miniscule returns. After all, 1.221 and 1.2125 are almost the same number, right? On the other hand, certain practical applications demand <em>tremendous</em> effort, and therefore any ounce of efficiency that an improved algorithm can provide becomes valuable. Larson includes as an example in his writings <a href="http://independencenumber.files.wordpress.com/2012/07/inp-intro-120804.pdf">a reference to the prediction of molecular stability in the tetrahedral C100 isomer</a>. For this example, the time complexity <em>T</em>(<em>n</em>) of determining the independence number of this molecule is <em>T</em>(100). Therefore, working out the arithmetic, we see the run time for this example reduced as follows (ignoring poly(<em>n</em>):</p>
<table>
<tr>
<th class="theme center">Algorithm</td>
<th class="theme center">Time Complexity</td>
<th class="theme center">≈</td>
<th class="theme center">Run Time</td>
</tr>
<tr>
<td class="theme"><a href="http://stackoverflow.com/a/12452086/983173">Brute Force</a></td>
<td class="theme"><a href="http://stackoverflow.com/a/12452086/983173">O(2<sup>100</sup>)</a></td>
<td class="theme"><a href="http://stackoverflow.com/a/12452086/983173">≈</a></td>
<td class="theme"><a href="http://stackoverflow.com/a/12452086/983173">1.26765e30</a></td>
</tr>
<tr>
<td class="theme"><a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">Best method described by Erickson</a></td>
<td class="theme"><a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">O(1.3802775691<sup>100</sup>)</a></td>
<td class="theme"><a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">≈</a></td>
<td class="theme"><a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">9.923e13</a></td>
</tr>
<tr>
<td class="theme"><a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">Fomin et al</a></td>
<td class="theme"><a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">O(1.221<sup>100</sup>)</a></td>
<td class="theme"><a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">≈</a></td>
<td class="theme"><a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">4.69425e8</a></td>
</tr>
<tr>
<td class="theme"><a href="http://www.labri.fr/perso/robson/mis/techrep.ps">State-of-the-art described by Robson</a></td>
<td class="theme"><a href="http://www.labri.fr/perso/robson/mis/techrep.ps">O(1.1889<sup>100</sup>)</a></td>
<td class="theme"><a href="http://www.labri.fr/perso/robson/mis/techrep.ps">≈</a></td>
<td class="theme"><a href="http://www.labri.fr/perso/robson/mis/techrep.ps">3.26989e7</a></td>
</tr>
</table>
<p>With these concrete numbers to reference, we can see clearly that the jump from the brute force method to even a slightly optimized solution is more than worth the effort. The first jump alone results in an improvement to run time of many orders of magnitude! After that, we admittedly begin to see diminishing returns for the effort taken to develop improved algorithms. For instance, I personally doubt that the extra effort by Bourgeois to beat Fomin by a mere 0.0085 on the exponentiation base was of debatable value as anything more than a stepping stone. In my personal opinion, the return on invested effort put in to develop Robson’s final state-of-the-art solution (discussed below) was not worth it for such a small gain from Fomin's algorithm. At least, not in the case of the C100 stability prediction problem. That said, <em>100</em> may be considered a small quantity of vertices in some problem domains, such as large network configuration optimization or scheduling problems. In those cases, it may actually be worth it to go to the trouble of researching and developing the absolute best state-of-the-art in terms of fast, efficient algorithms.</p>
<h3>Robson's Incredible State of the Art, Conclusions</h3>
<p>Research has yielded relatively fast algorithms for solving the independent set family of problems. Some, notably by Bourgeois, are <a href="http://arxiv.org/pdf/0901.1563v1.pdf">capable of a time complexity as low as a flabbergasting <em>T</em>(<em>n</em>) ≤ O(1.0854<sup><em>n</em></sup>) time complexity</a> using strategies of case analysis and reduction rules. However, it's worth noting that algorithms that are as fast as these come with severe limitations. For example, the Bourgeois algorithm is <a href="http://arxiv.org/pdf/0901.1563v1.pdf">limited to graphs with average vertex degree 3</a>. That is a serious limitation! The fastest published algorithm for solving the independent set family of problems for <em>generic</em> graphs (with unbounded number of degrees), by Bourgeois, <a href="http://arxiv.org/pdf/0901.1563v1.pdf">runs in only <em>T</em>(<em>n</em>) ≤ O(1.2125<sup><em>n</em></sup>)</a>.</p>
<p>The absolute state of the art for solving the independent set family of problems is actually a <em>computer-generated algorithm</em>. The algorithm is <a href="http://www.labri.fr/perso/robson/mis/techrep.ps">described in an unpublished technical report by Robson</a>, and is <a href="http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf">claimed to boast a time complexity of only O(1.1889<sup><em>n</em></sup>)</a>. However, the trade-off at this level of acceleration is mind-boggling algorithmic complexity. Just the high level <em>description</em> of the algorithm, excluding the rest of the accompanying report, fills fully <em>15 pages</em>, and thus excludes discussion of the algorithm in any depth from the scope of most academic papers, let along blogs. I'm not an expect on algorithmic analysis at quite that level, but I'd wager such an algorithm would even be excluded from use in applications at that point, due to its sheer complexity.</p>
<p>As algorithms grow in efficiency, but also in complexity, it gets tough to make universal recommendations on which to use – or, in the case of the algorithms described above, how deep through the iterations of optimization a project team should go to try and improve the performance of their algorithm. The context of the project would have to come into factor.</p>
<p>For projects dealing with small graphs, it wouldn't be worth the effort to interpret and implement something like Robson's solution. Something like the example described by Erickson and outlined above would probably be good enough. For projects dealing with graphs of moderate size and predictably small average vertex degrees throughout, but needing accelerated solutions, something like the algorithm developed by Bourgeois would provide a superior middle ground.</p>
<p>Thanks for reading!<br>- Steven Kitzes</p>Steven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-9590358139702013992014-02-22T02:27:00.001-08:002016-07-30T23:32:15.493-07:00Theory, Practice, and BalanceWhen I landed my first software gig almost four years ago, I was a self-taught programmer. Not to say that I didn't have help along the way; I had loads of tutoring and mentoring from friends. Point being, it was my own motivation that kept me going, and my own intuition that determined the direction my learning process would take. I had no formal training, schooling or guidance to keep me on track or ensure that I'd learn any particular skill set or theory in any kind of organized way.<br><br>
Especially in the beginning, before I was ever employed as a developer, my goal was to get to a point where my learning could become a self-sufficient process. For example, an early task I assigned myself was to learn enough about a programming language to get "hello, world" on the screen so I'd have <i>something</i> to build on from there. I explored IDEs and debuggers so I could figure out what was breaking in my rudimentary programs. I dove into docs, grabbed third party libraries to help, and set up RTEs. I don't think many in the community would argue that these aren't useful skills, if not important, maybe even <i>essential</i> skills. But essential or not with respect to any kind of career path, I was learning them haphazardly based on <i>immediate</i> need.<br><br>
By the time I started at my first job, I had made it to the point where I could jump onto a project and start delivering serviceable work within a few days, but my code wasn't what you might call <i>optimal</i>. It became quickly evident that there were a lot of gaps in my knowledge, skills, and experience that were holding me back. I understood, more or less, how to solve simple problems with code, how to compile and debug; I even stuck to some common best practices in program design from what I had picked up along the way. But I sure didn't know anything about math, theory, or architecture. Set theory, data structures, state machines, binary trees, Boolean algebra, recursion; even stats, calc, the supposedly basic stuff, linear algebra; let alone dynamic programming, approximation, or any of the other heavy theory you'll stagger through in upper division computer science coursework. At the time, I just <i>knew how to code</i>, even if the code came out slightly more organized than a trash can filled with spaghetti, and hey - for that first job, it was enough.<br><br>
I know from experience that this is a common attitude for some self-taught programmers. <i>"Hey, it compiles, and it works for most cases, what do you want?"</i> Well, depending who you want to work for and what you want to do with your life, there's plenty there to want, especially as the low-hanging fruit of the software development world is phased out of the career curriculum almost entirely in place of more challenging architectural and mathematically challenging problems.<br><br>
Now that I'm in the thick of an academic Computer Science program to fill some of the early gaps in my knowledge, I'm inundated in the polar opposite of a practicality-focused paradigm. This semester, for example, I'm taking classes in discrete math, formal proofs, and logic; set and language theory and automata; and operating system theory. So far, over a month into the semester, not a single line of code has been requested <i>or</i> demonstrated by any of my professors. In all honesty, hyperbole and exaggeration aside, a computer has not even been mentioned in the classroom. Where is the code? The practice? The application? Over a year into the curriculum and no one has so much as mentioned a debugger, spoken a word on environments, given a nod to APIs or anything of the sort. They are completely ignoring the fact that one day, presumably, we'll need to <i>actually apply</i> all this math and theory <i>to</i> something. They are training us all to be mathematicians and PhD candidates.<br><br>
Both of the above situations - the plight of the inexperienced CompSci grad, and the crude hacking style of the common self-taught developer - probably sound familiar to anyone who has spent significant time on the job as a professional developer. Even with my limited experience and time in the field, I've met both. Employers have complaints about these two types of entry level job candidates, and I think they are valid points to make. No one wants to hire a kid who can <i>technically</i> write a program, but can't for the life of him <i>do a good job</i> of it because he has never considered testing, or any kind of process, or software engineering principles, or the fact that someone - maybe even him- or herself - is going to have to maintain that code one day. On the other hand, it's rarely a good idea to hire a math whiz with a CompSci degree who has, ironically, no clue how to open Excel, let alone IDEs. I have had professors who prototype in notepad.exe and teach three-generation-old UI libraries because it's what they know best and they're too lazy to keep up on the tech and it's too easy to give the excuse that <i>hey, sometimes you have to maintain legacy code</i>. True as that may be, and though it may be a separate issue, it's part of the larger problem. At any rate, what does it tell you about the practical skills of the resultant graduates?<br><br>
I hear complaints from employers that CompSci grads too often come out of school knowing such-and-such theorem and So-and-So's Law but with no idea how to use any of it in the workplace; and that self-taught programmers with drive to succeed have taught themselves how to compile and debug but haven't the slightest clue how to improve their algorithms - or, heaven forbid, toss in a comment here and there. So, what do we do about it?<br><br>
I understand that opinions are a dime a dozen and my commentary is a drop in the bucket of sentiment on this topic, but I have lately felt the need to share it anyway, because these issues have impacted me both as a member of the workforce, and as a self- and university-taught developer. It seems, frankly, outrageous that more effort isn't being put into a combined emphasis on real-world application and theory. Students have to be given some kind of bigger picture with hands-on experience, so that they can connect the theory to the application. A few schools do seem to be getting it; I have one friend who graduated from a technical college with boatloads of practical experience, in addition to a detailed understanding of the math and theory on which best practices and problem solving are founded. But this guy is a painfully rare exception. I, for example, would never have learned how to set up my machine and get myself jump-started on a project without my own extracurricular work, industry experience, and attention from concerned personal contacts. Not to say that students shouldn't be doing any extracurricular work, but leaving the critical element of hands-on experience out of the schooling process by policy is counterproductive to the ultimate goal of schooling: which is preparing students for the real world.<br><br>
As for the self-taught developer and self-driven learner, the onus is on the community to give a sense of importance to the concepts underlying best practices and solutions to complex computing problems. When someone green behind the ears comes onto a forum to ask a question, instead of dismissing it as stupid, or shunning them with a condescending LMGTFY GTFO, or telling them to just do their project in an easier language, it is up to those with more experience to guide them to better solutions and opportunities for self-education. Otherwise, who do we have to blame when our co-workers are writing hacked up code that we have to fix for them?<br><br>
Thanks for reading!<br>
- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-24672438922663451792014-01-05T23:29:00.001-08:002015-01-25T15:33:59.801-08:00Android SDK Setup Pitfalls in Windows 7 without EclipseI'm delving into Android development for the first time and ran into some trouble during the SDK setup on my <b>Windows 7</b> machines. I wanted to use <b>an IDE other than Eclipse</b>, which complicated things somewhat. For example, if you're not using the Eclipse-ADT (Android Development Tools) bundle, you'll be keeping a lot more cozy with the command line. But I followed the provided platform-specific documentation as closely as possible and still ran into snags that cost me a lot of time. Hopefully by piecing together a write-up of my experience I can cement the process in my mind and consolidate some of this information to save others time during their setup.<br><br>
<h3>Resources, Downloads, Installation</h3><br>
First, if you are new to Android development, I recommend visiting and bookmarking <a href="http://developer.android.com/training/index.html">the Android developer home page</a>. From there you can (sorta) easily navigate to all the resources and information you need to get started. If the installation of the SDK goes smoothly (which I hope to help facilitate with this post), you can follow their tutorial and probably get a "hello, world" Android app up and running inside an hour.<br><br>
Start by installing the Android SDK (not the Eclipse-ADT bundle). Following the documentation for the SDK installer and resource download went smoothly for me. The only thing to mention is that there is some finagling you have to do to get all the licenses accepted in the SDK Manager if you want any of the options that aren't specified in the documentation (there are multiple methods of accepting certain licenses for some reason).<br><br>
<h3>Using a Batch Supportive CLI</h3><br>
One thing they won't tell you in the docs that they should, is that the command line input they give you includes some batch file execution. When I was going through this process, I was using Git Bash. This was causing me all kinds of problems because the syntax you use to execute batch files in Git Bash or other third party shells is different from that you'd use at the Windows 7 command line. I kept getting <i>android: command not found</i> and I didn't understand why, because I had correctly added all my directories to the Windows PATH variable and everything. Even once I'd figured out that these were batch files and needed different syntax to be run, it took me a while to realize that the reason the execution was failing wasn't just because my syntax was wrong, but because the Git Bash just doesn't fully support batch file execution.<br><br>
<b>In short,</b> the Android documentation assumes you're using a CLI that provides full support of Windows batch file execution.<br><br>
<h3>Setting Up an Android Virtual Device and Emulation</h3><br>
Skip this if you only plan to test on physical Android devices. I wanted to test virtually so I had to set up the emulator.
For the emulator to run on Windows 7, you can't give your virtual Android device too much memory or the emulator will crash. I was getting errors from emulator_arm.exe when trying to run my virtual Nexus 7. Reducing the allocated memory on the virtual device from 1024 to 512 allowed me to run the emulator with no trouble (though I'm not confident this provides a realistic testing environment down the road).<br><br>
Also note that when loading the emulator, the virtual device's boot time may be quite long. I have a reasonably quick laptop with SSD, 8GB RAM, yadda yadda yadda, and it still took a couple of minutes to boot the emulator. Be patient, don't panic.<br><br>
<h3>Windows Environment Variables, Including JAVA_HOME</h3><br>
Throughout this process, you may well find yourself working with Windows environment variables, including the PATH variable, at length. Be careful, you can do some pretty annoying damage to your system if you are careless in there. Follow directions carefully and correctly to make sure everything will work and you don't lose any important system information that may already have been added to any Windows environment variables.<br><br>
This is a preemptive note for the next section, but important nonetheless. There is a command line application you'll need by Apache called Ant. It's a command line build tool for Java projects. When installing Ant, make sure you add <i>that</i> to your Windows PATH variable. Otherwise, when you try to run Ant you'll just get the classic <i>'ant' is not recognized as a an internal or external command</i> error. Next, you need to make sure a Windows environment variable called <span class="code">JAVA_HOME</span> is correctly pointing to the location of the JDK (Java Development Kit) on your system, because Ant uses the JDK. If the JAVA_HOME variable doesn't exist, just create it (I had to).<br><br>
<h3>Installing an App onto an Android Device</h3><br>
At long last, I had the SDK all set up and I'd gotten the sample "hello, world" app built. To install an app onto a device (virtual or physical) for testing, the documentation first tells you to navigate to your project root directory and enter <span class="code">ant debug</span> at the command line. They don't tell you what this does, why it's important, or most critically, that <i>Apache Ant</i> (which you can <a href="http://ant.apache.org/">download and learn more about here</a>), may not even be installed on your system, and is essential to the tutorial in the documentation. Now you know.<br><br>
<h3>Finally</h3><br>
Now I'm running Android apps in emulation. My next step is to try running the "hello, world" app on a physical device, then I'm off to the races. Hope you found something here to help you along the way on your Android journey! And as always...<br><br>
Thanks for reading!<br>
- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-22283467310060776932013-09-26T03:11:00.001-07:002014-01-04T03:03:35.865-08:00The Story of My First Significant Java Project - Path Finding Using Frameworks and Data StructuresLast month I went back to school, and now I'm officially on the books as a CompSci Master's student. This week, I tackled my first big assignment, and it was a bit of a doozy.<br><br>
By way of context, I'm coming into this Master's program with some real-world work experience. I previously worked at a video game company, and have also made a few small PC games of my own (most notably a couple of 2D "bullet hell" shooters, for which I developed my own modest game designs, physics engines and AI routines). As such, I already have some of what is being taught in this curriculum in my repertoire. But the assignment I'm writing about today comes from an accelerated hybrid course on data structures, path finding, database administration and integration of custom frameworks. It is one of several courses that are famous within the program as having been added to the curriculum explicitly for the purpose of weeding out the poor kids who aren't cut out to be developers.<br><br>
The assignment itself required us to write a program that satisfied the following requirements:
<ul>
<li>generate a navigation mesh based on topographical map and geological/natural resource data provided in a text file</li>
<li>read in mouse clicks to define starting and destination waypoints on the map</li>
<li>include a "robot" (rudimentary AI) with limited traversal capabilities (stamina, resources, strength for handling inclines in 3-space, etc) that will try to find a path from start to destination</li>
<li>utilize (and modify if necessary) a custom graphics and time (framerate) management framework provided by the professor and written in Java to display everything in a window</li>
</ul><br>
So, there was a lot to do, and a lot to learn along the way. Just as one example, my work experience has revolved mostly around UI engineering, and though I'd created rudimentary AI algorithms for my bullet hell games, this was my first time working with anything like nav meshes and pathfinding. This was also my first time using Java. I've made a few dumpy practice programs to learn some of the basics, but on day one, even something as simple as reading and parsing a text file, or working with an array was a non-trivial task. And of course, because I had to balance this with my work from other classes and didn't want to neglect my non-academic projects, I ended up with only three days to do <i>everything</i>.<br><br>
At the time of this writing, I'm <b>not</b> actually done with the project (hah!). But it isn't due for another week and a half, and the remainder of the work is housekeeping (hiding <span class="code">print</span> calls behind <span class="code">DEBUG</span> flags and cleaning up documentation, for example). In any case, I'm happy with what I've produced, and I'd love to talk about everything I learned along the way. But there too much of it, so I'll fixate on my proudest achievement, the "simple path" pathfinding algorithm that I used in this iteration of the project, which will serve as a stepping stone to more complex iterations that will end up using the A* algorithm, remote database interactivity, and multiple simultaneous AI "players"!<br><br>
In class, we have already learned about <a href="http://stackoverflow.com/questions/1332466/how-does-dijkstras-algorithm-and-a-star-compare">Dykstra's algorithm and the A* algorithm</a> for path finding. These are both very good (much better, anyway) algorithms for path finding than the "simple path" algorithm I came up with. However, given the limited time to complete this task and the requirements set forth by the professor (he actually demanded a "simple path" solution for the first assignment as a stepping stone), I'm very happy with how quickly I generated a solution.<br><br>
Simply put, I begin with a <span class="code">while</span> loop. This loop will iterate until the robot runs out of stamina, the goal has been reached, or the robot has worked itself into a corner (backtracking is not allowed). Inside the loop, I first establish the current location of the robot (the nav mesh node it currently sits on). Then, I build an adjacency list for that node; in other words, a list of every node that the robot can navigate to from the current node. (A candidate node will only be added to the adjacency list if all of the conditions for travel between it and the current node are met; the candidate must not have been visited already, it must be close enough in 3D space (not too much of a slope), the robot must have enough stamina left to reach the candidate node, and there must actually be a node there.)<br><br>
At this point, I can already kill the program if the adjacency list size is zero; if the bot has no means to reach any node adjacent to its current node, it is trapped and the traversal is a failure. However, if there is at least one candidate node available for travel, I compare the distance between the goal and each candidate node in the adjacency list. I choose the navigable candidate that is closest to the goal, and move the bot there (adjusting its stamina values along the way, based on terrain difficulty and discovered resources).<br><br>
After each movement of the robot, I check if it has reached the goal. If so, that's a successful traversal! If not, I check if the robot's stamina has been exhausted. If so, that's a failed traversal, and if not, I can continue with another iteration of the <span class="code">while</span> loop until and exit condition is met. <br><br>
Not too shabby!<br><br>
I would have loved to post some of my code, but due to my professor's concerns regarding plagiarism (which I find to be valid) I will have to refrain for now. But, as always...<br><br>
Thanks for reading!<br>
- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com5tag:blogger.com,1999:blog-4160731462668027711.post-75102396414978114612013-09-03T11:31:00.002-07:002014-01-05T19:19:41.126-08:00Understanding Java from a C++ Background<center><h4>A short note of thanks before I begin. Some friends showed me a lot of shortcomings in the way I was thinking about this problem. That led to a huge, sweeping revision of this article. Hopefully it is more correct, coherrent and usable now.</h4></center><br><br>
I was born and raised in a world of C++, which treats class objects and primitives the same way. You can pass any variable around between functions either by value, or by reference. My dependency on this paradigm never became more apparent to me than when I finally made the switch to another language: Java.<br><br>
<h1>C++</h1>
In C++, you can instantiate a class object, let's call it <span class="code">MrObject</span>. You can then also create a pointer to it. Let's call that <span class="code">MrPointer</span>. If you then decide you want access to <span class="code">MrObject</span>'s data in another function, there are a lot of ways you can do this. You can:<br>
<blockquote><b>Pass a <i>reference</i></b> to <span class="code">MrObject</span> into the function using the '<span class="code">&</span>' operator, giving you direct access to the original instance of <span class="code">MrObject</span> himself.<br><br>
<span class="code">void MrFunction(MrObjectClass &MrObjectRef) {...}</span><br><br>
Within <span class="code">MrFunction</span>, you can use <span class="code">MrObjectRef</span> just the same as if it were <span class="code">MrObject</span> himself, because this is literally just creating another alias for the <i>same exact object in memory</i>.</blockquote>
You can also:<br>
<blockquote><b>Pass by <i>value</i></b>, creating a new instance of a <span class="code">MrObjectClass</span> inside <span class="code">MrFunction</span> that is a duplicate of <span class="code">MrObject</span>.<br><br>
<span class="code">void MrFunction(MrObjectClass MrObjectDupe) {...}</span><br><br>
When you pass <span class="code">MrObject</span> into this function by value like this, a new class object called <span class="code">MrObjectDupe</span> is created within the function. The original <span class="code">MrObject</span> stays where he is, and is isolated from anything that is going on within <span class="code">MrFunction</span>.</blockquote>
Things get a little more tricky when you create pointers to <span class="code">MrObject</span> and try passing those into functions. For example, let's say you make a pointer to <span class="code">MrObject</span>, like so:<br>
<blockquote><span class="code">MrObjectClass * MrPointer = &MrObject;</span><br><br>
If you're not fluent in C++, what we are doing here is <b>not</b> creating a new <span class="code">MrObject</span>. The asterisk (<span class="code">*</span>) tells us that we are creating a <i>pointer to an object of type</i> <span class="code">MrObjectClass</span>. The name of the pointer is <span class="code">MrPointer</span>. The assignment here (<span class="code">=</span>), combined with the ampersand (<span class="code">&</span>), tells us that the specific object in memory that <span class="code">MrPointer</span> points to is the one named <span class="code">MrObject</span> (which must be declared elsewhere, but <i>can</i>, if you wanna be fancy, be defined through <span class="code">MrPointer</span> via the <span class="code">new</span> keyword, for example).</blockquote>
<i>Now</i>, if you want to pass <span class="code">MrPointer</span> into a function, C++ also allows you to pass <i>that</i> either by value, or by reference. In other words, you can:<br>
<blockquote><b>Pass a pointer by value</b>; create a <i>new</i> pointer with the same <i>value</i> as the pointer you passed into the function. In other words, <i>a new pointer</i>, but one that points to the same address as the pointer that was passed into the function.<br><br>
<span class="code">void MrFunction(MrObjectClass * MrPointerDupe) {...}</span><br><br>
The asterisk must still be included so that C++ knows <span class="code">MrPointerDupe</span> <i>is</i> a pointer. The side effect of this is that we can access <span class="code">MrObject</span> through this duplicated pointer, but if we point <span class="code">MrPointerDupe</span> at a new address (to a different object of <span class="code">MrObjectClass</span>, or a new one, or to null), then the original <span class="code">MrPointer</span> will remain unaffected, still pointing at (and modifying, if dereferenced) our original <span class="code">MrObject</span>.</blockquote>
Alternatively, you can:<br>
<blockquote><b>Pass a pointer by <i>reference</i></b>; in other words, we are not creating a new pointer to <span class="code">MrObject</span>, we are using the same original <span class="code">MrPointer</span>; we are just creating a new <i>alias</i> for <span class="code">MrPointer</span> to be used within <span class="code">MrFunction</span>.<br><br>
<span class="code">void MrFunction(MrObjectClass * &MrPointerAlias) {...}</span><br><br>
The asterisk in this case tells us that we are declaring a <i>pointer</i> to an object of type <span class="code">MrObjectClass</span>, and the ampersand tells us that the pointer we are creating is not a new pointer, but just an <i>alias</i> (another name) for the existing pointer that is getting passed in to <span class="code">MrFunction</span>.</blockquote>
<h1>Java</h1>
The nature of Java variables may not seem clear at first, coming from a C or C++ background. In Java, <b>every variable you declare is a reference</b> (except for primitives like <span class="code">int</span> or <span class="code">boolean</span>). Even primitive types such as <span class="code">int</span> have Java class equivalents that give you reference type variables for handling primitive types (such as Java's <span class="code">Integer</span> class).<br><br>
Why is this so important? Just taking one important example, in C++, you might be used to creating a new instance of a class object, then being able to copy it into another second class object, like so:<br>
<blockquote>
// C++ code to create a new instance of MrObjectClass called MrObject.<br>
<span class="code">MrObjectClass MrObject();</span><br><br>
// C++ code to create a second, separate instance of MrObjectClass called<br>
// MrDuplicate, by copying MrObject. Note that this results in two<br>
// distinct class objects in memory.<br>
<span class="code">MrObjectClass MrDuplicate = MrObject;</span>
</blockquote>
By contrast, in Java, when you instantiate a class object like so:<br>
<blockquote><span class="code">MrObjectClass MrObject = new MrObjectClass();</span></blockquote>
you are <b>not</b> creating a <i>class object called <span class="code">MrObject</span></i>. You are implicitly creating a <i>reference</i> to an object of type <span class="code">MrObjectClass</span>, and that <i>reference is called</i> <span class="code">MrObject</span>. In the following Java snippet, the two declarations result in only one distinct class object instance, which has two reference variables referring or "pointing" to it. (Though these variables are not pointers, I found it useful to think about them as such in the beginning, as a sort of "training wheels" approach to getting going in Java. However, of course you should try to build an understanding of Java's implicit referential nature as early as possible.)<br>
<blockquote>
// Java instantiation of a reference called MrObject to a nameless object<br>
// of type MrObjectClass<br>
<span class="code">MrObjectClass MrObject = new MrObjectClass();</span><br><br>
// Java instantiation of a second reference called MrDuplicate, which<br>
// actually refers or "points to" the same nameless object as MrObject<br>
// refers to, resulting in only a single nameless MrObjectClass object<br>
<span class="code">MrObjectClass MrDuplicate = MrObject;</span>
</blockquote>
It's very important to understand this so that you will understand what happens the first time you attempt to duplicate a class object, then modify your new variable only to see the changes reflected in your first variable as well! In other words, in Java, you <i>cannot</i> create a <span class="code">MrObject</span> that you have "direct" C-style access to. Also, perhaps most importantly, it's critical to remember that reassigning <span class="code">MrObject</span> or <span class="code">MrDuplicate</span> <i>does not overwrite</i> any data! <span class="code">MrObject</span> and <span class="code">MrDuplicate</span> are references, and reassigning them simply points them to new memory locations. This can, in turn, potentially leave data unreferenced, in which case Java automatically cleans it up (but this unpredictable, sometimes seemingly sporadic process, often called <b>garbage collection</b> is another topic for another day).<br><br>
Another reason this concept is so important to grasp early on in a programmer's exposure to Java, is because Java does not support pass-by-reference! In other words, even if you get used to the fact that everything in Java is a reference, you then have to accept that <b>all functions in Java are pass-by-value</b>! In other words, if I pass my <span class="code">MrObject</span> reference from the example above into a function, the result is that <i>within</i> that function I <i>cannot</i> directly manipulate the original <span class="code">MrObject</span>, ever!<br><br>
What's happening within the function is we are creating a new reference variable whose value (referred or "pointed" address) is the same as <span class="code">MrObject's</span>, because that is what's passed <i>by value</i>. Using the new reference inside the function, we can access our referred, nameless class object's public members. <i>But</i> if I try to reassign my reference variable from within my function, <i>only the duplicated reference variable within the function</i> will refer to the new destination address (nameless class object instance) I designate (including, possibly, <span class="code">null</span>); the original <span class="code">MrObject</span> reference outside the function will still point to (and protect from garbage collection) the <i>original</i> address (nameless class object) it originally referred to in the first place.<br><br>
Are there ways to simulate pass-by-reference for those instances where you really want that behavior? Sort of (storing reference variables in an array or container class and passing the array or container itself into functions by value to preserve the original pointer-like variables <i>within</i> is the closest I can come up with so far, though these can feel like clumsy substitutes for true pass-by-reference). But when possible, it's better to just be aware of Java's idiosyncrasies and think in a <i>Java</i>-like way; its lack of pass-by-reference, and its requirement that all non-primitive class object variables are references; and to design around these features to the extent possible.<br><br>
Thanks for reading!<br>
-- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-55511686201846972792013-07-15T05:00:00.000-07:002014-01-05T21:50:26.807-08:00'const' vs 'final' - A Discussion(For the tl;dr, <a href="#tldr">click here</a>.)<br><br>
My latest forays into the realm of software development have taken me into <a href="http://en.wikipedia.org/wiki/Java_(programming_language)">Java</a> country. I'm going to be taking my first classes toward my Master's in Computer Science in the coming months, and the bulk of the courses taught at my university are in Java. It will be my first time working with Java, so I thought it'd be a good idea to test the waters and get up to speed.<br><br>
When I started writing my first entry level Java programs, one of the first features I instinctively tried to carry over from my C++ background was the <span class="code">const</span> concept. After some research, I discovered that <b>there is no <span class="code">const</span> keyword in Java</b>. Or, more accurately, <span class="code">const</span> is a <i>reserved</i> word, that Java prohibits you from using in your code. It has no function in Java, but you may not use it as a variable or function name, either.<br><br>
Instead, <b>Java has a keyword called <span class="code">final</span></b>, which seems on the surface to have a similar function to C++'s <span class="code">const</span>. I wondered what the difference was between the two, and why Java's creators decided to block the <span class="code">const</span> keyword from their language, I went on a quest to find out!<br><br>
I came across a variety of myths along my search that I quickly busted via simple testing. For example, some folks believe that Java's <span class="code">final</span> keyword can't be applied to primitive data types such as <span class="code">int</span>, <span class="code">double</span>, or <span class="code">char</span>; but it can. Others believe that <span class="code">const</span> C++ references are special, in that while they are immutable, the data they point to is mutable; however, this is also the case with a Java <span class="code">final</span>.<br><br>
<blockquote>
As a side note, I found some information indicating that you do have the option in C++ of differentiating between a <b>constant pointer</b> to data, a pointer <b>to constant data</b>, and a pointer that is declared as constant to <b>protect</b> the otherwise non-constant data that can be dereferenced through it. If that sounds a bit confusing, it's much easier to understand when you see the code:<br><br>
<script src="https://gist.github.com/StevenKitzes/5992672.js"></script><br>
Cases 1 and 3 are simple enough, as far as syntax, though case 3 may be a little more confusing because of <i>how</i> we are protecting our data. Case 2, on the other hand, is a bit more confusing in terms of syntax; the <span class="code">const</span> keyword appears <i>after</i> the pointer operator, even though the pointer itself is where we are applying the <span class="code">const</span> functionality.<br><br>
It would make more sense to me if the <span class="code">const</span> keyword immediately preceded the item that it modified, in this case, the pointer operator. But sometimes you just have to accept that things are the way they are, and forge ahead!
</blockquote><br>
<a id="tldr"></a>So what <i>is</i> the difference between <span class="code">const</span> and <span class="code">final</span>? It turns out the <b>primary difference is in initialization</b>. <b>In C++, a <span class="code">const</span> must be defined in the same statement in which it is declared</b>. In other words, you can't declare a C++ <span class="code">const</span> and define it later in a separate statement.<br><br>
<script src="https://gist.github.com/StevenKitzes/6000900.js"></script><br>
On the other hand, <b>a <span class="code">final</span> in Java <i>can</i> be initialized in the same statement that it is declared; but you can also choose to declare it and then define it later in the program</b>. This allows for each instance of a <span class="code">final</span> to be defined by one of a variety of values (as you can see in the below example), but still ensures that once it is defined, it is constant forevermore.<br><br>
<script src="https://gist.github.com/StevenKitzes/6000912.js"></script><br>
As you can see in the above example, depending on whether 'someBool' is true, <span class="code">x</span> might end up being defined as 10 <i>or</i> 20, but once it is set to one or the other, it can never be changed from there on out because it is <b>final</b>. Another important thing to note: when you are using a Java <span class="code">final</span> without defining and declaring it in the same statement, you must be careful to define it before it is used, or you <i>will</i> have an error.<br><br>
Hopefully this will help clear up some of the idiosyncrasies of and differences between C++'s <span class="code">const</span> and Java's <span class="code">final</span>!<br><br>
Thanks for reading!<br>
-- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-79726969273019897152013-07-08T07:00:00.000-07:002014-01-05T19:36:23.209-08:00Updating Environment Variables in WindowsThis weekend I installed the <a href="http://www.oracle.com/technetwork/java/javase/downloads/java-se-jre-7-download-432155.html">Java Runtime Environment</a> and the <a href="http://www.oracle.com/technetwork/java/javase/downloads/jdk7-downloads-1880260.html">Java Development Kit</a> onto my desktop and my laptop, both running identical Windows 7 environments. The installation onto the desktop went without a hitch. I ran both the JRE and JDK installers, got the <a href="http://www.jetbrains.com/idea/">JetBrains IntelliJ IDEA</a> Java IDE up and running, and tried executing my first Java 'Hello World' program from the console. Shockingly, this worked on the very first try with no errors, and from the <a href="http://git-scm.com/downloads">Git Bash</a>, no less! This was such a pleasant surprise and <i>unexpected result</i> that it even prompted me to rename my dev blog to 'Unexpected Result'!<br><br>
But for whatever reason, after going through all the same steps on my laptop, I couldn't seem to get Java to run from Git Bash. Upon checking my environment variable (typing <span class="code">env | grep PATH</span> in Git Bash), I discovered that the JDK directory somehow didn't seem to have been added!<br><br>
It turns out the solution was a simple matter of closing the Git Bash and reopening it! When a PATH variable change is registered, that change <i>won't be visible to any running instances</i> of Git Bash. It seems that Git Bash reads the PATH variable from Windows one time only, when the CLI is launched, and doesn't refresh it until the CLI is closed and launched again. This is true of other command line interfaces in Windows, as well (such as the Windows command prompt).<br><br>
So if you've just added something new to a Windows environment variable, and it doesn't seem to be working from your CLI, make sure you have restarted your CLI after the environment variable was modified and it should be smooth sailing from there!<br><br>
Thanks for reading!<br>
-- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-75552801880791614892013-07-01T07:00:00.000-07:002014-01-05T22:07:34.302-08:00Parsing XML in ActionScript 3I recently had a task handed down at work requiring me to parse XML data in ActionScript 3. It sounded simple, because AS3 includes documented libraries to handle XML content. But on my first pass trying to use them, I got unexpected results. After some investigation, I was able to understand what was happening. I was surprised the AS3 documentation didn't explain the behavior of the <span class="code">XML</span> and <span class="code">XMLList</span> classes in better detail, so I hope to fill some of the gaps with a quick write-up of my misadventure.<br><br>
It was little trouble getting the XML file loaded into AS3, and I verified that the file was loading correctly by tracing the resultant <span class="code">XML</span> object's contents in output. But when I tried to filter XML elements out of the <span class="code">XML</span> object by tag name or attribute content, I would sporadically get unexpected results, or get no results returned at all (an empty set).<br><br>
Just for some background, the XML files I was working with contained various lists of buttons for a video game UI. Each button had a button type denoted by its tag title, for example Slider, Toggle, or just plain Button. Each then had attributes, such as Name, ID, and DisplayText. So the XML would look something like this:<br><br>
<script src="https://gist.github.com/StevenKitzes/5833561.js"></script><br>
Note that none of the elements in the above example have any text content! My attributes have values, but the tags have no content between them. (This is legal in XML, but may have been unwise in retrospect, at least for debugging purposes.)<br><br>
When I tried to filter based on button type (in other words, by tag name, e.g. Slider, Toggle, or Button) I would get strange results. When filtering MainMenu, I'd get a list of <span class="code">XML</span> objects for Slider tagged elements and Button tagged elements, as desired; but would receive an empty string when filtering on Toggle tagged objects. Conversely, when filtering GfxMenu, I'd get the opposite; <span class="code">XML</span> objects for Toggle tagged elements but empty strings for the others. What?!<br><br>
At first, I didn't see why this would be happening, and I scoured the AS3 documentation to no avail. But after some experimentation I realized that when filtering, <b>if only one element within the search range meets the requirements of a given search, AS3's <span class="code">XML</span> class will return the text content of the element's tag</b> automatically! And <b>if multiple elements meet the search criteria, a list of XML elements will be returned</b>.<br><br>
I don't know if this was done to satisfy some language specifications or what, but that's what I was able to figure out!<h3>Mystery solved.</h3><br>
Thanks for reading!<br>
-- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-35321041609640095422013-06-24T07:00:00.000-07:002013-06-24T07:00:03.109-07:00Bitmask BasicsWorking directly with bits is one of my favorite things to do as a programmer. I just find it fun! I haven't used these techniques recently in any of my projects, but I wanted to take some time to explain how <i>bitmasks</i> work, and some of their uses and advantages. Hopefully you'll agree they're very useful, and you'll see why I like them so much!<br><br>
Higher level bitwise operations (also known as bit masking, bit flagging, etc) are great for a number of reasons. I find them quite fun, in addition to being useful and more efficient than other methods of Boolean comparisons and assignments. But before going into the methods and uses of bitmasking I should give a little bit of background on the topic. I'll be giving my examples in C++ because that's the language I'm most comfortable and familiar with, but bitmasking is possible in many languages.<br><br>
First of all, what is a <i>bitmask</i> (or, what do I mean when I say <i>bitmask</i>)? In C++ (or any typed language), there are many data types that you are probably familiar with. These data types represent collections of bits, organized into bytes, stored in memory. We normally think about our variables and constants in terms of a given type (for example, <span class="code">int</span>, <span class="code">double</span>, or maybe even <span class="code">float</span>), but behind the scenes <b>an <span class="code">int</span> or <span class="code">double</span> still represents a contiguous set of bits</b>.<br><br>
Let's take the <span class="code">char</span> data type in C++ as an easy example (it only represents a single byte, 8 bits). We can manipulate and compare data types such as <span class="code">char</span>s in terms of their constituent bits. One way of terming such a collection of bits in this context is as a <i>bitmask</i>. This is often the case when using a <span class="code">char</span> or <span class="code">int</span> not to represent an actual character or integer, but rather to represent <b>a condensed set of Boolean values</b>.<br><br>
At this point, you may be wondering: <b>why is this useful</b>? Isn't it simpler to just make a bunch of <span class="code">bool</span> variables and compare those? Well, yes; that would be simpler, and easier for a human to read in the code. But it would necessitate long, convoluted argument lists if those <span class="code">bool</span>s ever needed to be passed around; not to mention that the <span class="code">bool</span> type is very wasteful in languages like C++. Remember, the smallest size for a data type is one byte, 8 bits. So for C++ to store a <span class="code">bool</span> in memory, it must allocate a full byte - 8 bits - even though only one bit is really needed to represent a Boolean value. Then, when making comparisons, an entire operation is wasted on each individual check against each individual <span class="code">bool</span>. Holy smokes!<br><br>
Alternatively, if we have a large number of Boolean variables that we need to track, instead of wasting an entire byte on a <span class="code">bool</span> for each Boolean variable we want to track, we can track up to 8 Boolean values using a <span class="code">char</span>'s 8 individual bits, in the form of a <i>bitmask</i>! (Or, to expound on that idea, up to 16 values in a <span class="code">short int</span>, 32 in a standard <span class="code">int</span>, etc.) In addition to the efficiency achieved by storing several Boolean values' worth of information under a single primitive data type, this also means we can save a lot of time by comparing or manipulating several Boolean values in one go, as well! And of course, we can pass a bitmask as a single arg, which communicates a lot of Boolean data in a single variable, as opposed to needing to go through the hassle of passing multiple <span class="code">bool</span>s or encapsulating them in a container of some kind. So how does all this work...?<br><br>
<h3>Example Time</h3>
Let's start by visualizing a C++ <span class="code">char</span>'s bits.<br><br>
<blockquote>
As an empty bitmask, with no bits turned on, our <span class="code">char</span> would look like this:<br>
<div class="code center">00000000</div><br>
If all the bits were flipped / turned on, it would look like this:<br>
<div class="code center">11111111</div><br>
And with some bits on and some off, the bitmask would look like this:<br>
<div class="code center">00101101</div>
</blockquote><br><br>
Comparing two bitmasks against each other, or checking if a bitmask is either zero or non-zero works more or less as you would probably expect. Keep in mind, the following bitmasks are contained in <span class="code">char</span> type variables. That's why they have 8 bits each.<br><br>
<script src="https://gist.github.com/StevenKitzes/5812090.js"></script><br>
C++ doesn't know or care that we're using our <span class="code">char</span> as a bitmask. It just so happens that <b>we are able to use bitwise operations and comparisons</b> <i>on</i> our <span class="code">char</span>. This means that while we may choose to perform bitwise operations and comparisons on our <span class="code">char</span>, typical C++ comparisons like those on line 10 (comparing identical bitmasks) and line 14 (comparing differing bitmasks) return <span class="code">true</span> and <span class="code">false</span> results just as we would expect. Of course, zero / non-zero checks (such as on line 20) work as we are used to. And finally, assignment works as you would expect as well (such as on line 25).<br><br>
The real value in bitmasks starts to become clear when we look at some of the special operators we can use to compare bitmasks against each other. These are the ampersand, the bar, and the carrot (& | ^). Let's take a look at what each of these operators does.<br><br>
When using these operators with two bitmasks, the bit in each position of the first operand will be compared to the corresponding bit of the second operand. I call this vertical comparison, because it looks like this:
<blockquote>
<div class="code">00101101<br>vvvvvvvv<br>10110110<br>vvvvvvvv<br>????????</div>
</blockquote>
The return value (the question marks) will be a new bitmask, whose bits will be flipped off or on (to 0 or 1 respectively) depending on the rules associated with the operator you are using. The ampersand (and, '&') checks to see if the corresponding bits in <i>both</i> bitmasks are <i>both</i> switched on, and flips the resultant bit on if so. The bar (or, '|') checks to see if the corresponding bits in <i>either</i> (or both) of the compared bitmasks are switched on, and flips the resultant bit on if so. Finally, the carrot (exclusive or, '^') checks <i>specifically</i> to see if one of the compared bitmasks has the bit in a given position switched on, while the corresponding bit in the other bitmask is switched off, and sets the resultant bit on if so.<br><br>
This is a bit tricky to explain concisely, and a bit awkward to digest if you're not used to these concepts, so check out this Gist snippet for examples and visual representations. Here I show how each of these very useful operators works, and can be combined with a variety of comparisons and checks:
<script src="https://gist.github.com/StevenKitzes/5820034.js"></script><br>
<h3>Real-World Example</h3><br>
Now that we have some idea of the mechanics of bitmask assignment and comparison, let's look at some real-world application. One challenge that lends itself particularly well to handling via bitmask is control input checking in video games. Video games, especially action-intensive games, must run at high frame rates, so performance is key and wasting a full <span class="code">bool</span> data type's worth of data on each individual check is a monumental waste of space. As you'll see below, we can efficiently contain and check all the control input Boolean values we need in a single bitmask.<br><br>
In this simple example, imagine a simple game with a perspective looking down onto the top of the player, who can move up, down, left or right, who can perform a regular attack and a special attack. Let's check out how we can manage the input for this control scheme using a bitmask! Note the use of constants here; having these constants available for use in assignment and checks is what makes bitmasks usable as arrays of Boolean values. Without the constants to check against, we wouldn't know what the individual bits in a bitmask represent! Also note the use of hexadecimal expressions to define the constants. I'll talk about this more in the example, but for now, just bear in mind that this is the easiest way (that I know of) to define a bitmask with a single bit flipped on in the position you want. (If you want to understand why I'm using hexadecimal the way I am, you need an understanding of how integers are represented in binary, which I won't explore in this post. An understanding of hexadecimal isn't required to understand this bitmask example, though!)
<script src="https://gist.github.com/StevenKitzes/5824470.js"></script><br>
There is a lot of omitted error checking and pseudocode in this example, but it should give you an idea of how bitmasks can be useful in a real-world application.<br><br>
Thanks for reading!<br>
-- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com3tag:blogger.com,1999:blog-4160731462668027711.post-26805805426607738102013-03-29T09:47:00.000-07:002013-03-29T09:48:29.251-07:00Sum of DigitsWhile playing around and taking online classes in Python, I came across an exercise that I hadn't encountered before (in any language). The goal of the exercise was to write a function that took in an integer as an argument and returned the sum of the digits of the integer.<br><br>
Because this exercise was nestled in a section of <a href="http://www.codecademy.com">Codecademy</a> that showcased looping strategies, <span class="code">for</span> loops in particular, I starting trying to figure out a way to write a Python <span class="code">for</span> loop to solve this problem. That maent I needed to figure out how to iterate over the digits of the <span class="code">int</span> I received and add them up.<br><br>
I had lots of wrong ideas. (Well, not "wrong," per se, but definitely "bad.") My first thought was to convert the <span class="code">int</span> to a string, then iterate over the length of the string, taking each character and converting that back to an <span class="code">int</span> to be added to a total (and then returned later). I didn't like this approach because it seemed clunky and inefficient. I have always felt that using strings to solve any arithmetic problem is probably among the <i>worst</i> ways to do it. It certainly didn't seem like the best approach here.<br><br>
After a few moments of thought, I realized I could get the value of the last (rightmost) digit of any integer by taking the modulo (remainder) <span class="code">x % 10</span>. Attempting to extrapolate this, I got caught up in my excitement and tried to add the values of <span class="code">x % 10^1</span>, <span class="code">x % 10^2</span>, ... <span class="code">x % 10^n</span>, because this would translate somewhat easily to a <span class="code">for</span> loop. This was sort of close to a good answer, and ultimately led me to a good answer.<br><br>
I finally solved the problem by iterating through my integer <span class="code">x</span>, adding <span class="code">x % 10</span> to my total and then dividing <span class="code">x</span> by 10 with each iteration. This method gives each of <span class="code">x</span>'s original digits a turn in the ones' place, to be hit with <span class="code">% 10</span>. I used a <span class="code">while</span> loop instead of a <span class="code">for</span> loop, and iterated through the integer dividing by 10 until my integer was 0 (rounded down). It worked like a charm ...<br><br>
... until I tried a negative number! Python doesn't currently have native support for toward / away from infinity / negative infinity. When using modulo (<span class="code">%</span>), Python always rounds down toward negative infinity. This meant that for any negative, single-digit number <span class="code">x % 10</span>, Python would give me -1 as a result. So, my <span class="code">while</span> loop would never equal 0 and would never exit!<br><br>
My first thought was to write a needlessly complex snippet to catch negative numbers and use <span class="code">math.ceil()</span> to ensure Python would round up in these cases. But that is more complex than it needs to be, since the remainder of any integer <span class="code">x / 10</span> will be the same (in real life) whether <span class="code">x</span> is positive or negative. I fixed this by simply setting <span class="code">x = abs(x)</span> (taking the absolute value of my integer) at the beginning of the function. Perfect!<br><br>
Here is the code, in its beautiful simplicity (my first Python post!):<br><br>
<script src="https://gist.github.com/StevenKitzes/5269180.js"></script><br>
Thanks for reading!<br>
-- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-4605690608963883452013-03-18T11:19:00.000-07:002013-03-18T11:50:46.453-07:00Using Recursion - Word SearchAmid efforts to broaden horizons and learn as much about different disciplines of development as possible, my C++ and heavy algorithms skills have gone somewhat untested lately. Although I have personal projects and work experience that I owe to a past rich in C++ and OOP, it's been a while since I revisited those realms. I decided it was time to test myself and see how I would do on an old challenge I'd tackled before, but not since almost four years ago when I first began seriously programming.<br><br>
Long ago, a friend offered a challenge to help me learn. An aspiring developer himself, he'd taken several programming tests at job interviews. He forwarded one of them to me. The goals were as follows:<br><br>
<ol>
<li><b>Goals:</b></li>
<li>generate a grid of random characters</li>
<li>display the grid to the screen</li>
<li>read in a dictionary file (more a word list, really)</li>
<li>iterate through the list, obeying a set of rules to search the grid for each word</li>
<ol>
<li><b>Rules:</b> using recursion:</li>
<li>when seeking the next letter in a word, navigate only one spot at a time</li>
<li>navigate only in the cardinal directions (up, down, left, right)</li>
<li>never use the character at a single grid location more than once on a given attempt</li>
<li>once a given word is discovered, don't search for more instances of it</li>
</ol>
<li>display the number of words discovered</li>
<li>complete in 8 hours, 6 hours for bonus points</li>
</ol><br>
The first time I attempted this, years ago, it took me about a week's worth of evenings, totalling about 16 hours or so of total time. That's too long, and in the real world I would have failed that programmer test miserably. But it did give me an opportunity to learn about <b>recursion</b>.<br><br>
I still need to sit down and plan out my recursive algorithms if I want them to be clean and efficient, but at least I have a firm grasp of the concept. This time around, I was able to solve the problem in under 5 hours. Here is how I tackled the task:<br><br>
First thing being first, I generated a grid of <span class="code">char</span>s using a two dimensional array to satisfy Goal #1, and slapped together a simple print function to cover Goal #2. Later, instead of simple characters, I came up with <span class="code">structs</span> that contained both a <span class="code">char</span> and a <span class="code">bool</span> (for checking whether a given <span class="code">char</span> had been used during any given check attempt). Then I had to (I admit) Google a way to read in a word list from a text file. Incidentally, Goals #3 and #4 were achieved with the same single <span class="code">while</span> loop, but that part of the solution isn't relevant to the topic of recursion. (You can still see how I did it by viewing the project on my GitHub page, linked at the bottom of this post.)<br><br>
It was finally time to sort through the grid to see if a given word was contained within it ... using recursion! First, how does recursion work? Recursion is a way of looping that's a little more confusing and involved than a simple <span class="code">for</span> or <span class="code">while</span> loop. These types of loops generally (if clearly and cleanly constructed) encapsulated chunks of code that run over and over again until a condition is met, then they stop looping and the program moves forward. Recursion, likewise, allows you to loop a chunk of code over and over again until a condition (usually called the "base case") is met. However, instead of a simple keyword call such as <span class="code">for</span> or <span class="code">while</span>, a <b>recursive function</b> is called. That is, a function that runs some code, and then <i>calls itself</i>, resulting in a looping effect.<br><br>
<blockquote>
<ul>
<li>A recursive function runs some code and then calls itself to create a looping effect similar to a <span class="code">for</span> or <span class="code">while</span> loop.</li>
<li>A recursive function iterates by receiving values from previous calls to itself as arguments, then checks those values to see if the "base case" has been met.</li>
<ul><li>(In some cases, a recursive function may modify and check a variable that is outside its scope and check that variable for the "base case".)</li></ul>
<li>When the "base case" is met, the ultimate result of the nested recursive function calls is returned down through the chain (or "stack") of calls to the original.</li>
</ul>
</blockquote><br>
Take the following C++ snipped as an example. Notice how this simple function:<br>
- accepts a value to get it started<br>
- checks if the value has met the goal (or "base case")
- modifies the value and passes it to another call of itself<br>
- returns the result back down the chain<br><br><br>
<script src="https://gist.github.com/StevenKitzes/5188804.js"></script><br>
Here is a quick walkthrough of how this simple recursive function performs its duties on a call with the value <span class="code">8</span> passed to it.<br><br>
<ul>
<li>First, <span class="code">recursiveExample( 8 )</span> is called. CompSci professors would describe this as placing a call to <span class="code">recursiveExample</span> on the "call stack." In simpler terms, we're on the first layer of recursion and our <span class="code">value</span> is currently 8.</li>
<li><span class="code">recursiveExample</span> checks if the base case has been met; but <span class="code">value</span> is less than 10.</li>
<li>Since the base case was not met, we go to the <span class="code">else</span> block. Here, <span class="code">value</span> is incremented by 1, and <span class="code">recursiveExample</span> calls itself, passing <span class="code">value</span> (currently 9) as the argument.</li>
<ul>
<li>Now there are two instances of <span class="code">recursiveExample</span> on the call stack; we are on the second layer of recursion.</li>
<li><span class="code">recursiveExample</span> checks if <span class="code">value</span> (currently 9) meets the base case, but it doesn't, so again we go to the <span class="code">else</span> block.</li>
<li>In the <span class="code">else</span> block, <span class="code">value</span> is iterated once more, now to 10 (can you predict what will happen next?). <span class="code">recursiveExample</span> then calls itself again, passing <span class="code">value</span> (currently 10) to itself as an argument.</li>
<ul>
<li>We now have three instances of <span class="code">recursiveExample</span> on the call stack, and we're on the third level of recursion, and we have received 10 as the value for our <span class="code">value</span> variable.</li>
<li><span class="code">recursiveExample</span> checks the base case, and sees that it is met (<span class="code">value</span> is greater or equal to 10)!</li>
<li>Since the base case was met, <span class="code">recursiveExample</span> returns <span class="code">value</span>, which is 10. This removes one instance of <span class="code">recursiveExample</span> from the call stack and returns us down to the previous call of <span class="code">recursiveExample</span>.</li>
</ul>
<li>We are now back down on the second layer of recursion. Recall that the last thing we did on this layer was to call an instance of , the second layer of <span class="code">recursiveExample</span>. We pick upu exactly where we left off, and the next thing to appear in code is another <span class="code">return</span>! So that's exactly what we do; <span class="code">return</span> the 10 on down the chain. The 10 is returned, and this second instance of <span class="code">recusiveExample</span> is removed from the call stack.</li>
</ul>
<li>At last, we are back down at the bottom layer, to our original function call. Again, we pick up where we left off and the next piece of code is another <span class="code">return</span>. So we pass the 10 on down, and since this is the final layer of recursion, the 10 is what ends up actually being returned to the program that originally called <span class="code">recursiveExample</span> in the first place!</li>
</ul><br>
I used this idea of recursion in my word search program in checking the grid for successive letters of a given word. For example, taking the word "banana," I would search the grid for a 'b', then pass the word "banana" into my recursive function along with an iterator to represent the position of the next letter in "banana" that I was searching for. That function would check for the base case (in this case, if the letter position iterator had been incremented all the way up to the full length of the word I was searched for). If the base case was not met, the function would search the neighboring grid spots for the next letter in the word. If it found that letter, it would call itself, passing an incremented value as the iterator, with a reference to "banana" (or whatever word). This would continue until an instance of the letter-searching function met the base case (in which case it would <span class="code">return true</span> all the way down the chain), or the function was unable to find the next letter while obeying all the rules of the WordSearch challenge (in which case it would <span class="code">return false</span> all the way down the chain). Here, you can see what this recursive function looks like in my program:<br><br><br>
<script src="https://gist.github.com/StevenKitzes/5189691.js"></script><br>
You can see my <a href="https://github.com/StevenKitzes/WordSearch">WordSearch</a> program in its entirety on my GitHub page! The recursive function itself is called <span class="code">checkNextLetter</span>, and it can be found on line 76 of <span class="code">main.cpp</span>, <a href="https://github.com/StevenKitzes/WordSearch/blob/master/main.cpp">here</a>. It's a bit more complicated than the simple example above, but you can spot some of the basic elements of a recursive function. For example, see lines 79 to 82, where <span class="code">checkNextLetter</span> checks if the base case has been met and returns <span class="code">true</span> if it has. Also check out lines 88, 95, 102, and 109 where <span class="code">checkNextLetter</span> calls itself (and increments the <span class="code">spot</span> value at the same time), creating the recursive equivalent of the looping effect.<br><br>
Thanks for reading!<br>
--<br>
Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-48163420409707074512013-02-19T13:11:00.001-08:002013-06-05T17:40:18.031-07:00Mounting Nexus 7 Using MTPI'm sort of surprised no one else has come across this problem before, or posted this solution - at least, not that I could find - so I'm telling this story in the hopes it will help someone down the line. (If you want my solution to the problem, here's the <a href="#cliffsnotes">Cliff's Notes</a> at the bottom of this post.)<br><br>
I ran into a problem today, trying to mount my Nexus 7 to my laptop, which is equipped with Ubuntu 12.10. When I plugged in the Nexus 7, I expected it to just work. I thought the device would appear on the desktop and in the Nautilus sidebar and just be accessible for file transfers over MTP. The device didn't show up.<br><br>
I spent a good hour or so scouring the web for any help or hints I could find on how to mount a Nexus 7, running Jelly Bean, to Ubuntu. I found over a dozen convoluted work-arounds, updates, middleware installation guides, and other recommendations - all of which I tried (the free ones, anyway) and none of which made any difference at all. Using the work-arounds and various third-party software, I was able to determine that Ubuntu 12.10 could see the device, and obtain vendor and product ID information from it. But the device could not be mounted using MTP to transfer files. I got a variety of errors and warnings, which I followed up with Google searches that resulted in even more searches and fixes and updates and work-arounds, and another hour later, the device still wouldn't connect over MTP.<br><br>
Scratching my head, I moved the Nexus 7 to my PC, a 64 bit Windows 7 machine. I plugged in the Nexus and it appeared in my Windows Explorer sidebar under the name I had given the device, but it was not expandable and the file system couldn't be accessed. I went into the Windows Control Panel and the device appeared there, under the correct name and in the right location, but again, couldn't be accessed. Flabbergasted, I started the whole search / update / word-around routine from scratch, this time on Win7. Again, to no avail.<br><br>
I checked that the USB setting for the device itself was set to MTP, and it was. I tried restarting Ubuntu. I tried restarting Windows. I tried restarting the Nexus. I tried restarting them in varying orders. Nothing!<br><br>
In desperation, I went into the USB connection setting on the Nexus 7 and switched it from MTP to PTP (the Camera protocol). I did this with the device plugged into the Windows PC, and this prompted the installation of new drivers for PTP. The device was now fully available as a media storage device, and gave me access to the part of the Jelly Bean file system where picture files are normally stored (DCIM, etc). Ah-hah! The device's file system capacity and available free space appeared, and were accurate. Ah-<i>hah</i>!<br><br>
I switched back to MTP. No new installation of drivers, no pop-ups asking me what I wanted to do with the device, nothing changed on the surface. But when I accessed the device by name in Windows Explorer again, I now had access to the entire file system. Voila! I made some changes, moved things around, used the device some, and the file system disapparated from Windows yet again. Why?!<br><br>
I repeated the steps again, did some testing (my QA experience played a role in this process), and ultimately came to the discovery that the Android device would only give Windows access to its file system when the device's "USB computer connection" settings menu was in focus, with MTP selected. Ugh!<br><br>
<a name="cliffsnotes"></a><blockquote><b>Cliff's Notes:</b><br><br>To use an MTP connection between my Android 4.2 / Jelly Bean device and my computer, I must navigate to the "USB computer connection" menu on the Android device, make sure "Media device (MTP)" is selected, and leave that menu on-screen until I am done transferring files.</blockquote><br>
I want to note that I still can't get the device to mount on Ubuntu. I get a wholly new error, something about "Transport endpoint is not connected." But I have seen blog posts and articles about this error, as well. I'm sure I can spend another hour or two chasing wild geese around until I figure that one out, too. For now, I'm just glad I figured out how to knock some sense into the device itself!<br><br>
Thanks for reading!<br />
- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-20273444922961592642013-02-07T13:23:00.000-08:002013-02-19T13:08:08.621-08:00Value of an AceI made a Blackjack game to test myself on the JavaScript I have learned so far. (Link to it at the <a href="#linkToGame">bottom of this post</a>.) The greatest challenge I faced in getting the game to work was the variable value of an Ace. As you will know if you're familiar with the game of Blackjack, the objective is to get the player's hand as close as possible to a value of 21, <b>without</b> going over (which is an automatic loss). The player starts with two cards, and can continually ask for more cards until the player fears "busting" (going over 21), then the player may stop and pray that the dealer will do a worse job.<br /><br />
Aces behave in a special way in this game, as they are generally valued at 11, but their <b>value changes</b> if the player accidentally goes over 21. If the player is holding an Ace and goes over 21, the Ace will drop from a value of 11 to just 1. This value changes as the player draws new cards, and every Ace drawn will behave this way independently. So I needed to handle the scoring of a hand in a way that would allow the value of an Ace to be evaluated anew <b>every time</b> a new card was drawn.<br /><br />
When I started building the scoring function I ran into some problems. The first problem was timing. Because Aces change their value based on the non-Ace cards in the player's hand, I couldn't evaluate the player's hand in the order it was dealt.<br /><br />
Take the following example, in which the player is dealt (and the player hand is populated with) 5, 4, Ace, and 8, in that order. If I evaluate the cards in order, I would come to the Ace at a time when the cumulative value of the hand is still only 9 (first 5, then add the next card, 4). Since the 8 hasn't been added yet, the Ace seems like a great addition to the hand at this point, because even if I'm checking for bust (going over 21), 9 + Ace (11) would be 20, which is very close to 21. But then, when the 8 is added, the player would bust - I would want to evaluate the Ace as a 1, but it would be too late, the Ace was already evaluated!<br /><br />
One solution that came to mind early on was to reiterate through the hand any time a bust was detected, and check for Aces. I could subtract 10 from the total value of the hand for each Ace (if any) until the value of the hand came back to under 22 (leaving any remaining Ace valued at 11). But this struck me as a rather inelegant and scrappy solution. I wanted to evaluate the Aces on the fly so I wouldn't have to feel like I was "going back" and removing value that had already been added to the hand.<br /><br />
I got around this by adding the value of each non-Ace to the value of the hand and leaving out the values of any Aces, but <i>counting</i> the <b>number of</b> Aces. Only after the non-Ace value of the hand was evaluated, I began to evaluate and add in the value of each Ace. This is where things became complicated algorithmically. I needed to put together an algorithm to check not just whether an Ace would bust the hand, but whether an Ace would bust the hand <i>in light</i> of the fact that there is a variable quantity of Aces left to evaluate!<br /><br />
Here's what I came up with, I'll explain it below.<br /><br />
<script src="https://gist.github.com/StevenKitzes/4733468.js"></script>
The good part is the <span class="code">for</span> loop at line 24, where Ace values are evaluated. The <span class="code">for</span> loop iterates through all the Aces. For each Ace, I check whether the hand would bust if the Ace was valued at 11, and all remaining Aces were valued at 1. If the hand would bust, the Ace is evaluated to 1; otherwise, it gets an 11 and the loop continues.<br /><br />
<b>In retrospect</b>, and as more experienced developers / mathematicians / Blackjack players will likely have noticed, this excessively elaborate Ace evaluation algorithm is entirely unnecessary! You only ever have to check whether the <i>first</i> Ace would bust the hand. If one Ace is valued at 11, you know all the rest must be valued at 1, because if two Aces evaluated to 11, you would already have busted with 22. Oops! If I continue to iterate this game with future editions, I will fix this inefficiency (because now it's bugging me).<br /><br />
If you want to try out the game, you're of course welcome! Be warned, it's fairly rudimentary as Blackjack games go, I was more concerned with getting JavaScript up and running on a website than with putting together a faithful representation of the game of Blackjack. (No betting, can't double down or split, no automatic win for Blackjack, but the basics are all there, single player versus a dealer.) Also, as a bare-bones first attempt at writing my own JS in the wild, the entire game exists in alert() and confirm() pop-ups, so apologies for all the clicking you'll have to do to play it! At any rate, <a id="linkToGame" href="http://www.stevenkitzes.com/blackjack.html">here it is</a>.<br><br>
Thanks for reading!<br />
- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-11073406941198793312013-02-06T10:20:00.000-08:002014-01-04T02:42:21.630-08:00State Based MenusRecently I've been doing a lot of UI (user interface, or menu) work, specifically for console and mobile video games. This hasn't turned out to be nearly as easy as I originally thought it would be. To my relief, others have confided in me that even seasoned veterans of the gaming and mobile app industries find it difficult to engineer UI without things getting pretty kludgy. There are lots of problems to solve along the way, so I thought I'd share some of what I've learned along the way about designing and building game UI.<br /><br />
I want to concentrate on <b>state-based menus</b>. One of the easiest ways to navigate between screens, elements, and submenus of a user interface is using <i>states</i>. If you don't know what that means, my goal today is to try to explain it. I have seen it explained many times in terms that I, as a junior developer, did not understand, so I want to revisit the topic in a way that is as easy as possible to understand for beginners.<br /><br />
So, what is a <b>state</b>? Let's build an analogy using a very simple example. A light in your home has two states. One state, <i>on</i>, represents the light's status when it is (hopefully) powered and glowing. The other state, <i>off</i>, represents the light when it is unpowered and dark. The user can choose from these two states to tell the light how to behave. A simple, state-based interface! Of course, in computer programming terms, even this simple two-state interface can begin to look complicated. Obviously, if the light is off and the user attempts to turn it on, we apply power. If the light is on and the user tries to turn it off, we remove power. But what happens if the user tries to turn the light on when it's already on? What happens if the user tries to turn the light on, but there is no power? We have to account for these possibilities and more.<br /><br />
In the case of a menu system like one you might see in a video game, you might have a "Main Menu" state, a "Load Game" state, an "Options" state, and others. The "state" itself is stored somewhere as a variable. This can be conveniently handled with an <b>enumerated index</b>, which makes it easier for you (and other people working in your project) to read. Using enumeration at the lower level can be a bit intimidating for beginners, but think of it like this: you have a variable, an <span class="code">int</span> called <span class="code">menuState</span>, which is our state variable. Then you have a collection of words that represent <b>constant values</b> that <span class="code">menuState</span> might represent. If your <span class="code">menuState</span> integer matches one of the constant values you defined (an enumerated value), the menu is in a state that it recognizes! Consider the following snippet, defining (enumerating) some constant integer values that represent a menu's states, and setting up a <span class="code">menuState</span> variable.<br /><br />
<script src="https://gist.github.com/4674269.js"></script>
To connect this to our light bulb analogy, consider the menu system to be the light bulb itself - it can be switched from one state to another. For example, when your program is first loaded and the UI is initialized, the application might take the user to the Main Menu state automatically. But the user can then switch to another <b>state</b>, just as you can switch a light from "off" to "on." Just as you would use a switch to change a light's state from "off" to "on," you can use UI controls to change a menu's state from "Main Menu" to "Options Menu"! For a more concrete example of what I'm talking about, consider this next snippet. Read the comments if the code is a bit confusing right now.<br /><br />
<script src="https://gist.github.com/4674422.js"></script>
For a more complex example, I'll take the case of a project I was recently assigned. One feature of a game we are making is an image gallery. One of the greatest challenges in building this gallery has been organizing the functions of the menu so that each element is only visible when I want it to be - in other words, when the menu is in the proper state! In organizing the gallery menu into states, the first step was to look at the features and functions the gallery needed to have.<br /><br />
According to the project specifications, the gallery needed to be separated into categories, with a set of buttons to select each category; a grid of selectable image thumbnails filling the rest of the screen; a popup window to display selected images full size; a dialog window for providing extra information to the user; a confirm window for making selections; and an alert pop-up to warn the user when trying to select an item that is not available. If that sounds like a lot of things to manage in one menu, I agree. I felt the same way the first time an assignment like this was handed to me. But using states, breaking these menu elements into manageable chunks was a breeze! I'll talk through my process to make it a little easier to see.<br /><br />
The first step I took was to break each function of the gallery apart into pieces, to be grouped into states based on <i>when</i> the functions would be available. For example, when the category buttons needed to be active, nothing else in the menu could be. The game needed to know that when the category buttons were active, arrow key and button presses would <i>only</i> affect the category buttons themselves. The solution is to tell the gallery menu that it is in the CategoryButtons state!<br /><br />
When the menu is in a given state, input should only effect the part of the menu that corresponds to the current state. For example, when the user presses the down arrow, if the menu is in the CategoryButtons state, the cursor should move down the list of category buttons. The cursor in the thumbnail grid should not move; in fact, it probably shouldn't be visible at all! Then, when the player finally presses a button to confirm a category selection, the state of the menu is changed from CategoryButtons to ThumbnailButtons. Now, the game sees the state change, makes the category button cursor disappear, and makes a cursor appear on the thumbnail grid. Now, control input makes the thumbnail cursor move, instead of the category button cursor! See the following snippet for an example of how this would look in code. Again, I've tried to add a lot of comments to make it clear what I'm doing in the code.<br /><br />
<script src="https://gist.github.com/4674773.js"></script>
Obviously, there is a lot more to state-based UI development than just managing the states themselves. And of course, states can be used for a plethora of other tasks that I haven't begun to delve into, and there is a lot of other stuff to worry about when you are putting a UI together. States are just the beginning and help to organize your menu and control flow throughout the menu navigation process. But hopefully this will help you understand the fundamental state-based strategy for menu management!<br /><br />
Thanks for reading!<br />
- Steven KitzesSteven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com0tag:blogger.com,1999:blog-4160731462668027711.post-66890955091126982612013-01-16T14:16:00.003-08:002013-01-17T07:25:05.965-08:00MotivationI have struggled with the idea of <i>motivation</i> throughout my life. I was always told by family and friends that I was capable of great things. "You're so smart," they told me. "You'd be able to do such-and-such if only you'd get <i>motivated</i>." I could get in shape, I could find love, I could learn to program. All I needed was <i>motivation</i>.<br /><br />
That makes it sound so easy. You see people around you all the time who are motivated to do or attain things. They have reached, or are on the road to reaching those goals. You see the guy who is up and on his bicycle at 5am every morning to ride 60 miles. You see the guy who has his laptop out every morning at Starbucks monitoring the world financial markets. You see all kinds of people working hard to get what they want. Just do what they do: wake up in the morning and feel <i>motivated</i>.<br /><br />
I always wanted to be a computer programmer, to one end or another. And though I did genuinely desire to learn the trade, I never possessed the <i>motivation</i>. My friends and family told me to work at it, just keep plugging away, but I couldn't find the <i>motivation</i>. I used to beat myself up about it daily. It drove me mad, almost to tears. I truly wanted to be a programmer. So why, despite the <i>desire</i>, did I lack the <i>motivation</i>?<br /><br />
I tried telling myself I was motivated. I tried the infamous fake-it-till-you-make-it routine. I tried to <i>feel</i> motivated, to generate a sort of synthetic enthusiasm. I slipped in and out of periods of extraordinary effort - not effort toward learning programming, but effort toward <i>getting motivated</i> to learn programming. I even tried forcing myself to learn programming even <i>without</i> feeling motivated. This went on for no less than two decades.<br /><br />
But for some reason, no matter what I tried, I couldn't force it upon myself. It wasn't until after motivation finally struck me of its own accord that I realized <i>desire</i> and <i>effort</i> do not necessarily cultivate <i>motivation</i>.<br /><br />
One morning several months ago, I woke up, bleary-eyed, and gazed around the room, which was a shambles. The night, week, and month leading up to that morning had been a bit of a blur, part of a period of time I would define by its extraordinary <i>lack</i> of effort either to motivate myself or to learn programming. But as I came to my senses that fateful morning, I sensed that a new dawn had broken over the horizon of my life. I was going to get my ducks in a row. I was going to become a grown-up.<br /><br />
I redoubled my efforts as a Junior Programmer at work. I built my own libraries, not because I had to but because I wanted to know how it was done. I built very simple ones at first, of course. But I wanted to learn and grow and optimize and share and contribute. I was <i>motivated</i>. Not a single day has passed since then that I haven't learned something or improved upon something in my coding repertoire. Not a day has passed since that morning that I haven't spent an hour or so of my own free time learning. Sometimes more or less, but my free time is going into this on a daily basis. I am <i>motivated</i>.<br /><br />
Looking back on this motivational renaissance, I have attempted to identify the catalyst that led to the reignition of my passion as a budding programmer. I was somewhat dismayed to find that I couldn't. Perhaps to be more fair, I <i>could</i> speculate as to whether certain conditions in my life had performed a sort of slow-acting emotional catalysis. But I <i>couldn't</i> say in fairness that I did anything to motivate <i>myself</i>. Motivation came to <i>me</i>.<br /><br />
So if you are out there trying to figure out how to motivate yourself to learn programming, get in shape, or whatever it is you want to do, don't give up on the <i>desire</i>. It never hurts to practice or work toward your goals. But if the <i>motivation</i> doesn't come, don't be discouraged. When you are ready, life will let you know.Steven Kitzeshttp://www.blogger.com/profile/03316977460501102447noreply@blogger.com3