2009 Jul 05 23:55:04  -*- inimino rings a tiny, invisible bell
2009 Jul 05 23:59:13  <offby1> mummy says: every time a bell wings, another grad student gets his wings
2009 Jul 06 00:00:51  <inimino> mariorz, aamar, still around?
2009 Jul 06 00:01:03  <aamar> still around
2009 Jul 06 00:01:50  <inimino> I didn't get any further than 3.19
2009 Jul 06 00:04:06  <aamar> How about going until there?
2009 Jul 06 00:04:16  <aamar> I found these problems to take a long time.
2009 Jul 06 00:04:33  <inimino> alright
2009 Jul 06 00:04:47  <inimino> yeah they took some time
2009 Jul 06 00:05:13  <inimino> shall we start?
2009 Jul 06 00:07:09  <aamar> ok
2009 Jul 06 00:07:27  <inimino> ok
2009 Jul 06 00:08:06  <aamar> 3.9 ?
2009 Jul 06 00:08:32  <inimino> I think so
2009 Jul 06 00:08:37  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.9
2009 Jul 06 00:09:41  <inimino> yeah, I remember looking at 3.8 last time
2009 Jul 06 00:09:59  <aamar> http://pastie.org/535156
2009 Jul 06 00:10:17  <inimino> for some of these I used some primitive ASCII-art for the diagrams
2009 Jul 06 00:10:49  <inimino> ah, looks like you had the same idea
2009 Jul 06 00:12:37  <aamar> partly why it took so long
2009 Jul 06 00:12:46  <aamar> my ascii-art skillz are rusty
2009 Jul 06 00:13:03  <inimino> yeah, later I did SVGs
2009 Jul 06 00:13:19  <inimino> or just prose instead of a diagram
2009 Jul 06 00:13:34  <inimino> alright these answers look similar
2009 Jul 06 00:13:44  <offby1> | | | | / _ \\ \ /\ / /
2009 Jul 06 00:13:47  <offby1> | |_| || (_) |\ V  V /
2009 Jul 06 00:13:49  <offby1> \__, | \___/  \_/\_/
2009 Jul 06 00:13:53  <offby1> |___/
2009 Jul 06 00:13:59  -*- offby1 is 14 years old
2009 Jul 06 00:14:00  -*- offby1 nods gravely
2009 Jul 06 00:14:04  <inimino> yow
2009 Jul 06 00:14:06  <inimino> heh
2009 Jul 06 00:15:46  <aamar> ok
2009 Jul 06 00:16:48  <aamar> 3.10?
2009 Jul 06 00:16:51  <inimino> ok
2009 Jul 06 00:16:57  <aamar> http://pastie.org/535160
2009 Jul 06 00:17:01  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.10
2009 Jul 06 00:17:21  <inimino> ooh, nice
2009 Jul 06 00:17:47  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.10.svg
2009 Jul 06 00:18:03  <inimino> does that SVG work OK?
2009 Jul 06 00:19:21  <aamar> looks great
2009 Jul 06 00:19:32  <inimino> ok
2009 Jul 06 00:19:42  <inimino> looks like the answers are the same
2009 Jul 06 00:19:53  <aamar> yes
2009 Jul 06 00:19:55  <aamar> 3.11
2009 Jul 06 00:20:00  <inimino> ok
2009 Jul 06 00:20:19  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.11
2009 Jul 06 00:20:25  <aamar> http://pastie.org/535161
2009 Jul 06 00:20:35  <inimino> this one I just did an explanation in prose
2009 Jul 06 00:22:06  <inimino> your answer looks good
2009 Jul 06 00:23:28  <aamar> ok
2009 Jul 06 00:23:31  <inimino> I probably should go back and draw diagrams for some of these that I didn't
2009 Jul 06 00:23:41  <aamar> I agree with your description as well.
2009 Jul 06 00:23:43  <inimino> it probably helps thinking about it
2009 Jul 06 00:23:49  <inimino> alright 3.12?
2009 Jul 06 00:24:03  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.12
2009 Jul 06 00:25:05  <aamar> http://pastie.org/535164
2009 Jul 06 00:25:42  <aamar> agree
2009 Jul 06 00:26:50  <inimino> looks good
2009 Jul 06 00:26:51  <aamar> 3.13
2009 Jul 06 00:26:53  <inimino> ok
2009 Jul 06 00:26:55  <aamar> http://github.com/aalearn/aalearn-sicp/blob/24252ead0abd7907632852b7d2f6e4dda02a762d/ch3-outline.scm#L296
2009 Jul 06 00:27:15  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.13.svg
2009 Jul 06 00:27:23  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.13
2009 Jul 06 00:27:54  <aamar> same
2009 Jul 06 00:28:06  <inimino> same
2009 Jul 06 00:28:13  <inimino> 3.14
2009 Jul 06 00:28:48  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.14.svg
2009 Jul 06 00:28:56  <inimino> erm, this seems to have a big black box in it
2009 Jul 06 00:29:05  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.14
2009 Jul 06 00:29:22  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.14.png
2009 Jul 06 00:29:27  <inimino> the PNG seems OK
2009 Jul 06 00:29:55  <inimino> (maybe the black box is just a Firefox rendering glitch, I'm pretty sure I didn't put it there in Inkscape)
2009 Jul 06 00:30:21  <aamar> no black box in safari
2009 Jul 06 00:30:41  <inimino> ok
2009 Jul 06 00:30:43  <aamar> or in firefox for me
2009 Jul 06 00:30:56  <inimino> well it's a trunk build
2009 Jul 06 00:31:03  <inimino> probably just some random bug
2009 Jul 06 00:31:08  <aamar> http://github.com/aalearn/aalearn-sicp/blob/24252ead0abd7907632852b7d2f6e4dda02a762d/ch3-outline.scm#L303-316
2009 Jul 06 00:31:56  <aamar> same answer, essentially
2009 Jul 06 00:32:47  <inimino> yes
2009 Jul 06 00:32:55  <inimino> alright 3.15
2009 Jul 06 00:33:08  <aamar> http://github.com/aalearn/aalearn-sicp/blob/24252ead0abd7907632852b7d2f6e4dda02a762d/ch3-outline.scm#L317-330
2009 Jul 06 00:33:18  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.15
2009 Jul 06 00:33:24  <aamar> I'll keep pasting the links, but you can also just scroll down in the github window obviously.
2009 Jul 06 00:33:24  <inimino> I didn't do diagrams for this one either
2009 Jul 06 00:33:35  <inimino> yeah
2009 Jul 06 00:34:34  <inimino> looks good
2009 Jul 06 00:34:45  <aamar> ok, explanation agrrees
2009 Jul 06 00:35:12  <aamar> 3.16 took me longer than it should have
2009 Jul 06 00:35:14  <aamar> http://github.com/aalearn/aalearn-sicp/blob/24252ead0abd7907632852b7d2f6e4dda02a762d/ch3-outline.scm#L332-378
2009 Jul 06 00:35:20  <inimino> it took me awhile too
2009 Jul 06 00:35:34  <inimino> for some reason I had myself convinced that 7 was impossible until I saw how to do it
2009 Jul 06 00:35:39  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.16.svg
2009 Jul 06 00:37:31  <aamar> I drew my last diagram incorrectly
2009 Jul 06 00:38:06  <aamar> Otherwise we have equivalent answers.
2009 Jul 06 00:38:48  <inimino> the inf one?
2009 Jul 06 00:38:53  <inimino> what's wrong with it?
2009 Jul 06 00:39:26  <aamar> I have a "null" for the last item there.
2009 Jul 06 00:39:47  <inimino> oh, I see
2009 Jul 06 00:39:47  <aamar> But you don't
2009 Jul 06 00:40:03  <inimino> well it could come from the car of the last pair
2009 Jul 06 00:40:14  <aamar> Oh, I see -- mine works as well
2009 Jul 06 00:40:28  <inimino> yeah, I think it's ok
2009 Jul 06 00:41:13  <aamar> okay, 3.17 then?
2009 Jul 06 00:41:17  <inimino> ok, sure
2009 Jul 06 00:41:23  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.17
2009 Jul 06 00:41:56  <aamar> found this one interesting
2009 Jul 06 00:41:58  <aamar> http://github.com/aalearn/aalearn-sicp/blob/24252ead0abd7907632852b7d2f6e4dda02a762d/ch3-outline.scm#L380-398
2009 Jul 06 00:43:27  <aamar> ok, I think I can construct a situation where yours wouldn't be accurate.
2009 Jul 06 00:43:52  <inimino> ok
2009 Jul 06 00:44:08  <inimino> I'm still reading yours and trying to see why it's different
2009 Jul 06 00:44:10  <aamar> (define x (cons 'a 'b))
2009 Jul 06 00:44:26  <aamar> (define y (cons x x))
2009 Jul 06 00:44:31  <aamar> (count-pairs y)
2009 Jul 06 00:44:45  <aamar> it should return 2
2009 Jul 06 00:45:23  <inimino> oh...
2009 Jul 06 00:45:27  <inimino> right
2009 Jul 06 00:45:47  <inimino> hm...
2009 Jul 06 00:45:49  <inimino> good point
2009 Jul 06 00:46:28  <aamar> I think yours also has an extra close paren after the 1
2009 Jul 06 00:46:39  <inimino> I don't deal with any overlap between the car and cdr, only with direct ancestors
2009 Jul 06 00:47:03  <inimino> oh yeah, that seems to be true also
2009 Jul 06 00:47:39  <aamar> also in order to use my particular test example, need to check pair?
2009 Jul 06 00:48:10  <inimino> hm I wonder if there's an elegant way around this without using mutation
2009 Jul 06 00:48:39  <inimino> I just need to test the car first and then capture the 'seen' result to use in the recursion into the cdr
2009 Jul 06 00:48:40  <aamar> I bet there is.
2009 Jul 06 00:49:40  <inimino> hm, well that was a major failure on my part to see that that wouldn't work
2009 Jul 06 00:50:01  <aamar> interesting -- not sure how to handle this without mutation
2009 Jul 06 00:50:44  <aamar> if you go depth first down one path, you have to return the items found and the unique objects found
2009 Jul 06 00:50:45  <inimino> I can perhaps make count return a pair
2009 Jul 06 00:50:54  <aamar> right ok
2009 Jul 06 00:51:40  <aamar> ok
2009 Jul 06 00:52:22  <inimino> I think that should work
2009 Jul 06 00:52:29  <inimino> I'll try writing it later
2009 Jul 06 00:52:50  <aamar> ok
2009 Jul 06 00:52:52  <aamar> next one?
2009 Jul 06 00:52:55  <inimino> seems like it will be longer than what I had...
2009 Jul 06 00:52:56  <inimino> sure
2009 Jul 06 00:53:11  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.18
2009 Jul 06 00:53:20  <aamar> http://github.com/aalearn/aalearn-sicp/blob/24252ead0abd7907632852b7d2f6e4dda02a762d/ch3-outline.scm#L400-418
2009 Jul 06 00:55:16  <aamar> hm... yours is much, much simpler
2009 Jul 06 00:55:28  <aamar> conceptually similar except I used the mutable list
2009 Jul 06 00:55:38  <inimino> yeah, they seem to have the same outline
2009 Jul 06 00:55:48  <inimino> and I think both work
2009 Jul 06 00:55:49  <aamar> in this case, there's no reason for me to, since the data structure is limited to lists only.
2009 Jul 06 00:56:46  <inimino> agreed
2009 Jul 06 00:56:56  <aamar> okay
2009 Jul 06 00:57:08  <inimino> alright, next one?
2009 Jul 06 00:57:39  <aamar> ok 3.19
2009 Jul 06 00:57:49  <inimino> ok
2009 Jul 06 00:57:50  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.19
2009 Jul 06 00:58:01  <aamar> http://github.com/aalearn/aalearn-sicp/blob/24252ead0abd7907632852b7d2f6e4dda02a762d/ch3-outline.scm#L420-431
2009 Jul 06 00:58:03  <inimino> 3.19 is as far as I got
2009 Jul 06 00:59:18  <inimino> I was trying to prove my solution correct, or even explain it, but it seems hard
2009 Jul 06 01:00:37  <inimino> now I'm trying to understand yours
2009 Jul 06 01:01:16  <aamar> I have no real explanation
2009 Jul 06 01:01:36  <aamar> We're both comparing two elements -- x & y in mine.
2009 Jul 06 01:01:42  <aamar> I am advancing x by 1 and y by 2
2009 Jul 06 01:02:01  <aamar> Let me see if I can prove that will work, regardless of the size of the loop
2009 Jul 06 01:02:29  <inimino> I see
2009 Jul 06 01:02:40  <inimino> you are advancing by 1 and 2 each time
2009 Jul 06 01:02:41  <inimino> yeah
2009 Jul 06 01:03:34  <inimino> I think intuitively that should work
2009 Jul 06 01:05:34  <aamar> it should be provable...
2009 Jul 06 01:06:21  <aamar> with a cycle length of c, if X starts out at point p0 and Y starts out at p1, with 0 <= p0 and p1 < c...
2009 Jul 06 01:07:07  <aamar> is there some n where p0 + n % c == p1 + 2n % c ?
2009 Jul 06 01:08:10  <inimino> hm, right
2009 Jul 06 01:08:52  <inimino> I'm not sure how to prove that, but I think mine relies on something similar
2009 Jul 06 01:09:03  <aamar> would have to think about it... bet it can be solved
2009 Jul 06 01:09:19  <inimino> yeah, I will give it some thought
2009 Jul 06 01:09:37  <inimino> I liked this one
2009 Jul 06 01:09:54  <aamar> I tried it out with cycles of 4, 5, and 6 and it empirically works
2009 Jul 06 01:10:07  <aamar> proof!
2009 Jul 06 01:10:11  <inimino> hehe :-)
2009 Jul 06 01:10:35  <inimino> we tested for n up to 7, so it's almost certain we are right!
2009 Jul 06 01:11:06  <inimino> yeah I actually didn't test mine
2009 Jul 06 01:11:16  <inimino> but I like that they tell you there is a clever idea but not what it is
2009 Jul 06 01:11:48  <inimino> I took a break after reading that one and ruminated a bit
2009 Jul 06 01:12:17  <inimino> it's interesting that we came up with different solutions, too
2009 Jul 06 01:12:57  <inimino> well, that's as far as I got
2009 Jul 06 01:13:05  <aamar> so in yours...
2009 Jul 06 01:13:23  <aamar> if n = m, will ancestor = x because you're checking the same element?
2009 Jul 06 01:13:46  -*- inimino looks
2009 Jul 06 01:14:05  <aamar> oh, I see
2009 Jul 06 01:14:15  <aamar> you actually use the prior ancestor in that case
2009 Jul 06 01:14:17  <aamar> okay,
2009 Jul 06 01:14:19  <inimino> yeah
2009 Jul 06 01:14:35  <inimino> basically ancestor ascends by powers of two
2009 Jul 06 01:15:10  <aamar> Right, and you check every element in between as well
2009 Jul 06 01:15:14  <aamar> Okay
2009 Jul 06 01:15:24  <inimino> and n is just to keep track of where the next jump will happen
2009 Jul 06 01:15:45  <aamar> I found 3.22,23 to be long
2009 Jul 06 01:16:19  <inimino> yeah there seems to be a lot there on github
2009 Jul 06 01:16:48  <inimino> do you think we should try to get into 3.4 next time or just finish up 3.3?
2009 Jul 06 01:17:24  <aamar> How about just finishing up 3.3 ?
2009 Jul 06 01:17:35  <aamar> the upcoming sections look fairly long as well
2009 Jul 06 01:17:43  <inimino> alright, works for me
2009 Jul 06 01:18:33  <inimino> that'd be the 19th then
2009 Jul 06 01:20:39  <inimino> alright, see you in two weeks, aamar
2009 Jul 06 01:20:56  <aamar> right see you
2009 Jul 06 01:21:10  <aamar> good luck on 3box, inimino -- look forward to following the project!
2009 Jul 06 01:21:19  <inimino> thanks!