This assignment requires familiarity with the lecture materials presented in class through week 07.
The animations below show words found in a word-search grid by traveling sequences of adjacent grid squares in any horizontal, vertical, or diagonal direction.
<html> <style> @keyframes fadeInLoad {
from { opacity:0; } to { opacity:1; }
} .grid {
font-family: monospace; text-align: center;
} .gridtable {
margin-left: auto; margin-right: auto;
} .path {
font-weight: bold;
} </style> <center>
<p id=“grid-word” class=“grid path” style=“font-size: 2em;”></p>
</center> <script> let paths;
function shuffle(array) {
let currentIndex = array.length, randomIndex; while (currentIndex != 0) { randomIndex = Math.floor(Math.random() * currentIndex); currentIndex--; [array[currentIndex], array[randomIndex]] = [ array[randomIndex], array[currentIndex]]; } return array;
}
async function loadGridData() {
return await window.fetch('/datasets/grids/words-20', { method: 'get' }).then(response => response.json() ).then(json => { paths = json; shuffle(paths); }).catch(err => { console.log('Something bad happened: ' + err); });
}
let pathIndex = 0; function displayNextWord() {
let div = document.getElementById('grid'); while (div.firstChild) div.removeChild(div.firstChild); let grid = document.createElement('table'); grid.classList.add('gridtable'); let word = paths[pathIndex].word; let path = paths[pathIndex].path; window.fetch('/datasets/grids/grid-20', { method: 'get' }).then(response => response.text() ).then(text => { let lines = text.split('\n'); grid.style.fontSize = `${20 / lines[0].length}em`; for (let i = 0; i < lines.length; ++i) { let line = lines[i].split(''); let row = document.createElement('tr'); for (let j = 0; j < line.length; ++j) { let col = document.createElement('td'); col.textContent = line[j]; for (let k = 0; k < path.length; ++k) { if (path[k][0] == i && path[k][1] == j) { let hue = Math.round(k / (path.length - 1) * 270); col.classList.add('path'); col.setAttribute('style', `animation: fadeInLoad ${k + 1}s; background-color: hsl(${hue}, 60%, 75%)`); } } row.appendChild(col); } grid.appendChild(row); } }).catch(err => { console.log('Something bad happened: ' + err); }); div.appendChild(grid); div = document.getElementById('grid-word'); while (div.firstChild) div.removeChild(div.firstChild); for (let i = 0; i < word.length; ++i) { let hue = Math.round(i / (path.length - 1) * 270); let letter = document.createElement('span'); letter.setAttribute('style', `animation: fadeInLoad ${i + 1}s; background-color: hsl(${hue}, 60%, 75%)`); letter.textContent = word[i]; div.appendChild(letter); }
window.setTimeout(displayNextWord, word.length * 1000 + 1000); pathIndex = (pathIndex + 1) % paths.length;
}
loadGridData().then(result ⇒ { displayNextWord(); }); </script> </html>
You shall write a Python 3 program that reads a word-search grid from standard input, and prints all valid words in the grid to standard output. Specifically:
cs20p_word_search
as the name the module intended to be run as __main__
.
FYI, no need to overcomplicate this. My straightforward/unoptimized solution is 19 lines of code, as measured by sloccount
.
Make sure that you choose an approach with appropriate data types and algorithms so that the time complexity of your solution is:
8
for a 10×10
grid with a minimum length of 2
)Two sample executables are available on the server:
cs20p_word_search_gen
creates grids compatible with your program.n
: The dimension of the grid (i.e. output will consist n
lines, each of which has length n
)min_length
: The minimum length of a valid worddict_file
: A path to the same kind of dictionary file your program expects.cs20p_word_search
demonstrates the expected behavior of your program.
For example, try running cs20p_word_search_gen
to create a 10×10 grid using words at least 5 letters long from /usr/share/dict/american-english
, redirecting standard output to file test_grid
and standard error to file test_words
:
cs20p_word_search_gen 10 5 /usr/share/dict/american-english >test_grid 2>test_words
The contents of the two files will then be something like the following
$ cat test_grid ATSANACHZF UGALLAGHER JSSERYPGAS DRFPMQNMVR UEVHREFYEK BDJXIOBWRE ARZSPWMRRN IASPHHWOEI PWLGWKNSDR ALISTAIRTB
$ cat test_words ALISTAIR AVERRED BRINE CANASTA DUBAI GALLAGHER GNEISS PROMO PYRES WARDERS
You could then run cs20p_word_search
and your own program to verify that the output matches:
$ cs20p_word_search 5 /usr/share/dict/american-english <test_grid ALISTAIR AVERRED BRINE CANASTA DRAWL DUBAI ERRED GALLAGHER GNEISS PROMO PYRES REDRAW STAIR WARDER WARDERS
You could also automate some testing with diff
, to lessen the amount of typing. The following consists of two commands, the first of which generates a grid in file test_grid
, and the second of which runs diff
to compare your output with the expected output. Lines only in the expected output are prefixed with -
, and lines only in your output are prefixed with +
:
DIM=5 LEN=2 DICT=/usr/share/dict/american-english bash -c ' cs20p_word_search_gen $DIM $LEN $DICT >test_grid 2>/dev/null; diff -u <(cs20p_word_search $LEN $DICT <test_grid) \ <(python cs20p_word_search.py $LEN $DICT <test_grid) '
As submissions are received, this leaderboard will be updated with the top-performing solutions that are fully functional in at least 90% of tests.
<html>
<table> <thead> <tr><th>Rank</th><th>Average Test Time</th><th>Average Memory Usage (kB)</th><th>SLOC (lines)</th><th>User</th></tr> </thead> <tbody id=“leaderboard-table”> </tbody> </table> <script> function updateLeaderboard() { window.fetch('/~turnin/leaderboard-cs20ps23as07.txt', {
method: 'get'
}).then(response ⇒
response.text()
).then(text ⇒ {
let updated = document.getElementById('leaderboard-updated'); updated.innerText = `(Last updated: ${new Date()})`; let lines = text.split('\n'); let table = document.getElementById('leaderboard-table'); while (table.firstChild) table.removeChild(table.firstChild); for (let i = 0; i < lines.length; ++i) { let tokens = lines[i].split(' ').filter(token => token.length > 0); if (tokens.length < 2) continue; let tdRank = document.createElement('td'); tdRank.textContent = i + 1; let tdTime = document.createElement('td'); tdTime.textContent = Number(tokens[0]).toFixed(4); let tdMemUsage = document.createElement('td'); tdMemUsage.textContent = tokens[1]; let tdSloc = document.createElement('td'); tdSloc.textContent = tokens[2]; let tdUser = document.createElement('td'); let userLink = document.createElement('a'); userLink.href = `/~${tokens[3]}/`; userLink.target = '_blank'; userLink.textContent = tokens[3]; tdUser.appendChild(userLink); let tr = document.createElement('tr'); tr.appendChild(tdRank); tr.appendChild(tdTime); tr.appendChild(tdMemUsage); tr.appendChild(tdSloc); tr.appendChild(tdUser); table.appendChild(tr); }
}).catch(err ⇒ {
console.log('Something bad happened: ' + err);
});
window.setTimeout(updateLeaderboard, 60000);
} updateLeaderboard(); </script> </html>
Submit cs20p_word_search.py
(and any other source-code file(s), if you write multiple modules) via turnin.
Feedback Robot
This project has a feedback robot that will run some tests on your submission and provide you with a feedback report via email within roughly one minute.
Please read the feedback carefully.
Due at 23:59:59 on the date listed on the syllabus.
Assignment 07
is worth 60 points.
Possible point values per category: --------------------------------------- Correct output 30 Acceptable time complexity 30 Possible deductions: Style and practices 10–20% Possible extra credit: Submission via Git 5% ---------------------------------------