Piet Souris

hi Dave,

I'm not sure about this. It is true what you write, and I see the effect when I run the code. I did not know this. But if I look at the Java 8 documentation I am unable to find any of this documented (I do see it in the Java 10 API). So, it is probably something that was built into Java 9+. I have deleted my java 8, so can't test, but have a cow for your interesting remark.

hi Alfa,

okay.

I do not like the idea to use an instance of an Employee as indication in what order it should be processed, unless you can show me the real usecase. I must admit that I still do not understand how the real thing operates.

Suppose the rules are given in the form (x, y), meaning "x must be processed after y". It is a straightforward task to turn that into the list that I was talking about. If this list of Rules is a valid one, then there must be an y in this list of Rules that does not appear as x. For instance: if we have these Rules:

(3, 5), (5, 12), (2, 3)

then the x-list is {3, 5, 2} and the y-list is {5, 12, 3}.

As we see, 12 is the value in the y-list that does not appear lin the x-list, so that's our starting point. Now, look up the Rule that has 12 as y value. We find (5, 12). That means that 5 is our next "victim". Look up 5 as right element in the rules. We find the Rule (3, 5). So, 3 is next. And in the same fashion, we find 2 as our last number. So the processlist = {12, 5, 3, 2}. And then you can proceed in the way I described.

If all this is still not correct, then probably Norm is understanding your mission better than I do. Can you give an example of the original list, and what the external users do to this list (i. e. the rules), and when the moment arrives for you to do the processing? A small example would be fine.

For the last two or three weeks CodeRanch has been very unstable. Fetching a page takes quite some time, and every other fetch gives me a Time Out error, or similar.
And when replying to a post: if I do not submit a reply within say 10 seconds, then a submit requires me to log in again. It makes working with the site pretty unpleasat, I must say. Am I the only one?

I see. I apologize for having missed the last part of the JavaForum topic.

Well, sorting based on the index of an employee in the original list, or sorting based on a given id-order is equivalent qua complexity, but the second one seems more reliable, since the sorting then does not depend on some initial order of the list.

But if the user is able to supply a list of rules, like (1 after 2, 4 after 8, et ceera), then why not let the user give just one list like (8, 3, 7, 1, 0,...), to indicate that 3 comes after 8, 7 after 3, et cetera. That would be much less work and is much less errorprone.

Then you could have something like:
public class AlfaRiz {    public static void main(String... args) {        List<Integer> processOrder = Arrays.asList(6, 8, 3, 2);        Comparator<Emp> c = new Comparator<>() {            @Override            public int compare(Emp a, Emp b) {                int indexa = processOrder.indexOf(a.id);                int indexb = processOrder.indexOf(b.id);                if (indexa == -1) indexa = Integer.MAX_VALUE;                if (indexb == -1) indexb = Integer.MAX_VALUE;                return Integer.compare(indexa, indexb);            }        };        List<Emp> emps = new ArrayList<>();        for (int i = 1; i <= 10; i++) emps.add(new Emp(11 - i));        List<Emp> b = new ArrayList<>();        for (Emp a: emps) if (processOrder.contains(a.id)) b.add(a);        b.sort(c);        System.out.println(emps);        System.out.println(b);    }        static class Emp {        final int id;        Emp(int x) {id = x;}        @Override        public String toString() {            return "" + id;        }    } }

Thanks for the info, Norm.

That raises a couple of questions:

1) why is the discussion continued here at CodeRanch?
2) is there some usecase that makes all this a little comprehensible? First of all, the rules like "one comes after three" depends on some order of the list. and secondly, it is a very labourious way of doing. Three, the user must have full control over the Employee list, in order to invoke the method "processAfter()".

So, this seems unrealistic to me. Normally, you would have one or more fields in the Employee class, on which employees can be compared, for instance salary, function, department, service years, age, whatever. There must be a way to keep the employees up to date. Then all that the user needs to specify is on what field(s) the employees should be sorted.

If there IS a clear usecase, then please specify.

Since Norm is very involved in this, I will leave further replying to him, if that's okay.

I think so. But in oder for the function to do a correct sort, it must know these rules. Are the rules in question specified as shown in your first post? If not, how are these specified?

hi Alfa,

a way to automize this, although it is not a very efficient way, is to note that (in this case) the sorting order is: 6, 8, 3, 2.
So we can use a Comparator to sort the array. For instance:
public class AlfaRiz {    public static void main(String... args) {        var sortingOrder = List.of(6, 8, 3, 2);        Comparator<Integer> c = Comparator.comparingInt(sortingOrder::indexOf);        var a = Arrays.asList(2, 3, 8, 6, 2, 5, 10);        var b = a.stream().sorted(c).collect(toList());        System.out.println(a);        System.out.println(b);    } }

Objection, your Honors!

This talk about aliens is neither meaningless, nor drivel. On the contrary, much more interesting than this dull NP Salesman Dijkstra thingy... but ah well, I rest my case.    

hi mr Kommadi,

I recently found out about the existance of Binary Indexed (Fenwick) Trees, which were exactly what I needed to solve a problem. Do you treat these too?

Whott??? Forgotten 'Mars Attacks' and 'Alien'? No thanks, I'll wait for my new 4Gqbit quantum computer, expecting it any time soon now.

Hi Ryan,

I gave it another read, and you are absolutely right. So I think the difficulty lies in coming up with the idea of such a minimal spanning tree. And certainly given the time limit of 1 second, I think this exercise is pretty hard if you've never heard of these things.

hi DJ,

long time no see! You seem to be very busy, but that is a good thing.

I had to read that assignment twice, but I think I got it. You are given N cities (vertices) and M lines of input indicating where a pilot can fly to and from (edges). So, it is an undirected Graph with N vertices and M edges. And the question is what the shortest path is between any two cities. Correct me if I'm wrong. Now, first thing what comes to mind is Dijkstra's algorithm: Dijkstra.

So, have a read and see if you agree with me!

@Paul
Thanks!

@DJ
It was a pleasure for me to help.

@Salil
And thank you for mentioning dynamic programming, I would never have come up with the idea.

hi DJ,

well, having such a lovin'and understanding family is a great boon!

First of all: you might be forgiven to think that what we proposed, is like using a canon to shoot a mosquito. You could argue that, if there are no tails, the outcome will be decided by whether the heads are even or odd. If we have at leat one tail, we can expand that to any number of tails, and thus we can chop any number of heads accordingly. So, having one head and 51 ails, can you come up with a strategy that delivers you the number of moves as well?

But let's try the OOP approach a little. Your drawing looks daunting and a bit chaotic, so I can imagine you lost track of where you were going. I said that a tree structure would be good for some difficulties, but I wanted you to try it anyway, because I think it is a great way to expand your experience.

How do you present the possible situations of heads and tails? There are several ways. A simple way would be to have a 2D array headtail[x][y], with value the moves to succes. A headtail[x][y] with value -1 or so, would indicate no solution. Or you could use an existing class that has two integer fields, likeJava's Point and Dimension, and use a dictionary<Point, Integer>, where the value indicates the number of moves to succes.

But what about a class that represents all this? For instance the class HeadTail (I use Javacode here, because my Python knowledge is a little bit very rusty):
class HeadTail {    final int heads;    final int tails;    final int movesToSolution;    public HeadTail(int heads, int tails, int moves) {        if (heads < 0 || tails < 0) throw new RuntimeException(            "illegal arguments in constructor!!"        );        this.heads = heads;        this.tails = tails;        this.movesToSolution = moves;    }    public boolean hasSolution() {        return movesToSolution >= 0;    }    public int movesToSolution() {        return movesToSolution;    }    public List<HeadTail> determineSuccessors() {        List<HeadTail> successors = new ArrayList<>();        if (heads > 1) successors.add(            new HeadTail(heads - 2, tails, movesToSolution - 1)        );        //et cetera              return successors;    }    public List<HeadTail> determinePredecessors() {        // to implement        return null;    }    @Override    public boolean equals(Object o) {...}        @Override    public int hashCode() {...} } Now, set up a Queue<HeadTail> (I always use a LinkedList for that, I'm not sure what python has for this) and a Set<HeadTail> setOfAllHeadTails (a HashSet/dictionary would be nice).
Put HeadTail(0, 0, 0) in the queue and in result, and there goes:
while the queue is not empty
   remove the head H
   get H's predecessors
   remove all predecessors already present in 'result'
   remove all predecessors that have more heads and/or tails than according to specs
   put the remaining predecessors back in the queue
It would be a bit tedious to create that Set for evey query that they will ask. As with HackerRank, can you edit the code so that you make this resultset static, i.e. so that you only need to create it once?


Last but by no means leasT;
see the 'determineSuccessors()' method in the HeadTail class. It says rhat when the number of Heads > 1 a successor would be HeadTail(head - 2, ...). Can you think of a situation where that is plain wrong?

dario lobos wrote:(...) I Don want duplicated values (...)

When are two vehicles the same? Can you show us your Vehicle class?