32
\$\begingroup\$

Sometimes, when I'm really bored I like to take the sum of an array of non-negative integers. I only take the sum of arrays of lengths that are powers of two. Unfortunately I often make mistakes. Fortunately I keep track of my work as I go along in the following way:

I add pairs of adjacent numbers until there's only one left. For example:

 6 + 18 + 9 + 6 + 6 + 3 + 8 + 10
=  24   +   15  +   9   +   18
=       39      +       27
=               66

You're job is to determine if I've made a mistake somewhere. You may either get input passed to your function or read from standard in. Output can be printed or returned.

Input: An array/list/etc. of non-negative integers, and possibly also the length of that array if your language requires it. That array will be all the numbers read left to right then top to bottom. For example the array above would become:
[[6, 18, 9, 6, 6, 3, 8, 10], [24, 15, 9, 18], [39, 27], [66]]
or
[6, 18, 9, 6, 6, 3, 8, 10, 24, 15, 9, 18, 39, 27, 66] if you prefer.

Output: a single boolean representing whether or not a mistake was made. The boolean can be represented using any mapping provided that all inputs where a mistake is made return/print an identical result and all input which contain no mistakes return/print an identical result. This should go without saying, but those two outputs cannot be the same.

Some Examples of Correct Summations:

6

5+6
=11

  3 + 2 + 4 + 5
=   5   +   9
=       14

[0, 1, 2, 3, 1, 5, 6]

[[1, 2, 4, 8], [3, 12], [15]]

Some Examples of Incorrect Summation:

5+4
=8

4 + 4 + 4 + 4
= 9   +   7
=     16

[[1, 2, 3, 4], [7, 3], [10]]

[3, 4, 5, 6, 7, 8, 9]

Keep in mind that I can make mistakes and still get the right answer. If I do make a mistake it'll never result in an extra number or a missing number in the final array, only a wrong number.

Standard loopholes are forbidden. Shortest answer in each language is a winner. The older answer will win in the case of a tie. I retain the right to decide what the "same language" is, but I'll say upfront a point can't be earned in both Python 2, and Python 3.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to the site! Nice first challenge. \$\endgroup\$ – AdmBorkBork Mar 15 '17 at 18:22
  • \$\begingroup\$ Why the end date? Languages newer than the challenge are already forbidden by default. \$\endgroup\$ – Rɪᴋᴇʀ Mar 15 '17 at 18:26
  • \$\begingroup\$ I suppose I could remove it, the idea was that I need to have some cuttoff so I can crown a set of answers as correct, but I guess it doesn't have to be that way. \$\endgroup\$ – Bijan Mar 15 '17 at 18:28
  • 1
    \$\begingroup\$ No, you may use whichever makes golfing easier. \$\endgroup\$ – Bijan Mar 15 '17 at 19:23
  • \$\begingroup\$ The example [0,1,2,3,1,5,6] is invalid because "Input: An array/list/etc. of positive integers". \$\endgroup\$ – Ben Frankel Mar 15 '17 at 20:28

20 Answers 20

10
\$\begingroup\$

Jelly, 6 bytes

Ṗ+2/€ẇ

Try it online!

How it works

Ṗ+2/€ẇ  Main link. Argument: A (2D array)

Ṗ       Pop; yield A without its last element. Let's call the result B.
  2/    Pairwise reduce...
    €     each array in B...
 +          by addition.
     ẇ  Window exists; test if the result appears in A as a contiguous subarray.
\$\endgroup\$
9
\$\begingroup\$

Python 2, 51 bytes

lambda l:map(sum,zip(*[iter(l)]*2))==l[len(l)/2+1:]

Try it online! Thanks to Rod for the test cases.

Takes the whole list flat as input. Groups elements into adjacent pairs using the zip/iter trick, takes the sum of the pairs, and checks if the result equals the second half of the list.

A recursive method came close at 55 bytes:

f=lambda l:len(l)<2or l[0]+l[1]==l[len(l)/2+1]*f(l[2:])

This used that input integers are positive, which has since changed in the spec.

\$\endgroup\$
  • \$\begingroup\$ Since the question's conditions now allow non-negative entries, your recursive method will give a false positive for [0,0,1,1,1,1,1]. \$\endgroup\$ – Ben Frankel Mar 15 '17 at 20:38
7
\$\begingroup\$

Röda, 40 bytes

{[0]if{|x|[[x()|[_+_]]=y]if tryPeek y}_}

Try it online!

It's an anonymous function that returns 0 if there are no mistakes and nothing if there are mistakes.

Explanation:

{[0]if{|x|[[x()|[_+_]]=y]if tryPeek y}_}
{                                      } /* Anonymous function */
      {|x|                           }_  /* Loop over lists in the stream */
                         if tryPeek y    /* If there are lists left after this */
            x()                          /* Push values in list x to the stream */
               |[_+_]                    /* Sum every pair of numbers in x */
           [         ]                   /* Create a list of sums */
                      =y                 /* If the list equals to the next list */
          [             ]                /* Push the result */
    if                                   /* If all results are TRUE */
 [0]                                     /* Return 0 */
                                         /* Otherwise return nothing */

Here's a version that is shorter (35 bytes) but against the rules (I think):

{{|x|[[x()|[_+_]]=y]if tryPeek y}_}

Try it online!

It's an anonymous function that reads values from the stream and pushes TRUE or FALSE for each correct line.

I'm not sure if this (multiple return values) is accepted in the rules. Here's my defence: in Röda, conditions of if and while blocks are not boolean values, but streams. A "truthy" stream is either empty or contains only TRUEs, and a "falsy" stream contains one or more FALSEs. In this way, this function returns a "boolean" value. And can be used as a condition of an if statement without any reduce-operations, etc.

\$\endgroup\$
  • \$\begingroup\$ I'm not sure if that counts, but for now you have the only Roda solution, so it's hard to say until someone else comes along. I think that that should be fine, but I don't really like the idea of tweaking the rules after the question goes up. Though perhaps one could make a case for it not be a change in rule, so much as filling in an ambiguity. \$\endgroup\$ – Bijan Mar 15 '17 at 18:52
  • 2
    \$\begingroup\$ @Bijan There are other languages that have a similar construct. In MATL, for example, the whole array is falsey if there is a single 0 in it. I'm not sure exactly how Röda handles that, but it's not unheard of. \$\endgroup\$ – AdmBorkBork Mar 15 '17 at 20:48
  • 1
    \$\begingroup\$ @Bijan Our definition of truthy/falsy depends on what the language would do for an if conditional. If this is how Röda works, it complies with our rules, unless the challenge spec overrides the defaults explicitly. \$\endgroup\$ – Dennis Mar 16 '17 at 3:32
  • \$\begingroup\$ @Dennis It seems that the OP has forbidden this: "all inputs where a mistake is made return/print an identical result and all input which contain no mistakes return/print an identical result." The shorter variation of the program has an infinite number of outputs. \$\endgroup\$ – fergusq Mar 16 '17 at 15:40
  • \$\begingroup\$ @fergusq Oh, right, I've overlooked that. \$\endgroup\$ – Dennis Mar 16 '17 at 15:42
5
\$\begingroup\$

Python 2, 69 65 bytes

lambda x:reduce(lambda a,b:(b==map(sum,zip(a[::2],a[1::2])))*b,x)

Try it online!
Returns :
Empty List as Falsy
Total sum as Truthy

\$\endgroup\$
5
\$\begingroup\$

Mathematica, 36 bytes

Most[Tr/@#~Partition~2&/@#]==Rest@#&

Pure function taking a nested list as input and returning True or False. The function Tr/@#~Partition~2& takes the pairwise sums of a list, which is then applied (/@#) to each sublist of the input list. The first, second, ... sublists in the resulting list are supposed to equal the second, third, ... sublists in the original input; Most[...]==Rest@# tests for this property.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 80 bytes

lambda l:all(l[i+1]==map(sum,zip(l[i][::2],l[i][1::2]))for i in range(len(l)-1))

Try it online!

Not quite as good as the other python answer, but I felt like posting it anyway. This just goes to show why I'm not as good at golfing in regular languages.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 54 bytes

a=>!a.slice(-a.length/2).some((n,i)=>a[i+=i]+a[i+1]-n)

Takes a flattened array.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 15 12 bytes

¬svyQy2ôO}\P

Try it online!

Explanation

¬             # get the first element from input without popping
 sv      }    # for each element y in input
   yQ         # compare y to the top of the stack 
              # leaves 1 on the stack if equal and otherwise 0
     y2ô      # split y in pieces of 2
        O     # sum each pair in the list
          \   # discard the top of the stack (the left over final element of the list)
           P  # product of stack (all the 1's and/or 0's from the comparisons)
\$\endgroup\$
3
\$\begingroup\$

Haskell, 82 79 65 bytes

-14 bytes thanks to nimi!

p(x:y:z)=x+y:p z
f x=and.zipWith(==)(drop(length x`div`2+1)x)$p x

Works by comparing the sum each pair of elements to the corresponding element on the next line down. Some bytes can probably be golfed from f, but I can't figure out where.

\$\endgroup\$
  • \$\begingroup\$ You can add the two values directly in function p: p(x:y:z)=x+y:p z and then use zipWith(==) instead of zip and combine the list of Bool with and: f x=and.zipWith(==)(drop(length x`div`2+1)x)$p x. \$\endgroup\$ – nimi Mar 15 '17 at 22:05
2
\$\begingroup\$

Python 3, 69 68 bytes

lambda v:any(x+v[i-1]-v[(len(v)+i)//2]for i,x in enumerate(v)if i%2)

I know there are already two other python answers... but this one's in python 3, so it's exotic.

This works on a flattened input.

Output:

False if there is no mistake,

True if there is a mistake.

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

Ruby, 50 bytes

->x{a=b=0;b&&=x[a/2]==x[a]+x[a-1]while x[-a-=2];b}

Reversing the array, any element of the first half (position n) must be the sum of the elements in position n*2 and n*2+1.

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

Brachylog, 16 13 bytes

s₂ᵘ{{ġ₂+ᵐ}ᵈ}ᵐ

Try it online!

This is just dreadfully long! There has to be some way to not nest inline predicates here.

The predicate succeeds (printing true. as a program) if no mistakes were made and fails (printing false. as a program) otherwise.

s₂ᵘ              Every length 2 substring of the input
   {       }ᵐ    for every element satisfies the following:
    {ġ₂          the pairs of elements of the input
       +ᵐ        when each pair is summed is the output
         }ᵈ      where the input is the first item and the output is the second.
\$\endgroup\$
1
\$\begingroup\$

Python 2, 64 bytes

lambda a:[map(int.__add__,x[::2],x[1::2])for x in a[:-1]]==a[1:]

Try it online!

An unnamed function that takes a list of lists (one per line of working as it were), and returns True if no mistakes were made and False otherwise.

It works by using the input without the last entry, a[:-1], to form what the input without the first entry should be and checking that is what was input, ==a[1:].

This formation is achieved by mapping the integer type's addition function, int.__add__, over the pairs of numbers as yielded by two "slices", one slice being every other item starting at the 0th index, x[::2], the other slice being every other item starting at the 1st index, x[1::2].

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

Pip, 20 19 bytes

$*{{b=$+*Ya<>2}MPa}

This is an anonymous function that takes one argument, a list of lists (e.g. [[1 2 3 4] [3 7] [10]]). Verify all test cases: Try it online!

Explanation

In a Pip function, the first two arguments are assigned to a and b.

  {               }  Anonymous function:
   {          }MPa    To each pair of sublists from a, map this helper function:
          a<>2         Group the 1st member of the pair into 2-item sublists
         Y             Yank that value (no-op used to override precedence order)
      $+*              Map (*) the fold ($) on addition (+) operator
    b=                 If the 2nd member of the pair is = to the result, 1; else 0
$*                   Modify the outside function by folding its return value on *
                     (makes a list containing all 1's into 1 and any 0's into 0)

For example:

a
[[1 2 3 4] [7 3] [10]]

{...}MP
a:[1 2 3 4] b:[7 3]
a:[7 3]     b:[10]

a<>2
[[1 2] [3 4]]
[[7 3]]

$+*
[3 7]
[10]

b=
0
1

Final result of {...}MPa
[0 1]

$*
0
\$\endgroup\$
1
\$\begingroup\$

PHP, 96 95 bytes:

using builtins:

function f($a){return!$a[1]||array_pop($a)==array_map(array_sum,array_chunk(end($a),2))&f($a);}
// or
function f($a){return!$a[1]||array_map(array_sum,array_chunk(array_shift($a),2))==$a[0]&f($a);}

recursive functions return true or false.

breakdown for first function:

function f($a){
    return!$a[1]||      // true if array has no two rows ... or
    array_pop($a)==     // remove last row, true if equal to
    array_map(array_sum,    // 3. sum up every chunk
        array_chunk(        // 2. split to chunks of 2
            end($a)         // 1. new last row
        ,2))
    &f($a);             // and recursion returns true
}

older solutions (96 bytes each) using loops:

function f($a){foreach($a[0]as$k=>$v)$b[$k/2]+=$v;return$b==$a[1]&&!$a[2]|f(array_slice($a,1));}
//or
function f($a,$y=0){foreach($a[$y]as$k=>$v)$b[$k/2]+=$v;return$b==$a[++$y]&&!$a[$y+1]|f($a,$y);}

breakdown for last function:

function f($a,$y=0){
    foreach($a[$y]as$k=>$v)$b[$k/2]+=$v;    // build $b with correct sums from current row
    return$b==$a[++$y]                      // true if $b equals next row
    &&!$a[$y+1]                             // and (finished
        |f($a,$y);                          //      or recursion returns true)
}

iterative snippets, 81 bytes

for(;$a[1];)if(array_pop($a)!=array_map(array_sum,array_chunk(end($a),2)))die(1);
for(;$a[1];)if(array_map(array_sum,array_chunk(array_shift($a),2))!=$a[0])die(1);
for(;$a[++$y];$b=[]){foreach($a[$y-1]as$k=>$v)$b[$k/2]+=$v;if($a[$y]!=$b)die(1);}

assume array predefined in $a; exits with error if it is incorrect.

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

C, 54 bytes:

f(int*s,int*e){return e-s>1?*s+s[1]-*e||f(s+2,e+1):0;}

Ungolfed:

int f(int*s,int*e) {
    if(e-s>1) {
        return *s+s[1] != *e || f(s+2,e+1);
    } else {
        return 0;
    }
}

Test with

#include <assert.h>
int main() {
    int input1[15] = {6, 18, 9, 6, 6, 3, 8, 10, 24, 15, 9, 18, 39, 27, 66};
    assert(!f(input1, input1+8));

    int input2[7] = {3, 4, 5, 6, 7, 8, 9};
    assert(f(input2, input2+4));
}

As you see, f() returns true for invalid inputs and false (= 0) for valid ones.

As always, recursion is less bytes than iteration, so f() is recursive, even though it takes two iterators as arguments. It works by repeatedly comparing the sum of two integers at s to one integer at e, ignoring the level boundaries, and carrying on until the two iterators meet. I have also used some boolean zen together with the fact that any non-zero integer value is considered true in C to further shorten the code.

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

R, 92 77 bytes

Anonymous function which takes a flat sequence of numbers as input. Returns TRUE or FALSE as appropriate. Uses the same approach conceptually as xnor's python answer.

function(x,l=sum(1|x)/2)all(rowSums(cbind(x[1:l*2-1],x[1:l*2]))==tail(x,l-1))

Previous solution, using the rollapply function from the zoo package, and taking input as a list, e.g. list(c(6, 18, 9, 6, 6, 3, 8, 10), c(24, 15, 9, 18), c(39, 27), c(66)):

function(l,T=1){for(i in 2:length(l))T=T&all(zoo::rollapply(l[[i-1]],2,sum,by=2)==l[[i]]);T}
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 46 44 bytes

Takes input as a flattened array. Returns NaN for valid or 0 for invalid.

f=([a,b,...c])=>a+b==c[c.length>>1]?f(c):b-b

Test

f=([a,b,...c])=>a+b==c[c.length>>1]?f(c):b-b

console.log(f([6, 18, 9, 6, 6, 3, 8, 10, 24, 15, 9, 18, 39, 27, 66])) // NaN
console.log(f([0, 1, 2, 3, 1, 5, 6]))                                 // NaN
console.log(f([1, 2, 4, 8, 3, 12, 15]))                               // NaN
console.log(f([1, 2, 3, 4, 7, 3, 10]))                                // 0
console.log(f([3, 4, 5, 6, 7, 8, 9]))                                 // 0

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

PHP, 102 Bytes

input als url parameter in this format ?0=[1,2,3]&1=[3,3]&2=[6] use this input [[int,int],[int]]

<?$r=[$_GET[0]];for(;count(end($r))>1;)$r[]=array_map(array_sum,array_chunk(end($r),2));echo$r==$_GET;

Breakdown

$r=[$_GET[0]]; # Set the first item of the input in the result array 
for(;count(end($r))>1;) # till the last item in the result array has only one int
$r[]=array_map(array_sum,array_chunk(end($r),2));# add the next item to the result array
echo$r==$_GET; # compare the input array with the result array
\$\endgroup\$
0
\$\begingroup\$

Japt, 10 bytes

Takes input as a 2-D array.

äÏeXò mxÃe

Try it

äÏeXò mxÃe     :Implicit input of 2-D array
ä              :Reduce each consecutive pair of sub-arrays
 Ï             :By passing them through the following function as X & Y, respectively
  e            :  Test Y for equality with
   Xò          :    Split X on every 2nd element
      m        :    Map
       x       :      Reduce by addition
        Ã      :End function
         e     :All true?
\$\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.