Fortnightly challenge of 2015-01-23: Data Structures

4:11 PM

@Martin Can I just start word vomiting or do these things usually have a direction?

@Rainbolt I don't know if Sp3000 had something specific in mind, but go ahead and barf away if you want.

Random idea: Each submission forms a single node in a linked list. They must be capable of being traversed, deleted, removed, etc.

And when they are visited they must say something (Hello, world?)

ThreeFx

So basically a big, multi-language collaboration?

Well, I'm not sure exactly what they are collaborating on lol

I'm just throwing out half assed ideas.

The way I see it, we can either BE the data structure, BE A PART OF the data structure, PERFORM OPERATIONS ON the data structure, or something else I can't think of.

(we being the submissions)

@Rainbolt we could also design the data structure, which I thought was the idea

4:19 PM

I don't understand what you mean

Submissions are going to be designing?

no we are

3 mins ago, by Rainbolt

(we being the submissions)

I like the idea of a KoTH where bots are part of a larger data structure

@Rainbolt I'm sorry, that I reverted back to the normal use of "we" :P

maybe a hacking-based game where bots make up the network?

4:22 PM

as in "here is a problem. design a data structure to represent this problem. the following operations have to be performed on the data structure. lowest complexity/byte count/runtime/memory usage wins."

@NathanMerrill Ooooohhh. We could each be a router

Throwing packets at each other trying to gain information while giving away as little information as possible

Do networks count as data structures even?

Ok, a network is a cyclic graph, and it looks like normal data structures for cyclic graphs are arrays (matrices), balanced trees, or hash tables

ThreeFx

I like the idea of the router Rainbolt. We could do some extension of the prisoner dilemma and mix in a few Cluedo like elements.

I don't understand how a balanced tree works there. If there were a cycle then it would be a very long tree.

a tree is acyclic by definition

A "Master computer" wants to store and retrieve information

we receive a point each time our router is used to store or retrieve that information

however, we, ourselves, can only store 1 piece

the master computer will learn to pick players that retrieve/store information in the shortest amount of time

4:37 PM

I like the idea of some kind of distributed computing challenge

Seems not related to data structures though

The issue I see with performance based challenges is that submissions will be competing for CPU and Memory

You could test only one submission at a time, but some languages run on virtual machines. Starting and stopping them is costly.

by "shortest amount of time", I was referring to "shortest amount of player jumps"

because a player only stores 1 piece of information, it must learn to pick the player with the shortest distance

4:52 PM

Oh, I like that idea!

I still don't understand what this has to do with data structures.

@Martin Data structures are the solution to a problem, not the problem itself. You need a problem first. Granted, we can try to pick a problem that is well known to work best with a particular data structure. Someone mentioned networks, which use matrices and hash tables, so that's how we got to this point.

Of course, data structures are the solution. But what you're describing sounds like the submissions will have no part in using data structures to solve the problem, but merely of navigating a data structure set up by some controller (or just being part of that data structure).

I see what you are saying. Here's a more straightforward idea: I have a linked list. Implement removeNode(int index).

Right, so you are saying that the data structure is given by the challenge, and submissions will just manipulate it?

5:07 PM

You're right. I guess real life doesn't apply here. If the challenge says "Manipulate the list" then you have to manipulate the list just because.

I was hoping to think of a goal that would encourage players to use and manipulate a data structure without saying "use and manipulate a data structure" because that's boring.

Anyway, if you cover it up with a story about connecting train cars, I'm sure it will look alright.

@Rainbolt I don't understand how that answers my question. I'm sorry if my question seemed to be implying something it didn't, but I was actually interested in a straightforward answer, just to make sure we're on the same page.

Ok, the straightforward answer to your question is "No. I never said what you said I said."

Can we move on?

k, then I probably don't understand how you pictured the "I have a linked list. Implement removeNode(int index)." challenge, as that sounds like, "the data structure is given [...] and submissions will just manipulate it" to me.

If you have a point to make then make it. I made a suggestion, you rewrote what I said, you asked if that is what I said, and I said no.

Because my concession that you had the "meaning" of what I wrote wasn't good enough, you had to ask for the straightforward answer.

I don't understand what you want from me honestly.

Do you want the "You're right" answer or the "You're wrong" answer?

Allow me to rephrase for you since this isn't working. You are right, but I do not like the idea of "Manipulate a list because I told you to manipulate a list." because it is boring. Is any part of that unclear to you still?

I thought I'd said very clearly that I simply didn't understand your reply. I don't want to make any point at all. My initial question was simply to make sure I understood what you suggested, so we're on the same page. I didn't get your reply, so asked for an answer again. Which you then answered with no, which I found confusing.

@Rainbolt okay, that's fine

5:18 PM

Well I just restated since you didn't understand. And I hardly changed it at all.

I had no idea what your were getting at with "I guess real life doesn't apply here."

anyway, we can move on now

I'd say, let's worry about the fluff later.

In real life, people use data structures because they need something that they offer.

We could mimic that here, or we could make people use data structures because we forced them to.

Our discussion about networks was an effort towards the latter.

right

My recent suggestion was an effort towards the former

I prefer writing a challenge that rewards good use of a particular data structure.

What do you prefer?

and with the networks idea I didn't see where the submissions would even manipulate the data structure at all. it just seemed to be an arbitrary KotH that happened to be played on a weighted graph instead of a grid.

5:21 PM

Each router maintains a routing table.

ah, k

I must have missed that

You didn't miss it. We never got that far

well, as I said, I'd prefer a challenge in which the submissions have to design the structure themselves, and the challenge should be such that there are not one or two obvious implementations. and ideally, the challenge should also require a variety of different operations to be performed on the structure, so that the trade-offs between them are interesting.

whether we wrap that in a nice story for fluff or not, I don't really care about at all right now, because I think that's something that can be added later, once we have a good core challenge.

Ok, in order to make players care about a trade-off, you need at least two resources and their score needs to be a combination of how well they use each.

One data structure might be fast and huge, while another is slow and miniscule.

So I suggest using time and space as your two measures of performance.

You can also use code size

you don't necessarily need two resources. a single resource upon which different operations impose different requirements is enough.

5:27 PM

Ok. So instead of one challenge with two resources we have multiple challenges with a single resource.

e.g. constant-time insertion doesn't allow for O(log n) access.

I use the word challenge loosely there. It's basically a subtask.

What's wrong with the bots themselves being a data structure?

@NathanMerrill if they don't have to represent that data structure somehow I don't really see how the challenge is about data structures in such a case.

@NathanMerrill Martin couldn't understand what being a node in a data structure had to do with data structures.

5:29 PM

A data structure, fundamentally, is how I traverse from node to node

What exactly does a node do though? What tasks are important in the life of a node?

it 1. stores a piece of data

well that's my point

and 2. transfers control to another node

if, in the life of a node, the node doesn't have to have a concept of the data structure is in, then I don't think the challenge would be fundamentally about data structures (from the perspective of the submissions)

5:31 PM

It doesn't transfer control. It literally just identifies its links. It's up the the controller to actually go visit those links.

sure, but that's irrelavant

Every node I've ever created in Data Structures class was like class Node { object value; pointer neighbor; }

but we would allow our nodes to have multiple neighbors

and the difficult choice would be to pick the correct neighbor

also, to replace a neighbor

That sounds like it would work.

The node can be aware of its surroundings without necessarily being aware of the list it lives in. So you could give it some responsibility.

@NathanMerrill so what knowledge do nodes have?

5:35 PM

Well the first node in a LinkedList is actually omnipotent. It knows everything.

The second node knows everything except for the existence of the first node

that makes sense for a directed tree to me

but not for a general graph

All nodes start in a doubly-linked circle, and each have a unique piece of information. The controller picks a node at random, requesting that information. The node then picks a neighbor. when the information is finally reached, the path from my node to the information is given

In a network, every node is eventually omnipotent unless one of the nodes is disconnected

The question is, how fast can you become omnipotent

100 points minus the number of nodes traversed is given to every node in the path

however, we need to prevent the bots from pointing to more than 3? nodes

You mean they can make or break connections? Like make handshakes?

5:38 PM

I'm sorry, I think there's still more to this in your head than in your messages. ^^ I can't piece it together. Do I fetch the information or send it? From/to where? How am I not entirely susceptible to the rest of the network screwing up?

you fetch the information

@MartinBüttner Both in my opinion. If you don't have it, you fetch it.

unless, of course, you have it yourself

lol, this discussion again has nothing to do with 'data structures' as it would ordinarily be understood

Rainbolt, a node will have 3 outgoing connectins

two nodes could potentially connect both ways

but it isn't required

5:41 PM

does a node only know it's neighbours, or the entire structure of the network?

only knows its neighbors

however, neighbors == nodes it has outgoing connections to

initially, they are the neighbors in the circle

but the circle will quickly degrade

then I really don't see a) how it can make any informed decisions and I still don't see b) what this challenge has to do with data structures from the point of view of the submissions, if there is no data structure in the challenge which they have to represent themselves.

@NathanMerrill how do the edges change?

@feersum Care to define what you think a data structure is, since apparently discussing nodes, fetching (which is literally visiting a series of nodes), and their outgoing connections has nothing to do with data structures?

a) When the path is finally found, all nodes involved in that path will be told of the path

so after the first "round", they do know about more than only their neighbours?

5:43 PM

b) Simply requiring a submission to build a data structure is boring. This seems like the next most interesting thing

c) They would change after a successful connection, and I could replace one of my neighbors with another

6 mins ago, by Rainbolt

You mean they can make or break connections? Like make handshakes?

Not like a handshake. It doesn't require a 2 way path. Only 1 way

@Rainbolt I think a "challenge about data structures" should have the submissions work with data structures, and not just the controller implement one. If a node only knew its neighbours and nothing more, than I don't think the data structure has any relevance for the submissions at all, so I wouldn't call it a challenge about data structures.

I see. You are going to be my friend whether you like it or not.

So I can say "my neighbor right here is useless. Let me replace him with another node"

5:46 PM

haha ok. And our neighbor is useless if they always make poor decisions?

yes

@MartinBüttner "and not just the controller implement one" Alright, so how do you force submissions to implement a data structure without giving them a goal that requires one?

@Rainbolt you don't, and I never said you couldn't give them a goal that requires one

I specifically asked "does a node only know it's neighbours, or the entire structure of the network?" to which I got the answer "only knows its neighbors" - in which case I don't have any information which to represent I could implement a data structure for. but that has been cleared up in Nathan's recent messages.

I agree, though, that it doesn't requiring building any complete data structures. However, finding a challenge where a custom built data structure performs better than a standard structure seems near impossible

I don't understand how reassigning your neighbors is not "building a data structure"

5:49 PM

@Rainbolt "but that has been cleared up in Nathan's recent messages."

@NathanMerrill it's easy by choosing a non-standard optimisation goal. ;) a simple code golf would achieve that.

like what?

like anything. e.g. the recent Rubik's cube challenge was an interesting data structure challenge I think.

"how do you represent the cube to be able to perform all the available rotations in as few characters as possible?"

1. Insertion must be O(1).
2. Removal must be O(1).
3. Accessing must be O(n).

go

if you're asking for a doubly-linked list, I'm giving you a doubly-linked list.

removal is O(n)

5:55 PM

A doubly-linked list has insertion of O(1)?

absolutely

@Rainbolt sure, append to the end

@NathanMerrill given the node object, yes.

a singly-linked list does at well

InsertionToEnd has O(1). But insertion?

oh, we don't care about order

5:56 PM

@Rainbolt there was no requirement of it being sorted, I think.

yeah

Ok, I don't care whether the list is sorted or not. If you want to insert a node at position 5 in a list with 10 elements, then that is not O(1)

@MartinBüttner given the node object, accessing is O(1) as well

@NathanMerrill lol okay... I was thinking of a .get_at_index(i) and .delete(object), as you'd have on arrays in some languages.

If you guys are assuming insertion to the end and that is O(1), then removal is also O(1) because you just remove the end.

And so is accessing, because you just access the end

5:58 PM

@Rainbolt I assumed that insertion means "here is an object, put it somewhere in your data structure, so I can find it again later"

yeah

In that case, removal is O(1) because, given an object, you have immediate links to both neighbors.

@NathanMerrill for removal O(1) you could keep a hash of removed objects and add it to that list. then when accessing, you check if each element is in that hash and skip it if so. of course that makes accessing O(N), where N is all elements you ever inserted

@Rainbolt yeah, that's what I thought

that would be O(log(n))

hashing is log(n)

oh

I understand

that means over use, the structure gets slower

that changes the definition of N

yep

6:01 PM

from N elements in the data structure to N elements ever in the data structure

heh, that's actually a pretty interesting data structure

you could keep it efficient by occasionally going through the data structure and removing the items in your removed set

in fact, you could do that as you access

although, then that would be nlog(n)

why n log n?

for each element I would check the hash

oh wait. if we are inserting removed objects into a hash, that's still log(n)

you would have to make the removal list a doubly-linked list as well

I really don't see where the log(n) is coming from. with a good hash and random-access memory, it should be O(1)

on average

worst case is O(n)

it's trivial to come up with a perfect hash though

just give the nodes a unique, increasing ID upon insertion

alternatively, don't use a hash, but a linked list for the removed objects, and traverse it in parallel with the main list when accessing

6:09 PM

the linked list will work

but optimizing (removing the removed items) will be O(n^2)

why?

with two linked lists?

just drop them when you pass them.

you don't remove anything from the second linked list

actually no

the order of removal isn't the same as the order of insertion

which means that I have to check every item in the removed list for each item in the insertion list

I think we need to be clear on the inputs for the functions (indices or objects)

@NathanMerrill oh I see

yeah, then you need a hash

6:12 PM

Anyways, moving on

lets say we make a challenge where the crux is building a data structure

once somebody has built that data structure, what is there for anybody else to do?

building a data structure that performs better?

how do we define that?

that's like asking "once someone has golfed this algorithm, why would anyone else golf it?"

@NathanMerrill space complexity, time complexity, code size, number of $ in the source code, I don't know.

if we base it off of complexity, we are going to quickly have an answer hit the limit, and then it is over

the other two seem like code golf (which isn't inherently bad)

so, code golfing a custom-built data structure seems feasible

we could also base it off of time spent

a mix of complexity and golf is also an option if we can balance it

@NathanMerrill you mean runtime?

yes

6:18 PM

yes

We could potentially have the controller tell the program what it is going to do before it does it (so number of insertions, removals, other operations)

that way the program can custom build a data structure on the fly

that would be sick

btw, I think we shouldn't focus on insertions, removal, access, sorting... I think the rubik's cube example shows that it gets more interesting if we think about large-scale restructuring operations.

I'm racking my brain, and I can't think of anything besides rubik's cubes

Ypnypn

Structures of lego pieces?

hmmm :)

@NathanMerrill we also might want to include space somehow (at least with a limit, if not in the score), otherwise people could just keep around one structure for each purpose and use the one that's most convenient each time.

@Ypnypn although it'll be tough to come up with a simple but flexible format to specify operations

6:58 PM

Ok. Consider this

we have legos that are all perfect cubes

and all sides connect with all other sides

we can attach single pieces

and then, detach multiple pieces (that split blocks), and place them in other locations

(by attaching two pieces on separate blocks)

hahaha that's great, literally a Lego structure made of data

however, I have no idea how to query that data

also, to make sure its not a physics simulation, should we allow two blocks to occupy the same space?

scoring could be one or more of bounding box size of the structure, amount of snaps/unsaps which must be made

two blocks shouldn't be able to occupy a space

oh I was thinking that we would specify the snaps/unsnaps

there are fundamentally two errors that could be thrown: snapping two blocks that are connected to each other but not near each other

and snapping two blocks which will cause blocks to overlap

what about trying to remove a block surrounded on all sides

7:08 PM

that should be allowed

but then it's not like legos at all!

because otherwise, we wouldn't allow removing a 2x2 where the only exit is a 1x1

and all sorts of other physics

you're talking about a physics simulator

guise check out my linked list

imgur.com/Pfohrrh

physics is good

and complicated, and not what the challenge is about

it doesn't really need to be like legos

but you could have a rule that a cube must have a path to the outside to be removed

7:14 PM

so, would I be allowed to remove a 2x2 block through a 1x1 exit?

and, concerning data structures, what is "outside"?

somewhere an infinite distance away

what's a 2x2 block?

I thought all blocks were same size

yeah, but I can have 4 1x1 blocks connected to each other

if it is decided that is too complicated, then it can be disallowed

and only 1 block can move

only 1 block can move?

I definitely don't like that then. The initial idea was restructuring of data structures on a large scale

what do you mean by this? "The initial idea was restructuring of data structures on a large scale"

7:19 PM

@feersum "btw, I think we shouldn't focus on insertions, removal, access, sorting... I think the rubik's cube example shows that it gets more interesting if we think about large-scale restructuring operations." (my own quote)

lol

ninja'd

if we were doing a traditional data structure, perhaps those are too boring

but not if it's a lego data structure

if we do legos, then we definitely need to allow multi-block restructuring

otherwise, its simply a piece of data with 8 outgoing connections

and I connect one by one

although, with multi-block its really not that much more complicated

@NathanMerrill unless you include operations like querying the coordinates of a block in space

and rotating groups etc.

7:28 PM

true

not sure how rotating groups would work

do we rotate on a diagonal?

if we don't make this actual lego, someone (@Ypnypn?) should definitely add lego the the fortnightly challenge ideas though

only one side?

@NathanMerrill I'd probably rotate about a horizontal or vertical axis, rubik's cube style

that is, you fix two coordinates, and rotate by 90 degrees about that line

so, a single face of a lego can rotate

I'm not sure I understand what you mean by that

7:31 PM

oh, are you simply talking about rotating lego structures in space?

not rotating different parts of the same structure

I was referring to the second

yeah I was referring to rotating lego structures in space

you meant turning one half of a connection?

that's also interesting

both are equally

because rotating a single face is identical to detaching and rotating

yes

8:22 PM

Can we get a quick-fire list of real world uses of data structures?

(boring or otherwise - let's just list everything)

seriously?

List of data structures

This is a list of data structures. For a wider list of terms, see list of terms relating to algorithms and data structures. For a comparison of running time of subset of this list see comparison of data structures. == Data types == === Primitive types === Boolean, true or false Character Floating-point, single-precision real number values Double, a wider floating-point size Integer, integral or fixed-precision values Enumerated type, a small set of uniquely named values === Composite types === (Sometimes also referred to as Plain old data structures.) Array Record (also called tuple o...

2

@feersum That was my best attempt and finding a way to avoid going around in circles...

I like non-orthogonal k-d trees ;)

How do you make them non-orthogonal??

Does each node store an angle?

You could project them onto any axes to start with I suppose

8:30 PM

Do people have a leaning towards:

1. Choosing an interesting data structure and setting a challenge on it

2. Setting a challenge where people try to find the best data structure to solve it

3. legos

2

2 for me 2

I don't know what though

What if we give each player a defined amount of storage space and then send them a sequence of pieces of data. After some time, we request a specific piece of data. The difficulty will be that we will sometimes send more data than can obviously fit into the storage space

The number of pieces of data sent before requesting could be random, so all players can score something

@trichoplax that's one option. in principle each node can be a hyperplane of arbitrary shape as long as it partitions space.

e.g. for circular-zero I actually had to implement a kd-tree where the nodes were circles.

@trichoplax Nathan had a similar idea, where you first inform the bot how many operations of each type you will perform, such that the bot can use adapt its data structure to the given case.

I played a game once exactly like that except with lines instead of arcs

8:37 PM

@feersum it's basically a clone of Qix/Jezzball (and their dozens of clones) using novel geometry

8:51 PM

@MartinBüttner I was thinking more along the lines of not telling them up front. So they get pieces of data one at a time with no knowledge of how many more are to follow. At random intervals a previous one is requested. Some players will only be able to provide the previous data for early stages, before having to delete old data to make room for new. Eventually everyone will be unable to respond, and you see who was successful for longest

@trichoplax That seems like a compression challenge.

hm I agree with Rainbolt though... it's more of a compression challenge, and of being lucky with which ones you get rid of.

The theme this week was poorly chosen IMO. It's just going to keep going in circles. Pick a new theme.

A data structure isn't something that you can do. It's something you use.

2

If you find a way to force people to use data structures to solve problems, you'll be alright. But I don't see how you intend to do that