The data would be the same, but you'd avoid the overhead of copying all the extra lists.įor option 2, you'd want to use one board and keep track of what you're changing (and, depending on your implementation, perhaps exactly one copy of the board you never change). Two options occur to me: either look for a simpler board representation that is cheaper and easier to copy, or try to avoid the copies.įor option 1, the obvious simpler thing is a flat list or tuple with sixteen elements, which you then index into as. That is genuine time expenditure, and a good place to start hitting. Instead, a huge amount of time is spent within deepcopy: 27 of 32 seconds. The first few lines are just the call sequence in: for example there's a lot of time (cumtime) spent in find_words but almost all of it is in functions that it's calling and very little in the function directly (tottime). Ncalls tottime percall cumtime percall filename:lineno(function)ġ 0.000 0.000 32.455 32.455 python -m cProfile -s cumtime boggle.pyġ16983186 function calls (93930898 primitive calls) in 32.455 seconds I went with my internal clock, when what I should do is use a tool. Of course, I've been a bit naughty there. After all, even if we could make dictionary_check take no time at all, the program would take almost as long to run! That immediately tells me that it's not worth looking for faster ways to do the dictionary_check until get_permutations is much faster. Running the program, I immediately noticed that the get_permutations section was slow, and the dictionary_check section was many times faster. The problem that you observe with this program is speed, so let's look at that. Set_permutations = get_permutations(board)

With open('en-dict.txt', 'r', encoding='utf8') as file: '''Check set_permutations for valid English words''' Words = words_from(board, row, column, list_words=) Words_from(new_board, row + dx, column + dy, new_string, list_words) '''Calculate all possible words from a given starting position ''' The dictionary is from here '''Boggle game solver'''ĭef words_from(board, row, column, running_string='', list_words=): Please can you comment on general style improvements and if you can think of another method to solve this game, a hint as to what I should do for my next attempt. I had to limit word length to 8 otherwise it takes far too long. The problem with my solution is it is very slow. Letters may not be re-used.īelow is a recursive solution to the boggle board. Letters may connect diagonally, vertically or horizontally.Įxample words on the above board are 'son', lad' and 'land'. Words can be started from any letter and are formed by finding a sequence of connecting letters. `Boggle is a word game in which letters are randomly placed in a 4x4 grid

Boggle supreme license name code