|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
Hey,
so can You guys help me construct XPATH (preferebly) search term that would help me find this element? I cant use absolute XPATH since this element is loaded as apart of list of elements which are in random order and thus last part of path changes at random.
this is what i know about the element:
<div style=''position: absolute; overflow: hidden; z-index: 3; text-decoration: inherit; text-overflow: inherit; text-align: left; color: rgb(255, 255, 255); white-space: nowrap; font: normal normal normal normal 11px Verdana, "Lucida Sans", Arial, Helvetica, sans-serif; left: 57px; top: 2px; width: 164px; height: auto;''>HU6</div>
most likely none of that is unique to this element. My best bet is the text "HU6" between div, but there for sure are elements on the page that starts with the same string ("HU6").
|
On January 15 2018 23:44 Silvanel wrote:Hey, so can You guys help me construct XPATH (preferebly) search term that would help me find this element? I cant use absolute XPATH since this element is loaded as apart of list of elements which are in random order and thus last part of path changes at random. this is what i know about the element:
<div style=''position: absolute; overflow: hidden; z-index: 3; text-decoration: inherit; text-overflow: inherit; text-align: left; color: rgb(255, 255, 255); white-space: nowrap; font: normal normal normal normal 11px Verdana, "Lucida Sans", Arial, Helvetica, sans-serif; left: 57px; top: 2px; width: 164px; height: auto;''>HU6</div>
most likely none of that is unique to this element. My best bet is the text "HU6" between div, but there for sure are elements on the page that starts with the same string ("HU6").
document.getElementsByTagName('div').filter(e => e.textContent === 'HU6')
|
On January 15 2018 15:02 mahrgell wrote:
Other solution:
You write a function that reorders a circle, so that the lowest ID is first. (Also if you save nodes instead of edges, don't save the returning node twice...)
(6,7,8,5) -> (5,6,7,8)
(5,6,7,8) -> (5,6,7,8)
etc.
This means you have to store every circle only once.
If you need some quick access to know if there are circles starting at a given ID, make an additional map of lists/vectors of pointers, with the ID as mapkey, and the pointers pointing to all circles containing that ID. In case of the IDs used in circles being dense, make it an array of lists/vectors of pointers
fantastic, thank you.
There is some small extra overhead in doing this since to check prior existence of a cycle I will need to re-order it first, but this is nothing compared to how much time and space it can save overall.
I think what I will do is re-order the cycles per your suggestion, and then convert each one to tuple and store all of them in a single set.
Does this sound reasonable?
|
On January 15 2018 09:58 travis wrote:
DIFFICULT QUESTION:
I am doing more graph stuff. I want to maintain a history of any traversed sub-cycles, of varying sizes. So if I have hit (5, 4, 7, 5) - I want to save it. If I've hit (1,2,3,4,5,9,11,317,1), I want to save it. If I have hit (8,9,8), I want to save it.
I believe that I cannot store this information in the form of individual points. If I do this, then for say, (5,6,7,8,5), I will also potentially need to create and store (6,7,8,5,6), (7,8,5,6,7), and (8,5,6,7,8). The situation becomes even worse for bigger and bigger subcycles.
So, I choose to store them as edges. This way, if I store ((5,6),(6,7),(7,8),(8,5)) it covers all of the situations in the last paragraph. But, only if it's stored in a way where order doesn't matter (a set?).
So then, I would have a set for every path. I don't really see a reasonable alternative to this, but if there is an alternative then please let me know.
Continuing on, how can I store my sets? I am using python, where afaik sets can only immutable objects, not other sets. So, I could use a list...
but then I run into other problems. Which are my primary questions
1.) Is there no more efficient alternative? I don't want to have to traverse a list to check every set in it.
2.) If I do use a list... how do I efficiently check if the current set I want to add is already in it.
thanks
Can you post the original question you are trying to solve? You might have gone down a rabbit hole and made your problem intractable.
|
On January 15 2018 06:10 Excludos wrote:Show nested quote +On January 15 2018 01:09 WarSame wrote:
There's a few reasons, though I'm not sure how valid they are. First, I was under the impression that only having 1 db adapter could simplify access to the DB. Second, it seemed pointless to have 2 classes that extend a third and only contain functions, with no values of their own. Third, it simplifies queries that want more than 1 table at once because I don't need to instantiate a db adapter for the other table. Instead I can just directly access it.
Those may be stupid reasons, or not worth the tradeoff, but that's why I did it. Ok I might have misunderstood, so let's clear things up. I agree that the last layer, aka whatever actually does the connection to the DB, should be only one class (Let's call that DbApi). Simply because it might be used a lot of places and it's easier to debug and fix one class than 10x copies of one class. However it should also be extremely simple. It shouldn't hold any preference as to what type of data it asks or sends. That's where you need adapters or controllers or whatever you want to call it. Ie: One class does the connections to DB, then you have a Eth adapter and a account adapter which actually tells it what to get. If you've done this, then you've done it correctly. If you find yourself realizing that you never ask for one type of data without simultaneously asking for the other, then it's acceptable to combine these two adapters. Is that what you're asking? If you so you can either not worry about a long class (I know some unwritten rules specify that you should never have long classes but..pff, I don't care), or split functions into static helper classes. If you are worried about having too many singular database queries, and want to combine them, you should do that in the DbAPI class by having it collect queries and run them at a specific rate. I honestly wouldn't worry tho. At my work we have something like several hundred queries to the db every second and it doesn't affect performance at all. All done on regular run of the mill laptops.
No, I think you understood correctly.
I'm using SQLite Db Adapter on Android, which has a DatabaseHelper that provides a wrapper for using the DB.
I generally only request from one table or the other - only once or twice do I need both at once. I agree with you and will split back out to 2 classes. Thanks for the response!
I wasn't worried about the rate of queries, but that's good information to know, too.
|
I was attempting to implement Filters on my Infura instance in web3j but it turns out they explicitly mention in the documentation that you can not do that. I tried to get Geth working on Android, but the old documentation is deprecated, the new releases seem to have similar usage but no documentation, and when I try to actually run it under my app it just waits for a bit and then times out with "no suitable peers available".
It turns out it is quite difficult to develop for multiple intersecting systems when they're always changing rapidly, not well documented, and error-prone. :/
|
That's why you should use tried, true, stable and battle-tested releases if possible.
|
On January 15 2018 09:58 travis wrote:
DIFFICULT QUESTION:
I am doing more graph stuff. I want to maintain a history of any traversed sub-cycles, of varying sizes. So if I have hit (5, 4, 7, 5) - I want to save it. If I've hit (1,2,3,4,5,9,11,317,1), I want to save it. If I have hit (8,9,8), I want to save it.
I believe that I cannot store this information in the form of individual points. If I do this, then for say, (5,6,7,8,5), I will also potentially need to create and store (6,7,8,5,6), (7,8,5,6,7), and (8,5,6,7,8). The situation becomes even worse for bigger and bigger subcycles.
So, I choose to store them as edges. This way, if I store ((5,6),(6,7),(7,8),(8,5)) it covers all of the situations in the last paragraph. But, only if it's stored in a way where order doesn't matter (a set?).
So then, I would have a set for every path. I don't really see a reasonable alternative to this, but if there is an alternative then please let me know.
Continuing on, how can I store my sets? I am using python, where afaik sets can only immutable objects, not other sets. So, I could use a list...
but then I run into other problems. Which are my primary questions
1.) Is there no more efficient alternative? I don't want to have to traverse a list to check every set in it.
2.) If I do use a list... how do I efficiently check if the current set I want to add is already in it.
thanks
After you create your set, you don't change it. Doesn't that make it immutable? I'm not sure about python, but it could be done in [SuperiorLanguage]C++[/SuperiorLanguage].
Edit: Inserting of the path sets into the set of paths can be done*
You can compute the hashes for each set as you're constructing them. Insertion/search become O(n) where n is the length of the path.
On January 15 2018 15:02 mahrgell wrote:
Other solution:
You write a function that reorders a circle, so that the lowest ID is first. (Also if you save nodes instead of edges, don't save the returning node twice...)
(6,7,8,5) -> (5,6,7,8)
(5,6,7,8) -> (5,6,7,8)
etc.
This means you have to store every circle only once.
If you need some quick access to know if there are circles starting at a given ID, make an additional map of lists/vectors of pointers, with the ID as mapkey, and the pointers pointing to all circles containing that ID. In case of the IDs used in circles being dense, make it an array of lists/vectors of pointers
has order O(nlog(n)) as you need to sort them, and could be incorrect:
Given a figure 8 graph made of 7 vertices (two diamonds sharing a common vertex):
The path through the figure 8 that looks like the way the infinite symbol is usually drawn, passes through all vertices once.
The path through the figure 8 which looks like 2 number threes also passes through all vertices once.
These are different paths, but the sorting method makes the appear the same.
|
On January 16 2018 18:31 dekibeki wrote:Show nested quote +On January 15 2018 09:58 travis wrote:
DIFFICULT QUESTION:
I am doing more graph stuff. I want to maintain a history of any traversed sub-cycles, of varying sizes. So if I have hit (5, 4, 7, 5) - I want to save it. If I've hit (1,2,3,4,5,9,11,317,1), I want to save it. If I have hit (8,9,8), I want to save it.
I believe that I cannot store this information in the form of individual points. If I do this, then for say, (5,6,7,8,5), I will also potentially need to create and store (6,7,8,5,6), (7,8,5,6,7), and (8,5,6,7,8). The situation becomes even worse for bigger and bigger subcycles.
So, I choose to store them as edges. This way, if I store ((5,6),(6,7),(7,8),(8,5)) it covers all of the situations in the last paragraph. But, only if it's stored in a way where order doesn't matter (a set?).
So then, I would have a set for every path. I don't really see a reasonable alternative to this, but if there is an alternative then please let me know.
Continuing on, how can I store my sets? I am using python, where afaik sets can only immutable objects, not other sets. So, I could use a list...
but then I run into other problems. Which are my primary questions
1.) Is there no more efficient alternative? I don't want to have to traverse a list to check every set in it.
2.) If I do use a list... how do I efficiently check if the current set I want to add is already in it.
thanks After you create your set, you don't change it. Doesn't that make it immutable? I'm not sure about python, but it could be done in [SuperiorLanguage]C++[/SuperiorLanguage]. You can compute the hashes for each set as you're constructing them. Insertion/search become O(n) where n is the length of the path. Show nested quote +On January 15 2018 15:02 mahrgell wrote:
Other solution:
You write a function that reorders a circle, so that the lowest ID is first. (Also if you save nodes instead of edges, don't save the returning node twice...)
(6,7,8,5) -> (5,6,7,8)
(5,6,7,8) -> (5,6,7,8)
etc.
This means you have to store every circle only once.
If you need some quick access to know if there are circles starting at a given ID, make an additional map of lists/vectors of pointers, with the ID as mapkey, and the pointers pointing to all circles containing that ID. In case of the IDs used in circles being dense, make it an array of lists/vectors of pointers has order O(nlog(n)) as you need to sort them, and could be incorrect: Given a figure 8 graph made of 7 vertices (two diamonds sharing a common vertex): The path through the figure 8 that looks like the way the infinite symbol is usually drawn, passes through all vertices once. The path through the figure 8 which looks like 2 number threes also passes through all vertices once. These are different paths, but the sorting method makes the appear the same.
You don't order all nodes by ID, but just put the lowest first. This doesn't equalize those graphs you described.
|
On January 16 2018 18:37 mahrgell wrote:Show nested quote +On January 16 2018 18:31 dekibeki wrote:On January 15 2018 09:58 travis wrote:
DIFFICULT QUESTION:
I am doing more graph stuff. I want to maintain a history of any traversed sub-cycles, of varying sizes. So if I have hit (5, 4, 7, 5) - I want to save it. If I've hit (1,2,3,4,5,9,11,317,1), I want to save it. If I have hit (8,9,8), I want to save it.
I believe that I cannot store this information in the form of individual points. If I do this, then for say, (5,6,7,8,5), I will also potentially need to create and store (6,7,8,5,6), (7,8,5,6,7), and (8,5,6,7,8). The situation becomes even worse for bigger and bigger subcycles.
So, I choose to store them as edges. This way, if I store ((5,6),(6,7),(7,8),(8,5)) it covers all of the situations in the last paragraph. But, only if it's stored in a way where order doesn't matter (a set?).
So then, I would have a set for every path. I don't really see a reasonable alternative to this, but if there is an alternative then please let me know.
Continuing on, how can I store my sets? I am using python, where afaik sets can only immutable objects, not other sets. So, I could use a list...
but then I run into other problems. Which are my primary questions
1.) Is there no more efficient alternative? I don't want to have to traverse a list to check every set in it.
2.) If I do use a list... how do I efficiently check if the current set I want to add is already in it.
thanks After you create your set, you don't change it. Doesn't that make it immutable? I'm not sure about python, but it could be done in [SuperiorLanguage]C++[/SuperiorLanguage]. You can compute the hashes for each set as you're constructing them. Insertion/search become O(n) where n is the length of the path. On January 15 2018 15:02 mahrgell wrote:
Other solution:
You write a function that reorders a circle, so that the lowest ID is first. (Also if you save nodes instead of edges, don't save the returning node twice...)
(6,7,8,5) -> (5,6,7,8)
(5,6,7,8) -> (5,6,7,8)
etc.
This means you have to store every circle only once.
If you need some quick access to know if there are circles starting at a given ID, make an additional map of lists/vectors of pointers, with the ID as mapkey, and the pointers pointing to all circles containing that ID. In case of the IDs used in circles being dense, make it an array of lists/vectors of pointers has order O(nlog(n)) as you need to sort them, and could be incorrect: Given a figure 8 graph made of 7 vertices (two diamonds sharing a common vertex): The path through the figure 8 that looks like the way the infinite symbol is usually drawn, passes through all vertices once. The path through the figure 8 which looks like 2 number threes also passes through all vertices once. These are different paths, but the sorting method makes the appear the same. You don't order all nodes by ID, but just put the lowest first. This doesn't equalize those graphs you described.
Apologies on not understanding your algorithm properly.
I believe the problem still stands:
Take the same kind of paths but over a figure 8 with 5 vertices (two triangles):
If the lowest ided vertex is not the shared vertex, with appropriate starting vertex, you won't know if the path went clockwise or counter clockwise around the loop.
Also irrelevant correction, you pass through every vertex once, bar the shared which you go through twice.
Edit: Or did I misunderstand it again, and you're rotating until the lowest id is first?
|
On January 16 2018 18:44 dekibeki wrote:Show nested quote +On January 16 2018 18:37 mahrgell wrote:On January 16 2018 18:31 dekibeki wrote:On January 15 2018 09:58 travis wrote:
DIFFICULT QUESTION:
I am doing more graph stuff. I want to maintain a history of any traversed sub-cycles, of varying sizes. So if I have hit (5, 4, 7, 5) - I want to save it. If I've hit (1,2,3,4,5,9,11,317,1), I want to save it. If I have hit (8,9,8), I want to save it.
I believe that I cannot store this information in the form of individual points. If I do this, then for say, (5,6,7,8,5), I will also potentially need to create and store (6,7,8,5,6), (7,8,5,6,7), and (8,5,6,7,8). The situation becomes even worse for bigger and bigger subcycles.
So, I choose to store them as edges. This way, if I store ((5,6),(6,7),(7,8),(8,5)) it covers all of the situations in the last paragraph. But, only if it's stored in a way where order doesn't matter (a set?).
So then, I would have a set for every path. I don't really see a reasonable alternative to this, but if there is an alternative then please let me know.
Continuing on, how can I store my sets? I am using python, where afaik sets can only immutable objects, not other sets. So, I could use a list...
but then I run into other problems. Which are my primary questions
1.) Is there no more efficient alternative? I don't want to have to traverse a list to check every set in it.
2.) If I do use a list... how do I efficiently check if the current set I want to add is already in it.
thanks After you create your set, you don't change it. Doesn't that make it immutable? I'm not sure about python, but it could be done in [SuperiorLanguage]C++[/SuperiorLanguage]. You can compute the hashes for each set as you're constructing them. Insertion/search become O(n) where n is the length of the path. On January 15 2018 15:02 mahrgell wrote:
Other solution:
You write a function that reorders a circle, so that the lowest ID is first. (Also if you save nodes instead of edges, don't save the returning node twice...)
(6,7,8,5) -> (5,6,7,8)
(5,6,7,8) -> (5,6,7,8)
etc.
This means you have to store every circle only once.
If you need some quick access to know if there are circles starting at a given ID, make an additional map of lists/vectors of pointers, with the ID as mapkey, and the pointers pointing to all circles containing that ID. In case of the IDs used in circles being dense, make it an array of lists/vectors of pointers has order O(nlog(n)) as you need to sort them, and could be incorrect: Given a figure 8 graph made of 7 vertices (two diamonds sharing a common vertex): The path through the figure 8 that looks like the way the infinite symbol is usually drawn, passes through all vertices once. The path through the figure 8 which looks like 2 number threes also passes through all vertices once. These are different paths, but the sorting method makes the appear the same. You don't order all nodes by ID, but just put the lowest first. This doesn't equalize those graphs you described. Apologies on not understanding your algorithm properly. I believe the problem still stands: Take the same kind of paths but over a figure 8 with 5 vertices (two triangles): If the lowest ided vertex is not the shared vertex, with appropriate starting vertex, you won't know if the path went clockwise or counter clockwise around the loop. Also irrelevant correction, you pass through every vertex once, bar the shared which you go through twice. Edit: Or did I misunderstand it again, and you're rotating until the lowest id is first?
Yes, I rotate until the lowest ID ist first.
If you allow IDs to appear multiple times in the same path, you have to choose the rotation (of those with lowest ID first) where the 2nd ID is lowest etc. But from what I understood, he didn't allow ID's to appear multiple times, so this isn't an issue.
|
On January 16 2018 18:51 mahrgell wrote:Show nested quote +On January 16 2018 18:44 dekibeki wrote:On January 16 2018 18:37 mahrgell wrote:On January 16 2018 18:31 dekibeki wrote:On January 15 2018 09:58 travis wrote:
DIFFICULT QUESTION:
I am doing more graph stuff. I want to maintain a history of any traversed sub-cycles, of varying sizes. So if I have hit (5, 4, 7, 5) - I want to save it. If I've hit (1,2,3,4,5,9,11,317,1), I want to save it. If I have hit (8,9,8), I want to save it.
I believe that I cannot store this information in the form of individual points. If I do this, then for say, (5,6,7,8,5), I will also potentially need to create and store (6,7,8,5,6), (7,8,5,6,7), and (8,5,6,7,8). The situation becomes even worse for bigger and bigger subcycles.
So, I choose to store them as edges. This way, if I store ((5,6),(6,7),(7,8),(8,5)) it covers all of the situations in the last paragraph. But, only if it's stored in a way where order doesn't matter (a set?).
So then, I would have a set for every path. I don't really see a reasonable alternative to this, but if there is an alternative then please let me know.
Continuing on, how can I store my sets? I am using python, where afaik sets can only immutable objects, not other sets. So, I could use a list...
but then I run into other problems. Which are my primary questions
1.) Is there no more efficient alternative? I don't want to have to traverse a list to check every set in it.
2.) If I do use a list... how do I efficiently check if the current set I want to add is already in it.
thanks After you create your set, you don't change it. Doesn't that make it immutable? I'm not sure about python, but it could be done in [SuperiorLanguage]C++[/SuperiorLanguage]. You can compute the hashes for each set as you're constructing them. Insertion/search become O(n) where n is the length of the path. On January 15 2018 15:02 mahrgell wrote:
Other solution:
You write a function that reorders a circle, so that the lowest ID is first. (Also if you save nodes instead of edges, don't save the returning node twice...)
(6,7,8,5) -> (5,6,7,8)
(5,6,7,8) -> (5,6,7,8)
etc.
This means you have to store every circle only once.
If you need some quick access to know if there are circles starting at a given ID, make an additional map of lists/vectors of pointers, with the ID as mapkey, and the pointers pointing to all circles containing that ID. In case of the IDs used in circles being dense, make it an array of lists/vectors of pointers has order O(nlog(n)) as you need to sort them, and could be incorrect: Given a figure 8 graph made of 7 vertices (two diamonds sharing a common vertex): The path through the figure 8 that looks like the way the infinite symbol is usually drawn, passes through all vertices once. The path through the figure 8 which looks like 2 number threes also passes through all vertices once. These are different paths, but the sorting method makes the appear the same. You don't order all nodes by ID, but just put the lowest first. This doesn't equalize those graphs you described. Apologies on not understanding your algorithm properly. I believe the problem still stands: Take the same kind of paths but over a figure 8 with 5 vertices (two triangles): If the lowest ided vertex is not the shared vertex, with appropriate starting vertex, you won't know if the path went clockwise or counter clockwise around the loop. Also irrelevant correction, you pass through every vertex once, bar the shared which you go through twice. Edit: Or did I misunderstand it again, and you're rotating until the lowest id is first? Yes, I rotate until the lowest ID ist first. If you allow IDs to appear multiple times in the same path, you have to choose the rotation (of those with lowest ID first) where the 2nd ID is lowest etc. But from what I understood, he didn't allow ID's to appear multiple times, so this isn't an issue.
Yeah, my mistake again. I like it 
|
On January 16 2018 03:52 Neshapotamus wrote:Show nested quote +On January 15 2018 09:58 travis wrote:
DIFFICULT QUESTION:
I am doing more graph stuff. I want to maintain a history of any traversed sub-cycles, of varying sizes. So if I have hit (5, 4, 7, 5) - I want to save it. If I've hit (1,2,3,4,5,9,11,317,1), I want to save it. If I have hit (8,9,8), I want to save it.
I believe that I cannot store this information in the form of individual points. If I do this, then for say, (5,6,7,8,5), I will also potentially need to create and store (6,7,8,5,6), (7,8,5,6,7), and (8,5,6,7,8). The situation becomes even worse for bigger and bigger subcycles.
So, I choose to store them as edges. This way, if I store ((5,6),(6,7),(7,8),(8,5)) it covers all of the situations in the last paragraph. But, only if it's stored in a way where order doesn't matter (a set?).
So then, I would have a set for every path. I don't really see a reasonable alternative to this, but if there is an alternative then please let me know.
Continuing on, how can I store my sets? I am using python, where afaik sets can only immutable objects, not other sets. So, I could use a list...
but then I run into other problems. Which are my primary questions
1.) Is there no more efficient alternative? I don't want to have to traverse a list to check every set in it.
2.) If I do use a list... how do I efficiently check if the current set I want to add is already in it.
thanks Can you post the original question you are trying to solve? You might have gone down a rabbit hole and made your problem intractable.
I am doing TSP stuff. Anyways I've moved on past that question because mahrgell's solution worked great.
But now I have a much more difficult question. Any of you who found the last question easy may be challenged by this one.
Problem description:
+ Show Spoiler +
I think this is a fairly difficult question. So thank you ahead of time for any help.
I have a graph I am traversing, creating different paths, one at a time. I have a set of edges I "must" use, each is stored as a tuple of (to, from). I am avoiding repeat nodes, so we only go to each "to" once, and to each "from" once. I also don't want to create a cycle in the combination.
I want to create all combinations (where order matters) of edges. To be specific, I want all combinations of all valid sizes of tuples.
Some examples for clarity:
Valid combinations of edges:
((5,7))
((3,9),(9,11),(21,18))
((1,2),(2,3),(3,4),(4,5))
Invalid combinations:
((9,8),(9,6))
((2,5),(11,3),(8,5))
((1,2),(2,3),(3,4),(4,1))
So, one thing we can see, is that to make all combinations, we will make combinations of size 1, then of size 2, then of 3, ... 4....n
Don't worry, it's not quite this insane. The amount of edges I am creating combinations with is typically not that many. But it is variable, and who knows, maybe I could end up creating some combinations of size n.
So, I was thinking about using itertools to generate the combinations. I could put itertools.combinations in a loop, and increment the size of the combinations of each pass.
But then I realized, that it is likely that the majority of combinations will actually end up invalid, and if I use itertools I don't think I can check their validity until the entire combination has been generated. This seems incredibly inefficient.
So, my thinking then went to using an adjacency list, where any edge (to, from) I want to force is stored in indices [to][from]. This allows me to iterate the adjacency list such that I avoid getting duplicate "to"s or duplicate "froms".
However, I still can't conceptualize how I can actually write a function that generates all of the combinations I want through traversal of the adjacency list.
Any Ideas?
Note: For now, I don't mind if anyone chooses to ignore the challenge of avoiding closed cycles, ie: 1,2,3,4,1
Edit: I was provided a solution on stackoverflow. It's not a completely suitable answer for my question, but it can be altered to suit my needs and was something I hadn't seen before.
+ Show Spoiler +
from collections import defaultdict
# preprocess for better performance
edges = [(1,2),(2,1),(2,3),(3,4),(4,5),(5,7), (3,9),(9,11),(11,18)]
graph = defaultdict(set)
for f, t in edges:
graph[f].add(t)
def paths(graph, l, fr=None, avoid=None):
avoid = avoid or set() # avoid previous nodes
if l == 0: # base case: empty path
yield ()
from_nodes = [fr] if fr else graph.keys()
for f in from_nodes:
new_avoid = avoid | set([f]) # set union
for t in graph[f]: # for every adjacent node t...
if t not in avoid: # unless it has been seen
# take all paths starting at t with length l-1
for path in paths(graph, l-1, fr=t, avoid=new_avoid):
# and prepend the current edge
yield ((f, t),) + path
edit2, my edits:
+ Show Spoiler +
def paths(graph, l, fr=None, avoidfrom=None, avoidto=None):
avoidfrom = avoidfrom or set()
avoidto = avoidto or set()
if l == 0:
yield ()
from_nodes = [fr] if fr else graph.keys()
for f in from_nodes:
if f not in avoidfrom:
new_avoid_from = avoidfrom | set([f])
for t in graph[f]:
if (t not in avoidto) and (f < t):
new_avoid_to = avoidto | set([t])
for path in paths(graph, l-1, fr=None, avoidfrom=new_avoid_from, avoidto=new_avoid_to):
yield ((f, t),) + path
|
On January 16 2018 15:59 Manit0u wrote:
That's why you should use tried, true, stable and battle-tested releases if possible.
True! Unfortunately, very not possible in the world of blockchain.
I realize this is an extremely off-chance, but does anyone know how to Filter Ethereum events on Android? Infura is the only client I can get working on Android and it explicitly doesn't allow for Filters. As I mentioned earlier the other clients seem to be in an unsupported/not working state. Though I am going to try running geth light on my computer itself before entirely writing it off.
|
to those working in a particular field and/or have your mind set on a particular field, how did you get to that spot? (ex. frontend/backend/fullstack web, mobile, devops, systems, etc.)
trying everything else and see which one you liked best? and to what extent (coursework? projects? internship?)
got exposed to one thing and kept following it since it seemed decent?
etc?
I'm curious how people got to where they are as I feel like I should start specializing in something. For the most part I've done a bit of coursework and/or minor projects in a bunch of areas but not sure if I should commit harder when exploring or if I should look even broader. The only thing I know for sure is that I don't like systems programming or anything very low level.
I also welcome anyone sharing why they like their area of choice to me since your reasons for choosing your respective area might resonate with me.
|
On January 17 2018 08:36 travis wrote:Show nested quote +On January 16 2018 03:52 Neshapotamus wrote:On January 15 2018 09:58 travis wrote:
DIFFICULT QUESTION:
I am doing more graph stuff. I want to maintain a history of any traversed sub-cycles, of varying sizes. So if I have hit (5, 4, 7, 5) - I want to save it. If I've hit (1,2,3,4,5,9,11,317,1), I want to save it. If I have hit (8,9,8), I want to save it.
I believe that I cannot store this information in the form of individual points. If I do this, then for say, (5,6,7,8,5), I will also potentially need to create and store (6,7,8,5,6), (7,8,5,6,7), and (8,5,6,7,8). The situation becomes even worse for bigger and bigger subcycles.
So, I choose to store them as edges. This way, if I store ((5,6),(6,7),(7,8),(8,5)) it covers all of the situations in the last paragraph. But, only if it's stored in a way where order doesn't matter (a set?).
So then, I would have a set for every path. I don't really see a reasonable alternative to this, but if there is an alternative then please let me know.
Continuing on, how can I store my sets? I am using python, where afaik sets can only immutable objects, not other sets. So, I could use a list...
but then I run into other problems. Which are my primary questions
1.) Is there no more efficient alternative? I don't want to have to traverse a list to check every set in it.
2.) If I do use a list... how do I efficiently check if the current set I want to add is already in it.
thanks Can you post the original question you are trying to solve? You might have gone down a rabbit hole and made your problem intractable. I am doing TSP stuff. Anyways I've moved on past that question because mahrgell's solution worked great. But now I have a much more difficult question. Any of you who found the last question easy may be challenged by this one. Problem description: + Show Spoiler +
I think this is a fairly difficult question. So thank you ahead of time for any help.
I have a graph I am traversing, creating different paths, one at a time. I have a set of edges I "must" use, each is stored as a tuple of (to, from). I am avoiding repeat nodes, so we only go to each "to" once, and to each "from" once. I also don't want to create a cycle in the combination.
I want to create all combinations (where order matters) of edges. To be specific, I want all combinations of all valid sizes of tuples.
Some examples for clarity:
Valid combinations of edges:
((5,7))
((3,9),(9,11),(21,18))
((1,2),(2,3),(3,4),(4,5))
Invalid combinations:
((9,8),(9,6))
((2,5),(11,3),(8,5))
((1,2),(2,3),(3,4),(4,1))
So, one thing we can see, is that to make all combinations, we will make combinations of size 1, then of size 2, then of 3, ... 4....n
Don't worry, it's not quite this insane. The amount of edges I am creating combinations with is typically not that many. But it is variable, and who knows, maybe I could end up creating some combinations of size n.
So, I was thinking about using itertools to generate the combinations. I could put itertools.combinations in a loop, and increment the size of the combinations of each pass.
But then I realized, that it is likely that the majority of combinations will actually end up invalid, and if I use itertools I don't think I can check their validity until the entire combination has been generated. This seems incredibly inefficient.
So, my thinking then went to using an adjacency list, where any edge (to, from) I want to force is stored in indices [to][from]. This allows me to iterate the adjacency list such that I avoid getting duplicate "to"s or duplicate "froms".
However, I still can't conceptualize how I can actually write a function that generates all of the combinations I want through traversal of the adjacency list.
Any Ideas?
Note: For now, I don't mind if anyone chooses to ignore the challenge of avoiding closed cycles, ie: 1,2,3,4,1
Edit: I was provided a solution on stackoverflow. It's not a completely suitable answer for my question, but it can be altered to suit my needs and was something I hadn't seen before. + Show Spoiler +
from collections import defaultdict
# preprocess for better performance
edges = [(1,2),(2,1),(2,3),(3,4),(4,5),(5,7), (3,9),(9,11),(11,18)]
graph = defaultdict(set)
for f, t in edges:
graph[f].add(t)
def paths(graph, l, fr=None, avoid=None):
avoid = avoid or set() # avoid previous nodes
if l == 0: # base case: empty path
yield ()
from_nodes = [fr] if fr else graph.keys()
for f in from_nodes:
new_avoid = avoid | set([f] # set union
for t in graph[f]: # for every adjacent node t...
if t not in avoid: # unless it has been seen
# take all paths starting at t with length l-1
for path in paths(graph, l-1, fr=t, avoid=new_avoid):
# and prepend the current edge
yield ((f, t),) + path
edit2, my edits: + Show Spoiler +
def paths(graph, l, fr=None, avoidfrom=None, avoidto=None):
avoidfrom = avoidfrom or set()
avoidto = avoidto or set()
if l == 0:
yield ()
from_nodes = [fr] if fr else graph.keys()
for f in from_nodes:
if f not in avoidfrom:
new_avoid_from = avoidfrom | set([f]
for t in graph[f]:
if (t not in avoidto) and (f < t):
new_avoid_to = avoidto | set([t]
for path in paths(graph, l-1, fr=None, avoidfrom=new_avoid_from, avoidto=new_avoid_to):
yield ((f, t),) + path
The algorithm you are trying to ask about it called Search Tree/Graph Search. As you traverse the tree, you make the list of paths. In graph search, you don't explore already explored tree paths and you need a goal/stop condition. This algorithm starts a source node that you have to specify. The list of paths can be made in linear time to the number of nodes visited using a cons list (fyi).
ex:
1 -> 2 -> 3 -> 4
[1], [1,2] , [1,2,3], [1,2,3,4]
|
On January 17 2018 14:26 dsyxelic wrote:
to those working in a particular field and/or have your mind set on a particular field, how did you get to that spot? (ex. frontend/backend/fullstack web, mobile, devops, systems, etc.)
trying everything else and see which one you liked best? and to what extent (coursework? projects? internship?)
got exposed to one thing and kept following it since it seemed decent?
etc?
I'm curious how people got to where they are as I feel like I should start specializing in something. For the most part I've done a bit of coursework and/or minor projects in a bunch of areas but not sure if I should commit harder when exploring or if I should look even broader. The only thing I know for sure is that I don't like systems programming or anything very low level.
I also welcome anyone sharing why they like their area of choice to me since your reasons for choosing your respective area might resonate with me.
Before I knew what I wanted, I wanted to do front-end. Started with full-stack web and gradually moved to the back-end pretty much exclusively (front-end is fucking boring).
|
On January 17 2018 16:26 Manit0u wrote:Show nested quote +On January 17 2018 14:26 dsyxelic wrote:
to those working in a particular field and/or have your mind set on a particular field, how did you get to that spot? (ex. frontend/backend/fullstack web, mobile, devops, systems, etc.)
trying everything else and see which one you liked best? and to what extent (coursework? projects? internship?)
got exposed to one thing and kept following it since it seemed decent?
etc?
I'm curious how people got to where they are as I feel like I should start specializing in something. For the most part I've done a bit of coursework and/or minor projects in a bunch of areas but not sure if I should commit harder when exploring or if I should look even broader. The only thing I know for sure is that I don't like systems programming or anything very low level.
I also welcome anyone sharing why they like their area of choice to me since your reasons for choosing your respective area might resonate with me. Before I knew what I wanted, I wanted to do front-end. Started with full-stack web and gradually moved to the back-end pretty much exclusively (front-end is fucking boring).
How did you decide on wanting to do front-end? And did you look for a full-stack job or did it just happen that you got a full stack job and/or your skillset naturally fit it so you ended up there?
For me at the moment my skillset is so broad (or in a negative way, lacking) and unfocused and so are my interests. I guess that is because I'm only a student, but at the same time I feel like most of my peers have an idea of what field they want to go into and even intern listings seem to be more focused. It is mostly at large companies where there are more generalized roles but even there there are tons of specialist roles that it seems like I should aim to specialize soon. I've done at least one small project + a course in a bunch of fields but nothing really seemed to click. If I had to attempt to explain what was the most fun for me in the past, I'd say something that automates large tedious tasks. For ex. a program that constantly checks multiple sites for the latest news on a specific person/thing.
Basically anything that takes something super large and turns it into something small.
|
On January 17 2018 16:58 dsyxelic wrote:Show nested quote +On January 17 2018 16:26 Manit0u wrote:On January 17 2018 14:26 dsyxelic wrote:
to those working in a particular field and/or have your mind set on a particular field, how did you get to that spot? (ex. frontend/backend/fullstack web, mobile, devops, systems, etc.)
trying everything else and see which one you liked best? and to what extent (coursework? projects? internship?)
got exposed to one thing and kept following it since it seemed decent?
etc?
I'm curious how people got to where they are as I feel like I should start specializing in something. For the most part I've done a bit of coursework and/or minor projects in a bunch of areas but not sure if I should commit harder when exploring or if I should look even broader. The only thing I know for sure is that I don't like systems programming or anything very low level.
I also welcome anyone sharing why they like their area of choice to me since your reasons for choosing your respective area might resonate with me. Before I knew what I wanted, I wanted to do front-end. Started with full-stack web and gradually moved to the back-end pretty much exclusively (front-end is fucking boring). For me at the moment my skillset is so broad (or in a negative way, lacking) and unfocused and so are my interests. I guess that is because I'm only a student, but at the same time I feel like most of my peers have an idea of what field they want to go into and even intern listings seem to be more focused. It is mostly at large companies where there are more generalized roles but even there there are tons of specialist roles that it seems like I should aim to specialize soon. I've done at least one small project + a course in a bunch of fields but nothing really seemed to click. If I had to attempt to explain what was the most fun for me in the past, I'd say something that automates large tedious tasks. For ex. a program that constantly checks multiple sites for the latest news on a specific person/thing. Basically anything that takes something super large and turns it into something small.
This is pretty normal. Some few knows exactly what they want to do all along, but most have no clue, and end up specializing in whatever they get a job for. For me, that ended up being fullstack simply because thats what I did on my thesis, and my first job required I do literally all of the software. But my web/html/javascript skills are pretty much completely gone, and I would find myself a hard time changing over to do anything on that (Which, imo, is a shame simply because of its usefulness).
Honestly, while I'm writing this, I just realized I should probably pick up a couple of courses on web development. You're never truly "locked" on anything in the computer world, and neither can you be simply because it keeps changing. If you specialize too much you could end up having trouble finding jobs in an area no longer desirable after 20-30 years.
|
On January 17 2018 14:26 dsyxelic wrote:
to those working in a particular field and/or have your mind set on a particular field, how did you get to that spot? (ex. frontend/backend/fullstack web, mobile, devops, systems, etc.)
trying everything else and see which one you liked best? and to what extent (coursework? projects? internship?)
got exposed to one thing and kept following it since it seemed decent?
etc?
I'm curious how people got to where they are as I feel like I should start specializing in something. For the most part I've done a bit of coursework and/or minor projects in a bunch of areas but not sure if I should commit harder when exploring or if I should look even broader. The only thing I know for sure is that I don't like systems programming or anything very low level.
I also welcome anyone sharing why they like their area of choice to me since your reasons for choosing your respective area might resonate with me.
My first internship was a QA position at a local startup that hired lots of interns. I did very well, so they asked me to come back for a random dev internship. I did. I started learning Windows dev because I had a Windows Phone. I lucked into a really good mobile internship position because I _missed_ the deadline, so my application competed with much weaker intern candidates. I got the job without any technical interviews. Because I worked on Windows, I got an interview with Microsoft, got lucky with a technical question when I was super excited to find the solution, and got a Microsoft internship doing mobile. I did okay, but they gave me a return offer, and I asked to intern on a Windows team doing C++, which went great! I wanted to do more Windows mobile dev, but realized the platform was dying, so I switched over to Android. I interviewed at a local start-up doing Android, and they gave me the position without a technical interview because I already had many internships. I took a year off, but I'm now working on Android at Square because I recalled the start-up using lots of Square libraries in the app.
I have one of the most varied intern work history compared to almost all my classmates and friends. I had no clue what I wanted to do, and honestly at the time I didn't care and didn't plan it in any way. I just tried to find the best, most interesting opportunities to me at whatever point in time. I got an offer to return to Microsoft on Windows, but I declined because I felt it was in my best interest to diversify, but maybe someone else wouldn't feel the same way. My capstone project ended the same manner, jumping projects, from helping a teacher to writing a research paper to programming a technical solution, over a year and a half of project time. Our professor uses our capstone as an example of not being afraid to _not_ commit until it feels right.
I took courses that I felt were interesting: distributed systems, computation, security, real-time operating systems, UI, criminal law, geology. I dropped courses that didn't seem interesting after a few classes (b/c of teachers, coursework). I attended some of my friend's lectures, like etymology, genetics, music in film. Some were useful, some were fun, I feel better about expanding my horizons in this way, finding out all the things I liked, disliked or found interesting. This style fit closer to the type of person I am.
Go for the opportunities that you feel will bring you the best outcomes. Paul Graham calls this upwind. Read the whole post.
Instead of working back from a goal, work forward from promising situations. This is what most successful people actually do anyway.
In the graduation-speech approach, you decide where you want to be in twenty years, and then ask: what should I do now to get there? I propose instead that you don't commit to anything in the future, but just look at the options available now, and choose those that will give you the most promising range of options afterward.
It's not so important what you work on, so long as you're not wasting your time. Work on things that interest you and increase your options, and worry later about which you'll take.
|
|
|
|
|
|
EPT
