1:20 AM
@Joey: o/

Magic! A new room.

Yepyep. :-D

While we're at it. Two task ideas:
1. some cellular automaton on a hexagonal grid (might be a worthwhile distraction from the endless GoL)

@Joey I <3 the hex grid idea. Reminds me of some of the turn-based strategy games of my childhood. :-D

2. Given a rectangular room, a position of a ball and a direction of the ball, work out after how many bounces it lands at a certain point on an edge

1:22 AM
124

The challenge The shortest code by character count to input a 2D representation of a board, and output 'true' or 'false' according to the input. The board is made out of 4 types of tiles: # - A solid wall x - The target the laser has to hit / or \ - Mirrors pointing to a direction (depends ...

no no, not with mirrors
and yes, not as cool as Lasers
I'm not LiraNuna ;)

Hahahahaha.
@Joey LiraNuna actually gave me some (helpful) feedback re my last golf (cdbmake). He thinks I should stop with the "mathsy" golf questions already. :-P
He thinks that the ASCII art ones generally have more appeal because they require more lateral thinking.

He once said similar things to me ;)
I gave him hypftier.de/dump/codegolf2010/Aufgaben.pdf this. The problem set we used in our local contest

Nice. :-)

and from which I drew all problems I posted so far. Back then I noticed that creating good to golf tasks isn't very easy :)
I think it took us about two weeks to come up with the tasks, reference solutions and sample inputs/outputs

1:26 AM
@Joey That would partly be why he takes so long to come up with new questions, also.

Indeed

Apparently, he writes reference solutions to each one first, to make sure they're solvable within reasonable character limits.

well, Robot finds Kitten is a bit too long for my taste

From what he tells me, each of his puzzles should be solvable within 300 chars or so, so if the best solution takes 400+ chars, people aren't trying hard enough. ;-)
This goes double for Robot Finds Kitten.

If I need two days or more to come up even with an ungolfed solution ... well, there's not too much motivation to golf it down, or even retry with a different approach

1:28 AM
Well, the most straightforward solution is Dijkstra. (You do have to tweak it some since it's not just minimal distance, but also minimal number of turns.)

I usually aim for 100–200 chars
I should definitely revisit all the algorithms some day ;)
been a few years since I last implemented them

I flunked my on-site Google interview because I forgot all my graphing algorithms.
One of the questions posed would be easily solvable with Dijkstra if I remembered to use it. :-P

I think I could remember Bellman-Ford if I tried. Not a good sign ;)

Hehehehe. Well, brush 'em up before you apply to Google. ;-)

but I doubt I ever will

1:30 AM
Nice. :-D

a fellow student of mine currently has an internship at Google in Dublin
I wouldn't have expected it from him but it doesn't surprise me too much. He is good :)

Fancy pants. :-)

Me not so much. And I can hardly call golfing a useful skill for applying somewhere ;)
Re the hex grid ...
I think I'd rather write a program to try that than to draw more hex grids ...

@Joey Well, it demonstrates a certain type of sharp thinking, right? ;-)

And as for the bouncing ball, that was more thought in that way: hypftier.de/temp/IMG_8350.JPG

1:34 AM
It's nice that you draw all these things out. :-P

Well, possibly. But I fear most recruiters wouldn't know about it ;)
Pen+Paper takes less effort than writing code ;)
Oh, and as for problems. Number 3 (or 0, since I posted it a few days ago already):

I remember seeing that.

Hm, does Golly support hex grids?

@Joey I've not seen anything in the screenshots that suggest so (and I've not used the program very much), but never say never. :-)

I have it somewhere here ... let me look :)
had to show something to a colleague recently who was optimizing our cellular automata simulators

1:46 AM
*nods*

No hex grids there :(

2:19 AM
Ah well, bed calls. I think I'll just write me a small SVG for a A4 hex grid tomorrow and print it. Trivial to write and plenty of room to play around, then ;)

2:36 AM
@Joey Have fun! :-D

8 hours later…
10:20 AM
Random task idea: Get ASCII art musical notation and figure out the frequencies of the notes to play.
Optionally play them without length penalty

7 hours later…
5:28 PM
@Joey Fancy. :-)

5:54 PM
@ChrisJesterYoung Could be as fancy as I like, actually ;) Musical notation can be very complex
support different clefs (at least F and G), accidentals, notes above and below the lines, different note lengths, ...
@Chris: hypftier.de/temp/cg4.txt as a rough idea how input could look like ;)

Require C clef too, just for good measure. ;-)
(Granted, being mostly a piano-player, I almost never see C clef, but still. :-P)
Question is, with regard to frequency, which tuning system should be used? Or is that left open to the implementer? ;-)

that was the weird one that also could be shifted, right? ;)

Yep. :-P

(I've only ever played the piano and sung in a choir, so I only required G and F ;))

Ditto. :-P

6:03 PM
well, I didn't try to draw the clefs in ASCII yet ;)

That could be interesting. :-P

well, implementers will only need one part they can recognize and then just switch on that. Could be a single character so for an implementation it's probably irrelevant how ugly it looks
still, I guess, this task could be somewhat complex :)
Different note lengths could be fun too. Though I think only 1/1, 1/4 and 1/8 can be reasonably distinguished in above form

6:21 PM
@Joey Quite. :-)

4 hours later…
9:56 PM
Hm, why do I have so many task ideas right now? That's downright scary
I just need to write them down, now. And implement them. And golf them. Ah well.
(and drawing a G clef in ASCII art is ugly ... even with JavE)

@Joey All of the above. :-D

@ChrisJesterYoung Well, I can't post a problem if I don't have something to solve it and I can't do it if I don't have something to generate input (for the bridges and tunnels, for example).
I don't need to golf them, though. I have my lackeys for that coughs well, Ventero at least ;)

@Joey Hehehehehe.
@Joey But yeah, writing new, interesting problems is hard work. Just like writing new, interesting lesson plans. :-)

10:12 PM
lesson plans? What are you doing? ;)

10:27 PM

@Joey I have a teaching diploma. I can't say I used to be a teacher as such, since I didn't formally have my own classroom, but.... ;-)
gist: CipherSaber code golf, 2010-11-07 07:19:50Z
```Find the shortest way to write [CipherSaber](http://en.wikipedia.org/wiki/CipherSaber). There are several parts to this puzzle:

## RC4/Arcfour

[Arcfour is fully specified elsewhere](http://www.mozilla.org/projects/security/pki/nss/draft-kaukonen-cipher-arcfour-03.txt), but for completeness, I'll describe it here.

### Key setup

Set up two arrays, `S` and `S2`, both of length 256, where `k_1` is the first byte of the key, and `k_n` is the last.

S = [0, ..., 255]
S2 = [k_1, ..., k_n, k_1, ...]

(`S2` is filled with the bytes of the key, again and again, until all 256 bytes are filled up.)

Then, initialise `j` to 0, and shuffle 256 times:

j = 0
for i in (0 .. 255)
j = (j + S[i] + S2[i]) mod 256
swap S[i], S[j]
end

This completes key setup. The `S2` array is no longer used here, and can be scrubbed.

### Cipher stream generation

Initialise `i` and `j` to 0, then generate the key stream as follows:

i = 0
j = 0
while true
i = (i + 1) mod 256
j = (j + S[i]) mod 256
swap S[i], S[j]
k = (S[i] + S[j]) mod 256
yield S[k]
end

### Encrypting/decrypting data

+ To encrypt, XOR the keystream output with the plaintext
+ To decrypt, XOR the keystream output with the ciphertext

## CipherSaber

CipherSaber (which is what we're solving in this question) is a variation of RC4/Arcfour in two ways:

### 10-byte IV/nonce

When encrypting a message, 10 random bytes should be obtained, such as via `/dev/urandom`, and be written into the first 10 bytes of the encrypted output. When decrypting a message, the first 10 bytes of the input is the IV used to encrypt it.

The RC4/Arcfour key setup stage is run with `passphrase || IV` as the key, where `passphrase` is the user-specified passphrase, `IV` is as described above, and `||` is concatenation. So, a passphrase of "Hello, world!" and an IV of "supercalif" (however unlikely that is :-P) would result in a key of "Hello, world!supercalif".

### Multiple iterations of key setup

In order to help prevent the vulnerability that made WEP encryption completely broken, the key setup stage of RC4 is run a user-specified number of times. The value of `j` should be retained between iterations.

Because of this variation on the key setup, using your system's RC4 is unlikely to work (although kudos to you if you pull it off :-D).

## Test vectors

Here are some [test vectors](http://www.cypherspace.org/adam/csvec/) you can use to test your programs. I can post some more if people want more data to test with.```
@Joey Or, since you have enough rep to see the original (deleted) post:

@ChrisJesterYoung Noticed both. But didn't you want to post them here as well?
s/here/on cg.se/

@Joey Do you think it's ready for prime time here? Or will it just get nuked again? :-)

@ChrisJesterYoung We have a task that calls for reimplementing PCRE (which I actually dislike for its complexity). I doubt it'd be very much out of place here ;-)

@Joey Okay. I'll...ask an SO mod to migrate the question here or something (and thus resurrect @gnibbler's and my answers thereto).

10:31 PM
(Although reimplementing PCRE to use an efficient algorithm might actually be a nice challenge. And a useul one to boot)

*nods*

There's the article :)
But I'm fairly sure you already know it.

@Joey That sounds hardcore, but would be fun to implement, yes. :-)

@ChrisJesterYoung Well, I couldn't implement it, probably. I'm not that good with all that compiler/parser stuff ;)

@Joey Not even with Boost.Spirit? ;-)

10:38 PM
@ChrisJesterYoung If only I had a clue of C++ ;)

@Joey Hmm. So what is your home language, anyway?

PowerShell, Java, C#. Probably unordered.
let me find something
Might no longer be up-to-date. And little useful stuff on it, sadly

@Joey Interesting. :-)

spent the last few weeks in Java, though.
It's not my favorite language, however ;)
but judging from the TIOBE index it might be my best chance at a job ;)

@Joey Yes, I can probably agree with that. ;-)
/me has a Java certification, so is biased. :-P

10:45 PM
oh :)

But, my favourite language is probably Scheme, with Ruby a distant second.

Well, I'm not too convinced I actually want to move out of Academia. But I'm not too convinced I'd be good enough to stay here after my diploma, either.
Then there is my specialization which is HCI and UX for which there might be a demand but somehow most companies don't seem to need people there

@Joey I'm sure Apple always looks for HCI/UX people. :-P
@Joey You'll have to learn Objective-C, though. :-P

@ChrisJesterYoung I guess Apple is one of the places where I wouldn't want to be ;)

@RebeccaChernoff: o/

10:48 PM
but sure, most large corporations look for them. But with my grades, finding a job at Google, Apple, MS, IBM, etc. is probably hopeless ;)
:O
/me hides

@Joey Hehehehe, actually, I declined to give my GPA to Google, because it was crap. :-P
@Joey Not necessarily the best advice, since I'm not actually working for Google. But, never hurts to try. :-P

@ChrisJesterYoung Will try in a few months, then. Until then I probably have other thoughts in my head than finding a job. In fact, that was never somethnig I really thought about as long as I was studying. Probably the wrong way to approach that, but so far it served me well ;)

also, why are you hiding?

I didn't reply to the mail ;)

this is true.
50 lashes with a wet noodle!

10:52 PM
ouch

@RebeccaChernoff /me lashes StackExchangeScripts 50x with a wet noodle. ;-P

o:
can use /me, so meh q:

@Joey Lemme know if you want me to put you in touch with a Google recruiter. :-)

@RebeccaChernoff Hm, those would require a change of browser. Too lazy right now. Though keyboard shortcuts would come in handy, especially when replying to someone (given that the icon is tiny)

@RebeccaChernoff Meh. :-P

10:56 PM
@ChrisJesterYoung I will. Thanks. Though might take a while until then. Thesis and stuff ;)

@Joey What browser are you on?

@RebeccaChernoff I dare not say it ;)

@Joey No hurry. It's not my commission at stake (I'm just a programmer, what commission?). :-P

IE supports userscripts with Trixie.
Did I guess right? (;

@RebeccaChernoff last time I looked there was IE7Pro (which brings much stuff I do not need or want) and a few projects that force .NET onto IE which is usually a bad idea.
Let me look :)
@RebeccaChernoff And yes, you did guess correctly. Though it's 9 RC at least

10:57 PM
there are instructions there for each browser

Hm, we definitely still need a good GrIEsemonkey :|

@Joey Surely, you could write one? ;-)

@ChrisJesterYoung Without knowledge of C++ and COM ... sounds like a plan ;)

@Joey MS's ads suggest that IE9 will have a built-in Firebug-like thing. Well, maybe it could have a built-in userscripts thing too. :-P
@Joey Awwww.

Well, the firebug-like thing has been there for ages, actually. But it got a little more usable, yes :)
ok, now let me try whether the userscript actually works

11:27 PM
tries something
hm, appears to work
after many hoops and hurdles

Feel free to edit the wiki if appropriate.

Well, I'm using a non-final browser and I deemed some things Trixie did inappropriate, such as putting the scripts into its installation directory. So I created a symlink from my home there so that I don't need administrative permissions every time I want to add a script; Trxie's config was similarly located with the same permission issues. And it came with half a second initial load time + almost a second navigation time which slowed everything down pretty much :)

I just copied instructions from their page, I didn't actually try them.
So blah (;

:P
@RebeccaChernoff: What brings you here, actually?

11:43 PM
Gotta keep @ChrisJesterYoung in line (;

@RebeccaChernoff ;-)

@RebeccaChernoff Oh, he behaved, as far as I could tell :)
@ChrisJesterYoung: jave.de/blog2/?p=36 looks interesting, alas I have no idea how well color and graphics go with arbitrary choice of language.

He's a sneaky one though. You can't be too careful!

@Joey Well, you can at least specify which colour each segment should have, even if as a "memory status dump" kind of thing. That is at least cross-language.
Bonus points for showing it graphically, of course. :-)
@RebeccaChernoff Look who's talking. q:

I KNOW NOT WHAT YOU SPEAK OF