The Nineteenth Byte

Reimer Behrends's answer is even better

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

10

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

:)

@isaacg hi.. are you here?

Yep

8:17 AM

@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?

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.

great!

I was confused :)

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

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

thanks

Newly Featured Questions

32

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

8:26 AM

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?

why not :)

@isaacg Put a bounty on it

Fair enough

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?

Yeah

Bounty placed

8:33 AM

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

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

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."

@isaacg Can I golf the script there?

And post an answer :)

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

@V.Courtois No purpose.

8:36 AM

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

A: Sandbox for Proposed Challenges

sry

-1

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...

1 min ago, by Mr. Xcoder

@isaacg Can I golf the script there?

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

Hmm, ok

Hope I won't be ninja'd

@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.

8:40 AM

Yeah, ofc

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.

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?

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 ...

@isaacg is it better like this?

8:52 AM

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

Very procedural

@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∧

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

sorry, you are right.

oops

8:54 AM

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

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

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

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 :)

:)

because of course

>>> +False
0

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

8:58 AM

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

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

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

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

code-golf number array-manipulation matrix

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 ...

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

I got down to 340 bytes

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

9:00 AM

@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]

@Mr.Xcoder What's wrong about it?

It fails on this line

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

It works on my computer.

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

It doesn't on mine

9:01 AM

It completes in 17 seconds with the correct answer.

I'll check once more

@Jim To me: found it

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

I think of using F inside f

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

9:02 AM

You're welcome.

@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

Absolutely

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 )

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

9:11 AM

@Mr.Xcoder you can't

it will convert

How?

Place 4 spaces?

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

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

But I should count as tabs, right?

Ok, thanks @orlp

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

9:12 AM

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

no

boooo

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

it would make my life so much easier :)

Does repl.it work with itertools?

9:13 AM

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

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

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

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

@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

that never happened to me

9:15 AM

ah ok that's good news

Q: Evaluate modular power towers

for example

11

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.

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

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

exec I can excuse

@Lembik ?

9:18 AM

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

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

Was Q evaluated input in Pyth?

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

@Mr.Xcoder Yes

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

Sorry about that.

9:20 AM

@isaacg Learnt a new builtin :)

@isaacg About what?

Awesome!

Pyth being hard to learn.

@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

@Mr.Xcoder I was going to ask

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.

9:21 AM

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

essentially it's just a lot of builtins

@EriktheOutgolfer Isn't that hard?

and I always keep the docs open

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

:/

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

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?

9:25 AM

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

TNB might often be busy

busy?!

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

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

ok then

@isaacg Sure

9:26 AM

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

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

Leaky Nun

@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)

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.

9:37 AM

@Mr.Xcoder @ indexes a list.

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

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

@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

Q comes first, then w.

I mean Q happens first

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

9:44 AM

Why?

@Jim I visited that already

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

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

Excellent, well done.

Thanks

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

9:50 AM

@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

@Mr.Xcoder You can omit the separating ;

@Jim I know, I added for clarity

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.

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

@isaacg Like, unary range, with one parameter?

10:01 AM

Yes

@Mr.Xcoder Exactly

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

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

Great!

Thanks

Sorry for disrupting you

10:02 AM

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

@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

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

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

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

10:13 AM

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

:)

Any more golfing to do here?

I suppose there is a lot

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

Bifurcate?

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

10:17 AM

Oh, nice

For instance, +BT2 is [10, 12]

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

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

Oh, I know, don't tell me

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

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

10:22 AM

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

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

A is shorthand for =,GH

Wait

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

= has a special case for , and nothing else.

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

approach)

10:24 AM

AU2VQA+BHGH

Where did that U come from?

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

Unary range, remember?

yep

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

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

10:27 AM

That's not inherent to the A approach.

Were you reffering to my initial task

Yes

Ah, I see

I now will try to store the results in a list

AU2VQA+BHG;H does the new task

Cool!

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

10:28 AM

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

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

Oh, okay

@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.

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

pyth is polish notation...

i.e. you essentially prepend the builtins

10:32 AM

That's very cool IMHO @EriktheOutgolfer

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

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

No, it ain't

Adám

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

@EriktheOutgolfer I personally love imperative languages.

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

10:35 AM

@Adám Congrats!

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

Q: Shortest program that calculates the length of a number

-2

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

11:04 AM

@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???

A: Sandbox for Proposed Challenges

@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 AM

@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

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

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

11:36 AM

@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

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

-1

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

@Lembik oh Helka Homba has done that too

experimented with code-golf?

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

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

Q: Two programs that output each other in a loop

11:53 AM

0

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