current community

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 13 down vote favorite
1

This anecdote contains the following intriguing exchange:

"Fine, Fred," Avi interrupted. "Then how would you change this to avoid duplicate entries?"

"Oh, just change that one there to a negative one."

While this claim is not accurate in context, I do wonder if there's some plausible code for which that makes sense.

Your challenge is to write code (a program, a function, whatever) that fits this criteria:

  1. Merges two input lists into one, keeping duplicates. [edit: You can optionally assume that they are integers, and/or that the lists themselves are unique. You can't assume the integers are positive (the one answer that does this is grandfathered in).]
  2. A literal "1" appears somewhere in the code. If you change this to a literal "-1", the code does the same thing but removing duplicates.
  3. The code does not simply branch off of the 1/-1. We're not looking for if (1 < 1) removeDuplicates() or [do_nothing, merge_with_dups, merge_without_dups][1].call(), for example.

Input and output can be in any reasonable format you choose. One example might be

[1,2],[2,3]->[1,2,2,3] before the sign change, and [1,2,3] after.

This is a popularity contest. It is not code golf, unless you want to show off. I'll accept the highest-voted answer in about two weeks.

share|improve this question
 
What is the input - only integers? Positive and/or negative? If the input lists contain duplicates, should they be removed in the -1 case? –  WolframH May 9 '13 at 14:37
1  
Should we assume the input lists are sorted and don't contain duplicates themselves? –  ugoren May 9 '13 at 14:53
 
My first thought when I saw that on the DailyWTF was that they needed to define "merge". This question also needs a definition thereof. –  Peter Taylor May 9 '13 at 21:56
 
"They call him Boris the Bullet Dodger" "Why do they call him that?" "... Because he dodges bullets, Avi". Any Snatch fans on CodeGolf? –  Bojangles May 10 '13 at 5:50
add comment

7 Answers

up vote 10 down vote accepted

JavaScript

Take a conventional algorithm and write it with a bug:

function merge(a, b) {
  var ai = 0, bi = 0, oi = 0;
  var o = [];
  while (ai < a.length && bi < b.length) {
    var v = a[ai] < b[bi] ? a[ai++] : b[bi++];
    if (v !== o[oi + 1]) {
      o[oi++] = v;
    }
  }
  while (ai < a.length) o[oi++] = a[ai++];
  while (bi < b.length) o[oi++] = b[bi++];
  return o;
}

This code contains exactly one literal 1. If it is changed to -1, then duplicates will be removed. It can be used on any comparable values.

share|improve this answer
add comment
up vote 5 down vote

APL 22/23

Prompts for screen input via ←⎕ and returns an ordered merged list with or, if the leading one is set negative, without duplicates. 

(~1=0,-2=/v)/v←v[⍋v←⎕]

⎕:
    (1 2),(2 3)
1 2 2 3

(~¯1=0,-2=/v)/v←v[⍋v←⎕]

⎕:
    (1 2),(2 3)
1 2 3

Byte counters please note that the single byte APL characters have been converted to UTF8 to render properly on this site.

share|improve this answer
 
How does the -1 change everything? –  Johannes Kuhn May 9 '13 at 19:25
 
@Johannes Kuhn For the above example the code 0,-2=/v yields the vector 0 0 ¯1 0 with ¯1 indicating the position of a duplicate entry. Testing this vector against 1 and ¯1 yields 0 0 0 0 or 0 0 1 0 reversing the boolean elements gives 1 1 1 1 or 1 1 0 1. These vectors are used to select the appropriate elements from the merged vector. –  Graham May 9 '13 at 19:38
add comment
up vote 4 down vote

k (18)

Should work for any valid type of list

{(*1#(::;?:))@x,y}

Example:

k){(*-1#(::;?:))@x,y}[1 2 3 4;3 4 5 6]
1 2 3 4 5 6
k){(*1#(::;?:))@x,y}[1 2 3 4;3 4 5 6]
1 2 3 4 3 4 5 6
share|improve this answer
add comment
up vote 3 down vote

Python

def merge(a, b):
    return a + [i for i in b if i not in a*- 1]
share|improve this answer
add comment
up vote 1 down vote

Tcl

In the spirit of the quote

foreach item $list1 {
    if {$item in $list2} {set item [expr {$item * 1}]}
    lappend list2 $item
}
foreach item $list2 {
    if {$item >= 0} {lappend result $item}
}

If it is a duplicate, multiply it with (-)1, after that filter out negative values.

share|improve this answer
 
This answer was written that way before the question changed. In spirit of the quote, I still prefer making the entries negative. –  Johannes Kuhn May 9 '13 at 19:28
add comment
up vote 1 down vote

Bash

In the spirit of the context, this program removes the duplicates if you add a minus sign before the lowercase l on the grep line. If you add a minus sign before the uppercase I on the previous line, or before the digit 1 on the next line, the program doesn't behave differently.

The input files contain one integer per line (this is the usual representation of lists as text files). They must be passed as two arguments. The resulting list is written to standard ouptut.

# Create temp file for working
temp=$(mktemp -d)
# Copy left and right file to merge into same
cp $1 $temp/l
cp $2 $temp/r
cd $temp

while read num
do
  # I remove the output
  set `grep -Lax -e $num l ` <r> /dev/null
  if [ $# != 1 ]
  then echo $num >>r
  fi
done <l

cp r /dev/stdout
cd
rm -r $temp

Feel free to use this program as an example of your best code in an interview. All I ask is that you don't say that it's my best code.

share|improve this answer
add comment
up vote -1 down vote

I'm beginner in PHP I don't know if it's correct

$list1=explode(',',$_GET['list1']);
$list2=explode(',',$_GET['list2']);
$list_merged=array_merge($list1,$list2);
print_r($list_merged);
$list_unique=array_unique($list_merged);
print_r($list_unique);
share|improve this answer
6  
It doesn't look like this actually answers the challenge - I don't see a literal 1 anywhere in your code. –  Riking May 23 '13 at 14:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.