You are asked by airport security to balance this binary tree

>>60930371
The fuck is a binary tree.
And the fuck does it have to do with programing.

Wtf is a binary tree

>>60930380
>>60930386
This is why the Web is hell.

>>60930371
Is it harder than fizzbuzz?
https://leanpub.com/insidethepythonvirtualmachine/read#leanpub-auto-from-ast-to-code-objects

>>60930393
No this is why everyone with a degree uses incomprehensible terms that make no sense under normal usage that requires them to explain themselves to make them appear more intelligent then they really are.

Just write it down balanced:

(D (A (B C)) (E (F)))

>>60930371
I'd tell him that it's impossible since an unsorted tree of nodes containing strings has no means by which it can be sorted unless each string was assigned a numeric value.

File: retro-confusd-girl.jpg (263KB, 1181x1300px) Image search: [Google]

263KB, 1181x1300px

>>60930393
>implying web programming can't get hard
Why do people keep complaining about web development when what they really should be complaining about is shitty web developers

>>60930432
What would you call a binary tree then?

>>60930442
Wow! What about the height?

>>60930371
I remember this from school but I have not had to do this for long time so I'd have to see my notes.

>>60930371
I'd question their sanity. Sure, I can loosely rearrange the nodes to satisfy the shape, but there's no apparent logic to follow.

File: ape.jpg (134KB, 333x500px) Image search: [Google]

134KB, 333x500px

>>60930442

>>60930442
its hexadecimal

>>60930432

Do us all a favour and right rotate yourself back to the unemployment line.

File: whiteboard.jpg (106KB, 1040x780px) Image search: [Google]

106KB, 1040x780px

>>60930371
>pic related roles in
What can you do at this point?

Look for "Data structure"

>>60930539
is that from project euler?

>>60930438
this.

>>60930537
colourise and then rotate

>>60930386
It's a nodal data structure, where each node has two "pointers" (though they needn't be literal C-esque pointers as such) to child nodes or to nothing, and one or zero parent nodes- only one element can have zero parents, and it is called the "root" of the tree, and nodes with no children (only child pointers to nothing) are the "leaves".

>>60930539

import collection, primes

circular = collection.Counter()
for prime in primes.below(1000000):
    circular[sorted(str(prime))] += 1
print(sum(len(digits) == count for digits, count in circular.items())) 

File: dothis.png (30KB, 1009x305px) Image search: [Google]

30KB, 1009x305px

>>60930667
do this now

https://projecteuler.net/project/resources/p067_triangle.txt

File: 1497639847304asdf.jpg (46KB, 552x552px) Image search: [Google]

46KB, 552x552px

>>60930371
Done

That was easy

>>60930745
What is the time complexity of this solution?

>>60930380

A binary tree is a tree where every node has exactly two children. A tree is just another term for an acyclic connected graph. You can think of a linked list as being a tree where every node has exactly one child.

>the fuck does it have to do with programming
It's something any first year computer science or software engineering student would learn in a data structures class. Balanced binary trees are a common means of implementing map and set types.

>>60930790
less than a minute, for sure

>>60930667
>collection
What module is this? Your own, or do you mean "collections"? Is the primes module your own?
I get:
>TypeError: unhashable type: 'list'
Changing to this

import collections, primes
  
circular = collections.Counter()
for prime in primes.sieve(1e6 - 1):
    circular[tuple(sorted(str(prime)))] += 1
print(sum(len(digits) == count for digits, count in circular.items()))

I get

$ time python3 test6.py 
268

real    0m0.407s
user    0m0.396s
sys    0m0.008s

Which is wrong.

>>60930820
lol

>>60930820
Well, it's not NP-hard then.

>>60930710
you go from the bottom to the top and add the maximum value of a child to the father

3
7 4
2 4 6
8 5 9 3

3
7 4
10 13 15

3
20 19

23

if you also want the path you need to save pointers to the maximum child of each node or something similar.

>>60930844
But you're moms pussy is

do my homework /kek/
thx

>>60930710

def max_path(triangle):
    assert all(type(i) == list for i in triangle), \
    "Triangle and individual rows must be formatted as a list."

    row = len(triangle) - 1
    while len(triangle) > 1:
        index = 0
        path_sum = triangle[row-1]
        for i in triangle[row-1]:
            path_sum[index] = max(triangle[row][index:index + 2]) + i
            index += 1
        del triangle[row]
        triangle[row-1] = path_sum
        row -= 1
    return triangle[0][0]

    B
  /   \
 A     E
  \   / \
   C  D  F

or

    B
  /   \
 C     E
/     / \
A     D  F

or

     D
    /  \
   B    E
  /      \
 C        F
/
A

>>60930371
Tree to sorted array, then start from middle. It should be some k-balanced

>>60930857
>you're

>>60930881
also

     D
    /  \
   C    E
  / \    \
 A   B    F

>>60930853
well, I know, but thanks anyways.
>>60930876
here's muh solution

#!/usr/bin/python3

fname = "triangle100.txt"


with open(fname) as f:
    content = f.readlines()

size = len(content)
bottomline = []
for i in range(0, len(content[size-1].split(' '))):
    bottomline.append(int(content[size-1].split(' ')[i]))


for k in range(size-2, -1, -1):
    tmpline = []
    line = content[k].split(' ')
    for j in range(0, len(line)):
        leftval = int(line[j]) + bottomline[j]
        rightval = int(line[j]) + bottomline[j+1]

        if(leftval > rightval):
            tmpline.append(leftval)
        else:
            tmpline.append(rightval)
    bottomline = tmpline
print(tmpline)

>>60930539
approach it kind of like you would euler problem 24

you start with all the single digit primes excluding 2
then calculate your double digit primes by only using those numbers, since a prime number containing a digit that isn't prime can't be circular
then do the same for primes with 3 digits, etc

>>60930371
I dont really know much about binary trees. I know each node is meant to have 2 children but nothing else. Can someone explain them and their use to me thanks

File: 1437685776797.png (83KB, 400x387px) Image search: [Google]

83KB, 400x387px

>>60930380
>>60930386
>>60930432
>>60930456
Welcome to /g/.
Now get the fuck out.

>>60930371
What do you mean? An African or European binary?

>>60930710
same idea you use for the small triangle in problem 18

https://stackoverflow.com/questions/8002252/euler-project-18-approach

It's also very similar to the solutions for 81, 82, and 83.
Project euler problems almost always have some sort of elegant/simple solution

>>60930466
In a graph the only thing that matters is that A is connected to B via edge 'a'. (You can asign a value to the edge. E.g: GPS and whatnot)

>>60931003
>Project euler problems almost always have some sort of elegant/simple solution
sure. That's why it is fun - tryin to find an elegant solution

>>60930950
>since a prime number containing a digit that isn't prime can't be circular
But this is wrong. Such a prime can contain 9, and cannot contain 5.
>>60931003
>https://stackoverflow.com/questions/8002252/euler-project-18-approach
>getting help with project euler
What's the point of even doing it?

>>60930837
Yeah I meant collections, was just typing this in the text form. The primes module I pulled out of my ass... for something like 1 million you could just read them from a text file.

>>60931047
>What's the point of even doing it?
learning, motherfucker.
I solved it by using a search engine, does that matter?
Making use of the internet to research a problem is to be encouraged as there could be hidden treasures of mathematics to be discovered beneath the surface of many of these problems. However, there is a fine line between researching ideas and using the answer you found on another website. If you photocopy a crossword solution then what have you achieved?

https://projecteuler.net/

>>60931003
I find it easiest to just think of it as finding longest path in a DAG, then there's nothing special about it and you already know an algorithm for doing it

>>60930442
Nothing is saying those are strings, and strings are sortable anyway (this is actually how maps are sorted -- char[])

>>60930955
Every node has 2 children subtrees where every node in left subtree is smaller than its root tree and every node in right subtree is greater.

>>60930442
Those are not values but variables, the tree is already valid binary tree.

>>60930432
this HAS to be bait

>>60931185
That works obviously, but it's not as effecient as dynamic programming the way anon described it

>>60931129
>does that matter?
Yes, it matters. The link you posted solves it for you; all that's left is to implement a trivial algorithm in a few LOC. Using a "search engine" is not a skill, nor is it learning. Learning would entail understanding how to approach a problem of this scale, i.e. understanding what "dynamic programming" entails, and solving the problem yourself.
Your quote says it in "there is a fine line between researching ideas and using the answer you found on another website".

>>60931209
i sort of get you but why do this?

>>60931263
I wasnt that anon posting the stackoverflow link. I didnt even read it before i posted my response kek, but peeps should do whatever they want. No one cares. If they think googling the solutions makes them cool, then they should do that, I guess.

>>60931241
finding longest path in a dag IS dynamic programming
what are you talking about?

>>60931047
Yea I'm a dumbass.
You'd ignore anything that has a 0,2,4,5,6,8 as a digit

My idea was that you'd just construct new permutations by adding a usable number to the previous permutations. Like to calculate the circular primes of length 3, you put 1,3,7,9 in front of length 2 numbers that contain only 1,3,7,9
And since they're circular you don't need to try every permutation. you'd know 919 and 991 are valid because you checked 199

Why the tree wasn't balanced in the first place?
Checkmate airport security

>>60930816
>has exactly two children
a maximum of two children

File: 1454898455617.jpg (68KB, 700x700px) Image search: [Google]

68KB, 700x700px

>>60931389
>tfw you are a fat neckbeard virgin that'll never have children

File: 6348440383_f0d2191b9e.jpg (128KB, 447x500px) Image search: [Google]

128KB, 447x500px

>>60931371

>>60931281
For searching and easier insertion. You can do binary search on sorted array with O(log n) complexity, but adding into array is O(n) because you need to shift the part of array. Adding into binary tree is ideally O(log n) complexity.

Ideal case is when the tree is balanced, if you keep adding increasing values into binary tree, it will be similar to linked list and both search and insertion will have O(n) complexity, thus balancing is needed.

I don't see it being used often, but once case I can recall are "ropes" for holding long strings that need to have low complexity on inserting characters. Leaf nodes hold some short chunk of text and non-leaf nodes hold ending index of the last character in left subtree. Then operation is to "insert character C into index X".

It has disadvantages: every node needs allocation and additional space for 2 pointers, it can also be slower because it does not guarantee to be in memory next to each other unlike array. There is also BTree, kinda binary tree on steroids, that is being used more often.

File: 1493407252042.jpg (1MB, 3888x2592px) Image search: [Google]

1MB, 3888x2592px

is there a way to practice binary trees in JS?

>>60930371
This should be balanced in the first place if you and your data wasn't retarded

File: 1324098344481.jpg (84KB, 679x569px) Image search: [Google]

84KB, 679x569px

>>60931506
Wroite a bloody data stoctore mate

>>60930442
>no means by which it can be sorted
>doesn't know the difference between a binary tree and a binary search tree
>never heard of ASCII
t. brainlet

>>60931506
JSON is referential so yes. Make a factory function that generates a JSON "type" with root, left, right as members.

>>60931556
>Make a factory function
Java cubicle worker detected

>>60931506

function Node(key){
  this.key = key;
  this.left = null;
  this.right = null;
}

there you go anon

>>60931586
no u

>>60931591
>no space between ) and {
You absolute monster

>>60931469
what is this thingie??

>>60931616

function Node(key)
{
  this.key = key;
  this.left = null;
  this.right = null;
}

better now :^)

>>60930634
no its a type of graph where each node is connected by an edge to at most two other nodes, and there are no cycles you fucking idiot

File: illust_62068281_20170602_223354.jpg (163KB, 1200x1200px) Image search: [Google]

163KB, 1200x1200px

>>60930371
i don't know how to balance a tree. Nor do I know how to traverse a graph.
What do I need to read so I can participate in threads like this?

>>60931666
REEEEE LITERALLY SATAN

class Node {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

>>60930634
nodes in a tree do not have a reference to their parent node anon

(F (D (B A) C) E)

Yes, this is shit, but it's a possible representation of balanced binary tree.

For a meaningful balanced binary search tree I'd have to read muh algorithm design manual or just use an existing class, I can't be bothered to remember how all the optimal algorithms worked.

Alternatively, I could scream "TYPE ERROR & ORDERING NOT DEFINED" and kill myself. Because just assuming lexical ordering is for plebs.

File: perl6.jpg (34KB, 640x480px) Image search: [Google]

34KB, 640x480px

>>60930371
>take that piece of paper
>request a scissor
>cut the paper like pic related

>>60931709
Algorithm design manual or CLRS are good starts.

Epik!

#include <iostream>

using namespace std;

template <unsigned N>
struct fibonacci
{
    const static unsigned value = fibonacci<N - 1>::value + fibonacci<N - 2>::value;
};


template <>
struct fibonacci<1>
{
    const static unsigned value = 1;
};

template <>
struct fibonacci<0>
{
    const static unsigned value = 0;
};

int main()
{
    cout << fibonacci<10>::value << '\n';

    return 0;
}

>>60930371
I randomize the tree until I reach the solution

>>60931770
>pointlessly using C++11 features because you can

kys

>>60931770
>>60931788
>using sepples at all
shiggy

>>60931360
Your approach may be more efficient, but the trivial approach of checking every cyclic permutation of each candidate prime is far simpler and sufficient for the scope of this problem.

>>60931236
ikr...

I learned about binary trees in AP CS.

This is first-year shit.

>>60931803
you are the reason that smartphones need gigs of ram and quadcore cpus

>>60931801
luckily I don't. There's no need when there's C. If you need something higher level use a competent language.

use of C++ is a mental illness

>>60930371
Not at all.

import bintrees

x = bintrees.tree()
x.balance()

>>60931803
Yea but I was just spitballing an approach that I think would lead to something more elegant. Project Euler usually will give you harder versions of the easier problems

>>60931867
lol all that advanced data structures class for nothing

>>60930442
Literally every node in OP's tree has a numeric value you dipshit.

>>60931867
SHIEET

>>60930371
I'm not a programmer but if a binary tree means that every node has exactly two children, can you just arrange them all in a circle?

A-<B+C
B-<A+D
C-<A+E
D-<B+F
E-<C+F

I dunno really how to represent this and I don't want to draw. Does anyone understand what I'm saying and am I correct?

>>60931788
Ok, which C++11 feature did I use?

>>60931801
C++ a best.

#include <iostream>
#include <string>
#include <set>
#include <functional>
#include <algorithm>
#include <iterator>

using namespace std;

struct hue
{
    int id;
    string name;

    bool operator<(const hue& h) const
    {
        return id < h.id;    
    }
    
    bool operator<(int id) const
    {
        return this->id < id;    
    }

    friend bool operator<(int id, const hue& h)
    {
        return id < h.id;
    }
};

int main()
{
    set<hue, less<>> hues{};
    
    generate_n(inserter(hues, hues.begin()), 101, [id=0]() mutable {
        int cur_id = id++;
        return hue{cur_id, "i'm a hue #" + to_string(cur_id)};
    });

    auto it = hues.find(100);
    
    if (it != hues.end())
        cout << it->id << ": \"" << it->name << "\"\n";
        
    return 0;
}

>>60930432
OOOOOOOOOOOOOOOOOOOOOHHHHH

>>60931921
Trees are acyclical

>>60931938
I see, oh well.

>>60931926
lowlevel
>c
highlevel
>swift
it really isnt that hard anon

>>60931963
gtfo applecuck

File: Untitled.png (13KB, 773x864px) Image search: [Google]

13KB, 773x864px

>>60930438
>>60930604
Is this what it would look like? I know nothing about programming.

>>60932005
No

>>60931821
Shut it, kid. Excluding 6 digits from search already reduces the pool to completely manageable on even a Core M from 2000. And for sieving primes up to 1 million, assuming a char array and standard sieve, you only need 977 KiB of RAM.

File: Untitled.png (13KB, 773x864px) Image search: [Google]

13KB, 773x864px

>>60932019
What about this?

>>60930371
is it

D
B E
AC F

?

>>60932052
Swap B and C

>>60932052
>>60932058
And also move F to left child slot of E

>>60932058
oooo

I get it now.

>>60932056
oh wait it cant be,

D
A E
BC F

File: 1490161095939.jpg (18KB, 600x600px) Image search: [Google]

18KB, 600x600px

>>60930380
>>60930386
congrats on the bites ;^)

File: 1497555980550.jpg (139KB, 908x1100px) Image search: [Google]

139KB, 908x1100px

>>60931389
>a maximum of two children
has exactly two children (empty nodes, duh)

>>60930371
Every mathematician can answer this, and they need not be a programmer...

File: graph.png (6KB, 242x177px) Image search: [Google]

6KB, 242x177px

Is it not this?
If you parse it left-mid-right you get the sequence in order.

>>60931736
There is nothing in the definition of a binary tree that forces direction.

>>60932005
you actually nailed the image based on the faulty answer, but technically this isnt a balanced tree

>>60930371
But i'm not a programmer. What the fuck kind of airport security is this?

>>60933889
It's that.

>>60932077
No, F > E

Who the fuck doesn't know this, first few replies have to be bait. Third year CS and even I know this

>>60930881
How does this make sense? A and C weren't linked in the original

>>60931389
>tfw terminal node

>>60930371
>to prove you're a programmer
Embarrassing

File: fulcrum.gif (9KB, 640x480px) Image search: [Google]

9KB, 640x480px

Assuming all nodes are weighted equally, placing the fulcrum near B should do it.

>>60930816
>It's something any first year computer science or software engineering student would learn in a data structures class.

And then never use again because no programmer ever implements their own map and set types unless they are implementing/reimplementing a language's standard libraries.

>>60930456
nigger the hardest thing in "web programming" is async apis and callback hell.

Which is easy quite frankly.

File: 1496883801129.jpg (302KB, 922x720px) Image search: [Google]

302KB, 922x720px

>>60930371
assuming it's a binary search tree? like literally how is that even hard, you just move some nodes around based on their value to fit the bst rules

literally fizz buzz level shit

File: 1497657125887.jpg (110KB, 1366x768px) Image search: [Google]

110KB, 1366x768px

>>60938213
spoken like someone who barely knows anything about "web programming"

callback hell is literally not even a thing after promises were introduced

the hardest thing about web programming is compatibility with all the user agents

>>60938295
>found an issue with chromium based browsers
>searched for an existing issue tracker
>it's 7 years old and still not solved

>>60930371
No invariants specified?
No root marked?
Tell them it is, since D is the root.

>>60936457
They don't need to be. If we have

 *         (p)
 *        /   \
 *       (c)   T3
 *      /   \
 *     T1   T2

where p and c are nodes, and T1-T3 are subtrees, then we know for sure that T1 < c, T2 > c, c < p, T3 > p, just from looking at it. A slightly harder one to see is that T2 < p, because when we went to go insert nodes into T2 we would have had to take the left path at p to get there.

So we have that T1 < c < T2 < p < T3. Now we can perform a pivot, and it looks like this

 *       (c)
 *      /   \
 *     T1   (p)
 *         /   \
 *        T2   T3

in order to preserve the height balance property. For a full implementation, see http://0x0.st/lT1.c

>>60931709
>inb4 pajeet meme
these lectures are actually good, but skip to the lesson on AVL trees. https://www.youtube.com/watch?v=zWg7U0OEAoE

>>60930667
>import primes
>import somebody_else_wrote_the_solution_for_me
This is why python programmers are cancerous.

>>60930371
I don't have to prove anything to airport security. I am a white male citizen of the USA.

>>60930371
I iterate through it saving all nodes in an arraylist (just Java things haha;) the sort the list and make a new tree lol

>>60938559
Programming is 90% knowing your libraries.

>>60930432
a binary tree is a simple term.
If you wanted confuse normies by terminology, you would call it a unidirectional graph structure.
A tree is very easy term to understand and it doesn't matter what background you have, everyone can work out how to balance a binary tree.

>>60937565
how many children does a terminal/empty node have?

>>60937928
Out of the box thinking right there