Computer Science

« first day (762 days earlier) ← previous day next day → last day (3973 days later) »

Ilya_Gazman

11:02

The Board The Board is a two dimensional array of cells. Cells are populated by Animals. Every day, all Animals on the Board simultaneously make one move. If two or more Animals move to the same cell, they fight until one remains. The possible moves and attacks are as follows: Moves - { Move.U...

@vzn, @Raphael, @FrankW, @Gilles you must practice in this one.

Be ware of the shadow wolf.

3 hours later…

Raphael

14:30

@Ilya_Gazman I'm sure I don't.

Interesting, though. Especially the inherently flawed setup: by allowing all participants to see all submissions, you get those that specifically target some other solutions. Thus, it's unlikely you'll find any convergent "state", or an objectively meaningful solution.

Ilya_Gazman

15:02

@Raphael Unfortunately using other source submissions do not help. Most of them are random and you can't know what kind of wolf are you attacking.

vzn

hi ilya. saw that challenge. think its a decent competition. chatted in their chatroom. an edgy place there....! anyway they said that the top submissions involved variations on "doing nothing" ie not attacking. the game seems to favor combat-avoidant strategies. someone suggested a new competition where participants can "die from hunger" to fix that!

The Nineteenth Byte

The Nineteenth Byte: General discussion for codegolf.stackexc...

have been poking around that site. they have many great tags with potential CS overlap

some of the chat room denizens were talking about flocking behaviors also, which is a subj of serious CS study. eg

Q: Follow-the-leader algorithm in swarm formation: literature on the subject?

In an AI strategy game simulation, I devised an algorithm for forming a group and swarming a known location without communication among soldiers (ie. every individual agent makes a locally optimum decision without general knowledge of the map). I'm trying to get a more rigorous understanding of ...

ds.algorithms reference-request graph-algorithms natural-computing greedy-algorithms

Raphael

@Ilya_Gazman If you can beat the one that wins so far (statistically) and evade the others, you should not do too badly. It's not clear that or how, but it certainly is possible to exploit certain behaviours other submissions exhibit.

vzn

note also cs geek marzio recently had a high rated codegolf question...

Q: Kolmogorov-mania

The Kolmogorov complexity of a string s is defined as the length of the shortest program P that outputs s. If the length of P is shorter than the length of s, then s is said to be compressible, otherwise s is incompressible. Most strings are incompressible ... Write the shortest program that out...

code-golf puzzle kolmogorov-complexity

related to decryption & hash fns etc

many tags with potential cs content eg

algorithm math primes kolmogorov-complexity combinatorics regular-expression number-theory optimization cryptography compression graphs logic-gates fractal data-structures busy-beaver cellular-automata game-of-life ...

Raphael

15:32

@Juho Did you find anything?

@Gilles @FrankW New version of the algorithm analysis post trio, if you find the time.

FrankW

@Raphael In the last line of "Exmaple: Comparisons in Bubblesort" "since" should be "which", I think

Also in this paragraph, a more elaborate explanation how to arrive at the sum would be nice

General method, Sequence: In the last term of the equation /P should be /Q.

Raphael

@FrankW The closed form, or the sums themselves?

FrankW

@Raphael the arriving at the sum part.

Raphael

@FrankW "since" was intentional (1 instead of "some constant" because we count) but "which" is probably better.

@FrankW Jup, good catch.

@FrankW Done. Doesn't say much beyond "literal translation", though.

FrankW

15:49

For-Loops: add a short explanation of $c_{init_for}$ and $c_{step_for}$?

@Raphael Well, it's not difficult. But someone who has never seen it before might still benefit

Raphael

I've also added an item "expressions" in the Method section and elaborated on the factorial example.

@FrankW Doing that; should while-loops have a constant for jumping, too?

FrankW

@Raphael My gut feeleing is to leave it out. That constant should only be nonzero when looking at the machine instruction level -- and there the while will not be present anymore anyway.

Raphael

@FrankW Yea; the justification for the for-constants I have added now are higher-level, so it does not call for any of that.

Procedure calls, however, should definitely have that cost....

FrankW

For calls we can view it as part of the runtime of the procedure

However, I see your factorial example has them externalized.

In the final bullet of the section I'd replace "want" with "need".

Raphael

I like to highlight that procedure calls don't come for free; they may dominate runtime, after all.

We've had exam questions where using procedure calls was prudent for deriving lower runtime bounds. ^^

FrankW

16:00

Making them explicit is a good idea. Placing the cost into the caller or callee is what does not matter, as long as it is done consistently.

Raphael

16:17

@FrankW True. I don't think that's even a visible difference in the mathematical world.

Well, arguably you can drop c_return

Juho

16:28

@Raphael I'll check it!

Raphael

@Juho Wait a moment, I can upload a new version first.

No need for you to type the same things Frank did. :D

Juho

Okay, just let me know

Raphael

New version here, incorporating Frank's suggestions and some other stuff.

(that's a very useful commit message!)

Thank's guys!

I have to run now, see you tomorrow.

Juho

17:01

@Raphael I glanced over it, my comments are mostly typos or notational things: pastebin.com/raw.php?i=aRxwX4v7

It's probably too notation-heavy and scary for someone knowing next to nothing about asymptotic analysis, but hopefully it's helpful for someone

FrankW

"For-Foops" is an interesting typo ;)

Juho

Yeah, you'll probably catch more typos by running the thing through some proofreader

Raphael

17:52

@Juho Thanks, will check that out/in tomorrow.

@Juho I honestly don't know how to explain it with less notation, short of drowning people in examples. SE answers are not really a good format for inductive approaches.

@FrankW Haha, excellent! Of course, the author never reads the headlines again..

@Juho Good idea. Stackedit even tries to be helpful in this way, but I have long since trained myself to ignore red wiggles. :>

2 hours later…

Juho

20:16

@Raphael About explaining it all with as little notation as possible, I sympathize. I don't know how to best do it. You can't avoid it forever either, as a learner...

3 hours later…

Raphael

22:47

@Juho Maybe someone will post another answer to that effect. But I think a blackboard session is more effective for showing the process. So maybe we should record videos as answers? ;)

Huh, now I have half a mind to make a GIF (with TikZ, I guess) that shows the transformation from code to formulae. Hmmm.

I guess beginners will go for the second method and then quickly realize the the complexity only moved. :D

« first day (762 days earlier) ← previous day next day → last day (3973 days later) »

all rooms