Zorba the Hutt (zorbathut) wrote,
Zorba the Hutt
zorbathut

  • Mood:
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> ohhh
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> uh-uh.
zorbathut> because in your [1][6] node it'll still have 3
chogyonim> OH
chogyonim> NOW I get it
zorbathut> your [1][5] 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 ;)
zorbathut> yup.
chogyonim> hmm
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
zorbathut> *nod*
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> hahhah
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> ok
chogyonim> 0 to 9
chogyonim> so after 4 runs I have the following
chogyonim> [1][2] = 1
chogyonim> [1][3] = 2
System> guest101 has entered the room.
chogyonim> [1][4] = 3
chogyonim> [1][5]=4
System> guest101 is opening the 250-point problem.
System> guest101 is opening the 500-point problem.
chogyonim> then i get [2][6] = [1][2] + 1 which is 2
chogyonim> followed by all the 66's in the world
chogyonim> ok
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
chogyonim> cool
chogyonim> =)
zorbathut> I think you'd end up with [1][6] being that, actually
zorbathut> keeping in mind that the first value is the left side of the string.
chogyonim> i'd end up with [1][6] =4
chogyonim> 12,26,66,66
chogyonim> which is actually the same as my [1][5]=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 [1][6]
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> hehheh
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.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments