|Tuesday, October 16th, 2001|
chogyonim> do you have a link to a page on dynamic programming?
zorbathut> no :P
zorbathut> and my discussion with ambrose passed out of the buffer a while ago ^^;;
zorbathut> the basic idea for this, though, was "only store what you need", which in this case was the numbers on either side
zorbathut> so you make a 2d array, 10x10, then fill it with 0's
zorbathut> then go from there - each coordinate indicates a string that ends with those numbers
zorbathut> so you just match it up from there, and modify all the other points as you go, with max()
chogyonim> that's how I implemented my 500 pointer isn't it?
chogyonim> i only passed on the first and last blocks
chogyonim> rather than all the middle
zorbathut> *nod* bascially, yeah. you just keep an array of all the current longest-strings.
chogyonim> and then compare each following block to the arrays of existing trains
chogyonim> but wait
chogyonim> couldn't you have a situation
chogyonim> where 12-23-34-45 is your longest train
chogyonim> and the shorter train 12-23-36 was lost
chogyonim> but then the next two blocks are 66-66?
zorbathut> because in your  node it'll still have 3
chogyonim> NOW I get it
zorbathut> your  node will be 4, yes, but it doesn't matter :)
chogyonim> for each END type, you have a certain length
zorbathut> once you're done, you just scan the thing and dig out the highest length ;)
kyky> chogy, I found this one on google - http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html. I still prefer CLR's discussion on DP, though
chogyonim> and this is efficient? i'd hate to have to do the calculations on it's speed =D
zorbathut> chogy, it's linear-time. :)
chogyonim> LoL i already found that page
chogyonim> reading it in fact as we speak
zorbathut> assuming a constant domino max value.
chogyonim> wait let me see if I get this... take a situation with dominoes up to 3
zorbathut> man. I'm just realizing I invented this independently. that's kind of scary.
chogyonim> I have a 4x4 aray
chogyonim> let's say I have (like I said) 12, 23, 34, 45, 26, 66, 66
zorbathut> assuming you mean domino values from 0 to 3 - no limit on the number of dominoes
zorbathut> and 6 is more than 3. ;)
chogyonim> shut up
chogyonim> i'm using my old example under new parameters
chogyonim> stop bursting my bubble
zorbathut> heheh, okay.
chogyonim> ok ok
zorbathut> so, domino values from 0 to 9, let's make it? :P
zorbathut> it's just easier.
chogyonim> 0 to 9
chogyonim> so after 4 runs I have the following
chogyonim>  = 1
chogyonim>  = 2
System> guest101 has entered the room.
chogyonim>  = 3
System> guest101 is opening the 250-point problem.
System> guest101 is opening the 500-point problem.
chogyonim> then i get  =  + 1 which is 2
chogyonim> followed by all the 66's in the world
chogyonim> sounds good
System> mrblonde has logged out.
System> guest101 has left the room.
chogyonim> i'd always make sure that the new array space i'm assigning to doesn't already contain a valu greater than the new one
zorbathut> I think you'd end up with  being that, actually
zorbathut> keeping in mind that the first value is the left side of the string.
chogyonim> i'd end up with  =4
chogyonim> which is actually the same as my =4
chogyonim> so either way it's 4
chogyonim> but then if I came by a block 36 later, I wouldn't say "oh, 12,23,36 is 3" because I already have 4 in 
chogyonim> so i'd just ignore that 36?
chogyonim> do I sound like I understand?
zorbathut> *nod* think so :)
zorbathut> except you wouldn't ignore the 36
zorbathut> you'd turn it around and tack it on the end of your 6.
zorbathut> 12 23 36 66 63 :)
chogyonim> OK SHUT UP YOU GET THE POINT!! =D=D=D
chogyonim> thanks zorb
chogyonim> that was actually quite insightful
chogyonim> like, really
zorbathut> np :)
chogyonim> i'm gonna try coding that now in fact
zorbathut> and yeah, it's a nice technique
chogyonim> let's see if I can make it work
chogyonim> it's amazingly simple too
System> chogyonim is opening the 1000-point problem.
kyky> zorb, did you know about DP when you solved the museum tour prog about a month ago?
zorbathut> kyky, uhuh.
zorbathut> that's why I say I seem to have independently invented this technique. though it wasn't as full-formed
zorbathut> it was "oh, *this* would work! What an odd idea."
chogyonim> impressive, zorb
zorbathut> thanks :)
kyky> zorb: really, it is *very* darn impressive
chogyonim> i'd say we need to discuss and share techniques more often, but i doubt i think of anything you don't =P
kyky> zorb: the only person I know who came up with this technique without looking it up was my programming techer in HS. And it took him a couple of days, too.
zorbathut> kyky, wow. I think I must have done it in 10 or 15 minutes, considering it was during the competition and I had enough time to implement it O_O
zorbathut> I *must* have seen it somewhere else, but I can't think of anyplace I possibly could have.
kyky> zorb: you couldn't have seen *that* one - a similar one - may be, but not the museum tour ;-)
zorbathut> kyky, I mean the technique idea :)
zorbathut> and I really can't think of anyplace I might have seen it.
current mood: a bit scared
(6 comments |comment on this)
incidentally, the graph of (-1)^z is a corkscrew, if y is real and x is imaginary. Or vice-versa.
I'd always theorized on that, but I'd never managed to test it before today.
(I mean, it makes sense. (-1)^2 is 1, and (-1)^3 is -1, and what happens between that? It's certainly not going to approach 0. It only makes sense for || (-1)^x || == 1 for all values of x, therefore a corkscrew is the only possible shape. QED.)
(comment on this)
you know, that brings up another interesting question. Where does the corkscrew come from? It can't spring full-formed because that almost never happens in math. So how can you make it gradually appear?
You can't move the source point down through 0 and to 1, because that just makes it shrink and then come out as a line. *that* makes no sense. But - what if you rotate the source point around the imaginary axis?
I bet that would be interesting.
current mood: curious
(1 comment |comment on this)
Thinking about it, I think it would do very very strange things if you start at a point rotated around the complex axis. Because an easy way to rotate a point around the complex axis is (-1)^u. So the whole equation would end up being ((-1)^u)^y, which, as I remember, is identical to (-1)^(u*y). Which is definitely interesting, but makes *sense*. I'm going to have to graph this thing also.
On another note, Minotaur ships *absurdly* fast. I ordered this CD-R drive late on Friday, and it arrived today. That's, like, one business day :P
(1 comment |comment on this)