17
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Can input be sorted in either order? \$\endgroup\$ – mabel Feb 12 at 18:20
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – atlasologist Feb 12 at 18:20
  • \$\begingroup\$ 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 \$\endgroup\$ – Vlo Feb 12 at 19:40
  • 14
    \$\begingroup\$ what about negative numbers? what about the sequence of zeros? \$\endgroup\$ – mazzy Feb 12 at 20:03
  • \$\begingroup\$ "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. \$\endgroup\$ – kyrill Feb 12 at 22:19

35 Answers 35

9
\$\begingroup\$

R, 27 26 bytes

all(diff(log2(scan()))>=1)

Try it online!

1 byte saved by Giuseppe.

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
  • 3
    \$\begingroup\$ 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 ¬. \$\endgroup\$ – L. F. Feb 14 at 9:03
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – xnor Feb 13 at 3:35
  • \$\begingroup\$ @xnor Thanks for the suggestions, I will look into the second answer later \$\endgroup\$ – ovs Feb 13 at 9:14
4
\$\begingroup\$

Haskell, 30 bytes

f(x:s)=any(<2)$zipWith(/)s$x:s

Try it online!

True for false and False for true.

\$\endgroup\$
  • 3
    \$\begingroup\$ 27 bytes as a pointfree function. \$\endgroup\$ – ovs Feb 13 at 0:55
3
\$\begingroup\$

JavaScript (ES6),  26  24 bytes

Saved 2 bytes thanks to @Grimmy

a=>!a.some(n=>2*a>(a=n))

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 31 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ -2 bytes after not reversing the stack before the operation. \$\endgroup\$ – petStorm Feb 13 at 6:44
2
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save one byte by writing b>=a*2for without the space. \$\endgroup\$ – kaya3 Feb 13 at 13:03
  • \$\begingroup\$ @kaya3 Nice one - thanks! :-) \$\endgroup\$ – Noodle9 Feb 13 at 13:14
2
\$\begingroup\$

PHP, 53 49 47 43 bytes

for(;$argv[$i++]*2<=$k=$argv[$i];);echo!$k;

Try it online!

-4 bytes thanks to @Kaddath.

\$\endgroup\$
  • \$\begingroup\$ That's actually really clever! \$\endgroup\$ – Kaddath Feb 13 at 13:47
  • \$\begingroup\$ You can save 4 bytes by getting rid of the function: Try it online! \$\endgroup\$ – Kaddath Feb 13 at 13:50
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ codegolf.meta.stackexchange.com/questions/2447/… Use pre-defined variables as IO is a standard loophole \$\endgroup\$ – Vlo Feb 12 at 18:52
  • 1
    \$\begingroup\$ @Vlo oh, I need to make it a function? \$\endgroup\$ – HiddenBabel Feb 12 at 18:54
  • \$\begingroup\$ @LuisMendo Nice! I never knew about all... \$\endgroup\$ – HiddenBabel Feb 12 at 19:22
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Expired Data Feb 13 at 9:30
  • \$\begingroup\$ Thought you might be interested in seeing a different approach at just 18 bytes. \$\endgroup\$ – Sanchises Feb 17 at 13:27
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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?
\$\endgroup\$
1
\$\begingroup\$

EDIT: This is for strict doubling sequences, I have to fix it.

GolfScript, NOT 10 bytes

.{2*}%^,2=
.          #Duplicate the array
 {2*}%     #Double every value in the duplicate
      ^    #Check for values in one not the other
       ,2= #If there are two, return true.

This works because the only values left should be the first element of the non-doubled array and the last element of the doubled array. Size is two!

Try it online!

\$\endgroup\$
  • 5
    \$\begingroup\$ In this problem, "doubling sequence" includes those which more than double, such as 1,2,10. \$\endgroup\$ – 79037662 Feb 12 at 22:48
  • \$\begingroup\$ My bad, I'll rework it \$\endgroup\$ – Mathgeek Feb 12 at 23:59
  • \$\begingroup\$ You can add a little non-competing note in here until you fix it. \$\endgroup\$ – S.S. Anne Feb 14 at 14:41
  • \$\begingroup\$ Yeah, this is not a valid solution rn - non-competing until fixed. \$\endgroup\$ – Mathgeek Feb 14 at 18:14
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Dyalog APL, 8 bytes

∧/2≤2÷/÷

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice! Beats mine by more than half; would you be so kind as to provide a decomposition/explanation? \$\endgroup\$ – Jeff Zeitlin Feb 14 at 12:02
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ The spec allow Any distinct True or False value, so you can cut the _. \$\endgroup\$ – Grimmy Feb 14 at 18:02
  • \$\begingroup\$ @Grimmy Ah, hadn't noticed that. Thanks! \$\endgroup\$ – Kevin Cruijssen Feb 14 at 18:35
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Kirill L. Feb 14 at 11:41
  • \$\begingroup\$ not-any? What a confusing way to spell none. \$\endgroup\$ – Grimmy Feb 14 at 18:05
  • \$\begingroup\$ @KirillL. good catch. \$\endgroup\$ – MattPutnam Feb 14 at 18:51
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

J, 14 bytes

[:*/0.5>:2%/\]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -apl -MList::Util=reduce, 26 bytes

reduce{$_&&=$a<=$b/2;$b}@F

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Python 3, 52 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Python 3, 52 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.