John has made an array of numbers which are important to him. Unfortunately, John lost the array.

Luckily, he knows some details about the array. You will receive each of these sets of details (which are lists of 3 integers).

Each detail is the sum of a section of the list. Each has the numbers a, the starting index of the sum, b, the ending index of the array's sum, and c, which is 1 if the sum is positive and -1 if the sum is negative.

Your job is to find an array that matches the given details and to print them out, or to print -1 if no such array exists.

Example Input: (0-indexed and inclusive)

[0, 1, 1]
[1, 2, -1]


[-1, 2, -3]

The details here require that the sum from 0 to 1 is positive, and from 1 to 2 is negative. You can output any array that matches.

You can take the input in any reasonable format.

Whoever writes the shortest program wins! This is a code golf problem.

  • 2
    \$\begingroup\$ What are the scoring rules? \$\endgroup\$
    – Endenite
    Feb 10, 2018 at 22:50
  • 10
    \$\begingroup\$ I recommend getting your previous challenge reopened before posting a new one. You might also want to give the sandbox a try, instead of directly posting questions on main. \$\endgroup\$
    – Dennis
    Feb 10, 2018 at 23:03
  • 3
    \$\begingroup\$ If this is not your own problem please do provide its source. \$\endgroup\$ Feb 10, 2018 at 23:19
  • 1
    \$\begingroup\$ I've edited this to make it more clear and to make the i/o format less strict. Most languages don't require those extra details about how many lines of details there are, so I've removed that. In addition, challenges like this work best with only one 'test case' per input, so I've removed that as well. \$\endgroup\$
    – Riker
    Feb 11, 2018 at 1:26
  • 5
    \$\begingroup\$ @Riker Multiple test cases as input and their number as the first line is a strong indication the challenge is missing some attribution, although, as always, you can't be 100% sure that's the case. \$\endgroup\$ Feb 11, 2018 at 11:08

1 Answer 1


Perl, 101 bytes

Includes +7 for -0pF\n


#!/usr/bin/perl -0pF\n
$_="@G"x!grep{$a=!/ \d+ /;grep{$_+=$`if$`^$a<=>0}grep{$a+=$_;1}@G[$&+0..$']}@F until$n{"@G"}++

Input triples on seperate lines on STDIN in the order sign from to Outputs either a valid assignment or nothing. don't care positions in the output array are left empty (noticable as consecutive spaces). So for example:

(echo 1 0 1; echo -1 1 2) | lost_array.pl; echo


1 0 -1

This is way too long and I'm not even sure it is correct, but it's the best I could immediately think of.

For all given ranges it calculates the sum and if the sign isn't right adds the sign to all values in the range to make the sum better. It stops as soon as it detects that the array of values is repeated. If no value update was done during the last loop this is a solution and it is printed. Otherwise no solution is possible and nothing gets printed

  • \$\begingroup\$ I think it's correct, but it would be great if you could add an explanation of the code, not just how you did it. \$\endgroup\$
    – McLinux
    Feb 11, 2018 at 19:45

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.