The Nineteenth Byte

Mr. Xcoder

08:00

Like my new profile pic?

(from PPCG only)

Lembik

@Jim did you downvote?

Jim

@Lembik No I didn't

Lembik

ah ok.. I wouldn't have blamed you if you had

@Mr.Xcoder I don't

hence the question :)

Mr. Xcoder

@Lembik Nor did I

Lembik

interesting

thanks

Mr. Xcoder

08:03

Probably a raging downvoter like on my question

Lembik

:) a great phrase!

Mr. Xcoder

I should become a poem writer.

Or poet

@Lembik Why do you only post challenges on PPCG, and avoid answering?

Lembik

@Mr.Xcoder it's an interesting question

Partly because I have no interest at all in esolangs

Mayube

you don't have to answer with esolangs though

Mr. Xcoder

I am not interested in esolangs either

Lembik

08:07

partly because I have very limited time

Mayube

PHP, Python, JS, Haskell, Bash, C, Java. All non-esolangs that are used in PPCG

Lembik

partly because one of the things I enjoy about *.se is the amazing power of the crowd

that is that you can get really high quality answers from a group of unpaid volunteers

I also have no interest in code-golf :)

Mr. Xcoder

@Lembik I put a bounty on your 2014 question, because that answer by @PeterTaylor Was amazing

Lembik

@Mr.Xcoder thanks ! I have had a very incredibly awesome answers over the years on PPCG

Mr. Xcoder

I see, but that one was far too great to only have 9 upvotes... What a shame

Lembik

08:13

can you link it here?

we could upvote :)

Mr. Xcoder

30

Q: How high can you go? (A coding+algorithms challenge)

Now that everyone has developed their (often amazing) low level coding expertise for How slow is Python really? (Or how fast is your language?) and How Slow Is Python Really (Part II)? it is time for a challenge which will also stretch your ability to improve an algorithm. The following code c...

Second answer

Lembik

Reimer Behrends's answer is even better

Mr. Xcoder

10

A: How high can you go? (A coding+algorithms challenge)

Java (n=22?) I think most of the answers which do better than n=16 use a similar approach to this, although they differ in the symmetries they exploit and the way they divide the task between threads. The vectors defined in the question can be replaced with bit strings, and the inner product wi...

Ok, I will go now :P

Lembik

:)

@isaacg hi.. are you here?

isaacg

Yep

Lembik

08:17

@isaacg could you explain to a sleepy me how brute force would work? It seems you would have to try 33333300001 integers wouldn't you?

isaacg

For the input 50000000002, you try 1 as an inverse, then you try 2 as an inverse, then you're done.

Oh, you changed that. OK, then it seems good.

Lembik

great!

I was confused :)

isaacg

I'll remove my comments now that they're fixed, to reduce confusion.

Lembik

thanks

Newly Featured Questions

32

Q: How high can you go? (A coding+algorithms challenge)

Now that everyone has developed their (often amazing) low level coding expertise for How slow is Python really? (Or how fast is your language?) and How Slow Is Python Really (Part II)? it is time for a challenge which will also stretch your ability to improve an algorithm. The following code c...

code-challenge fastest-code

isaacg

08:26

I have a challenge out that's unanswered, and it's fallen off the first page of active questions. Would it be appropriate for me to bump it?

Lembik

why not :)

Mr. Xcoder

@isaacg Put a bounty on it

isaacg

Fair enough

Mr. Xcoder

9

Q: Calculate Treewidth

The treewidth of an undirected graph is a very important concept in Graph Theory. Tons of graph algorithms have been invented which run fast if you have a decomposition of the graph with small treewidth. The treewidth is often defined in terms of tree decompositions. Here's a graph and a tree de...

code-golf graph-theory

This one?

isaacg

Yeah

Bounty placed

Mr. Xcoder

08:33

I upvoted it in both the sandbox and on Main, but it fells so long and hard... Who knows, maybe you'll get an answer

isaacg

It's 15 lines of Python, I don't think it's that bad. Maybe that's just mode than people want to golf?

V. Courtois

Quote for a comment on my yesterday's post :

"KISS. This is far more complicated than common sense would require. Deliberately overcomplicating things to make it "more difficult" is a guaranteed method to make a bad question."

Mr. Xcoder

@isaacg Can I golf the script there?

And post an answer :)

V. Courtois

is it real ? I thought it was some purpose of PPCG to make difficult things

Mr. Xcoder

@V.Courtois No purpose.

isaacg

08:36

@V.Courtois Which post? I can give you more details/a second look.

V. Courtois

sry

-1

A: Sandbox for Proposed Challenges

Random lennyface selector Your mission Create, in the language of your choice, a program that outputs a randomly selected lennyface (artistic minifigures, see this) from a lennyface list. Rules Input : A list of lennyfaces and numbers (positive AND negative integers). Output (STDOUT for exam...

Mr. Xcoder

1 min ago, by Mr. Xcoder

@isaacg Can I golf the script there?

isaacg

@Mr.Xcoder Absolutely, that's why I posted that program.

Mr. Xcoder

Hmm, ok

Hope I won't be ninja'd

isaacg

@V.Courtois Basically, people tend to like hard questions better when the hardness comes from the core of the question, rater than when it feels added on afterwords.

In the question you posted, the core of the question is picking a random line from the program, but the hard part is parsing the input format.

V. Courtois

08:40

Yeah, ofc

isaacg

If you want the hard part to be parsing the input format, you should describe it that way, including in the title of the question and in the initial description of the problem.

That way, people understand what the problem's really about, rather than getting unpleasantly surprised halfway through reading it.

V. Courtois

I answered a challenge that has this feature too. So is that THAT bad? the challenge was fun and complex. I don't think KISS is on purpose when it comes to challenges.

Oh u mean I have to change the title?

Leaky Nun

@isaacg do you have any CMC?

isaacg

I've never posted one.

Let's see.

CMC: Calculate the log* of the input.

That's the number of natural logs you need to apply to the input until it falls below 1.

Iterated logarithm

In computer science, the iterated logarithm of n, written log* n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. The simplest formal definition is the result of this recurrence relation: log ∗ ⁡ n := { 0 if ...

V. Courtois

@isaacg is it better like this?

Jim

08:52

@isaacg Pyth, 14 bytes: W>Q1=hZ=Q.lQ;Z

Very procedural

isaacg

@V.Courtois Yeah, that looks better to me. One other important change: Rather than saying that chances of getting a lennyface is a sum, it would be better to say it is proportional to that sum.

Fatalize

@isaacg Brachylog, 9 bytes: ;.*₁ⁱ⁾≤1∧

isaacg

@Jim You can improve that type of program with f.

V. Courtois

sorry, you are right.

orlp

oops

isaacg

08:54

@Jim Also, you can leave out the second Q.

orlp

import math;f=lambda x:x>1and 1+f(math.log(x))

this is assuming it's ok to return False for inputs that are already <1, because False==0

isaacg

Yeah, I think that's fine, especially as a return from a function.

orlp

otherwise you need or 0

or even better

import math;f=lambda x:+(x>1and 1+f(math.log(x)))

that's only 3 extra characters :)

isaacg

:)

orlp

because of course

>>> +False
0

-False would work as well, but that unary + is always a bit more puzzling :)

Erik the Outgolfer

08:58

@isaacg Jelly, 9 bytes: Æl>1$Ð¿L’

for some reason Æl>Ð¿1L’ doesn't work

Mr. Xcoder

@isaacg Your code fails for the 3rd test case, it results in an infinite loop.

isaacg

If integer inputs are required/if a return of 0 is not allowed, then Pyth, 7 bytes: f>1=.lQ

New Main Posts

4

Q: Pad a matrix with its sums

Challenge: Given a square input matrix A, pad the matrix with one row and one column on all four sides. The value of each element in the top and bottom row should be the sum of the elements in each corresponding column. The value of each element in the left and right column should be the sum ...

code-golf number array-manipulation matrix

Mr. Xcoder

@isaacg I golfed it to death, but realised it's invalid.

I got down to 340 bytes

isaacg

@Mr.Xcoder Oh no! It worked when I tested it before. I'll check, sorry.

Mr. Xcoder

09:00

@isaacg On this line: graph = [edge for edge in graph if i not in edge] + [(a, b) for a in neighbors for b in neighbors if a < b]

isaacg

@Mr.Xcoder What's wrong about it?

Mr. Xcoder

It fails on this line

I don't know why, but that results in an infinite loop

isaacg

It works on my computer.

Jim

@isaacg I think I am missing a part, how do you perform log(log(log(…))) n times?

Mr. Xcoder

It doesn't on mine

isaacg

09:01

It completes in 17 seconds with the correct answer.

Mr. Xcoder

I'll check once more

Jim

@Jim To me: found it

isaacg

@Jim I'm doing the same thing you were, overwriting Q over and over again.

Jim

I think of using F inside f

Mr. Xcoder

@isaacg It terminated on my mac as well, after 45 seconds. Anyway, thanks!

isaacg

09:02

You're welcome.

orlp

@isaacg This weeked I'm going to make an implementation that can take a rational function and returns the sequence it's the generator function of

might be interesting for Pyth

isaacg

Absolutely

orlp

I have to do further investigation though

I know this can be done 100% with rational functions

but I want to know what the biggest set of functions (also for exponential generating functions and such) is so that you can always get an answer with available techniques

Stewie Griffin

@LuisMendo Thanks Luis! (a bit late reply :P )

Mr. Xcoder

How should I place a literal tab in my code to save bytes (in the StackExchange answer box)?

orlp

09:11

@Mr.Xcoder you can't

it will convert

Mr. Xcoder

How?

Place 4 spaces?

Jim

@isaacg I don't understand why f<Q1=Q.l loops forever

orlp

I mean you could copy/paste it

but it still converts to 4 spaces

but we understand that a tab is meant as 4 spaces

so don't worry about it

Mr. Xcoder

But I should count as tabs, right?

Ok, thanks @orlp

orlp

yes, you can score it as if it was a tab

Lembik

09:12

can I require that answers work on TIO in the future?

orlp

no

Lembik

boooo

isaacg

@Jim That parses as f<Q1 followed by other stuff. <Q1 is always true or always false, so f loops forever.

Lembik

it would make my life so much easier :)

Mr. Xcoder

Does repl.it work with itertools?

orlp

09:13

what's wrong with requiring that the program just... works?

isaacg

@orlp He was trying to rule out certain brute force algorithms, I think.

Lembik

@orlp because a) It's hard to run all the different code in different languages and b) what isaacg just said

orlp

just say an answer must be able to run on a reasonable consumer modern desktop pc in under 10 seconds

Lembik

@orlp people are very fussy about precision here.. they will say but what about this supercomputer I have on my desk and how can you verify I am not lying

orlp

that never happened to me

Lembik

09:15

ah ok that's good news

orlp

for example

11

Q: Evaluate modular power towers

Given two numbers n and m, evaluate the infinite power tower: n^(n+1)^(n+2)^(n+3)^(n+4)^... mod m Keep in mind that ^ is right-associative. So 2^3^4 = 2^(3^4). Now how can you possibly assign a value to an infinite sequence of right-associative operators? Define f(n,m,i) as the power towe...

code-golf arithmetic

Your program must be able to compute n = 2017, m = 10^10 in under 10 seconds on a reasonable modern PC. That is, you should implement an actual algorithm, no bruteforcing.

Lembik

that's cool

although I have noticed that some questions I have posed have been super popular and others with the same rules have been pilloried

it seems to depend on who reads it in the first hour after posting

Mr. Xcoder

Sometimes I forget exec and while exist, because I am used to for-loops :/

Lembik

exec I can excuse

Mr. Xcoder

@Lembik ?

Lembik

09:18

it's ok to forget exec is all I was saying

Jim

@isaacg Pyth, 7 bytes: f>1=.lQ

Mr. Xcoder

Was Q evaluated input in Pyth?

isaacg

Leave off the first Q, which is unnecessary, and you'll have the answer I posted.

@Mr.Xcoder Yes

Mr. Xcoder

@isaacg I've been trying (and failed) to learn it since May

isaacg

Sorry about that.

Jim

09:20

@isaacg Learnt a new builtin :)

Mr. Xcoder

@isaacg About what?

isaacg

Awesome!

Pyth being hard to learn.

Mr. Xcoder

@isaacg It ain't hard at all compared to 05AB1E or Jelly.

I just don't have the will to learn it till the end

Jim

@Mr.Xcoder I was going to ask

isaacg

Yeah, that's on purpose. I tried to make it comprehensible from the beginning. There's no harm in trying it out and learning from experience, though.

Erik the Outgolfer

09:21

@Mr.Xcoder umm 05AB1E is just stack-based language with some constructs

essentially it's just a lot of builtins

Mr. Xcoder

@EriktheOutgolfer Isn't that hard?

Erik the Outgolfer

and I always keep the docs open

@Mr.Xcoder the hard part is mainly implicit input imo

Mr. Xcoder

:/

Erik the Outgolfer

yeah it's a bit weird...other than that it's mostly builtins, but there are quite a few constructs in there

although that shouldn't discourage you from learning it

Mr. Xcoder

Can I make short programs in golfing languages and ask you what it's wrong when I encounter an error?

So that I can learn faster?

Erik the Outgolfer

09:25

there's also the 05AB1E - Oasis chatroom if you want help

TNB might often be busy

Mr. Xcoder

busy?!

isaacg

@Mr.Xcoder Feel free to do the same with me and Pyth if you want.

Mr. Xcoder

I don't wanna learn 05AB1E, I was thinking about Pyth

Erik the Outgolfer

ok then

Mr. Xcoder

@isaacg Sure

Erik the Outgolfer

09:26

although the busy thing is that sometimes you can literally see ~1.35 messages per second being posted

Mr. Xcoder

@isaacg How would I get the nth element of a sequence?

Leaky Nun

@Mr.Xcoder @

Mr. Xcoder

Let's pick G, the alphabet and its 5th element e. How do I get it?

@LeakyNun Usage?

Leaky Nun

@Mr.Xcoder @G4 (0-indexing)

Mr. Xcoder

Like @G5?

@LeakyNun Thanks

Now I have input problems... Can you take a String x and an integer n as input and get x[n]. My problem is the input.

isaacg

09:37

@Mr.Xcoder @ indexes a list.

Mr. Xcoder

Let me figure it out myself (about my comment above)

isaacg

@Lembik There's another exploit for your question, see the second half of my answer for details.

Mr. Xcoder

@isaacg I came up with something like this @wQ, but know I do not know hot to format the input, such that I don't get an EOF

isaacg

Q comes first, then w.

I mean Q happens first

Jim

@Mr.Xcoder You probably want to visit the documentation up to the part 4, it is very clear and really help for getting started

Mr. Xcoder

09:44

Why?

@Jim I visited that already

isaacg

Q happens before the program runs, w happens while it runs.

Mr. Xcoder

@isaacg I did it! I used @wQ and the input format 5\n"abcdefghijkl"

isaacg

Excellent, well done.

Mr. Xcoder

Thanks

Erik the Outgolfer

umm...can't you remove the Q?

Mr. Xcoder

09:50

@EriktheOutgolfer I don't care about golfing right now, I just want to learn and understand it

@isaacg I know you made a Fibonacci program in the docs, but I tried to make mine (way too long), and don't get the desired behaviour. Here is what I have: K0;J1;=T0;FNrQ=TK=KJ=J+JTJ, but the printed J is always 1...

Hope I don't bother you

Jim

@Mr.Xcoder You can omit the separating ;

Mr. Xcoder

@Jim I know, I added for clarity

isaacg

It looks like you're trying to use r to mean range on one input, but r is range on two inputs. You should use U, or better yet leave it out completely.

Jim

Also, you can use Z which is variable pre-initialized to 0

Mr. Xcoder

@isaacg Like, unary range, with one parameter?

isaacg

10:01

Yes

Jim

@Mr.Xcoder Exactly

isaacg

In this context, integers are implicitly cast to their range, in general U is range with one input.

Mr. Xcoder

It worked K0;J1;=T0;FNUQ=TK=KJ=J+JTJ...

isaacg

Great!

Mr. Xcoder

Thanks

Sorry for disrupting you

isaacg

10:02

Not a problem, I like doing this.

Fatalize

@Lembik I don't particularly appreciate that you update your challenge requirements 2 hours after posting it, to impose a new time limit which seems suspiciously here to disqualify answers such as mine

Mr. Xcoder

@isaacg Thanks

Now I'm trying to golf it...

I got this: K0J1=T0VQ=TK=KJ=+JTJ, and trying to figure it out with that double/triple assignment

Suggestions?

Shaved off some bytes, thanks to @Jim's suggestion: K0J1VQ=ZK=KJ=+JZJ

isaacg

You can use Z where you're using K and vice versa, that'll save a few bytes

Mr. Xcoder

@isaacg I already use Z, how shall it be done?

isaacg

Remove K0 and the first =, then replace all uses of Z with K and K with Z.

Mr. Xcoder

10:13

@isaacg Wow, you're a genius: J1VQKZ=ZJ=+JKJ

isaacg

:)

Mr. Xcoder

Any more golfing to do here?

I suppose there is a lot

isaacg

Well, the K can be removed without changing the length with J1VQ=,ZJ,J+JZJ

Then a byte can be saved using B, bifurcate, with J1VQ=,ZJ+BJZJ

Mr. Xcoder

Bifurcate?

isaacg

Creates a 2 element list, where the first element is the first input and the second is the result of the application.

Mr. Xcoder

10:17

Oh, nice

isaacg

For instance, +BT2 is [10, 12]

Mr. Xcoder

And can this get shorter - Getting the nth element of the Fib seq: J1VQ=,ZJ+BJZ=TJ;T

isaacg

With more dramatic changes, another byte can be saved with `JU2VQ=[eJ
sJ`

Mr. Xcoder

Oh, I know, don't tell me

@isaacg Getting the Qth element: J1VQ=,ZJ+BJZ;J.

isaacg

Seems solid. I don't think it can be beat without leaving the imperative approach.

Mr. Xcoder

10:22

@isaacg I want to keep it imperative such that I understand.

isaacg

Oh, actually, a big improvement is possible, using A.

A is shorthand for =,GH

Mr. Xcoder

Wait

Jim

@isaacg You can actually do that? Does it work for [ instead of ,?

isaacg

= has a special case for , and nothing else.

Mr. Xcoder

Reveal it to me. I don't get it (the `A`

approach)

isaacg

10:24

AU2VQA+BHGH

Mr. Xcoder

Where did that U come from?

isaacg

AU2 sets G to 0 and H to 1, since U2 = [0, 1]

Unary range, remember?

Mr. Xcoder

yep

isaacg

The rest is basically the same, but with G and H, not Z and J.

Mr. Xcoder

@isaacg But with A, J gets printed every time. I wanted the nth, by using J1VQ=,ZJ+BJZ;J

isaacg

10:27

That's not inherent to the A approach.

Mr. Xcoder

Were you reffering to my initial task

isaacg

Yes

Mr. Xcoder

Ah, I see

I now will try to store the results in a list

isaacg

AU2VQA+BHG;H does the new task

Cool!

Jim

@isaacg You have an idea of what you will add to Pyth this summer?

isaacg

10:28

@Jim Not much. It's not something I'm actively working on.

Mr. Xcoder

@isaacg Why does calling append print Y every iteration, in J1VQ=,ZJ+BJZaYJ;Y?

Jim

Oh, okay

isaacg

@Mr.Xcoder Most characters have an implicit autoprint. = and A are two of the few exceptions. a is not an exception. It can be silenced with a space.

This is part of why imperative style is not so short in Pyth.

OK, I need to go, but feel free to leave me messages.

Mr. Xcoder

@isaacg I think I'm better off learning the imperative way first, and then diving deeper into Pyth.

Erik the Outgolfer

pyth is polish notation...

i.e. you essentially prepend the builtins

Mr. Xcoder

10:32

That's very cool IMHO @EriktheOutgolfer

Pyth is very cool as a whole as I can see.

Erik the Outgolfer

well, that's a bit contrary to "imperative"...

Mr. Xcoder

No, it ain't

Adám

Today is the day for my code-golf gold badge. Yay!

Mr. Xcoder

@EriktheOutgolfer I personally love imperative languages.

Erik the Outgolfer

...unless you want to put multiple expressions in (well, easy to learn but not the shortest)

Mr. Xcoder

10:35

@Adám Congrats!

@EriktheOutgolfer they're also very powerful (imperative languages)

New Main Posts

-2

Q: Shortest program that calculates the length of a number

The question is very simple: Given a number between 0 and 999999999 and output its length. Although it's simple, I'm looking specifically for a program written in C (and I will accept it). Any other languages is welcome. This is what I managed to work out (scoring 33): s;main(){putchar(48...

code-golf string

Lembik

11:04

@Fatalize I do have sympathy for your view but I chose 30 minutes (instead of 10 seconds which would have made more sense) specifically to exclude as few existing answers as possible

Mayube

Why would you advertise local garage door repairs on stack exchange???

Lembik

@Fatalize but you are right that it would have been better to have had this rule from the start

@Mayube maybe they are really good repairs? :)

@Fatalize the mistake I made was to not realise that my initial constraint is inequivalent to requiring the code always to be not too slow

Fatalize

11:17

@Lembik If there was such a time limit on the challenge from the start, I would not have even wasted my time answering it, as I do not appreciate those kinds of challenges

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Sheet music ASCII-art generator The challenge Given an input like this: 8g 8Df 4cs 2C 1A Produce an output like this: /\ -○- | | ---|-|---------------------------------------------------|-| |/ ...

Erik the Outgolfer

@Lembik I see you have posted some really challenging math-related challenges...

Lembik

11:36

@Fatalize I understand and can only apologize. There was a time limit of course of sorts but not done properly

@EriktheOutgolfer yes :)

@EriktheOutgolfer I am experimenting with code-golf questions which is not my usual thing to do

New Main Posts

-1

Q: How to create a search Engine with php and a xml database?

How can I create a search engine with php and xml database? (I want to use SimpleXMLElement() function).

code-challenge fastest-algorithm search word-search php

Erik the Outgolfer

@Lembik oh Helka Homba has done that too

Lembik

experimented with code-golf?

Erik the Outgolfer

yeah...some of the most famous challenges are the result of that

Lembik

I don't have a famous code-golf challenge yet :)

New Main Posts

11:53

0

Q: Two programs that output each other in a loop

Program A outputs program B's code when run, and B outputs A's source. Requirements: Only one language across both programs Programs are different. One program that outputs itself does not qualify. Both programs are non-empty, or at least 1 byte in length. Trailing newlines in both source an...

code-golf quine

2

Q: Is it a Lynch-Bell number?

You will be given a positive, whole number (that will never contain a 0) as input. Your task is to check whether it is a Lynch-Bell number or not. A number is a Lynch-Bell number if all of its digits are unique and the number is divisible by each of its digits. In fact, there are actually only ...

code-golf number

New Main Posts

12:13

-1

Q: Fewest operations to 100

Overview Given a list of digits, find the fewest operations to make 100 Input A string of digits, which may or may not be in numerical order. The order of the digits cannot be changed, however plus (+) or minus (-) operators may be added between each so that the total sum is equal to 100. Out...

code-golf integer integer-partitions

New Sandboxed Posts

12:49

0

A: Sandbox for Proposed Challenges

Regex, Paper, Scissors code-golfregular-expression Write three regexes A, B and C such that they match each other in a cyclic Rock, Paper, Scissors fashion. In particular, A matches B, B matches C and C matches A, but A doesn't match C, B doesn't match A and C doesn't match B. Here's a handy ta...

Transcript for