The Nineteenth Byte

ASCII-only

10:15

@LeakyNun yeah. click "see full text"

>_> i'm an idiot

Erik the Outgolfer

no

ninja

ASCII-only

@LeakyNun
https://tio.run/##1Vtbb9s4Fn62f4Wmg2Dk@BJSStKJtymwWGCf/LLAPLQwPIFry4lQx/ZK8jb59V0ekqLJ8zHXabvdFq0i8ujwkDyX7ztFd/fNzXaTfy1vd9uqSar5Zrm97dq3zf52d99tirqpL6dTMbC/ZwP3s3Q/S29cunHpyUtPXnry0slLT7/09EtPv/T0S0@/9PRLT790@qVnv/Tsl5790rNfevZLz37p2S89@6Vnv/Tsl5790rNfevZLz37p2S89@935BzcggjkZ3k54P8ENhXfHbi@8v@AGRTAnw9sN7ze44fDu2e2H9x94gAjmZOgdoX8EHhL6DvOe0H8CDxLBnAy9K/SvwMNC32PeF/pf4IEimJOhd4b@GXho6LvMe0P/DTxYBHMy9O7QvwMPD32feX/o/0EEiGBOhtERxkcQIWHssOgJ4yeIIBHMyTC6wvgKIiyMPRZ9PP5YBAo2L3mE8hhlUcpjGKKYxzGLZJaHWTTzPMAzAeYCyAY8H7CMINi85BmD5wyWNXhOgazC8wrLLKyusOzC8xLPTJibIDvx/MQylGDzkmcwnsNYFuM5DrIcz…

Leaky Nun

ok now what

ASCII-only

(i still haven't started my own solution though >_>)

Leaky Nun

oh, you included correlation coefficient

ASCII-only

10:40

wait what

pinnochio has an emoji

orlp

@LeakyNun how are you?

Leaky Nun

i'm fine

orlp

done with exams?

I have two left

Leaky Nun

done

orlp

nice

went well?

Leaky Nun

10:48

@orlp i made this

sure

orlp

let me see

that's some messy code kenny :D

@LeakyNun in my complexity class I learned something that I didn't realize so far

you've heard of NP, NP-hard, NP-complete and such before, right?

ASCII-only

@orlp mfw i find out optimization expert is still in Uni (?)

orlp

@ASCII-only I'm doing 6 years for a 3 year study :P

health issues

Leaky Nun

@orlp right

@orlp look at the improvement

orlp

@LeakyNun that's a nice improvement :D

@LeakyNun quick refresher on NP: it's the set of problems that given a polynomial-space candidate solution you can verify whether it's correct in polynomial-time

e.g. you can verify a n^2 proposed sudoku solution correct in n^2 time

all these problems have a "non-deterministic polynomial time" algorithm: which is essentially guess and check

nevertheless they're very hard to solve, guess and check on sudoku is going to take you a while

now the part that I didn't realize what it truly meant is NP-hard

@LeakyNun if problem X is NP-hard means that given any NP problem Y, and a polynomial time instance translation T, that X can solve Y after transforming the problem with T

that's the part I didn't realize, and how crazy that is

NP-hard problems are essentially universal computers for any problem that is in NP

Leaky Nun

11:00

hmm

interesting

orlp

e.g. you can use subset-sum to sort an array of numbers

that seemed a bit ridiculous to me at first, but it made sense after reading some more

ASCII-only

(and that's why proving P=NP means you can use the solution to that to do any NP-hard (?) problem in polynomial time (i remember reading something like this somewhere) or w/e right?)

orlp

@ASCII-only please wait a moment

@LeakyNun the simplest problem to see that is NP-hard is simply "does this turing machine halt"

but that's not very useful

the interesting category of problems is NP-complete

those are the problems that are not only NP-hard, they are in NP themselves

the first problem that was proven to be this way is SAT

by essentially translating a turing machine that runs N steps into a boolean expression

every other problem is most often proved NP-complete by showing that it can solve SAT, and that SAT can solve it

(all again with at most polynomial T translation time)

(or proving it NP-complete by reducing it to a problem already shown NP-complete but most of the time you end up at SAT through a chain of reductions)

@ASCII-only P is the set of problems solvable in polynomial time

straight up

e.g. sort an array

now the crazy part is, if you can solve a problem in NP-complete in polynomial time

you've shown you can solve them ALL in polynomial time

and since they're NP-hard, you've shown you can solve ALL NP problems in polynomial time

in other words, P = NP

which means that if you can check whether an answer is correct in polynomial time you can find a solution in polynomial time as well

Leaky Nun

I see

orlp

@LeakyNun in our exam we had an interesting problem

Independent set (graph theory)

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in S. The size of an independent set is the number of vertices it contains. Independent sets have also been called internally stable sets. A maximal independent set is either an independent set such that adding any other vertex to the set forces the set to contain an edge or the set of all vertices of the empty graph...

given a graph G = (V, E), does there exist an independent set (without any connections between them) of vertices of size m?

that's as hard as 3SAT (SAT of the form (x1 || x2 || x3) && (x4 || x5 || x6) && ...)

which is as hard as SAT

Leaky Nun

11:09

surely we can just brute force it... :D

we should all just solve the travelling salesman problem in polynomial time

ASCII-only

@LeakyNun i think he means "hard" complexity-wise?

Leaky Nun

lol

orlp

11:59

@LeakyNun I have an idea for an optimal algorithm, let's see if it's feasible

Leaky Nun

for what?

orlp

8

A: Block partition a string

Python 3, (0.397 n + 3.58) steps 1000-point polynomial regression by numpy.polyfit. Number of steps for version 1: 0.0546 n² + 2.80 n - 221 Number of steps for version 2: 0.0235 n² + 0.965 n - 74 Number of steps for version 3: 0.00965 n² + 2.35 n - 111 Number of steps for version 4: 1.08 n -...

Leaky Nun

oooh, a competitor!

orlp

well either I destroy the competition

or it doesn't work :P

orlp

12:22

@LeakyNun (0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1)

Leaky Nun

?

orlp

your solution gives [24, 12, 17, 7, 20, 7, 23, 8, 9, 12, 13]

but misses [6, 5, 6, 9, 10, 7, 8, 10, 11] :)

Leaky Nun

:o

I'm busy these days

orlp

me too :(

it's not feasible though

at least not 500

unless I improve something

@LeakyNun what is the strongest admissable heuristic you can think of for the number of moves needed to solve an instance

admissable means it never overestimates the number of moves

right now I have this:

def h(l):
    """Number of groups of 1 with length <= 3 that come before a zero."""
    h = 0
    num_ones = 0
    for x in l:
        if x == 1:
            num_ones += 1
        else:
            while num_ones > 3:
                num_ones -= 3
                h += 1
            if num_ones > 0:
                h += 1
            num_ones = 0

    return h

the stronger I can make this heuristic the faster it will run

Leaky Nun

so what does my solution turn it to?

orlp

12:25

@LeakyNun what do you mean?

wait a sec I'm an evil genius I can use your solution to power mine mwuhahaha

Leaky Nun

you said my solution is wrong right

orlp

@LeakyNun no, I said it was suboptimal

ASCII-only

@LeakyNun it's not wrong. it's just suboptimal

:| ninja'd

Leaky Nun

oh... I didn't try to design the optimal algorithm

I'm just using evolution

randomly trying new things until the local optimum is obtained

ASCII-only

@LeakyNun you could just bruteforce for smaller n :P

Leaky Nun

12:27

insignificant

ASCII-only

that's true

orlp

actually no wait I can't

@LeakyNun so you do you know ways of improving my heuristic?

to get an upper bound on the number of moves needed to solve an instance

right now my logic is that if a group of 1s comes before a zero that requires at least one move to solve

ASCII-only

> upper bound

> never overestimates

this doesn't make sense

orlp

eh

no

the highest possible lower bound :P

sorry

ASCII-only

i'd say you can only obtain a better lower bound by understanding how exactly the optimal solution moves the runs of 0s/1s around

orlp

12:33

000000110110101011110101101
      ^ moved
000000110101011110101101110
     ^ moved
000000101011110101101110011
      ^ moved
000000011110101101110011101
         ^ moved
000000011101101110011101110
          ^ moved
000000011101110011101110011
       ^ moved
000000001110011101110011111
        ^ moved
000000000011101110011111111
          ^ moved
000000000001110011111111111
           ^ moved
000000000000011111111111111

there, clearer

Leaky Nun

@orlp why don't you decode my code and explain to ASCII-only what my code does lol

orlp

@LeakyNun eh it's kind of a mess :P

not sure what it does

ok I see what the optimal code does

it makes groups of three ones

ASCII-only

@orlp or a multiple of three

orlp

@ASCII-only that's just two groups of three :P

ASCII-only

true

orlp

12:37

(or more)

ohh I have an idea

it's all about the final suffix of the string

and what you can append to that

so the string 00100 always requires at least two moves to solve if it comes before a 1

ASCII-only

@orlp doesn't this require only 1

Leaky Nun

lol

@orlp that's the tail in my code

orlp

sorry I meant in the bigger picture

ASCII-only

ok so: i think a better lower bound would involve counting the number of pairs that join to make a run of 3 or something like that. (not sure what to do with pairs that don't do so though) (i.e. this would work fine with a string with n occurrences of 1 and n occurrences of 11, but doesn't work in any other situation)

(unless you consider some of the 11 as 2x1 maybe?)

(and you can join 2x1 together, and exclude a block of length length % 3)

AdmBorkBork

12:56

Any final comments on Upper or Lower Wythoff before I post it?

orlp

wow @LeakyNun

0000001101101010111101011010010
     ^
0000001101010111101011010010011
         ^
0000001100111101011010010011101
      ^
0000000111101011010010011101110
             ^
0000000111101010010011101110011
              ^
0000000111101010011101110011100
               ^
0000000111101011101110011100001
         ^
0000000111011101110011100001110
       ^
0000000011101110011100001110111
        ^
0000000001110011100001110111111
         ^
0000000000011100001110111111111
           ^
0000000000000001110111111111111

look at this optimal solution

multiple times it actually splits 111 groups

albeit in a way that makes a new 111 group

Leaky Nun

is this your solution or my solution?

orlp

mine

Leaky Nun

what does my solution make?

orlp

it's optimal

guaranteed

Leaky Nun

12:58

sure

but I'm still curious

orlp

sec

0000001101101010111101011010010
                           ^
0000001101101010111101011010001
                          ^
0000001101101010111101011001100
           ^
0000001101110111101011001100010
                ^
0000001101110111011001100010101
                     ^
0000001101110111011000010101110
        ^
0000001110111011000010101110011
                    ^
0000001110111011000001110011101
              ^
0000001110111000001110011101110
      ^
0000000111000001110011101110111
       ^
0000000000001110011101110111111

Leaky Nun

only one step more?

orlp

yes

although your first two steps are very questionable

Leaky Nun

yay

orlp

make that the first 3 steps

HyperNeutrino

13:00

obtw @Downgoat fixed green-on-blue colorscheme to neutral+monochromatic (here)

Leaky Nun

@orlp make that all the steps

ASCII-only

@LeakyNun ~~through mathematical induction~~

Leaky Nun

bingo

orlp

@LeakyNun no that's a different game :P

Leaky Nun

lol

New Main Posts

13:24

0

Q: Upper or Lower Wythoff?

First, let's talk about Beatty sequences. Given a positive irrational number r, we can construct an infinite sequence by multiplying the positive integers to r in order and taking the floor of each resulting calculation. For example, If r > 1, we have a special condition. We can form another ir...

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Quine of Hanoi Objetive Make a program that print a rearranged version of itself Rules Your program will consist of newlines and 3 blocks : A, B and C where each block will have distinct and nonzero lengths, i.e. 0 < length(A) < length(B) < length(C). The output will be based on the order ...

New Meta Posts

14:05

0

Q: Solutions Using Golfing Languages: Should Decomposition Be Required?

There are a number of programming languages that seem to be specifically designed for solving code-golf problems (05AB1E and Jelly immediately come to mind). Should providing a "decomposed" explanation be required, or at least strongly encouraged, as part of the answer? By '"decomposed" explanati...

discussion

Luis Mendo

14:26

@EsolangingFruit Thanks for the edit!

Pavel

At my school, the firewall keeps switching between blocking gmail and blocking hotmail, but never both at the same time.

user202729

@orlp Guess I have to quickly finish my answer.....

... you already finished it?

Zacharý

14:42

@Pavel RIP

Nathan Merrill

Is there a golfing language out there with list support that doesn't support sublists?

user202729

What is sublist?

Nathan Merrill

taking a list, and returning only a part of it

[0,2,3,4,5].sublist(1,3) -> [2,3,4]

Esolanging Fruit

CJam supports e[:n] and e[n:] but not both at the same time

user202729

Same for Jelly.

Nathan Merrill

14:45

fair enough

that's still a sublist operation

Esolanging Fruit

There was a list of golfing languages hosted somewhere on GitHub, but I can't find it

Cows quack

github.com/ETHproductions/golfing-langs possibly?

Esolanging Fruit

yep

Erik the Outgolfer

@user202729 cough cough Ẇ cough cough cough

Gabriel Romon

yo, quick easy question but I'm a noob with regex... Can someone write a string that matches ^abc\bd? I'm wondering why abc d is not matched...

user202729

14:52

@EriktheOutgolfer Ah...

Erik the Outgolfer

well, it's still not quite the same thing, but eh

user202729

@GabrielRomon \b is zero width.

@EriktheOutgolfer But... if you have a list you should be able to somehow decompose it.

Erik the Outgolfer

\b is word boundary

"decompose it" is subjective

user202729

@EriktheOutgolfer Hm...

Right. You can have index and not sublist and it's still very functional.

Esolanging Fruit

@NathanMerrill Seems like Arcyóu doesn't. It's a Lisp, so it obviously supports lists, but afaict it has no "sublist" operator

orlp

14:54

@user202729 no my idea isn't feasible

for larger strings

user202729

@orlp What's its asymptotic complexity?

orlp

@user202729 exponential

user202729

Well at least I had some motivation to quickly finish my solution...

Gabriel Romon

@user202729 so there's no string that could match ^abc\bd, right ?

Nathan Merrill

@EsolangingFruit github.com/Nazek42/arcyou/blob/master/arcstdlib.py

_index_slice

user202729

14:56

@GabrielRomon correct.

Nathan Merrill

hmmm, it appears that that code is unused?

orlp

@user202729 my algorithm is optimal though

Gabriel Romon

@user202729 thx

user202729

@orlp "exponential but not too bad"?

orlp

@user202729 that was the hope

AdmBorkBork

15:09

CMC: Given an input integer, bubble-sort its binary representation, outputting every number generated along the way. Example: Input 12 0b1100, output 12, 10 (0b1010), 9 (0b1001), 5 (0b0101), 3 (0b0011)

Erik the Outgolfer

VTC: unclear

> bubble-sort

?

Pavel

Bubble sort is a well-known sorting algorithm

Erik the Outgolfer

but why do I need to bubble-sort and not just sort

Pavel

Because you're outputing the result of each step

Erik the Outgolfer

oh wait now I see

AdmBorkBork

15:11

To get the right numbers in between

Erik the Outgolfer

ninja

AdmBorkBork

very much so

Erik the Outgolfer

then shouldn't the output be 12, 10, 9, 5, 3, 3?

AdmBorkBork

Yeah, could be.

Erik the Outgolfer

or do we bubble-sort in a different sense?

that would be the output if we don't consider how many iterations of bubble-sort we have already done

and, tbf, that couldn't be the output either

well, it would, if we do take the iterations into account

if we don't, then the output would be 12, 10, 9, 5, 3, 3, 3, 3, 3

but your given output is surely invalid

AdmBorkBork

15:15

*output every unique number generated along the way

ftfy

:p

Cows quack

anaother example?

AdmBorkBork

Uh, sure. I rolled that one by hand so let me create another.

orlp

@user202729 and your idea?

user202729

My idea?

I think I will post an answer first...

orlp

I mean is it optimal?

user202729

15:20

I don't think so.

AdmBorkBork

@Cowsquack input: 21, output: 21 (0b10101), 13 (0b1101), 11 (0b1011), 7 (0b111)

Cows quack

does output have to include the first number?

AdmBorkBork

No, I don't suppose so

Cows quack

bash, 44 bytes, Try it online!

still clunky

-2 bytes if the last number can be repeated (by removing ;d)

and another 2 if the sed version is ≤4.2.2 by removing labels

AdmBorkBork

What's with the close- and down-votes on the NMP? Tips for golfing a specific question are on-topic.

Erik the Outgolfer

15:29

it's very unclear, and it looks a bit effortless too

AdmBorkBork

"Here's some code. Any tips for golfing this code?" How in the world is that unclear? I can see your second point (effortless), but I can't understand how it's unclear.

Erik the Outgolfer

what is the code for?

can't know for sure, maybe it's a case of the XY problem

user202729

@AdmBorkBork Explained in a comment.

What I can say: The whitespaces looks very weird, especially consider that OP use 1-character for every variable name (except the function name?)

FrownyFrog

on codefights whitespace doesn't count

user202729

@FrownyFrog If it's true that needs clarification.

FrownyFrog

15:35

solutions often use tabs and spaces for functional code

Dennis

@AdmBorkBork We can only deduce what the code does, not what it is supposed to do.

FrownyFrog

I don't know how exactly

Erik the Outgolfer

@FrownyFrog does Whitespace count? ;)

AdmBorkBork

@EriktheOutgolfer Oh. That's a good point, I hadn't considered that.

user202729

Right.

FrownyFrog

15:37

@EriktheOutgolfer there's a list of languages you can use

cuz automated tests

Erik the Outgolfer

good thing, because history tends to repeat itself

New Main Posts

0

Q: Any golfing architect in c#?

int z, c; int distance(int[] t, int e) => t.Max(x => e < 0 ? 0 * (e += t[z++]-x) : ++c); Any tips for golfing this?

code-golf tips c#

user202729

CMP Which font do you use for terminal?

(don't tell me that you don't use a terminal :/)

Erik the Outgolfer

obvious answer: Ubuntu Mono

AdmBorkBork

Lucida Console

Adám

15:52

@user202729 cmd.exe: DejaVu Sans Mono; PuTTY: APL385 Unicode.

Erik the Outgolfer

@AdmBorkBork terminal ≠ cmd

wait, do you use that for a terminal

AdmBorkBork

PowerShell ISE

it's the closest equivalent

(that I use)

Adám

@user202729 Define "terminal".

Cows quack

@user202729 menlo

FreezePhoenix

Whatever font the terminal uses

Adám

15:59

@user202729 For APL2: Courier APL2 Unicode

@user202729 For APL\360: apl360i

Dennis

@user202729 DejaVu Sans Mono, same as TIO.

@EriktheOutgolfer I use Ubuntu for everything else, but I need better Unicode support in the terminal.

Thomas Ward

hands @Dennis a better Unicode-compliant font and a profile that configures the terminal to be UTF-8

less the terminal not supporting UTF-8, but your locale and terminal fonts not supporting it :P

user202729

@LeakyNun Ok, my solution gives 239 moves. I lose.

Leaky Nun

@user202729 still, you improved a lot

HyperNeutrino

does anyone here know jinja2

I want to know if there's a directive to force a block to re-render

although I doubt that's possible because it's all rendered at the start

user202729

16:10

My solution: (I can't post it right now, see line 65) (very slow too, probably O(n³) or something)
https://tio.run/##rVVbb9owFH4mv8LrJEgUQoP6MpE4U7Wi7WHqy7SnbopM4hCrwUaO08sov72zfRIwpXsbpZBzv33nUGy30booXl8/Ml40XUlTJlolKdlk3oH1QAslpMPoFGuYenY4pFkLyVTtmvFuQyUrMs/THrtCIcYrkatdx1u25rREDeXTttvkjJesoG2yT7yVEA0SWyqJjpj6YIHItH9YBTtvJKnqJEdkpu0/4JX5@myJ1D4vyMxxmq1cKvH26PISNUSuqbT5IL8ntCUivETthjSNprUV6q0CRCRFK6oUlZ7Xp7KhpO0k9VtVLhbQobSoicxQIXirxqgkiph03XJx7BaM48QbVUL6BxWmWSw1lrOW/aF@kBgPI1b5hnfHfmMcW84oDLW7xDw5DkPMEhDa7z1tWmq1WYivLMcz776Buzf91@3fe96DYLoJNavUeWlQ1PSYrsnFakmhiKI2y9mKrhn3g5BNT8nwChiUl34Q…

This can be improved.

My observation:

Every move operation does not change the position of each block modulo 3.

(spoiler ^)

HyperNeutrino

TIL you can dynamically modify the stylesheet of a site by doing something like element.href = "something" (where element is likely document.getElementsByTagName("link")[0])

Riker

@user202729 AFAICT, it means "Given a number being the product of two primes, decompose it into the two primes in polynomial time".

the latter bits of the thing tell you "I don't know if this is solvable"

it definitely falls under off-topic for that reason.

Mr. Xcoder

@user202729 Andale Mono 13pt

Riker

you're assuming his "assumption" part, which doesn't really work. plus, I don't think OP has a solid grasp on what exactly he's asking for

@Cowsquack when does school end for you wut

i've been out for like 3 wks, local HS just got done yesterday

Pavel

16:30

I'm out next Thursday

We had snow days so it was supposed to end today

orlp

@LeakyNun you know what's kinda cool about my solution?

(although it's infeasible)

FreezePhoenix

@orlp what

orlp

it can produce not only the optimal solution

it can produce the lexicographically first one

110110101011110101101001001
''''''''''  '''''^''''''
110110101011110101001001110
''''' ' ''  '' ' '' '^
110110101011110101001110001
''''''''''  ^''''''
110110101011101001110001110
''^'' ' '     ''
110101011101001110001110011
'''^''     ''
110011101001110001110011101
^''     ''
011101001110001110011101110
     '^
011101110001110011101110001
 '   '     '    '   ^
011101110001110011100001111
 '   '     '    ^
011101110001110000001111111
 '   '     ^
011101110000000001111111111
 '   ^
011100000000001111111111111

Leaky Nun

ok

orlp

' mean it considered that position

^ means it chose that position

Leaky Nun

16:32

I see

orlp

in this case it's lexicographically biggest

FreezePhoenix

Why you posting that big thing

orlp

to talk about it

FreezePhoenix

7

@orlp Its a big thing. How are you going to talk about it all in one day?

Erik the Outgolfer

uh, it's not very kind to confront people just because they're talking

FreezePhoenix

16:42

:P It was a big block

Erik the Outgolfer

still, you don't have to comment on how people talk...they just talk, and, if you're not really interested in a part of their discussion and just make comments about it, that contributes next to nothing in here, and is unnecessary and unkind

Cows quack

@Riker oh not in that sense, I meant finish 12th grade

DJMcMayhem

17:05

→ 4 messages moved to Trash

Sure

Mr. Xcoder

The CMC widget doesn't work at all anymore >___>

dzaima

@Mr.Xcoder because a-ta.co hosted it AFAIK (and ataco lost the code for it)

Mr. Xcoder

Ugh :(

I will uninstall it, then.

Soaku

17:43

@Mr.Xcoder It doesn't work for a while already

the same goes for "I'm typing"

Zacharý

Wait ... Java 10 has var?!

Cows quack

CMC: Given a string that is the unary representation of an integer (negative integers have a - at the start), return the number it represents. You can choose the repeating char ##### => 5, -111 => -3, !!!!!!!!!! => 10, <empty string> => 0

note, this is essentially the reverse of chat.stackexchange.com/transcript/240?m=45066277#45066277

DJMcMayhem

17:59

@Cowsquack Painfully long, but V, 12 bytes

Transcript for