Talk:Same fringe: Difference between revisions
m
Thundergnat moved page Talk:Same Fringe to Talk:Same fringe: Follow normal task title capitalization policy
Thundergnat (talk | contribs) m (Thundergnat moved page Talk:Same Fringe to Talk:Same fringe: Follow normal task title capitalization policy) |
|||
| (16 intermediate revisions by 5 users not shown) | |||
Line 37:
::Thanks. --[[User:Paddy3118|Paddy3118]] 22:00, 14 August 2012 (UTC)
:So you've basically made the task into the same fringe problem for a general tree, not just binary tree. You've made a transformation of binary trees into general trees, kind of in a Lisp list way, i.e. Turn a binary node into a general node (with variable number of children) where the left side is the first child, and if the right side is also a node, you include that as the "rest" of the children; until you find a right side that is a leaf, which you take as the last child. Your fringe function is essentially a fringe function for general trees, which also works for this case because your transformation preserves the ordering of the fringe. Do you want to just change the problem to be for general trees? --[[User:Spoon!|Spoon!]] 09:59, 15 August 2012 (UTC)
::You can represent a binary tree using a general tree, so that is already allowed. But this problem, when posed in the literature, is normally about binary trees. I see no reason to force a generalization. --[[User:TimToady|TimToady]] 14:44, 15 August 2012 (UTC)
== Concurrency required? ==
TimToady obviously had concurrency in mind for this task, but could a solution without it fit the bill? A binary tree can be constructed with each node pointing back to its parent for example, and the tree can be traversed across calls with a single node pointer without thread/coroutine/etc. It sort of violates "no extra work" clause since each node does need some extra information, but it also sort of doesn't because comparison doesn't require extracting the whole tree. What's Larry's stance on this? --[[User:Ledrug|Ledrug]] 01:17, 15 August 2012 (UTC)
:Using a data structure that requires no recursion seems a bit beyond the spirit of the problem to me. I wouldn't necessarily call it cheating, but it feels like it. Maybe not quite as bad as having a string representation of the tree and then extracting the leaves with a global regex search, but just because you have to pick between down/right/up pointers doesn't really mean you're solving the problem. Kinda like solving a maze by just keeping your right hand on the wall, it requires no brainpower. So I think we should probably eschew the use of parent pointers. Good question though. --[[User:TimToady|TimToady]] 02:05, 15 August 2012 (UTC)
:TimToady picked up on the data structure part of the original question, but I read the question and thought maybe Ledrug was asking about the need of [[wp:Concurrency (computer science)|concurrency]] as in parallel processing? The Python solution does not process each tree in a separate process or thread, which I thought was OK? --[[User:Paddy3118|Paddy3118]] 03:51, 15 August 2012 (UTC)
:: Python <code>yield</code> is basically a coroutine, so the validity is not a problem here. --[[User:Ledrug|Ledrug]] 04:10, 15 August 2012 (UTC)
::Coroutines will certainly work, though those can be emulated with closures if you work at it, and the literature also has implementations based on tree rotations, which is mentioned in the description. --[[User:TimToady|TimToady]] 05:34, 15 August 2012 (UTC)
::: Tree rotation sounds somewhat iffy. Isn't it essentially the same as massaging (part of) the tree into a singly linked list? --[[User:Ledrug|Ledrug]] 06:12, 15 August 2012 (UTC)
::::Well, sure, but who am I to argue with John McCarthy, who proposed that very solution? <tt>:-)</tt> See about 1/3 the way down [http://c2.com/cgi/wiki?SameFringeProblem this article]. --[[User:TimToady|TimToady]] 07:05, 15 August 2012 (UTC)
==Copy problem in D entry?==
I am not a D programmer but I see
<lang d>const t1 = n(10, n(20, n(30, n(40), n(50))));
...
const t2 = n(1, n(2, n(3, n(40), n(50))));
'''
sameFringe(t1, t2): true</lang>
I was just wondering about the 10, 20, 30 and 1, 2, 3? --[[User:Paddy3118|Paddy3118]] 19:49, 18 August 2012 (UTC)
:Judging from the previous Haskell code (which I have replaced), I believe the author intends the first argument of n to be the value of that node, and the following to be children. And if there are no children, then it is a leaf. And that the value of a node that is not a leaf is not considered when taking the fringe. Or something like that. They may be confused because there are different concepts of trees, some with values at nodes and some without; and the problem is not very specific about that. --[[User:Spoon!|Spoon!]] 01:28, 19 August 2012 (UTC)
==Elevate to task now?==
Any qualms about elevating this from draft status? --[[User:TimToady|TimToady]] 03:29, 2 September 2012 (UTC)
:None hear except I see a separate problem in that the RC server doesn't seem to be colourizing code at the moment so I might wait a little? --[[User:Paddy3118|Paddy3118]] 05:02, 2 September 2012 (UTC)
:: Elevated. Whatever the glitch was, it must have been temporary. --[[User:Short Circuit|Michael Mol]] 10:16, 2 September 2012 (UTC)
| |||