Counting sort in C apparently works but binarysearch doesn't
I am looking for help regarding the implementation of a counting sort function in the CS50 Course in week 3.
An int Array has to be sorted. I tested various unsorted arrays and my counting sort function seems to sort the array just correctly, yet my search functions won't work on the sorted array after. Could someone give me a hint?
void countsort( int array[], int size) {
int count=0;
int zahl=0;
int max=65536;
int countarr [max];
int finalarr [size];
memset (countarr, 0, sizeof(countarr));
for(int i=0;i<size;i++) {
zahl=array[i];
countarr[zahl]++;
}
for(int i=0;i<max;i++) {
while(countarr[i]>0) {
finalarr[count]=i;
countarr[i]--;
count++;
}
}
array=finalarr;
for(int i=0;i<size;i++){
printf(" %i ",array[i]);
}
}
This is my search algorithm used after the array is sorted, it works with sort algorithms from other people.
bool binarysearch(int value, int values[], int n){
int start=0,
end=n,
mid=0,
midpos=0;
while(end>0) {
midpos=(start+end)/2;
mid=values[midpos];
if(mid==value) return true;
if(mid<value) start=++midpos;
if(mid>value) end=--midpos;
}
return false;
}
1 answer
-
answered 2017-06-17 18:52
Gassa
In
binarysearch
, the loop conditionwhile(end>0)
is wrong. If we search for a value which is greater than at least one of the elements of the array,end
will never be zero. Try changing it towhile(end>=start)
, which literally means that the considered interval is non-empty.In
countsort
, the linearray=finalarr;
does not copy the whole array. Instead, the local variablearray
becomes a pointer tofinalarr
. The contents of the original array remain unchanged, and the sorted array is gone when you exit the function. This explains why your binary search works (better) with other sort functions.
Try changingfinalarr[count]=i;
toarray[count]=i;
and get rid offinalarr
completely, putting the values intoarray
right away. Alternatively, you can usememmove
instead of that line.
See also questions close to this topic
-
Program that checks for a valid Unix FTP Command (Not working)
I can compile this program in Unix (Sun-Solaris) to be specific, but I cant get it to run (Im un a Unix course and all of our programs/assignments are to be done on the schools servers). Hes only been teaching us C in the last 2 weeks of the course. Im fairly new to C and cant figure out why it is not working. Any help would be appreciated. I did some research on the error but unfortunately the methods I tried/found online either didnt work or im not doing them properly.
Code below.
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> char** splitString(char* inputString, const char delim) { char** output = 0; size_t c = 0; char* temp = inputString; char* final_space = 0; char delimiter[2]; delimiter[0] = delim; delimiter[1] = 0; while(*temp) { if(delim == *temp) { c++; final_space = temp; } temp++; } c += final_space < (inputString + strlen(inputString) - 1); c++; output = malloc(sizeof(char*) * c); if(output) { size_t index = 0; char* output = strtok(inputString, delimiter); while(output) { assert(index < c); *(output + index++) = strdup(output); output = strtok(0, delimiter); } assert(index == c - 1); *(output + index) = 0; } return output; } void main() { char input[50]; char** splitInput = NULL; int rs; printf("please enter a Unix FTP cmd. The program will check to see if it is a valid cmd: "); gets(input); splitInput = splitString(input, ' '); printf("input[%s]", *(splitInput)); rs = strcmp(*(splitInput), "ascii"); if(rs == 0) { printf("ascii is a valid ftp command\n"); return; } rs = strcmp(*(splitInput), "recv"); if(rs == 0) { printf("recv is a valid ftp command\n"); free(splitInput); printf("the entered cmd is %s", *(splitInput + 1)); return; } rs = strcmp(*(splitInput), "get"); if(rs == 0) { printf("get is a valid ftp command\n"); free(splitInput); printf("the entered cmd is %s", *(splitInput + 1)); return; } rs = strcmp(*(splitInput), "send"); if(rs == 0) { printf("send is a valid ftp command\n"); free(splitInput); printf("the entered cmd is %s", *(splitInput + 1)); return; } rs = strcmp(*(splitInput), "put"); if(rs == 0) { printf("put is a real Unix FTP cmd\n"); free(splitInput); printf("the entered cmd is %s", *(splitInput + 1)); return; } rs = strcmp(*(splitInput), "rmdir"); if(rs == 0) { printf("rmdir is a real Unix FTP cmd\n"); printf("the entered cmd is %s", *(splitInput + 1)); return; } rs = strcmp(*(splitInput), "mkdir"); if(rs == 0) { printf("mkdir is a real Unix FTP cmd\n"); free(splitInput); printf("the entered cmd is %s", *(splitInput + 1)); return; } rs = strcmp(*(splitInput), "rmdir"); if(rs == 0) { printf("rmdir is a real Unix FTP cmd\n"); free(splitInput); printf("the entered cmd is %s", *(splitInput + 1)); return; } rs = strcmp(*(splitInput), "ls"); if(rs == 0) { printf("ls a real Unix FTP cmd\n"); free(splitInput); printf("the entered cmd is %s", *(splitInput + 1)); return; } rs = strcmp(*(splitInput), "cd"); if(rs == 0) { printf("cd is a real Unix FTP cmd\n"); free(splitInput); printf("the entered cmd is %s", *(splitInput + 1)); return; } rs = strcmp(*(splitInput), "status"); if(rs == 0) { printf("status is a valid ftp command\n"); return; } rs = strcmp(*(splitInput), "quit"); if(rs == 0) { printf("quit is a valid ftp command\n"); return; } else { printf(*(splitInput), " isn't a real Unix FTP cmd"); } return; }
This is a screenshot of the error I get: Error inside PuTTy console
-
C - Algorithm for Bitwise operation on Modulus for number of not a power of 2
I know that modulo of power of 2 can be calculated using bitwise operator
x % 2^n == x & (2^n - 1).
But I am wondering is there any generalized bitwise algorithm exists to find the modulus of any number is not a power of 2. For example,
7%5
Thank you in advance.
-
Piping/dup2() not working properly (Implementing Unix Shell in C)
I'll post my code first, then explain the problem I'm having:
#include <stdio.h> #include <sys/wait.h> #include <unistd.h> #include <string.h> #include <stdlib.h> #include <fcntl.h> #define MAX_ARGS 20 #define BUFSIZE 1024 int get_args(char* cmdline, char* args[]) { int i = 0; /* if no args */ if((args[0] = strtok(cmdline, "\n\t ")) == NULL) return 0; while((args[++i] = strtok(NULL, "\n\t ")) != NULL) { if(i >= MAX_ARGS) { printf("Too many arguments!\n"); exit(1); } } /* the last one is always NULL */ return i; } void execute(char* cmdline) { int pid, async, oneapp; char* args[MAX_ARGS]; char* args2[] = {"-l", NULL}; int nargs = get_args(cmdline, args); if(nargs <= 0) return; if(!strcmp(args[0], "quit") || !strcmp(args[0], "exit")) { exit(0); } printf("before the if\n"); printf("%s\n",args[nargs - 2]); int i = 0; // EDIT: THIS IS WHAT WAS SUPPOSED TO BE COMMENTED OUT /* while (args[i] != ">" && i < nargs - 1) { printf("%s\n",args[i]); i++; } */ // Presence of ">" token in args // causes errors in execvp() because ">" is not // a built-in Unix command, so remove it from args args[i - 1] = NULL; printf("Escaped the while\n"); // File descriptor array for the pipe int fd[2]; // PID for the forked process pid_t fpid1; // Open the pipe pipe(fd); // Here we fork fpid1 = fork(); if (fpid1 < 0) { // The case where the fork fails perror("Fork failed!\n"); exit(-1); } else if (fpid1 == 0) { //dup2(fd[1], STDOUT_FILENO); close(fd[1]); //close(fd[0]); // File pointer for the file that'll be written to FILE * file; // freopen() redirects stdin to args[nargs - 1], // which contains the name of the file we're writing to file = freopen(args[nargs - 1], "w+", stdin); // If we include this line, the functionality works //execvp(args[0],args); // We're done writing to the file, so close it fclose(file); // We're done using the pipe, so close it (unnecessary?) //close(fd[1]); } else { // Wait for the child process to terminate wait(0); printf("This is the parent\n"); // Connect write end of pipe (fd[1]) to standard output dup2(fd[1], STDOUT_FILENO); // We don't need the read end, so close it close(fd[0]); // args[0] contains the command "ls", which is // what we want to execute execvp(args[0], args); // This is just a test line I was using before to check // whether anything was being written to stdout at all printf("Exec was here\n"); } // This is here to make sure program execution // doesn't continue into the original code, which // currently causes errors due to incomplete functionality exit(0); /* check if async call */ printf("Async call part\n"); if(!strcmp(args[nargs-1], "&")) { async = 1; args[--nargs] = 0; } else async = 0; pid = fork(); if(pid == 0) { /* child process */ execvp(args[0], args); /* return only when exec fails */ perror("exec failed"); exit(-1); } else if(pid > 0) { /* parent process */ if(!async) waitpid(pid, NULL, 0); else printf("this is an async call\n"); } else { /* error occurred */ perror("fork failed"); exit(1); } } int main (int argc, char* argv []) { char cmdline[BUFSIZE]; for(;;) { printf("COP4338$ "); if(fgets(cmdline, BUFSIZE, stdin) == NULL) { perror("fgets failed"); exit(1); } execute(cmdline) ; } return 0; }
So, what's the problem? Simple: the code above creates a file with the expected name, i.e. the name provided in the command line, which gets placed at args[nargs - 1]. For instance, running the program and then typing
ls > test.txt
Creates a file called test.txt... but it doesn't actually write anything to it. I did manage to get the program to print garbage characters to the file more than a few times, but this only happened during bouts of desperate hail mary coding where I was basically just trying to get the program to write SOMETHING to the file.
I do think I've managed to narrow down the cause of the problems to this area of the code:
else if (fpid1 == 0) { printf("This is the child.\n"); //dup2(fd[1], STDOUT_FILENO); close(fd[1]); //close(fd[0]); // File pointer for the file that'll be written to FILE * file; // freopen() redirects stdin to args[nargs - 1], // which contains the name of the file we're writing to file = freopen(args[nargs - 1], "w+", stdout); // If we include this line, the functionality works //execvp(args[0],args); // We're done writing to the file, so close it fclose(file); // We're done using the pipe, so close it (unnecessary?) //close(fd[1]); } else { // Wait for the child process to terminate wait(0); printf("This is the parent\n"); // Connect write end of pipe (fd[1]) to standard output dup2(fd[1], STDOUT_FILENO); // We don't need the read end, so close it close(fd[0]); // args[0] contains the command "ls", which is // what we want to execute execvp(args[0], args); // This is just a test line I was using before to check // whether anything was being written to stdout at all printf("Exec was here\n"); }
More specifically, I believe the problem is with the way I'm using (or trying to use) dup2() and the piping functionality. I basically found this out by process of elimination. I spent a few hours commenting things out, moving code around, adding and removing test code, and I've found the following things:
1.) Removing the calls to dup2() and using execvp(args[0], args) prints the result of the ls command to the console. The parent and child processes begin and end properly. So, the calls to execvp() are working properly.
2.) The line
file = freopen(args[nargs - 1], "w+", stdout)
Successfully creates a file with the correct name, so the call to freopen() isn't failing. While this doesn't immediately prove that this function is working properly as it's written now, consider fact #3:
3.) In the child process block, if we make freopen redirect to the output file from stdin (rather than stdout) and uncomment the call to execvp(args[0], args), like so:
// freopen() redirects stdin to args[nargs - 1], // which contains the name of the file we're writing to file = freopen(args[nargs - 1], "w+", stdin); // If we include this line, the functionality works execvp(args[0],args);
and run the program, then it works and result of the ls command is successfully written to the output file. Knowing this, it seems pretty safe to say that freopen() isn't the problem either.
In other words, the only thing I haven't been able to successfully do is pipe the output of the execvp() call that's done in the parent process to stdout, and then from stdout to the file using freopen().
Any help is appreciated. I've been at this since 10 AM yesterday and I'm completely out of ideas. I just don't know what I'm doing wrong. Why isn't this working?
-
Efficient node traffic allocation
Users can be assigned to one experiment on my site. I have an API that developers use to trigger logic for each experiment. They call ExperimentEngine.run() to trigger the code logic for the experiment.
I would like to allocate traffic to each experiment at exposure, at the point where a user might be exposed to the logic for that experiment. I would like to allocate traffic so that experiments that users usually see last don't get starved.
For example, if user A is exposed to experiment A at login and then goes to page B and get's exposed to experiment B, the user A should be assigned to either experiment A or B at point exposure. That means that they will only see one of the experiments and not both (either A or B) or neither. I would like to figure out the right algorithm so that experiment B (which is downstream and shown to the user after they've seen experiment A) does not get starved of traffic. I don't want all traffic going to experiment A.
So the flow is as follow
- User visits page A where experiment A is implemented
- We decide whether to assign users to experiment A. If user is assigned to A, user will be able to see experiment A.
- User visits page B where experiment B is implemented, we decide whether to assign users to experiment B
- Users can only see experiments that they are assigned to.
- I want to come up with an algorithm that allows me to assign traffic to experiments regardless of where they are implemented so that the traffic distribution is efficient and experiments implemented downstream don't get starved (even though user sees experiment B last, they still get a good chance of being assigned to B)
Can someone please point me in the right direction to an algorithm that I can use to efficiently allocate traffic to experiments so that experiments reach sample size and stats sig in good time in a system where experiments are allocated traffic at point of exposure and where experiments are "exposed" to the user at different points of the flow (early or later on) and in a way that makes it so that experiments exposed later on are not starved of traffic?
A possible algorithm:
- For each experiment, we make a decision of whether to assign based on the experiment's location using coin flip.
- If we get heads, a list of experiments that match the user's criteria and that are implemented for that location are selected.
- An experiment is chosen from that list based on priority system. At every location, a % of users are assigned to one of the experiments implemented at that location.
- When we decide to assign or not to assign to any experiments at that location, that decision is not made again for the user.
What I am struggling with is what that priority system algorithm should be? and also is this the most efficient way to assign users to experiments that are implemented at different points of the flow? How do we decide whether to assign users to an experiment at a specific location? Right now we use coin flip, but that means 50% of users will be assigned to an experiment at each location, which does not work.
-
Solve a simple packing combination with dependencies
This is not a homework question, but something that came up from a project I am working on. The picture above is a packing configuration of a set of boxes, where A,B,C,D is on the first layer and E,F,G on the second layer. The question is that if the boxes are given in a random order, what is the probability that the boxes can be placed in the given configuration?
The only condition for the placement is all the boxes need to be placed from top down and cannot be moved once placed. Therefore no sliding under the existing box or floating placement is allowed, but it's okay to save room for the box on the same layer. For example, E can only be placed when A and B are already in place. If the handing order is AEB... then it cannot be placed in the specified configuration, if the handing sequence is ACBE... then E can be correctly placed.
A more formulated description is to translate the packing configuration to a set of dependencies, or prerequisites. ABCD on the first layer has 0 dependencies, while dependencies of E are {A and B}, F are {B and C}, and G are {C and D}, the corresponding dependencies must happen before E or F or G happens. Also while it doesn't apply to this problem, in some problem the dependencies could also be of a "or" relationship instead of "and".
I wonder what are the general deterministic algorithms to solve this, or this class of problem? A way I could think of is generating A,B,C,D,E,F,G in random order for 10,000 times and for each order check if the corresponding prerequisites have happened when each element is called. This naive idea, however, is time consuming and cannot produce the exact probability(I believe the answer to this problem is 1/18 based on this naive algorithm I implemented).
And advice will be greatly appreciated!
-
Order the following functions in terms of their asymptotic growth, from fastest to slowest
I m quite new to soerting algorithms and i'm experenting a ittle bit by using online worksheets and form the list below and manged to sort them like this? did i sort them right?
Not sorted
- f(n) = n( n^2 + 2)
- f(n) = 2^n + 2n + 5
- f(n) = 5n + 20
- f(n) = 1000
- f(n) = 2n^2 - 5n + 12
Sorted
- f(n) = 1000 fastest
- f(n) = 5n + 20
- f(n) = 2^n + 2n + 5
- f(n) = n( n^2 + 2)
- f(n) = 2n^2 - 5n + 12 slowest
-
How to sort (order) WordPress playlist by metadata (such as artist, album, bitrate etc.)?
I can use WordPress in-built orderby to sort playlist by
title
or any column inwp_posts
table, as shown below.echo wp_playlist_shortcode( array( 'ids' => '7,8,9', 'order' => 'DESC', 'orderby' => 'title', ));
But how to sort playlist by attachment metadata (such as Album, Artist, Bitrate, Length, Year, File Size etc.)?
-
Sortable Html Table - Issues with Grabbing Data From Input Fields
Working on creating something similar to an "Interactive Whiteboard" using ASP.NET, C#, JS, etc. The structure boils down to it being an html based table, with input fields (Like textboxes) that are being continually pushed out to a database and pulled back with each refresh. We would like to implement a sorting feature to the columns but with there being input fields instead of hard coded values - I can't figure out a way to do it.
This is a general idea of the table layout:
<div id="tableThing"> <table class="tg"> <tr> <th class="tg-yw4l" id="asset1"> <asp:LinkButton ID="lnkAsset" runat="server" OnClientClick="return adjustColumn();">Asset ID</asp:LinkButton> <asp:LinkButton ID="lnkSortAsset" runat="server" OnClientClick="return callSort();">V</asp:LinkButton> </th> <th class="tg-yw4l">OP Status </th> <th class="tg-yw4l">Status Notes</th> <th class="tg-yw4l">Status Comments</th> <th class="tg-yw4l">Condition Status</th> <th class="tg-yw4l">Spot</th> <th class="tg-yw4l">Spot Description</th> </tr> <tr> <td class="tg-6k2t" id="asset2"> <asp:TextBox ID="txtAsset1" runat="server" Text="" /> </td> <td class="tg-6k2t"> <asp:Label ID="lblOP1" runat="server" Text=""></asp:Label> </td> <td class="tg-6k2t"> <asp:TextBox ID="txtStatusNotes1" runat="server" Text="" /> </td> <td class="tg-6k2t"> <asp:TextBox ID="txtStatusComments1" runat="server" Text="" /> </td> <td class="tg-6k2t"> <asp:TextBox ID="txtCond1" runat="server" Text="" /> </td> <td class="tg-6k2t"> <asp:TextBox ID="txtSpot1" runat="server" Text="" /> </td> <td class="tg-6k2t"> <asp:TextBox ID="txtSpotDesc1" runat="server" Text="" /> </td> </tr> <tr> <td class="tg-yw4l" id="asset3"> <asp:TextBox ID="txtAsset2" runat="server" Text="" /> </td> <td class="tg-yw4l"> <asp:Label ID="lblOP2" runat="server" Text=""></asp:Label> </td> <td class="tg-yw4l"> <asp:TextBox ID="txtStatusNotes2" runat="server" Text="" /> </td> <td class="tg-yw4l"> <asp:TextBox ID="txtStatusComments2" runat="server" Text="" /> </td> <td class="tg-yw4l"> <asp:TextBox ID="txtCond2" runat="server" Text="" /> </td> <td class="tg-yw4l"> <asp:TextBox ID="txtSpot2" runat="server" Text="" /> </td> <td class="tg-yw4l"> <asp:TextBox ID="txtSpotDesc2" runat="server" Text="" /> </td> </tr>
This is how the fields are being populated on the back end, HOWEVER, we will be changing this in the short term to use a Web API as opposed to just grabbing SQL values directly.
protected void Page_Load(object sender, EventArgs e) { getSQL(); } public void getSQL() { SqlConnection con = new SqlConnection(conString); con.Open(); using (SqlCommand command = new SqlCommand("SELECT * FROM [operator]", con)) { SqlDataReader reader = command.ExecuteReader(); List<String> lstAsset = new List<String>(); List<String> lstOP = new List<String>(); while (reader.Read()) { lstAsset.Add(reader[0].ToString()); lstOP.Add(reader[2].ToString()); } txtAsset1.Text = lstAsset[0]; txtAsset2.Text = lstAsset[1]; lblOP1.Text = lstOP[0]; lblOP2.Text = lstOP[1]; } }
This is what we had tried to get working in scripts in the bottom - Based on similar stack overflow questions that used hard-coded table values. It obviously isn't quite working for the way we have the table set up, but for context as to what we are trying to accomplish.
function callSort() { makeAllSortable(); return false; } function sortTable(table, col, reverse) { var tb = table.tBodies[0], // use `<tbody>` to ignore `<thead>` and `<tfoot>` rows tr = Array.prototype.slice.call(tb.rows, 0), // put rows into array i; reverse = -((+reverse) || -1); tr = tr.sort(function (a, b) { // sort rows if (!isNaN(a.cells[col].textContent) && !isNaN(b.cells[col].textContent)) return reverse * ((+a.cells[col].textContent) - (+b.cells[col].textContent)) return reverse // `-1 *` if want opposite order * (a.cells[col].textContent.trim() // using `.textContent.trim()` for test .localeCompare(b.cells[col].textContent.trim()) ); }); for (i = 0; i < tr.length; ++i) tb.appendChild(tr[i]); // append each row in order } function makeSortable(table) { var th = table.tHead, i; th && (th = th.rows[0]) && (th = th.cells); if (th) i = th.length; else return; // if no `<thead>` then do nothing while (--i >= 0) (function (i) { var dir = 1; sortTable(table, i, (dir = 1 - dir)); }(i)); } function makeAllSortable(parent) { parent = parent || document.body; var t = parent.getElementsByTagName('table'), i = t.length; while (--i >= 0) makeSortable(t[i]); }
-
Problems understanding code flow involving ifs and bool
Question from cs50, game of fifteen.
bool won(void) { // check if board is sorted int n = 1; // check to see if last tile is blank and return false if it is not if (board[d-1][d-1] != 0) return false; // set up for loops to check if numbers are in ascending order beginning with 1 for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) { // check last grid position first, if blank, return true if (i == d - 1 && j == d - 1) { return true; } // check the numbers on the rest of the tiles if (n != board[i][j]) { return false; } n++; } } return false; }
In the bool won(void), i am confused about whether the explanation i am giving myself is correct. Here why do we need the code below for the won function to return true.
if (i == d - 1 && j == d - 1) { return true; }
and why this(below) cant work and it seems to me it should. This returns true at the very start of the game.
for (int i = 0; i < d && n<=d-1; i++) { for (int j = 0; j < d; j++) { // check the numbers on the rest of the tiles if (n == board[i][j]) { return true; } n++; } }
If someone answers it, i would really appreciate your help. sorry for the bother. Thanks!
-
CS50 Resize Less: strange bmp output
I've been through the logic dozens times and it seems correct, I have no idea why the output is the way it is... Could someone help to explain why this logic output is wrong?
I cannot do debugging since I don't know how to check the content of
RGBTRIPLE* out_row
. I can't printf it with %i, %s, %c, %d... I'm really clueless... Thank you so much in advance...smiley output with scale factor 1
This is the code below, I've compared the output of
BITMAPFILEHEADER
andBITMAPINFOHEADER
to the sample and they seems to be correct.#include <stdio.h> #include <stdlib.h> #include <math.h> #include "bmp.h" int main(int argc, char *argv[]) { // ensure proper usage if (argc != 4) { fprintf(stderr, "Usage: ./resize n infile outfile\n"); return 1; } // get n factor int n = atoi(argv[1]); if (n > (pow(2,23)) - 1 ) { fprintf(stderr, "Error: n is too big\n"); fprintf(stderr, "Usage: ./resize n infile outfile\n"); return 5; } else if (n <= 0) { fprintf(stderr, "Error: n is too small\n"); fprintf(stderr, "Usage: ./resize n infile outfile\n"); return 6; } // remember filenames char *infile = argv[2]; char *outfile = argv[3]; // open input file FILE *inptr = fopen(infile, "r"); if (inptr == NULL) { fprintf(stderr, "Could not open %s.\n", infile); return 2; } // open output file FILE *outptr = fopen(outfile, "w"); if (outptr == NULL) { fclose(inptr); fprintf(stderr, "Could not create %s.\n", outfile); return 3; } // read infile's BITMAPFILEHEADER BITMAPFILEHEADER bf; fread(&bf, sizeof(BITMAPFILEHEADER), 1, inptr); // read infile's BITMAPINFOHEADER BITMAPINFOHEADER bi; fread(&bi, sizeof(BITMAPINFOHEADER), 1, inptr); // ensure infile is (likely) a 24-bit uncompressed BMP 4.0 if (bf.bfType != 0x4d42 || bf.bfOffBits != 54 || bi.biSize != 40 || bi.biBitCount != 24 || bi.biCompression != 0) { fclose(outptr); fclose(inptr); fprintf(stderr, "Unsupported file format.\n"); return 4; } printf("biSizeImage: %i, bfSize: %i\n", bi.biSizeImage, bf.bfSize); printf("inputheight:%i\n", bi.biHeight); // save input data to variable int in_width = bi.biWidth; int in_height = bi.biHeight; printf("temp inheight:%i\n", in_height); int in_padding = (4 - (bi.biWidth * sizeof(RGBTRIPLE)) % 4) % 4; // update outfile's HEADER bi.biWidth *= n; bi.biHeight *= n; int out_padding = (4 - (bi.biWidth * sizeof(RGBTRIPLE)) % 4) % 4; bi.biSizeImage = ((sizeof(RGBTRIPLE) * bi.biWidth) + out_padding) * abs(bi.biHeight); bf.bfSize = bi.biSizeImage + sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER); printf("new_biSizeImage: %i, new_bfSize: %i\n", bi.biSizeImage, bf.bfSize); // write outfile's BITMAPFILEHEADER fwrite(&bf, sizeof(BITMAPFILEHEADER), 1, outptr); // write outfile's BITMAPINFOHEADER fwrite(&bi, sizeof(BITMAPINFOHEADER), 1, outptr); // allocate memory to store output row RGBTRIPLE* out_row = malloc(bi.biWidth * sizeof(RGBTRIPLE)); // iterate over infile's scanlines for (int i = 0, biHeight = abs(in_height); i < biHeight; i++) { // initialize counter to write out_row int counter = 0; // iterate over pixels in scanline for (int j = 0; j < in_width; j++) { // temporary storage RGBTRIPLE triple; // read RGB triple from infile fread(&triple, sizeof(RGBTRIPLE), 1, inptr); // write the triple to out_row times n factor for (int o = 0; o < n ; o++) { out_row[counter] = triple; counter++; } // skip over padding, if any fseek(inptr, in_padding, SEEK_CUR); // write the out_row result and repeat vertically for (int m = 0; m < n; m++) { // write RGB triple to outfile fwrite(out_row, sizeof(RGBTRIPLE), bi.biWidth, outptr); // then add it back (to demonstrate how) for (int k = 0; k < out_padding; k++) { fputc(0x00, outptr); } } } } // release malloc free(out_row); // close infile fclose(inptr); // close outfile fclose(outptr); // success return 0; }
-
Excecuting Luhn's Algorithm in C - buggy code - ANSWERED
I'm currently working through CS50x's 2018 programme and I'm completing the 'credit' part of pset1. We're supposed to be executing Luhn's algorithm, but I can't get it to work.
Luhn's algorithm is an algorithm that uses checksum to determine whether or not a credit card is valid. The input should be a credit card number, or something that could be a credit card number. It then takes the number, multiplies every other digit by 2 (or every even digit as implied in my code), sums them, then takes the remaining digits (the odd ones) and sums them with the first sum. The algorithm then states that if the last digit of the summed value is 0 then the number is valid (or if it divides by ten perfectly). If the answer isn't 0 then it should print "INVALID" to the user. If it is 0 the code should then analyse whether or not the number could be a valid card. We are supposed to use American Express, Visa and MasterCard as our potential cards. If it's AMEX it will be 15 digits and start with 34 or 37, MASTERCARD is 16 digits and starts with 51, 52, 53, 54 or 55, and VISA is either 13 or 16 digits and starts with 4. The expected output is either one of the card companies or "INVALID" if the number doesn't fit that criteria.
Instead of this, my code simply runs until overflow after a number is submitted. I know my logic must be flawed somewhere, but I have no idea where I've gone wrong. My code is as follows:
//Checks credit card no. to see if valid #include <cs50.h> #include <stdio.h> #include <math.h> int main(void) { //Get card no. from user long long n; do { n = get_long_long("Card Number: "); } while (n < 0); //Define variables for checksum process int odd = 0; int even = 0; long long temp_n = n; int sum_a = 0; int sum_b = 0; int counter = 0; //Execute checksum until all of n assessed while (temp_n >= 0) { //Take final digit, add up, then update temp no., increase digit counter by 1 odd = temp_n % 10; sum_b = sum_b + odd; temp_n = (temp_n - odd) / 10; counter++; //Take final digit (which is an even digit of n), multiply by 2 and add up, update temp no., increase counter by 1 even = temp_n % 10; sum_a = sum_a + 2 * even; temp_n = (temp_n - even) / 10; counter++; } //Validate checksum int test = (sum_a + sum_b) % 10; //Return results if (test == 0) { if (counter == 16 && odd == 5 && (even == 1 || even == 2 || even == 3 || even == 4 || even == 5)) { printf("MASTERCARD\n"); } else if ((counter == 16 || counter == 13) && odd == 4) { printf("VISA\n"); } else if (counter == 15 && odd == 3 && (even == 4 || even == 7)) { printf("AMEX\n"); } else { printf("INVALID\n"); } } else { printf("INVALID\n"); } }
I would appreciate any help I can get about where I've gone wrong. Thank you in advance.
-
How to implement counting sort for integers in Clojure?
Say I have an array of integers
xs
taking values from0
tomax
, and I need to sort it in O(n) time, so I can't just do(sort xs)
.Is there a way to do it with the
frequencies
function?In another language I would then do a
for
to iterate over integers from0
tomax
, and for each valuex
in that range, look up(frequencies x)
and then dorepeat (frequencies x) x
or something.Crucially I need to do this IN ORDER from smallest to highest, which is what makes the whole thing a sort. So I DON'T want to just
map
each number inxs
.Any ideas for a clojure-ish idiomatic solution?
Thanks.
-
Counting sort code
I got this code (counting sort) to sort the numbers on the input but it is not working and I´m not able to finf the mistake.
For example: Input ---> 2 4 3 5 1 Output ---> 1 2 3 4 5
#include <stdio.h> #include <stdlib.h> void counting_sort(int data[], int n) { int c[21], i, result[1000]; for (i = 0; i <= 20; i++) c[i] = 0; for (i = 0;i<n;i++) c[data[i]]++; for (i = 1; i <=20; i++) c[i] = c[i] + c[i-1]; for (i = n-1;i>=0; i--) result[--c[data[i]]] = data[i]; for (i = 0; i < n; i++) data[i] = result[i]; } int main(void) { int numbers[1000], total, i; while(scanf("%d", &numbers[total]) == 1) total++; counting_sort(numbers, total); for (i=0; i<total; i++) printf("%d ", numbers[i]); return 0; }
-
Counting sort Java - Unexpected results
class CountingSort { int[] csort(int[] arr) { int n = arr.length; int max = arr[0]; int[] out = new int[n]; for (int i : arr) { if (max < i) { max = i; } } int range = max + 1; int[] te = new int[range]; for (int i = 0; i < range; ++i) { te[i] = 0; } for (int j = 1; j < n; j++) { te[arr[j]] = te[arr[j]] + 1; } // case1: {0,0,0,1,0,1,1,0,1,1} // case2: {0,0,0,1,0,1,1,0,1,1} for (int k = 1; k < range; ++k) { te[k] = te[k] + te[k - 1]; } // case1: {0,0,0,1,1,2,3,3,4,5} // case2: {0,0,0,1,1,2,3,3,4,5} for (int l = n - 1; l >= 0; --l) { out[te[arr[l]]] = arr[l]; te[arr[l]] = te[arr[l]] - 1; } return out; } }
Above is the code for Counting Sort. Following are my observations
- if the input array such that smallest is first element eg
{1, 6, 8, 3, 5, 9}
it gives the expected output{1, 3, 5, 6, 8, 9}
- But if give the input array such that first element is not the smallest eg
{4, 6, 8, 3, 5, 9}
then the output has first element zero and one number goes missing. I've tried but can't seem to find how this is happening.
- if the input array such that smallest is first element eg