The Nineteenth Byte - 2020-07-09

« first day (3449 days earlier) ← previous day next day → last day (1384 days later) »

New Sandboxed Posts

12:05 AM

0

A: Sandbox for Proposed Challenges

Sum the array times n, except the last code-golf arithmetic array-manipulation Task Given an array A and a number n, calculate the sum of all numbers of A multiplied by n, except the last one. All numbers (the elements of A and the value of n) are non-negative integers, and A is non-empty. Shorte...

1:05 AM

0

Q: Counting King's Hamiltonian Paths through 3-by-N grid

Background A Hamiltonian path is a path on a graph that steps through its vertices exactly once. On a grid, this means stepping through every cell exactly once. On a square grid, a Chess King can move to a horizontally, vertically, or diagonally adjacent cell in one step. Challenge Count the numb...

code-golf combinatorics grid graph-theory

3 hours later…

4:12 AM

CMC: write a Dodos program that takes [n, list] and returns list[n:] (list with n first elements removed). Assumes that n<len(list). Bonus if the program takes polynomial time in n, the list length and the list elements.

(If you know that esoteric language) -- (I can't solve the bonus part myself)

Third-party 'Chef'

4:42 AM

@Neil What kind of nonsense is this?

2 hours later…

New Sandboxed Posts

6:36 AM

0

A: Sandbox for Proposed Challenges

Find the Block on the Extended Periodic Table The periodic table gets its shape from the arrangement of elements into blocks: An element is assigned its block based on what type of orbital holds its valence electron(s). For instance, the sole valence electron of neutral hydrogen occupies the 1s ...

1 hour later…

8:02 AM

@NewMainPosts CMC: prove that the result still a linear recurrence if 3 is replaced with an arbitrary constant.

8:23 AM

@user202729 The rightmost column state is a combination of each cell's state plus a list of left-side-U-shaped connections between two distinct rows; each cell's state can be encoded with how many branches (0, 1, or 2) cross the right border. Going from one state to another (by adding a column) is well-defined, and the multiplicity can be found by enumerating all possible outbound branches in the former, plus adding optional vertical connections.

So it is possible to generate a transition matrix for any number of constant rows like I already did for 3, which can be reduced to a linear recurrence.

0

Q: Distributive on myself

Background We all know about distributivity, i.e. \$a(b+c) = ab + ac\$. This is a property on 2 different operations, namely addition and multiplication. But indeed, nothing can stop us from studying distributivity of 1 operation. In this challenge, you will be studying a kind of left-distributiv...

code-golf kolmogorov-complexity

@user202729 I guess it would be a good challenge to construct the transition matrix?

8:54 AM

@Bubbler Are U-shaped connections between rows really all that's possible in the general case? What about if you have, say, 10 rows, and go diagonally from the top row to the bottom row?

@xnor It will eventually be connected to the rightmost-column cell on some row that has one branch going right.

^ /s/the/a/

I think I'm not understanding. Is the claim that for a fixed number of rows, say 10, there is a finite number of nonequivalent possible states of the columns up to the rightmost column?

Yes.

OK, and say for 10 rows we consider paths that go right while bouncing between the top and bottom k times. Does the number of ways to backtrack and fill in the remaining spaces really not grow unboundedly with k?

Like, for 3 rows, it seems pretty constrained to me how you can go left and back, but for, say, 10 rows, it seems like the path can wiggle back and forth for quite a while even with a bit of cells excluded from the diagonally zigzagging path.

Even for 3 rows, you get something like this:

-x   x-
  \ /
   X
  / \
 x   x
  \ /
   X
  / \
 x---x

9:06 AM

How do I interpret that picture?

Are the 3 rows shown as columns?

small x's are the cells, large X's are crossings

Crossings?

so you enter at the top left and go front-back-front-back-front and exit through the top right cell.

What are front and back here?

right and left.

9:09 AM

Ohh, now I see it, I was being silly

I mean, the picture, I'm still confused about the argument

But like, even for N=4, it looks like there are many complicated ways to double back, for example:

1IJA987
H2BKL6
GC3M5
FED4N

I'm using a different and worse notation where the path goes 1-9A-N...

My classification doesn't consider how complicated the path is, except for crossings between two columns, and which crossings are connected on the left side of that border.

Oh interesting

Sorry, I'm still not seeing it

Like, what would the state description be for this path:

There's no such description for that path, because the left side isn't filled.

Left side isn't filled? What would that look like?

Wait a sec, I'm doing some drawing

I mean something like the following, where you start at 1 and go through the right border at 6, then re-enter at small a, go through b c ... to m and go through the border again, then re-enter at A and bounce back right away:

1 d c l m
e 2 k b 6
f j 3 5 a
g h i 4 A

So it is a collection of path fragments, completely describing the left side of a column.

9:24 AM

What are the path fragments in this one?

Is it just "6 goes to m", "a goes to A" (this is, row 1 to 2 and row 3 to 4)?

No, 1 to 6, break, a to m, break, then A.

Is the defining property here that a path fragment ends on a column further right or the same column?

Path fragments end at exactly that column (column 5 in the figure, 1-indexed)

Ah, ok

Does the left side being filled mean that all columns to the left of that column are fully occupied?

Yes.

9:33 AM

And those are the "states" of the transition matrix?

Yes, by keeping only the information that describes the rightmost known column.

0

Q: Music with pi and e(eulers number)

Music with pi and e(eulers number) Because I forgot to celebrate the pi-day(14.3) lets celebrate with pi, e and music! Challenge No, we don't have time to eat a pi-pizza, lets make a program. What you need is 500 digits of pi, and 10 digits of e. The User gives any digit from 0-499 through an in...

code-golf math number music pi

So say I make a Hamiltonian path with the property that it ends with a segment that starts in the leftmost column, and travels rightward at every step (possibly diagonally). That is, I contrive it to fill all but one cell in each column, all touching, then travel left to right to the finish completing the path. Then no column is filled until we start this last leg, right? What does the list of states encountered looked like?

To clarify: when the columns are filled doesn't matter. However, if you cut the completely-filled board on a particular column, you'll always end up with a path (from the start) and some U segments.

Oh, thanks, I think this was the bit I was not understanding

9:45 AM

e.g. If you have a fully connected path of 1..7 then a..q then A..D:

1 d c l m n o
e 2 k b 6 7 p
f j 3 5 a q C
g h i 4 A B D

Then consider only first five columns, which gives exactly the picture before

Then you get a path starting at 1 and ending at 6, then a U-shaped path fragment starting at a and ending at m, then a (single-cell) U-shaped path of A.

OK, I think my trouble is I was thinking of each state as being a property of the path up to some number of steps along it, not the completed trip up to some number of columns. Lemme see if I can convince myself that the transitions from one column's states to the next are fully described and counted by those states and not any external data.

I think I'm sold now! Nice technique, especially with having the state store connection pairs to make what seemed to be a global property be stored and updated locally. Thanks for the patient explanation.

:)

10:02 AM

@xnor If you're interested, or haven't already noticed, henkma has posted all of their anagol solutions to github

An obligatory follow-up would be a challenge to generate that transition matrix with a program, though I feel like it might be way too hard to understand for general users...

Or, generating a transition matrix for something easier would be interesting as a theme, as it bans the usual brute-force and makes the program results more observable

10:26 AM

0

Q: program to classify rice grains

i have written code but i am not getting right answer import cv2 import numpy import sys import numpy as np def get_classificaton(ratio): ratio =round(ratio,1) toret="" if(ratio>=3): toret="Slender" elif(ratio>=2.1 and ratio<3): toret="Medium" elif(ratio>=1.1 and ratio<2.1): to...

code-golf image-processing python

4 hours later…

2:22 PM

sigh Both answers on codegolf.meta.stackexchange.com/questions/19041/… are currently at negative votes, and there are no comments explaining what's wrong...

2

Q: Is "A solution wins if there's no strictly better solution in multiple measures" a valid winning criterion?

To cite a recently sandboxed challenge by l4m2: Solution win if there's no strictly better solution, aka. no solution that take less or same amount of items in mapping table, less or same amount of instrucions, and at least one of amounts of items and instructions is less. I understand this...

discussion winning-criteria

caird coinheringaahing

2:52 PM

@user202729 Even worse, both answers are supporting the same side, so there isn't even an opposing view (as an answer) :/

0

Q: Tau Search Engine

We had 48 Questions about tau and no one asked about a number search engine! Challenge We will now make a search engine. You need 500 digits of tau. The User will give a number Based on that number the program should print to stdout, The first occurrence and the number of all occurrences of the g...

code-golf math number

caird coinheringaahing

3:26 PM

@Neil my thoughts whenever I read the explanation for most answers on PPCG :P

Has there been an ultimate tic tac toe challenges?

If not, we need one

caird coinheringaahing

@Anush codegolf.stackexchange.com/questions/tagged/tic-tac-toe

That's the tic-tac-toe tag

Lots of questions but none about Ultimate Tic Tac Toe it seems

my pronoun is monicareinstate

Is a Totally Blind Tic-Tac-Toe KOTH a good idea?

3:42 PM

-1

Q: Proof of Fermat's Last Theorem By Infinite Descent of congruence

If show that the Diophantine equation has no solution, we have First method. show that has no solution modulo positive integer n. Second method. by descent infinite of Fermat. Problem. Is it possible to adopt a new method by mixing the previous two methods to prove that an equation does not accep...

decision-problem number-theory primes division equation

5 hours later…

8:56 PM

@H.PWiz I have not seen it -- where is it? I'm failing to Google for it. And how did you find out about it?

9:53 PM

@xnor Spoiler

I saw that henkma made a couple of posts on code.golf and looked at their github account.

It looks like they have also tweeted about it

New Sandboxed Posts

10:49 PM

0

A: Sandbox for Proposed Challenges

Solve a 2xN Maze Given a 2xN maze, determine if you can get from the start top left corner to end bottom right corner using only up, down, left, and right moves. Input A 2xN block (N <= 100) of your choice of two distinct ASCII characters, one representing walls and the other representing empty t...

Any feedback for this?

@Bubbler 3 bytes can simply be brute forced.

11:06 PM

@Adám It is <spoiler> an adverb train </spoiler>, and J threw SYNTAX ERROR at me when I tried to eval the 3-char string. So I believe one cannot brute force it, at least inside the J interpreter.

@Bubbler Just give it non-trivial arguments and eval the whole test case.

Well, it's OK to me if someone really does that.

(And let's see how all the golfing languages struggle only to lose against an ASCII-only general-purpose language)

seems to be 10 bytes in Charcoal, 20% of which are due to working around Sum([]) is None

New Sandboxed Posts

11:38 PM

0

A: Sandbox for Proposed Challenges

Laguerre Polynomials Laguerre polynomials are solutions to Laguerre's equation, a second-order linear differential equation: \$xy''+(1-x)y'+ny=0\$. The polynomials can be found without calculus using recursion: \$L_0(x)=1\$ \$L_1(x)=1-x\$ \$L_{k+1}(x)=\frac{(2k+1-x)L_k(x)-kL_{k-1}(x)}{k+1}\$ Summ...

« first day (3449 days earlier) ← previous day next day → last day (1384 days later) »

Transcript for

Jul '209

The Nineteenth Byte

The Nineteenth Byte: General discussion for codegolf.stackexc...

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile