Skip to content

Instantly share code, notes, and snippets.

@adamcrussell

adamcrussell/ch-1.p

Created Sep 6, 2020
Embed
What would you like to do?
Perl Weekly Challenge 076
primes([2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83
,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,
181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,
281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,
397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,
619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,
743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,
863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,
997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,
1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,
1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,
1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,
1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,
1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,
1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,
1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,
1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,
1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,
2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,
2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,
2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,
2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,
2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,
2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,
2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,
2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,
2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,
3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,
3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,
3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,
3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,
3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,
3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,
3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,
3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,
3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,
4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,
4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,
4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,
4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,
4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,
4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,
4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,
4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,
5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,
5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,
5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,
5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,
5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,
5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,
5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,
5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,
6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,
6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,
6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,
6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,
6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,
6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,
6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,
6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,
6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,
7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,
7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,
7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,
7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,
7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,
7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,
7873,7877,7879,7883,7901,7907,7919]).
nearest_prime(N, [H|T], Prime):-
N >= H,
N0 is N - H,
(N0 == 0; N0 >= 2; N0 >=3),
Prime is H,!;
nearest_prime(N, T, Prime).
prime_sum(N, Primes, Sum):-
prime_sum(N, Primes, [], Sum).
prime_sum(0, _, Sum, Sum).
prime_sum(N, Primes, SumAccum, Sum):-
nearest_prime(N, Primes, H),
N0 is N - H,
N0 >= 0,
prime_sum(N0, Primes, [H|SumAccum], Sum).
main:-
write("N: "),
read(N),
primes(Primes),
reverse(Primes, PrimesDescending),
prime_sum(N, PrimesDescending, Sum),
write(Sum),
write(" sum to "),
writeln(N),
halt.
use strict;
use warnings;
##
# You are given a number $N.
# Write a script to find the minimum number
# of prime numbers required, whose summation gives you $N.
##
my @primes = (
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,
89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,
181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,
281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,
397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,
619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,
743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,
863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,
997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,
1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,
1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,
1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,
1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,
1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,
1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,
1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,
1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,
1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,
2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,
2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,
2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,
2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,
2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,
2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,
2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,
2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,
2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,
3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,
3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,
3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,
3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,
3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,
3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,
3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,
3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,
3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,
4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,
4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,
4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,
4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,
4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,
4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,
4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,
4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,
5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,
5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,
5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,
5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,
5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,
5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,
5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,
5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,
6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,
6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,
6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,
6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,
6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,
6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,
6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,
6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,
6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,
7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,
7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,
7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,
7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,
7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,
7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,
7873,7877,7879,7883,7901,7907,7919
);
@primes = reverse(@primes);
sub nearest_prime{
my($n) = @_;
for my $i (0..@primes){
return $primes[$i] if($n == $primes[$i]);
if($n > $primes[$i] && ($n - $primes[$i] >=2 || $n - $primes[$i] >=3)){
return $primes[$i];
}
}
return undef;
}
sub prime_sum{
my($n) = @_;
my @p;
while($n > 0){
my $p = nearest_prime($n);
push @p, $p;
$n = $n - $p;
}
return @p;
}
MAIN:{
my $n = $ARGV[0];
my @p = prime_sum($n);
print join(" + ",@p) . " = $n\n";
}
word_grid([
["B","I","D","E","M","I","A","T","S","U","C","C","O","R","S","T"],
["L","D","E","G","G","I","W","Q","H","O","D","E","E","H","D","P"],
["U","S","E","I","R","U","B","U","T","E","A","S","L","A","G","U"],
["N","G","N","I","Z","I","L","A","I","C","O","S","C","N","U","D"],
["T","G","M","I","D","S","T","S","A","R","A","R","E","I","F","G"],
["S","R","E","N","M","D","C","H","A","S","I","V","E","E","L","I"],
["S","C","S","H","A","E","U","E","B","R","O","A","D","M","T","E"],
["H","W","O","V","L","P","E","D","D","L","A","I","U","L","S","S"],
["R","Y","O","N","L","A","S","F","C","S","T","A","O","G","O","T"],
["I","G","U","S","S","R","R","U","G","O","V","A","R","Y","O","C"],
["N","R","G","P","A","T","N","A","N","G","I","L","A","M","O","O"],
["E","I","H","A","C","E","I","V","I","R","U","S","E","S","E","D"],
["S","E","T","S","U","D","T","T","G","A","R","L","I","C","N","H"],
["H","V","R","M","X","L","W","I","U","M","S","N","S","O","T","B"],
["A","E","A","O","F","I","L","C","H","T","O","D","C","A","E","U"],
["Z","S","C","D","F","E","C","A","A","I","I","R","L","N","R","F"],
["A","R","I","I","A","N","Y","U","T","O","O","O","U","T","P","F"],
["R","S","E","C","I","S","N","A","B","O","S","C","N","E","R","A"],
["D","R","S","M","P","C","U","U","N","E","L","T","E","S","I","L"]
]).
grid_strings(Grid, Strings):-
grid_strings(Grid, [], Strings).
grid_strings([], Strings, Strings).
grid_strings([H|T], StringAccum, Strings):-
atomics_to_string(H, S),
grid_strings(T, [S|StringAccum], Strings).
read_word(InStream,W):-
get_code(InStream,Char),
check_char_read(Char,Chars,InStream),
atom_codes(W,Chars).
check_char_read(10,[],_):- !.
check_char_read(32,[],_):- !.
check_char_read(-1,[],_):- !.
check_char_read(end_of_file,[],_):- !.
check_char_read(Char,[Char|Chars],InStream):-
get_code(InStream,NextChar),
check_char_read(NextChar,Chars,InStream).
read_file(S, []):-
at_end_of_stream(S).
read_file(S, end_of_stream):-
at_end_of_stream(S).
read_file(S, [H|T]):-
\+ at_end_of_stream(S),
read_word(S, H),
read_file(S, T).
row_length([H|_], Columns):-
length(H, Columns).
column([H|T], Counter, C, Value):-
C0 is Counter + 1,
C0 == C,
Value is H;
C0 is Counter + 1,
column(T, C0, C, Value).
column_values([], _, _, Values, Values).
column_values([L|T], C, Columns, ValAccum, Values):-
C0 is C + 1,
C0 =< Columns,
column(L, 0, C0, Value),
column_values(T, C0, Columns, [Value | ValAccum], Values);
C0 is C + 1, C0 > Columns, column_values([], C0, Columns, ValAccum, Values).
diagonals([H|T], SubDiagonals):-
row_length([H|T], Columns),
diagonals([H|T], 0, Columns, [], SubDiagonals).
diagonals([], _, _, Diagonals, Diagonals).
diagonals([H|T], C, Columns, DiagAccum, SubDiagonals):-
column_values([H|T], C, Columns, [], D),
C0 is C + 1,
C0 =< Columns,
string_codes(S, D),
diagonals([H|T], C0, Columns, [S|DiagAccum], SubDiagonals);
diagonals(T, 0, Columns, DiagAccum, SubDiagonals).
word_found(_, []):-
fail.
word_found(Word, [H|T]):-
sub_string(H, _, _, _, Word);
word_found(Word, T).
word_search(Dictionary, Grid, Words):-
word_search(Dictionary, Grid, [], Words).
word_search([], _, Words, Words).
word_search([H|T], Grid, WordAccum, Words):-
string_upper(H, W),
word_found(W, Grid),
word_search(T, Grid, [W|WordAccum], Words);
word_search(T, Grid, WordAccum, Words).
main:-
open("words", read, S), %http://www-personal.umich.edu/~jlawler/wordlist.html
read_file(S, Lines),
close(S),
word_grid(WG),
diagonals(WG, Diagonals0),
reverse(WG, GW),
diagonals(GW, Diagonals1),
grid_strings(WG, Strings),
flatten([Strings, Diagonals0, Diagonals1], Grid),
word_search(Lines, Grid, Words),
writeln(Words),
halt.
use strict;
use warnings;
##
# Word Search
##
my @word_grid = (
["B","I","D","E","M","I","A","T","S","U","C","C","O","R","S","T"],
["L","D","E","G","G","I","W","Q","H","O","D","E","E","H","D","P"],
["U","S","E","I","R","U","B","U","T","E","A","S","L","A","G","U"],
["N","G","N","I","Z","I","L","A","I","C","O","S","C","N","U","D"],
["T","G","M","I","D","S","T","S","A","R","A","R","E","I","F","G"],
["S","R","E","N","M","D","C","H","A","S","I","V","E","E","L","I"],
["S","C","S","H","A","E","U","E","B","R","O","A","D","M","T","E"],
["H","W","O","V","L","P","E","D","D","L","A","I","U","L","S","S"],
["R","Y","O","N","L","A","S","F","C","S","T","A","O","G","O","T"],
["I","G","U","S","S","R","R","U","G","O","V","A","R","Y","O","C"],
["N","R","G","P","A","T","N","A","N","G","I","L","A","M","O","O"],
["E","I","H","A","C","E","I","V","I","R","U","S","E","S","E","D"],
["S","E","T","S","U","D","T","T","G","A","R","L","I","C","N","H"],
["H","V","R","M","X","L","W","I","U","M","S","N","S","O","T","B"],
["A","E","A","O","F","I","L","C","H","T","O","D","C","A","E","U"],
["Z","S","C","D","F","E","C","A","A","I","I","R","L","N","R","F"],
["A","R","I","I","A","N","Y","U","T","O","O","O","U","T","P","F"],
["R","S","E","C","I","S","N","A","B","O","S","C","N","E","R","A"],
["D","R","S","M","P","C","U","U","N","E","L","T","E","S","I","L"]
);
sub get_diagonals{
my @diagonals;
for my $i (0..@{$word_grid[0]}){
my @d;
push @d, $word_grid[0]->[$i];
my $j = 1;
my $k = $i;
while($j < @word_grid && $k < @{$word_grid[$j]}){
$k++;
push @d, $word_grid[$j]->[$k];
$j++;
}
push @diagonals, \@d;
}
return @diagonals;
}
sub get_reverse_diagonals{
my @reverse_grid = reverse(@word_grid);
my @diagonals;
for my $i (0..@{$reverse_grid[0]}){
my @d;
push @d, $reverse_grid[0]->[$i];
my $j = 1;
my $k = $i;
while($j < @reverse_grid && $k < @{$reverse_grid[$j]}){
$k++;
push @d, $reverse_grid[$j]->[$k];
$j++;
}
push @diagonals, \@d;
}
return @diagonals;
}
sub get_columns{
my @columns;
for my $i (0..@{$word_grid[0]}){
$columns[$i] = [];
for my $j (0..@word_grid){
push @{$columns[$i]}, $word_grid[$j]->[$i];
}
}
return @columns;
}
sub word_search{
my($words, $search) = @_;
my @found;
for my $s (@{$search}){
my @s = grep defined, @{$s};
$s = join("", @s);
for my $w (@{$words}){
my $u = uc($w);
my $r = reverse($u);
push @found, lc($w) if(($s =~ m/\Q$u/ || $s =~ m/\Q$r/) && length($w) > 3);
}
}
return @found;
}
MAIN:{
my @search=(get_columns(), get_diagonals(), get_reverse_diagonals(), @word_grid);
open(WORDS, "words");
my $words = do{
local $/;
<WORDS>;
};
close(WORDS);
my @words = split(/\n/, $words);
my @found_words = sort {$a cmp $b} word_search(\@words, \@search);
print "Found the following words: " . join(",", @found_words) . "\n";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.