Win a copy of React Cookbook: Recipes for Mastering the React Framework this week in the HTML Pages with CSS and JavaScript forum!
  • 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

 
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
Hello everybody,
I hope you doing well, I've struggled to resolve this problem, any helps?
here is it,



thanks

 
Master Rancher
Posts: 4457
38
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What have you tried?
Have you worked on the logic?  What steps should the program take to solve the problem.

Be sure to wrap any posted code in code tags.
 
Bartender
Posts: 1028
31
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
The first part might be the easiest of the three parts, at least, a simple brute force solution comes together in my mind pretty quickly.

1. if [0,0] or [n-1, n-1] isn't 1 you are already done, the answer is no.

2. It is reasonably easy to determine what a legal next move is, you are constrained to up, down, left and right so at most there are ever four possible choices you could make for next move, right?
2b. Actually, only at most three, because moving back the way you came never buys you anything, and if you are at a left edge, right edge, top edge or bottom edge, there are only a maximum of two possible next moves.

3. Saying you never want to go backwards means that there is no solution that takes a step and undoes it, which would just get you nowhere, it doesn't mean that while searching for a possible path you wouldn't revisit the same game state more than once considering other possible next moves from that state...think recursion?  It does mean that when considering possible moves, if you have already been there in a previous move along the path being considered, well, there is no reason to make that move.  If there is a 0 in a position then you simply can't move there...

4. If you keep track of whether you have hit a 0 or not along the path you've traveled, then the rule about moving into a 0-occupied spot only applies if you have done so already.  If not, you get to "cheat" once by moving there anyway and just remembering that along that path you are all done with moving into zero-occupied spaces for potential solutions stemming from that...

How do you know when you are done?  If you have no valid moves left and are not on a 1 at [n - 1, n -1] then the path you are exploring is hopeless, so we can RETURN from that exploration and see if the previous position had any valid moves left, if so, go explore those, if not give up on that one too and go see if any of the previous positions had valid/hopeful/unexplored legal possible moves...

I think that describes several generalities about how I would usually go to solve such a problem while leaving several important implementation details to your imagination.
 
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
I've tried this



this code resolves two cases out of 10
 
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
Thanks, Jesse Silverman,
I've tried many solutions, however, all of them failed, furthermore, I've used BackTracking algorithms but it also fail
 
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
I think that the best way to tackle this problem is using BFS
 
Norm Radder
Master Rancher
Posts: 4457
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Can you describe in English what steps the program is taking to solve the problem?
I do not see any comments in the code that does that.

Also can you post a complete program that compiles and executes for testing?
 
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

Norm Radder wrote:Can you describe in English what steps the program is taking to solve the problem?
I do not see any comments in the code that does that.

Also, can you post a complete program that compiles and executes for testing?



I Notice the code below isn't the correct way to solve this issue, I think the best way is to use Breadth-First-Search

 
Jesse Silverman
Bartender
Posts: 1028
31
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
EDIT -- For this thread, I decided to give everyone who cares (along with all the normal people who don't) an insight into my solution development style.  The first few stunk, but were just Proof of Concept as I stumbled towards the solution.  We had been discussing the benefits of letting people see your earlier partial solutions so that they could provide feedback, an advantage that gets lost if you try to polish things to perfection before you let anyone see it because you "worry that it's not good enough, for anyone else to hear..." -- this thread shows a case study of ignoring the embarrassment, unfortunately at a time not too many people were around to comment, but whatever.  It was fun.

So, of course the very first thing I did was in the answer I gave, how might I go about solving the problem, a general description of just the algorithm.

The next step I take is saying "What classes and data structures might I need to go about writing easy-to-write, easy-to-read code to do this?"

For me, the results of the first 15 minutes of that looked something like this (okay, exactly like this):

 
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 Silverman wrote:So, of course the very first thing I did was in the answer I gave, how might I go about solving the problem, a general description of just the algorithm.

The next step I take is saying "What classes and data structures might I need to go about writing easy-to-write, easy-to-read code to do this?"

For me, the results of the first 15 minutes of that looked something like this (okay, exactly like this):

....




I really appreciate your help, Jesse, however, this is not the solution that I seek, if you don't mind try to read the description again of the problem carefully, the description reveals how to traverse the matrix of int from top left to right bottom using up, down, right and left directions, don't forget that he constraint your moves through the matrix,

although I found a basic solution but I should develop it to fill my needs



1-I should find a way to check the output of the program and should be equals to 1's if all the path contains 1's then the program should print TRUE otherwise I would print the number of paths that can be generated  
 
Jesse Silverman
Bartender
Posts: 1028
31
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've now fixed my first bug, as maxX and maxY are each one less than the size, of course.

I am all done now, except for writing  canGetToTargetWithoutHittingZero(int xPos, int yPos):
 
Norm Radder
Master Rancher
Posts: 4457
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Can you post some matrixes for testing with?   Some with a path and some without a path.

Do you have a problem description in text so it can be copied into a testing program for easy reference?
 
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

Norm Radder wrote:Can you post some matrixes for testing with?   Some with a path and some without a path.

Do you have a problem description in text so it can be copied into a testing program for easy reference?



here the description of the whole problem

 
Norm Radder
Master Rancher
Posts: 4457
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


here the description of the whole problem


Sorry, that is an image.  I can not copy an image into my java source file.  I need text,

Also can you post the java source for some test matrices?
 
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

Sorry, that is an image.  I can not copy an image into my java source file.  I need text,


Also can you post the java source for some test matrices?



example 1 :
["100", "100", "111"]
Return TRUE a path exists with the following positions {0.0, 1.0, 2.0, 2.1, 2.2}

example 2:
["11100", "10011", "10101", "10011"]
should return 2 (two paths can be created, the first path can be made by flipping 0 at position 0.3m the second path can be created by flipping 0 at 1.2)





 
Saloon Keeper
Posts: 4611
182
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Houssam

why using Strings? I would use Points, and a List<Point> to specify a path.

Your code is what I would use. If you want to record the paths as well, I would suggest not to BFS over the Strings (or Points as I suggested), but over the Paths. So, Queue<Path> or Queue<List<Point>>.

When the queue becomes empty, it is then easy to check if a path ends with Point(N - 1, M - 1).

The last question about what zero to flip to a 1 in order to find a solution I have to think about that. A possibility is to "brute-force" every zero, but that seems something as a last resort. I'm thinking of defining a distance between paths, drawing also paths from (N - 1, M - 1), and see what elements of the two sets differ 1 (or 2) in length. Well, just a thought.
 
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
@Piet

I used String to store the location of variables in the matrix, I think Brute-Force will not work here, I haven't tried yet with the brute force

if you could implement your idea via code, it;s will be good
 
Norm Radder
Master Rancher
Posts: 4457
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The format of the input is confusing,  In one place it is a list of Strings, in the posted code it is a 2 dim int array.
How to get from one to the other?  Is there a method to read the Strings and fill in int array?
 
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

Norm Radder wrote:The format of the input is confusing,  In one place it is a list of Strings, in the posted code it is a 2 dim int array.
How to get from one to the other?  Is there a method to read the Strings and fill in int array?




I've used BFS to traverse the 2D matrix, you can look above to see the code that I've uploaded
 
Norm Radder
Master Rancher
Posts: 4457
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

I've used BFS to traverse the 2D matrix, you can look above to see the code that I've uploaded


Can you also post the calling code and the 2 dim array that was passed to the method?
 
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

Norm Radder wrote:

I've used BFS to traverse the 2D matrix, you can look above to see the code that I've uploaded


Can you also post the calling code and the 2 dim array that was passed to the method?



all information that you want is posted above
 
Jesse Silverman
Bartender
Posts: 1028
31
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 only tested this with one trivial win and one no-win-without-changing, but it passes for those two test cases.
I wrote it thinking about making counting zeroes it hits along the way to be easy but haven't implemented that yet.
I think I will wind up with something that will work with something that can solve for hitting and pushing thru an arbitrary number of blockages, in this case exactly zero or 1.
I had semi-memorized that depth-first search is always easiest to implement unless there is a good reason to go breadth-first (which is great to know how to do), is that not true?

 
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 Silverman

I have told you before that BFS is the solution to that problem, furthermore, I have some missing steps that I would use in my code to resolve this problem,
BFS gives you the ability to check the output of the program and control it

 
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

the following code gives me one path that forms 1's, you can test in your own machine

 
Norm Radder
Master Rancher
Posts: 4457
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

all information that you want is posted above


Sorry, I do not see any of your code with a main method or any where a 2 dim int array has values for testing.

Also I do not see any code that defines a class to hold the methods for testing.
 
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

Sorry, I do not see any of your code with a main method or any where a 2 dim int array has values for testing.

Also I do not see any code that defines a class to hold the methods for testing.



the last message that I wrote, I've copied from main method you can copy and past it to your machine inside main method and it will work fine
 
Norm Radder
Master Rancher
Posts: 4457
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

you can copy and past it to your machine


Please post the full code that will compile and execute for testing to make sure that all code being used is EXACTLY the same here and for you.  If I use my code for parts of the test, the code could be different.
 
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

Please post the full code that will compile and execute for testing to make sure that all code being used is EXACTLY the same here and for you.  If I use my code for parts of the test, the code could be different





Output : 1 1 1 1 1 the path that forms 1's


 
Norm Radder
Master Rancher
Posts: 4457
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry, that section of code will not compile and execute for testing.  It needs a class declaration and some  methods.


Is there a problem with providing full code that will compile and execute?
How are you compiling and testing the code?
 
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

Norm Radder wrote:Sorry, that section of code will not compile and execute for testing.  It needs a class declaration and some  methods.


Is there a problem with providing full code that will compile and execute?
How are you compiling and testing the code?



It compiles properly on my machine, I didn't declare some special or helper class, just copy and past it on your own machine
 
Norm Radder
Master Rancher
Posts: 4457
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok, I am done with this thread.

The posted code has no methods or classes.  It will not compile on my machine.
 
Jesse Silverman
Bartender
Posts: 1028
31
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
Sorry that Norm's out, he wants to be able to run the whole solution cut-and-paste as you have it to debug it, or else.

I will try to finish this after lunch.  You are right that the question insists on using ints for some reason, in case someone is using some language that doesn't even have boolean, changed that and started to prepare for returning a count in the 1 blocks allowed case.

 
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

Yeah, no issue, I knew that it's an awkward question or even a riddle question, I hope I will find the solution today, although, tomorrow is the last day    

Thanks, Norm for your help
 
Jesse Silverman
Bartender
Posts: 1028
31
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
My wife made me watch a whole episode of "The Wall" with her while eating lunch, and then the dog demanded not ONE but TWO walks, so this isn't an accurate assessment of my speed.

I am still in testing, but here is how I adapted the code to give the full answer.

Hey, where is this answer for?  If I can fix any stupid bugs in this I might enter myself?


 
Jesse Silverman
Bartender
Posts: 1028
31
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
Note to OP.
I am sort of serious about asking where this is from.
I looked at it to help you and because it looked challenging but doable but challenging (to me, others might find it very easy or very hard)...
but if I have it right, I might as well submit it...

Note also to OP.
When someone has something like this, where they think they probably got it right and now are bored with it and want to go do something else fun, the person they leave it with is called an SDET, Software Development Engineer in Testing.

Some Ranchers will think I am being sarcastic saying that many engineers don't want to play around with coming up with Unit Tests for every Edge and Corner case, nor to debug any of those failures, but will feel that is what their SDET is there for...I would say that is ten times better than what often happens, which is that they look at it for a second or two, blink twice, and push it to TEST where QA fails massively and I get no dinner and have a very grumpy wife (my spouse does QA).

Anyway, at first I wrote it representing the playfield with true and false because I grew up deprived in a world without boolean types and never want to use an int for something that logically seems to be a boolean.  That was my bad.  When an interviewer or contest sets ground rules, you follow ALL of them, not ones you pick.  If it was a live interview I might grumble aloud "I wish these were booleans instead!" and sometimes they are like "Yeah, okay, fine, make 'em booleans if you like, go right ahead, doesn't matter to me..." but this was NOT live...

Anyway, this answer may still be wildly wrong, I have only started testing.  In real life, I often got handed things in an "almost pretty much working, we think" state, to "clean this up, add some tests, check it in!"
Sometimes that was even true.  Other times, there were insufficient Unit Tests, which passed (because they were insufficient), and I had to add the Hard Ones or it would just go right into TEST and befuddled QA would come to me to go debug the Star Programmer's Code since they were busy working on the Next Great Thing and couldn't look back for just an allegation.

I am going to investigate whether this code that some Big Genius (me, ha) handed to me actually works right, because SDET is an important role.
Serious places need Very Good People in SDET roles, and too many people view it as a consolation prize for "I coulda been a contenda" but being kinda sorta okay at programming doesn't make you a good SDET...the big places make a Big Deal of letting you know if you apply to an SDET role that "You will need to be able to code, and code very well.  You will need to look at things that look 'pretty good' and notice what is wrong with them.  You will need to think of every test that should be applied, write them, and make sure they pass..."

Lastly, many people feel Microsoft Windows really jumped the shark when they had Massive Reductions in SDET's, including some people who were there (not just irate former SDET's)...

Note: there are optimizations I have already thought of making.  If this were a HackerRank medium problem, they would have a 3000 x 2000 grid to solve, with 61952 possible solutions by changing one cell.  I almost welcome finding out that there are some big cases that this solution is too slow for, but won't touch the code unless I come up with a test case that fails.  Premature Optimization and all that.  If the stack space runs out for some test cases, that would Truly Suck, because none of my Optimizations ready-to-go really cut down on stack consumption.

 
Master Rancher
Posts: 4001
52
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hmmm, the problem feels poorly specified for the case where there is no direct path between the corners.  Consider:

There's no direct path - but there are two places, (1,3) and (2,2) where we can change a 0 to 1 to create a path.  However, the requirements ask us to return the "no of paths".  Well, the number of possible paths here is considerably higher than 2.  So, do they want us to return the actual number of possible paths?  Or just the number of ways we can make a path, by changing a 0 to 1?  Literally, they're asking for the former, but I suspect they mean the latter.  At least, I can imagine much better algorithms for the latter.  For the actual number of paths, BFS doesn't work well - you can't reject a point just because it's been previously explored if you need to count all the alternatives.  You can still do a relatively simple brute-force approach, but it won't scale well for larger matrices.

So, I would suggest trying to get confirmation what they really mean by "no of paths", before getting too committed to any one solution.

If what is needed is just to identify the number of places you can create a path (or paths) by changing a 0 to 1, then consider the following algorithm:

1. Start at upper left corner and replace the 1 with 2.  Find every other point connected to that point by a path of 1's, and replace them all with 2.  If you get to the lower right corner, you've found a solution; you're done.

2. Start at lower right corner and replace the 1 with 3.  Do the same for all other connected 1's, as in the previous step.

3. Now look at every point that's a 0.  If it is adjacent to at least one 2 and at least one 3, then it's a solution.  Count all points like this.

Even if the "number of paths" is really what's needed, this could be a useful step to limit the solution space to search.
 
Mike Simmons
Master Rancher
Posts: 4001
52
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Jesse, I haven't looked closely at yours yet to see where you come down on the question of interpretation of "number of paths".  But a quick note:


This can be done more concisely as:
 
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 Silverman wrote:My wife made me watch a whole episode of "The Wall" with her while eating lunch, and then the dog demanded not ONE but TWO walks, so this isn't an accurate assessment of my speed.

I am still in testing, but here is how I adapted the code to give the full answer.

Hey, where is this answer for?  If I can fix any stupid bugs in this I might enter myself?

//code here



No issue, Jesse, there was a French proverb that said,

who women want, God wants it too

 

I've used another approach to solve it, but, it was fill only the need of the problem, it isn't general, in other words, it doesn't work for all lengths of matrices, it works only for 3x3, I've passed two cases out of 10.
 
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
Thanks a lot @Jesse, I really appreciate your help, furthermore, I will try to use your solutions and reply back later, if you don't mind Jesse send me your twitter. FB, or whatever you want  
 
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 knew that many questions roll up in your mind,

Q-where that question comes from?
A-It's a question that I've been interviewing during the interview

I have passing two interviews today, my mind is burning now, hahahah

the second interview was nearly easiest than the first, however, I found myself the first interview has taken much times than the second, for the second, I've resolve 4 questions out of 6

@Jesse, don't forget to send me your FB, Twitter, or whatever you want


I want to thank everybody that help me even with a single comment or views
 
He's giving us the slip! Quick! Grab this tiny ad!
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic