Years ago I discussed with a friend how to solve The Knight's Tour Problem with a program. Over time I started to implement a backtracking logic to solve the problem in different programming languages. In the following text I describe my adventures and insights during the development in different programming languages.
The Knight's Tour Problem searches for solutions in which a knight moves over a chessboard in a way that it jumps on every field exactly once. If the Knight can reach its starting point, when it moves to the last empty square, this is called a closed solution. (German: geschlossene Touren)
For more information on the Knight's tour problem see Wikipedia (German: Springerproblem)
Progressing in the development, I focused on finding all closed solutions only. The programs also count all solutions, but this is not an exhaustive list, because the algorithm I used only starts in the upper left corner.
Since I don't want to wait too long for the calculation of the solutions for a regular 8 x 8 chess board during development, I use a board of size 6 x 5 by default. In this case there are 4542 solutions and 16 roundtripps.
Because the Knight kind of jumps over the board, I call the project and programs jumpsaround or short jumper.
To compute the solutions I use the backtracking algorithm. No algorithmic optimizations are used.
I did this just for fun, to compare programming languages in syntax, design and performance, with a relatively simple, but non-trivial algorithm. The following code is ordered in the sequence I developed it.
A high level description of the logic I will use in the following lineup:
In the following you find code excerpts from parts which are discussed. Additionally there are always links to view and download the sources.
At the end is an overview of all the performance results.
C was the third programming language I learned after BASIC on home computers and Turbo Pascal 3.0 under CPM.
The C version ist the first implementation I made. I used the GCC compiler.
Let's talk about the implementation.
There is a Robustness principle also known as "Postel's law" for designing interfaces. Jon Postel was and RFC Editor, Protocol Guru. As functions are has an interface you can - or should - also apply this rule here.
"Be liberal in what you accept andIn other words, when you call a function make sure all parameters are within the expected value range. When you write a function, make sure that the function can handle unexpected values.
Implementing both rules in such a simple program would be
overkill.
I have weighted the first part of the rule a bit more.
So in the first version of the implementation, the jumpto function validates
if it was called with valid values for the board position.
Source of jumpsaround_0.c: view, download
40 void jumpto(signed char x, signed char y, int iter, char arity) { 41 42 // check if position is on the board 43 if ( x<0 || x>(SIZEX-1) || y<0 || y>(SIZEY-1) ) return; 44 45 // check if field on board is still empty 46 if ( board[x][y] != 0 ) return; 47 48 // ok - store position 49 board[x][y] = iter; 50 iters[iter] = arity + '0'; 51 52 // finished? 53 if (iter >= SIZEX*SIZEY ) { 54 55 // check for jumper roundtrips 56 signed int round = 0; 57 for (int i = 0; i < 8; i++) { 58 signed char nx = x + jump[i][0]; 59 signed char ny = y + jump[i][1]; 60 // check if position is on the board 61 if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue; 62 // detect roundtrip 63 if ( board[nx][ny] == 1 ) { round = 1; roundtrips++; break; } // True 64 } 65 solutions++; 66 printboard(round); 67 68 // end this iteration 69 board[x][y] = 0; 70 iters[iter] = 0; 71 return; 72 } 73 74 // try next jump 75 for (int i = 0; i < 8; i++) { 76 signed char nx = x + jump[i][0]; 77 signed char ny = y + jump[i][1]; 78 jumpto(nx, ny, iter + 1, i); 79 } 80 81 // this iteration is done 82 board[x][y] = 0; 83 iters[iter] = 0; 84 85 }
This obviously resulted in many function calls to board positions which are already used or are off the board. To check the impact of unnecessary calls I changed the implementation to validate the destination coordinates before the function is called. So here I followed the second part of the Robustness principle. (Remember, you should do both!)
"Be liberal in what you accept andThis second version reduced the time needed by about 30%.
I know that it takes time to push parameters onto the stack and reserve memory for the called function, but this is more then I expected.
Source of jumpsaround_1.c: view, download
42 void jumpto(signed char x, signed char y, int iter, char arity) { 43 44 // ok - store position 45 board[x][y] = iter; 46 iters[iter] = arity + '0'; 47 48 // finished? 49 if (iter >= SIZEX*SIZEY ) { 50 51 // check for jumper roundtrips 52 signed int round = 0; 53 for (int i = 0; i < 8; i++) { 54 signed char nx = x + jump[i][0]; 55 signed char ny = y + jump[i][1]; 56 // check if position is on the board 57 if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue; 58 // detect roundtrip 59 if ( board[nx][ny] == 1 ) { round = 1; roundtrips++; break; } // True 60 } 61 62 solutions++; 63 printboard(round); 64 65 board[x][y] = 0; 66 iters[iter] = 0; 67 return; 68 } 69 70 // try next jump 71 for (int i = 0; i < 8; i++) { 72 73 // new position 74 signed char nx = x + jump[i][0]; 75 signed char ny = y + jump[i][1]; 76 77 // check if new position is on the board 78 if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue; 79 80 // check if new field position is still empty 81 if ( board[nx][ny] != 0 ) continue; 82 83 jumpto(nx, ny, iter + 1, i); 84 } 85 86 // this iteration is done 87 board[x][y] = 0; 88 iters[iter] = 0; 89 90 }
This C program became the basic version for the following programs.
In my opinion C is still a pragmatic and consistent programming language, but it lacks some modern features and secure memory access and easy multithreading. C would not be my first choice for new programs, but is still good if it is used in existing projects.
With creating the initial version of this website I tried the gcc compiler option -O2.
Later I checked all "regular" -On compiler options in an separate test.
(There are options to activate each optimization individually.)
Here are the results.
Execution time in seconds:
| Optimizer Flag | none | -O1 | -O2 | -O3 |
|---|---|---|---|---|
| jumpsaround_0.c | 7.6 | 4.1 | 3.8 | 3.8 |
| jumpsaround_1.c | 5.5 | 2.4 | 3.2 | 1.8 |
As expected usually each higher optimization level speeds up the
program execution time.
But looking at version 1 and the optimizer flags -O1 and -O2
you can see that the higher optimization level made the code slower.
That's strange.
But note that the results cannot be generalized. The values are only valid for this example program. Other logics may result in different optimizer results.
Version 1 is always significant faster than version 0. So I deduct, that the compiler does not reorder code like I did manually.
I also took a look at the times needed to compile jumpsaround_x.c with the different optimizer flags.
Compile time in seconds:
| Optimizer Flag | none | -O1 | -O2 | -O3 |
|---|---|---|---|---|
| jumpsaround_0.c | 0.05 | 0.07 | 0.08 | 0.10 |
| jumpsaround_1.c | 0.06 | 0.07 | 0.09 | 0.11 |
As documented each higher optimization level needs more compile time. But the program is too small to make significant statements about the times.
Here you can find more about the Gcc optimizer options.
GO is a relatively new, modern, compiled language. It is straightforward in structure and easy to learn. The compiler is very fast and the standard library is extensive.
I use Go for a small personal project: Another static web-site generator.
In the first version I simply used "type inference"
to let the compiler determine the datatype, or used int if needed.
This program version is already faster than the C version.
Source of jumpsaround_1.go: view, download
18 var board boardt 19 var jump = [8][2]int{{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1}, {2, 1}, {-1, 2}, {1, 2}} 20 var solutions = 0 21 var roundtrips = 0 22 23 func main() { 24 fmt.Println("Hello, Jumper!") 25 26 jumpto(0, 0, 1) 27 28 fmt.Println("I am done.") 29 } 30 31 func jumpto(x, y, iter int) { 32 33 // ok - store position 34 board[x][y] = iter 35 36 // finished? 37 if iter >= SIZEX*SIZEY { 38 39 // check for jumper roundtrips 40 round := false 41 for _, d := range jump { 42 nx := x + d[0] 43 ny := y + d[1] 44 // check if position is on the board 45 if nx < 0 || nx > (SIZEX-1) || ny < 0 || ny > (SIZEY-1) { 46 continue 47 } 48 // detect roundtrip 49 if board[nx][ny] == 1 { 50 round = true 51 roundtrips++ 52 break 53 } // True 54 } 55 56 solutions++ 57 if round == true { 58 printboard(round) 59 } 60 board[x][y] = 0 61 return 62 } 63 64 // try next jump 65 for _, d := range jump { 66 nx := x + d[0] 67 ny := y + d[1] 68 69 // check if position is on the board 70 if nx < 0 || nx > (SIZEX-1) || ny < 0 || ny > (SIZEY-1) { 71 continue 72 } 73 74 // check if new field position is still empty 75 if board[nx][ny] != 0 { 76 continue 77 } // True 78 79 jumpto(nx, ny, iter+1) 80 } 81 82 // this iteration is done 83 board[x][y] = 0 84 85 }
By type inference and the normal int a 64-bit integer is used.
But 64-bit ints are not needed, so I used 32-bit integers in the second version.
This made the code about 7% faster.
Source of jumpsaround_2.go: view, download
15 type boardt [SIZEX][SIZEY]int32 16 var board boardt 17 var jump = [8][2]int32{{-1,-2}, {1,-2}, {-2,-1}, {2,-1}, {-2,1}, {2,1}, {-1,2}, {1,2}} 18 var solutions int32 = 0 19 var roundtrips int32 = 0
31 func jumpto(x, y, iter int32) { 32
Go is also known for its easy multithreading
and should handle thousands of threads well.
I tried this with version 3.
The jumpto function is simply always called with a go
in a single thread.
The board must now be passed as a copy.
An atomic addition is also used for the summation of solutions and round trips.
The number of threads is kept in a WaitGroup and waits until all threads are finished.
Source of jumpsaround_3.go: view, download
26 func main() { 27 fmt.Println("Hello, Jumper!") 28 var board boardt // [SIZEX][SIZEY]int 29 wg.Add(1) // <<-- 30 jumpto(board, 0, 0, 1) 31 wg.Wait() // waiting for waitgroup processes // <<-- 32 fmt.Println("===== Solution #", solutions," (Roundtripps:", roundtrips, ") ====== ") 33 fmt.Println("I am done.") 34 } 35 36 37 func jumpto(board boardt, x, y, iter int32) { 38 39 defer wg.Done() // <<-- 40 41 // ok - store position 42 board[x][y] = iter 43 44 // finished ? 45 if iter >= SIZEX*SIZEY { 46 47 // check for jumper roundtrips 48 round := false 49 for _, d := range jump { 50 nx := x + d[0] 51 ny := y + d[1] 52 // check if position is on the board 53 if nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) { continue } 54 // detect roundtrip 55 if board[nx][ny] == 1 { round = true; atomic.AddInt32(&roundtrips,1); break } // True 56 } 57 58 atomic.AddInt32(&solutions, 1) // <<-- 59 60 printboard(board, round) 61 62 return 63 } 64 65 // try next jump 66 for _, d := range jump { 67 nx := x + d[0] 68 ny := y + d[1] 69 70 // check if position is on the board 71 if nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) { continue } 72 73 // check if new field position is still empty 74 if board[nx][ny] != 0 { continue } // True 75 76 wg.Add(1) // <<-- 77 go jumpto(board, nx, ny, iter + 1); // <<-- 78 } 79 80 // this iteration is done 81 board[x][y] = 0; 82 83 }
As already expected, it is not a good idea to open thousands of threads without any reason. The program now needs 5 times longer to find the solution. But despite the fact that this version is slower, I'm amazed at how well Go handles so many threads.
That's why I chose a slightly smarter solution. Now a new thread is started only in the second iteration:
The output of the board has also been synchronized, so that no two boards are simultaneously printed by two threads to avoid a mess.
Here now follows the fastest solution so far, which needs only one third of the time of the C program.
Source of jumpsaround_4.go: view, download
69 // try next jump 70 for _, d := range jump { 71 nx := x + d[0] 72 ny := y + d[1] 73 74 // check if position is on the board 75 if nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) { continue } 76 77 // check if new field position is still empty 78 if board[nx][ny] != 0 { continue } // True 79 80 if iter == SPAWN { // SPAWN = 2 // <<-- 81 wg.Add(1) 82 go jumpto(board, nx, ny, iter + 1); // <<-- 83 } else { 84 jumpto(board, nx, ny, iter + 1); // <<-- 85 } 86 } 87 88 // this iteration is done 89 board[x][y] = 0; 90 91 } 92 93 94 func printboard(board boardt, round bool) { 95 mutex.Lock() // <<-- 96 if round == true { fmt.Println(" *** Roundtrip #", roundtrips, "*** ")
All in all, parallel programming in Go is quite easy.
Go is just fun to use. The easy to learn language, the fast turnaround cycles for code — compile — test is amazing. In my opinion it stands up to Python, in its clarity and simplicity. However, Go is by magnitudes faster than Python, as we will see later.
Go is current my favorite goto language for most programming tasks.
There is a nice, german introduction to Go on Heise: Ein Einstieg in die Programmiersprache Go
Racket is a Scheme. Scheme is a Lisp dialect. And I really wanted to try out Scheme as a functional program.
Of course you will notice the typical Lisp brackets in Racket.
Source of jumpsaround.rkt: view, download
1 #lang racket 2 3 ; jumpsaround - jumper game 4 ; (c) 2020 Alexander Kulbartsch 5 6 (define SIZEX 6) ;6 7 (define SIZEY 5) ;5 8 9 (define JUMP '{{-1 -2} {1 -2} {-2 -1} {2 -1} {-2 1} {2 1} {-1 2} {1 2}} ) 10 11 (define board (make-vector (* SIZEX SIZEY) 0)) 12 (define solutions 0) 13 (define roundtrips 0) 14 15 (define (board-ref x y) 16 (vector-ref board (+ x (* y SIZEX)))) 17 18 (define (board-set! x y v) 19 (vector-set! board (+ x (* y SIZEX)) v)) 20 21 (define (printboard rt) 22 (printf "===== Solution # ~a - Roundtripps: ~a ====== \n" solutions roundtrips) 23 (if rt (printf " *** Roundtrip *** ") #f) 24 (for ([i SIZEY]) 25 (for ([j SIZEX]) 26 (printf "~a:" (board-ref j i))) 27 (printf "\n")) 28 (printf "\n")) 29 30 31 (define (jumpto x y iter) 32 (board-set! x y iter) 33 ;check if finished 34 (if (>= iter (* SIZEX SIZEY)) 35 (begin ;check for roundtrips 36 (let ([round #f]) 37 (map (lambda (d) 38 (let ([nx (+ x (car d))] 39 [ny (+ y (cadr d))]) 40 (if (and (not round) 41 (>= nx 0) (< nx SIZEX) 42 (>= ny 0) (< ny SIZEY)) 43 (if (= (board-ref nx ny) 1) 44 (begin 45 (set! roundtrips (+ roundtrips 1)) 46 (set! round #t)) 47 #f ) 48 #f ))) 49 JUMP) 50 (set! solutions (+ solutions 1)) 51 (printboard round))) 52 ; else try next 53 (map (lambda (d) 54 (let ([nx (+ x (car d))] 55 [ny (+ y (cadr d))]) 56 (if (and (>= nx 0) (< nx SIZEX) 57 (>= ny 0) (< ny SIZEY)) 58 (if (= (board-ref nx ny) 0) 59 (begin 60 ; (display nx) 61 (jumpto nx ny (add1 iter)) ) 62 #f) 63 #f))) 64 JUMP)) 65 66 (board-set! x y 0) 67 ) 68 69 (define (start) 70 (printf "Hello Jumper!\n") 71 ;(display board) 72 (jumpto 0 0 1) 73 (printf "I am done.\n")) 74 75 (let ([start-sec (current-inexact-milliseconds)]) 76 (start) 77 (printf "Duration: ~a seconds.\n" (/ (- (current-inexact-milliseconds) start-sec) 1000))) 78 79 ; EOF
Idiomatic Scheme would separate code into smaller functions. Here it just reproduces the base version logic with a to big function.
Racket can be interpreted or compiled. The interpreted version needed 25 times more time than the C version, the Compiled version still needed 5 times longer.
But Racket is not just only a Scheme, it's also possible to define you own language with it. For example Typed Racket which adds statically type checking or Pollen which is a publishing system.
I like the Lisp and Scheme functional languages for their precise syntax
(function parameters...).
There is no difference between statements and (own) functions.
Even data is structured the same way.
This and the possibility to extend it
with the powerful macro system according to your needs to a
domain specific language
(DSL).
Racket also comes with a nice IDE
which has an integrated REPL.
But if you are used to ALGOL-like structured languages like C or Java you have to change your thinking to grasp the functional programming concepts.
Guile is another implementation of Scheme. It was recommended to me to try this out as well.
I had to change some function calls, where Racket offers some more first-time user friendly variants. But generally it's the same.
Source of jumpsaround.scm: view, download
The compiled Guile version needed 4 times as much time compared to the compiled Racket version. I am a little disappointed.
The V Programming Language is a relatively new language. It aims to be as simple (or simpler) as Go and as secure as Rust. The compiler is extremely fast, but for faster production builds it transpiles V to C and let the C compiler do the optimizations. V has an easy multithreading option like Go and gains to have a cross platform batteries included library with web, GUI, ORM and graphics features. Fascinating ist, that V is primarily a one person project. But there is already a growing community around it.
To gain the security of Rust V does not have global variables. So you have to pass the whole state. For the first version I put the Knights jump definitions into a not-mutable variable into the function. But this allocates memory on the heap whenever the function is called. This memory is (in the current version 0.1.29) not freed on the end of the function, which resulted in a memory exhaustion during run. In the next iteration I used constants, which are only allowed on module level. This worked well.
Source of jumpsaround_2.v: view, download
7 const ( 8 // {{-1,-2}, {1,-2}, {-2,-1}, {2,-1}, {-2,1}, {2,1}, {-1,2}, {1,2}} 9 jumpx = [-1, 1, -2, 2, -2, 2, -1, 1] 10 jumpy = [-2, -2, -1, -1, 1, 1, 2, 2] 11 ) 12 13 // Main 14 fn main() { 15 println('Hello, Jumper!') 16 17 sizex := 6 18 sizey := 5 19 20 mut board := [0].repeat(sizex * sizey) 21 22 solutions, roundtrips := jumpto(mut board, sizex, sizey, 0, 0, 1, 0, 0) 23 24 println('===== Solutions:$solutions - Roundtripps:$roundtrips ====== ') 25 println('I am done.') 26 } 27 28 29 // Jump to a new postion 30 fn jumpto(mut board []int, sizex int, sizey int, x int, y int, iter_in int, solutions_in int, roundtrips_in int) (int, int) { 31 32 mut solutions := solutions_in 33 mut roundtrips := roundtrips_in 34 mut iter := iter_in 35 36 // store position 37 // board_set(mut board, sizex, sizey, x, y, iter) 38 board[x + y * sizex] = iter 39 40 // check if finished 41 mut round := false 42 if iter == sizex * sizey { 43 for i, jx in jumpx { 44 nx := x + jx 45 ny := y + jumpy[i] 46 47 // new position still on board 48 if nx<0 || nx>(sizex-1) || ny<0 || ny>(sizey-1) { continue } 49 50 // check for roundtrips 51 if board[nx + ny * sizex] == 1 { 52 round = true 53 roundtrips++ 54 print_board(board, sizex, sizey, round, iter, solutions, roundtrips) 55 break 56 } 57 } 58 59 board[x + y * sizex] = 0 60 return solutions + 1, roundtrips 61 } 62 63 // try next jump 64 iter++ 65 for i, jx in jumpx { 66 nx := x + jx 67 ny := y + jumpy[i] 68 69 // new position still on board 70 if nx<0 || nx>(sizex-1) || ny<0 || ny>(sizey-1) { continue } 71 72 // check if new position is empty and jump to it 73 if board[nx + ny * sizex] == 0 { 74 solutions, roundtrips = jumpto(mut board, sizex, sizey, nx, ny, iter, solutions, roundtrips) 75 } 76 } 77 78 board[x + y * sizex] = 0 79 return solutions, roundtrips 80 }
For this project I just used the V native compilation (development build) and the trans-compilation to C (production build). The native compilation takes about double the time of the C version. The C based binary is as fast as the native C program.
Would I use it? When V becomes a little more mature, the answer is a veritable "Yes". The downside is, that it is currently not nearly as popular as Go or Rust.
Here is a short german article about V on Heise: V eine neue Programmiersprache betritt die Open Source Bühne
Around 1983 when I was a teenager I heard rumors about Forth and that it should be faster than assembler. Of course I knew that can't be possible but I was curious. So I bought a tape with an Forth implementation for Sharp MZ-700. But I only played around with it a little bit.
Now and then Forth pops up and stood on my mind. On the Open Rhein Ruhr 2019 I visited a booth where they used Forth to program microcontrollers. And during DIVOC - Hidden Service 2020 was an introduction talk to Forth I saw.
So I thought it will popup anyway in my live and I just have to give it a try. I decided to use Gforth.
This project was like a puzzle game to me. You have to remember a lot and fiddle out how it works together.
Forth has a REPL
where you can use it interactively,
but you define something new it will be immediately compiled.
A disgusting thing was, that the word char does only work interactive, not compiled.
For compilation [char] has to be used.
Forth uses a stack to hand over parameters to functions (called words in Forth). So far this is the way most programming languages work. But instead of using this parameters as variables you directly modify the stack. The same is true for returning parameters. So you have to take care to consume all parameters from the stack and to give back the exact returning values under any condition of your word. In other languages your function might ignore parameters in certain conditions, in Forth you have to handle with this.
Forth's stack uses native CPU words. This are 8 bytes on an 64bit machine. In the Go version I made a change to use smaller number types which increased performance. This I didn't try in Forth and which might gain performance increase as well.
Sorry, no syntax highlighting here.
A / is a comment to the end of the line.
A ( ... ) is a block comment, mostly used to describe
the expected stack input and after two dashes -- the output.
Source of jumpsaround_1.4th: view, download
4 6 constant SIZEX 5 5 constant SIZEY 6 7 \ init the possible 8 moves for a night 8 : init-jump ( n7..n0 a -- ) 8 0 ?do dup rot swap i cells + ! loop drop ; 9 variable jumpx 8 cells allot 10 1 -1 2 -2 2 -2 1 -1 jumpx init-jump 11 variable jumpy 8 cells allot 12 2 2 1 1 -1 -1 -2 -2 jumpy init-jump 13 \ display jumpto coordinates, only for needed testing 14 : jump-show ( -- ) 8 0 ?do ." {" jumpx i cells + @ . ." ," jumpy i cells + @ . ." }" loop cr ; 15 16 \ define and init more variables 17 variable board SIZEX SIZEY * cells allot board SIZEX SIZEY * cells erase 18 variable iters SIZEX SIZEY * cells allot iters SIZEX SIZEY * cells 0 fill 19 variable solutions 0 solutions ! 20 variable roundtrips 0 roundtrips ! 21 variable isroundtrip false isroundtrip ! 22 23 : board-get ( x y -- n ) SIZEX * + cells board + @ ; 24 : board-set ( n x y -- ) SIZEX * + cells board + ! ; 25 26 \ print board 27 : printboard ( -- ) 28 ." ===== Solution #" solutions @ . ." - Roundtripps:" roundtrips @ . ." ====== " 29 isroundtrip @ if ." *** Roundtrip ***" endif cr 30 SIZEY 0 ?do 31 SIZEX 0 ?do 32 i j board-get dup 10 < if space endif . [char] : emit 33 loop cr 34 loop cr ; 35 36 \ jump to 37 : jumpto ( nx ny ni -- ) 38 dup 2over board-set \ store position ( nx ny ni ) 39 \ finished? 40 dup SIZEX SIZEY * >= if \ finished ? 41 8 0 ?do 42 jumpx i cells + @ 3 pick + \ ( nx ny ni nx2 ) 43 jumpy i cells + @ 3 pick + \ ( nx ny ni nx2 ny2) 44 \ check if the new position is on the board 45 dup 0 >= over sizey < and 46 2 pick 47 dup 0 >= swap sizex < and and if 48 \ detect roundtrip 49 board-get 1 = if 1 roundtrips +! true isroundtrip ! leave then \ ( nx ny ni b ) 50 else 2drop 51 then \ btw "then" and "endif" are the same ;) 52 loop 53 1 solutions +! 54 printboard \ ( nx ny ) 55 else \ try next jump 56 8 0 ?do 57 jumpx i cells + @ 3 pick + \ ( nx ny ni nx2 ) 58 jumpy i cells + @ 3 pick + \ ( nx ny ni nx2 ny2) 59 \ ." i=" i . .s cr \ test 60 \ check if the new position is on the board 61 dup 0 >= over sizey < and 62 2 pick 63 dup 0 >= swap sizex < and and if 64 \ check if new field position is still empty 65 2dup board-get 0 = 66 if 2 pick 1+ 67 recurse 68 else 2drop 69 then \ ( nx ny ni ) 70 else 2drop 71 then \ btw "then" and "endif" are the same ;) 72 loop 73 then 74 drop \ ( nx ny ni -- nx ny ) 75 0 -rot board-set ; \ ( nx ny -- ) 76 77 \ main 78 cr 79 ." Hello, Jumper!" cr 80 0 0 1 jumpto 81 ." I am done" cr 82 bye
The first Forth version of jumpsaround is also a more or less 1:1 translation from the C version.
In this case the jumpto word has many lines.
In Forth it is more idiomatic to split up the code in to words just having just a few lines.
That way it is much easier to debug code an get the stack right.
For the second version I refactored some parts into smaller words. This has just a minor performance impact.
Source of jumpsaround_2.4th: view, download
36 : roundtrip? ( nx ny -- ) 37 board-get 1 = 38 if 1 roundtrips +! true isroundtrip ! 39 then ; 40 41 : position-on-board? ( nx ny -- nx ny b ) 42 dup 0 >= ( nx ny b ) 43 over sizey < ( nx ny b b ) 44 and ( nx ny b ) 45 2 pick ( nx ny b nx ) 46 dup 0 >= ( nx ny b nx b ) 47 swap sizex < ( nx ny b b b ) 48 and and ; ( nx ny b ) 49 50 \ jump to 51 : jumpto ( nx ny ni -- ) 52 dup 2over board-set \ store position ( nx ny ni ) 53 \ finished? 54 dup SIZEX SIZEY * >= if \ finished? 55 false isroundtrip ! 56 8 0 ?do 57 jumpx i cells + @ 3 pick + \ ( nx ny ni nx2 ) 58 jumpy i cells + @ 3 pick + \ ( nx ny ni nx2 ny2) 59 \ check if the new position is on the board 60 position-on-board? 61 if roundtrip? isroundtrip @ if leave endif 62 else 2drop 63 then \ btw "then" and "endif" are the same ;) 64 loop 65 1 solutions +! 66 printboard \ ( nx ny ) 67 else \ try next jump
Forth is a very low level programming language like C where directly manipulate pointers for memory access. So it is easy to shoot yourself in the foot.
Would I use Forth for future projects? I don't think I would do so for larger projects. Maybe just for fun or for programming micro controllers like an Adruino.
About the speed. At least for gforth I can tell that it is around 10 times slower than the basic C version. So I am a little disappointed with the speed of this language. I think that the reason for this, that every word is looked up in a directory, because you can (re)define words during runtime. In "normal" compiled languages the address of the function is known and can be called immediately.
After I finished my work on Forth heise online published a (german) article about Forth: Forth – die ewig junge Programmiersprache
Everybody loves Python!? At least it is very popular. So let's take a look.
Python is an interpreted language. It claims to be very easy. I think it is easy, but there are other languages - like Go - which are also that "easy".
Source of jumpsaround.py: view, download
8 jump = ((-1,-2), (1,-2), (-2,-1), (2,-1), (-2,1), (2,1), (-1,2), (1,2)) 9 10 # init board 11 board = [] 12 for i in range(SIZEX): 13 col = [] 14 for i in range(SIZEY): 15 col.append(0) 16 board.append(col) 17 18 solutions = 0 19 roundtrips = 0 20 21 def jumpto(x, y, iter): 22 global solutions 23 global roundtrips 24 global board 25 26 board[x][y] = iter 27 28 # finished? 29 if iter >= SIZEX * SIZEY: 30 # check for roundtrips 31 round = 0 32 for np in jump: 33 nx = x + np[0] 34 ny = y + np[1] 35 # check if position is on the board 36 if nx < 0 or nx > (SIZEX-1) or ny < 0 or ny > (SIZEY-1): 37 continue 38 # detect roundtrip 39 if board[nx][ny] == 1: 40 round = True 41 roundtrips += 1 42 break 43 solutions += 1 44 printboard(round) 45 board[x][y] = 0 46 return 47 48 # try next jump 49 for np in jump: 50 nx = x + np[0] 51 ny = y + np[1] 52 # check if position is on the board 53 if nx < 0 or nx > (SIZEX-1) or ny < 0 or ny > (SIZEY-1): 54 continue 55 # check if new field position is still empty 56 if board[nx][ny] != 0: 57 continue 58 jumpto(nx, ny, iter + 1) 59 board[x][y] = 0
What is noticeable is that there are no parentheses or begin-end blocks to structure code. Blocks such as loop bodies or conditional executions are only structured using indentation. This gives a novice programmer practice in formatting code cleanly and looks nice. But this has also the disadvantage that when moving code to another structural level you have to manually correct your indentation. For many other languages, that use brackets for structuring code, you have formatter available which can fix this for you.
The Python solution is 34 times slower than C and nearly 100 times slower than the parallel Go version.
If there is no need to use Python, I would prefer Go.
There are ways to speed up Python. I checked out two of the popular options.
First I tried Cython.
Cython transpiles Python code to C which you have to compile with gcc.
This can be run independently
or be used as C-modules in a regular Python program like numpy.
Even if it is compiled it still interprets the code.
You can add static types to your Python code,
this might speed up your program but then it's not Python anymore.
I didn't try this.
The performance of the cython version, with gcc compiled with the -O2
optimizer flag, needed less than half the time of the native Python version.
Nice.
Without the -O2 flag it was even slower than the native Python version.
The second option I tried was PyPy. PyPy is a just in time compiler. Jumpsaround runs with pypy3 8 times faster than the native Python version. That's an impressive speedup. But PyPy has the disadvantage that including of C modules does not work or incurs some overhead. Source Wikipedia on PyPy.
Javascript is a must to be looked at. Starting as a way to create active web sites it's now everywhere. With Node.js its powering servers and with Electron javascript now is used for frontend development as well.
For my program I use Node.js as the runtime. Node.js uses the V8 JavaScript engine which is also used in the Chrome browser.
The syntax is like C. if you remove type definitions and replace it with "var" or "function" when appropriate your mostly done. (Of course C library functions are not the same.)
Source of jumpsaround_1.js: view, download
7 const jump = [[-1, -2], [1, -2], [-2, -1], [2, -1], [-2, 1], [2, 1], [-1, 2], [1, 2]]; 8 9 let board = new Array; 10 let solutions = 0; 11 let roundtrips = 0; 12 13 14 function main() { 15 console.log("Hello, Jumper!\n"); 16 17 // init 18 for (i = 0; i < SIZEX; i++) { 19 board[i] = []; // same as "new Array" 20 for (j = 0; j < SIZEY; j++) { 21 board[i][j] = 0; 22 } 23 } 24 jumpto(0, 0, 1, 0); 25 console.log("I am done."); 26 return 0; 27 } 28 29 30 function jumpto(x, y, iter) { 31 32 // ok - store position 33 board[x][y] = iter; 34 35 // finished ? 36 if (iter >= SIZEX*SIZEY ) { 37 // check for jumper roundtrips 38 var round = false; 39 for (var i = 0; i < 8; i++) { 40 nx = x + jump[i][0]; 41 ny = y + jump[i][1]; 42 // check if position is on the board 43 if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue; 44 // detect roundtrip 45 if ( board[nx][ny] == 1 ) { round = true; roundtrips++; break; } // True 46 } 47 solutions++; 48 if(round) printboard(round); 49 board[x][y] = 0; 50 return; 51 } 52 53 // try next jump 54 for (i = 0; i < 8; i++) { 55 // new position 56 nx = x + jump[i][0]; 57 ny = y + jump[i][1]; 58 // check if new position is on the board 59 if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue; 60 // check if new field position is still empty 61 if ( board[nx][ny] != 0 ) continue; 62 jumpto(nx, ny, iter + 1, i); 63 } 64 65 // this iteration is done 66 board[x][y] = 0; 67 }
Javascript is fascinating fast. Even if Javascript is a scripting language it's compiled wherever possible. The compiled code is extremely fast. jumpsaround can be optimised very well. We can see that during the browser wars Millons of $ have bee pured into the development of fast javascript engines. In this case here the Node.js version just takes 30% more time than the C version. For a basically interpreted language, this is an impressive result.
With javascript you get the ease of a scripting language and the power of a compiled language.
What I dislike is that the language is not type save and uses implicit type conversion.
For example you have three variables a = 3; b = 2; c = 1; and compare them
with a >= b >= c - which is valid code - the result ist true. Good, isn't it?
Now change the values of the variables to a = 4; b = 3; c = 2;.
in this case the result is false. Why?
The explanation is, that first 4 >= 3 will evaluate to true.
In the comparison of true >= 2, true will be automatically be converted to
a number. true becomes 1. So the second part of the comparison is 1 >= 2.
This was ok for our first test.
Libraries often use objects as parameters. If you misspelled an attribute the
language won't warn you and it's sometimes hard to find the problem.
Here an example. You define a person Object p = { name: "Peter", birth: 1990 }.
And later you want to know if the person is born before 2000 with p.born < 2000
this will evaluate to true. There is no error that p.born was not declared.
Ouch!
There are many more of this pitfalls in Javascript, you wont recognize when you start programming with javascript, but you probably will unexpected behavior. That's a pain!
But today there are languages like TypeScript or Dart (and several more) which transcompiles to javascript and compensate those issues. Transcompiling (or shorter transpiling), on the other hand, gives you another layer of complexity that introduces new problems.
If possible, I would try to avoid Javascript and stick with Go. 😉
Performance was measured by just running time $Program.
| Language | Version | Program | Feature | LoC | X250* | X250* |
|---|---|---|---|---|---|---|
| C (gcc) | 10.1.0 | jumpsaround_0.c | jump dest. checked at beginning of func. | 62 | 7,62s | 7,62s |
| C (gcc) | 10.1.0 | jumpsaround_1.c | jump dest. checked before recursive call | 62 | 5,52s | 5,52s |
| C (gcc -O2) | 10.2.0 | jumpsaround_1.c | optimizer activated (same code as before) | 62 | 1,67s | 1,67s |
| Go | 1.15 | jumosaround_1.go | single thread, using type inference/int | 66 | 4,24s | 4,24s |
| Go | 1.15 | jumosaround_2.go | single thread, using int32 | 52 | 3,97s | 3,97s |
| Go | 1.15 | jumosaround_3.go | spawn each recursion in new thread - bad idea | 59 | 21,45s | 21,45s |
| Go | 1.15 | jumosaround_4.go | spawn new thread in 2nd iteration | 68 | 1,87s | 1,87s |
| Racket (comp.) | 7.8 | jumpsaround.rkt | (Scheme) compiled | 59 | 28,18s | 28,18s |
| Racket (intera.) | 7.8 | jumpsaround.rkt | interactive DrRacket | 59 | 2m 20,90s | 140,90s |
| Guile (Scheme) | 2.2.6 | jumpsaround.scm | 59 | 2m 6,00s | 126,00s | |
| V (dev=own comp.) | 0.129 | jumpsaround_2.v | no globals allowed, whole context as param. | 60 | 11,96s | 11,96s |
| V (prod=via C) | 0.129 | jumpsaround_2.v | no globals allowed, whole context as param. | 60 | 3,75s | 3,75s |
| Forth (Gforth) | 0.7.9 | jumpsaround_1.4th | 61 | 51,32s | 51,32s | |
| Forth (Gforth) | 0.7.9 | jumpsaround_2.4th | slightly more modularized | 70 | 53,62s | 53,62s |
| Python | 3.8.5 | jumpsaround.py | 53 | 3m 0,89s | 180,89s | |
| Python (cython3 -3) | 0.29.21 | jumpsaround.pyx | keine Cython type annotation, gcc | 53 | 3m 40.93s | 220,93s |
| Python (cython3 -3) | 0.29.21 | jumpsaround.pyx | keine Cython type annotation, gcc -O2 | 53 | 1m 18,85s | 78,85s |
| Python (PyPy) | 7.3.3 | jumpsaround.py | 53 | 22,02s | 22,02s | |
| Javascript (Node.js) | 14.8.0 | jumpsaround_1.js | 57 | 7,18s | 7,18s | |
| Ruby | 2.7.2 | jumpsaround_1.rb | 2m 6,69s | 126,69s | ||
| Crystal | 1.0.0 | jumpsaround_1.cr | build time 1,7s | 47,09s | 47,09s | |
| Crystal (release) | 1.0.0 | jumpsaround_1.cr | (crystal build --release) build time 16,58s (LLVM 10.0.0) | 4,16s | 4,16s |
* The X250 has an Intel i5-5300U (2 cores/4 threads) 2.90GHz CPU.
Keep in mind, this timings are only valid for this type of algorithm. For other situations, the performance of the languages will differ.
LoC = Lines of Code. There is noc significant difference. The number of code-lines are more dependent of writing, like writing a simple clause in same line as the condition.
In the beginning I mentioned, that I use a 6x5 sized board for the tests. What time would it take on slightly larger boards? Here are some results calculated with the jumosaround_4.go version on a faster machine with an Intel Core i7-8700T (6 cores/12 threads) 4GHz CPU.
| Size | h:mm:ss.s | Factor | Roundtrips |
|---|---|---|---|
| 6x5 | 00:00.5 | 1 | 16 |
| 6x6 | 01:45.0 | 210 | 19724 |
| 6x7 | 6:11:55.0 | 44.630 | m( |
I didn't try a larger board. No need to burn several days long energy for this. ;)
Maybe I'll do the implementation of Jumpsaround in one of those languages as well.
This website can be found at kulbartsch.de/jumper
The last update of this page: 2021-07-02
Release: Version 1.2
Write me an email if you have any comments to: a-jumper àt alice-and-bob·de
Many thanks to all the people who supported me and gave me feedback for this website and the corresponding presentation.
This Website has been hand crafted with aswsg, my static website generator.
All source code on this page is licensed under the GPLv3 - GNU GENERAL PUBLIC LICENSE Version 3.
Syntax highlighting is done with highlight.
The design of this website and the logo on the top of the page follows the design of the 2020s remote Chaos experience (rC3) - as an homage to this online congress and for fun. The logo was made with the help of the rC3 logo generator from bleeptrack.
Here you'll find my homepage kulbartsch.de.
