The Nineteenth Byte

« first day (3052 days earlier) ← previous day next day → last day (2087 days later) »

New Main Posts

01:03

Recent Questions - Programming Puzzles & Code G…: Polish Notation

posted on June 08, 2019 by User A

Unfortunately I can't use the sandbox, as I can't check the CAPTCHA. This is not a duplicate of Reverse Polish Notation, as this uses a different notation to evaluate numbers. The program must accept an input and return the output. For programming languages that do not have functions to receive input/output, you can assume functions like readLine/print. You are …

HyperNeutrino

what happened to this question lol

i'm guessing it's maybe a dupe?

not sure why OP would just delete it otherwise...

4 hours later…

New Main Posts

05:28

Q: Gomoku (5 in a row) implementation

I suspect Gomoku may be one of the simplest games to implement in code. https://en.wikipedia.org/wiki/Gomoku The game is this: players BLACK and WHITE take turns putting down black and white stones. Black traditionally goes first. If, when a player puts down their stone, they now have 5 in a row ...

Xylochoron

06:00

hi if anyone's there, i'm trying to do a challenge on code golf,

i submitted this: codegolf.stackexchange.com/questions/186527/…

someone made a comment saying it might not be specific enough, but I thought i'd specified what the person said I didn't. Also having trouble posting in the sandbox anyway, i click "add proposal" and nothing happens?

oops sorry i think this is the wrong chat room

1 hour later…

Anonymous

07:12

← 4 messages moved from PPCG-gaming

trichoplax

09:41

> Unfortunately I can't use the sandbox, as I am a robot

1 hour later…

New Main Posts

11:09

Q: Insert commas into numbers

Write a program that reads a string, and inserts commas to divide large numbers in groups of 3. i.e. 10000 => 10,000. It must work for multiple numbers on the same line but not for numbers after a decimal point. Example inputs: 10000 10,000 $1234.12 ~$123456789.12345~ HELLO123456.99BYE The_amou...

code-golf regular-expression text-processing

2 hours later…

New Sandboxed Posts

13:11

A: Sandbox for Proposed Challenges

Generate Aheui number Aheui is esolang written in only Korean character. Because of its nature, Aheui can't use Arabic numbers. But, of course, there is way to generate number. Brief introduction to Aheui Reading the link above is best, but put it shortly : Aheui is befunge-like esolang : hav...

3 hours later…

New Main Posts

16:10

Q: In what order we need to put weights on scale?

I' am doing my homework in programming, and I don't know how to solve this problem: We have a set of n weights, we are putting them on a scale one by one until all weights is used. We also have string of n letters "R" or "L" which means which pan is heavier in that moment, they can't be in balan...

math combinatorics programming-puzzle

4 hours later…

Rick

19:52

can a tree have a maximal set and can a graph with cycles have a maximal path?

1 hour later…

flawr

21:17

@Rick what is a maximal set or a maximal path in this context?

Rick

@flawr I've been doing some reading but I am not sure if this is right? "maximal can fall under a broad term, that being inclusion. And that term can be broken down into sets and components. Those being maximal independent sets and maximal connected subgraphs." I was originally confusing maximal path in a tree with maximal set in a planner graph

flawr

I still have trouble understanding, not sure whether it is because of my lack of english skills or lack of knowledge in math

Is this quotation something you wrote?

Usually when we talk about graphs a maximal path could be a path of maximal possible length.

Rick

that quote is just my conclusion after reading many things I found on the topic

flawr

I don't understand what a "set" is supposed to be here.

A set of nodes? Edges? Grahps? Components?

Rick

@flawr non-adjacent vertices

flawr

21:28

So you're asking whether there is a notion of "largest set of non adjecent vertices" in a tree?

It seems to me that this makes sense for all finite graphs.

Rick

well originally I wanted to know what defined a tree and one of the definitions was, to take the maximal path and see if the end vertex had one degree.

flawr

I don't thinkt this works out. Consider a graph comprising a single cycle, and one of the nodes is connected to one additional node outside of the cycle.

Rick

well that wouldn't be a tree

but a maximal path of a tree has two ends with exactly one degree on the end nodes

for example, the letter X can be thought of as a tree

flawr

well then take a cylce with two such appendages

G = (V, E ) with V={1,2,3,4,5}, E = {{1,2},{2,3},{3,4},{4,5},{2,4}}

now the maximal path is (1,2,3,4,5)

but it is still not a tree

Rick

21:44

Assume that some end (let's say vertex A) of the maximal path has degree > 1, which means at least 2.
Now if we consider that the maximal path has at least 2 vertices, this means that one of A's neighbours is in the path. However, the other neighbour isn't a part of the path. So the other neighbour can be added to the path. This contradicts the fact that the path is maximal

I don't think you can have a maximal path in a graph with a cycle

but a set in a graph can be maximal when that graph has a cycle. So long as the vertices in the set are independent.

by independent, I mean no two vertices of the set are adjacent in the graph

and those sets include all possible vertices

flawr

22:18

@Rick ah I see.

so we're talking exclusively about undirected graphs?

Rick

A tree is defined as an acyclic graph. Meaning there exists only one path between any two vertices

I am reasonably positive Trees are technically undirected, but I might be wrong.

flawr

I think you can certainly consider directed trees. (This is important for algorithmic things, otherwise the parent/children relationship would not be well defined.)

At least not without defining a root.

And an acyclic directed graph is not necessarily a tree.

Anonymous

@Rick Trees are more like undirected graphs where each direction between nodes is one of two types, since there's nothing inherent in the definition of a tree that specifies directionality

flawr

22:34

@Mego I think many people do require a tree to be a connected acyclic (undirected)graph with a distinguished node (the root).

Anonymous

Yeah, a distinguished node too

Anonymous

But in basically every use of a tree, the parent->child direction is also distinguished

Rick

@Mego That makes sense. directionality involves indegree outdegree which is not part of the definition for a Tree.

flawr

@Mego this is equivalent to defining a root

Anonymous

Oh i guess it is

flawr

22:39

WP defines two (independent) attributes: directedness and rootedness

New Sandboxed Posts

22:52

A: Sandbox for Proposed Challenges

Is this set doubly ordered? For input you are given a set of four or five sets of strings. Each string is at least two characters long; those first two characters are always digits but the remaining characters can also be letters. The set of sets is doubly ordered if a list can be constructed b...