I was raking around on the net and found this problem and coded up a solution. Once we get at least 10 solutions I'll post mine and a link to where I found the problem.
Any language, any libraries (but declare them) allowed. Aim for clarity and conciseness. Assume the input is well formed. Mine is 5 lines of scheme code (6 if we include requiring a library). No calling an "answer" function that "you wrote already and put in an external lib" ;)
Consider the problem of turning a list consisting
of a mix between symbols and non-symbols into a
list of lists of the symbol and its following
non-symbols. That is:
Input: ({<symbol> <non-symbol>*} ... )
Output: ((<symbol> (<non-symbol>*)) ...)
Example: (a 1 2 3 b 4 5 c d 8 9 e)
-> ((a (1 2 3)) (b (4 5)) (c ()) (d (8 9)) (e ()))
(()())())(((((((((((((((((((((()))))))))())))()(no-fun))))))))))))))))()())))))))))))))))((((((((((()))))))()()()()()))))))))))((((((())))()lambda()()))))))))))))))))))))))))((((()))))()))))))))(((((((((())))))))())))))))))))))))
the answer in lisp
Name:
Anonymous2009-12-12 18:28
>>2
That is a good point, how about a very large tuple ;) Alternatively, you could treat the symbols as strings i.e. ["a", "1", "2", "3", "b", "4", "5", "c", "d", "8", "9", "e"]
sub doIt{
my @ret;
for(@_){
/^[a-z]+$/i and push (@ret, [$_, []]), next;
/^\d+$/ and push @{$ret[-1]->[1]}, $_;
}
@ret;
}
tweaked it a bit.
and, as you see i only look at a-z as symbols. maybe you want something other, but meh.
Out of boredom, wrote one state-machine-based implementation, only using minimal CL:
(defun frob-flat-list (list)
(let ((element (pop list))
symbol non-symbols result)
(tagbody
SYMBOL
(unless (symbolp element)
(error "Not a symbol: ~A" element))
(setf symbol element)
;;(go NON-SYMBOL)
NON-SYMBOL
(setf element (pop list))
(cond
((symbolp element)
(push (list symbol (nreverse non-symbols)) result)
(setf non-symbols nil)
(go SYMBOL))
(t
(push element non-symbols)
(go NON-SYMBOL))))
(nreverse result)))
;TOY-PROBLEMS> (frob-flat-list '(a 1 2 3 b 4 5 c d 8 9 e))
;((A (1 2 3)) (B (4 5)) (C NIL) (D (8 9)) (E NIL))
>>19 http://www.lispworks.com/documentation/HyperSpec/Body/s_tagbod.htm
Within the body of the TAGBODY block, you can establish labels, to which you can jump using GO. Basically, it's like goto, however it can also do non-local transfer of control: if you lexically capture a (go tag) within a closure, you can call that closure and jump within the tagbody (with some limits). This allows one to use TAGBODY to create new control structures, condition/error handling systems and other things. People don't usually use TAGBODY/GO within normal code, but mostly within macros, however since state machines fit its model very well, it's considered acceptable use too.
Name:
Anonymous2009-12-12 21:40
It's a trick! The problem is already solved!
If before solving the problem, the string looks like this:
"a123b45cd89e"
Then it would look exactly the same afterwards!
>>21
Why are you assuming input and output have to be strings? It's pretty obvious that OP is talking about a linked list of objects as input, and that the output is a linked list of linked lists of objects.
>>22
How is this obvious? All I see are parentheses!
Furthermore, a linked list is an extremely inefficient way to store a series of characters; a null-terminated string is far superior. Remember, every byte is precious!!
Name:
OP2009-12-12 21:52
>>24 Consider the problem of turning a list consisting
of a mix between symbols and non-symbols into a
list of lists of the symbol and its following
non-symbols. That is: ... turning a list ... into a list of lists ...
Please consider reading the problem as well as looking at the example, it is usually enlightening. Efficiency wasn't the concern either, I was looking for clarity and conciseness. They are not mutually exclusive, I admit, but they are often at loggerheads.
Name:
Lisp2009-12-12 21:57
>>25
Sorry, I meant return array_combine($tmp[1], array_walk($tmp[2], 'str_split') );
Name:
OP2009-12-12 22:00
My own solution was
(define (mk-sym-list lst)
(if (null? lst) '()
(let-values (((vals rest) (break symbol? (cdr lst))))
(cons (list (car lst) vals)
(mk-sym-list rest)))))
and it takes break from SRFI 1.
I came across this problem when reading a few old posts on jao's blog[1], but the problem [linked to in the post] was from a comp.lang.scheme thread [2]
>>27
I didn't use it in this solution, but does anyone else use a "let1" macro, for instances where they only wish to bind one value? I find the additional parentheses used to be a little redundant and distracting.
>>30
I believe you mean But a string can be any number of lists, depending on how pointers are aused!
I have nothing against the text-based solutions, it just misses the point of the exercise.
>>33
It was never about strings, I merely suggested that you could use strings as a way of representing the symbols in a language that doesn't give you the flexibility to mix types in a list. As far as I know, very few languages actually have a symbol type (Lisp + derivatives, Erlang, Ruby), and Haskell and various other languages are strict about keeping list elements all of the same type.
No-one and I repeat NO-ONE is under the delusion that it is efficient to store strings as a list of characters.
>>33
Why do you think strings are stored as linked lists? That would be terribly inefficient.
Given OP's syntax, I'm mostly assuming Lisp/Scheme meaning of symbol/non-symbol, which would mean the following, in C-like languages:
symbol - an object/structure, usually referred by a pointer, the structure has a name as one of it's fields. If you want to simplify this, you're free to use null terminated strings
non-symbols - other types of objects, since it wasn't specified what it means. If you want to simplify this requirement, you could say they're numbers, even though that would probably be different from what OP asked.
a list - linked list: structure of 2 elements, first is a pointer to the object, the second is a pointer to the rest of the list. A symbol called NIL, or empty list object '() can be used to represent the empty list. If you want to simplify this in C, you could use a NULL or 0.
At least the meanings I assigned to the terms used in OP's problem, but maybe I'm reading too much into it.
>>36
You are correct, although I was hoping that most of it was obvious from the context.Certainly a percentage of the /prog/ population provided solutions with no such coaxing. The strings were suggested as a way for the Haskeller (who has yet to post a solution ;) to participate while using his language of choice.
>>38
Just assume 2 disjointed types of objects, one is a symbol, the othes are not. It doesn't matter what the objects are, but if you want to simplify the problem, you could say one is a string, and the other is a number.
f :: (String -> Bool) -> [String] -> [[String]]
f isSymbol = groupBy (const $ not . isSymbol)
Given a predicate that determines whether a string is a symbol or not, ``f'' produces the desired function.
Example:
GHCi> -- We define a symbol to be a string that does not begin with a digit.
GHCi> -- For the sake of simplicity, all strings are assumed to be non-empty.
GHCi> let isSymbol = (`notElem` ['0'..'9']) . head
GHCi> -- Let's test it.
GHCi> (isSymbol "foo", isSymbol "3bar")
(True,False)
GHCi> -- Finally, we test f.
GHCi> f isSymbol ["a", "1", "2", "3", "b", "4", "5", "c", "d", "8", "9", "e"]
[["a","1","2","3"],["b","4","5"],["c"],["d","8","9"],["e"]]
Now, due to the fact that Haskell's lists are homogenous, the output format is slightly different from the one specified in >>1. We can alter f to return tuples instead:
f :: (String -> Bool) -> [String] -> [(String, [String])]
f isSymbol = map (\ (s : ns) -> (s, ns)) . groupBy (const $ not . isSymbol)
And of course, constraining this function to Strings is quite pointless. The same code will work with the more general type signature (a -> Bool) -> [a] -> [(a, [a])].
Name:
132009-12-13 2:59
Thanks >>41, your post gave me an idea on how to write this a lot more concisely:
(asdf:oos 'asdf:load-op :split-sequence)
(use-package :split-sequence)
I am sorry, I must have missed something obvious, but how do we know that '1' is not also a symbol? You need a symbol table to correctly solve this problem, it seems to me. It seems unspecified what, exactly, a symbol is.
>>45
OP already mentioned that he meant Lisp-like symbols:
1, "1" or '|1| are very different kinds of objects, one is the integer 1, the other is a string containg the character #\1, and the other is a symbol named by the string "1". Things may be slightly different in Scheme, but 1 and '1' are different things. OP's problems essentially boils down to grouping down objects given a predicate which separates the objects into 2 disjoint groups, the actual meaning of symbols or non-symbols is not as relevant, sadly, at least some half of the solutions are string-based, so they miss the point of the problem, and work with some limited amount of input.
Name:
Anonymous2009-12-13 21:13
This is my first non-trivial algorithm in F#. Gosh, this is hard.
let rec splitlist l along =
let rec gather l =
match l with
|[] -> []
|head::tail when (head<>along) -> head::(gather tail)
|head::tail -> []
match l with
|[] -> []
|head::tail when (head=along) -> (head::(gather tail))::(splitlist tail along)
|head::tail -> (splitlist tail along)
let separate l along=
(splitlist l along) |> Seq.map (fun x -> match x with |head::tail -> (head ,tail))