Help please – Python vs. Julia for depth-first peg solitaire – how can this be made faster in Python? /u/ExperimentalWatchman Python Education

Hi – Peg solitaire (also called Brainvita) is an interesting game which can be solved using depth-first search. This is the game: https://en.wikipedia.org/wiki/Peg_solitaire

I recently wrote some code in Julia to solve this – and it runs really fast, solving the board in 0.03s. About 75-ish LOC. Here it is:

https://pastebin.com/fKt8mbzg

Result (in Julia):

solitaire = [ 8 8 1 1 1 8 8; 8 8 1 1 1 8 8; 1 1 1 1 1 1 1; 1 1 1 0 1 1 1; 1 1 1 1 1 1 1; 8 8 1 1 1 8 8; 8 8 1 1 1 8 8;
]

@time history = solve(solitaire, 1); No. of moves made to find this: 26846

0.028026 seconds (244.48 k allocations: 51.126 MiB, 9.58% gc time)

Now I decided to port this to Python – and I admit I’m no expert in Python. Just because I’m learning Python, and I like it a lot.

My code translation is not the best – I tried to keep it close to the Julia implementation in the first go. Here is the Python code (uses a bit of Numpy for the matrices):

https://pastebin.com/a2VZWXS0

Some changes are: 1/ Converted numpy arrays to str before putting them in a set() for easy lookup (mutable arrays are not hashable in Python). 2/ Small changes to account for the 0- and 1- based indexing between Python and Julia, respectively.

Otherwise the code is pretty much exactly the same.

Result in Python:

solitaire = np.array([ [8, 8, 1, 1, 1, 8, 8], [8, 8, 1, 1, 1, 8, 8], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [8, 8, 1, 1, 1, 8, 8], [8, 8, 1, 1, 1, 8, 8]
])

%timeit history = solve(solitaire, 1);

7.58 s ± 43.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

That’s a lot slower in Python – about 270x slower. This doesn’t make sense to me. Can someone please help me to make this faster?

Please note my intention is only to get better at Python – nothing else. So please refrain from commenting on Julia vs. Python etc.

Many thanks for any help!

Hi – Peg solitaire (also called Brainvita) is an interesting game which can be solved using depth-first search. This is the game: https://en.wikipedia.org/wiki/Peg_solitaire

I recently wrote some code in Julia to solve this – and it runs really fast, solving the board in 0.03s. About 75-ish LOC. Here it is:

https://pastebin.com/fKt8mbzg

Result (in Julia):

solitaire = [ 8 8 1 1 1 8 8; 8 8 1 1 1 8 8; 1 1 1 1 1 1 1; 1 1 1 0 1 1 1; 1 1 1 1 1 1 1; 8 8 1 1 1 8 8; 8 8 1 1 1 8 8;
]

@time history = solve(solitaire, 1); No. of moves made to find this: 26846

0.028026 seconds (244.48 k allocations: 51.126 MiB, 9.58% gc time)

Now I decided to port this to Python – and I admit I’m no expert in Python. Just because I’m learning Python, and I like it a lot.

My code translation is not the best – I tried to keep it close to the Julia implementation in the first go. Here is the Python code (uses a bit of Numpy for the matrices):

https://pastebin.com/a2VZWXS0

Some changes are: 1/ Converted numpy arrays to str before putting them in a set() for easy lookup (mutable arrays are not hashable in Python). 2/ Small changes to account for the 0- and 1- based indexing between Python and Julia, respectively.

Otherwise the code is pretty much exactly the same.

Result in Python:

solitaire = np.array([ [8, 8, 1, 1, 1, 8, 8], [8, 8, 1, 1, 1, 8, 8], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [8, 8, 1, 1, 1, 8, 8], [8, 8, 1, 1, 1, 8, 8]
])

%timeit history = solve(solitaire, 1);

7.58 s ± 43.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

That’s a lot slower in Python – about 270x slower. This doesn’t make sense to me. Can someone please help me to make this faster?

Please note my intention is only to get better at Python – nothing else. So please refrain from commenting on Julia vs. Python etc.

Many thanks for any help!