6by9
Raspberry Pi Engineer & Forum Moderator
Raspberry Pi Engineer & Forum Moderator
Posts: 7131
Joined: Wed Dec 04, 2013 11:27 am
Location: ZZ9 Plural Z Alpha, aka just outside Cambridge.

Re: How would you ...... in C ?

Mon Oct 24, 2016 2:25 pm

Paeryn wrote:I think this should work for any size variable, bit of bit twiddling magic...

Code: Select all

#include <stdio.h>

static inline int countBitsInWord(unsigned int word)
{
  word = word - ((word >> 1) & 0x55555555);
  word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
  return ((word + (word >> 4) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int countBits(void *var, int bytes)
{
  int bit_count = 0;
  while (bytes > 3) {
    unsigned int value = *(unsigned int*)var;
    bit_count += countBitsInWord(value);
    var += 4;
    bytes -= 4;
  }
  while (bytes) {
    unsigned int value = *(unsigned char*)var;
    bit_count += countBitsInWord(value);
    var += 1;
    bytes -= 1;
  }
  return bit_count;
}

#define CountBits(var) countBits(&(var), sizeof(var))

int main(void)
{
  int ivar = 10; // 2 bits
  double fvar = 1.23;
  int array[2] = {8, 15}; // 5 bits

  printf("int %d has %d bits\n", ivar, CountBits(ivar));
  printf("int array has %d bits\n", CountBits(array));
  printf("double %f has %d bits\n", fvar, CountBits(fvar));
  return 0;
}
If you did that without looking it up, then very well done. That is generally where a good candidate should get to with a few prods in the right direction :D
PeterO wrote:
jahboater wrote:
6by9 wrote:If I ask what "v &= v - 1" does as an operation then perhaps we'll get another solution (although potentially slower than the while loop).
You still need the while loop? Looks like I have failed the interview :(

Code: Select all

  while( var != 0 )
  {
    ++count;
    var &= var - 1;
  }
Impressive ! I looked at the result of applying it, but in hex it wasn't obvious it always just removed the bottom bit. I don't think I could have got that through a code review at work though :-)
It generally takes a bit of "try feeding some numbers into it" to get anywhere, but the good candidates normally pick up on a pattern.
I would agree that submitting just that should fail code review without a modest amount of commenting to accompany it.

And PiGraham has brought up the look up table as the final method that could be useful.

Between you you've passed that section of interview :D
https://graphics.stanford.edu/~seander/ ... tsSetNaive seems to be a good write up of most of the approaches.

Round 6?
Software Engineer at Raspberry Pi Trading. Views expressed are still personal views.
I'm not interested in doing contracts for bespoke functionality - please don't ask.

PiGraham
Posts: 3574
Joined: Fri Jun 07, 2013 12:37 pm
Location: Waterlooville

Re: How would you ...... in C ?

Mon Oct 24, 2016 4:20 pm

PeterO wrote:
jahboater wrote:
6by9 wrote:If I ask what "v &= v - 1" does as an operation then perhaps we'll get another solution (although potentially slower than the while loop).
You still need the while loop? Looks like I have failed the interview :(

Code: Select all

  while( var != 0 )
  {
    ++count;
    var &= var - 1;
  }
Impressive ! I looked at the result of applying it, but in hex it wasn't obvious it always just removed the bottom bit. I don't think I could have got that through a code review at work though :-)
PererO
That looks neat, but is it better than a shift, and add?

Code: Select all

  
int main(int argc,char *argv[])
{
        int var =0;
        int count=0;
        if(argc<2)
        {
                puts("Enter a number! \n");
                return -1;
        }
        var =atoi(argv[1]);
        count=0;

        while(var)
        {
                count+= var & 0x01;    // Add lsb to bit count
                var >>= 1;        // Shift all bits through lsb
        }

        printf("Value %d has %d bits set\n",val,count);
        return count;
}

Last edited by PiGraham on Mon Oct 24, 2016 4:39 pm, edited 1 time in total.

User avatar
PeterO
Posts: 4940
Joined: Sun Jul 22, 2012 4:14 pm

Re: How would you ...... in C ?

Mon Oct 24, 2016 4:25 pm

We did "shift and add" on the previous page !
PeterO
Discoverer of the PI2 XENON DEATH FLASH!
Interests: C,Python,PIC,Electronics,Ham Radio (G0DZB),1960s British Computers.
"The primary requirement (as we've always seen in your examples) is that the code is readable. " Dougie Lawson

PiGraham
Posts: 3574
Joined: Fri Jun 07, 2013 12:37 pm
Location: Waterlooville

Re: How would you ...... in C ?

Mon Oct 24, 2016 4:36 pm

PeterO wrote:We did "shift and add" on the previous page !
PeterO
OK, I missed it. It's here viewtopic.php?p=1057706#p1057706

Any thoughts on the question? Pros and cons of different methods?
Particularly Paeryn's more obscure approach. does it have an advantage?

6by9
Raspberry Pi Engineer & Forum Moderator
Raspberry Pi Engineer & Forum Moderator
Posts: 7131
Joined: Wed Dec 04, 2013 11:27 am
Location: ZZ9 Plural Z Alpha, aka just outside Cambridge.

Re: How would you ...... in C ?

Mon Oct 24, 2016 4:51 pm

PiGraham wrote:
PeterO wrote:We did "shift and add" on the previous page !
PeterO
OK, I missed it. It's here viewtopic.php?p=1057706#p1057706

Any thoughts on the question? Pros and cons of different methods?
Shift and add will take how ever many iterations as the highest set bit.
x &= (x-1) will only take as many iterations as there are bits set.
So the more bits clear in the variable below the msb then the more "x &= (x-1)" saves.

The logarithmic solution as given by Paeryn has the fewest iterations (log2(N)), but has more computational complexity. It'd need very close analysis to work out exactly which is going to be most efficient in particular situations.

Lookup table is the most computationally efficient for short types (8 or 16 bits), but requires storage. Further question of coding the table in as a const in code, or generating it on first use.

For most cases you don't need to extract every last bit of optimisation from the processor, but then there are times where you do need to do exactly that. Being able to do that analysis is a useful skill, but definitely falls into the "advanced" category.
Software Engineer at Raspberry Pi Trading. Views expressed are still personal views.
I'm not interested in doing contracts for bespoke functionality - please don't ask.

User avatar
Paeryn
Posts: 2634
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: How would you ...... in C ?

Mon Oct 24, 2016 5:06 pm

6by9 wrote:
Paeryn wrote:I think this should work for any size variable, bit of bit twiddling magic...
If you did that without looking it up, then very well done. That is generally where a good candidate should get to with a few prods in the right direction :D
I've known about that method for years, not an immediately obvious way of doing it I admit and not one I would come up with if I didn't need to do it that way (back in the day I needed the speed and lookup tables polluted the cache).

<Edit>
In case anybody is confused how the 32bit count works.
The first line converts pairs of bits into the count of the same 2 bits set (00 -> 00, 01 -> 01, 10 -> 01, 11 -> 10). The second line adds pairs of those 16 2bit counts together to make 8 4bit counts. The third line adds pairs of 4bit counts to make 4 8bit counts and the multiply/shift at the end adds those 4 counts together to give the total bit count for the full 32bit number.
Last edited by Paeryn on Mon Oct 24, 2016 5:30 pm, edited 1 time in total.
She who travels light — forgot something.

jahboater
Posts: 4598
Joined: Wed Feb 04, 2015 6:38 pm

Re: How would you ...... in C ?

Mon Oct 24, 2016 5:23 pm

6by9 wrote: Shift and add will take how ever many iterations as the highest set bit.
x &= (x-1) will only take as many iterations as there are bits set.
So the more bits clear in the variable below the msb then the more "x &= (x-1)" saves.
It looks like "x &= (x-1)" is Brian Kernighan's algorithm which gives it some credence (a truly brilliant software engineer).
6by9 wrote:For most cases you don't need to extract every last bit of optimisation from the processor, but then there are times where you do need to do exactly that. Being able to do that analysis is a useful skill, but definitely falls into the "advanced" category.
Intel included the popcnt instruction to speed up this operation.
5 bytes and 3 clock cycles for 64-bit operand on a skylake CPU beats all of the above algorithms!

PiGraham
Posts: 3574
Joined: Fri Jun 07, 2013 12:37 pm
Location: Waterlooville

Re: How would you ...... in C ?

Mon Oct 24, 2016 6:33 pm

6by9 wrote:
PiGraham wrote:
PeterO wrote:We did "shift and add" on the previous page !
PeterO
OK, I missed it. It's here viewtopic.php?p=1057706#p1057706

Any thoughts on the question? Pros and cons of different methods?
Shift and add will take how ever many iterations as the highest set bit.
x &= (x-1) will only take as many iterations as there are bits set.
So the more bits clear in the variable below the msb then the more "x &= (x-1)" saves.

The logarithmic solution as given by Paeryn has the fewest iterations (log2(N)), but has more computational complexity. It'd need very close analysis to work out exactly which is going to be most efficient in particular situations.

Lookup table is the most computationally efficient for short types (8 or 16 bits), but requires storage. Further question of coding the table in as a const in code, or generating it on first use.

For most cases you don't need to extract every last bit of optimisation from the processor, but then there are times where you do need to do exactly that. Being able to do that analysis is a useful skill, but definitely falls into the "advanced" category.
Good comments, thanks.

The use of the borrow to 'find and clear ' the lowest set bit is nice. It seems that shift and sub are equal in cycles on ARM so that will be quicker on average.

As you say, evaluating Paeryn's version would take some work.

User avatar
rurwin
Forum Moderator
Forum Moderator
Posts: 4258
Joined: Mon Jan 09, 2012 3:16 pm
Contact: Website

Re: How would you ...... in C ?

Tue Oct 25, 2016 10:57 am

Round 6:

A pair of functions to convert betwween a Gregorian date and the Julian day number.
You can assume all the standard C library except the date functions (maybe you're writing that library).

A Gregorian date is a normal one represented by three integers: Day, Month, Year
The Julian day number is the number of days since noon on January 1, 4713 BC, but for the sake of this exercise you can assume 1/1/2000 is Julian day number 2451544.5

You can assume the Gregorian calander (there are at least three different change-over dates so trying to allow for them is ambiguous) but, with that proviso, the functions should work for any date past or future.

Here's a web-page to test your work: http://quasar.as.utexas.edu/BillInfo/Ju ... eCalc.html

User avatar
Paeryn
Posts: 2634
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: How would you ...... in C ?

Tue Oct 25, 2016 4:25 pm

Think this should do it... For the julian->gregorian conversion I gave up calculating it mathematically half way through and counted backwards days in months which is why it's more long winded. I'm not at home and my back is aching from typing at this awkward angle.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

typedef struct gregorianDate_t {
  int day;
  int month;
  int year;
} gregorianDate_t;

float julianDay(gregorianDate_t *g_date)
{
  int m = (g_date->month + 9) % 12; // Months since March
  int y = g_date->year + 4800 - (m>=10); // Years since March 1st -4800

  // months to days is based on days in March-July and Aug-Dec all being
  // 31-30-31-30-31, and Jan-Feb 31-28. Leapyears dealt later
  int julian = g_date->day + ((153*m+2)/5) + 365*y - 32045;
  julian += (y/4) - (y/100) + (y/400); // Add a day for each leap year

  return julian - 0.5f; // Julian day starts at noon
}

gregorianDate_t *gregorianDate(gregorianDate_t *gregorian_date, float julian_day)
{
  // Allocate memory to hold date if not passed in.
  if (gregorian_date == NULL)
    if ((gregorian_date = malloc(sizeof *gregorian_date)) == NULL)
      return NULL;
  
  int julian = (int)(julian_day + 0.5f);

  julian += 32045;
  int year = (int)((float)julian / 365.2425f); // .2425 accounts for leap years
  julian = (int)((float)julian) - (float)year * 365.2425f);
  year -= 4800;

  int monthday[12] = {31,30,31,30,31, 31,30,31,30,31, 31, 29};
  int month = 0;
  while (julian >= monthday[month]) {
    julian -= monthday[month];
    month++;
  }
  if (month > 9)
    year += 1;
  gregorian_date->year = year;
  gregorian_date->month = (month+2) % 12 + 1;
  gregorian_date->day = julian+1;
  return gregorian_date;
}

void printGregorian(gregorianDate_t *g_date)
{
  printf("%d/%d/%d", g_date->day, g_date->month, g_date->year);
}
  
int main(void)
{
  gregorianDate_t *date, jan2000 = {1,1,2000};
  float jday = julianDay(&jan2000);

  printGregorian(&jan2000);
  printf(" = JD %f\n", jday);
  date = gregorianDate(NULL, jday);
  if (date) {
    printf("and back to ");
    printGregorian(date);
    putchar('\n');
    free(date);
  }
  return 0;
}
<Edit>
There's a bug in converting dates back from Julian days (leap days get added in the wrong years). Trying to do it in floats isn't the best of ideas. Abandoning it now.
Last edited by Paeryn on Wed Oct 26, 2016 7:38 pm, edited 1 time in total.
She who travels light — forgot something.

User avatar
rurwin
Forum Moderator
Forum Moderator
Posts: 4258
Joined: Mon Jan 09, 2012 3:16 pm
Contact: Website

Re: How would you ...... in C ?

Wed Oct 26, 2016 5:27 pm

Here's mine.

Code: Select all

#include <stdio.h>

double DayNumber(int day, int month, int year)
{
	long a,b,c;

	if (month > 2)
	{
		month -= 3;
	}
	else
	{
		month += 9;
		year -= 1;
	}
    a = ((year%100) * 1461) / 4;
	b = ((year/100) * 146097) / 4;
	c = (month * 153 + 2) / 5;
	return a + b + c + day + 1721118.5;
}

void Date (double daynumber, int *day, int *month, int *year)
{
	long r, a, centuries, pentdays, quarterdays, years;

	quarterdays = ((int)(daynumber - 1721118.5)) * 4 - 1;

	r = quarterdays % 146097;
	centuries = quarterdays / 146097;

	a = (r / 4) * 4 + 3;

	r = a % 1461;
	years = a / 1461;

	pentdays = (r / 4) * 5 + 2;

	*month = pentdays / 153;
	pentdays = pentdays % 153;
	
	*day = pentdays / 5 + 1;

	*year = (centuries * 100) + years;

	if (*month < 10)
	{
		*month += 3;
	}
	else
	{
		*month -= 9;
		*year += 1;
	}

}


int main (int argc, char**argv)
{
	int d, m, y, day;

	printf("1.  1721118.5 = %8.1f\n", DayNumber(28,2,0));
	printf("2.  2369915.5 = %8.1f\n", DayNumber(4,7,1776));
	printf("3.  2440423.5 = %8.1f\n", DayNumber(21,7,1969));
	printf("4.  2451544.5 = %8.1f\n", DayNumber(1,1,2000));
	printf("5.  2489588.5 = %8.1f\n", DayNumber(29,2,2104));
	printf("5.  2889894.5 = %8.1f\n", DayNumber(29,2,3200));
	printf("6.  2816846.5 = %8.1f\n", DayNumber(1,3,3000));
	
	
	Date(1721118.5, &d, &m, &y); printf("7.  1/3/0 = %d/%d/%d\n", d, m, y);
	Date(2369915.5, &d, &m, &y); printf("8.  4/7/1776 = %d/%d/%d\n", d, m, y);
	Date(2440423.5, &d, &m, &y); printf("9.  21/7/1969 = %d/%d/%d\n", d, m, y);
	Date(2451544.5, &d, &m, &y); printf("10.  1/1/2000 = %d/%d/%d\n", d, m, y);
	Date(2489588.5, &d, &m, &y); printf("11.  29/2/2104 = %d/%d/%d\n", d, m, y);
	Date(2889894.5, &d, &m, &y); printf("12.  29/2/3200 = %d/%d/%d\n", d, m, y);
	Date(2816846.5, &d, &m, &y); printf("13.  1/3/3000 = %d/%d/%d\n", d, m, y);
	
	return 0;
}
I did go over it and try to put obvious variable names in, but it's impossible to make it any more obvious. If you understand Date() in particular, you have mastered integer arithmetic.

Hint: there are 146097 days in 400 years.

PiGraham
Posts: 3574
Joined: Fri Jun 07, 2013 12:37 pm
Location: Waterlooville

Re: How would you ...... in C ?

Thu Oct 27, 2016 8:50 am

rurwin wrote:Hint: there are 146097 days in 400 years.
Not a criticism, but since you mentioned naming you could do:

Code: Select all

static const int DaysIn400Years = 146097;
//or
#define DAYS_IN_400_YEARS 146097
;)

User avatar
rurwin
Forum Moderator
Forum Moderator
Posts: 4258
Joined: Mon Jan 09, 2012 3:16 pm
Contact: Website

Re: How would you ...... in C ?

Thu Oct 27, 2016 9:35 am

True, but then you need

Code: Select all

#define DAYS_IN_FOUR_YEARS_ASSUMING_CENTURIES_ARE_LEAP_YEARS_WHICH_THEYRE_NOT_REALLY 1461
#define DAYS_IN_FIVE_MONTHS_ASSUMING_THEYRE_THE_RIGHT_FIVE_MONTHS 153
#define JULIAN_DAY_FOR_1ST_MARCH_1BC_ASSUMING_THE_GREGORIAN_CALENDAR_WAS_USED_BACK_THEN_WHICH_IS_WRONG_BY_OVER_A_MILLENIA_AND_A_HALF_AND_THAT_NOBODY_MISCOUNTED_WHEN_THEY_DID_MAKE_THE_CORRECTION 1721118.5

PiGraham
Posts: 3574
Joined: Fri Jun 07, 2013 12:37 pm
Location: Waterlooville

Re: How would you ...... in C ?

Thu Oct 27, 2016 11:54 am

:lol:

Still the slightly serious point is that informative naming of constants is generally a good idea.

User avatar
woodystanford
Posts: 122
Joined: Sun Feb 19, 2017 8:17 am

Re: How would you ...... in C ?

Sun Feb 26, 2017 11:05 pm

PeterO wrote:So.... Given an integer "hours" which is guaranteed to have a value in the range 0 to 23, how would you print it in the form "12 AM", or " 1 PM".
ok, how about:

Code: Select all

#include <stdio.h>
main()
{

   int hrs=5;
   char s[255];

   switch(hrs)
   {
        case 0: strcpy(s,"12 AM"); break;
        case 1: strcpy(s,"1 AM"); break;
        case 2: strcpy(s,"2 AM"); break;
        case 3: strcpy(s,"3 AM"); break;
        case 4: strcpy(s,"4 AM"); break;
        case 5: strcpy(s,"5 AM"); break;
        case 6: strcpy(s,"6 AM"); break;
        case 7: strcpy(s,"7 AM"); break;
        case 8: strcpy(s,"8 AM"); break;
        case 9: strcpy(s,"9 AM"); break;
        case 10: strcpy(s,"10 AM"); break;
        case 11: strcpy(s,"11 AM"); break;
        case 12: strcpy(s,"12 AM"); break;
        case 13: strcpy(s,"1 PM"); break;
        case 14: strcpy(s,"2 PM"); break;
        case 15: strcpy(s,"3 PM"); break;
        case 16: strcpy(s,"4 PM"); break;
        case 17: strcpy(s,"5 PM"); break;
        case 18: strcpy(s,"6 PM"); break;
        case 19: strcpy(s,"7 PM"); break;
        case 20: strcpy(s,"8 PM"); break;
        case 21: strcpy(s,"9 PM"); break;
        case 22: strcpy(s,"10 PM"); break;
        case 23: strcpy(s,"11 PM"); break;
        default: strcpy(s,"Out of Range"); break;
   }

   printf("Hour %d is in text %s\n\n",hrs,s);

}  


Good problem gotta say. I kind of speed thru these to keep sharp.

And DON'T think I'm trying to learn C this way....ooohhhh.....you burn me up sometimes, Peter :(

User avatar
woodystanford
Posts: 122
Joined: Sun Feb 19, 2017 8:17 am

Re: How would you ...... in C ?

Sun Feb 26, 2017 11:42 pm

PiGraham wrote:
PeterO wrote:Anyone care to propose "Round 2" ?
PeterO
How about:

A simple and easily extensible command interpreter.

Hold the position of a hypothetical bot in integer variables X and Y.
Decode command stings and apply values as increments to X,Y:

forward nn
back nn
left nn
right nn

Where nn is an integer distance.
Assume movement is orthogonal with no rotation and no slippage.
Discussion point (not competition entry), but pertains to system engineering.

How about if we assume the target platform is the R-Pi, we could use Peter's algorythm and drop it into Daemon1 here:

viewtopic.php?f=33&t=175567

That way we can put it in UN*X's autoexec.bat (and until they tell us how to do this, that's what I'm going to call it lol), have it running in the background. Then you can send it forward, back,left, right commands via file (maybe do the guidance in python...it doesn't matter where the command files come from) and then we'll do the PWM or GPIO-based relay out to the motors on the R-PI in C daemon.

We could even code part of the guidance in the daemon too. Just saying we have some flexibility there. We could add telemetry with wifi just by dropping in an FTP Server and HTTP server around Daemon1 so we can load new travel plans by external laptop or something.

Just thinking out loud.

User avatar
woodystanford
Posts: 122
Joined: Sun Feb 19, 2017 8:17 am

Re: How would you ...... in C ?

Mon Feb 27, 2017 12:27 am

stephj wrote:

Code: Select all

f1=0;
f2=1;

while(len(str(f2))<50):
    f3=f1+f2;
    f1=f2;
    f2=f3;

print(f2);
Idioms...how about this one?

What you do here is a "translate" between python and C. You don't even really need to know what is going on either with the algorythm (I mean you have to know something about it), you just translate it piece by piece.

If I knew python better I would have just spoken the C translation of it.

But I'll give it a whirl anyways (I don't let not knowing how to do things interfere with me getting them done):

Code: Select all

//f1=0;
long f1;
//f2=1;
long f2;

//while(len(str(f2))<50):
//    f3=f1+f2;
//    f1=f2;
//    f2=f3;

while (strlen(ltostr(f2))<50)
{
   f3=f1+f2;
   f1=f2;
   f2=f3;
}
//print(f2);
printf("%ld",f2);

Something like that right? lmfao. My first guess...

User avatar
Paeryn
Posts: 2634
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: How would you ...... in C ?

Mon Feb 27, 2017 2:09 pm

woodystanford wrote: What you do here is a "translate" between python and C. You don't even really need to know what is going on either with the algorythm (I mean you have to know something about it), you just translate it piece by piece.

If I knew python better I would have just spoken the C translation of it.

But I'll give it a whirl anyways (I don't let not knowing how to do things interfere with me getting them done):
Well, knowing helps a lot, there are numerous errors in your attempt, not least :-

1) It's not a valid program, not even a full function, just a few lines of code.
2) You never declared f3.
3) You never initialise either f1 or f2. If they are local variables then they could have random values, if global they will at least be initialised to 0 but the original code says f2 should be 1.
4) There's no standard function ltostr(), you could use snprintf(). There have been implementations, but not part of the C standard library.
5) The maximum size of a 32-bit long is 10 digits, even a 64-bit long would only be 20 digits. You need at least a 167-bit unsigned integer to fully hold a 50 digit number (though you could get away with 164-bits, that allows the first digit of a 50 digit number to be 2 which would be sufficient for this example).

So your code will sit in an infinite loop adding 0 to 0, the length will never be more than 1. Even initialising f1 and f2 properly will still result in an infinite loop as the result will keep wrapping around every time the value overflows the size of the type so you'll never get more than 10 (32-bit) or 20 (64-bit) digits (though you will get a length of 11 or 21 occasionally due to the minus sign appearing now and then).

Python handles it as it uses arbitrary precision integers, I think it uses the gmp (gnu multi-precision) library for it.
She who travels light — forgot something.

User avatar
PeterO
Posts: 4940
Joined: Sun Jul 22, 2012 4:14 pm

Re: How would you ...... in C ?

Mon May 22, 2017 9:23 am

Seeing this thread viewtopic.php?f=33&t=184264 I thought it would be a good time to resurrect this thread :)

So how would you do it ?

PeterO
Discoverer of the PI2 XENON DEATH FLASH!
Interests: C,Python,PIC,Electronics,Ham Radio (G0DZB),1960s British Computers.
"The primary requirement (as we've always seen in your examples) is that the code is readable. " Dougie Lawson

User avatar
rurwin
Forum Moderator
Forum Moderator
Posts: 4258
Joined: Mon Jan 09, 2012 3:16 pm
Contact: Website

Re: How would you ...... in C ?

Mon May 22, 2017 1:57 pm

Code: Select all

void loop()
{
    typedef enum { Start, Got1, Got12, Got123} States;
    static States state = Start;
    States FailState;
    bool printit = true;
    char keypressed = myKeypad.getKey();

    if (keypressed != NO_KEY)
    {
        if (keypressed == '1')
            FailState = Got1;
        else
            FailState = Start;

        switch (state)
        {
        case Start:
            if (keypressed == '1')
                state = Got1;
            break;

        case Got1:
            if (keypressed == '2')
                state = Got12;
            else
                state = FailState;
            break;

        case Got12:
            if (keypressed == '3')
                state = Got123;
            else
                state = FailState;
            break;

        case Got123:
            if (keypressed == '#')
            {
                state = Start;
                printit = false;
                Serial.print("Hooray!");
            }
            else
                state = FailState;
            break;
        }

        if (printit)
            Serial.print(keypressed);
    }
}
And now for the contentious one...

Code: Select all

void loop()
{
    typedef enum { Start, Got1, Got12, Got123} States;
    static States state = Start;
    bool printit = true;
    char keypressed = myKeypad.getKey();

    if (keypressed != NO_KEY)
    {
TryAgain:
        switch (state)
        {
        case Start:
            if (keypressed == '1')
                state = Got1;
            break;

        case Got1:
            if (keypressed == '2')
                state = Got12;
            else
            {
                state = Start;
                goto TryAgain;
            }
            break;

        case Got12:
            if (keypressed == '3')
                state = Got123;
            else
            {
                state = Start;
                goto TryAgain;
            }
            break;

        case Got123:
            if (keypressed == '#')
            {
                state = Start;
                printit = false;
                Serial.print("Hooray!");
            }
            else
            {
                state = Start;
                goto TryAgain;
            }
            break;
        }

        if (printit)
            Serial.print(keypressed);
    }
}

User avatar
Paeryn
Posts: 2634
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: How would you ...... in C ?

Mon May 22, 2017 2:30 pm

PeterO wrote:Seeing this thread viewtopic.php?f=33&t=184264 I thought it would be a good time to resurrect this thread :)

So how would you do it ?

PeterO
Made into a full program and allowing choosing the key rather than hard coding. Uses ncurses to simulate Keypad input and Serial printing.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ncurses.h>

struct Keypad_t {
    int (*getKey)(void);
} myKeypad;

struct Serial_t {
    int (*print)(const char *, ...);
} Serial;

#define NO_KEY ERR

/* readKeyString:
 *
 * Reads characters from the keyboard and checks against key
 *
 * returns:
 *   1 when the key has been entered correctly.
 *  -1 if a null pointer was passed as the key.
 */
static int readKeyString(const char *key)
{
    if (key == NULL)
        return -1;
    
    size_t length = strlen(key);
    size_t num_valid_chars = 0;
    int possibly_valid = 1;
    
    while (1) {
        int keypressed = myKeypad.getKey();
        if (keypressed == '#') {
            if (possibly_valid && num_valid_chars == length) {
                Serial.print("Hooray!");
                return 1;
            }
            Serial.print("Booo");
            num_valid_chars = 0;
            possibly_valid = 1;
        }
        else if (possibly_valid &&
                 num_valid_chars < length &&
                 keypressed == key[num_valid_chars]) {
            num_valid_chars++;
        }
        else if (keypressed != NO_KEY) {
            possibly_valid = 0;
        }
        Serial.print("%c", keypressed);
    }
}
    
int main(int argc, char *argv[])
{
    char *keystr;

    if (argc < 2) {
        printf("Program to wait for user to enter provided key string.\n"
               "Usage:\n%s <keystring>\n", argv[0]);
        exit(1);
    }
    else if (argc >2) {
        printf("Error: Too many key strings (only 1 allowed).\n");
        exit(1);
    }
    size_t key_length = strlen(argv[1]);
    keystr = malloc(key_length + 1);
    strcpy(keystr, argv[1]);

    initscr();
    printw("Enter the key followed by # to continue.\n");
    refresh();
    noecho();
    keypad(stdscr, TRUE);

    Serial.print = printw;
    myKeypad.getKey = getch;
    
    int retval = readKeyString(keystr);

    endwin();

    switch (retval) {
    case -1:
        printf("You tried passing a null pointer as key string\n");
        break;
    case 1:
        printf("You entered the key correctly\n");
        break;
    default:
        printf("Unknown return from readKeyString()\n");
    }
    
    free(keystr);
    return 0;
}
<Edit> I originally used ncurses' ERR instead of the original NO_KEY, #define it... And added static to the definition of readKeyString(). And fixed one of the error messages (I left a word in from what I originally wrote).
Last edited by Paeryn on Mon May 22, 2017 6:50 pm, edited 2 times in total.
She who travels light — forgot something.

User avatar
PeterO
Posts: 4940
Joined: Sun Jul 22, 2012 4:14 pm

Re: How would you ...... in C ?

Mon May 22, 2017 2:35 pm

I like the "state machine" approach. Here's my take on it....

Code: Select all

#include <stdio.h>
#include <unistd.h>
#include <termios.h>
#include <stdbool.h>

static bool loop(bool first)
{
    char keypressed;
    static const char *combination = "1234#";
    static int nextToMatch = 0;
    ssize_t numRead;

    if(first) nextToMatch = 0;

    /* OP's code had
       char keypressed = myKeypad.getKey();
       if (keypressed != NO_KEY)
    */
    numRead = read(STDIN_FILENO,&keypressed,1);
    if(numRead == 1)
    {
        printf("Read <%c>\n",keypressed);
        if(keypressed == combination[nextToMatch])
        {
            if(keypressed == '#')
            {
                printf("Open Sesame\n");
                return true;
            }
            // Move on to next key
            nextToMatch += 1;
        }
        else
            // Go back to start on a wrong key
            nextToMatch = 0;
    }
    return false;
}


int main(__attribute__((unused)) int argc, __attribute__((unused)) char **argv)
{
    bool start;
    struct termios old,new;


    /* Set up stdin to act like myKeypad.getKey() in OP's code */
    tcgetattr(STDIN_FILENO,&old);
    new = old;
    new.c_lflag&=(unsigned) ~ICANON;
    new.c_lflag&=(unsigned) ~ECHO;
    new.c_cc[VMIN] = 0;
    new.c_cc[VTIME] = 0;
    tcsetattr(STDIN_FILENO,TCSANOW,&new);
    
    /* Make sure "loop" starts correctly if it is used more than once! */
    start = true;
    /* Assume OP's code did this... */
    while(!loop(start)) start = false;

    tcsetattr(STDIN_FILENO,TCSANOW,&old);

    return 0;
}
PeterO

PS: Mods to make sure state variable is reset on first call.
Last edited by PeterO on Mon May 22, 2017 4:27 pm, edited 2 times in total.
Discoverer of the PI2 XENON DEATH FLASH!
Interests: C,Python,PIC,Electronics,Ham Radio (G0DZB),1960s British Computers.
"The primary requirement (as we've always seen in your examples) is that the code is readable. " Dougie Lawson

User avatar
Paeryn
Posts: 2634
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: How would you ...... in C ?

Mon May 22, 2017 2:59 pm

I wasn't sure if the intended behaviour of overly long entries that ended with the correct sequence was to be considered valid. I originally had it that way and then decided it shouldn't accept e.g. 5123# so I changed my implementation to require exactly 123#, with the # resetting the entry when an invalid code was tried.
She who travels light — forgot something.

User avatar
PeterO
Posts: 4940
Joined: Sun Jul 22, 2012 4:14 pm

Re: How would you ...... in C ?

Mon May 22, 2017 3:09 pm

Paeryn wrote:I wasn't sure if the intended behaviour of overly long entries that ended with the correct sequence was to be considered valid. I originally had it that way and then decided it shouldn't accept e.g. 5123# so I changed my implementation to require exactly 123#, with the # resetting the entry when an invalid code was tried.
Fair enough. We didn't have a specification to work to ! And clean code too, but not quite "clean and shiny code" by jahboater's standard ;) (I'm not taking the blame for this :lol: )

Code: Select all

gcc $ALLCFLAGS -o combination2 combination2.c  -lncurses
combination2.c:24:5: warning: no previous prototype for ‘readKeyString’ [-Wmissing-prototypes]
 int readKeyString(const char *key)
     ^


PeterO
Discoverer of the PI2 XENON DEATH FLASH!
Interests: C,Python,PIC,Electronics,Ham Radio (G0DZB),1960s British Computers.
"The primary requirement (as we've always seen in your examples) is that the code is readable. " Dougie Lawson

jahboater
Posts: 4598
Joined: Wed Feb 04, 2015 6:38 pm

Re: How would you ...... in C ?

Mon May 22, 2017 4:20 pm

trivia (but given your sig ;) ) ....

int main(void)

is a valid signature for main() and is more readable than

int main(__attribute__((unused)) int argc, __attribute__((unused)) char **argv)

There's two ;; after the loop in main.

Return to “C/C++”