text:
Cheating a multiple choice test
Introduction
While studying, I tried to come up with several ways to cheat a multiple choice test. It basically is a compressed version of the multiple choice answers. The method goes as following:
The answers to the test:
BCAABABA

These can be converted to 3 different arrays, which indicates true or false if the current letter is the answer:
    B  C  A  A  B  A  B  A
A: [0, 0, 1, 1, 0, 1, 0, 1]
B: [1, 0, 0, 0, 1, 0, 1, 0]
C: [0, 1, 0, 0, 0, 0, 0, 0]

Interpreting these numbers as binary would compress this a lot. But this can actually be compressed a bit more. If you know the positions of A and B, you don't need the positions for C. This can be done with a bitwise NOT operator:
A: [0, 0, 1, 1, 0, 1, 0, 1]
B: [1, 0, 0, 0, 1, 0, 1, 0]

A+B: [1, 0, 1, 1, 1, 1, 1, 1]
C:   [0, 1, 0, 0, 0, 0, 0, 0]

Converting the arrays A and B to binary numbers would result in:
A: 00110101
B: 10001010

That means that 8 multiple choice answers can be compressed to two bytes!

Task
Given two numbers in binary, or two arrays consisting of only 0's and 1's with the same length, output the multiple choice answers

Rules

Input can be in the any form you like, like [1, 0, 0, 1] or 1001.
You may provide a program or a function.
You may assume that the input is always valid.
You may also output as a list, separated with spaces, etc.
The multiple choice answers only consist of A's, B's and C's. You may however use lower case instead.
This is code-golf, so the submission with the least amount of bytes wins!

Test cases
Input: [1, 0, 0, 1, 0, 0, 1] [0, 1, 0, 0, 1, 0, 0]
Output: ABCABCA

Input: [0, 0, 0, 0, 1, 0, 1, 1] [1, 0, 1, 0, 0, 0, 0, 0]
Output: BCBCACAA

Input: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Output: CCCCCCCCCC

Leaderboard

var QUESTION_ID=69770,OVERRIDE_USER=34388;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important;font-family:Arial}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

Here is my solution. It is written in English (interpreter freely available wherever you are), and is Study.. Six bytes. Beat that.

@CᴏɴᴏʀO'Bʀɪᴇɴ Sadly, English does not meet our standards of a programming language and is therefore not a valid submission :p

You can actually compress eight multiple choice questions to 1.625 bytes (13 bits) by interpreting the answers as base 3, so technically this isn't the most efficient method. :P

You could add another answer in the same space by using all four combinations of two bits, 00, 01, 10, 11 for answer a, b, c or d. You are not using 11.

@Doorknob another method: give 8 bytes for A, and find that of B only if the question's answer is not A. E.g. [0,0,1,1,0,1,0,1],[1,0,0,0,1,0,1,0] becomes [0,0,1,1,0,1,0,1],[1,0,1,1], 12 bits this way, but may be any integer within [8,16], with a mean(or maybe not a mean) of 13.33333333333

How does taking input as "two numbers in binary" work with test case #3? That is, how can the program know that it's specifically the 10-bit representation of 0b0000000000?

Now convert it to base 64 for maximum compression, and write it on your hand!

@TimPederick it can also be interpreted as a string.

@Adnan How doesn't it? It's Turing-complete and fulfills all the listed requirements.

Can we take the test an arbitrary number of times before taking it for reals.

English satisfies all the criteria. The only problem is there isn't an interpreter available before this question is asked.

@jimmy23013 Then perhaps a question should be asked to write an interpreter for English in as few bytes as possible.

@kasperd I've already written one! (31 bytes) Run interpret ‘yourprogramhere’ (with quotes) in English to interpret an English program.

All it takes is one 'Choose all that apply' type question, and we're all screwed!

Why compress to 16 bits when you can fit it in ~13?

Jelly, 7 6 bytes
_/ị“ḃ»

Typing on phone. Will add description.
(1,0) goes to A, (0,1) to B, and (0,0) to C. Arrays in Jelly are 1-based, and the indexing function ị works cyclically. Therefore, we can just fold subtraction over the input.
_              [vectorized] subtraction
_/             Fold subtraction over the input
   “ḃ»         "ABC" compressed. '»' terminates a compressed string.
  ị            Vectorized cyclic index.

Try it here.

how on earth did you type that on a phone? o-O

Samsung's clipboard history. It wasn't easy.

:-DD And congrats on 10k!

Lol, same size as English now @CᴏɴᴏʀO'Bʀɪᴇɴ

I golf my answer to "Study"; I am using an interpreter that is okay with grammatical mistakes. @RK.

English, -6- 5 bytes: Blast. Previous: Touche. Gave wrong output.

Just checking: do you even need the »? It seems wrong that Dennis' custom golfing language should require an unnecessary byte at the end of a program.

@ETHproductions Without it the interpreter thinks it's a normal string. I agree that it would be better to have a comprssed-string-start delimiter but I don't know how many symbols Dennis has free.

@ETHproductions http://chat.stackexchange.com/transcript/message/26992106#26992106

I was really confused about the "ABC" thing until I remembered that strings are 1-indexed .

MATL, 14 9 bytes
2*+ 67w-c

Uses current version (10.1.0)
Try it online!
Explanation
Summary of what the code does
2*       % implicitly input array and multiply it by 2
+        % implicitly input array and add it to the first one
67w-    % subtract from 67
c        % convert to char. Implicitly display

Detailed explanation of how it works
2        % Push number 2 onto the stack
*        % Multiply the top two stack elements. Since there's only one
         % element, this triggers implicit input of a (yet inexistent)
         % element below the existing one. This is the first input array,
         % which will be called "A". Both "A" and number 2 are consumed,
         % and the array 2*A is left on the stack.
+        % Add the top two stack elements. Again, since there's only
         % one element (namely array 2*A) this triggers implicit input
         % of the second array, call it "B". Both 2*A and B are consumed
         % and 2*A+B is left on the stack
         % A blank space is needed after the "+" symbol to prevent it from
         % being interpreted as part of number "+67"
67       % Push number 67 onto the stack. The stack now contains, bottom
         % to top, 2*A+B and 67.
w        % Swap top two elements. The stack now contains 67 and 2*A+B
-        % Subtract top two elements. These are consumed and the result
         % 67-A*B is left on the stack
c        % Convert to char array, interpreting each number as ASCII code.
         % Number 67 corresponds to letter 'C'. Therefore at positions
         % where both arrays A and B were 0 this gives 'C' as result.
         % Where A was 1 and B was 0, i.e. 2*A+B is 2, this gives 'A'.
         % Where A was 0 and B was 1, i.e. 2*A+B is 1, this gives 'B'.
         % The stack contents, namely this char array, are implicitly
         % displayed at the end of the program.

This is amazing! Can you write a bit more about why this works? Why 67? And how does multiply input array by 2 and then add input array differ from 'multiply input array by 3'?

@Vincent Sure! I'll add some more detailed explanation later in the day

@Vincent Done! Let me know if it's clearer now

J, 8 bytes
'CAB'{~-

Usage:
   0 0 1 0 0 1 ('CAB'{~-) 0 1 0 1 0 0
CBABCA

Try it online here.

Java, 81 bytes
No reputation to comment the already existing Java solution, so here goes:
void x(int[]a,int[]b){int j=0;for(int i:a)System.out.printf("%c",67-2*i-b[j++]);}

This is smart. :D I like. I see that you got a teensy bit of inspiration, though. ;)

Damn, that's clever. I spent ages trying to figure out how I could get a foreach loop to fit...

Retina, 44 bytes
T`d`BA
B(?=(.)* .*B(?<-1>.)*(?(1)!)$)
C
 .+

The trailing linefeed is significant. Input is like
001101010 100010100

Try it online!
Explanation
T`d`BA

Start by turning 0s into B and 1s into A. That makes the first half correct, except that it lists B when it should contain C. We can identify those erroneous Bs by checking whether there's a B in the same position of the second string:
B(?=(.)* .*B(?<-1>.)*(?(1)!)$)
C

The lookahead is a classic balancing group counting technique to match up the positions of the two Bs. The (.)* counts the suffix after the first B by pushing one capture onto group 1 for each character. Then (?<-1>.)* pops from that group again. The $ ensures that we can reach the end of the string like that, and the (?(1)!) ensures that we've actually depleted the entire group.
Finally, we get rid of the separating space and the second string:
 .+

3 upvotes in the first 15 seconds of posting; that must be some kind of record.

@CᴏɴᴏʀO'Bʀɪᴇɴ Flattering, but I wonder how many of those 3 upvoters actually read and understood the answer in 15 seconds. :/

I did. I am rather fluent in reading regex and retina.

JavaScript ES6, 36 bytes
(a,b)=>a.map((x,y)=>"CBA"[x*2+b[y]])

Very simple, and probably obvious enough to understand: Map each item and index in a to the char at position (x*2 + item at index y in b) in "CBA".

Please add this as your ungolfed version :3

@CᴏɴᴏʀO'Bʀɪᴇɴ He CBA to do that. Also, he can't anyway, because do is a reserved keyword, so that's invalid syntax.

@Patrick simple fix: Do(...)

brainfuck, 52 bytes
,+[->>----[<--->----],+]<[<[>--<-]<]>>[<,[>-<-]>.>>]

Requires an interpreter that lets you go left from cell 0 and has 8-bit wrapping cells. Unlike most of my answers, EOF behaviour doesn't matter.
Takes byte input, with 0xFF as a delimiter. A stream of bytes representing the first input under "Test cases" would look like this:
0x01 0x00 0x00 0x01 0x00 0x00 0x01 0xFF 0x00 0x01 0x00 0x00 0x01 0x00 0x00

I could save a couple bytes by having 0x00 as a delimiter and using 0x01 and 0x02 as 0 and 1 respectively, but that felt like cheating :P
Once I figured out my strategy, writing this program was very easy. To find the nth letter to output, start with 0x43 (capital C in ASCII) and subtract ((nth element of first sequence)*2 + nth element of second sequence)
For what it's worth, here's the 52 byte program split into 3 lines and with some words beside them:
Get input until hitting a 255 byte; put a 67 byte to the right of each one
,+[->>----[<--->----],+]

For each 67 byte: Subtract (value to the left)*2 from it
<[<[>--<-]<]

For each byte that used to contain 67: Subtract input and print result
>>[<,[>-<-]>.>>]

Haskell, 29 bytes
zipWith(\x y->"BCA"!!(x-y+1))

An anonymous function. Use like:
>> zipWith(\x y->"BCA"!!(x-y+1)) [1, 0, 0, 1, 0, 0, 1] [0, 1, 0, 0, 1, 0, 0]
"ABCABCA"

I tried making the function point-free but got a total mess. 2022 edit: Wheat Wizard found a version for 28 bytes, one shorter than nimi's 29-byte equivalent:
zipWith$(!!).(["CB","AC"]!!)

a point-free version of equal length: zipWith((!!).(["CB","AC"]!!))

A point-free version that's 1 byte shorter zipWith$(!!).(["CB","AC"]!!).

Pyth, 18 16 10 bytes
3rd attempt: 10 bytes
Thank FryAmTheEggman for reminding me of the existence of G!
VCQ@<G3xN1

Input is of the form [ [0,0,1,1,0,1,0,1] , [1,0,0,0,1,0,1,0] ], which is essentially a matrix: row for choice and column for question number.
Hand-compiled pythonic pseudocode:
              G = "abcdefghijklmnopqrstuvwxyz"    // preinitialized var
VCQ           for N in transpose(Q):    // implicit N as var; C transposes 2D lists
   @<G3           G[:3][                // G[:3] gives me "abc"
       xN1            N.index(1)        // returns -1 if no such element
                  ]

2nd attempt: 16 bytes
VCQ?hN\A?.)N\B\C

Input is of the form [ [0,0,1,1,0,1,0,1] , [1,0,0,0,1,0,1,0] ], which is essentially a matrix: row for choice and column for question number.
This compiles to
assign('Q',Pliteral_eval(input()))
for N in num_to_range(Pchr(Q)):
   imp_print(("A" if head(N) else ("B" if N.pop() else "C")))

Ok, I know that looks messy, so let's hand-compile to pythonic pseudocode
                 Q = eval(input())
VCQ              for N in range transpose(Q): // implicit N as var; transposes 2D lists
   ?hN               if head(N):              // head(N)=1st element of N
      \A                 print("A")           // implicit print for expressions
                     else:
        ?.)N             if pop(N):
            \B               print("B")
                         else:
              \C             print("C")

1st attempt: 18 bytes
V8?@QN\A?@Q+8N\B\C

With input of the form [0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,0], essentially concatenation of two lists.
This compiles to
assign('Q',Pliteral_eval(input()))
for N in num_to_range(8):
   imp_print(("A" if lookup(Q,N) else ("B" if lookup(Q,plus(8,N)) else "C")))

Again, compiling by hand
                   Q = eval(input())
V8                 for N in range(8):
  ?@QN                 if Q[N]:
      \A                  print("A")
                       else:
        ?@Q+8N            if Q[N+8]:
              \B              print("B")
                          else:
                \C            print("C")

And there goes the first codegolf in my life!!! I just learned Pyth yesterday, and this is the first time I ever participated in a code golf.

Welcome to Programming Puzzles and Code Golf! This looks very nice for a first time, +1

Always nice to see someone learning Pyth! You can golf .) to be e, and I think it can be golfed quite a bit more. Consider the variable G which contains the lower case alphabet, I believe you can get to around 10 bytes using it, happy golfing! :)

@FryAmTheEggman oh e! I was searching for it for several minutes! Also, thank you for reminding me of G. You are right, 10 bytes!

Python 3, 39 bytes.
Saved 1 byte thanks to FryAmTheEggman.
Saved 2 bytes thanks to histocrat.
Haven't been able to solve with a one liner in a while!
lambda*x:['CBA'[b-a]for a,b in zip(*x)]

Here's my test cases. It also shows the way I'm assuming this function is called.
assert f([1,0,0,1,0,0,1], [0,1,0,0,1,0,0]) == ['A', 'B', 'C', 'A', 'B', 'C', 'A']
assert f([0, 0, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0, 0, 0]) == ['B', 'C', 'B', 'C', 'A', 'C', 'A', 'A']
assert f([0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) == ['C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C']

It uses zip to iterate through the arrays pairwise, and then indexes into a string to pick the correct letter. This all happens in a list comprehension, so it automagically becomes a list. The core of this solution is that the only possible combinations of a and b are [0, 1], [1, 0], [0, 0]. So if we subtract them, we get one of -1, 0, 1 which gets us the last, first, middle element respectively.

Mathematica, 30 24 22 19 bytes
3 bytes saved due to @alephalpha.
{A,B,C}[[3-2#-#2]]&

Quite simple.

{A,B,C}[[3-2#-#2]]&

Ruby, 35 bytes
->a,b{a.zip(b).map{|x,y|:CAB[x-y]}}

Usage:
->a,b{a.zip(b).map{|x,y|:CAB[x-y]}}[[1,0,0],[0,1,0]]
=> ["A", "B", "C"]

Takes the (x-y)th zero-indexed character of "CAB". (1-0) gives 1, and thus A. (0-0) gives 0, and thus C. (0-1) gives -1, which wraps around to B.
Alternate shorter solution with weirder output:
->a,b{a.zip(b){|x,y|p :CAB[x-y]}}

Output is quoted strings separated by newlines, which seems a bridge too far somehow.

Japt, 13 bytes
¡#C-X*2-VgY)d

Try it online!
How it works
¡#C-X*2-VgY)d  // Implicit: U, V = input lists
¡              // Map each item X and index Y in U to:
 #C-X*2        //  The char code of C (67), minus 2X,
       -VgY)   //  minus the item at index Y in V.
            d  //  Convert to a char code.

Vitsy, 40 bytes
sigh My baby was not made to do array manipulation.
Expects input through STDIN (something I never do) with a leading ".
WX&WXl\[68*-1+m]
?68*-2*"C"-i*O?
"B"O?X?
Explanation in the (soon available) verbose mode:
0:
STDIN;
remove top;
make new stack;
STDIN;
remove top;
push length of stack;
repeat next instruction set top times;
begin recursive area;
push 6;
push 8;
multiply top two;
subtract top two;
push 1;
add top two;
goto top method;
end recursive area;
1:
rotate right a stack;
push 6;
push 8;
multiply top two;
subtract top two;
push 2;
multiply top two;
toggle quote;
push cosine of top; // this is character literal "C"
toggle quote;
subtract top two;
push input item;
multiply top two;
output top as character;
rotate right a stack;
2:
toggle quote;
B;
toggle quote;
output top as character;
rotate right a stack;
remove top;
rotate right a stack;
This is getting golfed better real soon, people. I'm so sorry for its current length.
Basically, I treat the input as a string, and then manipulate from there.
Try it online!

:O Cannot wait until verbose mode. That will be interesting. Like the use of W!

@Adnan It is the input tab in tryitonline, but on the local interpreter, simply run the program and input each set of 0 and 1 with a leading " and a trailing newline while the program is running (W technically is prompt).

Ahh, I gave the input in the arguments section :p. Nice answer though :)

@Adnan It took me a while to figure this out - Vitsy autoparses input if it recognizes that it's a double. You can technically have a leading anything except for numbers, and it'll work the same.

Heh, that is quite weird, but on the other side it can be useful.

TI-BASIC, 59 57 50 37 36 bytes
Takes one list from Ans, and the other from Prompt L₁. Saved 13 bytes thanks to Thomas Kwa's suggestion to switch from branching to sub(.
Prompt X
For(A,1,dim(∟X
Disp sub("ACB",2+∟X(A)-Ans(A),1
End

I'll have to look for what Thomas Kwa said he found in the comments tomorrow. ¯\_(ツ)_/¯

You still have some bytes to save! Replace the Prompt L₁ with Prompt X and L₁ with ∟X. There's even more, but I'll let you find it.

@ThomasKwa L1 is a one-byte token, last I checked. Referencing it again with the list+x would be two bytes... am I not correct?

L1 is two bytes.

@ThomasKwa Oh. Dang.

I count 37 bytes as it is currently. (You can get 35.)

Rust, 79
Saved 8 bytes thanks to Shepmaster.
Saved 23 bytes thanks to ker.
I'm positive this could be golfed down a lot, but this is my first time writing a full Rust program.
fn b(a:&[&[u8]])->Vec<u8>{a[0].iter().zip(a[1]).map(|(c,d)|67-d-c*2).collect()}

Here's the ungolfed code and test cases in case anyone wants to try to shrink it.
fn b(a:&[&[u8]])->Vec<u8>{
    a[0].iter().zip(a[1]).map(|(c,d)|67-d-c*2).collect()
}
fn main() {
    assert_eq!("ABCABCA", b(&[&[1, 0, 0, 1, 0, 0, 1], &[0, 1, 0, 0, 1, 0, 0]]));
    assert_eq!("BCBCACAA", b(&[&[0, 0, 0, 0, 1, 0, 1, 1], &[1, 0, 1, 0, 0, 0, 0, 0]]));
    assert_eq!("CCCCCCCCCC", b(&[&[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], &[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]));
}

The approach is pretty similar to my Python answer. The main difference being that I can't directly index strings, so I can't do the c-d trick.

would it be legal to use a closure instead of a function? then you could skip all the types in the declaration and just pass a[0] and a[1] as two separate arguments.

also using the 64-y-2*x trick from the Octave solution saves quite a few bytes due to being able to use u8 instead of usize: http://is.gd/GNPK76

@ker I'm not totally sure about using a closure. I would assume it's okay, because it's essentially an anonymous function, right?

as long as you don't capture any surroundings it's exactly like an anonymous function.

@ker Then yeah, closure should be fine.

Octave, 19 bytes
@(x,y)[67-y-2*x,'']

Test:
f([1 0 0 0 1 1],[0 1 0 0 0 0])
ans = ABCCAA

I'll add an explanation later when I have a computer in front of me. This was written and tested on octave-online on my cell.

CJam, 10 bytes
'Cq~z2fbf-

Input as a list of two lists, e.g.
[[1 0 0 1 0 0 1] [0 1 0 0 1 0 0]]

Test it here.
Explanation
Treating the pairs as bits of a base-2 number, we get 2 for A, 1 for B and 0 for C.
'C  e# Push the character C.
q~  e# Read and evaluate input.
z   e# Transpose the pair of lists to get a list of pairs.
2fb e# Convert each pair from base 2.
f-  e# Subtract each result from the character C.

R 29 16 bytes
LETTERS[3-2*A-B]

removed declaration of function since I saw it's common in other contests.

Python 3, 48 45 bytes
I thought I had an elegant solution, then I saw @Morgan Thrapp's answer...
edit: Saved three bytes thanks to the aforementioned.
lambda*x:['A'*a+b*'B'or'C'for a,b in zip(*x)]

lambda *x:[a*'A'or b*'B'or'C'for a,b in zip(*x)]

Ah nice. Didn't see lamba*x:. I always think it's as compact as can be then I get told/find even more tricks. I really like your solution btw, very nice.

Java, 131 122 110 90 bytes
EDIT: Thanks to Bifz / FlagAsSpam for the help and inspiration
void x(int[]a,int[]b){int j=0;for(int i:a){System.out.print(i>0?"A":b[j]>0?"B":"C");j++;}}

First submission, naive Java solution. Can almost certainly be improved :)
static String x(int[]a,int[]b){String o="";for(int i=0;i0?"A":b[i]>0?"B":"C";return(o);}

==1 can be >0; it would also be better for you to return o rather than printing.

How about: void x(int[]a,int[]b){for(int i=0;i0?"A":b[i]>0?"B":"C");} (94 bytes)? You don't need the static declaration on functions.

You have to declare i first, +4 bytes :D

Perl 5 - 47
Already 30 answers and no perl? Here is a naive first attempt then :-)
Just the function:
sub x{($g,$h)=@_;map{$_?a:$h->[$i++]?b:c}@{$g}}

Usage:
@f = (0, 0, 0, 0, 1, 0, 1, 1);
@s = (1, 0, 1, 0, 0, 0, 0, 0);

print x(\@f, \@s);

I'm pretty sure that something better could be done with regex, but I couldn't find how.

PowerShell, 40 Bytes
param($a,$b)$a|%{"CBA"[2*$_+$b[++$d-1]]}

Takes input as two explicit arrays, e.g.. PS C:\Tools\Scripts\golfing> .\cheating-a-multiple-choice-test.ps1 @(1,0,0,1,0,0,1) @(0,1,0,0,1,0,0), and stores them in $a and $b. Next, loop through $a with $a|{...}. Each loop, we output a character indexed into the string "CBA", with the index decided by twice the current value $_, plus the value of $b indexed by our helper variable that's been pre-added then subtracted.
As an example, for the first test case, $a = @(1,0,0,1,0,0,1) and $b = @(0,1,0,0,1,0,0). The first loop iteration has $_ = 1, $d = $null (since $d hasn't previously been declared). We pre-add to $d so now $_ = 1 and $d = 1 (in PowerShell, $null + 1 = 1), meaning that $b[1-1] = $b[0] = 0. Then 2 * 1 + 0 = 2, so we index "CBA"[2], or A.

R 36 34 bytes
function(a,b)c('B','C','A')[a-b+2]

Two bytes saved removing unnecessary braces

You can save two bytes by removing the braces in the function definition. They aren't necessary since the function body consists of a single statement.

, 12 chars / 22 bytes
Ⓒ…îⓜṃ-$*2-í_

Try it here (Firefox only).
Explanation
Translates to Javascript ES6 as
String.fromCharCode(...input1.map(($,_)=>67-$*2-input2[_]))

F#, 33 bytes
Seq.map2(fun a b->67-a*2-b|>char)

That's a partially applied function that takes two int sequences - two arrays work fine - and returns a new sequence of characters representing the correct answers. =)

Seriously, 14 bytes
,,Z`i-"CBA"E`M

Try It Online
Probably due to a bug in the safe mode version of the interpreter, you must add an X to get it to work right in the online version. Download the local version to get the above program working correctly as-is.
It's too short to warrant a full explanation, so I'll just say: it uses the same algorithm as the Jelly answer.

JavaScript ES6, 75 bytes
I went the extra mile to accept integer arguments instead of array arguments.
(a,b)=>[...Array(8)].map((_,n)=>'CBA'[(a&(s=128>>n)*2+b&s)/s]).join('')

Explanation:
(a,b)=>              // input of two integers representing 8 answers (max value 255 each)
[...Array(8)]        // generates an array with 8 indices that allows .map() to work
.map((_,n)=>         // n is each index 0-7
'CBA'[...]           // reading character from string via index reference
      (...)          // grouping for division
       (a&...)       // AND operator to test if answer is A
          (s=128>>n) // calculating binary index in integer input and storing reference
       *2            // bias index in 'CBA' so truthy is 2 instead of 1
       +(b&s)        // AND operator to test if answer is B
      /s             // divide by binary index to convert AND operators to increments of 1
.join('')            // convert to string without commas

Credit to @ETHproductions for string indexing logic.
Test Here

f=(a,b)=>[...Array(8)].map((_,n)=>'CBA'[((a&(s=128>>n))*2+(b&s))/s]).join('');

console.log(f(0b01001001, 0b00100100));
console.log(f(0b00001011, 0b10100000));
console.log(f(0b00000000, 0b00000000));

Pssst
For 3 extra bytes, it can display the representation for up to 30 answers:
(a,b)=>[...Array(30)].map((_,n)=>'CBA'[((a&(s=1<<30>>n))*2+(b&s))/s]).join('')

Retina, 46 bytes
^
%
+`%(.)(.* )(.)
$1$3,%$2
10
A
01
B
00
C
\W
[empty line]

Merges the two strings and chooses the letters according to the digit pairs.
Try it online here.

Lua, 87 Bytes
Simply testing the values in the arrays, and concatenating A, B or C.
function f(a,b)s=""for i=1,#a do s=s..(0<a[i]and"A"or 0>n&1?65:b>>n&1?66:67);}

The sequences of bits are interpreted as big-endian (MSB is the first answer), the third parameter n indicates the number of answers encoded.
Test main:
int main() {
  F(73, 36, 7);
  putchar('\n');
  F(11, 160, 8);
  putchar('\n');
  F(0, 0, 10);
  putchar('\n');
}

Clojure, 41 bytes
(52 if a sequence of chars is not a permitted output format)
Finally a semi-cryptic Clojure answer :D Output as a sequence of characters:
#(map(fn[a b](or({1\A}a)({1\B}b)\C))% %2)

This version outputs a string:
#(apply str(map(fn[a b](or({1\A}a)({1\B}b)\C))% %2))

{1 \A} is a "dictionary" with key 1 and value character A. ({1 \A} a) returns \A if a is 1 and nil otherwise, same logic for b. or takes the first "truthy" value, which is \C if both a and b are zero.

Vyxal d, 10 bytes
~+†W∩vTkAİ

Try it Online!


text:
The branch predictor challenge
Every day, every minute, ... every microsecond, many decisions are made by your computer. In high-level languages, these typically take the form of statements like if, while and for, but at the most basic level there exist machine language instructions called branch/jump instructions. Modern processors queue instructions up in a pipeline, and this means that the processor needs to decide whether to fill the pipeline with instructions immediately following a branch (i.e. it is not taken) or the instructions at the branch destination.
If the processor does not guess correctly, the instructions which have been wrongly entered into the pipeline need to be ignored and the correct instructions must be fetched, causing a delay. The job of the branch predictor is to try and guess whether the branch will be taken to avoid the costly action of refilling the pipeline.
You must write a predictor that will, given a sequence of past decisions, guess the next decision correctly. Your program can be written in any language, provided you specify the link to its interpreter if it's an obscure/golfing language. It must take the past actual history as its first command-line argument, but it will not be provided for the first guess of the sequence. You must then return your guess by printing it to stdout. A decision is of the form "y" or "n". Each test case is a sequence of 72 decisions, so you can assume that the specified history argument will never be longer than 71 characters. For example, the "Alternating 1" test:
ynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynyn

You will be disqualified if your program:

does not return a result within one second
does not return either a y or n (new lines don't matter and are ignored)
attempts to modify any code or file associated with this challenge, including other contender's code
contains anything otherwise malicious

You may use a file for persistence if you wish, but it must be uniquely named and conform to the above.
This is a code-challenge, not code-golf. Victory will be granted by the branch predictor predictor to the contender whose solution successfully predicts the most branches in the whole test suite. Tests:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy,All yes
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn,All no
ynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynyn,Alternating 1
nnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyy,Alternating 2
yyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnn,Alternating 3
nnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyy,Alternating 4
yyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnn,Alternating 5
nnnnnnnnnnnnyyyyyyyyyyyynnnnnnnnnnnnyyyyyyyyyyyynnnnnnnnnnnnyyyyyyyyyyyy,Alternating 6
yyyyyyyyyyyyyyyyyynnnnnnnnnnnnnnnnnnyyyyyyyyyyyyyyyyyynnnnnnnnnnnnnnnnnn,Alternating 7
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyynnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn,Alternating 8
yynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyyn,2-1
ynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnn,1-3
nyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyy,5-1
nnnnnnnnnnnynnnnnnnnnnnynnnnnnnnnnnynnnnnnnnnnnynnnnnnnnnnnynnnnnnnnnnny,1-11
nyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyynyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy,35-1
yynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnn,2-4
ynnyyynyynnnynnyyynyynnnynnyyynyynnnynnyyynyynnnynnyyynyynnnynnyyynyynnn,1-2-3
ynynynynynynynynynynynynynynynynynynyyyyyyyyyyyyyyyyyynnnnnnnnnnnnnnnnnn,A1/A7
yyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnnnnyynnyynnyynnyynnyynnyynnyynnyynnyy,A5/A2
nnnnnnnnnnnnyyyyyyyyyyyynnnnnnnnnnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyy,A6/A4
nyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy,5-1/35-1
yyynnnyyynnnyyynnnnyyyyyyyyyyyyyyyyyyyyyyynyyyyynyyyyyyynnnnyynnnnyynnnn,A3/Y/5-1/2-4
yynnnnyynnnnyynnnnnyynnnynnyyynyynnnnnnynnnynnnynnnynnyynyynyynyynyynyyn,2-4/1-2-3/1-3/2-1

The full set of tests and runner program are situated at this GitHub repository. Simply add your predictor to src/predictors.txt in the form <name>,<command to run> and run main.py. I have provided two very basic predictors already for simple testing. I would recommend a column width of at least 92 when running the runner for nice output. If you happen to spot any bugs with it, please let me know. :)

I downvoted this challenge because in my opinion it does not capture the essence of a branch predictor. Right now your challenge is more about general predicion AI rather than a branch predictor. At the very least a branch predictor challenge must have very stringent memory requirements, incremental history, and every decision must be a function of a memory address. Also, your challenge is not self-contained.

I like this challenge.  I think that a purely 50/50 random test case is a bad idea.  However, an 80/20 random would be fine, as well as other test cases that include parts that are random (as some of your test cases currently do).  I'd recommend including all of your test cases on your post.

@NathanMerrill Thanks, I've removed all randomness from tests.

@orlp I'm not sure how to incorporate every aspect of a branch predictor into a challenge that's relatively easy and (hopefully) fun. With regards to it being a general AI predictor: isn't that what branch predictors are, at a high-level, when you take away the more complex elements? This challenge is also about educating those who are in this area, i.e. computing, and provoke some thought about performance (not that BP is usually the biggest performance issue, but I think you get me).

No, the interesting part of a branch predictor is how to manage a limited amount of shared space in order to predict branches at arbitrary positions in the executable code. The challenge as-is is more of a coin flipping game than a branch predictor.

@orlp How is this challenge in any way like coin flipping? The test cases have been refined to contain situations that a branch predictor would likely encounter.

@Doddy Sorry, I meant coin guessing game. One player keeps generating zeros and ones, and the other tries to guess then.

In high school a friend of mine write a TI85 BASIC game where you tried to stump a pattern guesser while entering 1/0 bits. I wish I had his code to submit for this.

are we supposed to avoid optimizing for these test cases? someone is going to just submit a "perfect" algorithm that compares the history to the known test corpus and scores 95%+

@Sparr I'm not sure, but I believe you're generally not supposed to do that anyway. Unless, of course, the specs explicitly say otherwise.

this would make an interesting kolmogorov-complexity code-golf challenge, if everyone was trying to make a perfect predictor for this data set as short as possible.

I keep getting disqualified for no apparent reason. I think I print my result within one second (other types of testing showed me that), and I print a "y" or a "n"...

Ohhh... I see... From the editing of your program just for the sake of testing, I see that there is a but in your program. It thinks that a "y" is "121", as the ASCII value of "y" is 121...

I'm pretty sure some of the tests are wrong. yyyyyynnnnnn,Alternating 5 noticed that this is six y's in a row, etc. All the Alternating 5-8 test cases are wrong.

Compressor (Ruby), score 1502/1656 ≈ 90.7%
require 'zlib'
input = $*[0].to_s.chomp
recent_input = input[-35..-1] || input
puts recent_input.chars.uniq.min_by { |char| [Zlib::Deflate.deflate(input+char,9).size,-input.count(char),-input[-10..-1].to_s.count(char)] } || ?y

Checks whether the current string would be more compressible if 'y' or 'n' were added to the end. If equally compressible, use the one that's shown up the most.

DéjàVu (Mathematica), score 503/552 ≈ 91.123%
If[Length[$ScriptCommandLine] < 2, Print["y"]; Exit[]];
input = Characters[$ScriptCommandLine[[2]]] /. {"y" -> 1, "n" -> 0};
For[test = Length[input], !
   ListQ[ker = FindLinearRecurrence[input[[-test ;;]]]], test--];
Print[LinearRecurrence[ker, input[[-test ;; Length[ker] - test - 1]],
     test + 1][[-1]] /. {1 -> "y", _ -> "n"}];

Looks for a linear recurrence in the pattern, and computes the next term. For testing, save as DéjàVu,MathematicaScript -script <file>.

Historian (Kotlin), score 1548/1656 ≈ 93.478%
Predicts the future from the past.
fun main(args : Array<String>) {
    if (args.size == 0) {
        println('y')
        return
    }
    val history = args[0].reversed()
    var bestLength = 0
    var ys = 0
    var ns = 0
    for (i in 1..history.length-1) {
        var length = 0
        var j = i
        while (j < history.length) {
            if (history[j] == history[j - i]) {
                length++
            } else {
                break
            }
            j++
        }
        if (length > bestLength) {
            bestLength = length
            ys = 0
            ns = 0
        }
        if (length == bestLength) {
            if (history[i - 1] == 'y') {
                ys++
            } else {
                ns++
            }
        }
    }
    println(if (bestLength == 0) history[0] else if (ys >= ns) 'y' else 'n')
}

Compile with: kotlinc Historian.kt
Run with: kotlin HistorianKt

Pattern-Finder (Java), score 1570/1656 (≈94.8%) 1532/1656 (≈92.5%)
Slight improvements for complex patterns.
public class Main {

    public static void main(String[] args) {
        if (args.length == 0) {
            System.out.print("y");
            return;
        }
        System.out.print(new Pattern(args[0]).getNext());
    }

}

class Pattern {

    private String pattern;
    private int index;
    private int length;

    public Pattern(String string) {
        setPattern(string);
    }

    private void setPattern(String string) {
        if (string.length() == 0) {
            this.pattern = "y";
            this.index = 0;
            this.length = 1;
            return;
        }
        if (string.length() == 1) {
            this.pattern = string;
            this.index = 0;
            this.length = 1;
            return;
        }
        if (string.startsWith("ynnyyy")) {
            this.pattern = "ynnyyynyynnn";
            this.index = string.length() % 12;
            this.length = 12;
            return;
        }
        this.length = 0;
        char first = string.charAt(0);
        char current = first;
        boolean hasReverse = false;
        while (length < string.length() - 1 && !(hasReverse
                && current == first)) {
            hasReverse |= current != first;
            length++;
            current = string.charAt(length);
        }
        if (!(hasReverse && current == first)) {
            this.pattern = Character.toString(current);
            this.index = 0;
            this.length = 1;
            return;
        }
        this.pattern = string.substring(0, length);
        int i = length;
        while (i <= string.length() - length) {
            if (!string.substring(i, i + length).equals(pattern)) {
                setPattern(string.substring(i));
                return;
            }
            i += length;
        }
        this.index = string.length() % i;
        if (!string.substring(i).equals(pattern.substring(0, index))) {
            setPattern(string.substring(i));
        }
    }

    public char getNext() {
        char result = pattern.charAt(index);
        index = (index + 1) % length;
        return result;
    }

}

@TheNumberOne Are you sure? If so, I will put that as the score. Good job on your post though; you win me!

Ah, you improved your performance for the 1-2-3 test case.

@TheNumberOne Yes, after some serious testing, I realised that was killing my percentage. The question does not exactly say that what I did was not allowed...

Factorio (Python3), score 1563/1656 ≈ 94.38%
Factors the sequence from left to right into a series of repeating and alternating patterns. Primarily favours longer match lengths, but chooses repeating over alternating patterns and shorter over longer cycle lengths in case of a tie.
def main():
    if len(sys.argv) < 2:
        print('y')
        sys.stdout.flush()
        return
    history = sys.argv[1]
    while history:
        score = 0
        period = 0
        l = 0
        for p in range(1, len(history)):
            if history[0] == history[p]:
                m = lambda a, b: a == b
                s0 = 1
            else:
                m = lambda a, b: a != b
                s0 = 0
            s = 0
            for i in range(len(history)):
                j = i + p
                if j < len(history):
                    if not m(history[i], history[j]):
                        break
                    s += 1
            if s > score or s == score and s0 > score0:
                score = s
                score0 = s0
                period = p
                match = m
                l = j
        if period == 0:
            print(history[0])
            sys.stdout.flush()
            return
        if l >= len(history):
            break
        l = (l // period) * period
        history = history[l:]
    print('y' if match(history[-period], 'y') else 'n')
    sys.stdout.flush()

if __name__ == '__main__':
    main()

Repeater (Python), score 1173/1656 ≈ 70.83%
This predictor simply guesses yes if there's no history, otherwise repeats the previous actual outcome.
import sys

if len(sys.argv) == 1:
   print "y"
else:
   print sys.argv[1][-1:]

!Repeater (Python), score 483/1656 ≈ 29.17%
If there's no history this predictor will guess no, otherwise will repeat the opposite of the last actual outcome.
import sys

if len(sys.argv) == 1:
   print "n"
else:
   if sys.argv[1][-1:] == "y":
      print "n"
   else:
      print "y"

2-toucher (Python), score 1087/1656 ≈ 65.64%
If there were at least two previous outcomes that were the same, or there has been one outcome so far, this predictor will choose the same. If there is no history, it will choose "y". If there were at least two outcomes and the most recent two were not the same, it will choose the opposite of the most recent.
import sys

if len(sys.argv) == 1:
   print "y"
elif len(sys.argv[1]) == 1:
   print sys.argv[1][-1:]
else:
   l = len(sys.argv[1])

   if sys.argv[1][l - 2:l - 1] == sys.argv[1][-1:]:
      print sys.argv[1][-1:]
   else:
      if sys.argv[1][-1:] == "y":
         print "n"
      else:
         print "y"

I would leave a comment, but the 50 rep requirement prevents me.
Was able to get a small improvement on @histocrat's answer
Compressor (Ruby), score 1504/1656 ≈ 90.82%
require 'zlib'
input = $*[0].to_s.chomp
recent_input = input[-35..-1] || input
puts recent_input.chars.uniq.min_by { |char| [Zlib::Deflate.deflate(input+char,9).size,-input[-3..-1].to_s.count(char),-input.count(char)] } || ?y

I tweaked it in a number of different ways, and a +0.12% improvement was the best I found.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Know a sequence by its subsequences
Introduction
Suppose you and your friend are playing a game.
Your friend thinks of some particular sequence of n bits, and your task is to deduce the sequence by asking them questions.
However, the only type of question you're allowed to ask is "How long is the longest common subsequence of your sequence and S", where S is any sequence of bits.
The fewer questions you need, the better.
The task
Your task is to write a program or function that takes as input a positive integer n, and a binary sequence R of length n.
The sequence may be an array of integers, a string, or some other reasonable type of your choice.
Your program shall output the sequence R.
Your program is not allowed to access the sequence R directly.
The only thing it's allowed to do to R is to give it as input to the function len_lcs along with another binary sequence S.
The function len_lcs(R, S) returns the length of the longest common subsequence of R and S.
This means the longest sequence of bits which occurs as a (not necessarily contiguous) subsequence in both R and S.
The inputs of len_lcs which may be of different lengths.
The program should call this function on R and other sequences some number of times, and then reconstruct the sequence R based on that information.
Example
Consider the inputs n = 4 and R = "1010".
First, we might evaluate len_lcs(R, "110"), which gives 3, since "110" is the longest common subsequence of "1010" and "110".
Then we know that R is obtained from "110" by inserting one bit at some position.
Next, we might try len_lcs(R, "0110"), which returns 3 since the longest common subsequences are "110" and "010", so "0110" is not correct.
Then we try len_lcs(R, "1010"), which returns 4.
Now we know that R == "1010", so we can return that sequence as the correct output.
This required 3 calls to len_lcs.
Rules and scoring
In this repository, you'll find a file called subsequence_data.txt containing 100 random binary sequences of lengths between 75 and 124.
They were generated by taking three random floats between 0 and 1, taking their average as a, and then flipping an a-biased coin n times.
You score is the average number of calls to len_lcs on these sequences, lower score being better.
Your submission should record the number of calls.
There are no time limits, except that you should run your program on the file before submitting it.
Your submission shall be deterministic.
PRNGs are permitted, but they must use today's date, 200116 (or closest equivalent), as the random seed.
You are not allowed to optimize your submission against these particular test cases.
If I suspect this is happening, I will generate a new batch.
This is not code golf, so you're encouraged to write readable code.
Rosetta Code has a page on the longest common subsequence; you may use that to implement len_lcs in your language of choice.

Cool idea! Does this have any applications?

@flawr I don't know of any direct applications. The idea came from query complexity theory, a subfield of computer science, and that has loads of applications.

I think it would be great to have the same challenge again but where you can access lcs instead of len_lcs.

@flawr That wouldn't be very interesting, since lcs(R, "01"*2*n) returns R. ;) But that could work if calling lcs(R, S) would increase the score by len(S) instead of 1, or something like that...

Oh right, you'd really need another restriction=)

I'd love to see other answers =S

Java, 99.04 98.46 97.66 lcs() calls
How it works
Exaple: Our line that is to be reconstructed is 00101.
First we find out how many zeros there are, by comparing (here comparing = computing lcs with the original string) by a zeros only string 00000. Then we go through each position, flip the 0 to a 1 and check if we now have a longer common substring. If yes, accept and go to next position, if no, flip the current 1 back to a 0 and go to next position:
For our example of "00101" we get following steps:
input  lcs  prev.'best'
00000  3    0           //number of zeros
̲10000  3    3           //reject
0̲1000  3    3           //reject
00̲100  4    3           //accept
001̲10  4    4           //reject
0010̲1  5    4           //accept

Optimizations
This is just a "naive" implementation, perhaps it would be possible to find a more sophisticated alogrithm checking multiple positions at once. But I am not sure if there really is a better one (e.g. based on the calculation of parity bits similar to the Hamming code), as you can always just evaluate the length of the common substring.
For one given line of digits, this algorithm needs exactly #ofDigitsUntilTheLastOccurenceOf1 + 1 checks. (Substract one if the last digits is an 1.)
EDIT: One small optimization: If we just checked the 2nd last digit and we still need to insert a 1, we know for sure that it must be in the very last position, and can omit the corresponding check.
EDIT2: I just noticed you can apply above idea to the last k ones.
It might of course be possible to achieve a slightly lower score with the this optimization, by reordering the all lines first, because it could be, that you get more lines with ones at the very end but that would obviously be and optimization for the current test cases which is no longer funny.
Runtime
The upper limit is O(#NumberOfBits).
Full code
Here the full code:
package jcodegolf;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

// http://codegolf.stackexchange.com/questions/69799/know-a-sequence-by-its-subsequences

public class SequenceReconstructor {
    public static int counter = 0;
    public static int lcs(String a, String b) { //stolen from http://rosettacode.org/wiki/Longest_common_subsequence#Java
        int[][] lengths = new int[a.length()+1][b.length()+1];

        // row 0 and column 0 are initialized to 0 already

        for (int i = 0; i < a.length(); i++)
            for (int j = 0; j < b.length(); j++)
                if (a.charAt(i) == b.charAt(j))
                    lengths[i+1][j+1] = lengths[i][j] + 1;
                else
                    lengths[i+1][j+1] =
                        Math.max(lengths[i+1][j], lengths[i][j+1]);

        // read the substring out from the matrix
        StringBuffer sb = new StringBuffer();
        for (int x = a.length(), y = b.length();
             x != 0 && y != 0; ) {
            if (lengths[x][y] == lengths[x-1][y])
                x--;
            else if (lengths[x][y] == lengths[x][y-1])
                y--;
            else {
                assert a.charAt(x-1) == b.charAt(y-1);
                sb.append(a.charAt(x-1));
                x--;
                y--;
            }
        }

        counter ++;
        return sb.reverse().toString().length();
    }

    public static String reconstruct(String secretLine, int lineLength){
        int current_lcs = 0;
        int previous_lcs = 0;
        char [] myGuess = new char[lineLength];
        for (int k=0; k<lineLength; k++){
            myGuess[k] = '0';
        }

        //find the number of zeros:
        int numberOfZeros = lcs(secretLine, String.valueOf(myGuess));
        current_lcs = numberOfZeros;
        previous_lcs = numberOfZeros;

        if(current_lcs == lineLength){ //were done
            return String.valueOf(myGuess);
        }

        int numberOfOnes = lineLength - numberOfZeros;
        //try to greedily insert ones at the positions where they maximize the common substring length
        int onesCounter = 0;
        for(int n=0; n < lineLength && onesCounter < numberOfOnes; n++){

            myGuess[n] = '1';
            current_lcs = lcs(secretLine, String.valueOf(myGuess));

            if(current_lcs > previous_lcs){ //accept

                previous_lcs = current_lcs;
                onesCounter ++;

            } else { // do not accept
                myGuess[n]='0';
            }

            if(n == lineLength-(numberOfOnes-onesCounter)-1 && onesCounter < numberOfOnes){ //lets test if we have as many locations left as we have ones to insert
                                                                // then we know that the rest are ones
                for(int k=n+1;k<lineLength;k++){
                    myGuess[k] = '1';
                }
                break;
            }

        }

        return String.valueOf(myGuess);
    }

    public static void main(String[] args) {
        try {

            //read the file
            BufferedReader br;

            br = new BufferedReader(new FileReader("PATH/TO/YOUR/FILE/LOCATION/subsequence_data.txt"));

            String line;

            //iterate over each line
            while ( (line = br.readLine()) != null){

                String r = reconstruct(line, line.length());
                System.out.println(line);     //print original line
                System.out.println(r);        //print current line
                System.out.println(counter/100.0);  //print current number of calls
                if (! line.equals(r)){
                    System.out.println("SOMETHING WENT HORRIBLY WRONG!!!");
                    System.exit(1);
                }

            }

        } catch(Exception e){
            e.printStackTrace();;
        }

    }

}

Since you get fewer calls when there are trailing 1s, it seems like you could do better on average if, after the first guess tells you there are more 0s than 1s you switch to hunting for 0 positions rather than 1 positions. You could even do that multiple times.

@histocrat I think he's already stopping once he uses up the last 1, which is equivalent to there being only zeroes left.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Apples are falling down
Introduction
There is an Apple tree trunk positioned between -2 to 2 on the x-axis, where some apples fall down around it:
        |   |
        |   |
<-------|---|------->
       -2   2

Everyday, n apples fall down. Each apple maintains its x coordinate as falls straight to the ground.
But if it lands on top of another apple, it will roll according to the following rules until it reaches the ground or a supporting layer of apples:

If the space at x+1 at its current height is empty the current apple goes there.
Else if the space at x-1 is empty the current apple goes there.
Otherwise the current apple stays where it is on top of that other apple.

Challenge
The input will be the n starting positions of each apple in order. You can take it as an array or as separated numbers or in any other valid way, just make sure you explain it in your answer.
The output should be an ASCII drawing of the tree trunk and the apples around. You are not required to draw the x-axis to the left of the leftmost apple and to the right of the rightmost apple, but you do need to draw it anywhere it is beneath some apple. You can also extend the tree above the highest apple.
You can assume all x-coordinates are between -100 and 100, but not between -2 and 2.
This is code-golf .. The shortest answer in bytes wins!
Examples
Input: [-3, 5, 5, -4, -4, 5, -3]
Output:
  a|   |
aaa|   | aaa
---|---|----

Input: [3, 3, 3, 3, 8, 9]
Output:
|   |a
|   |aaa  aa
|---|-------

Input: [-5, -5, -5, -5, -5, -5, -5, -5, -5]
Output:
  a  |   |
 aaa |   |
aaaaa|   |
-----|---|

Fond memories. :)

Your examples imply that the minimal possible extent in the x direction should be shown (no empty ground to the left and right of the trees and apples). Is that a requirement? Also, are we allowed to print trailing spaces, at least to pad the output to a rectangle?

Bonuses aren't very popular. I think requiring the "visible" output to be minimal (no empty rows at the top, no ground cells at the edges which are empty) is fine, but I would definitely allow padding the output to a rectangle with spaces.

Also, your bonus currently doesn't make sense because the spec doesn't actually allow any different output format to begin with.

I will give a 100 rep bounty to the first answer in Marbelous. Falling apples  computed by falling marbles...it's just too fitting.

PHP, 230 bytes
I've added the first two newlines for readibility.
function($l){for($y=count($l);$y>=0;$f[]="$a|   |$a")$a=str_repeat($y--?$w=' ':'-',99);
foreach($l as$x){for($x+=101,$s=$y=0;!$s;$b[$x]!=$w?$b[$x+1]!=$w?$b[$x-1]!=$w?$s=1:--$x
:++$x:0)$b=$f[$y++];$f[$y-2][$x]=a;}echo join('
',$f);};

Ideone
Here is the ungolfed version:
function drawApples(array $listStartX)
{
    $field = [];
    $maximalHeight = count($listStartX);
    for ($y = $maximalHeight; $y >= 0; --$y)
    {
        $line = str_repeat($y > 0 ? ' ' : '-', 98);
        $field[] = $line .'|   |'. $line;
    }

    foreach ($listStartX as $x)
    {
        $x += 100;
        for ($y = 0; true; ++$y)
        {
            if ($field[$y][$x] === ' ') {
                continue;
            }

            if ($field[$y][$x + 1] === ' ') {
                ++$x;
                continue;
            }

            if ($field[$y][$x - 1] === ' ') {
                --$x;
                continue;
            }

            $field[$y - 1][$x] = 'a';
            break;
        }
    }

    echo implode("\n", $field);
}

Python 2.7, 282 bytes
from collections import*;a=Counter();a[2]=-1;a[-2]=-1
for d in input():
 while 0<=a[d+1]<a[d]:d+=1
 while 0<=a[d-1]<a[d]:d-=1
 a[d]+=1
m=max(a.values())+1
print'\n'.join(''.join(' '*(m-a[i]-1)+'a'*a[i]+'-'if i**2!=4 else'|'*m for i in range(min(a),max(a)+1))[i::m]for i in range(m))

Ideone
Well… I tried.


text:
A Geometrical Challenge
Everybody loves geometry.  So why don't we try and code golf it?  This challenge involves taking in letters and numbers and making shapes depending on it.
The Input
The input will be in the form of (shapeIdentifier)(size)(inverter).
But what are shapeIdentifier, size, and inverter?
The shape identifier is the identifier for the type of shape you will be making with *s.  The following are the shape identifiers:

s - Square
t - Triangle

The size will be between 1-20, and it is the size of the figure.
The inverter is whether or not the shape will be upside down, which is denoted by a + or a -.  Do note:  s3- == (equals) s3+ because squares are symmetric.  However, t5- != (does not equal) t5+.
Trailing whitespace is okay in the output but leading whitespace is not.
Output Examples
Input: s3+
Output:
***
***
***

Input: t5+

Output:
  *
 ***
*****

Input: t3-
Output:
***
 *

Special Notes
The triangle input will always be an odd number, so the triangles will always end with 1 * at the top.

The size of the triangle is the size of the base if the inverter is
+ and is the size of the top if the inverter is -.

As someone who is taking Geometry right now, (and studying for a Geometry final), I can say with 100% certainty: Geometry is absolutely, not fun at all... D:

Pyth, 40 36 34 32 bytes
-1 byte by @isaacg
JstPz_W}\+zjl#m.[J*\*-J*}\tzyd;J

A semicolon inside a lambda is now the lambda variable's global value, a feature that saves one byte.
                         Implicit: z = input
JstPz                    J = size.
_W }\+z                  Reverse if "+" in z
j l# m                J  Join the nonempty lines in map lambda d:... over range(J)
      .[J            ;   Pad the following with spaces (;) to length J
         *\*               "*", this many times:
            -J*}\tzyd        J if "t" not  in z,
                             otherwise the correct number for a triangle.

Try it here.
Test suite.

Way too long, yet beating Japt by 15 bytes? I can't wait to see how this will be golfed :)

Nice solution! You can save a byte by replacing qez\+ with }\+z, because + can only appear in the last position.

Pyth, 38 bytes
JsPtzj?}\szm*\*JJ_W}\-zm.[J*\*hyd;/hJ2

Test suite
Basically as straightforward as it gets. I wish I could combine some of the logic for the two shapes, but currently it's separate.

Python 2, 106 bytes
s=raw_input()
n=int(s[1:-1])
for i in[range(1,n+1,2),n*[n]][s<'t'][::2*('+'in s)-1]:print('*'*i).center(n)

The output is a perfect rectangle, with each line padded with trailing spaces, which I'm assuming is okay based on the comments in the OP.
Note: I'm still never sure whether input is allowed in Python 2 for problems like these...

JavaScript (ES6), 142 146 147
Edit 1 byte saved thx @ETHproductions
Edit 2 bytes sve thx @user81655
i=>([,a,b]=i.match`.(.+)(.)`,Array(l=i<'t'?+a:-~a/2).fill('*'.repeat(a)).map((r,i)=>l-a?(' '.repeat(i=b<'-'?--l:i)+r).slice(0,a-i):r).join`
`)

Test (run in FireFox)

F=i=>(
  [,a,b]=i.match`.(.+)(.)`,
  Array(l=i<'t'?+a:-~a/2).fill('*'.repeat(a))
  .map((r,i)=>l-a?(' '.repeat(i=b<'-'?--l:i)+r).slice(0,a-i):r)
  .join`\n`
)

function test() { O.textContent=F(I.value) }

test()
Input: <input id=I oninput="test()" value="t11-"/>

\d -> ., since there's guaranteed to be exactly one non-digit before and after

@ETHproductions right, thanks

Nice. I think this is the optimal algorithm in JS, can't find a shorter one.

i.match(/.(.+)(.)/) -> i.match\.(.+)(.)``

@user81655 nice hint, thanks

Japt, 62 60 55 52 51 bytes
V=Us1 n;U<'t?Vo ç*pV):0oV2 £S²pY iY'*pV-X})·z2*!Uf-

Try it online!
The first thing we need to do is figure out how big our shape needs to be. This is pretty simple:
      // Implicit: U = input string, S = space
V=    // Set variable V to
Us1   // everything after the first char of U,
n;    // converted to a number. This turns e.g. "12+" into 12.

Now we organize the shape of the output:
U<'t?      // If U comes before "t" lexicographically (here, if the first char is "s"),
Vo         //  make a list of V items,
ç*pV)      //  and set each item to V asterisks.
:0oV2      // Otherwise, create the range [0, V) with steps of 2 (e.g. 7 -> [0,2,4,6]),
£       }) //  and map each item X and index Y to:
S²pY       //   Repeat 2 spaces Y times. This creates a string of Y*2 spaces.
iY'*pV-X   //   At position Y in this string (right in the middle), insert V-X asterisks.
·          // Join with newlines.

By now, we have taken care of the size and shape of the output. All that's left is the rotation. Triangles are currently pointed up, so we need to flip them if the third char is +:
!Uf-    // Take the logical not of U.match("-").
        // If U contains "-", this returns false; otherwise, returns true.
2*      // Multiply by two. This converts true to 2, false to 0.
z       // Rotate the list 90° that many times.
        // Altogether, this turns the shape by 180° if necessary.

And with implicit output, our work here is done. :-)

Python 2, 235 193 167 157 Bytes
Update:
Made some significant optimizing by using list comprehensions and str.center(). I have the feeling I can do some more tho, gonna hava a fresh look at it later.
Update 2
Saved 10 Bytes with the suggestions of Sherlock9. Thanks a lot! :)
d=raw_input()
x=int(d[1:-1])
o="\n".join("*"*x for i in range(x))if d<"t"else"\n".join(("*"*i).center(x)for i in range(x,0,-2))
print o[::-1]if"+"in d else o

Old answer
d=raw_input()
x=int(d[1:-1])
if "s" in d:
 for y in range(x):
    o+="*"*x+"\n"
 o=o[:-1]
else:
 b=0
 while x+1:
    o+=" "*b+"*"*x+" "*b+"\n"
    x-=2
    b+=1
 o=o[:-1]
 if d[-1]=="+":
    o=o[::-1]
print o

Pretty straighforward approach. Writing line per line in a string which I output in the end. Triangles are always drawn inverted and get reversed if needed. The fact that you can multiply a string with an Integer saved me a lot of bytes!
I will try to golf that down a bit more later, would appreciate suggestions in the meantime, since I am not that much exprienced with it yet.
edit: Golfed it down a lot with the help in the comments and stealing the size-calculation from one of the other python-answers. I think thats the most I can do with this algorithm.

How did you count? When using wc this gives me a byte count of 235. Am I wrong?

This is indeed 235 bytes. Golfing advice: Use tabs instead of two spaces, which is valid in Python 2 and will shave off 5 bytes.

Also you don't need to use raw_input, using input saves you 4 bytes. Further you don't need the brackets in the second line, this and not using the variable x at all (using if"s"in d) saves you another 9 bytes.

x being an odd number, you could replace while x>=1: by while x+1: saving one byte and adding an infinite loop for users abusing your program :)

Could x>=1 be x>0?

@ETHproductions Yes in fact, that would still be correct.

Thanks for the great suggestions! I like the x+1 thing a lot :) I have to use raw_input() tho, because input() evaluates the input which fails because there are numbers in there.
On the Byte-Count: On Windows I keep getting 251. Used notepad++ and wc to test it. Am I missing something?

@DenkerAffe when counting in window, subtract 1 byte for each newline  - newlines are 2 bytes in windows, but 1 byte in other environments

First, you can remove the [] brackets in each of the join function calls. Second, if d<"t"else is shorter and works because "s3+"<"t"<"t3+" in Python. Third, else"\n".join and .center(x)for. No space. It isn't required. Fourth, print o[::-1]if"+"in d else o where I rearranged things for two bytes (one space between ] and if and another between if and  "+".

Last line: print o[::2*('+'in d)-1]

JavaScript, 220 bytes.
q=s=>+s.slice(1,s.length-1);f=s=>s[0]=="s"?("*".repeat(q(s))+"\n").repeat(q(s)):Array.apply(0,Array(-~(q(s)/2))).map((_,n)=>(s[s.length-1]=="-"?~~(q(s)/2)-n:n)).map(n=>(" ".repeat(q(s)/2-n)+"*".repeat(n*2+1))).join("\n")

Run with f(input here)
Try it here!
The squares has trailing newlines, but the triangles don't. Explanation:
q=s=>+s.slice(1,s.length-1);                                                                                Define a function, q, that takes returns the argument, without the first and last character, casted into an integer.
                            f=s=>                                                                                Define a function, f, that takes one argument, s. (This is the main function)
                                 s[0]=="s"?                                                                                If the first character of s is "s" then...
                                           ("*".repeat(q(s))     )                                                                                Repeat the "*" character q(s) times.
                                           (                +"\n")                                                                                Append a newline to that
                                                                  .repeat(q(s))                                                                                Repeat that q(s) times.
                                                                               :                                                                                Else... (the first character of s isn't "s")
                                                                                Array.apply(0,Array(          ))                                                                                Create an array of length...
                                                                                Array.apply(0,Array(-~(q(s)/2)))                                                                                floor(q(s)/2)+1
                                                                                .map((_,n)=>                                   )                                                             Map each element, _ with index n to...
                                                                                .map((_,n)=>(s[s.length-1]=="-"?              ))                                                             If the last element of s is "-" then...
                                                                                .map((_,n)=>(s[s.length-1]=="-"?~~(q(s)/2)-n  ))                                                             floor(q(s)/2)-n
                                                                                .map((_,n)=>(s[s.length-1]=="-"?            : ))                                                             Else...
                                                                                .map((_,n)=>(s[s.length-1]=="-"?             n))                                                             Just n
                                                                                .map(n=>                                        )            Map each element into...
                                                                                .map(n=>(" ".repeat(q(s)/2-n)                   )            Repeat " ", q(s)/2-n times.
                                                                                .map(n=>(                   )+"*".repeat(n*2+1)))            Append "*", repeated 2n+1 times.
                                                                                .map(n=>(" ".repeat(        )+"*".repeat(n*2+1))).join("\n") Join with newlines

The length of your first line is 338 characters. It takes me one monitor and a half to display.

@isanae It says 220 here.

I won't click on a random tinyurl link, but check again. In any case, try avoiding scroll bars in code boxes, it makes it much harder to read.

@Loovjo I think he means the first line of the explanation. I usually indent my explanation rather than this style for JavaScript answers so you don't need to scroll to see half of it.

@user81655 Yes, I meant in the explanation. Now I understand the confusion!

Python 2, 157 132 bytes
def f(s):
 S=int(s[1:-1])
 for n in([range(1,S+2,2),range(S,0,-2)]['-'in s],[S]*S)['s'in s]:
  print "{:^{S}}".format('*'*n,S=S)

First attempt firgured that the +/- on the end was optional, getting rid of that let me shave off a bunch
The idea here is to make a list which can get thrown into a generic output.  Hardest part was separating out the length from the input.

For getting the length I used x=int(d[1]if len(d)<4 else d[1:3]) with d being the input string. Thats 5 Bytes shorter than your solution. You are still way ahead of my python-answer tho, gotta try to understand what you did there and beat you next time! :)

Actually x=int(d[1:-1])is a lot shorter for that, just saw it in the other python answer.

@DenkerAffe, for whatever reason I remember the inverter being optional, so that wouldn't work, but I guess I just made that up

MATL, 48 bytes
' *'jt4Y2m)U1$l't'Gm?2MQ2/:1L3$)R!P!R'+'Gm?P]]Q)

Uses current version (10.1.0) of the language/compiler.
The code accepts input characters in any order: all s11+, 11s+ and even 1+s1 would be valid input strings.
EDIT (July 30, 2016): the linked code replaces 1L3$) by Y) to conform to recent changes in the language
Try it online!
Explanation
' *'        % push string. Will be indexed into to obtain final result
j           % input string
t           % duplicate
4Y2         % predefined literal string '0123456789'
m           % logical index of digits in input string
)           % index into input string to obtain substring with digits
U           % convert to number
1$l         % generate square of ones with that size
't'         % push character 't'
G           % push input string
m           % true if input string contains 't'
?           % if so...
  2M        % push argument of call to function `l`, i.e. square size
  Q2/       % add 1 and divide by 2. Call result T
  :         % generate vector [1, 2, ... T]
  1L        % predefined literal representing Matlab's `:` index
  3$)       % two dimensional index. Transforms square into rectangle
  R         % remove (set to zero) lower-left corner
  !P!       % flip horizontally
  R         % remove lower-left corner. This gives inverted triangle
  '+'       % push character '+'
  G         % push input
  m         % true if input contains '+'
  ?         % if so...
    P       % flip vertically
  ]         % end if
]           % end if
Q           % add 1. This gives array of values 1 and 2
)           % index string ' *' with this array to produce char array
            % implicitly display that char array

ES6, 178 172 159 bytes
s=>(p=s.match(/d+|./g),u=n=+p[1],m=n+1>>1,t=' '.repeat(n)+'*'.repeat(n),v=s<'t'?0:p[2]<'-'?(u=m,1):-1,[...Array(s<'t'?n:m)].map(_=>t.substr(u,u,u+=v)).join`
`)

This works due to an interesting observation I made. If you repeat n spaces and n asterisks you get (e.g. for n=5) this:
     *****

Now, take substrings with the same start and length:
     |*****| (5)
    | ***| (4)
   |  *| (3)

These substrings are exactly the strings we need for t5.
Edit: Saved 6 bytes thanks to @edc65.
Edit: Saved 13 bytes thanks to hiding the u+=v in the third argument of substr thus allowing me to simplify the initialisation.

@ThomasKwa Huh, after I'd fixed the t handling code it turned out that w and u became equivalent and that saved me enough bytes to take me back down to 178!

[,b,c]=s.match and later s<'t'... should save some bytes (Firefox only)

@edc65 Just not saving the match in s allows me to use s<'t' which saved me 6 bytes, thanks.

Retina, 102 85 bytes
Byte count assumes that the source code is encoded as ISO 8859-1.
\d+
$0$*:¶
^((\w)+):(:+)
$1$2$3$2¶$0
m`s$|:t

)`(.+)¶-(\D*)
-$2¶$1
m`^.

G`.
T`ts:` *

Try it online.
I'll try to golf this some more later.

Notepad++ says that your code is 89 bytes, not 85. I've used the ISO-8859-1 encoding, and went on Edit > EOL Convertion > UNIX/Linux Format, to use \n instead of \r\n. Base64 of the content: XGQrCiQwJCo6wrYKXigoXHcpKyk6KDorKQokMSQyJDMkMsK2JDAKbWBzJHw6dAoKKWAoLispwrYtKFxEKikKLSQywrYkMQptYF4uCgpHYC4KVGB0czpgICo= (direct copy from Notepad++). Weirdly enough, any online solution gives me 85 bytes... Hum...

@IsmaelMiguel There's gotta be something off with how Notepad++ counts the ¶. They are definitely a single byte in ISO 8859-1 (with value 182).

Seriously, 54 bytes
,#i's=`≈;'**@½≈";#dXdXεj' +"£n`@`≈;'**n`@Iƒ('-=WXa0WXü

Try It Online
,#i                                                    Take input, push chars separately
   's=                                   Iƒ            IF the first char is "s":
                                `      `@                run the quoted function
                                 ≈;'**n                  make list of n strings of n *'s
      `                       `@                       ELSE run the quoted function:
       ≈;                                                make two copies of int n
         '**                                             use one to make string of n *'s
            @½≈                                          cut the other in half (e.g. 5->2)
               "           "£n                           run n/2 times the quoted function:
                ;#                                        copy the string as list of chars
                  dXdX                                    discard the last 2 *'s
                      εj                                  join back into string
                        ' +                               prepend a space
                                           ('-=WX 0WX  IF the third character is "-":
                                                 a       invert the stack
                                                     ü pop and print the entire stack

@Mego: See that #dXdXεj? STRING SLICING????

Jolf, 37 bytes, noncompeting
I added functions after this challenge was posted, so this cannot be considered for acceptation. This is encoded in ISO-8859-7. Try all test cases here.
onFiΒ€ioSgiγ?='sn―sΒ'*―TΒ1'*?='-SZiγγ

Part 1: parsing the string
onFiΒ€ioSgi
on          set n to
  Fi         the first entity of i (the shape identifier)
    Β       set Β (beta) to
     €i      the "inside" of i (in this case, the size) as a number
       oS   set S to
         gi  the last entity of i (the inverter)

Part 2: obtaining the result
γ?='sn―sΒ'*―TΒ1'*
γ                 set γ (gamma) to the result of the following expression
 ?='sn             if n is the character s,
      ―sΒ'*         then return a pattern "s" (a square) made with "*"s
           ―TΒ1'*    otherwise, return a pattern "T" (triangle) that is centered and
                     has a scale factor of 1, made with "*"s

Part 3: inverting the result
?='-SZiγγ
?='-S     if S is a "-"
     Ziγ   return γ, inverted across its lines
        γ  otherwise, return γ untouched

Ruby, 99
->s{n=s[1,2].to_i
n.times{|i|d=(s.ord-115)*(s[-1]<=>?,)*(n-1-i*2)
d<1&&puts((?**(n+d)).center(n))}}

Calculates a square or triangle of height n and average width n by verying the slope of the sides (so the calculated triangle width is 2n-1 at the base, 1 at the tip.) But it only prints those rows which do not exceed n characters.
ungolfed in test program
f=->s{                         #take a string as an argument
  n=s[1,2].to_i                #take 2 characters starting at index 1 and convert to a number for the size
  n.times{|i|                  #iterate through n rows
    d=                         #calculate how many stars "MORE THAN" n we need on a row
    (s.ord-115)*               #ascii code for 1st character of string - 115 : s-->0, t-->1
    (s[-1]<=>?,)*              #compare last character of input with comma character - --> +1 + --> -1
    (n-1-i*2)                  #row number * 2: 0 at centre, positive above it, negative below it
    d<1&&                      #only output if d is nonpositive (i.e we need less than n or exactly n stars)
    puts((?**(n+d)).center(n)) #print n+d stars, centred in a field of n characters padded by whitespace
  }
}

f[gets.chomp]

C, 259 bytes
#define x(y);)putchar(y)
#define m(n)for(n=0;n++<
#define T {m(q)i x(32);m(q)s-i*2 x(42);puts("");}
main(q,v,i,s)char**v;{s=atoi(v[1]+1);if(*v[1]=='s')m(i)s*s x(42)&&!(i%s)&&puts("");else if(strchr(v[1],'+'))for(i=s/2+1;i-->0;)T else for(i=-1;i++<s/2+1;)T}

ungolfed
main(q,v,i,size)char**v; // neat way of declaring variables
{
    size=atoi(v[1]+1);
    if(*v[1]=='s')
    {
        for(i=0;i++<size*size;)
        {
            putchar(42); // returns 42 (true)
            if(!(i%size))
                puts("");
        }
    }
    else if(strchr(v[1],'+')) // if finds plus sign
    {
        for(i=size/2+1;i-->0;) // iterate the height of the triangle
        {
            for(q=0;q++<i;)putchar(32); // conveniently i is the number os spaces before each line
            for(q=0;q++<size-i*2;) putchar(42);
            puts("");
        }
    }
    else for(i=-1;i++<size/2+1;) // does the same as above but inverted order
    {
        for(q=0;q++<i;)putchar(32);
        for(q=0;q++<size-i*2;)putchar(42);
        puts("");
    }
}

Suggestions and critique are very welcome.

Vyxal, 22 bytes
[⁰(×⁰*,)|¹ƛ×*¹↳øm;⁰ßṘ⁋

Try it Online!
[                      # If truthy (square) then...
 ⁰(    )               # (size) times
   ×⁰*,                # Print (size) asterisks
        |              # Else...
         ¹ƛ      ;     # Map input to...
           ×*          # That many asterisks
             ¹↳        # Right-justified to triangulate
               øm      # Palindromise
                  ⁰ßṘ  # If (input), reverse
                     ⁋ # Join by newlines

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Implement a URL shortener
URLs are getting too long. So, you must implement an algorithm to shorten a URL.
i. The Structure of a URL
A URL has 2 main parts: a domain and a path. A domain is the part of the URL before the first slash. You may assume that the URL does not include a protocol. The path is everything else.
ii. The Domain
The domain of a URL will be something like: xkcd.com meta.codegolf.stackexcchhannnge.cooom.  Each part is period-seperated, e.g. in blag.xkcd.com, the parts are "blag", "xkcd", and "com". This is what you will do with it:

If it contains more than two parts, put the last two aside and concatenate the first letter of the rest of the parts.
Then, concatenate that to the first letter to the second-to-last part.
Add a period and the second and third letter of the second-to-last part.
Discard the last part.

iii. The Path
The path will be like: /questions/2140/ /1407/. As before, "parts" are seperated by slashes.  For each part in the path, do:

Add a slash
If it is completely made of base-ten digits, interpret it as a number and convert to a base-36 integer.
Otherwise, add the first letter of the part.

At the end, add a slash.
iv. Misc.

This is code-golf, so shortest code wins.
The path can be empty, but the URL will always end with a slash.
There will not be a protocol (e.g. http://, file:///)
There will never be less than two parts in the domain.
Standard loopholes apply.

Examples
In: xkcd.com/72/
Out: x.kc/20/
In: math.stackexchange.com/a/2231/
Out: ms.ta/a/1pz/
In: hello.org/somecoolcodeintrepreteriijjkk?code=3g3fzsdg32,g2/
Out: h.el/s/

In your last example, doesn't the path end at kk and everything starting with ? is a query string, which shouldn't end with a slash? Also not all URLs will end with a slash /, like www.something.com/path. Or is this irrelevant for the purpose of this challenge?

That is irrelevant.

Pyth, 93 85 bytes
Lsm@+jkUTGdjb36J<zxz\/KP>zhxz\/=cJ\.pss[mhd<J_2hePJ\.<tePJ2\/;=cK\/sm+?-djkUThdysd\/K

Hand-compiled to pythonic pseudocode:
                z = input()                     # raw, unevaluated
                G = "abcdefghijklmnopqrstuvwxyz"
                k = ""
                T = 10
L               def y(b):                       # define y as base10to36
 sm                 join(map(lambda d:
  @+jkUTGd            (join(range(T),interleave=k)+G)[d],
                                                # the join(..)+G makes "0...9a...z"
  jb36                 convert(b,36)            # returns a list of digit values in base10
J<zxz\/         J = z[:z.index("\/")]           # domain portion
KP>zhxz\/       K = z[1+z.index("\/"):][:-1]    # path portion
=cJ\.           J = J.split(".")                # splits domain into parts
pss[            no_newline_print(join(join[     # 1 join yields a list, the other a string
 mhd<J_2            map(lambda d:d[0],J[:-2]),
 hePJ               J[:-1][-1][1],
 \.                 ".",
 <tePJ2             J[:-1][-1][1:][:2],
 \/                 "\/"
;               ])
=cK\/           K = K.split("\/")
sm              print(join(map(lambda d:
 +?-djkUThdysd\/    "\/"+(d[0] if filterOut(d,join(range(T),interleave=k)) else y(int(d))),
                    # the filter will turn pure number into empty string, which is False
 K                  K)))

Finally, the excruciation ends...

JavaScript (ES6), 149 bytes
u=>u.split`/`.map((p,i)=>i?/^\d+$/.test(p)?(+p).toString(36):p[0]:(d=p.split`.`).slice(0,-1).map((s,j)=>s[l=j,0]).join``+"."+d[l].slice(1,3)).join`/`

Explanation
I made this independent of @Neil's solution but it ended up looking very similar.
u=>
  u.split`/`.map((p,i)=>       // for each part p at index i
    i?                         // if this is not the first part
      /^\d+$/.test(p)?         // if p is only digits
        (+p).toString(36)      // return p as a base-36 number
      :p[0]                    // else return the first letter
    :
      (d=p.split`.`)           // d = domain parts
      .slice(0,-1).map((s,j)=> // for each domain part before the last
        s[l=j,0]               // return the first letter, l = index of last domain part
      ).join``
      +"."+d[l].slice(1,3)     // add the 2 letters as the final domain
  )
  .join`/`                     // output each new part separated by a slash

Test

var solution = u=>u.split`/`.map((p,i)=>i?/^\d+$/.test(p)?(+p).toString(36):p[0]:(d=p.split`.`).slice(0,-1).map((s,j)=>s[l=j,0]).join``+"."+d[l].slice(1,3)).join`/`
<input type="text" id="input" value="math.stackexchange.com/a/2231/" />
<button onclick="result.textContent=solution(input.value)">Go</button>

JavaScript ES6, 157 bytes
u=>u.split`/`.map((p,i)=>i?/^\d+$/.test(p)?(+p).toString(36):p[0]:p.split`.`.reverse().map((h,i)=>i--?i?h[0]:h[0]+'.'+h[1]+h[2]:'').reverse().join``).join`/`

Edit: Saved 4 bytes thanks to Doᴡɴɢᴏᴀᴛ.

You should be able to make .split('/') and .split('.') into string templates

@Doᴡɴɢᴏᴀᴛ Bah, I remembered on join as well!

Python 2, 378 365 Bytes
Update
Golfed it down by a bit. The ~150 Bytes for the base36-function are annoying, but I can't get rid of it until python has a builtin for that...
def b(n):
 a=abs(n);r=[];
 while a :
    r.append('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[a%36]);a//=36
 if n<0:r.append('-')
 return''.join(reversed(r or'0'))
u=raw_input();P=u.split("/")[0].split(".")
print"".join([p[0] for p in P[0:-2]]+[P[-2][0]]+["."]+list(P[-2])[1:3]+["/"]+[b(int(p))+"/"if p.isdigit()else p[0]+"/" for p in u.split(".")[-1].split("/")[1:-1]])

Old version
def b(n):
 a=abs(n)
 r=[]
 while a:
    r.append('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[a%36])
    a//=36
 if n<0:r.append('-')
 return''.join(reversed(r or'0'))
u=raw_input()
P=u.split("/")[0].split(".")
s=""
if len(P)>2:
 for p in P[:-2]:s+=p[0]
s+=P[-2][0]+"."+P[0][1:3]
P=u.split(".")[-1].split("/")[1:-1]
for p in P:
 s+="/"+(b(int(p)) if p.isdigit() else p[0])
print s+"/"

Since Python does not have a builtin way to convert ints to a base36-String, I took the implementation from numpy and golfed it down. Rest is pretty straightforward, I will golf it down more after work. Suggestions always appreciated in the meantime!

Pyhton 2, 336 329 bytes
update
fixed and shorter thanks to webwarrior
def b(a):
 r=''
 while a:
  r+=chr((range(48,58)+range(65,91))[a%36])
  a//=36
 return ''.join(reversed(r or '0'))
u=raw_input()
P=u.split('/')[0].split('.')
s=''
if len(P)>2:
 for p in P[:-2]: s+=p[0]
s+=P[-2][0]+'.'+P[0][1:3]
P=u.split('.')[-1].split('/')[1:]
for p in P: s+='/'+(b(int(p)) if p.isdigit() else p[0])
print s+'/'

original
DenkerAffe's version with some mods : correctly handle "foo/bar?baz" scheme, plus, no need for negative case in the base36 conversion function.
 def b(a):
 r=''
 while a:
  r+=('0123456789ABCDEFGHUKLMNOPQRSTUVWXYZ'[a%36])
  a//=36
 return ''.join(reversed(r or '0'))
u=raw_input()
P=u.split('/')[0].split('.')
s=''
if len(P)>2:
 for p in P[:-2]: s+=p[0]
s+=P[-2][0]+'.'+P[0][1:3]
P=u.split('.')[-1].split('/')[1:]
for p in P: s+='/'+(b(int(p)) if p.isdigit() else p[0])
print s+'/'

There's error in your lookup string, and also the whole line can be shorter: r+=chr((range(48,58)+range(65,91))[a%36])


text:
Decipher the mathematical symbols
If you've read the book Contact by Carl Sagan, this challenge may seem
familiar to you.

Given an input of a set of mathematical equations consisting of a number, an
unknown operator, another number, and a result, deduce which operators
represent addition, subtraction, multiplication, or division.
Each input equation will always consist of

a non-negative integer
one of the letters A, B, C, or D
another non-negative integer
the character =
a final non-negative integer

concatenated together. For example, a possible input is 1A2=3, from which you
can deduce that A represents addition. Each of the integers will satisfy 0 ≤ x ≤ 1,000.
However, it's not always as simple as that. It is possible for there to be
ambiguity between:

5A0=5: addition/subtraction
1A1=1: multiplication/division
0A5=0: multiplication/division
2A2=4: addition/multiplication
4A2=2: subtraction/division
0A0=0: addition/subtraction/multiplication

and so on. The challenge is to use this ability to narrow down choices,
combined with process of elimination, to figure out what operator each letter
represents. (There will always be at least one input equation, and it will
always be possible to unambiguously, uniquely match each letter used in the input with a single operator.)
For example, let's say the input is the following equations:

0A0=0: this narrows A down to addition, subtraction, or multiplication
(can't divide by 0).
10B0=10: B has to be either addition or subtraction.
5C5=10: C is obviously addition, which makes B subtraction, which makes A
multiplication.

Therefore, the output for these input equations should match A with *, B
with -, and C with +.
Input may be given as either a single whitespace-/comma-delimited string or
an array of strings, each representing one equation. Output may be either a
single string ("A*B-C+"), an array (["A*", "B-", "C+"]), or a dictionary / dict-like 2D array ({"A": "*", ...} or [["A", "*"], ...]).
You may assume that a number will never be divided by another number it isn't divisible by (so, you don't need to worry about whether division should be floating point or truncated).
Since this is code-golf, the shortest code in bytes wins.
Test cases:
In                       Out
-------------------------------
0A0=0 10B0=10 5C5=10     A*B-C+
100D100=10000            D*
4A2=2 4B2=2 0A0=0        A-B/
15A0=15 4B2=2 2C2=0      A+B/C-
1A1=1 0A0=0              A*
0A0=0 2A2=4 5B0=5 2B2=4  A*B+
2A2=4 0C0=0 5B0=5 5A0=5  A+B-C*
0A1000=0 4A2=2           A/

Are we doing (truncated) integer division?

@MartinBüttner You can assume that there will never be division by a number that doesn't result in an integer. (Edited into question.)

Can we output as a dictionary?

@ThomasKwa Sure, a dictionary is also acceptable output.

Most of the examples are inconsistent with "it will always be possible to unambiguously, uniquely identify which letter stands for which operator", although they are consistent with "it will always be possible to unambiguously identify which operator is represented by each letter used in the input".

@PeterTaylor Edited for wording.

How flexible is the output? If it's a string does it have to be in that format or can it have commas in between the pairs? Can arrays have empty elements? Can unknown letters be present in the output paired with the other (unused) operators?

@user81655 None of those are allowed. The output must conform exactly to any of the alternatives specified.

MATL, 53 bytes
j61tthYX'+-*/'X{Y@!"t'ABCD'!XKX{@YXU?K@Y}hwxKGm1L3$).

Uses current version (10.1.0)
EDIT (June 12, 2016): to adapt to changes in the language, replace Y} by g and 1L3$) by Y). The link below incorporates those modifications
Try it online!
Explanation
This tests all possible permutations of the four operators in a loop until one permutation makes all equations true.
To test if equations are true, a regex is applied to replace the four letters by the operators (in the order dictated by the current permutation), and the string is converted to numbers (evaluated). This gives an array with as many numbers as equations, in which equations that are true become 1 and equations that are false become 0. If this vector only contains 1 values, we're done.
The solution found assigns operators to the four letters, but not all of them necessarily appear in the input. So a final test is done to discard not used letters (and their matching operators).
j            % input data string
61           % '=' (ASCII)
tth          % duplicate twice and concat: '==' (ASCII)
YX           % regexprep to change '=' into '==' in input string
'+-*/'       % push string
X{           % transform into cell array {'+','-','*','/'}
Y@!          % all permutations, each in a column
"            % "for" loop. Iterate columns (that is, permutations)
  t          %   duplicate data string containing '=='
  'ABCD'!XK  %   create column array ['A';'B';'C';'D'] and copy to clipboard K
  X{         %   transform into column cell array {'A';'B';'C';'D'}
  @          %   push column cell array with current permutation of operator symbols
  YX         %   regexprep. Replaces 'A',...,'D' with current permutation of operators
  U          %   convert to numbers, i.e. evaluate string
  ?          %   if all numbers are 1 (truthy result): found it! But before breaking...
    K        %     push column array ['A';'B';'C';'D']
    @Y}      %     push column array with current permutation of operator symbols
    h        %     concatenate horizontally into 4x2 char array
    wx       %     delete original input so it won't be displayed
    K        %     push ['A';'B';'C';'D']
    G        %     push input string
    m        %     logical index that tells which of 'A',...,'D' were in input string
    1L3$)    %     apply that index to select rows of the 4x2 char array
    .        %     we can now break "for" loop
             %   implicitly end "if"
             % implicitly end "for"
             % implicitly display stack contents

Python, 278 characters
My first answer on code golf...
It is just a function implementing a brute force algorithm, you call it passing as argument the string of equations.
from itertools import *
def f(s):
    l=list("ABCD")
    for p in permutations("+-*/"):
        t=s
        for v,w in zip(l+["="," "],list(p)+["=="," and "]):
            t=t.replace(v, w)
        try:
            o=""
            if eval(t):
                for c,r in zip(l,p):
                    if c in s:
                        o+=c+r
                return o
        except:
            pass

I'm not sure if it works, but can you replace ["A","B","C","D"] with list("ABCD")?

What @Adnan suggested does indeed work. You can also remove the spaces around = in the definition of l.

@Adnan and Alex A. thanks, I edited the code.

Here's 257 bytes for the same approach, plus an online testing environment.

Made some changes - https://repl.it/BfuU. You can cut a lot of bytes more by picking a different output format. This solution only works on python 3 btw (4A2=2 4B3=1).

JavaScript (ES6), 213 208 bytes
f=(l,s="+-*/",p="",r)=>s?[...s].map(o=>r=f(l,s[g="replace"](o,""),p+o)||r)&&r:l.split` `.every(x=>(q=x.split`=`)[1]==eval(q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])))&&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")

Explanation
Input and output are strings.
Defines a function f which doubles as a recursive function for generating all the permutations of the operators and tests complete permutations with the input equations using eval.
f=(
  l,                          // l = input expression string
  s="+-*/",                   // s = remaining operators
  p="",                       // p = current permutation of operators
  r                           // r is here so it is defined locally
)=>
  s?                          // if there are remaining operators
    [...s].map(o=>            // add each operator o
      r=f(
        l,
        s[g="replace"](o,""), // remove it from the list of remaining operators
        p+o                   // add it to the permutation
      )
        ||r                   // r = the output of any permutation (if it has output)
    )
    &&r                       // return r
  :                           // else if there are no remaining operators
    l.split` `.every(x=>      // for each expression
      (q=x.split`=`)          // q = [ equation, result ]
      [1]==eval(              // if the results is equal to the eval result

        // Replace each letter with the current permutation
        q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])
      )
    )

    // If all results matched, add permutation symbols to present characters and return
    &&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")

Test
Test does not use default arguments for browser compatibility.

var solution = f=(l,s,p,r)=>s==null&&(s="+-*/",p="",0)?0:s?[...s].map(o=>r=f(l,s[g="replace"](o,""),p+o)||r)&&r:l.split` `.every(x=>(q=x.split`=`)[1]==eval(q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])))&&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")
<input type="text" id="input" value="2A2=4 0C0=0 5B0=5 5A0=5" />
<button onclick="result.textContent=solution(input.value)">Go</button>