-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathpc.nw
More file actions
12816 lines (10980 loc) · 434 KB
/
pc.nw
File metadata and controls
12816 lines (10980 loc) · 434 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[10pt]{article}
\usepackage[margin=1.45in]{geometry}
\usepackage{graphicx}
\usepackage{noweb}
\usepackage{mflogo}
\usepackage{amsmath}
\usepackage{textcomp}
\noweboptions{smallcode,longchunks}
\usepackage{multirow}
\usepackage{hyperref}
\usepackage{pstricks}
\usepackage{subfig}
\usepackage{booktabs}
\usepackage[normalem]{ulem}
\usepackage{mathtools}
\usepackage{tabularx}
\usepackage{amssymb}
\useunder{\uline}{\ul}{}
\newcommand{\MyHdr}[6]{
\begin{tabularx}{\textwidth}{XXXXXX}
\hline
\textbf{UVa ID} & \textbf{Popularity} & \textbf{Success Rate} & \textbf{Level} & \textbf{Personal} & \textbf{Problem} \\
{#1} & {#2} & {#3} & {#4} & {#5} & \href{{#6}}{Link} \\ \hline
\end{tabularx}
\vspace{1mm}
}
\begin{document}
\pagestyle{myheadings}\markright{Programming Challenges\hfill \today\hfill}
\vskip 1in
\centerline{\bf Programming Challenges}
\centerline{Roman Valiu\v{s}enko}
\centerline{roman.valiusenko@gmail.com}
\begin{abstract}
This is a collection of literate programs. If you are unfamiliar with the idea
of literate programming please refer \cite{Knuth1984}. These programs are my
solutions to the programming tasks from the ``Programming Challenges''
book\cite{PC} which in turn is a collection of problems from the UVa Online
Judge hosted by University of Valladolid\footnote{If you are going to submit
any of these programs to the UVa Online Judge (which you obviously shouldn't)
make sure the class name is Main and that it is not in any package; Note that
for the class names I use problem names}. \end{abstract}
\tableofcontents
\newpage
\section{Getting Started}
\subsection{The $3n+1$ Problem}
\MyHdr{100}{A}{low}{1}{$\bigstar$}{https://uva.onlinejudge.org/external/1/100.pdf}
This task is not difficult if you notice that all the lengths of the sequences
can easily be calculated up front. Then all that is needed is to lookup
the pre-calculated table to find out the maximum lengths for the given input
numbers.
(I noticed though that I could have simply calculated the values on the file
without any tricks. The reason why I have done a more sophisticated algorithm
is that at first I though the input number may go up to 1M, but in reality,
according to the problem statement, they won't exceed 10000. So I solved a more
tricky problem.)
So let's start with the definitions of the array that will hold all the
[[lengths]] and the [[reader]] that will be used to read the input data.
<<3n+1>>=
<<1.1 Imports>>
class Collatz {
private static int MAX = 1000000;
private int[] lengths = new int[MAX];
private static final BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
<<1.1 Helpers>>
<<1.1 Constructor>>
<<1.1 Input/Output>>
}
@
We need the necessary imports:
<<1.1 Imports>>=
import java.io.BufferedReader;
import java.io.InputStreamReader;
@
The idea is to hold the lengths of the sequences in the [[lengths]], but
because the sequence member can sometimes go over 1M we will need to store
them somewhere temporarily. For that a [[surplus]] hash map will be used. Its
contents will be thrown away once the sequence lengths were computed.
So we write two helper methods: [[set]] and [[get]]. Both take an [[index]] and
[[surplus]] hash map and depending on the index value either use the array or
the hash map to set or get a value.
<<1.1 Imports>>=
import java.util.HashMap;
@
<<1.1 Helpers>>=
int get(long index, HashMap<Long, Integer> surplus) {
return (index < MAX) ? lengths[(int) index] :
(surplus.containsKey(index) ? surplus.get(index) : 0);
}
void set(long index, int value, HashMap<Long, Integer> surplus) {
if (index < MAX) {
lengths[(int) index] = value;
} else {
surplus.put(index, value);
}
}
@
Now we can easily pre-calculate all the lengths using the helper methods [[set]]
and [[get]], but we must not re-calculate the lengths for the indexes that we
have calculated already.
We calculate a member of the sequence at each step using the definition. Each
time we calculate a new member of the sequence we push it onto the [[stack]].
We stop if we notice that we already have the length calculated for that
specific value or when we reach 1. Now all the values that are on the stack are
potential inputs, that is they are all potential initial [[n]]s. We use this
knowledge to update elements in the [[lengths]]:
<<1.1 Imports>>=
import java.util.ArrayDeque;
import java.util.Deque;
@
<<1.1 Constructor>>=
Collatz() {
final HashMap<Long, Integer> surplus = new HashMap<Long, Integer>();
lengths[1] = 1;
for (long i = 2; i < MAX; ++i) {
final Deque<Long> stack = new ArrayDeque<Long>();
long n = i;
int len = 2;
while (n != 1) {
stack.push(n);
int prev = get(n, surplus);
if (prev > 0) {
len = prev;
break;
}
n = n % 2 == 0 ? n / 2 : n * 3 + 1;
}
while (!stack.isEmpty()) {
set(stack.pop(), len++, surplus);
}
}
}
@
Processing the input is easy but cumbersome\footnote{It turns out that the UVa
Judge tends to give some extra spaces here and there in the input, so we need
to make sure we account for some sporadic spaces in the input. This was my
first submission and it took me seven attempts before I got past that super
annoying "Runtime Error", because the judge was giving some extra spaces
between the values which my program was not taking into account.}:
<<1.1 Imports>>=
import java.util.stream.IntStream;
@
<<1.1 Input/Output>>=
public static void main(String[] args) {
Collatz s = new Collatz();
String input;
while ((input = reader.readLine()) != null &&
!input.trim().equalsIgnoreCase("")) {
List<String> str = Arrays.stream(input.trim().split(" "))
.filter(x -> !x.equals("")).collect(Collectors.toList());
int x[] = new int[] { Integer.parseInt(str.get(0)),
Integer.parseInt(str.get(1)) };
System.out.println(x[0] + " " + x[1] + " " +
IntStream.rangeClosed(Math.min(x[0], x[1]), Math.max(x[0],
x[1])).map(v -> s.lengths[v]).max().getAsInt());
}
}
@
\subsection{Minesweeper}
\MyHdr{10198}{A}{high}{1}{$\bigstar$}{https://uva.onlinejudge.org/external/101/10189.pdf}
This task is trivial: We simply count the number of mines around each cell.
There are eigth cells around each cell that we need to inspect. If our cell is
$(x, y)$, then we check $(x-1, y-1)$, $(x, y-1)$ and so on, and count the
number of cells that have '*' in them.
Our program structure is simple as usual:
<<Minesweeper>>=
<<1.2 Imports>>
class Minesweeper {
<<1.2 Constants>>
<<1.2 Main>>
}
@
Of course, we need a reader, so we define it next. Then we need to define the
constants. We are going to split the lines by spaces, so let's have it as a
constant. We also define an array of the offsets [[p]] to determine the
cells around a given cell.
<<1.2 Imports>>=
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
@
<<1.2 Constants>>=
private static final BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
private static final String SPACE = " ";
private static final int[][] p = new int[][] {
{ -1, -1 }, { 0, -1 }, { 1, -1 }, { -1, 0 },
{ 1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }
};
@
Now let's write the main method. I'll delibirately use one-dimentional array
instead of the two-dimensional, and I will use a couple of helper lambdas. One,
[[count]], to count the mines around a cell, and another, [[mine]], which
returns a cell value for the given coordinates.
<<1.2 Imports>>=
import static java.util.Arrays.stream;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
import static java.util.stream.IntStream.range;
import java.util.List;
import java.util.function.IntBinaryOperator;
import java.util.function.IntUnaryOperator;
@
<<1.2 Main>>=
public static void main(String[] args) throws IOException {
int lineNum = 0;
String currentLine = INPUT_END;
while ((currentLine = reader.readLine()) != null) {
if (currentLine.equalsIgnoreCase("")) {
continue;
}
List<Integer> nm = stream(currentLine.split(SPACE))
.filter(x -> !x.equals("")).map(Integer::parseInt).collect(toList());;
int n = nm.get(0);
int m = nm.get(1);
if (n == 0 && m == 0) {
break;
}
final int[] field = reader.lines().limit(n)
.collect(joining()).chars().map(x -> x == '*' ? -1 : 0).toArray();
final IntBinaryOperator mine =
(x, y) -> (x < 0 || x > (n - 1) || y < 0 || y > (m - 1)) ? 0 : field[x * m + y];
final IntUnaryOperator count = (i) -> range(0, p.length)
.map(j -> Math.abs(mine.applyAsInt(i / m + p[j][0], i % m + p[j][1]))).sum();
int[] result = range(0, field.length)
.map(x -> field[x] >= 0 ? count.applyAsInt(x) : field[x]).toArray();
if (lineNum > 0) {
System.out.println();
}
System.out.println("Field #" + (++lineNum) + ":");
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
System.out.print(result[i * m + j] == -1 ? "*" : result[i * m + j]);
}
System.out.println();
}
}
}
@
\subsection{The Trip}
\MyHdr{10137}{B}{averge}{1}{$\bigstar$}{https://uva.onlinejudge.org/external/101/10137.pdf}
This task is much more fun that the previous two. The important thing that we
should note for ourselves is that we are not going to use the floating point
types to do the calculations.
<<The Trip>>=
<<1.3 Imports>>
class TheTrip {
<<1.3 Calculation>>
<<1.3 Input/Output>>
}
@
First thing we need to do is to calculate the average spend, don't we? Because
we know that the input is a list of how much each of [[n]] students spent,
let's define a function that takes this list of values and returns the minimum
amount of money asked in the problem. Of course, the types will be [[long]].
And we can immediately cover the degenerate case of a input consisting of one
element:
<<1.3 Imports>>=
import static java.util.Arrays.stream;
@
<<1.3 Calculation>>=
static long calculate(long[] values) {
if (values.length == 1)
return 0;
long total = stream(values).sum();
<<1.3 Finding the minimum>>
}
@
Now we need to partition the students into two groups: One group of students
that will be giving money (those that spent less than group average) and the
ones who will be receiving the money (those that spent more than the group
average). But the [[total]] won't always divide without a reminder. So we
divide the [[total]] by the number of students to get the quotient and the
reminder, and we partition only using the quotient; that is group 1 will
contain spends $x$ such that $x - quotient \leq 0$, and group 2 will have the others.
<<1.3 Imports>>=
import static java.lang.Math.abs;
import static java.util.stream.Collectors.partitioningBy;
import java.util.List;
import java.util.Map;
@
<<1.3 Finding the minimum>>=
long quotient = total / values.length;
long reminder = total % values.length;
Map<Boolean, List<Long>> diff =
stream(values).map(x -> x - quotient).boxed().collect(partitioningBy(x -> x > 0));
@
So what do we do with the [[reminder]]? These are those cents that we need to
finally re-distribute among the members of the two groups. Note that the
[[reminder]] will always be less than [[n]]. We choose the following strategy:
We distribute these cents to the group that spent less than or equal to the
[[quotient]], the remaining cents are finally distributed to group 2. This is
captured in the following code:
<<1.3 Finding the minimum>>=
long sum = abs(diff.get(false).stream().reduce(Long::sum).get());
long len = diff.get(true).size();
reminder = len <= reminder ? reminder - len : 0;
return sum + reminder;
@
All we need to do now is to write input reading, which is trivial:
<<1.3 Imports>>=
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
@
<<1.3 Input/Output>>=
public static void main(String[] args) throws IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int n = 0;
while ((n = Integer.parseInt(r.readLine().trim())) > 0) {
long[] values = r.lines().limit(n).map(x -> x.replaceAll("\\.",
"").trim()).mapToLong(Long::parseLong).toArray();
System.out.println("$" + BigDecimal.valueOf(calculate(values), 2));
}
}
@
\subsection{LC Display}
\MyHdr{706}{A}{average}{1}{$\bigstar\bigstar$}{https://uva.onlinejudge.org/external/7/706.pdf}
This task may seem quite involved at first sight, because you may start
thinking about two-dimensional patterns and scaling functions. But in reality
this task is much easier if you notice that the digits can be constructed not in
a top to bottom (or bottom to up) row-by-row manner, but in a columnar manner;
at the same time scaling becomes very easy.
<<LC Display>>=
<<1.4 Imports>>
class LCDisplay {
<<1.4 Constants>>
<<1.4 Convertion>>
<<1.4 Input/Output>>
}
@
Each LCD digit has 7 segments: Two in the first and the third columns and
three in the second column. Let's encode our digits as in the table.
\begin{table}
\begin{center}
\begin{tabular}{ l | l | l }
\hline
Digit & Binary & Hex \\
\hline
0 & 11 101 11 & 77 \\
1 & 00 000 11 & 03 \\
2 & 10 111 01 & 5D \\
3 & 00 111 11 & 1F \\
4 & 01 010 11 & 2B \\
5 & 01 111 10 & 3E \\
6 & 11 111 10 & 7E \\
7 & 00 001 11 & 07 \\
8 & 11 111 11 & 7F \\
9 & 01 111 11 & 3F \\
\hline
\end{tabular}
\caption{LCD segments}
\end{center}
\end{table}
Since we know that the input ends in two zeros we define this string constant
plus a couple of other string constants.
<<1.4 Imports>>=
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.Stream;
@
<<1.4 Constants>>=
private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
private static final String INPUT_END = "0 0";
private static final String EMPTY = "";
private static final String SPACE = " ";
private static final byte[] pattern = new byte[] {
0x77, 0x03, 0x5d, 0x1f, 0x2b, 0x3e, 0x7e, 0x07, 0x7f, 0x3f
};
@
The array [[pattern]] for the given digit [[i]] returns bits that correspond to
the segments, so for example [[digits[5]]] would return segments for digit 5.
We will be using masks to discover which bits are set and not set.
But let's write input/output first as this is very easy. At the same time, let's
assume our method that converts a string into LCD style digits is called
[[segments]]. This method takes two arguments, the digits string and [[scale]].
Let's assume it returns list of strings which we can simply output to the console.
<<1.4 Input/Output>>=
public static void main(String[] args) throws IOException {
String currentLine = INPUT_END;
while ((currentLine = reader.readLine()) != null &&
!currentLine.trim().equalsIgnoreCase(INPUT_END)) {
List<String> input = Arrays.stream(currentLine.trim().split(SPACE))
.filter(x -> !x.equals("")).collect(Collectors.toList());
segments(input.get(1), Integer.valueOf(input.get(0))).stream()
.forEach(System.out::println);
System.out.println();
}
}
@
Now all that's left is to implement [[segments]].
<<1.4 Convertion>>=
private static List<String> segments(final String digits, final int scale) {
<<1.4 Helpers>>
<<1.4 Process>>
<<1.4 Return>>
}
@
The idea is simple: We check bit 6 and bit 5 of the pattern and construct ASCII
representation of the first column, then we check bit 4, 3, and 2 and construct
the middle column, finally we check bit 1 and 0 to construct the last column.
Of course, we need to take into account the scaling.
So let's have a look at an example. Let's say we need to construct digit 2 with
scale 3. First, we get the pattern value [[pattern[2]]]=5D, or 1011101.
Then, we start with the masks $40$ and $20$ to see which segments are on in the
first column (bit 6 and bit 5); so, [[40 & 5D = 1]] and [[20 & 5D = 0]], which
means that the first segment is on and the second is off, so we output
$\textvisiblespace\vert\textvisiblespace\textvisiblespace\textvisiblespace$.
Because our scale is 3, we output $\vert$ and $\textvisiblespace$ three times,
so we end up with
$\textvisiblespace\vert\vert\vert\textvisiblespace\textvisiblespace\textvisiblespace\textvisiblespace\textvisiblespace$;
Similarly we construct the third column, but we use different masks: $02$ and
$01$.
OK, let's write some helpers already before we get back to producing the
middle column. We will need some function that replicates a specified string
$n$ times. There's a Java function [[nCopies]] that does that, so we will use
it. However, it returns a list of strings, therefore we use [[join]] function
to join that into a single string using [[EMPTY]] as a delimiter. Let's write
that:
<<1.4 Imports>>=
import static java.lang.String.join;
import static java.util.Collections.nCopies;
import java.util.function.Function;
@
<<1.4 Helpers>>=
Function<String, String> g = x -> join(EMPTY, nCopies(scale, x));
@
Note that we use the fact that the [[scale]] is captured in the closure.
OK, we also need a mapping function that checks which bits are on and off in
the given value using the list of masks. Depending on whether bits are on or
off it returns ASCII character $\vert$ or $\textvisiblespace$. It will be a
stream of such characters:
<<1.4 Helpers>>=
BiFunction<Stream<Integer>, Byte, Stream<String>> h =
(m, x) -> m.map(mask -> (x & mask) > 0 ? "|" : SPACE);
@
Here [[m]] is a stream of masks, and [[x]] is the value [[pattern[i]]] for some
[[i]]. Note the function returns a stream as well.
Now we can write a function that constructs a column of our LCD digit. Let's
call it [[k]]:
<<1.4 Imports>>=
import static java.util.stream.Collectors.joining;
import java.util.function.BiFunction;
@
<<1.4 Helpers>>=
BiFunction<Stream<Integer>, Byte, String> k =
(m, d) -> SPACE + h.apply(m, d).map(x -> g.apply(x)).collect(joining(SPACE)) + SPACE;
@
Note [[SPACE]]s around (as per requirement) and that the segments within a
column are joined by a space.
So far so good. Basically we can now write function [[f]] that takes a digit
pattern [[pattern[i]]] and returns a stream of strings (in fact, the columns of
our LCD digits).
<<1.4 Imports>>=
import static java.util.stream.Collectors.toList;
import static java.util.stream.Stream.of;
import java.util.Arrays;
@
<<1.4 Helpers>>=
final int digitHeight = scale * 2 + 3;
Function<Byte, Stream<String>> f = x -> Arrays.asList(
of(k.apply(of(0x40, 0x20), x)),
<<1.4 Middle Column Construction>>,
of(k.apply(of(0x02, 0x01), x)),
of(join(EMPTY, nCopies(digitHeight, SPACE))))
.stream().reduce(Stream::concat).get();
@
Also note the last line which adds spaces between consecutive digits.
Finally, let's get back to the middle of the digit. To contruct it, we will
re-use exactly the same functions we've already defined. We use [[h]] to obtain
the segments that are on and off. Note though that [[h]] returns $\vert$
symbols, not the dashes, which are used to indicate horizontal LCD segments. So
we will need to replace all occurances of vertical bars with dashes. It's easy
to see that the number of spaces between the horizontal segments will be
exactly [[scale]], which is already captured in the [[g]] function
implementation. Finally, all we need to do, is to replicate the middle column
[[scale]] times. All this can be very easily implemented like so:
<<1.4 Middle Column Construction>>=
nCopies(scale, h.apply(of(0x10, 0x08, 0x04), x)
.collect(joining(g.apply(SPACE))).replace('|', '-')).stream()
@
Now we can map the string of digits using our [[f]] function:
<<1.4 Imports>>=
import java.util.List;
@
<<1.4 Process>>=
List<String> segments = digits.chars().map(x -> x - '0').boxed()
.flatMap(x -> f.apply(pattern[x])).collect(toList());
@
But remember, this gives us a list of columns of the LCD digits, not rows, so
before returning it we need a little post-processing: For each column we take
the last characters, concatenate these last characters into a string, and add
to a list; then we take the next to the last characters and do the same, and so
on:
<<1.4 Imports>>=
import static java.util.stream.IntStream.range;
import static java.util.stream.IntStream.rangeClosed;
@
<<1.4 Return>>=
return rangeClosed(1, digitHeight).boxed()
.map(j -> digitHeight - j).map(j -> range(0, segments.size() - 1).boxed()
.map(i -> Character.toString(segments.get(i).charAt(j))).collect(joining())).collect(toList());
@
And that completes the program.
\subsection{Graphical Editor}
\MyHdr{10267}{B}{low}{1}{$\bigstar$}{https://uva.onlinejudge.org/external/102/10267.pdf}
Very straightforward task. The only difficult part being the [[fill]]
operation, but I leave it without comments either as the code is
self-explanatory.
<<Graphical Editor>>=
import static java.util.Arrays.stream;
import static java.util.stream.Collectors.toList;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
public class GraphicalEditor {
private static final BufferedReader reader = new BufferedReader(
new InputStreamReader(System.in));
private int[][] canvas;
private int m = 0, n = 0;
private void clear() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
canvas[j][i] = 'O';
}
}
}
private void execute(List<String> command) {
int x, y1, y2, y, x1, x2, c;
switch (command.get(0)) {
case "I":
m = Integer.parseInt(command.get(1));
n = Integer.parseInt(command.get(2));
canvas = new int[m][n];
clear();
break;
case "C":
clear();
break;
case "L":
x = Integer.parseInt(command.get(1)) - 1;
y = Integer.parseInt(command.get(2)) - 1;
canvas[x][y] = command.get(3).charAt(0);
break;
case "V":
x = Integer.parseInt(command.get(1)) - 1;
y1 = Integer.parseInt(command.get(2)) - 1;
y2 = Integer.parseInt(command.get(3)) - 1;
c = command.get(4).charAt(0);
for (y = Math.min(y1, y2); y <= Math.max(y1, y2); ++y) {
canvas[x][y] = c;
}
break;
case "H":
x1 = Integer.parseInt(command.get(1)) - 1;
x2 = Integer.parseInt(command.get(2)) - 1;
y = Integer.parseInt(command.get(3)) - 1;
c = command.get(4).charAt(0);
for (x = Math.min(x1, x2); x <= Math.max(x1, x2); ++x) {
canvas[x][y] = c;
}
break;
case "K":
x1 = Integer.parseInt(command.get(1)) - 1;
y1 = Integer.parseInt(command.get(2)) - 1;
x2 = Integer.parseInt(command.get(3)) - 1;
y2 = Integer.parseInt(command.get(4)) - 1;
c = command.get(5).charAt(0);
for (x = x1; x <= x2; ++x) {
for (y = y1; y <= y2; ++y) {
canvas[x][y] = c;
}
}
break;
case "F":
x = Integer.parseInt(command.get(1)) - 1;
y = Integer.parseInt(command.get(2)) - 1;
int newColor = command.get(3).charAt(0);
int oldColor = canvas[x][y];
fill(new Point(x, y), oldColor, newColor);
break;
case "S":
String name = command.get(1);
System.out.println(name);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
System.out.print((char) canvas[j][i]);
}
System.out.println();
}
break;
default:
break;
}
}
private static class Point {
final int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
private void fill(Point pt, int oldColor, int newColor) {
if (canvas[pt.x][pt.y] != oldColor || oldColor == newColor) {
return;
}
Deque<Point> q = new ArrayDeque<>();
q.addLast(pt);
canvas[pt.x][pt.y] = newColor;
while (!q.isEmpty()) {
pt = q.pop();
if (pt.x + 1 < m && canvas[pt.x + 1][pt.y] == oldColor) {
canvas[pt.x + 1][pt.y] = newColor;
q.addLast(new Point(pt.x + 1, pt.y));
}
if (pt.x - 1 >= 0 && canvas[pt.x - 1][pt.y] == oldColor) {
canvas[pt.x - 1][pt.y] = newColor;
q.addLast(new Point(pt.x - 1, pt.y));
}
if (pt.y + 1 < n && canvas[pt.x][pt.y + 1] == oldColor) {
canvas[pt.x][pt.y + 1] = newColor;
q.addLast(new Point(pt.x, pt.y + 1));
}
if (pt.y - 1 >= 0 && canvas[pt.x][pt.y - 1] == oldColor) {
canvas[pt.x][pt.y - 1] = newColor;
q.addLast(new Point(pt.x, pt.y - 1));
}
}
}
public static void main(String[] args) throws IOException {
GraphicalEditor editor = new GraphicalEditor();
String currentLine;
while ((currentLine = reader.readLine()) != null) {
List<String> command = stream(currentLine.trim().split(" "))
.filter(x -> !x.equals("")).collect(toList());
if (command.get(0).equalsIgnoreCase("X")) {
break;
}
editor.execute(command);
}
}
}
@
\subsection{Interpreter}
\MyHdr{10033}{B}{low}{2}{$\bigstar$}{https://uva.onlinejudge.org/external/100/10033.pdf}
This task is disappointingly straightforward.
<<Interpreter>>=
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
class Interpreter {
private static final BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
private static int interpret(List<Integer> input) {
int[] reg = new int[10];
int[] ram = new int[1000];
for (int i = 0; i < input.size(); ++i) {
ram[i] = input.get(i);
}
int pc = 0;
int r = 0;
while (ram[pc] != 100) {
int op = ram[pc];
int c = (op / 100) % 10;
pc = (pc + 1) % 1000;
r++;
switch (c) {
case 2:
reg[(op / 10) % 10] = op % 10;
break;
case 3:
reg[(op / 10) % 10] = (reg[(op / 10) % 10] + (op % 10)) % 1000;
break;
case 4:
reg[(op / 10) % 10] = (reg[(op / 10) % 10] * (op % 10)) % 1000;
break;
case 5:
reg[(op / 10) % 10] = reg[op % 10];
break;
case 6:
reg[(op / 10) % 10] = (reg[(op / 10) % 10] + reg[op % 10]) % 1000;
break;
case 7:
reg[(op / 10) % 10] = (reg[(op / 10) % 10] * reg[op % 10]) % 1000;
break;
case 8:
reg[(op / 10) % 10] = ram[reg[op % 10]];
break;
case 9:
ram[reg[op % 10]] = reg[(op / 10) % 10];
break;
case 0:
if (reg[op % 10] != 0) {
pc = reg[(op / 10) % 10];
}
break;
}
}
return r + 1;
}
public static void main(String[] args) throws IOException {
int n = Integer.valueOf(reader.readLine().trim());
reader.readLine();
String currentLine;
for (int i = 0; i < n; ++i) {
List<Integer> input = new ArrayList<Integer>();
while ((currentLine = reader.readLine()) != null &&
!currentLine.trim().equalsIgnoreCase("")) {
input.add(Integer.parseInt(currentLine.trim()));
}
System.out.println(interpret(input));
if (i < n - 1) {
System.out.println();
}
}
}
}
@
\subsection{Check The Check}
\MyHdr{10196}{B}{average}{1}{$\bigstar$}{https://uva.onlinejudge.org/external/101/10196.pdf}
This task is trivial.
<<Check The Check>>=
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class CheckTheCheck {
private static final BufferedReader reader = new BufferedReader(
new InputStreamReader(System.in));
private static final int BOARD_SIZE = 8;
private static final int[][] king = new int[][] {
{ -1, -1 }, { 0, -1 }, { 1, -1 }, { -1, 0 }, { 1, 0 }, { -1, 1 },
{ 0, 1 }, { 1, 1 }
};
private static final int[][] knight = new int[][] {
{ -2, -1 }, { -1, -2 }, { 1, -2 }, { 2, -1 }, { 2, 1 }, { 1, 2 },
{ -1, 2 }, { -2, 1 }
};
private static final int[][] bishop = new int[][] {
{ 1, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 }
};
private static final int[][] rook = new int[][] {
{ 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }
};
private static final int[][] queen = new int[][] {
{ 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 1, 1 }, { -1, -1 },
{ -1, 1 }, { 1, -1 }
};
private static final int[][] white_pawn = new int[][] {
{ -1, -1 }, { -1, 1 }
};
private static final int[][] black_pawn = new int[][] {
{ 1, -1 }, { 1, 1 }
};
private static boolean isWithinBounds(int d, int v) {
if (d == 0) {
return true;
}
return d > 0 ? (v < BOARD_SIZE) : (v >= 0);
}
private static void check(int di, int dj, int i, int j, int[][] board,
int[][] attackBoard) {
int c = j + dj;
int r = i + di;
while (isWithinBounds(dj, c) && isWithinBounds(di, r)) {
attackBoard[r][c] = 1;
if (board[r][c] != '.')
break;
r += di;
c += dj;
}
}
private static void check(int[][] d, int i, int j, int[][] board,
int[][] attackBoard) {
if (d == king || d == knight || d == black_pawn || d == white_pawn) {
for (int k = 0; k < d.length; ++k) {
if ((i + d[k][0] >= 0 && i + d[k][0] < BOARD_SIZE) &&
(j + d[k][1] >= 0 && j + d[k][1] < BOARD_SIZE)) {
attackBoard[i + d[k][0]][j + d[k][1]] = 1;
}
}
return;
}
for (int k = 0; k < d.length; ++k) {
check(d[k][0], d[k][1], i, j, board, attackBoard);
}
}
private static int[] locate(int v, int[][] board) {
for (int i = 0; i < BOARD_SIZE; ++i) {
for (int j = 0; j < BOARD_SIZE; ++j) {
if (board[i][j] == v) {
return new int[] { i, j };
}
}
}
return null;
}
private static String checkTheCheck(int[][] board) {
int[][] attackBoardWhites = new int[BOARD_SIZE][BOARD_SIZE];
int[][] attackBoardBlacks = new int[BOARD_SIZE][BOARD_SIZE];
for (int i = 0; i < BOARD_SIZE; ++i) {
for (int j = 0; j < BOARD_SIZE; ++j) {
if (board[i][j] == 'R' || board[i][j] == 'r') {
check(rook, i, j, board, board[i][j] == 'R'
? attackBoardWhites : attackBoardBlacks);
}
if (board[i][j] == 'B' || board[i][j] == 'b') {
check(bishop, i, j, board, board[i][j] == 'B'
? attackBoardWhites : attackBoardBlacks);
}
if (board[i][j] == 'K' || board[i][j] == 'k') {
check(king, i, j, board, board[i][j] == 'K'
? attackBoardWhites : attackBoardBlacks);
}
if (board[i][j] == 'N' || board[i][j] == 'n') {
check(knight, i, j, board, board[i][j] == 'N'
? attackBoardWhites : attackBoardBlacks);
}
if (board[i][j] == 'Q' || board[i][j] == 'q') {
check(queen, i, j, board, board[i][j] == 'Q'
? attackBoardWhites : attackBoardBlacks);
}
if (board[i][j] == 'P' || board[i][j] == 'p') {
boolean isWhite = board[i][j] == 'P';
check(isWhite ? white_pawn : black_pawn, i, j, board,
isWhite ? attackBoardWhites : attackBoardBlacks);
}
}
}
int[] wk = locate('K', board);
int[] bk = locate('k', board);
boolean bkCheck = (attackBoardWhites[bk[0]][bk[1]] == 1);
boolean wkCheck = (attackBoardBlacks[wk[0]][wk[1]] == 1);
if (wkCheck) {
return "white king is in check.";
}
if (bkCheck) {
return "black king is in check.";
}
return "no king is in check.";
}
public static void main(String[] args) throws IOException {
boolean empty = true;
int game = 1;