Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's TI-BASIC subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. TI-Basic Brain Teasers => TI-BASIC
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. Razz

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
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
    » Goto page 1, 2  Next
» View previous topic :: View next topic  
Page 1 of 2 » All times are GMT - 5 Hours

 

Advertisement