17
\$\begingroup\$

You are employed as Administrator in charge of Road Maintenance and Planning. The intelligence division of the Agency for Road Maintenance and Planning has come up with a brilliant and not at all inefficient way to take random sample pictures of the roads: missiles with cameras on them.

In this genius and not at all wasteful technique, smart non-explosive missiles are sent hurtling down each road. Each missile moves in a straight line and captures images at equal spatial intervals. Eventually the Agency will get a good overall sample of the state of affairs for each road. On Masagaki Road, for example, images are captured at positions 1, 4, 5, 6, 8, 11, 12 and 14:

1 X X 4 5 6 X 8 X X 11 12 X 14 (X represents no image)

Your job is to find the largest number of images that could have been captured by the camera on a single missile. A single camera could have captured the three images at positions 4, 5, 6 (having a spacing of 1); the three images at positions 4, 6, 8 (spacing 2); or the three images at 4, 8, 12 (spacing 4). However, here the answer is four: positions 5, 8, 11, 14 (spacing 3).

Input: a sequence of \$1\leq n\leq1000\$ unique integers, each satisfying \$1\leq i\leq1000000\$, representing the positions of the images captured for a certain road. These will be given from smallest to largest.

Output: a single integer representing the largest number of images that could have been captured by a single camera.

Sample 1

Input: 1 4 5 6 8 11 12 14

Output: 4

Sample 2

Input: 5 8 9 10 12 15 16 17

Output: 3


  • ; the shortest code in bytes wins.
  • The linked rules apply.
  • Please explain your code.
  • Please link to Try It Online! or another online demo.

Inspired by 'Air Drop' (AIO 2007, Senior)

\$\endgroup\$
  • 3
    \$\begingroup\$ Ah yes. Missiles. The best and most common way of conducting road planning! \s \$\endgroup\$ – Lyxal Apr 27 at 4:24
  • 1
    \$\begingroup\$ Q: Why is no one rioting over the use of missiles? A: This is not within the scope of the question. \$\endgroup\$ – lightlyheld Apr 27 at 4:25
  • \$\begingroup\$ Maybe I'm missing something obvious, but for sample 2, how do you get 4 ? \$\endgroup\$ – xnor Apr 27 at 4:25
  • \$\begingroup\$ @xnor Sorry, 3. \$\endgroup\$ – lightlyheld Apr 27 at 4:27
9
\$\begingroup\$

Python 2, 74 bytes

lambda l:max(reduce(lambda i,x:i+(a+i*(b-a)==x),l,0)for a in l for b in l)

Try it online!

Tries every possible sequence of the form a,b,... with a and b in the input l.

To find the smallest index i of this arithmetic progression that's outside l, we do something a bit unusual. Instead of counting up the progression to find an element not in l, we iterate over l, taking advantage of it being sorted. For each successive element x of l, we move to the next index in the arithmetic progression if its current value matches x, and stay at the current index otherwise.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I like how you use reduce to find sequence length, very clever! \$\endgroup\$ – Surculose Sputum Apr 27 at 5:58
7
\$\begingroup\$

05AB1E, 8 bytes

æʒ¥Ë}€gà

Try it online!

æ          # power set
 ʒ  }      # filtered by:
  ¥        #  deltas
   Ë       #  all equal
     €g    # length of each
       à   # maximum
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Power set??? The runtime exceeds 60 s once you get to the hundreds of elements. \$\endgroup\$ – lightlyheld Apr 27 at 8:04
  • \$\begingroup\$ Of course, I didn't say anything about time in the question... \$\endgroup\$ – lightlyheld Apr 27 at 8:12
  • 3
    \$\begingroup\$ @lightlyheld yup, the default for code-golf questions is that any runtime is fine, as long as the code works for arbitrarily large inputs in theory. If that's not what you want, you sould add the restricted-complexity tag. (Might be too late here, but for future questions). \$\endgroup\$ – Grimmy Apr 27 at 8:15
3
\$\begingroup\$

Python 2, 98 bytes

f=lambda l,i=1:i/l[-1]or max(f(l,i+1),*[g(a,l,i)for a in l])
g=lambda a,l,i:a in l and-~g(a+i,l,i)

Try it online!

A function that takes in a list of integers and returns the max number of images

Approach: Try for each element a in the list, and for each increment i in the range 1 to max(l).

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 22 bytes

I⊟Φ⊕Lθ⊙θΦ⌈θ¬⁻⁺×…⁰ι⊕νλθ

Try it online! Link is to verbose version of code. Explanation:

     θ                  Input array
    L                   Length
   ⊕                    Incremented
  Φ                     Filter over implicit range
       θ                Input array
      ⊙                 Any element where
          θ             Input array
         ⌈              Maximum
        Φ               Filter over implicit range where
               …⁰ι      Range of length given by outer index
              ×   ⊕ν    Multiplied by incremented inner index
             ⁺      λ   Offset by selected element
            ⁻        θ  Set difference with input array
           ¬            Is empty (i.e. this is a subset)
 ⊟                      Take the last (i.e. highest) element
I                       Cast to string for implicit print

The second Φ would be except Charcoal doesn't support this.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 89 bytes

A=>A.reduce((a,x)=>[...a,...a.map(y=>x-2*y[0]+y[1]?y:(b+=!!y[b],[x,...y]))],[[]],b=0)|b+1

Try it online!

Commented

A =>                  // A[] = input array
  A.reduce((a, x) =>  // for each value x in A[],
                      // using a[] as the previous list of lists:
    [                 //   build a new list of lists:
      ...a,           //     append all previous lists stored in a[]
      ...a.map(y =>   //     for each list y[] in a[]:
        x -           //       if both y[0] and y[1] are defined
        2 * y[0] +    //       and (x - y[0]) is not equal
        y[1] ?        //       to (y[0] - y[1]):
          y           //         leave y[] unchanged
        :             //       else:
          ( b +=      //         increment b if:
              !!y[b], //           y[b] is defined (i.e. the length of y[] is b+1)
            [x, ...y] //         prepend x to y[]
          )           //
      )               //     end of map()
    ],                //   end of the new list of lists
    [[]],             //   start with a[] containing a single empty list
    b = 0             //   start with b = 0
  )                   // end of reduce()
  | b + 1             // return b + 1
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Red, 127 bytes

func[b][m: 0 repeat s t: last b[n: 1 forall b[d: s until[either
find b b/1 + d[n: n + 1][m: max n m n: 1 d: t]t < d: d + s]]]m]

Try it online!

Naive imperative solution.

Explanation:

f: func [b][
    m: 0                                 ; the max number of images so far
    repeat s t: last b [                 ; s (for step) is a list 1..last 
        n: 1                             ; current max 
        forall b [                       ; iterate over the input
            d: s                         ; current step
            until [                      ; and do the following : 
                either find b b/1 + d [  ; if there is a number in the list that is equal
                                         ; to the current number + the current step
                    n: n + 1             ; increase the current max
                ][                       ; else
                    m: max n m           ; update max,
                    n: 1                 ; reset current max
                    d: t                 ; and set the current step at the last number
                ]
                t < d: d + s             ; until current step is beyond the last number  
            ]   

        ]
    ]
    m                                    ; return max
]
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 111 bytes

$_=max(map{$j=$_;(grep{(reduce{$a.(' 'x(-1+$b-length$a)).'x'}@F)=~join'.'x$j,('x')x$_}1..$F[-1])[-1]}0..$F[-1])

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Jelly, 8 bytes

ŒPIE$ƇṪL

A monadic Link accepting a list which yields an integer.

Try it online!

How?

We are looking for the longest sub-sequence which has equal incremental differences, this just filters all sub-sequences in length order and takes the length of the last one.

ŒPIE$ƇṪL - Link: list of numbers
ŒP       - powerset (all sub-sequences ordered by length)
    $    - last two links as a monad:
  I      -   incremental differences (e.g. [4, 7, 11] -> [7-4,11-7] = [3,4])
   E     -   all equal?
      Ṫ  - tail
       L - length
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Erlang (escript), 102 bytes

Port of xnor's Python 2 answer.

f(R)->lists:max([lists:foldl(fun(X,I)->I+(case A+I*(B-A)==X of true->1;_->0 end)end,0,R)||A<-R,B<-R]).

Try it online!

| improve this answer | |
\$\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.