text:
Anagram Bubble Sorter
The Challenge
A bubble sort takes a list of non-repeating integers and sorts them in ascending order, with only the use of one operation: switching two numbers which are next to eachother.
However for this puzzle, you must take in two strings, which are both anagrams, and bubble sort the letters of the first string into the second.
Example:
Trap, Part
TRAP
TRPA
TPRA
PTRA
PTAR
PATR
PART
Rules

Your program must only use the switching operation
Your program must use the most optimal way of bubble sorting
This is code golf, lowest amount of bytes wins!

Could you provide examples?

do we have to print each step?

@maltysen no, as long as you follow the rules provided its ok.

Can you elaborate on the sort algorithm used? In most bubble sorts I've seen, the example's T would quickly bubble down and the P would take longer to get in position. Here it seems to be the opposite.

@geobits The code does not have to be a specific algorithm. I listed that example because it follows the two rules: it only moves by switching and is the least possible moves for it

Your example shows some mixed case words on the first line and uppercase words on the second line. 1. Is the first line the input and the second line the desired output? 2. Should input and output be exactly like this, i.e., input separated by a comma, output separated by spaces? 3. Do we have to convert the input to uppercase?

@Dennis The program should not be case sensitive, i.e. PArt and TrAp should work with the program. And again, no output is required, and any input form is ok.

No output is required? Then I could just submit an empty program...

@Reto Koradi that makes no sense, you are not following the rules with that submission.You arent taking in two strings, and you arent modifying the first one with the switch movement to be equal to the second one.

If I understand your intentions, you want us to modify an array of letters in place using only swaps, using the minimum amount of swaps. I'm not sure how much sense this makes since a) Strings are immutable in many languages, so they can't be modified at all. b) That not at all what bubble sort does. Bubble sort is not about finding a minimum number of swaps, but about iterating over a list and conditionally swapping two adjacent elements if they're out of order.

source: Stack Exchange

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

sort: votes


text:
Make my pseudocode real
I've got some Java pseudocode that uses whitespace instead of curly braces, and I want you to convert it.
I/O
Your program should take an input file along with a number designating how many spaces are used to indent a block. Here's an example:

$ convert.lang input.p 4
// Convert using 4 spaces as the block delimiter
$ convert.lang input.p 2
// Convert using 2 spaces as the block delimiter

It should then convert the result using the specified block delimiter and output the result to stdout.
The meat of the program
Blocks open with : and each line within the block is indented using the block delimiter, like Python code.

while(true):
    System.out.println("Test");

Each : is replaced with a  {, and a } is appended to the end of the block.

while(true) {
    System.out.println("Test");
}

Examples
Input:

public class Test:
    public static void main(String[] args):
        System.out.println("Java is verbose...");
Output:

$ convert Test.pseudojava 4
public class Test {
    public static void main(String[] args) {
        System.out.println("Java is verbose...");
    }
}
Input:

main():
  printf("Hello World");

Output:

$ convert test.file 2
main() {
  printf("Hello World");
}
Input:
def generic_op(the_stack, func):
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list):
        if b:
            return
        top = b.pop(0)
        while b:
            top = func(top, b.pop(0))
        the_stack.push(top)
    else:
        a = the_stack.pop()
        return func(a, b)
Output:

$ convert code.py 4
def generic_op(the_stack, func){
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list) {
        if b {
            return
        }
        top = b.pop(0)
        while b {
            top = func(top, b.pop(0))
        }
        the_stack.push(top)
    }
    else {
        a = the_stack.pop()
        return func(a, b)
    }
}

Scoring
The code with the least amount of bytes wins!

Can we assume that the input contains no comments?

@MartinBüttner It may contain comments, but the comments won't contain ':'. Basically, yes.

What about labels, which are the usual reason that a line would end in a colon in valid Java source?

I've never seen a label anywhere but the beginning of a line.

@PeterTaylor Just ignore those. Let's assume the programmer who made it knew not to use them.

I've just been reminded of how much I hate Java.

Is the indentation block size a required parameter?

@NotthatCharles not if you can detect it automatically, but otherwise yes

Why would anyone want to convert OUT of Python pseudocode.

System.out.println("Java is verbose..."); ಠ_ಠ

Perl, 41 bytes
#!perl -p0
1while s/( *).*\K:((
\1 .*)+)/ {\2
\1}/

Counting the shebang as two, input is taken from stdin. A command line argument need not be provided. Any valid nesting context can be determined (and matched) without knowing the indentation size.

Regex Break-Down
( *)                   # as many spaces as possible (\1)
    .*                 # as many non-newline characters as possible \
                         (greediness ensures this will always match a full line)
      \K               # keep all that (i.e. look-behind assertion)
        :              # colon at eol (newline must be matched next)
         (
          (
           \n\1        # newline with at least one more space than the first match
                .*     # non-newlines until eol
                  )+   # as many of these lines as possible
                    )  # grouping (\2)

Sample Usage
in1.dat
public class Test:
    public static void main(String[] args):
        System.out.println("Java is verbose...");

Output
$ perl py2java.pl < in1.dat
public class Test {
    public static void main(String[] args) {
        System.out.println("Java is verbose...");
    }
}

in2.dat
main():
  printf("Hello World");

Output
$ perl py2java.pl < in2.dat
main() {
  printf("Hello World");
}

in3.dat
def generic_op(the_stack, func):
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list):
        if b:
            return
        top = b.pop(0)
        while b:
            top = func(top, b.pop(0))
        the_stack.push(top)
    else:
        a = the_stack.pop()
        return func(a, b)

Output
$ perl py2java.pl < in3.dat
def generic_op(the_stack, func) {
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list) {
        if b {
            return
        }
        top = b.pop(0)
        while b {
            top = func(top, b.pop(0))
        }
        the_stack.push(top)
    }
    else {
        a = the_stack.pop()
        return func(a, b)
    }
}

i just wrote this in ruby

Python 3, 299 265 bytes
import sys;s=int(sys.argv[2]);t="";b=0
for l in open(sys.argv[1]):
 h=l;g=0
 for c in l:
  if c!=" ":break
  g+=1
 if g/s<b:h=" "*g+"}\n"+h;b-=1
 if l.strip().endswith(":"):h=l.split(":")[0];h+=" {";b+=1
 t+=h+"\n"
b-=1
while b>-1:
 t+=" "*(b*s)+"}\n"b-=1
print(t)

Boom bam pow.
Algorithm used:

//global vars
string total //total modified program
int b //indent buffer

line thru lines: //iterate over every line
  string mline = "" //line to be added to the total

  //calculate the amount of spaces before the line (could be a lot easier)
  int spaces = 0 //total spaces
  c thru line: //go through every character in the line
    if c != " ": //if the current char isn't a space (meaning we went though all of them
        break //break out of iterating through chars
    spaces++ //increment the spaces because we've hit a space (hurr derr)

  if spaces/SPACE_SETTING < b: //if indent count of the current line is less than the indent buffer
    mline = "}\n" + line //add closing bracket to beginning of line
    b-- //decrement buffer

  if line.endswith(":"): //if the line ends with a `:`
    remove : from line
    mline += " {" //append {
    b++ //increment buffer
  total += mline //add modified line to total

print(total)

Can you include an explanation?

@TanMath Added the algorithm I used

Does it work with Python 2?

@wb9688 No idea, I only tested it with Python 3

I just tested, and it works with Python 2

Ruby, 70
x=$_+"
"
1while x.sub! /^(( *).*):
((\2 .*?
)*)/,'\1 {
\3\2}
'
$><<x

Adds a trailing newline.  Does not need the indent block-size parameter.
Run this with -n0 (this is really 68+2).  Thank you greatly to @primo for saving over a dozen bytes.

I think -p0 also works for ruby (-0 reads all input at once, -p stores stdin into $_, and auto-prints it at the end).

@primo Good point.  In case it wasn't clear with my comment above, this isn't a port of your code, but my own work that does exactly what yours does (but with more bytes)

I understood correctly, just providing a tip to remove the (rather verbose) x=$<.readlines*''. While I'm doing that, sub! also has a two parameter overload (rather than one paramater + block) that accepts a replacement string, so you can use \1, \2, etc. instead of needing to concatenate it all.

@primo Thanks!  I tried the two-parameter version before and abandoned it at some point last night.

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


text:
Program the Cup-Stacking Robot
I'm sure everyone has seen before that cups can be stacked into pyramids (and other shapes):
           A
        A A A
 A     A A A A
A A A A A A A A

Yes, A is definitely an adequate character to represent a cup.
New cups could be added either on the ground, to the right of the structure, or on top of two adjacent cups. Here is the above structure again, but all available spots for new cups are marked with _:
         _ A
        A A A
 A _ _ A A A A
A A A A A A A A _ _ _

Let's say we want to build a robot which can assemble these cup stacks. The robot will understand two simple instructions to manipulate such a structure:

a: Add a new cup in the first available spot in left-to-right reading order (that is, scan the rows from top to bottom, left to right until you find an available spot, then place the cup there). The above example would become:
         A A
        A A A
 A     A A A A
A A A A A A A A

r: Remove the first cup in left-to-right reading order. The above example would become:
        A A A
 A     A A A A
A A A A A A A A

It turns out that any structure can be constructed from scratch using only these two operations. E.g.
      A
 A   A A
A A A A A

Can be built with the sequence of instructions
aaaaaaaaaaaarrrrraa

The larger example above can be built using
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrraaaaaaarr

Here is an even bigger one:
    A
   A A                   A
  A A A     A   A       A A
 A A A A   A A A A     A A A A
A A A A A A A A A A   A A A A A

which can be built with
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa

Note: If spots on the ground are freed up by removal instructions they will be reused before placing cups to the right of all existing cups. E.g.
aaaarrra

will yield
A   A

not
    A A

You can think of the ground as being on top of a semi-infinite row of cups.
The Challenge
Given a structure of stacked cups, return a sequence representing the instructions to build this structure. Your primary score is the sum of the numbers of instructions for the test cases provided at the bottom. In the event of a tie (which is likely, because I'm convinced that an efficient optimal solution is possible), the shortest solution wins.
Here are some more details about the rules:

You may assume that there are no leading spaces on the bottom row of the input, so the left-most ground spot for a cup with always be used.
You may assume any reasonable amount of trailing spaces (no spaces, one space, padded to a rectangle, padded to a rectangle with a single trailing space).
You may optionally expect the input to end in a single trailing newline.
You may choose any two distinct printable ASCII characters (0x20 to 0x7E, inclusive) instead of A and spaces (the rules about spaces then transfer to your chosen character).
Your output should contain only two distinct characters representing the operations (you may choose other characters than a and r). You may optionally print a single trailing newline.
Your code must be able to solve any of the test cases below in less than a minute on a reasonable desktop PC (if it takes two minutes on mine, I'll give you the benefit of the doubt, but if it takes ten I won't - I believe an optimal algorithm is possible which solves any of them in less than a second).
You must not optimise your code towards individual test cases (e.g. by hardcoding them). If I suspect anyone of doing so, I reserve the right to change the test cases.

You can use this CJam script for the reverse operation: it will take a string of building instructions and print the resulting stack of cups. (Thanks to Dennis for rewriting the snippet and significantly speeding it up.)
Sp3000 also kindly provided this alternative Python script for the same purpose.
Test Cases
After each test case, there's a number indicating the optimal number of instructions as per Ell's answer.
                                       A
                                      A A
                                     A A A
                                    A A A A
                                   A A A A A
                                  A A A A A A
                                 A A A A A A A
                                A A A A A A A A
                               A A A A A A A A A
                              A A A A A A A A A A
                             A A A A A A A A A A A
                            A A A A A A A A A A A A
                           A A A A A A A A A A A A A
                          A A A A A A A A A A A A A A
                         A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A
                       A A A A A A A A A A A A A A A A A
                      A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A
                    A A A A A A A A A A A A A A A A A A A A
                   A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A
                 A A A A A A A A A A A A A A A A A A A A A A A
                A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A
              A A A A A A A A A A A A A A A A A A A A A A A A A A
             A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

820
                                             A
                                            A A
                                           A A A
                                          A A A A
                                         A A A A A
                                        A A A A A A
                                       A A A A A A A
                                      A A A A A A A A
                     A               A A A A A A A A A
                    A A             A A A A A A A A A A
                   A A A           A A A A A A A A A A A
                  A A A A         A A A A A A A A A A A A
         A       A A A A A       A A A A A A A A A A A A A
        A A     A A A A A A     A A A A A A A A A A A A A A
   A   A A A   A A A A A A A   A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

1946

               A
              A A
             A A A
            A A A A
           A A A A A
          A A A A A A
         A A A A A A A
        A A A A A A A A
       A A A A A A A A A               A
      A A A A A A A A A A             A A
     A A A A A A A A A A A           A A A
    A A A A A A A A A A A A         A A A A
   A A A A A A A A A A A A A       A A A A A       A
  A A A A A A A A A A A A A A     A A A A A A     A A
 A A A A A A A A A A A A A A A   A A A A A A A   A A A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

2252

                                                         A A
                                                      A A A A
                                                   A A A A A A
                                                A A A A A A A A
                                             A A A A A A A A A A
                                          A A A A A A A A A A A A
                                       A A A A A A A A A A A A A A
                                    A A A A A A A A A A A A A A A A
                                 A A A A A A A A A A A A A A A A A A
                              A A A A A A A A A A A A A A A A A A A A
                           A A A A A A A A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

9958

                   A A
                  A A A A
                 A A A A A A
                A A A A A A A A
               A A A A A A A A A A
              A A A A A A A A A A A A
             A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

5540

A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A

10280

 A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

10320

   A       A       A       A       A       A       A       A       A       A
  A A     A A     A A     A A     A A     A A     A A     A A     A A     A A
 A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

5794

              A
             A A
            A A A
           A A A A                                               A
          A A A A A                                             A A
         A A A A A A A                                         A A A
        A A A A A A A A               A                       A A A A
       A A A A A A A A A             A A             A       A A A A A   A
      A A A A A A A A A A           A A A           A A     A A A A A A A A
     A A A A A A A A A A A         A A A A         A A A   A A A A A A A A A
    A A A A A A A A A A A A       A A A A A       A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A     A A A A A A     A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A   A A A A A A A   A A A A A A A A A A A A A A A A

3297

                                                   A A
                                                  A A A
                                                 A A A A
                                                A A A A A
                                               A A A A A A
                                              A A A A A A A
                                             A A A A A A A A
                                            A A A A A A A A A
                                           A A A A A A A A A A     A
                                          A A A A A A A A A A A   A A
                                       A A A A A A A A A A A A A A A A
                                      A A A A A A A A A A A A A A A A A
                                     A A A A A A A A A A A A A A A A A A
      A                             A A A A A A A A A A A A A A A A A A A
     A A                           A A A A A A A A A A A A A A A A A A A A
    A A A             A A         A A A A A A A A A A A A A A A A A A A A A
   A A A A           A A A       A A A A A A A A A A A A A A A A A A A A A A
  A A A A A         A A A A     A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A     A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

4081

                      A
                     A A       A                     A
                    A A A     A A                   A A A                 A
             A     A A A A   A A A A               A A A A     A         A A
  A         A A   A A A A A A A A A A         A   A A A A A   A A       A A A
 A A       A A A A A A A A A A A A A A       A A A A A A A A A A A     A A A A
A A A   A A A A A A A A A A A A A A A A     A A A A A A A A A A A A   A A A A A

4475

                                                             A
      A           A                       A                 A A A   A       A
     A A         A A   A         A A     A A A   A         A A A A A A     A A
A   A A A A A   A A A A A   A   A A A   A A A A A A   A   A A A A A A A   A A A

5752

That means, the best possible score is 64,515 instructions.

Python 2, 64,515
import sys

input = map(str.rstrip, sys.stdin.readlines())
width = (len(input[-1]) + 1) / 2
for i in range(len(input)):
    indent = len(input) - i - 1
    input[i] = [c != " " for c in input[i][indent::2]]
    input[i] += [False] * (width - indent - len(input[i]))
input = [[False] * n for n in range(width - len(input) + 1)] + input
working_area = [[False] * n for n in range(width + 1)]

def add():
    sys.stdout.write("a")
    for row in range(width + 1):
        for i in range(row):
            if not working_area[row][i] and (
                row == width or
                (working_area[row + 1][i] and working_area[row + 1][i + 1])
            ):
                working_area[row][i] = True
                return
def remove():
    sys.stdout.write("r")
    for row in range(width + 1):
        if True in working_area[row]:
            working_area[row][working_area[row].index(True)] = False
            return

for row in range(width, -1, -1):
    r = input[row]; R = working_area[row]
    for i in range(len(r) - 1, -1, -1):
        if r[i]:
            while not R[i]: add()
        else:
            while R[i]: remove()

Results
 #1 - 820
 #2 - 1,946
 #3 - 2,252

 #4 - 9,958
 #5 - 5,540
 #6 - 10,280

 #7 - 10,320
 #8 - 5,794
 #9 - 3,297

 #10 - 4,081
 #11 - 4,475
 #12 - 5,752
Total 64,515
Explanation
We start with an empty "working area".
We scan the input in reverse reading order, i.e., right-to-left and bottom-to-top.
If there's a mismatch between the input and the working area at the current location (i.e., a cup is present in the input but not in the working area, or vice versa,) we add, or remove, cups to the working area, according to the rules, until the mismatch is resolved, at which point we continue to the next location.
Correctness
To show that this method is correct, i.e., that the resulting sequence generates the input structure, it's enough to show that we never modify (i.e., add or remove cups at) locations we've already visited (since, at each location we visit, we make sure that the working area matches the input.)
This is an easy consequence of the fact that we work in the reverse order in which cups are added and removed:

A cup at location l will always be removed before a cup at a location that succeeds l in reading order, and therefore, that precedes l in scan order, hence there's no danger of removing a cup we've already visited.
Similarly, a cup at location l will always be added before a cup that precedes it in scan order, given that there are already two cups below it (or that it's at the bottom);
however, since we will have already visited these locations, and hence added the necessary cups, and since, as noted above, there's no danger of later having removed those cups, this condition is met, and so there's no danger of adding a cup at a location we've already visited.

Optimality
Note that the effect of adding, or removing, a cup from a structure doesn't depend on the sequence of operations used to generate the structure, only on its current configuration.
As a result, given an optimal sequence Sn = {s1, ..., sn} of operations that generate a certain structure, every initial segment of Sn, i.e., any sequence Sm = {s1, ..., sm}, where m ≤ n, is also an optimal sequence, for the corresponding structure it generates, or else there would be a shorter sequence than Sn, generating the same structure.
We can show that our method is optimal by induction on the length of the optimal generating sequence:
Our method clearly generates an optimal sequence for any structure whose optimal generating sequence is empty (there's only one such structure—the empty structure.)
Suppose that our method generates an optimal sequence for all structures whose optimal sequence (or sequences) is of length n, and consider a structure generated by an optimal sequence Sn+1.
We want to show that, given the structure generated by Sn+1 as input, our method produces the same sequence (or, at least, a sequence of the same length.)
As noted above, Sn is also an optimal sequence, and so, by hypothesis, our method produces an optimal sequence given the structure generated by Sn as input.
Suppose, without loss of generality, that Sn is the sequence produced by our method (if it isn't, we can always replace the first n elements of Sn+1 with the said sequence, and get a sequence of length n + 1 that generates the same structure.)
Let l be the location modified by the last operation in Sn+1 (namely, sn+1), and let Sm be the initial segment of Sn, that our program will have produced once it reaches l (but before processing l).
Note that, since the structures generated by Sn and Sn+1 agree in all locations that follow l, in reading order, Sm is the same given either structure as input.
If sn+1 is a (i.e., cup addition), then there must not be any location preceding l, in reading order, where a cup can be added to the structure generated by Sn. As a result, the subsequence of Sn following Sm must be all a (since an r would imply that either there's an empty space before l, or that Sn is not optimal.)
When we come to process l, we'll need to add exactly n - m cups before we can add a cup at l, hence the resulting sequence will be Sm, followed by n - m + 1 a elements, which equals Sn+1 (there won't be any mismatch after this point, hence this is the complete sequence produced.)
Likewise, if sn+1 is r, then there must not be any cup at a location preceding l, in reading order, in the structure generated by Sn. As a result, the subsequence of Sn following Sm must be all r.
When we come to process l, we'll need to remove exactly n - m cups before we can remove the cup at l, hence the resulting sequence will be Sm, followed by n - m + 1 r elements, which again equals Sn+1.
In other words, our method produces an optimal sequence for the said input structure, and therefore, by induction, for any input structure.
Note that this doesn't mean that this implementation is the most efficient one.
It's definitely possible, for example, to calculate the number of cups that has to be added, or removed, at each point directly, instead of actually performing these operations.
Uniqueness
We can use the optimality of our method to show that optimal sequences are, in fact, unique (that is, that no two distinct optimal sequences generate the same structure.)
We use, again, induction on the size of the optimal generating sequence:
The empty sequence is obviously the unique optimal generating sequence of the empty structure.
Suppose that all optimal generating sequences of length n are unique, and consider a structure, Σ, generated by the two optimal sequences Sn+1 and Tn+1.
Recall that Sn and Tn are themselves optimal, and therefore, by hypothesis, unique.
Since our method produces optimal sequences, Sn and Tn can be thought of as generated by our method.
Let lS and lT be the locations modified by the last operation in Sn+1 and Tn+1, respectively, and suppose, without loss of generality, that lS follows, or equals, lT in reading order.
Since the structures generated by Sn and Tn agree in all locations following lS, in reading order, the sequence produced by our method, given either structure as input, once it reaches lS (but before processing it), is the same for both; call this sequence U.
Since the last action of Sn+1 modifies lS, if Σ has a cup at lS then there must not be any vacancy before lS, and if Σ doesn't have a cup at lS then there must not be any cup before lS, in reading order.
Therefore, the rest of the sequence generating Σ, following U, must consist of repeated application of the same instruction, dictated by the presence or absence of a cup at lS (or else it wouldn't be optimal).
In other words, Sn+1 and Tn+1 are equal (they both start with U, and end with the said sequence of repeated instructions,) that is, the optimal generating sequence of Σ is unique, and so, by induction, all optimal generating sequences are unique.

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


text:
*Overwrit*labels
If you've ever tried adding labels to a really dense plot, then you'll realise that sometimes labels will overlap one another, making them hard to read. We're going to do something similar but in 1D.
Input will be a sequence of (label, x-coordinate) pairs, and output will be the result of drawing each point and label, in the given order. An asterisk * representing the point should be placed at the given x-coordinate and the label should follow. Any existing characters will be overwritten.
For instance, if the input was
Hello  0
World  8
Fizz   3
Buzz   5
PPCG   16
X      9

Then the following would happen:
*Hello
*Hello  *World
*He*Fizz*World
*He*F*Buzzorld
*He*F*Buzzorld  *PPCG
*He*F*Buz*Xrld  *PPCG

The final line should then be outputted.
I/O rules

Input may consist of any number of pairs. Each label will only consist of uppercase and lowercase letters, and label lengths will be at most 127 chars. Each x-coordinate will be between 0 and 127 inclusive.
Input may be in any convenient list or string format such that the pairs are unambiguous and labels/x-coordinates alternate in the input. For example, a format like [("Hello", 0), ("World", 8) ...] or [0 "Hello" 8 "World" ...] is fine. However, you may not assume two separate lists of labels and x-coordinates.
Functions and full programs are both okay.
Any spots not covered by a label should be represented with a space. However, there may not be any extraneous leading or trailing whitespace aside from a single optional trailing newline.

Examples
Input:
OneLabel   10

Output:
          *OneLabel

Input:
Heathrow   0
Edinburgh  2
London     4
Liverpool  6
Oxford     8

Output:
*H*E*L*L*Oxfordl

Input:
alpha     20
beta       4
gamma     57
delta      3
epsilon   22
zeta      32
eta       53
theta     27

Output:
   *delta           *a*epsi*thetazeta                *eta*gamma

Input:
abc  5
d    5
abc  10
ABCDEFGHIJKLMNOPQRSTUVWXYZ 127

Output:
     *dbc *abc                                                                                *ABCDEFGHIJKLMNOPQRSTUVWXYZ

Note that labels and/or x-coordinates may be repeated.

If the x coords are [0,127] and the strings are (0,127], can a label run off the far right end of the line, or is it protected? That is, does "foo 127" end the line with "*" or "*foo"? Just checking if the string should have a soft or hard ending.

@PotatoOmeletteSandwich My intention was so that the total length fits within 255, so the maximal output length will occur when there is a length 127 label at x-coordinate 127. The final output should not be truncated in any way, except to remove trailing whitespace.

CJam, 24 23 19 bytes
l~Sf.*'*f*:.{S^+1=}

This reads the input as a CJam array of coordinate-label pairs.
Try this fiddle in the CJam interpreter or verify all test cases at once.
Thanks to @MartinBüttner for helping me save 4 bytes!
How it works
l~                   Read a line from STDIN and evaluate it.
  Sf                 For each pair, push the pair and " "; then:
    .*                 Perform vectorized repetition.
                         [X "label"] " " .* -> [(X spaces) "label"]
      '*f*           Join each resulting pair, using '*' as separator.
          :.{     }  Reduce by the following vectorized operator:
                       Push two characters (A and B).
             S^        Compute the symmetric difference of B and " ".
                       This pushes "B " for a non-space B and "" otherwise.
                +1=    Append and select the second character (with wrap).
                       This selects B for "AB " and A for "A".

I just added a test case and thought I'd leave a comment saying that no, it didn't break this submission - CJam's interpreter output just word wraps. Just in case anybody gets confused.

Python 2, 67 bytes
z=''
for a,b in input():z=(z+' '*b)[:b]+'*'+a+z[len(a)-~b:]
print z

Takes input like [('Heathrow', 0), ('Edinburgh', 2), ('London', 4), ('Liverpool', 6), ('Oxford', 8)] and prints the result.
Python doesn't allow strings to be modified, and converting to and from a list is expensive. So, this recreates the string z to add in a new word. We take the b characters before the word, padding with spaces if needed, then the new text with an asterisk, then the part of z after the new word. Note that trailing spaces are never added.
The reduce version is 3 chars longer (70):
lambda I:reduce(lambda z,(a,b):(z+' '*b)[:b]+'*'+a+z[len(a)-~b:],I,"")

Pyth, 20 bytes
V.Tmrj" *"d9Qpe+d-Nd

Try it online: Demonstration or Test Suite
Explanation
V.Tmrj" *"d9Qpe+d-Nd
   m        Q         map each pair d of the input to:
     j" *"d             join d by the string " *"
    r      9            range-length encode
                        (this gives x-coordinate spaces, a star and the label)
 .T                   transpose this table
V                     for N in ^:
                 -Nd    remove spaces from N
               +d       add a space at the beginning
              e         take the last character
             p          and print it (without newline)

This is way better than what I had.

JavaScript ES6, 104 bytes
c=>(a=Array(255).fill(" "))&&c.map(([u,v])=>a.splice(u,v.length+1,..."*"+v))&&a.join``.replace(/ +$/,"")

Example Usage
Input into a compliant console:
t = [[0,"Hello"],[8,"World"],[3,"Fizz"],[5,"Buzz"],[16,"PPCG"],[9,"X"]];
(c=>(a=Array(255).fill(" "))&&c.map(([u,v])=>a.splice(u,v.length+1,..."*"+v))&&a.join``.replace(/ +$/,""))(t);

Output from the last statement:
"*He*F*Buz*Xrld  *PPCG"

Explanation
This creates an anonymous function from c to three expressions that have been logically-ANDed together. The first two statements are always truthy, and the JS short-circuit rules say that whenever the first is truthy, return the entire value on the right hand side (without coercing to boolean): so this is formally equivalent to
(function (c) {
    a = Array(255).fill(" ");                    // global variable `a` overwritten
    c.map(function (x) {                         // only side-effects are used here.
       var u = x[0], v = x[1];                   // ES6 destructuring
       a.splice(u, v.length + 1, ..."*" + v));   // main logic
    });
    return a.join("").replace(/ +$/, "");        // postprocessing and trim
})

The first statement has to be wrapped in parentheses above because the assignment operator = has lower precedence than the logical-AND operator &&.
The "rest parameter" assembly ..."*"+v is also part of ES6; it concatenates a leading * to the string and then interprets it as a list-like parameter, splitting it into a bunch of arguments which are provided to Array.prototype.splice, which takes (m, n, ...rest) and modifies its array at position m to remove n elements and then insert all of the rest arguments. To accomplish this before ES6 you would use the more cumbersome:
[].slice.apply(a, [u, v.length + 1].concat(("*" + v).split("")))

The array then gets concatenated with the empty string and trailing whitespace is deleted.

Ruby, 94 81 75 bytes
Golfed:
s=" "*128;$<.map{|l|w,p=l.split;p=p.to_i;s[p..w.size+p]="*"+w};$><<s.rstrip

Here's the ungolfed code:
s = " "*128
$<.map{|l|                 # for each line entered via stdin, ctrl+D to stop
  w,p = l.split            # had to move the chomp down here
  p = p.to_i               # there's no 'to_i!'...
  s[p..w.size+p] = "*"+w   # in the range of *foobar, replace the string
}
$><<s.rstrip               # output suggested by w0lf

Thanks @w0lf for the suggestions on mapping the input!
Thanks @w0lf and @Not that Charles for the thought on removing a variable.

See the Ruby golfing tips. In this case you could apply the $<.map{|l|...} is shorter than while l=gets;...;end tip and probably replace puts  with $><< (which does not require the extra space).

also, I think .chomp can be removed.

In this case, now that you mention it, I think it's likely very safe to remove, as .to_i will catch that. Good thought. Thanks @w0lf!

You're welcome! Here's a shorter version in which I applied the tips above and a few more: http://ideone.com/BiOvV5. Feel free to post it in your answer if you like it.

Wow, that's a cool approach. Shows me I still have a lot to learn about golfing.

Why not drop the need for d with s[p,w.length+1]="*"+w?

1 byte: "*" -> ?*

@daniero at least the version of ruby I'm using converts ?* to the character code 42, which cannot be added to the string following it.

@PotatoOmeletteSandwich Upgrade your Ruby.  1.8.7 is end-of-lifed!  also, you should be able to use the s[int, int] form instead of s[range] for 1 char savings.

Javascript 121 chars
Using non-standard features, works on Firefox.
x=Array(255).fill(" ");eval(prompt()).map(s=>{s[0].split``.map((n,i)=>x[s[1]+i+1]=n);x[s[1]]="*"});x=x.join``.trimRight()
Older version:
x=Array(255).fill(" ");eval(prompt()).map(s=>{s[0].split``.map((n,i)=>x[s[1]+i+1]=n);x[s[1]]="*"});x=x.join``.replace(/ +$/,"")
x=Array(255).fill(" ");      //Creates an array with spaces
eval(prompt())               //Gets some input, has to look like [["Hello",4],["Hi",14],["Oi",0]]
.map(s=>{s[0].split``.map((n,i)=>x[s[1]+i+1]=n);x[s[1]]="*"}); //Main "logic"
x=x.join``.replace(/ +$/,"") //Gets rid of the trailing spaces

/ +/  makes much more sense than \s disappointed I missed that! Could you save bytes using x=' '.repeat(255); and avoiding the .join?

@DomHastings: JS strings are immutable so you would have to .split('') it into a mutable data structure, but at that point Array(255).fill(' ') is shorter. In my version most of my savings come from (a) using the "you can give either a function or program" rule to delete eval(prompt()) in exchange for c=>  and (b) using the builtin Array.prototype.slice method with a rest parameter to shorten the logic part a little bit.

@ChrisDrost ah of course... I forget it's just an accessor! Shame[].map.call(s[0], doesn't save any either...

Jelly, 14 bytes
0x;”*;µ/€Ṛo/o⁶

Try it online!
Takes input as a list of pairs [coordinate, label]. The last test case does work, TIO simply has wrapping
How it works
0x;”*;µ/€Ṛo/o⁶ - Main link. Takes a list of pairs I
        €      - Over each pair P in I:
      µ        -   Run the following, using:
       /       -     C (coord) as the left argument and L (label) as the right:
0x             -       Repeat 0 C times
  ;”*          -       Concatenate "*"
     ;         -       Append L
         Ṛ     - Reverse I
          o/   - Reduce columnwise by logical OR
                 This replaces 0s with the next non-zero element
            o⁶ - Replace the remaining zeros with spaces

Python, 85 bytes
def g(p):
 z=[' ']*256
 for a,b in p:z[b:b+len(a)+1]='*'+a
 return''.join(z).rstrip()

Try it online

You should be able to do 'z'[2::5] (backticks instead of apostrophes) instead of ''.join(z) to save one byte, and moving z=[' ']*256 to the parameters should save another. Also, I think you can change return to print.

I think you can save chars by writing a program with p=input() (Python 2) rather than a function, which avoids indentation. Also, b+len(a)+1 can be b-~len(a)

Actually, a program just lets you do for a,b in input():.

Perl, 66 bytes
63 bytes script + 3 bytes for -p
$}||=$"x128;/\s+/,substr$},$',1+length$`,"*$`"}{$_=$};s/\s+$/
/

Nothing too special, utilising the variables $` and $' which are 'before the match' and 'after the match' respectively, instead of splitting the string. I used a $} for the string variable as originally it was saving me a byte, but isn't any more!
Example run:
$perl -p overwritlabels.pl <<< 'Hello  0
World  8
Fizz   3
Buzz   5
PPCG   16
X      9'
*He*F*Buz*Xrld  *PPCG

Perl, 65 bytes
62 bytes script + 3 bytes for -p
Another version that prints out each line (for one less byte!). (Yes, I made this because I didn't read the question properly...)
$}||=$"x128;/\s+/;substr$},$',1+length$`,"*$`";$_=$};s/\s+$/
/

Example run:
$perl -p overwritlabels.pl <<< 'Hello  0
World  8
Fizz   3
Buzz   5
PPCG   16
X      9'
*Hello
*Hello  *World
*He*Fizz*World
*He*F*Buzzorld
*He*F*Buzzorld  *PPCG
*He*F*Buz*Xrld  *PPCG

PHP -- 84 bytes
<? foreach(array_chunk(array_slice($argv,1),2) as $p) echo "␣[".($p[1]+1)."G*$p[0]";
                                                            ^ ESC character (\x1b)

Uses ANSI escape codes to position the cursor (\x1b[XG, featuring the Escape character and X being the 1-based coordinate), followed by the * then the input string for that row. Accepts input on the command line of the form:
php filename.php Heathrow 0 Edinburgh 2 London 4 Liverpool 6 Oxford 8
php filename.php abc 5 d 5 abc 10 ABCDEFGHIJKLMNOPQRSTUVWXYZ 127

Accepts multi-word entries if they're in quotes, since they're command line arguments.

C++11, 95 bytes
Why not?
As a function, receive input as a map<int, string> named v containing the position and the string.
string t(255,' ');for(auto&m:v){int i=m.first;t[i++]='*';for(auto&c:m.second)t[i++]=c;}cout<<t;

Usage
#include <iostream>
#include <map>
using namespace std;
int main(){
    map<int,string> v{{0,"Heathrow"},{2,"Edinburgh"},{4,"London"},{6,"Liverpool"},{8,"Oxford"}};
    string t(255,' ');for(auto&m:v){int i=m.first;t[i++]='*';for(auto&c:m.second)t[i++]=c;}cout<<t;
}

Check it Running Here

Husk, 13 bytes
Fż|mF(J'*eR'

Try it online!
Takes a list of pairs (coordinate, label) as input. N.B.: there is a space character at the end of the code.
Explanation
Fż|mF(J'*eR'
   m             For each pair in the input
    F            apply the following function using the pair members as arguments
          R'     Repeat a space (coord) time
         e       put this in a list with the label
      J'*        and join the strings in the list with "*"
F                Fold over the resulting list
 ż               by zipping strings together
                   (keeping extra characters in the longer string unchanged)
  |              with OR (Second argument if truthy else first. Spaces in Husk are falsy)

Japt, 18 bytes
rÈh'*+YÎYÌ}Sp#ÿ)x1

Try it online!
Takes input as an array of [label, x-coordinate]
Explanation:
rÈh'*+YÎYÌ}Sp#ÿ)x1    #
           Sp#ÿ       # Store 255 spaces as X
r         }    )      # Do this for each pair in order:
 Èh                   #  Overwrite part of X:
        YÌ            #   Starting at index equal to the second item of the pair
   '*                 #   Write "*"
     +YÎ              #   Write the first item of the pair
                x1    # Remove any remaining whitespace on the right side

Stax, 11 8 bytes
┤6╧ß╡⌠░$

Run and debug it
Takes input as a list of pairs [coordinate, label]. Thanks to caird coinheringaahing for the testcases.
Explanation
zsFE'*s+|%
zs            push empty list and swap with the input
  F           for each element,
   E          push each item onto stack
    '*s+      add asterisk to label
              Stack: [index,label]
        |%    embed in the array

Canvas, 9 bytes
Ｈ｛｝０┘*；＋╋

Try it here!
Same as my Stax answer, except canvas is better at grid overlaps.

GolfScript, 29 bytes
~""\{~." "*3$\+<"*"+\+.,@>+}/

Try it online!


text:
Check if a given 8-bit Number is sparse
The task is the following:
Program the shortest fully functional program that checks, if an 8-bit value contains a consecutive sequence of 2 or more ones in its binary form.
If it does contain such a sequence, the output shall be 0. If not: 1.
Examples:
Input: 1
Output: 1
Input: 3
Output: 0
Input: 72
Output: 1
Input: 75
Output: 0

The shortest solution wins!

Welcome to PPCG! I'm a little confused though, so may I ask a few questions? 1) "If this is the case, the output shall be 1, if not: 1." Should one of these be a 0? and 2) Does a sequence mean a consecutive sequence like 11? If so, how do the last two cases work? (72 = 1001000, 73 = 1001001)

Closely related.

you're completely right. It was a typo and I mean indeed consecutive series of ones :)

I fixed one more place where the typo was, and added the "code-golf" tag. I strongly suggest that you read the tag wiki to get a general idea of what the tag is about. There are some folks checking for duplicates of your question. If they find none, I'm sure they will vote to reopen your question. Welcome to PPCG!

I do think this is a duplicate of the challenge I linked. The only real golfing trick that can be applied here is x&2*x which almost all of the answers on the other challenge already use. All answers to this challenge would do is taken an answer from there and remove the loop.

I think, you're right. Didn't see it.


text:
Print a cube's vertices and its covering triangles
Output coordinates of the vertices of a cube. Then, output a list of twelve triangles that will cover the cube, each triangle being a list of three vertex-indexes, consistently oriented. Output must be an ASCII string of distinct decimal numbers. This golf has no input. Winner is the fewest characters, where the character set is Unicode.
For an example, consider a 1x1x1 cube cornered at 0,0,0. The eight vertices of the cube can be described by the following xyz coordinates on a 3d Cartesian grid:
x y z = (0,0,1) (1,0,1) (1,1,1) (0,1,1) (0,0,0) (1,0,0) (1,1,0) (0,1,0)

Each vertex can be given an index: x y z->index: 0 0 1->0, 1 0 1->1, 1 1 1->2, 0 1 1->3, 0 0 0->4, 1 0 0->5, 1 1 0->6, 0 1 0->7
Now consider the top face, vertexes indexed zero to three. The two covering triangles can be described by three indices each:
[0,1,2] [2,3,0]

Here is a picture of this top face, viewed from above the cube:
 3_____2
 |    /|
 |   / |
 |  /  |
 | /   |
 0_____1

And here is a view from an angle.
    3____2
   / __-/|
 0/_`__1 |
  |    | /6
  |____|/
 4     5

Note the orientation, or 'winding', of both of these triangles is 'counterclockwise' when viewed from 'outside' the cube directly looking at the face in question (imagine visiting each vertex as listed, it goes counterclockwise). Now imagine this done for all six sides of the cube.
vertices: (0,0,1) (1,0,1) (1,1,1) (0,1,1) (0,0,0) (1,0,0) (1,1,0) (0,1,0)
triangles as indices: [0,1,2], [2,3,0], [6,5,4], [4,7,6],
  [5,2,1], [2,5,6], [0,3,4], [4,3,7], [2,6,3], [3,6,7], [0,4,1], [1,4,5]

You can output any size of cube located at any coordinates. You can number and order the vertex coordinates however you wish. Indices can be 0 based or 1 based. The triangle's orientation can be either clockwise or counterclockwise when viewed from outside the cube as long as it is consistent for all triangles.
The output can be formatted however you wish, as long as each ASCII decimal number is separated by at least one non-numeric ASCII character. For instance the above example could also be output as follows:
0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0
0 1 2 2 3 0 6 5 4 4 7 6 5 2 1 2 5 6 0 3 4 4 3 7 2 6 3 3 6 7 0 4 1 1 4 5

This golf is inspired by various 3d graphics systems and formats, including OpenGL, OBJ, OFF, AMF, CGAL, etc. This golf is similar to the golf by Calvin's Hobbies named Output a Face on a Numbered Cube , the big difference being you need to output the x y z coordinates of the vertices yourself and output triangle indices. Thanks for reading.
Per user inspiration here is a "helper" validation program in python2 (non-golfy) that will print 'ok' or 'not ok' for test output data in variables vertstr and idxstr. It doesn't work perfectly... but it can catch some errors.
Edit: fixed typo in example and bugs in validation code.

#vertstr = '0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1'
#idxstr = '1 2 0 2 1 3 7 5 6 4 6 5 2 4 0 4 2 6 7 3 5 1 5 3 4 1 0 1 4 5 7 6 3 2 3 6'
vertstr = '0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0'
idxstr = '0 1 2 2 3 0 6 5 4 4 7 6 5 2 1 2 5 6 0 3 4 4 3 7 2 6 3 3 6 7 0 4 1 1 4 5'

class Vector:
    def __init__(self,v):
        self.x,self.y,self.z=v[0],v[1],v[2]
    def __add__(self,v):
        return Vector([self.x+v.x,self.y+v.y,self.z+v.z])
    def __sub__(self,v):
        return Vector([self.x-v.x,self.y-v.y,self.z-v.z])
    def __str__(self):
        return str(self.x)+','+str(self.y)+','+str(self.z)

def cross(v1,v2):
    x = v1.y*v2.z-v2.y*v1.z
    z = v1.x*v2.y-v2.x*v1.y
    y = v1.z*v2.x-v2.z*v1.x
    return Vector([x,y,z])

# http://mathforum.org/library/drmath/view/55343.html & http://sympy.org
def winding(v1,v2,v3,obs):
    x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4=v1.x,v1.y,v1.z,v2.x,v2.y,v2.z,v3.x,v3.y,v3.z,obs.x,obs.y,obs.z
    d =     x1*(y2*z3 - y2*z4 - y3*z2 + y3*z4 + y4*z2 - y4*z3)
    d = d + y1*(-x2*z3 + x2*z4 + x3*z2 - x3*z4 - x4*z2 + x4*z3)
    d = d + z1*(x2*y3 - x2*y4 - x3*y2 + x3*y4 + x4*y2 - x4*y3)
    d = d - x2*y3*z4 + x2*y4*z3 + x3*y2*z4 - x3*y4*z2 - x4*y2*z3 + x4*y3*z2
    return d

def normals(v1,v2,v3):
    va = v2-v1
    vb = v3-v2
    vc = v1-v3
    n1 = cross(va,vb)
    n2 = cross(vb,vc)
    n3 = cross(vc,va)
    return [n1,n2,n3]

def triplify(str):
    nums,triples=[],[]
    for num in str.split(' '): nums+=[int(num)]
    for i in range(0,len(nums),3):
        triples += [[nums[i],nums[i+1],nums[i+2]]]
    return triples

verts = triplify(vertstr)
indices = triplify(idxstr)
nsum = Vector([0,0,0])
windsum = 0
xs,ys,zs=[],[],[]
for v in verts:
    xs+=[v[0]]
    ys+=[v[1]]
    zs+=[v[2]]
#print xs,ys,zs,len(xs)
center=Vector([float(sum(xs))/len(xs),float(sum(ys))/len(ys),float(sum(zs))/len(zs)])
for triangle in indices:
    v1 = Vector(verts[triangle[0]])
    v2 = Vector(verts[triangle[1]])
    v3 = Vector(verts[triangle[2]])
    norms = normals(v1,v2,v3)
    print v1,v2,v3,norms[0],norms[1],norms[2]
    for n in norms:
        nsum += n
    w = winding(v1,v2,v3,center)
    print 'winding',w
    if w<0: windsum-=1
    elif w>0: windsum+=1
if abs(windsum)==12: print 'winding ok'
else: print 'winding not ok'
if (nsum.x==0 and nsum.y==0 and nsum.z==0): print 'normal sum ok'
else: print 'normal sum not ok'

It's clear from the example, but just to make it perfectly unambiguous, you may want to mention that the indices are 0-based. This is not a given, since at least one of the formats you list as example (OBJ) uses 1-based indices.

That will work as well. I think one difficulty with this challenge is that it's moderately painful to verify the correctness of the output. You pretty much have to sketch a cube with the chose vertex ordering on a piece of paper, and manually validate all 12 triangles. Well, you could write a validation program. That might actually be another challenge idea... more difficult than this one, I think.

i really like that idea of another golf for a validator. i updated the example to give a full dataset. thanks again.

ok I added a very quick and dirty validation program that takes cross products of each pair of vectors in each triangle, adds them all, and if 0 says 'ok'.

Pyth, 18 characters
j`CM"⭧勛囃勦⾽仵ᶌﻘꚱ쥎➡˻ì

Same idea as my Haskell answer; prints:
[
1
1
1
1
1
,

2
1
2
1
1
...

i love that you used the same unicode string in 3 different languages

What is this unicode magic?

CJam, 35 bytes
YZm*`3{[XY4]m<)\0+_:+1$f-+_@f+W%}%`

Try it online
The output is:

[[0 0 0] [0 0 1] [0 1 0] [0 1 1] [1 0 0] [1 0 1] [1 1 0] [1 1 1]][[1 2 0 2 1 3] [7 5 6 4 6 5] [2 4 0 4 2 6] [7 3 5 1 5 3] [4 1 0 1 4 5] [7 6 3 2 3 6]]

Triangle orientation is clockwise from the outside. I checked this manually, and it looks correct to me.
Explanation:
YZ      Push 2 and 3 on stack.
m*      Cartesian power, creates the coordinates of the 8 vertices.
`       Convert to string for output. Done with vertices.
3{      Start loop over 3 coordinate directions.
  [XY4]   Push [1 2 4], which are the vertex index offsets for the 3 directions.
  m<      Rotate by loop counter. So the remaining loop body will be executed once
          with [1 2 4], once with [2 4 1], once with [4 1 2].
  )       Pop off last offset. Will use this as index offset between the two
          parallel faces.
  \       Swap pair of remaining two offsets to top. These are the index offsets
          within the face.
  0+      Add a 0 to the list. These 3 indices define the first triangle.
  _:+     Calculate the sum. This is the vertex index of the opposite corner.
  1$      Copy first triangle to the top.
  f-      Subtract all indices from the index of the opposite corner, producing
          the second triangle of the face.
  +       Concatenate the indices of the two triangles, resulting in a list with
          the 6 vertex indices for the face.
  _       Copy the list.
  @       Bring the offset between the two faces to the top.
  f+      Add the offset to each index in the copied list.
  W%      Revert the order, resulting in the properly oriented list of the 6 vertex
          indices for the parallel face.
}%      End of loop over 3 coordinate directions.
`       Convert to string for output. Done with triangles.

this is really cool. . . love the symmetry...

this is clearly the most fun answer, but i messed up my problem definition to have static description and "no input", so i have to keep the agreement and award the lowest character count, below (which is also a fun answer but in a different way), the Answer checkmark. thanks for participating.

Ruby, 98106
Fixed error spotted by Reto Koradi.
s=sprintf'%024b',342391
6.times{|i|t='15462315'[i,3];t+=t.reverse;t[1+i%2*3]='07'[i%2];s+=t}
p s.split(//)

Given that coordinates are required, the only corner numbering scheme that made sense seemed to be the one where each corner is the binary representation of its coordinates. That's quite different from the linked question, where various different numbering schemes were tried. In the end I decided to print the coordinates with a dirty hardcode: s is initialised to the string version of 24-bit number000001010011100101110111 whose decimal representation is 342391. Actually with this method of printing coordinates, the numbering of the vertices is flexible, so I may do another answer.
Going round the equator of the cube, we find the vertices 1,5,4,6,2,3 and we can define one triangle for each face from any 3 consecutive numbers on this list (wrapping back to the beginning at the end.) The other triangle on each face is defined by reversing the digits, and substituting the middle digit with 0 or 7 as appropriate.
This gives all the required output, but without any separating characters. To achieve that, I simply convert to an array of characters and print the array, like this (linebreaks inserted to prevent scrolling):
["0", "0", "0", "0", "0", "1", "0", "1", "0", "0", "1", "1", "1", "0", "0",
 "1", "0", "1", "1", "1", "0", "1", "1", "1", "1", "0", "4", "4", "5", "1",
 "5", "4", "6", "6", "7", "5", "4", "0", "2", "2", "6", "4", "6", "2", "3",
 "3", "7", "6", "2", "0", "1", "1", "3", "2", "3", "1", "5", "5", "7", "3"]

Are you sure that the winding order is consistent? Based on my sketch, 1, 5, 4 is CCW, 5, 4, 6 is CW.

@RetoKoradi fixed at a cost of 8 bytes. Thanks. Also, I've realised I may do better with a different numbering scheme.

JavaScript (ES6) 78
alert([...'1010011100101110111:120213756465240426735153410145763236'].join` `)

Sorry but I really don't understand these challenges with no input.

sorry, it was my first golf question. i guess it is too late to change it now...

Better next time. You have my vote anyway.

Haskell, 38 characters
f=mapM(mapM print.show)"⭧勛囃勦⾽仵ᶌﻘꚱ쥎➡˻ì"

Prints the right numbers, separated by a whole lot of junk:
'\''
'\\'
'1'
'1'
'1'
'1'
'1'
'\''
'\''
'\\'
'2'
'1'
'2'
'1'
'1'
...

The cube's diagonal is from (1, 1, 1) to (2, 2, 2).

CJam, 20 characters
"⭧勛囃勦⾽仵ᶌﻘꚱ쥎➡˻ì":isS*

Same idea as my Haskell answer; prints:
1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2 1 2 0 2 1 3 7 5 6 4 6 5 2 4 0 4 2 6 7 3 5 1 5 3 4 1 0 1 4 5 7 6 3 2 3 6

Ruby, Rev 1 62
29.downto(0){|c|p c>5?73888640>>c&1:[c,c^1,c|6,c|6,(c+3)%6,c]}

Got rid of the c-6 by multiplying the magic number by 64.
The assignment of coordinates is below. It's odd that I assigned 100 to number 1. I could have saved a byte in rev 0 by exchanging the axes and assigning 001 to number 1. The reason it was that way was because originally I had up counting in the loop, which would have meant I had to put everything in reverse in the magic string. Anyway, with the change I've made now, there's no additional saving to be made, so i'll leave the coordinates as they are
Cube rotated with 0163 face at back
Top layer from above
01   000 100
74   010 110
Bottom layer from above
36   001 101
25   011 111

Ruby, Rev 0 63
29.downto(0){|c|p c>5?1154510>>c-6&1:[c,c^1,c|6,c|6,(c+3)%6,c]}

Using hardcoding of the coordinates data to give flexibility in picking the corners. There are 54 digits in the output, meaning that the naive solution would have 63-54=9 bytes available for code. As I can't think of a way to insert spaces in 9 bytes, I believe this is shorter than the naive solution.
Numbering scheme (adapted from my Ruby answer to the linked question https://codegolf.stackexchange.com/a/48867/15599)
4---7
|  /|
| / |
|/  |
1---0---7
|  /|  /|
| / | / |
|/  |/  |
6---3---2---7
    |  /|  /|
    | / | / |
    |/  |/  |
    6---5---4
        |  /|
        | / |
        |/  |
        6---1

Output
0
0
0
1
0
0
0
1
1
0
0
1
1
1
0
1
1
1
0
0
1
1
1
0
[5, 4, 7, 7, 2, 5]
[4, 5, 6, 6, 1, 4]
[3, 2, 7, 7, 0, 3]
[2, 3, 6, 6, 5, 2]
[1, 0, 7, 7, 4, 1]
[0, 1, 6, 6, 3, 0]

I really like the incorporation of @Runer112 's method

@donbright I was the first one to think of putting the first 6 vertices on the equator and the last 2 on the poles in that previous question, which is why my C answer is the most popular answer. I had the 6 vertices in sequential order. Runer112 deserves some credit for his reordering of the 6 vertices on the equator. I had to modify the face order for Ruby on the previous question, but the vertex order is indeed identical to Runer112's. Phinotphi's alternative reordering of the 6 vertices on the equator would have given me equal length on the previous question, but would be longer on this one

wow awesome... thanks for the detailed explanation... very interesting. i should have allowed input then it would have been a better challenge.


text:
Acronyms can really obviously narrow your message sensors
Because of this, you need a better way of working out if a phrase is an acronym of a word. You also think it would be worthwhile to see if the phrase and word in question are recursive acronyms.
Your task:
Given a word and then a phrase separated by a line, output if the phrase is an acronym and then if it is a recursive acronym. (The phrase contains what it stands for)

The input will compose of alphabetical characters as well as spaces.
Your program shouldn't be case sensitive.

Example Input/Output:
Case 1:
Input:
Acronyms
Acronyms can really obviously narrow your message sensors

Output:
True
True

Case 2:
Input:
FAQ
frequently asked questions

Output:
True
False

Case 3:
Input:
foo
bar baz

Output:
False
False

Case 4:
Input:
GNU
GNU is not Unix

Output:
False
False

Case 5:
Input:
Aha
A huge Aha

Output:
True
True

Acronyms Can Recurse? Oh! Now You're Making Sense.

Do the newlines need to be present in the output?

No, just as long as it's clear what the output is

This reminds me of an XKCD: http://xkcd.com/917

Related.

New test case: Lolcat: Laughing over lolcat captions and tearing.  Is this True/True or do recursive acronyms need to recurse at the first or last word?

Yes it is True/True.

ABCDE: Another basic clearly defined example.

What should be the output for GNU: Gnus nettle unicorns?

True False. That probably breaks some stuff doesn't it? Let's say that case doesn't matter.

This reminds me of the Contracrostipunctus from Douglas Hofstadter's Gödel, Escher, Bach, which contains the acrostic "Hofstadter's Contracrostipunctus Acrostically Backwards Spells 'J.S. Bach'."

You should add the example PHP -> PHP Hypertext Preprocessor, since that's a real acronym.

Pyth, 19 18
&pqJrz0hCKcrw0)}JK

This prints the result in a rather odd format, like: TrueFalse.
You can try it online or run the Test Suite.
Explanation:
&pqJrz0hCKcrw0)}JK      :
    rz0    rw0          : read two lines of input, and convert each to lower case
          c   )         : chop the second input on whitespace
   J     K              : store the first line in J and the chopped second line in K
  q    hC               : zip K and take the first element, check if it is the same as J
 p                      : print and return this value
&              }JK      : and the value with whether J is in K, implicit print

Python 3, 89
Saved a bunch of bytes thanks to SOPython.
a=input().lower()
d=input().lower().split()
h=tuple(a)==next(zip(*d))
print(h,h&(a in d))

The most complicated part of this solution is h=tuple(a)==next(zip(*d)).
This unpacks the list d into zip and then calls next to return a tuple of the first element of each iterable passed into zip which is then compared against a tuple of each letter in a (tuple(a)).

You can save 7 bytes by substituting [0]==l  for .startswith(l).

CJam, 21 20 bytes
qeuN/)S/_:c2$s=_p*&,

Try this fiddle in the CJam interpreter or verify all test cases at once.
How it works
qeu                  e# Read from STDIN and convert to uppercase.
   N/                e# Split at linenfeeds.
     )S/             e# Pop the second line form the array.
      S/             e# Split it at spaces.
        _:c          e# Push a copy and keep on the initial of each word.
           2$s       e# Push a copy of the line array and flatten it.
                     e# This pushes the first line.
              =      e# Check for equality.
               _p    e# Print a copy of the resulting Boolean.
                 *   e# Repeat the word array 1 or 0 times.
                  &  e# Intersect the result with the line array.
                   , e# Push the length of the result (1 or 0).

Scala, 135 110 108 bytes
val Array(x,y)=args.map(_.toLowerCase)
val z=y.split(" ").map(_(0)).mkString
print(z==x,z==x&&y.contains(z))

Saved a few bytes by using command line arguments (thanks to J Atkin for the hint), putting the booleans out as a tupel, using mkString instead of new String and print instead of println.
EDIT:
Misinterpreted the question, and had to reimplement the solution

Haskell, 81 80 bytes
import Data.Char
f[a,b]|c<-words b=(a==map(!!0)c,elem a c)
p=f.lines.map toLower

The output format is not strictly defined, so I return a pair of booleans, e.g. p "Aha\na huge arm" -> (True,False).

Today I learned of pattern guards (<-)—thanks!

Python 3, 106 bytes
Well, at least it beat Scala ;)
x=input().lower()
y=input().lower().split()
g=all(x[i]==y[i][0]for i in range(len(y)))
print(g,g&(x in y))

@muddyfish Possibly more explanation of each examples would prevent this from happening to other people.

Would more time in the sandbox have helped? In my (obviously rather limited) experience of it, you only get responses whilst it's nearly at the top

@muddyfish Well I don't know how long you left it so, I don't know

I left it there for about a day

@muddyfish A week is the recommended norm

AppleScript, 302 301 297 293 Bytes
Aw, hell yeah. Not even bothered that I lose, this is competitive for AppleScript.
set x to(display dialog""default answer"")'s text returned
set y to(display dialog""default answer"")'s text returned's words
set n to y's items's number
repeat n
try
if not y's item n's character 1=(x as text)'s character n then return{false,false}
end
set n to n-1
end
return{true,x is in y}
Outputs as:
{true, false}
Or whatever the answer happens to be.

Ruby, 77 74 bytes
b=gets.chop.upcase
a=gets.upcase
p c=a.scan(/\b\w/)*''==b,c&&a.include?(b)

PHP, 120 bytes
Not being case sensitive is a lot of weight (26 bytes). Passed all test cases:
foreach($c=explode(' ',strtolower($argv[2]))as$l)$m.=$l[0];var_dump($x=$m==$a=strtolower($argv[1]),$x&&in_array($a,$c));

Outputs two bool values in this form:
bool(true)
bool(false)

Reads two arguments from the command line, like:
a.php Acronyms "Acronym can really obviously narrow your message sensors"

Ungolfed
$acronym = strtolower($argv[1]);
$words = strtolower($argv[2]);
$words = explode(' ', $words);

foreach($words as $word) {
    $letters .= $word[0];
}

$isAcronym = $letters == $acronym;

var_dump(
    $isAcronym,
    $isAcronym && in_array($acronym, $words)
);

Ruby, 52 bytes
p !!gets[/^#{x=gets.scan(/\b\w/)*""}$/i],!! ~/#{x}/i

Example:
$ echo "Aha
A huge AHA" | ruby acronym.rb
true
true

Matlab, 90 bytes
function z=f(r,s)
z=[sum(regexpi(s(regexpi(s,'(?<=(\s|^))\S')),r))>0 nnz(regexpi(s,r))>0];

Example (note that Matlab displays true/ false as 1/ 0):
>> f('Aha', 'A huge Aha')
ans =
     1     1

JavaScript ES6, 95 92 bytes
(a,b)=>[(r=eval(`/^${a}$/i`)).test((s=b.split` `).map(c=>c[0]).join``),s.some(c=>r.test(c))]

Input both strings as parameters. Outputs an array with two values: one for each boolean.

I wouldn't have thought of using a regex in place of .indexOf. Nice work! Perhaps r=eval(`/^${a}$/i`) would work in place of your current r setup.

@ETHproductions And I in turn wouldn't have thought of eval as a RegExp object shortener. Thanks for the tip!

GNU sed, 118 bytes
Requires -r flag, included in score as +1.  Note that I'm using \b for a word-boundary match, even though I can't find this documented in GNU sed.  It Works For Me...
N
h
s/^(.*)\n.*\b\1\b.*/True/i
/\n/s/.*/False/
x
:
s/(.)(.*\n)\1[^ ]* ?/\2/i
t
/../s/.*/False/
/F/h
/F/!s/.*/True/
G

Expanded:
#!/bin/sed -rf

N
h

# Is it recursive?
s/^(.*)\n.*\b\1\b.*/True/i
# If no replacement, there's still a newline => false
/\n/s/.*/False/

x

# Is it an acronym?
# Repeatedly consume one letter and corresponding word
:
s/(.)(.*\n)\1[^ ]* ?/\2/i
t
# If more than just \n remain, then false
/../s/.*/False/
# And falsify recursive, too
/F/h
# !False => true
/F/!s/.*/True/

G

Groovy, 91 bytes
a=args*.toLowerCase()
println([a[1].split()*.charAt(0).join("")==a[0],a[1].contains(a[0])])

Output format is  [bool, bool].This takes it's input from the command line args.

Lua 5.3, 182 bytes
a=""b=io.read c=a.lower d=a.reverse e=d(c(b()))f=~e:len()h=a.sub g=d(c(b()))for m in g:gmatch"[^ ]+"do f=-~f if h(e,f,f)~=h(m,~0)then break end k=k or m==e end f=f>~1print(f,f and k)

R, 93 bytes
a=tolower(readLines(,2));cat(a[1]==gsub("([^ ])\\w* ?","\\1",a[2]),a[1]%in%scan(t=a[2],w=""))

Usage:
> a=tolower(readLines(,2));cat(a[1]==gsub("([^ ])\\w* ?","\\1",a[2]),a[1]%in%scan(t=a[2],w=""))
Aha
A huge Aha
Read 3 items
TRUE TRUE
> a=tolower(readLines(,2));cat(a[1]==gsub("([^ ])\\w* ?","\\1",a[2]),a[1]%in%scan(t=a[2],w=""))
Acronyms
Acronyms can really obviously narrow your message sensors
Read 8 items
TRUE TRUE
> a=tolower(readLines(,2));cat(a[1]==gsub("([^ ])\\w* ?","\\1",a[2]),a[1]%in%scan(t=a[2],w=""))
FAQ
frequently asked questions
Read 3 items
TRUE FALSE
> a=tolower(readLines(,2));cat(a[1]==gsub("([^ ])\\w* ?","\\1",a[2]),a[1]%in%scan(t=a[2],w=""))
foo
bar baz
Read 2 items
FALSE FALSE

awk 137 bytes
awk 'BEGIN{T="True";F="False"}NR*NF<2{a=tolower($1)}END{for(i=1;i<=NF;i++)b=b substr(tolower($i),1,1);print(a==b?T:F)"\n"(a==tolower($1)?T:F)}'

Initialize T="True";F="False" to simplify output.
NR*NF<2{a=tolower($1)}: set a only if the first line only has one field.
END{...}: assuming only two lines...

for(i=1;i<=NF;i++)b=b substr(tolower($i),1,1): construct recursive acronym.
print(a==b?T:F)"\n"(a==tolower($1)?T:F): print the output of both comparisons, a==b and a==tolower($1).

If anyone knows how to optimize the recursive acronym construction, feel free to suggest.

SpecBAS - 144 bytes
1 INPUT a$,b$: LET a$=UP$(a$),b$=UP$(b$),d$="": DIM c$(SPLIT b$,NOT " ")
2 FOR EACH w$ IN c$(): LET d$=d$+w$(1): NEXT w$
3 TEXT d$=a$'POS(a$,b$)>0

Converting the 2 x inputs to uppercase saves characters vs. lowercase conversion. Can now have multiple assignments done in one LET statement, which also helps. And TEXT saves one character over PRINT.
Uses 1/0 to show true/false (the apostrophe just moves output to the next line).

Perl5, 90 bytes
($a,$b)=map{chomp;lc}<>;print((join"",map{substr($_,0,1)}split/ /,$b)ne $a?0:($b=~$a?2:1))

cheating a bit: 0 = all false, 1 = one true, 2 = both true. I'm not a golfer, but am upset perl is missing while browsing!
($a,$b)=map{chomp;lc}<>;              # get the two lines as lowercase
print((                               #
join"",map{substr($_,0,1)}split/ /,$b # collapse first letters of secondline
     ) ne $a  ? 0 : ( $b=~$a ? 2 : 1))# 0 nothing, 1 not recursive, or 2

JavaScript (ES6), 89 96 95 bytes
(a,b)=>[p=(a=a[l='toLowerCase']())==(c=b[l]().split` `).map(x=>x[0]).join``,p&&c.some(x=>x==a)]

Shucks...I thought I had it all sorted out, but apparently I was wrong.
This defines an anonymous function which takes input as two strings, and returns and array of two boolean items. The first item is calculated by comparing the the first string in all lowercase with the first char of each word in the second string. The second item is calculated simply by checking if the second string contains the first.
Here's another solution for the second item; 2 bytes shorter, but very few browsers support it:
p&&c.includes(a)

Checking if the second string contains the first fails for GNU: Gnus nettle unicorns

Please check again: tried it and does not even work: ReferenceError: l is not defined (missing l= before toLowerCase)

... fixed that bug, it fails for 'GNU','GNU is not unix' (test case 4) should be false, false

@edc65 Shucks, I erased the l= while looking for a bug and forgot to put it back. Thanks for bringing that up! The other test case should be fixed as well.

JavaScript (ES6) 93
(w,s)=>s[L='toLowerCase'](w=w[L](z=y='')).replace(/\w+/g,v=>y+=v[z=z||v==w,0])&&[y=y==w,y&&z]

Test running the snippet below in any EcmaScript 6 compliant browser

f=(w,s)=>s[L='toLowerCase'](w=w[L](z=y='')).replace(/\w+/g,v=>y+=v[z=z||v==w,0])&&[y=y==w,y&&z]

// TEST

out=x=>O.innerHTML+=x+'\n';

;[
 ['Acronyms', 'Acronyms can really obviously narrow your message sensors', true, true]
,['FAQ', 'frequently asked questions', true, false]
,['foo', 'bar baz', false, false]
,['GNU', 'GNU is not Unix', false, false]
,['Aha', 'A huge Aha', true, true]
,['Lolcat', 'Laughing over lolcat captions and tearing.', true, true]
,['ABCDE', 'Another basic clearly defined example.', true, false]
,['GNU', 'Gnus nettle unicorns', true, false]
,['PHP', 'PHP Hypertext Preprocessor', true, true]
].forEach(([a,b,c,d]) => (
  [r,s]=f(a,b),
  out(((r==c && s==d)?'OK ':'KO ') + a + ',' + b + ' -> ' + f(a,b))
))

Pyke (was untitled when posted), (noncompetitive), 20 bytes
l1c"jFh)J"iQl1qDji{&

You can find the source code here, language is completely unstable (first test challenge for it) so don't expect it to work in the future (commit 8)
Or 18 bytes (stableish)
l1idcmhsRl1jqDji{&

Try it here!

Jelly, 13 bytes
ŒlḲḢ€⁼ɗ,wɗ/«\

Try it online!
Takes input as a pair [phrase, word]. +2 bytes to input as a newline separated pair with the word first
If the inputs were always in a single case, then this much more elegant program would work for 9 bytes.
This outputs the pair [a, b], where a and b are truthy values (1) or falsey values (0). The Footer in the TIO link runs the code over each test case.
How it works
ŒlḲḢ€⁼ɗ,wɗ/«\ - Main link. Takes [phrase, word] on the left
Œl            - Convert both to lowercase
         ɗ    - Group the previous 3 links into a dyad, f(phrase, word):
      ɗ       -   Group the previous 3 links into a dyad, g(phrase, word):
  Ḳ           -     Split the phrase on spaces
   Ḣ€         -     Take the first characters of each word
     ⁼        -     Does this equal the word?
        w     -   Index of word as a sublist of phrase, or 0 if not found
       ,      -   Pair; Yield [g(phrase, word), index]
          /   - Reduce [phrase, word] by f, yielding f(phrase, word)
           «\ - Scan by minimum

It is possible for word to be a sublist of phrase, but not an acronym (for example, [GNU is not Unix, GNU]. In this case, f returns [0, 1] which isn't a valid output. Additionally, w returns a non-zero integer, rather than 1/0, any we want to turn this into 1.
Therefore, we scan f's return by « (minimum), which transforms it:
[g(phrase, word), index] «\ = [g(phrase, word), min(g(phrase, word), index)]

This zeros out any trailing 1s, and converts [1, x] (where x > 0) into [1, 1]

AWK, 107 bytes
$0=tolower($0){a="True"}b{for(c="False";$++d;e+=b==$d)f=f substr($d,1,1);$0=(b==f?a:c)"\n"(e?a:c)}!b{b=$1}f

Try it online!
Here's a different take using GAWK...  The code defines four conditions with associated code blocks.  The order they are evaluated when each line is read in matters in this case, to save a couple of characters.
The first condition,
$0=tolower($0)

is always true given the possible inputs.  The check is really unimportant here, the side effect of translating the input line to lowercase it what we care about.  The code run just sets variable a to the string True to shorten the code.
{a="True"}

The second condition,
b

is true only for the second input line, since b isn't set until the first line is processes.  So it's essentially a shortcut for NR>1.
{for(c="False";$++d;e+=b==$d)f=f substr($d,1,1);e=e?a:c;$0=(b==f?a:c)"\n"e}

The code block is two statement, first a for loop that processes each word in the input stream.  The top of loop statement,
c="False"

is just setting up c as a shortcut for False to save characters.  Putting here saves a character, since the ; is already there.
The "should I iterate" test,
$++d

sets d to the current word and stops when we run off the end of the line.  And the bottom of the loop statement,
e+=b==$d

increments e everytime the current word matches the acronym from the first line (which is in b).
Finally, the body of the loop appends the first character of the current word to f, which will end up being the acronym associated with the line.
f=f substr($d,1,1)

Once the loop is done, the output $0 is set by concatenating two ternary.
$0=(b==f?a:c)"\n"(e?a:c)

The (b==f?a:c) part is True or False depending on whether or not the provided and constructed acronyms match.  And the second part,
(e?a:c)

is True or False based on how many words in the second line matched the acronym from the first line.
The third condition applied to each line just sets b to the value of the first line, setting b only if is hasn't been set already.
!b{b=$1}

And the last condition is true only after the second line has been processed.
f

It uses the default action for unspecified code block.  So it's a shortcut for NR>1{print$0}.
One caveat: I'm not 100% clear on the rules of the contest.  If the second condition depends on the first, meaning only valid acronyms can be recursive acronyms, this slightly longer version is necessary.
$0=tolower($0){a="True"}b{for(c="False";$++d;e+=b==$d)f=f substr($d,1,1);$0=(g?a:c)"\n"(e&&(g=b==f)?a:c)}!b{b=$1}f