| --- Log opened Sat Jul 28 00:00:46 2012 |
| 00:01 | | McMartin [mcmartin@Nightstar-7d790d29.pltn13.sbcglobal.net] has quit [[NS] Quit: Hopefully this won't kernel panic...] |
| 00:20 | | McMartin [mcmartin@Nightstar-7d790d29.pltn13.sbcglobal.net] has joined #code |
| 00:20 | | mode/#code [+ao McMartin McMartin] by ChanServ |
| 01:03 | | You're now known as TheWatcher[T-2] |
| 01:06 | | You're now known as TheWatcher[zZzZ] |
| 01:40 | | Attilla [Obsolete@Nightstar-5dc38631.as43234.net] has quit [Ping timeout: 121 seconds] |
| 02:59 | | Kindamoody[zZz] is now known as Kindamoody |
| 04:07 | | Kindamoody is now known as Kindamoody|gaming |
| 04:16 | <&McMartin> | Woo |
| 04:16 | <&McMartin> | Top 100 4clojure hacker |
| 04:16 | <&McMartin> | http://www.4clojure.com/users |
| 04:28 | | iospace is now known as iospacedout |
| 05:36 | | Kindamoody|gaming is now known as Kindamoody |
| 06:48 | <~Vornicus> | I should get around to learning a new langauge properly, i haven't done it in a while. |
| 08:30 | | Kindamoody is now known as Kindamoody|afk |
| 08:50 | <&McMartin> | I should be learning Android properly =( |
| 09:10 | | Kindamoody|afk is now known as Kindamoody |
| 09:12 | | You're now known as TheWatcher |
| 09:29 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 09:53 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 09:53 | | mode/#code [+o himi] by ChanServ |
| 10:34 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 10:42 | | You're now known as TheWatcher[afk] |
| 11:27 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 11:27 | | mode/#code [+o himi] by ChanServ |
| 11:34 | | Attilla [Obsolete@Nightstar-5dc38631.as43234.net] has joined #code |
| 12:01 | | iospacedout is now known as iospace |
| 12:04 | | himi-cat [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 12:04 | | himi [fow035@Nightstar-5d05bada.internode.on.net] has quit [Connection reset by peer] |
| 12:14 | | Rhamphoryncus [rhamph@Nightstar-5697f7e2.abhsia.telus.net] has quit [Client exited] |
| 12:42 | | himi-cat [fow035@Nightstar-5d05bada.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 13:10 | <&ToxicFrog> | Vornicus: get on the bandwagon and learn Clojure~ |
| 13:19 | | iospace is now known as io|BAND_CAMP |
| 13:32 | | himi-cat [fow035@Nightstar-5d05bada.internode.on.net] has joined #code |
| 14:23 | | Kindamoody is now known as Kindamoody|out |
| 15:19 | | RichyB [MyCatVerbs@Nightstar-3b2c2db2.bethere.co.uk] has joined #code |
| 16:03 | | Moltare [Moltare@583787.FF2A18.190FE2.4D81A1] has quit [Ping timeout: 121 seconds] |
| 16:03 | | Moltare [Moltare@583787.FF2A18.190FE2.4D81A1] has joined #code |
| 16:38 | | Moltare [Moltare@583787.FF2A18.190FE2.4D81A1] has quit [Ping timeout: 121 seconds] |
| 16:38 | | Moltare [Moltare@583787.FF2A18.190FE2.4D81A1] has joined #code |
| 16:41 | | RichyB [MyCatVerbs@Nightstar-3b2c2db2.bethere.co.uk] has quit [[NS] Quit: Leaving] |
| 16:54 | | Moltare [Moltare@583787.FF2A18.190FE2.4D81A1] has quit [Ping timeout: 121 seconds] |
| 16:57 | | Moltare [Moltare@583787.FF2A18.190FE2.4D81A1] has joined #code |
| 17:12 | | Kindamoody|out is now known as Kindamoody |
| 19:45 | | Kindamoody is now known as Kindamoody[zZz] |
| 19:48 | | Rhamphoryncus [rhamph@Nightstar-5697f7e2.abhsia.telus.net] has joined #code |
| 21:20 | | Vash [Vash@Nightstar-e8057de2.wlfrct.sbcglobal.net] has joined #code |
| 21:20 | | mode/#code [+o Vash] by ChanServ |
| 21:46 | | You're now known as TheWatcher |
| 21:56 | < sshine> | I |
| 21:57 | <~Vornicus> | You what |
| 21:57 | < sshine> | I'm generating permutations. my current strategy is: look from the last element towards the first for the first occurence a,b where b < a, switch those. |
| 21:58 | <~Vornicus> | Okay hang on. |
| 21:58 | < sshine> | e.g. [1,2,3,4,5] -> [1,2,3,5,4] |
| 21:59 | <~Vornicus> | (but first, what language? some languages have a permutation finder built in) |
| 21:59 | < sshine> | Haskell. |
| 21:59 | < sshine> | oh shoot, it has. |
| 21:59 | < sshine> | and it's called "permutations". |
| 22:00 | <~Vornicus> | Yeah, I can't really imagine haskell without one. |
| 22:00 | <~Vornicus> | (Python has one too, it's in itertools) |
| 22:02 | < sshine> | how about a range 1 10 ==> [1,...,10]? |
| 22:02 | < sshine> | oh. shoot. range |
| 22:03 | <~Vornicus> | I learned how to do that in haskell once, after I gave up because I couldn't figure out how to do anything. |
| 22:03 | < sshine> | oh... [1..10]. there's sugar for it. |
| 22:03 | < sshine> | it's been a year since I coded haskell, except for ICFP, but I didn't perform very well. |
| 22:05 | < sshine> | shit... I'm solving this Project Euler task for generating permutations. it's problem 24. I skipped it when I first started university because I found it difficult. |
| 22:05 | < sshine> | now I solved it with a Haskell one-liner four years later. |
| 22:06 | <~Vornicus> | My python version of euler24 is also one line. |
| 22:07 | < sshine> | right. |
| 22:07 | <~Vornicus> | Well, sort of. I built a thing that finds permutation by index numbers. |
| 22:07 | <~Vornicus> | And then factored that out because I needed it elsewhere. |
| 22:08 | <~Vornicus> | It's ten lines. |
| 22:08 | | Vash [Vash@Nightstar-e8057de2.wlfrct.sbcglobal.net] has quit [[NS] Quit: I lovecraft Vorn!] |
| 22:13 | <&McMartin> | Standard ML doesn't have one but there's boilerplate code for it, so IIRC I translated that boilerplate to Haskell |
| 22:15 | < sshine> | I only have 26 completed tasks from my 1st year. I should get it to at least 50 this summer. |
| 22:33 | <~Vornicus> | If you need any help, I've gotten to like 140 |
| 22:34 | < sshine> | haha. |
| 22:34 | < sshine> | that's nice. |
| 22:37 | < sshine> | I really like Hoogle. |
| 22:40 | <~Vornicus> | hoogle? |
| 22:41 | < sshine> | Haskell's function search engine. you insert a type signature, and it looks through standard library and extended packages for functions matching that signature. it takes polymorphism and similarities into account |
| 22:43 | < sshine> | e.g. I have a function for generating the next permutation, and I want a list of permutations. so I think (a -> a) is my function, and given one value of a, I want another a... (a -> a) -> a -> a gave me Data.List.iterate as result number 4, even though its signature is (a -> a) -> a -> [a], which was, when I think about it, what I really wanted. |
| 22:44 | < sshine> | having this kind of search engine, I am sure, greatly reduces the amount of boilerplate. |
| 22:44 | < sshine> | it makes large standard libraries actually useful. |
| 22:45 | < sshine> | otherwise people start solving already solved problems in their little, un-idiomatic, wrong ways. |
| 22:46 | < froztbyte> | I should do some euler again |
| 22:46 | < sshine> | froztbyte, how many have you made? |
| 22:47 | < froztbyte> | the issue I usually run into is a lack of exposure on the maths side of things, so I'll get to some problem that you can brute force, or solve smartly |
| 22:47 | < sshine> | I'm always short of math. |
| 22:47 | < froztbyte> | but I just don't know the specifics for the smart option, and don't know the names for what to search for :P |
| 22:47 | < froztbyte> | sshine: 15~20, at most |
| 22:47 | < froztbyte> | lemme see |
| 22:51 | < froztbyte> | 16 |
| 22:51 | < froztbyte> | done: 1,2,3,4,5,6,7,8,9,10,12,13,14,16,20,25 |
| 22:51 | < froztbyte> | aka "all the really easy ones on the first page or so" |
| 22:51 | < froztbyte> | 8 was fun |
| 22:52 | < sshine> | :P |
| 22:52 | < froztbyte> | the last one I started working on was with a triangle of numbers |
| 22:52 | < sshine> | I've done 1-23,25,30,48 |
| 22:52 | < froztbyte> | and you have to find the move-by-diagonal-neighbor path that adds up to either the highest or lowest possible path |
| 22:53 | <~Vornicus> | http://pastebin.com/v8w08SYi this is my permutation by number thingy. |
| 22:53 | < froztbyte> | can't remember if it was min/max |
| 22:53 | < froztbyte> | now that one I suppose you can just walk from the top of the tree |
| 22:55 | <~Vornicus> | Can, but you should be careful - you can brute force it (2^rows actions) or do it right (rows^2 actions) |
| 22:55 | < froztbyte> | this is the thing |
| 22:55 | < froztbyte> | doing it from the top would likely only involve the local minimum for each move |
| 22:55 | < froztbyte> | which means walking each decision tree |
| 22:56 | < froztbyte> | walking it from the bottom means less paths, I think |
| 22:56 | < froztbyte> | but I'm still not sure if it's the right way |
| 22:56 | < sshine> | froztbyte, DP is the trick. |
| 22:56 | < froztbyte> | DP? |
| 22:56 | < sshine> | (not the porn genre) |
| 22:56 | < sshine> | dynamic programming |
| 22:56 | < froztbyte> | ah |
| 22:56 | < froztbyte> | in what sense? |
| 22:57 | < sshine> | dynamic programming is useful if one's problem displays optimal substructure and overlapping subproblems. |
| 22:57 | | * froztbyte whips out scythe (his newly-acquired air), does problem 22 |
| 22:57 | <~Vornicus> | And boy are there overlapping subproblems here. |
| 22:58 | < froztbyte> | sshine: could you eloborate a bit more about the specifics of what you mean? |
| 22:58 | < froztbyte> | I mean, my approach to that one is very head-on |
| 22:58 | < froztbyte> | so I'm wondering what better ways exist |
| 22:59 | < froztbyte> | also the cat likes my wifi antennas -_- |
| 22:59 | < froztbyte> | (they're 8dbi, so they're about 20cm tall) |
| 22:59 | <&ToxicFrog> | froztbyte: dynamic programming is just a fancy way of saying "memoize it" |
| 22:59 | < sshine> | froztbyte, overlapping substructure: if you have 2^n paths, some route between two nodes a,b is in several of those paths. |
| 23:00 | <~Vornicus> | Consider for a moment the demo one: the maximum path from the 4 in second to last row, will be the same whether you come /from/ the 7 or 4 above it. |
| 23:00 | < sshine> | froztbyte, yeah, it just means you save the best way to get from a to b, so whenever another path uses that route, you already know it, so you don't need to find out again. you just use a O(1) memory access function. |
| 23:00 | < froztbyte> | which problem was this? I only recall its details, not the actual problem number :P |
| 23:00 | <~Vornicus> | #18 |
| 23:00 | < froztbyte> | sshine: ah I see |
| 23:00 | < froztbyte> | vorn: ta |
| 23:00 | < sshine> | froztbyte, optimal substructure means: if you find an optimal way from a to b, it doesn't matter which path we're in... it's always going to be the optimal way from a to b. |
| 23:00 | <~Vornicus> | and #67, which is Much Larger but the same problem. |
| 23:01 | < sshine> | froztbyte, sometimes you have one property but not the other. in that case dynamic programming is not the solution. |
| 23:02 | <~Vornicus> | (you can also do this from the top: You can determine the best paths from the top to the nth row, and use those values to determine the best paths to the n+1th row, etc, and then just hit max() on the results for the last row) |
| 23:03 | < sshine> | in DP, top-down vs. bottom-up refers to the order you find solutions to subproblems. |
| 23:04 | < sshine> | if you know nothing about where the solution is, you can't say which gives you the answer faster. |
| 23:04 | < sshine> | e.g. going top-down you might find a really optimal-looking path which, at the end, you get a huge number that rejects the rest of the good-looking path completely. |
| 23:06 | <~Vornicus> | Actually in this case since you have to cover every location all told anyway |
| 23:23 | | * Vornicus eyes this code |
| 23:24 | <~Vornicus> | what the space am I doing in there. |
| 23:24 | <~Vornicus> | Oh, right. I built the factoradic, so I need that for loop, derp |
| 23:30 | < froztbyte> | sshine / Vornicus: I see |
| 23:31 | < froztbyte> | my mac still needs a bit of setup :/ |
| 23:31 | < froztbyte> | and I need to figure out what the right keys are for line navigation like I'm used to doing with ctrl+arrows on other things |
| 23:42 | < sshine> | my new Linux installation still needs a bit of set-up. wifi and battery status aren't showing anywhere. |
| --- Log closed Sun Jul 29 00:00:00 2012 |