text:
Is it a doubling sequence?
A doubling sequence is an array of numbers where each subsequent number is at least twice the previous number.
Given an ordered list of numbers, determine if the numbers in the list (\$n_{x}\$) have the property that:
\$n_1 \times 2 \le n_2\$
\$n_2 \times 2 \le n_3\ ...\$
and so on until reaching the end of the list.
Input
A list of two or more numbers.
Output
Any distinct True or False value.
Examples:
[10,20,30] -> False
[10,20,40] -> True
[1,2,3] -> False
[1,2,4] -> True
[1,2,10] -> True
[1,1] -> False
[10,1] -> False

Can input be sorted in either order?

Pre-sorted in that it may be sorted ascending, descending, or some other order, but you don't have to change the order of the list that is fed to the function.

Since inputs can be non-integers, do we care about floating point precision? Many of these solution fail for n_i+1 = n_i*(2-epislon) for some fairly large epsilons

what about negative numbers? what about the sequence of zeros?

"some other order" can be any reflexive transitive antisymmetric relation. In other words, your definition admits arbitrary order of the elements, which I'd guess is not what you intended.

@kyrill, I assume what's meant is that the input list of numbers aren't guaranteed to be in any particular order, however the result could only be True if they are sorted ascendingly. My assumption at least...

I see. That explains the last example.

is this limited to integers or does one have to accommodate decimals also?

R, 27 26 bytes
all(diff(log2(scan()))>=1)

Try it online!
1 byte saved by Giuseppe.

Jelly, 4 (5?) bytes
Monadic link taking the list as input.
I<ṖẸ

If I am allowed to output 0 for Truthy and 1 for Falsy... Otherwise,
I<ṖẸ¬

You can try all test cases!
Notice that \$x_{i+1} \geq 2x_i \iff x_{i+1} - x_i \geq x_i\$.
 <      Compare
I       the forward differences
  Ṗ     with the original list without the last item.
   Ẹ    Check if any comparison returned true
    ¬   and negate that

Jelly, 6 bytes
We can instead take pairwise quotients and check directly if they satisfy the inequality with this monadic link:
÷Ɲ>.Ẹ¬

You can verify all test cases!
÷Ɲ      Compute the quotient for all pairs of elements in the input list.
  >.    See if the elements are greater than 0.5
    Ẹ   and take the "OR" of that list,
     ¬  finishing off with the negation of that.

Any distinct True and False values are allowed, so you can define the distinct True and False values chosen as False and True to eliminate the final ¬.

Japt v2.0a0, 6 bytes
ä÷ e§½

Try it
ä÷ e§½     :Implicit input of array
ä          :Consecutive pairs
 ÷         :  Reduced by division
   e       :All
    §½     :  Less than or equal to 0.5

Haskell, 30 bytes
f(x:s)=any(<2)$zipWith(/)s$x:s

Try it online!
True for false and False for true.

27 bytes as a pointfree function.

Python 3, 37 29 bytes
-8 bytes thanks to xnor.
Fails for doubling sequences, completes otherwise.
f=lambda a,*b:2*a<=b[0]>f(*b)

Try it online!
Python 3, 40 bytes
f=lambda a,*b:b==()or 2*a<=b[0]and f(*b)

Try it online! Test suite by Noodle9.

In your second solution, it looks like you can shorter the check to 2*a<=b[0]*f(*b), it least assuming all values are positive. I'm not sure if the challenge allows switching True and False, but that might also allow a shorter condition. Likewise, the first answer might be shorter if failure corresponds to True, and is achieved when b[0] hits an empty list.

@xnor Thanks for the suggestions, I will look into the second answer later

JavaScript (ES6),  26  24 bytes
Saved 2 bytes thanks to @Grimmy
a=>!a.some(n=>2*a>(a=n))

Try it online!

-2 bytes by reusing a

Husk, 4 bytes
Λ·≤D

Try it online!
Returns 0 if False, a positive number if True.
Λ     Check if adjacent pairs of elements satisfy the predicate
 · D    by doubling the first number
  ≤     and checking if the second number is less than it

Dyalog APL, 8 bytes
∧/2≤2÷/÷

Try it online!

Nice! Beats mine by more than half; would you be so kind as to provide a decomposition/explanation?

Octave, 18 bytes
@(e)istril(e<2*e')

Try it online!
Octave has a nice feature known as broadcasting. Here, we take broadcast less-than of the input and the input doubled, by transposing the input. This creates a matrix of ones and zeroes. Iff this matrix is lower triangular (no nonzero entries above the diagonal), the sequence is a doubling sequence.

Octave, 46 33 31 bytes
@(n)all(2*n(1:end-1)<=n(2:end))

Try it online!
Thanks to Luis Mendo for all. Much shorter!

https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods?page=2&tab=oldest#tab-top Use pre-defined variables as IO is a standard loophole

@Vlo oh, I need to make it a function?

@LuisMendo Nice! I never knew about all...

Since you don't need the name f in your function you can save 2 bytes by not including f= as part of your code and having an anonymous function

Thought you might be interested in seeing a different approach at just 18 bytes.

Python 3, 57 \$\cdots\$ 44 43 bytes
Saved a byte thanks to kaya3!!!
lambda l:all(b>=a*2for a,b in zip(l,l[1:]))

Try it online!

You can save one byte by writing b>=a*2for without the space.

@kaya3 Nice one - thanks! :-)

PHP, 53 49 47 43 bytes
for(;$argv[$i++]*2<=$k=$argv[$i];);echo!$k;

Try it online!
-4 bytes thanks to @Kaddath.

That's actually really clever!

You can save 4 bytes by getting rid of the function: Try it online!

Keg, -rR, 15 13 bytes
1&÷{!;|":'½≤⑾

Try it online!
-2 bytes thanks to @a'_'
Answer History
15 Bytes
1&÷^{!;|":'2*≥⑾

Try it online!
I'm quite happy with this answer, and I'm quite happy with the explanation.
Explained
1&

First, we store the number 1 in the register. This will end up being the means by which the result is shown.
÷^

We then item split the input list and reverse it, so that things are in descending order.
{!;|

Now, we start a while loop that will run while the length of the stack - 1 is not zero.
":'

This bit of the algorithm took me a while to visualise and write... I had to resort to move playing cards around my living room floor to understand which stack shifting mechanics to use.
Lets say the input stack (after item splitting and reversal) is [4, 2, 1]. Right shifting the stack (") gives [1, 4, 2], duplicating the top gives [1, 4, 2, 2] and then left shifting the stack (') gives [4, 2, 2, 1].
We do this so that we can compare the top of the stack with the next item and preserve that second item (in other words, circumnavigate the side effects of operators consuming stack items).
2*≥

We then multiply the top item by two and see if the result is greater than or equal to the next item in the series.
⑾

The result is then augmented multiplied into the register and the while loop continues.
-rR prints the value of the register at the end of execution as an integer.

-2 bytes after not reversing the stack before the operation.

Ruby, 31 bytes
->l{x,*l=l;l.all?{|y|x*2<=x=y}}

Try it online!

05AB1E, 4 3 bytes
Crossed out 4 is still regular 4 ;(
¥›à

Outputs 0 for truthy and 1 for falsey.
Port of @RGS' first Jelly answer, so make sure to upvote him!
-1 byte thanks for @Grimmy for mentioning any two distinct truthy/falsey values are allowed, so I can drop the invert at the end
Try it online or verify all test cases.
Explanation:
¥    # Get the deltas (forward differences) of the (implicit) input-list
 ›   # Check for each whether it's larger than value at the same position in the (implicit)
     # input-list, which automatically ignores the trailing item of the input
  à  # Get the maximum of this, to check if any are truthy
     # (after which it is output implicitly as result)

The spec allow Any distinct True or False value, so you can cut the _.

@Grimmy Ah, hadn't noticed that. Thanks!

Clojure, 42 40 bytes
(fn[s](every? #(<= 2%)(map /(rest s)s)))

Try it online!
Basically the obvious pairwise thing, with a fun way to generate consecutive pairs of a sequence.

But it is still a tad shorter to reverse the comparison to a more common every?. And amusingly enough, Clojure also doesn't complain after removing the space after 2 :)

not-any? What a confusing way to spell none.

@KirillL. good catch.

Lua, 54 bytes
for i=2,#arg do b=b or arg[i-1]*2>0+arg[i]end print(b)

Try it online!
true and false are swapped.

Desmos, 41 Bytes
f(n)=1-l(n[2n[0...l(n)]>n])
l(n)=n.length

Try It Over Here

PowerShell, 49 bytes
param($n)($n|?{$_-ge2*$l;$l=$_}).count-eq$n.count

Try it online!
Takes input $n then uses a Where-Object to pull out those elements that are -greaterthanorequal to 2 times the $last element. Those are left on the pipeline, and we set our $last element for the next iteration. We then take the .count of that collection and make sure it's -equal to the .count of our input array. That Boolean value is left on the pipeline and output is implicit.

If we don't need to worry about negative numbers, we can use the following instead, thanks to mazzy:
PowerShell, 27 bytes
!($args|?{$_-lt2*$l;$l=$_})

Try it online!
This again takes input $args, and pulls out those items where they're -lessthan 2 times the $last element (i.e., they're not "big enough" to make the doubling sequence). If there are any left, then the Boolean-not surrounding the collection results in False, otherwise if the collection is empty we get True. That's left on the pipeline and output is implicit.

J, 14 bytes
[:*/0.5>:2%/\]

Try it online!

x86-16 machine code, 11 bytes
49          DEC  CX                 ; adjust to loop N-1 times
        N_LOOP:
AD          LODSW                   ; load N1 into AX
D1 E0       SHL  AX, 1              ; double AX
39 04       CMP  WORD PTR[SI], AX   ; compare to N2
7C 02       JL   DONE               ; if less, return
E2 F7       LOOP N_LOOP             ; keep looping
        DONE:
C3          RET                     ; return to caller

Input array at [SI], length in CX.  Returns ZF if truthy, NZ if falsey.

GolfScript, 28 bytes
GolfScript has its clunky zip function (I need a lot of code to convert the string to a list of codepoints).
.1>]zip);{1/~0=\0=2*<!}%{&}*

Try it online!
Explanation
.1>]zip                      # Zip itself with itself without the first item
       );                    # Discard the extra trailing item
         {1/~0=\0=2*<!}%     # Is the first item * 2 greater than or equal to the next item?
                        {&}* # All of them?

GolfScript, 31 bytes
.(+{2/}%]zip);{1/{0=}%~>!}%{&}*

Try it online!

Pyth, 11 bytes
<1hS/MP.T,t

Try it online!
Explanation
<1hS/MP.T,tQQ  # full program, last two Q (=input) are implicit

         ,tQQ  # [Q[1:], Q]
       .T      # Transpose -> [[Q[1],Q[0]], [Q[2],Q[1]], ...,  [Q[-1]]]
      P        # all but last element (gets rid of lone Q[-1])
    /M         # Map all pairs by division
   S           # Sort quotients
  h            # first element (minimum quotient)
<1             # is 1 smaller than this?

Burlesque, 15 bytes
raJ0{2.*>=}LO==

Try it online!
Finally got an answer where using LO is advantageous.
ra   # Read as array
J    # Duplicate
0    # 0 (start of loop)
{2.* # Double
 >=  # Greater than or equal to previous elem
}LO  # Loop through array performing op on each pair
     # Push to array if true
==   # Arrays are the same

Burlesque, 16 bytes
Alternative (but longer) solutions using 2-grams and map-reduce
ra2CO{./2>=}m^r&
ra2CO{p^./2>=}al

Try it online!

Wolfram Language (Mathematica), 25 15 bytes
Min@Ratios@#<2&

Returns True for false and False for true.
-10 bytes thanks to @att
Try it online!

15 bytes

Pip -r, 11 bytes
$&2*_<=BMPg

Try it online!
Takes input numbers separater by newlines. (-r flag)
Explanation
$&2*_<=BMPg  g → input
        MP   pass pairs from g to function on the left
  2*_<=B     a ≤ b? for pair (a, b)
$&           Fold with & operator

Proton, 41 bytes
a=>all([a[x+1]/a[x]>=2for x:0..len(a)-1])

Try it online!
This isn't very efficient because Proton is too buggy to do this right.

Arturo, 29 28 bytes
$=>[l:0every?&'x[x>=l*2l:x]]

Try it

Pyt, 6 bytes
↔ʁ/2≥Π

Try it online!
Outputs 1 if doubling array, 0 otherwise
↔           implicit input; flip array
 ʁ/         ʁeduce by division
   2≥       is each element greater than or equal to 2?
     Π      take product of list; implicit print

><> (Fish), 27 bytes
rl1)?v1n;n0<
@:$+:<|.!:0^?)

Try it

r reverse
l1)? is the length greater than 1?
v then go down
1n; otherwise, output 1 (true)
< go left
:+ double
$:@ duplicate NOS
)? is NOS greater than TOS?
^<0n; then output 0 (false)
0:!.| go back to start after inverting direction

StackCell, 16 bytes
:[{::+}x>?.:]'Y;

Assumes that the input list is already present on the stack (with the earliest element on the bottom of the stack, as it would be as a result of repeated pushing), and does not contain a 0 (will be interpreted as end of input) - For stack-based languages, function's input may be pushed to the stack before calling

To run the program, prepend the input in hex, with hashes, e.g. #01#02#04:[{::+}x>?.:]'Y; to run the program on [1, 2, 4]

Either prints Y (the input is a doubling sequence) or terminates without output (the input is not a doubling sequence) - Programs and functions may return a boolean value via the presence or absence of output

Explanation:

:[: Duplicate the top element of the stack, and then consume the duplicate. If it was non-zero, perform the loop body (up until the next ]) - else skip the loop body
{: Remove the top element of the stack, and place it in the 'cell' (temporary storage which is overwritten on writes and copied on reads)
::+: Create two duplicates of the top element of the stack (previously the top-but-one element), and add them together to get 2x
}: Put the stored element back on the top of the stack
x: Swap the top two elements of the stack
>: Consume and compare the top two elements of the stack: If the top-most element is larger than the second-most element of the stack, push 1 to the stack, otherwise push 0 to the stack
?: Consume the value on top of the stack, and skip the next instruction (.) if and only if the consumed value was 0
.: Halt the program immediately (falsy output)
:]: Duplicate the top value of the stack, then consume the duplicate. If it was non-zero, jump back to the instruction after the matching [; otherwise, continue
'Y: Push the character Y to the stack, as a byte
;: Print the top value of the stack, as a character

Nekomata + -e, 4 bytes
∆$i≥

Attempt This Online!
-e      Check that
∆       the delta
   ≥    is greater than or equal to
 $i     the original list without the last item

C (clang), 38 bytes
Returns 0 for doubling sequences, 1 otherwise.
f(*a,s){return--s?*a*2>*++a|f(a,s):0;}

Try it online!

Scala, 48 bytes
Golfed version. Try it online!
_.sliding(2).map{case Seq(a,b)=>b/a}.exists(_<2)

Ungolfed version. Try it online!
object Main {

  def f(x: List[Double]): Boolean = {
    x.sliding(2).map { case List(a, b) => b / a }.exists(_ < 2)
  }

  def main(args: Array[String]): Unit = {
    val data = List(
      List(10.0, 20.0, 30.0),
      List(10.0, 20.0, 40.0),
      List(1.0, 2.0, 3.0),
      List(1.0, 2.0, 4.0),
      List(1.0, 2.0, 10.0),
      List(1.0, 1.0),
      List(10.0, 1.0)
    )

    println(data.map(f))
  }
}

Desmos, 27 bytes

f(l)=\{l[2...]<2l,0\}.\max

Returns 0 for doubling sequences and 1 for non-doubling sequences.
Try It On Desmos!
Try It On Desmos! - Prettified

Vyxal G, 3 bytes
¯>Ṫ

Try it Online!
A port of 05AB1E
Explained
¯>Ṫ
¯   # deltas
 >  # greater than original input
  Ṫ # last item removed
# G flag gets biggest item.

Kotlin, 50 bytes
{a:IntArray->(0..a.size-2).first{a[it]*2>a[it+1]}}

Try it online!
Int for false and Nothing for true (throws NoSuchElementException)

Retina 0.8.2, 28 bytes
\d+
$*
((^|,(?=\3\3))(1+))+$

Try it online! Link includes test cases. Explanation:
\d+
$*

Convert to unary.
  ^|

On the first repeat, match at the beginning, otherwise...
    ,(?=\3\3)

... match a comma followed by a number which is at least twice as big as the previous match.
              (1+)

Capture the number so that it can be compared on the next repeat.
(                 )+$

All entries in the list need to satisfy the above conditions.

Clojure, 89 bytes
(fn[x](#(cond(empty? %)true(>=(first %)(* %2 2))(recur(rest %)(first %)):else false)x 0))

Try it online!
The obvious (and longest) solution to the problem.

Perl 5 -apl -MList::Util=reduce, 26 bytes
reduce{$_&&=$a<=$b/2;$b}@F

Try it online!

Python 3, 52 bytes
lambda l:all(2*l[i]<=l[i+1]for i in range(len(l)-1))

Try it online!

Zsh, 29 bytes
(($1*2<=$2))&&${=3+$0 ${@:2}}

Try it online!
(($1*2<=$2))&&     # return false if 2 * $1 > $2
  ${=3+$0 ${@:2}}  # recursive call:
  ${ 3+         }  # if there is a third parameter
       $0 ${@:2}   # ... substitute the program name ($0), " ", "$2 $3 $4 "...
  ${=           }  # ... then split on spaces

In cases like a && or b ||, Zsh will simply return with the exit code of the previous command.

Python 3, 52 bytes
lambda l:all(l[i-1]*2<=l[i]for i in range(1,len(l)))

Try it online!

APL (Dyalog Extended), 18 bytes
∧/{(2×¯1↓⍵)≤(1↓⍵)}

Try it online!
Decomposition/Explanation:
⍵ is the input vector (test cases). Output will be 1 or 0; 1 is TRUE/truthy, 0 is FALSE/falsey.

            (1↓⍵)  - Drop the first element from the input vector (call it LASTN)
      ¯1↓⍵         - Drop the last element from the input vector, separately, and
   (2×    )        - multiply it by two (call the result DFIRSTN)
           ≤       - compare corresponding elements - Each element of LASTN should be
                     equal to or greater than the corresponding element of DFIRSTN.
  {              } - encapsulate as a dfn to apply to the input vector. This dfn will
                     return 0 for elements where the comparison is FALSE, 1 where TRUE
∧/                 - AND (Boolean conjunction) reduction of the vector. ∧/ A B C D ... is
                     equivalent to A ∧ B ∧ C ∧ D ∧ ..., and if there are any FALSE values
                     in the vector, the result will be FALSE (0)

The linked TIO has the test cases and a REPL; you can test your own vectors by changing the input field, one vector per line.

T-SQL, 64 bytes
This can handle positive values above 0
Returns -1 for true, 0 for false
SELECT~min(1/~x)FROM(SELECT a/lag(2*a)over(ORDER BY i)x FROM @)y

Try it online

C (gcc), 51 bytes
r;f(a,l)int*a;{for(r=--l;l--;)r=*a*2>*++a?0:r;a=r;}

Pretty simple. For every element of the array, check if the current element times two is greater than the next element.
Returns zero if it is not a doubling sequence and non-zero (or more specifically the length minus one) otherwise.
-10 bytes thanks to ceilingcat!
Try it online!

@ceilingcat Thanks. I was trying to find a solution with no counter variable.

49 bytes

C++ (gcc), 75 71 67 65 bytes
int f(int*a,int s){int r=1;for(;--s;)r*=a[s]>=2*a[s-1];return r;}

Try it online!

@ceilingcat Thanks for the input! I thought the i++ placement was UB, so I dumped the variable - 67 bytes!

@ceilingcat Should've thought of that!

64

Rockstar, 101 100 bytes
listen to F
D's0
while F
listen to T
let R be F/T-.5
turn up R
let D be D or R
let F be T

say not D

Try it here (Code will need to be pasted in, with each input integer on an individual line)

Thunno 2 S!, 4 bytes
Ṣ$ṫ<

Try it online! Link is to verify all test cases.
Explanation
Ṣ$ṫ<  # Implicit input
Ṣ     # Deltas of input
 $ṫ   # Input without last item
   <  # Compare the two lists
      # Check if the sum is 0
      # Implicit output


text:
Gossipping ladies
Problem description
Vertices \$V\$ of directed graph \$G=(V,E)\$ represent gossipping ladies; edge \$(u,v) \in E\$ signifies that lady \$u\$ knows of lady \$v\$ (which does not imply that lady \$v\$ knows of lady \$u\$). Assume that each lady knows of herself.
Intuitively, lady \$a\$ gossips about every lady \$b\$ she knows about, except herself, to every other lady \$c\$ whom \$a\$ knows about (other than \$b\$ herself). Lady \$c\$, upon hearing gossip from lady \$a\$ about lady \$b\$, will learn about \$b\$ but not about \$a\$. For \$c\$, this then means two things:

\$c\$ will from now on gossip about \$b\$ to all other ladies she knows about, and
\$c\$ will from now on gossip to \$b\$ about all other ladies she knows about, except about her own self.

Formally, the Gossip Operation \$g(G)\$ produces a graph \$G' = (V, E')\$, where
$$E' = E \ \cup\ \{(c,b) \ \vert\ \exists\ (a,b) \in E : a \neq b \ \land\ \exists\ (a,c) \in E: c \neq b \}$$

(Added edges in red.)

The Gossip Closure of a graph \$G\$ is the fixed point of the Gossip Operation starting from \$G\$.
Example
Input:

a:{a,b,c,d}
b:{b,e}
c:{c,d}
d:{d}
e:{e}
f:{f,a}
g:{g}

Output:

a:{a,b,c,d}
b:{b,e,c,d}
c:{c,d,b,e}
d:{d,b,c,e}
e:{e,b,c,d}
f:{f,a}
g:{g}

Larger example
Original graph
After one iteration
Closure
Loops not shown in graphs.
Task
Implement an algorithm of lowest possible time complexity, which given an directed unweighted graph* \$G\$ in any suitable format (viz. any format supporting directed unweighted graphs), outputs its Gossip Closure.
* You may impose certain limits on the input, eg. an upper bound on graph density if your solution is better suited for sparse graphs.

Thanks for the challenge! Could you give an example of a graph and its Gossip Closure, to clarify the definition? Also, are self- loops allowed? Can b=c?

I clarified the definition a bit: each vertex implicitly has a loop. I will add an example later.

Just to verify;

lady a gossips about every lady she knows about
each lady knows of herself
Wouldn't that mean every lady gossips about herself? Do you mean to add another "other" in the first clause; "a gossips about every other lady b she knows about to all other ladies a knows about"? That way these relationships stay one-sided.

@Mathgeek Yes, that's how it was intended. The condition that each lady knows of herself was added later and I forgot to update the definitions. I believe the definition is now complete.

Regarding "lowest possible time complexity", graph algorithm time complexities are often stated in terms of the number of edges and number of vertices. Algorithms may do differently on sparse graphs or dense graphs, or depending on the input representation (edge lists, adjacency matrix, etc). Could you clarify this?

I think the math notation in the problem statement is too much and makes it intimidating, despite the good explanation in terms of gossip. Would it not work to say that the gossip closure of a graph G is the smallest graph G' that contains all the edges of G, and that whenever (a,b) and (a,c) are edges of G', so is (b,c)? Though now having written that, it seems like all edges between pairs of a,b,c end up in the closure this way.

@xnor I agree that the formal problem statement may be intimidating to some, but without a rigorous mathematical definition it would be ambiguous or incomplete. As per complexity, any solution X which takes the same kind of input (eg. restructed to "dense" / "sparse" graphs) as some solution Y and has a lower complexity, wins over such Y.

Frankly, I think this problem needs work before it's a good challenge. First, while you have clarified the winning criterion, @xnor's question about the lowest possible time complexity is still an issue. Moreover, the problem itself is pretty degenerate for most cases, as if $(a,b)$ and $(a,c)$ are edges in a graph, then $b\leftrightarrow c$ after one move. In other words, there is nothing that distinguishes $b$ from $c$. So, the general premise of any solution posted will be just taking combinations of nodes that are pointed to by one node, and adding bidirectional edges between these

combinations. Not only does that mean that most graphs (including sparse ones) will become dense, but they will become dense in a way that is quite uninteresting from a programming standpoint, as any language with a well implemented combinatorial library can just plug and chug.

@DonThousand Firstly, "just taking combinations of nodes that are pointed to by one node, and adding bidirectional edges between these" will accomplish one step of the operation; I am interested in the closure. Secondly, the challenge I am posing here is not to "plug and chug" into some combinatorial library and arrive at a short but inefficient solution. The challenge is to come up with an efficient algorithm; the key words being "come up with" and "efficient". If that is uninteresting for you then leave it.

Prolog
:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(pio)).

:- op(950, fx, *). *_.

% Read the data.
space --> " ", space.
space --> "".

seq([]) --> [].
seq([S|Ss]) --> [S], seq(Ss).

lines([L|Ls]) --> seq(L), "\n", lines(Ls),
    { \+ member('\n', L) }.
lines([]) --> [].

graph(S1-S2) --> space, seq(S1), space, ":", space, vertices(S2), space.

vertices([]) --> [].
vertices([V|Vs]) --> seq(V), space, ",", space, vertices(Vs).
vertices([V]) --> seq(V).

% Solve.

merge_vertices(Vs, Ws, Xs) :-
    append(Vs, Ws, Xs0),
    sort(Xs0, Xs).

merge_edges(As, Bs) :-
    merge_edges_(As, [], Bs1),
    keysort(Bs1, Bs).

merge_edges_([], Cs, Cs).
merge_edges_([A|As0], Bs0, Cs) :-
    U-Vs = A,
    (   select(U-Ws, As0, As1)
    ->  merge_vertices(Vs, Ws, Xs),
        append([U-Xs], As1, As),
        Bs = Bs0
    ;   append([A], Bs0, Bs),
        As = As0
    ),
    merge_edges_(As, Bs, Cs).

create_edges([], []).
create_edges([_], []).
create_edges(Vs0, Es) :-
    Vs0 = [_,_|_],
    findall(V-Vs, select(V, Vs0, Vs), Es).

gossip(G0, G) :-
    gossip_(G0, [], G).

gossip_([], G, G).
gossip_([E|Es], G0, G) :-
    U-Vs1 = E,
    (   select(U, Vs1, Vs)
    ->  true
    ;   Vs = Vs1
    ),
    create_edges(Vs, G1),
    append([E|G0], G1, G2),
    merge_edges(G2, G3),
    gossip_(Es, G3, G).

limit_gossip(G, G) :-
    gossip(G, G).
limit_gossip(G0, G) :-
    gossip(G0, G1),
    limit_gossip(G1, G).

build_graph(G, L) :- phrase(graph(G), L).

writeln(X) :-
    writeq(X), nl.

output(G) :-
    maplist(writeln, G).

test :-
    once((
        phrase_from_file(lines(Ls), 'g.txt'),
        maplist(build_graph, G1, Ls)
    )),
    limit_gossip(G1, G),
    output(G),
    halt.

:- initialization(test).

$ cat g.txt
a:a,b,c,d
b:b,e
c:c,d
d:d
e:e
f:f,a
g:g

[Complexity]: \$O(V^2\ln V)\$
Where \$V\$ is the number of vertices.

Note, library(dcgs) is not necessary (or even available) in SWI-Prolog.

Could limit_gossip be defined like this while preserving the original functionality and complexity? I think it could but I'm not sure, since I'm not exactly well-versed in Prolog.

Also, for $ cat g.txt you probably meant to include the original graph as given in the task description, not the closure.

Thanks, for limit_gossip and cat g.txt. The library(dcgs) is for reading the data from a file, it's a bit different from SWI-Prolog but I'm using Scryer-Prolog.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Count regex matches
Your task
Given a simple regular expression, you have to count how many strings of length n have a match of length n with the given simple regex. This will just be a subset of regexs. Like, no lookaheads or named groups or recursion or whatever weird things regexs have.
Simple regular expression
For the purposes of this challenge, a regex is said to be simple if, for one, it only contains characters in the ASCII range 32-126. Furthermore, it should only use the following functionalities:

match literal characters, much like the regex abc would only match the string "abc";
match options, like abc|def would match "abc" and "def";
match exactly 0 or 1 occurrence of something, e.g. https? matches "http" and "https";
match 1 or more occurrences of something, e.g. ah+ would match "ah", "ahh", "ahhh", "ahhhh", etc;
match any amount of occurrences of something, e.g. 1* matches "", "1", "11", "111", "1111", etc;
match between n and m occurrences of something, e.g. lo{1,4}l matches only "lol", "lool", "loool" and "looool". If n is ommited, it matches up to m occurrences. If m is ommited, it matches at least n occurrences. Assume at least one of n or m is present;
use () to group, e.g. ab(c|d)ef would match "abcef" and "abdef" (c.f. 2nd item in this list) or (10)+ would match "10", "1010", "101010", "10101010", etc;
use . to match any character (in the ASCII range [32, 126]), so ab. would match "abc", "ab9", "ab)", etc;
use \ to escape the special meaning of a character, e.g. ab? would match "a" and "ab", while ab\? only matches "ab?";
use [] as a group of possible characters. Inside the brackets, all characters lose their special behaviours, except for - and \. This means that, for one, ab[cde] is shorthand for ab(c|d|e) and secondly, ab[?+*] matches "ab?", "ab+" and "ab*"; also related to []:
use - to specify a character range within brackets. The ranges you have to support are a-z, A-Z and 0-9, as well as their subsets, like h-z or 3-8. E.g., the regex ab[c-g] matches "abc", "abd", "abe", "abf" and "abg"; Note that - has no special meaning outside of [] so a-z would only match "a-z".

Input
The input for your program/function/routine/etc should be a string representing the regex and an integer n. For the regex, you can further assume:

all characters that show up are in the ASCII range [32, 126]
if {n,m} is used, then \$n \leq m \$
if - is used inside [] then the specified range is well-formed

Output
The number of strings of length n that match the given regex. You only have to account for characters in the ASCII range [32, 126].
Test cases
".*", 0 -> 1
".*", 1 -> 95
".*", 2 -> 9025
".*", 3 -> 857375
".*", 4 -> 81450625
"abc", 2 -> 0
"abc", 4 -> 0
"ab|ac|ad", 2 -> 3
"a(b|c)", 2 -> 2
"hell(o|oo)", 5 -> 1
"https?", 5 -> 1
"ho{1,4}ly", 6 -> 1
"ho{3,}ly", 137 -> 1
"[abcde]{,2}", 2 -> 25
"(10)+", 7 -> 0
"(10)+", 8 -> 1
"ab\?", 3 -> 1
"[t7]h[i1][s5] is c[0o]d[Ee3] g[0oO][l1L]f", 17 -> 432
"\+351 9[1236] [0-9]{3,3} [0-9]{2,2} [0-9][0-9]", 17 -> 40000000
"-", 1 -> 1
"\\", 1 -> 1
"[+?*]", 1 -> 3
"Abc([d-z]*|(.H)+)", 11 -> 5132188812826241
"ab|ab", 2 -> 1
".(.(.(.(.|a))))|hello", 5 -> 7737809375

This is code code-golf so shortest solution in bytes, wins. If you like this challenge, consider upvoting it... And happy golfing!

Okay, I count 4 regex matches. Do I win? :P

@Lyxal python, 12 bytes, lambda s,n:4

Keg, 1 byte: 4. :P

Suggested test case: one containing {n:m} without n (i.e. "[abcde]{:2}", 2 -> 25)

Was the notion of simple regex an attempt at allowing someone to solve this by other means than brute force? (If yes, I think it's still much too complicated for that, as almost all key features of regular expressions are included.)

@Arnauld yes D: would you suggest further trimming down the specs of a simple regex? To what?

@RGS I would not recommend to change the spec now. But for another challenge, it might be interesting for instance to just count the number of strings matching a sequence of [...], e;g. [ac-f][xyz] -> 15, without \\ escaping or any other nasty features.

@Arnauld Thanks for your feedback! And what about the +*? "modifiers"? Would you think they make for a good addition?

I don't know for sure. The more features you add, the less likely you'll get non-brute-force solutions.

Java 10, 356 342 284 275 233 225 220 bytes
import java.util.*;List S;r->k->{S=new Stack();p("",k);k=0;for(var p:S)k+=(p+"").matches(r.replaceAll("\\{(,\\d+\\})","{0$1"))?1:0;return k;}void p(String p,int k){if(k<1)S.add(p);else for(char i=32;i<127;)p(p+i++,k-1);}

Works, but way too slow for \$n\geq4\$.
Try it online.
Explanation:
import java.util.*; // Required import for Stack and List
List S;             // List on class-level, uninitialized

k->r->{             // Method with integer and String parameter and integer return-type
  S=new Stack();    //  Create a new List
  p("",k);          //  Put all permutations of length `k` consisting of printable ASCII
                    //  characters in this list
  k=0;              //  Re-use `k` as counter-integer, starting at 0
  for(var p:S)      //  Loop over all permutations in the List:
    k+=             //   Increase the counter by:
       (p+"")       //    Convert the permutation from Object to String
       .matches(r   //    If it matches the input-regex,
         .replaceAll("\\{(,\\d+\\})","{0$1"))?
                    //    after we've replaced all {,m} with {0,m}
          1         //     Increase the counter by 1
       :            //    Else:
          0;        //     Leave the count the same by increasing with 0
  return k;}        //  And return the counter as result

void p(             // Separated method with two parameters and no return-type, where:
    String p,       //   `p` is the prefix-String, starting empty
    int k){         //   `k` is the length the permutations we want to generate
  if(k<1)           //  If `k` is 0:
    S.add(p);       //   Add the current prefix-String to the List
  else              // Else:
    for(char i=32;i<127;)
                    //  Loop over the printable ASCII characters:
      p(            //   And do a recursive call, with:
        p+i++,      //    The prefix-String appended with the current character
        k-1);}      //    And `k` decreased by 1

Some notes:

Java's regex only supports {n,m} and {n,}, since {,m} could be written as {0,m}.
And Java's String#matches builtin implicitly adds a leading ^ and trailing $ to check the entire String.

Will wait for further golfing and explanation :D

Will leave a comment appearing to be commenting on the answer but actually end up being a meta continuation of a now existent joke.

Good luck with that, hope it beats my brute-force solution!

@RGS I doubt it.. Java's regex uses {n,m} instead of {n:m}, so I have to account for that. In addition, it only supports {n,} and {n,m} (since {,m} can be {0,m}). So some bytes are already lost there in comparison to your answer. And Python just has better/shorter builtins in general tbh.. :)

Python 3, 139 137 129 bytes
Saved 2 naughty bytes thanks to @Kevin, then 6 thanks to @ovs and then 2 more by rewriting f, thanks to @wilkben!
lambda r,n:sum(1for s in map(''.join,i.product(map(chr,range(32,127)),repeat=n))if re.match(f"^{r}$",s))
import re,itertools as i

You can try the smaller test cases online. My solution generates all strings of length n with the generator g and then tries to match the regex to the whole string. If the test case is the regex r, I use the regex ^r$ to force the match to be on the whole string.

This fails on any test case that uses the {n:m} syntax, since Python regexes don't have that (see the [abcde]{:2}, 2 -> 0 X in the results of your test suite).

@Grimmy you are absolutely right! My problem was that I wrote the challenge believing the syntax I knew was {n:m} and didn't even check it. Since there is only one other answer that also benefits from me correcting the syntax to {n,m} which was what I intended, I edited the OP. Thanks for being on the lookout! Now the test cases are fine :)

g can be 6 bytes shorter with some rearrangements: g=lambda n:[""][n:]or(s+chr(c+32)for c in range(95)for s in g(n-1)).

-8 bytes using itertools
lambda r,n:sum(1for s in map(''.join,i.product(map(chr,range(32,127)),repeat=n))if re.match(f"^{r}$",s)) import re,itertools as i

JavaScript (Node.js), 86 bytes
Another brute-force solution taking input as (n)(regex).
n=>g=(p,s='',c=127)=>n*!s[n-1]?--c>>5&&g(p,s+Buffer([c]))+g(p,s,c):!!s.match(`^${p}$`)

Try it online!
Commented
n =>                      // n = target string length
  g = (                   // g is a recursive function taking:
    p,                    //   p = regex pattern
    s = '',               //   s = current string
    c = 127               //   c = current ASCII code
  ) =>                    //
    n * !s[n - 1] ?       // if n is not equal to 0 and s is less than n char. long:
      --c >> 5 &&         //   decrement c; if it's greater than or equal to 32:
      g(                  //     do a 1st recursive call where:
        p,                //
        s + Buffer([c])   //       the character with ASCII code c is added to s
                          //       c is not passed so that it's reset to 127
      ) +                 //
      g(                  //     do a 2nd recursive call where:
        p, s, c           //       this value of c is discarded
      )                   //
    :                     // else:
      !!s.match(`^${p}$`) //   return true (1) if s matches p, or false (0) otherwise

+1 Looking good! I see you also had to do the ^_$ tweak :)

I have the feeling you can contribute so many tips to the JavaScript tips page xD I.e. the Buffer([c]) to convert from integer to character. PS: Why do codegolfers always like to obscure their code? ;) The >>5 can simply be >31 (which imo makes it a lot more readable). Not that it matters here, since the byte-count remains the same, but stil.

@KevinCruijssen Buffer() doesn't exist in JS. It's a Node thing. So maybe we need a Node tips page, but I'm not sure there are enough Node-specific tricks to justify it. Or maybe we should include Node in Tips for Golfing in ECMAScript 6 and above.

perl -E, 79 bytes
($,,$")=@ARGV;@@="";@@=map{$,=$_;map$,.chr,32..126}@@for 1..$,;say~~grep/$"/,@@

Welcome to this community! Can you please include a tio.run link, so that people can check your code passes the test cases? :)

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Predictor Generator
Write a program that when given a string \$S\$, it generates a program of the same language as itself.
The generated program, when given a continuous substring of \$S\$, should predict the next character in an occurence of the subtring in \$S\$. You are guaranteed that this substring occurs exactly once in \$S\$ and does not occur at the end of \$S\$. \$S\$ will be a string of at most \$10000\$ characters consisting of only lowercase English letters.
The program that you are submitting will only be given \$S\$. The program that your program generates will be given a list of substrings and should return a list of answers in an acceptable format.
This is code-challenge, and the scoring criterion is as follows:
The score of the generated program is equal to \$\frac{|S|c}{1+Lt}\$, where \$|S|\$ is the length of the string, \$c\$ is the number of correct predictions, \$L\$ is the length of the generated program, and \$t\$ is the total number of predictions.
The score of your submission is the minimum score of your generated programs across all testcases.
Users are welcome to "hack" other people's submissions by proposing new test cases in order to decrease submissions' scores.
Some example test cases can be found here (currently only two test cases, I will add more later).

"Across all testcases" means over everyone's answers? Does this mean you don't know your score when you submit?

"Across all testcases" means min(score of the generated program for S) for your submission. (Can someone verify the link works?)

I'm confused then what you mean about hacking other users' submissions. How can you affect their scores?

@xnor Maybe he meant has "hack" as in codeforces, I think. The person have to write code again -> (maybe more increased length?)

The hacker can propose a test case, and since your score is the minimum for all the test cases, your score will decrease if your generator performs particularly badly on a certain case.

@jaeyongsung Well the person's code may just perform very badly, causing their score to decrease, and everyone's scores will be asked to be re-evaluated (I do mean codeforces' hacking system(

Oh, I see. It's really not clear though that users can add test cases, since usually these are written into the spec. And is this really better than just being required to prove that your program meets a score threshold? I understand it might not be obvious what the worst case is, but it seems to me it shouldn't be hard in practice.

I'd really suggest putting this challenge in the Sandbox, both as general advice, and because this challenge has unusual format and scoring which can be both hard to balance well and hard to explain clearly.

And maybe I'm missing something, but does anything stop me from "proposing" a random string of 10,000 lowercase letters along with a single random substring that appears once? Then, any program that doesn't guess the next letter gets a score of 0. And because my string is random as is the position of the substring, I think any generator has to encode the full string S, or a packed form, in is code. And this makes it seem like optimally compressing strings of lowercase letters into the character-space of your language is a crucial part of the challenge.

You definitely want to rethink that scoring formula. Right now, the only possible score is 0: nothing prevents me from adding a test case where S is the empty string, right? And even if you ban the empty string, now the score is 1 / (1 + length of the program generated for a length-1 test case).


text:
Are They Similar Polygons?
Task
Given the x,y coordinates (coordinates are guaranteed to be integers) of the vertices of two simple polygons in clockwise or anti-clockwise order. Output a Truthy value if both the polygons are similar otherwise a Falsy value
A simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If the sides intersect then the polygon is not simple. Two edges meeting at a corner are required to form a an angle that is not not straight (180°)
Two polygons are similar if either polygon can be rescaled, repositioned, and reflected, so as to coincide precisely with the other polygon.
Testcases
Input
[(0, 0), (1, 0), (1, 1), (0, 1)]
[(-1, 0), (2, 1), (1, 4), (-2, 3)]

Graph
Output
Truthy

Input
[(2, 3), (0, 0), (4, 0)]
[(-3, 0), (-2, 2), (0, 1), (1, -1), (-1, -2), (-2, -2)]

Graph
Output
Falsy

Input
[(1, 4), (1, 3), (0, 2), (1, 1), (-3, 2)]
[(2, 0), (2, -1), (3, -1), (4, -2), (-2, -2)]

Graph
Output
Falsy

Input
[(-1, 0), (2, 1), (1, 4), (-2, 3)]
[(1, 4), (2, 1), (-1, 0), (-2, 3)]

Graph
Output
Truthy

Input
[(-2, 0), (-1, 1), (0, 1), (1, 3), (1, 0)]
[(5, 4), (4, 2), (3, 2), (2, 1), (5, 1)]

Graph
Output
Truthy

Input
[(2, 13), (4, 8), (2, 3), (0, 8)]
[(0, 0), (5, 0), (8, 4), (3, 4)]

Graph
Output
Falsy

Input
[(-1, 0), (-5, 3), (-5, 9), (-1, 6)]
[(0, 0), (5, 0), (8, 4), (3, 4)]

Graph
Output
Falsy

Input
[(0, 0), (1, 2), (1, 0)]
[(2, 0), (2, 2), (3, 0)]

Graph
Output
Truthy

This needs way more falsy test cases! For starters: non-similar rhombi (defeats submissions that only check side lengths); non-similar rectangles (defeats submissions that only check angles). Also, I'd suggest cutting down on the diagrams: one or two are enough to get the idea, beyond that I'd rather have all the test data in a convenient text format.

@Grimmy, thanks for the suggestions working on more testcases.

Ok @Mukundan and what about the fact that the tests might have different lengths?

Are all vertices of each polygon guaranteed to be different?

Is the penultimate test case really falsy?

In the interests of being self-contained, the definition of "similar" should be included in the spec.

@Arnauld, Thanks for pointing that out fixed the sixth testcase

@LuisMendo All vertices of each polygon are guaranteed to be different

@RGS No, I don't plan on changing the question to be for only polygons with same number of vertices

Related: Similar triangles

The pictures you have drawn are great. Are you sure you don't want to include them in the question? You just need to lay them out so they don't use too much space.

Mathematica, 97 bytes (SBCS)
Or@@(Equal@@(a@u/#)&/@(a/@NestList[RotateLeft,v,Length@v]))
a@l_:=Norm[#〚1〛-#〚2〛]&/@l~Subsets~{2}

You can try it online!
The function a computes all the pairwise distances between any two vertices of the polygon.
The main function applies this to the first list and to every rotation of the second list, to try and find the corresponding vertices. The rotation of the second list is correct if all the corresponding distances have been scaled accordingly.
Thanks to @J42161217 for saving me some 3 bytes

@Grimmy I was still updating the link :) It should be correct now!

a[l_]:= is a@l_:=... Also you don't need the parentheses around Norm

Are you considering reversals of the list on addition to rotations?

No, I am not. Are you saying that I should..? I would say it is more than fair to assume that the lists give a path around the polygon in the same direction... I would argue the heart of the challenge is to check for polygon similarity, not to reverse a list...

@RGS I think considering reversals is necessary this is why the fourth and fifth testcases have a truthy value

@RGS also you code does not work for testcases where reflections are needed like
u = {{0, 0}, {1, 1}, {1, 0}}
v = {{2, 0}, {2, 1}, {3, 0}}
Try it online!


text:
Integer Logarithm
Objective
Take \$a \in ℤ_{>1}\$ and \$b \in ℤ_+\$ as inputs. Write a function \$f\$ such that:
$$
f(a,b) =
\left\{
    \begin{array}{ll}
        \log_ab & \quad \text{if} \space \log_ab \in ℚ \\
        -1 & \quad \text{otherwise}
    \end{array}
\right.
$$
Rules

Types and formats of the inputs doesn't matter.

Type and format of the output doesn't matter either, but the fraction must be irreducible. In C++, std::pair<int,unsigned> is an example. (Regarding logarithms, the numerator and the denominator need not to be arbitrary-length integers.)

Regardless of whether the input type can handle arbitrary-length integers, the algorithm must be "as if" it were handling those. So using floating-point numbers is implicitly banned.

If \$a\$ and \$b\$ aren't in the sets as specified above, the challenge falls in don't care situation.

\$f\$ may be curried or uncurried.

As this is a code-golf, the shortest code in bytes wins.

Test cases
a   b   => answer
-----------------
2   8   => 3/1
3   9   => 2/1
8   2   => 1/3
9   3   => 1/2
4   8   => 3/2
64  256 => 4/3
999 1   => 0/1
-----------------
2   7   => -1
10  50  => -1
5   15  => -1

Could you add some example test cases? Preferably ones where $log_ab \in \mathbb{Q} \setminus \mathbb{Z}$

@PostRockGarfHunter One example is $ \log_4 8 = 3/2 $.

they must be able to represent arbitrary-length integers This is a rather odd requirement, since it unfairly penalizes languages which don't have access to arbitrary-precision integer type (many of them don't even have a thing called "import"). Instead, we usually say "use the most natural number type for the language, but the underlying algorithm should generalize to higher numbers."

@Bubbler I added that requirement to implicitly ban floating-point numbers, but to think about it, that's better.

It looks like you posted this from the Sandbox with edits that are only in the live version, which is unfortunate. Had you waited, I would have pointed out that you still don't have any test cases, which I had commented to remind you to add. And Bubbler might have raised their point about integer size in the Sandbox, which would give you more time to think how to address it, and I might have asked to clarify your new "as if" rule, which I think is unclear as it stands. See Things to avoid: Assuming you've addressed sandbox feedback.

@xnor Well... You know what is more unfortunate? The Mathematica answer apparently use builtin exact arithmetic. This is not what I intended. To admit it, I didn't even want a code golf. I just wanted to see some art of integer arithmetics. So farewell, I'm closing this challenge.

Do we have to output as a fraction or can we output as a float?

Sledgehammer, 11 bytes
Alternatively, 83 bits.
I ended up forgetting to actually answer this with Sledgehammer for a while...
⣜⢍⡪⡱⣰⡵⠅⣧⣼⣅⣸

Compressed from this Wolfram Language code:
If[NumberQ[x1 = Log[Input[], Input[]]], x1, -1]

, where NumberQ is a built-in that checks whether Log has returned an actual number and not a symbolic expression, i.e. when it is rational.

Mathematica, 47 45 43 29 bytes SBCS
If[NumberQ[c=#~Log~#2],c,-1]&

You can try it online!
Thanks to @J42161217 for saving me a total of 16 bytes!!

@J42161217 weird it works in the pattern guard but not inside the if

29 bytes. This one works! Although OP doesn't like solutions like this at all (read main comments above). But after all, this is code-golf

@J42161217 wow incredible!!!

Fed floating point numbers ( Print[f[1.2,1.44]] ) it outputs the right value.... almost (  2.0000000000000004 ).  Is "Log" a floating point function?

OK.  I will admit to being impressed by Mathematica's Log operator(?).  It makes me wonder if I can't write something faster...

Python 3, 103 101 97 bytes
Saved 2 bytes thanks to Kevin Cruijssen!!!
Saved 4 bytes thanks to Value Ink!!!
from math import*
def f(a,b):
 l=log(b,a)
 n,m=l.as_integer_ratio()
 return -1if a**n-b**m else l

Try it online!

Times out on 8,4 (expected result 2/3) among other things. Nice idea for the fractional exponent check, though.

@ValueInk What a shame - guess using as_integer_ratio like this isn't quite up to Mathematica standards! T_T

Yeah, it's the floating point precision error causing problems, which Mathematica probably knows how to get around... I didn't get it submitted before the question closed but I tried something similar with Ruby's to_r which is equivalent -- while that function does return without timing out, because of the precision problems it was giving the wrong number. BTW, use log(b,a) next time. It won't help you with this question because of the aforementioned floating point problem, but could be useful for another problem later!

@ValueInk A golfs a golf, nice one - thanks! :-) Maybe I can sort out the floating point issue.

My solution (which I will post if this gets reopened) was basically to walk through the rationals manually by using the idea that $x > 1 \implies x^{1/x} \notin \mathbb{Z}$ to limit the denominator of the fraction to numbers up to $a$. Wolframalpha of $x^{1/x}$

Charcoal, 88 82 bytes
≔Ｅθ⟦⟧ζ≔²ηＷ⊖⌈θ¿⌊﹪θη≦⊕ηＵＭθ⎇﹪κηκ∧⊞Ｏ§ζλη÷κηＦζＦι⊞υκＵＭυＥζ№λιＵＭυ÷ι⊟Φ⊕⌈ι∧λ¬⌈﹪ιλ¿›⌈υ⌊υ-1Ｉ⊟υ

Try it online! Link is to verbose version of code. Takes input as a list in [value, base] order and outputs numerator and denominator. Edit: Saved 6 bytes by simplifying my check for exclusive factors. Explanation:
≔Ｅθ⟦⟧ζ≔²ηＷ⊖⌈θ¿⌊﹪θη≦⊕ηＵＭθ⎇﹪κηκ∧⊞Ｏ§ζλη÷κη

Factorise both numbers by trial division.
ＦζＦι⊞υκ

Collect the factors from both inputs, in case some factors are only present in one of them.
ＵＭυＥζ№λιＵＭυ÷ι⊟Φ⊕⌈ι∧λ¬⌈﹪ιλ

Divide the multiplicity of each factor in both the base and the value by their GCD.
¿›⌈υ⌊υ-1

If this is not unique then output -1.
Ｉ⊟υ

If it is unique then output it.

05AB1E, 18 17 bytes
-1 byte thanks to Kevin Cruijssen
Ó0ζD€¿÷ʒOĀ}DËiнë®

Try it online!
Ó                   # prime factorize each input
 0ζ                 # zip the factorizations together with filler 0
                    # for each pair of exponents:
    D€¿             #  get the gcd
       ÷            #  divide both by the gcd (reducing the fraction)
        ʒ  }        # filter the pairs, keep only those where:
         O          #  the sum
          Ā         #  is not 0
            DËi     # if all the resulting pairs are equal:
               н    #  output the first pair
                ë   # otherwise:
                 ®  #  output -1

-1 by using D€¿÷ instead of εD¿÷}

Python 3, 94 79 76 bytes

Nothing clever here; this is the obvious brute force approach.
Edit: Unified return point and switched to lambda syntax.
Edit 2: Shaved off three bytes due to @xnor's next trick and rules clarification.
lambda a,b:next(((i,j)for i in range(b)for j in range(1,a)if a**i==b**j),-1)

Try it online!

This is a great place to use the next syntax for generators: Try it online!. By the way, by default, you don't have to write f= for non-recursive functions.

@xnor Didn't know about that second next parameter. Nice one!

bc, 110 bytes
define f(a,b){
c=0
d=1
while(0!=e=a^c-b^d){if(a<2^d){print"-1";return}
if(e>1)d=d+1 else c=c+1}
print c,"/",d}

Try it online!
As with a number of my solutions, it outputs its answer and returns 0, which the test code ignores.
The use of scale= in the provided input is only so the expected value can be passed in.  (You can't have a string value in bc.)  The code is strictly integer... provided you pass in integers.  The code may fail if a or the needed root of a is less than two.  (See two failing samples in TIO.)

JavaScript (Node.js),  72  68 bytes
Takes input as (a)(b), where \$a\$ and \$b\$ are BigInts. Returns either [numerator, denominator] or \$-1\$.
a=>g=(b,p=0n,q=1n)=>p>b?-1:(d=a**p-b**q)?g(b,d>0?++q&&p:-~p,q):[p,q]

Try it online!
How?
We start with \$p=0\$ and \$q=1\$. We iteratively increment \$q\$ if \$a^p>b^q\$ or increment \$p\$ if \$a^p<b^q\$, until \$a^p=b^q\$ (success) or \$p>b\$ (no solution).

Ruby, 72 bytes
->a,b{n,d=[*1..a*b].product([*1..a]).find{|n,d|a**n==b**d};n ?n/1r/d:-1}

Try it online!


text:
Answer templating
Context
Just look around! Whenever someone posts an answer, the same template is followed over and over again! A first line with the byte count and language name. Then the code. Then the TIO link. This is the basic skeleton almost everyone follows.
Task
Your task, should you choose to accept it, is to write a program/function/procedure/etc that takes as input the variable bits and produces the basic CGCC answer.
Input
The language name, some code and a TIO link, in any sensible formats. For the language name and the TIO link, a string is suggested. For the code, sensible formats include a string with possibly some newlines, or a list of strings, one string per line.
Additionally, you may also take the byte count as input. If you don't, you have to compute it yourself (if you compute it yourself, you can assume the byte count equals the length of the code string).
You have to support that the input strings may contain any printable, non-whitespace ASCII characters plus the space. The only exclusion being the newlines in the source code. You don't have to worry about the weird characters used by golfing languages in their code pages.
The inputs may be ordered in any way you like.
Output
You should output this raw content:
# {name}, {byte count} bytes

    {code}

You can [try it online][tio]!

[tio]: {link}

Where {name}, {byte count}, {code} and {link} should be filled in by your code. Three of those are inputs, the byte count should be computed within your code if you chose not to receive it as input (you can assume the byte count is equal to the number of characters in the code argument). Beware that the code given may be multiline, in which case the {code} section must be indented by 4 spaces for each line of code.
Test cases
You can check some test cases.
Related challenge

This is code-golf, so shortest answer in bytes wins. If you liked the challenge, consider upvoting it... And happy golfing!

What if the code has a tab character? In TIO this makes the code formatting start with
 and HTML formatting to insert the tab, along with a bunch of other edge cases.

@ValueInk TIO also uses random ids for its link, but this challenge has nothing more to do with the actual TIO than inspiration.

@ValueInk sorry, I didn't understand your concern.

If you have a literal tab character \t, the code needs to be formatted differently to display it correctly, or something, so on TIO it will emit something like
	print 3
 instead of (four spaces)(tab)print 3 (because otherwise SE will change the tab into 4 spaces or something). Do we need to handle this case???

@ValueInk I tweaked the specs to guarantee that whitespace won't be too annoying

So if somebody attempts to put in some invalid code as input, what should our response be? Is that a valid test case?

@ouflak in those cases, the expected behaviour undefined. I think the linked Python code I wrote would behave correctly, but I did nothing to take care of it. You don't need to worry. If it still works, great! If it raises an error, fine by me. If it ruins the format of your string, still ok.

Can we take a multi-line string as a list (just like what the Keg answerhttps://codegolf.stackexchange.com/a/199503/92069 did?)

Seems like almost every answer is taking byte count as a parameter... Is that not wrong? (Oh nvm i see it can be done wither way)

@a'_' yes you can, as per the input section specs

Ruby, 98 95 94 bytes
Really simple string interpolation. I don't think there's all that much to optimize here that will save a lot of bytes.
Takes the byte count as a parameter in order to save 3 bytes, as per Kevin Cruijssen's suggestion.
->n,b,c,l{"# #{n}, #{b} bytes

#{c.gsub /^/,' '*4}

You can [try it online][tio]!

[tio]: "+l}

Try it online!

Looks fairly simple to me, you are right. But simple doesn't mean it doesn't deserve a +1!

-3 bytes by taking the byte-count as additional input b and replacing the #{c.size} with #{b}. The challenge states it's optional to take the length as input.

05AB1E (legacy), 56 53 52 51 50 bytes
“# ÿ, ÿ¡Ï“I4ú»"[tio]"D“You€© [try€•€Ø]ÿ!“s¶·ý„: IJ

Inputs in the order name, byte-count, [code-lines], link, where the [code-lines] is a list of lines.
Try it online.
50 bytes alternative (credit to @Grimmy):
“:# ÿ, ÿ¡Ï“I4ú»“You€© [try€•€Ø][tio]!“Â6£R¨¶·ýÀ$ú«

Try it online.
Explanation:
“# ÿ, ÿ¡Ï“  # Push dictionary string "# ÿ, ÿ bytes", where the `ÿ` are automatically
            # filled with the first two implicit inputs (name & byte-count)
I           # Push the third input-list of code-lines
 4ú         # Prepend 4 spaces before each line of code
   »        # And join it by newlines
"[tio]"     # Push string "[tio]"
       D    # Duplicate it
        “You€© [try€•€Ø]ÿ!“
            # Push dictionary string "You can [try it online]ÿ!", where the `ÿ` is
            # automatically filled with the "[tio]"
s           # Swap to get "[tio]" at the top of the stack again
¶           # Push a newline character
 ·          # Double it, which in the legacy version built in Python works with strings
  ý         # And join the stack by this double newline as delimiter
„:          # Push string ": "
   I        # Push the fourth input (link)
    J       # Join the entire stack together without delimiter
            # (after which the result is output implicitly)

“:# ÿ, ÿ¡Ï“ # Push dictionary string ":# ÿ, ÿ bytes", where the `ÿ` are automatically
            # filled with the first two implicit inputs (name & byte-count)
I4ú»        # Same as above
“You€© [try€•€Ø][tio]!“
            # Push dictionary string "You can [try it online][tio]!"
 Â          # Bifurcate it; short for Dulpicate & Reverse Copy
  6£        # Only leave the first 6 characters (the "![oit]")
    R       # Reverse it to "[tio]!"
     ¨      # Remove the last character: "[tio]"
¶·ý         # Same as above
À           # Rotate once towards the left, so the leading ":" becomes trailing
 $          # Push the fourth input (link) and a 1
  ú         # Prepend this link-string with that 1 space
   «        # And append it to the earlier created string
            # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to use the dictionary?) to understand why “# ÿ, ÿ¡Ï“ is "# ÿ, ÿ bytes" and “You€© [try€•€Ø]ÿ!“ is "You can [try it online]ÿ!".

Cool answer +1! String compression ftw

Good golfs, I'm not finding anything shorter. Here's an alternative 50

@Grimmy Oh, original alternative! Shall I add it to my answer, or you want to post it as separated answer, since the approach is quite different than mine?

I'm not gonna make a separate answer, feel free to add it if you want to!

Red, 102 94 bytes
-6 bytes thanks to Kevin Cruijssen!
func[l n c u][reduce["#"rejoin[l","]n{bytes

   }c{

You can [try it online][tio]!

[tio]:}u]]

Try it online!

@KevinCruijssen Oh, yes! Apparently I didn't read the question carefully enough :)

Your code looks "funny" because it looks like you have some strings in there with the " but then I can't understand what is wrapping the template string.

@RGS I don't have just one template string. The argument of the reduce function is a block, containing strings (they remain unchanged) and words (let's say they are variables) which are reduced (evaluated). The multline string is enclosed in {}

@KevinCruijssen I noticed, thanks. I tried editing the question to make it more clear. Thanks for the explanation Galen!

PHP, 134 132 125 119 bytes
# <?=($a=$argv)[1].", $a[2] bytes

".preg_replace("/^/m","    ",$a[3])."

You can [try it online][tio]!

[tio]: $a[4]";

Try it online!
Finally an easy job for PHP!
EDIT: easily saved 2 bytes with concatenation in first <?=
EDIT 2: saved another 7 bytes, just remembered that multi-lines strings work in PHP with "
EDIT 3: and another 6 with using /^/m instead of /\n/

Good job here! +1 for you!

You can also take advantage of NL's in strings instead of \n too. Obviously, I changed it a bit to be able to use it, but just an idea (118 bytes): https://tio.run/##xU7NjsIgGLzzFCz2YJMKYdcY60@87tGraTggfrZoBSyfqz49y64P4Vwmk/nJhC6kNKKrzXpc6HWhh/anbKTirKKFbj4V3T8RIiGMn7x1Y0ZoBqvgEXp/gKxZlXNfqiw5I2Tnb9RoRxscntQi9a63DlSD1qsPQv558Tc8VWyZUtp@b5OU83cd6BBDXAhh8lLr@yOPqM0ZHqbTrgVu/EVcbxBzyUUh63paS6FdvMMwQbiEXqN17cuYjV70Cw

@640KB Thanks! improved it with str_replace ;)

@640KB actually rolled back to the 119 version, the problem with your version and the improve I made on it is that there is not the 4 spaces in front of the first line of displayed code :/ so it would be a 120 with those spaces added..

Haskell, 125 121 119 113 bytes
-4 bytes thanks to kronicmage
-2 bytes thanks to xnor
(l!b)c t="# "++l++", "++show b++" bytes\n"++(("\n    "++)=<<c)++"\n\nYou can [try it online][tio]!\n\n[tio]: "++t

Try it online!

You can shave 4 bytes by using (=<<) instead of concatMap in your first answer (which you've already done in your second answer)

I liked how you defined your ! function! Good job +1

You can cut a paren pair with (("\n    "++)=<<lines c)

JavaScript (ES6), 102 bytes
(n,b,c,l)=>`# ${n}, ${b} bytes

${c.replace(/^/gm, '    ')}

You can [try it online][tio]!

[tio]: `+l

Try it online!
"/^/gm" is a Global Multi-line replace of start line (^)

You can save a byte by removing the space at gm,'. :)

Welcome to this community! Really good job here :D +1

Python 3, 97 \$\cdots\$ 118 116 bytes
Added 28 bytes to fix a bug kindly pointed out by RGS.
Saved 2 bytes thanks to ovs!!!
lambda n,b,c,l,x='\n':f"""# {n}, {b} bytes

    {c.replace(x,x+' '*4)}

You can [try it online][tio]!

[tio]: {l}"""

Try it online!
Takes code length as a parameter to save 3 bytes.

Hey, thanks for your submission ! If you check Haskell's test case, the second line of code isn't indented!

You can save one extra byte by deleting the space between a newline and You. Also, I mean that in my Haskell test case, the output has two lines of indented code but yours doesnt

@RGS Ok, got it now - problem fixed! :-)

I can't really be sure now, but taking multiline code as a list of lines and joining with "\n    " might be shorter!

Be shorter just to use '\n' instead of x.

@S.S.Anne You can't use escapes (\) in f-string expressions (inside ({ and })..

116 bytes with a multiline string.

@ovs Nice one - thanks! :-)

Kotlin, 83 109 101 95 bytes
{n,b,c,l->"""# $n, $b bytes

${c.prependIndent()}

You can [try it online][tio]!

[tio]: $l"""}

Try it online!
-6 bytes thanks to @snail_
-2 bytes thanks to @ovs
-6 bytes since prependIndent has a default of 4 spaces

Unfortunately your submission doesn't indent the code correctly when it is multiline! I hope you can fix it :)

@RGS lol damn, that adds quite a few bytes, but fixed

still, good job! +1

you can use String.prependIndent to save some bytes. https://tio.run/##NU/BboMwDD2Pr/AyDomUVgO2lVZqj5N63mlqewgkK1GpgyCZVCG@nSXAfLGfn5/9fDO21jj@ihqsNjugX7bVeOVwRMvhH8yZweqwlLAfe@QFL3m9OpAXiJFDXEDxsKo74xnjvlw3rWoUyiNKhZYS8EHYENhv46AUCCfbPkBbMOg9qMvJO7g8h4Gp2kFck2H8cQh3oZEy6KOnYBTFXcEeyKcxZO6URk4dQl6TNHuL3j82@dajma0VXm3l@TC2ntHCaLwFneikcpVLqzzJNkm@TTPRuUp6feO/tdTboeEqX3bxaRWf9IxFw/gH

a multiline string is 2 bytes shorter: https://tio.run/##NU/LboMwEDzXX7FxOdiSExVoGxIpOVbKuacqysFgN1ghawR2pAjx7dQ86st6dnZmZ2/WVQaHh6zAGbsH9u0ag1cBJ3QC/sFcOayPyxcOQ4ciF4Wo1kdK6StEKCDKIX863RISdcWmbnStUZ1QaXSMQniU94T8WA@FRDi75gnGgcWQQF/OYf9lRchU9xBVwbYffj3CXRpkHDryMsZEeddwAPplLZ07hVVTh9K3OEnfycfnNtsFNLOVxqsrAz@ObWa0MAZvo062SvvSJ2UWp9s42yWpbH2pgr4OtzoWArFxq1i8xGQlJj3npB/@AA (combined with snail_'s suggestion)

Thanks both of you!

Japt, 60 bytes
i`# {V}, {W} ßs

{XmiSp4 R}

YŒ ¯n [try Š Ò‚][o]!

[o]:

Try it

+1 nice handling of newline code blocks!

W j, 77 bytes
# "a", "ck" bytes
"c'
,"
    ":@\+"

You can [try it online][tio]!

[tio]: "b

Explanation
% Header section
# "               % The beginning header
   a              % The first input (the language name)
    ", "          % The comma & space
        ck        % The length of the program (taken at the 3rd input)
          " bytes % Appended with " bytes"
"                 % And a trailing newline

% Code section
c           % The third input
'
,           % Splitted by a newline
"
    "      % Add string representing a newline and 4 spaces
      :    % Stack: '\n'split(c), "    ", "    "
       @   % Stack: "     ",'\n'split(c), "    "
        \  % Join with 4 spaces
         + % Prepend 4 spaces

% Link section
          "

You can [try it online][tio]!

[tio]: "   % The template
         b % The second input
```

Nice answer +1!

This also calculates the byte-count, but it's just 1 byte longer than without calculation.

Java 10, 141 bytes
(n,b,c,l)->{var t="";for(var p:c)t+="    "+p+"\n";return t.format("# %s, %d bytes\n\n%s\nYou can [try it online][tio]!\n\n[tio]: "+l,n,b,t);}

Takes the byte-count as integer-input, and the code as an array of String-lines.
Try it online.
Explanation:
(n,b,c,l)->{    // Method with four parameters and String return-type
  var t="";     //  Temp-String, starting empty
  for(var p:c)  //  Loop over the code-lines:
    t+="    "   //   Append four spaces,
       +p       //   the code-line itself,
       +"\n";   //   and a newline to this temp-String
  return t.format("# %s, %d bytes\n\n%s\nYou can [try it online][tio]!\n\n[tio]: "
                //  Return this String above, where:
    +l,         //   The link is appended at the end
    n,          //   The first `%s` is replaced with the name `n`
    b,          //   The `%d` is replaced with the byte-count `b`
    t);}        //   And the second `%s` is replaced with the temp-String

Standard string formatting method, right? +1 for your work!

Wren, 117 bytes
Just a normal string interpolation here.
Fn.new{|a,b,c,d|"# %(a), %(b) bytes

%("    "+c.split("
").join("
    "))

You can [try it online][tio]!

[tio]: "+d}

Try it online!

Japt, 85 bytes
"# {U}, {V} bytes

{"    "+Wq"
" q"
    "}

You can [try it online][tio]!

[tio]: "+X

Try it online!

Nice answer still! +1

Keg, -pn, 92 83 79 75 bytes
®N®l®b`# ©N, ©b  ¬E;s\n`,÷(\    $+,)
,“0:0X“` [try it a.;][tio]!\n[tio]: ©l`+,

Input is: Name, link, byte count and code
Explained
®N®l®b

We first take the inputs name, link and byte count and store them in variable N, l and b respectively.
`# ©N, ©b  ¬E;s\n`,

Next, we construct a string that represents the header. The ©N and ©b are used for. string interpolation, and ¬E; is the compressed word for byte. Printing the string using , formats the string with variables.
÷(\ $+,)

Now, we item split the implicit code list and print each item with a tab appended to it.
<newline>,

Then, we print a newline to separate everything.
“0:0X“` [try it a.;][tio]!\n[tio]: ©l`+,

Finally, we construct two strings: the string You can (represented by “0:0X“) and  [try it online][tio]!\n[tio]: ©l (which has the variable l interpolated within it). The two strings are then joined and printed.
Try it online!
Answer History
79 bytes
0&®N®l®b`# ©N, ©b  ¬E;s\n`,÷(`\t`$+,)
,“0:0X“` [try it a.;][tio]!\n[tio]: ©l`+,

Try it Online!
83 bytes
0&®N®l®b`# ©N, ©b  bytes\n`,÷(`\t`$+,)
,`You can [try it online][tio]!\n[tio]: ©l`,

Try it online!
Saved 9 bytes due to not calculating the byte count.
92 bytes
0&®N®l÷(:⑴⑼⑹")"⑺⑻®b`# ©N, ©b  bytes\n`,(`\t`$+,)
,`You can [try it online][tio]!\n[tio]: ©l`,

Try it online!
Note that I haven't applied string compression yet, which would get this down to 89 bytes. I'll do it tomorrow. The code is to be given as a list where each item is an individual line.

Really impressive answer! (I didn't upvote it because I want to get the Electorate badge.)

@a'_' you've got a while left until you reach that badge though... That requires 600 upvotes, meaning it would take at least 15 days.

But there's only a 12-hour interval. That means it would take me 8 days.

@a'_' do you mean you will be upvoting a bunch of questions for the next days?

In fact I've already done it.

Jinja2, 102 bytes
# {{n}}, {{b}} bytes

{%for a in c%}
    {{a}}
{%endfor%}

You can [try it online][tio]!

[tio]: {{l}}

Does this count as a language? Used jinja cli from here: https://pypi.org/project/jinja2-cli/
I think it should as this is the usage to run it:
jinja2 tio.j2 test.json --format=json

It accepts a file as a program, and input in some format. That fits the definition of a language to me.
This was the input json tested with:
{"n": "lang_name", "b": 10, "c": ["line_1", "line_2"], "l": "https://example.com"}

Funny submission ;) +1

C (gcc), 162 bytes
t(n,b,c,l)char*n,*c,*l;{for(printf("# %s, %d bytes\n\n    ",n,b);*c;)putchar(*c++)-10?:printf("    ");printf("\n\nYou can [try it online][tio]!\n\n[tio]: %s",l);}

There may be spaces after a trailing newline but I'm not sure if I'll be able to find a solution (or if a solution is even needed).
You can try it online!

Looking promising! Will wait for the rest.

@RGS There's no way to do it without a loop so expect +25 bytes or more.

@RGS Take a look.

looks good to me! +1 and thanks for fixing your submission !

Charcoal, 67 56 bytes
Ｆ⪪“`⊟«Ｍ["Þ…εＵ↑⁵ï²¹@↧≡⊗»⭆∧⌕´r⪪ιυＮτ⁰⬤N➙⁺⁰UＹ⟧MyoJb⎇»﹪”¶«ι Ｓ

You can try it online!
Try it online! Link is to verbose version of code. Assumes you're not worried about Charcoal's default output padding, which can be turned off at a cost of 2 bytes. Explanation: Each input has a certain amount of text that appears before it, which always ends in a space, so the loop prints the text and space before each input. Because it uses separate print commands for the inputs, the newlines in the code block maintain the indent, but the text strings themselves include carriage returns which turn off the indent (particularly applicable to the TIO gubbins). The four text strings themselves are extracted from a large compressed string.