The Nineteenth Byte

> For a long time I’ve been aware of corecursion and coinduction as something mysteriously dual to recursion and induction, and related to maximal fixed points and bisimulation … but I’ve never understood what they are or what the duality signified by the “co” means.

I kind of feel the same

would appreciate it if someone can explain to me what it is

ASCII-only

> Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case.

hmm. wat

Leaky Nun

recursion is well-defined if the argument gets smaller each time

corecursion is well-defined if the argument gets bigger each time

> $~~~{{\small\mathsf{CountFrom}}}(n)~=~{{\mathsf{cons}}}(n, {{\small\mathsf{CountFrom}}}(n{+}1))$

bsaically Haskell type

Haskell has coinduction

ASCII-only

1:18 AM

55

A: What is coinduction?

First, to dispel a possible cognitive dissonance: reasoning about infinite structures is not a problem, we do it all the time. As long as the structure is finitely describable, that's not a problem. Here are a few common types of infinite structures: languages (sets of strings over some alphabe...

so, coinduction appears to be something like proving P(n-1) given P(n) (and P(some kind of infinity)? maybe?

Zacharý

I FEEL DUMB AS CRAP

I just realized why my code "wasn't working." I originally had UCS2 as a test function, and then reverted it back to its "None" functionality.

I spent a few hours trying to find a bug that didn't exist!

ASCII-only

@Zacharý :|

Zacharý

Wait, never mind. 1(⍇+)2 still doesn't work

ASCII-only

:|

Zacharý

1:37 AM

Yeah, I might just come back to this tomorrow. 1(+-)2 gives 3

user202729

2:12 AM

Some thought about restricted-complexity:

Almost none of the languages have a formal definition of time complexity (only the implementation has)

And so almost none of the answers to restricted-complexity is valid.

@HyperNeutrino Or untick 4 answers.

ASCII-only

@user202729 ... but a language is defined by its implementation

user202729

@ASCII-only And that is the problem.

All implementations are O(1).

And doesn't work for all inputs.

ASCII-only

@user202729 but they do...

user202729

@ASCII-only Until the machine is out of memory.

ASCII-only

@user202729 since when...

user202729

2:17 AM

Because asymptotic.

Leaky Nun

@user202729 why?

ASCII-only

@user202729 which is why most challenges have an implicit or explicit upper bound...

user202729

@ASCII-only Dennis said that.

@ASCII-only But asymptotic.

(seriously. Of course all implementations are O(1) because machines only have finite memory)

ASCII-only

@user202729 yes. asymptotic up to that upper bound

user202729

@ASCII-only Then it's not asymptotic.

ASCII-only

2:17 AM

we don't want to be pedantic here

user202729

See the problem?

ASCII-only

@user202729 sure

I guess.

user202729

@ASCII-only I don't want to be pedantic either, but is popcount O(1) or O(log n)?

ASCII-only

@user202729 O(1). 1 processor instruction

@user202729 okay. then "the asymptotic complexity of the algorithm(s) used"

Leaky Nun

@ASCII-only but time complexity is only defined for the implementation

not the algorithm

user202729

2:19 AM

@ASCII-only That is the problem.

@LeakyNun Algorithm can't define time complexity. Algorithm + machine model can.

Like, if I want to loop from 1 to input. That's O(input). But I will loop from 1 to INT_MAX instead.

ASCII-only

@LeakyNun hmm. then "an ideal implementation of the algorithm"

user202729

Then it's O(1).

Just like how popcount is O(1). Just with exponentially larger constant factor.

ASCII-only

@user202729 oh. this is a good point

user202729

Asymptotic doesn't make sense with bounded input. Unbounded input doesn't make sense with actual implementation. No actual implementation doesn't make sense with PPCG.

In other words: Asymptotic implies unbounded input. Unbounded input implies idealized implementation. Idealized implementation contradicts PPCG rule.

Generally we accept answers that only works up to 2^32.

Bigint answers probably only works up to (2^32)^(2^32).

ASCII-only

2:39 AM

:D
https://tio.run/##7T3bdttGks/SV7TpiUlQvIi2Z5IhJflIFuXwHJnyiNIkGcvhgUhQwhoEuACoSzJ62W@Yx/26@ZDNVlVf0A2AN0vMeM9Oco4FNLqqq6ur69YXDiaT6tVg8Ntvz11/4E2HDttxgygOHXu8t6mXjW3fnehFY9t4jWJ78FkvuAwAT91z7tyB7fUHdhTXrieTbI1p7HpufF@HRl3/qh86o/x6tncVhG58PRY164DS6Q8C/ya/vuxGVIc6A2cSR4vq8b/9y@lo5ISy8mjojNgPne7hyQ89DfYH1x8Gt4AS6jj@0B1tPp/6WLV7fny8@RyeXN9h5x/6pTuLUUPNZhz0p5OJEwLRk3tg2LDZ5F3ZK2kvAGBpCBBe/7oyLmtzs15nZyeHJ012aUfugAE/YLT8mI0Cbwi1WCkKwvC@wvwgZvRoJSDDgHUY8MXz7pnvOEMWB2waOfB8@4YBjUMWTGPm@iy@xsK7mDkTNwqAR8GIDUP7KvChWc9LMI7cO6g/dAdOVGFONKkhtHM3CZMq0b0f23fMCcMgFF83N317DLXtgcP@ckD9@HVzY@DZUcTeBt507Pdc…

weird 14-char columns work now

0

Q: Can someone please create a simple java program using the given below?(For Homework)

Create a class named payroll with a method named computepayroll. The computepayroll method will compute the salary of an employee base on the given data below. Given: Rate = 300 Number of days rendered = 5 10 % Tax Create a main method named payroll

:|

user202729

2:55 AM

@ASCII-only NMP will complain about that.

For such questions I would just use the "no winning criteria" offtopic reason.

Very generic.

Actually...

I don't think having a "Stack Overflow please" close reason is a good idea.

Because it's better if they figure out it themselves, then it's not our fault if they ask a bad question there.

If we redirect them there and then they ask a bad question, ...

New Main Posts

-2

Q: Can someone please create a simple java program using the given below?

Create a class named payroll with a method named computepayroll. The computepayroll method will compute the salary of an employee base on the given data below. Given: Rate = 300, Number of days rendered = 5 10 % Tax Create a main method named payroll

code-golf binary javascript java

-2

Q: split a string with two types of groups, ignoring characters in one

Example inputs and outputs: Input 1 "request.partner" Output 1 [request, partner] Input 2 "request.partner(invite: https://discord.gg, desc: poop).info(stuff)" Output 2 [request, partner, (invite: https://discord.gg, desc: poop), info, (stuff)] Input 3 "request(poop).partner(invite: https://...

string javascript

Zacharý

WTF do people think this is SO?!

user202729

@Zacharý .........

"Be nice applies to off-topic also"

Zacharý

Why the quotes?

@user202729 I just don't see how this place is like SO, or how people get here instead of SO.

user202729

Just to be sure.

BTW --

Anyone know how to see people's close reasons after the question had been closed or after you voted to close?

Zacharý

3:02 AM

Sure of what?

ASCII-only

@Zacharý "programming puzzles"

apparently some people take that to mean "post here if you're puzzled by programming"

Zacharý

"I'm looking for the shortest possible JS answer!", so not TOTALLY clueless.

user202729

You can make this a [tips] [code-golf] question, but then you need to have existing code to be golfed. — user202729 3 mins ago

ASCII-only

3:23 AM

hmm. should this be closed?

user202729

Why?

ASCII-only

it's not a PP or a CG. and it's really hard to read

user202729

codegolf.meta.stackexchange.com/questions/4687/… -

ASCII-only

@user202729 ok sure. but it's still not well defined

user202729

I can understand the challenge clearly and unambiguously.

^~~ I often leave such comments on posts having unclear CV but I think should not be close voted.

@ASCII-only Anyway, what do you think is not well-defined?

@NewMainPosts Deletable now.

ASCII-only

3:41 AM

> Your answer should take be a logical expression of that sort that can just be pasted into python, say, so I can test it. If two people get the same size expression, the code that runs the fastest wins.

user202729

So?

The classic "on which machine" thing?

ASCII-only

well the thing is. a lot of things have a lot of time variance on the same machine

so you might not be able to say which one is faster

user202729

Then they ties...

ASCII-only

also then most of it is just making the expression fast...

user202729

All fastest code use that.

ASCII-only

3:43 AM

@user202729 but fastest-code are usually slow enough that there's a decent amount of time difference

user202729

It's just bad, not unclear.

At least that part.

They could just not provide the tiebreak.

QFT room is really low-activity.

Leaky Nun

4:32 AM

CMC Given positive integer n, print the last n digits of the 10-adic cube root of 3.

(it is unique and it ends ...87895134587)

maybe I should post it on main

looks like this isn't exactly the peak hour... I'll wait

ASCII-only

hang on. i think i can do it the same way i did the last one (well, kinda)

Dennis

@Zacharý The frontend supports multiple categories. However, there's no esoteric category, only a recreational category, and I consider them mutually exclusive.

Zacharý

@Dennis Okay. But programming can be for recreation in a "practical" language :P. I'll just pick "Practical" whenever it's ready.

ASCII-only

@Zacharý it can't be both...

Leaky Nun

@ASCII-only go ahead

ASCII-only

4:43 AM

you can use Python for recreation. doesn't mean it's recreational

Dennis

@Zacharý You can use a shoe to drive in a nail. Doesn't make it a hammer.

7

Zacharý

@ASCII-only It's a practical language designed to be very good at golfing (i.e. better than APL/J/K)

ASCII-only

@Zacharý golfing != recreational...

@Zacharý APL is also "very good at golfing"

Zacharý

@ASCII-only I was basing my example off of Jelly

ASCII-only

@Zacharý and depending on how you view it, charcoal could be practical too (for obvious reasons it isn't)

@Zacharý jelly is not at all practical

~~nobody understands it~~

Zacharý

4:47 AM

@ASCII-only Verbose mode

ASCII-only

@Zacharý well really you could say non-verbose mode is simple to read too. if anything, it's easier to understand for normal people than APL IMO

xnor

@LeakyNun can I suggest including some sort of time or complexity restriction? I'd like to see answers that don't just try every possible value

Leaky Nun

@xnor hmm

ok

ASCII-only

@LeakyNun Python, 95 bytes

Leaky Nun

the 0741852963 part can obviously be golfed

ASCII-only

4:51 AM

@xnor for the CMC? I'm guessing brute force is nowhere near the golfiest way here

@LeakyNun yeah definitely

Leaky Nun

n*n*n is n**3

ASCII-only

just wanted to post something working first :P

@LeakyNun yeah. that was me being paranoid about "what if it becomes a float" >_>

Leaky Nun

and what is it with prec

ASCII-only

:| oops

i just copied the previous one for the template >_>

Leaky Nun

69 bytes

60 bytes with input

53 bytes with a trick

ASCII-only

4:55 AM

:|

Leaky Nun

Leaky Nun vs Leaky Nun

ASCII-only

60

Leaky Nun

close

with some trivial golfs you should get 54

with some maths you can go from 54 to 53

ASCII-only

> trivial golfs

user202729

Yay, new CMC!

ASCII-only

4:59 AM

i'm bad at golfing so those don't exist for me

user202729

@LeakyNun So what?

Leaky Nun

@user202729 and i would also have to modify the challenge

ASCII-only

54

Leaky Nun

you noticed the trivial golfs :P

ASCII-only

53

:D

xnor

5:02 AM

40 with brute force

Leaky Nun

and you noticed the math trick :P

CMC: show that it is unique

ASCII-only

@LeakyNun with math?

xnor

the multiplicative group modulo a power of a prime is cyclic, and the group mod 10^k is the product of those mod 2^k and 5^k

Leaky Nun

@ASCII-only right

xnor

and their orders are both not multiples of 3

Leaky Nun

5:07 AM

(2^4-1)/3 = 5

xnor

@LeakyNun there are 2^(k-1) numbers relatively prime to 2^k in the mult group

Leaky Nun

oh right

xnor

and 4*5^(k-1) for 5^k, i.e. 4/5 of them

Leaky Nun

right

would you like to hear my proof?

xnor

sure

Leaky Nun

5:10 AM

Z_10 is isomorphic to Z_2 x Z_5 as rings

if x in Q_5 such that x^3=1, then 3v(x) = 0, so v(x) = 0

so x is in Z_5

what's v(x)?

the valuation

in the 5-adics?

yes

ah, i see

5:13 AM

and then the last digit of x would have to be 1 (this is a finite problem, check by computer)

then by Hensel it is unique

same for Q_2

xnor

hensel's lemma is the one that you can keep extending to modulo higher powers of the prime?

Leaky Nun

and that it is unique

provided that the derivative of the polynomial is not 0 at the root

@xnor would you like another proof

xnor

i should sleep actually

Leaky Nun

ok

ASCII-only

hmm. i wonder if there's a proof using the fact that n^3 is an involution mod 10 (disclaimer: i don't know what i'm saying)

Leaky Nun

5:17 AM

@ASCII-only would you like to hear my proof

you mean injection not involution

ASCII-only

@LeakyNun why not

Leaky Nun

we will show that for every n > 0, there is a unique x (mod 10^n) such that x^3 = 3 (mod 10^n)

ASCII-only

@LeakyNun wait. injection? how

Leaky Nun

@ASCII-only oh wait is it an involution

yes it is an involution

so for n = 1, let's use your idea

x^3 = 3 (mod 10)

x = 3^3 (mod 10)

x = 7 (mod 10)

by way of induction hypothesis, let's say that there is a unique x (mod 10^k) such that x^3 = 3 (mod 10^k), where k > 0

if y^3 = 3 (mod 10^(k+1)), then y^3 = 3 (mod 10^k) as well, so x = y (mod 10^k)

so assume y = a * 10^k + x

we want (a * 10^k + x)^3 = 3 (mod 10^(k+1))

binomial expansion gives 3a * 10^k + x^3 = 3 (mod 10^(k+1))

multiply both sides by 7 to give 21a * 10^k + 7x^3 = 21 (mod 10^(k+1))

so a * 10^k + 7x^3 = 21 (mod 10^(k+1))

a * 10^k = 21 - 7x^3 (mod 10^(k+1))

21 - 7x^3 is really a multiple of 10^k [since x^3 = 3 (mod 10^k)]

so a exists and is unique

so y exists and is unique

by the principle of mathematical induction, for every n > 0 there is a unique x (mod 10^n) such that x^3 = 3 (mod 10^n) that extends the previous one

so we're done

ASCII-only

@LeakyNun hmm. is there supposed to be an x^2 here

Leaky Nun

5:27 AM

aha

yes

a x^2 10^k = 21 - 7x^3 (mod 10^(k+1))

well x^2 ends in 9 so x^2 is invertible

user202729

5:58 AM

Help. What do you see as the background color of npmjs.com/package/pnpm ?

ASCII-only

@user202729 normal (white)

@user202729 also you should do the most recent CMC with CRT (if it's possible?)

@user202729 also, how does this work

Mr. Xcoder

@user202729 white

user202729

@ASCII-only I don't think it's anyway easier than directly compute it in 10.

That's weird. I see the background in dark gray. Completely unreadable.

ASCII-only

@user202729 easier = shorter?

user202729

It fixed itself.

@ASCII-only I just compute 1/2, but easier.

ASCII-only

6:06 AM

@user202729 sounds like a userscript with a race condition

@user202729 1/2?

user202729

I don't have any userscript.

Mod 5^n.

ASCII-only

@user202729 ah.

user202729

Random question: When should I use i -g with pnpm and when should I not?

Because only one copy is stored anyway.

ASCII-only

@user202729 -g for global commands

i.e. CLI programs, not modules

same reason as -g for normal npm

user202729

Actually for normal npm I (ab)use -g to avoid duplication.

Install modules with -g, then all packages can use it.

ASCII-only

6:10 AM

e.g. sails

@user202729 yeah this doesn't actually really work for everyone

especially since they don't want things to break so they restrict dependency version

user202729

So use -g for packages where it has a corresponding cli.

ASCII-only

@user202729 yes. basically, packages that are intended as standalone programs, not dependencies (this includes pseudo-package-managers e.g. sails/bower etc)

user202729

About Jelly:

I intended to modify the æḟ and æċ in the wiki to note that it doesn't work for negative exponent like this

`æċ`|Ceil **x** to the nearest power of **y**, if **x ≤ y** and **y > 0** returns **y**.
`æḟ`|Floor **x** to the nearest power of **y**, if **x ≤ 1** and **y > 0** returns **1**.

Thoughts?

(because .5æċ2 returns 2 while it should return .5)

user202729

6:34 AM

Too bad I accidentally deleted the Jelly visualizer.

ASCII-only

@user202729 you what

user202729

Help, in *3_3ọ⁵ƲÞ how far does the Ʋ capture?

LNC is super hard to remember.

Ah, nvm.

Chain rules.

ASCII-only

@Dennis would it be possible to add a CLI flag to Jelly to visualise the parse tree (chain tree? idk)

user202729

6:54 AM

There is a small problem: How should ⁺ be displayed?

Just duplicate the link?

ASCII-only

@user202729 hmmmmm

@user202729 IMO just show the single argument

user202729

Jelly (efficient), 24 bytes

Just brute force one digit at a time.

ASCII-only

~~:| brutwforcing~~ i guess mine isn't that different

Cows quack

I would like to see an explanation on how your answer works, ascii

ASCII-only

@Cowsquack i have absolutely no clue >_>

user202729

7:08 AM

Probably non-bruteforce is a better idea ...

Cows quack

still D:

ASCII-only

well actually, the explanation is simple this time

@Cowsquack there's only one possible digit given the last nonzero digit of the square

since n^3%10 has to be that digit

Cows quack

ok

ASCII-only

n^3:10: {1: 1, 2: 8, 3: 7, 4: 4, 5: 5, 6: 6, 7: 3, 8: 2, 9: 9}

my code just calculates the values using maths. somehow

wait. that's not right

@Cowsquack for some reason i'm calculating digit where digit * 3 % 10 == n

Cows quack

>_>

user202729

7:11 AM

Anybody want to post an answer to my newest challenge ...?

ASCII-only

i have no idea how it works, but it's the same thing as last time

user202729

@ASCII-only What's the square?

ASCII-only

@user202729 *cube

@Cowsquack it kinda makes sense (for numbers very close to 1, n^3 roughly equals 1+(n-1)*3) but it doesn't explain why it works for even the second digit

Cows quack

the thing I'm really confused about is why you're adding to n

ASCII-only

@Cowsquack my code calculates the next digit: 7 -> 80+7 -> 500+87

Cows quack

7:16 AM

I misread the python so badly

ASCII-only

:D making all code, pre {font-family:'Fira Code'} was a good idea

@Cowsquack :|

Cows quack

evil snek

user202729

Nice closed form formula, actually...

Now I feel confused too.

ASCII-only

@user202729 +1. join everyone else that feels confused

user202729

Let me try to write the formula.

So assume p is a power of 10, p > 1.

0 ≤ n < p such that n³ ≡ 3 (mod p).

We want to find n + d × p such that (n + d × p)³ ≡ 3 (mod 10p).

Which is equivalent to n³ + 3n²dp ≡ 3 (mod 10p).

ASCII-only

7:26 AM

@user202729 yep. this is what Leaky Nun had

he proved it's unique. i guess you could try figuring out which one exactly

user202729

What I can't figure out is that why can the n² be "ignored".

Ah...

n² ≡ 9 (mod 10).

⇒ n²p ≡ 9p (mod 10p).

⇒ n³ + 7p×d ≡ 3 (mod 10p).

ASCII-only

@user202729 how does this follow from the previous thing

Cows quack

3×9pd ≡ 27pd ≡ 7 pd (mod 10p)

because it is mod 10p, 27→7

ASCII-only

ah, ok

@user202729 ah. and d = 3-n³÷(7p) (mod 10p) which is basically (well, not that close to actually) what I appear to have used? except for the 3- part?

user202729

7:43 AM

Because n³ - 3 ≡ 0 (mod p) and p > 3, floor(n³ ÷ p) = (n³ - 3) ÷ p.

@ASCII-only Substitute into the equation in a previous message.

34 mins ago, by user202729

Anybody want to post an answer to my newest challenge ...?

Cows quack

@ASCII-only don't you also do (n³÷p)×7?

user202729

Even a O(n²) steps solution should be fine.

ASCII-only

@Cowsquack yeah. not divide by 7p. and without 3-.