DATA Step, Macro, Functions and more

Gymnast Tower Routine Puzzle

Reply
Super User
Posts: 10,035

Gymnast Tower Routine Puzzle

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

Trusted Advisor
Posts: 1,301

Re: Gymnast Tower Routine Puzzle

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

Trusted Advisor
Posts: 1,301

Gymnast Tower Routine Puzzle

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

    Super User
    Posts: 10,035

    Re: Gymnast Tower Routine Puzzle

    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.

    Trusted Advisor
    Posts: 1,301

    Gymnast Tower Routine Puzzle

    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

    Super User
    Posts: 10,035

    Gymnast Tower Routine Puzzle

    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

    Super Contributor
    Posts: 1,636

    Gymnast Tower Routine Puzzle

    Hi Guys,

    I wish I was smart enough to play with you.

    Super User
    Posts: 10,035

    Gymnast Tower Routine Puzzle

    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.

    Ask a Question
    Discussion stats
    • 7 replies
    • 408 views
    • 0 likes
    • 3 in conversation