-
CliffR, I think you're right that there’s a bit of irony here worth pointing out. GPT was sent on a wild goose chase to identify nonexistent bugs based on your review, which turned out to include some inaccuracies. This isn’t meant as a dig—it’s a reminder that even expert human review can introduce errors that slow down the development process. Meanwhile, GPT produced a working solution to the problem almost immediately, which highlights the efficiency AI brings to tasks like these.
Originally Posted by CliffR
The core issue I have with your argument isn’t just the critique of AI’s output but that preexisting skepticism seems to have led to conclusions that weren’t fully supported. You originally asked if we could benchmark how long it takes AI to resolve bugs versus a human. The timestamps in this thread alone make the answer pretty clear.
Your follow-up on global variables and redundant checks is fine. But the bigger point here is that nitpicking these details caused far more slowdown than the actual limitations of GPT’s solution. Tasks like these—whether they involve debugging, repetitive coding, or migrations—are exactly what AI handles daily, and it does so in a fraction of the time humans spend reviewing or debating minor issues. You can critique the details, but that doesn’t change the broader trend: large tech companies are already applying this technology effectively, achieving significant efficiency gains even with validation layers in place.Last edited by omphalopsychos; 12-29-2024 at 09:19 AM.
-
12-29-2024 08:59 AM
-
Not at all, the target audiences are businesses where AI can vastly improve productivity, make them more profitable. As Juan pointed out in great detail, that is already happening across dozens of industries. Microsoft, OpenAI, Google, Meta, NVDA aren't investing billions to impress ivory tower humanities prof's. Originally Posted by RJVB
Isn't the main target audience for the technology also the main target audience of Reader's Digest, people who'll rarely ever read something more profound than what can be found in that catalogue?
It's also already improving lives in ways you probably haven't considered. Hearing aids are using it to "autosense" the environment and eliminate unwanted noise and make speech understandable. That's just one example...
-
Well, yes, that's supposedly what's paying for it, in addition to ads being served... Originally Posted by jhbpa
No, doing that would require only a fraction of their profits, and it has been like that for decades.Microsoft, OpenAI, Google, Meta, NVDA aren't investing billions to impress ivory tower humanities prof's.
I doubt though that there are language models behind that. Similar things have been done in photo cameras for decades, initially under the marketing name "fuzzy logic".Hearing aids are using it to "autosense" the environment and eliminate unwanted noise and make speech understandable. That's just one example...
-
Not quite correct. The primary audience is, at least in the short term, investors. The products themselves are actually I’d say second. Originally Posted by jhbpa
Sent from my iPhone using Tapatalk
-
I suggest you do as little research on the latest devices from Phonak, Starkey and Oticon. Comparing it to "things have been done in photo cameras for decades" is ludicrous. I'll GPT comment: Originally Posted by RJVB
Yes, some of the latest hearing aids incorporate elements inspired by language models and similar Al technologies. While they may not use full-scale language models like GPT, they leverage natural language processing (NLP) and machine learning techniques for specific tasks. Here's how these concepts are applied in hearing aids:
1. Speech Recognition and Enhancement
- Language Model-Like Algorithms:
- Hearing aids use Al models trained to recognize and enhance human speech by distinguishing it from background noise.
- These models predict speech patterns and prioritize processing spoken words in noisy environments, much like how language models understand and predict text.
2. Real-Time Translation
- Advanced hearing aids (e.g., Starkey or Oticon) use NLP-based models to enable real-time language translation.
- Similar to how language models process text input, these systems convert spoken words into a different language and output the translation in audio or text form.
3. Real-Time Captioning
- Some hearing aids offer live transcription, powered by NLP techniques:
- Speech-to-text capabilities transcribe conversations into readable text on a connected device.
- This involves processing spoken words using Al models similar to those in language translation apps or dictation software.
4. Contextual Understanding
- Predictive Adjustments:
- Hearing aids with contextual Al adapt settings based on the user's environment (e.g., a noisy restaurant versus a quiet home).
- While these systems may not be full language models, they use similar context-aware processing techniques to understand user needs and make adjustments.
5. Conversational Interaction
- Some hearing aids integrate with virtual assistants (e.g., Siri, Alexa, Google Assistant) that use language models.
- Users can give voice commands or ask questions directly through their hearing aids, enabling interaction with Al systems designed for natural language understanding.
6. NLP and Machine Learning for Feedback
- Al algorithms in hearing aids analyze auditory feedback and user behavior to improve performance over time.
- For example, these models can detect common conversational phrases or words and enhance their clarity, akin to how language models predict text based on context.
Key Differences from Full-Scale Language Models
While hearing aids use Al inspired by language models, they:
- Focus on Speech and Audio: Their primary goal is to enhance real-time auditory experiences rather than generate text or conversational output.
- Operate Locally or with Minimal Resources: Most hearing aid Al runs on lightweight, embedded systems, rather than requiring the computational power of large-scale language models.
- Task-Specific Optimization: The Al in hearing aids is highly specialized for speech enhancement, noise reduction, and similar tasks.
Future Potential
As Al in hearing aids evolves, there's a possibility of deeper integration with full-scale language models for:
- More Advanced Conversational Al: Providing users with detailed assistance or language support.
- Seamless Human Interaction: Greater contextual awareness for e natural-sounding and responsive speech enhancements.
-
For the record, that wasn't the issue btw. The implementation of the recursive function was correct but your Gemini's print statement erroneously assumed that the return value of solveNQueens() indicated whether or any solutions existed, whereas it was merely a utility function to route the recursive calls. solveNQueens() is structured to find all solutions, but its return value (true or false) is not designed to indicate whether any solutions were found. Instead, the program should have used the solutions counter to determine if solutions exist. Originally Posted by CliffR
Here's all your Gemini program needed in order to work properly. Replace your print statement for the number solutions with the following.
solveNQueens(0);
if (solutions > 0) {
printf("Total solutions: %d\n", solutions);
} else {
printf("No solution exists for n = %d.\n", n);
}
The fact that I’m indulging this after GPT resolved the issue instantly probably highlights the deeper point here: people enjoy debugging (and honestly, I enjoyed looking at this too). It’s the same reason people enjoy wordsmithing, designing, or creating art—these tasks are personally rewarding. But this is precisely why there’s resistance to AI: it threatens the work people find fulfilling, whether it’s debugging code, writing, or creating media content.
That’s why I emphasize the importance of AI as a complement, not a replacement. AI enhances workflows, making tasks faster and more efficient, but it doesn’t take away the deeper, more human parts of the work. GPT didn’t replace us here—it just sped up the process and gave us a starting point. I sense some job insecurity in the tone of responses from both CliffR and Litterick. That’s understandable, given the rapid evolution of AI, but I can guarantee that AI can already do many of the things you’re claiming it can’t. I’m happy to keep providing examples, but I suspect I won’t need to for long—these tools are becoming ubiquitous, and their results will speak for themselves.Last edited by omphalopsychos; 12-29-2024 at 10:22 AM.
-
Originally Posted by Christian Miller
This is an interesting point. Are you talking about NVDIA, OpenAI, etc? Or the companies using them?
Yes people who are producing AI hardware and software are trying to maximize their shareholder value and ride these hype cycles. Companies that are USING AI, however, are just looking for productivity gains and cost reducing measures. Both are true.
-
The return of 'false' by the recursive function and the interpretation of that by the caller was *exactly* the issue. Your proposed solution here is valid. But if we're looking at timestamps, it took you and ChatGTP nearly a day to figure out what was immediately obvious to me. Originally Posted by omphalopsychos
-
You're being hilarious right now.
Took Chat GPT 0 minutes to provide you a script without bugs.
Took you 30 minutes to decide on the number of "bugs" you thought there were.
Took me 30 minutes to manually debug (without Chat GPT, which was my whole point) this morning.
Cliff vs Juan - let's call it a tie at 30 min. Even though your statement that "The bug was the return 'false' at the end of the recursive function. This means all invocations would be seen as failures and the code would assume 0 solutions." was wrong. The bug was in the caller which was incorrectly counting solutions and neglecting the solutions counter, not in the recursive function. "Tie" is generous to you.
Chat GPT vs either of us: Chat GPT won this one with a 30 minute lead.
-
Drop the little digs and insults, please. The truth is, ChatGTP did produce working code, but it mis-characterised the bug. Comments and documentation are important in production code. You took it's explanation on face value and repeated it to me. You passed this off as your own work, since I asked *you* to identify the bug and you failed to reveal you'd used ChatGTP to do the work for you. For some reason you felt obliged today to spend 30 minutes of your time to get to the bottom of the real bug, which you successfully did. Time saved? None. Originally Posted by omphalopsychos
-
I'm not spending my holiday on this forum to "save time". I think you and I agree that coding and debugging is fun, which is why I came back to it.
I'm not trying to be insulting, but if you're going to be voicing criticisms, I'm going to hold you accountable to your errors. I'm also admitting that solving the problem took me about 60 times as long as it took GPT. I'd gladly can share runner up position here with you.
-
Cliff check this out. The testing is absolute overkill, but I think you can appreciate the enhancements here. (you might want to comment out the performance test if running locally). Here's a list of enhancements.
- Replaced static board array with dynamically allocated memory using malloc and free.
- Encapsulated global variables (board, solutions, n) into a NQueensState struct.
- Added input validation to ensure board size is within valid range and handles invalid input gracefully.
- Introduced runNQueens as a wrapper function for modular initialization, solving, and solution retrieval.
- Created modular functions for memory allocation (allocateBoard, freeBoard) and board initialization.
- Integrated predefined test cases for core, edge, and performance scenarios with known expected solutions.
- Included a scorecard summarizing test results (pass/fail) and calculating the pass rate.
- Improved error handling by returning -1 for invalid inputs or memory allocation failures in runNQueens.
- Enhanced output clarity with consistent formatting for test results, user input, and final summaries.
- Ensured scalability for larger board sizes while maintaining robustness and efficiency.
Excluding the performance test, here's the output.
Test Summary:
--------------------------------------
Total Test Cases: 12
Passed Test Cases: 12
Failed Test Cases: 0
Pass Rate: 100.00%
--------------------------------------
Also if you want it in C++ or Java that would be just another 30 seconds.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 20 // Define a maximum board size
// Struct to hold the board state and problem parameters
typedef struct {
int **board;
int size;
int solutions;
} NQueensState;
// Function to allocate memory for the board
bool allocateBoard(NQueensState *state) {
state->board = (int **)malloc(state->size * sizeof(int *));
if (!state->board) return false;
for (int i = 0; i < state->size; i++) {
state->board[i] = (int *)malloc(state->size * sizeof(int));
if (!state->board[i]) return false;
}
return true;
}
// Function to free allocated memory
void freeBoard(NQueensState *state) {
for (int i = 0; i < state->size; i++) {
free(state->board[i]);
}
free(state->board);
}
// Function to initialize the board
void initializeBoard(NQueensState *state) {
for (int i = 0; i < state->size; i++) {
for (int j = 0; j < state->size; j++) {
state->board[i][j] = 0;
}
}
}
// Function to print the board
void printBoard(NQueensState *state) {
for (int i = 0; i < state->size; i++) {
for (int j = 0; j < state->size; j++) {
printf("%d ", state->board[i][j]);
}
printf("\n");
}
printf("\n");
state->solutions++;
}
// Function to check if a queen can be placed at board[row][col]
bool isSafe(NQueensState *state, int row, int col) {
for (int i = 0; i < row; i++) {
if (state->board[i][col] == 1) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (state->board[i][j] == 1) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j < state->size; i--, j++) {
if (state->board[i][j] == 1) {
return false;
}
}
return true;
}
// Recursive function to solve the N-Queens problem
void solveNQueens(NQueensState *state, int row) {
if (row == state->size) {
printBoard(state);
return;
}
for (int col = 0; col < state->size; col++) {
if (isSafe(state, row, col)) {
state->board[row][col] = 1;
solveNQueens(state, row + 1);
state->board[row][col] = 0;
}
}
}
// Wrapper function to run the N-Queens problem
int runNQueens(int size) {
if (size <= 0 || size > MAX_SIZE) {
printf("Invalid board size: %d\n", size);
return -1;
}
NQueensState state;
state.size = size;
state.solutions = 0;
if (!allocateBoard(&state)) {
printf("Memory allocation failed for board size %d\n", size);
return -1;
}
initializeBoard(&state);
solveNQueens(&state, 0);
int solutionsFound = state.solutions;
freeBoard(&state);
return solutionsFound;
}
// Main function to run user input and test cases
int main() {
int userSize;
// Input validation for user-provided board size
printf("Enter the size of the board (1-%d): ", MAX_SIZE);
if (scanf("%d", &userSize) != 1 || userSize <= 0 || userSize > MAX_SIZE) {
printf("Invalid input. Please enter an integer between 1 and %d.\n", MAX_SIZE);
return 1;
}
printf("\nRunning user-defined N-Queens...\n");
int userSolutions = runNQueens(userSize);
if (userSolutions >= 0) {
printf("Total solutions for %dx%d board: %d\n", userSize, userSize, userSolutions);
} else {
printf("Failed to compute solutions due to invalid input or memory issues.\n");
}
// Predefined test cases
struct TestCase {
int boardSize;
int expectedSolutions;
};
struct TestCase testCases[] = {
// Core test cases
{1, 1}, {2, 0}, {3, 0}, {4, 2}, {5, 10}, {6, 4}, {7, 40}, {8, 92}, {9, 352}, {10, 724},
// Edge cases
{0, 0}, // Invalid size
{MAX_SIZE + 1, 0}, // Exceeds max size
// Performance tests
{15, 2279184}, {16, 14772512} // Larger boards for scalability
};
int testCaseCount = sizeof(testCases) / sizeof(testCases[0]);
int passedTests = 0;
printf("\nRunning predefined test cases:\n");
printf("--------------------------------------\n");
for (int i = 0; i < testCaseCount; i++) {
struct TestCase testCase = testCases[i];
printf("Test %d: Board Size = %d\n", i + 1, testCase.boardSize);
int foundSolutions = runNQueens(testCase.boardSize);
if (foundSolutions >= 0) {
printf("Expected Solutions: %d, Found Solutions: %d\n", testCase.expectedSolutions, foundSolutions);
if (foundSolutions == testCase.expectedSolutions) {
printf("Result: PASSED\n");
passedTests++;
} else {
printf("Result: FAILED\n");
}
} else {
if (testCase.boardSize <= 0 || testCase.boardSize > MAX_SIZE) {
printf("Result: PASSED (Invalid input correctly handled)\n");
passedTests++;
} else {
printf("Result: FAILED (Memory Allocation Issue)\n");
}
}
printf("--------------------------------------\n");
}
// Print the scorecard
printf("\nTest Summary:\n");
printf("--------------------------------------\n");
printf("Total Test Cases: %d\n", testCaseCount);
printf("Passed Test Cases: %d\n", passedTests);
printf("Failed Test Cases: %d\n", testCaseCount - passedTests);
printf("Pass Rate: %.2f%%\n", (passedTests / (float)testCaseCount) * 100);
printf("--------------------------------------\n");
return 0;
}
-
Yay!
Can you or it find and remove the redundant board-square checks?
-
The script performed redundant board scans for column and diagonal checks, which significantly slowed it down as board size increased. The optimized version replaces these scans with auxiliary arrays that allow quick lookups for conflicts, greatly improving efficiency. Performance tests for board sizes {6, 8, 10, 12, 14} show the improvement.
Output here (hopefully forum formatting doesn't ruin these cool plots).
EDIT: yes the forum formatting ruined the plots but it looks cool in the console.
Running predefined test cases and performance tests...
Comparing Performance (Original vs Optimized):
--------------------------------------
Performance Test: Board Size = 6
Original Time: 0.000 seconds, Optimized Time: 0.000 seconds
--------------------------------------
Performance Test: Board Size = 8
Original Time: 0.001 seconds, Optimized Time: 0.000 seconds
--------------------------------------
Performance Test: Board Size = 10
Original Time: 0.010 seconds, Optimized Time: 0.003 seconds
--------------------------------------
Performance Test: Board Size = 12
Original Time: 0.286 seconds, Optimized Time: 0.078 seconds
--------------------------------------
Performance Test: Board Size = 14
Original Time: 10.930 seconds, Optimized Time: 2.677 seconds
--------------------------------------
Performance Plot (Original Implementation):
Y-Axis: Time (seconds)
1.00 |
0.95 |
0.90 |
0.85 |
0.80 |
0.75 |
0.70 |
0.65 |
0.60 |
0.55 |
0.50 |
0.45 |
0.40 |
0.35 |
0.30 | *
0.25 |
0.20 |
0.15 |
0.10 |
0.05 | * * *
----------
6 8101214
X-Axis: Board Size
Performance Plot (Optimized Implementation):
Y-Axis: Time (seconds)
1.00 |
0.95 |
0.90 |
0.85 |
0.80 |
0.75 |
0.70 |
0.65 |
0.60 |
0.55 |
0.50 |
0.45 |
0.40 |
0.35 |
0.30 |
0.25 |
0.20 |
0.15 |
0.10 | *
0.05 | * * *
----------
6 8101214
X-Axis: Board Size
Script here.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define MAX_SIZE 20 // Define maximum board size for general use
typedef struct {
int **board;
int size;
int solutions;
} NQueensState;
// Function to allocate memory for the board
bool allocateBoard(NQueensState *state) {
state->board = (int **)malloc(state->size * sizeof(int *));
if (!state->board) return false;
for (int i = 0; i < state->size; i++) {
state->board[i] = (int *)malloc(state->size * sizeof(int));
if (!state->board[i]) return false;
}
return true;
}
// Function to free allocated memory
void freeBoard(NQueensState *state) {
for (int i = 0; i < state->size; i++) {
free(state->board[i]);
}
free(state->board);
}
// Function to initialize the board
void initializeBoard(NQueensState *state) {
for (int i = 0; i < state->size; i++) {
for (int j = 0; j < state->size; j++) {
state->board[i][j] = 0;
}
}
}
// Original Recursive Function Without Auxiliary Arrays
void solveNQueensOriginal(int row, NQueensState *state) {
if (row == state->size) {
state->solutions++;
return;
}
for (int col = 0; col < state->size; col++) {
int safe = 1;
// Check column and diagonals
for (int i = 0; i < row; i++) {
if (state->board[i][col] ||
(col - (row - i) >= 0 && state->board[i][col - (row - i)]) ||
(col + (row - i) < state->size && state->board[i][col + (row - i)])) {
safe = 0;
break;
}
}
if (safe) {
state->board[row][col] = 1;
solveNQueensOriginal(row + 1, state);
state->board[row][col] = 0;
}
}
}
// Optimized Recursive Function Using Auxiliary Arrays
void solveNQueensOptimized(int row, int n, int *columns, int *leftDiagonals, int *rightDiagonals, int *solutions) {
if (row == n) {
(*solutions)++;
return;
}
for (int col = 0; col < n; col++) {
int leftDiagonal = row - col + n - 1;
int rightDiagonal = row + col;
if (!columns[col] && !leftDiagonals[leftDiagonal] && !rightDiagonals[rightDiagonal]) {
columns[col] = leftDiagonals[leftDiagonal] = rightDiagonals[rightDiagonal] = 1;
solveNQueensOptimized(row + 1, n, columns, leftDiagonals, rightDiagonals, solutions);
columns[col] = leftDiagonals[leftDiagonal] = rightDiagonals[rightDiagonal] = 0;
}
}
}
// Wrapper function for the original N-Queens solver
int runNQueensOriginal(int size) {
NQueensState state = {0};
state.size = size;
state.solutions = 0;
if (!allocateBoard(&state)) {
printf("Memory allocation failed for board size %d\n", size);
return -1;
}
initializeBoard(&state);
solveNQueensOriginal(0, &state);
int solutionsFound = state.solutions;
freeBoard(&state);
return solutionsFound;
}
// Wrapper function for the optimized N-Queens solver
int runNQueensOptimized(int size) {
int solutions = 0;
int *columns = (int *)calloc(size, sizeof(int));
int *leftDiagonals = (int *)calloc(2 * size - 1, sizeof(int));
int *rightDiagonals = (int *)calloc(2 * size - 1, sizeof(int));
if (!columns || !leftDiagonals || !rightDiagonals) {
printf("Memory allocation failed for board size %d\n", size);
return -1;
}
solveNQueensOptimized(0, size, columns, leftDiagonals, rightDiagonals, &solutions);
free(columns);
free(leftDiagonals);
free(rightDiagonals);
return solutions;
}
// Plotting function for text-based scatter plot
void plotScatter(const char *label, int *sizes, double *times, int count) {
printf("\nPerformance Plot (%s):\n", label);
printf("Y-Axis: Time (seconds)\n");
// Generate plot
for (double y = 1.0; y >= 0.0; y -= 0.05) {
printf("%6.2f | ", y);
for (int x = 0; x < count; x++) {
if ((int)(times[x] * 20) == (int)(y * 20)) {
printf("* ");
} else {
printf(" ");
}
}
printf("\n");
}
// Print X-axis
printf(" ");
for (int i = 0; i < count; i++) {
printf("--");
}
printf("\n ");
for (int i = 0; i < count; i++) {
printf("%2d", sizes[i]);
}
printf("\nX-Axis: Board Size\n");
}
// Function to run performance tests and compare both implementations
void comparePerformance() {
int performanceSizes[] = {6, 8, 10, 12, 14};
double timesOriginal[sizeof(performanceSizes) / sizeof(performanceSizes[0])];
double timesOptimized[sizeof(performanceSizes) / sizeof(performanceSizes[0])];
printf("\nComparing Performance (Original vs Optimized):\n");
printf("--------------------------------------\n");
for (int i = 0; i < sizeof(performanceSizes) / sizeof(performanceSizes[0]); i++) {
int size = performanceSizes[i];
printf("Performance Test: Board Size = %d\n", size);
// Measure time for original implementation
clock_t startOriginal = clock();
runNQueensOriginal(size);
clock_t endOriginal = clock();
timesOriginal[i] = (double)(endOriginal - startOriginal) / CLOCKS_PER_SEC;
// Measure time for optimized implementation
clock_t startOptimized = clock();
runNQueensOptimized(size);
clock_t endOptimized = clock();
timesOptimized[i] = (double)(endOptimized - startOptimized) / CLOCKS_PER_SEC;
printf("Original Time: %.3f seconds, Optimized Time: %.3f seconds\n",
timesOriginal[i], timesOptimized[i]);
printf("--------------------------------------\n");
}
// Print time comparison in scatter plot
plotScatter("Original Implementation", performanceSizes, timesOriginal, sizeof(performanceSizes) / sizeof(performanceSizes[0]));
plotScatter("Optimized Implementation", performanceSizes, timesOptimized, sizeof(performanceSizes) / sizeof(performanceSizes[0]));
}
int main() {
printf("Running predefined test cases and performance tests...\n");
comparePerformance();
return 0;
}
-
Before you ask again, here's a further optimized version using bitmasking, symmetry reduction, and parallel processing. The fast implementation uses bitmasking to track column and diagonal conflicts efficiently, replacing array lookups with faster bitwise operations. Symmetry reduction halves the search space by solving for only half the columns in the first row and mirroring solutions. Finally, parallel processing distributes the first-row placements across multiple threads, leveraging multi-core CPUs to explore solutions concurrently. Together, these optimizations drastically reduce runtime while maintaining correctness.
OUTPUT
Running Performance Comparison...
Comparing Performance (Original vs Optimized vs Fast):
--------------------------------------
Board Size: 6
Original Time: 0.000 seconds, Solutions: 4
Optimized Time: 0.000 seconds, Solutions: 4
Fast Time: 0.000 seconds, Solutions: 4
Board Size: 8
Original Time: 0.000 seconds, Solutions: 92
Optimized Time: 0.000 seconds, Solutions: 92
Fast Time: 0.000 seconds, Solutions: 92
Board Size: 10
Original Time: 0.010 seconds, Solutions: 724
Optimized Time: 0.003 seconds, Solutions: 724
Fast Time: 0.000 seconds, Solutions: 724
Board Size: 12
Original Time: 0.251 seconds, Solutions: 14200
Optimized Time: 0.081 seconds, Solutions: 14200
Fast Time: 0.004 seconds, Solutions: 14200
Board Size: 14
Original Time: 9.743 seconds, Solutions: 365596
Optimized Time: 2.713 seconds, Solutions: 365596
Fast Time: 0.217 seconds, Solutions: 365596
--------------------------------------
PROGRAM
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <pthread.h> // For parallel processing
#define MAX_SIZE 20
// Struct for passing arguments to parallel threads
typedef struct {
int size;
long long solutions;
int firstCol; // First column for symmetry reduction
} ThreadArgs;
// Original Recursive Function Without Auxiliary Arrays
void solveNQueensOriginal(int row, int n, int **board, int *solutions) {
if (row == n) {
(*solutions)++;
return;
}
for (int col = 0; col < n; col++) {
int safe = 1;
// Check column and diagonals
for (int i = 0; i < row; i++) {
if (board[i][col] ||
(col - (row - i) >= 0 && board[i][col - (row - i)]) ||
(col + (row - i) < n && board[i][col + (row - i)])) {
safe = 0;
break;
}
}
if (safe) {
board[row][col] = 1;
solveNQueensOriginal(row + 1, n, board, solutions);
board[row][col] = 0;
}
}
}
// Optimized Recursive Function Using Auxiliary Arrays
void solveNQueensOptimized(int row, int n, int *columns, int *leftDiagonals, int *rightDiagonals, int *solutions) {
if (row == n) {
(*solutions)++;
return;
}
for (int col = 0; col < n; col++) {
int leftDiagonal = row - col + n - 1;
int rightDiagonal = row + col;
if (!columns[col] && !leftDiagonals[leftDiagonal] && !rightDiagonals[rightDiagonal]) {
columns[col] = leftDiagonals[leftDiagonal] = rightDiagonals[rightDiagonal] = 1;
solveNQueensOptimized(row + 1, n, columns, leftDiagonals, rightDiagonals, solutions);
columns[col] = leftDiagonals[leftDiagonal] = rightDiagonals[rightDiagonal] = 0;
}
}
}
// Fast Implementation with Bitmasking
void solveNQueensBitmask(int row, int n, int cols, int leftDiag, int rightDiag, long long *solutions) {
if (row == n) {
(*solutions)++;
return;
}
int available = (~(cols | leftDiag | rightDiag)) & ((1 << n) - 1);
while (available) {
int pos = available & -available;
available -= pos;
solveNQueensBitmask(row + 1, n, cols | pos, (leftDiag | pos) << 1, (rightDiag | pos) >> 1, solutions);
}
}
// Parallel Bitmask Solver
void *solveNQueensParallel(void *args) {
ThreadArgs *threadArgs = (ThreadArgs *)args;
int n = threadArgs->size;
int firstCol = threadArgs->firstCol;
long long solutions = 0;
int pos = 1 << firstCol;
solveNQueensBitmask(1, n, pos, pos << 1, pos >> 1, &solutions);
threadArgs->solutions = solutions;
return NULL;
}
// Wrapper for the fast bitmasking approach with symmetry reduction and parallel processing
long long runNQueensFast(int n) {
if (n <= 0 || n > MAX_SIZE) {
printf("Invalid board size: %d\n", n);
return -1;
}
long long totalSolutions = 0;
if (n == 1) return 1;
if (n == 2 || n == 3) return 0;
int half = n / 2;
pthread_t threads[half];
ThreadArgs threadArgs[half];
// Spawn threads for the first half of the board (symmetry reduction)
for (int col = 0; col < half; col++) {
threadArgs[col].size = n;
threadArgs[col].solutions = 0;
threadArgs[col].firstCol = col;
pthread_create(&threads[col], NULL, solveNQueensParallel, &threadArgs[col]);
}
// Join threads and aggregate solutions
for (int col = 0; col < half; col++) {
pthread_join(threads[col], NULL);
totalSolutions += threadArgs[col].solutions;
}
// Multiply by 2 (symmetry) and add center solutions if n is odd
totalSolutions *= 2;
if (n % 2 != 0) {
long long centerSolutions = 0;
solveNQueensBitmask(1, n, 1 << (n / 2), (1 << (n / 2)) << 1, (1 << (n / 2)) >> 1, ¢erSolutions);
totalSolutions += centerSolutions;
}
return totalSolutions;
}
// Performance Comparison
void comparePerformance() {
int boardSizes[] = {6, 8, 10, 12, 14};
int sizeCount = sizeof(boardSizes) / sizeof(boardSizes[0]);
printf("\nComparing Performance (Original vs Optimized vs Fast):\n");
printf("--------------------------------------\n");
for (int i = 0; i < sizeCount; i++) {
int n = boardSizes[i];
printf("\nBoard Size: %d\n", n);
clock_t start, end;
// Original
start = clock();
int **board = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) board[i] = (int *)calloc(n, sizeof(int));
int solutionsOriginal = 0;
solveNQueensOriginal(0, n, board, &solutionsOriginal);
for (int i = 0; i < n; i++) free(board[i]);
free(board);
end = clock();
printf("Original Time: %.3f seconds, Solutions: %d\n", (double)(end - start) / CLOCKS_PER_SEC, solutionsOriginal);
// Optimized
start = clock();
int *columns = (int *)calloc(n, sizeof(int));
int *leftDiagonals = (int *)calloc(2 * n - 1, sizeof(int));
int *rightDiagonals = (int *)calloc(2 * n - 1, sizeof(int));
int solutionsOptimized = 0;
solveNQueensOptimized(0, n, columns, leftDiagonals, rightDiagonals, &solutionsOptimized);
free(columns);
free(leftDiagonals);
free(rightDiagonals);
end = clock();
printf("Optimized Time: %.3f seconds, Solutions: %d\n", (double)(end - start) / CLOCKS_PER_SEC, solutionsOptimized);
// Fast
start = clock();
long long solutionsFast = runNQueensFast(n);
end = clock();
printf("Fast Time: %.3f seconds, Solutions: %lld\n", (double)(end - start) / CLOCKS_PER_SEC, solutionsFast);
}
printf("--------------------------------------\n");
}
int main() {
printf("Running Performance Comparison...\n");
comparePerformance();
return 0;
}
-
A writer friend of mine uses chatGPT by asking it "give 10 different ways of saying blah-de-blah." It comes back with different suggestions, and she'll take the parts she likes. But at that point she's already pretty far down the path of developing the text, she's just asking AI to brainstorm a bit.
AI will undoubtably get much better. It's still pretty new. It reminds me a bit of Optical Character Recognition software. Back in the 90s I had a job at the National Archives, where I'd sit in a windowless room with a computer, a scanner, and a boxes of index cards that referenced the film reels in the collection. It was so bad that I could type the index cards in by hand faster than the computer could do it (basically, I had to proof read the software's results, which were so bad to often be useless).
But now, it's just built into everything. I can point my phone camera at a page of text in a book and it will translate it from German to English almost in real time. So... 30 years later that awful new-fangled tech at the National Archives is so good I almost take it for granted.
-
Cliff, see if you can guess what additional enhancements yielded the ultrafast
implementation.
Benchmarking All Implementations:
--------------------------------------
Testing Board Size: 6
Original: Time = 0.000 seconds, Solutions = 4
Optimized: Time = 0.000 seconds, Solutions = 4
Fast: Time = 0.000 seconds, Solutions = 4
Ultra-Fast: Time = 0.000 seconds, Solutions = 4
--------------------------------------
Testing Board Size: 8
Original: Time = 0.000 seconds, Solutions = 92
Optimized: Time = 0.000 seconds, Solutions = 92
Fast: Time = 0.000 seconds, Solutions = 92
Ultra-Fast: Time = 0.000 seconds, Solutions = 92
--------------------------------------
Testing Board Size: 10
Original: Time = 0.010 seconds, Solutions = 724
Optimized: Time = 0.003 seconds, Solutions = 724
Fast: Time = 0.001 seconds, Solutions = 724
Ultra-Fast: Time = 0.000 seconds, Solutions = 724
--------------------------------------
Testing Board Size: 12
Original: Time = 0.256 seconds, Solutions = 14200
Optimized: Time = 0.080 seconds, Solutions = 14200
Fast: Time = 0.012 seconds, Solutions = 14200
Ultra-Fast: Time = 0.006 seconds, Solutions = 14200
--------------------------------------
Testing Board Size: 14
Original: Time = 9.787 seconds, Solutions = 365596
Optimized: Time = 2.734 seconds, Solutions = 365596
Fast: Time = 0.367 seconds, Solutions = 365596
Ultra-Fast: Time = 0.183 seconds, Solutions = 365596
--------------------------------------
-
Now we're cooking with gas. Originally Posted by omphalopsychos
-
You have to admit that is really sick. This is actually how people will spot students cheating on their CS homework: when submitted program runtimes are 1/10 of the professor's optimized solutions.
-
I am pleased to see that somebody understands these differences. Unfortunately, "AI" seems to have become a term attached to whatever somebody wants to sell as being the latest in tech. Originally Posted by Christian Miller
Tony
-
Really? How fascinating. Originally Posted by omphalopsychos
-
Looking forward to seeing Encanto 2 tomorrow with the kids.
-
Developer fires entire team for AI, now searching for engineers on LinkedIn
Wes Winder, a Canadian software developer, decided to fire his development team and replace it with AI tools. Winder used social media to brag about his decision, “I fired my entire dev team. Replaced them with O1, Lovable, and Cursor. Now I ship 100X faster with code that’s 10X cleaner. Open AI o3 is coming, and 90% of dev jobs won’t survive.”
Winder later took to LinkedIn in search of web developers: “Any web developers who are good with React/Remix/Supabase looking for some extra work on the side? I might have some work for you. Reply with your portfolio/recent work and I'll reach out.”
-
The debate around AI seems very polarized, with "AGI is just around the corner!" (seems unlikely) to "All these AI tools hallucinate and are generating useless crap" (not true).
In my world AI has been super-useful, saving me tons of time when it comes to kickstarting certain kinds of documents at work, proofreading, generating ideas, recapping meetings, summarizing long email threads I get added to, etc.
One area I don't see mentioned much where the latest crop of LLMs really excel is interpersonal issues. Having an issue with a difficult personality at work? Struggling with a personal relationship in some way? Having an issue with yourself even, e.g., "I find myself reacting in __ way in these kinds of situations and I'm not happy about it. What are some ways I could think about the situation differently?" I find that LLM's are very good at giving a balanced, impartial perspective on these kinds of issues.
Just came across this tool that lets you evaluate the output from several different LLMs at once. For now it's free with no login/account required, but will likely turned paid or bring-your-own-api-key at some point.
-
I find it useful for brainstorming stuff - present ideas, recipe ideas, that sort of thing. I can imagine it being good at relationship advice too.
Again - who predicted that lol?
Reply With Quote
Recommandations for Hollowbodies for $600 and under?
Today, 05:20 AM in Guitar, Amps & Gizmos