Why it’s hard for programmers to write a program to flatten a list?

Re:Why it’s hard for programmers to write a program to flatt... by cestith on Friday February 24, 2017 @01:52PM (#13726470)

This is pretty trivial. It doesn't require recursion, although the recursive implementation is much simpler. The spec doesn't specify breadth-first or depth-first. The example input offered comes out the example output offered either way. The spec in the article also doesn't mention making it generic, so I don't see how that's points away for programmers who tackle the input and output given as integers only.

Here's some pretty trivial Perl5 to do recursive or iterative versions.:

    use strict;
    use warnings;
    use Data::Dumper ();
    my $nested = [ 1, [ 2, 3 ], [ 4, [ 5, 6, [ 7, [ 8, [ 9, 10 ] ], 11, 12, [ 13, [ 14, [ 15, 16 ], 17 ], 18 ], 19 ], 20 ] ] ];

    sub flatten {
        my @f;
        push @f, (ref $_ ? flatten( $_ ) : $_ ) for @{ $_[0] };
        return @f;
    }

    sub flatten2 {
        my $n = shift;
        my ( @f, @queue1, @queue2 );
        my $pass = 0;

        for ( @$n ) {
            if ( ref $_ ) {
                push @queue1, $_;
            } else {
                push @f, $_;
            }
        }
        until ( $pass > 0 && scalar @queue1 == 0 && scalar @queue2 == 0 ) {
            for ( @queue1 ) {
                if ( ref $_ ) {
                    push @queue2, @{ $_ };
                } else {
                    push @f, $_;
                }
            }
            @queue1 = @queue2;
            @queue2 = ();
            $pass++;
        }

        return @f;
    }

    print STDOUT (join ' ', flatten( $nested )) . "\n";
    my @flat = flatten( $nested );
    print Data::Dumper::Dumper \@flat;

    print STDOUT (join ' ', flatten2( $nested )) . "\n";
    my @flat2 = flatten2( $nested );
    print Data::Dumper::Dumper \@flat2;

[ Parent | on HN ]

Re:Why it’s hard for programmers to write a program to flatt... by zzzcpan on Friday February 24, 2017 @02:18PM (#13726731)

You can make it nicer and more reliable with Perl:

    sub flatten {
       map { ref $_ eq 'ARRAY' ? flatten(@$_) : $_ } @_ 
    }

However, this is not something a Java/OO programmer would be comfortable with, especially under the stress of the interview. As it's a bit higher level and closer to a functional way of thinking, than OO.

[ Parent | on HN ]

Re:Why it’s hard for programmers to write a program to flatt... by cestith on Friday February 24, 2017 @02:23PM (#13726783)

I started to use map, but I've been told time and again anything that does is not a trivial example because you start by explaining what map does.

Anyway, I'm glad the first response to "this is trivial in Perl" is another, simpler Perl response rather than "Perl is dead".

[ Parent | on HN ]

Re:Why it’s hard for programmers to write a program to flatt... by alain_gilbert on Saturday February 25, 2017 @11:35PM (#13735700)

Non recursive algo with python:

  def flatten(array):
      queue = [array]
      result = []
      while len(queue) > 0:
          item = queue.pop(0)
          if isinstance(item, list):
              for sub_item in item:
                  queue.append(sub_item)
          else:
              result.append(item)
      return result

  a = [1,[2,3], [4, [5,6]]]
  print 'input:', a, '\noutput:', flatten(a)

[ Parent | on HN ]