StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>EDIT:</strong></p> <p>There are two solutions I've come up with: one based on convolution (using the function <a href="http://www.mathworks.com/help/techdoc/ref/conv2.html" rel="nofollow noreferrer">CONV2</a>) and one based on brute-force indexing for all possible strings of 5 elements (similar to <a href="https://stackoverflow.com/questions/5177758/winners-on-a-pentago-board/5186524#5186524">b3's newer answer</a>). Here they are:</p> <p><em>Convolution:</em></p> <pre><code>function winner = pentago_winner_conv(board) %# Input should be a 6-by-6 matrix with: %# - 0 for an empty space %# - 1 for pieces from one player %# - -1 for pieces from the other player %# The return value is 0 for no winner, -1 or 1 for the winning player, %# or 2 if there is a draw. metric = [conv2(board,ones(1,5),'same') ... %# Check horizontal strings conv2(board,ones(5,1),'same') ... %# Check vertical strings conv2(board,eye(5),'same') ... %# Check diagonal strings conv2(board,fliplr(eye(5)),'same')]; %# Check anti-diagonal strings limits = [min(metric(:)) max(metric(:))]; %# Find the min and max values limits = fix(limits/5); %# Convert them to -1, 0, or 1 if all(limits) winner = 2; %# A draw condition else winner = sum(limits); %# Find the winner, if any end end </code></pre> <p><em>Indexing:</em></p> <pre><code>function winner = pentago_winner_brute(board) %# Input should be a 6-by-6 matrix with: %# - 0 for an empty space %# - 1 for pieces from one player %# - -1 for pieces from the other player %# The return value is 0 for no winner, -1 or 1 for the winning player, %# or 2 if there is a draw. index = reshape(1:36,6,6); index = [index(1:5,:).'; index(2:6,:).'; ... %# Vertical string indices index(:,1:5); index(:,2:6); ... %# Horizontal string indices 1:7:29; 2:7:30; 7:7:35; 8:7:36; ... %# Diagonal string indices 5:5:25; 6:5:26; 11:5:31; 12:5:32]; %# Anti-diagonal string indices metric = sum(board(index),2); limits = [min(metric) max(metric)]; %# Find the min and max values limits = fix(limits/5); %# Convert them to -1, 0, or 1 if all(limits) winner = 2; %# A draw condition else winner = sum(limits); %# Find the winner, if any end end </code></pre> <p>Out of curiosity, I thought I'd measure the speed and accuracy of these solutions versus <a href="https://stackoverflow.com/questions/5177758/winners-on-a-pentago-board/5186524#5186524">b3's newer answer</a>. I created 4 test boards: -1 wins, no winner, 1 wins, both win (draw). Then I ran each solution 10,000 times for each board and timed them. Here are the results:</p> <pre><code> | Calculated winner ---------------+----------------------- convolution | -1 0 1 2 indexing | -1 0 1 2 b3 solution | -1 0 1 -1 | Running time for 10,000x (seconds) ---------------+--------------------------------------- convolution | 0.4863 0.5305 0.5248 0.4787 indexing | 0.1706 0.1770 0.1755 0.1889 b3 solution | 0.6607 1.3958 1.4223 0.7507 </code></pre> <p>Note that b3's solution fails to detect a draw. Even though the code for the convolution-based solution was the shortest and easiest to implement (I didn't have to create a list of indices by hand), the indexing solution I give above ends up being the fastest.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload