the only case that ever does anything is 0-x to get unary minus

I'm not convinced negative numbers are useless, but 0's even less likely to be useful. But I just don't see an obvious proof

@Sp3000 the only time negative numbers are useful is to subtract

but you can always subtract at the end

rather than make negative at the start, and add later

If we write the expression using the +, -, *, /, :+, and :* functions, I think we could make an algorithm to replace negative numbers.

@Sp3000 well

that's just ::*:*-

the bigger number can always be arranged at the top of the stack, so you want top - second

I was assuming second - top this whole time

@Sp3000 that makes no sense

Because that's how Befunge usually works

but not vice versa

It doesn't matter..

@feersum it does

Example?

if you don't have negative numbers, and you can only second - top, then n^4 - n is inefficient

if it's top - second you can do ::*:*-

n**4-n == x:::**1-* which is an inefficient 9 symbols

If you're doing top - second, how do you do n-n/3?

32x*/

@KennyLau not the same

with flooring division

For example?

lol I forgot that :- and :/ are also possible.

Start with n/3 as a number x, then x:3*-

:- is zero, :/ is one

All right, maybe negative numbers could matter.

@Sherlock9 n is not n/3*3 :)

Then you start with n//3 anyway

@KennyLau could you do us a favour?

@KennyLau just choose some order of - and put it in the question

@orlp by?

oh ok

this is really not something that should be left up to choice

@Sherlock9 What if starting with n//3 is a lot more inefficient, e.g. if n is a nice power of some number?

because we could have 4 different languages right now, depending on which order you choose - and /

Yeah, for golf the choice made sense but I'm not so sure about fastest code

@Sp3000 not even then tbh, but that's too late

Well... more sense

(I'd have preferred just second - top, but anyway...)

Done

@Sp3000 which was the big number you wanted to know again?

We should run all four systems and see which gets the most optimal solutions for 1 to 10000

@Sp3000 Ah, that is a problem

@orlp 38950002?

@Doorknob did you know that there's a Lojban Wikipedia?

Man it's annoying how the RPi has no reset button.

It disconnects from the network all the time and I have to go yank it gfrom the wall.

You could download it right now from here. It's only 12 MB.

@Sp3000 ah, don't have that one

I have 38951136 if you want

27*68*:+67*:*-:**

probably not efficient :P

holy shit I just spotted a cool series

Did you have any of the other numbers in my list? (I'll try 38951136 though)

39337975 9278*:**:*-
39337976 8278*:**:*-
39337977 7278*:**:*-
39337978 6278*:**:*-
39337979 5278*:**:*-
39337980 4278*:**:*-
39337981 3278*:**:*-
39337982 2278*:**:*-
39337983 1278*:**:*-

XD

@orlp I thought I just updated the question...

@KennyLau ah, these are still old results :)

@orlp 47*1+:*7-:*7*8*

This is all the numbers that can be generated in 7 digits btw pastebin.com/WZb48ccH

@CameronAavik Nice!

There may be a small issue with the usage of '/' in retrospect

it rounds it down to an int afterwards

I'll fix that

It should round down.

I mean, it rounds down after evaluating the entire statement

not after each division

By the way, your program should have a line to check whether the existing entry is shorter than the entry you want to update?

it does

oh ok

it's a really messy program, I'm gonna change it to be recursive

for example 22 is 52/9*

right now it's really nested

it can just be 59*2/

well, 52 comes first

in my code

alright

i'm now using hash @orlp

I am making a few assumptions, one that it will never reach a negative number at any point, and that the ':' won't appear in the first 3 characters

sounds reasonable

@CameronAavik 25 == 5:*

it also equals 55*

anyone wants to write an efficient integer power method?

Alright, fair enough

her is the list with the fix for division pastebin.com/R8SiYTS8

as a result it never actually divides anywhere

if we can prove that we don't ever need subtract or divide then that may be a good solution

but as we can see, it's not needed at all with seven characters

Your first skip appears to be 239 but I haven't verified that

	private static long sq(long a){
		return a*a;
	}
	private static long pow(int b,int i){
		if(b==4) return 1L<<2*i;
		if(i==0) return 1L;
		if(i==1) return b;
		if((i&1)==1){
			return b*sq(pow(b,i>>>1));
		}else{
			return sq(pow(b,i>>>1));
		}
	}

(the 4 is a special case for my program)

269 is also not possible in 7 characters

@CameronAavik You may need division for (9**6)/2

@KennyLau What's this for?

@Sp3000 power :)

integer power

b**i

@CameronAavik But 239 is possible with 65*8*1-

As in just general programming or are you using that for Befunge?

hmmm

Similar to going from 270 to 269

@Sp3000 Adapted to my challenge

Because exponentiation by squaring does not give optimal answers (in case it's for Befunge)

let me see why

@Sp3000 Then how?

oh

no it's not for the expression

I just want to check if this method is efficient.

Should have a runtime complexity of O(log n), where n is the index.

Surely Java has pow? o_O (I'm assuming that's Java)

sherlock9, we are doing subtraction differently it seems

@Sp3000 I don't think it has integer power.

I was doing top of stack - second of stack

as well with division

@KennyLau Not even Math.pow or BigInteger.pow or something? (I can never remember)

I'll have a look and see what happens if I switch it around

313, 314, 431, 485, 501, 502, 503, 561-566 all have simple 7-op answers with a subtraction from a close 5-op answer

@Sp3000 Math.pow is not integer, BigInteger I don't want to use :)

I'm afraid BigInteger would slow the whole thing down

I guess @CameronAavik didn't use subtraction?

oh, I did

i just did the opposite order

Not 307 and 309, though

switching it to other order works for those ones

And probably a few others are stuck

New Pastebin coming up?

pastebin.com/shr57bRv

this feels more wrong haha

first skip is 417 to 419

417 is first skip

oops ninja'd

458 is second skip

461

463

465-467

And it's patchwork by the 460's... ninja'd

But it was in the first draft, too

Did you implement second top integer division yet?

yes he did

[337, '95*:*6/']

Ah, I missed that. Thanks Kenny

((5*9)**2)/6

2025/6

@CameronAavik Did you post your code anywhere?

I have not

I just love how a=b=0 is valid in Java

and I won't as it is the most embarassing code I have written, I'm changing it to be recursive

instead of one big nested spaghetti code

I only planned to go up to 5 initially

How slow does it get if your turn it up to 11?

I haven't made it that dynamic yet

@flawr How did you generate this?

@CameronAavik I'd like to see the results when you do

how do you generate all binary strings of length n that has exactly 4 ones in it?

or, how do you generate the next, given the current?

you need all combinations of 4 digits from 0 to n

then sum up 2**m for each m in those 4 digits

I see

not including n though

ok

so if n = 5 then you can have (0,1,2,3), (0, 1, 2, 4), (0, 1, 3, 4), (0, 2, 3, 4), and (1, 2, 3, 4). For the first one you have 2^0 + 2^1 + 2^2 + 2^3 = 15

if n=6
> import itertools
> for item in itertools.permutations(["0"]*2+["1"]*4, 6):
      print(''.join(item),end=" ")

that works too

I speak Java xd

I do not. Good luck with Java :D

Thanks :p

Next given current's a lot more interesting than generate all :P

But anyway:

Rather than using a wall of text, link to code for itertools.permutations here docs.python.org/3/library/itertools.html#itertools.permutations

I guess I can do next given current

thanks @Sherlock9

next given current I'd have to go back to learning about generating sequences

in sequential circuits

you can do up a truth table for what each bit should be next etc.

@KennyLau Apologies for the edit. Didn't like the wall of text

@CameronAavik @Sherlock9 It's fine, I figured it out.

it's basically a state-machine (turing)

yep

Much faster

for item in set(itertools.permutations(list("001111"))):
    print(''.join(item),end=" ")

Or

for item in sorted(list(set(itertools.permutations(list("001111"))))):
    print(''.join(item),end=" ")

There should be a better way to do this. Back soon

> set(itertools.permutations(list("001111")))

Er... that set() and that list() aren't necessary

@Sherlock9 Again using processing. I wrote a code that, given a value between 0 and 1 and an integer n, returns the corresponding position on the n-th hilbert curve. Then I evaluated those at the first 5 (I think) curves for a certain number of points and continuously interpolated the position of those points.

for item in itertools.product(range(2),repeat=12):
    if item.count(1)==4:
        print(''.join(map(str,item)),end=" ")

@flawr Excellent! I wasn't here for last night's discussion, so I didn't hear about processing (the program, Processing?) or interpolation. Thanks for explaining again :D

Hello again

@DerpfacePython Hi!

Doesn't work

Don't try it

@Sherlock9 Well we did not talk about it. (Processing is basically Java but simplified a lot with built in libraries for graphical stuff.)

processing.org

I've used Processing before in class. Never did do interpolation like that though :D

I made Lissajous curves spin when you pressed certain keys, but that was just from redrawing the curves

how do I configure xubuntu such that it kills the highest memory process when it runs out of memory, rather than hang the machine?

	private static long next(long a,int n){
		int i=0,j;
		for(;i<n;i++){
			if(((a>>>i)&1)==0) break;
		}
		a = (a>>>i)<<i;
		for(j=i;j<n;j++){
			if(((a>>>j)&1)==1) return a^(((1L<<(i+2))-1)<<(j-i-1));
		}
		return 0;
	}

@DerpfacePython Are you asking a question?

Yeah

I was wondering how to fix it

Could you explain what each part does?

memory: 000 000 000 000
>>>>++++++++++
memory: 000 000 000 010
<<
++++++++++++++++++++++++
memory: 000 024 000 010
[
[->+>-[>+>]<<<<]
>>>>>[-]
<<[->+<]
<<+>
]
memory: 000 024 000 010

Line-by-line?

Then it goes

000 023 001 009 001

000 022 002 008 002

...

000 015 009 001 009

000 014 010 000

And because there's an 000 in the fourth memory byte thing

It removes the 009

Goes back to the 010

Moves it to the next one along

and starts the thing again

etc. etc.

Hello?

the pointer is here...

do you have the debug option in your BF parser?

alright, code is a little better for my generator thing

generating all up to 7 takes 0.833 seconds

however I think I can make some more optimisations

ok, applied some more optimisations and was able to generate all the shortest befunge code that can be done in 9 or less characters

can do it in 0.83 seconds

11 or less characters takes 7.21 seconds

Doesn't look like it, no

wow

I'm gonna make another paste

@DerpfacePython My analysis could be wrong. Use an actual debugger to see the memory dump :)

updated question

Oh, you mean the memory... no I have that.

I have a debugger.

Even with that, I still can't figure out how to fix the problem, though.

copy.sh/brainfuck

It's just here

put a debug-char before the last character

I got a 502 trying to paste it

will upload file and share it

it is 2MB

I'll just upload the code pastebin.com/Nz9uxL33

and you can run it and generate it yourself

@KennyLau @Sherlock9 ^

Nice @CameronAavik

@DerpfacePython I'm thinking

Thanks @KennyLau

Woop it died doing 1921600 :(

Oh, Python 2?

you running my code sp3000?

it doesn't take in the number you want to find

it takes in a number and it generates all the numbers that can be created in that or less characters

so by default it was 11

it finds all numbers that can be created in 11 or less characters

Well that's awkward :P oops (and thanks)

it creates a file called outputfile.txt

btw, first number that can't be done in 11 characters is 5963

it can only be done in 13 characters

@CameronAavik are you sure your program works?

I have no reason to believe it doesn't

well, you always alternate number and oper, right?

(seeing : as a number, for now)

yes

so your program can't generate ::*:*

which is the shortest way to cube a number

@CameronAavik what is your programs output for 59049?

it counts : as a number

@CameronAavik yes, and 9::*:* is 3 numbers in a row

@orlp 39*9*:*

@CameronAavik see? not optimal

wait, so * multiplies all the numbers on the stack?

not just the top 2?

@CameronAavik no

then that is an invalid program no?

it puts 9 three times on the stack

then multiplies top 2

@orlp The shortest way is ::**, not ::*:*.

so it has 81 9

then puts 81 on stack

err

multiplies 81 by 81

I mean ::*:**

and you have two left on stack

so in this case your thing is optimal

@orlp That's x**5?

but what about 371293?

(13 cubed)

94+::*:**

94+::**

ahh.. yeah

you are right

hmmm

alright, I think I know how to fix that

@DerpfacePython sorry I don't know how to fix it

gist.githubusercontent.com/orlp/…

all numbers with 7 characters or less

fully bruteforced, so pretty likely to be optimal

nice

only twelve numbers use /

(but since I don't store equal length duplicates, more are likely possible)

533: 85*:*3/

is that possible without /?

(in 7)

mine does the same

Considering that the factorisation is 13*41 and the only square in range is 23^2, seems unlikely

and not unsurprisingly, none of the solutions use 0

I'll get to work on 9 now

7's a little small for negatives to be of any use, assuming they're useful at all

If you're doing 9, you should see 1921600

Mine said 77*:*:*3/

Yup, sounds good

but I haven't fixed it to allow repeated colon

Yup, I do POV-Ray.

gist.github.com/schas002/4997dfa6ad6fb7e40942b1f49739cf79

@Sherlock9 do you want to join the UGL project?

what is UGL?

I only know _UNK

Unipants' Golfing Language

@Sherlock9 What is it?

@KennyLau ^

@zyabin101 I'm in

@zyabin101 I'd like to help generate snippets

It was my friend who wanted to try implementing it entirely

@Sherlock9 Okay. Our TODO list contains an item to golf UGL numbers.

Try to generate snippets for it.

Would that not mostly end up like Kenny's 0-9 optimal challenge?

@zyabin101 What am I supposed to do?

@Sherlock9 What is "Kenny's golfing challenge?"

Except since we have stack manipulation options, it's easier

@KennyLau Mistyped

I see

@Sherlock9 Don't forget registers!

Hooray for registers!

@zyabin101 What am I supposed to do?

@Sherlock9 Actually, the problem gets even harder when you have stack manipulation operators...

@KennyLau Help us complete the items in the TODO list.

Currently it has two items: make a prime checker and golf UGL numbers.

What do loading and saving registers do? It's not clear, as stated

(But please, don't do the latter as a challenge.)

@Sherlock9 cuscuuuR saves 3 into register 1.

cusr pushes the value from register 1.

@Sp3000 Ah, I misspoke (mistyped?). Finding optimality is harder. Optimal solutions should be shorter than in Kenny's challenge, though.

In some cases, at least

s and R pop a number from the stack.

Ohh

Added dot-module for even better ls.

I'm starting to think Kenny's problem is just impossible to do in the time constraint

the befunge one

it may be possible if he removes ':' though

I don't think there's a time constraint per se, just how many you can do in the set time

Removing : kinda removes the whole challenge though :P

oh, I need to read proper

"That means, the program needs to print the required representation from 1 onward" what does this mean?

that I need to make it work for all numbers from 1 to n?

Charlie Brooker looks a bit like a white Laurence Fishburne. Now I can't un-see it.

@CameronAavik your program must spit out representations of numbers

in order

so:

all in one minute?

or the maximum for an individual takes one minute?

etc

after one minute your program is terminated

the highest number it has printed it its score

(the printing itself is not counted in the time)

ah, so I need to change my program to use BFS

instead of DFS

if it didn't print numbers in order, or one of your solutions is suboptimal you are disqualified

How do you separate the I/O time from the rest of the running time?

probably time around it?

(The program is invalid if it outputs a string longer than needed for any number.)

@CameronAavik Do you have enough memory to store every answer lol

I was going to write to file

maybe i should delete that line then

kenny lau, adding the colon operator makes it ten times more difficult btw

it's_gone.gif

you can keep it if you want

but yeah

lol

@CameronAavik isn't that the point?

true ;P

the colon makes it interesting

would it safe to assume that the combination ':-' and ':/' never apepars?

since they spit out 0 and 1 respectively

yes

@CameronAavik beware though

:....- where ... is some operations might happen

$ unzip; strip; touch; finger; grep; mount; fsck; more; yes; fsck; fsck; umount; sleep

@orlp What does it do?

lel

At Sp3000's request, I've created a state graph of 4x4 toroidal Game of Life:

Full res is 2000x2000 and note that I've removed the arrowheads because they were cluttering up the graph (so all edges are directed, generally pointing towards the centre of each cluster, where the centre might be a loop).