Author |
Message |
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 10 Jan 2009 11:24:19 pm Post subject: |
|
|
You have a list at least three elements in Ans, not necessarily containing integers. The goal is to write a routine of the smallest size that will say whether it represents a geometric progression, by printing either a zero or one to the home screen.
Again, program size is measured objectively as the number of bytes given next to the program on the memory screen, minus the number of characters in the program's name. I haven't asked for a specific number because I want to see what you guys can come up with, but I will say that any routine that beats mine will be stuck on my website for download. (See the bottom link in my signature.)
Last edited by Guest on 11 Jul 2010 06:51:06 pm; edited 1 time in total |
|
Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007 Posts: 138
|
Posted: 11 Jan 2009 12:44:51 am Post subject: |
|
|
I have the program in 23 bytes. However, I need to add 3 or 4 bytes to deal with small floating-point errors for sequences with a ratio of like 1/7 or something. |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 11 Jan 2009 12:51:37 am Post subject: |
|
|
23 bytes..? :|
Example input: {‾2/3,4/9,‾8/27,19/81,‾32/243}
(Don't get me wrong – I'm half expecting you to surprise me with something here.)
Last edited by Guest on 11 Jul 2010 06:51:23 pm; edited 1 time in total |
|
Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007 Posts: 138
|
Posted: 11 Jan 2009 01:06:54 am Post subject: |
|
|
Yes, when you put in {-2/3,4/9,-8/27,16/81,-32/243}, it returns a 1.
However, if you put in seq(AR^X,X,0,N) with A=.1, R=1/3, and N=3, the program returns a 0. I need to add 3 or 4 bytes to take care of that.
Heheh, okay. Here we go.
[whiteout]:not(max(∆List(∆List(Ans)-1∆List(cumSum(Ans[/whiteout]
Here's with 3 bytes added to take care of floating point errors.
[whiteout]:not(iPart(E9max(∆List(∆List(Ans)-1∆List(cumSum(Ans[/whiteout]
However, the above version increases the tolerance enough to mistake the list {12,36.00000001,108.00000002,324.00000003} as a geometric sequence. This can be fixed by [whiteout]changing the 9 to a 14, or 20[/whiteout], adding a byte.
Last edited by Guest on 12 Jul 2010 01:22:01 am; edited 1 time in total |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 11 Jan 2009 01:15:01 am Post subject: |
|
|
Ed H wrote: Would you like me to post it now? Use [color=#222][[/color]spoiler] tags, and I'll take a look.
I'd say that the 9 was intentional, but you wouldn't believe me, and you'd also be right.
Last edited by Guest on 11 Jan 2009 01:15:13 am; edited 1 time in total |
|
Back to top |
|
|
bfr
Member
Joined: 13 Feb 2006 Posts: 108
|
Posted: 11 Jan 2009 01:30:54 am Post subject: |
|
|
No, don't post it yet! :P
I just saw this topic a short while ago and I think I just came up with a pretty good method. |
|
Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007 Posts: 138
|
Posted: 11 Jan 2009 01:32:35 am Post subject: |
|
|
Oops, too late! But don't worry, it's in spoiler tags and it's three posts up, so just don't Control + A and scroll up! :D
Edit: The fact that you didn't notice my solution 3 posts up is probably an indication that I need to stop putting my responses in edits of previous posts. Heh.
Quote: [whiteout]:not(max(∆List(∆List(Ans)-1∆List(cumSum(Ans[/whiteout]
Here's with 3 bytes added to take care of floating point errors.
[whiteout]:not(iPart(E9max(∆List(∆List(Ans)-1∆List(cumSum(Ans[/whiteout]
However, the above version increases the tolerance enough to mistake the list {12,36.00000001,108.00000002,324.00000003} as a geometric sequence. This can be fixed by [whiteout]changing the 9 to a 14, or 20[/whiteout], adding a byte.
Last edited by Guest on 12 Jul 2010 01:21:46 am; edited 1 time in total |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 11 Jan 2009 01:35:28 am Post subject: |
|
|
Hmm (looking at the Ed H's edit above)...
You'd need an [whiteout]abs([/whiteout] because of [whiteout]{‾1,‾2,4,8}[/whiteout], but then [whiteout]max(abs([/whiteout] can be replaced by [whiteout]stdDev([/whiteout] or [whiteout]variance([/whiteout], and you can also wedge a [whiteout]round([/whiteout] in between the two [whiteout][font="times new roman"]∆List('s[/whiteout].
[EDIT]
On second thought, those replacements each cost two bytes, and crash with several otherwise normal inputs.
Last edited by Guest on 12 Jul 2010 01:21:16 am; edited 1 time in total |
|
Back to top |
|
|
bfr
Member
Joined: 13 Feb 2006 Posts: 108
|
Posted: 11 Jan 2009 01:42:23 am Post subject: |
|
|
Pretty much the best I could come up with before I got the temptation to look at yours :ninja: was something like (this doesn't work with lists with negative elements or lists that decrease though, by the way):
Quote: not(max(Ans-augment(dList(Ans),{max(Ans I just knew the answer had to do something with dList, since I noticed that the dList of the progression would be same as the progression, except missing the last element. [s]I also noticed that if you reversed the list and multiplied it with the original list, all of the elements should be the same, but I couldn't figure out how to implement this in a small enough way.[/s]
And, by the way, I'm not using the spoiler tags in this instance so it is more obvious that this is an entire hidden block of text.
EDIT: [s]Weregoose, {‾1,‾2,4,8} is a geometric series?[/s] Nevermind
Last edited by Guest on 17 Jan 2009 02:48:40 pm; edited 1 time in total |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 11 Jan 2009 01:45:57 am Post subject: |
|
|
Cool, I was expecting some code like that.
I'll post my program later, as this challenge hasn't been open long enough yet.
Last edited by Guest on 11 Jan 2009 01:47:31 am; edited 1 time in total |
|
Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007 Posts: 138
|
Posted: 11 Jan 2009 01:49:08 am Post subject: |
|
|
Hmm, the program works fine on {-1,-2,4,8}
The mathematical justification of this program is that [whiteout]The deltaList of a geometric sequence should be a geometric sequence with the same ratio. Therefore, the deltaList should a constant multiple of the original sequence sans the first element.
arn - arn-1 = (r - 1)arn-1[/whiteout]
Using [whiteout]variance([/whiteout] instead of [whiteout]max(∆List([/whiteout] takes the size down to 22:
[whiteout]:not(variance(∆List(Ans)-1∆List(cumSum(Ans[/whiteout]
How exactly does the round( command work? I'm trying to use it but it keeps giving back what I put in. All I want is for anything less than 10^-24 to be recognized as 0.
Last edited by Guest on 12 Jul 2010 01:20:51 am; edited 1 time in total |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 11 Jan 2009 02:07:10 am Post subject: |
|
|
Eep, another typo. The first generation code that you posted showed {‾1,‾2,4,‾8} (with the 8 negative) to be geometric. Your latest routine fixes this.
round( without a second argument only truncates digits past the tenth from the mantissa, which would explain why numbers close to zero aren't being zeroed out.
Hint: Try putting the round( someplace else.
Last edited by Guest on 12 Jul 2010 12:23:22 am; edited 1 time in total |
|
Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007 Posts: 138
|
Posted: 11 Jan 2009 02:24:10 am Post subject: |
|
|
Ah, I see. I should have remembered to use [whiteout]variance or stdDev[/whiteout] to find out whether [whiteout]all the elements were the same[/whiteout]. Silly of me to forget. Thanks for pointing that out.
So here is a 25 byte version with tolerance for stupid fractional ratios.
Quote: [whiteout]:not(iPart(E9stdDev(∆List(Ans)-1∆List(cumSum(Ans[/whiteout]
You can adjust the tolerance by changing [whiteout]the stdDev to a variance, and changing E9 to anything between E16 to E25[/whiteout].
Of note: for some reason, when the ratio is Pi or e, the program without the Floating-Point correction performs perfectly well. Only when the ratio is a stupid fraction does the program need tolerance.
Edit: Or, thanks to that hint from Weregoose, 23 bytes with tolerance:
[whiteout]:not(variance(round(∆List(Ans)-1∆List(cumSum(Ans[/whiteout]
Last edited by Guest on 12 Jul 2010 01:20:00 am; edited 1 time in total |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 11 Jan 2009 02:30:33 am Post subject: |
|
|
Solid as a rock... I don't think we could possibly rearrange it any further without changing the algorithm.
[EDIT]
Is there any reason not to turn the inverse into a solidus at this point? It might fix some tolerance problems. *checks*
[EDIT×2]
Not sure why, but it worked. {12,36.00000001,108.00000002,324.00000003} is marked as not geometric.
Last edited by Guest on 11 Jul 2010 06:47:40 pm; edited 1 time in total |
|
Back to top |
|
|
bfr
Member
Joined: 13 Feb 2006 Posts: 108
|
Posted: 11 Jan 2009 02:05:39 pm Post subject: |
|
|
Or how about [whiteout]not(variance(∆List(Ans)/∆List(cumSum(Ans[/whiteout], which is 22 bytes (I haven't really looked closely at it or tested it much yet, because I have to get back to my homework, but I know it at least detects {-2/3,4/9,-8/27,16/81,-32/243} as geometric and {1,2,16) as not geometric)
Last edited by Guest on 12 Jul 2010 01:19:43 am; edited 1 time in total |
|
Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007 Posts: 138
|
Posted: 11 Jan 2009 03:24:35 pm Post subject: |
|
|
bfr wrote: Or how about [whiteout]not(variance(∆List(Ans)/∆List(cumSum(Ans[/whiteout], which is 22 bytes (I haven't really looked closely at it or tested it much yet, because I have to get back to my homework, but I know it at least detects {-2/3,4/9,-8/27,16/81,-32/243} as geometric and {1,2,16) as not geometric)
Yes, that's what Weregoose suggested in the previous post - changing the -1 to a division symbol. (I actually had 22 bytes, but miscounted as 23.)
The near-geometric sequence {12,36.00000001,108.00000002,324.00000003} actually got fixed when [whiteout]max(∆List([/whiteout] got changed to [whiteout]variance([/whiteout]. But I just did some more testing now, and with division, the round( catches the floating point errors more often, and fixes it. In general, division is more solid.
Last edited by Guest on 12 Jul 2010 01:19:16 am; edited 1 time in total |
|
Back to top |
|
|
bfr
Member
Joined: 13 Feb 2006 Posts: 108
|
Posted: 11 Jan 2009 03:38:06 pm Post subject: |
|
|
Er, sorry, I didn't really read your solution nor Weregoose's post carefully. I actually just thought of this now and that it was something new.... That's the second time in this thread that I didn't read the other posts carefully. *hides*
EDIT: Actually, taking another shot at this after looking at DarkerLine's method below, something like... [whiteout]
∆List(ln(Ans
not(variance(real(Ansconj(Ans[/whiteout] which is 23 bytes. It's [whiteout]a shame that I need the real( there, even though I think the result would be real anyway[/whiteout].
Last edited by Guest on 12 Jul 2010 01:18:57 am; edited 1 time in total |
|
Back to top |
|
|
DarkerLine ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328
|
Posted: 11 Jan 2009 06:46:57 pm Post subject: |
|
|
I'm looking at something based [whiteout]e^(∆List(ln(Ans[/whiteout], which should be a constant list for geometric series, and nonconstant otherwise -- check this with not(max(∆List or something. It works perfectly for positive geometric series; when some terms are negative, the complex numbers involved introduce round-off error. There's probably a way to fix this using round(... how about [whiteout]min(1=1+abs(∆List(e^(∆List(ln(Ans[/whiteout]?
Last edited by Guest on 12 Jul 2010 01:18:41 am; edited 1 time in total |
|
Back to top |
|
|
calc84maniac
Elite
Joined: 22 Jan 2007 Posts: 770
|
Posted: 11 Jan 2009 07:39:26 pm Post subject: |
|
|
Yeah, I did the [whiteout]log[/whiteout] approach too. Works perfectly for positive numbers only so far.
Last edited by Guest on 12 Jul 2010 01:18:16 am; edited 1 time in total |
|
Back to top |
|
|
DarkerLine ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328
|
Posted: 11 Jan 2009 09:28:25 pm Post subject: |
|
|
You'll need to be in complex number mode to use logs, since taking logs of negative numbers results in a complex answer. Another problem with these is that there's multiple branches for an inverse to exponentiation, so if you do things the naive way you might end up with certain elements differing by 2πi. |
|
Back to top |
|
|
|