# D.J. Quavern

Rancher
since Feb 19, 2019
D.J. likes ...
I am just a student
Cows and Likes
Cows
16
In last 30 days
0
Total given
1
Likes
22
0
Total given
277
Given in last 30 days
0
Scavenger Hunt
Rancher Scavenger Hunt
Ranch Hand Scavenger Hunt
Greenhorn Scavenger Hunt

## Recent posts by D.J. Quavern

I saw the book promotion for Zero to Ai of Nicolò Valigi and Gianluca Mauro. What an interesting subject, I wonder actually what is the "hype" in that subject?
We have AI courses now in our CS master but what is true information (along with how to avoid bias!) has always been a subject of interest.
Welcome Nicolò and Gianluca!
Hello and welcome!
I love Rust and microcontrollers!
1 year ago
Ok, I can post a brief edit to clarify my post, without deleting the original content.
1 year 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 year 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 year ago
Haha now I feel intense pressure to solve it! Thanks for the cow, I will call her Pepa 😀.
1 year ago

I will try to use the graph created by Fiset, it is basically the same since I followed his lecture and reimplemented it.
1 year 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 year 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 year 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.

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 year 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 year 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 year 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 year 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 year ago