Wednesday, July 5, 2017

More Maze Programming: Adding Some Bias for Longer Paths

Okay, so I know that I said I might be done with Mazes for Programmers, But, I went one chapter further and picked up a couple of more algorithms: Hunt and Kill, and Recursive Backtracker.

As a reminder, you can pick up the code here: GItHub - jeremybytes/mazes-for-programmers.

The reason these are interesting is that they add a bit of bias. Last time, we saw an unbiased algorithm that is completely random. This was better than the very biased algorithms that we had seen previously, but it was also a bit slow since it relies on random walks to fill an entire grid.

This works great, but good mazes are more than random events. So by adding a bit of bias, we can make longer paths, twistier paths, and fewer dead-ends. This makes a maze more interesting to solve.

Hunt and Kill
The first slightly-biased algorithm is Hunt and Kill. This scans the cells from the top left corner. When it finds a cell that has "unvisited neighbors" (meaning there are no links to the cell), then it makes a random connection and moves to the next cell. When it can't go any further (such as when it loops into a dead end), it goes back to scanning to find a cell with unvisited neighbors so that it can start again.

Because this is not completely random, it is much faster than the Aldous-Broder algorithm that we saw last time. And it creates some longer passages. Here's a graphical version:


And here's a text version:


It's particularly easy to spot the longer passage here when we look at the path from the center to the lower right corner.

It also makes nice patterns for larger mazes:



I find myself getting lost in some of the images. The dark areas represent the spots furthest from the center. So the top image has lots of things "furthest" away. The bottom image has a few things "furthest" away.

Recursive Backtracker
The other slightly-biased algorithm is the Recursive Backtracker. Like Hunt and Kill, this creates longer passages with fewer dead ends. But it operates a bit differently. When it hits a dead end, it doesn't start scanning for a new starting point (like Hunt and Kill). Instead, it keeps track of all the cells that have been visited by using a stack. If it comes to a dead end, it pops cells off the stack until it finds one that has an unvisited neighbor (meaning, another path to be started). When all of the cells are popped off the stack, that means we've visited each cell and we're done.

Here's the graphical version of Recursive Backtracker on a small grid:


And here's the text version:


Again, we can see a pretty long, twisty path from the center to the corner. And this is just as interesting when we create larger mazes:



I kind of like these because you'll find these twisty paths of one color running through the middle of a section with a lighter or darker color.

Differences
In addition to the slightly different patterns that come out of these algorithms, there are a few performance differences. I've noticed that the Hunt and Kill takes a little bit longer to complete. The Recursive Backtracker is a little bit faster, but it consumes more memory since it's keeping track of every single cell on the stack. Each of these has pros and cons, and if you're interested, pick up your own copy of Mazes for Programmers (Amazon link).

What's Next
As you can see, I've switched up the colors a little for these samples. But this is done by changing values in the code. Now that I'm seeing the interesting patterns that are created by these, I'm going to explore adding some more interesting color elements as well.

I've always been intrigued by pseudo-randomly created pictures. I can see that I'm going to be running quite a few of these in the future.

As always, keep playing and keep exploring.

Happy Coding!

Sunday, July 2, 2017

More Maze Programming: A Non-Biased Algorithm

So back to Mazes for Programmers, this time looking at a non-biased algorithm. This is where I start thinking about repurposing this whole maze-building thing.

As a reminder, you can get the code here: GitHub - jeremybytes/mazes-for-programmers. I added some comments to the "Program.cs" file so that you can do some experimentation with different algorithms, grids, and grid sizes.

Biased Algorithms
The two algorithms previously implemented were Sidewinder and Binary Tree. These both have biases, meaning there are certain patterns that repeat based on the algorithm. For example, the binary tree algorithm tends to create a diagonal across the maze. This is visible with a 15x15 maze:


But it's even more obvious when we have a larger maze (155 x 155):


Another thing is that this produces a straight path along the top (north) edge of the maze as well as the right (east) edge of the maze.

Non-Biased Algorithms
Mazes for Programmers presents 2 non-biased algorithms. I've implemented one of them: the Aldous-Broder algorithm. This was independently developed by David Aldous and Andrei Broder. It uses a random walk to create a non-biased algorithm.

One of the important points for a maze algorithm is that is should not create loops, and this algorithm does ensure that while still creating random paths. Basically, it creates random paths until they link up. If a loop is created, then that path is discarded.

Here's the Ruby code from the book:


And here's my implementation in C#:


This produces a random path. Here's a text representation showing the shortest path from the center to the lower-left corner:


And here's a graphical representation showing a heat map of distances from the center:


What's interesting is that if we run this multiple times, we won't see a pattern forming (such as the diagonal pattern formed with the Binary Tree). Here are several runs with a larger grid:





This starts to look pretty interesting. Unfortunately, because of the random nature of the algorithm, it gets much slower the larger the grid, and I don't think there's an easy way to parallelize the process.

As a side note, the other non-biased algorithm presented in the book, Wilson's algorithm, uses a random walk as well, and it suffers from a similar performance issue. The difference is that while Aldous-Broder has slowness at the end (while it tries to hook up the last few cells), Wilson's has slowness at the front (where it tries to hook up the first cell). I haven't done any performance analysis, and I think that's outside the scope of my interest right now.

Accidental Art
Here's a 255 x 255 grid. This took several minutes to produce on my machine. But because it uses random numbers, the time to produce it is non-deterministic.


This is really cool. I think it's time for me to repurpose this and start creating interesting visual patterns. I could probably set up some color transitions in addition to the shade transitions of the heat map. I'll be playing with this quite a bit in the near future.

Wrap Up
I don't know how much further I'll get in the Mazes for Programmers book. I think I may have gotten the information I need regarding the algorithms and how things work. This is a good jumping off point for me to explore on my own.

I'll be playing with the heat map quite a bit. It's easy to remove the maze lines and just have the colors (I did that accidentally last night). And adding some color transitions would be pretty cool.

I also need to go through the F# code that Steve Gilham put together. It looks like I'll need to decompose things a bit to make it work with various display output (it does text right now, but I'd want to add the graphical display) as well as to support the distance calculations that make the paths and heat maps possible. So I've got lots to play with.

I've also got lots of real work to do as well. But it's also good to play and explore from time to time. That's part of the learning process.

Happy Coding!

Saturday, July 1, 2017

More Maze Programming: Heat Map

It's been a while since I've pulled out Mazes for Programmers (it looks like it was March). I picked it up again tonight to do a bit of programming. This time, I added the code to create a heat map of a maze.

You can get the current code here: GitHub - jeremybytes/mazes-for-programmers.

Here's a sample of the output:


This uses the center square as the "start". The colors get darker as the path to each square is further away.

The code in its current state produces 2 outputs. The example above is a .png file that is saved to the file system (and automatically shown by the console application).

The console application also generates a text output:


If you compare this to the graphic output, you can see that these are the same maze. The numbers here are a bit different. Instead of creating a heat map of distances, this shows the shortest path from the start (the center of the grid) to the finish (the lower left corner). By following the path, this shows that 34 steps are required to get from the center to the finish.

The code isn't great at this point. The reason is that I'm doing a straight-across port from the Ruby code that is presented in the book. And I'm also not a big fan of the way the objects are put together in the book code. But I'm still working on the underlying concepts of mazes, and then I can work on making the code a bit better.

As stated previously, I'd like to get some F# code in here, and I've gotten some great contributions from the community including this sample from Steve Gilham: Steve's F# Implementation. I haven't had a chance to dig through Steve's sample. From my initial look, I can tell that I need to think about breaking down problems in a different way than I'm used to.

I'm looking forward to diving into that more.

Happy Coding!

Friday, June 30, 2017

Book Review: Working Effectively with Unit Tests

I recently finished reading Working Effectively with Unit Tests by Jay Fields (Amazon link). I'm a bit mixed on whether I would recommend this book. There are some good unit testing tips, but it wasn't especially memorable, and there were a few things that I didn't care for too much.

The short version is that my main recommendation for unit testing techniques will remain The Art of Unit Testing by Roy Osherove (Jeremy's review).

Things I Liked
Keep What Works
There were a few general messages that I really liked. The first is try stuff and keep what works. I always prefer a non-dogmatic approach because not every technique works in every environment. I really appreciate that Fields talks about some of the things that he's done in the past, liked them, but then later stopped using them because they no longer fit his situation.

Descriptive Tests
Another message that I really liked is to keep tests DAMP (Descriptive And Maintainable Procedures) as opposed to DRY (Don't Repeat Yourself). Keeping common code centralized is a good practice for our production code, but testing code is a bit different. Tests are really meant to be independent, isolated, and not interact with each other, whereas our production code needs to be cohesive and collaborative.

This really follows my general advice to make sure that tests are readable. It's good to be a bit more verbose and explicit so that they are very easy to approach when we need to look at the actual test code.

Setup Methods
As far as specific recommendations, there are several that I found useful. First is generally avoiding setup methods. By keeping setup (the "Arrange" step) local to the test, it enhances readability and helps make sure we are only using the things that we need for a particular test.

For example, in a test class-level setup method, we may have multiple objects instantiated with various states that we can use in different tests. This means that we could have objects that are instantiated in a setup but are not actually used for a test. This means that we've got some wasted code, and it also makes it a bit harder for us to determine exactly what's important for a particular test.

I've explored something along these lines (Unit Testing: Setup Methods or Not?), although I tended to use factory methods that are explicitly called to get some of the non-critical bits out of the tests themselves. Fields' technique is definitely worth exploring some more.

Assertions
There are a couple pieces of good advice regarding assertions, including one assertion per test. This is particularly important because most testing frameworks use exceptions for tests. So when the first assertion fails, no code after it will run. If we have several assertions, we don't know if we have a single failure or multiple failures. If we keep one assertion per test, then we can tell where our problems are. This also goes along with the DAMP approach; we don't need to be afraid of duplicating behavior in unit tests.

Another piece of advice is to assert last. The thing that we are actually verifying should be at the very end of the test method. This makes it really easy to find what we're testing. And this also goes along with the "Arrange/Act/Assert" layout which I really like.

Fields also spends time talking about testing for exceptions and some of the weirdness that is caused by using a try/catch block. When using a try/catch block, the assertion is in the middle of code (usually in the catch block), and we also need to have a "fail" in the middle of the code if an exception is not thrown.

To get around this, Fields suggests making a custom assertion method, Assert.Throws(), that can be used to check for exceptions without a try/catch block, and can also be put at the end of the test. That way we can follow the "assert last" advice. This is similar to the "Assert.Throws()" that is provided with NUnit (and other frameworks that provide custom assertions). I wrote a bit about this in Testing for Exceptions with NUnit.

Things I Have Mixed Feelings About
Solitary and Sociable
There were a few things that I had mixed feelings about. One of them had to do with Solitary Unit Tests vs. Sociable Unit Tests.

A solitary unit test is a test where only 1 object is "new"ed up. Everything else is some sort of test double, like a stub or mock. A sociable unit test has multiple objected "new"ed and checks the interaction between them.

I don't really like the definition of sociable unit test because to me that steps outside of the world of unit testing and starts moving into integration testing. Fields does mention integration testing, but he looks at that as more of an end-to-end type thing. I've generally looked at integration testing as checking that the objects work together at different levels -- from localized to end-to-end.

This isn't really important in the grand scheme of things. I just seem to put all of my "unit tests" into the "solitary unit test" bucket.

Fields does make the recommendation of separating the solitary unit tests and sociable unit tests. The solitary ones are generally very fast and we want to run those very often, and the sociable ones may take a bit longer (for example, if there are I/O operations) and we probably run those less frequently. This is very good advice.

Sample Scenario
Another thing that I was mixed about is the sample scenario. I do like that the same application code was used throughout the entire book. But the scenario was a video rental store. Since the book is from 2014, this example was a bit out of date when it was published. As someone who is well over 40, I have no problems remembering what it was like to rent movies from a physical store. But I'm sure there are lots of developers today who have not had that experience.

Again, not a big deal. The samples could easily be updated to use a video kiosk rather than store.

Things I Didn't Like
The First Test
While I like that the same scenario is used throughout the book and that there was a focus on continuously improving the tests, I really did not like the first example.

The reason is that Fields states, "Let's get straight to code" and then shows a rather-difficult-to-read example and says "you don't need to understand this." From my perspective, that defeats the purpose of going straight to code.

Motivators
Another thing that left a bit of a bad taste had to do with test motivators. Fields spends some time telling us that it is important to understand our motivation for writing tests in order to write effective tests that match the motivation. He also spends quite a bit of time listing different motivators. The problem is that these motivators are not used in the rest of the book (unless I missed it). So it looks like we're being told that it's important to understand the motivation, but doesn't tell us how that impacts things in a practical way.

Naming
Another thing I don't agree with is Fields' opinion on naming tests. He likens test names to comments. Since the test methods are never called directly, the test names are unnecessary and at worst can add confusion. I agree that test names are comments, but I have seen usefulness in that. When a test has a good name, when it fails I can tell what happened simply by looking at the test explorer; I don't need to dig into details to see what went wrong (at least, I don't need to dig into the test details nearly as often).

I would liken test names more to variable names than comments. When we have useful variable names, it enhances the readability of our code. This is why I'll often include an intermediate variable. Then I can include some "comments" about what it is doing by giving it a good name, even if the code itself is not that hard to understand.

The Last Test
While I like most of the techniques presented, I wasn't a big fan of the final test state. His use of Test Data Builders throughout the book were interesting, and they gave me some ideas that I would like to work through. But the conclusion was a bit of a logical extreme:


Here's the text

public class CustomerTest {
  @Test
  public void chargeForTwoRentals() {
    assertMoney(
      5.7,
      a.customer.build().addRentals(
        create(
          stub(Rental class)
            returning(a.money.w(2.2).build())
            .from().getCharge()),
        create(
          stub(Rental class)
            returning(a.money.w(3.5).build())
            .from().getCharge()))
      .getTotalCharge());
  }
}

For someone walking up to this test for the first time, it is a bit confusing. I think it's because the Arrange, Act, and Assert all get mixed together. Fields promotes this as a good choice because it does follow "assert last" (although it's basically crammed the entire test into the assertion).

To pick this apart a bit, the behavior that we're testing (the "Act") is at the very end: "getTotalCharge()". The "Arrange" is really everything after "a.customer.build()..." which creates an object with test data so that we can call "getTotalCharge()" on a populated object. The "Assert" is the last step, but also the first step (which is weird in my mind).

I think that the test data builders can be very useful, but I would really like to see a standard "Arrange/Act/Assert" layout with some intermediate variables for readability.

Wrap Up
While Working Effectively with Unit Tests by Jay Fields does have some good advice, I think the drawbacks keep me from making it a recommendation. For general testing advice, I'd still go with The Art of Unit Testing by Roy Osherove.

Happy Coding!

Thursday, May 25, 2017

It's a Bit Quiet Around Here

So, it's been a bit quiet around here lately: no new articles, videos, or other stuff. I've been a bit busy and a bit distracted.

Traveling
I've been traveling a bit more than usual. I've got 3 conferences over 5 weeks, with a total of 11 presentations (including a half-day workshop). And all of the conferences involve flying quite far from home. I've completed 2 of the trips (CodeStock in Knoxville TN and SDD in London, England). Next week, I wrap up with Music City Code in Nashville TN.

In addition to the conferences, I took a few extra days for sightseeing. I've always wanted to go to Dollywood, so when I was in eastern Tennessee, I had to jump on the opportunity. I had a great day riding roller coasters and listening to Smokey Mountain music. Here are some pictures: Dollywood! (and some other stuff).


CodeStock was a great conference. I got to catch up with a lot of old friends, and I got to meet some new people, too. With the way things are for me right now, conferences are all about the people. And I've had some great conversations.

London is one of my favorite cities, so I took some time to explore when I was there for SDD 2017. The thing about London is that there is history *everywhere*. It's easy to see something that looks interesting at the end of the road, check it out, and then see something else interesting to explore. I ran across all sorts of interesting things including William Blake's grave, canal boats, and a trapeze school. I also went to Regent's Park (which I visited back in January). I wanted to see what it looks like in the spring time, and it was really beautiful with the leaves on the trees. Here are the pictures from this trip: London May 2017.


I was also really busy at SDD 2017. I had 6 talks, including 2 in the Cinema -- which was an actual cinema. They showed Alien: Covenant there the night before I spoke. Here are a few shots of me speaking:



I got to talk to a lot of really great people at SDD. It was really exhausting, but I had a great time.

Relocating
The thing that's been taking up the rest of my time is relocating. I'm moving from Southern California to northern Washington. This is part of the path I started down when deciding whether to pursue a high-risk opportunity (and the update).

Relocating is a big step. But I've also wanted to get out of the expense and traffic of Southern California for a while now. The movers come in less than 3 weeks, so I'm frantically putting the last 15 years of my life into boxes (and figuring out all the stuff that I can jettison).


(BTW, don't worry about the Post-It notes in the picture. I'm going to label the boxes more permanently once I have a better idea of what everything looks like.)

I probably wouldn't be too panicked about the move, but I'm going to Nashville next week, so that's 5 fewer days that I have for packing, organizing, trips to Goodwill, etc.

I know that I'll be fine, but I'll be a bit stressed for the next few weeks.

I'll publish more articles and videos in the future; I've got several ideas that I've been working on. But it will be a while before I have some dedicated time to sit down and do them. Until then...

Happy Coding!

Sunday, April 30, 2017

May & June 2017 Speaking Engagements

My speaking schedule has been a bit slow lately, but things are picking up in May and June.

Friday-Saturday, May 5-6, 2017
CodeStock
Knoxville, TN
Event Site
Topics:
o I'll Get Back to You: Task, Await, and Asynchronous Methods in C#
o Becoming a Social Developer: A Guide for Introverts

I've been wanting to go to CodeStock for several years, so I was really happy when I learned I was selected to speak this year. On top of that, it's the 10th anniversary of CodeStock. I'm looking forward to meeting lots of new people and also catching up with some friends that I haven't seen in a while. The line-up of topics and speakers looks great. There's a lot of fun and learning in store.

Monday-Friday, May 15-19, 2017
SDD 2017
London, England
Event Site
Topics:
o I'll Get Back to You: Task, Await, and Asynchronous Methods in C#
o Becoming a Social Developer: A Guide for Introverts
o Learn to Love Lambdas (and LINQ, Too!)
o DI Why? Getting a Grip on Dependency Injection
o Unit Testing Makes Me Faster: Convincing Your Boss, Your Co-Workers, and Yourself
o Clean Code: Homicidal Maniacs Read Code, Too!

As you can see, I'll be pretty busy during the Software Design & Development Conference. These are all topics that I love to talk about, and I'm really excited that I get to share them with a new group of people. I've heard some great things about this event. The speaker line up is pretty incredible; check out the full list.

Thursday-Saturday, June 1-3, 2017
Music City Code
Nashville, TN
Event Site
Topics:
o Awesome C#: Unit Testing (Half-Day Workshop)
o Design Patterns: Not Just for Architects
o Unit Testing Makes Me Faster: Convincing Your Boss, Your Co-Workers, and Yourself

I had a really great time at Music City Code last year. I met lots of people and also started some lasting relationships. This time around, I have the opportunity to give a half-day workshop on unit testing. I'm really looking forward to sharing some of the hurdles I've run into as well as some techniques to make testing easier and more effective.

A Note About Topics
You might have noticed that I tend to do the same talks over and over. (I add 1 or 2 new topics each year.) That's because these are topics that I struggled with as a developer. And they are topics that developers still struggle with today. I do my best to help people over the hurdles that I had to get over. I know that when things are less mysterious, they suddenly get much more exciting to me, and I try to encourage that in everyone who comes to one of my talks.

I used to feel bad about talking about the same things over and over again. But I've found that I'm really effective at making these topics understandable. And there are always new people to show them to.

A Look Back
In April, I had the chance to speak at the Global Scrum Gathering in San Diego, CA. I got to share how "Unit Testing Makes Me Faster". Here are a few pictures taken by Lynn Winterboer and Scott Dunn.



Thanks to Lynn (@agilelynn) for lots of tweets during the talk. She even grabbed a couple videos of me showing videos:
https://twitter.com/agilelynn/status/851499685273579520

https://twitter.com/agilelynn/status/851506435913547776

A Look Ahead
There's lots of stuff coming up for the rest of the year. In July, I'll be headed to Detroit.Code() in Detroit MI. In August, I'm back at KCDC in Kansas City MO. In September, I'll be at Visual Studio Live Chicago in Chicago IL. In October, I'll be at TechBash in Pocono Manor PA and Visual Studio Live Anaheim (which is really in Garden Grove CA). And there's still a few tentative events on my calendar.

In the midst of all this, I'm relocating to Washington state in June. I'll be looking for local events, MeetUps, and user groups in the Pacific Northwest. So if you'd like me to come to your event, be sure to drop me a line.

Hope to see you at an event soon!

Happy Coding!


Tuesday, April 25, 2017

Implementing a Fibonacci Sequence with Value Tuples in C# 7

I decided to do some experimentation with the Fibonacci Sequence. I wanted to see if I could implement it with value tuples in C# similar to the way that I had previously done with F#. And I wanted to see how similar or different they are.

Previously, I implemented a Fibonacci Sequence in C# by TDDing into the code. The code is pretty imperative, but the readability is okay (it could be better):


Even better, we have a set of passing unit tests. So we can safely do experimentation and know when we've messed something up.

Note: you can grab the code for this article on GitHub: jeremybytes/fibonacci-tdd. Both the TDD and value tuple steps are included as branches.

The Idea (from F#)
Here's the idea: last year I worked through the first 10 Euler problems to learn F# a bit better. In particular, Euler #2 uses the Fibonacci Sequence. The implementation that I ended up with used tuples, and I wondered if I could use the C# 7 value tuples to create something similar.

Here's the code from the F# implementation (you can see the whole thing here: Functional Practice: Euler Problem #2 in F#):


This uses a "fold" which runs the specified function for each item in the list and hangs on to an accumulator value. In this case, the accumulator is a tuple that is initialized to "(0,1)". Then for each item in the list, it will create a new tuple consisting of the second value of the original ("b") and the sum of the first and second values ("a + b"). For a deeper dive, check out that article.

My implementation in C# will be a little bit different from this. First, this function gets the "nth" Fibonacci value. So if I call this function "fibonacci 4", it will give me the single value of "3". Instead of returning the "nth" value, we want to create a sequence that iterates through all the values (and yes, the F# article does describe that a little later, but we'll take things one step at a time).

Switching to Value Tuples
Rather than using a "fold" (or the LINQ version "Aggregate"), we'll stick with the "while" loop to return the values as they are requested. But we still want to use the same type of tuple for the accumulator.

So the first step is to create a tuple variable that we can initialize to "(0,1)":


As mentioned in a prior article, we cannot simply use a value tuple out of the box (even though we're using Visual Studio 2017 and C# 7). The feature has to be brought in through a NuGet package. I'm still not happy about how this works today. As Thomas Levesque pointed out in the comments, the release order is kind of out of whack. Welcome to the new world.

Anyway, we just need to bring in the "System.ValueTuple" package:


And everything works:


One slight difference is that we have the initial values noted as "0L" and "1L". This tells the compiler that we want to use the "long" integer type, and it will create the correct tuple with 2 long values.

Now we just need to do the same math as in the F# function and return the result:


Just like the F# "fold" function above, we create a new tuple where the first element is the second element of the previous value, and the second element is the sum of the first and second elements.

Then we return the first element of the tuple (which is what the "fst" function does in the F# code).

The good news is that all of the tests still pass:


Great! That means we have a working implementation.

Improving Readability
The readability of this is not great. One thing we can do is give our tuple elements names. We'll use "current" and "next":


This makes it a little bit easier to keep track of the elements in our tuple. And it's also clear that we're returning the correct value "current".

And importantly, all of our tests still pass:


Is This Better?
It's great that I got to experiment some with value tuples (and sad that I ran into the issue trying to use them initially). But is this a better implementation?

Let's look at them side-by-side:

Original Implementation

With Tuples

Neither of these implementations is particularly readable. The original version suffers because we're using the previous, current, and next variables and swapping them from place to place. It's a bit confusing to figure out exactly what's happening.

The tuple version has kind of the same problem. We have eliminated one of the variables so now we only have two (current and next), but we're still doing a swap and math that isn't real clear.

Wrap Up
The fun thing about experimenting is that you're never quite sure what you'll find. In this case, it's interesting that we can implement the Fibonacci Sequence fairly easily using value tuples. But I don't think we've improved readability much. Less code is often good, but not if it obfuscates things.

I think I'd have to call these implementations a "draw" in their current state. They both have similar readability issues. But that just means that we can do some more experimentation to see what we can come up with.

Happy Coding!