The Nineteenth Byte

1:00 PM

Anyone who wants to vote before I award the bounty to Geobits question, do it in the next 10 minutes or so

Also, the transcript looks strangely cohesive despite the fact that those two statements were typed hours apart...

1:15 PM

Well I have an idea... but the output may well be horrible. I do not have any audio processing experience at all so I cannot even determine whether is is viable until I have created it!

The basic premise is to take random 1 second samples from an audio corpus, lets say 1 million, normalise the samples then using k-mean clustering to create a set of 1024 filters. Compression would be, for each second, record the reverse transform to the normalised 1 second sample (using 8 bits) then choosing the best matching filter and recording its index (i.e. 10 bits). thus 18 bits per second which is …

ProgrammerDan

Fascinating idea

mniip

regarding the 46 bits thing, there are 1,112,032 printable unicode codepoints

ProgrammerDan

I'd love to hear the output -- given the loss of information implied in the several lossy steps, I'd imagine the output would be rather different from the input, but since you're using a corpus approach, it'd be .. audible, and not noise, at the least

mniip

I'm currently messing with fft'ed samples

Moogie

yeah, In truth I have no idea what sound would be generated... i.e. noise or very simple tones

ProgrammerDan

1:21 PM

depends on how your decompress against your corpus

if you use the normalized index sample, it'll be ... less awesome, probably, then if you used the unnormalized 1 second sample from the corpus most transform similar to the normalized index sample. Or something.

Moogie

well I was thinking that might be the case, however storing 2^18 filters is probably going to be problematic... i.e. 2^18 (number of filters) * 44100 (freq) * 2 (16 bit sample)

it would also need a larger set of random 1 second samples to perform clustering.

ProgrammerDan

why would you store 2^18 filters?

Moogie

well there would be no need to store the reverse transform and thus i would now have an extra 8 bits per second I can utilise to generate filters... allowing "better" matching.

mniip

One thing I don't get though...

what's the shape of a dfft outcome?

Moogie

cant help you there... i have never had to deal with fourier transforms...

ProgrammerDan

1:29 PM

Gotcha, yeah, I was about to write something stupid only to realize that you were intending to store 8 bits of reverse transform from the original sample. Honestly, though, the data density of 8 bits is so low that it's not worth storing -- so you would probably be better off just storing the larger number of samples. 2^18 isn't so large -- 262144

mniip

it doesn't seem to be a smooth function

why 8?

ProgrammerDan

(to leave 10 for normalized sample lookup, and still fit within 18 bit boundary per second)

Moogie

the 8 and 10 are arbitrary at the moment... i might give more to the lookup table and less to the reverse normalisation.

I think it might be against the spirit of the competition if the users will need to download a 21 gig table of filters if i use the full 18 bits for the lookup table... :)

ProgrammerDan

hehehe

what if instead, you just used a tones table of some sort? something that could easily be generated, an enumeration of chords or tones?

mniip

but why is it 18 per second

ProgrammerDan

1:35 PM

that way you wouldn't have to download anything, just an index is an arbitrary pointer to one of the enumerated "basic sounds"

mniip

lol. Stripping the complex part of the fft sounds funny as hell

ProgrammerDan

@mniip I think that was based on some discussion in the comments on the question about the true effective bit rate per second when expressing as valid unicode, especially if UTF-8, or something ... that it came out to 18 bps

Moogie

@ProgrammerDan sure but then it is just a glorified midi :P and also i dont know how to generate tones :P

mniip

there are 1,112,032 printable unicode codepoints

ProgrammerDan

@Moogle :D Yeah -- I know. Not sure that any other approach is realistically feasible, though

But I'm hoping to be surprised, this looks like a great challenge to watch!

Moogie

1:38 PM

@mniip hmm... I may have mis-understood the 140 character limit.

i thought it was 140 bytes... aka 18.6667 bits per second

ProgrammerDan

no, 140 characters, in UTF-8

hmm

Moogie

hmm it states: "140 bytes or less of printable UTF-8-encoded text." which is a little ambigious

ProgrammerDan

@mniip How did you arrive at 46 bps? I'm curious your approach

mniip

log(1112032)/log(2)*140/60

Moogie

with 46 bps i dont know what to do with the extra bandwith! :P

ProgrammerDan

1:44 PM

@mniip Of course, excellent. Yeah -- so you've got all kinds of bandwidth, Moogie :D

Peter Taylor

@Moogie It's not at all ambiguous. A bad match for Twitter, yes, but not ambiguous.

Moogie

hmm... i guess it could just reduce the sample size to 500 milliseconds :)

140 bytes is specific... but so is printable UTF-8-encoded text... and both are contradictory... maybe if it was "140 symbols or less of UTF-8-encoded text"

Peter Taylor

2:07 PM

There's no contradiction. You can have 140 printable ASCII characters, 70 printable characters from U+0080 to U+07FF, ...

mniip

he never said a thing about ascii

Peter Taylor

Printable ASCII characters are exactly the printable Unicode characters which are represented in one byte in UTF-8.

mniip

I beleive twitter permits utf-8 and counts them as 1 character

so I'm going with that version

this waw a triwuww Still far from 140 though

Rusher

Oh man... think before I click

I didn't realize clicking that would just download something

So rude.

mniip

3:14 PM

Screw it, I don't have any more progress

Howard

3:32 PM

?

2

A: EBCDIC code golf (Happy birthday, System/360!)

4 byte this AE 26 06 D9 convert 2 byte 1B A7 this formula

What's going on there?

ProgramFOX

That doesn't really look like an answer to me...

Howard

But has two upvotes.

ProgramFOX

Strange.

undergroundmonorail

3:55 PM

Thank god, I finally fixed the thing that annoyed me the most about nano.

It wouldn't recognize '' as a valid string, so if you had another string in the same line everything from the second quote of the empty string to the first quote of the next one would be bold and green.

mniip

its presence?

undergroundmonorail

;)

I should really learn vim but I'm so lazy

I just noticed a small bug in the way that I did the fix, but even if I can't fix that it's way less annoying than the actual problem

Howard

4:15 PM

codegolf.stackexchange.com/a/26173

Second try ;-) Can please anyone check it? I can't test TI-BASIC but I am very sure that this code doesn't do what it pretends.

undergroundmonorail

@TheDoctor On March 18th you said you could test answers in TI-Basic. Still game?

Howard

I can't see where there is a map and not even where it wraps around.

Peter Taylor

5:11 PM

@Howard No, it's clearly not implementing the right graph.

squeamish ossifrage

6:34 PM

Anyone there?

mniip

No

squeamish ossifrage

:-(

I'm trying to find out what "DP" stands for

in this page ---> hackerrank.com/blog/w1-p-sequences

Wikipedia's disambiguation page isn't much help

Geobits

Dynamic Programming? Wait, no...

squeamish ossifrage

Could be.. the English on that page isn't brilliant

Geobits

Yea, I thought it was, then I wasn't sure, but now I'm thinking if that's not it, I really have no idea.

squeamish ossifrage

6:43 PM

I wish these people could explain themselves a bit better. I spent hours trying to solve this problem

and now I don't even understand the solution!

BTW, here's the original problem if anyone's interested: hackerrank.com/contests/w1/challenges/p-sequences

Peter Taylor

7:28 PM

@squeamishossifrage They could start by linking to the problem from the blog post, so that it has context. I think it must be intended to be DP, although that's not really the obvious way of expressing it.

Combinatorics on words: binary strings avoiding the substring 11.

squeamish ossifrage

@PeterTaylor You're right, their site organisation is not too good either.

And yes, it seems that dynamic programming is the right sort of tool for this kind of problem.

I'm going to stop trying to decipher their solution and read up on dynamic programming elsewhere. (Watching this on YouTube ATM: youtube.com/watch?v=OQ5jsbhAv_M)

Peter Taylor

9:48 PM

Dynamic programming isn't the right tool. It's complete overkill.

squeamish ossifrage

10:05 PM

Better than my lousy effort, though. I timed out on 16 out of 20 test cases :-/

How would you approach it?

Peter Taylor

Oh, I see. It's a bit more complicated than combinatorics on words.

squeamish ossifrage

You have to count lists of N numbers where no adjacent pair has a product greater than P

where N can be up to 1000 and P can be up to 1.0E9 (iirc)

Peter Taylor

Yes, I saw the initial bit of the blog post about boolean <= sqrt P or > sqrt P and jumped off on an oversimplification where that was the only important property.

Now that I've read enough to understand their full approach, it's reasonable.

A variant would be to make N also be of the order of 10^9.

I wonder whether it would still be feasible to control the errors enough to solve it with eigenanalysis of a transition matrix.

squeamish ossifrage

That sounds ... complicated

Transcript for