BookmarkSubscribeRSS Feed
Ksharp
Super User

Under influence of FriedEgg , I also want to post a Puzzle. It is from my e-mail.

URL is http://www.gild.com/puzzles/details/320

But I can't understand this Puzzle totally. Is there somebody can explain to me ,it is better to give an example.

December  8 - January 15, 2012(Closes at 11:59pm GMT)

A gymnast center is designing a tower routine consisting of people standing on top of other’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her.

Given the heights and weights of each person in the event, write a program that computes the largest possible number of people in such a tower routine.

Rules and Terms

Why it is the largest number not smallest number?

Ksharp

7 REPLIES 7
FriedEgg
SAS Employee

This reminds me of Pascal's Triangle, somewhat.

You are missing the rest of the puzzle, which requires logging into the website through facebook or linked in:

Puzzle Description

A gymnast center is designing a tower routine consisting of people standing on top of other’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her.

Given the heights and weights of each person in the event, write a program that computes the largest possible number of people in such a tower routine.

The program accepts a single argument on the command line. This argument is a file name, which contains the information you need (the heights and weights of each person). The program must write to the standard output the largest possible number of people in the tower, followed by a single newline (‘\n’).

Input Specifications

The input file consists of a single line.
The line is made of pairs of heights and weights. Each pair is in the format (ht, wt), with ht and wt both positive integers.
Each pair is separated by a whitespace. The line might or might not be terminated by a new line ‘\n’.

There are no gymnasts having the same height or same weight.

Here is an example of a valid input:

(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)

Output Specifications

Your program should output on the standard output the largest possible number of people in the tower, followed by a single newline (‘\n’).

Here is an example of a valid output:

4 

Here is a test case to make sure your program works:

Input

(9430, 3656) (9147, 14355) (133, 14393) (7917, 9513) (3719, 12775) (9902, 3718) (7613, 46) (7339, 6417) (5034, 7800) (11555, 12870) (14959, 9297) (10707, 4664) (3376, 11162) (12748, 1591) (1299, 4653) (9050, 10847) (4412, 1720) (10030, 1402) (1777, 8625) (12725, 1775)

Expected Output

5

Input

(2850, 1806) (10220, 2971) (5934, 255) (13829, 12522) (9221, 6803) (1643, 8373) (1838, 1330) (5084, 13371) (1874, 2626) (3130, 9037) (4414, 2361) (11327, 1857) (11015, 9180) (10525, 5781) (1172, 10901) (14008, 8653) (5936, 8367) (5407, 6673) (11365, 12291) (6461, 9697) (833, 2632) (13967, 5717) (4363, 7795) (3614, 2924) (7349, 4493) (13674, 2025) (1258, 129) (2478, 14222) (9119, 11612) (2073, 4990)

Expected Output

10

FriedEgg
SAS Employee

There is one big issues with the following answer I quickly put together for this problem.  ALLPERM has a limit of 18 variables, both of the examples I give above are more than 18, so this will not work for them.  However, it does work for the initial question with 9 elements.

filename FT15F001 temp lrecl=512;

data ht_wt;

infile FT15F001 dlm=',)';

input @;

_infile_=prxchange('s/[\(\ ]//o',-1,_infile_);

input (ht wt) (:8.) @@;

parmcards;

(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)

;

run;

proc sql noprint;

select ht, wt into :ht separated by ' ',:wt separated by ' ' from ht_wt;

quit;

data _null_;

array ht[&sqlobs] (&ht);

array wt[&sqlobs] (&wt);

count=0;

do i=1 to fact(&sqlobs);

  call allperm(i, of ht

  • );
  •   call allperm(i, of wt

  • );
  •   _count=0;

      do ii=1 to &sqlobs-1;

       if ht[ii]>ht[ii+1] and wt[ii]>wt[ii+1] then _count+1;

      end;

      count=max(count,_count);

    end;

    file print;

    put count;

    run;

    4

    Ksharp
    Super User

    Haha. I understood what the puzzle means. I can code it correctly now.

    Fried Egg , It is not sensible method to use call perm which will waste lots of System Source ,because it might be yield a loop(i.e. you will search the track you have already searched.)

    Now I will post my code to GLID to Win My ipad. Smiley Happy

    Hope I can register at it. But Chinese Government has already forbidden FaceBook , Twitter .... and so on.

    I am not sure I can get a right to post.

    /*The following is SAS code. it is passed under SAS9.2*/
    /*input can change under datalines, output will be generated in SAS log */
    
    
    data have;
    infile datalines dlm='(), ';
    input height weight @@;
    datalines;
    (2850, 1806) (10220, 2971) (5934, 255) (13829, 12522) (9221, 6803) (1643, 8373) (1838, 1330) (5084, 13371) (1874, 2626) (3130, 9037) (4414, 2361) (11327, 1857) (11015, 9180) (10525, 5781) (1172, 10901) (14008, 8653) (5936, 8367) (5407, 6673) (11365, 12291) (6461, 9697) (833, 2632) (13967, 5717) (4363, 7795) (3614, 2924) (7349, 4493) (13674, 2025) (1258, 129) (2478, 14222) (9119, 11612) (2073, 4990)
    ;
    run;
    
    
    
    data _null_;
    if _n_ eq 1 then do;
    if 0 then set have;
    declare hash ha(dataset:'have');
    declare hiter hi('ha');
     ha.definekey('height','weight');
     ha.definedata('height','weight');
     ha.definedone();
    
    length obs 8 branch _branch $ 20000;
    declare hash h(hashexp:20,ordered:'Y');
    declare hiter i('h');
     h.definekey('obs');
     h.definedata('branch');
     h.definedone();
    end;
    set have end=last;  retain max 0;
    count+1;obs=1;branch=catx('|',height,weight);h.add();
    do while(i.next()=0);  num=(countc(branch,'|')+1)/2;
     max=max(max,num);
    _height=input(scan(branch,-2,'|'),best8.);
    _weight=input(scan(branch,-1,'|'),best8.);
     do while(hi.next()=0);
      _branch=branch;
      if _height lt height and _weight lt weight then do;
         obs+1;branch=catx('|',branch,height,weight);
         h.add();branch=_branch;end;
     end;
    end;
    h.clear();
    if last then putlog 'The largest possible number is : ' max  ;
    run;
    
    
    
    

    Ksharp

    Message was edited by: xia keshan ______ A fixed Version.

    FriedEgg
    SAS Employee

    Nice work Ksharp.  As I mentioned in my original post my code was not good.  It was a quick, brute-force type, not even fully working since it has a hard limit on number of variables.

    Unfortuneatly gild.com and codeeval.com and most other sites I know of similar do not accept SAS language solutions. Smiley Sad

    Ksharp
    Super User

    Hi. FriedEgg.

    I found my code above is not efficient. So I recode and optimize it.

    As your said . When I intend to post my code to Gild, I can't find a place for SAS, there are many language Java C Rubby Perl, only not include SAS. I can't own my Ipad. Smiley Sad

    data have;
    infile datalines dlm='(), ';
    input height weight @@;
    datalines;
    (2850, 1806) (10220, 2971) (5934, 255) (13829, 12522) (9221, 6803) (1643, 8373) (1838, 1330) (5084, 13371) (1874, 2626) (3130, 9037) (4414, 2361) (11327, 1857) (11015, 9180) (10525, 5781) (1172, 10901) (14008, 8653) (5936, 8367) (5407, 6673) (11365, 12291) (6461, 9697) (833, 2632) (13967, 5717) (4363, 7795) (3614, 2924) (7349, 4493) (13674, 2025) (1258, 129) (2478, 14222) (9119, 11612) (2073, 4990)
    ;
    run;
    
    
    data _null_;
    if _n_ eq 1 then do;
    if 0 then set have;
    declare hash ha(dataset:'have');
    declare hiter hi('ha');
     ha.definekey('height','weight');
     ha.definedata('height','weight');
     ha.definedone();
    
    length obs _height _weight person _person __height __weight 8;
    declare hash h(ordered:'Y');
    declare hiter i('h');
     h.definekey('obs');
     h.definedata('_height','_weight','_person');
     h.definedone();
    end;
    set have end=last;  retain max 0;
    obs=1; _person=1; _height=height; _weight=weight; h.add();
    do while(i.next()=0); 
     max=max(max,_person); person=_person;__height=_height;__weight=_weight;
     do while(hi.next()=0);
      if _height lt height and _weight lt weight then do;
         obs+1;_person+1;_height=height;_weight=weight;
         h.add();_person=person;_height=__height;_weight=__weight;
            end;
     end;
    end;
    h.clear();
    if last then putlog 'The largest possible number is : ' max  ;
    run;
    
    
    
    

    Ksharp

    Linlin
    Lapis Lazuli | Level 10

    Hi Guys,

    I wish I was smart enough to play with you.

    Ksharp
    Super User

    Thank you for your post. Linlin .

    I have already send my resume to Mr. Jason.

    But I am not sure whether they are interesting with a foreigner.

    sas-innovate-2024.png

    Join us for SAS Innovate April 16-19 at the Aria in Las Vegas. Bring the team and save big with our group pricing for a limited time only.

    Pre-conference courses and tutorials are filling up fast and are always a sellout. Register today to reserve your seat.

     

    Register now!

    How to Concatenate Values

    Learn how use the CAT functions in SAS to join values from multiple variables into a single value.

    Find more tutorials on the SAS Users YouTube channel.

    Click image to register for webinarClick image to register for webinar

    Classroom Training Available!

    Select SAS Training centers are offering in-person courses. View upcoming courses for:

    View all other training opportunities.

    Discussion stats
    • 7 replies
    • 1037 views
    • 0 likes
    • 3 in conversation