Qbasicnews.com
February 22, 2020, 06:56:50 AM
 Pages: [1] 2 3 ... 7
 Author Topic: Challenge: Algorithms having only one line of code.  (Read 34944 times)
Moneo
Na_th_an

Posts: 1971

 « on: June 23, 2003, 10:32:28 PM »

Code:

Ok, here's the rules:

1) It must be considered an algorithm, formula or method.
Add 15 to X   ----   X=X+15    This is not an algorithm, agreed?
If it were, then every line of code in a program would be.

2) You must describe the algorithm first, i.e., what is its purpose.

3) Then show the one line of code.

4) Multiple statments on one line; like: x=x+1 : x=x and 15
are not considered as one line of code.

A good example is one we've already seen with the XOR.
The purpose is to turn a switch on if it's off, and turn it off if it's on.
The one line of code is: sw=sw xor sw
or equally cool:              sw=1-sw

*****
 Logged
na_th_an
*/-\*

Posts: 8244

 « Reply #1 on: June 23, 2003, 11:17:04 PM »

The cycling counter:

Code:
counter% = (counter% + 1) MOD max%

If max% is a power of two it is better to do...

Code:
counter% = (counter% + 1) AND (max% - 1)

Does this one count?
 Logged

SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio
underBASIC, homegrown musicians
[img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
Moneo
Na_th_an

Posts: 1971

 « Reply #2 on: June 24, 2003, 01:28:37 AM »

Yes nathan, it may count if I can figure out what you mean by a "cycling counter".  Does your one instruction finish the whole idea?
*****
EDIT:
I just figured out with pencil and paper what you want to do. It's brilliant!
You want to do (or cycle) some code max number of times, where max is a power of 2. Actually, because of the logic, you need to do this from zero to max-1.
You need the following setup or initialization.

max = (some power of 2) - 1
counter = 0
gosub logic

Then, your one line algorittm embedded in a loop becomes:

loop:
counter = (counter + 1) and max
gosub logic
goto loop

In this manner, your one line instruction to increment and reset will enable us to perform the subroutine called "logic" repeatedly for values of zero to max.
The rest of you should notice the subtle point of his instruction, in that when the counter is incremented 1 beyond max, the "and" wraps it around to zero.
*****
 Logged
seph
Na_th_an

Posts: 1915

 « Reply #3 on: June 24, 2003, 02:06:38 AM »

I've tried the code and basically it counts starting at counter% until it hits max%, at which point it sets counter% to 0. Basically a normal counter. Works best in DO ... LOOPs. Might be used for a delay method.
 Logged

earn.
oracle
*/-\*

Posts: 3652

 « Reply #4 on: June 24, 2003, 02:06:47 AM »

Here's mine, to turn a switch on if off, or off if on, without using XOR. x = 1 if on, and 0 if off.

Code:
x = ((x = 0) AND 1) OR (1 AND (X = 0))

Though I suspect there may be an easier way, the logical (x=0) may be a hint to others about other algos.

EDIT: Aah. I've just seen Moneo's other way in the XOR thread. But my way still works.
 Logged

Moneo
Na_th_an

Posts: 1971

 « Reply #5 on: June 24, 2003, 02:33:12 AM »

Oracle,
I didn't complie and check yours out, but it looks like you're trying to implement an XOR without using it, which would be like:
a=a XOR b
is the same as
a=(a and not(b)) or (b and not(a))

So, let's substitute your x for a in the above, and 1 for b in above.
So then we have what I think you wanted:
x=(x and (not(1)) or (1 and not(x))

That looks awful. It's late here, let me compile and test it tomorrow.
*****
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #6 on: June 24, 2003, 10:43:11 AM »

Is this good? :|

Code:

CLS
fact& = 12
fact2& = 1

1 IF fact& = 2 THEN fact2& = fact2& * 2 ELSE fact2& = fact2& * fact&: fact& = fact& - 1: GOTO 1

PRINT fact2&
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Moneo
Na_th_an

Posts: 1971

 « Reply #7 on: June 24, 2003, 01:07:16 PM »

Quote from: "oracle"
Here's mine, to turn a switch on if off, or off if on, without using XOR. x = 1 if on, and 0 if off.

Code:
x = ((x = 0) AND 1) OR (1 AND (X = 0))

I was wrong. You are not implementing an XOR. Your code above is a very good approach and it works.

However,  the second expression after the OR is exactly the same as the first expression, and therefore you can just exclude it, leaving the resultant code as:
Code:
x = ((x = 0) AND 1)

Another observation: You have introduced the fact that any expression, like (x=0), results in a true (-1) or false (0) condition. For example:
result = (a>b)
if a is greater than b, result is -1, true
if a is not greater than b, then result is 0, false.

You did great, Oracle!
*****
 Logged
Moneo
Na_th_an

Posts: 1971

 « Reply #8 on: June 24, 2003, 01:17:36 PM »

Quote from: "seph"
I've tried the code and basically it counts starting at counter% until it hits max%, at which point it sets counter% to 0. Basically a normal counter. Works best in DO ... LOOPs. Might be used for a delay method.

Good observations, Seph.

Another use of this "increment and auto wrap at max" logic could be when you are processing a circular buffer whose size is a power of 2. Every time you access the buffer, you don't need to ask "I am at the end of the buffer?" and waste the execution time to test it.
*****
TO AGAMEMNUS:
It might be good if you gave us a hint as to what you want to do. Also, the clause after the ELSE has 2 instructions on it, which are not allowed.
*****
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #9 on: June 24, 2003, 01:51:12 PM »

d'oh! It's factorial!! Well, I have no idea how to code it otherwise. :|
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Moneo
Na_th_an

Posts: 1971

 « Reply #10 on: June 24, 2003, 02:21:45 PM »

Oh, you want to compute the factorial of a number. Well, for the moment, I can't see how you can do that in one line of code, without a function of course. Normally a factorial is computed using a FOR loop. That doesn't mean that it can't be done.  Keep trying.
*****
 Logged
Moneo
Na_th_an

Posts: 1971

 « Reply #11 on: June 25, 2003, 02:43:24 PM »

Here's a little algorithm that I derived.

Given a positive integer number N, compute the next multiple of X:
Result to M.

defint a-z

M = int((N+X)/X)*X

Note: "next" multiple means that if you're already at a multiple, you move up to the next multiple. Example: if N=5 and X=5, the result will be 10.

If you got that, then make a slight change to the algorithm to compute the "nearest" multiple. Example: if n=5 and x=5, the result is 5 because it is the nearest (you're already there). This is like rounding --- if it's already rounded, then that's the answer.
*****
 Logged
Antoni Gual
Na_th_an

Posts: 1434

 « Reply #12 on: June 25, 2003, 03:30:31 PM »

Factorial in one line?
Code:

function fact&(x&):if x& then fact&=x&*fact&(x&-1) else fact&=1 :end function
 Logged

Antoni
Moneo
Na_th_an

Posts: 1971

 « Reply #13 on: June 25, 2003, 04:16:37 PM »

Wow, Antoni! A recursive call to itself --- very sofisticated!
Let me try it out .
*****
Scolta noi ------------- it works!
Brilliant, Antoni.

*****
 Logged
Antoni Gual
Na_th_an

Posts: 1434

 « Reply #14 on: June 25, 2003, 06:12:32 PM »

I have not tested it, but I think it does'nt work.
END FUNCTION can't be in the same line of a single line IF...
 Logged

Antoni
 Pages: [1] 2 3 ... 7