4
\$\begingroup\$

Input

Two lists with binary values (list_a, list_b) of equal length=>3.

Output

Two lists with binary values (smoothed_a, smoothed_b) with minimal Forward Difference while keeping the same sum before and after processing sum(list_a) + sum(list_b) == sum(smoothed_a) + sum(smoothed_b).

Forward Difference being the absolute difference between items. For example:

  • [0, 1, 0] would be sum(abs([1, -1])) => 2

  • [1, 1, 1] would be sum(abs([0, 0])) => 0

Illustrative test cases

Formatted as (list_a, list_b) => (smoothed_a, smoothed_b)

([0, 0, 1, 0, 0],
 [1, 1, 0, 1, 1])
=>
([0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1])

The sum of both arrays pairs is 5. The forward difference was minimized to 0.

([1, 0, 1, 0, 1],
 [0, 0, 0, 1, 0])
=>
([0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0])

The sum of both arrays pairs is 4. The forward difference was minimized to 1.

Test cases

Formatted as (list_a, list_b): forward_diff => (smoothed_a, smoothed_b): min_diff where (smoothed_a, smoothed_b) are potential solutions.

([0, 0, 1],
 [0, 1, 0]): 3
([0, 0, 0],
 [0, 1, 1]): 1

([1, 1, 1],
 [0, 0, 0]): 0
([1, 1, 1],
 [0, 0, 0]): 0

([0, 1, 0],
 [1, 0, 1]): 4
([0, 0, 0],
 [1, 1, 1]): 0

([1, 1, 1, 1],
 [0, 0, 0, 0]): 0
([1, 1, 1, 1],
 [0, 0, 0, 0]): 0

([1, 0, 1, 1],
 [0, 0, 0, 1]): 3
([1, 1, 1, 1],
 [0, 0, 0, 0]): 0

([1, 0, 0, 1],
 [0, 0, 0, 1]): 2
([1, 1, 1, 0],
 [0, 0, 0, 0]): 1

([1, 1, 0, 1],
 [1, 0, 1, 0]): 3
([1, 1, 1, 1],
 [1, 0, 0, 0]): 1
\$\endgroup\$
  • \$\begingroup\$ So, if I understand right, "forward difference" means \$\sum_{i} | x_i - x_{i+1} |\$? \$\endgroup\$ – user77406 Oct 25 '18 at 17:08
  • \$\begingroup\$ @Rogem that is correct \$\endgroup\$ – Seanny123 Oct 25 '18 at 17:26

10 Answers 10

5
\$\begingroup\$

Jelly, 3 bytes

FṢṁ

Try it online!

Explanation:

  • Flatten the list
  • ort the flattened list
  • old the sorted flatten list in the shape of the input.
\$\endgroup\$
3
\$\begingroup\$

Retina, 4 bytes

O`\d

My shortest Retina answer thus far.

Try it online or verify all test cases.

Explanation:

Sorts all digits in the input, and leaves every other character unchanged (including their positions).

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

Python 2, 51 bytes

def f(a,b):s=sorted(a+b);l=len(a);print s[:l],s[l:]

Try it online!

Function that prints to STDOUT.

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

Husk, 3 bytes

½OΣ

Try it online!

½OΣ – Full program. Takes a list of two lists from the first CLA, outputs to STDOUT.
  Σ – Flatten (i.e. concatenate the contents of the 2 lists together).
 O  – Sort.
½   – Divide list in two halves (i.e. partition it into two equal-length sublists).
\$\endgroup\$
1
\$\begingroup\$

J, 7 bytes

$$/:~@,

explanation

$            NB. use the input shape
  $          NB. to shape the result of...
    /:~      NB. sorting the input
        @,   NB. after flattening it

Try it online!

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

05AB1E, 4 bytes

˜{2ä

Try it online or verify all test cases.

Explanation:

˜       # Flatten the (implicit) input list of lists
 {      # Sort it
  2ä    # Split it into two equal-sized lists (and output implicitly)
\$\endgroup\$
0
\$\begingroup\$

C gcc compile flag 64bit, 31 bytes by Rogem

-Df(a,n)=qsort(a,n+n,4,"\x8b\x07+\x06\xc3")

Try it online!

C gcc 32bit, 37 bytes

f(a,n){qsort(a,n+n,4,"YXZ\x8B\x00+\x02QQQ\xC3");}
struct {
    int a[5], b[5];
} test;
int main() {
    test.a[0] = test.a[2] = test.b[1] = 1;
    f(&test, 5);
    printf ("%d%d%d%d%d\n", test.a[0], test.a[1], test.a[2], test.a[3], test.a[4]);
    printf ("%d%d%d%d%d\n", test.b[0], test.b[1], test.b[2], test.b[3], test.b[4]);
    return 0;
}

Written non-ASCII to \x?? so se won't eat

\$\endgroup\$
  • \$\begingroup\$ Should probably mention that the input should be provided as a pointer to the first element of the list of lists. \$\endgroup\$ – user77406 Oct 25 '18 at 17:19
  • \$\begingroup\$ @Rogem x86 and x64 use different calling method, so they can't have same asm code \$\endgroup\$ – l4m2 Oct 25 '18 at 19:12
  • \$\begingroup\$ unfortunately, I do not have a 32-bit x86 to test it with, but the instructions 8b (MOV), 2b (SUB), c3 (RET) are shared between the two. This google hit seems to suggest that the registers would also be shared (in this case: eax, rdi, rsi) \$\endgroup\$ – user77406 Oct 25 '18 at 19:19
  • \$\begingroup\$ @Rogem No. x86 use cdecl that push everything via stack \$\endgroup\$ – l4m2 Oct 25 '18 at 19:20
  • \$\begingroup\$ Alright, won't argue since I don't know. \$\endgroup\$ – user77406 Oct 25 '18 at 19:21
0
\$\begingroup\$

Charcoal, 14 bytes

⪪⭆⊗Lθ‹ι№⁺θη¹Lθ

Try it online! Link is to verbose version of code. Explanation: Charcoal doesn't have a sort atom, but all we need to do is to put all the 1s at the front of the list, which is done by counting them and then setting that many list entries to 1 and the remaining ones to 0:

    θ           First input
   L            Length
  ⊗             Doubled
 ⭆              Map over implicit range and join
         θ      First input
          η     Second input
        ⁺       Concatenate
           ¹    Literal 1
       №        Count matches
      ι         Current index
     ‹          Less than
             θ  First input
            L   Length
⪪               Split into strings of that length
                Implcitly print each string on its own line
\$\endgroup\$
0
\$\begingroup\$

R, 57 bytes

function(a,b,s=1:sum(a|1),x=sort(c(a,b)))list(x[s],x[-s])

Try it online!

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

Scala, 60 bytes

def^(a:List[Int],b:List[Int])=(a:::b).sorted.splitAt(a.size)

Try it online!

\$\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.