CodeLegend wrote:

MartinBraendli2 wrote:

For the polynomial interpolation challenge:
I was looking for good algorithms, but all i can find are algorithms that take a list of x-values and their corresponding f(x)-values and produce an interpolation for a specific x-value (Newton, Heremite and others). Is there a good algorithm to tackle that challenge? I could do it by solving multiple linear equations, but I'm quite sure, there is a better algorithm out there.

I was taught to use matrix multiplication.

EDIT: (for everyone here)

Let's say you have 3 points: (0,1), (2,3), (5,4)
We want to find an equation of the form y=ax^2+bx+c which passes through them all. So we're looking to return the values of a, b, and c.
So we can form these equations, one for each point:
1=a*0^2+b*0+c
or 1=0a+0b+1c
3=a*2^2+b*2+c
or 3=4a+2b+c
4=a*5^2+b*5+c
or 4=25a+5b+c

With these equations, we can form this matrix relationship:

[ 0 0 1] [a] [1]
[ 4 2 1]*[b]=[3]
[25 5 1] [c] [4]

Then solve for [[a][b][c]]

[ 0 0 1]^-1[ 0 0 1] [a] [ 0 0 1]^-1[1]
[ 4 2 1] * [ 4 2 1]*[b]=[ 4 2 1] * [3]
[25 5 1]   [25 5 1] [c] [25 5 1]   [4]

[a] [ 0 0 1]^-1[1]
[b]=[ 4 2 1] * [3]
[c] [25 5 1]   [4]

[a] [ 1/10 -1/6  1/15] [1]
[b]=[-7/10  5/6 -2/15]*[3]
[c] [  1     0    0  ] [4]

[a] [-2/15]
[b]=[19/15]
[c] [  1  ]
a=-.13333333333
b=1.26666666666
c=1

So the program would output those three values. You can check them in the previous equations, and the math should check out.

So if you're going to use this method, you need a way to inverse and multiply matrices.

MartinBraendli2 wrote:

CodeLegend wrote:

-snip-

Yeah, I got that far, but i couldn't find a simple method for inversing matrices. I found a better method now. I won't tell how I'll do it atm, since I'm not yet sure that I'll beat Random-Man.

Random-Man wrote:

1. I only have 5 variables

Random-Man wrote:

2. My languages conditionals are dependent on the length of the program before it, so if I edit anything, I then must change all the conditionals to match it

[

]

|  Break loop
> Break loop if POP is bigger than 0 (boolean true = 1, false = -1)
< Break loop if  top of stack is not bigger than 0, only pop on break

(booleanValue)
?
     (ifTrueCode)
;

(booleanValue)
?
     (ifTrueCode)
.
     (elseCode)
;

(valuePreferableInteger)
!
     (ifInt1Code)
,
     (ifInt2Code)
,
     (ifInt3Code)
.
    (defaultCode)
;

Random-Man wrote:

I will add loops once this contest is over, considering I have many extra characters, for the fun of it… And though I don't have lists, I have two stacks and lots of stack manipulation commands, so that will be useful…

CodeLegend wrote:

Random-Man wrote:

I will add loops once this contest is over, considering I have many extra characters, for the fun of it… And though I don't have lists, I have two stacks and lots of stack manipulation commands, so that will be useful…

Yeah, I don't have lists either, but I have lots of stack manipulators, so I can use the stack as any number of lists. I also only have eight variables, so some of these challenges will be very difficult for me also…

Random-Man wrote:

2. My languages conditionals are dependent on the length of the program before it, so if I edit anything, I then must change all the conditionals to match it

CodeLegend wrote:

Random-Man wrote:

I will add loops once this contest is over, considering I have many extra characters, for the fun of it… And though I don't have lists, I have two stacks and lots of stack manipulation commands, so that will be useful…

Yeah, I don't have lists either, but I have lots of stack manipulators, so I can use the stack as any number of lists. I also only have eight variables, so some of these challenges will be very difficult for me also…

MartinBraendli2 wrote:

CodeLegend wrote:

MartinBraendli2 wrote:

For the polynomial interpolation challenge:
I was looking for good algorithms, but all i can find are algorithms that take a list of x-values and their corresponding f(x)-values and produce an interpolation for a specific x-value (Newton, Heremite and others). Is there a good algorithm to tackle that challenge? I could do it by solving multiple linear equations, but I'm quite sure, there is a better algorithm out there.

I was taught to use matrix multiplication.

EDIT: (for everyone here)

Let's say you have 3 points: (0,1), (2,3), (5,4)
We want to find an equation of the form y=ax^2+bx+c which passes through them all. So we're looking to return the values of a, b, and c.
So we can form these equations, one for each point:
1=a*0^2+b*0+c
or 1=0a+0b+1c
3=a*2^2+b*2+c
or 3=4a+2b+c
4=a*5^2+b*5+c
or 4=25a+5b+c

With these equations, we can form this matrix relationship:

[ 0 0 1] [a] [1]
[ 4 2 1]*[b]=[3]
[25 5 1] [c] [4]

Then solve for [[a][b][c]]

[ 0 0 1]^-1[ 0 0 1] [a] [ 0 0 1]^-1[1]
[ 4 2 1] * [ 4 2 1]*[b]=[ 4 2 1] * [3]
[25 5 1]   [25 5 1] [c] [25 5 1]   [4]

[a] [ 0 0 1]^-1[1]
[b]=[ 4 2 1] * [3]
[c] [25 5 1]   [4]

[a] [ 1/10 -1/6  1/15] [1]
[b]=[-7/10  5/6 -2/15]*[3]
[c] [  1     0    0  ] [4]

[a] [-2/15]
[b]=[19/15]
[c] [  1  ]
a=-.13333333333
b=1.26666666666
c=1

So the program would output those three values. You can check them in the previous equations, and the math should check out.

So if you're going to use this method, you need a way to inverse and multiply matrices.

Yeah, I got that far, but i couldn't find a simple method for inversing matrices. I found a better method now. I won't tell how I'll do it atm, since I'm not yet sure that I'll beat Random-Man.

Random-Man wrote:

MartinBraendli2 wrote:

CodeLegend wrote:

MartinBraendli2 wrote:

For the polynomial interpolation challenge:
I was looking for good algorithms, but all i can find are algorithms that take a list of x-values and their corresponding f(x)-values and produce an interpolation for a specific x-value (Newton, Heremite and others). Is there a good algorithm to tackle that challenge? I could do it by solving multiple linear equations, but I'm quite sure, there is a better algorithm out there.

I was taught to use matrix multiplication.

EDIT: (for everyone here)

Let's say you have 3 points: (0,1), (2,3), (5,4)
We want to find an equation of the form y=ax^2+bx+c which passes through them all. So we're looking to return the values of a, b, and c.
So we can form these equations, one for each point:
1=a*0^2+b*0+c
or 1=0a+0b+1c
3=a*2^2+b*2+c
or 3=4a+2b+c
4=a*5^2+b*5+c
or 4=25a+5b+c

With these equations, we can form this matrix relationship:

[ 0 0 1] [a] [1]
[ 4 2 1]*[b]=[3]
[25 5 1] [c] [4]

Then solve for [[a][b][c]]

[ 0 0 1]^-1[ 0 0 1] [a] [ 0 0 1]^-1[1]
[ 4 2 1] * [ 4 2 1]*[b]=[ 4 2 1] * [3]
[25 5 1]   [25 5 1] [c] [25 5 1]   [4]

[a] [ 0 0 1]^-1[1]
[b]=[ 4 2 1] * [3]
[c] [25 5 1]   [4]

[a] [ 1/10 -1/6  1/15] [1]
[b]=[-7/10  5/6 -2/15]*[3]
[c] [  1     0    0  ] [4]

[a] [-2/15]
[b]=[19/15]
[c] [  1  ]
a=-.13333333333
b=1.26666666666
c=1

So the program would output those three values. You can check them in the previous equations, and the math should check out.

So if you're going to use this method, you need a way to inverse and multiply matrices.

Yeah, I got that far, but i couldn't find a simple method for inversing matrices. I found a better method now. I won't tell how I'll do it atm, since I'm not yet sure that I'll beat Random-Man.

Bogo solving anyone?
I bet a program that could theoretically solve this using a Bogo and check method that is shorter than what you explained…

MartinBraendli2 wrote:

Random-Man wrote:

MartinBraendli2 wrote:

EDIT: snip

Bogo solving anyone?
I bet a program that could theoretically solve this using a Bogo and check method that is shorter than what you explained…

Hehe.
Theoretically correct is not enough for this competition, you also have to pass the required tests. Imagine how long it would take to verify a program. Lets say you have to get 15 bits per number right (all 11 bits exponent, plus 4 bits of the mantissa, which would give a tolerance of about +/- 5%). That would give you 1e18 possibilities for the test with 4 data points. Lets say you have a uber fast interpreter, that tests 1e12 combinations per second. Then you would still need 12 days to pass that test. So you would miss the deadline.

Random-Man wrote:

Oh… well I'm out…
I completely forgot to add an absolute value command…
…
…
…
…
…


I guess I'll need to use my ? command even more…

.0<(y-1*)

Random-Man wrote:

Oh… well I'm out…
I completely forgot to add an absolute value command…
…
…
…
…
…


I guess I'll need to use my ? command even more…

MartinBraendli2 wrote:

Random-Man wrote:

Oh… well I'm out…
I completely forgot to add an absolute value command…
…
…
…
…
…


I guess I'll need to use my ? command even more…

Where would you need abs()? The examples in the polygon challenge are both counter-clockwise, so they will produce the same sign (so if needed, you can hardcode the “negate output”, without conditional).

first post wrote:

As of posting this topic, I have already chosen several (15) challenges for you to attempt. In order for you to complete each one, you must write a program in your submitted language that performs the specified action.

CodeLegend wrote:

MartinBraendli2 wrote:

Random-Man wrote:

Oh… well I'm out…
I completely forgot to add an absolute value command…
…
…
…
…
…


I guess I'll need to use my ? command even more…

Where would you need abs()? The examples in the polygon challenge are both counter-clockwise, so they will produce the same sign (so if needed, you can hardcode the “negate output”, without conditional).

Your programs have to be able to work with any input, not just the ones in the examples… (otherwise the hard programs could all be much much shorter)

first post wrote:

As of posting this topic, I have already chosen several (15) challenges for you to attempt. In order for you to complete each one, you must write a program in your submitted language that performs the specified action.

dzaima wrote:

I've found a bug in my code that makes me not able to have the character space as the first character. Am I allowed to fix that?