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

I came across this question on SO and thought it'd make a nice golf challenge. So here it is:

Challenge:

Write a program that reads a sequence of character strings, one per line, and outputs a list of all positions where each string has the same character.

Input and output:

The input consists of one or more lines of printable non-whitespace ASCII characters, each followed by a newline. You may assume that all input lines have the same length. The newline is not to be considered part of the input (i.e. you should not output it as a matching character).

Example input (shamelessly stolen from the SO question):

abcdefg
avcddeg
acbdeeg

After reading the input, your program should print the positions of each matching column and the characters they contain. (Your program may, but need not, stop reading further input if it can determine early that there are no matching columns.) Any reasonable output format is permitted; in particular, you may use either 0-based or 1-based indexing for the positions.

Example output for the above input (using 0-based indexing):

0: a
3: d
6: g

Scoring:

This is code golf, so shortest answer wins. In the event of a tie, fractional tie-breaker chars may be awarded for additional features:

  • −½ chars for correctly handling input lines of unequal length. (Output should not contain positions past the end of the shortest input line.)
  • −¼ chars for correctly handling input consisting of arbitrary UTF-8 encoded Unicode characters.

For inspiration, you may find some ungolfed solutions at the SO question (see above).

Clarifications:

  • Simply concatenating the positions and characters, as in 0a3d6g, does not count as "reasonable output". You should provide some kind of separator (such as a space) between each element of the output so that it can be parsed unambiguously.

  • The input will be provided on the standard input stream (stdin), or using whatever text file input mechanism is most natural to your language of choice. (If your chosen language doesn't have a natural mechanism for file input, do whatever seems closest in spirit.)

  • The input ends when there is no more data to be read (i.e. when an end-of-file condition occurs). If you wish, you may require that the input be terminated by a blank line (which you then should not count as part of the input, obviously). If you do so, please mention it in your answer so that others can provide correct input for testing.

  • Every input line, including the last one, ends with a newline character. Your answer must not report this newline as a matching column. (It's fine if your solution can also handle input where the last line doesn't end in a newline, but that's not required.)

share|improve this question
    
So does a blank line terminate input? –  Steven Rumbalski Jan 17 '12 at 15:52
    
"You should provide some kind of separator between each element of the output so that it can be parsed unambiguously." Does a space count as a seperator? –  Steven Rumbalski Jan 17 '12 at 16:03
    
@StevenRumbalski: The input ends when there's no more data to read; I guess I can allow a trailing blank line if your language has trouble detecting EOF. And yes, a space is a perfectly good separator. –  Ilmari Karonen Jan 17 '12 at 16:44
    
Can we have some arbitrary UTF-8 encoded Unicode characters sample code? –  user unknown Jan 18 '12 at 2:18

21 Answers 21

up vote 11 down vote accepted

APL, 25 characters

∩/{0=⍴⍵:⍬⋄(⊂⍵,⍨¨⍳⍴⍵),∇⍞}⍞

I used Dyalog APL (version 13) as my interpreter. It handles both inputs of unequal length and Unicode (UTF-8) characters.

Examples:

      ∩/{0=⍴⍵:⍬⋄(⊂⍵,⍨¨⍳⍴⍵),∇⍞}⍞
abcdefg
avcddeg
acbdeeg

  1 a  4 d  7 g  

      ∩/{0=⍴⍵:⍬⋄(⊂⍵,⍨¨⍳⍴⍵),∇⍞}⍞
test日本
blat日本国foo

  4 t  5 日  6 本 

Explanation, somewhat from right to left:

  • The main chunk of this answer is the direct function (basically, anonymous function), defined within the curly braces. Its right argument is specified by .
    • 0=⍴⍵:⍬ is our first expression, and it checks if we've gotten an empty line (i.e., we are done). It uses a guard (a familiar construct to many functional programmers) to conditionally execute the expression to the right of the colon. In this case, if 0 is equal to the shape/length () of the right argument, we return the empty set ().
    • separates the two expressions within the function. If the previous expression didn't get evaluated (and thus didn't return anything), we move to the next expression.
    • We recursively call the function using the self-reference function (). The argument to the function is a line of non-evaluated user input, given by quote-quad ().
    • ⊂⍵,⍨¨⍳⍴⍵ creates pairs for each character in the string, where each pair's first element is its position in the string, and its second element is the character.
    • ⍳⍴⍵ gives a vector from 1 to ⍴⍵, or the length of the input string.
    • ⍵,⍨¨ applies the commuted concatenation function (,⍨) to each (¨) element to its left (, in this case the user's input) and right. Commuting the concatenation function causes its left and right arguments to be swapped.
    • Finally, we enclose the result using , so that we can differentiate between lines of input.
  • We initially feed our function with user input ().
  • Finally, we reduce (/) our resulting vector of vectors of pairs using the intersection function (), yielding the pairs that are found in all of the sub-vectors.
share|improve this answer
    
For no good reason I have a visceral negative response whenever I see APL that I don't have for J or GolfScript. But +1 anyway for an excellent solution. –  Steven Rumbalski Jan 20 '12 at 1:01
    
I've actually been thinking about switching to J... I'll tack that on my list of reasons. :) –  Dillon Cower Jan 21 '12 at 2:35

Golfscript (28 chars)

n/zip:^,,{.^=.&.,1>{;;}*}%n*

There are character set issues when piping Unicode through, so no quarter-point bonus.

share|improve this answer
1  
+1. This should not have less upvotes than my answer. –  Steven Rumbalski Jan 19 '12 at 16:49

J, 57 51 44 40 characters

,.&.>y;y{{.z[y=.I.*/2=/\]z=.];._2]1!:1]3

I'm getting there slowly but surely. This is still far from ideal though I think.

I felt sure that using a hook would be the answer but unfortunately not (44 chars):

,.&.>((];({{.)~)([:I.[:*/2=/\]))];._2]1!:1]3

I may need a completely different method to get any shorter.

share|improve this answer
1  
+1. But yes, I expect better from J. –  Steven Rumbalski Jan 17 '12 at 18:54
    
This should not have less upvotes than my answer. –  Steven Rumbalski Jan 19 '12 at 16:49
1  
@StevenRumbalski The upvotes don't always reflect the relative sizes of the code. It sometimes becomes a language popularity contest. I agree that the golfscript answer should be up there with the APL, unfortunately I've already given it my upvote and can't help push it up further. –  Gareth Jan 19 '12 at 17:05

Haskell, 64 characters

main=interact$show.foldl1(filter.flip elem).map(zip[0..]).lines

Handles lines of unequal length. Unicode support depends on the current locale settings.

Example output:

[(0,'a'),(3,'d'),(6,'g')]
share|improve this answer
    
+1. This should not have less upvotes than my answer. –  Steven Rumbalski Jan 19 '12 at 16:49

Python 2, score 81.5 (116 94 86 83 82 bytes minus bonus)

import sys
i=0
for x in zip(*sys.stdin)[:-1]:
 i+=1
 if len(set(x))<2:print i,x[0]
share|improve this answer
    
+1 for a nice Python golf but You can lose a whole FOUR characters: [:-1] isn't necessary unless to strip off an extraneous newline at the end of the input (which does not even seem to be there in the question). –  ChristopheD Jan 17 '12 at 22:41
    
@ChristopheD: Actually, the result of zip(*sys.stdin) is [('a', 'a', 'a'), ('b', 'v', 'c'), ('c', 'c', 'b'), ('d', 'd', 'd'), ('e', 'd', 'e'), ('f', 'e', 'e'), ('g', 'g', 'g'), ('\n', '\n', '\n')]. I don't see a way around avoiding stripping that last tuple of newlines. Please correct me if I've misunderstood. Thank you for the upvote. –  Steven Rumbalski Jan 17 '12 at 22:48
    
If you remove the last newline in your data file the tuple for that line isn't complete (misses one '\n' so zip only considers and returns the data we are looking for, allowing the removal of [:-1]. E.g. zip([1,2,3,4],[1,2,3])=> [(1, 1), (2, 2), (3, 3)] –  ChristopheD Jan 17 '12 at 23:08
    
@ChristopheD: Per spec, "input consists of [...] lines [...], each followed by a newline." –  Ilmari Karonen Jan 18 '12 at 10:24
1  
Would the person who downvoted this answer explain why? –  Steven Rumbalski Jan 18 '12 at 18:53

(Bash) Shell Scripting, 105 characters

If anyone has some more tricks for this, please fill free to comment!

for((i=1;i<`tail -1 $1|wc -c`;i++))do
x="cut -c$i $1";y=`$x`;[ `$x|uniq|wc -l` = 1 ]&& echo $i ${y:3};done

Result:

1 a
4 d
7 g
share|improve this answer
    
I'm having trouble getting this to work; running this on the sample input prints a series of errors like /tmp/cols.sh: line 2: [1: command not found and nothing else. –  Ilmari Karonen Jan 18 '12 at 15:47
    
@Ilmari Karonen: this was tested on a Mac (snow leopard, 10.6.2) but should work elsewhere. I'see to have it fixed on Linux tomorrow (should be a small fix) –  ChristopheD Jan 18 '12 at 17:23
2  
ormaaj lacked the rep but wanted to comment: it breaks for Ilmari because of a missing space after the [; and the ${y:3} will cause it to only work with exactly 3 lines of input. Fixing and optimising yields (100 chars) while((++i%`tail -1 $1|wc -c`));do x=`cut -c$i $1`;((`uniq|wc -l`==1))<<<"$x"&&echo $i ${x: -1};done and using default values should allow saving one more with for((;++i<`tail -1 $1|wc -c`;))do but there is an unfixed bug in bash. –  Peter Taylor Feb 12 '12 at 8:08

Perl, 87 characters (−½ char tie-break bonus)

Here's a golfed version of my own solution from the SO thread:

chomp($a=$b=<>);$a&=$_,$b|=$_ for<>;@$_=$$_=~/./sgfor a,b;$b[$i++]eq$_&&say"$i:$_"for@a

Unlike the SO version, this one uses 1-based indexes for the output. It uses the Perl 5.10 say feature, so needs to be run with perl -M5.010 (or with perl -E).

Like the SO version, this code handles variable-length lines, and would handle arbitrary Unicode input if the standard input and output were in UTF-8 mode. Alas, by default they're not, unless one specifies the non-free -CS command line switch. Thus, it earns the −½ char bonus, but not the −¼ one.

Edit: +1 char to fix a bug: just because the input strings don't contain line feeds doesn't mean they can't end up in $a (e.g. "+" & "J" eq "\n").

share|improve this answer
1  
You could save 1 char by using chop instead of chomp. –  M42 Jan 18 '12 at 15:11
    
@M42: Good point, although I rather like the robustness of the current version. I think I'll keep the m for now, it's not like it makes any difference to the rankings at the moment. :) –  Ilmari Karonen Jan 18 '12 at 15:24

T-SQL

SELECT N.number, letter = MIN(SUBSTRING(L.line, N.number, 1))
FROM Lines AS L
INNER JOIN master.dbo.spt_values AS N ON N.type = 'P'
WHERE N.number BETWEEN 1 AND (SELECT MAX(LEN(L2.line)) FROM Lines AS L2)
GROUP BY N.number
HAVING COUNT(DISTINCT SUBSTRING(L.line, N.number, 1)) = 1
ORDER BY N.number
share|improve this answer
    
+1 for unconventional language choice. –  Ilmari Karonen Feb 10 '12 at 13:42

Scala 115107: (−¼ for handling UTF-8)

io.Source.stdin.getLines.map(_.zipWithIndex).toList.flatten.groupBy(_._2).map(_._2.toSet).filter(_.size==1)

ungolfed, and Source.fromFile ("f") instead of stdin for better testability:

io.Source.fromFile ("f").
  getLines.map (_.zipWithIndex).
    toList.flatten.groupBy (_._2). 
      map (_._2.toSet).
        filter (_.size==1)

Result:

List(Set((a,0)), Set((g,6)), Set((d,3)))

Thanks to Gareth for the reduction of size 8 for using stdin.

share|improve this answer
    
Can't you use stdin instead of fromFile("f") to save 8 characters? –  Gareth Jan 18 '12 at 13:00
    
Thanks. Implementation done. –  user unknown Jan 18 '12 at 13:20

Q, 32

{a!((*:)x)a:(&)1=(#:')(?:')(+)x}

usage

q){a!((*:)x)a:(&)1=(#:')(?:')(+)x}[("abcdefg";"avcddeg";"acbdeeg")]
0| a
3| d
6| g

K, 22

The above solution can be reduced to 22 by writing it completely in K rather than passing K functions to a Q interpreter, reducing the number of parentheses required.

{a!@[*x]a:&1=#:'?:'+x}
share|improve this answer

PHP, 123 127 :(

I'm not happy with it (there's bound to be improvements to be had), but here goes:

<?$a=$b=trim(fgets(STDIN));while($l=fgets(STDIN)){$a&=$l;$b|=$l;}$n=-1;while(@$a[++$n]){echo$a[$n]!=$b[$n]?'':"$n:{$a[$n]}\n";}

Proof it works.

If anyone can think of a more clever way of initializing $a and $b, please let me know. Originally I had $a=$b=$n='' and $b eventually was correct, but [empty] & [anything] == [empty], so $a never had content.


Edit: Had to fix newline handling (+6) but dropped closing tag (-2).

share|improve this answer
    
I'm curious, why do you make most of your answers community wiki? –  Gareth Jan 17 '12 at 17:55
    
I didn't mean to on this one. Long time ago when I first joined CodeGolf someone told me that it was standard. Have to break the habit. Can un-wiki it now though. codegolf.stackexchange.com/a/2249/1419 (see comments) –  GigaWatt Jan 17 '12 at 18:20
    
I think it was the standard way of doing things on SO for code golf questions, but not here otherwise no-one would have any reputation at all. :-) –  Gareth Jan 17 '12 at 18:32
    
You could probably flag them and ask a moderator to un-CW them. Just explain that it was a mistake. –  Ilmari Karonen Jan 17 '12 at 18:35
    
You could save two chars by leaving out the ?>. However, I just noticed that your code has a bug: it prints an extra match if all lines contain a trailing newline as specified. –  Ilmari Karonen Jan 17 '12 at 20:17

JavaScript (125 134 140)

for(i=s=[];I=s[++i]=prompt(o='');S=I);for(c=-1;w=r=++c<S.length;o+=r?c+':'+C+'\n':'')for(C=S[c];w<i;)r&=s[w++][c]==C;alert(o)

Demo: http://jsfiddle.net/Fv7kY/4/

Edit 1: Rearrange loops to avoid braces. Initialize i with [] to combine with s. Move w increment into expression.

Edit 2: Set S=I to capture last entered word and save using s[1]. Combine r=1 and ++c<S.length. Set C=s[c] in inner loop and compare to C instead of previous and next words to shorten expression s[w][c]==s[w++][c] to just s[w++][c]==C. Saved a total of 9 characters. Also set w=r=... because when that's true w=1 which is what we need to initialize w with.

share|improve this answer

Ruby (71)

a,*s=*$<.lines
(a.size-1).times{|i|s.all?{|t|t[i]==a[i]}&&p([i,a[i]])}

output:

[0, "a"]
[3, "d"]
[6, "g"]
share|improve this answer
    
Note: appears to require Ruby 1.9; for Ruby 1.8 compatibility, replace t[i] with t[i,1]. –  Ilmari Karonen Jan 19 '12 at 16:58

Common Lisp, 183 165 characters

(let((l(loop for m =(read-line)until(equal m "")collect m)))(loop for c across(car l)for i from 0 if(null(remove c(mapcar(lambda(y)(char y i))l)))collect(list i c)))

Readable format:

(let ((l (loop for m = (read-line) until (equal m "") collect m)))
  (loop for c across (car l)
        for i from 0 
        if (null (remove c 
                         (mapcar (lambda(y) (char y i))l)))
        collect(list i c)))

Enter this directly into the REPL and enter lines, terminating with an empty line.

share|improve this answer

Bash, 133 130

(edit: backticks are shorter but ugly as sin. Suggest running the ungolfed version because various unquoted things for golfing are way too dangerous for my tastes.)

Extended globbing required. Disabled pathname expansion, $TMPDIR on a tmpfs, and a recent Bash version recommended. Not recommended in environments without forkbomb countermeasures.

This takes input on stdin and produces two space-separated columns on stdout. Input columns are 0-indexed. It should handle UTF-8, but I expect it will probably fail with unequal lines.

f()case `cut -c1` in ''):;;+(`head -c1 $x`?(?)))echo ${n:=0} `head -c1 $x`;&*)((n++));cut -c2- $x|f;;esac<<<"`<$x`";x=/dev/fd/0 f

Ungolfed:

#!/usr/bin/env bash

shopt -s extglob lastpipe
FUNCNEST=50 # increase for larger inputs

f() {
    case $(cut -c1) in
        '')
            return
            ;;
        +($(head -c1 $x)?(?)))
            echo "${n:=0} $(head -c1 $x)"
            ;&
        *)
            ((n++))
            cut -c2- $x | f
    esac
} <<<"$(<$x)"

x=/dev/fd/0 f

It doesn't beat out ChristopheD's nice arithmetic-for solution as I had hoped, but accomplished my goal of a single tail-recursive function.

  • Since herestrings use temporary files, every call to f expands stdin into a new herestring that can be effectively seeked back to zero within the case command by simply duping /dev/stdin.
  • cut -c1 grabs the first column that's tested against the case patterns.
  • If the pattern matches empty, return.
  • If head -c1 matches every 2nd character (skipping newlines) then both output the current column, the first character of the stdin, and continue executing the next code block regardless of whether it's pattern matches (the ;& operator).
  • If none of the above matched (or the previous case matched), increment the column counter (n), and pipe the remaining columns to another call to f.

In a nutshell, it's your basic cons cell traversal pattern except operating on entire columns at once.

share|improve this answer

C, 126 chars

char a[999],b[999];main(i){for(gets(a);gets(b);)for(i=0;b[i];++i)a[i]^b[i]?a[i]=0:0;
while(i--)a[i]&&printf("%d:%c\n",i,a[i]);}

I've been staring at this but I just can't make it smaller. A new approach may be needed.

(No bonus points; it only handles differently-sized lines if the first line is the shorter one.)

share|improve this answer

VBA (307.25 284 - 0.75 bonus = 283.25)

I know this has already been won, but here's my shot (not reading a file, just a string - needs to have the io added). I like that I got to use l() recursively. I usually don't have a need for recursion my real-life programming. I only did so much testing, but I believe this covers the unicode bonus point stipulation. It also assumes vbCr is the line terminator. This may not translate to all systems because of that.

Code:

Function a(i)
b=Split(Left(i,Len(i)-1),vbCr):c=UBound(b):For q=1 To Len(b(c)):d=Mid(b(c),q,1):If l(b,c,q,d) Then a=a & q & ": " & d & vbCr:Next
End Function
Function l(m, n, o, p)
If n+1 Then l=IIf(o<=Len(m(n)),Mid(m(n),o,1)=p,0) And l(m,n-1,o,p) Else l=Mid(m(n+1),o,1)=p
End Function

Example input/output:

Debug.Print a("abcdefghijklmnop" & vbCr & "abcdefg" & vbCr & "abcabcghijkl" & vbCr)

1: a
2: b
3: c
7: g
share|improve this answer

Ruby (242)

s = %w{ abcdefg avcddeg acbdeeg aejdjeggd }
cols = []
s.sort{ |a, b| b.size <=> a.size }[0].size.times do |i|
  uneq=true
  l = s[0][i]
  s.each { |w| uneq = false if l != w[i] }
  cols << [l, i] if uneq
end
cols.each { |c| puts c.join('|') }
share|improve this answer
    
The intent of the challenge was to read the lines from standard input. I'm willing to cut some slack for languages (like in-browser JavaScript) where that concept doesn't really exist, but Ruby does have STDIN (or ARGF or just plain gets). –  Ilmari Karonen Jan 18 '12 at 20:36
    
ah okay. But considering STDIN accepts one line, is it to assume something like: "Enter in another line, or 'n' to stop"? Therefore create a loop to build an array. –  agmcleod Jan 19 '12 at 2:00
    
I've added some clarifications to the question. Basically, you should keep reading input lines until your reach end-of-file. –  Ilmari Karonen Jan 19 '12 at 16:33

C#

List<string> strings = new List<string> { "abcdefg", "avcddeg", "acbdeeg", "aejdjeggd" };
var transposes = from index in Enumerable.Range(0, strings.First().Length)
                 select new string((from s in strings select s[index]).ToArray());
int i = 0;
foreach(string transpose in transposes)
{
   if (transpose.Distinct().Count() == 1)
     Console.WriteLine("{0}: {1}", i , transpose[0]);
   i++;
}
share|improve this answer
1  
Hi, Arjang, and welcome to codegolf.SE! A few comments on your answer: First, since this is a code-golf challenge, you're expected to try to make your solution as short as possible; just to start with, you have some long variable names that you could easily shorten to single characters, and some excess whitespace you could remove. (It's fine to post a readable version of your code along with the "golfed" one, but you should actually post a golfed solution too.) Second, if you read the question carefully, I specified that you should read the strings from standard input, not hardcode them. –  Ilmari Karonen Jan 21 '12 at 18:49

C# with .NET 4 (280)

using c=System.Console;class P{static void Main(){char[]a=c.ReadLine().ToCharArray();int r,i,l=a.Length;m:i=0;n:r=c.Read();if(r>0&&r!=10&&r!=13){if((int)a[i]!=r)a[i]='\0';i++;goto n;}for(;i>0&&i<l;)a[i++]='\0';if(r>0)goto m;for(i=0;i<l;i++)if(a[i]!='\0')c.WriteLine(i+":"+a[i]);}}
  • 1 line, 280 characters
  • Includes all necessary using statements and Main method.
  • Program does not require an empty line at the end, but will accept it
  • Empty lines are ignored
  • Handles input strings of any length.
  • Reserves output until the end (whereas the original answer provided incremental output)

Readable version

    char[]a=c.ReadLine().ToCharArray();
    int r,i,l=a.Length;
    m:
    i=0;
    n:
    r=c.Read();
    if(r>0&&r!=10&&r!=13){
        if((int)a[i]!=r)
            a[i]='\0';
        i++;
        goto n;
    }
    for(;i>0&&i<l;)
        a[i++]='\0';
    if(r>0)
        goto m;
    for(i=0;i<l;i++)
        if(a[i]!='\0')
            c.WriteLine(i+":"+a[i]);

Original answer

using c=System.Console;class P{static void Main(){char[]a;var b=c.ReadLine();a=b.ToCharArray();while(b!=""){for(int i=0;i

  • 1 line
  • 207 characters
  • Includes all necessary using statements and Main method.
  • Program ends when an empty line is entered.
  • Does not handle input strings that are shorter than the first.


Readable version:

    static void Readable()
    {
        char[]a;
        string b=System.Console.ReadLine();
        a=b.ToCharArray();
        while(b.Length>0)
        {
            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] != b[i])
                {
                    a[i] = '\0';
                }
                else
                {
                    System.Console.WriteLine(i+": "+a[i]);
                }
            }
            b=System.Console.ReadLine();
        }
    }

share|improve this answer
    
When I run this on the test input in the challenge, I get 0: a 1: b 2: c 3: d 4: e 5: f 6: g 0: a 2: c 3: d 6: g 0: a 3: d 6: g. The expected output would be 0: a 3: d 6: g. –  Ilmari Karonen Jan 23 '12 at 22:10
    
@Ilmari Ok, but it outputs the columns/characters that are the same after each input line. If you're feeding in a file as the standard input, then the output might seem strange, but if you input manually, I think it makes sense. I will consider how to refactor, though. –  Dr. Wily's Apprentice Jan 23 '12 at 22:13
    
Your solution crashes if any line is longer than the first line. –  Timwi May 9 '12 at 3:37
    
@Timwi Ah...thanks for pointing that out! –  Dr. Wily's Apprentice May 14 '12 at 12:40

python 122 characters:

print("\n".join([str(i)+':'+str(x[0]) for i,x in enumerate(zip(*[tuple(x) for x in input().split()])) if len(set(x))<2]))
share|improve this answer

Your Answer

 
discard

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

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