• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Rob Spoor
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Junilu Lacar
  • Tim Cooke
Saloon Keepers:
  • Tim Holloway
  • Piet Souris
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Frits Walraven
  • Himai Minh

Matrix problem

 
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks a lot, Mike!

I was so intent upon understanding what the problem wanted and seeing if I could get it right, that I forgot my basic Java crap.
I've been 99% working with Collections and Streams since coming back to Java.
It is important to remember for the cert exams, however.

Also, because so much of the code is creating the different test cases, it shortened the whole program up a LOT.

Regarding my take on it, is that they want to know how many ADDITIONAL distinct total paths open up by adding a single 1 anywhere in the matrix where there is currently a 0.
I did a lot of extra work to get that number correct, which is often very high, because I thought about the other interpretation and decided it made no darn sense.

It is moderately uncool that the OP didn't mention where this came from, since tomorrow is the last day I think they are taking entries, and I did 99% of the work needed to enter...

Lastly, my take on BFS.  I think BFS is so often used on problems that SOUND a little like this because they are usually looking for THE ONE SHORTEST PATH.
In a problem like this, where the hard work is enumerating and counting up all the possible paths, based on a limited number of possible "tunneling thru walls", I thought it only unnecessarily complicated and confused things.

Lastly, tho the problem as posed only gave us ONE opportunity to break thru walls, I think my code would work if they changed the problem to "sometimes, you can break thru two or three or four walls..." I thought about it on a long walk with my dog, and he agreed that it made sense to code for the general case.  I didn't write any test cases that did other than one bulldozing, but I didn't see anywhere that looked like that would break.

Without optimizations, all of which would be premature because I can't see their test cases, my code looked like this:



I see one error.  It recognizes that it has no clear path if the very first starting square is already a blocker, but somehow computed an incorrect number of paths opening up by bypassing just that one blockage.

There may be more errors, I didn't see them, but I was rushing a bit, and spending a lot of time counting possible paths, because they can go up FAST once you have a decent sized matrix:
For playfield of:
[1, 0, 0]
[1, 0, 0]
[1, 0, 1]
Is there a clear path with no blockers?
No, but number of ways to win passing a max of 1 blockers per path to target is:
1
For playfield of:
[1, 0, 0]
[1, 0, 0]
[1, 1, 1]
Is there a clear path with no blockers?
TRUE
For playfield of:
[1, 1, 1, 1]
[0, 0, 1, 0]
[1, 1, 1, 1]
Is there a clear path with no blockers?
TRUE
For playfield of:
[1, 1, 1, 1]
[0, 0, 0, 0]
[1, 1, 1, 1]
Is there a clear path with no blockers?
No, but number of ways to win passing a max of 1 blockers per path to target is:
4
For playfield of:
[1, 1, 1, 0, 0]
[0, 0, 0, 1, 1]
[1, 1, 0, 0, 1]
Is there a clear path with no blockers?
No, but number of ways to win passing a max of 1 blockers per path to target is:
2
For playfield of:
[1, 0, 1, 1, 1]
[0, 1, 1, 1, 1]
[1, 0, 1, 1, 1]
Is there a clear path with no blockers?
No, but number of ways to win passing a max of 1 blockers per path to target is:
32
For playfield of:
[0, 0, 0]
[1, 0, 0]
[1, 1, 1]
Is there a clear path with no blockers?
No, but number of ways to win passing a max of 1 blockers per path to target is:
4
For playfield of:
[1, 0, 0]
[1, 1, 0]
[1, 1, 0]
Is there a clear path with no blockers?
No, but number of ways to win passing a max of 1 blockers per path to target is:
2
For playfield of:
[1, 0, 0]
[0, 0, 0]
[1, 0, 1]
Is there a clear path with no blockers?
FALSE
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Houssam:

Thanks for replying!

I hope you did well on the interview.

I have posted solutions here that I came up with AFTER fumbling on a live interview, like, in an hour I could come up with something beautiful I want to carry around and show everyone I meet, but I only had 22 minutes on the live coding challenge and was scrambling like a maniac.

I went the opposite direction from you, I tried to write code that would solve every single potential problem of that form, even if some would take a REALLY, REALLY long time to complete.

Mike had some interesting tips on not just making the code faster, but how to avoid Brute Forcing it.

I most definitely Brute Force the "How many paths could you come up with by pushing thru a block?" problem, I try every single possibility that can't be ruled out.

Often, the best solutions come from starting with Brute Force and then finding special cases that can save time, other times (I mean you HackerRank) even Brute Force solutions will still work if coded very efficiently...then again, often not.

Most of the interviews I go on nowadays are asking "Can you mentor Junior Developers??  Can you do code reviews of problematic code without hurting the coder's feelings?  Can you help un-confuse confused people?"  These are all highly valuable skills that I find CodeRanch/JavaRanch helps me a lot in.

I will re-iterate that I think that coming up with Great Test Cases is a horribly undervalued skill, and the single thing I love the most about HackerRank (Okay, I also love that they have Java 15 as an option finally).

It is so, so, SO easy to think you have solved a problem "Nailed It!" that you have failed to think of many edge and corner cases on, where you will run out of stack space (a big risk for the solution as I've posted it for Very Large Matrices), out of heap space, consume too many CPU cycles or, in fact, generate totally bogus results that look really good, and are very hard to distinguish from being correct, except that 27396 other people have tried the same thing on HackerRank and reported any problems with test cases being wrong, so that you know the problem is (almost certainly) you if you fail some of them.  I have had things that I needed to switch languages for, because the standard scale factor they use (like, C++ is twice as fast as Java, and ten times as fast as Python) didn't work at least for the idiom I was using.  Bringing the identical algorithm over to the other language with its different fudge factor resulted in Sweet Success.

I always felt weird when people would say something similar in chat rooms, but I think I'd prefer doing most of our interaction on here for now.  I've been studying, interviewing and often posting about whatever I learn and experience, mostly here.  Not that I can resist commenting when people put wrong information in tutorial videos, because I can't.
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Doh!!

One more thing...

It might be interesting if you were able to confirm the correct interpretation of the problem.

I believe that the hard part of it was that they were asking for not the path itself, but the distinct number of different paths from start to finish in total that would be opened up by removing exactly one blocker.  i.e. 5 if you change this 0 to a 1, plus 8 if you change THAT 0 to a 1 and an additional 1 if you go change that OTHER 0 to a 1 for a total of 14.

That's what my code claims to output.

The only case I could SEE I got wrong was when you hit a 0 right on your front doorstep, but there may be others I missed.

I spent most of the time I spent on this writing the test cases and comparing my results to what I thought was correct, at least for my interpretation of what was being asked.

Cheers!
 
Master Rancher
Posts: 4002
52
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jesse Silverman wrote:Regarding my take on it, is that they want to know how many ADDITIONAL distinct total paths open up by adding a single 1 anywhere in the matrix where there is currently a 0.
I did a lot of extra work to get that number correct, which is often very high, because I thought about the other interpretation and decided it made no darn sense.


I agree that "number of distinct paths" is really the only interpretation that makes sense.  I think in my case, I was thinking about the problem for a bit, thought of a solution I liked, and then was annoyed when I re-read the problem and found it didn't match what I was thinking of.  Ah, well.

Though it's also very strange that they only care about the number of paths in the case where there is no direct path, but you can expose one or more by changine a 0 to 1.  Why not calculate the number of paths where there is a direct path too?  It also creates a situation where the optimal algorithms are quite different - a brute force counting of paths is needlessly inefficient for the first problem, finding if a direct path exists.  But it's probably needed, for counting distinct paths.  (Though a hybrid of these two may be even faster.)  I guess if the matrix size is small, it doesn't matter.  But if this were an Advent of Code challenge, I guarantee you that part 2 of the challenge would be something that forces you to upgrade to a more efficient algorithm.



Jesse Silverman wrote:Lastly, my take on BFS.  I think BFS is so often used on problems that SOUND a little like this because they are usually looking for THE ONE SHORTEST PATH.
In a problem like this, where the hard work is enumerating and counting up all the possible paths, based on a limited number of possible "tunneling thru walls", I thought it only unnecessarily complicated and confused things.


Agreed, that's basically how I got there, as described above.

Jesse Silverman wrote:Lastly, tho the problem as posed only gave us ONE opportunity to break thru walls, I think my code would work if they changed the problem to "sometimes, you can break thru two or three or four walls..." I thought about it on a long walk with my dog, and he agreed that it made sense to code for the general case.  I didn't write any test cases that did other than one bulldozing, but I didn't see anywhere that looked like that would break.


Yes, that's a good point.  Though I think we can similarly generalize my approach with Dijkstra's algoritm to handle an arbitrary number of crossings through a 0.  So first you find all points that are reachable from the upper left corner with no changes, then you find all the additional points reachable with one change, then the points reachable with two changes, etc, stopping when you reach the lower right corner.

Of course, that misses the part about counting distinct paths.  But, you can use the Dijstra shortest path to constrain the search space, so you only look for solutions that go through the crossing points identified in the shortest path solution.

If the problem space is big enough to justify it.  Which, yes, is premature.  But again, I refer you to Advent of Code challenges.

Later I will try to look at your solution more.  Cheers!
 
Saloon Keeper
Posts: 4612
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Coming back to the problem... interesting stuff! I'm still thinking about my idea of distances between paths, and looking for an efficient way to calculate that. Anyway, the whole stuff somehow reminded me of Project Euler problems 81, 82 and 83.
 
Saloon Keeper
Posts: 8455
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Dang, Carey!
Some advanced stuff in there..in particular both markPath() and countPossiblePaths().

Before I (and others) look at it in more detail (or at the same time), does this use some form of Dijkstra's algorithm?
 
Carey Brown
Saloon Keeper
Posts: 8455
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jesse Silverman wrote:Dang, Carey!
Some advanced stuff in there..in particular both markPath() and countPossiblePaths().

Before I (and others) look at it in more detail (or at the same time), does this use some form of Dijkstra's algorithm?

I'm not familiar with that algorithm, just knocked out the code. I did just notice a special case that the count method doesn't handle and that is if the lower-right corner is '0' and there is a path to the beginning ('B') one away from it.
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I realize that one of the points of contention in interpreting the problem was whether they intended the input to be an int[][] or it would be perfectly legitimate to make it a char[][].

Either way, my first departure, later corrected of interpreting it as a boolean[][] left me out in the cold as far as using a nifty solution like you used:


To de-clutter all my "Gee, is that position in bounds?" checks littering my source.
That's not even the coolest part of your solution, but it does make the source much cleaner since you have the semantics of "Go mark that square, if there even is a square there, this line doesn't even have to care about that."
 
Mike Simmons
Master Rancher
Posts: 4002
52
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Carey's code is not Dijkstra's algorithm - it's the fleshed out version of the solution I sketched out above.  Look for everything directly connected by "1" to either endpoint, then look for points that are connected via one "0" to points found in the previous step.  

The Dijkstra-like generalization to that would be to then look for everything not previously found but directly connected by "0" to the points found in the previous step, and then look for anything new connected by one more "1", and then look for anything new connected by one more "0", etc.  So you search outward in ever-growing "circles" (sorta) from either endpoint, until your two search areas meet up, and you've found the shortest route (or a shortest route) connecting the two endpoints.  There are tricks to doing this efficiently - you maintain a list of points in the "frontier" at any moment, and use a priority queue to rank them by distance from either endpoint.  So at any given time, the next point you search will be whatever is closest to either endpoint, that you haven't already searched.  For this problem, "distance" is measured in how many "0" points you travel through, since each "1" is basically free.
 
Carey Brown
Saloon Keeper
Posts: 8455
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The requirements for how you are supposed to count the number of possible connections through a single '0' is a bit vague. Take this for example:
Connecting the beginning path and the ending path through the '0' at matrix[2][2] could be counted as 1 connection or 4 connections depending on how you interpret it.

Here's the method with two IFs added to handle the special cases of the corners being '0'.
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
One silly thing, that I bet is right.

Mike was wondering why the question was posed so oddly, I was wondering where the question came from since I couldn't find it anywhere, thought my Google duck-duck-go foo was missing some mojo.

It turned out that it was from an interview question, which was NOT intended to be testing search engine skills, so that is why the question was posed so that there would be a million hits on canned answers of how to do it (which I didn't look for, because I get a LOT of "closed book" interviews and needed to practice relying on my own wits), but none of them would be cut-and-paste answers for the question.

It makes me think back to a lot of odd twists and turns and weirdness I've seen on interview questions, they want to make sure you can think on your feet and aren't just great at memorizing canned solutions to well-known problems (not that there is anything wrong with THAT).

That said, they could have done a much better job of fully specifying various parameters of the requested solution.  Each time I read it, I can imagine the requirement for the matrix to be composed of either int or String elements.  One (of multiple) things that annoyed Norm off the thread was a lack of clarity about how that was supposed to be implemented.

Besides algorithms, some of the issues this brought up was the importance of clarifying ambiguous problem statements, and possibly, the level of help to be offered on still active interview questions.  I have only posted here questions I already answered, or almost answered, on already completed interviews, basically saying "I did it like this -- does this suck or is it okay?"  The answers were, "Well, that works, but something like this might be nicer..."

I am simultaneously proud of, and embarrassed by my solution.  It was 100.00% my own work, I consulted no outside sources (except that I forgot how to neatly initialize 2-d arrays), I spent 90% of time cooking up test cases and validating that they were giving the right answers (an undervalued skill), and I think the code was fairly readable.  On the other hand, your solution is much neater and scales better.

So many times interviewers have said "The most important part is that we see you can get a correct answer, that you will know whether your answer is correct or not, and we want to see how you think when you are trying to solve problems."  So by those standards I think I did what my target is for interviews.  I'll be studying the already posted solutions and any further to come because it is an interesting class of problem, at least to me.

I already had said many times my favorite part of HackerRank is that they already cooked up all the test cases for you, just click SUBMIT and you know how good your solution actually is, but if I didn't appreciate that enough before, I sure would now.
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:The requirements for how you are supposed to count the number of possible connections through a single '0' is a bit vague. Take this for example:
Connecting the beginning path and the ending path through the '0' at matrix[2][2] could be counted as 1 connection or 4 connections depending on how you interpret it.



I thought about it a bit, and then decided "from real life" that there are indeed 4 distinct new possible pathways added by the change, and coded accordingly, if not very elegantly.
 
Carey Brown
Saloon Keeper
Posts: 8455
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jesse Silverman wrote:

Carey Brown wrote:The requirements for how you are supposed to count the number of possible connections through a single '0' is a bit vague. Take this for example:
Connecting the beginning path and the ending path through the '0' at matrix[2][2] could be counted as 1 connection or 4 connections depending on how you interpret it.



I thought about it a bit, and then decided "from real life" that there are indeed 4 distinct new possible pathways added by the change, and coded accordingly, if not very elegantly.

When I thought about it I came up with the opposite opinion. For instance:
How many paths does this have from the upper-left corner to the lower-right corner? Lots and lots. I couldn't quit fathom a way to compute them all. And the instructions say for a '0' when I'm pretty sure they mean 'foreach'. Then is the count the sum of them all or just the max of the one with the most paths?
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:
When I thought about it I came up with the opposite opinion. For instance:
How many paths does this have from the upper-left corner to the lower-right corner? Lots and lots. I couldn't quit fathom a way to compute them all. And the instructions say for a '0' when I'm pretty sure they mean 'foreach'. Then is the count the sum of them all or just the max of the one with the most paths?



I wonder if we will ever find out via. the OP (if they even tell him) what was actually intended.
I found the hardest part of testing to be some like that.  I had one of my answers come up as 32, I only saw 7 at first glance.
I kept looking, and they were like Clowns Coming Out of a Volkswagen, I kept seeing more and more and more that were indeed, legitimately distinct paths.

All questions about "What did he or she mean when they said?" can only be answered authoritatively by the person who originally wrote or said something.
It seemed to me that clearly they wanted all of them counted, just as if we had enumerated them as Paths, e.g. [0,0][0,1],[1,1]....[5,5] but without printing them out.

This all shows the value of both clear description and non-trivial samples shown on any programming problems.
Intelligent people are going to read less clear and full instructions differently from each other.
Note: HackerRank is usually good about this.  When they once in a while aren't, their big suite of test cases resolves the ambiguity after the fact, i.e. one interpretation makes all test cases pass if coded correctly, the other does not.  So in light of that this question was not great.

I can imagine, with my perverse imagination, a test filled with nothing but such types of questions, designed to select for those people who can turn draft specifications into production ones.  You don't actually have to code anything, just find and resolve the defects in each incompletely or ambiguously worded spec.
 
Ranch Hand
Posts: 165
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Jesse
Sorry for the delay, I was tired in recent days, although, I've passed two tests, the first one that characterized by the matrix problem, I've solved all questions except the matrix problem, I'm currently looking for an internship to be associated with it to flourish my skills, I've got accepted by one to pass the video test (interview) tomorrow,

Thanks, Jesse, I'm really thrilled that the Coderanch forum has a member like you

I wish success and best life
 
Houssam El
Ranch Hand
Posts: 165
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Jesse
I think that the best solution for this issue is BFS, I've succeeded to visit each point or location in the matrix with respect to the direction moves that have been revealed in the description of the problem, however, I struggled to check each point pop out if it equals 1, in addition, how would I flip 0's to 1's during iterations in the path with the respect of the directions moves (up, down, right, and left)
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Houssam El wrote:@Jesse
I think that the best solution for this issue is BFS, I've succeeded to visit each point or location in the matrix with respect to the direction moves that have been revealed in the description of the problem, however, I struggled to check each point pop out if it equals 1, in addition, how would I flip 0's to 1's during iterations in the path with the respect of the directions moves (up, down, right, and left)



I still don't see how BFS is helpful for a solution that needs to count "all possible paths".
BFS is very useful when you may have MANY paths, and you don't care about ANY of them except the SHORTEST POSSIBLE.
When that is the case, BFS saves you the work of going down a very, very long successful path that is of no interest because it is not the shortest.
If you know that there is only one path, or you are trying to determine if there is exactly one or not, it just seems to me that BFS is an unnecessary complication in that case.
[It is important to know how to do BFS anyway, of course, but I prefer depth-first with backtracking in the "does a path even exist?" case]

Carey's solution is very interesting, but I now realize from staring at the code, that it very cleverly and elegantly finds the number of '0' cells that would add one or more distinct paths were they to be changed to a '1' and thus unblocked.  This number will always be equal to or less than the number of resulting distinct new paths thru that would be created by such a move.

I thought they truly wanted the answer of "How many distinct paths would result?" which is a lot more work to compute than "How many of the 0's would yield one or more paths if they were changed to 1's?"

So Carey and I answered two different problems.  The problem statement is really unclear on that point, in both of our opinions, and we guessed differently at what they must be wanting.
 
Houssam El
Ranch Hand
Posts: 165
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Jesse
BFS allows you to traverse the path from the top left to the bottom rof the matrix (as shown below), the exercise doesn't ask you to count all possible paths on the matrix(counting the possible paths on the matrix is easy), however, it wants you to determine a certain path, and if this path filled with 1's return true otherwise you program should flip 0's to 1's along traversing the path.

 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Houssam El wrote:@Jesse
BFS allows you to traverse the path from the top left to the bottom right of the matrix (as shown below), the exercise doesn't ask you to count all possible paths on the matrix(counting the possible paths on the matrix is easy), however, it wants you to determine a certain path, and if this path filled with 1's return true otherwise you program should flip 0's to 1's along traversing the path.



I didn't think counting all possible distinct paths thru a matrix is easy, but that could be looked up, there is some standard formula.  So, in that sense it is perhaps easy.  My graph theory is a bit weak.

But my solution, while brute force and slow, if it doesn't run out of stack space (which could be increased for an invocation of the JVM) and the user doesn't get impatient and kill it, will always return TRUE if there exists at least one path with no 0 blockers.

Additionally, with the same caveats, it will return the number of distinct paths that could be created by changing any single '0' to a '1' on the matrix.
To be more specific, it returns the total number of paths that would be unblocked by changing each zero to a 1 in isolation, then summing that up.
I wrote it to be general, so that it would find the same by changing up to 2, changing up to 3 or changing up to well, m x n '0' chars to a '1' and counting the number of distinct paths in that case.
It doesn't scale well for very large matrices, but I think it would eventually give the correct answer for any case for which it doesn't run out of resources or time...

Carey's solution either returns true or the total number of 0 elements that would result in at least one successful path if they were changed to a 1 in isolation, which is much less work and much easier.  It does not tell you how many distinct paths would result from such changes.  It now seems that we might logically infer that was what was really desired, just because it is so much easier.

It remains unclear whether the problem was intentionally very hard, or just seems very hard because it was written so ambiguously.
If they told you that you are free to ask questions before you solve it, it may be an exercise in clarifying an ambiguous problem statement.
 
Houssam El
Ranch Hand
Posts: 165
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Jesse,
Counting all paths from the top left to right bottom is easy even without using BFS, moreover, I don't think that Brute Force could help here, according to my knowledge BRUTE FORCE could be used in computing, I'm still learning algorithms and data structures, you know that the field of algorithms and data structures is hard to master it you should practice more in order to get an acceptable level

if you want a program that prints available paths in the matrix I can write one, with two methods using Dynamic Programming, in short PP, and other one using Recursion.
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Independent of the algorithm, I am going to completely agree with Piet that it is very odd to be representing your points as a string value of:
"5,7" etc.

That is very hard to work with.

I find it somewhat difficult to tell if your solution only needs a minor tweak to work or is nowhere remotely near correct.

Looking harder at it, it seems it is likely further off than I was thinking earlier.

---> Anyway, don't stress too much over this one problem. <--- * * * most important thing I said in this whole thread * * *

There are several things to learn here, possibly the most important one about clarifying ambiguous and fuzzy problem statements.

But I also don't like the choice of a "3,2" as a way to represent the cells/squares of the matrix, it makes the rest of the code harder to work with and harder to read.
I do admit you get .equals() and .hashCode() for free because they are String values, but that is not hard to implement.
 
Houssam El
Ranch Hand
Posts: 165
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Jesse, I've succeeded to represent it in the following form "5.4", however, I struggled to flip 0's to 1's, it doesn't matter if I didn't succeed to solve this problem, but I think God that I've achieved 50% of the problem, the recruiter may take this in consideration, I wish that,
You going to encounter many problems similar to this one, and you would know how to deal with them,

who never struggle is the one who never tried something new, Albert Einstein said,



Thanks, Jesse for everything, I genuinely appreciate your help, much relief to me
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Houssam El wrote:@Jesse,
Counting all paths from the top left to right bottom is easy even without using BFS, moreover, I don't think that Brute Force could help here, according to my knowledge BRUTE FORCE could be used in computing, I'm still learning algorithms and data structures, you know that the field of algorithms and data structures is hard to master it you should practice more in order to get an acceptable level

if you want a program that prints available paths in the matrix I can write one, with two methods using Dynamic Programming, in short PP, and other one using Recursion.



'Brute Force' whenever I said it just means a straight, naive implementation of something that is technically correct but doesn't use any Deep Insights into the problem to avoid excessive compute costs.
It is the antonym to 'Very Clever Solution', which by realizing certain characteristics of the problem, finds the same result with 'Much Less Work'.  The terms were not specific to this problem type, but more general.

If you find counting all paths from top left to right bottom to be easy, why not just "do that" keeping track of number of 0's you hit.  If it is ever about to exceed 1, then that path doesn't work, and it is time to consider the next one.  That is what my solution did, which is straightforward and dumb but seems to work for my interpretation of the problem, but looks like it wouldn't scale well for very large matrices (just in terms of stack space and compute time, I believe it will always generate a correct answer if it doesn't run out of either).

It is still possible that my solution doesn't work right, even for pretty small matrices, I don't know how much attention people paid to it.
It is also possible that Carey's interpretation of what they were asking for is correct and mine was wrong, or possibly, even that both of ours was wrong (I can think of a third interpretation of the number they were asking for, hinted at by Carey in his comments -- what is the max number of resulting paths that would be opened by removing any single 0 blocker by changing it to a 1?)
 
Jesse Silverman
Bartender
Posts: 1064
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Houssam El wrote:

Thanks, Jesse for everything, I genuinely appreciate your help, much relief to me


Hopefully not all Comic Relief.
You're very welcome!  If you succeed in finding out which interpretation of what they were asking for was the intended one, let us know.
In Debate Team practice, I could pick any of the three and argue that is "Clearly what the Plaintiff was asking for!" that does not make for a great question unless one is intending to test the applicant's skill in clarifying ambiguous specifications.
 
Replace the word "snake" with "danger noodle" in all tiny ads.
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic