The Nineteenth Byte

7:00 AM

000 024 000
000 023 001
...
000 014 010
001 014 000
...
002 004 000
002 003 001
002 002 002
002 001 003
002 000 004

@DerpfacePython This is the algorithm I can think of, takes 3 bytes

Sherlock9

@Sp3000 Dang, missed that :D

DerpfacePython

@KennyLau Would something like [-[<]>-[<]>-[<]>-[<]>-[<]>-[<]>-[<]>-[<]>-[<]>-[<]>] and extending on it work?

I could use that as a tester

orlp

@Sp3000 gogo write a program

DerpfacePython

For if the thing is larger than 10

IDK

throwing around ideas

Kenny Lau

@DerpfacePython Just try my algorithm lol

DerpfacePython

7:01 AM

Sre

Sure

Have to go to sleep 1st though

Kenny Lau

@DerpfacePython ok, see you tomorrow

DerpfacePython

Just like a rest

Thanks @KennyLau

Kenny Lau

@DerpfacePython alright

orlp

@KennyLau if you order - and / right, then you could put all numbers always at the start, right (for the moment ignoring :)?

Sp3000

> for the moment ignoring :

Kenny Lau

7:04 AM

@orlp I think so...

Sp3000

The hardest part :P

orlp

if you do it that way then the bigger number will always be at the top at the stack, so you want - and / to do top - second or top / second

Kenny Lau

@orlp No need to ignore :. It can also be put at the last.

orlp

@KennyLau well, the stack needs to end up at one number

Kenny Lau

@orlp It doesn't really matter, since you can still swap them

orlp

7:05 AM

that is what I wanted to steer to

Sherlock9

1921600 is giving me 29+:*1-19+*1+6:*4+:** which is nowhere near 11

orlp

can we see :*, :+ as separate operations?

Kenny Lau

@orlp still, all the : can be put at the back

For example,

29+:*1-19+*1+6:*4+:**

orlp

there is no : in the back

in that example

Kenny Lau

I see

I can't convert that to all-back

I guess you can't put everything at the back

@Sherlock9 The first part 29+:*1- is 120?

Sherlock9

7:07 AM

It's done from left-to-right in that order, so I'm not sure how moving the operations around wouldn't affect the order

Yes

Then times 10 plus 1 to get 1201

Kenny Lau

654** is even shorter

So I'm not sure what your program is doing

Sherlock9

Then make 1600

Sp3000

I don't think it was a program :P

Kenny Lau

Your program is treating :* and :+ as two operations...

Sherlock9

Messing around mostly

No, they're two separate operations

Kenny Lau

7:08 AM

Your program is also treating them as one byte

Sherlock9

I said nowhere near 11

Kenny Lau

1201 is really 12658***+

57*:*38- (35**2 - 24)

by inspection lol

Sherlock9

@KennyLau That gets me 481. Did you mean 15568***+?

orlp

my question, is there ever an optimal solution that requires any series of : to not be followed by an equal length series of *+

Kenny Lau

@Sherlock9 Never mind, the second one is shorter

@orlp Just look at mine

orlp

7:12 AM

@KennyLau I have no reason to believe your solution is optimal

Sherlock9

@KennyLau That needs to be 57*:*38*- which is the same length as 15568***+

Cameron Aavik

what happens if an operation is used when only one number is on the stack?

orlp

@KennyLau and in your solution every : is followed by an equal amount of operators

@CameronAavik invalid

Sp3000

@orlp What do you mean, like can I have ::*:**?

Cameron Aavik

alright, because in the comments someone was saying 9*9*9*...

feersum

7:13 AM

Stack-based languages are gross; maybe we could have more clarity of thought by looking at it functionally.

Sherlock9

@CameronAavik That is a regular mathematical example, and not an example of code, I think

Cameron Aavik

ah

feersum

Like : is let x = f() in op(g(x), h(x))

Where g and h get to use x exactly once.

Sherlock9

@feersum I should figure out functional languages, verbs, left and right parameters and such very soon

Kenny Lau

@orlp I don't quite get your question. Every : creates one more element, which must get eliminated by an equal amount of * or +.

orlp

7:14 AM

@KennyLau not necessarily immediately

feersum

@Sherlock9 All of that crap is only for J

Sherlock9

Or - Since you can use 6:*6::--- though that isn't optimal for 18 and 36* should be used instead

@feersum Well, I do want to learn Jelly, as well :D

But I am going to go back to Learn You a Haskell and How to Design Programs (this is for Racket) soon

orlp

@Sp3000 hrm, that's basically ^5

feersum

Write-only languages, whatever.

Kenny Lau

Oh

@orlp You're asking an instance where : does not appear as :* or :+.

That's basically proven.

wait

not really

Sherlock9

7:17 AM

15568***+58*:** is 1921600

Sp3000

@orlp Yeah, it's meant to be. I wasn't sure whether you meant the *+ follow the : immediately, since in ::*:** the last colon happens after only one * instead of two. But based on your other comment I guess not

Sherlock9

Which is 15. Not sure what next to try to get <11

Kenny Lau

For example, 78*:5-* = 2856

zyabin101

Which lang?

orlp

@Sp3000 basically I'm trying to get rid of :

Sp3000

7:18 AM

How are you proposing to do that? I'm not quite following...

Sherlock9

@zyabin101 This challenge codegolf.stackexchange.com/questions/77956/…

orlp

and replacing it by instructions that do not grow the stack

Sherlock9

Oh did you see my post about UGL, zyabin?

orlp

e.g. + shrinks the stack by 1

:* leaves the stack size unchanged

zyabin101

@Sherlock9 Which post?

orlp

7:20 AM

:<expr>* leaves the stack unchanged

Sp3000

@orlp Well the 86387 test case I had was because I was hoping 77*:6-:2-** to be optimal, as in 49*43*41

which you can trivially extend to a longer chain of similar divisors

Kenny Lau

@orlp Prove that every solution must have odd length.

Sherlock9

2 hours ago, by Sherlock9

@zyabin101 So my friend who is also a programming guy and also an engineering guy took one look at UGL and decided to try implementing it in Arduino

orlp

@KennyLau that's not very difficult :)

every operation grows or shrinks the stack by 1

we must end at a stack size of 1

the stack is initially length 0

Kenny Lau

That's something I never considered.

I need to optimize my Depth-first search very hard.

orlp

7:23 AM

@Sp3000 basically, if we can transform the problem in some way that we only ever have to consider operations that shrink the stack or leave the stack unchanged, we do not need to keep track of stacks at all, since we can use the unit size stack

and then every operation is based on one or two numbers

Kenny Lau

@orlp Let's develop a regex that can match every valid expression of length 2n+1

orlp

@KennyLau fairly certain regex has no such recognition power

(division by zero)

_UNK

Kenny Lau

(?!.+0/)

Sp3000

@KennyLau You'd probably want to generate valid programs from ground up than filtering all possible strings via regex

Sherlock9

58*::56**1+** for 1921600 at 13 operations

Kenny Lau

7:25 AM

@orlp I just realize that if the length of an expression is 2n+1, there must be n+1 instances of [0-9:] and n instances [+-*/].

Sherlock9

Just realized that as well. So an expression with different total amounts of growing and shrinking operations would definitely be invalid

Kenny Lau

@Sherlock9 Can be used to optimize my DFS very far

orlp

I don't think you should loop over all strings

I think you should try to combine strings

Kenny Lau

why not?

I tried

It failed me on 3727

Sherlock9

^^^^^ Lots of memory wasted

Sp3000

7:28 AM

@orlp What does your program give for 5256?

Kenny Lau

It takes three layers to generate this: 19:*+59*99**+

Where this takes four layers but is shorter: 78*5+:*6+

Sherlock9

sigma(15**(2n+1)) for n in range(0, k) where 2*k+1 is the optimal number of operations (when found) is a lot to search through

orlp

@Sp3000 haven't made it print anything about 1000 yet, sec, let me run it

Kenny Lau

Three layers: ((1(9:*)+)((59*)(99*)*)+)

Four layers: ((((78*)5+):*)6+)

feersum

Does anyone have any thoughts on my functional representation earlier?

I think if this is correct, it should be clear that negative numbers are not needed.

orlp

7:31 AM

@feersum fairly certain they are not needed

Kenny Lau

@feersum What are you referring to?

@Sherlock9 Not really.

Sp3000

@orlp Oops, sorry overlooked an easy solution. Can you try 6162 instead?

orlp

I have an idea

feersum

let x = f() in op(g(x), h(x)) where g(x) and h(x) use x exactly once.

Kenny Lau

@Sherlock9 You only have n+1 instances of [0-9:] and n instances of [+-*/]

feersum

7:31 AM

As equivalent to using :.

orlp

@Sp3000 6348*:*+*

Sherlock9

Ah, I misread it earlier. Well, that could work. Not sure how useful it would be since we're not repeating code very much

Sp3000

Hm...

orlp

@feersum I had a different alternative to :

or maybe it's the same in other words

Kenny Lau

@Sherlock9 Which makes the count (binom(2n+1,n+1)*(11**(n+1)))*(binom(2n+1,n)*(4**n))

orlp

7:33 AM

you define all functions that do not grow or shrink the stack

e.g. :*, :+ and N+ N- N* N/ for arbitrary N

feersum

Functions of how many arguments?

Cameron Aavik

just confirming, all valid solutions will have an odd length right?

orlp

@feersum one

Kenny Lau

@CameronAavik Yes, we proved that earlier.

Cameron Aavik

well, all shortest ones

alright, cool

Kenny Lau

7:34 AM

@CameronAavik No, all valid ones.

orlp

then you can ignore :

feersum

What does the :* function mean?

Kenny Lau

@CameronAavik If you count 12 as invalid

@feersum x**2

anyone notice how J uses *: for squaring.

feersum

@KennyLau That can't be right.

orlp

by only considering :..........* and :.......+ where ..... are non-growing/shrinking functions

feersum

7:35 AM

Because the nyou couldn't use : to calculate x^3.

orlp

@feersum it duplicates the stack

then multiplies the top by the second-top

Sherlock9

@feersum 5::** is 5**3

Kenny Lau

@feersum x**3 is x::**

Cameron Aavik

I was thinking a good approach would be to cache all the shortest solutions that can be done in 5 or under characters, then work back from the input number

Sp3000

@orlp How about 38950002? Should be <= length 11 (not sure if that's too large for your program though)

orlp

7:36 AM

@Sp3000 too long for now

Kenny Lau

@CameronAavik nice.

But then you can't prove it must be the shortest.

feersum

Obviously : can be used for cubing in the actual Befunge code.

Why does everyone think I'm so stupid?

Sp3000

@orlp Hmm darn, I was hoping to do something like (something that pushes -n) ::*:*+ to calculate n^4-n

Kenny Lau

@feersum :* isn't a special operation in my challenge

Sherlock9

How did you mean to phrase it, feersum?

feersum

7:37 AM

I'm discussing @orlp's reference to a ":*" function that is supposed to have equivalent power.

orlp

@feersum basically I'm trying to get rid of : as an operator, and replace it by a set of non-growing operations

feersum

Which I still don't follow.

Maybe you could give an example of how to calculate x^3

Sherlock9

@orlp Feersum is right

feersum

With :* functions.

Sherlock9

If you replace that with just squaring

How do you do cubing?

Sorry for the misunderstanding, feersum

orlp

7:39 AM

@feersum ::**

I never said I tried to replace it with :*

feersum

I'm just going to go bang my forehead against walls now.

orlp

I said I want to replace it with :......*, where ..... is any combination of expressions that does not change the stack size

Sherlock9

No, no. Once you've replaced :* with something else, say @ or something, how do you do cubing

Oh

OH

orlp

::** is :......* where ...... = :*

feersum

I see.

Sp3000

7:41 AM

So... how does that handle the 49*43*41 and similar example?

feersum

So yeah, :* is like let x = f() in *(g(x), h(x))

Likewise with :+.

wait no it isn't

Because you can do functions to both uses of x in my example.

Sherlock9

77*:6-:2-** where :.....* the ..... is 6-:2-* and 2-

feersum

So I don't see how you would do (x^2 + 7) (3x+5)

With :....*

Kenny Lau

@feersum How would you do that?

feersum

@KennyLau Do what?

Kenny Lau

7:44 AM

(x**2+7)*(3*x+5)

Sp3000

@Sherlock9 Oh... so "does not change the stack size" is nested? Hmm struggling to see the advantage, but okay...

feersum

Oh right that's impossible.

I'm just bad in stack languages.

Kenny Lau

@Mego Another advantage of non-stack :p

Sherlock9

@Sp3000 Ask orlp. His idea

Sp3000

It's just that there's no swap here, but (x^2 + 7) (3x+5) is definitely possible

Kenny Lau

7:46 AM

x::*7+\3*5+* in stacks

Sp3000

Well unless you mean it has to be done with exactly that factorisation?

orlp

@KennyLau what is \ ?

@Sp3000 well the task is simple

Kenny Lau

@orlp I mean in stacks, not in my challenge

orlp

you start with a stack [x]

Sherlock9

In stacks, meaning it's swap. Not valid in this challenge

Kenny Lau

7:47 AM

@orlp In stack-based languages, `\` means swap

Sherlock9

Double `\\`

feersum

@Sp3000 Right, I mean it can't be done my multiplying thoes two things at the end.

orlp

and using "0123456789+-*/:", get [(x^2 + 7)(3x+5)] on the stack

which should be possible, just not in that form

feersum

So orlp's approach seems to be the right way.

Sp3000

@feersum So "exactly that factorisation", then yeah I agree

orlp

7:48 AM

@feersum that's why I think my approach works

exactly because there is no swap

Kenny Lau

(x**2+7)*(3*x+5) = (3*x**3+5*x**2+21*x+35)

orlp

the only problem

is that <some number>+ is an operation that doesn't grow or shrink

but as the amount of <some number>s you know goes up, combinations explode

e.g. if you know how to make 2348

then :<expr for 2348>+* should be valid

and so should :<expr for 2348>+<expr for 42>/*

on the positive side, we can throw away the concept of stack size

feersum

Right, you get complexity of a number instead.

orlp

N+, N- N*, N/, :...+, :...-, :...*, :.../ are all operations that leave the stack size unchanged

zyabin101

@orlp x^2 = x:*

orlp

7:54 AM

where N is an arbitrary number we found, and ... is an arbitrary expression that doesn't grow the stack

zyabin101

3x is obviously x3*

Kenny Lau

@orlp Is there any difference between N and ...?

Sp3000

@zyabin101 The problem isn't what's in the brackets, it's multiplying the two expressions at the end

feersum

Probably length 10 should be doable.

Integer overflows would be super annoying though.

orlp

@KennyLau yes, N grows the stack by one

zyabin101

7:55 AM

Uhh, then idk

orlp

e.g. 5

Kenny Lau

@orlp Is there any difference between N and :...?

orlp

@KennyLau I'm trying to get to a system where we can ignore that the stack exists at all

Kenny Lau

I see

Sherlock9

By definition, every set of operations after the first number, with [1-9:].....[+-*/] will not change the stack size. We have to go from stack size 0 to stack size 1 but we can't do it in one operation for any number larger than 9

I use [1-9:] as 0 is useless for these calculations

Sp3000

7:58 AM

I'm actually still not sure whether 0's actually useless

orlp

it is

feersum

It follows from negative numbers being useless.

orlp

@feersum not even then

feersum

Well, I'm convinced they are.

Sherlock9

0+, does nothing. 0-, does nothing, 0*, makes TOP 0, 0/, breaks the math

Transcript for