Imagine trying to write that Rubik's Cube challenge and, every five minutes, someone says "What does this have to do with data structures?"

(I assume you were talking about the Rubik's Cube challenge?)

Does anyone else know what challenge he is talking about?

yes, the Rubik's Cube challenge

So answer the question then: What does the Rubik's Cube challenge have to do with data structures?

4. People are the data structure

@Rainbolt you need to model the cube. sounds like a data structure to me.

Why do you need to model the cube?

I don't know, can you solve it without modelling the cube?

I can't.

If you store it into an array, is that considered modelling it?

I'm literally trying to make you answer your own question.

sure

When I understand why you think that challenge has a data structure theme, I will understand the theme of this week the way you want me to understand it.

no, all you're doing is trying (really hard) to misunderstand my original question

If you can't answer your own question with something better than "I don't know." then you need to stop pushing it on others.

when asked whether your network idea was about data structures, I asked, because there was no data to be modelled (well, there was, but my question for whether there was, was answered with "no there isn't")

I stopped participating earlier because both you and feersum seem to have an idea of what a "data structure challenge" is despite my repeated attempt to explain that a data structure is a tool and not a challenge.

But you won't share that idea clearly.

the second you guys clarified that bots do get information about the network, I didn't push it any further, because obviously you need a data structure to model that network

Actually, right after that feersum jumped in with the same complaint.

(although that still doesn't mean that the emphasis of the challenge is necessarily on designing a good data structure, which would be nice for the given theme)

I still hold that DS are tools. The theme of this week is literally "Force people to use tools."

so was last week's theme... it went pretty well.

Genetic algorithms actually do something.

genetic algorithms are a tool

they are a solution, not a problem

yet, we managed to come up with a challenge

You know what I mean. Algorithms solve problems. Data structures do not solve problems. A screwdriver does not screw itself in.

It's how people use data structures that solve the problems.

And "how people use data structures" is an algorithm.

hm, I don't know... I really don't see a problem with a challenge along the lines of "here is a bunch of data you can model however you want. the following operations have to be performed on the data. you should optimise your implementation towards goals X, Y, Z."

whether this task is explicit or implicitly wrapped in koth and some interesting story seems irrelevant

What task?

the task of implementing a set of operations on a given sort of data.

I think you could give them any task that has any data at all. The crux is the goals.

The goals have to line up with why people use data structures in real life: performance. The operations have to be fast and not take much space.

there are obviously tasks that would require more elaborate structures for the data than others

@Rainbolt why do those goals have to be the same (as in real life)?

Again, the task does not determine what data structure you use. You disagreed but failed to back it up.

It's the performance goals that determine what data structure you use.

For example: You need to search. What structure to use? Who cares?

Another example: You need to search quickly. What structure to use? Now suddenly it matters.

of course, there's no reason to use an interesting data structure without goals

but given goals, the task will make a difference

But I'm saying that the task doesn't make a difference.

of course it does... do you insert more often than you remove? do access more often than you insert? are there any common restructuring operations you need to perform all the time?

you can't solve all of these with a single data structure given a goal

Why does it matter if you insert more than you remove?

Because you want the operation you do most to be fast?

of course

and you won't be able to make all of them fast

but my question was why the goals have to be performance goals. why wouldn't golfing also determine what kind of data structure you use? surely, some data structures will allow for shorter code than others.

and I think this could actually be more interesting, because the well-known structures aren't optimised towards that goal.

The amount of space your program takes up is a real issue. I only listed two. I didn't say my list was all inclusive.

My point was that it's the goal that drives what structure you use. Not the task.

Same task. Three different performance goals.

But how does this not depend on the task? Do I want to model something that resembles a sparse graph? Adjacency list. Do I want to model something that resembles a dense graph? Adjacency matrix. Do I not care about the graph at large but only traverse neighbours locally? Network of linked nodes.

My main point is that everyone should stop shooting down ideas with "What does this have to do with data structures." You can take literally any task that involves data retrieval, slap a performance criteria on it an suddenly everyone is using a data structure.

Let the idea play out, and then decide how to encourage the use of data structures.

@MartinBüttner What motivates you to model those things with those structures? Literally nothing is driving you to do these things. You just decided you were going to.

@Rainbolt I'd argue that "given n print the numbers from 1 to n" cannot be turned into a data structure challenge, because there is no data to be modelled in a data structure.

@Rainbolt I never claimed that different goals wouldn't require different structures.

I claim that the task will also determine the data structure.

You can take literally any task that involves data retrieval

@MartinBüttner I disagree.

Okay.

You have stated "Well I would use this for that." but you never explained why.

You might say that those structures are suited for those problems. And I might ask how they are suited. And then you would realize that I am right.

okay, let's say we have a time and a size constraint

you're given a sparse graph and you want to perform some operations on it. you'll probably want an O(E) space solution, because otherwise you waste loads of space, which won't be worth the time savings, so you use an adjacency list. now you're given a dense graph. so E ~ O(V^2) anyway. so you might as well switch to an adjacency matrix, because it won't affect storage much, but greatly improve time complexity of accesses.

you'll probably want an O(E) space solution, because otherwise you waste loads of space

So saving space is one goal.

You also mentioned time savings.

And because of these two things you want to use an adjacency list.

You gave zero reasons that were not performance related.

Assume we don't care about time or space. Why would you decide to use an adjacency list? What part of the task dictates what we decide to use?

wtf, dude... you're really ignoring what I'm saying. yes, the goals are relevant in determining the structure. I've never said the goals are irrelevant. what I'm saying is the task also matters (which you keep disagreeing with and then arguing that the goals are important). I don't know if you deliberately stopped reading my last message after the first half... I've listed a different use case, with the same goals, where a different data structure would be beneficial.

well, I've got to go have some dinner...

The goals are literally the only thing that determines the structure.

"What I'm saying is the task also matters " and I disagree.

then please refute my above example instead of ignoring it

You listed a different use case with different goals. The latter use case had something about complexity of accesses. If you want to compare apples and oranges to prove that apples are like oranges then go ahead.

same goals, different use case.

Different goals, different use case.

Is there an echo in here?

okay

later

I love your argument style of "If you refute half of what I say then I cannot move on until you refute the other half."

Has anyone come up with a proposal that Martin feels has something to do with data structures that isn't already posted?

If so, we kind of got derailed, so please summarize.

If not, I suggest changing the theme to be problem centric rather than tool centric.

"Problems that force people to use data structures" is far too broad.

so.. what's the idea?

BTW, full room today..

nobody is here? what happened? @MartinBüttner u there? U know what happened?

@Rainbolt u available?

@Rainbolt You didn't refute half of what I said. You disagreed with me, then (apparently as an argument) used half of what I said for an entirely different point (which I said multiple times I agreed with), and ignored the other half. But if you'll just claim that any relevant part of the task is part of the goal, then I can't argue with that, and we've been agreeing all along. brilliant! :)

@MartinBüttner so what's happening?

@TAbraham just a casual argument ;) ... nothing happened yet... amongst other things because Sp3000 (who suggested the theme) wasn't online yet

there's no rush, we've got 2 weeks to come up with something

so data structures is decided?

It seems like there's some problems deciding a topic..

@Rainbolt btw, it is ridiculous that you keep getting back to this point after any unrelated argument we have. we've established at least twice now, that this is not an issue any more.

BTW, did I disturb u by mentioning u?

@TAbraham yes

@TAbraham no

@MartinBüttner so what's the current idea?

there is none yet. a few ideas have been thrown around though, so feel free to read through the transcript (the earlier parts were arguably more productive than the latter)

@TAbraham I'm here now

I can only summarize the one idea that I was excited about. I'll let others cover the other ideas

I think efficiency was determined by number of hops through the network. I don't know that that was settled.

I also may have embellished a lot. Take my recollection with a grain of salt lol

The idea was that participants would maintain a routing table or some other data structure in order to win. However, the ability to replace your neighbors and forge new connections might prevent people from blindly copy pasting online code for routing tables (which is a good thing).

@Rainbolt Okay, I'm going to try to ask you a question, and please don't take it the wrong way, I'm genuinely interested, because the problem sounds interesting: is there an incentive to make the data structure representing the network particularly sophisticated? i.e. will give a good choice of data structure with a mediocre algorithm an advantage over a submission with a good algorithm and a mediocre data structure?

@Rainbolt Yes you're right. I've been trying to think of something along those lines that would be about efficient arrangement of data rather than compression, but I don't think the two can be easily separated so I'm back to square one...

Whatever you do, make sure Java and Mathematica do not have built-in types for it.

;)

In the real world, people use data structures. They obviously have reasons for this. Are any of those reasons likely to make up part of an interesting challenge?

Are there any settings for which the majority of well studied data structures would be unsuitable, so that something novel would be rewarded?

@trichoplax sure, constraints or optimisation goals. (on complexity, runtime, memory usage or code size)

@trichoplax definitely code size ;)

@MartinBüttner No well studied structures for low memory embedded systems...?

hm, I don't know. I'm sure there are some that are nicely golfable, but I doubt any of them were developed with that in mind.

(although I did say "majority", which I now realise isn't really what I should have asked...)

Could we make a specific task for which a generalised data structure would work, but could be beaten by something tailored to the task?