java - Iterative Depth First Search To Find A String (2D Array) -

-

i'm trying create iterative approach boggle game. class contains fields 2d array of strings called "board" , has 2d array of booleans called "havevisit". method calls test 2 loops through whole board, finding positions of first character of target string, passes coordinates test2 method, returning list holding coordinates.

the return1index method takes 2d array coordinate @ creates int representative of coordinates corresponding 1d array it. return2dindex opposite , returns int array holding 2 coordinates.

public list<integer> test2(int row1, int row2, string findme){      string temp = findme;      list<integer> output = new arraylist<integer>();      if (board[row1][row2].charat(0) != findme.charat(0))         return output;      havevisit = new boolean[size][size];      int row = row1;       int column = row2;                                          output.add(return1dindex(row, column));                 havevisit[row][column] = true;                          //for each letter in string      for(int j = 0; j < temp.length(); j++)          //for every column , row combination         (int x = row - 1; x < row + 2 ; x++)            (int y = column - 1; y < column + 2 ; y++)                //if index valid , not visited               if (x > -1 && y > -1 && y < size && x < size && !havevisit[x][y])                  //if output same size string, return                  if(output.size() == findme.length())                     return output;                   //if character in board matches char we're looking                  if(board[x][y].charat(0) == temp.charat(j))                  {                     havevisit[x][y] = true;                     output.add(return1dindex(x, y));                      //update row , column indices                     row = x;                     column = y;                  }               }            }      return output;   }

for reason method works 50% of time. method works fine finding letters when they're arranged left right or top bottom, finding words right left or bottom top never works except 1 case: when you're searching string of length 1 or 2, method works.

i have working recursive solution wanted try way. thoughts why wouldn't work?

edit: code works right left, still not work when attempting search upwards.

i don't know problem is, there few suspects:

  • you updating row , column indices while checking neighbors. removing element array while iterating through it: it's defined, has tricky semantics. suggest either bailing out (greedy algorithm) or keeping stack of matches (deeper search, requires saving stack of visited cells too).

  • the fors missing opening braces, closing braces there, suggesting missing code.

  • i'm not familiar boggle, isn't possible letter have 2 similar neighbors, axa? doing output.add(return1dindex(x, y)); may outputting 2 ways same letter. may end output longer findme.

my suggestion follow more standard format of depth-first search while iron out bugs. wikipedia has non-recursive pseudocode implementation, example: https://en.wikipedia.org/wiki/depth-first_search#pseudocode .


Comments

Post a Comment

Popular posts from this blog

python - jinja2: TemplateSyntaxError: expected token ',', got 'string' -

-
i new jinja2 , having issue using python regular expression (re). in following code bold lines have error string in them. {% block content %} <div class="container"> {% l in lines %} {% if re.search(r"error", l) %} {# <<< throws error #} <b> {{ l }} </b> {% else %} {{ l }} <hr> {% endif %} {% endfor %} </div> {% endblock %} the re.search above throws following error: jinja2.exceptions.templatesyntaxerror templatesyntaxerror: expected token ',', got 'string' raw python code not supported in jinja2 template syntax. {% if re.search(r"error", l) %} replace line with {% if "error" in l %} can fix problem. if logical condition more complicated, should consider defining own custom filters (which can call python code) or complicated things in view layer. go check global namespace .
Read more

Qt4: how to send QString inside a struct via QSharedMemory -

-
i have struct struct control_data{ int column_number; qstring cell; }; i need send thread of qsharememory. read can't because qstring contains pointers inside. other ways? you have serialize struct byte array. can convert qstring const char* this: mystring.tostdstring().c_str(); but serializing qstring should work. the first step serialize struct qdatastream using qt, example here . then once struct can read , written can pass shared memory. a complete example of using qsharedmemory can found here . here relevant code: // first, test whether shared memory segment attached process. // if so, detach if (sharedmem.isattached()) { sharedmem.detach(); } ... qbuffer buffer; buffer.open( qbuffer::readwrite ); qdatastream out( &buffer ); out << youstruct; int size = buffer.size(); // size of int + size of qstring in bytes if ( !sharedmem.create( size ) ) { return; } // write shared memory sharedmem.lock(); char *to = (char*...
Read more

node.js - NodeJS remote terminal to Dropbear OpenWRT-Server -

-
i wandering whether there valid solution have remote terminal openwrt-box out of nodejs-app? connecting terminal works: ssh -i ~/.mykeys/id_rsa root@192.168.178.39 busybox v1.23.2 (2015-04-22 23:25:48 utc) built-in shell (ash) root@openwrt:~# the only interactive ssh solution nodejs doesn't interactive part described in readme.md following: var client = require('ssh2').client; var conn = new client(); conn.on('ready', function() { console.log('client :: ready'); conn.shell(function(err, stream) { if (err) throw err; stream.on('close', function() { console.log('stream :: close'); conn.end(); }).on('data', function(data) { console.log('stdout: ' + data); }).stderr.on('data', function(data) { console.log('stderr: ' + data); }); stream.end('ls -l\nexit\n'); }); }).connect({ host: '192.168.100.100', port: 22, username...
Read more