The Nineteenth Byte

Texas is big...

I wonder how many Bosnias and/or Herzegovinas you could fit in a Texas.

@Mego I'd also definitely be interested in coefficient improvements

@AlexA. Dunno, but you could almost fit four Washingtons in there.

@AlexA. you just invented 3 units of area in one sentence

Anonymous

5:02 AM

@orlp Inside the while loop, each of the list comprehensions are linear in n. The while loop should run at most n times, and even then I'm having a hard time coming up with an example where it would even run that many. The number of loops depends on the data values more than the data size.

Apparently it's 13.5 Bosnias.

@AlexA. 5 of them blended

Anonymous

The worst case is, you'd be n shy of 32767 due to the flooring (and you'd have no zeroes), and thus you'd have to add 1 to every element

@CSᵠ Well, they say that America is a melting pot.

@Mego so...

n*n = n^2

5:03 AM

@Mego it's O(i*n) then, i being the no. of loop iterations

@CSᵠ in big-O that's just O(n^2)

i=n ?

because i is dependent on n

Anonymous

I guess... That just doesn't seem right because the # of loop iterations is not really correlated to the size of the data

Anonymous

i <= n, but I'm not convinced there is ever a case where i == n

Anonymous

5:05 AM

It might be more like O(n*f(n)) for some f

@Mego oh, i don't know what you guys are actually talking about, I was just explaining big-O to @CSᵠ

Anonymous

So quasi-linear

@Maltysen ( ͡◉ ͜ʖ ͡◉)

Anonymous

Though for the actual main scoring, I think it'd be pretty hard to get a better score

@Geobits That is many Washingtons. Apparently you can fit several Bosnias in a Washington.

5:07 AM

@Mego its more out of personal interest

@Maltysen indeed, if i is related to n, if not, it's i*n, but i also just jumped in the convo...

@Mego f = n^420

@AlexA. You could fit a whole Florida in a Washington, too, but you'd need to fold it a bit.

@AlexA. was there a specific reason you picked 420? >_>

@Geobits Florida folding is my specialty.

@Maltysen I didn't pick it. It's the value of f.

5:09 AM

@Maltysen He's from Washington.

the reason is 42

times TEN

^

@Geobits Ain't no correlation there.

Clearly :P

╚═། ◑ ▃ ◑ །═╝

Anonymous

Here's the info from running my algo on the scoring data: gist.github.com/Mego/7b9af7581c13aaf55864

5:11 AM

Those are some very nice data you have there.

Anonymous

@AlexA. Do some stats on the stuff and see how much correlation there is please

who has mathematica and wants to fit some graphs?

ninja'd

@Mego Okay then pls to better format

Anonymous

@AlexA. Updated gist

Anonymous

I changed the order to n, loops

5:15 AM

@Mego ( ͡° ͜ʖ ͡°)

@Mego The order didn't matter so much as the labels and crap

> n: 187, loops: 92

Anonymous

Yeah

Anonymous

Scroll down

beautiful

@Mego can you use a much higher n?

anyway from your datadump you're at O(n)

Anonymous

@CSᵠ Yeah, I can gen some new data

5:19 AM

in no way n^2

and constants have no meaning in big-o

Anonymous

Pearson correlation for x=n, y=l is 0.9786039

Anonymous

I have very little idea what that means

Dennis

@Mego @Liam When Martin sandboxed his challenge, the radiation-hardened quine on main did not take code length into account.

codegolf.stackexchange.com/revisions/57257/4

@Mego n*ln(n)*sqrt(n) <-

@Mego The Pearson correlation coefficient measures the linear association between two variables.

A value of 1 means perfectly linearly correlated with a positive slope. A value of -1 means perfectly linearly correlated with a negative slope.

A value of 0 means no correlation.

5:27 AM

so its pretty much O(n^2) then

So 0.979 means that n and the number of loops are very closely linearly related.

Q: Duplicates with different restrictions or no restrictions

@Maltysen it can't be, growth clearly lesser than exp

Anonymous

5

Long ago, this challenge was posted, with the restriction that no numbers may be used in the source code. Recently, another challenge was posted, this time without any restrictions on the source code. Both challenges have the same theme - the look and say numbers. However, the original challeng...

feersum

I read this orlp's challenge again and still don't understand why it can't easily be optimally solved in O(n).

I'm pretty sure I must be failing hard at reading.

i was reading on the data btw

5:29 AM

@CSᵠ isn't the correlation saying that i and n are linearly correlated?

@AlexA. That's also apparent by how closely the line fits to the points in the plot.

Anonymous

@AlexA. I know what the coefficient is; I meant I didn't know what that value meant in the context of figuring out the complexity

by that graph it means that

so the actual thing of i*n is O(n^2)

but it doesn't fit the real data

5:30 AM

@Mego Oh. That I can't help with. ._.

Dennis

@Mego Not sure what that post has to do with anything. Anyway, my point is that I don't think Martin is planning to post his sandboxed challenge now that the challenge on main has its current form.

I don't really understand computational complexity, but I can make pretty graphs and tell you whether things are related. ¯\_(ツ)_/¯

@AlexA. big-o is really only about perceived relative growth

@AlexA. are you and @ಠ_ಠ related?

@Maltysen ಠ_ಠ no

5:32 AM

so by making a pretty graph, you can nail it instantly

Oh

Anonymous

@Dennis The point is, different restrictions/scoring doesn't make the challenge any less of a dupe

feersum

It's technically O(n) because the max iterations is bounded by 32767.

Anonymous

Added more data to the gist

-

Dennis

5:34 AM

@Mego That meta post addresses only restrictions, not scoring rules. And of course different scoring rules can prevent a challenge from being a dupe. It's not the same to have a task a code golf or code bowling.

The original radiation hardened quine would have been won by Unary. That can't happen in its current form, and wouldn't have happened with Martin's.

Anonymous

I changed the time complexity in my answer to O(n^2) until we're certain it's O(n)

@Mego Raw and more raw or just more raw?

Anonymous

Just more_raw.txt, it contains the original data

Anonymous

That looks pretty linear, which means l and n are linearly correlated, which means O(n^2) overall

5:39 AM

Mine has a line

Anonymous

Mine has a link

f really looks like (n^2)/2 -> O(n^2)

Mine would have a link, but R-Fiddle doesn't support reading from URLs. ;-;

But anyway, the line equation is loops = 0.451736 * n

Anonymous

@CSᵠ You mean f(n) = n/2?

Yeah, if it's linear with a coefficient of 0.45, it's more like n/2.

5:43 AM

i mean the growth functgin is looking like n*n/2

Anonymous

If f(n) = (n^2)/2, it'd be O(n^3) :P

Anonymous

I might be able to squeeze some better performance out of it

Anonymous

But I think it would just be lowering the coefficient

Shia LaBeouf "Just Do It" Motivational Speech (Original Video)

►

Feb 12 at 4:51, by Alex A.

@Geobits squez

Anonymous

5:44 AM

Because of the necessity of the correction step, I'm not sure if it could be made into O(n)

@Mego what about O(n*ln(n))

Anonymous

My score goes up by nearly 10x with the larger dataset: 2.83694887356e-05

I'm not clear on why it isn't O(n) based on the graphs.

Anonymous

@AlexA. Because that's loop iterations versus n, not total time versus n. There's n steps within each loop iteration.

@Mego Oh, so since there's n steps within each loop and the number of loops is linear in n, it's O(n^2)?

If that's right I think I get it, otherwise I'm confused.

Anonymous

5:49 AM

Yep

\o/

Anonymous

I'm relatively certain I can optimize it some just based off the fact that it's almost guaranteed to be under 32767 before the loop

Anonymous

I got it linear, but my score went down

Is bigger score better?

Anonymous

Wait a second

Anonymous

5:54 AM

Smaller score is better

A: Model a probability table using 15-bit fixed probabilities

ᕦ༼ ✖ ਊ ✖ ༽ᕤ

Anonymous

Actually no it's not linear, it's O(n*log(n))

Anonymous

4

Python, score 8.68267103351e-07 #!/usr/bin/env python from __future__ import division from ast import literal_eval from fractions import Fraction from math import hypot from operator import itemgetter from sys import argv with open(argv[1]) as f: for line in f: hist = literal_eval(l...

Anonymous

Not only did I improve my score by nearly 30x, but I also improved the complexity from quadratic to quasilinear

Anonymous

It helped when I realized the scoring was squared differences and not RMS

6:04 AM

@Mego o͡͡͡╮༼ ʘ̆ ۝ ʘ̆ ༽╭o͡͡͡

Anonymous

It's actually more like O(k * log(k)), where k is the number of nonzero elements

Anonymous

Since the zero elements get filtered out before the sort

(╭ರ_⊙)

Anonymous

My score on the 1000 dataset is a bit less impressive: 10.662405023671683

Anonymous

But the total score is also a function of n so I don't actually feel so bad

6:18 AM

userecript patch to toggle sites more quickly from topbar is here

Here is a super weird question: I'm writing my own programming language. I am parsing tokens from the src file to a string array (java). I have a methods that do stuff based on the token. (So say the token is "+", I have an add method. Currently, I'm just using if(token.equals("+") { add(); }. But then I'll have a million of these. Is there a bettter way?

Anonymous

Switch statement?

^

That's what I would use

Anonymous

Or transpile

Anonymous

But transpiling may be difficult depending on what type of language you're making

6:20 AM

@Downgoat whoops, forgot to increment version

@Mego okay now I feel like a total idiot.

This is what happens when you program at 10:30

=/

I also couldnt figure out why String s ="+"; if(s=="+") wouldn't work right.

Anonymous

Man it's 00:21 here

Finally got it.

Lol I'm CA

Anonymous

The answer is because Java is dumb

Well thank you.

It is true though. Why don't they add that darn functionality. I mean how many programmers have made that mistake (comparing strings as primative types?)

I mean if I can assign a String as a primative String s = "primative thingy". Why can't I compare it as such. if(s == "primative thingy") System.out.println("java isn't that bad");

6:24 AM

import javahate
print("Oh, but it is that bad. :P")

LOL

that's not right.

¯\_(ツ)_/¯ I've had very limited exposure to Java.

Well I've had limited exposure to everything

including radiation?

yes. Including radiation.

6:25 AM

Limited exposure to radiation is a good thing...

Well

Hulk?

@AshwinGupta define everything

No exposure is better

uv radiation is good

everything= programming languages and anything you learn past 8th grade

6:26 AM

every programming language?

I know java

brainfuck? smbf? lenguage?

and a bit of python

thats it.

I've heard of brainfck. I know all the commands. I have never written a brainfck program.

/me knows c#, js, a bit of python and html

kinda know jelly

cool.

6:27 AM

jelly is pretty much the only language i've golfed in

The thing is, I'm teaching myself code. So what I know comes from the book: Java A Begginer's Guide

@AshwinGupta same as me

cool. I love that book.

well, except I haven't used java yet

uh

@AshwinGupta Are you familiar with Codecademy?

6:28 AM

LOL

@AlexA. yeah. I did the JS tutorial on it a while back.

*all i know about code is self-taught/from SO

I love that site too. I ought to do the python one.

I did the Python one a long time ago. It was good. :)

@somebody finally.. someone who understands :D

I'll probably do it then Alex.

I think they've added even more languages recently.

IIRC they have Java as well now.

6:29 AM

Oh okay neat.

Anonymous

My langs: [C, C++, Java, Python, VB.NET, C#, HTML, JavaScript, PHP, Seriously, Boo]

When I was on it they had like python, JS, ruby, and php.

basically the first thing i did in python was translate shtriped from node

@AshwinGupta Same

Think I should learn C++. C# or something else next. I want to do windows desktop applications and video games(for fun not for distribution)

6:30 AM

@Mego Is Boo used? I heard some hype about it a while back but haven't really seen it in the wild.

@AshwinGupta C# is a good choice for Windows. Actually, the Unity game engine uses C#.

Anonymous

@AlexA. Not really. It's neat because its syntax is like Python's, but is a .NET language

So I've heard. Cool thanks.

Anonymous

(and is not at all the same as IronPython)

C# is almost the same as java, just only for windows (unless you use mono), and implements/extends -> :

I actually like C# better than Java (from what I know about Java).

6:31 AM

Actually people I'd better be leaving now. Its 10:30 and I've finished my HW and I got school tomorrow.

Okay. Have a good night!

I'll be back eventually. Just not for a while since I've got like a billion projects.

Cya

Anonymous

I'm tempted to play some Civ, but it's already after midnight

What's Civ?

Anonymous

Civilization V

6:36 AM

Oh

I

see

Anonymous

Relevant to the chatbot madness going on around here:

Anonymous

xD

Marky: "I'm not sure you're a good idea." Me: ԅ[ * ༎ຶ _ ༎ຶ * ]┐

7:16 AM

whoops, forgot i broke chat , fixed userscript (again)

Quill

> cheap flights australia

lol

I heard Australia

Go to Yahoo! Answers. You won't get any "malicious ratings" in there. Good luck! — Shadow Wizard 3 mins ago

7:35 AM

The Mobile World Congress (with plenty of live streaming) is about to start, if you're into cutting edges and stuff.

(they have robot dogs... cc@AlexA)

Optimizer

7:52 AM

@Calvin'sHobbies any schedule for that live stream?

@Optimizer The first keynote should start in 20 min (see mobileworldlive.com/mobile-world-congress-keynotes) and I guess you can watch it here but I'm not certain

Q: Comparing five integers in C

8:17 AM

:D shtriped now can be translated to python via python (mostly)

it is also now in python3

New Main Posts

0

In C, where given five integers as input, display each in the order entered by the user with the character '>', '<', or '=' in between each pair of numbers that represents their relationship. The Catch None of the following can be used: Loops, if statements, logical operators, relational operat...

c function integer

@Optimizer Hmm, maybe you need to be signed up for the event actually :/

Optimizer

today's events seems uninteresting..

8:34 AM

/me needs help translating shtriped to python

nonlocal detection is broken D:

also, toPython() is unreadable

Quill

@somebody Need a hand with something?

idk, wait a second

@somebody Once I actually finish the readme it may be easier to make sure things are working in your version :P I promise it's coming soon

it's working

it's just that i'm really bad at writing a translator

@zyabin101 the userscript works in firefox

zyabin101

@somebody I know.

8:50 AM

oh

my bad, was looking at Atom feed

VoteToClose

Any last comments?:

1

Surrounding Countries code-golfkolmogorov-complexity Ever wonder what countries surround another? I do too, sometimes, and, well, here's the challenge for it. I have provided a list of countries and the countries that they touch that you must recognize at the bottom of this post in a code bloc...

Adnan

9:13 AM

@quartata That is correct, you can also visualise this with the debugger: 05ab1e.tryitonline.net/#code=MyA0Kw&input=&args=LWQ

The debugger is kinda weird and chaotic though :p

what is the userscript dark theme meant to be like?

Anonymous

@somebody By the looks of it, broken forever

@Mego is it meant to be dark background + light text?

Anonymous

@somebody As far as I can tell, it's meant to be a checkbox that does nothing

New Sandboxed Posts

9:44 AM

0

Create an unkillable Windows process code-golf In various versions of the Microsoft Windows operating system, it is possible for a process to enter a state where it cannot be killed by the 'End Process' feature in the Task Manager. Your goal is to create a user-mode program that enters such a s...

@feersum funny thing about this challenge: I've created an unkillable cmd yesterday when working on my tape-based language...

feersum

@Katenkyo Heh. Do you remember how you did it ;) ?

@feersum didn't really understood what happened, I used ./lua53.exe ./GoLua.lua(where GoLua is a temp name) and looks like it wasn't happy to not have a program filled in.

I should have had an Out Of bound exception (or global table is nil), but it didn't throw the error, maybe because it looked in the wrong place in memory

New Sandboxed Posts

11:37 AM

0

LaTeX Table Generator Write a function or program which, given a number of lines and columns, generates a corresponding tabular environment for LaTeX with no data in it. Table format and tabular Environment Here is an example of a table with 2 rows and 4 columns: As you can see, we do not c...

New Sandboxed Posts

2:23 PM

0

Substitution Cipher Programming A substitution cipher maps each unique character text of string to another character. If my substitution cipher is [H->6, e->U, l->V, o->)], then Hello becomes 6UVV). You must write a program A, which takes A as input, and prints out a B, after having passed it ...

I'm planning on posting this in an hour or two, anyone have any last minute advice, criticism, etc? It's my first challenge.

4

When will I have a binary car? code-golf I noticed that my car's odometer was at 101101 when I got to work today. Which is a cool number because it's binary (and a palindrome, but that's not important). Now, I want to know when the next time I'll have a binary odometer reading. Now, I can't rea...

@MorganThrapp Sounds like a good one, I love the Idea

I think I'll start working on it before it get posted, sounds fun to do ^^

@MorganThrapp do you have a test case that hits a binary number before the sequence is finished?

(for the first time)?

I don't, but I'll make one.

also, I'd say that the program can assume that the sequence will eventually land on a binary number

2:34 PM

Just added one. Yeah, that's in the spec.

> The odometer will always eventually reach a binary state.

@NathanMerrill it is already specified :)

cool :)

ninja'd

the term is now Geobits'd

So would you say it's in a good state to post? It's my first challenge, so I want to make sure I'm not messing up anything obvious.

2:40 PM

@NathanMerrill I though it was bearmonkey'd ^^

@MorganThrapp I think it is

@NathanMerrill You can lowercase that if it's officially verbified now :P

GOOD MORNING COMPADRES

Top o the morning to ya, comrade.

@MorganThrapp I don't get the new challenge

@orlp The one I just posted? What don't you get?

2:49 PM

101101 + 229*27 = 107284

@orlp Huh. I may have done that math wrong. Let me fix the test case.

@orlp It would actually be 458*27, because each day is two steps, but that math is still wrong.

Q: Let's play Yatzy - in 1 Minute

wait

so the array of 10 elements represent the distances you travel on

New Main Posts

0

Let's play a few games of Yatzy. For those who don't know this game of dice, you need to fill a sheet with a certain combinations of numbers. Each round consists of up to 3 throws, you can lock any number of dice. If all 5 are locked, you need to write the result down. If you can't write it down ...

code-challenge

3

Q: When will I have a binary car?

I noticed that my car's odometer was at 101101 when I got to work today. Which is a cool number because it's binary (and a palindrome, but that's not important). Now, I want to know when the next time I'll have a binary odometer reading. I can't read the odometer while I'm driving, because that w...

code-golf sequence binary

monday morning, monday evening, tuesday morning, tuesday evening, etc..

@orlp Yes.

I just fixed the test case, it should've been 165

So, 165*2*27+101101 == 110011. (Which keeps it a palindrome. :D)

TimmyD

2:59 PM

@MorganThrapp I get 22.5 days for your second test case

@TimmyD Huh, let me check it.

I can confirm

1 + sum(([13, 25, 3, 4, 10, 8, 92, 3, 3, 100] * 100)[:45])

Yeah, looks like you're right. I'm not sure what I was on when I came up with those test cases. :P

@MorganThrapp Couldn't check them because I was using lua's online compiler, which abort the process if there's to much loops ^^

3:45 PM

is there concepts of "due dates" in multi-process programming? (think libraries)?

basically, we give you a period of time to use a resource, and, if at the end of that period of time, anybody else is waiting on that resource, then you have to give it up?

Like a "timed" lock?

New Main Posts

0

Q: Sum of Binary Substrings

This challenge is simple, given a decimal number, convert to binary, and calculate the sum of the sub-strings of the binary number, whose length is shorter than the original number. Here is an example: Input: 11 Binary: 11 -> 1011 Substrings: 101 = 5 011 = 3 10 = 2 01 = 1 11 = 3...

code-golf binary

TimmyD

Ahahaha ... we had a remote office go down in the middle part of last week, and our network team spent several days (and over the weekend) trying different things, contacting the ISP, swapping modems, etc. ... Turns out that the DSL account was past-due and so they suspended service. The bill was paid this morning and "magically" the site is back up.

@NathanMerrill I think, if your operation are atomic, you could set that up (ie, operation using X more than Y minutes are reversed if not finished).

@TimmyD Geniuses...

But you need your threads to know that they don't have the lcok on the ressource anymore

Eridan

If you want to represent pi using only positive integers (and you want those positive integers to remain relatively small while having an accurate value of pi), would continued fractions be the best way to do it?