Request Feedback on Test

[Christopher J. Pisz]

Seems to be a pretty standard interview screening test. I Googled it
after the fact and it pops up with a page of hits. Everyone seemed to
pretty much do what I did, yet I have been told mine performs like poop
compared to other candidates. I can't get any feedback on why it might
perform like poop or what could be done better.

Can you guys give your suggestions?
http://github.com/ChristopherPisz/Asking-for-Peer-Review/tree/master/Boggle

I did a depth first search and compared the path thus far with words in
the dictionary using a Radix Trei. I don't know of any other possible
algorithm to solve the problem, or how I would implement it "better."

C++ is getting REALLY performance orientated. I used to get a job within
2 days just by knowing what virtual inheritance is. Now, I don't really
know how to "Get better"

[Paavo Helde]

From a quick glance from your code I would say there is massive
overengineering in the Dictionary area. For finding words matching a
prefix one can just store them in a std::set and use
std::set::lower_bound(), no need to build complex hierarchies of classes.

I also see you have used std::upper_bound() on a pair of std::set
iterators, this is probably the most counter-performance thing there.
There is a reason why std::set has lower_bound() and upper_bound() as
member functions.

You also need to learn about std::string::compare(), I see things like
that in your code:

if ((*itChild)->m_value.substr(0, wordPart.size()) == wordPart) ...

Yes, C++ is a lot about performance nowadays, if there is no need for
performance the thing could be often programmed much more easily in some
scripting language.

Cheers
Paavo

[Christopher J. Pisz]

On 2/9/2017 4:06 PM, Paavo Helde wrote:
> On 9.02.2017 22:08, Christopher J. Pisz wrote:
>> Seems to be a pretty standard interview screening test. I Googled it
>> after the fact and it pops up with a page of hits. Everyone seemed to
>> pretty much do what I did, yet I have been told mine performs like poop
>> compared to other candidates. I can't get any feedback on why it might
>> perform like poop or what could be done better.
>>
>> Can you guys give your suggestions?
>> http://github.com/ChristopherPisz/Asking-for-Peer-Review/tree/master/Boggle
>>
>>
>> I did a depth first search and compared the path thus far with words in
>> the dictionary using a Radix Trei. I don't know of any other possible
>> algorithm to solve the problem, or how I would implement it "better."
>>
>> C++ is getting REALLY performance orientated. I used to get a job within
>> 2 days just by knowing what virtual inheritance is. Now, I don't really
>> know how to "Get better"
>
>
> From a quick glance from your code I would say there is massive
> overengineering in the Dictionary area. For finding words matching a
> prefix one can just store them in a std::set and use
> std::set::lower_bound(), no need to build complex hierarchies of classes.

I used std::lower_bound in my first submission and they said that was
shit, so I tried again with the Radix Trei.

Radix Trei is O(k) where k is the length of the word, if I understand
correctly, while lower_bound is O(logn) with n being the number of words
in the dictionary, right?

They hinted at the dictionary being some 20MB of words, so I figure the
lookup part is very significant.

In my tests, the gains were really minimal though and the code far more
complex, like you say, but I don't have a 20MB dictionary to test with.

> I also see you have used std::upper_bound() on a pair of std::set
> iterators, this is probably the most counter-performance thing there.
> There is a reason why std::set has lower_bound() and upper_bound() as
> member functions.

Hmm, whats the difference between the two?
You're talking about calling

std::lower_bound(myset.begin(), myset.end(), value);
vs
myset.lower_bound(value);

?
I thought they are equivalent, is that incorrect?

> You also need to learn about std::string::compare(), I see things like
> that in your code:
>
> if ((*itChild)->m_value.substr(0, wordPart.size()) == wordPart) ...

I feel dumb. Never used std::string::compare
So the equivalent would be

if ( (*itChild)->m_value.compare(0, wordPart.size(), wordPart) == 0) ??
and that would prevent one temporary from the substr return?

> Yes, C++ is a lot about performance nowadays, if there is no need for
> performance the thing could be often programmed much more easily in some
> scripting language.
>
> Cheers
> Paavo
>

How do I prepare myself for the transition of doing 10 years of mostly
back-end business services to doing more "high performance" code?

I appeased Flibble by using uint_32 and its kin where size or
portability are an issue.

I am doing all I can on HackerRank. Algorithms and Data structures.

I am performance testing code I write and alternatives, but of course I
come up with both myself, so I might not have the best alternatives.

I've looked up custom memory management and practiced it.

I've come to terms with people insisting on using c-style code in some
performance intensive areas, like sprintf vs stream.

I've reviewed the complexity of operations on the common data structures
every day this month.

I am not sure what else I can do.
I am a 40 year old man about to cry if I don't get a job soon.


Thanks for your feedback man. I appreciate all you guys on this newsgroup.

[Paavo Helde]

The average length of a word is probably less than 20 chars, so we are
talking about 1M of words here.

>
> In my tests, the gains were really minimal though and the code far more
> complex, like you say, but I don't have a 20MB dictionary to test with.

You can easily generate a 20MB dictionary of random character sequences.

>
>> I also see you have used std::upper_bound() on a pair of std::set
>> iterators, this is probably the most counter-performance thing there.
>> There is a reason why std::set has lower_bound() and upper_bound() as
>> member functions.
>
> Hmm, whats the difference between the two?
> You're talking about calling
>
> std::lower_bound(myset.begin(), myset.end(), value);
> vs
> myset.lower_bound(value);
>
> ?
> I thought they are equivalent, is that incorrect?

Yep, at least with std::set. You see, std::set is not random access.
When you need to find, e.g. the middle point in 1M words, you need to
advance the begin() iterator 500,000 times. You can see where it goes. A
20 MB dictionary might not fit in L3 caches (depending on hardware), so
traversing it in such a fashion over and over might be extremely slow.

http://www.cplusplus.com/reference/algorithm/lower_bound/ says: "On
non-random-access iterators, the iterator advances produce themselves an
additional linear complexity in N on average."

In contrast, std::set::lower_bound is guaranteed to be O(log N), with no
caveats.

Note that nowadays in general the memory access is the slowest thing and
cpu-intensive calculations (like short string comparison) are fast, so
if std::lower_bound() is O(log N) in comparisons and O(N) in iterator
traversal to find the things to compare, then O(N) it is, no wiggle room
left.

log2(1M)==20, so with 1M elements std::set::lower_bound() should be
about 50,000 times faster than std::lower_bound(), plus-minus a couple
of magnitudes for constant factors. It looks like with your complicated
radix trie structures you have managed to offset some of the losses, but
not all.

>
>
>> You also need to learn about std::string::compare(), I see things like
>> that in your code:
>>
>> if ((*itChild)->m_value.substr(0, wordPart.size()) == wordPart) ...
>
> I feel dumb. Never used std::string::compare
> So the equivalent would be
>
> if ( (*itChild)->m_value.compare(0, wordPart.size(), wordPart) == 0) ??
> and that would prevent one temporary from the substr return?

Yep. Maybe it should be possible to optimize the temporary creation
away, but I am not sure if the current compilers are smart enough for that.

Potentially the most expensive part in temporary string construction is
dynamic allocation. Luckily, nowadays most implementations use
short-string optimization, meaning no dynamic allocation for strings
less than 16 bytes, for example. Alas, for example gcc<5.0 does not have
SSO.

>> Yes, C++ is a lot about performance nowadays, if there is no need for
>> performance the thing could be often programmed much more easily in some
>> scripting language.
>>
>> Cheers
>> Paavo
>>
>
> How do I prepare myself for the transition of doing 10 years of mostly
> back-end business services to doing more "high performance" code?

Practice?

> I've looked up custom memory management

This is important indeed.

> I've come to terms with people insisting on using c-style code in some
> performance intensive areas, like sprintf vs stream.

Streams are indeed awful in performance. Luckily I have never had a need
for streams aka "formatted text" in my professional career, it has
always been binary files or XML. I should note that sprintf() is also a
bit slow and undeterministic because of locale dependencies.

>
> I've reviewed the complexity of operations on the common data structures
> every day this month.

That's one good point! But next time read beyond the first sentence, at
least for the complexity of std::lower_bound()!

>
> I am not sure what else I can do.
> I am a 40 year old man about to cry if I don't get a job soon.

I bet you are pretty young compared to the average of this newsgroup ;-)

Cheers
Paavo

[Alf P. Steinbach]

I didn't look at your code. I just implemented it straightforward using
`lower_bound` to look for dictionary words in a vector. It's sort of
instant. BUT I generally get more words than the solution file:

[example]
[C:\my\forums\clc++\057 boggle]
> fc my_solution.txt data\board_1_solution.txt
Comparing files my_solution.txt and DATA\BOARD_1_SOLUTION.TXT
***** my_solution.txt
a
as
entry
go
hint
***** DATA\BOARD_1_SOLUTION.TXT
entry
hint
*****

***** my_solution.txt
hits
in
is
it
its
***** DATA\BOARD_1_SOLUTION.TXT
hits
its
*****

***** my_solution.txt
pen
saint
***** DATA\BOARD_1_SOLUTION.TXT
pen
quit
quits
saint
*****

***** my_solution.txt
sits
so
thin
***** DATA\BOARD_1_SOLUTION.TXT
sits
thin
*****

***** my_solution.txt
try
we
went
***** DATA\BOARD_1_SOLUTION.TXT
try
went
*****


[C:\my\forums\clc++\057 boggle]
> _
[example]

The weasel word "generally" indicates a bug, that my implementation
didn't find "quit" and "quits" as it should.

Still, have I misunderstood the rules?

What are they, exactly?


Cheers!,

- Alf

[Christopher J. Pisz]

Don't forget to turn a board Q into QU when comparing to the dictionary.
And diagonal

Rules are, and I am retyping them from memory...:

Given a board that is a grid of characters and an input file
Given a dictionary of valid words as an input file
Output all the words in the dictionary that can be found on the board,
where "finding" means

Start at any coordinate on the board and be able to trace the word
through adjacent nodes without traveling to any node more than once.

You may travel in all 8 directions. (diagonals included)

The dictionary input and the output is ordered alphabetically.

Some examples:

G D L W
O O Z E
D E O S
I Q S D

Doe
Go
God
Godless
Good
Quid

Assuming those are all in the dictionary file.

[Alf P. Steinbach]

On 10.02.2017 01:15, Christopher J. Pisz wrote:
>
>
> Don't forget to turn a board Q into QU when comparing to the dictionary.

Oh!


> And diagonal

Huh?

> Rules are, and I am retyping them from memory...:
>
> Given a board that is a grid of characters and an input file
> Given a dictionary of valid words as an input file
> Output all the words in the dictionary that can be found on the board,
> where "finding" means
>
> Start at any coordinate on the board and be able to trace the word
> through adjacent nodes without traveling to any node more than once.
>
> You may travel in all 8 directions. (diagonals included)
>
> The dictionary input and the output is ordered alphabetically.
>
> Some examples:
>
> G D L W
> O O Z E
> D E O S
> I Q S D
>
> Doe
> Go
> God
> Godless
> Good
> Quid
>
> Assuming those are all in the dictionary file.

Okay I'm stilling getting more words than the solution file has.

Those are short words, like "go".

Here:

Comparing files my_solution.txt and DATA\BOARD_1_SOLUTION.TXT
***** my_solution.txt
a
as
entry
go
hint
***** DATA\BOARD_1_SOLUTION.TXT
entry
hint
*****

***** my_solution.txt
hits
in
is
it
its
***** DATA\BOARD_1_SOLUTION.TXT
hits
its
*****

***** my_solution.txt

sits
so
thin
***** DATA\BOARD_1_SOLUTION.TXT
sits
thin
*****

***** my_solution.txt
try
we
went
***** DATA\BOARD_1_SOLUTION.TXT
try
went
*****

I haven't tested more boards but it seems I get all the words in the
solution file, plus some?

Here's the code:


#include <algorithm> // std::(is_sorted, remove, sort, transform)
#include <assert.h> // assert
#include <ctype.h> // tolower
#include <fstream> // std::ifstream
#include <iostream>
#include <vector> // std::vector
#include <stddef.h> // ptrdiff_t
#include <stdexcept> // std::(exception, runtime_error)
#include <stdlib.h> // EXIT_FAILURE, EXIT_SUCCESS
#include <string > // std::string
#include <utility> // std::move

using Size = ptrdiff_t;
using Index = Size;

template< class Container >
auto n_items_of( Container const& c )
-> Size
{ return c.size(); }

namespace cppx {
using std::ostream;
using std::vector;
using std::runtime_error;
using std::string;

using Byte = unsigned char;
inline auto hopefully( bool const e ) -> bool { return e; }
inline auto fail( string const& s ) -> bool { throw runtime_error(
s ); }

struct Position
{
Index x;
Index y;
};

inline auto operator<<( ostream& stream, Position const& pos )
-> ostream&
{ return stream << "{" << pos.x << ", " << pos.y << "}"; }

template< class Item >
class Matrix
{
private:
struct Wrapped_item { Item object; }; // Avoid problems
with vector<bool>.

Size row_length_;
vector<Wrapped_item> items_;

auto index_for( Index x, Index y ) const
-> Index
{ return y*row_length_ + x; }

public:
auto id_for_position( Index x, Index y ) const
-> Index
{ return index_for( x, y ); }

auto size() const
-> Size
{ return row_length_; }

auto item( Index const x, Index const y ) const
-> Item
{ return items_[index_for( x, y )].object; }

auto item( Index const x, Index const y )
-> Item&
{ return items_[index_for( x, y )].object; }

Matrix(): Matrix{ 0 } {}

explicit Matrix( Size const size )
: row_length_( size )
, items_( size*size )
{}

};

auto inline to_lowercase( char const ch )
-> char
{ return tolower( static_cast<Byte>( ch ) ); }

auto inline starts_with( string const& prefix, string const& s )
-> bool
{ return s.substr( 0, prefix.length() ) == prefix; }

} // namespace cppx

namespace app {
using namespace std;
using namespace cppx;

auto load_dictionary( string const& file_path )
-> vector<string>
{
ifstream data{ file_path };
hopefully( not data.fail() )
|| fail( "Failed to open dictionary `" + file_path + "`." );

vector<string> result;
string word;
while( getline( data, word ) )
{
result.push_back( move( word ) );
}
return result;
}

auto chars_from( string s )
-> string
{
string chars{ s.begin(), remove( s.begin(), s.end(), ' ' ) };
transform( chars.begin(), chars.end(), chars.begin(),
to_lowercase );
return chars;
}

auto load_bubble_board( string const& file_path )
-> Matrix<char>
{
ifstream data{ file_path };
hopefully( not data.fail() )
|| fail( "Failed to open dictionary `" + file_path + "`." );

string line;
string chars; // Whitespace removed.
getline( data, line )
|| fail( "Unable to read first line of `" + file_path + "`." );
chars = chars_from( line );
Size const n = n_items_of( chars );
Matrix<char> result{ 2 + n };
for( Index x = 0; x < n; ++x ) { result.item( x + 1, 1 ) =
chars[x]; }
for( Index y = 1; y < n; ++y )
{
getline( data, line )
|| fail( "Unable to read line " + to_string( y + 1 ) +
" of `" + file_path + "`." );
chars = chars_from( line );
hopefully( n_items_of( chars ) == n )
|| fail( "Inconsistent row lengths in board data `" +
file_path + "`" );
for( Index x = 0; x < n; ++x ) { result.item( x + 1, y + 1
) = chars[x]; }
}
return result;
}

using Dictionary_iter = vector<string>::const_iterator;

void recursively_append_words_from(
Dictionary_iter const start_dict_range,
Dictionary_iter const end_dict_range,
Matrix<char> const& chars,
Position const position,
Matrix<bool>& visited,
string& word,
vector<string>& result
)
{
Size const original_word_length = word.length();
char const ch = chars.item( position.x, position.y );
if( ch == 'q' ) { word += "qu"; } else { word += ch; }
auto const lower = lower_bound( start_dict_range,
end_dict_range, word );

clog << position << " -> " << *lower << "\n";
if( starts_with( word, *lower ) )
{
if( word == *lower )
{
result.push_back( word );
}
visited.item( position.x, position.y ) = true;
for( int dx = -1; dx <= +1; ++dx )
{
for( int dy = -1; dy <= +1; ++dy )
{
Position const new_position = {position.x + dx,
position.y + dy};
if( not visited.item( new_position.x,
new_position.y ) )
{
recursively_append_words_from(
lower, end_dict_range, chars, new_position,
visited, word, result
);
}
}
}
visited.item( position.x, position.y ) = false;
}
word.resize( original_word_length );
}

void append_words_from(
vector<string> const& dictionary,
Matrix<char> const& chars,
Position const& start,
vector<string>& result
)
{
string word;
Size const n = chars.size();
Matrix<bool> visited{ n };

for( Index i = 0; i < n; ++ i )
{
visited.item( i, 0 ) = true;
visited.item( 0, i ) = true;
visited.item( i, n - 1 ) = true;
visited.item( n - 1, i ) = true;
}

recursively_append_words_from(
dictionary.begin(), dictionary.end(), chars, start,
visited, word, result
);
}

void cpp_main( vector<string> const& args )
{
hopefully( n_items_of( args ) == 3 )
|| fail( "Usage: " + args[0] + " DICTIONARY BUBBLEBOARD" );

vector<string> const dictionary = load_dictionary( args[1] );
Matrix<char> const board = load_bubble_board( args[2] );

assert( is_sorted( dictionary.begin(), dictionary.end() ) );
Size const n = board.size();
vector<string> words;
for( Index y = 0; y < n; ++y ) for( Index x = 0; x < n; ++x )
{
append_words_from( dictionary, board, {x + 1, y + 1}, words );
}

sort( words.begin(), words.end() );
words.erase( unique( words.begin(), words.end() ), words.end() );
for( auto const& word : words )
{
cout << word << "\n";
}
}
} // namespace app

auto main( int const n_args, char** args )
-> int
{
using namespace std;
try
{
app::cpp_main( {args, args + n_args} );
return EXIT_SUCCESS;
}
catch( exception const& x )
{
cerr << "! " << x.what() << "\n";
}
return EXIT_FAILURE;
}


Cheers & hth.,

- Alf

[Christopher J. Pisz]

Oh crap. I forgot a rule.
The word has to be at least 3 letters long. Sorry. From memory sucks
with old man memory.

[Christopher J. Pisz]

On 2/9/2017 5:35 PM, Paavo Helde wrote:
> On 10.02.2017 0:36, Christopher J. Pisz wrote:
>> On 2/9/2017 4:06 PM, Paavo Helde wrote:
>>> On 9.02.2017 22:08, Christopher J. Pisz wrote:
>>>> Seems to be a pretty standard interview screening test. I Googled it
>>>> after the fact and it pops up with a page of hits. Everyone seemed to
>>>> pretty much do what I did, yet I have been told mine performs like poop
>>>> compared to other candidates. I can't get any feedback on why it might
>>>> perform like poop or what could be done better.
>>>>
>>>> Can you guys give your suggestions?
>>>> http://github.com/ChristopherPisz/Asking-for-Peer-Review/tree/master/Boggle
>>>>
>>>>
>>>>
>>>>
>>>> I did a depth first search and compared the path thus far with words in
>>>> the dictionary using a Radix Trei. I don't know of any other possible
>>>> algorithm to solve the problem, or how I would implement it "better."
>>>>

SNIP

>>> I also see you have used std::upper_bound() on a pair of std::set
>>> iterators, this is probably the most counter-performance thing there.
>>> There is a reason why std::set has lower_bound() and upper_bound() as
>>> member functions.
>>
>> Hmm, whats the difference between the two?
>> You're talking about calling
>>
>> std::lower_bound(myset.begin(), myset.end(), value);
>> vs
>> myset.lower_bound(value);
>>
>> ?
>> I thought they are equivalent, is that incorrect?
>
> Yep, at least with std::set. You see, std::set is not random access.
> When you need to find, e.g. the middle point in 1M words, you need to
> advance the begin() iterator 500,000 times. You can see where it goes. A
> 20 MB dictionary might not fit in L3 caches (depending on hardware), so
> traversing it in such a fashion over and over might be extremely slow.
>
> http://www.cplusplus.com/reference/algorithm/lower_bound/ says: "On
> non-random-access iterators, the iterator advances produce themselves an
> additional linear complexity in N on average."
>
> In contrast, std::set::lower_bound is guaranteed to be O(log N), with no
> caveats.

SNIP

>>> You also need to learn about std::string::compare(), I see things like
>>> that in your code:
>>>
>>> if ((*itChild)->m_value.substr(0, wordPart.size()) == wordPart) ...
>>
>> I feel dumb. Never used std::string::compare
>> So the equivalent would be
>>
>> if ( (*itChild)->m_value.compare(0, wordPart.size(), wordPart) == 0) ??
>> and that would prevent one temporary from the substr return?
>
> Yep. Maybe it should be possible to optimize the temporary creation
> away, but I am not sure if the current compilers are smart enough for that.

I got about 30% better performance out of those changes.

Significant, but they were claiming other implemented it 25X as fast as
mine. There must be something else fundamentally wrong, like the
algorithm itself.

[Christopher J. Pisz]

As far as I can tell you are doing pretty much exactly what I did when I
used lower_bound. Although, you're code is fancier with new C++11 and
C++14 stuff.

My dictionary was a set<string> at that time though, compared to your
vector<string>

I wonder if they would have kicked you out too :/
Or maybe I am just missing some glaring error in my code or its logic.

I wish I could find a bigger board, dictionary, and solutions to test
with somewhere. Mine solves in a matter of microseconds in release with
the given data, but whatever they used, they claim it took 25 seconds.

I need to ponder how I would generate a bigger set of data, but still
have the solutions to test against.

[Paavo Helde]

On 10.02.2017 3:13, Christopher J. Pisz wrote:
> On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:
>> On 10.02.2017 01:15, Christopher J. Pisz wrote:
>>
>> using Dictionary_iter = vector<string>::const_iterator;
>>
>> void recursively_append_words_from(
>> Dictionary_iter const start_dict_range,
>> Dictionary_iter const end_dict_range,

[...]
>> )
>> {
[...]

>> auto const lower = lower_bound( start_dict_range,
>> end_dict_range, word );
>

> As far as I can tell you are doing pretty much exactly what I did when I
> used lower_bound. Although, you're code is fancier with new C++11 and
> C++14 stuff.
>
> My dictionary was a set<string> at that time though, compared to your
> vector<string>

Alf is using a sorted vector, and this means the iterators are random
access. This makes the big difference of O(log N) instead of O(N) in
std::lower_bound().

[Christopher J. Pisz]

So I just woke up and I can't sleep, because this is bothering me so much.

The thought occurred to me:

What if instead of traversing the board and checking if what we find on
every node along our path is some word in our huge dictionary, we
checked if words in the dictionary were on the board instead.

I saw so much work on prefixes, that I envision the pattern:
to
top
toppless
topper
topping

Well, if we don't find the letters "to" then we can eliminate ALL those
words!

Since the dictionary size is obviously really large, this will greatly
reduce it.

Also, we can make a lookup by word that gives us a structure containing
the last letter found, its location on the board, and a grid denoting
which nodes were traversed. That way after searching for the word "to"
we can pick up where we left off for any future searches for words
beginning with "to"

Eurika!
I am implementing this now. I suspect it will greatly speed things up.

[Öö Tiib]

Sure, yes. But beware! You may draw oversimplified conclusion
from that.

The dictionary structure that is used when that matters is suffix
tree also named "trie". You can likely find insightful discussions
in net about usage of trie for speeding such search algorithms.
Public domain trie implementations in C++ that I have seen are
not too great (or may be did not fit to my problems too well).

>
> Since the dictionary size is obviously really large, this will greatly
> reduce it.

Why? No. That's what I meant with "beware" above. It does not pack
data on general case.

>
> Also, we can make a lookup by word that gives us a structure containing
> the last letter found, its location on the board, and a grid denoting
> which nodes were traversed. That way after searching for the word "to"
> we can pick up where we left off for any future searches for words
> beginning with "to"
>
> Eurika!
> I am implementing this now. I suspect it will greatly speed things up.

:) Yes, usage of correct data layout can give order of magnitude or better
performance improvements. But ... read about it a bit.

[Paavo Helde]

On 10.02.2017 9:43, Christopher J. Pisz wrote:
> On 2/9/2017 2:08 PM, Christopher J. Pisz wrote:
>> Seems to be a pretty standard interview screening test. I Googled it
>> after the fact and it pops up with a page of hits. Everyone seemed to
>> pretty much do what I did, yet I have been told mine performs like poop
>> compared to other candidates. I can't get any feedback on why it might
>> perform like poop or what could be done better.
>>
>> Can you guys give your suggestions?
>> http://github.com/ChristopherPisz/Asking-for-Peer-Review/tree/master/Boggle
>>
>>
>> I did a depth first search and compared the path thus far with words in
>> the dictionary using a Radix Trei. I don't know of any other possible
>> algorithm to solve the problem, or how I would implement it "better."
>>
>> C++ is getting REALLY performance orientated. I used to get a job within
>> 2 days just by knowing what virtual inheritance is. Now, I don't really
>> know how to "Get better"
>
>
>
> So I just woke up and I can't sleep, because this is bothering me so much.
>
> The thought occurred to me:
>
> What if instead of traversing the board and checking if what we find on
> every node along our path is some word in our huge dictionary, we
> checked if words in the dictionary were on the board instead.

Checking all words in the dictionary is O(N) again - i.e. not better.

Why do I have a feeling that you are not actually reading our e-mails?
Generate a dictionary of 1e6 random words and test your solutions vs
Alf's solution and then it becomes immediately clear which solutions are
faster, no need for brilliant dream ideas.

If something is slow, profile it, find the bottlenecks and fix them.
BTW, this kind of work is a good exercise for a real performance-related
C++ job where one often needs to profile and optimize code. Plus, you
get some insight about what things are slow and what are fast, on your
current hardware at least.

[Chris Vine]

I haven't looked at your implementation and I may have misunderstood
what you mean, nor have I ever played boggle, but as I understand the
rules you have given, wouldn't either approach necessarily work that
way, so I don't see how this could be an improvement.

Take what you say was your original approach of "checking if what we

find on every node along our path is some word in our huge dictionary",

and take as an initial test point the simplest possible dictionary
implementation of a sorted std::vector and the most naive and
uncomplicated algorithm: to search for a word by picking a starting
square on the board, take the letter given (say 't') and then restrict
all further consideration of the dictionary for that starting square by
reference to the (already sorted) bounded sub-range of those words in
the dictionary beginning with 't'. You would then test all the possible
second and subsequent letters of the word against the dictionary
recursively by reference to ever more refined slices of the dictionary,
until you have found all the words in the dictionary beginning on the
chosen starting square; and then move on to the next starting square.

That is not to say that there aren't better algorithms: there almost
certainly are. Your idea of caching looks promising, so that already
checked sub-ranges can be reused for different starting squares. But as
I say, I may also have misunderstood the rules of the game that you
posted or the implementation that you developed.

Chris

[Scott Lurndal]

Your solution is way overkill. As someone who has interviewed hundreds
of candidates for jobs that require C++ coding skills, I'd also be leary
of such a solution. There is no need for trees or fancy data structures
for a simple problem like this. I'm looking for programmers that think
out-of-the-box and craft efficient solutions.

This uses a rather clever technique to simplify the algorithm.

50 lines (more would be needed to read the character matrix dynamically):

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

const char matrix[7][6] = {
{ '@', '@', '@', '@', '@', '@' },
{ '@', 'F', 'G', 'G', 'Y', '@' },
{ '@', 'R', 'O', '6', '7', '@' },
{ '@', 'P', 'O', 'P', 'E', '@' },
{ '@', 'H', 'A', 'M', 'Z', '@' },
{ '@', '@', '@', '@', '@', '@' },
{ '\0', '\0', '\0', '\0', '\0', '\0' },
};


bool
checkchar(const char *cp, size_t row, size_t col)
{
if (*++cp == '\0') return true;

for (size_t r = row - 1; r <= (row + 1); r++) {
for (size_t c = col - 1; c <= (col + 1); c++) {
if ((r == row) && (c == col)) continue;
if (matrix[r][c] == *cp) {
if (checkchar(cp, r, c)) return true;
}
}
}
return false;
}

int
main(int argc, const char **argv, const char **envp)
{
for (size_t arg = 1; arg < argc; arg++) {
const char *cp = argv[arg];
const char *mp = &matrix[0][0];

while ((*mp != '\0') && (*mp != *cp)) mp++;
if (*mp != '\0') {
if (checkchar(cp, ((ptrdiff_t)mp - (ptrdiff_t)matrix)/6, ((ptrdiff_t)mp - (ptrdiff_t)matrix)%6)) {
printf("match found for '%s'\n", argv[arg]);
}
}
}

return 0;
}

$ /tmp/abc GO FACE FROG FROGGY HAM HOPE POO POOP ZOO
match found for 'GO'
match found for 'FROG'
match found for 'FROGGY'
match found for 'HAM'
match found for 'HOPE'
match found for 'POO'
match found for 'POOP'

[Alf P. Steinbach]

I like the way you think here, of just demonstrating that one
understands recursive search, and thus only producing a special case
answer. After all it was an interview question. And assuming a competent
evaluation this would give high score on “result-oriented”.

Still, this code produces a false positive for “GOGO”, and it fails to
find (i.e. it produces a false negative for) “G7”.

And I think that would lower one's score on “attention to detail”.

In the same direction, the unused and in C++ non-standard `envp`.

So, it's not entirely clear to me that this short clever code would
improve one's chances of being hired. Still it's impressive. I wish I
would have thunk of that :D .


Cheers!,

- Alf

[Scott Lurndal]

Ah, missed the "not-yet-visited" clause for GOGO.

I'm not the interview candidate, and I whipped that out in
about 15 minutes. If I were doing production code, there
would be much more testing.

(I also missed the "Qu" -> "Q" transformation, but that's just
an additional line:

if (*mp != '\0') {

if ((*cp == 'q') && (*(cp+1) == 'u')) cp++;

>
>And I think that would lower one's score on “attention to detail”.
>
>In the same direction, the unused and in C++ non-standard `envp`.

Forty years of habit are hard to break.

>
>So, it's not entirely clear to me that this short clever code would
>improve one's chances of being hired. Still it's impressive. I wish I
>would have thunk of that :D .

Like I said, If I were submitting it as a interview answer, it would
have been much more rigorously checked.

[Christopher J. Pisz]

I am not really able to follow the idea here. If it solves it in as
little lines as written, then it is wonderful, but I am finding it hard
to follow with that the bird's eye view of the "plan" in text.

I am looking at the math without knowing the answer it is trying to find.

[Christopher J. Pisz]

I can see we are iterating through the matrix as a one dimensional
array, but we're checking every single letter of every single word in
the dictionary still, at least until a letter is rejected along the
path. So, while compact, this is not necessarily going to perform any
better, right?

[Scott Lurndal]

The algorithm first scans the matrix for the first character of the
test string[*]. If not found, go to the next string. So worst case,
we look at each element in the matrix once. Best case, we look at
one single matrix entry to start the word.

If the first character of the test string is in the matrix, then
we check each of the 8 surrounding characters for a match against
the second character, and bail if not found. If found, recurse.

We never allocate or deallocate memory (which your algorithms do).

The algorithm needs a small update to not visit the same matrix
location twice for a given word while recursing.

With a matrix this small, the entire thing fits into the processor cache,
with a larger matrix, the prefetcher would kick in.

It would be require a bit more space to handle multibyte UTF-8, UTF-16
or UTF-32 glyph data.

[*] A really good compiler would generate a SCASB instruction for this
on intel systems.

[Scott Lurndal]

The "trick" here (which I learned back in 1979) is to put a fence
around the matrix so the algorithm doesn't have to special case
cells at the borders.

[Christopher J. Pisz]

Pushed algorithm 2 to github.
It is significantly worse.

[Christopher J. Pisz]

On 2/10/2017 6:17 AM, Paavo Helde wrote:
SNIP

> Why do I have a feeling that you are not actually reading our e-mails?
> Generate a dictionary of 1e6 random words and test your solutions vs
> Alf's solution and then it becomes immediately clear which solutions are
> faster, no need for brilliant dream ideas.

Alf is using a lot fancy syntax I am unfamiliar with. However, his
algorithm looks the same. Beyond using the vector, I don't see any
differences and the performance increase I am getting is not enough to
match what they are claiming.

> If something is slow, profile it, find the bottlenecks and fix them.
> BTW, this kind of work is a good exercise for a real performance-related
> C++ job where one often needs to profile and optimize code. Plus, you
> get some insight about what things are slow and what are fast, on your
> current hardware at least.

Yea, I been doing just that all day.
Profiling alternative idea, different data structures, etc.

Just haven't found anything near the performance they are claiming.

I found this is a problem on leetcode.com under "Word Search II"
I am looking at some of the top solutions there now too.

[Christopher J. Pisz]

On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:

> inline auto operator<<( ostream& stream, Position const& pos )
> -> ostream&
> { return stream << "{" << pos.x << ", " << pos.y << "}"; }

Can you explain what -> ostream& means?

I don't think I've ever seen this syntax you are using with -> following
returntype functionname(arg1, arg1)

[Alf P. Steinbach]

The `->` is called trailing return type syntax, and was introduced in C++11.

The `auto` as pseudo return type at the front of the declaration, says
that either a `->` trailing return type will follow, or, in C++14 and
later, a return type specification is omitted and the type will be
inferred from the function body (obviously the latter is only possible
on a full function definition, not on a pure declaration).

Trailing return type is the only syntax available for lambdas, so it's
the only syntax that can be used uniformly for all function
declarations. It has some direct advantages including that one can avoid
qualification of the return type when it's a type defined in the
function's class (just as with argument types); that it allows the
return type to be specified in terms of the argument types; and that it
generally makes it easier to visually parse complicated declarations.

I adopted it early on as a single, uniform syntax, with no exceptions
for new code, not even for `main`. Using it for `main` on e.g. Stack
Overflow tends to generate questions about it. Which allows teaching. :)

Still I prefer to use the old syntax for `void` routines in general,
even though a `void` lambda can't be written that way. This corresponds
to Pascal's differentiation of `function` versus `procedure`: whether a
routine can meaningfully be used in an expression, contributing to the
expression result. More that way: I wish C++ had support for pure
functions, purely computational functions without side effects, beyond
the very limited C++11 compile time `constexpr` function.


Cheers!,

- Alf

[Chris Vine]

On Fri, 10 Feb 2017 19:21:07 -0600

"Christopher J. Pisz" <cp...@austin.rr.com> wrote:

I am quite surprised at this (assuming you have tested Alf's code)
because on looking at his implementation it seems reasonable (and
follows the recursive dictionary slicing approach I mentioned in
another post of mine). I thought it likely that your interviewers were
mainly interested in whether candidates understood how to build up
results using recursion, but it seems not.

The only thing that struck me about Alf's implementation is that the
starts_with() function is in the recursion hot path and by calling
std::string::substr() might allocate memory, although with small string
optimization one would hope not, which using std::string::compare()
shouldn't do. You could try substituting std::string::compare() in that
function and see if that makes any difference (it probably won't). You
would also need to omit the call to clog in the hot path (presumably
inserted for debugging) to get proper timings of that implementation.

Chris

[Alf P. Steinbach]

On 11.02.2017 12:25, Chris Vine wrote:
>
> The only thing that struck me about Alf's implementation is that the
> starts_with() function is in the recursion hot path and by calling
> std::string::substr() might allocate memory

I also compared strings for equality when known that one is leading
substring of other, instead of just comparing lengths then.

Even for a first working version that was, well, dumb. :)


Cheers!,

- Alf

[Chris Vine]

I think your code was OK on the equality test. The dictionary lower
bound has been reset on re-entering recursively_append_words_from(),
and end_dict_range is always one past the end of the dictionary, so
'word' might no longer be a leading substring of *lower. (It occurs
to me that since 'lower' could be at 'end_dict_range', this should
probably be checked for before 'lower' is dereferenced on calling
starts_with().)

Chris

[Öö Tiib]

On Saturday, 11 February 2017 10:16:14 UTC+2, Alf P. Steinbach wrote:
> On 11.02.2017 02:24, Christopher J. Pisz wrote:
> > On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:
> >
> >> inline auto operator<<( ostream& stream, Position const& pos )
> >> -> ostream&
> >> { return stream << "{" << pos.x << ", " << pos.y << "}"; }
> >
> > Can you explain what -> ostream& means?
> >
> > I don't think I've ever seen this syntax you are using with -> following
> > returntype functionname(arg1, arg1)
>
> The `->` is called trailing return type syntax, and was introduced in C++11.

For to get used to that syntax one may write few apps in Rust and/or Swift.
It is possible even to get paid for doing uneducated attempts of usage
of Swift since there seems to be quite serious shortage of experienced
iOS developers at the moment.

[Chris Vine]

On Fri, 10 Feb 2017 19:14:26 -0600

"Christopher J. Pisz" <cp...@austin.rr.com> wrote:

I am not surprised. From what I could make out of your code, you are
walking through the entire dictionary and testing iteratively whether
each word in the dictionary is on the board. On a large dictionary
that is about the worst possible implementation. Instead, on a large
dictionary you need to step through the board and work from there.

What are the respective timings, on the same input data, of:

1. Your first implementation.

2. Your second implementation

3. Alf's implementation?

Chris

[Christopher J. Pisz]

412 ms


> 2. Your second implementation

Didn't bother. It is visibly slower, so why measure

> 3. Alf's implementation?

Working on trying to get it to conform to test, so no idea yet.

I am using
https://leetcode.com/problems/word-search-ii/?tab=Description
to test now. It also has 1000s of submissions and is close enough to the
original problem that the interviewers asked. Just adjusted for 4
directions vs 8 and no q->qu.

The acceptable range is 40ms-60ms.

If I look at the top performing answer, they used a preallocated trie
and didn't even bother with any OO or separation of concerns, which I
guess is a requirement when we start trying to squeeze out performance
and drop all concern for reusability or maintenance.

I'll post updated times when I have them.

[Christopher J. Pisz]

On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:

> On 10.02.2017 01:15, Christopher J. Pisz wrote:

> inline auto operator<<( ostream& stream, Position const& pos )
> -> ostream&
> { return stream << "{" << pos.x << ", " << pos.y << "}"; }
>

> using Dictionary_iter = vector<string>::const_iterator;
>
> void recursively_append_words_from(
> Dictionary_iter const start_dict_range,
> Dictionary_iter const end_dict_range,

> Matrix<char> const& chars,
> Position const position,
> Matrix<bool>& visited,
> string& word,
> vector<string>& result
> )
> {
> Size const original_word_length = word.length();
> char const ch = chars.item( position.x, position.y );
> if( ch == 'q' ) { word += "qu"; } else { word += ch; }

> auto const lower = lower_bound( start_dict_range,
> end_dict_range, word );
>

> - Alf
>



I am trying to get this to confor to the test on
https://leetcode.com/problems/word-search-ii/?tab=Description

That way I can easily compare results of my various attempts, your, and
others.

I am having trouble with your indexing. you init things with +1 and then
get index_from, and I am lost.

The tester's format is a wee bit different then first discussed.

)They only go verticle and horizontal
)They don't care about q->qu
)They give the input data in Solution::findWords and we are to fill out
that method and class.


I tried to get your solution into the tester's format below and I am
getting vector out of range problems:

#include <algorithm>
#include <assert.h>
#include <ctype.h>
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <stddef.h>
#include <stdexcept>
#include <stdlib.h>
#include <string>
#include <utility>

using Size = ptrdiff_t;
using Index = Size;

template< class Container >
auto n_items_of(Container const& c)
-> Size
{
return c.size();
}

namespace cppx {
using std::ostream;
using std::vector;
using std::runtime_error;
using std::string;

using Byte = unsigned char;

inline auto hopefully(bool const e) -> bool { return e; }

inline auto fail(string const& s) -> bool { throw runtime_error(s); }

struct Position
{
Index x;
Index y;
};

inline auto operator<<(ostream& stream, Position const& pos)

-> ostream&
{
return stream << "{" << pos.x << ", " << pos.y << "}";
}

template< class Item >
class Matrix
{
private:
struct Wrapped_item { Item object; }; // Avoid problems
with vector<bool>.

Size row_length_;
vector<Wrapped_item> items_;

auto index_for(Index x, Index y) const

-> Index
{
return y*row_length_ + x;
}

public:
auto id_for_position(Index x, Index y) const
-> Index
{
return index_for(x, y);
}

auto size() const
-> Size
{
return row_length_;
}

auto item(Index const x, Index const y) const

-> Item
{
return items_[index_for(x, y)].object;
}

auto item(Index const x, Index const y)
-> Item&
{

return items_[index_for(x, y)].object;

}

Matrix() : Matrix{ 0 } {}

explicit Matrix(Size const size)
: row_length_(size)
, items_(size*size)
{}

};

auto inline to_lowercase(char const ch)
-> char
{
return tolower(static_cast<Byte>(ch));
}

auto inline starts_with(string const& prefix, string const& s)
-> bool
{

return s.substr(0, prefix.length()) == prefix;

}

} // namespace cppx

namespace app
{
using namespace std;
using namespace cppx;

auto load_dictionary(string const& file_path)
-> vector<string>
{
ifstream data{ file_path };

hopefully(!data.fail())

|| fail("Failed to open dictionary `" + file_path + "`.");

vector<string> result;
string word;
while( getline(data, word) )
{
result.push_back(move(word));
}
return result;
}

auto chars_from(string s)
-> string
{
string chars{ s.begin(), remove(s.begin(), s.end(), ' ') };
transform(chars.begin(), chars.end(), chars.begin(), to_lowercase);
return chars;
}

using Dictionary_iter = vector<string>::const_iterator;

void recursively_append_words_from(
Dictionary_iter const start_dict_range,
Dictionary_iter const end_dict_range,

Matrix<char> const& chars,
Position const position,
Matrix<bool>& visited,
string& word,
vector<string>& result
)
{
Size const original_word_length = word.length();
char const ch = chars.item(position.x, position.y);

word += ch;
auto const lower = lower_bound(start_dict_range,
end_dict_range, word);

clog << position << " -> " << *lower << "\n";

if( starts_with(word, *lower) )

{
if( word == *lower )
{
result.push_back(word);
}

visited.item(position.x, position.y) = true;

for( int dx = -1; dx <= +1; ++dx )
{
for( int dy = -1; dy <= +1; ++dy )
{

if( position.x + dx < 0 || position.x + dx >
chars.size() - 1 ||
position.y + dy < 0 || position.y + dy >
chars.size() - 1 )
{
continue;

}

Position const new_position = { position.x + dx,
position.y + dy };

if( !visited.item(new_position.x, new_position.y) )

{
recursively_append_words_from(
lower, end_dict_range, chars, new_position,
visited, word, result
);
}
}
}
visited.item(position.x, position.y) = false;
}
word.resize(original_word_length);
}

void append_words_from(
vector<string> const& dictionary,
Matrix<char> const& chars,
Position const& start,
vector<string>& result
)
{
string word;
Size const n = chars.size();
Matrix<bool> visited{ n };

for( Index i = 0; i < n; ++i )
{
visited.item(i, 0) = true;
visited.item(0, i) = true;
visited.item(i, n - 1) = true;

visited.item(n - 1, i) = true;

}

recursively_append_words_from(
dictionary.begin(), dictionary.end(), chars, start,
visited, word, result
);
}

} // namespace app


class Solution
{
public:

Solution() {}

std::vector<std::string> findWords(std::vector<std::vector<char>>&
board, std::vector<std::string>& words)
{
// Sort the dictionary
std::sort(words.begin(), words.end());

// Load the matrix
cppx::Matrix<char> matrix(board.size());

for( Index y = 0; y < board.size(); ++y )
{
for( Index x = 0; x < board[0].size(); ++x )
{
matrix.item(x, y) = board[y][x];
}
}

// Solve

Size const n = board.size();

std::vector<std::string> results;

for( Index y = 0; y < n; ++y )
{
for( Index x = 0; x < n; ++x )
{

app::append_words_from(words, matrix, {x, y}, results);
}
}

sort(results.begin(), results.end());
results.erase(unique(results.begin(), results.end()),
results.end());


return results;
}

private:

};

int main()
{
std::vector<std::vector<char>> board = { { 'o','a','a','n' },{
'e','t','a','e', },{ 'i','h','k','r' },{ 'i','f','l','v' } };
std::vector<std::string> words = { "oath", "pea", "eat", "rain" };

Solution solution;
std::vector<std::string> result = solution.findWords(board, words);

return 0;
}

[Christopher J. Pisz]

On 2/11/2017 11:30 AM, Christopher J. Pisz wrote:
> On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:
>> On 10.02.2017 01:15, Christopher J. Pisz wrote:
>

I think he is also using a fence.
If I put the indices back as normal, I still get a vector range
assertion here:

void recursively_append_words_from(
Dictionary_iter const start_dict_range,
Dictionary_iter const end_dict_range,
Matrix<char> const& chars,
Position const position,
Matrix<bool>& visited,
string& word,
vector<string>& result
)
{
Size const original_word_length = word.length();
char const ch = chars.item(position.x, position.y);
word += ch;
auto const lower = lower_bound(start_dict_range,
end_dict_range, word);

clog << position << " -> " << *lower << "\n";

I think that is an actual bug. What if lower_bound returned end()? You
cannot deref end?

[Öö Tiib]

No way. OO and separation of concerns usually improves performance.
However there is a "but".

In task under hand we have only two objects. We have "boggle field"
B and "dictionary" D. We have only one concern that involves both
objects. What texts from D are present on B? So what deep OO you
anticipate here?

Here can be done unneeded overengineering. That usually indeed
degrades performance in addition to making code more fragile and
harder to understand.

[Christopher J. Pisz]

I see a objects:
a board
a dictionary
a solver

and in the real world possibly:
a board::path
a coordinate

Now on the website mentioned, if we look at the best solutions, they did
indeed use a trei for their dictionary, and had to create it.

Rather than made a class Trei, they just implemented it as part of the
solver.

More than that, but a lot of them implemented it for the specific
problem at hand, rather than something that was reusable at all.

Consider this top ranked C++ solution and notice the board, the solver,
the dictionary, the trei, are all built into the one class and only
designed to solve the very specific problem:

class Solution {
vector<string> results;
int x_dim, y_dim;

struct TrieNode {
TrieNode* exits[26];
bool is_end;
};

void recurse( vector<vector<char>>& board, string& s, int x, int y,
TrieNode* trie_curr ) {
if ( unsigned(x) >= x_dim || unsigned(y) >= y_dim )
return;

const auto c = board[y][x];

if ( !c )
return;

auto trie_next = trie_curr->exits[ c-'a' ];
if ( !trie_next )
return;

s.push_back( c );
board[y][x] = 0;

if ( trie_next->is_end ) {
results.push_back( s );
trie_next->is_end = false;
}

recurse( board, s, x-1, y, trie_next );
recurse( board, s, x+1, y, trie_next );
recurse( board, s, x, y-1, trie_next );
recurse( board, s, x, y+1, trie_next );

board[y][x] = c;
s.pop_back();
}

public:
vector<string> findWords(vector<vector<char>>& board,
vector<string>& words) {
if ( !words.size() || !board.size() || !board[0].size() )
return results;

int tot_chars = 0;
for ( const auto& word : words )
tot_chars += word.length();

TrieNode* trie_pool = (TrieNode*)calloc( sizeof(TrieNode),
tot_chars + 2 );
int num_trie_nodes = 0;

TrieNode* trie_root = &trie_pool[ num_trie_nodes++ ];

for ( const auto& word : words ) {
TrieNode* trie_curr = trie_root;
for ( const auto c : word ) {
auto& trie_next = trie_curr->exits[ c-'a' ];

if (!trie_next)
trie_next = &trie_pool[ num_trie_nodes++ ];

trie_curr = trie_next;
}
trie_curr->is_end = true;
}

x_dim = board[0].size();
y_dim = board.size();

string s;
for ( auto y = 0 ; y < y_dim ; ++y )
for ( auto x = 0; x < x_dim; ++x )
recurse( board, s, x, y, trie_root );

free( trie_pool ); // from C to shining C.
return results;
}
};

[Christopher J. Pisz]

On 2/11/2017 11:49 AM, Christopher J. Pisz wrote:
> On 2/11/2017 11:30 AM, Christopher J. Pisz wrote:
>> On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:
>>> On 10.02.2017 01:15, Christopher J. Pisz wrote:
>>
>

SNIP

I got Alf's solution to run on the test site.

If I changed everything correctly, he has scored 66ms.
Mine ran in 412 ms.
The acceptable range is 40-60ms.

So yea, My RadixDictionary is craptastic. So, now I am going to go back
and redo my code without the trei, without set, and just vectors, and
use STL sort and lower_bound, when I need to, then see if that mathches
up with Alf's score. After that I will try to reduce it further with a
trei implementation that allocates up front.


Here is the code I ran:

#include <algorithm>
#include <assert.h>
#include <ctype.h>
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <stddef.h>
#include <stdexcept>
#include <stdlib.h>
#include <string>
#include <utility>

/*
* Solution from Alf Steinbach on comp.lang.C++ for me to compare against
*/

using Size = ptrdiff_t;
using Index = Size;

template< class Container >
auto n_items_of(Container const& c)
-> Size
{
return c.size();
}

namespace cppx {
using std::ostream;
using std::vector;
using std::runtime_error;
using std::string;

using Byte = unsigned char;
inline auto hopefully(bool const e) -> bool { return e; }
inline auto fail(string const& s) -> bool { throw runtime_error(s); }

struct Position
{
Index x;
Index y;
};

/*

inline auto operator<<(ostream& stream, Position const& pos)
-> ostream&
{
return stream << "{" << pos.x << ", " << pos.y << "}";
}

*/

template< class Item >
class Matrix
{
private:
struct Wrapped_item { Item object; }; // Avoid problems
with vector<bool>.

Size num_rows_;
Size num_cols_;

vector<Wrapped_item> items_;

auto index_for(Index x, Index y) const
-> Index
{

return y*num_cols_ + x;

}

public:
auto id_for_position(Index x, Index y) const
-> Index
{
return index_for(x, y);
}

auto num_rows() const
-> Size
{
return num_rows_;
}

auto num_cols() const
-> Size
{
return num_cols_;

}

auto item(Index const x, Index const y) const
-> Item
{
return items_[index_for(x, y)].object;
}

auto item(Index const x, Index const y)
-> Item&
{
return items_[index_for(x, y)].object;
}

Matrix() : Matrix{ 0 } {}

explicit Matrix(Size const num_rows, Size const num_cols)
: num_rows_(num_rows)
, num_cols_(num_cols)
, items_(num_rows * num_cols)

{}

};

auto inline to_lowercase(char const ch)
-> char
{
return tolower(static_cast<Byte>(ch));
}

auto inline starts_with(string const& prefix, string const& s)
-> bool
{
return s.substr(0, prefix.length()) == prefix;
}

} // namespace cppx

namespace app
{
using namespace std;
using namespace cppx;

auto chars_from(string s)
-> string
{
string chars{ s.begin(), remove(s.begin(), s.end(), ' ') };
transform(chars.begin(), chars.end(), chars.begin(), to_lowercase);
return chars;
}

using Dictionary_iter = vector<string>::const_iterator;

void recursively_append_words_from(
Dictionary_iter const start_dict_range,
Dictionary_iter const end_dict_range,
Matrix<char> const& chars,
Position const position,
Matrix<bool>& visited,
string& word,
vector<string>& result
)
{
Size const original_word_length = word.length();
char const ch = chars.item(position.x, position.y);
word += ch;
auto const lower = lower_bound(start_dict_range,
end_dict_range, word);

if( lower == end_dict_range )
{
word.resize(original_word_length);
return;
}
/*

clog << position << " -> " << *lower << "\n";

*/

if( starts_with(word, *lower) )
{
if( word == *lower )
{
result.push_back(word);
}

visited.item(position.x, position.y) = true;

const int offsetsX[] = { 0, 1, 0, -1};
const int offsetsY[] = {-1, 0, 1, 0};

for( int offsetIndex = 0; offsetIndex < 4; ++offsetIndex )

{
Position const new_position = { position.x +

offsetsX[offsetIndex], position.y + offsetsY[offsetIndex] };

if( !visited.item(new_position.x, new_position.y) )
{
recursively_append_words_from(
lower, end_dict_range, chars, new_position,
visited, word, result
);
}
}
visited.item(position.x, position.y) = false;
}
word.resize(original_word_length);
}

void append_words_from(
vector<string> const& dictionary,

Matrix<char> const& chars,
Position const& start,

vector<string>& result
)
{

string word;
Size const num_rows = chars.num_rows();
Size const num_cols = chars.num_cols();
Matrix<bool> visited{ num_rows, num_cols };

// Flag the fence visited
for( Index index = 0; index < num_cols; ++index )
{
visited.item(index, 0) = true;
visited.item(index, num_rows - 1) = true;
}

for( Index index = 0; index < num_rows; ++index )
{
visited.item(0 , index) = true;
visited.item(num_cols - 1, index) = true;

}

recursively_append_words_from(
dictionary.begin(), dictionary.end(), chars, start,
visited, word, result
);
}
} // namespace app


class Solution
{
public:

Solution() {}

std::vector<std::string> findWords(std::vector<std::vector<char>>&
board, std::vector<std::string>& words)
{
// Sort the dictionary
std::sort(words.begin(), words.end());

// Load the matrix with a fence
cppx::Matrix<char> matrix(board.size() + 2, board[0].size() + 2);

for( Index y = 0; y < board.size(); ++y )
{
for( Index x = 0; x < board[0].size(); ++x )
{

matrix.item(x + 1, y + 1) = board[y][x];
}
}

// Solve
Size const num_rows = board.size();
Size const num_cols = board[0].size();

std::vector<std::string> results;

for( Index y = 0; y < num_rows; ++y )
{
for( Index x = 0; x < num_cols; ++x )
{
app::append_words_from(words, matrix, {x + 1, y + 1},

[Öö Tiib]

On Saturday, 11 February 2017 20:20:34 UTC+2, Christopher J. Pisz wrote:
> On 2/11/2017 12:10 PM, Öö Tiib wrote:
> > On Saturday, 11 February 2017 18:27:33 UTC+2, Christopher J. Pisz wrote:
> >> On 2/11/2017 8:10 AM, Chris Vine wrote:
> >> If I look at the top performing answer, they used a preallocated trie
> >> and didn't even bother with any OO or separation of concerns, which I
> >> guess is a requirement when we start trying to squeeze out performance
> >> and drop all concern for reusability or maintenance.
> >
> > No way. OO and separation of concerns usually improves performance.
> > However there is a "but".
> >
> > In task under hand we have only two objects. We have "boggle field"
> > B and "dictionary" D. We have only one concern that involves both
> > objects. What texts from D are present on B? So what deep OO you
> > anticipate here?
> >
> > Here can be done unneeded overengineering. That usually indeed
> > degrades performance in addition to making code more fragile and
> > harder to understand.
> >
>
> I see a objects:
> a board
> a dictionary
> a solver

Yes, I think that those "something doers" (like that "solver") are not
objects but functions or methods. So if there is a board whose concern
is to know what board is and board_solver whose concern is to solve
that board then it is "knower and doer" overengineering antipattern
for me.

>
> and in the real world possibly:
> a board::path
> a coordinate

These do not seem to help during task and are not requested by task.
What I would imagine that make sense to put forward might be "trie"
(as just generic kind of dictionary) and "solution".

>
> Now on the website mentioned, if we look at the best solutions, they did
> indeed use a trei for their dictionary, and had to create it.
>
> Rather than made a class Trei, they just implemented it as part of the
> solver.

Yes, but that design does not give any performance advantages nor
disadvantages. What gives performance advantages is limiting that trie
to 26 letters of English alphabet and things like that.

[Paavo Helde]

On 11.02.2017 21:24, Christopher J. Pisz wrote:
> On 2/11/2017 11:49 AM, Christopher J. Pisz wrote:
>> On 2/11/2017 11:30 AM, Christopher J. Pisz wrote:
>>> On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:
>>>> On 10.02.2017 01:15, Christopher J. Pisz wrote:
>>>
>>
> SNIP
>
> I got Alf's solution to run on the test site.
>
> If I changed everything correctly, he has scored 66ms.
> Mine ran in 412 ms.
> The acceptable range is 40-60ms.
>
> So yea, My RadixDictionary is craptastic. So, now I am going to go back
> and redo my code without the trei, without set, and just vectors, and
> use STL sort and lower_bound, when I need to, then see if that mathches
> up with Alf's score.

Good! Meanwhile, Alf has posted some enhancement suggestions for his
code elsethread, like replacing substr() with compare() and replacing
word == *lower check with string size comparison.

One thing that it is not clear to me - is the initial sorting of the
dictionary included in the timings?

> After that I will try to reduce it further with a
> trei implementation that allocates up front.

I suspect this might make things worse, but YMMV.

Cheers
Paavo

[Chris Vine]

On Sat, 11 Feb 2017 13:24:14 -0600

"Christopher J. Pisz" <cp...@austin.rr.com> wrote:

> On 2/11/2017 11:49 AM, Christopher J. Pisz wrote:
> > On 2/11/2017 11:30 AM, Christopher J. Pisz wrote:
> >> On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:
> >>> On 10.02.2017 01:15, Christopher J. Pisz wrote:
> >>
> >
> SNIP
>
> I got Alf's solution to run on the test site.
>
> If I changed everything correctly, he has scored 66ms.
> Mine ran in 412 ms.
> The acceptable range is 40-60ms.
>
> So yea, My RadixDictionary is craptastic. So, now I am going to go
> back and redo my code without the trei, without set, and just
> vectors, and use STL sort and lower_bound, when I need to, then see
> if that mathches up with Alf's score. After that I will try to reduce
> it further with a trei implementation that allocates up front.
>
>
> Here is the code I ran:

OK, can you deal with the two outstanding points I raised, namely:

1. Try using std::string::compare() instead of std::string::substr() in
starts_with().

2. You need to test for lower == end_dict_range in
recursively_append_words_from() before calling starts_with(), as it
could be equal to the end of the dictionary. (You also spotted this,
but haven't dealt with it.)

You have dealt with the clog point.

Chris

[Christopher J. Pisz]

On 2/11/2017 2:21 PM, Paavo Helde wrote:
> On 11.02.2017 21:24, Christopher J. Pisz wrote:
>> On 2/11/2017 11:49 AM, Christopher J. Pisz wrote:
>>> On 2/11/2017 11:30 AM, Christopher J. Pisz wrote:
>>>> On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:
>>>>> On 10.02.2017 01:15, Christopher J. Pisz wrote:
>>>>
>>>
>> SNIP
>>
>> I got Alf's solution to run on the test site.
>>
>> If I changed everything correctly, he has scored 66ms.
>> Mine ran in 412 ms.
>> The acceptable range is 40-60ms.
>>
>> So yea, My RadixDictionary is craptastic. So, now I am going to go back
>> and redo my code without the trei, without set, and just vectors, and
>> use STL sort and lower_bound, when I need to, then see if that mathches
>> up with Alf's score.
>
> Good! Meanwhile, Alf has posted some enhancement suggestions for his
> code elsethread, like replacing substr() with compare() and replacing
> word == *lower check with string size comparison.

Oh, yea I forgot to throw those in too.

> One thing that it is not clear to me - is the initial sorting of the
> dictionary included in the timings?

Yes, the initialization is part of the problem.

The site I am now testing on actually gives their data unsorted, whereas
the in the interview it was sorted.

[Chris Vine]

On Sat, 11 Feb 2017 13:24:14 -0600
"Christopher J. Pisz" <cp...@austin.rr.com> wrote:

> On 2/11/2017 11:49 AM, Christopher J. Pisz wrote:
> > On 2/11/2017 11:30 AM, Christopher J. Pisz wrote:
> >> On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:
> >>> On 10.02.2017 01:15, Christopher J. Pisz wrote:
> >>
> >
> SNIP
>
> I got Alf's solution to run on the test site.
>
> If I changed everything correctly, he has scored 66ms.
> Mine ran in 412 ms.
> The acceptable range is 40-60ms.
>
> So yea, My RadixDictionary is craptastic. So, now I am going to go
> back and redo my code without the trei, without set, and just
> vectors, and use STL sort and lower_bound, when I need to, then see
> if that mathches up with Alf's score. After that I will try to reduce
> it further with a trei implementation that allocates up front.

Posting separately (as a programmer I don't want to mix concerns!), I
hope not to sound like a cracked record but as I have said the thing you
must attend to in your own implementation is the dictionary slicing, for
which a recursive implementation is the most natural fit, or at any
rate certainly the easiest. If you can code that up with treis,
excellent, if not it won't do the business.

Chris

[Paavo Helde]

On 11.02.2017 22:28, Christopher J. Pisz wrote:
> On 2/11/2017 2:21 PM, Paavo Helde wrote:
>> On 11.02.2017 21:24, Christopher J. Pisz wrote:
>>> On 2/11/2017 11:49 AM, Christopher J. Pisz wrote:
>>>> On 2/11/2017 11:30 AM, Christopher J. Pisz wrote:
>>>>> On 2/9/2017 6:22 PM, Alf P. Steinbach wrote:
>>>>>> On 10.02.2017 01:15, Christopher J. Pisz wrote:
>>>>>
>>>>
>>> SNIP
>>>
>>> I got Alf's solution to run on the test site.
>>>
>>> If I changed everything correctly, he has scored 66ms.
>>> Mine ran in 412 ms.
>>> The acceptable range is 40-60ms.
>>>
>>> So yea, My RadixDictionary is craptastic. So, now I am going to go back
>>> and redo my code without the trei, without set, and just vectors, and
>>> use STL sort and lower_bound, when I need to, then see if that mathches
>>> up with Alf's score.
>>
>> Good! Meanwhile, Alf has posted some enhancement suggestions for his
>> code elsethread, like replacing substr() with compare() and replacing
>> word == *lower check with string size comparison.
>
> Oh, yea I forgot to throw those in too.
>
>> One thing that it is not clear to me - is the initial sorting of the
>> dictionary included in the timings?
>
> Yes, the initialization is part of the problem.

OK, then I see why the winning trie solution is the best, it probably
initializes its dictionary faster than std::sort() of a vector.

> The site I am now testing on actually gives their data unsorted, whereas
> the in the interview it was sorted.

If the initial data is already a sorted random access array, then I
suspect the std::lower_bound() based solution should have an edge.

Cheers
Paavo

[Öö Tiib]

On Saturday, 11 February 2017 23:07:02 UTC+2, Paavo Helde wrote:
>
> If the initial data is already a sorted random access array, then I
> suspect the std::lower_bound() based solution should have an edge.

Trie is doomed to win any lower_bound in anything because finding
all words that start with F from trie is O(1) and after that
finding all the words that start with FR is again O(1).

[Paavo Helde]

Yes, but this O(1) may involve a large jump in memory whereas in a
sorted vector FR is guaranteed to be near F. The big-O notation holds
better in case of large N, which incidentally means those jumps in
memory go larger.

[Christopher J. Pisz]

I did both of those things in my code like 15 posts ago :)

[Chris Vine]

On Sat, 11 Feb 2017 15:53:37 -0600

Are we at cross purposes? It wasn't in the code you posted in your
posting beginning "I got Alf's solution to run on the test site" when
you gave your timings.

Did these changes affect the results?

Take this off line and email me (without the "--nospam--") if it isn't
clear what I was talking about.

[Öö Tiib]

Not sure what you mean. You mean that the "FR" of "FRACTAL" and "FR"
of "FROG" are not far from each other in a memory in sorted vector
of strings because of small string optimization? If so then Ok.

However in trie the "FRACTAL" and "FROG" share the starting "FR"
with each other. So if we have discovered "FR" on boggle board then
that means potential for both "FRACTAL" and "FROG" immediately.
No searches needed. Trie just rules in that task. ;)

[Tim Rentsch]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> On 10.02.2017 01:15, Christopher J. Pisz wrote:
>>

>> Don't forget to turn a board Q into QU when comparing to the
>> dictionary.
>
> Oh!
>
> [..program..]

I'm enjoying your algorithms (although I must admit I find the
layout style visually jarring). If you're taking votes,
count mine to continue as you have been.

What would you do if the input were not guaranteed to be sorted?

(And a side question: when will we see the next installment of
thread AVL tree tutorial?)

[Tim Rentsch]

"Christopher J. Pisz" <cp...@austin.rr.com> writes:

> Seems to be a pretty standard interview screening test. I Googled it
> after the fact and it pops up with a page of hits. Everyone seemed to
> pretty much do what I did, yet I have been told mine performs like
> poop compared to other candidates. I can't get any feedback on why it
> might perform like poop or what could be done better.
>
> Can you guys give your suggestions?
> http://github.com/ChristopherPisz/Asking-for-Peer-Review/tree/master/Boggle
>
> I did a depth first search and compared the path thus far with words
> in the dictionary using a Radix Trei. I don't know of any other
> possible algorithm to solve the problem, or how I would implement it
> "better."
>
> C++ is getting REALLY performance orientated. I used to get a job
> within 2 days just by knowing what virtual inheritance is. Now, I
> don't really know how to "Get better"

I have some comments about the problem and then some comments
about the job search/interview area.

I didn't look closely at your program. The problem is kind of
strange, or maybe I should say surprising. Usually for this kind
of "puzzle" program, the dictionary would be fixed, and then we
would want to solve lots of different board positions. In that
scenario time taken to process the dictionary is normally deemed
negligible (within reason, of course), because what is important
to optimize is the time to solve a board.

Here the situation is the opposite of that. We have _one_ small
board, and a potentially unbounded dictionary. The program needs
to do something with each dictionary word, even if just to read
and discard it. So for this problem the emphasis should be on
doing as little work as possible for each input word. It isn't
obvious how to do that. I took a run at writing a program for
this, and it took me couple of false starts before I got one
whose performance is competitive. I guess I should give a hint
huh? Okay my hint is this: there is a lot of information in
the board state, which is small; pre-process the board state
to allow an algorithm that can skip a candidate word very
quickly, which will be true for most words. For now I think
I'll leave it at that, but feel free to ask if you want a
further hint (or hints).

About interviewing: especially when you run into a problem like
this one, but also more generally, design decisions can depend a
lot on the details of the problem. Ask about those: make sure
you know what the boundaries are for what the program has to do,
and also how the result will be judged. Of course, try to ask
smart questions more than dumb questions, but ask. Just the act
of asking should raise their estimation of you, and if there is
some insight to the questions that will be even better. And, not
to be neglected, the answers may help you write a better program,
and write it more quickly.

(I hope the above isn't too preachy or obvious. I wanted to say
it because your comments make me think you're focusing on finding
a solution more than on improving the process of how you look for
solutions. It's important not to neglect the process aspect.)

[Tim Rentsch]

> that is about the worst possible implementation. [...]

It might seem that way but actually it is not so. I wrote a
program for this problem, roughly like this pseudo-code:

read board file
prepare search structures based on board file
for each word in dictionary file
if is-on-board( word )
print word
endif
endfor

The performance is pretty good, a little bit faster than Alf's
code. (I should add that this comparison may be a bit unfair
since my program was written in C rather than C++.)

[Öö Tiib]

On Sunday, 12 February 2017 19:05:19 UTC+2, Tim Rentsch wrote:
>
> The performance is pretty good, a little bit faster than Alf's
> code. (I should add that this comparison may be a bit unfair
> since my program was written in C rather than C++.)

Why comparing performance of C program with C++ program may be is
bit unfair?

[Alf P. Steinbach]

On 11.02.2017 13:52, Chris Vine wrote:
> On Sat, 11 Feb 2017 12:53:01 +0100
> "Alf P. Steinbach" <alf.p.stein...@gmail.com> wrote:
>> On 11.02.2017 12:25, Chris Vine wrote:
>>>
>>> The only thing that struck me about Alf's implementation is that the
>>> starts_with() function is in the recursion hot path and by calling
>>> std::string::substr() might allocate memory
>>
>> I also compared strings for equality when known that one is leading
>> substring of other, instead of just comparing lengths then.
>>
>> Even for a first working version that was, well, dumb. :)
>
> I think your code was OK on the equality test.

Well, slower than necessary. :o)

> The dictionary lower
> bound has been reset on re-entering recursively_append_words_from(),
> and end_dict_range is always one past the end of the dictionary, so
> 'word' might no longer be a leading substring of *lower. (It occurs
> to me that since 'lower' could be at 'end_dict_range', this should
> probably be checked for before 'lower' is dereferenced on calling
> starts_with().)

Good point, I didn't think of that. That's a bug.

Another bug is that I intended to use a matrix with border but as I can
see it was dimensioned as (n + 1)×(n + 1) instead of (n + 2)×(n + 2).
Ugh. I can believe I did that, but then, I just cobbled something up.

I wonder if Andrey Karpov's static checked (PVS studio) could have any
chance of detecting these bugs?

For the non-dereferencable iterator, instead of extra checking one can
theoretically add a dummy zero-length word, a sentinel value, at the end
of the dictionary and pass iterator to that, instead of beyond, as
end-iterator. But that to some degree breaks the structure of the
design, e.g. the same code can't be handed a dictionary that is without
such a sentinel value, and trying it out I found that it also made for
more complicated `assert`s about the data. So, an extra check it is.

With the bugs fixed the code, minus the Matrix class definition and the
file reading & checking, now looks like this in ¹Expressive C++:

inline $function starts_with(
ref_<const string> prefix,
ref_<const string> s
) -> bool
{
$let prefix_length = length_of( prefix );
if( prefix_length > length_of( s ) ) { return false; }
return s.compare( 0, prefix_length, prefix ) == 0;

}

using Dictionary_iter = vector<string>::const_iterator;

struct Position
{
Index x;
Index y;
};

$procedure recursively_append_words_from(
const Dictionary_iter start_dict_range,
const Dictionary_iter end_dict_range,
ref_<const Matrix<char>> board,
const Position position,
ref_<Matrix<bool>> visited,
ref_<string> word,
ref_<vector<string>> result
)
{
$let original_word_length = word.length();
$let ch = board.item( position.x, position.y );

if( ch == 'q' ) { word += "qu"; } else { word += ch; }

$let it_dict_entry = lower_bound( start_dict_range,
end_dict_range, word );

if( it_dict_entry != end_dict_range and starts_with( word,
*it_dict_entry ) )
{
$let length = word.length();
if( length >= 3 and length == it_dict_entry->length() )

{
result.push_back( word );
}
visited.item( position.x, position.y ) = true;

for( $each dy $in range( -1, +1 ) ) for( $each dx $in
range( -1, +1 ) )

{
Position const new_position = {position.x + dx,
position.y + dy};
if( not visited.item( new_position.x, new_position.y ) )
{
recursively_append_words_from(

it_dict_entry, end_dict_range, board, new_position,
visited, word, result
);
}
}

visited.item( position.x, position.y ) = false;
}
word.resize( original_word_length );
}

$procedure append_words_from(
ref_<const vector<string>> dictionary,
ref_<const Matrix<char>> board,
ref_<const Position> start,
ref_<vector<string>> result
)
{
string word;
$let board_size = board.size();
Matrix<bool> visited{ board_size };

for( $each i $in i_up_to( board_size ) )

{
visited.item( i, 0 ) = true;
visited.item( 0, i ) = true;

visited.item( i, board_size - 1 ) = true;
visited.item( board_size - 1, i ) = true;
}

recursively_append_words_from(
begin( dictionary ), end( dictionary ) - 1, board, start,
visited, word, result
);
}

$procedure cpp_main( ref_<const vector<string>> args )
{
// Using non-macro pure C++ `fail` to get unadorned message in
exception:
$hopefully( n_items_in( args ) == 3 )
or fail( ""s << "Usage: " << args[0] << " DICTIONARY

BUBBLEBOARD" );

vector<string> const dictionary = load_dictionary( args[1] );
Matrix<char> const board = load_bubble_board( args[2] );

assert( is_sorted( $items_of( dictionary ) ) );

$let board_size = board.size(); $let n = board_size - 2;
assert( n > 0 );
vector<string> words;
for( $each y $in i_up_to( n ) ) for( $each x $in i_up_to( n ) )
{
append_words_from( dictionary, board, {x + 1, y + 1}, words );
}

sort( $items_of( words ) );
$let start_of_duplicates = unique( $items_of( words ) );
words.erase( start_of_duplicates, end( words ) );
for( $each word $in words ) { cout << word << "\n"; }
}

Cheers!,

- Alf

Notes:
¹ It's a little language extension library I couldn't resist creating
after the “Fun with macros” posting here in clc++. The macros, supported
by various templates, currently are defined as follows:
# define $e ::progrock::expressive
#
# define $static_assert EXPRESSIVE_STATIC_ASSERT // Single
arg like C++17.
# define $funcname EXPRESSIVE_FUNCNAME // Qualified
__func__.
# define $noreturn EXPRESSIVE_NORETURN // MSVC
lacks [noreturn].
#
# define $function auto
# define $procedure void
#
# define $simple_pure_function constexpr $function
# define $compile_time_value static constexpr
#
# define $an_expected( Type, expr ) \
( \
[&]{ $static_assert(( ::std::is_same<Type,
decltype((expr))>::value )); }, \
expr \
)
# define $as static_cast
# define $let auto const
# define $let_mutable auto
# define $name auto&
# define $readonly_name auto const&
#
# // Range-based `for`, because deduced `auto`can't be expressed via
e.g. `ref_`:
# define $each_value auto const
# define $each_ref auto&
# define $each auto const&
# define $in :
#
# define $repeat do{
# define $until(e) }while(not(e))
#
# define $when( condition ) condition?
# define $use( value ) value :
# define $default_to( value ) value
#
# define $_generate_using_declaration_in( ns, name ) using ns::name;
# define $using_from_namespace( ns, ... ) \
MM_APPLY_WITH_FIXED_ARG( $_generate_using_declaration_in, ns,
__VA_ARGS__ ) \
static_assert( true, "- just to support a semicolon after this -" )
#
# define $using_all_from_namespace( ns ) \
using namespace ns
#
# define $using_nested_namespace( ns, nested ) \
namespace nested = ns::nested
#
# define $lambda_using( ... ) [__VA_ARGS__]
# define $byref( object ) &object
# define $byval( object ) object
# define $capture_byref &
# define $capture_byval =
#
# define $lambda $lambda_using()
# define $lambda_using_references $lambda_using( $capture_byref )
# define $lambda_using_values $lambda_using( $capture_byval )
#
# define $hopefully( e ) $e::hopefully( e )
# define $fail( ... ) $e::fail_from_location( \
$as<std::string>( $funcname ), __VA_ARGS__ \
)
#
# // Can't use unqualified type builders here, hence the `$e` qualifiers.
# // The `(void)` casts avoids unused-warnings when these names are
unused.
# // Commonly `n_args` is named the more cryptic `argc` (with `c` for
`count`),
# // and commonly `args` is named the more cryptic `argv` (`v` for
`values`).
# // To use `n_args` and `args` you can pass a lambda as macro argument.
# // The macro is variadic to allow specification of a fatal error
handler.
# define $start_with( ... ) \
$function main( const int n_args,
$e::raw_array_<$e::ptr_<char>> args ) \
-> int \
{ \
(void) n_args; (void) args; \
return $e::default_startup( __VA_ARGS__ ); \
}
#
# // This is just an extra-convenience wrapper and doesn't support a fatal
# // error handler (modern C++ requires at least one argument for a
`...`).
# define $start_with_arguments( main_procedure ) \
$start_with( $lambda_using_values() \
{ \
main_procedure( {args, args + n_args} ); \
} )

[Alf P. Steinbach]

On 13.02.2017 00:21, Alf P. Steinbach wrote:
> recursively_append_words_from(
> begin( dictionary ), end( dictionary ) - 1, board, start,
> visited, word, result
> );

A new bug, the “-1” here, weaseled its way into the code as a result of
exploring solutions of the dereferencing-of-beyond-array-iterator bug.

It's like bugs create new bugs.

Like they procreate!


Cheers!,

- Alf

[Gareth Owen]

Tim Rentsch <t...@alumni.caltech.edu> writes:

> Here the situation is the opposite of that. We have _one_ small
> board, and a potentially unbounded dictionary. The program needs
> to do something with each dictionary word, even if just to read
> and discard it

A digression : this reinforces your later point about asking smart
questions. Here asking about the problem parameters is key. If we know
nothing about the dictionary, we have to look at every word in it.

If we know its sorted, however ..

(In the world of books, being sorted is an important property of
anything calling itself a dictionary)

[Tim Rentsch]

Gareth Owen <gwo...@gmail.com> writes:

> Tim Rentsch <t...@alumni.caltech.edu> writes:
>
>> Here the situation is the opposite of that. We have _one_ small
>> board, and a potentially unbounded dictionary. The program needs
>> to do something with each dictionary word, even if just to read
>> and discard it
>
> A digression : this reinforces your later point about asking smart
> questions. Here asking about the problem parameters is key. If we know
> nothing about the dictionary, we have to look at every word in it.
>
> If we know its sorted, however ..

Right. In this particular case I'm not sure that knowing
the input is sorted provides any help. But I agree with
your point generally.

[Tim Rentsch]

Because programming in C you don't get distracted by wanting to
use all that template crap. ;) okay j/k.

Somewhat more seriously, being in a C++ environment naturally
nudges one's thinking towards the built-in maps, sets, vectors,
etc, and sometimes that interferes with run-time speed. My first
few attempts at writing this code were done in C++. I picked my
structures carefully, looking at the time guarantees for the
various types and methods. Despite that the performance wasn't
that good - not bad, but not good either. I thought about the
problem some more and came up with a different approach. The new
approach didn't need any STL types, and although I didn't try it
I think they would have gotten in the way more than helping. The
code I wrote uses fixed arrays, does no allocation, and in the
fast path uses pointer manipulation rather than array indexing.
No doubt all this could have been done in C++, but it would have
looked very un-C++-like. Or to say it another way, the primary
focus was speed rather than "nicely abstract" code, and I think
that was easier to accomplish in this case in C than it would
have been in C++.

Does that all make sense?