#Forward
#What is “Kata”
Kata is example code or question for practicing coding, that is repeatedly written to hone the proficiency of various programming skills (such as using IDE shortcut keys, using design patterns to refactor code…) to achieve the state of subconsciously completing hand actions.
This noun is from some sort of martial arts, means “type”, “form” or “move” etc, single part of whole. It’s written as かた in Japanese, pronounced as “ka ta”, same as the English word.
#What is “Conway’s Game of Life Kata”
You can read this Wikipedia page for information about “Conway’s Game of Life”, but I think most of us have already known it.
This kata is a question on Coding Dojo website.
#What will we do in this blog
In this article I’ll only cover the core function about cell’s next generation state checker, without any UI for playing it (it’s not easy to write an elegant UI for it with barely own code). I’ll use text-first (not strictly base on TDD practice I think) method to write it.
The “checker” will follow these rules to judge cell’s next state:
- Any live cell with less than two or more than three live neighbours dead.
- Any dead cell with three live neighbours becomes a live cell.
- Any live cell with two or three live neighbours survives.
- All other dead cell without three live neighbours stay dead.
What’s more, the grid where cells set in here is considered as simply connected, which means that:
- the grid has no edge, neighbors of one cell just beyond array edge is cells on the opposite side (e.g., cell (1,0) 3 left neighbors is (0,n-1),(1,n-1),(2,n-1) ).
You may have seen this feature on those old games, where the elements on the screen disappear in one side, then appear from opposite side again, the screen like a rolling scroll.
Get any pencil and paper beside you? Or open your editor, lets take down or just copy & paste these 5 rules as user stories i.e., user requirements.
Sounds pretty simple, huh? In the end we got 40 lines of function code and 90 lines of example-based unit-test code. I spend about less than half hour to write it after I’m familiar with it. A suitable size for daily practice I guess. I use this Kata to practice IntelliJ IDEA shortcuts (Settings > Keymap). In this kata we can practise refactor, run & debug, navigating… plenty of common shortcuts used in daily work.
By the way, you can get the code in this Github repo , it’s build with Maven, so I guess you can save some time of preparing environment by just downloading this repo if you’ve got Maven on you device.
And… if you think this post is too simple now, I recommend you to try the classic The Bowling Game Kata, and here is a solution: The Bowling Game: An example of test-first pair programming by Robert C. Martin and Robert S. Koss (this site seems to be a mirror and maybe can’t respond, but the original url Uncle Bob quoted on the book had down).
#Make the first rule passes test
#Init function code
Now lets implement the rule 1:
- Any live cell with less than two or more than three live neighbours dead.
New package “com.practice.daily.d20210606”, new file “Checker.java”:
|
|
Wait, what parameters should we type in? Lets think based on testing (you don’t need to really write unit test first, just think test first will benefit your code):
-
We’ll pass a custom gird and custom cell position to API, thus we can control the input Checker taken. So, the Checker APIs need receive an 2-dim array represent for whole grid, with a pair of coordinate for position of one cell. What type should array taken, int or boolean? I don’t want to write condition like “array[i][j] == 1”, and it ought to be boolean type from the problem description, so I choose boolean.
-
As we’re using Java, an Object-oriented Programming language, should we pass the grid as Checker’s construction parameter? Both is ok, and I choose to let Checker to be non-state component, because it’s easier for testing it. In Java, this type method is a “static method”.
So the method signature becomes:
|
|
#Write test code
Now Let’s write unit tests. New file under “src/test” directory, “CheckerTest.java”. I installed a plugin
called JUnitGenerator V2.0
, so I’ll use Generate...
: Alt
+ Insert
then select “Junit test” to generate and removing all
content (Extend Selection
: Shift
+ W
and Backspace
). Although I don’t need the code, this plugin can help me
generate directories and files, it’s enough:
|
|
Now add first test case (using JUnit to test). I had written an Editor > Live Templates
, set abbreviation “tpv” as "
@Test public void “, so I type “tpv” and enter, add method name, brackets, use Complete Current Statement
: Shift
Ctrl
+Enter
add braces.
|
|
Now… we have to decide how to construct test data, mainly means that grid. Let’s shrink Checker’s behavior without " simply connected” feature, so the ideal gird is 3 by 3 size, call Checker with central position (1,1). Based on SRP principle, I write an independent method about this test data generator, to separate instance creating code from test case ( it’s a Simple Factory):
|
|
Replacing 2-level-repeat for-loop with Java 8 Stream API can reduce keyboard typing. If you use for-loop, you’ll find that IDEA can’t help you a lot on auto-completion. You need to write almost every part of condition, and for-loop condition’s characters are allover the keyboard. You can get IDEA auto-completion to help you by using Stream API.
Now type Previous Method
: Alt
+ up arrow
, jump to upper test case method and finish it:
|
|
Type Run
: Shift
+ F10
, test failed, test turn over, now it’s turn of function code.
#Complete function code
Type Select Previous Tab
: Alt
+ left arrow
, go back. How the Checker works? Straightly think, it counts live
neighbors count of given cell (8 cells), judging it by rules, then return the judgment result, 3 steps. Implement it:
|
|
I use Stream API again, but what is the AtomicInteger ? Check this StackOverflow question . In brief, Java lambda expression will be converted to an anonymous inner class, and in this type of class you can’t use mutable local variables. So we need to change the “count” variable type from int to some sort of wrapper type, so we can change the value while remain object reference not changed.
“Integer” can’t work at here because inside it’s constructor it can only hold a final int type field “value”: “private final int value;”. If we want to change an Integer type variable, the compiler will generate a new instance then assign it to variable reference, which against anonymous inner class’s rule. So we’ll use this “AtomicInteger” type, which holds an “Integer” type field inside itself. In fact, there are two choices IDEA gives to us.
Don’t worry about additional typing. when you type “int count=0;” outside stream and “… count++ …” inside stream
lambda expression, IDEA will point it out with an error sign. Type Error Description
: Ctrl
+ F1
to check
information, IDEA says that “Variable used in lambda expression should be final or effectively final”. Then you can
fix it simply with familiar Alt
+ Enter
, IDEA gives you two option: “Convert to atomic”, or "
Transform ‘count’ into final one element array". You can try the second choice, it also works.
#Find the mistake with debug
Ok… Select Next Tab
: Alt
+ right arrow
, Run
the test case:
|
|
Uh-oh, debug time. Now back to function code, then Toggle Line Breakpoint
: Ctrl
+ F8
on “line 12: count.getAndIncrement();”. Run Debug
: Shift
+ F9
.
At first hint, we can see that IDEA shows the variable values as “i=1, m=-1, j=1, n=-1”. We want
to know which cell passes the condition now, without mental arithmetic even it’s easy. So we push
down Alt
, and take the mouse (first time picking up mouse after creating files), move cursor on
“line 11: if (grid[i + m][j + n]) {”, on “i + m” part (IDEA automatically selects them for you),
click the left mouse button, then IDEA shows this expression’s calculating result: "
0".
This is IDEA debugger
Quick Evaluate
function. You can trigger it with Ctrl
+ Alt
+ F8
on the keyboard, so you can still put your hands on the
keyboard. To do so, first you need to navigate your cursor on target text
(use Go to Line:Column...
: Ctrl
+ G
), then select them, then trigger evaluation. Sorry, pure keyboard programming
school, but I’d prefer one click with mouse.
Now back to code. Our evaluation shows that first hint is gird[0][0], yep, we do put the "
true"
value on (0,0) (getTestGrid(1, 0, 0, 0, 1, 0, 0, 0, 0);). Move to the next hint with Resume Program
: F9
, evaluate
index, it’s gird[1][1]. Oh, we find the bug, we mistakenly count the target cell while we shouldn’t.
There are only two “true” value we passed to the Checker, so we can assume that "
breakpoint line 12"
won’t be hinted again. Let’s type Step Over
: F8
until cursor moves to “line 16:
return count.get() >= 2;”: “count” value is 2, so that’s why the Checker returned wrong answer.
#Fix that mistake
We can fix that bug by slightly change line 16 to “return count.get() - 1 >= 2;”, type Esc
return to Editor window from Debug tab then change it. Though we have fixed it on source code, the debugger is still
running with old code, we need to reload it. IDEA gives us an approach to reload code without rerunning the test case (
e.g., the whole context). It seems useless in this Kata, but it really can reduce restart time when debugging big
complex projects. Type Build Project
:
Ctrl
+ F9
to rebuild it, and IDEA shows the message:
“CheckerTest.liveLessThanTwoDie: 1 class reloaded”.
Let’s set a breakpoint on line 16 for convenience. We have rebuild code now, but we want to see how command stream flows
in Checker.checkCellNextState() method again. Now here is the magic: Drop Frame
: no default keybinding
(you can find
the GUI button besides Quick Evaluate button), the top invoke frame is dropped, and we back to Checker calling line
(line 14: boolean state = Checker.checkCellNextState(gird, 1, 1);) in test case!
Type Resume Program
and go into the Checker again, resume, check, resume…… confirmed,
Step Out
: Shift
+ F8
to test case, Resume
, test pass.
#Add code to finish the rule 1
Add another test case:
|
|
Run it with Run
, fail as expected. Now change the function code:
|
|
Now we want to run both two test cases to check our change not break the first test.
IDEA can store 5 temporary configurations, which are automatically generated when you run code from one different
entrance (in Java, it’s a unit test or unit test suit or main method).
Run
can only rerun the latest configuration. If your cursor is inside a new entrance and push Run
, IDEA generates
that new configuration and run the code. If both 5 temp configs already be there, somehow IDEA can’t automatically
select the new config and run it (though already generated it), but rerun an old config, so we need additional steps
with Run...
Action.
Use Previous Method
move cursor to “line 10: public class CheckerTest {”. Type
Run...
:Shift
+ Alt
+ F10
to open IDEA’s Run Configurations pop-up. Now configuration about running “CheckerTest”
test suit should be at bottom, select and push Enter
, both two tests passed. From now on when I say “Run”, it means
run the whole test suit i.e., the whole test class.
Something can be refactored in function code, in the “line 16: return count.get() - 1 == 2 || count.get() - 1 == 3;”.
Based on Select “count.get() -1”, push
Introduce Variable
: Ctrl
+ Alt
+ V
, extract and rename it as “liveNeighborCount”. Oh, we can also extract live
neighbors count code into separate privat method by select lines and push
Extract Method...
: Ctrl
+ Alt
+ M
.
Whew, finally, we finished the rule 1, we’ve finished about more than half of the total work. Now code looks like:
|
|
#Make the 2,3,4 rules pass test
Let’s move to the second rule:
- Any dead cell with three live neighbours becomes a live cell.
|
|
Run test, oh, test pass, don’t worry about test not fail, it’s ok for now. Next rule:
- Any live cell with two or three live neighbours survives.
Uh-huh, we can confirm this behavior works because we just write the code as this description but…… we’d better write them down as new tests to make the test suit stay completed:
|
|
There’s no doubt that these tests can pass. Work on the rule 4 now:
- All other dead cell without three live neighbours stay dead.
|
|
“deadTwoDie()” passes and “deadMoreThanThreeDie()” fail….. Time to change function code. We can easily figure out the difference between count live cell’s live neighbors and count dead cell’s: dead cell don’t need to minus itself after count all live cells. So we can change code to this:
|
|
Yep, all 7 test cases pass after change. By the way, you can move two exist lines by move cursor on first line, keep
pushing Shift
and type one down arrow
to select two lines, and use
Move Line Up|Down
: Shift
+ Alt
+ up|down Arrow
. When one part of line has being selected, and you use commands
like “Copy”, “Move” etc, IDEA will adjust the target to whole line, it’s a little tip.
#Make the “simply connected” feature works
With normal rules already been implemented, we can consider that weird “simply connected” feature. I can figure out two test case for it:
- 1 0 1 | 1 0 1
- 0 0 0 | 0 0 0
- 1 0 1 | 0 0 1
On the cases above, none of live cell have live neighbors next to it, if not considering connected feature.
For the first case, if we call the Checker with four vertex positions, all of them get 3 live neighbors, so they can keep living in next generation. If something goes wrong cause duplicated count, Checker will judge some of them dead due to 4 or more live neighbors.
For the second case, Checker should count exactly two live neighbors or goes wrong with missed count, which also leads to wrong judgment. The corresponding test code is:
|
|
None of them pass, how to make them pass? This feature is sort of like circular array, we want to know how to calculate real index from virtual index. I’d prefer to scribble a draft in my notebook when question related to graph. First we draw a 3 by 3 grid. Center element is our target cell, assume that it’s coordinate is (i,j).
………………………………………………………
|
|
Tests pass, we finished the last requirement. After a little more refactors, now the whole code is:
|
|
I think that’s about as “clean” a code as I can do.
#What’s more
If you want to learn IDEA shortcuts, In late 2016, IDEA made an interactive tool to help you, and it was integrated right in the IDEA afterwards.