11
\$\begingroup\$

This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals.

Consider an array A of length n. The array contains only positive integers. For example A = (1,1,2,2). Let us define f(A) as the set of sums of all the non-empty contiguous subarrays of A. In this case f(A) = {1,2,3,4,5,6}. The steps to produce f(A) are as follows:

The subarrays of A are (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Their respective sums are 1,1,2,2,2,3,4,4,5,6. The set you get from this list is therefore {1,2,3,4,5,6}.

We call an array A unique if there is no other array B of the same length such that f(A) = f(B), except for the array A reversed. As an example, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6} but there is no other array of length 3 that produces the same set of sums.

We will only consider arrays where the elements are either a given integer s or s+1. E.g. if s=1 the arrays would only contain 1 and 2.

Task

The task, for a given n and s is to count the number of unique arrays of that length. You can assume that s is between 1 and 9.

You should not count the reverse of an array as well as the array itself.

Examples

s = 1, the answer is always n+1.

s = 2, the answers counting from n = 1 up are:

2,3,6,10,20,32,52,86

s = 8, the answers counting from n = 1 up are:

2,3,6,10,20,36,68,130

Score

For a given n, your code should output the answer for all values of s from 1 to 9. Your score is the highest value of n for which this completes in one minute.

Testing

I will need to run your code on my ubuntu machine so please include as detailed instructions as possible for how to compile and run your code.

Leaderboard

  • n = 24 by Anders Kaseorg in Rust (34 seconds)
  • n = 16 by Ourous in Clean (36 seconds)
  • n = 14 by JRowan in Common Lisp (49 seconds)
\$\endgroup\$
  • \$\begingroup\$ So if s=8 then its an array of all possible combinations of 8 and 9, nothing else? \$\endgroup\$ – JRowan Oct 24 '18 at 17:22
  • \$\begingroup\$ @JRowan No. You don't count any of those arrays that have the same set of sums as some other array. \$\endgroup\$ – Anush Oct 24 '18 at 18:06
  • \$\begingroup\$ This part i am a little confused about We will only consider arrays where the elements are either a given integer s or s+1. E.g. if s=1 the arrays would only contain 1 and 2. So if n is 2 and s is 3 what would the arrays to test be? \$\endgroup\$ – JRowan Oct 24 '18 at 18:21
  • \$\begingroup\$ what about [3,3] and im currently removing the reverse of the lists eg. [3,4]->[4,3] \$\endgroup\$ – JRowan Oct 24 '18 at 18:27
  • 2
    \$\begingroup\$ @RosLuP Firstly, you meant to post that on the other question, and secondly, [3, 5, 4] is a subset but not a subarray of [3, 5, 1, 4]. \$\endgroup\$ – Anders Kaseorg Oct 25 '18 at 23:17
5
\$\begingroup\$

Rust, n ≈ 24

Requires nightly Rust for the convenient reverse_bits feature. Compile with rustc -O unique.rs and run with (e.g.) ./unique 24.

#![feature(reverse_bits)]
use std::{collections::HashMap, env, mem, process};

type T = u32;
const BITS: u32 = mem::size_of::<T>() as u32 * 8;

fn main() {
    let args = env::args().collect::<Vec<_>>();
    assert!(args.len() == 2);
    let n: u32 = args[1].parse().unwrap();
    assert!(n > 0);
    assert!(n <= BITS);
    let mut unique = (2..=9).map(|_| HashMap::new()).collect::<Vec<_>>();
    let mut sums = vec![0 as T; n as usize];
    for a in 0 as T..=!0 >> (BITS - n) {
        if a <= a.reverse_bits() >> (BITS - n) {
            for v in &mut sums {
                *v = 0;
            }
            for i in 0..n {
                let mut bit = 1;
                for j in i..n {
                    bit <<= a >> j & 1;
                    sums[(j - i) as usize] |= bit;
                }
            }
            for s in 2..=9 {
                let mut sums_s =
                    vec![0 as T; ((n + (n - 1) * s) / BITS + 1) as usize].into_boxed_slice();
                let mut pos = 0;
                let mut shift = 0;
                let mut lo = 0;
                let mut hi = 0;
                for &v in &sums {
                    lo |= v << shift;
                    if BITS - shift < n {
                        hi |= v >> (BITS - shift);
                    }
                    shift += s;
                    if shift >= BITS {
                        shift -= BITS;
                        sums_s[pos] = lo;
                        pos += 1;
                        lo = hi;
                        hi = 0;
                    }
                }
                if lo != 0 || hi != 0 {
                    sums_s[pos] = lo;
                    pos += 1;
                    if hi != 0 {
                        sums_s[pos] = hi;
                    }
                }
                unique[s as usize - 2]
                    .entry(sums_s)
                    .and_modify(|u| *u = false)
                    .or_insert(true);
            }
        }
    }
    let mut counts = vec![n + 1];
    counts.extend(
        unique
            .iter()
            .map(|m| m.values().map(|&u| u as T).sum::<T>())
            .collect::<Vec<_>>(),
    );
    println!("{:?}", counts);
    process::exit(0); // Avoid running destructors.
}
\$\endgroup\$
  • \$\begingroup\$ This is great, thank you. It completes for n = 25 in about 90 seconds. But the main problem is that it uses 70% of my 8GB of RAM. \$\endgroup\$ – Anush Oct 21 '18 at 18:14
  • \$\begingroup\$ I have suddenly got worried about something. Are you checking that the arrays are unique with respect to all other possible arrays, or just arrays with values s and s+1 in them? \$\endgroup\$ – Anush Oct 21 '18 at 18:59
  • \$\begingroup\$ @Anush Yes, I traded some memory usage for speed. I’m counting arrays that are unique w.r.t. other arrays with values s and s + 1 (since you said those are the only arrays we will consider), although it’s not immediately obvious whether that would make a difference. \$\endgroup\$ – Anders Kaseorg Oct 21 '18 at 21:43
  • 1
    \$\begingroup\$ I think I will need to work this out tomorrow. The arrays 1,1,2,2 and 1,1,1,3 both give the set of sums 1,2,3,4,5,6. However the former is not unique amongst arrays with only 1 and 2 so I am a little confused if it makes a difference now. \$\endgroup\$ – Anush Oct 21 '18 at 21:47
  • 2
    \$\begingroup\$ @Anush It does make a difference: the sums of [1, 2, 2, 2] are unique among arrays with 1 and 2 of length 4, but equal to the sums of [1, 1, 2, 3]. \$\endgroup\$ – Anders Kaseorg Oct 21 '18 at 21:56
2
\$\begingroup\$

Common Lisp SBCL, N = 14

call function (goahead n s)

    (defun sub-lists(l m &optional(x 0)(y 0))
  (cond; ((and(= y (length l))(= x (length l)))nil)
        ((= y (length l))m)
        ((= x (length l))(sub-lists l m 0(1+ y)))
    (t (sub-lists l (cons(loop for a from x to (+ x y)

             when (and(nth (+ x y)l)(nth a l)(< (+ x y)(length l)))
                ;   while (nth a l)
             ;while(and(< (+ x y)(length l))(nth a l))
                    collect (nth a l))m) (1+ x)y))
    ))
(defun permutations(size elements)
  (if (zerop size)'(())
 (mapcan (lambda (p)
                    (map 'list (lambda (e)
                           (cons e p))
                         elements))
     (permutations (1- size) elements))))
(defun remove-reverse(l m)
  (cond ((endp l)m)
    ((member (reverse (first l))(rest l) :test #'equal)(remove-reverse (rest l)m))
    (t (remove-reverse (rest l)(cons (first l)m)))))
(defun main(n s)
  (let((l (remove-reverse (permutations n `(,s ,(1+ s)))nil)))

  (loop for x in l
     for j = (remove 'nil (sub-lists x nil))
       collect(sort (make-set(loop for y in j
        collect (apply '+ y))nil)#'<)
     )
  ))
(defun remove-dups(l m n)
  (cond ((endp l)n)
        ((member (first l) (rest l) :test #'equal)(remove-dups(rest l)(cons (first l) m) n))
    ((member (first l) m :test #'equal)(remove-dups(rest l)m n))
    (t(remove-dups (rest l) m (cons (first l) n))))

  )
(defun goahead(n s)
  (loop for a from 1 to s
  collect(length (remove-dups(main n a)nil nil))))
(defun make-set (L m)
  "Returns a set from a list. Duplicate elements are removed."
  (cond ((endp L) m)
    ((member (first L) (rest L)) (make-set (rest L)m))
    ( t (make-set (rest L)(cons (first l)m)))))

here is the run times

CL-USER> (time (goahead 14 9))
Evaluation took:
  34.342 seconds of real time
  34.295000 seconds of total run time (34.103012 user, 0.191988 system)
  [ Run times consist of 0.263 seconds GC time, and 34.032 seconds non-GC time. ]
  99.86% CPU
  103,024,254,028 processor cycles
  1,473,099,744 bytes consed

(15 1047 4893 6864 7270 7324 7328 7328 7328)
CL-USER> (time (goahead 15 9))
Evaluation took:
  138.639 seconds of real time
  138.511089 seconds of total run time (137.923824 user, 0.587265 system)
  [ Run times consist of 0.630 seconds GC time, and 137.882 seconds non-GC time. ]
  99.91% CPU
  415,915,271,830 processor cycles
  3,453,394,576 bytes consed

(16 1502 8848 13336 14418 14578 14594 14594 14594)
\$\endgroup\$
  • \$\begingroup\$ How do I run this? Do I copy your code into a file and call it from sbcl somehow? \$\endgroup\$ – Anush Nov 6 '18 at 20:47
  • 1
    \$\begingroup\$ I use emacs and slime but you could put it in a file say test.lisp and in sbcl promp at your directory call (load "test.lisp") and then call the function how i have it at the bottom \$\endgroup\$ – JRowan Nov 6 '18 at 20:53
2
\$\begingroup\$

Clean

Certainly not the most efficient approach, but I'm interested in seeing how well a naive by-value filter does.

That said, there's still a bit of improvement to be made using this method.

module main
import StdEnv, Data.List, System.CommandLine

f l = sort (nub [sum t \\ i <- inits l, t <- tails i])

Start w
	# ([_:args], w) = getCommandLine w
	= case map toInt args of
		[n] = map (flip countUniques n) [1..9]
		_ = abort "Wrong number of arguments!"

countUniques 1 n = inc n
countUniques s n = length uniques
where
	lists = [[s + ((i >> p) bitand 1) \\ p <- [0..dec n]] \\ i <- [0..2^n-1]]
	pairs = sortBy (\(a,_) (b,_) = a < b) (zip (map f lists, lists))
	groups = map (snd o unzip) (groupBy (\(a,_) (b,_) = a == b) pairs)
	uniques = filter (\section = case section of [a, b] = a == reverse b; [_] = True; _ = False) groups

Place in a file named main.icl, or change the top line to module <your_file_name_here>.

Compile with clm -h 1500m -s 50m -fusion -t -IL Dynamics -IL StdEnv -IL Platform main.

You can get the version TIO (and myself) use from the link in the heading, or a more recent one from here.

\$\endgroup\$
  • \$\begingroup\$ I don't think this code gives the right output. I tried it with s=8 and it gives [9,86,126,130,130,130,130,130,130] \$\endgroup\$ – Anush Nov 6 '18 at 20:44
  • \$\begingroup\$ @Anush hmm I know I tested it. I'll see if I changed anything between that and the posted one, give me a few hours and I can do it on my break. \$\endgroup\$ – Οurous Nov 6 '18 at 21:27
  • \$\begingroup\$ @Anush Why are you providing s? In the question you state "For a given n, your code should output the answer for all values of s from 1 to 9." \$\endgroup\$ – Οurous Nov 6 '18 at 23:51
  • 1
    \$\begingroup\$ I think that is what you call a brain freeze on my part :) I will time your code now. \$\endgroup\$ – Anush Nov 7 '18 at 8:59

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.