Page 5 of 7 « First<34567>
Topic Options
#69835 - 2002-09-17 03:28 PM Re: KiXtart Golf V: Game24
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
Well it looks like it's back to the drawing board. [Wink]
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#69836 - 2002-09-17 03:37 PM Re: KiXtart Golf V: Game24
Fernando Madruga Offline
Starting to like KiXtart

Registered: 2002-08-21
Posts: 149
Loc: Coimbra.Portugal.Europe.Earth....
I think we can rule out one of the 7 situations: a(bcd).

{EDIT} BOY! Was I wrong on this one!!! Read below... {/EDIT}

Why? Follow me...
We can have one of 4 operators between 'a' and the rest of the expression.

code:
a+(bcd) -> (bcd)+a  : does not matter what ops are inside as
+ is low precedence

a-(bcd) -> nothing! : What kind of expression would you need
inside parens to get 24 by subtracting
to 0..9?? Yes, I know that 0-(-something)
will be positive, but we can't have another
negative number inside the parens!!!
{edit} Actually, we can, but it does not create a solution! {/edit}
{edit} And it can be rewritten as not to need the parens! {/edit}

a/(bcd) -> nothing! : Again, what kind of number would we need
inside parens to get 24? A very small number!
In order to be so, we'd need something like
a/(b/c/d) because a/(b+c/d) or a/(b/c+d) would
not give a number below 1 unless the added item
was 0 and even then it would not be "small enough"
to get 24... (hope you're still following me!)
If we did not use a / inside the parens, then
the number would not be between 0 and 1 and so,
dividing a number from 1 to 9 by it would not
yield the needed result! Finally, a/(b/c/d) can
be simplified as a/b/c/d !!!

a*(bcd) -> (bcd)*a : We will arrive at this test case sooner or later!
So, no need to handle it in here.

Please check my assumptions, but I do believe that a(bcd) can be safely
left out of the game as we're not trying to get ALL solutions but just
ONE!

The same may hold true for more cases, but I have to go now. I'll check
the others later...

[ 18. September 2002, 02:06: Message edited by: Fernando Madruga ]
_________________________
Later,   [b]Mad[/b]ruga

Top
#69837 - 2002-09-17 03:53 PM Re: KiXtart Golf V: Game24
Jack Lothian Offline
MM club member
*****

Registered: 1999-10-22
Posts: 1169
Loc: Ottawa,Ontario, Canada
Well Richard, I think I must conceed, you gone to far. I think I could bring my score down but 400 is out of reach with the approach I chose. I am looking forward to seeing your solution.
_________________________
Jack

Top
#69838 - 2002-09-17 04:00 PM Re: KiXtart Golf V: Game24
Jack Lothian Offline
MM club member
*****

Registered: 1999-10-22
Posts: 1169
Loc: Ottawa,Ontario, Canada
Madruga

What about 8/(1*1/4)? Of course you could restructure this & get a large number of alternatives but in general duplicates always exist & eliminating them is more challanging than solving the problem.

[ 17. September 2002, 16:04: Message edited by: Jack Lothian ]
_________________________
Jack

Top
#69839 - 2002-09-17 04:03 PM Re: KiXtart Golf V: Game24
Fernando Madruga Offline
Starting to like KiXtart

Registered: 2002-08-21
Posts: 149
Loc: Coimbra.Portugal.Europe.Earth....
quote:

Madruga

What about 8/(1*1/4)?

=> 8*4+1-1 is another valid solution to be found without using parens...
_________________________
Later,   [b]Mad[/b]ruga

Top
#69840 - 2002-09-17 04:04 PM Re: KiXtart Golf V: Game24
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
Jack,
Keep going. It's surprising what you can strip out after staring at the code for 10 minutes.

And you never know, I may have violated some rule which will invalidate the code.

But just to keep you on your toes...

KixGolf v3.0.3 score = 404, running under KiXtart v4.11 RC 1

Top
#69841 - 2002-09-17 05:07 PM Re: KiXtart Golf V: Game24
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11164
Loc: Boston, MA, USA
Comment to the use of parenthesis, so far I've only seen the use of exactly three operators and either zero, one, or two sets of parentheses. Examples:
0 = a+b+c+d
1 = (a+b/c)*d
2 = (a+b)*(c+d)

Also, I do not think that there is a need for nested parentheses since I have not been able to find a formula that require a nested parenthesis and which cannot be rewritten without the need of a nest parenthesis.

For example ((a/b)*c)+d = (a/b*c)+d.
_________________________
There are two types of vessels, submarines and targets.

Top
#69842 - 2002-09-17 09:59 PM Re: KiXtart Golf V: Game24
MightyR1 Offline
MM club member
*****

Registered: 1999-09-09
Posts: 1264
Loc: The Netherlands
TomTieDom, [Confused]

found something else what surprised me:

code:
$a='cdbl(8)/(cdbl(3)-cdbl(8)/cdbl(3))'
$rc=Execute("$$b=$a")
? 'Result $$b = '$b
? 'Result 24=$$b = '+(24=$b)
? 'Result $$b=24 = '+($b=24)
? 'Result type = '+VarTypeName($b)

comes up with
code:
Result $b    = 24
Result 24=$b = 1
Result $b=24 = 0
Result type = Double

[Confused] [Confused]

Does anyone have an explaination for this behaviour???
_________________________
Greetz,
Patrick Rutten

- We'll either find a way or make one...
- Knowledge is power; knowing how to find it is more powerful...
- Problems don't exist; they are challenges...

Top
#69843 - 2002-09-17 10:02 PM Re: KiXtart Golf V: Game24
Jack Lothian Offline
MM club member
*****

Registered: 1999-10-22
Posts: 1169
Loc: Ottawa,Ontario, Canada
God richard,

I don't know how you got to 400. After 2 more hours work I am at 721.
_________________________
Jack

Top
#69844 - 2002-09-17 10:06 PM Re: KiXtart Golf V: Game24
Jack Lothian Offline
MM club member
*****

Registered: 1999-10-22
Posts: 1169
Loc: Ottawa,Ontario, Canada
Kixtart sets variable type from left to right I believe. Thus in the first test you are doing an integer test & in the second a floating point check. As lonkero has shown floating point has a leak. Thus the comparison fails.

Thank you Patrick,

Your example did it for me. The execute statement must literally see the cbdl function surrounding all 4 numbers for it to work consistently. I got rid of my fudge factor & I am down to a score of 702.

[ 17. September 2002, 22:50: Message edited by: Jack Lothian ]
_________________________
Jack

Top
#69845 - 2002-09-18 01:09 AM Re: KiXtart Golf V: Game24
Fernando Madruga Offline
Starting to like KiXtart

Registered: 2002-08-21
Posts: 149
Loc: Coimbra.Portugal.Europe.Earth....
I've been doing some perl experiments... Did you know that there are 465 unique 4 number combos that will evaluate to 24 according to the rules? (0038,0308,0380,... and all it's permutations all count as one).

Also, of all these possible 465 solutions:
code:
  13 (unlucky number!) depend on having two sets of (), that is (ab)(cd)
131 depend on having at least one '+'
174 depend on having at least one '-'
306 depend on having at least one '*'
36 depend on having at least one '/'

By now, it's clear to you guys: I was trying to simplify the algorithm by not including something!!!

Just thought to share my findings with you guys. Haven't coded a single KiXtart line yet... [Smile]

[ 18. September 2002, 01:09: Message edited by: Fernando Madruga ]
_________________________
Later,   [b]Mad[/b]ruga

Top
#69846 - 2002-09-18 01:27 AM Re: KiXtart Golf V: Game24
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
fernando, as I got my papers... 3 of them filled up of plans how to do it, I decided to give up.

and surely did the right thing. now I can spend my nights doing something usefull [Big Grin]
_________________________
!

download KiXnet

Top
#69847 - 2002-09-18 02:00 AM Re: KiXtart Golf V: Game24
Fernando Madruga Offline
Starting to like KiXtart

Registered: 2002-08-21
Posts: 149
Loc: Coimbra.Portugal.Europe.Earth....
You're not on this one? That's bad...

It's fun... It's my 1st one from "scratch": all I did in the last one was
crop some bytes out of someone else's code...
Maybe I'll do some coding this time... [Smile]

I did however continue my findings:
code:
   0 need (ab)cd
0 need a(bc)d
0 need ab(cd)
------------------
1 need (abc)d
------------------
3 need a(bcd)
13 need (ab)(cd)
------------------
131 need at least one '+'
174 need at least one '-'
306 need at least one '*'
36 need at least one '/'

So, and for the purpose of this game that is to find ONE
(repeat: ONE) solution, we can eliminate these constructs:
(ab)cd, a(bc)d, ab(cd).

The (abc)d construct is only used for these numbers
(and respective permutations): 1277 == (7*7-1)/2.

The a(bcd) construct is needed for these 3 sets:
1346 == 6/(1-3/4); 1456 == 6/(5/4-1); 1668 == 6/(1-6/8)

As for the (ab)(cd), 13 is too much to test for...
Even 3 may prove to be too much! [Smile]

Hope this helps you guys, even though I may be shooting myself in the foot,
but hey! this is just a friendly competition...

Gonna do some work, then sleep over it. I'll probably only get back to this
in some 48 hours or so to start (and finish) my coding for this one, so
don't be surprised if you don't read from me for a couple of days...

[ 18. September 2002, 17:31: Message edited by: Fernando Madruga ]
_________________________
Later,   [b]Mad[/b]ruga

Top
#69848 - 2002-09-18 06:29 PM Re: KiXtart Golf V: Game24
Jack Lothian Offline
MM club member
*****

Registered: 1999-10-22
Posts: 1169
Loc: Ottawa,Ontario, Canada
A problem …

After thinking on the issues discussed above, I believe several of the points brought up by Jens are important for this project. This basic problem is a topic that was talked about a lot in the 50s through the 70s. During this period most mainframes were IBM which had a ridiculously low word size of 4 bytes. This limited the size & accuracy of all numbers. If I remember, it limited integers to 9 digits & floating point to an accuracy of 7 digits. After this point you got an integer overflow or truncation in floating point.

The serious problems occur when you divide by a prime number & the result generates a repeating decimal pattern. Floating point math on a computer must truncate the pattern & thus internally the result is inaccurate.

An example: (3.0/7.0)*(7.0/3.0) will not generate 1 in most computer languages. Instead it will generate a decimal number very close to 1. Converting the resultant to integer will not produce exact results with any type of “int” function since the value in general can be above 1 or below 1 & with higher level primes the distance from 1 can get larger. Rounding doesn’t help because it can’t tell the difference between 0.5 or 0.99999 or 1.00001 or 1.49999.

Another factor is the mixing of operations types in floating point math. For multiplication or division, a scientific notation representation of the numbers gives the greatest accuracy but you can not add two scientific numbers so for addition floating point arithmetic uses pseudo integer formalism. This implies resultant decimal accuracy of an addition/subtraction is equal to the lowest accuracy of the 2 numbers.

Thus we get things like: 20*(1.0/3.0) + (1.0/3.0) = 20*(0.333333)+(0.3333333)= 6.9999933

Note as you increase the size of the leading multiplier the inaccuracy increases.

The 2 above factors tend to produce floating point resultants that have small pseudo random numbers added to them. This is why exact compares in floating point tend not to work. The problem worsens as the number of potential primes increases and the size of the numbers increase. If we had been asked to do another common variant of the game that uses a deck of cards then we might have all noticed the problem sooner because it uses a number range of 1 to 13 which includes 2 extra & larger primes.

The solution …

I have come to the conclusion that Jens point about not using decimal math is an absolute requirement for the routine to work consistently. All calculations must be done in integer math & this means all divisions must be re-structured as Jens suggested above so that division is never done unless the final result will be an integer.

A note to Madruga …

If you used floating point math in your perl script you can not be sure you found all solutions correctly.
_________________________
Jack

Top
#69849 - 2002-09-19 12:58 AM Re: KiXtart Golf V: Game24
Fernando Madruga Offline
Starting to like KiXtart

Registered: 2002-08-21
Posts: 149
Loc: Coimbra.Portugal.Europe.Earth....
Well, I could rewrite it to use some kind of "infinite" precision math routines: it would probably take a few days instead of some minutes, but would not fail...

However, you have to look at floating point math in another way: is the PC's floating point accuracy enough to overcome potential "rounding" errors? I think that, in this case, where we have only 4 numbers in the range 0..9 and 3 (THREE!) operations, any inacuracy that is introduced is certainly VERY close to 0, that is, below 0.000001 or most likely even lower than that.

Today's computers conforms to IEEE 8 byte floating point math: it's inexpensive (processing wise due to the builtin math coprocessor) and has "decent" accuracy (don't feel like digging some specs now!).

If you consider that, with only 3 operators, and something like 10+ decimal places of accurate calculation you will SURELY not have an error above the 8th decimal digit, I assume that testing for 24 within 1^-6 is most likely enough...

Also, I don't know how to prove this mathematically, but you would not get a number THAT close to 24 with only these 4 digits & 3 operators...

I'll do the following: I'll change my generator program to save ALL possible combinations regardless of whether they evaluate to near 24 or not, and I'll then see what is the number that comes closer to 24, without actually being 24 and that shouldn't be 24.

I'll post the results later...

[ 19. September 2002, 01:00: Message edited by: Fernando Madruga ]
_________________________
Later,   [b]Mad[/b]ruga

Top
#69850 - 2002-09-19 01:23 AM Re: KiXtart Golf V: Game24
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
Has everyone lost sight of what the purpose of this exercise is? Take a problem with a set of specific given criteria, mix in some KiXtart ingenuity, comradery, and FUN. Uncover some shortcuts, inconsistencies, workarounds, etc. Satisfy the given requirements not all possible requirements. After we play & learn a little, the code can then be written in a percise bulletproof fashion. We are still in the FUN stages. Don't scare away those that don't share is the enthusiasm for extremes.
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#69851 - 2002-09-19 01:44 AM Re: KiXtart Golf V: Game24
Fernando Madruga Offline
Starting to like KiXtart

Registered: 2002-08-21
Posts: 149
Loc: Coimbra.Portugal.Europe.Earth....
I second that Howard!

The only reason I wrote the perl program to compute all possible solutions, was because I figured that, being a small and easily computable set, I could perhaps simplify the algorithm! I did, as 3 types of parentheses constructs can be safely eliminated!

BTW: I'm now running the "updated" script, that will save all possible values, correct or not, but I'm doing this only for fun! I want to know if I'm right in my previous post...

Meanwhile, and this is not to blame Ruud, perl's floating point implementation is a LOT more robust: I ported the exact same script to KiXtart and (while taking loads more time to run! [Smile] ), it only found less than half the solutions! In fact, for some numbers, it wasn't even able to find ANY solution when the perl script DID find at least one! [Smile]

Again, KiXtart is certainly *not* the best tool for this "game" in case you're taking it a bit too serious, but it's a good tool for loads of other stuff!
_________________________
Later,   [b]Mad[/b]ruga

Top
#69852 - 2002-09-19 01:52 AM Re: KiXtart Golf V: Game24
Jack Lothian Offline
MM club member
*****

Registered: 1999-10-22
Posts: 1169
Loc: Ottawa,Ontario, Canada
howard,

Being a mathematician, I have a tendency to get over involved in anything that has to do with math. Thanks for the reminder.
_________________________
Jack

Top
#69853 - 2002-09-19 09:29 AM Re: KiXtart Golf V: Game24
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
I kinda like the high-brow tangents these things fly off into.

There is always the danger I might learn something new, and to a jaded techie that's one of the major bonuses of this board.

The code I have does *not* work with all possible combinations - it only finds 422 of Fernando's 465.

It's been crippled because of keeping the size down. In the processes I've also doubled the time that it takes to run, just to save 2 characters.

However, it does adhere to the rules and gives the correct results [Razz]

It's also given me a corker of a UDF that I'll publish once the first round is over. It is so cute I'm going to name my first-born after it.

Top
#69854 - 2002-09-19 09:33 AM Re: KiXtart Golf V: Game24
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
yeah...
this chit chat is nice reading especially when it's weekend.
allthough, I think we should do next golf on general so this mumble can't get off topic in anyway... [Wink]
_________________________
!

download KiXnet

Top
Page 5 of 7 « First<34567>


Moderator:  Glenn Barnas, NTDOC, Arend_, Jochen, Radimus, Allen, ShaneEP, Ruud van Velsen, Mart 
Hop to:
Shout Box

Who's Online
0 registered and 248 anonymous users online.
Newest Members
gespanntleuchten, DaveatAdvanced, Paulo_Alves, UsTaaa, xxJJxx
17864 Registered Users

Generated in 0.073 seconds in which 0.026 seconds were spent on a total of 12 queries. Zlib compression enabled.

Search the board with:
superb Board Search
or try with google:
Google
Web kixtart.org