The Nineteenth Byte

12:17 AM

actually disregard above was albe to test

1:14 AM

CMC: write a single-line python "indexOf" function using the algorithm "given a list L and item N pick random indexes until L(I) == N then return I". example, multiline:

def search(l, n):
	while True:
		i = random.randint(0, len(l)-1)
		if (l[i] == n): return i

my best guess so far is using py3.7 new := with l.__getitem__(i:=random.randint(0,len(l)-1))==n

can't get that into a single-line loop inside a function tho, RIP

DJMcMayhem

Vtc, unobservable behavior :P

Riker

there's a reason this is a CMC not a main post DJ lol

is it possible to make an infinite list comprehension?

DJMcMayhem

Probably not

Riker

yes, yes it is

DJMcMayhem

Maybe an infinite generator instead?

Riker

1:18 AM

yep using that in an inf list comp should work

DJMcMayhem

@Riker Remind me how := works? It's a 3.8 thing, right?

Riker

yep

long story short you can do if (match := pattern.match(data)) and then use match right after

instead of needing to re-call patten.match

I'm using it for i:=random.randint(0,len(l)-1)

which is a horrible line of code lmao

DJMcMayhem

Oh, I just had an idea

Just a sec

Nope, doesn't quite work: Try it online!

Riker

this works but doesn't end

DJMcMayhem

Oh wait, does TIO even have 3.8?

Riker

1:26 AM

nope

sys.vers says 3.7.2

@Dennis py3 on TIO is running 3.7.2 instead of 3.7.3 or even 3.8

should probably be updated to 3.7.3 at least, I'm not sure it matters much though

DJMcMayhem

Try it online!

@Riker It's just a different version on TIO

Anonymous

:= is a godsend for lambdas

Riker

yes

@DJMcMayhem can't use := inside a list index

you have to use l.__getitem__

mınxomaτ

Coffee break NLP project: github.com/turbo/Endering . Maybe something that could be made into a challenge.

Riker

but yeah that's what I'm coming up with too @DJMcMayhem

would be nice to make it non-recursive but that works

you can shave a byte by spinning it around tho

DJMcMayhem

1:30 AM

It works! Try it online!

Riker

I'll do you one better

Anonymous

@mınxomaτ That's pretty neat. Have a star

Riker

if you make it n==l... then you can remove the space after the ending parends, which is already removed with the ==

so you can do )else & if n not n else & if l

DJMcMayhem

@Riker Why is Gamora?

Riker

also that's still 2 lines ;p

@DJMcMayhem

though I think that might hit sys.recursionlimit

@DJMcMayhem I understood that reference

@mınxomaτ interesting, nice work on that

Anonymous

1:37 AM

@Riker

Riker

ah nice

what's the or~+i for?

Anonymous

Because i can be 0, which is falsey

Anonymous

And ~+i is a short way to cast 0 into non-zero that doesn't require a space between it and or

Riker

well, do you need +?

Anonymous

Oh true

Anonymous

1:39 AM

I'm just used to the short inline +1 trick :P

Riker

I get the ~ cast lol I was just confused about ~+

ah I see

and you stole my n==l vs l==n lol

Anonymous

Actually, I don't need ~i

Anonymous

Tuples are truthy :P

Anonymous

And so are lists

Riker

import*

Anonymous

1:42 AM

randrange works like range

Riker

oh nice

which has higher precedence, and vs or? and, right?

Anonymous

Yep

Riker

darn I can't replace else with or

Anonymous

You can, but no bytes saved

Riker

ah

Anonymous

1:46 AM

unless you do this :P

Riker

hm

tempted to do this for the spirit of the challenge

Anonymous

The rule was one line, not one self-contained lambda

Riker

yes tha'ts why "spirit"

I wasn't referring to the self-contained bit just the two statements with ;

Anonymous

75

Riker

hm, is there any way to use input() and := to remove something? idts

Anonymous

1:50 AM

Not in a way that would save bytes, I think

Riker

yeah don't think so

you'd have to use a loop and that's gonna nuke your line anyway

Anonymous

You could use an IIFE but that would definitely not save bytes

Riker

ofc

MilkyWay90

2:45 AM

Does anybody here see morse code in camel.mp3?

primo

7:11 AM

@H.PWiz perhaps mildly interesting, i just found a new summation for phi

wolfram alpha

and unlike the taylor series of (1 + 1/4)^(1/2), the terms are all positive

Leaky Nun

@primo what's the rate of convergence?

primo

7:24 AM

not sure actually

let me test it :p

primo

7:43 AM

@LeakyNun linear, at about 1.43 terms per digit

Leaky Nun

nice

primo

8:04 AM

1/log(5) terms per digit =~ 1.43068

Leaky Nun

8:43 AM

how to increase the rate of convergence?

of, say, sum 1/n^2 = pi^2/6

oh I may have some idea

primo

should already be super-linear

no, i'm definitely wrong about that :p

Leaky Nun

tio.run/##ZZC9bsMwDIRn6ykOnmyHqE1RP1EAP0nRIUPaGEFkw/…

still very slow

@primo sum[n>=N] 1/n^2 >= sum[n>=N] 1/n - 1/(n+1) = 1/N

primo

9:10 AM

euler's transform doesn't help either, it would need to be an alternating series

Try it online!

100 terms hasn't converged to the second decimal place

primo

9:26 AM

@LeakyNun linear convergence @ ~0.3 digits per term

Try it online!

the series doesn't seem factorable, though

Leaky Nun

@primo how does it work?

Adám

Interesting idea (for finite-precision languages)? Given a list of floats that may be very large and/or very small, answer their product (which is guaranteed to be within your float range). E.g. [3E200,4E200,5E-200,6E-200] → 360

primo

modified euler transform, in effect i discard half of each term

which is why there's a multiplication by two at the end

primo

10:55 AM

@LeakyNun Try it online!

i determined that each term of the series was factorable by the nth harmonic number

slightly better formulation: Try it online!

H.PWiz

12:26 PM

@primo Cool. I have it as 70 bytes in Python3 (might be over complicating it). Perhaps it is useful in C (I don't know how hard the division in the other algorithm is to implement)

primo

i think it might reduce C, perhaps also perl

i currently waste a few bytes in perl because integer division and mod of negatives don't agree

i.e. int(a/b)*b + a%b != a

@H.PWiz 67 bytes

i modified the summation slightly, though wolfram alpha

H.PWiz

Me too 70

My aim was just to get 1.%d

primo

i'm not actually sure how you hacked in the 1/2

H.PWiz

(Same way I get -3 for pi)

primo

12:41 PM

i'll have to study this ;)

i recently reduced 67->66 for pi

H.PWiz

I saw, presumably with f''

primo

embarrassingly, i didn't know about f'' format strings until 2 days ago <_<

H.PWiz

Yeah, I found out about them, after golfing all my solutions below the point at which they are useful

simple 68

Forgot to inline b. So 64

primo

nice

Adám

CMC: Given a list of numbers, reorder the list such that the sum of the absolute deviations from zero of the running total is minimised. E.g. [1,-5,-5,10] → [-5,10,-5,1]

Maltysen

12:54 PM

so like for the answer

the sum of deviations would be 11?

Adám

@Maltysen Yes.

primo

@H.PWiz 63

Maltysen

@Adám Pyth, 13 bytes

hos.aMsM._N.p

Adám

@Maltysen No speaketh Pyth. How?

Maltysen

.p is premutations

then we take head(h) of sortby(o)

._N is prefixes of the lambda var

then map(M)

sum (sM)

and abs (.aM)

and sum that (s)

Adám

1:02 PM

@Maltysen Ah, so brute force, and untenable for long lists.

Maltysen

oh yeah lol

I haven't figured out the pattern

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Gravitational Force Between Numbers The gravitational force is a force that attracts any two objects with mass. In this case our objects will be Numbers and their mass will be their value. In this challenge we are going to be trying to simulate this using numbers. TO do so we don't care about t...

Maltysen

im not sure if greedy would work

Adám

Maybe would make a good Main challenge if I can somehow prevent brute force.

Maltysen

u can just say

that it has to do the test cases <10 s

or something

or even an hour

and give a list with n=20

so people can do stupid golf stuff

but not brute force

New Sandboxed Posts

2:42 PM

0

A: Sandbox for Proposed Challenges

A word ladder Given a string consisting only of lowercase letters and spaces, use each space to alternate the direction of writing to the right, then to the left relatively to the initial direction from left to right. hello world hello w o r l d Here we start writing he...

ngn

3:09 PM

@Adám do you have a non-bruteforce solution?

Adám

@ngn No, you?

ngn

@Adám no, i'm trying to think of one

Adám

@ngn I have a feeling that an O(n²) solution is possible rather than the naive O(n!)

ngn

3:29 PM

@Adám this problem is a wolf in sheep's clothing

Veskah

codegolf.stackexchange.com/a/185734/78849 I'm not sure what's counted in Scala. Did this new guy chip out too much into the header?

dzaima

@Veskah don't know Scala, but val f:Int=>Unit = feels analogous to Consumer<Integer> f = in java, which is allowed

Veskah

Ah, makes sense

AdmBorkBork

3:44 PM

@Adám I've been trying to come up with an example where interleaving the smallest element and largest elements isn't the solution. I.e, sort the array, then take the first, then the last, then the second, etc. Or am I not understanding the challenge?

Adám

@AdmBorkBork [1,2,3]

AdmBorkBork

Oh, I see. The examples I've fiddled with have had negative numbers as well. Didn't think of an only-positive example. Haha.

ngn

5:59 PM

@Dennis @DJMcMayhem @Doorknob @Mego could you grant chat.stackexchange.com/users/390618/feeb write access to chat.stackexchange.com/rooms/90748/the-k-tree please?

Rick

is a matrix maze of 0 and 1 considered a complete graph?

ngn

@Rick in what sense? the usual?

Rick

correct the usual

ngn

@Rick if the vertices are the matrix cells and the edges are pairs of neighbouring cells, then obviously it's not a complete graph (except for a few trivial cases of 1×1, 2×1, etc)

Rick

then what is it?

an adjacency list?

and how do you calculate the time complexity of traversing from one vertex to another

ngn

6:11 PM

@Rick depends on what property of the graph you want to draw attention to, e.g. it could be a bounded-degree graph - each vertex has ≤4 edges (or ≤8 if you allow diagonals)

@Rick an adjacency list is a way to represent a graph, not a property of the graph as a mathematical object

@Rick is that homework? :)

Rick

The degree will vary from one vertex to the other. I just want to be able to explain maze traversal in graph theory terms. And I want to be able to explain the time complexity associated with traversing from one point to another point in the maze.

that fact that it's a maze is throwing me off

Not homework, I just want to make sure I understand what a maze is in concrete terms.

Rick

6:31 PM

@ngn I just found something that says Dijkstra can run on dense graphs which are complete graphs. This is so confusing

When I read about Dijkstra it talks about the graph as a weighted graph and it is only in terms of the path it traverses. Never in terms of the overall matrix that path is a part of, why is this?

DJMcMayhem

@ngn done

New Main Posts

6:57 PM

3

Q: Warped chessboard

This challenge is about building a chessboard in which the square size, instead of being constant across the board, follows a certain non-decreasing sequence, as described below. The board is drfined iteratively. A board of size n×n is extended to size n+k×n+k by extending it down and to the rig...

ngn

7:14 PM

@DJMcMayhem thanks

@Rick you can consider all edges in a maze to have weight 1

@Rick i'm not sure i understand the rest of your question. could you give a quote from or a link to what you read?

wikipedia has a nice animation of Dijkstra's algorithm working on a maze graph en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Algorithm

Rick

@ngn cs.smith.edu/~istreinu/Teaching/Courses/274/Spring98/Projects/…

Luis Mendo

@Arnauld @flawr Thanks for the edits! (I couldn't see what @flawr's edit was, though)

Erik the Outgolfer

flawr's was most likely a whitespace removal

Rick

@ngn Dijkstra can be run on many different graphs, it can also be run on a directed edge graph. I'm just confused about why no one ever talks about the path with respect to the larger structure that path resides in.

Veskah

Felt like I was taking crazy pills when I scrolled so far through the pwaS challenge and didn't see regex answers. They were all at the bottom

~~I also only thought of it after mucking about with swapping the actual letters~~

ngn

7:29 PM

@Rick i don't know. technically, the algorithm doesn't compute paths, only distances

(though the paths could be reconstructed from the distances after the algorithm has finished)

Rick

@ngn Dijkstra computes the path, the paths are the nodes that form the distances.

how do you think it gets to the target without visiting all the nodes in the matrix

ngn

@Rick ok, with a small modification, the algorithm can find the paths (without computing all distances first): at the step when we choose an edge that crosses the cut line, we could remember that we arrived at the new (right-hand side) node from the old (left-hand side) node

then it's easy to follow the paths backwards

this is at no extra complexity cost

flawr

@EriktheOutgolfer @LuisMendo It wasn't, I did the exact same edits as @Arnauld and it now seem to have saved it as a new revision without any changes

Erik the Outgolfer

oh, that too! :P

flawr

@LuisMendo Would you mind if I latexified it?

Erik the Outgolfer

7:44 PM

yeah, maybe the system slipped a bit, because normally it doesn't really consider non-changes as changes

flawr

I was surpized too, but maybe it is some caching issue

shouldiblamecaching.com

Rick

@ngn so it turns out that a binary matrix (maze) is an adjacency matrix en.wikipedia.org/wiki/Adjacency_matrix

ngn

@Rick no! the cells of a maze matrix represent vertices. the cells of an adjacency matrix represent edges

Erik the Outgolfer

@flawr pretty sure it's just the leeway the servers allow to reduce conflicts

Rick

@ngn so what is a binary maze then

ngn

7:55 PM

@Rick if i understand you correctly, 0 represent walkable areas and 1 represent walls (or vice versa). each cell is considered a vertex in a graph, and there's an edge between two cells iff they are neighbours and neither of them is a wall

Rick

vice versa, 0 is wall 1 is cell

ngn

1

Q: How to convert a maze to a Graph?

I am trying to convert a maze data structure into a graph. The maze is like a grid and some walls between cells. maze[8][8][4] is how the maze is represented. If maze[i][j][0] = 1 it means you can't go up from (i,j) if maze[i][j][1] = 1 it means you can't go down from (i,j) // and so on I want...

graph maze

^ this is slightly different, as the walls are between cells, but you get the gist...

Rick

@ngn this leads me back to my problem, which is, the graph path is looked at in isolation from the rest of the structure. Meaning, unless that cell is connected to the path it is not considered.

we just simply throw it out

and don't consider it in the space complexity or even the struct of the problem which is puzzling to me

Arnauld

@LuisMendo I missed of its reflected of rotated versions, btw :-)

Rick

and that becomes more problematic when Dijkstra itself will determine the relevant parts of the maze using its greedy approach.

sorry that last part is not correct it will visit all paths reachable from the source

ngn

8:10 PM

@Rick the complexity depends on how the graph is represented. i think in that paper they are assuming neighbour lists, not adjacency matrix

i'm not sure

Rick

@ngn I have a better understanding, although it's a maze not all of it is relevant to the problem

ngn

yeah, graph theory doesn't care how we lay out the vertices visually, only the relationships between them matter :)

shouldn't O(V^2 + E) be the same as O(V^2), by the way?

Rick

correct constants are thrown out

Oh i see what you did there

lol :)

ngn

the number of edges (E) is never greater than the square of the number of vertices (V^2)

so V^2 should always be the dominant term in the polynomial

Rick

But the problem isn't given to you like that, they give you a maze they don't cut out the irrelevant part for you they add them

ngn

8:20 PM

@Rick i didn't find the word "maze" there

Rick

if you were given a maze, and you were told to find the shortest path if one exists. how would you quantify that Time complexity when you only know the dimensions including the irrelevant parts

ngn

@Rick if the maze is m×n, then substitute V=m×n and E≤2×m×n

Rick

why 2xmxn?

Oh I got it

n(n-1)/2

for the total number of edges

Luis Mendo

@flawr Sure, go ahead. I don’t usually do it in case LaTeX support is removed, but that won’t probably happen

ngn

@Rick in a maze each vertex has at most 4 attached edges (so, ×4), and each edge is shared between two vertices (so, div 2)

Erik the Outgolfer

8:34 PM

@LuisMendo edited that in for you :P

Rick

@ngn sorry my brain is fogged up today, you are a genius thanks this helped a lot! :)

ngn

@Rick not at all

flawr

8:58 PM

@LuisMendo I don't think they are gonna remove it again

but you really have to say if you don't want me to!

@AdmBorkBork whats wrong with oboes?

Luis Mendo

@EriktheOutgolfer Oh, I hadn't seen that, but thanks! I've put it in the list of options below

Erik the Outgolfer

looks like you don't have quick notifications enabled in chat... ;)

(you should've still gotten a "question edited" notification)

also... it looks like you put that in the output section

Luis Mendo

@flawr No, it's ok. It will look much better :-)

@Arnauld Edited :-)

@flawr It looks great. Specially the square root

Erik the Outgolfer

9:13 PM

I like how he kept the wording intact to not make the challenge confusing... :P nice job

flawr

I think I undid some edit that was done while I was editing it

why don't they have a proper merge protocol:/

Erik the Outgolfer

you normally get an orange notification at the top, but it might be delayed

can confirm, you undid the "of" → "or" spelling fix

Luis Mendo

@EriktheOutgolfer Thanks for noticing! I'll (re-)do it, @flawr

Erik the Outgolfer

oh cancels edit

Luis Mendo

Aw. Sorry. What a mess :-)

flawr

9:19 PM

@EriktheOutgolfer I had that after I went through the whole post, but what else are you supposed to do?

Erik the Outgolfer

it has a link, click it to see what got changed and change it too

(not sure if it does, it's been a long time since I've last seen it...)

hm... let's see how long this discussion about these seemingly little errors has been so far...

Luis Mendo

9:44 PM

@Arnauld I'm afraid a matrix doesn't qualify as ASCII art (because of spaces in between... unless there's consensus otherwise that I'm not aware of). Is that what you are fixing?

I upvoted too hastily :-P

Arnauld

10:03 PM

@LuisMendo Well, an array of strings is usually accepted, but maybe not a matrix of characters. I'm not sure either, tbh. (The fix was unrelated. My original version failed for k>9.)

ThePlasmaRailgun

13

Q: Golf a number bigger than Loader's number

As a follow up to Shortest terminating program whose output size exceeds Graham's number and Golf a number bigger than TREE(3), I present a new challenge. Loader's number is a very large number, that is kind of hard to explain (since it was itself the result of a code golfing exercise with a fle...

code-golf math number busy-beaver

Arnauld

@LuisMendo Should I update it to output a single string?

ThePlasmaRailgun

I saw this question today, and wanted to see whether it's possible to get a reasonably sized non-trivial number bigger than Loader's number (likely using an implementation of finite promise games or greedy clique sequences. Would anyone be interesting in trying to figure out an algorithm for one of these functions?

Erik the Outgolfer

10:19 PM

@LuisMendo I think conosensus is that ascii-art challenges are a bit stricter unless otherwise specified

hm... or no

26

Q: ASCII Art Output Rules

I know there's a desire on PPCG for challenges to be flexible in terms of what they allow for input and output. However, I think there is an argument to be made that ascii-art is a special case, and should be stricter about the permitted output formats. As a case in point, there was a recent asc...

discussion policy rules

looks like a matrix wins by an ever-so-slight one vote currently, but eh

maybe the challenge should be clarified a bit

Luis Mendo

@Arnauld A matrix of characters is fine if it is displayed as such. Right now there are extraneous spaces between those characters

I mean, the point of ASCII art (or my idea in this challenge, sorry if I wasn't clear) is that it has to be displayed as required in the challenge

Arnauld

@LuisMendo I actually added a space on purpose because I thought it was looking better. :p But I see your point.

Updated.

Luis Mendo

@Arnauld I see. Now it qualifies as ASCII-art :-)

@Arnauld I've added this. I hope it clarifies:

Output may be through STDOUT or an argument returned by a function. In this case it may be a string with newlines, a 2D character array or an array of strings

@EriktheOutgolfer ^

Arnauld

10:47 PM

@LuisMendo Sounds good. IMO, it could have been tagged as binary-matrix rather than ascii-art just as well. (But both work.)

Luis Mendo

11:12 PM

@Arnauld Good point. I didn't remember that tag / challenge-category. I'll keep it in mind for future challenges. Anyway, that feels more appropriate for when you have to operate on a binary matrix (perhaps taken as an input), as opposed to simply creating it

Transcript for