Longest string challenge
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
Background
- This problem and challenge is inspired by one that used to be given as a challenge to students learning Icon. It was intended to be tried in Icon and another language the student was familiar with. The basic problem is quite simple the challenge and fun part came through the introduction of restrictions. Experience has shown that the original restrictions required some adjustment to bring out the intent of the challenge and make it suitable for Rosetta Code.
- The original programming challenge and some solutions can be found at Unicon Programming TWiki / Longest Strings Puzzle. (See notes on talk page if you have trouble with the site).
Basic problem statement:
- Write a program that reads lines from standard input and, upon end of file, writes the longest line to standard output.
- If there are ties for the longest line, the program writes out all the lines that tie.
- If there is no input, the program should produce no output.
Task
- Implement a solution to the basic problem that adheres to the spirit of the restrictions (see below).
- Describe how you circumvented or got around these 'restrictions' and met the 'spirit' of the challenge. Your supporting description may need to describe any challenges to interpreting the restrictions and how you made this interpretation. You should state any assumptions, warnings, or other relevant points. The central idea here is to make the task a bit more interesting by thinking outside of the box and perhaps show off the capabilities of your language in a creative way. Because there is potential for more variation between solutions, the description is key to helping others see what you've done.
- This task is likely to encourage multiple different types of solutions. They should be substantially different approaches.
Given the input:
a bb ccc ddd ee f ggg
The output should be (possibly rearranged):
ccc ddd ggg
Original list of restrictions:
- 1. No comparison operators may be used.
- 2. No arithmetic operations, such as addition and subtraction, may be used.
- 3. The only datatypes you may use are integer and string. In particular, you may not use lists.
An additional restriction became apparent in the discussion.
- 4. Do not re-read the input file. Avoid using files as a replacement for lists.
Intent of Restrictions
- Because of the variety of languages on Rosetta and the wide variety of concepts used in them there needs to be a bit of clarification and guidance here to get to the spirit of the challenge and the intent of the restrictions.
- The basic problem can be solved very conventionally and that's boring and pedestrian. The original intent here wasn't to unduly frustrate people with interpreting the restrictions, it was to get people to think outside of their particular box and have a bit of fun doing it.
- The guiding principle here should be that when using the language of your choice, try to solve this creatively showing off some of your language capabilities. If you need to bend the restrictions a bit, explain why and try to follow the intent. If you think you've implemented a 'cheat' call out the fragment yourself and ask the reader if they can spot why. If you absolutely can't get around one of the restrictions, say why in your description.
- Now having said that, the restrictions require some elaboration.
- In general, the restrictions are meant to avoid the explicit use of these features.
- "No comparison operators may be used" - At some level there must be some test that allows the solution to get at the length and determine if one string is longer. Comparison operators, in particular any less/greater comparison should be avoided. Representing the length of any string as a number should also be avoided. Various approaches allow for detecting the end of a string. Some of these involve implicitly using equal/not-equal; however, explicitly using equal/not-equal should be acceptable.
- "No arithmetic operations" - Again, at some level something may have to advance through the string. Often there are ways a language can do this implicitly advance a cursor or pointer without explicitly using a +, - , ++, --, add, subtract, etc.
- The datatype restrictions are amongst the most difficult to reinterpret. In the language of the original challenge strings are atomic datatypes and structured datatypes like lists are quite distinct and have many different operations that apply to them. This becomes a bit fuzzier with languages with a different programming paradigm. The intent would be to avoid using an easy structure to accumulate the longest strings and spit them out. There will be some natural reinterpretation here.
- To make this a bit more concrete, here are a couple of specific examples:
- In C, a string is an array of chars, so using a couple of arrays as strings is in the spirit while using a second array in a non-string like fashion would violate the intent.
- In APL or J, arrays are the core of the language so ruling them out is unfair. Meeting the spirit will come down to how they are used.
- Please keep in mind these are just examples and you may hit new territory finding a solution. There will be other cases like these. Explain your reasoning. You may want to open a discussion on the talk page as well.
- The added "No rereading" restriction is for practical reasons, re-reading stdin should be broken. I haven't outright banned the use of other files but I've discouraged them as it is basically another form of a list. Somewhere there may be a language that just sings when doing file manipulation and where that makes sense; however, for most there should be a way to accomplish without resorting to an externality.
- At the end of the day for the implementer this should be a bit of fun. As an implementer you represent the expertise in your language, the reader may have no knowledge of your language. For the reader it should give them insight into how people think outside the box in other languages. Comments, especially for non-obvious (to the reader) bits will be extremely helpful. While the implementations may be a bit artificial in the context of this task, the general techniques may be useful elsewhere.
Contents |
[edit] Ada
How to bypass the restrictions:
- All lines of potential output are stored in an (unbounded) string, named Buffer. On special character (Latin_1.Nul) is used to separate between different lines.
- We can't directly compare the lengths of two strings. So instead, we assign the difference of the lengths to a variable of type Natural (*). If the result is outside of Natural, this raises an exception. If there is no exception, we assign the result to a variable of type Positive (*), which raises an exception if the result is outside of Positive.
(*) Technically, Natural and Positive are not types but subtypes of Integer: Natural ranges from 0 to Integer'Last, Positive from 1 to Integer'Last.
So this is the first solution.
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Text_IO, Ada.Characters.Latin_1;
procedure Longest_String_Challenge is
function "+"(S: String) return Unbounded_String renames To_Unbounded_String;
Separator: constant Character := Ada.Characters.Latin_1.NUL;
procedure Funny_Stuff(B, L: in out Unbounded_String; N: Unbounded_String) is
Nat: Natural;
begin
Nat := Length(N) - Length(L);
declare
Pos: Positive;
begin
Pos := Nat;
B := N;
L := N;
exception
when Constraint_Error => B := B & Separator & N;
end;
exception
when Constraint_Error => null;
end Funny_Stuff;
Buffer: Unbounded_String := +"";
Longest: Unbounded_String := +"";
Next: Unbounded_String;
begin
while True loop
Next := + Ada.Text_IO.Get_Line;
Funny_Stuff(Buffer, Longest, Next);
end loop;
exception
when others =>
for I in To_String(Buffer)'Range loop
if To_String(Buffer)(I) = Separator then
Ada.Text_IO.New_Line;
else
Ada.Text_IO.Put(To_String(Buffer)(I));
end if;
end loop;
end Longest_String_Challenge;
Output, when run with its own source code as the input:
function "+"(S: String) return Unbounded_String renames To_Unbounded_String; procedure Funny_Stuff(B, L: in out Unbounded_String; N: Unbounded_String) is
Here is the second solution. It also makes heavy use of exceptions, but it does not require to compute the difference (which is an arithmetic operation, i.e., a cheat). Instead, the procedure Funny_Stuff carries some auxiliary strings S, T. If they are unequal and neither is empty, it recursively calls itself with the same strings shortened by 1. At some point of time, either S=T, or S is empty, or T is empty.
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Text_IO, Ada.Characters.Latin_1;
procedure Longest_String_Challenge is
function "+"(S: String) return Unbounded_String renames To_Unbounded_String;
function "-"(U: Unbounded_String) return String renames To_String;
Separator: constant Character := Ada.Characters.Latin_1.NUL;
procedure Funny_Stuff(B, L: in out Unbounded_String;
N: Unbounded_String;
S, T: String) is
C: Character;
begin
if S = T then
B := B & Separator & N;
else
C:= T(T'First); -- raises Constraint_Error if T is empty
begin
C := S(S'First); -- same if S is empty
Funny_Stuff(B,L,N,S(S'First+1 .. S'Last), T(T'First+1..T'Last)); --
exception
when Constraint_Error =>
B := N;
L := N;
end;
end if;
exception
when Constraint_Error => null;
end Funny_Stuff;
Buffer: Unbounded_String := +"";
Longest: Unbounded_String := +"";
Next: Unbounded_String;
begin
while True loop
Next := + Ada.Text_IO.Get_Line;
Funny_Stuff(Buffer, Longest, Next, -Longest, -Next);
end loop;
exception
when others =>
for I in To_String(Buffer)'Range loop
if To_String(Buffer)(I) = Separator then
Ada.Text_IO.New_Line;
else
Ada.Text_IO.Put(To_String(Buffer)(I));
end if;
end loop;
end Longest_String_Challenge;
The output, when given its own source code as the input:
function "+"(S: String) return Unbounded_String renames To_Unbounded_String;
Funny_Stuff(B,L,N,S(S'First+1 .. S'Last), T(T'First+1..T'Last)); --
[edit] AutoHotkey
This was fun to implement. How I bypassed the restrictions: SubStr() returns part of a string starting from somewhere. If it goes past the end of a string, it returns "" which can be treated as false. StrLen() returns the length of a string. Thus: If this line contains a character at position "longestLength" then append it to the output. If the top line of the output does not contain a character at the position of the last character in this line of the input, then reset the output to be this line *and* set "LongestLength" to be the length of this line. did I break any rules?
input =
(
a
bb
ccc
ddd
ee
f
ggg
)
longestLen := 0, buffer := ""
Loop Parse, input, `n
{
top := SubStr(buffer, 1, InStr(buffer, "`n"))
StringReplace, top, top, `n
If SubStr(A_LoopField, LongestLen) ; at least as long
buffer .= A_LoopField "`n"
If !SubStr(top, StrLen(A_LoopField)) ; longer
buffer := A_LoopField "`n", LongestLen := StrLen(A_LoopField)
}
MsgBox % buffer
[edit] AWK
#!/usr/bin/awk -f
BEGIN {
maxlen = 0;
lenList = 0;
}
{
if (length($0)>maxlen) {
lenList = 1;
List[lenList] = $0;
maxlen = length($0);
} else if (length($0)==maxlen)
List[++lenList]=$0;
}
END {
for (k=1; k <= lenList; k++) print List[k];
}
Output:
ccc ddd ggg
[edit] BBC BASIC
Key to this solution are the functions FNcmp, which compares the lengths of two strings without using comparison operators, and FNinc, which increments an integer without using arithmetic operators. It also strictly adheres to the requirement to use only integer and string data types (no arrays or pointers) and avoids the use of LEN.
DIM buffer% 65535
bufptr% = buffer%
longest$ = " "
ON ERROR PRINT $$buffer%; : END
REPEAT
READ A$
IF FNcmp(A$, longest$) THEN
IF FNcmp(longest$, A$) ELSE bufptr% = buffer%
longest$ = A$
$bufptr% = A$
WHILE ?bufptr%
bufptr% = FNinc(bufptr%)
ENDWHILE
?bufptr% = 10
bufptr% = FNinc(bufptr%)
ENDIF
UNTIL FALSE : REM Loops until 'Out of data' error
END
DATA a, bb, ccc, ddd, ee, f, ggg
DEF FNcmp(a$, b$) : REM Returns LEN(a$)>=LEN(b$) [if b$<>""]
LEFT$(a$, 65535) = b$
= INSTR(a$, b$)
DEF FNinc(i%) : REM Returns i%+1
FOR i% = i% TO i% : NEXT
= i%
Output:
ccc ddd ggg
[edit] C
This is pointless on so many levels.
#include <stdio.h>Running it:
#include <string.h>
int cmp(const char *p, const char *q)
{
while (*p && *q) p = &p[1], q = &q[1];
return *p;
}
int main()
{
char line[65536];
char buf[1000000] = {0};
char *last = buf;
char *next = buf;
while (gets(line)) {
strcat(line, "\n");
if (cmp(last, line)) continue;
if (cmp(line, last)) next = buf;
last = next;
strcpy(next, line);
while (*next) next = &next[1];
}
printf("%s", buf);
return 0;
}
% printf "a\nbb\nccc\nddd\nee\nf\nggg" | ./a.outNote that the above code never checked for memory bounds and long input can overrun the buffers. It's intentionally made this way to keep it simple, please don't complicate it by adding safety features: if you are really concerned with that, below is a second method that can handle arbitrary length input.
ccc
ddd
ggg
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int inc(int x) { return (int)&((char *)x)[1]; }
int dec(int x) { return (int)&((char *)x)[-1]; }
int gt(int x, int y)
{
while (y && x) y = dec(y), x = dec(x);
return x;
}
int eq(int x, int y)
{
return !gt(x, y) && !gt(y, x);
}
int add(int x, int y)
{
while(y) x = inc(x), y = dec(y);
return x;
}
/* strlen(a) + 1 */
int length(const char *a)
{
char *x = 0; // assuming (int)(char*)0 == 0
if (!a) return 0;
while (*a) a++, x++;
return (int)x;
}
char *str_cat(char *a, const char *b)
{
int len = add(1, add(length(a), length(b)));
if (!(a = realloc(a, len))) abort();
return strcat(a, b);
}
char *get_line(char *l, FILE *fp)
{
int c, len = 0;
char tmp[2] = {0};
*l = 0;
while ((c = fgetc(fp)) != EOF) {
*tmp = c;
len = inc(len);
l = str_cat(l, tmp);
if (eq(*tmp, '\n')) return l;
}
*tmp = '\n';
return len ? str_cat(l, tmp) : l;
}
int main()
{
int l1, l2;
char *line = malloc(1), *buf = malloc(1), *longest = malloc(1);
while (1) {
line = get_line(line, stdin);
if (!(l1 = length(line))) break;
l2 = length(longest);
if (gt(l1, l2)) {
*buf = *longest = 0;
longest = str_cat(longest, line);
} else if (gt(l2, l1)) continue;
buf = str_cat(buf, line);
}
printf("%s", buf);
free(buf);
free(longest);
free(line);
return 0;
}
Here is a more concise variation which exits (with a non-zero return code) if it encounters a buffer overflow:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int longer(const char *p, const char *q) {
while (*p && *q) p = &p[1], q = &q[1];
return *p;
}
int main() {
char line[100000];
char buf[1100001];
char *linend= &line[99999];
char *bufend= &buf[1000000];
char *last = buf;
char *next = buf;
memset(line, 1, 100000);
memset(buf, 1, 1100001);
buf[0]= buf[1100000]= 0;
while (fgets(line, 100000, stdin)) {
if (!*linend) exit(1);
if (longer(last, line)) continue;
if (!longer(bufend, line)) exit(1);
if (longer(line, last)) next = buf;
last = next;
strcpy(next, line);
while (*next) next = &next[1];
}
printf("%s", buf);
exit(0);
}
[edit] D
This is a silly task.
import std.stdio, std.array;
/// Return a.length - b.length if positive, 0 otherwise.
int longer(string a, string b) {
while (!a.empty && !b.empty)
a.popFront(), b.popFront();
return a.length;
}
void main() {
string longest, lines;
foreach (string line; stdin.lines())
if (longer(line, longest))
lines = longest = line;
else if (!longer(longest, line))
lines ~= line;
writeln(lines);
}
- Output:
ccc ddd ggg
[edit] Go
package main
import (
"bufio"
"os"
)
func main() {
in := bufio.NewReader(os.Stdin)
var blankLine = "\n"
var printLongest func(string) string
printLongest = func(candidate string) (longest string) {
longest = candidate
s, err := in.ReadString('\n')
defer func() {
recover()
defer func() {
recover()
}()
_ = blankLine[0]
func() {
defer func() {
recover()
}()
_ = s[len(longest)]
longest = s
}()
longest = printLongest(longest)
func() {
defer func() {
recover()
os.Stdout.WriteString(s)
}()
_ = longest[len(s)]
s = ""
}()
}()
_ = err.(error)
os.Stdout.WriteString(blankLine)
blankLine = ""
return
}
printLongest("")
}
Description: It's basically the recursion+exceptions solution used by others, but staying close to the restrictions.
Restriction 1. The program actually has no operators at all, much less comparison operators. By the Go language specification, assignment is a statement, for example, and an index into a string is simply an "index." For this program, comparisons that control program flow are ones that happen during expression evaluation and then either do or do not trigger a run-time panic, the rough equivalent of throwing an exception in other languages.
Restriction 2. No arithmetic is done on numeric types, and in fact there are no variables of any numeric type in the program. While numeric values do appear at points during expression evaluation (the len function, for example) no arithmetic is explicitly done with them. The compiler certainly generates arithmetic instructions for address calculations underlying an index expression, for example; but the source code here simply supplies numbers as indexes, and relies on the compiler to figure out what arithmetic is appropriate.
Restriction 3. Other than integer and string, data types used are:
- Function: Main is a function, and there is extensive use of function literals in the program.
- os.File: os.Stdin and os.Stdout are predefined in package os.
- bufio.Reader: Used to wrap os.Stdin so the convenient ReadString function can be used to get individual input strings.
- error: A predefined type in Go, returned by many library functions (such as bufio.ReadString.)
- byte: While there are no variables of type byte in the program, single byte values appear at various points in expression evaluation. A byte is the result of indexing into a string, for example.
The spirit of the challenge seems to be prohibiting easy ways of doing things until the only ways left are considered novel. I don't consider recursion a particularly novel way of implementing a list, but it's obviously allowed as a solution so I used it. Avoiding arithmetic was fairly easy using the fact that the Go len function returns the length of a string, but that strings are zero based. Thus,
if a[len(b)] panics, it means that len(a) <= len(b) if a[len(b)] does not panic, it means that len(a) > len(b)
The above expressions avoid arithmetic, but not all comparisons, because error values are typically tested and branched on. Eliminating all comparisons leaves no boolean values in the program and no way to use if statements, which in Go require a boolean condition. Conditional flow control is implemented with the following device:
func() {
// 1. statements executed in either case
// 2. func below is a closure that captures free variables
// now, although the defer statement keeps the function
// from running until later
defer func() {
// 5. function runs either when panic happens, or
// at the time of a normal function return.
recover() // this stops panic mode
// 6. statements executed in either case, just
// before function returns
}()
// 3. more statements executed in either case
// 4. an expression that may or may not panic
// 4a. conditional code. executed only if no panic happens
return // 7. function return happens in either case
}()
A complication of course is that sometimes you want to conditionally execute code if the expression panics. Without a boolean value to invert, this case requires introducing an extra layer of func..defer..recover with a different expression contrived that will panic with the opposite effect.
[edit] Groovy
Solution: recursive
def longer = { a, b ->
def aa = a, bb = b
while (bb && aa) {
bb = bb.substring(1)
aa = aa.substring(1)
}
aa ? a : b
}
def longestStrings
longestStrings = { BufferedReader source, String longest = '' ->
String current = source.readLine()
def finalLongest = current == null \
? longest \
: longestStrings(source,longer(current,longest))
if (longer(finalLongest, current) == current) {
println current
}
return finalLongest
}
Test:
def source = new BufferedReader(new StringReader('''a
bb
ccc
ddd
ee
f
ggg'''))
longestStrings(source)
Output:
ggg ddd ccc
[edit] Icon and Unicon
[edit] String Scanning / Pattern Matching Solution
procedure main(arglist)Sample Output:
local b # the current buffer (string)
local l # the last string
local L # a \n delimited accumulation of all the longest strings
while b := read() do {
/l := b # primes l on first pass
b ? ( move(*l), if move(1) then L := (l := b) || "\n" else if move(0) then L := (\L|"") || b || "\n")
# move(*l) - fails if b is not l characters long
# move(1) - succeeds/fails if the string is longer and triggers a reset of L
}
write(\L)
end
ccc ddd ggg
[edit] Recursive Solution
Here is a recursive solution using only single character substring-ing (no string scanning/pattern matching).
procedure main()Sample Output:
longest(".") # needs a single character seed to throw away
end
procedure longest(Longest)
Line := read() | return Longest # read until we can return the longest strings
if Line[*Longest] then Longest := Line # prime/reset Longest
Longest := longest(Longest) # use stack to hold multiples
if Line[*Longest] then write(Line) # write only longest strings,
# Line must be at least as long as Longest
return Longest # feed back longest for length
end
ggg ddd ccc
[edit] J
J programming really cannot be separated from lists, and I have made few attempts to do so here. However, all of the lists used are of a fixed length and could theoretically be simulated by explicit functions or are strings.
isempty =. (0 [ 0&{) :: 1: NB. 0=#
compare =. ($:&}.)`((0 1,:_1 0) {~ <@,&isempty)@.(+.&isempty) NB. *@-&#
add =. ,`(,:@[)`] @. (compare {:)
> add&.>/ (}: , ,:&.>@{:) ;: 'a bb ccc ddd ee f ggg'
ccc
ddd
ggg
[edit] Mathematica
FixedPoint[
StringReplace[#,
x : "\n" | StartOfString ~~ a : Except["\n"] ... ~~ "\n" ~~
b : Except["\n"] ... ~~ y : "\n" | EndOfString :>
x <> Switch[((#1 + #2) + Abs[#1 - #2])/2 &[StringLength@a,
StringLength@b], Except[StringLength@a], b,
Except[StringLength@b], a, _, a <> "\n" <> b] <> y] &, "a
bb
ccc
ddd
ee
f
ggg"]
- Output:
ccc ddd ggg
[edit] MATLAB / Octave
function longestString(file);
fid = fopen(file);
maxlen = 0; L = {};
while ~feof(fid)
line = fgetl(fid);
if (length(line)>maxlen)
maxlen = length(line);
L = {line};
elseif (length(line)==maxlen)
L{end+1} = line;
end;
end;
fclose(fid);
disp(L);
end;
Output:
L = {
[1,1] = ccc
[1,2] = ddd
[1,3] = ggg
}
[edit] OCaml
Without the restrictions, the standard way to solve the task would be to iterate the lines, compare their length, and accumulate the longest lines in a list. Here we bypass the restriction of not using comparison operators (in the function cmp) by taking advantage that characters of strings are indexed from 0 to [length - 1] and trying to access to a character which index is the length of the other string (if it is beyond the end of the string an exception is raised). The other restriction of not using lists is easily bypassed by concatenating the results instead of accumulating it in a list.
let input_line_opt ic =
try Some (input_line ic)
with End_of_file -> None
let cmp s1 s2 =
try ignore(s1.[String.length s2]); 1 (* s1 is longer *)
with _ ->
try ignore(s2.[String.length s1]); -1 (* s2 is longer *)
with _ -> 0 (* both same length *)
let () =
let ic = open_in Sys.argv.(1) in
let rec loop longest acc =
match input_line_opt ic with
| Some line ->
( match cmp line longest with
| 1 -> loop line (line ^ "\n")
| 0 -> loop line (acc ^ line ^ "\n")
| _ -> loop longest acc )
| None ->
close_in ic;
print_string acc
in
loop "" ""
[edit] Pascal
In this version, inc() is used instead of additions. It still has a comparison.
program LongestStringChallenge_1(input, output);
var
Line: string;
Lines: array of string;
position, len: integer;
begin
if not eoln(input) then
begin
len := 1;
position := 0;
readln (line);
setlength(lines, len);
lines[position] := line;
while not eoln(input) do
begin
readln (line);
if length(line) = length(lines[0]) then
begin
inc(position);
inc(len);
setlength(lines, len);
lines[position] := line;
end;
if length(line) > length(lines[0]) then
begin
position := 0;
len := 1;
setlength(lines, 1);
lines[0] := line;
end;
end;
for position := low(lines) to high(lines) do
writeln (lines[position]);
end;
end.
Output:
% ./LongestStringChallenge_1 a b ccc ddd ee f ggg ccc ddd ggg
This version uses range check exceptions for the comparisons of string lengths. The range checks are compiler specific. With FreePascal its requires the use of the type ANSIstring instead of "classic" type string.
program LongestStringChallenge_2(input, output);
{$mode ObjFPC}
{$rangechecks on}
uses
SysUtils;
var
Line: ANSIstring;
Lines: array of ANSIstring;
position: integer;
tester: char;
begin
if not eoln(input) then
begin
readln (line);
position := 0;
setlength(lines, 1);
lines[0] := line;
while not eoln(input) do
begin
readln (line);
try
tester := lines[0][length(line)];
try
tester := line[length(lines[0])];
inc(position);
setlength(lines, succ(position));
lines[position] := line;
except
end;
except
position := 0;
setlength(lines, 1);
lines[0] := line;
end;
end;
for position := low(lines) to high(lines) do
writeln (lines[position]);
end;
end.
Output:
% ./LongestStringChallenge_2 a b ccc ddd ee f ggg ccc ddd ggg
[edit] Perl
#!/usr/bin/perl -n
END{ print $all }
substr($_, length($l)) and $all = $l = $_
or substr($l, length) or $all .= $_;
[edit] Perl 6
my $l = ''; # Sample longest string seen.
my $a = ''; # Accumulator to save longest strings.
while get() -> $s {
my $n = "$s\n";
if $n.substr($l.chars) { # Is new string longer?
$a = $l = $n; # Reset accumulator.
}
elsif !$l.substr($n.chars) { # Same length?
$a ~= $n; # Accumulate it.
}
}
print $a;
Given the example input, returns:
ccc ddd ggg
[edit] PicoLisp
Not sure if this meets the spirit. I would implement it the same way if there were no "restrictions":
(mapc prinl
(maxi '((L) (length (car L)))
(by length group
(in NIL
(make (until (eof) (link (line)))) ) ) ) )
Another solution avoids 'group', and builds an associative buffer of lines instead:
(let Buf NIL
(in NIL
(until (eof)
(let (Line (line) Len (length Line))
(if (assoc Len Buf)
(conc @ (cons Line))
(push 'Buf (cons Len (cons Line))) ) ) ) )
(mapc prinl (cdr (maxi car Buf))) )
[edit] Pike
things of note:
the comparison of strings is done by converting the string into an array of indices: ("abc" becomes ({ 1,2,3 }))
the - operation is the set operation A / B and not a numerical subtraction. it removes all the elements in the second array from the first.
if there are any left, we know that the string is longer.
now, once a longer string is found we call write() to print it.
however we don't write it out directly, but instead we store the call in queue of pikes backend. the backend is used to handle callbacks for non-blocking I/O, and it provides a facility to call functions after a delay of time. (call_out(write, 5, "foo"); calls write after 5 seconds with the argument foo)
before we add the new call to write, we remove all older calls to write since we don't want them anymore.
return -1; starts the backend, which allows pike to execute the remaining call_outs and exit.
int main(int argc, array argv)
{
string longest = "";
foreach(Stdio.stdin.line_iterator();; string line)
{
if( sizeof(indices(line) - indices(longest)))
{
while(!zero_type(remove_call_out(write)));
longest = line;
call_out(write, 0, line+"\n");
}
else if( !sizeof(indices(longest) - indices(line)))
{
call_out(write, 0, line+"\n");
}
}
call_out(exit, 0.01, 0);
return -1;
}
[edit] PL/I
read: procedure options (main); /* 18 January 2012. */
declare line character (100) varying controlled;
declare text character (100) varying;
declare max_length fixed binary;
declare in file input;
on endfile (in) go to done;
open file (in) title ('/readline.pli,type(text),recsize(100)');
max_length = 0;
do forever;
get file (in) edit (text) (L);
put skip list (text);
if length (text) > max_length then
do;
max_length = length(text);
/* empty the stack */
do while (allocation(line) > 0);
free line;
end;
allocate line;
line = text;
end;
else if length(text) = max_length then
do;
allocate line;
line = text;
end;
end;
done:
put skip list (max_length || ' is the length of the longest line(s)' );
do while (allocation(line) > 0);
put skip list (line);
free line;
end;
end read;
output (the above file plus the following 3 lines):
74 is the length of the longest line(s)
put skip list (max_length || ' is the length of the longest line(s)' );
/* Read lines of a file, and print the longest. (If there is more than */
[edit] PureBasic
Procedure.i ConsoleWrite(t.s) ; compile using /CONSOLE option
OpenConsole()
PrintN (t.s)
CloseConsole()
ProcedureReturn 1
EndProcedure
Procedure.i StdOut(t.s) ; compile using /CONSOLE option
OpenConsole()
Print(t.s)
CloseConsole()
ProcedureReturn 1
EndProcedure
DataSection
s:
Data.s "a"
Data.s "bb"
Data.s "ccc"
Data.s "ddd"
Data.s "ee"
Data.s "f"
Data.s "ggg"
Data.s "~" ; the tilda is only to keep the code compact
e: ; and easy to understand
EndDataSection
l$="" ; memory allocation for strings is automatic
a$="" ; in fact these two lines are unnecessary
Restore s
Repeat
Read.s s$
If s$="~":Break:EndIf
s$+#CRLF$
s=Len(s$):l=Len(l$) ; using s$ allows the use of s as an integer type
If s>l :l$=s$:a$=l$
ElseIf s=l :a$+s$
EndIf
Forever
StdOut(a$)
- Output
; Directory of C:\_sys\temp
; 07/14/2012 03:04 PM 4,608 LongestStringChallenge.exe
; 1 File(s) 4,608 bytes
; 0 Dir(s) 434,768,625,664 bytes free
; C:\_sys\temp>LongestStringChallenge.exe
; ccc
; ddd
; ggg
[edit] Python
import fileinput
# originally, return len(a) - len(b) if positive, 0 otherwise.
# Observing that longer is used for its Boolean result,
# and that '' is False, while any other string is True,
# longer need only to return a after removing len(b) characters,
# which is done without resorting to len().
def longer(a, b):
while a and b:
a, b = a[1:], b[1:]
return a
longest, lines = '', ''
for x in fileinput.input():
if longer(x, longest):
lines, longest = x, x
elif not longer(longest, x):
lines += x
print(lines, end='')
- Sample runs
paddy@paddy-VirtualBox:~$ cat <<! | python3.2 longlines.py a bb ccc ddd ee f ggg ! ccc ddd ggg paddy@paddy-VirtualBox:~$ touch nothing.txt paddy@paddy-VirtualBox:~$ cat nothing.txt | python3.2 longlines.py paddy@paddy-VirtualBox:~$
[edit] Racket
#lang racket
;; First we write the general idea
;; note the comparison functions (f> and f=) are parametric
(define (longest-lines max-line acc f> f=)
(let*
((line (read))
(end? (eof-object? line));----------------------;; we read lines one-by-one until eof
(new-str (if end? "" (symbol->string line))))
(cond
(end? acc)
((f> new-str max-line) ;----------------------;; if the new-str is bigger (wrt length) than our
(longest-lines new-str new-str f> f=)) ;; current-max, we go on with the new one.
((f= new-str max-line) ;----------------------;; if the new-str is as big as the current-max,
(longest-lines ;----------------------;; we append it to acc(umulator).
max-line
(string-append acc "\n" new-str) f> f=))
(else
(longest-lines max-line acc f> f=)))))
With numeric comparisons (i.e. no restrictions), we can compute the longest strings with:
(define (str-len-comp compf s1 s2)
(compf (string-length s1) (string-length s2)))
(display "-------- Longest lines ---------")
(newline)
(display (longest-lines "" "" (curry str-len-comp >) (curry str-len-comp =)))
(newline)
We can also do this by building tiny bit of Peano arithmetics on the lengths of the strings:
(define zero "")
(define zero? (curry string=? zero))
(define (pred strnum)
(if (zero? strnum)
strnum
(substring strnum 1 (string-length strnum))))
(define (str> s1 s2)
(if
(zero? s2)
(not (zero? s1))
(str> (pred s1) (pred s2))))
(define (str= s1 s2)
(and (not (str> s1 s2))
(not (str> s2 s1))))
;; Now we can use the general function again with our new comparison functions
(display "-------- Longest lines ---------")
(newline)
(display (longest-lines "" "" str> str=))
(newline)
Given the input.file with contents
a bb ccc ddd ee f ggg
We run our program and get the result as follows:
$ racket LongestStringChallenge.rkt < input.file -------- Longest lines --------- ccc ddd ggg
[edit] REXX
In the REXX language, everything is a string (characters).
A stemmed array (y.1 y.2 y.3 ∙∙∙) is nothing more than three disjointed REXX variables.
[edit] read file until E-O-F
/*REXX pgm reads a file & prints the longest [widest] record(s)/line(s).*/
!.='' /*initialize stemmed array to nul*/
fileID='LONGEST1.TXT' /*point to the input file. */
m=0
do while min(lines(fileID),1); _=linein(fileID); w=length(_)
say 'input =' _ /*display the input to terminal. */
!.w=!.w || '0a'x || _ /*build a stemmed array element. */
m=max(m,w) /*find the maximum width so far. */
end /*while min(lines(... */
do j=m for m /*handle the case of no input. */
say center(' longest record(s): ',79,'═')
say substr(!.m,2)
say center(' list end ',79,'═')
exit /*stick a fork in it, we're done.*/
end /*j*/
output
input = a input = bb input = ccc input = ddd input = ee input = f input = ggg ═════════════════════════════ longest record(s): ══════════════════════════════ ccc ddd ggg ══════════════════════════════════ list end ═══════════════════════════════════
[edit] read file until not ready
/*REXX pgm reads a file & prints the longest [widest] record(s)/line(s).*/
!.='' /*initialize stemmed array to nul*/
fileID='LONGEST2.TXT' /*point to the input file. */
signal on notready /*when E-O-F is reached, jump. */
m=0 /*maximum width line so far. */
do forever; _=linein(fileID); w=length(_) /*read a line. */
say 'input =' _ /*display the input to terminal. */
!.w=!.w || '0a'x || _ /*build a stemmed array element. */
m=max(m,w) /*find the maximum width so far. */
end /*forever*/
notready: do j=m for m /*handle the case of no input. */
say center(' longest record(s): ',79,'═')
say substr(!.m,2)
say center(' list end ',79,'═')
exit /*stick a fork in it, we're done.*/
end /*j*/
output
input = -3 input = -two input = -one input = zero input = one input = two input = three input = ? input = four input = five input = six input = seven input = eight input = nine input = ten input = √121 input = 12.+0 ═════════════════════════════ longest record(s): ══════════════════════════════ three seven eight 12.+0 ══════════════════════════════════ list end ═══════════════════════════════════
[edit] Dual code (works on TSO and PC)
/* REXX ***************************************************************
* 27.10.2010 Walter Pachl
**********************************************************************/
Parse Arg fid
If fid='' Then Do
"ALLOC FI(IN) DA('N561985.PRIV.V100(LL)') SHR REUSE"
'EXECIO * DISKR IN (STEM L. FINIS' /* read all lines */
'FREE FI(IN)'
End
Else Do
Do i=1 By 1 While lines(fid)>0
l.i=linein(fid)
End
l.0=i-1
End
maxl = 0 /* initialize maximum length */
Do i=1 To l.0 /* loop through all lines */
linl=length(l.i) /* length of current line */
Select
When linl>maxl Then Do /* line longer than preceding */
maxl=linl /* initialize maximum length */
mem.0=1 /* memory has one entry */
mem.1=l.i /* the current line */
lin.1=i /* its line number */
End
When linl=maxl Then Do /* line as long as maximum */
z=mem.0+1 /* new memory index */
mem.z=l.i /* the current line */
lin.z=i /* its line number */
mem.0=z /* memory size */
End
Otherwise /* line is shorter than max. */
Nop /* ignore */
End
End
If mem.0>0 Then Do
Say 'Maximum line length='maxl
Say ' Line Contents'
Do i=1 To mem.0
Say right(lin.i,5) mem.i
End
End
Else
Say 'No lines in input file or file does not exist'
Maximum line length=5
Line Contents
1 99999
3 +++++
[edit] Ruby
# Without restrictions
BEGIN {
v = [ ]
m = 0
}
n = $_.length
if n == m then
v <<= $_
elsif n > m then
v = [$_]
m = n
end
END {
v.each { |s| puts s }
}
Then ruby -n longest.rb < file.txt
[edit] Run BASIC
Uses in memory database
sqliteconnect #mem, ":memory:" ' Create in memory DB
#mem execute("CREATE TABLE data(str)") ' And fields to hold the string data
strings$ = "a bb ccc ddd ee f ggg" ' The given string data
while word$(strings$,i + 1," ") <> ""
i = i + 1
#mem execute("INSERT INTO data VALUES('";word$(strings$,i," ");"')") ' insert the strings in to the DB
wend
#mem execute("SELECT length(str) as leng, str FROM data ORDER BY leng desc,str") ' pull data in reverse lenght sequence
WHILE #mem hasanswer()
#row = #mem #nextrow()
leng = #row leng()
str$ = #row str$()
print leng;" ";str$ ' print the data
WEND
Using a simple sort method
strings$ = "a bb ccc ddd ee f ggg" ' The given string data
while word$(strings$,numWords + 1," ") <> "" ' Count the words
numWords = numWords + 1
wend
dim string$(numWords) ' Dimension the string with the word cound
for j = 1 to numWords
string$(j) = word$(strings$,j," ") ' put the words from the string into the string array
next j
h$ = "1"
while h$ <> "" ' The good old simple bubble sort
h$ = ""
for i = 1 to numWords -1
if len(string$(i)) < len(string$(i+1)) then ' sort by length descending
h$ = string$(i)
string$(i) = string$(i+1)
string$(i+1) = h$
end if
next i
wend
for i = 1 to numWords
print len(string$(i));" ";string$(i) ' print out the words in length descending sequence
next i
3 ccc 3 ddd 3 ggg 2 bb 2 ee 1 a 1 f
[edit] Tcl
Uses only string comparisons for equality and glob-style matching
#!/usr/bin/env tclsh
set longest z
set output ""
while {[gets stdin line] != -1} {
set comparison [string repeat z [string length $line]]
if {$longest eq $comparison} {
# this line is equally long
append output $line \n
} elseif {[string match ${longest}z* $comparison]} {
# this line is longer
set longest $comparison
set output "$line\n"
}
}
puts -nonewline $output
Test:
$ ./longest.tcl <<END > a > bb > ccc > ddd > ee > f > ggg > END ccc ddd ggg $ ./longest.tcl </dev/null $
[edit] XSLT 2.0
This XSLT 2.0 style-sheet...
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output indent="yes" encoding="UTF-8" omit-xml-declaration="yes" />
<xsl:template match="/*">
<t><xsl:copy-of select="for $l in max( for $s in s return string-length($s))
return s[string-length(.) eq $l]" /></t>
</xsl:template>
</xsl:stylesheet>
...when applied to this input...
<t>
<s>a</s>
<s>bb</s>
<s>ccc</s>
<s>ddd</s>
<s>ee</s>
<s>f</s>
<s>ggg</s>
</t>
...yields...
<t>
<s>ccc</s>
<s>ddd</s>
<s>ggg</s>
</t>
