D.J. Quavern

Master Rancher
+ Follow
since Feb 19, 2019
D.J. likes ...
IntelliJ IDE Firefox Browser Java
I am just a student
Cows and Likes
Cows
Total received
16
In last 30 days
0
Total given
1
Likes
Total received
19
Received in last 30 days
0
Total given
273
Given in last 30 days
0
Forums and Threads
Scavenger Hunt
expand Rancher Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt Green check

Recent posts by D.J. Quavern

Ok, I can post a brief edit to clarify my post, without deleting the original content.
1 month ago
Yes sorry, that's python, but python is just pseudocode sometimes so I used it for illustrative purposes.

We will use Java together of course   .

I just don't know how to begin to solve the Tray problem (https://open.kattis.com/problems/tray) recursively. If we just ignore the "bad tiles" for now, I don't know how to come up with a better solution than the one in the video.

Maybe I should edit my post, this video and posting about another problem just made it confusing for everyone. What do you think Campbell?
1 month ago
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hello again! Here comes a brief edit because the original message is very unclear:

The problem we are trying to solve is
https://open.kattis.com/problems/tray. The other problem I am discussing, the python code and the video are only to give some background about a similar problem. You can just ignore my blabla, and jump to the problem

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hello!

It's probably very bad and shameful style from me to ask for help for another problem while the last one (Eulerian path in engineering forum) is not yet solved, but I feel stuck. And you already helped me out so much dynamic programming that I feel confident we will solve it      

Here is the problem description. You are supposed to fill a grid 3 by n, with dominos that are 1 by 1, or 2 by one, placed horizontally or vertically. Some places are forbidden.

It is very similar to this other problem, where you have only 2 by one dominos. You can generate all solutions column by column, where every solution depends on the previous column. If we represent each column as a binary 2^3, then to have a 1 in column [i+1], the previous column is either completely occupied ([i][7]) or we can place a domino horizontally at the bottom of [i], that will trespass to [i+1], means that we have [i][6] in the previous column. There is a video about it from William Fiset.



While it is apparently possible to do a similar solution for the new problem, there is an alternative more elegant solution with 2^6 matrix, and recursive calls. I cannot come up with it and don't know how to start experimenting. Will you help me find the way, like we crossed the Hydra?

1 month ago
Haha now I feel intense pressure to solve it! Thanks for the cow, I will call her Pepa 😀.
1 month ago
It's really weird I did not get a notification for your reply!

I will try to use the graph created by Fiset, it is basically the same since I followed his lecture and reimplemented it.
1 month ago

Piet Souris wrote:good afternoon, DJ,

no, reaching maxDepth says nothing about there being a solution or not. If the number of edges is larger than maxDepth, then the rourine simply isn't over yet when reaching maxDepth. And if the number of edges is smaller than maxDepth, then maxDepth will never be reached.

Have you thought about a non-recursive solution, that does not suffer from a too deep recursion level?

Still have to perform my test, I'm in a pretty lazy mood these days (months)



I know the feeling, difficult to stay motivated with the state of the world... :/

So an iterative dfs?
1 month ago
Oh Piet   , I wish I came up with it but I listen to a course by William Fiset and reproduced his algorithm. And then it took some time to understand the routine.  

Do you think that if max depth is reached then it can be a sign that the problem has no solution?

1 month ago

Piet Souris wrote:hi DJ,

these drawings of yours are always of the highest quality! It would make Picasso very jealous, if you ask me.    

For your points:

1) yes, your routine will discover that, but maybe only after a while, while you could test for it in the inputstage. But it is fine as it is.

2) If you look at your drawing, you see that 1 has neighbors 0 and 2. Since you pick the last one, you go from 1 to 2, and your dfs succeeds. However, if in the input the edges 1-0 and 1-2 were switched, then 1's neighbors would have been 2 and 0, and then you would get the sequence 0-1-0.

3) suppose you have a status, say an enum {FINISHED, STILL_BUSY}, and that you add two parameters to your dfs method: currentDepth and maxDepth. The dfs can then return for two reasons: either it is finished, and before returning, it changes the status to FINISHED, or it has reached maxDepth, and it returns with the status unchanged (i.e. STILL_BUSY).
From your main, you can have something like;



1. Please explain how I can do it?

2. I tested it (not on paper sorry), it skips 0 it seems between line 14 and 15, since "0" has no outgoing paths left.


3. I am not sure I know how to do that (== I have no clue!!). But what if the solution is at max_depth + 1?
1 month ago
Hi Piet!
Thank you for those bugs I am testing and considerating throughly    
And thanks for saying it's easy to follow, does not happen often I can say :p

Piet Souris wrote:hi DJ,

I gave your latest code a look, and don't worry: it is easy to follow code!

I haven't tested it yet, but there are three things that I wonder if you took these into consideration:

1) even when every node has a zero in-out difference, it does not mean there is a path. For instance, if we have the edges 0-1, 1-0, 2-3, 3-2, then the graph is not connected and so has no solution.

2) And in dfs, if at has an outgoing = 0, that does not mean the dfs is over! For instance: if we have the edges 0-1, 1-0. 1-2, 2-1 and we go from 0 to 1 and from 1 to 0, then 0 has no more outgoings. However, the solution is: 1-0-1-2-1. There is an algo, O(N), that says if your loop gets stuck, and not all edges have been used, then look for a vertex in that loop that has still some outgoings, then go on with that vertex, and merge the loops.


3) As I recall, the constraints may be 50.000 edges. That means in the worst case a recursion depth of 50.000. And that may fail.



1: this should be tested in line 53, the eulerian path should be one arc longer than the number of edges + 1 (since a path of n edges goes between n+1 nodes). I tested the below path you proposed and it gives "Impossible".


2: I tested this one as well and it works, it seems to pluck the latest possibility from the possible departures array. I add a picture of dry-testing. Aka on paper (picture attached)

3. that's probably the problem. I don't know how to manage those recursions, any advice? I can't do stack increase injection    (if such procedure exists!)


1 month ago
Thank you, I did not have time to notice it was wrong, I was at one of those extra relaxing week-ends without computer  
Here is the kattio class (for input output): https://github.com/Kattis/kattio/blob/master/Kattio.java?fbclid=IwAR0sR7yghgHpkrJhJLmJOOsMD4qyCKdXa4jqouaf2uaFsEvyoLhiSM9AE58


Here is the code:

1 month ago
@Junilu: absolutely. I will post my graph, and the eulerian graphs I tested it against. It passes the first test and the eulerian graphs I use as example, but on the secret tests it is caught either in an infinite loop or is too slow.
Please remember that it is ugly code as usual!!

@Stephan: thank you for your beautiful graph. This is beautiful flow, especially in your toString() method!! I noted that it was undirected last time but I was looking at your way to do the streams so it was of no consequence.
Also, I mispelled your name last time because in my language Stephan is usually with an f! My bad!!
1 month ago
Thank you Stefan and Junilu.
I managed to build the algorithm with crap tests but now it's way too slow. And I cannot figure out where since it's O(n)
1 month ago
Well, that's true.  i guess I love the idea of Java streams.
1 month ago
Thank you for all the help.
I agree with you Junilu and Stefan, of course there should be a structured solution with several methods to tests and not a single blog.

The problem I was describing was, how to write a "stream test"? So I can design a streaming of different graphs in the test-methods (and at the same time, use streams). Like the lambda streams we talked about last year(?).

But maybe, if I understand you well Junilu, I do not need that and write tests that will run "in cascade"?
1 month ago
Hi guys!
I am sorry, I need to get back to you tomorrow, another impending deadline. Thank you for your replies 😀😀
1 month ago